考研专业课之统考计算机蓝宝书(6)

来源：跨考网 2008-11-25 23:48

1.5 例题举例

【例1.1】将顺序表 (a1，a2，... ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大(这里假设数据元素的类型具有可比性, 不妨设为整型)，这一操作称为划分。a1 也称为基准。

划分的方法有多种，下面介绍的划分算法其思路简单，性能较差。

订阅收藏考研专业课之统考计算机蓝宝书

基本思路：
从第二个元素开始到最后一个元素，逐一向后扫描：
(1) 当前数据元素 aI 比 a1 大时，表明它已经在 a1 的后面，不必改变它
与 a1 之间的位置，继续比较下一个
(2) 当前结点若比 a1 小，说明它应该在 a1 的前面，此时将它上面的元素
都依次向下移动一个位置，然后将它置入最上方。
算法如下：

本算法中，有两重循环，外循环执行n－1次，内循环中移动元素的次数与当前数据的大小有关，当第ｉ个元素小于 a1 时，要移动它上面的 i-1个元素，再加上当前结点的保存及置入，所以移动 i-1+2次，在最坏情况下，a1 后面的结点都小于 a1 ，故总的移动次数为：

【例1.2】比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。 A′和B′分别为 A 和 B 中除去最大共同前缀后的子表。

【例1.3】已知单链表H，写一算法将其倒置。即实现如图2.11的操作。(a)为倒置前，(b)为倒置后。

算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下：