一、数组

  1. //JS数组方法  
  2. concat:连接2个或者更多数组,并返回结果
  3. every:对每一个元素都运行指定函数,如果每一个元素都返回true,则返回true
  4. filter:对每一个元素都运行指定函数,返回该函数会返回true的元素组成的数组
  5. forEach:对每一个元素都运行指定函数,无返回值
  6. join:将所有数组元素连接成一个字符串
  7. indexOf:返回第一个与给定参数相等的元素的索引,木有则返回-1
  8. lastIndexOf:返回在数组中搜索到的与给定参数相等的元素的最后一个元素的索引
  9. map:对数组中的元素运行给定函数,返回每次函数调用的结果组成的数组，新数组
  10. reverse:倒置
  11. slice:传入索引值,将对应索引范围内的元素作为新数组返回
  12. some:对每一个元素都运行指定函数,如果有一个元素返回true,则返回true
  13. sort:按照字母顺序对数组进行排序,支持传入指定排序方法的函数作为参数
  14. toString:作为字符串返回
  15. valueOf:与toString类似
  16. reduce:累加器
  18. function shuffle(array) {
  19.     for(var i = array.length - 1; i > 0; i--) {
  20.       var j = Math.floor(Math.random() * (i + 1));
  21.     var temp = array[i];
  22.     array[i] = array[j];
  23.     array[j] = temp;
  24.   }
  25. }
  26. shuffle(Array.from('today is Monday')).join()

二、栈

  1. function Stack(){
  2.     this.items = [];
  3.     Stack.prototype.push = function(element){
  4.         this.items.push(element);
  5.     }
  6.     Stack.prototype.pop = function(){
  7.         return this.items.pop();
  8.     }
  9.     Stack.prototype.peek = function(){
  10.         return this.items[this.items.length - 1];
  11.     }
  12.     Stack.prototype.isEmpty = function(){
  13.         return this.items.length == 0;
  14.     }
  15.     Stack.prototype.size = function(){
  16.         return this.items.length;
  17.     }
  19.     Stack.prototype.toString = function(){
  20.         var resultString = '';
  21.         for(var i = 0;i < this.items.length;i++){
  22.             resultString += this.items[i] + '';
  23.         }
  24.         return resultString;
  25.     }
  26. }
  27. var stack = new Stack();

三、队列

  1. function Queue(){
  2.     this.items = [];
  3.     Queue.prototype.enqueue = function(element){
  4.         this.items.push(element);
  5.     }
  6.     Queue.prototype.dequeue = function(){
  7.         return this.items.shift();
  8.     }
  9.     Queue.prototype.front = function(){
  10.         return this.items[0];
  11.     }
  12.     Queue.prototype.isEmpty = function(){
  13.         return this,items.length == 0;
  14.     }
  15.     Queue.prototype.size = function(){
  16.         return this.items.length;
  17.     }
  18.     Queue.prototype.toString = function(){
  19.         var resultString = '';
  20.         for(var i = 0;i < this.items.length;i++){
  21.             resultString += this.items[i] + '';
  22.         }
  23.         return resultString;
  24.     }
  25. }
  26. var queue = new Queue();
  1. //击鼓传花:
  2. function passGame(nameList, num){
  3.     var queue = new Queue();
  4.     for(var i = 0;i < nameList.length;i++){
  5.         queue.enqueue(nameList[i]);
  6.     }
  7.     while(queue.size() > 1){
  8.         for(var i = 0;i < num - 1;i++){
  9.             queue.enqueue(queue.dequeue());
  10.         }
  11.         queue.dequeue();
  12.     }
  13.     var endName = queue.front();
  14.     return nameList.indexOf(endName);
  15. }

