数据结构

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 373 | 阅读时长 ≈ 1 分钟
常见数据结构 js 的实现，包括：栈、队列、链表、二叉树、二叉堆、哈希表、集合、字典和图

栈

数据结构(三)之栈结构

代码实现：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function Stack () {  
  this.items = [];

  // 这个相当于给每个实例对象创建这个方法，不推荐这么使用
  // this.push = function () {  }

  // 这个相当于给整个类添加这个方法，节省内存，效率更高
  // 压栈
  Stack.prototype.push = function (item) {  
    this.items.push(item);
  }

  // 弹栈
  Stack.prototype.pop = function () {  
    return this.items.pop();
  }

  // 返回栈顶元素
  Stack.prototype.peek = function () {  
    return this.items[this.items.length - 1];
  }

  // 判断栈是否为空
  Stack.prototype.isEmpty = function () {  
    return this.items.length === 0;
  }

  // 栈的元素个数
  Stack.prototype.size = function () {  
    return this.items.length;
  }

  // 以字符形式返回栈的内容
  Stack.prototype.toString = function () {  
    let len = this.items.length;
    let resultString = '';

    // for (let i = 0; i < len; i++) {
    //   resultString += this.items[i] + ' ';
    // }

    this.items.forEach((item) => (
      resultString += item + ' '
    ))

    return resultString;

    // reducer 实现
  }
}

案例：

十进制转换为二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function dec2bin (decNum) {  
  let stack = new Stack();

  while(decNum > 0) {
    stack.push(decNum % 2);
    decNum = Math.floor(decNum / 2);
  }

  let binaryStr = '';
  while (!stack.isEmpty()) {
    binaryStr += stack.pop();    
  }

  return binaryStr;
}

console.log(

dec2bin(100)
);

队列

数据结构(四)之队列结构

代码实现：

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
function Queue() {
  this.items = [];

  Queue.prototype.enqueue = function (element) {
    this.items.push(element);
  }

  Queue.prototype.dequeue = function () {
    return this.items.shift();
  }

  Queue.prototype.front = function () {
    return this.items[0];
  }

  Queue.prototype.isEmpty = function () {
    return this.items.length === 0;
  }

  Queue.prototype.size = function () {
    return this.items.length;
  }

  Queue.prototype.toString = function () {
    let resultString = '';

    this.items.forEach((item) => (
      resultString += item + ' '
    ))
    return resultString;
  }
}

优先级队列：

1、利用二叉堆实现

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
34
35
36
37
38
const MinHeap = require('./js/MinHeap.js')

function PriorityQueue() {
  this.minHeap = new MinHeap();
  this.items = this.minHeap.heap;
}

