数据结构入门

Posted on

1.哈希（Hash）

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

2.队列

先进先出，和排队一样

1
2
3
4
5
6
7
8
let q = []; 

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

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

3.栈

先进后出，和队列相反

1
2
3
4
5
6
7
8
let stack = []; 

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

4.链表

1
2
3
4
5
6
7
8
9
let a = {
    value:1,
    next:{
         value:2,
         next:{
            value:3
         }
    }
}

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

1
a.next = a.next.next

5.树

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