《《数据结构-查找》PPT课件》由会员分享，可在线阅读，更多相关《《数据结构-查找》PPT课件（98页珍藏版）》请在金锄头文库上搜索。
1、数据结构-查找齐 恒大黑楼 B0912何谓查找表何谓查找表 ？ 查找表是由同一类型同一类型的数据元素(或记录)构成的集合集合，可从中查找某个含有特定关键字的数据元素。 由于“集合集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的对查找表经常进行的查找操作查找操作:1）查查询询某个“特特定定的的”数据元素是否在查找表中；2）检检索索某个“特特定定的的”数据元素的各种属性；3）在查找表中插入插入一个数据元素；4）从查找表中删去删去某个数据元素。仅作查询和检索操作的查找表。静态查找表静态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中不在查找表中”的
2、数据元素插入插入到到查找表中；或者，从查找表中删除删除其“查询”结果为“在查找表中在查找表中”的数据元素。动态查找表动态查找表查找表可分为两类查找表可分为两类:它是数据元素（或记录）中某个数据数据项项的值，用以标识标识（识别）一个数据元素（或记录）。查找一般都基于查找一般都基于关键字关键字. 若此关键字可以识别唯一的唯一的一个记录，则称之谓“主关键字主关键字”。 若此关键字能识别若干个若干个记录，则称之为“次关键字次关键字”。 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（记录）。 查找：查找： 若查找表中存在这样一个记录，则称“查找成功查找成功”。查找结果给出整个记录的信
3、给出整个记录的信息，或指示该记录在查找表中的位置息，或指示该记录在查找表中的位置； 否则称“查找不成功查找不成功”。查找结果给出给出“空记录空记录”或或“空指针空指针”。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，即：用便于查找的结构来用便于查找的结构来构造查找表构造查找表。如何进行查找？如何进行查找？查找的方法取决于查找的方法取决于查找表的结构查找表的结构。9.1 静态查找表静态查找表9.2 动态查找表动态查找表9.3 哈希表哈希表9.1 静静 态态 查查 找找 表表数据对象数据对象D：数据关系
4、数据关系R：D是具有相同特性的数据元素的集合。每个数每个数据元素含有类型相同的据元素含有类型相同的关键字关键字，可唯一标识该数据元素。 数据元素同属一个集合。ADT StaticSearchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P： ADT StaticSearchTable构造一个含n个数据元素的静态查找表ST。 Create(&ST, n);操作结果：销毁表ST。Destroy(&ST);初始条件：操作结果：静态查找表ST存在；若 ST 中存在其关键字等于 key 的数
5、据元素，则函数值为该元素的值或在表中的位位置置，否则为“空”。 Search(ST, key);初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；typedef struct / 数据元素存储空间基址基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;假设静态查找表静态查找表的顺序存储结构顺序存
6、储结构为ElemType *elem;数据元素类型的定义为数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; , TElemType ;一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、静态最优查找树三、静态最优查找树四、索引顺序表四、索引顺序表查查 找找 方方 式式 以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找表回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值 e=64,要求 ST.elemk = e, 问: k = ?kkint location( SqList L, ElemType&
7、 e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem+1; while ( & !(*compare)(*p+,e) k+; if ( k= L.length) return k; else return 0; /locationii60ikey=64key=60i64一点改进：设置监视哨，从后往前查找。一点改进：设置监视哨，从后往前查找。int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为
8、0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前查找 return i; / 找不到时，i为0 / Search_Seq 定义：定义： 查找算法的平均查找长度平均查找长度 (ASL - Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值进行比较的关键字个数的期望值 其中: n 为表长，Pi 为表中第i个记录的查找概率， 且 ， Ci为找到该记录时，曾和给定和给定值比较过的关键字的个数值比较过的关键字的个数。分析顺序查找的时间
9、性能在等概率等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表顺序表而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn在每次查找都成功的情况下：在每次查找都成功的情况下： 若查找概率无法事先测定，则查找过程采取的改进办法是：v 查找频率大的记录不断后移查找频率大的记录不断后移v 在每次查找之后，将刚刚查找到的记在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。录直接移至表尾的位置上。在概率查找不等的情况下，ASLss 在 PnPn-1P2P1时取极小值2. 在查找成功与不成功概率相同查找成功与不成功概率相同且等概等概率率查找的情况下，顺序表查找的
10、平均顺序表查找的平均查找长度查找长度为：考虑查找可能不成功的情况：考虑查找可能不成功的情况：1.实际应用中，查找不成功的可能性比查找成功的可能性小得多，特别是记录较多的情形下。 上述顺序查找表的查找算法简单且适应面广，但平均查找长度较大平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。例如例如: key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid = (low+high)/2int Search_Bin (
11、SSTable ST, KeyType key ) low = 1; ; / 置区间初值 while (low = high) mid = (low + high) / 2; /（向下）取整向下）取整 if （EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( key 50时，可得近似结果 一般情况下，表长为一般情况下，表长为 n 的查找表对的查找表对应的折半查找判定树的深度和含有应的折半查找判定树的深度和含有 n 个个结点的完全二叉树的深度相同。结点的完全二叉树的深度相同。关键字: A B C D E Pi: Ci: 2 3
12、1 2 3三、静态最优查找树三、静态最优查找树 在不等概率查找不等概率查找的情况下，折半查找的情况下，折半查找不是有序表最好的查找方法不是有序表最好的查找方法。例如例如:此时 ASL=20.2+30.3+10.05+20.3+30.15=若改变Ci的值 2 1 3 2 3则 ASL=20.2+10.3+30.05+20.3+30.15= 在不等概率查找不等概率查找的情况下，折半查找的情况下，折半查找性能未必是最优的，如何构建一颗查找性能未必是最优的，如何构建一颗查找性能最佳的二叉树性能最佳的二叉树。 如果只考虑查找成功的情况，查找性能最佳的判定树是其带权路径长度之和取最小值的二叉树。ASL值最
13、小的二叉树为静态最优查找树三、静态最优查找树三、静态最优查找树结构：索引表结构：索引表(块块)+顺序表顺序表(块内块内)索引表：按块最大关键字有序 =顺序/折半查找顺序表：记录任意排列 =顺序查找四、索引顺序表四、索引顺序表: 分块存储查找分块存储查找索引顺序表的查找过程索引顺序表的查找过程1）由索引确定记录所在区间（块）；2）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。可见， 索引顺序查找索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程。索引顺序查找的平均查找长度索引顺序查找的平均查找长度 = 查找查找“索引索引”的平均查找长度的平均查找长度 + 查找查找“顺
14、序表顺序表”的平均查找长度的平均查找长度9.2 动动 态态 查查 找找 表表ADT DynamicSearchTable 抽象数据类型抽象数据类型动态查找表动态查找表的定义如下：的定义如下：数据对象数据对象D：数据关系数据关系R： 数据元素同属一个集合。D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字， 可唯一标识数据元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable
15、(DT, Visit();ADT DynamicSearchTable操作结果：操作结果：构造一个空的动态查找表DT。InitDSTable(&DT);销毁动态查找表DT。DestroyDSTable(&DT);初始条件： 操作结果：动态查找表DT存在；若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。SearchDSTable(DT, key);初始条件：操作结果：动态查找表DT存在，key为与关键字类型相同的给定值；动态查找表DT存在， e 为待插入的数据元素；InsertDSTable(&DT, e);初始条件：操作结果：若DT中不存在其关键字
16、等于 e.key 的 数据元素，则插入 e 到DT。动态查找表DT存在，key为和关键字类型相同的给定值；DeleteDSTable(&T, key);初始条件：操作结果：若DT中存在其关键字等于key的数据元素，则删除之。动态查找表DT存在，Visit是对结点操作的应用函数；TraverseDSTable(DT, Visit();初始条件：操作结果：按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。(n) (1)(n) (1)(nlogn)综合上一节讨论的几种查找表的特性：综合上一节讨论的几种查找表的特性：查找 插入 删除无序顺序表 无序线性链表有序顺序表 有序线性链表 静态查找树表(n)(n) (logn)(n) (logn)(1) (1)(n) (1)(nlogn)1）从查找性能看，最好情况能达 (logn)，此时要求表有序有序；2）插入和删除涉及记录移动，从性能看，最好情况能达 (1)，此时要求存储结构是链表链表。可得如下结论：可得如下结论：一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、二叉平衡树二、二叉平
