串、数组和广义表

1. 串

1.1 串的定义

串(string)是由零个或多个字符组成的有限序列。一般记为

$$S=a_1{a}_2...a_n(n\ge 0)$$

其中，S是串名，单引号括起来的字符序列是串的值，$a_i$可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串(用表示)。

1.2 串的模式匹配

1.2.1 朴素模式匹配

使用暴力求解的方法，一直遍历，但时间复杂度过高。

int ViolentMatch(string &s, string &t)
{int i = 0, j = 0;while (i < s.size() && j < t.size()){if (s[i] == t[j]){i++;j++;}else{i = i - j + 1;j = 0;}}if (j == t.size())return i - j;elsereturn -1;
}

1.2.2 KMP算法

vector<int> make_next(const string &s)
{int i = 0, j = -1;vector<int> next(s.size() + 1, 0); // Initialize the vector with the correct sizenext[0] = -1;                      // Set the first element to -1while (i < s.size()){if (j == -1 || s[i] == s[j]){i++;j++;next[i] = j;}elsej = next[j];}return next;
}
int KMP(const string &s, const string &t)
{int i = 0, j = 0;vector<int> next = make_next(t);while (i < s.size() && j < (int)t.size()){if (j == -1 || s[i] == t[j]) // Fix the logic error here{i++;j++;}elsej = next[j];}if (j == t.size())return i - j;return -1;
}

2. 数组和广义表

2.1 数组

2.1.1 数组的定义

数组是由n(n>1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表;二维数组可视为其元素是定长数组的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

2.1.2 数组的存储结构

大多数计算机语言都提供了数组数据类型，逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。

以一维数组 A[0…n-1]为例，其存储结构关系式为

$$LOC(a_{i,j})=LOC(a_{0,0})+i\times L(0\le i\le n)$$

其中L是每个存储单元的大小。

对于多维数组，有两种映射方法:按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是:先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组的行下标与列下标的范围分别为[0,$h_1$]与[0,$h_2$]，则存储结构关系式为

$$LOC(a_{i,j})=LOC(a_{0,0})+[i\times (h_2+1)+j)\times L$$

2.2 特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

2.2.1 对称矩阵

对于矩阵$A$元素满足性质 $a_{i,j}=a_{j,i}$，则其为对称矩阵。

由于其上三角与下三角元素相同，使用二维数组会浪费空间，故使用一维数组存储来压缩空间。如下图所示，数组下标从0开始。

2.2.2 三角矩阵

下三角矩阵：

上三角矩阵：

2.2.3 三对角矩阵

2.2.4 稀疏矩阵