DATA STRUCTURES AND APPLICATIONS BCS304

MODULE 1 DATA STRUCTURES

The Contents of Module 1 is as follows

Introduction to Datastructures:

1. Data Structures,
2. Classifications (Primitive & Non Primitive),
3. Data structure Operations

Review of Pointers:

1. Review of Pointers and Dynamic Memory Allocation.

Array and Structures:

1. Arrays, Dynamically allocated arrays

2. Structures, Self-Referential Structures, and Unions.
3. Representation of Multidimensional Arrays,
4. Polynomials and Sparse Matrices.
5. Strings

Stack:

1. Stacks, Stacks Using Dynamic Arrays,

2. Evaluation and conversion of Expressions

Suggested Learning Resources:

Textbook: 1. Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed, Fundamentals of Data
Structures in C, 2nd Ed, Universities Press, 2014
Reference Books:
1. Seymour Lipschutz, Data Structures Schaum's Outlines, Revised 1 st Ed, McGraw Hill, 2014.
2. Gilberg & Forouzan, Data Structures: A Pseudo-code approach with C, 2 nd Ed, Cengage
Learning,2014.
3. Reema Thareja, Data Structures using C, 3 rd Ed, Oxford press, 2012.
4. Jean-Paul Tremblay & Paul G. Sorenson, An Introduction to Data Structures with Applications,
2nd Ed, McGraw Hill, 2013
5. A M Tenenbaum, Data Structures using C, PHI, 1989
6. Robert Kruse, Data Structures and Program Design in C, 2 nd Ed, PHI, 1996.

Text Book: Chapter-1:1.2 Chapter-2: 2.1 to 2.7 Chapter-3: 3.1,3.2,3.6

Reference Book 1: 1.1 to 1.4

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Data Structures:
Data Structure can be defined as the group of data elements which provides an efficient
way of storing and organizing data in the computer so that it can be used efficiently. Some
examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are
widely used in almost every aspect of Computer Science i.e. operating System, Compiler Design,
Artificial intelligence, Graphics and many more.

CLASSIFICATION OF DATA STRUCTURES

Data structures are generally classified into
• Primitive data Structures
• Non-primitive data Structures

Fig: Data structure classification

1. Primitive data Structures: Primitive data structures are the fundamental data types which are
supported by a programming language. Basic data types such as integer, real, character and
Boolean are known as Primitive data Structures. These data types consists of characters that
cannot be divided and hence they also called simple data types.

2. Non- Primitive data Structures: Non-primitive data structures are those data structures
which are created using primitive data structures. Examples of non-primitive data structures is
the processing of complex numbers, linked lists, stacks, trees, and graphs.

Based on the structure and arrangement of data, non-primitive data structures is further
classified into

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

1. Linear Data Structure

2. Non-linear Data Structure

1. Linear Data Structure: A data structure is said to be linear if its elements form a sequence or
a linear list. There are basically two ways of representing such linear structure in memory.
 One way is to have the linear relationships between the elements represented by means of
sequential memory location. These linear structures are called arrays.
 The other way is to have the linear relationship between the elements represented by
means of pointers or links. These linear structures are called linked lists.
The common examples of linear data structure are Arrays, Queues, Stacks, Linked lists

2. Non-linear Data Structure: A data structure is said to be non-linear if the data are not arranged
in sequence or a linear. The insertion and deletion of data is not possible in linear fashion. This
structure is mainly used to represent data containing a hierarchical relationship between elements.
Trees and graphs are the examples of non-linear data structure.

DATA STRUCTURES OPERATIONS

The data appearing in data structures are processed by means of certain operations. The
following four operations play a major role in this text:
 Traversing: accessing each record/node exactly once so that certain items in the record
may be processed. (This accessing and processing is sometimes called ―visiting‖ the
record.)
 Searching: Finding the location of the desired node with a given key value, or finding
the locations of all such nodes which satisfy one or more conditions.
 Inserting: Adding a new node/record to the structure.
 Deleting: Removing a node/record from the structure.

The following two operations, which are used in special situations:

 Sorting: Arranging the records in some logical order (e.g., alphabetically according to
some NAME key, or in numerical order according to some NUMBER key, such as social
security number or account number)
 Merging: Combining the records in two different sorted files into a single sorted file.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Review of Pointers:
• Pointer is a variable which holds the address of other variable. In pointer we use two operators
&(address operator) and (*)Dereference operator.

Pointer declaration and Initialization:

• Dereference operator(*) are used for defining pointer-variable.
• The syntax is shown below:
data_type *ptr_var_name;
• For ex:
int *a; // a as pointer variable of type int
float *c; // c as pointer variable of type

Steps to access data through pointers:

1) Declare a data-variable ex: int c;

2) Declare a pointer-variable ex: int *pc;
3) Initialize a pointer-variable ex: pc=&c;
4) Access data using pointer-variable ex: printf("%d",*pc);

int c=300,*ptr;
ptr =&c;

Here ptr is a pointer; it can hold the address of variable c & is called reference(address) operator

Example: Program to illustrate working of pointers.

#include<stdio.h>
void main()
{
int *pc;
int c;
c=22;
printf("Address of c: %d \n", &c);
printf("Value of c: %d \n", c);
pc=&c;
printf("Address of pointer pc: %d \n", pc);
printf("Content of pointer pc: %d",*pc);
}