四、链表

  1. //单向链表
  2. function LinkedList() {
  3.     function Node(data) {
  4.       this.data = data;
  5.     this.next = null;
  6.   }
  7.   this.head = null;
  8.   this.length = 0;
  10.   //单向链表添加
  11.   LinkedList.prototype.append = function(data) {
  12.     if(this.length == 0){
  13.         let newNode = new Node(data);
  14.       this.head = newNode;
  15.     }else{
  16.       let newNode = new Node(data);
  17.         let current = this.head;
  18.       while(current.next){
  19.           current = current.next;
  20.       }
  21.       current = newNode;
  22.     }
  23.     this.length += 1;
  24.   }
  26.   //遍历生成字符串
  27.   LinkedList.prototype.toString = function() {
  28.       let current = this.head;
  29.     let listString = '';
  30.     while(current) {
  31.         listString += current.data + '';
  32.       current = current.next;
  33.     }
  34.     return listString;
  35.   }
  37.   //指定位置插入
  38.   LinkedList.prototype.insert = function(position, data) {
  39.       if(position < 0 || positon > this.length) return false;
  40.     let newNode = new Node(data);
  41.     if(positon == 0) {
  42.         newNode.next = this.head;
  43.       this.head = newNode;
  44.     }else{
  45.       let index = 0;
  46.       let current = this.head;
  47.       let previous = null;
  48.       while(index++ < position){
  49.           previous = current;
  50.         current = current.next;
  51.       }
  52.       newNode.next = current;
  53.       previous.next = newNode;
  54.     }
  55.     this.length += 1;
  56.     return true;
  57.   }
  59.   //查找指定位置的值
  60.   LinkedList.prototype.get = function(position) {
  61.       if(position < 0 || position >= this.length) return null;
  62.     let current = this.head;
  63.     let index = 0;
  64.     while(index++ < position) {
  65.         current = current.next;
  66.     }
  67.     return current.data
  68.   }
  70.   //根据值查找位置
  71.   LinkedList.prototype.indexOf = function(data) {
  72.       let current = this.head;
  73.     let index = 0;
  74.     while(current) {
  75.         if(current.data == data) {
  76.           return index;
  77.       }
  78.       current = current.next;
  79.       index += 1;
  80.     }
  81.     return -1;
  82.   }
  84.   //根据位置删除数据
  85.   LinkedList.prototype.removeAt = function(position) {
  86.       if(position < 0 || position >= this.length) return false;
  87.     if(position == 0) {
  88.         this.head = this.head.next;
  89.     }else{
  90.         let current = this.head;
  91.       let index = 0;
  92.       let previous = null;
  93.       while(index ++ < position) {
  94.           previous = current;
  95.         current = current.next;
  96.       }
  97.       previous.next = current.next;
  98.     }
  99.     this.length -= 1;
  100.     return true;
  101.   }
  103.   //根据值删除数据
  104.   LinkedList.prototype.remove = function(data) {
  105.       let position = this.indexOf(data);
  106.     return this.removeAt(position);
  107.   }
  108. }
  1. //双向链表
  2. //链接是双向的,一个链向下一个元素,一个链向上一个元素,同时控制next和prev两个指针
  3. //head/tail
  4.         function DoublyLinkedList(){
  5.             function Node(data){
  6.                 this.data = null;
  7.                 this.prev = null;
  8.                 this.next = null;
  9.             }
  10.             this.head = null;
  11.             this.tail = null;
  12.             this.length = 0;
  13.             DoublyLinkedList.prototype.append = function (data){
  14.                 var newNode = new Node(data);
  15.                 if(this.length == 0){
  16.                     this.head = newNode;
  17.                     this.tail = newNode;
  18.                 }else{
  19.                     newNode.prev = this.tail;
  20.                     this.tail.next = newNode;
  21.                     this.tail = newNode;
  22.                 }
  23.                 this.length += 1;
  24.             }
  25.             DoublyLinkedList.prototype.toString = function(){
  26.                 return this.backwardString();
  27.             }
  28.             DoublyLinkedList.prototype.forwardString = function(){
  29.                 var current = this.tail;
  30.                 var resultString = "";
  31.                 while(current){
  32.                     resultString += current.data + "";
  33.                     current = current.prev;
  34.                 }
  35.                 return resultString;
  36.             }
  37.             DoublyLinkedList.prototype.backwardString = function(){
  38.                 var current = this.head;
  39.                 var resultString = "";
  40.                 while(current){
  41.                     resultString += current.data + "";
  42.                     current = current.next;
  43.                 }
  44.                 return resultString;
  45.             }
  47.             DoublyLinkedList.prototype.insert = function(position, data){
  48.                 if(position < 0 || position > this.length) return false;
  49.                 var newNode = new Node(data);
  50.                 if(this.length == 0){
  51.                     this.head = newNode;
  52.                     this.tail = newNode;
  53.                 }else{
  54.                     if(postion == 0){
  55.                         this.head.prev = newNode;
  56.                         newNode.next = this.head;
  57.                         this.head = newNode;
  58.                     }else if(position == this.length){
  59.                         newNode.prev = this.tail;
  60.                         this.tail.next = newNode;
  61.                         this.tail = newNode;
  62.                     }else{
  63.                         var current = this.head;
  64.                         var index = 0;
  65.                         while(index++ < position){
  66.                             current = current.next;
  67.                         }
  68.                         newNode.next = current;
  69.                         newNode.prev = current.prev;
  70.                         current.prev.next = newNode;
  71.                         current.prev = newNode;
  72.                     }
  73.                 }
  74.                 this.length += 1;
  75.                 return true;
  76.             }
  77.             DoublyLinkedList.prototype.get = function(position){
  78.                 if(position < 0 || position >= this.length) return null;
  79.                 var current = this.head;
  80.                 var index = 0;
  81.                 while(index++ < position){
  82.                     current = current.next;
  83.                 }
  84.                 return current.data;
  85.             }
  86.             DoublyLinkedList.prototype.indexOf = function(data){
  87.                 var current = this.head;
  88.                 var index = 0;
  89.                 while(current){
  90.                     if(current.data == data){
  91.                         return index;
  92.                     }
  93.                     current = current.next;
  94.                     index += 1;
  95.                 }
  96.                 return -1;
  97.             }
  98.             DoublyLinkedList.prototype.update = function(position, newData){
  99.                 if(position < 0 || position >= this.length) return false;
  100.                 var current = this.head;
  101.                 var index = 0;
  102.                 while(index++ < position){
  103.                     current = current.next;
  104.                 }
  105.                 current.data = newData;
  106.                 return true;
  107.             }
  108.             DoublyLinkedList.prototype.removeAt = function(position){
  109.                 if(position < 0 || position >= this.length) return null;
  110.                 var current = this.head;
  111.                 if(this.length == 1){
  112.                     this.head = null;
  113.                     this.tail = null;
  114.                 }else{
  115.                     if(position == 0){
  116.                         this.head.next.prev = null;
  117.                         this.head = this.head.next;
  118.                     }else if(position == this.length - 1){
  119.                         var current = this.tail;
  120.                         this.tail.prev.next = null;
  121.                         this.tail = this.tail.prev;
  122.                     }else{
  123.                         var index = 0;
  124.                         while(index++ < position){
  125.                             current = current.next;
  126.                         }
  127.                         current.prev.next = current.next;
  128.                         current.next.prev = current.prev;
  129.                     }
  130.                 }
  131.                 this.length -=1;
  132.                 return current.data;
  133.             }
  134.             DoublyLinkedList.prototype.remove = function(){
  135.                 var index = this.indexOf(data);
  136.                 return this.removeAt(index);
  137.             }
  138.         }

