一元多项式计算问题课程设计.docx
- 文档编号:14826404
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:24
- 大小:58.76KB
一元多项式计算问题课程设计.docx
《一元多项式计算问题课程设计.docx》由会员分享,可在线阅读,更多相关《一元多项式计算问题课程设计.docx(24页珍藏版)》请在冰点文库上搜索。
一元多项式计算问题课程设计
长沙学院
课程设计说明书
题目
一元多项式计算问题
系(部)
计算机系
专业(班级)
10级软件D班
姓名
向栋良
学号
2010022D08
指导教师
邓旭东
起止日期
2011.9.4-2011.9.8
课程设计任务书
课程名称:
数据结构与算法
设计题目:
一元多项式计算问题
已知技术参数和设计要求:
问题描述:
设计一个稀疏多项式简单计算器
基本要求:
(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课时
工作计划:
日期
节次
地点
设计方式
9月4日(周日)
1-4
科1408
讲授内容
9月4日(周日)
5-8
科1608
答疑
9月5日(周一)
1-4
科1408
上机调试
9月5日(周一)
5-8
科1608
答疑
9月6日(周二)
1-4
科1408
上机调试
9月6日(周二)
5-8
科1608
答疑
9月7日(周三)
1-4
科1408
上机调试
9月7日(周三)
5-8
科1608
答疑
9月8日(周四)
1-4
科1608
答疑
9月8日(周四)
5-8
科1408
答辩
指导教师签名:
日期:
教研室主任签名:
日期:
系主任签名:
日期:
长沙学院课程设计鉴定表
姓名
徐皖宁
学号
2010022509
专业
软件工程
班级
软件五班
设计题目
课程设计安排
指导教师
杜红燕
指导教师意见:
评定等级:
教师签名:
日期:
答辩小组意见:
评定等级:
答辩小组长签名:
日期:
教研室意见:
教研室主任签名:
日期:
系(部)意见:
系主任签名:
日期:
说明
课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类;
摘要
本文是关于一个一元稀疏多项式计算器的问题。
一元稀疏多项式计算内容包括输入并建立多项式,多项式相加,多项式相减,以及其输出多项式。
本程序运用面向对象的设计方法,使用C++语言,利用microsoftvisualC++6.0开发工具,还有数据结构中学到的链式存储架构,存储一元多项式,从而实现程序的基本功能,在程序中定义了各种类型的运算模块,通过主程序的调用来完成它们之间的配合,从而使程序正确运行。
关键词:
数据结构;一元多项式;链表;C++语言
第一章需求分析
1.1输入的形式和输入值的范围:
输入是从键盘输入的,输入的内容为多项式的系数和指数,数为任意的整数,指数为大于等于0的整数
1.2输出的形式
从屏幕输出,显示用户输入的多项式,并显示多项式加减以后的多项式的值。
1.3程序所能达到的功能
a:
输入并建立多项式;
b:
输出多项式,输出形式为整数序列:
n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
c:
多项式a和b相加,建立多项式a+b;
d:
多项式a和b相减,建立多项式a-b;
e:
多项式的输出形式为类数学表达式。
系数值为1的非零项的输出形式中略去系数1。
而-1x的输出形式为-x。
第二章概要设计
2.1设计思路
A:
数据结构的选用
为了实现任意多项式的加法,减法,因此选择单链表的结构体,它有一个系数,指数,下一个指针3个元属;
B:
多项式的输入
采用头插法的方式,输入多项式中一个项的系数和指数,就产生一个新的节点,建立起它的右指针,并用头节点指向它;为了判断一个多项式是否输入结束,定义一个结束标志,当输入非0时就继续,当输入0时,就结束一个多项式的输入;
C:
2个多项式的加法
它从2个多项式的头部开始,2个多项式的某一项都不为空时,如果指数相等的话,系数就应该相加;相加的和不为0的话,用头插法建立一个新的节点。
p的系数小于q的系数的话,就应该复制q接点到多项式中。
p的系数大于q的系数的话,就应该复制p接点到多项式中。
当第2个多项式空,第1个数不为空时,将第一个数剩下的全用新节点产生。
当第1个多项式空,第1个数不为空时,将第2个数剩下的全用新节点产生
D:
2个多项式的减法
它从2个多项式的头部开始,2个多项式的某一项都不为空时,如果指数相等的话,系数就应该相减;相加的和不为0的话,用头插法建立一个新的节点。
p的系数小于q的系数的话,就应该复制q接点到多项式中。
p的系数大于q的系数的话,就应该复制p接点到多项式中,并且建立的接点的系数为原来的相反数;当第2个多项式空,第1个数不为空时,将第一个数剩下的全用新节点产生。
当第1个多项式空,第1个数不为空时,将第2个数剩下的全用新节点产生,并且建立的接点的系数为原来的相反数。
第三章详细设计
3.1、创建一个结点,表示多项式的一项
pnodecreate(char*c,inti,intj){
if(j
inta=0,b=0,flag=0;//a系数,b指数,flag指数正负记录。
if(!
isnum(c[i]))
a=1;
else
while(isnum(c[i])&&i<=j){
a=a*10+c[i]-'0';
i++;
}//跳过系数与指数间非数字字符。
while(!
isnum(c[i])&&i<=j)
{
flag=1;
i++;
}//处理指数。
if(i>j&&flag==1)b=1;
else{
if(c[i-1]=='-'&&c[i-2]=='^')flag=2;//指数是负数情况记录。
while(isnum(c[i])&&i<=j){
b=b*10+c[i]-'0';
i++;
}
}
if(flag==2)b=-b;//指数是负数情况处理。
pnodep;
p=(pnode)malloc(sizeof(node));
p->x=a;
p->z=b;
returnp;
}//创建一个结点,表示多项式的一项。
把"12X^3"这样字符串转化成一个只有系数、指数、后继的结构体。
3.2、链式存储多项式
pnodecreate_duo(char*c,intm){
if(c[m]=='\0')returnNULL;
inti,j;
pnodep,q,*t;
i=m;
if(c[i]=='+'||c[i]=='-')i++;
j=i;
while(c[j]!
='\0'&&c[j]!
='+'&&(c[j]!
='-'||c[j-1]=='^')){
j++;
}//移动到多项式字符串的从下标m起第一项末。
if(c[i]!
='0')
{
p=create(c,i,j-1);
if(i>0&&c[i-1]=='-')p->x=-(p->x);
q=create_duo(c,j);//处理下一项
if(q==NULL)
p->next=q;
elseif(q&&q->z
p->next=q;
elseif(q){
t=&q;
while(*t!
=NULL)t=&(*t)->next;
*t=(pnode)malloc(sizeof(node));
*t=p;
(*t)->next=NULL;
p=q;
}
returnp;
}
else
returncreate_duo(c,j);//系数为0项,不建立,跳过。
}//把一元多项式的字符串用链式存储。
3.3、多项式的计算
pnodeplus(pnodep,pnodeq){
pnodeP,H,t,m,n;
m=p;
n=q;
H=P=(pnode)malloc(sizeof(node));
while(m!
=NULL&&n!
=NULL){
t=(pnode)malloc(sizeof(node));
if(m->z>n->z){
t->x=m->x;
t->z=m->z;
m=m->next;
}
else
if(m->z==n->z){
if(m->x==-(n->x))
{
m=m->next;
n=n->next;
continue;
}//指数相同,系数相反,情况处理。
t->x=m->x+n->x;
t->z=n->z;
m=m->next;
n=n->next;
}
else{
t->x=n->x;
t->z=n->z;
n=n->next;
}
P->next=t;
P=P->next;
}
while(m!
=NULL){
t=(pnode)malloc(sizeof(node));
t->x=m->x;
t->z=m->z;
m=m->next;
P->next=t;
P=P->next;
}
while(n!
=NULL){
t=(pnode)malloc(sizeof(node));
t->x=n->x;
t->z=n->z;
n=n->next;
P->next=t;
P=P->next;
}
P->next=NULL;
P=H;
H=H->next;
free(P);
returnH;
}//两个一元多项式的相加。
pnodeminus(pnodep,pnodeq)
{
if(q==NULL)returnp;
pnodet,h,g,q1;
t=q;
h=(pnode)malloc(sizeof(node));
h->x=-(t->x);
h->z=t->z;
t=t->next;
q1=h;
g=h;
while(t!
=NULL){
h=(pnode)malloc(sizeof(node));
h->x=-(t->x);
h->z=t->z;
g->next=h;
g=g->next;
t=t->next;
}
g->next=NULL;
if(p==NULL)returnq1;
return(plus(p,q1));
}//两个一元多项式的差
3.4、释放结点
voidfree_pnode(pnodep)
{
pnodet;
while(p!
=NULL)
{
t=p;
p=p->next;
free(t);
}
第四章运行界面
4.1、输入界面如图4-1:
图4-1
4.2、显示输出数据如图4-2:
图4-2
4.3、用户选择功能界面如图4-3
图4-3
4.4、各功能运行界面如图4-4:
图4-4
第五章总结
C++语言功能强,使用灵活,可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件
通过这次课程设计我觉得我们学习《数据结构》的方法存在一定的弊端,《数据结构》的效果直接影响到我们对其它专业课的学习和今后业务的成长。
我觉得我们对于《数据结构》的学习不仅包括理论部分的学习,还要让我们勤动手,多实践。
最后我要衷心的感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利!
参考文献
[1]王挺.C++程序设计.北京:
清华大学出版社,2005.1.
[2]严蔚敏.数据结构:
C语言版.北京:
清华大学出版社,2007.
附录:
源代码;
#include
#include
#include
#defineN999
typedefstructnode{
intx,z;//x系数,z指数
structnode*next;
}*pnode;
intisnum(charc)
{
if(c>='0'&&c<='9')return1;
elsereturn0;
}//判断用
pnodecreate(char*c,inti,intj){
if(j
inta=0,b=0,flag=0;//a系数,b指数,flag指数正负记录。
if(!
isnum(c[i]))
a=1;
else
while(isnum(c[i])&&i<=j){
a=a*10+c[i]-'0';
i++;
}//跳过系数与指数间非数字字符。
while(!
isnum(c[i])&&i<=j)
{
flag=1;
i++;
}//处理指数。
if(i>j&&flag==1)b=1;
else{
if(c[i-1]=='-'&&c[i-2]=='^')flag=2;//指数是负数情况记录。
while(isnum(c[i])&&i<=j){
b=b*10+c[i]-'0';
i++;
}
}
if(flag==2)b=-b;//指数是负数情况处理。
pnodep;
p=(pnode)malloc(sizeof(node));
p->x=a;
p->z=b;
returnp;
}//创建一个结点,表示多项式的一项。
把"12X^3"这样字符串转化成一个只有系数、指数、后继的结构体。
pnodecreate_duo(char*c,intm){
if(c[m]=='\0')returnNULL;
inti,j;
pnodep,q,*t;
i=m;
if(c[i]=='+'||c[i]=='-')i++;
j=i;
while(c[j]!
='\0'&&c[j]!
='+'&&(c[j]!
='-'||c[j-1]=='^')){
j++;
}//移动到多项式字符串的从下标m起第一项末。
if(c[i]!
='0')
{
p=create(c,i,j-1);
if(i>0&&c[i-1]=='-')p->x=-(p->x);
q=create_duo(c,j);//处理下一项
if(q==NULL)
p->next=q;
elseif(q&&q->z
p->next=q;
elseif(q){
t=&q;
while(*t!
=NULL)t=&(*t)->next;
*t=(pnode)malloc(sizeof(node));
*t=p;
(*t)->next=NULL;
p=q;
}
returnp;
}
else
returncreate_duo(c,j);//系数为0项,不建立,跳过。
}//把一元多项式的字符串用链式存储。
pnodeplus(pnodep,pnodeq){
pnodeP,H,t,m,n;
m=p;
n=q;
H=P=(pnode)malloc(sizeof(node));
while(m!
=NULL&&n!
=NULL){
t=(pnode)malloc(sizeof(node));
if(m->z>n->z){
t->x=m->x;
t->z=m->z;
m=m->next;
}
else
if(m->z==n->z){
if(m->x==-(n->x))
{
m=m->next;
n=n->next;
continue;
}//指数相同,系数相反,情况处理。
t->x=m->x+n->x;
t->z=n->z;
m=m->next;
n=n->next;
}
else{
t->x=n->x;
t->z=n->z;
n=n->next;
}
P->next=t;
P=P->next;
}
while(m!
=NULL){
t=(pnode)malloc(sizeof(node));
t->x=m->x;
t->z=m->z;
m=m->next;
P->next=t;
P=P->next;
}
while(n!
=NULL){
t=(pnode)malloc(sizeof(node));
t->x=n->x;
t->z=n->z;
n=n->next;
P->next=t;
P=P->next;
}
P->next=NULL;
P=H;
H=H->next;
free(P);
returnH;
}//两个一元多项式的相加。
pnodeminus(pnodep,pnodeq)
{
if(q==NULL)returnp;
pnodet,h,g,q1;
t=q;
h=(pnode)malloc(sizeof(node));
h->x=-(t->x);
h->z=t->z;
t=t->next;
q1=h;
g=h;
while(t!
=NULL){
h=(pnode)malloc(sizeof(node));
h->x=-(t->x);
h->z=t->z;
g->next=h;
g=g->next;
t=t->next;
}
g->next=NULL;
if(p==NULL)returnq1;
return(plus(p,q1));
}//两个一元多项式的差。
voidprint(pnodep){
if(p==NULL){
cout<<"0"< return; } while(p! =NULL){ if(p->x==-1&&p->z! =0)cout<<"-"; elseif(p->x! =1||p->z==0) cout< if(p->z) { cout<<"X"; if(p->z! =1) cout<<"^"< } p=p->next; if(p! =NULL&&p->x>0)cout<<"+"; } cout< }//输出链式存储多项式。 voidmain() { cout<<"********************************"< cout<<"****一元多项式的计算(和差积)****"< cout<<"********************************"< charch1[N];//="30X^45-X-9"; charch2[N];//="-4X^3-2X+1"; intn=1; pnodep1,p2; cout<<"输入第一个多项式,项按升序或降序排列(形式如.22X^31+X^22+X-1): \n"; cin>>ch1; inti=0; while(ch1[i]){ if(ch1[i]<='*'||ch1[i]==','||(ch1[i]>='.'&&ch1[i]<='/')||(ch1[i]>=': '&&ch1[i]<='W')||ch1[i]=='Y'||ch1[i]=='Z'||(ch1[i]>='_'&&ch1[i]<='w')||ch1[i]>='y'){ cout<<"删除错误字符"< intj=i; while(ch1[j]){ ch1[j]=ch1[j+1]; j++; } i--; }i++; }//删除错误字符 p1=create_duo(ch1,0); cout<<"输入第二个多项式,项按升序或降序排列(形式如.22X^31+X^24+X-1): \n"; cin>>ch2; i=0; while(ch2[i]){ if(ch2[i]<='*'||ch2[i]==','||(ch2[i]>='.'&&ch2[i]<='/')||(ch2[i]>=': '&&ch2[i]<='W')||ch2[i]=='Y'||ch2[i]=='Z'||(ch2[i]>='_'&&ch2[i]<='w')||ch2[i]>='y'){ cout<<"删除错误字符"< intj=i; while(ch2[j]){ ch2[j]=ch2[j+1]; j++; }i--; }i++; }//删除错误字符 p2=create_duo(ch2,0); cout<<"多项式p1: "; print(p1); cout<<"多项式p2: "; print(p2); cout<<"******************************************"< cout<<"*********用户选择************"< cout<<"*********************"< cout<<"*********1.两多项式和************"< cout<<"*********************"< cout<<"*********2.两多项式差************"< cout<<"*********************"< cout<<"*********0.退出************"< cout<<"*********************"< cout<<"******************************************"< while(n) {cout<<"请输入你的选择: "
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一元 多项式 计算 问题 课程设计
![提示](https://static.bingdoc.com/images/bang_tan.gif)