C语言实现链串基本操作_链串的基本操作c语言

C语言实现链串基本操作

通过调用简单函数实现顺序串的相关操作，其中大部分操作其实都可以通过string.h中的函数实现，所以这里的操作仅供理解，目的是领会链串存储结构和掌握链串中的各种基本运算算法设计。代码编译环境为VS2019 16.11.2。因为VS的某些原因，scanf写为了scanf_s，作用是一样的，在其他编译环境中可将scanf_s改回去。

#include<stdio.h>		//输入输出头文件
#include<stdlib.h>		//标准库头文件
#include<stdbool.h>		//C语言布尔类型头文件
#define MaxSize 999

typedef char ElemType;
typedef struct String //字符串结构体
{
	ElemType data;
	struct String* next;
}StrNode;

void menu(void);					//输出菜单
bool StrAssige(StrNode*&); 			//建立顺序串
bool StrShow(StrNode*);				//输出顺序串
bool StrLength(StrNode*);			//输出顺序串长度
bool InsStr(StrNode*&);				//特定位置插入字符串
bool DelStr(StrNode*&);				//删除特定位置字符串
bool RepStr(StrNode*&);				//替换特定位置字符串
bool SubStr(StrNode*);				//截取子串
bool Concat(StrNode*&);				//在顺序串后面追加内容
bool DestroyStr(StrNode*&);			//销毁链串

