VTU Data Structures Lab Manual

Lab manual consists of all 12 lab programs as per VTU new CBCS scheme

1. DS LAB PROGRAMS(18CSL38)

1) Design, Develop and Implement a menu driven Program in C for the following Array
operations
a. Creating an Array of N Integer Elements
b. Display of Array Elements with Suitable Headings
c. Inserting an Element (ELEM) at a given valid Position (POS)
d. Deleting an Element at a given valid Position(POS)
e. Exit.
Support the program with functions for each of the above operations.

#include<stdio.h>
#include<stdlib.h>
int a[6], n, elem, i, pos;
void create()
{
printf("\nEnter the size of the array elements: ");
scanf("%d", &n);
printf("\nEnter the elements for the array:\n");
for(i=0; i<n; i++)
scanf("%d", &a[i]);
}

void display()
{
int i;
printf("\nThe array elements are:\n");
for(i=0; i<n; i++)
{
printf("%d\t", a[i]);
}
}
void insert()
{
printf("\nEnter the position for the new element: ");
scanf("%d", &pos);
printf("\nEnter the element to be inserted: ");
scanf("%d", &elem);
for(i=n-1; i>=pos; i--)
{
a[i+1] = a[i];
}
a[pos] = elem;

2. n = n+1;
}
void del()
{
printf("\nEnter the position of the element to be deleted: ");
scanf("%d", &pos);
elem = a[pos];
for(i=pos; i<n-1; i++)
{
a[i] = a[i+1];
}
n = n-1;
printf("\nThe deleted element is = %d", elem);
}

int main()
{
int ch;
while(ch!=5)
{
printf("\n 1.Create\t 2.Display\t 3.Insert\t 4.Delete\t 5.Exit\n");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: create();
break;
case 2: display();
break;
case 3: insert();
break;
case 4: del();
break;
case 5: exit(0);
break;
default: printf("\nInvalid choice:\n");
break;
}
}
return 0;
}

3. 2) Design, Develop and Implement a Program in C for the following operations on
Strings
a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with
REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR
Support the program with functions for each of the above operations. Don't use Built-in
functions.

#include<stdio.h>
#include<stdlib.h>
char str[100], pat[50], rep[50], ans[100];
int i, j, c, m, k, flag=0;
void stringmatch()
{
i = m = c = j = 0;
while(str[c] != '\0')
{
if(str[m] == pat[i])
{
i++; m++;
if(pat[i] == '\0')
{
flag = 1;
for(k = 0; rep[k] != '\0'; k++, j++)
ans[j] = rep[k];
i = 0;
c = m;
}
}
else
{
ans[j] = str[c];
j++;
c++;
m=c;
}
}
ans[j] = '\0';
}
void main()
{
printf("Enter a main string \n");
gets(str);
printf("Enter a pattern string \n");
gets(pat);
printf("Enter a replace string \n");
gets(rep);
stringmatch();
if(flag == 1)
printf("The resultant string is\n %s" , ans);
else
printf("Pattern string NOT found\n");
}

4. 3) Design, Develop and Implement a menu driven Program in C for the following
operations on STACK of Integers (Array Implementation of Stack with maximum size
MAX)
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack
f. Exit
Support the program with appropriate functions for each of the above operations

#include <stdio.h>
#include<stdlib.h>
#define MAX 5
int stack[MAX], item, ch, top=-1, status=0;
void push(int stack[],int item)
{
if(top==(MAX-1))
printf("\nOverflow\n");
else
stack[++top]=item;
status++;
}

int pop()
{
if(top==-1)
printf("\nUnderflow\n");
else
return stack[top--];
status--;
}

void palindrome(int stack[])
{
int temp, count=0;
temp=status;
for(int i=0;i<temp;i++)
{
if(stack[i]==pop())
count++;
}
if(count==temp)
printf("Palindrome\n");
else
printf("not palindrome\n");
}

void display(int stack[])
{

5. if(top==-1)
printf("\nstack is empty\n");
else
for(int i=top;i>=0;i--)
{
printf("|%d|\n",stack[i]);
}
}

int main()
{
int ch;
while(ch<6)
{
printf("\n 1.push\t 2.pop\t 3.palindrome\t 4.display\t 5.exit\n");
printf("Enter the choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter the item: ");
scanf("%d",&item);
push(stack,item);
break;
case 2: printf("popped value = %d",pop());
break;
case 3: palindrome(stack);
break;
case 4: display(stack);
break;
case 5: exit(0);
default: printf("Invalid Choice\n");
break;
}
}
return 0;
}

