数据结构课程设计一元多项式

1、湖南工学院课程设计一元多项式计算班级：信息本1002学号： 09姓名：班级：信息本1002学号：26姓名：班级：信息本1002学号：34姓名：班级：信息本1002学号：41姓名：目 录一、课题任务1二、概要设计1三、详细设计2四、调试分析6五、测试结果6六、课程设计总结9七、参考文献9八、附录10一、课题任务功能： 1）能够按照指数降序排列建立并输出多项式； 2）能够完成两个多项式的相加，并将结果输出； 3）能根据输入的多项式及变量的值，能进行计算。并输出计算结果。 4）能对多个输入的表达式按照指数大小排序输出。二、概要设计一元多项式计算系统降序排列建立并输出多项式多项式的相加减并输出结果输入

2、的多项式及变量的值计算多个表达式按照指数大小排序输出按指数排序建立多项式相减建立多项式相加计算多项式建立多个多项式输出多式项或计算值排序后输出多个多项式排序三、详细设计一元多项式定义系数和指数结构如下： coefexpnnextcoef域-存放结点的系数值expn域-存放结点的指数值next域-存放结点的直接后继的地址（位置）的指针域（链域）一元多项式单链表存储结构：typedef struct term float coef; /系数 int expn; /指数 struct term *next; term;有了链表特定的数据类型term，接下来就需要建立这个链表。这里我们自定义一个构造函

3、数CreatePoly（）来构造链表。首先定义一个term型的指针变量h=p作为头结点，存储多项式的信息（项数），为h分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用malloc()函数来实现；这时输入多项式的项数m，先给p的coef赋值为0，此时利用一个for循环将p链表的coef与expn值从键盘输入，用m来控制循环的次数，若该从键盘输入的coef值不为0，则将该数值插入链表新建链表q，用malloc（）分配给p空间，p=p->next继续从键盘输入coef与expn的值，直到满足p->next=null,输入完成，返回链表q即为多项式的系数与指数，创建多项式完成。在

4、处理多项式相加的问题上，由于事先建立的多项式函数已经按指数大小排好序，那么多项式的相加就变得不那么复杂了，我们只要找出两个相加多项式指数相同的项进行合并，即将指数相同的项的系数相加，其它的保持不变存好即可。而查找指数相同的项，只要按链表从头到尾进行扫描，若发现相同，则两个同时往下移，否则只将其中指数较大的往下移。假若两个指数相同的项进行合并时，其系数相加值为0，则消除该项，继续下去。在处理输入的多项式及变量的值计算结果的问题时，定义一个C（）函数实现，需要定义一个float变量sum来存储和值，再引用一个pow()函数来计算多项式的和，利用一个for循环来一一计算x的q->expn次方后

5、与q->coef相乘的值，并存储在sum中，q=q->next，直到q->next =unll，跳出for循环，返回 sum的值就是多项式在用x赋值后的值。对多个输入的表达式按照指数从大到小排序输出:，利用一个for（包含两个函数CreatPolyn(M,n);selsort(M);）循环，用scanf()输入k来控制for的次数可控制输入的多项式个数，并一个trem型数组Gi来保存每一个多项式，方便后来的按最高指数大小排序。排序的思想利用枚举排序法可将每个多项式最高次expn按从大到小排列并保存在Gi数组中，再次利用for将排序好的Gi多项式按指数从大到小输出。开始具体子功

6、能流程图如下：输入变量x的值Nq不空Ysum+=q->coef*pow(x,q->expn)q=q->nextreturn sum;完成多项式计算输出多项式的计算开始从键盘输入项数mm<=0返回空定义存储多项式数据类型term动态分配空间完成建立多项式降次排序输出YN 多项式的建立 按指数排序将k个有序多项式用数组G i保存输入多项式个数k输出开始开始定义存储和链表h动态分配空间Pb=Pb->coef*(-1)两多项式相加输出Pb？Pb=pb->nextYN 多个多项式排序 多项式相减 定义存储和链表h动态分配空间Pa&&Pb?C=a->

