按照升幂排列的一元多项式P n (x)=p 1 x+p 2 x 2 +⋯+p n x n 可以用线性表来表示P=(p 1 ,p 2 ,…,p n ),对于一元多项式各种操作,实际上可以利用线性表来处理。若多项式的非零项指数很高并且非零项很少称之为稀疏多项式,此时使用链式存储结构较为方便。设计一个程序,实现一元稀疏多项式简单计算器。 基本要求 稀疏多项式简单计算器的基本功能是: (1)输入并建立多项式; (2)输出多项式,输出形式为整数序列:n,p 1 ,e 1 ,p 2 ,e 2 …,p n ,e n ,其中n是多项式的项数,p i 和e i 分别是第i项的系数和指数,序列按指数升幂排列; (3) 多项式a和b相加,建立多项式a+b; (4) 多项式a和c相减,建立多项式a-b; (5) 计算多项式在x处的值。 测试数据 (1)(x+x 2 +x 3 )+(x+x 2 )=(2x+2x 2 +x 3 ) (2) 当x=1,多项式(2x+2x 2 +x 3 )=5 (3)计算完成后销毁多项式 实现提示 用带表头结点的单链表存储多项式,每个结点由系数域、指数域、指针域组成。
时间: 2023-12-14 20:05:39 浏览: 158
好的,我可以为您提供一个基于链表存储结构的一元稀疏多项式简单计算器的实现。下面是代码实现及注释:
```python
class PolyNode:
def __init__(self, coef=0, exp=0, next=None):
self.coef = coef # 系数
self.exp = exp # 指数
self.next = next # 指向下一个节点的指针
class PolyList:
def __init__(self):
self.head = PolyNode() # 表头节点,不存储数据
def create_poly(self):
"""
输入并建立多项式
"""
print("请输入多项式,每一项用逗号分隔,输入0结束:")
while True:
coef, exp = input().split(",")
if coef == "0":
break
coef, exp = int(coef), int(exp)
# 创建新节点
new_node = PolyNode(coef, exp)
# 插入新节点
p = self.head
while p.next is not None and p.next.exp > exp:
p = p.next
if p.next is not None and p.next.exp == exp:
p.next.coef += coef
if p.next.coef == 0:
p.next = p.next.next
else:
new_node.next = p.next
p.next = new_node
def print_poly(self):
"""
输出多项式
"""
p = self.head.next
if p is None:
print("0")
else:
print("{},{},{}".format(p.coef, p.exp, end=""))
p = p.next
while p is not None:
print(",{},{},{}".format(p.coef, p.exp, end=""))
p = p.next
print("")
def add_poly(self, another_poly):
"""
多项式相加
"""
p1, p2 = self.head.next, another_poly.head.next
result = PolyList()
while p1 is not None and p2 is not None:
if p1.exp > p2.exp:
result.insert_node(p1.coef, p1.exp)
p1 = p1.next
elif p1.exp < p2.exp:
result.insert_node(p2.coef, p2.exp)
p2 = p2.next
else:
coef_sum = p1.coef + p2.coef
if coef_sum != 0:
result.insert_node(coef_sum, p1.exp)
p1 = p1.next
p2 = p2.next
while p1 is not None:
result.insert_node(p1.coef, p1.exp)
p1 = p1.next
while p2 is not None:
result.insert_node(p2.coef, p2.exp)
p2 = p2.next
return result
def sub_poly(self, another_poly):
"""
多项式相减
"""
p = another_poly.head.next
while p is not None:
p.coef *= -1
p = p.next
result = self.add_poly(another_poly)
return result
def eval_poly(self, x):
"""
计算多项式在x处的值
"""
p = self.head.next
val = 0
while p is not None:
val += p.coef * (x ** p.exp)
p = p.next
return val
def insert_node(self, coef, exp):
"""
在多项式中插入新节点
"""
new_node = PolyNode(coef, exp)
p = self.head
while p.next is not None and p.next.exp > exp:
p = p.next
if p.next is not None and p.next.exp == exp:
p.next.coef += coef
if p.next.coef == 0:
p.next = p.next.next
else:
new_node.next = p.next
p.next = new_node
def destroy_poly(self):
"""
销毁多项式
"""
p = self.head.next
while p is not None:
q = p
p = p.next
del q
self.head.next = None
# 主程序
if __name__ == "__main__":
print("请输入第一个多项式:")
poly1 = PolyList()
poly1.create_poly()
print("第一个多项式为:")
poly1.print_poly()
print("请输入第二个多项式:")
poly2 = PolyList()
poly2.create_poly()
print("第二个多项式为:")
poly2.print_poly()
poly3 = poly1.add_poly(poly2)
print("第一个多项式加上第二个多项式的结果为:")
poly3.print_poly()
poly4 = poly1.sub_poly(poly2)
print("第一个多项式减去第二个多项式的结果为:")
poly4.print_poly()
x = int(input("请输入x的值:"))
val = poly1.eval_poly(x)
print("第一个多项式在x={}处的值为:{}".format(x, val))
poly1.destroy_poly()
poly2.destroy_poly()
poly3.destroy_poly()
poly4.destroy_poly()
```
注意:在输入多项式时,需要按照指数从小到大的顺序输入,否则输出结果会出错。
阅读全文