数据结构与算法

数据结构与算法

数组

数组方法大全

数组解构赋值应用
1
2
3
4
5
6
// 交换变量
[a, b] = [b, a]
[o.a, o.b] = [o.b, o.a]
// 生成剩余数组
const [a, ...rest] = [...'asdf'] // a：'a'，rest: ["s", "d", "f"]
复制代码
数组浅拷贝
1
2
3
4
5
6
const arr = [1, 2, 3]
const arrClone = [...arr]
// 对象也可以这样浅拷贝
const obj = { a: 1 }
const objClone = { ...obj }
复制代码

浅拷贝方法有很多如arr.slice(0, arr.length)/Arror.from(arr)等，但是用了...操作符之后就不会再想用其他的了~

数组合并
1
2
3
4
5
const arr1 = [1, 2, 3]
const arr2 = [4, 5, 6]
const arr3 = [7, 8, 9]
const arr = [...arr1, ...arr2, ...arr3]
复制代码

arr1.concat(arr2, arr3)同样可以实现合并，但是用了...操作符之后就不会再想用其他的了~

数组去重
1
2
3
const arr = [1, 1, 2, 2, 3, 4, 5, 5]
const newArr = [...new Set(arr)]
复制代码

new Set(arr)接受一个数组参数并生成一个set结构的数据类型。set数据类型的元素不会重复且是Array Iterator，所以可以利用这个特性来去重。

数组取交集
1
2
3
4
5
const a = [0, 1, 2, 3, 4, 5]
const b = [3, 4, 5, 6, 7, 8]
const duplicatedValues = [...new Set(a)].filter(item => b.includes(item))
duplicatedValues // [3, 4, 5]
复制代码
数组取差集
1
2
3
4
const a = [0, 1, 2, 3, 4, 5]
const b = [3, 4, 5, 6, 7, 8]
const diffValues = [...new Set([...a, ...b])].filter(item => !b.includes(item) || !a.includes(item)) // [0, 1, 2, 6, 7, 8]
复制代码
数组转对象
1
2
3
4
5
6
7
8
const arr = [1, 2, 3, 4]
const newObj = {...arr} // {0: 1, 1: 2, 2: 3, 3: 4}
const obj = {0: 0, 1: 1, 2: 2, length: 3}
// 对象转数组不能用展开操作符，因为展开操作符必须用在可迭代对象上
let newArr = [...obj] // Uncaught TypeError: object is not iterable...
// 可以使用Array.form()将类数组对象转为数组
let newArr = Array.from(obj) // [0, 1, 2]
复制代码
数组摊平
1
2
3
4
5
6
7
const obj = {a: '群主', b: '男群友', c: '女裙友', d: '未知性别'}
const getName = function (item) { return item.includes('群')}
// 方法1
const flatArr = Object.values(obj).flat().filter(item => getName(item))
// 经大佬指点，更加简化（发现自己的抽象能力真的差~）
const flatArr = Object.values(obj).flat().filter(getName)
复制代码

二维数组用array.flat()，三维及以上用array.flatMap()。

数组常用遍历

数组常用遍历有 forEach、every、some、filter、map、reduce、reduceRight、find、findIndex 等方法，很多方法都可以达到同样的效果。数组方法不仅要会用，而且要用好。要用好就要知道什么时候用什么方法。

遍历的混合使用

filter、map方法返回值仍旧是一个数组，所以可以搭配其他数组遍历方法混合使用。注意遍历越多效率越低~

1
2
3
4
5
6
const arr = [1, 2, 3, 4, 5]
const value = arr
    .map(item => item * 3)
    .filter(item => item % 2 === 0)
    .map(item => item + 1)
    .reduce((prev, curr) => prev + curr, 0)
检测数组所有元素是否都符合判断条件
1
2
const arr = [1, 2, 3, 4, 5]
const isAllNum = arr.every(item => typeof item === 'number')
检测数组是否有元素符合判断条件
1
2
const arr = [1, 2, 3, 4, 5]
const hasNum = arr.some(item => typeof item === 'number')
找到第一个符合条件的元素/下标
1
2
3
4
5
6
7
8
9
10
const arr = [1, 2, 3, 4, 5]
const findItem = arr.find(item => item === 3) // 返回子项
const findIndex = arr.findIndex(item => item === 3) // 返回子项的下标

let findIndex
arr.find((item, index) => {
    if (item === 3) {
        findIndex = index
    }
})
数组使用误区

数组的方法很多，很多方法都可以达到同样的效果，所以在使用时要根据需求使用合适的方法。

垃圾代码产生的很大原因就是数组常用方法使用不当，这里有以下需要注意的点：

array.includes() 和 array.indexOf()

array.includes() 返回布尔值，array.indexOf() 返回数组子项的索引。indexOf 一定要在需要索引值的情况下使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const arr = [1, 2, 3, 4, 5]

// 使用indexOf，需要用到索引值
const index = arr.indexOf(1) // 0
if (~index) { // 若index === -1，~index得到0，判断不成立；若index不为-1，则~index得到非0，判断成立。
    arr.spilce(index, 1)
}

// 使用includes，不需要用到索引值
// 此时若用indexOf会造成上下文上的阅读负担：到底其他地方有没有用到这个index?
const isExist = arr.includes(6) // true
if (!isExist) {
    arr.push(6)
}

