write a program to perform circular queue using array

//circular queue using array
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>

#define S 5

int Q[S];
int front=-1,rear=-1;
void insert(int n){
if((front==0 && rear==S-1)||(front==rear+1)){
printf("\n overflow \n");
return ;
}
if(rear==-1)
rear=front=0;
else
if(rear==S-1)
rear=0;
else
rear++;
  Q[rear]=n;
}
int del(){
int val;
if(front==-1){
printf("\n underflow \n");
return -9999;
}
val=Q[front];
if(front==rear){
front=rear=-1;
}
else
if(front==S-1)
front=0;
else
front++;
    return val;
}
int main(){
int n,ch;
while(1){
printf("1.insert\n2.delete\n3.exit");
printf("\n enter y choice ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("\n enter the data ");
scanf("%d",&n);
insert(n);
break;
case 2:
n=del();
if(n!=-9999){
printf("\n popped item is %d\n",n);
}
break;
case 3:
exit(0);
break;
default:
printf("\n check y option ");
}
}
getch();
return 0;
}

write a program to perform dqueue using link list

//write a program to perform insertion,deletion and display operation on dqueue using link list
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
typedef struct dnode{
int data;
struct dnode *next;
}dnode;
dnode *front=NULL,*rear=NULL;
void insertf(int x){
dnode *temp;
temp=(dnode*)malloc(sizeof(dnode));
temp->data=x;
temp->next=NULL;
   if(front==NULL){
    front=rear=temp;
   }
   else{
      rear->next=temp;
     rear=temp;
 }
}
void insertr(int x){
dnode *temp,*temp1;
temp=(dnode*)malloc(sizeof(dnode));
temp->data=x;
temp->next=NULL;
if(rear==NULL){
front=rear=temp;
}
else{
temp1=front;
   while(temp1->next!=NULL)
temp1=temp1->next;
temp1->next=temp;
}
}
void delr(){
dnode *temp;
int i;
if(rear==NULL)
{
printf("\nunderflow");
return;
}
temp=front;
while(temp->next->next!=NULL)
temp=temp->next;
dnode *t=temp->next;
printf("\nDeleted node is %d\n",temp->next->data);
temp->next=NULL;
free(t);
rear=temp;
}
void delf(){
dnode *temp;
if(front==NULL)
{
printf("\nunderflow");
return;
}
temp=front;
front=front->next;
printf("\nDeleted node is %d\n",temp->data);
free(temp);
}
void display(){
dnode *temp;
    temp=front;
    printf("\n");
    while(temp!=NULL)
   {
    printf("\t%d",temp->data);
    temp=temp->next;
   
  }
  printf("\n");
}
int main(){
int n,ch;
while(1){
printf("1.insert at front \n2.insert at rear \n3.delete at rear \n4.delete at front \n5.display \n6.exit");
printf("\n enter y choice ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("\n enter the data ");
scanf("%d",&n);
insertf(n);
break;
   case 2:
      printf("\n enter the data ");
scanf("%d",&n);
insertr(n);
break;
  case 3:
      delr();
  break;
  case 4:
     delf();
 break;
 case 5:
  display();
  break;
case 6:
exit(0);
break;
default:
printf("check y option ");
}
  }
  getch();
  return 0;
}

PROGRAM TO CONVERT GIVEN BINARY TREE TO DOUBLE LINKED LIST

#include<stdio.h>

#include<stdlib.h>

struct node{

int data;

struct node *left,*right;

};

struct node  *array[];

int x=-1;

int size;

void insertTree(struct node **root,int data){

if(!(*root)){

*root=malloc(sizeof(struct node));

(*root)->data=data;

(*root)->left=NULL;

(*root)->right=NULL;

}

else {

if(data<(*root)->data)

insertTree(&((*root)->left),data);

else

insertTree(&((*root)->right),data);

}

}

void inoder(struct node *root){

if(root){

inoder(root->left);

array[++x]=root;

inoder(root->right);

}

}

void linekdlist(){

int i;

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

if(i==0){

array[i]->left=NULL;

array[i]->right=array[i+1];

}

else{

if(i==size-1)

{

array[i]->right=NULL;

array[i]->left=array[i-1];

}

else{

array[i]->left=array[i-1];

array[i]->right=array[i+1];

}

}

}}

void display(struct node *root){

while(root){

printf("data=%d\n",root->data);

root=root->right;

}

}

int main(){

struct node *root=NULL;

int i,temp;

printf("\nenter the total number of data:");

scanf("%d",&size);

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

printf("\nenter the data: ");

scanf("%d",&temp);

insertTree(&root,temp);

}

