4.1 串

4.1.1 定义

串(string)：由零个或任意字符组成的有限数列

子串：串中任意连续字符组成的子序列（含空串）称为该串的子串

真子串：不包含自身的所有子串

主串：包含子串的串相应地称为主串

字符位置：字符在序列中的序号为该字符在串中的位置

子串位置：子串第一个字符在主串中的位置

空格串：由一个或多个空格组成的串，与空串不同

串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同，这两个串才是相等的

如：“abcd”≠ “abc”

所有空串是相等的

4.1.2 案例引入

串的引用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑、符号处理、各种信息处理系统等等

病毒感染检测

• 研究者将人的DNA和病毒的DNA均表示成一些字母组成的字符串序列
• 然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染
• 例如：假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染；患者2的DNA序列为babbaa，则未感染

（注意，人的DNA序列是线性的，而病毒的DNA序列是环状的）

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

顺序存储

#define MAXSTRINGSIZE 255

typedef struct {
	char ch[MAXSTRINGSIZE + 1];		// 存储串的一维数组
	int length;						// 串的当前长度
}mystring;

链式存储

链式存储结构和链表一样

下面这种结构称为：块链结构

#define MAXBLOCKLINKSTRINGSIZE 80

typedef struct BlockLinkString {
	char ch[MAXBLOCKLINKSTRINGSIZE];		// 存储串的一维数组
	struct BlockLinkString* next;			// 指向下一个块的指针
}Block;


typedef struct {
	Block* head;		// 指向串的头块
	Block* tail;		// 指向串的尾块
	int length;			// 串的当前长度
}blockLinkString;

模式匹配算法

算法目的：确定主串中所含子串（模式串）第一次出现的位置（定位）

算法应用：搜索引擎、拼写检查、语言翻译、数据压缩

算法种类：

• BF(Brute-Force)，又称古典的、经典的、朴素的、穷举的
• KMP算法（特点：速度快）

BF算法

算法思路：

1. 将主串的第pos个字符和模式串的第一个字符比较

1. 若相等，继续逐个比较后续字符
2. 若不等，从主串的下一个字符起，重新与模式串的第一个字符比较

2. 直到主串的一个连续子串字符序列与模式串相等。返回值与S中T匹配的子序列第一个字符的序号，即匹配成功。
3. 否则，匹配失败，返回值 0

/*******************************************************************************************************************************
 * @description：BF算法
 * @param：S	主串
 * @param：T	子串
 * @param：pos	开始位置
 * @return：	匹配成功返回1；否则返回0
 */
int index_BF(mystring S, mystring T, int pos)
{
	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;	// 回溯
			j = 1;
		}
	}
	if (j > T.length)	// 匹配成功
		return i - T.length;
	else
		return 0;
}

时间复杂度：O(n*m)

KMP算法

利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针I不必回溯，可提速到O(n+m)

因此需要一个next[j]数组，表明当模式中第j个字符与主串中相应字符“失败”时，在模式中需要重新和主串中该字符进行比较的字符的位置

例如：

next函数的改进

if(pattern[j] == pattern[i]){
    next[i] = j+1;
    i++;
    j++;
}
else{
    next[i] = j-1;
    j++;
    i++;
}

/*******************************************************************************************************************************
 * @description：构造next数组
 * @param：T	模式串
 * @param：next
 */
static void get_next(mystring T, int 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;
			if (T.ch[i] != T.ch[j])
				next[i] = j;
			else
				next[i] = next[j];
		}
		else
			j = next[j];
	}
}





/*******************************************************************************************************************************
 * @description：KMP算法
 * @param：S	主串
 * @param：T	模式串
 * @param：pos	开始位置
 * @return：
 */
int index_KMP(mystring S, mystring T, int pos)
{
	int i = pos;
	int j = 1;
	int next[255];
	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;
}

测试代码

void StringMain()
{
	mystring S = { ' ', 'a','a','a','b','a','a','a','a','b' };		// 主串，第一个位置不用
	S.length = 9;
	mystring T = { ' ','a','a','a','a' };							// 模式串，第一个位置不用
	T.length = 4;
	printf("主串：");
	printString(S);
	printf("\n模式串：");
	printString(T);

	// 测试BF算法
	int pos = index_BF(S, T, 1);
	if (pos)
		printf("\nBF算法：匹配成功，位置为：%d\n\n", pos);
	else
		printf("\nBF算法：匹配失败\n\n");

	// 测试KMP算法
	pos = index_KMP(S, T, 1);
	if (pos)
		printf("\nKMP算法：匹配成功，位置为：%d\n", pos);
	else
		printf("\nKMP算法：匹配失败\n");

}

4.2 数组

数组：按一定格式排列起来的具有相同类型的数据元素的集合

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组

一维数组的逻辑结构：线性结构。定长的线性表

声明格式：数据类型 变量名称[长度];

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。

二维数组的逻辑结构：

• 非线性结构：每一个数据元素即在一个行表中，又在一个列表中
• 线性结构：该线性表的每个数据元素也是一个定长的线性表

数组特点：结构固定-定义后，维数和维界不再改变

数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作

4.2.1 抽象数据类型定义

二维数组存储方式：

• 以行序为主序：C、PASCAL、JAVA、Basic

• 以列序为主序：FORTRAN

4.2.2 特殊矩阵的压缩存储

什么时压缩存储？

为多个相同的非零元素只分配一个存储空间；对零元素不分配空间

什么样的矩阵能够压缩？

一些特殊矩阵：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等

什么叫稀疏矩阵？

矩阵中非零元素的个数较少（一般小于5%）

对称矩阵

三角矩阵

对角矩阵

稀疏矩阵

三元组

十字链表

例如：

4.3 广义表

4.3.1 定义

广义表（又称列表Lists）是n≥0个元素 a0，a1，... ，a(n-1)的有限序列，其中每一个ai或者是原子，或者是一个广义表

例如：

广义表的性质：

1. 广义表中的数据元素有相对次序；一个直接前驱和一个直接后继
2. 广义表的长度定义为最外层所包含元素的个数；如：C = (a，(b, c))是长度为2的广义表
3. 广义表的深度定义为该广义表展开后所含括号的重数；A = (b, c)的深度为1，B = (A, b)的深度为2，C = (f, B, h)的深度为3 注意：“原子”的深度为 0；“空表”的深度为 1
4. 广义表可以为其它广义表共享；如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用，B = （A）
5. 广义表可以是一个递归的表，如 F = (a, F=(a, (a, (a, ...)))) 注意：递归表的深度是无穷值，长度是有限值
6. 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表

4.3.2 基本运算

1. 求表头GetHead(L)：非空广义表的第一个元素，可以是一个原子也可以是一个子表
2. 求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表