数据结构(3)-串

引言

串，顾名思义字符串string,在一些高级语言，比如C++、Java中就有这个类型，在C中通过引入string.h头函数也可以采用该类型，但最初其实是没有这个类型的，只是因为现实生活中太多字符串类型的数据需要处理，所以才加上的。
其实一连串的字符组合在一起就是字符串。所以字符串可以看成字符的线性表。也是线性表的一种形式。字符串最常见的操作就是，判等、查找子串、字符串的切分、拼接等。

串的顺序实现(数组)

字符串就是一连串的字符，所以最简单的用字符型数组就可以实现字符串，这里实现书上给出的三个算法，分别是裁剪、拼接、查找

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
#include<stdio.h>
#include<stdlib.h>
# define MAXSIZE 20 //定义串的最大长度
typedef unsigned char SString[MAXSIZE+1]; //0号单元放串长度，后面MAXSIZE个空间放数据

void createString(SString &s, int n){//创建长度为n的串
	s[0] = n;
	for(int i=1;i<=n;i++){
		scanf("%c",&s[i]);
		getchar();
	}
}
void printString(SString &s){ //打印串
	printf("len:%d  ",s[0]);
	for(int i=1;i<=s[0];i++){
		printf("%c",s[i]);
	}
	printf("\n");
}
bool Concat(SString &T, SString &s1, SString &s2){ //将s1和s2连接成新的串，放在T中。如果能完整放下则返回true 如果不能放下，则会被截断返回false
	int i,j;
	//书上的实现方法
	if(s1[0]+s2[0]<=MAXSIZE){ //未截断
		i=1;
		while(i<=s1[0]){ //先把s1放进T
			T[i] = s1[i];
			i++;
		}
		j=1;
		while(j<=s2[0]){ //把s2放入T
			T[i] = s2[j];
			i++;
			j++;
		}
		T[0] = s1[0]+s2[0];
		return true;
	}else if(s1[0]<MAXSIZE){ //截断s2
		i=1;
		while(i<=s1[0]){
			T[i] = s1[i];
			i++;
		}
		j=1;
		while(i<=MAXSIZE){ //i作为T的下标最多到MAXSIZE
			T[i] = s2[j];
			i++;
			j++;
		}
		T[0] = MAXSIZE;
		return false;
	}else{//S1被截断
		i=1;
		while(i<=MAXSIZE){ //i作为T的下标最多到MAXSIZE
			T[i] = s1[i];
			i++;
		}
		T[0] = MAXSIZE;
		return false;
	}
}
bool Concat_my(SString &T, SString &s1, SString &s2){
	//书上写法逻辑很好理解，但代码量太冗余了，这里给个更简单的写法
	int i=1,j=1;
	while(i<=MAXSIZE&&i<=s1[0]){ //只要i不超过s1长度或者MAXSIZE 就一直把s1的数据放入T
		T[i] = s1[i];
		i++;
	}

	while(i<=MAXSIZE&&j<=s2[0]){ //只要i不超过MAXSIZE j不超过s2的长度 就一直把s2的数据放入T
		T[i] = s2[j];
		i++;
		j++;
	}
	T[0] = i-1;
	if(j<s2[0]) // 说明s2没放完就停了 则直接return false
		return false;
	return true;
}
bool SubString(SString s,SString &sub, int pos, int len){ //从主串s的post位置开始截取长度为len的子串给sub
	if(pos<1||pos+len-1>s[0]) return false; //截取位置和长度不符合条件
	int i=1;
	while(i<=len){
		sub[i] = s[i+pos-1];
		i++;
	}
	sub[0] = len;
	return true;

}
int Index(SString s, SString T, int pos){// 从串s的位置开始查找是否存在子串T, 如果存在，则返回第一次出现的位置。如果不存在，返回0
	int i=pos,j=1; //i跟主串 j跟子串
	while(i<=s[0]-T[0]+1&&j<=T[0]){
		if(s[i]==T[j]){ // 如果当前相等，继续比较下一个
			i++;
			j++;
		}else{ // 如果不等 则j复原到T的开始，i从上一个比较元素的后一个开始，也就是i减去此次比较的位移(j-1次)。然后+1 所以i = i-(j-1)+1
			i = i-j+2;
			j = 1;
		}
	}
	if(j>T[0]) return i-T[0]; //j超出T长度，说明找到子串了
	return 0;

}
int main(){
	SString s1,s2;
	SString T1,T2;
	/*
	createString(s1,4);
	createString(s2,5);
	Concat(T1,s1,s2);
	Concat(T2,s1,s2);
	printString(T1);
	printString(T2);
	*/
	/*
	createString(T1,10);
	SubString(T1,s1,3,5);
	printString(s1);
	*/
	createString(s1,10);
	createString(T1,3);
	int i = Index(s1,T1,2);
	printf("%d\n",i);
	return 0;
}

