इस अवधारणा को बेहतर ढंग से समझने के लिए आइए सबसे पहले आवश्यक सभी बुनियादी सामग्री को ब्रश करें।
लिंक की गई सूची एक डेटा संरचना है जो सूची के नोड में प्रत्येक तत्व को एक वस्तु के रूप में संग्रहीत करती है। प्रत्येक नोट में दो भाग डेटा होते हैं और अगले नोड से लिंक होते हैं।
बहुपद एक गणितीय व्यंजक है जिसमें चर और गुणांक होते हैं। उदाहरण के लिए x^2 - 4x + 7
बहुपद लिंक्ड सूची . में , बहुपद के गुणांक और घातांक सूची के डेटा नोड के रूप में परिभाषित होते हैं।
एक लिंक्ड सूची के रूप में संग्रहीत दो बहुपदों को जोड़ने के लिए। हमें समान घात वाले चरों के गुणांकों को जोड़ना होगा। लिंक की गई सूची में नोड में 3 सदस्य होते हैं, अगले नोड के लिए गुणांक मान लिंक।
एक लिंक की गई सूची जिसका उपयोग बहुपद को संग्रहीत करने के लिए किया जाता है, ऐसा दिखता है -
बहुपद :4x 7 + 12x 2 + 45
इस तरह एक लिंक की गई सूची बहुपद का प्रतिनिधित्व करती है।
एक लिंक्ड सूची द्वारा दर्शाए गए दो बहुपदों को जोड़ना। हम नोड के घातांक मान पर मानों की जाँच करते हैं। घातांक के समान मानों के लिए, हम गुणांक जोड़ेंगे।
उदाहरण,
Input : p1= 13x8 + 7x5 + 32x2 + 54 p2= 3x12 + 17x5 + 3x3 + 98 Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152
स्पष्टीकरण - सभी घातों के लिए, हम घातांकों के गुणांकों की जांच करेंगे जिनके घातांक का मान समान है और उन्हें जोड़ देंगे। अंतिम बहुपद लौटाएं।
एल्गोरिदम
इनपुट - बहुपद p1 और p2 को एक लिंक्ड सूची के रूप में दर्शाया गया है।
Step 1: loop around all values of linked list and follow step 2& 3. Step 2: if the value of a node’s exponent. is greater copy this node to result node and head towards the next node. Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result. Step 4: Print the resultant node.
उदाहरण
#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