CP&DS - All 5 Units - Notes
CP&DS - All 5 Units - Notes
Syllabus
Data Types - Variables - Operations - Expressions and Statements - Conditional
Statements - Functions - Recursive Functions - Arrays - Single and Multi-
Dimensional Arrays.
Contents
1.1 Introduction
Keywords:
Keywords are the standard words in C.
• These are basically the reserved words which have special meaning. The
meaning of keywords cannot be changed.
3) The variable name is case sensitive. A variable name can be in capital letters.
4) The length of the variable name can be any but only first 31 characters are
recognized.
6) Blank spaces or special characters, commas, use of quotes are not allowed in
the variable name.
Count,tax_id,INDEX,Xyz,brick01
Constants
Definition of constant: The specific alphabetical or numerical value that never
gets changed during the processing of the instructions is called as constant.
• The constants are given some names and are referred by the names.
• Example: The most commonly used constant is PI. Once the value to this
constant is assigned then it does not get changed.ohcorl tugi
• Generally all the letters in the name of the constant are capital.
Header Files
The header files contain standard library functions. For using these library
functions directly in the program, it is necessary to include the header file at the
beginning of the program.
stdio.h: It is standard input output header file. In this file the functions for printf,
scanf, fprintf, fscanf are defined. These functions deal with input and output
functions.
conio.h: It is Console Input Output header file. In this file the typical functions
such as clrscr() is defined. By using clrscr(), the console (output) screen gets
cleared.
alloc.h: This header file is used when a a function for allocating the
memory dynamically, such as malloc() is used in the program.
Data Types
• Data types specify the type of data we enter in our program.
• In C there are some predefined set of data types which are also called
as primitive data types.
(1) integer type: These data types are used to store whole number. (i.e. the number
without fraction).
(3) char type: This data type is used to store the character value.
(4) void type : Void data types mean no value. This data type is normally
associated with a function that return no value.
Review Questions
1. Examine the various data types in C with an example. AU: May-19, Marks 6
2. Give the length and range of the primitive data types. AU: Dec.-19, Marks 2
For handling the expressions the operators are used. C support following set of
operators -
Conditional operator :
For example A
a > b?true:false
This means if a is greater than b, if yes then the value will be true otherwise it will
be false.
Precedence of Operators
2. Within a paranthesis, the same hierarchy is operative. If there are more than one
set of paranthesis inner most parantheses will be performed first, followed by
operations within second.
e.g. a = 3/2*4+3/8+3
Stepwise evaluation to
a = 3/3*4+3/8+3 operation /
= 1*4+3/8+3 operation
= 4+3/8+30 operation
= 4+0+3 operation +
= 4+3 operation +
=7
Ex. 1.5.1 Determine the output of the following "C" statements: Assume a =
13, b = 25 and c = 5.
iv) x = c > b ?1 : 0,
As ++a is a pre increment operator the value of a is incremented by one before the
expression gets evaluated.
As b++ is a post increment operator, after expression gets incremented the value of
b becomes 26.
iv) 0
The meaning of this expression is if c> b is true then print 1 otherwise 0. As value
of c is less than b the output will be 0.
Review Questions
1. List all the operators in C with an example for each. AU: May-19, Marks 7 oals
neo insmeisje
2. Describe the various operators in C with examples and the associativity. AU:
Dec.-19, Marks 13
scanf(format specifier,variables);
Note that the format specifier is %d since the val is an integer variable. Also the
val variable is taken with the & symbol. The & (ampersand) means "address of".
Any variable is referred by its address. It is exactly similar to the way you find
your friend, either by his address or by his phone number. Thus any variable can be
obtained by its address.
printf(format specifier,variables);
Note that here there is no need of & because we are printing the value of val
variable. This value is already stored in some statement.
Even the printf can also be used to simply print the message on the console.
1. if statement
2. while statement
3. do-while statement
5. for loop
Let us discuss these control structures with the help of simple examples
1. If statement
There are two types of if statements - simple if statement and compound if
statement. The simple if statement is a kind of if statement which is followed by
single statement. The compound if statement is a kind of if statement for which a
group of statements are followed. These group of statements are enclosed within
the curly brackets.
3. do…while
The do...while statement is used for repeated execution. The difference between
do while and while statement is that, in while statement the condition is checked
before executing any statement whereas in do while statements the statement is
executed first and then the condition is tested. There is at least one execution of
statements in case of do...while. Following table shows the use of do while
statement.
Note that the while condition is terminated by a semicolon.
i) #include <stdio.h>
main ( )
int x=3;
float y=3.0;
if (x==y)
else
void main( )
int i=0;
for (; i ;)
main( )
int x=4;
while (x==1)
{
x = x-1;
- - X;
Sol. :
ii) The printf statement will not be executed. Hence there will not be any message
on the console.
iii) The printf statement will not be executed.As x=4 and the condition in while
loop gets false. The control will not enter in the loop at all. Hence there will not
be any message on the console.
Ex. 1.7.2 Explain use of "break" and "continue" keywords in "C" with suitable
example.
Sol. : The break statement is used to terminate the execution of the loop. It can
be used to break the looping of for, while, do-while and switch.
For example:
while(i<10)
printf("%d", i)
i++;
The continue statement is used to continue the execution of the control loop.
For example:
continue;
else
By above code if a[i] = b[j] simply go back and increment j. Hence if a[i] b[j] then
both a[i] and b[j] will be displayed.
Review Questions
Functions
AU: Dec.-18, May-19, Marks 13
1. Declaration of function
2. Definition of function
For example
void main( )
int a,b,c;
printf("\n Enter The two numbers");
scanf("%d %d",&a,&b);
c=a+b;
eqyt
//body of function
Function_name(Parameters);
void main( )
{
void sum ( ); /*declaration of the function*/
int a,b,c;
scanf("%d %d",&a,&b);
c=a+b;
In above example no parameter is passed and there is no return value from the
function. Hence the data type of the above function is void. The void data indicates
that the function is returning nothing or returning NULL.
We can also pass the argument as void to the function main. The parameter void to
function main indicates that there are no parameters to the function main. Thus
instead of void main() we can write void main(void)
Solution :
• The void data type indicates that the function is returning nothing.
• If the function is not returning anything from the function then its data type is
specified as void. We can also pass the argument void to the function to indicate
that there are no parameters to the function.
main( )
int a,b;
scanf("%d",&a,&b);
sum(a,b);/*call*/
{.
int c;
c=x+y;
The parameters a and b are passed. In the definition we have interpreted them as x
and y. You can take them as a, b respectively or x, y or any other names of your
own choice. It makes no difference. It takes them as a and b only. There are
actually two methods of parameter passing.
1. Call by Value.
2. Call by Reference.
In call by reference the parameters are taken by reference. Pointer variables are
passed as, parameters.
For example
main()
int a,b;
scanf("%d %d",&a,&b);
sum(&a,&b);
int c;
c=*x+*y;
printf("%d",c);
In this method the parameters are passed to the function. And this function returns
some value. If the function is returning integer value then the data type of that
function is int. Thus depending upon the type of data which is returning from the
function the data type of that function is determined. If nothing is returned form the
function then that function has a void data type.
void main( )
int a,b,c;
scanf("%d %d",&a,&b);
c = sum(a,b);
int sum()
c = a+b;
Ex. 1.8.2 Write a C program to interchange two variables without using third
variable.
Solution :
/**************************************
#include <stdio.h>
void main( )
int a=11;
int b=20;
printf("\na= %d b=%d",a,b);
a = a+b;
b = a-b;
a = a-b;
printf("\na= %d b=%d",a,b);
Ex. 1.8.3: Write a C program to get two numbers and exchange these numbers
using pass by value and pass by reference. AU: Dec.-18, Marks 7
Sol.:
#include<stdio.h>
int temp;
temp = a;
a = b;
b = temp;
int temp;
temp = *a
*a = *b;
*b= temp;
int main( )
int x, y;
scanf("%d", &x);
scanf("%d", &y);
y = %d", x, y);
printf("\nBefore Swaping x = %d and y = %d", x, y);
y = %d", x, y);
Output
Review Questions
1. Explain with a suitable example, function call by reference and function call by
value.
2. Write suitable 'C' program that creates different results after passing a
parameter by reference and by values.
AU May-19, Marks 13
Recursive Functions
AU: Dec.-18,19, Marks 13
Properties of Recursion
1. There must be at least one condition in recursive function which do not involve
the call to recursive routine. This condition is called a "way out" of the sequence
of recursive calls. The is called base case property.
2. The invoking of each recursive call must reduce to some manipulation and
must go closer to base case condition.
if(n= =0)
else
return n*fact (n-1);//on each call the computation will go closer to base case
1. Factorial
Algorithm for Factorial Function using Iterative Definition
1. prod = 1;
2. x=n;
3. while(x>0)
4. {
5. prod = prod*x;
6. X - - ;
7. }
8. return(prod);
1. if(n==0)
2. fact =1;
3. else
4. x-n-1;
5. y= value of x!;
6. fact = n* y;
This definition is called the recursive definition of the factorial function. This
definition is called recursive because again and again the same procedure of
multiplication is followed but with the different input and result is again
multiplied with the next input. Let us see how the recursive definition of the
factorial function is used to evaluate the 5!
Step 1. 5! = 5* 4!
Step 2. 4! = 4* 3!
Step 3. 3! = 3 * 2!
Step 4. 1! = 1 * 0!
Step 5. 2! = 2 * 1!
Step 6. 0! = 1.
Actually the step 6 is the only step which is giving the direct result.So to solve 5!
we have to backtrack from step 6 to step 1,collecting the result from each step.
Let us see how to do this.
Step 6'. 0! =1
Solution :
/*****************************
Program for finding out the factorial for any given number.
******************************/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void main(void)
int n,f;
int fact(int n);/* declaration*/
clrscr( );
scanf("%d", &n);
f=fact(n);/*call to fucntion*/
getch( );
int fact(int n)
int x,y;
if(n<0)
exit(0);
if(n= =0)
return 1;
x = n-1;
return(n*y);
}
Output
then
GCD = a
Consider there are two numbers 30 and 18 then we can find GCD as follows -
The above table itself illustrates the procedure for finding GCD using Euclid's
algorithm.
The algorithm in simple steps can be given as -
Step 5: Stop.
C program
/************************************
Program to find out the greatest common divisor of the two integers.
************************************/
void main(void)
int a,b,ans;
clrscr();
scanf("%d %d",&a,&b);
ans=gcd(a,b);
getch( );
int temp,ans;
return b;
else
if(a<b)
return(gcd(b,a));
else
ans = a%b;
return(gcd(b,ans));
Output
3. Fibonacci Sequence
The Fibonacci sequence is the sequence of integers
Let fib(0) = 0,fib(1) = 1,We can define the recursive definition of Fibonacci
sequence by the recursive definition :
= fib(0)+fib(1)
= 2+fib(0)+fib(1)+fib(5)
= 2+0+1+fib(5)
= 3+fib(5)
= 3+fib(3)+fib(4)
= 3+fib(1)+fib(2)+fib(4)
= 3+1+fib(2)+fib(4)
= 4+fib(0)+fib(1)+fib(4)
= 4+0+1+fib(4)
= 5+fib(4)
= 5+fib(2)+fib(3)
= 5+fib(0)+fib(1)+fib(3)
= 5+0+1+fib(3)
= 6+fib(1)+fib(2)
= 6+1+fib(2)
= 7+fib(0)+fib(1)
= 7+0+1
Hence fib(6) = 8
Here the recursive definition appears twice e.g. fib(6)=fib(4)+fib(5).
int fib(int n)
int x,y;
if(n< = 1)
return n;
x = fib(n-1);
y = fib(n-2);
return (x+y);
if(n< = 1)
return (n);
a = 0;
b = 1;
x=a;
a=b;
b=x+a;
}
return (b);
C Program
/*******************************************************
Program for computing the number in the fibonacci series at certain location.For
e.g.the sixth number in fibonacci series will be 8.The fibonacci series is 1 1 2 3 5 8
13 21 34...
**********************************************************/
/*header files*/
#include<stdio.h>
#include<conio.h>
void main(void)
int n,num;
clrscr( );
scanf("%d",&n);
num=fib(n);
getch();
}
int fib(int n)
int x,y;
if(n< = 1)
return n;
x = fib(n-1);
y = fib(n-2);
return (x+y);
Output
4. Tower of Hanoi
The problem is the "Towers of Hanoi". The initial setup is as shown in Fig. 1.9.1.
There are three pegs named as A,B and C. The five disks of different diameters are
placed on peg A. The arrangement of the disks is such that every smaller disk is
placed on the larger disk.
The problem of "Towers of Hanoi" states that move the five disks from peg A to
peg C using peg B as a auxillary.
i) Only the top disk on any peg may be moved to any other peg.
The above problem is the classic example of recursion. The solution to this
problem is very simple.
First of all let us number out the disks for our comfort
We can convert it to
Thus actually we have moved n-1 disks from peg A to C. In the same way we can
move the remaining disk from A to C.
'C' Program
/******************************************************
Program For Towers of Hanoi. The input will be the number of disks for which the
program should operate.
*******************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void main(void)
int n;
scanf("%d",&n);
towers(n,'A','C', 'B');
getch();
if(n = =1)
return;
towers(n-1,from,aux,to);
towers(n-1,aux,to,from);
Output
Solution :
Here m = 2, n = 1
= A (1, 3) …. (1)
A (2, 1) = 5
Solution:
= A(0,A(m-1,1))
= A(0,A(0,1) …. (1)
A(0,1) = n+1=2
C Function
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
count++;
if (m = = 0)
}
return (n + 1);
if (n = = 0 && m>0)
int main( )
int m, n;
scanf("%d", &m);
scanf("%d", &n);
int count = 0;
Output
Enter value of m: 2
Enter value of n: 1
Review Question
1. Explain recursion and write a C program to print the first 'n' numbers in the
Fibonacci series using recursion.
Arrays
AU May-19, Marks 7
Arrays can be defined as a set of pair-index and the value. Two basic operations
that can be performed on arrays are: Storing of data at desired location or index
and retrieving data from desired location (index).
Advantages of Arrays
1. Elements can be retrieved or stored very efficiently in array with the help of
index or memory location.
2. All the elements are stored at continuous memory locations. Hence searching
of element from sequential organization is easy.
Disadvantages of Arrays
2. For storing the data large continuous free block of memory is required.
Syntax
Here 'a' is the name of the array inside the square bracket size of the array is
given. This array is of integer type i.e. all the elements are of integer type in array
'a'. Similarly arrays may be of user defined type, called as array of structure C
supports both one dimensional and multidimensional arrays.
1. Initialization
• It is possible to initialize an array during declaration only. For example
• The list of values, enclosed in braces {}, separated by commas, provides the
initial values for successive elements of the array.
• If there are fewer initializers than elements in the array, the remaining elements
are automatically initialized to 0. For example,
would declare, define, and initialize an array b of 5 elements. Here only the
dimension is omitted; the brackets [] remain to indicate that b is in fact an array.
For example
Now let us see how to handle this array. We will write a simple C program in
which we are simply going to store the elements and then we will print those
stored elements.
C Program
#include<stdio.h>
#include<conio.h>
main( )
int a[10],index;
clrscr( );
For example
int a[10][10];
By this allocation the memory block of 10 x 10 =100 is getting created. The nested
for loops can be effectively used to access all the elements of an two dimensional
array. We will take a sample example to explain this idea. bon atomolo orb
for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
scanf("%d",&a[i][j]);
Again
Since now value of i and j has reached to 2 the scanning procedure will get
terminated as condition is i<=2 and j<=2. Thus all the elements from a[0][0] to
a[2][2] get scanned.
Ex. 1.10.1 How two dimensional arrays are created in C? Write a C program to
generate a population survey having citizen's record stored as a collection of
year-wise population.
#include <stdio.h>
int main( )
int arr[3][3],i,j;
for (i=0;i<3;i++)
for (j=0;j<3;j++)
{
printf("\n Enter the population for Year#%d", (j+1));
scanf("%d",&arr[i][j]);
printf("\n-----------------------\n");
for(i=0;i<3;i++)
for (j=0;j<3;j++)
printf("\t%dL", arr[i][j]);
printf("\n");
return 0;
Simple Programs
• Program 1.11.1: Sorting Program
/*****************************
*****************************/
/* Header Files*/
#include<stdio.h>
#include<conio.h>
#include <process.h>
/*Declaration*/
int i,j,m,temp;
for(i=0;i<n-1;i++)
for(j=0;j<n;j++)
if(a[j]>a[j+1])
{ temp=a[j];
a[j]=a[j+1];
alj+1]=temp;
}
}
for(i=0;i<n;i++)
printf("\n\t%d",a[i]);
void main( )
int a[20],i,n;
int ch;
clrscr( );
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubblesort (a,n);
getch( );
20
50
40
10
10
20
30
40
50
/***********************************************
************************************************/
#include<stdio.h>
#include<conio.h>
#define MAX 10
int a[MAX],n,i;
/*
Input :none
Output:none
Called By: main
Calls:none
*/
void create( )
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
/*
Input:none
Output:none
Called By:main
Calls:none
*/
void display( )
for(i=0;i<n;i++)
printf("\n%d",a[i]);
/*
Output:the status
Called By:main
Calls:none
*/
search(int k)
for(i=0;i<n;i++)
if(a[i]==k)
return 1;
return 0;
void main( )
int status,key;
clrscr( );
create( );
display( );
scanf("%d", &key);
status=search(key);
if (status = =1)
else
getch();
Output
100
1000
10000
10
1
100
1000
10000
100
1000
10000
10
100
1000
10000
*****************************************/
#include<stdio.h>
#include<conio.h>
#define MAX 5
void main( )
int m1,n1,m2,n2;
int choice;
int i,j;
char ans='y';
void Addition(int a[MAX] [MAX], int m1,int n1,int b[MAX] [MAX], int c[MAX]
[MAX]);
void Subtraction(int a[MAX] [MAX], int m1,int n1,int b[MAX] [MAX], int
c[MAX] [MAX]);
scanf("%d",&m1);
scanf("%d", &n1);
for(i=0;i<m1;i++)
for(j=0;j<n1;j++)
scanf("%d",&a[i][j]);
scanf("%d", &m2);
scanf("%d", &n2);
for(i=0;i<m2;i++)
for(j=0;j<n2;j++)
scanf("%d",&b[i][j]);
do
{
printf("\n\t Main Menu");
scanf("%d", &choice);
switch(choice)
Addition(a,m1,1,b,c);
Print_Matrix(c,m1,n1);
break;
Subtraction(a,m1,n1,b,c);
Print_Matrix(c,m1,n1); -
break;
if(n1= =m2)
Multiplication(a,m1,n1,b,m2,n2,c);
Print_Matrix(c,m1,n2);
}.
else
printf("\n Multiplication is not possible");
break;
Transpose(a,m1,n1,c);
Print_Matrix(c,m1,n1);
break;
ans = getch( );
} while(ans= ='y');
getch( );
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
printf("%d",c[i][j]);
printf("\n");
}
void Addition(int a[MAX] [MAX], int m1,int n1,int b[MAX][MAX], int c[MAX]
[MAX])
int i,j;
for(i=0;i<m1;i++)
for(j=0;j<n1;j++)
c[i][j]=a[i][j]+b[i][j];
void Subtraction(int a[MAX] [MAX], int m1,int n1,int b[MAX] [MAX], int
c[MAX][MAX])
int i,j;
for(i=0;i<m1;i++)
for(j=0;j<n1;j++)
{
c[i][j]=a[i][j]-b[i][j];
int i,j,k;
for(i=0;i<m1;i++)
for(j=0;j<n2;j++)
c[i][j]=0;
for(k=0;k<m2;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
int i,j;
for(i=0;i<m1;i++)
{
for(j=0;j<n1;j++)
c[i][j]=a[j][i];
Output
123
456
789
111
222
333
Main Menu
4. Transpose
234
678
10 11 12
Ex. 1.11.1: Write a C program to get a 4 digit number and display the reverse of
the same number.
AU: Dec.-18, Marks 6
Sol.:
#include <stdio.h>
int main( )
int n, reverse = 0;
scanf("%d",&n);
while (n!= 0)
reverse = reverse * 10
n = n/10;
return 0;
Ex.1.11.2 Write a C program to find the following, where A, B and C are the
matrices whose orders are M*N, M*N and N*N respectively. A = A+B*C
#include<stdio.h>
int main( )
int A[3][3],B[3][3],C[3][3],Temp[3][3],i,j,k,m,n;
scanf("%d %d",&m,&n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d", &A[i][j]);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&B [i][j]);
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d", &C[i][j]);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
Temp[i][j]=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
{
Temp[i][j]=Temp[i][j]+B[i] [k]*C[k][j]; //performing B*C
for(i=0;i<m;i++)
for(j=0;j<n;j++)
for(i=0;i<m;i++)
for(j=0;j<n;j++)
printf("%d ",A[i][j]);
printf("\n");
}
Two Marks Questions with Answers
Ans. : Primitive data types in C are the fundamental data types such as int, float,
char and void.
The int data type is for representing the whole number values.
Ans. :
Ans. : • The void data type indicates that the function is returning nothing.
• If the function is not returning anything from the function then its data type is
specified as void.
Ans. : Array is used to store the elements of same data type. For storing the strings
- the arrays is used.
char a="hello";
Ans.
Ans.
Nested loops mean loops within the loops. For example for nested, the loop is
given below
for (i=0;i<n;i++)
for(j=0;j<n;j++)
printf("It's My Life!!!");
For example:
30
scanf("%d", &a[i]);
Ans. :
do
statements;
For example
count = 1
do
Ans.: Array is simply a collection of elements which are of same data type.
Mainly we can perform following operations on an array-
#include <stdio.h>
#include <conio.h>
main( )
clrscr( );
}
Q.11 List the primary data types in C.
Ans. : Static variables are those variable that retain their values even after they
come out of the scope.
For example
#include<stdio.h>
int fun( )
count++;
return count;
int main( )
printf("\n%d",fun());
printf("\n%d",fun());
printf("\n%d",fun());
printf("\n%d",fun());
return 0;
Output
4
Q.14 Write a C program to get a paragraph of text as input.
AU: Dec.-19
Ans. :
#include<stdio.h>
int main( ) {
char para[100];
return 0;
AU: May-19
data_type array_name[table][row][column];
Ans. : In row-major order, consecutive elements of the rows of the array are
contiguous in memory; in column-major order, consecutive elements of the
columns are contiguous.
The difference between row-major and column-major order is simply that the order
of the dimensions is reversed.
C Programming - Advanced Features
Unit II
Chapter - 2
C Programming – Advanced Features
Syllabus
Structures-Union - Enumerated Data Types - Pointers: Pointers to Variables,
Arrays and Functions - File Handling - Preprocessor Directives.
Contents
2.1 Structures …….. May-17, Dec.-18,19, …….. Marks 16
Structures
AU May-17, Dec.-18,19, Marks 16
1. Definition
Definition: A structure is a group of items in which each item is defined by some
identifier. These items are called members of the structure. Thus structure is a
collection of various data items which can be of different data types.
struct name {
member 1;
member 2;
member n;
};
Example :
struct stud {
int roll_no;
char name[10];
float marks;
};
Using typedef
An alternative to using a structure tag is to use the structure tag is to use the
typed definition in C. For example
typedef struct {
int roll_no;
char name[10];
float marks;
} stud;
The word stud represents the complete structure now. So whenever the word
stud will appear there ever you can assume the complete structure. The stud will
act like a data type which will represent the above mentioned structure. So we
can declare the various structure variables using the tag stud like this-
stud stud1,stud2;
struct student {
int roll_no;
char name[10];
float marks;
}s1;
int roll_no;
char name[10];
float marks;
};
int roll_no;
char name[10];
float marks;
}S;
S, s1;
Ex. 2.1.1 Write a C program to initialize a structure and retrieve the values.
Sol. :
/***********************************************
This Program is for assigning the values to the structure variable. Also for
retrieving the values.
**************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct student {
int roll_no;
char name[10];
float marks;
void main(void)
clrscr();
scanf("%s", stud1.name);
scanf("%f",&stud1.marks);
printf("\n-------");
Enter the roll number 1
1 Shrinath 91.44
Ex. 2.1.2 Write a C program to represent a complex number using structure and
add two complex numbers.
Sol.:
#include<stdio.h>
#include<conio.h>
float real;
float img;
}C;
void main()
{
C x,y,z;
clrscr();
scanf("%f",&x.real);
toute lebegy
scanf("%f",&x.img);
scanf("%f",&y.real);
scanf("%f",&y.img);
z.real=x.real+ y.real;
z.img=x.img+ y.img;
getch( );
}
4. Array of Structures
Definition: Structure is used to store information of one particular object and if
one has to store large number of such objects then array of structure is used.
For example - If there are 10 students in a class then the record of each student is
in structure and 10 such records can be stored in array of structure.
The program is for storing the record of all the students in a particular class.
/*************************************
Program for maintaining the students' database using structure. The program
shows the use of typedef for a structure variable
************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int roll_no;
char name[20];
int marks;
} stud;
printf("\n------------");
printf("\n-------------");
for(i=0;i<n;i++){
printf("\n%d %s %d",s[i].roll_no,s[i].name,s[i].marks);}
printf("\n--------------“);
getch( );
}
Output
Ex. 2.1.3 Database of 100 students is required to be stored. Each student record
contains fields such as roll no, name of student, total marks. Write a program in
'C' to input the database of 100 students with fields mentioned above using:
Sol. :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct student
Int roll_no
char sname[20];
int Total_Marks;
}s[100];
int r[100],m[100];
char n[100][20];
void main( )
int i,j,choice;
clrscr( );
scanf("%d", &choice);
switch(choice)
scanf("%d", &r[i]);
printf("\n Enter name of student: ");
scanf("%s",n[i]);
scanf("%d",&m[i]);
j=0;
for(i=0;i<100;i++)
obtained*/
printf("\n %d %s %d",r[j],n[j],m[j]);
break;
scanf("%s",s[i].sname);
printf("\nEnter marks: ");
scanf("%d", &s[i].Total_Marks);
j=0;
for(i=0;i<100;i++)
if(s[i].Total Marks>s[j].Total_Marks)
j=i;
printf("\n %d %S %d",s[j].roll_no,s[j].sname,s[j].Total_Marks);
break;
Ex. 2.1.4 Write down only declaration in 'C' for : A database of 100 students
each with information as roll no, name, address and marks using: i) Only arrays
ii) Array of structures.
Sol. : i) Only arrays:
struct student
float marks;
}s[100];
Ex. 2.1.5 Develop a structure to represent planet in the solar system. Each
planet has fields for the planet's name, its distance from the sun in miles and
the number of moons it has. Write a program to read the data for each planet
and store. Also print the name of the planet that has less distance from the sun.
Sol.
Following table shows planets in the solar system, their distances from sun in
miles and number of moons.
C Program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
char name[20];
int distance;
int no_of_moons;
}Solar;
Solar Planet[10];
void main(void)
{
int n, i, min dist, position;
//clrscr( );
n = 9;//number of planets
scanf("%s", Planet[i].name);
scanf("%d", &Planet[i].distance);
scanf("%d", &Planet[i].no_of_moons);
printf("\n----------");
printf("\n----------------");
printf("\n-----");
min_dist Planet[0].distance;
position = i
printf("\n The planet having less distance from the Sun is %s", Planet
[position].name);
Output
Ex. 2.1.6 Define a structure to store details of 10 bank customers with customer
name,account no, balance, and city. Write a C program to store the details of
customers in the bank, access and print the customer details for a specified
account no.
Sol. :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
char name[20];
int balance;
char city[20];
}cust;
cust c[10];
int main( )
int n,i;
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &c[i].account_no);
scanf("%s",c[i].name);
scanf("%d", &c[i].balance);
scanf("%s",c[i].city);
printf("\n--------");
printf("\n-------------");
for(i=0;i<n;i++)
{
c[i].city);
return 0;
Output
Ex. 2.1.7: Write a C program to get 10 student details using structures from the
user and display these details on the screen.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int roll_no;
char name[20];
int std;
}cust;
cust c[10];
int main()
int i;
for(i=0;i<10;i++)
scanf("%d",&c[i].roll_no);
scanf("%s",c[i].name);
scanf("%d", &c[i].std);
scanf("%s",c[i].address);
}
printf("\n---------------“)
printf("\n-------");
for(i=0;i<10;i++)
return 0;
Ex. 2.1.8: Explain structures and write a C program using structures to store
roll_num, name, marks in 10 subjects of 100 students. Calculate the grade of
each student and print the student information. The grades are calculated as
follows -
Sol. :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct student
int roll_no;
char sname[20];
int Marks[10];
char *grade;
}s[100];
void main( )
int i,j;
for(i=0; i<100;i++)
scanf("%d", &s[i].roll_no);
scanf("%s",s[i].sname);
for(j=0;j<10;j++)
{
printf("\nEnter marks: ");
scanf("%d", &s[i].Marks[j]);
for(j=0;j<10;j++)
int total_marks = 0;
s[i].grade = "O";
s[i].grade = "A+";
s[i].grade ="A";
s[i].grade = "B+";
s[i].grade = "B";
else
s[i].grade = "RA";
printf("\n %d\t%s\t%s",s[i].roll_no,s[i].sname,s[i].grade);
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct bdate {
int day;
int month;
int year;
}dt;
struct address {
char street[10];
char city[10];
}add;
struct student {
int roll_no;
char name[10];
} std;
void main(void)
clrscr();
scanf("%d", &std.roll_no);
scanf("%s",std.name);
scanf("%s %s",std.add.street,std.add.city);
printf("\n----------");
printf("\n %d %s",std.roll_no,std.name);
printf("%d-%d-%d ",std.dt.month,std.dt.day,std.dt.year);
}
Ex. 2.1.9 Write a C program with appropriate structure definition and variable
declaration to store information about an employee, using nested structures.
Consider the following fields like ENAME, EMPID, DOJ(Date, Month, Year) and
Salary (Basic, DA, HRA)
Sol. :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct JoiningDate
int Date;
int Month;
int Year;
};
struct Amount
float Basic;
float DA;
float HRA;
};
struct Employee {
int EMPID;
}Emp;
void main(void)
scanf("%s",Emp.ENAME);
scanf("%d", &Emp.EMPID);
scanf("%d", &Emp.DOJ.Date);
scanf("%d", &Emp.DOJ.Month);
scanf("%d", &Emp.DOJ.Year);
scanf("%f",&Emp.Salary.Basic);
scanf("%f",&Emp.Salary.DA);
scanf("%f",&Emp.Salary.HRA);
Emp.DOJ.Date,Emp.DOJ.Month, Emp.DOJ.Year);
Emp.Salary.Basic,Emp.Salary. DA,Emp.Salary.HRA);
Output
Enter Date: 10
Enter Month: 10
Enter Year: 2012
1000.000000(HRA)
1. One can pass the member of the function like an ordinary variable to the
function.
/*******************************************************
********************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int roll_no;
char name[20];
float marks;
}student;
student st;
void main( )
char ans;
clrscr( );
do
clrscr( );
scanf("%d", &st.roll_no);
scanf("%s",st.name);
scanf("%f",&st.marks);
print_rec(st.roll_no,st.name, st.marks);
ans=getche();
}while(ans= ='y');
/**********************************************
Output:nones
Called By:main
***********************************************/
printf("\n %d %S %f",r,n,m);
}
Output
1 aaa 76.000000
/***********************************************
************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int roll_no;
char name[20];
float marks;
}student;
student st;
void main( )
char ans;
clrscr( );
do
clrscr( );
scanf("%d", &st.roll_no);
scanf("%s",st.name);
scanf("%f",&st.marks);
print_rec(st);
ans=getche();
}while(ans= ='y');
}
/***************************************************
Output:none
Called By:main
***************************************************/
printf("\n %d %s %f",st.roll_no,st.name,st.marks);
Output
1 aaa 76.000000
Union
AU: May-19, Marks 13
Definition: Union is a user defined data structure which is just similar to structure.
It is used to store members of different data types.
'C' allows another type of structure, the union, which allows the variables to be
interpreted in several different ways.
For example: Consider a structure giving the details of student. Such as his name,
roll number and standard. The categorisation of the standard will be primary or
pre-primary. The primary standard will be denoted by 1, 2 till 4 standards. The
pre-primary standard will be denoted by "Play group", "Jr. K.G.", and "Sr. K.G."
respectively.
struct student
char name[20];
int roll_no;
union {
int primary;
}std;
};
For example : If a record of student having name - Rama, roll number as 5 and he
is in 3rd standard. It will be stored in the following manner.
Similarly a record having name Shyam roll number 2 and standard as Jr. K.G will
be mapped as
The structure and the union both are very similar data structures. Both are meant
for storing the various member variables of different data types. But the only
difference between the two is that various members of the structure stored at
various is memory locations. And in case of unions, all the members are stored at
the same memory location and that is why only one member can be accessed at a
time by the unions variable. You just observe the above given example, the union
is defined for the standards primary and pre-primary. Note that the same location
is utilized to store the data of different data types. But at a time you can access
only one data type of union. In case of above example, the memory location for
std will hold either primary data or pre-primary data. The dot operators (exactly
like the structure) are used to access the members of the union.
Ex. 2.2.1 Define union having array of characters of size 2, one integer and one
float as its elements.
Sol. :
union {
char a[2];
int i;
float j;
};
1. Difference between Structure a
Ex. 2.2.2 Illustrate the representation of structure and union for an employee
record having empid, emp-name, DOB, basic pay, allowances, deductions,
grosspay and netpay. Examine their memory allocation.
AU May-19, Marks 13
Sol. : Structure allocates different memory locations for all its members while
union allocates common memory location for all its members. The memory
occupied by a union will be large enough to hold the largest member of the union.
#include<stdio.h>
union Employee
int empid;
char empName[30];
char dob[20];
float basic_pay;
float allowances;
float deduction;
float grosspay;
float netpay;
};
int main( )
union Employee E;
scanf("%d", &E.empid);
scanf("%s", &E.empName);
scanf("%s", &E.dob);
printf("\nEnter Employee basic_pay: ");
scanf("%f",&E.basic_pay);
scanf("%f",&E.allowances);
scanf("%f",&E.deduction);
E.grosspay = (E.basic_pay+E.allowances);
E.netpay = (E.basic_pay+E.allowances);
- E.deduction;
printf("\n\nEmployee Id : %d",E.empid);
return 0;
Output
Employee Name :
Employee DOB:
Note that only one memory location will be used by union at a time, rest of the
locations are treated as garbage. But in structure it is not so, for each member the
structure will allocate the separate memory location
#include<stdio.h>
struct Employee
int empid;
char empName[30];
char dob[20];
float basic_pay;
float allowances;
float deduction;
float grosspay;
float netpay;
};
int main( )
struct Employee E;
scanf("%d", &E.empid);
scanf("%s", &E.empName);
scanf("%s", &E.dob);
scanf("%f",&E.basic_pay);
scanf("%f",&E.allowances);
printf("\nEnter deductions: ");
scanf("%f",&E.deduction);
E.grosspay (E.basic_pay+E.allowances);
- E.deduction;
return 0;
Output
• The syntax is
• For example :
• Here fruit is the name given to the set of constants. If there is no value given to
the sequence then by default the first value in the list is 0. For instance here Mango
= 0, Orange = 1, Banana = 2, Grapes = 3 and Guava = 4. We can reassign these
values as well.
• For instance :
Mango= 2, Orange = 3
• The main advantage of enum is that even if we do not initialize the constants,
each one would have a unique value. The first would be zero and the rest would be
one more than the previous one.
• Let us understand the use of enumerated data type with the help of following C
program -
C Program
#include<stdio.h>
#include<stdlib.h>
void main( )
getch( );
Output
Mango: 0
Orange: 1
Banana: 2
Grapes: 3
Guava: 4
We can declare some variable of enum type and assign the integer constants to this
variable. Just go through the following program and its output:
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void main( )
clrscr( );
points=Mango;
getch( );
Output
Review Questions
2. Explain the data type enumeration? What are the various operations that can
perform on enumeration?
Pointers
AU: May-17, Marks 8
1. Pointers to Variables
Definition : Pointer is a variable that represents the memory location of some
other variable. The purpose of pointer is to hold the memory location and not the
actual value.
2. Advantages of Pointers
Following are some advantages of using pointer that illustrates its significance.
7. Pointers help to build the complex data structures such as linked list, stack,
queues, tree, graphs etc.
3. Initialization
Once the pointer variable is declared then it can be used further. In the sense we
can assign some value to it. But note that the pointer variable is basically used to
store some address of the variable which is holding some value.
Consider,
Line 5- > b=*ptr;/*getting value from address in ptr and storing it in b*/
Here we have used two important operators * and &. The * means 'contents at
the
On Line 1 and Line 2 we have declared the required variables out of which ptr is a
pointer variable and variables a and b are our normal variables. On Line 3 we have
assigned value 10 to variable a. The Line 4 tells us that address of variable a is
stored in a pointer variable ptr. And on Line 4 we have written that in ptr variable
we have stored some address and at that address whatever value is stored, store
that value in variable b. That means at ptr we have stored address of variable a.
Then at the address of a whatever is a value we have to store that value in
variable b. This can be illustrated by following Fig. 2.5.1.
We can declare pointer variables of various types such as int, char, double etc.
int *iptr;
char *cptr;
float *fptr;
The iptr will store the address of a variable which is of type integer, similarly cptr
will store the address of a variable which is of character type and so on.
Similarly we cannot assign one variable of some data type to a pointer variable of
different type
For example,
int *ptr;
float a,b;
a=3.14;
b=10.51;
#include<stdio.h>
#include<conio.h>
void main( )
int *ptr;
int a,b;
clrscr();
Output
a= 10
ptr= 65524
ptr=10
b= 10
Program Explanation :
The following program illustrates the concept of & and * in more detail
#include<stdio.h>
#include<conio.h>
void main()
int *ptr;
int a,b;
clrscr();
a=10;
b=20;
}
ptr=&a;
b=*ptr;
a= %d, b=%d",a,b);
getch();
Output
a=10,b=10
ptr = 65522
&ptr = 65524
*ptr = 10
*(&ptr) = 65522
Address of a is &a= 65522
In above program there are 2 variables and 1 pointer variable. The values stored
in these variables are - Refer Fig. 2.5.2.
Key Point: Whenever we want to store address of some variable into another
variable, then another variable should be of pointer type.
Ex. 2.5.1
1) (*p1)++
2) - - (*p2)
3) *p1 + (*p2)- -
4) ++(*p2) - *pl
5) *p1 + *p2
6) - (*p1) + *p2
Sol. :
1) (*p1) ++
Ans: 10
2) -- (*p2)
Ans : 9
3) *p1 + (* p2) -
Ans: Output 20
Explanation: Here value at p1 and value at p2 are added and then value at p2 is
decremented by 1.
so* p2 = 9
4) ++ (*p2) - * p1
Ans: Output = 1
5) *p1 + *p2ola
Ans. Output = 20
Ans: Output = 19
i) int p, *p;
ii) int q, *p = Ɛ q;
v) char *p;
Sol. :
i) int p, *p: This statement will cause a compiler error for multiple declarations of
variable p.
ii) int q, *p = & q: The variable p will act as an interger pointer and will hold the
address of q. Hence the result of q and *p will be the same.
iii) int (* p) ++: The (*p)++ means increment the value of p by 1. But at the
declaration, if we try to increment *p then it will generate syntax declaration
error.
iv) int p + + : The p++ means increment the value of p by 1, but during declaration
we cannot increment the value of variable. A declaration syntax error will be
generated.
v) char *p;: The *p will be a character pointer that means it will store the address
of character variable.
vi) int a = *p + 5; : If *p will store some value then variable a will store the value
of *p + 5.
5) The pointer can be used as a scalar data type as well as the derived data type.
Ex. 2.5.3 Given the following declarations: int m = 50, n = 50, int *p1 = Ɛ m, *p2 =
Ɛ n; What is the value of each of the following expressions?
i) (* p1) ++;
ii) -- (* p2);
Explanation: Here value at p1 and value at p2 are added and then decremented
by 1.
5. Pointer Arithmetic
Basic Concept: Pointer arithmetic is a method of calculating the address of an
object with the help of arithmetic operations on pointers.
Let
int *ptr1,*ptr2;
int x;
But here is a list of some invalid operations. These operations are not allowed in
any C program -
Now consider
int *ptr;
This is a pointer variable which is of integer type. This allocates the memory of 2
bytes for each such variable. If there are 10 integer pointers then total 20 bytes of
memory block will be reserved.
Consider a block in memory consisting of ten integers in a row. That is, 20 bytes of
memory are set aside to hold 10 integers.
Now, let's say we point our integer pointer ptr at the first of these integers.
Furthermore lets say that integer is located at memory location 100 (decimal).
What happens when we write :
ptr + 1;
it points to an integer it adds 2 to ptr instead of 1, so the pointer "points to" the
next integer, at memory location 102. The same goes for other data types such as
floats, doubles, or even user defined data types such as structures. This is
obviously not the same kind of "addition" that we normally think of. In C it is
referred to as addition using "pointer arithmetic".
int *ptr;
ptr = &my_array[0];
my_array
Thus there are two ways by which array element can be accessed -
Then we can print all the elements of an array. This is illustrated by following
program -
#include <stdio.h>
int my_array[] = {1,25,-17,4,45,10};
int *ptr;
int main(void)
int i;
ptr = &my_array[0]; /* point our pointer to the first element of the array */
printf("\n\n");
return 0;
Compile and run the above program and carefully note lines A and B and that the
program prints out the same values in either case. Also observe how we
dereferenced our pointer in line B, i.e. we first added i to it and then
dereferenced the new pointer. Thus the output will be -
Output
Now, change it to :
Try once more. Each time try and predict the outcome and carefully look at the
actual outcome. Again the same result will be achieved.
In C, instead of
ptr = &my_array[0];
we can write :
ptr = my_array;
to achieve the same result. This means that the name of an array is a pointer.
Key Point: "The name of the array is the address of first element in the array".
Using pointer arithmetic (increment or decrement operator) we can access the
subsequent elements of the array.
Ex. 2.5.4 Write a C program using pointer for searching the desired element
from the array.
Sol. :
#include<stdio.h>
#include<conio.h>
void main( )
clrscr( );
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d", &key);
for(i=0;i<n;i++)
if(*ptr==key)
break;
else
getch( );
Output
10
20
30
40
50
Ex. 2.5.5 Write a program using pointer to compute the sum of all elements
stored in any array.
Sol. :
#include<stdio.h>
void main()
int a[ ]={10,20,30,40,50};
int sum=0;
int n=5;
for(int i=0;i<5;i++)
sum=sum+(*(a+i));
printf("%d", sum);
Ex. 2.5.6 If we declare an array a [i] [j] and p is pointer to first row find out
i) Pointer to ith row
Sol. :
i)
void main( )
int *ptr;
for(int j=0;j<3;j++)
ptr=&a[0][j];
printf("%d", *ptr);
ii)
void main( )
int *ptr;
ptr=&a[0][0];
printf("%d", *ptr);
iii)
void main( )
int *ptr;
ptr=&a[1][2];
printf("%d", *ptr);
iv)
void main( )
int *ptr;
for(int i=0;i<2;i++)
for(int j=0;j<3;j++)
ptr=&a[i][j];
printf("%d", *ptr);
printf("\n");
printf("%d", *(*(*(t+2)+1)+3));
2) char *cp;
int *ip;
cp=(char *)0×100;
ip=(int *)cp;
ip++;
cp++;
Sol. :
1) The output is 5 because, the elements are arranged in two rows and four
columns. And there will be 3 such blocks. The arrangement of elements will be
*(t + 2) = {{1, 6, 2, 4}, {0, 7, 9, 5}}
*(*(*(t+2)+1)+3) = 5.
2) The address assigned to cp variable is 100. The same base address i.e. 100 is
assigned to ip. The cp represents character pointer and ip represents interger
pointer. The size of character variable is 1 byte and size of interger variable is 2
bytes.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 10
void main(void)
char name[size];
char *i;
clrscr();
gets(name);
i=name;
while(*i!= '\0')
printf("%c", *i);
i++;
getch();
Output
What is Your name? Parth
Now we will use the pointer arithmetic and copy the contents of one string to
another using pointer variable.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void main(void)
char str2[20];
clrscr();
while(*ptr1 != '\0')
*ptr2++= *ptr1++;
}
Output
In above program, there are two strings str1 and str2. The string str1 contains a
string "Hello India"
We have taken two pointer variables: ptr1 and ptr2. The starting address (base
address) is assigned to ptr1.
ptr1=str1;
Now we can get the same string "Hello India" in ptr1. Now we have set the ptr2 as
a pointer to second string str2.
ptr2 = str2;
There is nothing in str2, so we will copy the contents of first string to second
string using pointers
while(*ptr1 != '\0')
*ptr2++= *ptr1++;
}
*ptr2 = '\0';
Key Point: We can store one string in a pointer variable of character type. i.e
char *ptr="Hello";
is possible. We can apply pointer arithmetic to access the characters within the
string.
Sol. :
#include<stdio.h>
#include <conio.h>
void main()
char str1[20],str2[10];
char *ptr1,*ptr2;
gets(str1);
gets(str2);
ptr1=str1;
ptr2=str2;
*ptr1++;
while(*ptr2!= '\0')
*ptr1= *ptr2;
*ptr2++;
*ptr1++;
*ptr1='\0';
getch();
Output
Ex. 2.5.9 Write a "C" function using pointer for string reversal.
void main()
{
char s1[10],s2[10];
clrscr();
scanf("%s",s1);
char *i=s1;
char *j=s2;
while(*i!= '\0')
i++;
*j++=*i--;
*j='\0';
getch();
Ex. 2.5.10 Write pseudo C routine using pointers for checking whether a given
string is palindrome.
p = q = a;
while (* q!= '10')
q++;
q --;
while (p < q)
if (* p! = *q)
flag = 1;
p++; q--;
if (flag ==0)
else
Ex. 2.5.11 Write a C program to implement any four string handling functions
using functions and pointers.AU May-17, Marks 8
Sol. :
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int main(void)
{
int choice;
char ans='y';
do
scanf("%d", &choice);
switch(choice)
case 1:str_len();
break;
case 2:str_concat();
break;
case 3:str_copy();
break;
case 4:str_reverse();
break;
void str_len()
char *ptr,str[10];
int len=0;
scanf("%s", str);
ptr=str;
while(*ptr!='\0')
*ptr++;
len++;
void str_concat()
char *ptr1,*ptr2;
scanf("%s", str1);
printf("\n Enter second string ");
scanf("%s",str2);
ptr1=str1;
ptr2=str2;
*ptr1++;
while(*ptr2!='\0')
*ptr1=*ptr2;
*ptr2++;
*ptr1++;
*ptr1='\0';
void str_copy()
char str1[10],str2[20];
scanf("%s", str1);
printf("\n The first string i.e. str1 is: ");
while(*ptr1 != '\0')
*ptr2++ = *ptr1++;
}.
void str_reverse()
char str1[10],str2[10];
scanf("%s", str1);
char *ptr1=str1;
char *ptr2=str2;
while(*ptr1!= '\0')
ptr1++;
ptr1--;
while(ptr1>=&str1[0])/*copying the characters*/
*ptr2='\0';
7. Pointer to Function
The pointer to the function means a pointer variable that stores the address of
function. The function has an address in the memory same like variable. As
address of function name is a memory location we can have a pointer variable
which will hold the address of function. The data type of pointer will be same as
the return type of the function. For instance: if the return type of the function is
int then the integer pointer variable should store the address of that function.
Syntax
For example,
float (*fptr)(float);
Here fptr is a pointer to the function which has float parameter and returns the
value float. Note that the parenthesis around fptr otherwise the meaning will be
different. For example,
float *fptr(float);
This means fptr is a function with a float parameter and returns a pointer to float.
float fun(float);
Thus
#include<stdio.h>
#include<conio.h>
void main()
void display(float(*)(int),int);
float area(int);
int r;
scanf("%d", &r);
float area(int r)
return (3.14*r*r);
Output
Program Explanation
The function display calls the function area through pointer variable fptr. Thus
fptr is actually a pointer to the function area. As function area returns the float
value we have the pointer as of float type.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main()
int *m;
*m=5;
clrscr();
printf("%d", *m);
fun(m);
printf("%d",*m);
*x=10;
Output
10
i) int a, *b = Ɛa ii) int p, *p iii) a = (float *)Ɛ x iv) int (*fun) ().
Sol. :
iv) This is pointer to a function. This function returns the pointer to integer value.
Ex. 2.5.13 Write a "C" function using pointers to multiply two matrices and
return the resultant matrix to calling function.
int *mul(int m,int n,int (*a) [3], int (*b)[3], int (*c)[3])
int i,j,k;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
*(*(c+i)+j)=0;
for(k=0;k<m;k++)
*(*(c+i)+j)= *(*(c+i)+j)+((*(*(a+i)+k))*(*(*(b+k)+j)));
return *(c+0);
Review Questions
1. What is a pointer variable? Explain declaration, initialization and accessing a
pointer variable with an example.
2. What is the data type pointer in C? How do we declare the pointer? Give any
four advantages of using pointers.
4. Explain about how to declare pointer to a function with an example. AU: May-
17, Marks 8
#include<stdio.h>
#include<conio.h>
void main()
int a[]={10,20,30,40,50};
clrscr();
getch();
}
void fun(int a[6])
int i;
for(i=0;i<5;i++)
printf("%d",*(a+i));
/* or printf("%d",a[i]);*/
Output
10 20 30 40 50
For example :
But,
But
#include<stdio.h>
#include<conio.h>
void main()
int a[]={10,20,30,40,50};
clrscr();
getch();
}
int i,sum=0;
for(i=0;i<5;i++)
sum=sum+ *(a+i);
Using pointer the next location in array is = (a + i) and the value at that location is
obtained by * (a + i)
return sum;
Output
Sum = 150
File Handling
• Definition: File is a collection of records. In generalized form, a file of size n has
n records in sequence where each record is a collection of one or more fields.
• For example:
So with respect to above example we say that the file has 3 records.
To identify each record, a unique key is associated with it. In the above example
Roll No. can be thought of as an key. Using this key, we are in position to access
the information for that student.
FILE is a structure which is defined in "stdio.h". Each file we open will have its own
FILE structure. The structure contains information like usage of the file, its size,
memory location and so on. The fp is a pointer variable which contains the
address of the structure FILE.
1. Classification of File
• There are two types of files - Text file and Binary file.
• The text files are files in which textual information may be stored with
essentially no formatting.
• Binary files in which any type of data (it might be text, image, or audio) encoded
in binary form. The binary files contain the binary digits. That means it contains
the sequence of 1's and 0's.
write - "w"
append - "a"
• Using "r" opens the file in read mode. If the file does not exist, it will create a
new file, but such a file created is of no use as you cannot write to any file in read
mode.
• Using "r+" allows to read from file as well as write to the file.
• Using "w" opens a file in write mode. If the file does not exist, it will create a
new file.
• Using "w+" allows you to write contents to file, read them as well as modify
existing contents.
• Using "a" opens the file in append mode. If the file does not exist, then it
creates a new file. Opening a file in append mode allows you to append new
contents at the end of the file.
• Using "a+" allows to append a file, read existing records, cannot modify existing
records.
Example :
fp = fopen("Student.dat","w");
Syntax: fclose(filepointer);
Example :
Example :
Example:
Suppose we have
char ch='a';
To write the character to the file, we use
fputc(ch,fp);
Note: If the file is opened in "w" mode, it will overwrite the contents of the entire
file and write the only character we want to write. To write it at the end of the
file, open the file in "a+" mode.
Example :
char ch; /* ch is the character where you are going to get the char from file*/ ch=
fgetc(fp);
Example :
char s[]="abcd";
then we write as
fputs(s,fp);
The above operation writes the string "abcd" to the file pointed by fp.
Example :
char s[80]; /* declared a string into which we want to read the string from file
*/esolat fgets(s,79,fp); /* Will read the 78, (79-1) characters of string from file
into s */
8. Writing of characters, strings, integers,floats to file :
Syntax :
We are already aware of the printf function. fprintf has the same arguments as
that of printf, addition to which filepointer is added. The variables included in the
fprintf are written to the file. But how can we write the data without knowing
their values, so we need to have a scanf function before it and then can write the
data to file. You will understand this better by following example.
'C' Program
/**************************************************************
**************************************************************/
#include<stdio.h>
/*
Input:none
Output:none
Called By:O.S.
*/
main()
FILE *fp;
int rno;
char name[20];
clrscr();
fp = fopen("Student.dat", "w");
if(fp== NULL)
exit(1);
fclose(fp);
getch();
return;
/************End Of Program************/
Output
aaa
student.dat
1 aaa
9. Reading of variables from file:
Syntax:
Having similar arguments as that of the fprintf statement, the fscanf reads the
contents of the file into the variables specified.
Example :
Note: The fprintf and fscanf statements are useful only when the data we want to
enter is less, or rather they have disadvantage that when the number of variables
increase, writing them or reading them becomes clumsy.
/************************************************************
Program for file primitives such as fopen, fwrite. This program writes the string to
the file.
**************************************************************/
#include<stdio.h>
#define MAX 20
int rno;
char name[MAX];
};
main() {
struct stud s;
FILE *fp;
clrscr();
s.rno=1;
strcpy(s.name,"Sachin");
fp = fopen("Student.dat", "w");
if(fp== NULL)
exit(1);
fclose(fp);
return;
Output
student.dat
Sachin 0 =+ 2
Thus we can see from the output of the program that fwrite writes the data in the
file in binary mode.
Example :
fread(&s,sizeof(s),1,fp);
Note: Prior to this statement it is necessary that the pointer is located at the
proper position from where we want to read the file. Here you can use the
rewind(filepointer) function.
An fread or fwrite function moves the pointer to the beginning of the next record
in that file.
where
2) SEEK_CUR move the pointer with reference to its current position in file.
Example :
Let us take the example where we have written a record in file. Suppose we want
to read that record, we have two options:
fseek(fp,-sizeof(s), SEEK_CUR);
This will place the pointer to the beginning of the record we have currently
written. Then we can make use of fread(...) to read that record again.
/******************************************************
***********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct record
int a;
};
void main()
int i,j;
FILE *fp;
struct record r;
clrscr();
r.a=i;
fwrite(&r,sizeof(struct record),1,fp);
fclose(fp);
fp=fopen("input.dat","r");
fseek(fp,OL,SEEK_SET);
fread(&r,sizeof(struct record),1,fp);
printf("%d\n",r.a); fclose(fp); w sw
printf("\n");
fp=fopen("input.dat","r");
fread(&r,sizeof(struct record),1,fp);
printf("%d\n",r.a);
fclose(fp);
printf("\n");
printf(" Reading all the records in reverse order\n");
fp=fopen("input.dat","r");
fseek(fp,sizeof(struct record)*i,SEEK_SET);
fread(&r,sizeof(struct record),1,fp);
printf("%d\n",r.a);
fclose(fp);
printf("\n");
fp=fopen("input.dat","r");
fseek(fp,0,SEEK_SET);
fread(&r,sizeof(struct record),1,fp);
printf("%d\n",r.a);
}
fclose(fp);
printf("\n");
fp=fopen("input.dat","r+");
r.a=-999;
fseek(fp,sizeof(struct record)*4,SEEK_SET);
fwrite(&r,sizeof(struct record),1,fp);
fclose(fp);
printf("\n");
fp=fopen("input.dat","r");
fread(&r,sizeof(struct record),1,fp);
printf("%d\n",r.a);
fclose(fp);
printf("\n");
fp=fopen("input.dat","r+");
fread(&r,sizeof(struct record),1,fp);
printf("%d\n",r.a);
Output
10
-999
6
10
10
In above program we have used fseek with different modes. The output itself is
self explanatory!!
Reading the characters from the file and printing them on console using getc()
test.cpp
/*************************************************************
Reading the contents of the file using getc and printing them on the console
***********************************************************/
#include <stdio.h>
void main()
FILE *fp;
int ch;
fp = fopen("d:\input.dat","r");
ch = getc(fp);
putchar(ch);
ch= getc(fp);
fclose(fp);
} 090
Before running this program we should create an input file as d:\input.dat which
is as given below -
input.dat
T
A
S
T
R
U
C
T
R
E
S
Output
T
A
Program Explanation :
In above program we have to first create an input file say input.dat and store
some characters in it. Then the test.cpp is written in which we are opening the
input.dat file in reading mode using fopen(). By using getc(ch) function we can
read the file character by character. The putchar() is a function for printing a
single character on console. The EOF is a marker that indicates end of file. At the
end of program the file is closed using fclose().
/***********************************************************
Program for counting total number of lines and total number of characters from
the input file
************************************************************/
#include <stdio.h>
#include<conio.h>
void main()
{
FILE *fp;
int ch,chara,lines;
char fname[40];
clrscr();
lines = 0;
chara = 0;
if (fp ===NULL)
return;
ch=getc(fp);
}
{
fclose(fp);
if (chara != 0)
Input.dat
hello students
we are learning
C and
Files
Output
In File d:\input.dat
The putw is a function useful for inputting the integer value to the file and getw is
a function used to read the integer value from the input file
/**********************************************************
**********************************************************/
#include <stdio.h>
#include<conio.h>
#include<io.h>
void main()
FILE *fp;
int roll;
char fname[40];
clrscr();
gets(fname);
if (fp==NULL)
return;
scanf("%d", &roll);
putw(roll,fp);
fclose(fp);
fp=fopen(fname,"r");
roll=getw(fp);
printf("\n%d",roll);
fclose(fp);
getch();
Output
The purpose of fprintf is to write the contents to the file. That's why we have to
open the file in write mode. Following program illustrates the idea of
using fprintf.
test.cpp
/************************************************************
Program for writing the contents to some input file using fprintf
*************************************************************/
#include <stdio.h>
#include<conio.h>
void main()
FILE *fp;
int roll;
float marks;
clrscr();
roll=5;
marks=10.1;
gets(fname);
if (fp == NULL)
return;
fprintf(fp,"%d\n%s\n%f", roll,name,marks);
fclose(fp);
Output
Enter file name: d:\input.dat
The input file d:\input.dat will have some contents written by our
program test.cpp. Hence input.dat file is
d:\Input.dat
ABC
10.100000
The same program can be modified by adding fscanf. The purpose of fscanf is to
read the contents from the input file. We will
5. Using fscanf we will read the contents from the input file.
/***********************************************************
The use of fprintf and fscanf for writing to the file And reading from the file
********************************************************/
#include <stdio.h>
#include<conio.h>
void main()
{
FILE *fp;
int roll;
float marks;
clrscr();
roll=5;
marks=10.1;
if (fp == NULL)
return;
fprintf(fp,"%d\n%s\n%f", roll,name,marks); ni
fclose(fp);
fp=fopen(fname,"r");
while(!feof(fp))
fscanf(fp,"%d\n%s\n%f",&roll,name,&marks);
printf("%d\n%s\n%f", roll,name,marks);
}
getch();
Output
ABC
10.100000
The end of file is detected using a macro EOF (i.e. End Of File) when this condition
occurs then we should not read the contents further.
For example:
#include<stdio.h>
void main()
FILE *fp;
char c;
fp = fopen("try.c","r");
c = getc(fp);
{
putchar( c );
c = getc (fp);
fclose(fp);
In above program "try.c" file is first created in which we have to store some
characters. Another way of detecting end of file is use of feof() function. In this
function the file pointer is passed as an argument.
For example :
The syntax is
feof(file_pointer);
#include<stdio.h>
void main()
FILE *fp;
char c;
fp = fopen("try.c","r");
c = getc(fp);
putchar( c );
ic = getc (fp);
fclose(fp);
Review Questions
/***********************************************************
Implementation of various file operations such as create, display, search and
modification on student database with USN,Name and marks of three subjects
*************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
struct record
int USN;
char name[20];
};
struct record r;
FILE *fp;
void main()
int n,choice;
char ch;
void Create_file(int);
void Display_file(int);
void Modify_file();
struct record *Search_file();
clrscr();
scanf("%d",&n);
do
clrscr();
printf("\n5. Exit");
scanf("%d", &choice);
switch(choice)
case 1: Create_file(n);
break;
case 2: Display_file(n);
break;
case 3: r=*Search_file();
printf("\n USN Name marks1 marks2 marks3\n");
printf("\n---------\n");
flushall();
printf("\n-----------------\n”);
break;
case 4: Modify_file();
break;
case 5 exit(0);
ch=getch();
getch();
void Create_file(int n)
int i;
fp=fopen("stud.dat", "a+");
gets(r.name);
scanf("%d", &r.USN);
scanf("%d", &r.marks1);
scanf("%d", &r.marks2);
scanf("%d", &r.marks3);
fwrite(&r,sizeof(struct record),1,fp);
fclose(fp);
void Display_file(int n)
int i;
fp=fopen("stud.dat","r");
printf("\n------\n");
fread(&r,sizeof(struct record),1,fp);
flushall();
printf("\n------------------\n");
fclose(fp);
void Modify_file()
int i;
int key,new_USN,new_marks1,new_marks2,new_marks3;
char new_name[20];
printf("\n Enter the University Seat Number for modification of record ");
scanf("%d", &key);
fp=fopen("stud.dat","r+");
i=0;
while(!feof(fp))
fread(&r,sizeof(struct record),1,fp);
if(r.USN==key)
{
flushall();
gets(new_name);
scanf("%d",&new_marks1);
scanf("%d", &new_marks2);
scanf("%d", &new_marks3);
r.USN=new_USN;
strcpy(r.name,new_name);
r.marks1=new_marks1;
r.marks2=new_marks2;
r.marks3=new_marks3;
fwrite(&r,sizeof(struct record),1,fp);
i++;
}
fclose(fp);
int key,i;
printf("\n Enter the University Seat Number for Searching the record ");
scanf("%d", &key);
fp=fopen("stud.dat","r+");
i=0;
while(!feof(fp))
fread(&r,sizeof(struct record),1,fp);
if(r.USN==key)
fclose(fp);
return &r;
i++;
Output
Main Menu
1. Create a file
2. Display a file
3. Search a file
4. Modify a file
5. Exit
Main Menu
1. Create a file
2. Display a file
3. Search a file
4. Modify a file
5. Exit
Preprocessor Directives
• Pre-processing is a separate step applied on the source file before presenting it to
compilation process.
• The pre-processor directive is written at the beginning of the program with the #
preceded to it.
This directive tells the compiler to replace the instance of SIZE with 10.
(2) #include<stdio.>
This directive tells to get stdio.h from system libraries and add the text to the
current source file.
This line tells the compiler to get myfile.h from local director and add the contents
with the current source file.
(4)
#undef F_SIZE
#define F_SIZE 80
#ifndef MSG
#endif
Ans. : Union is a user defined data structure which is just similar to structure. It is
used to store members of different data types.
Q.2 What is the difference between structure and union ? AU: Dec.-18
Ans. :
1) Both the structure and union are user defined data types.
2) The structure and union are meant for storing the various member variables of
different data types.
3) The dot operators are used to access the members of the union and structures.
Q.4 How do you access the address, where the elements of a matrix, whose index
is given is stored ?
Ans : Following program shows how to access the address of particular array
#include<stdio.h>
#include<conio.h>
void main()
int a[]={1,2,3,4,5},i;
int *ptr;
ptr=a;
for(i=0;i<5;i++)
printf("\nAddress of a[%d]=%u",i,ptr);
ptr++;
}
expected output will be
Address of a[0]=65516
Address of a[1]=65518
Address of a[2]=65520
Address of a[3]=65522
Address of a[4]=65524
Q.5 Declare a variable 'code' of type union item consisting of an integer m,float
x and char c. Explain what would be the output of the following statements:
code.c='A';
code.m=385;
code.x=14.7;
printf("%c%d",code.c,code.m);
Ans.:
3 13107
These are basically garbage values because the union assigns memory of the
member occupying highest memory space. In above example float requires highest
memory space(i.e. 4 bytes). And at a time union keeps only one member active.
We have lastly accessed
code.x=14.7;
Hence the variable x will be currently active and remaining members will hold the
garbage values. Hence code.c and code.m are printing garbage values.
The structure tag is a name used along with the structure declaration. This tag is
useful in declaration of structure variables.
For example
int roll;
}st;
Ans. :
For example
s1.name or s1.roll
For example
struct bdata {
int day;
int mnth;
int year;
} dt;
struct student {
int roll.no;
} std;
The scope of the nested structure is within the outer structure, and it can be
accessed with the tag of outer and inner structure.
Q.9 Define preprocessor directives and list out a few examples. AU; Dec.-18,
May-19
Ans. :
• Preprocessor directive is a kind of program which is used to preprocess the C
program before compiling.
• Commands used in preprocessor are called preprocessor directives and they begin
with symbol #.
• Header file inclusion: Using #include the required header file can be included in
the C program.
Ans. : Pointer is a variable that represents the memory location of some other
variable. It can be initialized as
int a = 10;
int *ptr=&a;
Q.11 What does #include < header_name> do? How is it possible to tell the
preprocessor where to look for header files? AU: Dec.-19
Ans. : The #include is a preprocessor directive which requests the header file. It is
possible to tell the preprocessor to look for the desired header file by specifying its
name and path of the file. For standard header files of C program the system
directories are searched.
Linear Data Structures - List
Unit III
Chapter - 3
a. Linear Data Structures - List
Syllabus
Abstract Data Types (ADTS) - List ADT - Array-Based Implementation - Linked
List - Doubly- Linked Lists - Circular Linked List.
Contents
3.1 Introduction to Data Structure
For example :
The data structures can be divided into two basic types Primitive and Non
primitive data structures The Fig. 3.1.1. shows various types of data structures.
Linear data structures are the data structures in which data is arranged in a list or
in a straight sequence.
For example
Arrays, List
Non linear data structures are the data structures in which data may be arranged
in hierarchical manner.
For example
Trees, Graphs
1. ADT Operations
• While modeling the problems the necessary details are separated out from the
unnecessary details. This process of modeling the problem is called abstraction. It
is why represented by Fig. 3.2.1.
• The model defines an abstract view to the problem. Thus the model focuses
only on problem related stuff and that you try to define properties of the
problem.
2. Display: This operation is for displaying all the elements of the data structure.
4. Deletion: By this operation any desired element can be deleted from the data
structure.
Examples
If we want to write ADT for a set of integers, then we will use following
method AbstractDataType Set
Preconditions: none
Operations:
1. Store (): This operation is for storing the integer element in a set.
2. Retrieve (): This operation is for retrieving the desired element from the given
set.
There is a specific method using which an ADT can be written. We begin with
keyword AbstractDataType which is then followed by name of the data structure
for which we want to write an ADT. In above given example we have
taken Set data structure.
• Then a listing of all the required operations must be given. In this section, we
must specify the purpose of the function. We can also specify the data types of
these functions.
AbstractDataType Array
Instances: An array A of some size, index i and total number of elements in the
array n.
Operations:
Review Question
1. Define data abstraction. Write the ADT for the data structure in which the same
condition can used appropriately, for checking over flow and underflow. Define all
basic function of this ADT. (Hint: Check stack ADT in section 4.2) AU: May-19,
Marks 9
List ADT
• List is a collection of elements in sequential order.
• In memory we can store the list in two ways, one way is we can store the
elements in sequential memory locations. This is known as arrays. And the other
way is, we can use pointers or links to associate the elements sequentially. This
known as Linked Lists.
• In ADT the implementation details are hidden. Hence the ADT will be -
AbstractDataType List
3. Searching: Based on the value of the key element the desired element can be
searched.
• The linked list that can be represented by arrays is called static linked list.
• In this section we will discuss in detail how exactly the list can be represented
using arrays.
• To show the list using arrays we will have 'data' and 'link' fields in the array.
struct node
int data;
int next;
} a[10];
Last node. The next field gives the index as - 1 and - 1 is not any subscript in the
array. Hence - 1 is taken as end of the list.
1. Creation of list.
2. Display of list.
The list can be created by placing the node of list in an array. Each node consists of
two fields 'data' and 'next' pointer. We need to give the address of starting node
which is to be placed in the array.
While creating the list we have to first enter the location in an array where the first
node is placed and then input the pair: data and next.
Int Create()
int head,i;
printf("\n Enter the index for first node");
scanf("%d", &i);
head=i;
2. Display
After creation we can display the list. Normally when the list is displayed simply
the data fields are to be displayed.
After creation we can display the list. Normally when the list is displayed simply
the data fields are to be displayed.
void Display(int i)
printf("(");
while(i!= -1)
printf(" ");
else
{
printf("%d, ",a[i].data);
i=a[i].next;
In Insert function, consider that we have already created a list (10, 20, 30, 40) as -
While deleting a node from the list we simply manipulate the next pointer of
previous node in the list. And the data field of the node to be deleted is initialized
to - 1.
(10,20, 21,30,40)
While deleting this node copy 6 (a[i].next) to the next pointer of previous node in
the list. Here 20 comes before 21 in the list. Hence we will copy a[2].next to
a[1].next. And actual deletion takes place when a[2].data is assigned to -1.
Let us see a C program based on it -
/*************************************************************
*************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
struct node
{
int data;
int next;
}a[10];
void main()
char ans;
int Create();
void Display(int);
void Insert();
void Delete();
void Search();
do
clrscr();
printf("\n1. Creation");
printf("\n2. Display");
printf("\n6. Exit");
printf("\n Enter Your choice");
scanf("%d", &choice);
switch(choice)
head=Create();
break;
case 2:Display(head);
break;
case 3:Insert();
break;
case 4:Delete();
break;
case 5:Search();
break;
case 6:exit(0);
}
printf("\n Do you Wish to go to Main Menu?");
ans=getch();
getch();
int Create()
int head,i;
scanf("%d",&i);
head=i;
while(i!= -1)
scanf("%d %d",&a[i].data,&a[i].next);
i=a[i].next;
return head;
void Display(int i)
while(i!= -1)
if(a[i].data==-1)
printf(" ");
else
printf("%d, ",a[i].data);
i=a[i].next;
printf(" NULL)");
void Insert()
int i,new_data,temp;
scanf("%d", &new_data);
scanf("%d", &temp);
for(i=0;i<10;i++)
{
if(a[i].data==temp)
break;
a[i+1].next=a[i].next;
a[i].next=i+1;
a[i+1].data=new_data;
void Delete()
int i,temp,current,new_next;
scanf("%d",&temp);
for(i=0;i<10;i++)
if(a[i].data==temp)
if(a[i].next==-1)
for(i=0;i<10;i++)
if(a[i].next== current)
a[i].next=new_next;
a[current].data=-1;
void Search()
int i,temp,flag=0;
scanf("%d",&temp);
for(i=0;i<10;i++)
if(a[i].data==temp)
{
break;
if(flag==1)
else
Output
Main Menu
1. Creation
2. Display
6. Exit
Main Menu
1. Creation
2. Display
6. Exit
Main Menu
1. Creation
2. Display
6. Exit
Limitations
1. There is a limitation on the number of nodes in the list because of fixed size of
array. Hence sometimes memory may get wasted because of less elements in the
list or there may be large number of nodes in the list and we could not store some
elements in the array.
Hence we will go for dynamic memory allocation for implementing the list.
Key Point: The list creation using dynamic memory management is called linked
list.
(Note: The elements can shift to the left or to the right to make the minimum
number of moves) AU: May-14, Marks 16
Sol. :
Step 1: Enter the number of elements present in the array. Also enter the elements
in the array.
scanf("%d",&n);
printf("\n Enter the elements (Type -99 for empty location): ");
for(c=0;c<n;c++)
scanf("%d",&array[c]);
Step 2: Enter the value of the element which is to be inserted in the array, say Key
Element. Also enter the position at which this element is to be
inserted.Say Key_Position.
scanf("%d", &Key_Element);
scanf("%d", &Key_Postion);
Step 3:
//If the Key_Position is empty then insert the Key_Element at that position.
if(array[Key_Postion] ==-99)
array[Key_Position]=Key_Element;
Step 4:
LeftElementCount=i;
for(j=n-1;j>=Key_Position;j—);
RightElementCount=j;
If empty location is present then move the elements to the right by creating space
at Key_Position then
Else
goto step 8
Step 7:
//Create the space at Key_Position by shifting the last position elements to the
rightmost //empty space.
for(k=n-1;k>=Key_Position-1;k--)
array[k+1]=array[k];
array[Key_Position-1] =Key_Element;
printf("%d", array[c]);
Review Question
Linked List
AU: Dec.-15,18,19, May-16, Marks 16
• Definition: A linked list is a set of nodes where each node has two fields 'data'
and a 'link'. Where data field stores the actual piece of information and 'link' field
is used to point to next node. Basically link field is nothing but the address only.
• Note that the link field of last node consists of 'NULL' which indicates end of
linked list.
} SLL;
• Declare a structure in which two members are there i.e. data member and next
pointer member.
• The data member can be character or integer or real kind of data depending
upon the type of the information that the linked list is having.
• The 'next' member is essentially of a pointer type. And the pointer should be of
structure type. Because the 'next' field holds the address of next node. And each
node is basically a structure consisting of 'data' and 'next'.
In this type of linked list only one link is used to point to next element and this list
is circular means that the last node's link field points to the first or head node.
That means according to example after 40 the next number will be 10. So the list
is circular in nature.
This list called doubly because each node has two pointers previous and next
pointers. The previous pointer points to previous node and next pointer points to
next node. Only in case of head node the previous pointer is obviously NULL and
last node's next pointer points to NULL. This list is a linear one.
In circular doubly linked list the previous pointer of first node and the next pointer
of last node is pointed to head node. Head node is a special node which may have
any dummy data or it may have some useful information such as total number of
nodes in the list which may be used to simplify the algorithms carrying various
operations on the list.
node* create()
char ans='y';
node *get_node();
temp = NULL;
flag = TRUE; /* flag to indicate whether a new node is created for the first time or
not */
do
{
scanf("%d", &val);
New = get_node();
if (New == NULL)
head = New;
0.ebon Jer
flag = FALSE;
else
temp = New;
} while(ans == 'y');
getch();
clrscr();
return head;
node *get_node()
node *temp;
return temp;
Initially one variable flag is taken whose value is initialized to TRUE (i.e. 1). The
purpose of flag is for making a check on creation of first node. That means if flag is
TRUE then we have to create head node or first node of linked list. Naturally after
creation of first node we will reset the flag (i.e. assign FALSE to flag). Consider that
we have entered the element value 10 initially then,
Step 1:
New = New get_node ();
Step 2:
if (flag == TRUE)
head=New
temp=head;
/* We have also called this node as temp because head's address will be
preserved in 'head' and we can change 'temp' node as per requirement */
flag = FALSE;
Step 3:
If head node of linked list is created we can further create a linked list by
attaching the subsequent nodes. Suppose we want to insert a node with value 20
then,
Step 4:
If user wants to enter more elements then let say for value 30 the scenario will
be,
Step 5:
is the final linked list.
We are passing the address of head node to the display routine and calling head
as the 'temp' node. If the linked list is not created then naturally head-temp node
will be NULL. Therefore the message "The list is empty" will be displayed.
node *temp;
temp = head;
if (temp==NULL)
getch();
clrscr();
return;
}.
printf("NULL");
getch();
clrscr();
10 20 30 40 50 → NULL
There are three possible cases when we want to insert an element in the linked
list -
node *New,*temp;
New-get_node();
scanf("%d", &New→data);
if(head== NULL)
Now we will insert a node at the end -
node *New,*temp;
New get_node();
scanf("%d", &New→data);
if(head == NULL)
head=New;
else
Finding end of the linked list. Then temp will be a last node
temp=head;
temp-temp →next;
temp →next=New;
New →next=NULL;
To attach a node at the end of linked list assume that we have already created a
linked list like this-
Now we will insert a new node after some node at intermediate position
int key;
node *New,*temp;
New= get_node();
scanf("%d",&New→data);
if(head= NULL)
{
head=New;
Else
printf("\n Enter The element after which you want to insert the node");
scanf("%d", &key);
temp=head;
do
if(temp →data==key)
temp →next=New;
return;
else
temp-temp →next;
}while(temp!= NULL);
temp =*head;
if (temp == NULL)
getch();
Always check before deletion whether come? the linked list is empty or not.
Because if the list is empty there is no point in performing deletion
clrscr();
return
clrscr();
scanf("%d", &key);
temp = search(*head,key);
if (temp != NULL)
prev = get_prev(*head,key);
if (prev != NULL)
Once the node to be deleted is found then get the previous node of that node in
variable prev
else
*head=temp →next;
free(temp);
If we want to delete head node then set adjacent node as a new head node and
then deallocate the previous head node
getch();
Suppose we have,
Suppose we want to delete node 30. Then we will search the node containing 30,
using search (*head, key) routine. Mark the node to be deleted as temp. Then we
will obtain previous node of temp using get_prev () function. Mark previous node
as prev
This can be done using following statements.
free (temp);
The search function is for searching the node containing desired value. We pass
the head of the linked list to this routine so that the complete linked list can be
searched from the beginning.
{
node *temp;
int found;
temp =head
if (temp == NULL)
getch();
clrscr();
return NULL;
found = FALSE;
if (temp→data != key)
temp = temp→next;
else
Compare each node with the key value. If not matching then move to next node
Found =TRUE;
if (found ==TRUE)
{
If the node containing desired data is obtained in the linked list then found
variable is set to TRUE.
getch();
return temp;
else
getch();
return NULL;
Suppose key = 30 i.e. we want a node containing value 30 then compare temp→
data and key value. If there is no match then we will mark next node as temp.
Hence print the message "The Element is present in the list".
Thus in search operation the entire list can be scanned in search of desired node.
And still, if required node is not obtained then we have to print the message.
/*****************************************************************
************************************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
int data;
}node;
node *create();
void main()
/* Local declarations */
char ans;
node *head;
head =NULL;
do
{
clrscr();
printf("\n1.Create");
printf("\n2.Display");
printf("\n6.Quit");
scanf("%d", &choice);
switch( choice)
case 1: head=create();
break;
case 2: display(head);
break;
scanf("%d", &val);
search(head, val);
break;
case 4: head-insert(head);
break;
case 5: dele(&head);
break;
case 6 exit(0);
default:clrscr();
getch();
} while(choice != 6);
node* create()
char ans='y';
node *get_node();
temp = NULL;
flag=TRUE; /* flag to indicate whether a new node is created for the first time or
not */
do
scanf("%d", &val);
/* allocate new node */
New = get_node();
if (New==NULL)
head = New;
flag = FALSE;
else {
temp →next=New;
temp =New;
ans=getche();
}while(ans=='y');
getch();
clrscr();
return head;
node *get_node()
node *temp;
return temp;
node *temp;
temp=head;
if (temp == NULL)
getch();
clrscr();
return;
{
printf("%d → ", temp →data);
temp=temp →next;
printf("NULL");
getch();
clrscr();
node *temp;
int found;
temp = head;
if (temp==NULL)
getch();
clrscr();
return NULL;
found = FALSE;
else
found=TRUE;
if (found ==TRUE)
getch();
return temp;
else
getch();
return NULL;
/*
Calls search()
*/
int choice;
scanf("%d", &choice);
switch(choice)
break;
case 2:insert_last(head);
break;
case 3:insert_after(head);
break;
}
Hence we have to return the new head from the insert function to main
return head;
node *New,*temp;
New=get_node();
if(head == NULL)
head=New;
else
temp-head;
New →next=temp;
head=New;
return head;
}
/*Insertion of node at last position*/
node *New,*temp;
New=get_node();
scanf("%d", &New→data);
if(head == NULL)
head=New;
else
:{
temp=head;
temp-temp →next;
temp →next=New;
{
int key;
node *New,*temp;
New= get_node();
if(head == NULL)
head=New;
else
printf("\n Enter The element after which you want to insert the node");
scanf("%d", &key);
temp=head;
do
if(temp →data==key)
temp →next=New;
return;
}
else
temp-temp→next;
}while(temp!= NULL);
int flag;
temp = head;
if (temp==NULL)
return NULL;
flag = FALSE;
prev = NULL;
if (temp→data != val)
prev =temp;
else
flag = TRUE;
return prev;
else
return NULL;
/*
*/
int key;
temp = *head;
if (temp == NULL)
clrscr();
return;
clrscr();
scanf("%d", &key);
temp=search(*head,key);
if (temp != NULL)
prev =get_prev(*head,key);
if (prev != NULL)
free (temp);
Else
free(temp);
clrscr();
Output
1.Create
2.Display
6. Quit
1.Create
2.Display
6. Quit
10 → 20 → 30 → 40 → 50 → NULL
1.Create
2. Display
6. Quit
2.Display
6. Quit
1.Create
2.Display
6. Quit
9 → 10 →20 → 30 → 40 → 50 → NULL
2.Display
6. Quit
1.Create
2.Display
6. Quit
9 → 10 →20 → 30 → 40 → 50 → 60 → NULL
2.Display
6. Quit
Enter The element after which you want to insert the node 30
1.Create
2.Display
6. Quit
9 → 10 → 20 → 30 → 31 → 40 → 50 → 60 → NULL
Program to Perform Various operations on Linked List
1.Create
2.Display
6. Quit
1.Create
2.Display
6. Quit
9 → 10 → 20 → 30 → 31 → 50 → 60 → NULL
4 More Programs on Linked List
In this section we will discuss various operations that can be performed on the
linked list. For the sake of convenience we will discuss only functions performing
these operations assuming that the list is already created.
The create() and display() functions will be common to all these operations.
Sol. :
void count()
node *temp;
int c=0;
temp=head;
if(temp== NULL)
return;
temp-temp →next;
}
printf("\nThe Total number of nodes are: %d",c);
getch();
Sol. :
node *temp1,*temp2;
temp1=head1;
temp2=head2;
while(temp1→next!= NULL)
temp1=head1;
while(temp1!= NULL)
printf("%d",temp1→Data);
temp1=temp1→next;
}
Ex. 3.5.4 Algorithm to copy one singly list to another
Sol. :
node *temp1,*temp2;
head2=(node *)malloc(sizeof(node));
temp1=temp1 →next;
temp2=NULL;/*set the next pointer of last node of second list to NULL*/ printf("\
n The list is copied \n");
while(head2→next!= NULL)
printf("%d",head2 →data);
head2-head2 →next;
Ex. 3.5.5 Recursive routine to erase a linked list (delete all node from the linked
list)
Sol.:
temp→next=NULL;
free(temp);
list_free(temp1);/*recursive call*/
temp=NULL;
return temp;
Ex. 3.5.6: Write a routine to merge two sorted linked lists. AU : Dec.-15 Marks 8
Sol. Consider two linked lists
if(temp1== NULL)
temp1=temp2;
head=temp2;
if(temp1→data<temp2→data)
head=temp1;
else
head=temp2;
temp1=temp1→next;
if(temp1== NULL)
break;
/*when temp1's data>temp1 it will come out of while loop so adjust links with
temp1's prev node*/
prev_node1→next=temp2;
temp2→next=temp1;
temp1=temp2;
temp2=next_node2;
while(temp2!= NULL)
prev_node1→next=temp2;
prev_node1=temp2;
temp2=temp2→next;
return head;
}
Ex. 3.5.7: Returning the position of an element X in a list L
int count=0;
node *temp;
temp=head;
while(temp→data!=key)&&(temp!= NULL)
temp-temp→next;
count=count+1;
}
if(temp→data==key)
return count;
return -1; /* -1 indicates that the element X is not presentin the list*/
Ex. 3.5.8 Write a C function to display the sum of all the elements in a singly
linked list.
Sol. :
node *temp;
int s=0;
temp=head;
while(temp!= NULL)
s=s+temp→data;
temp-temp→next;
printf("%d",s);
}
Ex. 3.5.9: Assume a singly linked list where each node contains student details
like name, rollno and percentage of marks. Write a "C" function COUNTO to
traverse the linked list and count how many students have obtained more than
60 %.
struct student
char *name;
int roll;
float marks;
};
int count=0;
while(temp!= NULL)
if(temp→marks>60)
count++;
temp-temp→next;
}
printf("\n\n %d students have obtained more than 60 Percentage", count);
Ex. 3.5.10 : Write a C program to create a singly linked list and split it at the
middle. And make the second half as the first and vice versa, display the final
list.
Sol. :
int data;
}node;
void main()
node*head=NULL,*p, *q;
int n,i,x;
scanf("%d",&n);
for(i=0;i<n;i++)
printf("\nEnter element:");
scanf("%d", &x);
p=(node*)malloc(size of(node));
p→data=x;
p→next=NULL;
if(head == NULL)
head=q=p;
else {
q→next=p;
q=p;
p=q=head;
p=p→next;
q=q→next;
if(q→next!= NULL)
q-q→next;
q→next-head;
head=p→next;
p→next=NULL:
for(p=head;p!= NULL;p=p→next)
printf("\n%d",p-data);
Ex. 3.5.11: Write a function that removes all duplicate elements from a linear
singly linked list.
Sol. :
node *p,*q,*r;
p=head;
q=p→next;
while(q!= NULL)
if(p→data!-q→data)
p=p→next;
q=q→next;
else
if(p→data==q-data)
p→next-q→next;
r=q;
q=q→next;
free(r);
return(head); }
Ex. 3.5.12: Suppose a linked list consists of numerical values. Write a function
for finding the maximum element of the list and the product of all the numbers
in the list.
node *temp;
int Maxval;
temp=root;
Maxval-temp→data;
while(temp!= NULL)
{.
if(temp→data>Maxval)
Maxval-temp→data;
}
temp-temp→next;
node *temp;
int p=1;
temp=root;
while(temp!= NULL)
p=p*temp→data;
temp-temp→next;
Review Questions
1. Write C code for singly liked list with insert, delete, display operations using
structure pointer.D AU: May-16, Marks 16
2. What are the ways to insert a note in linked list? Write an algorithm for
inserting a node before a given node in a linked list.AU: Dec.-18, Marks 6
3. Explain the insertion operation linked list. How nodes are inserted after a
specified node? AU: Dec.-19, Marks 13
Ex. 3.6.1 Compare linked list with arrays with reference to the following
aspects :
b) In linked list, we can insert and delete elements easily and it is less time
consuming.
a) Array requires contiguous memory. First we have to declare array and compiler
allocates memory at declaration.
c) If we want to add more elements than the actual size of array, it is not possible.
• Definition: The doubly linked list has two link fields. One link field is previous
pointer and the other link field is that next pointer.
• The typical structure of each node in doubly linked list is like this.
• C Structure
int data;
}dnode;
• Representation
Thus the doubly linked list can traverse in both the directions, forward as well as
backwards.
Now, there may be one question in your mind that how do the empty doubly
circular linked lists look ? Here is the representation.
That means the prev and next pointers are pointing to the self node.
/************************************************
such as creation, insertion, deletion, search and display on doubly link lists.
******************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
int data;
}node;
node *create();
/*
*/
void main()
/* Local declarations */
char ans;
'node *head;
head = NULL;
do
clrscr();
printf("\n1.Create");
printf("\n2.Display");
printf("\n6.Quit");
scanf("%d", &choice);
switch( choice)
break;
case 2:display(head);
break;
scanf("%d", &val);
search(head, val);
break;
case 4:head-insert(head);
break;
case 5:dele(&head);
break;
case 6:exit(0);
default:clrscr();
} while(choice != 6);
/*
*/
node* create()
char ans='y';
node *get_node();
temp = NULL;
flag=TRUE; /* flag to indicate whether a new node is created for the first time or
not */
do
scanf("%d", &val);
New = get_node();
if (New == NULL)
gell edt to
head=New;
flag = FALSE;
Else
temp→next = New;
New→prev=temp;
temp = New;
ans=getche();
} while(ans=='y');
getch();
clrscr();
return head;
node *get_node()
node *temp;
temp=(node *) malloc(sizeof(node) );
temp→next = NULL;
temp→prev=NULL;
return temp;
/*
Called by main
*/
node *temp;
temp=head;
if (temp==NULL)
{
getch();
clrscr();
return;
temp= temp→next;
printf("NULL");
temp=head;
while(temp→next!= NULL)
printf("%d→", temp→data );
temp=temp → prev;
}
printf("NULL");
getch();
clrscr();
/*
*/
node *temp;
int found;
temp = head;
if (temp==NULL)
getch();
clrscr();
return NULL;
found=FALSE;
{
if (temp→data != key)
temp=temp→next;
else
found = TRUE;
if (found ==TRUE)
getch();
return temp;
else
getch();
return NULL;
/*
*/
node *insert(node *head)
int choice;
scanf("%d", &choice);
switch(choice)
break;
case 2:insert_last(head);
break;
case 3:insert_after(head);
break;
return head;
}
/* Insertion of node at first position*/
node *New,*temp;
New=get_node();
scanf("%d", &New→data);
if(head= NULL)
head=New;
else
temp=head;
New→next=temp;
temp→prev=New;
head=New;
return head;
node *New,*temp;
New=get_node();
scanf("%d", &New→data);
if(head == NULL)
head=New;
else
temp=head;
while(temp→next!= NULL)
temp=temp→next;
temp→next=New;
New→prev=temp;
New→next = NULL;
int key;
node *New,*temp;
New= get_node();
if(head == NULL)
head=New;
else
printf("\n Enter The element after which you want to insert the node");
scanf("%d", &key);
temp=head;
do
if(temp→data==key)
New→next=temp→next;
(temp→next)→prev=New;
temp→next=New;
New→prev=temp;
return;
else
temp=temp→next;
} while(temp!= NULL);
*/
int key;
temp = *head;
if (temp==NULL)
getch();
clrscr();
return;
clrscr();
scanf("%d", &key);
temp = search(*head,key);
if (temp!= NULL)
prev_node = temp->prev;
if (prev_node != NULL)
prev_node->next = temp->next;
(temp->next)->prev = prev_node;
free (temp);
else
*head = temp->next;
(*head)->prev=NULL;
free(temp);
clrscr();
Output
1.Create
2.Display
6. Quit
2. Display
1.Create
2.Display
6. Quit
1.Create
2.Display
6. Quit
1.Create
2.Display
6. Quit
1. Create
2. Display
6. Quit
1.Create
2. Display
6. Quit
Step 1: Initially one variable flag is taken whose value is initialized to TRUE. The
purpose of this flag is for making a check on creation of first node. After creating
first node reset flag (i.e. assign FALSE to flag)
Step 2: If head node is created, we can further create a linked list by attaching the
subsequent nodes. Suppose, we want to insert a node with value 20 then
2. Display of DLL
Previous link and next link. Hence we can display DLL in forward as well as in
reverse direction.
10->20->30->40
Reverse Display
First of all we must reach at the last node by using while statement.
40→30→20→10
3. Insertion of a node in DLL
Case 2: Insertion of a node at the end suppose we want to insert a node with
value 40 then, first move temp pointer to the last node
Case 3: Inserting a node at the intermediate position
Suppose, we want to insert a node with value 22 after node with value 20, then
first search the node with value 20
4. Deletion of node
Suppose we want to delete a node with a value 20 then, first search this node, call
it as temp.
After setting these links, free (temp) in order to delete this node physically no
thus we get
1. Singly and Doubly Linked List Comparison
Review Questions
1. What is meant by doubly linked list? Write the functions to perform the
following operations in a doubly linked list.
i) Insert after a specified node ii) Delete the node at a given position iii) Display-
from the beginning to end.AU: Dec.-15, Marks 16
2. Illustrate the algorithms to implement the doubly linked list and perform all the
operations on the created list.AU May-16, Marks 16
• Definition: The Circular Linked List (CLL) is similar to singly linked list except
that the last node's next pointer points to first node.
3. Deletion of any node from linked list. 4. Display of circular linked list.
char ans;
int flag=1;
clrscr();
do
New = get_node();
head = New;
flag=0;/*reset flag*/
temp-head;
ans=getch();
return head;
New->next = NULL;
Initially we will allocate memory for New node using a function get_node(). There
is one variable flag whose purpose is to check whether first node is created or not.
That means flag is 1 (set) then first node is not created. Therefore after creation of
first node we have to reset the flag (making flag = 0).
Initially,
Now as flag = 0, we can further create the nodes and attach them as follows.
temp = head;
if(temp == NULL)
else
do
{
printf("%d\t",temp->data);
temp = temp->next;
getch();
New=get_node();
scanf("%d",&New->data);
if(head == NULL)
head=New;
else
temp=head;
while(temp->next!=head)
temp=temp->next;
temp->next=New;
New->next = head;
head=New;
return head;
New=get_node();
scanf("%d", &New->data);
if(head == NULL)
head= New;
else
{
temp=head;
while(temp->next!=head)
temp=temp->next;
temp->next=New;
New->next = head;
int key;
New= get_node();
scanf("%d", &New->data);
if(head == NULL)
head=New;
else
{
printf("\n Enter The element after which you want to insert the node ");
scanf("%d", &key);
temp=head;
do
if(temp->data==key)
New->next-temp->next;
temp->next=New;
return;
else
temp-temp->next;
}while(templ=head);
int key;
scanf("%d", &key);
temp=head;
if(temp1==temp)
temp=NULL;
head=temp;
else
while(temp->next!=head)
temp->next=temp1;
head=temp1;/*new head*/
else
temp1=temp->next;
temp->next-temp1->next;
temp1->next=NULL;
free(temp1);
else
temp-temp->next;
return head;
If we want to delete an intermediate node from a linked list which is given below
The linked list can be -
temp=head;
while(temp->next!=head)
{
if(temp->data == num)
else
return NULL;
while searching a node from circular linked list we go on comparing the data field
of each node starting from the head node. If the node containing desired data is
found we return the address of that node to calling function.
/*********************************************************
*************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct node
int data;
struct node *next;
};
void main()
char ch;
int num,choice;
head=NULL;
do
clrscr();
scanf("%d", &choice);
switch(choice)
case 1 :head=Create();
break;
case 2 :Display(head);
break
case 3:head=Insert(head);
break;
break;
scanf("%d", &num);
temp Search(head,num);
if(temp!= NULL)
else
break;
case 6:exit(0);
}
ch=getch();
char ans;
int flag=1;
clrscr();
do
New = get_node();
scanf("%d",&New->data);
head =New;
flag=0;/*reset flag*/
}
temp=head;
temp->next=New;
ans=getch();
return head;
New->next = NULL;
temp = head;
if(temp ==NULL)
else
do
temp = temp->next;
getch();
int choice;
scanf("%d", &choice);
switch(choice)
case 1: head=insert_head(head);
break;
case 2: insert_last(head);
break;
case 3: insert_after(head);
break;
return head;
New=get_node();
scanf("%d", &New->data);
if(head= NULL)
head=New;
else
temp=head;
while(temp->next!=head)
temp=temp->next;
temp->next=New;
New->next-head;
head=New;
return head; }
New=get_node();
scanf("%d",&New->data);
if(head == NULL)
head=New;
else
temp=head;
while(temp->next!=head)
temp=temp->next;
temp->next=New;
New->next = head;
int key;
New= get_node();
scanf("%d",&New->data);
if(head == NULL)
head=New;
else
{
printf("\n Enter The element after which you want to insert the node");
scanf("%d", &key);
temp=head;
do
if(temp->data==key)
New->next-temp->next;
temp->next=New;
return;
else
temp=temp->next;
}while(temp!=head);
temp=head;
while(temp->next!=head)
if(temp->data == num)
else
temp-temp->next;
return NULL;
int key;
scanf("%d", &key);
temp=head;
temp1=temp->next;
if(temp1==temp)
/*if single node is present in circular linked listand we want to delete it*/
{
temp=NULL;
head=temp;
else /*otherwise*/
while(temp->next!=head)
temp->next=temp1;
head=temp1;/*new head*/
else
if((temp->next)->data==key)
temp1=temp->next;
temp->next=temp1->next;
temp1->next = NULL;
free(temp1);
else
temp-temp->next;
return head;
Output
6. Exit
10
30
40
6. Exit
10 20 30 40
6.Exit
Enter The element after which you want to insert the node 30
OF
6. Exit
6. Exit
6. Exit
10 30 33 40
6. Exit
6. Exit
6. Exit
In circular linked list the next pointer of last node points to the head node. Hence
we can move from last node to the head node of the list very efficiently. Hence
accessing of any node is much faster than singly linked list.
1) The circular list is used to create the linked lists in which the last node points to
the first node.
Review Question
1. Write a procedure to deleting the last node from a circular linked list. AU:
Dec.-18, Marks 6
1. The linked list is used for performing polynomial operations such as addition,
multiplication evaluation and so on.
Review Question
1. What are the applications of linked list in dynamic storage management? AU:
Dec.-19, Marks 13
Ans. : The data structure can be defined as the collection of elements and all the
possible operations which are required for those set of elements. Formally data
structure can be defined as a data structure is a set of domains D, a set of functions
F, and a set of axioms A. This triple (D, F, A) denotes the data structure d.
Ans. : The non linear data structure is the kind of data structure in which the data
may be arranged in hierarchical fashion. For example - Trees and graphs.
Ans. : Various operations that can be performed on the data structure are -
1. Create
2. Insertion of element
3. Deletion of element
Q. 5 What is abstract data type? What are all not concerned in an ADT ? AU:
Dec.-19
Ans. : The abstract data type is a triple of D i.e. set of axioms, F-set of functions
and A- Axioms in which only what is to be done is mentioned but how is to be
done is not mentioned. Thus ADT is not concerned with implementation details.
Q. 6. List out the areas in which data structures are applied extensively.
Ans. : Following are the areas in which the data structures are applied extensively.
1. Operating system - The data structures like priority queues are used for
scheduling the jobs in the operating system.
2. Compiler design - The tree data structure is used in parsing the source program.
inil vlduob Stack data structure is used in handling the recursive calls.
3. Database management system The file data structure is used in database
management systems. Sorting and searching techniques can be applied on these
data in the file.
5. Graphics - The array and linked list are useful in graphics applications.
6. Artificial intelligence - The graph and trees are used for the applications like
building expression trees, game playing.
7. Networking - The graph is used for finding the shortest path length between any
two computers that are connected in a LAN.
Ans. : A linked list is a set of nodes where each node has two fields 'data' and
'link'. The data field is used to store actual piece of information and link field is
used to store address of next node.
Ans. :
1. It is linear data structure in which the elements are arranged adjacent to each
other. elinteb neilstrsms.
3. If the LIST is implemented using dynamic memory then it is called linked list.
Ans. In circular list the next pointer of last node points to head node, whereas in
doubly linked list each node has two pointers: One previous pointer and another is
next pointer. The main advantage of circular list over doubly linked list is that with
the help of single pointer field we can access head node quickly. Hence some
amount of memory get saved because in circular list only one pointer field is
reserved.
Q. 11 What are the advantages of doubly linked list over singly linked list?
Ans. : The doubly linked list has two pointer fields. One field is previous link
field and another is next link field.
Because of these two pointer fields we can access any node efficiently whereas in
singly linked list only one pointer field is there which stores forward pointer,
which makes accessing of any node difficult one.
Ans. The circular linked list is a kind of linked list in which the last node is
connected to the first node or head node of the linked list.
Ans. : The header node is the very first node of the linked list. Sometimes a
dummy value such as -999 is stored in the data field of header node. Refer Fig.
3.10.1.
This node is useful for getting the starting address of the linked list. As there is
only a forward link present in the linked list, for accessing the entire linked list it is
necessary to obtain the starting address of the linked list.
Q. 16 Should arrays of linked lists be used for the following type of applications.
Justify your Answer.
Ans. :
a) If the list is sorted then using linked list the desired element can be searched,
simply by moving forward using 'next' pointer.
b) If a list is not sorted then using arrays the desired element can be searched. The
arrays facilitates the access to random element.
Ans. : Refer Q. 5.
Q. 18 What is static linked list? State any two applications of it. AU: May-15
Ans. The linked list structure which can be represented using arrays is called static
linked list.
Q. 19 Write syntax of calloc() and relloc() and mention its applications in the
linked list AU: May-15
Ans. : calloc() is for allocating the required amount of memory. The syntax is void
*calloc(size_t nitems, size_t size)
This function returns the pointer to the allocated memory. The calloc function is
just similar to malloc but it initializes the allocated memory to zero and malloc
does not.
The realloc() function modifies allocated memory size by malloc() and calloc()
functions to new size. The syntax is
If insufficient memory exists then to expand the memory block, realloc() is used.
Q. 20 What are the disadvantages of linked list over arrays. AU: Dec.-18
2) Some amount of memory gets wasted in storing the next node's address in each
nodes.
Linear Data Structures Stacks and Queues
Unit III
Chapter 4
Linear Data Structures Stacks and Queues
Syllabus
Contents
Part I: Stacks
4.5 Expression
Concept of Stack
• Definition :
A stack is an ordered list in which all insertions and deletions are made at one end,
called the top. If we made at on have to make stack of elements 10, 20, 30, 40, 50,
60 then 10 will be the bottommost element and 60 will be the topmost element in
the stack. A stack is shown in Fig. 4.1.1.
• Example
The typical example can be a stack of coins. The coins can be arranged one on
another, when we add a new coin it is always placed on the previous coin and
while removing the coin the recently placed coin can be removed. The example
resembles the concept of stack exactly.
Stack ADT
• Stack is a data structure which posses LIFO i.e. Last In First Out property.
AbstractDataType stack
Preconditions:
1. Stfull (): This condition indicates whether the stack is full or not. If the stack is
full then we cannot insert the elements in the stack.
2. Stempty(): This condition indicates whether the stack is empty or not. If the
stack is empty then we cannot pop or remove any element from the stack.
Operations:
1. Push: By this operation one can push elements onto the stack. Before
performing push we must check stfull () condition.
2. Pop: By this operation one can remove the elements from stack. Before popping
the elements from stack we should check stempty() condition.
Implementation of Stack
• A stack is a special case of an ordered list, i.e. it is a ordered list with some
restrictions on the way in which we perform various operations on a list.
• We need an integer variable top which will keep track of the top of the stack as
more and more elements are inserted into and deleted from the stack.
In the above declaration stack is nothing but an array of integers. And most recent
index of that array will act as a top.
The stack is of the size 100. As we insert the numbers, the top will get
incremented. The elements will be placed from oth position in the stack. At the
most we can store 100 elements in the stack, so at the most last element can be
at (size - 1) position, i.e. at index 99.
#define size 10
struct stack {
int s[size];
}st;
In the above declaration stack is declared as a structure.
Now compare declaration 1 and 2. Both are for stack declaration only. But the
second declaration will always preferred. Why? Because in the second declaration
we have used a structure for stack elements and top. By this we are binding or co-
relating top variable with stack elements. Thus top and stack are associated with
each other by putting them together in a structure. The stack can be passed to the
function by simply passing the structure variable.
We will make use of the second method of representing the stack in our program.
• For example if we want to store marks of all the students of forth semester we
can declare a structure of stack as follows
# define size 60
int roll.no;
char name[30];
float marks;
}stud;
stud S1[size];
• Thus we can store the data about whole class in our stack.
• Hence we will write only push and pop function to implement the stack.
• Elements may be pushed onto the stack and there may be a case that all the
elements are removed from the stack. Then the stack becomes empty.
int stempty()
if(st.top==-1)
return 1;
else
return 0;
• As we go on inserting the elements the stack gets filled with the elements.
• Stack full condition is achieved when stack reaches to maximum size of array.
int stfull()
if(st.top>=size-1)
return 1;
else
return 0;
• push is a function which inserts new element at the top of the stack. The
function is as follows.
• Note that the push function takes the parameter item which is actually the
element which we want to insert into the stack - means we are pushing g the
element onto the stack.
• In the function we have checked whether the stack is full or not, if the stack is
not full then only the insertion of the element can be achieved by means of push
operation.
• Now let us discuss the operation pop, which deletes the element at the top of
the stack. The function pop is as given below -
int pop()
int item;
item = st.s[st.top];
st.top--;
return(item);
• The value at the top is stored in some variable as item and it then decrements
the value of the top, which now points to the element which is just under the
element being retrieved from the stack.
• Finally it returns the value of the element stored in the variable item. Note that
this is what called as logical deletion and not a physical deletion, i.e. even when
we decrement the top, the element just retrieved from the stack remains there
itself, but it no longer belongs to the stack. Any subsequent push will overwrite
this element.
Key Point If stack is empty we cannot pop and if stack is full we cannot push any
element.
4. Implementation
/*************************************************************
Program for implementing a stack using arrays. It involves various operations such
as push,pop,stack empty, stack full and display.
*************************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 5
/* stack structure*/
struct stack {
int s[size];
int top;
}st;
int stfull()
if(st.top>=size-1)
return 1;
else
return 0;
st.top++;
st.s[st.top] = item;
int stempty()
if(st.top ==-1)
else
return 1;
else
return 0;
int pop()
int item;
item=st.s[st.top];
st.top--;
return(item);
}
/*
Input:none
Called By:main
Calls:none
*/
void display()
int i;
if(stempty())
else
printf("\n%d", st.s[i]);
void main(void)
int item,choice;
char ans;
st.top=-1;
clrscr();
do
printf("\n1.Push\n2.Pop\n3.Display\n4.exit");
scanf("%d", &choice);
switch(choice)
scanf("%d", &item);
else
push(item);
break;
else
{
item=pop();
break;
case 3:display();
break;
case 4:exit(0);
ans=getche();
getch();
/******End Of Program****************?
Output
Implementation Of Stack
Main Menu
1. Push
2. Pop
3. Display
4. exit
Main Menu
1. Push
2. Pop
3. Display
4. exit
Main Menu
1. Push
2. Pop
3. Display
4. exit
20
10
Main Menu
1. Push
2. Pop
3. Display
4. exit
Main Menu
1. Push
2. Pop
3. Display
4. exit
Main Menu
1. Push
2. Pop
3. Display
4. exit
Empty stack!Underflow !!
1. Expression conversion
2. Expression evaluation
5. Reversing a string
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 5
/* stack structure*/
struct stack {
char s[size];
{
st.top++;
st.s[st.top] = item;
int stempty()
if(st.top==-1)
return 1;
else
return 0;
char pop()
char item;
item=st.s[st.top];
st.top--;
return(item);
void main(void)
char item;
char ans,bracket[10];
int i; 80
st.top=-1;
clrscr();
scanf("%s", bracket);
i=0;
if(bracket[i]==')')
else
do
while(bracket[i]=='')
push(bracket[i]);
i++;
}while(bracket[i]==')')
item=pop();
i++;
} while(bracket[i]!='$');
if(!stempty())
else
getch();
Output
Expression
Expression is a string of operands and operators. Operands are some numeric
values and operators are of two types: Unary operators and Binary operators.
Unary operators are '+' and '-' and binary operators are '+', '-', '*', '/' and exponential.
In general, there are three types of expressions:
One of the application of stack is conversion of expression. First of all, let us see
these expressions with the help of examples :
1. Infix Expression :
1. (a+b)
2 (a+b) * (c-d)
3. (a+b/e) * (d+f).
Parenthesis can be used in these expressions. Infix expression are the most natural
way of representing the expressions.
2. Postfix Expression :
For example
1. ab+
2. ab + cd - *
3. ab+e/df + *
3. Prefix Expression :
For example
1. + ab
2. *+ ab - cd
3. */ +abe + df
In prefix expression, there is no parenthesis used. All the corresponding operators
come first and then operands are arranged.
2. If '(' is read, then simply push it onto the stack. Because the ( has highest priority
when read as an input.
3. If ')' is reads, then pop all the operands until ( is read. Discard (. Store the
popped characters in the postfix array.
1. If instack operator has greatest precedence (or equal to) over the incoming
operator then pop the operator and add it to postfix expression. Repeat this step
until we get the instack operator of higher priority than the current incoming
operator. Finally push the incoming operator onto the stack
The priorities of different operators when they are in stack will be called instack
operators and the priorities of different operator when they are read from input
will be called as incoming priorities. These priorities are as given below -
Note that higher value represents higher priority.
Sol. :
Ex. 4.6.2: Obtain the postfix expression for (A+B)*(C-D)$.
Sol. :
When closing parenthesis comes pop everything and print except '("
Ex. 4.6.3: Write an algorithm to convert an infix to postfix expression Trace the
algorithm to convert the infix expression "(a+b)*c/d+elf" to a postifx
expression. Explain the need for infix and postfix expressions.AU: May-14,
Marks 16
Sol. :
The infix expressions are used in mathematical expressions and postfix expressions
are used in compilers for checking the syntax of an expression. The postfix
expressions are also used in evaluating the expressions.
Ex. 4.6.4: Convert the following infix expression to the postfix expression. Show
stack traces. (i) A/B$C+D*E/F-G+H (ii) (A+B) *D+E/(F+G*D)+C.
Sol.: (i)
(ii)
Ex. 4.6.5: Show the simulation using stack for the following expression to
convert infix to postfix: p q + (r-s/t) AU: May-16, Marks 6
Ex. 4.6.6 Simulate the conversion of infix to postfix expression using stack for
the following expression : 3-(4/2)+(1*5)+6 AU: Dec.-16, Marks 8
Sol. :
The equivalent postfix expression is 342/-15*+6+
Ex. 4.6.7 Conversion of infix expression to postfix using C.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 20
char stk[SIZE];
char in[SIZE],post[SIZE];
int top=-1;
top++;
stk[top] = item;
char pop()
char temp;
temp = stk[top];
top--;
return temp;
int stempty()
{
if(top==-1)
return 1;
else
return 0;
void inTopost();
int precedence(char);
int main()
gets(in);
inTopost();
return 0;
switch(ch)
case '/':
case '*':
return 2;
case '+':
case '-':
return 1;
default: return 0;
void inTopost()
int i,j=0;
char ch,next_ch;
for(i=0;i<strlen(in);i++)
ch= in[i];
switch(ch)
break;
case ')':while((next_ch=pop())!='()
break;
case '+':
case '-':
case '*':
case '/':
vns be post[j++]=pop(); r
push(ch);//else partn
break;
while(!stempty())
post[j++]=pop();
post [j]='\0';
for(i=0;i<strlen(post);i++)
printf("%c",post[i]);
Output
ab+cd-*
As we have seen how to convert given infix expression to postfix form. It's the
time to learn an evaluation of postfix expression. Again use of stack is necessary in
postfix expression evaluation. But here we will use the stack for storing operands
rather than operators. Operands are taken as numeric values. Let us see an
algorithm first,
3. If the operator is read POP two operands and perform arithmetic operations if
operator is
Sol. Now as per the algorithm of postfix expression evaluation, we scan the input
from left to right. If operand comes we push them onto the stack and if we read any
operator, we must pop two operands and perform the operation using that operator.
Here $ is taken as exponential operator.
Now since there is no further input we should pop the contents of stack and print it
as a result of evaluation.
Sol. :
/******************************************************************
******************************************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define size 80
struct stack
double s[size];
int top;
}st;
void main()
{
char exp[size];
int len;
double Result;
double post();
clrscr();
scanf("%s", exp);
len = strlen(exp);
Result = post(exp);
getch();
exit(0);
char ch,*type;
void push(double);
double pop();
int i;
st.top = 0;
i=0;
ch = exp[i];
type="operand";
type="operator";
val=ch- 48;
push(val); The characters '0', '1', ... '9' will be converted to their values, so that they
will perform arithmatic operation
else
op1 = pop();
switch(ch)
}
case '+' result = op1 + op2;
break;
break;
break;
break;
break;
}/* switch */
i++;
ch=exp[i];
} /* while */
return(result);
st.top++;
st.s[st.top] = val;
double pop()
double val;
if(st.top == -1)
printf("\nStack is Empty\n");
val = st.s[st.top];
st.top--;
return(val);
Output
12+34*+
Let us take some example of postfix expression and try to evaluate it 123+*
Step 4:
At this point the stack is empty and the input is read as $. So here stop the
evaluation procedure and return the result = 5.
Step 1: Read expression from left to right. Go on pushing operands onto the stack.
When operator is read, pop two operands and form prefix expression push it onto
the stack.
Ex. 4.7.4 : Evaluate the following expression using stack 5 6 2 + * 84/- AU:
Dec.-15, Marks 2
Sol. :
Conversion of A-(B/C+(D%E*F)/F)*H
Postfix Form : A B C / DE F *% F/ + H * -
Review Question
1. Discuss any two applications of stack with relevant examples. AU: Dec.-15,
Marks 16
Concept of Queue
• Definition :
The queue can be formally defined as ordered collection of elements that has two
ends named as front and rear. From the front end one can delete the elements
and from the rear end one can insert the elements.
• For Example :
The typical example can be a queue of people who are waiting for a city bus at the
bus stop. Any new person is joining at one end of the queue, you can call it as the
rear end. When the bus arrives the person at the other end first enters in the bus.
You can call it as the front end of the queue.
Queue ADT
AbstractData Type Queue
Operations :
1. Insert : The insertion of the element in the queue is done by the end called rear.
Before the insertion of the element in the queue it is checked whether or not the
queue is full.
2. Delete: The deletion of the element from the queue is done by the end called
front. Before performing the delete operation it checked whether the queue is
empty or not.
Queue Implementation
AU: May-15, Marks 16
• Queue is nothing but the collection of items. Both the ends of the queue are
having their own functionality.
• The Queue is also called as FIFO i.e. a First In First Out data structure.
1.Queue overflow.
3.Queue underflow.
struct queue
int front;
int rear;
}Q;
The insertion of any element in the queue will always take place from the rear end.
We have inserted first 10, then 20, then 30, then 40, then 50, in the queue.
Before performing insert operation you must check whether the queue is full or
not. If the rear pointer is going beyond the maximum size of the queue then the
queue overflow Occurs.
The deletion of any element in the queue takes place by the front end always.
/******************************************************************
***************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define size 5
struct queue Queue data structure declared with array que[], front and rear
int que[size];
int front,rear;
}Q;
/*
Qfull()
if(Q.rear >=size-1) If Queue exceeds the maximum size of the array then it returns
1 - means queue full is true otherwise 0 means queue full is false
return 1;
else
return 0;
/*
*/
if(Q.front == -1)
Q.front++;
Q.que[++Q.rear] = item; Always increment the rear pointer and place the element
in the queue
return Q.rear;
int Qempty()
{
if((Q.front == -1) || (Q.front > Q.rear))
*/
void display()
int i;
printf("%d", Q.que[i]);
void main(void)
{
int choice,item;
char ans;
clrscr();
Q.front =-1;
do
printf("\n1.Insert\n2.Delete\n3.Display");
scanf("%d", &choice);
switch(choice)
else
{
printf("\n Enter The number to be inserted");
scanf("%d",&item);
insert(item);
break;
case 2:if(Qempty())
else
delet();
break;
case 3:if(Qempty())
printf("\nQueue Is Empty!");
else
display();
break;
break;
ans = getche();
}
/**************************End Of Program ***************/
Output
Main Menu
1. Insert
2. Delete
3. Display
Main Menu
1. Insert
2. Delete
3. Display
Main Menu
1. Insert
2. Delete
3. Display
10 20
Do You Want to continue?y
Main Menu
1. Insert
2. Delete
3. Display
Main Menu
1. Insert
2. Delete
3. Display
20
Key Point Always check queue full before insert operation and queue empty
before delete operation.
Ex. 4.10.2: Write a C program to implement queue functions using arrays and
macros. AU: May-15, Marks 16
Sol. :
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
/* Macro definitions */
#define size 5
struct queue
int front,rear;
}Q;
Qfull()
if(Isfull)
return 1;
else
return 0;
if(Q.front ==-1)
Q.front++;
Q.que[++Q.rear] = item;
return Q.rear;
int Qempty()
if(Isempty)
return 1;
else
return 0;
int delet()
int item;
item = Q.que[Q.front];
Q.front++;
return Q.front;
void display()
int i;
for(i=Q.front;i<=Q.rear;i++)
printf("%d", Q.que[i]);
void main(void)
int choice,item;
char ans;
Q.front = -1;
Q.rear =-1;
do
printf("\n1.Insert\n2.Delete\n3.Display");
scanf("%d", &choice);
switch(choice)
else
scanf("%d", &item);
insert(item);
break;
case 2:if(Qempty())
else
delet();
break;
case 3:if(Qempty())
printf("\nQueue Is Empty!");
else
display();
break;
break;
ans = getche();
Review Question
1. Develop an algorithm to implement Queue ADT. Give relevant examples and
diagrammatic representations.AU: May-16, Marks 12
Priority Queues
AU: Dec.-19, Marks 15
1. The typical example of priority queue is scheduling the jobs in operating system.
Typically operating system allocates priority to jobs. The jobs are placed in the
queue and position of the job in priority queue determines their priority. In
operating system there are three kinds of jobs. These are real time jobs, foreground
jobs and background jobs. The operating system always schedules the real time
jobs first. If there is no real time job pending then it schedules foreground jobs.
Lastly if no real time or foreground jobs are pending then operating system
schedules the background jobs.
The elements in the priority queue have specific ordering. There are two types of
priority queues -
1. Ascending priority queue: An ascending order priority queue gives the highest
priority to the lower number in that queue.
2. Descending priority queue: A descending order priority queue gives the
highest priority to the highest number in that queue.
In priority queue, the elements are arranged in any order and out of which only the
smallest or largest element allowed to delete each time.
The implementation of priority queue can be done using arrays or linked list. The
data structure heap is used to implement the priority queue effectively.
1. Insertion
2. Deletion
3. Display
Instances:
The front and rear should be within the maximum size MAX.
Before any deletion operation, whether the queue is empty or not is checked.
Operations :
1. create() - The queue is created by declaring the data structure for it.
3. delet() - If the priority queue is ascending priority queue then only smallest
element is deleted each time. And if the priority queue is descending priority queue
then only largest element is deleted each time.
1. Insertion operation
While implementing the priority queue we will apply a simple logic. That is while
inserting the element we will insert the element in the array at the proper position.
For example, if the elements are placed in the queue as
int item,j;
scanf("%d", &item);
if(front ==-1)
front++;
j=rear;
quelj+1]=que[j];
j- -;
que[j+1]=item;
rear=rear+1;
return rear;
}
2. Deletion operation
In the deletion operation we are simply removing the element at the front.
int item;
item=que[front];
front++;
return front;
Sol. :
/
******************************************************************
Program for implementing the ascending priority Queue
**************************************************************/
/*Header Files*/
#include<stdio.h>
#include<conio.h>
#define SIZE 5
void main(void)
char ans;
clrscr();
front=0;
rear=-1;
do
clrscr();
printf("\n1.Insert\n2.Delete\n3.Display");
scanf("%d", &choice);
switch(choice)
case 1:if(Qfull(rear))
else
rear=insert(que,rear, front);
break;
else
front=delet(que, front);
break;
display(que,rear, front);
break;
break;
ans =getche();
getch();
int item,j;
scanf("%d", &item);
if(front = = -1)
front++;
j=rear;
que[j+1]=que[j];
j- -;
que[j+1]=item;
rear=rear+1;
return rear;
if(rear==SIZE-1)
return 1;
else
return 0;
int item;
item=que[front];
front++;
return front;
if((front==-1) | | (front>rear))
return 1;
else
return 0;
int i;
for(i=front;i<=rear;i++)
printf("%d",que[i]);
Output
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Output
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Enter Your Choice: 1
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Enter Your Choice: 2
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Enter Your Choice: 2
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Priority Queue
Main Menu
1.Insert
2.Delete
3.Display
Queue is empty
Ex. 4.11.2: Write program for implementing the linked priority queue.
Sol. :
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int data;
}Q;
Q *front, *rear;
/*
*/
void main(void)
char ans;
int choice;
void insert();
Q *delet();
front= NULL;
rear= NULL;
do
printf("\n1.Insert\n2.Delete \n3.Display");
scanf("%d", &choice);
switch(choice)
case 1 : insert();
break;
break;
case 3 :display(front);
break;
break;
flushall();
ans = getch();
clrscr();
/*
*/
Q *get_node(Q *temp)
temp =(Q*)malloc(sizeof(Q));
temp->next = NULL;
return temp;
/*
*/
void insert()
char ch;
scanf("%d",&temp->data);
/*The new node which is to be inserted is temp */
front= temp;
rear=temp;
current=front;
prev=current;
if(current->data>temp->data)
temp->next=current;
front=temp;/*update front*/
else
{
/*prev is previous to current node */
prev=current;
current=current->next;
}/*end of while*/
if(current)
prev->next=temp;
temp->next = current;
/*attaching temp as a last node when temp has greaest among all the nodes in the
list and we have reached at the end of the list*/
else
prev->next=temp;
/*
Q *delet()
Q *temp;
temp=front;
if(Qempty(front))
else
temp->next = NULL;
free(temp);
return front;
/*
if(front== NULL)
return 1;
else
return 0;
/*
Called By:main
Calls:QEmpty
*/
if(Qempty(front))
else
printf("\t%d ",front->data);
getch();
Output
Main Menu
1.Insert
2.Delete
3.Display
Main Menu
1.Insert
2.Delete
3.Display
Main Menu
1.Insert
2.Delete
3.Display
15
Main Menu
1.Insert
2.Delete
3.Display
Main Menu
1.Insert
2.Delete
3.Display
12
Main Menu
1.Insert
2.Delete
3.Display
7 9 11 12 15
Main Menu
1.Insert
2.Delete
3.Display
Main Menu
1.Insert
2.Delete
3.Display
Main Menu
1.Insert
2.Delete
3.Display
11 12 15
1. Insertion of a node
Initially queue will be empty and if we want to insert the first node. Then first
memory will get allocated for temp node as :
temp = get_node();
if (front== NULL)
front = temp;
rear = temp;
Now, if want to insert next item say 11 then we will create temp node as
Then we will start scanning the queue from beginning because we want to insert
node with '11' at proper place.
While((current → data < temp → data)&&(current != NULL))
prev = current;
current = NULL;
else
rear = temp;
}
Now if we want to insert temp node with value '7' in the linked queue then we will
find the position for temp node in linked queue.
front = temp;
2. Deletion of a node
temp=front;
Review Question
Applications of Queue
AU: Dec.-19, Marks 15
1. Job Scheduling
• Some programs which are not executing but they are in a position to get executed
at any time such programs are in the 'ready' state.
• And there are certain programs which are neither in running state nor in ready
state. Such programs are in a state called as 'blocked' state.
• The operating system maintains a queue of all such running state, ready state,
blocked state programs. Thus use of queues help the operating system to schedule
the jobs.
• The jobs which are in running state are removed after complete execution of each
job, then the jobs which are in ready state change their state from ready to running
and get entered in the queue for running state.
• Similarly the jobs which are in blocked state can change their state from blocked
to ready state.
• These jobs then can be entered in the queue for ready state jobs.
• Thus every job changes its state and finally get executed. Refer Fig. 4.12.1.
• Thus queues are effectively used in the operating system for scheduling the jobs.
Categorizing Data
• The queue can be used to categorize the data.
• The typical example for categorizing the data is our college library.
• These sections are like multiple queues in which appropriate data (books) are
stored. Thus categorization of data can be possible using multiple queues.
Ex. 4.12.1: There are 'N' numbers of balls in the box. The colors of the balls are
red and blue. You are requested to stack the balls in the bottom sealed basket
one by one. The order of placing the balls is two consecutive red balls followed
by two consecutive blue balls. Later create two empty queues Q1 and Q2.
Remove the last inserted balls from the basket and place it in Q1. Similarly
remove the next inserted balls from the basket and insert it in Q2. Develop a
program to repeat this process until the basket is empty and also print the color
of the balls in both queues. AU: Dec.-19, Marks 15
Sol. :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 25
/* stack structure*/
struct stack
char s[size];
int top;
}st;
struct queue
char que[size];
int front,rear;
}Q1, Q2;
int stfull()
if(st.top>=size - 1)
return 1;
else
return 0;
void push()
for(int i=0;i<2;i++)
st.top++;
st.s[st.top]='r';
for(int i=0;i<2;i++)
{
st.top++;
st.s[st.top]='b'; tex
int stempty()
if(st.top== -1)
return 1;
else
return 0;
char pop()
char item;
item=st.s[st.top];
st.top--;
return(item);
if(Q1.front == -1)
Q1.front++;
Q1.que[++Q1.rear] = item;
if(Q2.front == -1)
Q2.front++;
Q2.que[++Q2.rear] = item;
int i;
for(i=Q.front;i<=Q.rear;i++)
printf("%c",Q.que[i]);
void display_stack()
int i;
if(stempty())
else
for(i=st.top;i>=0;i - -)
printf("\n%c", st.s[i]);
int main(void)
int choice;
char ans,item;
st.top = -1;
Q1.front= -1;
Q1.rear= -1;
Q2.front= -1;
Q2.rear =1;
do
switch(choice)
case 1:if(stfull())
int i;
for(i=Q.front;i<=Q.rear;i++)
printf("%c",Q.que[i]);
void display_stack()
int i;
if(stempty())
else
for(i=st.top;i>=0;i — −)
printf("\n%c", st.s[i]);
}
int main(void)
int choice;
char ans,item;
st.top = -1;
Q1.front = -1;
Q1.rear = -1;
Q2.front = -1;
Q2.rear = -1;
do
scanf("%d", &choice);
switch(choice)
case 1:if(stfull())
else {
push();
display_stack();
}
break;
case 2:if(stempty())
else
while(!stempty())
item=pop();
insert_Queue1(item);
item=pop();
insert_Queue2(item);
display_queue(Q1);
display_queue(Q2);
printf("\n----------------------\n");
display_stack();
break;
case 3:exit(0);
}
ans=getche();
getch();
return 0;
Output
Main Menu
2.Pop
3.exit
Main Menu
2.Pop
3.exit
Enter Your Choice: 2
Ball is popped
Inserting ball in Q1
Ball is popped og r
Inserting ball in Q2
Displaying Queue1...
Displaying Queue2...
------------------------
Ball is popped
Inserting ball in Q1
Ball is popped
Inserting ball in Q2
Displaying Queue1...
br
Displaying Queue2...
br
--------------------------
Stack Is Empty!
Ans. : In computer system the memory model consists of stack memory stores
types of variables that have a fixed lifetime based on how C programs run. It is a
section of RAM that grows and shrinks as the program runs. When you call a
function, its parameters and any variables you have defined in that function (which
are not static) are stored on the stack.
Ans. : This is also called as prefix notation. In this type of notation the operator
followed by two operands. For example if (a+b)*c is a given expression then its
polish notation will be *+ abc.
Ans. : The top denotes the only one end of the stack from which the element can
be inserted or deleted. When we push the element onto the stack, the top is
incremented. When we pop the element from the stack the top is decremented.
Ans.: Following steps can be followed for computing the postfix expression -
Step 1: (AB+)*C-(D-E)^F
Step 2: (AB+C*)-(D-E)^F
Step 3: (AB+C*)-(DE-)^F
Step 4: (AB+C*)-(DE-F^)
Step 5: AB+C*DE-F^-
Q. 5 Write any two applications of stack. AU: Dec.-14, 18, 19
Ans. :
1. Insertion and deletion can be made by one end only. Hence the element inserted
last will be first one to come out. Hence sometimes it is called LIFO.
Ans. : The stack is an useful data structure for handling the recursive function
calls. When a recursive call is encountered, the status of call is pushed onto the
stack. And at the return of the call the stack is popped off. Thus execution of
recursive statements is done with the help of stack.
Q. 8 What is Last-In-First-Out strategy? Which data structure follows this
strategy?
Ans. : In the Last In First Out strategy we insert the element in the data structure
lastly and while removing the elements from this data structure, the element which
is inserted lastly will get removed first.
The stack data structure makes use of Last In First Out(LIFO) data structure.
Q. 9 Write the steps to reverse the contents of the list with the help of stack data
structure.
Ans. :
Step 1: Read each element from the list and push it onto the stack.
Step 2: Pop the element from the stack and store the popped element in a separate
Step 3: Read the array completely from left to write. This will be the reversed list
of the elements.
Q. 11 Given the prefix for an expression write its postfix. AU: May-15
-*-+abc/ef-g/hi
Ans. :
-*-+abc/ef-g/hi
- * - T1 cef-g/hi T1 = ab+
-T2/ef-g/hi T2 = T1c-
- T2 T3 g/hi T3=ef /
- T4g-/hi T4 = T2T3*
- T4 g T5 T5 = hi/
T7 T7= T4 T6
By backward substitution,
T7
T4 T6-
T2 T3 T6 -
T1 c T3 * T6 -
ab + c - T3 * T6 -
ab + c –ef/*t6-
ab + c -ef/* g T5--
AU: May - 19
Ans. :
The required postfix expression is abc*def++g/+.
Q. 14 State the rules to be followed during infix to postfix conversion. AU: Dec.-
19
Ans. : The LIFO stands for Last In First Out. This property belongs to stack. That
means the element inserted lastly will be the element to be popped off first from
the stack.
The FIFO stands for First In First Out. This property belongs to queue. That means
the element inserted first in the queue will be the first to get deleted.
Ans. : The front end of the queue from which the element gets deleted is called
front and the end from which the element is inserted in the queue is called rear. is
called rear.roA For example: Refer Fig. 4..10.1.
Ans. :
2. In Local Area Network (LAN) multiple computers share few printers. Then
these printers accumulate jobs in a queue. Thus printers can process multiple print
commands with the help of queues.
Ans. : The dequeue is a data structure in which the element can be inserted from
both the ends i.e. front and rear. Similarly, the element can be deleted from both
the front and rear end.
if((Q.front==-1) | | (Q.front>Q.rear))
else
Ans. :
AU: Dec.-15
Ans. :
Stack is linear data structure in which insertion and deletion of element is from one
end called top.
Queue is a linear data structure in which insertion of element is from one end
called rear and deletion of element is from other end called front.
Q. 22 What are priority queues? What are the ways to implement priority
queue?
AU: Dec.-18
Ans. :
Unit IV
Chapter 5
a. Non-Linear Data Structures – Trees
Syllabus
Trees - Binary Trees - Tree Traversals - Expression Trees - Binary Search Tree.
Contents
5.1 Trees
Trees
A tree is a finite set of one or more nodes such that -
ii) The remaining nodes are partitioned into n> = 0 disjoint sets T1, T2,T3...Tn where
T1, T2,T3...Tn are called the sub-trees of the root.
1. Creation of a tree
1. Basic Terminologies
Let us get introduced with some of the definitions or terms which are normally
used.
From Fig. 5.1.2,
1. Root
Root is a unique node in the tree to which further subtrees are attached. For
above given tree, node 10 is a root node.
2. Parent node
The node having further sub-branches is called parent node. In Fig. 5.1.3 the 20 is
parent node of 40, 50 and 60.
3. Child nodes
The child nodes in above given tree are marked as shown below -
4. Leaves
For example -
The total number of subtrees attached to that node is called the degree of a node.
For example.
6. Degree of tree
The maximum level is the height of the tree. In Fig. 5.1.8 the height of tree is 3.
Sometimes height of the tree is also called depth of tree.
9. Predecessor
While displaying the tree, if some particular node occurs previous to some other
node then that node is called predecessor of the other node.
For example: While displaying the tree in Fig. 5.1.8 if we read node 20 first and
then if we read node 40, then 20 is a predecessor of 40.
10. Successor
For example: While displaying tree in Fig. 5.1.8 if we read node 60 after reading
node 20 then 60 is called successor of 20.
Leaf node means a node having no child node. As leaf nodes are not having
further links, we call leaf nodes External nodes and non leaf nodes are
called internal nodes.
12. Sibling
For example
In this chapter we will deal with special type of trees called binary trees. Let us
understand it.
Binary Trees
• Definition of a binary tree: A binary tree is a finite set of nodes which is either
empty or consists of a root and two disjoint binary trees called the left subtree and
right subtree.
• The binary tree can be as shown below -
Instances : Binary tree is a nonlinear data structure which contains every node
except the leaf nodes at most two child nodes.
Operations:
1. Insertion :
This operation is used to insert the nodes in the binary tree. By inserting desired
number of nodes, the binary tree gets created.
2. Deletion :
This operation is used to remove any node from the tree. root node is removed
the tree becomes empty.
• A full binary tree is a tree in which every node has zero or two children.
• In other words, the full binary tree is a binary tree in which all the nodes have
two children except the leaf node. (Refer Fig. 5.2.3)
• The complete binary tree is a binary in which all the levels are completely filled
except the last level which is filled from left.
• There are two points to be remembered
1) The leftmost side of the leaf node must always be filled first.
2) It is not necessary for the last leaf node to have right sibling.
• Note that in above representation, Treel is a complete binary tree in which all
the levels are completely filled, whereas Tree2 is also a complete binary tree in
which the last level is filled from left to right but it is incompletely filled.
1. Sequential representation
2. Linked representation.
representation :
Each node is sequentially arranged from top to bottom and from left to right. Let
us understand this matter by numbering each node. The numbering will start
from root node and then remaining nodes will give ever increasing numbers in
level wise direction. The nodes on the same level will be numbered from left to
right. The numbering will be as shown below.
Now, observe Fig. 5.3.1 carefully. You will get a point that a binary tree of depth n
having 2n-1 number of nodes. In Fig. 5.3.1 the tree is having the depth 4 and total
number of nodes are 15. Thus remember that in a binary tree of depth n there
will be maximum 2n-1 nodes. And so if we know the maximum depth of the tree
then we can represent binary tree using arrays data structure. Because we can
then predict the maximum size of an array that can accommodate the tree.
Thus array size can be > = n. The root will be at index 0. Its left child will be at
index 1, its right child will be at index 2 and so on. Another way of placing the
elements in the array is by applying the formula as shown below -
• Parent(n) = floor(n-1)/2
• Left(n) = (2n+1)
• Right(n) = (2n+2).
Advantages of sequential representation
The only advantage with this type of representation is that the direct access to
any node can be possible and finding the parent, left or right children of any
particular node is fast because of the random access.
For example In the skewed tree half of the array is unutilized. You can easily
understand this point simply by seeing Fig. 5.3.3.
2. In this type of representation the maximum depth of the tree has to be fixed
because we have already decided the array size. If we choose the array size quite
larger than the depth of the tree, then it will be wastage o of the memory. And if
we choose array size lesser than the depth of the tree then we will be unable to
represent some part of the tree.
3. The insertions and deletion of any node in the tree will be costlier as other
nodes have to be adjusted at appropriate positions so that the meaning of binary
tree can be preserved.
As these drawbacks are there with this sequential type of representation, we will
search for more flexible representation. So instead of array we will make use of
linked list to represent the tree.
trees
In binary tree each node will have left child, right child and data field.
The left child is nothing but the left link which points to some address of left
subtree whereas right child is also a right link which points to some address of
right subtree. And the data field gives the information about the node. Let us see
the 'C' structure of the node in a binary tree.
int data;
}bin;
2. Insertions and deletions which are the most common operations can be done
without moving the other nodes.
Disadvantages of linked representation
1. This representation does not provide direct access to a node and special
algorithms are required.
2. This representation needs additional space in each node for storing the left and
right sub-trees.
Ex. 5.3.1: For the given data draw a binary tree and show the array
representation of the same: 100 80 45 55 110 20 70 65
where n > 0.
Ex. 5.3.2: What is binary tree? Show the array representation and linked
representation for the following binary tree.
Sol. Binary Tree : Binary Tree is a finite set of nodes which is either empty or
consists of a root and two disjoint binary trees called left subtree and right
subtree.
Array Representation
Linked Representation
Tree Traversal
AU: Dec.-19, Marks 13 grej)rabroni
• Basically there are six ways to traverse a tree. For these traversals we will use
following notations :
• Thus with L, R, D we will have six combinations such as LDR, LRD, DLR,
DRL, RLD, RDL.
1) Inorder Traversal :
In this type of traversal, the left node is visited, then parent node and then right
node is visited.
For example
Algorithm :
if(temp!= NULL)
printf("%d", temp->data);
2) Preorder Traversal :
In this type of traversal, the parent node or root node is visited first; then left node
and finally right node will be visited.
For example
Algorithm:
if(temp!= NULL)
preorder(temp->left);
3) Postorder Traversal :
In this type of traversal, the left node is visited first, then right node and finally
parent node is visited.
For example
Algorithm:
if(temp!= NULL)
postorder(temp->left);
postorder(temp->right);
printf("%d",temp->data);
}
Ex. 5.4.1: Write inorder, preorder and postorder traversal for the following tree:
Sol. :
Inorder 8 10 11 30 20 25 40 42 45 60 50 55
Preorder 40 30 10 8 11 25 20 50 45 42 60 55
Postorder 8 11 10 20 25 30 42 60 45 55 50 40.
Sol.:
/******************************************
Program for creation of a binary tree and display the tree using recursive inorder,
preorder and post order traversals
********************************************/
#include <stdio.h>
#include <alloc.h>
#include<conio.h>
int data;
node *get_node();
void main()
int choice;
char ans='n';
node *New,*root;
root=NULL;
clrscr();
do
printf("\n 1.Create");
printf("\n 2.Inorder");
printf("\n 4.Postorder");
printf("\n 5.Exit");
scanf("%d", &choice);
switch(choice)
do
New=get_node();
scanf("%d", &New->data);
if(root == NULL)
root=New;
else
insert(root,New);
ans=getche();
clrscr();
break;
else
inorder(root);
break;
else
preorder(root);
break;
else
postorder(root);
break;
} while (choice!=5);
node *get_node()
node *temp;
temp->left = NULL;
temp->right = NULL;
return temp;
char ch;
ch=getche();
if ((ch=='r') || (ch=='R'))
if(root->right == NULL)
{
root->right=New;
else
insert(root->right,New);
else
if (root->left== NULL)
root->left=New;
else
insert(root->left, New);
if(temp!= NULL)
inorder(temp->left);
printf("%d",temp->data);
inorder(temp->right);
}
if(temp!= NULL)
printf("%d",temp->data);
preorder(temp->left);
preorder(temp->right);
if(temp!= NULL)
postorder(temp->left);
postorder(temp->right);
printf("%d",temp->data);
Output
2. Inorder
3. Preorder
4. Postorder
5. Exit
1.Create
2.Inorder
3.Preorder
4.Postorder
5.Exit
12 8 10 17
1.Create
2.Inorder
3.Preorder
4.Postorder
5.Exit
10 12 8 17
1. Create
2. Inorder
3. Preorder
4. Postorder
5. Exit
8 12 17 10
1. Create
2. Inorder
3. Preorder
4. Postorder
5. Exit
Review Question
Expression Trees
AU: Dec.-18, Marks 15
Definition: An expression tree is a binary tree in which the operands are attached
as leaf nodes and operators become the internal nodes.
For example -
If we traverse the above tree in inorder, preorder or postorder then we get infix,
prefix or postfix expressions respectively.
Key Point: Inorder traversal of expression tree fives infix expression. The preorder
traversal of expression tree gives prefix expression and post order traversal of
expression tree gives postfix expression.
Now we will read each symbol from left to right one character at a time. If we
read an operand then we will make a node of it and push it onto the stack. If we
read operator then pop two nodes from stack, the first popped node will be
attached as right child to operator node and second popped node will be attached
as a left child to operator node. For the above given expression let us build a tree.
Now as we read '+' pop two operands and attach them as follows -
Next we read '*'. Hence pop two nodes from the stack and attach them to * node.
As now we read '\0', pop the content of stack. The node which we will get is the
root node of an expression tree.
Let us implement it
Ex. 5.5.1: Program for creating an expression tree and printing it using an
inorder traversal.
Sol. :
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <ctype.h>
#define size 20
char data;
}btree;
btree *stack[size];
int top;
void main()
{
btree *root;
clrscr();
scanf("%s",exp);
root create(exp);
display(root);
getch();
btree *temp;
int pos;
char ch;
btree *pop();
pos = 0;
ch = exp[pos];
if (isalpha(ch)) /* is it a operand */
*/
temp->right = pop();
push(temp);
else
temp = pop();
return(temp);
top++;
stack[top] = Node;
btree* pop()
btree *Node;
if (top = = -1)
Node = stack[top];
top--;
return(Node);
}
void display(btree *root)
btree *temp;
temp = root;
if (temp!= NULL)
display(temp->left);
printf("%c", temp->data);
display(temp->right);
Output
ab+cd-*
a+b * c - d
Ex. 5.5.2: Show the binary tree with arithmetic expression A/B * C * D + E. Give
the algorithm for inorder, preorder, postorder traversals and show the result of
these traversals.
Sol. :
Algorithm for inorder, preorder and postorder Traversal - Refer section 5.4.
Review Question
1. What are expression trees. Write the procedure for constructing an expression
tree.
Binary search tree is a binary tree in which the nodes are arranged in specific
order. That means the values at left subtree are less than the root node value.
Similarly the values at the right subtree are greater than the root node. Fig. 5.6.1
represents the binary search tree.
Algorithm:
1. Read the value for the node which is to be created and store it in a node
called New.
4. If (New->value < root->value) then attach New node as a left child of root
otherwise attach New node as a right child of root.
5. Repeat steps 3 aand 4 for constructing required binary search tree completely.
if(New->data <root->data)
root->left=New;
else
insert(root->left,New);
if(New->data>root->data)
if(root->right == NULL)
root->right=New; ← If the root node has already some left child, then move onto
left subtree.
else
insert(root->right,New);
srit aupaib au fo
While inserting any node in binary search tree, first of all we have to look for its
appropriate position in the binary search tree. We start comparing this new node
with each node of the tree. If the value of the node which is to be inserted is greater
than the otolob totes a value of current node we move onto the right subbranch
otherwise we move onto the left subbranch. As soon as the appropriate position is
found we attach this new node as left or right child appropriately.
In the Fig. 5.6.2 if we want to insert 23. Then we will start comparing 23 with
value of root node i.e. 6. As 23 is greater than 10, will will move on right subtree.
Now we will compare 23 with 20 and move right, compare 23 with 22 and move
right. Now compare 23 with 24 but it is less than 24. We will move on left branch
of 24. But as there is NULL node as left child of 24, we can attach 23 as left child
of 24.
2. Deletion of an element from the binary tree
For deletion of any node from binary search tree there are three cases which are
possible.
This is the simplest deletion, in which we set the left or right pointer of parent node
as NULL.
From the above tree, we want to delete the node having value 6 then we will set
left pointer of its parent node as NULL. That is left pointer of node having value 8
is set to NULL.
To explain this kind of deletion, consider a tree as shown in the Fig. 5.6.6.
If we want to delete the node 15, then we will simply copy node 18 at place of 15
and then set the node free. The inorder successor is always copied at the position of
a node being deleted.
iii. The node having two children
Again, let us take some example for discussing this kind of deletion.
Let us consider that we want to delete node having value 7. We will then find out
the inorder successor of node 7. The inorder successor will be simply copied at
location of node 7. Thats it!
That means copy 8 at the position where value of node is 7. Set left pointer of 9 as
NULL. This completes the deletion procedure.
void del(node *root,int key)
temp=search(root,key,&parent);
parent=temp;
while(temp_succ->left!= NULL)
parent=temp_succ;
temp_succ=temp_succ->left; ← Moving to leftmost subtree
if(temp_succ == parent->left)
parent->left = NULL;
else
parent->right = NULL;
return;
if(parent->left==temp)
else
parent->right-temp->left;
temp=NULL;
free(temp);
if(parent->left == temp)
parent->left-temp->right;
else
parent->right-temp->right;
temp=NULL;
free(temp);
return;
In searching, the node which we want to search is called a key node. The key node
will be compared with each node starting from root node if value of key node is
greater than current node then we search for it on right subbranch otherwise on left
subbranch. If we reach to leaf node and still we do not get the value of key node
then we declare "node is not present in the tree".
In the above tree, if we want to search for value 9. Then we will compare 9 with
root node 10. As 9 is less than 10 we will search on left subbranch. Now compare 9
with 5, but 9 is greater than 5. So we will move on right subbranch. Now compare
9 with 8 but as 9 is greater than 8 we will move on right subbranch. Now we read
the node value as 9. Thus the desired node can be searched. Let us see the 'C'
implementation of it.
node *temp;
temp=root;
while(temp!= NULL)
if(temp->data==key)
{
return temp;
else
temp-temp->right;
return NULL;
/*****************************************
*****************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int data;
}node;
void main()
int choice;
char ans='N';
int key;
node *get_node();
root = NULL;
clrscr();
do
{
printf("\n1.Create\n2.Search\n3.Delete\n4.Display");
scanf("%d", &choice);
switch(choice)
case 1:do
New get_node();
scanf("%d", &New->data);
root=New;
else
insert(root,New);
ans=getch();;
}while(ans= ='y');
break;
scanf("%d", &key);
tmp=search(root,key,&parent);
break;
scanf("%d", &key);
del(root,key);
break;
else
inorder(root);
break;
}while(choice!=5);
node *get_node()
node *temp;
temp->left=NULL;
temp->right=NULL;
return temp;
if(New->data <root->data)
if(root->left== NULL)
root->left=New;
else
insert(root->left,New);
if(New->data>root->data)
if(root->right == NULL)
root->right=New;
else
insert(root->right,New);
/*
This function is for searching the node from binary Search Tree
*/
node *temp;
temp=root;
while(temp!= NULL)
if(temp->data= =key)
return temp;
*parent=temp;
if(temp->data>key)
temp-temp->left;
else
temp-temp->right;
return NULL;
/*
This function is for deleting a node from binary search tree. There exists three
possible cases for deletion of a node
*/
temp=search(root,key,&parent);
parent=temp;
temp_succ-temp->right;
while(temp_succ->left!= NULL)
parent=temp_succ;
if(temp_succ = = parent->left)
parent->left = NULL;
else
parent->right = NULL;
printf(" Now Deleted it!");
return;
if(parent->left == temp)
parent->left=temp->left;
else
parent->right-temp->left;
temp=NULL;
free(temp);
return;
if(parent->left == temp)
else
parent->right-temp->right;
temp=NULL;
free(temp);
return;
:{
if(parent->left= =temp)
parent->left= NULL;
else
return;
/*
*/
if(temp!= NULL)
inorder(temp->left);
printf("%d",temp->data);
inorder(temp->right);
Output
1. Create
2. Search
3. Delete
4. Display
1. Create
2. Search
3. Delete
4. Display
1. Create
2. Search
3. Delete
4. Display
Parent of node 16 is 15
1. Create
2. Search
3. Delete
4. Display
Ex. 5.6.1 Define binary search tree. Draw the binary search tree for the
following input. 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
Example
Recursive Algorithm for search - Refer example 5.6.4.
Ex. 5.6.3: What is binary search tree? Draw the binary search tree for the
following input. 14, 5, 6, 2, 18, 20, 16, 18, -1, 21.
Example
Ex. 5.6.4: What is binary search tree? Write a recursive search routine for
binary search tree.
return temp;
else
if (key<temp.data)
else
return search(temp->right,key);
Ex. 5.6.5 Write the following routines to implement the basic binary search tree
operations
For finding the minimum value from the binary search tree, we need to traverse to
the left most node. Hence the left most node in above Fig. 5.6.11 is with value 7
which is the minimum value. Note that for the leftmost node the left pointer is
NULL.
The routine for finding the minimum value from the binary search tree is,
Find_min(node *root)
while(current->left != NULL)
current=current->left;
printf("%d", current->data);
For finding the maximum value from the binary search tree, we need to traverse to
the right most node. Hence the right most node in above Fig. 5.6.11 is with value
13 which is the maximum value. Note that for the rightmost node the right pointer
is NULL. The routine for finding the maximum value from the binary search tree is
Find_max(node *root)
{
struct node* current=root;
while(current->right != NULL)
current-current->right;
printf("%d", current->data);
Review Questions
2. Describe the binary search tree with an example. Write a iterative function to
search for the key value in binary search tree. esmito giarollo sit stiW 2.8.2
3. How to insert and delete an element into binary search tree and write down the
code for the insertion routine with an example. dose grandi moitos
Programming Examples
Ex. 5.6.6 Program for counting total number of nodes.
Sol. :
/********************************************
*********************************************/
#include<stdio.h>
#include <alloc.h>
#include<conio.h>
int data;
}bs;
bs *New,*root;
/*---------------------------------------------------
--------------------------------------------------------*/
void main()
char ans='N';
int cnt;
bs *get_node();
clrscr();
root = NULL;
do
New=get_node();
if(root = = NULL)
root=New;
else
insert(root,New);
ans=getch();
}while(ans= ='y');
inorder(root);
cnt=0;
cnt count(root,cnt);
bs *get_node()
bs *temp;
temp=(bs*)malloc(sizeof(bs));
scanf("%d", &temp->data);
temp->left=NULL;
temp->right = NULL;
return temp;
if(New->data <root->data)
if(root->left== NULL)
root->left=New;
else
insert(root->left,New);
if(New->data>root->data)
if(root->right== NULL)
root->right=New;
else
insert(root->right, New);
if(temp!= NULL)
i++;
count(temp->left,i);
count(temp->right,i);
return i;
if(temp!= NULL)
inorder(temp->left);
printf("%d", temp->data);
inorder(temp->right);
Sol.:
/***************************************
****************************************/
#include<stdio.h>
#include <alloc.h>
#include <conio.h>
typedef struct bst1
int data;
}bs;
bs *New,*root;
/**************************************
***************************************/
void main()
char ans='N';
int count;
bs *get_node();
clrscr();
root=NULL;
do
New=get_node();
if(root == NULL)
root=New;
else
insert(root,New);
ans=getch();
} while(ans= ='y');
inorder(root);
count=0;
count height(root);
bs *get_node()
bs *temp;
temp=(bs*)malloc(sizeof(bs));
scanf("%d", &temp->data);
temp->left=NULL;
temp->right= NULL;
return temp;
}
void insert(bs *root,bs *New)
if(New->data <root->data)
if(root->left== NULL)
root->left=New;
else
insert(root->left,New);
if(New->data>root->data)
if(root->right == NULL)
root->right=New;
else
insert(root->right,New);
int max(int,int);
if (temp== NULL)
return 0;
else
return (1+max(height(temp->left),height(temp->right)));
if(x>y)
return x;
return y;
if(temp!= NULL)
inorder(temp->left);
printf("%d", temp->data);
inorder(temp->right);
Sol.:
/**********************************
Program to create a binary tree and print the data level wise or in a breadth first
search order. The data in each level will be
**********************************/
#include<stdio.h>
#include <alloc.h>
#include <conio.h>
#define size 50
int data;
}btree;
if(New->data <root->data)
{
eals
if(root->left= = NULL)
root->left=New;
else
insert(root->left, New);
if(New->data>root->data)
if(root->right== NULL)
root->right=New;
else
insert(root->right,New);
void display()
dummy = (btree*)malloc(sizeof(btree));
if (dummy = = NULL)
printf("Insufficient Memory\n");
dummy->left = root;
dummy->right = NULL;
dummy->data = '';
enque(temp);
enque(dummy);
temp = deque();
while(front != rear)
if (temp!= dummy)
printf("%d",temp->data);
if (temp->left != NULL)
if (temp->right != NULL)
else
enque(temp);
printf("\n");
temp = deque();
}
void enque(btree *Node)
if (rear = = size-1)
printf("Queue is full\n");
rear = rear + 1;
que[rear] = Node;
btree *deque ()
btree *Node;
if (front = = rear)
printf("Queue is empty\n");
front++;
Node = que[front];
return(Node);
void main()
char ans='y';
root=NULL;
front-rear =-1;
do
{
clrscr();
New->left=NULL;
New->right = NULL;
root=New;
else
insert(root,New);
ans=getch();
while(ans= ='y');
display();
getch();
Output
10
8 12
7 9 11 13
Sol. :
/***************************************
***************************************/
#include<stdio.h>
#include <alloc.h>
#include <conio.h>
int data;
bs *New,*second,*root;
/**************************************
***************************************/
void main()
char ans='N';
bs *copy(bs *);
bs *get_node();
clrscr();
root= NULL;
do
New get_node();
if(root== NULL)
root=New;
else
insert(root, New);
} while(ans= ='y');
inorder(root);
second copy(root);
inorder(second);
bs *get_node()
bs *temp;
temp=(bs*)malloc(sizeof(bs));
scanf("%d", &temp->data);
temp->left=NULL;
temp->right=NULL;
return temp;
if(New->data <root->data)
if(root->left== NULL)
root->left=New;
else
insert(root->left,New);
if(New->data>root->data)
if(root->right == NULL)
root->right=New;
else
insert(root->right,New);
bs *copy(bs * first)
bs *New;
if (first!= NULL)
if (New == NULL)
else
return NULL;
if(temp!= NULL)
inorder(temp->left);
printf("%d",temp->data);
inorder(temp->right);
Output
Sol. :
/*******************************************
*******************************************/
#include<stdio.h>
#include <conio.h>
#define TRUE 1
#define FALSE 0
int data;
struct bst1 *left, *right;
}bs;
bs *s;
bs *get_node();
/******************************************
*******************************************/
bs *get_node()
bs *temp;
temp=new bs;
scanf("%d", &temp->data);
temp->left= NULL;
temp->right = NULL;
return temp;
/**************************************
**************************************/
void insert(bs *root,bs *New)
if(New->data <root->data)
if(root->left== NULL)
root->left=New;
else
insert(root->left, New);
if(New->data>root->data)
if(root->right == NULL)
root->right=New;
else
insert(root->right,New);
/**************************************
***************************************/
if(temp!= NULL)
inorder(temp->left);
printf("%d", temp->data);
inorder(temp->right);
/**************************************
**************************************/
int flag;
flag = FALSE;
flag = TRUE;
else
/**************************************
***************************************/
void main()
{
int choice,flag;
bs *root1,*root2;
char ans='N';
clrscr();
root1=NULL;
root2= NULL;
do
s=get_node();
if(root1== NULL)
root1=s;
else
insert(root1,s);
ans=getch();
}while(ans= ='y');
do
s=get_node();
if(root2== NULL)
root2=s;
else
insert(root2,s);
ans=getch();
} while(ans= ='y');
inorder(root1);
printf("\nSecond Tree");
inorder(root2);
flag=equal(root1,root2);
if (flag==TRUE)
else
getch();
Output
First Tree 7 8 9 10 12
Second Tree 5 8 9 10 12
Q.1 What is the difference between linear and non-linear data structures?
Ans. :
A binary tree is a finite set of nodes which is either empty or consists of root and
two disjoint binary trees called the left subtree and right subtree. Refer Fig.
Ans. :
There are two ways of representing the binary tree - sequential representation and
linked representation. The linked representation is normally preferred by
developers because in the linked representation the binary tree is represented using
linked list. Hence the tree with any number of nodes can be created. Secondly there
is no wastage or shortage of the memory in this representation.
Ans. :
Ans. :
The linked list is the efficient data structure for constructing the trees. Because
using linked list there is no wastage of memory or shortage of memory. The nodes
can be allocated or de-allocated as per the requirements.
Ans. :
The two binary trees are said to be equivalent if the sequence of their traversal is
same.
Ans. :
A complete binary tree is a tree in which every node except the root node should
have exactly two children not necessarily on the same level. Refer Fig. 5.7.1
Q.9 What is level of a tree?
AU: Dec.-19
Ans. :
The root node is always considered at level zero. The adjacent nodes to root are
supposed to be at level 1 and so on.
Ans. :
Leaf node means a node having no child node. As leaf nodes are not having further
links, we call leaf nodes external nodes and non-leaf nodes are called internal
nodes.
Ans. : The nodes with common parent are called siblings or brothers.
Ans. Forest is a collection of disjoint trees. From a given tree if we remove its root
then we get a forest. Refer Fig. 5.7.2.
Q.13 What is full binary tree?
Ans. : A full binary tree is a tree in which every node has zero or two children.
Refer Fig. 5.7.3.
Ans. :
AU: Dec.-05
Ans. : In an array root node will be at position 1. Its left child will be at position 2
and right child will be at position 3. Hence the nodes of tree are placed in array
using following formula -
AU: May-06
Ans. :
Q.18 Define binary search tree.
Ans.: Binary search tree is a binary tree in which each node is systematically
arranged i.e. the left child has less value than its parent node and right child has
greater value than its parent node. The searching of any node in such a tree
becomes efficient in this type of tree.
For example -
Q.19 List the operations defined on binary trees data type with a suitable
example.
Ans. :
For example -
We can delete any desired node from the binary tree except root node.
For example -
Traversal means a walkover a binary tree. It can be preorder, postorder and inorder
traversal.
Ans. Algorithm :
int data;
}bin;
New (bin*)malloc(sizeof(bin));
New->left=NULL;
New->right=NULL;
Thus a single node gets created. This is the first node of the tree, hence it is called
as the root node.
root=New;
4. Attach the next subsequent nodes to either as a left child or a right child to the
corresponding parent nodes depending on the user's choice.
Q.21 Why it is said that the searching a node in a binary search tree is efficient
than that of a simple binary tree?
Ans. : In the binary search tree the nodes are arranged in such a way that the left
node is having less data value than root node value. And the right nodes are having
larger value than that of root. Because of this while searching any node the value
of target node will be compared with the parent node and accordingly either left
sub branch or right sub branch will be searched. This procedure will be repeated if
required. So one has to compare only particular branches. Thus searching becomes
efficient.
Q.22 If a binary tree with n nodes is represented sequentially, then for any node
with index i (a) 1 ≤ i ≤n, then left child (i) is at 2i, if 2i ≤n. (b) If 2i>n, then I has
no left child. Name the type of binary tree which satisfies both (a) and (b).
AU: May-11
AU : May-11
Ans. : The two binary trees are said to be equivalent if the sequence of there
traversal is same for example -
Ans.
2. Game tree
3. Expression tree
AU: Dec.-12
Ans. : A binary tree is a finite set of nodes which is either empty or consists of root
or two disjoint binary trees called the left subtree and right subtree.
Each node in the binary tree contains three fields left child pointer, data field and
right child pointer.
struct BST
BST *leftchild;
int data;
BST *rightchild;
};
Ans. :
For 3 nodes there are 2 3 - 3 trees possible. That means 5 such trees can be drawn.
For example - If there are 3 nodes with the value 10, 20, 30 then
Q. 27 Show the result of inorder traversal of the binary search tree given in
Fig. 5.7.4.
ii) The maximum level of tree is called height. The maximum level is AB-E-J-M.
Thus height of tree of tree is 4.
Q. 29 The depth of complete binary tree is 8 and compute the number of nodes
in leaf.
AU: May-19
Ans : The relationship between depth of a tree and maximum number of nodes in
leaf is,
2d -1 = n
28 -1 = n
n = 255
AU: May-19
Ans. : The left null link can point to predecessor node and the right null link can
point to successor node. This way the null links can be utilized so that tranversing
of the tree becomes efficient.
Hashing
Unit IV
Chapter 6
b. Hashing
Syllabus
Hashing - Hash Functions - Separate Chaining - Open Addressing - Linear
Probing- Quadratic Probing - Double Hashing - Rehashing.
Contents
6.1 Basic Concept … May-19, …. Marks 6
Basic Concept
Hashing is an effective way to reduce the number of comparisons. Actually
hashing deals with the idea of proving the direct address of the record where the
record is likely to store. To understand the idea clearly let us take an example -
Suppose the manufacturing company has an inventory file that consists of less
than 1000 parts. Each part is having unique 7 digit number. The number is called
'key' and the particular keyed record consists of that part name. If there are less
than 1000 parts then a 1000 element array can be used to store the complete file.
Such an array will be indexed from 0 to 999. Since the key number is 7 digit it is
converted to 3 digits by taking only last three digits of a key. This is shown in the
Fig. 6.1.1.
Observe in Fig. 6.1.1 that the first key 496700 and it is stored at oth position. The
second key is 8421002. The last three digits indicate the position 2nd in the array.
Let us search the element 4957397. Naturally it will be obtained at position 397.
This method of searching is called hashing. The function that converts the key (7
digit) into array position is called hash function. Here hash function is
Where key % 1000 will be the hash function and the key obtained by
hash function is called hash key.
2) Hash Function:
For example : Consider hash function as key mod 5. The hash table of size 5.
3) Bucket: The hash function H(key) is used to map several dictionary entries in
the hash table. Each position of the hash table is called bucket.
4) Collision: Collision is situation in which hash function returns the same address
for more than one record.
For example
5) Probe: Each calculation of an address and test for success is known as a probe.
6) Synonym: The set of keys that has to the same location are called synonyms.
For example - In above given hash table computation 25 and 55 are synonyms.
7) Overflow : When hash table becomes full and new record needs to be inserted
then it is called overflow.
For example -
Ex. 6.1.1: Indicate whether you use an Array, Linked List or Hash Table to store
data in each of the following cases. Justify your answer.
2) A library needs to maintain books by their ISBN number. Only thing important
is finding them as soon as possible.
3) A data set needs to be maintained in order to find the median of the set
quickly.
Sol. : 1) The list of employees can be stored in an array. The min or max value can
be searched easily from the array.
2) As the book is searched using ISBN, hash table can be used to store the book
records.
3) The data set can be stored in an array, so that the median of array can be easily
obtained.
Hash Functions
There are various types of hash functions or hash methods which are used to
place the elements in hash table.
1. Division Method
The hash function depends upon the remainder of division.
If the record 54, 72, 89, 37 is to be placed in the hash table and if the table size is
10 then
1) Multiply the key 'k' by a constant A where A is in the range 0 < A < 1. Then
extract the fractional part of kA.
2) Multiply this fractional part by m and take the floor.
Example :
A = 0.61803398987
3. Extraction
In this method some digits are extracted from the key to form the address
location in hash table.
For example: Suppose first, third and fourth digit from left is selected for hash
key.
4. Mid Square
This method works in following steps
2) Extract middle part of the result. This will indicate the location of the key
element in the hash table.
Note that if the key element is a string then it has to be preprocessed to produce
a number.
H(3111) = 783
Review Question
1. Chaining
1. Chaining without replacement
From the example, you can see that the chain is maintained the number who
demands for location 1. First number 131 comes we will place at index 1. Next
comes 21 but collision occurs so by linear probing we will place 21 at index 2, and
chain is maintained by writing 2 in chain table at index 1 similarly next comes 61
by linear probing we can place 61 at index 5 and chain will be maintained at index
2. Thus any element which gives hash key as 1 will be stored by linear probing at
empty location but a chain is maintained so that traversing the hash table will be
efficient.
The drawback of this method is in finding the next empty location. We are least
bothered about the fact that when the element which actually belonging to that
empty location cannot obtain its location. This means logic of hash function gets
disturbed.
Hence we will replace 21 by 2 and accordingly chain table will be updated. See the
table:
The value -1 in the hash table and chain table indicate the empty location. The
advantage of this method is that the meaning of hash function is preserved. But
each time some logic is needed to test the element, whether it is at its proper
position.
2. Open Addressing
Open addressing is a collision handling technique in which the entire hash table is
searched in systematic way for empty cell to insert new item if collision occurs.
1. Linear probing
2. Quadratic probing
3. Double hashing
1. Linear probing
When collision occurs i.e. when two records demand for the same location in the
hash table, then the collision can be solved by placing second record linearly
down wherever the empty location is found.
For example
In the hash table given in Fig. 6.4.3 the hash function used is number % 10. If the
first number which is to be placed is 131 then 131 % 10 = 1 i.e. remainder is 1 so
hash key = 1. That means we are supposed to place the record at index 1. Next
number is 21 which gives hash key 1 as 21 % 10 = 1. But already 131 is placed at
index 1. That means collision is occurred. We will now apply linear probing. In this
method, we will search the place for number 21 from location of 131. In this case
we can place 21 at index 2. Then 31 at index 3. Similarly 61 can be stored at 6
because number 4 and 5 are stored before 61. Because of this technique, the
searching becomes efficient, as we have to search only limited list to obtain the
desired number.
Ex. 6.4.1: Implement the hash table and perform collision handling by linear
probing
Sol. :
#include <stdio.h>
#include<conio.h>
printf("\n %d %d",i,a[i]);
int key = num % tsize;//Computing the hash key using hash function
int main()
int num;
int hash_table[SIZE];
char ans;
do
Linear_prob(hash_table,SIZE,num);
ans = getch();
}while(ans=='y');
return 0;
}
Output
0 -1
1 131
2 -1
3 -1
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 -1
1 131
2 21
3 -1
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
Do U Wish To Continue?(y/n)
1- 0
1 131
2 21
3 3
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
0 -1
1 131
2 21
3 3
44
5 -1
6 -1
7 -1
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 -1
1 131
2 21
33
44
LO
6 -1
7 -1
8 -1
9 -1
0 -1
1
131
2 21
33
44
55
6 -1
7 -1
8 8
9 -1
Do U Wish To Continue?(y/n)
0 -1
1 131
2 21
3 3
4 4
55
6 -1
7 -1
8 8
9 9
Do U Wish To Continue?(y/n)
0 18
1 131
2 21
3 3
4 4
5 5
6 -1
7 -1
8 8
9 9
Do U Wish To Continue?(y/n)
0 18
1 131
2 21
3 3
4 4
5 5
6 33
7 -1
8 8
9 9
Do U Wish To Continue?(y/n)
One major problem with linear probing is primary clustering. Primary clustering is
a process in which a block of data is formed in the hash table when collision is
resolved.
For example:
2. Quadratic probing
Quadratic probing operates by taking the original hash value and adding
successive values of an arbitrary quadratic polynomial to the starting value. This
method uses following formula -
Hi(key) = (Hash(key)+i2)%m
For example: If we have to insert following elements in the hash table with table
size 10: 37, 90, 55, 22, 11, 17, 49, 87.
Now if we want to place 17 a collision will occur as 17%10-7 and bucket 7 has
already an element 37. Hence we will apply quadratic probing to insert this record
in the hash table.
Hi(key) = (Hash(key)+i2)%m
Consider i = 0 then
(17+02) %10 = 7
49%10 = 9
(87+0)%10 = 7
Sol. :
#include <stdio.h>
#include<conio.h>
printf("\n %d %d",i,a[i]);
int key = num % t using size;//computing the hash key mod function
if (table[key] == -1)
table[key] = num;
else.
{
table[index] break; = num;//then insert element at that index
break;
display(table, tsize);
int main()
int num;
int hash_table[SIZE];
char ans;
do
ans = getch();
while(ans= ='y');
return 0;
Output
0 -1
1 -1
2 -1
3 -1
4 -1
5 -1
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 -1
2 -1
3 -1
4 -1
5 -1
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 -1
2 -1
3 -1
4 -1
5 55
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
1 -1
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 17
9 -1
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 17
9 49
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 87
7 37
8 17
9 49
Do U Wish To Continue?(y/n)
3. Double hashing
Double hashing is technique in which a second hash function is applied to the key
when a collision occurs. By applying the second hash function we will get the
number of positions from the point of collision to insert.
There are two important rules to be followed for the second function :
H1(17) = 17%10 = 7
H2(key) = M - (key%M)
Here M is a prime number smaller than the size of the table. Prime number
smaller than table size 10 is 7.
Hence M = 7
H2(17) = 7 (17%7) = 7 – 3 = 4
That means we have to insert the element 17 at 4 places from 37. In short we
have to take 4 jumps. Therefore the 17 will be placed at index 1.
H2(55) = 7-(55%7) = 7 - 6 = 1
That means we have to take one jump from index 5 to place 55. Finally the hash
table will be -
Comparison of quadratic probing and double hashing
The double hashing requires another hash function whose probing efficiency is
same as some another hash function required when handling random collision.
The double hashing is more complex to implement than quadratic probing. The
quadratic probing is fast technique than double hashing.
Ex. 6.4.3 Give the input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and hash
function X(mod 10), show the results for the following:
iii) Open addressing hash table with second hash function h2 (X) = 7 - (X mod 7).
1323 mod 10 = 3
Hence by linear probing we will place 6173 at next empty location. That is, at
location 4.
4199 mod 10 = 9
9679 mod 10 = 9 collision occurs so place at next location at 0. The hash table is of
size 10. Hence we find the next empty location by rolling the table in forward
direction.
1989 mod 10 = 9 collision occurs, so we find the next empty location at index 2.
In quadratic probing we consider the original hash key and then add an arbitrary
polynomial. This sum is then considered for hash function. The hash function will
be
Step 1:
Step 2:
Step 3:
Step 4:
Ex. 6.4.4 What do you understand by collision in hashing? Represent the
following keys in memory using linear probing with or without replacement.
Use modulo (10) as your hashing function: (24, 13, 16, 15, 19, 20, 22, 14, 17, 26,
84, 96)
We will consider the hash function as modulo (10) for the hash table size 12, that
is from 0 to 11. In linear probing with replacement, we first find the probable
position of the key element using hash function. If the location which we obtain
from hash function is empty then place the corresponding key element at that
location. If the location is not empty and the key element which is present at that
location belongs to that location only then, move down in search of empty slot.
Place the record at the empty slot.
If the location contains a record which does not belong to that location then
replace that record by the current key element. Place the replaced record at some
empty slot, which can be obtained by moving linearly down.
Sol.: i) Chaining
Similarly remaining elements can be placed. When collision occurs, double
hashing is applied.
3. Rehashing
Rehashing is a technique in which the table is resized, i.e., the size of table is
doubled by creating a new table. It is preferable if the total size of table is a prime
number. There are situations in which the rehashing is required –
In such situations, we have to transfer entries from old table to the new table by
recomputing their positions using suitable hash functions.
Consider we have to insert the elements 37, 90, 55, 22, 17, 49 and 87. The table
size is 10 and I will use hash function,
Now this table is almost full and if we try to insert more elements collisions will
occur and eventually further insertions will fail. Hence we will rehash by doubling
the table size. The old table size is 10 then we should double this size for new
table, that becomes 20. But 20 is not a prime number, we will prefer to make the
table size as 23. And new hash function will be
Now the hash table is sufficiently large to accommodate new insertions.
Advantages
1. This technique provides the programmer a flexibility to enlarge the table size if
required.
2. Only the space gets doubled with simple hash function which avoids occurrence
of collisions.
Review Questions
3. Illustrate with example the open addressing and chaining methods of collision
resolution techniques in hashing. AU: May-17, Marks 16
2. Number of collisions should be less while placing the record in the hash table.
Ideally no collision should occur. Such a function is called perfect hash function.
3. Hash function should produce such keys which will get distributed uniformly
over an array.
4. The hash function should depend on every bit of the key. Thus the hash function
that simply extracts the portion of a key is not suitable.
Review Question
Collision Handling
AU: Dec.-15, 18, May - 16, 17, 19, Marks 16
1. Chaining
1. Chaining without replacement
From the example, you can see that the chain is maintained the number who
demands for location 1. First number 131 comes we will place at index 1. Next
comes 21 but collision occurs so by linear probing we will place 21 at index 2, and
chain is maintained by writing 2 in chain table at index 1 similarly next comes 61
by linear probing we can place 61 at index 5 and chain will be maintained at index
2. Thus any element which gives hash key as 1 will be stored by linear probing at
empty location but a chain is maintained so that traversing the hash table will be
efficient.
The drawback of this method is in finding the next empty location. We are least
bothered about the fact that when the element which actually belonging to that
empty location cannot obtain its location. This means logic of hash function gets
disturbed.
2. Chaining with replacement
Now next element is 2. As hash function will indicate hash key as 2 but already at
index 2. We have stored element 21. But we also know that 21 is not of that
position at which currently it is placed.
Hence we will replace 21 by 2 and accordingly chain table will be updated. See the
table:
The value -1 in the hash table and chain table indicate the empty location. The
advantage of this method is that the meaning of hash function is preserved. But
each time some logic is needed to test the element, whether it is at its proper
position.
2. Open Addressing
Open addressing is a collision handling technique in which the entire hash table is
searched in systematic way for empty cell to insert new item if collision occurs.
1. Linear probing
2. Quadratic probing
3. Double hashing
1. Linear probing
When collision occurs i.e. when two records demand for the same location in the
hash table, then the collision can be solved by placing second record linearly
down wherever the empty location is found.
For example
In the hash table given in Fig. 6.4.3 the hash function used is number % 10. If the
first number which is to be placed is 131 then 131 % 10 = 1 i.e. remainder is 1 so
hash key = 1. That means we are supposed to place the record at index 1. Next
number is 21 which gives hash key 1 as 21 % 10 = 1. But already 131 is placed at
index 1. That means collision is occurred. We will now apply linear probing. In this
method, we will search the place for number 21 from location of 131. In this case
we can place 21 at index 2. Then 31 at index 3. Similarly 61 can be stored at 6
because number 4 and 5 are stored before 61. Because of this technique, the
searching becomes efficient, as we have to search only limited list to obtain the
desired number.
Ex. 6.4.1: Implement the hash table and perform collision handling by linear
probing
Sol. :
#include <stdio.h>
#include<conio.h>
printf("\n %d %d",i,a[i]);
int key = num % tsize;//Computing the hash key using hash function
int main()
int num;
int hash_table[SIZE];
char ans;
do
Linear_prob(hash_table,SIZE,num);
ans = getch();
}while(ans=='y');
return 0;
}
Output
0 -1
1 131
2 -1
3 -1
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 -1
1 131
2 21
3 -1
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
Do U Wish To Continue?(y/n)
1- 0
1 131
2 21
3 3
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
0 -1
1 131
2 21
3 3
44
5 -1
6 -1
7 -1
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 -1
1 131
2 21
33
44
LO
6 -1
7 -1
8 -1
9 -1
0 -1
1
131
2 21
33
44
55
6 -1
7 -1
8 8
9 -1
Do U Wish To Continue?(y/n)
0 -1
1 131
2 21
3 3
4 4
55
6 -1
7 -1
8 8
9 9
Do U Wish To Continue?(y/n)
0 18
1 131
2 21
3 3
4 4
5 5
6 -1
7 -1
8 8
9 9
Do U Wish To Continue?(y/n)
0 18
1 131
2 21
3 3
4 4
5 5
6 33
7 -1
8 8
9 9
Do U Wish To Continue?(y/n)
One major problem with linear probing is primary clustering. Primary clustering is
a process in which a block of data is formed in the hash table when collision is
resolved.
For example:
2. Quadratic probing
Quadratic probing operates by taking the original hash value and adding
successive values of an arbitrary quadratic polynomial to the starting value. This
method uses following formula -
Hi(key) = (Hash(key)+i2)%m
For example: If we have to insert following elements in the hash table with table
size 10: 37, 90, 55, 22, 11, 17, 49, 87.
Now if we want to place 17 a collision will occur as 17%10-7 and bucket 7 has
already an element 37. Hence we will apply quadratic probing to insert this record
in the hash table.
Hi(key) = (Hash(key)+i2)%m
Consider i = 0 then
(17+02) %10 = 7
49%10 = 9
(87+0)%10 = 7
Sol. :
#include <stdio.h>
#include<conio.h>
printf("\n %d %d",i,a[i]);
int key = num % t using size;//computing the hash key mod function
if (table[key] == -1)
table[key] = num;
else.
{
table[index] break; = num;//then insert element at that index
break;
display(table, tsize);
int main()
int num;
int hash_table[SIZE];
char ans;
do
ans = getch();
while(ans= ='y');
return 0;
Output
0 -1
1 -1
2 -1
3 -1
4 -1
5 -1
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 -1
2 -1
3 -1
4 -1
5 -1
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 -1
2 -1
3 -1
4 -1
5 55
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
1 -1
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 -1
9 -1
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 17
9 -1
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 -1
7 37
8 17
9 49
Do U Wish To Continue?(y/n)
0 90
1 11
2 22
3 -1
4 -1
5 55
6 87
7 37
8 17
9 49
Do U Wish To Continue?(y/n)
3. Double hashing
Double hashing is technique in which a second hash function is applied to the key
when a collision occurs. By applying the second hash function we will get the
number of positions from the point of collision to insert.
There are two important rules to be followed for the second function :
H1(17) = 17%10 = 7
H2(key) = M - (key%M)
Here M is a prime number smaller than the size of the table. Prime number
smaller than table size 10 is 7.
Hence M = 7
H2(17) = 7 (17%7) = 7 – 3 = 4
That means we have to insert the element 17 at 4 places from 37. In short we
have to take 4 jumps. Therefore the 17 will be placed at index 1.
H2(55) = 7-(55%7) = 7 - 6 = 1
That means we have to take one jump from index 5 to place 55. Finally the hash
table will be -
Comparison of quadratic probing and double hashing
The double hashing requires another hash function whose probing efficiency is
same as some another hash function required when handling random collision.
The double hashing is more complex to implement than quadratic probing. The
quadratic probing is fast technique than double hashing.
Ex. 6.4.3 Give the input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and hash
function X(mod 10), show the results for the following:
iii) Open addressing hash table with second hash function h2 (X) = 7 - (X mod 7).
1323 mod 10 = 3
Hence by linear probing we will place 6173 at next empty location. That is, at
location 4.
4199 mod 10 = 9
9679 mod 10 = 9 collision occurs so place at next location at 0. The hash table is of
size 10. Hence we find the next empty location by rolling the table in forward
direction.
1989 mod 10 = 9 collision occurs, so we find the next empty location at index 2.
In quadratic probing we consider the original hash key and then add an arbitrary
polynomial. This sum is then considered for hash function. The hash function will
be
Step 1:
Step 2:
Step 3:
Step 4:
Ex. 6.4.4 What do you understand by collision in hashing? Represent the
following keys in memory using linear probing with or without replacement.
Use modulo (10) as your hashing function: (24, 13, 16, 15, 19, 20, 22, 14, 17, 26,
84, 96)
We will consider the hash function as modulo (10) for the hash table size 12, that
is from 0 to 11. In linear probing with replacement, we first find the probable
position of the key element using hash function. If the location which we obtain
from hash function is empty then place the corresponding key element at that
location. If the location is not empty and the key element which is present at that
location belongs to that location only then, move down in search of empty slot.
Place the record at the empty slot.
If the location contains a record which does not belong to that location then
replace that record by the current key element. Place the replaced record at some
empty slot, which can be obtained by moving linearly down.
Sol.: i) Chaining
Similarly remaining elements can be placed. When collision occurs, double
hashing is applied.
3. Rehashing
Rehashing is a technique in which the table is resized, i.e., the size of table is
doubled by creating a new table. It is preferable if the total size of table is a prime
number. There are situations in which the rehashing is required –
In such situations, we have to transfer entries from old table to the new table by
recomputing their positions using suitable hash functions.
Consider we have to insert the elements 37, 90, 55, 22, 17, 49 and 87. The table
size is 10 and I will use hash function,
Now this table is almost full and if we try to insert more elements collisions will
occur and eventually further insertions will fail. Hence we will rehash by doubling
the table size. The old table size is 10 then we should double this size for new
table, that becomes 20. But 20 is not a prime number, we will prefer to make the
table size as 23. And new hash function will be
Now the hash table is sufficiently large to accommodate new insertions.
Advantages
1. This technique provides the programmer a flexibility to enlarge the table size if
required.
2. Only the space gets doubled with simple hash function which avoids occurrence
of collisions.
Review Questions
3. Illustrate with example the open addressing and chaining methods of collision
resolution techniques in hashing. AU: May-17, Marks 16
Applications of Hashing
1. In compilers to keep track of declared variables.
2. For online spelling checking the hashing functions are used.rw ni song piller 3.
Hashing helps in Game playing programs to store the moves made.
4. For browser program while caching the web pages, hashing is used.
Two Marks Questions with Answers
AU: May-16
Ans. :
Ans. :
Ans. : An uniform hash function is one that equally distributes data items over the
whole hash table data structure.
AU: Dec.-15
Ans. :
Rehashing is a technique in which the table is resized. That means the size of the
table is doubled by creating a new table. The total size of the table is usually a
prime number. Following are the situations in which the rehashing is required -
Ans. : The situation in which the hash function returns the same hash key for more
than one record is called collision.
Ans. : The situation in which there is no room for a new pair in the hash table is
called overflow.
1. This technique provides the programmer a flexibility to enlarge the table size if
required.
2. Only the space gets doubled with simple hash function which avoids occurrence
of collisions.
Q.10 What is the advantage of chained hash table over open addressing
scheme ?
Ans. : The deletion of particular record from the hash function becomes easier.
Q.12 Specify the hashing technique in which the table size can be changed.
Ans. : The rehashing is a hashing technique in which the table size can be changed.
Q.13 What will be the position of the number 3111 in a hash table, when the mid
square method is applied ? (The table size is 1000)
Q.14 Which hash function maintains the record in order of hash field values ?
Ans. : The folding method maintains the record in order of hash field values.
Q.15 Enlist the conditions in which the rehashing is required.
3. When there is a need to transfer the contents from old hash table to new hash
table.
Ans. : When collision happens we create a new memory location outside the
existing table and use a chain to link to the new memory location.
Ans. : chaining.
Q.18 What are the advantages and disadvantages of separate chaining and
linear probing?
Advantages:
i) It is simple to implement.
ii) Hash table never fills and we can add elements in the linked list fashion.
Disadvantages:
iii) There may be wastage of space as some parts of hash table are never used.
2) Linear probing:
Advantage:
Disadvantage:
1) It forms primary clustering. Hence only some part of hash table remain occupied
bim and other part remains vaccant.
Sorting and Searching Techniques
Unit V
Chapter 7
Sorting and Searching Techniques
Syllabus
Insertion Sort - Quick Sort - Heap Sort - Merge Sort - Linear Search - Binary
Search.
Contents
7.1 Sorting
Sorting
• Definition: Sorting is a technique for arranging data in particular order.
• Order of Sorting : Order means the arrangement of data. The sorting order can
be ascending or descending. The ascending order means arranging the data in
increasing order whereas descending order means arranging the data in
decreasing order.
1. Insertion sort
2. Selection sort
3. Shell sort
4. Bubble sort
5. Quick sort
6. Merge sort
• Passes: While sorting the elements in some specific order, there is lot of
arrangement of elements. The phases in which the elements are moving to acquire
their proper position is called passes.
Applications of Sorting
1. The sorting is useful in database applications for arranging the data in desired
order.
3. For searching the element from the list of elements, the sorting is required.
Insertion Sort
AU May-19, Marks 7
In this method the elements are inserted at their appropriate place. Hence is the
name insertion sort. Let us understand this method with the help of some example
3. More efficient than most other simple O (n2) algorithms such as selection sort or
bubble sort.
4. This is a stable (does not change the relative order of equal elements).
Sol. :
/************************************
************************************/
#include<stdio.h>
#include<conio.h>
void main()
{
int A[10],n,i;
clrscr();
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d", &A[i]);
Insert_sort(A,n);
getch();
int i,j,temp;
for(i=1;i<=n-1;i++)
temp=A[i];
j=i-1;
while((j>=0)&&(A[j]>temp))
Alj+1]=A[j];
j=j-1; smel
}.
A[j+1]=temp;
for(i=0;i<n;i++)
printf("\n%d",A[i]);
Output
'Insertion Sort
30
20
10
40
50
10
20
30
40
50
Logic Explanation
Then the control moves to while loop. As j >= 0 and A[j] > temp is True, the while
loop will be executed.
Ex. 7.2.2: Write a routine for insertion sort. Sort the following sequence using
insertion sort. 3, 10, 4, 2, 8, 6, 5, 1.
AU May-19, Marks 7
• The left subarray is having the elements less than pivot and right subarray is
having the elements greater than pivot.
• Thus array is partitioned repeatedly and the elements in subarray are sorted.
Example
Step 1:
Algorithm
The quick sort algorithm is performed using following two important functions –
Quick and partition. Let us see them -
Algorithm Quick(A[0...n-1],low,high)
//order
if(low<high)then
Quick(Allow...m-1])
Quick (A[mid+1...high])
pivot ← A[low]
i ← low
j ← high+1
while(i<=j) do
i ← i+1
j ← j-1;
if(i<=j) then
The partition function is called to arrange the elements such that all the elements
that are less than pivot are at the left side of pivot and all the elements that are
greater than pivot are all at the right of pivot. In other words pivot is occupying its
proper position and the partitioned list is obtained in an ordered manner.
C Program
/**************************************************
Program to sort the elements in ascending order using Quick Sort.
**************************************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 10
int n;
int main()
int i;
int A[SIZE];
clrscr();
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &A[i]);
}
Quick (A,0,n-1);
for(i=0;i<n;i++)
printf("\t%d ",A[i]);
getch();
return 0;
/*
*/
int m,i;
if(low<high)
Quick(A,low,m-1);//splitting of list
/*
This function is to partition a list and decide the pivot
element
*/
while(i<=j)
i++;
while(Alj]>pivot)
j--;
if(i<j)
swap(A,&i,&j);
swap(A,&low,&j);
return j;
int temp;
temp=A[*i];
A[*i]=A[*j];
inom A[*j]=temp;
Output
10 20 30 40 50 70 80 90
Ex. 7.3.1 Consider following numbers, sort them using quick sort. Show all
passes to sort the values in ascending order
After pass 1:
Ex. 7.3.2 Sort the following data to ascending order using quick sort. Show all
passes with Pivot: 17, 8, -9, 2, 0, -5, 7, 20, 11, 15
17 8 -9 2 0 -5 7 20 11 15
Pivot i j
When we get these above conditions to be false, Swap A [i] and and A [j].
17 8 -9 2 0 -5 7 15 11 20
In this section we will learn "What is heap?" and "How to construct heap?" and
heap sort.
A Max heap is a tree in which value of each node is greater than or equal to the
value of its children nodes.
For example:
A Min heap is a tree in which value of each node is less than or equal to value of
its children nodes.
For example:
Parent being greater or lesser in heap is called parental property. Thus heap has
two important properties.
Heap Sort
Operations :
1. Create_heap(): This is the first task to be performed for sorting the elements
using heap sort. The parent node must be either maximum of its children or
minimum than its children. That means a maxheap or minheap should be
constructed..
2. Swap(): The root node must be swapped with the node at the last position in
tree.
3. Delete_node(): The node at the last position in the heap tree must be deleted.
4. Insert_Q(): The deleted element from the heap must be inserted in the priority
queue.
5. Delete_Q(): The element can be deleted from the priority queue by the front
end, so that a sorted list can be obtained.
Ex. 7.4.1: State algorithm to sort elements of a given array in ascending order
using heap sort. Sort the following numbers using heap sort: 48, 0, -1, 82, 108,
72, 54.
Sol. Algorithm :
Step 3: Delete the last node and store its key at the end of the array.
Step 6: Delete the last node and store it at the end of the array.
Step 7: Print all the elements of the array. This will display the elements in sorted
order.
Sol. :
Merge Sort
AU: Dec.-15,18, May-19, Marks 13
Merge sort is a sorting algorithm in which array is divided repeatedly. The sub
arrays are sorted independently and then these subarrays are combined together to
form a final sorted list.
Divide : Partition array into two sub lists s1 and s2 with n/2 elements each. ano?
Ex. 7.5.1: Consider the following elements for sorting using merge sort
{
mid-low+high)/2 //split the list at mid
if(A[i]<=A[j])then
temp[k] A[i]
i ← i+1
k ← k+1
temp[k] ← A[j]
j ← j+1
k ← k+1
while(i<=mid)do
temp[k] A[i]
i ← i+1
k ← k+1
while(j<=high)do
temp[k] A[j]
j ← j+1
k ← k+1
Logic Explanation
To understand above algorithm consider a list of elements as
Let us see the combine operation more closely with the help of some example.
Consider that at some instance we have got two sublits 20, 30, 40, 70 and 10, 50,
60, then
Finally we will copy all the elements of array temp to array A. Thus array A
contains sorted list.
C Function
int mid;
if(low high)
int i,j,k;
int temp[10];
k=low;
i=low;
j=mid+1;
if(A[i]<=A[j])
temp[k]=A[i];
i++;
k++;
else
temp[k] =A[j];
j++;
k++;
while(i<=mid)
temp[k]=A[i];
i++;
k++;
while(j<=high)
temp[k] =A[j];
j++;
k++;
for(k=low;k<=high;k++)
A[k]=temp[k];
C Program
/**********************************
**********************************/
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
int n;
void main()
{
int i,low,high;
int A[10];
clrscr();
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d", &A[i]);
low=0;
high=n-1;
MergeSort(A,low,high);
Display(A);
getch();
/*
*/
int mid;
if(low high)
MergeSort(A,low,mid);//first sublist
*/
int i,j,k;
int temp[10];
k=low;
i=low;
j=mid+1;
{
if(A[i]<=A[j]) ← We compare elements from left sublist and right sublist. If
element in the left sublist is lesser than the element in the right sublist then copy
that smaller element of left sublist to temp array
temp[k]=A[i];
i++;
k++; ← We compare elements from left sublist and right sublist. If element in the
right sublist is lesser than the element in the left sublist then copy that smaller
element of right sublist to temp array
else
temp[k]=A[j];
j++;
k++;
while(i<=mid) ← Reached at the end of right sublist and elements of left sublist
are remaining, then copy the remaining elements of left sublist to temp
temp[k]=A[i];
i++;
k++;
}
while(j<=high) ← Reached at the end of left sublist and elements of right sublist
are remaining, then copy the remaining elements of right sublist to temp
temp[k]=A[j];
j++;
k++;
for(k=low;k<=high;k++)
A[k]=temp[k];
int i;
for(i=0;i<n;i++)
printf("%d\t",A[i]);
Output
Merge Sort
70
20
30
40
10
50
60
20 30 40 50 60 70
Ex. 7.5.2 Sort the following numbers using merge sort algorithm 11, 8, 55, 22,
33, 27, 62, 35, 71. Obtain the worst case and average case time complexity.
Sol. :
Review Question
AU May-19, Marks 6
Searching
AU: May-16,17, Dec.-18,19, Marks 13
• insure art sota of banist . When we want to find out particular record efficiently
from the given list of elements then there are various methods of searching that
element. These methods are called searching methods. Various algorithms based
on these searching methods are known as searching algorithms.
• The basic characteristic of any searching algorithm is -
i. It should be efficient
• The element to be searched from the given list is called the key element. Let us
discuss various searching algorithms.
1. Linear Search
• Linear search or sequential search is technique in which the given list of
elements is scanned from the beginning. The key element is compared with every
element of the list. If the match is found the searching is stopped otherwise it will
be continued to the end of the list.
• The time complexity of this algorithm is O(n). The time complexity will increase
linearly with the value of n.
• Example
From the above Fig. 7.6.1 the array is maintained to store the students record.
The record is not sorted at all. If we want to search the student's record whose
roll number is 12 then with the key-roll number we will see the every record
whether it is of roll number We can obtain such a record at Array [4] location.
'C' Program:
/******************************************
********************************************/
#include<stdio.h>
#include<conio.h>
#define MAX 10
int a[MAX],n,i; .
/*
The create Function
Input :none
Output:none
Calls:none
*/
void create()
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
/*
Input:none
Output:none
Called By:main
Calls:none
*/
void display()
for(i=0;i<n;i++)
printf("\n%d",a[i]);
/*
Output:the status
Called By:main
Calls:none
*/
search(int k)
for(i=0;i<n;i++)
if(a[i]==k)
return 1;
return 0;
}
void main()
int status,key;
clrscr();
create();
display();
scanf("%d",&key);
status=search(key);
if (status = =1)
else
getch();
/************End Of Program**********************/
100
1000
10000
The Elements Are
10
100
1000
10000
100
1000
10000
10
100
1000
10000
1. It is simple to implement.
1. It is less efficient.
2. Binary Search
Definition: Binary search is a searching technique in which the elements are
arranged in a sorted order and each time mid element is compared with the key
element recursively.
Example: The necessity of this method is that all the elements should be sorted.
So let us take an array of sorted elements.
Step 2: Find the middle element of the array. Compare it with the key
if middle? Key
i.e. if 42 ? 99
Now handle only sublist 2. Again divide it, find mid of sublist 2
if middle? key
i.e. if 99? 99
Thus by binary search method we can find the element 99 present in the given list
at array [6]th location.
/*************************************
****************************************/
beb #include<stdio.h>
#define SIZE 10
int n;
void main()
int A[SIZE],KEY,i,flag;
clrscr();
YSTIA
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &A[i]);
scanf("%d", &KEY);
flag=BinSearch(A,KEY);
if(flag= =-1)
else
getch();
}
int low,high,m;
low=0;
high-n-1;
while(low<=high)
if(KEY= =A[m])
return m;
else
Output (Run 1)
10
20
30
40
50
60
(Run 2)
10
20
30
40
50
1. if(low>high)
2. return
3. mid =(low+high)/2;
4. if(x==a[mid])
5. return (mid);
6. if(x<a[mid])
8. else
/*******************************
Program for searching the number by Binary Search. The list of numbers should
be in ascending order. The program also shows the location at which the number
is present(if at all)
**********************************/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 10
/*
Called By:main
Calls:itself
*/
int mid;
if(low>high)
return(-1);
mid = (low+high)/2;
if(x ==a[mid])
return(mid);
else if(x<a[mid])
binsearch(a,x,low,mid-1);
else
binsearch(a,x,mid+1,high);
/*
Input:none
Output:none
Called By:O.S.
Calls:binsearch
*/
void main(void)
int n,i,low,high,a[size],key,ans;
clrscr();
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
low = 0;
high = n-1;
scanf("%d", &key);
ans binsearch(a,key,low,high);
if(ans!= -1)
else
getch();
}
/************** End Of Program******************/
Output
10
20
30
40
50
Searching method
Linear search
Binary search
Time complexity
O(n)
O(nlogn)
3. Linear Search Vs. Binary Search
Review Questions
4. Write a C program to search a number with the given set of numbers using
binary search.
5. Distinguish between linear search and binary search. State and explain the
algorithms for both the search with example.
Ans.: Sorting is useful for arranging the data in desired order. After sorting the
required element can be located easily.
Searching technique is essential for locating the position of the required element
from the heap of data.
Ans. :
1. The sorting is useful in database applications for arranging the data in desired
order.
3. For searching the element from the list of elements, the sorting is required.
Ans. : Sort key is a field in the record based on which the sorting is conducted.
Ans. : Bubble sort is a slowest sorting technique and quick sort is the fastest
sorting technique.
AU: Dec.-14, 19
Ans. : Internal sorting: This is a type of sorting technique in which data resides on
main memory of computer.
External sorting: This is a sorting technique in which there is huge amount of data
and it resides on secondary storage devices while sorting.
Q.8 Explain the meaning of the term passes in context with sorting.
Ans. : While sorting the elements in some specific order, there is lot of
arrangement of elements. The phases in which the elements are moving to acquire
their proper position is called passes.
Ans.
Ascending order is the sorting order in which the elements are arranged from low
value to high value. In other words it is called increasing order. For example: 10,
20, 30, 40.
Descending order is the sorting order in which the elements are arranged from high
value to low value. In other words it is called decreasing order. For example: 40,
30, 20, 10.
Ans. :
Sorting and Searching Techniques The division of the list into two sublists(which
is called partition) and then sorting each sublist independently. This is the basic
principle used in quick sort. Based on the value of pivot element, the list is
subdivided.
1. Insertion sort
2. Selection sort
3. Shell sort
4. Bubble sort
Ans. : Ans. Heap is a complete binary tree or almost complete binary tree in which
every parent node be either greater or lesser than the parent node.
Q.13 What are the two stages in which heap sort is conducted ?
Ans. : Following are the two stages in which the heap sort is conducted - W Heap
construction: The heap structure is build for given list of elements
Deletion of maximum key: In this phase the root key is deleted for n 1 times.
Q.14 The way a card game player arranges his cards as he picks them one by
one, is an example of ----------
Q.15 A sort which iteratively passes through a list to exchange the first element
with any element less than it and then repeats with a new first element is
called……..
Q.16 Explain why binary search can not be performed using linked list ?
Ans. : In binary search algorithm, the mid element needs to be searched. If binary
search is implemented using arrays then by simply saying a[mid] we can access the
middle element of an array in constant time. But for finding the mid element of a
linked list we have to execute separate algorithm and it can not be done in constant
time. Thus implementing binary search using linked list is very inefficient way.
Hence it is not preferred to implement a binary search using linked list.
Ans. Searching means locating the position of the desired record or key element
from the given database.
Q.18 What are the advantages of binary search over the linear search?
Ans. : Binary search is an efficient searching method than the linear search. Using
this method, the list is subdivided each time and only sublist is scanned for locating
the key value.
Q.19 List the sorting algorithms which uses logarithmic time complexity
Ans. : The sorting algorithms which use the logarithmic time complexity are -
Quick sort and merge sort.
Ans. :