P.S.

V COLLEGE OF ENGINEERING AND

TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE

AND ENGINEERING

YEAR/SEM: II/III

LAB MANUAL

REGULATION 2021

SUBJECT CODE:CS311
SUBJECT NAME:DATA STRUCTURE
LABORATORY
Ex.No.1a ARRAY IMPLEMENTATION OF STACK ADTS

AIM:
To write a program for stack implementation using Array.

ALGORITHM/PSEUDO CODE:

1. Define a array which stores stack elements.

2. The operations on the stack are
a. PUSH data into the stack
b. POP data out of stack
3. PUSH DATA INTO STACK
a. Enter the data to be inserted into stack.
b. If TOP is NULL the input data is the first
node in stack. The link of the node is NULL.
TOP points to that node.
c. I f TOP is NOT NULL the link of TOP points to
the new node. TOP points to that node.
4. POP DATA FROM STACK
a. If TOP is NULL the stack is empty
b. If TOP is NOT NULL the link of TOP is
the current TOP. The pervious TOP is
popped from stack.
5. The stack represented by array is traversed to display its content.

PROGRAM:
#include <stdio.h>
#include <stdlib.h>
int stack[6],rev[6];
int top=-1,k=0;
int size;
void push();
void pop();
void display();
int pali();
void main()
{
int choice,f;
printf("Enter the size for stack\n");
scanf("%d",&size);
printf("1.Push\n2.Pop\n3.Display\n4.Check for Palindrome\n5.Exit\n");
while(1)
{
printf("Enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:f=pali();
if(f==1)
printf("It's Palindrome\n");
else
printf("It's not a Palindrome\n");
break;
case 5:exit(0);
default:printf("Wrong choice...\n");
}}}
void push() {
int num;
if(top==(size-1))
{
printf("Stack Overflow\n");
}
else {
printf("Enter the number to be pushed\n");
scanf("%d",&num);
top++;
stack[top]=num; }}
void pop() {
int num;
if(top==-1)
{
printf("Stack Underflow\n");
}
else {
num=stack[top];
printf("Popped element is %d\n",num);
top--;
}}
void display() {
int i;
if(top==-1)
{
printf("Stack Underflow\n");
}
else
{
printf("Stack Contents....\n");
for(i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
rev[k++]=stack[i];
}
}
}
int pali()
{
int i,flag=1;
for(i=top;i>=0;i--)
{
if(stack[i]!=rev[--k])
{
flag=0;
}
}
return flag;
}

OUTPUT:
--------STACK OPERATIONS-----------
1.Push
2.Pop
3. Display
4. Check for Palindrome
5.Exit
-----------------------
Enter your choice: 1
Enter the element to be inserted: 1
Enter your choice: 1
Enter the element to be inserted: 2
Enter your choice: 1
Enter the element to be inserted: 1
Enter your choice: 1
Enter the element to be inserted: 5
Enter your choice: 2
The poped element: 5
Enter your choice: 3
The stack elements
are:
1
2
1
Enter your choice: 4
It’s a Palindrome
Enter your choice: 5

RESULT:

Thus the C program has been executed successfully.

Ex.No.1b ARRAY IMPLEMENTATION OF QUEUE ADTS

AIM:
To write a program implements the queue.
ALGORITHM:
1. Define a array which stores queue elements
2. The operations on the queue are a)INSERT data into the queue
b)DELETE data out of queue.
3. INSERT DATA INTO queue
a. Enter the data to be inserted into queue.
b. If TOP is NULL the input data in the first node in the queue & the link
of the node is NULL.
c. If the TOP is not NULL the link of top points to the new node. TOP
points to the node
1. Delete data from queue.
a. If TOP is NULL the queue is empty
b. If TOP is NOT NULL the link of TOP is the current
TOP,the pervious TOP is popped from queue.
2. The queue represented by linked list is traversed to display its content.

PROGRAM:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define SIZE 5
char CQ[SIZE];
int front=-1, rear=-1;
int ch;
void CQ_Insert();
void CQ_Delet();
void CQ_Display();
void main()
{
printf("1.Insert\n2.Delete\n3.Display\n4.Exit\n");
while(1)
{
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: CQ_Insert();
break;
case 2:CQ_Delet();
break;
case 3:CQ_Display();
break;
case 4: exit(0);
}
}}
void CQ_Insert() {
char ele;
if(front==(rear+1)%SIZE) {
printf("Circular Queue Full\n");
return; }
if(front==-1)
front++;
printf("Enter the element to be inserted\n");
scanf("\n%c",&ele);
rear = (rear+1)%SIZE;
CQ[rear] =ele; }
void CQ_Delet() {
char item;
if(front ==-1)
{
printf("Circular Queue Empty\n");
return; }
else if(front == rear) {
item=CQ[front];
printf("Deleted element is: %c\n",item);
front=-1;
rear=-1;
}
else {
item =CQ[front];
printf("Deleted element is: %c\n",item);
front = (front+1)%SIZE; }}
void CQ_Display()
{
int i;
if(front==-1)
printf("Circular Queue is Empty\n");
else
{
printf("Elements of the circular queue are..\n");
for(i=front;i!=rear;i=(i+1)%SIZE)
{
printf("%c\t",CQ[i]);
}
printf("%c\n",CQ[i]);
}
}

OUTPUT:
Circular Queue operations
1.insert
2.delete
3.display
4.exit

Enter your choice:1

Enter element to be insert: a

Enter your choice:1

Enter element to be insert: b
Enter your choice:1
Enter element to be insert: c

Enter your choice:3

abc

Enter your choice:2

Deleted element is: a

Enter your choice:3

bc
Enter your choice:4
RESULT:

Thus the above C program has been executed successfully.

VIVA QUESTIONS:

1. Where are stacks used?

2. When would you choose the array representation?
3. Define stack.
4. What are the values that can be assigned to the top pointer in the stack?
5. What is ADT queue?
6. Why backtracking algorithm is one of the stack base applications.
7. What is the working logic of 8 queen problems?
8. What are the three conditions of tower of Hanoi concepts?
9. Is the palindrome checking process is one of stack application? Justify.
10. Explain the condition to be followed during the postfix conversion.
11. What is the operation to test queue?
Ex.No.2 ARRAY IMPLEMENTATION OF LIST ADTS

