Sorting

/* Program: sorting.c
 * ---------------------------------------------------------------------
 * This program implements and demonstrates several algorithms for
 * sorting arrays of integers.
 * ---------------------------------------------------------------------
 * Course: Data structures practical
* ---------------------------------------------------------------------
 */


/* Header files */

#include <stdio.h>


/* Selection sort */

void ssort (int a[], int n)
{
   int i, j;

   for (i = 0; i < n-1; i++) {
      int min = a[i], minj = i;

      for (j = i+1; j < n; j++)
         if (a[j] < min)
            min = a[minj = j];

      a[minj] = a[i];
      a[i] = min;
   }
}


/* Insertion sort */

void isort (int a[], int n)
{
   int i, j;

   for (i = 1; i < n; i++) {
      int x = a[i];

      for (j = i-1; j >= 0; j--)
         if (x < a[j])
            a[j+1] = a[j];
         else
            break;
         a[j+1] = x;
   }
}


/* Bubble sort */

void bsort (int a[], int n)
{
   int i, j;

   for (i = 0; i < n; i++)
      for (j = n-1; j > i; j--)
         if (a[j-1] > a[j]) {
            int temp = a[j-1];

            a[j-1] = a[j];
            a[j] = temp;
         }
}


/* Quick sort */

void qsort_auxil (int a[], int lower, int upper)
{
   if (lower < upper) {
      int x = a[(lower + upper) / 2];
      int i = lower, j = upper;

      for (i = lower, j = upper; i <= j; i++, j--) {
         while (a[i] < x) i++;
         while (a[j] > x) j--;

         if (i <= j) {
            int temp = a[i];

            a[i] = a[j];
            a[j] = temp;
         }
      }
      qsort_auxil(a, lower, j);
      qsort_auxil(a, i, upper);
   }
}

void qsort (int a[], int n)
{
   qsort_auxil(a, 0, n-1);
}


/* Main program -- for testing */

int test (int a[], int n)
{
   int i;

   for (i = 1; i < n; i++)
      if (a[i-1] > a[i]) {
         printf("\nERROR IN SORTING !!!\n\n");
         return 0;
      }
   return 1;
}