PriorityQueue.prototype = {
  constructor: PriorityQueue,
  enqueue: function (element, priority) {  
    function QueueElement(element, priority) {
      this.element = element;
      this.priority = priority;
    }
    let queueElement = new QueueElement(element, priority);
    this.minHeap.insert(queueElement);      
  },
  dequeue: function () {  
    return this.minHeap.remove(this.items[0]);
  },
  front: function () {  
    return this.items[0];
  },
  isEmpty: function () {  
    return this.items.length === 0;
  },
  size: function () {  
    return this.items.length;
  },
  toString: function () {  
    let resultString = '';

    this.items.forEach((item) => (
      resultString += `${item.element}-${item.priority} `
    ))
    return resultString;
  },
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
	MinHeap.js
  实现优先队列的最小二叉堆方法
*/

function MinHeap() {
  this.heap = [];
}

MinHeap.prototype = {
  constructor: MinHeap,

  size: function () {  
    return this.heap.length
  },

  // 插入
  insert: function (objectData) {  
    this.heap.push(objectData);
    // 堆上浮自调整
    this.siftUp(this.size() - 1)
  },

  // 删除结点
  remove: function (objectData) {  
    // 空堆返回-1
    if (!this.heap.length) return -1;
    // 获取 objectData 的索引
    let index = this.heap.indexOf(objectData);
    if (index === -1) return -1;

    //将最后的结点补到被删的结点处
    //实现为将最后的结点赋值覆盖被删的结点，再删除最后的结点
    this.heap[index] = this.heap[this.size() - 1];
    this.heap.pop();
    
    //堆中至少有两个结点才需要自调整下沉
    if (this.size() > 1) {
      this.siftDown(index, this.size() - 1);
    }

    // 返回删除的数据
    return objectData;
  },

  print: function () {  
    let str = '';
    for (let i = 0; i < this.size(); i++) {
      str += `${this.heap[i]} `;
    }
    console.log(str);
    
  },

  // 结点上浮
  siftUp: function (nodeIndex) {
    let parentIndex = Math.floor((nodeIndex - 1) / 2);
    let temp = this.heap[nodeIndex];

    while (nodeIndex > 0) {
      // 父结点的权重是否大于子结点的权重
      let isLarger = this.heap[parentIndex].priority > temp.priority;
      if (isLarger) {
        this.heap[nodeIndex] = this.heap[parentIndex];
        nodeIndex = parentIndex;
        parentIndex = Math.floor((parentIndex - 1) / 2);
      } else break;
    }

    this.heap[nodeIndex] = temp;
  },

  // 结点下沉
  siftDown: function (nodeIndex, lastIndex) {
    let childIndex = 2 * nodeIndex + 1;
    let temp = this.heap[nodeIndex];
    while (childIndex <= lastIndex) {
      // childIndex + 1 <= lastIndex 判断右孩子有没有超出边界，超出的话不会执行 && 后面的语句
      // 如果右孩子没有超出边界，则判断左孩子权重是否比右孩子权重大
      if (childIndex + 1 <= lastIndex && (this.heap[childIndex].priority > this.heap[childIndex + 1].priority)) {
        childIndex++;
      }
      // 判断当前结点是否比子结点大
      isLarger = temp.priority > this.heap[childIndex].priority;
      if (isLarger) {
        this.heap[nodeIndex] = this.heap[childIndex];
        nodeIndex = childIndex;
        childIndex = 2 * childIndex + 1;
      } else {
        break;
      }
    }
    this.heap[nodeIndex] = temp;
  },
}

module.exports = MinHeap;

2、每次插入队列时，都和队列里的每个数进行比较，按从小到大顺序在队列（数组）里面存储（性能不好）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
function PriorityQueue() {
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }

  this.items = [];

  PriorityQueue.prototype.enqueue = function (element, priority) {  
    let queueElement = new QueueElement(element, priority);
    
    let added = false;
    if (this.items.length === 0) {
      this.items.push(queueElement)
    } else {
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }

  PriorityQueue.prototype.dequeue = function () {
    return this.items.shift();
  }

  PriorityQueue.prototype.front = function () {
    return this.items[0];
  }

  PriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0;
  }

  PriorityQueue.prototype.size = function () {
    return this.items.length;
  }

  PriorityQueue.prototype.toString = function () {
    let resultString = '';

    this.items.forEach((item) => (
      resultString += `${item.element}-${item.priority} `
    ))
    return resultString;
  }
}

案例：

击鼓传花

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
/**
 * 击鼓传花
 * @param {名字列表} nameList
 * @param {淘汰的数字} num
 */
function passGame(nameList, num) {
  // 创建队列
  let queue = new Queue();

  // for (let i = 0; i < nameList.length; i++) {
  //   queue.enqueue(nameList[i]);
  // }
  // 将队列加入队列
  nameList.forEach((name) => (queue.enqueue(name)));

  // 开始数数字
  while (queue.size() > 1) {
    // 不是num的时候，将重新加入队尾
    // 是num的时候，将其从队首中删除
    for (let i = 0; i < num - 1; i++) {
      queue.enqueue(queue.dequeue());
    }
    queue.dequeue();
  }

  let index = nameList.indexOf(queue.front());
  return nameList[index];
}

let list = ['zhang', 'tang', 'shen', 'huang', 'lai']
let game = passGame(list, 3);
console.log(game);

链表

单向链表

数据结构(五)之链表结构

代码实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/**
 * 封装列表类
 */
