UNIT 3
                                       Concrete Data Types
                       „ Classification of Data Structures
                       „ Concrete vs. Abstract Data Structures
                       „ Most Important Concrete Data Structures
                           ¾Arrays
                           ¾Records
                           ¾Linked Lists
                           ¾Binary Trees
                   Overview of Data Structures
                   „ There are two kinds of data types: 
                        ¾simpleor atomic
                        ¾structured data types or data structures 
                   „ An atomic data type represents a single data item.
                   „ A data structure , on the other hand, has 
                        ¾a number of components 
                        ¾a structure 
                        ¾a set of operations 
                   „ Next slide shows a classification of the most important 
                      data structures (according to some specific properties) 
                    Unit 3- Concrete Data Types                                           2
                      Data Structure Classification
                       Unit 3- Concrete Data Types                                                      3
                      Concrete Versus Abstract Types
                      „ Concrete data types or structures (CDT's) are direct implementations of a 
                          relatively simple concept.
                      „ Abstract Data Types (ADT's) offer a high level view (and use) of a concept 
                          independent of its implementation.
                      „ Example: Implementing a student record:
                           ¾ CDT: Use a struct with  public data and no functions to represent the record 
                                – does not hide anything 
                           ¾ ADT: Use a class with private data and public functions to represent the record 
                                – hides structure of the data, etc. 
                      „ Concrete data structures are divided into: 
                           ¾ contiguous
                           ¾ linked
                           ¾ hybrid 
                      „ Some fundamental concrete data structures: 
                           ¾ arrays 
                           ¾ records, 
                           ¾ linked lists 
                           ¾ trees 
                           ¾ graphs. 
                       Unit 3- Concrete Data Types                                                      4
                   C++ Arrays
                    „ A C++ array has:
                        ¾a collection of objects of the same type 
                        ¾a set of index values in the range [0,n]
                    „ Structure: 
                        ¾objects are stored in consecutive locations 
                        ¾each object has a unique index 
                    „ Operations: 
                        ¾[i] accesses the (i+1)th object
                    „ E.g. In 
                                     char word[8]; 
                        ¾word is declared to be an array of 8 characters 
                        ¾8 is the dimension of the array 
                        ¾dimension must be known at compile time.
                    Unit 3- Concrete Data Types                                            5
                   C++ Arrays (cont’d)
                    „ Array indices (or subscripts ) start at 0. 
                       word 's elements are: 
                    „ word[0], word[1], ... , word[7] 
                    „ An array can also be initialized, but with constants only 
                    „ int ia[] = {1,2,0}; 
                    „ Arrays cannot be assigned to one another; each 
                       element must be assigned in turn 
                    Unit 3- Concrete Data Types                                            6
                      Arrays & Pointers 
                       „ Are closely related.                                     „ Suppose we declare
                           The declaration:                                                int a[10];
                                            type a[10]                               then 
                            ¾ allocates space for 10 items of type type
                            ¾ items are stored in consecutive memory locations
                       „ C++ treats consecutive elements in the array as 
                           having consecutive addresses: 
                           &a[0] < &a[1] < ... < &a[9] 
                           and 
                           &a[1] = &a[0] + 1 
                           &a[i] = &a[i-1] + 1
                       „ a is a variable of type pointer to type,
                       „ &a[i] is the same as a+i
                           a[i] is the same as *(a+i) 
                       „ There are two ways to access the elements of an 
                           array. We can use either: 
                            ¾ array subscripts, or 
                            ¾ pointers 
                       Unit 3- Concrete Data Types                                                        7
                      Example
                       „ Suppose we declare: 
                                 int i, a[10] 
                           The following two statements output the elements of a  
                                 1.  for (i = 0; i < 10; i++) 
                                      cout << a[i];           // using subscripts 
                                 2.  for (i = 0; i < 10; i++) 
                                       cout << *(a + i);                // using pointers 
                       „ If 
                                 int * p; 
                           then p = &a[i] or 
                                 p = a + i 
                           makes p point to the i-th element of a . 
                       „ Straying beyond the range of an array results in a segmentation fault. 
                       „ Pointers are not integers 
                            ¾ Exception: NULL (which is 0) can be assigned to a pointer. 
                            ¾ NULL is the undefined pointer value
                       Unit 3- Concrete Data Types                                                        8