Data structures using C

Chapter 1: Introduction to Data Structure

Computer is an electronic device, which takes the information from user, process it and
gives desired output. In this information is obtained from data, which is known fact.
Information is a processed data, which gives a desired meaning.
Data means known facts, figures or statistics, which is used to manipulation and
calculation purpose. In data there are two types i.e Numeric and Non numeric.

Numeric data means integer and floating point numbers. (Eg:123,-12,12.3, -0.25 etc)
Non-Numeric means characters and Strings (Eg: ‘a’, ‘x’,‘ RAMESH’, ‘SAVTITA’ etc)
While storing these types of data into computer memory, we have to store these data in some
particular order. So we maintain the structure of data, i.e organize the data in a particular
manner.

Definition:

 A data structure in computer science is a way of storing data in a computer so that it

can be used efficiently. It is an organization of mathematical and logical concepts of
data.
 A data structure is a representation of logical relationship among data elements.
 A data structure is the way of organizing the data in particular manner

Examples: Stack, Queue, Tree, Linked List, Array, Pointers etc.

Data structure mainly deals with the following things.

 Organization of data
 Accessing various operations and methods
 Data can be stored in the memory efficiently
 Different data items are logically related.

Data structures are implemented by a programming language as data types and operations
they provide.

Program = Algorithm + Data structure.

In this algorithm is technique of solving the problem step by step by carrying out certain task.
And data structure is the way of organizing the data in particular manner.

To develop a program of algorithm we should select an appropriate data structure for that
algorithm. Therefore algorithm and its associated data structures for a program.

1
 Data structures using C
Classification of Data structure.
The data structure normally classified as shown in below.

Data Structure

Primitive Non Primitive

Integer

Linear Non-linear
Floating point

Arrays Tree
Character

Stack Graphs
Double

Queue
Pointer

Linked List

 Primitive Data structure :- These are basic data types , which directly manipulated
by the machine instructions. Eg: Integer,floating point numbers, character, string,
pointers etc.

 Non-primitive Data structure:- These are derived from primitive data structures,
which can not be manipulated directly by machine instructions. Eg: Arrays, stack,
queues, linked list, files etc.
In non-primitive data structure again there are two types

1. Linear Data structure :- In this only one successor and one predecessor, i.e
it shows the relationship of logical adjacency between the elements. Eg:
Stack, Queue, Array etc.
2. Non-linear Data structure :- In this only one predecessor but more than one
successors. Eg: Trees and Graphs.

2
 Data structures using C
Operations on Data structure
The design of an efficient data structure must take operations to be performed on the data
structure for manipulation. Operations on data structure are
 Creating : Create means reserving memory for program elements
 Inserting : Inserting a data element into data structure..
 Deleting : Deleting a data element from data structure.
 Selecting : Accessing the data element within a data structure.
 Updating : Modify the content of data structure.
 Sorting : Arranging the all data elements in a data structure.
 Searching: : Finding the particular element from data structure.
 Merging : Combining the data element of two different list.

3
 Data structures using C

Chapter 2: Dynamic Memory Allocation and Pointers

Pointer :- Pointer is one of the most important feature in C language. It is a special data
type which is derived from basic data types(int, float, char, double).

Definition :- Pointer is an variable which holds the address of another variable. It holds only
address i.e pointer values.

Declaration :
Data type * pointer_variable;
Example: int *p; // Here p is an pointer variable of int type.
float *x; // Here x is an variable of float type.
Initialization :
Pointer_variable = & variable_name;
Example: int a=10; // Here a is normal variable
int *p; // Here p is pointer variable
p=&a; // Here p holds address of a

Variable_name a Pointer_variable p 6547

10
Address (&) 6547 Address (&) 5434

Pointer operators
There are two operators are used in pointers
1) *  Indirection operator
2) &  Address operator
Indirection operator gives the value of the address.
Address operator gives the address of the variable.

Simple Programs
//Ex 1: Program to add two Integer numbers by using pointer
#include<stdio.h>
void main( )
{
int a,b,c;
int *p,*q;
a=10;
b=20;
p=&a;
q=&b;
c=*p+*q;
printf(“Result = %d”,c);
}

4
 Data structures using C
//Ex 2: Program to swap to numbers using pointers
#include<stdio.h>
void main( )
{
int a,b,tmp;
int *p,*q;
a=10;
b=20;
p=&a;
q=&b;
tmp=*p;
*p=*q;
*q=tmp;
printf(“After swapping\n”);
printf(“a= %d and b= %d”,*p,*q);
}

Pointers and Functions.

Function means large programs are divided into several parts is called module or sub
program. Function is a group of instructions to perform well defined task.
In Function we are using three important factors.
 Function Declarations. Or Function Prototyping
 Function Call.
 Function Definition.

Function declaration means before using calling a function we must declare it. That is
function name, number of argument we are passing, their type and return type.
Eg: int fact(int);
Function call means we are calling the function with function name and passing the
arguments.
Function Definition means actual code to perform into that function.

In calling function, we are passing the parameters. There are two types while passing the
parameters into the function.
1. Call by Value.
2. Call by Reference.

In Call by Value we are passing the values of some variables to the calling function, these
variables are called actual parameters. In function definition we are declaring the
variables, these variables are called formal parameters. The values of actual parameters
are copied into formal parameters. If we made any changes in formal parameters, then
there is no effect on actual parameters.

5
 Data structures using C

//Example: Swap two numbers using call by value.

#include<stdio.h> void swap(int x, int y) // formal parameters

void swap(int,int); {
void main( ) int temp;
{ temp=x;
int a=10, b=20; x=y;
printf(“Before swapping\n”); y=temp;
printf(“a= %d b=%d”,a,b); }
swap(a,b); // actual parameters Output:
printf(“After swapping\n”); Before swapping
printf(“a= %d b=%d”,a,b); a=10 b=20
} After swapping
a=10 b=20

In Call by Reference we are passing the address of some variables to the calling function,
these variables are called actual parameters. In function definition we are declaring the
variables, these variables are called formal parameters. The addresses of actual
parameters are copied into formal parameters. If we made any changes in formal
parameters, then it effects on actual parameters.

//Example: Swap two numbers using call by Reference.

#include<stdio.h> void swap(int *x, int *y) // formal parameters

void swap(int *x, int *y); {
void main( ) int temp;
{ temp=*x;
int a=10, b=20; *x=*y;
printf(“Before swapping\n”); *y=temp;
printf(“a= %d b=%d”,a,b); }
swap(&a, &b); // actual parameters Output:
printf(“After swapping\n”); Before swapping
printf(“a= %d b=%d”,a,b); a=10 b=20
} After swapping
a=20 b=10

Advantages of Pointers

 Allocate the memory dynamically

 Return more than one value from function
 Data accessing is much faster than compared to array.

6
 Data structures using C

Memory allocation functions

Memory can be reserved for the variables either during compile time or run time.
Memory can be allocated for variables in two ways.
1. Static Memory Allocation
2. Dynamic Memory Allocation.

Static memory allocation

In compile time only allocating the memory for various variable. So in this we can not
alter the size of memory for that variable in execution time (run time). So it is called Static
memory location.
Ex: int a[10];
In this a is an variable which is having 10 elements and all are integer. It allocates 10
memory for variable a. So we can not increase or decrease the size of this variable.

Dynamic memory location.

In this type of memory allocation, memory is allocating during the run time or program
execution time. This is called as dynamic memory allocation. In this we can increase or
decrease the size of memory location in run time. In run time where memory is allocated
only when it is required. Hence in this case the memory to be allocated is not known earlier.

C language provides the following functions for allocating and deallocating the memory,
1. malloc( )
2, calloc( )
3. realloc( )
4. free ( )

1. malloc ( ) :- This function allocates a block of memory. That is it allocates a memory

block of required size in bytes and returns a pointer to the first bytes of the allocated
memory block.
Syntax : malloc( size ) ;
Here size indicates the size of memory in bytes. That is the numbers of contiguous
memory locations to be allocated.
Suppose we want to assign a particular pointer then
ptr_var=(type_cast *) malloc(size);
Ex:- ptr=(int *)malloc(20 * sizeof(int));
A memory block of 40 bytes is reserved and first address of the byte of this memory
block is assigned to the pointer ptr. Ptr is type of int.
// Example: Program to find maximum element from the list. Using malloc function
#include<stdio.h>
void main( )
{
int *p;
int i , n, max=0;
printf(“Enter the number of element “);
7
 Data structures using C
scanf(“%d”,&n);
p=(int *)malloc(n * sizeof(int));
printf(“Enter the elements one by one”);
for(i=0;i<n;i++)
scanf(“%d”,p+i);
for(i=0; i<n; i++)
{
if(max < *(p+i))
max=*(p+i);
}
Printf(“Maximum element = %d”, max);
}

2. calloc():- This function is used to allocate multiple blocks of memory.In this calloc
means contiguous allocation of multiple memory blocks. It is very useful in arrays
and structures.
Syntax :
calloc(n, size);
Ex: ptr=(int *) calloc(5, sizeof(int));
In this calloc function allocates 5 blocks of 2 bytes each.
3. realloc( ):- This function is used to modify the size of already allocated memory
space. Sometimes the allocated memory may not be sufficient and it may require
additional memory space or suppose we want to reduce the size of allocated memory.
For this we are using realloc function.
Syntax :
realloc(ptr,size);
Ex: ptr=(int *) realloc(ptr,3*sizeof(int));
4. free( ):- This function is used to deallocate the memory which is already allocated.

Syntax :
free(ptr);

Difference between Static and Dynamic memory allocation.

Static memory allocation Dynamic memory allocation

1. Memory is allocated during compile 1. Memory is allocated during run time
time
2. In this we can not increase or decrease 2. In this we can increase or decrease the
the size of memory allocation in run time size of memory allocation in run time as
and when required.
3. Execution is faster, since memory is 3.Execution is slower, since memory has to
already allocated. be allocated during run time.
4. Memory is allocated either in stack area 4. Memory is allocated only in heap area.
5. Ex: arrays 5. Ex: Linked list.

8
 Data structures using C

Difference between malloc function and calloc function.

malloc calloc
1.Allocates single block of memory 1.Allocates multiple blocks of memory
2. Allocated space will not be initialized 2. Each bype of allocated space is
initialized to zero
3.Syntax : malloc(size); 3. Syntax: calloc(n,size);
4. More efficiency 4. Less efficiency
5. Memory is not allocated contiguously 5. Memory is allocated contiguously

9
 Data structures using C
Chapter 3: Files

Definition : - A file is a collection of logically related information, which is stored on

secondary storage medium such as magnetic tape, or magnetic disk.
Example: A Student file contains RollNo, Name, Class, Date _of_Birth, address etc.
Differentiate between File and Array
File Array
1. Stored in and accessed from secondary 1. Stored in and accessed from main memory
memory
2. It is a collection of Hetrogeneous elements 2. It is collection of Homogeneous elements
3.The size of a file may grow or shrink 3. The size of an array is fixed.
4. Declaration: FILE *file_pointer_variable 4. Declaration: datatype arrayname[size]

Basic File operations

1. Creating a file (Declaration)
2. Opening a file
3. Reading a file
4. Writing a file
5. Closing a file

Declaration :
FILE *file_pointer;
Here FILE is a keyword and it is one type of datatype. It should be written in uppercase.
File_pointer:- is an variable which holds the starting address of the file being accessed.
Example:
FILE *infile;
Here infile is file_pointer variable.of type FILE. With the help of file_pointer variable we can
transfer the data from one memory location to another memory location.

