Christu Jyothi Institute of Technology & Science

Colombonagar,Yeswanthapur, Jangaon-506167,Telangana

1
 SYLLABUS PROGRAMS

[Link] a program that uses functions to perform the following operations on

singly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

#include<stdio.h>
#include<stdlib.h>
struct node{
int info;
struct node*link;
};
struct node*start=NULL;
void createlist()
{
if(start==NULL){
int n,i;
printf("\n enter the number of nodes:");
scanf("%d",&n);
if(n!=0)
{
int data;
struct node*newnode;
struct node*temp;
newnode=malloc(sizeof(struct node));
newnode->link=NULL;
start=newnode;
temp=start;
printf("\n Enter number to""be intserted:");
scanf("%d",&data);
start->info=data;
for(i=2;i<=n;i++)
{
newnode=malloc(sizeof(struct node));
newnode->link=NULL;

2
temp->link=newnode;
printf("\n enter number to"" be inserted:");
scanf("%d",&data);
newnode->info=data;
temp=temp->link;
}
}
printf("\n the list is created\n");
}
else
printf("\n the list is already created\n");
}
void traverse()
{
struct node*temp;
if(start==NULL)
printf("\n list is empty\n");
else{
temp=start;
while(temp!=NULL)
{
printf("data=%d\n",temp->info);
temp=temp->link;
}
}
}
void insert_At_front()
{
int data;
struct node*temp;
temp=malloc( sizeof(struct node));
printf("\n enter number to""be inserted:");
scanf("%d",&data);
temp->info=data;
temp->link=start;
start=temp;
}

3
void insert_At_End()
{
int data;
struct node*temp,*head;
temp=malloc(sizeof(struct node));
printf("\n Enter number to"" be interted:");
scanf("%d",&data);
temp->link=0;
temp->info=data;
head=start;
while(head->link!=NULL){
head=head->link;
}
head->link=temp;
}
void insert_At_position()
{
struct node*temp,*newnode;
int pos,data,i=1;
newnode=malloc(sizeof(struct node));
printf("\n enter position and data;");
scanf("%d%d",&pos,&data);
temp=start;
newnode->info=data;
newnode->link=0;
while(i<pos-1)
{
temp=temp->link;
i++;
}
newnode->link=temp->link;
temp->link=newnode;
}
void delete_first()
{
struct node*temp;
if(start==NULL)

4
printf("\n list is empty\n");
else
{
temp=start;
free(temp);
}
}
void delete_end()
{
struct node*temp,*prevnode;
if(start==NULL)
printf("\n List is empty\n");
else{
temp=start;
while(temp->link!=0)
{
prevnode=temp;
temp=temp->link;
}
free(temp);
prevnode->link=0;
}
}
void delete_position()
{
struct node*temp,*position;
int i=1,pos;
if(start==NULL)
printf("\n list is empty\n");
else
{
printf("\n enter index:");
scanf("%d",&pos);
position=malloc(sizeof(struct node));
temp=start;
while(i<pos-1)
{

5
temp=temp->link;
i++;
}
position=temp->link;
temp->link=position->link;
free (position);
}
}
void search()
{
int found=-1;
int key;
struct node*tr=start;
if(start==NULL)
{
printf("linked list is empty\n");
}
else
{
printf("\n enter the element you want to search:");
scanf("%d",&key);
while(tr!=NULL)
{
if(tr->info==key)
{
found=1;
break;
}
else
{
tr=tr->link;
}
}
if(found==1){
printf("yes,%d is present in the linked list.\n",key);
}
else

6
{
printf("no,%d is not present in the linked""list.\n",key);
}
}
}
int main()
{
int choice;
createlist();
while(1)
{
printf("\n\t1 To see list\n");
printf("\t2 for insertion at""starting\n");
printf("\t3 for insertion at""end\n");
printf("\t4 for intsertion at""any position\n");
printf("\t5 for delection of""first element\n");
printf("\t6 for delection of""lastelement\n");
printf("\t7 for delection of""element at any position\n");
printf("\t8 search an element in linked list\n");
printf("\t9 To exist\n");
printf("\n enter choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:traverse();
break;
case 2:insert_At_front();
break;
case 3:insert_At_End();
break;
case 4:insert_At_position();
break;
case 5:delete_first();
break;
case 6:delete_end();
break;
case 7:delete_position();

7
 break;
case 8:search();
break;
case 9:exit(1);
break;
default:
printf("incorrect choice\n");
}
return 0;
}
}
OUTPUT:
enter the number of nodes:3
Enter number to be inserted:2
Enter number to be inserted:1
Enter number to be inserted:3
the list is created
[Link] see list
2 for insertion at starting
3 for insertion at end
4 for intsertion at any position
5 for delection of first element
6 for delection of last element
7 for delection of element at any position
8 search an element in linked list
9 To exist
enter choice 1
data=2
data=1
data=3
2 Write a program that uses functions to perform the following operations
on doubly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

#include<stdio.h>
#include<stdlib.h>
struct node

