运维开发网

Javascript中的8种常见数据结构(建议收藏)

运维开发网 https://www.qedev.com 2021-01-13 08:59 出处:51CTO 作者:mb5ff982de32716
1.Stack(栈)堆栈遵循LIFO(后进先出)的原则。如果你把书堆叠起来,上面的书会比下面的书先拿。或者当你在网上浏览时,后退按钮会引导你到最近浏览的页面。Stack具有以下常见方法:push:输入一个新元素pop:删除顶部元素,返回删除的元素peek:返回顶部元素length:返回堆栈中元素的数量Javascript中的数组具有Stack的属性,但是我们使用 function Stack()

Javascript中的8种常见数据结构(建议收藏)

1.Stack(栈)

Javascript中的8种常见数据结构(建议收藏)

堆栈遵循LIFO(后进先出)的原则。如果你把书堆叠起来,上面的书会比下面的书先拿。或者当你在网上浏览时,后退按钮会引导你到最近浏览的页面。

Stack具有以下常见方法:

  • push:输入一个新元素
  • pop:删除顶部元素,返回删除的元素
  • peek:返回顶部元素
  • length:返回堆栈中元素的数量

Javascript中的数组具有Stack的属性,但是我们使用 function Stack() 从头开始构建Stack

function Stack() {

this.count = 0;

 this.storage = {};

 this.push = function (value) {

   this.storage[this.count] = value;

   this.count++;

 }

 this.pop = function () {

   if (this.count === 0) {

     return undefined;

   }

   this.count--;

   var result = this.storage[this.count];

   delete this.storage[this.count];

   return result;

 }

 this.peek = function () {

   return this.storage[this.count - 1];

 }

 this.size = function () {

   return this.count;

 }

}

2.Queue(队列)

Javascript中的8种常见数据结构(建议收藏)

Queue与Stack类似。唯一不同的是,Queue使用的是FIFO原则(先进先出)。换句话说,当你排队等候公交车时,队列中的第一个总是先上车。

队列具有以下方法:

  • enqueue:输入队列,在最后添加一个元素
  • dequeue:离开队列,删除前元素并返回
  • front:得到第一个元素
  • isEmpty:确定队列是否为空
  • size:获取队列中元素的数量

JavaScript中的数组具有Queue的某些属性,因此我们可以使用数组来构造Queue的示例:

function Queue() {

 var collection = [];

 this.print = function () {

   console.log(collection);

 }

 this.enqueue = function (element) {

   collection.push(element);

 }

 this.dequeue = function () {

   return collection.shift();

 }

 this.front = function () {

   return collection[0];

 }

 this.isEmpty = function () {

   return collection.length === 0;

 }

 this.size = function () {

   return collection.length;

 }

}

优先队列

队列还有另一个高级版本。为每个元素分配优先级,并将根据优先级对它们进行排序:

function PriorityQueue() {

 ...

 this.enqueue = function (element) {

   if (this.isEmpty()) {

     collection.push(element);

   } else {

     var added = false;

     for (var i = 0; i < collection.length; i++) {

       if (element[1] < collection[i][1]) {

         collection.splice(i, 0, element);

         added = true;

         break;

       }

     }

     if (!added) {

       collection.push(element);

     }

   }

 }

}

测试一下:

var pQ = new PriorityQueue();

pQ.enqueue([ gannicus , 3]);

pQ.enqueue([ spartacus , 1]);

pQ.enqueue([ crixus , 2]);

pQ.enqueue([ oenomaus , 4]);

pQ.print();

返回

[

 [  spartacus , 1 ],

 [  crixus , 2 ],

 [  gannicus , 3 ],

 [  oenomaus , 4 ]

]

3. Linked List(链表)

Javascript中的8种常见数据结构(建议收藏)

从字面上看,链表是一个链式数据结构,每个节点由两个信息组成:节点的数据和指向下一个节点的指针。链表和传统数组都是线性数据结构,具有序列化的存储方式。当然,它们也有差异:

比较ArrayLinked List
内存分配静态内存分配,发生在编译和序列化过程中动态内存分配,发生在运行过程中,非连续的。
获取元素从索引中读取,速度更快读取队列中的所有节点,直到得到特定的元素,速度较慢
添加/删除元素由于是顺序记忆和静态记忆,速度较慢由于是动态分配,只需要少量的内存开销,速度更快
空间结构一维或多维单边/双边,或循环链表

单边链表通常具有以下方法:

  • size:返回节点数
  • head:返回头部的元素
  • add:在尾部添加另一个节点
  • remove:删除某些节点
  • indexOf:返回节点的索引
  • elementAt:返回索引的节点
  • addAt:在特定索引处插入节点
  • removeAt:删除特定索引处的节点
