数据结构实验报告
实验名称： 实验1——一元多项式Polynomial 学生姓名： 孙广东 班 级： 2011211109 班内序号： 08 学 号： 2011210251 日 期： 2012年11月1日
1．实验要求
实验目的：
1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 2.学习指针、异常处理的使用 3.掌握单链表的操作的实现方法
4.学习使用线性表解决实际问题的能力
实验内容：
利用线性表实现一个一元多项式Polynomial
f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn 要求：
1． 能够实现一元多项式的输入和输出 2． 能够进行一元多项式相加 3． 能够进行一元多项式相减
4． 能够计算一元多项式在x处的值 5． 能够计算一元多项式的导数（选作） 6． 能够进行一元多项式相乘（选作）
7． 编写测试main()函数测试线性表的正确性 2. 程序分析
由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是带头结点的单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，程序的时间空间复杂度增加，而且顺序表的结点个数动态增加不便，因为决定采用单链表的方式解决。
本程序完成的主要功能：
1. 输入和输出：需要输入的信息有多项式的系数和指数，用来向系统动态申请内存；
系数和指数用来构造每个结点，形成链表。在构造链表的时候我添加了出泡排序以及合并同类项的功能，因此输入时没有要求。输出即是将多项式的内容向屏幕输出。 2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时
第1页
北京邮电大学信息与通信工程学院
要注意判断指数出现的各种不同的情况，分别考虑可能出现的不同情况。将每项运算得到的结果都插入到新的链表中，形成结果多项式。多项式相减可视为加上第二个多项式的相反数。
3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将
指数减1即可，将每项得到的结果更新到结果多项式的链表中。 4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。
2.1 存储结构
本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一 front 个结点的地址。 示意图如下： next …… coef1 expn1 next coef1 expn1 next coef1 expn1 next 1输入多项式 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. cin>>mod>>ind;
7. 运用头插法将结点插入链表。
时间复杂度：o(n)//n为链表长度 空间复杂度：o(n)
2.2冒泡排序算法:
for(int i=0;i 北京邮电大学信息与通信工程学院 if(j!=0) q=q->next; if(p->exp>p->next->exp) { q->next=p->next; p->next=p->next->next; q->next->next=p; } else p=p->next; } } 时间复杂度：o(n2); 空间复杂度：o(1); 2.3.合并同类项算法： 1. 从头遍历每一个结点，比较前后2个结点中exp的值大小 2. 前结点的exp比后一个小，继续向后遍历 3. 前结点的exp与后一个相等，合并，删掉后一个结点，继续遍历 4. 遍历到最后一个结点时结束 1．element*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) 第3页 6 7 8 9 10 11 12 13 14 15 16 17 北京邮电大学信息与通信工程学院 2.4输出多项式算法 ·自然语言描述： 1. 获取头结点； 2. 循环n-1次（n为多项式的项数） 2.1将指针的指向后移； 2.2依照多项式的各种情况，设置输出方式，当下一项系数为负时，不输出+号，否则输出+号 ·伪代码描述： 1element*p=front->next; 2 while(p!=NULL) 3 { 4 if(p->coef) 5 { 6 cout< 0 p=p->next; } 时间复杂度：O(n) 空间复杂度：o(1) 2.5多项式的相加相减 ·自然语言描述： [1]初始化工作指针p和q,以及p节点前驱节点指针p_prior [2]若p和q都不为空,则循环以下操作: [2.1]若p->data.exp [2.2.1]将q结点加入到A链表p结点之前 [2.2.2]q指向B链表的下一个结点 [2.3]否则:p->data.coef=p->data.coef+q->data.coef; [2.3.1]若p->data.coef为0,则删除结点p [2.3.2]p指向下一个结点 [2.3.3]删除q结点 [2.3.4]q指向下一个结点 [3]若p为空并且q不为空,则将q结点及其后所有结点追加到A链表的最后端 [4]将B链表 制成空链表 ·伪代码描述： 1.若p->exp (2)p=p->next; 第4页 北京邮电大学信息与通信工程学院 2.若p->exp>q->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 第5页 北京邮电大学信息与通信工程学院 (b)合并系数不为零,将其从新赋予p结点,主要步骤: (1)pre=p; (2)p=pre->next; (3)Node 4若p为空且q不为空的情况 pre->next=q; 示意图: 第6页 北京邮电大学信息与通信工程学院 时间复杂度：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次求导 ·伪代码描述： cout<<\"\\n输入阶数\"< for(int i=n;i>0;i--)//循环求导 { element*p=pa->next; while(p!=NULL) { p->coef*=p->exp; 第7页 北京邮电大学信息与通信工程学院 p->exp-=1; p=p->next; } } 时间复杂度：O(n*length)//length为链表的长度 空间复杂度：o(1) 3. 程序运行结果 1. 测试主函数流程： 2. 1 开始 3. 4. 5. 设置多项式A的项数和每进行减 6. 项系数及指数 的运算 7. 8. 9. 设置多项式B的项数和每输出相减 10. 项系数及指数 的结果minus 11. 12. 构建多项式A和B 13. 输入x的取值 14. 15. 16. 输出多项式A 计算A在x处17. 的取值并输出 18. 19. 进行对A 输出多项式B 20. 求导数的运算 21. 22. 进行A+B 输出求导 23. 的运算 的结果deri 24. 25. 输出相加 26. 结束 的结果add 27. 28. 29. 30. 1 31. 32. 测试条件：问题规模n的数量级为1 A多项式每项的系数和指数分别为：<1,3> <1,2> <1,4> B多项式每项的系数和指数分别为：<2,2> 第8页 北京邮电大学信息与通信工程学院 C多项式每项的系数和指数分别为：<1,2> X的值为：2 A+B-C带入x运行出来的结果是：32 输入的阶数是:1 测试结论：通过测试，本程序具有的功能有：多项式的建立、多项式的输入与输出、多项式的相加及相减，多项式求导以及多项式求值。 4. 总结 1. 调试时出现的问题及解决的方法 ① 输出多项式的时候有些问题，但经过查看是由于输出时没有将各种情况考虑全面的 结果。 ② 相加相减操作：在刚开始的时候，只考虑了p、q指针均非空的情况，计算的结果 就出现了问题，但逐项的运算后，会出现一个还非空但另一个已经遍历完毕的情况，故后又设计让非空的链表继续进行运算，解决了问题。 ③ 在插入结点的时候出现了一些问题，开始时运动头插法，但发现只能按指数从大到 小的顺序输入，后来添加了排序及合并同类项的算法，使得输入更为方便 ④ 开始算减法的时候只考虑将加法中的+改为-就可以，发现当B指数大于A时，指数 高的项没有减去，后来将减法看成加一个负数得以解决。 2. 心得体会 通过本次实验，我熟悉了链表的相关操作，包括链表的建立、头插法、排序法；同时由于多项式的运算中会出现许多种不同的情况，在这方面也锻炼了我的思维严密性。在编写程序的过程中，编译的时候出现了一些错误，但都经过自己的钻研以及与同学探 第9页 北京邮电大学信息与通信工程学院 讨成功解决。 3. 下一步的改进 ① 本程序没有完成多项式的乘法功能，以后会逐步完善。 ② 界面不够友好，加强人机交互 ③ 应当设置一元多项式类，方便日后的使用 第10页 因篇幅问题不能全部显示，请点此查看更多更全内容