C++のリンクリストを使用して2つの多項式を追加します。

この概念をよりよく理解するために、最初に必要なすべての基本的な内容をブラッシュアップしましょう。

リンクリスト リストのノードにオブジェクトとして各要素を格納するデータ構造です。すべてのメモには、2つの部分のデータハンと次のノードへのリンクが含まれています。

多項式 は変数と係数で構成される数式です。たとえば、x ^ 2-4x + 7

多項式リンクリスト 、多項式の係数と指数は、リストのデータノードとして定義されます。

リンクリストとして保存されている2つの多項式を追加します。同じ累乗の変数の係数を追加する必要があります。リンクリストノードには3つのメンバーが含まれ、係数値は次のノードにリンクします。

多項式を格納するために使用されるリンクリストは、次のようになります-

多項式：4x ⁷ + 12x ² + 45

これは、多項式で表されたリンクリストがどのように見えるかです。

リンクリストで表される2つの多項式を追加します。ノードの指数値で値をチェックします。同じ指数の値に対して、係数を追加します。

例、

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