8
{
struct node*prev;
struct node*next;
int data;
};
struct node*head;
void insertion_begining();
void insertion_last();
void insertion_specified();
void deletion_begining();
void deletion_last();
void deletion_specified();
void search();
void display();
void main()
{
int choice=0;
while(choice!=9)
{
printf("*********Main Menu*********\n");
printf("=============================================
==\n");
printf("[Link] in begining\[Link] at last\[Link] at any random
location\[Link] from Begining\[Link] from last\[Link] the
node after the given data\[Link]\[Link]\[Link]\n");
printf(" Enter your choice?\n");
scanf("%d",&choice);
switch (choice)
{
case 1:
insertion_begining();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();

9
break;
case 4:
deletion_begining();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("please enter vaild choice..");
}
}
}
void insertion_begining()
{
struct node*ptr;
int item;
ptr=(struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
{
printf(" OVERFLOW");
}
else
{
printf("\n Enter item value");
scanf("%d",&item);

10
if(head==NULL)
{
ptr->next=NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next=head;
head->prev=ptr;
head=ptr;
}
printf(" node inserted\n");
}
}
void insertion_last()
{
struct node*ptr,*temp;
int item;
ptr=(struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
{
printf("OVERFLOW");
}
else
{
printf(" Enter value");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
ptr->next=NULL;
ptr->prev=NULL;
head=ptr;

11
}
else
{
temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=ptr;
ptr->prev=temp;
ptr->next=NULL;
}
}
printf(" node inserted\n");
}
void insertion_specified()
{
struct node*ptr,*temp;
int item,loc,i;
ptr=(struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
{
printf(" OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp=temp->next;
if(temp==NULL)
{
printf(" There are less than %d elements",loc);
return;
}

12
}
printf("Enter value");
scanf("%d",&item);
ptr->data=item;
ptr->next=temp->next;
ptr->prev=ptr;
temp->next->prev=ptr;
printf(" node inserted\n");
}
}
void deletion_begining()
{
struct node*ptr;
if(head==NULL)
{
printf(" UNDERFLOW");
}
else if (head->next==NULL)
{
head=NULL;
free(head);
printf(" node deleted\n");
}
else
{
ptr=head;
head=head->next;
head->prev=NULL;
free(ptr);
printf(" node deleted\n");
}
}
void deletion_last()
{
struct node*ptr;
if(head==NULL)
{

13
printf(" UNDERFLOW");
}
else if(head->next==NULL)
{
head=NULL;
free(head);
printf(" node deleled\n");
}
else
{
ptr=head;
if(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->prev->next=NULL;
free(ptr);
printf(" node deleted\n");
}
}
void deletion_specified()
{
struct node*ptr,* temp;
int val;
printf(" Enter the data after which the node is to be deleted:");
scanf("%d",&val);
ptr=head;
while(ptr->data!=val)
ptr=ptr->next;
if(ptr->next==NULL)
{
printf(" Can't delete\n");
}
else if(ptr->next->next==NULL)
{
ptr->next=NULL;
}

14
else
{
temp=ptr->next;
ptr->next=temp->next;
temp->next->prev=ptr;
free(temp);
printf(" node deleted\n");
}
}
void display()
{
struct node*ptr;
printf(" printing values...\n");
ptr=head;
while(ptr!=NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node*ptr;
int item,i=0,flag;
ptr=head;
if(ptr==NULL)
{
printf(" Empty list\n");
}
else
{
printf(" Enter item which you want to search?\n");
scanf("%d",&item);
while(ptr!=NULL)
{
if(ptr->data==item)
{

15
printf(" item found at location%d",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr=ptr->next;
}
if(flag==1)
{
printf(" item not found\n");
}
}
}
OUTPUT:
*********Main Menu*********
[Link] in beginning
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] the node after the given data
[Link]
[Link]
[Link]
Enter your choice:
1
Enter item value
12
Node inserted
*********Main Menu*********
[Link] in beginning
[Link] at last
[Link] at any random location

16
[Link] from Beginning
[Link] from last
[Link] the node after the given data
[Link]
[Link]
[Link]
Enter your choice:
1
Enter item value
34
Node inserted
*********Main Menu*********
[Link] in beginning
[Link] at last
[Link] at any random location
[Link] from Beginning
[Link] from last
[Link] the node after the given data
[Link]
[Link]
[Link]
Enter your choice:
8
Printing values….
12
34

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

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node*next;
};
struct node*head;
void beginsert();
void lastinsert();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main()
{
int choice=0;
while(choice!=7)
{
printf("\n****Main menu****\n");
printf("\n choose one option from the following list...");
printf("\n===================================\n");
printf("\[Link] in beginning\[Link] at last\[Link] from
beginning\[Link] from last\[Link] for an element\[Link]\
[Link]\n");
printf("\nenter your choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:beginsert();

18
break;
case 2:lastinsert();
break;
case 3:begin_delete();
break;
case 4:last_delete();
break;
case 5:search();
break;
case 6:display();
break;
case 7:exit(0);
break;
default:
printf("please enter valid choice...");
}
}
}
void beginsert()
{
struct node*ptr,*temp;
int item;
ptr=(struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nenter the node data?");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head=ptr;
ptr->next=head;
}

19
else
{
temp=head;
while(temp->next!=head)
temp=temp->next;
ptr->next=head;
temp->next=ptr;
head=ptr;
}
printf("\nnode inserted\n");
}
}
void lastinsert()
{
struct node*ptr,*temp;
int item;
ptr=(struct node*)malloc(sizeof(struct node));
if(ptr==NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nenter data?");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head=ptr;
ptr->next=head;
}
else
{
temp=head;
while(temp->next!=head)
{
temp=temp->next;

20
ptr->next=head;
}
printf("\nnode inserted\n");
}
}
}
void last_delete()
{
struct node*ptr,*preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next==head)
{
head=NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr=head;
while(ptr->next!=head)
{
preptr=ptr;
ptr=ptr->next;
}
preptr->next=ptr->next;
free(ptr);
printf("\nnode deleted\n");
}
}
void begin_delete()
{
struct node*ptr;
if(head==NULL)
{

21
printf("\nUNDERFLOW");
}
else if(head->next==head)
{
head=NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr=head;
while(ptr->next!=head)
ptr=ptr->next;
ptr->next=head->next;
free(head);
head=ptr->next;
printf("\nnode deleted\n");
}
}
void search()
{
struct node*ptr;
int item,i=0,flag=1;
ptr=head;
if(ptr==NULL)
{
printf("\nempty list\n");
}
else
{
printf("\nenter item which you want to search?\n");
scanf("%d",&item);
if(head->data==item)
{
printf("item found at location %d",i+1);
flag=0;
}

22
else
{
while(ptr->next!=head)
{
if(ptr->data==item)
{
printf("item found at location %d",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr=ptr->next;
}
}
if(flag!=0)
{
printf("item not found\n");
}
}
}
void display()
{
struct node*ptr;
ptr=head;
if(head==NULL)
{
printf("\nnothing to print");
}
else
{
printf("\nprinting values...\n");
while(ptr->next!=head)
{

23
printf("%d\n",ptr->data);
ptr=ptr->next;
}
printf("%d\n",ptr->data);
}
}
OUTPUT:
****Main Menu****
choose one option from the following list..
[Link] in beginning
[Link] at last
[Link] from beginning
[Link] from last
[Link] for an element
[Link]
[Link]
Enter your choice:
1
Enter the node data?
12
Node inserted
****Main Menu****
choose one option from the following list..
[Link] in beginning
[Link] at last
[Link] from beginning
[Link] from last
[Link] for an element
[Link]
[Link]
Enter your choice:
1
Enter the node data?
23
Node inserted
****Main Menu****

24
 choose one option from the following list..
[Link] in beginning
[Link] at last
[Link] from beginning
[Link] from last
[Link] for an element
[Link]
[Link]
Enter your choice:
6
Printing values…
12
23

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

i) Arrays ii) Pointers
i) Arrays
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
clrscr();
top=-1;
printf("\n enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t-----------------");
printf("\n\t [Link]\n\t [Link]\n\t [Link]\n\t [Link]");
do
{
printf("\n enter the choice:");
scanf("%d",&choice);
switch (choice)
{

25
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT");
break;
}
default:
{
printf("\n\t please enter a valid choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\t STACK is over flow");
}
else
{

26
printf("enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t stack is underflow");
}
else
{
printf("\n\t the popped element is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n the elements in STACK\n");
for(i=top;i>=0;i--)
printf("\n%d",stack[i]);
printf("\n press next choice");
}
else
{
printf("\n the STACK is empty");
}
}
OUTPUT:
STACK OPERATIONS USING ARRAY
[Link]
[Link]
[Link]

27
[Link]
enter the choice:1
enter a value to be pushed:33
enter the choice:1
enter a value to be pushed:44
enter the choice:1
enter a value to be pushed:55
enter the choice:
the elements in STACK
55
44
33
press next choice

ii) Pointers
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX_SIZE 3
void push(int i);
void pop(void);
int choice,i;
int *tos,*p1,arr_stack[MAX_SIZE];
int exit_p=1;
int main()
{
int value;
clrscr();
tos=arr_stack;
p1=arr_stack;
printf("\n simple stack example=pointers");
do
{
printf("\n stack pointer:Main Menu");
printf("\n [Link]\t [Link]\t other to exit: Your Choice:");
scanf("%d",& choice);
switch(choice){

28
case 1:
printf("enter value:");
scanf("%d",&value);
push(value);
break;
case 2:
pop();
break;
default:
exit_p=0;
break;
}
}
while(exit_p);
return 0;
}
void push(int i){
if(p1==(tos+MAX_SIZE)){
printf("\n Status:Stack Overflow:\n");
}else{
*p1=i;
printf("\n push value=%d",*(p1));
p1++;
}
}
void pop(void){
if(p1==tos){
printf("\n Status:Stack Underflow.\n");
}else{
p1--;
printf("\n pop value:%d",*(p1));
}
}
OUTPUT:
Simple stack example=pointers
Stack pointer:Main menu
[Link] [Link] other to exit:your choice:1

29
 enter value:1
push value=1
stack pointer:main menu
[Link] [Link] other to exit:your choice:1
push value=3
stack pointer:main menu
[Link] [Link] other to exit:your choice:2
pop value=3

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

i) Arrays ii) Pointers
i) Arrays

