数据结构试验报告试验一题目3一元多项式

1、数据结构实验报告实验名称：实验一题目3一元多项式学生姓名：许虎班级：信通20班内序号：10学号：2011210578日期：2012年11月2日1.实验要求实验目的：利用线性表实现一个一元多项式Polynomialf（x）=a0+a1x+a2x2+a3x3+,+anxn并实现相应功能。实验内容：使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的main函数测试了其正确性。用户可自行输入正确的多项式进行相关运算，得到相应结果。相关函数实现的功能：1.能够实现一元多项式的输入和输出2 .能够进行一元多项式相加3 .能够进行一元多项式相减4 .能够计算一元多项式在x处的

2、值5 .能够计算一元多项式的导数6 .能够进行两个一元多项式相乘2) 程序分析2.1 存储结构存储结构：单链表（带头节点）单链表示意图如下：front在本程序中使用结构类型element（赋给模版类型T）数组data储存数据成员，包含coef（系数）和exp（指数）两个成员，但仍为一维数组。在节点构造类型Node（运用了模版类）中定义了指针域next指向下一个结点，直到链表尾将next置空，front头指针为该链表类私有数据成员，如此得到多项式链表（单链表）。2.2 关键算法分析1、关键算法：3) 一元多项式类求和函数(1)初始化工作指针p_prior(指向A链表头结点),p(p->ne

3、xt),q(指向B链表第一个结点)。(2)若p和q都不为空，则循环下列操作：(3)若p->data.exp<q->data.exp,贝Up_prior=p;p=p->next。(4)否贝U,若p->data.exp>q->data.exp,贝U：将q结点加入到A链表p结点之前，q指向B链表下移个结点。1) 否贝U,p->data.coef=p->data.coef+q->data.coef;(6)若p->data.coef=0,删除p结点，p指向下一个结点，删除q结点，q指向下一个结点。(7)跳出循环，若p为空且q不为空，则将q

4、结点及其后所有结点追加到A链表的最后。(8)将B链表置空。4) 一元多项式相乘函数(1)设置两个空链表分别为C、D,其中C为储存X每个元素链表与Y链表全部兀素相乘结果的链表，D为最终两个多项式相乘结果的链表。(2)初始化工作指针p1(X链表第一个结点)，p2(Y链表第一个结点)。(3)若p1不为空，则循环下列操作：(4)初始化工作指针p3(指向C链表头结点)，临时指针temp(p2)。(5)当丫链表第一个结点存在，即temp非空时，则循环下列操作：(6)定义新结点s,储存X链表中一个元素与丫链表中一个元素相乘结果，将此结点插入C链表中。(7)如(6)操作，使用尾插法建立了C链表。(8)跳出内循

5、环，将C链表加到D链表中，C链表被置空，p1指针后移一个。(9)跳出外循环，打印出最终的D链表。2、代码详细分析：一元多项式类求和函数(1)情况1,X链元素指数小于Y链元素(p->data.exp<q->data.exp)p_prior=p;p=p->next;情况1示意图(2)情况2,X链元素指数大于Y链元素p_prior->next=q;p_prior=q;q=q->next;p_prior->next=p;情况2示意图p-priorPq(3)情况3,指数相等可相加的情况(I)合并系数为零p_prior->next=p->next;de

6、letep;p=p_prior->next;Node<element>*temp=q;q=q->next;deletetemp;(I)示意图p-priortempq(n)合并系数不为零p_prior=p;p=p_prior->next;Node<element>*temp=q;q=q->next;deletetemp;(n)示意图(4)情况4,q结点及其后所有结点追加到A链表的最后p_prior->next=q;2)一元多项式相乘函数1)每次外循环用尾插法得到链表Cs->data.coef=p1->data.coef*temp-

7、>data.coef;s->data.exp=p1->data.exp+temp->data.exp;p3->next=s;p3=s;p3->next=NULL;示意图以上相应算法步骤说明参见关键算法部分，在此不再赘述。3、计算关键算法的时间、空间复杂度一元多项式类求和函数时间复杂度为O(n),空间复杂度为O(n)一元多项式相乘函数时间复杂度为O(nA2),空间复杂度为O(n2)3其他在此不做具所以不做具:义的对象，相应的减法函数Sub为将Y链个元素系数置空后调用加法函数Add得到,体说明。求多项式的值函数GetValue和求导函数Dir并未改变整个链表的结

8、构，体说明。在相乘函数Mul中传入的形参引用空链表C、D为在main函数中预先)并未写入这个多项式类中。3.程序运行结果1、测试主函数流程图：2、测试条件：输入的值满足数学中定义的一元多项式的有关要求，例如指数为非负的整数多项式元素不能为空或者其他非数字。可以定义多项式元素的数量，但仅能输入两个多项式。3、测试结论：按照相关操作可以很好的完成各项功能，一元多项式加减，求已知x时多项式的值，求导，求乘积都没有错误地得到了正确结果，且反复实验均没有出现问题，测试成功，验证了多项式类及各个函数的正确性。4.总结1、调试时出现的问题及解决的方法Mul中使用。C+不支持这样定义。所以这能在C、D,并作为

9、形参传入Mul函数中使问题一：无法构造两个空链表对象在多项式类相乘函数解决方法：开始时，希望能定义两个私有对象成员，但是main函数中定义并初始化两个空链表对象用。虽然这样做并不完美，但也能实现了函数的功能，并不影响这个程序的正确性。问题二：对于输出时，系数为负，不输出“+”，以及为零项不输出直接跳过，而只有零时又要输出的问题。解决方法：设置多个判断控制输出。若系数不为零则输出，若系数为零且其后为空则输出零，若指数不为零且系数不为零则输出x及系数。若下一个元素不为空且系数为正且当前元素系数不为零则输出“+”。问题三：无法按照用户定义任意元素个数得到多项式。解决方法：由于数组的元素个数必须是常量

10、，所以不能直接将用户所输入的值赋给数组，此时为变量。利用库函数malloc()得到根据用户所输入的值而向系统申请的内存空间，将此空间的头地址赋给相应数组，即可得到根据用户输入值而变化的数组了。也即用户可自定义多项式元素个数。其他小问题基本都可用设置断点，单步调试的方法一一得到解决。2、心得体会通过这次编程练习，让我加深了对单链表的理解，也一定程度上掌握了对单链表的使用，相关的运用得到了锻炼，更加熟练。尤其是这是第一次将类编写到.h文件中，所以也是让我增加了对C+移植性使用，以后可以在进行类似的操作时调用这次编好的.h文件，或者稍微进行相应修改就可使用。这次的另一收获是，让我打破了曾经一直困扰我的数组的大小为预定常数的观念，也让我学会了malloc()函数的使用方法。对于整个数据结构试验的开始而言，这次的结果还是不错的，虽然有些时候还是需要翻阅上学期C+的书查找类相关的知