C/C++教程

数据结构中的Direct-address table、Hash table、Biany Search tree

本文主要是介绍数据结构中的Direct-address table、Hash table、Biany Search tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Direct-address table(直接地址表)

非常占用空间的一种table。

通过索引其中的Key值(下图中2、3、5、8),来找到key值对应的data(图中的satellite data,也可以理解为element)。

而图中的0、1、4等key都是NULL。U代表全部key,暴力翻译一下是Key宇宙...或者通用Key?我也不知道对应什么中文,总之就是所有整形key的一个池子,包含了{0,1,2……,n-1}(注意从0开始)。

其中没有两个data对应同一个key。

 

这种方法优点是:Search、Insert、Delete操作都只需O(1),但是缺点是:key必须是小整数,且key数量不能过多。这项缺陷可以通过Hash table来改善。

 

 

 Hash table(哈希表)

也被称为Hash map。哈希表在CSDN等地方,时常见到,但一直以来我并不知道Hash是什么东西,直到玩了《戴森球计划》看到了里面的哈希块,才明白了一点(鬼扯)

 

Hash.1

 Hash collision(哈希碰撞),当复数的对象对应同一个key值时就会发生这种情况,如下图

Hash.2

 

Binary search tree(二叉搜索树)

上面的Hash table仅支持字典操作也就是insert, delete, search,但是二叉搜索树也支持求最大、最小值

二叉搜索树的x节点的left.pointer存在,则left child的每个节点的值 <=  x节点的值;反之,若x节点right.pointer存在,则right child的每个节点的值 >= x节点的值。

 

这篇关于数据结构中的Direct-address table、Hash table、Biany Search tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!