int main ()
{
   const int c[] = { 44, 55, 12, 42, 94, 18, 6, 67 };

#define n (sizeof(c) / sizeof(c[0]))

   int x[n];
   int i;

   printf("Original array:\n");
   for (i=0; i<n; i++) printf("%d ", c[i]); printf("\n");

   printf("\nSelection sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   ssort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   printf("\nInsertion sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   isort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   printf("\nBubble sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   bsort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   printf("\nQuick sort:\n");
   for (i=0; i<n; i++) x[i] = c[i];
   qsort(x, n);
   for (i=0; i<n; i++) printf("%d ", x[i]); printf("\n");
   test(x, n);

   return 0;
}

tree 1

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<alloc.h>
#include<dos.h>

enum bool{true,false};
typedef struct TreeNode* link;

struct TreeNode {

int item;      // The data in this node.
link left;    // Pointer to left subtree.
link right;   // Pointer to right subtree.



      };


struct BinaryTree{

   link root;


    };
void initTree(link &troot)
{
troot=NULL;
}

void treeInsert(link &troot,int newItem) {

if(troot==NULL){
 link temp;
temp=(TreeNode*)malloc(sizeof(TreeNode));
 temp->item=newItem;
 temp->left=NULL;
  temp->right=NULL;
  troot=temp;
 return;
     }

 else if ( newItem <troot->item ) {
    treeInsert( troot->left, newItem );
 }
 else {
    treeInsert( troot->right, newItem );
 }

       }

void preordertraverse( link troot ) {

if ( troot != NULL ) {
  cout << troot->item << " ";      // Print the root item.
  preordertraverse( troot->left );    // Print items in left subtree.
  preordertraverse( troot->right );   // Print items in right subtree.
   }
     }

void postordertraverse( link troot ) {

if ( troot != NULL ) {
  postordertraverse( troot->left );    // Print items in left subtree.
  postordertraverse( troot->right );   // Print items in right subtree.
  cout << troot->item << " ";       // Print the root item.
}
     }

void inordertraverse( link troot ) {

if ( troot != NULL ) {
 inordertraverse( troot->left );    // Print items in left subtree.
  cout << troot->item << " ";     // Print the root item.
  inordertraverse( troot->right );   // Print items in right subtree.
}
     }

bool treeContains( link troot, int item ) {

    if ( troot == NULL ) {
  // Tree is empty, so it certainly doesn't contain item.
return false;
    }
    else if ( item == troot->item ) {
  // Yes, the item has been found in the root node.
return true;
    }
    else if ( item < troot->item ) {
  // If the item occurs, it must be in the left subtree.
return treeContains( troot->left, item );
    }
    else {
  // If the item occurs, it must be in the right subtree.
return treeContains( troot->right, item );
    }
 }

void main(){
    clrscr();
      BinaryTree *bt;
      initTree(bt->root);

     treeInsert(bt->root,100);

      treeInsert(bt->root,90);
      treeInsert(bt->root,120);
      treeInsert(bt->root,70);
      treeInsert(bt->root,95);
      treeInsert(bt->root,130);
      cout<<"inserted items : 100 90 120 70 95 130\n\n";

      cout<<"Inorder traverse : \n\n";
   inordertraverse(bt->root);
   cout<<"\n\n";
   cout<<"post order traverse : \n\n";
   postordertraverse(bt->root);
   cout<<endl<<endl;
   cout<<"preorder traverse :\n\n";
   preordertraverse(bt->root);
   cout<<endl;
   getch();

 }

link list

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<stdio.h>
#include<dos.h>
#include<string.h>
#define INTERVAL 100

typedef struct node* link;
typedef int itemType;


struct node {
  itemType item;
  link next;
  };


typedef struct list {
link head, tail;
     };

//functions signatures.

  void initList(list*);
  link newNode(itemType);
  void insertFront(list*, link);
  void insertRear(list*, link);
  void insertNext(list*,itemType,link);
  void deleteNode(list*, itemType);
  void printList(list*);

  //main program which make use of list processing interface.

void main(){
  clrscr();
  list* l;
  link temp1,temp2;
  initList(l);
  temp1=newNode(12);
  insertFront(l,temp1);
   printList(l);

   temp2=newNode(20);
   insertRear(l,temp2);
   printList(l);
   temp2=newNode(30);
   insertRear(l,temp2);
   printList(l);
   temp2=newNode(50);
   insertRear(l,temp2);
   printList(l);
   temp2=newNode(45);
   insertNext(l,12,temp2);
   printList(l);

   deleteNode(l,45);
   printList(l);
   getch();


   // finalising....freeing used memory..
   delete l;
   clrscr();
   cout<<"Memory released....press any key...";
   getch();

}



// method list are implemented below.

void initList(list *l)
   {
l->head = l->tail=NULL;
    }

link newNode(itemType d)
   {
link temp;
itemType t;
temp =(link)malloc(sizeof(node));
//temp =(link)malloc(sizeof(link));
temp->item = d;
temp->next = NULL;
return temp;
   }

void insertFront(list *l, link t)
{
if (l->head==NULL)
{l->head = l->tail=t;}
else {
t->next = l->head;
l->head=t;
}
}

void insertRear(list* l, link t)
{
if (l->head==NULL)
l->head = l->tail= t;
else {
l->tail->next=t;
l->tail= t;
       }
}

void insertNext(list *l, itemType x, link t)
{
link temp;
int found=0;

if (l->head==NULL)
l->head = l->tail= t;
else{
temp=l->head;
while(temp !=NULL && (!found))
{
if (temp->item==x)
found =1;

else{
temp=temp->next;
found =0;
}
}
if(found)
{
t->next = temp->next;
temp->next=t;
}
else {
t->next=l->head;
l->head = t;
}
  }
}


void deleteNode(list* l, itemType d)
{
link temp1, temp2;
int found=0;
temp1 = l->head;
temp2 =temp1;

while((!found) && (temp1!= NULL))
{


if((temp1->item)==d){
found =1;
break;
}
else
{
temp2=temp1;
temp1=temp1->next;
}
}
if(found)
{
if(temp2 == temp1){
l->head=temp2->next;

}
else  {
temp2->next=temp1->next;

}
 delete temp1;
 cout<<"Succesfully deleted..."<<endl;
     }
else
cout<<"The node does not exists.."<<endl;
}

void printList(list *l)
{
link temp;
temp=l->head;
while(temp !=NULL)
{       delay(INTERVAL);
cout<< temp->item<<"\t"; /*display must be defined according to the itemType*/
temp=temp->next;
}
cout<<endl;
}