C++一元多项式计算问题-课程设计说明书

1、精选优质文档-倾情为你奉上 学 院课程设计说明书题目一元多项式计算问题系(部)计算机科学与技术系专业(班级)计算机科学与技术专业姓名学号指导教师起止日期第十三、十四周专心-专注-专业课程设计任务书课程名称：数据结构与算法设计题目：一元多项式计算问题已知技术参数和设计要求：问题描述：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；测试数据：(1) A+B A= 3x14-8x8+6x2+

2、2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x选作内容：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积设计工作量：40课时工作计划：班级：计科3班 指导教师：刘钢钦周次星期地点设计方式13星期一1-2节A多1讲授内容星期二3-4节科1608答疑星期二5-8节1403上机调试星期三1-4节科16

3、08答疑星期四1-4节1404上机调试星期四5-8节科1608答疑1414星期二3-4节科1608答疑星期二5-8节1403上机调试星期三1-4节科1608答疑星期四1-4节1404上机调试星期四5-8节科1608答疑星期四9-10节1403答辩指导教师签名：日期：教研室主任签名： 日期：系主任签名： 日期：长沙学院课程设计鉴定表姓名学号专业计算机科学与技术专业班级设计题目一元多项式计算问题指导教师指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”

4、、“及格”、“不及格”四类；摘要本文是关于一个一元稀疏多项式计算器的问题。一元稀疏多项式计算内容包括输入并建立多项式,多项式相加，多项式求值，多项式求乘积以及输出多项式。本程序运用面向对象程序设计方法，使用C+语言，利用Microsoft Visual C+ 6.0开发工具，还有数据结构课中学到的链式存储结构，存储一元稀疏多项式，从而实现程序的基本功能。在程序中定义了各种类型的运算的模块，通过主程序的调用来完成它们之间的配合，进而使得一元稀疏多项式计算器的顺利运行。关键词：数据结构；一元稀疏多项式；链表； C+语言目录1 设计内容与要求 12.设计说明 1 2.1 问题描述与功能设计1 2.2

5、 数据结构与算法1 2.3 函数定义3 2.4 界面设计4 2.5 编码5 2.6 测试103 总结14参考文献 15附录A 源代码16设计内容与要求设计内容：设计一个稀疏多项式简单计算器，能够进行简单的基本运算。如：多项式相加、多项式相减、多项式求值等等。基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；创新要求：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积2.设计说明2.1 问题描述与功能设计本

6、程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后，能够进行多项式输出、多项式相加、多项式相减、多项式求值、多项式求积的运算。2.2 数据结构与算法数据结构多项式的逻辑结构：视为线性表 p(x)=3x14-8x8+6x2+2数据元素 (coef,exp) 表示多项式项 coef·Xexp ，coef是该项的系数，exp是变元X的指数。为了实现任意多项式的运算，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个成员。算法多项式的输入与建立调用CreatePolyn（）函数建立链表，将多项式每一项的系数与指数作为链表一个结点的数据，按照指示输入每一项的系数与指数时，将调用

7、Insert（）函数，将输入的结点信息按指数降序排列的方式插入到之前建立的链表中，并合并同类项。依次输入、建立一元多项式pa和pb。如下图。多项式的输出 调用PrintPolyn（）函数将多项式链表中的结点数据按照一元多项式的格式(如：6x5+3x3+7x+3)输出到屏幕上。两个多项式的加法 调用AddPolyn（）函数直接对两个多项式的链表的结点成员的系数与指数按照数学中多项式相加的原则进行操作。其中要调用compare（）函数对两个多项式的指数或是项数进行比较。相加所得的多项式存放到新建的第三个多项式中。再对第三个多项式输出即可。两个多项式的减法调用SubtractPolyn（）函数对两个