AIM:
To write a program to create, insert, search and delete the element in the
list using array implementation.
ALGORITHM:
1. Start the program.
2. Create a node with two fields’ data and link field.
a. Allocate space for the node dynamically.
b. Create link between the created nodes and let the last node be with NULL
Link
c. Insert the input data in the data field and press –1 to stop the same.
3. Get the choice of operations either insertion or deletion.
4. For insertion get the position in which insertion is to be done and the
element to be Inserted. Check for the start, middle or end position of
insertion. Insert the node and Change its link accordingly.
5. For deletion get the position in which deletion is to be done. Delete the
node and then Link it to the next node. Before deletion check whether there
is data in the list to be deleted.
6. Using display option lists the elements of the list.
7. Stop the program.

PROGRAM:

#include<stdio.h>
#include<conio.h>
#define MAX 10
void create();
void insert();
void deletion();
void search();
void display();
int a,b[20], n, p, e, f, i, pos;
void main()
{
//clrscr();
int ch;
char g='y';
do
{
printf("\n main Menu");
printf("\n 1.Create \n 2.Delete \n 3.Search \n 4.Insert \n 5.Display\n 6.Exit \n");
printf("\n Enter your Choice");
scanf("%d", &ch);
switch(ch)
{
case 1:
create();
break;
case 2:
deletion();
break;
case 3:
search();
break;
case 4:
insert();
break;
case 5:
display();
break;
case 6:
exit();
break;
default:
printf("\n Enter the correct choice:");
}
printf("\n Do u want to continue:::");
scanf("\n%c", &g);
}
while(g=='y'||g=='Y');
getch();
}
void create()
{
printf("\n Enter the number of nodes");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\n Enter the Element:",i+1);
scanf("%d", &b[i]);
}
}
void deletion()
printf("\n Enter the position u want to delete::");
scanf("%d", &pos);
if(pos>=n)
{
printf("\n Invalid Location::");
}
else
{
for(i=pos+1;i<n;i++)
{
b[i-1]=b[i];
}
n--;
}
printf("\n The Elements after deletion");
for(i=0;i<n;i++)
{
printf("\t%d", b[i]);
}
}
void search()
{
printf("\n Enter the Element to be searched:");
scanf("%d", &e);
for(i=0;i<n;i++)
{
if(b[i]==e)
{
printf("Value is in the %d Position", i);
}
else
{
printf("Value %d is not in the list::", e);
continue;
}
}
}
void insert()
{
printf("\n Enter the position u need to insert::");
scanf("%d", &pos);
if(pos>=n)
{
printf("\n invalid Location::");
}
else
{
for(i=MAX-1;i>=pos-1;i--)
{
b[i+1]=b[i];
}
printf("\n Enter the element to insert::\n");
scanf("%d",&p);
b[pos]=p;
n++;
}
printf("\n The list after insertion::\n");
display();
}
void display()
{
printf("\n The Elements of The list ADT are:");
for(i=0;i<n;i++)
{
printf("\n\n%d", b[i]);
}
}

OUTPUT:

Main Menu
1. Create
2. Delete
3. Search
4. insert
5. Display
6. Exit
Enter Your Choice : 1
Enter the Number of Nodes : 3
Enter the Element : 1
Enter the Element : 12
Enter the Element : 23
Do you want to continue : Y
Main Menu
1. Create
2. Delete
3. Search
4. insert
5. Display
6. Exit
Enter Your Choice : 2
Enter the position you want to delete : 2
The Element after deletion : 112
Do you want to continue: Y Main Menu
1. Create
2. Delete
3. Search
4. insert
5. Display
6. Exit
Enter Your Choice : 3
Enter the Element to be Searched : 12
Value is in the Position : 1 Do you want to continue: Y Main Menu
1. Create
2. Delete
3. Search
4. Insert
5. Display
6. Exit
Enter Your Choice:4
Enter the position you need to insert:1
Enter the element to Insert:89
The list after insertion:1 89 12

Result:
Thus the C program has been executed successfully.
VIVA QUESTIONS:

1. What is an order list?

2. What is an array?
3. Give the syntax for declaring array?
4. Differentiate one dimensional and multidimensional array.
5. What is the logic used in searching the particular element in the array?
6. What will happen if in a C program you assign a value to an array element
whose subscript exceeds the size of array?
Ex.No.3a LINKED LIST IMPLEMENTATION OF LIST ADTs

AIM:
To write a program to create, insert, search and delete the element in
the list using linked list implementation.
ALGORITHM:
1. Initialize and declare variables.
2. Enter the choice.
3. If choice is INSERT then
a. Enter the element to be inserted.
b. Get a new node and set DATA[NEWNODE] = ITEM.
c. Find the node after which the new node is to be inserted.
d. Adjust the link fields.
e. Print the linked list after insertion.
4. If choice is DELETE then
a. Enter the element to be deleted.
b.Find the node containing the element (LOC) and
its preceding node (PAR).
c. Set ITEM = DATA[LOC] and delete the node LOC.
d. Adjust the link fields so that PAR points to the
next element. ie LINK[PAR] = LINK [ LOC].
e. Print the linked list after deletion.

