Course Objectives

The objective of this course is to introduce the subject of data structures with
the explanation of how data can be stored or manipulated in computer in an
optimized way.

An overview of data organization and certain data structures will be covered

along with a discussion of the different operations, which are applied to these
data structures.

Here, the space and time complexity will be taken care for different searching or
sorting techniques to deal with data. We also include how these efficient
techniques could be implemented in real life applications.
 Course Prerequisites
❑ Representing information in computers, Binary Number Systems,
Conversions.

❑ Using IDE.

❑ Basic conception of Data Storage, Data types, Variable, Array (single &
multidimensional), Pointers, String, Functions, Recursion, Scope of variable &
function, etc.

❑ Knowing different Libraries & their Functions.

❑ Concept of Structure & Class.

❑ Knowing Object Oriented Programming concepts.

 Importance of the course
❑ Data structure is required for all areas of computer science – especially for
the basic concept of programming.

❑ This course will give the basic for the understanding of the courses –
Algorithms, Database, Artificial Intelligence, object oriented programming,
etc.

❑ This course will give the basic for the understanding of the concepts – Data
storage, converting data into information, manipulation of data, etc.
 Course Contents

o Arrays [1D & 2D]

o Pointer, String, Structure
o Stack & Queue
o Application of Stack & Queue
o Searching & Sorting
o Linked Lists [Singly & Doubly]
o Introduction to Trees
o Binary Search Tree, Heap Tree
o Introduction to Graphs
o Generating Minimum Spanning Tree from Graph [Prim’s & Kruskal’s
Algorithms]
o Graph Traversals [BFS & DFS]
 Data & Structures
❑ What is Data?
o Data means raw facts or information that can be processed to get
results.

❑ What is Structure?
o Some elementary items constitute a unit and that unit may be
considered as a structure.

o A structure may be treated as a frame where we organize some

elementary items in different ways.
 Data Structures
❑ So, what is Data Structure?
o Data structure is a structure where we organize elementary data items in
different ways and there exits structural relationship among the items so
that it can be used efficiently.

o In other words, a data structure is means of structural relationships of

elementary data items for storing and retrieving data in computer’s
memory.
 Operations on Data Structures
❑ Basic
o Insertion (addition of a new element in the data structure)
o Deletion (removal of the element from the data structure)
o Traversal (accessing data elements in the data structure)

❑ Additional:
o Searching (locating a certain element in the data structure)
o Sorting (Arranging elements in a data structure in a specified order)
o Merging (combining elements of two similar data structures)
o Etc.
 Data Storage Concept: Variable
We have already gone through how computers represent information using
binary number system.

❑ But we need to understand how we are going to represent information in our

programming, which we will use as the basis for our computational
processes.

❑ To do this, we need to decide on representations for numeric values and for

symbolic ones.

❑ We will use the concept of variables.

 Data Storage Concept: Variable
❑ Let us think that, I ask you to retain the number 5 in your mental memory,
and then I ask you to memorize also the number 2 at the same time. You have
just stored two different values (5, 2) in your memory. Now, if I ask you to add
1 to the first number I said, you should be retaining the numbers 6 (that is
5+1) and 2 in your memory. Now subtract the second value from the first and
you obtain 4 as result.

❑ The whole process that you have just done with your mental memory is a
simile of what a computer can do with two variables. The same process can
be expressed in C/C++ with the following instruction set:

1. a = 5
2. b = 2
3. a = a + 1
4. result = a - b
 Data Storage Concept: Variable
1. a = 5
2. b = 2
3. a = a + 1
4. result = a – b

❑ Obviously, this is a very simple example since we have only used two small
integer values, but consider that your computer can store millions of numbers
like these at the same time and conduct sophisticated mathematical
operations with them.

❑ Therefore, we can define a variable as a portion of memory to store a

determined value. Each variable needs an identifier that distinguishes it from
the others. For example, in the previous code the variable
identifiers were a, b and result, but we could have called the variables any
names we wanted to invent, as long as they were valid identifiers.
 Data Storage Concept: Variable
❑ So, a variable is a storage location and an associated symbolic name (an identifier)
which contains some known or unknown quantity or information, a value.

