Algorithm to subtract two polynomials using linked list in c

The linked list completes the addition and subtraction of two polynomials

Keywords: Algorithm data structure linked list

Table of Contents Show

The linked list completes the addition and subtraction of two polynomials
Hot Keywords
Subtract Two Numbers represented as Linked Lists
C program to store a polynomial using linked list. Also perform addition and subtraction on two polynomials

Content: complete the addition operation of two polynomials. It is known that there are two polynomials PM (x) and QM (x). Design an algorithm to realize the operation of Pm(x)+Qm(x) and Pm(x)-Qm(x). Moreover, the wig operation does not reopen the storage space, and it is required to be realized by chain storage structure.

Steps:

algorithm analysis

The implementation of the addition algorithm of two polynomials is to store the two polynomials in a linked list. Set two pointers LAI and LBI to move the first node of equations Pm(x) and Qm(x) respectively, and compare the exponential direction of the node referred to by LAI and LBI, which can be divided into the following three cases:

If LAI - > exp < LBI - > exp, the node referred to by LAI is one of the polynomials, and the LAI pointer moves back one position on the original basis.
If LAI - > exp = LBI - > exp, add the coefficients of the corresponding terms, and then deal with them in two cases: if the sum of the coefficient terms is zero, release the node pointed to by LAI and LBI; if the sum of the coefficient terms is not zero, modify the coefficient field of the node pointed to by LAI and release the LBI node.
If Lai - > exp > LBI - > exp, the node referred to by LBI is one of the polynomials, and the LBI pointer moves back one position on the original basis.

Two polynomial subtraction algorithm, the first is to store the two polynomials in a linked list. Set two pointers LAI and LBI to move the first node of equations Pm(x) and Qm(x) respectively, and compare the exponential direction of the node referred to by LAI and LBI, which can be divided into the following three cases:

If LAI - > exp < LBI - > exp, the node referred to by LAI is one of the polynomials, and the LAI pointer moves back one position on the original basis.
If LAI - > exp = LBI - > exp, subtract the coefficients of the corresponding term, and then deal with it in two cases: if the sum of the coefficient terms is zero, release the node pointed to by LAI and LBI; if the sum of the coefficient terms is not zero, modify the coefficient field of the node pointed to by LAI and release the LBI node.
If Lai - > exp > LBI - > exp, the node referred to by LBI is one of the polynomials, and the LBI pointer moves back one position on the original basis.

Algorithm design

Five functions are designed in the program:

Init() is used to initialize the linked list;
CreatFromTail() creates a linked list by tail interpolation;
Polyadd() is used to realize the addition algorithm of two polynomials;
Polysub() is used to realize the subtraction of two polynomials;
Print() is used to output polynomials.
#include<stdio.h> #include<stdlib.h> #include<malloc.h> typedef struct poly { int exp; //index int coef; //coefficient struct poly *next; }PNode,*PLinklist; /*Linked list initialization*/ int Init(PLinklist *head) { *head=(PLinklist)malloc(sizeof(PNode)); if(*head) { (*head)->next=NULL; return 1; } else return 0; } /*Creating linked list by tail interpolation*/ int CreateFromTail(PLinklist*head) { PNode *pTemp,*pHead; int c; //Storage factor int exp; //Storage index int i=1 ; //Counter pHead=*head; scanf("%d,%d",&c,&exp); while(c!=0)//When the coefficient is zero, end the input { pTemp=(PLinklist)malloc(sizeof(PNode)); if(pTemp) { pTemp->exp=exp; //Acceptance index pTemp->coef=c; //Acceptance coefficient pTemp->next=NULL; pHead->next=pTemp; pHead=pTemp; scanf("%d,%d",&c,&exp); } else return 0; } return 1; } /*Add two polynomials*/ void Polyadd(PLinklist LA,PLinklist LB) { PNode*LAI=LA->next; //Pointer LAI moves in polynomial A PNode*LBI=LB->next; PNode*temp; //Pointer temp saves the node to be deleted int sum=0; //Sum of preservation factors /*Compare the exponential terms of the nodes referred to by LAI and LBI*/ while(LAI&&LBI) { if(LAI->exp<LBI->exp){ LA->next=LAI; LA=LA->next; LAI=LAI->next; } else if(LAI->exp==LBI->exp) { sum=LAI->coef+LBI->coef; if(sum) { LAI->coef=sum; LA->next=LAI; LA=LA->next; LAI=LAI->next; temp=LBI; LBI=LBI->next; free(temp); } else { temp=LAI; LAI=LAI->next; free(temp); temp=LBI; LBI=LBI->next; free(temp); } } else { LA->next=LBI; LA=LA->next; LBI=LBI->next; } } if(LAI) LA->next=LAI; else LA->next=LBI; } /*Subtraction of two polynomials*/ void Polysub(PLinklist LA,PLinklist LB) { PNode*LAI=LA->next; //Pointer LAI moves in polynomial A PNode*LBI=LB->next; PNode*temp; //Pointer temp saves the node to be deleted int difference=0; //Preservation factor /*Compare the exponential terms of the nodes referred to by LAI and LBI*/ while(LAI&&LBI) { if(LAI->exp<LBI->exp){ LA->next=LAI; LA=LA->next; LAI=LAI->next; } else if(LAI->exp==LBI->exp) { difference=LAI->coef-LBI->coef; if(difference) { LAI->coef=difference; LA->next=LAI; LA=LA->next; LAI=LAI->next; temp=LBI; LBI=LBI->next; free(temp); } else { temp=LAI; LAI=LAI->next; free(temp); temp=LBI; LBI=LBI->next; free(temp); } } else { LA->next=LBI; LA=LA->next; LBI=LBI->next; } } if(LAI) LA->next=LAI; else LA->next=LBI; } void Print(PLinklist head) { head=head->next; while(head) { if(head->exp) printf("(%dx^%d)",head->coef,head->exp); else printf("%d",head->coef); if(head->next) printf("+"); else break; head=head->next; } } int main(void) { PLinklist LA; PLinklist LB; Init(&LA); Init(&LB); printf("Please enter the coefficient of the first polynomial,index,Enter 0,0 End input\n"); CreateFromTail(&LA); printf("Please enter the coefficient of the second polynomial,index,Enter 0,0 End input\n"); CreateFromTail(&LB); Print(LA); printf("\n"); Print(LB); printf("\n"); int i; printf("(Please enter 1 for addition polynomial and 0 for subtraction polynomial)\n"); scanf("%d",&i); if(1==i){ Polyadd(LA,LB); printf("The result of adding two polynomials:\n"); Print(LA); printf("\n"); } else if(0==i){ Polysub(LA,LB); printf("The result of subtracting two polynomials:\n"); Print(LA); printf("\n"); } else printf("Please enter the correct characters"); return 0; }

