第2章线性表A-3(2012-3-4).ppt

* 应用举例 (1)一元多项式的数学通式？ (2)用抽象数据类型如何描述它的定义？ (3)用C语言如何描述它的定义？ (4)如何编程实现两个一元多项式相加？ 求两个一元多项式的和 (参见教材P39 – 43) 讨论： * 实验：链表的应用-求两个一元多项式之和 [问题描述] 求两个一元多项式之和。假设要求用户按幂从大到小次序输入各结点，并且没有两个结点具有相同的幂，这样一个一元多项式的链表是按幂expn从大到小顺序排列的，将这两个有序单链表按expn值相加得到一个新的有序单链表。 [基本要求] 用单链表存储一元多项式，将两个存储一元多项式的单链表相加产生结果单链表。 [测试数据] 第一个一元多项式为：3x^3+2x^2-5x+6 第二个一元多项式为：2x^3-2x^2+5x+4 * (1) 一元多项式的数学通式 一元多项式的通式可表示为： 　　一元多项式在计算机内存储时，既可用顺序表存储，又可用链表存储。 顺序表 链表 am-1 em-1 … a0 e0 ^ * (2)一元多项式的抽象数据类型定义 （参见P40） 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=1,2,…,n} 基本操作： CreatPolyn(P,m) 操作结果：输入m项的系数和指数，建立一元多项式P。/建表 * DestroyPolyn(P) 初始条件：一元多项式P已存在。 操作结果：销毁一元多项式P。 /释放表 PrintPolyn(P) 初始条件：一元多项式P已存在。 操作结果：打印输出一元多项式P。 /输出表 PolynLength(P) 初始条件：一元多项式P已存在。 操作结果：返回一元多项式P中的项数。/求表长 * AddPolyn(Pa,Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa＝Pa＋Pb，并销毁一元多项式Pb。 /两表相加 SubtractPolyn(Pa,Pb) 初始条件：一元多项式Pa和Pb已存在。 操作结果：完成多项式相减运算，即：Pa＝Pa－Pb， 并销毁一元多项式Pb。 /两表相减 }ADT Polynomial MultiplyPolyn(Pa,Pb) 初始条件：一元多项式Pa和Pb已存在。 操作结果：完成多项式相乘运算，即：Pa＝Pa×Pb， 并销毁一元多项式Pb。 /两表相乘 * (3) 用C语言具体描述其定义 typedef struct polynode *pnode; struct polynode{ int coef; /*系数*／ int expn;　／*幂*/ struct polynode *next; }; 　　　　　 coef expn next * (4) 编程实现两个一元多项式相加 3 14 2 8 1 0 a ^ 8 14 －3 10 10 6 b ^ 例： 运算规则：两多项式中指数相同的项对应系数相加，若和不为0,则构成多项式c(=a+b)中的一项；a和b中所有指数不相同的项均应复制到c中。 * 实现过程： 依次比较Pa和Pb所指结点中的指数项，可分为 Pa-expn = Pb-expn 和 Pa-expn !=Pb-expn两种情况.若Pa-expn = Pb-expn,则将Pa和Pb所指结点中系数域的数值相加（并判其和是否为0）,否则将Pa和Pb所指结点中较高指数项的结点插入到新表c中。 3 14 2 8 1 0 ^ a Pa 8 14 -3 10 10 6 ^ b Pb 11 14 -3 10 2 8 1 0 ^ c Pc 10 6 + * #include stdio.h #include malloc.h typedef struct polynode *pnode; struct polynode{ int coef; /*系数*／ int expn;　／*幂*/ struct polynode *next; }; 具体编程（用C语言） * pnode createpoly() /*根据用