常见的数据结构 · 技术文档

### 一、栈栈是一个线性结构，在计算机中是一个相当常见的数据结构。栈的特点是只能在某一端进行添加或者删除数据，遵循先进后出的原则 **实现** 每种数据结构都可以用很多方式来实现，其实可以把栈看做成数组的一个子集，所以这里用数组来实现 ``` class Stack { constructor() { this.stack = []; } push(item) { this.stack.push(item); } pop() { this.stack.pop(); } peek() { return this.stack[this.getConut() - 1] } getConut() { return this.stack.length; } isEmpty() { return this.getConut() === 0 } } ``` **应用** 选取了LeetCode 上序号为 20 的题目题意是匹配括号，可以通过栈的特性来完成这道题目 ``` var isValid = function (s) { let map = { '(': -1, ')': 1, '[': -2, ']': 2, '{': -3, '}': 3 } let stack = [] for (let i = 0; i < s.length; i++) { if (map[s[i]] < 0) { stack.push(s[i]) } else { let last = stack.pop() if (map[last] + map[s[i]] != 0) return false } } if (stack.length > 0) return false return true }; ``` ### 二、队列队列是一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则一下是两种实现队列的方式，分别是单链队列和循环队列** 单链队列** ``` class Queue { constructor() { this.queue = []; } enQueue(item) { this.queue.push(item); } deQueue() { return this.queue.shift() } getHeader() { return this.queue[0] } getLength() { return this.queue.length } isEmpty() { return this.getLength() === 0 } } ``` 因为单链队列在出队操作的时候需要O(n)的时间复杂度，所以引入循环队列，循环队里的出队操作平均是O(1)的时间复杂度 **循环队列** ``` class SqQueue { constructor(length) { this.queue = new Array(length + 1) // 队头 this.first = 0 // 队尾 this.last = 0 // 当前队列大小 this.size = 0 } enQueue(item) { // 判断队尾 + 1 是否为队头 // 如果是就代表需要扩容数组 // % this.queue.length 是为了防止数组越界 if (this.first === (this.last + 1) % this.queue.length) { this.resize(this.getLength() * 2 + 1) } this.queue[this.last] = item this.size++ this.last = (this.last + 1) % this.queue.length } deQueue() { if (this.isEmpty()) { throw Error('Queue is empty') } let r = this.queue[this.first] this.queue[this.first] = null this.first = (this.first + 1) % this.queue.length this.size-- // 判断当前队列大小是否过小 // 为了保证不浪费空间，在队列空间等于总长度四分之一时 // 且不为 2 时缩小总长度为当前的一半 if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) { this.resize(this.getLength() / 2) } return r } getHeader() { if (this.isEmpty()) { throw Error('Queue is empty') } return this.queue[this.first] } getLength() { return this.queue.length - 1 } isEmpty() { return this.first === this.last } resize(length) { let q = new Array(length) for (let i = 0; i < length; i++) { q[i] = this.queue[(i + this.first) % this.queue.length] } this.queue = q this.first = 0 this.last = this.size } } ``` ### 三、链表链表是一个线性结构，同时也是一个天然的递归结构，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理，但是链表失去了数组随机读取的优点，同时链表由于结点的指针域，空间开销比较大 **单向链表** ``` class Node { constructor(v, next) { this.value = v this.next = next } } class LinkList { constructor() { // 链表长度 this.size = 0 // 虚拟头部 this.dummyNode = new Node(null, null) } find(header, index, currentIndex) { if (index === currentIndex) return header return this.find(header.next, index, currentIndex + 1) } addNode(v, index) { this.checkIndex(index) // 当往链表末尾插入时，prev.next 为空 // 其他情况时，因为要插入节点，所以插入的节点 // 的 next 应该是 prev.next // 然后设置 prev.next 为插入的节点 let prev = this.find(this.dummyNode, index, 0) prev.next = new Node(v, prev.next) this.size++ return prev.next } insertNode(v, index) { return this.addNode(v, index) } addToFirst(v) { return this.addNode(v, 0) } addToLast(v) { return this.addNode(v, this.size) } removeNode(index, isLast) { this.checkIndex(index) index = isLast ? index - 1 : index let prev = this.find(this.dummyNode, index, 0) let node = prev.next prev.next = node.next node.next = null this.size-- return node } removeFirstNode() { return this.removeNode(0) } removeLastNode() { return this.removeNode(this.size, true) } checkIndex(index) { if (index < 0 || index > this.size) throw Error('Index error') } getNode(index) { this.checkIndex(index) if (this.isEmpty()) return return this.find(this.dummyNode, index, 0).next } isEmpty() { return this.size === 0 } getSize() { return this.size } } ``` ### 四、树 **二叉树** 树拥有很多结构，二叉树是树种最常用的结构，同时也是一个天然的递归结构。二叉树拥有一个根节点，每个节点之多拥有两个子节点，分别为：左节点、右节点，当一棵树的叶数量为满时，该树可以成为满二叉树 **二分搜索数** 二分搜索树也是二叉树，拥有二叉树的特性，但是区别在于二分搜索树每个节点的值都比他的左子树值大，都比右子树小这种存储方式很适合数据搜索，当需要查找6时，因为需要查找的值比根节点的值大，所以只需要在根节点的右子树上面寻找，大大提高了搜索效率 **实现** ``` class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BST { constructor() { this.root = null; this.size = 0; } getSize() { return this.size } isEmpty() { return this.size === 0 } addNode(v) { this.root = this._addChild(this.root, v) } // 添加节点时，需要比较添加的节点值和当前值的大小 _addChild(node, v) { if (!node) { this.size++; return new Node(v) } if (node.value > v) { node.left = this._addChild(node.left, v); } else if (node.value < v) { node.right = this._addChild(node.right, v) } return node } } ``` 以上是最基本的二分搜索树实现，接下来实现树的遍历。对于数的遍历涞水，有三种遍历方法，分别是先序遍历、中序遍历、后序遍历，三种遍历的区别在于何时访问节点，在遍历树的过程中，每个节点会被遍历三次，分别是遍历自己，编辑左子树、遍历右子树，如果需要实现先序遍历，name需要第一次遍历到节点时进行操作即可先序遍历实现 ``` breadthTraversal() { if (!this.root) return null; let q = new Queue(); q.enQueue(this.root); // 循环遍历队列是否为空，为空代表数遍历完毕 while (!q.isEmpty()) { // 将队首出队，判断是否有右子树 // 有的话，酒店左后右入队 let n = q.deQueue() console.log(n.value) if (n.left) q.enQueue(n.left) if (n.right) q.enQueue(n.right) } } ``` 下面介绍如何从树中寻找最大值、最小值，因为二分搜索树的特性，所以最小值一定在根节点的最左侧，最大值相反 ``` getMin() { return this._getMin(this.root).value } _getMin(node) { if (node.left) return this._getMin(node.left) return node } getMax() { return this._getMax(this.root).value } _getMax(node) { if (node.right) return node.right return node } ``` 向上取整，向下取整，这两个操作是相反的，所以代码也是类似的，这里只介绍如何向下取整，既然是向下取整，那么根据二分搜索树的特性，值一定在根节点的左侧，只需要一直遍历左子树直到大年节点的值不再大于等于需要的值，然后判断节点是否还拥有右子树，如果有的话，继续上面的递归遍历 ``` floor(v) { let node = this._floor(this.root, v) return node ? node.value : null } _floor(node, v) { if (!node) return null if (node.value === v) return node // 如果当前节点值还比需要的大，就继续递归 if (node.value > v) { return this._floor(node.left, v) } // 判断当前节点是否拥有右子树 let rihgt = this._floor(node.right, v) if (right) return right return node } ``` 排名，这是用于获取给定值的排名或者排名第几节点的值，这两个操作也是相反的，所以这个只介绍如何获取排名第几的节点的值，对于这个操作而言，我小略微的改造代码，让每个节点拥有一个size属性，该属性表示该节点下有多少子节点（包含自身） ``` class Node { constructor(value) { this.value = value this.left = null this.right = null // 修改代码 this.size = 1 } } // 新增代码 _getSize(node) { return node ? node.size : 0 } _addChild(node, v) { if (!node) { return new Node(v) } if (node.value > v) { // 修改代码 node.size++ node.left = this._addChild(node.left, v) } else if (node.value < v) { // 修改代码 node.size++ node.right = this._addChild(node.right, v) } return node } select(k) { let node = this._select(this.root, k) return node ? node.value : null } _select(node, k) { if (!node) return null // 先获取左子树下有几个节点 let size = node.left ? node.left.size : 0 // 判断 size 是否大于 k // 如果大于 k，代表所需要的节点在左节点 if (size > k) return this._select(node.left, k) // 如果小于 k，代表所需要的节点在右节点 // 注意这里需要重新计算 k，减去根节点除了右子树的节点数量 if (size < k) return this._select(node.right, k - size - 1) return node } ``` 下面是二分搜索树中最难实现的部分，删除节点，因为对于删除节点来说，会存在一下集中情况 1. 需要删除的节点没有字树 2. 需要删除的节点只有一条子树 3. 需要删除的节点有两条子树对于前两种情况很好解决，但是第三种情况就有难度了，所以先来实现想对简单的操作，删除最小节点，对于删除最小节点来说，是不存在第三种情况的，删除最大节相反 ``` delectMin() { this.root = this._delectMin(this.root) console.log(this.root) } _delectMin(node) { // 一直递归左子树，如果左子树为空就判断是否有右子树 // 如果有右子树就把需要删除的几点替换为右子树 if (node != null && !node.left) return node.right node.left = this._deleteMin(node.left) // 最后需要维护节点下的size node.size = this._getSize(node.left) + this._getSize(node.right) + 1 return node } ``` 最后讲解的就是如何删除任意节点了。对于这个操作，T.Hibbard 在 1962 年提出了解决这个难题的办法，也就是如何解决第三种情况。当遇到这种情况时，需要取出当前节点的后继节点（也就是当前节点右子树的最小节点）来替换需要删除的节点。然后将需要删除节点的左子树赋值给后继结点，右子树删除后继结点后赋值给他。你如果对于这个解决办法有疑问的话，可以这样考虑。因为二分搜索树的特性，父节点一定比所有左子节点大，比所有右子节点小。那么当需要删除父节点时，势必需要拿出一个比父节点大的节点来替换父节点。这个节点肯定不存在于左子树，必然存在于右子树。然后又需要保持父节点都是比右子节点小的，那么就可以取出右子树中最小的那个节点来替换父节点。 ``` delect(v) { this.root = this._delect(this.root, v); } _delect(node, v) { if (!node) { return null } // 寻找的节点比当前节点小，去左子树找 if (node.vlaue < v) { node.right = this._delect(node.right, v) } else if (node.value > v) { node.left = this._delect(node.left, v) } else { if (!node.left) return ndoe.right if (!node.right) return node.left let min = this._getMin(node.right); min.right = this._delectMin(node.right) min.left = node.left node = min } node.size = this._getSize(node.left) + this._getSize(node.right) + 1 return node } ```