#include<stdio.h>
#define MAX 50
void insert();
void delet();
void display();
int queue_array[MAX];
int rear=-1;
int front=-1;
main()
{
int chioce;
clrscr();
while(1)
{
printf("[Link] elemnts to queue:\n");
printf("[Link] elements from queue\n");
printf("[Link] all elements of queue\n");
printf("[Link]\n");
printf("enter your chioce\n");
scanf("%d", &chioce);
switch(chioce)
{
case 1:
insert();

30
break;
case 2:
delet();
case 3:
display();
break;
case 4:
exit(1);
default:
printf("wrong chioce");
}
}
}
void insert()
{
int add_item;
if(rear==MAX-1)
printf("queue overflow\n");
else
{
if(front==-1)
front=0;
printf("\ninsert the elmnt in queue");
scanf("%d",&add_item);
rear=rear+1;
queue_array[rear]=add_item;
}
}
void delet()
{
if(front==-1||front>rear)
{
printf("queue underflow\n");
return ;
}
else
{

31
printf("elements deleted from queue is %d\n",queue_array[front]);
front=front+1;
}
}
void display()
{
int i;
if(front==-1)printf("queue is empty\n");
else
{
printf("queue is \n");
for(i=front;i<=rear;i++)
printf("%d\n",queue_array[i]);
printf("\n");
}
}
OUTPUT:
[Link] elements to queue
[Link] elements from queue
[Link] all elements of queue
[Link]
Enter your choice:1
insert the element in queue:66
[Link] elements to queue
[Link] elements from queue
[Link] all elements of queue
[Link]
Enter your choice:1
insert the element in queue:55
[Link] elements to queue
[Link] elements from queue
[Link] all elements of queue
[Link]
Enter your choice:1
insert the element in queue:88
[Link] elements to queue
[Link] elements from queue

