本节将介绍顺序表的合并，单链表的逆置、合并等较复杂的操作实现。

2.3.1 顺序表的其他操作

在实际问题中，除了2.1.2节介绍的针对顺序表的基本操作以外，还会有合并顺序表等特殊要求的一些操作，本节将介绍这些操作的实现。本节所有算法都是基于通用性增强的顺序表的类型定义。

【 例2-1 】假设有两个集合 A 和 B ，完成求这两个集合并集 A = A ∪ B 的操作。

分析：可以用顺序表来表示集合。分别用顺序表La和Lb来存储集合 A 和 B 中的元素。 A = A ∪ B 的操作就可转换为将顺序表Lb中所有在La中不存在的数据元素插入到La中。算法的具体实现如算法2-16所示。

算法2-16 求集合的并集

通过上面这个例子可以看出，在解决实际问题时，遇到一些特殊的操作要求，可以利用已有的基本操作组合完成一个新的操作算法。

【 例2-2 】假设顺序表L中的数据元素递增有序，试设计一个算法，将元素 x 插入到顺序表L的适当位置上，以保持该表的有序性。

分析：本例可以仿照顺序表的基本插入操作进行，不同之处在于需要先找到插入位置的下标 i 。算法步骤如下：

1）检查顺序表的存储空间是否已到最大值（被占满），若是则停止插入，并给出提示；否则执行步骤2）。

2）查找插入位置的下标。

3）从最后一个元素（下标为length-1）向前直至下标为 i 的元素为止，将每一个元素均后移一个存储单元，将下标为 i 的元素的存储位置空出。

4）将新元素 x 写入到下标为 i 的位置。

5）将顺序表长度加1。

有序表插入算法的具体实现如算法2-17所示。

算法2-17 有序表的插入

请读者进一步思考，上述算法中的查找与后移是否可以合并在一起完成。

2.3.2 单链表的其他操作

与顺序表类似，在实际问题中，还会有合并单链表等特殊要求的一些操作，本节将介绍这些操作的实现。

【 例2-3 】单链表的逆置。

将一个单链表按逆序链接，即若原单链表中存储元素的次序为 a ₁ ， a ₂ ，…， a _{n -1} ， a _n ，则逆序链接后变为 a _n ， a _{n -1} ，…， a ₂ ， a ₁ 。

图2-16a为逆置前，图2-16b为逆置后。

设想逆置后的单链表是一个新建的链表，但表中的结点不是新生成的，而是从原单链表（待逆置）中依次“删除”得到的。算法步骤如下：

1）将逆置后的单链表初始化为一空表。

2）依次“删除”原单链表中的结点，并将其“插入”到逆置后单链表的表头，直至原链表为空。

具体实现如算法2-18所示。

算法2-18 单链表的逆置

【 例2-4 】合并两个有序单链表。

已知递增有序的两个单链表La和Lb，要求将Lb合并到La中，且结果链表依然保持递增有序。

为了实现合并操作，设置3个指针，指针pa和pb分别指向单链表La和Lb中等待比较的数据结点，指针pc始终指向结果单链表的表尾。

算法步骤如下。

1）初始化指针，使指针pa指向单链表La的第一个数据结点，指针pb指向单链表Lb的第一个数据结点，指针pc指向单链表La的头结点。

2）当pa和pb都不为空时，执行以下操作：

如果pa-＞data小于pb-＞data，则将pa所指向的结点链入结果有序单链表的表尾，并将指针pa和pc后移。

否则将pb所指向的结点链入结果有序单链表的表尾，并将指针pb和pc后移。

3）如果pa不为空，则将pa所指向的剩余结点链入结果有序单链表的表尾；如果pb不为空，则将pb所指向的剩余结点链入结果有序单链表的表尾。

具体实现如算法2-19所示。

算法2-19 合并有序单链表

请读者参考本算法思想，思考完成课后练习“算法设计题”的第8题，即实现两个有序顺序表的合并。

【 例2-5 】两个一元多项式相加

可将合并有序单链表的原理。拓展到一元多项式相加的问题上。已知按升幂表示的两个一元多项式： A （ x ）= a ₀ + a ₁ x + a ₂ x ² +…+ a _n x ⁿ 和 B （ x ）= b ₀ + b ₁ x + b ₂ x ² +…+ b _m x ^m ，求 A （ x ）= A （ x ）+ B （ x ）。

对于任意一元多项式 P （ x ）= p ₀ + p ₁ x + p ₂ x ² +…+ p _n x ⁿ ，可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的，即 P =（（ p ₀ ，0），（ p ₁ ，1），（ p ₂ ，2），…，（ p _n ， n ））。

