《一元稀疏多项式的加法运算(数据结构实习)》由会员分享，可在线阅读，更多相关《一元稀疏多项式的加法运算(数据结构实习)（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+x200) （3）
2、(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)一需求分析1. 输入的形式和输入值的范围：输入是从键盘输入的，输入的内容为多项式的系数和指数，其中多项式的每一项分别以一个系数和指数的形式输入，不带未知数X，系数为任意的实数，指数为任意的整数。要结束该多项式的输入时，输入的指数和系数都为0.2. 输出的形式 从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值，并且多项式中将未知数X表示了出来. 形式为：+c1Xe1+c2Xe2+ciXei+(ci和ei分别是第i项的系数和指数，序列按指数升序排列。) 当多项式的某一项的系数为+1或者-1时 侧
3、该项多项式的输出形式为Xei或-Xei； 当该项的系数为正时输出+ciXei,当为负数时则输出ciXei3. 程序所能达到的功能 输入并建立多项式，实现一元稀疏多项式的相加并输出。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,*p,*q,*s,*r;float x;p=he
5、ada; /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-next;p=p-next; /指向多项式的下一项/else if(p-eq-e)
6、 /多项式按升幂排序/s=(pnode *)malloc(sizeof(pnode);s-c=q-c;s-e=q-e;r-next=s;r=s;q=q-next;elses=(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-next=s;r=s;p=p-next;while(q!=NULL) /第二个式子不为0的相加法则/s=(pnode *)mal
7、loc(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() /*此函数时用来创建多项式的*/ void display(pnode *head) /*head为每个多项式的头指针*/ pnode * add(
8、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!=NULL) /判断头结点非空/if(one_time=1)if(p-e=0) /当指数为0即Xo时只需要输出系数c/printf(%f,p-c); else i
9、f(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;elseif(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);e
10、lse 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(); /调用创建函数，创建第一个多项式/ printf(input the second:n); /输入第二个多项式/b=creat(); /调用创建函数，创建第二个多项式/ c=add(a,b); /调用相加函数/printf(the first:);display(a); /输出第一个多项式/ printf(the second:
