DATA STRUCTURES & COMPUTER ALGORITHMS

1
 Introduction to Data Structures
● Introduction to Abstract DataTypes
● Need for Data Structures, Data Types, Data Abstraction
● Array and Structure Overview
● Linear Data Structures
● Stacks
● Queues
● Linked lists
● Non – Linear Data Structure
● Trees
● Graphs
● Sorting and Searching
2
 Module 1: Review of Data Structure

3
 Introduction to Data Structures
● Data is a set of elementary items.
● “The data structures deal with the study of how the data is
organized in the memory, how efficiently it can be retrieved
and manipulated and the possible ways in which different data
items are logically related”.
● They can be classified in to
● Primitive data structures
● Non primitive data structure.

4
 Introduction to Data Structures
● Primitive data structure:
● These are data structures that can be manipulated directly by
machine instructions.
● In C language, the different primitive data structures are int,
float, char, double.

● Non primitive data structures:

● These are data structures that can not be manipulated directly
by machine instructions. Arrays, linked lists, files etc., are some
of non-primitive data structures and are classified into linear
data structures and non-linear data structures.

5
 Introduction to Abstract Data Types
● An abstract data type is a data structure and a collection of
functions or procedures which operate on the data structure
● An Example: Collections
● Programs often deal with collections of [Link] collections
may be organized in many ways and use many different program
structures to represent them, yet, from an abstract point of view,
there will be a few common operations on any [Link]
might include:

create Create a new collection

add Add an item to a collection
delete Delete an item from a collection
find Find an item matching some criterion in the collection
6 destroy Destroy the collection
 Lifetime Of A Variable
● Is a run-time concept
● Period of time during which a variable has memory space
associated with it
● begins when space is allocated
● ends when space is de-allocated

● Three categories of "lifetime"

