❝js篇没有结束喔,只不过先复习一下数据结构吧
前两天看到一个大佬发的关于数据结构的博客,满满的字一个代码没有,众人都说太干了。然后小白就写一个只实现的吧
注意这里是下篇
希望你有一些数据结构的基础,了解他们的基本结构。这里主要是实现!!!
图中的图片,一部分是自己画的,一部分是百度图片找的。原来在某c开头的博客上记录笔记故有了上面的水印。
函数式编程的下篇毁于掘金更新那段时间了,很痛心,希望后面忍着泪补上 希望与大家共同进步,代码过多难免有疏漏,且图的部分因为有很多大佬写过了故我这里主要写的是其核心思想(像判空这类的细节没有处理)。如有误,望指教,感恩
代码过多不能排版,只能处理处理头部这样过过日子
❞
此系列博客文章进度
✅js篇
🔲html、css篇
🔲DOM、BOM篇
🔲轮子篇
🔲打包工具篇
✅数据结构篇
🔲前端必刷小算法篇
🔲HTTP篇
🔲性能优化篇
🔲常见设计模式篇
一、 二叉搜索树
树的实现与其相关操作其实都很简单,它的核心就是依靠递归嘛
至于我们为啥上来就直接实现二叉搜索树,而不是别的什么树呢?
首先这树这种数据结构中,其二叉树是最为重要的(也即度小于等于2)。
但是呢?在二叉树中,二叉搜索树又是极为重要且经典的数据结构
why?
那什么是二叉搜索树呢?
即它在二叉树的基础上又做了一个规定, 即只允许你在左侧节点存(比父节点)小的值,在右侧节点存储(比父节点)大的值。 左小右大嘛方便后面的搜索
在下面我们将实现以下方法
- add(key)向树中添加节点
- 遍历(中序先序后序只是输出key的位置不同而已,以中序为例)
- min()取最小值
- max()取最大值
- search(key)判数组是否存在某值
- remove(key)删除树中某节点
实现
1. 添加节点
add(key) {
const node = new TNode(key)
// 下面两种情况,树为空或不空
if (this.root === null) {
this.root = node
}
// 不为空得找地方,另写一个方法
else {
this._addNode(this.root, node)
}
}
_addNode(node, newNode) {
// 首先跟根节点比较大小以判断一会往左方还是往右方
// 放右边去吧
if (newNode.key > node.key) {
if (node.right === null) {
node.right = newNode
} else {
this._addNode(node.right, newNode)
}
}
// 放左边去吧
else {
if (node.left === null) {
node.left = newNode
} else {
this._addNode(node.left, newNode)
}
}
}
2. 遍历(前中后序遍历只在于打印语句代码的先后顺序)
// 中序遍历
//如果你对递归理解的不是很好,小白这里简单解释一下
// 首先这句this._middleTraversal(node.left),即进入函数看有无左孩子,有接着往左边跑,什么时候到打印语句呢?肯定此时已经到了最左边,开始之心函数下面的语句,打印就不用说了,打印完了再看它有无右孩子
// 接着这个递归栈开始弹栈,到上一个左孩子的父节点,然后打印看有无右孩子
//就这样随着弹栈,随着打印,随着判断有孩子,有有孩子就进去处理
//右的方式同理
_middleTraversal(node) {
if (node != null) {
// 去找左边
this._middleTraversal(node.left)
// 左到头了,开始打印
console.log(node.key)
this._middleTraversal(node.right)
}
}
// 对外暴露这个中序遍历的方法,以为上面的还有传入根节点
middleTraversal() {
this._middleTraversal(this.root)
}
3. 取最大、取最小值
// 我们都清楚一般使用递归的也可使用循环进行改造
// 递归简单好理解,但是性能差
// 循环不好理解,但是性能好(这里的都比较简单)
// 下面,我min用循环,max用递归
min() {
return this._minNode(this.root).key
}
//根据二叉搜索树的特性,最小值就是最左边的呗
_minNode(node) {
while (node != null && node.left != null) {
node = node.left
}
return node
}
max() {
return this._maxNode(this.root).key
}
// 在最右边呗
_maxNode(node) {
if (node.right === null) {
return node
} else {
return this._maxNode(node.right)
}
}
4. 搜索指定节点
isKey(key) {
return this._isKey(this.root, key)
}
_isKey(node, key) {
if (node === null) {
return false
}
// 左边
if (node.key > key) {
return this._isKey(node.left)
}
// 右边
else if (node.key < key) {
return this._isKey(node.right)
}
// 相等
else if (node.key === key) {
return true
} else {
return false
}
}
5. 移出节点(本章难点)
这段代码的难点是在于返回值有一个易错点
错误示例
容易认为像这样
// 情况二 if (node.left != null && node.right === null) { node = node.left return true }
直接node=node.left,就认为它们之间的指针关系连接好了,但其实并没有。其父节点仍然是指向的原来的子节点,即这棵树你根本没有做任何改变
为啥呢?因为你这样写是拿不到它的父节点的,它父节点指向的还是原来的它子节点那块地址
你可能又会说我不是改变node的值了么?
首先node只是个变量,它原先指的是一个对象的,你现在又让它指向一个新的对象
可是其父节点中指针域可不是指的你node啊,它指的你node指向的那块地址。此时你node又指向了新的地址,其父节点可不会跟着变化啊(小白还是纯小白时犯下的错误,公开处刑?害,谁让那时自己基础差啊,改了得有2-3天)
remove(key) {
return this._remove(this.root, key)
}
// 这里有三种情况
// 1. 叶子节点,直接干掉即可
// 2. 有一个孩子,那么将它的孩子作为继承人就行了
// 3. 两孩子就比较难受了,得找一个和它比较像的吧。有两个,它左子树的右叶子和它右子树的左叶子。这里我们将它的继承者定为它右子树的左叶子。
_remove(node, key) {
if (node.key > key) {
return this._remove(node.left, key)
} else if (node.key < key) {
return this._remove(node.right, key)
}
// 找到了开始删除
else if (node.key === key) {
// 情况一
if (node.left === null && node.right == null) {
node = null
return true
}
// 情况二
if (node.left != null && node.right === null) {
node = node.left
return true
}
if (node.left === null && node.right != null) {
node = node.right
return true
}
// 情况三
const rightTree = node.right
const currentKey = this._minNode(rightTree).key
node.key = currentKey
this._remove(node.right, currentKey)
return true
} else {
return false
}
}
}
正确代码
remove(key) {
return this.root = this._remove(this.root, key)
}
// 这里有三种情况
// 1. 叶子节点,直接干掉即可
// 2. 有一个孩子,那么将它的孩子作为继承人就行了
// 3. 两孩子就比较难受了,得找一个和它比较像的吧。有两个,它左子树的右叶子和它右子树的左叶子。这里我们将它的继承者定为它右子树的左叶子。
_remove(node, key) {
if (node.key > key) {
node.left = this._remove(node.left, key)
return node
} else if (node.key < key) {
node.right = this._remove(node.right, key)
return node
}
// 找到了开始删除
else if (node.key === key) {
// 情况一
if (node.left === null && node.right == null) {
node = null
return node
}
// 情况二
if (node.left != null && node.right === null) {
node = node.left
return node
}
if (node.left === null && node.right != null) {
node = node.right
return node
}
// 情况三
const rightTree = node.right
const currentKey = this._minNode(rightTree).key
node.key = currentKey
node.right = this._remove(node.right, currentKey)
return node
} else {
return false
}
}
}
部分测试代码
tree.add(6)
tree.add(7)
tree.add(4)
tree.add(2)
tree.add(10)
tree.middleTraversal()
console.log(tree.min())
console.log(tree.max())
console.log(tree.remove(6))
console.log(tree)
console.log(tree.isKey(11))
二、 二叉堆
终于到了一个比较来说实现不是那么常规的数据结构的实现了
首先来了解一下什么是二叉堆?
二叉堆的本质是一个完全二叉树,且其又有最大堆最小堆之分
最小堆:任何一个父节点的值都要小于它左右孩子的值
最大堆与最小堆相反
来看二叉堆的实现吧(原理一下,这里我们以最小堆为例)
我们接下来我实现以下功能:
- insert(val)像堆中插入新数据
- extract()剔除最小值(最小堆),最大堆就剔除最大值
- findMin() 返回最小者,最大堆中就findMax返回最大值呗
前提: 我们要知道储存一棵二叉树一般有两种方式,一个是“指针”的形式即保存数据之间的联系。 第二种形式即使用数组,我们可以事先给树编写序号,利用数组的索引位置一一对应。如下图
这时我们就得需要知道一些东西
在数组中给我们一个数据的位置,我们如何拿到它的父、子节点? 通过一些规律观察我们可以有以下结论。 数组中如果给定一已存储了节点元素个位置index,那么
- 它的左子节点位置是 2 * index + 1;
- 它的右子节点位置是 2 * index + 2;
- 它的父节点位置是(index -1)/ 2(向下取整,根节点除外)。
工具函数
class MinHeap {
constructor() {
this.data = []
}
//先写三个工具函数
// 拿左孩子
_getLeftIndex(index) {
return 2 * index + 1
}
// 拿右孩子
_getRightIndex(index) {
return 2 * index + 2
}
//拿父节点
_getParentIndex(index) {
if (index === 0) {
return undefined
} else {
return Math.floor((index - 1) / 2)
}
}
}
insert:插入数据
实现insert方法的核心就是它里面的上移操作。 什么上移及怎么上移呢? 看图 (图片是以前画的,其水印是我原来在某c开头博客做笔记时上传的,下面是我又截下来的)
新来一个节点2,要加入堆中,开始加入堆底。即放到节点3的右孩子位置上
这是因为二叉堆的特性,最小堆父节点数据是要小于它每个子节点的。现在不符合这一特性了,即节点2要进行上移。怎么上移呢,它先和自己的父节点进行数据的比较。若比其父节点数值小。则进行位置交换
交换完成
实现
insert(value) {
this.data.push(value) //此时相当于新来的在树的最后了
this._upHead(this.data.length - 1) //进行上移
}
// 上移
_upHead(index) {
// 拿其父节点
let parent = this._getParentIndex(index)
while (index > 0 && (this.data[index] < this.data[parent])) {
// 交换
this._swap(this.data, parent, index)
index = parent
parent = this._getParentIndex(index)
}
}
// 交换
_swap(arr, a, b) {
[arr[b], arr[a]] = [arr[a], arr[b]]
}
extract:剔除堆顶
extract方法的作用是剔除堆顶。 extract方法的核心是堆化,先来看看堆化的思路吧。
如下图我们要剔除堆顶,不能直接剔除就完事了吧。。。我们还要保持它的堆结构呢,怎么保持呢?
首先让这个堆顶节点1与它的子节点比较,小于它的子节点(废话嘛)。交换两者位置
交换完成之后,再与它的子节点比较。这时就出现了一点问题。如果是和节点7交换,那么我们直接pop掉即可,和6交换我们要怎么办呢?去data里面去找到吗?这显然不是我们不需要的。
来再换一种方法吧
首先我们就先把堆顶和堆底节点互换,然后把换完的新堆底扔出去
这时新堆顶是7,它要下移。则有子节点比较。交换位置
接着比较,交换位置
再换,大功告成
extract() {
//空堆
if (this.data.length === 0) {
return false
}
if (this.data.length === 1) {
return this.data.pop()
}
// 堆中有多值
let current = this.data[0] //要删除的
// 交换
this._swap(this.data, 0, this.data.length - 1)
//移出
this.data.pop()
// 下移
this._sinkDown(0)
return current
}
// 堆化(下移)
_sinkDown(index) {
let current = index
let left = this._getLeftIndex(index)
let right = this._getRightIndex(index)
let size = this.data.length
//与左孩子比较
if (this.data[current] > this.data[left] && left < size) {
current = left
}
if (this.data[current] > this.data[right] && left < size) {
current = right
}
//current发生了变动,开始进行交换及其递归处理,没有发生变动则说明此时已经是堆化的结构了
if (index != current) {
this._swap(this.data, index, current);
this._sinkDown(current)
}
}
findMin :返最小值(即堆顶)
findMin() {
return this.data.length === 0 ? undefined : this.data[0]
}
部分测试代码
heap.insert(4)
heap.insert(5)
heap.insert(1)
heap.insert(2)
heap.insert(3)
console.log(heap)
heap.insert(4)
heap.insert(5)
heap.insert(1)
heap.insert(2)
heap.insert(3)
heap.extract()
console.log(heap)
三、图(以最简单的无向无权图为例)
这可能是你见过最简单的图的实现方法
3.1 图的表示
来简单复习一下吧
邻接矩阵
采用一个二维矩阵
如图:(额找的这个图不太好,咋都有三个边啊)
顶点的存储方式好说,数组就可以。便就用这么一个矩阵,ab之间右边则记为1
再来简单说一下它的缺点:对于一个边极少(矩阵为稀疏矩阵)浪费空间
邻接表
邻接表可借助如图一个链表的方式存储每个顶点的边
也来简单说一下它的缺点:对于有向图的入边表示不了
3.2 图的实现
我们这里不使用链表表示边的情况了,为了简单。我们就使用一个对象
如顶点A相邻的顶点有B,C,D
我们就这样表示{"A":["B","C","D"]}
图的表示采有邻接表
class Graph {
constructor() {
this.vertexes = []//顶点
this.edges = {}//记录边
this.statu = {}//顶点状态
}
}
加入顶点
addVertexe(v) {
this.vertexes.push(v)
this.edges[v] = []
}
加入边
addEdges(v1, v2) {
this.edges[v1].push(v2)
this.edges[v2].push(v1)
}
3.3 图的遍历
记录状态
_initStatu() {
this.vertexes.forEach(item => {
this.statu[item] = 1
})
}
bfs需要借助队列,把上次写好的队列拿过来
class Queue {
constructor() {
this._data = {}
this._count = 0
this._first = 0 //队头指针
}
isEmpty() {
return this._count === this._first
}
enqueue(value) {
this._data[this._count++] = value
}
dequeue() {
if (this.isEmpty()) {
return undefined
}
let res = this._data[this._first]
delete this._data[this._first]
this._first++;
return res
}
peek() {
if (this.isEmpty()) {
return undefined
}
return this._data[this._first]
}
size() {
return this._count - this._first
}
clean() {
this._data = {}
this._count = 0
this._first = 0
}
}
广度优先搜索
哈哈,我又搞了个图。来举个栗子吧
bfs,人如其名,以广度为先
比如上图我们从a开始,与a相连的为g,e,b。依次访问到之后回到g处,与g相连的有f(重复的a我们不在要一遍了);在到e处,与e相连的暂时没有了(ab重复);再到b处,与b相连的有c...就这样一直搞下去直到把所有的顶点访问一遍(如果写过二叉树的层次遍历你会感觉他们非常相像,借用队列呗)
怎么记录一顶点访问过没有呢
这就用到顶点状态了。
如开始顶点的状态为1,访问过它之后就把它的状态设置为2,有时候我们还会传进去一个函数用于处理这个顶点,那么处理过的就设置为3
实现(注意下面的测试栗子不是上图中的啊,原来练习写的测试栗子,这个测试的栗子代码有点长和恶心就没有改动)
bfs(v, fn) {
// 初始化状态
this._initStatu()
const q = new Queue()
q.enqueue(v)
while (!q.isEmpty()) {
let current = q.dequeue()
// 将当前顶点状态设为2
this.statu[current] = 2
// 取与当前顶点相连的入队
this.edges[current].forEach(item => {
if (this.statu[item] == 1) {
this.statu[item] = 2
q.enqueue(item)
}
})
// 访问出队的顶点(即操作它)
fn(current)
this.statu[current] = 3
}
}
测试代码
const g = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(item => g.addVertexe(item))
g.addEdges('A', 'B')
g.addEdges('A', 'C')
g.addEdges('A', 'D')
g.addEdges('C', 'D')
g.addEdges('C', 'G')
g.addEdges('D', 'G')
g.addEdges('D', 'H')
g.addEdges('B', 'E')
g.addEdges('B', 'F')
g.addEdges('E', 'I')
console.log(g)
g.bfs('A', function(v) {
console.log(v)
})
深度优先搜索
dfs同样人如其名,还是用上面这个图举个栗子,还是从a开始
a找到了g,从g找到了f,从f(先选一条路)找到了h,从h找到了i到头了回去
回到f,进去另一条路,找到了e,找到了b,找到了c找到了d,又到头回去。这回中间没有可走的岔路了,故直接到了起始a,通过a又找到了e
完了,最简单的思路就是递归了
实现
dfs(v, fn) {
// 初始化状态
this._initStatu()
this._dfsVisit(v, fn)
}
_dfsVisit(v, fn) {
this.statu[v] = 2
fn(v)
// 拿与其相邻的顶点
this.edges[v].forEach(item => {
if (this.statu[item] === 1) {
this._dfsVisit(item, fn)
}
})
this.statu[v] = 3
}
}
测试代码
const g = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(item => g.addVertexe(item))
g.addEdges('A', 'B')
g.addEdges('A', 'C')
g.addEdges('A', 'D')
g.addEdges('C', 'D')
g.addEdges('C', 'G')
g.addEdges('D', 'G')
g.addEdges('D', 'H')
g.addEdges('B', 'E')
g.addEdges('B', 'F')
g.addEdges('E', 'I')
console.log(g)
g.dfs('A', function(v) {
console.log(v)
})
参考书籍
王道考研数据结构
严奶奶的那本(数据结构(C语言版) 第2版 (严蔚敏等))
学习js数据结构与算法
写到最后
小白原来的笔记链接(有一些错误没有进行更改)
AVL以及红黑树就留到以后有时间写吧
星光不问赶路人,时光不负有心人 期待着我们的下一次邂逅