数据结构一元稀疏多项式

NUMPAGES22 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 完成如下功能：（1）输入并建立多项式——creatpolyn()（2）输出多项式，输出形式为整数序列，序列按指数升序排列——printpolyn()（3）多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn()（4）多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn()用带表头结点的单链表存储多项式。课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 学生姓名：学号：专业班级：课程名称：数据结构学年学期：指导教师：目录1．需求分析说明……………………………………………………………12．概要设计说明……………………………………………………………33．详细设计说明……………………………………………………………54．调试分析…………………………………………………………………105．用户使用说明……………………………………………………………116．课程设计 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ……………………………………………………………127．测试结果…………………………………………………………………138．参考 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 目…………………………………………………………………169.附录………………………………………………………………………17数据结构课程设计PAGE１３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->coef>0&&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语言的添加才能执行。通过课程设计对这些知识也有了更深的理解和很好的掌握。许多困惑，有许多已经通过实际操作解决了，并能够深刻认识，但也有很多没有明白。通过课程设计，明白到了原来开发一个小小的实用系统，是需要考虑到很多方面的问题的，许多程序在运行时有很多小错误，在不仔细的情况下是不容易发现及改正的，这些都是要在实践中摸索的，另外就是要把错误总结，有许多错误或者陷阱是平时自己陷进去的，因此很深刻，但也有些错误或者陷阱是自己还没有接触或者犯过的，这就应该看多些别人的总结，使自己不犯这些错误。不让自己掉进这些陷阱。这样长期总结，会对自己有很大的帮助。由于时间原因程序到目前为止，还并不健壮，在对输入小数时，还需要进一步改进。不过通过这次课程设计，我体会到了理论与实际的差别，不仅要学习理论知识，还要勤动手，多实践。我感觉到要真正做出一个程序并不是很容易，但只需用心去做，总会有收获，特别是当我遇到问题去问老师，问同学，想尽办法去解决。对于数据结构有了更深层次的理解,循环队列中对边界条件的处理,满足什么条件为队满,满足什么条件为队空。在以后的学习中我会更加注意各个方面的能力的协调发展，选择一两门技术进行深入研究，成为一个既可以统筹全局，又有一定技术专长的优秀的程序开发人员。7测试结果1.(2x+5x8-3.1x11)+(7-5x8+11x9)的测试结果：请输入a的项数：3请输入第一项的系数与指数：21请输入第二项的系数和指数：58请输入第三项的系数和指数：-3.111请输入b的项数：3请输入第一项的系数和指数：70请输入第一项的系数和指数：58请输入第三项的系数和指数：119******************************************************************多项式操作程序*A：输出多项式aB：输出多项式b**C：输出a+bD：输出a-b**E：退出程序*********************************************************************请选择操作：Ca+b=2x+5x8-3.1x11+7-5x8+11x92.(6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)的测试结果：请输入a的项数：4请输入第一项的系数与指数：6O请输入第二项的系数和指数：-31请输入第三项的系数和指数：4.42请输入第四项的系数和指数：请输入b的项数：4请输入第一项的系数和指数：-60请输入第一项的系数和指数：-31请输入第三项的系数和指数：5.42请输入第四项的系数和指数：7.815******************************************************************多项式操作程序*A：输出多项式aB：输出多项式b**C：输出a+bD：输出a-b**E：退出程序*********************************************************************请选择操作：Da-b=12-x^2-1.2x^9-7.8x^153.(x+x2+x3)+0的测试结果：请输入a的项数：3请输入第一项的系数与指数：11请输入第二项的系数和指数：12请输入第三项的系数和指数：13请输入b的项数：0******************************************************************多项式操作程序*A：输出多项式aB：输出多项式b**C：输出a+bD：输出a-b**E：退出程序*********************************************************************请选择操作：Ca+b=x+x^2+x^34.(x+x3)-(-x-x-3)的测试结果：请输入a的项数：2请输入第一项的系数与指数：11请输入第二项的系数和指数：13请输入b的项数：2请输入第一项的系数和指数：-11请输入第一项的系数和指数：-1-3******************************************************************多项式操作程序*A：输出多项式aB：输出多项式b**C：输出a+bD：输出a-b**E：退出程序*********************************************************************请选择操作：Da-b=x^-3+2x+x^38参考书目[1]数据结构，汤文兵，华东理工大学出版社[2]数据结构——习题与解析，李春葆，清华大学出版社[3]C语言课程设计案例精编，郭翠英，中国水利出版社[4]BAIDU搜索9附录带注释的源代码：//头文件#include#include#include//定义多项式的项typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系数为0的话释放结点else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->expn>q2->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;}}}PolynCreatePolyn(Polynhead,intm){//建立一个头指针为head、项数为m的一元多项式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;icoef,&p->expn);Insert(p,head);//调用Insert函数插入结点}returnhead;}voidDestroyPolyn(Polynp){//销毁多项式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;q2=q2->next;}}voidPrintPolyn(PolynP){Polynq=P->next;intflag=1;//项数计数器if(!q){//若多项式为空，输出0putchar('0');printf("\n");return;}while(q){if(q->coef>0&&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");}intcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expnexpn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多项式已空，但b多项式非空elsereturn1;//b多项式已空，但a多项式非空}PolynAddPolyn(Polynpa,Polynpb){//求解并建立多项式a+b，返回其头指针Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立头结点hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case0:{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;}elsefree(qc);//当相加系数为0时，释放该结点}returnheadc;}PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式a-b，返回其头指针Polynh=pb;Polynp=pb->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->coef*=-1;returnpd;}voidmain(){intm,n,a;charflag;Polynpa=0,pb=0,pc;printf("欢迎使用多项式操作程序\n\n");printf("请输入a的项数:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多项式aprintf("请输入b的项数:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多项式b//输出菜单printf("*******************************************************\n");printf("*多项式操作程序*\n");printf("**\n");printf("*A:输出多项式B:输出多项式b*\n");printf("**\n");printf("*C:输出a+bD:输出a-b*\n");printf("**\n");printf("*E:退出程序*\n");printf("**\n");printf("*******************************************************\n");while(a){printf("\n请选择操作：");scanf("%c",&flag);switch(flag){case'A':case'a':{printf("\n多项式a=");PrintPolyn(pa);break;}case'B':case'b':{printf("\n多项式b=");PrintPolyn(pb);break;}case'C':case'c':{pc=AddPolyn(pa,pb);printf("\na+b=");PrintPolyn(pc);break;}case'D':case'd':{pc=SubtractPolyn(pa,pb);printf("\na-b=");PrintPolyn(pc);break;}case'E':case'e':{printf("\n感谢使用此程序！\n");DestroyPolyn(pa);DestroyPolyn(pb);a=0;break;}default:printf("\n您的选择错误，请重新选择!\n");}}}