数据结构课程设计一元多项式的加法与减法(共29页).docx

精选优质文档-倾情为你奉上课程设计(论文)题 目 名 称 一元多项式的加法、减法、乘法的实现 课 程 名 称 数据结构课程设计 学 生 姓 名 郭晗 学 号 系 、专 业 信息工程系、信息类 指 导 教 师 黄同成 2012年 12 月 23 日摘 要设有一元多项式Am(x)和Bn(x)：Am(x)=A0+A1x+A2x2+A3x3+ +AmxmBn(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+ +AmxmBn(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）用一维数组cp1n1和cp2n2存储一元多项式Am(x)和Bn(x)的系数，用for循环来计算顺序结构中的加法减法乘法的结果。（2）用指针*d,*q来存储一元多项式的内容，再利用指针计算动态链表下一元多项式的加法减法乘法的结果。（3）在用降幂升幂两种排列输出结果时，用expn和coef表示一元多项式的系数和指数，输出两种排列结果。3 概要设计31抽象数据类型定义（1）顺序存储结构的抽象数据类型定义int n1,n2;利用一维数组cp1n1和cp2n2存储多项式的系数基本操作：void creatpoly1(double *a,int pt)操作结果：建立顺序结构void addpoly(double *a,double *b,double *c)初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相加void subpoly(double *a,double *b,double *c)初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相减 void mulpoly(double *a,double *b,double *c) 初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相乘void ansprint(double *a,int n) 初始条件: 一维数组cp1n1和cp2n2已建立操作结果：选用升幂或降幂排列打印出结果（2）动态链表结构的抽象数据类型定义typedef struct p_pol double coef; int expn; p_pol *next；MPP；基本操作：MPP * creatlink(MPP *p,int n,int pt)初始条件：动态链表已定义操作结果：构造动态链表结构void addlink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相加void sublink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相减void mullink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相乘void printlink(MPP * p)初始条件：动态链表已定义操作结果：选用升幂或降幂排列打印结果void deletelink(MPP *p)初始条件：动态链表已定义操作结果：删除结点释放内存32模块划分本程序包括三个模块：（1）主程序模块void main()输入第一个多项式的项数；分别输入各项的系数和指数；输入第二个多项式的项数；分别输入各项的系数和指数；请选择实现结构：1 顺序结构 2 动态链表结构选择操作方式：1 相加 2 相减 3 相乘（2）顺序存储结构模块实现顺序存储结构的抽象数据类型（3）动态链表结构模块实现动态链表结构的抽象数据类型4 详细设计41数据类型的定义（1）顺序存储结构类型int n1,n2;int cp1n1; intcp2n2（2）动态链表结构类型#define INFEX 10000#define INFCO 10000double coef;int expn;p_pol *next;42主要模块的算法描述该题可画三个流程图：（1）一元多项式的计算主流程图；（2）顺序存储结构流程图；（3）动态链表结构流程图。流程图如下：（1）一元多项式的计算主流程图：如图4.1所示为动态链表结构为顺序结构开始输入两个多项式各项的系数和选择实现结构顺序结构？是否打印输出处理后的结果选择操作方式选择打印输出方式结束图4.1一元多项式的计算主流程图（2）顺序存储结构流程图如图4.2所示减法开始顺序存储结构加法调用加法函数是否调用降幂输出函数调用升幂输出函数是否调用减法函数调用乘法函数选择打印输出顺序升幂是否打印输出处理后的结果结束图4.2顺序存储结构流程图（3）动态链表结构流程图如图4.3所示减法开始动态链表存储结构加法调用加法函数是否调用降幂输出函数调用升幂输出函数是否调用减法函数调用乘法函数选择打印输出顺序升幂是否打印输出处理后的结果结束图4.3动态链表结构流程图5 测试分析测试数据及结果如下：6 课程设计总结 从这次数据结构课程设计，我不仅学会了怎样编出一个一元多项式的加法、减法、乘法的实现，而且还深深的体会到编好一个程序是一件非常有意义的事。我觉得编程不仅需要信心，还需要耐心，更需要团队合作之心，有了这些还不够，我们应该从实践出发，并从实践得到检验，不懂就是不懂，虚心求教才是解决问题的好办法。最后我要感谢老师给了我这次编程的机会，让我知道了团队合作原来如此重要，并且感受到数据结构原来也很奇妙，编程之路有点苦，但有我们团队一起走过的痕迹，我最后发现这是甜的味道！两周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，与同学分工设计，和同学们相互探讨，相互学习，相互监督。学会了合作，学会了运筹帷幄，学会了宽容，学会了理解，也学会了做人与处世。课程设计是我们专业课程知识综合应用的实践训练，是我们迈向社会，从事职业工作前一个必不少的过程”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础通过这次课程设计，本人在多方面都有所提高。提高了编程能力，绘图能力，熟悉了规范和标准，同时各科相关的课程都有了全面的复习，独立思考的能力也有了提高。在这次设计过程中，体现出自己综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#include<stdio.h>#include<math.h>#include<stdlib.h>#define INFEX 10000#define INFCO 10000typedef struct poldouble coef;int expn;MPOL;MPOL *cp1,*cp2;/-顺序结构部分-int n1,n2;void ansprint(double *a,int n) /打印出结果int choose;puts("请选择输出顺序：1 升幂 2 降幂：");scanf("%d",&choose);int i,num;if(choose!=2) /升幂打印if(choose!=1)printf("没有%d选项，系统将默认输出升序：nY(X)=",choose);elseprintf("Y(X)=");num=0;for(i=0;i<=n;i+)if(fabs(ai)>1e-8)if(num+)putchar('+');printf("%lfX%d",ai,i);else /降幂打印printf("Y(X)=");num=0;for(i=n;i>=0;i-)if(fabs(ai)>1e-8)if(num+)putchar('+'); printf("%lfX%d",ai,i);putchar(10);void addpoly(double *a,double *b,double *c) /顺序结构相加int min=(cp1n1-1.expn>cp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int max=(cp1n1-1.expn<cp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int i;for(i=0;i<=min;i+)ci=ai+bi;for(;i<=max;i+)if(cp1n1-1.expn>cp2n2-1.expn)ci=ai;elseci=bi;puts("相加结果为：");ansprint(c,max);void subpoly(double *a,double *b,double *c) /顺序结构相减int min=(cp1n1-1.expn>cp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int max=(cp1n1-1.expn<cp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int i;for(i=0;i<=min;i+)ci=ai-bi;for(;i<=max;i+)if(cp1n1-1.expn>cp2n2-1.expn)ci=ai;elseci=-bi;puts("相减结果为：");ansprint(c,max);void mulpoly(double *a,double *b,double *c) /顺序结构相乘int max=cp1n1-1.expn+cp2n2-1.expn+2;int i,j;for(i=0;i<max;i+)ci=0;for(i=0;i<=cp1n1-1.expn;i+)for(j=0;j<=cp2n2-1.expn;j+)ci+j+=ai*bj;puts("相乘结果为：");ansprint(c,max-1);void creatpoly1(double *a,int pt) /建立顺序结构int i;if(pt=1)for(i=0;i<=cp1n1-1.expn;i+)ai=0;for(i=0;i<n1;i+)acp1i.expn=cp1i.coef;elsefor(i=0;i<=cp2n2-1.expn;i+)ai=0;for(i=0;i<n2;i+)acp2i.expn=cp2i.coef;/-动态链式结构部分-typedef struct p_pol /结点定义double coef;int expn;p_pol *next;MPP;MPP * creatlink(MPP *p,int n,int pt) /构造动态链表结构MPP *d,*q;int i;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<n;i+)d=(MPP *)malloc(sizeof(MPP);if(d=NULL)exit(0);d->next=NULL;if(pt=1)d->coef=cp1i.coef;d->expn=cp1i.expn;elsed->coef=cp2i.coef;d->expn=cp2i.expn;q->next=d;q=d;return p;void printlink(MPP * p) /打印结果int num=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=new MPOLnum;p=tp->next;while(p!=NULL)di.coef=p->coef;di.expn=p->expn;i+;p=p->next;if(choose=2) /降幂打印count=0;printf("Y(X)=");for(i=num-1;i>=0;i-)if(count+)putchar('+');printf("%lfX%d",di.coef,di.expn);else /升幂打印if(choose!=1)printf("没有%d选项，系统将默认输出升序：nY(X)=",choose);elseprintf("Y(X)=");for(i=0;i<num;i+)if(count+)putchar('+');printf("%lfX%d",di.coef,di.expn);putchar(10);void addlink(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;else if(p1->expn<p2->expn)head->coef=p1->coef;head->expn=p1->expn;p1=p1->next;elsehead->coef=p2->coef;head->expn=p2->expn;p2=p2->next;puts("相加结果为：");printlink(p3);void sublink(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;else if(p1->expn<p2->expn)head->coef=p1->coef;head->expn=p1->expn;p1=p1->next;elsehead->coef=-p2->coef;head->expn=p2->expn;p2=p2->next;puts("相减结果为：");printlink(p3);void mullink(MPP *p1,MPP *p2,MPP *p3) /动态链表相乘MPP *p,*head,*d,*tp;int i,j;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p->coef=INFCO;p->expn=-INFEX;p->next=NULL;tp=head=p3=p;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p->coef=INFCO;p->expn=INFEX;p->next=NULL;tp->next=p;for(i=0;i<n1;i+)p1=p1->next;d=p2;for(j=0;j<n2;j+)d=d->next;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p->next=NULL;p->coef=p1->coef*d->coef;p->expn=p1->expn+d->expn;tp=p3;while(tp->next!=NULL)if(tp->expn=p->expn)tp->coef+=p->coef;free(p);break;if(tp->expn<p->expn&&tp->next->expn>p->expn)p->next=tp->next;tp->next=p;break;tp=tp->next;tp=p3;while(tp->next!=NULL)if(tp->next->expn=INFEX)free(tp->next);tp->next=NULL;break;tp=tp->next;puts("相乘结果为：");printlink(p3);void deletelink(MPP *p) /删除结点释放内存MPP *d;while(p!=NULL)d=p;p=p->next;free(d);int main()int i,choose,choose2;puts("输入第一个多项式的项数：");scanf("%d",&n1);cp1=(MPOL *)malloc(n1*sizeof(MPOL);puts("分别输入各项的系数和指数：");for(i=0;i<n1;i+)scanf("%lf%d",&cp1i.coef,&cp1i.expn);puts("输入第二个多项式的项数：");scanf("%d",&n2);cp2=(MPOL *)malloc(n2*sizeof(MPOL);puts("分别输入各项的系数和指数：");for(i=0;i<n2;i+)scanf("%lf%d",&cp2i.coef,&cp2i.expn);puts("请选择实现结构：1 顺序结构 2 动态链表结构！");scanf("%d",&choose);double *c1,*c2,*c3;MPP *p1=NULL,*p2=NULL,*p3=NULL;switch(choose)case 1:c1=(double *)malloc(cp1n1-1.expn+1)*sizeof(double);c2=(double *)malloc(cp1n2-1.expn+1)*sizeof(double);creatpoly1(c1,1);creatpoly1(c2,2);break;case 2:p1=creatlink(p1,n1,1);p2=creatlink(p2,n2,2);break;default:printf("没有%d选项系统将自动调用默认结构（动态链表）！n",choose);choose=2;p1=creatlink(p1,n1,1);p2=creatlink(p2,n2,2);puts("选择操作方式：1 相加 2 相减 3 相乘");scanf("%d",&choose2);c3=(double*)malloc(cp1n1-1.expn+cp2n2-1.expn+2)*sizeof(double);if(choose=1)switch(choose2)case 1:addpoly(c1,c2,c3);break;case 2:subpoly(c1,c2,c3);break;case 3:mulpoly(c1,c2,c3);break;default:printf("没有%d选项系统将自动调用默认操作（相加）！n",choose);addpoly(c1,c2,c3);elseswitch(choose2)case 1:addlink(p1,p2,p3);break;case 2:sublink(p1,p2,p3);break;case 3:mullink(p1,p2,p3);break;default:printf("没有%d选项系统将自动调用默认操作（相加）！n",choose);choose2=1;addlink(p1,p2,p3);deletelink(p1);deletelink(p2);deletelink(p3);free(cp1);free(cp2);if(choose!=2)free(c1);free(c2);free(c3);system("pause");system("cls");main();return 0;