Ex.

No: 1 BANKING USING STRUCTURE

PROGRAM: #include<stdio.h> #include<conio.h> void create(); void display(); void deposit(); void withdraw(); struct bank { int accno; char name[25]; char acctype[10]; float balance; }acc; void create() { float bal; acc.balance=0; printf("\nEnter your a/c.no"); scanf("%d",&acc.accno); fflush(stdin); printf("\n Enter your name"); gets(acc.name); printf("\nEnter your account type"); scanf("%s",acc.acctype); printf("\n Enter the initial deposit"); scanf("%f",&bal); acc.balance+=bal; } void withdraw() { float amount; printf("\nEnter amount to withdraw"); scanf("%f",&amount); if(amount<acc.balance) { acc.balance-=amount; printf("\nthe available balance is %f",acc.balance); } else printf("\nWithdrawal is not possible"); } void deposit() { float amount; printf("Enter the amount to be deposited"); scanf("%f",&amount);

acc.balance+=amount; printf("\n the amount balance is %f",acc.balance); } void display() { printf("\n**********Account Details*********\n"); printf("\n Account Type %d",acc.accno); printf("a/c Holder Name:%s",acc.name); printf("Account Type:%f",acc.balance); } void main() { int i,ch; clrscr(); do { fflush(stdin); printf("\n\t\t*********Menu********\n"); printf("\n1.create"); printf("\n2.deposit"); printf("\n3.withdraw"); printf("\n4.display"); printf("\n5.exit"); printf("enter your choice"); scanf("%d",&ch); switch(ch) { case 1: create(); break; case 2: deposit(); break; case 3: withdraw(); break; case 4: display(); break; case 5: printf("\n Thank you for using the system"); break; default: printf("\nWrong choice"); } } while(ch!=5); getch(); }

OUTPUT PROGRAM *********Menu******** 1.create 2.deposit 3.withdraw 4.display 5.exitenter your choice1 Enter your a/c.no1234 Enter your name Jithu Enter your account type SB Enter the initial deposit 1000 *********Menu******** 1.create 2.deposit 3.withdraw 4.display 5.exitenter your choice2 Enter the amount to be deposited 500 the amount balance is 1500.000000 *********Menu******** 1.create 2.deposit 3.withdraw 4.display 5.exitenter your choice3 Enter amount to withdraw 500 the available balance is 1000.000000 *********Menu******** 1.create 2.deposit 3.withdraw 4.display 5.exitenter your choice4 **********Account Details********* Account Type 1234a/c Holder Name: JithuAccount Type:1000.000000 2. LIST USING ARRAY #include<stdio.h> #include<conio.h> #define maxsize 10 int list[25],index=-1; void create(); void del(); void insert(); void display(); void main() { int choice; clrscr(); do { printf("\n1.CREATE"); printf("\n2.INSERT"); printf("\n3.DELETE"); printf("\n4.DISPLAY"); printf("\n5.EXIT"); printf("\nEnter your choice"); scanf("%d",&choice); switch(choice) { case 1: create(); break; case 2: insert(); break; case 3: del(); break; case 4: display(); break; case 5: exit(1); } }while(choice!=5); getch(); } void create() { int i,n; printf("\nEnter the no.of elements to be added in thelist"); scanf("%d",&n); if(n<=maxsize) for(i=0;i<n;i++)

{ scanf("%d",&list[i]); index++; } else printf("\nThe size is limited.You cannot add data to the list"); printf("\nThe index is %d",index); } void insert() { int i,data,pos; printf("\nEnter the data to be inserted"); scanf("%d",&data); printf("\nEnter the position at which the element is to be inserted"); scanf("%d",&pos); if(index<=maxsize) { for(i=index;i>=pos-1;i--) list[i+1]=list[i]; index++; list[pos-1]=data; } else printf("\nThe list is full"); } void del() { int i,pos; printf("\nEnter the position of the data to be deleted"); scanf("%d",&pos); printf("\nThe data deleted is %d",list[pos-1]); for(i=pos;i<=index;i++) list[i-1]=list[i]; index--; } void display() { int i; for(i=0;i<=index;i++) printf("\t%d",list[i]); } OUTPUT 1.CREATE 2.INSERT 3.DELETE 4.DISPLAY

5.EXIT Enter your choice1 Enter the no. of elements to be added in thelist3 1 2 3 The index is 2 1.CREATE 2.INSERT 3.DELETE 4.DISPLAY 5.EXIT Enter your choice2 Enter the data to be inserted6 Enter the position at which the element is to be inserted2 1.CREATE 2.INSERT 3.DELETE 4.DISPLAY 5.EXIT Enter your choice4 1 6 2 1.CREATE 2.INSERT 3.DELETE 4.DISPLAY 5.EXIT Enter your choice3

