数据结构—链串 Ⅶ

数据结构-串(第四章)的整理笔记，若有错误，欢迎指正。
数据结构—顺序串 Ⅵ

串 的 基 本 操 作 { S t r A s s i g n ( & s , c s t r ) — 生 成 串 D e s t r o y S t r ( & s ) — 销 毁 串 S t r C o p y ( & s , t ) — 串 的 复 制 S t r E q u a l ( s , t ) — 判 断 串 相 等 S t r L e n g t h ( s ) — 求 串 长 C o n c a t ( s , t ) — 串 的 连 接 S u b S t r ( s , i , j ) — 求 子 串 I n s S t r ( s 1 , i , s 2 ) — 子 串 的 插 入 D e l S t r ( s , i , j ) — 子 串 的 删 除 R e p S t r ( s , i , j , t ) — 子 串 的 替 换 D i s p S t r ( s ) — 输 出 串 串的基本操作

$$\begin{cases} StrAssign(\&s, cstr)—生成串\\ DestroyStr(\&s)—销毁串\\ StrCopy(\&s,t)—串的复制\\ StrEqual(s,t)—判断串相等\\ StrLength(s)—求串长\\ Concat(s,t)—串的连接\\ SubStr(s,i,j)—求子串\\ InsStr(s1,i,s2)—子串的插入\\ DelStr(s,i,j)—子串的删除\\ RepStr(s,i,j,t)—子串的替换\\ DispStr(s)—输出串\\ \end{cases}$$ 串的基本操作⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​StrAssign(&s,cstr)—生成串DestroyStr(&s)—销毁串StrCopy(&s,t)—串的复制StrEqual(s,t)—判断串相等StrLength(s)—求串长Concat(s,t)—串的连接SubStr(s,i,j)—求子串InsStr(s1,i,s2)—子串的插入DelStr(s,i,j)—子串的删除RepStr(s,i,j,t)—子串的替换DispStr(s)—输出串​

---

串的链式存储结构——链串

• 串采用链式存储结构存储时称为链串，这里采用带头结点的单链表作为链串。
  线性表-单链表(Ⅲ)
• 链串的组织形式与一般的单链表类似,主要区别在于链串中的一个结点可以存储多个字符。通常将链串中每个结点所存储的字符个数称为结点大小。
• 下图分别表示同一个串"ABCDEFGHIJ"的结点大小为4(存储密度大)和1(存储密度小)时的链串结构。
  
• 当结点大小大于1(例如结点大小为4)时，链串的尾结点的各个数据域不一定总能全被字符占满，此时应在这些未占用的数据域里补上不属于字符集的特殊符号(例如’#'字符)，以示区别。
• 在链串中，结点大小越大，存储密度越大，但一些基本操作(如插入、删除、替换等)有所不便，且可能引起大量字符移动，因此它适合于串很少修改的情况；结点大小越小(如结点大小为1时)，相关操作的实现越方便，但存储密度下降。为简便起见，这里规定链串结点大小均为1。

结点类型声明(结点大小为4)

typedef struct
{
	char data[4]; //存放字符
	LinkStrNode* next; //指向下一个结点的指针
}LinkStrNode; //链串的结点类型
1
2
3
4
5

结点类型声明(结点大小为1)

typedef struct
{
	char data; //存放字符
	LinkStrNode* next; //指向下一个结点的指针
}LinkStrNode; //链串的结点类型
1
2
3
4
5

生成串—StrAssign(&s, cstr)

• 将一个C/C++字符串常量cstr(以"\0"字符标识结尾)赋给链串s，即生成一个其值等于cstr的链串s。

void StrAssign(LinkStrNode*& s, char cstr[])
{
	int i;
	LinkStrNode* r, *p;
	s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	r = s; //r始终指向尾结点
	for (i = 0; cstr[i] != '\0'; i++)
	{
		p = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		p->data = cstr[i];
		r->next = p;
		r = p;
	}
	r->next = NULL; //尾结点的next域置为空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

销毁串— DestroyStr(&s)

void Destroy(LinkStrNode*& s)
{
	LinkStrNode* pre = s, * p = s->next; //pre指向结点p的前驱节点
	while (p != NULL) //扫描链串s
	{
		free(pre); //释放pre结点
		pre = p; //pre、p同步后移一个结点
		p = p->next;
	}
	free(pre); //循环结束时p为NULL，pre指向尾结点，释放它
}
1
2
3
4
5
6
7
8
9
10
11

串的复制—StrCopy(&s,t)

• 将链串t赋值给链串s。

void StrCopy(LinkStrNode*& s, LinkStrNode* t)
{
	LinkStrNode* p = t->next, * q, * r;
	s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	r = s; //r始终指向尾结点
	while (p != NULL) //扫描链串t的所有结点
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data; //将p结点复制到q结点
		r->next = q; //q结点链接到链串s的末尾
		r = q;
		p = p->next;
	}
	r->next = NULL; //尾结点的next域置为空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

判断串相等—StrEqual(s,t)

• 若两个链串s与t的长度相等且对应位置的字符均相同，则返回真；否则返回假。

bool StrEqual(LinkStrNode* s, LinkStrNode* t)
{
	LinkStrNode* p = s->next, * q = t->next; //p、q分别扫描链串s和t的数据结点
	while (p != NULL && q != NULL && p->data == q->data)
	{
		p = p->next;
		q = q->next;
	}
	if (p == NULL && q == NULL) return true; //s和t的长度相等且对应位置的字符均相同
	else return false;
}
1
2
3
4
5
6
7
8
9
10
11

求串长—StrLength(s)

• 通过遍历链串s的所有数据结点求其个数并返回。

int StrLength(LinkStrNode* s)
{
	int i = 0; //i用于累计数据结点的个数
	LinkStrNode* p = s->next; //p指向链串s的首结点
	while (p != NULL) //扫描所有数据结点
	{
		i++;
		p = p->next;
	}
	return i;
}
1
2
3
4
5
6
7
8
9
10
11

串的连接—Concat(s,t)

• 由两个链串s和t的数据结点连接在一起形成的结果串。

LinkStrNode* Concat(LinkStrNode* s, LinkStrNode* t)
{
	LinkStrNode* str, * p = s->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	r = str; //r指向结果串的尾结点
	while(p!=NULL) //用p扫描s的所有数据结点
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data; //将p结点复制到q结点中
		r->next = p; //将q结点链接到str的末尾
		r = p;
		p = p->next;
	}
	p = t->next;
	while (p != NULL) //用p扫描t的所有数据结点
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data; //将p结点复制到q结点中
		r->next = p; //将q结点链接到str的末尾
		r = p;
		p = p->next;
	}
	r->next = NULL; //尾结点的next域置为空
	return str;
}
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

求子串—SubStr(s,i,j)

• 返回链串s中从第(1≤i≤n)个字符开始的由连续j个字符组成的子串。当参数不正确时返回一个空串。

LinkStrNode* SubStr(LinkStrNode* s, int i, int j)
{
	int k;
	LinkStrNode* str, * p = s->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL; //置结果串str为空串
	r = str; //r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s)) return str; //参数不正确时返回空串
	for (k = 0; k < i; k++) p = p->next; //让p指向链串s的第i个数据结点
	for (k = 1; k <= j; k++) //将s的从第i个结点开始的j个结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL; //尾结点的next域置为空
	return str;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

子串的插入—InsStr(s1,i,s2)

• 将链串s2插入到链串s1的第i(1≤i≤n+1)个位置上，得到一个结果串。当参数不正确时返回一个空串。

LinkStrNode* InsStr(LinkStrNode* s, int i, LinkStrNode* t)
{
	int k;
	LinkStrNode* str, * p = s->next, * p1 = t->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL; //置结果串str为空串
	r = str; //r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s)) return str; //参数不正确时返回空串
	for (k = 1; k < i; k++) //将s的前i个结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	while (p1 != NULL) //将t的所有结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p1->data;
		r->next = q;
		r = q;
		p1 = p1->next;
	}
	while (p != NULL) //将p结点及其后的结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL; //尾结点的next域置为空
	return str;
}
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

子串的删除—DelStr(s,i,j)

• 在链串s删去从第i(1≤i≤n+1)个字符开始的长度为j的子串，得到一个结果串。当参数不正确时返回一个空串。

LinkStrNode* DelStr(LinkStrNode* s, int i, int j)
{
	int k;
	LinkStrNode* str, * p = s->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL; //置结果串str为空串
	r = str; //r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s)) return str; //参数不正确时返回空串
	for (k = 1; k < i; k++) //将s的前i-1个结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	for (k = 0; k < j; k++) p = p->next; //让p沿next跳j个结点
	while (p != NULL) //将p结点及其后的结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL; //尾结点的next域置为空
	return str;
}
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

子串的替换—RepStr(s,i,j,t)

• 在链串s中将第(1≤i≤n)个字符开始的连续j个字符构成的子串用链串t替换。当参数不正确时返回一个空串。

LinkStrNode* RepStr(LinkStrNode* s, int i, int j, LinkStrNode* t)
{
	int k;
	LinkStrNode* str, * p = s->next, * p1 = t->next, * q, * r;
	str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
	str->next = NULL; //置结果串str为空串
	r = str; //r指向结果串的尾结点
	if (i <= 0 || i > StrLength(s) || j<0 || i + j - 1>StrLength(s)) return str; //参数不正确时返回空串
	for (k = 1; k < i; k++) //将s的前i-1个结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	for (k = 0; k < j; k++) p = p->next; //让p沿next跳j个结点
	while (p1 != NULL) //将t的所有结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p1->data;
		r->next = q;
		r = q;
		p1 = p1->next;
	}
	while (p != NULL) //将p结点及其后的结点复制到str
	{
		q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
		q->data = p->data;
		r->next = q;
		r = q;
		p = p->next;
	}
	r->next = NULL; //尾结点的next域置为空
	return str;
}
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

