DATA STRUCTURE LAB MANUAL
Experiment No.1
Program :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct info
{
char name[30];
int eno;
struct info *next;
};
struct info *head=NULL,*temp,*disp;
void addrecord();
void deleterecord();
void disrecord();
void main()
{
int ch;
clrscr();
while (1)
{
printf("\n 1. To add records\n");
printf("\n 2. To delete a records\n");
printf("\n 3. To view the records\n");
printf("\n 4. To exit\n");
printf("\n Enter your choice\n");
scanf("%d",&ch);
fflush(stdin);
switch(ch)
{
case 1:addrecord();
break;
case 2:deleterecord();
break;
case 3: disrecord();
break;
case 4:exit(0);
}
}
}
void addrecord()
{
1
DATA STRUCTURE LAB MANUAL
struct info *add;
char ans='y';
while (ans=='y')
{
add=(struct info*)malloc(sizeof(struct info));
printf("\n Enter the names:\n");
gets(add->name);
fflush(stdin);
printf("\n Enter the enrollment number:\n");
scanf("%d",&add->eno);
fflush(stdin);
if (head==NULL)
{
head=add;
add->next=NULL;
temp=add;
}
else
{
temp->next=add;
add->next=NULL;
temp=add;
}
printf("\n Would you like to enter another name(y\\n): \n");
ans = getchar();
fflush(stdin);
}
} void deleterecord()
{
struct info *delete;
int teno, present=0;
if (head==NULL)
{
printf("\n No records to delete\n");
return;
}
printf("\n Enter the enrollment number to be deleted \n");
scanf("%d",&teno);
fflush(stdin);
for (delete=head;delete!=NULL;delete=delete->next)
{
if (delete->eno==teno)
{
2
DATA STRUCTURE LAB MANUAL
if (head->eno==teno)
{
delete=head;
head=head->next;
free(delete);
return;
}
else
{
temp->next=delete->next;
free(delete);
return;
}
}
temp=delete;
}
if (present==0)
printf("\nNo such enrollment number present\n");
}
void disrecord()
{
if (head==NULL)
{
printf("\n No records to view\n");
return;
}
for (disp=head;disp!=NULL;disp=disp->next)
{
printf("\n\n Name : %s",disp->name);
printf("\n\n Number : %d",disp->eno);
}
}
3
DATA STRUCTURE LAB MANUAL
Experiment No.2
Program :
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
struct Node *prev;
}node;
void insert(node *pointer, int data)
{
/* Iterate through the list till we encounter the last node.*/
while(pointer->next!=NULL)
{
pointer = pointer -> next;
}
/* Allocate memory for the new node and put data in it.*/
pointer->next = (node *)malloc(sizeof(node));
(pointer->next)->prev = pointer;
pointer = pointer->next;
pointer->data = data;
pointer->next = NULL;
}
int find(node *pointer, int key)
{
pointer = pointer -> next; //First node is dummy node.
/* Iterate through the entire linked list and search for the key. */
while(pointer!=NULL)
{
if(pointer->data == key) //key is found.
{
return 1;
}
pointer = pointer -> next;//Search in the next node.
}
/*Key is not found */
return 0;
}
void delete(node *pointer, int data)
{
/* Go to the node for which the node next to it has to be deleted */
while(pointer->next!=NULL && (pointer->next)->data != data)
{
4
DATA STRUCTURE LAB MANUAL
pointer = pointer -> next;
}
if(pointer->next==NULL)
{
printf("Element %d is not present in the list\n",data);
return;
}
/* Now pointer points to a node and the node next to it has to be removed */
node *temp;
temp = pointer -> next;
/*temp points to the node which has to be removed*/
pointer->next = temp->next;
temp->prev = pointer;
/*We removed the node which is next to the pointer (which is also temp) */
free(temp);
/* Beacuse we deleted the node, we no longer require the memory used for it .
free() will deallocate the memory.
*/
return;
}
void print(node *pointer)
{
if(pointer==NULL)
{
return;
}
printf("%d ",pointer->data);
print(pointer->next);
}
int main()
{
/* start always points to the first node of the linked list.
temp is used to point to the last node of the linked list.*/
node *start,*temp;
start = (node *)malloc(sizeof(node));
temp = start;
temp -> next = NULL;
temp -> prev = NULL;
/* Here in this code, we take the first node as a dummy node.
The first node does not contain data, but it used because to avoid handling special cases
in insert and delete functions.
*/
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Print\n");
printf("4. Find\n");
5
DATA STRUCTURE LAB MANUAL
while(1)
{
int query;
scanf("%d",&query);
if(query==1)
{
int data;
scanf("%d",&data);
insert(start,data);
}
else if(query==2)
{
int data;
scanf("%d",&data);
delete(start,data);
}
else if(query==3)
{
printf("The list is ");
print(start->next);
printf("\n");
}
else if(query==4)
{
int data;
scanf("%d",&data);
int status = find(start,data);
if(status)
{
printf("Element Found\n");
}
else
{
printf("Element Not Found\n");
}
}
}
6
DATA STRUCTURE LAB MANUAL
Experiment No.3
Program :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 5
struct stack {
int s[size];
int top;
} st;
int stfull() {
if (st.top >= size - 1)
return 1;
else
return 0;
}
void push(int item) {
st.top++;
st.s[st.top] = item;
}
int stempty() {
if (st.top == -1)
return 1;
else
return 0;
}
int pop() {
int item;
item = st.s[st.top];
st.top--;
return (item);
}
void display() {
int i;
if (stempty())
printf("\nStack Is Empty!");
else {
for (i = st.top; i >= 0; i--)
printf("\n%d", st.s[i]);
7
DATA STRUCTURE LAB MANUAL
}
}
int main() {
int item, choice;
char ans;
st.top = -1;
printf("\n\tImplementation Of Stack");
do {
printf("\nMain Menu");
printf("\n1.Push \n2.Pop \n3.Display \n4.exit");
printf("\nEnter Your Choice");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("\nEnter The item to be pushed");
scanf("%d", &item);
if (stfull())
printf("\nStack is Full!");
else
push(item);
break;
case 2:
if (stempty())
printf("\nEmpty stack!Underflow !!");
else {
item = pop();
printf("\nThe popped element is %d", item);
}
break;
case 3:
display();
break;
case 4:
exit(0);
}
printf("\nDo You want To Continue?");
ans = getche();
} while (ans == 'Y' || ans == 'y');
return 0;
}
8
DATA STRUCTURE LAB MANUAL
Experiment No.4
Program :
#include<stdio.h>
struct stack
{
int info;
struct stack *next;
};
typedef struct stack node;
class stlink
{
node *start;
public:
stlink()
{
start=NULL;
}
void display(void);
void push(int);
int pop(void);
};
void stlink::push(int term)
{
node *p,*s;
s=start;
if(s==NULL||s!=NULL)
{
p=(node *)malloc(sizeof(node));
p->info=term;
p->next=s;
s=p;
}
start=s;
return;
}
void stlink::display(void)
{
node *temp;
if(start==NULL)
{
9
DATA STRUCTURE LAB MANUAL
cout << endl<<"UNDERFLOEW";
}
temp=start;
while(temp!=NULL)
{
cout << endltemp=temp->next;
}
return;
}
int stlink::pop(void)
{
int term;
if(start==NULL)
{
cout<<"UNDERFLOW";
return(-1);
}
else
{
node *p;
term=start->info;
p=start;
free(start);
start=p->next;
return(term);
}
}
int main()
{
stlink s1;
int ch,temp;
do
{
clrscr();
cout<<"1->Push\n";
cout<<"2->Display\n";
cout<<"3->Pop\n";
cout<<"4->Exit\n";
cout<<"Enter your choice:";
cin>>ch;
switch(ch)
{
case'1':
10
DATA STRUCTURE LAB MANUAL
cout<<"Enter the term to push:";
cin>>temp;
s1.push(temp);
break;
case'2':
cout << endl<<"Stack";
s1.display();
getch();
break;
case'3':
temp=s1.pop();
if(temp!=-1)
cout<<"Popped term is " << temp;
getch();
break;
case'4':
cout<<"Exiting";
getch();
break;
default:
cout<<"Invalid choice";
getch();
break;
}
}while(ch!=4);
return(0);
}
11
DATA STRUCTURE LAB MANUAL
Experiment No.5
ALGORITHM OF QUEUE:
1. Insert Operation:
Insert operation inserting the new value from the rear side (right hand side). The first value is
arranged in the queue as a left most value (in queue as first value) and second value is also
inserted on rear side and set behind first value. Thus, each new value is set behind the previous
entered value.
Step 1: [Check overflow condition]
if rear >= size
Output “Overflow” and return
Step 2: [Increment rear pointer]
Rear = rear + 1
Step 3: [Insert an element]
Q [rear] = value
Step 4: [Set the front pointer]
If front = 0
front = 1
Step 5: return
2. Deletion Operation:
Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out
(FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue).
This operation is removed first entered item after second entered item and so on in the queue.
Step 1: [Check underflow condition]
if front = 0
Output “Underflow” and return
Step 2: [Remove an element]
Value = Q [front]
Step 3: [Check for empty queue]
If front = rear
front = 0
rear = 0
else
front = front + 1
12
DATA STRUCTURE LAB MANUAL
Program :
#include<stdio.h>
#define SIZE 10
struct queue
{
int item[SIZE];
}*q;
static int front = 0;
static int rear = 0;
main()
{
int ans;
do
{
clrscr();
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Display the Queue.\n");
printf("4. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert(&q);
break;
case 2:
rem(&q);
break;
case 3:
display(&q);
break;
case 4:
break;
default:
printf("You have entered wrong choice....");
}
}while(ans != 4);
getch();
return;
}
insert(struct queue *temp)
{
13
DATA STRUCTURE LAB MANUAL
int newitem;
if(front >= SIZE)
{
printf("QUEUE IS FULL....");
getch();
return;
}
else
{
printf("Enter a New Value :");
scanf("%d",&newitem);
temp->item[++rear] = newitem;
if(front <= 0)
front = 1;
}
getch();
return;
}
rem(struct queue *temp)
{
int remitem;
if (rear <= 0)
{
printf("THE QUEUE IS EMPTY....");
getch();
return;
}
else
{
temp->item[front++] = 0;
if(front > rear)
{
front = 0;
rear = 0;
}
}
getch();
return;
}
display(struct queue *temp)
{
int fnt = 1;
if(front <= 0 || rear <=0)
14
DATA STRUCTURE LAB MANUAL
{
printf("THE QUEUE IS EMPLTY....");
getch();
return;
}
else
{
while(fnt <= rear)
{
printf("%d ",temp->item[fnt]);
fnt++;
}
}
getch();
return;
}
15
DATA STRUCTURE LAB MANUAL
Experiment No.6
ALGORITHM OF QUEUE:
1. Insert Operation:
Insert operation inserting the new value from the rear side (right hand side). The first value is
arranged in the queue as a left most value (in queue as first value) and second value is also
inserted on rear side and set behind first value. Thus, each new value is set behind the previous
entered value.
Step 1: [Check overflow condition]
if rear >= size
Output “Overflow” and return
Step 2: [Increment rear pointer]
Rear = rear + 1
Step 3: [Insert an element]
Q [rear] = value
Step 4: [Set the front pointer]
If front = 0
front = 1
Step 5: return
2. Deletion Operation:
Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out
(FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue).
This operation is removed first entered item after second entered item and so on in the queue.
Step 1: [Check underflow condition]
if front = 0
Output “Underflow” and return
Step 2: [Remove an element]
Value = Q [front]
Step 3: [Check for empty queue]
If front = rear
front = 0
rear = 0
else
front = front + 1
16
DATA STRUCTURE LAB MANUAL
Program :
#include < stdio.h>
#include < conio.h>
#include < malloc.h>
#include < process.h>
#include < ctype.h>
struct linear_queue
{
int info;
struct linear_queue *next;
}*front,*rear,*newnode,*ptr;
void menu();
void display();
int underflow();
void enqueue(int);
void dequeue();
void main()
{
clrscr();
menu();
}
void menu()
{
int choice,item;
printf("MENU");
printf("\n1. Insert into the queue");
printf("\n2. Delete from queue");
printf("\n3. Display");
printf("\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
clrscr();
printf("\nEnter the item tobe inserted: ");
scanf("%d",&item);
enqueue(item);
clrscr();
printf("\nAfter inserting queue is:\n");
display();
getch();
clrscr();
menu();
break;
case 2:
17
DATA STRUCTURE LAB MANUAL
clrscr();
if(underflow()==1)
{
dequeue();
if(underflow()==1)
{
printf("\nAfter deletion queue is:\n");
display();
}
}
getch();
clrscr();
menu();
break;
case 3:
clrscr();
if(underflow()==1)
{
printf("The queue is:\n");
display();
}
getch();
clrscr();
menu();
break;
case 4:
exit(1);
default:
clrscr();
printf("Your choice is wrong\n\n");
menu();
}
} int underflow()
{
if((front==NULL)&&(rear==NULL))
{
printf("\nQueue is empty");
return(0);
}
else
{
return(1);
}
} void enqueue(int item)
{
newnode=(struct linear_queue*)malloc(sizeof(struct linear_queue));
18
DATA STRUCTURE LAB MANUAL
newnode->info=item;
if((front==NULL)&&(rear==NULL))
{
front=newnode;
rear=newnode;
newnode->next=NULL;
}
else
{
rear->next=newnode;
newnode->next=NULL;
rear=newnode;
}
} void dequeue()
{
if(front==rear)
{
front=NULL;
rear=NULL;
}
else
{
front=front->next;
}
}
void display()
{
int i;
ptr=front;
i=1;
while(ptr!=NULL)
{
printf("\nNode %d : %d",i,ptr->info);
ptr=ptr->next;
i++;
}
}
Experiment No.7
19
DATA STRUCTURE LAB MANUAL
Program:
#include < stdio.h>
#include < conio.h>
#include < malloc.h>
#include < process.h>
#include < ctype.h>
#define SIZE 10
void menu();
void display();
int underflow();
int overflow();
void enqueue(int);
void dequeue();
int cqueue[SIZE];
int front=-1;
int rear=-1;
void main()
{
clrscr();
menu();
}
void menu()
{
int choice,item;
printf("MENU");
printf("\n1. Insert into the queue");
printf("\n2. Delete from queue");
printf("\n3. Display");
printf("\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
clrscr();
if(overflow()==0)
{
printf("\nEnter the item tobe inserted: ");
scanf("%d",&item);
enqueue(item);
clrscr();
20
DATA STRUCTURE LAB MANUAL
printf("\nAfter inserting queue is:\n");
}
display();
getch();
clrscr();
menu();
break;
case 2:
clrscr();
if(underflow()==1)
{
dequeue();
if(underflow()==1)
{
printf("\nAfter deletion queue is:\n");
display();
}
}
getch();
clrscr();
menu();
break;
case 3:
clrscr();
if(underflow()==1)
{
printf("The queue is:\n");
display();
}
getch();
clrscr();
menu();
break;
case 4:
exit(1);
default:
clrscr();
printf("Your choice is wrong\n\n");
menu();
}
}
int underflow()
{
21
DATA STRUCTURE LAB MANUAL
if((front==-1)&&(rear==-1))
{
printf("\nQueue is empty");
return(0);
}
else
{
return(1);
}
}
int overflow()
{
if(((front==0)&&(rear==SIZE-1))||(front==rear+1))
{
printf("\nQueue is full\n");
return(1);
}
else
{
return(0);
}
}
void enqueue(int item)
{
if((front==-1)&&(rear==-1))
{
front=0;
rear=0;
}
else if(rear==SIZE-1)
{
rear=0;
}
else
{
rear=rear+1;
}
cqueue[rear]=item;
}
void dequeue()
{
if(front==rear)
{
22
DATA STRUCTURE LAB MANUAL
front=-1;
rear=-1;
}
else if(front==SIZE-1)
{
front=0;
}
else
{
front=front+1;
}
}
void display()
{
int i;
if(front<=rear)
{
for(i=front;i<=rear;i++)
{
printf("\nElement %d : %d",i+1,cqueue[i]);
}
}
else
{
for(i=front;i<=SIZE-1;i++)
{
printf("\nElement %d : %d",i+1,cqueue[i]);
}
for(i=0;i<=rear;i++)
{
printf("\nElement %d : %d",i+1,cqueue[i]);
}
}
}
Experiment No.8
23
DATA STRUCTURE LAB MANUAL
Program :
#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
void print_preorder(node * tree)
{
if (tree)
{
printf("%d\n",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}
}
void print_inorder(node * tree)
{
if (tree)
24
DATA STRUCTURE LAB MANUAL
{
print_inorder(tree->left);
printf("%d\n",tree->data);
print_inorder(tree->right);
}
}
void print_postorder(node * tree)
{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}
void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}
node* search(node ** tree, int val)
{
if(!(*tree))
{
return NULL;
}
if(val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
25
DATA STRUCTURE LAB MANUAL
void main()
{
node *root;
node *tmp;
//int i;
root = NULL;
/* Inserting nodes into tree */
insert(&root, 9);
insert(&root, 4);
insert(&root, 15);
insert(&root, 6);
insert(&root, 12);
insert(&root, 17);
insert(&root, 2);
/* Printing nodes of tree */
printf("Pre Order Display\n");
print_preorder(root);
printf("In Order Display\n");
print_inorder(root);
printf("Post Order Display\n");
print_postorder(root);
/* Search node into tree */
tmp = search(&root, 4);
if (tmp)
{
printf("Searched node=%d\n", tmp->data);
}
else
{
printf("Data Not found in tree.\n");
}
/* Deleting all nodes of tree */
deltree(root);
}
26
DATA STRUCTURE LAB MANUAL
27
DATA STRUCTURE LAB MANUAL
28