另外评论区大佬指出，array.indexOf()找 NaN 会找不到，返回-1，array.includes()能找到，返回true~

1
2
[NaN].includes(NaN) // true
[NaN].indexOf(NaN) // -1

array.find() 、 array.findIndex() 和 array.some()

array.find()返回值是第一个符合条件的数组子项，array.findIndex() 返回第一个符合条件的数组子项的下标，array.some() 返回有无复合条件的子项，如有返回true，若无返回false。注意这三个都是短路操作，即找到符合条件的之后就不在继续遍历。

在需要数组的子项的时候使用array.find() ；需要子项的索引值的时候使用 array.findIndex() ；而若只需要知道有无符合条件的子项，则用 array.some()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const arr = [{label: '男', value: 0}, {label: '女', value: 1}, {label: '不男不女', value: 2}]

// 使用some
const isExist = arr.some(item => item.value === 2)
if (isExist) {
    console.log('哈哈哈找到了')
}

// 使用find
const item = arr.find(item => item.value === 2)
if (item) {
    console.log(item.label)
}

// 使用findIndex
const index = arr.findIndex(item => item.value === 2)
if (~index) {
    const delItem = arr[index]
    arr.splice(index, 1)
    console.log(`你删除了${delItem.label}`)
}

建议在只需要布尔值的时候和数组子项是字符串或数字的时候使用 array.some()：

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
// 当子包含数字0的时候可能出错
const arr = [0, 1, 2, 3, 4]

// 正确
const isExist = arr.some(item => item === 0)
if (isExist) {
    console.log('存在要找的子项，很舒服~')
}

// 错误
const isExist = arr.find(item => item === 0)
if (isExist) { // isExist此时是0，隐式转换为布尔值后是false
    console.log('执行不到这里~')
}


// 当子项包含空字符串的时候也可能出错
const arr = ['', 'asdf', 'qwer', '...']

// 正确
const isExist = arr.some(item => item === '')
if (isExist) {
    console.log('存在要找的子项，很舒服~')
}

// 错误
const isExist = arr.find(item => item === '')
if (isExist) { // isExist此时是''，隐式转换为布尔值后是false
    console.log('执行不到这里~')
}

array.find() 和 array.filter()

只需要知道 array.filter() 返回的是所有符合条件的子项组成的数组，会遍历所有数组；而 array.find() 只返回第一个符合条件的子项，是短路操作。

合理使用 Set 数据结构

由于 es6 原生提供了 Set 数据结构，而 Set 可以保证子项不重复，且和数组转换十分方便，所以在一些可能会涉及重复添加的场景下可以直接使用 Set 代替 Array，避免了多个地方重复判断是否已经存在该子项。

1
2
3
4
5
6
const set = new Set()
set.add(1)
set.add(1)
set.add(1)
set.size // 1
const arr = [...set] // arr: [1]
强大的reduce

array.reduce 遍历并将当前次回调函数的返回值作为下一次回调函数执行的第一个参数。

利用 array.reduce 替代一些需要多次遍历的场景，可以极大提高代码运行效率。

  1. 利用reduce 输出一个数字/字符串

假如有如下每个元素都由字母’s’加数字组成的数组arr，现在找出其中最大的数字：（arr不为空）

1
2
3
4
5
6
7
8
9
10
11
const arr = ['s0', 's4', 's1', 's2', 's8', 's3']

// 方法1  进行了多次遍历，低效
const newArr = arr.map(item => item.substring(1)).map(item => Number(item))
const maxS = Math.max(...newArr)

// 方法2  一次遍历
const maxS = arr.reduce((prev, cur) => {
  const curIndex = Number(cur.replace('s', ''))
  return curIndex > prev ? curIndex : prev
}, 0)
  1. 利用reduce 输出一个数组/对象
1
2
3
4
5
6
7
8
9
const arr = [1, 2, 3, 4, 5]

 // 方法1  遍历了两次，效率低
const value = arr.filter(item => item % 2 === 0).map(item => ({ value: item }))

// 方法1  一次遍历，效率高
const value = arr.reduce((prev, curr) => {
    return curr % 2 === 0 ? [...prev, curr] : prev
}, [])

掌握了上面两种用法，结合实际需要，就可以用 reduce/reduceRight 实现各种奇巧淫技了。

实例：利用 reduce 做下面这样的处理来生成想要的 html 字符串：

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
// 后端返回数据
const data = {
  'if _ then s9': [
    '作用属于各种,结构属于住宅,结构能承受作用,作用属于在正常建造和正常使用过程中可能发生',
    '作用属于各种,结构属于住宅,结构能承受作用,作用属于在正常建造和正常使用过程中可能发生',
    '作用属于各种,结构属于住宅,结构能承受作用,作用属于在正常建造和正常使用过程中可能发生'
    ],
  'if C then s4': [
    '当有条件时时,结构构件满足要求,要求属于安全性、适用性和耐久性',
    '当有条件时时,住宅结构满足要求,要求属于安全性、适用性和耐久性'
  ]
}