Enter the position of the data to be deleted2 3. SINGLY LINKED LIST PROGRAM #include<stdio.h> #include<conio.h> void insert(); void delete(); void display(); void find(); struct list { int info; struct list *next;

}*ptr,*prev,*temp,*head=NULL; void main() { int choice; clrscr(); do { printf("\n1.Insert"); printf("\n2.Delete"); printf("\n3.Display"); printf("\n4.Find"); printf("\n5.Exit"); printf("\nEnter your option"); scanf("%d",&choice); switch(choice) { case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: find(); break; case 5: exit(1); } } while(choice!=5); getch(); } void insert() { int pos,i; temp=(struct list*)malloc(sizeof(struct list)); printf("\nEnter the data to be inserted"); scanf("%d",&temp->info); if(head==NULL) { head=temp; head->next=NULL; } else { printf("\n Enter the position to be inserted"); scanf("%d",&pos); if(pos==1) {

temp->next=head; head=temp; } else { prev=head; for(i=1;i<pos-1&&prev->next!=NULL;i++) prev=prev->next; prev->next=temp; } } } void delete() { int pos,i; if(head==NULL) printf("\nthe list is empty"); else printf("\nEnter the position of data to be deleted"); scanf("%d",&pos); temp=head; if(pos==1) { printf("\nThe deleted element is %d",temp>info); head=temp->next; } else { prev=head; for(i=1;i<pos-1;i++) prev=prev->next; ptr=prev->next; printf("The deleted element is %d",ptr->info); prev->next=ptr->next; } } void display() { if(head==NULL) printf("\nNo elements in the list"); else { printf("\nThe elements in the list are\n"); for(ptr=head;ptr!=NULL;ptr=ptr->next) printf("%d\t",ptr->info); } } void find() { int a,flag=0,count=0;

if(head==NULL) printf("\nThe list is empty"); else { printf("\nEnter the elements to be searched"); scanf("%d",&a); for(ptr=head;ptr!=NULL;ptr=ptr->next) { count++; if(ptr->info==a) { flag=1; printf("\nThe element is found"); printf("\nThe position is %d",count); break; } } if(flag==0) printf("The element is not found"); } } OUTPUT 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option1 Enter the data to be inserted11 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option1 Enter the data to be inserted12 Enter the position to be inserted1 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option3 The elements in the list are 12 11

1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option4 Enter the elements to be searched11 The element is found The position is 2 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option2 Enter the position of data to be deleted 1 The deleted element is 12 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option3 The elements in the list are 11

4. DOUBLY LINKED LIST

PROGRAM #include<stdio.h> #include<conio.h> void insert(); void delete(); void display(); void find(); struct list { int info; struct list *next; struct list *prev; }*node,*ptr,*temp,*head=NULL; void main() { int choice;

clrscr(); do { printf("\n1.Insert"); printf("\n2.Delete"); printf("\n3.Display"); printf("\n4.Find"); printf("\n5.Exit"); printf("\nEnter your option"); scanf("%d",&choice); switch(choice) { case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: find(); break; case 5: exit(1); } }while(choice!=5); getch(); } void insert() { int pos,i; temp=(struct list*)malloc(sizeof(struct list)); printf("\nEnter the data to be inserted"); scanf("%d",&temp->info); if(head==NULL) { head=temp; head->next=NULL; head->prev=NULL; } else { printf("\n Enter the position to be inserted"); scanf("%d",&pos); if(pos==1) { temp->next=head; temp->prev=NULL; head->prev=temp; head=temp;

} else { ptr=head; for(i=1;i<pos-1&&ptr->next!=NULL;i++) { ptr=ptr->next; } temp->next=ptr->next; ptr->next=temp; temp->prev=ptr; ptr->next->prev=temp; } } } void delete() { int pos,i; if(head==NULL) printf("\nthe list is empty"); else printf("\nEnter the position of data to be deleted"); scanf("%d",&pos); temp=head; if(pos==1) { printf("\nThe deleted element is %d",temp>info); head=temp->next; head->prev=NULL; } else { ptr=head; for(i=1;i<pos-1;i++) ptr=ptr->next; node=ptr->next; printf("The deleted element is %d",node>info); ptr->next=node->next; } } void display() { if(head==NULL) printf("\nNo elements in the list"); else { printf("\nThe elements in the stack are\n"); for(ptr=head;ptr!=NULL;ptr=ptr->next) printf("%d\t",ptr->info);

} } void find() { int a,flag=0,count=0; if(head==NULL) printf("\nThe list is empty"); else { printf("\nEnter the element to be searched"); scanf("%d",&a); for(ptr=head;ptr!=NULL;ptr=ptr->next) { count++; if(ptr->info==a) { flag=1; printf("\nThe element is found"); printf("\nThe position is %d",count); break; } } if(flag==0) printf("The element is not found"); } } OUTPUT 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option1 Enter the data to be inserted5 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option1 Enter the data to be inserted6 Enter the position to be inserted1 1.Insert 2.Delete 3.Display