Type of files
There are two type in file.
1. Sequential File.
2. Random Access file or Direct File
1. Sequential File:-
In this type of file all records are arranged in particular order. That is records are
stored in consecutive memory location. So we can insert or delete a records sequentially. For
searching record , we start from first to last records until the desired record is found.
Magnetic tape is used to store the records.

10
 Data structures using C
Opening a File:
Before performing any operation on file we must open the file with the function fopen( ).
Syntax : File_pointer=fopen(“File Name”, “AccessMode”);
Here File Name is the name of file which is to be opened for any operation.
Access Mode:- It indicates whether file is to be open for reading purpose or writing purpose.
Access Mode Meaning
w File is opened for writing onto the file.But
it overwrites.
r File is opened for reading purpose which is
already existed.
a File is opened for writing purpose which is
appending without overwriting the
previous contents.
w+ Created file is opened for both reading and
writing purpose. But it overwrites.
r+ Already existing file is opened for both
reading and writing purpose.
a+ Already existing file is opened for both
reading and writing purpose without
overwriting.

Writing Data into a File (Output function)

There are some specific functions are available in ‘C’ language for writing data into the file.
fprintf( ):- This function is used to write both numeric and non-numeric data into the file.
Syntax:
fprintf (file_pointer, “Control strings”, variable_list );
fputc( ) :- This function is used to write only singe character into the file.
Syntax :
fputc(character, file_pointer);
fputs( ) :- This function is used to write only group of characters (string) into the file.
Syntax :
fputs(String , file_pointer);
putw( ):- This function is used to write integer values only
Syntax:
putw (n , file_pointer);
Here n is an Integer variable.
Reading Data from the File (Input function)
There are some specific functions are available in ‘C’ language for reading data from the file.

fscanf( ):- This function is used to read both numeric and non-numeric data from the file.
Syntax:
fscanf (file_pointer, “Control strings”, variable_list );
fgetc( ) :- This function is used to read only singe character from the file.
Syntax :
fgetc(character,file_pointer);
fgets( ) :- This function is used to read only group of characters (string) from the file.
Syntax :
fgets(String , size, file_pointer);
getw( ):- This function is used to read integer values only
11
 Data structures using C
Syntax:
n = getw( file_pointer);
Here n is an Integer variable.

Closing a File
The file must be closed after performing the operation. To close a file ‘C’ provides the
function fclose().
Syntax:
fclose (file_pointer );

Error handling function in File

1. feof ( ):- This function returns a value non-zero when it reaches the end of file.
Example: - while(feof(fpt))
{
fscanf(fpt,%d%s%s”,rno,name,clss);
}
2. ferror( ):- This function is used to detect errors while reading or writing a file. It
takes one argument as file pointer variable and returns zero when there is a successful
read or write operation, otherwise it returns non-zero if there is a failure in read or
write.
Example:- if(ferror(fpt))
printf(“Errors in reading file”);

2. Random Access File or Direct Access File:-

In this type of file we can store the records directly. That is to insert ,delete or access the
records directly (random). In this magnetic disk is used to store the records. Each records has
their own address. By using random access file we can easily locate a records. These files are
faster than sequential files.
In C language there are certain important input/output functions are available, these are
ftell( ), fseek( ), rewind( ).

1. ftell( ):- This function is used to locate the current file position. It takes one
argument as file pointer variable and it returns a number of type long. This value
represents the number of bytes from the beginning of the file to the current position
Syntax : n=ftell(file_pointer)

2. fseek( ):- This function is used locate desired part in a file before data can be read
from or written to. It takes 3 arguments and moves file access position to desired
location within that file.
Syntax : fseek(file_pointer, offset, position);
file_pointer is a pointer of file type,
offset: it indicates number of bytes from specified position in a file.
Position : It indicates the position from which it should start moving

3. rewind( ):- This function is used to reset the position to the beginning of the file. It
moves the file pointer back to the beginning of the file.
Syntax : rewind(file_pointer)
12
 Data structures using C

//Example 1: -Write a C program to write and read the content of the file.

#include<stdio.h>
void main( )
{
int rno, ch;
char name[10], clss[10],ele;
FILE *fpt;
while(1)
{
printf("\n1. Write, 2.Read, 3.Quit");
printf("Enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1: fpt=fopen("Std.dat","a");
if(fpt==NULL)
{
printf("File can not open");
exit(0);
}
printf("Enter Roll Number");
scanf("%d",&rno);
printf("Enter name");
scanf("%s",name);
printf("Enter Class");
scanf("%s",clss);
fprintf(fpt ,"%-3d%10s%5s\n",rno,name,clss);
fclose(fpt);
break;
case 2: fpt=fopen("Std.dat","r");
if(fpt==NULL)
{
printf("File can not open");
exit(0);
}
clrscr();
while(!feof(fpt))
{
fscanf(fpt,"%d%s%s\n",&rno,&name,&clss);
printf("%d%10s%s\n",rno,name,clss);
}
fclose(fpt);
break;
case 3 : exit(0);
}
}

13
 Data structures using C
}

//Example 2: Write a C program to copy content of one file to another file

#include<stdio.h>
void main( )
{
int rno, ch;
char name[10], clss[10],ele;
FILE *fpt,*cp;
fpt=fopen("Std.dat","r");
cp=fopen("std1.dat","w");
while(!feof(fpt))
{
fscanf(fpt,"%d%s%s\n",&rno,&name,&clss);
fprintf(cp,"%d%s%s\n",rno,name,clss);
}
fclose(fpt);
fclose(cp);
printf(“File copied into another file”);
}

14
 Data structures using C
Chapter 4: Recursion

Definition :
Recursion is the name given to the ability of a function to call itself, until the desired
condition is satisfied.
During each recursive call, the local variables of a recursive function get a different
set of local variables but with the same name.
When we are executing a recursive function, it will not be executed immediately.
First it pushes the all the data onto the stack until desired condition is satisfied. Afterwards it
pops the element from the stack in the reverse order and executed one by one.

In recursion there are two types.

1.Direct Recursion :- A function which call itself
2.Indirect Recursion.:- A function1 calls function2 and function2 calls function1.

1. Direct Recursion 2. Indirect Recursion.

Function1( )
Function1( )

Function2( )
Function1( )

Function2( )

Function1( )

15
 Data structures using C

// Example 1: Write a recursive program to find Factorial of a given number.

#include<stdio.h>
int fact(int);
void main( )
{
int f, n;
printf(“Enter the number”);
scanf(“%d”,&n);
f=fact(n);
printf(“Factorial = %d”, f);
}

int fact(int n)
{
if(n = = 0) return 1;
else
return fact(n-1)*n;
}

// Example 2: Write a recursive program to find GCD of two numbers.

#include<stdio.h>
int GCD(int, int);
void main( )
{
int g,m,n;
printf(“Enter the two number”);
scanf(“%d%d” , &m , &n);
g = GCD(m , n);
printf(“GCD = %d”, g);
}

int GCD(int a, int b)

{
if(b = = 0) return a;
else
return GCD(b, a%b);
}

16
 Data structures using C
// Example 3: Write a recursive program to find Binomial co-efficient.

#include<stdio.h>
int BC(int, int);
void main( )
{
int n,r, ncr;
printf(“Enter value of n and r”);
scanf(“%d%d” , &n , &r);
ncr = BC(n , r);
printf(“Binomial coefficient = %d”, ncr);
}

int BC(int m, int k)

