Skip to content

Latest commit

 

History

History

DataStructure

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 

链表

我们知道用数组存放数据时,必须事先定义数组的长度(即元素个数)。当事先难以确定有多少个元素时,则必须把数组定义的足够大,以保证成功。无疑,这会造成内存浪费。因此可以考虑设计一种物理存储单元上非连续、非顺序的存储结构,来避免数组带来的问题,链表正是这样的一种数据结构。

链表由一系列结点(链表中每一个元素称为结点)组成,每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

更多内容参考 LinkedList

栈是一种最基本、最常用的数据结构,一个词来总结栈的特点就是后进先出。我们可以将栈看作是一个数据仓库,向栈内增加数据的操作叫入栈(push)操作,从栈内取出数据的操作叫出栈(pop)操作。不过不像一般的仓库一样,可以随意取出任何位置的物品,从一个栈取出的数据必须是最后一次增加的数据。换句话就是说,最后一个进入栈的数据,会被第一个取出来。

生活中有很多场景包含有后进先出的思想,比如刷盘子这个过程,我们将已经洗好的盘子叠在一起,每次洗好一个盘子就将堆在顶部,而我们需要用一个盘子时也是从最上面取走。

栈有许多典型应用场景,比如函数调用,表达式计算,表达式转换,模拟递归等。

更多内容参考 Stack

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

更多内容参考 Heap

Hashtable

哈希表就是一种以键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即 key,即可查找到其对应的值。例如若关键字为k,则其值存放在 f(k) 的存储位置上,由此不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数,按这个思想建立的表为哈希表(散列表)。

哈希查找第一步就是使用哈希函数将键映射成索引,这种映射函数就是哈希(散列)函数。哈希函数需要易于计算并且能够均匀分布所有键。一个好的哈希函数必须在理论上非常的快、稳定并且是可确定的。

对不同的关键字可能得到同一散列地址,即k1 != k2,而f(k1)=f(k2),这种现象称为冲突(Collision),避免hash碰撞碰撞的方法有:拉链法,开放定址法,再散列,建立一个公共溢出区等。

更多内容参考 HashTable

树(Tree)是n(n≥0)个有限数据元素的集合。当n=0 时,称这棵树为空树。在一棵非空树T 中:

  1. 有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。
  2. 除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm 为这个根结点的子树(subtree)。

二叉树是每个节点最多有两个子树的树结构。二叉树的每个结点至多只有二棵子树,二叉树的子树有左右之分,次序不能颠倒。

二叉查找树,也称排序二叉树,是指一棵空树或者具备下列性质的二叉树(每个结点都不能有多于两个儿子的树):

  1. 若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意结点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的结点

更多内容参考 BS_Tree

AVL树是最早提出的自平衡二叉树,它是一种特殊的二叉搜索树,任一节点的左子树深度和右子树深度相差不超过1,所以它也被称为高度平衡树。

更多内容参考 AVL_Tree

红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除等操作。

更多内容参考 RB_Tree

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

更多内容参考 Graph

bitmap

位图(bitmap)是一种非常常用的结构,在索引,数据压缩等方面有广泛应用,能同时使存储空间和速度最优化。例如可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合,可以用 01110100100 表示集合 {1,2,4,5,8} ,对应位置数字存在标记为1,否则标记为0。

C 语言位图实现如下:

主要程序如下:

#define SHIFT 5  
#define MASK 0x1F  

//set 设置所在的bit位为1  
//clr 初始化所有的bit位为0  
//test 测试所在的bit为是否为1  

set(int i) {
    a[i>>SHIFT] |=  (1<<(i & MASK)); }  
clr(int i) {
    a[i>>SHIFT] &= ~(1<<(i & MASK)); }  
test(int i){
    return a[i>>SHIFT] & (1<<(i & MASK)); } 

字节位置=数据/32 (采用位运算即右移5位)
位位置=数据%32 (采用位运算即跟0X1F进行与操作)。

特定适用场合:

  1. 对10亿个不重复的整数进行排序。
  2. 找出10亿个数字中重复的数字。

如果用普通的排序算法,数据放进内存就需要 ( 10^9 * 4)/( 2^30 ) = 3.7G。改用 Bitmap 的话,一个数字占一位,一共需要 3.7/32 = 0.1 G 内存。

更多阅读

《剑指 Offer》
树、森林与二叉树的转换
数据结构之树
轻松搞定面试中的二叉树题目
卡特兰数
详解bitmap算法
浅谈算法和数据结构: 十一 哈希表
哈希碰撞