2.2.3　典型例题解析

【例2-1】假设线性表LA和LB分别表示两个集合A和B，利用线性表的基本运算实现新的集合A=A∪B，即扩大线性表LA，将存在于线性表B中且不存在于A中的元素插入A中。

【分析】只有依次从线性表LB中取出每个数据元素，并依次在线性表LA中查找该元素，如果LA中不存在该元素，则将该元素插入LA中。程序的实现代码如下：

程序运行结果如图2-4所示。

【例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-5所示。

【考研真题】将n（n>1）个整数存放到一维数组R中，试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0<p<n）个位置，即把R中的数据序列由（x₀，x₁，…，x_n-1）变换为（x_p，x_p+1，…，x_n-1，x₀，x₁，…，x_p-1）。要求如下：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C语言描述算法。

（3）说明所设计算法的时间复杂度和空间复杂度。

【分析】该题目主要考查对顺序表的掌握情况，具有一定的灵活性。

（1）先将这n个元素序列（x₀，x₁，…，x_p，x_p+1，…，x_n-1）就地逆置，得到（x_n-1，x_n-2，…，x_p，x_p-1，…，x₀），然后再将前n-p个元素（x_n-1，x_n-2，…，x_p）和后p个元素（x_p-1，x_p-2，…，x₀）分别就地逆置，得到最终结果（x_p，x_p+1，…，x_n-1，x₀，x₁，…，x_p-1）。

（2）算法实现，可用Reverse和LeftShift两个函数实现。

（3）上述算法的时间复杂度为O（n），空间复杂度为O（1）。

【2018年计算机统考试题】给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组｛-5，3，2，3｝中未出现的最小正整数是1，数组｛1，2，3｝中未出现的最小正整数是4。要求如下：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

【分析】为了设计出尽可能高效的算法，设置一个辅助数组b［］，用于表示数组a［］中是否存在1~n之间的正整数，其中，b［1］表示是否存在整数1，b［2］表示是否存在整数2，…，b［n］表示是否存在整数n。例如，对于｛-5，3，2，3｝，不存在最小整数1，因此返回1；对于｛1，2，3｝，返回4。如果a［］中的数位于1~n之间，则将对应位置上的元素置为1；然后依次遍历数组b［］中元素，若b［i］为0，则表明a［］中不存在整数i，则返回i；若b［i］都不为0，则返回n+1，表明a［］中未出现的最小正整数是n+1。

该算法的主要执行时间耗费在3个for循环上，即数组b［］的初始化、标记数组b［］中的元素、查找不存在的最小正整数，故时间复杂度为O（n）。该算法引入了辅助数组b［］，故空间复杂度为O（n）。