一元多项式运算课程设计

1、学 号： 200940410*课 程 设 计题 目一元多项式运算教 学 院计算机学院专 业计算机科学与技术班 级09计科（1）班姓 名*指导教师祁文青2010年12月22日目录1课程设计任务书 3 2需求分析 9 3概要设计 10总体设计思路 10主函数和子程序 11创建链表 12实现排序 125 调试报告 136 改进意见及收获体会 207 程序清单 218 主要参考文献 291课程设计应达到的目的该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。学生通过课程设计加深理解课堂教学内容，使学生在课程设计中逐步提高程序设计能力、算法分析能力、和调试

2、能力；培养学生解决实际问题的能力，自主学习和独立创新的精神。提高学生的科技论文写作能力。2课程设计题目及要求题目：一元多项式相加1问题描述已知 A ( x ) = a 0 + a 1 x + a 2 x 2 + + a n x n 和 B ( x ) = b 0 + b 1 x + b 2 x 2 + + b m x m ，并且在 A ( x ) 和 B ( x ) 中指数相差很多，求 A ( x ) = A ( x ) + B ( x ) 。 2. 基本要求：（1）设计存储结构表示一元多项式； （2）设计算法实现一元多项式相加，相减，相乘运算；（3）要求输出结果的升幂和降幂两种排列情况（4）

3、分析算法的时间复杂度和空间复杂度。 3设计思想    一元多项式求和实质上是合并同类项的过程，其运算规则为： （1）若两项的指数相等，则系数相加； （2）若两项的指数不等，则将两项加在结果中。       一元多项式 A ( x ) =a 0 +a 1 x+a 2 x 2 + +a n x n 由 n +1 个系数唯一确定，因此，可以用一个线性表 ( a 0 ， a 1 ， a 2 ， a n ) 来表示，每一项的指数 i 隐含在其系数 a i 的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中

4、就会存在很多零元素。一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。       由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。 采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。 结点结构如图所示。       coefexpnext其中，coef ：系数域，存放非零项的系数； exp ：指数域，存放非零项的指数； next ：指针域，存放指

5、向下一结点的指针。       将两个一元多项式用两个单链表存储后，如何实现二者相加呢？       设两个工作指针 p 和 q ，分别指向两个单链表的开始结点。通过对结点 p 的指数域和结点 q 的指数域进行比较进行同类项合并，则出现下列三种情况：      （1）若 p -> exp exp ，则结点 p 应为结果中的一个结点；      （2）若 p -> exp>q -&

6、gt; exp ，则结点 q 应为结果中的一个结点，将 q 插入到第一个链表中结点 p 之前；       （3）若 p -> exp=q -> exp ，则结点 p 与结点 q 为同类项，将 q 的系数加到 p 的系数上。若相加结果不为 0 ，则结点 p 应为结果中的一个结点，同时删除结点 q ；若相加结果为 0 ，则表明结果中无此项，删除结点 p 和结点 q 。      3课程设计任务及工作量的要求包括课程设计计算说明书、图纸、实物样品等要求（1）分析问题，给出数学模型，设计相

7、应的数据结构。（2）算法设计在已经选择好数据结构的前提下，为解决问题设计算法。² 确定所需模块对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。² 各子模块功能描述给出主要模块的算法描述，用流程图或伪代码表示。² 模块之间的调用关系给出算法各模块之间的关系图示（3）源程序清单（草稿）为了提高工作效率，充分利用上机调试程序的时间，要求学生在上机之前给出源程序清单。（4）用测试数据去验证算法及程序的正确性正序、逆序、随机数（5）算法分析经过上机调试，源程序运行

8、正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度。（6）提供的主程序可以象一个应用系统一样有主窗口，通过主菜单和分级菜单调用课程设计中要求完成的各个功能模块，调用后可以返回到主菜单，继续选择其他功能进行其他功能的选择。（7）按照课程设计说明书的格式规范撰写课程设计说明书，其中正文包括： 需求分析：对系统要实现的功能进行简明扼要的描述。 概要设计：根据功能描述，建立系统的体系结构，即将整个系统分解成若干子功能模块，并用框图表示各功能模块之间的衔接关系，并简要说明各模块的功能。 详细设计：详细说明各功能模块的实现过程，算法、技巧等。重点功能部分要加上清

9、晰的程序注释。 效果及存在问题：说明系统的运行效果（附上运行界面图片）、存在哪些不足以及预期的解决办法。 心得体会：谈谈自己在课程设计过程中的心得体会。（8）课程设计说明书用B5纸统一打印，装订按学校的统一要求完成。（9）课程设计的程序以软盘形式上交，文件夹名称为学生姓名及学号的组合。未经指导教师许可或无故不到者，缺勤率达50%的学生不能参加答辩。 答辩时，设计者在5分钟内阐述自己的设计过程和最终结果，突出设计中遇到的主要问题和解决方法，然后回答教师提问。每位学生答辩总时间一般不超过15分钟。 4主要参考文献1 谭浩强. C+程序设计M . 北京：清华大学出版社，2004.2 吴乃陵C+程序设

