# 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;
};

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);
}
}
}
void count(struct node *q)
{int c=0;
while(q!=NULL)
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++)
if(temp==NULL)
{printf("\nThere are less than %d elements",pos);
return;
}
r=(struct node*)malloc(sizeof(struct node));
r->data=num;
}
void insertatbeg(struct node **q,int num)
{struct node *temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data = num;
*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)
free(temp);
return;
}
else
free(temp);
return;
}
}
else
{old=temp;
}
}
}
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;
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);
if(*l==NULL)
*l=temp;
else
{p=*l;
}
}/*
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 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  3
Enter Element 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  2

Enter 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  5

Number 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  4

Elements 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  7

Enter 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  6

Enter 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  4

Elements 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);
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 of

array ");
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 4

Insertion 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 any

key 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 ");
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))
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