数据结构C描述 查找ppt课件.ppt

《数据结构C描述 查找ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构C描述 查找ppt课件.ppt（68页珍藏版）》请在金锄头文库上搜索。

1、第8章 查找 数据结构 C 描述 1 目录 8 4 散列查找 8 3 树表查找 8 1 查找的基本概念 8 2 线性表的查找 退出 2 8 1 查找的基本概念 查找 也称为检索 在我们日常生活中 随处可见查找 的实例 如查找某人的地址 电话号码 查某单位45岁 以上职工等 都属于查找范畴 本书中 我们规定查找 是按关键字进行的 所谓关键字 key 是数据元素 或记 录 中某个数据项的值 用它可以标识 或识别 一个数据 元素 例如 描述一个考生的信息 可以包含 考号 姓名 性别 年龄 家庭住址 电话号码 成绩等关键 字 但有些关键字不能唯一标识一个数据元素 而有的 关键字可以唯一标识一个数据元素

2、 如刚才的考生信息 中 姓名不能唯一标识一个数据元素 因有同名同姓的人 而考号可以唯一标识一个数据元素 每个考生考号是 唯一的 不能相同 我们将能唯一标识一个数据元素的 关键字称为主关键字 而其它关键字称为辅助关键字或 从关键字 3 有了主关键字及关键字后 我们可以给查找下一个完整 的定义 所谓查找 就是根据给定的值 在一个表中查 找出其关键字等于给定值的数据元素 若表中有这样的 元素 则称查找是成功的 此时查找的信息为给定整个 数据元素的输出或指出该元素在表中的位置 若表中不 存在这样的记录 则称查找是不成功的 或称查找失败 并可给出相应的提示 因为查找是对已存入计算机中的数据所进行的操作

3、所 以采用何种查找方法 首先取决于使用哪种数据结构来 表示 表 即表中结点是按何种方式组织的 为了提高查 找速度 我们经常使用某些特殊的数据结构来组织表 因此在研究各种查找算法时 我们首先必须弄清这些算 法所要求的数据结构 特别是存储结构 查找有内查找和外查找之分 若整个查找过程全部在内 存进行 则称这样的查找为内查找 反之 若在查找过 程中还需要访问外存 则称之为外查找 我们仅介绍内 查找 4 要衡量一种查找算法的优劣 主要是看要找的值与关键字 的比较次数 但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准 对于一个含 有n个元素的表 查找成功时的平均查找长度可表

4、示为 ASL 其中 i为查找第i个元素的概率 且 1 一般情形下我们认为查找每个元素的概率相等 i为查 找第i个元素所用到的比较次数 要衡量一种查找算法的优劣 主要是看要找的值与关键字 的比较次数 但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准 对于一个含 有n个元素的表 查找成功时的平均查找长度可表示为 ASL 其中 i为查找第i个元素的概率 且 1 一般情 形下我们认为查找每个元素的概率相等 i为查找第i个 元素所用到的比较次数 5 8 2 线性表的查找 8 2 1 顺序查找 1 顺序查找的基本思想 顺序查找是一种最简单的查找方法 它的基本思想是 从表的一端

5、开始 顺序扫描线性表 依次将扫描到 的结点关键字和待找的值 相比较 若相等 则查找 成功 若整个表扫描完毕 仍末找到关键字等于 的 元素 则查找失败 顺序查找既适用于顺序表 也适用于链表 若用顺序 表 查找可从前往后扫描 也可从后往前扫描 但若 采用单链表 则只能从前往后扫描 另外 顺序查找 的表中元素可以是无序的 下面以顺序表的形式来描述算法 6 2 顺序查找算法实现 const int n maxn n为表的最大长度 struct node elemtype key key为关键字 类型设定为elemtype int seqsearch node R n 1 elemtype k 在表 中

