关于javascript:窥探数据结构的世界-ES6版

1. 什么是数据结构？

数据结构是在计算机中组织和存储数据的一种非凡形式，使得数据能够高效地被拜访和批改。更确切地说，数据结构是数据值的汇合，示意数据之间的关系，也包含了作用在数据上的函数或操作。

1.1 为什么咱们须要数据结构？

• 数据是计算机科学当中最要害的实体，而数据结构则能够将数据以某种组织模式存储，因而，数据结构的价值显而易见。
• 无论你以何种形式解决何种问题，你都须要解决数据——无论是波及员工薪水、股票价格、购物清单，还是只是简略的电话簿问题。
• 数据须要依据不同的场景，依照特定的格局进行存储。有很多数据结构可能满足以不同格局存储数据的需要。

1.2 八大常见的数据结构

1. 数组：Array
2. 堆栈：Stack
3. 队列：Queue
4. 链表：Linked Lists
5. 树：Trees
6. 图：Graphs
7. 字典树：Trie
8. 散列表（哈希表）：Hash Tables

在较高的档次上，基本上有三种类型的数据结构:

• 堆栈和队列是相似于数组的构造，仅在我的项目的插入和删除形式上有所不同。
• 链表，树，和图 构造的节点是援用到其余节点。
• 散列表依赖于散列函数来保留和定位数据。

在复杂性方面：

• 堆栈和队列是最简略的，并且能够从中构建链表。
• 树和图 是最简单的，因为它们扩大了链表的概念。
• 散列表和字典树 须要利用这些数据结构来牢靠地执行。

就效率而已：

• 链表是记录和存储数据的最佳抉择
• 而哈希表和字典树 在搜寻和检索数据方面成果最佳。

2. 数组 – 常识补充

数组是最简略的数据结构，这里就不讲过多了。
贴一张每个函数都运行 10,000 次迭代：

• 10,000 个随机密钥在 10,000 个对象的数组中查找的执行效率比照图：

[
  {
    id: "key0",
    content: "I ate pizza 0 times"
  },
  {
    id: "key1",
    content: "I ate pizza 1 times"
  },
  {
    id: "key2",
    content: "I ate pizza 2 times"
  },
  ...
]

["key284", "key958", "key23", "key625", "key83", "key9", ...]

2.1 for... in为何这么慢？

for... in语法令人难以置信的迟缓。在测试中就曾经比失常状况下慢近 9 倍的循环。

这是因为 for ... in 语法是第一个可能迭代对象键的 JavaScript 语句。

循环对象键（{}）与在数组（[]）上进行循环不同，

因为引擎会执行一些额定的工作来跟踪曾经迭代的属性。

3. 堆栈：Stack

堆栈是元素的汇合，能够在顶部增加我的项目，咱们有几个理论的堆栈示例：

• 浏览器历史记录
• 吊销操作
• 递归以及其它。

三句话解释堆栈：

1. 两个准则操作：push和 pop。Push 将元素增加到数组的顶部，而Pop 将它们从同一地位删除。
2. 遵循 ”Last In，First Out“，即：LIFO，后进先出。
3. 没了。

3.1 堆栈的实现。

请留神，下方例子中，咱们能够颠倒堆栈的程序：底部变为顶部，顶部变为底部。

因而，咱们能够别离应用数组 unshift 和shift办法代替 push 和pop。

class Stack {constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }

    push(...items) {
        return this.reverse
            ? this.stack.unshift(...items)
            : this.stack.push(...items);
    }
    
    pop() {return this.reverse ? this.stack.shift() : this.stack.pop();}
}

const stack = new Stack(4, 5);
stack.reverse = true;
console.log(stack.push(1, 2, 3) === 5) // true
console.log(stack.stack ===[1, 2, 3, 4, 5]) // true

4. 队列：Queue

在计算机科学中，一个队列 (queue) 是一种非凡类型的抽象数据类型或汇合。汇合中的实体按程序保留。

而在前端开发中，最驰名的队列应用当属浏览器 /NodeJs 中 对于宏工作与微工作，工作队列的常识。这里就不再赘述了。

在后端畛域，用得最宽泛的就是音讯队列：Message queue：如 RabbitMQ、ActiveMQ 等。

以编程思维而言，Queue能够用两句话形容：

• 只是具备两个次要操作的数组：unshift和pop。
• 遵循 "Fist In，first out" 即：FIFO，先进先出。

4.1 队列的实现

请留神，下方例子中，咱们能够颠倒堆队列的程序。

因而，咱们能够别离应用数组 unshift 和shift办法代替 push 和pop。

