DATA STRUCTURES

LAB MANUAL
 Lab Manual
DataStructures

1. Write a program that uses functions to perform the following operations on singly linked list.:
i) Creation ii) Insertion iii) Deletioniv) Traversal

2. Write a program that uses functions to perform the following operations on doubly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

3. Write a program that uses functions to perform the following operations on circular linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

4. Write a program that implement stack (its operations) using

i) Arrays ii) Pointers

5. Write a program that implement Queue (its operations) using

i) Arrays ii) Pointers

6. Write a program that implements the following sorting methods to sort a given list of integers in
ascending order
i) Bubble sort ii) Selection sort iii) Insertion sort

7. Write a program that use both recursive and non recursive functions to perform the following
searching operations for a Key value in a given list of integers:
i) Linear search ii) Binary search

8. Write a program to implement the tree traversal methods.

9. Write a program to implement the graph traversal methods.

10. . Implement a Pattern matching algorithms using Boyer- Moore, Knuth-Morris-Pratt

 PROGRAM-1

Aim: Write a program that uses functions to perform the following operations on singly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

SourceCode:

# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
struct slinklist
{
int data;
struct slinklist *next;
};
typedef struct slinklist node;
node *start = NULL;
int menu()
{
int ch;
clrscr();
printf("\n [Link] a list ");
printf("\n ");
printf("\n [Link] a node at beginning
"); printf("\n [Link] a node at end");
printf("\n [Link] a node at middle");
printf("\n ");
printf("\n [Link] a node from
beginning"); printf("\n [Link] a node
from Last"); printf("\n [Link] a node from
Middle"); printf("\n ");
printf("\n [Link] the list (Left to Right)");
printf("\n [Link] the list (Right to Left)");
printf("\n ");
printf("\n 10. Count nodes ");
printf("\n 11. Exit ");
printf("\n\n Enter your choice: ");
scanf("%d",&ch);
return ch;
}

node* getnode()
{
node * newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter data: ");
scanf("%d", &newnode -> data);
newnode -> next = NULL;
return newnode;
}
int countnode(node *ptr)
{
int count=0;
while(ptr !=
NULL)
{
count++;
ptr = ptr -> next;
}
return (count); }
void createlist(int
n)
{
int i;
node *newnode;
node *temp;
for(i = 0; i < n; i++)
{
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}
}

void traverse()
{
node *temp;
temp = start;
printf("\n The contents of List (Left to Right): \n");
if(start == NULL)
{
printf("\n Empty
List"); return;
}
else
{

while(temp != NULL)
{
printf("%d-->", temp -> data);
temp = temp -> next;
}
}
printf(" X ");
}
void rev_traverse(node *start)
{
if(start == NULL)
{
return;
}
else
{
rev_traverse(start -> next);
printf("%d -->", start -> data);
}
}

void insert_at_beg()
{
node *newnode;
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start;
start = newnode;
}
}

void insert_at_end()
{
node *newnode,
*temp; newnode =
getnode(); if(start ==
NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}

void insert_at_mid()
{
node *newnode, *temp, *prev;
int pos, nodectr, ctr = 1;
newnode = getnode(); printf("\
n Enter the position: ");
scanf("%d", &pos);
nodectr = countnode(start);

if(pos > 1 && pos < nodectr)

{
 temp = prev = start;
while(ctr < pos)
{
prev = temp;
temp = temp -> next; ctr+
+;
}
prev -> next = newnode;
newnode -> next = temp;
}
else
printf("position %d is not a middle position", pos);
}

void delete_at_beg()
{
node *temp;
if(start == NULL)
{
printf("\n No nodes are exist..");
return ;
}
else
{
temp = start;
start = temp -> next;
free(temp);
printf("\n Node deleted ");
}
}

void delete_at_last()
{
node *temp,
*prev; if(start ==
NULL)
{
return printf("\n Empty List..");
;
}
else
{
temp = start;
prev = start;
while(temp -> next != NULL)
{
prev = temp;
temp = temp -> next;
}
prev -> next = NULL;
free(temp);
printf("\n Node deleted ");
}
}

void delete_at_mid()
{
int ctr = 1, pos, nodectr;
node *temp, *prev;
if(start == NULL)
{
printf("\n Empty List..");

return ;
}
else
{
printf("\n Enter position of node to delete: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > nodectr)
{
printf("\nThisnode doesnot exist");
}
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
while(ctr < pos)
{
prev = temp;
temp = temp -> next;
ctr ++;
}
prev -> next = temp -> next;
free(temp);
printf("\n Node deleted..");
}
else
{
printf("\n Invalid position..");
getch();
}
}
}

void main(void)
{
int ch,
n;
clrscr();
while(1)
{
ch = menu();
switch(ch)
{
case 1:
if(start == NULL)
{
printf("\n Number of nodes you want to create: ");
scanf("%d", &n);
createlist(n);
 printf("\n List created..");
}
else
printf("\n List is already created..");
break;
case
2:
insert_at_beg();
break;
case
3: insert_at_end();
break;

case insert_at_mid();
4: break;

case
5: delete_at_beg();
break;
case delete_at_last();
6: break;

delete_at_mid();
case break;
7:
traverse();
break;
case
8: printf("\n The contents of List (Right to Left): \n");
rev_traverse(start);
printf(" X
case "); break;
9:
case 10:
printf("\n No of nodes : %d ", countnode(start));
break;
case 11 :
exit(0);
}
getch();
}
}
OUTPUT :
 PROGRAM-2

Aim: Write a program that uses functions to perform the following operations on doubly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

SourceCode:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct dlinklist
{
struct dlinklist *left; int
data;
struct dlinklist *right;
};
typedef struct dlinklist node; node
*start = NULL;

node* getnode()
{
node * newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter data: ");
scanf("%d", &newnode -> data);
newnode -> left = NULL;
newnode -> right = NULL;
return newnode;
}
int countnode(node *start)
{
if(start == NULL)
return 0;
else
return 1 + countnode(start -> right);
}
int menu()
{
int ch;
clrscr();
printf("\n [Link]");
printf("\n ");
printf("\n 2. Insert a node at beginning
"); printf("\n 3. Insert a node at end");
printf("\n 4. Insert a node at middle");
printf("\n ");
printf("\n 5. Delete a node from beginning");
printf("\n 6. Delete a node from Last");
printf("\n 7. Delete a node from Middle");
printf("\n ");
printf("\n 8. Traverse the list from Left to Right ");
printf("\n 9. Traverse the list from Right to Left ");
printf("\n ");
printf("\n [Link] the Number of nodes in the list");
printf("\n [Link]");
printf("\n\n Enter your choice: ");
scanf("%d", &ch);
return ch;
}
void createlist(int n)
{
int i;
node *newnode;
node *temp;
for(i = 0; i < n; i++)
{
newnode = getnode();
if(start == NULL)
start = newnode;
else
{
temp = start;
while(temp -> right)
temp = temp -> right;
temp -> right = newnode;
newnode -> left = temp;
}
}
}

void traverse_left_to_right()
{
node *temp;
temp = start;
printf("\n The contents of List: ");
if(start == NULL )
printf("\n Empty
List"); else
{
while(temp != NULL)
{
printf("\t %d ", temp -> data);
temp = temp -> right;
}
}
}
void traverse_right_to_left()
{
node *temp;
temp = start;
printf("\n The contents of List: ");
if(start == NULL)
printf("\n Empty
List"); else
{
while(temp -> right != NULL)
temp = temp -> right;
}
while(temp != NULL)
{
printf("\t%d", temp -> data);
temp = temp -> left;
}
}
void dll_insert_beg()
{
node *newnode;
newnode = getnode();
if(start == NULL)
start = newnode;
else
{
newnode -> right = start;
start -> left = newnode;
start = newnode;
}
}
void dll_insert_end()
{
node *newnode,
*temp; newnode =
getnode(); if(start ==
NULL)
start = newnode;
else
{
temp = start;
while(temp -> right != NULL)
temp = temp -> right;
temp -> right = newnode;
newnode -> left = temp;
}
}
void dll_insert_mid()
{
node *newnode,*temp;
int pos, nodectr, ctr = 1;
newnode = getnode();
printf("\n Enter the position: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos - nodectr >= 2)
{
printf("\n Position is out of range..");
return;
}
if(pos > 1 && pos < nodectr)
{
temp = start;
while(ctr < pos - 1)
{
temp = temp -> right;
ctr++;
}
newnode -> left = temp;
newnode -> right = temp -> right;
temp -> right -> left = newnode;
temp -> right = newnode;
}
else
printf("position %d of list is not a middle position ", pos);
}
void dll_delete_beg()
{
node *temp;
if(start == NULL)
{
printf("\n Empty list");
getch();
return ;
}
else
{
temp = start;
start = start -> right;
start -> left = NULL;
free(temp);
}
}
void dll_delete_last()
{
node *temp;
if(start == NULL)
{
printf("\n Empty list");
getch();
return ;
}
else
{
temp = start;
while(temp -> right != NULL)
temp = temp -> right;
temp -> left -> right = NULL;
free(temp);
temp = NULL;
}
}
void dll_delete_mid()
{
int i = 0, pos, nodectr;
node *temp;
if(start == NULL)
{
printf("\n Empty List");
getch();
return;
}
else
{
printf("\n Enter the position of the node to delete: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > nodectr)
{
printf("\nthis node does not exist");
getch();
return;
}
if(pos > 1 && pos < nodectr)
{
temp = start;
i= 1;
while(i < pos)
{
temp = temp -> right;
i++;
}
temp -> right -> left = temp -> left;
temp -> left -> right = temp -> right;
free(temp);
printf("\n node deleted..");
}
else
{
printf("\n It is not a middle position..");
getch();
}
}
}
void main(void)
{
int ch,
n;
clrscr();
while(1)
{
ch = menu();
switch( ch)
{
case 1 :
printf("\n Enter Number of nodes to create: ");
scanf("%d", &n);
createlist(n);

printf("\n List created..");

break;
case 2 :
dll_insert_beg();
break;
case 3 :
dll_insert_end();
break;
case 4 :
dll_insert_mid();
break;
case 5 :
dll_delete_beg();
break;
case 6 :
dll_delete_last();
break;
case 7 :
dll_delete_mid();
break;
case 8 :
traverse_left_to_right();
break;
case 9 :
traverse_right_to_left();
break;
case 10 :
printf("\n Number of nodes: %d", countnode(start));
break;
case 11:
exit(0);
}
getch();
}
}

OUTPUT :
 PROGRAM-3

Aim: Write a program that uses functions to perform the following operations on circular linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

Sourcecode:

# include <stdio.h> #
include <conio.h> #
include <stdlib.h>
struct cslinklist
{
int data;
struct cslinklist *next;
};
typedef struct cslinklist node; node
*start = NULL;
int nodectr; node*
getnode()
{
node * newnode;
newnode = (node *) malloc(sizeof(node));
printf("\n Enter data: ");
scanf("%d", &newnode -> data);
newnode -> next = NULL;
return newnode;
}

int menu()
{
int ch;
clrscr();
printf("\n 1. Create a list "); printf("\n\n
");
printf("\n 2. Insert a node at beginning ");
printf("\n 3. Insert a node at end");
printf("\n 4. Insert a node at middle");
printf("\n\n ");
printf("\n 5. Delete a node from beginning");
printf("\n 6. Delete a node from Last");
printf("\n 7. Delete a node from Middle");
printf("\n\n "); printf("\
n 8. Display the list");
printf("\n 9. Exit");
printf("\n\n ");
printf("\n Enter your choice: ");
scanf("%d", &ch);
return ch;
}
void createlist(int n)
{
int i;
node *newnode;
node *temp;
nodectr = n;
for(i = 0; i < n ; i++)
{
newnode = getnode();
if(start == NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}
newnode ->next = start; /* last node is pointing to starting node */
}
void display()
{
node *temp;
temp = start;
printf("\n The contents of List (Left to Right): ");
if(start == NULL )
printf("\n Empty List");
else
{
do
{
printf("\t %d ", temp -> data);
temp = temp -> next;
} while(temp != start);
printf(" X ");
}
}

void cll_insert_beg()
{
node *newnode, *last;
newnode = getnode();
if(start == NULL)
{
start = newnode;
newnode -> next = start;
}
else
{
last = start;
while(last -> next != start)
last= last -> next;
newnode -> next = start;
start = newnode;
last -> next = start;
}
printf("\n Node inserted at beginning..");
nodectr++;
}
void cll_insert_end()
{
node *newnode,
*temp; newnode =
getnode(); if(start ==
NULL )
{
start = newnode;
newnode -> next = start;
}
else
{
temp = start;
while(temp -> next != start)
temp = temp -> next;
temp -> next = newnode;
newnode -> next = start;
}
printf("\n Node inserted at end..");
nodectr++;
}
void cll_insert_mid()
{
node *newnode, *temp, *prev;
int i, pos ;
newnode = getnode(); printf("\
n Enter the position: ");
scanf("%d", &pos);
if(pos > 1 && pos < nodectr)
{
temp = start;
prev = temp;
i= 1;
while(i < pos)
{
prev = temp;
temp = temp -> next;
i++;
}
prev -> next = newnode;
newnode -> next = temp;

nodectr++;
printf("\n Node inserted at middle..");
}
else
{
printf("position %d of list is not a middle position ", pos);
}
}
void cll_delete_beg()
{
node *temp,
*last; if(start ==
NULL)
{
printf("\n No nodes exist..");
getch();
return ;
}
else
{
last = temp = start;
while(last -> next != start)
last= last -> next;
start = start -> next;
last -> next = start;
free(temp);
nodectr--;
printf("\n Node deleted..");
if(nodectr == 0)
start = NULL;
}
}
void cll_delete_last()
{
node *temp,*prev;
if(start == NULL)
{
printf("\n No nodes exist..");
getch();
return ;
}
else
{
temp = start;
prev = start;
while(temp -> next != start)
{
prev = temp;
temp = temp -> next;
}
prev -> next = start;
free(temp);
nodectr--;
if(nodectr == 0)
start = NULL;
printf("\n Node deleted..");
}
}

void cll_delete_mid()
{
int i = 0, pos;
node *temp,
*prev; if(start ==
NULL)
{
printf("\n No nodes exist..");
getch();
return ;
}
else
{
printf("\n Which node to delete: ");
scanf("%d", &pos);
if(pos > nodectr)
{
printf("\nThis node does not exist");
getch();
return;
}
if(pos > 1 && pos < nodectr)
{
temp=start;
prev = start;
i= 0;
while(i < pos - 1)
{
prev = temp;
temp = temp -> next ;
i++;
}
prev -> next = temp -> next;
free(temp);
nodectr--;
printf("\n Node Deleted..");
}
else
{
printf("\n It is not a middle position..");
getch();
}
}
}
void main(void)
{
int result;
int ch, n;
clrscr();
while(1)
{
ch = menu();
switch(ch)
{
case 1 :
if(start == NULL)
{
printf("\n Enter Number of nodes to create: ");
scanf("%d", &n);
createlist(n); printf("\
nList created..");
}

else
printf("\n List is already Exist..");
break;
case 2 :
cll_insert_beg();
break;
case 3 :
cll_insert_end();
break;
case 4 :
cll_insert_mid();
break;
case 5 :
cll_delete_beg();
break;
case 6 :
cll_delete_last();
break;
case 7 :
cll_delete_mid();
break;
case 8 :
display();
break;
case 9 :
exit(0);
}
getch();
}
}

Output :
 PROGRAM-4

Aim: Write a program that implement stack (its operations) using

i) Arrays ii) Pointers

Source code to implement Stack using linked list :

# include <stdio.h> #
include <conio.h> #
include <stdlib.h>
struct stack
{
int data;
struct stack *next;
};
void push(); void
pop(); void
display();
typedef struct stack node;
node *start=NULL;
node *top = NULL;
node* getnode()
{
node *temp;
temp=(node *) malloc( sizeof(node)) ;
printf("\n Enter data ");
scanf("%d", &temp -> data);
temp -> next = NULL;
return temp;
}
void push(node *newnode)
{
node *temp;
if( newnode == NULL )
{
printf("\n Stack Overflow..");
return;
if(start == NULL)
{
start = newnode; top
= newnode;
}
else
{
temp = start;
while( temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode; top
= newnode;
}
printf("\n\n\t Data pushed into stack");
}
void pop()
{
node *temp;
if(top ==
NULL)
{
printf("\n\n\t Stack underflow");
return;
}
temp = start;
if( start -> next == NULL)
{
printf("\n\n\t Popped element is %d ", top -> data);
start = NULL;
free(top);
top =
NULL;
}
else
{
while(temp -> next != top)
{
temp = temp -> next;
}
temp -> next = NULL;
printf("\n\n\t Popped element is %d ", top -> data);
free(top);
top = temp;
}
}
void display()
{
node *temp;
if(top ==
NULL)
{
printf("\n\n\t\t Stack is empty ");
}
else
{
temp = start;
printf("\n\n\n\t\t Elements in the stack: \n");
printf("%5d ", temp -> data);
while(temp != top)
{
temp = temp -> next;
printf("%5d ", temp -> data);
}
}
}

char menu()
{
char ch;
clrscr();
printf("\n \tStack operations using pointers.. ");
printf("\n -----------**********-------------\n");
printf("\n 1. Push ");
printf("\n 2. Pop ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Enter your choice: ");
ch = getche();
return ch;
}
void main()
{
char ch;
node *newnode;
do
{
ch = menu();
switch(ch)
{
case '1' :
newnode = getnode();
push(newnode);
break;
case '2' :
pop();
break;
case '3' :
display();
break;
case '4':
return;
}
getch();
} while( ch != '4' );
}
OUTPUT :
 PROGRAM-5

Aim: Write a program that implement Queue (its operations) using

i) Arrays ii) Pointers

Source code (Using array ) :

# include <conio.h> #
define MAX 6
int Q[MAX]; int
front, rear;
void insertQ()
{
int data;
if(rear == MAX)
{
printf("\n Linear Queue is full");
return;
}
else
{
printf("\n Enter data: ");
scanf("%d", &data);
Q[rear] = data;
rear++;
printf("\n Data Inserted in the Queue ");
}
}
void deleteQ()
{
if(rear == front)
{
printf("\n\n Queue is Empty..");
return;
}
else
{
printf("\n Deleted element from Queue is %d", Q[front]); front++;
}
}
void displayQ()
{
int i;
if(front == rear)
{
printf("\n\n\t Queue is Empty");
return;
}
else
{
printf("\n Elements in Queue are: ");
for(i = front; i < rear; i++)
{
printf("%d\t", Q[i]);
}
}
}
int menu()
{
int ch;
clrscr();
printf("\n \tQueue operations using
ARRAY.."); printf("\n -----------**********
---------------------------------------------------\n");
printf("\n 1. Insert ");
printf("\n 2. Delete ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Enter your choice: ");
scanf("%d", &ch);
return ch;
}
void main()
{
int ch;
do
{
ch = menu();
switch(ch)
{
case 1:
insertQ();
break;
case 2:
deleteQ();
break;
case 3:
displayQ();
break;
case 4:
return;
}
getch();
} while(1);
}
Output :
 ii) Source code to implement Queue operations using pointer

# include <stdlib.h>
# include <conio.h>
struct queue
{
int data;
struct queue *next;
};
typedef struct queue node;
node *front = NULL;
node *rear = NULL;
node* getnode()
{
node *temp;
temp = (node *) malloc(sizeof(node)) ;
printf("\n Enter data ");
scanf("%d", &temp -> data);
temp -> next = NULL;
return temp;
}
void insertQ()
{
node *newnode;
newnode= getnode();
if(newnode== NULL)
{
printf("\n Queue Full");
return;
}
if(front == NULL)
{
front = newnode;
rear=newnode;
}
else
{
rear -> next = newnode;
rear=newnode;
}
printf("\n\n\t Data Inserted into the Queue..");
}
void deleteQ()
{
node *temp;
if(front ==
NULL)
{
printf("\n\n\t Empty Queue..");
return;
}
temp = front;
front = front -> next;
printf("\n\n\t Deleted element from queue is %d ", temp -> data);
free(temp);
}
void displayQ()
{
node *temp;
if(front ==
NULL)
{
printf("\n\n\t\t Empty Queue ");
}
else
{
temp = front;
printf("\n\n\n\t\t Elements in the Queue are: ");
while(temp != NULL)
{
printf("%5d ", temp -> data);
temp = temp -> next;
}
}
}
char menu()
{
char ch;
clrscr();
printf("\n \t..Queue operations using pointers.. ");
printf("\n\t -----------**********-------------\n");
printf("\n 1. Insert ");
printf("\n 2. Delete ");
printf("\n 3. Display");
printf("\n 4. Quit ");
printf("\n Enter your choice: ");
ch = getche();
return ch;
}
void main()
{
char ch;
do
{
ch = menu();
switch(ch)
{
case '1' :
insertQ();
break;
case '2' :
deleteQ();
break;
case '3' :
displayQ();
break;
case '4':
return;
}
getch();
} while(ch != '4' }
 PROGRAM-6

Aim: Write a program that implements the following sorting methods to sort a given list of integers in
ascending order
i) Bubble sort ii) Selection sort iii) Insertion sort

Source code:

i) Bubble sort

#include<std
io.h>
#include<co
nio.h>
#include<all
oc.h>

void bubblesort(int
*,int); void main()
{
int
*a,n,i;
clrscr()
;
printf("\n enter the size of the
array \n"); scanf("%d",&n);
a=(int *)calloc(n,sizeof(int));
printf("\n enter the elements
\n"); for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n elements before sorting\
n"); a for(i=0;i<n;i++)
printf("\t
%d",a[i]);
bubblesort(
a,n);
printf("\n sorted array elements \n");
for(i=0;i<n;i++)
printf("\t
%d",a[i]); getch();
}
void bubblesort(int *a,int n)
{
int i,j,t;
for(i=0;i<
n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[
 j+1];
a[j+1]
=t;
}
}
}
}

OUTPUT:
 ii) Selection sort

#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],i,j,temp,n;
clrscr();
printf("\n enter the size of an array: \n");
scanf("%d",&n);
printf("enter array elementas \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n selection sort: \n\n");
printf("array elements before sorting: \n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);
for(i=0;i<=n-2;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("\n array after sorting: \n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);
getch();
}
Output
Insertion sort :

#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],i,j,k,temp,n;
clrscr();
printf("enter the size of an array: \n");
scanf("%d",&n);
printf("enter the elements in to an array: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n array before sorting \n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);
printf("\n\n insertion sort \n");
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[j]>a[i])
{
temp=a[j];
a[j]=a[i];
for(k=i;k>j;k--)
a[k]=a[k-1];
a[k+1]=temp;
}
}
}
printf("\n array after sorting: \n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);
getch();
}

OUTPUT :
 PROGRAM-7

AIM : Write a program that use both recursive and non recursive functions to perform the following
searching operations for a Key value in a given list of integers:
i) Linear search ii) Binary search
i) Linear Search

#include<stdio.h>
#include<conio.h>
void linear(int[],int,int);

void main()
{
int i,n,key; int
a[50];
clrscr();
printf("\n how many elements you want to insert into an array= \n");
scanf("%d",&n);
printf("\n\n enter the array elements= \n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("the elements in the array=\n");
for(i=0;i<n;i++)
{
printf("%5d",a[i]);
}
printf("\n which elements you want to search=");
scanf("%d",&key);
linear(a,n,key);
getch();
}

void linear(int a[],int n,int key)

{
int flag=1,i;
for(i=0;i<n;i++)
{
if(a[i]==key)
{
printf("\n search is successfull \n");
printf("elements %d found at location %d \n",key,i+1); flag=0;
break;
}
}
if(flag)
{
printf("\n unsuccessful search %d not found ",key);
}
getch();
}
Output :
 ii) Binary Search

#include<stdio.h>
#include<conio.h>
void binary(int [],int,int);
void main()
{
int a[50];
int i,n,key;
clrscr();
printf("\n enter how many elements you want to insert=\n");
scanf("%d",&n);
printf("\n enter the elements in the ascending order= \n"); for(i=0;i<n;i+
+)
scanf("%d",&a[i]);
printf("the array elements are = \n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
printf("\n which elements you want to search=");
scanf("%d",&key);
binary(a,n,key);
getch();
}

void binary(int a[],int n,int key)

{
int low,high,mid;
int flag=1;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(key<a[mid])

high=mid-1;
else
if(key>a[mid])
low=mid+1;
else
if(key==a[mid])
{
printf("\n search successful \n");
printf("\n elements %d found at location %d \
n",key,mid+1); flag=0;
break;
}
}
if(flag)
printf("\n unsuccessful search %d not found",key);
}
OUTPUT :
 PROGRAM-8

AIM : Write a program to implement the tree traversal methods.

Source code:

# include <stdio.h> #
include <stdlib.h>
struct tree
{
struct tree* lchild;
char data[10];
struct tree*
rchild;
};

typedef struct tree node;

node *Q[50];
int node_ctr;

node* getnode()
{
node *temp ;
temp = (node*)
malloc(sizeof(node)); printf("\n Enter
Data: "); fflush(stdin);
scanf("%s",temp->data);
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}

void create_binarytree(node *root)

{
char option;
node_ctr = 1;
if( root != NULL )
{
printf("\n Node %s has Left SubTree(Y/N)",root->data); fflush(stdin);
scanf("%c",&option);
if( option=='Y' || option == 'y')
{
root->lchild = getnode(); node_ctr+
+; create_binarytree(root-
>lchild);
}
else
{
root->lchild = NULL;
create_binarytree(root->lchild);
}
printf("\n Node %s has Right SubTree(Y/N) ",root->data);
fflush(stdin);
 scanf("%c",&option);
if( option=='Y' || option == 'y')
{
root->rchild = getnode();
node_ctr++;
create_binarytree(root->rchild);
}
else
{
root->rchild = NULL;
create_binarytree(root->rchild);
}
}
}

void make_Queue(node *root,int parent)

{
if(root != NULL)
{
node_ctr++;
Q[parent] = root;
make_Queue(root->lchild,parent*2+1);
make_Queue(root->rchild,parent*2+2);
}
}

void inorder(node *root)

{
if(root != NULL)
{
inorder(root->lchild);
printf("%3s",root->data);
inorder(root->rchild);
}
}

void preorder(node *root)

{
if( root != NULL )
{
printf("%3s",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}

void postorder(node *root)

{
if( root != NULL )
{
postorder(root->lchild);
postorder(root->rchild);
printf("%3s", root->data);
}
}

void level_order(node *Q[],int ctr)

{
int i;
for( i = 0; i < ctr ; i++)
{
if( Q[i] != NULL )
printf("%5s",Q[i]->data);
}
}

int menu()
{
int ch;
clrscr();
printf("\n 1. Create Binary Tree ");
printf("\n 2. Inorder Traversal ");
printf("\n 3. Preorder Traversal ");
printf("\n 4. Postorder Traversal ");
printf("\n 5. Level Order Traversal");
printf("\n 6. Quit ");
printf("\n Enter Your choice: ");
scanf("%d", &ch);
return ch;
}
void main()
{
int i,ch;
node *root = NULL;
do
{
ch = menu();
switch( ch)
{
case 1 :
if( root == NULL )
{
root = getnode();
create_binarytree(root);
}
else
{
printf("\n Tree is already Created ..");
}

case break;
2:
printf("\n Inorder Traversal: ");
inorder(root);
break;
 case
3: printf("\n Preorder Traversal: ");
preorder(root);
break;

case
4: printf("\n Postorder Traversal: ");
postorder(root);
break;
case 5: printf("\n Level Order Traversal ..");
make_Queue(root,0);
level_order(Q,node_ctr);
break;
case 6 exit(0);
:

getch();
}while(1);
}

OUTPUT :
 PROGRAM-9

AIM : Write a program to implement the graph traversal methods (Breadth First
Search)

#include<stdio.h>

// creating queue data structure using arrays

int queue[10];

// defining pointers of the queue to perform pop and push

int front=0,back=0;

// defining push operation on the queue

void push(int var)
{
queue[back] = var;
back++;
}

// defining pop operation on queue

void pop()
{
queue[front] = 0;
front++;
}

// creating a visited array to keep the track of visited nodes

int visited[7] = {0};

int main()
{
int v,n,i,j;
// adjacenty matrix representing graph
int graph[10][10];
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter graph data in matrix form: \n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &graph[i][j]);

// adding a starting node in the list

printf("Enter the starting vertex: ");
scanf("%d", &v);
push(v);
while(front != back)
{
int current = queue[front];
 // printing current element
printf("%d ", current);

// popping the front element from the queue

pop();

for(int i=0;i < 6;i++)

{
// adding non-visited connected nodes of the current node to the queue
if((graph[current-1][i] == 1) && (visited[i] == 0))
{
visited[i] = 1; // marking visisted
push(i+1);
}
}
}
return 0;
}

OUTPUT :

Enter the number of vertices: 6

Enter graph data in matrix form:
011000
101000
110110
001000
001001
000010
Enter the starting vertex: 2
2 132456
ii)Write a program to implement the graph traversal methods (Depth First Search)

#include <stdio.h>
int a[20][20], visited[20], n;
void dfs(int v)
{
int i;
visited[v] = 1;
for (i = 1; i <= n; i++)
{
if (a[v][i] && !visited[i])
{
printf("\n %d->%d", v, i);
dfs(i);
}
}
}

int main( )
{
int i, j,v, count = 0;
printf("\n Enter number of vertices:");
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
visited[i] = 0;
for (j = 1; j <= n; j++)
a[i][j] = 0;
}
printf("\n Enter the adjacency matrix:\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
printf("Enter the starting vertex: ");
scanf("%d", &v);
dfs(v);
return 0;
}
 OUTPUT :

Enter number of vertices:6

Enter the adjacency matrix:
011000
101000
110110
001000
001001
000010
Enter the starting vertex: 2
2->1
1->3
3->4
3->5
5->6
 PROGRAM-10

AIM : Write a program to Implement a Pattern matching algorithms using Boyer-

Moore

#include <stdio.h>
#include <string.h>

int max(int a, int b)

{
if(a > b)
return a;
else
return b;
}
int boyermorre(char p[],char t[])
{
int bctable[128],i,j,k;
int n = strlen(t);
int m = strlen(p);
for(j=0; j<128; j++)
{
bctable[j]=m;
}
for(j=0; j<m; j++)
{
k=(int)p[j];
bctable[k]=m-j-1;
}
i=m-1;
while(i < n)
{
j=m-1;
while(j >= 0 && p[j] == t[i])
{
i--;
j--;
}
if(j == -1)
return i+1;
i = i + max((int)bctable[t[i]],m-j);
}
return 0;
}

int main() {
char t[]="kiss*miss*in*mississippi";
char p[]="missi";
 int i;
i=boyermorre(p,t);
if(i)
printf("pattern is present in text at position
%d",i+1);
else
printf("pattern is not present in text");
return 0;
}

OUTPUT :

pattern is present in text at position 14

[Link] a program to Implement a Pattern matching algorithms using Knuth-Morris-
Pratt

#include <stdio.h>
#include <string.h>

int lps[100];
void longestPrefixSuffix(char p[])
{
int i=1,j=0;
int m = strlen(p);
lps[0] = 0;
while(i < m)
{
if( p[j] == p[i])
{
lps[i]=j+1;
i++;
j++;
}
else if(j>0)
j = lps[j-1];
else
{
lps[i]=0;
i++;
}
}
}

int kmp (char p[],char t[])

{
int n,m;
int i=0,j=0;
n = strlen(t);
m = strlen(p);
longestPrefixSuffix(p);
while( i < n )
{
if ( p[j] == t[i])
{
if (j == m-1 )
return i-j;
i++;
j++;
}
else if(j>0)
j = lps[j-1];
else
 i++;
}
return 0;
}

int main() {
char t[]="kiss*miss*in*mississippi";
char p[]="missi";
int i;
i=kmp(p,t);
if(i)
printf("pattern is present in text at position
%d",i+1);
else
printf("pattern is not present in text");
return 0;
}

OUTPUT:

pattern is present in text at position 14