Datastructures Lab Programs 5i3q31

DATA STRUCTURES LABORATORY

LIST OF EXPERIMENTS 1) Implement singly and doubly linked lists.

L 0

T 0

P C 3 2

2) Represent a polynomial as a linked list and write functions for polynomial addition. 3) Implement stack and use it to convert infix to postfix expression 4) Implement a double-ended queue (dequeue) where insertion and deletion operations are possible at both the ends. 5) Implement an expression tree. Produce its pre-order, in-order, and post-order traversals. 6) Implement binary search tree. 7) Implement insertion in AVL trees. 8) Implement priority queue using binary heaps 9) Implement hashing with open addressing. 10) Implement Prim's algorithm using priority queues to find MST of an undirected graph.

Total: 45

DATA STRUCTURES LABORATORY List of Experiments: 1. Singly Linked List. 2. Doubly Linked List. 3. Polynomial Addition. 4. Infix to Postfix Expression. 5. Double Ended Queue. 6. An Expression Tree. 7. Binary Search Tree. 8. AVL Tree. 9. Priority Queue using Binary Heap. 10.Hashing with Open Addressing. 11.Prim’s Algorithm.

EX:NO:1a.

SINGLY LINKED LIST IMPLEMENTATION

DATE: AIM: To implement singly linked list and performing insert, delete and search operations. ALGORITHM: 1.

Set a node to contain INFO and LINK fields.

2.

Allot memory dynamically for a node and declare it as a header H.

3.

To create a singly linked lists get the element N and allot memory for a node S1.

4.

Set S1->INFO=N; and S1->LINK=NULL.

5.

Repeat the above two steps for all the elements.

6.

A node can be inserted at the front, in the middle or at the end of the list.

7.

To insert a node X at the front check whether the list is empty,

if

not set

X->LINK=H->LINK and H->LINK=X. 8.

To insert a node X at the end travel till the end of the list and assign the last node’s LINK value to X.

9.

To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->LINK=Y->LINK and Y->LINK=X

10.

A node can be deleted at the front, in the middle or at the end of the list.

11.

To delete a node X at the front set H->LINK=H->LINK>LINK.

12.

To delete a node X at the end travel the list till the end and assign the previous to last node’s LINK value to be NULL.

13.

To delete a node X after the specified node Y, travel the list till the node Y is reached Set Y->LINK= Y>LINK->LINK.

14.

To search an element E traverse the list until E is found.

**** SINGLY LINKED LIST **** #include<stdio.h> #include #include<stdlib.h> #define TRUE 1 #define FALSE 0 typedef struct SLL { int data; struct SLL *next; }node; node *create(); void main() { int choice,val; char ans; node *head; void display(node *); node *search(node *,int); void insert(node *); void delete(node **); node *get_prev(node *,int); head=NULL; clrscr(); do { printf("\n Singly Linked List\n"); printf("\n 1.create\n2.Display\n3.search\n4.insert\n5.delete\n6.quit\n"); printf("\n Enter ur choice:"); scanf("%d",&choice); switch(choice) { case 1: head=create(); break; case 2:display(head); break; case 3:printf("Enter the element to search"); scanf("%d",&val); search(head,val); break; case 4:insert(head); break; case 5:delete(&head); break;

case 6:exit(0); efault:clrscr(); printf("Invalid choice, try again"); getch(); } } while(choice!=6); } node *create() { node *temp,*new,*head; int val,flag; char ans='y'; node *get_node(); temp=NULL; flag=TRUE; do { printf("\nEmter the element:"); scanf("%d",&val); new=get_node(); if(new==NULL) printf("\nMemory is not allocated"); new->data=val; if(flag) {head=new; temp=head; flag=FALSE; } else { temp->next=new; temp=new; } printf("\n Do u want to enter more elements?"); ans=getche(); }while(ans=='y'); printf("\nThe singly linked list is created\n"); getch(); return head; } node *get_node() { node *temp; temp=(node *)malloc(sizeof(node)); temp->next=NULL; return temp;

} void display(node *head) { node *temp; temp=head; if(temp==NULL) { printf("\nThe listis empty\n"); getch(); return; } while(temp!=NULL) { printf("%d->",temp->data); temp=temp->next; } printf("NULL"); getch(); } node* search(node *head,int key) { node *temp; int found; temp=head; if(temp==NULL) { printf("\nThe listis empty\n"); getch(); return NULL; } found=FALSE; while(temp!=NULL && !found) { if(temp->data!=key) temp=temp->next; else found=TRUE; } if(found) { printf("\nThe element is present\n"); getch(); return temp; } else { printf("\nThe element is not found\n");

getch(); return NULL; } } void insert(node *head) { node *temp,*new; int val; temp=head; if(temp==NULL) { printf("\nInsertion is not possible\n"); getch(); return; } printf("\n Enter the element after which to insert:"); scanf("%d",&val); temp=search(head,val); if(temp!=NULL) { printf("Enter the element to insert:"); scanf("%d",&val); new=(node*)malloc(sizeof(node)); if(new==NULL) printf("memory is not allocated\n"); new->data=val; new->next=NULL; new->next=temp->next; temp->next=new; printf("\n The element is inserted"); getch(); } } node* get_prev(node *head,int val) { node *temp,*prev; int flag; temp=head; if(temp==NULL) return NULL; flag=FALSE; prev=NULL; while(temp!=NULL && !flag) { if(temp->data!=val) { prev=temp;

temp=temp->next; } else flag=TRUE; } if(flag) return prev; else return NULL; } void delete(node **head) { node *temp,*prev; int key; temp=*head; if(temp==NULL) { printf("\nThe list is empty\n"); getch(); return; } printf("\nEnter the element u want to delete:"); scanf("%d",&key); temp=search(*head,key); if(temp!=NULL) { prev=get_prev(*head,key); if(prev!=NULL) { prev->next=temp->next; free(temp); } else { *head=temp->next; free(temp); } printf("\nThe element is deleted\n"); getch(); } }