4.Find 5.Exit Enter your option3 The elements in the stack are 6 5 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option2 Enter the position of data to be deleted1 The deleted element is 6 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option2 Enter the position of data to be deleted1 The deleted element is 5 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option4 The list is empty 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option1 Enter the data to be inserted5 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option1 Enter the data to be inserted2

Enter the position to be inserted1 1.Insert 2.Delete 3.Display 4.Find 5.Exit Enter your option4 Enter the element to be searched2 The element is found The position is 1

display(); break; case 4: exit(1); } }while(choice!=4); getch(); } void push() { int data; if(top==maxsize) printf("\nStack Overflow"); else { top++; printf("\nEnter the data to be inserted "); scanf("%d",&data); stack[top]=data; } } void pop() { if(top==-1) printf("\nStack Underflow"); else { printf("\nThe deleted element in the stack is %d",stack[top]); top--; } } void display() { int i; if(top==-1) printf("\nNo elements in the stack"); else { printf("\nThe elements in the stack are \n"); for(i=0;i<=top;i++) printf("%d\t",stack[i]); } } OUTPUT 1.PUSH 2.POP 3.DISPLAY 4.EXIT

5. ARRAY IMPLEMENTATION OF STACK ADT

PROGRAM #include<stdio.h> #include<conio.h> #define maxsize 10 int stack[20],top=-1; void push(); void pop(); void display(); void main() { int choice; clrscr(); do { printf("\n1.PUSH"); printf("\n2.POP"); printf("\n3.DISPLAY"); printf("\n4.EXIT"); printf("\nEnter your option "); scanf("%d",&choice); switch(choice) { case 1: push(); break; case 2: pop(); break; case 3:

Enter your option 1 Enter the data to be inserted 100 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your option 1 Enter the data to be inserted 50 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your option 3 The elements in the stack are 100 50 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your option 2 The deleted element in the stack is 50 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your option 3 The elements in the stack are 100 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your option 4

6. LINKED LIST IMPLEMENTATION OF STACK ADT

PROGRAM #include<stdio.h> #include<conio.h> void push(); void pop(); void display();

struct stack { int info; struct stack *next; }*node,*ptr,*temp,*top=NULL; void main() { int choice; clrscr(); do { printf("\n1.PUSH"); printf("\n2.POP"); printf("\n3.DISPLAY"); printf("\n4.DISPLAY"); printf("\nEnter your choice"); scanf("%d",&choice); switch(choice) { case 1: push(); break; case 2: pop(); break; case 3: display(); break; case 4: exit(1); } }while(choice!=4); getch(); } void push() { int data; temp=(struct stack*)malloc(sizeof(struct stack)); printf("\nEnter the data to be inserted"); scanf("%d",&data); if(top==NULL) { top=temp; temp->info=data; temp->next=NULL; } else { temp->info=data; temp->next=top; top=temp;

} } void pop() { if(top==NULL) printf("\nStack is empty"); else { printf("\nThe deleted element is %d",top>info); top=top->next; } } void display() { int i; if(top==NULL) printf("\nThere are no elements in the stack"); else { printf("\nThe elements in the stack are\n"); for(ptr=top;ptr!=NULL;ptr=ptr->next) printf("%d\t",ptr->info); } } OUTPUT 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your choice 1 Enter the data to be inserted 20 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your choice 1 Enter the data to be inserted 40 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your choice 3 The elements in the stack are 40 20

1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your choice 2 The deleted element is 40 1.PUSH 2.POP 3.DISPLAY 4.EXIT Enter your choice 4 7. IMPLEMENTATION OF BALANCED PARENTHESIS USING STACK ADT

Main program
#include<stdio.h> #include<conio.h> #include"Z:STACK.C" void main() { char exp[50]; int i=0,n; clrscr(); printf("Enter the expression"); scanf("%s",exp); n=strlen(exp); for(i=0;i<=n;i++) { if(exp[i]=='(') push(exp[i]); else if(exp[i]==')') { if(top==NULL) { printf("\nUnbalanced Expression"); getch(); exit(1); } else pop(); } } if(top==NULL) printf("\nBalanced Parenthesis"); else printf("\nUnbalanced Parenthesis"); getch(); }

