数据结构重读 – 一元多项式的表示及相加

一元多项式的表示及相加:

我们定义P(x)=p0+p1*x+p2*x^2…pn*x^n简写为P=(p0, p1, p2…pn)

再定义Q=(q0, q1, 12…qm)

现在要求R = P(X) + q(X),显然,实际上R=(p0+q0, p1+q1, p2+q2 .. pm+1, pn) 假设m<n。

这种应用场景,用顺序存储不合适,它虽然运算简单,但因为很有可能从1~1000次幂都是0,是稀疏的。因此,链表类似的存储更合适。

首先考虑加法,其实算法很简单:
我们假设多项式是按照幂次递增的,例如7+3x+9x^8+5x^17。
假设指针pa和pb分别指向多项式A和B的某个结点,pc指向结果。
(0)while pa!=NULL && pb!=NULL
(1)若pa的幂次<pb的幂次,将pa复制到pc新结点,pa后移动;
(2)若pb的幂次<pa的幂次,pb复制到pc新结点,pb后移动;
(3)若pa幂次和pb幂次相等,则结点的系数相加;pa、pb后移。如果和不为零,则将pa和pb的系数相加,放到pc新结点中,继续操作;
(4)如果退出while后,pa或者pb依然不是0,把他们复制到pc中。

注意:一元多项式相加这种不涉及到进位,退位!

算法如下:

 

Leave a Reply

Your email address will not be published.