数据结构课程设计一元多项式的加法、减法、乘法的实现.doc

HUNAN CITY UNIVERSITY 数据结构课程设计 报 告设计题目：一元多项式的加法、减法、乘法的实现专 业： 计算机科学与技术（嵌入式） 学生姓名： 班级学号： 分组成员： 指导教师： 陈强老师 2012 年 6月 8日1006402数据结构课程设计报告一、 设计时间2011年6月4日6月8日二、 设计地点湖南城市学院实验楼计算机房407三、 设计目的数据结构主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论，是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。该课程的特点是实践性较强，为了学好这门课程，需要在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。具体要求如下：1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能;3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。四、 设计小组成员五、 指导教师：六、 设计课题：顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+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)分别采用顺序和动态存储结构实现；3)结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况七、 基本思路及关键问题的解决方法输入多项式各项的系数和指数并对其进行稀疏判断，然后选择实现结构，判断为顺序结构或动态链表结构，分别进行处理，再选定计算方法（进行加法、减法和乘法判断），然后用相应的计算方法对多项式进行计算，最后判断升幂或降幂的输出方式进行输出。八、 算法及流程图;流程图：开始输入两个多项式各项的系数和指数是判断是否稠密？否为稀疏多项式为稠密多项式选择实现结构 顺序结构？ 是否 为顺序结构为动态链表结构选择操作方式选择操作方式 加法？ 加法？调用加法函数是否 是否 减法？ 减法？调用加法函数否是否调用乘法函数调用减法函数调用减法函数调用乘法函数是否选择打印输出顺序选择打印输出顺序 升幂？ 升幂？ 是否是否调用降幂输出函数调用升幂输出函数调用降幂输出函数调用升幂输出函数打印输出处理后的结果结束 运行如图： 运算操作方式：1 加法：两多项式指数相同项指数不变系数相加2 减法：两多项式指数相同项指数不变系数相减3 相乘：第一个多项式的各项和第二个多项式的各项分别相乘再相加，其中系数相乘指数相加，具体表达式如下：假设A(x)和B(x)为一元多项式，则M(x) = A(x) * B(x)= A(x) * b1xe1+b2xe2+bnxen= biA(x)xei 九、 调试过程中出现的问题及相应解决办法； 独立测试各个模块的功能时发现在创建链表后和另一个进行运算后多余的存储单元没有释放而造成内存的泄漏，还有对于链表的运算时结束条件掌握不透彻导致没有按计划地去结束，比如在用For循环及While循环时没有正确地判断指针的移动与结束条件而得不到自己想要的结果。进入函数内部调试时发现有误用没有初始化的变量，还有赘余的语句扰乱了代码的健壮性。 在主函数中对各个函数的调用时没有一个清晰的思路，使程序显得很混乱，给调试造成了很大困难。 对非法操作控制的不够完善，例如缺少对越界访问及其非法数据的控制机制，使程序的安全性下降。对于每创建一个链表，每次在进行完相应操作之后应该对其链表进行删除释放，并且要做到在适当的时间进行删除，对于运算结束的条件的意识不是很清楚，运算结束的标识是当结点指针移动并且为空时结束，还有在用指针和变量的时候注意初始化问题，并且尽量使得程序保持良好的可读性。十、 课程设计心得体会；编写的程序不但要拿来使用，还要给别人查看，以便代码的维护。所以代码编写的风格尽量规范，清晰。变量要尽量少定义，结构夜采用简单的。另外，对指针的使用要小心，尽量在定义的时候就进行初始化，避免野指针，指针的使用涉及到内存的分配。该程序基本实现了要求的顺序结构、动态链表结构下的一元多项式的加法、减法、乘法等功能。代码较为冗余，可读性较差，可以多添加一些提示语句以及注释。在这次课程设计中我又进一步地了解了数据结构中算法的核心思想的重要性，懂得了一个程序地好坏关键在于算法是否优秀，一个好的优秀的算法可以使我们的程序更加完善，安全性更高以及有更高的效率。这次设计中我发现了自己的许多不足，如对指针的机制掌握的还不是很透彻，有的时候会出现指针指向错误以及空指针的错误,还有不能很好地分析自己算法地复杂度以及不能很好地使用控制机制使自己的程序流畅地运行。十一、 部分源程序(核心代码)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 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);动态链表的建立和构造：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 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) /如果系数不为0p=(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);源程序：#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);if(n1<(cp1n1-1.expn+1)/2)puts("此多项式稀疏！");elseputs("此多项式稠密！");puts("输入第二个多项式的项数：");scanf("%d",&n2);cp2=(MPOL *)malloc(n2*sizeof(MPOL);puts("分别输入各项的系数和指数：");for(i=0;i<n2;i+)scanf("%lf%d",&cp2i.coef,&cp2i.expn);if(n2<(cp2n2-1.expn+1)/2)puts("此多项式稀疏！");elseputs("此多项式稠密！");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;参考文献1苏仕华等编著.数据结构课程设计.机械工业出版社.20072严蔚敏等编著.数据结构（C语言版）.清华大学出版社.20033严蔚敏等编著.数据结构题集（C语言版）.清华大学出版社，20034郑莉等 编著. C+程序设计语言（第三版）.清华大学出版社，2005.06北京5.陈清华 朱红主编. Visual C+课程设计案例精选与编程指导.东南大学出版社，2003.06，南京6.刘振安等编著. C+程序设计课程设计.机械工业出版社，2004.08，北京