算法分析与设计的课程设计(一元多项式的加法、减法、乘法的实现).doc

湖南师范大学电子与信息工程系课程设计报告书一元多项式的加法、减法、乘法的实现2010-09-25Hunan Normal UniversityELECTRONIC & INFORMATION ENGINEERING DEPARTMENT课程设计题目一元多项式的加法、减法、乘法的实现指导教师姓名指导老师职称学生姓名所属班级任务要求1) 首先判定多项式是否稀疏；2) 分别采用顺序和动态存储结构实现；3) 结果M(x)中无重复阶项和无零系数项；4) 要求输出结果的升幂和降幂两种排列情况主要实施步骤1) 9月13日9月14日：分析题目，查阅书籍，理解一元多项式加减乘的思想，对如何实现该题进行一个整体构思；2) 9月15日9月16日：确定实验所用到的数据结构，并给出抽象定义3) 9月17日9月20日：编写各模块的代码，并整合成一个系统4) 9月21日：对程序进行调试与编译5) 9月22日9月24日：美化界面，对部分不合理的地方进行修改6) 9月25日：实验完成，撰写结论结论通过课程设计，基本上完成了老师所要求的功能，但系统还有不足之处，给操作者一个不很直观的操作，希望下一步的完善中，能够改用窗体界面，从而使界面更友好；此次课程设计让我们得到了实践，不再局限于理论的学习之中。湖南师范大学工学院电子与信息工程系课程设计登记表注：此表格内容中的任务要求为指导教师提供的课程设计要求，主要实施步骤是指课程设计的时间安排，结论是指通过课程设计得出的有关结论及课程设计不足之处或进一步开发方向。目 录1引言41.1课程设计目标41.2编程工具（编程环境）介绍51.3实施时间及主要实施步骤52需求分析53系统总体设计64数据结构设计75详细设计与实现95.1功能模块1输入一元多项式详细设计105.1.1详细设计105.1.2界面设计及测试结果105.2功能模块2 创建一元多项式 详细设计105.2.1详细设计105.2.2界面设计及测试结果115.3功能模块3主菜单详细设计115.3.1详细设计115.3.2界面设计及测试结果125.4功能模块4 顺序存储的一元多项式运算 详细设计125.4.1详细设计125.4.2算法流程125.4.3界面设计及测试结果135.5功能模块5顺序存储的一元多项式运算 详细设计135.5.1详细设计135.5.2算法流程135.5.3界面设计及测试结果146 算法分析(5)7 用户手册 .(58 结论 )9 参考文献.10 附录1引言1.1 课程设计目标设计一个一元多项式运算的系统，主要包括：加减乘法的运算。 本文是关于一个一元稀疏多项式计算器的问题。内容包括输入并建立多项式,多项式相加，多项式求导，多项式求值以及输出多项式。本文使用链式存储结构存储一元稀疏多项式，可以方便的计算简单的一元稀疏多项式的基本运算。本课程设计运用所学的一些C+知识，构成整个计算器的形成框架。在程序中定义了各种类型的运算的模块，通过主程序的调用来完成他们之间的配合，进而完善了计算器。1.2 编程工具（编程环境）介绍编程工具：Microsoft Visual C+编程环境：Microsoft Windows xp1.3 实施时间及主要实施步骤l 实施时间： 9月13日至9月25日l 基本步骤大致为：Ø 前期分析Ø 中期编码Ø 后期调试2 需求分析l 本问题描述本实验要求利用带头结点的有序链表实现任意两个一元实系数的加减乘法运算。基本功能要求1首先，根据键盘输入的一元实系数多项式的系数与指数序列，对多项式进行初始化，并按未知数x的升幂形式排序。2对于从键盘输入的任意两个一元多项式，正确计算它们的和，差，积多项式，并输出结果。l 测试数据见Test.txt3 系统总体设计进入界面，系统提示用户输入多项式的指数和系数并选择存储方式。然后出现操作界面，由用户选择相关操作以及按照升幂还是降幂输出。具体实现见流程图： 本程序包括5个模块：1、 输入一元多项式该模块主要是用户根据提示输入一元多项式的指数和系数2、 根据输入创建一元多项式并存储并且判断是否稀疏该模块主要是将输入的一元多项式按顺序存储方式存储，并判断是否稀疏，如果稀疏，则转换为链式方式存储3、 主菜单该模块主要是显示菜单信息，并且由用户显示要进行的步骤4、 顺序存储的一元多项式的加减乘法并输出结果 该模块主要是实现多项式的运算5、 链式存储的一元多项式的加减乘法并输出结果 该模块主要是实现多项式的运算4 数据结构设计本程序主要应用了链表，结构体和类模板。用结构体来定义多项式的结点（即每一项），它包含三个域，分别存放该项的系数、指数以及指向下一项结点的指针；用链表来存储多项式，为了节省空间，只存储多项式中系数非0 的项，用多项式链表类来实现设定的程序的基本功能。为实现上述功能定义一元多项式的抽象数据类型如下：ADT  Polynomial数据对象：D=ai |aiTermSet,  i=1,2,m,  m10，TermSet中的元素包含一个实系数和一个表示指数的整数数据关系：R1=<ai-1,ai> |ai-1,aiD, 且ai-1中的指数值< ai中的指数值，i=2,n ADT  Polynomial定义结构体：typedef struct LNode float ceof; /系数 int expn,xs; /指数 项数 struct LNode *next;LNode,*LinkList;typedef struct float aN;/下标表示指数，值表示系数/ int len,Nz;/记录多项式的长度，非零项/polynomial;函数功能描述：1、 Menu()操作菜单2、 cmp()对系数进行比较3、 AddPolyn()顺序存储的一元多项式相加4、 CreatPolyn()创建链式存储的一元多项式5、 ADD()链式存储的一元多项式相加6、 AscendPrint( )升幂输出 7、 Getpoly ()创建顺序存储的一元多项式8、 LAscend()链式存储的一元多项式升幂排序9、 PrintPolyn()打印链式存储的一元多项式5 详细设计与实现一元多项式计算器各功能模块的详细介绍。5.1 功能模块1详细设计5.1.1 详细设计 1、模块名称：输入一元多项式 2、功能说明：用户根据提示输入一元多项式的系数和指数 3、输入参数：输入指数和系数，系数为负数就结束5.1.2 界面设计及测试结果5.2 功能模块2详细设计5.2.1 详细设计模块名称：根据输入创建一元多项式并存储并且判断是否稀疏 功能说明：主要是创建一元多项式5.2.2 界面设计及测试结果5.3 功能模块3详细设计5.3.1 详细设计 模块名称：主菜单功能说明：该模块主要是显示菜单信息，并且由用户显示要进行的步骤5.3.2 界面设计及测试结果5.4 功能模块4详细设计5.4.1 详细设计模块名称：顺序存储的一元多项式的加减乘法并输出结果 功能说明：该模块主要是实现多项式的运算5.4.2 算法流程 void ADD(polynomial A,polynomial B,polynomial &M) int la=A.len,lb=B.len,i; M.len=la>lb?la:lb; for(i=0;i<=la&&i<=lb;i+) M.ai=A.ai+B.ai; /此处若为稀疏式，则会浪费大量时间 while(i<=la) M.ai=A.ai;i+; while(i<=lb) M.ai=B.ai;i+; print(M);/=/M(x)=A(m)-B(n)/void SUB(polynomial A,polynomial B,polynomial &M) int la=A.len,lb=B.len,i; M.len=la>lb?la:lb; for(i=0;i<=la&&i<=lb;i+) M.ai=A.ai-B.ai; while(i<=la) M.ai=A.ai;i+; while(i<=lb) M.ai=0-B.ai;i+; /B的相反数 print(M); /=/M(x)=A(m)*B(n)/void MUL(polynomial A,polynomial B,polynomial &M) int i,j; for(i=0;i<=A.len+B.len+1;i+) M.ai=0; /为什么要多1 for(i=0;i<=A.len;i+) for(j=0;j<=B.len;j+) M.ai+j+=A.ai*B.aj; M.len=A.len+B.len; print(M); 5.4.3 界面设计及测试结果5.5 功能模块5详细设计5.5.1 详细设计模块名称：链式存储的一元多项式的加减乘法并输出结果 功能说明：该模块主要是实现多项式的运算5.5.2 算法流程Lpolynomial AddPolyn(Lpolynomial Pa,Lpolynomial Pb) float sum; Lpolynomial ha,hb,hc,qa,qb,qc,pc; if(Pa->xs>Pb->xs) ha=Pb; hb=Pa; else ha=Pa; hb=Pb; hc=pc=(Lpolynomial)malloc(sizeof(LNode); qa=ha->next; qb=hb->next; while(qa->next!=NULL)&&(qb->next!=NULL) qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; switch(cmp(qa->expn,qb->expn) case -1: qc->ceof=qa->ceof; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; break; case 0: sum=qa->ceof+qb->ceof; if(sum!=0.0) qc->ceof=sum; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; qb=qb->next; break; else free(qc); qa=qa->next; qb=qb->next; break; case 1: qc->ceof=qb->ceof; qc->expn=qb->expn; pc->next=qc; pc=qc; qb=qb->next; break; if(qa->next!=NULL) while(qa!=NULL) qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; qc->ceof=qa->ceof; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; else while(qb!=NULL) qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; qc->ceof=qb->ceof; qc->expn=qb->expn; pc->next=qc; pc=qc; qb=qb->next; qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; prints(hc); pc->next=qc; qc->ceof=0; Pa=ha; Pb=hb;/=/-相减，构成和多项式 hc-/Lpolynomial SubtractPolyn(Lpolynomial Pa,Lpolynomial Pb) float result; Lpolynomial ha,hb,hc,qa,qb,qc,pc; if(Pa->xs>Pb->xs)ha=Pb; hb=Pa; else ha=Pa; hb=Pb; qa=ha->next; qb=hb->next;hc=pc=(Lpolynomial)malloc(sizeof(LNode); while(qa->next!=NULL)&&(qb->next!=NULL) qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; switch(cmp(qa->expn,qb->expn) case -1: qc->ceof=qa->ceof; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; break; case 0: result=qa->ceof-qb->ceof; if(result!=0.0) qc->ceof=result; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; qb=qb->next; break; else free(qc); qa=qa->next; qb=qb->next; break; case 1: qc->ceof=0-qb->ceof; qc->expn=qb->expn; pc->next=qc; pc=qc; qb=qb->next; break; if(qa->next!=NULL) while(qa!=NULL) qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; qc->ceof=qa->ceof; qc->expn=qa->expn; pc->next=qc; pc=qc; qa=qa->next; else while(qb!=NULL) qc=(Lpolynomial)malloc(sizeof(LNode); qc->next=NULL; qc->ceof=0-qb->ceof; qc->expn=qb->expn; cout<<qc->ceof; pc->next=qc; pc=qc; qb=qb->next; if(Pa->xs>Pb->xs) for(qc=hc;qc->next!=NULL;qc=qc->next) qc->ceof=0-qc->ceof; qc->ceof=0-qc->ceof; cout<<qc->ceof; prints(hc); Pa=ha; Pb=hb;Lpolynomial MultiplyPolyn(Lpolynomial Pa,Lpolynomial Pb)/相乘，Pa构成积多项式hc Lpolynomial s,hc,q,p,r,ha,hb; ha=Pa; hb=Pb; hc=(Lpolynomial)malloc(sizeof(LNode); r=hc; for(p=Pa->next;p!=NULL;p=p->next) for(q=Pb->next;q!=NULL;q=q->next) s=(Lpolynomial)malloc(sizeof(LNode); s->ceof=p->ceof*q->ceof; s->expn=p->expn+q->expn; r->next=s; r=s; r->next=NULL; for(int i=20; i!=0;i-) for(q=hc;q->next!=NULL;q=q->next)/合并同类项 for(p=q->next;p!=NULL&&p->next!=NULL;p=p->next) if(q->expn=p->next->expn) q->ceof=q->ceof+p->next->ceof; r=p->next; p->next=p->next->next; free(r); LAscend(hc); prints(hc); Pa=ha; Pb=hb;计算多项式加减，其算法思想是相同的。以多项式加法为例，先对两多项式排序，再将两多项式的每一项逐项相加，在相加之前，先比较两项的指数是否相等，若相等则将系数相加，再判断系数是否为零，若为零则删除，否则存储在和多项式中。若两项指数不相等，当多项式pa指数大于多项式pb指数时，则将pa结点副本插入到和多项式PolyC尾部；当pa指数小于pb指数时，则将pb结点副本插入到和多项式PolyC尾部，最后插入剩余结点。（8）计算多项式乘法时，先判断两多项式是否为空，若为空，则返回乘多项式，否则要先对两多项式进行合并排序，先将两多项式的第一项相乘，即系数相乘，指数相加，其值作为乘多项式的第一结点，其后使用双重循环将一多项式的每一项与另一多项式的每一项分别相乘，结果存到乘多项式中。5.5.3 界面设计及测试结果6 算法分析主要的算法是对多项式的计算，分别有1、A+B：用了一个循环，循环n次，即T=O(n)2、A-B：A-B即为A+（-B），即T=O(n)3、A*B：用了两个循环来完成计算，第二个循环嵌套在第一个循环里面，即时间复杂度T=O(n2)7 结论 课程设计终于做完了，虽然有些疲劳和困倦，但带给我很多的收获。数绝结构已经学了一个学期，大概三个多月了，有许多知识都存在似懂非懂的现象，这种现象通过实际的上机操作，实际应用，已经减少了许多。对这些知识也有了更深的理解和很好的掌握。许多困惑，有许多已经通过实际操作解决了，并能够深刻认识，但也有很多没有明白。通过课程设计，明白到了原来开发一个小小的实用系统，是需要考虑到很多方面的问题的，这些都是要在实践中摸索的，这与平时做练习是不同的，但也因为平时有许多的练习基础，会使你做起程序来，更加得心应手。另外就是要把错误总结，有许多错误或者陷阱是平时自己陷进去的，因此很深刻，但也有些错误或者陷阱是自己还没有接触或者犯过的，这就应该看多些别人的总结，使自己不犯这些错误。不让自己掉进这些陷阱。这样长期总结，会对自己有很大的帮助。 主要内容是对一元多项式存储结构的选择，输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；虽然一元多项式可以用顺序和链式两种存储结构表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费了巨大的存储空间，所以应该选择用链式存储结构来存储一元多项式。单链表的结构体可以用来存储多项式的系数，指数，这样便于实现任意多项式的运算。8参考文献1严蔚敏，吴伟民. 数据结构（C语言版）M，北京：清华大学出版社，1997.42007.42 C+程序设计教程(第二版) 钱能 著 清华大学出版社3百度搜索