function LinkedList() {
  // 内部的类：节点类
  function Node(data) {
    this.data = data;
    this.next = null;
  }

  this.head = null;
  this.length = 0;

  // 追加方法
  LinkedList.prototype.append = function (data) {
    // 创建新节点
    let newNode = new Node(data);

    // 判断是否为第一个节点
    if (this.length === 0) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }

    // 最后的节点的next指向新节点
    this.length++;
  }

  // insert 方法
  LinkedList.prototype.insert = function (position, data) {  
    // 越界判断
    if (position < 0 || position > this.length) return false;

    let newNode = new Node(data);
    if(position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let previous = this.getNode(position - 1);
      newNode.next = previous.next;
      previous.next = newNode;
    }

    return true;
  }

  LinkedList.prototype.get = function (position) {  
    if (position < 0 || position > this.length) return false;
    return this.getNode(position).data;
  }

  LinkedList.prototype.getNode = function (position) {  
    if (position < 0 || position >= this.length) return false;

    let current = this.head;
    let index = 0;
    while (index++ < position) {
      current = current.next;
    }

    return current;
  }


  LinkedList.prototype.indexOf = function (data) {  
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  LinkedList.prototype.update = function (position, data) {  
    if (position < 0 || position >= this.length) return false;

    this.getNode(position).data = data;
    return true;
  }

  LinkedList.prototype.removeAt = function (position) {  
    if (position < 0 || position >= this.length) return false;

    if (position === 0) {
      this.head = this.head.next;
    } else {
      // 找到要删除节点的前一个节点
      let previous = this.getNode(position - 1);
      // 将 position 的前一个节点指向 position 的后一个节点,即删除了 position 位置的节点
      previous.next = previous.next.next;
    }
  }

  LinkedList.prototype.remove = function (data) { 
    if (this.head.data === data) {
      this.head = this.head.next;
    } else {
      let current = this.head;
      while (current !== null && current.next !== null) {
        if (current.next.data === data) {
          current.next = current.next.next;
          return data;
        }
        current = current.next;
      }
    }
    return false;
  }

  LinkedList.prototype.isEmpty = function () {  
    return this.length === 0;
  }

  LinkedList.prototype.size = function () {  
    return this.length;
  }

  LinkedList.prototype.toString = function () {  
    let listString = '';
    current = this.head;

    while(current) {
      listString += current.data + ' ';
      current = current.next;
    }

    return listString;
  }
}

双向链表

数据结构(六)之双向链表

代码实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
function DoublyLinkedList() {
  function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }

  this.head = null;
  this.tail = null;
  this.length = 0;

  DoublyLinkedList.prototype.append = function (data) {  
    let newNode = new Node(data);

    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
  }

  DoublyLinkedList.prototype.toString = function (data) {  
    return this.forwardString();
  }

  DoublyLinkedList.prototype.backwardString = function (data) {  
    let listString = '';
    let current = this.tail;

    while (current) {
      listString += current.data + ' ';
      current = current.prev;
    }
    return listString;
  }

  DoublyLinkedList.prototype.forwardString = function (data) {  
    let listString = '';
    let current = this.head;

    while(current) {
      listString += current.data + ' ';
      current = current.next;
    }

    return listString;
  }

  // 根据节点获取节点的数据
  DoublyLinkedList.prototype.get = function (position) {  
    if (position < 0 || position >= this.length) return false;
    
    return this.getNode(position).data;
  }

  DoublyLinkedList.prototype.getNode = function (index) {  
    if (index < 0 || index >= this.length) return false;
    // index 小于链表中间位置时，从头结点开始遍历，否则从尾结点开始遍历
    if (index < (this.length >> 1)) {
      let x = this.head;
      for (let i = 0; i < index; i++)
        x = x.next;
      return x;
    } else {
      let x = this.tail;
      for (let i = this.length - 1; i > index; i--)
        x = x.prev;
      return x;
    }
  }


  DoublyLinkedList.prototype.indexOf = function (data) {  
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

  DoublyLinkedList.prototype.update = function (position, data) {  
    if (position < 0 || position >= this.length) return false;

    // this.length / 2 < position: 从后向前遍历
    // this.length / 2 > position: 从前向后遍历
    this.getNode(position).data = data;
    return true;
  }

  DoublyLinkedList.prototype.removeAt = function (position) {  
    if (position < 0 || position >= this.length) return false;
    this.removeNode(this.getNode(position));
  }

  DoublyLinkedList.prototype.remove = function (data) {
    let current = this.head;
    while (current !== null) {
      if (current.data === data) {
        this.removeNode(current);
      }
      current = current.next;
    }
  }

  DoublyLinkedList.prototype.removeNode = function (node) {  
    let data = node.data;
    let prev = node.prev;
    let next = node.next;
    // 判断当前节点的前驱指针是否为空，为空时，则当前节点为头节点
    if (prev === null) {
      this.head = next;
    } else {
      prev.next = next;
    }

    // 判断当前节点的后继指针是否为空，为空时，则当前节点为尾节点
    if (next === null) {
      this.tail = prev;
    } else {
      next.prev = prev;
    }
    // 上述两种情况已经包含链表长度为 1 的情况

    this.length--;
    return data;
  }

  DoublyLinkedList.prototype.size = function () {  
    return this.length;
  }

  DoublyLinkedList.prototype.isEmpty = function () {  
    return this.length === 0;
  }

  DoublyLinkedList.prototype.getHead = function () {  
    return this.head.data;
  }

  DoublyLinkedList.prototype.getTail = function () {  
    return this.tail.data;
  }
}

