更新、更全的《數據結構與算法》的更新網站，更有python、go、人工智能教學等著你：https://www.cnblogs.com/nickchen121/p/11407287.html

一、題意理解

題目：
設計函數分別求兩個一元多項式的乘積與和。

輸入格式：
輸入分2行，每行分別先給出多項式非零項的個數，再以指數遞降方式輸入一個多項式非零項系數和指數（絕對值均為不超過1000的整數）。數字間以空格分隔。

輸出格式：
輸出分2行，分別以指數遞降方式輸出乘積多項式以及和多項式非零項的系數和指數。數字間以空格分隔，但結尾不能有多余空格。零多項式應輸出0 0。

例子：
\[ \text{已知兩個多項式：} \\ \begin{align} & 3x^4-5x^2+6x-2 \\ & 5x^{20}-7x^4+3x \end{align} \]

          
            # python語言實現

# 輸入樣例：
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

# 輸出樣例：
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
          
        

二、解題思路

存儲方式可以采用鏈表存儲和數組存儲，為了熟悉鏈式操作，所以采用鏈表存儲。其中指針定義的格式如下所示

三、多項式加法

          
            # python語言實現

def adds(l1, l2):  # l1,l2為鏈表,且不為空
    p1 = l1.head
    p2 = l2.head
    addRes = []
    while (p1 is not None) and (p2 is not None):  # 當p1和p2都部位空時，進行運算
        tmp1_exp = p1.get_data()[1]  # 獲取p1指針處節點的指數
        tmp2_exp = p2.get_data()[1]  # 獲取p2指針處節點的指數

        # 當指數相同時，系數相加，指數不變
        if tmp1_exp == tmp2_exp:
            addRes.append([p1.get_data()[0] + p2.get_data()[0], p1.get_data()[1]])
            p1 = p1.next  # 指針指向下一個節點
            p2 = p2.next

        # 當指數不相同時，選擇較大的指數項存到結果中
        if tmp1_exp > tmp2_exp:
            addRes.append([p1.get_data()[0], p1.get_data()[1]])
            p1 = p1.next
        if tmp1_exp < tmp2_exp:
            addRes.append([p2.get_data()[0], p2.get_data()[1]])
            p2 = p2.next

    # 對于鏈表中剩余的節點添加到結果中
    while p1 is not None:
        addRes.append([p1.get_data()[0], p1.get_data()[1]])
        p1 = p1.next
    while p2 is not None:
        addRes.append([p2.get_data()[0], p2.get_data()[1]])
        p2 = p2.next

    # 此時的addRes結果
    # addRes [[5, 20], [-4, 4], [-5, 2], [9, 1], [-2, 0]]
    # 列表中每一項代表一各指數項，其中第一個元素代表系數，第二個元素代表指數。如[5，20]：5x^20

    # 以下是對addRes進行變形處理
    res1 = []
    for item in addRes:
        if item[0] != 0:  # 如果指數為0，即存在抵消情況，此時不應該輸出
            res1.append(item[0])
            res1.append(item[1])
    if len(res1) == 0:  # 如果結果為0,需要輸出：0  0
        return [0, 0]

    # 此時的輸出結果變為
    # [5,20,-4,4,-5,2,9,1,-2,0]
    return res1
          
        

四、多項式乘法

          
            # python語言實現

def muls(l1, l2):
    p1 = l1.head
    p2 = l2.head
    mulRes = []
    while p1 is not None:  # 將第一項的每一項乘以第二項的每一項
        tmp1 = p1.get_data()
        while p2 is not None:
            tmp2 = p2.get_data()
            # 將系數相乘和指數相加放入結果中
            mulRes.append([tmp1[0] * tmp2[0], tmp1[1] + tmp2[1]])
            p2 = p2.next
        p2 = l2.head  # 每次遍歷完l2，都需要回到頭指針，進行下一次遍歷
        p1 = p1.next
    # 上述運算后，需要合并同類項。定義一個字典，key=指數，values=系數
    d = {}
    for item in mulRes:
        if item[1] not in d.keys():
            d[item[1]] = 0
        d[item[1]] += item[0]
    # 字典按照key的大小排序
    d = sorted(d.items(), key=lambda x: x[0], reverse=True)
    # 結果變形輸出
    res2 = []
    for item in d:
        if item[1] != 0:
            res2.append(item[1])
            res2.append(item[0])
    if len(res2) == 0:
        return [0, 0]
    return res2
          
        

