（四）串

定义

　　定义：串(string)是由零个或多个字符组成的有限序列

　　空串：串的字符数目为零

　　子串：串中任意个连续的字符组成的子序列
　　两个串相等：当且仅当这两个串值相等，即两个串的长度相等，并且各个对应位置上的字符都相等
　　抽象数据类型

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
　　ADT String{
　　　数据对象：D={ai|ai∈CharacterSet,i=1,2,...,n,n≥0}
　　　数据关系：Rl={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
　　　基本操作：
　　　StrAssign(&T,chars)
　　　　初始条件：chars是字符串常量
　　　　操作结果：生成一个其值等于chars的串T
　　　StrCopy(S)
　　　　初始条件：串S存在
　　　　操作结果：若S为空串，则返回true，否则返回false
　　　StrEmpty(S)
　　　　初始条件：串S存在
　　　　操作结果：若S为空串，则返回true,否则返回false
　　　StrCompare(S,T)
　　　　初始条件：串S和T存在
　　　　操作结果：将若S>T，则返回值为>0;若S=T，则返回值=0；若S<T，则返回绘制<0
　　　StrLength(S)
　　　　初始条件：串S存在
　　　　操作结果：返回S的元素个数，称为串的长度
　　　ClearString(&S)
　　　　初始条件：串S存在
　　　　操作结果：将S清为空串
　　　Concat(&T,S1,S2)
　　　　初始条件：串S1和S2存在
　　　　操作结果：用T返回由S1和S2联接而成的新串
　　　SubString(&Sub,S,pos,len)
　　　　初始条件：串S存在，1≤pos≤StrLength(S)且0≤StrLength(S)-pos+1
　　　　操作结果：用Sub返回串S的第pos个字符起长度为len的子串
　　　Index(S,T,pos)
　　　　初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)
　　　　操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则函数值为0
　　　Replace(&S,T,V)
　　　　初始条件：串S，T和V存在，T是非空串
　　　　操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串
　　　StrInsert(&S,pos,T)
　　　　初始条件：串S和T存在，1≤pos≤StrLength(S)+1
　　　　操作结果：在串S的第pos个字符之前插入串T
　　　StrDelete(&S,pos,len)
　　　　初始条件：串S存在，1≤pos≤StrLength(S)-len+1
　　　　操作结果：从串S中第pos个字符起长度为len的子串
　　　DestroyString(&S)
　　　　初始条件：串S存在
　　　　操作结果：串S被销毁
　　　}ADT String；

串的表示和实现
　　　1.定长顺序存储表示
　　　

1
2
　　　#define MAXSTRLEN 255  //用户可在255以内定义最大串长
　　　typedef unsigned cahr SString[MAXSTRLEN+1];  //0号单元存放串的长度

　　　图示：
　　　串图示

　　　1.以下标为0的数组分量存放串的实际长度
　　　2.在串值后面加一个不计入串长的结束标记字符

　　　静态存储分配：直接用定长的字符数组来定义

　　　优点：涉及串长的操作速度快，但不适合插入、链接操作
　　　
　　　2.对分配存储表示：
　　　　

1
2
3
4
　　　　typedef struct{
　　　　　char  *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
　　　　　int length;  //串长度
　　　　}HString;

　　　　动态存储分配：定义串是不分配存储空间，需要使用时按所需串的长度分配存储单元

　　　3.块链存储表示：
　　　　

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

　　　　图示：
　　　　串图示

　　　　当节点大小大于1时，由于串长不一定是节点大小的整数倍，则链表中的最后一个节点不一定全被串值沾满，此时通常补上“#”或其他的非串值字符

　　　三种存储表示的比较
　　　　定长顺序存储
　　　　　①在串联接和求子串的操作中，操作的时间复杂度基于复制的字符序列的长度
　　　　　②如果在操作中出现序列长度超过上届MAXSRELEN，约定用结尾法处理，这种情况在联接、插入、置换等都可能发生

