第八章查找53923.ppt

第8章 查找 本章中介绍下列主要内容： 静态查找表及查找算法：顺序查找、折半查找 动态查找表及查找算法：二叉排序树 哈希表及查找算法 8.1 基本概念 8.2 静态查找 8.3 动态查找 8.4 哈希表 8.5 应用举例 8.1 基本概念 查找表 用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。 静态查找表 若只对查找表进行如下两种操作： （1）在查找表中查看某个特定的数据元素是否在查找表中， （2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。 动态查找表 若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。 关键字 是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。 查找 在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于某个给定值”，在查找表有哪些信誉好的足球投注网站关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。 查找表的存储结构 查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。 查找算法的时间效率 查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。 查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字——是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~ 8.2 静态查找 正如本章第一节所述：静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。 8.2.1 顺序查找 1. 顺序查找的基本思想 顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。 /* 顺序存储结构 */ typedef struct{ ElemType *elem； /* 数组基址 */ int length； /* 表长度 */ }S_TBL； /* 链式存储结构结点类型 */ typedef struct NODE{ ElemType elem； /* 结点的值域 */ struct NODE *next；/* 下一个结点指针域 */ }NodeType； 8.1 顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 算法描述 8.2.2 折半查找 1. 折半查找的基本思想 折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。 8.2 折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下