Ex. No.

: 1a ARRAY IMPLEMENTATION OF STACK ADT

AIM
To write a C program to implement stack ADT using array.

ALGORITHM
Step 1: Start the program.
Step 2: For Push operation, check for stack overflow.
Step 3: If Top>=N then print stack overflow else increment Top and insert the element.
Step 4: For Pop operation, check for underflow of the stack.
Step 5: If Top=0 then print stack underflow else decrement Top and delete the element.
Step 6: Stop the program.

PROGRAM

#include <stdio.h>
#define MAXSIZE 5

struct stack
{
int stk[MAXSIZE];
int top;
};
typedef struct stack STACK;

STACK s;

void push(void);
int pop(void);
void display(void);

void main ()
{
int choice;
int option = 1;
s.top = -1;

printf ("STACK OPERATION\n");

while (option)
{
printf ("------------------------------------------\n");

printf (" 1 --> PUSH \n");

1
 printf (" 2 --> POP \n");
printf (" 3 --> DISPLAY \n");
printf (" 4 --> EXIT \n");
printf ("------------------------------------------\n");

printf ("Enter your choice\n");

scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
return;
}

fflush (stdin);
printf ("Do you want to continue(Type 0 or 1)?\n");
scanf("%d", &option);
}
}

void push ()
{
int num;
if (s.top == (MAXSIZE - 1))
{
printf ("Stack is Full\n");
return;
}
else
{
printf ("Enter the element to be pushed\n");
scanf ("%d", &num);
s.top = s.top + 1;
s.stk[s.top] = num;
}
return;
}

2
int pop ()
{
int num;
if (s.top == - 1)
{
printf ("Stack is Empty\n");
return (s.top);
}
else
{
num = s.stk[s.top];
printf ("Popped element is = %dn", s.stk[s.top]);
s.top = s.top - 1;
}
return(num);
}

void display ()
{
int i;
if (s.top == -1)
{
printf ("Stack is empty\n");
return;
}
else
{
printf ("\n The status of the stack is \n");
for (i = s.top; i >= 0; i--)
{
printf ("%d\n", s.stk[i]);
}
}
printf ("\n");
}

3
OUTPUT

STACK OPERATION
------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice 1
Enter the element to be pushed 34
Do you want to continue(Type 0 or 1)? 0

STACK OPERATION
------------------------------------------
1 --> PUSH 2
--> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice 1
Enter the element to be pushed 34
Do you want to continue(Type 0 or 1)? 1
------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice 2
Popped element is = 34
Do you want to continue(Type 0 or 1)? 1
------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice 3
Stack is empty
Do you want to continue(Type 0 or 1)? 1
------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------

4
Enter your choice 1
Enter the element to be pushed 50
Do you want to continue(Type 0 or 1)? 1
------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice
1
Enter the element to be pushed 60
Do you want to continue(Type 0 or 1)? 1
------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice 3

The status of the stack is

60
50

Do you want to continue(Type 0 or 1)? 1

------------------------------------------
1 --> PUSH
2 --> POP
3 --> DISPLAY
4 --> EXIT
------------------------------------------
Enter your choice 4

RESULT
Thus the C program for stack ADT using array was implemented and executed
successfully.

5
Ex. No. : 1b ARRAY IMPLEMENTATION OF QUEUE ADT

AIM
To write a C program to implement Queue ADT using array.

ALGORITHM
Step 1: Start the program.
Step 2: For queue insertion operation, check for queue overflow.
Step 3: If Rear>=N then print queue overflow
else increment rear pointer and insert the element.
Step 4: For queue deletion operation, check for underflow of the queue.
Step 5: If Front=0 then print queue underflow
else delete the element and increment the front pointer.
Step 6: Stop the program.

PROGRAM
#include <stdio.h>
#define MAX 50
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
int choice;
while (1)
{
printf("1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1: insert();
break;
case 2: delet();
break;
case 3: display();
break;
case 4: exit(1);
default: printf("Wrong choice \n");
}
}
}

6
insert()
{
int add_item;

if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
front = 0;

printf("Inset the element in queue : ");

scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
}

delet()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}

display()
{
int i;

if (front == - 1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}

7
OUTPUT
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Inset the element in queue : 10

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Inset the element in queue : 15

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Inset the element in queue : 20

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 10

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 3
Queue is :
15 20
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 4

RESULT
Thus the C program for Queue ADT using array was implemented and executed
successfully.

8
Ex. No. : 1c ARRAY IMPLEMENTATION OF CIRCULAR QUEUE ADT

AIM
To write a C program to implement Circular Queue ADT.

ALGORITHM
Step 1: Start the program.
Step 2: Define max as 6.
Step 3: Initialize both front and rear as -1.
Step 4: Get your choice.
Step 5: If choice is 1, Perform Enqueue operation as follows:
Step 5.1: If queue is empty, then increment both rear and front by 1 and
assign element to queue[rear].
Step 5.2: If queue is full, then display queue if overflow.
Step 5.3: Otherwise, do the following:
 rear = (rear + 1) % max.
 queue[rear] = element.
Step 6: If choice is 2, Perform Dequeue operation as follows:
Step 6.1: If queue is empty, then display queue is underflow.
Step 6.2: If front == rear, then initialize both front and rear as -1.
Step 6.3: Otherwise assign front = (front + 1) % max and display deleted element.
Step 7: If choice is 3, display the elements of queue.
Step 8: Stop the program.

PROGRAM
#include <stdio.h>
# define max 6
int queue[max];
int front = -1;
int rear = -1;

int main()
{
int choice = 1, x;

while(choice < 4 && choice != 0)

{
printf(“\n Press 1: Insert an element - Enqueue”);
printf(“\n Press 2: Delete an element - Dequeue”);
printf(“\n Press 3: Display”);
printf(“\n Enter your choice: ”);
scanf(“%d”, &choice);

9
 switch(choice)
{
case 1:
printf(“Enter the element which is to be inserted\n”);
scanf(“%d”, &x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();
}
}
return 0;
}

void enqueue(int element)

{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
queue[rear] = element;
}

else if((rear + 1) % max == front)

{
printf(“Queue is overflow\n”);
}

else
{
rear = (rear + 1) % max;
queue[rear] = element;
}
}

int dequeue()
{
if((front == -1) && (rear == -1))
{
printf(“\n Queue is underflow\n”);
}

10
 else if(front == rear)
{
printf(“\nThe dequeued element is %d”, queue[front]);
front = -1;
rear = -1;
}
else
{
printf(“\nThe dequeued element is %d”, queue[front]);
front = (front + 1) % max;
}
}

void display()
{
int i = front;

if(front == -1 && rear == -1)

{
printf(“\n Queue is empty”);
}

else
{
printf(“\n Elements in a Queue are \n”);

while(i <= rear)

{
printf(“%d\n”, queue[i]);
i = (i + 1) % max;
}
}
}

11
OUTPUT
Press 1: Insert an element - Enqueue
Press 2: Delete an element -Dequeue
Press 3: Display
Enter your choice: 1
Enter the element which is to be inserted
10

Press 1: Insert an element - Enqueue

Press 2: Delete an element -Dequeue
Press 3: Display
Enter your choice: 1
Enter the element which is to be inserted
20

Press 1: Insert an element - Enqueue

Press 2: Delete an element -Dequeue
Press 3: Display
Enter your choice: 1
Enter the element which is to be inserted
30
Press 1: Insert an element - Enqueue
Press 2: Delete an element -Dequeue
Press 3: Display
Enter your choice: 2
The dequeued element is 10

Press 1: Insert an element - Enqueue

Press 2: Delete an element -Dequeue
Press 3: Display
Enter your choice: 3
Elements in a Queue are
20
30

Press 1: Insert an element - Enqueue

Press 2: Delete an element -Dequeue
Press 3: Display
Enter your choice: 4

RESULT
Thus the C program for Circular Queue ADT using array was implemented and
executed successfully.

12
Ex. No. : 2 IMPLEMENTATION OF SINGLY LINKED LIST

AIM
To write a C program for singly linked list using list.

ALGORITHM
Step1: Start the program
Step2: Get the values for insertion into the list
Step3: Get the position of the value to be deleted
Step4: Display the values entered into the list
Step5: Display the number of items in the list
Step6: Stop the program

PROGRAM
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct node
{
int value;
struct node *next;
};
void insert();
void display();
void delet();
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");

13
 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:
delet();
break;
case 3:
display();
break;
case 4:
count();
break;
default:
printf(“\n Enter valid choice\n”);
}
}
return 0;
}