Output:
Address of c: 1232
Value of c: 22

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Address of pointer pc: 1232

Content of pointer pc: 22

NULL POINTER : A NULL pointer is defined as a special pointer value that points to
'\0'(nowhere) in the memory. In other words, NULL pointer does not point to any part of the
memory.
• For ex:
int *p=NULL;
DANGLING POINTER: A pointer variable which do not contain valid address is called Dangling
Pointer.
int *p;
float *p;
char *p;

void Pointer: A void pointer is a pointer that has no associated data type with it. A void pointer
can hold an address of any type and can be type-casted to any type.
#include <stdio.h>
int main()
{
int a = 10;
char b = 'x';

// void pointer holds address of int 'a'

void* p = &a;
// void pointer holds address of char 'b'
p = &b;
}
Dynamic Memory Allocation:
Dynamic memory allocation is the process of allocating memory-space during execution-time i.e.
run time.If there is an unpredictable storage requirement, then the dynamic allocation technique is
used.This allocation technique uses predefined functions to allocate and release memory for data
during execution-time.There are 4 library functions for dynamic memory allocation:

malloc()

calloc()

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

free()

realloc()

These library functions are defined under "stdlib.h"

malloc()

The name malloc stands for "memory allocation".This function is used to allocate the requirement
memory-space during execution-time. The syntax is shown below:

data_type *p;
p=(data_type*)malloc(size);

here p is pointer variable data_type can be int, float or char size is number of bytes to be allocated

If memory is successfully allocated, then address of the first byte of allocated space is returned.
If memory allocation fails, then NULL is returned.

For ex:

ptr=(int*)malloc(100*sizeof(int));

The above statement will allocate 200 bytes assuming sizeof(int)=2 bytes.

Example: Program to find sum of n elements entered by user. Allocate memory dynamically using
malloc() function.

Program: C Program to Demonstrate malloc() function

#include <stdio.h>
#include <stdlib.h>
void main()
{
int n,i,*ptr;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)malloc(n*sizeof(int));
printf("Enter elements of array: ");

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

for(i=0;i<n;++i)
{
scanf("%d",ptr+i);
}
printf("The Entered Elements are as follows\n");
for(i=0;i<n;++i)
{
printf("%d\n",*(ptr+i));
}
}
Output:

Enter number of elements: 3

Enter elements of array: 2 5 1
The Entered Elements are as follows
2
5
1

calloc()

The name calloc stands for "contiguous allocation". This function is used to allocate the blocks of
memory required during execution-time and at the same time, automatically initialize memory
with 0's. The syntax is shown below:
data_type *p;
p=(data_type*)calloc(n,size);
If memory is successfully allocated, then address of the first byte of allocate space is returned. If
memory allocation fails, then NULL is returned.
The allocated memory is initialized automatically to 0's.
For ex:

ptr=(int*)calloc(25,sizeof(int));
The above statement allocates contiguous space in memory for an array of 25 elements each of
size of int, i.e., 2 bytes.

Example: Program to find sum of n elements entered by user. Allocate memory dynamically using
calloc() function.
Program: C Program to Demonstrate calloc() function
#include <stdio.h>
#include <stdlib.h>
void main()
{
int n,i,*ptr;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)calloc(n,sizeof(int));

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

printf("Enter elements of array: ");

for(i=0;i<n;++i)
{
scanf("%d",&ptr[i]);
}
printf("The Entered Elements are as follows\n");
for(i=0;i<n;++i)
{
printf("%d\n",*(ptr+i));
}
}
Output:
Enter number of elements: 3
Enter elements of array: 2 5 1
The Entered Elements are as follows
2
5
1
realloc()

If the previously allocated memory is insufficient or more than sufficient. Then, you can change
memory-size previously allocated using realloc().

The syntax is shown below:

ptr=(data_type*)realloc(ptr,newsize);

Program to illustrate working of realloc().

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void main()
{
char *str;
str=(char*)malloc(10*sizeof(char));
strcpy(str,"Computer");
str=(char*)realloc(str,40);
strcpy(str,"Computer Science and Engineering");
printf("%s",str);
}
output: Computer Science and Engineering

free()

Dynamically allocated memory with either calloc() or malloc() does not get return on its own. The
programmer must use free() explicitly to release space.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

The syntax is shown below: free(ptr);

This statement causes the space in memory pointed by ptr to be deallocated.

char *str;
str=(char*)malloc(10*sizeof(char));
free(str);
str=NULL;

Advantages of pointers
1. Pointer reduces the code and improves the performance, it is used to retrieving strings,
trees, etc. and used with arrays, structures, and functions.
2. We can return multiple values from a function using the pointer.
3. It makes you able to access any memory location in the computer's memory.

Disadvantages of Pointer

1. Uninitialized pointers might cause segmentation fault.

2. Dynamically allocated block needs to be freed explicitly.
3. If pointers are updated with incorrect values, it might lead to memory corruption

Structure Definition: “A structure can be defined a group of related data elements of same
or different data type with a common name”.
or
“A structure can be defined as a user defined data type that helps the programmer to store and
process a group of related data elements of different data type with a common name”.

