数据结构

本章节工具提供一些扩展的数据结构的构造和操作方法来方便我们构建更多的应用

栈

栈的使用场景有很多, 满足先进后出, 后进先出的原则. 比如函数递归的调用过程, 比如对树的深度优先遍历, 再比如使用逆波兰表示法(后缀表达式)进行数学四则运算.

12345678910111213141516171819202122232425262728293031323334353637383940414243444546

<template>
  <div>
    <div>检查字符串中的括号是否匹配. 结果: {{ matched ? '匹配' : '不匹配' }}</div>
    <input
      style="border: 1px solid #ccc"
      type="text"
      v-model="str"
      placeholder="表达式"
    />

    <br/><br />

    <div>遍历树</div>
  </div>
</template>

<script lang="ts" setup>
import { Stack } from '@cat-kit/fe'
import { computed, shallowRef } from 'vue'

const str = shallowRef('10 / (4 - 2)')

const matched = computed(() => {
  const stack = new Stack()

  let i = 0

  while (i < str.value.length) {
    let char = str.value[i]
    i++
    if (char === '(') {
      stack.push(char)
      continue
    }

    if (char === ')') {
      let ret = stack.pop()
      if (!ret) return false
      continue
    }
  }

  return stack.isEmpty()
})
</script>

树

树是最广泛使用的数据结构之一, 文件系统, 目录, 多级分类, 数据库引擎...

基于本工具库提供的Tree和TreeNode API, 你可以很轻易地构建一个树形组件

Tree API

Tree API是一个具有一组操作树节点的方法的集合

const data = {
  id: 0,
  children: [{ id: 1 }, { id: 2 }]
}
// 创建树
const tree = Tree.create(
  data,
  (v, index, parent) => new TreeNode(v, index, parent)
)

// 深度优先遍历
Tree.dft(tree, node => {})

// 广度优先遍历
Tree.bft(tree, node => {})

// 获取树的符合条件的第一个子节点
Tree.getChild(tree, node => {
  return node.value.id === 1
})

// 获取树的所有符合条件的子节点
Tree.getChildren(tree, node => {
  return node.value.id > 0
})

// 通过索引访问节点(访问树形数据索引为1的子节点)
Tree.visit(treeData, [1], 'children')

TreeNode API

TreeNode是一个树节点的类, 你可以通过继承这个类来扩展更多的属性和方法

TreeNode接受2-3个参数, 第一个参数为节点数据, 第二个参数为节点的索引, 第三个参数为父节点(可选, 在使用append等方法时会自动设置父节点)

const node = new TreeNode({ id: 1 }, 0)

node.append(index => new TreeNode({ id: 2 }, index))

构建树形组件

对于前端来说，通常使用派生出的Forest(森林)API来构建树相关的组件，森林和树唯一的区别在于森林拥有多个根节点。

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124

<template>
  <div>
    <JsonEditor v-model="data" />
    {{ forest.size }}
    <NodeRender v-for="node of forest.nodes" :node="node" />
  </div>
</template>

<script lang="tsx" setup>
import { Forest, TreeNode } from '@cat-kit/fe'
import {
  type PropType,
  computed,
  defineComponent,
  shallowReactive,
  shallowRef
} from 'vue'

type Data = {
  id: number
  children?: Data[]
}

const data = shallowRef<Data[]>([
  {
    id: 1,
    children: [{ id: 2 }, { id: 3, children: [{ id: 4 }] }, { id: 5 }]
  },
  { id: 6 }
])

type DataItem = (typeof data.value)[number]

// TreeNode是一个抽象类，所以你必须派生出自己的子类才能使用树相关的API
class CustomTreeNode<Val extends Record<string, any>> extends TreeNode<Val> {
  children?: CustomTreeNode<Val>[]

  parent: CustomTreeNode<Val> | null = null

  expanded = true

  constructor(value: Val, index: number, parent?: CustomTreeNode<Val>) {
    super(value, index)

    if (parent) {
      this.parent = parent
    }
    return shallowReactive(this)
  }
}

const forest = computed(() => {
  return Forest.create(data.value, CustomTreeNode)
})

const NodeRender = defineComponent({
  name: 'NodeRender',

  props: {
    node: {
      type: Object as PropType<CustomTreeNode<DataItem>>,
      required: true
    }
  },

  setup(props) {
    const toggleExpand = () => {
      props.node.expanded = !props.node.expanded
    }

    const handleDelete = () => {
      if (props.node.remove()) {
      }
    }

    const append = () => {
      props.node.append({ id: Math.random() })
    }

    const insert = () => {
      props.node.addToNext({ id: Math.random() })
    }
    const insertBefore = () => {
      props.node.addToPrev({ id: Math.random() })
    }

    return () => {
      const { node } = props
      return (
        <>
          <div style={{ paddingLeft: (node.depth - 1) * 20 + 'px' }}>
            <span>- {node.data.id}</span>
            {!node.isLeaf ? (
              <VButton onClick={toggleExpand}>
                {node.expanded ? '收起' : '展开'}
              </VButton>
            ) : null}
            <VButton onClick={handleDelete}>删除</VButton>
            <VButton onClick={append}>添加</VButton>
            <VButton onClick={insert}>插入到当前行下</VButton>
            <VButton onClick={insertBefore}>插入到当前行前</VButton>
          </div>

          {node.expanded
            ? node.children?.map(child => <NodeRender node={child} />)
            : null}
        </>
      )
    }
  }
})
</script>

<style>
a {
  user-select: none;
  cursor: pointer;
}

a + a {
  margin-left: 6px;
}
</style>