数据结构实验报告,一元多项式

1、 数据结构课程设计报告 课 题: 一元多项式 姓 名： XX 学 号： 201417030218 专业班级： XXXX 指导教师： XXXX 设计时间： 2015年12月30日星期三 评阅意见：评定成绩： 指导老师签名： 年 月 日 目录一、 任务目标 3二、 概要设计 4三、 详细设计 6四、 调试分析 8五、 源程序代码 8六、 程序运行效果图与说明 15七、 本次实验小结 16八、 参考文献 16一丶任务目标分析 (1) a.能够按照指数降序排列建立并输出多项式b.能够完成两个多项式的相加，相减，并将结果输入要求：程序所能达到的功能： a.实现一元多项式的输入；b.实现一元多项式的输出；

2、 c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果；除任务要求外新增乘法：计算两个一元多项式的乘积并输出结果（2）输入的形式和输入值的范围：输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。输入形式：2 3-1 23 01 20 0输入值的范围：系数为int型，指数为float型（3）输出的形式：第一行输出多项式1；第二行输出多项式2；第三行输出多项式1与多项式2相加的结果多项式；第四行输出多项式1与多项式2相减的结果多项式；第五行输出多项式1与多项式2相乘的结果多项式二、概要设计 程序实现a. 功能

3、：将要进行运算的二项式输入输出；b. 数据流入：要输入的二项式的系数与指数；c. 数据流出：合并同类项后的二项式；d. 程序流程图：二项式输入流程图；e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。流程图：开始申请结点空间输入二项式各项的系数 x, 指数 y输入二项式的项数输出已输入的二项式是否输入正确合并同类项结束是否17三、详细设计（1）：存储结构 一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一

4、元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。（2）：数据链表由于采用链表的方法，我们可以建立3条链；一条用于存放多项式HA，一条用于存放多项式HB，还有一条用于存放新形成的HC。此外，我们的程序应具备以下几个功能：建立链表，撤销链表，打印链表，按要求插入一个新的结点，复制链表；为了使上面程序结构分析进一步细化，为了使程序结构更加清晰，我们可以把上面的内容都编写成函数形式。1、建立链表该程序建立链表的函数与大多数建立链表的操作基本一致，但是由于实体是一元多项式的关系。我们更希望，在处理客户输入的数据的同时，能对数据进行适当的处理。也就是数学上所说的，“对一元多项

5、式进行化简，并按照降幂排序。”由于在前面的练习中，我们得知，在链表中插入一个结点的函数，具有对链表的成员进行排序与合并的功能。如此一来，我们可以巧妙地处理，在建立链表的同时，调用”在链表中插入一个结点的函数”，对新建立的链表进行化简。 该函数的算法描述如下；声明指针变量，并作为头指针的指针变量赋初值NULL；创建一个新的结点，并输入链表的信息；若输入的系数值与函数值同不为0时，调用”在链表中插入一个结点的insert函数”，将结点插入链表中；(注：这里建立链表的函数与以往的不同，我们是通过假想有一条空链，不断地调用insert函数来实现建立链表的功能。简言之；链表中成员的链接全都靠insert

6、函数来实现，而该函数仅仅是不断地提供建立链表所要的数据罢了。)若还要继续插入结点，转到步骤2继续进行；否则，程序结束，把头指针返回主程序。2、撤销链表撤销链表是为了把链表所占用的地址回收起来，防止造成浪费。我们该程序可以采用从链表的始端逐步销去结点。在这个过程中，我们需要链表的头地址作为形式参数，还需要建立一个指针用来指向新头地址。该函数的算法描述如下：指针变量；并把头地址指针赋给新指针变量；把头地址指针指向下一个结点；删除新指针变量；若还要继续删除结点，转到步骤1继续执行；否则，结束程序。3、按要求插入一个新的结点由于前面的建立链表的creat函数，调用了该函数，所以我们这个函数的设计思想也

7、明朗多了，由于建立的链表是有序的，并且需要合并指数相同的结点，所以要新结点需要按指数值降幂的顺序插入链表中。判断链表是否为空，如果为空则直接插入即可；否则按照要插入结点指数值的大小在链表中寻找他要插入的位置，对于插入位置有第一个节点、最后一个结点和链表中间这三种情况分别进行处理。函数的形式参数：链表的头地址，指向要插入结点的指针；返回结果：插入结点后新链表的头地址。该函数的算法描述如下：声明指针变量并令它指向连头结点；判断指向要插入结点的指针是否为空；如果是，则不需要插入新结点，直接返回头地址，程序结束；否则再判断链表是否为空；如果是，则直接插入结点，然后返回链表的头地址，程序结束；否则，在链

8、表中寻找待插入结点的插入位置：1，若链表中存在着与“插入的结点”的指数相同的情况，我们依然插入链中，只是把该结点的系数修改为”0”，把链中的结点系数修改为”两系数之和”。(为了方便，我们并没有把结点进行删除的操作，只是在输出的操作里加入权限设置。) 2，若链表中不存在着与“插入的结点”的指数相同的情况，我们正常地插入链中。返回插入结点后链表的头地址，程序结束。4、主函数主函数主要负责输出界面的指引语句，并合理地调用各个函数，还要有适当的循环操作以及停止循环的语句，以致可以方便地达到合并两个一元多项式的功能。四、调试分析（1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析:在输

9、入诸如“0,3”，“2,0”时，程序无法正常运行或总是出错.解决：对指数或系数为0的情况应单独讨论。为此，建立了delZeroCoef函数来解决问题。（2）算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插