void insert()
{
printf("\nEnter Element to Insert in 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);
}

14
void delet()
{
int countvalue, pos, i = 0;
countvalue = count();
temp_node = first_node;

printf("\nEnter Position to 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;
}
else
{
i++;
prev_node = temp_node;
temp_node = temp_node -> next;
}
}
}
}

else
printf("\nInvalid Position \n\n");
}

15
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;
}

16
OUTPUT

Singly Linked List Example - All Operations

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 to Insert in Linked List : 100

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 to Insert in Linked List : 200

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 to Insert in Linked List : 300

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 to Insert in Linked List : 400

17
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 to Insert in Linked List : 500

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

Display Linked List :

# 100 # # 200 # # 300 # # 400 # # 500 #
No. of Items in Linked List : 5

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

No. of Items in Linked List : 5

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

No. of Items in Linked List : 5

Enter Position to Delete element : 3

Deleted Successfully

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

Display Linked List :

# 100 # # 200 # # 400 # # 500 #
No. of Items in Linked List : 4

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

No. of Items in Linked List : 4

Enter Position to Delete element : 6

Invalid Position

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

RESULT
Thus the C program for singly linked list using list was implemented and executed
successfully.

19
Ex. No. : 3a LINKED LIST IMPLEMENTATION OF STACK ADT

AIM
To write a c program to implement stack using linked list.

ALGORITHM
Step 1: Start the program.
Step 2: For Push operation, check for stack overflow
Step 3: If Top>=N then print stack overflow else increment Top and insert the element.
Step 4: For Pop operation, check for underflow of the stack.
Step 5: If Top=0 then print stack underflow else decrement Top and delete the element.
Step 6: Stop the program.

PROGRAM
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int Data;
struct Node *next;
}*top;
int main()
{
int i = 0;
top = NULL;
clrscr();
printf(" \n1. Push to stack");
printf(" \n2. Pop from Stack");
printf(" \n3. Display data of Stack");
printf(" \n4. Exit\n");

while(1)
{
printf(" \nChoose Option: ");
scanf("%d",&i);

switch(i)
{
case 1:
int value;
printf("\nEnter a value to push into Stack: ");
scanf("%d",&value);
push(value);
break;

20
 case 2:
popStack();
printf("\n The element is popped");
break;
case 3:
display();
break;
case 4:
struct Node *temp;
while(top!=NULL)
{
temp = top->next;
free(top);
top = temp;
}
exit(0);
default:
printf("\nwrong choice for operation");
}
}
}

void push(int value)

{
struct Node *temp;
temp = (struct Node *)malloc(sizeof(struct Node));
temp->Data = value;
if (top == NULL)
{
top = temp;
top->next = NULL;
}
else
{
temp->next = top;
top = temp;
}
}

void popStack()
{
struct Node *temp, *var = top;
if(var == top)
{
top = top->next;
free(var);
}

21
 else
printf("\nStack Empty");
}

void display()
{
struct Node *var = top;
if(var != NULL)
{
printf("\nElements are as:\n");
while(var != NULL)
{
printf("\t%d\n",var->Data);
var = var->next;
}
printf("\n");
}
else
printf("\nStack is Empty");
}

22
OUTPUT

1. Push to stack
2. Pop from Stack
3. Display data of Stack
4. Exit
Choose Option:1
Enter a value to push into Stack 5
Choose Option:1
Enter a value to push into Stack 3
Choose Option:1
Enter a value to push into Stack 2
Choose Option:1
Enter a value to push into Stack 9
Choose Option:3
Elements are as :
5
3
2
9

Choose Option:2
The element is popped
Choose Option:3
Elements are as :
5
3
2

RESULT
Thus the C program for implementation of stack using linked list was done and
executed successfully.

23
Ex. No. : 3b LINKED LIST IMPLEMENTATION OF LINEAR QUEUE ADT

AIM
To write a C program to implement queue using linked list.

ALGORITHM
Step 1: Start the program.
Step 2: For queue insertion operation, check for queue overflow
Step 3: If R>=N then print queue overflow else increment rear pointer and insert the element.
Step 4: For queue deletion operation, check for underflow of the queue.
Step 5: If F=0 then print queue underflow else delete the element and increment the front pointer
Step 6: Stop the program.

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 - Enqueue");
printf("\n 2 - Dequeue");
printf("\n 3 - Front element");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Queue size");

24
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;
}
}
}

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

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

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++;
}

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);
}

