第十章 查我 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 二分查找: • 要求:查找表为有序表 • 查找过程:先确定待查找记录范围; 然后逐步缩小范围; 直到:查找成功或不成功