7、;expn - b->expnh=UNLL返回系统C>=1C>=0h=Pb Pb = Pb->next;h=Pa Pa = Pa->next;sum = Pa->coef + Pb->coef;sum=0Pa->coef = sum;h=Pa;Pa=Pa->next;Pa = Pa->next;Pa=0Pb=0h->next = Pa;h->next = Pa;h = h->next;Return hNYNYNYNYYNYYNN输出开始完成多项式相加调用函数查找同类项同类项系数相加进行合并合并后检查a b扫描是否完整

8、输出多项式q流程图：putchar(1)printf(“x%d”,q->expn)Putchar(x)q->expn=0p=p->nextputchar (0);开始printf(“%g”,q->coef)q!=UNLLq->coef!=1q->expn=1q->coef>=0q!=UNLLPutchar(+)退出 N Y N Y Y N Y N Y N Y N多项式输出主要是对已建立的多项式按链表从头到尾扫描指数跟系数进行多重判断，根据指数和系数输出相应的数值与符号，直到多项式输出完成。四、调试分析程序的调试是程序顺利完成中非常关键的一步。通过

9、程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，运行结果输出是否正确。决定程序成功与否的第一步是定义的CreatPolyn()函数操作是否正确，如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作是由Delet()与free()函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是函数相加，控制此操作的关键是一个A ()函数，其中调用APolyn（）函数是决定成功与否的关键，而函数的相减正是相加一个负数，将减数多项式的

10、coef变为负值便实现了多项式的相减。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。对于根据输入的多项式及变量的值进行计算，控制此操作的关键是如何计算多项式中多次方的值，此操作关键是一个C()函数，调用pow()函数来实现计算次方的功能，其中sum值的计算是否正确起关键作用。而对多个输入的表达式按照指数从大到小排序输出，这个主要是用到了一个trem型数组对各已按指数排序好的多项式保存，然后对数组中的每个多项式的第一个p->expn值利用枚举排序法进行比较将多项式排序。各个关键部分都已检查完毕，剩下的就是对程序的

11、进一步细心的完善化、美观化、清晰化直到满足要求。下面我们分析一下程序的性能。在主函数中，首先调用构造单链表函数CreatePoly()，在这个函数中需要通过一个for循环为每个结点分配存储空间，变换节点的next域，时间复杂度为O（n）。接下来执行selsort()函数对多项式进行按指数排序，其中一个双重for循环，在内部的for循环中是对相邻结点指数大小比较进行操作，所以每个结点的操作都需要m次，共n个结点，则需要mn次操作，时间复杂度为O（nn）。其后的for循环是比较将指数相同的数进行合并，时间复杂度为O（n）。五、测试结果系统选择界面如图 6-1图6-1测试按照指数降序排列输出多项式

12、8*x1+9*x0+7*x2+6*x3 输入数据为：1（enter）4（enter）8 1 9 0 7 2 6 3（enter）输出结果为：6*x3+7*x2+8*x1+9测试结果如图6-2图6-2测试两个多项式相加8*x1+9*x0+7*x2+6*x3; 0*x0+1*x3+5*x2；输入数据为：2（enter）4（enter）8 1 9 0 7 2 6 3 （enter）3（enter）0 0 1 3 5 2（enter）输出结果为：7x3+12x2+8x+9测试结果如图6-3图6-3输入的多项式及变量的值计算结果测试测试多项式4x3+5x4+6x1+7x0 当x值为2.5时的值为279.

13、8125输入数据为：4（enter） 4（enter）4 3 5 4 6 1 7 0（enter）2.5（enter）测试结果如图6-4图6-4测试对多个输入的表达式按照指数从大到小排序输出测试多项式8*x1+9*x0+7*x2+6*x3; 0*x0+1*x3+5*x2；4x3+5x4+6x1+7x0输入数据为：5（enter） 3（enter） 4（enter） 8 1 9 0 7 2 6 3 （enter）3（enter） 0 0 1 3 5 2 （enter）4（enter） 4 3 5 4 6 1 7 0 （enter）输出结果为：5x4+4x3+6x+7； 6*x3+7*x2+8*x

