第四章 字符串和多维数组
4.1 字符串
4.1.1 字符串的定义
1.字符串的定义
字符串是零个或多个组成的有限序列，只包含空格的串成为空格串。串中所包含的字符个数成为串的长度，长度为0的串为空串，记作“”，一个非空串通常该记作： S=“s1，s2…sn”
字符串中任意个连续的字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串，子串的第一个字符在主串的序号成为子串在主串的位置。
2.字符串的比较
当下列条件之一成立时，称X>Y。
（1）n<m，且x1<y1，(i=1,2…,n);
（2）存在某个k≤min(m,n)，使得xi=yi,(i=1,2,…,k-1)，xk<yk。
4.1.3 模式匹配
给定两个字符S=“s1，s2…sn”和T=“t1，t2…tn”，在主串S中寻找子串T的过程称为模式匹配，T成为模式。如何匹配成功，返回T在S中的位置;如果匹配失败，返回0.
1. 朴素的模式匹配算法
朴素的模式匹配算法BF
intBF(char S[],char T[])
{
i=0;j=0;
while ((S[i]!='\0')&&T[j]!='\0'))
{
if(S[i]==T[j]){i++;j++}
else {i=i-j+1;j=0;}
}
if(T[j]=='\0')return (i-j+1);
else return 0;
}
2. 改进的模式匹配算法
BF算法简单但效率较低，一种对BF算法做了很大改进的模式匹配算法是KMP算法，其基本思想是主串不进行回溯。
由T[0]~T[k-1]=S[i-k]~S[i-1]和T[j-k]~T[j-1]=S[i-k]~S[i-1]。
可得： T[0]~T[k-1]=T[j-k]~T[j-1]
用next[j]表示T[j]对应的k值(0≤j<m),其定义如下：
-1 j=0
next[j]= max {k|1≤k<j且 T[0]…T[k-1]=T[j-k]…T[j-1]}
0 其他情况
KMP算法的时间复杂度是O(n+m)。KMP算法和BF算法相比，增加了很大难度，我们主要学习该算法的设计技巧。
4.2 多维数组
4.2.1 数组的定义
数组是由类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素，每个元素受n（n≥1）个线性关系的约束，每个元素在n个线性关系中的序号i1,i2,…,in称为该元素的下标，并称该数组为n维数组。
数组是一个具有固定格式和数量的数据集合，在数组中一般不能执行插入或删除某个数组元素的操作。因此，除了初始化和销毁之外，在数组中通常只有两种操作。
（1）读操作：给定一组下标，读取相应的数组元素。
（2）写操作：给定一组下标，存储或修改相应的数组元素。
4.2.2 数组的存储结构与存址
由于数组一般不执行插入和删除操作，也就是说，一旦建立了数组，其元素个数和元素之间的关系就不再发生变动，而且，数组是一种特殊的数据结构，一般要求能够随机存取，因此，数据采用顺序存储结构。由于内存单元是一维结构，而多维数组是多维结构，所以，采用顺序存储结构存储数组首先需要将多维结构映射到一维结构。
二维数组的每个元素含有两个下标，需将二维关系映射为一维关系。常用的映射方法有两种：以行序为主序和以列序为主序。
按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。
按列优先存储的基本思想是：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。任一元素存储地址的计算与按行优先存储类似。
按行优先存储的基本思想是：最右边的下标先变化，即最右下表从小到大，循环一遍后，右边第二个下标再变，……最后是最左下标。
按列优先存储的基本思想恰好相反:最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，……最后是最右下标。
4.3 矩阵的压缩存储
矩阵是很多科学与工程计算问题中的处理对象。在实际应用中，经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素并且他们的分布有一定的规律——称为特殊矩阵，或者矩阵中与很多零元素——称为稀疏矩阵。
压缩存储的基本思想是：1 为多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。
4.3.1 对称矩阵的压缩存储
对称矩阵关于主对角线对称，因此只需存储下三角部分即可。这样，原来需要n*n个存储单元，现在只需n*（n+1）/2个存储单元，节约了大约一半的存储单元。当n较大时，这是客观的一部分存储单元。
4.3.2 三角矩阵的压缩存储
下三角矩阵的压缩存储与对称矩阵类似，不同之处仅在于存储下三角中的元素以外，还要存储对角线上方的常数。因为是同一个常数，所以只存储一个即可。这样，共存储n*(n+1)/2+1个元素，将其按行优先存入数组SA[n*(n+1)/2+1]中。
下三角矩阵中任一元素a(ij)在SA中的下标k与i、j的对应关系为：
当i>=j时，k=i*(i-1)/2+j-1;
当i<j时，k=n*(n+1)2；
同理，上三角矩阵中任一元素a(ij)在SA中的下标k与i、j对应关系为：
当i<=j时，k=(i-1)*(2n-i+2)/2+j-i;
当i>j时，k=n*(n+1)/2
4.3.3 对角矩阵的压缩存储
在对角矩阵中，所有非零元素都集中在以主对角线为中心的带状区域，除了主对角线和他的上下若干条主对角线的元素外，所有其他元素都为零。因此，对角矩阵也称为带状矩阵。
对于一个m*n的w对角矩阵（w是占有非零元素的对角线的个数，也称带宽），一种压缩方法是将其压缩到一个m行w列的二维数组B中，则a(ij)映射为b(ts)，其映射关系为：
（1） t=i
（2） s=j-i+2
4.3.4 稀疏矩阵的压缩存储
将稀疏矩阵的非零元素对应的三元组成所构成的集合，按行优先的顺序排列成一个线性表，称为三元组表，则稀疏矩阵的压缩存储转化为三元组表的存储。
1. 三元组顺序表
采用顺序存储结构存储的三元组表称为三元组顺序表。显然，要唯一表示一个稀疏矩阵，还需要在存储三元表的同时存储该矩阵的行数、列数和非零元素的个数，其存储结构定义如下：
const int MaxTerm=100;
struct Sparsematrix
{
elementdata [MaxTerm];
intmu,nu,tu;
};
2. 十字链表
稀疏矩阵的链接存储结构称为十字链表。它具备存储结构的特点，因此，在非零元素的个数及位置都会发生变化的情况下，通常采用十字链表存储稀疏矩阵。
十字链表存储稀疏矩阵的基本思想是：将每个非零元素对应的三元组存储为一个链接表结点，节点由5个域组成。
其中，element为数据域，存储非零元素对应的三元组；
right为指针域，指向同一行中的下一个三元组；
down为指针域，指向同一列中的下一个三元组。
4.4 应用举例
1. 字符串的应用举例——凯撒密码
2. 数组的应用举例——幻方