目标：一文彻底掌握软考上午题中“串与数组”所有高频考点。包含串的基本概念、模式匹配的朴素算法与KMP思想，以及对称矩阵、三角矩阵、对角矩阵、稀疏矩阵的压缩存储与地址计算。配大量例题与解题技巧，看完这篇，无需再翻其他资料。

一、串的基本概念

1. 串的定义

串（字符串）是由零个或多个字符组成的有限序列，记为 S = "a1a2...an"。其中：

• 空串：长度为0的串，记为 ""。
• 空格串：由一个或多个空格组成的串，长度不为0。
• 子串：串中任意个连续字符组成的子序列。
• 主串：包含子串的串。
• 子串位置：子串在主串中第一次出现时，首字符在主串中的位置（通常从1开始）。

2. 串的比较

串的比较按字符的ASCII码或字典序进行，逐字符比较，直到出现不同字符或结束。

例题1：串 "abc" 和 "abd" 的大小关系是（ ）。
A. "abc" > "abd" B. "abc" < "abd" C. 相等 D. 无法比较
答案：B
解析：逐字符比较，前两个字符相同，第三个字符 c 的ASCII码小于 d，所以 "abc" < "abd"。

二、模式匹配

模式匹配是指在一个主串中查找某个子串（模式串）第一次出现的位置。设主串长度为n，模式串长度为m（n ≥ m）。

1. 朴素模式匹配算法（Brute-Force）

• 思想：从主串的第一个字符开始，依次与模式串比较。若当前字符匹配，继续比较下一个；若不匹配，主串指针回退到本次匹配开始位置的下一个字符，模式串指针回到开头，重新比较。
• 时间复杂度：最坏情况 O(n×m)，平均情况 O(n+m)。
• 优点：简单直观。
• 缺点：主串指针频繁回退，效率低。

例题2：主串 "ababcabcacbab"，模式串 "abcac"，用朴素算法需要比较多少次？
（略，软考通常不要求具体次数，只考复杂度）

2. KMP算法（了解即可）

基本思想

KMP算法由Knuth、Morris、Pratt提出，核心是利用已经匹配过的信息，避免主串指针回退。当匹配失败时，主串指针不回退，模式串指针根据next数组滑动到指定位置继续比较。

next数组

• next[j] 表示模式串第j个字符失配时，模式串指针应跳转到的位置。
• 对于模式串 P = p1p2...pm，next[j] 定义为：P[1..j-1] 的最长相等前后缀的长度 + 1（通常从1开始编号）。
• 软考中“了解即可”，一般只考查KMP相比朴素算法的优点（主串指针不回退，时间复杂度O(n+m)），不要求手动计算next数组。

KMP时间复杂度

• 预处理next数组：O(m)
• 匹配过程：O(n)
• 总时间复杂度：O(n+m)

例题3：KMP算法相比朴素模式匹配算法的主要优点是（ ）。
A. 不需要模式串
B. 主串指针不需要回退
C. 时间复杂度为O(n×m)
D. 适用于任何语言
答案：B
解析：KMP利用已匹配信息，主串指针不回退，时间复杂度降为O(n+m)。

三、数组与矩阵压缩存储

1. 数组的基本概念

数组是由相同类型数据元素组成的有限序列，按一定顺序排列。一维数组是线性表，二维数组可视为一维数组的扩展。

数组的存储方式：

• 行优先存储：按行依次存储，先存第0行，再存第1行……（C/C++、Java默认）。
• 列优先存储：按列依次存储，先存第0列，再存第1列……（Fortran默认）。

二维数组地址计算（行优先）：
设二维数组 A[m][n]，每个元素占L字节，起始地址为Loc(a00)，则元素 a[i][j] 的地址为：
[ \text{Loc}(a_{ij}) = \text{Loc}(a_{00}) + (i \times n + j) \times L ]

列优先：
[ \text{Loc}(a_{ij}) = \text{Loc}(a_{00}) + (j \times m + i) \times L ]

例题4：二维数组 A[5][6]，每个元素占2字节，起始地址为1000，按行优先存储，求 A[3][4] 的地址。
解析：