const ifthens = Object.entries(data).reduce((prev, cur) => {
  const values = cur[1].reduce((prev, cur) => `${prev}<p>${cur}</p>`, '')
  return `
    ${prev}
    <li>
      <p>${cur[0]}</p>
      ${values}
    </li>
  `
}, '')

const html = `
  <ul class="nlp-notify-body">
    ${ifthens}
  </ul>
`

生成的 html 结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
<ul class="nlp-notify-body">            
  <li>
    <p>if _ then s9</p>
    <p>作用属于各种,结构属于住宅,结构能承受作用,作用属于在正常建造和正常使用过程中可能发生</p>
    <p>作用属于各种,结构属于住宅,结构能承受作用,作用属于在正常建造和正常使用过程中可能发生</p>
    <p>作用属于各种,结构属于住宅,结构能承受作用,作用属于在正常建造和正常使用过程中可能发生</p>
  </li>
  <li>
    <p>if C then s4</p>
    <p>当有条件时时,结构构件满足要求,要求属于安全性、适用性和耐久性</p>
    <p>当有条件时时,住宅结构满足要求,要求属于安全性、适用性和耐久性</p>
  </li>
</ul>

这里还有一个替代 reverse 函数的技巧

由于 array.reverse() 函数会改变原数组自身，这样就限制了一些使用场景。如果我想要一个不会改变数组自身的 reverse 函数呢？拿走！

1
2
3
const myReverse = (arr = []) => {
    return  arr.reduceRight((prev, cur) => [...prev, cur], []) // 也可以返回逗号表达式 (prev.push(cur), prev)
}

栈

用JavaScript封装栈
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
// 封装栈
   function Stack(){
       // 栈中的属性
       this.items = [];
       // 栈中的相关操作
       // 1.将元素压入栈中
       Stack.prototype.push = function(element){
		this.items.push(element);
       };
       // 2.将元素弹出栈中
       Stack.prototype.pop = function(){
		return	this.items.pop();
       };
       // 3.查看一下栈顶元素
       Stack.prototype.check = function(){
		return this.items[this.items.length - 1];
       };
       // 4.判断栈中是否有元素
       Stack.prototype.isEmpty = function(){
		return this.items.length == 0;
       };
       // 5.获取栈中的元素的个数
       Stack.prototype.size = function(){
		return this.items.length;
       };
       // 6.toString方法
       Stack.prototype.toString = function(){
           // 方法一：
           // var resultString = '';
           // for(var i = 0; i < this.items.length; i ++){
           // 	resultString += this.items[i] + ' ';
           // }
           // return resultString;
           // 方法二：
           return this.items.join(' ');
       };
   }

之所以不使用this.push=function(){}，而是采用原型的方法，是因为通过prototype原型的方法相当于给整个类添加了方法，而this.push方式则仅是给某个实例添加方法。

用栈将十进制转为二进制
  • 因为我们习惯使用十进制，而计算机里面的所有内容都是用二进制数字表示的（0和1）
  • 可采用对十进制的数字进行除二取余法，将十进制转为二进制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//函数：将十进制转为二进制
function dec2bin(decNumber){
    // 1.定义栈对象
    var stack = new Stack();
    while(decNumber > 0){
        stack.push(decNumber % 2);
        decNumber = Math.floor(decNumber / 2);
        console.log(decNumber)
    }
    var binaryString = '';
    while(!stack.isEmpty()){
        binaryString += stack.pop();
    }
    return binaryString;
}

队列