6、查找关键字值为 的元素 R 0 key k int i n 从表尾开始向前扫描 while R i key k i return i 7 在函数seqsearch中 若返回的值为 表示查找不成功 否则查找成功 函数中查找的范围从 n 到 为监视哨 起两个作用 其一 是为了省去 判定 while循环中下标越界的条件i 1 从而节省比较 时间 其二 保存要找值的副本 若查找时 遇到它 表示查找不成功 若算法中不设立监视哨R 0 程 序花费的时间将会增加 这时的算法可写为下面形式 int seqsearch node R n 1 elemtype k int i n while R i key k

7、return i 当然上面算法也可以改成从表头向后扫描 将监视哨设在右 边 这种方法请读者自己完成 8 3 顺序查找性能分析 假设在每个位置查找的概率相等 即有pi 1 n 由于查 找是从后往前扫描 则有每个位置的查找比较次数Cn 1 Cn 1 2 C1 n 于是 查找成功的平均查找ASL 即它 的时间复杂度为O n 这就是说 查找成功的平均比较次数约为表长的一半 若k值不在表中 则必须进行n 1次比较之后才能确定查 找失败 另处 从ASL可知 当n较大时 ASL值较大 查找的效率较低 顺序查找的优点是算法简单 对表结构无任何要求 无 论是用向量还是用链表来存放结点 也无论结点之间是 否按关键

8、字有序或无序 它都同样适用 顺序查找的缺 点是查找效率低 当n较大时 不宜采用顺序查找 而 必须寻求更好的查找方法 9 8 2 2二分查找 1 二分查找的基本思想 二分查找 也称折半查找 它是一种高效率的查找方法 但二分查找有条件限制 要求表必须用向量作存贮结 构 且表中元素必须按关键字有序 升序或降序均可 我 们不妨假设表中元素为升序排列 二分查找的基本思想 是 首先将待查值K与有序表R 1 到R n 的中点mid上的 关键字R mid key进行比较 若相等 则查找成功 否则 若R mid key k 则在R 1 到R mid 1 中继续查找 若有R mid key k 则在R mid 1

9、 到R n 中继续查找 每通过一次关键字的比较 区间的长度就缩小一半 区 间的个数就增加一倍 如此不断进行下去 直到找到关 键字为K的元素 若当前的查找区间为空 表示查找失败 10 从上述查找思想可知 每进行一次关键字比较 区间数 目增加一倍 故称为二分 区间一分为二 而区间长 度缩小一半 故也称为折半 查找的范围缩小一半 2 二分查找算法实现 int binsearch node R n 1 elemtype k int low 1 high n while lowk high mid 1 在左子区间中查找 else low mid 1 在右子区间中查找 return 0 查找失败 11 例

10、如 假设给定有序表中关键字为 8 17 25 44 68 77 98 100 115 125 将查找K 17和K 120 的情况描述为图8 1及图8 2形式 12 13 14 15 3 二分查找的性能分析 为了分析二分查找的性能 可以用二叉树来描述二分查找 过程 把当前查找区间的中点作为根结点 左子区间和右 子区间分别作为根的左子树和右子树 左子区间和右子区 间再按类似的方法 由此得到的二叉树称为二分查找的判 定树 例如 图8 1给定的关键字序列 8 17 25 44 68 77 98 100 115 125 的判定树见图8 3 16 从图8 3 可知 查找根结点68 需一次查找 查找17和

11、100 各需二次查找 查找8 25 77 115各需三次查 找 查找44 98 125各需四次查找 于是 可以得到 结论 二叉树第K层结点的查找次数各为k次 根结点为 第1层 而第k层结点数最多为2k 1个 假设该二叉树的 深度为h 则二分查找的成功的平均查找长度为 假设 每个结点的查找概率相等 ASL 1 n 1 n 1 2 2 3 22 h 2h 1 因此 在最坏情形下 上面的不等号将会成立 并根据 二叉树的性质 最大的结点数n 2h 1 h log2 n 1 于是 可以得到平均查找长度ASL n 1 n log2 n 1 1 该公式 可以按如下方法推出 17 设s 20 2 21 3 2