32
[Link] all elements of queue
[Link]
Enter your choice:3
queue is:
66
55
88
ii) Pointers
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define max_size 10
int insert_q(int queue[max_size],int*rear,int*data)
{
if(*rear==max_size-1)
return(-1);
else
{
*rear=*rear+1;
queue[*rear]=*data;
return(1);
}
}
int del_q(int queue[max_size],int*front,int*rear,int*data)
{
if(*front==*rear)
return(-1);
else
{
(*front)++;
(*data)==queue[front];
return(1);
}
}
int main()
{
int queue[max_size],data;

33
int front,rear,reply,option;
clrscr();
front=rear=-1;
printf("\t menu");
printf("\n============\n");
printf("\n [Link] element in queue");
printf("\n [Link] element from the queue");
printf("\n [Link]");
printf("\n ===========");
while(1)
{
printf("\n choose operation:");
scanf("%d",&option);
switch(option)
{
case 1:// insert
printf("\n enter number:");
scanf("%d",&data);
reply=insert_q(queue,&rear,&data);
if(reply==-1)
printf("queue is full");
else
printf("%d is inserted in queue\n",data);
break;
case 2:// delete_q(int,int,int,int);
reply=del_q(queue,&front,&rear,&data);
if(reply==-1)
printf("queue is empty");
else
printf("\n deleted number is:%d\n", data);
break;
case 3:exit(0);
}
}
}

OUTPUT:

34
 Menu
[Link] element in queue
[Link] element from queue
[Link]
Choose operation:1
Enter number:22
22 is inserted in queue
Menu
[Link] element in queue
[Link] element from queue
[Link]
Choose operation :1
Enter number:33
33 is inserted in queue
Menu
[Link] element in queue
[Link] element from queue
[Link]
Choose operation :2
Deleted number is : 33

6. Write a program that implements the following sorting methods to sort a

35
given list of integers in ascending order
i) Quick sort ii) Heap sort iii) Merge sort

i) Quick sort
// C program to implement Quick Sort Algorithm
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function
int partition(int arr[], int low, int high)
{
// initialize pivot to be the first element
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
// condition 1: find the first element greater than
// the pivot (from starting)
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
// condition 2: find the first element smaller than
// the pivot (from last)
while (arr[j] > pivot && j >= low + 1) {
j--;
}
if (i < j) {
swap(&arr[i], &arr[j]);
}
}
swap(&arr[low], &arr[j]);
return j;

36
 }
