数据结构

发表于 | 分类于

本文主要介绍了哈希、队列、栈(stack)、链表、数(tree)

哈希（Hash）

满足键值对(‘key’:’value’)的就是哈希。
数组就是哈希

  • 计数排序中的桶（复杂度 O(n+max)，比快排还快
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    计数排序：
    数组[第0个是4，第1个是1，第二个是8......]
    将数组
    ['0':4,
    '1':1,
    '2':8,
    '3':2,
    '4':9,
    '5':8,
    'length':6  //length等于最大下标index+1
    ]
    里的值放入桶内hash=[]
    hash[
    '1':1 //1有1个
    '2':1
    '4':1
    '8':2 //8有2个
    '9':1
    ]  //hash的length=10，因为最大下标index是9
    然后再从桶里把数值取出来newArr=[]
    newArr[1,2,4,8,8,9]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//计数排序的js代码
var a = [0,2,1,56,4,67,3,2];
//存入hash
var hash = {};
for (i=0;i<a.length;i++) {
  var num = a[i];
  if(!hash[num]){//如果还没有对应的hash
    hash[num] = 1;
  } else {
    hash[num]++;
  }
}
/* console.log(hash); 结果hash = {0: 1, 1: 1, 2: 2, 3: 1, 4: 1, 56: 1, 67: 1}，
表示数字0有1个，数字1有1个，数字2有2个，数字3有1个......  */
//从hash中取出
var max = Math.max.apply(null,a);//获取hash里的最大值
//最大值是max,那么hash的长度length就是max+1;
var length = max+1;
var result = [];
for (i=0;i<length;i++){
  var 个数 = hash[i];
  if (个数) {//如果不是0个
    for (j=0;j<个数;j++) {
      result.push(i);
    }
  }
  
}
console.log(result);

  • (桶排序)[http://bubkoo.com/2014/01/15/sort-algorithm/bucket-sort/] 与计数排序的区别

    1
    2
    3
    4
    5
    6
    7
    8
    9
    桶排序
    hash[
    '1':[5,2,8]  //第1个桶表示10以内的数有5,2,8，然后将这个桶内的数字二次排序
    '2':[]
    '3':[27]
    '4':[33,37,31] //40以内的数有33,37,31,将这几个数字二次排序
    ]
    与计数排序的区别：假设数组中最大的数是1000，那么计数排序需要1000个桶，而桶排序(如果每个桶的区间是100一分割),那么只需要10个桶，但是桶内的数们需要二次排序

  • (基数排序)[http://bubkoo.com/2014/01/15/sort-algorithm/radix-sort/] 与计数排序的区别

    1
    基数排序始终只有10个桶，按照个位、十位、百位、千位.....的数值进行比较,每个桶里的数们组成队列，先进先出

队列（Queue）

  • 先进先出
  • 可以用数组实现
  • 举例：排队
    1
    var out = arr.shift()

栈（Stack）

  • 先进后出
  • 可以用数组实现
  • 举例：坐电梯
    1
    var out = arr.pop()

链表（Linked List）

  • 数组无法直接删除中间的一项，链表可以


  • 用哈希（JS里面用对象表示哈希）实现链表(一个哈希指向另一个哈希)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    [0,2,1]
    var a = {
    value:0,
     next:{
      value:2,
      next:{
       value:1,
       next:undefined
      }
     }
    }
    a.value //0
    a.next.value  //2
    a.next.next.value  //1
    删除中间的2:
    a.next = a.next.next //将a.next指向a.next.next
    a.value //仍旧是0
    a.next.value //变成了1
    a.next.next.value  //undefined

  • head、node 概念

    1
    2
    head：链表的表头
    node：节点，表头属于第一个节点

树（tree）

https://segmentfault.com/a/1190000000740261

  • 举例：有层级结构的需要用到tree，比如DOM树
  • 概念：层数(第0层、第1层、第2层…)、深度(总共有几层)、节点个数(没有下一个节点的叫做叶子节点)
  • 二叉树
  • 满二叉树
  • 完全二叉树

  • 完全二叉树和满二叉树可以用数组实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    arr=[1,2,3,4,5,6,7,8,9,10,11,12,13,15,15]
    如何取第3层的第1个数字？
    arr[Math.pow(2,3-1)-1] //4 【2的3减1次方后减1】
    如何取第3层的第2个数字？
    arr[Math.pow(2,3-1)-1+1]
    如何取第3层的第3个数字？
    arr[Math.pow(2,3-1)-1+2]

  • 其他树可以用哈希（对象）实现

  • 操作：增删改查
  • 堆排序用到了 tree

    1.将数组里的数表示成完全二叉树
    2.然后进行最大堆调整【每个父节点的数值都大于等于其两个孩子结点的数值】：从最后一层的最右边开始到最左边，然后上一层的最右边到最左边，每发生一次交换时，踢下来的数都需要与子节点再次比较
    3.最终，最上面的那个数就是最大的数，把他与最后一个数交换(即放到数组的最后一位)，且这个最大数不再参与排序
    4.由于顶上的数发生了交换，所以继续进行顶上的数与两个子节点比较(也就是说，一开始是从右往左，从下往上比较；当第一次最大堆调整完后，将顶点的数与最后一个数进行交换；接下来就是从上到下进行比较了)

1
2
3
4
5
6
7
1.将数组里的数表现成完全二叉树的形式
2.进行最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
3.创建最大堆：将堆所有数据重新排序，使其成为最大堆
此时最顶端(根节点)的数就是最大的数
4.将根节点的数和最后一个数交换位置，并将最大数挪出，不参与下一轮的排序
5.由于第4步根节点发生了变化，所以剩余的堆需要继续调整为最大堆
6.重复2~5的过程，直到剩余数只有一个时结束。
  • 其他：B树、红黑树、AVL树

堆排序可视化

https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

堆排序JS代码

完整讲解（看到最后）：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/

-------------本文结束感谢您的阅读-------------