在多项式相加时，所产生的结果多项式的项数和次数都是难以预料的，因此计算机实现时，可采用单链表来表示。多项式中的每一项为单链表中的一个结点，每个结点包含3个域：系数域（coef）、指数域（exp）和指针域（next），其形式如图2-17所示。

定义如下：

只要将2.3.1节中单链表节点类型定义的Node换成struct PolyNode，就可得到一元多项式单链表的定义。

设有两个一元多项式为 A （ x ）=12+3 x ² +8 x ⁷ +5 x ⁹ 和 B （ x ）= -3 x ² +10 x ⁷ +6 x ⁸ +7 x ¹²

它们的链表结构如图2-18所示。

一元多项式相加的运算规则如下：两个多项式中所有指数相同的项，对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不同的项均复制到“和多项式”中。

利用单链表存放一元多项式后，多项式相加就可演变为合并两个有序单链表。分别用两个指针pa和pb指向两个一元多项式单链表的开始结点。合并过程实际上是对两个单链表中相应结点的指数域进行比较，根据比较结果来决定操作方法，具体情况如下：

1）如果pa-＞exp＜pb-＞exp，则表明pa所指结点应该为结果中的结点，则pa指针后移，如图2-19所示。

2）如果pa-＞exp=pb-＞exp，则合并同类项，即系数相加pa-＞coef=pa-＞coef+pb-＞coef。

若相加结果pa-＞coef=0，结果中不再有系数为pa-＞exp的项，则删除pa和pb所指结点，且pa和pb指针均后移，如图2-20a所示。

若相加结果pa-＞coef≠0，表明pa所指结点为结果中的结点，则删除pb所指结点，且pa和pb指针均后移，如图2-20b所示。

3）如果pa-＞exp＞pb-＞exp，表明pb所指结点应该为结果中的结点，则将pb所指结点链入单链表A中，且pb指针后移，如图2-21所示。

此外，还应当考虑两个一元多项式项数不同的情况，请读者自行完成算法的实现。

2.3.3 顺序表和链表的综合比较

线性表的顺序表和单链表两种表示方法各有优劣：顺序表可按序号进行随机访问，但其插入和删除操作由于需要移动表长一半的元素，因此时间复杂度均为 O （ n ）；单链表只能从表头开始依次向后扫描，因此无法按序号进行随机访问，但其插入和删除无须移动元素，因此在给出单链表某个结点的指针后，其插入和删除操作的时间复杂度均为 O （ n ）。

在实际应用时，选用哪种结构应根据具体问题进行具体分析，通常可从以下两个方面考虑。

1）线性表的长度 n 能否预先确定？在程序执行过程中， n 的变化范围多大？

由于顺序表需要预分配一定长度的存储空间，如果事先不能明确知道线性表的大致长度，则有可能对存储空间预分配得过大，致使在程序执行过程中很大一部分的存储空间得不到充分利用，而造成浪费。若估计得太小，又将造成频繁地进行存储空间的再分配。链表的显著优点之一就是其存储分配的灵活性，不需要为链表预分配空间，链表中的结点可在程序执行过程中随时根据需要动态生成（只要内存尚有可分配的空间）。因此，当线性表的长度变化较大或难以估计最大值时，宜采用链表存储结构。反之，当线性表的长度变化不大，且能事先确定变化的大致范围时，宜采用顺序存储结构。

2）对线性表进行的主要操作是哪些？

顺序表是一种随机存储的结构，对顺序表中任一元素进行存取的时间相同。链表是一种顺序存取的结构，对链表中的每个结点都必须从头指针所指结点起顺链扫描。因此，若线性表需频繁查询，却很少进行插入和删除时，宜采用顺序表作存储结构。另外，由于顺序表中以一维数组存储数据元素，数组中第 i 个分量的元素即为线性表中第 i 个数据元素，因此对于那些和“位序”密切相关的操作采用顺序表则比较方便。

由于在顺序表中进行插入和删除时，需要移动将近表长一半的元素，这在线性表中元素个数很多时，特别是当每个元素占用的空间也较多时，移动元素的时间开销会很大。而在链表的任何位置上进行插入或删除时，只需要修改少量指针。因此，若线性表需频繁进行插入或删除操作，则宜采用链表作存储结构。 4pj0QUFOksySPpyRew3v023Is0S3tnWdpSSLZiDVVCQqrN6Ag4zwRQoaHMJMc9wx