　　　堆分配存储表示
　　　　　①存储空间动态分配
　　　　　②处理方便，操作对于串长没有任何限制，更显灵活

　　　块链存储
　　　　　对某些串操作，诸如联接操作等有一定的方便之处，但总的来说不如另外两种存储结构灵活

　　　　存储密度
　　　　1.存储密度=串值所占的存储位/实际分配的存储位
　　　　2.存储密度小，运算处理方便，然而存储占用大

　　　串的模式匹配
　　　　子串的定位操作
　　　　主串为S，子串为模式T

　　　　1.常规匹配算法：
　　　　　逐字符比较
　　　　　n是主串长度，m是模式长度
　　　　　最好时间复杂度O(n+m)
　　　　　最坏时间复杂度O(n*m)

　　　　2.KMP算法：
　　　　　改进在于：
　　　　　　每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较
　　　　　时间复杂度O(n+m)

　　　　3.两种算法比较：
　　　　虽然前者时间复杂度是O(n*m)，但是一般情况改下，其实际的执行时间近似于O(n+m)，因此至今仍被采用

串代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW_ -2

typedef int Status;
typedef int QElemType;
typedef int ElemType;

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

class Hstring{
private:
	int * nextval;   //子串匹配的KMP算法的next函数
public:
	Status StrAssign(HString &T,char * chars);
	//生成一个其值等于串常量chars的串T
	int StrLength(HString S);
	//返回S的元素个数，称为串的长度
	int StrCompare(HString S,HString T);
	//若S>T，则返回值>0，；若S=T，则返回值=0；若S<T.则返回<0
	Status ClearString(HString &S);
	//将S清为空串，并释放S所占空间
	Status Concat(HString &T,HString S1,HString S2);
	//用T返回由S1和S2联接而成的新串
	Status SubString(HString &Sub,HString S, int pos, int len);
	//1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
	//返回串S的第pos个字符起长度为len的子串
	int Index_KMP(HString S,HString T, int pos);
	//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中，T非空，1<=pos<=StrLength(S)
	Status Get_nextval(HString T);
	//求模式串T的next函数修正值并存入数组nextval
	Status DeleteSubstring_KMP(HString &S, HString T,int pos);
	//删除S中的子串T
	int Index(HString S, HString T, int pos);
	//返回子串T在主串S中的第pos个字符之后的位置。若不存在，则函数值为0
	//其中，T非空，1<=pos<=StrLength(S)
	//常规算法
	Status DeleteSubstring(HString &S, HString T,int pos);
	//删除S中的子串T
};

Status Hstring::StrAssign(HString &T,char * chars){
	//生成一个其值等于串常量chars的串T
	//if(T.ch) free(T.ch);	//释放T原有空间
	int chars_length=strlen(chars);
	if(!chars_length){
		T.ch=NULL; T.length=0;
	}
	else{
		//if(!(T.ch=(char*)malloc((chars_length+1)* sizeof(char)))) exit(OVERFLOW_);
		if(!(T.ch=new char[chars_length+1])) exit(OVERFLOW_);
		for(int i=0;i<chars_length;i++){
			T.ch[i]=chars[i];
			T.length=i+1;
		}
		T.ch[chars_length] = '\0';
	}
	return OK;
}

int Hstring::StrLength(HString S){
	//返回S的元素个数，称为串的长度
	return S.length;
}

