Data Structure lab on a practical in computer science

Data Structure lab on a practical in computer science

• 1.
  /*binary search tree*/ #include<iostream.h> #include<conio.h> structtree { int info; struct tree *left,*right; }*head,*new1,*temp; void insert() { int flag=1; new1=new tree; new1->right=new1->left=NULL; cout<<"n Enter the info="; cin>>new1->info; temp=head; if(head->left==NULL) { head->left=new1; cout<<"n Node is attached"; } else{ temp=temp->left; while(flag) { if(temp->info<new1->info) { if(temp->right==NULL) { temp->right=new1; flag=0; cout<<"n node is attached"; } else{ temp=temp->right; } } else{ if(temp->left==NULL)
• 2.
  { temp->left=new1; flag=0; cout<<"n node isattached"; } else{ temp=temp->left; } } } } } void preorder(struct tree *temp) { cout<<" "<<temp->info; if(temp->left!=NULL) preorder(temp->left); if(temp->right!=NULL) preorder(temp->right); } void postorder(struct tree *temp) { if(temp->left!=NULL) postorder(temp->left); if(temp->right!=NULL) postorder(temp->right); cout<<" "<<temp->info; } void inorder(struct tree *temp) { if(temp->left!=NULL) inorder(temp->left); cout<<" "<<temp->info; if(temp->right!=NULL) inorder(temp->right); } void menu() { cout<<"n1.INSERTn";
• 3.
  cout<<"n1.PREORDERn"; cout<<"n1.INORDERn"; cout<<"n1.POSTORDERn"; } main() { clrscr(); int ch=0; head=new tree; head->left=head->right=NULL; menu(); while(ch!=5) { cout<<"nEnter your choice = "; cin>>ch; switch(ch) { case 1:insert();break; case 2:preorder(head->left);break; case 3:inorder(head->left);break; case 4:postorder(head->left);break; default:cout<<"Exit";break; } } getch(); } /*Quick Sort*/ #include <stdio.h> #include<iostream.h> #include<conio.h> int partition(int arr[], int start, int end) { int pivot = arr[end]; int i = start-1 ; int temp;
• 4.
  for (int j=start; j<end; j++) { if (arr[j] < pivot) { i++; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } temp=arr[i+1]; arr[i+1]=arr[j]; arr[j]=temp; return(i+1); } // The QuickSort function implementation void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi-1); quickSort(arr, pi+1, high); } } void main() { clrscr(); int i; int arr[] = {2,7, 8, 9, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"n unsorted array=>n"; for(i =0; i<n;i++) cout<<arr[i]<<" "; quickSort(arr,0,n-1); cout<<"nsorted arra=>"<<endl; for (i = 0; i<n; i++) { cout << arr[i] << " "; } getch(); } /*Simple merge*/ #include<iostream.h> #include<conio.h> main()
• 5.
  { clrscr(); int A[4],B[4],C[8]; int i,j,k; cout<<"Enterthe array A =>"; for(i=0;i<4;i++) cin>>A[i]; cout<<"Enter the array B =>"; for(i=0;i<4;i++) cin>>B[i]; i=0;j=0;k=0; while(i<4 && j<4) { if(A[i]<B[j]) { C[k]=A[i]; k++; i++; } else{ C[k]=B[j]; j++; k++; } } while(j<4) { C[k]=B[j]; k++;j++; } while(i<4) { C[k]=A[i]; i++; k++; } cout<<"n Sorted array"; for(k=0;k<8;k++) cout<<" "<<C[k];
• 6.
  getch(); } /* merge sort*/ #include<iostream.h> #include<conio.h> #include<alloc.h> voidmerge(int a[],int i1,int j1,int i2,int j2) { int temp[50]; int i,j,k; i=i1;j=i2; k=0; while(i<=j1 && j<=j2) { if(a[i]<a[j]) { temp[k++]=a[i++]; } else{ temp[k++]=a[j++]; } } while(i<=j1) { temp[k++]=a[i++]; } while(j<=j2) { temp[k++]=a[j++]; } for(i=i1,j=0;i<=j2;i++,j++) { a[i]=temp[j]; } } void mergesort(int a[],int start,int end) { int mid;
• 7.
  if(start<end) { mid=(start+end)/2; mergesort(a,start,mid); mergesort(a,mid+1,end); merge(a,start,mid,mid+1,end); } } main() { clrscr(); int *a,n; int i,j,k; cout<<"nEnter the size of array=>"; cin>>n; a=(int *)malloc(sizeof(n)); cout<<"Enter the array =>"; for(i=0;i<n;i++) cin>>a[i]; mergesort(a,0,n); cout<<"Sorted array =>"; for(i=0;i<n;i++) cout<<a[i]<<" "; getch(); } /*BFS*/ #include<iostream.h> #include<conio.h> void main() { int a[10][10],q[10],v[10]; int f=0,r=-1,i,j,x,start,nov; cout<<"enter the number of vertices"; cin>>nov; cout<<"enter the matrix"; for(i=0;i<nov;i++) {
