数据结构（2）：链表（下）
数据结构（2）：链表（下）
上一回，我讲了一下链表的定义和基本操作的实现；这一会我们来看一下链表相关的一个典型应用：一元多项式！一元多项式的定义
形如 an*x^n+...+a1*x+a0 的表达式称之为一元多项式。在计算机中，我们可以一个线性表来存储一个一元多项式，表中的每个元素是每一项的系数和指数的一个整体。众所周知，线性表有两种存储结构——顺序存储结构和链式存储结构。那么，应该使用哪一种存储结构？因为考虑到存在合并同类项的操作，合并同类项经常需要删除已经参与合并的元素，而顺序表删除元素可能需要大量移动元素，而链表不需要，所以我们选择链式存储结构。
下面我就来说一下我选择的是什么样的链式存储结构，我选择带头结点（头结点没有信息）的单链表。
结点类型描述如下：
class Polynomial:
def __init__(self, coefficient=1.0, exponent=0):
self.coefficient = coefficient
self.exponent = exponent
self.next = None
coefficient 表示系数，exponent 表示指数，next 就是指针域。
创建一元多项式
创建一元多项式很简单，首先我们需要提供需要的系数和指数的整体构成的一个容器即可，格式：[(系数 0, 指数 0), (系数 1, 指数 1)……]，当然格式你想弄成什么样的都可以，只要体现出内容即可。如果容器为空，直接结束；否则遍历容器，根据提供的系数和指数添加新项。最后进行化简即可。代码如下：
def create_polynomial(self, ces):
if not ces:
return
item = Polynomial(ces[0][0], ces[0][1])
r = self.next = item
for coefficient, exponent in ces[1:]:
item = Polynomial(coefficient, exponent)
r.next = item
r = item
self.simplify()
大家可能就最后一行 simplify 方法有点迷，这个就是接下来要讲的化简方法。
化简
因为考虑到里面有系数为 0 的项以及指数相同的项，如果不进行化简将极大的浪费存储空间并且会导致运算变得复杂。化简操作分为两步：
- 对指数相同的项进行合并，也就是合并同类项。
- 删除系数为 0 的项。
这两步不能颠倒顺序，因为考虑到多项式 2*x+x^2+(-2)*x，如果先删去系数为 0 的项，再执行合并同类项，会使得这个多项式变成 0*x+x^2，这显然不是最简。代码如下：
def simplify(self):
p = self.next
while p:
pre_q = p
q = pre_q.next
while q:
if p.exponent == q.exponent:
p.coefficient += q.coefficient
pre_q.next = q.next
q = pre_q.next
else:
pre_q, q = pre_q.next, q.next
p = p.next
pre, p = self, self.next
while p:
if p.coefficient == 0:
pre.next = p.next
p = pre.next
else:
pre, p = pre.next, p.next
第一个 while p 对应合并同类项的操作，第二个 while p 对应删除系数为 0 的项的操作。
复制
这个复制操作不是非要有的，我主要是考虑到一般情况下我们不希望对一个多项式就地修改而设计的。复制操作非常简单，通过获取当前多项式每一项的系数和指数来创建一个新的多项式并返回即可。后面需要返回修改后的多项式的操作我都不会就地修改，而是返回修改后的副本。复制操作的实现代码如下：
def copy(self):
p, ces = self.next, []
while p:
ces.append((p.coefficient, p.exponent))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
复制操作的实现代码非常简单，不讲了。
求导
我们如果把这个多项式看成一个关于某个变量（这里是 x）的函数，那么我们就可以对它求导以及积分，求导操作非常简单，根据幂函数的求导公式，常数乘以一个函数的求导公式以及多个函数相加的求导公式即可得出多项式的求导公式：(an*x^n+...+a1*x+a0)'=(an*n)*x^(n-1)+...+a1。需要注意的是常数项求导为 0，常数项就是指数为 0，但是系数不为 0 的项（一个经过化简之后的多项式最多只有一项常数项）。代码如下：
def derivative(self):
p, ces = self.next, []
while p:
if p.exponent:
ces.append((p.coefficient*p.exponent, p.exponent-1))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
代码实现求导操作非常简单，下面我们直接看到求导的逆运算：积分。
积分
既然常数求导数会变成 0，那么积分是不是会把 0 变成任意常数呢？当然会，只不过我在实现积分操作并不会去加上某个常数或者表示常数的一个字母，而是直接令其为 0，代码如下：
def integral(self):
p, ces = self.next, []
while p:
ces.append((p.coefficient/(p.exponent+1), p.exponent+1))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
看完了两个复杂的数学运算之后，我们先看一下如何人性化地输出多项式，也就是多项式转字符串操作。
转字符串
若为 0 多项式（0 多项式就是多项式的系数全部为 0），则格式为 Polynomial(0)；否则格式为 Polynomial(c0*x^e0+...+cn*x^en)。代码如下：
def __str__(self):
p = self.next
if not p:
return'Polynomial(0)'
s = f'Polynomial({p.coefficient}*x^{p.exponent}'
while p:
p = p.next
if p:
if p.coefficient > 0:
s += f'+{p.coefficient}*x^{p.exponent}'
else:
s += f'{p.coefficient}*x^{p.exponent}'
else:
s += ')'
return s
第 9 行到第 12 行这个 if...else... 大家可能会有点迷，简单地说，就是看当前项的系数是不是大于 0，如果是，就在系数前面补上一个 + 号，来充当运算符 +，那么为什么小于 0 不去补上 - 号呢？这是因为一个数在格式化字符串的过程中默认省略 + 号，不省略 - 号，所以使用不会省略的 - 号来充当运算符 -。
求负
求负非常简单，就是整个多项式乘 -1，也就是每一项的系数乘 -1，代码如下：
def __neg__(self):
p, ces = self.next, []
while p:
ces.append((-p.coefficient, p.exponent))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
单个多项式的运算就这么多，接下来我们看到多项式和一个数的运算以及两个多项式的运算。
两个多项式的加法
两个多项式的加法非常简单，依次读取两个多项式的每一项的系数和指数并放入有一个容器中，随后根据这个容器创造一个新的多项式并化简即可。代码如下：
def __add__(self, other):
if self is other:
other = other.copy()
p, q, ces = self.next, other.next, []
while p:
ces.append((p.coefficient, p.exponent))
p = p.next
while q:
ces.append((q.coefficient, q.exponent))
q = q.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
需要注意的就只有开头的 if 了，在这里我判断两个指针是否指向同一个多项式，如果是就需要对另一个进行复制，避免两个指针对同一个对象同时操作导致各种各样的问题，后面的运算写上这个 if 的原因也是一样。
两个多项式的减法
只要实现了加法和求负，两个多项式的减法简直太简单了，因为学过数学都知道 a-b=a+(-b)，直接利用这个公式，实现两个多项式的减法简直就是太简单了，代码如下：
def __sub__(self, other):
if self is other:
other = other.copy()
return self+-other
大家唯一不理解的应该就是 -other 怎么没有括号。其实是因为求负的优先级高于加法。
两个多项式的乘法
两个多项式的乘法略微有点复杂，毕竟要把两个多项式的每一项系数部分都得两两相乘，把两个多项式的每一项指数部分都得两两相加，代码如下：
def __mul__(self, other):
if self is other:
other = other.copy()
p, ces = self.next, []
while p:
q = other.next
while q:
ces.append((p.coefficient*q.coefficient, p.exponent+q.exponent))
q = q.next
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
看完了两个多项式的乘法，大家可能会去实现多项式的除法，但是多项式的除法并没有想的那么简单。
多项式除以一个数
在实现多项式除以一个数之前，首先看来说一下为什么不去实现多项式的除法，因为多项式的除法并不一定能保证商是一个多项式，比如 x/(x+1)，这种情况下结果就不是一个多项式，因为结果无论怎样都会有分式，非常麻烦，所以我就不去实现两个多项式相除，而是直接去实现多项式除以一个数，只要这个数不为 0，除完之后结果还是一个多项式。
多项式除以一个数，就是把多项式的每一项的系数除以这个数，实现代码如下：
def __truediv__(self, num):
p, ces = self.next, []
while p:
ces.append((p.coefficient/num, p.exponent))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
其实之前讲的求负操作也可以利用这个除操作来实现，把除的那个数变成 -1 就行。
多项式的 n 次方
一个多项式乘 n 次就是一个多项式的 n 次方，代码如下：
def __pow__(self, n):
polynomial = Polynomial()
if not self.next and n:
return polynomial
polynomial.create_polynomial([(1, 0)])
for _ in range(n):
polynomial = polynomial*self
return polynomial
如果为 0 多项式的非 0 次方，那么返回 0 多项式（0 的非 0 次方等于 0），否则创建一个系数为 1 的常数多项式，和当前的多项式实例进行乘操作 n 次。如果不进行自乘，直接返回系数为 1 的常数多项式（任何非 0 数的 0 次方等于 1；在级数中，0 的 0 次方可以看成 1）。
两个多项式判断相等
两个多项式判断相等，就判断两个多项式的每一项是否相等，多项式的每一项相等，就是该项的系数和指数在另一个多项式中可以找到，又因为 1+x==x+1 所以看多项式是否相等不看多项式中每一项的具体位置，这个时候可以把判断两个多项式是否相等等价于判断两个集合是否相等，每个集合中的元素是一个元组，格式：(系数, 指数)。代码如下：
def __eq__(self, other):
if type(other) != Polynomial:
return False
self_ces, other_ces, p, q = set(), set(), self.next, other.next
while p:
self_ces.add((p.coefficient, p.exponent))
p = p.next
while q:
other_ces.add((q.coefficient, q.exponent))
q = q.next
return True if self_ces == other_ces else False
第一行的 if 是为了处理其他类型和多项式进行 == 运算的情况。
总结
最后给出完整代码以及对应的测试结果。
class Polynomial:
def __init__(self, coefficient=1.0, exponent=0):
self.coefficient = coefficient
self.exponent = exponent
self.next = None
def create_polynomial(self, ces):
if not ces:
return
item = Polynomial(ces[0][0], ces[0][1])
r = self.next = item
for coefficient, exponent in ces[1:]:
item = Polynomial(coefficient, exponent)
r.next = item
r = item
self.simplify()
def simplify(self):
p = self.next
while p:
pre_q = p
q = pre_q.next
while q:
if p.exponent == q.exponent:
p.coefficient += q.coefficient
pre_q.next = q.next
q = pre_q.next
else:
pre_q, q = pre_q.next, q.next
p = p.next
pre, p = self, self.next
while p:
if p.coefficient == 0:
pre.next = p.next
p = pre.next
else:
pre, p = pre.next, p.next
def copy(self):
p, ces = self.next, []
while p:
ces.append((p.coefficient, p.exponent))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def derivative(self):
p, ces = self.next, []
while p:
if p.exponent:
ces.append((p.coefficient*p.exponent, p.exponent-1))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def integral(self):
p, ces = self.next, []
while p:
ces.append((p.coefficient/(p.exponent+1), p.exponent+1))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def __str__(self):
p = self.next
if not p:
return'Polynomial(0)'
s = f'Polynomial({p.coefficient}*x^{p.exponent}'
while p:
p = p.next
if p:
if p.coefficient > 0:
s += f'+{p.coefficient}*x^{p.exponent}'
else:
s += f'{p.coefficient}*x^{p.exponent}'
else:
s += ')'
return s
def __add__(self, other):
if self is other:
other = other.copy()
p, q, ces = self.next, other.next, []
while p:
ces.append((p.coefficient, p.exponent))
p = p.next
while q:
ces.append((q.coefficient, q.exponent))
q = q.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def __sub__(self, other):
if self is other:
other = other.copy()
return self+-other
def __mul__(self, other):
if self is other:
other = other.copy()
p, ces = self.next, []
while p:
q = other.next
while q:
ces.append((p.coefficient*q.coefficient, p.exponent+q.exponent))
q = q.next
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def __truediv__(self, num):
p, ces = self.next, []
while p:
ces.append((p.coefficient/num, p.exponent))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def __neg__(self):
p, ces = self.next, []
while p:
ces.append((-p.coefficient, p.exponent))
p = p.next
polynomial = Polynomial()
polynomial.create_polynomial(ces)
return polynomial
def __pow__(self, n):
polynomial = Polynomial()
if not self.next and n:
return polynomial
polynomial.create_polynomial([(1, 0)])
for _ in range(n):
polynomial = polynomial*self
return polynomial
def __eq__(self, other):
if type(other) != Polynomial:
return False
self_ces, other_ces, p, q = set(), set(), self.next, other.next
while p:
self_ces.add((p.coefficient, p.exponent))
p = p.next
while q:
other_ces.add((q.coefficient, q.exponent))
q = q.next
return True if self_ces == other_ces else False
if __name__ == '__main__':
p1 = Polynomial()
p1.create_polynomial([(1, 0), (1, 1)])
p2 = p1.copy()
print('求导：', p1.derivative())
print('积分：', p1.integral())
print('求负：', -p1)
print('加：', p1+p2)
print('减：', p1-p2)
print('乘：', p1*p2)
print('除一个数：', p1/2)
print('n 次方：', p1**2)
print('判断相等：', p1 == p2)
运行结果如图所示：
当然，我从今年开始已经入驻 B 站了！下面给出 B 站账号：新时代的运筹帷幄，喜欢的可以关注一下，看完视频不要忘记一键三连啊！
本文分享自 Python机器学习算法说书人 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！