五、集合

  1. // 集合
  2. function Set() {
  3.     this.items = {};
  4.     Set.prototype.add = function(value) {
  5.         if(this.has(value)) {
  6.             return false;
  7.         }
  8.         this.items[value] = value;
  9.         return true;
  10.     }
  11.     Set.prototype.has = function(value) {
  12.         return this.items.hasOwnProperty(value);
  13.     }
  14.     Set.prototype.remove = function(value) {
  15.         if(!this.has(value)) {
  16.             return false;
  17.         }
  18.         delete this.items[value];
  19.         return true;
  20.     }
  21.     Set.prototype.clear = function() {
  22.         this.item = {};
  23.     }
  24.     Set.prototype.size = function() {
  25.         return Object.keys(this.items).length;
  26.     }
  27.     Set.prototype.values = function() {
  28.         return Object.keys(this.items);
  29.     }
  30. }

六、字典

  1. // 字典
  2. //一一对应,key不可以重复,value可以重复,key无序
  3. // 创建字典的构造函数
  4. function Dictionary() {
  5.     // 字典属性
  6.     this.items = {}
  7.     // 字典操作方法
  8.     // 在字典中添加键值对
  9.     Dictionary.prototype.set = function (key, value) {
  10.         this.items[key] = value
  11.     }
  12.     // 判断字典中是否有某个key
  13.     Dictionary.prototype.has = function (key) {
  14.         return this.items.hasOwnProperty(key)
  15.     }
  16.     // 从字典中移除元素
  17.     Dictionary.prototype.remove = function (key) {
  18.         // 1.判断字典中是否有这个key
  19.         if (!this.has(key)) return false
  20.         // 2.从字典中删除key
  21.         delete this.items[key]
  22.         return true
  23.     }
  24.     // 根据key去获取value
  25.     Dictionary.prototype.get = function (key) {
  26.         return this.has(key) ? this.items[key] : undefined
  27.     }
  28.     // 获取所有的keys
  29.     Dictionary.prototype.keys = function () {
  30.         return Object.keys(this.items)
  31.     }
  32.     // 获取所有的value
  33.     Dictionary.prototype.values = function () {
  34.         return Object.values(this.items)
  35.     }
  36.     // size方法
  37.     Dictionary.prototype.size = function () {
  38.         return this.keys().length
  39.     }
  40.     // clear方法
  41.     Dictionary.prototype.clear = function () {
  42.         this.items = {}
  43.     }
  44. }
  45. // 创建字典对象
  46. var dict = new Dictionay()

七、哈希表

