heap sort

#include <stdio.h>

void main()

{

    int heap[10], no, i, j, c, root, temp;

    printf("\n Enter no of elements :");

    scanf("%d", &no);

    printf("\n Enter the nos : ");

    for (i = 0; i < no; i++)

       scanf("%d", &heap[i]);

    for (i = 1; i < no; i++)

    {

        c = i;

        do

        {

            root = (c - 1) / 2;            

            if (heap[root] < heap[c])   /* to create MAX heap array */

            {

                temp = heap[root];

                heap[root] = heap[c];

                heap[c] = temp;

            }

            c = root;

        } while (c != 0);

    }

    printf("Heap array : ");

    for (i = 0; i < no; i++)

        printf("%d\t ", heap[i]);

    for (j = no - 1; j >= 0; j--)

    {

        temp = heap[0];

        heap[0] = heap[j];    /* swap max element with rightmost leaf element */

        heap[j] = temp;

        root = 0;

        do

        {

            c = 2 * root + 1;    /* left node of root element */

            if ((heap[c] < heap[c + 1]) && c < j-1)

                c++;

            if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */

            {

                temp = heap[root];

                heap[root] = heap[c];

                heap[c] = temp;

            }

            root = c;

        } while (c < j);

    }

    printf("\n The sorted array is : ");

    for (i = 0; i < no; i++)

       printf("\t %d", heap[i]);

    printf("\n Complexity : \n Best case = Avg case = Worst case = O(n logn) \n");

}

program for implement hashing.

#include<stdio.h>

#include<conio.h>

void main()

{

int a[10]={1,2,3,4,5,6,7,8,9,10};

int n,value;

int temp, hash;

printf("\nEnter the value of n(table size):");

scanf("%d",&n);

do

{

printf("\nEnter the hash value");

scanf("%d",&value);

hash=value%n;

if(a[hash]==0)

{

a[hash]=value;

printf("\na[%d]the value %d is stored",hash,value);

}

else

{

for(hash++;hash<n;hash++)

{

if(a[hash]==0)

{

printf("Space is allocated give other value");

a[hash]=value;

printf("\n a[%d]the value %d is stored",hash,value);

goto newentry;

}

}

hash=0;

for(hash;hash<n;hash++)

{

if(a[hash]==0)

{

printf("Space is allocated give other value");

a[hash]=value;

printf("\n a[%d]the value %d is stored",hash,value);

goto newentry;

}

}

printf("ERROR");

}

newentry:

printf("\n Do u want enter more");

scanf("%d",&temp);

}

while(temp==1);

getch();

}

program to create a doubly circular linked list.

#include<stdio.h>

#include<conio.h>

struct circular

{

    int i;

    struct circular *front;

    struct circular *back;

};

int cnt=0;

struct circular *temp;

struct circular *head;

struct circular *p;

struct circular *mid;

struct circular *move;

void create(void);

void insert(void);

void display(void);

void del(void);

void main()

{

    int ch=0;

    while(ch!=5)

    {

        printf("\n1.CREATE");

        printf("\n2.INSERT");

        printf("\n3.DELETE");

        printf("\n4.DISPLAY");

        printf("\n5.EXIT");

        printf("\nEnter your choice=");

        scanf("%d",&ch);

if(ch==1)

        {

            create();

            cnt++;

            cnt++;

        }

if(ch==2)

        {

            insert();

            cnt++;

        }

if(ch==3)

        {

            del();

            cnt--;

        }

if(ch==4)

        {

            display();

        }

if(ch==5)

        {

            break;

        }

    }

    getch();

}

void create()

{

    head=(struct circular *)malloc(sizeof(struct circular));

    head->back=head;

    head->front=head;

printf("\nENTER THE DATA");

    scanf("%d",&head->i);

    temp=head;

temp->back=(struct circular *)malloc(sizeof(struct circular));

    temp=temp->back;

    temp->back=head;

    head->front=temp;

printf("\nENETER THE DATA");

    scanf("%d",&temp->i);

}

