第章线性表.ppt

P999(x) = 7x3 - 2x12 - 8x999 例如: 可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) 表示 ADT Polynomial { 数据对象： 数据关系： 抽象数据类型一元多项式的定义如下： D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个 表示系数的实数和表示指数的整数 } R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 } CreatPolyn ( P, m ) DestroyPolyn ( P ) PrintPolyn ( P ) 基本操作： 操作结果：输入 m 项的系数和指数， 建立一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：销毁一元多项式 P。 初始条件：一元多项式 P 已存在。 操作结果：打印输出一元多项式 P。 PolynLength( P ) AddPolyn ( Pa, Pb ) SubtractPolyn ( Pa, Pb ) … … } ADT Polynomial 初始条件：一元多项式 P 已存在。 操作结果：返回一元多项式 P 中的项数。 初始条件：一元多项式 Pa 和 Pb 已存在。 操作结果：完成多项式相加运算，即： Pa = Pa＋Pb，并销毁一元多项式 Pb。 一元多项式基本操作的实现： typedef struct polyn { // 每一项的表示 float coef; // 系数 int expn; // 指数 struct polynode *next; } Polyn, ElemType; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: 则多项式 A99(x)=8-3x+9x10+2x99 与 B10(x)=5x+4x7-9x10 的单链表存储结构可分别表示如下，其头指针分别为Ah与Bh。 8 0 -3 1 9 10 2 99∧ Ah 5 1 4 7 -9 10 ∧ Bh 多项式的有序链表存储结构 一元多项式加法操作的具体实现： 例如，求和多项式 A99(x)=A99(x)+B10(x)。 // 用带表头结点的有序链表表示多项式 则和多项式 = 8-3x+9x10+2x99 + 5x+4x7-9x10 =8+2x+4x7 +2x99 如何求？ 8 0 2 1 4 7 2 99∧ Ah 操作步骤（思路参考2.1节中的有序表合 并算法）： 设指针qa和qb分别指向多项式有序链表Ah和Bh中当前进行比较的某个结点，则比较两个结点的数据域的指数项，有三种情况： （1）小于 :指针qa所指结点的指数值＜指针qb所指结点的指数值：将qa指针所指向的结点插入到“和链表”的后面，qa指针后移； （2）大于:指针qa所指结点的指数值＞指针qb所指结点的指数值：将qb指针所指向的结点插入到“和链表”的后面，qb指针后移； （3）等于:将两个结点中的系数相加，若和不为零，则修改qa所指结点的系数值,删除并释放qb所指结点，qa和qb指针均后移 ；若和为零，删除并释放指针qa和qb所指结点， qa和qb指针均后移。 8 0 -3 1 9 10 2 99∧ Ah 5 1 4 7 -9 10 ∧ Bh qa qc qb 2 qa qc s qb …… 求和多项式有序链表Ah的示意图 多项式的有序链表表示加法操作的算法实现 void AddPolyn(Polyn Ah, Polyn Bh) { Poly *qa, *qb, *qc, *s; qa=Ah-next; qb=Bh-next; qc=Ah; while(qa!=NULLqb!=NULL) { if(qa-exp qb-exp) { /*qc-next=qa;*/ qc=qa; qa=qa-next;} else if(qa-exp qb-exp) {qc