• 行优先：Loc = 1000 + (3×6 + 4)×2 = 1000 + (18+4)×2 = 1000 + 44 = 1044。

2. 矩阵压缩存储

矩阵压缩存储的核心思想：多个相同的非零元素只分配一个存储空间，零元素不分配空间，从而节省存储量。

（1）对称矩阵

• 特点：a[i][j] = a[j][i]，矩阵关于主对角线对称。
• 压缩方法：只存储下三角（或上三角）部分，共 n(n+1)/2 个元素。
• 存储方式：按行优先存储下三角。

地址计算（下三角，行优先，下标从0开始）：
对于元素 a[i][j]（i ≥ j），在一维数组中的下标 k 为：
[ k = \frac{i(i+1)}{2} + j ]
若下标从1开始，则：
[ k = \frac{i(i-1)}{2} + j ]

例题5：对称矩阵 A[5][5]，采用行优先压缩存储下三角，每个元素占1字节，起始地址为100，求 A[3][2] 的地址。
解析（下标从0开始）：

• i=3, j=2，满足 i≥j。
• k = 3×4/2 + 2 = 6 + 2 = 8。
• 地址 = 100 + 8×1 = 108。

（2）三角矩阵

• 下三角矩阵：主对角线以上元素全为常数c（通常为0）。
• 上三角矩阵：主对角线以下元素全为常数c。
• 压缩方法：只存储非常数部分，另加一个存储常数的空间。
• 下三角矩阵：存储下三角及对角线，共 n(n+1)/2 个元素，再加1个常数，共 n(n+1)/2 + 1 个。
• 上三角矩阵：存储上三角及对角线，共 n(n+1)/2 个元素，再加1个常数。

下三角矩阵地址计算（行优先，下标从0开始）：
对于 a[i][j]（i ≥ j），k = i(i+1)/2 + j。
对于 i < j，值为常数，存放在最后一个位置。

上三角矩阵地址计算（行优先，下标从0开始）：
对于 a[i][j]（i ≤ j），前 i 行共有 i(2n - i + 1)/2 个元素，第 i 行从 j=i 开始，所以：
[ k = \frac{i(2n - i + 1)}{2} + (j - i) ]
或简化为：k = i*n - i(i-1)/2 + (j - i)。

例题6：上三角矩阵 A[4][4]，采用行优先压缩存储，每个元素占2字节，起始地址为200，求 A[1][3] 的地址。
解析（下标从0开始，n=4）：

• i=1, j=3，满足 i≤j。
• k = 1×4 - 1×0/2 + (3-1) = 4 + 2 = 6。
• 地址 = 200 + 6×2 = 212。

（3）对角矩阵（带状矩阵）

• 特点：所有非零元素集中在主对角线及其两侧的若干条对角线上。
• 三对角矩阵：非零元素在主对角线及上下各一条对角线上，共 3n-2 个非零元素。
• 压缩方法：按行存储非零元素。

三对角矩阵地址计算（行优先，下标从0开始）：
对于 a[i][j]，满足 |i - j| ≤ 1，其在一维数组中的下标 k 为：
[ k = 2i + j ]
（注意：这是简化公式，需要根据具体存储方式调整）

例题7：三对角矩阵 A[5][5]，按行优先压缩存储非零元素，每个元素占4字节，起始地址为500，求 A[3][2] 的地址。
解析（下标从0开始）：

• i=3, j=2，满足 |3-2|=1≤1。
• k = 2×3 + 2 = 8。
• 地址 = 500 + 8×4 = 532。

（4）稀疏矩阵

• 特点：非零元素极少，零元素占绝大多数。
• 压缩方法：
  • 三元组表：存储每个非零元素的行号、列号、值。(row, col, value)。
  • 十字链表：每行每列用链表链接，适合非零元素动态变化。
• 三元组表：顺序存储，每个非零元素占三个域。若共有t个非零元素，则需3t个存储单元。

例题8：稀疏矩阵有1000个元素，其中非零元素只有20个。若用三元组表存储，需要多少个存储单元？
解析：每个非零元素存3个值（行、列、值），共20×3 = 60个存储单元。若加上矩阵行列数等信息，略多。

