当前位置:   article > 正文

数据结构—链串 Ⅶ

链串

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

串 的 基 本 操 作 { 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 ) — 输 出 串 串的基本操作

{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)
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

分析

  • 以上算法中的插入均采用尾插法创建。
  • 运行结果:
    在这里插入图片描述
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/670405
推荐阅读
相关标签
  

闽ICP备14008679号