Wednesday 13 February 2013

Important Programs in C




Program to implement circular queue 

#include <stdio.h>
#include <conio.h>
#define  QSIZE  5

struct Queue
{
int item[QSIZE];
int front, rear;
};

int empty( struct Queue *q )
{
if( q->front == q->rear )
return( 1 );
return(0);
}

void insert( struct Queue *q, int x )
{
int temp;
temp = q->rear;
q->rear = ( q->rear + 1 ) % QSIZE;

if( q->rear == q->front )
{
printf("\nThe queue is full.");
q->rear = temp;
}
else
q->item[ q->rear] = x;
}

int del( struct Queue *q )
{
if( empty(q) )
{
printf("\nThe queue is empty.");
return( -9999 );
}

q->front = ( q->front + 1 ) % QSIZE;
return( q->item[ q->front ] );
}

void operation()
{
struct Queue *q;
char c;
int x, value;

q = ( struct Queue * ) malloc( sizeof( struct Queue ) );

do
{
printf("\n\nMain Menu:\n"
   "    1. Empty,\n"
   "    2. Insert,\n"
   "    3. Delete,\n"
   "    4. Display,\n"
   "    5. Exit.\n"
   "Enter your choice: ");
c = getche();

switch( c )
{
case '1':
if( empty(q) )
printf("\nThe queue is empty.");
else
printf("\nThe queue is not empty.");
break;

case '2':
printf("\nEnter the item to insert: ");
scanf("%d",&x);
insert( q, x );
break;

case '3':
if( ( value = del( q ) ) != -9999 )
printf("The deleted item: %d",value );
break;
}
}
while( c != '5' );
}

void main()
{
clrscr();
operation();
}

...................................................................................................................................
Program To implement FourLink

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

struct Node
{
int item;
struct Node *next;
};

typedef struct Node *Nodeptr;

Nodeptr getnode()
{
return( (Nodeptr) malloc( sizeof( struct Node ) ) );
}

Nodeptr create( int x )
{
Nodeptr temp;
temp = getnode();
if( temp == NULL )
{
printf("The memory is full.\n");
}
else
{
temp->item = x;
temp->next = NULL;
}
return( temp );
}

Nodeptr insert(  Nodeptr p, int x )
{
Nodeptr temp;

temp = getnode();
temp->item = x;
temp->next = NULL;

p->next = temp;
return( temp );
}

Nodeptr dividing( Nodeptr list, int x )
{
Nodeptr l, p, temp;
l = NULL;
while( list != NULL )
{
if( list->item == x )
{
if( l == NULL )
{
l = getnode();
l->item = list->item;
temp = l;
}
else
{
p = getnode();
p->item = list->item;
l->next = p;
l = p;
}
x = x + 4;
}
list = list->next;
}
l->next = NULL;
return( temp );
}

void display( Nodeptr temp )
{
if( temp != NULL )
{
printf("%d -> ",temp->item );
display( temp->next );
}
else
{
printf("END.\n");
}
}

void main()
{
Nodeptr list, temp, L[4];
int i, x;

clrscr();

printf("Creating the Main Linked List:-\n"
   "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"
   "Enter the numbers to insert ( at end type -999 ):  ");
scanf("%d",&x);
list = create( x );
temp = list;
while( 1 )
{
scanf("%d",&x);
if( x == -999 )
break;
temp = insert( temp, x );
}

   for( i = 0; i < 4; i++ )
{
L[i] = dividing( list, i + 1 );
printf("\nDisplaying the linked list L[%d]:-\n"
   "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"
   "The linked list: ", i + 1);
display( L[i] );
}

printf("\nDisplaying the main linked list:-"
   "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
   "\nThe linked list: ");
display( list );

getch();
}

..................................................................................................................................
Program To implement Heap Sort

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

void buildheap( int a[], int n )
{
int i, s, f, elt;

for( i = 1; i < n; i++ )
{
elt = a[i];
s = i;
f = ( s - 1 ) / 2;

while( s > 0 && a[f] < elt )
{
a[s] = a[f];
s = f;
f = ( s - 1 ) / 2;
}

a[s] = elt;
}
}