class Queue {constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ? this.queue.push(...items)
            : this.queue.unshift(...items);
    }

    dequeue() {return this.reverse ? this.queue.shift() : this.queue.pop();}
}

5. 链表：Linked Lists

与数组一样，链表是按顺序存储数据元素。

链表不是保留索引，而是指向其余元素。

第一个节点称为头部(head)，而最初一个节点称为尾部(tail)。

单链表与双向链表：

• 单链表是示意一系列节点的数据结构，其中每个节点指向列表中的下一个节点。
• 链表通常须要遍历整个操作列表，因而性能较差。
• 进步链表性能的一种办法是在每个节点上增加指向列表中上一个节点的第二个指针。
• 双向链表具备指向其前后元素的节点。

链表的长处：

• 链接具备常量工夫 插入和删除，因为咱们能够只更改指针。
• 与数组一样，链表能够作为堆栈运行。

链表的利用场景：

链接列表在客户端和服务器上都很有用。

• 在客户端上，像 Redux 就以链表形式构建其中的逻辑。
• React 外围算法 React Fiber的实现就是链表。

• • React Fiber之前的Stack Reconciler，是自顶向下的递归mount/update，无奈中断(继续占用主线程)，这样主线程上的布局、动画等周期性工作以及交互响应就无奈立刻失去解决，影响体验。
• • React Fiber解决过来 Reconciler 存在的问题的思路是把渲染 / 更新过程 (递归 diff) 拆分成一系列小工作，每次查看树上的一小部分，做完看是否还有工夫持续下一个工作，有的话持续，没有的话把本人挂起，主线程不忙的时候再持续。
• 在服务器上，像 Express 这样的 Web 框架也以相似的形式构建其中间件逻辑。当申请被接管时，它从一个中间件管道输送到下一个，直到响应被收回。

5.1 单链表实现

单链表的操作外围有：

• push（value） – 在链表的开端 / 头部增加一个节点
• pop（） – 从链表的开端 / 头部删除一个节点
• get（index） – 返回指定索引处的节点
• delete（index） – 删除指定索引处的节点
• isEmpty（） – 依据列表长度返回 true 或 false
• print（） – 返回链表的可见示意

class Node {constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {constructor() {
    this.head = null
    this.tail = null
    // 长度非必要
    this.length = 0
  }
  push(data) {
    // 创立一个新节点
    const node = new Node(data)
    // 查看头部是否为空
    if (this.head === null) {
      this.head = node
      this.tail = node
    } 
    this.tail.next = node
    this.tail = node
    this.length++
  }
  pop(){
    // 先查看链表是否为空
    if(this.isEmpty()) {return null} 
    // 如果长度为 1
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return this.tail
    }
    let node = this.tail
    let currentNode = this.head
    let penultimate
    
    while (currentNode) {if (currentNode.next === this.tail) {
        penultimate = currentNode
        break
      }
      currentNode = currentNode.next
    }
    
    penultimate.next = null
    this.tail = penultimate
    this.length --
    return node
  }
  
  get(index){
    // 解决边界条件
    if (index === 0) {return this.head}
    if (index < 0 || index > this.length) {return null}
    
    let currentNode = this.head
    let i = 0
    while(i < index) {
      i++
      currentNode = currentNode.next
    }
    return currentNode
    
  }
  delete(index){
    let currentNode = this.head
    
    if (index === 0) {
      let deletedNode
      currentNode.next = this.head
      deletedNode = currentNode
      this.length--
      
      return deletedNode
    }
    
    if (index < 0 || index > this.length) {return null}
    
    let i = 0
    let previous
    
    while(i < index) {
      i++
      previous = currentNode
      currentNode = currentNode.next
    }
    previous.next = currentNode.next
    this.length--
    return currentNode
  }
  
  isEmpty() {return this.length === 0}
  print() {const list = []
    let currentNode = this.head
    while(currentNode){list.push(currentNode.data)
      currentNode = currentNode.next
    }
    return list.join('=>')
  }
}

测试一下：

const l = new LinkedList()

// 增加节点
const values = ['A', 'B', 'C']
values.forEach(value => l.push(value))

console.log(l)
console.log(l.pop())
console.log(l.get(1))
console.log(l.isEmpty())
console.log(l.print())

5.2 双向链表实现

1. 双向链表的设计

相似于单链表，双向链表由一系列节点组成。每个节点蕴含一些数据以及指向列表中下一个节点的指针和指向前一个节点的指针。这是 JavaScript 中的简略示意：

class Node {constructor(data) {
        // data 蕴含链表项应存储的值
        this.data = data;
        // next 是指向列表中下一项的指针
        this.next = null;
        // prev 是指向列表中上一项的指针
        this.prev = null;
    }
}

