数据结构-多项式-实验报告

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业数据结构实验报告实验名称： 实验一多项式的实现学生姓名： 班 级： 班内序号： 学 号： 日 期： 2011年10月29日1实验要求实验目的：1.熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容： 利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 要求：能够实现一元多项式的输入和输

2、出能够进行一元多项式相加能够进行一元多项式相减能够计算一元多项式在x处的值能够计算一元多项式的导数（选作）能够进行一元多项式相乘（选作）编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表

3、里。本程序完成的主要功能：输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。 2.1 存储结构本程序采用的存储结构是单链表结构

4、，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下：coef1 expn1 nextcoef1 expn1 nextcoef1 expn1 next nextcoef1 expn1 nextcoef1 expn1 nextcoef1 expn1 next next 2.2 关键算法分析输入多项式自然语言描述：设置多项式的项数n；按照多项式的项数申请动态数组coef和expn存储多项式的系数和指数；按照指数递增的次序输入各项的系数以及指数，分别存入coef和expn；再将输入的系数以及指数赋给每一个结点的coef和expn域； 利用头插法将每个结点加入链表。伪代码：输入项数n；

5、float* coef1=new floatn1;int* expn1=new intn1;运用for循环，循环n次3.1 term* s=new term; 3.2 s-coef=coefi;3.3 s-expn=expni; 3.4 r-next=s; 3.5 r=s; 4. 运用头插法将结点插入链表。时间复杂度：空间复杂度：输出多项式自然语言描述：获取头结点；循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式 2.2.1 系数为1且指数不为1和0，输出xexpn+； 2.2.2 系数不为0且指数为0，输出（coef）+； 2.2.3 系数不为

6、0且指数为1，输出（coef）x+； 2.2.4 系数不为0和1，指数不为0和1，输出(coef)x(expn)+； 3.将指针指向移到最后一个节点。重复2.2中判断，但不输出+号。伪代码描述：term* m=front;for(int i=0;inext;if(m-coef=1&(m-expn!=1&m-expn!=0)coutxexpncoef=1&m-expn=0)coutcoefcoef!=1&m-expn=0)coutcoefcoef!=0&m-expn=1)coutcoefxcoef=1&m-expn=1)coutxcoef=0)cout+;elsecoutcoefxexpnnex

7、t;if(m-coef=1&(m-expn!=1&m-expn!=0)coutxexpncoef=1&m-expn=0)coutcoef;else if(m-coef!=1&m-expn=0)coutcoef;else if(m-coef!=1&m-expn=1)coutcoefxcoef=1&m-expn=1)coutcoef=0)cout;elsecoutcoefxexpnexpnq-expn复制q到结果多项式（减法系数为q-coef的相反数）如果p-expnexpn复制p到结果多项式3.3.3.4 判断后将项数+，插入新节点d；如果q为空，p仍存在，逐项将p复制到结果多项式。每进行一次，

8、项数+，p后移。如果p为空，q仍存在，逐项将q复制到结果多项式（减法将系数变为原来的相反数）。每进行一次，项数+，q后移。返回结果多项式的项数 伪代码描述：工作指针p、q初始化：term* p=front-next;term* q=b.front-next; 2. int nAdd=0;/加法 int nMinus=0;/减法 3. while(p|q) 3.1 term* d=new term;d-next=NULL; 3.3.1 if(p&q) 3.3.3.1 if(p-expn=q-expn) d-coef=p-coef+q-coef;d-expn=p-expn;p=p-next;q=q

9、-next;/加法 d-coef=p-coef-q-coef;d-expn=p-expn;p=p-next;q=q-next;/减法 3.3.3.2 p-expnq-expn d-coef=q-coef;d-expn=q-expn;q=q-next;/加法d-coef=-q-coef;d-expn=q-expn;q=q-next;/减法 3.3.3.3p-expnexpnd-coef=p-coef;d-expn=p-expn;p=p-next;/加法d-coef=p-coef;d-expn=p-expn;p=p-next;/减法 3.3.3.4 nAdd+;add.Insert(d);/加法

10、nMinus+;min.Insert(d);/减法 3.3.2 while(p)term* d=new term;d-coef=p-coef; d-expn=p-expn;d-next=NULL;nAdd+; add.Insert(d);p=p-next;/加法term* d=new term;d-coef=(p-coef); d-expn=p-expn;d-next=NULL; nMinus+;min.Insert(d);p=p-next;/减法 3.3.3 while(q) term* d=new term;d-coef=q-coef; d-expn=q-expn;d-next=NULL;

11、 nAdd+;add.Insert(d);q=q-next;/加法term* d=new term;d-coef=0-(q-coef); d-expn=q-expn;d-next=NULL; nMinus+;min.Insert(d);q=q-next;/减法3.2 return nAdd; return nMinus;时间复杂度：O(n)空间复杂度：O(2)求值自然语言描述：将工作指针指向多项式的第一项；将结果result置为0；指针不为空，即进行循环：3.1 result+=s-coef*(pow(x,s-expn); 3.2 s=s-next; 4返回result；伪代码描述：term*

12、 s=front-next;float result=0;while(s)3.1 result+=s-coef*(pow(x,s-expn); 3.2 s=s-next; 4. return result;时间复杂度：O(n)空间复杂度：S(1)求导数自然语言描述：将指针指到多项式的第一项的结点：term* p=a.front-next;循环n次每项求导的系数为：p-coef*p-expn;指数为：p-expn-1;将新结点插入新链表；指针p后移。 伪代码描述： 1. term* p=a.front-next; 2. for(int i=0;iexpn) 2.2.1 s-coef=(p-coe

13、f)*(p-expn); 2.2.2 s-expn=p-expn-1; 2.2.3p=p-next; 2.2.4 de.Insert(s); 2.3 else 2.3.1 s-coef=0;2.3.2 s-expn=0;2.3.3 p=p-next;2.3.4 de.Insert(s);时间复杂度：O(n)空间复杂度：S(1)3. 程序运行结果测试主函数流程：1开始1开始进行A-B的运算进行A-B的运算设置多项式A的项数按照A的项数动态申请coef1和expn1按照A的项数动态申请coef1和expn1输出相减输出相减的结果minus进行对A求导数的运算进行对A求导数的运算输出A设置多项式B的

14、项数设置多项式B的项数输出求导输出求导的结果de按照B的项数动态申请coef2和expn2按照B的项数动态申请coef2和expn2输入x的取值输入x的取值计算A在x处的取值并输出计算A在x处的取值并输出输出B输出B结束进行A+B结束进行A+B的运算输出相加输出相加的结果add11测试条件：问题规模n的数量级为1A多项式每项的系数和指数分别为： B多项式每项的系数和指数分别为： X的值为：2运行出来的结果是：测试结论：通过测试，本程序具有的功能有：多项式的建立、多项式的输入与输出、多项式的相加及相减，多项式求导以及多项式求值。4. 总结 调试时出现的问题及解决的方法输出多项式的时候有些问题，但经过查看是由于输出时没有将各种情况考虑全面的结果。相加相减操作：在刚开始的时候，只考虑了p、q指针均非空的情况，计算的结果就出现了问题，但逐项的运算后，会出现一个还非空但另一个已经遍历完毕的情况，故后又设计让非空的链表继续进行运算，解决了问题。在插入结点的时候出现了一些问题，经查看是尾插法运用地并不熟练，后运用头插法将结点插入链表中，编完