实验链表实验报告

一元多项式表达和相加 实验报告

一、 实验内容和目的

实验目的：掌握单链表的建立、合并和遍历操作

实验内容：1. 单链表的建立（创建一个一元多项式）

2. 单链表的遍历（一元多项式的输出、一元多项式的项数统计） 3. 单链表的合并（一元多项式的加减运算）

二、 实验原理

基本原理：使用单链表储存一元多项式的指数和系数信息。每个结点含有两个数据域，分别用于存放每一项的指数和系数；一个指针域用于存放下一个结点的指针。一个完整的链表表示一个一元多项式。文档来自于网络搜索 单链表的建立：

为了后续操作的方便，本实验中创建的单链表是按指数倒序排序的。 例：创建一元多项式：

为了更好说明建立的过程，输入的过程并非按照指数降序的顺序输入。

实际的输入如下：

步骤一：把最先输入的数据作为链表的第一个结点

步骤二：用第二个数据创建一个新的结点，如果新结点指数大于某个结点，则新的结点插在该结点的前面；否则跟后面一个再比较（源码中p和q指针向链表后移动）；如果新的结点比前面的每一个结点都要小（即q指向链表最后一个结点），则插在链表的末尾端。文档来自于网络搜索 下图为新结点中指数比前面每个结点的指数都要小

1 / 17

如果发现新结点的指数大于链表中某个特定结点时（图中红色数字表示操作顺序）

不断重复上述步骤，直到所有的数据都储存到单链表中。 单链表的合并（即本例中的一元多项式的加减法）：

根据上述的链表创建算法，创建好的链表都具有按指数大小降序的特点。为了确保合并以后的单链表也具有此特点，因此合并的过程中，同样会边合并，边比较大小，从而确保合并的结果仍然具有此特性。文档来自于网络搜索 例：多项式P1为：多项式P2为：

多项式运算P1+P2的结果为：

从上述的链表创建算法可以创建出两个对应的链表

2 / 17

先利用两个指针，Pa和Pb，分别指向两个多项式的结点。

如果Pa指向结点指数大于Pb指向结点的指数，把Pa指向的结点插入到新的链表之中。具体步骤如图

如果Pa指向结点指数小于Pb指向结点的指数，则把Pb指向的结点插入到新的链表之中。具体步骤如图

如果Pa指向的结点指数等于Pb指向的结点指数，则先把两者指向结点指数相加，储存到Pa指向结点中。移动Pa，Pb指针，释放原来Pb指向的结点。具体步骤如图文档来自于网络搜索 一直重复上述操作，当其中一个链表结点已经全部插入到新的链表中时，则把另外

3 / 17

一个链表剩下的所有结点插入到链表之中（即只需要把剩下的结点接起来）。具体步骤

如图文档来自于网络搜索 当完成上述的操作，把Pa指针指向新链表的指向新的链表头。把旧的两个链表头释放掉。

一元多项式的减法，实际上也是一元多项式的加法。程序对于一元多项式的减法处理如下，A和B是两个多项式，A-B = A+(-B)，也就是说，把作为减数的多项式中每一项的系数变成其相反数，然后将两个多项式进行加法运算。文档来自于网络搜索 三、 程序流程图

4 / 17

四、 实验结果

4.1 程序主菜单

4.2 创建多项式

4.3 一元多项式的加法操作

5 / 17