Sub Program
#include<stdio.h> #include<conio.h> struct stack { char element; struct stack *next; }*node,*temp,*top=NULL; void push(char x) { temp=(struct stack*)malloc(sizeof(struct stack)); temp->element=x; if(top==NULL) { top=temp; temp->next=NULL; } else { temp->next=top; top=temp; } } void pop() { if(top==NULL) printf("Stack Underflow"); else { temp=top; top=temp->next; free(temp); } } OUTPUT Enter the expression (A+B) Balanced Parenthesis

int queue[20],front=-1,rear=-1; void insert(); void delete(); void display(); void main() { int choice; clrscr(); do { printf("\n1.INSERT"); printf("\n2.DELETE"); printf("\n3.DISPLAY"); printf("\n4.EXIT"); printf("\nEnter your option"); scanf("%d",&choice); switch(choice) { case 1: insert(); break; case 2: delete(); break; case 3: display(); break; case 4: exit(1); } }while(choice!=4); getch(); } void insert() { int data; printf("\nEnter the element to be inserted"); scanf("%d",&data); if(rear==maxsize) printf("\nQueue is full"); else if(front==-1) { front++; rear++; queue[front]=data; } else { rear++; queue[rear]=data; }

8. QUEUE IMPLEMENTATION USING ARRAY

PROGRAM
#include<stdio.h> #include<conio.h> #define maxsize 10

} void delete() { if(front==-1) printf("\nQueue is empty"); else if(front==rear) { printf("\nThe deleted element is %d",queue[front]); front=-1; rear=-1; } else { printf("\nThe deleted element is %d",queue[front]); front++; } } void display() { int i; if(front==-1) printf("\nNo elements in the queue"); else { printf("\nThe elements in the queue are\n"); for(i=front;i<=rear;i++) printf("%d\t",queue[i]); } } OUTPUT 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option 1 Enter the element to be inserted 50 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option 1 Enter the element to be inserted 20 1.INSERT 2.DELETE

3.DISPLAY 4.EXIT Enter your option 2 The deleted element is 50 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option 3 The elements in the queue are 20 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option 4

9. POLYNOMIAL ADDITION USING LINKED LIST

PROGRAM #include<stdio.h> #include<conio.h> #include<malloc.h> struct link { int coeff; int pow; struct link *next; }; struct link *poly1=NULL,*poly2=NULL,*poly=NULL; void create(struct link *node) { char ch; do { printf("\n Enter Coeff\n "); scanf("%d",&node->coeff); printf("\nEnter power \n"); scanf("%d",&node->pow); node->next=(struct link*)malloc(sizeof(struct link)); node=node->next; node->next=NULL; printf("\nContinue(y/n): "); ch=getch(); }

while(ch=='y'||ch=='y'); } void show(struct link *node) { while(node->next!=NULL) { printf("%dx^%d",node->coeff,node->pow); node=node->next; if(node->next!=NULL) printf("+"); } } void polyadd(struct link *poly1,struct link *poly2,struct link *poly) { while(poly1->next&&poly2->next) { if(poly1->pow>poly2->pow) { poly->pow=poly1->pow; poly->coeff=poly1->coeff; poly1=poly1->next; } else if(poly1->pow<poly2->pow) { poly->pow=poly2->pow; poly->coeff=poly2->coeff; poly2=poly2->next; } else { poly->pow=poly1->pow; poly->coeff=poly1->coeff+poly2->coeff; poly1=poly1->next; poly2=poly2->next; } poly->next=(struct link*)malloc(sizeof(struct link)); poly=poly->next; poly->next=NULL; } while(poly1->next||poly2->next) { if(poly1->next) { poly->pow=poly1->pow; poly->coeff=poly1->coeff; poly1=poly1->next; } if(poly2->next) { poly->pow=poly2->pow;

poly->coeff=poly2->coeff; poly2=poly2->next; } poly->next=(struct link*)malloc(sizeof(struct link)); poly=poly->next; poly->next=NULL; } } void main() { char ch; clrscr(); do { poly1=(struct link*)malloc(sizeof(struct link)); poly2=(struct link*)malloc(sizeof(struct link)); poly=(struct link*)malloc(sizeof(struct link)); printf("\nEnter 1st number: \n"); create(poly1); printf("\n\nEnter 2nd number:\n "); create(poly2); printf("\n\n1st number\n"); show(poly1); printf("\n\n2nd number\n "); show(poly2); polyadd(poly1,poly2,poly); printf("\n\nAdded polynomial\n"); show(poly); printf("\n\nAdd two more numbers "); ch=getch(); } while(ch=='y'||ch=='y'); } OUTPUT Enter 1st number: Enter Coeff 3 Enter power 2 Continue(y/n): Enter 2nd number:

