数据结构(
Java版)数据结构(版
(第2版)版
叶核亚
数据结构(数据结构(Java版)(第2版)版版
第0章Java
程序设计基础第1章绪论第2章线性表第3章栈与队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章排序第10章综合应用设计第11章Java开发运行环境
第8章章
8.18.2
查找
查找的基本概念基于线性表的查找
8.3树结构的查找8.4散列目的:查找算法设计。目的:查找算法设计。要求:掌握给定数据结构的查找操作,要求:掌握给定数据结构的查找操作,掌握提高查找效率采取的各种方法。握提高查找效率采取的各种方法。重点:二叉排序树,散
列表。重点:二叉排序树,散列表。难点:二叉排序树,散列表。难点:二叉排序树,散列表。
《数据结构(Java版)(第2版)》
8.1查找的基本概念
1.2.3.
查找操作和查找结果查找算法查找算法性能评价
ASL=∑(pi×ci)
i=1n
《数据结构(Java版)(第2版)》
8.2基于线性表的查找
8.2.1顺序查找8.2.2基于有序顺序表的折半查找8.2.3基于索引顺序表的分块查找
《数据结构(Java版)(第2版)》
8.2.1顺序查找
1.2.3.
顺序表的顺序查找单链表的顺序查找顺序查找算法分析
1n1n(n+1)n+1=∑(pi×ci)=∑i=×==O(n)ni=1n22i=1
n
ASL成功
ASL不成功
1=∑(pi×ci)=∑(×n)=n=O(n)i=1i=1n
《数据结构(Java版)(第2版)》
n
n
8.2.2基于有序顺序表的折半查找
1.2.
折半查找算法描述折半查找算法实现
《数据结构(Java版)(第2版)》
3.折半查找算法分析折半查找算法分析
121ASL成功=(1+2+2+3+3+3+3+4)==2.62588
《数据结构(Java版)(第2版)》
8.2.3基于索引顺序表的分块查找
1.2.
索引分块查找
①
字典的分块查找
《数据结构(Java版)(第2版)》
判断一个字符串是否为Java关键字。关键字。例8.1判断一个字符串是否为关键字
《数据结构(Java版)(第2版)》
(2)支持插入和删除操作的索引结构)及其分块查找
《数据结构(Java版)(第2版)》
《数据结构(Java版)(第2版)》
8.3树结构的查找
8.3.1二叉排序树及其查找8.3.2平衡二叉树
《数据结构(Java版)(第2版)》
8.3.1二叉排序树及其查找
1.2.3.
定义查找插入
《数据结构(Java版)(第2版)》
【例8.2】二叉排序树的插入和查找】操作。操作。