数据结构实验报告一元多项式的加法运算.docx
数据结构实验报告一元多项式的加法运算问题描述： 设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时，该项不输出 当系数为负数时，不要再在前面输出+。 程序的流程 程序由三个模块组成： 输入模块：完成两个多项式的输入。 处理模块：将多项式按其指数大小进行排列。 输出模块：输出合并后的多项式。 三、详细设计 算法的具体步骤： 数组方法 ： struct code int p,q; a1000,b1000;/结构体数组，可以用二维数组代/替 for(i=0;i<n;i+) for(j=i+1;j<n;j+) if(aj.q>ai.q) temp=aj.q;/指数排序 aj.q=ai.q; ai.q=temp; temp=aj.p;/系数跟着变化 aj.p=ai.p; ai.p=temp; /对输入的指数进行排序，相应的系数跟着变化 cout<<a0.p<<"x"<<a0.q; /先输出第一项 if(ai.p>0) else if(ai.p<0) cout<<ai.p<<"x"<<ai.q; cout<<'+'<<ai.p<<"x"<<ai.q;/完成运算符和其他项的输/出,然后类似于上面，对第二个多项式进行相应的操作。 for(i=0;i<m;i+) an+i.q=bi.q; an+i.p=bi.p; /将两个多项式的指数，系数存储到一个数组 for(i=0;i<m+n;i+) for(j=i+1;j<n+m;j+) if(aj.q>ai.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) cout<<a0.p<<"x"<<a0.q; j=1; else cout<<a0.p+a1.p<<"x"<<a0.q; j=2; /进行合并同类项的操作，如果该项与下一项的指数相等，/则系数相加。否则，只输出该项 for(i=j;i<m+n-1;i+) if(ai.q!=ai+1.q) if(ai.p>0) cout<<"+"<<ai.p<<"x"<<ai.q; if(ai.p<0) /负号相当于减号 cout<<ai.p<<"x"<<ai.q; else if(ai.p+ai+1.p)>0) cout<<"+"<<ai.p+ai+1.p<<"x"<<ai.q; else if(ai.p+ai+1.p)<0) cout<<ai.p+ai+1.p<<"x"<<ai.q; i+; if(am+n-1.q!=am+n-2.q) if(ai.p>0) cout<<"+"<<ai.p<<"x"<<ai.q; else if(ai.p<0) cout<<ai.p<<"x"<<ai.q; /对第一项与最后一项做特殊处理，以免输出多余的运算符,同时，当系数为0，则不输出该项 四、调试分析 略。 五、测试结果 六、用户使用说明 本程序的运行环境为windows 操作系统，执行文件为 duoxianshi.exe 运行程序时按顺序输入数字即可得到多项式。 七、实验心得 对于多项式的运算的，运算符的输出很重要，一开始多输出一个+，并且当为负数时会输出+-。还有当系数为0时的输出都没有专门考虑。 通过与同学讨论，这次用链表的来做这道题目让我收获很大。对链表的构建更加的熟练。对链表向前推进把握的更加准确。 通过本次试验，我发现自己分析问题不是很全面，忽略掉一些细节。以后分析问题时要仔细考虑，认真分析，避免在细节上犯错误。 在此次实验的同时也将上课所学内容进行了复习。 附录 #include<iostream> using namespace std; struct code int p,q; a1000,b1000; 存储指数 /定义一个结构体数组,p存储系数,qint main int i,j,n,m,temp; while(cin>>n) for(i=0;i<n;i+) cin>>ai.p>>ai.q; for(i=0;i<n;i+) for(j=i+1;j<n;j+) if(aj.q>ai.q) temp=aj.q; /指数排序 aj.q=ai.q; ai.q=temp; temp=aj.p; /系数跟着变化 aj.p=ai.p; ai.p=temp; /对输入的指数进行排序，相应的系数跟着变化 cout<<a0.p<<"x"<<a0.q; for(i=1;i<n;i+) if(ai.p>0) cout<<'+'<<ai.p<<"x"<<ai.q; else if(ai.p<0) cout<<ai.p<<"x"<<ai.q; cout<<endl; /输出第一个多项式 cin>>m; for(i=0;i<m;i+) cin>>bi.p>>bi.q; for(i=0;i<m;i+) for(j=i+1;j<m;j+) if(bj.q>bi.q) temp=bj.q; bj.q=bi.q; bi.q=temp; temp=bj.p; bj.p=bi.p; bi.p=temp; cout<<b0.p<<"x"<<b0.q; for(i=1;i<m;i+) if(bi.p>0) cout<<"+"<<bi.p<<"x"<<bi.q; else if(bi.p<0) cout<<bi.p<<"x"<<bi.q; cout<<endl; /输出第二个多项式 for(i=0;i<m;i+) an+i.q=bi.q; an+i.p=bi.p; /将两个多项式的指数，系数存储到一个数组 for(i=0;i<m+n;i+) for(j=i+1;j<n+m;j+) if(aj.q>ai.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) cout<<a0.p<<"x"<<a0.q; j=1; else cout<<a0.p+a1.p<<"x"<<a0.q; j=2; /进行合并同类项的操作，如果该项与下一项的指数相等，则系数相加。否则，只输出该项 for(i=j;i<m+n-1;i+) if(ai.q!=ai+1.q) if(ai.p>0) cout<<"+"<<ai.p<<"x"<<ai.q; if(ai.p<0) cout<<ai.p<<"x"<<ai.q; else if(ai.p+ai+1.p)>0) cout<<"+"<<ai.p+ai+1.p<<"x"<<ai.q; else if(ai.p+ai+1.p)<0) cout<<ai.p+ai+1.p<<"x"<<ai.q; i+; /负数情况 if(am+n-1.q!=am+n-2.q) if(ai.p>0) cout<<"+"<<ai.p<<"x"<<ai.q; else if(ai.p<0) cout<<ai.p<<"x"<<ai.q; /对第一项与最后一项做特殊处理，以免输出多余的运算符,同时，当系数为0，则不输出该项 return 0;
