数据结构一元稀疏多项式

1、要求完成如下功能：（1） 输入并建立多项式creatpolyn()（2） 输出多项式，输出形式为整数序列，序列按指数升序排列printpolyn()（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式addpolyn()（4） 多项式a和b相减，建立多项式a-b，输出相减的多项式subpolyn()用带表头结点的单链表存储多项式。课 程 设 计学生姓名： 学 号： 专业班级： 课程名称： 数据结构 学年学期： 指导教师： 目 录1需求分析说明12概要设计说明33详细设计说明54调试分析105用户使用说明116课程设计总结127测试结果138参考书目169. 附录1724数 据 结 构

2、课 程 设 计1 需求分析说明1.程序所能达到的功能是（1） 输入并建立多项式creatpolyn()（2） 输出多项式，输出形式为整数序列，序列按指数升序排列printpolyn()（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式addpolyn()（4） 多项式a和b相减，建立多项式a-b，输出相减的多项式subpolyn()用带表头结点的单链表存储多项式。2输入的形式和输入值的范围 ：本系统要输入的数据主要是有多项式中每项的系数和指数，可以把它们定义为整形数据，既可以为整数也可以为非负整数，即有符号的整形数据，由于整形数据在内存里占用两个字节，所以它的取值范围为-327683

3、2767。其次还有就是选择功能时，要输入的功能号，它们是字符型数据，取值范围是ASS|表中的字符。例如输入的格式如下： 请输入a的项数：3请输入第一项的系数与指数：2，1请输入第二项的系数和指数：5，8请输入第三项的系数和指数：-3.1,11请输入b的项数：3请输入第一项的系数和指数：7，0请输入第一项的系数和指数：5，8请输入第三项的系数和指数：11,9* 多项式操作程序* A：输出多项式a B：输出多项式b * C：输出a+b D：输出a-b * F：退出程序 *请选择操作：Ca+b=2x+5x8-3.1x11+7-5x8+11x9请选择操作：Da-b=2x+5x8-3.1x11-7+5x

4、8-11x93.输出的形式：本系统要输出的是把创建好的第一个多项式和第二个多项式按指数升序排列，并把进行运算后的结果也按指数升序排列输出，输出形式如上面所示。4.测试数据正确的输入及输出结果：（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2） (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)2 概要设计说明模块调用图：主函数多项式相加建立链表输出多项式 1. 抽象数据类型的定义多项式的结点类型定义typedef struct Polynomial/多项式结点类型 float coef

5、; /多项式的系数 int expn; /多项式的指数 struct Polynomial *next;/指向下一个结点*Polyn,Polynomial;建立表示一元多项式的有序表Polyn CreatePolyn(Polyn head,int m)；销毁一元多项式void DestroyPolyn(Polyn p)；返回一元多项式的项数void PrintPolyn(Polyn P)；完成多项式加法运算Polyn AddPolyn(Polyn pa,Polyn pb)；完成多项式相减运算Polyn SubtractPolyn(Polyn pa,Polyn pb)；2.主程序的流程（1）输出

6、提示信息（2）输入多项式项数（3） 输入每项的系数和指数（4）输出选择操作的菜单（5） 根据选择输出多项式（6）释放链表占用的内存空间（7）完成退出程序3.各程序模块之间的层次（调用）关系本系统首先是创建多项式，在进行排序显示，然后按提示输入要实现的功能。此系统有五个模块，它们的调用关系如下：在CreatePolyn函数中调用Insert;在main函数中调用CreatePolyn(pa,m). CreatePolyn(pb,n). PrintPolyn(pa). PrintPolyn(pb). AddPolyn(pa,pb). SubtractPolyn(pa,pb). DestroyPol