// ##哈希表
//1.优势:非常快速的插入-删除-查找操作,比树还快
//2.缺点:数据没有顺序,不能以固定的方式来遍历
//3.哈希表究竟是个啥?
//结构就是数组,神奇于下标值的变换-哈希函数,获取HashCode
//将字符串转成下标值
//4.哈希化:将指定数据（例如key）转化为数组范围内下标的过程
//5.哈希表:将最终数据插入数组,进行封装
//6.重复问题:转化下标的过程中会出现下标相同的情况
//7.解决方案一:链地址法-也就是存入数组的是一个数组/链表
//8.解决方案二:开放地址法-继续向下寻找空白位置来放置重复数据
//9.哈希表效率更高:哈希化越好,也就是减少重复,进而要求哈希函数设计的巧妙
//霍纳法则-秦九韶算法:多项式-O(n^2) -> O(n)
//那就是哈希表就是通过将关键值也就是key通过一个散列函数加工处理之后得到一个值，这个值就是数据//存放的位置，我们就可以根据这个值快速的找到我们想要的数据
//吴磊———-(散列函数/哈希函数)———>吴
//键值对：key-value通过对key的哈希化得到一个下标，如果出现相同的下标就要进行冲突处理
JS实现常见数据结构与算法 - 图1

  1. //哈希函数
  2.     function hashFunc(str, size) {
  3.         var hashCode = 0;
  4.         for(var i = 0; i < str.length; i++) {
  5.             hashCode = 37 * hashCode + str.charCodeAt(i);
  6.         }
  7.         var index = hashCode % size;
  8.         return index;
  9.     }
  1. //哈希表
  2.     function HashTable() {
  3.         this.storage = [];
  4.         this.count = 0;
  5.         this.limit = 7;
  6.         HashTable.prototype.hashFunc = function(str, size) {
  7.             var hashCode = 0;
  8.             for(var i = 0; i < str.length; i++) {
  9.                 hashCode = 37 * hashCode + str.charCodeAt(i);
  10.             }
  11.             var index = hashCode % size;
  12.             return index;
  13.         }
  14.         HashTable.prototype.put = function(key, value) {
  15.             var index = this.hashFunc(key, this.limit);
  16.             var bucket = this.storage[index];
  17.             if(bucket == null) {
  18.                 bucket = [];
  19.                 this.storage[index] = bucket;
  20.             }
  21.             for(var i = 0; i < bucket.length; i++) {
  22.                 var tuple = bucket[i];
  23.                 if(tuple[0] == key) {
  24.                     tuple[1] = value;
  25.                     return true;
  26.                 }
  27.             }
  28.             bucket.push([key, value]);
  29.             this.count += 1;
  30.         }
  31.         HashTable.prototype.get = function(key) {
  32.             var index = this.hashFunc(key, this.limit);
  33.             var bucket = this.storage[index];
  34.             if(bucket == null) {
  35.                 return null;
  36.             }
  37.             for(var i = 0; i < bucket.length; i++) {
  38.                 var tuple = bucket[i];
  39.                 if(tuple[0] == key) {
  40.                     return tuple[1];
  41.                 }
  42.             }
  43.             return null;
  44.         }
  45.         HashTable.prototype.remove = function(key) {
  46.             var index = this.hashFunc(key, this.limit);
  47.             var bucket = this.storage[index];
  48.             if(bucket == null) {
  49.                 return null;
  50.             }
  51.             for(var i = 0; i < bucket.length; i++) {
  52.                 var tuple = bucket[i];
  53.                 if(tuple[0] == key) {
  54.                     bucket.splice(i, 1);
  55.                     this.count -= 1;
  56.                     return tuple[1];
  57.                 }
  58.             }
  59.             return null;
  60.         }
  61.         //扩容,装填因子大于0.75,所有数据同时进行修改
  62.         HashTable.prototype.resize = function(newLimit) {
  63.             var oldStorage = this.storage;
  64.             this.storage = [];
  65.             this.count = 0;
  66.             this.limit = newLimit;
  67.             for(var i = 0; i < oldStorage.length; i++) {
  68.                 var bucket = oldStorage[i];
  69.                 if(bucket == null) {
  70.                     continue;
  71.                 }
  72.                 for(var j = 0; j < bucket.length; j++) {
  73.                     var tuple = bucket[j];
  74.                     this.put(tuple[0], tuple[1]);
  75.                 }
  76.             }
  77.         }
  78.         //添加操作之后:
  79.         if(this.count > this.limit * 0.75) {
  80.             this.resize(this.limit * 1);
  81.         }
  82.         //删除操作之后:
  83.         if(this.limit > 7 && this.count < this.limit * 0.25) {
  84.             this.resize(Math.floor(this.limit / 2));
  85.         }
  86.         //质数判断
  87.         function isPrime(num) {
  88.             var temp = parseInt(Math.sqrt(num));
  89.             for(var i = 2; i <= temp; i++) {
  90.                 if(num % i == 0) {
  91.                     return false;
  92.                 }
  93.             }
  94.             return true;
  95.         }
  96.         //实现容量恒为质数
  97.         HashTable.prototype.getPrime = function(num) {
  98.             while(!this.isPrime(num)) {
  99.                 num += 1;
  100.             }
  101.             return num;
  102.         }
  103.     }

