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

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为空时结束。算法如下：

• ·2010年迦思佑考研6000词逻辑辨证记忆
• ·2010年迦思佑张纪元考研6000词汇记忆课堂录音
• ·10版研究生英语难句过关-盘内容
• ·【VIP专享】2009新东方考研英语复试听力(音频+讲义)
• ·沪江考研原创：和我一起突破考研长难句1-33
• ·胡敏考研英语词汇-读故事记单词（09最新版）MP3
• ·2010淘金高阶考研英语词汇词典版MP3
• ·2010考研英语阅读理解精读100篇（高分版）文本下载
• ·2009年考研英语大纲词汇
• ·2010考研英语万能作文MP3

• 一月速背6000单词
• 英语口语需要自然流露
• 7月名师讲座
• 点滴积累学英语系列之一
• 点滴积累学英语系列之二