更新、更全的《数据结构与算法》的更新网站，更有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}
\]
\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))