一元多项式的加法减法乘法的实现数据结构课程设计.docx
- 文档编号:10478542
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:36
- 大小:360.63KB
一元多项式的加法减法乘法的实现数据结构课程设计.docx
《一元多项式的加法减法乘法的实现数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《一元多项式的加法减法乘法的实现数据结构课程设计.docx(36页珍藏版)》请在冰点文库上搜索。
一元多项式的加法减法乘法的实现数据结构课程设计
课程设计(论文)
题目名称一元多项式的加法、减法、乘法的实现
课程名称数据结构课程设计
学生姓名
学号
系、专业信息工程系、通信工程
指导教师
设有一元多项式Am(x)和Bn(x):
Am(x)=A0+A1x+A2x2+A3x3+…+Amxm
Bn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn
分别采用顺序和链式存储结构实现:
M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。
并要结果M(x)中无重复阶项和无零系数项,且输出结果用升幂和降幂两种排列情况。
关键词:
一元多项式;顺序存储;链式存储;升幂;降幂
1问题描述
设有一元多项式Am(x)和Bn(x):
Am(x)=A0+A1x+A2x2+A3x3+…+Amxm
Bn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn
实现M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)、M(x)=Am(x)×Bn(x)。
要求:
(1)分别采用顺序和链式存储结构实现;
(2)结果M(x)中无重复阶项和无零系数项;
(3)要求输出结果用升幂和降幂两种排列情况。
2需求分析
(1)用一维数组cp1[n1]和cp2[n2]存储一元多项式Am(x)和Bn(x)的系数,用for循环来计算顺序结构中的加法、减法、乘法的结果。
(2)用指针*d,*q来存储一元多项式的内容,再利用指针计算动态链表下一元多项式的加法、减法、乘法的结果。
(3)在用降幂升幂两种排列输出结果时,用expn和coef表示一元多项式的系数和指数,输出两种排列结果。
3概要设计
3.1抽象数据类型定义
(1)顺序存储结构的抽象数据类型定义
intn1,n2;
利用一维数组cp1[n1]和cp2[n2]存储多项式的系数
基本操作:
voidcreatpoly1(double*a,intpt)
操作结果:
建立顺序结构
voidaddpoly(double*a,double*b,double*c)
初始条件:
一维数组cp1[n1]和cp2[n2]已建立
操作结果:
顺序结构相加
voidsubpoly(double*a,double*b,double*c)
初始条件:
一维数组cp1[n1]和cp2[n2]已建立
操作结果:
顺序结构相减
voidmulpoly(double*a,double*b,double*c)
初始条件:
一维数组cp1[n1]和cp2[n2]已建立
操作结果:
顺序结构相乘
voidansprint(double*a,intn)
初始条件:
一维数组cp1[n1]和cp2[n2]已建立
操作结果:
选用升幂或降幂排列打印出结果
(2)动态链表结构的抽象数据类型定义
typedefstructp_pol{doublecoef;intexpn;p_pol*next;}MPP;
基本操作:
MPP*creatlink(MPP*p,intn,intpt)
初始条件:
动态链表已定义
操作结果:
构造动态链表结构
voidaddlink(MPP*p1,MPP*p2,MPP*p3)
初始条件:
动态链表已定义
操作结果:
动态链表相加
voidsublink(MPP*p1,MPP*p2,MPP*p3)
初始条件:
动态链表已定义
操作结果:
动态链表相减
voidmullink(MPP*p1,MPP*p2,MPP*p3)
初始条件:
动态链表已定义
操作结果:
动态链表相乘
voidprintlink(MPP*p)
初始条件:
动态链表已定义
操作结果:
选用升幂或降幂排列打印结果
voiddeletelink(MPP*p)
初始条件:
动态链表已定义
操作结果:
删除结点释放内存
3.2模块划分
本程序包括三个模块:
(1)主程序模块
voidmain()
{
输入第一个多项式的项数;
分别输入各项的系数和指数;
输入第二个多项式的项数;
分别输入各项的系数和指数;
请选择实现结构:
1顺序结构2动态链表结构
选择操作方式:
1相加2相减3相乘
}
(2)顺序存储结构模块——实现顺序存储结构的抽象数据类型
(3)动态链表结构模块——实现动态链表结构的抽象数据类型
4详细设计
4.1数据类型的定义
(1)顺序存储结构类型
intn1,n2;
intcp1[n1];intcp2[n2]
(2)动态链表结构类型
#defineINFEX10000
#defineINFCO10000
doublecoef;
intexpn;
p_pol*next;
4.2主要模块的算法描述
该题可画三个流程图:
(1)一元多项式的计算主流程图;
(2)顺序存储结构流程图;(3)动态链表结构流程图。
流程图如下:
(1)一元多项式的计算主流程图:
如图4.1所示
图4.1一元多项式的计算主流程图
(2)顺序存储结构流程图
如图4.2所示
图4.2顺序存储结构流程图
(3)动态链表结构流程图
如图4.3所示
图4.3动态链表结构流程图
5测试分析
测试数据及结果如下:
6课程设计总结
通过这次课程设计使我了解到编写的程序不但要拿来使用,还要让人看得懂。
所以,代码编写的风格要尽量规范,清晰。
变量要尽量少定义,结构体采用简单的。
另外,对指针的使用要小心,尽量在定义的时候就进行初始化,避免出现没有被定义的指针。
该程序主要实现了顺序结构、动态链表结构下的一元多项式的加法、减法、乘法等运算功能。
同时,也应用了升幂和降幂的输出方法,输出程序的结果。
虽然此次的程序不是很完备,但是总体还是一个比较能体现数据结构知识点的程序了,当然只是相对于我这个初学者来说。
这次设计中我发现了自己的许多不足,如对指针的机制掌握的还不是很透彻,有的时候会出现指针指向错误以及空指针的错误,还有不能很好地分析自己算法地复杂度以及不能很好地使用控制机制使自己的程序流畅地运行。
因此,在今后我会更加努力地。
在此我要非常感谢的是我的指导老师黄同成老师,感谢老师的细心认真的辅导,让我对数据结构这门课程有了更多的了解,也让我对这门课程产生了浓厚的兴趣。
在这次课程设计中我又进一步地了解了数据结构中算法的核心思想的重要性,懂得了一个程序地好坏关键在于算法是否优秀,一个好的优秀的算法可以使我们的程序更加完善,安全性更高以及有更高的效率。
参考文献
[1]黄同成,黄俊民,董建寅.数据结构[M].北京:
中国电力出版社,2008
[2]董建寅,黄俊民,黄同成.数据结构实验指导与题解[M].北京:
中国电力出版社,2008
[3]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:
清华大学出版社,2002
[4]刘振鹏,张晓莉,郝杰.数据结构[M].北京:
中国铁道出版社,2003
附录(源程序清单)
#include
#include
#include
#defineINFEX10000
#defineINFCO10000
typedefstructpol
{
doublecoef;
intexpn;
}MPOL;
MPOL*cp1,*cp2;
//-----顺序结构部分-----
intn1,n2;
voidansprint(double*a,intn)//打印出结果
{
intchoose;
puts("请选择输出顺序:
1升幂2降幂:
");
scanf("%d",&choose);
inti,num;
if(choose!
=2)//升幂打印
{
if(choose!
=1)
printf("没有%d选项,系统将默认输出升序:
\nM(X)=",choose);
else
printf("M(X)=");
num=0;
for(i=0;i<=n;i++)
if(fabs(a[i])>1e-8)
{
if(num++)
putchar('+');
printf("%lfX^%d",a[i],i);
}
}
else//降幂打印
{
printf("M(X)=");
num=0;
for(i=n;i>=0;i--)
if(fabs(a[i])>1e-8)
{
if(num++)
putchar('+');
printf("%lfX^%d",a[i],i);
}
}
putchar(10);
}
voidaddpoly(double*a,double*b,double*c)//顺序结构相加
{
intmin=(cp1[n1-1].expn>cp2[n2-1].expn?
cp2[n2-1].expn:
cp1[n1-1].expn);
intmax=(cp1[n1-1].expn cp2[n2-1].expn: cp1[n1-1].expn); inti; for(i=0;i<=min;i++) c[i]=a[i]+b[i]; for(;i<=max;i++) if(cp1[n1-1].expn>cp2[n2-1].expn) c[i]=a[i]; else c[i]=b[i]; puts("相加结果为: "); ansprint(c,max); } voidsubpoly(double*a,double*b,double*c)//顺序结构相减 { intmin=(cp1[n1-1].expn>cp2[n2-1].expn? cp2[n2-1].expn: cp1[n1-1].expn); intmax=(cp1[n1-1].expn cp2[n2-1].expn: cp1[n1-1].expn); inti; for(i=0;i<=min;i++) c[i]=a[i]-b[i]; for(;i<=max;i++) if(cp1[n1-1].expn>cp2[n2-1].expn) c[i]=a[i]; else c[i]=-b[i]; puts("相减结果为: "); ansprint(c,max); } voidmulpoly(double*a,double*b,double*c)//顺序结构相乘 { intmax=cp1[n1-1].expn+cp2[n2-1].expn+2; inti,j; for(i=0;i c[i]=0; for(i=0;i<=cp1[n1-1].expn;i++) for(j=0;j<=cp2[n2-1].expn;j++) c[i+j]+=a[i]*b[j]; puts("相乘结果为: "); ansprint(c,max-1); } voidcreatpoly1(double*a,intpt)//建立顺序结构 { inti; if(pt==1) { for(i=0;i<=cp1[n1-1].expn;i++) a[i]=0; for(i=0;i a[cp1[i].expn]=cp1[i].coef; } else { for(i=0;i<=cp2[n2-1].expn;i++) a[i]=0; for(i=0;i a[cp2[i].expn]=cp2[i].coef; } } //-----动态链式结构部分----- typedefstructp_pol//结点定义 { doublecoef; intexpn; p_pol*next; }MPP; MPP*creatlink(MPP*p,intn,intpt)//构造动态链表结构 { MPP*d,*q; inti; q=(MPP*)malloc(sizeof(MPP)); if(q==NULL) exit(0); q->next=NULL; q->coef=INFCO; q->expn=-INFEX; p=q; for(i=0;i { d=(MPP*)malloc(sizeof(MPP)); if(d==NULL) exit(0); d->next=NULL; if(pt==1) { d->coef=cp1[i].coef; d->expn=cp1[i].expn; } else { d->coef=cp2[i].coef; d->expn=cp2[i].expn; } q->next=d; q=d; } returnp; } voidprintlink1(MPP*p)//打印结果Am(x) { intnum=0,i=0,choose,count; puts("请选择输出顺序: 1升幂2降幂: "); scanf("%d",&choose); MPP*tp=p; p=p->next; while(p! =NULL) { num++; p=p->next; } MPOL*d=newMPOL[num]; p=tp->next; while(p! =NULL) { d[i].coef=p->coef; d[i].expn=p->expn; i++; p=p->next; } if(choose==2)//降幂打印 { count=0; printf("Am(X)="); for(i=num-1;i>=0;i--) { if(count++) putchar('+'); printf("%lfX^%d",d[i].coef,d[i].expn); } } else//升幂打印 { if(choose! =1) printf("没有%d选项,系统将默认输出升序: \nAm(X)=",choose); else printf("Am(X)="); for(i=0;i { if(count++) putchar('+'); printf("%lfX^%d",d[i].coef,d[i].expn); } } putchar(10); } voidprintlink2(MPP*p)//打印结果Bn(x) { intnum=0,i=0,choose,count; puts("请选择输出顺序: 1升幂2降幂: "); scanf("%d",&choose); MPP*tp=p; p=p->next; while(p! =NULL) { num++; p=p->next; } MPOL*d=newMPOL[num]; p=tp->next; while(p! =NULL) { d[i].coef=p->coef; d[i].expn=p->expn; i++; p=p->next; } if(choose==2)//降幂打印 { count=0; printf("Bn(X)="); for(i=num-1;i>=0;i--) { if(count++) putchar('+'); printf("%lfX^%d",d[i].coef,d[i].expn); } } else//升幂打印 { if(choose! =1) printf("没有%d选项,系统将默认输出升序: \nBn(X)=",choose); else printf("Bn(X)="); for(i=0;i { if(count++) putchar('+'); printf("%lfX^%d",d[i].coef,d[i].expn); } } putchar(10); } voidprintlink(MPP*p)//打印结果M(x) { intnum=0,i=0,choose,count; puts("请选择输出顺序: 1升幂2降幂: "); scanf("%d",&choose); MPP*tp=p; p=p->next; while(p! =NULL) { num++; p=p->next; } MPOL*d=newMPOL[num]; p=tp->next; while(p! =NULL) { d[i].coef=p->coef; d[i].expn=p->expn; i++; p=p->next; } if(choose==2)//降幂打印 { count=0; printf("M(X)="); for(i=num-1;i>=0;i--) { if(count++) putchar('+'); printf("%lfX^%d",d[i].coef,d[i].expn); } } else//升幂打印 { if(choose! =1) printf("没有%d选项,系统将默认输出升序: \nM(X)=",choose); else printf("M(X)="); for(i=0;i { if(count++) putchar('+'); printf("%lfX^%d",d[i].coef,d[i].expn); } } putchar(10); } voidaddlink(MPP*p1,MPP*p2,MPP*p3)//动态链表相加 { MPP*p,*head; p=(MPP*)malloc(sizeof(MPP)); if(p==NULL) exit(0); p->coef=INFCO; p->expn=-INFEX; p->next=NULL; head=p3=p; p1=p1->next; p2=p2->next; while(p1! =NULL||p2! =NULL) { if(fabs(head->coef)>1e-8) { p=(MPP*)malloc(sizeof(MPP)); if(p==NULL) exit(0); head->next=p; head=p; head->next=NULL; } if(p1==NULL) { head->coef=p2->coef; head->expn=p2->expn; p2=p2->next; continue; } if(p2==NULL) { head->coef=p1->coef; head->expn=p1->expn; p1=p1->next; continue; } if(p1->expn==p2->expn) { head->coef=p1->coef+p2->coef; head->expn=p1->expn; p1=p1->next; p2=p2->next; } elseif(p1->expn { head->coef=p1->coef; head->expn=p1->expn; p1=p1->next; } else { head->coef=p2->coef; head->expn=p2->expn; p2=p2->next; } } puts("相加结果为: "); printlink(p3); } voidsublink(MPP*p1,MPP*p2,MPP*p3)//动态链表相减 { MPP*p,*head; p=(MPP*)malloc(sizeof(MPP)); if(p==NULL) exit(0); p->coef=INFCO; p->expn=-INFEX; p->next=NULL; head=p3=p; p1=p1->next; p2=p2->next; while(p1! =NULL||p2! =NULL) { if(fabs(head->coef)>1e-8) { p=(MPP*)malloc(sizeof(MPP)); if(p==NULL) exit(0); head->next=p; head=p; head->next=NULL; } if(p1==NULL) { head->coef=-p2->coef; head->expn=p2->expn; p2=p2->next; continue; } if(p2==NULL) { head->coef=p1->coef; head->expn=p1->expn; p1=p1->next; continue; } if(p1->expn==p2->expn) { head->coef=p1->coef-p2->coef; head->expn=p1->expn; p1=p1->next; p2=p2->next; } elseif(p1->expn { head->coef=p1->coef; head->expn=p1->expn; p1=p1->next; } else { head->coef=-p2->coef; head->expn=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一元 多项式 加法 减法 乘法 实现 数据结构 课程设计