❑ The variable name is the usual way to reference the stored value; this separation of
name and content allows the name to be used independently of the exact information
it represents.

❑ The identifier in computer source code can be bound to a value during run time, and
the value of the variable may thus change during the course of program execution.

❑ In computing, a variable may be employed in a repetitive process: assigned a value in

one place, then used elsewhere, then reassigned a new value and used again in the
same way.

❑ Compilers have to replace variables' symbolic names with the actual locations of the
data in the memory.
 Data Storage Concept: Memory Management
❑ A variable is an area of memory that has been given a name. For example: the
declaration int x; acquires four byte memory area and this area of
memory that has been given the name x.

❑ One can use the name to specify where to store data. For example: x=10; is
an instruction to store the data value 10 in the area of memory named x.

❑ The computer access its own memory not by using variable names but by
using a memory map with each location of memory uniquely defined by a
number, called the address of that memory location.

❑ To access the memory of a variable the program uses the & operator. For
Example: &x returns the address of the variable x.

&x represents the memory area of variable named x.

int
x;
 Array [1-Dimensional]: Definition & Structure
❑ An array can hold a series of elements of the same type placed in contiguous
memory locations.
❑ Each of these elements can be individually referenced by using an index to a unique
identifier.
❑ In other words, arrays are a convenient way of grouping a lot of values of same
type under a single variable name.
❑ For example, an array to contain 5 integer values of type int called mimo could be
represented like this:

where each blank panel represents an element of the array, that in this case are
integer values of type int with size 4 bytes. These elements are numbered/indexed
from 0 to 4 since in arrays the first index is always 0, independently of its length.
 Array [1-Dimensional]: Declaration
❑ Like a regular variable, an array must be declared before it is used. A typical
declaration for an array in C++ is:

type name [total_number_of_elements];

where type is a valid data type (like int, float …), name is a valid identifier and
the elements field (which is always enclosed in square brackets []), specifies how
many of these elements the array can contain.

❑ Therefore, in order to declare an array called mimo as the one shown in the above
diagram it is as simple as:

int mimo [5];

❑ The elements field within brackets [] which represents the number of elements
the array is going to hold, must be a constant integer value, since arrays are blocks
of non-dynamic memory whose size must be determined before execution.
 Array [1-Dimensional]:Initialization
❑ When declaring a regular array (int mimo[5];) of local scope (within a function,
for example) its elements will not be initialized to any value by default, so their
content will be undetermined until we store some value in them. The elements of
global and static arrays are automatically initialized with their default values, zeros.

❑ When we declare an array, we have the possibility to assign initial values to each
one of its elements by enclosing the values in braces { } separated by comas. For
example: int mimo[5] = { 16, 2, 77, 40, 12071 };

❑ This declaration would have created an array like this:

❑ The number of values between braces { } must not be larger than the number of
elements that we declare for the array between square brackets [ ].
 Array [1-Dimensional]:Initialization
❑ An array can also be partially initialized. i.e. we assign values to some of the initial
elements. For example: int mimo[5] = { 16, 2};

❑ This declaration would have created an array like this:

❑ Here the first 2 values are assigned sequentially. The rest 3 elements are
unassigned.

❑ Some more initialization –

