Pythonで連結リストを使って2つの多項式を加算するプログラムの作り方

問題の概要

この記事では、連結リストで表現された2つの多項式を加算するPythonプログラムを紹介します。

2つの多項式が与えられ、それらの和を求めることを考えます。多項式は連結リストとして表現し、多項式の各項は連結リストの1つのノードに対応させます。各ノードには「係数」「次数（べき指数）」、そして「次のノードへの参照（ポインタ）」を持たせます。最終的なゴールは、2つの多項式の和を表す新しい連結リストを返すことです。

たとえば、入力が以下の画像のような2つの多項式だった場合を見てみましょう。

1x^1 + 1x^2 = 0 と 2x^1 + 3x^0 = 0

この場合、出力は次のようになります。

3x^1 + 1x^2 + 3x^0 = 0

解き方の手順

この問題は、マージソートのように2つのリストを走査しながら統合していく要領で解けます。具体的には、以下の手順に従います。

1. ダミーノード（dummy）と作業用ノード（node）として、それぞれ新しい多項式ノードを作成します。
2. poly1とpoly2のどちらも空になるまで、次の処理を繰り返します。
   • poly1の次数がpoly2の次数より大きい場合：nodeのnextにpoly1をつなぎ、nodeをpoly1に更新して、poly1を次のノードへ進めます。
   • poly1の次数がpoly2の次数より小さい場合：同様に、nodeのnextにpoly2をつなぎ、nodeをpoly2に更新して、poly2を次のノードへ進めます。
   • 両者の次数が等しい場合：poly1とpoly2の係数を加算します。係数の和がゼロでない場合のみ、新しいノードを結果につなげます。その後、poly1とpoly2の両方を次のノードへ進めます。
3. ループを抜けた後、どちらか一方のリストに残っている項をすべて結果の末尾につなげます。
4. dummyのnextを結果として返します。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class polynomial:
    def __init__(self, coeff=0, pow=0, nxt=None):
        self.coefficient = coeff
        self.power = pow
        self.next = nxt

def create_poly(expression):
    head = None
    for element in expression:
        if head == None:
            head = polynomial(element[0], element[1])
        else:
            temp = head
            while temp.next != None:
                temp = temp.next
            temp.next = polynomial(element[0], element[1])
    return head

def show_poly(head):
    temp = head
    while temp.next != None:
        print(str(temp.coefficient) + 'x^' + str(temp.power), end=' + ')
        temp = temp.next
        if temp.next == None:
            print(str(temp.coefficient) + 'x^' + str(temp.power), end=' = 0')

def solve(poly1, poly2):
    dummy = node = polynomial()
    while poly1 and poly2:
        if poly1.power > poly2.power:
            node.next = node = poly1
            poly1 = poly1.next
        elif poly1.power < poly2.power:
            node.next = node = poly2
            poly2 = poly2.next
        else:
            coef = poly1.coefficient + poly2.coefficient
            if coef:
                node.next = node = polynomial(coef, poly1.power)
            poly1 = poly1.next
            poly2 = poly2.next
    node.next = poly1 or poly2
    return dummy.next

poly1 = create_poly([[1,1], [1,2]])
poly2 = create_poly([[2,1], [3, 0]])
poly3 = solve(poly1, poly2)
show_poly(poly3)

コードのポイント

• polynomialクラス：各ノードは係数（coefficient）、次数（power）、次ノードへの参照（next）の3つの属性を持ちます。
• create_poly関数：「[係数, 次数]」のペアからなるリストを受け取り、多項式の連結リストを構築します。
• show_poly関数：多項式を「3x^1 + 1x^2 + 3x^0 = 0」のような形式で画面に出力します。
• solve関数：ダミーノードを先頭に置くことで、結果リストの先頭操作をシンプルにしています。同じ次数の項同士は係数が加算され、打ち消し合ってゼロになった項は自動的に除外される点も特徴です。

入力

poly1 = create_poly([[1,1], [1,2]])
poly2 = create_poly([[2,1], [3, 0]])

出力

3x^1 + 1x^2 + 3x^0 = 0

計算量

このアルゴリズムは両方の連結リストを一度ずつ走査するだけで完了するため、時間計算量はO(m + n)です。また、必要な追加メモリは結果のリスト長に依存するため、空間計算量もO(m + n)となります（mとnはそれぞれpoly1とpoly2の項数）。

まとめ

連結リストで表現された多項式の加算は、「次数を比較しながら大きい方の項を先に進め、次数が等しい場合は係数を足し合わせる」というマージ処理の考え方で実現できます。さらに、ダミーノードを使うテクニックによって先頭ノードの扱いが簡潔になり、コード全体の可読性も向上します。データ構造とアルゴリズムの学習題材としても最適なので、ぜひご自身でも手を動かして実装してみてください。