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 2008OutlineIntroduction to Abstract Data Types (ADTs)ArraysA first look an ADTsSolving a problem involves processing data, and an important part of the solution is the careful organization of the dataIn order to do that, we need to identify:1. The collection of data items 2. Basic operation that must be performed on themAbstract 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 implementedWe think about what can be done with the data, not how it is doneADT exampleImplementation of ADTAn implementation of ADT consists of storage structures to store the data items and algorithms for basic operationData Structures, Abstract Data Types, and ImplementationsConsider example of an airplane flight with 10 seats to be assignedTasksList available seatsReserve a seatHow to store, access data?Data Structures, Abstract Data Types, and ImplementationsConsider example of an airplane flight with 10 seats to be assignedTasksList available seatsReserve a seatHow to store, access data?10 individual variablesUse 10 individual variablesAlgorithm to List available seats1. If seat1 == ‘ ’:display 12. If seat2 == ‘ ’: display 2...10. If seat10 == ‘ ’: display 10Algorithm 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 ImplementationsConsider example of an airplane flight with 10 seats to be assignedTasksList available seatsReserve a seatHow to store, access data?10 individual variablesAn array of variablesUse ArrayAlgorithm to List available seatsFor number ranging from 0 to max_seats-1, do:If seat[number] == ‘ ’:Display numberAlgorithm 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 occupiedADTsIn 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 themIn the example, a collection of data is a list of seatsThe basic operations are (1) Scan the list to determine which seats are occupied (2) change seat’s statusData Structure and Abstract Data TypeThe term of Data Structure and Abstract Data Type are often used interchangeablyHowever, we use ADT when data is studied at a logical levelThe term data structure refers to a construct in programming language that can be used to store dataOutlineIntroduction to Abstract Data Types (ADTs)ArraysArray ADTCollection of data elementsA fixed-size sequence of elements, all of the same typeBasic OperationsDirect 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 ArrayOne-dimensional array: only one index is usedMulti-dimensional array: array involving more than one index Static array: the compiler determines how memory will be allocated for the arrayDynamic array: memory allocation takes place during executionOne-Dimensional Static ArraySyntax: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 ADTCollection of data elementsA fixed-size sequence of elements, all of the same typeBasic OperationsDirect 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 arrayConsider 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 ArraysConsider a table of test scores for several different studentsArray of Array DeclarationsAn array of arraysAn array whose elements are other arraysArray of Array DeclarationsEach 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 ArraysSyntax: 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 ArraysConsider multiple pages of the student grade booktypedef double ThreeDimArray[NUM_ROWS][NUM_COLS][NUM_RANKS]; . .
View Full Document