一元多项式求和

实验二一．学生基本情况：专业班级：学号：姓名：二．实验题目、实验内容1、实验目的：（1）熟练掌握链表结构及有关算法的设计；（3）掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。2、实验内容：一元多项式求和。把任意给定的两个一元多项式P(x),Q(x)输入计算机，计算它们的和并输出计算结果。三．设计分析先构造两个项链表，分别存储两个多项式的系数和指数，然后将每个链表按指数的大小从小到大排列，以便于后来的合并。合并的伪代码如下：当然，多项式的输出也不简单，要考虑系数是否为1，为1时x前的系数不显示，指数是否为1，为1时也不显示。还有最前面的项如果系数为正，则不显示+号。四．源程序代码#includestdio.h#includestdlib.h#defineM50typedefstructnode//项节点{1.工作指针p、q初始化；2.while（p存在且q存在）执行下列三种情形之一2.1如果p-expq-exp，则指针p后移;2.2如果p-expq-exp，则2.2.1将结点q插入到结点p之前；2.2.2指针q指向原指结点的下一个结点；2.3如果p-exp=q-exp，则2.3.1p-coef=p-coef+q-coef；2.3.2如果p-coef==0，则执行下列操作，否则，指针p后移;2.3.2.1删除结点p；2.3.2.2使指针p指向它原指结点的下一个结点；2.3.3删除结点q；2.3.4使指针q指向它原指结点的下一个结点；3.如果q不为空，将结点q链接在第一个单链表的后面；floatcoef;//系数floatexp;//指数node*next;//下一节点}Linode;voidInitlinode(Linode*&L)//初始化{L=(Linode*)malloc(sizeof(Linode));L-coef=L-exp=0;L-next=NULL;}voidCreatelinode(Linode*&L,intn)//建立项链表{Linode*p,*s=L;inti;for(i=0;in;i++){printf(输入第%d个数的系数和指数:\n,i+1);p=(Linode*)malloc(sizeof(Linode));scanf(%f%f,&(p-coef),&(p-exp));s-next=p;p-next=NULL;s=p;}}voidDestroylinode(Linode*&L)//销毁链表{Linode*p=L,*s=L-next;while(s!=NULL){free(p);p=s;s=s-next;}free(p);}boolSort(Linode*&L)//排序{Linode*p,*pre,*q;if(L-next==NULL)return0;p=L-next-next;L-next-next=NULL;while(p!=NULL){q=p-next;pre=L;while(pre-next!=NULL&&pre-next-expp-exp)pre=pre-next;p-next=pre-next;pre-next=p;p=q;}return1;}boolPlus(Linode*&A,Linode*&B)//合并多项式{Linode*p=A-next,*q=B-next,*r=A,*s;if(q==NULL)return0;while(p!=NULL&&q!=NULL){s=q-next;if(p-expq-exp){while(p!=NULL&&p-expq-exp){p=p-next;r=r-next;}}if(p!=NULL&&p-expq-exp){r-next=q;q-next=p;r=q;q=s;if(s!=NULL)s=s-next;}if(p!=NULL&&q!=NULL&&p-exp==q-exp){p-coef=p-coef+q-coef;if(p-coef==0){r-next=p-next;free(p);p=r-next;}else{p=p-next;r=r-next;}free(q);q=s;}}if(q!=NULL)r-next=q;return1;}voidDisplinode(Linode*&L){Linode*p=L-next;while(p!=NULL){if(p-exp==0)printf(%.4f,p-coef);elseif(p==L-next&&p-coef=0){if(p-coef==1){if(p-exp==1)printf(x);elseprintf(x^%.2f,p-exp);}else{if(p-exp==1)printf(%.4fx,p-coef);elseprintf(%.4fx^%.2f,p-coef,p-exp);}}else{if(p-coef=0){if(p-coef==1){if(p-exp==1)printf(+x);elseprintf(+x^%.2f,p-exp);}else{if(p-exp==1)printf(+%.4fx,p-coef);elseprintf(+%.4fx^%.2f,p-coef,p-exp);}}else{if(p-coef==-1){if(p-exp==1)printf(-x);elseprintf(-x^%.2f,p-exp);}else{if(p-exp==-1)printf(%.4fx,p-coef);elseprintf(%.4fx^%.2f,p-coef,p-exp);}}}p=p-next;}printf(\n);}voidmain(){intm,n;Linode*A;Linode*B;Initlinode(A);Initlinode(B);printf(输入P(x)的项数:);scanf(%d,&m);Createlinode(A,m);if(Sort(A)==1)printf(排序成功\n);printf(P(x)=);Displinode(A);printf(输入Q(x)的项数:);scanf(%d,&n);Createlinode(B,n);if(Sort(B)==1)printf(排序成功\n);printf(Q(x)=);Displinode(B);if(Plus(A,B)==1)printf(表达式为F(x)=);Displinode(A);Destroylinode(A);}五．测试用例（尽量覆盖所有分支）六．实验总结对于这个实验，我最开始的想法是输入字符串，然后将字符串拆分成几个项存入链表中，然后再排序，合并。用到了switch语句，对‘+’号，‘x’，‘-’，和数字进行处理。要考虑的问题有很多，比如说如果x的系数是1，则它前面的1不会输到字符串表达式中，同理，x的系数为1是也要特殊处理。顺着这个思路写完后别人一句话提醒了我，那就是如果指数为浮点数怎么办，后来我也想到如果系数也是浮点数那就更处理不了了。我的那个程序只能用于系数和指数是整数，而且是一位整数的。想到这里，只有改变做法，把表达式的项数的系数和指数一项一项输入，这样就很容易建立链表了。然而修改好后任不能合并，用单步执行调试，错误出在合并的那个程序里面。修改了之后有的式子跑的了，而交换位置之后就出错了。再调试，还是出现在合并的那个程序，还是指针的问题，后来终于发现如果p-nextq-next这句的问题，如果p=NULL,那么p-next显然没有意义，所以老是出错，最后加了些限定条件，终于也就成功了。这次试验我学到的不仅是链表，更重要的是指针，相信以后遇到类似的错误可以很快的处理。