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

有序表的查找 例如: key = 64 的查找过程如下 ST.elem ST.length low high mid low mid mid high 有序表的查找 int Search_Bin ( SSTable ST, KeyType kval ) { low = 1; high = ST.length; // 置区间初值 while (low = high) { mid = (low + high) / 2; if （kval == ST.elem[mid].key ) return mid; // 找到待查元素 else if ( kval ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin 有序表的查找 1 2 2 3 3 3 3 4 4 4 4 折半查找性能分析 当有序表中有11个元素时，其元素的比较次数如下表所示 有序表的查找 判定树： 6 3 9 1 2 5 7 8 10 11 4 有序表的查找 6 3 9 1 2 5 7 8 10 11 4 1）查找64的过程 6 9 7 2）查找30的过程 3 4 6 5 有序表的查找 判定树： 1.用二叉树来描述折半查找，树中每个结点表示一个记录，结点中的值为该记录在表中的位置，这种描述查找过程的二叉树成为判定树。 2.查找有序表中任一记录的过程就是走了一条从根结点到该记录相应结点的路径。 3.和给定值进行比较的关键字个数为该结点在判定树上的层次。 有序表的查找 假设 n=2h-1 并且查找概率相等，则 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。 在 n50 时，可得近似结果 * * 查找和静态查找表 1. 查找问题的定义 2. 静态查找表 3. 小结和作业 查找问题的定义 1. 查找表 2. 查找表分类 3. 关键字 4. 查找 静态查找表 1. 静态查找表的类型定义 2. 顺序表的查找 3. 有序表的查找 4. 索引顺序表 查找表 定义： 由同一类型的数据元素(或记录)构成的集合。 查找表 对查找表经常进行的操作: 1）查询：查询某个“特定的”数据元素是否在查找表中； 2）检索：检索某个“特定的”数据元素的各种属性； 3）插入：在查找表中插入一个数据元素； 4）删除：从查找表中删去某个数据元素。 查找表分类 仅作查询和检索操作的查找表。 1.静态查找表 1）在查询之后，需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中； 2）从查找表中删除其“查询”结果为“在查找表中”的数据元素。 2.动态查找表 关键字 关键字：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 主关键字：可以识别唯一的一个记录的关键字 次关键字：能识别若干记录的关键字 查找 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录） 查找成功：若查找表中存在这样一个记录，则称“查找成功”。 查找结果：给出整个记录的信息，或指示该记录在查找表中的位置； 查找 查找不成功：若查找表中不存在这样一个记录，则称“查找不成功”。 查找结果：给出“空记录”或“空指针”。 如何进行查找 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间仅存在“同属于一个集合”的松散关系，不存在明显的组织规律，因此不便于查找。 如何进行查找 1.静态查找表 2.动态查找表 3.哈希表 为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。 静态查找表 数据对象D： 数据关系R： D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据元素同属一个集合。 ADT StaticSearchTable { 静态查找表 Create(ST, n); Destroy(ST); Search(ST, key); Traverse(ST, Visit()); 基本操作 P： } ADT StaticSearchTable 静态查找表—基本操作 Create(ST, n); 操作结果：构造一个含 n 个数据元素的静态查找表ST。 Destroy(ST); 初始条件：静态查找表ST存在； 操作结果：销毁表ST。 静态查找表—基