DATA STRUCTURES

MODULE 1
INTRODUCTION TO DATA STRUCTURES: Data Structures, Classifications
(Primitive
& Non-Primitive), Data structure Operations
Review of pointers and dynamic Memory Allocation
ARRAYS and STRUCTURES: Arrays, Dynamic Allocated Arrays, Structures and
Unions,
Polynomials, Sparse Matrices, representation of Multidimensional Arrays, Strings
STACKS: Stacks, Stacks Using Dynamic Arrays, Evaluation and conversion of
Expressions
INTRODUCTION TO DATA STRUCTURES
BASIC TERMINOLOGY
Data: Data are simply values or sets of values that convey no meaning. For example, numbers,
names, marks etc are the data. Consider the two data items “Rama” and 10. The data “Rama”
and 10 does not convey any meaning to the reader.
Information: Information is defined as a collection of data from which conclusions may be
drawn.
“Rama scored 10 marks”. This sentence is an information. Because, it conveys meaning to the
reader.
The instructions given to a person or commands issued to the computer are considered as
information.
Entity: An entity can be defined as a person, place, thing or concept about which data can be
collected and stored. An entity is made up of a number of attributes which represent that entity.
An attribute is the one which describes the facts, details or characteristics of an entity.
For example, if we collect name, usn, phone number, branch of engineering of a particular
student, then student is treated as an entity whereas name, usn, phone number, branch are the
attributes.
Entity set: A collection of entities with similar attributes is an entity set. For example, all the
students in a college represent entity set.
Field:A field is a single elementary unit of information representing an attribute of an entity.
Record: A record is a collection of field values of a given entity.
File: A file is a collection of records of the entities in a given entity set.
Data Structures: The study of how the data is collected and stored in the memory, how
efficiently the data is organized in the memory, how efficiently the data can be retrieved and
manipulated, and the possible ways in which different data items are logically related is called
data structures.
Data Structures can be divided into two categories,
i) Primitive Data Structures
ii) Non-Primitive Data Structures

The data structures that can be manipulated directly by machine instructions are called
primitive data structures. Thus, the primitive data structures are fundamental data types that
are supported by a programming language. These data types consists of characters that cannot
be divided and hence they also called simple data types.
Example: Integers, Floating Point Numbers, Characters and Pointers etc.

The data structures that cannot be manipulated directly by machine instructions are called non-
primitive data structures. Thus, the non-primitive data structures are created or constructed
using primitive data structures. The nonprimitive data structures are also called compound data
structures.Example: Arrays, Lists and Files, Graphs, trees etc.
Based on the structure and arrangement of data, non-primitive data structures is
Further classified into
1. Linear Data Structure
2. Non-linear Data Structure
The data structure where its values or elements are stored in a sequential or linear order is called
linear data structure. The elements can be accessed sequentially one after the other in a linear
order and hence the name. The linear relationship between the elements is maintained:
 • by means of sequential memory locations as in arrays: Here, one or more elements
are stored one after the other sequentially.

• by means of links as in linked list: Here, each element is stored in a node. One or more
nodes are logically adjacent and the logical adjacency is maintained using links. In
linked lists, even though the nodes are not physically adjacent, they seem to be adjacent
logically because of links. The logical adjacency is maintained using pointers.
For example, arrays, stacks, queues, linked lists etc., are all linear data structures.
The data structure where its values or elements are not stored in a sequential or linear order is
called non-linear data structures. Unlike linear data structures, here, the logical adjacency
between the elements is not maintained and hence elements cannot be accessed if we go in
sequential order.
For example, graphs, trees, files are all non-linear data structures.

OPERATION ON DATA STRUCTURES

The commonly used operations on data structures are as follows,
1. Creating: The process of repatedly adding various data items into the list is called
creating a list. For example, we can create a student records consisting of names, marks,
address, phone number etc., by repeatedly adding or inserting data items into the list.
2. Inserting: The process of adding a data item into the list is called inserting. For example,
a student record consisting of name, marks and address can be added whenever a
student joins a course. It is called inserting student record into the list.
3. Deleting: The process of removing a data item from a list is called deleting. For
example, removing a student record from the list whenever the student leaves the course
in the middle.
4. Searching: The process of informing whether a particular item is present in a list or it
is not present in a list is called searching. We can also find a set of elements based on
some criteria.
5. Sorting: The process of arranging various data items either in ascending order or
descending order is called sorting. For example, in a student record consisting of names,
marks, phone number etc., we can arrange student records based on alphabetical order
of names or based on ascending order of marks etc.
6. Merging: Given two sorted lists we can combine those two lists into a single sorted list.
This process is called merging. For example, two sorted arrays can be combined into a
single sorted array. This process is called simple merge.
7. Traversing: The process of accessing each data item exactly once so that it can be
processed and manipulated is called traversal. For example, to print all array elements,
to display all student names in a class, to display each item in a list etc.
REVIEW OF POINTERS AND DYNAMIC MEMORY ALLOCATION
Pointers: Pointers are primitive data structures.
Difference between structure and union:
DYNAMIC MEMORY ALLOCATION
In static memory allocation, the memory space to be allocated for various variables is decided
during compilation time itself, then the memory space cannot be expanded to accommodate
more data or cannot be reduced to accommodate less data.
In Dynamic Memory Allocation, memory-space is allocated during execution-time (or run-
time). Memory-allocation is done on a heap.
• Memory management functions include:
→ malloc (memory allocate)
→ calloc (contiguous memory allocate)
→ realloc (resize memory)
→ free (deallocate memory)
malloc() function:
is used to allocate required amount of memory-space during run-time.
• If memory allocation succeeds, then address of first byte of allocated space is returned. If
memory allocation fails, then NULL is returned.
The syntax is shown below:
 • ptr is a pointer variable of type data_type
