Q.

1) /*program to insert a node at the begining, at the end

and in the middle of the given linked list*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void insert(int x)
{
struct node *link=(node*)malloc(sizeof(node));
link->data=x;
link->next=head;
head=link;
}
void insert_position(int value, int position)
{
int count=0;
struct node *current,*temp;
current=head;
while(current!=NULL)
{
count++;
if(count==position-1)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->data=value;
temp->next=current->next;
current->next=temp;
}
current=current->next;
}
}
void disp()
{
struct node *prt=head;
printf("List is=\n");
while(prt!=NULL)
{
printf("%d ",prt->data);
prt=prt->next;
}
printf("\n");
}
void main()
{
clrscr();
int x ,n;
printf("\n enter no of element in linked list=");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("\n enter data in list=");
scanf("%d",&x);
insert(x);
}
disp();
int pos;
printf("\n Mention at which position to insert a node=");
scanf("%d",&pos);
printf("\n enter data in list=");
scanf("%d",&x);
insert_position(x,pos);
disp();
getch();
}
OUTPUT
Q.2) /*program to delete a node at the beginning, at the
end and in the middle of the given linked list*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void Insert(int x)
{
struct node *newnode=(node*)malloc(sizeof(node));
newnode->data=x;
newnode->next=head;
head=newnode;
}

void DeleteFirstNode()
{
struct node *temp=head;
if(temp==NULL)
{
printf("Linked list is empty");
}
else
{
head=head->next;
free(temp);
}
}

DeleteLastNode()
{
struct node *temp=head;
struct node *pretemp;
 if(temp==NULL)
{
printf("\n List is empty");
}
else
{
while(temp->next!=NULL)
{
pretemp=temp;
temp=temp->next;
}
pretemp->next=NULL;
free(temp);
}
}
void DeleteAnyNode(int n)
{
struct node *temp1=head;
if(n==1)
{
head=temp1->next;
free(temp1);
}
else
{
int i;
for(i=0;i<n-2;i++)
{
temp1=temp1->next;
}
struct node *temp2=temp1->next;
temp1->next=temp2->next;
free(temp2);
}
}

void Disp()
{
struct node *prt=head;
printf("\n list is=");
while(prt!=NULL)
{
printf("%d ",prt->data);
prt=prt->next;
}
printf("\n");
}

void main()
{
clrscr();
int x ,n;
printf("\n enter no of element in linked list=");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("\n enter data in list=");
scanf("%d",&x);
Insert(x);
}
Disp();
int p;
printf("\n enter position of node to delete=");
scanf("%d",&p);
DeleteAnyNode(p);
printf("\n after deletion list is=");
Disp();
DeleteFirstNode();
printf("\n After deletion of first node list is=\n");
Disp();
DeleteLastNode();
printf("\n After dleletion of last node list is=\n");
Disp();
getch();
}
OUTPUT
Q.3) /*program to reverse a linked list*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void Insert(int x)
{
struct node *link=(node*)malloc(sizeof(node));
link->data=x;
link->next=head;
head=link;
}
void Reverse()
{
struct node *curnode=head;
struct node *nextnode=NULL;
struct node *prevnode=NULL;
while(curnode!=NULL)
{
nextnode=curnode->next;
curnode->next=prevnode;
prevnode=curnode;
curnode=nextnode;
}
head=prevnode;
printf("\n Reverse Linked List Is=");
}
void Disp()
{
struct node *prt=head;
while(prt!=NULL)
{
 printf(" %d",prt->data);
prt=prt->next;
}
printf("\n");
}

void main()
{
clrscr();
int x ,n;
printf("\n enter no of element in linked list=");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("\n enter data in list=");
scanf("%d",&x);
Insert(x);
}
Disp();
Reverse();
Disp();
getch();
}
OUTPUT
Q.4) /*program to search a value in the given linked list*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void Insert(int x)
{
struct node *link=(node*)malloc(sizeof(node));
link->data=x;
link->next=head;
head=link;
}
void Search(int x)
{
struct node *temp=head;
int value=0;
while(temp!=NULL)
{
if(temp->data==x)
{
value=value+1;
}
temp=temp->next;
}
if(value==1)
printf("\n Element Found");
else
printf("\n Element not Found");
}
void Disp()
{
struct node *prt=head;
 printf("\n List is");
while(prt!=NULL)
{
printf(" %d",prt->data);
prt=prt->next;
}
printf("\n");
}
void main()
{
clrscr();
int x ,n;
printf("\n enter no of element in linked list=");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("\n enter data in list=");
scanf("%d",&x);
Insert(x);
}
Disp();
int element;
printf("\n Enter element to search=");
scanf("%d",&element);
Search(element);
getch();
}
OUTPUT
Q. 5) /*program to create insert and delete
noe in circular linked list*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head;
void createList(int n);
void displayList();
void insertAtBeg(int data);
void insertAtPos(int data,int pos);
void deleteNode(struct node *head,int key);
void main()
{
int n, data,key, choice=1;
head=NULL;
while (choice!=0)
{
printf("1. Create List\n");
printf("2. Display List\n");
printf("3. Insert at beginning\n");
printf("4. Insert At Any position\n");
printf("5. Delete by key");
printf("0. Exit\n");
printf("Enter your choice=");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the total no of nodes in the list=");
scanf("%d",&n);
createList(n);
break;
case 2:
 displayList();
break;
case 3:
printf("\n Enter data to be inserted at beginning=");
scanf("%d",&data);
insertAtBeg(data);
break;
case 4:
printf("\n Enter node position=");
scanf("%d",&n);
printf("\nEnter data you want to insert at % position=",n);
scanf("%d",&data);
insertAtPos(data,n);
break;
case 5:
printf("\n Enter key to delete from list=");
scanf("%d",&key);
deleteNode(head,key);
break;
case 0:
break;
default:
printf("\n Invalid choice. please enter choice between 0-4");
}
printf("\n");
}
getch();
}
void deleteNode(struct node *head,int key)
{
int i, count;
struct node *current,*prev;
if(head==NULL)
printf("\n List is empty");
count=0;
current=head;
prev=current;
 while(prev->next!=head)
{
prev=prev->next;
count++;
}
i=0;
while(i<=count)
{
if(current->data==key)
{
if(current->next!=current)
prev->next=current->next;
else
prev->next=NULL;
if(current==head)
head=prev->next;
free(current);
if(prev!=NULL)
current=prev->next;
else
current=NULL;
}
else
{
prev=current;
current=current->next;
}
i++;
}
}

void createList(int n)
{
int i,data;
struct node *prevNode,*newNode;
if (n>=1)
{
 head=(struct node*)malloc(sizeof(struct node));
printf("\n Enter data of 1 node=");
scanf("%d",&data);
head->data=data;
head->next=NULL;
prevNode=head;
for(i=2;i<=n;i++)
{
newNode=(struct node*)malloc(sizeof(struct node));
printf("\n Enter data of %d node=",i);
scanf("%d",&data);
newNode->data=data;
newNode->next=NULL;
prevNode->next=newNode;
prevNode=newNode;
}
prevNode->next=head;
printf("\n Circular linked list created successfully");
}
}
void displayList()
{
struct node *current;
int n=1;
if(head==NULL)
printf("\n List is empty");
else
{
current=head;
printf("\n Data in the list =");
do
{
printf("\n Data %d=%d",n,current->data);
current=current->next;
n++;
}while(current!=head);
}
}
void insertAtBeg(int data)
{
struct node *newNode,*current;
if(head==NULL)
printf("\nList is empty");
else
{
newNode=(struct node*)malloc(sizeof(struct node));
newNode->data=data;
newNode->next=head;
current=head;
while(current->next!=head)
{
current=current->next;
}
current->next=newNode;
head=newNode;
printf("\n Node inserted successfully");
}
}
void insertAtPos(int data, int pos)
{
struct node *newNode, *current;
int i;
if(head==NULL)
printf("\n List is empty");
else if(pos==1)
insertAtBeg(data);
else
{
newNode=(struct node*)malloc(sizeof(struct node));
newNode->data=data;
current=head;
for(i=2;i<=pos-1;i++)
{
current=current->next;
 }
newNode->next=current->next;
current->next=newNode;
printf("\n Node inserted successfully");
}
}

OUTPUT
 Q.6) /*program to push
and pop an element into/from
stack implemented using linked list*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *top=NULL;
void push(int value)
{
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=value;
temp->link=top;
top=temp;
}
void pop()
{
struct node *del=top;
if(top!=NULL)
{
top=top->link;
free(del);
}
else
{
 printf("\n stack underflow");
}
}
void Top()
{
struct node *t=top;
printf("\n top element is=%d ",t->data);
}
void disp()
{
struct node *head=top;
printf("\n elements are=");
while(head!=NULL)
{
printf("%d ",head->data);
head=head->link;
}
printf("\n");
}
void main()
{
clrscr();
push(10);
push(20);
push(30);
disp();
Top();
pop();
printf("\n After pop operation");
disp();
Top();
getch();
}
OUTPUT
Q.7) /*program to push and pop an elemen into/from
stack implemented using array*/
#include<stdio.h>
#include<conio.h>
#define MAX 5
int arr[MAX],top=-1,i;
void push(int x)
{
if(top==(MAX-1))
printf("stack is overflow \n");
else
arr[++top]=x;
}
void pop()
{
if(top<0)
printf("stack underflow \n");
else
arr[top--];
}
void disp()
{
printf("\n Elements in the stack are=");
for(i=0;i<=top;i++)
printf("%d ",arr[i]);
}
void main()
{
clrscr();
push(10);
push(20);
push(30);
disp();
printf("\n After pop operation=");
pop();
disp();
 getch();
}