PROGRAM :

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
void insert();
void display();
void delete();
int count();
typedef struct node DATA_NODE;
DATA_NODE *head_node, *first_node, *temp_node = 0, *prev_node,
next_node; int data;
int main() {
int option = 0;
printf("Singly Linked List Example - All Operations\n");
while (option < 5) {
printf("\nOptions\n");
printf("1 : Insert into Linked List \n");
printf("2 : Delete from Linked List \n");
printf("3 : Display Linked List\n");
printf("4 : Count Linked List\n");
printf("Others : Exit()\n");
printf("Enter your option:");
scanf("%d", &option);
switch (option) {
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
count();
break;
default:
break;
}
}
return 0;
}
void insert() {
printf("\nEnter Element for Insert Linked List :
n"); scanf("%d", &data);
temp_node = (DATA_NODE *)
malloc(sizeof(DATA_NODE)); temp_node->value =
data;
if (first_node == 0) {
first_node = temp_node;
} else {
head_node->next = temp_node;
}
temp_node->next = 0;
head_node = temp_node;
fflush(stdin);
}
void delete() {
int countvalue, pos, i = 0;
countvalue = count();
temp_node = first_node;
printf("\nDisplay Linked List : \n"); printf("\
nEnter Position for Delete Element : \n");
scanf("%d", &pos);
if (pos > 0 && pos <= countvalue) {
if (pos == 1) {
temp_node = temp_node -> next;
first_node = temp_node;
printf("\nDeleted Successfully \n\n");
} else {
while (temp_node !=
0) { if (i == (pos - 1))
{
prev_node->next = temp_node-
>next; if(i == (countvalue - 1))
{
head_node = prev_node;
}
printf("\nDeleted Successfully \n\
n"); break;
}
els
e{
i+
+;
prev_node = temp_node;
temp_node = temp_node -> next;
}
}
}
} else
printf("\nInvalid Position \n\n");
}
void
display() {
int count =
0;
temp_node = first_node;
printf("\nDisplay Linked List : \n");
while (temp_node != 0) {
printf("# %d # ", temp_node->value);
count++;
temp_node = temp_node -> next;
}
printf("\nNo Of Items In Linked List : %d\n", count);
}
int count() {
int count = 0;
temp_node = first_node;
while (temp_node != 0) {
count++;
temp_node = temp_node -> next;
}
printf("\nNo Of Items In Linked List : %d\n", count);
return count;
}

OUTPUT:
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:1
Enter Element for Insert Linked List :
100

Result:
Thus the above program has been completed successfully.
Ex.No. 3b LINKED LIST IMPLEMENTATION OF STACK ADTs

AIM:
To write a program for linked list implementation of stack
ALGORITHM:
1. Define a struct for each node in the stack. Each node in the stack contains data
and link to the next node. TOP pointer points to last node inserted in the stack.
2. The operations on the stack are
a. PUSH data into the stack b.POP data out of stack
3. PUSH DATA INTO STACK
a. Enter the data to be inserted into stack.
b. If TOP is NULL the input data is the first node in stack. the link of the
node is NULL. TOP points to that node.
c. If TOP is NOT NULL the link of TOP points to the new node. TOP
points to that node.

4. POP DATA FROM STACK

a. If TOP is NULL the stack is empty
b. If TOP is NOT NULL the link of TOP is the current TOP. the pervious
TOP is popped from stack.
5. The stack represented by linked list is traversed to display its content.

PROGRAM
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;

int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main()
{
int no, ch, e;
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Dipslay");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
create();
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
/* Create empty stack */
void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}
/* Push data into stack */
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
/* Display stack elements */
void display()
{
top1 = top;

if (top1 == NULL)
{
printf("Stack is empty");
return;
}
while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
/* Pop Operation on stack */
void pop()
{
top1 = top;

if (top1 == NULL)
{
printf("\n Error : Trying to pop from empty
stack"); return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
/* Return top element */
int topelement()
{
return(top->info);
}

/* Check if stack is empty or not */

void empty()
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}
/* Destroy entire stack */
void destroy()
{
top1 = top;

while (top1 != NULL)

{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;
printf("\n All stack elements destroyed");
count = 0;
}

OUTPUT

Enter Your Choice :

1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Dipslay
7 - Stack Count
8 - Destroy stack

Enter choice : 1
Enter data : 56

Enter choice : 1
Enter data : 80

Enter choice : 2

Popped value : 80
Enter choice : 3

Top element : 56
Enter choice : 1
Enter data : 78

Enter choice : 1
Enter data : 90

Enter choice : 6
90 78 56
Enter choice : 7

No. of elements in stack : 3

Enter choice : 8

All stack elements destroyed

Enter choice : 4

Stack is empty
Enter choice : 5

Result:

Thus the above C program has been executed successfully.

Ex.No. 3c LINKED LIST IMPLEMENTATION OF QUEUE ADTs

AIM:
To write a program to perform Front and Rear operation.
ALGORITHM:
1. Define a structure for each node in the queue. Each node in the queue contains data
and link to the next node. Front and rear pointer points to first and last node inserted in the
queue.
2. The operations on the queue are
3. a)INSERT data into the queue
4. b)DELETE data out of queue
5. INSERT DATA INTO queue
a. Enter the data to be inserted into queue.
b. If TOP is NULL, the input data is the first node in queue,the link of the node
is NULL. TOP points to that node.
c. If TOP is NOT NULL the link of TOP points to the
new node,TOP points to that node.
6. DELETE DATA FROM queue
a. If TOP is NULL the queue is empty
b. If TOP is NOT NULL the link of TOP is the
current TOP,the pervious TOP is popped from
queue.
7. The queue represented by linked list is traversed to display its
content.

PROGRAM
#include <stdio.h>
#include <stdlib.h>

struct node
{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;

int frontelement();
void enq(int data);
void deq();
void empty();
void display();
void create();
void queuesize();
int count = 0;
void main()
{
int no, ch, e;
printf("\n 1 - Enque");
printf("\n 2 - Deque");
printf("\n 3 - Front element");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Queue size");
create();
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2:
deq();
break;
case 3:
e = frontelement();
if (e != 0)
printf("Front element : %d", e);
else
printf("\n No front element in Queue as queue is
empty"); break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
queuesize();
break;
default:
printf("Wrong choice, Please enter correct choice
"); break;
}
}
}

/* Create an empty queue */

void create()
{
front = rear = NULL;
}

/* Returns queue size */

void queuesize()
{
printf("\n Queue size : %d", count);
}

/* Enqueing the queue */

void enq(int data)
{
if (rear == NULL)
{
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}
else
{
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;

rear = temp;
}
count++;
}

/* Displaying the queue elements */

void display()
{
front1 = front;

if ((front1 == NULL) && (rear == NULL))

{
printf("Queue is empty");
return;
}
while (front1 != rear)
{
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}

/* Dequeing the queue */

void deq()
{
front1 = front;
if (front1 == NULL)
{
printf("\n Error: Trying to display elements from empty
queue"); return;
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf("\n Dequed value : %d", front->info);
free(front);
front = front1;
}
else
{
printf("\n Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
count--;
}

/* Returns the front element of queue */

int frontelement()
{
if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}

/* Display if queue is empty or not */

void empty()
{
if ((front == NULL) && (rear == NULL))
printf("\n Queue empty");
else
printf("Queue not empty");
}

OUTPUT:

Enter Your Choice :

1 - Enque
2 - Deque
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size

Enter choice : 1
Enter data : 14

Enter choice : 1
Enter data : 85

Enter choice : 1
Enter data : 38

Enter choice : 3
Front element : 14
Enter choice : 6
14 85 38
Enter choice : 7

Queue size : 3
Enter choice : 2

Dequed value : 14
Enter choice : 6
85 38
Enter choice : 7

Queue size : 2
Enter choice : 4
Queue not empty
Enter choice : 5
Result:
Thus the above C program has been executed successfully.

VIVA QUESTIONS:
1. What is the difference between array and linked list?
2. How can we reduce the search time in linked list?
3. Is there possibility to reverse the single linked list?
4. How can you find the Kth node from the end of linked list that contains loop?
5. How to represent a linked list node?
Ex:No. 4a APPLICATION OF LIST ADTs

AIM:
To write a program to create the adjacency matrix of the graph representation using
queue.

ALGORITHM:

1. Start the program

2. Read the no of vertices.
3. Calculate the indegree, outdegree, Total degree of a graph.
4. Find the directed graph using dir-graph of function.
5. Find the undirected graph using undir-graph of function.
6. Read the adjacency values of a graph.
7. Stop the program

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#define new_node (struct node*)malloc(sizeof(struct node))
struct node
{
int vertex;
struct node *next;
};

void main()
{
int option;
do
{
printf("\n A Program to represent a Graph by using an Adjacency List \n ");
printf("\n 1. Directed Graph ");
printf("\n 2. Un-Directed Graph ");
printf("\n 3. Exit ");
printf("\n\n Select a proper option : ");
scanf("%d", &option);
switch(option)
{
case 1 : dir_graph();
break;
case 2 : undir_graph();
break;
case 3 : exit(0);
}
}while(1);
}
int dir_graph()
{
struct node *adj_list[10], *p;
int n;
int in_deg, out_deg, i, j;
printf("\n How Many Vertices ? : ");
scanf("%d", &n);
for( i = 1 ; i <= n ; i++ )
adj_list[i] = NULL;
read_graph (adj_list, n);
printf("\n Vertex \t In_Degree \t Out_Degree \t Total_Degree ");
for (i = 1; i <= n ; i++ )
{
in_deg = out_deg = 0;
p = adj_list[i];
while( p != NULL )
{
out_deg++;
p = p -> next;
}
for ( j = 1 ; j <= n ; j++ )
{
p = adj_list[j];
while( p != NULL )
{
if ( p -> vertex == i )
in_deg++;
p = p -> next;
}
}
printf("\n\n %5d\t\t\t%d\t\t%d\t\t%d\n\n", i, in_deg, out_deg, in_deg + out_deg);
}
return;
}
int undir_graph()
{
struct node *adj_list[10], *p;
int deg, i, j, n;
printf("\n How Many Vertices ? : ");
scanf("%d", &n);
for ( i = 1 ; i <= n ; i++ )
adj_list[i] = NULL;
read_graph(adj_list, n);
printf("\n Vertex \t Degree ");
for ( i = 1 ; i <= n ; i++ )
{
deg = 0;
p = adj_list[i];
while( p != NULL )
{
deg++;
p = p -> next;
}
printf("\n\n %5d \t\t %d\n\n", i, deg);
}
return;
}
int read_graph ( struct node *adj_list[10], int n )
{
int i, j;
char reply;
struct node *p, *c;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= n ; j++ )
{
if ( i == j )
continue;
printf("\n Vertices %d & %d are Adjacent ?
(Y/N) :", i, j); scanf("%c", &reply);
if ( reply == 'y' || reply == 'Y' )
{
c = new_node;
c -> vertex = j;
c -> next = NULL;
if ( adj_list[i] == NULL )
adj_list[i] = c;
else
{
p = adj_list[i];
while ( p -> next != NULL )
p = p -> next;
p -> next = c;
}
} } }
return;
}

OUTPUT:

A Program to represent a Graph by using an Adjacency Matrix method

1. Directed Graph
2. Un-Directed Graph
3. Exit

Select a proper option

:
How Many
Vertices ? :
Vertices 1 & 2 are Adjacent ?
(Y/N) : N
Vertices 1 & 3 are Adjacent ?
(Y/N) : Y
Vertices 1 & 4 are Adjacent ?
(Y/N) : Y
Vertices 2 & 1 are Adjacent ?
(Y/N) : Y
Vertices 2 & 3 are Adjacent ?
(Y/N) : Y
Vertices 2 & 4 are Adjacent ?
(Y/N) : N
Vertices 3 & 1 are Adjacent ?
(Y/N) : Y
Vertices 3 & 2 are Adjacent ?
(Y/N) : Y
Vertices 3 & 4 are Adjacent ?
(Y/N) : Y
Vertices 4 & 1 are Adjacent ?
(Y/N) : Y
Vertices 4 & 2 are Adjacent ?
(Y/N) : N
Vertices 4 & 3 are Adjacent ?
(Y/N) : Y
Vertex In_Degree Out_Degree Total_Degree

1 2 0 2

2 1 2 3

3 0 1 1

4 1 1 2

Result:
Thus the above C program has been executed successfully.
Ex.No.4b APPLICATIONS OF STACK ADTS

AIM:
To write the program to create the stack applications.

ALGORITHM:

1. Start the program

2. Read the no of disks.
3. Call the function using towers(num, ‘A’, ‘C’, ‘B’).
4. Move the appropriate disks from on to another.
5. Stop the program.

PROGRAM:

#include <stdio.h>
void towers(int, char, char, char);
int main()
{
int num;
printf("Enter the number of disks : ");
scanf("%d", &num);
printf("The sequence of moves involved in the Tower of Hanoi are :\n");
towers(num, 'A', 'C', 'B');
return 0;
}
void towers(int num, char frompeg, char topeg, char auxpeg)
{
if (num == 1)
{
printf("\n Move disk 1 from peg %c to peg %c", frompeg, topeg);
return;
}
towers(num - 1, frompeg, auxpeg, topeg);
printf("\n Move disk %d from peg %c to peg %c", num, frompeg, opeg);
towers(num - 1, auxpeg, topeg, frompeg);
}

OUTPUT:
Enter the number of disks : 3
The sequence of moves involved in the Tower of Hanoi are :
Move disk 1 from peg A to peg C
Move disk 2 from peg A to peg B
Move disk 1 from peg C to peg B
Move disk 3 from peg A to peg C
Move disk 1 from peg B to peg A
Move disk 2 from peg B to peg C
Move disk 1 from peg A to peg C

Result:

Thus the C Program to perform SJF Scheduling has been executed successfully.
Ex.No.4c. APPLICATIONS OF QUEUE ADTs

AIM:
To write the program to create the queue applications.

ALGORITHM:

1. Start the program.

2. Read the total number of processes.
3. Read the Burst time of all the processes.
4. Calculate the waiting time and Turnaround time.
5. Print the result.
6. Stop the program.

PROGRAM:

#include<stdio.h>
int main()
{
int n,bt[20],wt[20],tat[20],avwt=0,avtat=0,i,j;
printf("Enter total number of processes(maximum
20):"); scanf("%d",&n);

printf("\nEnter Process Burst Time\n");

for(i=0;i<n;i++)
{
printf("P[%d]:",i+1);
scanf("%d",&bt[i]);
}
wt[0]=0; //waiting time for first process is 0
//calculating waiting time
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];
}
printf("\nProcess\t\tBurst Time\tWaiting Time\tTurnaround Time");
//calculating turnaround time
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
avwt+=wt[i];
avtat+=tat[i];
printf("\nP[%d]\t\t%d\t\t%d\t\t%d",i+1,bt[i],wt[i],tat[i]);
}

avwt/=i;
avtat/=i;
printf("\n\nAverage Waiting Time:%d",avwt);
printf("\nAverage Turnaround Time:%d",avtat);

return 0;
}
OUTPUT:

Result:
Thus the C program has been executed successfully.

VIVA QUESTIONS:

1. Where are stacks used?

2. Where are queue used?
3. What is a linked list?
4. Define node structure in list.
5. Mention some applications of arrays.
Ex.No.5 IMPLEMENTATIONS OF BINARY TREE AND OPERATIONS OF BINARY
TREE

AIM:
To write the program to create the binary tree and its operations.

ALGORITHM:

1. Start the program

2. Create the nodes using insert() function.
3. Calculate inorder, preorder, postorder of the nodes using
inorder(), preorder(), postorder() function separately.
4. Print the result.
5. Stop the program.

PROGRAM:
#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)

{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}

if(val < (*tree)->data)

{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_preorder(node * tree)
{
if (tree)
{
printf("%d\n",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}
}
void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
printf("%d\n",tree->data);
print_inorder(tree->right);
}
}
void print_postorder(node * tree)
{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}
void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}
node* search(node ** tree, int val)
{
if(!(*tree))
{
return NULL;
}

if(val < (*tree)->data)

{
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
}

void main()
{
node *root;
node *tmp;
//int i;
root = NULL;
/* Inserting nodes into tree */
insert(&root, 9);
insert(&root, 4);
insert(&root, 15);
insert(&root, 6);
insert(&root, 12);
insert(&root, 17);
insert(&root, 2);

/* Printing nodes of tree */

printf("Pre Order Display\n");
print_preorder(root);

printf("In Order Display\n");

print_inorder(root);

printf("Post Order Display\n");

print_postorder(root);

/* Search node into tree */

tmp = search(&root, 4);
if (tmp)
{
printf("Searched node=%d\n", tmp->data);
}
else
{
printf("Data Not found in tree.\n");
}

/* Deleting all nodes of tree */

deltree(root);
}
OUTPUT
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
Searched node=4

Result:
Thus the C program has been executed successfully.

VIVA QUESTIONS:

1. What is a complete binary tree?

2. When is B-tree used?
3. What are the properties of red black trees?
4. What is leaf node?
5. What is the height of the binary tree?
Ex.No.6 IMPLEMENTATION OF BINARY SEARCH TREES

AIM:
To write a program that creates, search, delete and display.
ALGORITHM:
1. Declare function create(),search(),delete(),Display().
2. Create a tree with pointers for left and right sub tree.
3. Insert an element is by checking the top node and the leaf node and the
operation will be performed.
4. Deleting an element contains searching the tree and deleting the item.
5. Display the Tree elements.

PROGRAM:
#include<stdio.h>
#include<stdlib.h>
typedef struct BST
{
int data;
struct BST *left;
struct BST *right;
}node;
node *create();
void insert(node *,node *);
void preorder(node *);
int main()
{
char ch;
node *root=NULL,*temp;

do
{
temp=create();
if(root==NULL)

root=temp;
else
insert(root,temp);

printf("nDo you want to enter more(y/n)?");

getchar();
scanf("%c",&ch);
}while(ch=='y'|ch=='Y');

printf("nPreorder Traversal: ");

preorder(root);
return 0;
}

node *create()
{
node *temp;
printf("nEnter data:");
temp=(node*)malloc(sizeof(node));
scanf("%d",&temp->data);
temp->left=temp->right=NULL;
return temp;
}
void insert(node *root,node *temp)
{
if(temp->data<root->data)
{
if(root->left!=NULL)
insert(root->left,temp);
else
root->left=temp;
}
if(temp->data>root->data)
{
if(root->right!=NULL)
insert(root->right,temp);
else
root->right=temp;
}
}
void preorder(node *root)
{
if(root!=NULL)
{
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}

OUTPUT:
[com39@localhost ~]$ cd os
[com39@localhost os]$ gcc ex6.c
[com39@localhost os]$ ./a.out

Result:
Thus the C program to implement Binary search tree was executed successfully.
VIVA QUESTIONS:

1. What is the Max heap property?

2. What is a complete binary tree?
3. When is B-tree used?
4. What are the properties of red black trees?
5. If there are 'n' number s in a full binary tree, what is the height of the tree?
Ex.No. 7 IMPLEMENTATION OF AVL TREES

AIM
To write a code for implementation of AVL trees.

ALGORITHM:

1. Create a structure for tree with right and left pointers.

2. Declare the functions for insert, delete, inorder, preorder, postorder, rotate right, rotate
left operations.
3. Carry out the creation, insertion, deletion and traversal operations.
4. Do necessary rotation operation to maintain the property of AVL trees.
5. Display the tree.

PROGRAM:

#include<stdio.h>
typedef struct node
{
int data;
struct node *left,*right;
int ht;
}node;
node *insert(node *,int);
node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
int main()
{
node *root=NULL;
int x,n,i,op;

do
{
printf("\n1)Create:");
printf("\n2)Insert:");
printf("\n3)Delete:");
printf("\n4)Print:");
printf("\n5)Quit:");
printf("\n\nEnter Your Choice:");
scanf("%d",&op);
switch(op)
{
case 1: printf("\nEnter no. of elements:");
scanf("%d",&n);
printf("\nEnter tree data:");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;

case 2: printf("\nEnter a data:");

scanf("%d",&x);
root=insert(root,x);
break;

case 3: printf("\nEnter a data:");

scanf("%d",&x);
root=Delete(root,x);
break;

case 4: printf("\nPreorder sequence:\n");

preorder(root);
printf("\n\nInorder sequence:\n");
inorder(root);
printf("\n");
break;
}
}while(op!=5);

return 0;
}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x < T->left->data)
T=LL(T);
else
T=LR(T);
}

T->ht=height(T);

return(T);
}

node * Delete(node *T,int x)

{
node *p;

if(T==NULL)
{
return NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2) //Rebalance during windup
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
//data to be deleted is found
if(T->right!=NULL)
{ //delete its inorder succesor
p=T->right;

while(p->left!= NULL)
p=p->left;

T->data=p->data;
T->right=Delete(T->right,p->data);

if(BF(T)==2)//Rebalance during windup

if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);\
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}

int height(node *T)

{
int lh,rh;
if(T==NULL)
return(0);

if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);

return(rh);
}

node * rotateright(node *x)

{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);

return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}