集合

数据结构(七)之集合结构

代码实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
function Set() {
  this.items = {};

  Set.prototype.has = function (value) {  
    return this.items.hasOwnProperty(value);
  }

  Set.prototype.add = function (value) {  
    if (this.has(value)) {
      return false;
    }

    this.items[value] = value;
    return true;
  }

  Set.prototype.remove = function (value) {  
    if (!this.has(value)) {
      return false;
    }

    delete this.items[value];
    return true;
  }

  Set.prototype.clear = function () {  
    this.items = {};
  }

  Set.prototype.size = function () {  
    return Object.keys(this.items).length;
  }

  Set.prototype.values = function () {  
    return Object.keys(this.items);
  }

  // 并集
  Set.prototype.union = function (otherSet) {  
    // this: 集合对象A
    // otherSet：集合对象B
    // 创建新的集合
    let unionSet = new Set();

    let values = this.values();
    // for (let i = 0; i < values.length; i++) {
    //   unionSet.add(values[i]);      
    // }
    values.forEach((item) => (unionSet.add(item)))

    values = otherSet.values();
    // for (let i = 0; i < values.length; i++) {
    //   unionSet.add(values[i]);
    // }
    values.forEach((item) => (unionSet.add(item)))

    return unionSet;
  }

  // 交集
  Set.prototype.intersection = function (otherSet) {  
    let intersectionSet = new Set();
    let values = this.values();

    // for (let i = 0; i < values.length; i++) {
    //   const item = values[i];
    //   if (otherSet.has(item)) {
    //     intersectionSet.add(item);
    //   }
    // }

    values.forEach((item) => {
      if (otherSet.has(item)) {
        intersectionSet.add(item);
      }
    })

    return intersectionSet ;
  }

  // 差集
  Set.prototype.difference = function (otherSet) {  
    let diffSet = new Set();
    let values = this.values();

    values.forEach((item) => {
      if (!otherSet.has(item)) {
        diffSet.add(item);
      }
    })

    return diffSet ;
  }

  // 判断是否为 Otherset 的子集
  Set.prototype.subset = function (otherSet) { 
    let values = this.values();
    for (let i = 0; i < values.length; i++) {
      const item = values[i];
      if (!otherSet.has(item)) {
        return false;
      }
    }
    return true;
  }
}

字典

数据结构(八)之字典结构

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function Dictionary() {
  this.items = {};

  Dictionary.prototype.set = function (key, value) {  
    this.items[key] = value;
  }

  Dictionary.prototype.has = function (key) {  
    return this.items.hasOwnProperty(key);
  }

  Dictionary.prototype.remove = function (key) {  
    if (!this.has(key)) {
      return false;
    }

    delete this.items[key];
    return true;
  }

  Dictionary.prototype.get = function (key) {  
    return this.has(key) ? this.items[key] : undefined;
  }

  Dictionary.prototype.update = function (key, value) {  
    if (!this.has(key)) {
      return false;
    }
    this.items[key] = value;
  }

  Dictionary.prototype.keys = function () {  
    return Object.keys(this.items);
  }

  Dictionary.prototype.values = function () {  
    return Object.values(this.items);
  }

  Dictionary.prototype.size = function () {  
    return this.keys().length;
  }

  Dictionary.prototype.isEmpty = function () {  
    return this.size() === 0;
  }

  Dictionary.prototype.clear = function () {  
    this.items = {};
  }
}

哈希表

