数据结构按类复习

为此间目录

  1. 模式匹配
  2. 画二义树（根据中序和后序，前序和中序）以及其线索二义树
  3. 求叶子结点个数，建立二叉排序树
  4. 广义表
  5. 求存储地址
  6. 代码设计
  7. 哈夫曼树
  8. 最小生成树
  9. 深度遍历，广度遍历，邻接表建立
  10. 哈希表（线性探测法、拉链法）
  11. 排序

接下来我们按顺序讲

模式匹配

对于模式匹配，实际的它的前身是一个叫做前缀表的东西
什么是前缀表？
一个文本串，一个模式串
模式串的作用是在文本串进行匹配，而我们的前缀表以及next数组就是在这个模式串上做文章
栗子：
一个模式串是：abcdaaf
此时这个的前缀表是什么？
分别是 0 0 0 0 1 1 0
这个数值就是为了跳到模式串本身的什么位置开始继续对文本串进行匹配
注意： 这里下标是从0开始

那么前缀表说完了，next数组又是什么呢？
next就是在前缀表的基础上进行了统一操作，比如统一减一，又或者是右移（同时将首位设置为-1）
p.s. 在严蔚敏老师的书中，逻辑都是右移的操作
同时提到了nextval数组，这是什么呢？
nextval的值的逻辑：

  1. 可以确定nextval的第一位与next数组第一位相同
  2. 看自身的next值，以next值为下标在这个模式串中寻找，如果是同样的字符，nextval的值变为此字符的nextval值，如果不同则为自身的next值

按照学习流程：此处放置案例，自行对逻辑进行验证：

广义表

实际上这类题型主要就是对其中概念进行一个理解，问的都是概念的东西：
表头：第一个逗号前面的东西
表尾：第一个逗号后面的东西（全部），同时用一个括号括起来
长度：逗号分隔成了几块就是几个
深度：数括号最多的数（单侧）

代码设计

给出建议需要记忆的有：
求二叉树的节点个数，叶子节点个数，求树的深度