Data Structures & System Programming Lab File

Data Structures & System Programming S.NO PROGRAM . 1. Program to traverse an array 2. Program to insert an element in an array 3. Program to find a number using linear search 4. Program to delete an element from an array 5. Program to Binary search 6. Program to find the smallest and largest number 7. Program to Bubble sort 8. Program to enter and traverse a linked list 9. Program to insert an element at begining, at end, after a given element, before a given element. 10. Progrm to delete at begning, at end, before given element, given element and after the given element. 11. Program to search in a linked list 12. Program of insertion two way link list 13. WAP to demonstrate Quick sort. 14. Program to implement stacks using array 15. Program to Stack using linked list

1

PAGE NO. 3 4 5 6 7 8 9 10 12 16 20 22 23 26 28

Data Structures & System Programming

//1.Program to traverse an array

DATE:- 17/08/09

#include #include void main() { int i,a[100],n; clrscr(); cout<<"Enter the number of elements of array:"; cin>>n; for(i=0;i>a[i]; cout<<" The entered array is \n"; for(i=0;i
2

Data Structures & System Programming

//2.Program to insert an element in an array #include #include void main() {int i,j,a[100],n,num,k; clrscr(); cout<<"Enter the number of elements of array "; cin>>n; cout<<"enter the array elements\n"; for(i=0;i>a[i]; cout<<"The given array is\n"; for(i=0;i>j>>num; for(k=n;k>=j;k--) a[k+1]=a[k]; a[j]=num; cout<<" The array after intertion is \n"; for(i=0;i
DATE:-17/08/09

Data Structures & System Programming The array after insertion is 43 32 23 41 65

67

//3.Program to find a number using linear search DATE:-17/08/09 #include #include void main() {int i,a[100],n,num,k=0; clrscr(); cout<<" Enter the number of elements"; cin>>n; cout<<"Enter the array elements \n"; for(i=0;i>a[i]; cout<<"enter the element to search"; cin>>num; for(i=0;i
4

Data Structures & System Programming

4.// Program to delete an element from an array #include #include void main() {int i,j,k,n,a[100]; clrscr(); cout<<"enter the number of array elements"; cin>>n; cout<<" enter the array elements \n"; for(i=0;i>a[i]; cout<<" enter the location to delete the element"; cin>>j; for(;j
5

DATE:-17/08/09

Data Structures & System Programming

5.// Binary search #include #include void main() {int i,j,b=0,e,n,m,a[100],k=1; clrscr(); cout<<"Enter the number of array elements: "; cin>>n; cout<<"Enter the array elements in order :\n"; for(i=0;i>a[i]; cout<<"Enter the element to search "; cin>>m; e=n; while(b<e) {j=(b+e)/2; if(a[j]==m) {k=0; break;} if(ma[j]) b=j+1; } if(k==0) cout<<"\nElement "<<m<<"found at "<<j; else cout<<"\nElement not found"; getch(); } Output Enter the number of array elements: 3 Enter the array elements in order: 21 34 35 6

DATE:-24/08/09

Data Structures & System Programming Enter the element to search34 Element34 found at2 //6. Program to find the smallest and largest number #include #include void main() {int i,j,k,a[100],n; clrscr(); cout<<"Enter the number of elements of array"; cin>>n; cout<<"Enter the array elements\n "; for(i=0;i>a[i]; j=a[0]; for(i=0;ia[i]) j=a[i]; } cout<<"The Smallest element is "<<j; getch(); } Output Enter the number of array elements 7 Enter the array elements 64 67 4563 34 2 23 The greatest element is 4563 The smallest element is 2 7

DATE:-24/08/09

Data Structures & System Programming

7//. Program to Bubble sort #include #include void main() {int i,j,k,a[100],n,temp; clrscr(); cout<<"Enter the number of array elements "; cin>>n; cout<<"Enter the array elements\n"; for(i=0;i>a[i]; for(j=0;ja[k+1]) {temp=a[k]+a[k+1]; a[k+1]=temp-a[k+1]; a[k]=temp-a[k+1]; } }} cout<<"The array after rearrangement is\n"; for(i=0;i
8

DATE:-24/08/09

Data Structures & System Programming

//8.Program to enter and traverse a linked list

DATE:-7/09/09

#include #include struct node {int item; node*next; }; void main() {clrscr(); int a,i=0; node*start=NULL; node*temp2; cout<<"enter the number of items:"; cin>>a; do {node*temp=new node; cout<<"Enter the item no. "; cin>>temp->item; temp->next=NULL; if(start==NULL) start=temp; else {for(temp2=start;temp2->next!=NULL;temp2=temp2->next); temp2->next=temp;} i++; }while(inext) cout<<"The item no. is "<item<<"\n"; getch();} Output: Enter the number of items 4 Enter the item no. 4 Enter the item no. 3 Enter the item no. 2 Enter the item no. 5 The item no. is 4 9

