408数据结构-串的基本概念 自学知识点整理

前置知识：单链表

---

串

字符串简称 串 ，计算机上非数值处理的对象基本上都是字符串数据。
串（string）是由零个或多个字符组成的有限序列。
串中字符数$n$被称为串的长度，当$n=0$时，串为 空串 。需要注意的是，由一个或多个空格组成的字符串被称为 空格串 ，它并不是空串，其长度为串中空格字符的个数。
串中任意多个连续的字符组成的子序列成为该串的子串，包含子串的串称为主串。
串的逻辑结构与线性表极其类似，区别仅在于串的数据对象限定为字符集。此外，对线性表的基本操作（增删查改）多是以单个数据元素为对象，而串的基本操作通常以子串作为操作对象。

串的存储结构

1. 定长顺序存储表示

#define MaxLen 259//预定义最大串长，致敬传奇指挥259
typedef struct {//静态数组存储
	char ch[MaxLen];//字符数组储存串
	int length;//串长
}SString;
1
2
3
4
5

2. 堆分配存储表示

typedef struct {//动态数组实现
	char* ch;//按串长分配存储区，ch指向串的基地址
	int length;
}HString;//（堆分配存储）
1
2
3
4

3. 块链存储表示

typedef struct LNode {//串的链式存储
//	char ch;//每个结点存一个字符，占用1B，存储密度低（狗都不用
	char ch[4];//解决方案，每个结点存多个字符，提高存储密度
	struct LNode* next;//每个结点存一个指针，占用4B
}LNode, * String;
1
2
3
4
5

串的基本操作

因为定长顺序（静态数组）存储表示法书写代码较为简便，故使用之。若对堆分配（动态分配）存储表示有需求可参考这篇博客：数据结构笔记（十三）-- 串的堆分配存储表示
初始化，判空，求串长，清空，销毁：

void InitString(SString& S) {//初始化
	S.length = 0;
	return;
}

bool StrEmpty(SString S) {//判空
	return S.length == 0 ? true : false;
}

int StrLength(SString S) {//求串长
	return S.length;
}

void ClearString(HString& S) {//清空（静态分配和动态分配逻辑相同）
	S.length = 0;
	return;
}

void DestoryString(HString& S) {//销毁（仅动态分配）
	free(S.ch);
	S.ch = NULL;//下面两行的逻辑与动态分配的串初始化逻辑相同
	S.length = 0;
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

注意：有一部分函数无需对串作引用，只需传入参数即可。

另外就是下面的代码都是我根据王道考研408数据结构的B站视频讲解，自己手打的，不一定正确，仅供参考，欢迎指出问题。
赋值：

void StrAssign(SString& S, char c[]) {//赋值
	InitString(S);//初始化串S防止其内部残留“脏数据”
	int len = strlen(c)-1;
	//因为采用字符数组传参，需要对其长度-1，排除数组下标为0的数据干扰
	if (len == 0)return;//如果传入的是空串，则无需操作
	else S.length = len;//否则将串长更改为len
	for (int i = 1; i <= len; ++i)
		S.ch[i] = c[i];//按位传入字符串
	return;
}
/*
void StrAssign(HString& S, char *chars) {//动态分配的做法如下
	DestoryString(S);
	int len = strlen(chars);
	if (len == 0)return;
	else S.length = len;
	S.ch = (char*)malloc(len * sizeof(char));
	for (int i = 0; i < len; ++i)
		S.ch[i] = chars[i];
	return;
}
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复制：没什么好说的，直接替换。

void StrCopy(SString& S, SString& T) {//复制
	S.length = T.length;
	for (int i = 1; i <= T.length; ++i)
		S.ch[i] = T.ch[i];
	return;
}
1
2
3
4
5
6

串联接：

void Contact(SString& S, char T1[], char T2[]) {//串联接，用S返回T1,T2拼接成的新串
	int len1 = strlen(T1) - 1, len2 = strlen(T2) - 1, i;
	//len1表示T1串长，len2表示T2串长，i表示联接串数组下标
	for (i = 1; i <= len1; ++i)
		S.ch[i] = T1[i];//先复制T1串
	for (int j = 1; j <= len2; ++i, ++j)
		S.ch[i] = T2[j];//再在其后复制T2串
	S.length = len1 + len2;//新串的长度等于两串长度和
	return;
}
1
2
3
4
5
6
7
8
9
10

求子串：

bool SubString(SString& Sub, SString S, int pos, int len) {
	//查找S串中，在pos位置开始，长度为len的子串，并用Sub返回
	if (pos + len - 1 > S.length)return false;//如果子串位置和长度非法直接返回false
	for (int i = pos; i < pos + len; ++i)//从pos处开始，到pos+len-1处结束 
		Sub.ch[i - pos + 1] = S.ch[i];
	Sub.length = len;//子串长度就是len
	return true;
}
1
2
3
4
5
6
7
8

比较两串大小：

int StrCompare(SString S, SString T) {//比较串大小
	//若S串＞T串，返回值＞0；若S串=T串，返回值=0；若S串＜T串，返回值＜0
	for (int i = 1; i <= S.length && i <= T.length; ++i)
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	return S.length - T.length;//长的串值更大
}
1
2
3
4
5
6
7

查询子串T在主串S中的位置：

int Index(SString S, SString T) {//查询子串T在主串S中的位置
	SString Sub;//临时子串Sub
	for (int i = 1; i <= S.length - T.length + 1; ++i) {
		SubString(Sub, S, i, T.length);//从位置1开始查找，并用Sub临时存放子串
		if (StrCompare(Sub, T) != 0)continue;//比较Sub和T，如果不同则继续循环
		else return i;//否则返回i，即T在S中第一次出现的位置
	}
	return 0;//若未找到则返回0
}
1
2
3
4
5
6
7
8
9

---

串的模式匹配——朴素模式

（关于KMP算法及其优化，我会单独开一篇博客写）
子串的定位操作通常被称为串的模式匹配。它求的是模式串（与子串不同，因为它不一定出现在主串里）在主串中的位置，若不存在返回0。
其实具体实现上面的查询已经有了，以下是不使用基本操作函数，直接使用数组下标实现的代码：

int INdex(SString S, SString T) {//朴素模式匹配算法
	//S为主串，T为模式串，查找T在S中第一次出现的起始位置，若无匹配返回0
	int i = 1, j = 1;//i为主串的指针，j为模式串指针
	for (; i <= S.length && j <= T.length; ++i, ++j) {
		if (S.ch[i] == T.ch[j])continue;//若当前位匹配则继续匹配下一位
		else {//若不匹配
			i = i - j + 2;//i指针往后退到起始位置的下一位
			j = 1;//j指针恢复到模式串第一位
		}
	}
	if (j > T.length)return i - T.length;//如果j大于模式串长度则代表匹配成功，返回i-模式串长度
	else return 0;//否则匹配失败，返回0
}//若主串长度为n，模式串长度为m，最坏的时间复杂度为O(nm)
1
2
3
4
5
6
7
8
9
10
11
12
13

本文的完整代码也可到我的Github看：传送门

关于（字符）串的基本概念就这些，理解起来并不难，主要还是对字符类型数组的操作与数字类型的操作写法上会有一些不同，需要特别注意语法方面的问题。
以上。