7、yn(pa). DestroyPolyn(pb)3 详细设计说明1.设计中定义的所有数据类型伪码算法(1)多项式建立的算法该算法是用来创建多项式链表。首先要创建一个结点，并用一个指针指向它，并给它进行初始化void CreatPolyn(polynomial &p,int m)/输入m项的系数和指数，建立一元多项式的有序链表pInitList(p); h=GetHead(p);e.coef=0.0;e.expn=-1; SetCurElem(h,e);/设置头结点的数据元素for(i=1;inext; int flag=1;/项数计数器 if(!q) putchar(0); /若多项式为空，输

8、出0 printf(n); return; while(q) if(q-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1) /系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coe

9、f=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);(3)多项式加法的算法该模块是实现两个多项式相加的算法。要求两个多项式的指数从小到大的排列顺序。 void AddPolyn(polynomial &pa,polynomial &pb) /多项式加法 ha=GetHead(pa);hb=GetHead(pb); /ha和hb分别指向pa和pb的头结点 qa=NexPos(pa,ha);qb=NexPos(pb,hb);

10、/qa和qb分别指向和中当前结点 while(qa&qb) /qa和qb均非空 a=GetCurElem(qa);b=GetCurElem(qb); /a/和b为表中当前比较元素 switch(*cmp(a,b)case -1: /多项式pa中当前结点的指数较小 Ha=qa; qa=NexPos(pa,ha);case 0: /两者的指数相等 sum=a.coef+b. coef; if(sum!=0.0) /修改多项式pa中当前结点的系数值 SetCurElem(qa,sum); ha=qa; else /删除多项式pa中当前结点 DelFirst(ha,qa);FreeNode(qa);D

11、elFirst(hb,qb);FreeNode(qb); qb=NexPos(pb,qb);qa=NexPos(pa,ha);break;case 1: /多项式pb中当前结点的指数较小 DelFirst(hb,qb); InFirst(ha,qb); qb=NexPos(pb,hb); ha=NexPos(pa,ha); break if(!ListEmpty(pb) Append(pa.qb); /链接pb中剩余结点FreeNode(hb); /释放pb的头结点(4)多项式减法的算法该模块是实现两个多项式相减，它的设计思想和多项式相加类似，只是实现有点差别。 void SubtractPo

12、lyn(Polyn pa,Polyn pb) /求解并建立多项式a-b，返回其头指针 Polyn h=pb; Polyn p=p-next; Polyn pd; while(p) /将pb的系数取反 p-coef*=-1;p=p-next;pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢复pb的系数p=p-coef*=-1;return pd;2、主程序和其它主要函数 void main() int m,n,a,x;Char flag; Polyn pa=0,pb=0,pc; float ValuePolyn(Polyn head,int x) vo

13、id DestroyPolyn(Polyn p) Polyn q1,q2; q1=p-next; while(q1-next) free(q1) q1=q2;q2=q2-next; 4 调试分析 （1）、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析 问题1：在进行多项式减法时，没有真正的实现该功能，即有些多项式的系数并没有变化。 原因：在进行最后插入处理时，没有改变多项式的系数变为相反数。 解决方法：加了一条语句，即q-coef*=-1. 问题2：在进行多项式显示时，出现了加号和减号同时显示的错误，并且最后一想后面还带有加号。 原因：在输入时没有考虑正负号显示问题。 解决方

14、法：在结点系为负时，不要输出正号，控制最后一个加号，只要加一条语句，即if(p-next=NULL).（2）、算法的时间复杂度和空间复杂度的分析，改进设想该算法的核心算法是多项式的排序算法和加减算法，排序算法的时间复杂度为O(n*n),而实现多项式加法的时间复杂度为O(n),所以本程序的时间复杂度为O(n*n).其中n为多项式的项数。由于多项式的排序算法和加减算法中只使用了一些简单变量和指针变量，它的空间复杂度为O(1). 改进思想：在实现加减法过程中可以把第二多项式所占的存储空间释放掉，这样便于存储空间的回收。还有在显示多项式时可以采取更简洁的方式，类似于指数方式显示形式。5 用户使用说明1

15、本程序的运行环境为Visualc+6.02进入演示程序后，即显示文本方式的用户界面：3按照提示输入需要测试的数据4选择相应的操作，输入对应的操作6 课程设计总结数据结构虽然已经学了一个学期，但有许多知识还不是很清楚，许多数据结构中的程序需要c语言的添加才能执行。通过课程设计对这些知识也有了更深的理解和很好的掌握。许多困惑，有许多已经通过实际操作解决了，并能够深刻认识，但也有很多没有明白。通过课程设计，明白到了原来开发一个小小的实用系统，是需要考虑到很多方面的问题的，许多程序在运行时有很多小错误，在不仔细的情况下是不容易发现及改正的，这些都是要在实践中摸索的，另外就是要把错误总结，有许多错误或者

16、陷阱是平时自己陷进去的，因此很深刻，但也有些错误或者陷阱是自己还没有接触或者犯过的，这就应该看多些别人的总结，使自己不犯这些错误。不让自己掉进这些陷阱。这样长期总结，会对自己有很大的帮助。由于时间原因程序到目前为止，还并不健壮，在对输入小数时，还需要进一步改进。不过通过这次课程设计，我体会到了理论与实际的差别，不仅要学习理论知识，还要勤动手，多实践。我感觉到要真正做出一个程序并不是很容易，但只需用心去做，总会有收获，特别是当我遇到问题去问老师，问同学，想尽办法去解决。对于数据结构有了更深层次的理解,循环队列中对边界条件的处理,满足什么条件为队满,满足什么条件为队空。在以后的学习中我会更加注意各

17、个方面的能力的协调发展，选择一两门技术进行深入研究，成为一个既可以统筹全局，又有一定技术专长的优秀的程序开发人员。7 测试结果1. (2x+5x8-3.1x11)+(7-5x8+11x9)的测试结果： 请输入a的项数：3请输入第一项的系数与指数：2 1请输入第二项的系数和指数：5 8请输入第三项的系数和指数：-3.1 11请输入b的项数：3请输入第一项的系数和指数：7 0请输入第一项的系数和指数：5 8请输入第三项的系数和指数：11 9* 多项式操作程序* A：输出多项式a B：输出多项式b * C：输出a+b D：输出a-b * E：退出程序 *请选择操作：Ca+b=2x+5x8-3.1x1

18、1+7-5x8+11x92. (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)的测试结果： 请输入a的项数：4请输入第一项的系数与指数：6 O请输入第二项的系数和指数：-3 1请输入第三项的系数和指数：4.4 2请输入第四项的系数和指数：请输入b的项数：4请输入第一项的系数和指数：-6 0请输入第一项的系数和指数：-3 1请输入第三项的系数和指数：5.4 2请输入第四项的系数和指数：7.8 15* 多项式操作程序* A：输出多项式a B：输出多项式b * C：输出a+b D：输出a-b * E：退出程序 *请选择操作：D a-b=12-x2-1.2x9-7.8x1

19、53. (x+x2+x3)+0的测试结果： 请输入a的项数：3请输入第一项的系数与指数：1 1请输入第二项的系数和指数：1 2请输入第三项的系数和指数：1 3请输入b的项数：0* 多项式操作程序* A：输出多项式a B：输出多项式b * C：输出a+b D：输出a-b * E：退出程序 *请选择操作：C a+b=x+x2+x34. (x+x3)-(-x-x-3)的测试结果： 请输入a的项数：2请输入第一项的系数与指数：1 1请输入第二项的系数和指数：1 3请输入b的项数：2请输入第一项的系数和指数：-1 1请输入第一项的系数和指数：-1 -3* 多项式操作程序* A：输出多项式a B：输出多项

20、式b * C：输出a+b D：输出a-b * E：退出程序 *请选择操作：D a-b=x-3+2x+x38 参考书目1数据结构，汤文兵，华东理工大学出版社2数据结构习题与解析，李春葆，清华大学出版社3C语言课程设计案例精编，郭翠英，中国水利出版社4BAIDU搜索9 附录带注释的源代码：/头文件#include#include#include/定义多项式的项typedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Polyn h) if

21、(p-coef=0) free(p);/系数为0的话释放结点 else Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnq2-expn)/查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn)/将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef)/系数为0的话释放结点 q1-next=q2-next; free(q2); else/指数为新时将结点插入 p-next=q2; q1-next=p;Polyn CreatePolyn(Polyn head,int m)/建立一个

22、头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;void DestroyPolyn(Polyn p)/销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next;void PrintPolyn(Pol

23、yn P)Polyn q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while(q) if(q-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1

24、); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);int compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else

25、if(!a&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多项式a+b，返回其头指针 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial

26、); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多项式a-b，返回其头指针 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /将pb的系数取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa