数据结构入门4-1（串、数组）

目录

注

串的定义

串的类型定义、存储结构及其运算

串的抽象类型定义

串的存储结构

1. 串的顺序存储

2. 串的链式存储

串的模式匹配算法（定长存储结构下）

1. BF算法

2 - 1. KMP算法 - 分析部分

2 - 2. KMP算法 - 代码部分

数组

数组的类型定义

数组的顺序存储

数组的存储结构（以行序为主序举例）

特殊矩阵的压缩存储

1. 对称矩阵

2. 三角矩阵

3. 对角矩阵

---

注

        本笔记主要参考《数据结构（C语言版）》

---

  字符串数据是计算机上的一种非数值处理的对象，字符串简称为串。

        串 是一种特殊的线性表，其特殊性在于：其数据元素是一个字符 。所以，串是一种内容受限的线性表。因为字符串数据处理复杂，为了有效处理字符串，就需要设计合适的存储结构。

串的定义

        串（string），又称字符串，是由零个或者多个字符组成的有限序列，一般记为：

一些概念：

1. 子串：串中任意连续的字符组成的子序列；
2. 主串：包含子串的串；
3. 通常将字符在序列中的序号称为该字符在串中的位置（子串在主串中的位置则以字符的第一个字符在主串中的位置来表示）。
4. 特殊的串：
   1. 空串：包含零个字符（长度为 0）的串，用符号“∅”表示；
   2. 空格串：由一个或多个空格（" "）组成的串。

例如：

        假设a、b、c、d四个串：

        其中：

• a、b分别是c 和 d的子串；
• a 在c 和 d中的位置都是 1；
• b 在c 中的位置是 4，在d 中的位置是 5。

        串相等的情况：当两个串的长度相等，并且各个对应位置的字符都相等时才相等。

串的类型定义、存储结构及其运算

串的抽象类型定义

        串的逻辑结构与线性表相似，区别仅在于串的数据对象为字符的集合。

        但是，串的基本操作却不同于线性表，因为线性表往往是针对 “单个元素” 进行操作，而串却要以 “串的整体” 作为操作对象。

        串的抽象数据类型定义：

串的存储结构

        串也存在着两种基本结构：顺序存储 和 链式存储（不过顺序存储因为存储效率高、算法较为方便，更受欢迎）。

1. 串的顺序存储

        类似于线性表，串也使用一组地址连续的存储单元存储串值的字符序列。

 串的定长顺序存储结构：

#define MAXLEN 255			//串的最大长度
 
typedef struct 
{
	char ch[MAXLEN + 1];	//使用一维数组存储串
	int length;				//记录串的当前长度
}SString;

        这种定义方式在编译时就确定了串空间的大小。但是，在多数情况下，串的操作是以串的整体形式作为对象，而串变量之间的长度往往相差很大，这就会导致（栈区）空间的浪费。

        相比于上述这种声明方式，在程序运行阶段进行空间的分配就更加合理，即在 堆区（Heap） 进行空间的动态开辟。

串的堆式顺序存储结构：

typedef struct {
	char* ch;		//若是非空串，则按串长分配存储区，否则ch为空指针（NULL）
	int length;		//串的当前长度
}HString;

---

2. 串的链式存储

        顺序串的插入和删除操作存在不便，为此，可能需要移动大量的字符。为了处理该问题，可采用单链表的方式存储串。

        由于串结构的特殊性（即结构中的每个元素都是一个字符），在实际通过链表存储串的值时，存在“节点大小”的问题：在一个节点中可以存储一个字符，或者存储多个字符。

（除了上述出现的头指针外，还可以设置尾指针指向链表的最后一个节点。）

串的链式存储结构：

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

        一般而言，在链式存储结构中，需要考虑：

1. 串值的存储密度（节点大小）。若节点大小是1，则运算处理方便，但相对的，存储占用量就会大；
2. 串的字符集的大小。字符集小，则字符的机内编码就短，则会影响存储方式的选择。

        串值的链式存储结构在一些特定的操作（如联接操作）中，会较为方便，但总体而言，占用存储量大，操作复杂，不如顺序存储结构灵活。

串的模式匹配算法（定长存储结构下）

        子串的定位运算通常被称为串的模式匹配或者串匹配。通常，串的模式匹配设有两个字符串S和T：