// QuickSort function
void quickSort(int arr[], int low, int high)
{
if (low < high) {
// call Partition function to find Partition Index
int partitionIndex = partition(arr, low, high);
// Recursively call quickSort() for left and right
// half based on partition Index
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
// driver code
int main()
{
int arr[] = { 19, 17, 15, 12, 16, 18, 4, 11, 13 },i;
int n = sizeof(arr) / sizeof(arr[0]);
// printing the original array
printf("Original array: ");
for ( i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
// calling quickSort() to sort the given array
quickSort(arr, 0, n - 1);
// printing the sorted array
printf("\nSorted array: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
OUTPUT:
Original array:19 17 15 12 16 18 4 11 13
Sorted array: 4 11 12 13 15 16 17 18 19

ii) Heap sort

37
 #include <stdio.h>
// Heapify function
void heapify(int arr[], int n, int i)
{
int temp, maximum, left_index, right_index;
// currently assuming i postion to
// be holding the largest value
maximum = i;
// right child index
right_index = 2 * i + 2;
// left child index
left_index = 2 * i + 1;
// if left index value is grater than the current index
// value
if (left_index < n && arr[left_index] > arr[maximum])
maximum = left_index;
// if right index value is grater than the current index
// value
if (right_index < n && arr[right_index] > arr[maximum])
maximum = right_index;
// checking if we needed swaping the elements or not
if (maximum != i) {
temp = arr[i];
arr[i] = arr[maximum];
arr[maximum] = temp;
heapify(arr, n, maximum);
}
}
// HeapSorting function
void heapsort(int arr[], int n)
{
int i, temp;
// performing heapify on the non leaf nodes so n/2 - 1
// to 0 are the non leaf nodes
for (i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// the current array is changed to max heap
for (i = n - 1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
} // Driver code
int main()
{
// initializing the array
int arr[] = { 20, 18, 5, 15, 3, 2 };

38
int n = 6;
// Displaying original array
printf("Original Array : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
heapsort(arr, n);
// Displaying sorted array
printf("Array after performing heap sort: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
OUTPUT:

Original Array : 20 18 5 15 3 2
Array after performing heap sort:2 3 15 18 20

iii) Merge sort

#include<stdio.h>
#define max 100
int a[11]= {10,14,19,26,27,31,33,35,42,44,0};
int b[10];
void merging(int low,int mid,int high)
{
int l1,l2,i;
for(l1=low,l2=mid+1,i=low;l1 <=mid &&l2 <= high; i++)
{
if(a[l1]<=a[l2])
b[i]=a[l1++];else
b[i]=a[l2++];
}
while(l1<=mid)b[i++]=a[l1++];
while(l2 <= high)b[i++]=a[l2++];
for(i=low; i<=high; i++)a[i]= b[i];
}
void sort(int low,int high)
{
int mid;
if(low<high)

39
 {
mid = (low + high) / 2;
sort(low,mid);sort(mid+1,high);
merging(low,mid,high);
}
else
{
return;
}
}
int main()
{
int i;
clrscr();
printf("\nListbeforesorting\n");for(i= 0;i<=max;i++)
printf("%d\t\t",a[i]);
sort(0,max);
printf("\nList after sorting\n");for(i = 0; i <= max; i++)
printf("%d\t\t",a[i]);
}
OUTPUT
List be for sorting
10 14 19 26 27
31 33 35 42 44 0
List after sorting
0 10 14 19
26 27 31 33 35 42 44

7. Write a program to implement the tree traversal methods

#include<stdio.h>
#include<stdlib.h>
struct node
{
data;
struct node* left;struct node*right;

40
 };
struct node*newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;node->left=NULL;node->right = NULL;return(node);
}
void printPostorder(struct node*node)
{
if(node == NULL) return;printPostorder(node->left);printPostorder(node-
>right);printf("%d",node->data);
}
void printInorder(struct node*node)
{
if (node == NULL)return;printInorder(node->left);
printf("%d ", node->data);printInorder(node->right);
}
void printPreorder(struct node*node)
{
if (node == NULL) return;printf("%d ", node->data);printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node *root = newNode(1);root->left=newNode(2);
clrscr();
root->right=newNode(3);
root->left->left=newNode(4);root->left->right=newNode(5);
printf("\nPreordertraversalofbinarytree is\n")
;printPreorder(root);
printf("\nInorder traversal of binary tree is \n");printInorder(root);
printf("\nPostorder traversal of binary tree is \n");printPostorder(root);
getchar();
return 0;
}
OUTPUT
Preordertraversalofbinarytree is
12453
Inorder traversal of binary tree is
42513

Postorder traversal of binary tree is

4 5231

8. Write a program to implement

i) Binary Search tree ii) B Trees iii) B+ Trees iv)AVL trees v)
Red - Black trees
i) Binary Search Tree
// C program to implement binary search tree
#include <stdio.h>

41
 #include <stdlib.h>
// Define a structure for a binary tree node
struct BinaryTreeNode {
int key;
struct BinaryTreeNode *left, *right;
};
// Function to create a new node with a given value
struct BinaryTreeNode* newNodeCreate(int value)
{
struct BinaryTreeNode* temp
= (struct BinaryTreeNode*)malloc(
sizeof(struct BinaryTreeNode));
temp->key = value;
temp->left = temp->right = NULL;
return temp;
}// Function to search for a node with a specific key in the
// tree
struct BinaryTreeNode*
searchNode(struct BinaryTreeNode* root, int target)
{
if (root == NULL || root->key == target) {
return root;
}
if (root->key < target) {
return searchNode(root->right, target);
}
return searchNode(root->left, target);
}
// Function to insert a node with a specific value in the
// tree
struct BinaryTreeNode*
insertNode(struct BinaryTreeNode* node, int value)
{
if (node == NULL) {
return newNodeCreate(value);
}
if (value < node->key) {
node->left = insertNode(node->left, value);
}
else if (value > node->key) {
node->right = insertNode(node->right, value);
}
return node;
}// Function to perform post-order traversal
void postOrder(struct BinaryTreeNode* root)
{ if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf(" %d ", root->key);
}

42
}// Function to perform in-order traversal
void inOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
inOrder(root->left);
printf(" %d ", root->key);
inOrder(root->right);
}
}// Function to perform pre-order traversal
void preOrder(struct BinaryTreeNode* root)
{
if (root != NULL) {
printf(" %d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
// Function to find the minimum value
struct BinaryTreeNode* findMin(struct BinaryTreeNode* root)

{
if (root == NULL) {
return NULL;
}
else if (root->left != NULL) {
return findMin(root->left);
}
return root;
}
// Function to delete a node from the tree
struct BinaryTreeNode* delete (struct BinaryTreeNode* root,int x)
{
if (root == NULL)
return NULL;

if (x > root->key) {
root->right = delete (root->right, x);
}
else if (x < root->key) {
root->left = delete (root->left, x);
}
else {
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
else if (root->left == NULL
|| root->right == NULL) {
struct BinaryTreeNode* temp;
if (root->left == NULL) {
temp = root->right;

43
 }
else {
temp = root->left;
}
free(root);
return temp;
}
else {
struct BinaryTreeNode* temp
= findMin(root->right);
root->key = temp->key;
root->right = delete (root->right, temp->key);
}
}
return root;
}

int main()
{
// Initialize the root node
struct BinaryTreeNode* root = NULL;
struct BinaryTreeNode* temp = delete (root, 70)
// Insert nodes into the binary search tree
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
//struct BinaryTreeNode* temp = delete (root, 70);
// Search for a node with key 60
if (searchNode(root, 60) != NULL) {
printf("60 found");
}
else {
printf("60 not found");
}
printf("\n");
// Perform post-order traversal
postOrder(root);
printf("\n");
// Perform pre-order traversal
preOrder(root);
printf("\n");
// Perform in-order traversal
inOrder(root);
printf("\n");
// Perform delete the node (70)
//struct BinaryTreeNode* temp = delete (root, 70);

44
 printf("After Delete: \n");
inOrder(root);
// Free allocated memory (not done in this code, but
// good practice in real applications)
return 0;
}

OUTPUT

60 found

20 40 30 60 80 70 50
50 30 20 40 70 60 80

20 30 40 50 60 70 80
After delete:

20 30 40 50 60 70 80

ii) B TREE
#include<stdio.h>
#include<stdlib.h>
#define MAX 3
#define MIN 2
struct BTreeNode{
int val[MAX+1],count;
struct BtreeNode*link[MAX+1];
};
struct Btree*root;
//creat a node
struct BTreeNode*creatNode(int val,struct BTreeNode*child){
struct BTreeNode*newNode;
newNode=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
newNode->val[1]=val;
newNode->count=1;
newNode->link[0]= root;
newNode->link[1]= child;
return newNode;
}
//insert node
void insertNode(int val,int pos,struct BTreeNode*node,struct BTreeNode*child){
int j=node->count;
while(j>pos){
node->val[j+1]=node->val[j];
node->link[j+1]=node->link[j];
j--;
}
node->val[j+1]=val;
node->link[j+1]=child;
node->count++;

45
 }
//split node
void splitNode(int val,int*pval,int pos,struct BTreeNode*node,struct
BTreeNode*child,struct BtreeNode**newNode){
int median,j;
if(pos>MIN)
median=MIN+1;
else
median=MIN;
*newNode=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
j=median=1;
while(j<=MAX){
(*newNode)->val[j-median]=node->val[j];
(*newNode)->link[j-median]=node->link[j];
j++;
}
node->count=median;
(*newNode)->count=MAX-median;
if(pos<=MIN){
insertNode(val,pos,node,child);
}else{
insertNode(val,pos-median,*newNode,child);
}
*pval=node->val[node->count];
(*newNode)->link[0]=node->link[node->count];
node->count--;
}
//set the value
int setValue(int val,int*pval,struct BTreeNode*node,struct BTreeNode**child){
int pos;
if(!node){
*pval=val;
*child=NULL;
return 1;
}
if(val<node->val[1]){
pos=0;
}else{
for(pos=node->count;
(val<node->val[pos]&&pos>1);pos--);
if(val==node->val[pos]){
printf("Duplicates are not permitted\n");
return 0;
}
}
if(setValue(val,pval,node->link[pos],child)){
if(node->count<MAX){
insertNode(*pval,pos,node,*child);
}else{
splitNode(*pval,pval,pos,node,*child,child);

46
return 1;
}
}
return 0;
}
//insert the value
void insert(int val){
int flag,i;
struct BTreeNode*child;
flag=setvalue(val,&i,root,&child);
if(flag)
root=CreatNode(i,child);
}
//search node
void search(int val,int*pos,stuct BTreeNode*myNode){
if(!myNode){
return,
}
if(val<myNode->val[1]){
*pos=0;
}else{
for(*pos=myNode->count;(val<myNode->val[*pos]&&*pos>1);(*pos)--)
if(val==myNode->val[*pos]){
print("%d is fount",val);
return;
}
}
search(val,pos,myNode->link[*pos]);
return;
}
//Traverse then nodes
void traversal(struct BTreeNode*myNode){
int i;
if(myNode){
for(i=0,i<myNode->count;i++){
traversal(myNode->link[i]);
}
}
int main(){
int val,ch;
insert(8); insert(9); insert(10); insert(11); insert(15); insert(16); insert(17); insert(18);
insert(20); insert(23); traversal(root);
printf("\n");
search(11,&ch,root);}

OUTPUT:
9 10 11 15 16 17 18 20 23
11 is found

iii)B+TREE

47
 /* For simplicity, provide a basic implementation focusing on insertion, search, and a
simple traversal. We will not include deletion as it is quite complex and would make
the code exceedingly long. In practice, B-tree deletion requires handling numerous
cases to redistribute or merge nodes. */

#include <stdio.h>
#include <stdlib.h>
#define MAX_KEYS 3 // Maximum keys in a node (t-1 where t is the minimum
degree)
#define MIN_KEYS 1 // Minimum keys in a node (ceil(t/2) - 1)
#define MAX_CHILDREN (MAX_KEYS + 1) // Maximum children in a
node (t)
typedef struct BTreeNode {
int keys[MAX_KEYS];
struct BTreeNode* children[MAX_CHILDREN];
int numKeys;
int isLeaf;
} BTreeNode;

BTreeNode* createNode(int isLeaf) {

BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
int i;
node->isLeaf = isLeaf;
node->numKeys = 0;
for ( i = 0; i < MAX_CHILDREN; i++) {
node->children[i] = NULL;
}
return node;
}

void splitChild(BTreeNode* parent, int index, BTreeNode* child) {

int i;
BTreeNode* newChild = createNode(child->isLeaf);
newChild->numKeys = MIN_KEYS;

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

newChild->keys[i] = child->keys[i + MIN_KEYS + 1];
}

if (!child->isLeaf) {
for ( i = 0; i < MIN_KEYS + 1; i++) {
newChild->children[i] = child->children[i + MIN_KEYS + 1];
}
}

child->numKeys = MIN_KEYS;

for ( i = parent->numKeys; i >= index + 1; i--) {

parent->children[i + 1] = parent->children[i];
}

48
parent->children[index + 1] = newChild;
for ( i = parent->numKeys - 1; i >= index; i--) {
parent->keys[i + 1] = parent->keys[i];
}
parent->keys[index] = child->keys[MIN_KEYS];
parent->numKeys++;
}
void insertNonFull(BTreeNode* node, int key) {
int i = node->numKeys - 1;
if (node->isLeaf) {
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->numKeys++;
} else {
while (i >= 0 && node->keys[i] > key) {
i--;
}

if (node->children[i + 1]->numKeys == MAX_KEYS) {

splitChild(node, i + 1, node->children[i + 1]);

if (key > node->keys[i + 1]) {

i++;
}
}

insertNonFull(node->children[i + 1], key);

}
}
void insert(BTreeNode** root, int key) {
BTreeNode* r = *root;
int i = 0;
if (r->numKeys == MAX_KEYS) {
BTreeNode* newRoot = createNode(0);
newRoot->children[0] = r;
splitChild(newRoot, 0, r);
if (newRoot->keys[0] < key) {
i++;
}
insertNonFull(newRoot->children[i], key);
*root = newRoot;
} else {
insertNonFull(r, key);
}
}
void traverse(BTreeNode* root) {
int i;

49
if (root == NULL) return;
// int i;
for (i = 0; i < root->numKeys; i++) {
if (!root->isLeaf) {
traverse(root->children[i]);
}
printf("%d ", root->keys[i]);
}

if (!root->isLeaf) {
traverse(root->children[i]);
}
}
int main() {
BTreeNode* root = createNode(1);
clrscr();
insert(&root, 10);
insert(&root, 20);
insert(&root, 5);
insert(&root, 6);
insert(&root, 12);
insert(&root, 30);
insert(&root, 7);
insert(&root, 17);

printf("Traversal of the constructed B-tree is:\n");

traverse(root);

return 0;
}