Enter Coeff 4 Enter power 2 Continue(y/n): 1st number 3x^2 2nd number 4x^2 Added polynomial 7x^2 Add two more numbers

while(top!=-1) { output[j]=stack[top]; top--; j++; } } printf("\n\n%s",output); getch(); } OUTPUT Enter the expression A+B AB+

11. DOUBLE ENDED QUEUE

PROGRAM

10. CONVERSION OF INFIX TO POSTFIX

PROGRAM #include<stdio.h> #include<conio.h> #include<ctype.h> char input[20],output[20],stack[20],top=-1; void main() { int i,j=0,n; clrscr(); printf("\nEnter the expression "); scanf("%s",input); n=strlen(input); for(i=0;input[i]!='\0';i++) { if(isalpha(input[i])) { output[j]=input[i]; j++; } else { top++; stack[top]=input[i]; } } if(i==n) {

#include<stdio.h> #include<conio.h> void insert(); void delete(); void display(); struct queue { int data; struct queue *next; struct queue *prev; }*temp,*front=NULL,*rear=NULL,*ptr; void main() { int choice; clrscr(); do { printf("\n1.INSERT"); printf("\n2.DELETE"); printf("\n3.DISPLAY"); printf("\n4.EXIT"); printf("\n\nEnter your option"); scanf("%d",&choice); switch(choice) { case 1: insert(); break; case 2: delete(); break;

case 3: display(); break; case 4: exit(1); } }while(choice!=4); getch(); } void insert() { int n,a; printf("\n\nEnter the element"); scanf("%d",&a); printf("\n\nWhere do you want to insert"); printf("\n\n1.Front side"); printf("\n2.Rear Side"); printf("\n\nEnter the option"); scanf("%d",&n); switch(n) { case 1: temp=(struct queue*)malloc(sizeof(struct queue)); temp->data=a; if(front==NULL&&rear==NULL) { temp->next=NULL; temp->prev=NULL; front=temp; rear=temp; } else { temp->next=front; front->prev=temp; temp->prev=NULL; front=temp; } break; case 2: temp=(struct queue*)malloc(sizeof(struct queue)); temp->data=a; rear->next=temp; temp->prev=rear; temp->next=NULL; rear=temp; } } void delete() {

int n; printf("\n\nWhere do you want to delete"); printf("\n\n1.Front side"); printf("\n2.Rear Side"); printf("\n\nEnter the option"); scanf("%d",&n); switch(n) { case 1: printf("\n\nThe deleted element is %d",front>data); front=front->next; front->prev=NULL; break; case 2: printf("\n\nThe deleted element is %d",rear>data); rear=rear->prev; rear->next=NULL; } } void display() { if(front==NULL&&rear==NULL) printf("\n\nThe queue is empty"); else for(ptr=front;ptr!=NULL;ptr=ptr->next) printf("%d\t",ptr->data); }

OUTPUT 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option 1 Enter the element 20 Where do you want to insert 1.Front side 2.Rear Side Enter the option 1 1.INSERT 2.DELETE 3.DISPLAY

4.EXIT Enter your option 1 Enter the element 10 Where do you want to insert 1.Front side 2.Rear Side Enter the option 2 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option 3 20 10 1.INSERT 2.DELETE 3.DISPLAY 4.EXIT Enter your option2 Where do you want to delete 1.Front side 2.Rear Side Enter the option1 The deleted element is 20 1.INSERT 2.DELETE 3.DISPLAY

12. BINARY TREE TRAVERSALS

PROGRAM #include<stdio.h> #include<stdlib.h> struct tree { char data[10]; struct tree *lchild,*rchild; }*p,*rdata[30];

inorder(struct tree *cnode) { if(cnode!=NULL) { inorder(cnode->lchild); if(cnode->data!=NULL) printf("%s\t",cnode->data); inorder(cnode->rchild); } return; } preorder(struct tree *cnode) { if(cnode!=NULL) { if(cnode->data!=NULL) printf("%s\t",cnode->data); preorder(cnode->lchild); preorder(cnode->rchild); } return; } postorder(struct tree *cnode) { if(cnode!=NULL) { postorder(cnode->lchild); postorder(cnode->rchild); if(cnode->data!=NULL) printf("%s\t",cnode->data); } return; } void main() { int i,n; clrscr(); printf("\n\nEnter the no.of nodes: \n"); scanf("%d",&n); printf("\n\nEnter the element: "); for(i=1;i<=n;i++) { rdata[i]=malloc(sizeof(struct tree)); scanf("%s",&rdata[i]->data); rdata[i]->lchild=NULL; rdata[i]->lchild=NULL; } for(i=1;i<=n;i++) { rdata[i]->lchild=rdata[2*i]; rdata[i]->rchild=rdata[(2*i)+1]; p=rdata[1];

} printf("\n\n\nGiven order: "); for(i=1;i<=n;i++) printf("%s\t",rdata[i]->data); printf("\n\n\nInorder traversal: "); inorder(p); printf("\n\n\nPreorder traversal: "); preorder(p); printf("\n\n\nPostorder traversal: "); postorder(p); getch(); } OUTPUT Enter the no.of nodes: 5 Enter the element: 10 20 Given order: 10 20 30 30 40 50 40 20 40 50 10 50 30 30 30 10 50

