|
经过n久的沉寂，偶又回来了！
第七日：基本数据结构(二)
1、哈希表
也叫散列表
很多时候，应用程序需要这样一种结构
仅需要三个基本操作：
插入、查找、删除
哈希表就可以提供这样的功能组合
哈希表是一种在线性表基础上实现的数据结构
一般而言,可以把数组理解为一个不带操作线性表
为了便于理解,以数组的概念代替线性表
假定每个元素(数据项)都有一个域称为关键域
通过某种方法,如果可以在数组的下标和关键域值(简称关键值)之间建立某种映射关系(如果高中数学没忘光的话,应该记得这个概念)
那么这个数组就可以叫做一个哈希表
建立下标和关键值之间映射的方法,称为哈希函数,或者散列函数
在这里,散列的意思可以理解为,将集合中的元素,分散到了数组之中
哈希表是实现字典的一个很有效的手段
想到了点儿什么没有？bingle！拼音检字法就是一种有效的哈希方案
声母和韵母作为关键值，页码是数组下标，拼音检字表就是一个哈希表
不过想要检索到一个字，要计算两次哈希函数
第一次检索到声母，第二次检索到拼音对应的页码
偏旁部首检字也是类似的
最简单的哈希表是直接寻址表,下标等于关键值
哈希函数是T[k]=k,也就是y=x
插入、删除、查找操作都很好实现，就不一一列出了
而且这些操作都很快，o(1)时间就可以实现
但是这种表的缺陷也很明显，如果集合内关键值的取值范围很大，就要有一个相应大小的数组与之对应才行
这个问题也很好解决，想想字典是怎么做的
建立哈希函数的时候，使定义域大于值域，也就是缩小结果的取值范围
简单的讲就是从关键值中提取共性，比如拼音中的声母，比如部首检字法中的偏旁
作用都是一样的
这样就可以使不同的关键值被映射到哈希表中的同一个位置
这样又引出了两个问题：
1、数组的一个下标的位置只能存一个值，如何处理映射过来的多个值？
2、如何使对应到每个下标的元素个数不要相差太大
第一个问题很好解决，可以在数组中存放一个指向链表的指针，具体元素存放在链表中
第二个问题就很不好回答了，如果做不到这一点，一个哈希函数就必定不是一个好的哈希函数
2、二叉查找树(二叉搜索树)
二叉查找树首先是一颗二叉树，它仅比二叉树多了以下特性
假设x是二叉查找树上的一个节点
如果y是x的左子树上的一个节点，那么key[y]<=key[x]
如果y是x的右子树上的一个节点，那么key[y]>=key[x]
从这种意义上讲，一个升序排列的链表可以看作是一个所有左子为nil的二叉排序树
定义在二叉搜索树上的基本操作：
查找:
TREE-SEARCH(x,k)
1 if x = NIL or k= key[x]
2 then return x
3 if k<key[x]
4 then return TREE-SEARCH(left[x],k)
5 else return TREE-SEARCH(right[x],k)
非递归的查找算法:
ITERATIVE-TREE-SEARCH(x,k)
1 while x <> NIL and k <> key[x]
2 do if k < key[x]
3 then x <- left[x]
4 else x <- right[x]
5 return x
最小和最大
TREE-MINIMUM(x)
1 while left[x] <> nil
2 do x <- left[x]
3 return x
TREE-MAXIMUM(x)
1 while right[x] <> nil
2 do x <- right[x]
3 return x
后继与前驱
TREE-SUCCESSOR(x)
1 if right[x] <> NIL
2 then return TREE-MINIMUM(right[x])
3 y <- p[x]
4 while y <> NIL and x = right[y] //父亲节点是左孩子的直接后继
5 do x <- y
6 y <- p[y]
7 return y
求前驱把以上过程中左右反过来就可以了
插入与删除
插入比较简单,找到地方,插进去,嗯
TREE-INSERT(T,z)
1 y <- NIL
2 x <- root[T]
3 while x <> NIL
4 do y <- x
5 if key[z] < key [x]
6 then x <- left[x]
7 else x <- right[x]
8 p[z] <- y
9 if y = NIL
10 then root[T] <- z //树T空的时候
11 else if key[z] < key[y]
12 then left[y] <- z
13 else right[y] <- z
删除就比较麻烦了,自己画个图可能会比较好理解
分以下几种情况：
如果z的左子树或者右子树为空，直接以左子树或右子树替换z
都不空的情况下
如果z的直接后继没有右子树(肯定没有左子树)，用后继替换z
如果后继有右子树，先用右子树替换后继，在用后继替换z
不知道有没有人能看懂我说了些什么
TREE-DELETE(T,z)
1 if left[z] = NIL or right[z] = NIL
2 then y <- z
3 else y <- TREE-SUCCESSOR(z)
4 if left[y] <> NIL
5 then x <- left[y]
6 else x <- right[y]
7 if x <> NIL
8 then p[x] <- p[y]
9 if p[y] = NIL
10 then root[T] <- x
11 else if y = left[p[y]]
12 then left[p[y]] <- x
13 else right[p[y]] <- x
14 if y <> z
15 then key[z] <- key[y]
16 把y的数据copy到z
17 return y
就到这里，休息！
|
