本文共 13939 字,大约阅读时间需要 46 分钟。
push
:将一个元素推入栈顶
pop
:移除栈顶元素,并返回被移除的元素
peek
:返回栈顶元素
length
:返回栈中元素的个数
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; } }
enqueue
:入列,向队列尾部增加一个元素
dequeue
:出列,移除队列头部的一个元素并返回被移除的元素
front
:获取队列的第一个元素
isEmpty
:判断队列是否为空
size
:获取队列中元素的个数
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; } }
enqueue
方法的实现: 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); } } } }
[ [ 'spartacus', 1 ], [ 'crixus', 2 ], [ 'gannicus', 3 ], [ 'oenomaus', 4 ] ]
比较维度 | 数组 | 链表 |
内存分配 | 静态内存分配,编译时分配且连续 | 动态内存分配,运行时分配且不连续 |
元素获取 | 通过Index获取,速度较快 | 通过遍历顺序访问,速度较慢 |
添加删除元素 | 因为内存位置连续且固定,速度较慢 | 因为内存分配灵活,只有一个开销步骤,速度更快 |
空间结构 | 可以是一维或者多维数组 | 可以是单向、双向或者循环链表 |
size
:返回链表中节点的个数
head
:返回链表中的头部元素
add
:向链表尾部增加一个节点
remove
:删除某个节点
indexOf
:返回某个节点的index
elementAt
:返回某个index处的节点
addAt
:在某个index处插入一个节点
removeAt
:删除某个index处的节点
/** * 链表中的节点 */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; }}
values
:返回集合中的所有元素
size
:返回集合中元素的个数
has
:判断集合中是否存在某个元素
add
:向集合中添加元素
remove
:从集合中移除某个元素
union
:返回两个集合的并集
intersection
:返回两个集合的交集
difference
:返回两个集合的差集
subset
:判断一个集合是否为另一个集合的子集
add
:增加一组键值对
remove
:删除一组键值对
lookup
:查找一个键对应的值
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]; } } } } }
Root(根):代表树的根节点,根节点没有父节点
Parent Node(父节点):一个节点的直接上级节点,只有一个
Child Node(子节点):一个节点的直接下级节点,可能有多个
Siblings(兄弟节点):具有相同父节点的节点
Leaf(叶节点):没有子节点的节点
Edge(边):两个节点之间的连接线
Path(路径):从源节点到目标节点的连续边
Height of Node(节点的高度):表示节点与叶节点之间的最长路径上边的个数
Height of Tree(树的高度):即根节点的高度
Depth of Node(节点的深度):表示从根节点到该节点的边的个数
Degree of Node(节点的度):表示子节点的个数
add
:向树中插入一个节点
findMin
:查找树中最小的节点
findMax
:查找树中最大的节点
find
:查找树中的某个节点
isPresent
:判断某个节点在树中是否存在
remove
:移除树中的某个节点
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没有子节点 if (node.left == null && node.right == null) { return null; } // node没有左侧子节点 if (node.left == null) { return node.right; } // node没有右侧子节点 if (node.right == null) { return node.left; } // node有两个子节点 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));
add
:向字典树中增加一个单词
isWord
:判断字典树中是否包含某个单词
print
:返回字典树中的所有单词
/** * 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; } }
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 }
转载地址:http://aufpi.baihongyu.com/