void insert()

{

    int add,t;

      printf("\n\t ENTER ANY NUMBER=");

    scanf("%d",&add);

    p=head;

    t=1;

    while(t<add)

    {

        p=p->back;

        t++;

    }

    mid=(struct circular *)malloc(sizeof(struct circular));

    printf("\n\n\nENTER THE DATA");

    scanf("%d",&mid->i);

      mid->back=p->back;

    p->back=mid;

    p->back->front=mid;

    mid->front=p;

}

void display()

{

    p=head;

    printf("\n%d-->",p->i);

    p=p->back;

    while(p!=head)

    {

        printf("\t%d-->",p->i);

        p=p->back;

    }

}

void del(void)

{

    int add,t;

      printf("\n\n\t ENTER ANY NUMBER");

    scanf("%d",&add);

    p=head;

    t=1;

    while(t<add-1)

    {

        p=p->back;

        t++;

    }

    mid=p->back;

    p->back=mid->back;

    mid->back->front=p;

    free(mid);

}

dijkstra algo

  #include <stdio.h>

  #include <stdlib.h>

  #define INFINITY 9999

  int main() {

        int vertexCount, **edgeLength, **res;

        int i, j, k;

        printf("Enter the no of vertices:");

        scanf("%d", &vertexCount);

        edgeLength = (int **)calloc(sizeof(int),  vertexCount);

        res = (int **)calloc(sizeof(int), vertexCount);

        for (i = 0; i < vertexCount; i++) {

                edgeLength[i] = (int *)calloc(sizeof(int),  vertexCount);

                res[i] = (int *)calloc(sizeof(int), vertexCount);

        }

        /* Adjacency Matrix to store Cost of the edges */

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        printf("Edge weight %d to %d(0 if no edge):", i + 1, j + 1);

                        scanf("%d", &edgeLength[i][j]);

                        if (edgeLength[i][j] == 0) {

                                res[i][j] = INFINITY;

                        } else {

                                res[i][j] = edgeLength[i][j];

                        }

                }

        }

        printf("Adjacent matrix for edge weights:\n");

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        printf("%3d", edgeLength[i][j]);

                }

                printf("\n");

        }

        /* Calculate shortest path from each vertex to every other vertices */

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        for (k = 0; k < vertexCount; k++) {

                                if (res[j][k] > res[j][i] + res[i][k]) {

                                        res[j][k] = res[j][i] + res[i][k];

                                }

                        }

                }

        }

        printf("\nShortest path between vertices\n");

        for (i = 0; i < vertexCount; i++) {

                for (j = 0; j < vertexCount; j++) {

                        if (res[i][j] == INFINITY)

                                printf("%3d", 0);

                        else

                                printf("%3d", res[i][j]);

                }

                printf("\n");

        }

        return 0;

  }

dfs using matrix

#include<stdio.h>

#include<conio.h>

void DFS(int);

int G[10][10],visited[10],n;

void main()

{

      int i,j;

      printf("Enter no, of nodes=");

      scanf("%d",&n);

      printf("\nEnter adjacency matrix of the graph=");

      for(i=0;i<n;i++)

      for(j=0;j<n;j++)

      scanf("%d",&G[i][j]);

      for(i=0;i<n;i++)

      visited[i]=0;

      DFS(0);

      getch();

}

void DFS(int i)

{

      int j;

      printf("\n%d",i);

      visited[i]=1;

      for(j=0;j<n;j++)

            if(!visited[j]&&G[i][j]==1)

            DFS(j);

}

dfs using list

#include<stdio.h>

#include<conio.h>

typedef struct node

{

      struct node *next;

      int vertex;

}node;

node *G[20];

int visited[20];

int n;

void readgraph();

void insert(int,int);

void DFS(int);

void main()

{

      int i;

      readgraph();

      for(i=0;i<n;i++)

      visited[i]=0;

      DFS(0);

      getch();

}

void DFS(int i)