串的堆实现

其实也是顺序实现，只是用指针指向的连续空间来代替了数组，其优点就是长度可以动态增加

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
#include<stdio.h>
#include<stdlib.h>
typedef struct{
	char *ch; // 若是非空串，则根据串长分配存储区，否则ch为NULL
	int length; //串长度
}HString;
void init(HString &T, int n){ //初始化串T为长度n的空串
	T.length = n;
	T.ch = (char *)malloc(T.length*sizeof(char));
}
void printHString(HString &T){
	for(int i=0; i<T.length; i++){
		printf("%c", T.ch[i]);
	}
	printf("\n");
}
void CreateHString(HString &T, int n){
	init(T,n);
	for(int i=0; i<n; i++){
		scanf("%c",&T.ch[i]);
		getchar();
	}
}
void StrAssign(HString &T, char *chars){
	//生成一个其值等于串常量chars的串T
	int len = chars[0]-'0';
	init(T,len);
	int i =0;
	while(i<len){
		T.ch[i] = chars[i+1];
		i++;
	}
}
int StrCompare(HString &S, HString &T){ //比较两个串 S>T返回正数 S=T返回0 S<T返回负数
	if(S.length==T.length){
		int i = 0;
		while(i<S.length&&S.ch[i]==T.ch[i]){ //i没超出范围 且当前元素相等，比较下一个元素
			i++;
		}
		if(i>S.length) return 0;//比较完了都相等
		return S.ch[i]-T.ch[i];
	}else{
		return S.length-T.length;
	}

}
void Concat(HString &T,HString &T1,HString &T2){ //将T1和T2拼接成新串
	init(T,T1.length+T2.length);
	int i=0;
	while(i<T1.length){
		T.ch[i] = T1.ch[i];
		i++;
	}
	int j = 0;
	while(j<T2.length){
		T.ch[i] = T2.ch[j];
		i++;
		j++;
	}
}
bool SubString(HString &T,HString &sub,int pos, int len){//从主串s的post位置开始截取长度为len的子串给sub
	if(pos<1||pos-len-1>T.length) return false;
	init(sub,len);
	int i = pos-1,j=0;
	while(j<len){
		sub.ch[j] = T.ch[i];
		j++;
		i++;
	}
	return true;
}
int main(){
	HString T1,T2,T3;
	/*
	char chars[7] = {'6','a','b','c','d','e','f'};
	StrAssign(T1,chars);
	printHString(T1);
	*/

	CreateHString(T1,10);
	//CreateHString(T2,3);
	/*
	int i = StrCompare(T1,T2);
	printf("%d",i);
	*/
	/*
	Concat(T3,T1,T2);
	printHString(T3);
	*/
	SubString(T1,T2,3,3);
	printHString(T2);
	return 0;
}

串的链表实现

链式表示书上只是介绍，没要求具体算法，我这也就不写了，参考前面的线性链表，把里面int类型的数据域换成char类型就是串的链式实现了

匹配算法-KMP

原理 自行看书，三两句话解释不清楚

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
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef unsigned char SString[MAXSIZE+1];

void createString(SString &s, int n){
	s[0] = n;
	for(int i=1; i<=n; i++){
		scanf("%c",&s[i]);
		getchar();
	}
}

