【软考】9.2 串/数组/矩阵/广义表/树
《字符串》
- 一种特殊的线性表，数据元素都为字符
- 模式匹配：寻找子串第一次在主串出现的位置
- 模式匹配算法
1. 暴力破解法（布鲁特-福斯算法）
- 主串与子串一个个匹配
- 效率低
2. KMP算法
- 主串后缀和子串前缀能否找到一样的元素，能就把子串移上去，不用再对比，从主串当前中断的位置开始对比
- abaac:P1P2P3P4P5
- j=1 ——> next[1]=0
- j=2，1<k<2，其他情况 ——> next[2]=1
- j=3，1<k<3：k=2，‘P(2-1)’=‘P(3-1)’ ——> ‘P1’=‘P2’——> a=b，其他情况 ——> next[3]=1
- j=4，1<k<4：
k=2，‘P(2-1)’=‘P(4-2+1)’ ——> ‘P1’=‘P3’——> a=a ——>next[4]=2;
k=3，‘P1P(3-1)’=‘P(4-3+1)P(4-1)’ ——> ‘P1P2’=‘P2P3’——> ab=ba ，其他情况；
- j=5，next[5]=2
- 即 next = 01122
《数组》
- 适用于采用顺序结构
- 数组存储地址的计算
《矩阵》
- 直接带算式
- a[1,1]——> B[1] ——> i=1，j=1，k=1；
- A[0,0]——>B[1]；A[0,1]——>B[2]；
《广义表》
- 长度：最外层包含的元素个数
- 深度：单边括号的个数；原子的深度为0，空表深度为1
《树与二叉树》
- 树
- 线性表的每个节点只有一个入度和一个出度
- 树的每个节点只有一个入度，多个出度
- 度：一个结点的子树个数
- 叶子结点：度为0的结点
- 树的高度（深度）：一棵树的最大层数
- 二叉树
- 二叉树：每一个结点的度 ≤2
- 满二叉树：除了最后一层的叶子结点外，每一个结点的度都是2
- 一共有k层，第 k-1 层是满的，第 k 层：
- （完全二叉树）从左到右是不间断的（如左4右5，左6）
- （非完全二叉树）从左到右是可间断的（如左4右5，右6）
- 二叉树的性质
- 二叉树第 i 层 至多有 2^(i -1) 个节点
- 深度为k的二叉树（满二叉树）至多有 (2^k) -1 个节点
- 终端节点数为n0，度为2的节点数为n2，则 n0 = n2 +1
