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 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;

• }

C program for Addition of Sparse Matrix

/*  Add Sparse Matrix...- Contributed by Tushar Anand  */


#include<stdio.h>
#include<stdlib.h>
struct sparse
{
        int *arr;
        int cnt;
};
int c=0;
void create(struct sparse *s)
{
        int arr[3][3];
        int l,i,j;
        s->cnt=0;
        printf("Enter elements\n");
        for(i=0;i<3;i++)
        {
                for(j=0;j<3;j++)
                {
                        scanf("%d",&arr[i][j]);
                        if(arr[i][j]!=0)
                        s->cnt++;
                }//for j
        }//for i
        if(s->cnt>9/2)
        {
                printf("\nNot Sparse matrix\n");
        }
        else
        {
                c=1;
                s->arr=(int *)malloc(sizeof(int)*(s->cnt+1)*3);
                *(s->arr+0)=3;
                *(s->arr+1)=3;
                *(s->arr+2)=s->cnt;
                l=3;
                for(i=0;i<3;i++)
                {
                        for(j=0;j<3;j++)
                        {
                                if(arr[i][j]!=0)
                                {
                                        *(s->arr+l+0)=i;
                                        *(s->arr+l+1)=j;
                                        *(s->arr+l+2)=arr[i][j];
                                        l=l+3;
                                }//if
                        }//for j
                }//for i
        }
}
display(struct sparse *s)
{
        int i;
        for(i=0;i<(s->cnt)*3+3;i++)
        {
                if(i%3==0&&i!=0)
                printf("\n");
                printf("%d\t",*(s->arr+i));
        }//for i
}
void add(struct sparse *s1,struct sparse *s2,struct sparse *s3)
{
        int i,j,k=3,l=3,m=3,flag=0;    
        s3->arr=(int *)malloc(sizeof(int)*(s1->cnt+s2->cnt+1)*3);
        *(s3->arr+0)=3;
        *(s3->arr+1)=3;
        for(i=0;i<3;i++)
        {
                if(*(s1->arr+m+0)==i &&*(s2->arr+l+0)==i)
                {
                        for(j=0;j<3;j++)
                        {
                                if(*(s1->arr+m+1)==j&&*(s2->arr+l+1)==j && *(s1->arr+m+0)==i &&*(s2->arr+l+0)==i)
                                {
                                        *(s3->arr+k+0)=i;
                                        *(s3->arr+k+1)=j;
                                        *(s3->arr+k+2)=*(s1->arr+m+2)+*(s2->arr+l+2);
                                        k+=3;
                                        flag++;
                                        m+=3;
                                        l+=3;
                                }
                                else if(*(s1->arr+m+1)==j && *(s1->arr+m+0)==i)
                                {
                                        *(s3->arr+k+0)=i;
                                        *(s3->arr+k+1)=j;
                                        *(s3->arr+k+2)=*(s1->arr+m+2);
                                        flag++;
                                        k+=3;
                                        m+=3;
                                }
                                else if(*(s2->arr+l+1)==j && *(s2->arr+l+0)==i)
                                {
                                        *(s3->arr+k+0)=i;
                                        *(s3->arr+k+1)=j;
                                        *(s3->arr+k+2)=*(s2->arr+l+2);
                                        flag++;
                                        k+=3;
                                        l+=3;
                                }
                        }
                }
                else if(*(s1->arr+m+0)==i)
                {
                        for(j=0;j<3;j++)
                        {
                                *(s3->arr+k+0)=i;
                                *(s3->arr+k+1)=j;
                                *(s3->arr+k+2)=*(s1->arr+m+2);
                                flag++;
                                k+=3;
                                m+=3;
                        }
                }
                else if(*(s2->arr+l+0)==i)
                {
                        for(j=0;j<3;j++)
                        {
                                *(s3->arr+k+0)=i;
                                *(s3->arr+k+1)=j;
                                *(s3->arr+k+2)=*(s2->arr+l+2);
                                flag++;
                                k+=3;
                                l+=3;
                        }
                }
        }
        *(s3->arr+2)=flag;
        s3->cnt=flag;
}
void main()
{
        struct sparse head,head1,head2;
        create(&head);
        create(&head1);
        if(c==1)
        {
        display(&head);
        display(&head1);
        add(&head,&head1,&head2);
        printf("\n\nAdded matrix :: \n\n");
        display(&head2);
        }
}

