ds lab
1. Write a C Program to
construct a stack of integers and to perform the following operations on it: a.
Push
b. Pop
c. Display
The program should print appropriate messages
for stack overflow, stack underflow and stack
empty.
#include<stdio.h>
#include<conio.h>
#include<process.h>
#define MAX_SIZE 4
int s[MAX_SIZE],top=-1;
void main()
{
void PUSH(int); void POP();
void DISPLAY();
int ch,x;
while(1)
{ clrscr();
printf("\n enter your choice \n\n 1.PUSH
\n 2.POP \n 3.DISPLAY \n 4.EXIT \n\n");
scanf("%d",&ch);
switch(ch)
{
case
1: printf("\n enter the element to be inserted \n");
scanf("%d",&x);
PUSH(x);
break;
case 2: POP();
break;
case
3: DISPLAY();
break;
case
4: printf("\n Bye! See you next time.... \n");
getch();
exit(0);
default:
printf("\n Illegal choice, try again \n");
}
printf("\n\n press any key to
continue........\n"); getch();
}
}
void PUSH(int x)
{
if(top>=MAX_SIZE-1) printf("\n
stack overflow, insertion not possible \n"); else
{
top++;
s[top]=x;
printf("\n
element %d has been inserted \n",x);
}
}
void POP() {
int temp;
if(top==-1)
printf("\n stack
underflow, deletion not possible \n");
else
{
temp=s[top];
top--;
printf("\n
deleted element is %d \n",temp);
}
}
void DISPLAY()
{
int i;
if(top==-1)
printf("\n stack is empty,
no elements to display \n"); else
{
printf("\n\n
the elements on the stack are \n\n");
for(i=0;i<=top;i++)
printf("%d\t",s[i]);
}
2. Write recursive C
Programs for
a. Searching
an element on a given list of integers using the Binary Search method.
b. Solving
the Towers of Hanoi problem.
a. Searching an element
on a given list of integers using the Binary Search method.
#include<stdio.h>
#include<conio.h>
void main()
{
int a[10],n,key,i,low,high,res; int binsearch(int
a[10],int key,int low,int high); clrscr();
printf("\n\n enter the number of elements to be
stored in the array \n\n"); scanf("%d",&n);
printf("\n\n enter the array elements \n\n"); for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n\n enter the element to be searched
\n\n");
scanf("%d",&key);
low=0;
high=n-1;
res=binsearch(a,key,low,high);
if(res = = -1) printf("\n\n element %d is not found
\n\n",key); else
printf("\n\n element %d is found at position %d
\n\n",key,res+1); getch();
}
int binsearch(int a[10],int key,int low,int high)
{ int mid; if(low>high)
return -1; mid=(low+high)/2; return( key = = a[mid]?
mid : key>a[mid]? binsearch(a,key,mid+1,high) : binsearch(a,key,low,mid-1));
}
b. Solving the Towers of
Hanoi problem.
#include<stdio.h>
#include<conio.h>
int count; void main() { int n;
void THANOI(int,char,char,char);
clrscr(); printf("\n Enter the number of disks
to be considered \n\n");
scanf("%d",&n);
THANOI(n,'A','C','B');
printf("\n Total number of moves= %d
\n",count);
getch();
}
void THANOI(int n,char start,char end,char mid)
{
/* If
only one disk, move it from A to C and return */ if(n = = 1)
{
printf("\n move disk %d from peg %c to peg
%c\n",n,start,end);
count++; getch(); return;
}
/* move top
n-1 disks from A to B using C as auxiliary */
THANOI(n-1,start,mid,end);
/* move
remaining disk from A to C */
printf("\n move disk %d from peg %c to
peg %c\n",n,start,end); count++;
getch();
/* move n-1
disk from B to C using A as auxiliary */
THANOI(n-1,mid,end,start);
}
3. Write a C Program to convert and print a
given valid parenthesized infix expression
consists of single character operands and the binary operators + (plus),
- (minus), *(multiply) and / (divide) to suffix/postfix expression.
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<process.h>
#define MAX_SIZE 25
char s[MAX_SIZE]; int top=-1;
void main()
{
void PUSH(char); char POP(); int PRIORITY(char); char
infix[25],postfix[25]; int i=0,j=0;
clrscr();
PUSH('#');
printf("\n enter a valid infix expression
\n\n"); gets(infix);
while(infix[i]! = '\0' )
{
if(isalnum(infix[i]))
postfix[j++]=infix[i];
else
if(infix[i] = = '(' )
PUSH(infix[i]);
else
if(infix[i] = = ')' )
{
while(
s[top]! = '(' )
postfix[j++]=POP();
POP();
}
else if(
infix[i] = = '+' || infix[i] = = '-' || infix[i] = = '*' || infix[i] = = '/' )
{
while(PRIORITY(s[top])>=PRIORITY(infix[i])) postfix[j++]=POP(); PUSH(infix[i]);
}
else
{
printf("\n Illegal operator %c \n",infix[i]); getch(); exit(0); }
i++; }
while(s[top]! = '#' )
postfix[j++]=POP();
postfix[j]='\0';
printf("\n given infix expession is: %s \n\n
converted postfix expression is: %s \n",infix,postfix); getch();
}
void PUSH(char ch)
{
if(top>=MAX_SIZE-1)
{
printf("\n stack overflow \n"); getch();
exit(0); }
s[++top]=ch;
}
char POP()
{ if(top==-1)
{
printf("\n stack underflow \n"); getch();
exit(0); } return s[top--];
}
int PRIORITY(char ch)
{
if(ch = = '(' || ch = = '#' ) return
(1);
else if(ch = = '+' || ch = = '-' ) return
(2);
else if(ch = = '*' || ch = = '/' ) return
(3);
}
4. Write a C Program to
evaluate a valid suffix/postfix expression using stack. Assume that the suffix/ postfix expression is read as a
single line consisting of non-negative single digit operands and binary arithmetic operators. The
arithmetic operators are + (add), - (subtract), *(multiply) and
/ (divide).
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<process.h>
#define MAX_SIZE 25
int s[MAX_SIZE],top=-1;
char expr[25];
void main()
{
void PUSH(int); int POP(); int i=0,op1,op2,op3;
clrscr(); printf("\n enter a valid postfix
expression \n\n"); gets(expr);
while(expr[i]!='\0')
{
if(isdigit(expr[i]))
PUSH(expr[i]-'0');
else
{
op2=POP();
op1=POP();
switch(expr[i])
{
case
'+':op3=op1+op2;
break;
case
'-':op3=op1-op2;
break;
case
'*':op3=op1*op2;
break;
case
'/':op3=op1/op2;
break;
default:
printf("\n invalid operator %c \n",expr[i]);
getch();
exit(0);
}
PUSH(op3);
}
i++;
} if(top>0) printf("\n invalid input
expression %s \n",expr);
else printf("\n the result of the expression %s
is %d \n",expr,s[top]); getch();
}
void PUSH(int x)
{
if(top>=MAX_SIZE-1)
{
printf("\n stack overflow \n"); getch();
exit(0); } s[++top]=x;
}
int POP() { if(top==-1) {
printf("\n invalid infix expression %s
\n",expr); getch(); exit(0); } return s[top--];
}
5. Write a C Program to simulate the
working of a queue of integers using an array. Provide the following operations: a. Insert
b. Delete
c. Display
#include<stdio.h>
#include<conio.h>
#include<process.h>
#define MAX_SIZE 4
int Q[MAX_SIZE], f = -1, r = -1; void main()
{
int ch,x;
void QINSERT(int); void QDELETE();
void QDISPLAY();
while(1)
{ clrscr();
printf("\n 1.insert \n 2.delete \n 3.display \n 4.exit \n\n enter
your choice \n\n");
scanf("%d",&ch);
switch(ch)
{
case
1:
printf("\n
enter the element to be inserted into the queue \n\n");
scanf("%d",&x); QINSERT(x); break; case 2:
QDELETE(); break; case 3:
QDISPLAY(); break; case 4:
printf("\n
Bye!!! See you later \n");
getch(); exit(0); default:
printf("\n
Invalid choice... try again \n");
} /* end of
switch */
printf("\n\n press any key to continue........\n"); getch();
} /* end of
while */
} /* end of main */
void QINSERT(int x)
{
if(r>=MAX_SIZE-1)
{
printf("\n
queue overflow, insertion not possible \n");
return;
}
r++;
Q[r]=x;
if(f = = -1)
f
= 0;
printf("\n element %d has been inserted
into the queue \n",x);
}
void QDELETE()
{ int
temp; if(f = = -1)
{
printf("\n
queue is empty, deletion not possible \n");
return;
}
temp=Q[f];
if(f = = r)
f
= r = -1;
else
f++;
printf("\n deleted element from the queue
is %d \n",temp);
}
void QDISPLAY()
{
int i; if(f = = -1)
{
printf("\n
queue is empty \n");
return;
}
printf("\n\n elements of the quere are
\n\n");
for(i = f; i
<= r; i++)
printf("%d\t",Q[i]);
}
6. Write a C
Program to simulate the working of a circular queue of integers using an array.
Provide the following operations: a. Insert
b. Delete
c. Display
#include<stdio.h>
#include<conio.h>
#include<process.h>
#define MAX_SIZE 4
int CQ[MAX_SIZE],cf = -1,cr = -1;
void main()
{
int ch,x;
void
CQINSERT(int); void CQDELETE();
void
CQDISPLAY();
while(1)
{
clrscr();
printf("\n
1.insert \n\n 2.delete \n\n 3.display \n\n 4.exit \n\n");
printf("\n enter your choice
\n\n"); scanf("%d",&ch);
switch(ch)
{
case
1:
printf("\n
enter the element to be inserted \n");
scanf("%d",&x); CQINSERT(x); break; case
2: CQDELETE(); break; case
3: CQDISPLAY(); break; case
4:
printf("\n
Bye!. See you later...\n");
getch(); exit(0); default:
printf("\n
Invalid choice, try again \n");
}
/* end of switch */
printf("\n\n press any key to
continue........\n"); getch();
} /* end of
while */
} /* end of main */
void CQINSERT(int x)
{ int
temp; temp=cr; if(cr = = MAX_SIZE-1) cr = 0;
else
cr++;
if(cf = = cr)
{
printf("\n queue overflow
\n"); cr = temp; return;
}
CQ[cr]=x;
if(cf = = -1)
cf
= 0;
}
void CQDELETE()
{ int
temp; if(cr = = -1)
{
printf("\n
circular queue is empty \n");
return;
}
temp=CQ[cf];
if(cf = = cr)
cf
= cr = -1;
else if(cf = =
MAX_SIZE-1) cf = 0;
else
cf++;
printf("\n deleted element from the
circular queue is %d \n",temp);
}
void CQDISPLAY()
{
int i;
if(cf = = -1)
{
printf("\n
circular queue is empty \n");
return;
}
printf("\n the elements of the circular
queue are \n\n");
if(cf > cr)
{
for(i=cf; i<= AX_SIZE-1; i++) printf("%d\t",CQ[i]); for(i=0;i<=cr;i++) printf("%d\t",CQ[i]);
}
else
for(i=cf;i<=cr;i++)
printf("%d\t",CQ[i]);
}
7. Write C program to
simulate the working of a priority queue of integers using an array. Provide the
following operations:
a. Insert
b. Delete
c. Display
#include<stdio.h>
#include<conio.h>
#include<process.h>
#define MAX_SIZE 2
int PQ[3][MAX_SIZE], pf[3]={-1,-1,-1},
pr[3]={-1,-1,-1}; void main()
{ int ch,x,p;
void
PQINSERT(int,int); void PQDELETE();
void
PQDISPLAY();
while(1)
{
clrscr();
printf("\n
1.insertion\n\n 2.deletion\n\n 3.display\n\n 4.exit\n\n");
printf("\n enter your
choice\n\n"); scanf("%d",&ch); switch(ch)
{
case
1:
printf("\n
enter the element to be inserted and also the priority \n\n");
scanf("%d%d",&x,&p);
PQINSERT(x,p-1); break; case
2: PQDELETE(); break; case
3: PQDISPLAY(); break; case 4:
printf("\n
Bye.. see you later...\n");
getch(); exit(0); default:
printf("\n\n
invalid choice, try again later \n");
}
/* end of switch */
printf("\n\n press any key to continue
\n\n"); getch();
} /* end of
while */ } /* end of main */ void PQINSERT(int x,int i) { if(pr[i]>=MAX_SIZE-1)
{
printf("\n
queue %d is full, insertion not possible \n",i+1);
return;
}
pr[i]++; PQ[i][pr[i]] = x;
printf("\n element %d is inserted into
queue %d \n",x,i+1); if(pf[i] = =
-1)
pf[i]
= 0;
}
void PQDELETE()
{ int i,temp;
for(i=0;i<3;i++)
{
if(pf[i]
= = -1)
|
|
|
printf("\n\n
queue %d is empty \n",i+1); |
|
|
else |
|
|
|
|
{ |
|
|
|
temp =
PQ[i][pf[i]]; |
|
|
|
if(pf[i]
= = pr[i]) |
|
|
|
pf[i] = pr[i] = -1; |
|
|
|
else |
|
|
|
pf[i]++; |
|
|
|
printf("\n element %d is deleted from
queue %d \n",temp,i+1); |
|
|
|
break;
|
|
|
|
} |
|
} |
} |
|
void PQDISPLAY()
{
int i,j;
for(i=0;i<3;i++)
{
if(pf[i] = = -1) printf("\n\n
queue %d is empty \n",i+1);
else
{
printf("\n\n
elements of queue %d are \n\n",i+1);
for(j=pf[i];j<=pr[i];j++)
printf("%d\t",PQ[i][j]);
}
}
}
8. Write a C Program using dynamic variables and pointers, to construct a singly linked list consisting of the following information in each node: student id (integer), student name (character string) and semester (integer). The operations to be supported are:
8 (a)
Operations:
(i)Inserting node at
front end
(ii)Deleting node based
on student id
(iii)Displaying all the
nodes in the list
#include<stdio.h>
#include<string.h>
typedef struct sll
{
int sid;
char name[25]; int sem;
struct sll *link; }node; node *first=NULL;
void main()
{
int ch,n,i,id,sem,pos; char name[25]; void
INS_FRONT(int,char [],int); void DEL_ID(int);
void DISPLAY();
while(1) { printf("\n 1.create \n\n 2.insertion
at the front \n"); printf("\n
3.deletion of a node based on student id \n");
printf("\n 4.display \n"); printf("\n 5.exit \n\nEnter your
choice \n\n"); scanf("%d",&ch);
switch(ch) { case 1:
printf("\n enter the number of nodes to be
initially created \n");
scanf("%d",&n); for(i=0;i<n;i++)
{ printf("\n enter the student id, name and sem
for student %d \n",i+1);
scanf("%d%s%d",&id,name,&sem);
INS_FRONT(id,name,sem);
} break; case 2: printf("\n enter the id, name
and sem of a new student to be inserted at the front \n");
scanf("%d%s%d",&id,name,&sem); INS_FRONT(id,name,sem); break;
case 3:
printf("\n enter the student id to delete
his/her details \n"); scanf("%d",&id); DEL_ID(id); break;
case 4:
DISPLAY(); break;
case 5:
printf("\n BYE!!! SEE YOU LATER \n");
getch(); exit(0); default:
printf("\n Illegal choice, try
again...\n");
} /* end of switch */
printf("\n\n press any key to
continue...\n\n"); getch();
} /* end of while */
} /* end of main */
void INS_FRONT(int id,char name[25],int sem)
{ node *new; new=(node*)malloc(sizeof(node));
new->sid=id; strcpy(new->name,name); new->sem=sem;
new->link=NULL;
if(first == NULL) first = new; else {
new->link=first; first=new;
}
}
void DEL_ID(int id)
{ node *temp,*prev;
temp=first;
while((temp->sid!=id)&&(temp!=NULL))
{ prev=temp;
temp=temp->link;
} if(temp == NULL) printf("\n student id %d is
not found, deletion not possible \n",id);
else if(temp==first)
{ first=first->link; free(temp); } else
{
Prev->link=temp-.link;
Free(temp);
}
}
void DISPLAY()
{ node *temp;
if(first == NULL)
printf("\n list is empty \n");
else
{
temp=first;
while(temp!=NULL)
{
printf("\n%d-->%s-->%d\n",temp->sid,temp->name,temp->sem);
temp=temp->link;
}
}
}
8(b) Operations:
(i)Inserting node at
front
(ii)Searching node based
on student id and update information
(iii)Displaying all the
nodes in the list
#include<stdio.h>
#include<string.h>
typedef struct sll
{
int sid;
char name[25]; int sem; struct sll *link; }node;
node *first=NULL;
void main()
{
int ch,n,i,id,sem,pos; char name[25]; void
INS_FRONT(int,char [],int); void SEARCH_UPDATE(int);
void DISPLAY();
while(1)
{
printf("\n 1.create \n\n 2.insertion at the
front \n"); printf("\n 3.search and update based on student id \n\n
4.display \n"); printf("\n 5.exit \n\nEnter your choice \n\n");
scanf("%d",&ch);
switch(ch) { case 1:
printf("\n enter the number of nodes to be
initially created \n");
scanf("%d",&n); for(i=0;i<n;i++)
{
printf("\n enter the student id, name and sem
for student %d \n",i+1);
scanf("%d%s%d",&id,name,&sem);
INS_FRONT(id,name,sem);
}
break;
case 2:
printf("\n enter the id, name and sem of a new
student to be inserted at the front \n");
scanf("%d%s%d",&id,name,&sem); INS_FRONT(id,name,sem); break;
case
3:
printf("\n enter the student id to search and
update his/her details \n"); scanf("%d",&id);
SEARCH_UPDATE(id);
break; case 4: DISPLAY(); break;
case 5:
printf("\n BYE!!! SEE YOU LATER \n");
getch(); exit(0); default:
printf("\n Illegal choice, try
again...\n");
} /* end of switch */
printf("\n\n press any key to
continue...\n\n"); getch();
} /* end of while */
} /* end of main */
void INS_FRONT(int id,char name[25],int sem)
{ node *new; new=(node*)malloc(sizeof(node));
new->sid=id; strcpy(new->name,name); new->sem=sem;
new->link=NULL;
if(first == NULL)
first = new;
else { new->link=first; first=new;
}
}
void SEARCH_UPDATE(int id)
{ node *temp;
temp=first;
while((temp->sid!=id)&&(temp!=NULL))
temp=temp->link;
if(temp == NULL) printf("\n given id %d is not
found, updation not possible \n",id);
else
{
printf("\nenter
the new id, name & sem to update the old details\n");
scanf("%d%s%d",&temp->sid,temp->name,&temp->sem);
}
}
void DISPLAY()
{ node *temp;
if(first == NULL)
printf("\n list is empty \n");
else
{
temp=first;
while(temp!=NULL)
{ printf("\n%d-->%s-->%d\n",temp->sid,temp->name,temp->sem);
temp=temp->link;
}
}
}
9. Write a C program
using dynamic variables and pointer to construct a Doubly linked list
consisting of the following information in each node:student
ID(integer),student name(string) and semester (integer. The operations to be
supported are:
9 (a) Create a doubly
linked list by adding each node at the front.
b. insert a new node to
the left of the node whose key value is read as an input
d. display the contents
of the list.
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
typedef struct dll
{ int sid;
char name[25]; int sem;
struct dll *llink, *rlink;
} node;
node *first = NULL;
void main() { int ch, n, i, id,pos, sem, key; char name[25];
void INS_FRONT(int, char[], int); void INS_KEY(int, int, char[], int);
void DISPLAY();
while (1) {
printf("\n 1.create \n\n 2.insertion new node to
the left of the node \n"); printf("\n 3.display \n");
printf("\n 4.exit \n\nEnter your choice \n\n");
scanf("%d", &ch); switch (ch) { case 1:
printf("\n enter the number of nodes to be
initially created \n"); scanf("%d", &n);
for (i = 0; i < n; i++) { printf("\n enter
the student id, name and sem for student %d \n", i + 1);
scanf("%d%s%d", &id, name, &sem);
INS_FRONT(id, name, sem);
} break;
case 2:
printf("\n enter the key value at which node has to be inserted \n");
scanf("%d", &key);
printf("\n
enter the id, name and sem of a new student to be inserted at the front
\n"); scanf("%d%s%d", &id, name, &sem);
INS_KEY(key, id, name, sem); break;
case 3:
DISPLAY(); break;
case 4:
printf("\n BYE!!! SEE YOU LATER \n");
exit(0);
default:
printf("\n Illegal choice, try
again...\n");
} /* end of switch */
printf("\n\n press any key to
continue...\n\n"); getchar(); } /* end of while */
} /* end of main */
void INS_FRONT(int id, char name[25], int sem)
{ node *new; new = (node *)malloc(sizeof(node)); new->sid =
id; strcpy(new->name, name); new->sem = sem;
new->llink = new->rlink = NULL;
if (first == NULL) first = new;
else {
new->rlink =
first; first->llink = new;
first = new;
}
}
void INS_KEY(int key, int id, char name[25], int sem)
{ node *new, *temp; new = (node *)malloc(sizeof(node));
new->sid = id; strcpy(new->name, name); new->sem = sem;
new->llink = new->rlink = NULL;
if (first == NULL) { printf("\n list is
empty\n\n"); return; }
temp = first;
while (temp != NULL && temp->sid != key)
temp = temp->rlink;
if (temp == NULL) { printf("\n node with data
part %d is not found \n \n", key); return;
}
if (temp == first) { new->rlink = first;
first->llink = new; first = new; } else { new->llink = temp->llink;
new->rlink = temp; temp->llink->rlink = new; temp->llink = new;
}
}
void DISPLAY() {
node *temp;
if (first == NULL) { printf("\n list is empty
\n"); return;
}
printf("\nList Contents (Forward):\n");
temp = first; while (temp != NULL) { printf("%d --> %s -->
%d\n", temp->sid, temp->name, temp->sem); temp = temp->rlink;
}
printf("\nList Contents (Backward):\n");
temp = first; while (temp->rlink != NULL) { temp =
temp->rlink;
}
while (temp != NULL) { printf("%d --> %s
--> %d\n", temp->sid, temp->name, temp->sem); temp =
temp->llink;
}
9. (b)
a.Create a doubly linked
list by adding each node at the front.
c. delete
the node of a given data, if it found, otherwise display appropriate message.
d. display
the contents of the list
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
typedef struct dll
{ int sid;
char name[25]; int sem;
struct dll *llink, *rlink;
} node;
node *first = NULL;
void main() { int ch, n, i, id, sem, key; char
name[25]; void INS_FRONT(int, char[], int); void DEL_KEY(int);
void DISPLAY();
while (1) { printf("\n 1.create \n\n");
printf("\n 2.deletion of a node based on student id \n 3.display
\n"); printf("\n 4.exit \n\nEnter your choice \n\n");
scanf("%d", &ch); switch (ch) {
case 1:
printf("\n enter the number of nodes to be
initially created \n"); scanf("%d", &n);
for (i = 0; i < n; i++) { printf("\n enter
the student id, name and sem for student %d \n", i + 1);
scanf("%d%s%d", &id, name, &sem);
INS_FRONT(id, name, sem);
} break;
case 2:
printf("\n enter the student id to delete
his/her details \n"); scanf("%d", &key);
DEL_KEY(key); break; case 3:
DISPLAY(); break;
case 4:
printf("\n BYE!!! SEE YOU LATER \n");
exit(0);
default:
printf("\n Illegal choice, try
again...\n");
} /* end of switch */
printf("\n\n press any key to
continue...\n\n"); getchar(); } /* end of while */
} /* end of main */
void INS_FRONT(int id, char name[25], int sem)
{ node *new; new = (node *)malloc(sizeof(node));
new->sid = id; strcpy(new->name, name); new->sem = sem; new->llink
= new->rlink = NULL;
if (first == NULL) first = new;
else {
new->rlink =
first; first->llink = new;
first = new;
}
}
void DEL_KEY(int key) { node *temp; if (first ==
NULL) { printf("\n list is empty\n\n"); return; }
temp = first; while (temp != NULL &&
temp->sid != key)
temp = temp->rlink;
if (temp == NULL) { printf("\n node with data
part %d is not found \n \n", key); return; }
if (temp == first) { first = first->rlink; if
(first != NULL) first->llink = NULL; free(temp); } else {
temp->llink->rlink = temp->rlink; if
(temp->rlink != NULL) temp->rlink->llink = temp->llink; free(temp);
}
}
void DISPLAY() { node *temp;
if (first == NULL) { printf("\n list is empty
\n"); return;
}
printf("\nList Contents (Forward):\n");
temp = first; while (temp != NULL) { printf("%d --> %s -->
%d\n", temp->sid, temp->name, temp->sem); temp = temp->rlink;
}
printf("\nList Contents (Backward):\n");
temp = first; while (temp->rlink != NULL) { temp =
temp->rlink;
}
while (temp != NULL) { printf("%d --> %s
--> %d\n", temp->sid, temp->name, temp->sem); temp =
temp->llink;
}
10. Write a C Program
a. To
construct a binary search tree of integers.
b. To
traverse the tree using all the methods i.e inorder, preorder and postorder.
c. To
display the elements in the tree.
#include<stdio.h>
#include<conio.h> #include<stdlib.h>
typedef struct tree
{ int
data; struct tree *lchild,*rchild;
}node;
node *root=NULL; void main() { int n,i,x,ch;
void CREATE(int); void DISPLAY(node*); void
INORDER(node*); void PREORDER(node*);
void POSTORDER(node*);
while(1)
{ clrscr();
printf("\n\n 1.create \n\n 2.display \n\n
3.inorder traversal\n"); printf("\n 4.preorder traversal \n\n
5.postorder traversal \n\n 6.exit\n\n"); printf("\n enter your choice
\n\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\n enter the number of nodes to be created in the tree
\n\n"); scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n enter the data part
of node %d\n",i+1); scanf("%d",&x);
CREATE(x);
}
break;
case 2:
if(root = = NULL)
printf("\n\n
tree is empty \n\n");
else
{
printf("\n\n
elements of the BST are \n\n");
DISPLAY(root);
} break; case
3: if(root = = NULL)
printf("\n\n
tree is empty \n\n");
else
{
printf("\n\n
inorder tree traversal is \n\n");
INORDER(root);
}
break;
case 4:
if(root = = NULL)
printf("\n\n
tree is empty \n\n");
else
{
printf("\n\n
preorder tree traversal is \n\n");
PREORDER(root);
}
break;
case 5:
if(root = = NULL)
printf("\n\n
tree is empty \n\n");
else
{
printf("\n\n
postorder tree traversal is \n\n");
POSTORDER(root);
}
break;
case 6:
printf("\n\n Bye!!!! See You Later!!!! \n\n"); getch();
exit(0);
default:
printf("\n\n Illegal choice \n\n");
}
printf("\n\n enter any key to continue
\n\n"); getch();
}
}
void CREATE(int x)
{ node
*new,*temp;
new=(node*)malloc(sizeof(node));
new->data=x;
new->lchild=new->rchild=NULL;
if(root = = NULL) root=new;
else
{
temp=root; while(1)
{
if(x<temp->data) if(temp->lchild==NULL)
{
temp->lchild=new;
break;
}
else
temp=temp->lchild;
else
if(x>temp->data)
if(temp->rchild==NULL)
{
temp->rchild=new;
break;
}
else
temp=temp->rchild;
else
{
printf("\n\n
node with data %d already exists, enter the new data \n\n",x); scanf("%d",&x); CREATE(x); break;
}
}
}
}
void DISPLAY(node *R)
{
if(R!=NULL)
{
DISPLAY(R->lchild); printf("%d\t",R->data);
DISPLAY(R->rchild);
}
}
void INORDER(node *R)
{
if(R!=NULL)
{
INORDER(R->lchild); printf("%d\t",R->data); INORDER(R->rchild);
}
}
void PREORDER(node *R)
{
if(R!=NULL)
{
printf("%d\t",R->data);
PREORDER(R->lchild); PREORDER(R->rchild);
}
}
void POSTORDER(node *R)
{ if(R!=NULL)
{
POSTORDER(R->lchild); POSTORDER(R->rchild);
printf("%d\t",R->data);
}
}
}
Comments
Post a Comment