# js_data_structure_ algorithm **Repository Path**: bufanxy/js_data_structure_algorithm ## Basic Information - **Project Name**: js_data_structure_ algorithm - **Description**: javascript数据结构和算法代码示例 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2023-01-02 - **Last Updated**: 2023-05-08 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ## 什么是数据结构？ > 数据结构是[计算机](https://baike.baidu.com/item/计算机/140338?fromModule=lemma_inlink)存储、组织[数据](https://baike.baidu.com/item/数据?fromModule=lemma_inlink)的方式。数据结构是指相互之间存在一种或多种特定关系的[数据元素](https://baike.baidu.com/item/数据元素/715313?fromModule=lemma_inlink)的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储[效率](https://baike.baidu.com/item/效率/868847?fromModule=lemma_inlink)。数据结构往往同高效的检索[算法](https://baike.baidu.com/item/算法/209025?fromModule=lemma_inlink)和[索引](https://baike.baidu.com/item/索引/5716853?fromModule=lemma_inlink)技术有关。-- 百度百科 ## 常见的数据结构有哪些？ > 在[计算机科学](https://baike.baidu.com/item/计算机科学/9132?fromModule=lemma_inlink)的发展过程中，数据结构也随之发展。程序设计中常用的数据结构包括如下几个。 ![image-20221229152020816](C:\Users\bufanjun-office\AppData\Roaming\Typora\typora-user-images\image-20221229152020816.png) ## 数组(Array) > [数组](https://baike.baidu.com/item/数组/3794097?fromModule=lemma_inlink)是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。数组还可以有一维、二维以及多维等表现形式。 ### 为什么使用数组？ 假如有这样一个需求：保存所在城市每个月的平均温度。可以这么做： ```javascript const averageTempJan = 31.9; const averageTempFeb = 35.3; const averageTempMar = 42.4; const averageTempApr = 52; const averageTempMay = 60.8; ``` 当然，这肯定不是最好的方案。这样需要保存很多变量，当然如果有了数组，我们可用这样： ```javascript const averageTemp = []; averageTemp[0] = 31.9; averageTemp[1] = 35.3; averageTemp[2] = 42.4; averageTemp[3] = 52; averageTemp[4] = 60.8; ``` ![image-20221229162451464](C:\Users\bufanjun-office\Desktop\数据结构和算法\image-20221229162451464.png) 当然关于数组的操作我们不再赘述，大家用的比较多。 ## 栈(Stack) > [栈](https://baike.baidu.com/item/栈/12808149?fromModule=lemma_inlink)是一种特殊的[线性表](https://baike.baidu.com/item/线性表/3228081?fromModule=lemma_inlink)，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出 LIFO（last in first out）或先进后出 (FILO) 的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。 ### 定义 - 是一种特殊的线性表，这种表只能在固定的一端进行插入与删除操作。 - 固定插入的一端叫**栈顶(top)**，而另一端称为**栈底(bottom)**。位于栈顶和栈底的元素分别称为**顶元**和**底元**。当表中无元素时，称为空栈 比如浏览器的浏览器记录，回退和向前就是栈的数据结构。 ![image-20221229170306289](C:\Users\bufanjun-office\Desktop\数据结构和算法\image-20221229170306289.png) ### 定义栈的方法 - `push()` 添加一个新元素到栈顶位置。 - `pop()` 移除栈顶的元素，同时返回被移除的元素。 - `peek()` 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。 - `isEmpty()` 如果栈里没有任何元素就返回 `true`，否则返回 `false`。 - `size()` 返回栈里的元素个数。这个方法和数组的 `length` 属性类似。 - `toString()` 将栈结构的内容以字符串的形式返回。 ### 代码封装 ```javascript // 构造方法 function Stack() { // 集合 this.items = []; } // - `push()` 添加一个新元素到栈顶位置。 Stack.prototype.push = function (item) { return this.items.push(item); } // - `pop()` 移除栈顶的元素，同时返回被移除的元素。 Stack.prototype.pop = function () { return this.items.pop(); } // - `peek()` 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。 Stack.prototype.peek = function () { return this.items[this.items.length - 1]; } // - `isEmpty()` 如果栈里没有任何元素就返回 `true`，否则返回 `false`。 Stack.prototype.isEmpty = function () { return this.items.length === 0; } // - `size()` 返回栈里的元素个数。这个方法和数组的 `length` 属性类似。 Stack.prototype.size = function () { return this.items.length; } // - `toString()` 将栈结构的内容以字符串的形式返回。 Stack.prototype.toString = function () { let str = ''; for (var i = 0; i < this.items.length; i++) { str += ',' + this.items[i]; } // 去掉第一个逗号 str = str.substring(1); return str; } module.exports = Stack; ``` ### 测试代码 ```javascript const Stack = require('./01-stack_es5'); // 构造实例对象 const myStack = new Stack(); // 按顺序入栈 myStack.push(6); myStack.push(5); myStack.push(3); console.log(myStack.items); // [ 6, 5, 3 ] // pop() 出栈 console.log(myStack.pop()); // 3 // peek() 返回栈顶元素 console.log(myStack.peek()); // 5 // isEmpty() 是否为空 console.log(myStack.isEmpty()); // false // size() 返回大小 console.log(myStack.size()); // 2 // toString() 转换字符串 console.log(myStack.toString()); // "6,5" ``` ### 栈的应用 题目： [力扣20](https://leetcode.cn/problems/valid-parentheses/) 题目描述： 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。1<= s.length <=10^4 , s仅有括号'{}[]()'组成。 有效字符串需满足： 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 3. 每个右括号都有一个对应的相同类型的左括号。 ```javascript //示例 输入：s = "()" 输出：true 输入：s = "()[]{}" 输出：true 输入：s = "(]" 输出：false ``` ### 解题 ```javascript // commonJs规范引入Stack，实际运行可自行选择commonJs或者es6 const Stack = require('./01-stack_es5'); /** * * @param {*} str 比如：{}()()[] * @returns boolean类型 */ function isValid(str) { // 构建一个栈 var stack = new Stack(); // 遍历字符串 for (var i = 0; i < str.length; i++) { // 当前元素 var current = str[i]; if (current == '{') { stack.push('}'); } else if (current == '(') { stack.push(')'); } else if (current == '[') { stack.push(']'); } else { // 遇到右括号,判断栈顶元素是否和当前括号相同即可 // 同时出栈 var stackTop = stack.pop(); // 只要有一个顺序不同，则返回false if (current !== stackTop) { return false; } } } // 如果栈最终为空，说明字符串完全符合规则。 return !stack.isEmpty(); } console.log(isValid('()[]{}')); // true console.log(isValid('()[(')); // false ``` ## 队列(Queue) > [队列](https://baike.baidu.com/item/队列/14580481?fromModule=lemma_inlink)和栈类似，也是一种特殊的线性表。和栈不同的是，队列遵循先进先出原则（FIFO），队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。 ![image-20221229174312337](C:\Users\bufanjun-office\Desktop\数据结构和算法\image-20221229174312337.png) ### 定义 - 只允许在表的前端（front）进行删除操作。 - 只允许在表的后端（rear）进行插入操作。 ![image-20221229175418834](C:\Users\bufanjun-office\Desktop\数据结构和算法\image-20221229175418834.png) ### 定义队列的方法 - `enqueue(element)` 向队列尾部添加一个（或多个）新的项。 - `dequeue()` 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。 - `front()` 返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Map 类的 peek 方法非常类似）。 - `isEmpty()` 如果队列中不包含任何元素，返回 true，否则返回 false。 - `size()` 返回队列包含的元素个数，与数组的 length 属性类似。 - `toString()` 将队列中的内容，转成字符串形式。 ### 代码封装 ```javascript // 定义队列的构造方法 function Queue() { // 队列的容器 this.items = []; } // enqueue(element) 向队列尾部添加一个（或多个）新的项。 Queue.prototype.enqueue = function (item) { return this.items.push(item); } // dequeue() 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。 Queue.prototype.dequeue = function () { return this.items.unshift(); } // front() 返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Map 类的 peek 方法非常类似）。 Queue.prototype.front = function () { return this.items[0]; } // isEmpty() 如果队列中不包含任何元素，返回 true，否则返回 false。 Queue.prototype.isEmpty = function () { return this.items.length === 0; } // size() 返回队列包含的元素个数，与数组的 length 属性类似。 Queue.prototype.size = function () { return this.items.length; } // toString() 将队列中的内容，转成字符串形式。 Queue.prototype.toString = function () { let str = '' for (let i = 0; i < this.items.length; i++) { str += ',' + this.items[i]; } // 去掉第一个逗号 str = str.substring(1); return str; } module.exports = Queue; ``` ### 测试代码 ```javascript const Queue = require('./01-queue_es5'); // 构造实例对象 const myQueue = new Queue(); // 按顺序进入队列 myQueue.enqueue(6); myQueue.enqueue(5); myQueue.enqueue(3); console.log(myQueue.items); // [ 6, 5, 3 ] // dequeue() 出队列 console.log(myQueue.dequeue()); // 6 // front() 返回对头元素 console.log(myQueue.front()); // 5 // isEmpty() 是否为空 console.log(myQueue.isEmpty()); // false // size() 返回大小 console.log(myQueue.size()); // 2 // toString() 转换字符串 console.log(myQueue.toString()); // "5,3" ``` ### 队列的应用 [力扣387](https://leetcode.cn/problems/first-unique-character-in-a-string/) 题目描述： 给定一个字符串 `s` ，找到 *它的第一个不重复的字符，并返回它的索引* 。如果不存在，则返回 `-1` 。1<= s.length ，只包含小写字母。 ```javascript 示例 1： 输入: s = "leetcode" 输出: 0 示例 2: 输入: s = "loveleetcode" 输出: 2 示例 3: 输入: s = "aabb" 输出: -1 ``` ### 解题 **思路一：** 遍历字符串把字符串变成对象，key为字符本身，value为出现的位置。如果重复出现，则value变成-1；因为属性是无序的，谁是第一位？则需要对属性进行遍历，找到value值不是-1且最小的一位就是第一次出现的不重复数。 ```javascript 输入: s = "leetcode" 输出: 0 // 形成对象，对属性进行遍历找到值最小的且！=-1的。（思路：选择排序） var obj = { l: 0, e: -1, t: 3, c: 4, o: 5, d: 6 } ``` **思路二：** 思路着实有点难，需要有相当的想象力。总结一句话“秋后算账”。 ```javascript const Queue = require('./01-queue_es5'); /** * 找到字符串第一个不重复字符 * @param {*} str * @returns 返回符合条件的字符下标，如果找不到返回-1 */ function firstUniqChar(str) { // 创建哈希映射 const map = {}; // 创建队列 const queue = new Queue(); // 对str进行遍历 for (let i = 0; i < str.length; i++) { // 当前元素 let current = str[i]; // 如果不存在，则加入映射。 这里注意0会被判定为false的问题。 if (map[current] == null) { map[current] = i; // 同时把当前元素和下标加入队列，因为首次出现，可以作为预备人选（考察对象）。如果后续有问题，秋后算账。 queue.enqueue([current, i]); // console.log(queue.items); } else { // 当前元素不是第一次出现,则修改哈希表，把value变为-1 map[current] = -1; // 同时对队列（预备人选）进行排查，如果和当前元素相同，则立即出列（不再作为考察对象）。 // 这里要使用while检测，因为出队列，下一个对头也要进行考察。直到队列的某次对头暂时符合条件。 // 获取对头元素字符,比如 [[a,1],....] ==> a while (!queue.isEmpty() && map[queue.front()[0]] === -1) { // 不符合条件，出队列 queue.dequeue(); } } } // console.log(map); // console.log(queue.items); // 最后只要队列有一个数据经过了考验，则返回对头元素即可。否则全军覆没。 return !queue.isEmpty() ? queue.front()[1] : -1; } console.log(firstUniqChar('leetcode')); // 0 console.log(firstUniqChar('loveleetcode')); // 2 console.log(firstUniqChar('hahabufanxueyuan')); // 4 ``` ## 链表(Linked List)：单向链表 > [链表](https://baike.baidu.com/item/链表/9794473?fromModule=lemma_inlink)是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。 ### 为什么用链表？ 要存储多个元素，数组（或列表）可能是最常用的数据结构。然而，这种数据结构有一个缺点：（在大多数语言中）数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。（尽管我们已经学过，JavaScript有来自Array类的方法可以帮我们做这些事，但背后的情况同样如此。）链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展示了一个链表的结构。 ![image-20221229203515540](C:\Users\bufanjun-office\Desktop\数据结构和算法\image-20221229203515540.png) 还有一个可能是用来说明链表的最流行的例子，那就是火车。一列火车是由一系列车厢（也称车皮）组成的。每节车厢或车皮都相互连接。你很容易分离一节车皮，改变它的位置、添加或移除它。下图演示了一列火车。每节车皮都是链表的元素，车皮间的连接就是指针。 ![image-20221229205513892](C:\Users\bufanjun-office\Desktop\数据结构和算法\image-20221229205513892.png) ### 定义链表的方法 + push(element)：向链表尾部添加一个新元素。 + insert(element, position)：向链表的特定位置插入一个新元素。 + getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined。 + remove(element)：从链表中移除一个元素。 + indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。 + removeAt(position)：从链表的特定位置移除一个元素。❑ isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。 + isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。 + size()：返回链表包含的元素个数，与数组的length属性类似。 + toString()：返回表示整个链表的字符串。由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。 ### 代码封装 #### 1. 定义LinkedList和Node + LinkedList为链表本身 + Node为链表中的某个元素 ```javascript // 两个构造函数 function LinkList() { // 定义初始长度为0 this.length = 0; // 定义head为第一个节点 this.head = null; } function Node(data) { this.data = data; this.next = null; } ``` #### 2. 方法 push(element) ![image-20221229212547081](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221229212547081.png) ```javascript // + push(data)：向链表尾部添加一个新元素。 LinkList.prototype.push = function (data) { const node = new Node(data); let current; if (this.head == null) { this.head = node; } else { // 遍历链表，找到最后一项 current = this.head; while (current.next) { current = current.next; } // 此时current为最后一个元素，在后面追加新元素 current.next = node; } this.length++; } ``` #### 3. 方法 getElementAt(index) ```javascript // + getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined。 LinkedList.prototype.getElementAt = function (index) { // 处理下标越界 if (index < 0 || index >= this.length) return null; let current = this.head; if (index === 0) return current; for (var i = 1; i < index; i++) { current = current.next; } return current; } ``` #### 4. 方法 removeAt(index) ![image-20221229214400629](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221229214400629.png) ```javascript // + removeAt(index)：从链表的特定位置移除一个元素,返回被删除的元素本身 LinkedList.prototype.removeAt = function (index) { // 处理下标越界 if (index < 0 || index >= this.length) return null; let current = this.head; // 移除第一项 if (index === 0) { this.head = current.next; } else { // 如果不是第一项，则应该找到前面的节点和后面的节点 preNode = this.getElementAt(index - 1); current = preNode.next; // 跳过当前元素.把当前元素去除，则应该preNode的next指向下一个元素 preNode.next = current.next; } // 修改长度 this.length--; // 返回被删除的元素本身 return current.data; } ``` #### 5. 方法 insert(data, index) ![image-20221229220845164](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221229220845164.png) ```javascript // + insert(data, index)：向链表的特定位置插入一个新元素。 LinkedList.prototype.insert = function (data, index) { // 下标越界 if (index < 0 || index > this.length) return false; const node = new Node(data); // head节点 if (index === 0) { // 修改当前node的下一个节点为原来的head节点 node.next = this.head; this.head = node; // 在最后面插入一个节点 } else if (index === this.length) { // 找到最后的元素 const lastNode = this.getElementAt(this.length - 1); lastNode.next = node; } else { // 在中间位置插入元素 // 找到之前index对应的元素的前一个元素 const preNode = this.getElementAt(index - 1); // 找到当前元素 const current = preNode.next; // 重新构建链表 preNode.next = node; node.next = current; } // 修改链表长度 this.length++; return true; } ``` #### 6. 方法 indexOf(node) ```javascript // + indexOf(node)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。 LinkedList.prototype.indexOf = function (node) { let current = this.head; // 假设发现下标为 -1； let index = -1; for (var i = 0; i < this.length; i++) { // TODO: 相等的条件是什么？ // 这里使用元素node的地址做比较，当然我们可以自定义比较函数，那么需要在LinkedList构造函数传递 // 如果采用自定义比较： this.eqFn(current,node) if (current === node) { return i; } current = current.next; } return -1; } // 补充:如果需要自定义比较函方法 // 两个构造函数 function LinkList(eqFn) { // 定义初始长度为0 this.length = 0; // 定义head为第一个节点 this.head = null; this.eqFn = eqFn; } const linkedList = new LinkedList((a,b)=> a.id === b.id); ``` #### 7. 方法 remove(node) ```javascript // + remove(node)：从链表中移除一个元素，返回新链表的长度。 LinkedList.prototype.remove = function (node) { let current = this.head; // 如果移除的是head节点，则直接把head指向下一个节点 if (current === node) { this.head = current.next; this.length--; } for (var i = 0; i < this.length; i++) { let preNode = current; current = current.next; // 如果是中间节点,则直接跳过当前节点 if (current === node) { // 如果current是null,说明需要移除最后一个节点。 preNode.next = current ? current.next : null; this.length--; } } // 最终返回删除元素后的新长度 return this.length; } ``` #### 8. 方法 isEmpty() ```javascript // + isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。 LinkedList.prototype.isEmpty = function () { return this.length === 0; } ``` #### 9. 方法 size() ```javascript // + size()：返回链表包含的元素个数，与数组的length属性类似。 LinkedList.prototype.size = function () { return this.size()===0 ; } ``` #### 10. 方法 toString() ```javascript // + toString()：返回表示整个链表的字符串。由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。 LinkedList.prototype.toString = function () { let current = this.head; let str = ''; while (current.next) { str += current.next.data + ''; current = current.next; } return str; } ``` ### 测试代码 ```javascript const LinkedList = require('./01-linked_es5'); const linkedList = new LinkedList(); // 用基本数据类型构建最简单的链表，实际开发中如果遇到，往往都是对象类型，而且必须重写isEqFn for (var i = 0; i < 5; i++) { // 添加到链表 linkedList.push(i); } // 测试 // console.log(linkedList); // 测试 getElementAt(index); console.log(linkedList.getElementAt(2)); // 测试 removeAt(index); linkedList.removeAt(1); //如果删除下标为1的元素，则下标为0的元素的next应该是node = 2 ; linkedList的长度应该-1 console.log(linkedList.getElementAt(0), linkedList.length); // {data:1,next: {data : 2}}, 4 // 测试 insert(data, index) // 在下标2的位置插入data9 ，则下标1的下一位应该是data9 ;下标3的位置应该是data2 linkedList.insert(9, 2); console.log(linkedList.getElementAt(1), linkedList.getElementAt(2)); // {data: 0},{data:9} // 这里只做了最重要的几个测试，其余的几个方法比较简单，可以自行测试。 ``` ### 完整代码 ```javascript function LinkedList() { // 定义初始长度为0 this.length = 0; // 定义head为第一个节点 this.head = null; } // + push(data)：向链表尾部添加一个新元素。 LinkedList.prototype.push = function (data) { const node = new Node(data); let current; if (this.head == null) { this.head = node; } else { // 遍历链表，找到最后一项 current = this.head; while (current.next) { current = current.next; } // 此时current为最后一个元素，在后面追加新元素 current.next = node; } this.length++; } // + insert(data, index)：向链表的特定位置插入一个新元素。 LinkedList.prototype.insert = function (data, index) { // 下标越界 if (index < 0 || index > this.length) return false; const node = new Node(data); // head节点 if (index === 0) { // 修改当前node的下一个节点为原来的head节点 node.next = this.head; this.head = node; // 在最后面插入一个节点 } else if (index === this.length) { // 找到最后的元素 const lastNode = this.getElementAt(this.length - 1); lastNode.next = node; } else { // 在中间位置插入元素 // 找到之前index对应的元素的前一个元素 const preNode = this.getElementAt(index - 1); // 找到当前元素 const current = preNode.next; // 重新构建链表 preNode.next = node; node.next = current; } // 修改链表长度 this.length++; return true; } // + getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined。 LinkedList.prototype.getElementAt = function (index) { // 处理下标越界 if (index < 0 || index >= this.length) return null; let current = this.head; if (index === 0) return current; for (var i = 1; i < index; i++) { current = current.next; } return current; } // + remove(element)：从链表中移除一个元素，返回新链表的长度。 LinkedList.prototype.remove = function (node) { let current = this.head; // 如果移除的是head节点，则直接把head指向下一个节点 if (current === node) { this.head = current.next; this.length--; } for (var i = 0; i < this.length; i++) { let preNode = current; current = current.next; // 如果是中间节点,则直接跳过当前节点 if (current === node) { // 如果current是null,说明需要移除最后一个节点。 preNode.next = current ? current.next : null; this.length--; } } // 最终返回删除元素后的新长度 return this.length; } // + indexOf(node)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。 LinkedList.prototype.indexOf = function (node) { let current = this.head; for (var i = 0; i < this.length; i++) { // TODO: 相等的条件是什么？ // 这里使用元素node的地址做比较，当然我们可以自定义比较函数，那么需要在LinkedList构造函数传递 if (current === node) { return i; } current = current.next; } return -1; } // + removeAt(index)：从链表的特定位置移除一个元素。 LinkedList.prototype.removeAt = function (index) { // 处理下标越界 if (index < 0 || index >= this.length) return null; let current = this.head; // 移除第一项 if (index === 0) { this.head = current.next; } else { // 如果不是第一项，则应该找到前面的节点和后面的节点 preNode = this.getElementAt(index - 1); current = preNode.next; // 跳过当前元素.把当前元素去除，则应该preNode的next指向下一个元素 preNode.next = current.next; } // 修改长度 this.length--; // 返回被删除的元素本身 return current.data; } // + isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。 LinkedList.prototype.isEmpty = function () { return this.length === 0; } // + size()：返回链表包含的元素个数，与数组的length属性类似。 LinkedList.prototype.size = function () { return this.size() === 0; } // + toString()：返回表示整个链表的字符串。由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。 LinkedList.prototype.toString = function () { let current = this.head; let str = ''; while (current.next) { str += current.next.data + ''; current = current.next; } return str; } function Node(data) { this.data = data; this.next = null; } module.exports = LinkedList; ``` ### 链表的应用 **题目：** [力扣876](https://leetcode.cn/problems/middle-of-the-linked-list/) **题目描述：** 给定一个头结点为 `head` 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。节点数[1,100]。 ``` 示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。 ``` #### 解题 > 问题的关键也在于我们⽆法直接得到单链表的⻓度 `n`，常规⽅法也是先遍历链表计算 `n`，再遍历⼀次得到第 `n / 2` 个节点，也就是中间节点。如果想⼀次遍历就得到中间节点，也需要耍点⼩聪明，使⽤「快慢指针」的技巧：我们让两个指针 `slow` 和 `fast` 分别指向链表头结点 `head`。每当慢指针 `slow` 前进⼀步，快指针 `fast` 就前进两步，这样，当 `fast` ⾛到链表末尾时，`slow` 就指向了链表中点。 ```javascript const LinkedList = require('./01-linked_es5'); // 定义链表的长度，这里需要测试奇数和偶数 const count = 10; const linkedList = new LinkedList(); for (let i = 0; i < count; i++) { linkedList.push(i); } // 当count = 9 时，返回 {data: 4} // 当count = 10 时，返回 {data: 5},符合"如果有两个中间结点，则返回第二个中间结点" console.log(middleNode(linkedList)); function middleNode(lk) { // 快慢指针 let slow = lk.head; let fast = lk.head; // 慢指针每次走 1步，快指针每次走 2步； while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 慢指针就是中间位置 return slow; } ``` ### 链表(Linked List): 双向链表 #### 定义 双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素，如下图所示。 ![image-20221230105947694](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221230105947694.png) #### 说明 双向链表和单向链表基本相同，只是每个节点多了一个prev指针指向前面的元素节点。 代码不再赘述，如果你理解了前面的单向链表封装，实现双向链表自然不再话下。 ​ ## 树(Tree) > [树](https://baike.baidu.com/item/树/2699484?fromModule=lemma_inlink)是典型的非线性结构，它是包括，2个结点的有穷集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个后继结点，m≥0。 树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱，或是公司的组织架构图，如下图所示。 ![image-20221230143722584](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221230143722584.png) ### 树的相关术语 一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点： ![image-20221230143814162](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221230143814162.png) - 节点的度（Degree）：节点的子树个数，比如节点 11 的度为 2； - 树的度：树的所有节点中最大的度数，如上图树的度为 2； - 叶节点（Leaf）：度为 0 的节点（也称为叶子节点），如上图的 3，6，8，10...等； - 父节点（Parent）：如上图节点 5 是节点 3 和 6 的父节点； - 子节点（Child）：3 和 6 是 5 的子节点； - 兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点，比如上图的 3 和 6，5 和 9 互为兄弟节点； - 路径和路径长度：路径指的是一个节点到另一节点的通道，路径所包含边的个数称为路径长度，比如 3 > 11 的路径长度为 3； - 节点的层次（Level）：规定根节点在 1 层，其他任一节点的层数是其父节点的层数加 1。如 7 和 15 节点的层次为 2； - 树的深度（Depth）：树种所有节点中的最大层次是这棵树的深度，如上图树的深度为 4； ### 定义 这里我们主要说二叉树。 **二叉树**中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这个定义有助于我们写出更高效地在树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用非常广泛。 **二叉搜索树（BST**）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。上一节的图中就展现了一棵二叉搜索树。二叉树的查找效率非常高，所以二叉搜索树将是我们要在本章研究的数据结构。 ![image-20221230145240371](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\linked\image-20221230145240371.png) ### 定义树的方法 值得注意的一个小细节是，不同于在之前的章节中将节点本身称作节点或项，我们将会称其为**键**。键是树相关的术语中对节点的称呼。 + insert(key)：向树中插入一个新的键。 + search(key)：在树中查找一个键。如果节点存在，则返回true；如果不存在，则返回false。 + inOrderTraverse()：通过中序遍历方式遍历所有节点。 + preOrderTraverse()：通过先序遍历方式遍历所有节点。 + postOrderTraverse()：通过后序遍历方式遍历所有节点。 + min()：返回树中最小的值/键。 + max()：返回树中最大的值/键。 + remove(key)：从树中移除某个键。 ### 代码封装 > 树的种类有很多，这里主要讨论搜索二叉树（BST) 的实现和运用。BST二叉树的条件如下： > > 1. 非空左子树的所有键值小于其根节点的键值； > 2. 非空右子树的所有键值大于其根节点的键值； > 3. 左、右子树本身也都是二叉搜索树； #### 1. 定义BST构造函数 ```javascript /** * 定义树的节点 * @param {*} key */ function Node(key) { this.key = key; // 节点值 this.left = null; // 左侧子节点 this.right = null; // 右侧子节点 } /** * 定义二叉树的构造方法 * @param {*} compareFn(a,b) 接受一个函数，用于自定义节点（键）的比较. * compareFn会对a和b进行比较，如果满足a>b返回1；a==b返回0；ab返回1；a==b返回0；a 中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访问所有节点。 ![image-20221230163250549](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\tree\image-20221230163250549.png) ```javascript // + inOrderTraverse(callback)：通过中序遍历方式遍历所有节点。 BinarySearchTree.prototype.inOrderTraverse = function (callback) { inOrderTraverseNode(this.root, callback); // 必须递归，辅助函数 function inOrderTraverseNode(node, callback) { if (node != null) { // 从左边进行遍历 inOrderTraverseNode(node.left, callback); // 处理当前节点 callback(node.key); // 从右边开始 inOrderTraverseNode(node.right, callback); } } } ``` ##### 3.1 测试代码 ```javascript // 测试中序遍历 const arr = []; bst.inOrderTraverse(function (v) { arr.push(v); }) console.log(arr); // [ 3, 5, 7, 8, 9, 11, 15 ] ``` #### 4. 先序遍历 preOrderTraverse() > 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。 ![image-20221230163940494](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\tree\image-20221230163940494.png) ```javascript // + preOrderTraverse(callback)：通过先序遍历方式遍历所有节点。 BinarySearchTree.prototype.preOrderTraverse = function (callback) { preOrderTraverseNode(this.root, callback); // 用于递归的辅助方法 function preOrderTraverseNode(node, callback) { if (node != null) { // 先打印当前,再左再右 callback(node.key); preOrderTraverseNode(node.left, callback); preOrderTraverseNode(node.right, callback); } } } ``` ##### 4.1 测试代码 ```javascript // 测试中序遍历 const arr = []; // bst.inOrderTraverse(function (v) { // arr.push(v); // }) bst.preOrderTraverse(function (v) { arr.push(v); }) console.log(arr); // 中序遍历结果：[ 3, 5, 7, 8, 9, 11, 15 ] console.log(arr); // 先序遍历结果：[ 11, 7, 5, 3, 9, 8, 15 ] ``` #### 5. 后序遍历 postOrderTraverse() > 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。 ![image-20221230164424800](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\tree\image-20221230164424800.png) ```javascript // + postOrderTraverse()：通过后序遍历方式遍历所有节点。 BinarySearchTree.prototype.postOrderTraverse = function (callback) { postOrderTraverseNode(this.root, callback); // 用于递归的辅助方法 function postOrderTraverseNode(node, callback) { if (node != null) { postOrderTraverseNode(node.left, callback); postOrderTraverseNode(node.right, callback); callback(node.key); } } } ``` ##### 5.1 测试代码 ```javascript bst.postOrderTraverse(function (v) { arr.push(v); }) // console.log(arr); // 中序遍历结果：[ 3, 5, 7, 8, 9, 11, 15 ] // console.log(arr); // 先序遍历结果：[ 11, 7, 5, 3, 9, 8, 15 ] console.log(arr); // 后序遍历结果：[ 3, 5, 8, 9, 7, 15, 11 ] ``` #### 6. 方法min() > 对于BST结构一眼就能看到最小值和最大值。 ![image-20221230165323487](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\tree\image-20221230165323487.png) ```javascript // + min()：返回树中最小的值/键。 BinarySearchTree.prototype.min = function () { return minNode(this.root); function minNode(node) { let currnt = node; // 直接找寻左子节点就是最小值 while (node != null & node.left != null) { currnt = currnt.left; } return currnt; } } ``` #### 7. 方法max() > 对于BST结构一眼就能看到最小值和最大值。 ![image-20221230165323487](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\tree\image-20221230165323487.png) ```javascript // + max()：返回树中最大的值/键。 BinarySearchTree.prototype.max = function () { return maxNode(this.root); function maxNode(node) { let currnt = node; while (node != null && node.right != null) { currnt = node.right; } return currnt; } } ``` #### 8. 方法search() > seach可以跟据构造函数中定义到comperFn来对比值，从而确定下一个比较的是左子键还是又子键。 ```javascript /** * 定义二叉树的构造方法 * @param {*} compareFn(a,b) 接受一个函数，用于自定义节点（键）的比较. * compareFn会对a和b进行比较，如果满足a>b返回1；a==b返回0；a remove这个方法的实现比较复杂，不是单纯的移除某个键，而是移除当前键的同时要保留其余的键（包括曾经属于这个键的子树）。保留的键被合并到当前节点后也要符合满足BST树的规则。 **情况分析：** 1. 删除的是叶子节点（没有左右子树）； 2. 删除的节点只有单个子节点； 3. 删除的节点同时存在两个子节点； ![image-20221231112149922](C:\Users\bufanjun-office\Desktop\数据结构和算法\imgs\tree\image-20221231112149922.png) ```javascript // + remove(key)：从树中移除某个键。 BinarySearchTree.prototype.remove = function (key) { const that = this; this.root = removeNode(this.root, key); // 递归辅助函数 function removeNode(node, key) { if (node == null) return null; // 去左子树找 if (that.compareFn(key, node.key) === -1) { node.left = removeNode(node.left, key); return node; } else if (that.compareFn(key, node.key) === 1) { node.right = removeNode(node.right, key); return node; // 相等。 } else { // 1. 如果是叶子节点，直接删除 if (node.left == null && node.right == null) { node = null; return node; } // 2. 如果只有左子树或者右子树 if (node.right == null) { node = node.left; return node; } else if (node.left == null) { node = node.right; return node; } // 3. 如果同时存在两个子树 // 3.1 规律是从左子树找到最大值的键替换当前键 // 3.2 或者从右子树找到最小值的键替换当前键 const minNodeRight = that.min(node.right); node.key = minNodeRight.key; // 删除这个键 that.removeNode(node.right, minNodeRight.key); return node; } } } // 测试: // 测试remove() bst.remove(5); console.log(JSON.stringify(bst)); // 返回结果满足条件 ``` ### 完整代码 ```javascript /** * 定义树的节点 * @param {*} key */ function Node(key) { this.key = key; // 节点值 this.left = null; // 左侧子节点 this.right = null; // 右侧子节点 } /** * 定义二叉树的构造方法 * @param {*} compareFn(a,b) 接受一个函数，用于自定义节点（键）的比较. * compareFn会对a和b进行比较，如果满足a>b返回1；a==b返回0；ab返回1；a==b返回0；a #### Adelson-Velskii-Landi树（AVL树） AVL树是一种自平衡树。添加或移除节点时，AVL树会尝试保持自平衡。任意一个节点（不论深度）的左子树和右子树高度最多相差1。添加或移除节点时，AVL树会尽可能尝试转换为完全树。 #### 红黑树 和AVL树一样，红黑树也是一个自平衡二叉搜索树。AVL书插入和移除节点可能会造成旋转，所以我们需要一个包含多次插入和删除的自平衡树，红黑树是比较好的。如果插入和删除频率较低（我们更需要多次进行搜索操作），那么AVL树比红黑树更好。 在红黑树中，每个节点都遵循以下规则： + 顾名思义，每个节点不是红的就是黑的； + 树的根节点是黑的； + 所有叶节点都是黑的（用NULL引用表示的节点）； + 如果一个节点是红的，那么它的两个子节点都是黑的； + 不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点； + 从给定的节点到它的后代节点（NULL叶节点）的所有路径包含相同数量的黑色节点。 ## 图(Graph) > [图](https://baike.baidu.com/item/图/13018767?fromModule=lemma_inlink)是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。 ## 堆(Heap) > [堆](https://baike.baidu.com/item/堆/20606834?fromModule=lemma_inlink)是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。 ## 散列表(Hash) > 散列表源自于[散列函数](https://baike.baidu.com/item/散列函数/2366288?fromModule=lemma_inlink)(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。 ## 算法 1.1 枚举算法 「枚举算法」也称为穷举算法，是按照问题本身的性质一一列举出该问题所有可能的解。 1.2 递归算法 「递归」指的是一种通过重复将原问题分解为同类的子问题而解决的方法。 1.3 分治算法 「分治」就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 1.4 回溯算法 「回溯」是一种选优搜索方法，按选优条件进行深度优先搜索，以达到目标。 1.5 贪心算法 「贪心」是一种在每次决策时采用当前状态下最优或最好的策略，从而希望导致结果是最好或最优的算法。 1.6 位运算 「位运算」是针对二进制的运算，对每一个位进行布尔运算操作。 1.7 动态规划 「动态规划」与分治法相似，都是通过组合子问题的解来求解原问题答案，将问题划分为互不相交的子问题，递归的求解子问题，最后合并子问题的答案。