Javascript中有哪些常见的数据结构
本篇文章为大家展示了Javascript中有哪些常见的数据结构,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
成都创新互联公司服务项目包括莱芜网站建设、莱芜网站制作、莱芜网页制作以及莱芜网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,莱芜网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到莱芜省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
1.Stack(栈)
堆栈遵循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(队列)
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(链表)
从字面上看,链表是一个链式数据结构,每个节点由两个信息组成:节点的数据和指向下一个节点的指针。链表和传统数组都是线性数据结构,具有序列化的存储方式。当然,它们也有差异:
比较 | Array | Linked 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(集合)
集合是数学的基本概念:定义明确且不同的对象的集合。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(哈希表)
哈希表是一种键值数据结构。由于通过键值查询的速度快如闪电,所以常用于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(树)
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:子节点数
这里以二叉树为例。每个节点最多有两个节点,左边节点比当前节点小,右边节点比当前节点大。
二叉树中的常用方法:
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”)
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(图)
Graph(有时称为网络)是指具有链接(或边)的节点集。根据联系是否有方向性,可以进一步分为两组(即定向图和不定向图)。Graph在我们的生活中被广泛使用——在导航应用中计算最佳路线,或者在社交媒体中推荐朋友,举两个例子。
图有两种表示形式:
邻接清单
在此方法中,我们在左侧列出所有可能的节点,并在右侧显示已连接的节点。
邻接矩阵
相邻矩阵以行和列的形式显示节点,行和列的交点诠释了节点之间的关系,0表示没有联系,1表示有联系,>1表示权重不同。
要查询图中的节点,必须用 “宽度优先搜索"(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中有哪些常见的数据结构,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注创新互联行业资讯频道。
本文题目:Javascript中有哪些常见的数据结构
本文来源:http://scyanting.com/article/iiejph.html