C++の連結リストを使って2つの多項式を加算する方法

この概念をより深く理解するために、まず必要な基本事項をおさらいしましょう。

連結リスト（Linked List）とは

連結リストは、各要素を「ノード」と呼ばれるオブジェクトとして格納するデータ構造です。各ノードは、データ部分と次のノードへのリンクの2つの要素で構成されています。

多項式（Polynomial）とは

多項式とは、変数と係数から構成される数学的な式のことです。例えば、x² − 4x + 7 のようなものが該当します。

多項式を表す連結リスト

多項式連結リストでは、多項式の係数と指数がリストのデータノードとして定義されます。連結リストとして格納された2つの多項式を加算するには、同じ次数（べき乗）を持つ変数同士の係数を足し合わせる必要があります。

このとき、各ノードは「係数」「指数」「次のノードへのリンク」の3つのメンバーを持ちます。

多項式を格納する連結リストは、以下のように表現されます。

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

これが連結リストで表現された多項式のイメージです。

多項式の加算の考え方

連結リストで表現された2つの多項式を加算する際は、各ノードの指数値を確認します。そして、指数値が同じノード同士については、その係数を加算します。

具体例

入力：
p1 = 13x8 + 7x5 + 32x2 + 54
p2 = 3x12 + 17x5 + 3x3 + 98

出力：3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152

解説：すべての次数について、同じ指数値を持つ項の係数を見つけて加算し、最終的な多項式として返します。上の例では x⁵ の項（7 + 17 = 24）や定数項（54 + 98 = 152）が加算されていることがわかります。

アルゴリズム

入力：連結リストとして表現された多項式 p1 および p2

ステップ1：連結リストのすべてのノードを巡回し、ステップ2とステップ3を実行する。
ステップ2：片方のノードの指数値がもう片方より大きい場合、そのノードを結果ノードにコピーし、次のノードへ進む。
ステップ3：両方のノードの指数値が等しい場合、係数を加算し、その結果をノードごと結果にコピーする。
ステップ4：残りのノードを結果に連結した後、結果の多項式を出力する。

C++による実装例

#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;
   }
}
// 2つの多項式を加算する関数
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;
   // 多項式1の作成：41x^7 + 12x^5 + 65
   create_node(41,7,&p1);
   create_node(12,5,&p1);
   create_node(65,0,&p1);
   // 多項式2の作成：21x^5 + 15x^2
   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

実行結果から、同じ指数 x⁵ を持つ項（12 + 21 = 33）が正しく加算され、新しい多項式が生成されていることが確認できます。この手法の計算量は、両方のリストの長さに比例する O(m + n) となります（m、n はそれぞれの多項式の項数）。