Sri

PROBLEM 98:- Write a program to store a character string in a block of memory space created by MALLOC() and then modify the same to store a larger string. PROCEDURE:1. MALLOC() function is used to allocate memory at run time , initialized with garbage values 2. realloc() is used to modify the existing size of memory allocated with the help of MALLOC()

CODE:#include<stdio.h> #define NULL 0 void main() { char *buffer; if((buffer=(char *)malloc(10))= = NULL) { printf(“malloc failed”); exit(1); } printf(“buffer of size %d created \n”,_msize(buffer)); strcpy(buffer,”HYDERBAD”); printf(“\nBuffer containsn:%s\n”,buffer); if((buffer=(char *)realloc(buffer,15))= =NULL) { printf(“reallocation failed\n”); exit(1); } printf(“\nbuffer size modified\n”); printf(“\nbuffer still contains : %s\n”,buffer); strcpy(buffer,”SECUNDERABAD”); printf(“\nbuffer now contains : %s\n”,buffer); free(buffer); }

1

PROBLEM 99:- Write a small example program to explain the usage of CALLOC(). PROCEDURE:1. CALLOC() function is used to allocate memory for a set of blocks at run time

CODE:#include<stdio.h> #define NULL 0 void main() { char *buffer; if((buffer=(char *)calloc(10,1))= = NULL) { printf(“calloc failed”); exit(1); } printf(“buffer of size %d created \n”,_msize(buffer)); strcpy(buffer,”HYDERBAD”); printf(“\nBuffer containsn:%s\n”,buffer); if((buffer=(char *)realloc(buffer,15))= =NULL) { printf(“reallocation failed\n”); exit(1); } printf(“\nbuffer size modified\n”); printf(“\nbuffer still contains : %s\n”,buffer); strcpy(buffer,”SECUNDERABAD”); printf(“\nbuffer now contains : %s\n”,buffer); free(buffer); }

2

DATA STRUCTURES: PROGRAMS ON STACKS PROBLEM 100:- Program to implement push and pop operations in a stack using arrays. PROCEDURE:1.PUSH(x,n,top) x is item to be pushed , n is max. no. of elements in stack,top initially set to -1 a) if(top = n-1) print “stack overflow” b) else increment top by 1, stack[top]=x; 2. POP(x,n,top) x is item to be popped , n is max. no. of elements in stack,top is pointing to a position in stack a)if(top=-1) print “stack underflow” b) else set x=stack[top] ,return(x) and decrement top by 1

CODE:#include<stdio.h> #define max 10 void push(int); int pop(); void display(); int stack[max],top=-1; void main() { char ch=’y’; int c,x; while(ch= =’y’) { printf(“1: push 2: pop 3: display 4: exit\n”); printf(“enter your choice”); scanf(“%d”,&c); switch(c) { case 1: printf(“enter the item to push”); scanf(“%d”,&x); push(x); break; case 2: printf(“the item popped is %d”,pop()); break; case 3: printf(“the contents of the stack are\n”); display();

3

break; } printf(“do you want to continue (y/n)”); ch=getchar(); } } void push(int x) { if(top= = max-1) { printf(“stack is full”); exit(); } stack[++top]=x; } int pop() { if (top= = -1) { printf(“stack is empty”); exit(); } return(stack[top--]); } void display() { int i; if(top= =-1) { printf(“stack is empty”); exit(); } else { for(i=top;i>=0;i--) printf(\n%3d”,stack[i]); } }

4

PROBLEM 101:- Write a program to convert infix to post fix expression. PROCEDURE:POSTFIX(Q,P) Suppose Q is an arithmetic expression written in infix notation. This alg. finds the equivalent postfix expression P. 1. Push “(“ onto STACK, and add “)” to the end of Q 2. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty: 3. if an operand is encountered, add it to P. 4. if a left parenthesis is encountered , push it onto STACK. 5. if an operator X is encountered ,then : a. Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has the same precedence as or higher precedence than X. b. Add X to STACK. [ end of IF structure] 6. if a right parenthesis is encountered, then: a. Repeatedly pop from STACK and add to P each operator(on the top of STACK} until a left parenthesis is encountered. b. Remove the left parenthesis. [end of IF structure] [end of step 2 loop.] 7. exit.

CODE:#include<stdio.h> void push(); char pop(); int prec();int top=-1; char ifix[25], pfix[25],stack[20]; void main() { int i,j=0; char c; printf(“enter the infix expression”); gets(ifix); for(i=0;ifix[i]!=’\0’,i++) { if(isalpha(ifix[i])) { pfix[j]=ifix[i]; j++; } else if (ifix[i]= =’(‘) push(ifix[i]); else

5

