数据结构课程设计一元多项式的加减法运算

1、.wd.wd.wd.武汉理工大学华夏学院课程设计报告书课程名称：数据构造与算法分析题 目：用C语言实现一元多项式的加减法运算系 名：信息工程系 专业班级： 物联网工程1122班 姓 名： 隋明超学 号： 10213312201指导教师:司晓梅2014年 1 月3日武汉理工大学华夏学院信息工程系课 程 设 计 任 务 书课程名称： 数据构造与算法分析 指导教师： 司晓梅 班级名称： 物联网1121-2 开课系、教研室： 信息系计算机 一、课程设计目的与任务?数据构造?课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的：学习数据构造课程，旨在使学生学会分析研究数据

2、对象的特性，学会数据的组织方法，以便选择适宜的数据的逻辑构造和存储构造以及相应操作，把现实世界中的问题转换为计算机内部的表示和处理，这就是一个良好的程序设计技能训练的过程。提高学生的程序设计能力、掌握 基本知识、 基本技能，提高算法设计质量与程序设计素质的培养就是本门课程的课程设计的目的。任务：根据题目要求，完成算法设计与程序实现，并按规定写出课程设计报告。二、课程设计的内容与 基本要求设计题目：用C语言实现一元多项式的加减法计算问题描述输入并建设两个多项式并输出多项式设计一个程序：对两个多项式进展加、减法运算，建设一个新多项式并输出。实现提示：选择单链表存储多项式 具体要完成的任务是： A.

3、 编制完成上述问题的C语言程序、进展程序调试并能得出正确的运行结果。B. 写出标准的课程设计报告书；三、课程设计步骤及时间进度和场地安排时间：本课程设计安排在第18周 地点：现代教育中心具体时间安排如下：第一天：布置题目，确定任务、查找相关资料第二天第四天：功能分析，编写程序，调试程序、运行系统；第五天上午：撰写设计报告；第五天下午：程序验收、辩论。四、课程设计考核及评分标准课程设计考核将综合考虑学生的系统设计方案、运行结果、课程设计报告书的质量、态度、考勤、辩论情况等各因素。具体评分标准如下：1设计方案正确，具有可行性、创新性； 30分2系统开发效果较好； 20分3设计报告标准、课程设计报告

4、质量高； 20分4课程设计辩论时，问题答复正确； 20分5态度认真、刻苦钻研、遵守纪律； 10分 按上述五项分别记分后求和，总分按五级制记载最后成绩。优秀10090分，良好8089分，中等7079分，及格6069分，不及格059分设计题目：用C语言实现一元多项式的加减法运算2.开发环境、采用的语言：(1)Windows XP中文操作系统(2) Visual C+ 6.03.设计思想对你的整个设计思路作出说明：3.1问题描述：输入并建设两个多项式并输出多项式，对两个多项式进展加、减法运算，建设一个新多项式并输出。3.2问题思考：用C语言编写一段程序，该程序的功能相当于一个一元多项式的计算器，能够

5、实现按照指数降幂建设并输出多项式，并且能够完成多个多项式的相加、相减运算及结果输出的功能。此程序的数据构造是选择用带表头结点的单链表存储多项式。虽然一元多项式可以用顺序和链表存储结果表示，但顺序构造的最大长度很难确定。比方当多项式的系数较大时，此时就会浪费存储空间，所以应该选用链表构造来存储一元多项式。但链表的构造体可以用来存储多项式的系数、指数、下一个指针3个元素，这样便于实现任意多项式的加法、减法运算。3.3功能设计：1多项式建设：提示用户输入两个多项式A和B，输入形式为：先输入多项式A的项数，回车输入多项式A第一项的系数，空格隔开输入多项式A第一项的指数，继续输入多项式A的其他项，输入方

6、式与上同；再建设多项式B，数据输入方式与建设多项式A一样。2功能项：设计一个功能项，分别为1.输出多项式a和b 2.输出多项式a+b 3.输出多项式a-b 4.退出3执行操作：此时用户可以根据需要选择功能项中四项进展输出。4.程序总的流程图：通过设计思想，可设计出如图4-1所示的一元多项式总流程图：开场申请结点空间+num输入多项式的项数指针数组tempi中i=1num输入多项式各项的系数 M, 指数 N输出已输入的多项式 进展多项式的输出、加法、减法运算完毕否是是否输入正确图4.1一元多项式总流程图5.数据构造说明及模块算法说明或流程图：、5.1存储构造：一元多项式的表示在计算机内可以用链表

7、来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创立一元多项式链表，对一元多项式的运算中会出现的各种可能情况进展分析，实现一元多项式的相加、相减操作。5.2 基本算法：1一元多项式的建设：输入多项式采用头插法的方式，输入多项式中的一个项的系数和指数，就产生一个新的结点，建设起它的右指针，并用头结点指向它；为了判断一个多项式是否输入完毕，定义一个完毕标志，当输入非0时就继续；输入为0时，就完毕一个多项式的输入。2显示一元多项式：如果系数是大于0的话就输出的形式；如果系数是小