数据结构(十)之哈希表实现

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
function HashTable() {
  // 属性
  this.storage = [];
  this.count = 0;
  this.limit = 7;
  // loadFactor(装载因子) > 0.75 要进行扩容
  
  // 哈希函数
  HashTable.prototype.hashFunc = function (str, size) {
    // 1、定义hashCode变量
    let hashCode = 0;
  
    // 2、霍纳算法，来计算hashCode的值
    // cats -> Unicode编码
    for (let i = 0; i < str.length; i++) {
      hashCode = 37 * hashCode + str.charCodeAt(i); // 幂一般要取质数，这里取37
    }
  
    // 3、取余操作
    let index = hashCode % size;
    return index;
  }

  // 插入&修改操作
  HashTable.prototype.put = function (key, value) {  
    // 1、根据 key 获取对应的 index
    let index = this.hashFunc(key, this.limit);

    // 2、根据 index 取出对应的 bucket（桶）
    let bucket = this.storage[index];

    // 3、判断该bucket是否为null
    if (bucket === null || bucket === undefined) {
      bucket = [];
      this.storage[index] = bucket;
    }

    // 4、判断是否为修改数据
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i];
      if (tuple[0] === key) {
        tuple[1] = value;
        return;
      }
    }

    // 5、进行添加操作
    bucket.push([key, value]);
    this.count++;

    // 6、判断是否需要扩容
    // loadFactor = count / limit, 如果loadFactor > 0.75，则需要扩容
    if (this.count > this.limit * 0.75) {
      let newSize = this.limit * 2;
      newSize = this.getPrime(newSize);
      this.resize();
    }
  }

  HashTable.prototype.get = function (key) {  
    let index = this.hashFunc(key, this.limit);

    let bucket = this.storage[index];

    if (bucket === null || bucket === undefined) {
      return null;
    }

    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) {
        return tuple[1];
      }
    }
    return null;
  }

  HashTable.prototype.remove = function (key) {  
    let index = this.hashFunc(key, this.limit);

    let bucket = this.storage[index];

    if (bucket === null || bucket === undefined) {
      return null;
    }

    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) {
        bucket.splice(i, 1);
        this.count--;

        // 判断是否需要缩容
        // loadFactor = count / limit, 如果loadFactor < 0.25，则需要缩容
        if (this.limit > 7 && this.count < this.limit * 0.25) {
          let newSize = Math.floor(this.limit / 2);
          newSize = this.getPrime(newSize);
          this.resize(newSize);
        }

        return tuple[1];
      }
    }
    return null;
  }

  HashTable.prototype.isEmpty = function () {  
    return this.count === 0;
  }

  HashTable.prototype.size = function () {  
    return this.count;
  }

  // 哈希表扩容/缩容
  HashTable.prototype.resize = function (newLimit) {  
    // 1、保存旧的数组内容
    let oldStorage = this.storage;

    // 2、重置属性
    this.storage = null;
    this.count = 0;
    this.limit = newLimit;

    // 3、遍历oldStorage所有的bucket
    for (let i = 0; i < oldStorage.length; i++) {
      // 3.1、取出对应的bucket
      let bucket = oldStorage[i];

      // 3.2、判断bucket是否为null
      if (bucket === null || bucket === undefined) {
        continue;
      }

      // 3.3、bucket中有数据，重新插入
      for (let j = 0; j < bucket.length; j++) {
        let tuple = bucket[i];
        this.put(tuple[0], tuple[1]);
      }
    }
  }

  // 判断是否为质数
  HashTable.prototype.isPrime = function (num) {  
    let temp = parseInt(Math.sqrt(num));
    for (let i = 2; i <= temp; i++) {
      if (num % i === 0) {
        return false;
      }
    }
    return true;
  }

  // 获取质数
  HashTable.prototype.getPrime = function (num) {  
    while (!this.isPrime(num)) {
      num++;
    }
    return num;
  }
}

二叉搜索树

数据结构(十一)之树结构

数据结构(十二)之二叉搜索树

