起航学习网

- 让每个人都能学到最前沿新知识、新技能!
起航学习网
当前位置: 起航学习网 > 短期培训 > Web前端 > 如何掌握数据机构和JavaScript技术

如何掌握数据机构和JavaScript技术

时间:2019-08-13 13:41:43来源:WEB前端网 作者:IT培训网 已有: 名学员访问该课程

  快捷搜索:JavaScript(46)

前言:Queue和Stack有一些类似,不同的是Stack是先进后出,而Queue是先进先出。Queue在生活中的例子比如排队上公交,排在第一个的总是最先上车;又比如打印机的打印队列,排在前面的最先打印。

常见数据结构和Javascript实现总结,在学习前端技术的路上,我们需要掌握的边缘知识很多,虽然这些前端相关知识不难,可想要精通也是不容易的,如js技术,虽然简单,却掌握非常难的,许多前端特效还是离不开JavaScript。所以学好这门技术还是非常有必要的。

做前端的同学不少都是自学成才或者半路出家,计算机基础的知识比较薄弱,尤其是数据结构和算法这块,所以今天整理了一下常见的数据结构和对应的Javascript的实现,希望能帮助大家完善这方面的知识体系。

1. Stack(栈)

如何掌握数据机构和JavaScript技术_www.epx365.cn

Stack的特点是后进先出(last in first out)。生活中常见的Stack的例子比如一摞书,你最后放上去的那本你之后会最先拿走;又比如浏览器的访问历史,当点击返回按钮,最后访问的网站最先从历史记录中弹出。

  1. Stack一般具备以下方法:
  2. push:将一个元素推入栈顶
  3. pop:移除栈顶元素,并返回被移除的元素
  4. peek:返回栈顶元素
  5. length:返回栈中元素的个数

