《一元稀疏多项式的加法运算(数据结构实习).pdf》由会员分享，可在线阅读，更多相关《一元稀疏多项式的加法运算(数据结构实习).pdf（11页珍藏版）》请在三一文库上搜索。
1、实习一线性表、栈和队列及其应用一元稀疏多项式的加法运算【问题描述】设计一个实现一元稀疏多项式相加运算的演示程序。【基本要求】（ 1）输入并建立两个多项式；（ 2）多项式a 与 b 相加，建立和多项式c；（ 3）输出多项式a,b,c。输出格式：比如多项式a 为： A(x)=c1xe1+ c2xe2+ + cmxem ，其中， ci 和 ei 分别为第i 项的系数和指数，且各项按指数的升幂排列，即0e1e2em。多项式b,c 类似输出。【测试数据】（ 1）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) （ 2）(x+x100)+(x100+x200)=(x+2x100
2、+x200) （ 3）(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) 一需求分析1.输入的形式和输入值的范围：输入是从键盘输入的，输入的内容为多项式的系数和指数，其中多项式的每一项分别以一个系数和指数的形式输入，不带未知数X，系数为任意的实数，指数为任意的整数。要结束该多项式的输入时，输入的指数和系数都为0.2. 输出的形式从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值，并且多项式中将未知数X表示了出来 . 形式为：+c1Xe1+c2Xe2+ciXei+ (ci 和ei 分别是第 i项的系数和指数，序列按指数升序排列。) 当多项式的某
3、一项的系数为+1或者 -1 时 侧该项多项式的输出形式为Xei 或-Xei ；当该项的系数为正时输出+ciXei,当为负数时则输出ciXei 3. 程序所能达到的功能输入并建立多项式，实现一元稀疏多项式的相加并输出。4. 注意： 所有多项式都必须以指数升密形式输入。5. 测试数据为（ 1） (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) （ 2）(x+x100)+(x100+x200)=(x+2x100+x200) （ 3）(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) 二设计1.设计思路（1）.储存结构：链式存储（2）.
4、主要算法基本思路首先定义一个多项式的结构体，存放多项式每一项的系数和指数以及next 指针；然后定义两个指针，第一个指针指向第一个多项式，第二个指针指向第二个多项式。然后比较两个多项式第一项的指数的大小，如果两个多项式的指数相同，则将他们的系数相加，指数不变；如果不同则比较他们指数的大小，并将指数小的放在第一项。然后指向指数小的那一项的指针后移，它的指数去和刚才必然的那一项的指向相比较,直至两个多项式相加完。其中如果某二项的系数相加后为0，则该项不输出。相加时的程序如下：pnode * add(pnode *heada,pnode *headb) /多项式相加 / pnode *headc,*
5、p,*q,*s,*r; float x; p=heada; /p 指针指向第一个多项式的第一项/ q=headb; /q 指针指向第二个多项式的第一项/ headc=(pnode *)malloc(sizeof(pnode); /为两式相加的结果c 申请内存 / r=headc; /r 指向结果 / while(p!=NULL&q!=NULL) /判断两个式子都合法/ if(p-e=q-e ) /指数相同时系数相加/ x=p-c+q-c; if(x!=0) s=(pnode *)malloc(sizeof(pnode); s-c=x; s-e=p-e; r-next=s; r=s; q=q-n
6、ext;p=p-next; /指向多项式的下一项/ else if(p-eq-e) /多项式按升幂排序/ s=(pnode *)malloc(sizeof(pnode); s-c=q-c; s-e=q-e; r-next=s; r=s; q=q-next; else s=(pnode *)malloc(sizeof(pnode); s-c=p-c; s-e=p-e; r-next=s; r=s; p=p-next; while(p!=NULL) /第一个式子不为0 时的相加法则 / s=(pnode *)malloc(sizeof(pnode); s-c=p-c; s-e=p-e; r-nex
7、t=s; r=s; p=p-next; while(q!=NULL) /第二个式子不为0 的相加法则 / s=(pnode *)malloc(sizeof(pnode); s-c=q-c; s-e=q-e; r-next=s; r=s; q=q-next; r-next=NULL; headc=headc-next; /c 的指向依次指向下一项/ return headc; /返回两式相加的结果/ 2.设计表示（1）函数调用关系图main-create()-create()-add()-display()-display()-display() （2）函数规格接口说明pnode * creat
8、() /* 此函数时用来创建多项式的*/ void display(pnode *head) /*head 为每个多项式的头指针*/ pnode * add(pnode *heada,pnode *headb) /* heada headb 为两个多项式的头指针*/ 3.实现注释（1）根据提示输入多项式每一项的指数和系数，结束该多项式的输入时系数和指数都应该输入 0。（2）可以输入任何指数型式的多项式。4.详细设计（主要算法的细化）输出函数如下：void display(pnode *head) /多项式输出 / pnode *p;int one_time=1; p=head; while(p
9、!=NULL) /判断头结点非空/ if(one_time=1) if(p-e=0) /当指数为 0即 Xo 时只需要输出系数c/ printf(%f,p-c); else if(p-c=1) /系数为 1 时输出 Xei/ printf(x%d,p-e); else if(p-c=-1 ) /系数为 -1 时输出 -Xei/ printf(-x%d,p-e); else if(p-c0) /系数大于 0 时系数前面带“+”/ printf(+%fx%d,p-c,p-e); else if(p-cc,p-e); one_time=0; else if(p-e=0) if(p-c!=0) pri
10、ntf(+%f,p-c); else if(p-c=1) /系数为 1 时输出 Xei/ printf(+x%d,p-e); else if(p-c=-1 ) /系数为 -1 时输出 -Xei/ printf(-x%d,p-e); else if(p-c0) /系数大于 0 时系数前面带“+”printf(+%fx%d,p-c,p-e); else if(p-cc,p-e) p=p-next; printf(n); 主函数如下：void main() pnode * a,*b,*c; /定义三个多项式/ printf(input the first:n); /输入第一个多项式/ a=creat
11、(); /调用创建函数，创建第一个多项式/ printf(input the second:n); /输入第二个多项式/ b=creat(); /调用创建函数，创建第二个多项式/ c=add(a,b); /调用相加函数 / printf(the first:);display(a); /输出第一个多项式/ printf(the second:);display(b); /输出第二个多项式/ printf(sum is:);display(c); /输出两多项式相加的结果/ 相加部分见算法设计部分。三调试分析1.调试遇到的主要问题以及解决方案：a 刚写程序时输出时没有分系数大于0 和小于0 分，
12、输出的形式都为printf( “ %fX%d ” , p-c,p-e ),结果两个多项式相加时当某相邻两项时，中间的加号没有表示出来。所以我就将系数分为大于0和小于0来分，输出形式为if(p-c0)printf(+%fx%d,p-c,p-e);else if(p-cc,p-e); b 刚开始多项式输入时没有按升幂的形式输入，结果运行的结果怎么都不对，然后将它按升幂的形式输入后就可以了。c 刚开始时没有考虑结束多项式的输入时该则么弄，结果运行时一直都在输入第一个多项式，怎么都结束不了，直到将结束位的系数和指数都设置为0 时才解决了这个问题。2.时间和空间复杂度的分析：时间复杂度为：O（n）空间复
13、杂度为：O（n）3 改进设想A 由于两个多项式的某两项相加为0 时是不输出数的，所以当两个多项式相加为0 时，结果什么都不输出为空值，一直想办法改进，却没有什么结果，所以想在这方面改进一下；B 由于多项式的系数为正时，输出的形式中带有一个“+” ，所以当多项式的第一项的系数为正值时总会带有一个“+” ，觉得很别扭。但如果输出形式中不带“+” ，结果中两个不同项之间有没有“+” ，与偶以很苦恼。C 由于没有菜单函数，所以每次只能显示本次相加的两的多项式，而不能显示前一次货前几次的多项式，所以想在此方面做一些改进，产生一个菜单， 包括：进去多项式相加程序帮助功能.退出。让用户在没有退出之前都能看见
14、每一次多项式相加的过程和结果，并在不懂的时候能获得帮助。4 .经验与体会：一直都知道C 语言学的很差，但是最基本的编程还是能完成的，但是这次实习让我知道原来的我的编程能力是如此之差，它让我很深刻的认识到我的基础功没有打扎实，我还要多下功夫。学数据结构式好多东西都是纸上谈兵，以为懂了， 结果上机的时候什么都不知道。这次实习也让我认识到时间的重要性，我知道光有利临时没有用的，必须将理论与实际结合起来。四运行结果验证 （1）(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5) 截图为验证（2）(x+x100)+(x100+x200)=(x+2x100+x200) 截图为验证（
15、3）(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11) 截图为六源程序清单#include#include #include #include typedef struct pnode /定义结构体 / float c; /系数 / int e; /指数 / struct pnode *next; /指向多项式下一项的指针/ pnode; pnode * creat() /创建多项式 / int m;float n; pnode *head,*rear,*s; head=(pnode *)malloc(sizeof(pnode); /申请内存空间 / rea
16、r=head; printf(input c:); scanf(%f,&n); /输入系数 / printf(input e:); /输入指数 / scanf(%d,&m); while(n!=0) /当系数不为0 时输入多项式/ s=(pnode *)malloc(sizeof(pnode); /申请内存空间/ s-c=n; s-e=m; s-next=NULL; /next 指针置空 / rear-next=s; /定义 next 指针 / rear=s; printf(input c:); scanf(%f,&n); /输入下一项的系数/ printf(input e:); scanf(
17、%d,&m); /输入下一项的指数/ head=head-next; return head; /返回头结点 / void display(pnode *head) /多项式输出 / pnode *p;int one_time=1; p=head; while(p!=NULL) /判断头结点非空/ if(one_time=1) if(p-e=0) /当指数为 0即 Xo 时只需要输出系数c/ printf(%f,p-c); else if(p-c=1) /系数为 1 时输出 Xei/ printf(x%d,p-e); else if(p-c=-1 ) /系数为 -1 时输出 -Xei/ pri
18、ntf(-x%d,p-e); else if(p-c0) /系数大于 0 时系数前面带“+”/ printf(+%fx%d,p-c,p-e); else if(p-cc,p-e); one_time=0; else if(p-e=0) if(p-c!=0) printf(+%f,p-c); else if(p-c=1) /系数为 1 时输出 Xei/ printf(+x%d,p-e); else if(p-c=-1 ) /系数为 -1 时输出 -Xei/ printf(-x%d,p-e); else if(p-c0) /系数大于 0 时系数前面带“+”printf(+%fx%d,p-c,p-e
19、); else if(p-cc,p-e) p=p-next; printf(n); pnode * add(pnode *heada,pnode *headb) /多项式相加 / pnode *headc,*p,*q,*s,*r; float x; p=heada; /p 指针指向第一个多项式的第一项/ q=headb; /q 指针指向第二个多项式的第一项/ headc=(pnode *)malloc(sizeof(pnode); /为两式相加的结果c 申请内存 / r=headc; /r 指向结果 / while(p!=NULL&q!=NULL) /判断两个式子都合法/ if(p-e=q-e
20、 ) /指数相同时系数相加/ x=p-c+q-c; if(x!=0) s=(pnode *)malloc(sizeof(pnode); s-c=x; s-e=p-e; r-next=s; r=s; q=q-next;p=p-next; /指向多项式的下一项/ else if(p-eq-e) /多项式按升幂排序/ s=(pnode *)malloc(sizeof(pnode); s-c=q-c; s-e=q-e; r-next=s; r=s; q=q-next; else s=(pnode *)malloc(sizeof(pnode); s-c=p-c; s-e=p-e; r-next=s; r
21、=s; p=p-next; while(p!=NULL) /第一个式子不为0 时的相加法则 / s=(pnode *)malloc(sizeof(pnode); s-c=p-c; s-e=p-e; r-next=s; r=s; p=p-next; while(q!=NULL) /第二个式子不为0 的相加法则 / s=(pnode *)malloc(sizeof(pnode); s-c=q-c; s-e=q-e; r-next=s; r=s; q=q-next; r-next=NULL; headc=headc-next; /c 的指向依次指向下一项/ return headc; /返回两式相加
22、的结果/ void main() pnode * a,*b,*c; /定义三个多项式/ printf(input the first:n); /输入第一个多项式/ a=creat(); /调用创建函数，创建第一个多项式/ printf(input the second:n); /输入第二个多项式/ b=creat(); /调用创建函数，创建第二个多项式/ c=add(a,b); /调用相加函数 / printf(the first:);display(a); /输出第一个多项式/ printf(the second:);display(b); /输出第二个多项式/ printf(sum is:);display(c); /输出两多项式相加的结果/