You cannot copy content of this page.

Monthly Archive October 2012

Program to implement Linear Queues using Linked List

Queues

Program to implement Linear Queues using Linked List

/*Implementation of Linear Queues using Linked List*/

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

typedef struct queue
{int info;
struct queue *next;
}queue;

queue *create()
{queue *temp=(queue *)malloc(sizeof(queue));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

queue *makenode(int x)
{queue *temp=create();
temp->info=x;
temp->next=NULL;
return temp;
}

/*Enqueue operation requires traversing the entire
queue for inserting a new node.*/

queue *enqueue(queue *front,int x)
{
queue *temp,*ptr=makenode(x);
if(front==NULL)
{front=ptr;
return front;
}
/*entire queue is traversed to insert at end*/
for(temp=front;temp->next!=NULL;temp=temp->next);
temp->next=ptr;
return front;
}

queue *dequeue(queue *front)
{
queue *temp=front;
if(front==NULL)
{printf(“nQueue Underflow!”);
exit(1);
}
/*the following assignment directly operates upon front
pointer by making it point to the next node and deleting
the first node*/
front=front->next;
free(temp);
return front;
}

void display(queue *front)
{queue *temp=front;
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
queue *front=NULL,*rear=NULL;
int num,ch;
while(1)
{
clrscr();
printf(“nMenu”);
printf(“nn1. Enqueue”);
printf(“n2. Dequeue”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“nEnter an element?”);
scanf(“%d”,&num);
front = enqueue(front,num);
break;
case 2: printf(“Removing front element from the queue…!”);
front=dequeue(front);
break;
case 3: display(front);
break;
case 4: exit(0);
default:printf(“nInvalid choice…!”);
}
getch();
}
}

 

Tags,

Program to implement a Queue using Array by incrementing front as well as rear

Queues

Program to implement a Queue using Array by incrementing front as well as rear

/*Implementation of Linear queues using arrays*/
/*Queue implementation by shifting front as well as rear*/

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

#define MAX 4

typedef struct queue
{int front, rear;
int arr[MAX];
}queue;

/*Enqueue will increment rear by one and add new element
at this subscript*/

void enqueue(queue *q, int x)
{if(q->rear==MAX-1)
{printf(“nQueue Overflow!”);
exit(1);
}
q->arr[++q->rear]=x;
}
/*Dequeue operation increments front by 1.
Linear queues are not considered efficient since
such an approach may result in an overflow, even if
empty blocks are available at beginning. To remove
this deficiency circular queues may be considered*/

int dequeue(queue *q)
{
int i,no;
if((q->rear==-1)&&(q->front>q->rear))
{printf(“nQueue Underflow!”);
exit(1);
}
return (q->arr[q->front++]);
}

void display(queue *q)
{int i;
for(i=q->front;i<=q->rear;i++)
printf(“%dt”,q->arr[i]);
}