node * LL(node *T)

{
T=rotateright(T);
return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}

node * RL(node *T)

{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}

int BF(node *T)

{
int lh,rh;
if(T==NULL)
return(0);

if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;

if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;

return(lh-rh);
}

void preorder(node *T)

{
if(T!=NULL)
{
printf("%d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}

void inorder(node *T)

{
if(T!=NULL)
{
inorder(T->left);
printf("%d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}
}
OUTPUT:

1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
Enter Your Choice:1
Enter no. of elements:4
Enter tree data:7 12 4 9
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
Enter Your Choice:4
Preorder sequence:
7(Bf=-1)4(Bf=0)12(Bf=1)9(Bf=0)
Inorder sequence:
4(Bf=0)7(Bf=-1)9(Bf=0)12(Bf=1)
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
Enter Your Choice:3
Enter a data:7
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
Enter Your Choice:4
Preorder sequence:
9(Bf=0)4(Bf=0)12(Bf=0)
Inorder sequence:
4(Bf=0)9(Bf=0)12(Bf=0)
1)Create:
2)Insert:
3)Delete:
4)Print:
5)Quit:
Enter Your Choice:5

Result:

Thus AVL has been implemented and executed successfully.

VIVA QUESTIONS:
1. What is an AVL tree?
2. How to delete a node from AVL trees?
3. What are the different types of rotations in AVL trees?
4. What is meant by balance factor?
5. What is the need for AVL trees?
Ex.No. 8 IMPLEMENTATION OF HEAPS USING PRIORITY QUEUES