OUTPUT: Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:1 Enter the element:12 Do u want to enter more elements?y Enter the element:11 Do u want to enter more elements?n The singly linked list is created Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:2 12->11->NULL Singly Linked List 1.Create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:3 Enter the element to search 11 The element is present

Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:4 Enter the element after which to insert:12 The element is present Enter the element to insert:10 The element is inserted Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:2 12->10->11->NULL Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:5 Enter the element u want to delete:10 The element is present The element is deleted

Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:2 12->11->NULL Singly Linked List 1.create 2.Display 3.search 4.insert 5.delete 6.quit Enter ur choice:6

RESULT: Thus the singly linked list is implemented and insert, delete and

search

operations

are

performed

and

verified.

EX:NO:1b.

DOUBLY LINKED LIST IMPLEMENTATION

DATE: AIM: To implement doubly linked list and perform insert, delete and search operations. ALGORITHM:

1.

Set a node to contain INFO and RLINK and LLINK fields.

2.

Allot memory dynamically for a node and declare it as a header H.

3.

To create a doubly linked list get the element N and allot memory for a node S1.

4.

Set S1->INFO=N; and S1->RLINK=NULL, S1->LLINK=H.

5.

Repeat the above two steps for all the elements.

6.

A node can be inserted at the front, in the middle or at the end of the list.

7.

To insert a node X at the front check whether the list is empty, if not set X->RLINK=H->RLINK and H->RLINK=X.

8.

To insert a node X at the end travel till the end of the list and assign the last node’s RLINK value to X and set X->LLINK=last node’s RLINK.

9.

To insert a node X after the specified node Y, travel the list till the node Y is reached. Set

X->RLINK=Y-

>RLINK , Y->RLINK=X,X->LLINK=Y and X->RLINK->LLINK=X 10.

A node can be deleted at the front, in the middle or at the end of the list.

11.

To delete a node X at the front set X->RLINK->LLINK=H,H>RLINK->RLINK= X.

12.

To delete a node X at the end travel the list till the end and assign the previous to last node’s RLINK value to be NULL.

13.

To delete a node X after the specified node Y, travel the

list

till

the

node

Y

is

reached

Set

X->RLINK-

>LLINK=Y, Y->RLINK= X->RLINK. 14.

To search an element E traverse the list until E is found.

**** DOUBLY LINKED LIST **** #include<stdio.h> #include #include<stdlib.h> #define TRUE 1 #define FALSE 0 struct node { int data; struct node *next,*prev; }*new,*new1,*temp,*start,*dummy; void add(void); struct node *get_node(); void display(void); void del(void); int find(int); int first=1; void main() { char ans; int choice,num; start=NULL; clrscr(); do { printf("\nprogram for Doubly Linked List\n"); printf("\n1.insertion\n2.deletion\n3.display\n4.searching\n5.exit\ n"); printf("\nEnter ur choice:"); scanf("%d",&choice); switch(choice) { case 1: add(); break; case 2:del(); break; case 3:display(); break; case 4:printf("\nenter the element to be searched:");

scanf("%d",&num); find(num); break; case 5:exit(0); } }while(choice!=5); getch(); } void add(void) { new=get_node(); printf("\n\n\n enter the element\n"); scanf("%d",&new->data); if(first==1) { start=new; first=0; } else { dummy=start; while(dummy->next!=NULL) dummy=dummy->next; dummy->next=new; new->prev=dummy; } } struct node *get_node() { new1=(struct node *)malloc(sizeof(struct node)); new1->next=NULL; new1->prev=NULL; return(new1); } void display(void) { temp=start; if(temp==NULL) printf("\n The Doubly Linked List is empty\n"); else { while(temp!= NULL)

{ printf("%d=>",temp->data); temp=temp->next; } printf("NULL"); } getch(); } int find(int num) { int found; temp=start; if(temp==NULL) { printf("The linked list is empty\n"); getch(); return NULL; } found=FALSE; while(temp != NULL && !found) { if(temp->data!=num) temp=temp->next; else found=TRUE; } if(found) { printf("\nThe element is present in the list\n"); getch(); return found; } else { printf("The element is not found\n"); getch(); return NULL; } } void del(void) { int num,flag=0; int found; int last=0;

if(temp==NULL) printf("\nsorry:DLL not created\n"); else { printf("\nEnter the number to be deleted:"); scanf("%d",&num); while((flag==0) && (temp!=NULL)) { found=find(num); ); flag=found; } if(temp==start) { start=start->next; temp->next=NULL; start->prev=NULL; free(temp); getch(); printf("\n the starting node is deleted"); } else { if(temp->next==NULL) last=1; else last=0; (temp->next)->prev=temp->prev; (temp->prev)->next=temp->next; temp->prev=NULL; temp->next=NULL; free(temp); if(last) printf("\n The last node is deleted\n"); else printf("\nThe intermediate node is deleted\n"); } } }

OUTPUT: program for Doubly Linked List 1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:1 enter the element 11 program for Doubly Linked List 1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:1 enter the element 12 program for Doubly Linked List 1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:3 11=>12=>NULL program for Doubly Linked List 1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:4 enter the element to be searched:11 The element is present in the list program for Doubly Linked List