Simple Stacks Implementation using arrays : PUSH , POP

/*Simple Stacks Implementation : PUSH , POP*/

#include<stdio.h>

#define max 10

struct stack
 {
  int arr[max];
  int top;
 };
void ini(struct stack *s)
 {
  s->top=(-1);
 }
void push(struct stack *s,int val)
 {
  if(s->top==(max-1))
  {
  printf("\nSTACK OVERFLOW\n");
  return;
 }

  s->top++;
  s->arr[s->top]=val;

 }
int pop(struct stack *s)
 {
  int data;
  if(s->top==-1)
    {
  printf("\nSTACK UNDERFLOW\n");
return;
}


data=s->arr[s->top];
s->top--;
return data;

}
void main()
 {
  struct stack s1;
  int i;
  ini(&s1);
  push(&s1,10);
  push(&s1,40);
  push(&s1,20);
  i=pop(&s1);
  printf("\n%d\n",i);
  i=pop(&s1);
  printf("\n%d\n",i);
  i=pop(&s1);
  printf("\n%d\n",i);
 }

Program to Convert Infix expression to prefix Expression

/*Program to Convert Infix expression to prefix Expression*/

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

#define MAX 50

struct infix
{
char target[MAX];
char stack[MAX];
char *s,*t;
int top,l;
};



void initinfix ( struct infix *p )
{
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
strcpy ( p -> stack, "" ) ;
p -> l = 0 ;
}

void strrev(char *x)
 {
int i,j=0;
char *t;
t=(char *)malloc(sizeof(char)*strlen(x));
for(i=strlen(x)-1;i>=0;i--)
{
t[j++]=x[i];
}
x=t;
//return x;
 }
void setexpr ( struct infix *p, char *str )
{
p->s=str;
strrev(p->s);
p->l=strlen(p->s);
*(p->target+p->l)='\0';
p->t=p->target + (p->l-1);
}


void push ( struct infix *p, char c )
{
if (p->top==MAX-1)
printf ("Stack is full.\n");
else
{
p->top++;
p->stack[p->top]=c;
}
}


char pop (struct infix *p)
{
if (p->top==-1)
{
printf("Stack is empty.\n");
return -1;
}
else
{
char item = p->stack[p->top];
p->top--;
return item ;
}
}

int priority (char c)
{

if(c=='*'||c=='/'||c=='%')
return 2 ;
else
{
if(c=='+'||c=='-')
return 1 ;

else return 0 ;
}
}

void convert (struct infix *p)
{
char opr;

while (*(p->s))
{
if(*(p->s) == ' ' || *(p->s) == '\t')
{
p->s++;
continue ;
}

if (isdigit(*(p->s))||isalpha(*(p->s)))
{
while(isdigit(*(p->s)) || isalpha(*(p->s)))
{
*(p->t) = *(p->s);
p->s++;
p->t--;
}
}

if(*(p->s)==')')
{
push(p,*(p->s));
p->s++;
}

if (*(p->s) == '*' || *(p->s) == '+'||  *(p->s) == '/' || *(p->s ) == '%'|| *(p->s) == '-'|| *(p->s) == '$' )
{
if (p->top!=-1)
{
opr=pop(p);

while (priority(opr)>priority(*(p->s)))
{
*(p->t) = opr;
p->t--;
opr = pop(p);
}
push (p,opr);
push (p,*(p->s));
}
else
push (p,*(p->s));
p->s++;
}

if(*(p->s) == '(')
{
opr=pop(p);
while (opr!=')')
{
*(p->t)=opr;
p->t--;
opr=pop(p) ;
}
p->s++;
}
}

while (p->top!=-1)
{
opr=pop(p);
*(p->t)=opr;
p->t--;
}
p->t++;
}




void show (struct infix p)
{
while(*(p.t))
{
printf(" %c",*(p.t));
p.t++;
}
}






int main()
{
struct infix q ;
char expr[MAX] ;

initinfix(&q);

printf("Enter infix expression : " ) ;
gets(expr);

setexpr(&q,expr);
convert(&q);

printf ("\nThe Prefix expression is: ");
show(q);
printf("\n");

return 0;
}