inoder(root);

linekdlist();

root=array[0];

printf("Linked list:\n");

display(root);

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

free(array[i]);

return 0;

}

Find more at http://pawankumar2394.quora.com/

PROGRAM TO BUILD EXPRESSION TREE USING STACK

 /*

Algorithm

  1 Take any postfix epression 
  2 Run the loop If it is an operand then simply push it to stack 
  3 Else if it is the operator then pop two operand  from the stack 
  4 Make the first and  second poped operand as a left child  and right child of current operand respectively then push it to stack 
  5 Continue the steps and run the loop till the length of postfix expression Anonymous Anonymous

*/

• #include<stdio.h>

• #include<stdlib.h>

• #include<string.h>

• #define SIZE 50

• struct express_tree

• {

• char ch;

• struct express_tree *left,*right;

• };

• struct stack

• {

• struct express_tree **array;

• int top;

• };

• /*...................................................................*/

• struct stack* create_stack()

• {

• struct stack *st=(struct stack *)malloc(sizeof(struct stack));

• st->array=malloc(sizeof(struct express_tree)*SIZE);

• return st;

• }

• /*...................................................................*/

• int is_empty_stack(struct stack *s)

• {

• return(s->top==-1);

• }

• /*...................................................................*/

• int is_full_stack(struct stack *s)

• {

• return(s->top==SIZE-1);

• }

• /*...................................................................*/

• void push(struct stack *s,struct express_tree *new)

• {

• if(is_full_stack(s))

• return;

• s->array[++s->top]=new;

• }

• /*...................................................................*/

• struct express_tree* pop(struct stack *s)

• {

• if(is_empty_stack(s))

• return NULL;

• return s->array[s->top--];

• }

• /*......................................................................*/

• void delete_stack(struct stack *s)

• {

• if(s)

• {

• if(s->array)

• free(s->array);

• free(s);

• }

• }

• /*......................................................................*/

• void delete_express_tree(struct express_tree *expression)

• {

• if(expression)

• {

• delete_express_tree(expression->left);

• delete_express_tree(expression->right);

• free(expression);

• }

• }

• /*......................................................................*/

• void display_tree(struct express_tree *root)

• {

• if(root)

• {

• display_tree(root->left);

• display_tree(root->right);

• printf("%c\n",root->ch);

• }

• }

• /*......................................................................*/

• struct stack* tree_making(char str[])

• {

• struct stack *s=create_stack();

• struct express_tree *new_node,*t2,*t1,*new;

• int i;

• for(i=0;i<strlen(str);i++)

• {

• if(isalpha(str[i]))

• {

• new_node=malloc(sizeof(struct express_tree));

• new_node->ch=str[i];

• new_node->left=new_node->right=NULL;

• push(s,new_node);

• }

• else

• {

• t2=pop(s);

• t1=pop(s);

• new=malloc(sizeof(struct express_tree));

• new->ch=str[i];

• new->left=t1;

• new->right=t2;

• push(s,new);

• }

• }

• return s;

• }

• /*......................................................................*/

• int main()

• {

• struct express_tree *temp;

• struct stack *s;

• char str[SIZE];

• printf("\nenter any postfix expression ");

• fgets(str,SIZE,stdin);

• s=tree_making(str);

• temp=pop(s);

• printf("expression tree\n");

• display_tree(temp);

• delete_express_tree(temp);

• delete_stack(s);

• return 0;

• }

Program to convert expression infix to prefix

//infix to prefix

#include<stdio.h>

#include<string.h>

#define SIZE 10

int pr(char op)
{
if(op=='*' || op=='/')
return 3;
if(op=='+' || op=='-')
return 2;
else
return 0;
}

char stack[SIZE];
int top=-1;

void push(char op)
{
stack[++top]=op;
}

char pop()
{
return stack[top--];
}

void polish(char infix[],char prefix[])
{
int i,l,j=0;
char op;
strrev(infix);
l=strlen(infix);
infix[l]='(';
infix[l+1]='\0';
push(')');
for(i=0;infix[i]!='\0';i++)
{
if(isalpha(infix[i]))
{
prefix[j++]=infix[i];
continue;
}
if(infix[i]==')')
{
push(infix[i]);
continue;
}
if(infix[i]=='(')
{
while((op=pop())!=')')
prefix[j++]=op;
}
else
{
while(pr(infix[i])<pr(stack[top]))
prefix[j++]=pop();
push(infix[i]);
}

}
prefix[j]='\0';
strrev(prefix);
}

