DOC PREVIEW
GSU CSC 2320 - Chapter 3

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Chapter 3 Data Structures and Abstract Data TypeOutlineA first look an ADTsAbstract Data Type (ADT)ADT exampleImplementation of ADTData Structures, Abstract Data Types, and ImplementationsSlide 8Use 10 individual variablesSlide 10Use ArrayADTsData Structure and Abstract Data TypeSlide 14Array ADTDifferent types of ArrayOne-Dimensional Static ArrayArray and ADTExample of arrayArray Output FunctionMultidimensional ArraysArray of Array DeclarationsSlide 23Slide 24Slide 25Chapter 3 Data Structures and Abstract Data TypeDr. Bernard Chen Ph.D.University of Central ArkansasFall 2008OutlineIntroduction to Abstract Data Types (ADTs)ArraysA first look an ADTsSolving a problem involves processing data, and an important part of the solution is the careful organization of the dataIn order to do that, we need to identify:1. The collection of data items 2. Basic operation that must be performed on themAbstract Data Type (ADT): a collection of data items together with the operations on the dataAbstract Data Type (ADT)The word “abstract” refers to the fact that the data and the basic operations defined on it are being studied independently of how they are implementedWe think about what can be done with the data, not how it is doneADT exampleImplementation of ADTAn implementation of ADT consists of storage structures to store the data items and algorithms for basic operationData Structures, Abstract Data Types, and ImplementationsConsider example of an airplane flight with 10 seats to be assignedTasksList available seatsReserve a seatHow to store, access data?Data Structures, Abstract Data Types, and ImplementationsConsider example of an airplane flight with 10 seats to be assignedTasksList available seatsReserve a seatHow to store, access data?10 individual variablesUse 10 individual variablesAlgorithm to List available seats1. If seat1 == ‘ ’:display 12. If seat2 == ‘ ’: display 2...10. If seat10 == ‘ ’: display 10Algorithm to Reserve a seat1. Set DONE to false2. If seat1 ==‘ ’:print “do you want seat #1??”Get answerif answer==‘Y’:set seat1 to ‘X’set Done to True3. If seat2 ==‘ ’:print “do you want seat #2??”Get answerif answer==‘Y’:set seat2 to ‘X’set Done to True...Data Structures, Abstract Data Types, and ImplementationsConsider example of an airplane flight with 10 seats to be assignedTasksList available seatsReserve a seatHow to store, access data?10 individual variablesAn array of variablesUse ArrayAlgorithm to List available seatsFor number ranging from 0 to max_seats-1, do:If seat[number] == ‘ ’:Display numberAlgorithm to Reserve a seatReadin number of seat to be reservedIf seat[number] is equal to ‘ ’:set seat[number] to ‘X’ElseDisplay a message that the seat having this number is occupiedADTsIn this simple example, it does illustrate the concept of an Abstract Data Type ADT consists of1. The collection of data items 2. Basic operation that must be performed on themIn the example, a collection of data is a list of seatsThe basic operations are (1) Scan the list to determine which seats are occupied (2) change seat’s statusData Structure and Abstract Data TypeThe term of Data Structure and Abstract Data Type are often used interchangeablyHowever, we use ADT when data is studied at a logical levelThe term data structure refers to a construct in programming language that can be used to store dataOutlineIntroduction to Abstract Data Types (ADTs)ArraysArray ADTCollection of data elementsA fixed-size sequence of elements, all of the same typeBasic OperationsDirect access to each element in the array by specifying its position so that values can be retrieved from or stored in that positionDifferent types of ArrayOne-dimensional array: only one index is usedMulti-dimensional array: array involving more than one index Static array: the compiler determines how memory will be allocated for the arrayDynamic array: memory allocation takes place during executionOne-Dimensional Static ArraySyntax:ElementType arrayName [CAPACITY];ElementType arrayName [CAPACITY] = { initializer_list };Example:int b [10];int b [10]={1,2,3,4,5,6,7,8,9,10};Array and ADTCollection of data elementsA fixed-size sequence of elements, all of the same typeBasic OperationsDirect access to each element in the array by specifying its position so that values can be retrieved from or stored in that positionAn Array as an ADT C++ ArrayFixed size ----------------------specify the capacity of the arrayOrdered-------------------------indices are numbered 0,1,2,…,capacity-1 Same type of elements-------specify the element type Direct access-------------------subscript operator[]Example of arrayConsider array a,b,c,d to store collection of 10 integers declared by:int capacity=10int a[capacity], b[capacity]={1,2,3,4,5,6,7,8,9,10}, c[capacity]={1,2,3}, d[capacity]={0};char name[capacity]=“John Doe”;Array Output FunctionVoid display(int array[], int num_values){for (int I = 0; i<num_values; i++)cout<< array[i] << “ ”;}Multidimensional ArraysConsider a table of test scores for several different studentsArray of Array DeclarationsAn array of arraysAn array whose elements are other arraysArray of Array DeclarationsEach of the rows is itself a one dimensional array of valuesscoresTable[2]is the whole row numbered 2scoresTable[2]is the whole row numbered 2scoresTable [1][3]scoresTable [1][3]Multidimensional ArraysSyntax: ElementType arrayName [num_rows][num_columns];int scoretable [num_students][num_tests];int scoretable[2][5]={{80,80,80,80,80},{60,60,60,60,60}};If you want to change the score of first student’s 3rd test score to 100, you just need to do:Scoretable[0][2]=100Multidimensional ArraysConsider multiple pages of the student grade booktypedef double ThreeDimArray[NUM_ROWS][NUM_COLS][NUM_RANKS]; . .


View Full Document

GSU CSC 2320 - Chapter 3

Download Chapter 3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?