计算机软件技术基础 数据结构与算法（5）

数据结构研究的内容

2.5 查找 基本概念 是一种数据结构 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——若表中存在特定元素，称查找成功（应输出该记录） ——否则，称查找不成功（也应输出失败信息） ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 （预先确定的记录的某种标志 ） 例如“学号”

讨论1：查找的过程是怎样的？ 讨论2：对查找表常用的操作有哪些？ 讨论3：有哪些查找方法？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 讨论2：对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 “特定的”=关键字 例如查字典 讨论3：有哪些查找方法？ 查找方法取决于表中数据的排列方式; 针对静态查找表和动态查找表的查找方法也有所不同。

讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。 Average Search Length 统计意义上的数学期望值 其中： n是文件记录个数； pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; ci是找到第i个记录时所经历的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。

一、顺序查找（ Linear search，又称线性查找 ） 假定记录按逻辑次序顺序存储在一个连续存储区中，n个记录用数组R[1..N] 表示，用C语言说明如下： #define N 100 //数组长度常量 typedef int keytype; //关键字类型定义 typedef struct{ keytype key; //关键字数据项 othertype otherdata; //其他数据项 } Element; //数据元素类型定义 typedef Element Sqlist[N+1]; //数组定义 顺序查找：用逐一比较的办法顺序查找关键字，这显然是最直接的办法。

int Seq_Search (Sqlist R , KeyType k ){ int i; R[0].key =k; 算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“监视哨”），这样可以加快执行速度。 例： 若将待查找的特定值key存入顺序表的首部（如0号单元），并从后向前逐个比较，就不必担心“查不到”。 int Seq_Search (Sqlist R , KeyType k ){ int i; R[0].key =k; for( i=n; ST.elem[i].key!=k; i - - ); return i; } // Search_Seq //在顺序表R中，查找关键字与k相同的元素；若成功，返回其位置信息，否则返回0 //设立监视哨，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。 监视哨在顺序表的首部，所以扫描的方向必须是从后向前。 //找不到=不成功，返回值必为i=0； //找得到=成功，返回值i正好代表所找元素的位置。

讨论1：查找失败怎么办？ 返回特殊标志，例如返回空记录或空指针。前例中设立了“监视哨”，就是将关键字送入ST.elem[0].key使之结束，并返回 i=0。 讨论2：查找效率怎样计算？ 用平均查找长度ASL衡量。 讨论3：如何计算ASL？ 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； …… 查找第n个元素所需的比较次数为n； 未考虑查找不成功的情况：查找监视哨所需的比较次数为n+1 总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即：ASL＝(1＋n) / 2 ，时间效率为 O(n) 这是查找成功的情况

二、折半查找（又称二分查找或对分查找） 讨论4：顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL 太大，时间效率太低。 如何改进？ 二、折半查找（又称二分查找或对分查找） 这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 对顺序表结构如何编程实现折半查找算法？ ——见下页之例，或见教材（P113） 对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能从头指针head开始 对非线性(树)结构如何折半查找？ ——可借助二叉排序树来查找（P116，自学内容）。

已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。 折半查找举例： 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。 Low指向待查元素所在区间的下界 mid指向待查元素所在区间的中间位置 high指向待查元素所在区间的上界 解：① 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 ② 运算步骤： (1) low =1,high =11 ,故mid =6 ，待查范围是 [1,11]； (2) 若 R[mid].key < key，说明 key[ mid+1,high] ， 则令：low = mid + 1;重算 mid＝ (low+high)/2；. (3) 若 R[mid].key > key，说明key[low ,mid-1]， 则令：high = mid -1;重算 mid ； (4)若 R[mid].key = key，说明查找成功，元素序号=mid; ③ 结束条件：（1）查找成功 ： R[mid].key = key （2）查找不成功 ： high≤low （意即区间长度小于0）

讨论1：若关键字不在表中，怎样得知并及时停止查找？ ——典型标志是：当查找范围的上界≤下界时停止查找。 讨论2：如何计算二分查找的时间效率（ASL）？ 设元素个数为n＝ 2m个，则： 经1次比较就查找成功的元素有1个（20），即中间值； 经2次比较就查找成功的元素有2个（21），即1/4处和3/4处； 3次比较就查找成功的元素有4个（22），即1/8，3/8， 5/8，7/8处 4次比较就查找成功的元素有8个（23），即1/16处，3/16处…… …… 则第m次比较时查找成功的元素应该有（2m-1）个。 推导过程

2.6 排序 1. 什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。 2. 排序的目的是什么？ ——便于查找！ 存放在数据表中 按关键字排序 2. 排序的目的是什么？ ——便于查找！ 3.排序算法的好坏如何衡量？ 时间效率 ——排序速度（即排序所花费的全部比较次数） 空间效率 ——占内存辅助空间的大小 稳定性 ——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

4. 什么叫内部排序？什么叫外部排序？ 5. 内部排序的算法有哪些？ —— 若待排序记录都在内存中，称为内部排序； —— 若待排序记录一部分在内存，一部分在外存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。 5. 内部排序的算法有哪些？ ——按排序的规则不同，可分为5类： 冒泡排序 插入排序 选择排序 快速排序 归并排序

1. 冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构 例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。 初态： 第1趟 第2趟 第3趟 第4趟 第5趟 21，25，49， 25*，16， 08 21，25，25*，16， 08 ， 49 21，25， 16， 08 ，25*，49 21，16， 08 ，25， 25*，49 16，08 ，21， 25， 25*，49 08，16， 21， 25， 25*，49

冒泡排序的算法分析 最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。 最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1 i n) 做了n- i 次关键码比较，执行了n-i 次对象交换。此时的比较总次数KCN和记录移动次数RMN为： 因此： 时间效率：O(n2) ——因为要考虑最坏情况 空间效率：O(1) ——只在交换时用到一个缓冲单元 稳 定 性： 稳定——25和25*在排序前后的次序未改变

