数据结构－第09章－查找_01.pptVIP

计算机控制系统 第一讲 第九章 查找 主要内容及基本要求 1、主要内容 静态查找的几种基本查找算法(顺序查找(9.1.1)、有序查找(9.1.2) 、索引顺序查找(9.1.4) ) 动态查找的几种基本查找算法（二叉排序树、平衡二叉树(9.2.1) 2、基本要求 掌握有序表的查找方法 了解动态查找基本算法 概述 例1：大学入学考试成绩 概述-几个概念 查找表：同一类型的数据元素(或记录)构成的集合； 查找表操作: （1）查询某个“特定的”数据元素是否在查找表中。 （2）检索某个“特定的”数据元素的各种属性。 （3）在查找表中插入一个数据元素； （4）从查找表中删除某个数据元素。 静态查找表：对查找表只做(1), (2)两种操作。 动态查找表：在查找过程中查找表元素集合动态改变，对查找表做 (1), (2) ,(3), (4)操作。 概述-几个概念 关键字(键)：数据元素某数据项的值，能唯一确定结点的一个或多个域。 主关键字：若某关键字能唯一地标识一个记录。 次关键字：用以识别若干记录的关键字。 概述-几个概念 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找是成功的，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功。 平均查找长度：查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）。 概述-关键字类型说明 一些约定： 典型的关键字类型说明 typedef float KeyType; //实型 typedef int KeyType; //整型 typedef char *KeyType; //字符串型 数据元素类型定义 typedef struct { KeyType key; //关键字域 … //其他域 } ElemType ; 概述-关键字类型说明 对两个关键字的比较约定为如下的宏定义： //--对数值型关键字 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)(b)) #define LQ(a,b) ((a)=(b)) //--对字符串型关键字 #define EQ(a,b) (!strcmp(a,b)) #define LT(a,b) (strcmp(a,b)0) #define LQ(a,b) (strcmp(a,b)=0) 9.1 静态查找表 静态查找表的定义（P.216） ADT StaticSearchTable{ 数据对象D: D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R: 数据元素同属一个集合。 基本操作： Create(ST,n); 操作结果：构造一个含n个数据元素的静态查找表ST。 Destroy(ST); 初始条件：静态查找表ST存在。 操作结果：销毁表ST。 9.1 静态查找表 Search(ST，key); 初始条件：静态查找表ST存在，key为给定值。 操作结果：若ST中存在其关键字等于key的数据元素， 则函数值为该元素的值或在表中的位置，否则为“空”。 Traverse(ST,Visit()); 初始条件：静态查找表ST存在，Visit是对数据元素操 作的应用函数。 操作结果：按某种次序对ST的每个数据元素调用函数 visit( )一次且仅一次。一旦visit( )失败，则操作失败。 }ADT StaticSearchTable 9.1 静态查找表 不同的存储方式对应不同的查找算法 用顺序表或线性链表表示静态查找表-Search函数可用 顺序查找； 以有序表表示静态查找表-Search函数可用折半查找； 以索引顺序表表示静态查找表-Search函数可用分块查 找； 9.1.1 顺序表的查找 应用范围：顺序表或线性链表表示的静态查找表。表内元素之间无序。 顺序表的表示和查找。 9.1.1 顺序表的查找 顺序查找算法思想： 从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。 9.1.1 顺序表的查找-例 9.1.1 顺序表的查找-例续1 9.1.1 顺序表的查找 顺序查找算法： 9.1.1 顺序表查找 顺序查找算法性能分析 算法好坏度量：