？5-2 一元多项式的乘法与加法运算

### 实现一元多项式的乘法与加法运算 #### 方法概述 为了实现一元多项式的乘法与加法运算，可以采用两种主要的数据结构来表示多项式：数组或链表。对于稠密多项式（即大多数指数都有对应的项），推荐使用数组；而对于稀疏多项式（即只有少数几项有非零系数），则更倾向于使用链表[^1]。 以下是具体实现方案： --- #### 加法运算的实现 加法运算是通过逐项比较两个多项式的每一项来进行的。如果两项具有相同的指数，则将其系数相加并保留该指数下的新系数值。如果没有相同指数的项，则直接将该项加入结果多项式中。 代码示例如下： ```python class PolyNode: def __init__(self, coef=0, expn=0, next=None): self.coef = coef # 系数 self.expn = expn # 指数 self.next = next def add_poly(p1_head, p2_head): dummy = PolyNode() # 创建虚拟头节点 current = dummy while p1_head and p2_head: if p1_head.expn > p2_head.expn: # 如果p1当前项指数大于p2 current.next = PolyNode(p1_head.coef, p1_head.expn) p1_head = p1_head.next elif p1_head.expn < p2_head.expn: # 如果p1当前项指数小于p2 current.next = PolyNode(p2_head.coef, p2_head.expn) p2_head = p2_head.next else: # 如果两者指数相等 sum_coef = p1_head.coef + p2_head.coef if sum_coef != 0: # 只有当系数不为零时才添加到结果中 current.next = PolyNode(sum_coef, p1_head.expn) p1_head = p1_head.next p2_head = p2_head.next current = current.next # 添加剩余部分 if p1_head: current.next = p1_head if p2_head: current.next = p2_head return dummy.next ``` --- #### 乘法运算的实现 乘法可以通过分解成多次加法的方式完成。具体来说，遍历第一个多项式的每一项，并将其与第二个多项式的每一项逐一相乘，最终将这些中间结果累加起来形成最终的乘积多项式。 代码示例如下： ```python def multiply_term_with_poly(term_node, poly_head): """辅助函数：单项 * 整个多项式""" result_dummy = PolyNode() current_result = result_dummy while poly_head: new_expn = term_node.expn + poly_head.expn new_coef = term_node.coef * poly_head.coef if new_coef != 0: current_result.next = PolyNode(new_coef, new_expn) current_result = current_result.next poly_head = poly_head.next return result_dummy.next def multiply_poly(p1_head, p2_head): result_dummy = PolyNode() temp_p1 = p1_head while temp_p1: partial_product = multiply_term_with_poly(temp_p1, p2_head) result_dummy.next = add_poly(result_dummy.next, partial_product) # 使用加法规则累积结果 temp_p1 = temp_p1.next return result_dummy.next ``` --- #### 输入输出格式说明 按照给定的要求，程序需支持如下输入输出格式： - **输入**：两行数据，每行先给出多项式非零项的数量 $N$，接着以指数递减顺序提供各非零项的系数和指数。 - **输出**：共两行，分别为乘积多项式和加法多项式的结果，同样按指数递减顺序排列，且无多余空格。若结果为空，则输出 `0 0`[^2][^3]。 --- #### 测试案例 假设输入如下： ``` 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 ``` --- #### 总结 以上展示了如何利用链表作为基础数据结构来高效地解决一元多项式的加法与乘法问题。此方法不仅能够满足复杂度需求，还具备良好的扩展性和灵活性[^4]。