【数据结构】串的基础知识及代码实现

串类型的定义

串（string）【或字符串】是由零个或多个字符组成的有限序列。串中字符的数目称为串的长度。零个字符的串称为空串。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。
串值必须用一对单引号括起来，但单引号本身不属于串，它的作用在于避免与常量名或数的常量混淆。
由一个或多个空格组成的串称为空格串（注意：此处不是空串），它的长度为串中空格字符的个数。
串的数据对象约束为字符集。
在串的基本操作中，通常以“串的整体”作为操作对象。而在线性表的基本操作中，大多以“单个元素”作为操作对象。

串的表示和实现

在大多数非数值处理的程序中，串也以变量的形式出现。

串的抽象数据类型

定义

• StrAssign(&T, chars): 赋值操作。把串T赋值为 chars
• StrCopy(&T, S): 复制操作。由串S复制得到串T。
• StrEmpty(S): 判空操作。若S为空串,则返回TRUE,否则返回 FALSE
• StrCompare(S,T): 比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S
• StrLength(S): 求串长。返回串S的元素个数
• ClearString(&S):将S清为空串
• Concat(&T,S1,S2): 串联接。用T返回由S1和S2联接而成的新串。
• Substring(&Sub,S,pos,1en):求子串。用Sub返回串S的第pos个字符起长度为len的子串。
• Index(S,T,pos): 定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0
• Replace（&S,T,V）：用V替换主串S中出现的所有与T相等的不重叠的子串
• StrInsert(&S,pos,T):在串S的第pos个字符之前插入串T
• StrDelete(&S,pos,len):从串S中删除第pos个字符起长度为len的子串
• Destroystring(&S): 销毁串。将串S销毁

代码实现

