第04讲 一元多项式与线性表习题.doc

数据结构第 4 次课章节名称2.4 一元多项式的表示及相加线性表总结与习题目的要求1. 熟悉线性链表的应用（一元多项式的表示及相加运算）。熟练地通过上机编程练习掌握对线性表的操作算法。2. 通过习题的练习，熟练掌握线性表的操作和具体应用。主要内容与时间概算序号主要内容时间概算1一元多项式及相加的表示10分2一元多项式及相加的实现35分3本章知识点回顾5分4内容精要15分5习题35分共计100分重点难点重点：一元多项式的表示及相加的表示与实现；难点：采用线性表实现一元多项式相加。方法手段采用教员课堂讲授、学员上机实验实施教学。授课中应对于重/难点作详细分析，并结合课堂讲授的内容实施上机实验教学任务。（续表）课 堂 提 问在计算机中如何表示一个一元多项式Pn(x) = p0+ p1x+ p2x2+.+ pnxn？本 次 课 内 容 总 结1. 一元多项式及相加的表示；2. 一元多项式及相加的实现；3. 本章知识要点回顾及内容精要；思考题作业题1. 约瑟夫（Joseph）问题：编号为1，2，n的n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值m，然后，从第一个人开始按顺时针方向自1开始顺序报数，报到m的人离开桌旁，并将他手中的密码作为新的m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从1报数，如此下去，直至所有人全部离开桌旁为止。2. 假设有7个人，编号从1到7，他们手中的密码分别是3，1，7，2，4，8，4，最初的m=2，通过报数，这7个人离开桌旁的顺序应该是：2，3，5，4，7，6，1。参考资料数据结构辅导与提高，徐孝凯编著，清华大学出版社数据结构习题解答与考试指导，梁作娟等编著，清华大学出版社授课内容2.4 一元多项式的表示及相加一、一元多项式的表示在数学上，一元多项式Pn(x)可按升幂写成： Pn(x) = p0+ p1x+ p2x2+.+ pnxn它由n+1个系数唯一确定 ，因此，在计算机里，它可用一个线性表P来表示： P = (p0 ,p1 ,p2 , pn)每一项的指数i隐含在其系数pi的序号里。 然而在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难决定。形如: S(x) = 1+3x10000+2x2000的多项式时，就要用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显然必须同时存储相应的指数。 一般情况下的一元n次多项式可写成: Pn(x) = p1xe1 + p2xe2 + + pmxem 其中pi，是指数为ei的项的非零系数，且满足0 e1 e2 =0；TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1= | ai-1, ai D，且ai-1中的指数值0的元素的前驱的位置，并返回FALSE ；Status OrderInsert( LinkList &L，ElemType e，int(*compare) (ElemType， ElemType) )；/ 按有序判定函数compare()的约定，将值为e的结点插入到有序链表L的适当位置（1）抽象数据类型Polynomial的实现typedef struct /项的表示，多项式的项作为LinkList的数据元素float coef； /系数int expn； /指数term，ElemType； /两个类型名：term用于本ADT，ElemType为LinkList的数据对象名typedef LinkList polynomial；/用带头结点的有序链表表示多项式（2）基本操作的函数原型说明void CreatPolyn (polynomail &P，int m) /输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid DestroyPolyn (polynomail &P)； /销毁一元多项式P void PrintPolyn (polynomail P)； /打印输出一元多项式P int PolynLength (polymomail P)； /返回一元多项式P中的项数void AddPolyn (polynomail &Pa，polynomail &Pb)；/完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb void SubtractPolyn (polynomail &Pa，polynomail &Pb)；/完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb void MultiplyPolyn (polynomail &Pa，polynomail &Pb)； /完成多项式相乘运算，即：Pa= Pa * Pb，并销毁一元多项式Pb（3）基本操作的算法描述(部分) int cmp (term a，term b)； /依a的指数值)b的指数值，分别返回-1,0和1；void CreatPolyn (polynomail &P，int m) /输入m项的系数和指数，建立表示一元多项式的有序链表PInitList(P)；h = GetHead(P)；e.coef = 0.0；e.expn = -1；SetCurElem (h，e)； /设置头结点的数据元素 for( i=1；i next = HL； B） p - next = HL； HL = p ； C） p - next = HL； p = HL ； D） p - next = HL - next； HL - next = p ；（2）在一个单链表HL中，若要在指针q指向的结点的后面插入一个由指针P指向的结点，则执行（ ）。 A） q - next = p - next ； p = q； B） p - next = q - next ； q = p； C） q - next = p - next ； p - next = q ； D） p - next = q - next ； q - next = p ；（3）指出以下算法中的错误和低效（费时）之处，并将其修改正确。Status DeleteK ( &L,i,k) /从顺序存储结构的线性表L中删除第i个元素起的K个元素 if ( i 1 | k L.len ) return ERROR; for (count = 1; count = i; j- - ) L.elemj-1 = L.elemj; L.len - -; return OK; / DeleteK2. 算法设计题（1）有一个有n个结点的单链表，设计一个函数将第i-1个结点与第i个结点互换，但指针不变。（2）已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然递增有序。（3）已知一个顺序表，编写一个函数从此顺序表