8、多项式减法运算。首先对要减的多项式的系数求反，接着调用AddPolyn（）函数对处理后的多项式相加即两个多项式的相减。所得的多项式存放到新建的第三个多项式中，再对第三个多项式输出即可。多项式的求值调用ValuePolyn（）函数对多项式求值。在用户输入X的值后，对链表每个结点的数据进行求值，然后求和即多项式在X为某一值的值。其中用到C语言中的数学函数：pow。其功能为计算x的y次幂，所在头文件：math.h 。两个多项式的乘法调用MultiplyPolyn（）函数对两个多项式进行乘法运算。根据数学知识，依次用一个多项式的每一项乘以另一个多项式的每一项，再求和、合并同类项即两个多项式的

9、乘积。当中用了多两个多项式的while循环，以确保两个多项式的每一项都得到相应的运算，每一次运算后调用Insert()函数把乘积插入到新建的链表中，以得到一个结点信息按指数降序排列的方式排列，并以合并同类项的链表。2.3 函数定义为了程序功能的顺利实现，在本程序中定义了如下函数：函数名 功能Insert() 链表结点数据的插入与排序CreatePolyn() 链表头结点的创建DestroyPolyn() 链表的销毁PrintPolyn() 链表数据的多项式形象化输出Compare() 两个多项式的指数或是项数进行比较AddPolyn() 两个多项式的加法SubtractPolyn() 两个多项

10、式的减法ValuePolyn() 多项式的求值MultiplyPolyn() 两个多项式的乘法desktop() 程序界面的实现2.4 界面设计程序数据初始界面： 程序操作主界面：2.5 编码链表建立的函数,该函数在多项式信息输入时按照指数降序排列建立链表，并在出现同类项时合并。void Insert(Polyn p,Polyn h) if(p->coe=0) delete p; /当前结点的coe成员等于0的时候删除当前结点 elsePolyn q1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp) /查找

11、插入位置 q1=q2;q2=q2->next;if(q2&&p->exp=q2->exp) /将指数相同相合并 q2->coe+=p->coe;delete p;if(!q2->coe) q1->next=q2->next;delete q2;else/指数为新时将结点插入 p->next=q2;q1->next=p;链表信息按照多项式形式输出。void PrintPolyn(Polyn P) Polyn q=P->next; int flag=1; /项数计数器if(!q) /若多项式为空，输出0cout<

12、;<"0" cout<<endl;return; while (q)if(q->coe>0&&flag!=1) cout<<"+" /系数大于0且不是第一项时就输出+if(q->coe!=1&&q->coe!=-1) /系数非1或-1的普通情况cout<<q->coe; if(q->exp=1) cout<<"X"/当前结点exp为1时else if(q->exp) cout<<"X&q

13、uot;<<q->exp;elseif(q->coe=1) 系数为1的特殊情况if(!q->exp) cout<<"1"/指数不存在else if(q->exp=1) cout<<"X"/指数等于一else cout<<"X"<<q->exp;if(q->coe=-1) 系数为-1的特殊情况情况if(!q->exp) cout<<"-1" /指数不存在else if(q->exp=1) cout&

14、lt;<"-X" /指数等于一else cout<<"-X"<<q->exp;q=q->next; /当前指针指向下一结点flag+;/项序数自加1cout<<endl;两个多项式的加法。int compare(Polyn a,Polyn b)/对两个多项式的系数或项数进行比较if(a&&b) /两个多项式都存在if(!b|a->exp>b->exp) return 1;当b多项式不存在或者a多项式的指数大于b的的时候，返回1else if(!a|a->exp&

15、lt;b->exp) return -1; 当a多项式不存在或者b多项式的指数大于a的的时候，返回-1else return 0;/其他情况返回0else if(!a&&b) return -1; /a多项式已空，但b多项式非空else return 1; /b多项式已空，但a多项式非空Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa->next;Polyn qb=pb->next;Polyn headc,hc,qc;hc=new Polynomial;/建立一个新的结点hc->next=NULL;headc=hc

