一元多项式的运算-实验报告和代码

一．问题描述：设Pn(x)和Qm(x)分别两个一元多项式。试编写程序实现一元多项式的加法运算。二．需求分析：1.本程序需要基于线性表的基本操作来实现一元多项式的加法，也可以用数组实现。2．两个多项式都有键盘输入相应的系数和指数。3．//第一个多项式为9x15+7x8+5x3+3x输入4//表示第一个多项式的项数9，15（回车）//表示9x157，8（回车）5，3（回车）3，1（回车）输出9x^15+7x^8+5x^3+3x^1//第二个多项式为-7x8+6x3+2输入3//表示第二个多项式的项数6，3（回车）//表示9x15-7，8（回车）2，0（回车）输出-7x^8+6x^3+2x^0求和结果9x^15+11x^3+3x^1+2x^0三．概要设计抽象数据类型：为实现上述程序的功能，应以整数存储用户的输入，以及计算的结果。实现多项式的运算，利用数组的方式需开辟一个二维数组，利用链表的方式须创造两个链表。算法的基本思想：数组实现：定义一个结构体数组,p存储系数,q存储指数。分别输出两次输入的多项式。将两次输入的多项式的指数按从大到小的顺序进行排列，同时相应的系数要进行交换。输出时如果进行判断。如果当前该项与下一项的的系数相同，将两项系数相加后输出，并跳过下一项。如果不相等，直接输出。输出时需注意的问题：当系数为0时，该项不输出当系数为负数时，不要再在前面输出+。链表实现：定义一个结构体，分别用exp，coef来存储系数和指数，同时在结构体里面定义一个该结构类型指针。对输入的第一个多形式和第二个多项式分别构建一个链表（按指数的大小）输出时，通过比较两个链表当前位置的指数大小，相同，系数相加后输出，两个链表同时向前推进。如果其中一个大，只输出较大项，同时将其推进。程序的流程：（1）输入模块：完成两个多项式的输入。（2）处理模块：将多项式按其指数大小进行排列。（3）输出模块：输出合并后的多项式。四．详细设计：算法的具体步骤：数组方法structcode{intp,q;}a[1000],b[1000];//结构体数组，可以用二维数组代//替for(i=0;in;i++){for(j=i+1;jn;j++){if(a[j].qa[i].q){temp=a[j].q;//指数排序a[j].q=a[i].q;a[i].q=temp;temp=a[j].p;//系数跟着变化a[j].p=a[i].p;a[i].p=temp;}}//对输入的指数进行排序，相应的系数跟着变化couta[0].px^a[0].q;//先输出第一项if(a[i].p0)elseif(a[i].p0)couta[i].px^a[i].q;cout'+'a[i].px^a[i].q;//完成运算符和其他项的输//出,然后类似于上面，对第二个多项式进行相应的操作。for(i=0;im;i++){a[n+i].q=b[i].q;a[n+i].p=b[i].p;}//将两个多项式的指数，系数存储到一个数组for(i=0;im+n;i++)for(j=i+1;jn+m;j++){if(a[j].qa[i].q){temp=a[j].q;a[j].q=a[i].q;a[i].q=temp;temp=a[j].p;a[j].p=a[i].p;a[i].p=temp;}}//按指数由大到小进行排列if(a[0].q!=a[1].q){couta[0].px^a[0].q;j=1;}else{couta[0].p+a[1].px^a[0].q;j=2;}//进行合并同类项的操作，如果该项与下一项的指数相等，//则系数相加。否则，只输出该项for(i=j;im+n-1;i++){if(a[i].q!=a[i+1].q){if(a[i].p0)cout+a[i].px^a[i].q;if(a[i].p0)//负号相当于减号couta[i].px^a[i].q;}else{if((a[i].p+a[i+1].p)0)cout+a[i].p+a[i+1].px^a[i].q;elseif((a[i].p+a[i+1].p)0)couta[i].p+a[i+1].px^a[i].q;i++;}}if(a[m+n-1].q!=a[m+n-2].q){if(a[i].p0)cout+a[i].px^a[i].q;elseif(a[i].p0)couta[i].px^a[i].q;}//对第一项与最后一项做特殊处理，以免输出多余的运算//符,同时，当系数为0，则不输出该项循环链表的方法：structcode{floatcoef;//存系数intexpn;//存指数code*next;}List;voidCreate(List*L,intn){for(inti=n;i0;i--){p=newList[sizeof(code)];//每次都要new一个cinp-coef;cinp-expn;p-next=L-next;L-next=p;}}voidpaixu(LinkList*head)//将链表中的元素按降幂排列{类似于数组的冒泡排序法。}voidprint(List*L){打印多项式的函数，特别注意负数的输出，当系数为零时的输出}ListList(List*La,List*Lb){将两个链表合成一个}再用输出函数输出即可算法的时空分析：算法复杂度为O(（m+n)^2）;五．调试分析：调试的主要内容是观察链表的每一元素是否按降幂排列。判断什么时候跳出while循环。六．测试结果：七．实验心得：1．对于多项式的运算的，运算符的输出很重要，一开始多输出一个‘+’，并且当为负数时会输出+--。还有当系数为0时的输出都没有专门考虑。和周围的同学交流一下算法，相互探讨了出现的问题，和解决的方法。讨论中改掉很多不足。使代码更加完善。2．这次用链表的来做这道题目让我收获很大。对链表的构建更加的熟练。对链表向前推进把握的更加准确。在调试代码，检验的时候，遇到很大的阻碍，但解决问题后，自己明白了很多。3．通过本次试验，我发现自己分析问题不是很全面，忽略掉一些细节。以后分析问题时要仔细考虑，认真分析，避免在细节上犯错误。附：#includeiostreamusingnamespacestd;structcode{intp,q;}a[1000],b[1000];intmain(){inti,j,n,m,temp;while(cinn){for(i=0;in;i++)cina[i].pa[i].q;for(i=0;in;i++){for(j=i+1;jn;j++){if(a[j].qa[i].q){temp=a[j].q;a[j].q=a[i].q;a[i].q=temp;temp=a[j].p;a[j].p=a[i].p;a[i].p=temp;}}}couta[0].px^a[0].q;for(i=1;in;i++){if(a[i].p0)cout'+'a[i].px^a[i].q;elseif(a[i].p0)couta[i].px^a[i].q;}coutendl;cinm;for(i=0;im;i++)cinb[i].pb[i].q;for(i=0;im;i++){for(j=i+1;jm;j++){if(b[j].qb[i].q){temp=b[j].q;b[j].q=b[i].q;b[i].q=temp;temp=b[j].p;b[j].p=b[i].p;b[i].p=temp;}}}coutb[0].px^b[0].q;for(i=1;im;i++){if(b[i].p0)cout+b[i].px^b[i].q;elseif(b[i].p0)coutb[i].px^b[i].q;}coutendl;for(i=0;im;i++){a[n+i].q=b[i].q;a[n+i].p=b[i].p;}for(i=0;im+n;i++)for(j=i+1;jn+m;j++){if(a[j].qa[i].q){temp=a[j].q;a[j].q=a[i].q;a[i].q=temp;temp=a[j].p;a[j].p=a[i].p;a[i].p=temp;}}if(a[0].q!=a[1].q){couta[0].px^a[0].q;j=1;}else{couta[0].p+a[1].px^a[0].q;j=2;}for(i=j;im+n-1;i++){if(a[i].q!=a[i+1].q){if(a[i].p0)cout+a[i].px^a[i].q;if(a[i].p0)couta[i].px^a[i].q;}else{if((a[i].p+a[i+1].p)0)cout+a[i].p+a[i+1].px^a[i].q;elseif((a[i].p+a[i+1].p)0)couta[i].p+a[i+1].px^a[i].q;i++;}}if(a[m+n-1].q!=a[m+n-2].q){if(a[i].p0)cout+a[i].px^a[i].q;elseif(a[i].p0)couta[i].px^a[i].q;}}return0;}