数据结构查找技术1--静态查找表.ppt

第九章 查 找 本章的主要内容是: 查找的基本概念（难度系数*） 静态查找表（难度系数*） 动态查找表（难度系数*） 哈希表（难度系数*） 何谓查找表 ？ 查找表是由同一类型的数据元素( 或记录)构成的集合。 由于“集合”中的数据元素之间存在着 松散的关系，因此查找表是一种应用灵 便的结构。 查找的基本概念 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否 在查找表中； 2）检索某个“特定的”数据元素的各 种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。 不涉及插入和删除操作的查找 。 涉及插入和删除操作的查找。 查找的基本概念 静态查找适用于：查找集合一经生成，便只对其进行 查找，而不进行插入和删除操作，或经过一段时间的 查找之后，集中地进行插入和删除等修改操作； 动态查找适用于：查找与插入和删除操作在同一个阶 段进行，例如当查找成功时，要删除查找到的记录， 当查找不成功时，要插入被查找的记录。 静态查找表 动态查找表 是数据元素（或记录）中某个数据项 的值，用以标识（识别）一个数据元 素（或记录）。 关键字 若此关键字可以识别唯一的一个记 录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称 之谓“次关键字”。 50女李爽0005 25女齐梅0004 47女刘楠0003 25男张亮0002 38男王刚0001 年龄性别姓名职工号 1972.9 2003.7 1979.9 2003.7 1990.4 工作时间 根据给定的某个值，在查找表中确定一个 其关键字等于给定值的数据元素或（记录） 。 查找 若查找表中存在这样一个记录，则称“ 查找成功”。查找结果给出整个记录的信 息，或指示该记录在查找表中的位置； 否则称“查找不成功”。查找结果给出 “空记录”或“空指针”。 由于查找表中的数据元素之间不存在明 显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中 的元素之间人为地 附加某种确定的关系， 换句话说， 用另外一种结构来表示查找表 。 如何进行查找？ 查找的方法取决于查找表的结构。 9.1 静态查找表 9.2 动态查找树表 9.3 哈希表 主要采用顺序查找技术和折半查找技术。 主要采用二叉排序树的查找技术 。 静态查找和动态查找均适用， 主要采用散列技术。 查找算法的性能 查找算法时间性能通过关键码的比较次数来度量。 关键码的比较次数与哪些因素有关呢？ 平均查找长度：将查找算法进行的关键码的比较次数 的数学期望值定义为平均查找长度，即： ASL= = n i ii cp 1 ci取决于算法；pi与算法无关，取决于具体应用。如果pi 是已知的，则平均查找长度只是问题规模的函数。 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 中存在其关键字等于 key 的数据元素，则函数值 为该元素的值或在表中的位 置，否则为“空”。 Search(ST, key); 初始条件： 操作结果： 静态查找表ST存在，key 为 和查找表中元素的关键字类 型相同的给定值； 按某种次序对ST的每个元 素调用函数Visit()一次且仅 一次，一旦Visit()失败，则 操作失败。 Traverse(ST, Visit(); 初始条件： 操作结果： 静态查找表ST存在，Visit 是对元素操作的应用函数； typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable; 假设静态查找表的顺序存储结构为 ElemType *elem; 数据元素类型的定义为: typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; , TElemType ; 一、顺序查找表 二、有序查找表 三、索引顺序表 以顺序表或线性链表 表示静态查找表 一、顺序查找表 顺序查找 （线性查找） 基本思想：从线性表的一端向另一端逐个将关键码与 给定值进行比较，若相等，则查找成功，给出该记录 在表中的位置；若整个表检测完仍未找到与给定值相 等的关键码，则查找失败，给出失败信息。 10 15 24 6 12 35 40 98 55 0 1 2 3 4 5 6 7 8 9 i 例：查找key35 iiiii 顺序查找 （线性查找） int SeqSearch1(int r , int n, int key) /数组r1 rn存放查找集合 i = 1; while (i rmid) low = mid + 1; else return mid; return 0; 折半查找非递归算法 int BinSearch1(int r , int n, int k) /数组r1 rn存放查找集合 low = 1; high = n; while (low rmid) low = mid + 1; else return mid; return 0; 8.2 线性表的查找技术 折半查找非递归算法 折半查找判定树 判定树：折半查找的过程可以用二叉树来描述，树中 的每个结点对应有序表中的一个记录，结点的值为该 记录在表中的位置。通常称这个描述折半查找过程的 二叉树为折半查找判定树，简称判定树。 先看一个具体的情况，假设：n=11 分析折半查找的平均查找长度 6 39 1 4 2 5 7 8 10 11 判定树 12233334444 具有n个结点的折半查找判定树的深度为 查找成功：在表中查找任一记录的过程，即是折半查 找判定树中从根结点到该记录结点的路径，和给定值 的比较次数等于该记录结点在树中的层数。 查找不成功：查找失败的过程就是走了一条从根结 点到外部结点的路径，和给定值进行的关键码的比 较次数等于该路径上内部结点的个数。 。 1log 2 +n 折半查找性能分析 三、索引顺序表的查找 以索引顺序表表示静态查找表，则查找函数可用分 块查找来实现。 分块查找又称索引顺序查找，这是顺序查找的一种 改进方法。 索引顺序表的查找过程： 1）由索引确定记录所在区间； 2）在顺序表的某个区间内进行查找。 注意：索引可以根据查找表的特点来构造。 可见， 索引顺序查找的过程也是一个 “缩小区间”的查找过程。 分块查找方法描述 将n个数据元素“按块有序”划分为m块（m n）。每一块中的结 点不必有序，但块与块之间必须“按块有序”；即第1块中任一元 素的关键字都必须小于第2块中任一元素的关键字；而第2块中 任一元素又都必须小于第3块中的任一元素，依次类推，直至m 块。 分块查找操作步骤 step1 先选取各块中的最大关键字构成一个索引表； step2 查找分两个部分：先对索引表进行二分查找或 顺序查找，以确定待查记录在哪一块中； 然后，在已确定的块中用顺序法进行查找。 分块查找 35 20 8 52 40 61 65 88 76 第 1 块 文件 关键码 其他数据项 第 2 块 第 3 块 35 3 61 3 88 3 索引表 最大值 块长 块首地址 有序 索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度 分块查找 设有n个记录的文件分为m个块，每个块均为t 个记录，则n=mt。设Lb为查找索引表确定关键码 所在块的平均查找长度，Lw为在块内