1.2 性表的实现

1.2.3 线性表的应用

　　线性表是一种应用很广的数据结构，一方面，线性表是最基础的数据结构，很多其他数据结构的实现都离不开线性表的支持，例如，栈、树的表示等；另一方面，顺序表简单方便、链表操作灵活，它们本身就可以应用在很多实践中，例如，一元多项式的存储等。
　　线性表之间常见的运算如下：
　　① 求并运算A∪B。将线性表A和B合并为一个线性表，在有序表中通常要求相同的元素只保留一次。
　　② 求交运算A∩B。获取在线性表A、B中都存在的元素。
　　③ 求差运算A-B（或B-A）。获取在线性表A（B）中但不在线性表B（A）中的元素。
　　如果线性表中的数据元素相互之间可以比较，并且数据元素在线性表中非递减（非递增）有序排列，即a_i+1≤a_i (a_i ≤a_i+1)(i = 1,2,3,…,n)，则称该线性表为有序表。有序表在执行以上操作时可以减少比较元素的次数，降低时间复杂度。
　　【例1-6】设有顺序结构线性表LA与LB，其结点数据元素为整数，并且非递减有序，假设线性表空间足够大，试给出一种最大限度避免移动元素的算法，将LB中的元素合到LA中，使新的LA的元素仍保持非递减有序。
　　【解析】将元素一次到位复制到新链表的位置上可以尽量少地移动元素，采用从后到前的遍历方式，定义变量cur为新线性表LA中当前的插入位置，变量pa为原线性表LA中的遍历位置，变量pb为原线性表LB中的遍历位置。
　　① 将cur、pa、pb分别赋值为新线性表LA、线性表LA和线性表LB中尾结点的位置：
　　
　　② 分别从LA和LB的尾部向前遍历链表，同时比较两表中元素LA．Elem[pa]和元素LB．Elem[pb]的大小，将大者移动到新线性表LA中下标cur处，并将大者所指线性表的遍历位置向前移动一个，即pa--或pb--。
　　③ 将新线性表LA中下一个插入元素的位置向前移动一个位置，即cur--。
　　④ 如果有链表遍历完毕（即遍历到链表头），则执行下一步，否则回到第②步继续执行。
　　⑤ 如果LB遍历完毕，则算法结束。否则将LB中未遍历部分按非递减顺序移动为LA中第1～cur+1个数据元素。
　　关键代码如下：

　　【例1-7】已知两个带头结点的线性链表LA和LB中的结点均按照元素值从小到大非递减排列（链表LA和LB之间可能存在两个以上值相同的结点，但是单个链表内部的元素值均不相同），编写算法对LA表进行如下操作：使操作后的链表LA中仅留下LA表和LB表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用的结点。限定算法的时间复杂度为O(m+n)，其中m和n分别为LA表和LB表的长度。
　　【解析】可按如下步骤执行：
　　① 从头结点开始从前向后遍历链表LA和LB，并且比较两链表中当前结点的直接后继的取值：如果相等，则LA的当前元素下移一位，并删除LB中当前元素的直接后继结点；如果不相等，则删除数值小者所在线性链表的当前元素的直接后继结点。
　　② 循环执行以上步骤，直到某个线性链表遍历结束。
　　③ 销毁LB。
　　此时，LA即为所求，关键代码如下：

　　此类应用一般通过最小的遍历次数完成实际需求。