OUTPUT
Traversal of the constructed B+tree is:
5 6 7 10 12 17 20 30

iv)AVL trees
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int getHeight(struct Node *n){
if(n==NULL)
return 0;
return n->height;

50
 }
struct Node *createNode(int key){
struct Node* node = (struct Node *) malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
int getBalanceFactor(struct Node * n){
if(n==NULL){
return 0;
}
return getHeight(n->left) - getHeight(n->right);
}
struct Node* rightRotate(struct Node* y){
struct Node* x = y->left;
struct Node* T2 = x->right;
x->right = y;
y->left = T2;
x->height = max(getHeight(x->right), getHeight(x->left)) + 1;
y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
return x;
}
struct Node* leftRotate(struct Node* x){
struct Node* y = x->right;
struct Node* T2 = y->left;
y->left = x;
x->right = T2;

x->height = max(getHeight(x->right), getHeight(x->left)) + 1;

y->height = max(getHeight(y->right), getHeight(y->left)) + 1;
return y;
}
struct Node *insert(struct Node* node, int key){
int bf;
if (node == NULL)
return createNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
bf = getBalanceFactor(node);
// Left Left Case
if(bf>1 && key < node->left->key){
return rightRotate(node);
}
// Right Right Case
if(bf<-1 && key > node->right->key){

51
 return leftRotate(node);
}
// Left Right Case
if(bf>1 && key > node->left->key){
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if(bf<-1 && key < node->right->key){
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preOrder(struct Node *root)
{
if(root != NULL)
{ printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
int main(){
struct Node * root = NULL;
clrscr();
root = insert(root, 1);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 5);
root = insert(root, 6);
root = insert(root, 3);
preOrder(root);
return 0;
}

OUTPUT
421356

v) Red - Black trees

#include <stdio.h>
#include <stdlib.h>
// Structure to represent each
// node in a red-black tree
struct node {
int d; // data
int c; // 1-red, 0-black
struct node* p; // parent
struct node* r; // right-child

52
struct node* l; // left child
};

// global root for the entire tree

struct node* root = NULL;

// function to perform BST insertion of a node

struct node* bst(struct node* trav,
struct node* temp)
{
// If the tree is empty,
// return a new node
if (trav == NULL)
return temp;
// Otherwise recur down the tree
if (temp->d < trav->d)
{
trav->l = bst(trav->l, temp);
trav->l->p = trav;
}
else if (temp->d > trav->d)
{
trav->r = bst(trav->r, temp);
trav->r->p = trav;
}

// Return the (unchanged) node pointer

return trav;
}
// Function performing right rotation
// of the passed node
void rightrotate(struct node* temp)
{
struct node* left = temp->l;
temp->l = left->r;
if (temp->l)
temp->l->p = temp;
left->p = temp->p;
if (!temp->p)
root = left;
else if (temp == temp->p->l)
temp->p->l = left;
else
temp->p->r = left;
left->r = temp;
temp->p = left;
}
// Function performing left rotation
// of the passed node
void leftrotate(struct node* temp)

53
{
struct node* right = temp->r;
temp->r = right->l;
if (temp->r)
temp->r->p = temp;
right->p = temp->p;
if (!temp->p)
root = right;
else if (temp == temp->p->l)
temp->p->l = right;
else
temp->p->r = right;
right->l = temp;
temp->p = right;
}
// This function fixes violations
// caused by BST insertion
void fixup(struct node* root, struct node* pt)
{ int t;
struct node* parent_pt = NULL;
struct node* grand_parent_pt = NULL;
while ((pt != root) && (pt->c != 0)
&& (pt->p->c == 1))
{
parent_pt = pt->p;
grand_parent_pt = pt->p->p;
/* Case : A
Parent of pt is left child
of Grand-parent of
pt */
if (parent_pt == grand_parent_pt->l)
{
struct node* uncle_pt = grand_parent_pt->r;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle_pt != NULL && uncle_pt->c == 1)
{
grand_parent_pt->c = 1;
parent_pt->c = 0;
uncle_pt->c = 0;
pt = grand_parent_pt;
}

else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt == parent_pt->r) {
leftrotate(parent_pt);

54
 pt = parent_pt;
parent_pt = pt->p;
}

/* Case : 3
pt is left child of its parent
Right-rotation required */
rightrotate(grand_parent_pt);
t = parent_pt->c;
parent_pt->c = grand_parent_pt->c;
grand_parent_pt->c = t;
pt = parent_pt;
}
}

/* Case : B
Parent of pt is right
child of Grand-parent of
pt */
else {
struct node* uncle_pt = grand_parent_pt->l;

/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if ((uncle_pt != NULL) && (uncle_pt->c == 1))
{
grand_parent_pt->c = 1;
parent_pt->c = 0;
uncle_pt->c = 0;
pt = grand_parent_pt;
}
else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt == parent_pt->l) {
rightrotate(parent_pt);
pt = parent_pt;
parent_pt = pt->p;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
leftrotate(grand_parent_pt);
t = parent_pt->c;
parent_pt->c = grand_parent_pt->c;
grand_parent_pt->c = t;
pt = parent_pt;
}

55
 }
}
}
// Function to print inorder traversal
// of the fixated tree
void inorder(struct node* trav)
{
if (trav == NULL)
return;
inorder(trav->l);
printf("%d ", trav->d);
inorder(trav->r);
}
// driver code
int main()
{
int n = 7,i;
int a[7] = { 17, 62, 52, 14, 35, 27, 18 };
clrscr();
for (i = 0; i < n; i++) {
// allocating memory to the node and initializing:
// 1. color as red
// 2. parent, left and right pointers as NULL
// 3. data as i-th value in the array
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->r = NULL;
temp->l = NULL;
temp->p = NULL;
temp->d = a[i];
temp->c = 1;
// calling function that performs bst insertion of
// this newly created node
root = bst(root, temp);
// calling function to preserve properties of rb
// tree
fixup(root, temp);
root->c = 0;
}
printf("\nInorder Traversal of Created Tree\n");
inorder(root);
return 0;
}
OUTPUT
inorder traversal of created tree

