数据结构实验报告实验一题目3一元多项式.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验一 题目3 一元多项式学生姓名： 许虎班 级： 信通20班内序号： 10学 号： 2011210578日 期： 2012年11月2日1 实验要求实验目的：利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 并实现相应功能。实验内容： 使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的main函数测试了其正确性。用户可自行输入正确的多项式进行相关运算，得到相应结果。相关函数实现的功能：1.能够实现一元多项式的输入和输出2.能够进行一元多项式相加3.能够进行一元多项式相减4.能够计算一元多项式在x处的值5.能够计算一元多项式的导数6.能够进行两个一元多项式相乘2. 程序分析2.1 存储结构存储结构：单链表（带头节点）单链表示意图如下： 在本程序中使用结构类型element（赋给模版类型T）数组data储存数据成员，包含coef（系数）和exp（指数）两个成员，但仍为一维数组。在节点构造类型Node（运用了模版类）中定义了指针域next指向下一个结点，直到链表尾将next置空，front头指针为该链表类私有数据成员，如此得到多项式链表（单链表）。2.2 关键算法分析1、关键算法：1）一元多项式类求和函数（1）初始化工作指针p_prior(指向A链表头结点),p(p-next)，q(指向B链表第一个结点)。（2）若p和q都不为空，则循环下列操作：（3）若p-data.expdata.exp，则p_prior=p;p=p-next。（4）否则，若p-data.expq-data.exp，则： 将q结点加入到A链表p结点之前，q指向B链表下移个结点。（5）否则，p-data.coef=p-data.coef+q-data.coef;（6）若p-data.coef=0，删除p结点，p指向下一个结点，删除q结点，q指向下一个结点。（7）跳出循环，若p为空且q不为空，则将q结点及其后所有结点追加到A链表的最后。（8）将B链表置空。2）一元多项式相乘函数（1）设置两个空链表分别为C、D，其中C为储存X每个元素链表与Y链表全部元素相乘结果的链表，D为最终两个多项式相乘结果的链表。（2）初始化工作指针p1（X链表第一个结点），p2（Y链表第一个结点）。（3）若p1不为空，则循环下列操作：（4）初始化工作指针p3（指向C链表头结点），临时指针temp（p2）。（5）当Y链表第一个结点存在，即temp非空时，则循环下列操作：（6）定义新结点s，储存X链表中一个元素与Y链表中一个元素相乘结果，将此结点插入C链表中。（7）如（6）操作，使用尾插法建立了C链表。（8）跳出内循环，将C链表加到D链表中，C链表被置空，p1指针后移一个。（9）跳出外循环，打印出最终的D链表。2、代码详细分析：1）一元多项式类求和函数（1）情况1,X链元素指数小于Y链元素（p-data.exp data.exp）p_prior=p;p=p-next; 情况1示意图pp-prior（2）情况2，X链元素指数大于Y链元素p_prior-next=q; p_prior=q;q=q-next;p_prior-next=p; 情况2示意图 pp-priorq（3）情况3，指数相等可相加的情况（）合并系数为零 p_prior-next = p-next; delete p; p = p_prior-next; Node * temp = q; q = q-next; delete temp; ()示意图p-priorpqtempq（）合并系数不为零 p_prior = p; p=p_prior-next; Node * temp = q; q = q-next; delete temp; （）示意图pp-priorqtemp（4）情况4， q结点及其后所有结点追加到A链表的最后 p_prior-next=q;2）一元多项式相乘函数(1)每次外循环用尾插法得到链表Cs-data.coef=p1-data.coef*temp-data.coef;s-data.exp=p1-data.exp+temp-data.exp;p3-next=s;p3=s; p3-next=NULL; 示意图q3 s以上相应算法步骤说明参见关键算法部分，在此不再赘述。3、计算关键算法的时间、空间复杂度1）一元多项式类求和函数时间复杂度为O（n），空间复杂度为O（n）2）一元多项式相乘函数时间复杂度为O（n2），空间复杂度为O（n2）2.3 其他相应的减法函数Sub为将Y链个元素系数置空后调用加法函数Add得到，在此不做具体说明。求多项式的值函数GetValue和求导函数Dir并未改变整个链表的结构，所以不做具体说明。在相乘函数Mul中传入的形参引用空链表C、D为在main函数中预先定义的对象，并未写入这个多项式类中。3. 程序运行结果1、测试主函数流程图：开始等待用户输入进行相应运算，并输出相应结果结束2、测试条件：输入的值满足数学中定义的一元多项式的有关要求，例如指数为非负的整数多项式元素不能为空或者其他非数字。可以定义多项式元素的数量，但仅能输入两个多项式。3、测试结论：按照相关操作可以很好的完成各项功能，一元多项式加减，求已知x时多项式的值，求导，求乘积都没有错误地得到了正确结果，且反复实验均没有出现问题，测试成功，验证了多项式类及各个函数的正确性。4. 总结 1、调试时出现的问题及解决的方法问题一：无法构造两个空链表对象在多项式类相乘函数Mul中使用。解决方法：开始时，希望能定义两个私有对象成员，但是C+不支持这样定义。所以这能在main函数中定义并初始化两个空链表对象C、D，并作为形参传入Mul函数中使用。虽然这样做并不完美，但也能实现了函数的功能，并不影响这个程序的正确性。问题二：对于输出时，系数为负，不输出“+”，以及为零项不输出直接跳过，而只有零时又要输出的问题。解决方法：设置多个判断控制输出。若系数不为零则输出，若系数为零且其后为空则输出零，若指数不为零且系数不为零则输出x及系数。若下一个元素不为空且系数为正且当前元素系数不为零则输出“+”。问题三：无法按照用户定义任意元素个数得到多项式。解决方法：由于数组的元素个数必须是常量，所以不能直接将用户所输入的值赋给数组，此时为变量。利用库函数malloc（）得到根据用户所输入的值而向系统申请的内存空间，将此空间的头地址赋给相应数组，即可得到根据用户输入值而变化的数组了。也即用户可自定义多项式元素个数。其他小问题基本都可用设置断点，单步调试的方法一一得到解决。2、心得体会 通过这次编程练习，让我加深了对单链表的理解，也一定程度上掌握了对单链表的使用，相关的运用得到了锻炼，更加熟练。尤其是这是第一次将类编写到.h文件中，所以也是让我增加了对C+移植性使用，以后可以在进行类似的操作时调用这次编好的.h文件，或者稍微进行相应修改就可使用。这次的另一收获是，让我打破了曾经一直困扰我的数组的大小为预定常数的观念，也让我学会了malloc（）函数的使用方法。对于整个数据结构试验的开始而言，这次的结果还是不错的，虽然有些时候还是需要翻阅上学期C+的书查找类相关的知识点，但这为