《字符串》
- 一种特殊的线性表,数据元素都为字符
- 模式匹配:寻找子串第一次在主串出现的位置
- 模式匹配算法
1. 暴力破解法(布鲁特-福斯算法)
- 主串与子串一个个匹配
- 效率低
2. KMP算法文章来源:https://www.toymoban.com/news/detail-718279.html
- 主串后缀和子串前缀能否找到一样的元素,能就把子串移上去,不用再对比,从主串当前中断的位置开始对比
- 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
《数组》
- 适用于采用顺序结构
- 数组存储地址的计算
《矩阵》
文章来源地址https://www.toymoban.com/news/detail-718279.html
- 直接带算式
- 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
到了这里,关于【软考】9.2 串/数组/矩阵/广义表/树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!