数组，串和广义表

一维数组与多维数组

一位数组

• 定义：数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由下标（index）和值（value）组成。

多维数组

• 多维数组是一维数组的推广。n 多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。

• 数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。

• 二维数组
• 一维数组常被称为向量（Vector）。
• 二维数组 A[n][m]可看成是由 n 个行向量组成的向量，也可看成是由 m 个列向量组成的向量。
• 一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型:
• 二维数组a在存储器中有两种地址映射方式：行优先、列优先
• 行优先



在这个情况下，假设首元素地址为，单个元素占的个储存单元，则(此处从（1，1）开始计算)
• 列优先



在这个情况下，假设首元素地址为，单个元素占的个储存单元，则(此处从（1，1）开始计算)

• 对n微数组推广一下，得到（从（0，0）开始计算）
其中为第个维度的个数。

特殊矩阵

• 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
• 对称矩阵
• 三对角矩阵

• 利用特殊矩阵的一些性质寻找特殊的存储方法，可以节省大量的存储空间和计算时间

• 对称矩阵的压缩存储
• 对称矩阵中的元素关于主对角线对称，
• 为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。
• 把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储方式。
• 数组B共有个元素。
• 若上三角矩阵存储的储存位置为
• 若下三角矩阵存储的储存位置为

• 三对角矩阵的压缩存储



• 三对角矩阵中总共有个非零元素。
• 在三条对角线上的元素满足
• 反过来
若已知三对角矩阵中某元素 A[i][j] 在数组B存放于第 个位置，则有

稀疏矩阵

• 设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数（即），则称 A 为稀疏矩阵。

• 设矩阵 A 中有 s 个非零元素。令 ,称 为矩阵的稀疏因子（通常认为 时称之为稀疏矩阵）。

• 稀疏矩阵的两种表示方法：

• 三元组表示 （数组存储）
• 对于非零元素，每一个三元组记下它所在的行和列的位置 ，以及值。
• 三元组 唯一确定了矩阵A的一个非零元素

• 正交链表表示 （链表存储）

• 三元组
• 存储规则：在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。
• 稀疏矩阵的转置运算要转化为对应三元组表的转置。



• 设矩阵列数为 Cols，对矩阵三元组表扫描Cols次。第 k 次检测列号为 k 的项。
• 第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
• 快速转置算法
• 设矩阵三元组表总共有项，上述算法的时间代价为。当非零元素的个数和同数量级时，算法transMatrix的时间复杂度为。
• 快速转置算法的思想为：对原矩阵A扫描一遍，按 A中每一元素的列号，立即确定在转置矩阵B三元组表中的位置，并装入它。
• 为加速转置速度，建立辅助数组 rowSize 和rowStart：
• rowSize：记录矩阵转置前各列，即转置矩阵各行非零元素个数；
• rowStart：用于记录转置矩阵 B 中每行的第一个非零元素在 B.smArray 中的存储位置。
• 扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 rowStart 表, 按查到的位置直接将该项存入转置三元组表中



代码

• 带行指针数组的二元组
• 稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。
• 在行指针数组中元素个数与矩阵行数相等。第 i 个元素的下标 i 代表矩阵的第 i 行，元素的内容即为稀疏矩阵第 i 行的第一个非零元素在二元组表中的存放位置。
• 二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按列号递增的顺序排列。

• 稀疏矩阵表示为行链表与列链表的十字交叉——称为正交链表(十字链表)
• 优点：适应矩阵操作(+、-、*)时矩阵非零元素的动态变化

字符串

• 字符串是 n ( ≥0 ) 个字符的有限序列，记作 S : “c1c2c3…cn”其中，S 是串名字“c1c2c3…cn”是串值ci 是串中字符n 是串的长度，n = 0 称为空串。
例如,S : “Nanjing University”。
注意：空串和空白串不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。

• 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
• 设A和B分别为A = “This is a string” B = “is”
则 B 是 A 的子串，A 为主串。B 在 A 中出现了两次，首次出现所对应的主串位置是2（从0开始）。因此，称 B 在 A 中的位置为2。

• 一些重载的操作

• 串的模式匹配
• 定义在主串中寻找子串（第一个字符）在串中的位置。
• 在模式匹配中，子串称为模式，主串称为目标。
例如：在“Beijing”中匹配“jin”，得到结果为3
• 朴素的模式匹配（B-F算法）
• 一趟一趟的从头匹配。
• 对这个进行时间复杂度分析，最坏的情况下需要跑 次，显然是一个 的复杂度。
• 改进的模式匹配（ KMP算法）
• 只要消除了每趟失配后为实施下一趟比较时目标指针的回退/回溯，可以提高模式匹配效率。
• 实施KMP算法的时间代价：
• 若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(nm)+m = n。
• 若每趟第 m 个不匹配，总比较次数最坏亦达到 n。
• 也就是说，直接去找和前k个一样最后k个字符！

• Knuth 等人发现，对于不同的 j（失配位置），k 的取值不同，它仅依赖于模式 P 本身前 j 个字符的构成，与目标无关。

• 可以用一个 next 特征向量来确定：当模式 P 中第 j 个字符与目标 S 中相应字符失配时，模式P 中应当由哪个字符（设为第k+1个）与目标中刚失配的字符重新继续进行比较。

• next数组的定义为：next[i]表示模式串A[0]至A[i]这个字串，使得前k个字符（前缀）等于后k个字符（后缀）的k的最大值。

• 那么现在整个算法变为：
若设若在进行某一趟匹配比较时在模式 P 的第 j 位失配：
• 如果 j > 0，那么在下一趟比较时模式串 P的起始比较位置是 ，目标串 T 的指针不回溯，仍指向上一趟失配的字符；
• 如果 j = 0，则目标串指针 T 进一，模式串指针 P 回到 ，继续进行下一趟匹配比较。

• KMP算法的时间复杂度不会超过。

广义表

• 广义表是 n ( ≥0 ) 个表元素组成的有限序列，记作

• LS是表名，a是表元素，可以是表（称为子表），可以是数据元素（称为原子）。n为表的长度。n= 0的广义表为空表。

• 特性
• 有次序的，第一个元素称为表头，后面的元素称为表尾。也就是说返回表尾返回的是后面的元素组成的表。
• 有深度的，因为包含了子表。同时也是有长度的。
• 可递归
• 有长度
• 可共享

• 几种类型

• 广义表结点定义
• 结点类型 utype：= 0, 表头；= 1, 原子数据；= 2, 子表
• 信息info：utype = 0时,存放引用计数(ref)；utype = 1时, 存放数据值(value)；utype = 2时, 存放指向子表表头的指针(hlink)
• 尾指针tlink：utype = 0时,指向该表第一个结点；utype = 1, 2时, 指向同一层下一个结点

• 广义表的递归算法
• 广义表的复制算法
• 广义表的删除算法
• 广义表的深度算法

• 代码