摘要:做前端的同學不少都是自學成才或者半路出家,計算機基礎(chǔ)的知識比較薄弱,尤其是數(shù)據(jù)結(jié)構(gòu)和算法這塊,所以今天整理了一下常見的數(shù)據(jù)結(jié)構(gòu)和對應的的實現(xiàn),希望能幫助大家完善這方面的知識體系。
做前端的同學不少都是自學成才或者半路出家,計算機基礎(chǔ)的知識比較薄弱,尤其是數(shù)據(jù)結(jié)構(gòu)和算法這塊,所以今天整理了一下常見的數(shù)據(jù)結(jié)構(gòu)和對應的Javascript的實現(xiàn),希望能幫助大家完善這方面的知識體系。
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();
結(jié)果:
[ [ "spartacus", 1 ], [ "crixus", 2 ], [ "gannicus", 3 ], [ "oenomaus", 4 ] ]3. Linked List(鏈表)
顧名思義,鏈表是一種鏈式數(shù)據(jù)結(jié)構(gòu),鏈上的每個節(jié)點包含兩種信息:節(jié)點本身的數(shù)據(jù)和指向下一個節(jié)點的指針。鏈表和傳統(tǒng)的數(shù)組都是線性的數(shù)據(jù)結(jié)構(gòu),存儲的都是一個序列的數(shù)據(jù),但也有很多區(qū)別,如下表:
比較維度 | 數(shù)組 | 鏈表 |
---|---|---|
內(nèi)存分配 | 靜態(tài)內(nèi)存分配,編譯時分配且連續(xù) | 動態(tài)內(nèi)存分配,運行時分配且不連續(xù) |
元素獲取 | 通過Index獲取,速度較快 | 通過遍歷順序訪問,速度較慢 |
添加刪除元素 | 因為內(nèi)存位置連續(xù)且固定,速度較慢 | 因為內(nèi)存分配靈活,只有一個開銷步驟,速度更快 |
空間結(jié)構(gòu) | 可以是一維或者多維數(shù)組 | 可以是單向、雙向或者循環(huán)鏈表 |
一個單向鏈表通常具有以下方法:
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ù)結(jié)構(gòu),因為Hash Table根據(jù)key查詢value的速度很快,所以它常用于實現(xiàn)Map、Dictinary、Object等數(shù)據(jù)結(jié)構(gòu)。如上圖所示,Hash Table內(nèi)部使用一個hash函數(shù)將傳入的鍵轉(zhuǎn)換成一串數(shù)字,而這串數(shù)字將作為鍵值對實際的key,通過這個key查詢對應的value非常快,時間復雜度將達到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ù)結(jié)構(gòu)和自然界中的樹極其相似,有根、樹枝、葉子,如上圖所示。Tree是一種多層數(shù)據(jù)結(jié)構(gòu),與Array、Stack、Queue相比是一種非線性的數(shù)據(jù)結(jié)構(gòu),在進行插入和搜索操作時很高效。在描述一個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é)點,而左側(cè)子節(jié)點小于當前節(jié)點,而右側(cè)子節(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沒有左側(cè)子節(jié)點 if (node.left == null) { return node.right; } // node沒有右側(cè)子節(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));
打印結(jié)果:
1 7 6 false7. 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); } } else { string.length > 0 ? words.push(string) : undefined; return; } }; search(this.root, new String()); return words.length > 0 ? words : null; } }8. Graph(圖)
Graph是節(jié)點(或頂點)以及它們之間的連接(或邊)的集合。Graph也可以稱為Network(網(wǎng)絡(luò))。根據(jù)節(jié)點之間的連接是否有方向又可以分為Directed Graph(有向圖)和Undrected Graph(無向圖)。Graph在實際生活中有很多用途,比如:導航軟件計算最佳路徑,社交軟件進行好友推薦等等。
Graph通常有兩種表達方式:
Adjaceny List(鄰接列表):
鄰接列表可以表示為左側(cè)是節(jié)點的列表,右側(cè)列出它所連接的所有其他節(jié)點。
和 Adjacency Matrix(鄰接矩陣):
鄰接矩陣用矩陣來表示節(jié)點之間的連接關(guān)系,每行或者每列表示一個節(jié)點,行和列的交叉處的數(shù)字表示節(jié)點之間的關(guān)系:0表示沒用連接,1表示有連接,大于1表示不同的權(quán)重。
訪問Graph中的節(jié)點需要使用遍歷算法,遍歷算法又分為廣度優(yōu)先和深度優(yōu)先,主要用于確定目標節(jié)點和根節(jié)點之間的距離,
在Javascript中,Graph可以用一個矩陣(二維數(shù)組)表示,廣度優(yōu)先搜索算法可以實現(xiàn)如下:
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));
打?。?/strong>
{ 0: 2, 1: 0, 2: 1, 3: 3, 4: Infinity }
最后,推薦大家使用Fundebug,一款很好用的BUG監(jiān)控工具~
本文旨在向廣大前端同學普及常見的數(shù)據(jù)結(jié)構(gòu),本人對這一領(lǐng)域也只是初窺門徑,說的有差池的地方歡迎指出。也希望大家能打牢基礎(chǔ),在這條路上走的更高更遠!
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/106561.html
摘要:如果沒有學習過計算機科學的程序員,當我們在處理一些問題時,比較熟悉的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,數(shù)組無疑是一個很好的選擇。 showImg(https://segmentfault.com/img/bVTSjt?w=400&h=300); 1、常見 CSS 布局方式詳見: 一些常見的 CSS 布局方式梳理,涉及 Flex 布局、Grid 布局、圣杯布局、雙飛翼布局等。http://cherryb...
摘要:如果沒有學習過計算機科學的程序員,當我們在處理一些問題時,比較熟悉的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,數(shù)組無疑是一個很好的選擇。 showImg(https://segmentfault.com/img/bVTSjt?w=400&h=300); 1、常見 CSS 布局方式詳見: 一些常見的 CSS 布局方式梳理,涉及 Flex 布局、Grid 布局、圣杯布局、雙飛翼布局等。http://cherryb...
摘要:但是在中,的生命還會繼續(xù)。這其中最典型的問題便是批量增加元素。這時,如果構(gòu)造函數(shù)被調(diào)用時沒有參數(shù),則會自動設(shè)置為。因為從系統(tǒng)的角度來說,當你用字符串的時候,它會被傳進構(gòu)造函數(shù),并且重新調(diào)用另一個函數(shù)。 序言 在今天,JavaScript已經(jīng)成為了網(wǎng)頁編輯的核心。尤其是過去的幾年,互聯(lián)網(wǎng)見證了在SPA開發(fā)、圖形處理、交互等方面大量JS庫的出現(xiàn)。 如果初次打交道,很多人會覺得js很簡單...
摘要:創(chuàng)建數(shù)組的基本方式有兩種。為數(shù)組專門提供了和方法,以便實現(xiàn)類似棧的行為。反轉(zhuǎn)數(shù)組,按升序排列數(shù)組項即最小的值位于最前面。例如,會刪除數(shù)組中的前兩項。對數(shù)組中的每一項運行給定函數(shù),返回該函數(shù)會返回的項組成的數(shù)組。 ===什么是數(shù)組=== 數(shù)組是數(shù)據(jù)的有序列表。創(chuàng)建數(shù)組的基本方式有兩種。第一種是使用 Array 構(gòu)造函數(shù):var colors = new Array();創(chuàng)建數(shù)組的第二種基...
摘要:歡迎來我的個人站點性能優(yōu)化其他優(yōu)化瀏覽器關(guān)鍵渲染路徑開啟性能優(yōu)化之旅高性能滾動及頁面渲染優(yōu)化理論寫法對壓縮率的影響唯快不破應用的個優(yōu)化步驟進階鵝廠大神用直出實現(xiàn)網(wǎng)頁瞬開緩存網(wǎng)頁性能管理詳解寫給后端程序員的緩存原理介紹年底補課緩存機制優(yōu)化動 歡迎來我的個人站點 性能優(yōu)化 其他 優(yōu)化瀏覽器關(guān)鍵渲染路徑 - 開啟性能優(yōu)化之旅 高性能滾動 scroll 及頁面渲染優(yōu)化 理論 | HTML寫法...
閱讀 3514·2023-04-25 20:09
閱讀 3720·2022-06-28 19:00
閱讀 3035·2022-06-28 19:00
閱讀 3058·2022-06-28 19:00
閱讀 3132·2022-06-28 19:00
閱讀 2860·2022-06-28 19:00
閱讀 3014·2022-06-28 19:00
閱讀 2611·2022-06-28 19:00