Remove From My Forums

Data Structures & Algorithms

General discussion
0

Sign in to vote

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

0

Sign in to vote

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
0

Sign in to vote

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
0

Sign in to vote

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

Sign in to vote

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
0

Sign in to vote

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
0

Sign in to vote

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
0

Sign in to vote

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
0

Sign in to vote

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

Asked by:

Data Structures & Algorithms

General discussion

All replies