习题四实验报告

实验报告题目：一元多项式加法班级：08113701姓名：韩校欢学号：0811370115完成日期：2010年11月20日一、需求分析一元多项式加法的任务主要是对用户输入的合法的两个一元多项式进行加法运算并输出计算后的结果。(1)输入的形式和输入值的范围：用户只需输入多项式每一项的指数e和系数m(必须成对输入，常数项的指数为0)，其中e必须是正整数（0,1,2……），m必须是实数。规定多项式最多只能有20项。(2)输出的形式：（m0，e0）(m1，e1)(m2，e2)…………(3)程序所能达到的功能：计算用户输入的两个多项式的加法结果(4)测试数据：输入被加的多项式为(1.24)(32)来检验当用户不按顺序输入时程序的处理能力输入字母时，输入H来检验程序处理错误的能力输入被加的多项式(40)(1.25)(266)(57)(208)(1410)输入加的多项式(23)(155)(3.28)(209)(1210)(5.611)(8012)(5613)(414)(7.315)(116)(117)(118)(119)(120)(121)(122)(123)(124)(125)二、概要设计线性表的抽象数据类型定义：ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,……,n}基本操作：Init(&L)操作结果：构造一个空的线性表L。Destroy(&L)初始条件：线性表L已经存在。操作结果：销毁线性表L。}ADTList本程序的主函数顺序执行各个函数，只有一个主函数模块，所以没有模块的调用。三、详细设计全部程序：#include<iostream.h>#include<stdlib.h>#defineOK1#defineERROR0typedefintStatus;typedefstructxiang{//项的表示floatcoef;//系数intexpn;//指数structxiang*next;}xiang,*term;StatusInit(term&L){//创建一个空链表 L=(term)malloc(sizeof(xiang)); if(!L)exit(ERROR); L->next=NULL; returnOK;}//InitStatuscreat(term&p){//输入多项式的系数和指数，建立一元多项式的有序链表ptermq; q=(term)malloc(sizeof(xiang)); if(!q)exit(ERROR); p->next=q; charh;//用于判断用户是否输入结束 intd;//用于判断用户是否顺序输入 for(inti=1;i<=20;i++){cout<<"请输入第"<<i<<"项的系数(实数)"<<endl; cin>>q->coef; cout<<"请输入第"<<i<<"项的指数(正整数)"<<endl;cin>>q->expn;if(i!=1){ if(d>q->expn) {cout<<"您没有顺序输入，程序结束"<<endl; exit(ERROR);} }//判断用户是否顺序输入 d=q->expn; if(i==20){ cout<<"您已输入到规定的最大项数"<<endl; q->next=NULL; returnOK;}//限定用户最多只能输入20项cout<<"还需要继续输入吗？（Y/N请输入小写）"<<endl; cin>>h; if(h=='n'){q->next=NULL;returnOK;} if(h!='y'){cout<<"您输入了错误的字符，程序结束"<<endl;exit(ERROR);}termr; r=(term)malloc(sizeof(xiang)); if(!r)exit(ERROR);q->next=r; q=r; }//for q->next=NULL; returnOK;}//creatintqiuxiao(inta,intb){ //判断a,b的大小 if(a!=b){ if(a<b)return1; elsereturn2; }//if elsereturn0;}Statusadd(term&pa,termpb){ //多项式加法：pa=pa+pb,利用两个多项式的结点构成“和多项式”//“和多项式”存储在线性链表pa中 termqa,qb,s;qa=pa->next; qb=pb->next; s=pa; intc;while(qa&&qb){ c=qiuxiao(qa->expn,qb->expn); switch(c){ case1: s=qa; qa=qa->next; break; case2: termo;o=qb->next; s->next=qb; s=qb; qb->next=qa; qb=o; break; case0: floatx;x=qa->coef+qb->coef; if(x!=0.0){ termu;qa->coef=x; s=qa; qa=qa->next; u=qb;qb=qb->next; free(u); }//ifelse{s->next=qa->next;free(qa);qa=s->next; termu;u=qb;qb=qb->next;free(u); }//elsebreak;}//switch }//while if(qb)s->next=qb;//链接Pb中剩余结点 free(pb);//释放Pb的头结点 returnOK;}//addStatusshow(termp){ cout<<"计算结果如下:"<<endl; termk; k=p->next; for(inti=1;i<=40;i++){ cout<<"("<<k->coef<<","<<k->expn<<")";if(!(k->next))returnOK; k=k->next; }//for returnOK;}//showvoidmain(void){ termm1,m2; Init(m1); Init(m2); cout<<"请按指数递增的顺序输入多项式的每一项(最多只能输入20项)"<<endl; cout<<"请输入被加的多项式"<<endl; creat(m1); cout<<"请输入加的多项式"<<endl; creat(m2); add(m1,m2); show(m1);}函数的调用关系图反映如下：

四、调试分析该程序在调试的时候发现在建立链表m1和m2时在处理数据时会出现多种问题，特别是链表的尾节点的next一定要赋值NULL，所以要在每个结束语句前加上q->next=NULL。还有就是多种结束语句的位置一定要放的恰到好处。函数creat的空间复杂度为O(n),函数add的最大空间复杂度为O(n1+n2)。经过程序的调试收获很多，单单写一个程序算法(简单的)不是很难，但是到调试的时候就会有很多错误，经过调试可以培养我们小心谨慎的办事态度。五、用户使用说明在执行该程序时，首先要根据提示顺序(指数递增的顺序)输入每一项的系数(实数)和指数(整数)，在遇到系统提示是否继续输入的时候要输入字母小写y(继续)或n(输入结束)，当用户输完第20项时，系统不再提示用户是否继续输入而自动运行下边程序，因为该程序限制了多项式的最大项数不能超过20。当用户输完以上数据后，系统便会自动输出计算结果。六、测试结果输入被加的多项式为(1.24)(32)时系统提示出错自动结束程序当用户遇到提示是否继续输入字符时输入字母H系统提示输入错误的字符，程序自动结束。当用户输入被加的多项式(4，0)(1.2，5)(26，6)(5，7)(20，8)(14，10)输入加的多项式(2，3)(15，5)(3.2，8)(20，9)(12，10)(5.6，11)(80，12)(56，13)(4，14)(7.3，15)(1，16)(1，17)(1，18)(1