locked
Data Structures & Algorithms RRS feed

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