(C语言详细版)第九章查找选读.ppt

重点：掌握顺序查找、折半查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。 难点：二叉排序树的删除算法及B-树上的插入和删除算法。 ;第九章 查找;9.0 一些定义(1);9.0 一些定义(2);9.0 一些定义(3);9.0 一些定义(4);9.1 静态查找表;ADT StaticSearchTable{ 数据对象D:具有相同特性的数据元素的集合。 数据关系R:数据元素同属一个集合。 基本操作P: Create(ST, n) 操作结果：构造一个含n个数据元素的静态查找表ST. Destroy(ST) 初始条件：静态查找表ST存在. 操作结果：销毁表ST. Search(ST, key) 初始条件：静态查找表ST存在，key为和关键字类型相同的给定值. 操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该 元素的值或在表中的位置，否则为“空”. Traverse(ST,Visit()) 初始条件：静态查找表ST存在,Visit是对元素操作的应用函数. 操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一 次。一旦Visit()失败，则操作失败. } ADT StaticSearchTable;9.1.1 顺序查找(1);9.1.1 顺序查找(2);9.1.1 顺序查找(3);9.1.1 顺序查找(4);9.1.2 有序表的查找-折半查找(1);9.1.2 有序表的查找-折半查找(2);9.1.2 有序表的查找-折半查找(3);9.1.2 有序表的查找-折半查找(4);9.1.2 有序表的查找-折半查找(5);9.1.2 有序表的查找-斐波拉契查找;9.1.2 有序表的查找-插值查找;9.1.3 静态树表的查找(1);9.1.3 静态树表的查找(2);9.1.3 静态树表的查找(3);9.1.3 静态树表的查找(4);9.1.3 静态树表的查找(5);9.1.3 静态树表的查找(6);9.1.4 索引顺序表的查找(1);9.1.4 索引顺序表的查找(2);9.2 动态查找表;9.2 动态查找表-ADT(1);9.2 动态查找表-ADT(2);9.2.1 -二叉排序树(1);9.2.1 -二叉排序树(2);9.2.1 -二叉排序树(3);9.2.1 -二叉排序树(4);9.2.1 -二叉排序树(5);9.2.1 -二叉排序树(6);9.2.1 -二叉排序树(7);48;9.2.1 -二叉排序树(9);9.2.1 -二叉排序树(10);9.2.1 -二叉排序树(11);9.2.1 -二叉排序树(12);9.2.1 -二叉排序树(13);9.2.1 -二叉排序树(14);9.2.1 -平衡二叉树(1);9.2.1 -平衡二叉树(2);9.2.1 -平衡二叉树(3);9.2.1 -平衡二叉树(4);9.2.1 -平衡二叉树(5);9.2.1 -平衡二叉树(6);9.2.1 -平衡二叉树(7);9.2.1 -平衡二叉树(8);9.2.1 -平衡二叉树(9);9.2.1 -平衡二叉树(10);9.2.2 -B-树(1);9.2.2 -B-树(2);9.2.2 -B-树(3);9.2.2 -B-树(4);9.2.2 -B-树(5);9.2.2 -B-树(6);9.2.2 -B-树(7);9.2.2 -B-树(8);9.2.2 -B-树(9);9.2.2 –B+树(1);9.2.2 –B+树(2);9.2.3 键树(1);9.2.3 键树(2);9.2.3 键树(3);9.2.3 键树(4);9.2.3 键树(5);9.2.3 键树(6);9.3 哈希表;9.3.1 什么是哈希表(1);9.3.1 什么是哈希表(2);9.3.1 什么是哈希表(3);9.3.2 哈希函数的构造方法(1);9.3.2 哈希函数的构造方法(2);9.3.2 哈希函数的构造方法(3);9.3.2 哈希函数的构造方法(4);9.3.2 哈希函数的构造方法(5);9.3.2 哈希函数的构造方法(6);9.3.3 处理冲突的方法(1);9.3.3 处理冲突的方法(2);9.3.3 处理冲突的方法(3);9.3.3 处理冲突的方法(4);9.3.3 处理冲突的方法(5);9.3.4 哈希表的查找及其分析(1);9.3.4 哈希表的查找及其分析(2);9.3.