《数据结构第08章--查找课件》由会员分享,可在线阅读,更多相关《数据结构第08章--查找课件(22页珍藏版)》请在金锄头文库上搜索。
1、数据结构(数据结构(C+版)版)n第1章 绪论第2章 线性表第3章 排序第4章 串第5章 栈与队列第6章 数组和广义表第7章 树和二叉树第8章 查找第9章 图第10章 综合应用设计第8章 查找8.1 查找的基本概念8.2 线性表的查找8.3 二叉排序树及其查找算法8.4 哈希查找数据结构(C+版)叶核亚8.1 查找的基本概念1.查找表与关键字2.查找操作与查找结果3.查找表所具有的数据结构4.查找方法5.查找算法的性能评价6.静态查找表与动态查找表7.查找技术的实现数据结构(C+版)叶核亚8.2 线性表的查找l8.2.1 顺序查找l8.2.2 折半查找l8.2.3 分块查找数据结构(C+版)叶
2、核亚8.2.1 顺序查找1.顺序表的顺序查找数据结构(C+版)叶核亚顺序表的顺序查找算法实现 数据结构(C+版)叶核亚2. 单链表的顺序查找 数据结构(C+版)叶核亚在单链表类Onelink中增加顺序查找算法 数据结构(C+版)叶核亚3算法分析数据结构(C+版)叶核亚8.2.2 折半查找数据结构(C+版)叶核亚2折半查找算法实现数据结构(C+版)叶核亚8.2.3 分块查找1.分块查找算法的基本思想“块间有序、块内无序”。 2.静态查找表的分块查找3.动态查找表的分块查找数据结构(C+版)叶核亚2. 静态查找表的分块查找数据结构(C+版)叶核亚3动态查找表的分块查找数据结构(C+版)叶核亚8.3
3、 二叉排序树及其查找算法1.二叉排序树的定义二叉排序树又称二叉查找树,它可以是一棵空树,若非空时具有下述性质:n若根结点的左子树非空,则左子树上所有结点的关键字值均小于等于根结点的关键字值。n若根结点的右子树非空,则右子树上所有结点的关键字值均大于等于根结点的关键字值。n根结点的左、右子树也分别为二叉排序树。数据结构(C+版)叶核亚2二叉排序树的建立数据结构(C+版)叶核亚3. 二叉排序树插入结点的递归算法 数据结构(C+版)叶核亚建立二叉排序树的算法 数据结构(C+版)叶核亚4. 二叉排序树的查找数据结构(C+版)叶核亚8.4 哈希查找1.哈希函数与哈希表2.哈希查找技术的设计思想设计一个好的哈希函数,尽可能地减少冲突。因为冲突是不可避免的,发生冲突时,使用一种解决冲突的有效方法。3.设计哈希函数4.解决冲突的方法线性开放寻址法拉链法数据结构(C+版)叶核亚采用拉链法的哈希表结构 n设哈希函数hash(k) = k % 10n关键字序列:n9,4,12,3,1,14,74,6,16,96 数据结构(C+版)叶核亚拉链法的哈希表类 数据结构(C+版)叶核亚