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:
¾ simple or 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

Dynamic arrays
„ Are declared as pointers
„ Space for these arrays is allocated later, when the size is known
„ Example: Consider the declarations:
int b[10];
int * a;
a = new int[10];
Then:
¾ a and b are both arrays
¾ b is a fixed array ; a is a dynamic array
¾ [] can also be used on a
¾ a[2] is the third element of a
Example Using Dynamic
BUT Arrays:
¾ b has space for ten integers
¾ a has space for one pointer
– space for its elements must be allocated by new Implementation of
¾ b is a constant pointer; a can be changed EmployeeDB using dynamic
arrays:
„ A dynamic array can be expanded EmployeeDB (Dynamic
¾ I.e. to expand a we can write: Array)
int* temp = new int[10 + n];
for (int i = 0; i<10; i++)
temp[i] = a[i];
delete a;
a = temp;
Unit 3- Concrete Data Types 9

Passing Array Parameters

„ Arrays are always passed by reference
„ Suppose we declare,
int a[10];

To pass array a to a function f, f may be declared as:

type f( int d[], int size ) or

type f( int* d , int size)

„ In any case, f is called by f(a, sizeof a) .

Unit 3- Concrete Data Types 10

Multi-dimensional Arrays
„ To store the temperature measured at each hour of each day for a
week, we can declare :
int temp[7][24];
¾ temp is a 2-dimensional array.
¾ to get the temperature at noon on Monday, we can do:
temp[1][11];

„ To pass a multi-dimensional array to a function, the first subscript

can be free.
„ i.e. To pass temp to f, f may been declared as

... f(int t[][24], int size1); or

... f(int (*t)[24], int size1); or
... f(int** t, int size1, int size2)
„ In the last declaration, t is a pointer to a pointer, while in the other
two t is a pointer to an array of 24 integers

Unit 3- Concrete Data Types 11

Multi-dimensional Arrays vs. Pointers

„ Given the declarations:
int t[7][24];
int* s[7];
int** r;
we can allocate adequate space to s and r so that t, s and r behave
as 2d arrays
¾ i.e t[3][4] s[3][4] r[3][4] all work fine

„ But
¾ t is a true 2-dimensional array (has space allocated)
¾ s is an array of 7 pointers (each pointing to an array of 24 integers)
¾ r is a pointer to a pointer

„ A use of semi-dynamic arrays:

arrays with different row length
„ i.e.
char* day[8] = {"Illegal day name", "Sunday", ..., "Friday"}
Unit 3- Concrete Data Types 12
Features of Arrays
„ Simple structures.
„ Their size is fixed;
¾ dynamic arrays can be expanded, but expansion is expensive.
„ Insertion and deletion in the middle is difficult.
„ Algorithms are simple.
„ Accessing the i-th element is very efficient

Unit 3- Concrete Data Types 13

