《数据结构课件第9章查找》由会员分享，可在线阅读，更多相关《数据结构课件第9章查找（163页珍藏版）》请在金锄头文库上搜索。
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： ADT StaticSearchTable构造一个含n个数据元素 的静态查找表ST。Create(操作结果：销毁表ST。Destroy(初始条件：操作结果：静态查找表ST存在；若 ST 中存在其关键
4、字等于key 的数据元素，则函数值为该元素的值或在表中的位 置，否则为“空”。 Search(ST, key);初始条件：操作结果：静态查找表ST存在，key 为 和查找表中元素的关键字类 型相同的给定值；按某种次序对ST的每个元 素调用函数Visit()一次且仅 一次，一旦Visit()失败，则操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；typedef struct / 数据元素存储空间基址，建表时/ 按实际长度分配，0号单元留空int length; / 表的长度 SSTable;假设静态查找表的顺序存储结构
5、为ElemType *elem;数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; , TElemType ;一、顺序查找表二、有序查找表三、静态查找树表四、索引顺序表以顺序表或线性链表表示静态查找表一、顺序查找表ST.elem回顾顺序表的查找过程：假设给定值 e=64, 要求 ST.elemk = e, 问: k = ?kkint location( SqList L, ElemTypep = L.elem;while ( k50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的
6、完全二叉树的深度相同。关键字: A B C D EPi: 0.2 0.3 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 =
7、 0，则推导可得023811 15 18 23例如:lh21 18 124310 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,
8、low, i-1); / 构造左子树if (i=high) T-rchild = 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; / CreatSOSTr
9、ee对比顺序表和有序表的查找性能之差别顺序查找表有序查找表表的特性无序表有序表存储结构顺序结构或 链式结构顺序结构插入删除操 作容易进行需要移动元 素 ASL大小四、 索引查找当数据对象个数 n 很大时, 如果 用无序表形式的静态查找结构存储 , 采用顺序查找, 则查找效率极低。 如果采用有序表存储形式的静态查 找结构, 则插入新记录进行排序, 时 间开销也很可观。这时可采用索引 方法来实现存储和查找。索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。可见，索引顺序查找的过程也是一个 “缩小区间”的查找过程。n示例：有一个
10、存放职工信息的数据表 , 每一 个职工对象有近 1k 字节的信 息, 正好占据一 个页块的存储空间。100140180220260300340380key addr03 18008 14017 34024 26047 30051 38083 10095 220职工号 姓名 性别 职务 婚否 83 张珊 女 教师 已婚 08 李斯 男 教师 已婚 . 03 王鲁 男 教务员 已婚 .95 刘琪 女 实验员 未婚 .24 岳跋 男 教师 已婚 .47 周斌 男 教师 已婚 .17 胡江 男 实验员 未婚 .51 林青 女 教师 未婚 . 索引表数据表索引顺序查找的平均查找长度 =查找“索引”的平均
11、查找长度+ 查找“顺序表”的平均查找长度9.2 动 态 查 找 树 表(n)(1)(n)(nlogn)综合上一节讨论的几种查找表的特性：查找 插入 删除无序顺序表 无序线性链表有序顺序表 静态查找树表(n)(n)(logn)(logn)(1)(1)(n)(nlogn)1）从查找性能看，最好情况能达(logn)，此时要求表有序；2）从插入和删除的性能看，最好情况能达(1)，此时要求存储结构是链表。可得如下结论：一、二叉排序树（二叉查找树）二、二叉平衡树三、B - 树四、B+树一、二叉排序树 （二叉查找树）1定义2查找算法3插入算法4删除算法5查找性能的分析（1）若它的左子树不空，则左子树上所有结
12、点的值均小于根结点的值；1定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；503080209010854035252388例如:是二叉排序树。66不通常，取二叉链表作为 二叉排序树的存储结构typedef struct BiTNode / 结点结构struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;TElemType data;2二叉排序树的查找算法： 1）若给定值等于根结点的关键字， 则查找成功； 2）若给定值
13、小于根结点的关键字， 则继续在左子树上进行查找； 3）若给定值大于根结点的关键字， 则继续在右子树上进行查找。否则，若二叉排序树为空，则查找不成功；50 3080 20908540358832例如:二叉排序树查找关键字= 50 ,505035 ,50 30 40355090 ,50 80 9095 ,从上述查找过程可见，在查找过程中，生成了一条查找路径：从根结点出发，沿着左分支或右分支 逐层向下直至关键字等于给定值的结点;或者从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。查找成功查找不成功算法描述如下：Status SearchBST (BiTree T, KeyType ke
14、y, BiTree f, BiTree / SearchBST 否则表明查找不成功，返回/ 指针 p 指向查找路径上访问的最后一个结点，/ 并返回函数值为FALSE, 指针 f 指向当前访问/ 的结点的双亲，其初始调用值为NULLif (!T)else if ( EQ(key, T-data.key) )else if ( LT(key, T-data.key) )else p = f; return FALSE; / 查找不成功 p = T; return TRUE; / 查找成功SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找30201040352523fT设 key = 48fTfT22pfTfTTTTfffp 根据动态查找表的定义，“插入”操作在查找不成功时才进行；3二叉排序树的插入算法 若二叉排序树为空树，则新插入的 结点为新的根结点；否则，新插入 的结点必为一个新的叶子结点，其 插入位置由查找过程得到。Status Insert BST(BiTree 否则，不进行插入并返回FALSEif (!SearchBST ( T, e.key, NULL,