26
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 Dequeued value : %d", front->info); free(front);
front = front1;
}
else
{
printf("\n Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
count--;
}

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

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

27
OUTPUT

1 - Enqueue
2 - Dequeue
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
Dequeued 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 C program for queue using linked list was implemented and executed
successfully.

28
Ex. No. : 4 IMPLEMENTATION OF POLYNOMIAL MANIPULATION USING LINKED LIST

AIM
To write a C program to perform polynomial manipulation using linked list.

ALGORITHM
Step 1: Start the program.
Step 2: Define structure with three fields coef, expo, and link.
Step 3: Create two polynomials.
Step 4: Add two polynomials.
Step 5: Multiply two polynomials.
Step 6: Display polynomials.
Step 7: Stop the program.

PROGRAM

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

struct node
{
float coef;
int expo;
struct node *link;
};

struct node *create(struct node *);

struct node *insert_s(struct node *,float,int);
struct node *insert(struct node *,float,int);
void display(struct node *ptr);
void poly_add(struct node *,struct node *);
void poly_mult(struct node *,struct node *);

void main( )
{
struct node *start1 = NULL,*start2 = NULL;

printf("Enter polynomial 1 :\n");

start1 = create(start1);

printf("Enter polynomial 2 :\n");

start2 = create(start2);

29
 printf("Polynomial 1 is : ");
display(start1);
printf("Polynomial 2 is : ");
display(start2);
poly_add(start1, start2);
poly_mult(start1, start2);
}

struct node *create(struct node *start)

{
int i,n,ex;
float co;
printf("Enter the number of terms : ");
scanf("%d",&n);
for(i = 1; I <= n; i++)
{
printf("Enter coeficient for term %d : ",i);
scanf("%f",&co);
printf("Enter exponent for term %d : ",i);
scanf("%d",&ex);
start = insert_s(start,co,ex);
}
return start;
}

struct node *insert_s(struct node *start, float co,int ex)

{
struct node *ptr,*tmp;
tmp = (struct node *)malloc(sizeof(struct node));
tmp->coef = co;
tmp->expo = ex;

if(start == NULL || ex > start->expo)

{
tmp->link = start;
start = tmp;
}
else
{
ptr = start;
while(ptr->link != NULL && ptr->link->expo >= ex)
ptr = ptr->link;
tmp->link = ptr->link;
ptr->link = tmp;
}
return start;
}

30
struct node *insert(struct node *start, float co,int ex)
{
struct node *ptr,*tmp;
tmp = (struct node *) malloc(sizeof(struct node));
tmp->coef = co;
tmp->expo = ex;

if(start == NULL)
{
tmp->link = start;
start = tmp;
}
else
{
ptr = start;

while(ptr->link != NULL)
ptr = ptr->link;

tmp->link = ptr->link;
ptr->link = tmp;
}
return start;
}

void display(struct node *ptr)

{
if(ptr == NULL)
{
printf("Zero polynomial\n");
return;
}

while(ptr != NULL)
{
printf("(%.1fx^%d)", ptr->coef, ptr->expo);
ptr = ptr->link;

if(ptr != NULL)
printf(" + ");
else
printf("\n");
}
}

31
void poly_add(struct node *p1, struct node *p2)
{
struct node *start3;
start3 = NULL;

while(p1 != NULL && p2 != NULL)

{
if(p1->expo > p2->expo)
{
start3 = insert(start3, p1->coef, p1->expo);
p1 = p1->link;
}

else if(p2->expo > p1->expo)

{
start3 = insert(start3, p2->coef, p2->expo);
p2 = p2->link;
}

else if(p1->expo == p2->expo)

{
start3 = insert(start3, p1->coef+p2->coef, p1->expo);
p1 = p1->link;
p2 = p2->link;
}
}

while(p1 != NULL)
{
start3 = insert(start3, p1->coef, p1->expo);
p1 = p1->link;
}

while(p2 != NULL)
{
start3 = insert(start3, p2->coef, p2->expo);
p2 = p2->link;
}

printf("Added polynomial is : ");

display(start3);
}

32
void poly_mult(struct node *p1, struct node *p2)
{
struct node *start3;
struct node *p2_beg = p2;
start3=NULL;

if(p1==NULL || p2==NULL)
{
printf("Multiplied polynomial is zero polynomial\n");
return;
}

while(p1!=NULL)
{
p2 = p2_beg;

while(p2 != NULL)
{
start3 = insert_s(start3, p1->coef*p2->coef, p1->expo+p2->expo);
p2 = p2->link;
}
p1 = p1->link;
}
printf("Multiplied polynomial is : ");
display(start3);
}

33
OUTPUT

Enter polynomial 1 :
Enter the number of terms : 2
Enter coeficient for term 1 : 2
Enter exponent for term 1 : 2
Enter coeficient for term 2 : 3
Enter exponent for term 2 : 4

Enter polynomial 2 :
Enter the number of terms : 5
Enter coeficient for term 1 : 4
Enter exponent for term 1 : 3
Enter coeficient for term 2 : 2
Enter exponent for term 2 : 1
Enter coeficient for term 3 : 2
Enter exponent for term 3 : 3
Enter coeficient for term 4 : 4
Enter exponent for term 4 : 5
Enter coeficient for term 5 : 6
Enter exponent for term 5 : 3

Polynomial 1 is : (3.0x^4) + (2.0x^2)

Polynomial 2 is : (4.0x^5) + (4.0x^3) + (2.0x^3) + (6.0x^3) + (2.0x^1)

Added polynomial is : (4.0x^5) + (3.0x^4) + (4.0x^3) + (2.0x^3) + (6.0x^3) + (2.0x^2) +

(2.0x^1)

Multiplied polynomial is : (12.0x^9) + (12.0x^7) + (6.0x^7) + (18.0x^7) + (8.0x^7) + (6.0x^5) +

(8.0x^5) + (4.0x^5) + (12.0x^5) + (4.0x^3)

RESULT
Thus the C program for the implementation of Polynomial Manipulation using Linked
List was done and executed successfully.

34
Ex. No. : 5a IMPLEMENTATION OF EVALUATING POSTFIX EXPRESSIONS

AIM
To write a C program to perform evaluation of postfix expressions.

ALGORITHM
Step 1: Start the program.
Step 2: Read postfix expression.
Step 3: If input is a digit, push into stack.
Step 4: If input is an operator, then do the following:
Step 4.1: Pop top two elements from the stack.
Step 4.2: Perform respective operation between two popped elements and Push the result
into the stack.
Step 5: Repeat step 3 and 4 until the end of expression.
Step 6: Print value of evaluated expression.
Step 7: Stop the program.

PROGRAM

#include<stdio.h>

int stack[20];
int top = -1;

void push(int x)
{
stack[++top] = x;
}

int pop()
{
return stack[top--];
}

int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;

printf("Enter the expression :: ");

scanf("%s",exp);

35
 e = exp;

while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
n3 = n1 + n2;
break;
case '-':
n3 = n2 - n1;
break;
case '*':
n3 = n1 * n2;
break;
case '/':
n3 = n2 / n1;
break;
}
push(n3);
}
e++;
}
printf("\nThe result of expression %s = %d\n\n",exp,pop());
return 0;
}

OUTPUT

Enter the expression :: 245+*

The result of expression 245+* = 18

RESULT
Thus the C program for evaluating postfix expressions was implemented and executed
successfully.

36
Ex. No. : 5b IMPLEMENTATION OF INFIX TO POSTFIX CONVERSION

AIM

To write a C program to convert the infix expression into postfix expression using stack.

ALGORITHM

Step 1: Start the program.

Step 2: Get the infix expression as input.
Step 3: Read the input from left to right.
Step 4: If the input is operand then place it in the postfix expression.
Step 5: Else if the input symbol is an operator then check for the operator type and also the
precedence, pop entries from the stack and place them in the postfix expression until
the lowest priority operator is encountered.
Step 6: “(” symbol will be popped from stack only when we get a “)” symbol.
Step 7: When the input is completely read then pop the elements in stack until it becomes empty.
Step 8: Display the postfix expression.
Step 9: Stop the program.

PROGRAM

#include<stdio.h>
char stack[20];
int top = -1;

void push(char x)
{
stack[++top] = x;
}

char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}

int priority(char x)
{
if(x == '(')
return 0;

37
 if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
}

main()
{
char exp[20]; char *e, x;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isalnum(*e))
printf("%c",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c", x);
}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c",pop());
push(*e);
}
e++;
}

while(top != -1)
{
printf("%c",pop());
}
}

OUTPUT

Enter the expression :: a+b*c abc*+

Enter the expression :: (a+b)*c+(d-a) ab+c*da-+

RESULT
Thus the C program to convert the infix expression into postfix expression using
stack has been implemented successfully.

38
Ex. No. : 6 IMPLEMENTATION OF BINARY SEARCH TREES

AIM

To write a C program to construct a binary search tree and perform various operations.

ALGORITHM

Algorithm for INSERT(X,P)

1. if(P==NULL)
t=(struct treenode *)malloc(sizeof(struct treenode));
2. else
t->element=x;
t->left=t->right=NULL;
3. else if(x<t->element)
t->left=insert(x,t->left);
4. else if(x>t->element)
t->right=insert(x,t->right); return t;

Algorithm For INORDER(P)

1. If(P!=Null)
2. CALL INORDER (P→lchild)
3. WRITE (P→data)
4. CALL INORDER (P→rchild)
5. [End the function]

Algorithm for PREORDER(P)

1. If (P! =NULL)
2. WRITE (P->Data)
3. CALL PREORDER (P→lchild)
4. CALL PREORDER (P→ rchild)
5. [END OF FUNTION]