1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:2 Enter the number to be deleted:12 The element is present in the list The last node is deleted program for Doubly Linked List 1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:3 11=>NULL program for Doubly Linked List 1.insertion 2.deletion 3.display 4.searching 5.exit Enter ur choice:5

RESULT: Thus the doubly linked list is implemented and insert, delete and

search

operations

are

performed

and

verified.

EX:NO:2

POLYNOMIAL ADDITION

DATE: AIM: To write a C program to find the addition of two polynomial expressions using Linked List. ALGORITHM: 1. Initialize all the variables. 2. Read the polynomial expressions as , coefficients and exponents. 3. Check for exponents. 4. If exponents are equal then add the two coefficients and append the exponent. 5. Else check for another. 6. If not add the coefficient and exponent. 7. Print the added polynomial expression. 8. End of the program.

**** Polynomial Addition **** #include<stdio.h> #include typedef struct poly { int coeff; int expo; }p; p p1[10],p2[10],p3[10]; void main() { int t1,t2,t3,k; int read(p p1[10]); int add(p p1[10],p p2[10],int t1,int t2,p p3[10]); void print(p p2[10],int t2); void printo(p pp[10],int t2); clrscr(); t1=read(p1); print(p1,t1); t2=read(p2); print(p2,t2); t3=add(p1,p2,t1,t2,p3); printo(p3,t3); getch(); } int read(p p[10]) { int t1,i; printf("\n enter the total no of "); scanf("%d",&t1); printf("\n enter the coeff and expo in descending order"); for(i=0;i
i++;j++;k++; } else if(p1[i].expo > p2[j].expo) { p3[k].coeff=p1[i].coeff; p3[k].expo=p1[i].expo; i++;k++; } else { p3[k].coeff=p2[j].coeff; p3[k].expo=p2[j].expo; j++;k++; } } while(i
OUTPUT: enter the total no of 3 enter the coeff and expo in descending order4 3 4 2 2 1 Given polynomial:4 x^3 +4 x^2 +2 x^1 enter the total no of 2 enter the coeff and expo in descending order4 5 3 0 Given polynomial:4 x^5 +3 x^0 The addition of polynomial:4 x^5 +4 x^3 +4 x^2 +2 x^1 +3 x^0

RESULT: Thus the polynomial addition is performed using linked list.

EX:NO:3

INFIX TO POSTFIX CONVERSION

DATE: AIM: To write a C program to convert the infix expression into a postfix expression using stack. ALGORITHM: 1. Scan the Infix string from left to right. 2. Initialize an empty stack. 3. If the scanned character is an operand, add it to the Postfix string.

If the scanned character is an operator and

if the stack is empty Push the character to stack. a. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). b. If

topStack

has

higher

precedence

over

the

scanned

character Pop the stack else Push the scanned character to stack. c. Repeat this step as long as stack is not empty and topStack

has precedence over the character.

4. Repeat this step till all the characters are scanned. 5. If stack is not empty add topStack to Postfix string and Pop the stack.

Repeat this step as long as stack is not empty.

6. Return the Postfix string. 7. End.

**** INFIX TO POSTFIX CONVERSION **** #include<stdio.h> #include<string.h> #include<stdlib.h> #include char infix[100]; char stack[200]; int top; int r; char next; char postfix[100]; void convert(); int input_p(char); int stack_p(char); int rank(char); int input_p(char c) { if(c=='+' || c=='-') return 1; else if(c=='*' || c=='/') return 3; else if(c=='^') return 6; else if(isalpha(c)!=0) return 7; else if(c=='(') return 9; else if(c==')') return 0; else printf("\nInvalid expression\n"); return next; } int stack_p(char c) { if(c=='+' || c=='-') return 2; else if(c=='*' || c=='/') return 4; else if(c=='^') return 5; else if(isalpha(c)!=0) return 8; else if(c=='(') return 0;

else printf("\nInvalid Expression::Stack Error\n"); return c; } int rank(char c) { if(c=='+' || c=='-') return -1; else if(c=='*' || c=='/') return -1; else if(c=='^') return -1; else if(isalpha(c)!=0) return 1; else printf("\nInvlid expression in rank\n"); return c; } void convert() { int l,x,i; char next; printf("\nInfix to Postfix Conversion\n"); printf("\nEnter an infix Expression::"); scanf("%s",infix); l=strlen(infix); infix[l]=')'; infix[l+1]='\0'; top=1; stack[top]='('; r=0; x=-1; i=0; next=infix[i]; while(next!='\0') { while( input_p(next) < stack_p(stack[top]) ) { if(top<1) { printf("\nInvalid expression::satck error\n"); exit(0); } postfix[++x]=stack[top]; top--; r=r+rank(postfix[x]);

if(r<1) { printf("\nInvalid expression::r<1\n"); exit(0); } } if(input_p( next ) != stack_p( stack[top])) stack[++top]=next; else top--; i++; next=infix[i]; } postfix[++x]='\0'; if(r!=1 || top!=0) { printf("\nInvalid expression::error in rank or stack\n"); exit(0); } printf("\nThe corresponding postfix expression is ::"); printf("%s",postfix); } int main() {scr(); convert(); getch(); return 0; } OUTPUT: Infix to Postfox Conversion Enter an infix Expression::(a+b^c^d)*(c+d) The corresponding postfix expression is ::abcd^^+cd+*

RESULT:

Thus the given infix expression is converted into a postfix expression using stack successfully. EX:NO:4

DOUBLE ENDED QUEUE (DEQUEUE)

DATE: AIM: To

write

(dequeue)

a

C

with

program all

to

implement

possible

a

double

operations

ended on

queue it.