void main()
{
int ch,num;
queue q;
q.front=0;
q.rear=-1;
while(1)
{
clrscr();
printf(“nMenu”);
printf(“nn1. Enqueue”);
printf(“n2. Dequeue”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number?”);
scanf(“%d”,&num);
enqueue(&q,num);
break;
case 2:
num=dequeue(&q);
printf(“nElement removed from the queue is %d”,num);
break;
case 3:
display(&q);
break;
case 4:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}

 

Tags,

Program to implement a Queue using Array with front always at zero

Queues

Program to implement a Queue using Array with front always at zero

/*Implementation of queues using arrays*/
/*Queue implementation with front always at zero*/

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

#define MAX 10

typedef struct queue
{int front, rear;
int arr[MAX];
}queue;

/*Enqueue will increment rear by one and add new element
at this subscript*/

void enqueue(queue *q, int x)
{if(q->rear==MAX-1)
{printf(“Queue Overflow!”);
exit(1);
}
q->arr[++q->rear]=x;
}

/*Front is always kept at zero.
Deletion involves shifting of elements to the left by one
position and rear gets decremented by one*/

int dequeue(queue *q)
{
int i,no;
if(q->rear<q->front)
{printf(“Queue Underflow!”);
exit(1);
}
no=q->arr[q->front];
/*fixed front at zero results in shifting of elements*/
for(i=q->front;i<q->rear;i++)
q->arr[i]=q->arr[i+1];
q->arr[q->rear]=0;
q->rear–;
return no;
}

void display(queue *q)
{int i;
for(i=q->front;i<=q->rear;i++)
printf(“%dt”,q->arr[i]);
}

void main()
{
int ch,num;
queue q;
q.front=0;
q.rear=-1;
while(1)
{
clrscr();
printf(“nMenu”);
printf(“nn1. Enqueue”);
printf(“n2. Dequeue”);
printf(“n3. Display”);
printf(“n4. Exit”);
printf(“nnEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number?”);
scanf(“%d”,&num);
enqueue(&q,num);
break;
case 2:
num=dequeue(&q);
printf(“nElement removed from the queue is %d”,num);
break;
case 3:
display(&q);
break;
case 4:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}

 

Tags,

Queues

  • Queues
    • Introduction
    • Representation
    • Operations
    • Implementation
      • Simple queue
      • With front always at zero
      • Linked queue
      • Dequeue
      • Priority Queues
        • Max Priority
        • Min Priority

Queues

A queue is a FIFO structure – First In First Out.  A queue is a data structure in which insertion of a new element is done at the rear end and deletion of an element is done at the front end of the queue.  Hence, it is different from the stack, since it uses both the ends to perform insertion and deletion rather than using only one end for these operations.  The operations on queue are similar to those of stack.  Enqueue operation represents insertion of a new element in the queue and Dequeue operation represents deletion of an element from the queue.

Representation:

Queue may be represented using arrays or linked list.  Array representation involves keeping track of two positions via. subscript for front and rear, whereas linked list involves two pointers, one positioned at the front end of the queue and the other positioned at the rear end of the queue.

i)  Array representation of queue:  Queues may be representated using arrays as follows:


ii) Linked list implementation of queueLinked list may also be used to represent a queue as follows:


Double Ended Queues (Dequeue):

A double ended queue allows fast insertion and deletion at the beginning as well as at the end of the queue.  It supports all the operations applicable for an ordinary queue.  But, enqueue may be done at front end too and dequeue may be done at rear end.

Priority Queues:

In a priority queue, the elements are dequeued according to their priority and their current queue position.  Priority may be assigned to elements such that dequeue operation may be based on priority.  Thus, it is not necessary in a priority queue, that the element at the front position is the candidate for deletion.  Priorities may be assigned such that higher priorities may be associated with lower numbers and lower priorities may be associated with higher numbers or vice-versa.   The elements may be arranged at the time of entry or using some ordering function.  Two versions of priority queues may be implemented in general.  First one is Max priority queue and the second one is Min priority queue.

i)  Max Priority Queue:

In a max priority queue, each element is assigned a priority.  The element to be dequeued is the element with the max priority.  The elements are extracted in the descending order of priority.  The program to implement max priority queue is as follows-

ii) Min Priority Queue:

In a min priority queue, each element is assigned a priority.  The element to be dequeued is the element with the min priority.  The elements are extracted in the ascending order of priority.  The program to implement min priority queue is as follows-


Tags,

Program to compute power of a given number x raised to y



Recursion

Program to compute power of a given number x raised to y

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

int power(int x,int n)
{
if(n==0)
return 1;
else
return(x * power(x,n-1));
}



void main()
{
int x,n,res;
clrscr();
printf(“nEnter base?”);
scanf(“%d”,&x);
printf(“nEnter exponent?”);
scanf(“%d”,&n);
res=power(x,n);
printf(“Power of %d raised to %d is %d”,x,n,res);
getch();
}


Tags,

Program to compute GCD of given two numbers x and y



Recursion

Program to compute GCD of given two numbers x and y

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