2. 插入排序 插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 插入排序有多种具体实现算法： 1) 直接插入排序 2) 折半插入排序

最简单的排序法！ 1) 直接插入排序 新元素插入到哪里？ 在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。 例1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。 【13】, 6, 3, 31, 9, 27, 5, 11 【6, 13】, 3, 31, 9, 27, 5, 11 【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13, 31】, 9, 27, 5, 11 【3, 6, 9, 13, 31】, 27, 5, 11 【3, 6, 9, 13, 27, 31】, 5, 11 【3, 5, 6, 9, 13, 27, 31】, 11 【3, 5, 6, 9, 11, 13, 27, 31 】

直接插入排序算法的实现： void InsertSort ( SqList &L ) { //对顺序表L作直接插入排序 for ( i = 2; i <=L.length; ++ i ) //直接在原始无序表L中排序 if (L.r[i].key < L.r[i-1].key) //若L.r[i]较小则插入有序子表内 { L.r[0]= L.r[i]; //先将待插入的元素放入“哨兵”位置 L.r[i]= L.r[i-1]; //子表元素开始后移 for ( j=i-2; L.r[0].key < L.r[j].key; --j ) L.r[j+1]= L.r[j]; //只要子表元素比哨兵大就不断后移 L.r[j+1]= L.r[0]; //直到子表元素小于哨兵，将哨兵值送入 //当前要插入的位置（包括插入到表首） } //if }// InsertSort

完成! 例1：关键字序列T= （21，25，49，25*，16，08）， 请写出直接插入排序的具体实现过程。 解：假设该序列已存入一维数组r[7]中，将r[0]作为哨兵（Temp）。则程序执行过程为： 25* 25* 49 21 25 49 25* 16 08 0 1 2 3 4 5 6 哨 兵 21 25 49 25* 49 49 49 25* 08 16 初态： 08 25 25 25* 16 21 16 21 16 08 完成! i=1 i=2 i=3 i=4 i=5 i=6 时间效率：因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n2)。其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n2) 空间效率：仅占用1个缓冲单元——O(1) 算法的稳定性：因为25*排序后仍然在25的后面——稳定

2） 折半插入排序 一个想得到的改进方法： 既然子表有序且为顺序存储结构，则插入时采用折半查找定可加速。 优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。 时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。 空间效率：仍为 O(1) 稳定性： 稳定

思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。 3. 选择排序 选择排序的基本思想是：每一趟在后面n-i个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。 思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。 ——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。 优点：实现简单 缺点：每趟只能确定一个元素，表长为n时需要n-1趟 前提：顺序存储结构

例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。 最小值 08 与r[1]交换位置 原始序列： 21，25，49，25*，16，08 第1趟 第2趟 第3趟 第4趟 第5趟 08，25，49，25*，16，21 08，16, 49，25*，25，21 08，16, 21，25*，25，49 时间效率：O(n2) ——虽移动次数较少，但比较次数仍多。 空间效率：O(1) ——没有附加单元（仅用到1个中间变量）。 算法的稳定性：不稳定——因为排序时，25*到了25的前面。

各种内部排序方法的比较 (教材P131） 第2章结束 排序方法 最好情况 平均时间 最坏情况 辅助存储 稳定性 冒泡排序 O(n) 插入排序 选择排序 不稳定 快速排序 O(nlogn ) O(nlogn) O(logn) 归并排序 O(n） 第2章结束

作业： P133 习题16，17（前三种排序法） 与第1次的作业一起交