Algorithm for POSTORDER(P)

1. If (P!=NULL)
2. Call POSTORDER (P→lchild)
3. Call POSTORDER (P→rchild)
4. Write (P→data)
5. [End of function]

39
Algorithm for COUNT
1. If (P==NULL)
2. Return 0
3. Else
4. Return (1+count(P→lchild)+call count(P→rchild))

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

#define NULL 0
struct treenode
{
int element;
struct treenode *left;
struct treenode *right;
};
typedef struct treenode *position, *searchtree;
searchtree insert(int x, searchtree t)
{
if(t == NULL)
{
t = (struct treenode *)malloc(sizeof(struct treenode));
if(t == NULL)
exit(0);
else
{
t->element = x;
t->left = t->right = NULL;
}
}
else if(x < t->element)
t->left = insert(x, t->left);
else if(x > t->element)
t->right = insert(x, t->right);
return t;
}

position findmin(searchtree t)
{
if(t == NULL)
return NULL;
else
return findmin(t->left);
}

40
position findmax(searchtree t)
{
if(t == NULL)
return NULL;
else if(t->right == NULL)
return t;
else
return findmax(t->right);
}

searchtree rem(int x, searchtree t)

{
position temp;
if(t == NULL)
printf("\n Element not found\t");
else if(x < t->element)
t->left = rem(x, t->left);
else if(x > t->element)
t->right = rem(x, t->right);
else if(t->left && t->right)
{
temp = findmin(t->right);
t->element = temp->element;
t->right = rem(t->element, t->right);
}
else
{
temp = t;
if(t->left == NULL)
t = t->right;
else if(t->right == NULL)
t = t->left;
free(temp);
}
return t;
}

void intrav(searchtree head)

{
if(head == NULL)
return;
if(head->left != NULL)
intrav(head->left);
printf("%d\t", head->element);
if(head->right != NULL)
intrav(head->right);
}

41
void main()
{
int n,i,dat,ch;
searchtree t = NULL;
position node;
printf("\nElement no. of elements:\t");
scanf("%d",&n);
printf("\nEnter the elements:\t");
for(i=1; i<=n; i++)
{
scanf("%d",&dat);
t = insert(dat,t);
}
intrav(t);
do
{
printf("\n****MENU****\n");
printf("1->Insert a node \n");
printf("2->Delete a node \n");
printf("3->Find Minimum\n");
printf("4->Find Maximum\n");
printf("5->Display (Inorder Traversal)\n");
printf("6->Exit\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n Enter the element to be inserted:\t");
scanf("%d",&dat);
t=insert(dat,t);
break;
case 2: printf("\n Enter the node to be deleted:\t");
scanf("%d",&dat);
t=rem(dat,t);
break;
case 3: node=findmin(t);
printf("\nThe minimum element is %d",node->element);
break;
case 4: node=findmax(t);
printf("\n The maximum element is %d",node->element); break;
case 5: intrav(t); break;
case 6: exit(0);
}
}
while(ch!=6);
}

42
OUTPUT
Enter no. of elements: 3
Enter the elements:
5
2
9
259

****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display (Inorder Traversal)
6->Exit
Enter your choice:1
Enter the element to be inserted: 4

****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display (Inorder Traversal)
6->Exit
Enter your choice:1
Enter the element to be inserted:6

****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display (Inorder Traversal)
6->Exit
Enter your choice:2
Enter the element to be deleted:5

****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display(Inorder Traversal)
6->Exit
Enter your choice: 5
2 4 6 9

43
****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display (Inorder Traversal)
6->Exit

Enter your choice:3

The minimum element is: 2

****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display (Inorder Traversal)
6->Exit

Enter your choice:4

The maximum element is:9

****MENU****
1->Insert a node
2->Delete a node
3->Find Minimum
4->Find Maximum
5->Display (Inorder Traversal)
6->Exit

Enter your choice:6

RESULT
Thus the C program to construct a binary search tree and perform various operations
has been executed successfully.

44
Ex. No. : 7 IMPLEMENTATION OF AVL TREES

AIM
To write a C program for the implementation of AVL trees.

ALGORITHM
Step 1: Start the program.
Step 2: Declare all the functions and using the switch case select the operation to be performed.
Step 3: Declare a structure with all the required variables and allocate the memory using the
malloc function.
Step 4: Check if (search(root, info) == NULL), if so assign the value to the variable root .
Step 5: Insert an element into the tree.
Step 6: After insertion check if the tree is balanced or not .If not balance the tree.
Step 7: Stop the program.

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;

45
 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;
}

46
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)
{
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)
{
T->right = Delete(T->right, x);
if(BF(T) == 2)
T = LL(T);
else
T = LR(T);
}

47
 else if(BF(T->left) >= 0)
T = LL(T);
else
T = LR(T);
if(x < T->data)
{
T->left = Delete(T->left, x);
if(BF(T) == -2)
if(BF(T->right) <= 0)
T = RR(T);
else
T = RL(T);
}
else
{
if(T->right!=NULL)
{
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)
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;

48
 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);
}

49
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);
}
}

50
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:5

RESULT
Thus the C program for the implementation of AVL trees has been executed
successfully.

51
Ex. No. : 8 IMPLEMENTATION OF HEAPS USING PRIORITY QUEUES

AIM

To write a C program for the implementation of heaps using priority queues.

ALGORITHM

Step 1: Start the program

Step 2: Declare the necessary variables
Step 3: Write the functions for Insert, Delete, Display and Exit
Step 4: Do the deletion for the higher order element and display it.
Step5: End the program

PROGRAM

#include<stdio.h>
#include<math.h>

#define MAX 100

void swap(int*,int*);

void main()
{
int choice, num, n, a[MAX], data, s;
void display(int[], int);
void insert(int[], int, int, int);
int del_hi_priori(int[], int, int);

int lb = 0;
n = 0;

while(1)
{
printf(".....MAIN MENU.....\n");
printf("\n1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");

printf("\nEnter your choice : ");

scanf("%d",&choice);

52
 switch(choice)
{
case 1:
printf("Enter data to be inserted : ");
scanf("%d",&data);
insert(a,n,data,lb);
n++;
break;
case 2:
s=del_hi_priori(a,n+1,lb);
if(s!=0)
printf("\nThe deleted value is : %d \n",s);
if(n>0)
n--;
break;
case 3:
printf("\n");
display(a,n);
break;
case 4:
return;
default:
printf("Invalid choice \n");
}
printf("\n\n");
}
}

void insert(int a[], int heapsize, int data, int lb)

{
int i,p;
int parent(int);
if(heapsize == MAX)
{
printf("Queue Is Full!!\n");
return;
}
i = lb + heapsize;
a[i] = data;

while(i > lb && a[p = parent(i)] < a[i])

{
swap(&a[p], &a[i]);
i = p;
}
}

53
int del_hi_priori(int a[], int heapsize, int lb)
{
int data,i,l,r,max_child,t;
int left(int);
int right(int);

if(heapsize == 1)
{
printf("Queue is Empty!!\n");
return 0;
}

t = a[lb];
swap(&a[lb], &a[heapsize-1]);
i = lb;
heapsize--;

while(1)
{
if((l = left(i)) >= heapsize)
break;
if((r = right(i)) >= heapsize)
max_child = l;
else
max_child = (a[l] > a[r]) ? l : r;

if(a[i] >= a[max_child])

break;

swap(&a[i], &a[max_child]);
i = max_child;
}
return t;
}