Javascript的Array天生具备了Stack的特性,但我们也可以从头实现一个 Stack类:


  1. function Stack() { 
  2.   this.count = 0; 
  3.   this.storage = {}; 
  4.  
  5.   this.push = function (value) { 
  6.     this.storage[this.count] = value; 
  7.     this.count++; 
  8.   } 
  9.  
  10.   this.pop = function () { 
  11.     if (this.count === 0) { 
  12.       return undefined; 
  13.     } 
  14.     this.count--; 
  15.     var result = this.storage[this.count]; 
  16.     delete this.storage[this.count]; 
  17.     return result; 
  18.   } 
  19.  
  20.   this.peek = function () { 
  21.     return this.storage[this.count - 1]; 
  22.   } 
  23.  
  24.   this.size = function () { 
  25.     return this.count
  26.   } 

2. Queue(队列)

如何掌握数据机构和JavaScript技术_www.epx365.cn

Queue和Stack有一些类似,不同的是Stack是先进后出,而Queue是先进先出。Queue在生活中的例子比如排队上公交,排在第一个的总是最先上车;又比如打印机的打印队列,排在前面的最先打印。

  • Queue一般具有以下常见方法:
  • enqueue:入列,向队列尾部增加一个元素
  • dequeue:出列,移除队列头部的一个元素并返回被移除的元素
  • front:获取队列的第一个元素
  • isEmpty:判断队列是否为空
  • size:获取队列中元素的个数

Javascript中的Array已经具备了Queue的一些特性,所以我们可以借助Array实现一个Queue类型:


  1. function Queue() { 
  2.   var collection = []; 
  3.  
  4.   this.print = function () { 
  5.     console.log(collection); 
  6.   } 
  7.  
  8.   this.enqueue = function (element) { 
  9.     collection.push(element); 
  10.   } 
  11.  
  12.   this.dequeue = function () { 
  13.     return collection.shift(); 
  14.   } 
  15.  
  16.   this.front = function () { 
  17.     return collection[0]; 
  18.   } 
  19.  
  20.   this.isEmpty = function () { 
  21.     return collection.length === 0; 
  22.   } 
  23.  
  24.   this.size = function () { 
  25.     return collection.length; 
  26.   } 

Priority Queue(优先队列)

Queue还有个升级版本,给每个元素赋予优先级,优先级高的元素入列时将排到低优先级元素之前。区别主要是enqueue方法的实现:


  1. function PriorityQueue() { 
  2.  
  3.   ... 
  4.  
  5.   this.enqueue = function (element) { 
  6.     if (this.isEmpty()) { 
  7.       collection.push(element); 
  8.     } else { 
  9.       var added = false
  10.       for (var i = 0; i < collection.length; i++) { 
  11.         if (element[1] < collection[i][1]) { 
  12.           collection.splice(i, 0, element); 
  13.           added = true
  14.           break; 
  15.         } 
  16.       } 
  17.       if (!added) { 
  18.         collection.push(element); 
  19.       } 
  20.     } 
  21.   } 

测试一下:


  1. var pQ = new PriorityQueue(); 
  2.  
  3. pQ.enqueue(['gannicus', 3]); 
  4. pQ.enqueue(['spartacus', 1]); 
  5. pQ.enqueue(['crixus', 2]); 
  6. pQ.enqueue(['oenomaus', 4]); 
  7.  
  8. pQ.print(); 

结果:


  1.   [ 'spartacus', 1 ], 
  2.   [ 'crixus', 2 ], 
  3.   [ 'gannicus', 3 ], 
  4.   [ 'oenomaus', 4 ] 

3. Linked List(链表)

如何掌握数据机构和JavaScript技术_www.epx365.cn

顾名思义,链表是一种链式数据结构,链上的每个节点包含两种信息:节点本身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构,存储的都是一个序列的数据,但也有很多区别,如下表:

如何掌握数据机构和JavaScript技术_www.epx365.cn

一个单向链表通常具有以下方法:

  1. size:返回链表中节点的个数
  2. head:返回链表中的头部元素
  3. add:向链表尾部增加一个节点
  4. remove:删除某个节点
  5. indexOf:返回某个节点的index
  6. elementAt:返回某个index处的节点
  7. addAt:在某个index处插入一个节点
  8. removeAt:删除某个index处的节点

单向链表的Javascript实现:


  1. /** 
  2.  * 链表中的节点  
  3.  */ 
  4. function Node(element) { 
  5.   // 节点中的数据 
  6.   this.element = element; 
  7.   // 指向下一个节点的指针 
  8.   this.next = null
  9.  
  10. function LinkedList() { 
  11.   var length = 0; 
  12.   var head = null
  13.  
  14.   this.size = function () { 
  15.     return length; 
  16.   } 
  17.  
  18.   this.head = function () { 
  19.     return head; 
  20.   } 
  21.  
  22.   this.add = function (element) { 
  23.     var node = new Node(element); 
  24.     if (head == null) { 
  25.       head = node; 
  26.     } else { 
  27.       var currentNode = head; 
  28.  
  29.       while (currentNode.next) { 
  30.         currentNode = currentNode.next
  31.       } 
  32.  
  33.       currentNode.next = node; 
  34.     } 
  35.     length++; 
  36.   } 
  37.  
  38.   this.remove = function (element) { 
  39.     var currentNode = head; 
  40.     var previousNode; 
  41.     if (currentNode.element === element) { 
  42.       head = currentNode.next
  43.     } else { 
  44.       while (currentNode.element !== element) { 
  45.         previousNode = currentNode; 
  46.         currentNode = currentNode.next
  47.       } 
  48.       previousNode.next = currentNode.next
  49.     } 
  50.     length--; 
  51.   } 
  52.  
  53.   this.isEmpty = function () { 
  54.     return length === 0; 
  55.   } 
  56.  
  57.   this.indexOf = function (element) { 
  58.     var currentNode = head; 
  59.     var index = -1; 
  60.     while (currentNode) { 
  61.       index++; 
  62.       if (currentNode.element === element) { 
  63.         return index
  64.       } 
  65.       currentNode = currentNode.next
  66.     } 
  67.  
  68.     return -1; 
  69.   } 
  70.  
  71.   this.elementAt = function (index) { 
  72.     var currentNode = head; 
  73.     var count = 0; 
  74.     while (count < index) { 
  75.       count++; 
  76.       currentNode = currentNode.next
  77.     } 
  78.     return currentNode.element; 
  79.   } 
  80.  
  81.   this.addAt = function (index, element) { 
  82.     var node = new Node(element); 
  83.     var currentNode = head; 
  84.     var previousNode; 
  85.     var currentIndex = 0; 
  86.  
  87.     if (index > length) { 
  88.       return false
  89.     } 
  90.  
  91.     if (index === 0) { 
  92.       node.next = currentNode; 
  93.       head = node; 
  94.     } else { 
  95.       while (currentIndex < index) { 
  96.         currentIndex++; 
  97.         previousNode = currentNode; 
  98.         currentNode = currentNode.next
  99.       } 
  100.       node.next = currentNode; 
  101.       previousNode.next = node; 
  102.     } 
  103.     length++; 
  104.   } 
  105.  
  106.   this.removeAt = function (index) { 
  107.     var currentNode = head; 
  108.     var previousNode; 
  109.     var currentIndex = 0; 
  110.     if (index < 0 || index >= length) { 
  111.       return null
  112.     } 
  113.     if (index === 0) { 
  114.       head = currentIndex.next
  115.     } else { 
  116.       while (currentIndex < index) { 
  117.         currentIndex++; 
  118.         previousNode = currentNode; 
  119.         currentNode = currentNode.next
  120.       } 
  121.       previousNode.next = currentNode.next
  122.     } 
  123.     length--; 
  124.     return currentNode.element; 
  125.   } 

4. Set(集合)

如何掌握数据机构和JavaScript技术_www.epx365.cn

集合是数学中的一个基本概念,表示具有某种特性的对象汇总成的集体。在ES6中也引入了集合类型Set,Set和Array有一定程度的相似,不同的是Set中不允许出现重复的元素而且是无序的。

一个典型的Set应该具有以下方法:

  1. values:返回集合中的所有元素
  2. size:返回集合中元素的个数
  3. has:判断集合中是否存在某个元素
  4. add:向集合中添加元素
  5. remove:从集合中移除某个元素
  6. union:返回两个集合的并集
  7. intersection:返回两个集合的交集
  8. difference:返回两个集合的差集
  9. subset:判断一个集合是否为另一个集合的子集

使用Javascript可以将Set进行如下实现,为了区别于ES6中的Set命名为MySet:


  1. function MySet() { 
  2.   var collection = []; 
  3.   this.has = function (element) { 
  4.     return (collection.indexOf(element) !== -1); 
  5.   } 
  6.  
  7.   this.values = function () { 
  8.     return collection; 
  9.   } 
  10.  
  11.   this.size = function () { 
  12.     return collection.length; 
  13.   } 
  14.  
  15.   this.add = function (element) { 
  16.     if (!this.has(element)) { 
  17.       collection.push(element); 
  18.       return true
  19.     } 
  20.     return false
  21.   } 
  22.  
  23.   this.remove = function (element) { 
  24.     if (this.has(element)) { 
  25.       index = collection.indexOf(element); 
  26.       collection.splice(index, 1); 
  27.       return true
  28.     } 
  29.     return false
  30.   } 
  31.  
  32.   this.union = function (otherSet) { 
  33.     var unionSet = new MySet(); 
  34.     var firstSet = this.values(); 
  35.     var secondSet = otherSet.values(); 
  36.     firstSet.forEach(function (e) { 
  37.       unionSet.add(e); 
  38.     }); 
  39.     secondSet.forEach(function (e) { 
  40.       unionSet.add(e); 
  41.     }); 
  42.     return unionSet; 
  43.   } 
  44.  
  45.   this.intersection = function (otherSet) { 
  46.     var intersectionSet = new MySet(); 
  47.     var firstSet = this.values(); 
  48.     firstSet.forEach(function (e) { 
  49.       if (otherSet.has(e)) { 
  50.         intersectionSet.add(e); 
  51.       } 
  52.     }); 
  53.     return intersectionSet; 
  54.   } 
  55.  
  56.   this.difference = function (otherSet) { 
  57.     var differenceSet = new MySet(); 
  58.     var firstSet = this.values(); 
  59.     firstSet.forEach(function (e) { 
  60.       if (!otherSet.has(e)) { 
  61.         differenceSet.add(e); 
  62.       } 
  63.     }); 
  64.     return differenceSet; 
  65.   } 
  66.  
  67.   this.subset = function (otherSet) { 
  68.     var firstSet = this.values(); 
  69.     return firstSet.every(function (value) { 
  70.       return otherSet.has(value); 
  71.     }); 
  72.   } 

5. Hash Table(哈希表/散列表)

如何掌握数据机构和JavaScript技术_www.epx365.cn

Hash Table是一种用于存储键值对(key value pair)的数据结构,因为Hash Table根据key查询value的速度很快,所以它常用于实现Map、Dictinary、Object等数据结构。如上图所示,Hash Table内部使用一个hash函数将传入的键转换成一串数字,而这串数字将作为键值对实际的key,通过这个key查询对应的value非常快,时间复杂度将达到O(1)。Hash函数要求相同输入对应的输出必须相等,而不同输入对应的输出必须不等,相当于对每对数据打上唯一的指纹。

一个Hash Table通常具有下列方法:

  1. add:增加一组键值对
  2. remove:删除一组键值对
  3. lookup:查找一个键对应的值

一个简易版本的Hash Table的Javascript实现:


  1. function hash(string, max) { 
  2.   var hash = 0; 
  3.   for (var i = 0; i < string.length; i++) { 
  4.     hash += string.charCodeAt(i); 
  5.   } 
  6.   return hash % max
  7.  
  8. function HashTable() { 
  9.   let storage = []; 
  10.   const storageLimit = 4; 
  11.  
  12.   this.add = function (key, value) { 
  13.     var index = hash(key, storageLimit); 
  14.     if (storage[index] === undefined) { 
  15.       storage[index] = [ 
  16.         [key, value] 
  17.       ]; 
  18.     } else { 
  19.       var inserted = false
  20.       for (var i = 0; i < storage[index].length; i++) { 
  21.         if (storage[index][i][0] === key) { 
  22.           storage[index][i][1] = value; 
  23.           inserted = true
  24.         } 
  25.       } 
  26.       if (inserted === false) { 
  27.         storage[index].push([key, value]); 
  28.       } 
  29.     } 
  30.   } 
  31.  
  32.   this.remove = function (key) { 
  33.     var index = hash(key, storageLimit); 
  34.     if (storage[index].length === 1 && storage[index][0][0] === key) { 
  35.       delete storage[index]; 
  36.     } else { 
  37.       for (var i = 0; i < storage[index]; i++) { 
  38.         if (storage[index][i][0] === key) { 
  39.           delete storage[index][i]; 
  40.         } 
  41.       } 
  42.     } 
  43.   } 
  44.  
  45.   this.lookup = function (key) { 
  46.     var index = hash(key, storageLimit); 
  47.     if (storage[index] === undefined) { 
  48.       return undefined; 
  49.     } else { 
  50.       for (var i = 0; i < storage[index].length; i++) { 
  51.         if (storage[index][i][0] === key) { 
  52.           return storage[index][i][1]; 
  53.         } 
  54.       } 
  55.     } 
  56.   } 

6. Tree(树)

如何掌握数据机构和JavaScript技术_www.epx365.cn

顾名思义,Tree的数据结构和自然界中的树极其相似,有根、树枝、叶子,如上图所示。Tree是一种多层数据结构,与Array、Stack、Queue相比是一种非线性的数据结构,在进行插入和搜索操作时很高效。在描述一个Tree时经常会用到下列概念:

  1. Root(根):代表树的根节点,根节点没有父节点
  2. Parent Node(父节点):一个节点的直接上级节点,只有一个
  3. Child Node(子节点):一个节点的直接下级节点,可能有多个
  4. Siblings(兄弟节点):具有相同父节点的节点
  5. Leaf(叶节点):没有子节点的节点
  6. Edge(边):两个节点之间的连接线
  7. Path(路径):从源节点到目标节点的连续边
  8. Height of Node(节点的高度):表示节点与叶节点之间的最长路径上边的个数
  9. Height of Tree(树的高度):即根节点的高度
  10. Depth of Node(节点的深度):表示从根节点到该节点的边的个数
  11. Degree of Node(节点的度):表示子节点的个数

我们以二叉查找树为例,展示树在Javascript中的实现。在二叉查找树中,即每个节点最多只有两个子节点,而左侧子节点小于当前节点,而右侧子节点大于当前节点,如图所示:

如何掌握数据机构和JavaScript技术_www.epx365.cn

一个二叉查找树应该具有以下常用方法:

  1. add:向树中插入一个节点
  2. findMin:查找树中最小的节点
  3. findMax:查找树中最大的节点
  4. find:查找树中的某个节点
  5. isPresent:判断某个节点在树中是否存在
  6. remove:移除树中的某个节点

以下是二叉查找树的Javascript实现:


  1. class Node { 
  2.   constructor(data, left = nullright = null) { 
  3.     this.data = data; 
  4.     this.left = left
  5.     this.right = right
  6.   } 
  7.  
  8. class BST { 
  9.   constructor() { 
  10.     this.root = null
  11.   } 
  12.  
  13.   add(data) { 
  14.     const node = this.root; 
  15.     if (node === null) { 
  16.       this.root = new Node(data); 
  17.       return
  18.     } else { 
  19.       const searchTree = function (node) { 
  20.         if (data < node.data) { 
  21.           if (node.left === null) { 
  22.             node.left = new Node(data); 
  23.             return
  24.           } else if (node.left !== null) { 
  25.             return searchTree(node.left); 
  26.           } 
  27.         } else if (data > node.data) { 
  28.           if (node.right === null) { 
  29.             node.right = new Node(data); 
  30.             return
  31.           } else if (node.right !== null) { 
  32.             return searchTree(node.right); 
  33.           } 
  34.         } else { 
  35.           return null
  36.         } 
  37.       }; 
  38.       return searchTree(node); 
  39.     } 
  40.   } 
  41.  
  42.   findMin() { 
  43.     let current = this.root; 
  44.     while (current.left !== null) { 
  45.       current = current.left
  46.     } 
  47.     return current.data; 
  48.   } 
  49.  
  50.   findMax() { 
  51.     let current = this.root; 
  52.     while (current.right !== null) { 
  53.       current = current.right
  54.     } 
  55.     return current.data; 
  56.   } 
  57.  
  58.   find(data) { 
  59.     let current = this.root; 
  60.     while (current.data !== data) { 
  61.       if (data < current.data) { 
  62.         current = current.left 
  63.       } else { 
  64.         current = current.right
  65.       } 
  66.       if (current === null) { 
  67.         return null
  68.       } 
  69.     } 
  70.     return current
  71.   } 
  72.  
  73.   isPresent(data) { 
  74.     let current = this.root; 
  75.     while (current) { 
  76.       if (data === current.data) { 
  77.         return true
  78.       } 
  79.       if (data < current.data) { 
  80.         current = current.left
  81.       } else { 
  82.         current = current.right
  83.       } 
  84.     } 
  85.     return false
  86.   } 
  87.  
  88.   remove(data) { 
  89.     const removeNode = function (node, data) { 
  90.       if (node == null) { 
  91.         return null
  92.       } 
  93.       if (data == node.data) { 
  94.         // node没有子节点 
  95.         if (node.left == null && node.right == null) { 
  96.           return null
  97.         } 
  98.         // node没有左侧子节点 
  99.         if (node.left == null) { 
  100.           return node.right
  101.         } 
  102.         // node没有右侧子节点 
  103.         if (node.right == null) { 
  104.           return node.left
  105.         } 
  106.         // node有两个子节点 
  107.         var tempNode = node.right
  108.         while (tempNode.left !== null) { 
  109.           tempNode = tempNode.left
  110.         } 
  111.         node.data = tempNode.data; 
  112.         node.right = removeNode(node.right, tempNode.data); 
  113.         return node; 
  114.       } else if (data < node.data) { 
  115.         node.left = removeNode(node.left, data); 
  116.         return node; 
  117.       } else { 
  118.         node.right = removeNode(node.right, data); 
  119.         return node; 
  120.       } 
  121.     } 
  122.     this.root = removeNode(this.root, data); 
  123.   } 

测试一下:


  1. const bst = new BST(); 
  2.  
  3. bst.add(4); 
  4. bst.add(2); 
  5. bst.add(6); 
  6. bst.add(1); 
  7. bst.add(3); 
  8. bst.add(5); 
  9. bst.add(7); 
  10. bst.remove(4); 
  11. console.log(bst.findMin()); 
  12. console.log(bst.findMax()); 
  13. bst.remove(7); 
  14. console.log(bst.findMax()); 
  15. console.log(bst.isPresent(4)); 

打印结果:


  1. false 

7. Trie(字典树,读音同try)

如何掌握数据机构和JavaScript技术_www.epx365.cn

Trie也可以叫做Prefix Tree(前缀树),也是一种搜索树。Trie分步骤存储数据,树中的每个节点代表一个步骤,trie常用于存储单词以便快速查找,比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母,跟着树的分支可以可以拼写出一个完整的单词,每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。

Trie一般有以下方法:

  • add:向字典树中增加一个单词
  • isWord:判断字典树中是否包含某个单词
  • print:返回字典树中的所有单词 

  1. /** 
  2.  * Trie的节点 
  3.  */ 
  4. function Node() { 
  5.   this.keys = new Map(); 
  6.   this.end = false
  7.   this.setEnd = function () { 
  8.     this.end = true
  9.   }; 
  10.   this.isEnd = function () { 
  11.     return this.end
  12.   } 
  13.  
  14. function Trie() { 
  15.   this.root = new Node(); 
  16.  
  17.   this.add = function (input, node = this.root) { 
  18.     if (input.length === 0) { 
  19.       node.setEnd(); 
  20.       return
  21.     } else if (!node.keys.has(input[0])) { 
  22.       node.keys.set(input[0], new Node()); 
  23.       return this.add(input.substr(1), node.keys.get(input[0])); 
  24.     } else { 
  25.       return this.add(input.substr(1), node.keys.get(input[0])); 
  26.     } 
  27.   } 
  28.  
  29.   this.isWord = function (word) { 
  30.     let node = this.root; 
  31.     while (word.length > 1) { 
  32.       if (!node.keys.has(word[0])) { 
  33.         return false
  34.       } else { 
  35.         node = node.keys.get(word[0]); 
  36.         word = word.substr(1); 
  37.       } 
  38.     } 
  39.     return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false
  40.   } 
  41.  
  42.   this.print = function () { 
  43.     let words = new Array(); 
  44.     let search = function (node = this.root, string) { 
  45.       if (node.keys.size != 0) { 
  46.         for (let letter of node.keys.keys()) { 
  47.           search(node.keys.get(letter), string.concat(letter)); 
  48.         } 
  49.         if (node.isEnd()) { 
  50.           words.push(string); 
  51.         } 
  52.       } else { 
  53.         string.length > 0 ? words.push(string) : undefined; 
  54.         return
  55.       } 
  56.     }; 
  57.     search(this.root, new String()); 
  58.     return words.length > 0 ? words : null
  59.   } 

8. Graph(图)

如何掌握数据机构和JavaScript技术_www.epx365.cn

Graph是节点(或顶点)以及它们之间的连接(或边)的集合。Graph也可以称为Network(网络)。根据节点之间的连接是否有方向又可以分为Directed Graph(有向图)和Undrected Graph(无向图)。Graph在实际生活中有很多用途,比如:导航软件计算最佳路径,社交软件进行好友推荐等等。

Graph通常有两种表达方式:

Adjaceny List(邻接列表):

如何掌握数据机构和JavaScript技术_www.epx365.cn

邻接列表可以表示为左侧是节点的列表,右侧列出它所连接的所有其他节点。

和 Adjacency Matrix(邻接矩阵):

如何掌握数据机构和JavaScript技术_www.epx365.cn

邻接矩阵用矩阵来表示节点之间的连接关系,每行或者每列表示一个节点,行和列的交叉处的数字表示节点之间的关系:0表示没用连接,1表示有连接,大于1表示不同的权重。

访问Graph中的节点需要使用遍历算法,遍历算法又分为广度优先和深度优先,主要用于确定目标节点和根节点之间的距离,

在Javascript中,Graph可以用一个矩阵(二维数组)表示,广度优先搜索算法可以实现如下:


  1. function bfs(graph, root) { 
  2.   var nodesLen = {}; 
  3.  
  4.   for (var i = 0; i < graph.length; i++) { 
  5.     nodesLen[i] = Infinity; 
  6.   } 
  7.  
  8.   nodesLen[root] = 0; 
  9.  
  10.   var queue = [root]; 
  11.   var current
  12.  
  13.   while (queue.length != 0) { 
  14.     current = queue.shift(); 
  15.  
  16.     var curConnected = graph[current]; 
  17.     var neighborIdx = []; 
  18.     var idx = curConnected.indexOf(1); 
  19.     while (idx != -1) { 
  20.       neighborIdx.push(idx); 
  21.       idx = curConnected.indexOf(1, idx + 1); 
  22.     } 
  23.  
  24.     for (var j = 0; j < neighborIdx.length; j++) { 
  25.       if (nodesLen[neighborIdx[j]] == Infinity) { 
  26.         nodesLen[neighborIdx[j]] = nodesLen[current] + 1; 
  27.         queue.push(neighborIdx[j]); 
  28.       } 
  29.     } 
  30.   } 
  31.  
  32.   return nodesLen; 

测试一下:


  1. var graph = [ 
  2.   [0, 1, 1, 1, 0], 
  3.   [0, 0, 1, 0, 0], 
  4.   [1, 1, 0, 0, 0], 
  5.   [0, 0, 0, 1, 0], 
  6.   [0, 1, 0, 0, 0] 
  7. ]; 
  8.  
  9. console.log(bfs(graph, 1)); 

打印:


  1.   0: 2, 
  2.   1: 0, 
  3.   2: 1, 
  4.   3: 3, 
  5.   4: Infinity 

最后,推荐大家使用Fundebug,一款很好用的BUG监控工具~

本文旨在向广大前端同学普及常见的数据结构,本人对这一领域也只是初窥门径,说的有差池的地方欢迎指出。也希望大家能打牢基础,在这条路上走的更高更远!

来源地址:http://www.epx365.cn/peixun/web/201953769.html

来源标题:如何掌握数据机构和JavaScript技术

 (责任编辑:IT培训网)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
培训学校
IT培训网 访问该机构站点 报名留言 加为好友 用户等级:注册会员 用户级别:10 机构名称:IT培训网 联 系 人:罗老师 联系电话: 联系手机:13783581536 在线客服:起航学习网客服 在 线 QQ:起航学习网客服 电子邮件:3158895217@qq.com 网站域名:http://www.cnitedu.cn 注册时间:2016-07-18 11:07 最后登录:2019-08-14 10:08