《数据结构》课程教学资源：第十章 查找

第十章 查我 10.1查找的基本撬念 102戌性表的查找 10.3树表的查找 104哈希表查找

1 10.1 查找的基本概念 10.2 线性表的查找 10.3 树表的查找 10.4 哈希表查找 第十章 查找

10.1查找的基本概念 查龙:也叫检索,是根据给定的某个值,在表 中确定一个关键字等于给定值的记录或数据元 素的过程。 ●查结果 >查找成功tabe中存在给定值的记录,返回 该记录的信息或该记录在表中的位置 >查不成tabe中不存在给定值的记录 返回相关的指示信息。 2

2 ⚫ 查找：也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元 素的过程。 ⚫ 查找结果： ➢ 查找成功(table中存在给定值的记录，返回 该记录的信息或该记录在表中的位置） ➢ 查找不成功(table中不存在给定值的记录， 返回相关的指示信息。 10.1 查找的基本概念

10.1查找的基本概念 就表 search table:是由同一类型的数据元素 (或记录)构成的集合,集合中的数据元素之间 的关系是完全松散的 查找表的主要缲作: 查询某个“特定的”数据元素是否在表中 检索某个“特定的”数据元素的各种属性 >在查找表中插入一个数据元素 >从查找表中删去某个数据元素 查找表分为: >静态查花表对表中的DE不进行插入和删除) 3 >动态查龙表对表中的DE可进行插入和删除);

3 ⚫ 查找表(search table):是由同一类型的数据元素 （或记录）构成的集合，集合中的数据元素之间 的关系是完全松散的。 ⚫ 查找表的主要操作： ➢查询某个“特定的”数据元素是否在表中； ➢检索某个“特定的”数据元素的各种属性； ➢在查找表中插入一个数据元素； ➢从查找表中删去某个数据元素。 ⚫ 查找表分为： ➢静态查找表(对表中的DE不进行插入和删除)； ➢动态查找表(对表中的DE可进行插入和删除)； 10.1 查找的基本概念

10.1查找的基本概念 平均查线长度 average search length):查找过程中, 对关键字进行比较的平均次数即比较次数的期望值。 ASL=∑Pc i=1 其中:n是结点个数,p是查找第个结点的概率 C是查找第个结点所需的比较次数 4

4 ⚫ 平均查找长度(average search length):查找过程中, 对关键字进行比较的平均次数即比较次数的期望值。 = = n i ASL pi ci 1 其中：n是结点个数，pi是查找第i个结点的概率 Ci是查找第i个结点所需的比较次数 10.1 查找的基本概念

102线性表的查找 线性表是表的组织方式中最简单的一种,在其上 我们主要介绍顺序查线二分查找和分块查 版序查找( Sequential search):从表的一端开 始,顺序扫描线性表,依次将扫描到的结点关键字和 给定值进行比较,若当前扫描到的结点值与给定值相 等,则查找成功;反之,若扫描到最后,仍未找到关 键宇等于k的结点,则查找失败。适用于顺序存储结 构和链表存储结构

5 10.2 线性表的查找 线性表是表的组织方式中最简单的一种，在其上 我们主要介绍顺序查找、二分查找和分块查找。 一、顺序查找（Sequential Search)：从表的一端开 始，顺序扫描线性表，依次将扫描到的结点关键字和 给定值进行比较，若当前扫描到的结点值与给定值相 等，则查找成功；反之，若扫描到最后，仍未找到关 键字等于k的结点，则查找失败。适用于顺序存储结 构和链表存储结构

版序查找算法 int SeqSearch ( seqlist r, int n, Key Type k) i int i=0; while(i=n) return -1 比较次数=7*2 else 返回结果:i=6 return 找64 例 05 1234567891011 13192137566475808892

顺序查找算法： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while (i=n) return -1; else return i; } i 例 0 1 2 3 4 5 6 7 8 9 10 11 找64 i i i i 比较次数=7*2 返回结果：i=6 5 13 19 21 37 56 64 75 80 88 92 i i

●改进的版序查找算法: int SeqSearch(seq list r, int n, Key Type k) i int i=0 RIn]key=k;/哨兵免去监测查找完毕的操作 whil(R[lkey!=k)i+;从前往后找 if(i==n return-1 else return i: 比较次数=7 返回结果:i=6 找64 例 01234567891011 51319213756647580889264 监视哨

⚫ 改进的顺序查找算法： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; R[n].key=k; //哨兵,免去监测查找完毕的操作 while( R[i].key!=k) i++; //从前往后找 if(i= =n) return -1; else return i; } i 例 0 1 2 3 4 5 6 7 8 9 10 11 找64 64 监视哨 i i i i 比较次数=7 返回结果：i=6 5 13 19 21 37 56 64 75 80 88 92 i i

平均查长度ASL 对于含有n个纪录的表,查找功时的平均查找长度为: ASL 芝 其中:为查找表中第i个纪录的概率,等概率时P2=1/n C为找到第个记录时,已比较的次数。 ke y ASL (i+1)=(n+1)/2 n i=0

i+1 对于含有n个纪录的表，查找成功时的平均查找长度为：  − = = 1 0 n i ASL Pi Ci 其中: Pi 为查找表中第i个纪录的概率,等概率时 pi =1/ n Ci 为找到第i个记录时，已比较的次数。 key i ( 1) ( 1)/ 2 1 1 0 =  + = + − = i n n ASL n i 平均查找长度(ASL)

102线性表的查找 版序查物的优缺点: 优点:算法简单且适应面广,对表的结构无 任何要求,对线性链表同样适用。 缺点:平均查找长度较大,特别是当n很大时 查找效率较低

9 顺序查找的优缺点： 优点：算法简单且适应面广，对表的结构无 任何要求，对线性链表同样适用。 缺点：平均查找长度较大，特别是当n很大时， 查找效率较低。 10.2 线性表的查找

102线性表的查找 二.二分查线( Binary Search): 有表:查找表中记录按关键字有序排列的表。 即:r[ikey<=r[i计1keyi=1,2,,n-1 二分查线: 要求:查找表为有序表 查找过程:先确定待查找记录范围; 然后逐步缩小范围; 直到:查找成功或不成功。 10

10 10.2 线性表的查找 二、二分查找（Binary Search)： 有序表：查找表中记录按关键字有序排列的表。 即：r[i].key<=r[i+1].key i=1,2,…,n-1 二分查找： • 要求：查找表为有序表 • 查找过程：先确定待查找记录范围； 然后逐步缩小范围； 直到：查找成功或不成功