Posted by blckspder on Wed, 06 Oct 2021 12:20:44 -0700

Hot Keywords

Java - 6961
Database - 2683
Python - 2616
Programming - 2419
Attribute - 2418
Javascript - 2383
Spring - 2111
Android - 2077
xml - 1972
Linux - 1818
JSON - 1764
network - 1748
github - 1720
less - 1676
MySQL - 1538
SQL - 1332
PHP - 1318
encoding - 1179
Mobile - 1029
Apache - 925

Subtract Two Numbers represented as Linked Lists

Given two linked lists that represent two large positive numbers. Subtract the smaller number from the larger one and return the difference as a linked list. Note that the input lists may be in any order, but we always need to subtract smaller from the larger ones.
It may be assumed that there are no extra leading zeros in input lists.
Examples:

Input: l1 = 1 -> 0 -> 0 -> NULL, l2 = 1 -> NULL Output: 0->9->9->NULL Explanation: Number represented as lists are 100 and 1, so 100 - 1 is 099 Input: l1 = 7-> 8 -> 6 -> NULL, l2 = 7 -> 8 -> 9 NULL Output: 3->NULL Explanation: Number represented as lists are 786 and 789, so 789 - 786 is 3, as the smaller value is subtracted from the larger one.

C program to store a polynomial using linked list. Also perform addition and subtraction on two polynomials

data structure / December 14, 2021 / yashpalsinghdeveloper / 0

Complete C program to store a polynomial using linked list. Also, perform addition and subtraction on two polynomials