{
if(k= = 0) || (k= =m) return 1;
else
return (BC(m-1, k-1) + BC(m-1,k);
}

// Example 4: Write a recursive program to find the nth Fibonacci number .

#include<stdio.h>
int fibo(int);
void main( )
{
int n, f;
printf(“Enter number”);
scanf(“%d” , &n);
f = fibo( n );
printf(“nth Fibonacci number is = %d”,f);
}

int fibo(int m)
{
if(m= =1) return 0;
else
if (m = = 2) return 1;
else
return fibo(n-1)+fibo(n-2)
}

17
 Data structures using C
// Example 5: Write a recursive program to find xn where n>0, n<0 and n=0 .

#include<stdio.h>
float pwr(int,int);
void main( )
{
int x,n;
float power;
printf(“Enter base and exponent”);
scanf(“%d%d” , &x , &n);
power=pwr(x , n);
printf(“Power of x to n is = %f”,power);
}

int pwr(int a, int b)

{
if(b= = 0) return 1;
else
if(b>0) return pwr(a,b-1)*a;
else
return pwr(a,b+1)/a;
}

//Example 6: Problem associated with TOWER OF HANOI problem

Problem : It is a game problem. There will be three pegs and n number of different sized
disks ( plates). Each disk has a central hole so that it can be stacked on any of the pegs. We
call these pegs as A (Source), B( Destination) and C (temporary).
Initially all the disks are stacked on A peg in decreasing order. So we transfer all the disks
from A to B in same order. But conditions are no large disk is placed on the smaller one.
Secondly only one disk may be moved at a time and lastly each disk must be stacked on any
one of the pegs.

A C B

Disk-1
Disk-2
Disk-3

Fig: Tower of Hanoi Problem

Solution :- Now we can solve this problem by using recursion. There are 3 disks so
there are 7 moves in transferring these 3 disks from A to B by taking C as temporary peg.
These moves are as follows .
1. Move Disk1 from A peg to the B peg
2. Move Disk2 from A peg to the C peg.
3. Move Disk1 from B peg to the C peg.

18
 Data structures using C
4. Move Disk3 from A peg to the B peg.
5. Move Disk1 from C peg to the A peg.
6. Move Disk2 from C peg to the B peg.
7. Move Disk1 from A peg to the B peg.

The graphical representation of these moves is shown as follows.

A C B A C B A C B

A C B A C B A C B

A C B A C B

// Program to solve Tower of Hanoi problem using recursion.

#include<stdio.h>
void tower_hanoi( int, char, char, char);
void main( )
{
int n;
printf(“Enter the number of disks”);
scanf(“%d”,&n);
tower_hanoi(n, ‘A’, ‘B’, ‘C’);
}

void tower_hanoi(int n , char src, char dest, char tmp)

{
if(n>0)
{
/* Moving n-1 disks from A to C peg*/
tower_hanoi(n-1,src,tmp,dest);

/* Moving n disks from A to B peg*/

printf(“Moves disk %d from %c to %c \n”, n, src,dest);

19
 Data structures using C
/* Moving n-1 disks from C to B peg*/
tower_hanoi(n-1,tmp,dest , src);
}
return;
}

Advantages of Recursion
1. Ease in proving correctness.
2. Ease in complexity analysis
3. Ease to implement and it very efficient.
4. Recursive definition can be easily translated into a recursive function.
5. Recursion avoids the initialization, decisions and other activities like in iterative.
Disadvantages of Recursion
1. Consumes lot of memory
2. It takes more time to compute the result.
3. It executes slowly compare to Iterative.

Applications of Recursion
1. In Symbol manipulation
2. Non-numeric application
3. To solve a problem where there is a recursive in nature.

Difference between Iterative and Recursion

Iterative Recursion
1. It executes the statements again and 1. It is function which call itself.
again until condition become false.
2. It uses repetition such as for loop, while 2. It uses selection structure such as if or
loop or do-while loop as a control structure switch.
3. It explicitly uses repetition 3. Repetition is done by calling same
function name repeatedly.
4. It terminates when loop structure 4. It terminates when base case is satisfied.
become false.
5. In some situation we are not using 5. It is very efficient use for solving Tower
iterative, for example solving in Tower of of Hanoi and tree traversal problem.
Hanoi and tree traversal problem.
6. It more efficient in terms of memory 6. It is not efficient in term of memory
utilization utilization.
7. Executes much faster. 7. Executes slowly.

20
 Data structures using C
Chapter 5 Searching: and Sorting

Searching :
It is one type of problem solving technique where we can find the desired element
from the list.
Definition : To find a particular element from the list

Basic Search Techniques.

There are several search techniques are available, but some techniques are faster and
few of them are slower to find a desired element in a file. We know that file is a logically
collection of records. And each records has different types of data items. There is a key
associated with each record, which is used to distinguish among different records. A key may
be one of the following
 Internal Key : Which is within record at a particular position from the beginning of
the record.
 External Key :Which is separate table of key maintained pointers to the records.
 Primary Key : Which maintains the record uniqueness.
 Secondary Key: Which is alternative key for maintaining the record unique.

Searching Algorithm
Step 1: Read Key element
Step 2: Search the Key element from the list
Step 3: If the Key element is found in a list then search become “Successful” and returns the
entire record or a pointer to that record
Step 4” Otherwise display “Unsuccessful”

Search and insertion algorithm : An algorithm that is used to insert a new record with the
given key element, when the search is Unsuccessful is called search and insertion algorithm.

Retrieval : It is a successful search operation. It retrieves the desired information from a file
Dictionary: It is a table of records. It is also called search table . A key is used to retrieve the
information from this dictionary.

TYPES OF SEARCHES:
There are two types of searches. This classification depends on whether the search table is
present in the main memory or in the secondary memory. There are
1. Internal searching: In this entire search table is kept in main memory.
2. External searching: In this entire search table is kept in secondary memory.
Search table organization: Search tables that consist of records are organized in several
methods. These are.
1. Sequential organization : Eg: array
2. Non- Sequential organization: Eg: Linked list, tree, graph.

21
 Data structures using C
Searching Techniques
1. Linear Search or Sequential Searching.
2. Binary Search
3. Interpolation Search
4. Tree Searching
5. Index Sequential Searching
6. Hashing.
Sequential Searching
This is the simplest technique for searching. In this elements are unordered, so search
scanned from its first record until the desired record is found. That is element are examined
one by one sequential. Hence the name is Sequential or Linear Search. The search table is
organized either as an array or as linked list.
Algorithm:
Sequential_search( a[ ] , n , ele)
// Here a[ ] is an array, n is number of elements, ele is the searching element.
Step1: Flag=0
Step2: for i=0 to n-1 do
Step3: if(a[i] = ele) then
Step4: Flag=1
Step5: Go to step 6
Step6: if (Flag = 1) then
Step7: Display “ Element is Found”
Step8: else
Step9: Display “Element is not Found”
Step10: End
// Program: To search an element from the list using
//Using Iterative method //Using Recursion method
#include<stdio.h> #include<stdio.h>
void main( ) int linsearch(int a[],int n, int key);
{ void main( )
int a[10] , i .n,x, flag=0; {
printf(“Enter the number of elements”); int a[10] , i .n,x, flag ;
scanf(“%d”, &n); printf(“Enter the number of elements”);
printf(“Enter the elements”); scanf(“%d”, &n);
for(i=0 ; i<n ; i++) printf(“Enter the elements”);
scanf(“%d”, &a[i]); for(i=0 ; i<n ; i++)
printf(“Enter the search elements”); scanf(“%d”, &a[i]);
scanf(“%d”, &x); printf(“Enter the search elements”);
for(i=0 ; i<n ; i++) scanf(“%d”, &x);
{ flag = linsearch(a , n , x);
if(a[i]= = x) if(flag= = 1)
{ printf(“Element is found”);
flag=1; else
break; printf(“Element is not found”);
} }
} int linsearch(int a[],int n ,int key)
if(flag= = 1) {
printf(“Element is found”); if( n < 0 ) return 0;
else if( a[n-1]= = key) return 1;
printf(“Element is not found”); 22 else
} return linsearch(a,n-1,key);
}
 Data structures using C

Advantages of linear search

1. Very simple to understand
2. Ease to implement.
3. Elements are in unordered.
Disadvantages of linear search
1. It takes more time when array size is large.
2. If elements are stored in sorted order, then it is not efficient.

Binary Searching
In linear search it takes lengthy time for searching the element if the list is large. For
avoiding that we are using Binary Search. It is a divide and conquers strategy. In this we
divide the list into two part and find out the middle element, if the middle element is
searching element, then search become successful, otherwise to check whether the search
element is belongs to upper part of the list or lower part of the list. And again the divide the
list into two part, until element is found.

Algoritm:
Step1: Start
Step2: Read the number of elements, N
Step3: Read the elements.
Step4: for i=0 to n-1
Step5: Read a[i];
Step6: Read the search element, S
Step7: Initially flag=0, low =0 , high= n-1
Step8: while (low <= high)
Step9: mid = (low + high)/2;
Step10: if(a[mid] = S) then
Step11: flag=1 goto step
Step12: else
Step13:if ( a[mid] < S) then
Step14: low = mid + 1;
Step15: else
Step16: high = mid -1
Step17: while end
Step18:if ( flag = 1) then
Step19: Diplay “Element is Found”
Step20: else
Step21: Display “Element is not Found”
Step22: Stop

23
 Data structures using C

// Program: To search an element from the list using

//Using Iterative method

//Using Recursion method #include<stdio.h>
#include<stdio.h> void main( )
int bs(int a[],int n, int key,int low,int high); {
void main( ) int a[10] , i .n,x, flag=0,low,high,mid;
{ printf(“Enter the number of elements”);
int a[10] , i .n,x, flag ; scanf(“%d”, &n);
printf(“Enter the number of elements”); printf(“Enter the elements”);
scanf(“%d”, &n); for(i=0 ; i<n ; i++)
printf(“Enter the elements”); scanf(“%d”, &a[i]);
for(i=0 ; i<n ; i++) printf(“Enter the search elements”);
scanf(“%d”, &a[i]); scanf(“%d”, &x);
printf(“Enter the search elements”); low=0 ; high=n-1;
scanf(“%d”, &x); while(low<=high)
flag = bs(a , n , x , 0 ,n-1); {
if(flag = = 1) mid=(low+high)/2;
printf(“Element is found”); if(a[mid] = = x)
else {
printf(“Element is not found”); flag=1;
} break;
int bs(int a[],int n ,int key,int low,int high) }
{ else
int mid; if(x > a[mid]) low=mid+1;
if(low>high) return 0; else
mid=(low+high)/2; high=mid-1;
if(key = = a[mid]) return 1; }
else }
if(key < a[mid]) if(flag= = 1)
return bs(a,n,key,low,mid-1); printf(“Element is found”);
else else
return bs(a,n,key,mid+1,high); printf(“Element is not found”);
} }

Advantages of Binary search.

1. It is very efficient
2. Fast search execution

Disadvantages of Binary search.

1. Elements should be in a proper order.
2. If the elements are stored in linked list, this method can not be used.

24
 Data structures using C

Difference between Sequential Search and Binary Search

Sequential Search Binary Search

1. It is not necessary to sort the elements 1. It works on only sorted elements
2. It takes more time when list is large 2. It takes less time for searching
3. It is useful when list is small 3. It is useful when list is large.
4. Easily represent in array and linked list 4. Easily represent in array not in linked list
5.Number of comparisons are more 5. Number of comparisons are less

25
 Data structures using C

Sorting
Sorting it is a one type of problem solving technique. Suppose we want to
search for the telephone number of a person in the telephone directory. If the
telephone directory is not sorted in alphabetical order, then we may have to search for
the entire telephone directory. Since telephone directory is sorted, so we can find any
telephone number easily.
The main goal of sorting is to generate report of data and accessing data
efficiency.

General Background:

Definition :-Arranging the elements in a particular order, either ascending or descending.

Consider a file is collection of related records. Each record is having their unique key. Which
maintains the record uniquely. Here key is used to sort the records in a specified order. In
general a file is said to be sorted if the key associated with it record precedes the key.
Consider student information file system in which all the names are sorted in alphabetical
order. Here name is the key used to sorted the student record.
There are two type of sorting.

1. Internal Sorting: If all the records to be sorted are present in the main memory then
such a sorting is called internal sorting.
2. External Sorting.: If some of the records to be sorted are kept on secondary
memory. It is called external sorting.

Different types of sorting techniques.

1. Selection sort
2. Bubble sort
3. Insertion sort
4. Quick sort
5. Merge sort
6. Heap sort
7. Shell sort
8. Radix sort
9. Address calculation sort.

Efficiency of sorting
There are various types are available for sorting technique. But they have their own
advantages and disadvantages. Different techniques are useful in different application.
There are three most important consideration one should look at during the selection of a
sorting technique. They are.

1. Coding time: - The amount of time invested in writing full length sorting program.
2. Execution time: - The time required executing the program.
3. Space (Memory):- The amount of memory space to store the program.

26
 Data structures using C
1. Selection Sort.
This is one type of sorting technique. In this we are selecting the smallest elements and put it
into the first place, select the second smallest element and put into the second place, and so
on. It takes n-1 passes to sort the elements.
45 34 34 23 12 12 12 12 12
34 45 45 45 45 45 45 34 23
56 56 56 56 56 56 56 56 56
23 23 23 34 34 34 34 45 45
12 12 12 12 23 23 23 23 34

Pass-1 Pass-2

12 12 12 12 12
23 23 23 23 23
56 45 34 34 34
45 56 56 56 45
34 34 45 45 56

Pass-3 Pass-4