int main()
{
char infix[20],prefix[20];
printf("\nEnter the infix : ");
gets(infix);
polish(infix,prefix);
printf("\nprefix : %s",prefix);

return 0;
}

Program to convert express infix to postfix in stack using array

//infix to postfix





#include<stdio.h>

#include<string.h>

#define SIZE 10

int pr(char op)
{
if(op=='*' || op=='/')
return 3;
if(op=='+' || op=='-')
return 2;
else
return 0;
}

char stack[SIZE];
int top=-1;

void push(char op)
{
stack[++top]=op;
}

char pop()
{
return stack[top--];
}

void rev_polish(char infix[],char postfix[])
{
int i,l,j=0;
char op;
l=strlen(infix);
infix[l]=')';
infix[l+1]='\0';
push('(');
for(i=0;infix[i]!='\0';i++)
{
if(isalpha(infix[i]))
{
postfix[j++]=infix[i];
continue;
}
if(infix[i]=='(')
{
push(infix[i]);
continue;
}
if(infix[i]==')')
{
while((op=pop())!='(')
postfix[j++]=op;
}
else
{
while(pr(infix[i])<=pr(stack[top]))
postfix[j++]=pop();
push(infix[i]);
}

}
postfix[j]='\0';
}

int main()
{
char infix[20],postfix[20];
printf("\nEnter the infix : ");
gets(infix);
rev_polish(infix,postfix);
printf("\nPostfix : %s",postfix);
return 0;
}

circular queue using linked list

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

#define SIZE 5

int Q[SIZE],front=-1,rear=-1;

void insert(int x)
{
if( (front==0 && rear==SIZE-1) || front==rear+1)
{
printf("\nOverflow");
return ;
}
if(rear==-1)
front=rear=0;
else
if(rear==SIZE-1)
rear=0;
else
rear++;
Q[rear]=x;
}

int del()
{
int item;
if(front==-1)
{
printf("\nUnderflow");
return -9999;
}
item=Q[front];
if(front==rear)
front=rear=-1;
else
if(front==SIZE-1)
front=0;
else
front++;
return item;
}

int main()
{
int n,ch;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insert");
printf("\n\t\t\t2 : Deletion");
printf("\n\t\t\t3 : Exit");
printf("\n\t\t\tEnter your choice :");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the item :");
scanf("%d",&n);
insert(n);
break;
case 2:
n=del();
if(n!=-9999)
printf("\nPopped item : %d",n);
break;
case 3:
exit(0);
default:
printf("\nInvalid Choice");
}
}
return 0;
}

priority queue using linked list

//priority queue using linked list

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

typedef struct node
{
int info,pr;
struct node *next;
}node;
node *start=NULL;

void insert_at_end(int x,int p);
void insert_at_beg(int x,int p);
void insert_at_specific(int ,int, int);
void del_at_beg();
void insert(int x,int p);

int main()
{
int n,po,ch,p;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insertion");
printf("\n\t\t\t2 : Deletion");
printf("\n\t\t\t3 : Exit");
printf("\n\t\t\tEnter ur choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the info :");
scanf("%d",&n);
printf("\nEnter the priority :");
scanf("%d",&p);
insert(n,p);
break;
case 2:
del_at_beg();
break;
case 3:
exit(0);
default:
printf("\nInvalid choice");
}
}
return 0;
}

void insert_at_end(int x, int p)
{
node *temp,*new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=NULL;
if(start==NULL)
start=new_node;
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new_node;
}
}

void insert_at_beg(int x,int p)
{
node *new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=start;
start=new_node;
}

void insert_at_specific(int x,int p,int po)
{
int i;
node *new_node,*temp;
if(po<1 || po>count()+1)
{
printf("\nInvalid position");
return;
}
if(po==1)
insert_at_beg(x,p);
else
{
if(po==count()+1)
insert_at_end(x,p);
else
{
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=NULL;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
new_node->next=temp->next;
temp->next=new_node;
}
}
}


int count()
{
node *temp;
int c=0;
for(temp=start;temp!=NULL;temp=temp->next)
c++;
return c;
}

void del_at_beg()
{
node *temp;
if(start==NULL)
{
printf("\nList Empty");
return;
}
temp=start;
start=start->next;
printf("\nDeleted node : %d",temp->info);
printf("\nDeleted priority : %d",temp->pr);
free(temp);
}

void insert(int x,int p)
{
node *temp;
int po=0;
if(start==NULL)
{
insert_at_beg(x,p);
return;
}
temp=start;
while(temp!=NULL)
{
if(temp->pr >= p)
{
po++;
temp=temp->next;
}
else
break;
}
insert_at_specific(x,p,po+1);
}