【软考】9.2 串/数组/矩阵/广义表/树

《字符串》

• 一种特殊的线性表，数据元素都为字符
• 模式匹配：寻找子串第一次在主串出现的位置
  

• 模式匹配算法

1. 暴力破解法（布鲁特-福斯算法）

• 主串与子串一个个匹配
• 效率低
  

2. KMP算法

• 主串后缀和子串前缀能否找到一样的元素，能就把子串移上去，不用再对比，从主串当前中断的位置开始对比
  
• abaac:P1P2P3P4P5
• 1. j=1 ——> next[1]=0
• 2. j=2，1<k<2，其他情况 ——> next[2]=1
• 3. j=3，1<k<3：k=2，‘P(2-1)’=‘P(3-1)’ ——> ‘P1’=‘P2’——> a=b，其他情况 ——> next[3]=1
• 4. 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 ，其他情况；
• 5. 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