第10章排序 10.1查找的基本概念 10.2静态查找表 10.3动态查找表 10.4哈希表
1 10.1 查找的基本概念 10.2 静态查找表 10.3 动态查找表 10.4 哈希表 第10章 排序
10.1查找的基本概念 是一种数据结构 查找表由同一类型的数据元素(或记录)构成的集合。 查找 查询特定元素是否在(数据元素集合)表中的过程。 查找成功若表中存在特定元素,称查找成功,应输出该记录; 查找不成功—否则,称查找不成功(也应输出失败标志或失败位置 静态查找—只查找,不改变数据元素集合内的数据元素。 动态查找—既查找,又改变(增减)集合内的数据元素 关键字 记录中某个数据项的值,可用来识别一个记录 (预先确定的记录的某种标志 主关键字 可以唯一标识一个记录的关键字—刚如“学号 次关键字识别若干记录的关键字一例如“女
2 10.1 查找的基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询特定元素是否在(数据元素集合）表中的过程。 ——只查找，不改变数据元素集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志) ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” 是一种数据结构 ——识别若干记录的关键字
讨论: 查找的过程是怎样的? 给定一个值K,在含有η个记录的文件中进行搜索,寻找 一个关键字值等于K的记录,如找到则输出该记录,否则输 出查找不成功的信息。 对查找表常用的操作有哪些? 特定的”=关键 查询某个“特定的”数据元素是否在表中 查询某个“特定的”数据元素的各种属性; 在查找表中插入一元素 从查找表中删除一元素 有哪些查找方法? 例如查字典 查找方法取决于表中数据的排列方式; 针对静态查找表和动态查找表的查找方法也有所不同
3 讨论2：对查找表常用的操作有哪些？ ❖ 查询某个“特定的”数据元素是否在表中； ❖ 查询某个“特定的”数据元素的各种属性； ❖ 在查找表中插入一元素； ❖ 从查找表中删除一元素。 讨论3：有哪些查找方法？ 查找方法取决于表中数据的排列方式; 讨论： 讨论1：查找的过程是怎样的？ 给定一个值K，在含有n个记录的文件中进行搜索，寻找 一个关键字值等于K的记录，如找到则输出该记录，否则输 出查找不成功的信息。 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。 “特定的”=关键 字
如何评估查找方法的优劣? 明确:查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度AS Average Search L eno 其中: 统计意义上的 n是文件记录个数; 数学期望值 P是查找第个记录的查找概率(通常取等概率即P;=1/n); c是找到第个记录时所经历的比较次数。 物理意义:假设每一元素被查找的概率相同,则查找每一 元素所需的比较次数之总和再取平均,即为 显然,ASL值越小,时间效率越高
4 讨论4：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 = = n i ASL Pi Ci 1 其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 统计意义上的 数学期望值 物理意义：假设每一元素被查找的概率相同，则查找每一 元素所需的比较次数之总和再取平均，即为 ASL。 显然，ASL值越小，时间效率越高。 Average Search Length
10.2静态查找表 静态查找表主要有三种结构: 顺序表 有序顺序表 索引顺序表 针对静态查找表的查找算法主要有: 顺序查找(线性查找) 折半查找(二分查找) 分块查找(索引顺序查找)
5 针对静态查找表的查找算法主要有： 10.2 静态查找表 顺序查找（线性查找） 折半查找（二分查找） 分块查找（索引顺序查找） 静态查找表主要有三种结构： 顺序表 有序顺序表 索引顺序表
、顺序表 在顺序表上的顺序查找(又称线性查找)的基本思想 从顺序表的一端开始,用给定数据元素的关键字逐个与顺序 表中各数据元素的关键字比较,若在顺序表中查找到要查找 的数据元素,则查找成功,函数返回该数据元素在顺序表中 的位置;否则查找失败,函数返回-1。 (1)顺序表的机内存储结构 typedef struct i DateType list[Max] nt size seqlist
6 一、顺序表 （1）顺序表的机内存储结构 在顺序表上的顺序查找（又称线性查找 ）的基本思想： 从顺序表的一端开始，用给定数据元素的关键字逐个与顺序 表中各数据元素的关键字比较，若在顺序表中查找到要查找 的数据元素，则查找成功，函数返回该数据元素在顺序表中 的位置；否则查找失败，函数返回-1。 typedef struct { DateType list[MaxSize]; int size; }SeqList;
(2)算法的实现 int SeqSearch(SeqList S, DataType x) i int i=0 while(i<s size &&S list[i]. key! =x key) 1++t if(S. listli] key == x. key) return i else return -1
7 （2）算法的实现 int SeqSearch(SeqList S, DataType x) { int i = 0; while(i<S.size && S.list[i].key!=x.key) i++; if(S.list[i].key == x.key) return i; else return -1; }
(3)顺序查找算法性能评价 分析: 查找第1个元素所需的比较次数为1; 查找第2个元素所需的比较次数为2; 查找第n个元素所需的比较次数为n; 总计全部比较次数为:1+2+.+n=(1+n)m/2 若求某一个元素的平均查找次数,还应当除以n(等概率), 即:ASL 成功 (1+n)12,时间效率为O( 这是查找成功的情况 同理:ASL失败=(1+n)/2 (4)顺序查找的特点 优点:算法简单,且对顺序结构或链表结构均适用 缺点:ASL太大,时间效率太低
8 （3）顺序查找算法性能评价 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； …… 查找第n个元素所需的比较次数为n； 总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 这是查找成功的情况 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL成功＝（1＋n）/2 ，时间效率为O(n) 同理：ASL失败＝（1＋n）/2 （4）顺序查找的特点 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL 太大，时间效率太低
思考题: 1、问:对顺序结构如何线性查找? 答:利用顺序表 2、问:对单链表结构如何线性查找? 答:从头指针始“顺藤摸瓜” 3、问:对非线性(树结构)如何顺序查找? 答:借助各种二叉树遍历操作!
9 思考题： 1、问：对顺序结构如何线性查找？ 答：利用顺序表 2、问：对单链表结构如何线性查找？ 答：从头指针始 “顺藤摸瓜” 3、问：对非线性（树结构）如何顺序查找? 答：借助各种二叉树遍历操作！
有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法 1、顺序查找 有序顺序表上顺序查找算法类同顺序表上的顺序查找算法 2、二分查找(又称折半查找) (1)算法的基本思想:先给数据排序(例如按升序排好),形成 有序表,然后再将key与正中元素相比,着key小,则缩小至 前半部内查找;再取其中值比较,每次缩小1/2的范围,直到 查找成功或失败为止。(详细见教材P263) 思考题: 问:能否使用单链表结构进行折半査查找? 无法实现!因全部元素的定位只能从头指针head开 始 问:对非线性(树)结构如何进行折半查找? 可借助二叉排序树来查找(属动态查找表形式)
10 (1)算法的基本思想：先给数据排序（例如按升序排好），形成 有序表，然后再将key与正中元素相比，若key小，则缩小至 前半部内查找；再取其中值比较，每次缩小1/2的范围，直到 查找成功或失败为止。（详细见教材P263) 思考题： 问：能否使用单链表结构进行折半查找？ ——无法实现！因全部元素的定位只能从头指针head开 始 问：对非线性(树)结构如何进行折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。 二、有序顺序表 有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。 1、顺序查找 有序顺序表上顺序查找算法类同顺序表上的顺序查找算法。 2、二分查找（又称折半查找）