一元多项式求和.doc

计算机科学与工程学院计算机科学与工程学院数据结构与算法实验报告专业班级实验地点机423学生学号指导教师学生姓名实验时间实验项目链表的应用实验类别操作性（ ）验证性（ ）设计性（ ）综合性（ ）其它（ ）实验目的及要求（1）熟练掌握链表结构及有关算法的设计；（2）掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明： 评阅教师： 日 期： 年 月 日一 实验内容一元多项式求和:把任意给定的两个一元多项式P(x),Q(x)输入计算机，计算它们的和并输出计算结果。二、实验说明一元多项式可以用单链表表示，结点结构图示如下： 一元多项式链表的结点结构coef exp next一元多项式算法伪代码如下：1. 工作指针p、q初始化；2. while（p存在且q存在）执行下列三种情形之一 2.1 如果p-expexp，则指针p后移; 2.2 如果p-expq-exp，则 2.2.1 将结点q插入到结点p之前； 2.2.2 指针q指向原指结点的下一个结点； 2.3 如果p-exp=q-exp，则 2.3.1 p-coef =p-coef+q-coef； 2.3.2 如果p-coef =0，则执行下列操作，否则，指针p后移; 2.3.2.1 删除结点p； 2.3.2.2 使指针p指向它原指结点的下一个结点； 2.3.3 删除结点q； 2.3.4 使指针q指向它原指结点的下一个结点； 3. 如果q不为空，将结点q链接在第一个单链表的后面；三、 设计分析（实验流程）实现要定义的一元多项式应采用链式存储结构。根据一元多项式相加的运算法则，对于两个多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成新多项式的一项；对于两个多项式中所有指数不同的项，分别复制到新多项式中。新多项式不必另外生成，而是在原来的两个多项式中摘取结点即可。采用顺序存储结构存储多项式系数A，使多项式的某些运算变得更简洁。但在实际使用时，多项式的阶数可能很高，不同的多项式阶数可能相差很大，这使顺序存储结构的最大长度难以确定。而且，最高次幂与最低次幂项之间缺项很多时，采用顺序存储结构显然十分浪费存储空间，因此，一般情况下多采用链式存储结构来存储高阶多项式。在用线性链表来存储一个多项式时，多项式中的每个非零项系数对应一个结点，结点由数据元素项和指针组成。数据元素项中包含系数和指数值， 设计中先定义定义数据元素中的数据，其中有指数、系数级指针next等。并要先构造一元多项式。在定义输出、删除、合并等模块。假设指针qa和qb分别指向多项式A和B中当前进行操作的某个结点，比较这个结点的指数项，可能有三种情况： 指针qa-expexp,则摘取qa指针所指结点插入到和多项式中； 指针qa-expexp,则摘取qb指针所指结点插入到和多项式中； 指针qa-exp=qb-exp,则将系数相加，若和数不为零，则修改qa-coef的值，同时释放qb所指结点，反之，从多项式A的链表中删除相应的结点，并释放指针Pa和Pb所指结点；还有就是在输入是采取的降序输入，也好使两个多项式进行合并。并输出。在主函数中将前面也的这些功能都运用起来就可以了。四、源程序代码#include#define NULL 0using namespace std;typedef struct Polynomial float coef; /系数 int exp; /指数struct Polynomial *next;Polynomial;Polynomial *CreatPolyn() /输入m项的系数和指数，建立一元多项式float mod; int ind; Polynomial *H,*p,*s; H=new Polynomial; s=H; cout请输入多项式的系数和指数：(按0结束输入)modind;while(mod) p=(Polynomial *)new Polynomial;p-coef=mod;p-exp=ind;s-next=p;s=p;cinmodind;s-next=NULL;return H;void Print(Polynomial *pa) /打印输出一元多项式pwhile(pa-next!=NULL) pa=pa-next; coutcoef*xexp; if(pa-next!=NULL&pa-next-coef0)coutnext;while(p)q=p;p=p-next;delete q;pa-next=NULL;void AddPolyn(Polynomial *pa,Polynomial *pb) /用于链表的合并使用完成多项式的相加运算float sum;Polynomial *p,*q,*pre,*temp;p=pa-next;q=pb-next;pre=pa; while(p!=NULL&q!=NULL)if(p-expq-exp) pre-next=p; pre=pre-next; p=p-next; else if(p-exp=q-exp) sum=p-coef+q-coef; if(sum!=0) p-coef=sum; pre-next=p;pre=pre-next;p=p-next; temp=q;q=q-next;delete temp; else temp=p-next;delete p; p=temp; temp=q-next;delete q; q=temp; else pre-next=q; pre=pre-next; q=q-next; if(p!=NULL) /将多项式A中剩余的结点加入到和多项式中 pre-next=p; else pre-next=q; int main()int c;int t=1;while(t)cout*菜单*endlendl;cout1.创建并显示一元多项式A和B，计算一元多项式A加B并显示和endlendl;cout2.退出程序.c;switch(c)case 1:Polynomial *p1,*p2;p1=CreatPolyn();cout一元多项式A是: ;Print(p1);coutendl;p2=CreatPolyn();cout一元多项式B是: ;Print(p2);coutendl;AddPolyn(p1,p2);cout一元多项式A加B的和是: ;Print(p1);coutendl;Delete(p1);break;case 2:t=0;break;system(pause);return 0; 五、实验结果六、实验总结这次实验做了好久。刚开始都不知道怎么去下手，首先是把题目的意思理解错了，本来是一元多项式以为是多元多项式，也不太知道怎么去表达那个次数。后来才知道是自己理解错了。后来想想就用之前在课程设计中用的思路去做。在