if(ifix[i]= =’*’ || ifix[i]= =’\’ || ifix[i]= =’+’ || ifix[i]= =’-‘) { while(prec(stack[top])>= prec(ifix[i])) pfix[j++]=pop(); push(ifix[i]); } else if(ifix[i]= =’)’) { while(stack[top]!=’(‘) pfix[j++]=pop(); c=pop(); } } pfix[j]=’\0’; printf(“the postfix form of the infix %s is %s”,ifix,pfix); } void push(char c) { stack[++top]=c; } char pop() { return(stack[top--]); } int prec(char c) { switch(c ) { case ‘*’: case ‘/’: return(5); break; case ‘+’: case ‘-‘: return(4); break; case ‘(‘: return(1); } }

Input:- enter the infix expression Ouput:- Postfix expression is : abc*d/+

a+(b*c/d)

6

PROBLEM 102:- Write a program to convert infix to pre fix expression. PROCEDURE:PREFIX(Q,P) Suppose Q is an arithmetic expression written in infix notation first reverse it. This alg. finds the equivalent prefix expression P. 1.Push “)“ onto STACK, and add “(” to the end of Q 2.Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty: 3.if an operand is encountered, add it to P. 4.if a right parenthesis is encountered , push it onto STACK. 5.if an operator X is encountered ,then : c. Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has the higher precedence than X. d. Add X to STACK. [ end of IF structure] 6.if a left parenthesis is encountered, then: e. Repeatedly pop from STACK and add to P each operator(on the top of STACK} until a right parenthesis is encountered. f. Remove the right parenthesis. [end of IF structure] [end of step 2 loop.] 7.reverse P. 8.exit.

CODE:#include<stdio.h> void push();char pop();int prec();int top=-1; char ifix[25], pfix[25],stack[20]; void main() { int i,j=0; char c; printf(“enter the infix expression”); gets(ifix); strrev(ifix); for(i=0;ifix[i]!=’\0’,i++) { if(isalpha(ifix[i])) { pfix[j]=ifix[i]; j++; } else if (ifix[i]= =’)‘)

7

push(ifix[i]); else if(ifix[i]= =’*’ || ifix[i]= =’\’ || ifix[i]= =’+’ || ifix[i]= =’-‘) { while(prec(stack[top])> prec(ifix[i])) pfix[j++]=pop(); push(ifix[i]); } else if(ifix[i]= =’(’) { while(stack[top]!=’)‘) pfix[j++]=pop(); c=pop(); } } pfix[j]=’\0’; printf(“the prefix form is %s ”,strrev(pfix)); } void push(char c) { stack[++top]=c; } char pop() { return(stack[top--]); } int prec(char c) { switch(c ) { case ‘*’: case ‘/’: return(5); break; case ‘+’: case ‘-‘: return(4); break; case ‘)‘: return(1); } } Input:-enter infix expression: a+(b*c/d) Output:- Prefix expression :+a/*bcd

8

PROBLEM 103:- Program to evaluate a given postfix expression using stack PROCEDURE:This procedure VALUE of an arithmetic expression P written in postfix notation. 1. Add a right parenthesis”)” at the end of P(sentinel). 2. Scan P from left to right and repeat steps 3 and 4 for each element of P until the sentinel “)” is encountered. 3. If an operand is encountered, put it on STACK. 4. If an operator X is encountered, then: a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element. b) Evaluate B X A. c) Place the result of (b) back on STACK. [End of If structure.] 5. Set VALUE equal to the top element on STACK. 6. Exit.

CODE:#include<stdio.h> #define max 30 int top=-1; int stack[max]; void push(int a) { stack[++top]=a; } int pop() { return(stack[top--]); } main() { int i,j=0,c[30],a,v; char s[100]; clrscr(); printf(“Enter the postfix expression”); for(i=0;(s[i]=getchar())1=’\n’;i++) { if(s[i]>=’a’ && s[i]<=’z’) c[j++]=i; } printf(“Enter values”); for(i=0;i<j;j++) {\ printf(“%c=”,s[c[i]]); scanf(“%d”,&c[i]);

9

} j=0; for(i=0;s[i]!=’\n’;i++) if(s[i]>=’a’ && s[i]<=’z’) push(c[j++]); else { v=pop(); switch(s[i]) { case ‘+’ : a=pop()+v; break; case’-‘: a=pop()-v; break; case’*’: a=pop()*v; break; case ‘/’: a=pop()/v; break; } push(a); } printf(“the result is %d”,pop()); getch(); }

Input:-enter postfix expression: abc*d/+ Enter values for a,b,c,d: 5 8 2 2

Output:-the result is 13

10

PROBLEM 104:- Towers of Hanoi( Stack Application) PROCEDURE:TOWER(N,BEG,AUX,END) This procedure gives a recursive solution to the Towers of Hanoi problem for N disks. 1. If N=1, then: (a) Write: BEG->END. (b) Return. [End of If structure.] 2. [Move N-1 disks from peg BEG to peg AUX.] Call TOWER(N-1,BEG,END,AUX). 3. Write: BEG->END. 4. [Move N-1 disks from peg AUX to peg END.] Call TOWER(N-1,AUX,BEG,END). 5. Return.

CODE:#include<stdio.h> #include void main() { int n; char indl, sndl,dndl; sndl=’a’;indl=’b’;dndl=’c’; printf(“Enter the no.of discs”); sacnf(“%d”,&n); hanoii(n,sndl,indl,dndl); getch(); } hanoii(int n, char sndl, char indl, char dndl) { if(n>0) { hanoii(n-1,sndl,dndl,indl); printf(“Move disc %d from %c to %c”, n,sndl,dndl); hanoii(n-1,indl,sndl,dndl); } } Input:-enter the no. of discs: 3 ( POLES are A B C) Output:-move top disc from A to C move top disc from A to B move top disc from C to B move top disc from A to C move top disc from B to A move top disc from B to C move top disc from A to C

11

PROGRAMS ON QUEUES PROBLEM 105:- Write a program to implement Queue using arrays. PROCEDURE:1.QUEUEINSERT(QUEUE,N,FRONT,REAR,ITEM) (This procedure inserts an element ITEM into a queue a) [queue already filled] if FRONT=0 and REAR=N-1 then: print “Overflow” return b) else set REAR=REAR+1 and queue[REAR]=ITEM 2.QUEUEDELETE(QUEUE,N,FRONT,REAR,ITEM) (This procedure inserts an element ITEM into a queue b) [queue already filled] if FRONT=0 and REAR=-1 then: print “UNDERFLOW” return b) else set FRONT=FRONT+1

CODE:#include<stdio.h> #define max 10 void insert(int); int delete(); void display(); int queue[max],front=0, rear=-1; void main() { char ch=’y’; int c,x; while(ch= =’y’) { printf(“1: insert 2: delete 3: display 4: exit\n”); printf(“enter your choice”); scanf(“%d”,&c); switch(c) { case 1: printf(“enter the item to insert”); scanf(“%d”,&x); insert(x); break; case 2: printf(“the item deleted is %d”,delete()); break; case 3: printf(“the contents of the queue are\n”); display(); break;

12

} printf(“do you want to continue (y/n)”); ch=getchar(); } } void insert(int x) { if(rear= = max-1) { printf(“queue is full”); exit(); } queue[++rear]=x; } int delete() { if (front= =0 && rear= = -1) { printf(“queue is empty”); exit(); } return(queue[front--]); } void display() { int i; if(front= =0 && rear= =-1) { printf(“queue is empty”); exit(); } else { for(i=front;i<=rear;i++) printf(“%3d”,queue[i]); } }

13

PROBLEM 106: Write a program to implement a circular queue using arrays. PROCEDURE:1.CQUEUEINSERT(QUEUE,N,FRONT,REAR,ITEM) (This procedure inserts an element ITEM into a queue a) [queue already filled] if FRONT=1 and REAR=N-1 or if FRONT = REAR+1 then: print “Overflow” return b) if FRONT=0 then set FRONT=1 and REAR=1 else if REAR=N then set REAR=1 else set REAR=REAR+1 c) set queue[REAR]=ITEM d)return 2.CQUEUEDELETE(QUEUE,N,FRONT,REAR,ITEM) (This procedure inserts an element ITEM into a queue a)[queue already filled] if FRONT=0 then: print “UNDERFLOW” return b) set ITEM=queue[FRONT] c) if FRONT=REAR then set FRONT=0 and REAR=0 d) else if FRONT=N then FRONT=1 e) else set FRONT=FRONT+1 f)return

CODE:#include<stdio.h> #define max 10 void insert(int); int delete(); void display(); int cqueue[max],front=0, rear=-1; void main() { char ch=’y’; int c,x; while(ch= =’y’) { printf(“1: insert 2: delete 3: display 4: exit\n”); printf(“enter your choice”); scanf(“%d”,&c); switch(c) { case 1: printf(“enter the item to insert”);

14

scanf(“%d”,&x); insert(x); break; case 2: printf(“the item deleted is %d”,delete()); break; case 3: printf(“the contents of the queue are\n”); display(); break; } printf(“do you want to continue (y/n)”); ch=getchar(); } } void insert(int x) { if if ((front= =0 &&rear= = max-1) | | ((front= = rear+1)&&(front!=0&&rear!=-1))) { printf(“circular queue is full”); exit(); } else { rear=(rear+1)%max; cqueue[rear]=x; } } int delete() { if (front= =0 && rear= = -1) { printf(“queue is empty”); exit(); } else if (front= = rear) { x=front; front=0; rear =-1; } else {

15

x=front; front=(front+1)%max; } return(cqueue[x]); } void display() { int i; if(front= =0 && rear= =-1) { printf(“queue is empty”); exit(); } else if (front=rear) { for(i=front;i<=max-1;i++) printf(“%3d”,cqueue[i]); front(i=0;i
16

PROBLEM 107:- Write a program to implement a dequeue using arrays PROCEDURE:1.INSERTFRONT(ITEM,DQUEUE,N,FRONT,REAR) ITEM to be inserted, DQUEUE array to store elements,N max. size of array a) if FRONT=0 or if FRONT=0 and REAR=N-1 print “OVERFLOW” return b) decrement FRONT by1 and DQUEUE[FRONT]=ITEM 2.INSERTREAR(ITEM,DQUEUE,N,FRONT,REAR) ITEM to be inserted, DQUEUE array to store elements,N max. size of array a) if FRONT=0 and REAR=N-1 print “OVERFLOW” return b) increment REAR by1 and DQUEUE[REAR]=ITEM 3.DELETEFRONT(ITEM,DQUEUE,N,FRONT,REAR) ITEM to be deleted, DQUEUE array to store elements,N max. size of array a) if REAR =-1 print “UNDERFLOW” return b) if FRONT= REAR then reset FRONT=0 AND REAR=-1 c) else increment FRONT by1 4.DELETEREAR(ITEM,DQUEUE,N,FRONT,REAR) ITEM to be deleted, DQUEUE array to store elements,N max. size of array a) if REAR =-1 print “UNDERFLOW” return b) if FRONT= REAR then reset FRONT=0 AND REAR=-1 c)else decrement REAR by1

CODE:#include<stdio.h> #include # define max 4 int r=-1,f=0,u,r; char dq[max]; void insertf(char c) { if(f==0 || (f==0 && r==max-1)) { printf(“Insertion not possible from f”); getch(); } else { dq[--f]=c; } } char dltf() { if(r= =-1) {

17

u=1; printf(“deletion not possible from f”); } else if(f==r) { t=f; f=0; r=-1; return(dq[t]); } else return(dq[f++) } void insertr(char c) { if(r= =max-1 && f= =0) { printf(“insertion not possible form r”); getch(); } else dq[++r] =c; } char dltr() { if(r==-1 { u=-1; printf(“deletion not possible r”); } else if (r==f) { t=r; r=-2; f=0; return(dq[t]); } else return(dq[r--]); } main() { int i, n; char c; do { clrscr(); printf(“\n 1: Insert front\n”); printf(“ 2: Insert Rear \n”); printf(“ 3: Delete Front \n”); printf(“ 4: Delete Rear \n”); printf(“ 5: Display \n”); printf(“ 6: Quit \n”);

18

printf(“ Enter choice \n”); scanf(“%d”,&n); switch(n) { case 1: printf(“Enter Item to be inserted”); flushall(); c=getchar(); insertf(c); break; case 2: printf(“Enter item to be inserted”); flushall(); c=getchar(); insertr©; break; case 3: c=dltf(); if(u!=1) printf(“deleted %c”,c); getch(); u=0; reak; case 4: c=dltr(); if(u!=1) printf(“deleted %c”,c); getch(); u=0; break; case 5: for (i=f;i<=r;i++) printf(“%c”,dq[i]); getch(); } }while(n!=6); }

19

PROGRAMS ON LINKED LISTS PROBLEM 108:- Write a program to implement singly linked list PROCEDURE:1.CREATE() a) set FIRSTNODE to NULL and TEMPNODE to FIRSTNODE b) create NEWNODE if FIRSTNODE=NULL then FIRSTNODE=NEWNODE and TEMPNODE=NEWNODE c) else set LINK[TEMPNODE]=NEWNODE d) set TEMPNODE=NEWNODE e) to create another node goto step b f) set LINK[NEWNODE]=NULL 2. INSERTBEG() a) create a NEWNODE b) set LINK[NEWNODE]=FIRST c) FIRST=NEWNODE 3. INSERTEND() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the last node using TEMP=LINK[TEMP] d) set LINK[TEMP]=NEWNODE 4. INSERTPOS() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the position required using TEMP=LINK[TEMP] d) set LINK[NEWNODE]=LINK[TEMP], and set LINK[TEMP]=NEWNODE 5. DELETEBEG() a) FIRST= LINK[FIRST] 3. DELETEEND() a) set TEMP=FIRST b) traverse till the last but one node using TEMP=LINK[TEMP] c) set LINK[TEMP]=NULL 4. DELETEPOS() a) set TEMP=FIRST b) traverse till the position required using TEMP=LINK[TEMP] d) set TEMP=LINK[LINK[TEMP]]

CODE:#include<stdio.h> #include struct sll {

20

int data; struct ll *link; }; typedef struct sll node; node *first=NULL,*new; void create(), insertbeg(), insertmid(), insertend(); void delbeg(), delmid(),delend(); void display(); void main() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: create 2: insert 3: delete 4: display 5: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: create(); break; case 2: insert(); break; case 3: delete(); break; case 4: display(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void create() { node *temp; char ch=’y’; temp=first; do { printf(“enter the data for the new node\n”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); if(first= =NULL) { first=new;

21

temp=new; new->link=NULL; } else { temp->link=new; new->link=NULL; temp=new; } printf(“do you want to create another node(y/n)”); ch=getchar(); }while(ch!=’n’); } void insert() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: insertbeg 2: insertmid 3: insertend 4: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: insertbeg(); break; case 2: insertmid(); break; case 3: insertend(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void insertbeg() { printf(“ enter data for node to be added in the beginning”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); if(first= = NULL) {first =new; new->link=NULL; }

22

else { new->link=first; first=new; } } void insertmid() { int pos,i=1; node *temp; temp=first; printf(“enter the position to insert a node”); scanf(“%d”,&pos); printf(“ enter data for node to be added at the position %d”,pos); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); while(i<pos) { temp=temp->link; i++; } new->link=temp->link; temp->link=new; } } void insertend() { node *temp; temp=first; printf(“ enter data for node to be added at end”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); while(temp->link!=NULL) { temp=temp->link; } temp->link=new; new->link=NULL; } void delete() { char ch=’y’; int c;

23

while(ch= = ‘y’) { printf(“ 1: delbeg 2: delmid 3: delend 4: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: delbeg(); break; case 2: delmid(); break; case 3: delend(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void delbeg() { if(first= = NULL) {printf(deletion not possible “); exit(); } else { first=first->link; } } void delmid() { int pos,i=1; node *temp; temp=first; printf(“enter the position to delete a node”); scanf(“%d”,&pos); while(i<pos) { temp=temp->link; i++; } temp->link=temp->link->link; }

24

void delend() { node *temp; temp=first; while(temp->link->link!=NULL) { temp=temp->link; } temp->link=NULL; } void display() { node * temp; if (first= =NULL) { printf(“linked list is empty”); exit(); } else { printf(“the contents of single linked list are :\n”); temp=first; while(temp!=NULL) { printf(“%3d”,temp->data); temp=temp->link; } }

25

PROBLEM 109:- Write a program to implement push and pop operations in a stack using linked list. PROCEDURE:1.CREATE() a) set FIRSTNODE to NULL and TEMPNODE to FIRSTNODE b) create NEWNODE if FIRSTNODE=NULL then FIRSTNODE=NEWNODE and TEMPNODE=NEWNODE c) else set LINK[NEWNODE]=FIRST d) FIRST=NEWNODE 2. PUSH() a) create a NEWNODE b) set LINK[NEWNODE]=FIRST c) FIRST=NEWNODE 3. POP() a) FIRST= LINK[FIRST]

CODE:#include<stdio.h> struct node { int qyt; struct node *next; }; void main() { struct node *start; int stop; char k; struct node *push(void); struct node *pop(void); void display(void); printf(“stack using single linked list”); start=NULL; stop=0; do { printf(“ push : P pop: O exit: E”); printf(“enter choice”); do k=getchar(); while(strchr(“PpOoEe”,k)= = NULL); switch(k) { case ‘P’: case ‘p’: start=push(start); printf(“STACK”);

26

display(start); break; case ‘O’: case ‘o’ : start=pop(start); printf(“STACK”); display(start); break; case ‘E’: case ‘e’: stop=1; } }while(!stop); } void display(struct node *record) { printf(“ROOT”); while(record!=NULL) { printf(“%d”,&record->qty); record=record->next; } return(); } struct node *push(struct node *first) { struct node * newnode; int newele; printf(“enter value to be pushed”); scanf(“%d”,&newele); new_node=(struct node *)malloc(sizeof(struct node)); new_node->element=new_element; new_node->next=first; first=new_node; return(first); } struct node *pop(struct node *first) { struct node *temp; int element; if(first= =NULL) printf(“empty”); else {

27

printf(“popped element =%d”,first->element); temp=first->next; free(first); first=temp; if(first= =NULL) printf(“empty”); } return(first); }

28

PROBLEM 110:- Write a program to implement queue operations using linked list. PROCEDURE:1.ADDREAR(ITEM) traverse till the end and always add data at the end 2.DELETEFRON(ITEM) always delete elements from front end only

CODE:#include<stdio.h> struct queue { struct node *front, *rear; }*q; struct node { int data; struct node *next; }; void insert(struct queue *q,int x) { struct node *new; new=(struct node *)malloc(sizeof(struct node)); new->data=x; new->next=NULL; if(q->rear= =NULL) q->front=new; q->rear=new; else q->rear->next=new; q->rear=new; } int delete(struct queue *q) { int x; struct node *new; new=(struct node*)malloc(sizeof(struct node)); if(q->front = =NULL) printf(“underflow”); new=q->front; x=new->data;

29

q->front=q->front->next; } } void main() { int x, ch; printf(“1:insert 2: delete 3:display 4:exit”); printf(“enter choice”); scanf(“%d”,&ch); while(ch!=4) { switch(ch) { case 1: printf(“enter the number to be inserted”); scanf(“%d”,&x); insert(q,x); break; case 2: x=delete(q); printf(“element deleted is %d”,x); break; case 3: display(); break; case 4: exit(0); } printf(“1:insert 2: delete 3:display 4:exit”); printf(“enter choice”); scanf(“%d”,&ch); } getch(); }

30

PROBLEM 111:- Linked list Concatenation PROCEDURE:1. create two linked lists L1 and L2 2. traverse till the last node in first list L1 3. set LINK field of that node to L2

CODE:#include<stdio.h> #include struct node { int info; struct node *l; }*fl=NULL,*s1,*s,*f,*n,*t,*t1; struct node create() { char c= ‘y’ f=NULL; while(c= =’y’) { n=(struct node *)malloc(sizeof(struct node)); printf(“Enter the data”); scanf(“%d”,&n->info); if(f= =NULL) { f=n;t=f; } else { t->l=n; t=n; } n->l=NULL; printf(“continue(y/n”); flushall(); c=getchar(); } return(f) } Void Display(struct node f) { Printf(“ist LL”); For(t=f;t!=NULL;t=t->l) Printf(“%d”,t->info); Printf(“\n 2nd LL”); For(t=f1;t!=NULL;t=t->l) Printf(“%d”,t->info);

31

} struct node concat(struct node f,struct node t) { t1=f; while(t1->l!=NULL) { t1=t1->l; } t1->l=t ; return(f) ; } void main() { int n; clrscr(); do{ printf(“1: create\n 2: concat\n 3: Display 4.quit\n Enter choice”); scanf(%d”,&n); switch(n) { case 1: f=create(); t=create(); break; case 2: f1=concat(f,t); break; case 3: display(f1); break: } }while(n!=4); }

32

PROBLEM 112:- Merging of two linked lists PROCEDURE:1. 2. 3. 4. 5. 6.

create two linked lists L1 and L2 starting with first node in L1 ,set link of first node to first node in L2 called next set next node in L1 as current first node , set current next node in L2 as next repeat steps 2 and 3 till either of L1 or L2 becomes NULL If L1=NULL add L2 ‘s remaining nodes at end of the merged list if L2=NULL add L1’s remaining nodes at end of the merged list

CODE:#include<stdio.h> #include struct node { int info; struct node *l; }*fl=NULL,*s1,*s,*f,*n,*t,*t1; struct node create() { char c= ‘y’ f=NULL; while(c= =’y’) { n=(struct node *)malloc(sizeof(struct node)); printf(“Enter the data”); scanf(“%d”,&n->info); if(f= =NULL) { f=n;t=f; } else { t->l=n; t=n; } n->l=NULL; printf(“continue(y/n”); flushall(); c=getchar(); } return(f) } Void Display(struct node f) { Printf(“ist LL”); For(t=f;t!=NULL;t=t->l) Printf(“%d”,t->info); Printf(“\n 2nd LL”);

33

For(t=f1;t!=NULL;t=t->l) Printf(“%d”,t->info); } struct node merge(struct node t,struct node f1) { t=f; while(t->l!=NULL && f1->l;!=NULL) { s=t->l; n=f1->l; f1->l=t->l; t->l=f1; t=s; f1=n; } if(t->l= =NULL) t->l=f1->l; if(f1->l= =NULL) f1->l=t } return(t); } void main() { int n; clrscr(); do{ printf(“1: create\n 2: merge\n 3: Display 4.quit\n Enter choice”); scanf(%d”,&n); switch(n) { case 1: f=create(); t=create(); break; case 2: f1=merge(f,t); break; case 3: display(f1); break: } }while(n!=4); }

34

PROBLEM 113:- Spliting of linked list PROCEDURE:1. 2. 3. 4. 5.

create a one list L1 Find the no. of nodes to be in first list n set temp to first node traverse till the n’th node is reached set link field of that node as L2 set link field of n’th node as NULL

CODE:#include<stdio.h> #include struct node { int info; struct node *l; }*fl=NULL,*s1,*s,*f,*n,*t,*t1; struct node create() { char c= ‘y’ f=NULL; while(c= =’y’) { n=(struct node *)malloc(sizeof(struct node)); printf(“Enter the data”); scanf(“%d”,&n->info); if(f= =NULL) { f=n;t=f; } else { t->l=n; t=n; } n->l=NULL; printf(“continue(y/n”); flushall(); c=getchar(); } return(f) } void split(struct node f) { int i=1,n; printf(“Enter the position”); scanf(%d”,&n); t=f; while(i
35

t=t->l; i++; } f1=t->l; t->l=NULL; printf(“SLL splited”); display(t); display(f1); } Void Display(struct node f) { Printf(“ LL is”); For(t=f;t!=NULL;t=t->l) Printf(“%d”,t->info); } void main() { int n; clrscr(); do{ printf(“1: create\n 2: split\n 3.quit\n Enter choice”); scanf(%d”,&n); switch(n) { case 1: f=create(); break; case 2: split(f); break; } }while(n!=3); }

36

PROBLEM 114:- Reversing a linked list PROCEDURE:1. create a linked list f 2. set f1=f; set s=NULL; 3. repeat step 4 while(f1!=NULL) 4. set t=LINK[f1]; set link[f1]=s; set s=f1; set f1=t; 5. set f=s

CODE:#include<stdio.h> #include struct node { int info; struct node *l; }*fl=NULL,*s1,*s,*f,*n,*t,*t1; struct node create() { char c= ‘y’ f=NULL; while(c= =’y’) { n=(struct node *)malloc(sizeof(struct node)); printf(“Enter the data”); scanf(“%d”,&n->info); if(f= =NULL) { f=n;t=f; } else { t->l=n; t=n; } n->l=NULL; printf(“continue(y/n”); flushall(); c=getchar(); } return(f) } struct node rev() { f1=f; s=NULL; while(f1!=NULL) { t=f1->l; f1->l=s;

37

s=f1; f1=t; } f=s; return(f); } Void Display(struct node f) { Printf(“ LL is”); For(t=f;t!=NULL;t=t->l) Printf(“%d”,t->info); } void main() { int n; clrscr(); do{ printf(“1: create\n 2: split\n 3.quit\n Enter choice”); scanf(%d”,&n); switch(n) { case 1: f=create(); break; case 2: f=rev(); break; case 3: display(f) } }while(n!=4); }

38

PROBLEM 115:- Write a program to add two polynomials using linked representation PROCEDURE:1.enter two polynomials in terms of two linked lists P1 P2 2. repeat steps 3 to 5 while P1!=NULL 3. take power field of the node and start comparing with power fields in P2 until P2!=NULL 4.if power fields are equal find sum of corresponding coeffiecients and place the result in third linked list 5. set P1=LINK[P1]

CODE:Struct poly { int coeff,power; struct poly *link; }*p1,*p2,*p3,*prev,*temp,*first; void create(int n) { int i=1; first=(struct poly*)malloc(sizeod(struct poly)); printf(“\n Enter coeff & power:”); scanf(“%d%d”,&first->coeff,&first->pow); first->link-NULL; prev=first; p1=first; while(icoeff,&temp->pow); prev->link=temp; prev=prev->link; i++; } prev->link=NULL; } main() { int n1,n2,x; printf(“Enter no. of item of poly 1:”); scanf(“%d”,&n1); printf(“Enter no. of item of poly 2:”); scanf(“%d”,&n2); crete(p1);

39

p1=first; create(p2); temp=(struct poly *)malloc(sizeod(struct poly)); p3=temp; prev=temp; while(p1!=NULL && p2!=NULL) { temp=(struct poly *)malloc(sizeof(struct poly)); if(p1->pow > p2->pow) { temp->pow=p1->pow; temp->coeff = p1->coeff; p1=p1->link; } else if (p2->pow > p1->pow) { temp->pow – p2->pow; temp->coef = p2->coef;p2=p2->link; } else { x=p1->coeff+p2->coeff; if(x!=0) { temp->ceoff=x; temp->pow=p1->pow; } p1=p1->link; p2=p2->link; } prev->link=temp; prev=prev->link; } if(p1!=NULL) { while(p1!=NULL) { temp-struct poly *)malloc(sizeof(sturct poly)); temp->coef=p1->coef; temp->pow=p1->pow; p1=p1->link; prev->link=temp; prev->link; prev=prev->link; } }

40

else if(p2!=NULL) { while(p2!=NULL) { temp=struct poly *)malloc(sizeof(struct poly)); temp->coef=p2->coef; temp->pow=p2->pow; p2=p2->link; prev->link=temp; prev=prev->link; } } prev->link-NULL; temp=p3; p3=p3->link; free(temp); temp=p3; printf(“:poly after addition is \n”); while(temp!-NULL) { printf(“%3d * %d”,temp->coeff,temp->pow); temp=temp->link; } getch(); }

41

PROBLEM 116:- Write a program to implement a circular single linked list PROCEDURE:1.CREATE() a) set FIRSTNODE to NULL and TEMPNODE to FIRSTNODE b) create NEWNODE if FIRSTNODE=NULL then FIRSTNODE=NEWNODE and TEMPNODE=NEWNODE c) else set LINK[TEMPNODE]=NEWNODE d) set TEMPNODE=NEWNODE e) to create another node goto step b f) set LINK[NEWNODE]=FIRST 2. INSERTBEG() a) create a NEWNODE b) set TEMP=FIRST traverse till the last node set LINK[TEMP]=NEWNODE c) set LINK[NEWNODE]=FIRST, set FIRST=NEWNODE 3. INSERTEND() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the last node’s link field is not equal FIRST using TEMP=LINK[TEMP] d) set LINK[TEMP]=NEWNODE and LINK[NEWNODE]=FIRST 4. INSERTPOS() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the position required using TEMP=LINK[TEMP] d) set LINK[NEWNODE]=LINK[TEMP], and set LINK[TEMP]=NEWNODE 5. DELETEBEG() a) Set TEMP=FIRST traverse until the last node’s link field is not equal to FIRST and set TEMP= LINK[FIRST] and FIRST=LINK[FIRST] 3. DELETEEND() a) set TEMP=FIRST b) traverse till the last but one node using TEMP=LINK[TEMP] c) set LINK[TEMP]=FIRST 4. DELETEPOS() a) set TEMP=FIRST b) traverse till the position required using TEMP=LINK[TEMP] d) set TEMP=LINK[LINK[TEMP]]

CODE:#include<stdio.h> #include struct csll { int data; struct csll *link; }; typedef struct csll node;

42

node *first=NULL,*new; void create(), insertbeg(), insertmid(), insertend(); void delbeg(), delmid(),delend(); void display(); void main() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: create 2: insert 3: delete 4: display 5: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: create(); break; case 2: insert(); break; case 3: delete(); break; case 4: display(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void create() { node *temp; char ch=’y’; temp=first; do { printf(“enter the data for the new node\n”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); if(first= =NULL) { first=new; temp=new; new->link=first; } else

43

{ temp->link=new; new->link=first; temp=new; } printf(“do you want to create another node(y/n)”); ch=getchar(); }while(ch!=’n’); } void insert() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: insertbeg 2: insertmid 3: insertend 4: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: insertbeg(); break; case 2: insertmid(); break; case 3: insertend(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void insertbeg() { node *temp; printf(“ enter data for node to be added in the beginning”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); if(first= = NULL) {first =new; new->link=first; } else { temp=first;

44

while(temp->link!=first) temp=temp->link; temp->link=new; new->link=first; first=new; } } void insertmid() { int pos,i=1; node *temp; temp=first; printf(“enter the position to insert a node”); scanf(“%d”,&pos); printf(“ enter data for node to be added at the position %d”,pos); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); while(i<pos) { temp=temp->link; i++; } new->link=temp->link; temp->link=new; } } void insertend() { node *temp; temp=first; printf(“ enter data for node to be added at end”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); while(temp->link!=first) { temp=temp->link; } temp->link=new; new->link=first; } void delete() { char ch=’y’;

45

int c; while(ch= = ‘y’) { printf(“ 1: delbeg 2: delmid 3: delend 4: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: delbeg(); break; case 2: delmid(); break; case 3: delend(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void delbeg() { node *temp; if(first= = NULL) {printf(deletion not possible “); exit(); } else { temp=first; while(temp->link!=first) temp=temp->link; temp->link=first->link; first=first->link; } } void delmid() { int pos,i=1; node *temp; temp=first; printf(“enter the position to delete a node”); scanf(“%d”,&pos); while(i<pos) {

46

temp=temp->link; i++; } temp->link=temp->link->link; } void delend() { node *temp; temp=first; while(temp->link->link==first) { temp=temp->link; } temp->link=first; } void display() { node * temp; if (first= =NULL) { printf(“linked list is empty”); exit(); } else { printf(“the contents of circularly single linked list are :\n”); temp=first; do { printf(“%3d”,temp->data); temp=temp->link; }while(temp!=first); }

47

PROBLEM 117:- Write a program to implement a doubly linked list. PROCEDURE:1.CREATE() a) set FIRSTNODE to NULL and TEMPNODE to FIRSTNODE b) create NEWNODE if FIRSTNODE=NULL then FIRSTNODE=NEWNODE and TEMPNODE=NEWNODE and LLINK[NEWNODE]=NULL c) else set RLINK[TEMPNODE]=NEWNODE and LLINK[NEWNODE]=TEMPNODE d) set TEMPNODE=NEWNODE e) to create another node goto step b f) set RLINK[NEWNODE]=NULL 2. INSERTBEG() a) create a NEWNODE b) set RLINK[NEWNODE]=FIRST and LLINK[NEWNODE]=NULL c) FIRST=NEWNODE 3. INSERTEND() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the last node using TEMP=RLINK[TEMP] d) set RLINK[TEMP]=NEWNODE and LLINK[NEWNODE]=TEMP and RLINK[NEWNODE]=NULL 4. INSERTPOS() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the position required using TEMP=RLINK[TEMP] d) set LLINK[ RLINK [TEMP]=NEWNODE set RLINK[NEWNODE]=RLINK[TEMP] set RLINK[TEMP]=NEWNODE; set LLINK[NEWNODE]=TEMP 5. DELETEBEG() a) FIRST= RLINK[FIRST] b)LLINK[FIRST]=NULL 3. DELETEEND() a) set TEMP=FIRST b) traverse till the last but one node using TEMP=RLINK[TEMP] c) set RLINK[TEMP]=NULL 4. DELETEPOS() a) set TEMP=FIRST b) traverse till the position required using TEMP=LINK[TEMP] c) set LLINK[RLINK[RLINK[TEMP]=TEMP set RLINK[TEMP]=RLINK[RLINK[TEMP]]

CODE:#include<stdio.h> #include struct dll

48

{ struct dll *llink int data; struct dll *rlink; }; typedef struct dll node; node *first=NULL,*new; void create(), insertbeg(), insertmid(), insertend(); void delbeg(), delmid(),delend(); void display(); void main() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: create 2: insert 3: delete 4: display 5: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: create(); break; case 2: insert(); break; case 3: delete(); break; case 4: display(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void create() { node *temp; char ch=’y’; temp=first; do { printf(“enter the data for the new node\n”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); if(first= =NULL)

49

{ first=new; temp=new; new->llink=NULL; new->rlink=NULL; } else { temp->rlink=new; new->llink=temp; new->rlink=NULL; temp=new; } printf(“do you want to create another node(y/n)”); ch=getchar(); }while(ch!=’n’); } void insert() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: insertbeg 2: insertmid 3: insertend 4: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: insertbeg(); break; case 2: insertmid(); break; case 3: insertend(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void insertbeg() { printf(“ enter data for node to be added in the beginning”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data);

50

if(first= = NULL) {first =new; new->llink=NULL; new->rlink=NULL; } else { new->rlink=first; first->llink=new; new->llink=NULL; first=new; } } void insertmid() { int pos,i=1; node *temp; temp=first; printf(“enter the position to insert a node”); scanf(“%d”,&pos); printf(“ enter data for node to be added at the position %d”,pos); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); while(i<pos) { temp=temp->rlink; i++; } temp->rlink->llink=new new->rlink=temp->rlink; temp->rlink=new; new->llink=temp; } } void insertend() { node *temp; temp=first; printf(“ enter data for node to be added at end”); new=(node*)malloc(sizeof(node)); scanf(“%d”,&new->data); while(temp->rlink!=NULL) {

51

temp=temp->rlink; } temp->rlink=new; new->llink=temp; new->rlink=NULL; } void delete() { char ch=’y’; int c; while(ch= = ‘y’) { printf(“ 1: delbeg 2: delmid 3: delend 4: exit\n”); printf(“enter your option”); scanf(“%d”,&c); switch(c ) { case 1: delbeg(); break; case 2: delmid(); break; case 3: delend(); } printf(“do you want to continue(y/n)”); ch=getchar(); } } void delbeg() { node *temp; if(first= = NULL) {printf(deletion not possible “); exit(); } else { first=first->rlink; first->llink=NULL; } } void delmid() {

52

int pos,i=1; node *temp; temp=first; printf(“enter the position to delete a node”); scanf(“%d”,&pos); while(i<pos) { temp=temp->rlink; i++; } temp->rlink->rlink->llink=temp; temp->rlink=temp->rlink->rlink; } void delend() { node *temp; temp=first; while(temp->rlink->rlink!=NULL) { temp=temp->rlink; } temp->rlink->llink=NULL; temp->rlink=NULL; } void display() { node * temp; if (first= =NULL) { printf(“linked list is empty”); exit(); } else { printf(“the contents of doubly linked list are :\n”); temp=first; while(temp->rlink!=NULL) { printf(“%3d”,temp->data); temp=temp->rlink; } }

53

PROBLEM 118: Implement circular doubly linked list PROCEDURE:1.CREATE() a) set FIRSTNODE to NULL and TEMPNODE to FIRSTNODE b) create NEWNODE if FIRSTNODE=NULL then FIRSTNODE=NEWNODE and TEMPNODE=NEWNODE and LLINK[NEWNODE]=FIRST and RLINK[FIRST]=FIRST c) else set RLINK[TEMPNODE]=NEWNODE and LLINK[NEWNODE]=TEMPNODE d) set TEMPNODE=NEWNODE e) to create another node goto step b f) set RLINK[NEWNODE]=FIRST 2. INSERTBEG() a) create a NEWNODE b) set TEMP=FIRST traverse till the end of list using TEMP=RLINK[TEMP] set RLINK[NEWNODE]=FIRST and LLINK[NEWNODE]=TEMP, RLINK[TEMP]=NEWNODE c) FIRST=NEWNODE 3. INSERTEND() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the last node using TEMP=RLINK[TEMP] d) set RLINK[TEMP]=NEWNODE and LLINK[NEWNODE]=TEMP and RLINK[NEWNODE]=FIRST 4. INSERTPOS() a) create a NEWNODE b) set TEMP=FIRST c) traverse till the position required using TEMP=RLINK[TEMP] d) set LLINK[ RLINK [TEMP]=NEWNODE set RLINK[NEWNODE]=RLINK[TEMP] set RLINK[TEMP]=NEWNODE; set LLINK[NEWNODE]=TEMP 5. DELETEBEG() a) set TEMP=FIRST traverse till the last node using TEMP=RLINK[TEMP] set RLINK[TEMP]=RLINK[FIRST] set FIRST=RLINK[FIRST] b)LLINK[FIRST]=FIRST 6. DELETEEND() a) set TEMP=FIRST b) traverse till the last but one node using TEMP=RLINK[TEMP] c) set RLINK[TEMP]=FIRST, set LLINK[FIRST]=TEMP 7. DELETEPOS() a) set TEMP=FIRST b) traverse till the position required using TEMP=LINK[TEMP] c) set LLINK[RLINK[RLINK[TEMP]=TEMP set RLINK[TEMP]=RLINK[RLINK[TEMP]]

54

CODE:#include<stdio.h> struct abc { int a; struct abc *p; }; typedef struct abc node; node *f=NULL,*t,*n; void main() { int c; void add(),addbeg(),addany(),del(),delbeg(),delany(); void display(); do { clrscr(); printf(“1) add node \n 2) add node at beginning \n 3) add node at desired position\n 4) delete node\n 5) delete node at beginning\n 6)delete node at desired position\n 7) display\n 8) exit\n”); scanf(“%d”,&i); switch© { case 1:add(); break; case 2:addbeg(); break; case 3:addany(); break; case 4:del(); break; case 5:delbeg(); break; case 6:delany(); break; case 7:display(); break; } }while(c!=8); } vios add() { if(f==NULL)

55

{ f=(node *)malloc(sizeof(node)); printf(“enter value:”); scanf(“%d”,&f->a); f->lp=->lp=f; } else { n=(node *)malloc(sizeof(node)); printf(“Enter value:”); scanf(“%d”,&n->a); n->rp=f; for(t=f;t->rp!=f;t=t->rp); t->rp=n; n->lp=t; f->lp=n; } } void addbeg() { n=(node *)malloc(sizeof(node)); printf(“Enter number:”); scanf(“%d”,&n->a); n->rp=f; for(t=f;t->rp=f;t=t->rp); t->rp=n; n->lp=t; f=n; f->lp=n; } void addany() { int x.i; printf(“Enter position”); scanf(“%d”,&x); n=(node *)malloc(sizeof(node)); printf(“Enter number”); scanf(%d”,&n->a); for(i=1,t=f;i<x-1;i++,t=t->rp); n->rp=t->rp; n->lp=t; t->rp->lp=n; t->rp=n; }

56

void del() { for(t=f;t->rp->rp!=f;t=t->rp); n=t->rp); t->rp=f; f->lp=t; } void delbeg() { n=f; for(t=f;t->rp!=f;t=t->rp); f=f->rp; t->rp=f; f->lp=t; free(n); } void delany() { int I,x; printf(“Enter position; scanf(“%d”,&x); for(i=1,t=f;i<x-1;i++,t=t->rp); n=t->rp; t->rp=t->rp->lp; t->rp->lp=t; free(n); } void display() { t=f; do { printf(“%d”,t->a); t=t->rp; } while(t!=f); getvh(); }

57

PROBLEM 119:- Implement Polynomial subtraction using singly linked list PROCEDURE:1.enter two polynomials in terms of two linked lists P1 P2 2. repeat steps 3 to 5 while P1!=NULL 3. take power field of the node and start comparing with power fields in P2 until P2!=NULL 4.if power fields are equal find difference of corresponding coeffiecients and place the result in third linked list 5. set P1=LINK[P1]

CODE:Struct poly { int coeff,power; struct poly *link; }*p1,*p2,*p3,*prev,*temp,*first; void create(int n) { int i=1; first=(struct poly*)malloc(sizeod(struct poly)); printf(“\n Enter coeff & power:”); scanf(“%d%d”,&first->coeff,&first->pow); first->link-NULL; prev=first; p1=first; while(icoeff,&temp->pow); prev->link=temp; prev=prev->link; i++; } prev->link=NULL; } main() { int n1,n2,x; printf(“Enter no. of item of poly 1:”); scanf(“%d”,&n1); printf(“Enter no. of item of poly 2:”); scanf(“%d”,&n2); crete(p1); p1=first;

58

create(p2); temp=(struct poly *)malloc(sizeod(struct poly)); p3=temp; prev=temp; while(p1!=NULL && p2!=NULL) { temp=(struct poly *)malloc(sizeof(struct poly)); if(p1->pow > p2->pow) { temp->pow=p1->pow; temp->coeff = p1->coeff; p1=p1->link; } else if (p2->pow > p1->pow) { temp->pow – p2->pow; temp->coef = p2->coef;p2=p2->link; } else { x=p1->coeff-p2->coeff; if(x!=0) { temp->ceoff=x; temp->pow=p1->pow; } p1=p1->link; p2=p2->link; } prev->link=temp; prev=prev->link; } if(p1!=NULL) { while(p1!=NULL) { temp-struct poly *)malloc(sizeof(sturct poly)); temp->coef=p1->coef; temp->pow=p1->pow; p1=p1->link; prev->link=temp; prev->link; prev=prev->link; } } else if(p2!=NULL)

59

{ while(p2!=NULL) { temp=struct poly *)malloc(sizeof(struct poly)); temp->coef=p2->coef; temp->pow=p2->pow; p2=p2->link; prev->link=temp; prev=prev->link; } } prev->link-NULL; temp=p3; p3=p3->link; free(temp); temp=p3; printf(“:poly after subtraction is \n”); while(temp!-NULL) { printf(“%3d * %d”,temp->coeff,temp->pow); temp=temp->link; } getch(); }

60

PROGRAMS ON TREES & GRAPHS PROBLEM 120:- Write a program to create and traverse a binary tree in a) Preorder. b) Inorder. c) Postorder. PROCEDURE for Preorder Traversal:PREORD(INFO, LEFT, RIGHT, ROOT) A binary tree T is in memory. This procedure does a preorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Initially push NULL onto STACK, and initialize PTR.] Set TOP:=1, STACK[1]:=NULL and PTR:=ROOT. 2. Repeat steps 3 to 5 while PTR ≠ NULL: 3. Apply PROCESS to INFO[PTR]. 4. [Right child?] If RIGHT[PTR] ≠ NULL, then: [Push on STACK.] Set TOP:= TOP+1, and STACK[TOP]:=RIGHT[PTR]. [End of If structure] 5. [Left child?] If LEFT[PTR] ≠ NULL, then: Set PTR:=LEFT[PTR]. Else: [Popfrom STACK.] Set PTR:=STACK[TOP] and TOP:=TOP-1. [End of If structure.] [End of stop2 loop.] 6. Exit.

PROCEDURE for Inorder Traversal:INORD(INFO,LEFT,RIGHT,ROOT) A binary tree T is in memory. This procedure does an inorder traversal of T applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Push NULL onto STACK and initialize PTR.] Set TOP:=1, STACK[1]:= NULL and PTR:= ROOT. 2. Repeat while PTR ≠ NULL: [Pushes left-most path onto STACK.] a) Set TOP:= TOP+1 and STACK[TOP:=PTR.[Saves node.] b) Set PTR:= LEFT[PTR], [Updates PTR.] [End of loop.] 3. Set PTR:=STACK[TOP] and TOP:=TOP-1.[Pops node from STACK.]

61

4. Repeat Steps 5 to 7 while PTR ≠ NULL:[Backtracking.] 5. Apply Process to INFO[PTR]. 6. [Right child?] If RIGHT[PTR] ≠ NULL, then: (a) Set PTR:= RIGHT[PTR]. (b) Goto Step 3. [End of If structure.] 7. Set PTR:=STACK[TOP] and TOP:=TOP-1 {Pops node.] [End of Step 4 loop] 8. Exit.

PROCEDURE for Postorder Traversal:POSTORD(INFO,LEFT,RIGHT,ROOT) A binary tree T is in memory. This procedure does a postorder traversal of T applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Push NULL onto STACK and initialize PTR.] Set TOP:=1, STACK[1]:= NULL and PTR:= ROOT. 2 [Push left-most path onto STACK.]. Repeat steps 3 to 5 while PTR ≠ NULL: 3. Set TOP:= TOP+1 and STACK[TOP:=PTR [Pushes PTR on STACK]. 4. If RIGHT[PTR ]≠ NULL then: [Push on STACK] Set TOP:= TOP+1 and STACK[TOP]:= -RIGHT[PTR]. [End of If structure.]. 5. Set PTR: = LEFT[PTR]. [Updates pointer PTR.] [End of step 2 loop.] 6. Set PTR: = STACK[TOP] and TOP: = TOP-1. [Pops node from STACK.] 7. Repeat while PTR>0: (a) Apply PROCESS to INFO[PTR]. (b) Set PTR: = STACK[ TOP] and TOP: = TOP-1. [Pops node from STACK.] [End of loop.] 8. If PTR<0, then: (a) Set PTR: = -PTR. (b) Go to Step 2. [End of If structure.] 9. Exit.

62

CODE:#include<stdio.h> #include struct tree { char data; struct tree *left; struct tree *right; } typedef struct tree btree; btree *root,*stack[100]; int top=0; void rec(); void withoutrec(); void traversal(); void postorder(); void inorder(); void preorder(); void recpostorder(); void recinorder(); void recpreorder(); void push(btree *x) { stack[++top]=x; } btree *pop() { return(stack[top--]); } void create() { btree *p,*temp; char ans; stack[top]=NULL; root=(btree *)malloc(sizeof(btree)); printf(“enter data for root node”); scanf(“%c”,&root->data); p=root; while(p) { printf(“do u want to create a right child for node %c(y/n):”,p->data); scanf(“%c”,&ans); if(toupper(ans)= =’n’) p->right=NULL;

63

else { temp=(btree *)malloc(sizeof(btree)); printf(“enter data for the node”); scanf(“%c”,&temp->data); p->right=temp; push(temp); } printf(“do u want to create a left child for the node %c(y/n):”,p->data); scanf(“%c”,&ans); if(toupper(ans)= =’N’) { p->left=NULL; p=pop(); } else { temp=(btree *)malloc(sizeof(btree)); printf(“enter data for the node”); scanf(“%c”,&temp->data); p->left=temp; p=p->left; } } } int menu() { int c; printf(“MAIN MENU\n”); printf(“1:create btree\n 2: traversal \n 3:exit\n enter ur choice\n”); scanf(“%d”,&c); return( c); } void recinorder(btree *r) { if(r!=NULL) { recinorder(r->left); printf(“%c”,r->data); recinorder(r->right); } } void recpreorder(btree *r) { if(r!=NULL)

64

{ printf(“%c”,r->data); recpreorder(r->left); recpreorder(r->right); } } void recpostorder(btree *r) { if(r!=NULL) { recpostorder(r->left); recpostorder(r->right); printf(“%c”,r->data); } } void preorder() { btree *t; t=root; top=0; stack[top]=NULL; printf(“the preorder form is:\n”); while(t!=NULL) { printf(“%c”,t->data); if(t->right!=NULL) push(t->right); if(t->left!=NULL) t=t->left; else t=pop(); } } void inorder() { btree *t; t=root; printf(“the inorder form is :\n”); top=0; stack[top]=NULL; a: while(t!=NULL) { push(t); t=t->left;

65

} t=pop(); while(t!=NULL) { printf(“%c”,t->data); if(t->right!=NULL) { t=t->right; goto a; } t=pop(); } } void postorder() { btree *p,*temp; printf(“the postorder form\n”); top=0; temp=NULL; p=root; while(p->left!=NULL) { push(p); p=p->left; } while(p!=NULL) { if((p->right = = NULL) || (p->right= =temp)) { printf(“%c”,p->data); temp=p; p=pop(); } else { push(p); p=p->right; while(p->left!=NULL) { push(p); p=p->left; } } } }

66

void main() { int ch,n; top=0; while(1) { ch=menu(); switch(ch) { case 1: create(); break; case 2: traversal(); break; case 3: exit(0; } } } void traversal() { int x; printf(“1: with recursion\n 2: without recursion\n); scanf(“%d”,&x); switch(x) { case 1: rec(); break; case 2: withoutrec(); break; } } void rec() { while(1) { int x; printf(“1: inorder 2: preorder 3: postorder\n enter ur choice”); scanf(“%d”,&x); switch(x) { case 1: recinorder(root); break; case 2: recpreorder(root); break; case 3: recpostorder(root); break; case 4: return; } }

67

} void withoutrec() { while(1) { int x; printf(“1: inorder 2: preorder 3: postorder\n enter ur choice”); scanf(“%d”,&x); switch(x) { case 1: inorder(); break; case 2: preorder(); break; case 3: postorder(); break; case 4: return; } } }

68

PROBLEM 121:- Write a program to create and traverse a binary search tree in a) Preorder. b) Inorder. c) Postorder. d) Counting leaf nodes e) Counting non leaf nodes f) Counting total nodes PROCEDURE for Preorder Traversal:PREORD(INFO, LEFT, RIGHT, ROOT) A binary tree T is in memory. This procedure does a preorder traversal of T, applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Initially push NULL onto STACK, and initialize PTR.] Set TOP:=1, STACK[1]:=NULL and PTR:=ROOT. 10. Repeat steps 3 to 5 while PTR ≠ NULL: 11. Apply PROCESS to INFO[PTR]. 12. [Right child?] If RIGHT[PTR] ≠ NULL, then: [Push on STACK.] Set TOP:= TOP+1, and STACK[TOP]:=RIGHT[PTR]. [End of If structure] 13. [Left child?] If LEFT[PTR] ≠ NULL, then: Set PTR:=LEFT[PTR]. Else: [Popfrom STACK.] Set PTR:=STACK[TOP] and TOP:=TOP-1. [End of If structure.] [End of stop2 loop.] 14. Exit.

PROCEDURE for Inorder Traversal:INORD(INFO,LEFT,RIGHT,ROOT) A binary tree T is in memory. This procedure does an inorder traversal of T applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Push NULL onto STACK and initialize PTR.] Set TOP:=1, STACK[1]:= NULL and PTR:= ROOT. 2. Repeat while PTR ≠ NULL: [Pushes left-most path onto STACK.] a) Set TOP:= TOP+1 and STACK[TOP:=PTR.[Saves node.] b) Set PTR:= LEFT[PTR], [Updates PTR.] [End of loop.]

69

3. Set PTR:=STACK[TOP] and TOP:=TOP-1.[Pops node from STACK.] 4. Repeat Steps 5 to 7 while PTR ≠ NULL:[Backtracking.] 5. Apply Process to INFO[PTR]. 6. [Right child?] If RIGHT[PTR] ≠ NULL, then: (a) Set PTR:= RIGHT[PTR]. (b) Goto Step 3. [End of If structure.] 7. Set PTR:=STACK[TOP] and TOP:=TOP-1 {Pops node.] [End of Step 4 loop] 8. Exit.

PROCEDURE for Postorder Traversal:POSTORD(INFO,LEFT,RIGHT,ROOT) A binary tree T is in memory. This procedure does a postorder traversal of T applying an operation PROCESS to each of its nodes. An array STACK is used to temporarily hold the addresses of nodes. 1. [Push NULL onto STACK and initialize PTR.] Set TOP:=1, STACK[1]:= NULL and PTR:= ROOT. 2 [Push left-most path onto STACK.]. Repeat steps 3 to 5 while PTR ≠ NULL: 3. Set TOP:= TOP+1 and STACK[TOP:=PTR [Pushes PTR on STACK]. 4. If RIGHT[PTR ]≠ NULL then: [Push on STACK] Set TOP:= TOP+1 and STACK[TOP]:= -RIGHT[PTR]. [End of If structure.]. 5. Set PTR: = LEFT[PTR]. [Updates pointer PTR.] [End of step 2 loop.] 6. Set PTR: = STACK[TOP] and TOP: = TOP-1. [Pops node from STACK.] 7. Repeat while PTR>0: i. Apply PROCESS to INFO[PTR]. ii. Set PTR: = STACK[ TOP] and TOP: = TOP-1. [Pops node from STACK.] [End of loop.] 8. If PTR<0, then: i. Set PTR: = -PTR. ii. Go to Step 2. [End of If structure.] 9. Exit.

PROCEDURE TO COUNT NO. OF LEAF NODES:1.While tree traversal if nodes left link and it’s right link are both NULL 2. then increase leaf nodes count by 1

PROCEDURE TO COUNT NO. OF LEAF NODES:1.While tree traversal if nodes left link is NULL and right link is not NULL

70

2. or if left link is not NULL and right link is NULL 3. or if left link is not NULL and as well as right link is not NULL then in 4. all these cases increase the non leaf nodes count by one

PROCEDURE TO COUNT NO. OF NODES:1. no. of nodes=no.of leaf nodes+no.of non leaf nodes

CODE:#include<stdio.h> #include struct tree { char data; struct tree *left; struct tree *right; } typedef struct tree btree; btree *root,*stack[100]; int top=0; btree * insert(int, btree *); void countnode(); void rec(); void withoutrec(); void traversal(); void postorder(); void inorder(); void preorder(); void recpostorder(); void recinorder(); void recpreorder(); void push(btree *x) { stack[++top]=x; } btree *pop() { return(stack[top--]); } btree * insert(int data,btree *p) { if(!p) { p=(btree *)malloc(sizeof(btree)); p->data=data; p->left=NULL; p->right=NULL;

71

return(p); } if(datadata) p->left=insert(data,p->left); elseif if(data>p->data) p->right=insert(data,p->right); else printf(“duplicate value not allowed”); return(p); } int menu() { int c; printf(“MAIN MENU\n”); printf(“1:create btree\n 2: traversal \n 3:exit\n enter ur choice\n”); scanf(“%d”,&c); return( c); } void countnode() { btree *t; int count=0; t=root; top=0; while(top>=0) { if(t!=NULL) { if((t->left= =NULL) && (t->right= =NULL)) lnode++; count++; if(t->right!=NULL) push(t->right); t=t->left; } else t=pop(); } printf(“the total no. of nodes =%d\n”,count); printf(“the count of leaf nodes is %d\n”,lnode); printf(“the no. of interior nodes is %d”,count-lnode-1); } void recinorder(btree *r) { if(r!=NULL) { recinorder(r->left); printf(“%c”,r->data);

72

recinorder(r->right); } } void recpreorder(btree *r) { if(r!=NULL) { printf(“%c”,r->data); recpreorder(r->left); recpreorder(r->right); } } void recpostorder(btree *r) { if(r!=NULL) { recpostorder(r->left); recpostorder(r->right); printf(“%c”,r->data); } } void preorder() { btree *t; t=root; top=0; stack[top]=NULL; printf(“the preorder form is:\n”); while(t!=NULL) { printf(“%c”,t->data); if(t->right!=NULL) push(t->right); if(t->left!=NULL) t=t->left; else t=pop(); } } void inorder() { btree *t; t=root; printf(“the inorder form is :\n”);

73

top=0; stack[top]=NULL; a: while(t!=NULL) { push(t); t=t->left; } t=pop(); while(t!=NULL) { printf(“%c”,t->data); if(t->right!=NULL) { t=t->right; goto a; } t=pop(); } } void postorder() { btree *p,*temp; printf(“the postorder form\n”); top=0; temp=NULL; p=root; while(p->left!=NULL) { push(p); p=p->left; } while(p!=NULL) { if((p->right = = NULL) || (p->right= =temp)) { printf(“%c”,p->data); temp=p; p=pop(); } else { push(p); p=p->right; while(p->left!=NULL)

74

{ push(p); p=p->left; } } } } void main() { int ch,n; char c=’y’; top=0; while(1) { ch=menu(); switch(ch) { case 1: root=NULL; while(c= =’y’) { printf(“enter data”); scanf(“%d”,&n); root=insert(a,root); printf(“enter choice (y/n):”); scanf(“%c”,&c); } break; case 2: traversal(); break; case 3: exit(0; } } } void traversal() { int x; printf(“1: with recursion\n 2: without recursion\n); scanf(“%d”,&x); switch(x) { case 1: rec(); break; case 2: withoutrec(); break; } }

75

void rec() { while(1) { int x; printf(“1: inorder 2: preorder 3: postorder\n enter ur choice”); scanf(“%d”,&x); switch(x) { case 1: recinorder(root); break; case 2: recpreorder(root); break; case 3: recpostorder(root); break; case 4: return; } }} void withoutrec() { while(1) { int x; printf(“1: inorder 2: preorder 3: postorder\n enter ur choice”); scanf(“%d”,&x); switch(x) { case 1: inorder(); break; case 2: preorder(); break; case 3: postorder(); break; case 4: return; } } }

76

PROBLEM 122:- DFS (Graph Traversal using stacks) PROCEDURE:1. Initialize all nodes to the ready state (STATUS=1) 2. Push the starting node A onto STACK and change its status to the waiting state (STATUS=2). 3. Repeat steps 4 and 5 until STACK is empty. 4. Pop the top node N of STACK. Process N and change its status to the processed state (STATUS=3) 5. Push onto STACK all the neighbors of N that are still in the ready state (STATUS=1), and change their status to the waiting state (STATUS=2). 6. Exit.

CODE:#include<stdio.h> char stack[10]; int top=-1; char pop(); void push(char x); void main() { int a[10][10],m,n; int i,j,state[10]; char g[10],x; printf(“enter the no. of nodes of graph”); scanf(“%d”,&n); printf(“enter the nodes of the graph”); for(i=1;i<=n;i++) g[i]=getchar(); printf(“enter the adjacency matrix of the graph”); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf(“%d”,&a[i][j]); for(i=1;i<=n;i++) state[i]=1; state[1]=2; push(g[1]); while(top!=-1) { x=pop(); for(i=1;i<=n;i++) if(x= =g[i]) break; state[i]=3;

77

printf(“%c”,g[i]); for(j=1;j<=n;j++) { if((a[i][j]= =1) && (state[j] = =1)) { state[j]=2; push(g[j]); } } } } void push(char x) { top++; stack[top]=x; } char pop() { return(stack[top--]); }

78

PROBLEM 123:- BFS (Graph Traversal using queues) PROCEDURE:1. Initialize all nodes to the ready state (STATUS=1) 2. put the starting node A in QUEUE and change its status to the waiting state (STATUS=2) 3. Repeat steps 4 and 5 until QUEUE is empty: 4. Remove the front node N of QUEUE. Process N and change the status of N to the processed state (STATUS=3) 5. Add to the rear of QUEUE all the neighbors of N that are in the steady state (STATUS=1) and change their status to the waiting state (STATUS=2). 6. Exit.

CODE:#include<stdio.h> char queue[10]; int front=0,rear=-1; char delete(); void insert(char x); void main() { int a[10][10],m,n; int i,j,state[10]; char g[10],x; printf(“enter the no. of nodes of graph”); scanf(“%d”,&n); printf(“enter the nodes of the graph”); for(i=1;i<=n;i++) g[i]=getchar(); printf(“enter the adjacency matrix of the graph”); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf(“%d”,&a[i][j]); for(i=1;i<=n;i++) state[i]=1; state[1]=2; insert(g[1]); while(front<=rear) { x=delete(); for(i=1;i<=n;i++) if(x= =g[i]) break; state[i]=3; printf(“%c”,g[i]); for(j=1;j<=n;j++)

79

{ if((a[i][j]= =1) && (state[j] = =1)) { state[j]=2; insert(g[j]); } } } } void insert(char x) { queue[++rear]=x; } char delete() { return(queue[front++]); }

80

PROGRAMS ON SEARCHING & SORTING PROBLEM 124:- Write a program to perform linear search. PROCEDURE:1. enter n value 2. read n values into the array a[]. 3. enter the element x which we want to search 4. compare x value with each element of array elements from a[0] to a[n] 5. if element found print “element found” else print “element is not found” 6. exit.

CODE:#include<stdio.h> void main() { int i,b,a[100],flag,n; clrscr(); printf(“Entern:”); scanf(“%d”,&n); printf(“”Enter %d elements:”,n); for(i=0;i
81

PROBLEM 125:- Write a program to perform binary search PROCEDURE:1. enter n value 2. read n values into the array a[]. 3. sort the array elements. 4. enter the element x which we want to seach 5. assign flag=0,low=0 and high =n-1; 6. while ( low<=high) repeat the process 7. find mid value of an array mid=(low+high)/2. 8. if (a[mid])>x) high=mid-1; 9. else if (a[mid]<x) low=mid+1; 10 else print “ element found”. Flag =1; 11. if (flag==0) print” element is not found”; 12. exit.

CODE:#include<stdio.h> int a[50],I,x,n,z; void main() { clrscr(); prinf(“Enter n:”); scanf(“%d”,&n); printf(“Enter %d elements:”,n); for(i=1;i<=n;i++) scanf(“%d”,&a[i]); printf(“Enter element to be seached:”); scanf(“%d”,&n); z=bs(); if(z>0) printf(“The element os found at %dth position”,z); else printf(“Element is not found”); getch(); } int bs() { int mid,lb=1,ub=n; while(lb<=ub)

82

{ mid=(lb+ub)/2; if(xa[mid]) lb=mid+1; else terurn mid; } return(-1); }

83

PROBLEM 126:- Write a program to sort data using bubble sort. PROCEDURE:BUBBLE(DATA,N) Here DATA is an array with N elements. This algorithm sorts the elements in DATA 1. Repeat steps 2 and 3 for k=1 to n-1 2. set PTR:=1 3. Repeat while PTR<=n-k (a) if DATA[PTR]> DATA[PTR+1], then interchange DATA[PTR] and DATA[PTR+1] (b) set PTR:= PTR+1. 4. Exit.

CODE:#include<stdio.h> void main() { int I,n,j,a[50],t; clrscr(); prinf(“Enter how many no’s”); scanf(“%d”,&n); printf(“Enter the no’s:\n”); for(i-1;i<=n;i++0 scanf(“%d”,&a[i]); for (i=1;i<=n-1;i++) { for(j=1;j<=n;j++) if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } printf(“pass %d-“,i); for(j=1;j<=n;j++) printf(“%d”,j[a]); printf(“\n”,); } getch(); }

84

PROBLEM 127:- Write a program to sort data using selection sort. PROCEDURE:Min(a,k,n,loc) 1. set min=a[k] and loc=k 2. Repeat for j =k+1 …….n if min>a[j], then set min=a[j] and loc=a[j] and loc=j 3. return. Selection(a,n) 1. repeat steps 2 and 3 for k=1,2…..n-1 2. call min(a,k,n,loc) 3. set temp=a[k], a[k]=a[loc], a[loc]=temp 4. Exit.

CODE:Void main() { int I,n,j,a[50],k,f,min; clrscr(); printf(“Enter hoe many no’s”); scanf(%d”,&n); printf(“Enter the no’s:\n”); for(i=1;i<-n;i++) scanf(“%d”,&i[a]); for(i-1;i<=n-1;i++) { min=a[i]; for(j=i+1;j<=n;j++0 if(min>a[j]) { min=a[j]; k=j; } if(a[i]!=min) { a[k]=a[i]; a[i]=min; } printf(“pass %d-“,i); for(j=1;j<=n;j++) printf(:%d”,j[a]); printf(“\n”); }getch();}

85

PROBLEM 128:- Write a program to sort data using insertion sort. PROCEDURE:insertion (a,n) 1. set a[0]=-9999. 2. Repeat steps 3 t 5 for k=2,3….n; 3. set temp=a[k] and ptr=k-1; 4. repeat while temp
CODE:#include<stdio.h rel="nofollow"> int i,j,l,in[20]; void insertionsort(); void main() { clrscr(); printf(“Enter the no. of numbers U want to enter :”); scanf(“%d”,&l); printf(“\n Enter %d n’s:”,l); for(i=1;i
86

in[ptr+1]=temp; printf(“\n pass %d:”,pass+1); for(k=1;k<=l;k++) printf(:%6d”,in[k]); } }

87

PROBLEM 129:- Program to sort data using quick sort. PROCEDURE:quick (a,n,beg,end,loc) Here a is an array with n elements. Parameters beg and end contain the boundary values of the sublist of a to which this procedure applies. Loc keeps track of the position of the first element a[beg] of the sublist during the procedure. The local variables left and right will contain the boundary fvalues of the list of elements that have not been scanned. 1. set left=beg, right =end and loc=beg 2. (a) repeat while a[loc]<=a[right] and loc!=right right=right-1. (b) if loc=right then return (c ) if a[loc]>a[right] , then (i) interchange a[loc] and a[right] (ii) set loc=right (iii) go to step 3. 3. (a) repeat while a[left]<=a[loc] and left!=loc; left=left+1; (b) if loc=left then return; (c ) if a[left]>a[loc], then (i) interchange a[left] and a[loc] (ii) set loc=left (iii) go to step 2. Quick sort , this algorithm sorts an array a with n elements. 1. top=null; 2. if n>1, then top =top+1, lower[1]=1, upper[1]=n 3. repeat steps 4 to 7 while top!=null 4. set beg=lower[top], end=upper[top] top=top-1; 5. call quick(a,n,beg,end,loc) 6. if beg
CODE:#include<stdio.h> int a[20],l; void quicksort(int m,int p) { int i,j,x,t,k; static int pass=1;

88

i=m;j=p; x=a[(m+p)/2]; do { while((a[i]<x) && (i
89

PROBLEM 130:- Write a program to sort data using heap sort. PROCEDURE:INHEAP(tree, n, item) a heap h with n elements is stored in the array tree, and an item of information is given. This procedure inserts item as a new element of h. ptr gives the location of item as it rises in the tree, and par denotes the location of the parent of item. 1. set n=n+1 and ptr=n. 2. repeat steps 3 to 6 while ptr<1. 3. set par=ptr/2 4. if item <=tree[par], then set tree[ptr]=item, and return 5. set tree[ptr]=tree[par] 6. set ptr=par. 7. set tree[1]=item 8. return

DELHEAP(tree, n, item) A heap h with n elements is stored in the array tree. This procedure assigns the root tree[1] of h to the variable item and then reheaps the remaining elements. The variable last saves the value of the original last node of h. The pointers ptr, left and right give the locations of last and its left and right children as last sinks in the tree. 1. set item=tree[1] 2. set last=tree[n] and n=n-1. 3. set ptr=1, left=2 and right=3 4. repeat steps 5 to 7 while right<=n; 5. if last rel="nofollow">= tree[left] and last>=tree[right], then set tree[ptr]=last and return. 6. if tree[right]<=tree[left], then set tree[ptr]=tree[left] and ptr=left else set tree[ptr]=tree[right] and ptr=right 7. set left=2*ptr and right=left+1 8. if left=n and if last
CODE:#include<stdio.h> #include int a[50],l; int s,f,i,i1,k1=0,elt;

90

void sort(int); void crheap(int n1) { for(i=1;i0 && a[f]<elt) { a[s]=a[f]; s=f; f=(s-1)/2i; } a[s]=elt; } } void sort(int n1) { crheap(n1); for(i=n1-1;i>o;i--) { elt =a[i]; a[i]=a[0]; f=0; if(i= =1) s=-1; else s=1; if((i>z) && (a[z]>a[i])) s=z; while(s>=0 && elti-1) s=-1; } a[f]=elt; k1++; printf(“\n PASS %d”,k1); for(i1=1,i1<=n;i1++) printf(“%d”, a[i]); }} void main() { int I,t; clrscr(); printf(“HEAP SORT”); printf(“enter the no of elements”); scanf(“%d”, &l;

91

printf(“Enter the elements”); for(i=0;i
92