AIM:
To Implement of heaps using priority queues.

ALGORITHM:

1. Start the program.

2. Create a structure for a node.
3.Declare the functions insert(),del() and display().
4.Insert a node and allocate the space dynamically using malloc().
5.Insert the priorities of the node.
6.Use pointers to reference the nodes.
7.Perform deletion operation and accordingly reference the nodes.
8.Display the nodes
9.Stop the program.

PROGRAM:
#include<stdio.h>
#include<malloc.h>
void insert();
void del();
void display();
struct node
{
int priority;
int info;
struct node *next;
}*start=NULL,*q,*temp,*new;
typedef struct node N;
int main()
{
int ch;
do
{
printf("\n[1] INSERTION\t[2] DELETION\t[3] DISPLAY [4]
EXIT\t:"); scanf("%d",&ch);
switch(ch)
{
case 1:insert();
break;
case 2:del();
break;
case 3:display();
break;
case 4:
break;
}
}
while(ch<4);
}
void insert()
{
int item,itprio;
new=(N*)malloc(sizeof(N));
printf("ENTER THE ELT.TO BE INSERTED :\t");
scanf("%d",&item);
printf("ENTER ITS PRIORITY :\t");
scanf("%d",&itprio);
new->info=item;
new->priority=itprio;
new->next=NULL;
if(start==NULL )
{
//new->next=start;
start=new;
}
else if(start!=NULL&&itprio<=start->priority)
{ new->next=start;
start=new;
}
else
{
q=start;
while(q->next != NULL && q->next-
>priority<=itprio) {q=q->next;}
new->next=q->next;
q->next=new;
}
}
void del()
{
if(start==NULL)
{
printf("\nQUEUE UNDERFLOW\n");
}
else
{
new=start;
printf("\nDELETED ITEM IS %d\n",new->info);
start=start->next;
//free(start);
}
}

void display()
{
temp=start;
if(start==NULL)
printf("QUEUE IS EMPTY\n");
else
{
printf("QUEUE IS:\n");
if(temp!=NULL)
for(temp=start;temp!=NULL;temp=temp->next)
{
printf("\n%d priority =%d\n",temp->info,temp->priority);
//temp=temp->next;
}
}
}

OUTPUT:

[1] Insertion [2] Deletion [3]Display [4] Exit

ENTER THE ELT.TO BE INSERTED: 45

ENTER ITS PRIORITY: 3
ENTER THE ELT.TO BE INSERTED: 57
ENTER ITS PRIORITY: 4
ENTER THE ELT.TO BE INSERTED: 89
ENTER ITS PRIORITY: 6
ENTER THE ELT.TO BE DELETED: 45

DISPLAY
57 Priority:4
89 Priority:6
Result:

Thus heaps using priority queue has been implemented and executed successfully.

VIVA QUESTIONS:
1. Define heaps
2. Define priority queues
3. Difference between MIN heap and MAX heap.
4. List the use of priority queues.
5. What is binary heap?
Ex.No. 9 GRAPH REPRESENTATION AND TRAVERSAL ALGORITHMS

AIM:
Graph Traversal Algorithms

ALGORITHM:

1. Start the program.

2. Get the input graph in matrix form.
3. Create the vertex and edges for a graph.
4. Declare the function dfs() and bfs() to traverse the node.
5 .Traverse the nodes using dfs() and bfs().
6. Display the output.
7. Stop the program.

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
int a[20][20],q[20],visited[20],reach[10],n,i,j,f=0,r=-1,count=0;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
}
void dfs(int v)
{
int i;
reach[v]=1;
for(i=1;i<=n;i++)
{
if(a[v][i] && !reach[i])
{
printf("\n %d->%d",v,i);
count++;

dfs(i);
}
}
}
void main()
{
int v, choice;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
for(i=1;i<=n-1;i++)
reach[i]=0;
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("1.BFS\n 2.DFS\n 3.Exit\n");
scanf("%d",&choice);
switch(choice)
{case 1: printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
if((v<1)||(v>n))
{
printf("\n Bfs is not possible");
}
else
{
printf("\n The nodes which are reachable from %d:\n",v);
for(i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
}
break;
case 2:dfs(1);
if(count==n-1)
printf("\n Graph is connected");
else
printf("\n Graph is not connected");
break;
case 3: exit(0);
}
}

OUTPUT:

Enter the number of vertices:5

Enter graph data in matrix form:

01010
10101
01010
10100
01000
1.BFS
2.DFS
3.Exit
2
1->2
2->3
3->4
2->5
Graph is connectedcsdept
Enter the number of vertices:5
Enter graph data in matrix form:
01010
10100
01010
10100
00000
1.BFS
2.DFS
3.Exit
2
1->2
2->3
3->4
Graph is not connected
Enter the number of vertices:5
Enter graph data in matrix form:
01100
00010
00000
00100
00100
1.BFS
2.DFS
3.Exit
1
Enter the starting vertex:1
The nodes which are reachable from 1:
234
Enter graph data in matrix form:
01100
00010
00000
00100
00100
1.BFS
2.DFS
3.Exit
1
Enter the starting vertex:0
BFS is not possible
Result:

Thus the graph traversal algorithms has been implemented and executed successfully.

VIVA QUESTIONS:
1. Define a graph data structure.
2. What are traversal algorithms in graph?
3. Define BFS.
4. Define DFS.
5. Give the time complexity of traversal algorithms.
Ex.No. 10 APPLICATIONS OF GRAPHS - TRAVELLING SALESMAN
PROBLEM

AIM:
To implement travelling salesman problem.

ALGORITHM:

1. Start the program.

2. Enter the number of villages to be visited.
3.Enter the cost matrix for the villages.
4.Consider village 1 as the starting and ending point. Since route is cyclic, we can consider
any point as starting point.
5.Generate all (n-1)! permutations of cities.
6.Calculate cost of every permutation and keep track of minimum cost permutation.
7.Return the permutation with minimum cost.
8.Stop the program.

PROGRAM:

#include<stdio.h>
int ary[10][10],completed[10],n,cost=0;
void takeInput()
{
int i,j;

printf("Enter the number of villages: ");

scanf("%d",&n);

printf("\nEnter the Cost Matrix\n");

for(i=0;i < n;i++)

{
printf("\nEnter Elements of Row: %d\n",i+1);

for( j=0;j < n;j++)

scanf("%d",&ary[i][j]);
completed[i]=0;
}
printf("\n\nThe cost list is:");

for( i=0;i < n;i++)

{
printf("\n");

for(j=0;j < n;j++)

printf("\t%d",ary[i][j]);
}
}

void mincost(int city)

{
int i,ncity;

completed[city]=1;

printf("%d--->",city+1);
ncity=least(city);

if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=ary[city][ncity];

return;
}
mincost(ncity);
}

