更新、更全的《數(shù)據(jù)結(jié)構(gòu)與算法》的更新網(wǎng)站，更有python、go、人工智能教學(xué)等著你：https://www.cnblogs.com/nickchen121/p/11407287.html

一、題意理解

題目：
設(shè)計(jì)函數(shù)分別求兩個(gè)一元多項(xiàng)式的乘積與和。

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

輸出格式：
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項(xiàng)式以及和多項(xiàng)式非零項(xiàng)的系數(shù)和指數(shù)。數(shù)字間以空格分隔，但結(jié)尾不能有多余空格。零多項(xiàng)式應(yīng)輸出0 0。

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

          
            # python語言實(shí)現(xiàn)

# 輸入樣例：
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
          
        

二、解題思路

存儲(chǔ)方式可以采用鏈表存儲(chǔ)和數(shù)組存儲(chǔ)，為了熟悉鏈?zhǔn)讲僮鳎圆捎面湵泶鎯?chǔ)。其中指針定義的格式如下所示

三、多項(xiàng)式加法

          
            # python語言實(shí)現(xiàn)

def adds(l1, l2):  # l1,l2為鏈表,且不為空
    p1 = l1.head
    p2 = l2.head
    addRes = []
    while (p1 is not None) and (p2 is not None):  # 當(dāng)p1和p2都部位空時(shí)，進(jìn)行運(yùn)算
        tmp1_exp = p1.get_data()[1]  # 獲取p1指針處節(jié)點(diǎn)的指數(shù)
        tmp2_exp = p2.get_data()[1]  # 獲取p2指針處節(jié)點(diǎn)的指數(shù)

        # 當(dāng)指數(shù)相同時(shí)，系數(shù)相加，指數(shù)不變
        if tmp1_exp == tmp2_exp:
            addRes.append([p1.get_data()[0] + p2.get_data()[0], p1.get_data()[1]])
            p1 = p1.next  # 指針指向下一個(gè)節(jié)點(diǎn)
            p2 = p2.next

        # 當(dāng)指數(shù)不相同時(shí)，選擇較大的指數(shù)項(xiàng)存到結(jié)果中
        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

    # 對(duì)于鏈表中剩余的節(jié)點(diǎn)添加到結(jié)果中
    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

    # 此時(shí)的addRes結(jié)果
    # addRes [[5, 20], [-4, 4], [-5, 2], [9, 1], [-2, 0]]
    # 列表中每一項(xiàng)代表一各指數(shù)項(xiàng)，其中第一個(gè)元素代表系數(shù)，第二個(gè)元素代表指數(shù)。如[5，20]：5x^20

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

    # 此時(shí)的輸出結(jié)果變?yōu)?    # [5,20,-4,4,-5,2,9,1,-2,0]
    return res1
          
        

四、多項(xiàng)式乘法

          
            # python語言實(shí)現(xiàn)

def muls(l1, l2):
    p1 = l1.head
    p2 = l2.head
    mulRes = []
    while p1 is not None:  # 將第一項(xiàng)的每一項(xiàng)乘以第二項(xiàng)的每一項(xiàng)
        tmp1 = p1.get_data()
        while p2 is not None:
            tmp2 = p2.get_data()
            # 將系數(shù)相乘和指數(shù)相加放入結(jié)果中
            mulRes.append([tmp1[0] * tmp2[0], tmp1[1] + tmp2[1]])
            p2 = p2.next
        p2 = l2.head  # 每次遍歷完l2，都需要回到頭指針，進(jìn)行下一次遍歷
        p1 = p1.next
    # 上述運(yùn)算后，需要合并同類項(xiàng)。定義一個(gè)字典，key=指數(shù)，values=系數(shù)
    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)
    # 結(jié)果變形輸出
    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語言實(shí)現(xiàn)

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

    # 添加節(jié)點(diǎn)
    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]
        # 當(dāng)指數(shù)相同時(shí)，系數(shù)相加
        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:
        # 如果多項(xiàng)式中出現(xiàn)抵消，即系數(shù)為0需要?jiǎng)h除
        if item[1] != 0:
            res2.append(item[1])
            res2.append(item[0])
    # 如果最后出現(xiàn)空數(shù)組需要輸出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()))

# 變?yōu)殒湵?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)
# 考慮鏈表長(zhǎng)度進(jìn)行運(yùn)算
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:  # 一個(gè)為0，另一個(gè)為多項(xiàng)式
    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:  # 都為多項(xiàng)式
    print_list(muls(l1, l2))
    print()
    print_list(adds(l1, l2))