2.2.4 顺序表应用举例

【例2.1】 利用线性表的基本运算，实现如果在线性表A中出现的元素，在线性表B中也出现，则将A中的该元素删除。

分析：这其实是求两个表的差集，即A-B。依次检查线性表B中的每一个元素，如果该元素在线性表A中也出现，则在A中删除该元素。

求A-B的差集算法如下：

测试程序如下：

程序运行结果如图2.6所示。

【例2.2】 编写一个算法，把一个顺序表分拆成两个部分，使顺序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如，顺序表（-12，3，-6，-10，20，-7，9，-20）经过分拆调整后变为（-12，-20，-6，-10，-7，20，9，3）。

【分析】设置两个指示器i和j，分别扫描顺序表中的元素，i和j分别从顺序表的左端和右端开始扫描。如果i遇到小于等于0的元素，略过不处理，继续向前扫描；如果遇到大于0的元素，暂停扫描；如果j遇到大于0的元素，略过不处理，继续向前扫描；如果遇到小于等于0的元素，暂停扫描。如果i和j都停下来，则交换i和j指向的元素。重复执行直到i≥j为止。

算法描述如下：

测试程序如下：

程序运行结果如图2.7所示。