int Hstring::StrCompare(HString S,HString T){
	//若S>T，则返回值>0，；若S=T，则返回值=0；若S<T.则返回<0
	for(int i=0;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;
}

Status Hstring::ClearString(HString &S) {
	//将S清为空串，并释放S所占空间
	if (S.ch) { free(S.ch); }//释放旧空间
	S.length = 0;
	return OK;
}

Status Hstring::Concat(HString &T,HString S1,HString S2){
	//用T返回由S1和S2联接而成的新串
	//if(T.ch) free(T.ch); //释放旧空间
	if(!(T.ch=(char * )malloc((S1.length+S2.length+1)* sizeof(char)))) exit(OVERFLOW_);
	for(int i=0;i<S1.length;i++){
		T.ch[i]=S1.ch[i];
	}
	T.length=S1.length+S2.length;
	for(int i=0;i<S2.length;i++){
		T.ch[i+S1.length]=S2.ch[i];
	}
	T.ch[T.length ] = '\0';
	return OK;
}

Status Hstring::SubString(HString &Sub,HString S, int pos,int len){
	//1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
	//返回串S的第pos个字符起长度为len的子串
	if(pos<1||pos>S.length||len<0||len>S.length-pos+1) //查询位置不当
		return ERROR;
	if(Sub.ch) free(Sub.ch); //释放旧空间
	if(!len){Sub.ch=NULL;Sub.length=0;} //空子串
	else{
		Sub.ch=(char*)malloc((len+1)* sizeof(char));
		for(int i=0;i<len;i++){
			Sub.ch[i]=S.ch[pos-1+i];
		}
		Sub.ch[len] = '\0';
		Sub.length=len;
	}
	return OK;
}

//--------KMP算法删除子串----------
int Hstring::Index_KMP(HString S,HString T, int pos){
	//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中，T非空，1<=pos<=StrLength(S)
	int i = pos - 1, j = 0;
	while(i<StrLength(S)&&j<StrLength(T)){
		if (j == -1 || S.ch[i] == T.ch[j]) { ++i;++j; }    //继续比较后继字符
		else j=nextval[j];						   //模式串向右移动
	}
	if(j== StrLength(T)) return i+1- StrLength(T);    //匹配成功
	else return 0;
}

Status Hstring::Get_nextval(HString T){
	//求模式串T的next函数修正值并存入数组nextval
	int i=0,j=-1;
	nextval[0]=-1;
	while(i<StrLength(T)-1){
		if(j==-1||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];
		}
	}
	return OK;
}
Status Hstring::DeleteSubstring_KMP(HString &S,HString T,int pos){
	//删除S中的子串T
	nextval = new int[StrLength(T)];
	Get_nextval(T);
	int index;
	if (!(index = Index_KMP(S, T, pos))) return ERROR; //不存在子串
	else{
		for(int i=index-1;i<StrLength (S)-StrLength (T)+index;i++){
			S.ch[i]=S.ch[i+ StrLength(T)];
		}
	}
	return OK;
}

//-------普通算法删除子串-------
int Hstring::Index(HString S,HString T,int pos) {
	//返回子串T在主串S中的第pos个字符之后的位置。若不存在，则函数值为-1
	//其中，T非空，1<=pos<=StrLength(S)
	int i = pos-1, j = 0;
	while (i < StrLength(S) && j < StrLength(T)) {
		if (S.ch[i] == T.ch[j]) { ++i;++j; } //继续比较后续字符
		else { i = i - j + 1;j = 0; } //指针后退重新开始匹配
	}
	if (j == StrLength(T)) return i - StrLength(T)+1;
	else return -1;
}

Status Hstring::DeleteSubstring(HString &S, HString T,int pos) {
	//删除S中的子串T
	int index = Index(S, T, pos);
	if (index == -1) return ERROR;
	else {
		for (int i = index-1;i < StrLength(S)  - StrLength(T);i++) {
			S.ch[i] = S.ch[i + StrLength(T)];
		}
		S.ch[StrLength(S)-StrLength(T)]='\0';
	}
	return OK;
}
赏

Thank you for inviting me to have candy.

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

做一个安静细微的人，<br> 于角落里自在开放，<br> 默默悦人，<br> 却始终不引起过分热闹的关注，<br> 保有独立而随意的品格，<br> 这就很好。<br><br> Stick to what you insist on,<br> believe what you believe!<br> Life hastily for decades,<br> do what I can!