最新公告
  • 欢迎您光临起源地模板网，本站秉承服务宗旨 履行“站长”责任，销售只是起点 服务永无止境！立即加入钻石VIP
    • 10年
    专注帝国cms二次开发
    升级SVIP
    站长资源平台
    当前位置：站长学院 > 综合教程 > 前端常见数据结构总结

    前端常见数据结构总结

    正文概述 掘金(liangyue)   2021-05-03   615

    一、栈

    简介

    代码实现

    function Stack() {
    this.stack = []
    this.push = function(item) {
        stack.push(item)
    }
    this.pop = function() {
        stack.pop()
    }
}

    应用场景

    函数调用堆栈

    为了便于理解这个场景，先来看一段代码：

    function first() {
  console.log('first start')
  second()
  console.log('first end')
}

function second() {
  console.log('second start')
}

console.log('start')
first()
console.log('end')

// start
// first start
// second start
// first end
// end

    二、队列

    简介

    代码实现

    function Queue() {
  this.queue = []
  this.enqueue = function(item) {
    this.queue.push(item)
  }
  this.dequeue = function() {
    return this.queue.shift()
  }
}

    应用场景

    JS任务队列

    由于js是单线程的，所以在处理多个异步函数同时执行的情况下，当异步任务有了结果时，会先进入一个任务队列，在js主线程的同步任务执行完成后，才会读取任务队列，按照异步函数进入任务队列的顺序开始一次支持异步函数的回调函数，即先进入任务队列中的函数会先执行

    三、链表

    简介

    代码实现

    /**
 * 链表
 * @param {*} val
 */
function LinkList(val) {
  /**
   * 创建一个node结点
   * @param {*} val
   * @param node
   */
  function _creatNode(val) {
    return {
      val: val,
      next: null,
    }
  }

  this.head = _creatNode(val)
  this.tail = this.head

  /**
   * 查找
   * @param {*} val 查找val
   * @returns node
   */
  this.find = function (val) {
    let node = this.head
    while (node) {
      if (val === node.val) {
        return node
      }
      node = node.next
    }
    return null
  }

  /**
   * 在node结点后插入结点
   */
  this.insert = function (insertVal, val) {
    const insertNode = _creatNode(insertVal)
    if (val) {
      const node = this.find(val)
      insertNode.next = node.next
      node.next = insertNode
    } else {
      this.tail.next = insertNode
      this.tail = insertNode
    }
  }

  /**
   * 遍历
   * @param {Function} fn 回调函数
   */
  this.map = function (fn) {
    let p = this.head
    while (p) {
      fn(p)
      p = p.next
    }
  }
}

    应用场景

    1. 原型链

    在js中原型链的结构与链表结构非常类似。链表中我们使用next属性来链接下一个元素，而原型链则使用__proto__属性来链接原型对象

    四、集合

    简介

    代码实现

    // 由于es6中有专门的数据结构，可以直接创建一个集合
const set = new Set()

set.add(1)
set.add(2)
...

    应用场景

    1.数组去重

    通常我们在实际开发中使用Set这种数据结构最多的就是用来去重了，不过在数组去重时，要注意对于引用类型的数据，如果引用不同那么会按不同的值存在集合中，同时Set也可以存储NaN undefined这类的特殊数据

    2.数组判断、删除等操作

    比如在判断数组中是否存在某一个值，或者删除数组中某一个值时，也可以使用Set.prototype.has和Set.prototype.delete等方法方便的对数组进行操作

    五、字典

    简介

    代码实现

    const map = new Map()

    应用场景

    用来存储数据

    Map通常可以用来存储一些具有映射关系的数据，类似一个id对应一个内容，这种实现与js中普通对象的功能类似，但是Map的功能更加强大，Objet只能使用字符串、数字等简单类型当作键值，但是Map可以使用任意类型作为键，同时Map也可以直接获取长度；而且就是同样取值的操作，Map执行会比Object[key]这种方式更快。

    与其他类似数据结构区别

    与普通对象Object的区别

    1. 有序性：Map会按照原有的添加顺序存储，Object会根据key自动排序
    2. 可迭代：Map实现了迭代器，可以使用for...of方式进行遍历
    3. Map可直接获取长度
    4. Map的key可以是任何基本类型，Object只可以是字符串、数字、Symbol

    与集合Set的区别

    1. 存储：Set只能存储key不能存value，由于key不能重复，所以Set没有重复的key
    2. 展开：Map展开后每项格式为[key, value]

    六、树

    简介

    代码实现

    为了后面方便测试树的相关操作，我们先模拟一个树的数据结构：

    const treeData = {
  value: '1',
  children: [
    {
      value: '1-1',
      children: [
        {
          value: '1-1-1',
          children: []
        },
        {
          value: '1-1-2',
          children: [
            {
              value: '1-1-2-1',
              children: []
            }
          ]
        },
      ],
    },
    {
      value: '1-2',
      children: [
        {
          value: '1-2-1',
          children: [],
        },
      ],
    },
  ],
}

    深度优先遍历

    树的深度优先遍历即有children就继续遍历children，直到没有children后再遍历下一个结点: 深度优先遍历流程：

    1. 访问根结点
    2. 对根结点的children继续深度优先遍历
    function des(root) {
  console.log('value', root.value)
  root.children.forEach(item => {
    des(item)
  })
}