void printString(SString &s){
	for(int i=1; i<=s[0]; i++){
		printf("%c",s[i]);
	}
	printf("\n");
}
void getNext(SString &s, int next[]){
	int j=1,k=0; // i用来遍历s, k用来记录最长相等前后缀
	next[j] = k;
	while(j<s[0]){
		if(k==0||s[j]==s[k]){ //当前相等 最长相等前后缀+1
			j++; //比较后一个
			k++; //最长相等前后缀+1
			next[j] = k;//记录j前面j-1子串的最长相等前后缀+1 = k
		}else{ //不相等
			k = next[k]; // 往前回溯
		}
	}
}
void get_nextval(SString &s, int next[]){
	int j=1,k=0;
	next[j] = k;
	while(j<s[0]){
		if(k==0||s[j]==s[k]){
			j++;
			k++;
			// 优化
			if(s[j]==s[k]){ //记录的回溯和当前的相等了 则
				next[j] = next[k];
			}else{
				next[j] = k;
			}
		}else{
			k = next[k];
		}
	}
}
int KMP(SString &T, SString &s, int next[]){
	int i=1,j=1;
	while(i<=T[0]&&j<=s[0]){
		if(j==0||T[i]==s[j]){ //如果相等，比较下一个
			i++;
			j++;
		}else{ // 如果不等，i不动 j根据next回溯
			j=next[j];
		}
	}
	if(j>s[0]){
		return i-j+1;
	}
	return -1;
}
int main(){
	SString T,s;
	createString(T,8);
	printf("\n");
	createString(s,4);
	for(int i=1; i<=T[0];i++){
		printf("%c",T[i]);
	}printf("\n");
	for(int i=1; i<=s[0];i++){
		printf("%c",s[i]);
	}printf("\n");
	int next[6];
	getNext(s,next);
	for(int i=1; i<=s[0];i++){
		printf("%d",next[i]);
	}
	printf("\n");
	get_nextval(s,next);
	for(int i=1; i<=s[0];i++){
		printf("%d",next[i]);
	}
	printf("\n");
	int index = KMP(T,s,next);
	printf("%d",index);
}

串操作-建立书目关键字索引

逻辑其实不复杂，但完美的用到了之前提到的各种线性表，直接上源码

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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#include<stdio.h>
#include<stdlib.h>

#define MaxBookNum 10 // 输入最大书数目
#define MaxKeyNum 30 //索引表最大容量，最多关键词个数
#define MaxLineLen 5 // 书名称中最多有多少个关键字
#define MaxWordNum 10  // 一个关键字最多有多少个字符
typedef int ElementType; // 书号定义为int类型
typedef struct{
	char *elem;
	int length;
}HString; // 串的堆实现
typedef struct Node{
	int bookno;
	struct Node *next;
}Node, *NodeList;
typedef struct{
	NodeList head,tail;
	int length;
}LinkList; // 线性链表
typedef struct {
	HString *item;  // 字符串数组
	int last; //词表长度
}WordListType; // 词表类型， 用来存放书名中提取出来的关键字。
typedef struct {
	HString key; // 关键字
	LinkList bnolist; // 存放书号索引的链表
}IdxTermType; //索引表结点类型
typedef struct{
	IdxTermType item[MaxKeyNum+1];
	int last; // 长度，也是最后一个单元下标
}IdxListType;

void print_word(HString s){ //打印一个关键词
	for(int i=0; i<s.length;i++){
		printf("%c", s.elem[i]);
	}
	printf(" ");
}
void print_wordList(WordListType book_keys){ //打印一个关键词表
	for(int i=0; i<book_keys.last;i++){
		print_word(book_keys.item[i]);
	}
	printf("\n");
}

void print_idxTerm(IdxTermType IdxTerm){
	print_word(IdxTerm.key);
	NodeList p =  IdxTerm.bnolist.head;
	while(p != NULL){
		printf("%d ",p->bookno);
		p = p->next;
	}
}
void print_IdxList(IdxListType bookidx){ // 打印简历好的索引表
	for(int i=0; i<bookidx.last;i++){
		print_idxTerm(bookidx.item[i]);
		printf("\n");
	}
}


void init_WordList(WordListType &wd){
	wd.last = 0;
	wd.item = (HString*)malloc(MaxLineLen*sizeof(HString));	
}

bool create_word(HString &s){ // 根据输入创建一个字符串 回车或者空格结束
	s.elem = (char *)malloc(MaxWordNum*sizeof(char));
	s.length = 0;
	char c;
	while(scanf("%c",&c)&&c!=' '&&c!='\n'){
		s.elem[s.length] = c;
		s.length++;
	}
	if(c=='\n'){
		return false;
	}else{
		return true;
	}
}

