Hash table

<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta Name ="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> </head> <body> The efficiency of inserting and deleting arrays is low.2. Search 2.1 The Efficiency of Searching based on indexes is High. Modified 3.1 High efficiency based on index 3.2 Low Efficiency Based on Content Hash table Implements insert, delete and search operations based on array Very high The hash table is faster than the tree. Disadvantages: Data is not sequential, the key value can not repeat the hash table in the hash, the resulting subscript value conflict, there are two solutions: 1, chain address method (zipper method) 2. Open address method </body> <script> // hash function // convert a string to a larger number // Compress a larger number hashcode into an array range (size) Size) {// define the hashcode variable let hashcode = 0; For (let I = 0; i < str.length; HashCode = 37 * hashCode + str.charcodeat (I)} let index = hashCode % size return index Function HashTable () {this.storage = [] this.count = 0 this.limit = 7 // Hash function HashTable. Prototype. HashFunc = function (STR, size) {/ / hashcode variables let hashcode = 0; For (let I = 0; i < str.length; HashCode = 37 * hashCode + str.charcodeat (I)} let index = hashCode % size return index // Insert and modify operations are the same method /* 1. Get index value based on key (purpose: to insert data into corresponding position) 2. 2.1 If the bucket does not exist, create a bucket and place the data in the index. 3. Determine whether to add or modify the original value 3.1 if there is a value, modify the value 3.2 if there is no value, Prototype put = function (key, value) {// Let index = this.hashfunc (key, Let bucket = this.storage[index] // Check whether bucket is null if (bucket === null) {bucket = [] this. Storage [index] = bucket} for (let I = 0; i < bucket.length; I ++) {let tuple = bucket[I] if (tuple[0] == key) {tuple[1] = value return}} If (this.count > this.limit * 0.75) {let sizeNum = this.limit * 2 // To ensure that the capacity is a prime number Let newSize = this.getPreim (sizeNum) this.resize(newSize)}} hashtable.prototype. get = function (key)  let index = this.hashFunc(key, Let bucket = this. Storage [index] if (bucket === null) {return null} for (let I = 0;  i < bucket.length; i++) { let tuple = bucket[i] if (tuple[0] === key) { return tuple[1] } } return null } HashTable.prototype.remove = Function (key) {// Let index = this.hashfunc (key, Let bucket = this. Storage [index] if (bucket === null) {return null} for (let I = 0;  i < bucket.length; I ++) {let tuple = bucket[I] if (tuple[0] === key) {// Delete bucket.splice(I,1) this.count -= 1 return tuple[1] // Reduce the capacity if (this.limit > 7 && this.count < this.limit * 0.25){let sizeNum = math.floor (this.limit / 2) // To ensure that the capacity must be a prime let newSize = this.getpreim(sizeNum) this.resize(newSize) } } } return null } HashTable.prototype.isEmpty = function () { Return this.count == 0} hashtable.prototype. size = function () {return this.count HashTable. Prototype. The resize = function (newLimit) {/ / save the old array contents let oldSrorage = this. Storage / / reset all attributes this. Storage = [] this. Count = 0 this. Limit = newLimit i< oldSrorage.length; i++) { let bucket = oldSrorage[i] if (bucket == null) { continue } for (let j = 0; j < bucket.length; j++) { let tuple = bucket[j] this.put(tuple[0], Tuple [1])}}} / / distinguish the prime HashTable. Prototype. IsPre = function (num) {/ / for num square let temp = parseInt (math.h SQRT (num)) // for (let I = 2; i <= temp; I++) {if I = = 0) (num % {return false}} return true} / / to get prime method HashTable. Prototype. Getpreim = function (num) { while(! This. IsPre (num)) {num ++} return num}} function isPrime(num) {for(let I = 2; i< num; I ++) {if (num % I == 0) {return false}} return true} function isPre(num) {// get num square let temp = ParseInt (math.sqrt (num)) for (let I = 2; i <= temp; i++) { if (num % i == 0) { return false } } return true } alert(hashFunc('abc', 7)) </script> </html>Copy the code

A collection of