8、于0的话就输出的形式；如果指数为0的话就直接输出；如果指数是1的话就直接输出；如果指数是-1的话，就直接输出。3一元多项式加法运算 ：从两个多项式的头部开场判断，当两个多项式的某一项度不为空时，假设P、Q分别指向多项式A和多项式B中当前进展比较的结点，然后比较两个结点中的指数项，有三种情况：1、当P所指结点的指数小于Q的话，就应该复制P的结点到多项式链中。2、P所指结点的指数如果大于Q的指数的话，就应该复制Q的结点到多项式链中。3、当P所指结点的指数等于Q所指结点的指数时，那么将两个结点中的系数相加，假设和不为0，那么修改P所指结点的系数值，同时释放Q所指结点；假设和为0，从多项式A的链表中删

9、除相应结点，并释放P、Q所指结点。加法流程图如图5.2-1所示：开场定义存储结果的空链 r是 否输出存储多项式的和的链r完毕是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项图5.2-1一元多项式加法运算流程图4一元多项式的减法从两个多项式的头部开场判断，当两个多项式的某一项度不为空时，假设P、Q分别指向多项式A和多项式B中当前进展比较的结点，然后比较两个结点中的指数项，有三种情况：1、当P所指结点的指数小于Q的话，就应该复制P的结点到多项式链中。2、P所指结点的指数如果大于Q的指数的话，就应该复

10、制Q的结点到多项式链中，并将建设的结点系数变为相反数。3、当P所指结点的指数等于Q所指结点的指数时，并将Q的结点系数变为相反数，并将两个结点中的系数相加，假设和不为0，那么修改P所指结点的系数值，同时释放Q所指结点；假设和为0，从多项式A的链表中删除相应结点，并释放P、Q所指结点。减法流程图如图5.2-2所示：开场定义存储结果的空链 r是 否输出存储多项式的和的链r完毕是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项图5.2-2 一元多项式减法运算流程图6. 程序运行说明及结果截图：6.1欢迎界

11、面：程序翻开，首先显示上的是欢迎界面，在欢迎界面下方有第一个多项式的输入模块。图 6.1欢迎界面6.2输入界面：看到输入界面后，输入第一个多项式的项数，接下来输入这个多项式第一项的系数，空格继续输入这个多项式的指数。回车继续输入下一项，输入完后回车输入下一个多项式图6.2输入界面6.3功能选项：当数据输入完成后进入功能选项，在功能选项可以选择自己想要实现的功能进展操作。图6.3功能选项6.4多项式输出：在执行操作中选择1，输出多项式a和b。图6.4多项式输出6.5多项式相加：在执行操作中选择2，输出多项式a+b。图6.5多项式相加6.6多项式相减：在执行操作中选择3，输出多项式a-b。图6.6

12、多项式相减7. 程序调试及测试过程记载：本次课程设计中，经过反复调试，程序已经可以正常运行。在设计该算法时，出现了一些问题，例如在建设链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建设第三个链表来存放运算结果，而是再度利用了链表之一来进展节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进展之后加减运算。8. 总结及心得体会：在这次课程设计中，我遇到了不少困难，但是在我的坚持和虚心请教中都得到顺利解决。在这次课程设计中，我发现

13、理论必须和实践相结合，才能真正学会程序设计，才能完成一个课题。在这次设计中我参考了不少书籍，从中学到了课堂中无法学到的许多东西，对此我感到很兴奋。原来不断的学习，不断的探索是苦中带着甜，虽然经历了不少弯路，经历了不少挫折，但当程序调试成功后，当运行能到达要求后，我感到十二分成就感。面对课题，要展现自信出来，这是成功的一半，在这个设计过程中，不懂的可以虚心向教师请教，与同学交流经历。态度是成功的基石！在我这课题中，关键在于对一元多项式的表示及相加的操作。这个实际问题，在学习过的知识中找到一种适宜的模型来模拟，数据构造的选择是主要，而对于编写代码，所涉及的并不是很复杂，对于链表数据存储访问方式，在

14、C语言的学习过程中已经有过很多讲解，为了进一步了解，我还阅读了一些数据构造中关于链表的表达。对于这个课题，运用C语言简单一点的构造化程序设计已足能满足要求而不至于构造过于复杂，为了简便的实现插入操作，我选择了一个带表头结点的链表。在写源代码时要注意指针使用的正确性，为产生的新结点需及时分配存储空间。在设计中将问题抽象化，而完成后在运行时，可以说是用抽象的数据模型来解决实际问题。我的这个课题相比较于其他同学来说，是相对简单的一点的。在现实中，很多功能现在都没法实现，还有不少操作需进一步完善，这次程序设计有很多缺乏处，可能是因为经历缺乏，对问题预期不够等一些不可预见的原因所致，这些都是我以后要汲取

15、的教训。9. 附录：源代码注意要加上详细的注释#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

16、=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,&

17、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

18、(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)

19、; else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; /while printf(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多项式非空/comparePoly

20、n 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; q

21、a=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; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolynPolyn SubtractPolyn(P

22、olyn 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,h); for(p=h-next;p;p=p-next) /恢复pb的系数 p-coef*=-1; return pd;/SubtractPolynint main() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULL pri

23、ntf(*欢迎您的使用*n); printf(请输入多项式a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建设多项式a printf(*n); printf(请输入多项式b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建设多项式b /输出菜单 printf(*n); printf(功能项：nt1.输出多项式a和bnt2.建设多项式a+bnt3.建设多项式a-bn); printf(t4.退出n*请输入功能项编号*n); for(;flag=0) printf(执行操作：); scanf(%d,&flag); if(flag=1) printf(多项式a：);PrintPolyn(pa); printf(多项式b：);PrintPolyn(pb);printf(*请输入功能项编号*n);continue; if(flag=2) pc=Add