2018-03-11 数据结构入门

1.哈希（Hash）

计数排序中的桶就是hash，hash的意思就是一个key对应一个value，如：
数组也是hash：a[0]=1，a[1]=2,......
对象也是hash

2.队列

先进先出，和排队一样

let q = []; 

q.push('第一')；
q.push('第二');
q.push('第三');
q.shift(); //第一
q.shift(); //第二
q.shift(); //第三

基数排序里的桶就是队列，因为是先进先出

3.栈

先进后出，和队列相反

let stack = []; 

stack.push('第一')；
stack.push('第二');
stack.push('第三');
stack.pop(); //第三
stack.pop(); //第二
stack.pop(); //第一

4.链表

let a = {
    value:1,
    next:{
         value:2,
         next:{
            value:3
         }
    }
}

a.next.value=2;
a.next.next.value=3;
比数组好在删除中间的数据很方便，比如删除第二项，直接:

a.next = a.next.next

5.树

1. html就是一种树。
2. 二叉树每个节点最多有两个分支，被称为左子树和右子树
3. 定义根节点为第0层，二叉树的第i层最多有 2ⁱ个节点，整棵树最多有2ⁱ⁺¹-1个节点
4. 完全二叉树和满二叉树可以用数组来存
5. 定义二叉树根节点为第0层，完全二叉树或满二叉树每一层的第一个数在数组中为a[2ⁱ-1]，每一层的最后一个数为a[2ⁱ⁺¹-1-1]