Algorithm Pseudocode for solving polynomial using singly Linkedlist
INPUT: HEADER1 AND HEADER2 ARE POINTER TO THE HEADER NODE OF THE LINKEDLISTS
OUTPUT: MERGED LINKEDLIST POLYNOMIAL RESULT
DATA STRUCTURE: SINGLY LINKEDLIST
STEP 1: START
STEP 2: PTR1=HEADER1->LINK ,PTR2=HEADER2->LINK ,PTR3=HEADER3->LINK
STEP 3: WHILE(PTR1!=NULL&&PTR2!=NULL)
STEP 4: NEW=NEWNODE(NODE)
STEP 4: IF(PTR1->EXP<PTR2->EXP)
STEP 5: NEW->EXP=PTR1->EXP
STEP 6: NEW->COEFF=PTR1->COEFF+PTR2->COEFF
STEP 7: NEW->LINK=NULL
STEP 8: PTR3->LINK=NEW
STEP 9: PTR3=NEW
STEP 10: PTR1=PTR1->LINK
STEP 11: ELSE IF(PTR1->EXP==PTR2->EXP)
STEP 12: NEW->EXP=PTR2->EXP
STEP 13: NEW->COEFF=PTR2->COEFF
STEP 14: NEW->LINK=NULL;
STEP 15: PTR3->LINK=NEW
STEP 16: PTR3-NEW
STEP 17: PTR1=PTR1->LINK
STEP 18: PTR2=PTR2->LINK
STEP 19: ELSE
STEP 20: NEW->EXP=PTR2->EXP
STEP 21: NEW->COEFF=PTR2->COEFF
STEP 22: NEW->LINK=NULL
STEP 23: PTR3->LINK=NEW
STEP 24: PTR3=NEW
STEP 25: PTR2=PTR2->LINK
STEP 26: ENDWHILE
STEP 27: WHILE(PTR1!=NULL)
STEP 28: NEW->DATA=PTR1->DATA
STEP 29: NEW->LINK=NULL
STEP 30: PTR3->LINK=NEW
STEP 31: PTR3=NEW
STEP 32: PTR1=PTR1->LINK
STEP 33: ENDWHILE
STEP 34: WHILE(PTR2!=NULL)
STEP 35: NEW->DATA=PTR2->DATA
STEP 36: NEW->LINK=NULL
STEP 37: PTR3->LINK=NEW
STEP 38: PTR3=NEW
STEP 39: PTR2=PTR2->LINK
STEP 40: ENDWHILE
STEP 41: END
This pseudocode represents the merging of two sorted singly linked lists into a third sorted linked list, commonly used for merging polynomial terms. Each node contains two fields: EXP (exponent) and COEFF (coefficient). Let’s break it down step by step:
STEP 1: START
- Begin the algorithm.
STEP 2: Initialization
PTR1
,PTR2
, andPTR3
are pointers for traversing three linked lists.PTR1
points to the first node of the first list (HEADER1->LINK
).PTR2
points to the first node of the second list (HEADER2->LINK
).PTR3
is used to construct the merged list, starting at the head of the third list (HEADER3->LINK
).
STEP 3: WHILE (PTR1 != NULL && PTR2 != NULL)
- Loop through both lists as long as neither is fully traversed.
Inside the WHILE loop: for merging polynomials represented as nodes in a linkedlist.
STEP 4: Allocate memory for a new node
- Create a new node to add to the merged list.
STEP 4-25: Compare Exponents
- IF (
PTR1->EXP < PTR2->EXP
)- Copy the exponent and coefficient from
PTR1
to the new node. - Add
PTR1->COEFF
andPTR2->COEFF
to compute the coefficient. - Update the links and move
PTR1
to the next node.
- Copy the exponent and coefficient from
- ELSE IF (
PTR1->EXP == PTR2->EXP
)- Both nodes have the same exponent.
- Copy the exponent and coefficient of either pointer (e.g.,
PTR2
) to the new node. - Move both
PTR1
andPTR2
to their respective next nodes.
- ELSE (
PTR1->EXP > PTR2->EXP
)- Copy the exponent and coefficient from
PTR2
to the new node. - Update the links and move
PTR2
to the next node.
- Copy the exponent and coefficient from
STEP 26: ENDWHILE
- Exit the loop when at least one of the lists has been fully traversed.
STEP 27-33: Add Remaining Nodes from List 1
- If nodes remain in
PTR1
(list 1), add them to the merged list by:- Copying the data from
PTR1
to the new node. - Updating the links and moving
PTR1
to the next node.
- Copying the data from
STEP 34-40: Add Remaining Nodes from List 2
- If nodes remain in
PTR2
(list 2), add them to the merged list in the same way as above.
STEP 41: END
- End the algorithm.
Key Points
- This algorithm assumes that both input lists are sorted by exponents (
EXP
). - The merged list will also be sorted.
- The
NEW->COEFF
calculation in step 6 may require additional clarification depending on whether coefficients should be summed for duplicate exponents.
Code for solving polynomial using Singly Linkedlist
The provided C program is designed to merge two polynomials represented as linked lists.
#include <stdio.h>
#include <stdlib.h>
int getnode(int);void display();void merge();void newnode();
int x, pos, n;
struct node
{
int coeff;
int exp;
struct node *link;
};
struct node *prev, *head, *news, *p, *ptr,*ptr1,*ptr2,*ptr3;
struct node *q1;
struct node *header, *header1,*header3,*header2;
struct node *q, *r, *s;
int main()
{
printf("ENTER THE LIMIT OF POLYNOMIAL 1: ");
scanf("%d", &n);
getnode(n);
header1=header;
printf("ENTER THE LIMIT OF POLYNOMIAL 2 ");
scanf("%d", &n);
getnode(n);
header2=header;
merge();
printf("THE MERGE LIST IS:");
display(header3);
return 0;
}
void display(struct node *head1)
{
struct node *ptr;
ptr = head1->link;
// ptr=header->link;
while (ptr != NULL)
{
printf("%d ", ptr->coeff);
printf("%d",ptr->exp);
ptr = ptr->link;
}
}
void newnode()
{
news=malloc(sizeof(struct node));
}
void merge()
{
header3=malloc(sizeof(struct node));
header3->link=news;
ptr1=header1->link;
ptr2=header2->link;
ptr3=header3;
while(ptr1!=NULL&&ptr2!=NULL)
{
if(ptr1->exp<ptr2->exp)
{
newnode();
news->exp=ptr1->exp;
news->coeff=ptr1->coeff+ptr2->coeff;
news->link=NULL;
ptr3->link=news;
ptr3=news;
ptr1=ptr1->link;
}
else if(ptr1->exp==ptr2->exp)
{
newnode();
news->exp=ptr2->exp;
news->coeff=ptr2->coeff;
news->link=NULL;
ptr3->link=news;
ptr3=news;
ptr1=ptr1->link;
ptr2=ptr2->link;
}
else{
newnode();
news->exp=ptr2->exp;
news->coeff=ptr2->coeff;
news->link=NULL;
ptr3->link=news;
ptr3=news;
ptr2=ptr2->link;
}
}
while(ptr1!=NULL)
{
newnode();
news->exp=ptr1->exp;
news->coeff=ptr1->coeff;
news->link=NULL;
ptr3->link=news;
ptr3=news;
ptr1=ptr1->link;
}
while(ptr2!=NULL)
{
newnode();
news->exp=ptr2->exp;
news->coeff=ptr2->coeff;
news->link=NULL;
ptr3->link=news;
ptr3=news;
ptr2=ptr2->link;
}
}
int getnode(int n)
{
header = malloc(sizeof(struct node));
head = NULL;
for (int i = 0; i < n; i++)
{
p = malloc(sizeof(struct node));
q1 = malloc(sizeof(struct node));
q = NULL;
printf("enter the coefficient");
scanf("%d", &p->coeff);
printf("enter the degree");
scanf("%d",&p->exp);
p->link = NULL;
if (head == NULL)
head = p;
else
prev->link = p;
prev = p;
}
header->link = head;
display(header);
return 0;
}
Explanation of the above program
Key Components
- Data Structure:
- Each polynomial is stored as a linked list where:
coeff
stores the coefficient of a term.exp
stores the exponent.link
points to the next node.
- Each polynomial is stored as a linked list where:
- Functions:
getnode(int n)
:- Creates a linked list of
n
terms based on user input.
- Creates a linked list of
display(struct node *head)
:- Prints the terms of the polynomial from the given linked list.
merge()
:- Merges two sorted polynomial linked lists (
header1
andheader2
) into a third sorted list (header3
).
- Merges two sorted polynomial linked lists (
newnode()
:- Allocates memory for a new node.
- Global Variables:
header1
,header2
: Headers for the two polynomials.header3
: Header for the merged polynomial.
Program Flow
- Input Polynomials:
- The program first asks for the number of terms in Polynomial 1, then collects the coefficients and exponents using
getnode()
. - This process is repeated for Polynomial 2.
- The program first asks for the number of terms in Polynomial 1, then collects the coefficients and exponents using
- Merging Polynomials:
- The
merge()
function iterates over both linked lists simultaneously. - It compares the exponents of the terms in the two polynomials:
- If the exponents are equal, the coefficients are added.
- If one exponent is smaller, the corresponding term is added to the merged list.
- Remaining terms from either polynomial are added at the end.
- The
- Display the Result:
- The merged polynomial is printed using
display()
.
- The merged polynomial is printed using
Output
user@computer$ : ENTER THE LIMIT OF POLYNOMIAL 1: 3
enter the coefficient1
enter the degree2
enter the coefficient3
enter the degree3
enter the coefficient4
enter the degree4
1 23 34 4ENTER THE LIMIT OF POLYNOMIAL 2 3
enter the coefficient5
enter the degree5
enter the coefficient6
enter the degree6
enter the coefficient7
enter the degree8
5 56 67 8THE MERGE LIST IS:6 28 39 45 56 67 8