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

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

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

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

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

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

6、续输入多项式 A的其他项，输入方式与上同；4)再建立多项式 B,数据输入方式与建立多项式 A相同。(2)功能项：设计一个功能项，分别为 1.输出多项式a和b2.输出多项式a+b3. 输出多项式a-b4. 退出(3)执行操作：此时用户可以根据需要选择功能项中四项进行输出。4 .程序总的流程图：通过设计思想，可设计出如图4-1所示的一元多项式总流程图:图4.1 一元多项式总流程图5 .数据结构说明及模块算法说明(或流程图)：、5.1 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存

7、放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。5.2 基本算法：(1) 一元多项式的建立：输入多项式采用头插法的方式，输入多项式中的一个项的系数和指数，就产生一个新的结点，建立起它的右指针，并用头结点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非 。时就继续；输入为 。时，就结束一个多项式的输入。(2)显小一兀多项式：如果系数是大于0的话就输出+系数MA指数的形式；如果系数是小于0的话就输出 系数XA指数的形式；如果指数为 0的话就直接输出系数；如果指数是1的话就直接

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

9、如图5.2-1所示：图5.2-1 一元多项式加法运算流程图(4) 一元多项式的减法从两个多项式的头部开始判断，当两个多项式的某一项度不为空时，假设P、Q分别指向多项式A和多项式B中当前进行比较的结点， 然后比较两个结点中的指数项，有三种情况：1、当P所指结点的指数小于 Q的话，就应该复制 P的结点到多项式链中。2、P所指结 点的指数如果大于 Q的指数的话，就应该复制Q的结点到多项式链中，并将建立的结点系数 变为相反数。3、当P所指结点的指数等于 Q所指结点的指数时，并将 Q的结点系数变为相 反数，并将两个结点中的系数相加，若和不为0,则修改P所指结点的系数值，同时释放 Q若和为 0,从多项式A

10、的链表中删除相应结点，并释放P、Q所指结点。减法流程图如图5.2-2所示:图5.2-2 一元多项式减法运算流程图6.程序运行说明及结果截图:6.1欢迎界面:程序打开，首先显示上的是欢迎界面，在欢迎界面下方有第一个多项式的输入模块。c数据结构tDebugt需图超.ex丁日日瓜图6.1欢迎界面6.2 输入界面:看到输入界面后，输入第一个多项式的项数， 接下来输入这个多项式第一项的系数，空格继续输入这个多项式的指数。回车继续输入下一项，输入完后回车输入下一个多项图6.2输入界面6.3 功能选项：当数据输入完成后进入功能选项，在功能选项可以选择自己想要实现的功能进行操作。人多项式双的项数:2 士项的系

11、数与指数工1 3入第2项的系数与指数:2 6IJZ入1A1A1A项式h的项数门1项的系数与指数:2 52项的系数与指数:二二3项的家数与指数二4 2：3 612 3 4一电力 禾+ - aaa 项项攻 多的多 出立立出 输建建退丸行操作:图6.3功能选项6.4 多项式输出：在执行操作中选择1,输出多项式a和b。XMXXXXXXXXXXXXM*MMX*MXXXX算请输入第2项的系数与指数：2 6请揄入爰项式总的项数二2踵霸入篦1项的系数与指数门3<第差人入入入项式b的项数：3t项的系数与相数S2项的系数与指数二3 63项的系数与指数：4 2功能项：1 .输出多项式a和h2 ,建立多项式a*

12、h3 .建立多项式af4 .退出、口:匕.苜'M MMM MMM M X M MMM MMM 注射 M WK执行鎏作；1 多项式廷：2/6十k3 多项式b： 3X% +2XA5 +4X2XJtX/JtXKJtXKJtXKJtXKJOIltatXKJOIlti青福一入及J 官昌*乂*/ HKK，1t 1tHlt K，1tMlt，* 1txlt 执行操作，图6.4多项式输出6.5多项式相加：在执行操作中选择2,输出多项式a+b。NPM用手用2 3 4 却如期 3匕日匕日匕日 :frYJL寸 4141 数与与与 夜数期破 的系系系 b内向内 嚅项项 r 1 2 3 1AJA1A1A &quo

13、t;月MnMRwfr功能项：工”输出多项式&和b2.立多项式币+h3 .建立多项式4 ,退出、：2XA6+XA3s 3m5+4*2 !WWM7C»iWM>JWM j舌| /'1. jf茸* 工贝M 注 3cM it JWM; 也行壁作，2、,多项式mb； 5«%+25+»*3+4«*2,紧一具-其其<-其-一- 青，前月|苜*工号板行操作工图6.5多项式相加6.6多项式相减：虹项的系数与揖数 眨项的系数与指数:1IX入入1A项式h的项薮：31项的系数与揖数二2 5Z项的系数与指数：3 612 .而出多项式a和h 隹立多项式a

14、<b5XA6+2X5+XA3+4XA2*1 请输入功昌县项编号*2.建立多项式小-b4.退出口XKHXXXXKMEKXXXKMEXXMXKMtKXMX 11c j 青苜行 当扁3项的系数与目於4 22X6 *产33X6+2XA5+4XA2*请输入功能项编号*2瑞福人功能项编号在执行操作中选择3,输出多项式a-bo图6.6多项式相减7 .程序调试及测试过程记载：本次课程设计中，经过反复调试，程序已经可以正常运行。在设计该算法时，出现 了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好 的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链 表