C++ Records (struct's)

„ Records allow us to group data and use them together as a unit
„ The record type has:
¾ a collection of objects of same or different type
¾ each object has a unique name
¾ .obname accesses the object with name obname.
„ C++ uses "struct" for records. They are also called "structures" in C++.
„ For instance, after declaring
struct date { A C++ struct may also
int day; have function members.
char* month;
int year; The difference
}; between classes
date is now a new type; it can be used as: and records:
date today = {20, "jun" , 1993}; by default, a class
„ We can access the components of a structure components are private,
using the select member operator ".“ while a struct's
E.g. today.month[2] // 'n' components are public
Unit 3- Concrete Data Types 14
C++ Records (cont’)
„ Structures are commonly used to implement lists, trees, etc. An item
of these types of structures usually looks like:
struct item {
int data;
item* next;
};
„ We can then declare:
item item1, item2, *head, *current;

¾ The physical structure of this would look like the following:

Unit 3- Concrete Data Types 15

The operator ->

„ Structure components can be accessed by pointers using the point
at member operator "->".
„ E.g. If we set
head = &item1
then
head -> data
is the data field of item1 .
„ Structures can be copied member-wise :
item2 = *head

„ We can also pass a structure as a parameter to a function.

However, it is usually more efficient to pass a structure by
reference, or to pass a pointer to the structure instead.
„ i.e.
void f(const date& d ) or
void f(const date* d )
Unit 3- Concrete Data Types 16
Linked Lists
„ A (singly ) linked list is a sequence of nodes linked together:

„ They represent sequences of data items.

„ Each node in the list contains the item and a pointer to the next
element.
„ The last pointer is set to 0 (or NULL) to denote the end of the list.
„ The whole list is defined by a pointer to the first item (called list here).
„ In C++ the node and the list are defined as:
// TYPE is the type of our items or typedef int TYPE;
typedef int TYPE; class node {
struct node { public:
TYPE item; TYPE item;
node* next; node* next;
}; };
Unit 3- Concrete Data Types 17

Common Operations on Linked List

„ Insert an item in the list. Many types of insertion:
¾ insert_first: insert item at the front of list
¾ insert_last: insert item at the end of the list
¾ insert_after: insert item in list after a certain node
„ find: finds the node in the list with a given item
„ delete_item: removes an item from the list
„ printNode: prints the contents of a node

„ A Singly Linked List Toolkit

The following files contain an implementation of a module (or toolkit)
for the singly linked list structure:
Singly Linked List

„ Example Using Linked Lists

Implementation of EmployeeDB using singly linked lists:
EmployeeDB (Linked List )
Unit 3- Concrete Data Types 18
Head Nodes
„ Processing of this first node is different from processing
of the other nodes.
„ A head node is a dummy node at the beginning of the
list.
¾ It is similar to the other nodes, except that it has a special value
¾ It is never deleted.
¾ Processing every actual node is the same.
„ Usually, it is more confusing and it is not used.

Unit 3- Concrete Data Types 19

Circular Linked Lists (or rings)

„ A circular linked list looks like:

„ A circular linked list is appropriate when there is no

distinct first and last item.
„ The algorithms for circular linked lists are similar to
those for singly linked lists, except that
¾ none of the links is null
¾ the end of the list is reached when
curr->next == head

Unit 3- Concrete Data Types 20

Doubly-linked Lists
„ Similar to singly linked lists except that each node also has a
pointer to the previous node.
„ Doubly linked list node definition:
struct dnode { A Doubly Linked
TYPE item;
List Toolkit :
dnode* next;
Can be found in
dnode* prev;
};
Doubly Linked List
„ Operations are defined similarly

Unit 3- Concrete Data Types 21

Features of Linked Lists

Compared to arrays, linked lists have the following
advantages/disadvantages:

„ Advantages
¾ Are dynamic structures; space is allocated as required.
¾ Their size is not fixed; it grows as needed.
¾ Insertion and deletion in the middle is easy.
„ Disadvantages
¾ More space is needed for the links.
¾ Algorithms are more complex.
¾ Impossible to directly access a node of the list.

Unit 3- Concrete Data Types 22

Binary Trees
„ A binary tree is a structure that
¾ is either empty, or
¾ it consists of a node called a root and two binary trees called the
left subtree and the right subtree .
„ Pictorially a binary tree looks like the following:

Unit 3- Concrete Data Types 23

Parents, Children & Paths

„ Parents & Children:
¾ If there is a link from node N to M then N is the parent of M and
M is a child of N.
¾ The root has no parent.
¾ A leaf is a node on the bottom level of the tree without any
children.
¾ A node can have a maximum of 2 children.
¾ A tree cannot have cycles.
„ Grandparents, grand children, ancestors, descendants
are defined similarly.
„ Path from N1 to Nk
¾ a sequence of nodes N1, N2,..., Nk, where Ni is a parent of
Ni+1.
¾ path length : # of nodes in the path from N1 to Nk (some authors
use # of edges).
Unit 3- Concrete Data Types 24
„ Depth or level of a node N
¾ length of the unique path from the root to N
¾ the level of the root is 1.
„ Height of a node N:
¾ length of the longest path from N to a leaf
¾ a leaf's height is 1.
„ Height of the tree:
¾ height of its root
„ The number of nodes in a binary tree of height h is >= h
and <= 2h -1 nodes.

Unit 3- Concrete Data Types 25

Implementation of Trees
„ Implementation of a binary tree in C++:
¾ a node in the tree contains the item and two pointers to the
subtrees:
typedef int TYPE ;
struct bnode {
TYPE item;
bnode* left;
bnode* right;
};
„ A C++ binary search tree is just a pointer to the root.

Unit 3- Concrete Data Types 26

Common Operations for Binary Trees
„ Insert an item in the tree: To the left or right of a node:
¾ insert_left: insert item on the left of a given node
¾ insert_right: insert item on the right of a given node
„ find: finds the node in the tree with a given item
„ find_parent: finds the parent of a given node in the tree
„ delete_node: removes the node with the given item from the tree
„ print: prints the whole tree (sideways)

A Binary Tree Toolkit

„ An implementation of a module (or toolkit) for the binary tree
structure can be found in the Examples:
¾ Binary Tree

Unit 3- Concrete Data Types 27

Traversing a binary tree

„ There are three types of traversal.
¾ preorder : node then left subtree then right subtree
¾ inorder : left subtree then node then right subtree
¾ postorder : left subtree then right subtree then node

„ Inorder traversal: The following code applies a function visit to every

node in the tree inorder:

void inorder( bnode* root ) {

// apply the function visit to every node in the tree, inorder
if( root != NULL ) {
inorder( root->left);
visit ( root ); // apply visit to the root of the tree
inorder( root->right);
}
}
„ Tree traversal is not usually implemented by a function. What is
shown here is just an example.
Unit 3- Concrete Data Types 28
Higher trees and Graphs
N-ary Trees
„ Like binary trees except that a node may have up to n
subtrees.

Graphs
„ More general than trees. They can have cycles and are
usually hybrid structures.

Unit 3- Concrete Data Types 29