12、2 h 1 2h 2 h 2h 1 则2s 21 2 22 h 2 2h 2 h 1 2h 1 h 2h s 2s s h 2h 20 21 22 2h 2 2h 1 h 2h 2h 1 log2 n 1 n 1 n 所以 ASL s n n 1 n log2 n 1 1 当n很大时 ASL log2 n 1 1 可以作为二分查找成功 时的平均查找长度 它的时间复杂度为O log2n 18 8 2 3 索引查找 1 索引查找的思想 索引查找 又称分级查找 它既是一种查找方法 又是 一种存贮方法 称为索引存贮 它在我们的日常生活中 有着广泛的应用 例如 在汉语字典中查找某个汉字时 若知道某个汉字

13、读者 则可以先在音节表中查找到对 应正文中的页码 然后再在正文中所对应的页中查出待 查的汉字 若知道该汉字的字形 但不知道读者 则可 以先在部首表中根据字的部首查找到对应检字表中的页 码 再在检字表中根据字的笔画找到该汉字所在的页码 在这里 整个字典就是索引查找的对象 字典的正文 是字典的主要部分 被称之为主表 而检字表 部首表 和音节表都有是为了方便查找主表而建立的索引 所以 被称之为索引表 19 在索引查找中 主表只有一个 其中包含的是待查找的 内容 而索引表可以有多个 包含一级索引 二级索引 所需的级数可根据具体问题而定 如刚才的利用 读音查找汉字为一级索引 而 利用字形查找汉字为二级

14、索引 部首表 检字表 汉字 在此 我们仅讨论一 级索引 索引查找是在线性表 主表 的索引存贮结构上进行的 而索引存贮的基本思想是 首先将一个线性表 主表 按 照一定的规则分成若干个逻辑上的子表 并为每个子表分 别建立一个索引项 由所有这些索引项得到主表的一个索 引表 然后 可采用顺序或链接的方法来存储索引表和各 个子表 索引表中的每个索引项通常包含三个域 一是索 引值域 用来存储标识对应子表的索引值 它相当于记录 的关键字 在索引表中由此索引值来唯一标识一个索引项 子表 二是子表的开始位置 用来存储对应子表的第 一个元素的存储位置 三是子表的长度 用来存储对应子 表的元素个数 20 例如 设有

15、一个学校部分教师档案表如表8 1所示 设 编号为主关键字 则该表可以用一个线性表L a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 来表示 其中ai 1 i n 表示第i位 教师的信息 包含有编号 姓名 部门 职称 而 它的索引表可以按部门进行 也可以按职称进行 按 部门的索引表中有4个子表 分别为 计算机系J a1 a2 a3 a4 电工系 D a5 a6 a7 管理系G a8 a9 成教部C a10 该4个子表示成一个索引表如表8 2所示 21 表8 1 教师档案表 编号 姓名 部门 职称 J001 赵一 计算机系 教授 J002 钱二 计算机系 讲师 J003 张三 计算机

16、系 副教授 J004 李四 计算机系 助教 D001 王五 电工系 讲师 D002 孙六 电工系 助教 D003 刘七 电工系 副教授 G001 朱八 管理系 教授 G002 杨九 管理系 讲师 C001 罗十 成教部 副教授 表8 2 按部门的索引表 J 0 4 D 4 3 G 7 2 C 9 1 index start length 22 若按职称进行索引 则得到的索引表中也有4个子表 分别为 Jiaosou a1 a8 FuJiaosou a3 a7 a10 Jiangshi a2 a5 a9 Zhujiao a4 a6 这时的主表用顺序存贮不太方便 因相同职称的教师没 有连在一起 故用链式存储得到主表较方便 具体的存 贮如图8 4所示 在图8 4中 箭头上面的数字表示该元 素在主表中的下标位置 指针 每个子表中最后个元 素的指针为 1 表示为空指针 23 于是 可以得到如表8 3所示的职称索引表 表8 3 按职称的索引表 index start length 教授 0 2 副教授 2 3 讲师 1 3 助教 3 2 24 从刚才的两种索引表中 可以给出索引查找的基本思 想如下