int parent(int i)
{
float p;
p = ((float) i / 2.0) - 1.0;
return ceil(p);
}

int left(int i)
{
return 2 * i + 1;
}

54
int right(int i)
{
return 2 * i + 2;
}

void display(int a[], int n)

{
int i;
if(n == 0)
{
printf("Queue Is Empty!!\n");
return;
}
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
}

void swap(int*p, int*q)

{
int temp;
temp=*p;
*p=*q;
*q=temp;
}

55
OUTPUT

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 1

Enter data to be inserted : 52

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 1
Enter data to be inserted : 63

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 1

Enter data to be inserted : 45

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 1

Enter data to be inserted : 2

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 1

Enter data to be inserted : 99

56
.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 3

99 63 45 2 52

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 2

The deleted value is : 99

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.

Enter your choice : 3

63 52 45 2

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
.
Enter your choice : 4

RESULT
Thus the C program for the implementation of heaps using priority queues has been
executed successfully.

57
Ex. No. : 9 IMPLEMENTATION OF DIJKSTRA’S ALGORITHM

AIM

To write a C program for finding shortest path (minimum number of vertices) on the given
source of graph using Dijkstra’s algorithm.

ALGORITHM

Step 1: Create cost matrix C[ ][ ] from adjacency matrix adj[ ][ ]. C[i][j] is the cost of going from
vertex i to vertex j. If there is no edge between vertices i and j then C[i][j] is infinity.
Step 2: Array visited[ ] is initialized to zero as follows:
for(i=0;i<n;i++)
visited[i]=0;
Step 3: If the vertex 0 is the source vertex then visited[0] is marked as 1.
Step 4: Create the distance matrix, by storing the cost of vertices from vertex no. 0 to n-1
from the source vertex 0 as follows:
for(i=1;i<n;i++)
distance[i]=cost[0][i];
Step 5: Initially, distance of source vertex is taken as 0. i.e. distance[0]=0;
Step 6: for(i=1;i<n;i++)
– Choose a vertex w, such that distance[w] is minimum and visited[w] is 0.
Mark visited[w] as 1.
– Recalculate the shortest distance of remaining vertices from the source.
– Only, the vertices not marked as 1 in array visited[ ] should be considered for
recalculation of distance. i.e. for each vertex v
if(visited[v]==0)
distance[v]=min(distance[v], distance[w]+cost[w][v])

PROGRAM

#include<stdio.h>

#define INFINITY 9999

#define MAX 10

void dijkstra(int G[MAX][MAX], int n, int startnode);

int main()
{
int G[MAX][MAX],i,j,n,u;
printf("Enter no. of vertices: ");
scanf("%d", &n);

58
 printf("\nEnter the adjacency matrix:\n");
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &G[i][j]);
printf("\nEnter the starting node: ");
scanf("%d",&u);
dijkstra(G,n,u);
return 0;
}

void dijkstra(int G[MAX][MAX], int n, int startnode)

{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i, j;

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

for(j = 0; j <n ; j++)
if(G[i][j] == 0)
cost[i][j] = INFINITY;
else
cost[i][j] = G[i][j];

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

{
distance[i] = cost[startnode][i];
pred[i] = startnode;
visited[i] = 0;
}

distance[startnode] = 0;
visited[startnode] = 1;
count = 1;

while(count < n-1)

{
mindistance = INFINITY;

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

if(distance[i] < mindistance && !visited[i])
{
mindistance = distance[i];
nextnode = i;
}
visited[nextnode] = 1;

59
 for(i = 0; i < n; i++)
if(!visited[i])
if(mindistance + cost[nextnode][i] < distance[i])
{
distance[i] = mindistance + cost[nextnode][i];
pred[i] = nextnode;
}
count++;
}

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

if(i != startnode)
{
printf("\nDistance of node%d=%d", i, distance[i]);
printf("\nPath=%d", i);
j = i;
do
{
j = pred[j];
printf("<-%d", j);
}while( j != startnode );
}
}

OUTPUT
Enter no. of vertices: 5
Enter the adjacency matrix:
0 10 0 30 100
10 0 50 0 0
0 50 0 20 10
30 0 20 0 60
100 0 10 60 0
Enter the starting node: 0
Distance of node1=10
Path=1<-0
Distance of node2=50
Path=2<-3<-0
Distance of node3=30
Path=3<-0
Distance of node4=60
Path=4<-2<-3<-0

RESULT
Thus the C program for finding minimum distance of vertices on the given source in a
graph using Dijkstra's algorithm has been implemented and executed successfully.

60
Ex. No. : 10 IMPLEMENTATION OF PRIM’S ALGORITHM

AIM
To write a C program for finding minimum spanning tree[MST] using Prim's algorithm.

ALGORITHM
Step 1. Create a set mstSet that keeps track of vertices already included in MST.
Step 2. Assign a key value to all vertices in the input graph. Initialize all key values as
INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
Step 3. While mstSet does not include all vertices
Step 3.1. Pick a vertex u which is not there in mstSet and has minimum key value.
Step 3.2. Include u to mstSet.
Step 3.3. Update key value of all adjacent vertices of u. To update the key values, iterate
through all adjacent vertices.
For every adjacent vertex v,
if weight of edge u-v is less than the previous key value of v,
update the key value as weight of u-v
PROGRAM
#include <limits.h>
#include <bool.h>
#include <stdio.h>
#define V 55
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
primMST(graph);
return 0;
}
int minKey(int key[], bool mstSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
{
min = key[v];
min_index = v;
}
return min_index;
}

61
int printMST(int parent[], int graph[V][V])
{
printf(“Edge \tWeight\n”);
for (int i = 1; i < V; i++)
printf(“%d - %d \t%d \n”, parent[i], i, graph[i][parent[i]]);
}

void primMST(int graph[V][V])

