更好地了解數據結構如何工作

這聽起來是否熟悉："我通過完成網上課程開始了前端開發"

您可能正在尋求提高計算機科學的基礎知識，尤其是在數據結構和算法方面。 今天，我們將介紹一些常見的數據結構，并以JAVAScript實施它們。

希望這部分內容可以補充您的技能！

 

1.Stack 堆棧

 

堆棧遵循LIFO（后進先出）的原理。 如果您堆疊書籍，則最上層的書籍將排在最底層的書籍之前。 或者，當您在Internet上瀏覽時，后退按鈕會將您帶到最近瀏覽的頁面。

Stack具有以下常見方法：

· push：輸入一個新元素

· pop：刪除頂部元素，返回刪除的元素

· peek：返回頂部元素

· length：返回堆棧中的元素數

JavaScript中的數組具有Stack的屬性，但是我們使用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 隊列

 

隊列類似于堆棧。 唯一的區別是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.鏈表

 

從字面上看，鏈表是一個鏈式數據結構，每個節點由兩部分信息組成：該節點的數據和指向下一個節點的指針。 鏈表和常規數組都是帶有序列化存儲的線性數據結構。 當然，它們也有差異：

 

單邊鏈表通常具有以下方法：

· size：返回節點數

· head：返回head的元素

· add：在尾部添加另一個節點

· delete：刪除某些節點

· indexOf：返回節點的索引

· elementAt：返回索引的節點

· addAt：在特定索引處插入節點

· removeAt：刪除特定索引處的節點

/** Node in the linked list **/
function Node(element) { 
 // Data in the node
 this.element = element; 
 // Pointer to the next node 
 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.集合

 

集合是數學的基本概念：定義明確且不同的對象的集合。 ES6引入了集合的概念，它與數組有一定程度的相似性。 但是，集合不允許重復元素，也不會被索引。

一個典型的集合具有以下方法：

· values：返回集合中的所有元素

· size：返回元素數

· has：確定元素是否存在

· add：將元素插入集合

· delete：從集合中刪除元素

· union：返回兩組的交集

· difference：返回兩組的差異

· subset：確定某個集合是否是另一個集合的子集

為了區分ES6中的集合，在以下示例中我們聲明為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.哈希表

 

哈希表是鍵值數據結構。 由于通過鍵查詢值的閃電般的速度，它通常用于Map，Dictionary或Object數據結構中。 如上圖所示，哈希表使用哈希函數將鍵轉換為數字列表，這些數字用作相應鍵的值。 要快速使用鍵獲取價值，時間復雜度可以達到O（1）。 相同的鍵必須返回相同的值-這是哈希函數的基礎。

哈希表具有以下方法：

· add：添加鍵值對

· delete：刪除鍵值對

· find：使用鍵查找對應的值

Java簡化哈希表的示例：

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.樹

 

樹數據結構是多層結構。 與Array，Stack和Queue相比，它也是一種非線性數據結構。 在插入和搜索操作期間，此結構非常高效。 讓我們看一下樹數據結構的一些概念：

· root：樹的根節點，無父節點

· parent 父節點：上層的直接節點，只有一個

· children 子節點：較低層的直接節點，可以有多個

· siblings 兄弟姐妹：共享同一父節點

· leaf 葉：沒有子節點

· edge 邊緣：節點之間的分支或鏈接

· path 路徑：從起始節點到目標節點的邊緣

· height of node 節點高度：特定節點到葉節點的最長路徑的邊數

· height of tree 樹的高度：根節點到葉節點的最長路徑的邊數

· depth of node 節點深度：從根節點到特定節點的邊數

· degree of node 節點度：子節點數

這是二叉搜索樹的示例。 每個節點最多有兩個節點，左節點小于當前節點，右節點大于當前節點：

 

二進制搜索樹中的常用方法：

· add：在樹中插入一個節點

· findMin：獲取最小節點

· findMax：獲取最大節點

· find：搜索特定節點

· isPresent：確定某個節點的存在

· delete：從樹中刪除節點

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"）

 

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在我們的生活中得到了廣泛使用，例如，在導航應用中計算最佳路線，或者在社交媒體中向推薦的朋友舉兩個例子。

圖有兩種表示形式：

鄰接表

在此方法中，我們在左側列出所有可能的節點，并在右側顯示已連接的節點。

 

鄰接矩陣

鄰接矩陣顯示行和列中的節點，行和列的交點解釋節點之間的關系，0表示未鏈接，1表示鏈接，> 1表示不同的權重。

 

要查詢圖中的節點，必須使用"廣度優先"（BFS）方法或"深度優先"（DFS）方法在整個樹形網絡中進行搜索。

讓我們看一個用Javascript編寫BFS的示例：

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中的示例。 這應該使您更好地了解計算機中數據結構的工作方式。 編碼愉快！

 

(本文翻譯自Kingsley Tan的文章《8 Common Data Structures in Javascript》， 參考 https://medium.com/better-programming/8-common-data-structures-in-javascript-3d3537e69a27)