数据结构上机实验-多项式加法.doc

多项式加法班级: 姓名: 完成日期:2014-04-061. 需求分析本程序的任务是实现两个多项式的加法其中多项式的系数为浮点型，指数为整数，输出的结果也为系数和指数。（1） 输入的形式和输入值的范围： 输入多项式的系数a和未知数X的指数b，当a和b都为零时，输入结束。 输入值的范围：a为实数，b为整数。（2） 输出形式： 输出多项式的系数和多项式未知数X的指数即(a,b)形式。（3） 程序所能达到的功能： 实现两个多项式的加法，并输出最后的结果。（4） 测试数据： 输入：7 0 3 1 9 8 5 17 0 0 8 1 22 7 -9 8 0 0 输出：(7,0)(11,1)(22,7)(5,17) 2. 概要设计（1） 抽象数据类型的定义如下： ADT LinkList 数据对象：D=Ei|i=1,2,3.n;n0;Ei属于AtomSet; AtomSet是某个数据对象 基本操作： InitList_L(&L); 操作结果：创建头节点，并初始化该节点。 ADT LinkList；（2） 主程序： Void main( ) 创建链表并用循环结构将数据输入到链表中； AddPolyn(L1,L2); 输出结果；（3） 程序模块的调用关系 主程序多项式加法模块 链表模块 3.详细设计 （1）节点类型 typedef struct Lnode float coef; /存储项系数 int expn;/存储项指数 struct Lnode *next; Lnode,*LinkList; （2）多项式的基本操作为： InitList_L(LinkList &L); /初始化头节点； void AddPolyn(polynomial pa, polynomial pb); /实现多项式加法，并返回多项式加法的最终结果 /同时释放节点 Void main() /创建链表L1和L2，并使p=L1,q=L2； InitList_L(LinkList &L); for(;) cina; cinb; if(a=0&b=0)/跳出循环，结束输入 break; m=new Lnode;/创建新节点 m-coef=a; m-expn=b; q-next=m; q=m; q-next=null; /输入第一个多项式的系数和X的指数 for(;) cina; cinb; if(a=0&b=0)/跳出循环，结束输入 break; n=new Lnode;/创建新节点 n-coef=a; n-expn=b; p-next=n; p=n; p-next=null; /输入第二个多项式的系数和X的指数 AddPolyn(L1,L2); while(L1-next)!=null) coutnext-coef next-expnnext; /循环输出结果 main （3）函数的调用关系图 AddPolyn InitList_L4. 调试分析（1） 调试过程中遇到的问题及解决方法： 在向创建的链表里输入数据时，因为忘记将创建的新节点的next指针置空（即q-next=null），导致在输出节点的数据时出现错误。解决方法将for循环输入的最后一条语句改为q-next=null，正确的解决了这个问题。（2） 算法的时空分析整个程序运行期间实行动态创建节点，一边输入数据，一边创建节点。当将全部数据输入到单链表中后再调用多项式加法这个函数，并一边实现多项式的相加，一边释放节点，有效防止了在程序反复运行过程中可能出现系统空间不够分配的现象。（3） 经验和体会 通过编写多项加法这个程序，我将自己所学到的创建链表，初始化链表和多项式加法算法都应用了一次，这使我们不仅仅只是理论化的学习书本上的知识，而是将学习到的理论知识应用到实际的操作中来增强我们的实际操作能力，这使我增加了实际操作经验，也使我通过实际操作来认识到自己在程序编写上的不足从而增强了我的实际编写程序的能力。5. 用户使用说明（1） 本程序的运行环境为Microsoft Visual C+ 6.0。（2） 进入程序后的界面为 （3） 输入数据，当一组数据中的系数与指数都为零时，输入结束，按回车键，同样的方法再输入第二组数据。最后按回车键就会输出结果。6. 测试结果 （1）输入数据：7 0 3 1 9 8 5 17 0 0 8 1 22 7 -9 8 0 0 输出操作结果：(7,0) (11,1) (22,7) (5 ,17) （2）输入数据：3 1 4 3 8 5 9 8 0 0 2 1 5 2 7 5 0 0 输出操作结果：(5,1) (5,2) (4,3) (15,5) (9,8) （3）输入数据：2 0 3 2 5 4 6 7 0 0 3 0 4 3 8 4 5 7 0 0 输出操作结果：(5,0) (3,2) (4,3) (13,4) (11,7) （4）输入数据：4 2 3 5 6 7 9 8 0 0 3 2 5 5 7 7 2 10 0 0 输出操作结果：(7,2) (8,5) (13,7) (9,8) (2,10)7.附录 #includeusing namespace std;typedef int Status;#define OVERFLOW -1#define null 0typedef struct Lnodefloat coef; /存储项系数 int expn;/存储项指数struct Lnode *next;Lnode,*LinkList;typedef LinkList polynomial;Status InitList_L(LinkList &L) /初始化头节点L=(LinkList)malloc(sizeof(Lnode);if(!L)return(-1);L-next=null; return 1; void AddPolyn(polynomial pa, polynomial pb) /实现两个多项式相加的算法float x;polynomial qa;polynomial qb;polynomial s;polynomial u; qa=pa-next; qb=pb-next; s=pa; while(qa&qb) if(qa-expnexpn) s=qa; qa=qa-next; else if(qa-expn=qb-expn) x=qa-coef+qb-coef; if(x!=0) qa-coef=x; s=qa; qa=qa-next; u=qb; qb=qb-next; free(u); else s-next=qa-next; free(qa); qa=s-next; u=qb; qb=qb-next; free(u); else if(qa-expnqb-expn) u=qb-next; s-next=qb; s=qb; qb-next=qa; qb=u; if(qb) qa-next=qb; free(pb);void main()float a;int b;polynomial L1;polynomial L2;LinkList q;LinkList p;LinkList m;LinkList n;InitList_L(L1);q=L1;InitList_L(L2);p=L2;cout请输入数据：a;cinb;if(a=0&b=0)break;m=new Lnode;m-coef=a;m-expn=b;q-next=m;q=m;q-next=null;/循环输入第一个多项式的系数与指数for(;)cina;cinb;if(a=0&b