队列结构

  • 队列是一种受限的数据结构，可解决某些特定的问题。它的受限之处在于他只允许在表的前端（font）进行删除操作，而在表的后端（rear）进行插入操作。

  • 队列的实现和栈一样有两种方案：

    • 基于数组实现
    • 基于链表实现

  • 队列常见的操作

    • enqueue(element)：向队列尾部添加一个或多个新的项。
    • dequeue（）：移除队列的第一（即排在队列最前面的）项，并返回移除的元素；
    • front（）：返回队列中第一个元素。
    • isEmpty（）：判断队列中是否含有元素。
    • size（）：返回队列中的元素个数。
    • toString（）：将队列中的内容转为字符串形式
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
// 用数组封装队列
function Queue(){
this.item = [];

// 1.添加元素
Queue.prototype.enqueue = function(element){
    this.item.push(element);

};
// 2.移除元素
Queue.prototype.dequeue = function(){
    return this.item.shift();
};
// 3.查看队列中第一个元素
Queue.prototype.front = function(){
    return this.item[0];
};
// 4.判断元素是否为空
Queue.prototype.isEmpty = function(){
    return this.item.length == 0;
};
// 5.队列中的元素个数
Queue.prototype.size = function(){
    return this.item.length;
};
// 6.将队列中的内容转为字符串
Queue.prototype.toString = function(){
    return this.item.join(' ');
}
队列击鼓传花
  • 参数：所有参与人的性名，基于此的数字
  • 结果：最终剩下的一人的姓名
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
 // 击鼓传花
    function passGame(nameList, num) {
        //创建一个队列
        var queue = new Queue();
        // 将所有人加入队列中
        for(var i = 0; i < nameList.length; i++){
            queue.enqueue(nameList[i]);
        }
        // 不是num，重新加入队列末尾
        // 是num时，从队列中删除并把不是num的值重新放入队列中
        // 当队列中只剩下一人退出循环
        while (queue.size() > 1) {
            for (var i = 0; i < num - 1; i++) {
                queue.enqueue(queue.dequeue());
            }
            queue.dequeue();
        }
        var index = nameList.indexOf(queue.front());
        return queue.front();
    }// 击鼓传花
function passGame(nameList, num) {
    //创建一个队列
    var queue = new Queue();
    // 将所有人加入队列中
    for(var i = 0; i < nameList.length; i++){
        queue.enqueue(nameList[i]);
    }
    // 不是num，重新加入队列末尾
    // 是num时，从队列中删除并把不是num的值重新放入队列中
    // 当队列中只剩下一人退出循环
    while (queue.size() > 1) {
        for (var i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue());
        }
        queue.dequeue();
    }
    var index = nameList.indexOf(queue.front());
    return queue.front();
}
优先级队列
  • 普通的队列插入一个元素，数据就会被放入后端，并且需要前面的所有元素处理完后才会处理前面的数据。但是优先级队列，在插入一个元素的的时候会考虑该数据的优先级。
  • 和其他数据优先级进行比较，比较完成后可得出这个元素在队列中正确的位置。
  • 优先级队列主要考虑的问题：
    • 每个元素不再只是一个数据，且包含数据的优先级。
    • 在添加方式中，根据优先级放入正确的位置。
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
// 封装优先级队列
function PriorityQueue() {
    // 内部类
    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    // 封装属性
    this.item = [];
    // 实现插入方法
    PriorityQueue.prototype.enqueue = function (element, priority) {
        // 创建QueueElement对象
        var queueElement = new QueueElement(element, priority);
        if (this.item.length == 0) {
            this.item.push(queueElement);
        } else {
            let flag = false;
            for (let i = 0; i < this.item.length; i++) {
                if (queueElement.priority < this.item[i].priority) {
                    this.item.splice(i, 0, queueElement);
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                this.item.push(queueElement);
            }
        }
    }
    // 2.移除元素
    PriorityQueue.prototype.dequeue = function () {
        return this.item.shift();
    };
    // 3.查看队列中第一个元素
    PriorityQueue.prototype.front = function () {
        return this.item[0];
    };
    // 4.判断元素是否为空
    PriorityQueue.prototype.isEmpty = function () {
        return this.item.length == 0;
    };
    // 5.队列中的元素个数
    PriorityQueue.prototype.size = function () {
        return this.item.length;
    };
    // 6.将队列中的内容转为字符串
    PriorityQueue.prototype.toString = function () {
       let result = '';
       for(let i = 0; i < this.item.length; i++){
           result += this.item[i].priority + ' ' + this.item[i].element + ' ';
       }
       return result;
    }
}
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue('nikita',10);
priorityQueue.enqueue('nikita1',110);
priorityQueue.enqueue('nikit2a',101);
priorityQueue.enqueue('nikitak',210);
console.log(priorityQueue.toString());

链表

单向链表

要存储多个元素，有两个选择：数组和链表。

但不同于数组，链表中的元素在内存中不必是连续的空间，链表的每一个元素由一个存储元素本身的节点和指向下一个元素的引用（即指针）组成。

相对于数组，链表优势：

  1. 内存不必连续，可充分利用计算机的内存，实现灵活的内存动态管理。
  2. 链表不必在创建时就确定大小，并且大小可以无限的延伸下去。
  3. 链表在插入和删除操作时，时间复杂度可达O（1），相对数组效率高很多。

劣势：

  1. 链表访问任何一个位置的元素都必须从头开始。（无法跳过第一个元素访问任何一个元素）。
  2. 无法通过下标直接访问元素，必须从头开始，直到找到元素。

![1 (3)](C:\Users\CCY\Desktop\1 (3).png)

常见操作：

  1. append（element）：向链表尾部添加一个新的项。
  2. insert（position,element）：向特定位置添加一个项
  3. get（position）
  4. indexOf（element）
  5. update（position）：修改某个位置的元素
  6. removeAt（position）
  7. remove（element）
  8. isEmpty()
  9. size()
  10. toString()
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
![4](C:\Users\CCY\Desktop\4.png)// 封装单向链表
function LinkedList(){
    // 内部类，节点类
    function Node(data){
        this.data = data;
        this.next = null;
    }
    // 定义属性
    this.head = null;
    this.length = 0;

    // 追加append方法
    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;
        }
        
        this.length++;
    }

    // toString方法
    LinkedList.prototype.toString = function(){
        let resultString = '';
        let current = this.head;
        while(current){
            resultString += current.data + ' ';
            current = current.next;
        }
        return resultString;
    }

    // 在任意位置加元素
    LinkedList.prototype.insert = function(position,data){
        // 对position进行边界判断
        if(position < 0 || position > this.length){
            return false;
        }else{
            let newNode = new Node(data);
            let index = 0;
            let previous = null;
            let current = this.head;
            while(index++ < position){
                previous = current;
                current = current.next;
            }
            previous.next = newNode;
            newNode.next = current;
        }
        this.length++;
        return true;
    }

    // 获取对应位置的值
    LinkedList.prototype.get = function(position){
        // 对position边界判断
        if(position < 0 || position >= this.length){
            return null;
        }else{
            let current = this.head;
            let index = 0;
            while(index++ < position){
                current = current.next;
            }
            return current.data;
        }
    }

    // 返回元素索引值indexOf，没有返回-1
    LinkedList.prototype.indexOf = function(value){
        let current = this.head;
        let index = 0;
        while(current){
            if(current.data == value){
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    }

    // update方法
    LinkedList.prototype.update = function(position,value){
        // 对position边界判断
        if(position < 0 || position >= this.length){
            return false;
        }else{
            let current = this.head;
            let index = 0;
            while(index++ < position){
                current = current.next;
            }
            current.data = value;
            return true;
        }
    }

    // 在特定位置删除数据
    LinkedList.prototype.removeAt = function(position){
        // 方便后续返回里面的值
        let current = this.head;
        // 对position边界判断
        if(position < 0 || position >= this.length){
            return false;
        }else{
            let index = 0;
            let previous = null;
            while(index++ < position){
                previous = current;
                current = current.next;
            }
            current.next = previous.next;
        }
        this.length -= 1;
        return current.data;
    }

    // 在列表中删除某个值
    LinkedList.prototype.remove = function(value){
        // 获取data在列表中的位置
        let position = this.indexOf(value);

        return this.removeAt(position);
    }

    // 是否为空
    LinkedList.prototype.isEmpty = function(){
        return !this.length;
    }

    // 元素个数
    LinkedList.prototype.size = function(){
        return this.length;
    }
}
双向链表

既可以从头遍历到尾，又可以从尾遍历到头。

实现原理是：一个节点既有向前连接的引用，也有一个向后连接的引用。

但有以下缺点：

每次插入删除某个节点时，需要处理四个引用，而不是两个，也就是实现起来更困难一些。并且相当于单向链表，必然占用内存空间更大些。4

特点：

  1. 可以使用一个head和一个tail分别指向头部和尾部的节点。
  2. 每个节点由三部分组成：前一个节点的指针（prev）/保存的元素（item）/后一个节点的指针（next）。
  3. 双向链表的第一个节点的prev是null，最后一个节点的next为null。
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
// 封装双向链表
function DoubleLinkedList(){
    // 内部节点类
    function Node(data){
        this.data = data;
        this.prev = null;
        this.next = null;
    }

    // 内部属性
    this.head = null;
    this.tail = null;
    this.length = 0;

    // append追加方法
    DoubleLinkedList.prototype.append = function(data){
        let newNode = new Node(data);
        if(this.length == 0){
            this.head = newNode;
            this.tail = newNode;
        }else{
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }

    // 任意位置插入值
    DoubleLinkedList.prototype.insert = function(position,value){
        if(position < 0 || position >= this.length) return false;
        let newNode = new Node(value);
        // 原链表为空
        if(this.length == 0){
            this.prev = newNode;
            this.tail = newNode;
        }else if(position == 0){
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }else if(position == this.length){
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }else{
            let index = 0;
            let current = this.head;
            while(index++ < position){
                current = current.next;
            }
            newNode.next = current;
            newNode.prev = current.prev;
            current.prev.next = newNode;
            current.prev = newNode;
        }

        this.length++;
    }

    // get方法
    DoubleLinkedList.prototype.get = function(position){
        if(position < 0 || position >= this.length) return null;
        let index = 0;
        let current = this.head;
        while(index++ < position){
            current = current.next;
        }
        return current.data;
    }

    // indexOf方法
    DoubleLinkedList.prototype.indexOf = function(value){
        let index = 0;
        let current = this.head;
        while(current){
            if(current.data == value){
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }
    
    // update方法
    DoubleLinkedList.prototype.update = function(position,newValue){
        if(position < 0 || position >= this.length) return false;
        let current = this.head;
        let index = 0;
        while(index++ < position){
            current = current.next;
        }
        current.data = newValue;
        return true;
    }

    // 移除数据
    DoubleLinkedList.prototype.removeAt = function(position){
        if(position < 0 || position >= this.length) return null;
        let current = this.head;
        if(position == 0){
            this.head.next.prev = null;
            this.head = this.head.next;
        }else if(position == this.length - 1){
            current = this.tail;
            this.tail.prev.next = null;
            this.tail = this.tail.prev;
        }else{
            let index = 0;
            while(index++ < position){
                current = current.next;
            }
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
        this.length -= 1;
        return current.data;
    }

    // remove方法
    DoubleLinkedList.prototype.remove = function(value){
        let position = this.indexOf(value);
        return this.removeAt(position);
    }

    // isEmpty方法
    DoubleLinkedList.prototype.isEmpty = function(){
        return !this.length;
    }

    // size方法
    DoubleLinkedList.prototype.size = function(){
        return this.length;
    }

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

    DoubleLinkedList.prototype.getTail = function(){
        return this.tail.data;
    }
    // 将链表转成字符串
    DoubleLinkedList.prototype.toString = function(){
        return this.backwardString();
    }

    DoubleLinkedList.prototype.forwardString = function(){
        let current = this.tail;
        let resultString = '';
        while(current){
            resultString += current.data + ' ';
            current = current.prev;
        }
        return resultString;
    }

    // 从前向后遍历
    DoubleLinkedList.prototype.backwardString = function(){
        let current = this.head;
        let resultString = '';
        while(current){
            resultString += current.data + ' ';
            current = current.next;
        }
        return resultString;
    }
}

集合

几乎每种编程语言中，都有集合结构，比较常见的实现方式是哈希表。

集合通常是由一组无序的，不能重复的元素组成与数学中的集合不同，计算机中的集合表示的结构中元素是不允许重复的。ES6中的Set类就是一种集合类。

集合常见操作：
  1. add（value）向集合添加一个新的项。
  2. remove（value）：从集合中一个数
  3. has（value）：值是否在集合中，有返回true，没有返回false
  4. clear（）：移除集合所有项。
  5. size（）：length属性
  6. values（）：返回所有值的数组。
集合间的操作

并集

交集

差集

子集

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
// 封装集合
function Set(){
    // 属性
    this.item = {};

    // add方法
    Set.prototype.add = function(value){
        // 先判断是否有该值
        if(this.has(value)){
            return false;
        }

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

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

    Set.prototype.remove = function(value){
        // 判断有无该值
        if(!this.has(value)){
            return false;
        }
        delete this.item[value];
        return true;
    }

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

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

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

    // 并集
    Set.prototype.union = function(otherSet){
        // this: 集合对象A
        // otherSet：集合对象B
        let unionSet = new Set();
        let value = this.values();
        for(let i = 0; i < value.length;i++){
            unionSet.add(value[i])
        }
        // 去除B集合中的元素，判断是否需要添加到新的集合
        value = otherSet.values();
        for(let i = 0; i < value.length;i++){
            unionSet.add(value[i]);
        }
        return unionSet;
    }

    // 交集
    Set.prototype.intersection = function(otherSet){
        let intersection = new Set();
        let value = this.values();
        for(let i = 0; i < value.length;i++){
            if(otherSet.has(value[i])){
                intersection.add(value[i]);
            }
        }
        return intersection;
    }

    // 差集
    Set.prototype.differce = function(otherSet){
        let differce = new Set();
        let value = this.values();
        for(let i = 0; i < value.length;i++){
            if(!otherSet.has(value[i])){
                differce.add(value[i]);
            }
        }
        return differce;
    }

    // 子集：集合A是否为集合B的子集
    Set.prototype.subSet = function(otherSet){
        let value = this.values();
        for(let i = 0; i < value.length;i++){
            if(!otherSet.has(value[i])){
                return false;
            }
        }
        return true;
    }

}

哈希表

哈希表无论多少条数据，插入删除值需要接近常量的时间：即O（1）的时间级。实际上，只需要几个机器指令即可完成。

哈希表的速度比树快，基本可在瞬间找到想要的元素，且哈希表相对于树来说编码要容易得多。哈希表基于数组，但效率比数组高。

哈希表相对于数组：

  1. 哈希表中的数据没有顺序，所以不能以一种固定的方式，比如从小到大来遍历其中的元素。
  2. 哈希表中的key不允许重复，不能放置相同的key用于保存不同的元素。
字母转数字

方案一：把数字相加求和产生的数组下标太少。

方案二：与27的幂相乘求和产生的数组下标又太多。

哈希化

哈希化：将大数字转化为数组范围内下标的过程，我们称之为哈希化。

哈希函数：通常我们将单词转为大数字，大数字在进行哈希化的代码实现放在一个函数中，这就是哈希函数。

哈希表：最终将数据插入到这个数组，对整个结构的封装，我们就称之为哈希表。

哈希化后的下标值仍可能会重复，解决方案有二：

1.链地址法

链地址解决冲突的办法是每个数组单元中存放的不再是单个数据，而是一个链条（数组和链表），当发现重复时，便把重复的元素插入到链表的首端或末端即可。当查询时，先根据哈希化后的下标值找到对应的位置，再取出链表，依次查询寻找的数据。

一般哈希化的index找出这个链表或数组时，通常就会使用线性查找，这时数组和链表的效率是差不多的。

但若是需要将新插入的数据放在数组或链表的最前面，因为觉得新插入的数据用于取出的可能性更大，这种情况最好采用链表，因为数组在首位插入数据时需要其他项后移，链表则没有此问题。5

2.开放地址法

开放地址法的主要工作方式是寻找空白的单元格来添加重复的数据。

6

线性探测

线性的查找空白的单元。

插值：当我们通过哈希化找到下标值时，发现该位置已经有值了，下标值就自加1开始一点一点查找合适的位置（空的位置）

查询：首先经过哈希化得到下标值，比较该下标值的结果与查询的数值是否相同，相同则返回，不同则线性查找（下标值加1），查到空位置即停止。因为插值时不可能跳过空位置去其他位置。

删除：删除一个数据项时，不可以将这个位置下标的内容设置为null，因为将它设置为null可能影响我们之后查询其他操作，所以通常删除一个位置的数据项时，需将其进行特殊处理（比如设置为-1）。

当我们之后看到-1位置的数据项时就知道查询时要继续查询，但是插入该位置可放置数据。

线性探测有一个较严重的问题就是聚集（连续填充单位），它会影响哈希表的性能，无论删除/插入/删除都会影响。

树

  1. 节点的度（degree）：节点的子树个数。
  2. 树的度：树的所有节点中最大的度数。
  3. 叶节点（leaf）：度为0的节点（也称为叶子节点）。
  4. 父节点（parent）：有子树的节点是其树的根节点的父节点。
  5. 子节点（child）
  6. 兄弟节点路径和路径长度：一个节点序列的父节点，路径所包含的边的个数为路径的长度。
  7. 节点的层次（level）：规定根节点在1层，其他节点的层数是其父节点的层数加1.
  8. 树的深度（depth）：树中所有节点中的最大层次是这棵树的深度。
二叉树
  1. 一个二叉树第i层的最大节点数为2^(i-1),i>=1;
  2. 深度为k的二叉树有最大的节点总数为：2^k-1,k>=1;
  3. 对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶节点个数，则两者关系n0 = n2 + 1。
二叉搜索树

二叉搜索树（BST ,Binary Search Tree)，也称二叉排序树或二叉查找树。二叉搜索树是一颗二叉树，可以为空；二分查找法其实就是利用的二叉搜索树。

如果不为空，满足以下性质：

  1. 非空左子树的所有键值小于其根节点的键值。
  2. 非空右节点的所有键值大于其根节点的键值。
  3. 左，右子树本身也都是二叉树。

常见操作：

  1. insert（key）：向树中插入一个新的键

  2. search（key）：树中查找键

  3. inOrderTraverse：通过中序遍历所有节点。

  4. preOrderTraverse：先序

  5. postOrderTraverse：后序

  6. min

  7. max

  8. remove（key）

    如果我们要删除的节点current有两个子节点，甚至子节点还有子节点，这种情况下就需要从current下面所有节点中找到一个最接近current的节点来替换current。

    最接近curren的节点必定是比current小一点点的节点（它必是current左子树中的最大值，叫做前驱）和比current大一点点的节点（current右子树的最小值，叫做后继）

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
function BinarySearchTree() {
    function Node(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    this.root = null;
    // insert方法:对外给用户调用的方法
    BinarySearchTree.prototype.insert = function (key) {
        // 根据key值创建节点
        let newNode = new Node(key);
        // 判断根节点是否为空，空节点直接将新节点赋给根节点
        // 非空节点则调用内部insertNode方法
        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);
            }
        }
    }

    // 树的遍历
    // 1.先序遍历
    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);
            this.postOrderTraversalNode(node.right);
            handler(node.key);
        }
    }
    
     //层序遍历
    BinarySearchTree.prototype.levelOrderTraversal = function(){
        if(!this.root) return false;   //头节点为空返回false
        let result = [];   //创建一个数组存放结果
        let tree = [];    //创建一个数组存放二叉树
        tree.push(this.root);    //先传入头节点
        while(tree.length){       //当tree数组长度不为空
            let node = tree.shift();     //将数组中的第一个节点放到node中
            result.push(node.key);         // 将node节点的值放入result中
            if(node.left){                 //如果node的左节点不为空，就将左节点压入tree数组中
                tree.push(node.left);
            }
            if(node.right){                //如果node的右节点不为空，就将左节点压入tree数组中
                tree.push(node.right);
            }
        }
        return result;
    }
    

    // 找最小值，在最左边位置
    BinarySearchTree.prototype.min = function () {
        let node = this.root;
        while (node.left) {
            node = node.left;
        }
        return node.key;
    }

    // max
    BinarySearchTree.prototype.max = function () {
        let node = this.root;
        while (node.right) {
            node = node.right;
        }
        return node.key;
    }

    // search搜索特定的值
    // 递归搜索
    // BinarySearchTree.prototype.search = function (key) {
    //     return this.searchNode(this.root, key);
    // }
    // BinarySearchTree.prototype.searchNode = function (node, key) {
    //     if (node == null) {
    //         return false;
    //     }
    //     if (key < node.key) {
    //        return this.searchNode(node.left, key);
    //     } else if (key > node.key) {
    //         return this.searchNode(node.right, key);
    //     } else {
    //         return true;
    //     }
    // }
    // 循环搜索
    BinarySearchTree.prototype.search = function(key){
        let node = this.root;
        while(node){
            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){
        // 寻找要删除的节点，定义变量，保存一些信息
        let parent = null;
        let current = this.root;
        let isLeftChild = true;

        // 开始寻找删除的节点
        while(current.key != key){
            parent = current;
            if(key < current.key){
                isLeftChild = true;
                current = current.left;
            }else{
                isLeftChild = false;
                current = current.right;
            }
            // 若已经找到最后的节点，依然没找到等于key的节点
            if(current == null)   return false;
        }

        // 找到了要删除的节点
        // 1.是一个叶节点
        if(current.left == null && current.right == null){
            if(isLeftChild){
                parent.left = null;
            }else{
                parent.right = null;
            }
        }
        // 2.删除节点有一个子节点
        else if(current.right == null){
            if(current == this.root){
                this.root = current.left;
            }else if(isLeftChild){
                parent.left = current.left;
            }else{
                parent.right = current.left;
            }
        }else if(current.left == null){
            if(current == this.root){
                this.root = current.right;
            }else if(isLeftChild){
                parent.left = current.right;
            }else{
                parent.right = current.right;
            }
        }
        // 3.删除的节点上有两个节点
        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;
        }

    }

    // 找后继的方法
    BinarySearchTree.prototype.getSuccessor = function(delNode){
        // 定义变量，保存找到的后继
        let successor = delNode;
        let current = delNode.right;
        let successorParent = delNode.parent;

        // 循环查找
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.left;
        }
        // 判断寻找的后继节点是否直接就是delNode的right节点
        if(successor != delNode.right){
            successorParent.left = successor.right;
            successor.right = delNode.right;
        }
        return successor;

    }
}
let bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(42);
bst.insert(5);
bst.insert(8);
let resultStr = '';
bst.preOrderTraversal(function (key) {
    resultStr += key + ' ';
})
console.log(resultStr);
bst.remove(11);
resultStr = '';
bst.midOrderTraversal(function (key) {
    resultStr += key + ' ';
})
console.log(resultStr);