Inorder traversal: 40 20 Preorder traversal: 10 20 Postorder traversal: 40 50

13. BINARY SEARCH TREE PROGRAM ADT PROGRAM #define NULL 0 #include<alloc.h> typedef int elementtype; typedef struct treenode *position; typedef struct treenode *searchtree; struct treenode { elementtype element; searchtree left; searchtree right; }; searchtree makeempty(searchtree t) {

if(t!=NULL) { makeempty(t->left); makeempty(t->right); free(t); } return NULL; } position find(elementtype x,searchtree t) { searchtree t3=t; if(t3==NULL) return NULL; if(x<t3->element) return find(x,t3->left); if(x>t->element) return find(x,t3->right); return t3; } searchtree insert(elementtype x,searchtree t) { if(t==NULL) { t=malloc(sizeof(struct treenode)); if(t==NULL) printf("\nNo Space"); else { t->element=x; t->left=t->right=NULL; return t; } } 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) { searchtree t1=t; if(t1!=NULL) while(t1->left!=NULL) t1=t1->left; return t1; } position findmax(searchtree t) { searchtree t2=t;

if(t2!=NULL) while(t2->right!=NULL) t2=t2->right; return t2; } void display(searchtree t) { if(t!=NULL) { display(t->left); printf("%d\n",t->element); display(t->right); } } MAIN PROGRAM #include<stdio.h> #include<conio.h> #include<process.h> #include"z:biseatre.c" void main() { int ch,x; searchtree min,max,ins,t=NULL,t1=NULL,t2=NULL,t3 =NULL; clrscr(); while(1) { printf("\n1-> Make empty\n2-> Findmin\n3-> Findmax\n4-> Insert\n5-> Find\n6-> Display\n7-> Exit\n"); printf("\nEnter the choice "); scanf("%d",&ch); switch(ch) { case 1: t=makeempty(t); break; case 2: t1=findmin(t); if(t1==NULL) printf("\nTree is empty"); else printf("\nmin=%d\n",t1->element); break; case 3: t2=findmax(t); if(t2==NULL) printf("\ntree is empty"); else printf("\nmax=%d\n",t2->element);

break; case 4: printf("\nEnter the number to be inserted"); scanf("%d",&x); t=insert(x,t); printf("\ninserted node is %d\n",x); break; case 5: printf("\nEnter the element to be searched "); scanf("%d",&x); t3=find(x,t); if(x==t3->element) printf("\nThe element %d is found\n",t3->element); else printf("\nThe element is not found\n"); break; case 6: if(t==NULL) printf("\nTree is empty"); else printf("\nThe data are\n"); display(t); break; case 7: exit(0); } } } OUTPUT 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 4 Enter the number to be inserted 10 inserted node is 10 1-> Make empty 2-> Findmin 3-> Findmax

4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 4 Enter the number to be inserted 20 inserted node is 20 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 4 Enter the number to be inserted 30 inserted node is 30 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 4 Enter the number to be inserted 40 inserted node is 40 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 4 Enter the number to be inserted 50 inserted node is 50

1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 2 min=10 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 3 max=50 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 5 Enter the element to be searched 20 The element 20 is found 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 6 The data are 10 20

30 40 50 1-> Make empty 2-> Findmin 3-> Findmax 4-> Insert 5-> Find 6-> Display 7-> Exit Enter the choice 7

14. PRIORITY QUEUE USING BINARY HEAPS

PROGRAM #include<stdio.h> #include<conio.h> #define MAX_SIZE 10 typedef struct { unsigned char priority; unsigned char packetType; unsigned int destinationAddress; unsigned int sourceAddress; char payload[26]; }packet; typedef struct { packet* packets[MAX_SIZE]; unsigned int size; }packetheap; void heap_intit(packetheap* h) { h->size=0; } void heap_heapify(packetheap* h,int i) { int l,r,smallest; packet* tmp; l=2*i; r=2*i+1; if((l<h->size)&&(h->packets[l]->priority<h>packets[i]->priority)) smallest=l; else smallest=i; if((r<h->size)&&(h->packets[r]->priority<h>packets[smallest]->priority))