{
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
{
key[i] = INT_MAX;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++)
{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
printMST(parent, graph);
}

OUTPUT

Edge Weight
0-12
1-23
0-36
1-45

RESULT
Thus the C program for finding minimum spanning of trees using Prim's algorithm
was successfully implemented and executed.

62
Ex. No. : 11a IMPLEMENTATION OF LINEAR SEARCH

AIM
To write a C program to implement Linear Search.

ALGORITHM
Step 1. Start the program
Step 2. Initialize i,j,,n,a[20],size
Step 3. Read the size of sorting numbers size
Step 4. Read the elements of the array
Step 5. Read the element to be searched n
Step 6. Using for(i=0;i<size;i++), If it is true then
Step 6.1. Check the condition, if(n==array[i]) if it is true go to next step,
else go to step 6.
Step 6.2. Display the element is found and terminate the for loop
Step 7. if i==size, then display element is not found
Step 8. Stop the program

PROGRAM

#include <stdio.h>

int main()
{
int a[20], i, j, n, size;

printf("Linear Search\n");

printf("Enter the size of the list:");

scanf("%d", &size);

printf("Enter %d Integers \n", size);

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

scanf("%d", &a[i]);

printf("Enter value to find\n");

scanf("%d", &n);

linear_search(a, size, n);

return 0;
}

63
void linear_search(int array[], int size, int n)
{
int i;

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

{
if (array[i] == n)
{
printf("%d found at location %d.\n", n, i+1);
break;
}
}

if (i == size)
printf("Not found! %d is not present in the list.\n", n);
}

OUTPUT

Linear Search

Enter the size of the list:10

Enter 10 Integers 12 5 8 22 16 25 11 45 78 55

Enter value to find 16

16 found at location 5.

RESULT
Thus the C program to perform linear search has been implemented and executed
successfully.

64
Ex. No. : 11b IMPLEMENTATION OF BINARY SEARCH

AIM
To write a C program to implement Binary Search.

ALGORITHM

Step 1. Start the program

Step 2. Initialize i,j,,n,a[20],size
Step 3. Read the size of sorting numbers size
Step 4. Read the elements of the array in ascending order
Step 5. Read the element to be searched n
Step 6. Initialize first =0, last = size-1
Step 7. Calculate middle as (first+last) / 2
Step 8. If first <= last, then do the following:
Step 8.1 If array[middle] == n then display element is found and terminate while the loop
Step 8.2 If array[middle] > n then last = middle – 1 and repeat step 8
Step 8.3 If array[middle] < n then first = middle + 1 and repeat step 8
Step 8.4 Update middle as (first + last) / 2
Step 9: If first > last, then display element is not found
Step 10. Stop the program

PROGRAM
#include <stdio.h>

int main()
{
int a[20], i, j, n, size;

printf("Binary Search\n");

printf("Enter the size of the list:");

scanf("%d", &size);

printf("Enter %d Integers in ascending order\n", size);

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

scanf("%d", &a[i]);

printf("Enter value to find\n");

scanf("%d", &n);

binary_search(a, size, n);

return 0;
}

65
void binary_search(int array[], int size, int n)
{
int i, first, last, middle;

first = 0;
last = size - 1;
middle = (first+last) / 2;

while (first <= last)

{
if (array[middle] < n)
first = middle + 1;
else if (array[middle] == n)
{
printf("%d found at location %d.\n", n, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last) / 2;

}

if ( first > last )

printf("Not found! %d is not present in the list.\n", n);
}

OUTPUT

Binary Search

Enter the size of the list:10

Enter 10 Integers 2 5 8 12 16 25 31 45 48 55

Enter value to find 16

16 found at location 5.

RESULT
Thus the C program to perform binary search has been implemented and executed
successfully.

66
Ex. No. : 12a IMPLEMENTATION OF INSERTION SORT

AIM

To write a C program for sorting an array of N numbers using Insertion Sort.

ALGORITHM

Step 1. Start the program

Step 2. Initialize arr[max],i,j,tmp,n,p
Step 3. Read the number of elements from the user
Step 4. Read the elements
Step 5. Display the unsorted elements to the user
Step 6. Invoke function call insertionsort(arr,n)
Step 6.1 In function block, using for loop, for(p=1;p<n;p++)
Step 6.2 Initialize tmp=a[p]
Step 6.3 for(j=p; j>0 && a[j-1] > tmp; j--), if it is true go to next step, else go to step 6.5
Step 6.4 Assign a[j]=a[j-1]
Step 6.5 Assign a[j]=tmp
Step 7. Display sorted list to the user
Step 8. Stop the program

PROGRAM
#include<stdio.h>

void insertionsort(int[], int);

#define max 20

void main()
{
int arr[max],i,j,tmp,n,p;

printf(“\n enter the size of the sorting”);

scanf(“%d”,&n);

for(i=0;i<n;i++)
{
printf(“\n Enter element %d”, i+1);
scanf(“%d”,&arr[i]);
}

printf(“unsorted list are:”);

67
 for(i = 0;i < n; i++)
printf(“%d \t”, arr[i]);

insertionsort(arr, n);

printf(“sorted list:”);

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

printf(“%d\t”, arr[i]);
}

void insertionsort(int a[], int n)

{
int p,j,tmp;

for( p = 1; p < n; p++)

{
tmp = a[p];

for( j = p; j > 0 && a[ j -1 ] > tmp; j--)

a[j] = a[j-1];
a[j] = tmp;
}
}

OUTPUT

Enter the number of elements: 5

Enter element 1: 8
Enter element 2: 5
Enter element 3: 1
Enter element 4: 3
Enter element 5: 4

Unsorted list are: 8 5 1 3 4

Sorted list are: 1 3 4 5 8

RESULT
Thus the C program for sorting an array of N numbers using insertion sort has been
executed successfully.

68
Ex. No. : 12b IMPLEMENTATION OF SELECTION SORT

AIM
To write a C program for sorting an array of N numbers using Selection Sort.

ALGORITHM

Step 1. Start the program

Step 2. Initialize a[max],i,j,n
Step 3. Read the number of elements from the user
Step 4. Read the elements
Step 5. Display the unsorted elements to the user
Step 6. Invoke function call selectionsort(a,n)
Step 6.1 In function block, using for loop for(i=0;i<n-1;i++)
Step 6.2 index=i;
Step 6.3 using for loop, for(j=i+1;j<n;j++)
Step 6.4 if(a[j]<a[index]), if it is true go to next step else go to step 6.6.
Step 6.5 index=j;
Step 6.6 Swap
smallno=a[index];
a[index]=a[i];
a[i]=smallno;
Step 7. Display sorted list to the user
Step 8. Stop the program

PROGRAM
#include<stdio.h>

void selectionsort(int[], int);

#define max 20

void main()
{
int a[max],i,j,n;

printf(“\n enter the size of the sorting”);

scanf(“%d”, &n);

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

{
printf(“\n Enter element %d”, i+1);
scanf(“%d”, &a[i]);
}

69
 printf(“unsorted list are:”);

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

printf(“%d \t”, a[i]);

selectionsort(a,n);

printf(“sorted list: ”);

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

printf(“%d\t”, a[i]);
}

void selectionsort(int a[], int n)

{
int i,j,index,smallno;

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

{
index=i;

for( j = i + 1; j < n; j++)

if(a[j] < a[index])
index = j;

smallno = a[index];
a[index] = a[i];
a[i] = smallno;
}
}

OUTPUT

Enter the number of elements: 5

Enter element 1: 8
Enter element 2: 5
Enter element 3: 1
Enter element 4: 3
Enter element 5: 4
Unsorted list are: 8 5 1 3 4
Sorted list are: 1 3 4 5 8

RESULT
Thus the C program for sorting an array of N numbers using selection sort has been
executed successfully.

70
Ex. No. : 13 IMPLEMENTATION OF MERGE SORT

AIM
To write a C program for sorting an array of N numbers using Merge Sort.

ALGORITHM

Step 1. Read number of elements n to sort

Step 2. Read n number of elements
Step 3. Calculate mid = (i + j) / 2
Step 4. merge_sort(i, mid, a, aux)
Step 5. merge_sort(mid + 1, j, a, aux)
Step 6. pointer_left = i, pointer_right = mid + 1
Step 7. for k in [i ... j]
if pointer_left points to smaller element,
aux[k] = a[pointer_left] and
increment pointer_left by 1
if pointer_right points to smaller element,
aux[k] = a[pointer_right] and
increment pointer_right by 1
copy the contents of aux[i .. j] to a[i .. j]
Step 8. Print sorted numbers

PROGRAM

#include <stdio.h>

int merge_sort(int i, int j, int a[], int aux[])

{
if (j <= i)
{
return 0;
}

int mid = (i + j) / 2;

merge_sort(i, mid, a, aux);

merge_sort(mid + 1, j, a, aux);

int pointer_left = i;
int pointer_right = mid + 1;
int k;

71
 for (k = i; k <= j; k++)
{
if (pointer_left == mid + 1)
{
aux[k] = a[pointer_right];
pointer_right++;
}
else if (pointer_right == j + 1)
{
aux[k] = a[pointer_left];
pointer_left++;
}
else if (a[pointer_left] < a[pointer_right])
{
aux[k] = a[pointer_left];
pointer_left++;
}
else
{
aux[k] = a[pointer_right];
pointer_right++;
}
}
for (k = i; k <= j; k++)
{
a[k] = aux[k];
}
}

int main()
{
int a[100], aux[100], n, i, d, swap;
printf("Enter number of elements in the array:\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);

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

scanf("%d", &a[i]);

merge_sort(0, n - 1, a, aux);

printf("Printing the sorted array:\n");

for (i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}

72
OUTPUT

Enter number of elements in the array: 5

Enter 5 integers

12

456

67

Printing the sorted array:

12

67

456

RESULT
Thus the C program for sorting an array of N numbers using Merge Sort has been
executed successfully.

73
Ex. No. : 14a IMPLEMENTATION OF OPEN ADDRESSING (LINEAR PROBING)

AIM

To write a C program to implement Open Addressing (Linear Probing).

ALGORITHM

Step 1. Create an array of structure (i.e a hash table).

Step 2. Take a key and a value to be stored in hash table as input.
Step 3. Corresponding to the key, an index will be generated.
Step 4. Using the generated index, access the data located in that array index.
Step 5. In case of absence of data, create one and insert the data item (key and value) into it and
Increment the size of hash table.
Step 6. In case the data exists, probe through the subsequent elements (looping back if necessary)
for free space to insert new data item.
Step 7. Display all the elements of hash table, element at each index is accessed (via for loop).
Step 8. Remove a key from hash table is done as follows, we will first calculate its index and
delete it if key matches, else probe through elements until we find key or an empty space
where not a single data has been entered (means data does not exist in the hash table).

PROGRAM

#include <stdio.h>

int tsize;

int hasht(int key)

{
int i ;
i = key%tsize ;
return i;
}

//-------LINEAR PROBING-------
int rehashl(int key)
{
int i ;
i = (key+1)%tsize ;
return i ;
}

74
void main()
{
int key,arr[20],hash[20],i,n,s,op,j,k ;

printf ("Enter the size of the hash table: ");

scanf ("%d",&tsize);
printf ("\nEnter the number of elements: ");
scanf ("%d",&n);
for (i=0;i<tsize;i++)
hash[i] = -1 ;
printf ("Enter Elements: ");
for (i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}

for (i=0;i<tsize;i++)
hash[i] = -1 ;

for(k=0;k<n;k++)
{
key=arr[k] ;

i = hasht(key);

while (hash[i] != -1)

{
i = rehashl(i);
}
hash[i]=key ;
}

printf("\nThe elements in the array are: ");

for (i=0;i<tsize;i++)
{
printf("\n Element at position %d: %d",i,hash[i]);

}
}

75
OUTPUT
Enter the size of the hash table: 10
Enter the number of elements: 8
Enter Elements: 72 27 36 24 63 81 92 101

The elements in the array are:

Element at position 0: -1
Element at position 1: 81
Element at position 2: 72
Element at position 3: 63
Element at position 4: 24
Element at position 5: 92
Element at position 6: 36
Element at position 7: 27
Element at position 8: 101
Element at position 9: -1

RESULT
Thus the C program to implement open addressing (Linear Probing) has been done
and executed successfully.

76
Ex. No. :14b IMPLEMENTATION OF OPEN ADDRESSING (QUADRATIC PROBING)

AIM

To write a C program to implement Open Addressing (Quadratic Probing).

ALGORITHM

Step 1. Create an array of structure (i.e., a hash table).

Step 2. Take a key and a value to be stored in hash table as input.
Step 3. Corresponding to the key, an index will be generated.
Step 4. Using the generated index, access the data located in that array index.
Step 5. In case of absence of data, create one and insert the data item (key and value) into it and
Increment the size of hash table.
Step 6. In case the data exists, probe through the subsequent elements using this calculation
(key+(j*j))%tsize to find free space to insert new data item.
Step 7. Display all the elements of hash table, element at each index is accessed (via for loop).
Step 8. Remove a key from hash table is done as follows, we will first calculate its index and
delete it if key matches, else probe through elements until we find key or an empty space
where not a single data has been entered (means data does not exist in the hash table).

PROGRAM

#include <stdio.h>

int tsize;

int hasht(int key)

{
int i ;
i = key%tsize ;
return i;
}

//-------QUADRATIC PROBING-------
int rehashq(int key, int j)
{
int i ;
i = (key+(j*j))%tsize ;
return i ;
}

77
void main()
{
int key,arr[20],hash[20],i,n,s,op,j,k ;

printf ("Enter the size of the hash table: ");

scanf ("%d",&tsize);

printf ("\nEnter the number of elements: ");

scanf ("%d",&n);

for (i=0;i<tsize;i++)
hash[i] = -1 ;

printf ("Enter Elements: ");

for (i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}

for (i=0;i<tsize;i++)
hash[i]=-1 ;

for(k=0;k<n;k++)
{
j=1;
key=arr[k] ;
i = hasht(key);
while (hash[i] != -1)
{
i = rehashq(i,j);
j++;
}
hash[i]=key ;
}

printf("\nThe elements in the array are: ");

for (i=0;i<tsize;i++)
{
printf("\n Element at position %d: %d",i,hash[i]);
}
}

78
OUTPUT
Enter the size of the hash table: 10
Enter the number of elements: 8
Enter Elements: 72 27 36 24 63 81 92 101

The elements in the array are:

Element at position 0: -1
Element at position 1: 81
Element at position 2: 72
Element at position 3: 63
Element at position 4: 24
Element at position 5: 101
Element at position 6: 36
Element at position 7: 27
Element at position 8: 92
Element at position 9: -1

RESULT
Thus the C program to implement open addressing (Quadratic Probing) has been done
and executed successfully.

79
Ex. No. : 15 IMPLEMENTATION OF DEQUEUE

AIM

To write a C program to implement DeQueue.

ALGORITHM

Insertion at the front end

 If the queue is empty, both rear and front are initialized with 0. Now, both will point to
the first element.
 Otherwise, check the position of the front if the front is less than 1 (front < 1), then
reinitialize it by front = n - 1, i.e., the last index of the array.

Insertion at the rear end

 If the queue is empty, both rear and front are initialized with 0. Now, both will point to
the first element.
 Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead of
increasing it by 1, we have to make it equal to 0.

Deletion at the front end

 If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot
perform the deletion. If the queue is not full, then the element can be inserted from the
front end by using the below conditions -
 If the deque has only one element, set rear = -1 and front = -1.
 Else if front is at end (that means front = size - 1), set front = 0.
 Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

 If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot
perform the deletion.
 If the deque has only one element, set rear = -1 and front = -1.
 If rear = 0 (rear is at front), then set rear = n - 1.
 Else, decrement the rear by 1 (or, rear = rear -1).

Check empty
 If front = -1, it means that the deque is empty.

Check full
 If front = rear + 1, or front = 0 and rear = n - 1 it means that the deque is full.

80
PROGRAM

#include <stdio.h>

#define size 5

int deque[size];

int f = -1, r = -1;

void insert_front(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{
f=r=0;
deque[f]=x;
}
else if(f==0)
{
f=size-1;
deque[f]=x;
}
else
{
f=f-1;
deque[f]=x;
}
}

void insert_rear(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{
r=0;
deque[r]=x;
}

81
 else if(r==size-1)
{
r=0;
deque[r]=x;
}
else
{
r++;
deque[r]=x;
}

void display()
{
int i=f;
printf("\nElements in a deque are: ");

while(i!=r)
{
printf("%d ",deque[i]);
i=(i+1)%size;
}
printf("%d",deque[r]);
}

void getfront()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at front is: %d", deque[f]);
}

void getrear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}

82
else
{
printf("\nThe value of the element at rear is %d", deque[r]);
}

void delete_front()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[f]);
f=-1;
r=-1;

}
else if(f==(size-1))
{
printf("\nThe deleted element is %d", deque[f]);
f=0;
}
else
{
printf("\nThe deleted element is %d", deque[f]);
f=f+1;
}
}