/** 链表中的节点 **/

function Node(element) {

   // 节点中的数据

   this.element = element;

   // 指向下一个节点的指针

   this.next = null;

}

function LinkedList() {

 var length = 0;

 var head = null;

 this.size = function () {

   return length;

 }

 this.head = function () {

   return head;

 }

 this.add = function (element) {

   var node = new Node(element);

   if (head == null) {

     head = node;

   } else {

     var currentNode = head;

     while (currentNode.next) {

       currentNode = currentNode.next;

     }

     currentNode.next = node;

   }

   length++;

 }

 this.remove = function (element) {

   var currentNode = head;

   var previousNode;

   if (currentNode.element === element) {

     head = currentNode.next;

   } else {

     while (currentNode.element !== element) {

       previousNode = currentNode;

       currentNode = currentNode.next;

     }

     previousNode.next = currentNode.next;

   }

   length--;

 }

 this.isEmpty = function () {

   return length === 0;

 }

 this.indexOf = function (element) {

   var currentNode = head;

   var index = -1;

   while (currentNode) {

     index++;

     if (currentNode.element === element) {

       return index;

     }

     currentNode = currentNode.next;

   }

   return -1;

 }

 this.elementAt = function (index) {

   var currentNode = head;

   var count = 0;

   while (count < index) {

     count++;

     currentNode = currentNode.next;

   }

   return currentNode.element;

 }

 this.addAt = function (index, element) {

   var node = new Node(element);

   var currentNode = head;

   var previousNode;

   var currentIndex = 0;

   if (index > length) {

     return false;

   }

   if (index === 0) {

     node.next = currentNode;

     head = node;

   } else {

     while (currentIndex < index) {

       currentIndex++;

       previousNode = currentNode;

       currentNode = currentNode.next;

     }

     node.next = currentNode;

     previousNode.next = node;

   }

   length++;

 }

 this.removeAt = function (index) {

   var currentNode = head;

   var previousNode;

   var currentIndex = 0;

   if (index < 0 || index >= length) {

     return null;

   }

   if (index === 0) {

     head = currentIndex.next;

   } else {

     while (currentIndex < index) {

       currentIndex++;

       previousNode = currentNode;

       currentNode = currentNode.next;

     }

     previousNode.next = currentNode.next;

   }

   length--;

   return currentNode.element;

 }

}

4. Set(集合)

Javascript中的8种常见数据结构(建议收藏)

集合是数学的基本概念:定义明确且不同的对象的集合。ES6引入了集合的概念,它与数组有一定程度的相似性。但是,集合不允许重复元素,也不会被索引。

一个典型的集合具有以下方法:

  • values:返回集合中的所有元素
  • size:返回元素个数
  • has:确定元素是否存在
  • add:将元素插入集合
  • remove:从集合中删除元素
  • union:返回两组交集
  • difference:返回两组的差
  • subset:确定某个集合是否是另一个集合的子集

为了区分ES6中的 set,我们在以下示例中声明为 MySet

function MySet() {

 var collection = [];

 this.has = function (element) {

   return (collection.indexOf(element) !== -1);

 }

 this.values = function () {

   return collection;

 }

 this.size = function () {

   return collection.length;

 }

 this.add = function (element) {

   if (!this.has(element)) {

     collection.push(element);

     return true;

   }

   return false;

 }

 this.remove = function (element) {

   if (this.has(element)) {

     index = collection.indexOf(element);

     collection.splice(index, 1);

     return true;

   }

   return false;

 }

 this.union = function (otherSet) {

   var unionSet = new MySet();

   var firstSet = this.values();

   var secondSet = otherSet.values();

   firstSet.forEach(function (e) {

     unionSet.add(e);

   });

   secondSet.forEach(function (e) {

     unionSet.add(e);

   });

   return unionSet;  }

 this.intersection = function (otherSet) {

   var intersectionSet = new MySet();

   var firstSet = this.values();

   firstSet.forEach(function (e) {

     if (otherSet.has(e)) {

       intersectionSet.add(e);

     }

   });

   return intersectionSet;

 }

 this.difference = function (otherSet) {

   var differenceSet = new MySet();

   var firstSet = this.values();

   firstSet.forEach(function (e) {

     if (!otherSet.has(e)) {

       differenceSet.add(e);

     }

   });

   return differenceSet;

 }

 this.subset = function (otherSet) {

   var firstSet = this.values();

   return firstSet.every(function (value) {

     return otherSet.has(value);

   });

 }

}

5. Hast table(哈希表)

Javascript中的8种常见数据结构(建议收藏)