Example 1. To store and process student information like roll number, name, total marks and
grade in computer’s memory, the programmer defines own data type.

Syntax Example
Struct tagname{ struct student {

Type1 Member1; int rno;

Type2 Member2; char name[25];
Type3 Member3; int marks;
Type4 Member4; char grade;

}; };

The above written code creates the new data type named struct student to store and process
student information. Now, programmer can use this data type like other built in data types to define
variables.

e.g. struct student s; /* s is variable of type struct student*/

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Now, programmer can store and process the data within the structure variable.

s.rno=101;
strcpy(s.name,”John”);
s.marks=600;
s.grade=’A’;

Structure Declaration: A Structure can be declared using three different ways as shown below.
1. Tagged Structure
2. Structure without tag
3. Type defined structures
Example1. Structure Definition to store and process student information.
struct student /* definition of structure */
{
int rno;
char name[25];
int marks;
char grade;
};
Example2. Structure Definition to store and process book information.
struct book /* structure declaration*/
{
int book_no;
char book_name[25];
int book_price;
};

Observe the following points:

 just by defining the structure as shown above memory is not reserved for the
structure.Memory is allocated for structures only when the variables are declared.
 Memory allocated to the above structure is 2 bytes for book_no 25 bytes for book_name
and 2 bytes for book_price total=29 bytes of memory is allocated for the each variable of
structure.
Declaration of Structure Variables
Syntax: struct tag_name variables_list;
 Where, Struct is a keyword
 Tag_name valid identifier or name of structure
 Variables_list List of variables
Example1. Structure to store and process student information.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

struct student /* definition of structure*/

{
int rno; /* Here, No memory is allocated for structure*/
char name[25];
int marks;
char grade;
};
struct student s; /* To store info. of 1 student*/
struct student s1,s2,s3; /* To store info.of 3 students*/
struct student s[50]; /* To store info. of 50 students*/