• data_type can be any of the basic data type or user defined data type
• size is the number of bytes required
free() function:
is used to deallocate(or free) an area of memory previously allocated by
malloc() or calloc().

Immediately, after the printf (“an integer=%d”,pi); if I write a statement ,

pi=(int *) malloc(sizeof(int)); ,then the pointer to the storage used to hold the value 1024
disappears.Now there is no way to retrieve this storage.This is an example of Dangling
Reference.
If specified size of memory space is not available, the condition is called “overflow of
memory”. In such case, the function returns NULL.

if ptr is NULL appropriate message has to be displayed using the following statement:
if (ptr == NULL)
{
printf(“Insufficient memory\n”);
return;
}
Pointers are Dangerous

• In many computers, the size of int data type and size of pointer is same. So, a valid
integer value can be interpreted as a pointer which is very serious error. For example,
when a function returns an integer value, the returned value can be interpreted as a
pointer. This is very serious error.

ARRAYS AND STRUCTURES

Arrays:
An Array is defined as, an ordered set of similar data items. All the data items of an array are
stored in consecutive memory locations.
• The data items of an array are of same type and each data items can be accessed using the
same name but different index value.
• An array is a set of pairs, such that each index has a value associated with it. It can be
called as corresponding or a mapping ,mathematically.
Ex: <index, value>
< 0 , 25 > list[0]=25
< 1 , 15 > list[1]=15
< 2 , 20 > list[2]=20
< 3 , 17 > list[3]=17
< 4 , 35 > list[4]=35
Here, list is the name of array. By using, list [0] to list [4] the data items in list can be accessed.

Arrays in C:
A one-dimensional array can be declared as follows:
int list[5]; //array of 5 integers
int *plist[5]; //array of 5 pointers to integers

• Address of first element list[0] is called base-address.

• Memory-address of list[i] can be computed by compiler as

Program to print both address of ith element of given array & the value found at that
address:
ptr+i can be replaced by &ptr[i] also.
So, *(ptr+i) is equal to ptr[i].

DYNAMICALLY ALLOCATED ARRAYS :

ONE-DIMENSIONAL ARRAYS
• When writing programs, sometimes we cannot reliably determine how large an array must
be.
• A good solution to this problem is to
→ defer this decision to run-time &
→ allocate the array when we have a good estimate of required array-size
• Dynamic memory allocation can be performed as follows:

The above code would allocate an array of exactly the required size and hence would not result
in any wastage.

TWO DIMENSIONAL ARRAYS

• These are created by using the concept of array of arrays.
• A 2-dimensional array is represented as a 1-dimensional array in which each element is a 1-
dimensional array .(or) it is a 1 dimensional array of pointers where each pointer contain
address of 1-dimensional array.
int a[3][5]; //we create a 1-dimensional array x whose length is 3;
//each element of x is a 1-dimensional array whose length is 5.

• Address of a[i][j] = a[i]+j*sizeof(int)

Program to dynamically create a 2D array:
#include <stdlib.h>
#include<stdio.h>
int main()
{
int rows = 3;
int cols = 4;
// Allocate memory for an array of pointers to int
int** myarray = (int**)malloc(rows * sizeof(int*));
// Allocate memory for each row
for(int i = 0; i < rows; i++)
 {
myarray[i] = (int*)malloc(cols * sizeof(int));
}
// Free the allocated memory
for(int i = 0; i < rows; i++)
{
free(myarray[i]);
}
free(myarray);
return 0;
}

REALLOC
• These functions resize memory previously allocated by either malloc or calloc. For
example,
realloc(p,s); //this changes the size of memory-block pointed at by p to s

• When s< oldSize, the rightmost oldSize-s bytes of old block are freed.
• When s>oldSize, the additional s-oldSize have an unspecified value.
• On successful resizing, it returns a pointer to the start of the new block. On failure, it returns
the value NULL.
• To create clean and readable programs, the REALLOC macro can be created as shown below:

STRUCTURES AND UNIONS

STRUCTURES:
Arrays are collections of data of the same type. In C there is an alternate way of grouping data
that permits the data to vary in type. This mechanism is called the struct, short for structure. A
structure (called a record in many other programming languages) is a collection of data items,
where each item is identified as to its type and name.
Creates a variable whose name is person and that has three fields:
• a name that is a character array
• an integer value representing the age of the person
• a float value representing the salary of the individual