int main(int argc, const char* argv[])
{
	StrNode* Str = NULL;
	bool flag = false;
	int n;
	menu();
	while (scanf_s("%d", &n) != EOF) {
		switch (n) {
		case 1:flag = StrAssige(Str); break;
		case 2:flag = StrShow(Str); break;
		case 3:flag = StrLength(Str); break;
		case 4:flag = InsStr(Str); break;
		case 5:flag = DelStr(Str); break;
		case 6:flag = RepStr(Str); break;
		case 7:flag = SubStr(Str); break;
		case 8:flag = Concat(Str); break;
		case 0:DestroyStr(Str); goto Out;
		default:
			printf("指令错误，请重新输入，若想终止程序请输入文件尾。\n");
		}
		if (flag)
			printf("指令执行成功！\n");
		else
			printf("指令执行失败！\n");
		menu();
	}
Out:
	return 0;
}
void menu(void)
{
	printf("===========菜单==========\n");
	printf("== 1.建立顺序串        ==\n");
	printf("== 2.输出顺序串        ==\n");
	printf("== 3.输出顺序串长度    ==\n");
	printf("== 4.特定位置插入字符串==\n");
	printf("== 5.删除特定位置字符串==\n");
	printf("== 6.替换特定位置字符串==\n");
	printf("== 7.截取子串          ==\n");
	printf("== 8.在顺序串后面连接  ==\n");
	printf("== 0.退出              ==\n");
}
bool StrAssige(StrNode* &s)
{
	int i = 0;
	StrNode* p = NULL, * r = NULL;
	s = (StrNode*)malloc(sizeof(StrNode));	//为头结点申请空间
	while (s == NULL) {
		s = (StrNode*)malloc(sizeof(StrNode));
	}
	r = s;	//将尾指针指向最后一个元素
	printf("请输入一个字符串：\n");
	ElemType str[MaxSize];
	scanf_s("%s", str, MaxSize);
	for (i = 0; str[i] != '\0'; i++) {	//将字符串中除结尾'\0'外的字符按顺序放入链串
		p = (StrNode*)malloc(sizeof(StrNode));
		while (p == NULL) {
			p = (StrNode*)malloc(sizeof(StrNode));
		}
		p->data = str[i];	//将存有元素的节点采用尾插法插入链串中
		r->next = p;
		r = p;
	}
	r->next = NULL;
	return true;
}
bool StrShow(StrNode* s)
{
	if (s == NULL || s->next == NULL) {
		printf("字符串不存在，请先建立字符串。\n");
		return false;
	}
	StrNode* r = s->next;
	while (r != NULL) {	//挨个遍历顺序串
		printf("%c", r->data);
		r = r->next;
	}
	printf("\n");
	return true;
}
bool StrLength(StrNode* s)
{
	int length = 0;
	StrNode* r = s->next;
	while (r != NULL) {	//挨个遍历顺序串
		length ++;
		r = r->next;
	}
	printf("该字符串长度为%d。\n", length);	//输出长度
	return true;
}
bool InsStr(StrNode*& s)
{
	if (s == NULL || s->next == NULL) {
		printf("字符串不存在，请先建立字符串。\n");
		return false;
	}
	int i, n, length = 0;
	StrNode* p, * r = s->next;
	while (r != NULL) {	//挨个遍历顺序串并统计长度
		length++;
		r = r->next;
	}
	printf("请输入插入位置:\n");
	scanf_s("%d", &n);
	if (n <= 0 || n > length) {	//当位置比顺序串的头还要靠前，比尾还要靠后时位置无效
		printf("位置不合法，无法插入。\n");
		return false;
	}
	ElemType strs[MaxSize]; //要插入的字符串
	r = s;
	for (i = 1; i < n; i++) {	//将尾指针移到要插入位置的前驱节点
		r = r->next;
	}
	printf("请输入要插入的字符串：\n");
	scanf_s("%s", strs, MaxSize);
	//将字符串插入它要插入的位置
	for (i = 0; strs[i] != '\0'; i++) {
		p = (StrNode*)malloc(sizeof(StrNode));
		while (p == NULL) {
			p = (StrNode*)malloc(sizeof(StrNode));
		}
		p->data = strs[i];
		p->next = r->next;
		r->next = p;
		r = p;
	}
	return true;
}
bool DelStr(StrNode*& s)
{
	if (s == NULL || s->next == NULL) {
		printf("字符串不存在，请先建立字符串。\n");
		return false;
	}
	int i, j, k, length = 0;
	StrNode* p, *r = s->next;
	while (r != NULL) {	//挨个遍历顺序串并统计长度
		length++;
		r = r->next;
	}
	printf("请输入要删除的开始位置与要删除的长度：");
	scanf_s("%d%d", &i, &j);
	if (i <= 0 || i > length || j<0 || i+j>length) {	//当位置比顺序串的头还要靠前，比尾还要靠后时位置无效
		printf("位置不合法，无法删除。\n");
		return false;
	}
	r = s;
	for (k = 1; k < i; k++) {	//将尾指针移到要删除位置的前驱节点
		r = r->next;
	}
	//将被删除的子串释放
	for (k = 0; k < j; k++) {
		p = r->next;
		r->next = p->next;
		free(p);
	}
	return true;
}
bool RepStr(StrNode*& s)
{
	if (s == NULL || s->next == NULL) {
		printf("字符串不存在，请先建立字符串。\n");
		return false;
	}
	int i, j, k, length = 0;
	StrNode* p = NULL, * r = s->next;
	while (r != NULL) {	//挨个遍历顺序串并统计长度
		length++;
		r = r->next;
	}
	printf("请输入要替换的开始位置与要替换的长度：");
	scanf_s("%d%d", &i, &j);
	if (i <= 0 || i > length || j<0 || i + j>length) {	//当位置比顺序串的头还要靠前，比尾还要靠后时位置无效
		printf("位置不合法，无法完成替换。\n");
		return false;
	}
	r = s;
	for (k = 1; k < i; k++) {	//将尾指针移到要替换位置的前驱节点
		r = r->next;
	}
	ElemType strs[MaxSize]; //替换后的字符串
	printf("请输入替换后的字符串：\n");
	scanf_s("%s", strs, MaxSize);
	//将被替换的字符串删除
	for (k = 0; k < j; k++) {
		p = r->next;
		r->next = p->next;
		free(p);
	}
	//将替换后的字符串插入
	for (i = 0; strs[i] != '\0'; i++) {		//将数据结点顺序插入
		p = (StrNode*)malloc(sizeof(StrNode));
		while (p == NULL) {
			p = (StrNode*)malloc(sizeof(StrNode));
		}
		p->data = strs[i];
		p->next = r->next;
		r->next = p;
		r = p;
	}
	return true;
}
bool SubStr(StrNode* s)
{
	if (s == NULL || s->next == NULL) {
		printf("字符串不存在，请先建立字符串。\n");
		return false;
	}
	int i, j, k, length = 0;
	StrNode* r = s->next;
	while (r != NULL) {	//挨个遍历顺序串并统计长度
		length++;
		r = r->next;
	}
	printf("请输入要提取的开始位置与要提取的长度：");
	scanf_s("%d%d", &i, &j);
	if (i <= 0 || i > length || j<0 || i + j>length-1) {	//当位置比顺序串的头还要靠前，比尾还要靠后时位置无效
		printf("位置不合法，无法完成提取。\n");
		return false;
	}
	r = s;
	for (k = 1; k < i; k++) {	//将尾指针移到要提取位置的前驱节点
		r = r->next;
	}
	//将规定的子串输出
	for (k = 0; k < j; k++) {
		r = r->next;
		printf("%c", r->data);
	}
	printf("\n");
	return true;
}
bool Concat(StrNode*& s)
{
	if (s == NULL || s->next == NULL) {
		printf("字符串不存在，请先建立字符串。\n");
		return false;
	}
	StrNode* p, * r = s->next; 
	ElemType str[MaxSize];
	int i;
	printf("请输入要连接的字符串：\n");
	scanf_s("%s", str, MaxSize);
	//将新字符串接到原字符串后面
	while (r->next != NULL) {	//将尾指针移到尾部
		r = r->next;
	}
	for (i = 0; str[i] != '\0'; i++) {
		p = (StrNode*)malloc(sizeof(StrNode));
		while (p == NULL) {
			p = (StrNode*)malloc(sizeof(StrNode));
		}
		p->data = str[i];
		p->next = r->next;
		r->next = p;
		r = p;
	}
	return true;
}
bool DestroyStr(StrNode*& s)
{
	//将链串包括头结点全部释放
	StrNode* p;
	while (s != NULL) {
		p = s;
		s = s->next;
		free(p);
	}
	return true;
}
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294