14、 +9；x3+5*x2数组测试结果如图6-5图6-5六、课程设计总结计算一元多项式加法，其结果取决于多项式的各项系数与指数，因此程序核心是处理两个多项式的系数与指数。定义结构体将多项式的各项系数与指数存放，定义结构体类型链表为程序的循环控制提供了可能，利用对链表的运算来确定结果多项式的各项系数与次数，同理算出相应的幂数。链表是在计算机内存中使用一组连续的存储单元保存数据类型和名字相同的变量。就链表这种数据类型而言，在排列上采用的方法也是按序排放，先存放第一行，接着存放第二行，直到所有数据元素被存放。多项式采用的是链表形式，以牺牲一定的空间提高程序的运行速度和可行性。算法思想：采用链式结构存储多

15、项式，用链表结构体的一个域标记多项式的次数，另一个域标记多项式的系数，程序中采用的是m表示最高次系数，进行加法运算时，标记系数域相加即为相加的对应系数，标记指数域相同则表示为同类项。链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。链表顾名思义，要把各个元素链接起来才算撒。通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。本次课程设计，我查找过资料，请教过同学，以及不懈的努力，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在程序设计中，我学会了很多学习的方法，而这是日后最实用的，真的是受益匪浅。本学期的程序设计课程，我锻炼了能

16、力，学到很多东西，比如思考问题的角度也会从多方面着手；对自己的专业也有自己的想法在和同学的交流过程中，互动学习，将知识融会贯通。通过这次课程设计，我对很多的函数有了新的认识，也学会了运用多种函数，我也明白了写软件的基本过程和基本方法。在程序的设计过程中遇到拉很多的困难，在程序一次一次的调试失败下曾经想过要放弃，我最后还是让自己坚持啦下来，毫不畏惧困难，在同学的帮助与讲解下我总算是顺利的完成了程序的课程设计。在这几天的编写过程中我对语言有了更进一步的认识和了解，也感受到了编程给我带来的快乐与充实，明白了想成为一个合格的甚至是优秀的程序员，我还需要更多更难的锻炼。所以我还要不断地学习不断地说活，不

17、断地成长，为我的理想而奋斗。七、参考文献1） 严蔚敏 吴伟民 数据结构(C语言版) 清华大学出版社.2006.2） 恰汗 合孜尔 C语言程序设计 中国铁道出版社2009.3） 杨永斌 数据结构(理论与实践). 天津科学技术出版社4） 百度资料八、附录#include<stdlib.h>#include<stdio.h> #include<ctype.h> #include<iostream>#include<math.h>#define null 0#define W 10using namespace std;typedef str