/*Recursive function to compute GCD*/
int GCD(int x,int y)
{
if(y==0)
return x;
else if(x<y)
return GCD(y,x);
else
return GCD(y,x%y);
}



void main()
{
int x,y,res;
clrscr();
printf(“nEnter first number?”);
scanf(“%d”,&x);
printf(“nEnter second number?”);
scanf(“%d”,&y);
res=GCD(x,y);
printf(“nGCD of %d and %d is %d”,x,y,res);
getch();
}



Tags,

Program to solve Towers of Hanoi problem



Recursion

Program to solve Towers of Hanoi problem

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

void hanoi(int num_disks,char *src,char *tmp,char *trgt);

void main()
{
int disks;
char source[10],temp[10],target[10];
clrscr();
printf(“nEnter total number of disks?”);
scanf(“%d”,&disks);
printf(“nEnter source pillar?”);
scanf(“%s”,source);
printf(“nEnter intermediate pillar?”);
scanf(“%s”,temp);
printf(“nEnter target pillar?”);
scanf(“%s”,target);
hanoi(disks,source,temp,target);
getch();
}



void hanoi(int num_disks,char *src,char *tmp,char *trgt)
{
if(num_disks==1)
{printf(“nMove disk from %s to %s”,src,trgt);
}
else
{
hanoi(num_disks-1,src,trgt,tmp);
printf(“nMove disk from %s to %s”,src,trgt);
hanoi(num_disks-1,tmp,src,trgt);
}
}



Output:

Enter total number of disks?3

Enter source pillar?First

Enter intermediate pillar?Second

Enter target pillar?Third

Move disk from First to Third
Move disk from First to Second
Move disk from Third to Second
Move disk from First to Third
Move disk from Second to First
Move disk from Second to Third
Move disk from First to Third



Tags,

Program to compute factorial of a given number



Recursion

Program to compute factorial of a given number

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




/*Recursive Definition*/
/*int factorial(int n)
{if(n==0)
return 1;
else
return(n*factorial(n-1));
}
*/



/*Non-Recursive Definition*/

int factorial(int n)
{int i,res=1;
for(i=n;i>=1;i–)
res=res*i;
return(res);
}

void main()
{
int num,res;
clrscr();
printf(“nEnter number to compute factorial?”);
scanf(“%d”,&num);
res=factorial(num);
printf(“nFactorial = %d”,res);
getch();
}



Tags,

Recursion


Recursion

A function call is said to be recursive, if we invoke a function from within the same function.  The phenomenon being referred to as recursion.  A termination condition must be specified with each recursive call to avoid infinite execution of that function.  Recursion is basically required whenever a function has to operate upon different set of values to obtain the result.

The recursive calls must store the intermediate results of arguments of arguments and local variables.  Recursive calls cannot store these values in the memory allocated to variables during compile time, hence dynamic memory management issues are involved in recursion.  Thus, the arguments must be stored along with the return address to evaluate the result, since most recently saved variables are restored first.  Thus activation stacks are created which support LIFO (Last In First Out) order for the purpose of evaluating result in recursion.



Thus recursion may also be used in programs that must operate in Last In First Out order.  Recursive programs may also be written using non-recursive approach to programming either with the use of stack or by using GOTO to transfer the control to any specific part of the program, wherever required.  However, some recursive functions may be converted to iterative definitions simply by using an iterative construct.

Recursion is explained further with examples such as computing factorial of a given number, computing GCD (Greatest Common Divisor), solving Towers of Hanoi problem, raising a number to a given power etc.

Recursive function to find the factorial of a given number:

/*Recursive Definition*/

int factorial(int n)
{if(n==0)
return 1;
else
return(n*factorial(n-1));
}



As the above definition implies, computing a factorial using recursion is similar to computing method performed manually.  The recursive function may be converted to non-recursive/iterative function as follows:

/*Non-Recursive Definition*/

int factorial(int n)
{int i,res=1;
for(i=n;i>=1;i–)
res=res*i;
return(res);
}

