单链表实现两个多项式的求和.doc

北京理工大学珠海学院计算机科学与技术学院北京理工大学珠海学院数据结构课程设计报告题目：用重定义的单链表存储一元多项式，并实现两个多项式的相加运算 所在学院：计算机科学技术学院 专业班级： 学生姓名： 指导教师： 2010年 月 日第17页目录前言12概要设计12.1 数据结构设计13详细设计13.1 算法设计13.1.1 建立链表的算法13.1.2 链表插入一个元素的算法23.1.3 一元多项式的相加23.2 ADT描述23.3 功能模块分析33.4 数据存储结构设计：33.5主要算法流程图（流程图在下一页）34软件测试95设计体会10致谢:11参考文献：11附录：11前言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构及其相应的算法并初步掌握算法的时间分析和空间分析的技术。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。2概要设计2.1 数据结构设计数据的链接存储表示又被称为链接表。当链接表中的每个结点只含有一个指针称为单链表。在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置是保存在它的或后继结点中的，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到自访问任一元素的时间与该元素结点在链接存储中的位置有关。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。 详细设计.1 算法设计 3.1.1 建立链表的算法（1）算法思想分析链表的创建，首先是创建一个结构体，用该结构体的创建该结构体的指针，便于我们对链表中的节点的操作，用head保存头节点，用输入数据时的节点保存到p2节点中，然后p1重新分配内存存储我们下一个输入的数据，再用p2的next指针指向p1（2）要点描述链表的要点主要是怎样把数据链接在一起，首先是创建结构体，创建头结点，用p1保存下一个节点的 3.1.2 链表插入一个元素的算法 （1）算法思想分析链表的插入操作设计是根据链表的结构特点，链表的每一个节点中都有数据域和指向下一个节点的指针，通过分配一个新的节点的内存，将我们要插入的位置的前一个节点的指针保存到新创建的节点中 3.1.3 一元多项式的相加（1）算法思想分析采用链式存储结构存储一元多项式，对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于一元多项式中所有指数不同的项，则分别抄复到“和多项式”中去；（2）要点描述运算规则：假设指针和分别指向和多项式和多项式中当前进行比较的某个结点，则比较两个结点中的指数项分别有下列三种情况：1. 指针所指向结点的指数值指针所指向的结点的指数值，则应摘取指针所指结点插入到“和多项式”链表中去；2. 指针所指向结点的指数值指针所指向的结点的指数值，则应摘取指针所指结点插入到“和多项式”链表中去；3. 指针所指向结点的指数值指针所指向的结点的指数值，则将两个结点中的系数相加，若和不为零则修改所指结点的系数值，同时释放所指结点；反之，从多项式的链表中删除相应的结点，并释放和所指结点。3.2 ADT描述ADT Polynomial数据对象：D=ai|ai属于TermSet，i=1,2,3, ,m, m=0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=|ai-1,ai属于D,i=1,2,3,，n基本操作：CreatPolyn( &P, m);操作结果：输入项的系数和指数，建立一元多项式DestroyPolyn(Polynomial *p );初始条件：一元多项式已存在操作结果：销毁一元多项式Order(Polynomial *p)初始条件：一元多项式p已存在操作结果：多项式的单项式升幂排序PolyLength(Polynomial *p)初始条件：一元多项式p已存在操作结果：返回多项式的单项式个数PaiXu(Polynomial *p)初始条件：一元多项式p已存在，调用Order(Polynomial *p)操作结果：完成多项式的升幂排序PrintPolyn( P );初始条件：一元多项式已存在操作结果:打印输出一元多项式AddPolyn( &Pa, &Pb);初始条件：一元多项式Pa和Pb已存在操作结果：完成多项式相加运算，即：Pa = Pa + Pb,并销毁一元多项式PbADT Polynomial ;3.3 功能模块分析（1）typedef struct Polynomial 块主要实现多项式的单链表存储结构；（2）CreatPolyn( &P, m);主要实现一元多项式的输入；（3）PrintPolyn( P )；主要实现打印输出一元多项式；（4）Order(Polynomial *p)；多项式的单项式幂最大的放在最后；（5）PolyLength(Polynomial *p)；返回多项式的单项式个数；（6）PaiXu(Polynomial *p)；完成多项式的升幂排序；（7）DestroyPolyn(Polynomial *P )；销毁一元多项式；（8）AddPolyn( &Pa, &Pb)；主要实现多项式相加运算，即：Pa = Pa + Pb；3.4 数据存储结构设计：采用链式存储结构存储多项式typedef struct Polynomial /*用单链表存储多项式的结点结构*/int coef; /*多项式的系数*/int exp; /*指数*/struct Polynomial *next;/*next是struct Polynomial类型中的一个成员， 它又指向struct Polynomial类型的数据，以此建立链表*/Polynomial;3.5主要算法流程图（流程图在下一页）主函数main()N输出多项式PaiXu(poly);PrintPolyn(poly)NYNN输出界面菜单和多项式AddPolyn(polya,polyb);PrintPolyn(polya);DestroyPolyn(polya);结束YYYYpoly=NULL创建多项式poly=CreatPolyn();N若4若3若2若1scanf(%d,&i);开始开始申请头结点head=(Polynomial*)malloc(POLY);if(!head)tail=head；printf(系数:);scanf(%d,&c);printf(指数: );scanf(%d,&e);c=0s=(Polynomial *) malloc(POLY); /*申请新结点*/s-coef=c; /*申请新结点后赋值*/s-exp=e; /*申请新结点后赋值*/tail-next=s; /*做尾插，插入新结点*/ tail=s; /*tail始终指向单链表的表尾*/tail-next=NULLreturn(head);return NULL;exit(ERROR);c!=0printf(请重新输入)printf(系数:);scanf(%d,&c);printf(指数: );scanf(%d,&e);YNY结束创建多项式* CreatPolyn(void)Yp!=NULL&q!=NULLp-expexp开始p=polya-next;q=polyb-next;he=polya;Polynomial*p,*q,*he,*temp;int sum;p-exp=q-expp!=NULLhe-next=q; he=he-next;q=q-next;p-coef=sum; he-next=p; he=he-next; p=p-next; temp=q-next; free(q);q=temp;sum=p-coef+q-coef;temp=p-next;free(p); p=temp; temp=q-next; free(q); q=temp;sum!=0he-next=p; he=he-next; p=p-next;he-next=p;YYYNNNhe-next=q;YNN结束两个多项式相加AddPolyn(Polynomial *polya,Polynomial *polyb)Polynomial *q;int i=0;q=p;q=q-next; i+;q=p-next; free(p); p=q;Polynomial *q;开始p-next!=NULLq-next!=NULLY结束开始return(i);结束NYN返回多项式中单项式的个数PolyLength(Polynomial *p)DestroyPolyn(Polynomial *p)/删除多项式执行循环体;j+;Order(p);j=1q=q-next; i+;a=q-coef;b=q-exp;q-coef=q-next-coef;q-exp=q-next-exp;q-next-coef=a;q-next-exp=b;Polynomial *q;int a,b,i=0; q=p;开始q-next!=NULLq-expq-next-expjPolyLength(p)结束YYNN开始结束YN函数PaiXu(Polynomial *p)函数Order(Polynomial *p)/*多项式的升幂排序*/3软件测试5设计体会1.不论问题规模的大小和程序的难易程度，都应该保持严谨的变成态度，这样才可以避免一些低级错误，浪费额外的时间;.手写的代码和上机的程序运行是有差距的，我觉得自己今后应该进一步的加强上机实践；.成功的基础依赖于平时扎实的基本功，依赖于老师的辛勤指导和教学，掌握老师课堂上的教学内容很重要；.我要树立简洁易明的编程风格，实现良好的沟通；.通过这次“多项式的相加”实践，我更进一步的掌握了线性表的链式存储结构。.对程序“精益求精”，就会发现其实还有许多自己力所能及的地方可以改进，不能放弃。致谢:感谢老师对我的指导，没有你的诲人不倦，就没有我的豁然开朗，就没有我这“多项式的和”，再次感谢！您的学生：*参考文献：.数据结构（语言版）严蔚敏吴伟民编著清华大学出版社语言程序设计丁俊岭余坚姜德森编著中国铁道社出版社.面向对象程序设计教程（第版）陈维兴林小茶编著清华大学出版社附录：#include#include#include#include#define ERROR 0#define POLY sizeof(Polynomial)typedef struct Polynomial /*用单链表存储多项式的结点结构*/int coef; /*多项式的系数*/int exp; /*指数*/struct Polynomial *next;/*next是struct Polynomial类型中的一个成员， 它又指向struct Polynomial类型的数据，以此建立链表*/Polynomial;Polynomial * CreatPolyn(void)/*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/Polynomial *head,*tail,*s;int c,e;head=(Polynomial *)malloc(POLY);/*建立多项式的头结点，为头结点分配存储空间*/ if(!head)exit(ERROR); tail=head;/*tail指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/printf(系数:);scanf(%d,&c); /*输入系数*/printf(指数: );scanf(%d,&e); /*输入指数*/ if(c=0)printf(请重新输入); return NULL;elsewhile(c!=0) /*输入系数为0时，表示多项式的输入结束*/ s=(Polynomial *) malloc(POLY); /*申请新结点*/ s-coef=c; /*申请新结点后赋值*/ s-exp=e; /*申请新结点后赋值*/ tail-next=s; /*做尾插，插入新结点*/ tail=s; /*tail始终指向单链表的表尾*/ printf(系数:); scanf(%d,&c); printf(指数: ); scanf(%d,&e); tail-next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/ return(head);void DestroyPolyn(Polynomial *p)/删除多项式Polynomial *q;while(p-next!=NULL) q=p-next; free(p);p=q;int PolyLength(Polynomial *p)Polynomial *q;int i=0;q=p;while(q-next!=NULL)q=q-next;i+;return(i);void Order(Polynomial *p)/*多项式的升幂排序*/Polynomial *q;int a,b,i=0;q=p;while(q-next!=NULL)if(q-expq-next-exp)a=q-coef;b=q-exp;q-coef=q-next-coef;q-exp=q-next-exp;q-next-coef=a;q-next-exp=b;q=q-next;i+;void PaiXu(Polynomial *p)/重复调用升幂排序函数int j;for(j=1;jnext;/*令p指向polya多项式链表中的第一个结点*/ q=polyb-next;/*令q指向polyb多项式链表中的第一个结点*/ he=polya; /*令he指向和多项式polya*/ while(p!=NULL&q!=NULL)/*当两个多项式均未扫描结束时，执行以下操作*/ if(p-expexp) /*若p指向的多项式指数小于q指的指数*/ he-next=p; /*将p结点加入到和多项式中*/ he=he-next; p=p-next; /*将p指针后移一位*/ else if(p-exp=q-exp) /*若指数相等，则相应的系数相加*/ sum=p-coef+q-coef; if(sum!=0) /*系数和不为零，执行下列操作*/ p-coef=sum; he-next=p; he=he-next; p=p-next; temp=q-next; free(q);/q=q-next; q=temp; /*释放原q节点*/ else /*系数和为零，则删除结点p与q，并将指针指向下一个结点*/ temp=p-next; free(p); p=temp; temp=q-next; free(q); q=temp; else /*若p指数大于q指数*/ he-next=q; /*p结点不动，将q结点加入到和多项式中*/ he=he-next; q=q-next; if(p!=NULL)/*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ he-next=p; else /*否则将B的结点加入到和多项式中*/ he-next=q;void PrintPolyn(Polynomial *p) /*输出函数，打印出一元多项式*/p=p-next;if(p-exp0) printf(A(x)= %d*x%d,p-coef,p-exp);else if(p-expcoef,p-exp);elseprintf(A(x)= %d,p-coef);while(p-next!=NULL)p=p-next;if(p-coef0)if(p-exp0) printf( + %d*x%d,p-coef,p-exp);else if(p-expcoef,p-exp);elseprintf( + %d,p-coef);elseif(p-exp0) printf( %d*x%d,p-coef,p-exp);else if(p-expcoef,p-exp);elseprintf( %d,p-coef);void main() /*主函数*/Polynomial *polya,*polyb;int i;printf( !两个多项式的相加!);/printf(若输入的单项式为0，则表明多项式创建完毕n);begin: printf(ntt* * * * * * * * * *); printf(ntt* 1、输入第一个多项式 *); printf(ntt* 2、输入第二个多项