{

      node *p;

      printf("\n%d",i);

      p=G[i];

      visited[i]=1;

      while(p!=NULL)

      {

            i=p->vertex;

            if(!visited[i])

            DFS(i);

            p=p->next;

      }

}

void readgraph()

{

      int i,vi,vj,no;

      printf("\nEnter no. of vertices");

      scanf("%d",&n);

      for(i=0;i<n;i++)

      {

            G[i]=NULL;

            printf("\nEnter no. of edges");

            scanf("%d",&no);

            for(i=0;i<no;i++)

            {

                  printf("\nEnter an edge(u,v):");

                  scanf("%d%d",&vi,&vj);

                  insert(vi,vj);

            }

      }

}

void insert(int vi,int vj)

{

      node *p,*q;

      q=(node *)malloc(sizeof(node));

      q->vertex=vj;

      q->next=NULL;

      if(G[vi]==NULL)

      G[vi]=q;

      else

      {

            p=G[vi];

            while(p->next!=NULL)

            p=p->next;

            p->next=q;

      }

}

program for dequeue

#include<stdio.h>

#include<conio.h>

#define MAX 50

struct queue

{

      int a[MAX];

      int rear,front;

}

st;

void enqueuefront(int x);

void enqueuerear(int x);

void dequeuefront();

void dequeuerear();

void display();

void main()

{

      int op,x;

      st.rear=st.front=-1;

      do

      {

            printf("\n1.Insertion from rear\n2.Insertion from front\n3.Deletion from rear\n4.Deletion from front\n5.Print\n6.Exit");

            printf("\nEnter choice");

            scanf("^D",&op);

            switch(op)

            {

                  case 1:if((st.rear+1)%MAX==st.front)

                  printf("\nFull queue");

                  else

                  enqueuerear(x);

                  break;

                  case 2:if((st.rear+1)%MAX==st.front)

                  printf("\nFull queue");

                  else

                  enqueuefront(x);

                  break;

                  case 3:if(st.rear==-1)

                  printf("\nEmpty queue");

                  else

                  {

                        dequeuerear();

                  }

                  break;

                  case 4:if(st.front==-1)

                  printf("\nEmpty queue");

                  else

                  {

                        dequeuefront();

                  }

                  break;

                  case 5:display();

                  break;

            }

      }while(op!=6);

      getch();

}

void enqueuerear(int x)

{

      printf("\nEnter data:");

      scanf("%d",&x);

      if(st.rear==-1&&st.front==-1)

      {

            st.rear=0;st.front=0;

            st.a[0]=x;

      }

      else

      {

            st.rear=(st.rear+1)%MAX;

            st.a[st.rear]=x;

      }

}

void enqueuefront(int x)

{

      printf("\nEnter data:");

      scanf("%d",&x);

      if(st.rear==-1&&st.front==-1)

      {

            st.rear=0;st.front=0;

            st.a[0]=x;

      }

      else

      {

            st.front=(st.front-1+MAX)%MAX;

            st.a[st.front]=x;

      }

}

void dequeuerear()

{

      int y;

      if(st.rear==st.front)

      {

            y=st.a[st.rear];

            st.front=-1;

            st.rear=-1;

      }

      else

      {

            y=st.a[st.rear];

            st.rear=(st.rear-1+MAX)%MAX;

      }

            printf("\nDeleted element=%d",y);

      }

void dequeuefront()

{

      int y;

      if(st.rear==st.front)

      {

            y=st.a[st.front];

            st.front=-1;

            st.rear=-1;

      }

      else

      {

            y=st.a[st.front];

            st.front=(st.front+1)%MAX;

      }

            printf("\nDeleted element=%d",y);

      }

void display()

{

      int i;

      if(st.rear==-1&&st.front==-1)

      printf("\nEmpty queue");

      else

      {

            printf("\nQueue is:");

            i=st.front;

            while(i!=st.rear)

            {

                  printf("<%d>",st.a[i]);

                  i=(i+1)%MAX;

            }

            printf("<%d>",st.a[st.rear]);

      }

}