八、树

//1.二叉树:几乎所有的树都可以表示成二叉树的形式
//2.完全二叉树:只有叶节点不是满的,且优先为左侧节点
//3.二叉搜索树(BST):
//非空左子树的所有键值小于根节点的键值
//非空右子树的所有键值大于根节点的键值
//左右子树本身也是二叉搜索树
//利用了二分查找的思想,查找所需的最大次数为BST的深度

  1. function BinarySearchTree() {
  2.     function Node(key) {
  3.       this.key = key;
  4.     this.left = null;
  5.     this.right = null;
  6.   }
  7.   this.root = null;
  9.   BinarySearchTree.prototype.insert = function(key) {
  10.       let newNode = new Node(key);
  11.     if(this.root == null) {
  12.         this.root = newNode;
  13.     }else{
  14.         this.insertNode(this.root, newNode);
  15.     }
  16.   }
  18.   BinarySearchTree.prototype.insertNode = function(node, newNode) {
  19.       if(newNode.Key < node.key) {
  20.         if(node.left == null) {
  21.           node.left = newNode;
  22.       }else{
  23.           this.insertNode(node.left, newNode);
  24.       }
  25.     }else{
  26.         if(node.right == null) {
  27.           node.right = newNode;
  28.       }else{
  29.           this.insertNode(node.right, newNode);
  30.       }
  31.     }
  32.   }
  33. }
  1. //先序遍历:先访问根节点,然后左右子树
  2. //递归版
  3. BinarySearchTree.prototype.preOrderTraversal = function(handler) {
  4.     this.preOrderTraversalNode(this.root, handler);
  5. }
  6. BinarySearchTree.prototype.preOrderTraversalNode = function(node, handler) {
  7.   if(node != null) {
  8.       handler(node.key);
  9.     this.preOrderTraversalNode(node.left, handler);
  10.     this.preOrderTraversalNode(node.right, handler);
  11.    }
  12. }
  13. //使用
  14. var bst = new BinarySearchTree();
  15. var resultString = "";
  16. bst.preOrderTraversal(function(key){
  17.     resultString += key + "";
  18. })
  19. alert(resultString);
  1. //中序遍历:根节点第二次访问
  2. //递归版
  3. BinarySearchTree.prototype.inOrderTraversal = function(handler) {
  4.   this.inOrderTraversalNode(this.root, handler);
  5. }
  6. BinarySearchTree.prototype.inOrderTraversalNode = function(node, handler) {
  7.   if(node != null) {
  8.       this.inOrderTraversalNode(node.left, handler);
  9.     handler(node.key);
  10.     this.inOrderTraversalNode(node.right, handler);
  11.    }
  12. }
  1. //后序遍历:先访问左右子树,最后访问根节点
  2. //递归版
  3. BinarySearchTree.prototype.postOrderTraversal = function(handler) {
  4.     this.postOrderTraversalNode(this.root, handler);
  5. }
  7. BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler) {
  8.     if(node != null) {
  9.       this.postOrderTraversalNode(node.left, handler);
  10.     this.postOrderTraversalNode(node.right, handler);
  11.     handler(node.key);
  12.   }
  13. }
  1. //非空左子树的所有键值小于根节点的键值
  2. //非空右子树的所有键值大于根节点的键值
  3. //所以最小值就是最左边的值
  4. BinarySearchTree.prototype.min = function() {
  5.     let node = this.root;
  6.   while(node.left !== null) {
  7.       node = node.left;
  8.   }
  9.   return node.key;
  10. }
  12. //最大值也就是最右边的值
  13. BinarySearchTree.prototype.max = function() {
  14.     let node = this.root;
  15.   while(node.right != null) {
  16.       node = node.right;
  17.   }
  18.   return  node.key;
  19. }
  21. BinarySearchTree.prototype.search = function(key) {
  22.     return this.searchNode(this.root, key);
  23. }
  25. BinarySearchTree.prototype.searchNode = function(node, key) {
  26.     if(node == null) {
  27.       return false;
  28.   }
  29.   if(node.key > key) {
  30.       return this.searchNode(node.left, key);
  31.   }else if(node.key < key) {
  32.       return this.searchNode(node.right, key);
  33.   }else{
  34.       return true;
  35.   } 
  36. }
  1.  <br />        //删除节点:<br />        //1.找到节点<br />        //2.删除节点<br />        //叶节点:父节点的left/right为null<br />        //一个子节点:父节点指向子节点<br />        //两个子节点:右子树的最小节点去更新这个节点,将原点删除,最后返回新的引用(前驱/后继)
  1. BinarySearchTree.prototype.remove = function(key) {
  2.             var current = this.root;
  3.             var parent = null;
  4.             var isLeftChild = true;
  5.             while(current.key != key) {
  6.                 parent = current;
  7.                 if(key < current.key) {
  8.                     isLeftChild = true;
  9.                     current = current.left;
  10.                 }else{
  11.                     isLeftChild = false;
  12.                     current = current.right;
  13.                 }
  14.                 if(current == null) {
  15.                     return false;
  16.                 }
  17.             }
  1. // 3.删除的结点是叶结点
  2.             if (current.left === null && current.right === null) {
  3.                 if (current == this.root) {
  4.                     this.root == null
  5.                 } else if (isLeftChild) {
  6.                     parent.left = null
  7.                 } else {
  8.                     parent.right = null
  9.                 }
  10.             }
  11.             // 4.删除有一个子节点的节点
  12.             else if (current.right === null) {
  13.                 if (current == this.root) {
  14.                     this.root = current.left
  15.                 } else if (isLeftChild) {
  16.                     parent.left = current.left
  17.                 } else {
  18.                     parent.right = current.left
  19.                 }
  20.             } else if (current.left === null) {
  21.                 if (current == this.root) {
  22.                     this.root = current.right
  23.                 } else if (isLeftChild) {
  24.                     parent.left = current.right
  25.                 } else {
  26.                     parent.right = current.right
  27.                 }
  28.             }
  1. // 5.删除有两个节点的节点
  2.             else {
  3.                 // 1.获取后继节点
  4.                 var successor = this.getSuccessor(current)
  5.                 // 2.判断是否是根节点
  6.                 if (current == this.root) {
  7.                     this.root = successor
  8.                 } else if (isLeftChild) {
  9.                     parent.left = successor
  10.                 } else {
  11.                     parent.right = successor
  12.                 }
  13.                 // 3.将删除节点的左子树赋值给successor
  14.                 successor.left = current.left
  15.             }
  16.             return true
  17.         }
  18.         // 找后继的方法
  19.         BinarySerachTree.prototype.getSuccessor = function (delNode) {
  20.             // 1.使用变量保存临时的节点
  21.             var successorParent = delNode
  22.             var successor = delNode
  23.             var current = delNode.right // 要从右子树开始找
  24.             // 2.寻找节点
  25.             while (current != null) {
  26.                 successorParent = successor
  27.                 successor = current
  28.                 current = current.left
  29.             }
  30.             // 3.如果是删除图中15的情况, 还需要如下代码
  31.             if (successor != delNode.right) {
  32.                 successorParent.left = successorParent.right
  33.                 successor.right = delNode.right
  34.             }
  35.             return successor;
  36.         }
  37.     }

