数据结构课程设计——一元多项式计算.doc

成绩 南京工程学院课程设计说明书(论文)题 目 一元多项式计算 课 程 名 称 数据结构 院（系、部、中心） 通信工程 专 业 计算机通信 班 级 算通111 学 生 姓 名 余丹红 学 号 208110410 设 计 地 点 信息楼322 指 导 教 师 郝慧珍 设计起止时间：2012年12月 17日至2012 年12月18日目 录1设计目标12总体设计121数据结构描述与定义122模块设计23测试结果与分析114课程设计总结13参考文献:15附录A： 源程序清单151 设计目标通过课程设计，达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，使学生能够根据数据对象的特性，掌握数据组织、算法设计、算法性能分析的方法，并培养良好的程序设计能力。本程序是利用单链表来表示一元多项式然后实现各项指数和系数的输入，进行多项式建立，并以多项式的形式输出，实现多项式的相加，相减和多项式的相乘这三种运算。2总体设计21数据结构描述与定义一元多项式定义系数和指数结构如下： coefexpnnextcoef域-存放结点的系数值expn域-存放结点的指数值next域-存放结点的直接后继的地址（位置）的指针域（链域）定义多项式的结构为线性链表的存储结构，每个结点包含三个元素：系数coef，指数expn和指向下一个结点的指针*next。通过指针，我们就可以把多个单项式连接起来，形式一个多项式，需要说明的是从广义的角度讲，单项式也是一个多项式。基于以上的分析，我们定义多项式的数据结构为如下结构体形式：typedef struct Polynomial float coef; /系数 int expn; /指数 struct Polynomial *next; /下一个指针*Polyn,Polynomial; /Polyn结构体变量名22模块设计从实现多项式式运算过程的角度来分析，至少需要这样一些子功能模块。 多项式创建功能 多项式销毁功能 多项式输出功能 多项式的相加功能 多项式的相减功能 多项式的相乘功能定义并调用的函数有：void Insert(Polyn p,Polyn h);/将结点p插入链表hPolyn CreatePolyn(Polyn head,int m);/创建链表（多项式）void DestroyPolyn(Polyn p);/销毁void PrintPolyn(Polyn P);/输出Polyn AddPolyn(Polyn pa,Polyn pb);/a+bPolyn SubtractPolyn(Polyn pa,Polyn pb);/a-bPolyn MultiplyPolyn(Polyn pa,Polyn pb);/a*b void main()/主函数系统共分几个模块，每个模块的算法描述及流程图（核心模块）1系统模块图（模块划分）图1 系统模块划分图2 模块流程图及算法描述 分模块流程图(1)多项式的创建 (2)多项式的销毁开始从键盘输入项数mm<=0返回空定义存储多项式数据类型term动态分配空间完成建立多项式YN开始P的next值赋给q1q1的next值赋给q2q1的next值存在Y释放q1q2赋给q1q2的next值赋给q2N释放q1结束 (3)多项式的输出开始q存在输出“0”Nq的系数不等于1和-1Y输出q的系数q的指数为1NYNq的系数等于1Yq的系数为0输出“1”YNNq指数为0YNq的指数为1YNYNY输出“+”q的指数为1q的系数大于0且flag不等于1p=p->nextq不为空NY结束输出“-X（q的指数）”输出“-X”输出“-1”输出X（q的指数）输出“X”输出“X”输出X（q的指数）YN(4)多项式的相加开始定义存储和链表hc动态分配空间qa=pa->nextqb=pb->nextqa!=qb?Yqa>qb?Yqa的各个值赋给qcqa指向qa的nextqb的各个值赋给qcqb指向qb的nextNqa的系数加qb的系数赋给qc的系数qa的指数赋给qc的指数qa指向qa的nextqb指向qb的nextqc插入到hc中qc的系数不为0Y释放qc空间结束(5)多项式的相减 (6)多项式的相乘开始定义存储和链表h动态分配空间p=p->coef*(-1)两多项式相加输出P不为0？p=p->nextYN结束开始定义存储和链表hf动态分配空间qa=pa->nextqb=pb->nextqb存在？qa存在？Y定义存储和链表pf动态分配空间将qa和qb的系数相乘赋给pf的系数将qa和qb的指数相加赋给pf的指数将pf插入到hf中qb=pb->nextYNqa=qa->next返回hf结束算法描述(1)多项式的创建Polyn CreatePolyn(Polyn head,int m) /建立一个头指针为head、项数为m的一元多项式 /在主程序初始时，先输入的多项式中的项数m、n 在这里为m。主程序中的pa、pb在此为headint i;/用来计数 Polyn p;/定义一个p链表 p=head=(Polyn)malloc(sizeof(struct Polynomial);/动态分配空间，建立头结点 head->next=NULL; for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Polynomial);/建立新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1); /上面循环中i从0开始，所以此处为i+1 scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /调用Insert函数插入结点p return head;(2)多项式的销毁利用循环逐渐销毁多项式void DestroyPolyn(Polyn p) /销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next)/利用循环逐渐销毁多项式Pfree(q1); q1=q2;/指针后移 q2=q2->next;free(q1);(3)多项式的输出void PrintPolyn(Polyn P) /输出多项式Polyn q=P->next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar('0'); printf("n"); return; while(q) /多项式存在 if(q->coef>0&&flag!=1) putchar('+'); /系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1) /系数非1或-1的普通情况 printf("%g",q->coef); /%g表示使用%e或%f，哪个输出宽度稍短就使用哪一个 if(q->expn=1) putchar('X'); /若指数为1 else if(q->expn) printf("X%d",q->expn); /指数不为1 else if(q->coef=1) /系数为1的情况 if(!q->expn) putchar('1'); /指数为0，则为1 else if(q->expn=1) putchar('X'); /指数为1则为xelse printf("X%d",q->expn); if(q->coef=-1)/系数为-1的情况if(!q->expn) printf("-1"); /指数为0，则为-1else if(q->expn=1) printf("-X"); /指数为1,则为-xelse printf("-X%d",q->expn);q=q->next; flag+; /项数加1 printf("n");(4)多项式的相加利用对a、b两个多项式每一项分模块讨论进行的，如a指数大或者b空，则将a项该节点插入新链c中，若b指数大或者a空，则将b项插入到c中，如若a、b两项指数相等，则合并后再插入到c链中。Polyn AddPolyn(Polyn pa,Polyn pb) /求解并建立多项式a+b，返回其头指针 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hc->next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb)case 1: qc->coef=qa->coef; qc->expn=qa->expn; / a的指数大或b为空，把qa赋值给qc qa=qa->next; /qa指向下一个 break;case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; /qc等于qa与qb的和 qa=qa->next; qb=qb->next; /qa，qb都分别指向下一个 break;case -1: qc->coef=qb->coef; /b的指数大或a为空，把qb赋值给qc qc->expn=qb->expn; qb=qb->next; /qb指向下一个 break; if(qc->coef!=0) qc->next=hc->next;/qc插入到hc中去，并重新生成新的hc，到最后实现a与b的和 hc->next=qc; hc=qc;else free(qc);/当相加系数为0时，释放该结点 return headc; /返回头指针，实现多项式a与b的相加(5)多项式的相减利用a-b=a+(-b)来进行的，即只将b系数取反即可。Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多项式a-b，返回其头指针，将pb的系数取反后调用相加的函数，实现相减功能 Polyn h=pb; Polyn p=pb->next; Polyn pd;while(p) /将pb的系数取反 p->coef*=-1; p=p->next; /p向后移动 pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) /恢复pb的系数 p->coef*=-1; return pd; /返回pd的值，实现a与b两个多项式相减(6)多项式的相乘将a中的每一项乘b中的每一项，即系数相乘，指数相加，将它放在新节点中并插入新链h，最后返回链h。Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多项式a*b，返回其头指针 Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hf->next=NULL; for(;qa;qa=qa->next) for(qb=pb->next;qb;qb=qb->next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);/调用Insert函数以合并指数相同的项 return hf;3 测试结果与分析系统选择界面如图1图1输入数据为：2（enter）2（pase）3（enter）8（pase）2（enter）3（enter）5（pase）1（enter）3（pase）6（enter）7（pase）2（enter）图2输出菜单：如图2图3分别输入a,b,c,d,e五个选项显示结果：如图4图4输入f，结束，显示结果：如图五图54 课程设计总结一 程序总结计算一元多项式加法，其结果取决于多项式的各项系数与指数，因此程序核心是处理两个多项式的系数与指数。定义结构体将多项式的各项系数与指数存放，定义结构体类型链表为程序的循环控制提供了可能，利用对链表的运算来确定结果多项式的各项系数与次数，同理算出相应的幂数。链表是在计算机内存中使用一组连续的存储单元保存数据类型和名字相同的变量。就链表这种数据类型而言，在排列上采用的方法也是按序排放，先存放第一行，接着存放第二行，直到所有数据元素被存放。多项式采用的是链表形式，以牺牲一定的空间提高程序的运行速度和可行性。采用链式结构存储多项式，用链表结构体的一个域标记多项式的次数，另一个域标记多项式的系数，程序中采用的是m表示最高次系数，进行加法运算时，标记系数域相加即为相加的对应系数，标记指数域相同则表示为同类项。链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。链表顾名思义，要把各个元素链接起来才算撒。通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。二 错误分析错误产生的原因有很多：1. 函数定义冲突；2. 函数调用错误； 3. 符号字母等输入错误；4. 链表的定义错误；5. 变量名重复发生冲突；6. 指针指向发生错误；7. 未释放空空间；错误显示：如图6 图6三收获与体会本次课程设计，我查找过资料，请教过同学，以及自己的努力，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在程序设计中，我学会了很多学习的方法，而这是日后最实用的，真的是受益匪浅。本学期的程序设计课程，我锻炼了能力，学到很多东西，比如思考问题的角度也会从多方面着手；对自己的专业也有自己的想法在和同学的交流过程中，互动学习，将知识融会贯通。通过这次课程设计，我对很多的函数有了新的认识，也学会了运用多种函数，我也明白了写软件的基本过程和基本方法。在程序的设计过程中遇到了很多的困难，在程序一次一次的调试失败下曾经想过要放弃，我最后还是让自己坚持下来，毫不畏惧困难，在同学的帮助与讲解下我总算是顺利的完成了程序的课程设计。另外也需要提出的是在这次程序设计的过程中，非常感谢老师对我们的耐心指导。老师在教学过程中表现出来的对学术专研一丝不苟的精神让我非常有收获。在这几天的编写过程中我对语言有了更进一步的认识和了解，也感受到了编程给我带来的快乐与充实，明白了想成为一个合格的甚至是优秀的程序员，我还需要更多更难的锻炼。所以我还要不断地学习不断地学习,不断地成长。参考文献:1严蔚敏，吴伟民数据结构（C语言版）北京：清华大学出版社，19972朱战立 数据结构西安：西安电子科技大学出版社,20043严蔚敏，吴伟民 数据结构题集（C语言版）北京：清华大学出版社,2000附录A： 源程序清单#include<stdio.h>#include<malloc.h>#include<stdlib.h>/定义多项式数据结构typedef struct Polynomial float coef; /系数 int expn; /指数 struct Polynomial *next; /下一个指针*Polyn,Polynomial; /Polyn结构体变量名void Insert(Polyn p,Polyn h);/将结点p插入链表hPolyn CreatePolyn(Polyn head,int m);/创建链表（多项式）void DestroyPolyn(Polyn p);/销毁void PrintPolyn(Polyn P);/输出int compare(Polyn a,Polyn b);/比较a，b的指数大小，为下面a+b做铺垫Polyn AddPolyn(Polyn pa,Polyn pb);/a+bPolyn SubtractPolyn(Polyn pa,Polyn pb);/a-bPolyn MultiplyPolyn(Polyn pa,Polyn pb);/a*b /*主函数*/void main() int m,n,a,x;char flag; Polyn pa=0,pb=0,pc;/system("color F5");/字体颜色system("color 5F");/背景颜色printf("n");printf("*W E L C O M E*nn");printf("*【欢迎使用简便式一元多项式计算程序】*nn");printf("*nn");printf("*【使用说明：您可建立a,b两个多项式，并进行相加、相减、相乘三种运算】*nn");printf("*nn");printf("*【请按以下提示请输入您所需的数据】*nn");printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);/建立多项式a printf("请输入b的项数:"); scanf("%d",&n); pb=CreatePolyn(pb,n);/建立多项式bsystem("cls");printf("n");printf("*n");printf("* A.【输出多项式a】*n");printf("* B.【输出多项式b】*n");printf("* C.【 输出a+b 】*n");printf("* D.【 输出a-b 】*n");printf("* E.【 输出a*b 】*n");printf("* F.【 退出程序 】*n"); printf("*n");while(1) printf("n请选择操作："); scanf(" %c",&flag);/空格符号一定要注意switch(flag)case'A':case'a':printf("n 多项式a=");PrintPolyn(pa);break;case'B':case'b':printf("n 多项式b=");PrintPolyn(pb);break;case'C':case'c':pc=AddPolyn(pa,pb); printf("n a+b=");PrintPolyn(pc);break;case'D':case'd':pc=SubtractPolyn(pa,pb);printf("n a-b=");PrintPolyn(pc);break;case'E':case'e':pc=MultiplyPolyn(pa,pb);printf("n a*b=");PrintPolyn(pc);break;case'F':case'f':system("cls");printf("n");printf("n");printf("t*nn");printf("t* 感谢使用此程序 *nn");printf("t* O(_)O *nn");printf("t* 再 见 *nn");printf("t* Made by YDH *nn");printf("t*nn");DestroyPolyn(pa);DestroyPolyn(pb);return;default:printf("n 您的选择错误，请重新选择!n");/*合并两个多项式*/void Insert(Polyn p,Polyn h) /将两个多项式合并的算法，即将p插入h来实现 if(p->coef=0) free(p);/系数为0的话释放结点 else Polyn q1,q2; q1=h; q2=h->next; while(q2&&p->expn<q2->expn)/查找插入位置,直到p结点指数大于等于h结点 q1=q2; q2=q2->next; if(q2&&p->expn=q2->expn)/将指数相同相合并，指数相等时，系数相加 q2->coef+=p->coef; free(p); if(!q2->coef)/系数为0的话释放结点 q1->next=q2->next;/将q2释放掉 free(q2); else/指数为新时将结点插入 p->next=q2; /将p结点插入到h中去 q1->next=p;/*建立一元多项式*/Polyn CreatePolyn(Polyn head,int m) /建立一个头指针为head、项数为m的一元多项式 /在主程序初始时，先输入的多项式中的项数m、n 在这里为m。主程序中的pa、pb在此为headint i;/用来计数 Polyn p;/定义一个p链表 p=head=(Polyn)malloc(sizeof(struct Polynomial);/动态分配空间，建立头结点 head->next=NULL; for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Polynomial);/建立新结点以接收数据 printf("请输入第%d项的系数与指数:",i+1); /上面循环中i从0开始，所以此处为i+1 scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /调用Insert函数插入结点p return head;/*销毁多项式*/void DestroyPolyn(Polyn p) /销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next)/利用循环逐渐销毁多项式Pfree(q1); q1=q2;/指针后移 q2=q2->next;free(q1);/*输出多项式*/void PrintPolyn(Polyn P) /输出多项式Polyn q=P->next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar('0'); printf("n"); return; while(q) /多项式存在 if(q->coef>0&&flag!=1) putchar('+'); /系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1) /系数非1或-1的普通情况 printf("%g",q->coef); /%g表示使用%e或%f，哪个输出宽度稍短就使用哪一个 if(q->expn=1) putchar('X'); /若指数为1 else if(q->expn) printf("X%d",q->expn); /指数不为1 else if(q->coef=1) /系数为1的情况 if(!q->expn) putchar('1'); /指数为0，则为1 else if(q->expn=1) putchar('X'); /指数为1则为xelse printf("X%d",q->expn); if(q->coef=-1)/系数为-1的情况if(!q->expn) printf("-1"); /指数为0，则为-1else if(q->expn=1) printf("-X"); /指数为1,则为-xelse printf("-X%d",q->expn);q=q->next; flag+; /项数加1 printf("n");/*分模块讨论*/int compare(Polyn a,Polyn b) if(a&&b) if(a->expn>b->expn) return 1; /b为空或a的指数大 else if