10、入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。五、 源程序代码#include<stdlib.h> #include<stdio.h> #include<ctype.h> typedef struct LNode float coef; int expn; struct LNode *next; LNode; LNode* InitPolyn(LNode *La,int n) if(n <= 0) return NULL; LNode *h = La = (LNode*)mall

11、oc(sizeof(LNode), *Lb; La->coef = 0.0; int i; printf("依次输入%d个非零项（每项前一个为系数，后一个为指数）n",n); for (i = 1; i <= n; +i) scanf("%f%d",&La->coef,&La->expn); if(La->coef) Lb = La; La = La->next = (LNode*)malloc(sizeof(LNode); Lb->next = NULL; free(La); return h;

12、 LNode* selsort(LNode *h) LNode *g, *La, *Lb; if(!h) return NULL; float f; int i, fini = 1; for(g = h;g->next&&fini;g = g->next) fini = 0; for(La = h,Lb = h->next;Lb;La = La->next,Lb = Lb->next) if (La->expn < Lb->expn) f = La->coef;i = La->expn; La->coef = L

13、b->coef;La->expn = Lb->expn; Lb->coef = f;Lb->expn = i; fini = 1; for(g = h,La = g->next;La;) if(g->expn=La->expn) g->coef += La->coef; g->next = La->next; Lb = La; La = La->next; free(Lb); else if(g->next) g = g->next; La = La->next; return h; void Pr

14、intfPoly(LNode *La) LNode *Lb = La; if(!Lb) putchar('0'); return; if(Lb->coef!=1) printf("%g",Lb->coef); if(Lb->expn=1) putchar('X'); else if(Lb->expn) printf("X%d",Lb->expn); else if(!Lb->expn) putchar('1'); else if(Lb->expn=1) putcha

15、r('X'); else printf("X%d",Lb->expn); Lb = Lb->next; while (Lb) if(Lb->coef > 0) putchar('+'); if(Lb->coef!=1) printf("%g",Lb->coef); if(Lb->expn=1) putchar('X'); else if(Lb->expn) printf("X%d",Lb->expn); else if(!Lb->

16、;expn) putchar('1'); else if(Lb->expn=1) putchar('X'); else printf("X%d",Lb->expn); Lb = Lb->next; Compare(LNode *a, LNode *b) if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; LNode* AddPolyn(LNode *Pa, LNode *Pb) LNode

17、 *h, *qa = Pa, *qb = Pb, *La, *Lb; float sum; h = La = (LNode*)malloc(sizeof(LNode); La->next = NULL; while (qa && qb) switch (Compare(qa,qb) case -1: La->next = qb; La = qb; qb = qb->next; break; case 0: sum = qa->coef + qb->coef; if (sum != 0.0) La->next = qa; qa->coef

18、 = sum; La = qa; qa = qa->next; else Lb = qa; qa = qa->next; free(Lb); Lb = qb; qb = qb->next; free(Lb); break; case 1: La->next = qa; La = qa; qa = qa->next; break; if (Pa) La->next = qa; if (Pb) La->next = qb; Lb = h; h = h->next; free(Lb); return h; LNode* Add(LNode *Pa, L

19、Node *Pb) int n; puts("再输入1个一元多项式的项数"); scanf("%d",&n); Pb = InitPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); if(Pb && Pb->coef>0) printf(" + "); PrintfPoly(Pb); Pa = AddPolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return

20、Pa; LNode* SubtractPolyn(LNode *Pa, LNode *Pb) LNode *La = Pb; while(La) La->coef *= -1; La = La->next; return AddPolyn(Pa,Pb); LNode* Subtract(LNode *Pa, LNode *Pb) int n; puts("n再输入1个一元多项式的项数"); scanf("%d",&n); Pb = InitPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); p

21、rintf(" - "); putchar('(');PrintfPoly(Pb);putchar(')'); Pa = SubtractPolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; LNode* MultiplyPolyn(LNode *Pa, LNode *Pb) if(!Pb) return NULL; LNode *pa = Pa, *p, *q, *r, *s, *t; r = p = (LNode*)mallo

22、c(sizeof(LNode); while(pa) p->coef = pa->coef; p->expn = pa->expn; q = p; p = p->next = (LNode*)malloc(sizeof(LNode); pa = pa->next; q->next = NULL; free(p); pa = Pa; t = s = (LNode*)malloc(sizeof(LNode); while(pa) q = s; s = s->next = (LNode*)malloc(sizeof(LNode); pa = pa-&g

23、t;next; q->next = NULL; free(s); pa = Pa; while(pa) pa->coef *= Pb->coef; pa->expn += Pb->expn; pa = pa->next; Pb = Pb->next; while(Pb) p = r; s = t; while(p) s->coef = p->coef * Pb->coef; s->expn = p->expn + Pb->expn; p = p->next; s = s->next; Pa = AddPo

24、lyn(Pa,t); Pb = Pb->next; return Pa; LNode* Multiply(LNode *Pa, LNode *Pb) int n; puts("n再输入1个一元多项式的项数"); scanf("%d",&n); Pb = InitPolyn(Pb,n); Pb = selsort(Pb); putchar('(');PrintfPoly(Pa);putchar(')'); printf("×"); putchar('(');Prin

25、tfPoly(Pb);putchar(')'); printf(" = "); Pa = MultiplyPolyn(Pa,Pb); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; void main() LNode *A,*B; char s2; int i,n; printf("tttOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOn"); printf("ttt 一元多项式计算n "); printf("tttOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOn"); printf("ttt # 王伟 #n");puts("n输入1个一元多项式的项数"); scanf("%d",&n); A = InitPolyn(A,n); A = selsort(A); PrintfPoly(A); p: puts(&qu