6. 4) Design, Develop and Implement a Program in C for converting an Infix Expression
to Postfix Expression. Program should support for both parenthesized and free
parenthesized expressions with the operators: +, -, *, /, %(Remainder), ^(Power) and
alphanumeric operands.

#include <stdio.h>
#include <ctype.h>
char stack[100];
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;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/' || x=='%')
return 2;
if(x=='^')
return 3;
return 0;
}
void main()
{
char exp[20];
char *e, x;
printf("enter the expression : ");
scanf("%s", exp);
printf("\n");
e = exp;
while (*e != '\0')
{
if(isalnum(*e))
printf("%c", *e);
else if (*e == '(')
push(*e);

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

8. 5. Design, Develop and Implement a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
b. Solving Tower of Hanoi problem with n disks.

/* Evaluation of Suffix expression*/
#include <stdio.h>
#include <ctype.h>
#include<math.h>
char stack[100];
int top = -1;

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

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

int main()
{
char postfix[20], *p;
int n1,n2,n3,num;
printf("Enter the postfix expression: ");
scanf("%s",postfix);
p = postfix;
while(*p != '\0')
{
if(isdigit(*p))
{
num=(*p-48);
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*p)
{
case '+': n3 = n2 + n1;
break;
case '-': n3 = n2 - n1;
break;
case '*': n3 = n2 * n1;
break;

9. case '/': n3 = n2 / n1;
break;
case '^': n3 = pow(n2,n1);
break;
case '%': n3 = n2%n1;
break;
}
push(n3);
}
p++;
}
printf("\nThe result = %d",pop());
}

/* Tower of Hanoi */

#include<stdio.h>
#include<math.h>
void tower(int n, char S, char T, char D)
{
if(n==0)
return;
tower(n-1,S,D,T);
printf("\n Move disc %d from %c to %c",n,S,D);
tower(n-1,T,S,D);
}
void main()
{
int n;
printf("Enter the number of Discs: ");
scanf("%d",&n);
tower(n,'A','B','C');
printf("\n Total number of Moves=%d",(int)pow(2,n)-1);
}

10. 6. Design, Develop and Implement a menu driven Program in C for the following operations on
Circular QUEUE of Characters (Array Implementation of Queue with maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Support the program with appropriate functions for each of the above operations.

#include <stdio.h>
#include<stdlib.h>
#define MAX 5
int q[MAX],f=0,r=-1,count=0;

void insert (int item)
{
if (count==MAX)
printf("Queue Overflow\n");
else
{
r=(r+1)%MAX;
q[r]=item;
count=count+1;
}
}

int delete()
{
int itemdel;
if (count==0)
return 0;
else
{
itemdel=q[f];
f=(f+1)%MAX;
count=count-1;
return (itemdel);
}
}

void display()
{
int i,j;
if (count==0)
printf("Q empty\n");
else
{
i=f;
for (j=1;j<=count;j++)
{
printf("%d\t",q[i]);

11. i=(i+1)%MAX;
}
}
}

void main()
{
int ch,item,itemdel;
while (1)
{
printf("\nEnter the choice\n");
printf("1.Insert\t2.Delete\t3.Display\t4.Exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Enter the item\n");
scanf("%d",&item);
insert(item);
break;
case 2: itemdel=delete();
if (itemdel)
printf("The deleted item is %d\n",itemdel);
else
printf("Queue underflow\n");
break;
case 3: display();
break;
case 4: exit(0);
default: pritnf("Enter a valid choice\n");
}
}
}

12. 7. Design, Develop and Implement a menu driven Program in C for the following operations
on Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo.
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit

#include <stdio.h>
#include<stdlib.h>
typedef struct student
{
char usn[10];
char name[30];
char branch[5];
int sem;
char phno[15];
struct student *link;
}NODE;

NODE* getnode()
{
NODE *x;
x=(NODE*)malloc(sizeof(NODE));
printf("\n Enter Student Details: ");
scanf("%s %s %s %d %s",x->usn,x->name,x->branch,&x->sem,x->phno);
x->link=NULL;
return x;
}

NODE* insert_front(NODE* first)
{
NODE *temp;
temp=getnode();
if(first==NULL)
{
first=temp;
}
else
{
temp->link=first;
first=temp;
}
return first;
}

NODE* insert_rear(NODE* first)
{
NODE *temp,*cur;
temp=getnode();
if(first==NULL)

13. {
first=temp;
}
else
{
cur=first;
while(cur->link!=NULL)
{
cur=cur->link;
}
cur->link=temp;
}
return first;
}

NODE* delete_front(NODE* first)
{
NODE *cur;
if(first==NULL)
{
printf("\n List is empty\n");
}
else
{
cur=first;
first=first->link;
free(cur);
}
return first;
}

NODE* delete_rear(NODE *first)
{
NODE *prev, *cur;
if(first==NULL)
{
printf("\n List is empty\n");
}
if(first->link==NULL)
{
free(first);
return NULL;
}
prev=NULL;
cur=first;
while(cur->link!=NULL)
{
prev=cur;
cur=cur->link;
}
prev->link=NULL;

14. free(cur);
return first;
}

void display(NODE *first)
{
NODE *cur;
int count=0;
if(first == NULL)
printf("\nNo student data\n");
else
{
cur=first;
printf("\nUSN\t NAME\t Branch\t Sem\t Phno\n");
while(cur!=NULL)
{
printf("\n %s\t %s\t %s\t %d\t %s\n", cur->usn, cur->name,cur->branch,cur->sem,cur->phno);
cur = cur->link;
count++;
}
printf("\nThe no. of nodes in list is: %d",count);
}
}

NODE* stack(NODE *first)
{
int ch;
while(1)
{
printf("\nSLL used as Stack...");
printf("\n 1.PUSH \t 2.POP\t3.Display\t 4.Exit\t");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: first=insert_front(first); break;
case 2: first=delete_front(first); break;
case 3: display(first); break;
case 4: exit(0);
}
}
return first;
}

