实验1-一元多项式实验报告.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验1一元多项式Polynomial学生姓名： 孙广东班 级： 2011211109班内序号： 08学 号： 2011210251日 期： 2012年11月1日1实验要求实验目的：1.熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、异常处理的使用3.掌握单链表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容： 利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 要求：1 能够实现一元多项式的输入和输出2 能够进行一元多项式相加3 能够进行一元多项式相减4 能够计算一元多项式在x处的值5 能够计算一元多项式的导数（选作）6 能够进行一元多项式相乘（选作）7 编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是带头结点的单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，程序的时间空间复杂度增加，而且顺序表的结点个数动态增加不便，因为决定采用单链表的方式解决。本程序完成的主要功能：1. 输入和输出：需要输入的信息有多项式的系数和指数，用来向系统动态申请内存；系数和指数用来构造每个结点，形成链表。在构造链表的时候我添加了出泡排序以及合并同类项的功能，因此输入时没有要求。输出即是将多项式的内容向屏幕输出。2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别考虑可能出现的不同情况。将每项运算得到的结果都插入到新的链表中，形成结果多项式。多项式相减可视为加上第二个多项式的相反数。3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果更新到结果多项式的链表中。4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。 2.1 存储结构front本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下： nextcoef1 expn1 nextcoef1 expn1 nextcoef1 expn1 next1输入多项式2申请动态内存创建新结点；3输入各项的系数以及指数，分别存入coef和expn；4再将输入的系数以及指数赋给每一个结点的coef和expn域，直到输入系数为0时结束； 5利用头插法将每个结点加入链表，形成一元多项式链表。6循环输入：直到系数为0伪代码：1. element*s=new element;2. s-coef=mod;3. s-exp=ind;4. s-next=front-next;5. front-next=s;6. cinmodind;7. 运用头插法将结点插入链表。时间复杂度：o(n)/n为链表长度空间复杂度：o(n)2.2冒泡排序算法: for(int i=0;inext;4 for(int j=0;jnext;8 if(p-expp-next-exp)9 10 q-next=p-next;11 p-next=p-next-next;12 q-next-next=p;13 14 else15 p=p-next;16 17 时间复杂度：o(n2);空间复杂度：o(1);2.3.合并同类项算法：1. 从头遍历每一个结点，比较前后2个结点中exp的值大小2. 前结点的exp比后一个小，继续向后遍历3. 前结点的exp与后一个相等，合并，删掉后一个结点，继续遍历4. 遍历到最后一个结点时结束1element*l=front-next ;2 while(l-next !=NULL)3 4 if(l-exp=l-next -exp)5 6 l-coef +=l-next -coef ;7 element*temp=l-next ;8 l-next =temp-next ;9 delete temp;10 11 else 12 l=l-next ;13 时间复杂度：O(n)/n为链表长度空间复杂度：O(1)2.4输出多项式算法自然语言描述：1. 获取头结点；2. 循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式，当下一项系数为负时，不输出+号，否则输出+号 伪代码描述：1element*p=front-next;2while(p!=NULL)34if(p-coef)56coutcoef *xexp;7if(p-next!=NULL&p-next-coef0)8coutnext;时间复杂度：O(n)空间复杂度：o(1)2.5多项式的相加相减自然语言描述：1初始化工作指针p和q,以及p节点前驱节点指针p_prior 2若p和q都不为空,则循环以下操作:2.1若p-data.expdata.exp,则p_prior=p;p=p-nenx;2.2否则,若p-data.expq-data.exp,则: 2.2.1将q结点加入到A链表p结点之前 2.2.2q指向B链表的下一个结点2.3否则:p-data.coef=p-data.coef+q-data.coef; 2.3.1若p-data.coef为0,则删除结点p 2.3.2p指向下一个结点 2.3.3删除q结点 2.3.4q指向下一个结点3若p为空并且q不为空,则将q结点及其后所有结点追加到A链表的最后端 4将B链表 制成空链表 伪代码描述：1.若p-expexp(1)q结点不变(2)p结点向下移(1)pre=p;(2)p=p-next; 2.若p-expq-exp执行一下主要操作步骤(1) pre-next=q;(2)pre=q;(3)q=q-next;(4)pre-next=p;示意图:3.若p-exp=q-exp执行以下操作步骤: (a)若合并系数为零,则删除p结点,主要步骤:(1)pre-next=p-next;(2)delete p;(3)p=pre-next;(4)Node*temp=q;(5)q=q-next;(6)delete temp;示意图: (b)合并系数不为零,将其从新赋予p结点,主要步骤: (1)pre=p; (2)p=pre-next;(3)Node*temp=q; (4)q=q-next; (5)delete temp;示意图:4若p为空且q不为空的情况pre-next=q;示意图: 时间复杂度：0（m+n）m为多项式A的长度，n为多项式B的长度空间复杂度：0（1） 2.6求值算法自然语言描述：1. 将工作指针指向多项式的第一项；2. 将结果result置为0；3. 指针不为空，即进行循环：3.1 result+=p-coef*(pow(x,p-expn); 3.2 p=p-next; 4返回sum； 伪代码描述：1. element* p=front-next;2. double result=0;3. while(p-next!=NULL)3.1 result+=p-coef*(pow(x,p-expn); 3.2 p=p -next; 4. return sum;时间复杂度：O(n)/n为链表长度空间复杂度：o(1)2.7求导数自然语言描述：1. 输入要求导的阶数n;2. 将指针指到多项式的第一项的结点：element* p=front-next;3. 指针指向NULL时结束一次求导3.1 每项求导的系数为：p-coef*p-expn;指数为：p-expn-1;3.2 将新结点插入新链表；3.3 指针p后移。 4循环n次求导 伪代码描述：coutn输入阶数n;for(int i=n;i0;i-)/循环求导element*p=pa-next;while(p!=NULL)p-coef*=p-exp;p-exp-=1;p=p-next;时间复杂度：O(n*length)/length为链表的长度空间复杂度：o(1)3. 程序运行结果1. 测试主函数流程：开始12.3.4.设置多项式A的项数和每项系数及指数进行减的运算5.6.7.设置多项式B的项数和每项系数及指数8.输出相减的结果minus9.10.11.构建多项式A和B12.输入x的取值13.14.计算A在x处的取值并输出输出多项式A15.16.17.进行对A求导数的运算18.输出多项式B19.20.21.输出求导的结果deri进行A+B的运算22.结束23.24.输出相加的结果add25.26.27.28.129.30.31.32.测试条件：问题规模n的数量级为1A多项式每项的系数和指数分别为： B多项式每项的系数和指数分别为： C多项式每项的系数和指数分别为：X的值为：2A+B-C带入x运行出来的结果是：32输入的阶数是:1测试结论：通过测试，本程序具有的功能有：多项式的建立、多项式的输入与输出、多项式的相加及相减，多项式求导以及多项式求值。4. 总结 1. 调试时出现的问题及解决的方法 输出多项式的时候有些问题，但经过查看是由于输出时没有将各种情况考虑全面的结果。 相加相减操作：在刚开始的时候，只考虑了p、q指针均非空的情况，计算的结果就出现了问题，但逐项的运算后，会出现一个还非空但另一个已经遍历完毕的情况，故后又设计让非空的链表继续进行运算，解决了问题。 在插入结点的时候出现了一些问题，开始时运动头插法，但发现只能按指数从大到小的顺序输入，后来添加了排序及合并同类项的算法，使得输入更为方便 开始算减法的时候只考虑将加法中的+改为-就可以，发现当B指数大于A时，指数高的项没有减去，后来