数据结构》课件C语言02.ppt

空间效率分析 链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。 2.4.1多项式的线性表表示 An(x)=anxn+an-1xn-1+...+a1x+a0 ,用线性表表示为： A=(an,an-1,...,a1,a0) 若多项式的阶次很高，而系数ai不为零的很少，则这 种表示浪费空间。 可写为： A(x)=amxem+an-1xem-1+...+a1xe1+a0xe0,用线性表表示为: A=((am,em),(am-1,em-1),...,(a1,e1),(a0,e0)) 二、多项式相加的方法 A+B=C 1、线性表C置空 2、各取线性表A和B的第一个元素作为当前处理的元素 3、比较当前处理的元素的指数值，相等，系数相加若不为零追加到线性表C，各取线性表A和B的下一个元素作为当前处理的元素；若指数不相等，则把大的元素追加到线性表C， 2.4 应用举例 (一元多项式的计算) 取该元素所在线性表的下一个元素作为当前处理的元素。 4、重复步骤3直到其中一个线性表处理完毕，再把另一个线性表的剩余元素追加到线性表C。 在计算机中，可以用一个线性表来表示: P = (p0, p1, …，pn) 一元多项式 但是对于形如 S(x) = 1 + 3x10000 – 2x20000 的多项式，上述表示方法是否合适？ 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 e2 ┄ em = n 可以下列线性表表示： （（p1, e1）, (p2, e2), ┄, (pm,em) ） 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 { // 项的表示 float coef; // 系数 int expn; // 指数 } term, ElemType; typedef OrderedLinkList polynomial; // 用带表头结点的有序链表表示多项式 结点的数据元素类型定义为: Status CreatPolyn ( polynomail P, int m ) { // 输入m项的系数和指数，建立表示一元多项式的有序链表P } // CreatPolyn InitList (P); e.coef = 0.0; e.expn = -1; SetCurElem (h, e); // 设置头结点的数据元素 for ( i=1; i=m; ++i ) { // 依次输入 m 个非零项 } return OK; scanf (e.coef, e.expn); if (!LocateElem ( P, e, (*cmp)()) )