➢ Dot operator(.) is used to access a particular member of the structure.

strcpy(person.name,"james") ;
Person.age=20;
person.salary = 35000;

➢ We can create our own structure data types by using the typedef statement as below:

➢ Variables can be declared as follows:

humanBeing person1,person2;

➢ Structures cannot be directly checked for equality or inequality. So, we can write a function
to do this.
PRG: Function to check equality of structures
int humansequal(humanbeing personl,humanbeing person2)
{ /* being otherwise return FALSE
if (strcmp(personl.name, person2.name)) return FALSE;
if (personl.age != person2.age) return FALSE;
if (personl.salary != person2.salary) return FALSE;
return TRUE;
return TRUE if personl and person2 are the same human
*/
}
if (humansequal(personl,person2))
 printf("The two human beings are the same\n");
else
printf{"The two human beings are not the same\n");

➢ We can embed a structure within a structure.

typedef struct {
int month;
int day;
int year; } date;
typedef struct humanbeing {
char name[10];
int age;
float salary;
date dob;
};
humanbeing person1;
➢ A person born on February 11, 1944, would have the values for the date struct set as:

personl.dob.month = 2;
personl.dob.day = 11;
personl.dob.year = 1944;
Unions

➢ This is similar to a structure, but the fields of a union must share their memory space. This
means that only one field of the union is "active" at any given time.
typedef struct sextype {
enum tagfield {female, male
} sex;
union {
int children;
int beard ;
} u;
};
typedef struct humanbeing {
char name[10];
int age;
float salary;
date dob;
sextype sexinfo;
};
humanbeing personl, person2;
➢ We could assign values to person1 and person2 as:

personl.sexinfo.sex = male;
personl.sexinfo.u.beard = FALSE;
and
person2.sexinfo.sex = female;
person2.sexinfo.u.children - 4;
➢ we first place a value in the tag field. This allows us to determine which field in the union
is active. We then place a value in the appropriate field of the union.
Internal Implementation Of Structures
• The size of an object of a struct or union type is the amount of storage necessary to represent
the largest component, including any padding that may be required.
• Structures must begin and end on the same type of memory boundary, for example, an even
byte boundary or an address that is a multiple of 4, 8, or 16.
Self-Referential Structures
• A self-referential structure is one in which one or more of its components is a pointer to itself.
• These require dynamic storage management routines (malloc & free) to explicitly obtain and
release memory.
typedef struct list
{
char data;
list *link; //link is a pointer to a list structure
};
• Consider three structures and values assigned to their respective fields:
list item1,item2,item3;
item1.data='a';
item2.data='b';
item3.data='c';
item1.link=item2.link=item3.link=NULL;
• We can attach these structures together as follows
item1.link=&item2;
item2.link=&item3;

POLYNOMIALS
Definition: A polynomial is a mathematical expression consisting of sum of terms
where each term is made up of a coefficient multiplied by a variables raised to a
power.
Ex: A polynomial consisting of only one variable is shown below:
x4+ 10 x3+ 3x2+ 1
 Each term consists of a co-efficient multiplied by a variable raised to a power. So, each term
can be represented by a structure consisting of 2 fields namely:coefficient and exponent.
To represent the polynomial 2x3+8x2+5

A[0]

A[1]

A[2]

Short program to read the polynomial

Int A[10][2],n,i;
printf(“Enter the no: of terms in the polynomial”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“Enter the coefficient and exponent of %d term”,i);
scanf(“%d%d”,&a[i][0],&a[i][1]);
}
To add 2 polynomials :
Steps:
1. Initialize indices i, j, k to traverse arrays a, b, and c respectively.
2. Use a while loop to merge and add terms from arrays a and b into array c:

• If exponents of current terms from a and b are equal, add their coefficients into c.
• If exponent of term in a is greater, copy term from a to c.
• If exponent of term in b is greater, copy term from b to c.
• Increment indices accordingly.

3 After merging, if there are any remaining terms in either a or b, copy them directly into
c.

Program:

i = 0; // Initialize index for array 'a'

j = 0; // Initialize index for array 'b'

k = 0; // Initialize index for array 'c'

// Merge and add polynomials A and B into C