int least(int c)
{
int i,nc=999;
int min=999,kmin;

for(i=0;i < n;i++)

{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i];
kmin=ary[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}

int main()
{
takeInput();

printf("\n\nThe Path is:\n");

mincost(0); //passing 0 because starting vertex

printf("\n\nMinimum cost is %d\n ",cost);

return 0;
}

OUTPUT:

Enter the number of villages: 4

Enter the Cost Matrix
Enter Elements of Row: 1
0413
Enter Elements of Row: 2
4021
Enter Elements of Row: 3
1205
Enter Elements of Row: 4
3150
The cost list is:
0413
4021
1205
3150
The Path is:
1—>3—>2—>4—>1
Minimum cost is 7

RESULT:
Thus the application of graph data structure has been implemented and executed
successfully.

VIVA QUESTIONS:

1. Define graph data structure.

2. What is meant by a vertex in graph
3. Define edges.
4. List the applications of graphs.
5. Define topological sorting.
Ex.No. 11.a IMPLEMENTATION OF SEARCHING ALGORITHM

AIM:
Implementation of Linear Search Algorithm.

ALGORITHM:

1. Start the program

2. Get an array of numbers as input.
3. Get a number as input to be searched in the array.
4. Define a loop to find the matching items in the array.
5. Repeat the loop until a match is found.
6. Stop the program.

PROGRAM:
#include <stdio.h>
void main()
{
int array[10];
int i, num, keynum, found = 0;

printf("Enter the value of num \n");

scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array is \n");
for (i = 0; i < num; i++)
{
printf("%dn", array[i]);
}
printf("Enter the element to be searched \n");
scanf("%d", &keynum);
/* Linear search begins */
for (i = 0; i < num ; i++)
{
if (keynum == array[i] )
{
found = 1;
break;
}
}
if (found == 1)
printf("Element is present in the array\n");
else
printf("Element is not present in the array\n");
}
OUTPUT:

Enter the value of num

5
Enter the elements one by one
456
78
90
40
100
Input array is
456
78
90
40
100
Enter the element to be searched
70
Element is not present in the array
Result:

Thus the Linear search algorithm has been executed successfully

Ex.No.11b IMPLEMENTATION OF SORTING ALGORITHM

AIM:
Implementation of selection sort.

ALGORITHM:

1.Start the program

2. Get an Array of numbers to be sorted.
3. Set MIN to location 0.
4. Search the minimum element in the list
5. Swap with value at location MIN
6. Increment MIN to point to next element
7. Repeat until list is sorted.
8.Stop the program
PROGRAM:
#include <stdio.h>
void selection(int [], int, int, int, int);
int main()
{
int list[30], size, temp, i, j;
printf("Enter the size of the list: ");
scanf("%d", &size);
printf("Enter the elements in list:\n");
for (i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
selection(list, 0, 0, size, 1);
printf("The sorted list in ascending order is\n");
for (i = 0; i < size; i++)
{
printf("%d ", list[i]);
}

return 0;
}

void selection(int list[], int i, int j, int size, int flag)

{
int temp;

if (i < size - 1)
{
if (flag)
{
j = i + 1;
}
if (j < size)
{
if (list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
selection(list, i, j + 1, size, 0);
}
selection(list, i + 1, 0, size, 1);
}
}

OUTPUT:

Enter the size of the list: 5

Enter the elements in list:
23
45
64
12
34
The sorted list in ascending order is
12 23 34 45 64

RESULT:
Thus the selection sort algorithm has been implemented and executed successfully.

VIVA QUESTIONS:
1. What is the need for sorting algorithm?
2. Define pivot in quick sort.
3. What is the time complexity of selection sort?
4. What is the time complexity of insertion sort?
5. What is the time complexity of quick sort?
Ex.No.12 HASHING - IMPLEMENTATION OF LINEAR PROBING

AIM:
Implementation of Linear Probing.

ALGORITHM:
1. Start the program.
2. Enter the elements of an array.
3. Declare the functions linear prob( ) and display( ).
4. Use the hash function to allocate the spot and to find the index
for record.
5. Repeat the process until collision occurs.
6. If collision occurs, call linear prob( ) function to allocate the
next available spot in "higher" index.
7. Stop the program.

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int create(int);
void linear_prob(int[], int, int);
void display (int[]);
void main()
{
int a[MAX],num,key,i;
int ans=1;
printf(" collision handling by linear probing : \n");
for (i=0;i<MAX;i++)
{
a[i] = -1;
}
do
{
printf("\n Enter the data");
scanf("%4d", &num);
key=create(num);
linear_prob(a,key,num);
printf("\n Do you wish to continue ? (1/0) ");
scanf("%d",&ans);
}while(ans);
display(a);
}
int create(int num)
{
int key;
key=num%100;
return key;
}
void linear_prob(int a[MAX], int key, int num)
{
int flag, i, count=0;
flag=0;
if(a[key]== -1)
{
a[key] = num;
}
else
{
printf("\nCollision Detected...!!!\n");
i=0;
while(i<MAX)
{
if (a[i]!=-1)
count++;
i++;
}
printf("Collision avoided successfully using LINEAR PROBING\n");
if(count == MAX)
{
printf("\n Hash table is full");
display(a);
exit(1);
}
for(i=key+1; i<MAX; i++)
if(a[i] == -1)
{
a[i] = num;
flag =1;
break;
}
//for(i=0;i<key;i++)
i=0;
while((i<key) && (flag==0))
{
if(a[i] == -1)
{
a[i] = num;
flag=1;
break;
}
i++;
}
}
}
void display(int a[MAX])
{
int i,choice;
printf("1.Display ALL\n 2.Filtered Display\n");
scanf("%d",&choice);
if(choice==1)
{
printf("\n the hash table is\n");
for(i=0; i<MAX; i++)
printf("\n %d %d ", i, a[i]);
}
else
{
printf("\n the hash table is\n");
for(i=0; i<MAX; i++)
if(a[i]!=-1)
{
printf("\n %d %d ", i, a[i]);
continue;
}
}
}

OUTPUT:

collision handling by linear probing :

Enter the data1234

Do you wish to continue ? (1/0) 1

Enter the data2548

Do you wish to continue ? (1/0) 1

Enter the data3256

Do you wish to continue ? (1/0) 1

Enter the data1299

Do you wish to continue ? (1/0) 1

Enter the data1298

Do you wish to continue ? (1/0) 1

Enter the data1398

Collision Detected...!!!
Collision avoided successfully using LINEAR PROBING
Do you wish to continue ? (1/0) 0
1.Display ALL
2.Filtered Display
2
the hash table is
0 1398
34 1234
48 2548
56 3256
98 1298
99 1299
Result:

Thus the C program has been implemented and executed successfully to resolve collision
techniques.

VIVA QUESTIONS:

1. Define hash function.

2. Draw a sample hash table.
3. Define open addressing for collision handling
4. Define separate chaining for collision handling
5. List other collision handling techniques.