#include <stdio.h> #include <conio.h> #include <malloc.h> struct node { int num; int coeff; struct node *next; }; struct node *start1 = NULL; struct node *start2 = NULL; struct node *start3 = NULL; struct node *start4 = NULL; struct node *last3 = NULL; struct node *create_poly(struct node *); struct node *display_poly(struct node *); struct node *add_poly(struct node *, struct node *, struct node *); struct node *sub_poly(struct node *, struct node *, struct node *); struct node *add_node(struct node *, int, int); int main() { int option; clrscr(); do { printf("\n******* MAIN MENU *******"); printf("\n 1. Enter the first polynomial"); printf("\n 2. Display the first polynomial"); printf("\n 3. Enter the second polynomial"); printf("\n 4. Display the second polynomial"); printf("\n 5. Add the polynomials"); printf("\n 6. Display the result"); printf("\n 7. Subtract the polynomials"); printf("\n 8. Display the result"); printf("\n 9. EXIT"); printf("\n\n Enter your option : "); scanf("%d", &option); switch(option) { case 1: start1 = create_poly(start1); break; case 2: start1 = display_poly(start1); break; case 3: start2 = create_poly(start2); break; case 4: start2 = display_poly(start2); break; case 5: start3 = add_poly(start1, start2, start3); break; case 6: start3 = display_poly(start3); break; case 7: start4 = sub_poly(start1, start2, start4); break; case 8: start4 = display_poly(start4); break; } }while(option!=9); getch(); return 0; } struct node *create_poly(struct node *start) { struct node *new_node, *ptr; int n, c; printf("\n Enter the number : "); scanf("%d", &n); printf("\t Enter its coefficient : "); scanf("%d", &c); while(n != –1) { if(start==NULL) { new_node = (struct node *)malloc(sizeof(struct node)); new_node -> num = n; new_node -> coeff = c; new_node -> next = NULL; start = new_node; } else { ptr = start; while(ptr -> next != NULL) ptr = ptr -> next; new_node = (struct node *)malloc(sizeof(struct node)); new_node -> num = n; new_node -> coeff = c; new_node -> next = NULL; ptr -> next = new_node; } printf("\n Enter the number : "); scanf("%d", &n); if(n == –1) break; printf("\t Enter its coefficient : "); scanf("%d", &c); } return start; } struct node *display_poly(struct node *start) { struct node *ptr; ptr = start; while(ptr != NULL) { printf("\n%d x %d\t", ptr -> num, ptr -> coeff); ptr = ptr -> next; } return start; } struct node *add_poly(struct node *start1, struct node *start2, struct node *start3) { struct node *ptr1, *ptr2; int sum_num, c; ptr1 = start1, ptr2 = start2; while(ptr1 != NULL && ptr2 != NULL) { if(ptr1 -> coeff == ptr2 -> coeff) { sum_num = ptr1 -> num + ptr2 -> num; start3 = add_node(start3, sum_num, ptr1 -> coeff); ptr1 = ptr1 -> next; ptr2 = ptr2 -> next; } else if(ptr1 -> coeff > ptr2 -> coeff) { start3 = add_node(start3, ptr1 -> num, ptr1 -> coeff); ptr1 = ptr1 -> next; } else if(ptr1 -> coeff < ptr2 -> coeff) { start3 = add_node(start3, ptr2 -> num, ptr2 -> coeff); ptr2 = ptr2 -> next; } } if(ptr1 == NULL) { while(ptr2 != NULL) { start3 = add_node(start3, ptr2 -> num, ptr2 -> coeff); ptr2 = ptr2 -> next; } } if(ptr2 == NULL) { while(ptr1 != NULL) { start3 = add_node(start3, ptr1 -> num, ptr1 -> coeff); ptr1 = ptr1 -> next; } } return start3; } struct node *sub_poly(struct node *start1, struct node *start2, struct node *start4) { struct node *ptr1, *ptr2; int sub_num, c; ptr1 = start1, ptr2 = start2; do { if(ptr1 -> coeff == ptr2 -> coeff) { sub_num = ptr1 -> num – ptr2 -> num; start4 = add_node(start4, sub_num, ptr1 -> coeff); ptr1 = ptr1 -> next; ptr2 = ptr2 -> next; } else if(ptr1 -> coeff > ptr2 -> coeff) { start4 = add_node(start4, ptr1 -> num, ptr1 -> coeff); ptr1 = ptr1 -> next; } else if(ptr1 -> coeff < ptr2 -> coeff { start4 = add_node(start4, ptr2 -> num, ptr2 -> coeff); ptr2 = ptr2 -> next; } }while(ptr1 != NULL || ptr2 != NULL); if(ptr1 == NULL) { while(ptr2 != NULL) { start4 = add_node(start4, ptr2 -> num, ptr2 -> coeff); ptr2 = ptr2 -> next; } } if(ptr2 == NULL) { while(ptr1 != NULL) { start4 = add_node(start4, ptr1 -> num, ptr1 -> coeff); ptr1 = ptr1 -> next; } } return start4; } struct node *add_node(struct node *start, int n, int c) { struct node *ptr, *new_node; if(start == NULL) { new_node = (struct node *)malloc(sizeof(struct node)); new_node -> num = n; new_node -> coeff = c; new_node -> next = NULL; start = new_node; } else { ptr = start; while(ptr -> next != NULL) ptr = ptr -> next; new_node = (struct node *)malloc(sizeof(struct node)); new_node -> num = n; new_node -> coeff = c; new_node -> next = NULL; ptr -> next = new_node; } return start; }

Output

Enter the first polynomial
Display the first polynomial
–––––––––––––––––––––––––––––––
EXIT
Enter your option : 1
Enter the number : 6 Enter its coefficient : 2
Enter the number : 5 Enter its coefficient : 1
Enter the number : –1
Enter your option : 2
6 x 2 5 x 1
Enter your option : 9