Data Structures Lab -CSL 201- Practice questions - KTU 2019 scheme
**********************************************************************************
1. Write a program to read two polynomials and store them in an array. Calculate the sum of thetwo polynomials and display the first polynomial, second polynomial and the resultant
polynomial.
#include<stdio.h>
void create(int poly[],int degree)
{
int i=0;
printf("Enter the coeffecients for:\n");
for(i=degree;i>=0;i--)
{
printf("Exp_%d: ",i);
scanf("%d",&poly[i]);
}
}
void display(int poly[],int degree)
{
int i;
for(i=degree;i>=0;i--)
{
if(i!=degree && poly[i]>0)
{
printf("+");
}
printf("%dx^%d",poly[i],i);
}
}
void main()
{
int poly1[100]={0},degree1,poly2[100]={0},degree2,degreeresult,polyresult[100],i=0;
printf("Enter the degree of first polynomial");
scanf("%d",°ree1);
create(poly1,degree1);
printf("Enter the degree of second polynomial");
scanf("%d",°ree2);
create(poly2,degree2);
if(degree1>degree2)
{
degreeresult=degree1;
}
else
{
degreeresult=degree2;
}
for(i=0;i<=degreeresult;i++)
{
polyresult[i]=poly1[i]+poly2[i];
}
printf("The first polynomial is:\n");
display(poly1,degree1);
printf("\nThe second polynomial is:\n");
display(poly2,degree2);
printf("\nThe sum of 2 polynomials is:\n");
display(polyresult,degreeresult);
}
***************
*****************************************************************************************
Alternate implementation
/*********************************************
* Polynomial addition using arrays in C
*********************************************/
#include<stdio.h>
#include<math.h>
/*
This structure is used to store a polynomial term. An array of such terms represents a
polynomial.
The "coeff" element stores the coefficient of a term in the polynomial,while
the "exp" element stores the exponent.
*/
struct poly
{
float coeff;
int exp;
};
//declaration of polynomials
struct poly a[50],b[50],c[50];
int main()
{
int i;
int deg1,deg2; //stores degrees of the polynomial
int k=0,l=0,m=0;
printf("Enter the highest degree of poly1:");
scanf("%d",°1);
//taking polynomial terms from the user
for(i=0;i<=deg1;i++)
{
//entering values in coefficient of the polynomial terms
printf("\nEnter the coeff of x^%d :",i);
scanf("%f",&a[i].coeff);
//entering values in exponent of the polynomial terms
a[k++].exp = i;
}
//taking second polynomial from the user
printf("\nEnter the highest degree of poly2:");
scanf("%d",°2);
for(i=0;i<=deg2;i++)
{
printf("\nEnter the coeff of x^%d :",i);
scanf("%f",&b[i].coeff);
b[l++].exp = i;
}
//printing first polynomial
printf("\nExpression 1 = %.1f",a[0].coeff);
for(i=1;i<=deg1;i++)
{
printf("+ %.1fx^%d",a[i].coeff,a[i].exp);
}
//printing second polynomial
printf("\nExpression 2 = %.1f",b[0].coeff);
for(i=1;i<=deg2;i++)
{
printf("+ %.1fx^%d",b[i].coeff,b[i].exp);
}
//Adding the polynomials
if(deg1>deg2)
{
for(i=0;i<=deg2;i++)
{
c[m].coeff = a[i].coeff + b[i].coeff;
c[m].exp = a[i].exp;
m++;
}
for(i=deg2+1;i<=deg1;i++)
{
c[m].coeff = a[i].coeff;
c[m].exp = a[i].exp;
m++;
}
}
else
{
for(i=0;i<=deg1;i++)
{
c[m].coeff = a[i].coeff + b[i].coeff;
c[m].exp = a[i].exp;
m++;
}
for(i=deg1+1;i<=deg2;i++)
{
c[m].coeff = b[i].coeff;
c[m].exp = b[i].exp;
m++;
}
}
//printing the sum of the two polynomials
printf("\nExpression after additon = %.1f",c[0].coeff);
for(i=1;i<m;i++)
{
printf("+ %.1fx^%d",c[i].coeff,c[i].exp);
}
return 0;
}
**************
2/3. C Write a program to enter two matrices in normal form . Write a function to convert twomatrices to tuple form and display it. Also find the transpose of the two matrices represented
in tuple form and display it. Find the sum of the two matrices in tuple form and display the
sum in tuple form.
#include<stdio.h>
void read_mat_normal(int mat_normal[100][100],int r,int c)
{
int i=0,j=0;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%d",&mat_normal[i][j]);
}
}
}
void print_mat_normal(int mat_normal[100][100],int r,int c)
{
int i=0,j=0;
for(i=0;i<r;i++)
{
printf("\n");
for(j=0;j<c;j++)
{
printf("%d ",mat_normal[i][j]);
}
}
}
void conv_trans(int mat_normal[100][100],int r,int c)
{
//Normal Form to Tuple Form Conversion
int mat_tup[100][100];
int i,j,cnz=0,tr=0,tc=0;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(mat_normal[i][j]!=0)
{
cnz++;
mat_tup[cnz][0]=i;
mat_tup[cnz][1]=j;
mat_tup[cnz][2]=mat_normal[i][j];
}
}
}
mat_tup[0][0]=r;
mat_tup[0][1]=c;
mat_tup[0][2]=cnz;
tr=cnz+1;
tc=3;
printf("\nrows columns values");
for(i=0;i<tr;i++)
{
printf("\n");
for(j=0;j<tc;j++)
{
printf("%d ",mat_tup[i][j]);
}
}
// Transpose
int temp[100];
for(i=0;i<tr;i++)
{
temp[i]=mat_tup[i][0];
}
for(i=0;i<tr;i++)
{
mat_tup[i][0]= mat_tup[i][1];
mat_tup[i][1]=temp[i];
}
printf("\nThe Transpose is\n");
for(i=0;i<tr;i++)
{
printf("\n");
for(j=0;j<tc;j++)
{
mat_normal[i][j]=mat_tup[i][j];
printf("%d ",mat_tup[i][j]);
}
}
}
void sum(int mat1[100][100],int mat2[100][100])
{
int tr1,tr2,n=0,mat[100][100],i,j,k;
if((mat1[0][0]==mat2[0][0]) && (mat1[0][1]==mat2[0][1]))
{
tr1=mat1[0][2];
tr2=mat2[0][2];
i=1;
j=1;
k=1;
n=tr1+tr2;
while((i<=tr1) &&(j<=tr2))
{
if((mat1[i][0]==mat2[j][0]) &&(mat1[i][1]==mat2[j][1]))
{
mat[k][0]=mat1[i][0];
mat[k][1]=mat1[i][1];
mat[k][2]=mat1[i][2]+mat2[j][2];
i++;j++;k++;
}
else if(mat1[i][0]<mat2[j][0])
{
mat[k][0]=mat1[i][0];
mat[k][1]=mat1[i][1];
mat[k][2]=mat1[i][2];
i++;k++;
}
else
{
mat[k][0]=mat2[j][0];
mat[k][1]=mat2[j][1];
mat[k][2]=mat2[j][2];
j++;k++;
}
}
while(i<=tr1)
{
mat[k][0]=mat1[i][0];
mat[k][1]=mat1[i][1];
mat[k][2]=mat1[i][2];
i++;k++;
}
while(j<=tr2)
{
mat[k][0]=mat2[j][0];
mat[k][1]=mat2[j][1];
mat[k][2]=mat2[j][2];
j++;k++;
}
mat[0][0]=mat1[0][0];
mat[0][1]=mat1[0][1];
mat[0][2]=k-1;
printf("\nThe sum is:\n");
for(i=0;i<k;i++)
{
printf("\n");
for(j=0;j<3;j++)
{
printf("%d ",mat[i][j]);
}
}
}
else
{
printf("The matrix is incompatible");
}
}
void main()
{
int mat1[100][100],r1,c1,mat2[100][100],r2,c2;
printf("\nFirst matrix:");
printf("\nEnter the no. of rows:");
scanf("%d",&r1);
printf("\nEnter the no. of columns:");
scanf("%d",&c1);
printf("Enter the elements\n");
read_mat_normal(mat1,r1,c1);
printf("\nSecond matrix:");
printf("\nEnter the no. of rows:");
scanf("%d",&r2);
printf("\nEnter the no. of columns:");
scanf("%d",&c2);
printf("Enter the elements\n");
read_mat_normal(mat2,r2,c2);
printf("\nThe first matrix in normal form is:");
print_mat_normal(mat1,r1,c1);
printf("\nThe second matrix in normal form is:");
print_mat_normal(mat2,r2,c2);
printf("\nFirst Matrix in tuple form:\n");
conv_trans(mat1,r1,c1);
printf("\nSecond Matrix in tuple form:\n");
conv_trans(mat2,r2,c2);
printf("\nSum\n");
sum(mat1,mat2);
}
*****************************************************************************
4. Implement a circular queue using arrays with the operations:4.1.Insert an element to the queue.
4.2.Delete an elements from the queue.
4.3.Display the contents of the queue after each operation.
#include<stdio.h>
#include<stdlib.h>
int cqueue[50],front=-1,rear=-1,n;
void display()
{
int i=0;
if(front==-1)
{
printf("Circular Queue is empty");
}
else
{
for(i=front;i!=rear;i=(i+1)%n)
{
printf("%d ",cqueue[i]);
}
printf("%d ",cqueue[i]);
}
}
void enqueue()
{
int next,item,i;
printf("Enter the element");
scanf("%d",&item);
if(front==-1)
{
front=0;
rear=0;
cqueue[rear]=item;
}
else
{
next=(rear+1)% n;
if(next!=front)
{
rear=next;
cqueue[rear]=item;
}
else
{
printf("Circular Queue is full\n");
}
}
printf("The circular queue is:\n");
display();
}
void dequeue()
{
int item,i;
if(front==-1)
{
printf("Circular queue is empty");
}
else
{
item=cqueue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=(front+1)%n;
}
}
display();
}
void main()
{
int ch;
printf("Enter the size of the queue");
scanf("%d",&n);
while(1)
{
printf("\nOperations:\n1. Enqueue\n2. Dequeue\n3. Exit");
printf("\nEnter the choice");
scanf("%d",&ch);
switch(ch)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
exit(0);
default:
printf("There is no such operation");
break;
}
}
}
*****************************************************************************
5. Implement a Queue using arrays with the operations:5.1.Insert elements to the Queue.
5.2.Delete elements from the Queue.
5.3.Display the contents of the Queue after each operation.
#include<stdio.h>
#include<stdlib.h>
int lqueue[100],front=-1,rear=-1,n;
void display()
{
int i=0;
if(front==rear)
{
printf("The Queue is empty");
}
else
{
printf("The queue is:\n");
for(i=front+1;i<=rear;i=i+1)
{
printf("%d ",lqueue[i]);
}
}
}
void enqueue()
{
int item;
printf("Enter the element");
scanf("%d",&item);
if(rear==n-1)
{
printf("Queue is full");
}
else
{
rear=rear+1;
lqueue[rear]=item;
}
display();
}
void dequeue()
{
int item;
if(front==rear)
{
printf("Queue empty...\n");
}
else
{
front=front+1;
item=lqueue[front];
printf("Removed item=%d\n",item);
if(front==rear)
{
front=-1;
rear=-1;
}
}
display();
}
void main()
{
int ch;
printf("Enter the size of the queue");
scanf("%d",&n);
while(1)
{
printf("\nOperations:\n1. Enqueue\n2. Dequeue\n3. Exit");
printf("\nEnter the choice");
scanf("%d",&ch);
switch(ch)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
exit(0);
default:
printf("There is no such operation");
break;
}
}
}
*****************************************************************************
6.Implement a Stack using arrays with the operations:6.1.Pushing elements to the Stack.
6.2.Popping elements from the Stack
6.3.Display the contents of the Stack after each operation
#include<stdio.h>
int stack[100],n,top=-1;
void push(void);
void pop(void);
void display(void);
int main()
{
//clrscr();
int choice;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t Program terminated ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{ int x;
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{ int i;
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}
****************************************************************************
7. Implement a Priority Queue using arrays with the operations:7.1.Insert elements to the Priority Queue.
7.2.Delete elements from the Priority Queue.
7.3.Display the contents of the Priority Queue after each operation.
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
void insert(int);
void delete(int);
void create();
void check(int);
void display();
int prique[MAX];
int front, rear;
void main()
{
int n, ch;
printf("\n1 - Insert an element into queue");
printf("\n2 - Delete an element from queue");
printf("\n3 - Display queue elements");
printf("\n4 - Exit");
create();
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nEnter value to be inserted : ");
scanf("%d",&n);
insert(n);
break;
case 2:
printf("\nEnter value to delete : ");
scanf("%d",&n);
delete(n);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nChoice is incorrect, Enter a correct choice");
}
}
}
/* Function to create an empty priority queue */
void create()
{
front = rear = -1;
}
/* Function to insert value into priority queue */
void insert(int data)
{
if (rear >= MAX - 1)
{
printf("\nQueue overflow no more elements can be inserted");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
prique[rear] = data;
return;
}
else
check(data);
rear++;
}
/* Function to check priority and place element */
void check(int data)
{
int i,j;
for (i = 0; i <= rear; i++)
{
if (data >= prique[i])
{
for (j = rear + 1; j > i; j--)
{
prique[j] = prique[j - 1];
}
prique[i] = data;
return;
}
}
prique[i] = data;
}
/* Function to delete an element from queue */
void delete(int data)
{
int i;
if ((front==-1) && (rear==-1))
{
printf("\nQueue is empty no elements to delete");
return;
}
for (i = 0; i <= rear; i++)
{
if (data == prique[i])
{
for (; i < rear; i++)
{
prique[i] = prique[i + 1];
}
prique[i] = -99;
rear--;
if (rear == -1)
front = -1;
return;
}
}
printf("\n%d not found in queue to delete", data);
}
/* Function to display queue elements */
void display()
{
if ((front == -1) && (rear == -1))
{
printf("\nQueue is empty");
return;
}
for (; front <= rear; front++)
{
printf(" %d ", prique[front]);
}
front = 0;
}
****************************************************************************
8. Implement a Double-Ended Queue (DEQUEUE) with the operations:
8.1.Insert elements to the Front of the queue.
8.2.Insert elements to the Rear of the queue
8.3.Delete elements from the Front of the queue.
8.4.Delete elements from the Rear of the queue.
8.5.Display the queue after each operation.
#include<stdio.h>
#include<stdlib.h>
#define MAX 7
int deque_arr[MAX];
int front=-1;
int rear=-1;
void insert_frontEnd(int item);
void insert_rearEnd(int item);
int delete_frontEnd();
int delete_rearEnd();
void display();
int isEmpty();
int isFull();
int main()
{
int choice,item;
while(1)
{
printf("\n\n1.Insert at the front end\n");
printf("2.Insert at the rear end\n");
printf("3.Delete from front end\n");
printf("4.Delete from rear end\n");
printf("5.Display\n");
printf("6.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nInput the element for adding in queue : ");
scanf("%d",&item);
insert_frontEnd(item);
break;
case 2:
printf("\nInput the element for adding in queue : ");
scanf("%d",&item);
insert_rearEnd(item);
break;
case 3:
printf("\nElement deleted from front end is : %d\n",delete_frontEnd());
break;
case 4:
printf("\nElement deleted from rear end is : %d\n",delete_rearEnd());
break;
case 5:
display();
break;
case 6:
exit(1);
default:
printf("\nWrong choice\n");
}/*End of switch*/
printf("\nfront = %d, rear =%d\n", front , rear);
display();
}/*End of while*/
}/*End of main()*/
void insert_frontEnd(int item)
{
if( isFull() )
{
printf("\nQueue Overflow\n");
return;
}
if( front==-1 )/*If queue is initially empty*/
{
front=0;
rear=0;
}
else if(front==0)
front=MAX-1;
else
front=front-1;
deque_arr[front]=item ;
}/*End of insert_frontEnd()*/
void insert_rearEnd(int item)
{
if( isFull() )
{
printf("\nQueue Overflow\n");
return;
}
if(front==-1) /*if queue is initially empty*/
{
front=0;
rear=0;
}
else if(rear==MAX-1) /*rear is at last position of queue */
rear=0;
else
rear=rear+1;
deque_arr[rear]=item ;
}/*End of insert_rearEnd()*/
int delete_frontEnd()
{
int item;
if( isEmpty() )
{
printf("\nQueue Underflow\n");
exit(1);
}
item=deque_arr[front];
if(front==rear) /*Queue has only one element */
{
front=-1;
rear=-1;
}
else
if(front==MAX-1)
front=0;
else
front=front+1;
return item;
}/*End of delete_frontEnd()*/
int delete_rearEnd()
{
int item;
if( isEmpty() )
{
printf("\nQueue Underflow\n");
exit(1);
}
item=deque_arr[rear];
if(front==rear) /*queue has only one element*/
{
front=-1;
rear=-1;
}
else if(rear==0)
rear=MAX-1;
else
rear=rear-1;
return item;
}/*End of delete_rearEnd() */
int isFull()
{
if ( (front==0 && rear==MAX-1) || (front==rear+1) )
return 1;
else
return 0;
}/*End of isFull()*/
int isEmpty()
{
if( front == -1)
return 1;
else
return 0;
}/*End of isEmpty()*/
void display()
{
int i;
if( isEmpty() )
{
printf("\nQueue is empty\n");
return;
}
printf("\nQueue elements :\n");
i=front;
if( front<=rear )
{
while(i<=rear)
printf("%d ",deque_arr[i++]);
}
else
{
while(i<=MAX-1)
printf("%d ",deque_arr[i++]);
i=0;
while(i<=rear)
printf("%d ",deque_arr[i++]);
}
printf("\n");
}/*End of display() */
****************************************************************************
9. Using stack convert an infix expression to a postfix expression
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define SIZE 100
/* declared here as global variable because stack[]
* is used by more than one fucntions */
char stack[SIZE];
int top = -1;
/* define push operation */
void push(char item)
{
if(top >= SIZE-1)
{
printf("\nStack Overflow.");
}
else
{
top = top+1;
stack[top] = item;
}
}
/* define pop operation */
char pop()
{
char item ;
if(top <0)
{
printf("stack under flow: invalid infix expression");
getchar();
/* underflow may occur for invalid expression */
/* where ( and ) are not matched */
exit(1);
}
else
{
item = stack[top];
top = top-1;
return(item);
}
}
/* define function that is used to determine whether any symbol is operator or not
(that is symbol is operand)
* this fucntion returns 1 if symbol is opreator else return 0 */
int is_operator(char symbol)
{
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-')
{
return 1;
}
else
{
return 0;
}
}
/* define fucntion that is used to assign precendence to operator.
* Here ^ denotes exponent operator.
* In this fucntion we assume that higher integer value
* means higher precendence */
int precedence(char symbol)
{
if(symbol == '^') /* exponent operator, highest precedence*/
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-') /* lowest precedence */
{
return(1);
}
else
{
return(0);
}
}
void InfixToPostfix(char infix_exp[], char postfix_exp[])
{
int i, j;
char item;
char x;
push('('); /* push '(' onto stack */
strcat(infix_exp,")"); /* add ')' to infix expression */
i=0;
j=0;
item=infix_exp[i]; /* initialize before loop*/
while(item != '\0') /* run loop till end of infix expression */
{
if(item == '(')
{
push(item);
}
else if( isdigit(item) || isalpha(item))
{
postfix_exp[j] = item; /* add operand symbol to postfix expr */
j++;
}
else if(is_operator(item) == 1) /* means symbol is operator */
{
x=pop();
while(is_operator(x) == 1 && precedence(x)>= precedence(item))
{
postfix_exp[j] = x; /* so pop all higher precendence operator and */
j++;
x = pop(); /* add them to postfix expresion */
}
push(x);
/* because just above while loop will terminate we have
oppped one extra item
for which condition fails and loop terminates, so that one*/
push(item); /* push current oprerator symbol onto stack */
}
else if(item == ')') /* if current symbol is ')' then */
{
x = pop(); /* pop and keep popping until */
while(x != '(') /* '(' encounterd */
{
postfix_exp[j] = x;
j++;
x = pop();
}
}
else
{ /* if current symbol is neither operand not '(' nor ')' and nor
operator */
printf("\nInvalid infix Expression.\n"); /* the it is illegeal symbol */
getchar();
exit(1);
}
i++;
item = infix_exp[i]; /* go to next symbol of infix expression */
} /* while loop ends here */
if(top>0)
{
printf("\nInvalid infix Expression.\n"); /* the it is illegeal symbol */
exit(1);
}
if(top>0)
{
printf("\nInvalid infix Expression.\n"); /* the it is illegeal symbol */
getchar();
exit(1);
}
postfix_exp[j] = '\0'; /* add sentinel else puts() fucntion */
/* will print entire postfix[] array upto SIZE */
}
/* main function begins */
int main()
{
char infix[SIZE], postfix[SIZE]; /* declare infix string and postfix string */
/* why we asked the user to enter infix expression
* in parentheses ( )
* What changes are required in porgram to
* get rid of this restriction since it is not
* in algorithm
* */
printf("ASSUMPTION: The infix expression contains single letter variables and single digit constants only.\n");
printf("\nEnter Infix expression : ");
scanf("%s",infix);
InfixToPostfix(infix,postfix); /* call to convert */
printf("Postfix Expression: ");
puts(postfix); /* print postfix expression */
return 0;
}
*********************************************************************
9.Evaluation of Postfix expression#include <stdio.h>
#include <ctype.h>
#define MAXSTACK 100
#define POSTFIXSIZE 100
/* declare stack and its top pointer to be used during postfix expression
evaluation*/
int stack[MAXSTACK];
int top = -1;
/* define push operation */
void push(int item)
{
if (top >= MAXSTACK - 1) {
printf("stack over flow");
return;
}
else {
top = top + 1;
stack[top] = item;
}
}
/* define pop operation */
int pop()
{
int item;
if (top < 0) {
printf("stack under flow");
}
else {
item = stack[top];
top = top - 1;
return item;
}
}
/* define function that is used to input postfix expression and to evaluate it */
void EvalPostfix(char postfix[])
{
int i;
char ch;
int val;
int A, B;
/* evaluate postfix expression */
for (i = 0; postfix[i] != '$'; i++) {
ch = postfix[i];
if (isdigit(ch)) {
/* we saw an operand,push the digit onto stack
ch - '0' is used for getting digit rather than ASCII code of digit */
push(ch - '0');
}
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
/* we saw an operator
* pop top element A and next-to-top elemnet B
* from stack and compute B operator A
*/
A = pop();
B = pop();
switch (ch) /* ch is an operator */
{
case '*':
val = B * A;
break;
case '/':
val = B / A;
break;
case '+':
val = B + A;
break;
case '-':
val = B - A;
break;
}
/* push the value obtained above onto the stack */
push(val);
}
}
printf(" \n Result of expression evaluation : %d \n", pop());
}
int main()
{
int i;
/* declare character array to store postfix expression */
char postfix[POSTFIXSIZE];
printf("ASSUMPTION: There are only four operators(*, /, +, -) in an expression and operand is single digit only.\n");
printf(" \nEnter postfix expression,\npress right parenthesis '$' for end expression : ");
/* take input of postfix expression from user */
for (i = 0; i <= POSTFIXSIZE - 1; i++) {
scanf("%c", &postfix[i]);
if (postfix[i] == '$') /* is there any way to eliminate this if */
{
break;
} /* and break statement */
}
/* call function to evaluate postfix expression */
EvalPostfix(postfix);
return 0;
}
*************************************************************************
10. Write a program to convert an infix expression to a prefix expression using stack.
12. Write a menu driven program for performing the following operations on a Linked List:#include<stdio.h>
#include<math.h>
#include<string.h>
#include <stdlib.h>
#define MAX 120
void push(int);
char pop();
void infix_to_prefix();
int precedence (char);
char *strrev(char *str);
char stack[120],infix[120],prefix[120];
int top = -1;
int main()
{
printf("\nINPUT THE INFIX EXPRESSION : ");
scanf("%s",infix);
infix_to_prefix();
return 0;
}
// method that pushes the elements onto the character stack
void push(int pos)
{
if(top == MAX-1)
{
printf("\nSTACK OVERFLOW\n");
}
else {
top++;
stack[top] = infix[pos];
}}
// method that removes character from stack and returns them
char pop()
{
char ch;
if(top < 0)
{
printf("\nSTACK UNDERFLOW\n");
exit(0);
}
else
{
ch = stack[top];
stack[top] = '\0';
top--;
return(ch);
}
return 0;
}
// method that converts String from infix to prefix
// all the strings are assumed to be valid expressions
void infix_to_prefix()
{
int i = 0,j = 0;
strrev(infix); // Reverse the infix expression
while(infix[i] != '\0')
{
// if an alphabet is found then copy it to the output string
if(infix[i] >= 'a' && infix[i] <= 'z')
{
prefix[j] = infix[i];
j++;
i++;
}
// In the reversed string, closing bracket will be found first so put it in the stack
else if(infix[i] == ')' || infix[i] == '}' || infix[i] == ']')
{
push(i);
i++;
}
// if an opening bracket is found, then
else if(infix[i] == '(' || infix[i] == '{' || infix[i] == '[') /* when closing bracket is found */
{
if(infix[i] == '(')
{
while(stack[top] != ')') /* pop till opening bracket is found */
{
prefix[j] = pop();
j++;
}
pop();
i++;
}
else if(infix[i] == '[')
{
while(stack[top] != ']') /* pop till corresponding opening bracket is found */
{
prefix[j] = pop();
j++;
}
pop();
i++;
}
else if(infix[i] == '{')
{
while(stack[top] != '}') /*pop till corresponding opening bracket is found*/
{
prefix[j] = pop();
j++;
}
pop();
i++;
}}
else
{
// if the stack if empty, then we simply put the operator in stack
if(top == -1)
{
push(i);
i++;
}
// if the precedence of operator is less than the stack top then
else if( precedence(infix[i]) < precedence(stack[top]))
{
prefix[j] = pop(); // pop the stack top and add it to the prefix string
j++;
// if you have an operator that has precedence greater than operator
while(precedence(stack[top]) > precedence(infix[i])){
prefix[j] = pop(); // Pop the operator
j++;
if(top < 0) {
break;
}}
push(i);
i++;
}
// if the precedence of operator is greater than or equal to the stack top
else if(precedence(infix[i]) >= precedence(stack[top]))
{
push(i); // Push it onto the stack
i++;
}}}
// At the end remove all the operators from the stack
while(top != -1)
{
prefix[j] = pop();
j++;
}
// Reverse the final string before output
strrev(prefix);
prefix[j] = '\0';
printf("EQUIVALENT PREFIX NOTATION : %s ",prefix);
}
/* Function to return precedence of operators */
int precedence(char alpha)
{
if(alpha == '+' || alpha =='-')
{
return(1);
}
if(alpha == '*' || alpha =='/')
{
return(2);
}
return 0;
}
char *strrev(char *str)
{
if (!str || ! *str)
return str;
int i = strlen(str) - 1, j = 0;
char ch;
while (i > j)
{
ch = str[i];
str[i] = str[j];
str[j] = ch;
i--;
j++;
}
return str;
}
****************************************************************************
12.1.Display
12.2.Insert at Beginning
12.3.Insert at End
12.4.Insert at a specified Position
12.5.Delete from Beginning
12.6.Delete from End
12.7.Delete from a specified Position
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
}*first=NULL,*last=NULL,*temp=NULL,*trav=NULL,*prev=NULL;
void create()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
temp->link=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
{
last->link=temp;
last=temp;
}
}
void display()
{
temp=first;
while(temp!=NULL)
{
printf(" %d---->",temp->data);
temp=temp->link;
}
printf(" NULL");
}
void insert_begin()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data");
scanf("%d",&temp->data);
temp->link=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
{
temp->link=first;
first=temp;
}
}
void insert_at_end()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data");
scanf("%d",&temp->data);
temp->link=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
{
last->link=temp;
last=temp;
}
}
void insert_at_pos()
{
int pos,i=0;
printf("Enter the position");
scanf("%d",&pos);
if(pos==0)
{
insert_begin();
}
else
{ prev=NULL;
trav=first;
for(i=0;i<pos;i++)
{
prev=trav;
trav=trav->link;
}
if(trav==NULL)
{
insert_at_end();
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data");
scanf("%d",&temp->data);
temp->link=NULL;
prev->link=temp;
temp->link=trav;
}
}
}
void del_from_begin()
{
if(first==NULL)
{
printf("List is empty");
}
else
{
trav=first;
first=first->link;
trav->link=NULL;
free(trav);
}
}
void del_from_end()
{
if(first==NULL)
{
printf("List is empty");
}
else
{
prev=NULL;
trav=first;
while(trav->link!=NULL)
{
prev=trav;
trav=trav->link;
}
prev->link=NULL;
last=prev;
free(trav);
}
}
void del_from_pos()
{
int pos,i=0;
printf("Enter the position");
scanf("%d",&pos);
if(pos==0)
{
del_from_begin();
}
else
{ prev=NULL;
trav=first;
for(i=0;i<pos;i++)
{
prev=trav;
trav=trav->link;
}
if(trav==NULL)
{
printf("position beyond list");
}
else if(trav->link==NULL)
{
del_from_end();
}
else
{
if(first==NULL)
{
printf("List is empty");
}
else
{
prev->link=trav->link;
free(trav);
}
}
}
}
void main()
{
int ch;
do
{
printf("\nMenu\n----\n1. Create\n2. Display\n3. Insert At Beginning\n4. Insert At End\n5. Insert At a Specified Position\n6. Delete From Beginning\n7. Delete From End\n8. Delete From a Specified Position\n9. Exit");
printf("\nEnter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insert_begin();
break;
case 4:
insert_at_end();
break;
case 5:
insert_at_pos();
break;
case 6:
del_from_begin();
break;
case 7:
del_from_end();
break;
case 8:
del_from_pos();
break;
case 9:
exit(0);
default:
printf("There is no such operation:");
}
}
while(1);
}
****************************************************************************
13. Implement a stack using linked list with the operations:13.1.Push elements to the stack.
13.2.Pop elements from the stack.
13.3.Display the stack after each operation.
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
}*first=NULL,*last=NULL,*temp=NULL;
void push()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
temp->link=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
{
temp->link=first;
first=temp;
}
}
void pop()
{
if (first==NULL)
printf("Stack is empty...underflow");
else
first=first->link;
}
void display()
{
temp=first;
while(temp!=NULL)
{
printf(" %d---->",temp->data);
temp=temp->link;
}
printf(" NULL");
}
void main()
{
int ch;
do
{
printf("\nMenu\n----\n1. Push\n2. Pop\n3.display\n4. Exit");
printf("\nEnter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
display();
break;
case 2:
pop();
display();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("There is no such operation:");
}
}
while(1);
}
****************************************************************************
14. Implement a Queue using linked list with the operations:14.1.Insert an elements to the queue.
14.2.Delete an elements from the queue.
14.3.Display the queue after each operation.
14. Implement a Queue using linked list with the operations:
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *link;
}*first=NULL,*last=NULL,*temp=NULL;
void add()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&temp->data);
temp->link=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
{
last->link=temp;
last=temp;
}
}
void delete()
{
if (first==NULL)
printf("Queue is empty...underflow");
else
first=first->link;
}
void display()
{
temp=first;
while(temp!=NULL)
{
printf(" %d---->",temp->data);
temp=temp->link;
}
printf(" NULL");
}
void main()
{
int ch;
do
{
printf("\nMenu\n----\n1. Add\n2. Delete\n3.display\n4. Exit");
printf("\nEnter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
add();
display();
break;
case 2:
delete();
display();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("There is no such operation:");
}
}
while(1);
}
****************************************************************************
15. Write a program to reverse the content of queue using stack
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int lqueue[100],front=-1,rear=-1,n,top=-1,stack[100];
void display()
{
int i=0;
if(front==rear)
{
printf("The Queue is empty");
}
else
{
printf("The queue is:\n");
for(i=front+1;i<=rear;i=i+1)
{
printf("%d ",lqueue[i]);
}
}
}
void enqueue(int item)
{
if(rear==n-1)
{
printf("Queue is full");
}
else
{
rear=rear+1;
lqueue[rear]=item;
}
}
int dequeue()
{
int item;
if(front==rear)
{
//printf("Queue empty...\n");
return -1;
}
else
{
front=front+1;
item=lqueue[front];
//printf("Removed item=%d\n",item);
if(front==rear)
{
front=-1;
rear=-1;
}
return item;
}
}
void push(int item)
{
if(top==n-1)
{
printf("Stack is full");
}
else
{
top=top+1;
stack[top]=item;
}
}
int pop()
{
int item;
if(top==-1)
{
//printf("Stack is empty");
return -1;
}
else
{
item=stack[top];
top=top-1;
return item;
}
}
void reverse()
{
int data;
do{
data=dequeue();
if(data==-1) break;
push(data);
}while(1);
do{
data=pop();
if(data==-1) break;
enqueue(data);
}while(1);
}
void main()
{
int ch,item;
printf("Enter the size of the queue..:");
scanf("%d",&n);
while(1)
{
printf("\nOperations:\n1. Enqueue\n2. Dequeue\n3.Display\n4. Reverse\n5. Exit");
printf("\nEnter the choice..:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter the element");
scanf("%d",&item);
enqueue(item);
break;
case 2:
item=dequeue();
if(item!=-1)
printf("removed element is %d\n",item);
else
printf("Queue Empty\n");
break;
case 3:
display();
break;
case 4:
reverse();
display();
break;
case 5:
exit(0);
default:
printf("There is no such operation");
}
}
}
******************************************************************************
16. Write a program to read two polynomials and store them using linked list. Calculate the sum
of the two polynomials and display the first polynomial, second polynomial and the resultant
polynomial.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int coeff,exp;
struct node *link;
}*A=NULL,*B=NULL,*S=NULL;
struct node * create()
{
struct node *TP=NULL,*temp=NULL,*LTP=NULL;
int n,coeff,exp,i;
printf("\n Enter no of Terms of Poly : ");
scanf("%d",&n);
printf("\n Enter Coefficint and Exponent of Poly in order(k1x^n+k2x^n-1..+knx^0 : ");
for(i=0;i<n;i++)
{
scanf("%d%d",&coeff,&exp);
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=coeff;
temp->exp=exp;
temp->link=NULL;
if(TP==NULL)
{
TP=temp;
LTP=temp;
}
else
{
LTP->link=temp;
LTP=temp;
}
}
return TP;
}
void display(struct node*temp)
{
while(temp!=NULL)
{
printf("%dx^%d ---> ",temp->coeff,temp->exp);
temp=temp->link;
}
printf("NULL\n");
}
struct node * polyadd(struct node*P1, struct node *P2)
{
struct node *P3=NULL,*lastP3=NULL,*temp=NULL;
if(P1==NULL) P3=P2;
else if(P2==NULL) P3=P1;
else
{
while(P1!=NULL && P2!= NULL)
{
if(P2->exp > P1->exp)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P2->coeff;
temp->exp=P2->exp;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P2=P2->link;
}
else if(P2->exp < P1->exp)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P1->coeff;
temp->exp=P1->exp;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P1=P1->link;
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P1->coeff+P2->coeff;
temp->exp=P1->exp;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P1=P1->link;
P2=P2->link;
}
}
while(P1!=NULL)
{
lastP3->link=P1;
lastP3=P1;
P1=P1->link;
}
while(P2!=NULL)
{
lastP3->link=P2;
lastP3=P2;
P2=P2->link;
}
}
return P3;
}
void main()
{
int ch;
do
{
printf("\n\n 1. Create Poly \n 2. Add Poly \n 3. Display Poly \n 4. Exit ");
printf("\n Enter Option : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
A=create();
B=create();
break;
case 2:
S=polyadd(A,B);
display(S);
break;
case 3:
printf("\n Polynomial A : ");
display(A);
printf("\n Polynomial B : ");
display(B);
break;
case 4:
exit(0);
default :
printf("\n Invalid Option !!!");
}
}
while(1);
}
***********************************************************************************
17. Write a program to read two polynomials and store them using linked list. Find the product
of two polynomials and store the result using linked list. Display the resultant polynomial.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int coeff,exp;
struct node *link;
}*A=NULL,*B=NULL,*S=NULL,*P=NULL;
struct node * create()
{
struct node *TP=NULL,*temp=NULL,*LTP=NULL;
int n,coeff,exp,i;
printf("\n Enter no of Terms of Poly : ");
scanf("%d",&n);
printf("\n Enter Coefficint and Exponent of Poly in order(k1x^n+k2x^n-1..+knx^0 : ");
for(i=0;i<n;i++)
{
scanf("%d%d",&coeff,&exp);
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=coeff;
temp->exp=exp;
temp->link=NULL;
if(TP==NULL)
{
TP=temp;
LTP=temp;
}
else
{
LTP->link=temp;
LTP=temp;
}
}
return TP;
}
void display(struct node*temp)
{
while(temp!=NULL)
{
printf("%dx^%d ---> ",temp->coeff,temp->exp);
temp=temp->link;
}
printf("NULL\n");
}
struct node * polyadd(struct node*P1, struct node *P2)
{
struct node *P3=NULL,*lastP3=NULL,*temp=NULL;
if(P1==NULL) P3=P2;
else if(P2==NULL) P3=P1;
else
{
while(P1!=NULL && P2!= NULL)
{
if(P2->exp > P1->exp)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P2->coeff;
temp->exp=P2->exp;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P2=P2->link;
}
else if(P2->exp < P1->exp)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P1->coeff;
temp->exp=P1->exp;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P1=P1->link;
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P1->coeff+P2->coeff;
temp->exp=P1->exp;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P1=P1->link;
P2=P2->link;
}
}
while(P1!=NULL)
{
lastP3->link=P1;
lastP3=P1;
P1=P1->link;
}
while(P2!=NULL)
{
lastP3->link=P2;
lastP3=P2;
P2=P2->link;
}
}
return P3;
}
struct node *polymult(struct node *P1,struct node *P2)
{
struct node *CTEMP,*LCTEMP,*P=NULL,*temp;
while(P1!=NULL)
{
P2=B;
CTEMP=NULL;
while(P2!=NULL)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->link=NULL;
temp->coeff=P1->coeff*P2->coeff;
temp->exp=P1->exp+P2->exp;
if(CTEMP==NULL) {CTEMP=temp;LCTEMP=temp;}
else{LCTEMP->link=temp;LCTEMP=temp;}
P2=P2->link;
}
display(CTEMP);
P=polyadd(P,CTEMP);
P1=P1->link;
}
return P;
}
void main()
{
int ch;
do
{
printf("\n\n 1. Create Poly \n 2. Multiply Poly \n 3. Display Poly \n 4. Exit ");
printf("\n Enter Option : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
A=create();
B=create();
break;
case 2:
P=polymult(A,B);
printf("Polinomial Product..\n");
display(P);
break;
case 3:
printf("\n Polynomial A : ");
display(A);
printf("\n Polynomial B : ");
display(B);
break;
case 4:
exit(0);
default :
printf("\n Invalid Option !!!");
}
}
while(1);
}
***********************************************************************************
18. Write a program for addition of polynomials containing two variables using linked list.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int coeff,exp1,exp2;
struct node *link;
}*A=NULL,*B=NULL,*S=NULL;
struct node * create()
{
struct node *TP=NULL,*temp=NULL,*LTP=NULL;
int n,coeff,exp1,exp2,i;
printf("\n Enter no of Terms of Poly : ");
scanf("%d",&n);
printf("\n Enter Coefficint and Exponent of Poly in order(k1x^ny^n+k2x^n-1y^n-1..+knx^0y^0 : ");
for(i=0;i<n;i++)
{
scanf("%d%d%d",&coeff,&exp1,&exp2);
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=coeff;
temp->exp1=exp1;
temp->exp2=exp2;
temp->link=NULL;
if(TP==NULL)
{
TP=temp;
LTP=temp;
}
else
{
LTP->link=temp;
LTP=temp;
}
}
return TP;
}
void display(struct node*temp)
{
while(temp!=NULL)
{
printf("%dx^%dy^%d---> ",temp->coeff,temp->exp1,temp->exp2);
temp=temp->link;
}
printf("NULL\n");
}
struct node * polyadd(struct node*P1, struct node *P2)
{
struct node *P3=NULL,*lastP3=NULL,*temp=NULL,*P2T=P2;
if(P1==NULL) P3=P2;
else if(P2==NULL) P3=P1;
else
{
while(P1!=NULL)
{
while(P2!=NULL)
{
if(P1->exp1==P2->exp1 && P1->exp2==P2->exp2)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P2->coeff+P1->coeff;
temp->exp1=P1->exp1;
temp->exp2=P1->exp2;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
P2->coeff=0;
break;
}
else P2=P2->link;
}
if(P2==NULL)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P1->coeff;
temp->exp1=P1->exp1;
temp->exp2=P1->exp2;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
}
P1=P1->link;
}
P2=P2T;
while(P2!=NULL)
{ if (P2->coeff!=0)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->coeff=P2->coeff;
temp->exp1=P2->exp1;
temp->exp2=P2->exp2;
temp->link=NULL;
if(P3==NULL)
{
P3=temp;
lastP3=temp;
}
else
{
lastP3->link=temp;
lastP3=temp;
}
}
P2=P2->link;
}
}
return P3;
}
void main()
{
int ch;
do
{
printf("\n\n 1. Create Poly \n 2. Add Poly \n 3. Display Poly \n 4. Exit ");
printf("\n Enter Option : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
A=create();
B=create();
break;
case 2:
S=polyadd(A,B);
printf("Polynomial Sum..\n");
display(S);
break;
case 3:
printf("\n Polynomial A : ");
display(A);
printf("\n Polynomial B : ");
display(B);
break;
case 4:
exit(0);
default :
printf("\n Invalid Option !!!");
}
}
while(1);
}
*****************************************************************************
19. The details of students(number, name, total-mark) are to be stored in a linked list. Write
functions for the following operations:
19.1.Insert
19.2.Delete
19.3.Search
19.4.Sort on the basis of number
19.5.Display the resultant list after every operation
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int n=0;
struct student
{
int number;
char name[25];
int total_mark;
struct student *link;
}*first=NULL,*last=NULL,*temp=NULL,*trav=NULL,*prev=NULL;
void display()
{
temp=first;
printf("\nThe details of students are:\n");
printf("|Number:");
printf("|Name:");
printf("|Total_mark:|\n");
while(temp!=NULL)
{
printf("|%d",temp->number);
printf("|%s",temp->name);
printf("|%d|",temp->total_mark);
temp=temp->link;
printf("--->");
}
printf(" NULL\n");
}
void create()
{
temp=(struct student*)malloc(sizeof(struct student));
printf("Enter the number:");
scanf("%d",&temp->number);
printf("Enter the name:");
scanf("%s",temp->name);
printf("Enter the total mark:");
scanf("%d",&temp->total_mark);
temp->link=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
{
last->link=temp;
last=temp;
}
n++;
display();
}
void del_from_begin()
{
if(first==NULL)
{
printf("List is empty");
}
else
{
trav=first;
first=first->link;
free(trav);
}
}
void del_from_end()
{
if(first==NULL)
{
printf("List is empty");
}
else
{
prev=NULL;
trav=first;
while(trav->link!=NULL)
{
prev=trav;
trav=trav->link;
}
prev->link=NULL;
last=prev;
free(trav);
}
}
void del_by_number()
{
int no,i=0,flag=0;
printf("Enter the number to be removed:");
scanf("%d",&no);
prev=NULL;
trav=first;
while(trav!=NULL)
{
if(trav->number==no)
{
flag=1;
if(trav==first)
{
del_from_begin();
}
else if(trav==last)
{
del_from_end();
}
else
{
prev->link=trav->link;
free(trav);
break;
}
}
else
{
prev=trav;
trav=trav->link;
}
}
if(flag==0)
{
printf("The details of student not found!");
n++;
}
n--;
display();
}
void search_by_number()
{
int no,i=0,flag=0;
printf("Enter the number to be searched:");
scanf("%d",&no);
prev=NULL;
trav=first;
while(trav!=NULL)
{
if(trav->number==no)
{
flag=1;
break;
}
else
{
prev=trav;
trav=trav->link;
}
}
if(flag==0)
{
printf("The details of student not found!");
}
else
{
printf("\nThe details of student number %d is:\n",trav->number);
printf("|Number:");
printf("|Name:");
printf("|Total_mark:|\n");
printf("|%d",trav->number);
printf("|%s",trav->name);
printf("|%d|",trav->total_mark);
}
}
void sort()
{
int i,j,num,tot;
char name[25];
for (i = 0; i < n-1; i++)
{
trav=first;
for (j = 0; j < n-i-1; j++)
{
if(trav->number>trav->link->number)
{
num=trav->number;
trav->number=trav->link->number;
trav->link->number=num;
strcpy(name,trav->name);
strcpy(trav->name,trav->link->name);
strcpy(trav->link->name,name);
tot=trav->total_mark;
trav->total_mark=trav->link->total_mark;
trav->link->total_mark=tot;
}
trav=trav->link;
}
}
display();
}
void main()
{
int ch;
do
{
printf("\nMenu\n----\n1. Insert\n2. Delete by number\n3. Search by number\n4. Sort\n5. Exit");
printf("\nEnter the choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
create();
break;
case 2:
del_by_number();
break;
case 3:
search_by_number();
break;
case 4:
sort();
break;
case 5:
exit(0);
default:
printf("There is no such operation:");
}
}
while(1);
}
*******************************************************************************
20. Create a Doubly Linked List from a string taking each character from the string. Check if the
given string is palindrome in an efficient method.
given string is palindrome in an efficient method.
struct node
{
char c;
struct node *fron;
struct node *back;
}*head=NULL,*tail=NULL; // to pointer head point to first node & tell point to last node
//initialy list is empty so head=tell=NULL
typedef struct node node;
int create(char ch) // creating double link list
{
node *temp,*r;
temp=head;
r=(node*)malloc(sizeof(node)); // allocating space node dynamicaly
r->c=ch;
if(head == NULL)
{
head=r;
tail=r;
head->fron=NULL;
head->back=NULL;
}
else
{
tail->fron=r;
r->back=tail;
tail=tail->fron;
tail->fron=NULL;
}
}
display()
{
node *temp;
temp=head;
printf("\n\n\t");
while(temp != NULL) // traverse list & print volue
{
printf("%c-->",temp->c);
temp=temp->fron;
}
}
check(int n) // funtion check our requrement
{
node *tf,*tt;
tf=head;
tt=tail;
while(n/2 > 0)
{
if(tf->c == tt->c)
{
tf=tf->fron;
tt=tt->back;
}
else
{
printf("\n\n\t not a palidrome :???");
exit(0);
}
n--;
}
printf("\n\n\t it is palidrome !!!!");
}
main()
{
char arr[200];
int n,i;
printf("\n enter string to check :");
scanf("%s",arr);
n=strlen(arr); // calculating length of string
printf("\n length of string is %d",n);
for(i=0;i<n;i++)
{
create(arr[i]); // creating a double ling list with each node containing a single char
}
display();
check(n);
}
*****************************************************************************
21. Create a binary tree with the following operations21.1.Insert a new node
21.2.Inorder traversal.
21.3.Preorder traversal.
21.4.Postorder traversal.
21.5.Delete a node.
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node Node;
// Inorder traversal
void inorder(Node *root)
{
if (root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}
// Preorder traversal
void preorder(Node *root) {
if (root == NULL) return;
printf("%d ->", root->data);
preorder(root->left);
preorder(root->right);
}
// Postorder traversal
void postorder(Node *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ->", root->data);
}
// Create a new Node
Node* createNode(value) {
Node *newNode = malloc(sizeof(Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert on the left of the node
Node* insertLeft(Node *root, int value) {
root->left = createNode(value);
return root->left;
}
// Insert on the right of the node
Node* insertRight(Node *root, int value) {
root->right = createNode(value);
return root->right;
}
int main() {
Node* root = createNode(50);
insertLeft(root, 20);
insertRight(root, 30);
insertLeft(root->left, 40);
insertRight(root->left, 10);
printf("Inorder traversal \n");
inorder(root);
printf("\nPreorder traversal \n");
preorder(root);
printf("\nPostorder traversal \n");
postorder(root);
}
****************************************************************************
22. Write a program to create a binary search tree and find the number of leaf nodes
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
struct node
{
int data;
struct node *lchild;
struct node *rchild;
}*root=NULL;
typedef struct node Node;
void insert()
{
Node *t;
t=(Node *)malloc(sizeof(Node));
printf("Enter data....");
scanf("%d",&t->data);
t->lchild=NULL;
t->rchild=NULL;
if(root==NULL) root=t;
else
{
Node *pre,*cur;
cur=root;
while(1)
{
if(t->data<cur->data) { pre=cur;cur=cur->lchild;if(cur==NULL) {pre->lchild=t;break;}}
else if(t->data>cur->data){ pre=cur;cur=cur->rchild;if(cur==NULL) {pre->rchild=t;break;}}
else { printf("Invalid Input");exit(0);}
}
}
}
void search()
{ int key;
int f=0;
int nc=0;
printf("Enter key to serach...");
scanf("%d",&key);
Node *cur=root;
while(cur!=NULL)
{ nc++;
if(cur->data==key) {f=1;break;}
if(key<cur->data) cur=cur->lchild;
else if(key>cur->data) cur=cur->rchild;
}
if(f)printf("Keyfound!!! number of comaprisons %d",nc);else printf("key Not found...");
}
void inorder(Node *r)
{
if(r!=NULL)
{
inorder(r->lchild);
printf("<--> %d",r->data);
inorder(r->rchild);
}
}
count(Node *t)
{
if(t == NULL)
return 0;
if(t->lchild == NULL && t->rchild==NULL)
return 1;
else
return count(t->lchild)+count(t->rchild);
}
main()
{int op,cnt=0;
do
{
printf("\n.menu\n1.insert\n2.inorder\n3.count leaves\n4.exit\nenter option\n");
scanf("%d",&op);
switch(op)
{
case 1:insert();break;
case 2:inorder(root);break;
case 3:cnt=count(root);printf("Number of leaves=%d",cnt);break;
}
}
while(op!=4);
}
****************************************************************************
23. Create a binary search tree with the following operations:23.1.Insert a new node .
23.2.Inorder traversal.
23.3.Preorder traversal.
23.4.Postorder traversal.
23.5.Delete a node.
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
struct node
{
int data;
struct node *lchild;
struct node *rchild;
}*root=NULL;
typedef struct node Node;
void insert()
{
Node *t;
t=(Node *)malloc(sizeof(Node));
printf("Enter data....");
scanf("%d",&t->data);
t->lchild=NULL;
t->rchild=NULL;
if(root==NULL) root=t;
else
{
Node *pre,*cur;
cur=root;
while(1)
{
if(t->data<cur->data) { pre=cur;cur=cur->lchild;if(cur==NULL) {pre->lchild=t;break;}}
else if(t->data>cur->data){ pre=cur;cur=cur->rchild;if(cur==NULL) {pre->rchild=t;break;}}
else { printf("Invalid Input");exit(0);}
}
}
}
void search()
{ int key;
int f=0;
int nc=0;
printf("Enter key to serach...");
scanf("%d",&key);
Node *cur=root;
while(cur!=NULL)
{ nc++;
if(cur->data==key) {f=1;break;}
if(key<cur->data) cur=cur->lchild;
else if(key>cur->data) cur=cur->rchild;
}
if(f)printf("Keyfound!!! number of comaprisons %d",nc);else printf("key Not found...");
}
void inorder(Node *r)
{
if(r!=NULL)
{
inorder(r->lchild);
printf("<--> %d",r->data);
inorder(r->rchild);
}
}
void preorder(Node *r)
{
if(r!=NULL)
{
printf("<--> %d",r->data);
preorder(r->lchild);
preorder(r->rchild);
}
}
void postorder(Node *r)
{
if(r!=NULL)
{
preorder(r->lchild);
preorder(r->rchild);
printf("<-->%d",r->data);
}
}
Node* insuc(Node *r)
{
Node *q=NULL;
while(r->lchild!=NULL)
{
q=r; r=r->lchild;
}
if(r->rchild!=NULL) q->lchild=r->rchild;else q->lchild=NULL;
return(r);
}
void delete()
{
printf("Enter key to delete...");
int d;
scanf("%d",&d);
Node *cur=root;
int f=0;
Node *pr=NULL;
while(cur!=NULL)
{
if(cur->data==d) {f=1;break;}
if(d<cur->data) {pr=cur; cur=cur->lchild;}
else if(d>cur->data){pr=cur; cur=cur->rchild;}
}
if(f==0) printf("key not found..!!!");
else
{
Node *t=cur;// node to be deleted...
//leaf nodes....
if(t->lchild==NULL&&t->rchild==NULL)
{
if(pr->lchild==t) pr->lchild=NULL;
if(pr->rchild==t) pr->rchild=NULL;
}
else if(t->lchild==NULL) // only right child exist
{
if(pr->lchild==t) pr->lchild=t->rchild;
if(pr->rchild==t) pr->rchild=t->rchild;
}
else if(t->rchild==NULL) // only left child exist
{
if(pr->lchild==t) pr->lchild=t->lchild;
if(pr->rchild==t) pr->rchild=t->lchild;
}
else //both left and right child
{
Node *in=t->rchild;
if(in->lchild==NULL) {t->data=in->data;t->rchild=in->rchild;}
else {in=insuc(t->rchild);t->data=in->data;}
}
}//end of found else
}// end of delete fn
main()
{int op;
do
{
printf("\n.menu\n1.insert\n2.preorder\n3.postorder\n4.inorder\n5.delete\n6.search\n7.exit\nenter option\n");
scanf("%d",&op);
switch(op)
{
case 1:insert();break;
case 2:preorder(root);break;
case 3:postorder(root);break;
case 4:inorder(root);break;
case 5:delete();break;
case 6:search();break;
}
}
while(op!=7);
}
****************************************************************************
24.Write a program to sort a set of numbers using a binary tree.#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
struct node
{
int data;
struct node *lchild;
struct node *rchild;
}*root=NULL;
typedef struct node Node;
void insert(int d)
{
Node *t;
t=(Node *)malloc(sizeof(Node));
t->data=d;
t->lchild=NULL;
t->rchild=NULL;
if(root==NULL) root=t;
else
{
Node *pre,*cur;
cur=root;
while(1)
{
if(t->data<cur->data) { pre=cur;cur=cur->lchild;if(cur==NULL) {pre->lchild=t;break;}}
else if(t->data>cur->data){ pre=cur;cur=cur->rchild;if(cur==NULL) {pre->rchild=t;break;}}
else { printf("Invalid Input");exit(0);}
}
}
}
void inorder(Node *r)
{
if(r!=NULL)
{
inorder(r->lchild);
printf("%d-->",r->data);
inorder(r->rchild);
}
}
int main()
{
int i,n,d;
printf("Enter the number of elements\n");
scanf("%d",&n);
printf("Enter the elements\n");
for(i=0;i<n;i++)
{ scanf("%d",&d);insert(d);}
printf("Sorted List\n");
inorder(root);
}
****************************************************************************
25. Represent any given graph and
25.1.Perform a depth first search .
25.2.Perform a breadth first search
Depth first search .
#include <stdio.h>struct vertex{
int num;
int visit;
}S[50],v[50],t;
int adj[50][50],n,top=-1;
void push(struct vertex v)
{
top++;
S[top]=v;
}
struct vertex pop()
{
return(S[top--]);
}
int sempty()
{
if(top==-1) return 1;else return 0;
}
void dfs()
{ int i;
push(v[1]);v[1].visit=1;
while(!sempty())
{
t=pop();
printf("V%d-------->",t.num);
for(i=n;i>=1;i--) if(adj[t.num][i]==1 && v[i].visit==0) {push(v[i]);v[i].visit=1;}
}
}
void read()
{ int ad,i;
printf("Enter the Number of vertices\n");
scanf("%d",&n);
// storing element from [1][1]
//// assuming the vertices are numbered v1 v2..vn and we will enter only the index 1,2...n
for(i=1;i<=n;i++) {v[i].num=i;v[i].visit=0;}
for(i=1;i<=n;i++)
{
printf("Enter the list of vertices adjacent to v%d -1 to stop\n",i);
while(1)
{
scanf("%d",&ad);
if(ad==-1) break;
adj[i][ad]=1;
}
}
}//end of read
void disp()
{
printf("Adjacency Matrix..\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%5d",adj[i][j]);
printf("\n");
}
}
int main()
{
read();
disp();
printf("Depth First Search Result\n");
dfs();
return 0;
}
Breadth first search
#include <stdio.h>struct vertex{
int num;
int visit;
}Q[50],v[50],t;
int adj[50][50],n,f=-1,r=-1;
void addq(struct vertex v)
{
r++;
Q[r]=v;
}
struct vertex deleteq()
{
++f;
return(Q[f]);
}
int qempty()
{
if(f==r) return 1;else return 0;
}
void bfs()
{ int i;
addq(v[1]);v[1].visit=1;
while(!qempty())
{
t=deleteq();
printf("V%d-------->",t.num);
for(i=1;i<=n;i++) if(adj[t.num][i]==1 && v[i].visit==0) {addq(v[i]);v[i].visit=1;}
}
}
void read()
{ int ad,i;
printf("Enter the Number of vertices\n");
scanf("%d",&n);
// storing element from [1][1]
//// assuming the vertices are numbered v1 v2..vn and we will enter only the index 1,2...n
for(i=1;i<=n;i++) {v[i].num=i;v[i].visit=0;}
for(i=1;i<=n;i++)
{
printf("Enter the list of vertices adjacent to v%d -1 to stop\n",i);
while(1)
{
scanf("%d",&ad);
if(ad==-1) break;
adj[i][ad]=1;
}
}
}//end of read
void disp()
{
printf("Adjacency Matrix..\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%5d",adj[i][j]);
printf("\n");
}
}
int main()
{
read();
disp();
printf("Breadth First Search Result\n");
bfs();
return 0;
}
****************************************************************************
27. Write a program to sort a set of numbers using Heap sort and find a particular number from
the sorted set using Binary Search.
the sorted set using Binary Search.
#include <stdio.h>
#include<conio.h>
void bin_search(int arr[],int n,int search)
{
int c, first, last, middle;
first = 0;
last = n - 1;
while (first <= last) {
middle = (first+last)/2;
if (arr[middle] < search)
first = middle + 1;
else if (arr[middle] == search) {
printf("\n%d Element found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
}
if (first > last)
printf("Not found! %d isn't present in the list.\n", search);
}
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
int i;
for (i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
void main() {
int arr[50],n,i,search;
printf("\nEnter the number of elements:");
scanf("%d",&n);
printf("Enter array elements\n");
for (i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("\n Array elements are\n");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
printf("Enter the element to be searched..:");
scanf("%d",&search);
bin_search(arr,n,search);
getch();
}
****************************************************************************
28. Implement a Hash table using Chaining method. Let the size of hash table be 10 so that the
index varies from 0 to 9.
index varies from 0 to 9.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define size 10
struct node
{
int data;
struct node *next;
};
struct node *chain[size];
void init()
{
int i;
for(i = 0; i < size; i++)
chain[i] = NULL;
}
void insert(int value)
{
//create a newnode with value
int key;
struct node *newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->next = NULL;
//calculate hash key
key = value % size;
//check if chain[key] is empty
if(chain[key] == NULL)
chain[key] = newNode;
//collision
else
{
//add the node at the end of chain[key].
struct node *temp = chain[key];
while(temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
printf("Entered Value added to hash table\n");
}
void printhashtable()
{
int i;
for(i = 0; i < size; i++)
{
struct node *temp = chain[i];
printf("chain[%d]-->",i);
while(temp)
{
printf("%d -->",temp->data);
temp = temp->next;
}
printf("NULL\n");
}
}
void main()
{
//init array of list to NULL
int i,num,val;
init();
printf("Enter the number of elements\n");
scanf("%d",&num);
for(i=0;i<num;i++)
{
printf("Enter Elements\n");
scanf("%d",&val);
insert(val);
}
printf("\n\n The hash table is\n\n");
printhashtable();
getch();
}
****************************************************************************
29. Implement a Hash table that uses Linear Probing for collision resolution#include<stdio.h>
#include<stdlib.h>
/* to store a data (consisting of key and value) in hash table array */
struct item
{
int key;
int value;
};
/* each hash table item has a flag (status) and data (consisting of key and value) */
struct hashtable_item
{
int flag;
/*
* flag = 0 : data does not exist
* flag = 1 : data exists
* flag = 2 : data existed at least once
*/
struct item *data;
};
int size = 0;
int max = 10;
struct hashtable_item array[10];
/* initializing hash table array */
void init_array()
{
int i;
for (i = 0; i < max; i++)
{
array[i].flag = 0;
array[i].data = NULL;
}
}
/* to every key, it will generate a corresponding index */
int hashcode(int key)
{
return (key % max);
}
/* to insert an element in the hash table */
void insert(int key, int value)
{
int index = hashcode(key);
int i = index;
/* creating new item to insert in the hash table array */
struct item *new_item = (struct item*) malloc(sizeof(struct item));
new_item->key = key;
new_item->value = value;
/* probing through the array until we reach an empty space */
while (array[i].flag == 1)
{
if (array[i].data->key == key)
{
/* case where already existing key matches the given key */
printf("\n Key already exists, hence updating its value \n");
array[i].data->value = value;
return;
}
i = (i + 1) % max;
if (i == index)
{
printf("\n Hash table is full, cannot insert any more item \n");
return;
}
}
array[i].flag = 1;
array[i].data = new_item;
size++;
printf("\n Key (%d) has been inserted \n", key);
}
/* to remove an element from the hash table */
void remove_element(int key)
{
int index = hashcode(key);
int i = index;
/* probing through array until we reach an empty space where not even once an element had been present */
while (array[i].flag != 0)
{
if (array[i].flag == 1 && array[i].data->key == key )
{
// case when data key matches the given key
array[i].flag = 2;
array[i].data = NULL;
size--;
printf("\n Key (%d) has been removed \n", key);
return;
}
i = (i + 1) % max;
if (i == index)
{
break;
}
}
printf("\n This key does not exist \n");
}
/* to display all the elements of hash table */
void display()
{
int i;
for (i = 0; i < max; i++)
{
struct item *current = (struct item*) array[i].data;
if (current == NULL)
{
printf("\n Array[%d] has no elements \n", i);
}
else
{
printf("\n Array[%d] has elements -: \n %d (key) and %d(value) ", i, current->key, current->value);
}
}
}
int size_of_hashtable()
{
return size;
}
void main()
{
int choice, key, value, n;
init_array();
do {
printf("MENU-: \n1.Inserting item in the Hashtable"
"\n2.Removing item from the Hashtable"
"\n3.Check the size of Hashtable"
"\n4.Display Hashtable"
"\n5.Exit"
"\n\n Please enter your choice-:");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Inserting element in Hashtable\n");
printf("Enter key and value-:\t");
scanf("%d%d", &key, &value);
insert(key, value);
break;
case 2:
printf("Deleting in Hashtable \n Enter the key to delete-:");
scanf("%d", &key);
remove_element(key);
break;
case 3:
n = size_of_hashtable();
printf("Size of Hashtable is-:%d\n", n);
break;
case 4:
display();
break;
case 5:
exit(0);
break;
default:
printf("Wrong Input\n");
}
}while(1);
}
****************************************************************************
Comments
Post a Comment