哈希表是一种键值数据结构。由于通过键值查询的速度快如闪电,所以常用于Map、Dictionary或Object数据结构中。如上图所示,哈希表使用哈希函数(hash function)将键转换为数字列表,这些数字作为对应键的值。要快速使用键获取价值,时间复杂度可以达到O(1)。相同的键必须返回相同的值——这是哈希函数的基础。

哈希表具有以下方法:

  • add:添加键值对
  • remove:删除键值对
  • lookup:使用键查找对应的值

一个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(树)

Javascript中的8种常见数据结构(建议收藏)

Tree(树)数据结构是多层结构。与Array,Stack和Queue相比,它也是一种非线性数据结构。这种结构在插入和搜索操作时效率很高。我们来看看树型数据结构的一些概念。

  • root:树的根节点,无父节点
  • parent node:上层的直接节点,只有一个
  • child node:下层的直接节点可以有多个
  • siblings:共享同一个父节点
  • leaf:没有孩子的节点
  • Edge:节点之间的分支或链接
  • path:从起始节点到目标节点的边
  • Height of Nod:特定节点到叶节点的最长路径的边数
  • Height of Tree:根节点到叶节点的最长路径的边数
  • Depth of Node:从根节点到特定节点的边数
  • Degree of Node:子节点数

这里以二叉树为例。每个节点最多有两个节点,左边节点比当前节点小,右边节点比当前节点大。

Javascript中的8种常见数据结构(建议收藏)

二叉树中的常用方法:

  • add:将节点插入树
  • findMin:获取最小节点
  • findMax:获取最大节点
  • find:搜索特定节点
  • isPresent:确定某个节点的存在
  • 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) {

       // no child node

       if (node.left == null && node.right == null) {

         return null;

       }

       // no left node

       if (node.left == null) {

         return node.right;

       }

       // no right node

       if (node.right == null) {

         return node.left;

       }

       // has 2 child nodes

       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”)

Javascript中的8种常见数据结构(建议收藏)

Trie或“前缀树”也是搜索树的一种。Trie分步存储数据——树中的每个节点代表一个步骤。Trie是用来存储词汇的,所以它可以快速搜索,特别是自动完成功能。

Trie中的每个节点都有一个字母——分支之后可以组成一个完整的单词。它还包括一个布尔指示符,以显示这是否是最后一个字母。

Trie具有以下方法:

  • add:在字典树中插入一个单词
  • isWord:确定树是否由某些单词组成
  • print:返回树中的所有单词
/** Node in 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(图)

Javascript中的8种常见数据结构(建议收藏)

Graph(有时称为网络)是指具有链接(或边)的节点集。根据联系是否有方向性,可以进一步分为两组(即定向图和不定向图)。Graph在我们的生活中被广泛使用——在导航应用中计算最佳路线,或者在社交媒体中推荐朋友,举两个例子。

图有两种表示形式:

邻接清单

在此方法中,我们在左侧列出所有可能的节点,并在右侧显示已连接的节点。

Javascript中的8种常见数据结构(建议收藏)

邻接矩阵

相邻矩阵以行和列的形式显示节点,行和列的交点诠释了节点之间的关系,0表示没有联系,1表示有联系,>1表示权重不同。

Javascript中的8种常见数据结构(建议收藏)

要查询图中的节点,必须用 “宽度优先搜索"(BFS)方法或 "深度优先搜索"(DFS)方法在整个树网中进行搜索。

让我们看一个例子的BFS在Javascript:

function bfs(graph, root) {

 var nodesLen = {};

 for (var i = 0; i < graph.length; i++) {

   nodesLen[i] = Infinity;

 }

 nodesLen[root] = 0;

 var queue = [root];

 var current;

 while (queue.length != 0) {

   current = queue.shift();

   var curConnected = graph[current];

   var neighborIdx = [];

   var idx = curConnected.indexOf(1);

   while (idx != -1) {

     neighborIdx.push(idx);

     idx = curConnected.indexOf(1, idx + 1);

   }

   for (var j = 0; j < neighborIdx.length; j++) {

     if (nodesLen[neighborIdx[j]] == Infinity) {

       nodesLen[neighborIdx[j]] = nodesLen[current] + 1;

       queue.push(neighborIdx[j]);

     }

   }

 }

 return nodesLen;

}

测试一下:

var graph = [

 [0, 1, 1, 1, 0],

 [0, 0, 1, 0, 0],

 [1, 1, 0, 0, 0],

 [0, 0, 0, 1, 0],

 [0, 1, 0, 0, 0]

];

console.log(bfs(graph, 1));

// 结果

{

 0: 2,

 1: 0,

 2: 1,

 3: 3,

 4: Infinity

}

就是这样——我们已经介绍了所有常见的数据结构,并给出了JavaScript中的例子。这应该能让你更好地了解数据结构在计算机中的工作原理。祝你编码愉快!

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号