按照升幂排列的一元多项式P n (x)=p 1 x+p 2 x 2 +⋯+p n x n 可以用线性表来表示P=(p 1 ,p 2 ,…,p n ),对于一元多项式各种操作,实际上可以利用线性表来处理。若多项式的非零项指数很高并且非零项很少称之为稀疏多项式,此时使用链式存储结构较为方便。设计一个程序,实现一元稀疏多项式简单计算器。
时间: 2024-03-13 20:48:19 浏览: 153
好的,我来设计一个简单的一元稀疏多项式计算器。首先,我们需要定义一个存储一元稀疏多项式的链表节点,包括该项的系数和指数,可以定义如下:
```
class PolyNode:
def __init__(self, coef=0, exp=0):
self.coef = coef
self.exp = exp
self.next = None
```
然后,我们可以定义一个一元稀疏多项式类,该类包括多项式的头节点和一些基本操作,如多项式的加、减、乘、求导等等,具体实现如下:
```
class SparsePoly:
def __init__(self):
self.head = PolyNode()
# 添加一项到多项式
def add_term(self, coef, exp):
if coef == 0:
return
node = PolyNode(coef, exp)
cur = self.head
while cur.next and cur.next.exp > exp:
cur = cur.next
if cur.next and cur.next.exp == exp:
cur.next.coef += coef
if cur.next.coef == 0:
cur.next = cur.next.next
else:
node.next = cur.next
cur.next = node
# 多项式加法
def __add__(self, other):
res = SparsePoly()
cur1, cur2 = self.head.next, other.head.next
while cur1 and cur2:
if cur1.exp > cur2.exp:
res.add_term(cur1.coef, cur1.exp)
cur1 = cur1.next
elif cur1.exp < cur2.exp:
res.add_term(cur2.coef, cur2.exp)
cur2 = cur2.next
else:
res.add_term(cur1.coef + cur2.coef, cur1.exp)
cur1, cur2 = cur1.next, cur2.next
while cur1:
res.add_term(cur1.coef, cur1.exp)
cur1 = cur1.next
while cur2:
res.add_term(cur2.coef, cur2.exp)
cur2 = cur2.next
return res
# 多项式减法
def __sub__(self, other):
res = SparsePoly()
cur1, cur2 = self.head.next, other.head.next
while cur1 and cur2:
if cur1.exp > cur2.exp:
res.add_term(cur1.coef, cur1.exp)
cur1 = cur1.next
elif cur1.exp < cur2.exp:
res.add_term(-cur2.coef, cur2.exp)
cur2 = cur2.next
else:
res.add_term(cur1.coef - cur2.coef, cur1.exp)
cur1, cur2 = cur1.next, cur2.next
while cur1:
res.add_term(cur1.coef, cur1.exp)
cur1 = cur1.next
while cur2:
res.add_term(-cur2.coef, cur2.exp)
cur2 = cur2.next
return res
# 多项式乘法
def __mul__(self, other):
res = SparsePoly()
cur1 = self.head.next
while cur1:
cur2 = other.head.next
while cur2:
coef = cur1.coef * cur2.coef
exp = cur1.exp + cur2.exp
res.add_term(coef, exp)
cur2 = cur2.next
cur1 = cur1.next
return res
# 多项式求导
def derivative(self):
res = SparsePoly()
cur = self.head.next
while cur:
coef = cur.coef * cur.exp
exp = cur.exp - 1
res.add_term(coef, exp)
cur = cur.next
return res
# 打印多项式
def __str__(self):
if not self.head.next:
return "0"
res = ""
cur = self.head.next
while cur:
if cur.coef > 0 and res:
res += "+"
res += str(cur.coef)
if cur.exp > 1:
res += "x^" + str(cur.exp)
elif cur.exp == 1:
res += "x"
cur = cur.next
return res
```
以上就是一个简单的一元稀疏多项式计算器的实现。你可以通过定义两个多项式对象,然后进行加减乘等操作,最后打印结果来测试程序的正确性。
阅读全文