14 17 18 27 35 52 62

56
9. Write a program to implement the graph traversal methods.
i) BFS ii) DFS

i)BFS
#include<stdio.h>
#include<stdlib.h>
#define MAX 5
struct Vertex {
char label;
int visited;
};
int queue[MAX];
int rear=-1;
int front=0;
int queueItemCount=0;
struct Vertex* firstVertices[MAX];
int adjMatrix[MAX][MAX];
int vertexCount=0;
//int vertexIndex[];
void insert(int data) {
queue[++rear]=data;
queueItemCount++;
}
int removeData() {
queueItemCount--;
return queue[front++];
}
int isQueueEmpty(){
return queueItemCount==0;
}
void addVertex(char label){
struct Vertex*vertex=(struct Vertex*)malloc(sizeof(struct Vertex));
vertex->label=label;
vertex->visited=0;
firstVertices[vertexCount++] = vertex;
}
void addEdge(int start, int end) {
adjMatrix[start][end]= 1;
adjMatrix[end][start]= 1;
}
void displayVertex(int vertexIndex) {
char label;
printf("%c", firstVertices[vertexIndex]->label);
}
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for(i=0;i<vertexCount;i++) {
if(adjMatrix[vertexIndex][i]==1&&firstVertices[i]->visited==0)
return i;

57
 }
