数据结构一元稀疏多项式

24要求完成如下功能：（1）输入并建立多项式——creatpolyn()（2）输出多项式，输出形式为整数序列，序列按指数升序排列——printpolyn()（3）多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn()（4）多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn()用带表头结点的单链表存储多项式。课程设计学生姓名：学号：专业班级：课程名称：数据结构学年学期：指导教师：24目录1．需求分析说明……………………………………………………………12．概要设计说明……………………………………………………………33．详细设计说明……………………………………………………………54．调试分析…………………………………………………………………105．用户使用说明……………………………………………………………116．课程设计总结……………………………………………………………127．测试结果…………………………………………………………………138．参考书目…………………………………………………………………169.附录………………………………………………………………………17数据结构课程设计１1需求分析说明1.程序所能达到的功能是（1）输入并建立多项式——creatpolyn()（2）输出多项式，输出形式为整数序列，序列按指数升序排列——printpolyn()（3）多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn()（4）多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn()用带表头结点的单链表存储多项式。2．输入的形式和输入值的范围：本系统要输入的数据主要是有多项式中每项的系数和指数，可以把它们定义为整形数据，既可以为整数也可以为非负整数，即有符号的整形数据，由于整形数据在内存里占用两个字节，所以它的取值范围为-32768—32767。其次还有就是选择功能时，要输入的功能号，它们是字符型数据，取值范围是ASS||表中的字符。例如输入的格式如下：请输入a的项数：3请输入第一项的系数与指数：2，1请输入第二项的系数和指数：5，8请输入第三项的系数和指数：-3.1,11请输入b的项数：3请输入第一项的系数和指数：7，0请输入第一项的系数和指数：5，8请输入第三项的系数和指数：11,9******************************************************************多项式操作程序*A：输出多项式aB：输出多项式b**C：输出a+bD：输出a-b**F：退出程序*********************************************************************请选择操作：Ca+b=2x+5x8-3.1x11+7-5x8+11x9数据结构课程设计２请选择操作：Da-b=2x+5x8-3.1x11-7+5x8-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.抽象数据类型的定义多项式的结点类型定义typedefstructPolynomial{//多项式结点类型floatcoef;//多项式的系数intexpn;//多项式的指数structPolynomial*next;//指向下一个结点}*Polyn,Polynomial;建立表示一元多项式的有序表PolynCreatePolyn(Polynhead,intm)；销毁一元多项式voidDestroyPolyn(Polynp)；返回一元多项式的项数voidPrintPolyn(PolynP)；完成多项式加法运算PolynAddPolyn(Polynpa,Polynpb)；完成多项式相减运算PolynSubtractPolyn(Polynpa,Polynpb)；输出多项式建立链表多项式相加数据结构课程设计４2.主程序的流程（1）输出提示信息（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).DestroyPolyn(pa).DestroyPolyn(pb)数据结构课程设计５3详细设计说明1.设计中定义的所有数据类型伪码算法(1)多项式建立的算法该算法是用来创建多项式链表。首先要创建一个结点，并用一个指针指向它，并给它进行初始化voidCreatPolyn(polynomial&p,intm){//输入m项的系数和指数，建立一元多项式的有序链表pInitList(p);h=GetHead(p);e.coef=0.0;e.expn=-1;SetCurElem(h,e);//设置头结点的数据元素for(i=1;i=m;++i){//依次输入m个非零项scanf(e.coef,e.expn);if(!LocateElem(p,e,q(*cmp))){//当链表中不存在该指数项if(MakeNode(s,e))InsFirst(q,s);//生成结点并插入链表}}}(2)显示多项式的算法该算法用来显示多项式。访问第一个结点，并判断是否为空表，如果是空表就不进行任何操作，否则就输出该结点的系数。voidPrintPolyn(PolynP){Polynq=P-next;intflag=1;//项数计数器if(!q){putchar('0');//若多项式为空，输出0printf(\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');elseif(q-expn)printf(X^%d,q-expn);}else{if(q-coef==1){if(!q-expn)putchar('1');elseif(q-expn==1)putchar('X');elseprintf(X^%d,q-expn);}if(q-coef==-1){if(!q-expn)printf(-1);elseif(q-expn==1)printf(-X);elseprintf(-X^%d,q-expn);}}q=q-next;flag++;}数据结构课程设计７printf(\n);}(3)多项式加法的算法该模块是实现两个多项式相加的算法。要求两个多项式的指数从小到大的排列顺序。voidAddPolyn(polynomial&pa,polynomial&pb){//多项式加法ha=GetHead(pa);hb=GetHead(pb);//ha和hb分别指向pa和pb的头结点qa=NexPos(pa,ha);qb=NexPos(pb,hb);//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);case0://两者的指数相等sum=a.coef+b.coef;if(sum!=0.0){//修改多项式pa中当前结点的系数值SetCurElem(qa,sum);ha=qa;}else{//删除多项式pa中当前结点DelFirst(ha,qa);FreeNode(qa);}DelFirst(hb,qb);FreeNode(qb);qb=NexPos(pb,qb);数据结构课程设计８qa=NexPos(pa,ha);break;case1://多项式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)多项式减法的算法该模块是实现两个多项式相减，它的设计思想和多项式相加类似，只是实现有点差别。voidSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b，返回其头指针Polynh=pb;Polynp=p-next;Polynpd;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;returnpd;}2、主程序和其它主要函数voidmain(){数据结构课程设计９intm,n,a,x;Charflag;Polynpa=0,pb=0,pc;}floatValuePolyn(Polynhead,intx)voidDestroyPolyn(Polynp){Polynq1,q2;q1=p-next;while(q1-next){free(q1)q1=q2;q2=q2-next;}}数据结构课程设计１０4调试分析（1）、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析问题1：在进行多项式减法时，没有真正的实现该功能，即有些多项式的系数并没有变化。原因：在进行最后插入处理时，没有改变多项式的系数变为相反数。解决方法：加了一条语句，即q-coef*=-1.问题2：在进行多项式显示时，出现了加号和减号同时显示的错误，并且最后一想后面还带有加号。原因：在输入时没有考虑正负号显示问题。解决方法：在结点系为负时，不要输出正号，控制最后一个加号，只要加一条语句，即if(p-next=NULL).（2）、算法的时间复杂度和空间复杂度的分析，改进设想该算法的核心算法是多项式的排序算法和加减算法，排序算法的时间复杂度为O(n*n),而实现多项式加法的时间复杂度为O(n),所以本程序的时间复杂度为O(n*n).其中n为多项式的项数。由于多项式的排序算法和加减算法中只使用了一些简单变量和指针变量，它的空间复杂度为O(1).改进思想：在实现加减法过程中可以把第二多项式所占的存储空间释放掉，这样便于存储空间的回收。还有在显示多项式时可以采取更简洁的方式，类似于指数方式显示形式。数据结构课程设计１１5用户使用说明1．本程序的运行环境为Visualc++6.02．进入演示程序后，即显示文本方式的用户界面：3．按照提示输入需要测试的数据4．选择相应的操作，输入对应的操作数据结构课程设计１２6课程设计总结数据结构虽然已经学了一个学期，但有许多知识还不是很清楚，许多数据结构中的程序需要c语言的添加才能执行。通过课程设计对这些知识也有了更深的理解和很好的掌握。许多困惑，有许多已经通过实际操作解决了，并能够深刻