ALGORITHM: 1. Initialize all variables and functions. 2. Read choices. 3. If queue is not full, add items at front or back. And increment top value by 1. 4. Else print “Queue is full”. 5. If Queue is not empty, delete items at front or back. And decrement top value by 1. 6. Else print “Queue is empty”. 7. Display the queue items. 8. End of the program.

**** Program for Double Ended Queue **** #include<stdio.h> #include #include<stdlib.h> #define size

5

struct dequeue{ int deq[size]; int front,rear; }Q; int Qfull() { if(Q.rear==size-1) return 1; else return 0; } int Qempty() { if((Q.front>Q.rear) || (Q.front==-1 && Q.rear==-1)) return 1; else return 0; } int insert_rear(int item) { if(Q.front==-1 && Q.rear==-1) Q.front++; Q.deq[++Q.rear]=item; return Q.rear; } int del_front() { int item; if(Q.front==-1) Q.front++; item=Q.deq[Q.front];

Q.deq[Q.front]=-1; Q.front++; return item; } int insert_front(int item) { int i,j; if(Q.front==-1) Q.front++; i=Q.front-1; while(i>=0) { Q.deq[i+1]=Q.deq[i]; i--; } j=Q.rear; while(j>=Q.front) { Q.deq[j+1]=Q.deq[j]; j--; } Q.rear++; Q.deq[Q.front]=item; return Q.front; } int del_rear() { int item; item=Q.deq[Q.rear]; Q.deq[Q.rear]=-1; Q.rear--; return item; } void display() { int i; printf("\n Queue is "); for(i=Q.front;i<=Q.rear;i++) printf(" %d ",Q.deq[i]); } void main() { int choice,i,item;

Q.front=-1; Q.rear=-1; for(i=0;i<size;i++) Q.deq[i]=-1; clrscr(); printf("\n\n\n\n Double ended queue OR Dequeue\n"); do { printf("\n1.Insert front\n2.Insert rear\n3.Delete front\n4.Delete rear\n"); printf("5.Display\n6.Exit\n"); printf("\nEnter ur choice:"); scanf("%d",&choice); switch(choice) { case 1:if(Qfull()) printf("\nDequeue is full"); else { printf("\nEnter item to be inserted:"); scanf("%d",&item); Q.front=insert_front(item); } break; case 2:if(Qfull()) printf("\nDequeue is full"); else { printf("\nEnter item to be inserted:"); scanf("%d",&item); Q.rear=insert_rear(item); } break; case 3:if(Qempty()) printf("\nDequeue is empty"); else { item=del_front(); printf("\nThe item deleted from queue is } break; case 4:if(Qempty()) printf("\nDequeue is else

empty");

%d",item);

{ item=del_rear(); printf("\nThe item deleted from queue is } break; case 5:display(); break; case 6:exit(0); } }while(choice!=6); getch(); } OUTPUT: 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:1 Enter item to be inserted:11 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:2 The item deleted from queue is 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:5

12

%d",item);

Queue is 11 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit

12

Enter ur choice:1 Enter item to be inserted:10 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:2 Enter item to be inserted:13 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:5 Queue is

10

11

12

13

1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:3 The item 1.Insert 2.Insert 3.Delete

deleted from queue is front rear front

10

4.Delete rear 5.Display 6.Exit Enter ur choice:4 The item deleted from queue is 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:5 Queue is 11 1.Insert front 2.Insert rear 3.Delete front 4.Delete rear 5.Display 6.Exit Enter ur choice:6

RESULT:

12

13

Thus the C program for Double ended queue is implemented and insertion, deletion on both ends is done successfully.

EX:NO:5

EXPRESSION TREE TRAVERSAL

DATE: AIM: To write a C program to implement an expression tree and produce its pre-order, in-order, and post-order traversals. ALGORITHM: 1. preorder(T, v) a. visit node v b. if T.hasLeft(v) preorder(T, T.left(v)) c. if T.hasRight(v) preorder(T, T.right(v)) 2. postorder(T, v) a. if T.hasLeft(v) postorder(T, T.left(v)) b. if T.hasRight(v) postorder(T, T.right(v)) c. visit node v 3. inorder(T, v) a. if T.hasLeft(v) inorder(T, T.left(v)) b. visit node v c. if T.hasRight(v) inorder(T, T.right(v))

**** Expression tree ***** #include<stdio.h> #include #include #include<math.h> #define MAX 50 struct node { struct node* left_child; char x; struct node* right_child; } * stack[50]; int top = -1; struct node* CreateExpTreePostfix(char*); struct node* CreateExpTreePrefix(char*); void preorder(struct node* sr); void inorder(struct node* sr); void postorder(struct node* sr); void push(struct node**, struct node*); struct node* pop(struct node**); void Delete_Tree(struct node*); main() { struct node* root; char str[50]; int z; char ch; clrscr(); printf("Input expression is:\n1)Prefix\n2)Postfix "); ch=getche(); if(ch=='1') { printf("\nEnter Prefix Expression:"); gets(str);

root = CreateExpTreePrefix(str); } else { printf("\nEnter Postfix Expression:"); gets(str); root = CreateExpTreePostfix(str); } printf("\nPrefix Exp. :"); preorder(root); printf("\nInfix Exp. :"); inorder(root); printf("\nPostfix Exp. :"); postorder(root); Delete_Tree(root); getch(); } struct node* CreateExpTreePostfix(char* str) { struct node* nleft, * nright, * nodeptr; while (*str) { nodeptr = (struct node *) malloc(sizeof(struct node)); nodeptr->x = *str; if (*str == '+' || *str == '-' || *str == '/' || *str == '*' || *str == '^') { nright = pop(stack); nleft = pop(stack); nodeptr->left_child = nleft; nodeptr->right_child = nright; } else { nodeptr->left_child = NULL; nodeptr->right_child = NULL; } push(stack, nodeptr); str++; } return pop(stack); struct node* CreateExpTreePrefix(char* str) { struct node* nleft, * nright, * nodeptr; strrev(str); while (*str)

{ nodeptr = (struct node *) malloc(sizeof(struct node)); nodeptr->x=*str; if (*str == '+' || *str == '-' || *str == '/' || *str == '*' || *str == '^') { nleft = pop(stack); nright = pop(stack); nodeptr->left_child = nleft; nodeptr->right_child = nright; } else { nodeptr->left_child = NULL; nodeptr->right_child = NULL; } push(stack, nodeptr); str++; } return pop(stack); } void inorder(struct node* sr) { if (sr != NULL) { inorder(sr -> left_child) ; printf("%c", sr ->x) ; inorder(sr -> right_child) ; } } void preorder(struct node* sr) { if (sr != NULL) { printf("%c", sr -> x) ; preorder(sr -> left_child) ; preorder(sr -> right_child) ; } } void postorder(struct node* sr) { if (sr != NULL) { postorder(sr -> left_child) ;

postorder(sr -> right_child) ; printf("%c", sr -> x) ; } } void push(struct node** stack, struct node* ptr) { if (top == MAX - 1) printf("\nStack is full.\n") ; else { top++ ; stack[top] = ptr ; } } struct node* pop(struct node** stack) { if (top == -1) { printf("Stack is empty\n") ; return -1 ; } else { struct node* ptr = stack[top] ; top-- ; return ptr ; } } void Delete_Tree(struct node * root) { if(root!=NULL) { Delete_Tree(root->left_child); Delete_Tree(root->right_child); free(root); } } OUTPUT: Input expression is: 1)Prefix 2)Postfix 1

Enter Prefix Expression:+*abc Prefix Exp. :+*abc Infix Exp. :a*b+c Postfix Exp. :ab*c+ Input expression is: 1)Prefix 2)Postfix 2 Enter Postfix Expression:ab*c+ Prefix Exp. :+*abc Infix Exp. :a*b+c Postfix Exp. :ab*c+

RESULT:

Thus an expression tree is implemented and its pre-order, inorder, and post-order traversals are produced successfully. EX:NO:6

BINARY SEARCH TREE

DATE: AIM: To implement binary search tree using linked list and possible operations on binary search trees. ALGORITHM: 1. Create the memory space for the root node and initialize the value to zero. 2. Read the value. 3. If the value is less than the root value ,it is assigned as the left child of the root. 4. Else if new value is greater than the root value, it is assigned as the right child of the root. 5. Else if there is no value in the root, the new value is assigned as the root. 4. The step (2) and (3) is repeated to insert the ‘n’ number of values. Search operation 1. Read the value to be searched. 2. Check whether the root is not null. 3. If the value to be searched is less than the root, consider the left sub-tree for searching the particular element else if the value is greater than the root consider the right sub - tree to search the particular element else if the value is equal then return the value that is the value which was searched. Insertion 1. Read the value to be inserted 2. First perform the search operation to check whether the key values is different from those existing element 3. If the search is unsuccessful, then the key is inserted at the point the search is terminated. 4. If the key value is the leaf-node, assign null

**** Binary Search Tree **** #include<stdio.h> struct BT { int data; struct BT *right,*left; }; void insert(struct BT ** ptr,int d) { if((*ptr)==NULL) { (*ptr)=(struct BT*)malloc(sizeof(struct BT)); (*ptr)->data=d; (*ptr)->left=(*ptr)->right=NULL; } else { if((*ptr)->data>d) insert(&((*ptr)->left),d); else insert(&((*ptr)->right),d); } return; } int search(struct BT *ptr,int no) { if(ptr==NULL) return(0); if(ptr->data==no) return(1); if(ptr->data>no) return(search(ptr->left,no)); else return(search(ptr->right,no)); } void inorder(struct BT *ptr) {

if(ptr==NULL) return; else { inorder(ptr->left); printf("\t%d",ptr->data); inorder(ptr->right); } } void preorder(struct BT*ptr) { if(ptr==NULL) return; else { printf("\t%d",ptr->data); preorder(ptr->left); preorder(ptr->right); } } void postorder(struct BT*ptr) { if(ptr==NULL) return; else { postorder(ptr->left); postorder(ptr->right); printf("\t%d",ptr->data); } } main() { struct BT*root; int ch,d,no,f; clrscr(); root=NULL; while(ch!=6) { printf("\n 1.Insert\n 2.Search\n 3.Inorder\n 4.Preorder\n 5.Postorder\n 6.Exit\n"); printf("\n Enter the choice:"); scanf("%d",&ch); switch(ch) {

case 1: printf("Enter the data:"); scanf("%d",&d); insert(&root,d); break; case 2: printf("Enter the node:"); scanf("%d",&no); f=search(root,no); if(f==0) printf("Node is not present"); else printf("Node is present"); break; case 3: inorder(root); break; case 4: preorder(root); break; case 5: postorder(root); break; case 6: break; } } getch(); } OUTPUT: 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:1 Enter the data:11 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:1 Enter the data:10 1.Insert

2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:1 Enter the data:14 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:1 Enter the data:15 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:1 Enter the data:9 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:2 Enter the node:10 Node is present 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit

Enter the choice:3 9 10

11

14

15

9

14

15

15

14

11

1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:4 11 10 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:5 9 10 1.Insert 2.Search 3.Inorder 4.Preorder 5.Postorder 6.Exit Enter the choice:6

RESULT: Thus the Binary Search tree is implemented and possible operations are performed successfully. EX:NO:7

AVL TREE INSERTION

DATE: AIM: To write a C program to implement insertion in AVL trees. ALGORITHM: 1. Initialize all variables and functions. 2. To insert and element read the value. 3. Check whether root is null 4. If yes make the new value as root. 5. Else check whether the value is equal to root value. 6. if yes, print “duplicate value”. 7. Otherwise

insert

the

value

at

its

proper

position

and

balance the tree using rotations. 8. To display the tree values check whether the tree is null. 9. If yes, print “tree is empty”. 10.Else print all the values in the tree form and in order of the tree. 11.Repeat the steps 2 to 10 for more values. 12.End.

**** Program for insertion in AVL tree **** #include<stdio.h> #include typedef enum { FALSE ,TRUE } bool; struct node { int info; int balance; struct node *lchild; struct node *rchild; }; struct node *insert (int , struct node *, int *); struct node* search(struct node *,int); main() { bool ht_inc; int info ; int choice; struct node *root = (struct node *)malloc(sizeof(struct node)); root = NULL; clrscr(); while(1) { printf("1.Insert\n"); printf("2.Display\n"); printf("3.Quit\n"); printf("Enter your choice : "); scanf("%d",&choice); switch(choice) { case 1: printf("Enter the value to be inserted : "); scanf("%d", &info); if( search(root,info) == NULL ) root = insert(info, root, &ht_inc); else printf("Duplicate value ignored\n");

break; case 2: if(root==NULL) { printf("Tree is empty\n"); continue; } printf("Tree is :\n"); display(root, 1); printf("\n\n"); printf("Inorder Traversal is: "); inorder(root); printf("\n"); break; case 3: exit(1); default: printf("Wrong choice\n"); }/*End of switch*/ }/*End of while*/ }/*End of main()*/ struct node* search(struct node *ptr,int info) { if(ptr!=NULL) if(info < ptr->info) ptr=search(ptr->lchild,info); else if( info > ptr->info) ptr=search(ptr->rchild,info); return(ptr); }/*End of search()*/ struct node *insert (int info, struct node *pptr, int *ht_inc) { struct node *aptr; struct node *bptr; if(pptr==NULL) { pptr = (struct node *) malloc(sizeof(struct node)); pptr->info = info; pptr->lchild = NULL; pptr->rchild = NULL; pptr->balance = 0; *ht_inc = TRUE; return (pptr); }

if(info < pptr->info) { pptr->lchild = insert(info, pptr->lchild, ht_inc); if(*ht_inc==TRUE) { switch(pptr->balance) { case -1: /* Right heavy */ pptr->balance = 0; *ht_inc = FALSE; break; case 0: /* Balanced */ pptr->balance = 1; break; case 1: /* Left heavy */ aptr = pptr->lchild; if(aptr->balance == 1) { printf("Left to Left Rotation\n"); pptr->lchild= aptr->rchild; aptr->rchild = pptr; pptr->balance = 0; aptr->balance=0; pptr = aptr; } else { printf("Left to right rotation\n"); bptr = aptr->rchild; aptr->rchild = bptr->lchild; bptr->lchild = aptr; pptr->lchild = bptr->rchild; bptr->rchild = pptr; if(bptr->balance == 1 ) pptr->balance = -1; else pptr->balance = 0; if(bptr->balance == -1) aptr->balance = 1; else aptr->balance = 0; bptr->balance=0; pptr=bptr; } *ht_inc = FALSE;

}/*End of switch */ }/*End of if */ }/*End of if*/ if(info > pptr->info) { pptr->rchild = insert(info, pptr->rchild, ht_inc); if(*ht_inc==TRUE) { switch(pptr->balance) { case 1: /* Left heavy */ pptr->balance = 0; *ht_inc = FALSE; break; case 0: /* Balanced */ pptr->balance = -1; break; case -1: /* Right heavy */ aptr = pptr->rchild; if(aptr->balance == -1) { printf("Right to Right Rotation\n"); pptr->rchild= aptr->lchild; aptr->lchild = pptr; pptr->balance = 0; aptr->balance=0; pptr = aptr; } else { printf("Right to Left Rotation\n"); bptr = aptr->lchild; aptr->lchild = bptr->rchild; bptr->rchild = aptr; pptr->rchild = bptr->lchild; bptr->lchild = pptr; if(bptr->balance == -1) pptr->balance = 1; else pptr->balance = 0; if(bptr->balance == 1) aptr->balance = -1; else aptr->balance = 0; bptr->balance=0;

pptr = bptr; }/*End of else*/ *ht_inc = FALSE; }/*End of switch */ }/*End of if*/ }/*End of if*/ return(pptr); }/*End of insert()*/ display(struct node *ptr,int level) { int i; if ( ptr!=NULL ) { display(ptr->rchild, level+1); printf("\n"); for (i = 0; i < level; i++) printf(" "); printf("%d", ptr->info); display(ptr->lchild, level+1); }/*End of if*/ }/*End of display()*/ inorder(struct node *ptr) { if(ptr!=NULL) { inorder(ptr->lchild); printf("%d ",ptr->info); inorder(ptr->rchild); } }/*End of inorder()*/ OUTPUT: 1.Insert 2.Display 3.Quit Enter your choice : 1 Enter the value to be inserted : 12 1.Insert 2.Display 3.Quit Enter your choice : 1