Data Structures & System Programming The item no. is 3 The item no. is 2 The item no. is 5 //9.Program to insert an element at begining, at end, after a given element, before a given element. DATE:-7/09/09 #include #include #include<dos.h> struct node {int item; node*next; }; void insertb(node**x,int c) { node*temp=new node; temp->item=c; temp->next=*x; *x=temp; } void insertbe(node**x,int c) {node*temp2; node*y=NULL; int n,k=0; cout<<"enter the item to insert"; cin>>n; if((*x)->item==c) insertb(x,n); else{ node*temp=new node; for(temp2=(*x);temp2!=NULL;temp2=temp2->next) {if(temp2->item==c) {k=1; break;} y=temp2;} if(k==0) cout<<"item not found"; if(k==1) {temp->item=n; temp->next=temp2; 10

Data Structures & System Programming y->next=temp;}}} void insertaf(node**x,int c) { int k=0,n; node*temp2; for(temp2=*x;temp2!=NULL;temp2=temp2->next) {if(temp2->item==c) {k=1; break;}} if(k==0) cout<<"item not found"; if(k==1) {cout<<"enter the item"; cin>>n; node*temp=new node; temp->item=n; temp->next=temp2->next; temp2->next=temp; } } void main() {clrscr(); int a,i=0; char d; node*start=NULL; node*temp2; cout<<"enter the number of nodes:"; cin>>a; do {node*temp=new node; cout<<"enter he item no. "; cin>>temp->item; temp->next=NULL; if(start==NULL) start=temp; else {for(temp2=start;temp2->next!=NULL;temp2=temp2->next); temp2->next=temp;} i++; 11

Data Structures & System Programming }while(inext) cout<item<<"\n"; int b,c; do{ cout<<"What operation you want to perform \n1. Insert at begning \n"; cout<<"2. Insert at end \n3. Insert before given node \n"; cout<<"4. Insert after a given node\n5. Exit\n"; cout<<"enter your choice(1-5)"; cin>>b; if(b==5) break; switch (b) {case 1:cout<<"enter the item to insert"; cin>>c; insertb(&start,c); break; case 2:cout<<"enter the item to insert"; cin>>c; node*temp=new node; temp->item=c; temp->next=NULL; for(temp2=start;temp2->next!=NULL;temp2=temp2->next); temp2->next=temp; break; case 3:cout<<"enter the item for search"; cin>>c; insertbe(&start,c); break; case 4:cout<<"enter the item for search"; cin>>c; insertaf(&start,c); break; default: cout<<"wrong choice\n"; } cout<<"do you want to insert again (n/y)"; cin>>d; 12

Data Structures & System Programming sleep(2); clrscr(); }while(d=='y'); cout<<"the list after processing is\n"; for(temp2=start;temp2!=NULL;temp2=temp2->next) cout<item<<"\n"; getch(); } Output: Enter the number of nodes 4 Enter the item no. 4 Enter the item no. 6 Enter the item no. 7 Enter the item no. 9 The item no. of items selected are 4 6 7 9 What operation you want to perform 1. Insert at beginning 2. Insert at end 3. Insert before given node 4. Insert after a given node 5. Exit. Enter your choice (1-5) 1 Enter the item to insert 2 Do you want to insert again (n/y) y What operation you want to perform 1. Insert at beginning 2. Insert at end 3. Insert before given node 4. Insert after a given node 5. Exit. Enter your choice (1-5) 2 Enter the item to insert 10 Do you want to insert again (n/y) y What operation you want to perform 6. Insert at beginning 13

Data Structures & System Programming 7. Insert at end 8. Insert before given node 9. Insert after a given node 10.Exit. Enter your choice (1-5) 3 Enter the item for search 4 Enter the item to insert 3 Do you want to insert again (n/y) y What operation you want to perform 1. Insert at beginning 2. Insert at end 3. Insert before a given node 4. Insert after a given node 5. Exit. Enter your choice (1-5) 4 Enter the item for search 4 Enter the item 5 Do you want to insert again (n/y) y What operation you want to perform 1. Insert at beginning 2. Insert at end 3. Insert before a given node 4. Insert after a given node 5. Exit. Enter your choice (1-5) 5 The list after processing is 2 3 4 5 6 7 8 9 10

14