• S为主串，也称为正文串；
• T为子串，也称为模式。

        在主串S中查找与子串T匹配的子串，如果匹配成功，则返回子串的第一个字符在主串S中出现的位置。

        接下来介绍较为著名的模式匹配算法。

1. BF算法

||| BF（Brute-Force）算法，优点：简单直观。

【代码】

  前置条件：① T非空，② 1 ≤ pos ≤ S.length 。

  为了方便描述算法，规定：数组的存储从下标为[1]处开始，下标为[0]处闲置。

int Index_BF(SString S, SString T, int pos)
{//返回T在S中第pos个字符开始，第一次出现的位置。若不存在，返回值为0
	int i = pos;
	int j = 1;
 
	while (i <= S.length && j <= T.length)	//比较，直至两个串均比较到末尾
	{
		if (S.ch[i] == T.ch[j])
		{
			++i;
			++j;
		}					//若当前字符相等，继续比较下面的字符
		else
		{
			i = i - j + 2;	//数组从下标为[1]处开始比较，故此处 +2
			j = 1;
		}					//若当前字符不相等，则指针后退继续比较
	}
 
	if (i > T.length)		//若匹配成功
		return i - T.length;
	else
		return 0;
}

  上述函数使用的是字符串的顺序存储结构，所以可以不用调用其他串操作的函数。

【分析】

        BF算法较好理解：将模式T内的字符与主串S中的字符一一比较，若比较失败（出现某个字符无法匹配的情况），则将主串S中的下一个字符作为开头，重新进行比较。

        一般来讲，BF算法会有两种极端情况：

        （1）最好的情况：每趟不成功的匹配都发生在模式串T的第一个字符与主串S中相应字符的比较。

        若设主串S的长度为n，模式T的长度为m。且：

1. 在第一次比较成功前，匹配失败的次数为：i - 1；
2. 在第 i 次比较时，成功匹配；

        那么总的比较次数将会是 i - 1 + m 。

        一般而言，对时间复杂度的判断参考的是平均时间复杂度。而在上述条件下，只有pos（即比较中主串的起始位置）是未知的，也就是说，为了得到平均时间复杂度，需要考虑pos所有的取值。

        而pos的取值并不难以判断，从主串和子串的长度可知：1 ≤ pos ≤ n - m + 1。假定在这 n - m + 1 个主串的起始位置上匹配成功的概率相等，则在最好的情况下，匹配成功的平均比较次数为

故此时的平均时间复杂度为O(n + m)。

---

        （2）最坏的情况：每趟不成功的匹配都发生在模式串的最后一个字符与住主串中相应字符的比较。

        依旧和上面一样，设主串S的长度为n，模式T的长度为m。且：

1. 在子串与主串成功匹配之前，共进行了 i - 1 趟匹配；
2. 每次匹配比较m个字符；
3. 第 i 次匹配时子串匹配成功。

        因为第 i 次匹配成功时也进行了 m 次比较，故总的比较次数为 i × m 。因为pos的取值范围不变（依旧是1 ≤ pos ≤ n - m + 1），所以在最坏的情况下，匹配成功的平均比较次数为

故此时的平均时间复杂度为O(n × m)。

        由上述可知，BF算法的优点是直观简明，而缺点是时间复杂度较高且不稳定。相比之下，下面的KMP算法的时间复杂度就较低。

2 - 1. KMP算法 - 分析部分

算法主体部分

        该算法的名称来自三位设计了该算法的前辈。此算法可以在O(n + m)的时间量级上完成串的模式匹配操作。比起BF算法，KMP算法更加接近人在处理串匹配时的情况：

假设存在主串S与子串T，并存在指针 s 和 t 分别指向两个串。

        请尝试思考，如果要求我们从头开始寻找S中出现的第一个T，应该怎么做？

