60x Filetype PDF File size 0.13 MB Source: www.cs.ubc.ca
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
no reviews yet
Please Login to review.