第四章 串、数组、广义表

4.1 关于串

4.11 串的定义与特点

串(string)(或字符串）是由零个或多个字符组成的有限序列。严格意义上讲，串存储结构也是一种线性存储结构，因为字符串中的字符之间也具有"一对一"的逻辑关系。

4.12 串的具体实现

存储一个字符串，数据结构包含以下 3 种具体存储结构：

1. 定长顺序存储：实际上就是用普通数组（又称静态数组）存储。
2. 堆分配存储：用动态数组存储字符串；
3. 块链存储：用链表存储字符串；

4.13 串的定长顺序存储结构

串的定长顺序存储结构，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。

定长顺序串的存储结构如下：

#define MAXLEN 255
typedef struct {char ch[MAXLEN+1];int length;
}SString;

缺点：这种定义方式是静态的， 在编译时刻就确定了串空间的大小。 而多数情况下， 串的操作是以串的整体形式参与的， 串变量之间的长度相差较大， 在操作中串值长度的变化也较大， 这样为串变量设定固定大小的空间不尽合理。

4.14 串的堆式存储结构

串的堆分配存储，其具体实现方式是采用动态数组存储字符串。

堆与其他区域不同，堆区的内存空间需要程序员手动使用malloc() 函数申请，并且在不用后要手动通过 free() 函数将其释放。 可以
为每个新产生的串动态分配一块实际串长所需的存储空间， 若分配成功， 则返回 一 个指向起始地址的指针， 作为串的基址， 同时为了以后处理方便， 约定串长也作为存储结构的 一 部分。

串的堆式存储结构如下：

typedef struct{char *ch;int length;
}HString;

4.15 串的链式存储结构

顺序串的插入和删除操作不方便，需要移动大量的字符。因此，可采用单链表方式存储串。而且需要注意的是，此结构还有一个名字，就是“串的块链式存储结构”，也就是说，链式存储结构可以是分块的，每块可以是一个字符，也可以是多个字符。其存储方式，如下图：

串的链式存储结构如下：

#define CHUNKSIZE 80 //可由用户定义的块大小typedef struct Chunk{char ch [CHUNKSIZE];struct Chunk *next;
}Chunk;typedef struct{Chunk *head,*tail;		//串的头和尾指针int length;				//串的当前长度
}String;

关于串的存储结构，较简单，将不放代码，此部分着重学习理解BF算法和KMP算法思想。

---

4.16 BF算法

普通模式匹配算法，其实现过程没有任何技巧，就是简单粗暴地拿一个串同另一个串中的字符一一比对，得到最终结果。即暴力匹配。

算法步骤图示

1. 从主串起始位置开始，将模式串与主串逐个匹配，如果匹配，就比较模式串下一个位置和主串下一个位置，如果不匹配，将模式串向右移动一位，然后从头开始匹配

   

2. 定义指针i和j分别指向主串当前位置和模式串当前位置。如上图，初始时i和j都指向开头，i=0,j=0。有S[0]==P[0]，所以将i和j都后移一位，继续比较。直至i=3，j=3，此时S[3]!=P[3]

   

3. 所以将模式串向右移动一位，重新匹配

   

算法总结

1. 如果当前字符匹配成功（即S[i]==P[j]），则i++，j++，继续匹配下一个字符；
2. 如果当前字符匹配失败（即S[i]!=P[j]S[i]），则i=i−(j−1)，j=0，即i回溯，j重置为0，重新开始匹配。

算法代码描述

int ViolentMatch(char *s, char *p){int i = 0;int j = 0;     				// 初始化while (i < strlen(s) && j < strlen(p)){if (s[i] == p[j]){      // 当前位置匹配成功i++;j++;}else{                	// 当前位置匹配失败i = i - j + 1;      // i回溯j = 0;      		// j重置}}if (j == strlen(p))     	// 匹配成功return i - j;elsereturn -1;
}

由以上分析，可知每轮的查找，一旦失败，主串的指针i总是会回溯到i-j+1的位置，模式串的指针也会回溯到j=1的位置。

不难看出，BF算法（暴力匹配算法）的效率过低，平均时间复杂度能达到O(m × n)，唯一的优点也就是思路简单，容易理解了。

---

4.17 KMP算法

经上文分析，导致BF算法时间复杂度过高的一大原因就是主串指针i和模式串指针j的回溯操作过于频繁

因为在模板串P的每一个位置都有可能发生不匹配，也就是说我们要计算每一个位置对应的k，在KMP算法中，用数组next对其进行保存，即next[j]=k，表示当S[i]!=P[j]时，指针j下一步指向下标k。 假设我们已经求出next数组，我们可以对暴力匹配进行改进，代码如下：

int kmpSearch(char *s, char *p){int i = 0;int j = 0;     // 初始化int next[strlen(s)];GetNext(p,next);while (i < strlen(s) && j < strlen(p)) {if (j == -1 || s[i] == p[j])      // 当前位置匹配成功{i++;j++;} else      // 当前位置匹配失败{j = next[j];   // i不回溯，j移动到next[j]位置，相当于模板串右移j - next[j]}}if (j == strlen(p))     // 匹配成功return i - j;elsereturn -1;
}