还是敲一遍吧：

class DoublyLinkedList {constructor() {
        this.head = null;
        this.tail = null;
    }
    // 各种操作方法
    // ...
}

2. 双向链表的操作方法

• Append & AppendAt: 在链表的尾部 / 指定地位增加节点

append(item) {let node = new Node( item);
  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node
  }
}

appendAt(pos, item) {
   let current = this.head;
   let counter = 1;
   let node = new Node(item);
   if(pos == 0) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } else {while(current) {
      current = current.next;
      if(counter == pos) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}

• Remove & RemoveAt: 在链表的尾部 / 指定地位删除节点

remove(item) {
  let current = this.head;
  while(current) {if( current.data === item) {if( current == this.head && current == this.tail) {
        this.head = null;
        this.tail = null;
      } else if (current == this.head) {
        this.head = this.head.next
        this.head.prev = null
      } else if (current == this.tail) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}

removeAt(pos) {
  let current = this.head;
  let counter = 1;
  if(pos == 0) {
   this.head = this.head.next;
   this.head.prev = null;
  } else {while( current) {
    current = current.next
    if (current == this.tail) {
     this.tail = this.tail.prev;
     this.tail.next = null;
    } else if(counter == pos) {
     current.prev.next = current.next;
     current.next.prev = current.prev;
     break;
    }
    counter++;
   }
  }
}

• Reverse: 翻转双向链表

reverse(){
  let current = this.head;
  let prev = null;
  while(current){
   let next = current.next
   current.next = prev
   current.prev = next
   prev = current
   current = next
  }
  this.tail = this.head
  this.head = prev
}

• Swap：两节点间替换。

swap(nodeOne, nodeTwo) {
   let current = this.head;
   let counter = 0;
   let firstNode;
   while(current !== null) {if( counter == nodeOne){firstNode = current;} else if(counter == nodeTwo) {
       let temp = current.data;
       current.data = firstNode.data;
       firstNode.data = temp;
     }
     current = current.next;
     counter++;
   }
   return true
}

• IsEmpty & Length：查问是否为空或长度。

length() {
  let current = this.head;
  let counter = 0;
  while(current !== null) {
   counter++
   current = current.next
  }
  return counter;
}
isEmpty() {return this.length() < 1
}

• Traverse: 遍历链表

traverse(fn) {
   let current = this.head;
   while(current !== null) {fn(current)
    current = current.next;
   }
   return true;
}

<center> 每一项都加 10</center>

• Search：查找节点的索引。

search(item) {
  let current = this.head;
  let counter = 0;
  while(current) {if( current.data == item) {return counter}
    current = current.next
    counter++
  }
  return false;
}

6. 树：Tree

计算机中常常用到的一种非线性的数据结构——树（Tree），因为其存储的所有元素之间具备显著的档次个性，因而常被用来存储具备层级关系的数据，比方文件系统中的文件；也会被用来存储有序列表等。

• 在树结构中，每一个结点只有一个父结点，若一个结点无父节点，则称为树的根结点，简称树的根（root）。
• 每一个结点能够有多个子结点。
• 没有子结点的结点称为叶子结点。
• 一个结点所领有的子结点的个数称为该结点的度。
• 所有结点中最大的度称为树的度。树的最大档次称为树的深度。

6.1 树的分类

常见的树分类如下，其中咱们把握二叉搜寻树即可。

• 二叉树：Binary Search Tree
• AVL 树：AVL Tree
• 红黑树：Red-Black Tree
• 线段树：Segment Tree – with min/max/sum range queries examples
• 芬威克树：Fenwick Tree (Binary Indexed Tree)

6.2 树的利用

1. DOM树。每个网页都有一个树数据结构。

1. Vue和 React 的Virtual DOM也是树。

6.3 二叉树：Binary Search Tree

• 二叉树是一种非凡的树，它的子节点个数不超过两个。
• 且别离称为该结点的左子树（left subtree）与右子树（right subtree）。
• 二叉树常被用作二叉查找树和二叉搜寻树、或是二叉排序树（BST）。

6.4 二叉树的遍历

按肯定的规定和程序走遍二叉树的所有结点，使每一个结点都被拜访一次，而且只被拜访一次，这个操作被称为 树的遍历，是对树的一种最根本的运算。

因为二叉树是非线性构造，因而，树的遍历本质上是将 二叉树的各个结点转换成为一个线性序列 来示意。

依照根节点拜访的程序不同，二叉树的遍历分为以下三种：前序遍历，中序遍历，后序遍历；

前序遍历：Pre-Order

根节点 -> 左子树 -> 右子树

中序遍历：In-Order

左子树 -> 根节点 -> 右子树

后序遍历：Post-Order

左子树 -> 右子树 -> 根节点

因而咱们能够得之下面二叉树的遍历后果如下：

• 前序遍历：ABDEFGC
• 中序遍历：DEBGFAC
• 后序遍历：EDGFBCA

6.5 二叉树的实现

class Node {constructor(data) { 
    this.left = null
    this.right = null
    this.value = data
  } 
} 

class BST {constructor() {this.root = null}
    // 二叉树的各种操作
    // insert(value) {...}
    // insertNode(root, newNode) {...}
    // ...

1. insertNode& insert：插入新子节点 / 节点

  insertNode(root, newNode) {if (newNode.value < root.value) {
      // 先执行无左节点操作
      (!root.left) ? root.left = newNode : this.insertNode(root.left, newNode)
    } else {(!root.right) ? root.right = newNode : this.insertNode(root.right, newNode)
    }
  }
  
insert(value) {let newNode = new Node(value)
    // 如果没有根节点
    if (!this.root) {this.root = newNode} else {this.insertNode(this.root, newNode)
    }
}

2. removeNode& remove：移除子节点 / 节点

  removeNode(root, value) {if (!root) {return null}
    
    // 从该值小于根节点开始判断
    if (value < root.value) {root.left = this.removeNode(root.left, value)
      return root
    } else if (value > root.value) {root.right = tis.removeNode(root.right, value)
      return root
    } else {
      // 如果没有左右节点
      if (!root.left && !root.right) {
        root = null
        return root
      }
      
      // 存在左节点
      if (root.left) {
        root = root.left
        return root
      // 存在右节点
      } else if (root.right) {
        root = root.right
        return root
      }
      
      // 获取正确子节点的最小值以确保咱们有无效的替换
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
      // 确保删除已替换的节点
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }
  
remove(value) {if (!this.root) {return 'Tree is empty!'} else {this.removeNode(this.root, value)
    }
}
  

3. findMinNode: 获取子节点的最小值

findMinNode(root) {if (!root.left) {return root} else {return this.findMinNode(root.left)
    }
}

4. searchNode & search：查找子节点 / 节点

searchNode(root, value) {if (!root) {return null}
    
    if (value < root.value) {return this.searchNode(root.left, value)
    } else if (value > root.value) {return this.searchNode(root.right, value)
    }
    
    return root
}

search(value) {if (!this.root) {return 'Tree is empty'} else {return Boolean(this.searchNode(this.root, value))
    }
}

1. Pre-Order：前序遍历

preOrder(root) {if (!root) {return 'Tree is empty'} else {console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }

1. In-Order：中序遍历

inOrder(root) {if (!root) {return 'Tree is empty'} else {this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
  }

1. Post-Order：后序遍历

postOrder(root) {if (!root) {return 'Tree is empty'} else {this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}

7. 图：Graph

图是由具备边的节点汇合组成的数据结构。图能够是定向的或不定向的。

图的介绍遍及，找了一圈文章，还是这篇最佳：

Graphs—-A Visual Introduction for Beginners

7.1 图的利用

在以下场景中，你都应用到了图：

• 应用搜寻服务，如Google，百度。
• 应用 LBS 地图服务，如高德，谷歌地图。
• 应用社交媒体网站，如微博，Facebook。

图用于不同的行业和畛域：

• GPS零碎和谷歌地图应用图表来查找从一个目的地到另一个目的地的最短门路。
• 社交网络应用图表来示意用户之间的连贯。
• Google搜索算法应用图 来确定搜寻后果的相关性。
• 经营钻研是一个应用图 来寻找升高运输和交付货物和服务老本的最佳路径的畛域。
• 甚至化学应用图 来示意分子！

图，能够说是利用最宽泛的数据结构之一，实在场景中处处有图。

7.2 图的形成

图表用于示意，查找，剖析和优化元素（屋宇，机场，地位，用户，文章等）之间的连贯。

1. 图的根本元素

• 节点：Node，比方地铁站中某个站 / 多个村庄中的某个村庄 / 互联网中的某台主机 / 人际关系中的人.
• 边：Edge，比方地铁站中两个站点之间的间接连线, 就是一个边。

2. 符号和术语

• |V|= 图中顶点（节点）的总数。
• |E|= 图中的连贯总数（边）。

在上面的示例中

|V| = 6 
|E| = 7 

3. 有向图与无向图

图依据其边（连贯）的特色进行分类。

1. 有向图

在有向图中，边具备方向。它们从一个节点转到另一个节点，并且无奈通过该边返回到初始节点。

如下图所示，边（连贯）当初具备指向特定方向的箭头。将这些边视为单行道。您能够向一个方向后退并达到目的地，然而你无奈通过同一条街道返回，因而您须要找到另一条门路。

<center> 有向图 </center>

2. 无向图

在这种类型的图中，边是无向的（它们没有特定的方向）。将无向边视为双向街道。您能够从一个节点转到另一个节点并返回雷同的“门路”。

4. 加权图

在加权图中，每条边都有一个与之相干的值（称为权重）。该值用于示意它们连贯的节点之间的某种可量化关系。例如：

• 权重能够示意间隔，工夫，社交网络中两个用户之间共享的连接数。
• 或者能够用于形容您正在应用的上下文中的节点之间的连贯的任何内容。

驰名的 Dijkstra 算法，就是应用这些权重通过查找网络中节点之间的最短或最优的门路来优化路由。

5. 稠密图与密集图

当图中的边数靠近最大边数时，图是密集的。

<center> 密集图 </center>

当图中的边数显著少于最大边数时，图是稠密的。

<center> 稠密图 </center>

6. 循环

如果你依照图中的一系列连贯，可能会找到一条门路，将你带回到同一节点。这就像“走在圈子里”，就像你在城市四周开车一样，你走的路能够带你回到你的初始地位。????

在图中，这些“圆形”门路称为“循环”。它们是在同一节点上开始和完结的无效门路。例如，在下图中，您能够看到，如果从任何节点开始，您能够通过追随边缘返回到同一节点。

循环并不总是“孤立的”，因为它们能够是较大图的一部分。能够通过在特定节点上开始搜寻并找到将你带回同一节点的门路来检测它们。

<center> 循环图 </center>

7.3 图的实现

咱们将实现具备邻接列表的有向图。

class Graph {constructor() {this.AdjList = new Map();
  }
  
  // 根底操作方法
  // addVertex(vertex) {}
  // addEdge(vertex, node) {}
  // print() {}
}

1. addVertex：增加顶点

addVertex(vertex) {if (!this.AdjList.has(vertex)) {this.AdjList.set(vertex, []);
  } else {throw 'Already Exist!!!';}
}

尝试创立顶点：

let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');

打印后将会发现：

Map {'A' => [],
  'B' => [],
  'C' => [],
  'D' => []}

之所以都为空数组 '[]'，是因为数组中须要贮存边(Edge) 的关系。
例如下图：

该图的 Map 将为：

Map {'A' => ['B', 'C', 'D'],
  // B 没有任何指向
  'B' => [],
  'C' => ['B'],
  'D' => ['C']
}

2. addEdge：增加边(Edge)

 addEdge(vertex, node) {
    // 向顶点增加边之前，必须验证该顶点是否存在。if (this.AdjList.has(vertex)) {
      // 确保增加的边尚不存在。if (this.AdjList.has(node)){let arr = this.AdjList.get(vertex);
        // 如果都通过，那么能够将边增加到顶点。if(!arr.includes(node)){arr.push(node);
        }
      }else {throw `Can't add non-existing vertex ->'${node}'`;
      }
    } else {throw `You should add '${vertex}' first`;
    }
}

3. print：打印图(Graph)

print() {for (let [key, value] of this.AdjList) {console.log(key, value);
  }
}

测试一下

let g = new Graph();
let arr = ['A', 'B', 'C', 'D', 'E', 'F'];
for (let i = 0; i < arr.length; i++) {g.addVertex(arr[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
g.print();
/* PRINTED */
// A ['B', 'D', 'E']
// B ['C']
// C ['F']
// D ['E']
// E ['F', 'C']
// F []

到目前为止，这就是创立图所需的。然而，99%的状况下，会要求你实现另外两种办法：

• 广度优先算法，BFS。
• 深度优先算法，DFS
• BFS 的重点在于队列，而 DFS 的重点在于递归。这是它们的本质区别。

5. 广度优先算法实现

广度优先算法（Breadth-First Search），同广度优先搜寻。

是一种利用 队列 实现的搜索算法。简略来说，其搜寻过程和“湖面丢进一块石头激发层层涟漪”相似。

如上图所示，从终点登程，对于每次出队列的点，都要遍历其周围的点。所以说 BFS 的搜寻过程和“湖面丢进一块石头激发层层涟漪”很类似，此即“广度优先搜索算法”中“广度”的由来。

该算法的具体步骤为：

• BFS 将起始节点作为参数。（例如'A'）
• 初始化一个空对象：visited。
• 初始化一个空数组：q，该数组将用作队列。
• 将起始节点标记为已拜访。（visited = {'A': true}）
• 将起始节点放入队列中。（q = ['A']）
• 循环直到队列为空

循环外部：

• 从中获取元素 q 并将其存储在变量中。（let current = q.pop()）
• 打印 以后 current
• 从图中获取 current 的边。（let arr = this.AdjList.get(current)）。
• 如果未拜访元素，则将每个元素标记为已拜访并将其放入队列中。

visited = {
  'A': true,
  'B': true,
  'D': true,
  'E': true
}
q = ['B', 'D', 'E']

具体实现：

createVisitedObject(){let arr = {};
  for(let key of this.AdjList.keys()){arr[key] = false;
  }
  return arr;
}

bfs(startingNode){let visited = this.createVisitedObject();
  let q = [];

  visited[startingNode] = true;
  q.push(startingNode);

  while(q.length){let current = q.pop()
    console.log(current);

    let arr = this.AdjList.get(current);

    for(let elem of arr){if(!visited[elem]){visited[elem] = true;
        q.unshift(elem)
      }
    }

  }
}

6. 深度优先算法实现

深度优先搜索算法（Depth-First-Search，缩写为 DFS），是一种利用递归实现的搜索算法。简略来说，其搜寻过程和“不撞南墙不回头”相似。

如上图所示，从终点登程，先把一个方向的点都遍历完才会改变方向 …… 所以说，DFS 的搜寻过程和“不撞南墙不回头”很类似，此即“深度优先搜索算法”中“深度”的由来。

该算法的后期步骤和 BFS 类似，承受起始节点并跟踪受访节点，最初执行递归的辅助函数。

具体步骤：

• 承受终点作为参数dfs(startingNode)。
• 创立拜访对象let visited = this.createVisitedObject() 。
• 调用辅助函数递归起始节点和拜访对象this.dfsHelper(startingNode, visited) 。
• dfsHelper 将其标记为已拜访并打印进去。

createVisitedObject(){let arr = {};
  for(let key of this.AdjList.keys()){arr[key] = false;
  }
  return arr;
}

 dfs(startingNode){console.log('\nDFS')
    let visited = this.createVisitedObject();
    this.dfsHelper(startingNode, visited);
  }

  dfsHelper(startingNode, visited){visited[startingNode] = true;
    console.log(startingNode);

    let arr = this.AdjList.get(startingNode);

    for(let elem of arr){if(!visited[elem]){this.dfsHelper(elem, visited);
      }
    }
  }

  doesPathExist(firstNode, secondNode){let path = [];
    let visited = this.createVisitedObject();
    let q = [];
    visited[firstNode] = true;
    q.push(firstNode);
    while(q.length){let node = q.pop();
      path.push(node);
      let elements = this.AdjList.get(node);
      if(elements.includes(secondNode)){console.log(path.join('->'))
        return true;
      }else{for(let elem of elements){if(!visited[elem]){visited[elem] = true;
            q.unshift(elem);
          }
        }
      }
    }
    return false;
  }
}

Vans，下一个。

8. 字典树：Trie

Trie（通常发音为“try”）是针对特定类型的搜寻而优化的树数据结构。当你想要获取局部值并返回一组可能的残缺值时，能够应用Trie。典型的例子是主动实现。

Trie，是一种搜寻树，也称字典树或单词查找树，此外也称前缀树，因为某节点的后辈存在独特的前缀。

它的特点：

• key 都为字符串，能做到高效查问和插入，工夫复杂度为O(k)，k 为字符串长度
• 毛病是如果大量字符串没有独特前缀时很耗内存。
• 它的核心思想就是缩小没必要的字符比拟，使查问高效率。
• 即用空间换工夫，再利用独特前缀来进步查问效率。

例如：
搜寻前缀“b”的匹配将返回 6 个值：be，bear，bell，bid，bull，buy。

搜寻前缀“be”的匹配将返回 2 个值：bear，bell

8.1 字典树的利用

只有你想要将前缀与可能的残缺值匹配，就能够应用Trie。

事实中多使用在：

• 主动填充 / 事后输出
• 搜寻
• 输入法选项
• 分类

也能够使用在：

• IP 地址检索
• 电话号码
• 以及更多 …

8.2 字典树的实现

class PrefixTreeNode {constructor(value) {this.children = {};
    this.endWord = null;
    this.value = value;
  }
}
class PrefixTree extends PrefixTreeNode {constructor() {super(null);
  }
  // 根底操作方法
  // addWord(string) {}
  // predictWord(string) {}
  // logAllWords() {}
}

1. addWord: 创立一个节点

addWord(string) {const addWordHelper = (node, str) => {if (!node.children[str[0]]) {node.children[str[0]] = new PrefixTreeNode(str[0]);
            if (str.length === 1) {node.children[str[0]].endWord = 1;
            } else if (str.length > 1) {addWordHelper(node.children[str[0]], str.slice(1));
        }
    };
    addWordHelper(this, string);
}

2. predictWord：预测单词

即：给定一个字符串，返回树中以该字符串结尾的所有单词。

predictWord(string) {let getRemainingTree = function(string, tree) {
      let node = tree;
      while (string) {node = node.children[string[0]];
        string = string.substr(1);
      }
      return node;
    };

    let allWords = [];
    
    let allWordsHelper = function(stringSoFar, tree) {for (let k in tree.children) {const child = tree.children[k]
        let newString = stringSoFar + child.value;
        if (child.endWord) {allWords.push(newString);
        }
        allWordsHelper(newString, child);
      }
    };

    let remainingTree = getRemainingTree(string, this);
    if (remainingTree) {allWordsHelper(string, remainingTree);
    }

    return allWords;
  }

3. logAllWords：打印所有的节点

  logAllWords() {console.log('------ 所有在字典树中的节点 -----------')
    console.log(this.predictWord(''));
  }

logAllWords，通过在空字符串上调用 predictWord 来打印 Trie 中的所有节点。

9. 散列表（哈希表）：Hash Tables

应用哈希表能够进行十分疾速的查找操作。然而，哈希表到底是什么玩意儿？

很多语言的内置数据结构像 python 中的字典，java中的HashMap，都是基于哈希表实现。但哈希表到底是啥？

9.1 哈希表是什么？

散列（hashing）是电脑迷信中一种对材料的解决办法，通过某种特定的函数 / 算法（称为散列函数 / 算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜寻的数据结构（称为散列表）。也译为散列。旧译哈希（误以为是人名而采纳了音译）。

它也罕用作一种资讯平安的实作办法，由一串材料中通过散列算法（Hashing algorithms）计算出来的材料指纹（data fingerprint），常常用来辨认档案与材料是否有被篡改，以保障档案与材料的确是由原创者所提供。—-Wikipedia

9.2 哈希表的形成

Hash Tables优化了键值对的存储。在最佳状况下，哈希表的插入，检索和删除是恒定工夫。哈希表用于存储大量快速访问的信息，如明码。

哈希表能够概念化为一个数组，其中蕴含一系列存储在对象外部子数组中的元组：

{[[['a'，9]，['b'，88]]，[['e'，7]，['q'，8]]，[['j'，7]，['l'，8]]]};

• 内部数组有多个等于数组最大长度的桶（子数组）。
• 在桶内，元组或两个元素数组放弃键值对。

9.3 哈希表的基础知识

这里我就尝试以大白话模式讲清楚根底的哈希表常识：

散列是一种用于从一组类似对象中惟一标识特定对象的技术。咱们生存中如何应用散列的一些例子包含：

• 在大学中，每个学生都会被调配一个惟一的卷号，可用于检索无关它们的信息。
• 在图书馆中，每本书都被调配了一个惟一的编号，可用于确定无关图书的信息，例如图书馆中的确切地位或已发给图书的用户等。

在这两个例子中，学生和书籍都被分成了一个惟一的数字。

1. 思考一个问题

假如有一个对象，你想为其调配一个键以便于搜寻。要存储键 / 值对，您能够应用一个简略的数组，如数据结构，其中键（整数）能够间接用作存储值的索引。

然而，如果密钥很大并且无奈间接用作索引，此时就应该应用散列。

2, 一个哈希表的诞生

具体步骤如下：

1. 在散列中，通过应用 散列函数 将大键转换为小键。
2. 而后将这些值存储在称为哈希表的数据结构中。
3. 散列的想法是在数组中统一分配条目（键 / 值对）。为每个元素调配一个键（转换键）。
4. 通过应用该键，您能够在 O(1) 工夫内拜访该元素。
5. 应用密钥，算法（散列函数）计算一个索引，能够找到或插入条目标地位。

具体执行分两步：

• 通过应用散列函数将元素转换为整数。此元素可用作存储原始元素的索引，该元素属于哈希表。
• 该元素存储在哈希表中，能够应用散列键疾速检索它。

hash = hashfunc（key）index = hash % array_size

在此办法中，散列与数组大小无关，而后通过应用运算符（%）将其缩减为索引（介于 0 和array_size 之间的数字 - 1）。

3. 哈希函数

• 哈希函数是可用于将任意大小的数据集映射到固定大小的数据集的任何函数，该数据集属于散列表
• 哈希函数返回的值称为哈希值，哈希码，哈希值或简略哈希值。

要实现良好的散列机制，须要具备以下根本要求：

1. 易于计算：它应该易于计算，并且不能成为算法自身。
2. 对立散布：它应该在哈希表中提供对立散布，不应导致群集。
3. 较少的抵触：当元素对映射到雷同的哈希值时发生冲突。应该防止这些。

留神：无论散列函数有多强壮，都必然会发生冲突。因而，为了放弃哈希表的性能，通过各种抵触解决技术来治理抵触是很重要的。

4. 良好的哈希函数

假如您必须应用散列技术 {“abcdef”，“bcdefa”，“cdefab”，“defabc”} 等字符串存储在散列表中。

首先是建设索引：

• a，b，c，d，e和 f 的ASCII值别离为 97,98,99,100,101 和102，总和为：597
• 597不是素数，取其左近的素数599，来缩小索引不同字符串（抵触）的可能性。

哈希函数将为所有字符串计算雷同的索引，并且字符串将以下格局存储在哈希表中。

因为所有字符串的索引都雷同，此时所有字符串都在同一个“桶”中。

• 这里，拜访特定字符串须要 O(n) 工夫（其中 n 是字符串数）。
• 这表明该哈希函数不是一个好的哈希函数。

如何优化这个哈希函数？

留神察看这些字符串的异同

{“abcdef”，“bcdefa”，“cdefab”，“defabc”}

• 都是由 a，b，c，d，e 和f组成
• 不同点在于组成程序。

来尝试不同的哈希函数。

• 特定字符串的索引将等于字符的 ASCII 值之和乘以字符串中它们各自的程序
• 之后将它与2069（素数）取余。

字符串哈希函数索引

在正当的假如下，在哈希表中搜寻元素所需的均匀工夫应是 O（1）。

9.4 哈希表的实现

class Node {constructor( data){
        this.data = data;
        this.next = null;
    }
}

class HashTableWithChaining {constructor( size = 10) {this.table = new Array( size);
    }
    
    // 操作方法
    // computeHash(string) {...}
    // ...
}

1. isPrime：素数判断

isPrime(num) {for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num !== 1;
}

2. computeHash|findPrime：哈希函数生成

computeHash(string) {let H = this.findPrime( this.table.length);
    let total = 0;
    for (let i = 0; i < string.length; ++i) {total += H * total + string.charCodeAt(i);
       }
    return total % this.table.length;
}
// 取模
findPrime(num) {while(true) {if( this.isPrime(num) ){break;}
        num += 1
    }
    return num;
}

3. Put：插入值

put(item) {let key = this.computeHash( item);
    let node = new Node(item)
    if (this.table[key] ) {node.next = this.table[key]
    }
    this.table[key] = node
}

4. Remove：删除值

remove(item) {let key = this.computeHash( item);
    if(this.table[key] ) {if( this.table[key].data === item ) {this.table[key] = this.table[key].next
        } else {let current = this.table[key].next;
            let prev = this.table[key];
            while(current) {if( current.data === item) {prev.next = current.next}
                prev = current
                current = current.next;
            }
        }
    }
}

5. contains：判断蕴含

contains(item) {for (let i = 0; i < this.table.length; i++) {if (this.table[i]) {let current = this.table[i];
            while (current) {if (current.data === item) {return true;}
                current = current.next;
            }
        }
    }
    return false;
}

6. Size & IsEmpty：判断长度或空

size(item) {
  let counter = 0
  for(let i=0; i<this.table.length; i++){if( this.table[i] ) {let current = this.table[i]
      while(current) {
        counter++
        current = current.next
      }
    }
  }
  return counter
}
isEmpty() {return this.size() < 1
}

7. Traverse：遍历

traverse(fn) {for(let i=0; i<this.table.length; i++){if( this.table[i] ) {let current = this.table[i];
      while(current) {fn( current);
        current = current.next;
      }
    }
  }
}

10. 为啥写这篇

还是和面试无关。尽管 leetcode 上的题刷过一些，但因为不足对数据结构的整体认知。很多时候被问到或考到，会无所下手。

网上的帖子大多深浅不一，写这篇的过程中翻阅了大量的材料和示例。在下的文章都是学习过程中的总结，如果发现错误，欢送留言指出。

参考：

1. DS with JS – Hash Tables— I
2. Joseph Crick – Practical Data Structures for Frontend Applications: When to use Tries
3. [Thon Ly – Data Structures in JavaScript

](https://medium.com/siliconwat…

1. Graphs — A Visual Introduction for Beginners
2. Graph Data Structure in JavaScript
3. Trie (Keyword Tree)