Write a program to implement a linked stack.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *link;
};
typedef struct node *NODE;
NODE first=NULL;
NODE getnode()
{
NODE x;
x=(NODE) malloc(sizeof(NODE));
if(x==NULL)
{
printf("out of memory\n");
exit(0);
}
return x;
}
void freenode(NODE x)
{
free(x);
}
NODE insert_front(NODE first)
{
NODE temp;
int item;
printf("\nThe value to insert\n");
scanf("%d",&item);
temp=getnode();
temp->info=item;
temp->link=first;
first=temp;
printf("%d is inserted into list\n",temp->info);;
return first;
}
NODE delete_front(NODE first)
{
NODE cur;
if(first==NULL)
{
printf("List is underflow\n");
return first;
}
cur=first;
first=first->link;
printf("%d is deleted from list\n",cur->info);
freenode(cur);
return first;
}
NODE display(NODE first)
{
NODE cur;
if(first==NULL)
{
printf("List is empty\n");
return 0;
}
printf("Contents of the list are\n");
cur=first;
while(cur!=NULL)
{
printf("%d\t",cur->info);
cur=cur->link;
}
printf("\n");
}
void main()
{
int option,item;
do
{
printf("\n****Linked Satck operations****");
printf("\n1.push\n2.pop \n 3.Display \n4:Exit\n");
printf("Enter your choice");
scanf("%d",&option);
switch(option)
{
case 1:first=insert_front(first);
break;
case 2:first=delete_front(first);
break;
case 3:display(first);
break;
case 4:break;
default:printf("Invalid option\n");
}
}while(option!=4);
}
Write a program to implement a linked queue.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *link;
};
typedef struct node *NODE;
NODE first=NULL;
NODE getnode()
{
NODE x;
x=(NODE) malloc(sizeof(NODE));
if(x==NULL)
{
printf("out of memory\n");
exit(0);
}
return x;
}
void freenode(NODE x)
{
free(x);
}
NODE insert_rear(NODE first)
{
NODE temp,cur;
int item;
printf("\nThe value to insert\n");
scanf("%d",&item);
temp=getnode();
temp->info=item;
cur=first;
while(cur->link!=NULL)
{
cur=cur->link;
}
cur->link=temp;
temp->link=NULL;
printf("%d is inserted into list\n",temp->info);
return first;
}
NODE delete_front(NODE first)
{
NODE cur;
if(first==NULL)
{
printf("List is underflow\n");
return first;
}
cur=first;
first=first->link;
printf("%d is deleted from list\n",cur->info);
freenode(cur);
return first;
}
NODE display(NODE first)
{
NODE cur;
if(first==NULL)
{
printf("List is empty\n");
return 0;
}
printf("Contents of the list are\n");
cur=first;
while(cur!=NULL)
{
printf("%d\t",cur->info);
cur=cur->link;
}
printf("\n");
}
void main()
{
int option,item;
do
{
printf("\n****Linked Queue operations****");
printf("\n1.Insert\n2.Delete\n3.Display \n4:Exit\n");
printf("Enter your choice");
scanf("%d",&option);
switch(option)
{
case 1:first=insert_rear(first);
break;
case 2:first=delete_front(first);
break;
case 3:display(first);
break;
case 4:break;
default:printf("Invalid option\n");
}
}while(option!=4);
}
Write a program to store a polynomial using linked list. Also, perform addition
and subtraction on two polynomials.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
int coeff;
struct node *link;
};
typedef struct node * NODE;
NODE f1 = NULL;
NODE f2 = NULL;
NODE f3 = NULL;
NODE f4 = NULL;
NODE last3 = NULL;
NODE read_poly(NODE);
NODE display_poly(NODE);
NODE add_poly(NODE, NODE,NODE);
NODE sub_poly(NODE, NODE, NODE);
NODE add_node(NODE, int, int);
int main()
{
printf("Enter the first polynomial\n");
f1=read_poly(f1);
printf("Enter the second polynomial\n");
f2=read_poly(f2);
printf("first polynomial\n");
display_poly(f1);
printf("second polynomial\n");
display_poly(f2);
printf("Addidtion of two polynomials is\n");
f3 = add_poly(f1, f2, f3);
display_poly(f3);
printf("Subtraction of two polynomials is\n");
f4= sub_poly(f1, f2, f4);
display_poly(f4);
}
NODE read_poly(NODE first)
{
NODE temp, ptr;
int n, num, c;
printf("\n Enter the number of terms : ");
scanf("%d",&num);
while(num>0)
{
printf("Enter the coefficient:\n");
scanf("%d",&n);
printf("Enter its power:\n");
scanf("%d",&c);
if(first==NULL)
{
temp = (NODE )malloc(sizeof(NODE));
temp -> num = n;
temp -> coeff = c;
temp -> link = NULL;
first = temp;
}
else
{
ptr = first;
while(ptr -> link != NULL)
ptr = ptr -> link;
temp = (NODE)malloc(sizeof(NODE));
temp-> num = n;
temp -> coeff = c;
temp -> link = NULL;
ptr -> link = temp;
}
num--;
}
return first;
}
NODE display_poly(NODE first)
{
NODE ptr;
ptr = first;
while(ptr != NULL)
{
printf("%dX^%d\t", ptr -> num, ptr -> coeff);
ptr = ptr -> link;
}
printf("\n");
return first;
}
NODE add_poly(NODE f1, NODE f2, NODE f3)
{
NODE ptr1, ptr2;
int sum_num, c;
ptr1 = f1, ptr2 = f2;
while(ptr1 != NULL && ptr2 != NULL)
{
if(ptr1 -> coeff == ptr2 -> coeff)
{
sum_num = ptr1 -> num + ptr2 -> num;
f3 = add_node(f3, sum_num, ptr1 -> coeff);
ptr1 = ptr1 -> link;
ptr2 = ptr2 -> link;
}
else if(ptr1 -> coeff > ptr2 -> coeff)
{
f3 = add_node(f3, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> link;
}
else if(ptr1 -> coeff < ptr2 -> coeff)
{
f3 = add_node(f3, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> link;
}
}
if(ptr1 == NULL)
{
while(ptr2 != NULL)
{
f3 = add_node(f3, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> link;
}
}
if(ptr2 == NULL)
{
while(ptr1 != NULL)
{
f3 = add_node(f3, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> link;
}
}
return f3;
}
NODE sub_poly(NODE f1, NODE f2, NODE f4)
{
NODE ptr1, ptr2;
int sum_num, c;
ptr1 = f1, ptr2 = f2;
while(ptr1 != NULL && ptr2 != NULL)
{
if(ptr1 -> coeff == ptr2 -> coeff)
{
sum_num = ptr1 -> num - ptr2 -> num;
f4= add_node(f4, sum_num, ptr1 -> coeff);
ptr1 = ptr1 -> link;
ptr2 = ptr2 -> link;
}
else if(ptr1 -> coeff > ptr2 -> coeff)
{
f4 = add_node(f4, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> link;
}
else if(ptr1 -> coeff < ptr2 -> coeff)
{
f4 = add_node(f4, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> link;
}
}
if(ptr1 == NULL)
{
while(ptr2 != NULL)
{
f4 = add_node(f4, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> link;
}
}
if(ptr2 == NULL)
{
while(ptr1 != NULL)
{
f4 = add_node(f4, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> link;
}
}
return f4;
}
NODE add_node(NODE first, int n, int c)
{
NODE ptr, temp;
if(first == NULL)
{
temp = (NODE)malloc(sizeof(NODE));
temp -> num = n;
temp -> coeff = c;
temp -> link = NULL;
first = temp;
return first;
}
else
{
ptr = first;
while(ptr -> link != NULL)
ptr = ptr -> link;
temp = (NODE)malloc(sizeof(NODE));
temp -> num = n;
temp -> coeff = c;
temp -> link = NULL;
ptr -> link = temp;
return first;
}
}