int main()
{
NODE *first=NULL;
int ch;
while(1)
{

15. printf("\n1.InsertFront\t 2. InsertRear\t 3.DeleteFront\t 4.DeleteRear\t 5.Display\t 6.Stack\t
7.exit\n");
printf("Enter Your Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:first=insert_front(first);
break;
case 2:first=insert_rear(first);
break;
case 3:first=delete_front(first);
break;
case 4:first=delete_rear(first);
break;
case 5:display(first);
break;
case 6:first=stack(first);
break;
case 7:exit(0);
break;
default: printf("\n Invalid choice\n");
break;
}
}
return 0;
}

16. 8. Design, Develop and Implement a menu driven Program in C for the following operations
on Doubly Linked List (DLL) of Employee Data with the fields: SSN, Name, Dept,
Designation, Sal, PhNo.
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue
f. Exit

#include <stdio.h>
#include<stdlib.h>
typedef struct student
{
int ssn;
char name[30];
char dept[5];
int sal;
char des[15];
struct student *next,*prev;
}NODE;

NODE* getnode()
{
NODE *x;
x=(NODE*)malloc(sizeof(NODE));
printf("\n Enter Employee Details: ");
scanf("%d %s %s %d %s",&x->ssn,x->name,x->dept,&x->sal,x->des);
x->next=x->prev=NULL;
return x;
}

NODE* insert_front(NODE* first)
{
NODE *temp;
temp=getnode(first);
if(first==NULL)
{
first=temp;
}

else
{
temp->next=first;
first->prev=temp;
first=temp;
}
return first;
}

NODE* insert_rear(NODE* first)

17. {
NODE *temp,*cur;
if(first==NULL)
{
temp=getnode(first);
first=temp;
}
else
{
temp=getnode(first);
cur=first;
while(cur->next!=NULL)
{
cur=cur->next;
}
cur->next=temp;
temp->prev=cur;
}
return first;
}

NODE* delete_front(NODE* first)
{
NODE *cur;
if(first==NULL)
{
printf("\n List is empty\n");
}
else if(first->next==NULL)
{
free(first);
return NULL;
}
else
{
cur=first;
first=first->next;
first->prev=NULL;
free(cur);
first->prev=NULL;
}
return first;
}

NODE* delete_rear(NODE* first)
{
NODE *prev, *cur;
if(first==NULL)
{
printf("\n List is empty\n");
}

18. else if(first->next==NULL)
{
free(first);
return NULL;
}
else
{
prev=NULL;
cur=first;
while(cur->next!=NULL)
{
prev=cur;
cur=cur->next;
}
prev->next=NULL;
free(cur);
}
return first;
}

void display(NODE *first)
{
NODE *cur;
int count=0;
if(first == NULL)
printf("\nNo Employee data\n");
else
{
cur=first;
printf("\nSSN\t NAME\t Dept\t Sal\t Designtn\n");
while(cur!=NULL)
{
printf("\n %d\t %s\t %s\t %d\t %s\n", cur->ssn, cur->name,cur->dept,cur->sal,cur->des);
cur = cur->next;
count++;
}
printf("\nThe no. of nodes in list is: %d",count);
}
}

NODE* dequeue(NODE *first)
{
int ch;
while(ch<6)
{
printf("\nDLL used as DEQUEUE...");
printf("\n 1.Insert_Front \t
2.Delete_Rear\t3.Insert_rear\t4.Delete_Front\t5.Display\t 6.Exit\n");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)

19. {
case 1: first=insert_front(first); break;
case 2: first=delete_rear(first); break;
case 3: first=insert_rear(first); break;
case 4: first=delete_front(first);break;
case 5: display(first); break;
case 6: exit(0);
}
}
return first;
}

int main( )
{
NODE *first=NULL;
int ch;
while(1)
{
printf("\n1.InsertFront\t 2. InsertRear\t 3.DeleteFront\t 4.DeleteRear\t 5.Display\t 6.Dequeue\t
7.exit\n");
printf("Enter Your Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:first=insert_front(first);
break;
case 2:first=insert_rear(first);
break;
case 3:first=delete_front(first);
break;
case 4:first=delete_rear(first);
break;
case 5:display(first);
break;
case 6:first=dequeue(first);
break;
case 7:exit(0);
break;
default: printf("\n Invalid choice\n");
break;
}
}
return 0;
}

20. 9. Design, Develop and Implement a Program in C for the following operations on Singly
Circular Linked List (SCLL) with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result in
POLYSUM(x,y,z)
Support the program with appropriate functions for each of the above operations

9a. Program
/* Program to Represent and Evaluate a Polynomial */

#include<stdio.h>
#include<conio.h>
#include<math.h>
typedef struct node
{
int cf;
int px,py,pz;
struct node* link;
}NODE;

NODE getnode()
{
NODE x;
x=(NODE)malloc( sizeof(struct node));
if(x==NULL)
{
printf("Out of memeory");
exit(0);
}
return x;
}

NODE insert_rear(int cf,int px,int py,int pz, NODE head)
{
NODE temp,cur;
temp=getnode();
temp->cf=cf;
temp->px=px;
temp->py=py;
temp->pz=pz;
cur=head->link;

while(cur->link!=head)
{
cur=cur->link;
}
cur->link=temp;
temp->link=head;
return head;
}

21. NODE read_poly(NODE head)
{
int i,n;
int cf,px,py,pz;
printf("Enter the no. of terms in the polynomial");
scanf("%d",&n);
for(i=1; i<=n; i++)
{
printf("Enter term:%d\n",i);
printf("Cf Px, py, pz=");
scanf("%d %d %d %d",&cf,&px,&py,&pz);
head= insert_rear(cf,px,py,pz,head);
}
return head;
}

void display(NODE head)
{
NODE temp;
if(head->link==head)
{
printf("Polynomail does not exist");
return;
}
temp=head->link;
while(temp!=head)
{
if(temp->cf<0)
printf("%d",temp->cf);
else
printf("+%d",temp->cf);
if(temp->px!=0)
printf("x^%d",temp->px);
if(temp->py!=0)
printf("y^%d",temp->py);
if(temp->pz!=0)
printf("z^%d",temp->pz);
temp=temp->link;
}
printf("\n");
}

float evaluate(NODE head)
{
int x,y,z;
float sum=0;
NODE p;
printf("Enter the value of x,y,z");
scanf("%d %d %d",&x,&y,&z);
p=head->link;
while(p!=head)

22. {
sum+=p->cf*pow(x,p->px)* pow(y,p->py)* pow(z,p->pz);
p=p->link;
}
return sum;
}

void main()
{
NODE head;
float res;
head=getnode();
head->link=head;
printf("Enter the polynomial\n");
head=read_poly(head);
res=evaluate(head);
printf("The given polynomial is\n");
display(head);
printf("The result=%f\n",res);
}

9b. Program
/* Program to find the sum of two Polynomial */

#include<stdio.h>
#include<conio.h>
#include<math.h>
typedef struct node
{
int cf;
int px,py,pz;
struct node* link;
}NODE;

NODE getnode()
{
NODE x;
x=(NODE)malloc( sizeof(struct node));
if(x==NULL)
{
printf("Out of memeory");
exit(0);
}
return x;
}

NODE insert_rear(int cf,int px,int py,int pz, NODE head)
{
NODE temp,cur;
temp=getnode();
temp->cf=cf;

23. temp->px=px;
temp->py=py;
temp->pz=pz;
cur=head->link;
while(cur->link!=head)
{
cur=cur->link;
}
cur->link=temp;
temp->link=head;
return head;
}

NODE read_poly(NODE head)
{
int i,n;
int cf,px,py,pz;
printf("Enter the no. of terms in the polynomial");
scanf("%d",&n);
for(i=1; i<=n; i++)
{
printf("Enter term:%d\n",i);
printf("Cf Px, py, pz=");
scanf("%d %d %d %d",&cf,&px,&py,&pz);
head= insert_rear(cf,px,py,pz,head);
}
return head;
}

void display(NODE head)
{
NODE temp;
if(head->link==head)
{
printf("Polynomail does not exist");
return;
}
temp=head->link;
while(temp!=head)
{
if(temp->cf<0)
printf("%d",temp->cf);
else
printf("+%d",temp->cf);
if(temp->px!=0)
printf("x^%d",temp->px);
if(temp->py!=0)
printf("y^%d",temp->py);
if(temp->pz!=0)
printf("z^%d",temp->pz);
temp=temp->link;

24. }
printf("\n");
}

NODE search(NODE p1,NODE h2)
{
NODE p2;
int cf1,px1,py1,pz1, cf2,px2,py2,pz2;
px1=p1->px;
py1=p1->py;
pz1=p1->pz;
p2=h2->link;
while ( p2 != h2)
{
px2=p2->px;
py2=p2->py;
pz2=p2->pz;
if( px1==px2 && py1==py2 && pz1==pz2 ) break;
p2=p2->link;
}
return p2;
}

NODE copy_poly (NODE h2, NODE h3)
{
NODE p2;
int cf2,px2,py2,pz2;
p2=h2->link;
while( p2!=h2)
{
if( p2->cf != -999)
{
cf2=p2->cf;
px2=p2->px;
py2=p2->py;
pz2=p2->pz;
h3=insert_rear(cf2, px2, py2, pz2, h3);
}
p2 = p2->link;
}
return h3;
}

NODE add_poly(NODE h1, NODE h2, NODE h3)
{
NODE p1,p2;
int cf1,px1,py1,pz1, sum;
p1 = h1->link;
while(p1!=h1)
{
cf1=p1->cf;

25. px1=p1->px;
py1=p1->py;
pz1=p1->pz;
p2=search(p1,h2);
if(p2!=h2)
{
sum=cf1+p2->cf;
h3=insert_rear(sum,px1,py1,pz1,h3);
p2->cf=-999;
}
else
h3= insert_rear(cf1,px1,py1,pz1,h3);
p1=p1->link;
}
h3=copy_poly(h2,h3);
return h3;
}

void main()
{
NODE h1,h2,h3;
clrscr();
h1= getnode();
h2=getnode();
h3= getnode();
h1->link=h1; h2->link=h2; h3->link=h3;
printf("Enter the first polynomial\n");
h1=read_poly(h1);
printf("Enter the second polynomial\n");
h2=read_poly(h2);
printf("Poly 1:");
display(h1);
printf("Poly2:");
display(h2);
printf("----------------------------------------------------------------\n");
h3= add_poly(h1,h2,h3);
printf("Poly 3:");
display(h3);
printf("----------------------------------------------------------------\n");
getch();
}

26. 10. Design, Develop and Implement a menu driven Program in C for the following operations
on Binary Search Tree (BST) of Integers:
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int item;
struct node *llink, *rlink;
}NODE;

NODE* getnode()
{
NODE* x;
x=(NODE*)malloc(sizeof(NODE));
scanf("%d",&x->item);
x->llink=x->rlink=NULL;
return x;
}

NODE* insert(NODE* root)
{
NODE *temp,*cur,*prev;
temp=getnode();
if(root==NULL)
{
root=temp;
}
else
{
prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur;
if(temp->item<cur->item)
cur=cur->llink;
else
cur=cur->rlink;
}
if(temp->item<prev->item)
prev->llink=temp;
else
prev->rlink=temp;
}

27. return root;
}

void search(NODE *root)
{
int item;
NODE *cur;
cur=root;
if(root==NULL)
{
printf("Tree is empty\n");
}
else
{
printf("Enter the item to be searched: ");
scanf("%d",&item);
while(cur!=NULL)
{
if(cur->item==item)
break;
if(cur->item<item)
cur=cur->rlink;
else
cur=cur->llink;
}
if(cur!=NULL)
{
printf("Item found\n");
}
else
{
printf("Item Not found");
}
}
}

void preorder(NODE *root)
{
if(root==NULL) return;
printf("%d\t",root->item);
preorder(root->llink);
preorder(root->rlink);
}

void postorder(NODE *root)
{
if(root==NULL) return;
postorder(root->llink);
postorder(root->rlink);

28. printf("%d\t",root->item);
}

void inorder(NODE *root)
{
if(root==NULL) return;
inorder(root->llink);
printf("%d\t",root->item);
inorder(root->rlink);
}

int main()
{
int ch,i,n,ht;
NODE *root=NULL;
while(1)
{
printf("\n 1.Create\t 2.Traverse\t 3.Search\t 4.Height\t 5.Exit\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("Enter the number of nodes to be inserted: ");
scanf("%d",&n);
printf("Enter the tree nodes\n");
for(i=0;i<n;i++)
{
root=insert(root);
}
break;
case 2:printf("\n Preorder Traversal: ");
preorder(root);
printf("\n Inorder Traversal: ");
inorder(root);
printf("\n Postorder Traversal: ");
postorder(root);
break;
case 3:search(root);
break;
case 4:exit(0);
default:printf("\n Invalid Choice\n");
break;
}
}
return 0;
}

29. 11. Design, Develop and Implement a Program in C for the following operations on Graph(G) of
Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS method
/* Traversal using DFS method*/
#include<stdio.h>
int stack[10];
int top=-1;
int adj[10][10];
int vis[10]={0};

void main()
{
int n, s, u, v, i, j;
int found=0;
printf("\n Enter the number of vertex:");
scanf("%d",&n);
printf("\n Enter the adj matrix:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&adj[i][j]);
}
}
printf("\n Enter the source vertex:");
scanf("%d",&s);
stack[++top]=s;
vis[s]=1;
printf("source %d:",s);
while(top!=-1)
{
found=0;
u=stack[top];
for(v=0;v<n && found==0;v++)
{
if(adj[u][v]==1 && vis[v]==0)
{
printf("->%d",v);
stack[++top]=v;
vis[v]=1;
found=1;
}
}
if(found==0)
{
top--;
}
}
}