16、;while(qa|qb)qc=new Polynomial;/新建一个结点switch(compare(qa,qb)/调用compare函数对两个多项式进行比较case 1:/ a多项式的指数大于b的qc->coe=qa->coe;qc->exp=qa->exp;qa=qa->next;break;case 0:/有同类项则合并 qc->coe=qa->coe+qb->coe;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;case -1: a多项式的指数小于b的qc->

17、coe=qb->coe;qc->exp=qb->exp;qb=qb->next;break; if(qc->coe!=0) /当相加系数不为0时qc->next=hc->next;hc->next=qc;hc=qc;else delete qc; /当相加系数为0时，释放该结点return headc;两个多项式的减法。两个多项式的减法是建立在加法的的基础上，对要减的多项式的系数求反，接着调用AddPolyn（）函数对处理后的多项式相加即两个多项式的相减Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn h=p

18、b;Polyn p=pb->next;/新建一个结点作为pb的后继结点Polyn pd;while(p)/当结点存在时，对所有coe数据求反 p->coe*=-1;p=p->next;pd=AddPolyn(pa,h);/调用加法函数for(p=h->next;p;p=p->next) /恢复pb的系数 p->coe*=-1;return pd;多项式求值函数。当中运用到了C语言中的数学函数：pow。其功能为计算x的y次幂，所在头文件：math.h 。float ValuePolyn(Polyn head,float x)Polyn p; p=he

19、ad->next; float result=0; while(p!=NULL) /当前结点信息存在时，对其求值并累加到前驱结点的值 result+=(p->coe)*(float)pow(x,p->exp); p=p->next; return result; 两个多项式的乘法Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;/Polyn qa=pa->next; /新建一个结点作为pa的后继结点Polyn qb=pb->next; /新建一个结点作为pb的后继结点hf=new Polynomial;hf-

20、>next=NULL;while(qa)/使用while循环，使得多项式的每项得以运算qb=pb->next;while(qb)pf=new Polynomial;pf->coe=qa->coe*qb->coe;pf->exp=qa->exp+qb->exp;Insert(pf,hf);/调用插入函数，将新的结点插入到新建链表中，并合并同类项qb=qb->next;qa=qa->next;return hf;/返回所得链表的头指针2.6 测试测试软件：Microsoft Visual C+ 6.0测试的数据：(1) A+B A= 3x

21、14-8x8+6x2+2 B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x(6) A*B A= 5x6+4x5+3x4 B= 6x6+5x5 (7) A= 5x6+4x5+3x4 X=2测试过程与结果：(1) A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 A+B=3x14+2x10-4x8+2

22、 (2) A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 A-B=9x14+3x10-x8+5x6-2 (3) A=x3+x1 B=-x3-x1A+B=0 (4) A=0 B=x7+x5+x3+x1A+B=x7+x5+x3+x (5)A=100x100+50x50+20x20+x B=10x100+10x50+10x20+xA-B=90x100+40x50+10x20 (6)A= 5x6+4x5+3x4 B= 6x6+5x5 A*B =30x12+49x11+38x10+15x9 (7)A= 5x6+4x5+3x4 X=2A=4963 总结本次课程设计中，通过

23、对一元多项式计算问题的解决，不仅让我对数据结构学到的知识得到温习，而且让我在实践的过程中队所学知识得到了巩固。实验设计的过程中，坚持“学以致用”的原则，让我充分利用所学的理论知识进行相对复杂的应用设计，以进一步提高综合能力和创新实践能力，让我在课堂教学中所得进一步升华。最后我要衷心的感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利!参考文献1 王挺，周会平，贾丽丽，许锡山. C+程序设计M. 北京：清华大学出版社，20052 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，2005.3 李根强. 数据结构（C+版）习题解答及实训指导M. 北京：

24、中国水利水电出版社，2009.附录A 源代码#include<iostream.h>#include <stdlib.h>#include <math.h> typedef struct Polynomialint coe;int exp;struct Polynomial *next;*Polyn,Polynomial; void Insert(Polyn p,Polyn h) if(p->coe=0) delete p; elsePolyn q1,q2;q1=h;q2=h->next;while(q2&&p->exp&l

25、t;q2->exp) q1=q2;q2=q2->next;if(q2&&p->exp=q2->exp) q2->coe+=p->coe;delete p;if(!q2->coe) q1->next=q2->next;delete q2;else p->next=q2;q1->next=p;Polyn CreatePolyn(Polyn head,int m)int i;Polyn p;p=head=new Polynomial;head->next=NULL;for(i=0;i<m;i+)p=new

