Program – 9: Create a doubly linked list of integers and display in forward and backward direction. #include #include struct node { struct node *prev; struct node *next; int data; }; struct node *start=NULL; void traverse(); int main(void) { int n,i,item; struct node *ptr,*temp; printf("Enter how many nodes:"); scanf("%d",&n); for(i=0;idata=item; if(start==NULL) { ptr->next=NULL; ptr->prev=NULL; start=ptr; } College of Applied Science, Thamarassery 13 Lab – Data Structure Using C else { temp=start; while(temp->next!=NULL) { temp=temp->next; } temp->next=ptr; ptr->prev=temp; ptr->next=NULL; } } printf("Printing values forward direction....\n"); ptr=start; while(ptr!=NULL) { printf("%d->",ptr->data); ptr=ptr->next; } ptr=start; while(ptr->next!=NULL) { ptr=ptr->next; } printf("\nPrinting values backward direction....\n"); while(ptr!=NULL) { printf("%d->",ptr->data); ptr=ptr->prev; } return 0; } Output: Enter how many nodes:5 Enter value:1 Enter value:2 Enter value:3 Enter value:4 College of Applied Science, Thamarassery 14 Lab – Data Structure Using C Enter value:5 Printing values forward direction.... 1->2->3->4->5-> Printing values backward direction.... 5->4->3->2->1-> Program – 10: Implement Stack using array. #include #define maxsize 50 int stack[maxsize],top=-1; void create(); void display(); void pop(); void push(); int main() { int ch,top=-1; while(1) { printf("\n1.Create\n"); printf("2.Display\n"); printf("3.Push\n"); printf("4.Pop\n"); printf("5.Exit\n"); printf("Enter your choice:"); scanf("%d",&ch); if(ch==5) { return 0; } switch(ch) { case 1: create(); break; case 2: display(); break; College of Applied Science, Thamarassery 15 Lab – Data Structure Using C case 3: push(); break; case 4: pop(); break; } } } void create() { int che; do { top++; printf("Input element:"); scanf("%d",&stack[top]); printf("Press 1 if more data other wise 0:"); scanf("%d",&che); }while(che==1); return; } void display() { int i; if(top==-1) { printf("Stack is empty"); } for(i=top;i>=0;i--) { printf("%d\t",stack[i]); } return; } void push() { int m; if(top==maxsize-1) { College of Applied Science, Thamarassery 16 Lab – Data Structure Using C printf("Overflow"); return; } top++; printf("Enter new element:"); scanf("%d",&m); stack[top]=m; return; } void pop() { if(top==-1) { printf("Underflow"); return; } printf("%d is deleted",stack[top]); stack[top]='\0'; top--; return; } Output: 1.Create 2.Display 3.Push 4.Pop 5.Exit Enter your choice:1 Input element:5 Press 1 if more data other wise 0:1 Input element:4 Press 1 if more data other wise 0:1 Input element:3 Press 1 if more data other wise 0:2 1.Create 2.Display College of Applied Science, Thamarassery 17 Lab – Data Structure Using C 3.Push 4.Pop 5.Exit Enter your choice:2 345 1.Create 2.Display 3.Push 4.Pop 5.Exit Enter your choice:3 Enter new element:7 1.Create 2.Display 3.Push 4.Pop 5.Exit Enter your choice:2 7345 1.Create 2.Display 3.Push 4.Pop 5.Exit Enter your choice:4 7 is deleted 1.Create 2.Display 3.Push 4.Pop 5.Exit Enter your choice:2 345 1.Create 2.Display 3.Push 4.Pop 5.Exit Enter your choice:5 College of Applied Science, Thamarassery 18 Lab – Data Structure Using C Program – 11: Implement Stack using linked list. #include #include #define maxsize 50 struct node { int data; struct node *link; }; struct node *top; void create(); void traverse(); void pop(); void push(); int main() { int c; while(1) { printf("\n1.Create\n"); printf("2.Traverse\n"); printf("3.Push\n"); printf("4.Pop\n"); printf("5.Exit\n"); printf("Enter your choice:"); scanf("%d",&c); if(c==5) { return 0; } switch(c) { case 1: create(); break; case 2: traverse(); College of Applied Science, Thamarassery 19 Lab – Data Structure Using C break; case 3: push(); break; case 4: pop(); break; } } } void create() { int che; do { struct node *p; p=(structnode*)malloc(sizeof(struct node)); printf("Input element:"); scanf("%d",&p->data); p->link=NULL; p->link=top; top=p; printf("Press 1 if more data other wise 0:"); scanf("%d",&che); }while(che==1); return; } void traverse() { struct node *p; p=top; if(p==NULL) { printf("Stack is empty"); return; } printf("Stack traversing...\n"); while(p!=NULL) { printf("%d->",p->data); College of Applied Science, Thamarassery 20 Lab – Data Structure Using C p=p->link; } return; } void push() { struct node *p; p=(structnode*)malloc(sizeof(struct node)); printf("Enter new element:"); scanf("%d",&p->data); p->link=top; top=p; return; } void pop() { if(top==NULL) { printf("Underflow"); return; } struct node *p; printf("%d is deleted",top->data); top=top->link; free(p); return; } Output: 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:1 Input element:6 Press 1 if more data other wise 0:1 Input element:7 College of Applied Science, Thamarassery 21 Lab – Data Structure Using C Press 1 if more data other wise 0:1 Input element:5 Press 1 if more data other wise 0:0 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:2 Stack traversing... 5->7->6-> 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:3 Enter new element:9 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:2 Stack traversing... 9->5->7->6-> 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:4 9 is deleted 1.Create 2.Traverse 3.Push 4.Pop 5.Exit College of Applied Science, Thamarassery 22 Lab – Data Structure Using C Enter your choice:2 Stack traversing... 5->7->6-> 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:4 5 is deleted 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:2 Stack traversing... 7->6-> 1.Create 2.Traverse 3.Push 4.Pop 5.Exit Enter your choice:5 Program – 12: Evaluation ofpostfixexpression. #include #include int stack[20]; int top=-1; void push(int); int pop(); int main(void) { char exp[20],*e; int n1,n2,n3,num; printf("Enter the postfix expression:"); scanf("%s",exp); College of Applied Science, Thamarassery 23 Lab – Data Structure Using C e=exp; while(*e!='\0') { if(isdigit(*e)) { num=*e-48; push(num); } else { n1=pop(); n2=pop(); switch(*e) { case '+': n3=n1+n2; break; case '-': n3=n2-n1; break; case '*': n3=n2*n1; break; case '/': n3=n2/n1; break; } push(n3); } e++; } printf("Result=%d",pop()); return 0; } void push(int x) { stack[++top]=x; } int pop() { College of Applied Science, Thamarassery 24 Lab – Data Structure Using C return stack[top--]; } Output: Enter the postfix expression:74+5- Result=6 Program – 13: Implement Queue using array. #include #define maxsize 50 int queue[maxsize],front=-1,rear=-1; void push(); void pop(); void display(); int main(void) { int ch,c=1; while(1) { printf("\n1.Push"); printf("\n2.Pop"); printf("\n3.Display"); printf("\n4.Exit"); printf("\nEnter Your Choice:"); scanf("%d",&ch); if(ch==4) { return 0; } switch(ch) { case 1: push(); break; case 2: pop(); College of Applied Science, Thamarassery 25 Lab – Data Structure Using C break; case 3: display(); break; } } return 0; } void push() { int a; printf("Enter value:"); scanf("%d",&a); if(rear==maxsize-1) { printf("Overflow"); return; } rear++; queue[rear]=a; if(front==-1) { front=0; } return; } void pop() { int a; if(front==-1) { printf("Queue Empty"); return; } printf("%d is deleted",queue[front]); a=queue[front]; queue[front]=0; if(front==rear) { front=rear=-1; College of Applied Science, Thamarassery 26 Lab – Data Structure Using C } else { front++; } return; } void display() { int t; if(front==-1) { printf("Queue is Empty"); } else { printf("Queue elements are....\n"); for(t=front;t<=rear;t++) { printf("%d\t",queue[t]); } } return; } Output: 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter value:2 1.Push 2.Pop 3.Display 4.Exit College of Applied Science, Thamarassery 27 Lab – Data Structure Using C Enter Your Choice:1 Enter value:4 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter value:6 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 246 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter value:7 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 2467 1.Push 2.Pop 3.Display 4.Exit College of Applied Science, Thamarassery 28 Lab – Data Structure Using C Enter Your Choice:2 2 is deleted 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 467 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter value:8 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 4678 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:2 4 is deleted 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... College of Applied Science, Thamarassery 29 Lab – Data Structure Using C 678 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:4 Program – 14: Implement Queue using linked list. #include #include struct node { int data; struct node *link; } *front,*rear; void push(); void pop(); void display(); int main(void) { int ch; while(1) { printf("\n1.Push"); printf("\n2.Pop"); printf("\n3.Display"); printf("\n4.Exit"); printf("\nEnter Your Choice:"); scanf("%d",&ch); if(ch==4) { return 0; } switch(ch) { case 1: push(); College of Applied Science, Thamarassery 30 Lab – Data Structure Using C break; case 2: pop(); break; case 3: display(); break; } } return 0; } void push() { struct node *p; int d; p=(struct node*)malloc(sizeof(struct node)); printf("Enter Data:"); scanf("%d",&d); p->data=d; p->link=NULL; if(front==NULL) { front=p; } else { rear->link=p; } rear=p; return; } void pop() { struct node *p; if(front==NULL) { printf("Queue is Empty"); return; } printf("%d is deleted",front->data); College of Applied Science, Thamarassery 31 Lab – Data Structure Using C if(front==rear) { free(front); rear=NULL; front=NULL; } else { p=front; front=p->link; free(p); } return; } void display() { struct node *ptr; ptr=front; if(front==NULL) { printf("Queue is Empty"); return; } printf("Queue elements are....\n"); while(ptr!=NULL) { printf("%d->",ptr->data); ptr=ptr->link; } return; } Output: 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 College of Applied Science, Thamarassery 32 Lab – Data Structure Using C Enter Data:3 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter Data:4 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter Data:5 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 3->4->5-> 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:1 Enter Data:7 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 College of Applied Science, Thamarassery 33 Program – 15: College of Applied Science, Thamarassery 34 Lab – Data Structure Using C Queue elements are.... 3->4->5->7-> 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:2 3 is deleted 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 4->5->7-> 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:2 4 is deleted 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:3 Queue elements are.... 5->7-> 1.Push 2.Pop 3.Display 4.Exit Enter Your Choice:4 Lab – Data Structure Using C Search an element in a binary search tree. #include #include struct bst { int info; struct bst *left; struct bst *right; }; struct bst* search(struct bst *root, int); int main(void) { struct bst *q,*p,*root,*k; int n,i,item,key; printf("Enter how many nodes:"); scanf("%d",&n); for(i=0;iinfo=item; p->left=NULL; p->right=NULL; if(i==0) root=p; else { q=root; while(1) { if(p->info>q->info) { if(q->right==NULL) { q->right=p; break; } else { College of Applied Science, Thamarassery 35 Lab – Data Structure Using C q=q->right; } } else { if(q->left==NULL) { q->left=p; break; } else { q=q->left; } } } } } printf("\nenter an element for search:"); scanf("%d",&key); k=search(root,key); if(k!=NULL) { printf("%d is present in this bst",key); } else { printf("%d is not present in this bst",key); } } struct bst* search(struct bst *root,int key) { if(root==NULL) { return root; } else if(key==root->info) { return root; } College of Applied Science, Thamarassery 36 Lab – Data Structure Using C else if(keyinfo) return search(root->left,key); else return search(root->right,key); } Output: Enter how many nodes:5 enter element [1]:3 enter element [2]:6 enter element [3]:4 enter element [4]:8 enter element [5]:5 enter an element for search:4 4 is present in this bst Program – 16: Implement exchange sort. #include int main(void) { int i,j,temp,n,a[10]; printf("Enter your array limit:"); scanf("%d",&n); printf("Enter %d array elements....\n",n); for(i=0;ia[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } printf("\nArray elements after sort....\n"); for(i=0;i int main(void) { int i,j,min,n,a[10],temp; printf("Enter your array limit:"); scanf("%d",&n); printf("Enter %d array elements....\n",n); for(i=0;i int main(void) { int i,j,n,a[10],value; printf("Enter your array limit:"); scanf("%d",&n); printf("Enter %d array elements....\n",n); for(i=0;i=0)&&(a[j]>value));j--) { a[j+1]=a[j]; } a[j+1]=value; } printf("\nArray elements after sort....\n"); for(i=0;i