void delete_rear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[r]);
f=-1;
r=-1;

83
 else if(r==0)
{
printf("\nThe deleted element is %d", deque[r]);
r=size-1;
}
else
{
printf("\nThe deleted element is %d", deque[r]);
r=r-1;
}
}

int main()
{
insert_front(20);
insert_front(10);
insert_rear(30);
insert_rear(50);
insert_rear(80);
display();
getfront();
getrear();
delete_front();
delete_rear();
display();
return 0;
}

OUTPUT

Elements in a deque are: 10 20 30 50 80

The value of the element at front is: 10

The value of the element at rear is 80

The deleted element is 10

The deleted element is 80

Elements in a deque are: 20 30 50

RESULT
Thus the C program for implementation of DeQueue was done and executed
successfully.

84
Ex. No. : 16 IMPLEMENTATION OF THREADED BINARY TREE

AIM

To write a C program to implement Threaded Binary Tree.

ALGORITHM

Algorithm Inorder(I)

ThreadedTreeNode *Header;
Header=I;
while(1)

I=fnFindInorder_Successor(H);
if(I==Header)
return;
else
print(I->info);

PROGRAM

#include <stdio.h>
#include <stdlib.h>
typedef enum {false,true} boolean;
struct node *in_succ(struct node *p);
struct node *in_pred(struct node *p);
struct node *insert(struct node *root, int ikey);
struct node *del(struct node *root, int dkey);
struct node *case_a(struct node *root, struct node *par,struct node *ptr);
struct node *case_b(struct node *root,struct node *par,struct node *ptr);
struct node *case_c(struct node *root, struct node *par,struct node *ptr);
void inorder( struct node *root);
void preorder( struct node *root);