If we compare the recursive definition with the iterative one, we note that recursion is eliminated by using a for loop for operating n times restoring the value at each call in a variable called res.  Thus, we may write a recursive algorithm considering the basic step required to sort out a given problem.




 

Recursive function to solve Towers of Hanoi Problem: 

This problem is all about shifting disks from one pillar to the other pillar using a third pillar such that only one disk from the top may be moved at a time such that it is transferred to one pillar while considering that larger disk should be at the bottom of smaller disk.  Recursion is used to solved Towers of Hanoi problem, since it involves repetitive shifting of disks from one pillar to the other.  The ‘C’ recursive function for the same is given below with the output to trace the execution of the program:

void hanoi(int num_disks,char *src,char *tmp,char *trgt)
{
if(num_disks==1)
{printf(“nMove disk from %s to %s”,src,trgt);
}
else
{
hanoi(num_disks-1,src,trgt,tmp);
printf(“nMove disk from %s to %s”,src,trgt);
hanoi(num_disks-1,tmp,src,trgt);
}
}



Recursive function to compute GCD of a given number:

To compute the greatest common divisor of two given numbers x and y, if x is lesser than y, then GCD is invoked with alternate set of arguments.  If the second argument y=0, the first argument x is returned, otherwise GCD function is called with the arguments as y and xmody.  The ‘C’ function for computing GCD is given below:



/*Recursive function to compute GCD*/

int GCD(int x,int y)
{
if(y==0)
return x;
else if(x<y)
return GCD(y,x);
else
return GCD(y,x%y);
}

Recursive function to compute power of a given number:

The power of a given number may be computed by using the following function, f(x,n):

f(x,n) =                     1                ;      if n=0

                x * xn-1   ;      if n>0

/*Recursive definition to computer power of a given number*/

int power(int x,int n)
{
if(n==0)
return 1;
else
return(x * power(x,n-1));
}




Tags,

Conversion from Prefix to Infix


Application of Stacks



Conversion from Prefix to Infix

The algorithm for converting a Prefix expression to an Infix notation is as follows:

  • Accept a prefix string from the user.
  • Start scanning the string from right one character at a time.
  • If it is an operand, push it in stack.
  • If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, optr, opnd2) as follows:

strcpy(arr,opnd1);
strcat(arr,optr);
stracat(arr,opnd2);

Push the result in the stack.

  • Repeat these steps until arr of input prefix string ends.
  • Pop the remaining element of the stack, which is the required Infix notation equivalent to a given Prefix notation.

Program to convert Prefix expression to Infix:



 

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20

struct stack
{
int top;
char arr[MAX];
};

void push(struct stack *,char);
char pop(struct stack *);
int isdigit(char);
void prefix_to_infix(char instr[],char outstr[]);

void main()
{
clrscr();
char str[MAX],resstr[MAX];
printf(“nEnter a prefix string?”);
gets(str);
printf(“nPrefix string: %s”,str);
prefix_to_infix(str,resstr);
printf(“nInfix string: %s”,resstr);
getch();
}

void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow!”);
exit(1);
}
s->arr[++(s->top)]=ch;
}

char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow!”);
exit(1);
}
return(s->arr[(s->top)–]);
}

int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′); }

void prefix_to_infix(char instr[],char outstr[])
{
int i,j,ct=1,z=0;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;instr[i]!=’�’;i++);
for(j=i-1;j>=0;j–)
{
ch=instr[j];
if(isdigit(ch))
{push(&stk,ch);
}
else {
if(ct==1)
{opnd1=pop(&stk);
opnd2=pop(&stk);
outstr[z++]=opnd1;
outstr[z++]=ch;
outstr[z++]=opnd2;
ct++;
}
else {
opnd2=pop(&stk);
outstr[z++]=ch;
outstr[z++]=opnd2;
}
}
}
outstr[z]=’�’;
}



Tags,

x Close

Like Us On Facebook