/* Write a C Program To read and display student

information by using structure */
#include<stdio.h>
struct student
{
int rno;
char name[25];
float avg;
};
void main()
{
struct student s;
printf("Enter student roll no:");
scanf("%d",&s.rno);
printf("Enter student name:");
scanf("%s",&s.name);
printf("Enter student average marks:");
scanf("%f",&s.avg);
printf("\n STUDENT DETAILS ARE AS FOLLOWS");
printf("\n Roll no=%d",s.rno);
printf("\n Name=%s",s.name);
printf("\n Average marks=%f",s.avg);

o/p:
Enter student roll no: 101
Enter student name: Thomas
Enter student average marks: 69
STUDENT DETAILS ARE AS FOLLOWS
Roll no= 101
Name= Thomas

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Average marks= 69
Array of Structures: The programmers can define arrays of structures variables to store and
process large volume of data i.e. a group of related data elements of dissimilar type.
Syntax: struct tag_name array_name[size];
Example:
To store student information(roll no, name & average marks) of ‘n’ students.
struct student
{
int rno;
char name[25];
int marks;
};
struct student s[25]; /* Array of size 25 */

/*Write a C Program to read and display the information of n students*/

#include<stdio.h>
#include<conio.h>
void main()
{
int i,n;
struct student
{
int rno;
char name[25];
float avg;
};
struct student s[100];
clrscr();
printf(“Enter the number of students\n”);
scanf(“%d”,&n);
printf(“ Enter %d students information\n”);
for(i=0;i<n;i++)
{
printf(“Enter the details\n”);
printf("Enter student roll no:");
scanf("%d",&s[i].rno);
printf("Enter student name:");
scanf("%s",s[i].name);
printf("Enter student average marks:");
scanf("%f",&s[i].avg);
}
for(i=0;i<n;i++)
{
printf("\n STUDENT DETAILS ARE");

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

printf("\n Roll no=%d",s[i].rno);

printf("\n Name=%s",s[i].name);
printf("\n Average marks=%f",s[i].avg);
}
}

Nested Structure: The C language permits the programmers to nest structures within one another
i.e. structure can contain another structure member.
Example:
struct date
{
int dd, mm, yy;
};
struct student
{
char name[25];
struct date dob; /* nesting of structure member*/
}s;
Example:Program to store student information and display
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
struct subject
{
int marks1;
int marks2;
int marks3;
};
typedef struct
{
char name[25];
int usn;
struct subject marks;
}STUDENT;
void main()
{
STUDENT a[100], temp;
int i,n;
printf(“Enter the number of student\n”);
scanf(“%d”,&n);
printf(“Enter all details of students\n”) ;
for(i=0;i<n;i++){
printf(“Enter Name”);
scanf(“%s”,a[i].name);

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

printf(“Enter USN”);
scanf(“%d”,&a[i].usn);
printf(“Enter First IA Marks\n”);
scanf(“%d”, &a[i].marks.marks1);
printf(“Enter Second IA marks\n”);
scanf(“%d”,&a[i].marks.marks2);
printf(“Enter third IA marks\n”);
scanf(“%d”,&a[i].marks.marks3);
}
printf(“details of students are as follows\n”);
printf(“Name\tUSn\tIAMARKS1\t IAMARKS2\t IAMARKS3”);
for(i=0;i<n;i++){
printf (“%s”,a[i].name);
printf (“%d”,&a[i].usn);
printf (“%d”, &a[i].marks.marks1);
printf (“%d”,&a[i].marks.marks2);
printf (“%d”,&a[i].marks.marks3);
printf(“\n”);
}
}
Self Referential structures are those structures that have one or more pointers which point to the
same type of structure, as their member.

In other words, structures pointing to the same type of structures are self-referential in nature.
Example:

Types of Self Referential Structures

 Self Referential Structure with Single Link
 Self Referential Structure with Multiple Links

Self Referential Structure with Single Link: These structures can have only one self-pointer
as their member. The following example will show us how to connect the objects of a self-
referential structure with the single link and access the corresponding data members. The
connection formed is shown in the following figure.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

#include <stdio.h>

struct node {
int data1;
char data2;
struct node* link;
};
int main()
{
struct node ob1; // Node1
// Initialization
ob1.link = NULL;
ob1.data1 = 10;
ob1.data2 = 20;
struct node ob2; // Node2
// Initialization
ob2.link = NULL;
ob2.data1 = 30;
ob2.data2 = 40;

// Linking ob1 and ob2

ob1.link = &ob2;
// Accessing data members of ob2 using ob1
printf("%d", ob1.link->data1);
printf("\n%d", ob1.link->data2);
return 0;
}
Output:
30
40
Applications self-referential structures: Self-referential structures are very useful in creation
of other complex data structures like:
 Linked Lists
 Stacks
 Queues
 Trees
 Graphs etc

Union:

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Union is a user defined data type that is used to hold different data type & it doesn't occupy sum
of all the members size like structure, instead it occupies the memory of largest member only. It
shares memory of largest member to the members of the structure. The union keyword is used
to define union. The syntax to define union:
union union_name
{
data_type member1;
----------------------
--------
data_type memeberN;
};
Example to define union for employee.
union employee
{
int id;
char name[50];
float salary;
};
Ex:

#include <stdio.h>
union employee
{
int id;
char name[50];
}e1;
//declaring e1 variable for union
void main( )
{
e1.id=1; //store first employee information
strcpy(e1.name, "S");//copying string into char array

printf( "employee 1 id : %d\n", e1.id); //printing first employee information

printf( "employee 1 name : %s\n", e1.name);

Output: employee 1 id :
employee 1 name : S

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

S.NO Structure Union

Structure allocates storage space for all Union allocates one common storage space for all its
1 its members separately. Keyword: struct members. Union finds that which of its member needs
high storage space over other members and allocates
that much space. Keyword: union
Structure occupies larger memory space. Union occupies lower memory space over structure.
2

We can access all members of structure at We can access only one member of union at a time.
3 a time.

Structure example: struct student { int Union example: union student { int mark; double
4 mark; double average; }; average; };

For above structure, memory allocation For above union, only 8 bytes of memory will be
5 will be like below. int mark – 2 Bytes allocated since double data type will occupy
double average – 8B Total memory maximum space of memory over other data types.
allocation = 2+8 = 10 Bytes Total memory allocation = 8 Bytes

Polynomials are algebraic expressions that consist of exponents and coefficients. An example of
a polynomial with one variable is x2+x-12
Representation of Polynomial in C is to define typedef structure as follows:
MAX_TERMS 100
typedef struct{
float coeff;
int expon;
}polynomial;
Polynomial terms[MAX_TERMS];
int avail=0;

A(x) =2x1000+1 and B(x) =x4+10x3+3x2+1

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

The above figure shows how these polynomials are stored in the array terms. The index of the first
term of A and B is given by startA and startB, while finishA and finishB give the index of the last
term of A and B.
• The index of the next free location in the array is given by avail.
• For above example, startA=0, finishA=1, startB=2, finishB=5, & avail=6.

Polynomial Addition
• C function is written that adds two polynomials, A and B to obtain D =A + B.
• To produce D (x), padd( ) is used to add A (x) and B (x) term by term. Starting at position
avail, attach( ) which places the terms of D into the array, terms.
C Function to add two polynomials:

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

The time for the remaining two for loops is bounded by O(n + m) because we cannot iterate
the first loop more than m times and the second more than n times. So, the asymptotic
computing time of this algorithm is O(n +m).

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

SPARSE MATRIX
A matrix contains m rows and n columns of elements as illustrated in below figures. In this
figure, the elements are numbers. The first matrix has five rows and three columns and the second
has six rows and six columns. We write m x n (read "m by n") to designate a matrix
with m rows and n columns. The total number of elements in such a matrix is mn. If m equals n,
the matrix is square.

What is Sparse Matrix? A matrix which contains many zero entries or very few non-zero entries
is called as Sparse matrix. In the figure B contains only 8 of 36 elements are nonzero and that is
sparse.

Important Note: A sparse matrix can be represented in 1-Dimension, 2- Dimension and 3-

Dimensional array. When a sparse matrix is represented as a two-dimensional array as shown in
Figure B, more space is wasted.

Example: consider the space requirements necessary to store a 1000 x 1000 matrix that has only
2000 non-zero elements. The corresponding two-dimensional array requires space for 1,000,000
elements. The better choice is by using a representation in which only the nonzero elements are
stored.

Sparse Matrix Representation

 An element within a matrix can characterize by using the triple <row,col,value> This
means that, an array of triples is used to represent a sparse matrix.
 Organize the triples so that the row indices are in ascending order.
 The operations should terminate, so we must know the number of rows and columns, and
the number of nonzero elements in the matrix.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Implementation of the Create operation as below:

SparseMatrix Create(maxRow, maxCol) ::=
#define MAX_TERMS 101 /* maximum number of terms +1*/
typedef struct {
int col;
int row;
int value;
} term;
term a[MAX_TERMS];

The below figure shows the representation of matrix in the array “a” a[0].row contains the number
of rows, a[0].col contains the number of columns and a[0].value contains the total number of
nonzero entries.
• Positions 1 through 8 store the triples representing the nonzero entries. The row index is in the
field row, the column index is in the field col, and the value is in the field value. The triples are
ordered by row and within rows by columns.

Row Col value Row Col value

a[0] 6 6 8 b[0] 6 6 8

a[1] 0 0 15 b[1] 0 0 15

a[2] 0 3 22 b[2] 0 4 91

a[3] 0 5 -15 b[3] 1 1 11

a[4] 1 1 11 b[4] 2 1 3

a[5] 1 2 3 b[5] 2 5 28

a[6] 2 3 -6 b[6] 3 0 22

a[7] 4 0 91 b[7] 3 2 -6

a[8] 5 2 28 b[8] 5 0 15

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Figure: Sparse Matrix and its transpose stored as triples.

Write a C function to transpose the sparse matrix

Write a C function to fast transpose the sparse matrix

void fast_transpose(sparse a[], sparse b[])

{
int row_terms[100], start_pos[100];
int i, j, p;
int numTerms = a[0].val;
int numCols = a[0].col;

b[0].row = numCols;
b[0].col = a[0].row;
b[0].val = numTerms;

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

if(numTerms>0)
{
for(i =0; i<numCols; i++)
row_terms[i] = 0;
for(i=1; i<=numTerms; i++)
row_terms[a[i].col]++;
start_pos[0]=1;
for(i=1; i<numCols; i++)
start_pos[i] = start_pos[i-1] + row_terms[i-1];
for(i=1; i<=numTerms; i++)
{
j = start_pos[a[i].col]++;
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].val = a[i].val;
}
}

DYNAMICALLY ALLOCATED ARRAYS

One Dimensional Array

While writing computer programs, if finds ourselves in a situation where we cannot determine
how large an array to use, then a good solution to this problem is to defer this decision to run
time and allocate the array when we have a good estimate of the required array size.
Example:
int i, n, *list;
printf(“Enter the number of numbers to generate:”);
scanf(―%d‖, &n);
if(n<1) {
fprintf (stderr, ―Improper value of n \n‖);
exit(EXIT_FAILURE);
}
MALLOC (list, n*sizeof(int));
The programs fails only when n<1 or insufficient memory to hold the list of numbers that are to
be sorted.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Two Dimensional Arrays

C uses array-of-arrays representation to represent a multidimensional array. The two
dimensional arrays is represented as a one-dimensional array in which each element is
itself a one-dimensional array.
Example: int x[3][5];

C find element x[i][j] by first accessing the pointer in x[i].

Where x[i] = α+ i* sizeof(int), which give the address of the zeroth element of row i of
the array.
Then adding j*sizeof(int) to this pointer ( x[i] ) , the address of the [j]th element of row i
is determined.
x[i] = α+ i* sizeof(int)
x[j] = α+ j* sizeof(int)
x[i][j] = x[i]+ i* sizeof(int)

Creation of Two-Dimensional Array Dynamically

int **myArray;
myArray = make2dArray(5,10);
myArray[2][4]=6;

int ** make2dArray(int rows, int cols) {

/* create a two dimensional rows X cols array */
int **x, i; MALLOC(x, rows * sizeof (*x));
/*get memory for row pointers*/
for (i= 0;i<rows; i++)
/* get memory for each row */
MALLOC(x[i], cols * sizeof(**x));
return x;
}
The second line allocates memory for a 5 by 10 two-dimensional array of integers and the
third line assigns the value 6 to the [2][4] element of this array.
STACKS, RECURSION AND QUEUES

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

STRING OPERATION

Substring
Accessing a substring from a given string requires three pieces of information:

(1) The name of the string or the string itself

(2) The position of the first character of the substring in the given string
(3) The length of the substring or the position of the last character of the substring.

Syntax: SUBSTRING (string, initial, length)

The syntax denote the substring of a string S beginning in a position K and having a length L.

Ex: SUBSTRING ('TO BE OR NOT TO BE’, 4, 7) = 'BE OR N’ SUBSTRING ('THE END', 4, 4)

= ' END'

Indexing
Indexing also called pattern matching, refers to finding the position where a string pattern P first
appears in a given string text T. This operation is called INDEX

Syntax: INDEX (text, pattern)

If the pattern P does not appears in the text T, then INDEX is assigned the value 0.
The arguments “text” and “pattern” can be either string constant or string variable.

Concatenation
Let S1 and S2 be string. The concatenation of S1 and S2 which is denoted by S1 // S2, is the string
consisting of the characters of S1 followed by the character of S2.

Ex:
(a) Suppose S1 = 'MARK' and S2= ‘TWAIN' then
S1 // S2 = ‘MARKTWAIN’

Concatenation is performed in C language using strcat function as shown below strcat

(S1, S2); Concatenates string S1 and S2 and stores the result in S1

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

strcat ( ) function is part of the string.h header file; hence it must be included at the time of pre-
processing

Length
The number of characters in a string is called its length.

Syntax: LENGTH (string)

Ex: LENGTH (‘computer’) = 8

String length is determined in C language using the strlen( ) function, as shown below:

X = strlen ("sunrise");

strlen function returns an integer value 7 and assigns it to the variable X

Similar to strcat, strlen is also a part of string.h, hence the header file must be included at the time of
pre-processing.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

PATTERN MATCHING ALGORITHMS

Pattern matching is the problem of deciding whether or not a given string pattern P appears in a string
text T. The length of P does not exceed the length of T.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

First Pattern Matching Algorithm

The first pattern matching algorithm is one in which comparison is done by a given pattern P with
each of the substrings of T, moving from left to right, until a match is found.

WK = SUBSTRING (T, K, LENGTH (P))

• Where, WK denote the substring of T having the same length as P and beginning with the Kth
character of T.
• First compare P, character by character, with the first substring, W1. If all the characters are the
same, then P = W1 and so P appears in T and INDEX (T, P) = 1.
• Suppose it is found that some character of P is not the same as the corresponding character of
W1. Then P ≠ W1
• Immediately move on to the next substring, W2 That is, compare P with W2. If P ≠ W2 then
compare P with W3 and so on.
• The process stops, When P is matched with some substring WK and so P appears in T and
INDEX(T,P) = K or When all the WK'S with no match and hence P does not appear in T.
• The maximum value MAX of the subscript K is equal to LENGTH(T) -LENGTH(P) +1.

Algorithm: (Pattern Matching)

P and T are strings with lengths R and S, and are stored as arrays with one character per element. This
algorithm finds the INDEX of P in T.

1. [Initialize.] Set K: = 1 and MAX: = S - R + 1

2. Repeat Steps 3 to 5 while K ≤ MAX
3. Repeat for L = 1 to R: [Tests each character of P]
If P[L] ≠ T[K + L – l], then: Go to Step 5

[End of inner loop.]

4. [Success.] Set INDEX = K, and Exit

5. Set K := K + 1
[End of Step 2 outer loop]

6. [Failure.] Set INDEX = O

7. Exit

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Observation of algorithms
• P is an r-character string and T is an s-character string
• Algorithm contains two loops, one inside the other. The outer loop runs through each successive
R-character substring WK = T[K] T[K + 1] ... T[K+R-l] of T.
• The inner loop compares P with WK, character by character. If any character does not match, then
control transfers to Step 5, which increases K and then leads to the next substring of T.
• If all the R characters of P do match those of some WK then P appears in T and K is the INDEX of
P in T.
• If the outer loop completes all of its cycles, then P does not appear in T and so INDEX = 0.

Complexity
The complexity of this pattern matching algorithm is equal to O(n2)

Second Pattern Matching Algorithm

The second pattern matching algorithm uses a table which is derived from a particular pattern P but is
independent of the text T.

For definiteness, suppose

P = aaba

This algorithm contains the table that is used for the pattern P = aaba.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

The table is obtained as follows.

• Let Qi denote the initial substring of P of length i, hence Q0 = A, Q1 = a, Q2 = a2, Q3
= aab, Q4 = aaba = P (Here Q0 = A is the empty string.)
• The rows of the table are labeled by these initial substrings of P, excluding P itself.
• The columns of the table are labeled a, b and x, where x represents any character that doesn't
appear in the pattern P.
• Let f be the function determined by the table; i.e., let f(Qi, t) denote the entry in the table in row
Qi and column t (where t is any character). This entry f(Qi, t) is defined to be the largest Q that
appears as a terminal substring in the string (Qi t) the concatenation of Qi and t.

For example, a2 is the largest Q that is a terminal substring of Q2a = a3, so f(Q2, a)
= Q2 A is the largest Q that is a terminal substring of Q1b = ab, so f(Q1, b) = Q0 a is
the largest Q that is a terminal substring of Q0a = a, so f(Q0, a) = Q1 A is the largest
Q that is a terminal substring of Q3a = a3bx, so f(Q3, x) = Q0

Although Q1 = a is a terminal substring of Q2a = a3, we have f(Q2, a) = Q2 because Q2 is also a terminal
substring of Q2a = a3 and Q2 is larger than Q1. We note that f(Qi, x) = Q0 for any Q, since x does not
appear in the pattern P Accordingly, the column corresponding to x is usually omitted from the table.

Pattern matching Graph

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

The graph is obtained with the table as follows.

First, a node in the graph corresponding to each initial substring Qi of P. The Q's are called the states of
the system, and Q0 is called the initial state.

Second, there is an arrow (a directed edge) in the graph corresponding to each entry in the table.
Specifically, if

f(Qi, t) = Qj
then there is an arrow labeled by the character t from Qi to Qj

For example, f(Q2, b) = Q3 so there is an arrow labeled b from Q2 to Q3

For notational convenience, all arrows labeled x are omitted, which must lead to the initial state Qo.

The second pattern matching algorithm for the pattern P = aaba.

• Let T = T1 T2 T3 ... TN denote the n-character-string text which is searched for the pattern P.
Beginning with the initial state Q0 and using the text T, we will obtain a sequence of states S1,
S2, S3, ... as follows.
• Let S1 = Q0 and read the first character T1. The pair (S1, T1) yields a second state S2; that is,
F(S1, T1) = S2, Read the next character T2, The pair (S2, T2) yields a state S3, and so on.
There are two possibilities:

1. Some state SK = P, the desired pattern. In this case, P does appear in T and its index is K -
LENGTH(P).
2. No state S1, S2, ... , SN +1 is equal to P. In this case, P does not appear in T.

Algorithm: (PATTERN MATCHING) The pattern matching table F(Q1, T) of a pattern P is in memory, and
the input is an N-character string T = T1 T2 T3 …… TN. The algorithm finds the INDEX of P in T.

1. [Initialize] set K: =1 ans S1 = Q0

2. Repeat steps 3 to 5 while SK ≠ P and K ≤ N
3. Read TK
4. Set SK+1 : = F(SK, TK) [finds next state]
5. Set K: = K + 1 [Updates counter]
[End of step 2 loop]

6. [Successful ?]
If SK = P, then

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

INDEX = K – LENGTH (P)

Else

INDEX = 0

[End of IF structure]

7. Exit.

STACKS:
Definition: A stack is a list of elements in which an element may be inserted or deleted only at
one end called top end of the stack. This means, In particular, that elements are removed from a
stack in the reverse order of that in which they were inserted into stack.

Basic operations associated with stack are as follows:

a) “PUSH” is the term used to insert an element into stack.
b) “POP” is the term used to delete an element from a stack.

A Stack is an ordered list on which insertions (Pushes and adds) and deletions (Pops and removes)
are made at same end is called the top. Given Stack S = (a0, a1 a2 a3 a4 a5………. an-1), we say that a0
is the bottom element, an-1 is the top element. Since last element is inserted into a stack is the first
element removed, a stack is also known as a Last-In-First-Out (LIFO) list.

Representation of Stack:

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Stack ADT:
ADT Stack is
 Objects: a finite ordered list with zero or more elements.
 Functions: for all stack ϵ Stack, item ϵ element, maxSTackSize ϵ positive
integer
1. Stack CreateS(maxStackSize)::= Create an empty stack whose maximum size is
maxStackSize.
2. Boolean isFull(stack,maxStackSize)::=
if (number of elements in stack = = maxStackSize)
return TRUE
else
return FALSE
3. Stack Push(stack,item)::=
if (isFull(stack))
stackFull
else
insert item into top of the stack and return.
4. Boolean IsEmpty(stack)::=
if (stack = = CreateS(maxStackSize()))
return TRUE

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

else
return FALSE
5. Element Pop(stack)::=
if (IsEmpty(stack)) return
else remove and return the element at the top of the stack.

STACK OPERATIONS
1. Push( ) operation : Write a C function to add an item in to a stack.
void push(){

/* add an item to the global stack */

If(top>=MAX_STACK_SIZE-1)
stackFull()
stack[++top] = item
}
2. Pop( ) operation : Write a C function to remove an item from a stack.
element pop(){

/* delete and return the top item from the stack */

If(top = =-1)
stackEmpty()
return stack[top--]
}
Array Representation of STACKS: Stacks are represented in the computer in various ways,
usually by means of a one way list or linear array. In stack we use TOP pointer initially
when stack is empty TOP=-1 or TOP = NULL MAXTACKSIZE=7 Where
MAXSTACKSIZE is the no of elements stack can held. If TOP >MAXSTACKSIZE then
stack overflow occurs which means there is no space to add element in to the stack.

Fig: Array representation of stack.

STACK using Dynamic arrays:

Stack CreateS() ::= typedef struct {

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

int key;
}element;
Element *stack;
MALLOC(stack,sizeof(*stack));
int capacity=1;
int top=-1;
void stackFull(){

REALLOC(stack,2*capacity*sizeof(*stack))
Capacity= Capacity*2;
}

Applications of STACK:
1. POLISH Notation
2. Evaluation of a Postfix expression
3. Transforming an infix expression into Postfix expression.
Infix notation(Infix Expression): The operator symbol is placed between its two operands.

Example: (A + B) * (C - D)

Prefix Notation(Polish Notation/Prefix Expression):The operator symbol is placed before its

two operands.
Example: * + A B – C D

(A+B)*C=[+AB]*C=*+ABC

A+(B*C)=A+[*BC]=+A*BC

(A+B)/(C-D)=[+AB]/[-CD]=/+AB-CD

Postfix Notation(Reverse Polish Notation/Postfix Expression): The operator symbol is placed

after its two operands. The postfix notation is called as suffix notation and is also referred to reverse
polish notation.
Example: A B + C D - *

Operator Precedence and Associativity

Operator Precedence Associativity

( ),[ ] 1 Left to right

Exponentiation ($ or ↑ or ^) 2 Right to Left

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

*, / 3 Left to right

+, - 4 Left to right

Evaluation of a Postfix Expression

Algorithm: This algorithm finds the VALUE of an arithmetic expression P written in postfix
notation.
1. Add a right parenthesis “)” at the end of P.[This acts as sentinel]
2. Scan P from left to right and repeat Step 3 and Step 4 for each element of P until the sentinel
“)” is encountered.
3. If an operand is encountered, put it on STACK.
4. If an operator is encountered then:
a) Remove the two top elements of STACK, where A is the top element and B is the
next top element.
b) Evaluate B A
c) Place the result of (b) back on STACK.
[End of If step]
[End of Step 2 loop.]
5. Set VALUE equal to the top element on STACK.
6. EXIT.
Evaluate the Following Expression
P: 5,6,2,+,*,12,4,/,-