smallest=r; if(smallest!=i) { tmp=h->packets[smallest]; h->packets[smallest]=h->packets[i]; h->packets[i]=tmp; heap_heapify(h,smallest); } } void heap_additem(packetheap* h,packet* packet) { unsigned int i,parent; h->size=h->size+1; i=h->size-1; parent=i/2; while((i>0)&&(h->packets[parent]>priority>packet->priority)) { h->packets[i]=h>packets[parent]; i=parent; parent=i/2; } h->packets[i]=packet; } packet* heap_extractmin(packetheap* h) { packet* max; if(heap_isempty(h)) return 0; max=h->packets[0]; h->packets[0]=h->packets[h->size-1]; h->size=h->size-1; heap_heapify(h,0); return max; } int heap_isempty(packetheap *h) { return h->size==0; } int heap_isfull(packetheap *h) { return h->size>=MAX_SIZE; } int main() { packetheap heap; unsigned char i; packet p[10]; clrscr(); p[0].priority=123;

p[1].priority=23; p[2].priority=0; p[3].priority=22; p[4].priority=255; p[5].priority=1; p[6].priority=10; p[7].priority=3; p[8].priority=101; p[9].priority=102; heap_intit(&heap); for(i=0;i<10;i++) { printf("Add %i\n",p[i].priority); heap_additem(&heap,&(p[i])); } while(!heap_isempty(&heap)) { i=heap_extractmin(&heap)->priority; printf("%i\n",i); } getch(); } OUTPUT Add123 Add23 Add0 Add22 Add255 Add1 Add10 Add3 Add101 Add102 0 1 3 10 22 23 101 102 123 255

#include<stdio.h> #include<conio.h> #include<stdlib.h> #define MAX 10 void main() { int a[MAX],num,key,i; char ans; int create(int); void linear_prob(int[],int,int),display(int[]); clrscr(); printf("\n\nCollision Handling by linear probing"); for(i=0;i<=MAX;i++) a[i]=-1; do { printf("\n\nEnter the number ); scanf("%d",&num); key=create(num); linear_prob(a,key,num); printf("\n\nDo you want tocontinue(y/n)"); ans=getche(); }while(ans=='y'); display(a); getch(); } int create(int num) { int key; key=num%10; return key; } void linear_prob(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) {

15. HASHING WITH OPEN ADDRESSING

PROGRAM