des(treeData)
// value 1
// value 1-1
// value 1-1-1
// value 1-1-2
// value 1-1-2-1
// value 1-2
// value 1-2-1

    可以看出其顺序为优先遍历children，知道children遍历结束开始下一个结点的深度遍历

    广度优先遍历

    广度优先遍历即优先遍历子结点，如果子结点遍历完成，则遍历各子结点的children： 广度优先遍历流程：

    1. 创建一个数组，将根结点作为第一项
    2. 将数组中第一项弹出并访问
    3. 将弹出项中的children遍历并依次添加至数组中
    4. 重复2、3步骤直到队列为空
    function bfs(root) {
  let arr = [root]

  while(tree = arr.shift()) {
    console.log('value', tree.value)
    tree.children.forEach(item => {
      arr.push(item)
    })
  }
}

bfs(treeData)
// value 1
// value 1-1
// value 1-2
// value 1-1-1
// value 1-1-2
// value 1-2-1
// value 1-1-2-1

    从输出结果可以看到树的遍历是按照优先遍历子结点，待子结点遍历后继续遍历子结点的子结点...直到arr数组为空表示遍历完成

    二叉树

    先模拟一个二叉树的数据结构:

    const binaryTreeData = {
  value: 'root',
  left: {
    value: 'left',
    left: {
      value: 'left-left',
      left: null,
      right: null,
    },
    right: {
      value: 'left-right',
      left: {
        value: 'left-right-left',
        left: null,
        right: null,
      },
      right: null,
    },
  },
  right: {
    value: 'right',
    left: {
      value: 'right-left',
      left: null,
      right: null,
    },
    right: {
      value: 'right-right',
      left: null,
      right: null,
    },
  },
}

    二叉树关系图：

    graph TD
root --> left
root --> right
left --> left-left
left --> left-right
left-right --> left-right-left
left-right --> null
right --> right-left
right --> right-right

    先序遍历

    根结点 -> 左子树先序遍历 -> 右子树先序遍历, 即：

    function preOrder(binaryTree) {
  if (!binaryTree) return
  console.log(binaryTree.value)
  preOrder(binaryTree.left)
  preOrder(binaryTree.right)
}

preOrder(binaryTreeData)
// root
// left
// left-left
// left-right
// left-right-left
// right
// right-left
// right-right

    中序遍历

    左子树中序遍历 -> 根结点 -> 右子树中序遍历，即：

    function inOrder(binaryTree) {
  if (!binaryTree) return
  inOrder(binaryTree.left)
  console.log(binaryTree.value)
  inOrder(binaryTree.right)
}

inOrder(binaryTreeData)
// left-left
// left
// left-right-left
// left-right
// root
// right-left
// right
// right-right

    后序遍历

    左子树后序遍历 -> 右子树后序遍历 -> 根结点，即：

    function postOrder(binaryTree) {
  if (!binaryTree) return
  postOrder(binaryTree.left)
  postOrder(binaryTree.right)
  console.log(binaryTree.value)
}

postOrder(binaryTreeData)
// left-left
// left-right-left
// left-right
// left
// right-left
// right-right
// right
// root

    应用场景

    domTree、vDom

    在浏览器中的dom结构和react、vue这类框架中的虚拟dom都应用到了树这个数据结构来表示页面元素之间的关系

    七、图

    简介

    图的表示法

    为了更直观的理解图的数据结构及其表示，我们先举一个例子，后面对图的其他操作都基于这个例子来测试：

    graph TD