OUTPUT
Q.08) /*program to evaluate postfix expression*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
const int max=50;
class postfix
{
private:
int stack[max];
int top,nn;
char *s;
public:
postfix();
void setexpr(char *str);
void push(int item);
int pop();
void calculate();
void show();
};
postfix::postfix()
{
top=-1;
}
void postfix::setexpr(char *str)
{
s=str;
}
void postfix::push(int item)
{
if(top==max-1)
cout<<endl<<"stack is empty";
else
{
top++;
stack[top]=item;
}
}
int postfix::pop()
{
if(top==-1)
{
cout<<endl<<"stack is empty";
return NULL;
}
int data=stack[top];
top--;
return data;
}
void postfix::calculate()
{
int n1,n2,n3;
while(*s)
{
if(*s==' '||*s=='\t')
{
s++;
 continue;
}
if(isdigit(*s))
{
nn=*s-'0';
push(nn);
}
else
{
n1=pop();
n2=pop();
switch(*s)
{
case '+':n3=n2+n1;
break;
case '-':n3=n2-n1;
break;
case '/':n3=n2/n1;
break;
case '*':n3=n2*n1;
break;
case '%':n3=n2%n1;
break;
case '$':n3=pow(n2,n1);
break;
default:cout<<"unknown operator";
break;
}
push(n3);
 }
s++;
}
}
void postfix::show()
{
nn=pop();
cout<<endl<<"Result is="<<nn;
}
void main()
{
clrscr();
char expr[max];
cout<<"\n Enter postfix expression to be evaluated=";
cin.getline(expr,max);
postfix q;
q.setexpr(expr);
q.calculate();
q.show();
getch();
}

OUTPUT
Q.9) /*program to sort an array using quicksort*/
#include<stdio.h>
#include<conio.h>
void quicksort(int num[25],int first,int last)
{
int i,j,pivot,temp;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(num[i]<=num[pivot] && i<last)
i++;
while(num[j]>num[pivot])
j--;
if(i<j)
{
temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
temp=num[pivot];
num[pivot]=num[j];
num[j]=temp;
quicksort(num,first,j-1);
quicksort(num,j+1,last);
 }
}
void main()
{
int i,count,num[25];
printf("\n How many elements you want to enter?");
scanf("%d",&count);
printf("\n Enter %d elements=",count);
for(i=0;i<count;i++)
{
scanf("%d",&num[i]);
}
quicksort(num,0,count-1);
printf("\n Order of sorted elements=");
for(i=0;i<count;i++)
printf(" %d",num[i]);
getch();
}
OUTPUT
Q.10) /*program to solve towers of hanoi
problem using recursion*/
#include<stdio.h>
#include<conio.h>
void towers(int,char,char,char);
void main()
{
clrscr();
int num;
printf("\n enter the number of disks=");
scanf("%d",&num);
printf("\n the sequence of moves involved in the towers of Hanoi are=");
towers(num,'A','C','B');
getch();
}
void towers(int num,char frompeg,char topeg, char auxpeg)
{
if(num==1)
{
printf("\n move disk 1 from peg %c to peg %c", frompeg, topeg);
return;
}
towers(num-1,frompeg,auxpeg,topeg);
printf("\n move disk %d from peg %c to peg %c", num,frompeg,topeg);
towers(num-1,auxpeg,topeg,frompeg);
}
OUTPUT
Q.11) /* program to perform insertion and
deletion operation on circular queue*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define max 3
int q[10],front=0;
int rear=-1;
void main()
{
clrscr();
int ch;
void insert();
void delet();
void display();
printf("\n Circular Queue operations");
printf("\n 1. insert\t 2. delete\t3. display\t4. exit\n");
while(1)
{
printf("\nEnter your choice=");
scanf("%d",&ch);

switch(ch)
{
case 1:insert();
break;
case 2:delet();
break;
case 3:display();
 break;
case 4:exit(0);
default:printf("invalid option\n");
}
}
}
void insert()
{
int x,i,n;
if((front==0 && rear==max-1)||(front>0 && rear==front-1))
printf("\n Queue is overflow");
else
{
printf("\n how many element you want to enter=");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\n Enter element to be insert=");
scanf("%d",&x);

if(rear==max-1 && front>0)

{
rear=0;
q[rear]=x;
}
else
{
if((front==0 && rear==-1)||(rear!=front-1))
q[++rear]=x;
 }
}
}
}
void delet()
{
int a;
if((front==0) && (rear==-1))
{
printf("\n Queue is underflow");
getch();
exit(0);
}
if(front==rear)
{
a=q[front];
rear=-1;
front=0;
}
else if(front==max-1)
{
a=q[front];
front=0;
}
else
a=q[front++];
printf("\n Deleted element is %d",a);
}
void display()
{
int i,j;
if (front==0 && rear==-1)
{
printf("\n Queue is underflow");
getch();
exit(0);
}
if(front>rear)
{
for(i=0;i<=rear;i++)
printf("\t%d",q[i]);
for(j=front;j<=max-1;j++)
printf("\t%d",q[j]);
printf("\n rear is at %d",q[rear]);
printf("\n front is at %d ",q[front]);
}
else
{
for(i=front;i<=rear;i++)
{
printf("\t%d",q[i]);
}
printf("\n rear is at %d",q[rear]);
printf("\n front is at %d",q[front]);
}
printf("\n");
}
OUTPUT
Q.12) /*program to insert an element in binary search tree*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *GetNewNode(int value)
{
struct node *newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=value;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
struct node *insert(node *root,int x)
{
if(root==NULL)
{
root=GetNewNode(x);
return root;
}
else if(x<=root->data)
{
root->left=insert(root->left,x);
printf("\n Successfully Insert %d",x);
}
else
{
root->right=insert(root->right,x);
printf("\n Successfully Insert %d",x);
}
return root;
}
void main()
{
clrscr();
node *root=NULL;
int n,x;
printf("\n Enter no of element in binary search tree=");
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
printf("\n Enter element in tree=");
scanf("%d",&x);

root=insert(root,x);
}
getch();
}

OUTPUT
Q.13) /*program to traverse inorder of binary tree*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *GetNewNode(int data)
{
struct node *newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=data;
newnode->left=newnode->right=NULL;
return newnode;
}
struct node *Insert(node *root,int x)
{
if(root==NULL)
{
root=GetNewNode(x);
return root;
}
else if(x<=root->data)
{
root->left=Insert(root->left,x);
}
else
{
root->right=Insert(root->right,x);
}
return root;
}
void Inorder(node *root)
{
if(root!=NULL)
 {
Inorder(root->left);
printf("%d \n",root->data);
Inorder(root->right);
}
}
void main()
{
clrscr();
node *root=NULL;
root=Insert(root,10);
root=Insert(root,20);
root=Insert(root,30);
root=Insert(root,10);
root=Insert(root,20);
root=Insert(root,30);
Inorder(root);
getch();
}

OUTPUT
Q.14) /*program to traverse preorder of binary tree*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *GetNewNode(int data)
{
struct node *newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=data;
newnode->left=newnode->right=NULL;
return newnode;
}
struct node *Insert(node *root,int x)
{
if(root==NULL)
{
root=GetNewNode(x);
return root;
}
else if(x<=root->data)
{
root->left=Insert(root->left,x);
}
else
{
root->right=Insert(root->right,x);
}
return root;
}
void Preorder(node *root)
{
if(root!=NULL)
 {
printf("%d \n",root->data);
Preorder(root->left);
Preorder(root->right);
}
}
void main()
{
clrscr();
node *root=NULL;
root=Insert(root,10);
root=Insert(root,20);
root=Insert(root,30);
root=Insert(root,40);
root=Insert(root,50);
root=Insert(root,60);
Preorder(root);
getch();
}

OUTPUT
Q.15) /*program to traverse postorder of binary tree*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *GetNewNode(int data)
{
struct node *newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=data;
newnode->left=newnode->right=NULL;
return newnode;
}
struct node *Insert(node *root,int x)
{
if(root==NULL)
{
root=GetNewNode(x);
return root;
}
else if(x<=root->data)
{
root->left=Insert(root->left,x);
}
else
{
root->right=Insert(root->right,x);
}
return root;
}
void Postorder(node *root)
{
if(root!=NULL)
 {
Postorder(root->left);
Postorder(root->right);
printf("%d \n",root->data);
}
}
void main()
{
clrscr();
node *root=NULL;
root=Insert(root,10);
root=Insert(root,20);
root=Insert(root,30);
root=Insert(root,40);
root=Insert(root,50);
root=Insert(root,60);
Postorder(root);
getch();
}

OUTPUT