Enter the value to be inserted : 34 1.Insert 2.Display 3.Quit Enter your choice : 1 Enter the value to be inserted : 56 Right to Right Rotation 1.Insert 2.Display 3.Quit Enter your choice : 1 Enter the value to be inserted : 2 1.Insert 2.Display 3.Quit Enter your choice : 1 Enter the value to be inserted : 9 Left to right rotation 1.Insert 2.Display 3.Quit Enter your choice : 2 Tree is : 56 34 12 9 2 Inorder Traversal is: 2 9 12 34 56 1.Insert 2.Display 3.Quit Enter your choice : 3

RESULT:

Thus the AVL tree is implemented and the insertion operation is performed successfully. EX:NO:8

PRIORITY QUEUE USIGN BINARY HEAPS

DATE: AIM: To write a C program to implement Priority Queue using Binary Heaps. ALGORITHM: 1. Initialize all necessary variables and functions. 2. Read the choices. 3. For insertion, read the element to be inserted. 4. If root is NULL, assign the given element as root. 5. If the element is equal to the root, print “Duplicate value”. 6. Else if element value is less than the root value, insert element at the left of the root. 7. Else insert right side of the root. 8. For deletion, get the priority for maximum or minimum. 9. If maximum, it deletes the root and rearranges the tree. 10.If minimum, it deletes the leaf. 11.End of the program.