A --> B --> D --> B
B --> C --> E --> A

    在这个图中我们可以很清晰的看出A、B、C、D、E这几个结点的相互关系，那么在javaScript中我们要如何表示这种关系：

    邻接矩阵

    ABCDE
    A01000B00110C00001D01000E10000

    邻街表

    {
    A: [B],
    B: [C, D],
    C: [E],
    D: [B],
    E: [A]
}

    图的遍历

    深度优先遍历

    深度优先遍历是从某一个顶点开始，对该顶点的未遍历相邻顶点依次进行深度优先遍历,即：

    // 记录遍历过的顶点
const visited = new Set()
function dfs(node) {
  console.log(node)
  visited.add(node)
  graph[node].forEach(childNode => {
    if (!visited.has(childNode)) {
      dfs(childNode)
    }
  })
}

dfs('A')
// A B C E D

    我们假设从A顶点开始进行深度优先遍历,那么输入结果为A B C E D,对比前面那张关系图可以看出深度优先遍历的顺序当遍历到C时，会继续遍历E之后才遍历到了D,符合深度优先遍历的规则。

    广度优先遍历

    图的广度优先遍历和树的广度优先遍历类似：

    1. 需要将根元素入队
    2. 再出队并访问
    3. 将未遍历的相邻结点依次入队
    4. 重复2、3步，直到队列为空, 即：
    const visited = new Set()
function bfs(node) {
  const queue = [node]
  // 根元素在遍历时要手动添加至已访问队列，后面只是添加了根元素的相邻结点
  visited.add(node)
  while(visitNode = queue.shift()) {
    console.log(visitNode)
    graph[visitNode].forEach(childNode => {
      if (!visited.has(childNode)) {
        visited.add(childNode)
        queue.push(childNode)
      }
    })
  }
}

bfs('A')
// A B C D E

    我们从A顶点进行广度优先遍历，当遍历到C结点时，没有继续遍历C下的相邻结点，而是遍历了D,符合广度优先遍历的规则。

    八、堆

    简介

    代码实现

    实现最小堆

    function MinHeap() {
  this.heap = []

  this.getParentIndex = function (childIndex) {
    return Math.floor((childIndex - 1) / 2)
  }
  /**
   * 交换位置
   * @param {number} index1
   * @param {number} index2
   */
  this.swap = function (index1, index2) {
    const temp = this.heap[index1]
    this.heap[index1] = this.heap[index2]
    this.heap[index2] = temp
  }

  /**
   * 上移到合适位置,和父结点比较，如果比父结点小则交换
   * @param {number} index 索引
   */
  this.moveUp = function (index) {
    if (index === 0) return
    const parentIndex = this.getParentIndex(index)
    if (this.heap[index] < this.heap[parentIndex]) {
      this.swap(index, parentIndex)
      this.moveUp(parentIndex)
    }
  }
  /**
   * 添加元素
   * @param {number} value
   */
  this.append = function (value) {
    this.heap.push(value)
    this.moveUp(this.heap.length - 1)
  }
}

const minHeap = new MinHeap()
minHeap.append(3)
minHeap.append(4)
minHeap.append(1)
minHeap.append(0)
minHeap.append(2)
minHeap.append(7)
minHeap.append(9)
// [0, 1, 3, 4, 2, 7, 9]

    通过heap可以模拟一个堆的表示，即：

    graph TD
0 --- 1 --- 4
0 --- 3 --- 7
1 --- 2
3 --- 9

    可以看到这个结构满足最小堆的定义

    应用场景

    1. 高效快速找到最大值最小值

    可以通过构建最大堆或最小堆快速找到最大最小值

    2. 实现堆排序

    上面我们实现了一个简单构建最小堆的方法，那么实现堆排序的原理其实就是先构建一个最小堆然后将堆顶（最小值弹出），再将其他元素构建堆，每次都弹出堆顶元素直到剩余元素为1时结束，这样就是实现了一个堆排序。

    九、最后


    起源地下载网 » 前端常见数据结构总结

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用？
    本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了？
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或 联络我们.。
    找不到素材资源介绍文章里的示例图片？
    对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发？
    请QQ联系我们
    掘金(liangyue)

    掘金(liangyue) SVIP

    分享到：

    相关推荐

    发表评论

    还没有评论，快来抢沙发吧！

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元