इस अवधारणा को बेहतर ढंग से समझने के लिए, पहले आवश्यक सभी बुनियादी बातों को दोहरा लेते हैं।
लिंक्ड लिस्ट एक डेटा संरचना है जो प्रत्येक तत्व को लिस्ट के एक नोड में ऑब्जेक्ट के रूप में संग्रहीत करती है। प्रत्येक नोड में दो भाग होते हैं: डेटा और अगले नोड का लिंक।
बहुपद (Polynomial) एक गणितीय अभिव्यक्ति है जिसमें चर और गुणांक होते हैं। उदाहरण के लिए: x² - 4x + 7
बहुपद लिंक्ड लिस्ट में, बहुपद के गुणांक और घातांक को लिस्ट के डेटा नोड के रूप में परिभाषित किया जाता है।
दो बहुपदों को जोड़ने के लिए जो लिंक्ड लिस्ट के रूप में संग्रहीत हैं, हमें समान घात वाले चरों के गुणांकों को जोड़ना होगा। एक लिंक्ड लिस्ट नोड में तीन सदस्य होते हैं: गुणांक मान, घातांक, और अगले नोड का लिंक।
बहुपद को संग्रहीत करने के लिए उपयोग की जाने वाली एक लिंक्ड लिस्ट इस तरह दिखती है:
बहुपद: 4x7 + 12x2 + 45
यह दर्शाता है कि एक लिंक्ड लिस्ट द्वारा दर्शाया गया बहुपद कैसा दिखता है।
लिंक्ड लिस्ट द्वारा दर्शाए गए दो बहुपदों को जोड़ना। हम नोड के घातांक मान पर मानों की जांच करते हैं। समान घातांक मानों के लिए, हम गुणांकों को जोड़ देंगे।
उदाहरण:
Input : p1= 13x8 + 7x5 + 32x2 + 54 p2= 3x12 + 17x5 + 3x3 + 98 Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152
व्याख्या - सभी घातों के लिए, हम उन घातांकों के गुणांकों की जांच करेंगे जिनके घातांक का मान समान है और उन्हें जोड़ देंगे। अंतिम बहुपद लौटाएं।
एल्गोरिदम
इनपुट - लिंक्ड लिस्ट के रूप में दर्शाए गए बहुपद p1 और p2।
चरण 1: लिंक्ड लिस्ट के सभी मानों पर लूप चलाएं और चरण 2 और 3 का पालन करें। चरण 2: यदि किसी नोड के घातांक का मान अधिक है, तो इस नोड को परिणाम नोड में कॉपी करें और अगले नोड की ओर बढ़ें। चरण 3: यदि दोनों नोड्स के घातांक का मान समान है, तो गुणांकों को जोड़ें और फिर जोड़े गए मान को नोड के साथ परिणाम में कॉपी करें। चरण 4: परिणामी नोड को प्रिंट करें।
उदाहरण
#include<bits/stdc++.h> using namespace std; struct Node{ int coeff; int pow; struct Node *next; }; void create_node(int x, int y, struct Node **temp){ struct Node *r, *z; z = *temp; if(z == NULL){ r =(struct Node*)malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y; r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } } void polyadd(struct Node *p1, struct Node *p2, struct Node *result){ while(p1->next && p2->next){ if(p1->pow > p2->pow){ result->pow = p1->pow; result->coeff = p1->coeff; p1 = p1->next; } else if(p1->pow < p2->pow){ result->pow = p2->pow; result->coeff = p2->coeff; p2 = p2->next; } else { result->pow = p1->pow; result->coeff = p1->coeff+p2->coeff; p1 = p1->next; p2 = p2->next; } result->next = (struct Node *)malloc(sizeof(struct Node)); result = result->next; result->next = NULL; } while(p1->next || p2->next){ if(p1->next){ result->pow = p1->pow; result->coeff = p1->coeff; p1 = p1->next; } if(p2->next){ result->pow = p2->pow; result->coeff = p2->coeff; p2 = p2->next; } result->next = (struct Node *)malloc(sizeof(struct Node)); result = result->next; result->next = NULL; } } void printpoly(struct Node *node){ while(node->next != NULL){ printf("%dx^%d", node->coeff, node->pow); node = node->next; if(node->next != NULL) printf(" + "); } } int main(){ struct Node *p1 = NULL, *p2 = NULL, *result = NULL; create_node(41,7,&p1); create_node(12,5,&p1); create_node(65,0,&p1); create_node(21,5,&p2); create_node(15,2,&p2); printf("polynomial 1: "); printpoly(p1); printf("\npolynomial 2: "); printpoly(p2); result = (struct Node *)malloc(sizeof(struct Node)); polyadd(p1, p2, result); printf("\npolynomial after adding p1 and p2 : "); printpoly(result); return 0; } आउटपुट
polynomial 1: 41x^7 + 12x^5 + 65x^0 polynomial 2: 21x^5 + 15x^2 polynomial after adding p1 and p2 : 41x^7 + 33x^5 + 15x^2 + 65x^0