18、uct term /项的表示，多项式的项作为LinkList的数据元素 float coef; /系数 int expn; /指数 struct term *next; term; int Empty(term *L) if(L->next!=null) return 1; return 0;void Delete(term * L,term * p) term * s,*q; s=L; q=L->next; while(p!=q) s=q; q=q->next; s->next=q->next; free(q); term* CreatPolyn(term *P

19、,int m) / 输入m项的系数和指数，建立表示一元多项式的有序链表P if(m <= 0) return NULL; term *h = P = (term*)malloc(sizeof(term), *q; P->coef = 0.0; int i; printf("依次输入%d个数（前一个为系数，后一个为指数）n",m*2); for (i = 1; i <= m; +i) / 依次输入m个非零项 scanf("%f%d",&P->coef,&P->expn); if(P->coef) q =

20、P; /若该系数值不为0，则p数值插入链表qP = P->next = (term*)malloc(sizeof(term); q->next = NULL; free(P); return h; / CreatPolyn term* selsort(term *h) /将有序链表进行指数排列term *g, *p, *q; if(!h) return NULL; float f; int i, fini = 1; for(g = h;g->next&&fini;g = g->next) /确定排序需要扫描的次数 fini = 0; for(p = h,

21、q = h->next;q;p = p->next,q = q->next) /相邻的指数进行比较，一次循环将最小指数排到最后，若两两比较没交换，则.if (p->expn < q->expn) /将链表中的元素按指数从高到低排列 f = p->coef;i = p->expn; p->coef = q->coef;p->expn = q->expn; q->coef = f;q->expn = i; fini = 1; for(g = h,p = g->next;p;) /比较将指数相同的数进行合并 i

22、f(g->expn=p->expn) g->coef += p->coef; g->next = p->next; /合并后跳过一个元素，并删除该结点 q = p; p = p->next; free(q); else if(g->next) g = g->next; p = p->next; return h; void PrintfPoly(term *P) /输出按指数从大到小排列后的一元多次式term *q = P; if(!q) putchar('0'); return; if(q->coef!=1)

23、printf("%g",q->coef); /%g用来输出实数，它根据数值的大小，自动选f格式或e格式，且不输出无意义的0 if(q->expn=1) putchar('X'); /若指数值大小为1，则指数省略 else if(q->expn) printf("X%d",q->expn); else if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d"

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

25、tchar('X'); else printf("X%d",q->expn); q = q->next; int Compare(term *a, term *b) if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; float C(term *c,float x) /计算输入变量的多项式的值 float sum=0,a; int b; term *q=c; for(;q ;q=q->next) a=q-

26、>coef ;b=q->expn ; sum+=a*pow(x,b); return sum;term* APolyn(term *Pa, term *Pb) / 多项式加法：Pa = PaPb，利用两个多项式的结点构成"和多项式"。 term *h, *qa = Pa, *qb = Pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term); p->next = NULL; while (qa && qb) / Pa和Pb均非空 switch (Compare(qa,qb) case

27、 -1: / 多项式PA中当前结点的指数值小 p->next = qb; p = qb; qb = qb->next; break; case 0: / 两者的指数值相等 sum = qa->coef + qb->coef; if (sum != 0.0) / 修改多项式PA中当前结点的系数值 p->next = qa; qa->coef = sum; p = qa; qa = qa->next; else / 删除多项式PA中当前结点 q = qa; qa = qa->next; free(q); q = qb; qb = qb->nex

28、t; free(q); break; case 1: / 多项式PB中当前结点的指数值小 p->next = qa; p = qa; qa = qa->next; break; / 结束switch / 结束while if (Pa) p->next = qa; / 链接Pa中剩余结点 if (Pb) p->next = qb; / 链接Pb中剩余结点 q = h; h = h->next; free(q); return h; / APolyn term* A(term *Pa, term *Pb) int n; printf("请输入第二个一元多项式

29、的项数: "); scanf("%d",&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); cout<<"两个多项式相加结果为："PrintfPoly(Pa); if(Pb && Pb->coef>0) printf(" + "); PrintfPoly(Pb); Pa = APolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa

30、; term* BPolyn(term *Pa, term *Pb) / 多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成"差多项式"。 term *p = Pb; while(p) p->coef *= -1; p = p->next; return APolyn(Pa,Pb); / BPolyn term* B(term *Pa, term *Pb) int n; printf("请输入第二个一元多项式的项数: ");scanf("%d",&n); Pb = CreatPolyn(Pb,n); Pb

31、= selsort(Pb); cout<<"两个多项式相减结果为："PrintfPoly(Pa); printf(" - "); putchar('(');PrintfPoly(Pb);putchar(')'); Pa = BPolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; void main() term *M,*N; term *q;int i,j,n; float x,y; term *G

32、W;int k; f: puts("t= 一元多项式计算系统：="); printf("nttt1:按照指数降序排列输出多项式nttt2:一元多项式的加法运算"); printf("nttt3:一元多项式的减法运算nttt4:输入的多项式及变量的值计算结果"); puts("nttt5:对多个输入的表达式按照指数从大到小排序输出nttt0:退出系统"); puts("t="); printf("n请选择您要进行的操作：");cin>>i;switch(i) cas

33、e 1:printf("nttt按照指数降序排列输出多项式:n请输入该一元多项式的项数: "); scanf("%d",&n); M = CreatPolyn(M,n); M = selsort(M); cout<<"您输入的多项式按指数降序排列为： "PrintfPoly(M);cout<<endl<<endl; goto f;case 2: printf("nttt一元多项式加法计算:n请输入第一个一元多项式的项数: "); scanf("%d",&n); M = CreatPolyn(M,n); M = selsort(M); M = A(M,N); cout<<endl<<endl;goto f; case 3: printf