jagomart
digital resources
picture1_Unit3 C0ncretedatatypes


 60x       Filetype PDF       File size 0.13 MB       Source: www.cs.ubc.ca


File: Unit3 C0ncretedatatypes
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 ...

icon picture PDF Filetype PDF | Posted on 07 Feb 2023 | 2 years ago
Partial capture of text on file.
                                                  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
The words contained in this file might help you see if this file matches what you are looking for:

...Unit concrete data types classification of structures vs abstract most important arrays records linked lists binary trees overview there are two kinds simpleor atomic structured or an type represents a single item structure on the other hand has number components set operations next slide shows according to some specific properties versus cdt s direct implementations relatively simple concept adt offer high level view and use independent its implementation example implementing student record struct with public no functions represent does not hide anything class private hides etc divided into contiguous hybrid fundamental graphs c array collection objects same index values in range stored consecutive locations each object unique accesses i th e g char word is declared be characters dimension must known at compile time cont d indices subscripts start elements can also initialized but constants only int ia cannot assigned one another element turn pointers closely related suppose we declar...

no reviews yet
Please Login to review.