● static - start to end of program execution
● automatic (stack) - start to end of declaring function's
execution
● heap (variable declared dynamic at runtime, and also de-
7 allocated dynamically at runtime.
 Data Memory Model
static data
space for global variables

automatic data
run-time stack - activation records added
and removed as program runs (expands and
shrinks in an orderly LIFO manner)

space for variables allocated at run-time

heap data (allocation and de-allocation requests occur
in unpredictable order)

8
 What is data structure?
● The way information is organized in the memory of a computer is
called adata structure
(OR)
● Adata structure is a way of organizing data that considers not only the
items stored but also their relationship to each other. Advanced
knowledge about the relationship between data items allows
designing of efficient algorithms for the manipulation of data.

9
 Definition of data structures
● Many algorithms require that we use a proper representation of data
to achieve efficiency.
● This representation and the operations that are allowed for it are
called data structures.
● Each data structure allows insertion access deletion etc.

10
 Why do we need data structures?
● Data structures allow us to achieve an important goal:
component reuse
● Once each data structure has been implemented once, it can be
used over and over again in various applications.
● Common data structures are
o Stacks
o Queues
o Lists
o Tree
o Tables
o Graphs

11
 Classification of data structure
● Based on how the data items are operated, it will classified
into:
1. Primitive data structure: is one data items are operated
closest to the machine level instruction. e.g. int, char,
double etc.
2. Non-primitive data structure: is one data items are
operated not closest to the machine level instruction.
(a) Linear data structure: it is a data structure in which
data items are stored in a sequence order. e.g. Arrays,
Lists, Stack and, Queuesets.

12
Operations performed on any linear structure

● Traversal – processing each element in the list

● Search – finding the location of the element with a given value.
● Insertion – adding a new element to the list.
● Deletion – removing an element from the list.
● Sorting –arranging the elements in some type of order.
● Merging – combining two lists into a single list.

(b) Non-linear data structure: in which order of data

items is not present. [Link], Graphs.

13
 Abstract Data Types
● Abstract data type (ADT) is a specification of a set of data and the set of
operations that can be performed on the data.
● Examples
o Associative array
o Set
o Stack
o Queue
o Tree

14
 Uses of ADT
● It helps to efficiently develop well designed program.
● Facilitates the decomposition of the complex task of
developing a software system into a number of simpler
subtasks
● Helps to reduce the number of things the programmer has
to keep in mind at any time
● Breaking down a complex task into a number of earlier
subtasks also simplifies testing and debugging.

15
 Algorithm
● Definition: an algorithm is a finite set of instructions
which, if followed, accomplish a particular task. In addition
every algorithm must satisfy the following criteria:
oInput: there are zero or more quantities which are
extenally supplied;
oOutput: at least one quantity is produced;
o Definiteness: each instruction must be clear and
unambiguous;
oFiniteness: if we trace out the instructions of an algorithm,
then for all cases the algorithm will terminate after a finite
number of steps;
16
 Linear Data Structures
● A data structure is said to be linear if its elements
form a sequence or a linear list.
● Examples:
o Arrays
o Linked Lists
o Stacks, Queues

17
 Arrays
● The very common linear structure is array. Since arrays are usually easy
to traverse, search and sort, they are frequently used to store
relatively permanent collections of data.
● An array is a list of a finite number n of homogeneous data elements
(i.e. data elements of the type) such that:
● The elements of the array are referenced respectively by an index
consisting of n consecutive numbers.
● The elements of the array are stored respectively in successive
memory locations.

18
 Operation of Array:
● Two basic operations in an array are storing
and retreiving (extraction)
o Storing: Avalue is stored in an element of the array with the
statement of the form;
o Data[i] = x where i is the valid index in the array and x is
the element.
o Extraction: Refers to getting the value of an element stored in
an array.
▪ x = Data[i]; where i is the valid index in the array and x is the
element.

19
 Array Representation:
● The number n of elements is called the length or size of the
array. If not explicitly stated we will assume that the index
starts from 0 and end with n-1.
● In general, the length (range) or the number of data
elements of the array can be obtained from the index by the
formula: Length = UB-LB+1
● Where UB is the largest index, called the Upper Bound, and

LBis the smallest index, called Lower Bound, of the array.

● If LB= 0 and UB= 4 then the length is, Length = 4-0+1
= 5.
20
 Array Representation Cont’d
● The elements of an array A may be denoted by the subscript
notation A[0],A[1],A[2], ..., A[N]
● The number k in A[k] is called a subscript or an index and
A[k] is called subscripted variable.
● Subscripts allow any element of A to be referenced by its
relative position in A.
● If each element in the array is referenced by a single subscript,
it is called single dimensional array.
● In other words, the number of subcripts gives the dimension
of that array.

21
 Two-dimensional Arrays
● A two-dimensional mxn array A is a collection of m*n data
elements such that each element is specified by a pair of
integers (such as i, j), called subcripts, with the property that,
0<i<m and 0<j<n.
● The element of A with first subscript i and second subscript j
will be denoted by A[i][j]
● There is a standard way of drawing two-dimensional mxn array Awhere
the element of A for a rectangular array with m rows and n columns and
where the element A[i][j] appears in row i and column j.
● A row is a horizontal list of elements and a column is a vertical list of
elements.

22
 Two-dimensional Arrays Cont’d
● The two-dimensional array will be represented in
memory by a block of m*n sequential memory
locations.
● Specifically, the programming languages will store the
array either:
● Column bycolumn, i.e. column-major order, or
● Row byrow, i.e. row-major order.

23
Two-dimensional Arrays Cont’d

24
 Abstract Data Types (ADT)
● The ADT consists of a set of definitions that allow
programmers to use the functions while hiding the
implementation. This generalization of operations
with unspecified implementations is known as
abstraction.
● An ADT is a data declaration packaged together with
the operations that are meningful on the data type.
●Declaration of Data
●DeClaration claration of operations

25
 Abstract Data Types (ADT) CONT’D

An array is a collection of
memory locations which allows
storing homogeneous elements.
It is an example for linear data
structure.

26
 Abstract Data Types (ADT)CONT’D
● An array lets you declare and work with a collection of values of the
same type (homogeneous). For example, you might want to create a
collection of five integers. One way to do it would be to declare five
integers directly:

● int a, b, c, d, e
● supose you need to find average of 100 numbers. What will you do? Youhave
to declare 100 variables.
● For example: int a,b,c,d,c,e,f,g,h,i,j,k,l,m,n,....,etc.
An easier way is to declare an array of 100 integers:
● Int a[100];
● The general sytax is:
Datatype arrat_name[size]

27
 Abstract Data Types (ADT) CONT’D
● For example:
int a[5]
the five seperate integers inside this array are accessed by an index. All arrays start
at index zero and go to [Link], int a[5] contains five element. For example:
a[0] = 12;
a[1] = 9;
a[2] = 14;
a[3] = 5;
a[4] = 1;
● Note: the array name will hold the address of the first element. It is
called BASE ADDRESS of that array. The base address cann’t be modified
during execution, because it is static. This means that the
increament/decreament operation would not work on the base address.
● Let us consider the first element that is stored in the address of 1020. It will
look like this:
28
29
 Memory Representation of linearArray
● The memory of a computer is a sequence of address locations as seen below:
● Tofind the location or address of any element of a linear array A,
● we use
LocA[i] = Base Address of A + w(i – Lower Bound)
● where LocA[i] is the address of an element of A with subscript i.
● Base address of A is the starting address of the first element of array A.
● w is the word length (i.e the number of bytes contained in the word)
● i is the index of the element whose address is sought.
● Lower Bound is the least index.
a[0] means a+0 → 1020+0 → 1020 (locates the 1020)
a[1] means a+1→ 1020+1*size of datatype → 1020+2→ 1022(for int size is 2 sbyte)
a[2] means a+2 → 1020+2*size of datatype→ 1 0 2 0 + 4 → 1024
a[3] means a+3→ 1020+3*size of datatype → 1020+6 →1026
a[4] means a+4 → 1020+4*size of datatype→1 0 2 0 + 8 → 1028

30
Memory Representation of linear ArrayCont’d
● For example, the following code initializes all of the values in the array
to 0:

int a[5]; / / array declaretion

int i;
for (i=0; i<5; i++)
a[i] = 0;
printf(“Element in the array”);

for (i=0; i<5; i++)

printf(“%d\n”, a[i]);

31
Memory Representation of linear ArrayCont’d
● Advantages
● Reducess memory access time, because all the elements are
stored sequentially. By incrementing the index, it is possible to
access all the elements in an array.
● Reduces number of variables in a program.
● Easy to use for the programmers.
● Disadvantages
● Wastage of memory space is possible. For example, storing
only 10 element in a 100 size array. Here, remaining 90
elements space is waste because these spaces can’t be used by
other programs till this program completes its execution.
● Storing heterogeneous elements are not possible.

32
 Memory representation of Multidimensional
Array
An n-dimensional m1 x m2 x … x mn array A is a collection of m1,
m2, …, mn elements where each element is specified by a list of n
integers which are called the subscripts(e.g i1, i2, i3, …in) such
that 1 ≤ i1 ≤ m1, 1 ≤ i2 ≤ m2, …1 ≤ in ≤ mn . Aparticular element
of A is written as A[i1, i2,… in]. That is, the element of A with
subscript i1, i2, … in.
● A multidimensional array can be represented in the memory
either by
● (i) Column major order or
● (ii) Row major order.
33
 Multidimensional Array Cont’d
● Column Major Order
The address of any element of A when A contains m columns, n rows and using
column major order is given by:
Loc(A[i,j]) = Base address of A + w[(i – 1) + n(j – 1)]
● Row Major Order
For row-major order, we have
Loc(A[i,j]) = Base address of A + w[m(i – 1) + (j – 1)]
● Where Base address of A and w are as defined under the linear array
representation.
● i is the row number of the element whose address is sought, j is the column
number of the element whose address is sought.
● Suppose we want to find the address of the element A[2,6] of the array with
dimension A[6,10] where w is given as 2 using the row major order, and given
that Base address of A= 5, we have

34
 Multidimensional Array Cont’d
● Loc(A[2,6]) = 5 + 2(10(2 -1) + (6 – 1)
= 5 + 2(10 + 5)
= 5 + 30
= 35

35
 Structure
● Struct: Declares a structure, an object consisting of
multiple data items that may be of different types.
● General syntax:
struct tag
{
data-type member 1;
data-type member 2;
...................
data-type member m;
};
36
 Structure
● Here, struct is the required keyword; tag (optional) is a name that
identifies structures of this type; and member1, member2, .... ,
member m are individual member declarations.
● The individual members can be ordinary variables, pointers, arrays,
or other structures.
● Astorage class cannot be assigned to an individual member, and
individual members can not initialized within a structure type
declaration.
● Declares structure variables:
Once the composition of the structure has been defined, induvidual
structure-type-variables can be declared as follows:

37
 Structure
● storage-class struct tag variable 1, variable 2, ..., variable n;
Where storage-class is an optional storage class specifier, struct is a
required keyword, tag is the name that appeared in the structure
declaration and variable1, variable2, ..., variable n are structure
variables of type tag.
● Example:
struct student
{
int regno;
char name[20];
char dept[10];
int year;
};

38
 Structure
● Here, regno, name, dept and year are the members of the student structure. And
this is the definition of the datatype. So, no memory will be allocated at this stage.
The memory will be allocated after the declaration only. Structure variables can be
declared as following methods:
A. Normal way of declaration
struct student s1, s2;
It is possible to combine the declaration of the structure composition with that of the
structure variables, as shown below:
struct student
{
int regno;
char name[20];
char dept[10];
int year;
} s1, s2;

39
 Structure
● if we are going to declare all the necessary structure variables at
definition time then we can create them without the tag, as shown
below:
struct
{
int regno;
char name[20];
char dept[10];
int year;
} s1, s2;
● Since there is no tag name, additional variables can not be generated
other than this location.

40
Stacks
● Definition
● Basic Stack Operations
● Array Implementation of Stacks

41
 DEFINITION OF THESTACK
● Astack is an ordered collection of items where new items may be
inserted or deleted only at one end, called the top of the stack.

● Astack is a data structure that keeps objects in Last- In-First-Out

(LIFO) order, Objects are added to the top of the stack. Only the
top of the stack can be accessed.

42
BASIC STACK OPERATIONS
● Initialize the Stack.
● Pop an item off the top of the stack (delete an item)
● Push an item onto the top of the stack (insert an
item)
● Is the Stack empty?
● Is the Stack full?
● Clear the Stack
● Determine Stack Size

43
 ARRAYIMPLEMENTATIONOFTHESTACKS
● The stacks can be implemented by the use of arrays and linked lists.
● One way to implement the stack is to have a data structure where a variable
called top keeps the location of the elements in the stack (array). An array is
used to store the elements in the stack.

● The following structure can be used to define the stack data structure:
Alternative 1:
struct stack{
int count; /* keeps the number of
elements in the stack */ int top; /*
indicates the location of the top of
the stack*/ int items[STACKSIZE];
/*array to store stack elements*/
};

Alternative 2: 44
45
46
 Initialize the Stack.
● You can initialize the stack by assigning -1 to the top pointer
to indicate that the array based stack is empty (initialized) as
follows:

● You can write following lines in the main program:

STACK s;
[Link] = -1;

● Alternatively you can use the following function:

void StackInitialize(STACK *Sptr)

{
Sptr->top=-1;
}
47
 Push an item onto the top of the stack (insert an
item)
● The function below can be used to push an item into the stack: Note
that ps can be some other type than integer.
void push(STACK *Sptr, int ps) /*pushes ps into stack*/
{
if(Sptr->top == STACKSIZE-1){
printf("Stack is full\n");
return; /*return back to main function*/
}
else {
Sptr->top++;
Sptr->items[Sptr->top]= ps;
Sptr->count++;
}
}
48
 Pop an item off the top of the stack(delete an item)

The functions below can be used to pop an item from the stack. Note that exit(1) is a library
function in <stdlib.h> which terminates the program. The stacks are assumed to contain integer
elements. Different types can be used.
void pop(STACK *Sptr, int *pptr)
int pop(STACK*Sptr)
{
{
if(Sptr->top == -1){
int pp;
if(Sptr->top = = -1){
printf("Stack is empty\n");
printf("Stack is empty\n"); return;/*return back*/
exit(1); /*exit from the }
function*/ else {
} *pptr = Sptr->items[Sptr->top];
else { Sptr->top--;
pp = Sptr->items[Sptr->top]; Sptr->count--;
Sptr->top--;
}
Sptr->count--;
}
}
return pp;
53
}
EXAMPLE

50
Application of Stacks
● Reversing a String
● Palindrome Example
● Infix, Postfix and Prefix Notations

51
Reversing a String
● Stacks can be used to reverse a sequence. For
example, if a string Computers” is entered by the user
the stack can be used to create and display the reverse
string “sretupmoC” asfollows.

● The program simply pushes all of the characters of the

string into the stack. Then it pops and display until
the stack is empty.

52
 Main Program
#include<stdio.h>
#include<stdlib.h> for(i=0;A[i] != '\0';i++){
#define STACKSIZE50 p = A[i];
push(&s,p);
void push(STACK *, char);
}
char pop(STACK *);
printf("The string in reverse order
is:");
int main()
{ /*popping and printing the string
int i; in reverse order*/
STACK s; while([Link] >= 0){
char p, A[20]; p=pop(&s);
[Link] = -1; /*indicates that the stack is empty printf("%c",p);
at the beginning*/
}
[Link]=0;
printf("Input the string please:\n"); return 0;
gets(A); /* alternatively you can use }
scanf("%s",A); */
58 /*pushing the characters into the stack*/
 PALINDROMEEXAMPLE
● The strings where the reading from the reverse and forward
directions give the same word are called a palindrome. For
example, the string ”radar” is an example for palindrome.

● Among many other techniques stack can be used to

determine if a string is a palindrome or not. This is achieved
by pushing all the letters of a given word into stack and
checking if the letters popped are the same as the letter of
the string.

54
 Struct definition for the stack
STACK
typedef struct{
int count;
int top;
char items[STACKSIZE];/*stack can contain
up to 20 characters*/
}STACK;

55
 Main Program
#include<stdio.h>
#include<stdlib.h> size = [Link];
/*popping and checking if the letters are equal
#define STACKSIZE 25 in rev. & [Link]*/
void push(STACK *, int); for(i=0;i<=size-1;i++){
char pop(STACK *); p=pop(&s);
int main() if(p != A[i])
{ check ++;
int i, check=0, size; }
STACK s; if(check == 0)
char p, A[20]; printf("\nThe string %s is a
[Link]=0; palindrome\n",A);
[Link] = -1; /*indicates that the stack is empty at the else
beginning*/
printf("\nThe string %s is NOT a
printf("Enter the string\n"); palindrome\n",A);
gets(A); /* alternatively you can use scanf("%s",A); */
return 0;
/*pushing the characters of the string into the stack*/
}
for(i=0;A[i]!='\0';i++){
p = A[i];
push(&s,p);
62
}
Push() & Pop() Functions
• void push(STACK *Sptr, int ps) char pop(STACK *Sptr)
• /*pushes ps into stack*/ {
• { char pp;
• if(Sptr->top == STACKSIZE-1){ if(Sptr->top == -1){
• printf("Stack is full\n"); printf("Stack is empty\n");
• exit(1); /*exit from the function*/ exit(1); /*exit from the function*/
• } }
• else { else {
• Sptr->top++; pp = Sptr->items[Sptr->top];
Sptr->count++; Sptr->top--;
• Sptr->items[Sptr->top]= ps; Xcx
Sptr->count--;
• }
}
• }
return pp;
}

57
 INFIX, POSTFIX ANDPREFIXNOTATIONS

58
 INFIX, POSTFIXAND PREFIX NOTATIONS
● Infix, Postfix and Prefix notations are used in many
calculators. The easiest way to implement the
Postfix and Prefix operations is to use stack.
● Infix and prefix notations can be converted to
postfix notation using stack.
● The reason why postfix notation is preferred is

that you don’t need any parenthesis.

59
 INFIX, POSTFIXANDPREFIXNOTATIONS

● In Postfix notation the expression is scanned from

left to right. When a number is seen it is pushed onto
the stack; when an operator is seen the operator is
applied to the two numbers popped from the stack
and the result is pushed back to the stack.

● Example: 6 5 2 3 + 8 * + 3 + *

60
 INFIX, POSTFIXANDPREFIXNOTATIONS
● - The first 4 numbers are pushed onto the stack :

● Example: 6 5 2 3 + 8 * + 3 + *

- Next + is read , so 3 and 2 are popped and their sum (3+2=5) is pushed onto
the stack:

- Next 8 is pushed onto the stack:

61
 INFIX, POSTFIXANDPREFIXNOTATIONS
● - Next * is read, so 8 and 5 are popped and their product
(8*5=40) is pushed onto the stack:

● Example: 6 5 2 3 + 8 * + 3 + *

- Next + is read, so 40 and 5 are popped and their sum

(40+5=45) is pushed onto the stack:

- Next 3 is pushed onto the stack:

62
 INFIX, POSTFIXANDPREFIXNOTATIONS
● - Next + is read , so 3 and 45 are popped and their sum
(3+45=48) is pushed onto the stack:

● Example: 6 5 2 3 + 8 * + 3 + *

- Finally * is read, so 48 and 6 are popped and their product

(6+48=288) is pushed onto the stack:

❖ Note that 6 5 2 3 + 8 * + 3 + * = 288

The corresponding infix notation is:((3+2)*8+5+3)*6

63
Programming Example-Postfix-Infix
● The following program is an example of the
evaluation of a given Postfix expression. Note that the
user may enter any postfix expression as a string. The
program reads the characters in the string one by one
and if the character is a digit (number) then it
converts the character into an integer otherwise uses
the related operation.

64
Struct definition for the stackSTACK
typedef struct{
int top;
int items[STACKSIZE]; /*stack can
contain up to 20integers*/
}STACK;

65
Main program
#include<stdio.h>
#include<stdlib.h>
#define STACKSIZE 20
void push(STACK *, int);
int pop(STACK*);
int calculate(char []);
int main()
{
int result;
char E[50];
printf("Enter your Postfix expression(don't use spacecharacter):\n");
scanf("%s",E);
result = calculate(E);
printf("The result of the Postfix expression%s=%d\n",E,result);
return 0;
}

66
Calculate() function
int calculate(char exp[])
{
STACK s;
[Link] =-1;/*indicates that the stack is empty at the beginning*/ int
i,num1,num2,value;
for(i=0; exp[i]!='\0';i++){
if(exp[i] >='0' && exp[i] <='9') /*checks if exp[i] has adigit*/
push(&s,(int)(exp[i] -'0')); /*converts digit into integer*/
else{ num1= pop(&s);
num2= pop(&s); switch(exp[i]){
case '+': value=num2+num1;break; case '-':
value=num2-num1;break; case '*':
value=num2*num1;break; case '/':
value=num2/num1;break; default : printf("Illegal
Operator\n");
exit(1);
}
push(&s,value);
}
}
return pop(&s);
}

67
 Push() & Pop() Functions
• int pop(STACK*Sptr) void push(STACK *Sptr, int ps)
/*pushes ps into stack*/
• {
{
• int pp;
if(Sptr->top == STACKSIZE-1){
•if(Sptr->top == -1){
printf("Stack is full\n");
printf("Stack is empty\n");
exit(1); /*exit from the function*/
• exit(1); /*exit from the function*/
}
• }
else {
• else {
Sptr->top++;
• pp = Sptr->items[Sptr->top];
Sptr->items[Sptr->top]= ps;
Sptr->top--;
}
• }
}
• return pp;
• }

74
 INFIX TO POSTFIX CONVERSION
● Given Infix Expressions , stack can be used to convert the Infix
Expressions to Postfix expression by using the following Approach:
Scan the Infix expression left to right
If the character x is an operand
o Output the character into the Postfix Expression
If the character x is a left or right parenthesis
o If the character is “(“
Push it into the stack
o if the character is “)”
Repeatedly pop and output all the operators/characters until “(“ is popped
from the stack.
If the character x is a is a regular operator
o Step 1: Check the character y currently at the top of the stack.
o Step 2: If Stack is empty or y=‘(‘ or y is an operator of lower precedence
than
x, then push x into stack.
o Step 3: If y is an operator of higher or equal
precedence than x, then pop and
output y and push x into the stack.

69
ASSIGNMENTI
● Write a C/C++ program to coverts a given Infix
expression with variable a to z and operators ‘+’, ‘-
‘,‘*’ and ‘/’ intoaPostfix Expression.

70
NEXT TOPIC
QUEUE

71