next[]的求解

首先要理解清楚，next[]是个什么东西，next[j]的值（也就是k）表示当S[i]!=P[j]时，指针j下一步指向下标k。

模式串中各字符对应 next 值的计算方式是，取该字符前面的字符串（不包含自己），其前缀字符串和后缀字符串相同字符的最大个数再 +1 就是该字符对应的 next 值。

前缀字符串指的是位于模式串起始位置的字符串，例如模式串 “ABCD”，则 “A”、“AB”、“ABC” 以及 “ABCD” 都属于前缀字符串；后缀字符串指的是位于串结尾处的字符串，还拿模式串 “ABCD” 来说，“D”、“CD”、“BCD” 和 “ABCD” 为后缀字符串。

**注：**模式串中第一个字符对应的值为 0，第二个字符对应 1 。而严蔚敏版教材中第一个字符对应值为1。如图：

代码实现如下：

/*** 获取Next表* @param p 模式串* @param next*/
void GetNext(char* p, int next[]){int k = -1;int j = 0;next[0] = -1;while (j < strlen(p) - 1){if (k == -1 || p[j] == p[k]){k++;j++;next[j] = k;}else{k = next[k];}}
}

next[]的优化

此时的next表获取方法还有一个弊端，见下图场景：

→

出现这种多余的操作，问题在当 T[i-1]==T[j-1]成立时，没有继续对 i++ 和 j++ 后的 T[i-1] 和 T[j-1] 的值做判断。针对这个问题可对next表获取函数做出优化如下：

/*** 优化next表* @param p 模式串* @param next*/
void NextVal(char* p, int next[]){int k = -1;int j = 0;next[0] = -1;while (j < strlen(p) - 1){if (k == -1 || p[j] == p[k]){k++;j++;if (p[j] != p[k] ){next[j] = k;} else{next[j] = next[k];}}else{k = next[k];}}
}

---

4.2 关于数组

TIPS:本节无演示代码

4.2.1 数组的定义及特点

数组作为一种线性存储结构，对存储的数据通常只做查找和修改操作，因此数组结构的实现使用的是顺序存储结构。

因为在数组中做插入和删除的操作的话，效率太差，一般不会做这种骚操作。

​ 由于数组可以是多维的，而顺序存储结构是一维的，因此数组中数据的存储要制定一个先后次序。通常，数组中数据的存储有两种先后存储方式：

1. 以列序为主（先列后行）：按照行号从小到大的顺序，依次存储每一列的元素
2. 以行序为主（先行后序）：按照列号从小到大的顺序，依次存储每一行的元素

列序为主的存储方式如图：

行序为主的存储方式如图：

在C/C++语言、Java语言中，一般都是以行序为主的顺序存储方式。

4.2.2 多维数组如何查找指定元素

当需要在顺序存储的多维数组中查找某个指定元素时，需知道以下信息：

• 多维数组的存储方式；
• 多维数组在内存中存放的起始地址；
• 该指定元素在原多维数组的坐标（比如说，二维数组中是通过行标和列标来表明数据元素的具体位置的）；
• 数组中数组的具体类型，即数组中单个数据元素所占内存的大小，通常用字母 L 表示；

根据存储方式的不同，查找目标元素的方式也不同。如果二维数组采用以行序为主的方式，则在二维数组 a_nm 中查找 a_ij 存放位置的公式为：

LOC(i,j) = LOC(0,0) + (i*m + j) * L;

其中，LOC(i,j) 为 a_ij 在内存中的地址，LOC(0,0) 为二维数组在内存中存放的起始位置（也就是 a₀₀ 的位置）。

而如果采用以列存储的方式，在 anm 中查找 aij 的方式为：

LOC(i,j) = LOC(0,0) + (i*n + j) * L;

4.2.3 矩阵的三种压缩方式

在实际应用中，经常会遇到一些特殊的矩阵（即有一定规律的矩阵）。而我们可以利用其规律或者特点来进行存储优化，提升存储效率。

这些特殊的矩阵主要分为两种：

• 含有大量相同的元素的矩阵，如对称矩阵
• 含有大量的0元素的矩阵（在实际应用中，也可能含大量其他相同元素），如稀疏矩阵、上/下三角矩阵

对这种特殊矩阵，我们的压缩存储的思路就是，重复的尽量只存一次，节约存储空间。

对称矩阵

上图矩阵中，数据元素沿主对角线对应相等，这类矩阵称为对称矩阵。即 a_ij = a_ji (1 ≤ i,j ≤ n)，成为n阶对称矩阵。

矩阵中有两条对角线，其中图 1 中的对角线称为主对角线，另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。

结合数据结构压缩存储的思想，我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等，因此数组中只需存储对角线一侧（包含对角线）的数据即可。

