数据结构实验报告
实验名称： 实验一 题目3 一元多项式
学生姓名： 许虎
班 级： 信通20
班内序号： 10
学 号： 2011210578
日 期： 2012年11月2日
1． 实验要求
实验目的：
利用线性表实现一个一元多项式Polynomial f (x ) = a 0 + a 1x + a 2x 2 + a 3x 3 + „ + a n x n
并实现相应功能。
实验内容：
使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的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.exp>q->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示意图
（2）情况2，X 链元素指数大于Y 链元素
①p_prior->next=q;
②p_prior=q;
③q=q->next;
④p_prior->next=p;
情况2示意图
（3）情况3，指数相等可相加的情况
（Ⅰ）合并系数为零
① p_prior->next = p->next;
② delete p;
③ p = p_prior->next;
④ Node * temp = q;
⑤ q = q->next;
⑥ delete temp;
(Ⅰ) 示意图
（Ⅱ）合并系数不为零
① p_prior = p;
② p=p_prior->next;
③
Node * temp = q;
④ q = q->next;
⑤ delete temp;
① p_prior->next=q;
2
）一元多项式相乘函数
(1)每次外循环用尾插法得到链表C
①s->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;
示意图
以上相应算法步骤说明参见关键算法部分，在此不再赘述。
3、计算关键算法的时间、空间复杂度
1）一元多项式类求和函数
时间复杂度为O （n ），空间复杂度为O （n ）
2）一元多项式相乘函数
时间复杂度为O （n^2），空间复杂度为O （n^2）
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++的书查找类相关的知识点，但这为接下来的编程打下了一定的基础，相信通过不断的练习，这点不久就会摆脱。
3、下一步的改进
将C 、D 链的定义和初始化包含的类的定义实现中去，或通过其他手段达到此目的。编写扩展的函数能够进行一元多项式的除法运算，不过感觉意义不大。扩展一元多项式的个数，使其可进行3个甚至任意个多项式的运算。增加元数，扩展到多元多项式运算。
数据结构实验报告
实验名称： 实验一 题目3 一元多项式
学生姓名： 许虎
班 级： 信通20
班内序号： 10
学 号： 2011210578
日 期： 2012年11月2日
1． 实验要求
实验目的：
利用线性表实现一个一元多项式Polynomial f (x ) = a 0 + a 1x + a 2x 2 + a 3x 3 + „ + a n x n
并实现相应功能。
实验内容：
使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的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.exp>q->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示意图
（2）情况2，X 链元素指数大于Y 链元素
①p_prior->next=q;
②p_prior=q;
③q=q->next;
④p_prior->next=p;
情况2示意图
（3）情况3，指数相等可相加的情况
（Ⅰ）合并系数为零
① p_prior->next = p->next;
② delete p;
③ p = p_prior->next;
④ Node * temp = q;
⑤ q = q->next;
⑥ delete temp;
(Ⅰ) 示意图
（Ⅱ）合并系数不为零
① p_prior = p;
② p=p_prior->next;
③
Node * temp = q;
④ q = q->next;
⑤ delete temp;
① p_prior->next=q;
2
）一元多项式相乘函数
(1)每次外循环用尾插法得到链表C
①s->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;
示意图
以上相应算法步骤说明参见关键算法部分，在此不再赘述。
3、计算关键算法的时间、空间复杂度
1）一元多项式类求和函数
时间复杂度为O （n ），空间复杂度为O （n ）
2）一元多项式相乘函数
时间复杂度为O （n^2），空间复杂度为O （n^2）
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++的书查找类相关的知识点，但这为接下来的编程打下了一定的基础，相信通过不断的练习，这点不久就会摆脱。
3、下一步的改进
将C 、D 链的定义和初始化包含的类的定义实现中去，或通过其他手段达到此目的。编写扩展的函数能够进行一元多项式的除法运算，不过感觉意义不大。扩展一元多项式的个数，使其可进行3个甚至任意个多项式的运算。增加元数，扩展到多元多项式运算。