//串
#include
#include
#include
#define MAX 20
using namespace std;
 /*void StrCopy(char *T,char *S){
 	int i;
 	 for(i=0;S[i]!='\0';i++)
 	 	T[i]=S[i];
 	T[i]='\0';
 }*/
 	void StrCopy(string &T,string &S){
 		T=S;
	 }
 void StrAssign(string &T,char *S){
 	T=S;
 }
 void ClearString(string &T){
 	for(int i=0;T[i]!='\0';i++)
 		T[i]='\0';
 }
 bool StrEmpty(string S){
 	if(S[0]=='\0')
 		return true;
 	else
 		return false;
 }
 int StrLength(string S){
 	int i=0;
 	while(S[i]!='\0')
 		i++;
 	return i;
 }
 int StrCompare(string S,string T){
 	int i=0;
 	while(S[i]!='\0'&&T[i]!='\0'){
 		if(S[i]>T[i])
 			return 1;
 		else if(S[i]<T[i])
 			return -1;
 		i++;
	 }
	 if(S[i]!='\0')
	 	return 1;
	else if(T[i]!='\0')
		return -1;
	else
		return 0;
 }
 void Concat(string &T,string S1,string S2){
 	T=S1+S2;
 }
 //返回主串中pos位置处长度为len的子串到sub中 
 void SubString(string &sub,string s,int pos,int len){
 	int i=0;
 	for(i=0;i<len;i++){
 		sub[i]=s[pos];
 		pos++;
	 }
	 sub[i+1]='\0';
 }
 int index(string s,string t,int pos){
 	//T为非空串，若主串S中第Pos个字符之后存在与T相等的子串
	 //则返回第一个这样的子串在S中的位置，否则返回0
	 	int n=StrLength(s);
	 	int m=StrLength(t);
	 	string sub;
	 	int i=pos;
		 cout<<"给sub开辟与子串相同的空间\n";
		 cin>>sub; 
		 if(pos>0){
		 	while(i<n-m+1){
		 		SubString(sub,s,i,m);
		 		if(StrCompare(sub,t)!=0)
		 			i++;
		 		else
		 			return i;//返回子串在主串中的位置 
			 }
		 } 
	 return 0;//S中不存在与T相等的子串 
 }
 void StrInsert(string &S,int pos,string T){
 	int n,m,i=0;
 	n=StrLength(T);
 	for(int j=pos;j<pos+n;i++)
 		S[j+n]=S[j];
 	while(i<n){
 		S[pos]=T[i];
 		i++;
 		pos++;
	 }
 }
 //计算S串的长度然后用长度减去要删除的长度+1为后续要前移的元素，
 //然后将后面的元素进行前移操作，再将原来后面的元素置为空即可
 void StrDelete(string &S,int pos,int len){
 	int i,m;
	m=StrLength(S);
	for(i=pos;i<m-len+1;i++)
	{
		S[i]=S[i+len];	
		S[i+len]=' ';		
	}

 }
  //用V替换主串S中出现的所有与T相等的不重叠的子串 
 /*void Replace(string &S,string T,string V){
 	int i,n;
 	i=index(S,T,0);
 	n=StrLength(V);
 	int j=i,k=0;
 	while(k
  void Replace(string &S,string T,string V){
 	int i,n,m;
 	m=StrLength(T);
 	i=index(S,T,0);
 	StrDelete(S,i,m);
 	StrInsert(S,i,V);
 }
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

串的三种机内表示方法

1.定长顺序存储表示
2.堆分配存储表示
3.块链存储表示

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述

//---串的定长顺序存储表示----
#define MAX 255//用户可在255以内定义最大串长
typedef unsigned char SString[MAX+1];//0号单元存放串的长度
1
2
3

串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。
对串长有两种表示方法
1.如上述定义描述的，以下标为0的数组分量存放串的实际长度
2.以’\0’表示串值的终结

堆分配存储表示

特点：仍以一组地址连续的存储单元存放串值字符序列，但存储空间是在程序执行过程中动态分配而得。在C中，存在“堆”区（自由存储区），由动态分配函数malloc()和free()管理。用malloc()分配存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址。

//串的堆分配存储表示
typedef struct(
	char *ch;//若是非空串，则按串长分配存储区，否则为NULL
	int length;//串长度
)HString;
1
2
3
4
5

块链存储表示

类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性(结构中的每个数据元素是一个字符)，在具体实现时，每个结点既可以存放一个字符， 也可以存放多个字符。每个结点称为块，整个链表称为块链结构。
由于串长不一定是节点大小的整数倍，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符。
为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个节点，并给出当前串的长度。

#define size 80 //可由用户定义的块大小
typedef struct CHUNK{
	char ch[size];
	struct CHUNK *next;
}CHUNK;
typedef struct{
	CHUNK *head,*tail;//串的头和尾指针
	int curlen;//串的当前长度
}
1
2
3
4
5
6
7
8
9

设尾指针的目的：便于进行联结操作。（要注意联结时需要处理第一个串尾的无效字符）
串值的链式存储结构对于某些串操作（比如联结）有方便之处，但哦总体不如另外两种灵活，它占用存储量大且操作复杂。

串的模式匹配算法

串的模式匹配

子串的定位操作通常称为串的模式匹配—Index(S,T,pos),T称为模式串。
采用定长顺序存储结构，写出不依赖于其他串操作的匹配算法

int index(SString S,SString T,int pos){
//返回子串T在主串S中第pos个字符之后的位置，若不存在返回0
//T非空，1<=pos<=StrLength(S)
int i=pos;
int j=1;
while(i<=S[0]&&j<=T[0]){
	if(S[i]==T[j]){//继续比较后继字符
	i++;
	j++;
	}
	else{//指针后退重新进行匹配
	i=i-j+2;
	j=1;
}
}
if(j>T[0])
	return i-T[0];
else
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

该算法的最坏时间复杂度为O（nm）,n为主串长度，m为模式串长度，这种情况常常在只有0 1两种字符的文本串处理中出现。

KMP算法

文本理解：
数据结构：串(String)【详解】

数据结构—串的详细解释（含KMP算法）

配合视频讲解：

【天勤考研】KMP算法易懂版

KMP算法之求next数组代码讲解

视频截图：

四分钟搞定！数据结构 KMP改进算法 nextval数组求值

KMP算法升级（引入nextval数组）

视频截图;