float x[5] = {5.6, 5.7, 5.8, 5.9, 6.1};
char vowel[6] = {'a', 'e', 'i', 'o', 'u', ‘\0'};
is equivalent to string declaration: char vowel[6] = "aeiou";
 Array [1-Dimensional]:Access
❑ The number in the square brackets [ ]of the array is referred to as the 'index'
(plural: indices) or 'subscript' of the array and it must be an integer number 0 to
one less than the declared number of elements.

❑ We can access the value of any of its elements individually as if it was a normal
variable, thus being able to both read and modify its value. The format is as simple
as: name[index]

❑ For the declaration int mimo[5]; the five (5) elements in mimo is referred in the
program by writing: mimo[0] mimo[1] mimo[2] mimo[3] mimo[4]

❑ Each of the above array elements is an integer and each of them also acts as an
integer variable. That is, whatever operation we can perform with an integer
variable we can do the same with these array elements using same set of rules.
 Array [1-Dimensional]:Some Facts
❑ Arrays have a natural partner in programs: the for loop. The for loop provides a
simple way of counting through the numbers of an index in a controlled way. The
for loop can be used to work on an array sequentially at any time during a
program.

❑ It is important to be able to clearly distinguish between the two uses that

brackets [] have related to arrays.
▪ one is to specify the size of arrays when they are declared - char
array[5]; Here the index (5) is always an integer constant.
▪ the second one is to specify indices for concrete array elements, like-
array[3] = '*'; Here the index (3) is always an integer or an integer
expression.
 Array [1-Dimensional]:Some Facts
❑ Consider the following example:
char array[5];
array[7] = '*';

❑ The assignment of array[7] is clearly wrong as index 7 or element 8 in

array[5] does not exists. But, C/C++ would happily try to write the character *
at the index 7. Unfortunately this would probably be written in the memory taken
up by some other variable or perhaps even by the operating system. The result
would be either:
▪ The value in the incorrect memory location would be corrupted with
unpredictable consequences.
▪ The value would corrupt the memory and crash the program completely! On
Unix systems this leads to a memory segmentation fault.

❑ The second of these tends to be the result on operating systems with no proper
memory protection. Writing over the bounds of an array is a common source of
error. Remember that the array limits run from zero to the size of the array minus
one.
Array [1-Dimensional]: Array Access Demonstration
1. int mimo[5], a, b, i; // declaration of a new array
2. mimo[2] = 75; // store 75 in the third element of mimo
3. a = mimo[2]; // copy/assign a with the third value of
mimo
4. cin >> mimo[2]); // read a value for the third element of mimo
5. /* read 5 values for the five elements of mimo sequentially */
6. for(i=0; i<5; i++)
7. cin >> mimo[i];
8. /* print 5 values for the five elements of mimo sequentially */
9. for(i=0; i<5; i++) ;
10. cin >> mimo[i];
11. /* some more interesting accesses */
12. a = 4;
13. mimo[2] = a;
14. mimo[a] = 3;
15. b = mimo[a-2] + 2; //use of expression in index
16. mimo[mimo[a]] = mimo[2] + b;
 Array [1-Dimensional]: Searching an element in Array
1. int mimo[10] = {32,4,5,12,5,54,6,23,3,5}; //
declaration of a new array
2. int n;
3. cout<<“Enter the number to be searched: “<<endl;
4. cin>>n; // inputting the number to be searched in the
array
5. for(int i=0; i<10; i++){ // searching begins
6. if (n == mimo[i]){
7. break; // searching ends
8. }
9. }
10. cout<<n<<“ was found in index “<<i<<“ of the
array.”<<endl;

OUTPUT: 5 was found in index 2 of the array.

Can you guess the output if we take 5 as input in the 4th line of the code?

This searching technique is also called Linear Search, because it searches the
array for a given element chronologically or linearly.
 Array [1-Dimensional]: Operation on Array - Insertion
1. int k, i, n=5, mimo[10]={2, 3, 5, 6, 7}; //partial initialization; n=total elements
2. mimo[n++] = 8; // insert value 8 at the end of the array; increase n;
3. /* insert value 1 at the beginning of array */
4. for(i=n; i>0; i--) //shift all the values one index forward. i.e. the value
5. mimo[i] = mimo[i-1]; //in index 1 goes to 2, 2 goes to 3,…, (n-1)th goes to nth.
6. mimo[0] = 1; n++; //1 is inserted at index 1; n increases;
7. // insert value 4 in the middle (index k=3) of the array
8. k = 3;
9. for(i=n; i>k; i--) //shift all the values one index forward. i.e. the value
10. mimo[i] = mimo[i-1]; //in index k goes to k+1,…, (n-1)th goes to nth.
11. mimo[k] = 4; n++; //4 is inserted at index k; n increases;
12. for(i=0; i<n; i++) //printing all the values in the array after insert
13. cout << mimo[i];
OUTPUT:
1 2 3 4 5 6 7 8
 Array [1-Dimensional]: Operation on Array - Deletion