输出串—DispStr(s)

• 输出链串s的所有元素值。

void DispStr(LinkStrNode* s)
{
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

主函数验证

int main()
{
	LinkStrNode* s, * t, * str;
	char cstr1[] = "Can you speak Chinese?";
	//生成串s和t
	printf("-----生成串s和t-----\n");
	StrAssign(s, cstr1);
	printf("s：");
	DispStr(s);
	printf("s.length=%d\n", StrLength(s));
	char cstr2[] = "Yes,I can!";
	StrAssign(t, cstr2);
	printf("t：");
	DispStr(t);
	printf("t.length=%d\n", StrLength(t));

	//串的连接
	printf("\n-----串的连接-----\n");
	str = Concat(s, t);
	printf("str：");
	DispStr(str);
	printf("str.length=%d\n", StrLength(str));

	//串的复制
	printf("\n-----串的复制-----\n");
	StrCopy(s, t);
	printf("s：");
	DispStr(s);
	printf("s.length=%d\n", StrLength(s));

	//判断串相等
	printf("\n-----判断串相等-----\n");
	printf("串s和t相等吗？— %d\n", StrEqual(s, t));

	//求子串
	printf("\n-----求子串-----\n");
	str = SubStr(s, 6, 4);
	printf("str：");
	DispStr(str);
	printf("str.length=%d\n", StrLength(str));

	//子串的删除
	printf("\n-----子串的删除-----\n");
	str = DelStr(s, 4, 6);
	printf("str：");
	DispStr(str);
	printf("str.length=%d\n", StrLength(str));

	//子串的插入
	printf("\n-----子串的插入-----\n");
	str = RepStr(s, 5, 6, t);
	printf("str：");
	DispStr(str);
	printf("str.length=%d\n", StrLength(str));
	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

分析

• 以上算法中的插入均采用尾插法创建。
• 运行结果：