《严蔚敏数据结构课件第八章》由会员分享，可在线阅读，更多相关《严蔚敏数据结构课件第八章（170页珍藏版）》请在金锄头文库上搜索。
1、 何谓查找表 ？查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。仅作查询和检索操作的查找表。静态查找表有时在查询之后，还需要将“查询”结果 为“不在查找表中”的数据元素插入到查 找表中；或者，从查找表中删除其“查询 ”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:是数据元素（或记录）中某个数据项 的值，用以标识（识别）一
2、个数据元 素（或记录）。关键字若此关键字可以识别唯一的一个记 录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录 ） 查找若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。如何进行查找？查找的方法取决于查找表的
3、结构。9.1 静态查找表9.2 动态查找树表9.3 哈希表9.1 静 态 查 找 表数据对象D：数据关系R：D是具有相同特性的数 据元素的集合。每个数 据元素含有类型相同的 关键字，可唯一标识数 据元素。 数据元素同属一个集合。ADT StaticSearchTable Create(Destroy(Search(ST, key);Traverse(ST, Visit();基本操作 P：next ADT StaticSearchTable构造一个含 n 个数据元素的静态查找表ST。 Create(操作结果：销毁表ST。Destroy(初始条件：操作结果：静态查找表ST存在；若 ST 中存在其关
4、键字等于kval 的数据元素，则函数值为该元素的值或在表中的位 置，否则为“空”。 Search(ST, kval);初始条件：操作结果：静态查找表ST存在，kval 为和查找表中元素的关键字 类型相同的给定值；按某种次序对ST的每个元 素调用函数Visit()一次且仅 一次，一旦Visit()失败，则操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；假设静态查找表的顺序存储结构为typedef struct *elem;/ 数据元素存储空间基址，建表时/ 按实际长度分配，0号单元留空int length; / 表的长
5、度 SSTable;ElemType数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; , TElemType ;一、顺序查找表二、有序查找表三、静态查找树表四、索引顺序表以顺序表或线性链表表示静态查找表一、顺序查找表ST.elem回顾顺序表的查找过程：假设给定值 e = 64, 要求 ST.elemi = e, 问: i = ?ii66iiint location( SqList L, ElemTypep = L.elem;while ( i50 时，可得近似结果 关键字: A B C D EPi: 0.2 0.3
6、 0.05 0.3 0.15 Ci: 2 3 1 2 3三、静态查找树表在不等概率查找的情况下，折半查找不是有序表最好的查找方法 例如:此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变Ci的值 2 1 3 2 3则 ASL=20.2+10.3+30.05+20.3+30.15=1.9使 达最小的判定树称为最优二叉树，其中: 定义:为计算方便，令 wi = pi，选择二叉树的根结点，使 达到最小 介绍一种次优二叉树的构造方法:为便于计算，引入累计权值并设 wl-1 = 0 和 swl-1 = 0，则推导可得023811 15 18 23例如:lh21 18 124
7、310 18h9608EC21 Ah53lhG3 0 13ECGABDF所得次优二叉树如下所示:查找比较“总次数”= 32+41+25+33+14+33+25 = 52查找比较“总次数”= 32+21+35+13+34+23+35 = 59和折半查找相比较DBACFEGStatus SecondOptimal(BiTree T-data = Ri; / 生成结点构造次优二叉树的算法if (i=low) T-lchild = NULL; / 左子树空 else SecondOptimal(T-lchild, R, sw, low, i-1); / 构造左子树if (i=high) T-rchil
8、d = NULL; / 右子树空else SecondOptimal(T-rchild, R, sw, i+1, high); / 构造右子树return OK; / SecondOptimal次优查找树采用二叉链表的存储结构Status CreateSOSTre(SOSTree else FindSW(sw, ST);/ 按照有序表 ST 中各数据元素/ 的 weight 值求累计权值表SecondOpiamal(T, ST.elem, sw, 1, ST.length);return OK; / CreatSOSTree四、索引顺序表在建立顺序表的同时，建立一个索引。01234567891
9、0 11 12 13 17 08 21 19 14 31 33 22 25 40 52 61 78 4621 040 578 10例如 ：索引顺序表 = 索引 + 顺序表顺序表索引typedef struct KeyType maxkey;int stadr; indexItem; / 索引项typedef struct indexItem *elem;int stadr; indexTable; / 索引表索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。可见，索引顺序查找的过程也是一个 “缩小区间”的查找过程。顺序表有序表表的特性无序有序存储结构顺序 或
10、链式顺序插删操作易于进行需移动元素ASL的值大小对比顺序表和有序表的查找性能 ：索引顺序查找的平均查找长度 =查找“索引”的平均查找长度+ 查找“顺序表”的平均查找长度注意：索引可以根据查找表的特点来构造。ADT DynamicSearchTable 抽象数据类型动态查找表的定义如下：数据对象D：数据关系R： 数据元素同属一个集合。D是具有相同特性的数据元素的集合。 每个数据元素含有类型相 同的关键字， 可唯一标识 数据元素。InitDSTable(InsertDSTable(DeleteDSTable(TraverseDSTable(DT, Visit();nextADT DynamicSe
11、archTable操作结果：构造一个空的动态查找表DT。InitDSTable(销毁动态查找表DT。DestroyDSTable(初始条件：操作结果：动态查找表DT存在；若 DT 中存在其关键字等于 kval的数据元素，则函数值为该元素的值或在表中的位 置，否则为“空”。SearchDSTable(DT, kval);初始条件：操作结果：动态查找表 DT 存在，kval为和关键字类型相同的给定值；动态查找表 DT 存在，e 为待插入的数据元素；InsertDSTable(初始条件：操作结果：若 DT 中不存在其关键字等于 e.key 的 数据元素， 则插入 e 到 DT。动态查找表DT存在，k
12、val为和关键字类型相同的给 定值；DeleteDSTable(初始条件：操作结果：若DT中存在其关键字等 于kval的数据元素，则删除之。动态查找表DT存在，Visit是对结点操作的应用函数；TraverseDSTable(DT, Visit();初始条件：操作结果：按某种次序对DT的每个结 点调用函数 Visit() 一次且至 多一次。一旦 Visit() 失败，则操作失败。9.2 动 态 查 找 树 表(n)(1)(n)(1)(nlogn)综合上一节讨论的几种查找表的特性：查找 插入 删除无序顺序表 无序线性链表有序顺序表 有序线性链表 静态查找树表(n)(n)(logn)(n)(log
13、n)(1)(1)(n)(1)(nlogn)1）从查找性能看，最好情况能达(logn)，此时要求表有序；2）从插入和删除的性能看，最好情况能达(1)，此时要求存储结构是链表。可得如下结论：一、二叉排序树（二叉查找树）二、二叉平衡树三、B - 树四、B+树五、键 树一、二叉排序树 （二叉查找树）1定义2查找算法3插入算法4删除算法5查找性能的分析（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；503080209010
14、854035252388例如:是二叉排序树。66不通常，取二叉链表作为 二叉排序树的存储结构typedef struct BiTNode / 结点结构struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;TElemType data;2二叉排序树的查找算法： 1）若给定值等于根结点的关键字， 则查找成功； 2）若给定值小于根结点的关键字， 则继续在左子树上进行查找； 3）若给定值大于根结点的关键字， 则继续在右子树上进行查找。否则若二叉排序树为空，则查找不成功；50 3080 20908540358832例如:二叉排序树查找关键字
15、= 50 ,505035 ,50 30 40355090 ,50 80 9095 ,从上述查找过程可见，在查找过程中，生成了一条查找路径:从根结点出发，沿着左分支或右分支 逐层向下直至关键字等于给定值的结点;或者从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。查找成功查找不成功算法描述如下：Status SearchBST (BiTree T, KeyType kval, BiTree f, BiTree / SearchBST 否则表明查找不成功，返回/ 指针 p 指向查找路径上访问的最后一个结点，/ 并返回函数值为FALSE, 指针 f 指向当前访问/ 的结点的双亲，其初始调用值为NULLif (!T)else if ( EQ(kval, T-data.key) )else if ( LT(kval, T-data.key) )el