30. /* Traversal using BFS method*/

#include<stdio.h>
int q[10];
int r=-1, f=0;
int adj[10][10];
int vis[10]={0};

void main()
{
int n, i, j, s, v, u;
printf("\n Enter the number of vertex:");
scanf("%d",&n);
printf("\n Enter the Adj matrix:\n ");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&adj[i][j]);
}
}
printf("\n Enter the source vertex:");
scanf("%d",&s);
q[++r]=s;
vis[s]=1;
printf("%d: ",s);
while(f<=r)
{
u=q[f++];
for(v=0;v<n;v++)
{
if(adj[u][v]==1 && vis[v]==0)
{
printf("->%d",v);
vis[v]=1;
q[++r]=v;
}
}
}
}

31. 12. Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine the
records in file F. Assume that file F is maintained in memory by a Hash Table(HT) of m memory
locations with L as the set of memory addresses (2-digit) of locations in HT. Let the keys in K and
addresses in L are Integers. Design and develop a Program in C that uses Hash function H: K →L as
H(K)=K mod m (remainder method), and implement hashing technique to map a given key K
to the address space L. Resolve the collision (if any) using linear probing.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 10
typedef struct
{
int id;
char name[20];
}EMPLOYEE;
EMPLOYEE e[SIZE];

void initialize_table()
{
for(int i=0; i<SIZE; i++)
{
e[i].id=0;
}
}

void insert_table()
{
int i,id,index,hvalue;
char name[26];
printf("Enter the employee id and name: ");
scanf("%d %s",&id,name);
hvalue= id % SIZE;
for(i=0; i<SIZE; i++)
{
index=(hvalue+i) % SIZE;
if(e[index].id==0)
{
e[index].id=id;
strcpy(e[index].name,name);
break;
}
}
if(i==SIZE)
{
printf("Hash table full\n");
}
}

void display_table()

32. {
printf("H\t Id\t Name\n");
for(int i=0; i<SIZE; i++)
{
printf("%d\t %d\t %s\n",i,e[i].id,e[i].name);
}
}

void main()
{
int ch, id;
char name[26];
initialize_table();
while(ch<4)
{
printf("1:Insert\t 2:Display\t 3:Exit\n");
printf("Enter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:insert_table( );
break;
case 2:display_table();
break;
case 3: exit(0);
break;
deafult: printf("Enter valid choice\n");
break;
}
}
}