四、软考常见题型与技巧

题型一：串的基本操作

例题9：串 "software" 的子串个数是（ ）。
A. 8 B. 36 C. 9 D. 45
答案：B
解析：长度为n的串，子串个数为 n(n+1)/2 + 1（包括空串）。n=8，则 8×9/2 + 1 = 36 + 1 = 37？但通常子串不包括空串，则 n(n+1)/2 = 36。软考中若问子串个数，一般不包括空串，答案为36。

题型二：模式匹配复杂度

例题10：朴素模式匹配算法在最坏情况下的时间复杂度为（ ）。
A. O(n) B. O(m) C. O(n+m) D. O(n×m)
答案：D
解析：最坏情况下，主串每个位置都要比较m次，共n-m+1个位置，时间复杂度O(n×m)。

题型三：对称矩阵地址计算

例题11：对称矩阵 A[6][6]，采用行优先压缩存储下三角，每个元素占1字节，起始地址为0，求 A[4][3] 的地址。
解析（下标从0开始）：

• i=4, j=3，满足 i≥j。
• k = 4×5/2 + 3 = 10 + 3 = 13。
• 地址 = 0 + 13 = 13。

题型四：三角矩阵地址计算

例题12：下三角矩阵 A[5][5]，采用行优先压缩存储，每个元素占2字节，起始地址为100，求 A[3][1] 的地址。
解析（下标从0开始）：

• i=3, j=1，满足 i≥j。
• k = 3×4/2 + 1 = 6 + 1 = 7。
• 地址 = 100 + 7×2 = 114。

题型五：三对角矩阵地址计算

例题13：三对角矩阵 A[6][6]，按行优先压缩存储非零元素，每个元素占1字节，起始地址为0，求 A[4][3] 的地址。
解析（下标从0开始）：

• i=4, j=3，满足 |4-3|=1≤1。
• k = 2×4 + 3 = 11。
• 地址 = 0 + 11 = 11。

五、易错点与注意事项

1. 串的子串个数：长度为n的串，非空子串个数为 n(n+1)/2，包括空串则为 n(n+1)/2 + 1。注意题目是否包含空串。
2. KMP算法：软考只需了解思想，知道主串指针不回退、时间复杂度O(n+m)即可。
3. 矩阵压缩存储：注意下标是从0开始还是从1开始，公式不同。
4. 对称矩阵：只存储下三角（或上三角），注意 a[i][j] 与 a[j][i] 的转换。
5. 三角矩阵：常数项只存一个，注意存储单元总数。
6. 三对角矩阵：非零元素个数为 3n-2，注意地址公式。
7. 稀疏矩阵：三元组表每个非零元素占3个域，十字链表适合动态操作。
8. 行优先与列优先：C语言默认行优先，Fortran默认列优先，注意题目指定。

六、总结与速记

速记1：串

• 子串个数：n(n+1)/2（非空）
• 朴素匹配：O(n×m)
• KMP：O(n+m)，主串指针不回退

速记2：矩阵压缩

• 对称矩阵：存下三角，n(n+1)/2个元素，k = i(i+1)/2 + j（下标从0开始）
• 下三角矩阵：存下三角+常数，n(n+1)/2 + 1个元素
• 上三角矩阵：存上三角+常数，n(n+1)/2 + 1个元素
• 三对角矩阵：3n-2个非零元素，k = 2i + j（简化）
• 稀疏矩阵：三元组表，每个非零元素3个域

速记3：地址计算

• 二维数组行优先：Loc = 基址 + (i×n + j)×L
• 对称矩阵下三角：Loc = 基址 + (i(i+1)/2 + j)×L
• 上三角矩阵：Loc = 基址 + (i×n - i(i-1)/2 + (j-i))×L

---

掌握以上内容，配合历年真题练习，串与数组部分即可轻松得分。建议重点练习对称矩阵和三角矩阵的地址计算，以及串的子串个数统计。

下期预告：数据结构与算法（下）——树与二叉树（性质、遍历、哈夫曼树、二叉排序树），敬请关注。

发布日期：2026-09-15