数据结构（初级）

数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面会简单的介绍一些数据结构和算法，欢迎纠错。

一、数据结构

1、哈希表（Hash table）

Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。
这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。
也就是说，哈希表的结构就是以键-值(key-value)这样一种映射来存储数据，这样当我们需要查找时只要输入key，就可以查找到相对应的值。

这是对于简单的键的情况。当我们处理更加复杂的类型的键的时候就会涉及到处理多个键被哈希到同一个索引值的情况，也就是我们要学习如何处理哈希碰撞冲突，由于还没深入学习，这里就先不涉猎了。

2、队列（Queue）

• 先进先出
• 在队尾插入元素，在队首删除元素

就像排队一样，在队列中先进来排队的人也就是队首的先出去，而新来的人想要排队也只能从队尾开始。

var q = []  //空队
// 进队
q.push('柠萌')
1
q.push('曹玫')
2
q.push('项焦')
3
// 出队
q.shift()
'柠萌'
q.shift()
'曹玫'
q.shift()
'项焦'

3、栈(Stack)

• 先进后出
• 限定仅在表尾进行插入和删除操作

我们把允许插入和删除的一端成为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。

就像盗梦空间，我们依次进入第一层梦，第二层梦，第三层梦，退出时也只能先退出第三层梦，再退出第二层，第一层。

var stack = []
// 进栈
stack.push('第一层梦')
1
stack.push('第二层梦')
2
stack.push('第三层梦')
3
// 出栈
stack.pop()
"第三层梦"
stack.pop()
"第二层梦"
stack.pop()
"第一层梦"

4、链表（Linked list）

• 链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成。
• 结点包括两个部分：一、存储数据元素的数据域（内存空间），二、存储指向下一个结点地址的指针域。
• 实现数据元素的存储按一定顺序储存，允许在任意位置插入和删除结点。
• c/c++/jave都可以实现

image

5、树(tree)

树是由n（n>=1）个有限节点组成一个具有层次关系的集合。

特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树。

二叉树：满足每个节点最多两个叉（Binary tree）

满二叉树：叶子全满

每一层上节点数都是最大节点数

image

满足i层，最多节点2^i, 所有层节点数即2^(i-1) - 1

完全二叉树：除了最后一层，其余层叶子均满，最后一层或满或右边缺少连续若干节点。

image

完全二叉树和满二叉树都可以用数组来存储。