1. 首先是第一个字符'A'相同；
2. 然后是第二个字符'B'相同；
3. 那么再然后呢？

        当我们发现了无法匹配的字符'A'与'C'，我们仅需要回溯子串T的指针 t ，直到指针t指向合适的位置，就可以进行再一次的匹配：

        这就是这种模式匹配的基本思路了。当然，上述讲述的部分还未涉及该算法最难懂的部分，如果仔细观察上述推导中的子串，能够发现：上述子串中的字符是不重复的。如果这样考虑算法，显然是不充分的。

        为什么呢？假设：

        在上述这种子串中，"X"重复了两次（即 T 包括了两个相同的子串"X"）。当该主串和子串发生第一次匹配失败时，情况应该是：

        现在存在的问题是：指针t应该回溯到哪个位置？从上帝视角可以轻易发现，如果把指针t往回回溯2个元素，S 和 T 就会匹配：

        但在真实操作中，计算机无法通过“观察”这种方式发现指针t的移动方式。为了达到这种效果，就需要为计算机设计相应的算法。由此，就引出了主串T的next函数。

函数get_next( )部分

||| get_next函数（用以获得next值的函数）的定义：

------

        在接触该函数前，需要先理解该函数的运行思路。假设主串S和子串T：

        此时，按照上面的理解，我们如果将T向右移动 5个元素 ，就可以直接完成子串与主串的匹配，但这要怎么告诉计算机？

        为了达成目的，可以近似地认为：子串T除了下标之外，还存在名为next值的属性，这个属性对应的就是子串T的指针需要移动到的位置。而程序就是通过next值寻找到目标字符的。

• 对上述 T 的第二个字符'A'而言，其对应的next值就是 1，即第一个字符'A'所在的位置；
• 对第三个字符'A'而言，其对应第二个字符'A'所在的位置；
• ……

（注意：此处next值其实存在可优化空间，但当前并不要紧。这些问题会在最后进行讨论。）

        以此类推，可以得到前几个字符的next值：

        如果就这样往下推，就会发现一个问题，字符'C'该何去何从？

        当字符'B'处发生比较失败，可以说：因为在此之前没有字符'B'的存在，所以T应该向前一个元素，找到与'B'不同的最近的'A'。但同样的逻辑却不能适用于当前的字符'C'，因为'C'之前并不存在相同的子串。

  其实，上述的字符'B'的next值之所以是3，不仅仅是因为字符'B'当前的唯一性，也因为在'B'之前存在着相同的子串"AA"。

         现在，回到更早之前的问题：

        在KMP算法中，区分一个字符依靠的不仅仅是该字符本身，更重要的是其之前的子串。在上述的移动中，认为之所以能够移动到目标位置，依靠的是其之前已经完成识别的相同子串。因此，上述的移动才能成立。

       而 "AAABC" 中的字符'C'，因为其之前没有相同子串，所以next值只能被设置为1，即回到 T 的开头，进行重新寻找。

------

||| next[ ]的定义：

• k的定义：发生匹配失败时，子串中重新进行匹配的字符位置。

||| next[ j ]：

• j 的定义：（匹配失败发生时）当前子串T中进行匹配的字符的位置；
• next的功能：表明当匹配失败发生时，子串T中重新和主串S进行匹配的字符的位置。

        但next函数的功能要如何实现呢？假设：

1. 主串长度为 n ；
2. 子串长度为 m；
3. 发生匹配失败时，子串中重新进行匹配的字符位置为 k （k < j）。

        在上图中，存在着如下的关系式：

        由上可知，当形如子串T的状况出现时，仅需将子串向右移动直至 主串的第i个字符 与 子串的第k个字符 对齐。此时，子串的前 k - 1 个字符的子串 和 子串中第i个字符之前的长度为 k - 1 的子串 相等。

        此时可能存在两种情况：

此时存在 next[ j  + 1 ] = k + 1 ，即

---

        此时求next值的问题就是一个模式匹配的问题，T 即是主串，又是子串，而字符'B'就是需要被匹配的字符（即在 T 中寻找能够与 下标为j 的字符'B'相匹配的字符）。而在此之前，已经得出结论：

        现在的问题是：既然 k 对应位置上的字符已经比较失败，那么接下来应该匹配哪个字符？

        答案是将 next[ k ] 上的字符与 j 上的字符"B"进行比较（因为在位置 j 之前的所有字符已经拥有了它们的 next[] 值，可以直接使用）。

① 若比较成功，类似于：

        此时存在 next[ j + 1] = k' + 1，即

