Asked by:
Data Structures & Algorithms

General discussion
-
Heap Sort
Code Block//Heap Sort
#include <stdio.h> //Include files
#include <conio.h>
void heapsort(int ar[], int len); //Function Prototypes
void heapbubble(int pos, int ar[], int len);
void main() //Start of main()
{int arr[10],i=0,n=0; clrscr(); //To clear the screen
printf("\nEnter number of Elements "); scanf("%d",&n);
printf("\nEnter Elements "); //Input data
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("\nEntered Array is "); //Display data
for(i=0;i<n;i++)
printf("%d ",arr[i]);
heapsort(arr,n); //Function call
printf("\nSorted Array is ");
for(i=0;i<n;i++) //Display Result
printf("%d ",arr[i]);
getch(); //To stop the screen
} //End of main()
void heapbubble(int pos,int array[],int len) //Function Definition
{int z=pos,max=0,tmp=0,left=0,right=0;
for(;;)
{left=2*z+1; right=left+1;
if(left>=len) return;
else if(right>=len) max=left; //Comparisons
else if(array[left]>array[right]) max=left;
else max=right;
if(array[z]>array[max]) return;
tmp=array[z];array[z]=array[max];array[max]=tmp; //Swapping
z=max;
}
} //End of function definition
void heapsort(int array[], int len) //Function Definition
{int i,tmp=0;
for(i=len/2;i>=0;--i)
heapbubble(i,array,len); //Function Call
for(i=len-1;i>0;i--)
{tmp=array[0];
array[0]=array[i];
array[i]=tmp;
heapbubble(0,array,i); //Function Call
}
} //End of function definition /*
OUTPUT
Enter number of elements 5
Enter Elements 1 9 8 7 5
Entered array is 1 9 8 7 5
Sorted Array is 1 5 7 8 9 */Wednesday, November 21, 2007 10:03 AM
All replies
-
Stack Implementation by Array
Code Block//Stack Implementation by Array
#include<stdio.h>
#include<conio.h>
int max=5,stack[5]; //Global Variables
void push(int stack[],int *top,int item); //Inserting
void pop(int stack[],int *top); //Deleting
void main() //Start of main()
{int value,i,ch,st_top=0; //Local variables
do{printf("\n1 to Add\n2 to Delete\n3 to Display\n0 to Quit ");
scanf("%d",&ch);
if(ch==1)
{printf("\nEnter Element "); scanf("%d",&value);
push(stack,&st_top,value); //Insertion call
}
if(ch==2) pop(stack,&st_top); //Deletion call
if(ch==3)
{if(st_top<=0) printf("\nStack Empty");
else
{printf("Elements are"); //Traversing
for(i=1;i<=st_top;i++) printf(" %d",stack[i]);
}
}
}while(ch!=0); //End of do_while loop
getch();
} //End of main()
void push(int stack[],int *top,int item) //Function definition
{if(*top==max) { printf("\nOverflow"); }
else
{*top=*top+1;
stack[*top]=item;
}
}
void pop(int stack[],int *top) //Function definition
{int item; //To store the deleted element
if(*top<=0) printf("\nUnderflow");
else
{item=stack[*top];
*top=*top-1;
printf("\nDeleted Element %d",item);
}
}Wednesday, November 21, 2007 10:08 AM -
Merge Sort
Code Block//Merge Sort
#include <stdio.h>
#include <conio.h>
void mergesort(int a[],int low,int high); //Function Prototype
void main() //Start of main()
{int arr[10],n=0,i; clrscr(); //To clear the screen
printf("\nEnter number of elements "); scanf("%d",&n);
printf("\nEnter Elements "); //Input data
for(i=0;i<n;i++)
{scanf("%d",&arr[i]); }
printf("\nEntered array is "); //Display data
for(i=0;i<n;i++)
{printf("%d ",arr[i]); }
mergesort(arr,0,n-1); //Function Call
printf("\nSorted Array is "); //Display Result
for(i=0;i<n;i++)
{printf("%d ",arr[i]); }
getch(); //To stop the screen
} //End of main()
void mergesort(int a[],int low,int high) //Function Definition
{int length=high-low+1,pivot=0,i;
int merge1=0,merge2=0;
int working[10];
if(low==high) return;
pivot=(low+high)/2;
mergesort(a,low,pivot); //Recursive Call
mergesort(a,pivot+1,high);
for(i=0;i<length;i++)
working[i]=a[low+i];
merge1=0; merge2=pivot-low+1;
for(i=0;i<length;i++) //Comparing
{if(merge2<=high-low)
if(merge1<=pivot-low)
if(working[merge1]>working[merge2])
a[i+low]=working[merge2++];
else
a[i+low]=working[merge1++];
else
a[i+low]=working[merge2++];
else
a[i+low]=working[merge1++];
}
} //End of function definition /*
OUTPUT
Enter number of elements 5
Enter Elements 1 9 8 7 5
Entered array is 1 9 8 7 5
Sorted Array is 1 5 7 8 9 */Wednesday, November 21, 2007 10:09 AM -
Operations on a Linked List
Code Block//Operations on a Linked List
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
void insertbet(struct node ** ,int ,int);
void insertatbeg(struct node ** ,int );
void insertatend(struct node **l);
void search(struct node **,int);
void del(struct node ** ,int);
void count(struct node * );
void display(struct node *);
struct node
{int data;
struct node *link;
};
void main()
{int choice=0,pos,num;
struct node *p;
p=NULL; //clrscr();
do{printf("\n1.Insert at Beginning\t2.Insert After Location\t3.Insert at End\n4.Display elements\t5.Count of nodes\t6.Delete the element\n7.Search an element\t0.QUIT\t");
scanf("%d",&choice);
switch(choice)
{case 0:choice=0;
break;
case 1:printf("\nEnter Element ");
scanf("%d",&num);
insertatbeg(&p,num);
break;
case 2:printf("\nEnter Position ");
scanf("%d",&pos);
printf("Enter Element ");
scanf("%d",&num);
insertbet(&p,pos-1,num);
break;
case 3:insertatend(&p);
break;
case 4:display(p);
break;
case 5:count(p);
break;
case 6:printf("\nEnter Element ");
scanf("%d",&num);
del(&p,num);
break;
case 7:printf("\nEnter Element ");
scanf("%d",&num);
search(&p,num);
break;
default:printf("\nWrong Entry");
}
}while(choice!=0);
getch();
}
void display(struct node *q)
{if(q==NULL)
printf("\nList Empty");
else
{printf("\nElements are ");
while(q!=NULL)
{printf("%d ",q->data);
q=q->link;
}
}
}
void count(struct node *q)
{int c=0;
while(q!=NULL)
{q=q->link;
c++;
}
printf("Number of nodes %d",c);
}
void insertbet(struct node**q ,int pos,int num)
{struct node *temp,*r;
int i;
temp=*q;
for(i=0;i<pos;i++)
temp=temp->link;
if(temp==NULL)
{printf("\nThere are less than %d elements",pos);
return;
}
r=(struct node*)malloc(sizeof(struct node));
r->data=num;
r->link=temp->link;
temp->link=r;
}
void insertatbeg(struct node **q,int num)
{struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data = num;
temp->link = *q;
*q=temp;
}
void del(struct node **q,int num)
{struct node *old,*temp;
temp=*q;
while(temp!=NULL)
{if(temp->data == num)
{if(temp==*q)
{*q=temp->link;
free(temp);
return;
}
else
{old->link=temp->link;
free(temp);
return;
}
}
else
{old=temp;
temp=temp->link;
}
}
printf("\nElement not Found");
}
void search(struct node **q,int num)
{int flag=0,c=0;
struct node *temp;
temp=*q;
while(temp != NULL)
{if(temp->data==num)
flag=1;
temp=temp->link;
c++;
}
if(flag)
printf("\nElement Found");
else
printf("\nNot such element ");
}
void insertatend(struct node **l)
{struct node *temp,*p;
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter Element ");
scanf("%d",&temp->data);
temp->link=NULL;
if(*l==NULL)
*l=temp;
else
{p=*l;
while(p->link!=NULL)
p=p->link;
p->link=temp;
}
}/*
OUTPUT:
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 1
Enter Element 51.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 3
Enter Element 151.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 2Enter Position 1
Enter Element 10
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 5Number of nodes 3
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 4Elements are 5 10 15
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 7Enter Element 12
Not such element
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 6Enter Element 5
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 4Elements are 10 15
1.Insert at Beginning 2.Insert After Location 3.Insert at End
4.Display elements 5.Count of nodes 6.Delete the element
7.Search an element 0.QUIT 0
Press any key to continue */Wednesday, November 21, 2007 10:11 AM -
Binary Search
Code Block//Binary Search
#include<stdio.h>
#include<conio.h>
void main()
{int data[25],i,j,temp,mid,loc=0,lb,ub,item,n;
printf("\Enter the no of elements ");
scanf("%d",&n);
ub=n-1; lb=0;
printf("\nEnter element ");
for(i=0;i<n;i++)
{scanf("%d",&data[i]);}
for(i=0;i<n;i++)
{for(j=i;j<n;j++)
{if(data[j]<data[i])
{temp=data[j];
data[j]=data[i];
data[i]=temp;
}
}
}
for(i=0;i<n;i++)
{printf("%d\t",data[i]);}
printf("Enter element to be searched");
scanf("%d",&item);
do{mid=(lb+ub)/2;
if(item==data[mid])
{loc=mid;break;}
if(item>data[mid])
{lb=mid+1;}
if(item<data[mid])
{ub=mid-1;}
}
while(ub>=lb);
if(loc==0) printf("Not found");
else
printf("Element at location %d",loc+1);
getch();
}Wednesday, November 21, 2007 10:12 AM -
Various Sorting Techniques
Code Block//Various Sorting Techniques
#include<stdio.h>
#include<conio.h>
void insertion(int,int d[20]);
void selection(int,int d[20]);
void bubble(int,int d[20]);
void display(int,int d[20]);
void main()
{
int size,i,data[20];
printf("Enter the size ofarray ");
scanf("%d",&size);
printf("Enter elements ");
for(i=0;i<size;i++)
{scanf("%d",&data[i]);}
insertion(size,data);
selection(size,data);
bubble(size,data);
getch();
}
void insertion(int s,int d[20])
{int i,temp,count;
for(i=1;i<s;i++)
{temp=d[i];
count=i-1;
while((temp<d[count])&&(count>=0))
{d[count+1]=d[count];
count=count-1;
}
d[count+1]=temp;
}
printf("\nInsertion Sort\n");display(s,d);
}
void selection(int s,int d[20])
{int i,small,posn,count,temp;
for(i=0;i<s-1;i++)
{small=d[i];
posn=i;
for(count=i+1;count<s;count++)
{if(small>d[count])
{posn=count;
small=d[count];
}
}
temp=d[i];
d[i]=d[posn];
d[posn]=temp;
}
printf("\nSelection Sort\n");display(s,d);
}
void bubble(int s,int d[20])
{int i,j,temp;
for(i=0;i<s;i++)
{for(j=0;j<s;j++)
if(d[j]>d[i])
{temp=d[i];
d[i]=d[j];
d[j]=temp;
}
}
printf("\nBubble Sort\n");display(s,d);
}
void display(int si,int d[20])
{int i,s=si;
printf("Sorted array is\t");
for(i=0;i<s;i++)
{printf("%d ",d[i]);}
}
/*OUTPUT
Enter the size of array 5
Enter elements 1 78 96 0 4Insertion Sort
Sorted array is 0 1 4 78 96
Selection Sort
Sorted array is 0 1 4 78 96
Bubble Sort
Sorted array is 0 1 4 78 96 Press anykey to continue */
Wednesday, November 21, 2007 10:13 AM -
Operations on a 2D Array
Code Block//Operations on a 2D Array
#include<stdio.h>
#include<conio.h> //Pre processor directives
#include<process.h>
void display(int d[20][20],int m,int n); //Functions
void trans(void);
void main() //Start of function main()
{int ch,r1,c1,r2,c2,i,j,k,a[20][20]={0},b[20][20]={0},c[20][20]={0};
do{printf("Press 1 to Multiply, 2 to Add,3 for Transpose, 0 to Exit ");
scanf("%d",&ch); //MENU
if(ch==0) exit(0); //Condition for exit
if(ch==3)
{trans(); //Function Call
break;
}
printf("Enter rows, columns(1st matrix) ");
scanf("%d %d",&r1,&c1);
printf("Enter matrix 1 elements ");
fflush(stdin); //Clears the buffer for next input
for(i=0;i<r1;i++)
{for(j=0;j<c1;j++)
{scanf("%d",&a[i][j]);} //Enter 2nd matrix
}
printf("Enter rows, columns(2nd matrix) ");
scanf("%d %d",&r2,&c2);
printf("Enter matrix 2 elements ");
fflush(stdin);
for(i=0;i<r2;i++)
{for(j=0;j<c2;j++)
{scanf("%d",&b[i][j]);} //Enter 2nd matrix
}
if(ch==1)
{if(c1!=r2) //Condition for no product
printf("Multiplication Not Possible!");
for(i=0;i<r1;i++)
{for(j=0;j<c2;j++) //Nested for loops for multiplication
{for(k=0;k<r2;k++)
{c[i][j]=c[i][j]+a[i][k]*b[k][j]; }
}
}
display(c,r1,c2); //Function Call
}
if(ch==2)
{if((r1!=r2)||(c1!=c2))
printf("No Addition Possible");
for(i=0;i<r1;i++)
{for(j=0;j<c1;j++)
{c[i][j]=a[i][j]+b[i][j]; }
}
display(c,r1,c1); //Function Call
}
} while(ch!=0); //End of do_while loop
getch(); //To stop the screen
} //End of function main()
void trans(void) //Function definition
{int i,j,m,n,temp,M[20][20]={0};
fflush(stdin); //Clears the buffer for next input
printf("Enter order m n ");
scanf("%d%d",&m,&n);
printf("Enter elements ");
for(i=0;i<m;i++)
{for(j=0;j<n;j++)
{scanf("%d",&M[i][j]);}
}
for(i=0;i<m;i++)
{for(j=i;j<n;j++)
{temp=M[i][j];
M[i][j]=M[j][i];
M[j][i]=temp;
}
}
display(M,m,n); //Function call
}
void display(int d[20][20],int m,int n) //Function definition
{int x=m,y=n,i,j;
for(i=0;i<x;i++)
{for(j=0;j<n;j++)
{printf("%d\t",d[i][j]);}
printf("\n");
}
}
/*OUTPUT
Press 1 to Multiply, 2 to Add,3 for Transpose, 0 to Exit 1
Enter rows, columns(1st matrix) 2 2
Enter matrix 1 elements 1 2 3 4
Enter rows, columns(2nd matrix) 2 1
Enter matrix 2 elements 1 2
5
11
Press 1 to Multiply, 2 to Add,3 for Transpose, 0 to Exit 2
Enter rows, columns(1st matrix) 2 2
Enter matrix 1 elements 1 2 3 4
Enter rows, columns(2nd matrix) 2 2
Enter matrix 2 elements 1 2 3 4
2 4
6 8
Press 1 to Multiply, 2 to Add,3 for Transpose, 0 to Exit 3
Enter order m n 2 2
Enter elements 1 2 3 4
1 3
2 4
Press any key to continue
*/Wednesday, November 21, 2007 10:14 AM -
Codes for string functions
Code Block//Codes for string functions
#include<iostream.h>
#include<conio.h> //Pre processor directive
#include<stdio.h>
#include<process.h>
int length();
void copy();
int cmp(); //Function prototypes
void cat();
int length() //Function definition
{char text[500]={" "}; //String initialization to NULL
int i=0;
cout<<"Enter Text:";
do{gets(text); //Enter the text
i++;
}
while(text[i]!='\0'); //Checking for NULL character
return(i);
}
void copy() //Function definition
{char txt[500]={" "},cpy[500]={" "}; //String initialization to NULL
cout<<"Enter text to copy ";
int i=0;
gets(txt); //Enter the text
do{ cpy[i]=txt[i];
i++;
}
while(txt[i]!='\0'); //Checking for NULL character
cout<<"Copied text "<<cpy;
}
int cmp() //Function definition
{char t1[500]={" "},t2[500]={" "}; //String initialization to NULL
cout<<"Enter 1st text ";
gets(t1); //Enter the text
cout<<"Enter 2nd text ";
gets(t2); //Enter the text
int i=0,flag=0;
while((t1[i]!='\0')||(t2[i]!='\0')) //Checking for NULL character
{ if(t1[i]!=t2[i])
{flag=1;}
i++;
}
return(flag); //Return the check condition
}
void cat() //Function definition
{char t1[500]={" "},t2[500]={" "},t[1000]={" "}; //String initialization to NULL
int i=0,j=0;
cout<<"Enter text 1 ";
gets(t1); //Enter the text
do{t[i]=t1[i];
i++;
}
while(t1[i]!='\0'); //Checking for NULL character
cout<<"\nEnter text 2 ";
gets(t2); //Enter the text
do{t[i]=t2[j];
i++;j++;
}
while(t2[j]!='\0'); //Checking for NULL character
cout<<"\n\tConcatenated text is "<<t;
}
void main() //main() function definition
{clrscr(); //To clear the screen
int l,ch;
do {cout<<"\nPress 1 for strlen() 2 for strcpy() 3 for strcmp() 4 for strcat() 0 to EXIT ";//MENU
cin>>ch;
if(ch==0) {exit(0);} //Condition for EXIT
if(ch==1)
{int l=length();
cout<<"Length is "<<l<<" characters including spaces";
}
if(ch==2) {copy();}
if(ch==3)
{int f=cmp();
if(f==1)
{cout<<"\tEntered Texts Do Not Match\n";}
else cout<<"\tEntered Texts Do Match\n";
}
if(ch==4) {cat();}
} //End of do_while loop
while((ch!=0)||(ch>4));
getch(); //To stop the screen
} //End of main()
/*
OUTPUT
Press 1 for strlen() 2 for strcpy() 3 for strcmp() 4 for strcat() 0 to EXIT 1
Enter Text:Vikram Jeet Singh^Z
Length is 17 characters including spaces
Press 1 for strlen() 2 for strcpy() 3 for strcmp() 4 for strcat() 0 to EXIT 2
Enter text to copy Vikram Jeet Singh
Copied text Vikram Jeet Singh
Press 1 for strlen() 2 for strcpy() 3 for strcmp() 4 for strcat() 0 to EXIT 3
Enter 1st text Vikram
Enter 2nd text Jeet Singh
Entered Texts Do Not Match
Press 1 for strlen() 2 for strcpy() 3 for strcmp() 4 for strcat() 0 to EXIT 4
Enter text 1 Vikram
Enter text 2 Jeet Singh
Concatenated text is Vikram Jeet Singh
Press 1 for strlen() 2 for strcpy() 3 for strcmp() 4 for strcat() 0 to EXIT */Wednesday, November 21, 2007 10:15 AM -
Swapping by using call by value & reference
Code Block//Swapping by using call by value & reference
#include<iostream.h>
#include<conio.h> //Pre processor directive
void value(int x,int y); //Function prototype for call_by_value
void ref(int *x,int *y); //Function prototype for call_by_reference
void main() //Start of main()
{int a=2,b=5; //Initialization
clrscr(); //To clear the screen
cout<<"Original values a:b::"<<a<<" "<<b;
value(a,b); //Function call
cout<<"\nValues in main after swapping by value a:b::"<<a<<" "<<b;
ref(&a,&b); //Function call
cout<<"\nValues in main after swapping by reference a:b::"<<a<<" "<<b;
getch(); //To hold the screen
} //End of main()
void value(int x,int y) //Function definition
{int temp;
temp=x;
x=y; //Inter-change of values
y=temp;
cout<<"\nValues in call_by_value function a:b::"<<x<<" "<<y;
}
void ref(int *x,int *y) //Function definition
{int temp;
temp=*x;
*x=*y; //Inter-change of values
*y=temp;
}
/*
OUTPUT
Original values a:b::2 5
Values in call_by_value function a:b::5 2
Values in main after swapping by value a:b::2 5
Values in main after swapping by reference a:b::5 2 */Wednesday, November 21, 2007 10:22 AM