5 6 2 + * 12 4 / - )

1 2 3 4 5 6 7 8 9 10

S.NO Symbols Scanned STACK

(1) 5 5

(2) 6 5,6

(3) 2 5,6,2

(4) + 5,8

(5) * 40

(6) 12 40,12

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

(7) 4 40,12,4

(8) / 40,3

(9) - 37

(10) )

Transforming Infix expression into Postfix expression

Algorithm: POLISH(Q,P)This algorithm finds the VALUE of an arithmetic expression P written
in postfix notation.
1. PUSH “(” On to STACK, and add ”)” to the end of Q.
2. Scan Q from left to right and repeat Step 3 to Step 6 for each element of Q until the STACK
is empty.
3. If an operand is encountered, add it to P.
4. If a left parenthesis is encountered, PUSH it onto STACK.
5. If an operator is encountered then:
a) Repeatedly pop from STACK and add to P each operator(on the top of the STACK)
which has the same precedence as or higher precedence than
b) Add to the STACK
[End of If step]
6. If a right parenthesis is encountered then:
a) Repeatedly pop from STACK and add to P each operator(on top of the STACK)
until a left parenthesis is encountered.
b) Remove the left parenthesis.[Do not add left parenthesis to P.]
[End of If structure]
[End of step 2 loop]
7. EXIT.
Convert the following Infix expression into Postfix expression.