struct node
{
struct node *left;
boolean lthread;
int info;
boolean rthread;
struct node *right;
};

85
int main( )
{
int choice,num;
struct node *root=NULL;
while(1)
{
printf("\nProgram of Threaded Tree in C\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Inorder Traversal\n");
printf("4.Preorder Traversal\n");
printf("5.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the number to be inserted : ");
scanf("%d",&num);
root = insert(root,num);
break;
case 2:
printf("\nEnter the number to be deleted : ");
scanf("%d",&num);
root = del(root,num);
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
exit(1);

default:
printf("\nWrong choice\n");
}
}
return 0;
}

struct node *insert(struct node *root, int ikey)

{
struct node *tmp,*par,*ptr;
int found=0;

86
ptr = root;
par = NULL;
while( ptr!=NULL )
{
if( ikey == ptr->info)
{
found =1;
break;
}
par = ptr;
if(ikey < ptr->info)
{
if(ptr->lthread == false)
ptr = ptr->left;
else
break;
}
else
{
if(ptr->rthread == false)
ptr = ptr->right;
else
break;
}
}
if(found)
printf("\nDuplicate key");
else
{
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=ikey;
tmp->lthread = true;
tmp->rthread = true;
if(par==NULL)
{
root=tmp;
tmp->left=NULL;
tmp->right=NULL;
}
else if( ikey < par->info )
{
tmp->left=par->left;
tmp->right=par;
par->lthread=false;
par->left=tmp;
}

87
 else
{
tmp->left=par;
tmp->right=par->right;
par->rthread=false;
par->right=tmp;
}
}
return root;
}

struct node *del(struct node *root, int dkey)

{
struct node *par,*ptr;
int found=0;
ptr = root;
par = NULL;
while( ptr!=NULL)
{
if( dkey == ptr->info)
{
found =1;
break;
}
par = ptr;
if(dkey < ptr->info)
{
if(ptr->lthread == false)
ptr = ptr->left;
else
break;
}
else
{
if(ptr->rthread == false)
ptr = ptr->right;
else
break;
}
}
if(found==0)
printf("\ndkey not present in tree");
else if(ptr->lthread==false && ptr->rthread==false)/*2 children*/
root = case_c(root,par,ptr);
else if(ptr->lthread==false )
root = case_b(root, par,ptr);

88
 else if(ptr->rthread==false)
root = case_b(root, par,ptr);
else
root = case_a(root,par,ptr);
return root;
}

struct node *case_a(struct node *root, struct node *par,struct node *ptr )
{
if(par==NULL)
root=NULL;
else if(ptr==par->left)
{
par->lthread=true;
par->left=ptr->left;
}
else
{
par->rthread=true;
par->right=ptr->right;
}
free(ptr);
return root;
}

struct node *case_b(struct node *root,struct node *par,struct node *ptr)

{
struct node *child,*s,*p;
if(ptr->lthread==false)
child=ptr->left;
else
child=ptr->right;
if(par==NULL )
root=child;
else if( ptr==par->left)
par->left=child;
else
par->right=child;
s=in_succ(ptr);
p=in_pred(ptr);
if(ptr->lthread==false)
p->right=s;
else
{
if(ptr->rthread==false)
s->left=p;

89
 }
free(ptr);
return root;
}
struct node *case_c(struct node *root, struct node *par,struct node *ptr)
{
struct node *succ,*parsucc;
parsucc = ptr;
succ = ptr->right;
while(succ->left!=NULL)
{
parsucc = succ;
succ = succ->left;
}
ptr->info = succ->info;
if(succ->lthread==true && succ->rthread==true)
root = case_a(root, parsucc,succ);
else
root = case_b(root, parsucc,succ);
return root;
}
struct node *in_succ(struct node *ptr)
{
if(ptr->rthread==true)
return ptr->right;
else
{
ptr=ptr->right;
while(ptr->lthread==false)
ptr=ptr->left;
return ptr;
}
}
struct node *in_pred(struct node *ptr)
{
if(ptr->lthread==true)
return ptr->left;
else
{
ptr=ptr->left;
while(ptr->rthread==false)
ptr=ptr->right;
return ptr;
}
}

90
void inorder( struct node *root)
{
struct node *ptr;
if(root == NULL )
{
printf("Tree is empty");
return;
}
ptr=root;
while(ptr->lthread==false)
ptr=ptr->left;
while( ptr!=NULL )
{
printf("%d ",ptr->info);
ptr=in_succ(ptr);
}
}

void preorder(struct node *root )

{
struct node *ptr;
if(root==NULL)
{
printf("Tree is empty");
return;
}
ptr=root;
while(ptr!=NULL)
{
printf("%d ",ptr->info);
if(ptr->lthread==false)
ptr=ptr->left;
else if(ptr->rthread==false)
ptr=ptr->right;
else
{
while(ptr!=NULL && ptr->rthread==true)
ptr=ptr->right;
if(ptr!=NULL)
ptr=ptr->right;
}
}
}

91
OUTPUT

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 1

Enter the number to be inserted : 100

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 1

Enter the number to be inserted : 200

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 1

Enter the number to be inserted : 300

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 3

100 200 300

92
Program of Threaded Tree in C
1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 4

100 200 300

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 2

Enter the number to be deleted : 200

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 3

100 300

Program of Threaded Tree in C

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Quit

Enter your choice : 5

RESULT
Thus the C program for implementation of Threaded Binary Tree was done and
executed successfully.

93