当前位置:
文档之家› 源代码--数据结构与算法(Python版)chap9 查找
源代码--数据结构与算法(Python版)chap9 查找
8
折半查找代码
def binarysearch(a, num):
length = len(a)
low = 0 # 最小数下标
high = length – 1
# 最大数的下标
while low <= high: mid = int(low + ((high - low) / 2)) # 取中间值
if a[mid] < num:
5
顺序查找算法容易理解,对表的结构无任 何要求,无论是用顺序存储还是用链表存 储,也无论结点之间是否按关键字排序, 都同样适用。但缺点是效率较低,复杂度 高,时间复杂度为 O(n),折半查找
折半查找的前提是线性表(a0,a1 ,…an-1)已经 按照从小到大的顺序排列。设要查找元素的关键字 为key,首先将查找范围的下限设为low=0,上限 为high=n-1,其中点为m (low high) / 2,中点元 素记为am。用key与中点元素am比较,若key=am, 该元素正为要找的元素,查找停止;否则,若 key>am,则替换下限low=(mid+1),到下半段继续 查找;若key<am,则替换上限high=mid-1,到上 半段继续查找;依此循环,直至找到元素或 low>high为止,low>high时说明此元素未找到。
15 i=7 1 2 5 7 8 11 14 20
(a)查找成功
(b)查找失败
15
i=8(失败) 4
顺序查找代码
def sequential_search(lis, item): pos=0 found = False while pos < len(lis) and not found: if lis[pos] == item: found = True else: pos = pos+1 return(found)
3
【例】如下图,为序列(1, 2, 5, 7, 8, 11, 14, 20)的顺序查
找过程,其中(a)是查找关键字14成功的情况。(b)是未
找到关键字15的情况。
14 查找
01 2345 67 1 2 5 7 8 11 14 20
14 i=0
15 查找
01 2345 67 1 2 5 7 8 11 14 20
30
20
40
10
25 35
48
23
二叉排序树特点:
30
所以,二叉排序树的20形态完全由一4个0 输入序 列决定,一个无1序0 序列可25以通3过5 构造一48棵二
叉排序树而得到一个有23序序列
中序遍历:10,20,23,25,30,35,40,48
1. 中序遍历二叉排序树可得到关键字有序序列。
2. 在构造二叉排序树时,每次插入的新结点都是新 的叶子结点,则进行插入时,不必移动其它结点。
15 i=0
1 2 5 7 8 11 14 20
1 2 5 7 8 11 14 20
14 i=1
15 i=1
1 2 5 7 8 11 14 20
1 2 5 7 8 11 14 20
14 i=2
15 i=2
1 2 5 7 8 11 14 20
1 2 5 7 8 11 14 20
14 i=3
1 2 5 7 8 11 14 20
67 56
30
0
1∧
2
3
4∧
5
6
7
8∧
9
10 ∧ 11 ∧ 12 ∧ 13 ∧
Apr
Dec ∧ Feb ∧
Jan
Mar
Oct
Sep ∧
Aug ∧
Jun May ∧ Nov ∧
采用链地址法处理冲突: Jul ∧
67 14 20
14 low mid high
01 2345 67
15 1 2 5 7 8 11 14 20
查找
15
low mid
high
4567 8 11 14 20
15 low mid high
67 14 20
15 low mid high
7 20
(a)搜索成功
15 low mid high (b)搜索失败
最小数据。为此,构造一个索引表index[l..B],每个
元素index [i](0≤i≤B-1)中存放第i块的最大关键字
key、该块的起始位置start及结束位置end
10
由索引确定记录所在的块,在块内进行查找。 可见,分块查找的过程是一个逐步缩小搜索 空间的过程。
11
二叉查找树
二叉查找树(Binary Search Tree), 又称二叉搜索树或者二叉排序树,具有如下 特性: 1. 若它的左子树不空,则左子树上所有结点 的值均小于根结点的值; 2. 若它的右子树不空,则右子树上所有结点 的值均大于根结点的值; 3. 它的左、右子树也都分别是二叉排序树。
return
bt = bt.left
elif key > entry:
if bt.right is None:
bt.right = BSTNode(key)
return
bt = bt.right
else:
bt.data = key
return
23
{62,88,58,47,35,73,51,99,37,93},构造如图9.7所示的 二叉排序树;如果 {62,88,58,47,35,73,51,99,37,93} 是升序,即{35,37,47,51,58,62,73,88,93,99},构造二 叉排序树如图9.8所示。查找结点99,图9.7只需2次比 较,而图9.8需要比较10次,二者差异很大。
3. 二叉排序树不但拥有类似于折半查找的特性,又 采用了链表作存储结构,因此是动态查找表的一
种适宜表示。
4.二叉排序树的删除算法
和插入相反,删除在查找成功之后进行,并 且要求在删除二叉排序树上某个结点之后,仍 然保持二叉排序树的特性。
可分三种情况讨论:
1. 被删除的结点是叶子; 2. 被删除的结点只有左子树或者只有右子树; 3. 被删除的结点既有左子树,也有右子树。
7
序列(1, 2, 5, 7, 8, 11, 14, 20)的折半查找过程, 其中(a)是查找关键字14的成功的情况,(b)是 未找到关键字15的情况。
01 2345 67
14 1 2 5 7 8 11 14 20
查找 low
14 mid
high
4567 8 11 14 20
14 low mid high
(1)被删除的结点是叶子结点
例如:
被删关键字 = 20 88
50 30
20
40
80 90
35
85
32
88
其双亲结点中相应指针域的值改为“空”
(2) 被删除结点只有左子树或只有右子树
50 30
20
40
被删关键字=40 80
80 90
35
85
32
88
其双亲结点的相应指针域的值改为“指向被 删除结点的左子树或右子树”。
第9章 查找
查找
查找,也称检索,目标是从数据记录中找 到符合某个给定条件的数据记录。查找的 方法大致可分为顺序查找、折半查找与分 块查找等几种类型。
2
查找
顺序查找 顺序查找是一种简单的查找方法,其基本
思想是从表的一端开始,顺序扫描线性表, 依次将扫描到的结点元素值与给定的关键字 key相比较,若结点元素值与key相等,则查 找成功;若扫描完所有结点,仍未找到等于 key的结点,则查找失败。
low = mid + 1 # 如果中间值比目标值小,则在mid右半边
elif a[mid] > num:
high = mid – 1 边找
# 如果中间值比目标值大,则在mid左半
else: return mid
return -1
#查找到,位置是mid+1 #没查到
每执行一次while循环, 搜索空间减少一半。在最坏情 况下,while循环被执行O(logn) 次。循环体内运算需要执 行O(1) 次,因此整个算法的计算时间复杂度为O(logn) 。
22
插入
def insert(self, key):
#插入操作
bt = self._root
if not bt:
self._root = BSTNode(key)
return
while True:
entry = bt.data
if key < entry:
if bt.left is None:
bt.left = BSTNode(key)
15 i=3
1 2 5 7 8 11 14 20
14 i=4 1 2 5 7 8 11 14 20
15 i=4 1 2 5 7 8 11 14 20
14 i=5
15 i=5
1 2 5 7 8 11 14 20
1 2 5 7 8 11 14 20
14 i=6(找到)
15 i=6 1 2 5 7 8 11 14 20
12
二叉查找树
13
二叉查找树
14
3.二叉排序树的插入算法
根据动态查找表的定义,“插入”操作在查 找不成功时才进行;
(1)若二叉排序树为空树,
则新插入的结点是新的根结点
设 key = 30
30
(2)若二叉排序树非空, 则新插入的结点是新的叶子结点, 且插入的位置由查找过程得到 。
设 key = 25 48
关键 12 25
16
字
67 56
29