Data Structures & System Programming 10.// Progrm to delete at begning, at end, before given element, given element and after the given element. DATE:-7/09/09 #include #include struct node {int item; node*next; }; void deleteb(node**x) {node*temp; temp=*x; *x=(*x)->next; delete temp;} void deletebe(node**x) {int c,k=0; node*temp2,*temp=NULL,*temp3=NULL; cout<<"enter the item before ehich you want to delete"; cin>>c; for(temp2=(*x);temp2!=NULL;temp2=temp2->next) {if(temp2->item==c) {k=1; break;} temp3=temp; temp=temp2;} if(k==0) cout<<"item not found"; if(k==1) {if(temp==temp3) cout<<"deletion not possible\n"; else if(temp3==NULL) deleteb(x); else{ temp3->next=temp2; delete(temp);}}} void deleteaf(node**x) 15

Data Structures & System Programming {int c,k=0; node*temp2,*temp; cout<<"enter the item after which you want to delete"; cin>>c; for(temp2=(*x);temp2->next!=NULL;temp2=temp2->next) {if(temp2->item==c) {k=1; break;}} if(k==0) cout<<"deletion not possible\n"; else{ temp=temp2->next; temp2->next=temp->next; delete temp;}} void atnode(node**x) {int c,k=0; node*temp2,*temp=NULL; cout<<"enter the item which you want to delete"; cin>>c; for(temp2=(*x);temp2!=NULL;temp2=temp2->next) {if(temp2->item==c) {k=1; break;} temp=temp2;} if(k==0) cout<<"Item not found"; else if(temp2==*x) deleteb(x); else{ temp->next=temp2->next; delete temp2;}} void main() {clrscr(); int a,i=0; node*start=NULL; node*temp2,*temp; cout<<"enter the number of nodes:"; cin>>a; 16

Data Structures & System Programming do {node*temp=new node; cout<<"enter he item no. "; cin>>temp->item; temp->next=NULL; if(start==NULL) start=temp; else {for(temp2=start;temp2->next!=NULL;temp2=temp2->next); temp2->next=temp;} i++; }while(inext) cout<item<<"\n"; int b; cout<<"What operation you want to perform \n1. Delete at begning \n"; cout<<"2. Delete at end \n3. Delete before given node \n"; cout<<"4. Delete after a given node\n5. Delete a node with given piece of information\n"; cout<<"6. Exit\nenter your choice(1-6)"; cin>>b; if(start==NULL) cout<<"Deletion not possible"; switch (b) {case 1:deleteb(&start); break; case 2: for(temp2=start;temp2->next!=NULL;temp2=temp2->next) temp=temp2; delete (temp2); temp->next=NULL; break; case 3:deletebe(&start); break; case 4:deleteaf(&start); break; case 5:atnode(&start); break; case 6: break; default:cout<<"wrong choice"; 17

Data Structures & System Programming } Cout<< ”The list after processing is\n”; for(temp2=start;temp2!=NULL;temp2=temp2->next) cout<item<<"\n"; getch(); } Output Enter the number of nodes 5 Enter the item no. 3 Enter the item no. 5 Enter the item no. 7 Enter the item no. 9 Enter the item no. 11 The item no. of items selected are 3 5 7 9 11 What operation do you want to perform 1. Delete at beginning 2. Delete at end 3. Delete before given node 4. Delete after a given node 5. Delete a node with given piece of information 6. Exit. Enter your choice (1-6) 5 Enter the item which you want to delete 3 The list after processing is 5 7 9 11

18

Data Structures & System Programming //11. Program to search in a linked list DATE:-7/09/09 #include #include struct node {int item; node*next;}; void main() {clrscr(); int a,i=0,c,k=0; node*start=NULL; node*temp2; cout<<"enter the number of nodes:"; cin>>a; do {node*temp=new node; cout<<"enter the item no. "; cin>>temp->item; temp->next=NULL; if(start==NULL) start=temp; else {for(temp2=start;temp2->next!=NULL;temp2=temp2->next); temp2->next=temp;} i++; }while(i>c; for(temp2=start;temp2!=NULL;temp2=temp2->next) {if(temp2->item==c) {cout<<"item found"; k=1; break;}} if(k==0) cout<<"item not found"; getch(); }

19

Data Structures & System Programming Output Enter the number of nodes 6 Enter the item no. 12 Enter the item no. 23 Enter the item no. 34 Enter the item no. 45 Enter the item no. 56 Enter the item no. 67 Enter the item to search 34 Item found

20