<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta  name="viewport" content="width=device-width, Initial-scale =1.0"> <title>Document</title> </head> <body> </body> <script Set {} / / method. The prototype. From = function (value) {return this. The items. The hasOwnProperty (value)} Set. The prototype. The add = function (value) { if (this.has(value)) { return false } this.items[value] = value return true } Set.prototype.remove = function (value) {// Whether the collection contains the element if (! this.has(value)) { return false } delete this.items[value] return true } Set.prototype.clear = function () { this.items = {} } Set.prototype.size = function (value) { return Object.keys(this.items).length } Set.prototype.values = function Set.prototype.union = function (otherSet) {// otherSet other sets let unionSet = new Set() let values = this.values() for (let i = 0; i < values.length; i++) { unionSet.add(values[i]) } values = otherSet.values() for (let i = 0; i< values.length; I++) {unionSet. Add (values) [I]} return unionSet} Set. The prototype. The intersection computes = function (otherSet) {/ / otherSet other collections let intersectionSet = new Set() let values = this.values() for (let i = 0; i< values.length; i ++) { let item = values[i] if (otherSet.has(item)) { intersectionSet.add(item) } } return intersectionSet } Set.prototype.difference = function (otherSet) {// otherSet otherSet let differenceSet = new Set() let values = this.values() for (let i = 0; i < values.length; i++) { let item = values[i] if (! Otherset.has (item)) {differenceset.add (item)}} return differenceSet} // subSet set.prototype. subSet = function (otherSet) { let values = this.values() for (let i = 0; i< values.length; i ++) { let item = values[i] if (! otherSet.has(item)) { return false } } return true } } </script> </html>Copy the code

The list

<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta  name="viewport" content="width=device-width, Initial-scale =1.0"> <title>Document</title> </head> <body> </body> <script>  { this.data = data; this.next = null; } this.head = null; this.length = 0; / / append method LinkedList. Prototype. Append = function (data) {let newNode = new Node (data) / / judge whether to add the if is the first Node (this length === 0) {// let newNode = newNode (data) this.head = newNode} else {// let newNode = newNode (data) // Let current = this.head while (current. Next) {current = current. Next} // Next of the last node specifies the new node current newNode } this.length += 1; } / / toString method LinkedList. Prototype. ToString = function () {let current = this. Head let listString = "while" (current) { listString += current.data + "" current = current.next } return listString } // LinkedList.prototype.insert = function (position, data) {/ / to crossing the line judge if the position (the position < 0 | | position > this. Length) return false. Let newNode = new node (data) // 3. If (position === 0) {newNode.next = this.head this.head = newNode} else {let index = 0 let current = This. Head // current let previous = null // previous while (index ++ < position) {previous = current current = current. Head} Newnode. next = current previous.next = newNode} this.length += 1 return true} // get method linkedlist.prototype.get = function (position) { if (position < 0 || position >= this.length) return false; let current = this.head let index = 0 while (index++ < position) { current = current.next } return current.data } // indexOf LinkedList.prototype.indexOf = function (data) { let current = this.head let index = 0 while (current) { if (current.data === data) { return index } current = current.next index += 1 } return -1 } // update LinkedList.prototype.update = function (position, NewDate) {/ / determine if seams (position < 0 | | position > = this. Length), return false. Let current = this.head let index = 0 while (index++ < position) {current = current To replace the data that postionwenode newDAta current. Data = newDate return true} / / removeAt (position) LinkedList. Prototype. The removeAt =  function (position) { if (postion < 0 || position >= this.length) return null; let current = this.head if (position === 0) { this.head = this.head.next } else { let index = 0; let previous = null while (index ++ < position) { previous = current current = current.next } previous.next = current.next } this.length -= 1 return current.data } // remove LinkedList.prototype.remove = function (data) { // 1. Let postion = this.indexof (data) return this.removeat (position)}} let list = new LinkedList() list.append('abc') list.append('ccc') console.log(list, '---list') alert(list) </script> </html>Copy the code

Two-way linked list

<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta  name="viewport" content="width=device-width, Initial-scale =1.0"> <title>Document</title> </head> <body> </body> <script> function DoubleLinkedList() {function Node(data) { this.data = data this.prev = null this.next = null } this.head = null; Enclosing tail = null enclosing length = 0 / / DoubleLinkedList append method. The prototype. Append = function (data) {let newNode = new Node(data) if (this.length === 0) { this.head = newNode this.tail = newNode } else { newNode.prev = this.tail this.tail.next = newNode this.tail = newNode } this.length += 1 } DoubleLinkedList.prototype.toString = function () { return this.backwardString() } DoubleLinkedList.prototype.forwardString = function () { let current = this.tail; let resultString = "" while (current) { resultString += current.data + " " current = current.prev } return resultString } DoubleLinkedList.prototype.backwardString = function () { let current = this.head let resultString = "" while (current) { resultString += current.data + "" current = current.next } return resultString } DoubleLinkedList.prototype.insert = function (position, data) { if (position < 0 || position > this.length) return false; If (this.length === 0) {this.head = newNode this.tail = newNode} else {this.head = newNode this.tail = newNode} // Add if (position === 0) {// Add the first node. Next = this.head. Prev = newNode newNode.next = this.head this.head = newNode} else If (position === this.length) {// Add newNode.prev = this.tail this.tail.next = newNode this.tail = newNode} else {// Add newNode this.tail = newNode. Let current = this.head let index = 0 while (index++ < position) {current = current. Next} newnode.next = current newNode.prev = current.prev current.prev.next = newNode current.prev = newNode } } this.length += 1 } // get(position) DoubleLinkedList.prototype.get = function (position) { if (position < 0 || position >= this.length) return  null; let index = 0; Let current = this.head while (index++ < position) {current = current. Next} return current. Data // optimize TODO // This. Length / 2 > position traverse back / / before this. Length / 2 < position from the back forward} DoubleLinkedList. Prototype. The indexOf = function (data) { let index = 0; let current = this.head while (current) { if (current.data === data) { return index } current = current.next index += 1 } return -1 } DoubleLinkedList.prototype.update = function (position, newdata) { if (position < 0 || position >= this.length) return false; let index = 0; let current = this.head while (index++ < position) { current = current.next } current.data = newdata return true } DoubleLinkedList.prototype.removeAt = function (position) { if (position < 0 || position >= this.length) return null; Let current = this.head if (this.length === = 1) {this.tail = null this.head = null} else {// Check whether the first node is deleted if (position == 0) { this.head.next.prev = null; this.head = this.head.next } else if (position === this.length -1) { current = this.tail this.tail.prev.next = null this.tail = this.tail.prev } else { let index = 0 while (index++ < position) { current = current.next } current.prev.next = current.next current.next.prev = current.prev } } this.length -= 1 return current.data } DoubleLinkedList.prototype.remove = function (data) { let index = this.indexOf(data) return this.removeAt(index) } } let  DoubleList = new DoubleLinkedList() </script> </html>Copy the code

Queue (Priority queue)

<! DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta  name="viewport" content="width=device-width, Initial-scale =1.0"> <title>Document</title> </head> <body> </body> <script> function PriorityQueue() {function QueElement(element, priority) { this.element = element this.priority = priority } this.items = [] PriorityQueue.prototype.enqueue = function  (element, priority) { let queElement = new QueElement(element, priority) if (this.items.lenght === 0) { this.items.push(queElement) } else { let added = false for (let i = 0; i< this.items.length; i ++) { if (queElement.priority < this.items[i].priority) { this.items.splice(i, 0, queElement) added = true break } } if (! added) { this.items.push(queElement) } } } } let pq = new PriorityQueue() function Stack() { this.items = []; Stack.prototype.push = function(ele) { this.items.push(ele) } Stack.prototype.pop = function() { this.items.pop() } Stack.prototype.peek = function() { return this.items[items.lenght - 1] } Stack.prototype.isEmpty = function () { return  this.items.lenght === 0 } Stack.prototype.size = function () { return this.items.lenght } Stack.prototype.toString = function () { // return this.items.join(' ') return this.items.toString() } } let stack = new Stack() </script> </html>Copy the code

The tree

Constructor () {this.root = null; this.Node = function Node (key) { this.key = key this.left = null this.right = null }; } // Node(key) {// this.key = key // this.left = null // this.right = null //} // insertNode (Node, NewNode) {if (newNode.key < node.key) {// Look left if (node.left === null) {node.left = newNode} else {// Look left if (node.left === null) {node.left = newNode} else { this.insertNode(node.left, If (node.right === null) {node.right = newNode} else {this.insertNode(node.right, node.right, node.right) Insert (key) {// create a Node let newNode = new this.Node(key) // Check whether the root Node has a value if (this.root === null) { This. root = newNode} else {this.insertNode(this.root, newNode)}} handler) { if (node ! == null) {handler(node.key) {this.preOrderTreenode (node.left, this.preOrderTreenode (node.left, node.left); This.preordertreenode (node.right, PreOrderTree (handler) {this.preorderTreenode (this.root, Handler)} midOrderTree(handler) {this.midOrderTreenode (this.root, handler)} midOrderTreeNode(node, handler) { if (node ! == null) {this.midOrderTreenode (node.left, Handler (node.key) handler(node.key) this.midOrderTreenode (node.right, Handler)}} min() {let node = this.root; let key = null; while(node ! == null) { key = node.key node = node.left } return key } max () { let node = this.root let key = null while(node ! == null) {key = node.key node = node.right} return key} // Search for specific values key search (key) {let node = this.root while (node) ! == null) { if (node.key > key) { node = node.left } else if (key > node.key) { node = node.right } else if (key === Key){return true}} return false} // Delete // find the node to delete first // 1. Check whether the left and right node of the parent node is left or right // 2. The node to be deleted has only one left or right node. Direct the left or right node of the parent node to the left or right node to be deleted. Remove (key) {// Find the node to remove, // define variables, Let current = this.root let parent = null let isLeftChild = true == key) { parent = current if (key < parent.key) { isLeftChild = true current = current.left } else { isLeftChild = If (current === null) return false} // Find current. Key == key // 1 (current.right === null && current.left === null) { if (current === this.root) { this.root = null } else if (isLeftChild) { parent.left = null } else { parent.right = null } } // 2. else if (current.right === null && IsLeftChild) {// If only one root node, If (current === this.root) {this.root = current. Left} else {parent.left = current. Left}} else if (current.right === null && ! isLeftChild) { if (current === this.root) { this.root = current.left } else { parent.right = current.left } } else if (current.left === null && isLeftChild) { if (current === this.root) { this.root = current.right } else { parent.left = current.right } } else if (current.left === null && ! isLeftChild) { if (current === this.root) { this.root = current.right } else { parent.right = current.right } } // 3. // The maximum value of the left subtree (precursor) is the minimum value of the right subtree (successor). If (current === this.root) {if (current === this.root) {this.root = antecedent Succeeded} else if (isLeftChild) {parent. Left = antecedent} else {parent. Right = antecedent Left = current. Left}} // The method to find the successor getend(delNode) {// Save the found let forerunner = delNode let current = delNode.right let successorParent = delNode while (current ! == null) {successorParent = current current = current. Left} // Determine whether the successorParent is directly the right delNode if ( successor ! == delNode.right) { successorParent.left = successor.right successor.right = delNode.right } return successor } } let bst = new Tree() bst.insert(11) bst.insert(7) bst.insert(15) bst.insert(5) bst.insert(3) bst.insert(9) bst.insert(8) bst.insert(10) bst.insert(13) bst.insert(12) bst.insert(14) bst.insert(20) bst.insert(18) bst.insert(25) console.log(bst) let resultString = "" bst.preOrderTree((key) => { resultString += key + " " }) console.log(resultString.split(" "), Bst.midordertree ((key) => {resultString1 += key + ""}) Console. log(resultString1.split(" "), 'middle order traversal ') console.log(bst.min(), bst.max())Copy the code

The dictionary

function Dictionay() { this.items = {} Dictionay.prototype.set = function (key, value) { this.items[key] = value } Dictionay.prototype.has = function (key) { return this.items.hasOwnProperty(key) } Dictionay.prototype.remove = function (key) { if (! this.has(key)) return false delete this.items[key] return true } Dictionay.prototype.get = function (key) { return this.has(key) ? this.items[key] : undefined } Dictionay.prototype.keys = function () { return Object.keys(this.items) } Dictionay.prototype.size = function () { return this.keys().length } Dictionay.prototype.clear = function () { this.items = {} } }Copy the code

figure

Function Graph() {// attribute: Vertices (array) (dictionary) enclosing vertexes = [] this. Edges = new Dictionay () method of adding vertex / / Graph. The prototype. AddVertex = function (v) { Array.edge = function (array.edge); array.edge = function (array.edge); array.edge = function (array.edge); array.edge = function (array.edge); array.edge = function (array.edge); Enclosing v2) {/ / undirected Graph edges. The get (v1). Push (v2) enclosing edges. The get (v2). Push (v1)} Graph. The prototype. ToString = function () {let ResultString = "" // Walk through all vertices and vertices corresponding edges for (let I = 0; i< this.vertexes.length; i ++) { resultString += this.vertexes[i] + '--->' let vEdges = this.edges.get(this.vertexes[i]) for (let j = 0; j< vEdges.length; J ++) {resultString += vEdges[j] + "} resultString += '\n'} return resultString} // BFS breadth first search // DFS depth first search // Both times calendar calculation method need to specify the first vertex to be accessed/color/initialization state Graph. The prototype. InitColor = function () {let colors = [] for (let I = 0; i< this.vertexes.length; I ++) {colors[this.vertexes[I]] = 'white'} return colors} Queue = new queue() // Add vertices to queue. Enqueue (initV) // The loop retrieves the element from the queue while (! Queue.isempty ()) {// Fetch a vertex from the queue let v = queue.dequeue() // Fetch another vertex connected to the vertex let vList = this.edges. Get (v) // set the color of v to grey Color [v] = 'gray' // for (let I = 0; i< vList.length; I ++) {let e = vList[I] if (colors[e] === 'white') {colors[e] = 'gray' queue. Graph.prototype. DFS = function (initV,); // Color [v] = 'black'}} This.dfsvisit (initV, colors,) {let colors = this.initcolor (); handler) } Graph.prototype.dfsVisit =function (v, colors, Beagles; beagles = beagles; beagles = beagles; beagles = beagles; beagles = beagles; i< vList.length; i++) { let e = vList[i] if (colors[e] === 'white') { this.dfsVisit(e, colors, // color [v] = 'black'}}Copy the code