实验-一元多项式实验报告【优质】

《实验-一元多项式实验报告【优质】》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验1——一元多项式Polynomial学生姓名：孙广东班级：2011211109班内序号：08学号：2011210251日期：2012年11月1日1．实验要求实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、异常处理的使用3.掌握单链表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+…+anxn要求：1．能够实现一元多项式的输入和输出2．能够进行一元多项式相加3．能够进行一元多项式相减

2、4．能够计算一元多项式在x处的值5．能够计算一元多项式的导数（选作）6．能够进行一元多项式相乘（选作）7．编写测试main()函数测试线性表的正确性2.程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是带头结点的单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，程序的时间空间复杂度增加，而且顺序表的结点个数动态增加不便，因为决定采用单链表的方式解决。本程序完成的主要功能：1.输入和输出：需要输入的信息有多项式的系数和指数，用来向系统动态申请内存；系数和指数用来构造每个结点，

3、形成链表。在构造链表的时候我添加了出泡排序以及合并同类项的功能，因此输入时没有要求。输出即是将多项式的内容向屏幕输出。2.第54页北京邮电大学信息与通信工程学院多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别考虑可能出现的不同情况。将每项运算得到的结果都插入到新的链表中，形成结果多项式。多项式相减可视为加上第二个多项式的相反数。1.多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果更新到结果多项式的链表中。2.多项式在某点的值：由用户输入x的值，然后求出每项的值相加

4、即可。2.1存储结构front本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下：next……coef1expn1nextcoef1expn1nextcoef1expn1next1输入多项式2申请动态内存创建新结点；3输入各项的系数以及指数，分别存入coef和expn；4再将输入的系数以及指数赋给每一个结点的coef和expn域，直到输入系数为0时结束；5利用头插法将每个结点加入链表，形成一元多项式链表。6循环输入：直到系数为0·伪代码：1.element*s=newelement;2.s->coef=mod;3.s->exp=i

5、nd;4.s->next=front->next;5.front->next=s;6.cin>>mod>>ind;7.运用头插法将结点插入链表。时间复杂度：o(n)//n为链表长度空间复杂度：o(n)2.2冒泡排序算法:for(inti=0;inext;4for(intj=0;jnext;4if(p->exp>p->next->exp)5{6q->next=p->next;7p->next=p->

6、next->next;8q->next->next=p;9}10else11p=p->next;12}13}时间复杂度：o(n2);空间复杂度：o(1);2.3.合并同类项算法：1.从头遍历每一个结点，比较前后2个结点中exp的值大小2.前结点的exp比后一个小，继续向后遍历3.前结点的exp与后一个相等，合并，删掉后一个结点，继续遍历4.遍历到最后一个结点时结束1．element*l=front->next;2while(l->next!=NULL)3{4if(l->exp==l->next->exp)5{6l->coef+=l->next->coef;7element*tem

7、p=l->next;8l->next=temp->next;9deletetemp;10}11else12l=l->next;13}时间复杂度：O(n)//n为链表长度空间复杂度：O(1)第54页北京邮电大学信息与通信工程学院2.4输出多项式算法·自然语言描述：1.获取头结点；2.循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式，当下一项系数为负时，不输出+号，否则输出+号·伪代码描述：1element*p=front->next;