1. int k, i, n=8, mimo[10]={1, 2, 3, 4, 5, 6, 7, 8}; //n=total elements.

2. n--; // Deleting the last element of the array. Decrease n; last element 8 is
no longer part of list.
3. /* delete value 1 from the beginning of array. */
4. n--; // deleting the value 1 will decrease the total elements n by
one.
5. for(i=0; i<n; i++) //shift all the values one index backward. The value in
index
6. mimo[i] = mimo[i+1]; //2 goes to 1, 3 goes to 2,…, nth goes to (n-1)th.
7. k = 2; // delete value 4 from the middle (index k=2) of the array
8. n--; // deleting the value 4 will decrease the total elements n by
one.
9. for(i=k; i<n; i++) //shift all the values one index forward. i.e. the
value
10. mimo[i] = mimo[i+1]; //in index k+1 goes to k,…, nth goes to (n-1)th.
11. for(i=0; i<n; i++) //printing all the values in the array after insert
12. cout<<mimo[i];
OUTPUT:
2 3 5 6 7
 Q/A
• Thank you
 Array [2-Dimensional]
• Definition, Structure & Declaration
• Initialization
• Access
• Memory Access
 Array [2-Dimensional]: Definition, Structure & Declaration
❑ Two-dimensional arrays can be described as "arrays of arrays". For example, a 2D
array can be imagined as a Two-dimensional table made of elements of same
uniform data type.

❑ minu represents a Two-dimensional array of 3 per 5 elements of type int. The

way to declare this array in C++ would be: int minu [3][5];
❑ The way to reference the 2nd element vertically and 4th horizontally or the (2 × 4) 8th
element in an expression would be: minu [1][3];
❑ Generally, for two-dimensional array, 1st dimension is considered as row and the 2nd
dimension is considered as column. Here, we have 3 rows and 5 columns.
 Array [2-Dimensional]: Initialization
❑ Assigning values at the time of declaring a two-dimensional array can be any one of the
following ways:

int minu[3][5] = {1,2,3,4,5,2,4,6,8,10,3,6,9,12,15};

int minu[3][5] = {{1,2,3,4,5},{2,4,6,8,10},{3,6,9,12,15}};
int minu[3][5] = {
{1,2,3,4,5},
{2,4,6,8,10},
{3,6,9,12,15}
};

❑ The internal braces are unnecessary, but helps to distinguish the rows from the columns.
❑ Take care to include the semicolon at the end of the curly brace which closes the
assignment.
❑ If there are not enough elements in the curly braces to account for every single element
in an array, the remaining elements will be filled out with garbage/zeros.
❑ Static and global variables are always guaranteed to be initialized to zero anyway,
whereas auto or local variables are guaranteed to be garbage.
 Array [2-Dimensional]: Access
❑ Nested loop is used to take input Consider the following example (the dark area
and give output. at the end consists the input and the output of
this program; the yellow colored text
❑ The input is taken in row (1st represents input given by the user and black
dimension) major. i.e. all the
colored text represents output):
values of row 0 is scanned first,
then the values of row 1, and
values of row 2. For each row,
value at column 0 is scanned
1 // input & output of a 2D array
first, then the value at column 1,
2 void main (void)
and value at column 2. 3 {
4 int i, j, a[3][3], b[3][3]={1,3,5,7,9,2,4,6,8};
❑ In output, array a is used in row 5 for(i=0;i<3;i++)
6 for(j=0;j<3;j++)
major. But array b is used in
7 cin>>a[i][j];
column (2nd dimension) major. 8 for(i=0;i<3;i++)
i.e. all the values of column 0 is 9 for(j=0;j<3;j++)
added first, then the values of 10 cout<<a[i][j] + b[j][i];
column 1, and values of column 11 }

2. For each column, value at row 2 4 6 8 1 3 5 7 9

0 is added first, then the value at 3 11 10 11 10 9 10 9 17
row 1, and value at row 2.
 Array [2-Dimensional]:Memory Access