② 若匹配没有成功，这需要继续寻找位置在 next[ k' ] 上的字符，直到匹配成功 或者 无法找到匹配字符 ，当后者发生时，有：

  通过上述记叙方式，可以得到：

2 - 2. KMP算法 - 代码部分

所使用串的结构：

#define MAXLEN 255			//串的最大长度
 
typedef struct
{
	char ch[MAXLEN + 1];	//使用一维数组存储串
	int length;				//记录串的当前长度
}SString;

函数 Index-KMP( )

int Index_KMP(SString S, SString T, int pos)
{//利用子串T的get_next函数求出T在主串S中第pos个字符之后的位置
 //（T非空，1 ≤ pos ≤ S.length）
	int i = pos;
	int j = 1;
 
	int next[100] = { 0 };					//类型及大小可以自行定义，此处进行简单处理
	get_next(T, next);
 
	while (i <= S.length && j <= T.length)	//当两个串均比较到串尾（实际上此处多移动一位，是为了后面方便计算）
	{
		if (j == 0 || S.ch[i] == T.ch[j])	//当前字符匹配成功
		{
			++i;
			++j;							//指针向后移动
		}
		else
			j = next[j];					//寻找新的字符进行匹配
	}
 
	if (j >= T.length)						//匹配成功（判断条件会因为使用的串的结构不同而发生变化）
		return i - T.length;
	else									//匹配失败
		return 0;
}

---

函数 get_next( )

void get_next(SString T, int next[])
{//求模式串T的next函数值并存入数组next
	int i = 1;
	int j = 0;
	next[1] = 0;
 
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])	//当前字符匹配成功
		{
			++i;
			++j;							//向后移动指针
			next[i] = j;					//进行相应的next值赋值
		}
		else
			j = next[j];					//寻找新的可匹配字符
	}
}

---

函数get_nextval( ) —— get_next( )的优化

【分析】

        如果仔细思考，就会发现上述定义的next函数是有缺点的。假设：

        如果使用上述的next函数，主串T的next值就会如下所示：

        这意味着为了获得能够与 S当前字符 匹配的字符，需要将T一个元素一个元素地向右移动，每移动一个元素就要比较一次，这很明显是没有必要的（子串T的前4个字符相同，都是字符'A'）。

        为此，就需要更新next函数，使其能够满足：当字符相同时，能够令子串T的向右移动能够直接跳过相同字符，抵达目标位置。即：

例如：

【代码】

void get_nextval(SString T, int nextval[])
{//将子串T的next函数值存入数组nextval中
	int i = 1;
	int j = 0;
	nextval[1] = 0;
 
	while (i < T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j])
		{
			++i;
			++j;
			if (T.ch[i] != T.ch[j])		//当前比较的两个字符不同时
				nextval[i] = j;
			else
				nextval[i] = nextval[j];
		}
		else
			j = nextval[j];
	}
}

数组

数组的类型定义

        数组是由相同的数据元素构成的有序集合，其中：

• 数组元素：每个元素都被称为一个数组元素（受到 n 个线性关系的约束（n ≥ 1））；
• 下标：每个元素在n个线性关系中的序号（可以通过下标进行数组元素的访问）。

        元素处在 n个关系中的数组 被称为 n维数组 。如果把数组看作是线性表的一种推广，那么这种线性表中的每一个元素都可以被看作是 具有某种结构的数据 ，且属于同种数据类型。

例如：尝试将一个二维数组化为一个线性表

① 如果选择将二维数组通过列向量化为线性表：

② 如果选择将二维数组通过行向量化为线性表：

------

        由上述例子可知，一个二维数组可以被拆分为两个由其分量类型定义的 一维数组 类型：

        同理，一个n维数组可以被拆分为一个 n-1维数组 和一个 一维数组 类型。

        由于数组在初始化时进行的声明已经固定了数组的形式，因此在数组定义完毕后，其维数和维界都无法被改变。因此，数组的操作包括：

① 初始化；

② 销毁；

③ 存取元素；

④ 修改元素值。

        抽象数据类型数组的定义（来自《数据结构（C语言版）》）：

【解释】 （参考19991215的博客）

        既然该数据类型是对于数组而言，那么其的数据对象毫无疑问就是一个 n维数组 。设：存在 二维数组A ，有：

        其中：

        由上图可以轻松得知二维数组中的每一个数组元素（除第一个和最后一个）都存在一个直接后驱与直接前驱：

        若把上述假设扩展到n维数组：

        即可得知：

