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

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