数据结构多项式相加程序实习报告

实习一实验报告1、需求及规格说明本次实习要求完成一个程序，实现两个多项式的加法。为了练习单链表的操作，要求对两个多项式实现合并同类项。2、设计设计思想：每个节点有两个数据：系数和次数，同时含有指向下一个节点的指针。在实现加法的时候要先判断两个节点的次数是否相同，如果相同就让系数相加。如果相加后系数为0，则在输出结果时要避免输出这一项。设计表示：主函数main，在其中首先定义两个多项式p1和p2，然后调用input函数来输入多项式，接着调用print函数来输出这两个多项式。然后调用add函数来对p1和p2实现加法，将结果存入链表p。最后调用print函数输出p（结果）。3、用户手册输入时每一项按照“系数”+“空格符”+“次数”的格式输入。当整个多项式都输入完毕时，请输入“0”作为结束。4、调试报告两个多项式加法的函数add是程序的核心函数。相加时要对同次数的项进行合并，不相同次数的项直接跳过。实现时定义了一个临时的链表，将已经完成的部分存入该链表。最后，当两个链表的加法做完就返回该临时链表。在相同次数项相加后可能会出现系数为0的情况。为了解决这个问题，我在输出中加了一项判断：在判断指针不是空指针的同时判断节点系数是不是0，如果是0就不再输出。时间复杂度O(n)。5、附录源程序代码//polynomial.hstructpolynomial{ doublecoef;//记录成员(系数和次数，coef：系数，exp：次数） doubleexp; polynomial*next;//记录下一个结构体对象地址 //构造函数初始化私有数据成员 polynomial(doublec=0,doublee=0,polynomial*N=0) { coef=c; exp=e; next=N; }//构造函数结束定义 //定义析构函数 ~polynomial(){} //析构函数结束定义};//polynomial结构体定义结束//polynomial.cpp#include<iostream>#include"polynomial.h"usingnamespacestd;polynomial*input()//输入函数。{ doublecoef=0; doubleexp=0; polynomial*p; inti=1; while(true) { cout<<"第"<<i<<"项"<<endl; cin>>coef; if(coef==0)break; cin>>exp; if(i==1) { p=newpolynomial(coef,exp,0); } else { polynomial*q=p; polynomial*rear=0;while(q!=0&&q->exp<=exp) { rear=q; q=q->next; } if(rear==0) { p=newpolynomial(coef,exp,q); } else { if(rear->exp<exp) rear->next=newpolynomial(coef,exp,q); else rear->coef+=coef; } } i++; } returnp;}polynomial*add(polynomial*exp1,polynomial*exp2)//实现两个多项式的加法的函数。{ if(exp1==0) returnexp2; elseif(exp2==0) returnexp1; polynomial*p1=exp1; polynomial*p2=exp2; polynomial*Result=newpolynomial(); polynomial*p3=Result; while(true) { if(p1==0&&p2!=0) { p3->coef=p2->coef; p3->exp=p2->exp; p2=p2->next; } elseif(p2==0&&p1!=0) { p3->coef=p1->coef; p3->exp=p1->exp; p1=p1->next; } elseif(p1==0&&p2==0) { p3=0; break; } elseif(p1->exp==p2->exp) { p3->coef=p1->coef+p2->coef; p3->exp=p1->exp; p1=p1->next; p2=p2->next; } elseif(p1->exp<p2->exp) { p3->coef=p1->coef; p3->exp=p1->exp; p1=p1->next; } elseif(p1->exp>p2->exp) { p3->coef=p2->coef; p3->exp=p2->exp; p2=p2->next; } if(p1!=0||p2!=0) { p3->next=newpolynomial(); p3=p3->next; } } returnResult;}voidprint(polynomial*n)//输出一个多项式。{ polynomial*p=n; polynomial*q=newpolynomial(); while(true) { q->coef=p->coef; q->exp=p->exp; if(p->next!=0) { q=newpolynomial(0,0,q); p=p->next; } elsebreak; } while(q!=0&&q->coef!=0)//节点的系数不为0时才将该节点输出。 { cout<<""<<q->coef<<"x^"<<q->exp; q=q->next; if(q!=0&&q->coef>0)//系数为正数的时候要先输出一个“+”号。 cout<<"+"; } cout<<endl;}//main.cpp#include<iostream>#include"polynomial.h"usingnamespacestd;polynomial*add(polynomial*,polynomial*);voidprint(polynomial*);polynomial*input();voidmain(){ cout<<"该程序是为了实现两个多项式的加法"<<endl <<"请输入第一个式子中的系数以及次数（输入格式：12），输入0（只需要输入0，不要输入0X）结束。"<<endl; polynomial*p1=input(); cout<<"请输入第二个式子中的系数以及次数（输入格式：12），输入0（只需要输入0，不要输入0X）结束。"<<endl; polynomial*p2=input(); cout<<endl<<"式子1