Two-dimensional arrays are just an abstraction for programmers, since we can obtain the
same results with a simple array just by putting a factor between its indices: int minu
[3][5]; is equivalent to (3 * 5 = 15); int minu [15];

❑ 2D Array ❑ 1D array
int minu [3][5], H=3, W=5, n, m, i=0; int minu [3 * 5], H=3, W=5, n, m, i=0;
void main (void){ 0 1 2 3 4 void main (void){
0 1 2 3 4 5
for (n=0; n<H; n++) for (n=0; n<H; n++)
1 6 7 8 9 10
for (m=0; m<W; m++) 2 11 12 13 14 15 for (m=0; m<W; m++)
minu [n][m]= ++i;
minu [ W * n + m ] = ++i;
}
}

As memory is flat, in both codes the values are actually 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

stored sequentially in the memory (just like the 1D array). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
The access for the two-dimensional array in that case is just
as the indexing of the array,
[(Total_column) * (row_index) + (column_index)] Height Width n m Width * n + m
3 5 01 2
2 0
341 2
5
3896
14
13
11
10
12 0
7
1
4
 Array [2-Dimensional]:Memory Access
Memory Access
❑ Memory of each element of an array can be accessed using the & operator.
❑ &mimo[2] gives the memory location of the 3rd element of the array mimo.
❑ If the element is more than a byte, it gives the starting byte of the element.
❑ Let us consider the starting address of int mimo[5] is 567.

0 1 2 3 4
mimo
567 569 571 573 575 577 579 581 583 585 587
568 570 572 574 576 578 580 582 584 586

❑ &mimo[2] will give us the memory location 575.

❑ mimo[2] will give us 4 bytes (int) of information starting from 575 to 579.
❑ The name of an array always refer to the starting location of the array. i.e. the first
element of the array. So, mimo = &mimo[0].
 Array [2-Dimensional]:Memory Access
Memory Access

❑ &mimo[2] will give us the memory location 575.

❑ mimo[2] will give us 4 bytes (int) of information starting from 575 to 579.

❑ The name of an array always refer to the starting location of the array. i.e. the first
element of the array. So, mimo = &mimo[0].

&array[index]=start_location_array + index * size_of_data

⇒&mimo[ 2 ] = mimo (or &mimo[0]) + 2 * sizeof(int)
⇒&mimo[ 2 ] = 567 + 2 * 4 = 575
 Array [2-Dimensional]:Memory Access
Memory Access
567 571 575 579
0 1 2
❑ Consider a 2D array mimo[R][C] each element addressed by
&mimo[i][j], where R=total element in 1st dimension,
0
C=total element in 2nd dimension, 0≤ i < R, 0 ≤ j < C.
❑ Let int mimo[4][3]; Here, mimo or &mimo[0]
[0] gives us the starting memory location 567. 1
🡨583 🡨587
❑ mimo[1][1] will give us 4 bytes (int) of information
starting from 583 to 587.
579🡪

0 1 2 3 4
mimo
2
567 569 571 573 575 577 579 581 583 585 587
568 570 572 574 576 578 580 582 584 586

3
&array[i][j]=start_location + (i * (C * size_of_data)) + (j * size_of_data)
⇒ &mimo[1][1] = mimo + (1 * (3 * sizeof(int))) + (1 * sizeof(int))
⇒ &mimo[1][1] = 567 + (1 * 3 * 4) + (1 * 4) = 583
 Array [2-Dimensional]:Memory Access
❑ There is a general way to access the memory location of a 2 dimensional array.

❑ For an array int mimo[R][C]; and 0≤i<R; 0≤j<C.

▪ mimo[i] = &mimo[i][0] represents the starting address of ith row.
▪ mimo[i] skips i number of rows each with C number of elements from the
start_location of the array.
▪ So, mimo[i] = start_location + (i * C elements), where C
elements are counted in bytes based on the size_of_data, here int.
▪ So, mimo[i] = start_location + (i * (C *
size_of_data)).
▪ So, mimo[i] = mimo(or &mimo[0][0]) + (i * (C
*sizeof(int))).

❑ A 2D array is also referred as an array of arrays. i.e. an array of which each element
is another array.
 Q/A

Thank you