#include<stdio.h>
void main( )
{
int a[10] , i .n,tmp;
printf(“Enter the number of elements”);
scanf(“%d”, &n);
printf(“Enter the elements”);
for(i=0 ; i<n ; i++)
scanf(“%d”, &a[i]);
for(i=0 ; i<n-1 ; i++)
{
for(j=i+1 ; j<n; j++)
{
if( a[i] < a[j] )
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
}
printf(“\n Array elements are \n”);
for(i=0; i<n; i++)
printf(“%d\n”, a[i]); }

27
 Data structures using C
2. Bubble Sort.
This is simplest and easiest type of sorting technique. In this method during each pass each
element of an array is compared with its successor. If the element is not in the proper order
then they are interchanged. At the end of the first pass the largest element will be bubbled up
to the last position. And similarly at the end of second pass the second largest is bubbled up
to the last but one position and so on.

45 34 34 34 34 34 34 34 34
34 45 45 45 45 45 45 23 23
56 56 56 23 23 23 23 45 12
23 23 23 56 12 12 12 12 45
12 12 12 12 56 56 56 56 56

Pass-1 Pass-2

34 23 23 23 12
23 34 12 12 23
12 12 34 34 34
45 45 45 45 45
56 56 56 56 56

Pass-3 Pass-4
#include<stdio.h>
void main( )
{
int a[10] , i .n, tmp;
printf(“Enter the number of elements”);
scanf(“%d”, &n);
printf(“Enter the elements”);
for(i=0 ; i<n ; i++)
scanf(“%d”, &a[i]);
for(i=0 ; i<n ; i++)
{
for(j=i+1 ; j< (n-i-1); j++)
{
if( a[j] < a[j+1] )
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
printf(“\n Array elements are \n”);
for(i=0; i<n; i++) printf(“%d\n”,a[i]); }

28
 Data structures using C
3. Merge Sort.
This is one type divide and conquers sorting technique. In this method we divide the list into
smaller and smaller part until individual element. Compare these individual element and sort
into single list that is merging the element until n-1 elements. This process is called merge
sort.
93 77 65 49 85 51 41 28 18 43 27 21

93 77 65 49 85 51 41 28 18 43 27 21

93 77 65 49 85 51 41 28 18 43 27 21

93 77 65 49 85 51 41 28 18 43 27 21

93 77 65 49 85 51 41 28 18 43 27 21

77 93 65 49 85 51 28 41 18 27 43 21

65 77 93 49 51 85 18 28 41 21 27 43

49 51 65 77 85 93 18 21 27 28 41 43

18 21 27 28 41 43 49 51 65 77 85 93

C Funtion
void mergesort(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}
void merge(int a[],int low,int mid,int high)
{
int i,j,k,c[10];
i=low;

29
 Data structures using C
j=mid+1;
k=0;
while(i<=mid && j<=high)
{
if(a[i]<=a[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=a[j];
j++;
k++;
}
}

while(i<=mid)
{
c[k]=a[i];
i++;
k++;
}
while(j<=high)
{
c[k]=a[j];
j++;
k++;
}
for(i=0;i<k;i++)
a[i]=c[i];
}

// C program to sort n number in an ascending order using Merge Sort technique.

#inclue<stdio.h>
void megre(int a[], int, int , int);
void mergesort(int a[], int, int);
void main( )
{
int a[10],n,i;
printf(“Enter the number of elements”);
scanf(“%d”,&n);
printf(“Enter the elements “);
for( i = 0 ; i < n ; i ++)
scanf(“%d”,&a[i]);
mergesort(a, 0, n-1);
printf(“\n Sorted elements are\n”);

30
 Data structures using C
for( i = 0 ; i < n ; i ++)
printf(“\n%d”,a[ i ]);
}
void mergesort(int a[ ],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}
void merge(int a[ ],int low,int mid,int high)
{
int i,j,k,c[10];
i=low;
j=mid+1;
k=0;
while(i<=mid && j<=high)
{
if(a[i]<=a[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=a[j];
j++;
k++;
}
}
while(i<=mid)
{
c[k]=a[i];
i++;
k++;
}
while(j<=high)
{
c[k]=a[j];
j++;
k++;
}
for(i = 0 ; i < k ; i ++)
a[i]=c[i];

31
 Data structures using C
}

4. Quick Sort.

This is also one type of divide and conquers sorting technique. In this method we are
partitioning the list and one of the array elements is chose as a key value. This key value can
be the first element of an array. That is, if A is an array then key =A [0] and rest of the array
elements are grouped into two partitions such that
 One partition contains elements smaller than the key value.
 Another partition contains elements larger than the key value.

Partition 1 Partition 2

values<key Key values>key

#include<stdio.h>
void quicksort ( int a[ ] , int low , int high);
int partition ( int a[ ] , int low , int high );
void main( )
{
int a[10] , i .n,tmp;
printf(“Enter the number of elements”);
scanf(“%d”, &n);
printf(“Enter the elements”);
for(i=0 ; i<n ; i++)
scanf(“%d”, &a[i]);
quicksort ( a ,0 , n-1 );
printf(“\n Array elements are \n”);
for(i=0; i<n; i++)
printf(“%d\n”,a[i]);
}

void quicksort (int a[ ] ,int low , int high )

{
int p;
if( low < high )
p=partition(a, low, high);
quicksort(a, low, p-1);
quicksort(a, p+1, high);
}

int partition(int a[ ] , int low, int high)

32
 Data structures using C
{
int i , j , tmp , key , flag=1;
key=a[low];
i=low+1;
j=high;
while ( flag )
{
while ( key > a[i] && i < high )
i = i + 1;
while ( key < a[j] )
j = j – 1;
if ( i < j)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
else
flag=0;
}
tmp=a[low];
a[low]=a[j];
a[j]=tmp;
return j;
}

5. Insertion Sort.
This sorting technique involves the insertion of an elements into a sorted array in such a way
that the resulting array is also sorted. In this sort we assume that the first element of an array
is in its proper position. Then we take next element from the unordered array and place it in
its proper position, by comparing it with the one already sorted. This process is continued
until all the elements are placed into their proper positions.

#include<stdio.h>
void main( )
{
int a[10],i,j,n,tmp;
clrscr( );
printf("Enter the elements");
scanf("%d", &n);
printf("Enter the elements");
for(i=0;i<n;i++)
scanf("%d", &a[i]);
for(i=0;i<n;i++)
{
j = i;
while(j > = 1)

33
 Data structures using C
{
if(a[j] < a[j-1])
{
tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
j--;
}
}
printf("\n Sorted elements are\n");
for(i=0;i<n;i++)
printf("%d\n", a[i]);
getch( );
}

Chapter 6 : Stack

Definition: A stack is a non- primitive linear data structure. It is a collection of elements in

which elements are inserted and deleted at the same end is called top of the stack. (TOS). By
using this approach the last element inserted is to be deleted first from the stack. Hence it is
also known as Last In First Out (LIFO).

Example : Suppose n number of books are placed one above the other. The books are
inserted from top only. If a book is required, then the top book is selected. This process of
inserting the books at the top and removing the books from the top is called stacking of
books.

Top Application of Stack

i. Recursion
34 ii. Keeping track of function ca
iii. Evaluation of expressions
iv. Reversing the characters
 Data structures using C

Representation of Stacks
We can represent the stacks in the computer memory by using either the static representation
or the dynamic representation. The static representation means array representation. The
dynamic representation means the linked list representation.

Static Representation (Array representation)

To make it more simple, an array can be used to represent stack in memory . An array
representing a stack must be declared larger enough to hold all the elements at any point of
time.
In C a stack is created by the following statement.
int stack [ maxsize ];
Here maxsize is maximum number of elements. We can define this maxsize by marco
# define maxsize 10;
Now maxsize is 10. It means stack holds only up to 10 elements.

Operations on Stack:
There are three important operations on stack, these are
1. Push
2. Pop
3. Display.

1. Push operation
This operation adds (pushes) a new element on to the stack. While inserting a new element
into the stack, we first check out whether stack is full or not. If it is full then it is not possible
to insert into the stack. That is to check whether it exceeds maxsize or not.
If stack is not full then only we can insert the new element into the stack.
Top
Top 50 50
Top 40 40 40
30 30 30 30
Top
Top 20 20 20 20 20
Top 10 10 10 10 10 10

Insert 10 Insert 20 Insert 30 Insert 40 Insert 50 Insert 60

Stack Full
35
 Data structures using C

Over Flow: IF the stack is full it is not possible to insert a new element onto the
stack.. This is called Stack is Over Flow.

Algorithm for Push operation. C Function for Push operation.

Step1:- Start void push(int X)
Step2:- Check whether stack is full or not {
if (Top = maxsize-1) then if( top = = maxsize-1)
Display (“ Stack is Over flow:”); {
Exit printf(“Stack is Overflow”);
Step3:- Increment top of stack pointer return;
Top = Top + 1 }
Step4:- Insert an element X on to the stack top top = top +1;
Stack[Top]=X stack[top]=X;
Step5:- Stop. }

2. Pop operation
This operation deletes (pops) an element from the top of the stack. While deleting an
element from the stack, we first check out whether stack is empty or not. If it is empty then it
is not possible to delete from the stack. That is to check whether it top is less than zero or
not. If stack is not empty then only we can delete the element from the stack.

Top 50
40 Top 40
30 30 Top 30
20 20 20 Top 20
10 10 10 10 Top 10
) Top
Delete
Stack Empty
Under Flow: IF the stack is empty it is not possible to delete an element from the
stack.. This is called Stack is Under Flow.

36
 Data structures using C

Algorithm for Pop operation. C Function for Push operation.

Step1:- Start int pop( )
Step2:- Check whether stack is empty or not {
if (Top = -1) then if( top = =-1)
Display (“ Stack is Under Flow:”); {
Exit printf (“Stack is Under Flow”);
Step3:- Delete an element from the stack top return;
Step4:- Decrease top of stack pointer }
Top = Top - 1 return ( stack[top] );
Step5:- Stop. top = top -1;
}

3. Display operation
We can access the stack element from top of the stack until it reaches 0 that is bottom of the
stack. If the stack is empty, then it display the message “Stack is Empty” otherwise it
displays the all elements from the stack
void display( )
{
int i;
if(top= = -1)
printf(“Stack is Empty”);
else
for ( i = top ; i > = 0; i - - )
printf( “%d\n”, stack[i]);
}

// Program to demonstrate the operation of a stack.

#include<stdio.h>
#define MAX 10
void push(int);
int pop ( );
37
 Data structures using C
void display( );
int stack[MAX],top=-1,ele;
void main( )
{
int ch;
clrscr( );
while(1)
{
printf("1. Push. 2.Pop 3.Display 4. Exit \n");
printf("Enter Your choice");
scanf("%d" , &ch);
switch(ch)
{
case 1: printf("Enter the element");
scanf("%d", &ele);
push(ele);
break;
case 2: ele=pop( );
printf("Delete element = %d" ,ele);
break;
case 3: display( );
break;
case 4: exit(0);
}
}
}

void push(int x)
{
if(top==MAX-1)
{
printf("Stack is Over Flow");
return;
}
top=top+1;
stack[top]=x;
}

int pop( )
{
if(top==-1)
{
printf("Stack is Under Flow");
return 0;
}
return(stack[top--]);
}

void display( )

38
 Data structures using C
{
int i;
if(top==-1)
printf("Stack is Empty");
else
for(i = top; i>=0 ; i--)
printf("%d\n", stack[i]);
}

Infix, prefix and postfix notations

An expression in any programming language is meaningful combination of operands and
operators. The operand may be any type of the data i.e int , float ,or double. The operator
may be arithmetic, logical, relational or bitwise operators.
There are three ways of writing arithmetic expressions. These are infix, prefix and postfix
1. Infix :
In this type expression operator is in between the two operands. This is the usual
notation of writing mathematical expression.
Example : A + B , A – B , A * B , A / B , ( A + B ) * C , A * B + C etc
Depending upon the precedence of operator we are evaluating the expression.
2. Prefix:
In this type expression operator is before its two operands. This is also called polish
notation as it was developed by the polish mathematical Jan Lukasiewicz .

Example :
Infix Expression Prefix Expression
1. A+B +AB
2. A–B –AB
3. A*B *AB
4. A/B /AB
5. A+B *C +A*BC
6. A+B– C –+ABC
7. (A + B) * C * + A BC
8. X/Y^Z+A +/X^YZA
9. A*B+C/D +*AB/CD
10. B * C – D + E / F / (G + H) +–*BCD//EF+GH
3. Postfix:
In this type expression operator is after its two operands. This is also called suffix
notation. It is a reverse polish notation

Example :
Infix Expression Postfix Expression
1. A+B AB+
2. A–B AB–
3. A*B AB*
4. A/B AB/
5. A+B *C ABC*+
6. A+B– C AB+C–
7. (A + B) * C AB+C*

39
 Data structures using C
8. X/Y^Z+A XYZ^/A+
9. A*B+C/D AB*/CD+
10. B * C – D + E / F / (G + H) BC*DEF/GH+/–+

40
 Data structures using C
Conversion of an arithmetic expression from infix to postfix.
In converting an expression from infix to postfix the following assumptions are made.
1. Only single character operands are used.
2. Only + – * and / operators are considered
3. Expression is error free.
The conversion procedure assigns a precedence to each operator. This helps in determining
where an operator will be placed in the postfix expression.

Algorithm:
Step 1:- Scan the infix expression from LEFT to RIGHT
Step 2:- If the scanned symbol is left parenthesis push it onto the stack
Step 3:- If the scanned symbol is an operand then place directly in the postfix expression.
Step 4:- If the scanned symbol is right parentheses, then go on popping all the elements from
the stack and place them in the postfix expression till we get matching left
parenthesis.
Step 5:- If the scanned symbol is an operator then go on removing all the operators from the
stack and place them in the postfix expression . If and only if the precedence of the
operator which is on the top of the stack is greater than or equal to the precedence of
the scanned operator. Otherwise push the scanned operator onto the stack.

Example : Convert the infix expression to Postfix expression A+B*C

Action Symbol Stack Postfix Description
Scan A A Empty A Place it on the postfix
Scan + + + A `Push + onto the stack
Scan B B + AB Place it in the postfix
Scan * * +* AB * has higher precedence than + so
push onto the top of stack.
Scan C C +* A BC Place it in the postfix
Symbols are over A B C * + Popped all the operator from the stack
and place them in the postfix.

41
 Data structures using C

// Program to convert infix expression into postfix expression.

#include<stdio.h>
#include<string.h>
int i=0, pos=0, top=-1,len;
char symbol, tmp;
char infix[20], postfix[20], stack[20];
void push(char);
char pop( );
void infix_postfix(char a[], char b[]);
void main( )
{
clrscr( );
printf("Enter the infix expression");
scanf("%s", infix);
infix_postfix(infix,postfix);
printf(" Postfix expression = %s", postfix);
getch( );
}

void infix_postfix(char infix[],char postfix[])

{
len=strlen(infix);
push('#');
while(i<len)
{
symbol=infix[i];
switch(symbol)
{
case '(': push(symbol); break;
case ')':tmp=pop( );
while(tmp != '(' )
{
postfix[pos]=tmp;
pos++;
tmp=pop();
}
break;
case '+':
case '-':
case '*':
case '/':
case '^': while(precd(stack[top]) >= precd(symbol))
{
tmp=pop();
postfix[pos]=tmp;
pos++;
}

42
 Data structures using C
push(symbol);
break;
default: postfix[pos++]=symbol;
break;
}
i++;
}
while(top > 0)
{
tmp=pop();
postfix[pos++]=tmp;
}
return;
}
void push(char ele)
{
top=top+1;
stack[top]=ele;
}
char pop()
{
char ele;
ele=stack[top];
top=top-1;
return (ele);
}
int precd(char ele)
{
int p;
switch(ele)
{
case '^': p=3; break;
case '*':
case '/': p=2; break;
case '+':
case '-': p=1; break;
case ')':
case '(': p=0; break;
case '#': p=-1; break;
}
return p;
}

43
 Data structures using C
Evaluation of a Postfix Expression.
It is another application of stack. In this we are evaluate the postfix expression. In this we are
storing the numeric value instead of character into the stack.

Algorithm
Step 1: Store the numeric values corresponding to each operand in an array.
Step 2: Scan the given postfix expression from LEFT to RIGHT
Step 3: If the scanned symbol is an operand , then push its value onto the stack.
Step 4: If the scanned symbol is an operator then pop out two values from the stack and
assign them respectively to operand2 and operand1.
Step 5: Then perform the required arithmetic operation.
If operator is * then result =operand1 * operand2
If operator is / then result =operand1 / operand2
If operator is + then result =operand1 + operand2
If operator is - then result =operand1 - operand2
Step 6: Push the result onto the stack
Step 7: Repeat step 1 to 4 until all the symbols in the postfix expression are over.

Example : Evaluate the following postfix expression

A B C * + (A=2 B=4 C=5)

Action Symbol Stack Operand1 Operand2 Result Description

Scan A A 2 - - - Push A into
stack
Scan B B 2 4 - - - Push B into
stack
Scan C C 2 4 5 - - - Push C into
stack
Scan * * 2 20 4 5 20 Pop 2 values and
assign them to
operand2 and
operand1 and
evaluate. Then
push result back
to the stack.
Scan + + 22 2 20 22 ”
Pop Value 22 is the
out the result.
stack
content

44
 Data structures using C
// Program to evaluate postfix expression
#include<stdio.h>
#include<math.h>
#include<ctype.h>
#include<string.h>
float stack[10];
int top=-1;
void push(float);
float pop( );
float eval_exp(char *n,float a[]);
void main( )
{
int i=0;
char postfix[20];
float value[20],result;
printf("Enter the valid Postfix Expression");
scanf("%s",postfix);
while(postfix[i]!='\0')
{
if(isalpha(postfix[i]))
{
printf("Enter the value of %c", postfix[i]);
scanf("%f", &value[i]);
}
i++;
}
result=eval_exp(postfix, value);
printf("The result of %s = %f", postfix , result);
getch();
}
float eval_exp(char postfix[],float value[])
{
int i=0;
float op1,op2,result;
char ch;
while(postfix[i]!='\0')
{
ch=postfix[i];
if(isalpha(postfix[i]))
push(value[i]);
else
{
op2=pop( );
op1=pop( );
switch(ch)
{
case '+': push(op1+op2); break;
case '-': push(op1-op2); break;
case '*': push(op1*op2); break;

45
 Data structures using C
case '/': push(op1/op2); break;
case '^': push(pow(op1,op2)); break;
}
}
i++;
}
result=pop();
return (result);
}
void push(float num)
{
top++;
stack[top]=num;
}
float pop( )
{
float n;
n=stack[top];
top--;
return n;
}

46
 Data structures using C

Chapter 7 : Queue

Definition : A queue is a non-primitive linear data structure. It is an ordered collection of

data items into which items are added at one end called rear and they are deleted from the
other end, called the front.
In queue, data elements can only be deleted from the queue in the order in which they are
inserted into the queue. That is fist element added to the queue us the first one to be deleted.
Therefore, a queue is often called a First in First out (FIFO) data structure.

Front 10 20 30 40 50 Rear

Queue
In the above queue, there are five elements . This number is the capacity or the size of a
queue. This queue cannot hold more than five elements. And the element 50 is the most
recently added one and hence it is the last to be deleted.

Representation of a Queue.
We can represent the queue in the computer memory by using either the static representation
or the dynamic representation. The static representation means array representation. The
dynamic representation means the linked list representation.

Static Representation (Array representation)

An array based representation of a queue, involves declaring a one-dimensional array of
some specified size. The array representation of a queue needs two indices , Front and Rear
which indicate the position of front and rear end.
In C a queue is created by the following statement.
int queue [ maxsize ];
Here maxsize is maximum number of elements. We can define this maxsize by marco
# define maxsize 10;
Now maxsize is 10. It means queue holds only up to 10 elements.

Operations on a queue:
There are three important operations on queue, these are

1. Insert operation : It inserts a new data item at the rear of the queue.
2. Deletion operation: It deletes and then returns the data item at the front of the queue
3. Display operation : It displays the contents of queue.

Types of queue
1. Simple Queue / Ordinary Queue.
2. Circular Queue

47
 Data structures using C
3. Double ended Queue
4. Priority Queue.

1. Simple Queue:

Algorithm for Insertion operation. C Function for Insert operation.

Step1:- Start void Qinsert(int X)
Step2:- Check whether queue is full or not {
if (Rear = maxsize-1) then if(Rear > = maxsize-1)
Display (“Queue is over flow :”); {
Exit printf(“Queue is Full ”);
Step3:- Increment rear of queue pointer return;
Rear = Rear + 1 }
Step4:- Insert an element X into the queue. Rear = Rear +1;
queue[Rear]=X queue[Rear]=X;
if(front= -1) if(Front = = -1)
front=0 Front =0;
Step5:- Stop. }

Initially Front and Rear is equal to -1, Total Capacity of Queue is 4

So initially Queue is Empty
Empty Queue
Front = Rear = -1

F R
Now Insert Element 10 to the queue.
Rear= Rear + 1
10
Front = 0

F R

Now Insert 20 to the queue.

Rear= Rear + 1
10 20
Front = 0

F R
Now Insert 30 to the queue.
Rear= Rear + 1
10 20 30
Front = 0
48
 Data structures using C

F R

Now Insert 40 to the queue.

Rear= Rear + 1
10 20 30 40
Front = 0

F R
Now delete an element

20 30 40 Front = Front +1

F R
Now delete an element
30 40
Front = Front +1

F R

Algorithm for Delete operation. C Function for Delete operation.

Step1:- Start int Qdelete( )
Step2:- Check whether queu is empty or not {
if (Front = -1) then if( Front = =-1)
Display (“Queue is Under Flow :”); {
Exit printf (“Queue is Under Flow”);
Step3:- Delete an element from the queue return;
Step4:- Increment Front by 1 }
If ( Front = Rear) return ( queue[Front] );
Front = Rear = -1 if( Front = = Rear) Front = Rear = -1;
else else
Front = Front + 1 Front = Front+1
Step5:- Stop. }
Stack (data structure)
From Wikipedia, the free encyclopedia

49
 Data structures using C

// Program to Demonstrate the Queue operation, such as insertion deletion and display
#include<stdio.h>
#define MAX 5
void QInsert( );
void QDelete( );
void QDisplay( );
int q[MAX], front = -1, rea r= -1, ch;
void main( )
{
clrscr( );
while(1)
{
printf("\n-------------\n");
printf("1.Insert \n 2.Delete \n 3.Display \n 4.Exit \n");
printf("\n------------------\n");
printf("Enter your choice");
scanf("%d", &ch);
switch(ch)
{
case 1: QInsert( ); break;
case 2: QDelete( ); break;
case 3: QDisplay( ); break;
case 4: exit(0);
}
}
}
void Qinsert( )
{
int n;
if(rear = = MAX-1)
{
printf("\n Queue is Full\n");
return;
}
else
{
printf("Enter the element");
scanf("%d", &n);
rear++;
q[rear]=n;
if(front = = -1) front++;
}
return;
}

50
 Data structures using C

void QDelete( )
{
int n;
if(front == -1)
{
printf("\n Queue is Empty \n");
return;
}
else
{
if(front = =rear)
front = rear = -1;
else
{
n=q[front];
printf("\n Deleted element is = %d", n);
front ++;
}
}
}
void QDisplay ( )
{
int i;
if(front = = -1)
printf("\n Queue is Empty\n");
else
{
printf("\n Queue Elements are \n");
for(i=front; i < = rear; i++)
printf("%3d", q[i]);
}
}

Draw backs (Disadvantages) of Simple Queue

1. Time Consuming
2. Signaling queue full even if the queue is actually empty.

2. Circular queue:
In simple queue, if we delete all the elements from the queue. At the end of these deletions
the value of Front would become n value. In this situation , if we attempt to insert a new data
item to the queue., we would receive a message “ Queue is Full”, even though queue is not
full. This problem can be overcome by implementing a queue as a circular queue.

In circular queue, if we reach the end while inserting elements to it, it is possible to
insert new elements if the slots at the beginning of the circular queue are empty.

Q [Max-1] Q [0]

Rear Front 51
Q [1]
 Data structures using C
Here also Front and Rear are used to keep track of the
elements to be deleted and inserted respectively.
Front is one position behind the first element of the
queue. Front = Rear if and only if the queue is empty.
Each time a new element is inserted into the queue the
variable Rear is incremented by one. Similarly each
time an item is deleted from the queue; the variable
front is increment by one. In this we maintain the one
counter variable. It increments when the inserting a new
element and decrement when we are deleting the
element.

Algorithm for Insertion operation. C Function for Insert operation.

Step1:- Start void CQinsert(int X)
Step2:- Check whether queue is full or not {
if (count = maxsize-1) then if(count = maxsize-1)
Display (“Queue is over flow :”); {
Exit printf(“Queue is Full ”);
Step3:- Increment counter variable return;
count=count + 1 }
Rear=(Rear+1) % maxsize Rear = (Rear +1) % maxsize;
Step4:- Insert an element X into the queue. count++;
queue[Rear]=X queue[Rear]=X;
Step5:- Stop }

Algorithm for Delete operation. C Function for Delete operation.

Step1:- Start int CQdelete( )
Step2:- Check whether queue is empty or not {
if (count = 0) then if( count = = 0)
Display (“Queue is Under Flow :”); {
Exit printf (“Queue is Under Flow”);
Step3:- Delete an element from the queue return;
Step4:- Decrement counter by 1 }
Count=count - 1 return ( queue[Front] );
Front = (Front + 1)%maxsize count - -;
Step5:- Stop. Front = (Front + 1) % maxsize;
}

52
 Data structures using C

// Program to Demonstrate the Circular Queue operation, such as insertion deletion and
display
#include<stdio.h>
#define MAX 5
void CQInsert( );
void CQDelete( );
void CQDisplay( );
int q[MAX], front = -1, rea r= -1, ch,count=0,ele;
void main( )
{
clrscr( );
while(1)
{
printf("\n-------------\n");
printf("1.Insert \n 2.Delete \n 3.Display \n 4.Exit \n");
printf("\n------------------\n");
printf("Enter your choice");
scanf("%d", &ch);
switch(ch)
{
case 1: CQInsert( ); break;
case 2: CQDelete( ); break;
case 3: CQDisplay( ); break;
case 4: exit(0);
}
}
}
void CQinsert( )
{
if(count = maxsize-1)
{
printf(“Circular Queue is Full ”);
return;
}
printf(“Enter the element”);
scanf(“%d”,&ele);
Rear = (Rear +1) % MAX;

53
 Data structures using C
count++;
queue[Rear]=ele;
}

int CQdelete( )
{
if( count = = 0)
{
printf (“Circular Queue is Empty”);
return;
}
ele= queue[Front] ;
count - -;
Front = (Front + 1) % Max;
return ele;
}

void CQDisplay ( )
{
int i;
if(count = = 0)
printf("\n Circular Queue is Empty\n");
else
{
printf("\n Circular Queue Elements are \n");
for(i=1; i < = count; i++)
{
printf("%3d", q[Front]);
Front=(Front+1)%Max;
}
}

54
 Data structures using C

3. Double Ended Queue (DEque)

It is also a ordered collection of elements in which insertion and deletion operations are
performed from both the ends. That is we can insert elements from the rear end or from the
front end. Similarly the deletion can be made either from the front end or from the rear end.
Hence it is called double ended queue (DEque).
There are two types of deques. These two types are due to the restrictions put to perform
either the insertions or deletions only at one end. They are,
1. Input-restricted deque.
2. Output-restricted deque.
Front Rear
Deletion Insertion
Insertion 10 20 30 40
Deletion

There are 4 Operations on Deque.

1. Insertion of an element at the Rear end of the queue.
2. Deletion of an element from the Front end of the queue.
3. Insertion of an element at the Front end of the queue.
4. Deletion of an element from the Rear end of the queue

For an Input-restricted deque only the operations in 2, 3, 4 are valid.

For an Output-restricted deque only the operations in 1, 2, 3 are valid.

4. Priority Queue.
A priority queue a queue in which items can be inserted or deleted based in the priority. An
element with highest priority is processed before processing any of the lower priority
elements. If the elements in the queue are of same priority , then the elements ,which is
inserted first into the queue, is processed.
In priority queue, there are two types.
a) Ascending priority queue: In this elements can be inserted in any order. But while
deleting an element from the queue, only the smallest element is removed first.
b) Descending priority queue: In this elements can be inserted in any order. But while
deleting an element from the queue, only the largest element is removed first.

55
 Data structures using C

Application of queue.

1. Computer Science: Process queue and print queue.

2. Simulation: traffic light control.

Chapter 8 : Linked List

Definition:- A linked list is a dynamic data structure, it is non-sequential collection of data
items. For every data item in the linked list, there is an associated pointer that would given
the memory location of the next data item in the linked list.
The data items in the linked list are not in consecutive memory locations. But they
may be anywhere in memory . However accessing of these item is easier as each data item
contained within itself the address of the next data item. A linked list is shown as below.

Start

10 20 30 40

Null

Components of a Linked List

A linked list is a non-sequential collection of data items called nodes. These nodes in
principle are structure containing fields. Each node in a linked list basically contains two
fields.
1. Data field:- It contains an actual value to be stored and processed.
2. Link field:- It contains the address of the next data item.

Null Pointer: The link field of the last node contains zero rather than a valid address. It is a
null pointer and indicates the end of the list.

External Pointer: It is the pointer to the vary first node in the linked list. It enables us to
access the entire lined list. In the above figure start is an external pointer.

Empty List: IF the nodes are not present in a linked list, then it is called an empty linked
list or simply empty list or null list.

Representation of a Linked List.

A linked list is a list of links. Representation of a linked list in the computer’s memory as a
whole is done by representing each constituent node with its appropriate link to another node.
Therefore, let us first look at how each node is represented. Each and every node in a linked
list is a structure containing two fields such as the data field and the link field. Such a
structure is represented in c as follows.

56
 Data structures using C
Physical view:
Data Link

node
Logical view: struct node
{
int data;
struct node *link;
};

Self-referential structures :- The node has clearly two fields. The first one is an integer
data item and second one is link( pointer) to the next node of the same type. Hence such
structures are called self-referential structures.

A structure for a node having many fields can be defined as follows

Struct node Example
{ struct std_node
Data_type variable1; {
Data_type variable2; int RollNo;
Data_type variable3; char Name[20];
Data_type variable4; float avg;
. struct std_node *next;
. };
Data_type variableN;
struct node *next;
};

Advantages of Linked List

1. Linked lists are dynamic data structures: That is they can grow or shrink during
the execution of a program.
2. Efficient memory utilization: Here memory is not allocated already. Memory is
allocated whenever it is required. And it is de-allocated (removed) when it is no
longer needed.
3. Insertion and deletions are easier and efficient: Linked lists provide flexibility in
inserting a data item at a specified position and deletion of a data item from the given
position.
4. Many complex applications can be easily carried out with linked list.

Disadvantages of Linked List

1. More memory : if the number of fields are more then more memory space is needed.
2. Access to an arbitrary data item is little bit cumbersome and also time-consuming.

Types of Linked Lists

57
 Data structures using C
Basically, we can put linked lists into the following four types.

1. Singly-linked list
2. Doubly linked list
3. Circular linked list
4. Circular doubly linked list

Basic Operations
The basic operations to be performed on the lists are as following.
1.Creation. : It is used to create a new linked list. Here, the constituent node is created
2.Insertion. : It is used to insert a new node in the linked list at the specified position.
3.Deletion. : It is used to delete an item from the linked list.
4. Traversing.: It is used to traverse the all nodes of a linked list from one end to another
end. In this 2 types.
a. Forward Traversing : Start traversing from first node to last node.
b. Backward Traversing : Start traversing from last node to first node.
5.Searching : It is used to access the desired node in the linked list.
6.Concatenation : It is used to join the two lists.
7.Display : It is used to display the node information from the linked list.

A singly linked list is a dynamic data structure . It may be grow or shrink depending upon
the operation made. It is one in which all nodes are linked together in some sequential
manner. Hence, it is also called linear linked list. Clearly it has the beginning and the end.
In C a linked list is created using structures, pointers and dynamic memory allocation
function malloc. In this we consider head is an external pointer. It is used to create and
access the nodes from linked list.
Creating a node:
struct node
{
int data;
struct node *next;
};
typedef struct node *Node;
Node * head;
Inserting Nodes:
In this we are inserting a new element into the linked list it has the following three instances.
1. Inserting at the beginning of the list.
2. Inserting at the end of the list.
3. Inserting at the specified position within the list.

To insert the element into the linked list, the following three things should be done.
1. Allocating a node

58
 Data structures using C
2. Assigning the node.
3. Adjusting the position.

1. Inserting a Node at the Beginning

Algorithm :
Step1: Allocate the memory for the new node.
Step2: Assign the value to the data field of the new node.
Step3: Make the link(pointer) field of the new node to point to the starting node of the
linked list.
Step4: Then set the external pointer to the point to the new node.

head

10 20 30 40

Null
50
temp

C Function to insert a Node at the beginning

struct node
{
int data;
struct node *next;
};
typedef struct node *Node;

Node getnode()
{
Node tmp;
tmp=(Node)malloc(sizeof(struct node));
tmpnext=NULL;
return tmp;
}

Node insert(int ele)

{
Node tmp;
tmp=getnode();

59
 Data structures using C
tmpdata=ele;
if(head= =NULL)
head=tmp;
else
{
tmpnext=head;
head=tmp;
}
return head;
}

2. Inserting a Node at the End.

Algorithm :
Step1: Allocate the memory for the new node.
Step2: Assign the value to the data field of the new node.
Step3: If the list is empty then make the new node as a head.
Step4: If the list is not empty then go to the last node and then inset the new node
after the last node.

head

10 20 30 40

50
Null
temp

C Function to insert a Node at the End

struct node
{
int data;
struct node *next;
};
typedef struct node *Node;

Node getnode()
{
Node tmp;
tmp=(Node)malloc(sizeof(struct node));
tmpnext=NULL;
return tmp;
}
Node insertEnd(int ele)
{
Node tmp , p;
tmp=getnode( );

60
 Data structures using C
tmpdata=ele;
if(head= =NULL)
head=tmp;
else
{
p=head;
while(pnext!=NULL)
p=pnext;
pnext=tmp;
}
return head;
}

3. Inserting a Node at the Specified Position

Algorithm:
Step1: Allocate the memory for the new node.
Step2: Assign the value to the data field of the new node.
Step3: Make the link field of the new node to point to NodeB
Step4: Make the link field of NodeA to point to new node..

head NodeA NodeB

10 20 30 40

50
temp

C Function to insert a Node at thespecified position

struct node
{
int data;
struct node *next;
};
typedef struct node *Node;

Node getnode( )
{
Node tmp;
tmp=(Node)malloc(sizeof(struct node));
tmpnext=NULL;
return tmp;
}
Node insertS(int ele,int k)
{
int count=0;
Node tmp,p;

61
 Data structures using C
tmp=getnode( );
tmpdata=ele;
if(head= =NULL)
head=tmp;
else
{
p=head;
while(pvnext!=NULL || count<k)
{
p=pnext;
count++;
}
if(p= =NULL)
{
printf("Not a Valide position");
return head;
}
tmpnext=pnext;
pnext=tmp;
}
return head;
}

Deleting Nodes:
In this we are deleting a node from the linked list it has the following three instances.
1. Deleting the first node of the linked list.
2. Deleting the last node of the linked list.
3. Deleting the specified node within the linked list.

1. Deleting the first Node

Algorithm :
Step1: If the list is empty then display message “List is Empty”.
Step2: If the list is not empty then move head pointer to the next node.
Step3: Free the first node.
.

head temp

10 20 30 40

Null

C Function to Delete the node from the first.

struct node

62
 Data structures using C
{
int data;
struct node *next;
};
typedef struct node *Node;

Node deleteF()
{
Node tmp=head;
if(head= =NULL)
{
printf("List is Empty\n");
return head;
}
head=headnext;
free(tmp);
return head;
}

2. Deleting the Last Node.

Algorithm:
Step1: If the list is empty then display message “List is Empty”.
Step2: If the list is not empty then go on traversing the list till the last but one
Step3: Set the link pointer field of the last but one node to NULL.
Step4: Free Last Node.

head p temp

10 20 30 40

Null

C Function to Delete a node from the last

struct node
{
int data;
struct node *next;
};
typedef struct node *Node;

Node deleteE()
{
Node tmp=head,p;
if(head= =NULL)
{

63
 Data structures using C
printf("List is Empty\n");
return head;
}
while(tmpnext!=NULL)
{
p=tmp;
tmp=tmpnext;
}
free(tmp);
pnext=NULL;
return head;
}

3. Deleting a Node from Specified Position

Algorithm:
Step1: If the list is empty then display message “List is Empty”.
Step2: If the list is not empty then make the link field of NodeA to point to NodeB
Step3: Make the link field of the new node to point to NodeB
Step4: Free the node between NodeA and NodeB..

head NodeA NodeB

10 20 30 40 50

C Function to Delete a node from specified position.

struct node
{
int data;
struct node *next;
};
typedef struct node *Node;

Node deleteS(int k)
{
int count=1;
Node tmp=head,p=tmp;
if(head= =NULL)
{
printf("List is Empty\n");
return head;
}
while(tmpnext!=NULL)
{
if(k==count)
{
pnext=tmpnext;

64
 Data structures using C
free(tmp);
}
p=tmp;
tmp=tmpnext;
count++;
}
if(tmp= =NULL)
{
printf("Invalid Position\n");
return head;
}
return head;
}

// Program to demonstrate the linked list operations- Insert node from Beginning, End,
Specified position, Deleting Node from Beginning, End, Specified Position and Display the
elements.

#include<stdio.h>
struct node
{
int data;
struct node *next;
};
typedef struct node *Node;
Node getnode();
Node insert(int);
Node insertE(int);
Node insertS(int,int);
Node deleteF();
Node deleteE();
Node deleteS(int);
void display(Node);
Node head=NULL;
void main()
{
int ch,ele,p;
clrscr();
while(1)
{
printf("\n----Insert Node -----\n");
printf("1.Front \n2.End \n3.Specific position \n");
printf("\n----Delete Node -----\n");
printf("4.Front \n5.End \n6.Specific position \n7.Display\n8.Exit\n");
printf("Enter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter the element");

65
 Data structures using C
scanf("%d",&ele);
head=insert(ele);
break;
case 2: printf("Enter the element");
scanf("%d",&ele);
head=insertE(ele);
break;
case 3: printf("Enter the element");
scanf("%d",&ele);
printf("Enter the position");
scanf("%d",&p);
head=insertS(ele,p);
break;
case 4: head=deleteF();
break;
case 5: head=deleteE();
break;
case 6: printf("Enter the position");
scanf("%d",&p);
head=deleteS(p);
break;
case 7: printf("Elements of list are\n");
display(head);
break;
case 8: exit(0);
}
}
}

Node getnode()
{
Node tmp;
tmp=(Node)malloc(sizeof(struct node));
tmpnext=NULL;
return tmp;
}

Node insert(int ele)

{
Node tmp;
tmp=getnode();
tmpdata=ele;
if(head= =NULL)
head=tmp;
else
{
tmpnext=head;
head=tmp;
}

66
 Data structures using C
return head;
}

Node insertE(int ele)

{
Node tmp,p;
tmp=getnode();
tmpdata=ele;
if(head= =NULL)
head=tmp;
else
{
p=head;
while(pnext!=NULL)
p=pnext;
pnext=tmp;
}
return head;
}

Node insertS(int ele,int k)

{
int count=1;
Node tmp,p;
tmp=getnode();
tmpdata=ele;
if(head==NULL)
head=tmp;
else
{
p=head;
while(pnext!=NULL && count<k-1)
{
p=pnext;
count++;
}
if(p==NULL)
{
printf("Not a Valide position");
return 0;
}
tmpnext=pnext;
pnext=tmp;
}
return head;
}

Node deleteF()
{

67
 Data structures using C
Node tmp=head;
if(head==NULL)
{
printf("List is Empty\n");
return head;
}
head=headnext;
free(tmp);
return head;
}

Node deleteE()
{
Node tmp=head , p;
if(head= =NULL)
{
printf("List is Empty\n");
return head;
}
while(tmpnext!=NULL)
{
p=tmp;
tmp=tmpnext;
}
free(tmp);
pnext=NULL;
return head;
}

Node deleteS(int k)
{
int count=1;
Node tmp=head,p=tmp;
if(head= =NULL)
{
printf("List is Empty\n");
return head;
}
while(tmpnext!=NULL)
{
if(k==count)
{
pnext=tmpnext;
free(tmp);
}
p=tmp;
tmp=tmpnext;
count++;
}

68
 Data structures using C
if(tmp==NULL)
{
printf("Invalid Position\n");
return head;
}
return head;
}

void display(Node first)

{
Node tmp;
tmp=first;
while(tmp!=NULL)
{
printf("%d\t",tmp->data);
tmp=tmpnext;
}
}

Advantages of Singly Linked List.

 Accessibility of a node in the forward direction is easier.
 Insertion and deletion of nodes are easier.

Disadvantages of Singly Linked List.

 There is a no backward traversal.
 Accessing a node is time-consuming..

2. Circular Linked List.

It is also a singly linked list, but last node is connected to the first node. That is the last node
does not have a NULL pointer, rather than it points to the beginning of the linked list.

First Last
10 20 30 40

A circular linked list has no beginning and no end. Therefore it is necessary to establish the
First and Last node in such linked list.

1. Inserting a Node From the beginning.

Algorithm
Step1: Allocate the memory for the new node.
Step2: Assign value to the new node.
Step3: If the list is empty then set First = Last= New_node
Step4: If the list is not empty then make the link field of the new node to point to the First
node. And make the link field of the Last node to point to the new node, and finally
set First to the new node

First Last
10 20 30 69 40
 Data structures using C

50 temp

C Function to insert a node from the Beginning.

Insert_Node(Node first, Node last)
{
Node temp;
temp=getnode( );
tempnext=temp;
if(first = = NULL)
first = last = temp;
else
{
tempnext=first;
lastnext=temp;
first=temp;
}
}

1. Inserting a Node at the End.

Algorithm
Step1: Allocate the memory for the new node.
Step2: Assign value to the new node.
Step3: If the list is empty then set First = Last= New_node
Step4: If the list is not empty then make the link field of the Last node point to the new node.
Also make the link field of the new node to point to the First node , and finally set
Last to the new node

First Last
10 20 30 40
tmp

50

C Function to insert a node at End.

Insert_Node(Node first, Node last)
{
Node temp;
temp=getnode( );
tempnext=temp;

70
 Data structures using C
if(first = = NULL)
first = last = temp;
else
{
Lastnext = temp;
tempnext = First;
Last=temp;
}
}

1. Deleting a Node from the beginning.

Algorithm
Step1: If the list is empty then display the message “ List is Empty”
Step2: If the list is not empty then make temp pointer to point to the First node and move the
First Node to next node. Then set the link field of the last node point to the First.
Step3: Free temp node

temp First Last

10 20 30 40

C Function to Delete a node from the Beginning.

Delete_Node(Node first, Node last)
{
Node temp;
if(first = = NULL)
printf(“List is Empty”);
else
{
temp=First;
First=Firstnext;
Lastnext=First;
Free(temp);
}
}

2.Deleting a Node at the End.

Algorithm
Step1: If the list is empty then display the message “ List is Empty”
Step2: If the list is not empty then move the temp pointer to up to last node. Then link field
of temp node the First node. Free Last node, Set the temp node to Last node..

First temp Last

10 20 30 40

71
 Data structures using C

C Function to Delete a node from the Beginning.

Delete_Node(Node first, Node last)
{
Node temp;
if(first = = NULL)
printf(“List is Empty”);
else
{
temp=First;
while(tempnext !=NULL)
temp-tempnext;
tempnext=First;
free(Last);
Last=temp;
}
}

Advantages
 Nodes can be accessed easily
 Deletion of node is easier
 Concatenation and splitting of circular linked list are more efficient.

Disadvantages
 It may enter an infinite loop
 Head node is required to indicate the First and Last of the circular linked list.
 Backward traversing is not possible.

3. Doubly Linked List

The problem with singly linked list is that we cannot access the predecessor or nodes from
the current node. This can be over come in doubly linked list.
A doubly linked list is one in which all nodes are linked together by multiple links which
help in accessing both the successor node(next node) and predecessor node(previous node)
for any arbitrary node within the list. Therefore each node in a doubly linked list has two link
fields(pointers) to point to the left node(previous) and the right node(next). This helps to
traverse the list in the forward direction and backward direction. A doubly linked list is
shown in figure.

Left Data Right

In this Left link points to the predecessor node and the Right link points to the successor
node. The structure for the doubly linked list is given below.
struct node
{
72
 Data structures using C
int data;
struct node *left ;
struct node *right ;
};
typedef struct node Node;

a. Inserting a Node at the Beginning

Algorithm
Step1: Allocate memory for the new node.
Step2: Assign value to the data field of the new node.
Step3: Assign Left and Right links to NULL of the new node.
Step4: If the list is empty then assign new node to the head.
Step5: Otherwise make the Right link of the new node to point to the head node. And make
the left link of the head node to point to the new node.
Step6: Finally set the head pointer of the new node.

Head
40 20 30

10
tmp

C function for Inserting a Node at the Beginning

Node getnode( )
{
Node tmp;
tmp=(Node)malloc(sizeof(struct node));
tmpleft=NULL;
tmpright=NULL;
return tmp;
}

Insert_Node(Node head)
{
Node tmp;
tmp=getnode( );
tmpdata=ele;
if(head = = NULL)
{
head = tmp;
return head;
73
 Data structures using C
}
tmpright = head;
headleft = tmp;
return head;
}

b. Inserting a Node at the End.

Algorithm
Step1: Allocate memory for the new node.
Step2: Assign value to the data field of the new node.
Step3: Assign Left and Right links to NULL of the new node.
Step4: If the list is empty then assign new node to the head.
Step5: Otherwise traverse the list till the last node and make the Right link of the last node to
point to the new node and left link of the new node to point to the last node.

Head p tmp

10 20 30 40

C function for Inserting a Node at the End

Node getnode( )
{
Node tmp;
tmp=(Node)malloc(sizeof(struct node));
tmpleft=NULL;
tmpright=NULL;
return tmp;
}

Insert_Node(Node head)
{
Node tmp, p=head;
tmp=getnode( );
tmpdata=ele;
if(head = = NULL)
{
head = tmp;
return head;
}
While(pright!=NULL)

74
 Data structures using C
p=pright;
pright=tmp;
tmp->left=p;
}

a. Deleting a Node from the Beginning

Algorithm
Step1: If the list is empty then display message “ List is empty”.
Step2: Otherwise, make the head pointer to point to the second node.
Step3: Now make second node’s left link to NULL.
Step4: Free the first node..

tmp Head
10 20 30 40

C function for Inserting a Node at the Beginning

Delete_Node(Node head)
{
Node tmp;
if(head = = NULL)
{
printf(“ List is empty”);
return;
}
else
{
tmp = head;
head = head Rigth;
free(tmp);
headLeft=NULL
}

b. Deleting a Node at the End.

Algorithm
Step1: If the list is empty then display message “ List is Empty “.
Step2: Otherwise traverse the list till the last but one node and make the Right link of the last
but one node to point to NULL.
Step3: Free last Node.

Head tmp p

10 20 75 30 40
 Data structures using C

C function for Inserting a Node at the End

Delete_Node(Node head)
{
Node tmp, p=head;
if(head = = NULL)
{
printf(“ List is Empty”);
return;
}
while(p->right!=NULL)
{
tmp=p;
p=p->right;
}
p->right=NULL;
free(tmp);
}

Advantages
 Insertion and deletion are simple as compared to other linked lists.
 Efficient utilization of memory.
 Bidirectional traversal helps in efficient and easy accessibility of nodes.
Disadvantages
 Uses two pointer, hence there is a wastage of memory.

3. Circular Doubly Linked List

A circular doubly linked list is one which has both the successor pointer and
predecessor pointer in circular manner. That is Right link of the last node contains address of
the first node. And Left link of the first node contains the address of last node.
The objective behind consideration circular doubly linked list is to simplify the insertion and
deletion operations performed on doubly linked list. Consider the situation of the empty list.
This situation can be dispensed with by never allowing a list to be empty. It can be dispensed
with by never allowing a list to be empty. It can be accomplished by providing a special node
called head node that always remains in list. So, it is the only node that can be present in an
empty list. This head node is useful in realizing a some degree of symmetry in the linked
structure by making the list circular.

76
 Data structures using C

10 20 30
Head node

Creation of circular doubly linked list.

1. Allocate the memory to the node.

2. Set its Left and Right links to head;
3. Set its data field to Zero
4. Return the node.

C function for creating a circular doubly linked list.

Node create()
{
Node head;
head=allocate_node( )
headleft = head right =head
headdata = 0;
return head;
}

Inserting a node at the beginning

Algorithm
Step1: Allocate the memory for the new node.
Step2: Assign value to its data field
Step3: Make the Right link of the head node to point to the new node and Left link of the
new node to point to the head node. And similarly make the Right link of the new
node to point to the node immediately appearing after the head node and Left link of
this node back to the new node.

Temp

10 20 30
Head node

80
newnode

77
 Data structures using C

C function for inserting a new node at the beginning

Insert_beg(Node *head)
{
Node *newnode, *tmp;
int item;
newnode=allocate_node( );
newnodedata=item;
tmp=headRight;
headRight=newnode;
newnodeLeft=head;
newnodeRight=temp
tempLeft=newnode;
return (head);
}

Inserting a node at the End

Algorithm
Step1: Allocate the memory for the new node.
Step2: Assign value to its data field
Step3: Make the Left link of the head node to point to the new node and Right link of the
right most node to point the new node . And similarly make the Right link of the new
node to point back to the head node.

Temp

10 20 30
Head node
80
newnode

C function for inserting a new node at the beginning

Insert_beg(Node *head)
{
Node *newnode, *tmp;
int item;
newnode=allocate_node( );
newnodedata=item;
tmpRight=newnode;
newnodeLeft=tmp;
newnodeRight=head;
headLeft=newnode
return (head);
}

78
 Data structures using C
Deleting a node from the Beginning
Algorithm
Step1: If the Right link of the head node is pointing to itsef then print the message “List is
empty” and return
Step2: Make the Right link of the head node to point to the second node and the Left link of
the second node point to the head node
Step3: Free the first node and return head node.

Temp

10 20 30
Head node

C function for deleting a node from the beginning

Insert_beg(Node *head)
{
Node *tmp;
if(headRight ==head)
{
printf(“List is Empty”);
return;
}
else
{
tmp=head->Rigth;
headRight=tmpRight;
tmpRightLeft=head;
printf(“Deleted element is =%d”, tmpdata);
free(tmp);
}
}

Deleting a node from the End

Algorithm
Step1: If the Right link of the head node is pointing to itsef then print the message “List is
empty” and return
Step2: Make the Right link of the last but one node to point to the head node and similary
the Left link of the head node to point to the last but one node in the list.
Step3: Free the last node and return head node.

Temp

10 20 30
Head node

C function for deleting a node from the beginning

Insert_beg(Node *head)
79
 Data structures using C
{
Node *tmp;
if(headRight ==head)
{
printf(“List is Empty”);
return;
}
else
{
tmp=head->Left;
tmpLeftRight =head;
headLeft=tmpLeft;
printf(“Deleted element is =%d”, tmpdata);
free(tmp);
}
} Chapter 9 : Trees
Trees are one of the most important data structures in computer science. Trees are very
flexible; versatile and powerful data structures that can be used to represent data items
possessing hierarchical relationship among them. For example , consider a family geneology.
That is, the relationship between the grandfather and his descendants and in turn their
descendants and so on.
Tree: A tree is a non-linear data structure in which items are arranged in a sorted sequence.
It is used to represent hierarchical relationship existing amongst several data items. The
graph theoretic definition of a tree is : it is a finite set of one or more data items (nodes) such
that
1. There is a special data item called the root of the tree.
2. Its remaiing data items are partitioned into number of mutually exclusive subsets, each of
which is itsef a tree. And they are called subtree.

Tree
Level 0
A Root

Leve l
B C D
1

E F G I Level 2
H

Level 3
J K L

Terminal Node
or Leaf

80
 Data structures using C
Tree Terminoloy
1. Root : It is a firsrt node in the hierarchical arrangement of nodes.In the above figure
A is root node.
2. Node : Each data item in a tree is called a node. And it is a basic structure in tree.It
contains a data and pointer field.
3. Degree of a node: It is a number of subtrees of a node in a given tree. In the above
figure
a. The degree of node A is 3
b. The degree of node B is 2
c. The degree of node C is 1
d. The degree of node D is 2
e. The degree of Node E J F K L I is having 0
4. Degree of Tree : I us the maximum degree of a nodes in a given tree. In the above
figure A has degree 3 which is maximum degree of a nodes in that tree.
5. Termial nodes: A node without having children or a node with degree zero is called
terminal node or leaf node.
6. Non- Terminal node: Any node except root node whose degree is not zero is called
non termial node.
7. Siblings : The children nodes of a given parent node are alled sibling or brothers.
In the above figure E & F are the siblings of parent node B.
8. Level: The root has always level 0 then immediate childrens are at level 1 and so on.
9. Edge : A line connecting two nodes.
10. Path : It is a sequence of consecutive edges from source to destination.
11. Depth : It is the maximum level of any node in a given tree.
12. Forest: It is set of disjoint trees. By removing its root node in a tree is called forest.
13. Parent.node: It is the immediate predecessor of a node. For example B is a parent
node for its children E & F
14. Ancestor of Node:The node n1 is said to be ancestor of node n2 if and only if n1 is
father pf n2. In above fig A is ancestor of node K.
15. Descendant Node:The node n2 is descendant of node n1 if and only if n2 is a child of
n1. In the above figure J is a descendant of a node B.
Binary Tree :
Definition: A binary tree is a finite set of data items which is either empty or consists of a
single item called the root and two disjoint binary tree called the left subtree and right
subtree.
In binary tree maximum degree of any node is at most two.
A

B C

G
D E F

H I

Properties of Binary Tree:

1. The maixmum number of nodes at level i of a binary tree is 2i , where i >=0
2. The maximum number of nodes in binary tree ofdepth d is 2d-1 , where d >=1.

81
 Data structures using C
3. The total number of edges in a complete binary tree with n terminal nodes is 2(n-1).

Strictl Binary Trees: If every non-terminal node in a binary tree consist of non empty left
subtree and right subtree, then such a tree is called strickly binary tree.

B C

D E

F G

A Strictly binar tree

Complete Binary Tree: In a complete Binary tree, there is exactly one node at level 0 ,
two nodes at level 1 , four nodes at level 2 and so on. A binary tree with n nodes and of
depth d is a strictly binary tree all of whose terminal nodes are at level d.
A

B C

D E F G

H I J K E N O
L
M

Complete Binary tree

Heap Tree ( Almost complete Binary Tree) : A binary tree with n nodes and of depth
d is said to be an heap tree if it satisfy the two following conditions.
1. Each node in a tree is either at level d or d-1
2. If any node in such a tree has a right descendant at level d then all the left
descendants of that node also appear at level d only.
A

B C

D E F G

H I 82
 Data structures using C

Heap tree

Binary Search Tree : A binary tree has the property that all data elements in the left
subtree of node n are less than the contents of node n and all elements in the right subtree of
node n are greater than or equal to the content of node n, is termed as Binary search tree.

7 11

5 8 10 13

3 6

Binary search tree

Binary Tree Represenatation
Binary tree can be represented either using an static representation (Array) or using a
Dynamic representation (Linked List).
A node consists of three fields such as
 Data
 Left Child
 Right Child.
The data field contains the value to be given. The left child is a link field which contains the
address of its left node and the right node contains the address of its right node.

The Structure of node

Left Data Right

The logical representation

Struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
typedef struct node BTNODE;

Struct btnode

83
 Data structures using C
{
int data;
int left;
int right;
int father;
};
struct btnode bn[max];

Operations on Binary Trees

The basic operations to be performed on a binary are
1. Create :- It creates an empty binary tree.
2. makeBT:- It creates a new binary tree having a single node with data field set to some
value.
3. emptyBT:- It returns true If the binary tree is empty. Otherwise it returns false.
4. Lchild :- It returns a pointer to the left child of the node. If the node has no left child it
returns the null pointer.
5.Rchild:- it returns a pointer to the right child of the node. If the node has no right child it
returns the null pointer.
6. father :- It returns a pointer to the father of the node. Otherwise returns the null pointer.
7. brother(sibling):- it returns a pointer to the brother of the node. Otherwise returns the null
pointer.
8. Data:- It returns the contents of the node.
9. Tree traversal
10. Insertion of nodes
11. Deletion of nodes
12. Searching for the node
13. Copying the binary tree.

Traversal of a Binary Tree

Tree traversal is one of the most common operations performed on tree data
structures. It is a way in which each node in the tree is visited exactly ones in a systematic
manner. There are many application that essentially require traversal of binary trees.
There are three popular ways of binary tree traversal. They are .
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
1. Inoder : The inorder traversal of a non-empty binary tree is defined as follows.

1) Traverse the left subtree in inorder

2) Visit the root node. C function
3) Traverse the right subtree in inorder. Inorder( BTNODE * tree)
{
A
if(tree != NULL)
{
Inorder(treeleft);
B C printf(“%c”,treedata);
Inorder(treeright);
D E
}
G
F }

84
 Data structures using C
Inorder : DBEAFCG

2. Preorder : The Preorder traversal of a non-empty binary tree is defined as follows.

1) Visit the root node. C function

2) Traverse the left subtree in Preorder Preorder( BTNODE * tree)
3) Traverse the right subtree in Preorder. {
if(tree != NULL)
A {
printf(“%c”,treedata);
B
Preorder(treeleft);
C
Preorder(treeright);
}
D E G }
F

Preorder : ABDECFG

3. Postoder : The Postorder traversal of a non-empty binary tree is defined as follows.

1) Traverse the left subtree in Postorder

2) Traverse the right subtree in Postorder C function
3) Visit the root node. Postorder( BTNODE * tree)
A {
if(tree != NULL)
{
B C Postorder(treeleft);
Postorder(treeright);
D E G
printf(“%c”,treedata);
F }
}

Postorder: DEBFGCA
Constructing a Binary tree and perform inorder, preorder and postorder tree traversal.

85