数据结构(十三)之红黑树

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
function BinarySearchTree() {
  function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    // this.parent = null; // 找出某个节点的前驱或者后继节点时，会用到这个属性
  }
  this.root = null;

  // 插入
  BinarySearchTree.prototype.insert = function (key) {  
    let newNode = new Node(key);

    // 判断根节点是否为空，如果为空，则该节点直接当做为根节点，否则调用插入节点函数
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  // 插入节点
  BinarySearchTree.prototype.insertNode = function (node, newNode) {  
    // 新节点与当前节点进行比较
    if (newNode.key < node.key) {
      // 当前节点的左节点如果为空，则直接插入当前节点的左节点，否则继续递归
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 先根遍历
  BinarySearchTree.prototype.preOrderTraversal = function (handler) {  
    this.preOrderTraversalNode(this.root, handler);
  }

  BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {  
    if (node !== null) {
      handler(node.key);

      this.preOrderTraversalNode(node.left, handler);

      this.preOrderTraversalNode(node.right, handler);
    }
  }

  // 中根遍历
  BinarySearchTree.prototype.midOrderTraversal = function (handler) {  
    this.midOrderTraversalNode(this.root, handler);
  }

  BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {  
    if (node !== null) {
      this.midOrderTraversalNode(node.left, handler);

      handler(node.key);

      this.midOrderTraversalNode(node.right, handler);
    }
  }

  // 后根遍历
  BinarySearchTree.prototype.postOrderTraversal = function (handler) {  
    this.postOrderTraversalNode(this.root, handler);
  }

  BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {  
    if (node !== null) {
      this.postOrderTraversalNode(node.left, handler);

      this.postOrderTraversalNode(node.right, handler);

      handler(node.key);
    }
  }

  // 二叉树的最大值
  BinarySearchTree.prototype.max = function () {  
    let node = this.max(this.root);
    if (node !== null) {
      return node.key;
    }
    return null;
  }

  // 获取当前子树的最大节点
  BinarySearchTree.prototype.maxNode = function (node) {  
    while ((node !== null) && (ndoe.right !== null)) {
      node = node.right;
    }
    return node;
  }

  // 二叉树的最小值
  BinarySearchTree.prototype.min = function () {
    let node = this.min(this.root);
    if (node !== null) {
      return node.key;
    }
    return null;
  }

  // 当前子树的最小节点
  BinarySearchTree.prototype.minNode = function (node) {  
    while ((node !== null) && (node.left !== null)) {
      node = node.left;
    }
    return node;
  }



  // 搜索（此处用while循环实现，也可以递归实现）
  BinarySearchTree.prototype.search = function (key) {  
    let node = this.root;

    while (node !== null) {
      if (key < node.key) {
        node = node.left;
      } else if (key > node.key) {
        node = node.right;
      } else {
        return true;
      }
    }
    return false;
  }

  BinarySearchTree.prototype.remove = function (key) {  
    // 1、找到删除节点
    // 1.1、定义变量，保存一些信息
    let current = this.root;
    let parent = null;
    let isLeftChild = true;

    // 1.2、开始寻找节点
    while (current.key !== key) {
      parent = current;
      if (key < current.key) {
        isLeftChild = true;
        current = current.left;
      } else if (key > current.key) {
        isLeftChild = false;
        current = current.right;
      }

      if (current === null) {
        return false;
      }
    }

    // 2、根据对应情况删除节点
    // 2.1、删除的是叶子节点
    if (current.left === null && current.right === null) {
      if (current === this.root) {
        this.root = null;
      } else if (isLeftChild) {
        parent.left = null;
      } else {
        parent.right = null;
      }
    }

    // 只有一个左子树
    else if (current.right === null) {
      if (current === this.root) {
        current.left = null;
      } else if (isLeftChild) {
        parent.left = current.left;
      } else {
        parent.right = current.left;
      }
    }

    // 只有一个右子树
    else if (current.left === null) {
      if (current === this.root) {
        current.right = null;
      } else if (isLeftChild) {
        parent.left = current.right;
      } else {
        parent.right = current.right;
      }
    }

    // 有左右子树
    else {
      let successor = this.getSuccessor(current);
      if (current === this.root) {
        this.root = successor;
      } else if (isLeftChild) {
        parent.left = successor;
      } else {
        parent.right = successor;
      }

      successor.left = current.left;

      /* let precursor = this.getPrecursor(current);
      if (current === this.root) {
        this.root = precursor;
      } else if (isLeftChild) {
        parent.left = precursor;
      } else {
        parent.right = precursor;
      }

      precursor.right = current.right; */
      
    }

    return true;
  }


  // 获取后继节点并且调整后继节点的子节点(此函数并不是真正的获取后继节点的函数)
  BinarySearchTree.prototype.getSuccessor = function (delNode) {  
    // 保存临时节点
    let successorParent = delNode;
    let successor = delNode;
    let current = delNode.right;

    // 在delNode的右子树寻找后继节点，即寻找右子树的最小值
    while (current !== null) {
      successorParent = successor;
      successor = current;
      current = current.left;
    }

    // 后继节点不是删除节点的右节点时，则需要后继节点的父节点指向后继节点的右子树
    // 并且后继节点的right指向删除节点的右子树；
    // 后继节点是删除节点的右节点时，直接返回后继节点
    if (successor !== delNode.right) {
      successorParent.left = successor.right;
      successor.right = delNode.right;
    }

    return successor;
  }

  BinarySearchTree.prototype.getPrecursor = function (delNode) {  
    let precursorParent = delNode;
    let precursor = delNode;
    let current = delNode.left;

    // 寻找左子树的最大值
    while (current !== null) {
      precursorParent = precursor;
      precursor = current;
      current = current.right;
    }

    // 前驱节点不是删除节点的左节点时，则需要前驱节点的父节点指向前驱节点的左子树，
    // 并且前驱节点的left指向删除节点的左子树；
    // 前驱节点是删除节点的左节点时，直接返回前驱节点
    if (precursor !== delNode.left) {
      precursorParent.right = precursor.left;
      precursor.left = delNode.left;
    }
    return precursor;
  }
}

二叉树获取中序前驱节点和中序后继节点的方法：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function BinarySearchTree() {
  function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.parent = null; // 找出某个节点的前驱或者后继节点时，会用到这个属性
  }
  this.root = null;

  BinarySearchTree.prototype = {
    constructor: BinarySearchTree,

    // 当前子树的最小节点
    minNode: function (node) {  
      while ((node !== null) && (node.left !== null)) {
        node = node.left;
      }
      return node;
    },

    // 获取当前子树的最大节点
    maxNode: function (node) {  
      while ((node !== null) && (ndoe.right !== null)) {
        node = node.right;
      }
      return node;
    },

    // 获取当前节点的 中序后继节点，即大于当前结点的最小结点
    getSuccessor: function (node) {
      //如果当前结点有右子树，则返回当前结点右子树的最小结点
      if (node.right !== null) {
        return this.minNode(node.right);
      }

      //如果当前结点没有右子树，两种情况
      let parent = node.parent;
      //情况一，如果当前结点是其父结点的左孩子，则其后继结点为其父结点
      if ((parent !== null) && node === parent.left) {
        return parent;
      }
      //情况二，如果当前结点是其父结点的右孩子，则其后继结点为其最近的有左子树的父结点
      //可以一直向上寻找其父结点，直到找到结点P，P是其父结点Q的左孩子
      //结点Q即为当前结点的后继结点
      while ((parent !== null) && (node === parent.right)) {
        node = parent;
        parent = parent.parent;
      }
      return parent;
    },

    //返回直接前驱结点，即小于当前结点的最大结点
    predecessor: function(node) {
      //如果当前结点有左子树，则返回当前结点左子树的最大结点
      if (node.left !== null) {
        return maxNode(node.left);
      }
      //如果当前结点没有左子树，两种情况
      let parent = node.parent;
      //情况一，如果当前结点是其父结点的右孩子，则其前驱结点为其父结点
      if ((parent !== null) && node === parent.right) {
        return parent;
      }
      //情况二，如果当前结点是其父结点的左孩子，则其前驱结点为其最近的有右子树的父结点
      //可以一直向上寻找其父结点，直到找到结点P，P是其父结点Q的右孩子
      //结点Q即为当前结点的前驱结点
      while ((parent !== null) && (node === parent.left)) {
        node = parent;
        parent = parent.parent;
      }
      return parent;
    }
  }
}

二叉堆

数据结构_二叉堆

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
  最小二叉堆
*/

function MinHeap() {
  this.heap = [];
}

MinHeap.prototype = {
  constructor: MinHeap,

  size: function () {  
    return this.heap.length
  },

  // 插入
  insert: function (objectData) {  
    this.heap.push(objectData);
    // 堆上浮自调整
    this.siftUp(this.size() - 1)
  },

  // 删除结点
  remove: function (objectData) {  
    // 空堆返回-1
    if (!this.heap.length) return -1;
    // 获取 objectData 的索引
    let index = this.heap.indexOf(objectData);
    if (index === -1) return -1;

    //将最后的结点补到被删的结点处
    //实现为将最后的结点赋值覆盖被删的结点，再删除最后的结点
    this.heap[index] = this.heap[this.size() - 1];
    this.heap.pop();
    
    //堆中至少有两个结点才需要自调整下沉
    if (this.size() > 1) {
      this.siftDown(index, this.size() - 1);
    }

    // 返回删除的数据
    return objectData;
  },

  print: function () {  
    let str = '';
    for (let i = 0; i < this.size(); i++) {
      str += `${this.heap[i]} `;
    }
    console.log(str);
    
  },

  // 结点上浮
  siftUp: function (nodeIndex) {
    let parentIndex = Math.floor((nodeIndex - 1) / 2);
    let temp = this.heap[nodeIndex];

    while (nodeIndex > 0) {
      // 父结点的权重是否大于子结点的权重
      let isLarger = this.heap[parentIndex].priority > temp.priority;
      if (isLarger) {
        this.heap[nodeIndex] = this.heap[parentIndex];
        nodeIndex = parentIndex;
        parentIndex = Math.floor((parentIndex - 1) / 2);
      } else break;
    }

    this.heap[nodeIndex] = temp;
  },

  // 结点下沉
  siftDown: function (nodeIndex, lastIndex) {
    let childIndex = 2 * nodeIndex + 1;
    let temp = this.heap[nodeIndex];
    while (childIndex <= lastIndex) {
      // childIndex + 1 <= lastIndex 判断右孩子有没有超出边界，超出的话不会执行 && 后面的语句
      // 如果右孩子没有超出边界，则判断左孩子权重是否比右孩子权重大
      if (childIndex + 1 <= lastIndex && (this.heap[childIndex].priority > this.heap[childIndex + 1].priority)) {
        childIndex++;
      }
      // 判断当前结点是否比子结点大
      isLarger = temp.priority > this.heap[childIndex].priority;
      if (isLarger) {
        this.heap[nodeIndex] = this.heap[childIndex];
        nodeIndex = childIndex;
        childIndex = 2 * childIndex + 1;
      } else {
        break;
      }
    }
    this.heap[nodeIndex] = temp;
  },
}

let heap = new MinHeap();
let test = [7, 1, 3, 10, 5, 2, 8, 9, 6];
test.forEach(i => heap.insert(i));
// heap.heapify([7, 1, 3, 10, 5, 2, 8, 9, 6])
heap.print();  //1 5 2 6 7 3 8 10 9
heap.remove(1);

heap.print();  //2 5 3 6 7 9 8 10

图

数据结构(十四)之图结构

数据结构(十五)之图算法

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
let Dictionary = require('./Dictionary');
let Queue = require('./Queue');
// 图结构
function Graph() {
  // 属性：顶点（数组）/ 边（字典）
  this.vertexes = [];
  this.edges = new Dictionary();

  // 添加顶点
  Graph.prototype.addVertex = function (v) {  
    this.vertexes.push(v);
    this.edges.set(v, []);
  }

  // 添加边
  Graph.prototype.addEdge = function (v1, v2) {  
    this.edges.get(v1).push(v2);
    this.edges.get(v2).push(v1);
  }

  Graph.prototype.toString = function () {  
    let resultString = '';

    for (let i = 0; i < this.vertexes.length; i++) {
      resultString += this.vertexes[i] + ' -> ';
      let vEdges = this.edges.get(this.vertexes[i]);
      for (let j = 0; j < vEdges.length; j++) {
        resultString += vEdges[j] + ' ';
      }
      resultString += '\n';
    }

    return resultString;
  }

  // 初始化状态颜色
  Graph.prototype.initColor = function () {  
    let colors = [];
    this.vertexes.forEach((item) => (colors[item] = 'white'));
    return colors;
  }

  // 广度优先搜索（BFS：Breadth-First Search）
  Graph.prototype.bfs = function (initV, handler) {  
    // 1、初始状态颜色
    let colors = this.initColor();

    // 2、创建队列
    let queue = new Queue();

    // 3、将定点加入队列
    queue.enqueue(initV);

    // 4、循环获取队列中的顶点
    while (!queue.isEmpty()) {
      // 4.1、获取队列中的一个顶点
      let v = queue.dequeue();

      // 4.2、获取和v顶点相连的其他顶点
      let vList = this.edges.get(v);

      // 4.3、将v顶点设置成灰色，表示已经被访问过了
      colors[v] = 'gray';

      // 4.4、遍历与v顶点相连的其他顶点，并加入队列中
      for (let i = 0; i < vList.length; i++) {
        let e = vList[i];

        // 只有状态颜色为白色的顶点才要加入队列中，即未被访问过的顶点
        if (colors[e] === 'white') {
          colors[e] = 'gray';
          queue.enqueue(e);
        }
      }

      // 4.5、处理v顶点
      handler(v);

      // 4.6、探索过的顶点v的状态颜色设置为黑色
      colors[v] = 'black';
    }
  }

  // 深度优先搜索（DFS：Depth-First Search）
  Graph.prototype.dfs = function (initV, handler) {  
    let colors = this.initColor();
    this.dfsVisit(initV, colors, handler);
  }

  Graph.prototype.dfsVisit = function (v, colors, handler) {  
    colors[v] = 'gray';
    handler(v);
    let vList = this.edges.get(v);

    for (let i = 0; i < vList.length; i++) {
      let e = vList[i];
      if (colors[e] === 'white') {
        this.dfsVisit(e, colors, handler);
      }
    }

    colors[v] = 'black';
  }
}

let graph = new Graph();
// 添加顶点
var myVertexes = ["A", "B", "C", "D", "E", "F", "G", "H", "I"]
myVertexes.forEach((item) => (graph.addVertex(item)))

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

let str = ''
graph.bfs('A', function (v) {  
  str += v + ' ';
})
-------文章到此结束  感谢您的阅读-------