printf("\n\nHash table 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<key&&flag==0;i++) if(a[i]=-1) { a[i]=num; flag=1; break; } for(i=0;i<key&&flag==0;i++) if(a[i]==-1) { a[i]=num; flag=1; break; } } } void display(int a[MAX]) { int i; printf("\n\nThe hash table is.......\n"); for(i=0;i<MAX;i++) printf("\n\n%d%d",i,a[i]); } OUTPUT Collision Handling by linear probing Enter the number 10 Do you want to continue(y/n) y Enter the number 20 Do you want to continue(y/n) y Enter the number 30

Do you want to continue(y/n) y Enter the number 40 Do you want to continue(y/n) y Enter the number 50 Do you want to continue(y/n) n The hash table is....... 0 10 1 20 2 30 3 40 4 50 5 -1 6 -1 7 -1 8 -1 9 -1

16. BACKTRACKING ALGORITHM FOR KNAPSACK PROBLEM

PROGRAM #include<stdio.h> #include<conio.h> float final_profit=-1.0; int p[9]={0,11,21,31,33,43,53,55,65}; int w[9]={0,1,11,21,33,43,45,55}; int m=110; int n=8; int temp[9],x[9]; float final_wt=-1.0; float bound_calculation(int cp,int cw,int k)

{ int ub,c,i; ub=cp; c=cw; for(i=k+1;i<=n;i++) { c=c+w[i]; if(c<m) ub=ub+p[i]; else return (ub+(1-(cm)/w[i]*p[i])); } return ub; } void bk(int k,int cp,int cw) { int new_k,new_cp,new_cw,j; if(cw+w[k]<=m) { temp[k]=1; if(k<n) { new_k=k+1; new_cp=cp+p[k]; new_cw=cw+w[k]; bk(new_k,new_cp,new_cw); } if((new_cp>final_profit)&&(k==n)) { final_profit=new_cp; final_wt=new_cw; for(j=1;j<=k;j++) x[j]=temp[j]; } } if(bound_calculation(cp,cw,k)>=final_profit) { temp[k]=0; if(k<n) bk(k+1,cp,cw); if((cp>final_profit)&&(k==n)) { final_profit=cp; final_wt=cw; for(j=1;j<=n;j++) x[j]=temp[j]; } }

} void main() { int i; clrscr(); printf("\n\n\tKnapsack Problem using Back Tracking algoritm\n"); printf("\n\nCapacity of Knapsack is %d",m); printf("\n\n\nProfit\tWeight"); printf("\n--------------"); bk(1,0,0); printf("\n\nThe following are selected items from knapsack......"); for(i=1;i<=n;i++) { if(x[i]==1) printf("\n\n\t\tItem %d",i); } printf("\n\n\nFinal Weight= %0.2f",final_wt); printf("\n\n\nFinal Profit= %0.2f",final_profit); getch(); } OUTPUT

Knapsack Problem Using Back Tracking Algoritm Capacity of Knapsack is 110 Profit Weight -------------11 1 21 11 31 21 33 33 43 43 53 45 55 55 65 0 -------------The following are selected items from knapsack......

Item 1 Item 2 Item 3 Item 4 Item 5 Final Weight=109.00 Final Profit=139.00

17. DIJIKSTRAS ALGORITHM

PROGRAM #include<stdio.h> #include<conio.h> #define member1 #define nomember0 #define infinity 999 #define MAX 10 int g[MAX][MAX],q[MAX]; int n; void main() { int src,dest,path_node; void build_graph(); void dijkstra(int,int); int delete_q(int); int front,rear; clrscr(); printf("\nProgram for shortest path algorithm using priority queue"); printf("\n\n\nEnter the number of vertices:"); scanf("%d",&n); build_graph(); printf("\nEnter the source: "); scanf("%d",&src); printf("\nEnter the destination: "); scanf("%d",&dest); dijkstra(src,dest); printf("\nThe shortest path is....\n"); front=1;rear=n; while(front<=rear) { path_node=delete_q(front);

if(path_node!=infinity) printf("%d",path_node); front++; } getch(); } void build_graph() { int i,j,v1,v2; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("\nEnter the no. of edges of v%d to v %d: ",i,j); scanf("%d",g[i][j]); } printf("\n"); } } void insert_q(int index) { q[index]=1; } int delete_q(int i) { if(q[i]==1) return i; return infinity; } void dijkstra(int src,int dest) { int small,dist[10],current,start,new1; int temp,i,j; void insert_q(int); for(i=0;i<=n;i++); { q[i]=0; dist[i]=infinity; } q[src]=1; dist[src]=0; current=src; while(current!=dest) { small=infinity; start=dist[current]; for(i=1;i<=n;i++) { if(q[i]==0) {

new1=start+g[current][i]; if(new1<dist[i]) dist[i]=new1; if(dist[i]<small) { small=dist[i]; temp=i; } } } current=temp; insert_q(current); } } OUTPUT Program for shortest path algorithm using priority queue Enter the number of vertices: 5 Enter the no. of edges of v1 to v1: 999 Enter the no. of edges of v1 to v2: 9 Enter the no. of edges of v1 to v3: 4 Enter the no. of edges of v1 to v4: 999 Enter the no. of edges of v1 to v5: 999 Enter the no. of edges of v2 to v1: 9 Enter the no. of edges of v2 to v2: 999 Enter the no. of edges of v2 to v3: 999 Enter the no. of edges of v2 to v4: 3 Enter the no. of edges of v2 to v5: 999 Enter the no. of edges of v3 to v1: 4 Enter the no. of edges of v3 to v2: 999 Enter the no. of edges of v3 to v3: 999 Enter the no. of edges of v3 to v4: 999

Enter the no. of edges of v3 to v5: 1 Enter the no. of edges of v3 to v1: 4 Enter the no. of edges of v3 to v2: 999 Enter the no. of edges of v3 to v3: 999 Enter the no. of edges of v3 to v4: 999 Enter the no. of edges of v3 to v5: 1 Enter the no. of edges of v4 to v1: 999 Enter the no. of edges of v4 to v2: 3 Enter the no. of edges of v4 to v3: 999 Enter the no. of edges of v4 to v4: 999 Enter the no. of edges of v4 to v5: 1 Enter the no. of edges of v5 to v1: 999 Enter the no. of edges of v5 to v2: 999 Enter the no. of edges of v5 to v3: 1 Enter the no. of edges of v5 to v4: 1 Enter the no. of edges of v5 to v5: 999 Enter the source: 1 Enter the destination: 5 The shortest path is.... Enter the destination: 5 The shortest path is.... 12345