return -1;
}
void breadthFirstSearch() {
int i;
int unvisitedVertex;
//void displayVertex(int);
firstVertices[0]->visited=1;
insert(0);
while(!isQueueEmpty()) {
int tempVertex=removeData();
while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex))!=-1)
{
firstVertices[unvisitedVertex]->visited=1;
displayVertex(unvisitedVertex) ;
insert(unvisitedVertex);
}
}
for(i=0;i<vertexCount;i++) {
firstVertices[i]->visited =0;
}
}
int main() {
int i, j;
for(i=0;i<MAX;i++) {
for(j=0;j<MAX;j++)
adjMatrix[i][j] = 0;
}
addVertex('S');
addVertex('A');
addVertex('B');
addVertex('C');
addVertex('D');
addEdge(0, 1);
addEdge(0, 2);
addEdge(0, 3);
addEdge(1, 4);
addEdge(2, 4);
addEdge(3, 4);
printf("\nBreadth First Search:");
breadthFirstSearch();
return 0;
}
OUPUT:

Breadth first search :ABCD

58
iii) DFS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
void addVertex(char);
void addEdge(int, int);
void displayVertex(int);
void depthFirstSearch();
int getAdjUnvisitedVertex(int);
struct Vertex {
char label;
bool visited;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex * lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
stack[++top] = item;
}

int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
struct Vertex * vertex = (struct Vertex * ) malloc(sizeof(struct Vertex));
vertex -> label = label;
vertex -> visited = false;
lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start, int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;

59
}
//display the vertex
void displayVertex(int vertexIndex) {
printf("%c ", lstVertices[vertexIndex] -> label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for (i = 0; i < vertexCount; i++) {
if (adjMatrix[vertexIndex][i] == 1 && lstVertices[i] -> visited == false) {
return i;
}
}
return -1;
}
void depthFirstSearch() {
int i;
//mark first node as visited
lstVertices[0] -> visited = true;
//display the vertex
displayVertex(0);
//push vertex index in stack
push(0);
while (!isStackEmpty()) {
//get the unvisited vertex of vertex which is at top of the stack
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//no adjacent vertex found
if (unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex] -> visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//stack is empty, search is complete, reset the visited flag
for (i = 0; i < vertexCount; i++) {
lstVertices[i] -> visited = false;
}
}
int main() {
int i, j;
for (i = 0; i < MAX; i++) // set adjacency {
for (j = 0; j < MAX; j++) // matrix to 0
adjMatrix[i][j] = 0;
addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4

60
 addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D
printf("Depth First Search: ");
depthFirstSearch();
return 0;
}

OUTPUT:
Depth First Search: S A D B C

[Link] a Pattern matching algorithms using Boyer- Moore, Knuth-Morris-

Pratt
KMP
#include<stdio.h>
#include<string.h>
char txt[100],pat[100];
int M ,N ,lps[100],j=0,i=0;
void computeLPSArray()
{
int len = 0, i;
lps[0] = 0;
i = 1;
while(i < M)
{
if(pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if( len != 0 )
len = lps[len-1];
else
{
lps[i] = 0;
i++;
}
}
}
}
Qvoid KMPSearch()
{
int j=0,i=0;

61
 M = strlen(pat);
N = strlen(txt);
computeLPSArray();
while(i < N)
{
if(pat[j] == txt[i])
{
j++;
i++;
}

if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
else if(pat[j] != txt[i])
{
if(j != 0)
j = lps[j-1];
else
i = i+1;
}
}
}

int main()
{
clrscr();
printf("\n ENTER THE TEXT : ");
gets(txt);
printf("\n ENTER THE PATTERN : ");
gets(pat);
KMPSearch();
return 0;
}

OUTPUT:
ENTER THE TEXT:welcome to cjits

Enter the pattern:cjits

Found pattern at index 11

Boyer morrie .c

62
 # include <limits.h>
# include <string.h>
# include <stdio.h>
# define NO_OF_CHARS 256
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}/
/ The preprocessing function for Boyer Moore's bad character heuristic
void badCharHeuristic(char *str, int size, int badchar[NO_OF_CHARS]) {
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
void search(char *txt, char *pat) {
int m = strlen(pat);
int n = strlen(txt);
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with respect to text
while (s <= (n - m)) {
int j = m - 1;

while (j >= 0 && pat[j] == txt[s + j])

j--;
if (j < 0) {
printf("\n pattern occurs at shift = %d", s);
s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
}
El se
s += max(1, j - badchar[txt[s + j]]);
}
}
int main() {
char txt[] = "ABAAABCD";
char pat[] = "ABC";
search(txt, pat);
return 0;
}

OUTPUT:

Pattern occurs at shift=4

63