两个高次多项式加法和乘法运算

西安文理学院软件学院课程设计报告 设计名称： 数据结构课程设计 设计题目： 两个高次多项式加法和乘法运算 专业班级： 软件工程2012级2班 课题工作时间： 2014.6.16 至 2014.6.27 软件学院课程设计任务书学生姓名学号专业班级软件工程2012级2班设计题目设计程序已实现任意两个高次多项式的加法和乘法运算内容概要： 在Microsoft Visual C+ 6.0环境下运用C语言编写。运用了循环结构、指针、链表的插入和删除运算等方法编写程序。多次调试和纠错之后，用具体多项式试验，运行程序，得出结果。 文献资料：1尹宝林.C育出版社，20程序设计思想与方法M.机械工业出版社,2011.2黄明.C语言课程设计M.电子工业出版社,2009.3谭浩强.C程序设计M.清华大学出版社,2012.4柴欣，C/C+程序设计M. 河北大学出版社，2009.5余苏宁,王明福，C+程序设计M. 北京：高等教育出版社,2010设计要求：程序实现的功能：1.输入并建立多项式；2.输出多项式；3.两个多项式相加，输出和多项式；4.两个多项式相乘，输出积多项式。工作期限：设计工作自2014年6月16日至2014年6月27日止。指导教师： 院长： 日 期：2014年6月16日软件学院课程设计进度安排表学生姓名： 学号： 1402120222 专业： 软件工程 班级： 2012级2班 起止日期内 容备注6月16日 6月 17日下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名： 2014年6月16日成绩评定表学生姓名： 学号： 1402120222 专业： 软件工程 班级： 2012级2班 类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分指导教师： （签字）日期：2014 年6月 27 日摘 要摘要：在这次的课程设计中我选择的题目是一元多项式的加法和乘法的实现。运用C语言编写，在Microsoft Visual C+ 6.0环境下运行。一元多项式计算是用C语言设计一个一元多项式简单计算器。它能够实现按指数升序排列建立并输出多项式，并且能够完成两个多项式的相加、相减与相乘的运算和将其结果输入的功能。通过设计一元多项式，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能提高，综合运用所学的理论知识和方法独立分析和解决问题的能力；加深对常用数据结构的理解，强化逻辑思维能力和动手能力，巩固良好的编程习惯，掌握工程软件设计的基本方法，为后续课程的学习打下坚实基础。关键词：C语言；指针；链表；循环；一元多项式I目录摘 要II第一章 课题背景11.1 设计的课题11.2 课题的背景及意义11.3课题的目的和要求1第二章 设计简介及设计方案22.1 设计简介22.2设计方案2第三章 详细设计43.1 存储结构43.2设计思路分析43.3详细设计5第四章 设计结果及分析94.1 测试数据94.2运行过程与结果9总结13参考文献14附录 程序源代码15西安文理学院软件学院 课程设计报告第一章 课题背景1.1 设计的课题设计程序以实现任意两个高次多项式相加和相乘运算。1.2 课题的背景及意义数据结构是一门实践性的计算机课程，想要学好这门课程，不仅需要掌握理论知识，而且要加强上机实践，通过这次课程设计，要求掌握较大程序的设计方法，相应数据结构的选择应用、算法的设计及其实现和性能分析等方面中加强对课程基本内容的理解。同时在设计方法以及上机操作等技能和科学作风方面受到比较系统和严格的锻炼，每次的课程设计都是一次锻炼自己能力的好机会。1.3课题的目的和要求课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。第2章 设计简介及设计方案2.1 设计简介1. 运用动态链表结构实现一元多项式的加法、减法、乘法的运算。可以分为几个模块：输入模块、输出模块（升幂）、数据处理模块（多项式的加减乘）、主程序模块。2. 在程序执行过程中加入汉字提示符，让使用者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。3. 程序执行时的命令：创建两个一元多项式；输入第一个一元多项式的项数；依次输入一元多项式的系数和指数；以相同方式输入第二个一元多项式；数据处理；输出结果。2.2设计方案1.数据结构的设计为了节省存储空间，只存储多项式中系数非零的项，本程序使用链式存储结构。2.算法的设计本设计从总体上划分为3个模块。主函数模块。程序的入口，主要实现各个函数的调用。头文件模块。定义类和结构体。函数模块。数据处理和实现每个功能。3.基本操作：CreatPolyn（&Pm）操作结果：输入m项的系数和指数，建立一元多项式P。DestroyPolyn（&P）初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。PrintPolyn（P）初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。ValuePolyn(Polyn head,int x) 初始条件：一元多项式P已存在。操作结果：输入x值，计算并返回多项式的值AddPolyn（&Pa，&Pb）初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式PbSubtractPolyn(&Pa,&Pb) 初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb) 初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa=PaPb，并销毁一元多项式Pb。ADT Polynomia 第三章 详细设计3.1 存储结构建立一元多项式的在计算机内可以用链表来实现，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。存储结构定义：公用头文件DS0.h: #include #include #include 带头结点单链表存储结构：typedef struct Polynomialfloat coef; int expn; struct Polynomial *next; *Polyn,Polynomial; 3.2设计思路分析要解决多项式相加，相减，相乘，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为：系数coef指数expn指针域next运用尾插法建立两个单链表，以单链表Polyn p和Polyn h分别表示一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将Polyn p中的结点插入到单链表Polyn h中），因此“和多项式”的结点无须另生成。为了实现处理，设p、q2分别指向单链表polya和polyb的当前项，比较p、q2结点的指数。由此得到下列运算规则：（1）若p-expnexpn，则结点q2所指的结点应是“和多项式”中的一项，令指针q2后移。（2）若p-expn=q2-expn，则将两个结点中的系数相加，当和不为0时修改结点q2的系数。（3）若p-expnq2-expn，则结点p所指的结点应是“和多项式”中的一项，将结点p插入在结点q2之前，且令指针p在原来的链表上后移。建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的运算并输出结果。简要运行流程图如图3-1。54321 菜单choose？Printpoly（）建立多项式Addpoly（） 相加SubtractPolyn 相减*退出*MultiplyPolyn 相乘图3-1 简要运行流程图结 束开 始3.3详细设计主函数int main()int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf;void PrintPolyn(Polyn P) /输出多项式a和bPolyn AddPolyn(Polyn pa,Polyn pb) /求解并建立多项式a+b，返回其头指针。Polyn SubtractPolyn(Polyn pa,Polyn pb) /求解并建立多项式a-b，返回其头指针。Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多项式a*b，返回其头指针。基本算法多项式的输入（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x 指数 y输出已输入的多项式 合并同类项结束否是是否输入正确图3-2 输入（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图3-2所示。（5） 主要代码段：建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点:Polyn CreatePolyn(Polyn head,int 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;多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。（5）主要代码段：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);switch(compare(qa,qb).略去四个case语句./switchif(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;else free(qc);/当相加系数为0时，释放该结点/whilereturn headc;/AddPolyn多项式的乘法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。（5）主要代码段：Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多项式a*b，返回其头指针 Polyn hf,pf;Polyn qa=pa-next;Polyn qb=pb-next;hf=(Polyn)malloc(sizeof(struct Polynomial); /建立头结点hf-next=NULL;for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial);pf-coef=qa-coef*qb-coef;pf-expn=qa-expn+qb-expn;Insert(pf,hf); /调用Insert函数以合并指数相同的项return hf;/MultiplyPolyn第四章 设计结果及分析4.1 测试数据测试如下多项式，以下多项式中，项数有两项，三项，四项，项数的系数和指数有正有负，测试结果正确无误。1. (x3+2x4+5x7)和(6x8+9x11+10x12)；2. (1.1x2+5x3+8x6+5.7x9)+(4x6+2.1x4+2x10)=(2x10+5.7x9+12x6+2.1x4+5x3+1.1x2)；3. (8x10+5x8+2x2+4x8)*(2x10+6x7+8x2+5x9+3.8x4)=(16x20+40x19+18x18+93x17+54x15+30.4x14+102.2x12+10x11+72x10+12x9+7.6x6+16x4)4.2运行过程与结果开始界面，提示开始输入数据建立多项式，如图4-1所示。 图4-1 开始界面输入数据，输入多项式的系数和指数，如图4-2所示。 图4-2 输入数据 按回车键，出现菜单界面，用户可以选择其中任意一个功能执行，如图4-3所示 图4-3 菜单界面选择功能1，输出多项式，操作及结果如图所示如图4-4所示。 图4-4 输出多项式选择功能2，两个多项式相加，输出和多项式。如图4-5所示。 图4-5 多项式相加选择功能3，两个多项式相乘，输出积多项式，如图4-6所示。 图4-6 多项式相乘 选择功能4，按任意键退出程序，如图4-7所示。 图4-7 退出程序 总结这次课程设计使本学期所学的数据结构知识得到了巩固和应用，并且对C+也有了更进一步的了解。虽然在设计过程中遇到了一些困难，但感觉收获还是挺多的，自己扩充了很多知识点 。通过这周的课程设计，我意识到好的学习方法的重要性，在学习中要学会主动，学会自学，不要什么东西都指望别人，要靠自己去细心观察，多问自己一个为什么，多动手查查、看看，不会的问题，抬头是google，这样自己学到手的东西才会更多！ 参考文献1尹宝林.C育出版社，20程序设计思想与方法M.机械工业出版社,2011.2黄明.C语言课程设计M.电子工业出版社,2009.3谭浩强.C程序设计M.清华大学出版社,2012.4柴欣，C/C+程序设计M. 河北大学出版社，2009.5余苏宁,王明福，C+程序设计M. 北京：高等教育出版社,2010 19 附录 程序源代码#include#includetypedef struct Polynomial float coef;int expn;struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点else Polyn q1,q2;q1=h;q2=h-next;while(q2&p-expnexpn) /查找插入位置 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;/InsertPolyn CreatePolyn(Polyn head,int m) /建立一个头指针为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;/CreatePolynvoid 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(Polyn 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); 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+;/whileprintf(n);/PrintPolynint 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 if(!a&b) return -1; /a多项式已空，但b多项式非空else return 1; /b多项式已空，但a多项式非空/comparePolyn 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);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; /switchif(qc-coef!=0)qc-next=hc-next;hc-next=qc;hc=qc;else free(qc);/当相加系数为0时，释放该结点/whilereturn headc;/AddPolynPolyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多项式a*b，返回其头指针 Polyn hf,pf;Polyn qa=pa-next;Polyn qb=pb-next;hf=(Polyn)malloc(sizeof(struct Polynomial); /建立头结点hf-next=NULL;for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial);pf-coef=qa-coef*qb-coef;pf-expn=qa-expn+qb-expn;Insert(pf,hf); /调用Insert函数以合并指数相同的项return hf;/MultiplyPolynint main()int m,n,flag=0;float x;Polyn pa=0,pb=0,pc,pd,pe,pf; /定义各式的头指针，pa与pb在使用前赋初值NULLprintf(请输入a的项数:);scanf(%d,&m);pa=CreatePolyn(pa,m); /建立多项式aprintf(请输入b的项数:);scanf(%d,&n);pb=CreatePolyn(pb,n); /建立多项式b/输出菜单printf(*操作提示*n);printf(t 1.输出多项式a和bn);printf(t 2.建立多项式a+bn);printf(t 3.建立多项式a*bn);printf(t 4.退出n*n);for(;flag=0)printf(执行操作);scanf(%d,&flag);if(flag=1)printf(多项式a：);PrintPolyn(pa);printf(多项式b：);PrintPolyn(pb);continue;if(flag=2)pc=AddPolyn(pa,pb);printf(多项式a+b：);PrintPolyn(pc);DestroyPolyn(pc);continue;if(flag=3)pf=MultiplyPolyn(pa,pb);printf(多项式a*b：);PrintPolyn(pf);DestroyPolyn(pf);continue;if(flag=4) break;if(flag8) printf(Error!n);continue;/forDestroyPolyn(pa);DestroyPolyn(pb);return 0;