15、并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后 先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。8 .总结及心得体会：在这次课程设计中，我遇到了不少困难，但是在我的坚持和虚心请教中都得到顺利解 决。在这次课程设计中，我发现理论必须和实践相结合，才能真正学会程序设计，才能完成一个课题。在这次设计中我参考了不少书籍，从中学到了课堂中无法学到的许多东西， 对此我感到很兴奋。原来不断的学习，不断的探索是苦中带着甜，虽然经历了不少弯路，经历了不少挫折，但当程序调试成功后，当运行能达到要求后

16、，我感到十二分成就感。面对课题， 要展现自信出来，这是成功的一半，在这个设计过程中，不懂的可以虚心向老师请教，与同学交流经验。态度是成功的基石！ 在我这课题中，关键在于对一元多项式的表示及相加的操作。这个实际问题，在学习过的知识中找到一种合适的模型来模拟，数据结构的选择是主要，而对于编写代码，所涉及的并不是很复杂，对于链表数据存储访问方式，在C语言的学习过程中已经有过很多讲解，为了进一步了解，我还阅读了一些数据结构中关于链表的叙述。对于这个课题，运用C语言简单一点的结构化程序设计已足能满足要求而不至于结构过于复杂，为了简便的实现插入操作，我选择了一个带表头结点的链表。在写源代码时要注意指针使用

17、的正确性，为产生的新结点需及时分配存储空间。在设计中将问题抽象化，而完成后在运行时，可以说是用抽象的数据模 型来解决实际问题。我的这个课题相比较于其他同学来说，是相对简单的一点的。 在现实中，很多功能现在都没法实现，还有不少操作需进一步完善，这次程序设计有很多不足处， 可能是因为经验不足，对问题预期不够等一些不可预见的原因所致，这些都是我以后要汲取的教训。9 .附录：源代码（注意要加上详细的注释）#include<stdio.h>#include<malloc.h>typedef struct Polynomialfloat coef;int expn;struct P

18、olynomial *next;*Polyn,Polynomial; /Polynvoid Insert(Polyn p,Polyn h) if(p->coef=0) free(p); / elsePolyn q1,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) /q1->ne

19、xt=q2->next;free(q2);else/p->next=q2;q1->next=p; /InsertPolyn CreatePolyn(Polyn head,int m)/多项式int i;为结点指针类型系数为0的话释放结点查找插入位置将指数相同相项合并系数为0的话释放结点指数为新时将结点插入建立一个头指针为head、项数为m的一元Polyn p;p=head=(Polyn)malloc(sizeof(struct Polynomial);head->next=NULL;for(i=0;i<m;i+)p=(Polyn)malloc(sizeof(str

20、uct Polynomial);/建立新结点以接收数据printf("请输入第狈的系数与指数:",i+1);scanf("%f %d",&p->coef,&p->expn); Insert(p,head); / 调用Insert 函数插入结点return head;CreatePolynvoid DestroyPolyn(Polyn p)/销毁多项式 pPolyn q1,q2;q1=p->next;q2=q1->next;while(q1->next)free(q1);q1=q2;/指针后移q2=q2->

21、;next;void PrintPolyn(Polyn P)Polyn q=P->next;int flag=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-

22、>coef);if(q->expn=1) putchar('X');else if(q->expn) printf("XA%d",q->expn);elseif(q->coef=1)if(!q->expn) putchar('l');else if(q->expn=1) putchar('X');else printf("XA%d",q->expn);if(q->coef=-1)if(!q->expn) printf("-1")

23、;else if(q->expn=1) printf("-X");else printf("-XA%d",q->expn); q=q->next;flag+;/whileprintf("n");PrintPolynint compare(Polyn a,Polyn b)if(a&&b)if(!b|a->expn>b->expn) return 1;else if(!a|a->expn<b->expn) return -1;多项式已空，但 b多项式非空else ret

24、urn 0;else if(!a&&b) return -1;/aelse 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

25、(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;/sw

26、itchif(qc->coef!=0)qc->next=hc->next;hc->next=qc;hc=qc;else free(qc);/ 当相加系数为。时，释放该结点/whilereturn headc;/AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb)求解并建立多项式 a+b,返回其头指针Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p)/将pb的系数取反p->coef*=-1;p=p->next;恢复pb的系数pd=AddPolyn(pa,h);for(p=h-

27、>next;p;p=p->next) / p->coef*=-1;return pd;SubtractPolynint main() int m,n,flag=0;Polyn pa=0,pb=0,pc,pd,pe,pf;/float x;定义各式的头指针，pa与pb在使用前付初值 NULLprintf( "*n");printf（" 请输入多项式 a的项数："）;scanf("%d",&m);pa=CreatePolyn(pa,m);/建立多项式 aprintf( "* *n，);printf（” 请输入多项式 b的项数："）;scanf("%d",&n);pb=CreatePolyn(pb,n);/建立多项式 b /输出菜单printf( "* *n，);printf（" 功能项：nt1