10、计实践教程M北京: 高等教育出版社,2003.3 4 5课程设计进度安排起 止 日 期工 作 内 容2009年 12月27日31日2007年12月27 日2007年12月28 日2007年12月29 日2007年12月30 日2007年12月31 日 熟悉任务，设计算法，编写源程序上机调试上机调试上机调试上机调试考核验收6成绩考核办法课程设计成绩的评定：根据设计的完成情况、程序的编制质量、独立设计能力以及答辩情况综合衡量，由答辩小组讨论决定。原则上按以下公式计算： 课程设计成绩工作表现×30%设计成果×40%考核测评×30% 工作表现：独立工作能力及设计过程的表现

11、。占总成绩的30%。设计成果：设计说明书（计算书、论文）、图纸、程序、作品等的质量。占总成绩的40%。考核测评：课程设计结束前，指导教师应采用考试或答辩等形式对所指导的学生进行测评。测评成绩占总成绩的30%。有创新的同学根据具体情况适当加分。教研室审查意见：教研室主任签字： 年 月 日院（系、部、中心）意见：主管领导签字： 年 月 日一元多项式运算1、 需求分析 该程序的主要包括三大功能：加法、减法、乘法。 1、加法：对多项式A(x)和B(x)进行相加运算，并排序； 2、减法：对多项式A(x)和B(x)进行相减运算，并排序； 3、乘法：对多项式A(x)和B(x)进行相乘运算，并排序； 要实现对

12、多项式的运算主要是对式中的系数和指数的运算，每一项都会有系数和指数，将每 项的系数和指数都放入结点中，那么对多项式的运算即为对链表进行操作。 根据程序的功能，建立系统的体系结构，即将整个系统分解成若干子功能模块： 1、createlist 创建链表，把多项式的系数和指数放入结点中，系数为0结束链表的创建； 2、display 输出链表中的系数和指数，以“A(x)= ”的形式输出； 3、heb 查找到同类项后合并同类项； 4、addlist 实现两个链表的合并，并合并同类项，从而对两个多项式相加； 5、minus 多项式的减法运算，将第二个链表中的系数取反后，再调用add_list； 6、che

13、ngfa 多项式的乘法运算，将两个链表结点中的系数相乘、指数相加后放入第三个 链表，调用heb功能； 7、paixu、daoxu 对运算结束后的链表进行升序和降序； 8、jiemian、主函数main 则是联系各子函数的链，同时也用来制作主界面。二、概要设计3、 调试报告 （1）程序开始运行，进入通讯录的主菜单,根据操作提示，选择你将进行的操作。 （1）输入1，选择加法运算 （2）输入2，选择减法运算（3）输入3，选择乘法运算 4、 改进意见及收获体会 软件课程设计能够培养我们的动手能力，创新能力，同时使我们对所学知识进一步巩固。为期一周的软件课程设计，我们掌握了如何提出设想，如何调整思路，如

14、何面对困难，如何解决问题。面对我们的课题实现一元多项式运算，我思考了很久，主要是先进行构思。首先分析了一元多项式，对于每一项都有系数和指数，对一元多项式的运算即对系数和指数的运算。其次，按照要求需要使用单项链表，将每项的系数和指数放入结点，从而创建链表。第三，对链表进行操作，实现多项式的运算。当创建链表的函数写完，我便思考加法、减法、乘法的算法。我发现三种运算方式虽然不同，但设计思路确是相通的。加法是在先合并链表后再合并同类项而实现的，减法可以在系数取反后用加法实现，乘法运算则是使每个结点相乘后放入第三个链表中，再合并同类项。因此，具体的各个功能可以分开设计，然后再各运算中调用，避免了重复编写

15、，例如程序中的heb和paixu就是按照这种想法设计的。在设计界面过程中，我确实花费了不少精力。为了界面美观大方，我查找各种资料寻找有用的界面函数，最终我找到了system（corlor）、system（cls）两个函数，用来实现界面是颜色和清屏。在设置输出图像界面时，通过反复比较、反复更改从而实现了满意的界面。程序编写完毕，在编译过程中又遇到了非常多的问题。我通过单步调试，反反复复，最终解决了这些问题。通过三天的努力，我实现了从构思到编程，到各种功能的具体运行，整个过程是艰辛的，也是快乐。五、程序清单：#include<stdlib.h>#include<stdio.h&g

