快捷搜索：  汽车  科技
当前位置： 爱玩科技 > 科技 > 正文

前端js框架推荐：前端 8种常见数据结构及其JS实现

威哥 317

前端js框架推荐：前端 8种常见数据结构及其JS实现class Node { constructor(data left = null right = null) { this.data = data; this.left = left; this.right = right; } } class BST { constructor() { this.root = null; } add(data) { const node = this.root; if (node === null) { this.root = new Node(data); return; } else { const searchTree = function (node) { if (data < node.data) { if (node.left === null) { node.left = new Node(d

Hash Table是一种用于存储键值对（key value pair）的数据结构，因为Hash Table根据key查询value的速度很快，所以它常用于实现Map、Dictinary、Object等数据结构。如上图所示，Hash Table内部使用一个hash函数将传入的键转换成一串数字，而这串数字将作为键值对实际的key，通过这个key查询对应的value非常快，时间复杂度将达到O(1)。Hash函数要求相同输入对应的输出必须相等，而不同输入对应的输出必须不等，相当于对每对数据打上唯一的指纹。

一个Hash Table通常具有下列方法：

  1. add：增加一组键值对
  2. remove：删除一组键值对
  3. lookup：查找一个键对应的值

一个简易版本的Hash Table的Javascript实现：

function hash(string max) { var hash = 0; for (var i = 0; i < string.length; i ) { hash = string.charCodeAt(i); } return hash % max; } function HashTable() { let storage = []; const storageLimit = 4; this.add = function (key value) { var index = hash(key storageLimit); if (storage[index] === undefined) { storage[index] = [ [key value] ]; } else { var inserted = false; for (var i = 0; i < storage[index].length; i ) { if (storage[index][i][0] === key) { storage[index][i][1] = value; inserted = true; } } if (inserted === false) { storage[index].push([key value]); } } } this.remove = function (key) { var index = hash(key storageLimit); if (storage[index].length === 1 && storage[index][0][0] === key) { delete storage[index]; } else { for (var i = 0; i < storage[index]; i ) { if (storage[index][i][0] === key) { delete storage[index][i]; } } } } this.lookup = function (key) { var index = hash(key storageLimit); if (storage[index] === undefined) { return undefined; } else { for (var i = 0; i < storage[index].length; i ) { if (storage[index][i][0] === key) { return storage[index][i][1]; } } } } }

6. Tree（树）

前端js框架推荐：前端 8种常见数据结构及其JS实现(1)

顾名思义，Tree的数据结构和自然界中的树极其相似，有根、树枝、叶子，如上图所示。Tree是一种多层数据结构，与Array、Stack、Queue相比是一种非线性的数据结构，在进行插入和搜索操作时很高效。在描述一个Tree时经常会用到下列概念：

  1. Root（根）：代表树的根节点，根节点没有父节点
  2. Parent Node（父节点）：一个节点的直接上级节点，只有一个
  3. Child Node（子节点）：一个节点的直接下级节点，可能有多个
  4. Siblings（兄弟节点）：具有相同父节点的节点
  5. Leaf（叶节点）：没有子节点的节点
  6. Edge（边）：两个节点之间的连接线
  7. Path（路径）：从源节点到目标节点的连续边
  8. Height of Node（节点的高度）：表示节点与叶节点之间的最长路径上边的个数
  9. Height of Tree（树的高度）：即根节点的高度
  10. Depth of Node（节点的深度）：表示从根节点到该节点的边的个数
  11. Degree of Node（节点的度）：表示子节点的个数

我们以二叉查找树为例，展示树在Javascript中的实现。在二叉查找树中，即每个节点最多只有两个子节点，而左侧子节点小于当前节点，而右侧子节点大于当前节点，如图所示：

前端js框架推荐：前端 8种常见数据结构及其JS实现(2)

一个二叉查找树应该具有以下常用方法：

  1. add：向树中插入一个节点
  2. findMin：查找树中最小的节点
  3. findMax：查找树中最大的节点
  4. find：查找树中的某个节点
  5. isPresent：判断某个节点在树中是否存在
  6. remove：移除树中的某个节点

以下是二叉查找树的Javascript实现：

class Node { constructor(data left = null right = null) { this.data = data; this.left = left; this.right = right; } } class BST { constructor() { this.root = null; } add(data) { const node = this.root; if (node === null) { this.root = new Node(data); return; } else { const searchTree = function (node) { if (data < node.data) { if (node.left === null) { node.left = new Node(data); return; } else if (node.left !== null) { return searchTree(node.left); } } else if (data > node.data) { if (node.right === null) { node.right = new Node(data); return; } else if (node.right !== null) { return searchTree(node.right); } } else { return null; } }; return searchTree(node); } } findMin() { let current = this.root; while (current.left !== null) { current = current.left; } return current.data; } findMax() { let current = this.root; while (current.right !== null) { current = current.right; } return current.data; } find(data) { let current = this.root; while (current.data !== data) { if (data < current.data) { current = current.left } else { current = current.right; } if (current === null) { return null; } } return current; } isPresent(data) { let current = this.root; while (current) { if (data === current.data) { return true; } if (data < current.data) { current = current.left; } else { current = current.right; } } return false; } remove(data) { const removeNode = function (node data) { if (node == null) { return null; } if (data == node.data) { // node没有子节点 if (node.left == null && node.right == null) { return null; } // node没有左侧子节点 if (node.left == null) { return node.right; } // node没有右侧子节点 if (node.right == null) { return node.left; } // node有两个子节点 var tempNode = node.right; while (tempNode.left !== null) { tempNode = tempNode.left; } node.data = tempNode.data; node.right = removeNode(node.right tempNode.data); return node; } else if (data < node.data) { node.left = removeNode(node.left data); return node; } else { node.right = removeNode(node.right data); return node; } } this.root = removeNode(this.root data); } }

测试一下：

const bst = new BST(); bst.add(4); bst.add(2); bst.add(6); bst.add(1); bst.add(3); bst.add(5); bst.add(7); bst.remove(4); console.log(bst.findMin()); console.log(bst.findMax()); bst.remove(7); console.log(bst.findMax()); console.log(bst.isPresent(4));

打印结果：

1 7 6 false

7. Trie（字典树，读音同try）

前端js框架推荐：前端 8种常见数据结构及其JS实现(3)

Trie也可以叫做Prefix Tree（前缀树），也是一种搜索树。Trie分步骤存储数据，树中的每个节点代表一个步骤，trie常用于存储单词以便快速查找，比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母，跟着树的分支可以可以拼写出一个完整的单词，每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。

Trie一般有以下方法：

  1. add：向字典树中增加一个单词
  2. isWord：判断字典树中是否包含某个单词
  3. print：返回字典树中的所有单词

/** * Trie的节点 */ function Node() { this.keys = new Map(); this.end = false; this.setEnd = function () { this.end = true; }; this.isEnd = function () { return this.end; } } function Trie() { this.root = new Node(); this.add = function (input node = this.root) { if (input.length === 0) { node.setEnd(); return; } else if (!node.keys.has(input[0])) { node.keys.set(input[0] new Node()); return this.add(input.substr(1) node.keys.get(input[0])); } else { return this.add(input.substr(1) node.keys.get(input[0])); } } this.isWord = function (word) { let node = this.root; while (word.length > 1) { if (!node.keys.has(word[0])) { return false; } else { node = node.keys.get(word[0]); word = word.substr(1); } } return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false; } this.print = function () { let words = new Array(); let search = function (node = this.root string) { if (node.keys.size != 0) { for (let letter of node.keys.keys()) { search(node.keys.get(letter) string.concat(letter)); } if (node.isEnd()) { words.push(string); } } else { string.length > 0 ? words.push(string) : undefined; return; } }; search(this.root new String()); return words.length > 0 ? words : null; } }

8. Graph（图）

前端js框架推荐：前端 8种常见数据结构及其JS实现(4)

Graph是节点（或顶点）以及它们之间的连接（或边）的集合。Graph也可以称为Network（网络）。根据节点之间的连接是否有方向又可以分为Directed Graph（有向图）和Undrected Graph（无向图）。Graph在实际生活中有很多用途，比如：导航软件计算最佳路径，社交软件进行好友推荐等等。

Graph通常有两种表达方式：

Adjaceny List（邻接列表）：

前端js框架推荐：前端 8种常见数据结构及其JS实现(5)

网站首页

返回栏目

猜您喜欢：

相关文章