《第九章 查找(1)教程文件》由会员分享，可在线阅读，更多相关《第九章 查找(1)教程文件（26页珍藏版）》请在金锄头文库上搜索。
1、第九章 查找(1),主要内容,1、查找的基本概念 2、静态查找表 3、动态查找表 4、哈希表,1、查找的基本概念,一、查找表：由同一类型的数据元素(或记录)构成的集合。集合是一种数据元素之间关系松散的数据结构，应用非常灵活。 二、查找:按给定的某个值 K、在查找表中查找关键字为给定值K的数据元素（记录）的过程。 对查找表经常进行的操作: 查询某个“特定”数据元素是否在查找表中； 检索某个“特定”数据元素的各种属性； 在查找表中插入一个数据元素； 从查找表中删去某个数据元素。,三、静态查找表和动态查找表 根据对查找表的操作不同，查找表又分两类。 静态查找表：只能进行查找而不能插入和删除的查找表；
2、 动态查找表：可以进行查找、插入和删除的查找表。 四、关键字 是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。,六、如何进行查找？ 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。,2、静态查找表,2.1 顺序查找表 2.2 有序查找表 2.3 索引顺序表,静态查找表的ADT定义 ADT Static
3、SearchTable ,数据对象D：,数据关系R：,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,数据元素同属一个集合。,基本操作 P：,Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();, ADT StaticSearchTable,函数说明 Create( 初始条件：查找表ST存在，Visit是对元素操作的应用函数； 操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。,2.1 顺序查找表,设静态查找表的顺序存储结构为： Type
4、def struct ElemType * elem ; / 数据元素存储空间基址，建表时按 / 实际长度分配，0号单元留空 int length; / 表的长度 SSTable; 数据元素类型的定义为: typedef struct keyType key; / 关键字域 / 其它属性域 ElemType , TElemType ;,存储结构: 用顺序表或线性链表表示静态查找表。 回顾顺序表的查找过程分析：,ST.elem,假设给定值 e=64,要求 ST.elemk = e, 问: k = ?,k,k,int location( SqList L, ElemType /location,查
5、找过程,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq,分析顺序查找的时间性能,定义： 查找算法的平均查找长度 (Average Searc
6、h Length)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 Ci为找到该记录时，曾和给定值比较过的关键字的个数。,在等概率查找的情况下，顺序表查找的平均查找长度为：,对顺序表而言， Ci = n-i+1 ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。,在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值,2.2 有序查找表,上述顺序查找表的查找算法简单， 但平均查找长
7、度较大，特别不适用于表长较大的查找表。,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,ST.elem,ST.length,例如: key=64 的查找过程如下：,low,high,mid,low,mid,high,mid,low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2,int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if （EQ (key ,
8、 ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin,先看一个具体的情况，假设：n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,具有n个结点的折半查找判定树的深度为,查找成功：在表中查找任一记录的过程，即是
9、折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。,查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键字的比较次数等于该路径上内部结点的个数。,假设 n=2h-1 并且查找概率相等，则 在n50时，可得近似结果,一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。,2.3 索引顺序表,索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,注意：索引可以根据查找表的特点来构造。,可见， 索引顺序查找的过程也是一个“缩小区间”的查找过程。,索引顺序查找的
10、平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度,P225,本章小结,本章中介绍下列主要内容： 1、静态查找表查找算法（顺序、折半查找） 2、动态查找表及查找算法（二叉排序树） 3、哈希表及查找算法 本章的重点与难点 1、静态查找的折半查找 2、二叉排序树查找、插入、删除算法 3、哈希表构造及查找算法,作业：,（一）纸或本 （11月19日交） 1、填空题： （1）设有100个结点，用二分法查找时，最大比较次数是（ ）次。 （2）折半查找有序线性表（4, 6, 12, 20, 28, 38, 50, 70, 88, 100），若查找表中元素20，它将依次与表中元素（ ）比较大小。 2、简答题：折半查找算法的查找速度必定比顺序查找算法的查找速度快，这种说法对吗？为什么？ （二）实验 顺序查找表、折半查找表,
