### 实现一元多项式的加法、减法和乘法 以下是使用 Python 编写的一元多项式加法、减法和乘法的完整代码。该程序通过链表结构存储多项式，并支持按题目描述中的输入格式处理多个测试用例。 #### 定义节点类 为了表示多项式的每一项，定义了一个 `Node` 类来保存系数 (`coef`) 和指数 (`exp`) 的信息。 ```python class Node: def __init__(self, coef=0, exp=0): self.coef = coef # 系数 self.exp = exp # 指数 self.next = None # 下一项指针 ``` #### 多项式类 创建一个 `Polynomial` 类用于管理多项式的操作，包括初始化、相加、相减、相乘以及打印结果等功能。 ```python class Polynomial: def __init__(self): self.head = None def add_term(self, coef, exp): # 添加单项到多项式中 new_node = Node(coef, exp) if not self.head or exp > self.head.exp: # 插入头部的情况 new_node.next = self.head self.head = new_node else: current = self.head while current.next and current.next.exp >= exp: current = current.next new_node.next = current.next current.next = new_node @staticmethod def _merge(p1, p2, operation): # 合并两个多项式 (内部方法) result = Polynomial() node1, node2 = p1.head, p2.head while node1 and node2: if node1.exp > node2.exp: result.add_term(node1.coef, node1.exp) node1 = node1.next elif node1.exp < node2.exp: if operation == '-': result.add_term(-node2.coef, node2.exp) else: result.add_term(node2.coef, node2.exp) node2 = node2.next else: # 当前两项指数相同 if operation == '+': combined_coef = node1.coef + node2.coef elif operation == '-': combined_coef = node1.coef - node2.coef if combined_coef != 0: result.add_term(combined_coef, node1.exp) node1 = node1.next node2 = node2.next while node1: # 剩余部分来自第一个多项式 result.add_term(node1.coef, node1.exp) node1 = node1.next while node2: # 剩余部分来自第二个多项式 if operation == '-': result.add_term(-node2.coef, node2.exp) else: result.add_term(node2.coef, node2.exp) node2 = node2.next return result def multiply(self, other): # 两多项式相乘 result = Polynomial() temp_result = Polynomial() # 中间临时变量 current = other.head while current: temp_result = Polynomial() ptr = self.head while ptr: temp_result.add_term(ptr.coef * current.coef, ptr.exp + current.exp) ptr = ptr.next result = Polynomial._add(result, temp_result) # 将中间结果累加至最终结果 current = current.next return result @staticmethod def _add(p1, p2): # 静态方法实现加法逻辑 return Polynomial._merge(p1, p2, '+') @staticmethod def subtract(p1, p2): # 减法静态方法 return Polynomial._merge(p1, p2, '-') def to_string(self): # 转换为字符串形式输出 terms = [] current = self.head while current: term_str = f"{current.coef}x^{current.exp}" if current.exp != 0 else str(current.coef) terms.append(term_str) current = current.next return ' + '.join(terms[::-1]) if terms else "0" ``` #### 主函数 主函数负责读取输入数据并调用相应的多项式操作。 ```python def main(): n = int(input()) # 输入组数 results = [] # 存储每组的结果 for _ in range(n): a, b = map(int, input().split()) poly_a = Polynomial() poly_b = Polynomial() # 构建 A(x) for _ in range(a): coef, exp = map(int, input().split()) poly_a.add_term(coef, exp) # 构建 B(x) for _ in range(b): coef, exp = map(int, input().split()) poly_b.add_term(coef, exp) op = input().strip() # 运算符 (+, -, *) if op == '+': # 加法 res_poly = Polynomial._add(poly_a, poly_b) elif op == '-': # 减法 res_poly = Polynomial.subtract(poly_a, poly_b) elif op == '*': # 乘法 res_poly = poly_a.multiply(poly_b) results.append(res_poly.to_string()) # 输出所有结果 for r in results: print(r) if __name__ == "__main__": main() ``` 此代码实现了基于链表的数据结构来完成多项式的加法、减法和乘法运算[^1]。它能够按照指定格式接收多组输入，并返回对应的计算结果。 ---