东华大学数据结构第二章线性表.ppt

一个带头结点的线性链表类型定义：P37~38数据结构（C语言版严蔚敏著）.pdf 2.3 线性表的链式表示及实现 多项式运算的问题，几乎成为表处理的一个经典问题。用单链表结构来表示多项式，研究两个多项式的相加运算 一元多项式 Pn(x) = p0+p1x+p2x2+?+pnxn Qm(x) = q0+q1x+q2x2+?+qmxm 在计算机中可以用一个线性表P, Q（顺序存储）来表示： P = (p0, p1, p2, ? ,pn) Q = (q0, q1, q2, ? ,qm) 每一项的指数都隐含在系数pi , qj的序号里 2.4 一元多项式的表示及相加 多项式相加： Rn(x)= Pn(x)+Qm(x) (mn) 在计算机中可以用一个线性表R（顺序存储）来表示： R = (p0+q0, p1+q1, p2+q2, pm+qm, pm+1,?, pn) 采用顺序结构使的多项式相加的算法非常简洁 这种表示方法对于所有项都比较全的时候是很好的，但是如果指数很高并且变化很大时，不合适，顺序表的最大长度难以确定。 2.4 一元多项式的表示及相加 例如：一个稀疏多项式 : S(x) = 1+3x109-5x231+6x354 把每一项的系数和指数都存储下来，也就是对于每一项都用两个数据项来存储。即为如下的形式： P=((p1,e1), (p2,e2), ?(pm,em)) 可用线性表((1,0), (3,109), (-5, 231), (6, 354)) 表示 对于这种表示方法，采用链式存储。利用单链表表示多项式时，每个结点设有三个域：系数域coef，指数域exp和链域next。 2.4 一元多项式的表示及相加 coef exp next 抽象数据类型一元多项式的定义 ADT Polynomial { 数据对象：D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 } 数据关系：R1＝{ ai-1 ,ai |ai-1 ,ai∈D, 且ai-1中的指数值＜ai中的指数值，i=2,...,n } 基本操作： CreatPolyn ( P, m ) 操作结果：输入m项的系数和指数，建立一元多项式P。 DestroyPolyn ( P ) 初始条件：一元多项式P已存在。 2.4 一元多项式的表示及相加 操作结果：销毁一元多项式P。 PrintPolyn ( P ) 初始条件：一元多项式P已存在。 操作结果：打印输出一元多项式P。 AddPolyn ( Pa, Pb ) 初始条件：一元多项式Pa和Pb已存在。 操作结果：完成多项式相加运算，即：Pa = Pa＋Pb， 并销毁一元多项式Pb。 SubtractPolyn ( Pa, Pb ) 初始条件：一元多项式Pa和Pb已存在。 操作结果：完成多项式相减运算，即：Pa = Pa－Pb， 并销毁一元多项式Pb。 2.4 一元多项式的表示及相加 MultiplyPolyn ( Pa, Pb ) 初始条件：一元多项式Pa和Pb已存在。 操作结果：完成多项式相乘运算，即：Pa = Pa×Pb， 并销毁一元多项式Pb。 PolynLength( P ) 初始条件：一元多项式P已存在。 操作结果：返回一元多项式P中的项数。 } ADT Polynomial 2.4 一元多项式的表示及相加 例 AH = 1 - 10x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18 CH(x)=AH(x)+BH(x) 它的单链表表示如图 2.4 一元多项式的表示及相加 多项式的加法运算规则: (1) 若指数相等，系数相加，得C(x)的一项（若和为0，此项不存在）； (2) 若A(x)当前项指数小于B(x)，复抄A(x)的这一项到C(x)上； (3) 若A(x)当前项指数大于B(x)，复抄B(x)的这一项到C(x)上； (4) 若一个多项式每项都加到C(x)上了，就把另一多项式的剩余部分复抄到C(x)上。 2.4 一元多项式的表示及相加 C(x)是动态建立的，需要从表头指针所指的结点开始检测，为此我们设两个指针pa和pb分别指向两个多项