while (i < m && j < n) {

// Check if exponents of current terms from A and B are equal

if (a[i][1] == b[j][1]) {

// If equal, add coefficients and keep exponent

 c[k][0] = a[i][0] + b[j][0]; // Add coefficients of A and B

c[k][1] = a[i][1]; // Keep the exponent (common)

i++; // Move to next term in A

j++; // Move to next term in B

k++; // Move to next position in C

} else if (a[i][1] > b[j][1]) {

// If exponent of term in A is greater than B

c[k][0] = a[i][0]; // Copy term from A's coefficient

c[k][1] = a[i][1]; // Copy term from A's exponent

k++; // Move to next position in C

i++; // Move to next term in A

} else {

// If exponent of term in B is greater than A

c[k][0] = b[j][0]; // Copy term from B's coefficient

c[k][1] = b[j][1]; // Copy term from B's exponent

k++; // Move to next position in C

j++; // Move to next term in B

// Copy remaining terms from polynomial A

while (i < m) {

c[k][0] = a[i][0]; // Copy remaining term from A's coefficient

c[k][1] = a[i][1]; // Copy remaining term from A's exponent

k++; // Move to next position in C

i++; // Move to next term in A

}

// Copy remaining terms from polynomial B

while (j < n) {

c[k][0] = b[j][0]; // Copy remaining term from B's coefficient

c[k][1] = b[j][1]; // Copy remaining term from B's exponent

k++; // Move to next position in C

j++; // Move to next term in B

// Print the result after addition of polynomials

printf("After addition:\n");

for (i = 0; i < k; i++) {

for (j = 0; j < 2; j++) {

printf("%d", c[i][j]); // Print each coefficient and exponent pair

printf("\n"); // Move to the next line after printing each term

Let m and n be the number of non-zero terms in A and B respectively.The asymptotic

computing time of this algorithm is O(n+m)

SPARSE MATRICES

A sparse matrix is a matrix that has very few non-zero elements spread out thinly.
Conversely, a matrix which has more number of zero elements (or high proportion of zeros
elements is called sparse matrix. The sparse matrix can be single dimensional or
multidimensional such as 2-dimensional, 3-dimensional and so on.
 In the first matrix, 10 non-zero elements are present and 2 zero elements. The

number of non-zero elements are more than the number of zero elements. So, it is

not a sparse matrix.

In the second matrix only 8 non-zero elements are present and 12 zero elements

are present. So, the number of non-zero elements are less than the number of zero

elements. So, it is a sparse matrix.

Disadvantage of a sparse matrix

The sparse matrix contains many zeroes. If we are manipulating only non-zero values, then
we are wasting the memory space by storing unnecessary zero values. This disadvantage can
be overcome by storing only non-zero values thus saving the space.
Sparse Matrix Representation:
We know that any element in the matrix can be uniquely defined using the triples
<row, col, val>. Thus, a sparse matrix can be created using the array of triples as
shown below:
#define MAX_TERMS 101 /* Maximum number of terms */
typdef struct
{
int row;
int col;
int val;
} TERM;
/* 1- dimensional array representing array of triples <row, col, val> */
TERM a[MAX_TERMS];
How do you represent the following spare matrix using triples in a single dimensional array?

The non-zero elements in the above matrix along with row and col position can be
represented using a single dimensional array starting from a[1] as shown below:
Transpose of a matrix
A matrix which is obtained by changing row elements into column elements and column
elements into row elements is called transpose of a matrix.

Initially, the size of the matrix must be reversed. This can be done by interchanging rows and
columns as shown below:
b[0].row = a[0].col
b[0].col = a[0].row
b[0].val = a[0].val
We find the transpose of given matrix by accessing col index of each non-zero element in array
a and store in array b as shown below:
b[k].row = a[j].col // make column as row
b[k].col = a[j].row // make row as column
b[k].val = a[j].val
k++; // to add the next entry
To obtain the index j, we start searching for 0th column, 1st column, 2nd column, 3rdcolumn
and 4th column from a[1].col to a[8].col. The corresponding code can be written as shown
below:

The index value i = 0, 1, 2,3 can be written as i = 0 to 3

i = 0 to 4 – 1
i = 0 to a[0].col – 1
Now, the above code can be translated into C as shown below:
Representation of multidimensional arrays
Arrays with one set of square brackets [] are single dimensional arrays. Arrays with two sets of
square brackets [][] are called 2-dimensional arrays and so on. Arrays with two or more
dimensions are called multi-dimensional arrays.
int a[10]; /* a is declared as single dimensional array */
int b[10][10]; /* b is declared as two dimensional array */
int c[3][4][5]; /* c is declared as three dimensional array */
Declaring and initializing two dimensional arrays:
For example, consider the following declaration
int a[3][4];
The array a has two sets of square brackets [][] and hence it is a 2-dimensional array with 3
rows and 4 columns. This declaration informs the compiler to reserve 12 locations (3 * 4 = 12)
contiguously one after the other. The pictorial representation of this array a is shown below:
int a[4][3] = {
{11, 22, 33},
{44, 55, 66},
{77, 88, 99},
{10, 11, 12}
};
The declaration indicates that array a has 4 rows and 3 columns. The pictorial
representation of this 2-dimensional array is shown below:

Storage representation of 2-dimensional arrays

The elements in a 2-dimensional array can be stored using:

• Row major order

• Column major order
Row Major Order
For example, consider the following 2-dimensional matrix:
int a[4][3] = {
{11, 22, 33},
{43, 55, 66},
{77, 88, 99},
};
Assume that address of first byte of a (usually called base address) is 2000 and size of integer
is 2 bytes. The above matrix can be stored in memory using row-major order as shown below:

Coloumn Major Order

In column major order, the elements are stored column by column one column at a time. For
example, consider the following 2-dimensional matrix

Storage representation of 2-dimensional arrays (Row-major order):

Let us take the following array declaration in Pascal language:
a : array[3..5, 4..7] of integer; // size of array is 3 x 4
The pictorial representation of above array can be written as shown below:

In the above matrix representation observe that:

There are three rows ranging from 3 to 5 and so lower bound and upper bound for rows is given
by lb1 = 3 and ub1= 5
There are four columns ranging from 4 to 7 and so lower bound and upper bound for columns
is given by lb2 = 4 and ub2 = 7
The location of a[i][j] is given by:
Loc A[i][j] = base address(a) + w * (ub2 – lb2 + 1) * (i – lb1) + w * ( j – lb2)
w=size of the datatype
Example: Consider the array declaration in Pascal language:
a : array[2..4, 3..6] of integer; // size of array is 3 x 4
Find the location a[3][5] when elements are stored in row-major order. The 2-dimensional array
elements stored using row major order assuming base address = 3000
Loc A[i][j] = base address + (ub2 – lb2 + 1) * w * (i – lb1) + w * (j – lb2)
Loc a[3][5] = 3000 + ( 6 – 3 + 1) * 2 * (3 – 2) + 2 * (5 – 3)
Loc a[3][5] = 3012
Storage representation of 2-dimensional arrays (column-major order)
Loc A[i][j] = base address(a) + w * (ub1 – lb1 + 1) * (j – lb2) + w * ( i – lb1)
Consider the array declaration in Pascal language:
a : array[2..4, 3..6] of integer; // size of array is 3 x 4
Find the location a[3][5] when elements are stored in column-major order.Base address is 3000.
Loc A[i][j] = base address(a) + w * (ub1 – lb1 + 1) * (j – lb2) + w * ( i – lb1)
Loc A[3][5]= 3000 + 2 * ( 4 – 2 + 1) * (5 – 3) + 2 * ( 3 – 2)
= 3000 + 12 + 2
= 3014
STRINGS
The string abstract Datatype:
The string, whose component elements are characters. As an ADT, we define a string to have
the form, S = So, .. .Sn-1, where Si are characters taken from the character set of the
programming language. If n = 0, then S is an empty or null string. We represent strings as
character arrays terminated with the null character \0.

Some string functions:

 1) strlen(str) – String Length
Syntax: It is defined in header file “string.h”. The syntax to use strlen() is shown below:
int strlen (char str[]);
This function returns the length of the string str i.e., it counts all the characters up to ‘\0’ except
‘\0’. So, an empty string has length zero.
Function returning the string length:
int my_strlen(char str[])
{
int i = 0;
while (str[i] != ‘\0’) i++;
return i;
}
To start with, the index variable i is zero. Now, keep incrementing value of index variable i as
long as str[i] is not equal to ‘\0’. Once control comes out the loop, the index variable i gives
the length of the string.
2) strcpy(dest, src) – string copy
It is defined in header file “string.h”. The syntax to use strcpy() is shown below:
strcpy (char dest[], char src[]);
The function strpcy copies the contents of source string src to destination string dest including
‘\0’. So, the size of destination string dest should be greater or equal to the size of source string
src. After copying, the original contents of destination string dest are lost.
Function to copy string src to string dest is shown below:
void my_strcpy(char dest[], char src[])
{
int i = 0;
while (src[i] != ‘\0’) /* Copy the string till we get NULL character */
{
dest[i] = src[i];
i++;
}
dest[i] = ‘\0’; /* Attach null character at the end */
}
3) strcat(s1, s2) – string concatenate
It is defined in “string.h” as: strcat (char s1[], char s2[]);
where

• s1 is the first string

• s2 is the second string
The function copies all the characters of string s2 to the end of string s1.The delimiter of string
s1 is replaced by the first character of s2. Only condition is that the size of s1 should be
sufficiently large enough to store a string whose length is s1 + s2.
Given two strings s1 and s2 perform the following activities:

• Obtain the position of the null character of str1. This can be done using the following
statements:
i = 0;
while (str1[i] != ‘\0’) i++;

• Copy the second string to the end of the first string

j = 0;
while ( str2[j] != '\0')
{
str1[i++] = str2[j++];
}

• Attach null character at the end using the statements:

str1[i++] = ‘\0’;
So, the complete C function to implement my_strcat is below:
void my_strcat(char str1[], char str2[])
{
 int i, j;
i = 0;
/* obtain position of null character of str1 */
while (str1[i] != ‘\0’) i++;
/* Copy second string to destination string */
j = 0;
while ( str2[j] != '\0')
{
str1[i++] = str2[j++];
}
str1[i++] = ‘\0’; // attach ‘\0’
}
4) strcmp(s1, s2) – string compare
This function is used to compare two strings. The comparison starts with
first character of each string. The comparison continues till the corresponding
characters differ or until the end of the character is reached. The following values are
returned after comparison:

• If the two strings are equal, the function returns 0

• If s1 is greater than s2, a positive value is returned
• If s1 is less than s2, the function returns a negative value.
int my_strcmp(char s1[], char s2[])
{
int i;
i = 0;
while (s1[i] == s2[i]) /* As long as two strings are equal */
{
if (s1[i] == ‘\0’) break; /* Check if end of string */
i++; /* Point to next character of each string */
}
return s1[i] – s2[i]; /* Return the difference between chars */
 }
The above function returns one of the following values:

• zero if s1 = s2
• positive if s1 > s2
• negative if s1 < s2
5) strrev(str) – string reverse
we see the built in function strrev() and we write one user defined function without using any
of the built-in functions. It is defined in “string.h”.
Syntax:
void strrev (char str[])
This function reverses all characters in the string str except the terminating
NULLcharacter ‘\0’. The original string is lost.
C function that shows implementation of strrev()
void my_strrev (char src[], char dest[])
{
int i; /* Used as index to read characters from src */
int n; /* Holds the string length */
n = strlen(src); /* Compute the length of the string */
for (i = 0; i < n; i++) /* Reverse the given string */
{
dest[n-1-i] = src[i];
}
dest[n] = ‘\0’; /* NULL terminate the string */
}
Pattern matching algorithms
Given a string called pattern p with n characters and another string called text with m characters
where n <= m. It is required to search for the pattern string p in the text string t. If search is
successful return the position of the first occurrence of pattern string p in the text string t.
Otherwise, return -1. This process of searching for a pattern string in a given text string is called
pattern matching.
The easiest way to determine if pat is in string is to use the built-in function strstr.
The call (t = strstr(string,pat)) returns a null pointer if pat is not in string.
If pat is in string, t holds a pointer to the start of pat in string. The entire string beginning at
position t is printed out.
Although strstr seems ideally suited to pattern matching, there are two reasons why we may
want to develop our own pattern matching function:
• The function strstr is new to ANSI C. Therefore, it may not be available with the Compiler
we are using.
• There are several different methods for implementing a pattern matching function. The easiest
but least efficient method sequentially examines each character of the string until it finds the
pattern or it reaches the end of the string. If pat is not in string, this method has a computing
time of O(n . m) where n is the length of pat and m is the length of string.
Knuth, Morris, Pratt Pattern Matching algorithm.(KMP Algorithm)
Proper suffix and prefix for the string ABABD

The algorithm for pattern matching using KMP method?” The two steps to be followed using
this technique are:
Step 1: Create a failure function for the pattern to be searched
Step 2: Search for the pattern using the above failure function
Create a failure function for the pattern to be searched:For obtaining the
failure function for the pattern “ABABD”
Step 1: Given the pattern string “ABABD” obtain the proper prefixes and proper
suffixes for the strings “A”, “AB”, “ABA”, “ABAB” and “ABABD”. Refer
columns 1, 2 and 3 in the table in the next page.
Step 2: For every substring in step 1, obtain a longest proper prefix which is same
as the longest proper suffix.
Step 3: Find the length of the longest proper prefix which is same as the longest
proper suffix

Failure function:

Failure function for the pattern string

void failure(int f[], char p[])
{
int i = 0, j = 1;
f[i] = 0;
while ( j < strlen(p))
{
if (p[i] == p[j])
f[j] = i+1, i++, j++;
else if (i == 0)
f[j++] = i;
else
i = f[i-1];
}
}
Pattern match using Knuth, Moris and Pratt method:
int pattern_match(char p[], char t[], int f[])
{
int i = 0, j = 0;
while (i < strlen(t) && j < strlen(p))
{
if (t[i] == p[j])
i++, j++; // compare successive characters
else if (j == 0)
i++; // Move the pattern string towards right by 1
else
j = f[j-1]; // Move the pattern string towards right so that i = j
}
if (j == strlen(p)) // Pattern string found
return i - strlen(p);
else // Pattern string not found
return -1;
}
THE STACK ABSTRACT DATA TYPE
STACK
• This is an ordered-list in which insertions(called push) and deletions(called pop) are made at
one end called the top
• Since last element inserted into a stack is first element removed, a stack is also known as a
LIFO list(Last In First Out).
When an element is inserted in a stack, the concept is called push, and when an element is
removed from the stack, the concept is called pop.
Trying to pop out an empty stack is called underflow and trying to push an element in a full
stack is called overflow.

As shown in above figure, the elements are added in the stack in the order A, B, C, D, E, then
E is the first element that is deleted from the stack and the last element is deleted from stack is
A. Figure illustrates this sequence of operations.
Since the last element inserted into a stack is the first element removed, a stack is also known
as a Last-In-First-Out (LIFO) list.
SYSTEM STACK
A stack used by a program at run-time to process function-calls is called system-stack.
• When functions are invoked, programs
→ create a stack-frame (or activation-record) &
→ place the stack-frame on top of system-stack
• Initially, stack-frame for invoked-function contains only
→ pointer to previous stack-frame &
→ return-address
• The previous stack-frame pointer points to the stack-frame of the invoking-function while
return-address contains the location of the statement to be executed after the function
terminates.
• If one function invokes another function, local variables and parameters of the invoking
function are added to its stack-frame.
• A new stack-frame is then
→ created for the invoked-function &
→ placed on top of the system-stack
• When this function terminates, its stack-frame is removed (and processing of the
invokingfunction, which is again on top of the stack, continues).
• Frame-pointer(fp) is a pointer to the current stack-frame.

ARRAY REPRESENTATION OF STACKS

• Stacks may be represented in the computer in various ways such as one-way
linked list (Singly linked list) or linear array.
• Stacks are maintained by the two variables such as TOP and MAX_STACK_SIZE.
• TOP which contains the location of the top element in the stack. If TOP= -1,
then it indicates stack is empty.
• MAX_STACK_SIZE which gives maximum number of elements that can be
stored in stack.
Stack can represented using linear array as shown below

Stack ADT
• The following operations make a stack an ADT. For simplicity, assume the data is an integer
type.
• Main stack operations
– Push (int data): Inserts data onto stack.
– int Pop(): Removes and returns the last inserted element from the stack.
• Auxiliary stack operations
– int Top(): Returns the last inserted element without removing it.
– int Size(): Returns the number of elements stored in the stack.
– int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.
– int IsFullStack(): Indicates whether the stack is full or not.
• The easiest way to implement this ADT is by using a one-dimensional array, say, stack [MAX-
STACK-SIZE], where MAX STACK SIZE is the maximum number of entries.
• The first, or bottom, element of the stack is stored in stack[0], the second in stack[1] and the
ith in stack [i-1].
• Associated with the array is a variable, top, which points to the top element in the stack.
Initially, top is set to -1 to denote an empty stack.
• we have specified that element is a structure that consists of only a key field
1. CREATE STACK:

The element which is used to insert or delete is specified as a structure that consists of
only a key field.
1. Boolean IsEmpty(Stack)::= top < 0;
2. Boolean IsFull(Stack)::= top >= MAX_STACK_SIZE-1;
The IsEmpty and IsFull operations are simple, and is implemented directly in the
program push and pop functions. Each of these functions assumes that the variables
stack and top are global.
Insert an item into stack(Push operation)
C function to insert an integer item (by passing parameters)

Delete an item in a stack(Pop Operation)

C function to delete an integer item (by passing parameters)
STACK USING DYNAMIC ARRAYS
• Shortcoming of static stack implementation: is the need to know at compile-time, a good
bound(MAX_STACK_SIZE) on how large the stack will become.
• This shortcoming can be overcome by
→ using a dynamically allocated array for the elements &
→ then increasing the size of the array as needed
• Initially, capacity=1 where capacity=maximum no. of stack-elements that may be stored in
array.
• The CreateS() function can be implemented as follows
typedef struct
{
int key;
/* other fields */
} element;
element *stack;
malloc(stack,sizeof(*stack));
int capacity=1;
int top = -1;
Boolean IsEmpty(Stack) ::= top <0;
Boolean IsFulI(Stack) ::= top >= capacity-1;
• Once the stack is full, realloc() function is used to increase the size of array.
• In array-doubling, we double array-capacity whenever it becomes necessary to increase the
capacity of an array.
ANALYSIS
• In worst case, the realloc function needs to
→ allocate 2*capacity*sizeof(*stack) bytes of memory and
→ copy capacity*sizeof(*stack) bytes of memory from the old array into the new one.
• The total time spent over all array doublings = O(2k ) where capacity=2k
• Since the total number of pushes is more than 2k-1 , the total time spend in array doubling is
O(n) where n=total number of pushes.
Evaluation Of Expressions
Expressions:It is sequence of operators and operands that reduces to a single value after
evaluation is called an expression.
X=a/b–c+d*e–a*c
In above expression contains operators (+, –, /, *) operands (a, b, c, d, e).
Expression can be represented in in different format such as
• Prefix Expression or Polish notation
• Infix Expression
• Postfix Expression or Reverse Polish notation

Infix Expression: In this expression, the binary operator is placed in-between the operand. The
expression can be parenthesized or un- parenthesized.
Example: A + B
Here, A & B are operands and + is operand
Prefix or Polish Expression: In this expression, the operator appears before its operand.
Example: + A B
Here, A & B are operands and + is operand
Postfix or Reverse Polish Expression: In this expression, the operator appears after its
operand.
Example: A B +
Here, A & B are operands and + is operand
Precedence of the operators
The rules that determine the order in which different operators are evaluated are called
precedence rules or precedence of operators.
Highest precedence operators will have the highest value and lowest precedence operators will
have the least value. The table below shows arithmetic operators along with priority values.

The symbol ‘$’ or ‘^’ is considered as the operator to perform exponentiation and should be
given first precedence since it has higher priority value. The addition or subtraction is given
the least precedence since it has least priority value as shown in above table.
During evaluation, if two or more operators have the same precedence, then precedence rules
are not applicable. Instead, we go for associativity of the operators. The order in which the
operators with same precedence are evaluated in an expression is called associativity of the
operator. In such case, precedence rules are not considered.
In an expression, if two or more operators have the same priority and are evaluated from left-
to-right, then the operators are called left associative operators. The process of evaluating from
left to right is called left associativity.eg. The operator “+” is left associative.
In an expression, if two or more operators have the same priority and if they are evaluated from
right-to-left, then the operators are called right associative
Operators.Eg. the operator “$” is right-to-left associative (also called right associative).
Conversion from infix to postfix
1. Obtain the postfix expression for ( ( A + ( B – C ) * D ) ^ E + F )
2. Obtain the postfix expression for X ^ Y ^ Z – M + N + P / Q
To convert a given infix expression to its equivalent postfix expression
PROGRAM:
#include <ctype.h>
#include <stdio.h>
#define SIZE 50 /* Size of Stack */
char s[SIZE]; /* Global declarations */
int top = -1;
push(char elem) /* Function for PUSH operation */
{
s[++top] = elem;
}
char pop() /* Function for POP operation */
{
return (s[top--]);
}
int pr(char elem) /* Function for precedence */
{
switch (elem)
{
case '#': return 0;
case '(': return 1;
case '+':
case '-': return 2;
case '*':
case '/':
case '%': return 3;
case '^': return 4;
}
}
void main() /* Main Program */
{
char infx[50], pofx[50], ch, elem;
int i = 0, k = 0;
printf("\n\n Enter the Infix Expression : ");
scanf(“%s”,infx);
push('#');
while ((ch = infx[i++]) != '\0')
{
if (ch == '(')
push(ch);
else if (isalnum(ch))
pofx[k++] = ch;
else if (ch == ')')
{
while (s[top] != '(')
pofx[k++] = pop();
elem = pop(); /* Remove ( */
}
else /* Operator */
{
while (pr(s[top]) >= pr(ch))
pofx[k++] = pop();
push(ch);
}
}
while (s[top] != '#') /* Pop from stack till empty */
pofx[k++] = pop();
pofx[k] = '\0'; /* Make pofx as valid string */
printf("\n\n Given Infix Expn is: %s\n The Postfix Expn is: %s\n", infx, pofx);
}
Evaluation of Postfix expression
The evaluation of infix expression is not recommended because of the following reasons:

• Evaluation of infix expression requires the knowledge of precedence of operators and

the associativity of operators.
• The problem becomes complex, if there are parentheses in the expression because they
change the order of precedence.
• During evaluation, we may have to scan from left to right and right to left repeatedly
thereby complexity of the program increases.
The postfix expression can be evaluated using the following procedure:

• Scan the symbol from left to right

• If the scanned symbol is an operand, push it on to the stack
• If the scanned symbol is an operator, pop two elements from the stack. The first popped
element is operand2 and the second popped element is operand1.
This can be achieved using the statements
op2 = s[top--]; /* First popped element is operand2 */
op1 = s[top--]; /* Second popped element is operand1 */

• Perform the indicated operation

res = op1 op op2 /* op is an operator such +, -, /, * etc. */
 • Push the result on to the stack.
• Repeat the above procedure till the end of input is encountered.
C program to evaluate the postfix expression
#include <stdio.h>
#include <math.h>
#include <string.h>
/* Function to evaluate */
double compute(char symbol, double op1, double op2)
{
switch(symbol)
{
case '+': return op1 + op2; /* Perform addition operation */
case '-': return op1 - op2; /* Perform subtraction operation */
case '*': return op1 * op2; /* Multiply two operands */
case '/': return op1 / op2; /* Perform division */
case '$':
case '^': return pow(op1, op2); /* Compute power */
}
}
void main()
{
double s[20]; /* Place for stack elements */
double res; /* Holds the result of partial or final result */
double op1; /* First operand */
double op2; /* Second operand */
int top; /* Points to the topmost element */
int i; /* Index to obtain each symbol from the postfix */
char postfix[20]; /* Valid input expression */
char symbol; /* Scanned symbol of postfix */
printf("Enter the postfix expression\n");
scanf("%s",postfix);
top = -1; /* Stack is empty */
for(i = 0; i < strlen(postfix); i++)
{
symbol = postfix[i]; /* Obtain the next character */
if ( isdigit(symbol) ) /* If operand insert into the stack */
s[++top] = symbol –’0’;
else
{
op2 = s[top--]; /* Obtain second operand from stack */
op1 = s[top--]; /* Obtain first operand from stack */
/* Perform the specified operation */
res = compute(symbol, op1, op2);
s[++top] = res; /* Push the partial result on the stack */
}
}
res = s[top--]; /* Obtain result from the stack */
printf("The result is %f\n",res);
}
Give the tracing to evaluate the following postfix expression
1. A B C – D * + E $ F +
corresponding to the infix expression ( ( A + ( B – C ) * D ) $ E + F ) with following values
assigned: A = 6, B = 3, C= 2, D = 5, E = 1, F = 7
SOLN:
After substituting the given values, the resulting postfix expression is:
632–5*+1$7+
2. Apply the evaluation algorithm and trace for the valid postfix
expression
AB C +* C BA- +*
for given value A = 1, B = 2, C = 3 .
SOLN:
Substituting the values for the variables we have the following postfix
expression:
123+*321-+*
3. Apply the evaluation algorithm discussed in section 6.3.13 and trace
for the valid postfix expression
AB +C – BA+C $ -
for given value A = 1, B = 2, C = 3 .
SOLN:
Substituting the values for the variables we have the following postfix
expression:
12+3–21+3$