16、t;#include<conio.h>typedef struct list1int zhishu;int xishu;struct list1 *next;typedef struct list1 node;typedef node *link;/*/link create_list(link head) link new1; link pointer; head=(link)malloc(sizeof(node); if(head=NULL) printf("出现错误！n"); else head->next=NULL;head->zhishu=

17、0;head->xishu=0; pointer=head; printf("nn"); while(1) new1=(link)malloc(sizeof(node); printf("n 系数:"); scanf("%d",&(new1->xishu); if (new1->xishu=0) printf("n * 参数已输入完成！ *nn"); free(new1);break; printf(" 输入指数:"); scanf("%d",&am

18、p;(new1->zhishu); new1->next=NULL; pointer->next=new1;pointer=new1; return head;/*/link heb(link head) int a;link pt1,pt2,t;pt1=head->next; while(pt1!=NULL) pt2=pt1; a=pt1->xishu; while(pt2->next!=NULL) if(pt1->zhishu)=(pt2->next->zhishu) t=pt2->next; a=a+(t->xishu);

19、 pt2->next=t->next; free(t); else pt2=pt2->next; pt1->xishu=a; pt1=pt1->next; return head;/*/link add_list(link head1,link head2) link pt1; link pt2; pt1=head1->next; pt2=head2->next; free(head2); if(pt1=NULL) pt1=head1; else while(pt1->next!=NULL)pt1=pt1->next; if(pt2=NUL

20、L) return head1; else pt1->next=pt2; head1=heb(head1); return head1;/*/link minus(link head1,link head2) link pt,head3; pt=head2->next; while(pt!=NULL) pt->xishu=-(pt->xishu); pt=pt->next; head3=add_list(head1,head2); return head3;/*/link chengfa(link head1,link head2) link p1,p2,p3,s

21、; link head3=NULL; head3=(link)malloc(sizeof(node); if(head3=NULL) printf("Memory allocate Failure!n"); else head3->next=NULL;head3->zhishu=0;head3->xishu=0; p1=head1->next;p2=head2->next;p3=head3; while(p1!=NULL) p2=head2->next; while(p2!=NULL) s=(link)malloc(sizeof(node

22、); s->zhishu=p1->zhishu+p2->zhishu; s->xishu=(p1->xishu)*(p2->xishu); s->next=NULL; p3->next=s; p3=s; p2=p2->next; p1=p1->next; head3=heb(head3); return head3;link daoxu(link head) link p1,p2; p1=head->next; p2=p1->next; p1->next=NULL; while(p2!=NULL) head->

23、next=p2; p2=p2->next; head->next->next=p1; p1=head->next; return head;/*/link paixu(link head) link p=head,q=head->next,f,t; int j=0,i; while(p!=NULL) j+; p=p->next; if(j=1) printf("n"); return head; if(j=2) printf("n"); return head; f=head; if(j>2) printf(&q

24、uot;n");for(i=1;i<=j;i+) while(q->next!=NULL) if(q->zhishu>q->next->zhishu) t=q->next; t=t->next; q->next->next=q; q=q->next; q->next->next=t; f->next=q; f=f->next; q=q->next; f=head; q=head->next; j-; return head;/*/void display(link head) lin

25、k p; p=head; p=p->next; if(p=NULL) printf("0"); else if(p->xishu=0)printf("0"); else printf("(%d)x(%d)",p->xishu,p->zhishu); p=p->next; while(p!=NULL) if(p->xishu=0)printf("+0"); else printf("+(%d)x(%d)",p->xishu,p->zhishu); p

26、=p->next; /*/void jiemian() int i; system("cls"); system("color 2"); printf("n "); for(i=0;i<7;i+) printf(""); for(i=0;i<1;i+)printf("n ");printf("n 欢迎使用一元多项式运算器！ "); printf("n ");printf("n "); printf("n &q

27、uot;); printf("n 说明：为链表输入数据，系数值为零时退出! "); printf("n "); printf("n ");printf("n "); printf("n - ");printf("n (1)加法! "); printf("n - "); printf("n (2)减法! "); printf("n - "); printf("n (3)乘法! "); printf(

28、"n - "); printf("n (0)退出运算! "); printf("n - "); printf("n "); printf("n "); for(i=0;i<7;i+) printf("");printf("nn 请输入运算法则："); int main() int q=1,i; int f; while(q=1) jiemian(); scanf("%d",&q); if(q!=0) link head1=

29、NULL; link head2=NULL; link head3=NULL; system("cls"); system("color 6"); if(q>=1&&q<=3) printf("nn *请输入A(x)的系数和指数*"); head1=create_list(head1); printf("输入任意键继续！ "); scanf("%d",&f); system("cls"); printf("n *请输入B(x)的系数和指数*"); head2=create_list(head2); printf("