**** PRIORITY QUEUE USING BINARY HEAP **** #include<stdio.h> #include #include <stdlib.h> enum {FALSE=0,TRUE=-1}; struct Node { struct Node *Previous; int Data; struct Node *Next; }Current; struct Node *head; struct Node *ptr; static int NumOfNodes; int PriorityQueue(void); int Maximum(void); int Minimum(void); void Insert(int); int Delete(int); void Display(void); int Search (int); void main() { int choice; int DT; clrscr(); PriorityQueue(); while(1) { printf("\nEnter ur Choice:"); printf("\n1.Insert\n2.Display\n3.Delete\n4.Search\n5.Exit\n"); scanf("%d",&choice); switch(choice) { case 1: printf("\nEnter a data to enter Queue");

scanf("%d",&DT); Insert(DT); break; case 2: Display(); break; case 3: { int choice,DataDel; printf("\nEnter ur choice:"); printf("\n1.Maximum Priority queue\n2.Minimum priority Queue\n"); scanf("%d",&choice); switch(choice) { case 1: DataDel=Maximum(); Delete(DataDel); printf("\n%d is deleted\n",DataDel); break; case 2: DataDel=Minimum(); Delete(DataDel); printf("\n%d is deleted\n",DataDel); break; default: printf("\nSorry Not a correct Choice\n"); } } break; case 4: printf("\nEnter a data to Search in Queue:"); scanf("%d",&DT); if(Search(DT)!=FALSE) printf("\n %d is present in queue",DT); else printf("\n%d is not present in queue",DT); break; case 5: exit(0); default: printf("\nCannot process ur choice\n"); } } } int PriorityQueue(void)

