你可能知道的 javaScript 数据结构与算法
本文已同步到github 你可能知道的 javaScript 数据结构与算法，欢迎Star。
如果想阅读笔者更多文章，欢迎猛戳这里
关于数据结构与算法，终于抽时间把之前看过的这两本书《学习JavaScript数据结构与算法》、《数据结构与算法JavaScript描述》，整理出来了一部分内容，由于最近较忙，先把已整理出来的内容发一下。对于未整理出来的内容会在后续整理出来，并更新到此文，也会随着对数据结构与算法不断的学习，不断优化更新此文，感兴趣的小伙伴可以先收藏哦。这两本书对前端来讲是很好的入门数据结构与算法的书，个人感觉《学习JavaScript数据结构与算法》这本书从排版以及思路上更清晰一些。
另外，为了截图和验证方便，本文的例子大多是书中的例子。
本文较长，如果阅读起来不方便，可链接到我的github中，单独查看。
| github | |
|---|---|
| 数据结构 | 栈 |
| 队列 | |
| 链表 | |
| 集合 | |
| 树 | |
| 排序算法 | 冒泡排序 |
| 选择排序 | |
| 插入排序 |
闲言少叙，直接开始了
JavaScript 数据结构
栈
栈是一种遵从后进先出LIFO（Last In First Out，后进先出）原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。
定义一个栈的类，并为该栈声明一些方法，存储数据的底层数据结构使用数组
class Stack {
constructor() {
this.dataStore = []
}
// 向栈中添加一个或多个元素到栈顶
push() {
for (let i = 0; i < arguments.length; i++) {
this.dataStore.push(arguments[i])
}
}
// 移出栈顶元素，并返回被移出的元素
pop() {
return this.dataStore.pop()
}
// 返回栈顶元素，不对栈做修改
peek() {
return this.dataStore[this.dataStore.length - 1]
}
// 判断栈是否为空，如果为空返回true，否则返回false
isEmpty() {
return this.dataStore.length === 0
}
// 清空栈
clear() {
this.dataStore = []
}
// 返回栈中元素的个数
size() {
return this.dataStore.length
}
}
// 栈的操作
let stack = new Stack()
stack.push(1, 2, 3)
console.log(stack.dataStore) // [1, 2, 3]
console.log(stack.pop()) // 3
console.log(stack.dataStore) // [1, 2]
console.log(stack.peek()) // 2
console.log(stack.dataStore) // [1, 2]
console.log(stack.size()) // 2
console.log(stack.isEmpty()) // false
stack.clear()
console.log(stack.dataStore) // []
console.log(stack.isEmpty()) // true
console.log(stack.size()) // 0栈的应用
本文举书中一个进制转换的例子并稍作修改,栈的类还是使用上面定义的Stack
function transformBase(target, base) {
let quotient; // 商
let remainder; // 余数
let binaryStr = ''; // 转换后的值
let digits = '0123456789ABCDEF' // 对转换为16进制数做处理
let stack = new Stack()
while(target > 0) {
remainder = target % base
stack.dataStore.push(remainder)
target = Math.floor(target / base)
}
while(!stack.isEmpty()) {
binaryStr += digits[stack.dataStore.pop()].toString()
}
return binaryStr
}
console.log(transformBase(10, 2)) // 1010
console.log(transformBase(10, 8)) // 12
console.log(transformBase(10, 16)) // A队列
队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。
其实队列和栈类似，只是原则不同，队列是先进先出，用代码来实现一个队列及操作队列的一些方法，以下用代码实现一个队列的类, 测试和栈类似，就不做具体测试了。
class Queue {
constructor() {
this.dataStore = []
}
// 入队
enqueue() {
for (let i = 0; i < arguments.length; i++) {
this.dataStore.push(arguments[i])
}
}
// 出队
dequeue() {
return this.dataStore.shift()
}
// 返回队列第一个元素，不改变队列
front() {
return this.dataStore[0]
}
// 队列是否为空
isEmpty() {
return this.dataStore.length === 0
}
// 返回队列的的元素个数
size() {
return this.dataStore.length
}
}优先队列
队列中在生活中有着大量应用，如登机时，商务舱要优于经济舱，这时候可以给队列中的元素设置优先级，下面用代码来实现一个优先队列的类
class PriorityQueue {
constructor() {
this.dataStore = []
}
isEmpty() {
return this.dataStore.length === 0
}
enqueue(element, priority) {
function QueueElement(element, priority) {
this.element = element
this.priority = priority
}
// 定义每次往队列里添加的元素
let queueElement = new QueueElement(element, priority)
if (this.isEmpty()) {
// 如果每次队列为空直接添加到队列中
this.dataStore.push(queueElement)
} else {
// 定一个是否被添加到队列的标志
let isAdded = false
for (let i = 0; i < this.dataStore.length; i++) {
if (queueElement.priority < this.dataStore[i].priority) {
// 优先级数值越小，代表优先级越高
this.dataStore.splice(i, 0, queueElement)
isAdded = true
break;
}
}
if (!isAdded) {
// 如果被添加的新元素优先级最低，添加到队尾
this.dataStore.push(queueElement)
}
}
}
//
}
let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('a', 5)
priorityQueue.enqueue('b', 2)
priorityQueue.enqueue('c', 3)
console.log(priorityQueue.dataStore)最后的队列如下图：
链表
直接上代码:
class LinkedList {
constructor() {
this.head = null // 链表的第一个元素
this.length = 0
}
// 向链表尾部添加一个新元素
append(element) {
let Node = function(element) {
this.element = element
this.next = null
}
let node = new Node(element)
let currentNode;
if (this.head == null) {
// 如果链表head为null，表示链表无元素，直接把node赋值给head即可
this.head = node
} else {
currentNode = this.head
while (currentNode.next) {
// 每次循环会进行到链表的倒数第一个元素，把currentNode设置为倒数第一个元素
currentNode = currentNode.next
}
// 把新增的node赋值给currentNode的next属性，最后一个元素的next永远为null
currentNode.next = node
}
// 链表的元素个数每次append后 +1
this.length++
}
// 从链表中按位置删除元素
removeAt(position) {
// position表示要移除元素的位置
let index = 0
let previous = null
let currentNode = this.head
if (position >= 0 && position < this.length) {
while (index < position) {
// 主要是找出position位置的元素，设置为currentNode
previous = currentNode
currentNode = currentNode.next
index++
}
// 把currentNode的上一个元素的next指向currentNode的下一个元素，就对应删除了currentNode
previous.next = currentNode.next
} else {
// 表示链表中不存在这个元素，直接return null
return null
}
// 删除后链表的元素个数每次删除减1
this.length--;
// 返回删除的元素
return currentNode
}
// 按元素值删除元素
remove(element) {
let index = this.indexOf(element)
return this.removeAt(index)
}
// 向链表中插入新元素
insert(element, position) {
// element表示被插入元素的具体值
// position表示被插入元素的位置
if (position >= 0 && position < this.length) {
let index = 0
let previous = null
let currentNode = this.head
let Node = function(element) {
this.element = element
this.next = null
}
let node = new Node(element)
while (index < position) {
previous = currentNode
currentNode = currentNode.next
index++
}
// 把当前元素的上一个元素的next设置为被插入的元素
previous.next = node
// 把被插入元素的next设置为当前元素
node.next = currentNode
// 链表元素个数加1
this.length++;
// 如果插入元素成功，返回true
return true
} else {
// 如果找不到插入元素位置，返回false
return false
}
}
// 查找元素在链表中的位置
indexOf(element) {
let currentNode = this.head
let index = 0
// 如果currentNode也就是head为空，则链表为空不会进入while循环，直接返回 -1
while (currentNode) {
if (element === currentNode.element) {
// 如果被找到，返回当前index
return index
}
// 每一轮循环如果被查找元素还没有被找到，index后移一位，currentNode指向后一位元素，继续循环
index++
currentNode = currentNode.next
}
// 如果一直while循环结束都没找到返回 -1
return -1
}
// 链表是否为空
isEmpty() {
return this.length === 0
}
// 链表元素个数
size() {
return this.length
}
}
let linkedList = new LinkedList()
linkedList.append('a')
linkedList.append('b')
linkedList.append('c')
linkedList.append('d')
linkedList.removeAt(2)
linkedList.insert('e', 2)
console.log('bIndex', linkedList.indexOf('b'))
console.log('fIndex', linkedList.indexOf('f'))
linkedList.remove('d')
console.log(linkedList)上述代码测试结果如下图所示:
集合
class Set {
constructor() {
this.items = {}
}
has(val) {
return val in this.items
}
// 向集合中添加一个新的项
add(val) {
this.items[val] = val
}
// 从集合中移除指定项
remove(val) {
if (val in this.items) {
delete this.items[val]
return true
}
return false
}
// 清空集合
clear() {
this.items = {}
}
// 返回集合中有多少项
size() {
return Object.keys(this.items).length
}
// 提取items对象的所有属性，以数组的形式返回
values() {
return Object.keys(this.items)
}
// 取当前集合与其他元素的并集
union(otherSet) {
let unionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
unionSet.add(values[i])
}
let valuesOther = otherSet.values()
for (let i = 0; i < valuesOther.length; i++) {
unionSet.add(valuesOther[i])
}
return unionSet
}
// 取当前集合与其他元素的交集
intersection(otherSet) {
let intersectionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
intersectionSet.add(values[i])
}
}
return intersectionSet
}
// 取当前集合与其他元素的差集
diff(otherSet) {
let intersectionSet = new Set()
let values = this.values()
for (let i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
intersectionSet.add(values[i])
}
}
return intersectionSet
}
// 判断当前集合是否是其他集合的子集
isSubSet(otherSet) {
// 如果当前集合项的个数大于被比较的otherSet的项的个数，则可判断当前集合不是被比较的otherSet的子集
if (this.size() > otherSet.size()) {
return false
} else {
let values = this.values()
for (let i = 0; i < values.length; i++) {
// 只要当前集合有一项不在otherSet中，则返回false
if (!otherSet.has(values[i])) {
return false
}
}
// 循环判断之后，当前集合每一项都在otherSet中，则返回true
return true
}
}
}// 测试
let setA = new Set()
setA.add('a')
setA.add('b')
setA.add('c')
setA.remove('b')
console.log(setA.values()) // ['a', 'c']
console.log(setA.size()) // 2
let setB = new Set()
setB.add('c')
setB.add('d')
setB.add('e')
let unionAB = setA.union(setB)
console.log(unionAB.values()) // ['a', 'c', 'd', 'e']
let intersectionAB = setA.intersection(setB)
console.log(intersectionAB.values()) // ['c']
let diffAB = setA.diff(setB)
console.log(diffAB.values()) // ['a']
let setC = new Set()
setC.add('d')
setC.add('e')
let isSubSetCB = setC.isSubSet(setB)
console.log(isSubSetCB) // true
let isSubSetAB = setA.isSubSet(setB)
console.log(isSubSetAB) // false树
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点
二叉树
// 创建一个键
function createNode(key) {
this.key = key
this.left = null
this.right = null
}
// 向树中插入键
function insertNode(node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
// 遍历回调
function printNode(value) {
console.log(value)
}
// 中序遍历
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
// debugger 可以加入debugger，用浏览器控制观察Call Stack(执行环境栈)来分析程序执行过程
inOrderTraverseNode(node.right, callback)
}
}
// 先序遍历
function prevOrderTraverseNode(node, callback) {
if (node !== null) {
// 先访问节点本身
callback(node.key)
// 再访问左侧节点
prevOrderTraverseNode(node.left, callback)
// 然后再访问右侧节点
prevOrderTraverseNode(node.right, callback)
}
}
// 后序遍历
function postOrderTraverseNode(node, callback) {
if (node !== null) {
// 先访问左侧节点
postOrderTraverseNode(node.left, callback)
// 再访问右侧节点
postOrderTraverseNode(node.right, callback)
// 然后再访问节点本身
callback(node.key)
}
}
class BinarySearchTree {
constructor() {
this.key = null
}
insert(key) {
let newNode = new createNode(key)
if (this.key === null) {
this.key = newNode
} else {
insertNode(this.key, newNode)
}
}
// 中序遍历访问节点(结果为按值由小到大访问)
inOrderTraverse(callback) {
inOrderTraverseNode(this.key, callback)
}
// 先序遍历访问节点(结果为先访问节点本身，再左侧节点，然后再访问右侧节点)
prevOrderTraverse(callback) {
prevOrderTraverseNode(this.key, callback)
}
// 后序遍历访问节点(结果为先访问左侧节点，再访问右侧节点，然后再访问节点本身)
postOrderTraverse(callback) {
postOrderTraverseNode(this.key, callback)
}
// 查找树中的最小值
findMin(node) {
if (node) {
while(node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}
// 查找树中的最小值对应的节点
findMinNode(node) {
if (node) {
while(node && node.left !== null) {
node = node.left
}
return node
}
return null
}
// 查找树中的最大值
findMax(node) {
if (node) {
while(node && node.right !== null) {
node = node.right
}
return node.key
}
return null
}
// 查找树中的特定值，如果存在返回true，否则返回false
search(node, key) {
if (node === null) {
return false
}
if (key < node.key) {
// 如果被查找的key小于节点值，从节点的左侧节点继续递归查找
return this.search(node.left, key)
} else if (key > node.key) {
// 如果被查找的key大于节点值，从节点的左侧节点继续递归查找
return this.search(node.right, key)
} else {
// 被查找的key等于node.key
return true
}
}
// 移除树中的特定节点
removeNode(node, key) {
if (node === null) {
return null
}
if (key < node.key) {
node.left = this.removeNode(node.left, key)
} else if (key > node.key) {
node.right = this.removeNode(node.right, key)
} else {
// console.log(node)
// 移除叶子节点(无左右节点的节点)
if (node.left === null && node.right === null) {
node = null
return node
}
// 移除只有一个节点的节点(只有左节点或只有右节点)
if (node.left === null) {
node = node.right
return node
} else if (node.right === null) {
node = node.left
return node
}
// 移除有两个节点(既有左节点又有右节点)
if (node.left && node.right) {
// 1. 找到被移除节点的右节点下的最小节点，替换被移除的节点
let minRightNode = this.findMinNode(node.right)
// 2. 把被移除节点的key设置为 被移除节点的右节点下的最小节点的key
node.key = minRightNode.key
// 3. 移除找到的那个最小节点
this.removeNode(node.right, node.key)
// 4. 向被移除节点的父节点返回更新后节点的引用
return node
}
}
}
}测试如下:
let tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(6)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(20)
tree.insert(12)
tree.insert(14)
tree.insert(18)
tree.insert(25)
tree.inOrderTraverse(printNode) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
tree.prevOrderTraverse(printNode) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
tree.postOrderTraverse(printNode) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
// tree.key为根节点，为了保持树不同层的结构一致，没有使用root为属性，使用了key
let minNodeVal = tree.findMin(tree.key)
console.log('minNodeVal', minNodeVal)
let maxNodeVal = tree.findMax(tree.key)
console.log('maxNodeVal', maxNodeVal)
let isHasNodeVal = tree.search(tree.key, 7)
console.log(isHasNodeVal) // true
tree.removeNode(tree.key, 15)
console.log(tree) // 可以查看树的结构，15的这个节点的key已经被替换为18，并且key为18的节点已经被删除树的遍历
1. 中序遍历
2. 先序遍历
3. 后序遍历
移除节点的过程
1. 移除以一个叶节点
2. 移除只有一个左侧子节点或右侧子节点的节点
3. 移除有两个子节点的节点
JavaScript 算法
排序算法
1.冒泡排序
冒泡排序的执行过程
代码如下:
let arr = [5, 4, 3, 2, 1]
// 交换元素的位置
function swap(arr, index1, index2) {
var temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
function bubbleSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1)
}
}
}
}
bubbleSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]2.选择排序
选择排序的执行过程
代码如下:
let arr = [5, 4, 3, 2, 1]
function swap(arr, index1, index2) {
var temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
function changeSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i
for (let j = i; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j
}
}
if (i !== minIndex) {
swap(arr, i, minIndex)
}
}
}
changeSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]3.插入排序
插入排序的执行过程
代码如下:
let arr = [5, 4, 3, 2, 1]
function swap(arr, index1, index2) {
var temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
let j = i
let temp = arr[i]
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1]
j--
}
arr[j] = temp
}
}
insertSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]由于功力有限，本文有错误和不合理的地方，欢迎各位大神多多指正，非常感谢。
参考文章：
相关推荐
hugebawu 2020-10-12
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
LauraRan 2020-09-28
shenwenjie 2020-09-24
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02
xiesheng 2020-08-02
范范 2020-07-30
chenfei0 2020-07-30