对称矩阵的实现过程是，若存储下三角中的元素，只需将各元素所在的行标 i 和列标 j 代入下面的公式：

最终求得的 k 值即为该元素存储到数组中的位置（矩阵中元素的行标和列标都从 1 开始）。

上（下）三角矩阵

如图所示，即为上三角和下三角矩阵

对于这类特殊的矩阵，压缩存储的方式是：上（下）三角矩阵采用对称矩阵的方式存储上（下）三角的数据（元素 0 不用存储）

其实也并非元素0不用存储，只不过是约定好了剩下的就是元素0。在特殊情况下是可以适当变通。、

1. 上三角矩阵

   sa[k] 和 矩阵元a_ij之间的对应关系为

   

2. 上三角矩阵

   sa[k] 和 矩阵元a_ij之间的对应关系为

   

对角矩阵

如图，即为对角矩阵

这种矩阵的规律分厂简单，对角线上的元素 a_ij 特征都是 i=j 。显而易见，可以将其压缩为一个一维数组。

sa[k] 和 矩阵元a_ij之间的对应关系为 k=i=j

稀疏矩阵

通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵。形如下图：

压缩存储稀疏矩阵的方法是：只存储矩阵中的非 0 元素。稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。

例如存储上图中的矩阵：

• (5,5,2) : 存储此系数矩阵的大小
• (3,2,1) : 在矩阵位置为(3,2)上存储的数据是 1
• (4,4,2) : 在矩阵位置为(4,4)上存储的数据是 2

这样就可以存储一个完整的稀疏矩阵了。

在严蔚敏版本的《数据结构》教材中，并未对压缩矩阵的实现方法以及稀疏矩阵的压缩存储方法进行详细描述。在此先不做详解，日后再补上~

4.3 关于广义表

之前学过的数组，即可以存储不可再分的数据元素（如数字 5、字符 ‘a’），也可以继续存储数组（即 n 维数组）。但是同一数组存储两种数据，如{3,5,{1,3,6}}，虽然可以通过二维数组来实现，但是会造成大量的存储空间浪费。而对于这种数据，有一个更好的存储方案，那就时使用广义表。

4.3.1 广义表的定义

广义表，又称列表，也是一种线性存储结构。

同数组类似，广义表中既可以存储不可再分的元素，也可以存储广义表，记作：

LS = (a₁,a₂,…,a_n)

其中，LS 代表广义表的名称，a_n 表示广义表存储的数据。广义表中每个 a_i 既可以代表单个元素，也可以代表另一个广义表。

通常，广义表中存储的单个元素称为 “原子”，而存储的广义表称为 “子表”。

广义表存储数据的常用形式有：

• A = ()：A 表示一个广义表，称其为空表。
• B = (e)：广义表 B 中只有一个原子 e。
• C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
• D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。
• E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

注：A = () 和 A = (()) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。

4.3.2 广义表的表头和表尾

当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。

注意：广义表的表尾一定是一个广义表。

4.3.3 广义表的存储结构

由于广义表中的数据元素可以有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构。

tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1。

子表节点中的 hp 指针用于连接本子表中存储的原子或子表，tp 指针用于连接广义表中下一个原子或子表。

广义表头尾链表

广义表头尾链表的存储结构

typedef struct GLNode{int tag;				//标志域union{char atom;			//原子结点的值域struct{struct GLNode * hp,*tp;}ptr;				//子表结点的指针域，hp指向表头；tp指向表尾};
}*Glist;

这里用到了 union 共用体，因为同一时间此节点不是原子节点就是子表节点，当表示原子节点时，就使用 atom 变量；反之则使用 ptr 结构体。

例如，广义表 {a,{b,c,d}} 是由一个原子 a 和子表 {b,c,d} 构成，而子表 {b,c,d} 又是由原子 b、c 和 d 构成，用链表存储该广义表如图：

可见，存储原子 a、b、c、d 时都是用子表包裹着表示的，因为原子 a 和子表 {b,c,d} 在广义表中同属一级，而原子 b、c、d 也同属一级。

举例如下：

​ 广义表G1

针对以上例子，使用此种表示法的存储结构如下图所示：

扩展线性链表

如图所示，表示原子的节点构成由 tag 标记位、原子值和 tp 指针构成，表示子表的节点还是由 tag 标记位、hp 指针和 tp 指针构成。

扩展线性链表的存储结构

typedef struct GLNode{int tag;					//标志域union{int atom;				//原子结点的值域struct GLNode *hp;		//子表结点的指针域，hp指向表头};struct GLNode * tp;			//这里的tp相当于链表的next指针，用于指向下一个数据元素
}*Glist;

举例如下：

​

​ 广义表G2

针对以上例子，使用此种表示法的存储结构如下图所示：

对于广义表的长度、深度的计算，在严蔚敏版本《数据结构》中，没有详细讲解，暂时先不做整理，之后再补。