INTRODUCTION TO C
C has emerged as the most widely used
programming language for software development. Its features allow the
development of well-structured programs. Most computers directly support its
data types and control structures, resulting in the construction of efficient
programs. It is independent of any particular machine architecture or operating
system, which makes it easy to write portable programs. It is this contribution
of rich control structure and data types, portability and conciseness that has
contributed to the popularity of C.
History of C
C programming language is basically
developed for UNIX Operating System. UNIX was developed in 1969 at bell
telephone laboratories. It was entirely written on PDP 7 assembly language.
After UNIX has been implemented Ken Thompson implemented a compiler for a new
language called B used for transporting UNIX onto other machines. B was heavily
influenced by BCPL (Basic Cambridge Programming Language) written for writing
system software. B was latter modified by Dennis Ritchie who was also working
at bell Labs. He named the successor C. Unix was later rewritten in C by Dennis
Ritchie, Thompson and others by 1973.
C Program Structure
A basic fact about computer
programming is that all programs can be written using a combination of only
three control structures: Sequential, Selective and repetitive. The sequential
structure consists of a sequence of program statements that are executed one
after another in order, the selective structure consists of a test for a
condition followed by alternative paths that the program can follow, and the
repetitive structure consists of program statements that are repeatedly
executed while some condition holds.
The sequential structure can be pictorially represented as follows
Entry
Statement 1
Statement 2
Statement 3
Exit
All C programs are made up of one or more functions, each
performing a particular task. Every program has a special function named main.
It is special because the execution of any program starts at the beginning of
its main function.
A typical C program has following sections
1.
Preprocessor
Directives
2.
Global
Variable Declarations
3.
Functions
In a C program, preprocessor directive, if present, should come
first followed by global variable definition if any.
Variable Declaration in C
1.
The
variable can be 31 characters long.
2.
The
variable can be any of a-z, A-Z, 0-9 and the underscore.
3.
Should
not be a keyword.
4.
First
character must be an alphabet
5.
The
variable is case sensitive
Data Types
Every programming language has its own data type. The basic data
types in C are
Int - an integer
Float – a single precision floating point number
Char - a character in C
character set
Double – a double precision floating point number
Variables
Variables are data objects that are
manipulated in a program. Information can be stored in a variable and recalled
later. Variables must be declared before they can be used in a program.
Constants
A constant is an entity whose value does
not change during program execution. Constants are of five different types
1.
Integer
Constants
2.
Floating
point Constants
3.
Character
Constants
4.
String
Constants
C Operators
The operators in C include
1.
Arithmetic
2.
Assignment
3.
Relational
4.
Increment
and Decrement
5.
Bit
6.
Logical
or Boolean
7.
Conditional
expression
INPUT / OUTPUT
The important aspects of C programming language are its ability to
handle input and output (I/O). A program using input / output functions must
include the standard header file (stdio.h) in it using the directive.
Printf functions (CONIO.H, STDIO.H)
printf – sends formatted
output to stdout
fprintf – sends formatted output to a stream
cprintf – sends formatted output to the text window on the screen
Scanf Function
Scanf - reads data from
stdin
Fscanf – reads data from stream
The GETCHAR and PUTCHAR Function
Getchar, putchar (STDIO.h)
-
getchar
is a macro that gets a character from stdin
-
putchar
is a macro outputs a character on stdout
The GETCH and GETCHE Function
-
getch
gets a character from console but does not echo to the screen
-
getche
gets a character from console and echoes to the screen
gets, puts
gets() - gets a string from stdin
puts() – outputs a string to stdout
CONDITIONAL STATEMENTS
If (condition) Statement
When an if statement is encountered in a program, condition is
evaluated, if its value is true, then the following statements are executed.
The if statement allows conditional execution of a group of
statements.
If-else Statement
SYNTAX
If condition
Statement 1;
Else
Statement 2;
If the condition is true then statement 1 is executed else
statement 2 is executed (if it exists). Else part is optional.
LOOPS IN C
WHILE LOOP
While loop provides the mechanism for looping as long as a
specified condition is met. The while loop should be used in applications that
do not require the modification of any variables at each iteration.
SYNTAX
While (condition)
Statements
The statement may be a single statement or a block of statements
that is to be repeated. The condition may be any expression, with true being
any non-zero value. The statements are executed while the condition is true.
When the condition becomes false, program control passes to the line after the
loop code.
FOR LOOP
This is used when the statements are to be executed more than once.
This is the most widely used iteration construct. The for loop supported by C
is much more powerful than its counterpart in any other programming language.
SYNTAX
For (exp1;exp2;exp3)
{
statements;
…………….
}
Generally exp1 is an initialization, exp2 is condition checking;
exp3 is either an increment or decrement statement.
The initialization is usually an assignment statement that is used
to set the loop control variable. The condition is a relational expression that
determines when the loop will terminate. The increment determines how the loop
control variable change each time the loop is repeated.
1. Write a C program to
determine the sum of odd and even numbers.
# include<stdio.h>
# include<conio.h>
main()
{
int n, i,
seven=0, sodd=0;
int a[25];
clrscr();
printf(:\n Enter
the total number to be entered:”);
scanf(“%d”,&n);
printf(“\n Enter
the values”);
for(i=0;i<n;i++)
{
if(a[ i]%2==0)
seven=seven+a[i];
else
sodd=sodd+a[I];
}
printf(“\n The
Sum of Even number is %d”,seven);
printf(“\n The
Sum of Odd number is %d”,sodd);
getch();
}
- Write a C program to count the number of positive,
negative and zero number in the given list of numbers.
# include
<stdio.h>
# include
<conio.h>
main()
{
int n, i,
npos=0, nneg=0, nzero=0;
int a[25];
clrscr();
printf(:\n Enter
the total number to be entered:”);
scanf(“%d”,&n);
printf(“\n Enter
the values”);
for(i=0;i<n;i++)
{
if(a[ i]>0)
npos=npos+1;
if(a[I]<0)
nneg=nneg+1;
else
nzero=nzero+1;
}
printf(“\n The
number of positive value is %d”,npos);
printf(“\n The
number of negative value is %d”,nneg);
printf(“\n The
number of zeros is %d”,nzero);
getch();
}
3. Write a C program for temperature conversion.
#include<stdio.h>
#include<conio.h>
main()
{
int faren,cen;
clrscr();
printf(“\n Enter
the farenheit value :”);
scanf(“%d”,&faren);
cen=(faren-32)+5/9;
printf(“\n The
equivalent Centigrade value is %d”,cen);
getch();
}
4. Write a C program to check
whether the number is prime or not.
#include<stdio.h>
#include<conio.h>
main()
{
int
n, i;
clrscr();
printf(:\n Enter
the total number to be entered:”);
scanf(“%d”,&n);
for(i=2;i<=n/2;i++)
{
if(n%i= =0)
printf(“\n the given
number is not prime”);
break;
}
if(n%i)
printf(“\n
the given number is prime”);
getch();
}
5. Write a C program to find
whether the given number is palindrome or not.
#include<stdio.h>
#include<conio.h>
main()
{
int
n, i;
int
p,s,e;
clrscr();
printf(:\n Enter
the number :”);
scanf(“%d”,&n);
e=0;
p=n;
while(p!=0)
{
s=p%10;
e=(e*10)+s;
p=p/10;
}
if(e= = n)
printf(“\n the given number is
palindrome”);
else
printf(“\n the given number is not a
palindrome”);
getch();
}
6. Write a C program to find
the sum of digits.
#include<stdio.h>
#include<conio.h>
main()
{
int n,q,r,s=0;
clrscr();
printf(“\n Enter
the no");
scanf(“%d”,&n);
while(n!=0)
{
q=n/10;
r=n-q*10;
s=s+r;
n=q;
}
printf(“\n the sum of digits :%d”,s);
getch();
}
7. Write a program to find
whether the given number is perfect or not.
#include<stdio.h>
#include<conio.h>
main()
{
int a = 0;
int m;
printf(“Enter a number to check
whether it is a perfect number or not \n”);
printf(“ Enter a number \n”);
scanf(“%ld”,&n);
for (m=0;m<n;m++)
{
if (n % m = = 0 )
a = a + m;
}
if (a = = n)
printf(“the given number is
perfect number \n”);
else
printf(“the given number is not a
perfect number \n”);
getch();
8. Write a program to
find whether the given number is Armstrong or not.
#include<stdio.h>
#include<conio.h>
main()
{
int s = 0;
int c= 0;
int m,n,b;
printf(“Enter a number to check
whether it is a perfect number or not \n”);
printf(“ Enter a number \n”);
scanf(“%ld”,&b);
n = b;
while (b>0)
{
c = b % 10;
s = s + (c*c*c);
b = b / 10;
}
if (s = = n)
printf(“the given number is
armstrong number \n”);
else
printf(“the given number is not a
armstrong number \n”);
getch();
}
9. Write a C program to find
the given number using linear search method.
#include<stdio.h>
#include<conio.h>
main()
{
int
n,a[30],sea,flag;
clrscr();
printf(“\n
Enter the number of terms :”);
scanf(“%d”,&n);
printf(“\n
Enter the values:”);
for(i=0;i<n;i++)
scanf(“%d”,a[i]);
printf(“\n
Enter the number to be searched :”);
scanf(“%d”,&sea);
for(i=0;i<n;i++)
{
if(a[i]
= = sea)
{
flag=1;
break;
}
else
flag=0;
}
if(flag=
= 1)
printf(“\n
The given number %d is present in the position number %d”,sea,i);
else
printf(“\n
The given number is not present”);
getch();
}
10. Write a C program to find
the given number using binary search method.
#include<stdio.h>
#include<conio.h>
main()
{
int
n,a[30],sea,flag,x,y,t;
int
low,high,mid;
clrscr();
printf(“\n
Enter the number of terms :”);
scanf(“%d”,&n);
printf(“\n
Enter the values:”);
for(i=0;i<n;i++)
scanf(“%d”,a[i]);
for(x=0;x<n-1;x++)
for(y=x+1;y<n;y++)
{
if(a[x]>a[y])
{
t=a[x];
a[x]=a[y];
a[y]=t;
}
}
printf(“\n The
sorted numbers are :”);
for(x=0;x<n;x++)
printf(“%d\n”,a[x]);
printf(“\n
Enter the number to be searched :”);
scanf(“%d”,&sea);
low=0;
high=n;
while(low<=high)
{
mid=(low+high)/2;
if(t<a[mid])
high=mid-1;
if(t>a[mid])
low=mid+1;
if(t=
= a[mid])
{
printf(“\n the number %d is present
in the position %d”,t,mid);
flag=0;
break;
}
if(mid
= =1 | | mid= = n)
break;
}
if(flag)
printf(“\n
The given number is not present”);
getch();
}
- Write a program to print fibonacci series using
functions
#include
<STDIO.H>
#include
<CONIO.H>
void main()
{
int n;
void fibo(int);
clrscr();
printf(“\t\t PROGRAM TO PRINT THE
FIBONACCI SERIES \n”);
printf(“\n Enter the number of terms to be
in the series \n “);
scanf(“%d”,&n);
fibo(n);
getch();
}
void fibo(int
num)
{
int
I=1,ct,ft,st;
ft = 0;
st = 1;
printf(“\t %d
\t %d”,ft,st);
while(I<=num-2)
{
ct = ft + st;
ft = st;
st = ct;
printf(“\t%d”,ct);
I++;
}
}
12. Program to perform the matrix additions
#include
<stdio.h>
#include
<conio.h>
void main()
{
int
a[10][10],b[10][10],c[10][10],row,col,r,co,I,j,k;
clrscr();
printf(“\t\t
Matrix Addition\n”);
printf(“Enter
Row order of Matrix A : “);
scanf(“%d”,&row);
printf(“Enter
Column order of Matrix A : “);
scanf(“%d”,&col);
printf(“Enter
Row order of Matrix B : “);
scanf(“%d”,&r);
printf(“Enter
Column order of Matrix B : “);
scanf(“%d”,&co);
if ((row!=r) ||
(col != co) )
{
printf(“Matrix
Multiplication is impossible\n”);
getch();
}
else
{
printf(“Enter
First Matrix Elements : “);
for
(I=0;I<row;I++)
for
(j=0;j<col;j++)
scanf(“%d”,&a[I][j]);
printf(“Enter
Second Matrix Elements : “);
for
(I=0;I<r;I++)
for
(j=0;j<co;j++)
scanf(“%d”,&b[I][j]);
for
(I=0;I<row;I++)
for
(j=0;j<col;j++)
c[I][j] =
a[I][j] + b[I][j];
printf(“The
resultant matrix is \n”);
for
(I=0;I<row;I++)
{
for
(j=0;j<col;j++)
{
printf(“%t%d”,c[I][j]);
}
pritnf(“\n”);
}
}
13 . Program
to print the factorial number
#include
<stdio.h>
#include
<conio.h>
void main()
{
int n;
int n;
clrscr();
printf(“program
to print the factorial\n”);
printf(“\n\n
Enter the number : “);
scanf(“%d”,&n);
factorial(n);
getch();
}
void
factorial(double x)
{
double fact =
1;
for(I=1;I<=n;I++)
{
fact = fact *
I;
printf(“The
factorial of a given number is %d\n”,fact);
}
14. Program to
implement the Tower
of Hanoi
#include
<stdio.h>
#include
<conio.h>
void main()
{
void transfer(int,char,char,char);
int n;
clrscr();
printf(“\t\t TOWERS OF HANOI \n”);
printf(“How many disks ? “);
scanf(“%d”,&n);
transfer(n,’1’,’r’,’c’);
getch();
}
void transfer(int n, char from,
char to, char temp)
{
if(n>0)
{
transfer(n-1,from,temp,to);
printf(“Move
disk %d from %c to %c \n”,n,from,to);
transfer(n-1,temp,to,from);
}
return;
}
15. Program to count the number of vowels,
consonants, digits, white space characters and
in a line of
text using pointers
#include
<stdio.h>
main()
{
char line[80];
int vowels = 0;
int cons = 0;
int digits = 0;
int ws = 0;
int other = 0;
void scan_line(char line[], int *pv, int *pc, int pd, int *pw, int *po);
printf(“Enter a line of text \n”);
scanf(“%[^\n],line);
scan_line(line, &vowels, &cons, &digits, &ws,
&other);
printf(“%d %d %d %d %d”,vowels,cons,digits,ws,other);
return(0);
}
void
scan_line(char line[], int *pv, int *pc, int *pd, int *pw,int *po)
{
char c;
int count = 0;
while((c =
toupper(line[count])) != ‘\0’)
{
if (c = = ‘A’ |
| c = = ‘E’ | | c = =’I’ || c = = ‘O’ || c = = ‘U’)
++
*pv;
else if (c >
= ‘A’ && c < = ‘Z’)
++ *pc;
else if ( c
> = ‘0’ && c < = ‘9’)
++
*pd ;
else if (c = =
‘ ‘ | | c = = ‘\0’)
++ *pw;
else
++ *po;
++ count;
}
return;
}
16. Program to implement to Floyds Triangle
void main()
int n,i,j,x=1;
clrscr();
printf("\t\t\tFloyds Triangle\n");
printf("\t\t\t===============\n");
printf("Enter
the no of Lines:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
{
printf("%4d",x);
x++;
}
printf("\n");
}
getch(); }
17. Program to implement to Pascal Triangle
#include <stdio.h>
void main()
{
int i=1,j,k,m,n;
clrscr();
printf("\t\t\tPascal Triangle\n");
printf("\t\t\t===============\n");
printf("Enter
the no of Lines:");
scanf("%d",&n);
for(j=0;j<n;++j)
{
for(k=35-2*j;k>0;k--)
printf("
");
for(m=0;m<=j;++m)
{
if((m==0)||(j==0))
i=1;
else
i=(i*(j-m+1))/m;
printf("%4d",i);
}
printf("\n");
}
getch();
}
18. Program to implement sine series
#include <stdio.h>
#include <math.h>
void main()
{
float
d,x,sum=0,fact(int);
int terms,sign=1,i;
clrscr();
printf("\t\t\t
Sine Series \n");
printf("\t\t\t
=========== \n");
printf("\nEnter the X value:");
scanf("%f",&d);
printf("\nEnter the number of terms:");
scanf("%d",&terms);
x=3.14/180*d;
for(i=1;i<=terms;i+=2)
{
sum=sum+sign*pow(x,i)/fact(i);
sign=-sign;
}
printf("\nThe
value of sine(%4.2f)is %8.4f",d,sum);
getch();
}
float fact(int n)
{
float f=1;
int i;
for(i=1;i<=n;++i)
f*=i;
return(f);
}
19. Programs on Manipulations on strings
#include <stdio.h>
void main()
{
int
ch,i,j,l,m,sign,c,l1,k;
char
name[80],name1[80],name2[80],namer[80],nameff[80],ans='y';
clrscr();
printf("\t\t\tManipulations on Strings\n");
printf("\t\t\t========================\n");
printf("1.Concatenation\n");
printf("2.Reverse\n");
printf("3.Find\n");
printf("4.Replace\n");
printf("5.Length\n");
printf("Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
printf("\t\tConcatenation\n");
printf("\t\t=============\n");
printf("Enter the first string
\n");
scanf("%s",name);
printf("Enter the second string
\n");
scanf("%s",name1);
i=j=0;
while(name[i]!='\0')
{
name2[i]=name[i];
i++;
}
while(name1[j]!='\0')
{
name2[i]=name1[j];
i++;
j++;
}
name2[i]='\0';
printf("Resultant String in name2
is%s",name2);
break;
}
case 2:
{
printf("\t\tReverse\n");
printf("\t\t=======\n");
printf("Enter the string \n");
scanf("%s",name);
i=j=0;
while(name[i]!='\0')
i++;
while(--i>=0)
name1[j++]=name[i];
name1[j]='\0';
printf("\nThe reversed String
is%s",name1);
break;
}
case 3:
{
printf("\n\t\tFind\n");
printf("\t\t====\n");
printf("\nEnter first
string:");
scanf(" %[^\n]",name);
printf("Enter search string:");
scanf(" %[^\n]",name1);
l=strlen(name);
l1=strlen(name1);
for(i=0;i<l;++i)
{
c=0;
if(name[i]==name1[c])
{
m=i;
sign=0;
while(name1[c]!='\0'&&sign!=1)
{
if(name[m]==name1[c])
{
m++;
c++;
}
else
sign=1;
}
if(sign==0)
{
printf("The given string is
present");
printf("\nIts starting position
is%d",i+1);
exit(1);
k=-1;
}
}
if(k<0)break;
}
if(sign!=0)
printf("The given string is not
present");
break;
}
case 4:
{
i=0;
j=0;
strcpy(nameff," ");
puts("Enter the string:");
scanf(" %[^\n]",name);
fflush(stdin);
puts("Enter find string");
scanf(" %[^\n]",name1);
fflush(stdin);
puts("Enter replace string:");
scanf(" %[^\n]",namer);
fflush(stdin);
l=strlen(name);
strcat(namer," ");
while(i<l)
{
j=0;
for(k=0;k<80;++k)
name2[k]=' ';
while(name[i]!=' '&&name[i]!='\0')
{
name2[j]=name[i];
++i;
++j;
}
name2[j]='\0';
++i;
if((strcmp(name2,name1))==0)
{
strcat(nameff," ");
strcat(nameff,namer);
}
else
{
strcat(nameff," ");
strcat(nameff,name2);
}
}
puts("string after replacement");
puts(nameff);
break;
}
case 5:
{
i=0;
printf("Enter
String:");
scanf("
%[^\n]",name);
while(name[i]!='\0')
i++;
printf("\nThe
length of the given string is%d",i);
break;
}
}
getch();
}
Data Structures
An introduction to C:
Dennis Ritchie at AT & T Bell
laboratory, Murray Hill , New Jersey
How to run C
program:
1.
From the Ms Dos prompt start C by typing ‘tc’.
2.
Open a file by selecting File | Open | File name from
the IDE menu. Or press
F3 Key
3.
Run the program by selecting Run | Run, Or press
Ctrl+F9 Key
4.
To see the program’s output select Window | User screen
or press
Alt+F5 Key.
We may compile and
run the programs from the Dos command
Line like tcc Filename <Enter>.
After the program is compiled, we may run
it and view the output by typing
Filename <Enter>
Problem solving using computer:
To solve a problem using
a computer, the following steps are required :
Ø
A program is developed using a high level
programming language (program development)
Ø
The developed program is entered into a commuter
(Program editing).
Ø
The edited program is translated and is produced
as an executable machine code.
Ø
The Executable machine code is run in the
computer to carry out the actual task (execution).
To implement the above
steps, the programmer develops a program and the developed program is entered
and edited with the help of an editor. Normally the editor is provided along with
the compiler. After editing the program, the compilation commands us used for
the translation process. Then the execution command is used to run the program
to get the desired output.
Compilation:
High-level languages allow some
English –like words and mathematical expressions that facilitate the better
understanding of the logic involved in a program. High-level languages are
machine independent. Since a computer system cannot follow programs written in
a high language, high language programs are translated into low-level language
programs and then executed.
Translation of a high-level language program
to allow level language program is done by software known as Compiler. Object
code is an intermediate code between the source code and the executable code.
Linking:
Linker performs the linking of libraries with the
object code, to make the generated object code into an executable machine code.
Thus the object code becomes an input to the linker, which produces an
executable machine code. Sometimes programs are divided into modules and these
modules are compiled separately and then linked by the linker and executed.
When running a program, the following files will be
created automatically.
Þ OBJ (Object file)
Þ EXE (Executable file)
Þ Bak
(Backup file)
Þ SWP (Swap file)
Data Structures Definition
Data
Structure is a specialized format for storing data so that the data’s can be
organized in an efficient way.
Classification
 |
|||
 |
|||
Primitive Non – Primitive
Example:
-
·
Integer
·
Real
·
Character Linear Non – Linear
·
Pointer Example:
- Example: -
·
Logical ·Linear
List ·
Graph
·
Stack ·Tree
·
Queue
Array
An array is
a finite collection of similar elements stored in contiguous location. The
operations done on an array are: -
·
Insertion
·
Deletion
·
Changing a particular element
Linked List
There are
three types of linked lists. They are: -
v Single
Linked List
v Doubly
Linked List
v Singly
Circular Linked List
v Doubly
Circular Linked List
Single Linked List
Node structure
 |
The data
field contains the data elements that have to be stored in the list. The pointer
will point the next node in the list.
The
operations done on a list are: -
ä Insertion
ä Deletion
Insertion
ä Insertion
in the head node
To
insert a node in the head node, just change the pointer field of the new node
to point to the head node. Let the new node be ‘Temp’ and the head node
be ‘Head’, then the insertion is
Temp ® data = X;
Head ® next = head
ä Insertion
in the middle node
To insert in the
middle node we need to change two pointers. Let the new node be ‘Temp’
and the present node is ‘Present’ and, the next node to the present node
is ‘future’. The pointers used are ‘data’ for the data field, ‘next’
to the pointer field, the data to be inserted is ‘X ’then the
insertion is
Temp ® data = X
Present ® next = temp
Temp
®
next = future
ä Insertion
in the last node
To insert an
element in the last position just change the pointer field of the present last
node to point to the new node, then set the pointer field of the new node to NULL.
Let the new node be ‘Temp’ and the present node is ‘Present’. The
pointers used are ‘data’ for the data field, ‘next’ to the
pointer field, the data to be inserted is ‘X ’then the insertion
is
Present ® next =Temp
Temp
®
next =null
Temp
®
data = X
Deletion
Ø
Deletion in the head node
To delete a node
in the head node, just point the head node as the second node. Let the head
node be ‘Head’, and then the deletion is
Head
®
next = head
Ø
Deletion in the middle node
To delete a node
in the middle we need to change two pointers. Let the node to be deleted
is ‘Temp’ and the node previous
to the node to be deleted is ‘Present’ and, the next node to the present
node is ‘future’. The pointers used are ‘data’ for the data field, ‘next’ to the pointer
field, the data to be inserted is ‘X ’then the insertion is
Present ® next = future
Ø
Deletion in the last node
To
delete an element in the last position just change the pointer field of the previous
node to the last to null. Let the last node be ‘Temp’ and the
previous node is ‘Present’. The pointers used are ‘data’ for the
data field, ‘next’ to the pointer field, the data to be inserted
is ‘X ’then the insertion is
Previous ® next =NULL
Singly Circular Linked List
The advantage of using Circular Linked List is the last null
pointer is replaced and the pointer field of the last node points to the
first node, due to this circular arrangement the traversing become quite
easier. The insertion and deletion in the first and middle are same as singly
linked list except the last node.
Insertion
·
Insertion in the last node
To
insert a node in the last position, insert the new node after the current last
node, and then change the pointer field of the new node to point to the first
node. Let the last node be last, the new node to be inserted to be new,
the first node in the list to be first. The pointers used are ‘data’
for the data field, ‘next’ to the pointer field, the data to
be inserted is ‘X ’then the insertion is
Last ® next = new
New
®
next =first
Deletion
·
Deletion in the last node
To delete a node in the last position, change the pointer field of the
previous node to the current last to point the first node. Let the last node be
last, the previous node to the current last node to be pre, the
first node in the list to be first. The pointers used are ‘data’ for
the data field, ‘next’ to the pointer field, the data to be
inserted is ‘X ’then the deletion is
Prev ® next = first
Stack
An important
subclass of lists permits the insertion and deletion of an element to occur
only at one end. A linear list of this type is known as ‘stack’. The
insertion is referred to as ‘push’. The deletion is referred to as ‘pop’.
The two pointers used for accessing is top & bottom pointer.
|
PUSH – Storing
the element into the stack.
Check top<= allowed size if
yes increment the top position and store the value in the top position.
POP -
Deleting the element from the stack. If top<= we can not delete.
Otherwise decrement the top by one
and return the top+1 element.
Queue
The
information in this list is processed in the same order as it was received,
that is first in first out order (FIFO) or a first – come first – served (FCFS)
basis. This type of frequently used list is known as queue. We have two
pointers to access the queue. They are
1. Front
(used for deletion)
2. Rear
(Used for insertion)
Insertion :
if rear>n queue overflow
else
increment the rear pointer and insert the
value in the rear position.
Deletion :
Else
Increment
the front pointer and return the front-1 value
Tree
An
important class of digraph, which involves for the description of hierarchy. A
directed tree is an acyclic digraph which has one node called root with
in degree 0, while other nodes have in degree 1. Every directed tree must have
at least one node. An isolated node is also called as directed tree. The node
with out degree as 0 is called as leaf. The length of the path from root to
particular node level of the node. If the ordering of the node at each level is
prescribed then the tree is called as ordered tree.
Binary Tree
If a
tree has at most of two children, then such tree is called as Binary tree. If
the elements in the binary tree are arranged in the following order
Left
element is lesser than the root
Right
element is greater then the root
No
duplication of elements
Then such binary tree is called as Binary Search Tree
Operations performed in a binary tree are:
- Inserting a node
- Deleting a node
- Traversing the tree
Traversing Methods
1. Pre
– order method
2. In
– order method
3. Post
– order method
4. Converse
Pre – order method
5. Converse
In – order method
6. Converse
post – order method
Pre – order
method
This
method gives the tree key value in the following manner: -
1. Process
the root
2. Traverse
the left sub tree
3. Traverse
the right Sub tree
In – order method
This
method gives the tree key value in the following manner: -
1. Traverse
the left sub tree
2. Process
the root
3. Traverse
the right Sub tree
Post – order
method
This
method gives the tree key value in the following manner: -
1. Traverse
the left sub tree
2. Traverse
the right Sub tree
3. Process the root
Sorting Sorting is, without doubt, the most fundamental algorithmic problem
- Supposedly, 25% of all CPU cycles are spent
sorting
- Sorting is fundamental to most other
algorithmic problems, for example binary search.
- Many different approaches lead to useful sorting
algorithms, and these ideas can be used to solve many other problems.
What is sorting?
It is the problem of taking an arbitrary permutation of n items and rearranging
them into the total order,
Issues in Sorting
Increasing or Decreasing Order? - The same algorithm can be used by both all we need do is change
to 
in the
comparison function as we desire. What about equal keys? – May be we need to sort on secondary keys, or leave in the same order as the original permutations.
What about non-numerical data? - Alphabetizing is sorting text strings, and libraries have very complicated rules concerning punctuation, etc. Is Brown-Williams before or after Brown
We can ignore all three of these issues by assuming a comparison function which depends on the application. Compare (a,b) should return ``<'', ``>'', or ''=''.
Applications of Sorting
One reason why sorting is so important is that once a set of items is sorted, many other problems become easy.
Heaps
A heap is a complete binary tree with values
stored in its nodes such that no child has a value bigger than the value of the
parent. Below is a heap.
9
/ \
8 2
/ \
6 4
A heap provides a representation for a priority queue.
Example: messages processed by priority at a server - messages given priority weighting, higher
numbers give better service
- highly dynamic, messages coming and going
frequently
- need efficient insert new message and remove
highest priority message
9
/ \
8 2
/ \
6 4
then we reheapify
by copying rightmost leaf to root (4 becomes the root)
4
/ \
8 2
/
6
and then we
recursively reestablish the heap property as follows: if the parent is greater
than a child, swap the parent with the highest priority child. Keep swapping
until no more swaps are possible. So in the above tree, first we would swamp 4
with 8.
8
/ \
4 2
/
6
Then we would
swap 4 with 6.
8
/ \
6 2
/
4
The final swap
yields a heap!
The cost of removing an item (reheapifiying after
removing the item) is O(log n). The algorithm just traverses one path in the
tree, which is O(log n) in length. For each node on that path it performs at
most two comparisons and one swap (3 operations -> constant time). So
overall the algorithm has a worst case time complexity of O(log n). Space complexity is O(n) since a sequential array representation can be used.
Quick sort
is a very efficient sorting algorithm invented by C.A.R. Hoarer. It has two phases:
- The partition phase and
- The sort phase.
As we will see, most of the work is done in the partition
phase - it works out where to divide the work. The sort phase simply sorts the
two smaller problems that are generated in the partition phase.
This
makes Quick sort a good example of the divide and conquers strategy for
solving problems. (You've already seen an example of this approach in the binary search procedure.) In quick sort, we
divide the array of items to be sorted into two partitions and then call the
quick sort procedure recursively to sort the two partitions, i.e. we divide
the problem into two smaller ones and conquer by solving the smaller
ones. Thus the conquer part of the quick sort routine looks like this: quicksort( void *a, int low, int high )
{
int pivot;
/* Termination condition! */
if ( high > low )
{
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
}
|
 Initial Step - First Partition |
 Sort Left Partition in the same way |
To do this, we choose a pivot element
and arrange that all the items in the lower part are less than the pivot and
all those in the upper part greater than it. In the most general case, we don't
know anything about the items to be sorted, so that any choice of the pivot
element will do - the first element is a convenient one.
Dijkstra's AlgorithmDjikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem.
Graph Traversal
Systematic traversals of graph are similar to preorder and
post order traversal for trees. There are two graph traversals,
depth-first and breadth-first search. Frequently the graph searches start
at an arbitrary vertex. The searches are efficient if they are done in O(n
+ m), where n is the number of vertices and m the number of
edges.
Graph traversal can be used to determine the general characteristic of the graph, or to solve a specific problem on a particular graph, for example:
Graph traversal can be used to determine the general characteristic of the graph, or to solve a specific problem on a particular graph, for example:
- Routing phone calls, or packets
- Planning a car trip
- Locate particular vertices, for example a win position in a game.
Depth-first
Search
We start the graph traversal at arbitrary vertices, and go
down a particular branch until we reach a dead end. Then we back up and
go as deep possible. In this way we visit all vertices, and all edges.
Breath-First Search
Breadth-first search visit all adjacent vertices before going
deeper. Then we go deeper in one of the adjacent vertices.
Sparse Matrix :
A
matrix consists of more number of zeros is called sparse matrix. Once the
matrix is stored as it is then there is wastage of memory. For an efficient
memory utilization the sparse matrix can be stored in a linear form. The linear
form can be of array type or linked list type.
DATA STRUCTURES
Definition:
Data
structure is collection of data elements organized in a specified manner and
accessing functions are defined to store and retrieve individual data elements.
Data structures are sometimes called Data types.
Classification of Data Structure:
A
data type may be defined as a set and the elements of the set are called the
values of the type. There are four basic or atomic or primitive data types in
C. They are int, float, char and double. The Simple data types built from
primitives are arrays , pointers, strings and records with which we can build
new types called structured or composite types such as stacks, queues, and
trees etc. The structured data types can be categorized as linear and
non-linear. The linear data structures are stacks, queues and linked lists. The
non-linear data structures are trees and graphs.
Stacks
Definition:
A stack is
an ordered collection of items into which new items may be inserted and from
which items may be deleted at one end, called the top of the stack. The first
example of stack, which permits the selection of only its end element , is a pile
of coins.
Second example could be a pile of trays or a books lying one
above the other.
Let us draw a stack
containing integers as in the following figure.
 5 |
|
9
|
|
1
|
|
3
|
|
7
|
top
Here, 5 is the current of the stack. If we add any element
in the stack, it will be placed on top of 5 , and if we delete an element , it
will be 5, which is on top of the stack.
Operations on Stacks:
Associated
with the stack , there are several primitives operations. We can define the
following necessary operations on stack.
a) create(s) - To create s as an empty stack.
b) push(s,i) - To
insert the element I on top of the stack s.
c) pop(s) -
To remove the top element of the stack and to return the removed
element as a function value.
d) top(s) -
To return the top element of stack(s).
e) empty(s) - To
check whether the stack is empty or not. It returns true if stack is empty and
returns false otherwise.
If a stack is
empty and it contains no element, it is not possible to pop the stack.
Therefore, before popping an element, we must ensure that the stack is not
empty.
PUSH & POP OPERATIONS:
When we add an
element to a stack, we stay that we push it on the stack and if we delete an
element from a stack, we say that we pop it from the stack. Let us see how
stack shrinks or grows when we pop or push an element in the following figures.
Push (8) on the stack
 8 |
|
5
|
|
9
|
|
1
|
|
3
|
|
7
|
top
Push (4) on to stack
 4 |
|
8
|
|
5
|
|
9
|
|
1
|
|
3
|
|
7
|
top
Pop an element from the stack
|
|
|
8
|
|
5
|
|
9
|
|
1
|
|
3
|
|
7
|
Top Popped element = 4
Pop an element from the stack
|
|
|
|
|
5
|
|
9
|
|
1
|
|
3
|
|
7
|
Top Popped element = 8
We may notice that
the last item pushed onto a stack is always the first that will be popped from
the stack. That is why stack is called
last in, first out or LIFO in short.
Implementation of Stacks
There are two ways to implement
stacks, one using arrays and other is
using linked list.
Array:
Since the elements of the stack are
ordered , an obvious choice would be an array as a structure t contains a
stack. We can fix one end of the array as bottom of the stack. The other end of
the array may be used as a top of the stack, which keeps shifting constantly as
items are popped and pushed. We must store the index of the array
containing the top element.
We can , therefore, declare a
stack as a structure containing two fields- an array to hold the elements of
the stack, and an integer top to indicate the position of the current top of
the stack within the array.
# define MAX 50
struct stack{
int top;
int
elements [5];
};
struct stack s;
Here s is defined to be a stack
containing elements of type integer . The maximum number of elements in the
stack is defined to be 50. Elements [0] contain the first element so that the
value of top is 0. If there are five elements in the stack, the value of top
will be four and the top element is in elements[4].
A stack is empty when it contains
no elements we can indicate this by making top as –1. We can write our function
clearstack as
clearstack(ts)
struct stack *ts;
{
ts->top = -1;
}
Another operation is to check
whether the stack is empty. To do this we must check whether s.top = = -1.
Let us now consider the PUSH operation . To push or add an
element we must perform the two steps:
i.
increment top indicator
ii.
put the new element at the new top.
We might code the PUSH & POP operations as follows:
push(ts,x)
Struct stack *ts;
Int x;
{
if (fullstack(ts)){
printf( “ %s”, “ Stack overflow”);
exit(1);
}
else
ts->elements[++(ts->top)]
= x;
return;
}
This routine increments the top
by 1 and puts x into array s.elements at the new top position. In this routine
we use another routine Full Stack which checks whether the stack is full,
before we push an element onto stack. A stack is full when ts->top = =
MAX-1.
Full Stack routine as follows:
fullstack (ts)
struct stack *ts;
{
if ( ts->top = = MAX-1)
return(1);
else
return(0);
}
To remove an element or pop
an element from the stack, we must first check the possibility of underflow as
it is quite possible that somebody tries to pop an element from an empty stack.
Therefore, we can write function POP as,
Pop(ts)
struct stack *ts;
{
if (empty(ts))
printf( “ % s” , “ stack underflow”);
return(0);
else
return(ts->elements[ts->top--]);
}
We can write function empty (s)
that returns 1 if the stack is empty and 0 if it is not empty as follows:
empty(ts)
struct stack *ts;
{
if ( ts -> top = = -1)
return (1);
else
return(0);
}
Stack as a Linked List ( Using Pointers):
Using this representation we are using the pool of available nodes and
we will never have to test whether a particular stack is full. We can declare
such as a stack as follows.
Node structure:
Each node has two fields. i.e.
Data and Next field
 |
Data field Next field
Stack- Node representation:
A B C D
Stack End
node
Top element
Declaration : ( Using C++)
# include <iostream.h>
# include < process.h>
class sta{
struct node {
int data;
node * next;
} *stack ;
public :
void push();
void pop();
void disp();
}
PUSH OPERATION:
Void sta :: push()
{
int n;
node temp;
temp = new node;
3
cout << “ Push the element “ <<
endl; ( First node of
temp the stack).
cin >> temp->data;
temp->next=NULL; stack
if(stack= = NULL)
stack=temp;
else 3
{
temp->next=stack; stack
stack=temp; 4
} 4
temp
}
4 3
stack 
POP Operation:
stack 2 4 3
Void sta :: pop() 
{ temp
node *temp;
if (stack= = NULL)
cout << “ Stack is empty “
<< endl;
else { stack
temp= stack;
stack= stack->next; temp
cout << “Popped element “
<< endl;
cout << temp->data;
delete temp;
}
}
TREE TRAVERSAL:
When
traversing a binary tree, we want to treat each node and its sub trees in the
same fashion. If we let L, V, and R stand for moving left, visiting the node,
and moving right when at a node, then there are six possible combinations of
tree traversal: LVR, LRV, VLR, VRL, RVL, and RLV. If we adopt the convention
that we traverse left before right, then only three traversals remain : LVR,
LRV and VLR. To these we assign the
names inorder, postorder, and preorder, respectively, because of the position
of the V with respect to the L and the R.
Procedure for Preorder:
1. Visit the
root node.
2. Traverse the
Left sub tree in preorder.
3. Traverse the
Right sub tree in preorder.
Example:
Fig.1
The result is :
+ A B
Algorithm:
void preorder(node
*nodeptr)
{
if ( nodeptr
!= NULL)
{
printf(“%d\n”, nodeptr->data);
/* visit the root node */
preorder(nodeptr->left);
/* Traverse the left sub tree */
perorder(nodeptr->right); /* Traverse the right sub tree */
}
}
Procedure for Inorder:
1. Traverse the
Left sub tree in inorder.
2. Visit the
root node
3. Traverse the
Right sub tree in inorder.
Fig.2
The result is : A + B
void inorder( node
*nodeptr)
{
if ( nodeptr
!= NULL)
{
inorder(nodeptr->left); /*
Traverse the left sub tree */
printf(“%d\n”, nodeptr->data);
/* Visit the root node */
inorder(nodeptr->right); /*
Traverse the right sub tree */
}
}
Procedure for Postorder:
1. Traverse the
Left sub tree in postorder.
2. Traverse
the Right sub tree in postorder.
3. Visit the
root node.
Fig.3
The result is : A B +
void postorder( node
* nodeptr)
{
if (nodeptr
!= NULL)
{
postorder(nodeptr->left); /*
Traverse the left sub tree */
postorder(nodeptr->right); /*
Traverse the right sub tree */
printf(“%d\n”, nodeptr->data);
/* Visit the root node */
}
}
Fig.4
PRE ORDER : A,B,D,C,E,AND F
IN ORDER
: B,D,A,E,F,C
POSTORDER : D,B,F,E,C,AND A
Fig.5.
PREORDER : * + A
B / C D
INORDER
: A + B * C / D
POSTORDER : A B + C D / *
BINARY SEARCH TREES
Definition:
A
binary search tree is a binary tree. It may be empty. If it is not empty then
it satisfies the following properties:
- Every element has a key and no two elements have the same key.
- The keys in the left sub tree are smaller than the key in the root.
- The keys in the right sub tree are larger than the key in the root.
- The left and right sub trees are also binary search trees.
It has two
operations. They are,
1. Insertion
2. Deletion
Example Fig.
To construct (Insertion) the Binary search tree for the
following elements:
25, 15,
27, 13, 17, 26, 29, 28
To delete a particular node from
the Binary search tree:
1. Leaf node
Deletion of a leaf node is quite easy. To delete 28 from the below tree
the left child field of its parent is set to 0 and the node disposed. To delete
the 17 from this tree, the right-child field of 15 is set to 0 , and the node
containing 17 is disposed.
To delete a leaf node 28
To delete a leaf node 17
2. Non-leaf node:
The deletion of a non-leaf element or
node that has only one child is also easy. The node containing the element to
be deleted is disposed, and the single-child takes the place
of the disposed node.
So, to delete the element 15 from
the above tree, we simply change the pointer from the parent node (25) to the single-child node(13).
3. Root node:
When the element to be deleted is in a non-leaf node that has two children, the element is
replaced by either the largest element in its left sub tree or the smallest one
in its right sub tree. Then we proceed to delete this replacing element from
the sub tree from which it was taken.
If we wish to delete the element with key 25 from the above tree, then
we replace it by either the largest element, 17 , in its left sub tree or the
smallest element , 26 , in its right sub tree.
Suppose we opt for the largest element in the left sub tree. The 17 is
moved in to the root and the following tree is obtained.
HEAPS
Priority Queue:
The priority queue is a
data structure in which the intrinsic ordering of the elements does determine
the results of its basic operations. There are two types of priority queues:
An ascending priority
queue and a descending priority queue.
An ascending priority queue is a
collection of items into which items can be inserted arbitrarily and from which
only the smallest item can be removed. A descending priority queue is similar
but allows deletion of only the largest item.
Heaps Definition:
A max (min) heap is a tree
in which the key value in each node is no smaller (larger) than the key values
in its children (if any). A max heap is a complete binary tree that is also a max tree. A min heap is a complete
binary tree that is also a min tree.
Max. Heap
Min. Heap
QUEUE
Definition:
A queue is an ordered collection of
items from which items may be deleted at one end ( called the front of the
queue) and into which items may be inserted at the other end ( called rear of
the queue). This data structure is commonly known as FIFO or first-in-
first-out.
Fig.1
|
|
3 |
6 |
|
Fig.2
|
|
3
|
6
|
8
|
|
OPERATION S
ON QUEUES:
It has two operations. They are
Ø
Insertion
Ø
Deletion
Insertion an element is popularly
known as ENQ and deleting an element is known as DEQ. A minimum set of useful
operations on queue includes the following.
i.
CREATEQ(Q) – which creates Q as an empty Queue.
ii.
ENQ(i) – which adds the element I to the rear of a
queue and returns the new queue.
iii.
DEQ(Q)- which removes the element at the front end of
the queue and returns the resulting queue as well as the removed element.
iv.
EMPTY(Q)- It checks the queue whether it is empty or
not and returns true if it is empty and returns false otherwise.
v.
FRONT(Q)- which returns the front element of the queue
without changing the queue.
vi.
QUEUESIZE(Q)-which returns the number of entries in the
queue.
We can obtain the queue by the
following sequence of operations. We assume that the queue in initially empty.
ENQ(q,8)
|
5
|
7
|
8
|
|
|
ENQ(q,9)
|
5 |
7
|
8
|
9 |
|
ENQ(q,4)
 5 |
7
|
8
|
9
|
4 |
x =DEQ(q) Element 5 is deleted
|
7
|
8
|
9
|
4
|
 |
 |
||
x =DEQ(q) Element 7 is deleted
|
8
|
9
|
4
|
IMPLEMENTING THE QUEUE
There
are two ways to implement queue, one using arrays, and another is using Linked
list.
i.
Array :
Let us implement the queue within an array so that the array holds the
elements of the queue. There are two variables front and rear to indicate the
positions of the first and last element of the queue within the array.
Let the size of the array be 4. Initially let us assume that
the queue is empty which means front = 0 and rear = -1.
Empty Queue:
|
|
|
|
|
q[0] q[1] q[2] q[3]
front = 0(array
position) rear = -1 ( NULL)
Insertion:
There
are two variables front and rear to indicate the positions of the first and
last element of the queue within the array. Let the size of the array be 4.
Initially let us assume that the queue is empty which means front = 0 and rear
= -1.After we have added three elements to the queue rear becomes 2 and front
becomes 0. Now if we add one more elements to the queue from the rear, the
value of rear changes to 3. Now the queue becomes full.
ENQ(q,3)
|
3
|
|
|
|
q[0] q[1] q[2] q[3]
front = 0 rear
=0
ENQ(q,5)
|
3
|
5
|
|
|
q[0] q[1] q[2] q[3]
front = 0 rear =
1
ENQ(q,7)
|
3
|
5
|
7
|
|
q[0] q[1] q[2]
q[3]
front = 0 rear = 2
ENQ(q,9) [ Q is full ]
|
3
|
5
|
7
|
9
|
q[0] q[1] q[2]
q[3]
front
= 0 rear = 3
Deletion:
At this point, we delete one
element. The element which is deleted is 3. This leaves a hole in the first
position. To delete this element we must increment front, to indicate the true first
element of the queue and assign the value of that slot to x. To check whether
queue is empty or not, we must check whether front = rear.
To add an element we must
increment rear so that it points to the location next to the rear and place an
element in that slot of the array. If we wish to add another element, and we
increment rear by 1, rear becomes equal to front, which indicates that the
queue is full.
X= DEQ(q)
|
|
5
|
7
|
9
|
q[0] q[1] q[2]
q[3]
front = 1 rear = 3
x=DEQ(q)
|
|
|
7
|
9
|
q[0] q[1] q[2] q[3]
front = 2 rear = 3
x=DEQ(q)
|
|
|
|
9
|
q[0] q[1] q[2] q[3]
front = 3 rear
= 3
x=DEQ(q) [ Queue is empty]
|
|
|
|
|
q[0] q[1] q[2] q[3]
front = rear = -1(NULL)
Therefore, the condition for full
queue is that the next slot of rear is equal to front and the condition for
empty queue is that front = rear. Before we DEQ an element from queue we must
make sure that queue is not empty and before we ENQ an element we must ensure
that the queue is not full.
Queue implementations in ARRAY
using C++
class qu{
Public :
Int front, rear, n , q[10];
void get(){
cout<< “ Enter the Queue size “
<< endl;
cin>> n;
front = rear =-1;
}
void enq();
void deq();
};
int I, a[10];
void qu :: enq(){
int item;
if ( rear >= n)
{
cout << “ Queue is full
\n”;
return;
}
else
{
cout << “ Enter the item
to be inserted” <<endl;
cin>>item;
rear = rear+1;
q[rear] = item;
i++;
}
}
void qu :: deq()
{
int t;
if ( front >= rear)
{
cout << “ Queue is Empty”
<< endl;
return;
}
else
{
front = fornt +1;
t = q[front];
cout << “ The deleted
element : “ << t << endl;
}
}
Implementation of Queue as Linked list
Another
way of implementing queues is as a linked list. Let us have two pointers, front
to the first element of the list and rear to the last element of the list.
|
4
|
|
|
6
|
|
 8 |
|
front
rear
.
class que {
struct node
{
int data;
node *next;
} * front, *rear;
public:
void insq();
void delq();
que(){
front = rear =
NULL;
}
};
void que :: insq()
{ temp
|
4
|
|
int n;
node *temp;
temp = new node;
front
cout << “ Insert the element “
<< endl;
cin >> n;
temp-data = n;
temp->next = NULL;
if ( front = = NULL)
front = rear=temp;
|
4
|
 |
else
|
5
|
|
{
rear->next = temp; front
rear= rear->next;
rear
}
}
void que :: delq()
{
|
4
|
|
node *temp;
|
6
|
 |
temp = front; temp
8 |
 |
if ( front = = NULL)
front
cout << “ Queue is empty
“ << endl;
else
{ rear
front = front->next;
cout << temp->data;
delete temp;
}
}
DEQUE:
A single queue behaves in a FIFO manner
in the sense that each deletion removes the oldest remaining item in the
structure. A double ended queue or deque, in short is a linear list in which
insertions and deletions are made to or from either end of the structure.
Deletion Insertion|
|
|
|
|
Insertion
Deletion
Front
RearWe can have two variations of a
deque, namely, the input-restricted deque and the output –restricted deque. The
output-restricted deque allows deletion from only one end and input-restricted
deque allows insertions at only one end.
Queue Applications:
The most useful
application of queues is the simulation of a real world situation so that it is
possible to understand what happens in a real world in a particular situation
without actually observing its occurrence.
Queues are also very useful in a
time-sharing computer system where many users share the system simultaneously.
Whenever a user requests the system to run a particular program, the operating
system adds the request at the end of the queue of jobs waiting to be executed.
Whenever the CPU is free, it executes the job, which is at the front of the job
queue. Similarly there are queues for sharing I/O devices. Each device
maintains its own queue of request.
Another
useful application of queues is in the solution of problems involving searching
a nonlinear collection of states. Queue is used for finding a path using
breadth-first-search of graphs.
LINKED LIST
Definition:
A collection of node is
called list. Each node or item in a linked list must contain at least two
fields, an information field or data field and the next address field. The
first, field contains the actual element on the list which may be a simple
integer, a character, a string or even a
large record. The second field, which is a pointer, contains the address of the
next node in the list used to access the next node. A node of a linked list may
be represented by the following figure.
|
Data
or
Info
|
Next |
List
( External pointer)
The entire linked list is
accessed from an external pointer List pointing to the first node in the list.
We can access the first node through the external pointer, the second node
through next pointer of the first node, the third node through the next pointer
of the second node till the end of the list.
The next address field of the
last node contains a special value, known as the NULL value. This is not a
valid address. This only tells us that we have reached the end of the list. We
will draw linked lists as an ordered sequence of nodes with links being
represented by arrows.
List
|
4
|
 |
|
5
|
 |
|
6 |
 |
OPERATIONS ON LINKED LIST
There are
five basic types of operations associated with the list data abstraction:
1.
To determine if the list is empty. Returns true if the
list contains no elements.
2.
Add new elements any in the list
3.
To check if a particular element is present in the
list.
4.
To delete a particular element from the list placed
anywhere in the list.
5.
To print all the elements of the list.
We will introduce some notations
to be used in algorithms:
If p is
a pointer to a node, then
node(p) refers to the node pointed to by p
info(p) refers to the data part of that node
next(p) refers to the address part of that node
info(next(p)) refers to the data part of the next node which node, which
follows node(p)
in the list if next(p) is not null.
We can initialize the list by
making the external pointer null.
List = null
Also, we can check whether the
list is empty by checking whether the external pointer is null.
if
list = null
then return(true)
else return(false)
This routine will return true if
the list is empty, otherwise it will return false.
To traverse or to
print the elements of a linked list, we need to use a temporary pointer, p
known as a traversal pointer.
P
= list
while list < > null do
begin
print( info(p))
p= next(p)
end
Inserting into a Linked list
To add a new node containing data value x in
the beginning of the list we need to follow the step:
i. To get a new node which is not in use.
ii. To set the data field of the new node to x
iii. To set the next field of the new node to
point to list
iv. To set pointer list point to the new node.
To do this we can write the
following algorithm:
getnode(p)
info(p)
= x
next(p)
= list
list
= p
We are assuming that the
operation getnode(p) obtains an empty node and sets the contents of a variable
named p to the address of that node.
|
|
|
p
Getnode(p)
p
|
x
|
|
Info(x) = p
p List
|
x
|
|
|
5
|
|
|
6 |
|
next(p)
= list
List
|
4
|
|
|
5
|
|
|
6 |
|
p
list
= p
Sample programs :
Ex. No. 1 Stack
Program:
#include<stdio.h>
#include<conio.h>
int top=1;
int a[20];
void main()
{
int n,x,b,c,i,temp;
clrscr();
printf("Enter the no of elements\n");
scanf("%d",&n);
do
{
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.DISPLAY\n");
printf("4.EXIT\n");
break;
printf("enter your choice\n");
scanf("%d",&b);
switch(b)
{
case 1:
printf("enter the number\n");
if(top>=n+1)
printf("\nstack is overflow\n");
else
scanf("%d",&x);
a[top]=x;
top=top+1;
break;
case 2:
if (top<=0)
printf("stack is underflow\n");
else
{
top=top-1;
temp=a[top];
}
break;
case 3:
for(i=1;i<top-1;i++)
printf("%d-->",a[i]);
printf("%d",a[top-1]);
break;
case 4:
exit(0);
}
printf("\ndo you want
to continue(1/0)\n");
scanf("%d",&c);
}
while(c==1);
getch();
}
Ex. No. 2 Queue
Program:
#include<stdio.h>
#include<conio.h>
int n,x,b,c,i,r=0,f=0,te;
int q[20];
void
main()
{
clrscr();
printf("Enter the no of
elements\n");
scanf("%d",&n);
do
{
printf("1.insertion\n");
printf("2.deletion\n");
printf("3.display\n");
printf("4.exit\n");
printf("enter your choice\n");
scanf("%d",&b);
switch(b)
{
case 1:
insert();
display();
break;
case 2:
delet();
display();
break;
case 3:
display();
break;
case 4:
exit(0);
}
printf("\ndo you want to
continue(1/0)\n");
scanf("%d",&c);
}
while(c==1);
getch();
}
insert()
{
if(r>=n)
printf("\nqueue
is overflow\n");
else
{
printf("enter the
number\n");
scanf("%d",&x);
r=r+1;
q[r]=x;
}
if(f==0)
f=1;
return(0);
}
int delet()
{
int te;
if (f==0)
printf("queue is underflow\n");
else if (f==r)
{
f=0;r=0;
}
else
{
te=q[f];
f=f+1;
}
return(te);
}
display()
{
if(r==0)
{
printf(" queue is empty");
}
else
{
for(i=f;i<r;i++)
printf("%d-->",q[i]);
printf("%d",q[r]);
}
return(0);
}
Ex. No: 3 Singly Linked list
Program:
#include<stdio.h>
#include<conio.h>
#define
null 0
int
a,s;
struct
node
{
int data;
struct node *link;
};
struct node *head,*first,*previous,*temp;
void main()
{
first=null;
head=null;
clrscr();
do
{
printf("1.creation\n");
printf("2.display\n");
printf("3.insert first\n");
printf("4.insert last\n");
printf("5.insert middle\n");
printf("6.delete first\n");
printf("7.delete last\n");
printf("8.delete middle\n");
printf("enter your choice");
scanf("%d",&a);
switch(a)
{
case 1:
create();
display();
break;
case 2:
display();
break;
case 3:
insfirst();
display();
break;
case 4:
inslast();
display();
break;
case 5:
insmiddle();
display();
break;
case 6:
delfirst();
display();
break;
case 7:
dellast();
display();
break;
case 8:
delmiddle();
display();
break;
case 9:
exit(0);
}
printf("\ndo you want to
continue(1/0)\n");
scanf("%d",&s);
}
while(s==1);
}
create()
{
int
s;
s=sizeof
(struct node);
first=(struct
node*) malloc (s);
printf("enter
the data");
scanf("%d",&first->data);
first->link=null;
if(head==null)
head=first;
else
{
previous=head;
while(previous->link !=null)
previous=previous->link;
}
previous->link=first;
previous=first;
return(0);
}
display()
{
if(head==null)
printf("null first");
else
temp=head;
while(temp!=null)
{
printf("%d->",temp->data);
temp=temp->link;
}
printf("null\n");
return(0);
}
insfirst()
{
int s;
if (head==null)
printf("list is null");
else
{
s=sizeof (temp);
temp=(struct node*) malloc(s);
printf("enter data\n");
scanf("%d",&temp->data);
temp->link=head;
head=temp;
}
return(0);
}
delfirst()
{
int
s;
if(head==null)
printf("list
is null");
else
head=head->link;
return(0);
}
inslast()
{
int s;
struct node *temp,*last;
if (head==null)
printf("list is null");
else
{
s=sizeof
(last);
last=(struct
node*) malloc(s);
printf("enter
the data\n");
scanf("%d",&last->data);
last->link=null;
temp=head;
while(temp->link!=null)
temp=temp->link;
temp->link=last;
}
return(0);
}
dellast()
{
int
s,m;
struct
node *pre,*next;
if(head==null)
printf("list is
null");
else
{
next=head;
next=head->link;
pre=head;
while(next->link!=null)
{
next=next->link;
pre=pre->link;
}
pre->link=next->link;
}
return(0);
}
insmiddle()
{
int
s,f,count;
struct
node *next,*pre,*nex;
if
(head==null)
printf("list is null");
else
{
s=sizeof (temp);
temp=(struct node*) malloc(s);
pre=head;
next=pre->link;
count=2;
printf("enter the position of the element");
scanf("%d",&f);
printf("enter the data\n");
scanf("%d",&nex->data);
while((count<f) && (next->link!=null))
{
next=next->link;
pre=pre->link;
count=count+1;
}
if((count<f) && (next->link==null))
{
printf("not possible to insert. the list is contains %d
elements",count);
}
else
{
pre->link=nex;
nex->link=next;
}
}
return(0);
}
delmiddle()
{
int s,f,count;
struct node *next,*pre,*nex;
if (head==null)
printf("list is null");
else
{
s=sizeof (temp);
temp=(struct node*) malloc(s);
pre=head;
next=pre->link;
count=2;
printf("enter the position of the element");
scanf("%d",&f);
while((count<f) && (next->link!=null))
{
next=next->link;
pre=pre->link;
count=count+1;
}
if((count<f) && (next->link==null))
{
printf("not possible to insert. the list is contains %d
elements",count);
}
pre->link=next->link;
}
return(0);
}
Ex. No. 4 doubly linked list
Program:
4. Write a C program to implement the Double
Linked List.
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
struct student
{
int
rollno;
struct
student *prev;
struct
student *next;
};
typedef struct student list;
void add(list *head,int rollno)
{
list
*new_elt,*temp=head;
new_elt=(list
*)malloc(sizeof(list));
new_elt->rollno=rollno;
new_elt->next=NULL;
while(temp->next!=NULL)
temp=temp->next;
new_elt->prev=temp;
temp->next=new_elt;
}
void insert(list *head,int rollno,int
position)
{
int
i;
list
*new_elt,*adj_elt,*temp=head;
new_elt=(list
*)malloc(sizeof(list));
new_elt->rollno=rollno;
for(i=1;i<position;i++)
temp=temp->next;
adj_elt=temp->next;
adj_elt->prev=new_elt;
new_elt->next=adj_elt;
new_elt->prev=temp;
temp->next=new_elt;
}
int find(list *head,int rollno)
{
list
*temp=head->next;
int
found=0,i=1;;
while(temp!=NULL)
{
if(temp->rollno==rollno)
{
found=i;
break;
}
i++;
temp=temp->next;
}
return
found;
}
void removeElt(list *head,int rollno)
{
list
*del_elt,*successor,*predecsor,*temp=head->next;
int
i,found;
found=find(head,rollno);
if(found!=0)
{
while(temp->rollno!=rollno)
temp=temp->next;
del_elt=temp;
predecsor=del_elt->prev;
successor=del_elt->next;
predecsor->next=del_elt->next;
successor->prev=del_elt->prev;
free(del_elt);
printf("\nOne
Element is deleted");
}
else
printf("\nElement
has not Found!Cann't perform Deletion!");
}
void print_list(list *head)
{
if(head->next!=NULL)
{
list
*temp=head->next;
printf("\nThe
List:\n");
while(temp!=NULL)
{
printf("%d-->
",temp->rollno);
temp=temp->next;
}
printf("Null");
}
else
printf("\n
The List is Empty");
}
void make_emptylist(list *head)
{
head->prev=NULL;
head->next=NULL;
printf("\nThe
List has been deleted!");
}
void main()
{
list
*head;
int
position,rollno,option;
head=(list
*)malloc(sizeof(list*));
head->prev=NULL;
head->next=NULL;
clrscr();
while(1)
{
printf("\n\n1.Add\n2.Insert
a Item\n3.Remove a Item\n4.Find\n5.Print the
List\n6.Delete the
List\n7.Exit");
printf("\nEnter
your Choice:");
scanf("%d",&option);
switch(option)
{
case
1:
printf("\nEnter
Rollno of the New Element:");
scanf("%d",&rollno);
add(head,rollno);
break;
case
2:
printf("\nEnter
Rollno of Element to be Inserted:");
scanf("%d",&rollno);
printf("\nEnter
Position to insert:");
scanf("%d",&position);
insert(head,rollno,position);
break;
case
3:
printf("\nEnter
the Rollno of the element to Removed:");
scanf("%d",&rollno);
removeElt(head,rollno);
break;
case
4:
printf("Enter
rollno of Item to be found:");
scanf("%d",&rollno);
position=find(head,rollno);
if(position!=0)
printf("\nElement
has been found!Position=%d",position);
else
printf("\nElement
has not found in the List!");
break;
case
5:
print_list(head);
break;
case
6:
make_emptylist(head);
break;
case
7:
exit(0);
}
}
getch(); }
Ex. No: 5 Circular Singly Linked list
Program
:
#include<stdio.h>
#include<conio.h>
int a,s;
struct node
{
int data;
struct node *link;
};
struct node
*head,*first,*previous,*last,*temp;
void main()
{
first=NULL;
head=NULL;
previous=NULL;
clrscr();
do
{
printf("1.creation\n");
printf("2.display\n");
printf("3.insert first\n");
printf("4.insert last\n");
printf("5.insert middle\n");
printf("6.delete first\n");
printf("7.delete last\n");
printf("8.delete
middle\n");
printf("enter
your choice");
scanf("%d",&a);
switch(a)
{
case 1:
create();
display();
break;
case 2:
display();
break;
case 3:
insfirst();
display();
break;
case 4:
inslast();
display();
break;
case 5:
insmiddle();
display();
break;
case 6:
delfirst();
display();
break;
case 7:
dellast();
display();
break;
case 8:
delmiddle();
display();
break;
case 9:
exit(0);
}
printf("\ndo
you want to continue(1/0)\n");
scanf("%d",&s);
}
while(s==1);
}
create()
{
int s;
s=sizeof (struct node);
first=(struct node*) malloc (s);
printf("enter the data");
scanf("%d",&first->data);
first->link=first;
if(head==NULL)
{
head=first;
previous=first;
}
else
{
previous=head;
while(previous->link !=head)
previous=previous->link;
previous->link=first;
previous=first;
}
last=first;
return(0);
}
display()
{
if(head==NULL)
printf("list is null");
else
{
temp=head;
while(temp!=last)
{
printf("%d->",temp->data);
temp=temp->link;
}
if(temp==last)
{
printf("%d
->",temp->data);
temp=temp->link;
}
}
return(0);
}
insfirst()
{
int s;
if (head==NULL)
printf("list is null");
else
{
s=sizeof (temp);
temp=(struct node*) malloc(s);
printf("enter data\n");
scanf("%d",&temp->data);
temp->link=head;
head=temp;
first=temp;
last->link=temp;
}
return(0);
}
delfirst()
{
int s;
if(head==NULL)
printf("list is null");
else
head=head->link;
last->link=head;
if(last->link==head)
head=NULL;
return(0);
}
inslast()
{
int s;
struct node
*last1,*first1;
if (head==NULL)
printf("list
is null");
else
{
s=sizeof (last1);
last1=(struct node*) malloc(s);
printf("enter the data\n");
scanf("%d",&last1->data);
last1->link=NULL;
temp=head;
while(temp->link!=head)
temp=temp->link;
temp->link=last1;
last1->link=head;
last=last1;
}
return(0);
}
dellast()
{
int s,m;
struct node *pre,*next;
if(head==NULL)
printf("list is null");
else
{
if(head==last)
head=last=NULL;
else
{
next=head;
while(next->link!=last)
next=next->link;
next->link=head;
last=next;
}
}
return(0);
}
insmiddle()
{
int s,f,count;
struct node
*next,*pre,*nex;
if (head==NULL)
printf("list
is null");
else
{
s=sizeof (temp);
temp=(struct node*) malloc(s);
pre=head;
next=pre->link;
count=2;
printf("enter the position of the
elemant");
scanf("%d",&f);
printf("enter the data\n");
scanf("%d",&nex->data);
while((count<f) &&
(next->link!=head))
{
next=next->link;
pre=pre->link;
count=count+1;
}
if((count<f) &&
(next->link==head))
{
printf("not possible to insert. the
list is contains %d elements",count);
}
else
{
pre->link=nex;
nex->link=next;
}
}
return(0);
}
delmiddle()
{
int s,f,count;
struct node
*next,*pre,*nex;
if (head==NULL)
printf("list is null");
else
{
s=sizeof (temp);
temp=(struct node*) malloc(s);
pre=head;
next=pre->link;
count=2;
printf("enter the position of the
elemant");
scanf("%d",&f);
while((count<f) &&
(next->link!=head))
{
next=next->link;
pre=pre->link;
count=count+1;
}
if((count<f) &&
(next->link==head))
{
printf("not possible to insert. the
list is contains %d elements",count);
}
pre->link=next->link;
}
return(0);
}
Ex. No: 6 Operations On Binary
Trees
Program :
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node
*lchild;
struct node
*rchild;
}
void creation()
{
printf("\n
Enter the value of the root node \n");
t=(struct
node*)malloc(sizeof(struct node));
scanf("%d",&t->data);
t->lchild=NULL;
t->rchild=NULL;
}
void insert(int n,struct node *a)
{
struct node *x;
if(a->data
!=0)
{
if(a->data>n)
insert(n,a->lchild);
else
insert(n,a->rchild);
}
x=(struct node*) malloc(sizeof(struct node));
x->data=n;
if(a->data>n)
{
if((a->lchild)==NULL)
{
a->lchild=x;
a->lchild->lchild=NULL;
a->lchild->rchild=NULL;
}
}
else
if(a->rchild==NULL)
{
a->rchild=x;
a->rchild->lchild=NULL;
a->rchild->rchild=NULL;
}
}
void
inorder(struct node* a)
{
if(a!=NULL)
{
inorder(a->lchild);
printf("
%10d ",a->data);
inorder(a->rchild);
}
}
void
preorder(struct node *a)
{
if(a!=NULL)
{
printf(" %10d",a->data);
preorder(a->lchild);
preorder(a->rchild);
}
}
void
postorder(struct node *a)
{
if(a!=NULL)
{
postorder(a->lchild);
postorder(a->rchild);
printf(" %10d",a->data);
}
}
void main()
{
int num,c;
clrscr();
creation();
do{
printf("\n 1. Insertion \n2. Inorder \n3. preorder \n4.postorder
");
printf("\n for exit give choice greater than four");
printf(" \nEnter your choice ");
scanf("%d",&c);
switch(c)
{
case 1:printf(" \n Data to be inserted
");
scanf("%d",&num);
insert(num,t);
break;
case 2: inorder(t);
break;
case 3: preorder(t);
break;
case 4: postorder(t);
break;
}
}while(c<5);
}
Ex. No. 7 binary tree operation
Program:
7. Write a C program to implement the binary
tree operations – insert, delete, and search.
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
struct bstree
{
int
data;
struct
bstree *left;
struct
bstree *right;
};
struct bstree *root,*temp;
struct bstree* insertbst(struct bstree
*root,int x)
{
if(
root == NULL)
{
root=malloc(sizeof(struct
bstree));
root->data=x;
root->left=root->right=NULL;
}
else
if(x < root->data)
root->left=insertbst(root->left,x);
else
if(x > root->data)
root->right=insertbst(root->right,x);
return root;
}
struct bstree* findMin(struct bstree *t)
{
if(t==NULL)
return
NULL;
else
if(t->left
!= NULL)
return
findMin(t->left);
else
return
t;
}
struct bstree* findMax(struct bstree *t)
{
if(t==NULL)
return
NULL;
else
if(t->right
!= NULL)
return
findMax(t->right);
else
return
t;
}
int find(struct bstree *temp,int key)
{
if
(temp==NULL)
{
return
NULL;
}
else
{
if(key
< temp->data)
return
find(temp->left,key);
else
if (key > temp->data)
return
find(temp->right,key);
else
return
temp;
}
}
int find_min(struct bstree *temp)
{
if(temp->left
== NULL)
return
temp->data;
else
return
find_min(temp->left);
}
int find_max(struct bstree *temp)
{
if(temp->right
== NULL)
return
temp->data;
else
return
find_max(temp->right);
}
struct bstree* removeElt(struct bstree *t,int
key)
{
struct
bstree *temp;
if
(t==NULL)
printf("\nNode
is not available");
else
if(key < t->data)
t->left=removeElt(t->left,key);
else
if(key > t->data)
t->right=removeElt(t->right,key);
else
if(t->left != NULL && t->right != NULL)
{
temp=findMin(t->right);
t->data=temp->data;
t->right=removeElt(t->right,t->data);
}
else
{
temp=t;
if(t->left==NULL)
t=t->right;
else
if(t->right==NULL)
t=t->left;
free(temp);
}
return
t;
}
void print_list(struct bstree *root)
{
if(root!=NULL)
{
if(root->left
!= NULL)
print_list(root->left);
printf("
%d",root->data);
if(root->right
!= NULL)
print_list(root->right);
}
}
void main()
{
struct
bstree *new_elt;
int option,rollno,info;
root=NULL;
clrscr();
while(1)
{
printf("\n\n1.Insert
a Item\n2.Remove a Item\n3.Find\n4.Find Minimum Value\n5.Find Maximum
Value\n6.Print the List\n7.Exit");
printf("\nEnter
your Choice:");
scanf("%d",&option);
switch(option)
{
case
1:
printf("\nEnter
Rollno of Element to be Inserted:");
scanf("%d",&rollno);
root=insertbst(root,rollno);
break;
case
2:
printf("\nEnter
the Rollno of the element to Removed:");
scanf("%d",&rollno);
root=removeElt(root,rollno);
break;
case
3:
printf("Enter
rollno of Item to be found:");
scanf("%d",&rollno);
info=find(root,rollno);
if(info!=0)
printf("\nElement
has been found! at Position=%d",info);
if(info
== 0)
printf("\nElement
has not found in the List!");
break;
case
4:
if(root
== NULL)
printf("\nTree
is empty");
else
{
info=find_min(root);
printf("\n
The Minimum Value is:%d",info);
}
break;
case
5:
if(root
== NULL)
printf("\nTree
is empty");
else
{
info=find_max(root);
printf("\n
The Maximum Value is:%d",info);
}
break;
case
6:
if(root
== NULL)
printf("\nTree
is empty");
else
print_list(root);
break;
case
7:
exit(0);
}
}
getch();
}
Ex. No. 8 Quick
Sort
Program:
#include <stdio.h>
#include<conio.h>
int n,a[30],pass=1;
void quicksort(int
low, int high)
{
if(low<high)
{
int k,i;
k=partition(low,high);
printf("pass %d\n",pass++);
for(i=1;i<=n;i++)
printf("%6d",a[i]);
printf("\n");
quicksort(low,k-1);
quicksort(k+1,high);
}
}
int partition(int
low,int high)
{
int v,i,t;
v=a[low];
i=low;
do
{
while(a[i]<=v)
i++;
while(a[high]>v)
high--;
if(i<high)
{
t=a[i];
a[i]=a[high];
a[high]=t;
}
}
while(i<high);
a[low]=a[high];
a[high]=v;
return
high;
}
void main()
{
int
low,high,i;
clrscr();
printf("
Enter the array size \n");
scanf("%d",&n);
printf("Enter
the elements \n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
low=1;
high=n;
quicksort(low,high);
getch();
}
Ex. No. 9 Heap
Sort
Program:
#include<conio.h>
#include<stdio.h>
int x[20],n,n1;
void heapsort();
void adjust();
void heapify();
void main()
{
int i;
clrscr();
printf("ENTER THE NO. OF ELEMENTS
:");
scanf("%d",&n);
n1=n;
printf(“ENTER
THE ELEMENTS\n”);
for(i=1;i<=n;i++)
scanf("%d",&x[i]);
clrscr();
printf(" \n ARRAY BEFORE SORT :");
for(i=1;i<=n;i++)
printf("%d\t",x[i]);
heapsort();
getch();
}
void heapsort()
{
int i,t,j;
heapify();
for(i=n;i>=2;i--)
{
t=x[i];
x[i]=x[1];
x[1]=t;
adjust(1,i-1);
printf("\npass %d \n",n-(i-1));
for(j=1;j<=n1;j++)
printf("
%d\t",x[j]);
}
}
void adjust(int i,int n)
{
int j;
int t;
j=2*i;
t=x[i];
while(j<=n)
{
if(j<n && x[j] < x[j+1])
j++;
if(t>=x[j])
break;
x[j/2]=x[j];
j=2*j;
}
x[j/2]=t;
}
void heapify()
{
int i,j;
for(i=n/2;i>=1;i--)
adjust(i,n);
}
Ex. No. 10 Depth first search
Program:
10. Write
a C program to implement the Depth First
Search.
#include<conio.h>
#include<stdio.h>
int graph[10][10];
int visited[10];
void Intilize_Graph(int no_v)
{
int
i,j;
for(i=1;i<=no_v;i++) //Intialize the Graph
{
visited[i]=0;
for(j=1;j<=no_v;j++)
graph[i][j]=0;
}
}
void print_graph(int no_v)
{
int
i,j;
printf("\nThe
Graph(Matrix Representation):\n");
for(i=1;i<=no_v;i++)
printf("\tV%d",i);
for(i=1;i<=no_v;i++)
{
printf("\nV%d",i);
for(j=1;j<=no_v;j++)
{
printf("\t%d",graph[i][j]);
}
}
}
void DFS(int start_v,int no_v)
{
int
i;
visited[start_v]=1;
printf("%d-->",start_v);
for(i=1;i<=no_v;i++)
{
if(i!=start_v
&& visited[i]==0 && graph[start_v][i]==1)
{
DFS(i,no_v);
}
}
}
void main()
{
int
no_v,no_e;
int
s_v,e_v,start_v;
int
i,j;
clrscr();
printf("\nEnter
the No of Vertices in the Graph:");
scanf("%d",&no_v);
printf("Enter
the no of Edges in the Graph:");
scanf("%d",&no_e);
printf("\nEnter
the Adjacent vertices of each edge");
for(i=1;i<=no_e;i++)
{
printf("\nEdge:%d-->Start_V
& End_V:",i);
scanf("%d
%d",&s_v,&e_v);
graph[s_v][e_v]=1;
graph[e_v][s_v]=1;
}
print_graph(no_v);
printf("\nDepth
First Search:\nEnter the Starting Vertex for Searching:");
scanf("%d",&start_v);
printf("Depth
First Search Tree:\n");
DFS(start_v,no_v);
getch();
}
Ex. No. 11 shortest path of the graph
Program:
11. Write a C program to find the
shortest path of a graph.
#include<conio.h>
#include<stdio.h>
int start_V[20],end_V[20],weight[20];
int no_v,no_e;
struct VertexInfo
{
int
known;
int
distance;
int
prev_vertex;
}vertex[20];
void Intilize_VertexInfo()
{
int
i,j;
for(i=1;i<=no_v;i++) //Intialize the Graph
{
vertex[i].known=0;
vertex[i].distance=1000;
vertex[i].prev_vertex=0;
}
}
void print_Path(int e_v)
{
int
temp=e_v;
if(vertex[e_v].prev_vertex==0)
printf("\nNo
path from Source to Given Destination!");
else
{
printf("\nShortest
Path:%d ",e_v);
while(vertex[e_v].prev_vertex!=0)
{
printf("%d
",vertex[e_v].prev_vertex);
e_v=vertex[e_v].prev_vertex;
}
printf("\nThe
Distance is:%d",vertex[temp].distance);
}
}
void main()
{
int
s_v,e_v,start_v;
int
i,j;
int
v,w,index;
int
min,qw,next_v;
char
ch;
clrscr();
printf("\nEnter
the No of Vertices in the Graph:");
scanf("%d",&no_v);
printf("Enter
the no of Edges in the Graph:");
scanf("%d",&no_e);
printf("\nEnter
the Adjacent vertices of each edge");
for(i=1;i<=no_e;i++)
{
printf("\nEdge:%d-->Start_V
& End_V & Weight:",i);
scanf("%d
%d %d",&start_V[i],&end_V[i],&weight[i]);
}
Intilize_VertexInfo();
printf("\nEnter
Vertices to find the Shortest Path:");
scanf("%d
%d",&s_v,&e_v);
vertex[s_v].distance=0;
next_v=s_v;
while(next_v)
{
v=next_v;
vertex[v].known=1;
for(i=1;i<=no_e;i++)
{
if(start_V[i]==v)
{
w=end_V[i];
if(vertex[v].distance+weight[i]
< vertex[w].distance)
{
vertex[w].distance=vertex[v].distance+weight[i];
vertex[w].prev_vertex=v;
}
}
}
min=1000;
for(j=1;j<=no_v;j++)
{
if(vertex[j].known==0
&& min>vertex[j].distance)
{
min=vertex[j].distance;
next_v=j;
}
}
if(min==1000)
next_v=0;
}
print_Path(e_v);
while(1)
{
printf("\nDo
you want shortest to one more destination:");
fflush(stdin);
ch=getchar();
if(ch=='y'
| ch=='Y')
{
printf("\nEnter
the Destination Vertex:");
scanf("%d",&e_v);
print_Path(e_v);
}
else
break;
}
getch();
}
K.L.N
COLLEGE OF ENGINEERING, POTTAPALAYAM
DEPARTMENT
OF COMPUTER APPLICATIONS (MCA)
DATA STRUCTURES LAB(MC1606)
I
SEMESTER – (June 2006 – November 2006)
DATA
STRUCTURES LAB CYCLE PROGRAMS
- Represent the given sparse matrix using one-dimensional array and linked list.
- Create a Stack and do the following operations using arrays and linked lists
(i)Push (ii) Pop
(iii) Peep
- Create a Queue and do the following operations using arrays and linked lists
(i)Add (ii) Remove
- Implement the operations on singly linked list, doubly linked list and circular linked list.
- Create a binary search tree and do the following traversals
(i)In-order (ii) Pre order (iii) Post order
- Implement the following operations on a binary search tree.
(i)
Insert a node (ii) Delete a node
- Sort the given list of numbers using heap and quick sort.
- Perform the following operations in a given graph
(i)
Depth first search (ii) Breadth first
search
- Find the shortest path in a given graph using Dijkstra algorithm
K.L.N
COLLEGE OF ENGINEERING, POTTAPALAYAM
DEPARTMENT
OF COMPUTER APPLICATIONS (MCA)
PROGRAMMING
LAB (MC1607)
I
SEMESTER – (June 2006 – November 2006)
C
LAB CYCLE PROGRAMS
1. Display the following:
(i) Floyd’s triangle (ii) Pascal
Triangle
2. Generate the following series
of numbers:
Armstrong numbers between 1 to 100
Prime numbers between 1 to 50
Fibonacci series up to N numbers
3. Manipulate the strings with
following operations.
(i) Concatenating two strings (ii)
Reversing the string (iii) Finding the
sub string
(iv) Replacing a string (v) Finding length of the string
4. Find the summation of the
following series:
(i) Sine (ii) Cosine (iii) Exponential
5. Create the sales report for M
sales person and N products using two-dimensional array.
6. Simulate following Banking
operations using functions.
(i) Deposit (ii) Withdrawal (iii) Balance Enquiry
7. Implement using recursion
I, Find the solution of Towers of Hanoi problem using recursion.
II, Fibonacci number generation.
III, Factorial
8. Generate Student mark sheets
using structures.
9. Create a collection of books
using arrays of structures and do the following:
(i) Search a book with title and
author name (ii) Sorts the books on title.
No comments:
Post a Comment