我们发现删除操作很棘手。实际上，因为它复杂，所以我们尽量避免删除操作。做法是在Node类中添加一个boolean的字段，比如isDeleted。要删除一个节点时就将该字段设为true。进行其他操作时，比如find（），在查找前会先判断这个节点是不是被标记为删除。这样比较简单，不会删除原来的树结构，但在二叉树存储中仍保留着本该被删除的节点，造成了很大的空间浪费。

二叉搜索树可快速找到给定关键字的数据项，并且可快速插入和删除数据项。但是当插入的数据是有序的数据时，树的深度就会变得很大，变成非平衡二叉树。

非平衡树：

  1. 比较好的二叉搜索树数据项应该是左右分布均匀的，但是插入连续数据后，分布的不均匀即为非平衡树。
  2. 对于一颗平衡二叉树来说，查找和插入等操作的效率是O（logN）。
  3. 非平衡二叉树相当于编写了一个链表，查找效率变成了O（N）。

AVL树

AVL树是最早的一种平衡树，他有办法保持树的平衡（每个节点多存储了一个额外的数据），时间复杂度为O（logN），但每次删除插入操作不及红黑树，所以整体效率不如红黑树。

红黑树

红黑树除了满足二叉搜索树的基本规则外，还有以下特性：

  1. 节点都是黑色或红色。
  2. 根节点是黑色。
  3. 每个叶子节点都是黑色的空节点（Null节点）。
  4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根所有路径上不能有两个连续的红色节点）。
  5. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点。

