Program – 9:
Create a doubly linked list of integers and display in forward and backward
direction.
  #include <stdio.h>
 #include<malloc.h>
 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(**0;i<n;i++)
 {
printf("Enter value:");
scanf("%d",&item);
ptr=(struct node*)malloc(sizeof(struct node));
 ptr->data=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 <stdio.h> #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(**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 <stdio.h>
 #include<malloc.h>
 #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 <stdio.h> #include<ctype.h> 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 <stdio.h> #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 <stdio.h> #include<malloc.h>
 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 <stdio.h> #include<malloc.h>
 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(**0;i<n;i++) {
p=(struct bst*)malloc(sizeof(struct bst)); printf("enter element [%d]:",i+1); scanf("%d",&item);
 p->info=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(key<root->info)
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 <stdio.h>
  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(**0;i<n;i++)
 {
printf("Enter element [%d]:",i+1); scanf("%d",&a[i]);
}
 printf("Array elements before sort....\n"); for(**0;i<n;i++)
{
  College of Applied Science, Thamarassery 37

Lab – Data Structure Using C
   printf("%d\t",a[i]); }
for(**0;i<n-1;i++) {
 for(j=0;j<n-i-1;j++) {
 if(a[j]>a[j+1]) {
temp=a[j];
 a[j]=a[j+1]; a[j+1]=temp;
 } }
}
 printf("\nArray elements after sort....\n"); for(**0;i<n;i++)
 { printf("%d\t",a[i]);
}
return 0; }
  Output:
Enter your array limit:7
  Enter 7 array elements....
 Enter element [1]:9 Enter element [2]:4
 Enter element [3]:3 Enter element [4]:6 Enter element [5]:4
 Enter element [6]:2
Enter element [7]:4
Array elements before sort....
 9436424
Array elements after sort.... 2344469
  College of Applied Science, Thamarassery 38

Lab – Data Structure Using C
  Program – 17:
  Implement selection sort.
 #include <stdio.h>
  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(**0;i<n;i++) {
printf("Enter element [%d]:",i+1);
 scanf("%d",&a[i]);
 }
 printf("Array elements before sort....\n");
 for(**0;i<n;i++) {
printf("%d\t",a[i]);
 }
 for(**0;i<n-1;i++)
 {
 min=i; for(j=i+1;j<n;j++) {
 if(a[j]<a[min]) {
min=j;
 } }
temp=a[i]; a[i]=a[min];
 a[min]=temp; }
printf("\nArray elements after sort....\n");
 for(**0;i<n;i++) {
printf("%d\t",a[i]); }
  College of Applied Science, Thamarassery 39

Lab – Data Structure Using C
   return 0; }
Output:
   Enter your array limit:6 Enter 6 array elements....
 Enter element [1]:9
 Enter element [2]:3 Enter element [3]:8
 Enter element [4]:6 Enter element [5]:7 Enter element [6]:5
 Array elements before sort....
 938675
Array elements after sort.... 356789
Program – 18:
  Implement insertion sort.
 #include <stdio.h>
 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(**0;i<n;i++)
{
 printf("Enter element [%d]:",i+1);
scanf("%d",&a[i]); }
 printf("Array elements before sort....\n"); for(**0;i<n;i++)
{
printf("%d\t",a[i]);
  College of Applied Science, Thamarassery 40

Lab – Data Structure Using C
   } for(**1;i<n;i++) {
value=a[i];
 for(j=i-1;((j>=0)&&(a[j]>value));j--) {
 a[j+1]=a[j]; }
a[j+1]=value;
 }
printf("\nArray elements after sort....\n");
 for(**0;i<n;i++) {
printf("%d\t",a[i]);
 }
return 0;
 }
Output:
  Enter your array limit:9 Enter 9 array elements....
 Enter element [1]:9 Enter element [2]:2 Enter element [3]:8
 Enter element [4]:5 Enter element [5]:7 Enter element [6]:6
 Enter element [7]:4 Enter element [8]:3 Enter element [9]:1
 Array elements before sort.... 928576431 Array elements after sort....
 123456789
  College of Applied Science, Thamarassery