C++一元多项式计算问题课程设计说明书.docx
- 文档编号:9493145
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:29
- 大小:234.25KB
C++一元多项式计算问题课程设计说明书.docx
《C++一元多项式计算问题课程设计说明书.docx》由会员分享,可在线阅读,更多相关《C++一元多项式计算问题课程设计说明书.docx(29页珍藏版)》请在冰点文库上搜索。
C++一元多项式计算问题课程设计说明书
XX学院
课程设计说明书
题目
一元多项式计算问题
系(部)
计算机科学与技术系
专业(班级)
计算机科学与技术专业
姓名
学号
指导教师
起止日期
课程设计任务书
课程名称:
数据结构与算法
设计题目:
一元多项式计算问题
已知技术参数和设计要求:
问题描述:
设计一个稀疏多项式简单计算器
基本要求:
(1)输入并分别建立多项式A和B
(2)输入输出多项式,输出形式为整数序列:
n,c1,e1,c2,e2……,其中n是多项式的项数,ci和ei是第i项的系数和指数,序列按指数降序排列
(3)完成两个多项式的相加、相减,并将结果输出;
测试数据:
(1)A+BA=3x14-8x8+6x2+2B=2x10+4x8+-6x2
(2)A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7
(3)A+BA=x3+x1B=-x3-x1
(4)A+BA=0B=x7+x5+x3+x1
(5)A-BA=100x100+50x50+20x20+xB=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节
科1608
答疑
星期四1-4节
1404
上机调试
星期四5-8节
科1608
答疑
14
14
星期二3-4节
科1608
答疑
星期二5-8节
1403
上机调试
星期三1-4节
科1608
答疑
星期四1-4节
1404
上机调试
星期四5-8节
科1608
答疑
星期四9-10节
1403
答辩
指导教师签名:
日期:
教研室主任签名:
日期:
系主任签名:
日期:
长沙学院课程设计鉴定表
姓名
学号
专业
计算机科学与技术专业
班级
设计题目
一元多项式计算问题
指导教师
指导教师意见:
评定等级:
教师签名:
日期:
答辩小组意见:
评定等级:
答辩小组长签名:
日期:
教研室意见:
教研室主任签名:
日期:
系(部)意见:
系主任签名:
日期:
说明
课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类;
摘要
本文是关于一个一元稀疏多项式计算器的问题。
一元稀疏多项式计算内容包括输入并建立多项式,多项式相加,多项式求值,多项式求乘积以及输出多项式。
本程序运用面向对象程序设计方法,使用C++语言,利用MicrosoftVisualC++6.0开发工具,还有数据结构课中学到的链式存储结构,存储一元稀疏多项式,从而实现程序的基本功能。
在程序中定义了各种类型的运算的模块,通过主程序的调用来完成它们之间的配合,进而使得一元稀疏多项式计算器的顺利运行。
关键词:
数据结构;一元稀疏多项式;链表;C++语言
目录
1设计内容与要求…………………………………………………………………………………1
2.设计说明…………………………………………………………………………………………1
2.1问题描述与功能设计…………………………………………………………………………1
2.2数据结构与算法………………………………………………………………………………1
2.3函数定义………………………………………………………………………………………3
2.4界面设计………………………………………………………………………………………4
2.5编码……………………………………………………………………………………………5
2.6测试……………………………………………………………………………………………10
3总结…………………………………………………………………………………………………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问题描述与功能设计
本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后,能够进行多项式输出、多项式相加、多项式相减、多项式求值、多项式求积的运算。
2.2数据结构与算法
数据结构
多项式的逻辑结构:
视为线性表
p(x)=3x14-8x8+6x2+2
数据元素(coef,exp)
表示多项式项coef·Xexp,coef是该项的系数,exp是变元X的指数。
为了实现任意多项式的运算,因此选择单链表的结构体,它有一个系数,指数,下一个指针3个成员。
算法
多项式的输入与建立
调用CreatePolyn()函数建立链表,将多项式每一项的系数与指数作为链表一个结点的数据,按照指示输入每一项的系数与指数时,将调用Insert()函数,将输入的结点信息按指数降序排列的方式插入到之前建立的链表中,并合并同类项。
依次输入、建立一元多项式pa和pb。
如下图。
多项式的输出
调用PrintPolyn()函数将多项式链表中的结点数据按照一元多项式的格式(如:
6x^5+3x^3+7x+3)输出到屏幕上。
两个多项式的加法
调用AddPolyn()函数直接对两个多项式的链表的结点成员的系数与指数按照数学中多项式相加的原则进行操作。
其中要调用compare()函数对两个多项式的指数或是项数进行比较。
相加所得的多项式存放到新建的第三个多项式中。
再对第三个多项式输出即可。
两个多项式的减法
调用SubtractPolyn()函数对两个多项式减法运算。
首先对要减的多项式的系数求反,接着调用AddPolyn()函数对处理后的多项式相加即两个多项式的相减。
所得的多项式存放到新建的第三个多项式中,再对第三个多项式输出即可。
多项式的求值
调用ValuePolyn()函数对多项式求值。
在用户输入X的值后,对链表每个结点的数据进行求值,然后求和即多项式在X为某一值的值。
其中用到C语言中的数学函数:
pow。
其功能为计算x的y次幂,所在头文件:
math.h 。
两个多项式的乘法
调用MultiplyPolyn()函数对两个多项式进行乘法运算。
根据数学知识,依次用一个多项式的每一项乘以另一个多项式的每一项,再求和、合并同类项即两个多项式的乘积。
当中用了多两个多项式的while循环,以确保两个多项式的每一项都得到相应的运算,每一次运算后调用Insert()函数把乘积插入到新建的链表中,以得到一个结点信息按指数降序排列的方式排列,并以合并同类项的链表。
2.3函数定义
为了程序功能的顺利实现,在本程序中定义了如下函数:
函数名功能
Insert()链表结点数据的插入与排序
CreatePolyn()链表头结点的创建
DestroyPolyn()链表的销毁
PrintPolyn()链表数据的多项式形象化输出
Compare()两个多项式的指数或是项数进行比较
AddPolyn()两个多项式的加法
SubtractPolyn()两个多项式的减法
ValuePolyn()多项式的求值
MultiplyPolyn()两个多项式的乘法
desktop()程序界面的实现
2.4界面设计
程序数据初始界面:
程序操作主界面:
2.5编码
链表建立的函数,该函数在多项式信息输入时按照指数降序排列建立链表,并在出现同类项时合并。
voidInsert(Polynp,Polynh)
{
if(p->coe==0)deletep;//当前结点的coe成员等于0的时候删除当前结点
else{
Polynq1,q2;
q1=h;q2=h->next;
while(q2&&p->exp
{
q1=q2;
q2=q2->next;
}
if(q2&&p->exp==q2->exp)//将指数相同相合并
{
q2->coe+=p->coe;
deletep;
if(!
q2->coe)
{
q1->next=q2->next;
deleteq2;
}
}
else//指数为新时将结点插入
{
p->next=q2;
q1->next=p;
}
}
}
链表信息按照多项式形式输出。
voidPrintPolyn(PolynP){
Polynq=P->next;
intflag=1;//项数计数器
if(!
q)
{//若多项式为空,输出0
cout<<"0";
cout< return; } while(q) { if(q->coe>0&&flag! =1)cout<<"+";//系数大于0且不是第一项时就输出+ if(q->coe! =1&&q->coe! =-1)//系数非1或-1的普通情况 { cout< if(q->exp==1)cout<<"X";//当前结点exp为1时 elseif(q->exp)cout<<"X^"< } else { if(q->coe==1)系数为1的特殊情况 { if(! q->exp)cout<<"1";//指数不存在 elseif(q->exp==1)cout<<"X";/指数等于一 elsecout<<"X^"< } if(q->coe==-1)系数为-1的特殊情况情况 { if(! q->exp)cout<<"-1";//指数不存在 elseif(q->exp==1)cout<<"-X";//指数等于一 elsecout<<"-X^"< } } q=q->next;//当前指针指向下一结点 flag++;//项序数自加1 } cout< } 两个多项式的加法。 intcompare(Polyna,Polynb)//对两个多项式的系数或项数进行比较 { if(a&&b){//两个多项式都存在 if(! b||a->exp>b->exp)return1;当b多项式不存在或者a多项式的指数大于b的的时候,返回1 elseif(! a||a->exp elsereturn0;//其他情况返回0 } elseif(! a&&b)return-1;//a多项式已空,但b多项式非空 elsereturn1;//b多项式已空,但a多项式非空 } PolynAddPolyn(Polynpa,Polynpb) { Polynqa=pa->next; Polynqb=pb->next; Polynheadc,hc,qc; hc=newPolynomial;//建立一个新的结点 hc->next=NULL; headc=hc; while(qa||qb){ qc=newPolynomial;//新建一个结点 switch(compare(qa,qb)){//调用compare函数对两个多项式进行比较 case1: //a多项式的指数大于b的 { qc->coe=qa->coe; qc->exp=qa->exp; qa=qa->next; break; } case0: //有同类项则合并 { qc->coe=qa->coe+qb->coe; qc->exp=qa->exp; qa=qa->next; qb=qb->next; break; } case-1: a多项式的指数小于b的 { qc->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; } elsedeleteqc;//当相加系数为0时,释放该结点 } returnheadc; } 两个多项式的减法。 两个多项式的减法是建立在加法的的基础上,对要减的多项式的系数求反,接着调用AddPolyn()函数对处理后的多项式相加即两个多项式的相减 PolynSubtractPolyn(Polynpa,Polynpb) { Polynh=pb; Polynp=pb->next;//新建一个结点作为pb的后继结点 Polynpd; 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; returnpd; } 多项式求值函数。 当中运用到了C语言中的数学函数: pow。 其功能为计算x的y次幂,所在头文件: math.h 。 floatValuePolyn(Polynhead,floatx) { Polynp; p=head->next; floatresult=0; while(p! =NULL)//当前结点信息存在时,对其求值并累加到前驱结点的值 { result+=(p->coe)*(float)pow(x,p->exp); p=p->next; } returnresult; } 两个多项式的乘法 PolynMultiplyPolyn(Polynpa,Polynpb) { Polynhf,pf;// Polynqa=pa->next;//新建一个结点作为pa的后继结点 Polynqb=pb->next;//新建一个结点作为pb的后继结点 hf=newPolynomial; hf->next=NULL; while(qa)//使用while循环,使得多项式的每项得以运算 { qb=pb->next; while(qb) { pf=newPolynomial; pf->coe=qa->coe*qb->coe; pf->exp=qa->exp+qb->exp; Insert(pf,hf);//调用插入函数,将新的结点插入到新建链表中,并合并同类项 qb=qb->next; } qa=qa->next; } returnhf;//返回所得链表的头指针 } 2.6测试 测试软件: MicrosoftVisualC++6.0 测试的数据: (1)A+BA=3x14-8x8+6x2+2B=2x10+4x8+-6x2 (2)A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7 (3)A+BA=x3+x1B=-x3-x1 (4)A+BA=0B=x7+x5+x3+x1 (5)A-BA=100x100+50x50+20x20+xB=10x100+10x50+10x20+x (6)A*BA=5x6+4x5+3x4B=6x6+5x5 (7)A=5x6+4x5+3x4X=2 测试过程与结果: (1)A=3x14-8x8+6x2+2 B=2x10+4x8+-6x2 A+B=3x14+2x10-4x8+2 (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-x1 A+B=0 (4)A=0 B=x7+x5+x3+x1 A+B=x7+x5+x3+x (5)A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x A-B=90x100+40x50+10x20 (6)A=5x6+4x5+3x4 B=6x6+5x5 A*B=30x12+49x11+38x10+15x9 (7)A=5x6+4x5+3x4 X=2 A=496 3总结 本次课程设计中,通过对一元多项式计算问题的解决,不仅让我对《数据结构》学到的知识得到温习,而且让我在实践的过程中队所学知识得到了巩固。 实验设计的过程中,坚持“学以致用”的原则,让我充分利用所学的理论知识进行相对复杂的应用设计,以进一步提高综合能力和创新实践能力,让我在课堂教学中所得进一步升华。 最后我要衷心的感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利! 参考文献 [1]王挺,周会平,贾丽丽,许锡山.C++程序设计[M].北京: 清华大学出版社,2005 [2]严蔚敏,吴伟民.数据结构(C语言版)[M].北京: 清华大学出版社,2005. [3]李根强.数据结构(C++版)习题解答及实训指导[M].北京: 中国水利水电出版社,2009. 附录A源代码 #include #include #include typedefstructPolynomial{ intcoe; intexp; structPolynomial*next; }*Polyn,Polynomial; voidInsert(Polynp,Polynh) { if(p->coe==0)deletep; else{ Polynq1,q2; q1=h;q2=h->next; while(q2&&p->exp { q1=q2; q2=q2->next; } if(q2&&p->exp==q2->exp) { q2->coe+=p->coe; deletep; if(! q2->coe) { q1->next=q2->next; deleteq2; } } else { p->next=q2; q1->next=p; } } } PolynCreatePolyn(Polynhead,intm) { inti; Polynp; p=head=newPolynomial; head->next=NULL; for(i=0;i p=newPolynomial;; cout<<"请输入第"< "; cin>>p->coe; cout<<"指数: "; cin>>p->exp; Insert(p,head); } returnhead; } voidDestroyPolyn(Polynp) { Polynt; while(p! =NULL) { t=p; p=p->next; deletet; } } voidPrintPolyn(PolynP) { Polynq=P->next; intflag=1; if(! q) { cout<<"0"; cout< return; } while(q) { if(q->coe>0&&flag! =1)cout<<"+"; if(q->coe! =1&&q->coe! =-1) { cout< if(q->exp==1)cout<<"X"; elseif(q->exp)cout<<"X^"< } else { if(q->coe==1) { if(! q->exp)cout<<"1"; elseif(q->exp==1)cout<<"X"; elsecout<<"X^"< } if(q->coe==-1) { if(! q->exp)cout<<"-1"; elseif(q->exp==1)cout<<"-X"; elsecout<<"-X^"< } } q=q->next; flag++; } cout< } intcompare(Polyna,Polynb) { if(a&&b) { if(! b||a->exp>b->exp)return1; elseif(! a||a->exp elsereturn0; } elseif(! a&&b)return-1; elsereturn1; } PolynAddPolyn(Poly
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+ 一元 多项式 计算 问题 课程设计 说明书