《数据结构》-一元多项式的表示及相加

2.1 线性表的类型定义,2.3 线性表的链式表示和实现,2.4 一元多项式的表示及相加,2.2 线性表的顺序表示和实现,第二章 线性表,2.4 一元多项式的表示及相加,若对P,Q,R采用顺序存储结构，则问题很简单：,在数学上，一个多项式可表示为： 。用线性表可表示为 。 假设 是一元m次多项式： （mn）。 则两个多项式相加的结果： 。用线性表可表示为： 。,p0 q0 p0 + q0 p1 q1 p1 + q1, + pm qm pm + qm pn pn,但是对于形如,S(x) = 1 + 3x10000 2x20000,的多项式，上述表示方法是否合适？,然而，在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。例如：。就要用一长度为20001的线性表来表示，而表中仅有3个非零元素，这种对内存空间的浪费是应该避免的。,为此我们可以用单链表来实现。在单链表中每个结点有两个数据项（系数项和指数项）。,例如： 和 相加。A -1 7 0 3 1 9 8 5 17 B -1 8 1 22 7 -9 8 C -1 7 0 11 1 5 17 22 7 图2.14 多项式相加链式存储结构示例,一元多项式的实现：,typedef struct / 项的表示 float coef; / 系数 int expn; / 指数 term, ElemType;,typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,void AddPolyn (Polynomial ,算法2.15如下：,多项式相加,else /删除多项式PA中当前结点DelFirst (ha, qa);FreeNode (qa);DelFirst (hb, qb);FreeNode (qb);qb = NextPos (Pb, hb);qa = NextPos (Pa, ha);break;case 1:/多项式PB中当前结点的指数值小DelFirst (hb, qb);InsFirst (ha, qb);qb = NextPos (Pb, hb);ha = NextPos (Pa, ha);break; /switch /whileif (!ListEmpty (pb) Append (Pa, qb);/链接Pb中剩余结点FreeNode (hb);/释放Pb的头结点 /AddPolyn,两个一元多项式相乘的算法，可以利用两个一元多项式相加的算法来实现，因为乘法运算可以分解为一系列的加法运算。假设A(x)和B(x)为多项式：则：M(x) = A(x) B(x) = A(x) = 其中每一项都是一个一元多项式。,本章小结,1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