北邮数据结构实验一元多项式实验报告.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验一线性表实现一个多项式学生姓名： 黄锦雨班 级：2011211109班内序号： 20学 号： 2011210263日 期： 2012年10月31日实验目的：1.熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容： 利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 要求：1 能够实现一元多项式的输入和输出2 能够进行一元多项式相加3 能够进行一元多项式相减4 能够计算一元多项式在x处的值5 能够计算一元多项式的导数（选作）6 能够进行一元多项式相乘（选作）7 编写测试main()函数测试线性表的正确性2. 程序分析 由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。2.1本程序完成的主要功能：1. 输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。2.2存储结构单链表: 其定义的结点包括三部分：系数、指数以及下一个结点的地址2.3关键算法分析内容要求关键算法：1.一元多项式求和算法: 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链表 制成空链表2.一元多项式求导 1初始化工作指针p及p_prior 2若p不为空,循环以操作2.1若p-data.exp=0;p_prior-next=p-next; delete p; p=p_prior;2.2否则p-data.coef*=p-data.exp; p-data.exp-;3.一元多项式求在X处的值 1初始化工作指针p,定义会参数a 2若p不为空,循环以下操作 a+=p-data.coef*pow(x,p-data.exp);p=p-next;4.输出多项式1获取头结点；2循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式2.2.1 系数为1且指数不为1和0，输出xexpn+； 2.2.2 系数不为0且指数为0，输出（coef）+；2.2.3 系数不为0且指数为1，输出（coef）x+；代码详细分析：求和算法详细分析:1.若p-data.expdata.exp(1)q结点不变(2)p结点向下移(1)p_prior=p;(2)p=p-next; 2.若p-data.expq-data.exp执行一下主要操作步骤(1) p_prior-next=q;(2)p_prior=q;(3)q=q-next;(4)p_prior-next=p;示意图:3.若p-data.exp=q-data.exp执行以下操作步骤: (a)若合并系数为零,则删除p结点,主要步骤:(1)p_prior-next=p-next;(2)delete p;(3)p=p_prior-next;(4)Node*temp=q;(5)q=q-next;(6)delete temp;示意图: (b)合并系数不为零,将其从新赋予p结点,主要步骤: (1)p_prior=p; (2)p=p_prior-next;(3)Node*temp=q; (4)q=q-next; (5)delete temp;示意图:5. 若p为空且q不为空的情况p_prior-next=q;示意图: 3、计算关键算法的时间,空间复杂度时间复杂度(1)一元多项式的构建(2)求和(3)减法(4)求导 时间复杂度都为O(n)空间复杂度为:S(1)2.3 其他内容要求说明:为了防止word版本不一样而可能带来的图形错乱,示意图,流程图都用截图3. 程序运行结果测试主函数流程：流程图如图所示开始设置多项式A的项数和每项系数及指数设置多项式B的项数和每项系数及指数构建多项式A和B输出多项式A和B求多项式A在X=3处的值f(3)输出多项式A求一介导后的结果进行A+B的运算并输出结果进行A-B的运算并输出结果结束4. 总结正文格式要求 见1实验要求中的格式要求1. 这次实现一元多项式的运算运用了模版类,单链表模版类,一元多项式模版类是单链表模版类的的继承,在掌握模版类及链表的同时又复习了上学期的相应内容.2. 这次试验另一比较大的工程是一元多项式加法的算法示意图,以上截图全是我自己一点点打出来又截图完成的,真的是一个比较大工程!3.这次一元多项式实验问题让我的收获很大,对链表的构建更加熟练,