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

数据结构实验报告实验名称:实验1——一元多项式Polynomial学生姓名:孙广东班级:2011211109班内序号:08学号:2011210251日期::++语言的基本编程方法,、:利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+…+anxn要求:能够实现一元多项式的输入和输出能够进行一元多项式相加能够进行一元多项式相减能够计算一元多项式在x处的值能够计算一元多项式的导数(选作)能够进行一元多项式相乘(选作)编写测试main(),故选择线性表来实现,在这个程序中我采用的是带头结点的单链表结构,每个结点代表一个项,多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储,那么对于结点的插入和删除的操作会比较麻烦,程序的时间空间复杂度增加,而且顺序表的结点个数动态增加不便,因为决定采用单链表的方式解决。本程序完成的主要功能:输入和输出:需要输入的信息有多项式的系数和指数,用来向系统动态申请内存;系数和指数用来构造每个结点,形成链表。在构造链表的时候我添加了出泡排序以及合并同类项的功能,因此输入时没有要求。输出即是将多项式的内容向屏幕输出。多项式相加与相减:多项式的加减要指数相同即是同类项才能实现,所以在运算时要注意判断指数出现的各种不同的情况,分别考虑可能出现的不同情况。将每项运算得到的结果都插入到新的链表中,形成结果多项式。多项式相减可视为加上第二个多项式的相反数。多项式的求导运算:多项式的求导根据数学知识,就是将每项的系数乘以指数,将指数减1即可,将每项得到的结果更新到结果多项式的链表中。多项式在某点的值:由用户输入x的值,然后求出每项的值相加即可。,其定义的结点包括三部分:系数、指数以及下一个结点的地址。示意图如下:next……coef1expn1nextcoef1expn1nextcoef1expn1next1输入多项式2申请动态内存创建新结点;3输入各项的系数以及指数,分别存入coef和expn;4再将输入的系数以及指数赋给每一个结点的coef和expn域,直到输入系数为0时结束;5利用头插法将每个结点加入链表,形成一元多项式链表。6循环输入:直到系数为0·伪代码: element*s=newelement; s->coef=mod; s->exp=ind; s->next=front->next; front->next=s;cin>>mod>>ind;运用头插法将结点插入链表。时间复杂度:o(n)//n为链表长度空间复杂度:o(n):for(inti=0;i<n-1;i++)1. { element*p=front; element*q=p;4 p=p->next; for(intj=0;j<n-1;j++) { if(j!=0) q=q->next; if(p->exp>p->next->exp) { q->next=p->next; p->next=p->next->next; q->ne