九、堆

满足以下两个条件就是堆

  • 堆是完全二叉树
  • 堆的节点值必须大于等于或小于等于子节点的值

堆其实可以用一个数组表示，给定一个节点的下标 i （i从1开始） ，那么它的父节点一定为 A[i/2] ，左子节点为 A[2i] ，右子节点为 A[2i+1]

  1. //插入式建堆
  2. //总是先加入到尾部，然后和父节点i/2进行比较，大或者小就进行交换
  3. function insert(key) {
  4.     items.push(key)
  5.     // 获取存储位置
  6.     let i = items.length-1 
  7.     while (i/2 > 0 && items[i] > items[i/2]) {  
  8.         swap(items, i, i/2); // 交换 
  9.         i = i/2; 
  10.     }
  11. }  
  12. function swap(items, i, j) {
  13.     let temp = items[i]
  14.     items[i] = items[j]
  15.     items[j] = temp
  16. }

十、图

// 1.一个图G=(V,E)
// V:一组顶点
// E:一组边,连接V中的顶点
// 2.由一条边连接在一起的顶点称为相邻顶点
// 一个顶点的度是其相邻顶点的数量
// 路径是顶点的一个连续序列
// 简单路径要求不包含重复的顶点
// 环也是一个简单路径
// 无环:无环的 连通的:每两个顶点间都存在路径
// 3.有向图/无向图
// 图可以是无向的或是有向的,双向上都存在路径则是强连通的
// 4.图的表示
// 6.图的遍历
// 两种算法:广度优先搜索/深度优先搜索
// 可以寻找特定的点或寻找两个顶点之间的路径,检查图是否连通,检查图是否含有环
// 思想:必须追踪每个第一次访问的节点,并且追踪有哪些节点还没有被完全探索,需要指定第一个被访问的节点
// 完全搜索一个顶点要求我们查看该顶点的每一条边,对于连接的未被访问的标注被发现,加入待访问顶点列表
// 为了保证算法的效率,务必访问每个顶点至多两次,连通图中每条边和顶点都会被访问到
// 1.广度优先搜索:队列 存入队列,最先入队的顶点先被探索
// 先宽后深的访问顶点
// 1.创建一个队列Q
// 2.标注v为被发现的,并将v入队列Q
// 3.如果Q非空,则运行以下的步骤
// 1.将u从Q出队列
// 2.标注u被发现
// 3.将u所有未被访问过的邻点入队列
// 4.标注u为已被探索的
// 2.深度优先搜索:栈 存入栈,沿路径被探索,存在新的相邻顶点就去访问
// 先深后广的访问顶点
// 1.标注v为被发现的
// 2.对于v的所有未访问的邻点w,访问顶点w
// 3.标注v为已被探索的
function Graph() {
// 属性
this.vertex = []; // 存储顶点
this.edges = new Dictionay(); // 存储边

  1. // 添加方法<br />    _Graph_.prototype.addVertex = function (_v_) {<br />        _this_.vertex.push(v);<br />        _this_.edges.set(v, []);<br />    }
  3. _Graph_.prototype.addEdge = function (_v_, _w_) {<br />        _this_.edges.get(v).push(w);<br />        _this_.edges.get(w).push(v);<br />    }
  5. _Graph_.prototype.toString = function () {<br />        var resultStr = ""<br />        for (var i = 0; i < _this_.vertex.length; i++) {<br />            resultStr += _this_.vertex[i] + "->"<br />            var edg = _this_.edges.get(_this_.vertex[i])<br />            for (var j = 0; j < edg.length; j++) {<br />                resultStr += edg[j] + " "<br />            }<br />            resultStr += "\n"<br />        }<br />        return resultStr<br />    }
  7. // 初始化颜色<br />    _Graph_.prototype.initColor = function () {<br />        var colors = [];<br />        for (var i = 0; i < _this_.vertex.length; i++) {<br />            colors[_this_.vertex[i]] = "white";<br />        }<br />        return colors;<br />    }
  9. // 广度优先算法<br />    _Graph_.prototype.bfs = function (_v_, _handler_) {<br />        // 1.初始化颜色<br />        var color = _this_.initColor();<br />        // 2.创建队列<br />        var queue = **new** _Queue_();<br />        // 3.将传入的顶点放入队列中<br />        queue.enqueue(v);<br />        // 4.从队列中依次取出和放入数据<br />        while (!queue.isEmpty()) {<br />            // 4.1.从队列中取出数据<br />            var qv = queue.dequeue();<br />            // 4.2.获取qv相邻的所有顶点<br />            var qEdg = _this_.edgs.get(qv);<br />            // 4.3.将qv的颜色设置成灰色<br />            color[qv] = "gray";<br />            // 4.4.将qAdj的所有顶点依次压入队列中<br />            for (var i = 0; i < qEdg.length; i++) {<br />                var a = qEdg[i];<br />                if (color[a] === "white") {<br />                    color[a] = "gray";<br />                    queue.enqueue(a);<br />                }<br />            }<br />            // 4.5.因为qv已经探测完毕, 将qv设置成黑色<br />            color[qv] = "black";<br />            // 4.6.处理qv<br />            if (handler) {<br />                handler(qv);<br />            }<br />        }<br />    }
  11. // 深度优先搜索<br />    _Graph_.prototype.dfs = function (_handler_) {<br />        // 1.初始化颜色<br />        var color = _this_.initColor();<br />        // 2.遍历所有的顶点, 开始访问<br />        for (var i = 0; i < _this_.vertex.length; i++) {<br />            if (color[_this_.vertex[i]] === "white") {<br />                _this_.dfsVisit(_this_.vertex[i], color, handler);<br />            }<br />        }<br />    }
  13. // dfs的递归调用方法<br />    _Graph_.prototype.dfsVisit = function (_u_, _color_, _handler_) {<br />        // 1.将u的颜色设置为灰色<br />        color[u] = "gray";<br />        // 2.处理u顶点<br />        if (handler) {<br />            handler(u)<br />        }<br />        // 3.u的所有邻接顶点的访问<br />        var uEdg = _this_.edgs.get(u)<br />        for (var i = 0; i < uEdg.length; i++) {<br />            var w = uEdg[i]<br />            if (color[w] === "white") {<br />                _this_.dfsVisit(w, color, handler)<br />            }<br />        }<br />        // 4.将u设置为黑色<br />        color[u] = "black"<br />    }<br />}<br />//##排序和搜索算法<br />//5.快排<br />    //1.首先,在数组中选择一个值作为主元,也就是数组中间的那个值<br />    //2.创建两个指针引用,左边一个指向数组的第一个值,右边一个指向数组的最后一个值<br />    //移动左指针找到一个比主元大的值,移动右指针找到一个比主元小的值,然后交换<br />    //重复这个过程,直到左指针超过右指针,这一步叫做划分操作<br />    //3.接着对划分后的小数组重复之前的步骤,最后数组完全排序<br />    // 算法复杂度:O(nlog(n))<br />// 封装ArrayList<br />function ArrayList() {<br />    _this_.array = []
  15. _ArrayList_.prototype.insert = function (_item_) {<br />        _this_.array.push(item)<br />    }
  17. _ArrayList_.prototype.toString = function () {<br />        return _this_.array.join()<br />    }
  19. _ArrayList_.prototype.bubbleSort = function () {<br />        // 1.获取数组的长度<br />        var length = _this_.array.length
  21.     // 2.反向循环, 因此次数越来越少<br />        for (var i = length - 1; i >= 0; i--) {<br />            // 3.根据i的次数, 比较循环到i位置<br />            for (var j = 0; j < i; j++) {<br />                // 4.如果j位置比j+1位置的数据大, 那么就交换<br />                if (_this_.array[j] > _this_.array[j+1]) {<br />                    // 交换<br />                    _this_.swap(j, j+1)<br />                }<br />            }<br />        }<br />    }
  23. _ArrayList_.prototype.selectionSort = function () {<br />        // 1.获取数组的长度<br />        var length = _this_.array.length
  25.     // 2.外层循环: 从0位置开始取出数据, 直到length-2位置<br />        for (var i = 0; i < length - 1; i++) {<br />            // 3.内层循环: 从i+1位置开始, 和后面的内容比较<br />            var min = i<br />            for (var j = min + 1; j < length; j++) {<br />                // 4.如果i位置的数据大于j位置的数据, 记录最小的位置<br />                if (_this_.array[min] > _this_.array[j]) {<br />                    min = j<br />                }<br />            }<br />            _this_.swap(min, i)<br />        }<br />    }
  27. _ArrayList_.prototype.insertionSort = function () {<br />        // 1.获取数组的长度<br />        var length = _this_.array.length
  29.     // 2.外层循环: 外层循环是从1位置开始, 依次遍历到最后<br />        for (var i = 1; i < length; i++) {<br />            // 3.记录选出的元素, 放在变量temp中<br />            var j = i<br />            var temp = _this_.array[i]
  31.         // 4.内层循环: 内层循环不确定循环的次数, 最好使用while循环<br />            while (j > 0 && _this_.array[j-1] > temp) {<br />                _this_.array[j] = _this_.array[j-1]<br />                j--<br />            }
  33.         // 5.将选出的j位置, 放入temp元素<br />            _this_.array[j] = temp<br />        }<br />    }
  35. _ArrayList_.prototype.shellSort = function () {<br />        // 1.获取数组的长度<br />        var length = _this_.array.length
  37.     // 2.根据长度计算增量<br />        var gap = Math.floor(length / 2)
  39.     // 3.增量不断变量小, 大于0就继续排序<br />        while (gap > 0) {<br />            // 4.实现插入排序<br />            for (var i = gap; i < length; i++) {<br />                // 4.1.保存临时变量<br />                var j = i<br />                var temp = _this_.array[i]
  41.             // 4.2.插入排序的内存循环<br />                while (j > gap - 1 && _this_.array[j - gap] > temp) {<br />                    _this_.array[j] = _this_.array[j - gap]<br />                    j -= gap<br />                }
  43.             // 4.3.将选出的j位置设置为temp<br />                _this_.array[j] = temp<br />            }
  45.         // 5.重新计算新的间隔<br />            gap = Math.floor(gap / 2)<br />        }<br />    }
  47. ArrayList.prototype.swap = function (_m_, _n_) {<br />        var temp = _this_.array[_m_]<br />        _this_.array[_m_] = _this_.array[_n_]<br />        _this_.array[_n_] = temp<br />    }
  1. //快排
  2. ArrayList.prototype.quickSort = function(arr) {
  3.     if(arr.length <= 1) {
  4.       return arr
  5.   }
  6.   let pivotIndex = Math.floor(arr.length / 2)
  7.   let pivot = arr.splice(pivotIndex, 1)[0]
  8.   let left = []
  9.   let right = []
  10.   for(let i = 0;i < arr.length; i++) {
  11.       if(arr[i] < pivot) {
  12.         left.push(arr[i])
  13.     }else{
  14.         right.push(arr[i])
  15.     }
  16.   }
  17.   return quickSort(left).concat([piovt], quickSort(right))
  18. }