以上约束确保了红黑树的关键特性：

  1. 从根到叶子的最长可能路径不会超过最短可能路径的两倍长。最短者的可能路径是都是黑色节点，最长的可能路径是红色和黑色交替。
  2. 红黑树基本是平衡的，虽然没有做到绝对的平衡，但是可以保证在最坏的情况下依然是高效的。

本文标题:数据结构与算法

文章作者:陈楚吟

发布时间:2020-04-27, 20:36:59

最后更新:2020-06-23, 21:35:34

原始链接:http://yoursite.com/2020/04/27/数据结构与算法/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数据结构与算法
    1. 1.0.1. 数组
      1. 1.0.1.0.1. 数组解构赋值应用
      2. 1.0.1.0.2. 数组浅拷贝
      3. 1.0.1.0.3. 数组合并
      4. 1.0.1.0.4. 数组去重
      5. 1.0.1.0.5. 数组取交集
      6. 1.0.1.0.6. 数组取差集
      7. 1.0.1.0.7. 数组转对象
      8. 1.0.1.0.8. 数组摊平
      9. 1.0.1.0.9. 数组常用遍历
      10. 1.0.1.0.10. 遍历的混合使用
      11. 1.0.1.0.11. 检测数组所有元素是否都符合判断条件
      12. 1.0.1.0.12. 检测数组是否有元素符合判断条件
      13. 1.0.1.0.13. 找到第一个符合条件的元素/下标
      14. 1.0.1.0.14. 数组使用误区
      15. 1.0.1.0.15. 合理使用 Set 数据结构
      16. 1.0.1.0.16. 强大的reduce
  2. 1.0.2. 栈
    1. 1.0.2.0.1. 用JavaScript封装栈
    2. 1.0.2.0.2. 用栈将十进制转为二进制
  • 1.0.3. 队列
    1. 1.0.3.0.1. 队列结构
    2. 1.0.3.0.2. 队列击鼓传花
    3. 1.0.3.0.3. 优先级队列
  • 1.0.4. 链表
    1. 1.0.4.0.1. 单向链表
    2. 1.0.4.0.2. 双向链表
  • 1.0.5. 集合
    1. 1.0.5.0.1. 集合常见操作：
    2. 1.0.5.0.2. 集合间的操作
  • 1.0.6. 哈希表
    1. 1.0.6.0.1. 字母转数字
    2. 1.0.6.0.2. 哈希化
    3. 1.0.6.0.3. 1.链地址法
    4. 1.0.6.0.4. 2.开放地址法
    5. 1.0.6.0.5. 线性探测
  • 1.0.7. 树
    1. 1.0.7.0.1. 二叉树
    2. 1.0.7.0.2. 二叉搜索树
    3. 1.0.7.0.3. 红黑树
    • |