S.NO Symbols Scanned STACK Expression P

(1) A ( A

(2) + (+ A

(3) ( (+( A

(4) B (+( AB

(5) * (+(* AB

(6) C (+(* ABC

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

(7) - (+(- ABC*

(8) ( (+(-( ABC*

(9) D (+(-( ABC*D

(10) / (+(-(/ ABC*D

(11) E (+(-(/ ABC*DE

(12) ↑ (+(-(/↑ ABC*DE

(13) F (+(-(/↑ ABC*DEF

(14) ) (+(- ABC*DEF↑/

(15) * (+(-* ABC*DEF↑/

(16) G (+(-* ABC*DEF↑/G

(17) ) (+ ABC*DEF↑/G*-

(18) * (+* ABC*DEF↑/G*-

(19) H (+* ABC*DEF↑/G*-H

(20) ) ABC*DEF↑/G*-H*+

/* Write a C program to implement STACK Operations */

#include <stdio.h>
#include <stdlib.h>
int stack[6];
int top=-1,k=0;
int size;
void push();
void pop();
void display();
void main() {
int choice,f;
printf("Enter the size for stack\n");
scanf("%d",&size);
printf("1.Push\n2.Pop\n3.Display\n4.Exit\n");
while(1) {

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

printf("Enter the choice\n");

scanf("%d",&choice);
switch(choice)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:exit(0);
default:printf("Wrong choice...\n");
}
}
}
void push() {
int num;
if(top==(size-1)){
printf("Stack Overflow\n");
} else {
printf("Enter the number to be pushed\n");
scanf("%d",&num);
top++;
stack[top]=num;
}
}
void pop() {
int num;
if(top==-1) {
printf("Stack Underflow\n");
} else {
num=stack[top];
printf("Popped element is %d\n",num);
top--;
}
}

void display()

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

{
int i;
if(top==-1) {
printf("Stack Underflow\n");
} else {
printf("Stack Contents....\n");
for(i=top;i>=0;i--) {
printf("%d\n",stack[i]);
}
}
}

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

Recursion:
Recursion: Suppose P is a procedure containing either a call statement to itself or a call statement
to a second procedure that may eventually result in a statement back to the original procedure P
Then P is called a recursive procedure. So that the program will not continue to run indefinitely, a
recursive procedure must have the following two properties or rules.
a) There must be a certain criteria called base criteria for which the procedure will not call
itself.
b) Each time the procedure does call itself(directly or indirectly), it must be closer to the base
criteria.

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

DEPARTMENT OF ISE,RIT HASSAN

DATA STRUCTURES AND APPLICATIONS BCS304

LAB PROGRAM
Solving Tower of Hanoi problem with n disks. Source code
#include<stdio.h>
#include<math.h>
void tower(int n, int source, int temp, int destination)
{
if (n == 0) return;
tower(n - 1, source, destination, temp);
printf("\nMove disc %d from %c to %c", n, source, destination);
tower(n - 1, temp, source, destination);
}
void main() {
int n;
printf("\nEnter the number of discs: \n");
scanf("%d", & n); tower(n, 'A', 'B', 'C');
printf("\n\nTotal Number of moves are: %d", (int) pow(2, n) - 1);
}

DEPARTMENT OF ISE,RIT HASSAN