2024年4月30日发(作者：)

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

一、 实验内容和目的

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

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

2. 单链表的遍历（一元多项式的输出、一元多项式的项数统计）

3. 单链表的合并（一元多项式的加减运算）

二、 实验原理

基本原理：使用单链表储存一元多项式的指数和系数信息。每个结点含有两个数据域，

分别用于存放每一项的指数和系数；一个指针域用于存放下一个结点的指针。一个完整

的链表表示一个一元多项式。

文档来自于网络搜索

单链表的建立：

为了后续操作的方便，本实验中创建的单链表是按指数倒序排序的。

例：创建一元多项式：

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

实际的输入如下：

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

步骤二：用第二个数据创建一个新的结点，如果新结点指数大于某个结点，则新的

结点插在该结点的前面；否则跟后面一个再比较（源码中p和q指针向链表后移动）；

如果新的结点比前面的每一个结点都要小（即q指向链表最后一个结点），则插在链表

的末尾端。

文档来自于网络搜索

下图为新结点中指数比前面每个结点的指数都要小

1 / 17

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

不断重复上述步骤，直到所有的数据都储存到单链表中。

单链表的合并（即本例中的一元多项式的加减法）：

根据上述的链表创建算法，创建好的链表都具有按指数大小降序的特点。为了确保

合并以后的单链表也具有此特点，因此合并的过程中，同样会边合并，边比较大小，从

而确保合并的结果仍然具有此特性。

文档来自于网络搜索

例：多项式P

1

为：

多项式P

2

为：

多项式运算P

1

+P

2

的结果为：

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

2 / 17