26、Polynomial;cout<<"请输入第"<<i+1<<"项的系数:"cin>>p->coe;cout<<" 指数:"cin>>p->exp;Insert(p,head);return head;void DestroyPolyn(Polyn p)Polyn t;while(p!=NULL)t=p;p=p->next;delete t;void PrintPolyn(Polyn P) Polyn q=P->next; int flag=

27、1;if(!q) cout<<"0" cout<<endl;return; while (q)if(q->coe>0&&flag!=1) cout<<"+" if(q->coe!=1&&q->coe!=-1)cout<<q->coe; if(q->exp=1) cout<<"X"else if(q->exp) cout<<"X"<<q->exp;else

28、if(q->coe=1)if(!q->exp) cout<<"1"else if(q->exp=1) cout<<"X"else cout<<"X"<<q->exp;if(q->coe=-1)if(!q->exp) cout<<"-1" else if(q->exp=1) cout<<"-X" else cout<<"-X"<<q->

29、exp;q=q->next; flag+;cout<<endl;int compare(Polyn a,Polyn b)if(a&&b)if(!b|a->exp>b->exp) return 1;else if(!a|a->exp<b->exp) return -1;else return 0;else if(!a&&b) return -1;else return 1;Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa->next;Polyn qb=pb->

30、next;Polyn headc,hc,qc;hc=new Polynomial;hc->next=NULL;headc=hc;while(qa|qb)qc=new Polynomial;switch(compare(qa,qb)case 1:qc->coe=qa->coe;qc->exp=qa->exp;qa=qa->next;break;case 0: qc->coe=qa->coe+qb->coe;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;case -1:qc-

31、>coe=qb->coe;qc->exp=qb->exp;qb=qb->next;break; if(qc->coe!=0)qc->next=hc->next;hc->next=qc;hc=qc;else delete qc;return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p) p->coe*=-1;p=p->next;pd=AddPolyn(pa,h);for(p=h->nex

32、t;p;p=p->next) p->coe*=-1;return pd;float ValuePolyn(Polyn head,float x)Polyn p; p=head->next; float result=0; while(p!=NULL) result+=(p->coe)*(float)pow(x,p->exp); p=p->next; return result; Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;Polyn qa=pa->next;Polyn qb=pb->next

33、;hf=new Polynomial;hf->next=NULL;while(qa)qb=pb->next;while(qb)pf=new Polynomial;pf->coe=qa->coe*qb->coe;pf->exp=qa->exp+qb->exp;Insert(pf,hf);qb=qb->next;qa=qa->next;return hf;void desktop()system("cls");cout<<" 一元多项式的计算"<<endl;cout<&

34、lt;"*"<<endl;cout<<"* 1.输出多项式a和b *"<<endl;cout<<"* 2.建立多项式a+b *"<<endl;cout<<"* 3.建立多项式a-b *"<<endl;cout<<"* 4.计算多项式a的值 *"<<endl;cout<<"* 5.建立多项式a*b *"<<endl;cout<<&quo

35、t;* 6.重新建立多项式a和b *"<<endl;cout<<"* 7.退出 *"<<endl;cout<<"*"<<endl;cout<<"执行操作:"void main()int m,n;float x,result;char key;Polyn pa,pb,pc,pd,pf;r1:cout<<"欢迎您的使用！"<<endl;cout<<"请您初始化数据."<<

36、endl<<endl;cout<<"请输入多项式a的项数:"cin>>m;pa=CreatePolyn(pa,m);cout<<endl;cout<<"请输入多项式b的项数:"cin>>n;pb=CreatePolyn(pb,n);system("pause");system("cls");while(key)desktop();cin>>key;switch (key)case'1':cout<<"多项式a：&qu