void heapsort( int a[], int n )
{
int i, s, f, ivalue;
buildheap( a, n );

for( i = n - 1; i > 0; i-- )
{
ivalue = a[i];
a[i] = a[0];
f = 0;

if( i == 1 )
s = -1;
else
s = 1;

if( a[s] < a[s+1] && i > 2 )
s = 2;

while( s >= 0 && ivalue < a[s] )
{
a[f] = a[s];
f = s;
s = f * 2 + 1;

if( s + 1 <= i - 1 && a[s] < a[s+1] )
s = s + 1;

if( s > i - 1 )
s = -1;
}

a[f] = ivalue;
}
}

void main()
{
int *item, n, i;

clrscr();
printf("Enter total number of items: ");
scanf("%d",&n);

item = ( int * ) malloc( n * sizeof( int ) );

printf("Enter the items: ");
for( i = 0; i < n; i++ )
scanf("%d", (item+i) );

heapsort( item, n );

printf("\nThe sorted list => ");
for( i = 0; i < n; i++ )
printf("%d ", *(item+i) );

getch();
}
................................................................................................................................

Implementation Of HuffMan Coding

 #include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define  SIZE  10

struct Node
{
int info;
struct Node *father, *left, *right;
};

typedef struct Node *Nodeptr;

struct Pqueue
{
Nodeptr item[SIZE];
int front, rear;
};


int empty( struct Pqueue *pq )
{
if( pq->front == pq->rear )
return 1;
else
return 0;
}

void pqinsert( struct Pqueue *pq, Nodeptr x )
{
if( pq->rear == SIZE - 1 )
printf("The queue is full.");
else
pq->item[++pq->rear] = x;
}

Nodeptr pqmindel( struct Pqueue *pq )
{
int i, index;
Nodeptr min;

if( empty( pq ) )
{
printf("UNDERFLOW. The queue is empty.");
getch();
exit( 1 );
}

min = pq->item[0];
index = 0;

for( i = 1; i <= pq->rear; i++ )
if( ( pq->item[i] )->info < min->info )
{
min = pq->item[i];
index = i;
}

for( i = index; i < pq->rear; i++ )
pq->item[i] = pq->item[i+1];

pq->rear--;

return( min );
}

Nodeptr getnode()
{
return( ( Nodeptr ) malloc( sizeof ( struct Node ) ) );
}

Nodeptr maketree( int a )
{
Nodeptr temp;
temp = getnode();
temp->info = a;
temp->father = temp->left = temp->right = NULL;
return( temp );
}

void setleft( Nodeptr p, Nodeptr x )
{
if( p == NULL )
printf("Inavlid insertion.");
else if( p->left != NULL )
printf("Left node already present.");
else
{
p->left =  x ;
x->father = p;
}
}

void setright( Nodeptr p, Nodeptr x )
{
if( p == NULL )
printf("Inavlid insertion.");
else if( p->right != NULL )
printf("Right node already present.");
else
{
p->right = x;
x->father = p;
}
}

int isleft( Nodeptr p )
{
if( ( p->father )->left == p )
return( 1 );
else
return( 0 );
}


void huffmantree( int frcq[], int n )
{
struct Pqueue *root;
Nodeptr tree, p, p1, p2, pos[SIZE];
char code[20][15], temp[15];
int i, j, k;

root->rear = root->front = -1;
for( i = 0; i < n; i++ )
{
p = maketree( frcq[i] );
pos[i] = p;
pqinsert( root, p );
}

while( root->rear > 0  )
{
p1 = pqmindel( root );
p2 = pqmindel( root );

p = maketree( p1->info + p2->info );

setleft( p, p1 );
setright( p, p2 );

pqinsert( root, p );
}

tree = pqmindel( root );

for( i = 0; i < n; i++ )
{
j = 0;
p = pos[i];
code[i][j] = '\0';

while( p != tree )
{
if( isleft( p ) )
code[i][++j] = '0';
else
code[i][++j] = '1';

p = p->father;
}

for( k = 0; j >= 0; k++, j-- )
temp[k] = code[i][j];

strcpy( code[i], temp );
}

for( i = 0; i < n; i++ )
printf("\nCode of frequency %d => %s",frcq[i],code[i]);
}

void main()
{
int *frcq, i, n;

printf("Enter total number of frequencies: ");
scanf("%d",&n);

frcq = ( int * ) malloc( n * sizeof( int ) );

printf("Enter the frequencies: ");
for( i = 0; i < n; i++ )
scanf("%d",(frcq+i));


huffmantree( frcq, n );

getch();
}



0 comments:

Post a Comment