数组的顺序存储

        由于在数组定义完成后，数据元素个数和元素之间的关系不再变动。所以，使用顺序存储结构表示较为合适。

        因为存储单元是一维结构，在对多维的数组结构进行存储时，就会存在存放数据的次序约定问题。打个比方，就类似于上述的二维数组，它可以根据依据的是行向量或者列向量的不同，变化成两个截然不同的一维数组。

        由上图可知，二维数组可以通过两种不同的方式进行存储：

• 以 列序 为主序的存储方式；
• 以 行序 为主序的存储方式。

  因此，在不同的语言中，对于数组的存储方式其实也是不同的。比如C语言选择了以行序为主序，而FORTRAN语言选择了列序。

        同时，通过上述结论可以得知，如果要定义一个数组，需要拥有的数据是：

1. 维数；
2. 各维的长度。

数组的存储结构（以行序为主序举例）

        首先，给定一个二维数组A，其中：每个数组元素占有L个存储单元。要求表示出其中的每一个元素：

||| 先给出公式1：

        再进行分类讨论，设二维数组A[0.. m-1, 0.. n-1]（下标从0开始，有m行n列）：

||| 再把公式1推广到一般情况，即 n维数组 的数据元素存储位置的计算公式：

        将上述公式缩写，可得 n维数组的映像函数 ：

  由此可知，数组元素的存储位置是一个关于下标的线性函数。

        因为计算 数组中各个元素存储位置 都是通过同一个线性函数完成的，即所消耗的时间是相同的，所以存取数组中任一元素的时间也是相等的。因此，数组是一种随机存取结构。

特殊矩阵的压缩存储

        所谓的压缩存储，指的是为多个值相同的元分配一个存储空间，对零元不分配空间。

  在数值分析问题中，可能会出现如下的情况：

1. 阶数很高的矩阵；
2. 一个矩阵中存在很多值相同的元素或者零元素。

  这些情况会浪费存储空间，压缩存储的方式可以解决这个问题。

        特殊矩阵（线性代数知识）：指 相同元素 或者 零元素 在矩阵中的分布具有一定规律的矩阵。它包括：

• 对称矩阵；
• 三角矩阵；
• 对角矩阵；
• ……

        接下来将讨论上述提到的三种特殊矩阵的压缩存储。

1. 对称矩阵

        n阶对称矩阵（是方形矩阵）满足以下性质：

        因为其对称的性质，对于对称矩阵，有这样的处理思路：

1. 为每一对对称的元分配一个存储空间；
2. 将所有的元（共n²个）压缩存储到 n(n+1)/2 个元大小的空间内。

        而为了做到这一点，可以使用以行序为主序的存储方式，存储对称矩阵下三角（包括对角线）中的元。

        假设一个一维数组sa[n(n+1)/2] ，现在使用该数组作为矩阵A的存储结构，则 数组sa 和 矩阵A 的元之间存在着对应关系：

        通过上述这种方式进行存储，就实现了由矩阵元的位置到数组下标的转换。称上述的数组sa[n(n+1)/2]为n阶对称矩阵A的压缩存储。

---

2. 三角矩阵

        通过主对角线，可以把三角矩阵分为 上三角矩阵 和 下三角矩阵 两种。形如：

        对三角矩阵的压缩存储：除了和对称矩阵相似地，只存储其上（下）三角中的元素之外，只需多一个空间进行 常数c（或 0）的存储即可。

        类似地，假设一个一维数组sa，使用该数组存储一个n阶三角矩阵：

        （1）对于 上三角矩阵（n是矩阵的维数）

        对于其中的任一元，可以这样表示： 

        对应的计算公式：

---

        （2）对于 下三角矩阵（n是矩阵的维数）

         对于其中的任一元，可以这样表示： 

        对应的计算公式：

---

3. 对角矩阵

        对角矩阵的所有非零元都集中在以主对角线为中心的带状区域内（此处对角矩阵的概念和一些大学学到过的线性代数中的有些区别）：

        例如，存在三对角矩阵：

        此处仅涉猎对该种矩阵的概念。

  除上述矩阵之外，还存在一类矩阵——稀疏矩阵，这类矩阵的特点是非零元比零元少，且分别没有一定规律。此处不进行讨论。