Data Structures & System Programming 12. //Program of insertion two way link list DATE:-7/09/09 #include #include struct node {int item; node*forw; node*rev; }; void main() {int a,i=0; node*header; node*temp,*temp2; header->item=4355; header->forw=NULL; header->rev=NULL; cout<<"enter the number of nodes"; cin>>a; do{ node*temp=new node; cout<<"Enter the item code"; cin>>temp->item; temp->forw=NULL; temp->rev=NULL; if(header->forw==NULL) {header->forw=temp; temp->rev=header;} else{ for(temp2=header;temp2->forw!=NULL;temp2=temp2->forw); temp2->forw=temp; temp->rev=temp2; } i++; }while(iforw;temp2!=NULL;temp2=temp2->forw) cout<item<<endl; getch();}

21

Data Structures & System Programming 13. // WAP to demonstrate Quick sort. #include #include void main() { clrscr(); int top=NULL,lower[10],beg,end,loc; int higher[10],q[20],n; cout<<"This is programme of quick sort"<<endl; cout<<"Enter the no of element "<<endl; cin>>n; cout<<"Enter the element in integer"<<endl; for(int i=1;i<=n;i++) { cin>>q[i]; } int quick_sort(int [20],int,int,int,int); if(n>1) { ++top; lower[1]=1; higher[1]=n; } while(top!=NULL) { beg=lower[top]; end=higher[top]; --top; loc=quick_sort(q,n,beg,end,loc); if(beg
DATE:-5/10/09

Data Structures & System Programming lower[top]=loc+1; higher[top]=end; } } cout<<"The sorted list is following"<<endl; for(i=1;i<=n;i++) { cout<q[right]) { int temp; temp=q[loc]; q[loc]=q[right]; q[right]=temp; loc=right; } while(q[left]<=q[loc]&&left!=loc) { ++left; } 23

Data Structures & System Programming if(loc==left) return loc; if(q[left]>q[loc]) { int temp; temp=q[loc]; q[loc]=q[left]; q[left]=temp; loc=left; } } } Output: This is the program of quick sort Enter the number of elements 5 Enter the element in integer 12 33 44 11 16 The sorted list is following 11 12 16 33 44

24

Data Structures & System Programming //14.Program to implement stacks using array #include #include int push(int a[],int top) {if(top==20) cout<<"operation not possible"; else{ cout<<"Enter the element to push"; cin>>a[top]; top=top+1;} return top; } int pop(int top) {if(top==0) cout<<"operation not possible"; else top=top-1; return top;} void main() {int a[20],i,top,c,v=0; char ch; clrscr(); cout<<"Enter the no. of stack elements(>19)"; cin>>top; cout<<"Enter the elements\n"; for(i=0;i>a[i];

DATE:-12/10/09

do{cout<<"What operation do you want to perform\n"; cout<<"1. Push\n2. Pop\n3.Exit\n enter your choice(1-3) "; cin>>c; switch (c) {case 1:top=push(a,top); break; case 2:top=pop(top); break; case 3: v=1; break; 25

Data Structures & System Programming default: cout<<"wrong choice"; break;} if(v==1) break; cout<<"Do you want to perform operation again(n/y)"; cin>>ch; }while(ch=='y'); cout<<"\nThe stack elements are\n"; for(i=0;i
26

Data Structures & System Programming 15.//Stack using linked list DATE:-12/10/09 #include #include struct stack { int info; stack *next; }; class sta { stack *temp,*top,*ptr; public: sta () { top=NULL; } void push(); void pop(); void display(); }; void main() { clrscr(); sta st; int ch; char c='y'; cout<<"This is the programme of stack"<<endl; do { cout<<"The following choice in stack"<<endl; cout<<"1. Push()"<<endl<<"2. Pop"<<endl<<"3. Display"<<endl<<"4. Exit"<<endl; cout<<"Enter the chioce (1-4) :"<<endl; cin>>ch; switch(ch) { case 1:st.push(); getch(); 27

Data Structures & System Programming break; case 2:st.pop(); getch(); break; case 3:st.display(); getch(); break; case 4:c='n'; break; default: cout<<"You enter the wrong choice"<<endl; } }while(c=='y'||c=='Y'); cout<<"thank you"<<endl; getch(); } void sta::push() { temp=new stack; cout<<"Enter the info of the new node "<<endl; cin>>temp->info; temp->next=NULL; if(top==NULL) top=temp; else { temp->next=top; top=temp; } } void sta::pop() { if(top==NULL) cout<<"The stack is underflow"<<endl; else { top=top->next; cout<<"The pop opreation of stack is complete"<<endl; } } 28

Data Structures & System Programming void sta::display() { if(top==NULL) cout<<"The stack is empty"<<endl; else { cout<<"The element in stack is following"<<endl; ptr=top; while(ptr!=NULL) { cout<info<<"\t"; ptr=ptr->next; } cout<<endl; }}

29