• 8.
  for(j=0;j<nov;j++) { cin>>a[i][j]; } } cout<<"n enter thestarting point"; cin>>start; for(i=0;i<nov;i++) v[i]=0; cout<<"n BFS"; ++r; q[r]=start; v[start]=1; while(f<=r) { x=q[f]; cout<<" "<<x; f++; for(i=0;i<nov;i++) { if(v[i]==0 && a[x][i]==1) { r++; q[r]=i; v[i]=1; } } } getch(); } /*DFS*/ #include<iostream.h> #include<conio.h> void main() { int a[10][10],s[10],v[10]; int top=-1,i,j,x,start,nov; cout<<"enter the number of vertices"; cin>>nov;
• 9.
  cout<<"enter the matrix"; for(i=0;i<nov;i++) { for(j=0;j<nov;j++) { cin>>a[i][j]; } } cout<<"nenter the starting point"; cin>>start; for(i=0;i<nov;i++) v[i]=0; cout<<"n DFS"; top++; s[top]=start; v[start]=1; while(top>-1) { x=s[top]; cout<<" "<<x; top--; for(i=0;i<nov;i++) { if(v[i]==0 && a[x][i]==1) { top++; s[top]=i; v[i]=1; } } } getch(); } /*linear search*/ #include<iostream.h> #include<conio.h> #include<alloc.h> int linear_search(int *b,int n,int val) {
• 10.
  int cnt=-1,j; for(j=0;j<=n;j++) { if(b[j]==val) { cnt=j; break; } } return cnt; } voidmain() { clrscr(); int*a,n,i,val; cout<<"enter the size of array=>"; cin>>n; a=(int*)malloc(n*sizeof(int)); cout<<"n enter the elements of array=>"; for(i=0;i<n;i++) { cin>>a[i]; } cout<<"n enter the ele for serach=>"; cin>>val; int result=linear_search(a,n,val); (result!=-1)?cout<<"n element is present at "<<result+1:cout<<"element is not present"; getch(); } /*binary search*/ #include<iostream.h> #include<conio.h> #include<stdlib.h> void binary_search(int *a,int lb,int ub,int key) { while(lb<=ub) {
• 11.
  int mid=(lb+ub)/2; if(key==a[mid]) { cout<<"n Searchsuccessful key present at ="<<mid+1; getch(); exit(0); } if(key>a[mid]) lb=mid+1; else ub=mid-1; } cout<<"n Unsuccessful search"; } void main() { clrscr(); int*a,n,i,val; cout<<"enter the size of array=>"; cin>>n; a=(int*)malloc(n*sizeof(int)); cout<<"n enter the elements of array=>"; for(i=0;i<n;i++) { cin>>a[i]; } cout<<"n enter the ele for serach=>"; cin>>val; binary_search(a,0,n,val); getch(); } /*Bubble Sort*/ #include<iostream.h> #include<conio.h> #include<alloc.h> void main() { clrscr(); int i,*a,n,temp,pass; cout<<"n Enter the size of array=>";
• 12.
  cin>>n; a=(int *)malloc(n*sizeof(int)); cout<<"n Enterthe array=>"; for(i=0;i<n;i++) cin>>a[i]; int last=n; for(pass=n;pass>=0;pass--) { for(i=last;i>=0;i--) { if(a[i]>a[i-1]) { temp=a[i]; a[i]=a[i-1]; a[i-1]=temp; } } } cout<<"n Sorded arrayn"; for(i=0;i<n;i++) cout<<" "<<a[i]; getch(); } /*insertion Sort*/ #include<iostream.h> #include<conio.h> #include<alloc.h> void main() { clrscr(); int i,*a,n,mid_id,j; cout<<"n Enter the size of array=>"; cin>>n; a=(int *)malloc(n*sizeof(int)); cout<<"n Enter the array=>"; for(i=0;i<n;i++) cin>>a[i]; int key; for(i=1;i<n;i++)
• 13.
  { key=a[i]; j=i-1; while(j>=0 && a[j]>key) { a[j+1]=a[j]; j--; } a[j+1]=key; } cout<<"nSorded arrayn"; for(i=0;i<n;i++) cout<<" "<<a[i]; getch(); } /*selection Sort*/ #include<iostream.h> #include<conio.h> #include<alloc.h> void main() { clrscr(); int i,*a,n,min_id,pass,temp; cout<<"n Enter the size of array=>"; cin>>n; a=(int *)malloc(n*sizeof(int)); cout<<"n Enter the array=>"; for(i=0;i<n;i++) cin>>a[i]; int key; for(pass=0;pass<n;pass++) { min_id=pass; for(i=pass+1;i<n;i++) { if(a[i]<a[min_id]) min_id=i; }
• 14.
  if(min_id!=pass) { temp=a[pass]; a[pass]=a[min_id]; a[min_id]=temp; } } cout<<"n Sorded arrayn"; for(i=0;i<n;i++) cout<<""<<a[i]; getch(); }