{ Current.Previous=NULL; printf("\nEnter first element of Queue:"); scanf("%d",&Current.Data); Current.Next=NULL; head=&Current; ptr=head; NumOfNodes++; return; } int Maximum(void) { int Temp; ptr=head; Temp=ptr->Data; while(ptr->Next!=NULL) { if(ptr->Data>Temp) Temp=ptr->Data; ptr=ptr->Next; } if(ptr->Next==NULL && ptr->Data>Temp) Temp=ptr->Data; return(Temp); } int Minimum(void) { int Temp; ptr=head; Temp=ptr->Data; while(ptr->Next!=NULL) { if(ptr->Data Data; ptr=ptr->Next; } if(ptr->Next==NULL && ptr->Data Data; return(Temp); } void Insert(int DT) { struct Node *newnode;

newnode=(struct Node *)malloc(sizeof(struct Node)); newnode->Next=NULL; newnode->Data=DT; while(ptr->Next!=NULL) ptr=ptr->Next; if(ptr->Next==NULL) { newnode->Next=ptr->Next; ptr->Next=newnode; } NumOfNodes++; } int Delete(int DataDel) { struct Node *mynode,*temp; ptr=head; if(ptr->Data==DataDel) { temp=ptr; ptr=ptr->Next; ptr->Previous=NULL; head=ptr; NumOfNodes--; return(TRUE); } else { while(ptr->Next->Next!=NULL) { if(ptr->Next->Data==DataDel) { mynode=ptr; temp=ptr->Next; mynode->Next=mynode->Next->Next; mynode->Next->Previous=ptr; free(temp); NumOfNodes--; return(TRUE); } ptr=ptr->Next; } if(ptr->Next->Next==NULL && ptr->Next->Data==DataDel) { temp=ptr->Next; free(temp); ptr->Next=NULL;

NumOfNodes--; return(TRUE); } } return(FALSE); } int Search(int DataSearch) { ptr=head; while(ptr->Next!=NULL) { if(ptr->Data==DataSearch) return ptr->Data; ptr=ptr->Next; } if(ptr->Next==NULL && ptr->Data==DataSearch) return ptr->Data; return(FALSE); } void Display(void) { ptr=head; printf("\nPriority Queue is as Follows:-\n"); while(ptr!=NULL) { printf("\t\t%d",ptr->Data); ptr=ptr->Next; } } OUTPUT: Enter first element of queue: 3 Enter ur Choice: 1.Insert 2.Display 3.Delete 4.Search 5.Exit 1 Enter a data to enter Queue11

Enter ur Choice: 1.Insert 2.Display 3.Delete 4.Search 5.Exit 2 Priority Queue is as Follows:3 Enter ur Choice: 1.Insert 2.Display 3.Delete 4.Search 5.Exit 3

11

Enter ur choice: 1.Maximum Priority queue 2.Minimum priority Queue 1 11 is deleted Enter ur Choice: 1.Insert 2.Display 3.Delete 4.Search 5.Exit 4 Enter a data to Search in Queue:3 3 is present in queue Enter ur Choice: 1.Insert 2.Display 3.Delete 4.Search 5.Exit 5

RESULT: Thus the Priority Queue using Binary Heap is implemented and the result is verified successfully. EX:NO:9

HASHING WITH OPEN ADDRESSING (LINEAR PROBING)

DATE: AIM: To

write

a

C

program

to

implement

hashing

with

open

addressing (Linear Probing). ALGORITHM: 1. Initialize all necessary variables and functions. 2. Read the number to be inserted in the hash table. 3. Find the location to insert using num % size. 4. If any value is present at that position then find the next unoccupied location. 5. Else if key value is greater than the maximum table size then print “Hash Table is full”. 6. Repeat the steps 1 to 5 to insert more values. 7. End of the program.

****Program for Hash Table with Open Addressing **** #include<stdio.h> #include #include<stdlib.h> #define max 10 void main() { int a[max],num,key,i; char ans; int create(int); void hash(int [],int,int); void display(int[]); clrscr(); printf("\nhash table\n"); for(i=0;i<max;i++) a[i]=-1; do { printf("\n enter the number:"); scanf("%d",&num); key=create(num); hash(a,key,num); printf("\ndo u want to continue"); ans=getche(); }while(ans=='y'); display(a); getch(); } int create(int num) { int key; key=num % 10; return key; } void hash(int a[max],int key,int num)

{ int flag,i,count=0; void display(int a[]); flag=0; if(a[key]==-1) a[key]=num; else { i=0; while(i<max) { if(a[i]!= -1) count++; i++; } if(count==max) { printf("\n hashtable is full"); display(a); getch(); exit(1); } for(i=key+1;i<max;i++) if(a[i]==-1) { a[i]=num; flag=1; break; } for(i=0;i
OUTPUT: hash table enter the number:131 do u want to continue y enter the number:21 do u want to continue y enter the number:3 do u want to continue y enter the number:4 do u want to continue y enter the number:5 do u want to continue n The hash table is.......... 0 1 2 3 4 5 6 7 8 9

-1 131 21 3 4 5 -1 -1 -1 -1

RESULT: Thus the program for hashing using open addressing (Linear Probing) is implemented successfully. EX:NO:10

PRIMS ALGORITHM

DATE: AIM: To write a C program to implement Prim's algorithm using priority queues to find MST of an undirected graph. ALGORITHM: 1. (Initializations). O={1} (V(1) root of the T tree). P={2,...,n} For every j belonging to P :e(j):=c[e(j1)] , p(j)=1 all peaks connected to the root. 2. By definition of the cost function:e(j)=infinite when V(j) does not connect to V(1).). 3. Choose a k for which e(k)<=e(j) for every j belonging to P. 4. In case of tight choose the smaller one. Exchange the O set with the set produced by the union of the O set and {k}. 5. Exchange the P set with the set produced by the difference of the P set and {k}. 6. (P<-P-{k}) If P=0 then stop. 7. For every j belonging to P compare e(j) with c[e(kj)]. 8. If e(j) >c[e(kj)] exchange e(j) <-c(e(kj)). 9. Go back to Step 1.

****program for prim's algorithm **** #include<stdio.h> #include #include<stdlib.h> #define size

8

int cost[size][size]={0},n=0; void get_mat() { int i,j,v1,v2,wt; for(i=0;i<=size;i++) for(j=0;j<=size;j++) cost[i][j]=1000; printf("\nEnter the no. of vertices:"); scanf("%d",&n); do { printf("\nEnter the edge & their weight(v1 v2,wt):"); scanf("%d%d%d",&v1,&v2,&wt); cost[v1][v2]=cost[v2][v1]=wt; printf("\nContinue:"); fflush(stdin); }while(getche()=='y'); } void main() { int t[size]={0},wt[size]={0},min,p,sum=0,temp,i,j,k=0,l=0,m=0; clrscr(); get_mat(); t[1]=1; printf("\n\ntree includes following edges:"); for(p=1;p<=n-1;p++) { temp=1000; for(i=1;i<=n;i++) {

if(t[i]==1) { min=1000; for(j=1;j<=n;j++) { if(cost[i][j]<min && t[j]==0) { min=cost[i][j]; k=j; } } if(min < temp) { temp=min; l=k; m=i; } } } wt[p]=cost[m][l]; sum=sum+wt[p]; printf("\nedge:%d%d wt:%d",m,l,cost[m][l]); t[l]=t[m]=1; } printf("\n\n weight of minimum spanning tree: %d",sum); getch(); } OUTPUT: Enter the no. of vertices:5 Enter the edge & their weight(v1 v2,wt):1 2 3 Continue:y Enter the edge & their weight(v1 v2,wt):1 4 3 Continue:y Enter the edge & their weight(v1 v2,wt):2 3 1 Continue:y Enter the edge & their weight(v1 v2,wt):3 4 2 Continue:y Enter the edge & their weight(v1 v2,wt):2 5 4 Continue:y

Enter the edge & their weight(v1 v2,wt):4 5 3 Continue:y Enter the edge & their weight(v1 v2,wt):3 5 1 Continue:n tree includes following edges: edge:12 wt:3 edge:23 wt:1 edge:35 wt:1 edge:34 wt:2 weight of minimum spanning tree: 7

RESULT: Thus the Prim's algorithm using priority queues is implemented and MST of an undirected graph is found successfully.