void init_BookIdx(IdxListType &bookIdx){
	bookIdx.last = 0;
}
bool get_word(WordListType &book_keys, HString &s){ //从词表中 拿一个关键字，如果空了返回false
	if(book_keys.last == 0)
		return false;
	book_keys.last -= 1;
	s = book_keys.item[book_keys.last];
	return true;
}
int compare(HString a,HString b){ //比较a和b的大小，相等0 a<b 负数 a>b正数
	int i=0,j=0;
	while(i<a.length&&j<b.length){
		if(a.elem[i]==b.elem[j]){
			i++;
			j++;
		}else{
			return a.elem[i]-b.elem[j];
		}
	}
	if(a.length==b.length){
		return 0;
	}else{
		return a.length-b.length;
	}
}
bool get_idx(IdxListType bookidx, HString s, int &idx){ //判断关键字是否在索引表中，如果在返回true  否则返回false idx用来返回 在索引表中的位置，如果 不在索引表中idx则是需要插入的位置
	if(bookidx.last==0){ // 索引表还是空的
		idx = 0;
		return false;
	}
	//折半查找，找到返回下标
	int l = 0,r=bookidx.last;
	int m = (l+r)/2;
	while(l<m||m<r){
		int cmp = compare(bookidx.item[m].key,s);
		if(cmp==0){
			idx=m;
			return true;
		}else if(cmp<0){ //  继续向右边找
			l=m+1;
			m=(l+r)/2;
		}else{ // 继续向左边找
			r=m-1;
			m=(l+r)/2;
		}
	}
	//没找到 则做判断插入位置
	if(m>=bookidx.last){
		idx = m;
		return false;
	}
	int cmp = compare(bookidx.item[m].key,s);
	if(cmp==0){
		idx=m;
		return true;
	}else if(cmp<0){
		idx = m+1;
		return false;
	}else{
		idx = m;
		return false;
	}	
}
void input_bookNo(IdxListType &bookidx,int idx,int bookno){ // 在书索引的idx位置的关键字插入一个书号
	NodeList p = (NodeList)malloc(sizeof(Node));
	p->bookno = bookno;
	p->next = NULL;
	bookidx.item[idx].bnolist.tail->next = p;
	bookidx.item[idx].bnolist.tail = p;
	bookidx.item[idx].bnolist.length +=1;
}
void create_IdxTerm(IdxTermType &IdxTerm,int bookno, HString s){ //创建一个索引结点，并把书号和关键字插入这个结点
	
	IdxTerm.key = s;
	NodeList p = (NodeList)malloc(sizeof(Node));
	p->bookno = bookno;
	p->next = NULL;
	IdxTerm.bnolist.head = IdxTerm.bnolist.tail = p;
	IdxTerm.bnolist.length = 1;
}
void input_IdxTerm(IdxListType &bookidx,int idx,IdxTermType IdxTerm){ //将一个索引结点插入到索引表的idx位置
	int i;
	for(i=bookidx.last;i>idx;i--){
		bookidx.item[i] = bookidx.item[i-1];
	}
	bookidx.item[i] = IdxTerm;
	bookidx.last++;
}

int main(){
	int bookno; //用来接收输入的书号
	IdxListType bookidx;
	init_BookIdx(bookidx);
	WordListType book_keys;
	init_WordList(book_keys);
	HString s;
	while(scanf("%d",&bookno)&&bookno){
		// 创建词表
		getchar();
		while(create_word(s)){
			book_keys.item[book_keys.last] = s;
			book_keys.last++;
		}
		book_keys.item[book_keys.last] = s;
		book_keys.last++;

		// // 从词表中拿出一个关键字
		while(get_word(book_keys,s)){
			int idx;
			if(get_idx(bookidx,s,idx)){
				//该关键字在索引表中，直接把书号插入
				input_bookNo(bookidx,idx,bookno);
			}else{
				//用该关键字创建IdxTermType
				IdxTermType  IdxTerm;
				create_IdxTerm(IdxTerm,bookno,s);
				input_IdxTerm(bookidx,idx,IdxTerm);
			}
		}
	}
	//打印创建好的索引表
	// print_wordList(book_keys);
	print_IdxList(bookidx);
}