2.4　一元多项式的表示和相加

视频二维码（扫码观看）

一、一元多项式的表示

一元多项式p（x）＝p₀＋p₁x＋p₂x²＋…＋p_nxⁿ，由n＋1个系数唯一确定。则在计算机中可用线性表（p₀，p₁，p₂，…，p_n）表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下：

（1）顺序存储表示的类型

（2）链式存储表示的类型

二、一元多项式的相加

不失一般性，设有两个一元多项式：

P（x）＝p₀＋p₁x＋p₂x²＋…＋p_nxⁿ，Q（x）＝q₀＋q₁x＋q₂x²＋…＋q_mx^m（m＜n）

R（x）＝P（x）＋Q（x）

R（x）由线性表R（（p₀＋q₀），（p₁＋q₁），（p₂＋q₂），…，（p_m＋q_m），…，p_n）唯一表示。

1．顺序存储表示的相加

线性表的定义

用顺序表表示的相加非常简单。访问第5项可直接访问：L.a[4].coef，L.a[4].expn

2．链式存储表示的相加

当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。

一元多项式相加的实质是：

若指数不同，则是链表的合并。

若指数相同，则系数相加，和为0，去掉结点，和不为0，修改结点的系数域。

①算法之一：

就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不再存在，因此再对原来两个多项式进行其他操作就不允许了。

算法描述

②算法之二：

对两个多项式链表进行相加，生成一个新的记录相加后的结果的多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其他操作也不影响。

算法描述