建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
常見數(shù)據(jù)結構和Javascript實現(xiàn)總結
做前端的同學不少都是自學成才或者半路出家，計算機基礎的知識比較薄弱，尤其是數(shù)據(jù)結構和算法這塊，所以今天整理了一下常見的數(shù)據(jù)結構和對應的Javascript的實現(xiàn)，希望能幫助大家完善這方面的知識體系。
創(chuàng)新互聯(lián)"三網(wǎng)合一"的企業(yè)建站思路。企業(yè)可建設擁有電腦版、微信版、手機版的企業(yè)網(wǎng)站。實現(xiàn)跨屏營銷，產(chǎn)品發(fā)布一步更新，電腦網(wǎng)絡+移動網(wǎng)絡一網(wǎng)打盡，滿足企業(yè)的營銷需求！創(chuàng)新互聯(lián)具備承接各種類型的成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設項目的能力。經(jīng)過十多年的努力的開拓，為不同行業(yè)的企事業(yè)單位提供了優(yōu)質(zhì)的服務，并獲得了客戶的一致好評。
1. Stack(棧)
Stack的特點是后進先出(last in first out)。生活中常見的Stack的例子比如一摞書，你最后放上去的那本你之后會最先拿走;又比如瀏覽器的訪問歷史，當點擊返回按鈕，最后訪問的網(wǎng)站最先從歷史記錄中彈出。
- Stack一般具備以下方法：
- push：將一個元素推入棧頂
- pop：移除棧頂元素，并返回被移除的元素
- peek：返回棧頂元素
- length：返回棧中元素的個數(shù)
Javascript的Array天生具備了Stack的特性，但我們也可以從頭實現(xiàn)一個 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和Stack有一些類似，不同的是Stack是先進后出，而Queue是先進先出。Queue在生活中的例子比如排隊上公交，排在第一個的總是最先上車;又比如打印機的打印隊列，排在前面的最先打印。
- Queue一般具有以下常見方法：
- enqueue：入列，向隊列尾部增加一個元素
- dequeue：出列，移除隊列頭部的一個元素并返回被移除的元素
- front：獲取隊列的第一個元素
- isEmpty：判斷隊列是否為空
- size：獲取隊列中元素的個數(shù)
Javascript中的Array已經(jīng)具備了Queue的一些特性，所以我們可以借助Array實現(xiàn)一個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;
- }
- }
Priority Queue(優(yōu)先隊列)
Queue還有個升級版本，給每個元素賦予優(yōu)先級，優(yōu)先級高的元素入列時將排到低優(yōu)先級元素之前。區(qū)別主要是enqueue方法的實現(xiàn)：
- 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(鏈表)
顧名思義，鏈表是一種鏈式數(shù)據(jù)結構，鏈上的每個節(jié)點包含兩種信息：節(jié)點本身的數(shù)據(jù)和指向下一個節(jié)點的指針。鏈表和傳統(tǒng)的數(shù)組都是線性的數(shù)據(jù)結構，存儲的都是一個序列的數(shù)據(jù)，但也有很多區(qū)別，如下表：
一個單向鏈表通常具有以下方法：
- size：返回鏈表中節(jié)點的個數(shù)
- head：返回鏈表中的頭部元素
- add：向鏈表尾部增加一個節(jié)點
- remove：刪除某個節(jié)點
- indexOf：返回某個節(jié)點的index
- elementAt：返回某個index處的節(jié)點
- addAt：在某個index處插入一個節(jié)點
- removeAt：刪除某個index處的節(jié)點
單向鏈表的Javascript實現(xiàn)：
- /**
- * 鏈表中的節(jié)點
- */
- function Node(element) {
- // 節(jié)點中的數(shù)據(jù)
- this.element = element;
- // 指向下一個節(jié)點的指針
- 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(集合)
集合是數(shù)學中的一個基本概念，表示具有某種特性的對象匯總成的集體。在ES6中也引入了集合類型Set，Set和Array有一定程度的相似，不同的是Set中不允許出現(xiàn)重復的元素而且是無序的。
一個典型的Set應該具有以下方法：
- values：返回集合中的所有元素
- size：返回集合中元素的個數(shù)
- has：判斷集合中是否存在某個元素
- add：向集合中添加元素
- remove：從集合中移除某個元素
- union：返回兩個集合的并集
- intersection：返回兩個集合的交集
- difference：返回兩個集合的差集
- subset：判斷一個集合是否為另一個集合的子集
使用Javascript可以將Set進行如下實現(xiàn)，為了區(qū)別于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. Hash Table(哈希表/散列表)
Hash Table是一種用于存儲鍵值對(key value pair)的數(shù)據(jù)結構，因為Hash Table根據(jù)key查詢value的速度很快，所以它常用于實現(xiàn)Map、Dictinary、Object等數(shù)據(jù)結構。如上圖所示，Hash Table內(nèi)部使用一個hash函數(shù)將傳入的鍵轉(zhuǎn)換成一串數(shù)字，而這串數(shù)字將作為鍵值對實際的key，通過這個key查詢對應的value非?？欤瑫r間復雜度將達到O(1)。Hash函數(shù)要求相同輸入對應的輸出必須相等，而不同輸入對應的輸出必須不等，相當于對每對數(shù)據(jù)打上唯一的指紋。
一個Hash Table通常具有下列方法：
- add：增加一組鍵值對
- remove：刪除一組鍵值對
- lookup：查找一個鍵對應的值
一個簡易版本的Hash Table的Javascript實現(xiàn)：
- 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(樹)
顧名思義，Tree的數(shù)據(jù)結構和自然界中的樹極其相似，有根、樹枝、葉子，如上圖所示。Tree是一種多層數(shù)據(jù)結構，與Array、Stack、Queue相比是一種非線性的數(shù)據(jù)結構，在進行插入和搜索操作時很高效。在描述一個Tree時經(jīng)常會用到下列概念：
- Root(根)：代表樹的根節(jié)點，根節(jié)點沒有父節(jié)點
- Parent Node(父節(jié)點)：一個節(jié)點的直接上級節(jié)點，只有一個
- Child Node(子節(jié)點)：一個節(jié)點的直接下級節(jié)點，可能有多個
- Siblings(兄弟節(jié)點)：具有相同父節(jié)點的節(jié)點
- Leaf(葉節(jié)點)：沒有子節(jié)點的節(jié)點
- Edge(邊)：兩個節(jié)點之間的連接線
- Path(路徑)：從源節(jié)點到目標節(jié)點的連續(xù)邊
- Height of Node(節(jié)點的高度)：表示節(jié)點與葉節(jié)點之間的最長路徑上邊的個數(shù)
- Height of Tree(樹的高度)：即根節(jié)點的高度
- Depth of Node(節(jié)點的深度)：表示從根節(jié)點到該節(jié)點的邊的個數(shù)
- Degree of Node(節(jié)點的度)：表示子節(jié)點的個數(shù)
我們以二叉查找樹為例，展示樹在Javascript中的實現(xiàn)。在二叉查找樹中，即每個節(jié)點最多只有兩個子節(jié)點，而左側子節(jié)點小于當前節(jié)點，而右側子節(jié)點大于當前節(jié)點，如圖所示：
一個二叉查找樹應該具有以下常用方法：
- add：向樹中插入一個節(jié)點
- findMin：查找樹中最小的節(jié)點
- findMax：查找樹中最大的節(jié)點
- find：查找樹中的某個節(jié)點
- isPresent：判斷某個節(jié)點在樹中是否存在
- remove：移除樹中的某個節(jié)點
以下是二叉查找樹的Javascript實現(xiàn)：
- 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沒有子節(jié)點
- if (node.left == null && node.right == null) {
- return null;
- }
- // node沒有左側子節(jié)點
- if (node.left == null) {
- return node.right;
- }
- // node沒有右側子節(jié)點
- if (node.right == null) {
- return node.left;
- }
- // node有兩個子節(jié)點
- 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也可以叫做Prefix Tree(前綴樹)，也是一種搜索樹。Trie分步驟存儲數(shù)據(jù)，樹中的每個節(jié)點代表一個步驟，trie常用于存儲單詞以便快速查找，比如實現(xiàn)單詞的自動完成功能。 Trie中的每個節(jié)點都包含一個單詞的字母，跟著樹的分支可以可以拼寫出一個完整的單詞，每個節(jié)點還包含一個布爾值表示該節(jié)點是否是單詞的最后一個字母。
Trie一般有以下方法：
- add：向字典樹中增加一個單詞
- isWord：判斷字典樹中是否包含某個單詞
- print：返回字典樹中的所有單詞
- /**
- * Trie的節(jié)點
- */
- 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);
- &nbs
網(wǎng)站標題：常見數(shù)據(jù)結構和Javascript實現(xiàn)總結
網(wǎng)站URL：http://m.fisionsoft.com.cn/article/dpehepo.html