五、完整代碼

          
            # python語言實現

class Node:
    def __init__(self, coef, exp):
        self.coef = coef
        self.exp = exp
        self.next = None

    def get_data(self):
        return [self.coef, self.exp]


class List:
    def __init__(self, head):
        self.head = head

    # 添加節點
    def addNode(self, node):
        temp = self.head
        while temp.next is not None:
            temp = temp.next
        temp.next = node

        # 打印

    def printLink(self, head):
        res = []
        while head is not None:
            res.append(head.get_data())
            head = head.next
        return res


def adds(l1, l2):  # l1,l2為鏈表,且不為空
    p1 = l1.head
    p2 = l2.head
    addRes = []
    while (p1 is not None) and (p2 is not None):
        tmp1_exp = p1.get_data()[1]
        tmp2_exp = p2.get_data()[1]
        # 當指數相同時，系數相加
        if tmp1_exp == tmp2_exp:
            addRes.append([p1.get_data()[0] + p2.get_data()[0], p1.get_data()[1]])
            p1 = p1.next
            p2 = p2.next
        if tmp1_exp > tmp2_exp:
            addRes.append([p1.get_data()[0], p1.get_data()[1]])
            p1 = p1.next
        if tmp1_exp < tmp2_exp:
            addRes.append([p2.get_data()[0], p2.get_data()[1]])
            p2 = p2.next
    while p1 is not None:
        addRes.append([p1.get_data()[0], p1.get_data()[1]])
        p1 = p1.next
    while p2 is not None:
        addRes.append([p2.get_data()[0], p2.get_data()[1]])
        p2 = p2.next

    res1 = []
    for item in addRes:
        if item[0] != 0:
            res1.append(item[0])
            res1.append(item[1])
    if len(res1) == 0:
        return [0, 0]
    return res1


def muls(l1, l2):
    p1 = l1.head
    p2 = l2.head
    mulRes = []
    while p1 is not None:
        tmp1 = p1.get_data()
        while p2 is not None:
            tmp2 = p2.get_data()
            mulRes.append([tmp1[0] * tmp2[0], tmp1[1] + tmp2[1]])
            p2 = p2.next
        p2 = l2.head
        p1 = p1.next

    exps = []
    for item in mulRes:
        if item[1] not in exps:
            exps.append(item[1])

    d = {}
    for item in mulRes:
        if item[1] not in d.keys():
            d[item[1]] = 0
        d[item[1]] += item[0]

    d = sorted(d.items(), key=lambda x: x[0], reverse=True)

    res2 = []
    for item in d:
        # 如果多項式中出現抵消，即系數為0需要刪除
        if item[1] != 0:
            res2.append(item[1])
            res2.append(item[0])
    # 如果最后出現空數組需要輸出0 0
    if len(res2) == 0:
        return [0, 0]
    return res2


def print_list(x):
    for i in x[:-1]:
        print(i, end=' ')
    print(x[-1], end='')


# 輸入
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))

# 變為鏈表
if a1[0] != 0:
    head1 = Node(a1[1], a1[2])
    l1 = List(head1)
    if a1[0] > 1:
        for i in range(a1[0] - 1):
            node = Node(a1[i * 2 + 3], a1[i * 2 + 4])
            l1.addNode(node)

if a2[0] != 0:
    head2 = Node(a2[1], a2[2])
    l2 = List(head2)
    if a2[0] > 1:
        for i in range(a2[0] - 1):
            node = Node(a2[i * 2 + 3], a2[i * 2 + 4])
            l2.addNode(node)
# 考慮鏈表長度進行運算
if len(a1) == 1 and len(a2) == 1:  # 都為0，則輸出都為0
    print_list([0, 0])
    print()
    print_list([0, 0])
elif len(a1) == 1 and len(a2) > 1:  # 一個為0，另一個為多項式
    print_list([0, 0])
    print()
    print_list(a2[1:])
elif len(a2) == 1 and len(a1) > 1:
    print_list([0, 0])
    print()
    print_list(a1[1:])
else:  # 都為多項式
    print_list(muls(l1, l2))
    print()
    print_list(adds(l1, l2))