1. AI技术聚合首页
  2. IT

探索数据结构：顺序串与链式串的深入理解

社会演员多 • • IT • 阅读 70

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 串的定义

串是一种特殊的顺序表，即每一个元素都是单独一个字符。在C语言中我们学习的字符串便是串的一种，它在我们的数据搜索与文本编译中起着不可或缺的作用。

img

特别注意：空格也是一个字符！！

下面是与串相关概念：

  • 串的长度：指串中有效元素的个数(不包括字符\0)。
  • 空串：不含任何元素的串，即长度为0。
  • 子序列：抽取串的一些字符，按照原字符串的顺序进行放置的新串。
  • 子串：串中任意连续字符组成的子序列称为该串的子串，其中空串是任意串的子串。
  • 主串：包含子串的串称为该子串的主串。

2. 串的实现方式

串是一种特殊的顺序表，所以实现方式也与顺序表类似，分别以顺序表和链表来实现。

  1. 顺序实现

img

  1. 链式实现

img

3. 串的功能

  1. 串的初始化
  2. 串的生成。
  3. 串的复制。
  4. 判断两个串是否相等。
  5. 返回串的长度。
  6. 链接两个串。
  7. 取子串。
  8. 在串1的指定位置插入串2。
  9. 删除指定位置长度为n的某个子串。

4. 串的声明

4.1. 顺序串

顺序串的存储自然是以顺序表的形式，但是在定义其长度有三种实现方式，如下：

  1. 初始化一个头结点作为长度的存储。

img

但是这种存储有一个明显的缺点就是char类型的最大表示范围为255，所以这种方式并不可取。

  1. 以字符\0作为结束标志。

img

C/C++中的字符串就是以这种实现方式，但是这种实现方式每次求长度都需要遍历整个顺序表。所以在这里也不是特别好。

  1. 添加为结构体成员。

img

这种实现方式相较于前两种更加合理，后续我们也将以这种方式实现。

同时为了方便扩容，我们可以再增加一个结构体成员capacity。

#define MAXSIZE 50
typedef struct string
{
	char *data;
	int length;
	int capacity;
}Sstring;

4.2. 链式串

链式串我们使用单链表来实现，为了方便操作我们可以添加一个头节点。

typedef struct snode 
{
	char data;
	struct snode* next;
}LinkStrNode;

5. 串的初始化

5.1. 顺序串

void StrInit(Sstring* s)//初始化串
{
	char *arr = (char*)malloc(sizeof(char) * MAXSIZE);
	if (arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	s->data = arr;
	s->length = 0;
	s->capacity = MAXSIZE;
}

5.2. 链式串

链式串并不需要单独初始化，可以在具体的实现中初始化。

5.3. 复杂度分析

  • 时间复杂度：顺序串花费时间是一个常数，所以时间复杂度为O(1)。
  • 空间复杂度：初始化开辟了MAXSIZE的空间。可以视为O(N)的复杂度。

6. 串的生成

6.1. 顺序串

在对串进行拷贝时，要检查是否需要扩容，放置越界。

void CheckCapacity(Sstring* s, int len)
{
	if (s->length + len > s->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * (s->length + len));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = MAXSIZE + len;
	}
}
void StrAssign(Sstring* s, char*str)//生成串
{
	assert(s && str);
	int i = 0;
	int len = strlen(str);
	CheckCapacity(s, len);
	for (i = 0; str[i] != '\0'; i++)
	{
		s->data[i] = str[i];
	}
	s->length = len;
}

6.2. 链式串

链式串每次插入都要生成一个节点，所以我们可以单独封装成一个函数。

LinkStrNode* BuyListNode()
{
	LinkStrNode*tmp= (LinkStrNode*)malloc(sizeof(LinkStrNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	return tmp;
}
void StrAssign(LinkStrNode** s, char*str)
{
	assert(str);
	LinkStrNode* r, * p;
	*s = BuyListNode();
	r = *s;
	for (int i = 0; str[i] != '\0'; ++i)
	{
		p = BuyListNode();
		p->data = str[i];
		r->next = p;	
		r = p;
	}
	r->next = NULL;
}

6.3. 复杂度分析

  • 时间复杂度：无论是顺序串还是链式串都需要遍历一遍目标串，间复杂度可以视为O(N))。
  • 空间复杂度：顺序串可能会扩容，链式串需要开辟等量节点，所以空间复杂度可以视为O(N)。

7. 串的复制

7.1. 顺序串

串的复制也需要检查是否需要扩容，然后再依次拷贝。

void StrCopy(Sstring* s, Sstring* t)//复制串
{
	assert(s && t);
	if (s->capacity < t->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * t->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = t->capacity;
	}
	for (int i = 0; i < t->length; i++)
	{
		s->data[i] = t->data[i];
	}
	s->length = t->length;
}

7.2. 链式串

链式串的拷贝我们采用一种方法：即先将原串销毁，然后再拷贝。

void StrCopy(LinkStrNode** s, LinkStrNode* t)//复杂
{
	assert(t);
	DestroyStr(*s);//销毁
	LinkStrNode* r, * q;
	LinkStrNode* p = t->next;
	*s = BuyListNode();
	r = *s;
	while (p != NULL)
	{
		q = BuyListNode();
		q->data = p->data;		

		r->next = q;
		r = q;			

		p = p->next;
	}
	r->next = NULL;
}

7.3. 复杂度分析

  • 时间复杂度：需要遍历一遍被复制串，所以时间复杂度可以视为O(N)。
  • 空间复杂度：顺序串可能扩容，链式串需要复制等量节点，所以空间复杂度可以视为O(N)。

8. 串的比较

串的比较与C语言中strcmp函数功能类似，都是依次比较串中的字符，直至结束或者出现不同的字符为至。

若大于则返回>0，等于返回0，小于则返回<0。

列如：

  • 当串长度不同时：“aabc”>“abbca”，“aaa”<“aaab”。
  • 当串长度相同时：“acbc”>“bcbc”，“acac”=“acac”。

8.1. 顺序串

int StrCmp(Sstring* s, Sstring* t)//比较两个串
{
	assert(s && t);
	char* p1 = s->data;
	char* p2 = t->data;
	int i = 0;
	while (i < s->length && i < t->length && p1[i] == p2[i])
	{
		i++;
	}
	if (i == s->length&&i==t->length)
	{
		return 0;
	}
	if (i == s->length && i != t->length)
	{
		return -1;
	}
	if (i != s->length && i == t->length)
	{
		return 1;
	}
	return p1[i] - p2[i];
}

8.2. 链式串

int StrCmp(LinkStrNode* s, LinkStrNode* t)//比较两个串
{
	assert(s&&t);
	LinkStrNode* p = s->next, * q = t->next;
	while (p != NULL && q != NULL && p->data == q->data)
	{
		p = p->next;
		q = q->next;
	}
	if (p == NULL&&q == NULL)		
		return 0;
	if (p == NULL && q != NULL)
	{
		return -1;
	}
	if (p != NULL && q == NULL)
	{
		return 1;
	}
	return p->data - q->data;
}

8.3. 复杂度分析

  • 时间复杂度：无论是链式串还是顺序串都可能遍历整个串，所以时间复杂度可以视为O(N)
  • 空间复杂度：无论是顺序串还是链式串花费空间是一个常数，所以空间复杂度为O(1)。

9. 返回串的长度

9.1. 顺序串

int StrLength(Sstring* s)//返回串的长度
{
	assert(s);
	return s->length;
}

9.2. 链式串

int StrLength(LinkStrNode* s)//返回串的长度
{
	assert(s);
	int count = 0;
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}

9.3. 复杂度分析

  • 时间复杂度：顺序串是一个常数，所以时间复杂度为O(1)。但是链式串需要遍历整个串，所以为O(N)。
  • 空间复杂度：无论是顺序串还是链式串花费空间是一个常数，所以空间复杂度为O(1)。

10. 链接两个串

链接两个串十分简单，首先找个一个串的末尾，然后再链接即可。

10.1. 顺序串

链接两个串也需要判断该串是否需要扩容。

Sstring Strcat(Sstring* s, Sstring* t)//链接两个串
{
	assert(s && t);
	int len = t->length;
	CheckCapacity(s, len);
	for (int i = s->length; i < s->length + t->length; i++)
	{
		s->data[i] = t->data[i - s->length];
	}
	s->length = s->length + t->length;
	return *s;
}

10.2. 链式串

LinkStrNode*Strcat(LinkStrNode* s, LinkStrNode* t)//链接两个串
{
	assert(s && t);
	LinkStrNode* p = s->next, * q = t->next;
	while (p->next != NULL)
	{
		p = p->next;
	}
	LinkStrNode* str1 = p,*str2;
	while (q != NULL)
	{
		str2 = BuyListNode();
		str2->data =q->data;

		str1->next = str2;
		str1 = str2;

		q = q->next;
	}
	str1->next = NULL;
	return s;
}

10.3. 复杂度分析

  • 时间复杂度：无论是顺序串还是链式串都需要遍历两个串，所以时间复杂度为O(N)。
  • 空间复杂度：顺序串可能会扩容，链式串需要开辟等量节点，所以空间复杂度为O(N)

11. 取子串

我们通过传入的目标位置与长度来截取一段子串返回，如果长度过大则截取后续所有字符。

11.1. 顺序串

Sstring SubStr(Sstring* s, int i, int len)//取子串
{
	assert(i < s->length);
	assert(s);
	Sstring str;
	str.data = (char*)malloc(sizeof(char) * s->capacity);
	if (str.data == NULL)
	{
		perror("malloc fail");
		return *s;
	}
	str.capacity = s->capacity;
	if (i + len >= s->length)
	{
		for (int pos = i; pos < s->length; pos++)
		{
			str.data[pos-i] = s->data[pos];
		}
		str.length = s->length - i;
	}
	else
	{
		for (int pos = i; pos < i+len; pos++)
		{
			str.data[pos - i] = s->data[pos];
		}
		str.length = len;
	}
	return str;
}

11.2. 链式串

LinkStrNode*SubStr(LinkStrNode* s, int i, int len)//取子串
{
	assert(s);
	assert(i <= StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;//跳过头节点
	r = BuyListNode();
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		p = p->next;
	}
	LinkStrNode* str1=r,*str2;
	while (len--&&p!=NULL)
	{
		str2 = BuyListNode();
		str2->data = p->data;
		str1->next = str2;
		str1 = str2;
		p = p->next;
	}
	str1->next = NULL;//末尾置空
	return r;
}

11.3. 复杂度分析

  • 时间复杂度：都可能遍历整个串，所以时间复杂度为O(N)。
  • 空间复杂度：都需要开辟len个大小的空间，所以空间复杂度可以视为O(N)。

12. 指定位置插入

12.1. 顺序串

指定位置插入也许检查是否扩容，然后指定位置后续字符移动len个单位。

img

img

Sstring InsStr(Sstring* s1, int i, Sstring* s2)//指定位置插入
{
	assert(s1 && s2);
	assert(i < s1->length);
	int len = s2->length;
	CheckCapacity(s1, len);
	for (int pos = s1->length - 1; pos >= i; pos--)
	{
		s1->data[pos + len] = s1->data[pos];
	}
	for (int pos = i; pos < i + len; pos++)
	{
		s1->data[pos] = s2->data[pos - i];
	}
	s1->length += len;
	return *s1;
}

12.2. 链式串

LinkStrNode*InsStr(LinkStrNode* s1, int i, LinkStrNode* s2)//指定位置插入
{
	assert(s1&&s2);
	assert(i <= StrLength(s1));
	int count = 0;
	LinkStrNode* r, * p,*q;
	q=p = s1->next;//q为i之前的位置
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		q = p;//记录前一个位置
		p = p->next;
	}
	r = q;
	LinkStrNode* str;
	LinkStrNode* ptr=s2->next;//跳过头节点
	while (ptr != NULL)
	{
		str = BuyListNode();
		str->data = ptr->data;
		r->next = str;
		r = str;
		ptr = ptr->next;
	}
	r->next= p;//链接
	return s1;
}

12.3. 复杂度分析

  • 时间复杂度：顺序串需要移动覆盖，链式串需要寻找目标位置，时间复杂度都可以视为O(N)。
  • 空间复杂度：顺序串可能扩容，链式串需要开辟等量空间，空间复杂度都可以视为O(N)。

13. 指定删除子串

13.1. 顺序串

如果删除的长度过长，只需要修改串的length。否则需要从前往后覆盖。

Sstring DelStr(Sstring* s, int i, int len)//指定删除子串
{
	assert(i < s->length);
	assert(s);
	if (i + len >=s->length)
	{
		s->length = i ;
	}
	else
	{
		for (int pos = i+len; pos <s->length; pos++)
		{
			s->data[pos-len] = s->data[pos];
		}
		s->length -= len;
	}
	return *s;
}

13.2. 链式串

LinkStrNode* DelStr(LinkStrNode* s, int i, int len)//指定删除子串
{
	assert(s);
	assert(i < StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;
	r = p;//r为前一个节点
	while (p != NULL)
	{
		count++;
		if (count == i)
		{
			break;
		}
		r = p;
		p = p->next;
	}
	while (len-- && p != NULL)
	{
		LinkStrNode* str = p->next;
		free(p);
		p = str;
	}
	r->next = p;
	return s;
}

13.3. 复杂度分析

  • 时间复杂度：顺序串可能需要移动覆盖，链式串需要寻找目标位置，时间复杂度都可以视为O(N)。
  • 空间复杂度：顺序串与链式串都不需要开辟格外空间，空间复杂度都可以视为O(1)。

14. 串的打印

14.1. 顺序串

void PrintStr(Sstring* s)
{
	assert(s);
	char* p = s->data;
	for (int i = 0; i < s->length; i++)
	{
		printf("%c", p[i]);
	}
	printf("\n");
}

14.2. 链式串

void PrintStr(LinkStrNode* s)//打印
{
	assert(s);
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}

14.3. 复杂度分析

  • 时间复杂度：无论是顺序串还是链式串都需要遍历整个串，所以时间复杂度为O(N)。
  • 空间复杂度：顺序串与链式串都不需要开辟格外空间，空间复杂度都可以视为O(1)。

15. 串的销毁

15.1. 顺序串

void StrDestroy(Sstring* s)//销毁串
{
	free(s->data);
	s->data = NULL;
	s->length = s->capacity = 0;
}

15.2. 链式串

void DestroyStr(LinkStrNode* s)//销毁
{
	LinkStrNode* pre = s, * p = s->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}

15.3. 复杂度分析

  • 时间复杂度：顺序串消耗时间固定，时间复杂度为O(1)。链式串需要遍历这个串，时间复杂度为O(N)
  • 空间复杂度：顺序串与链式串都不需要开辟格外空间，空间复杂度都可以视为O(1)。

16. 对比与应用

16.1. 对比

因为串也是一种顺序表，所以无论是顺序表还是链式串的优劣都与顺序表与链表差不多。这里就不在赘述。

16.2. 应用

串在计算机领域有着广泛的应用：

  1. **文本处理：**文本编辑器或处理器中，文本被表示为一个字符串，可以进行查找、替换、插入、删除等操作
  2. 加密和安全：加密算法中经常使用字符串表示数据，例如对称加密和非对称加密中的密钥和明文。

17. 完整代码

17.1. 顺序串

17.1.1. Sstring.h
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
#define MAXSIZE 50
typedef struct string
{
	char *data;
	int length;
	int capacity;
}Sstring;
void StrInit(Sstring* s);//初始化串
void StrAssign(Sstring* s, char str[]);//生成串
void StrCopy(Sstring* s, Sstring*t);//复制串
int StrCmp(Sstring*s, Sstring*t);//比较两个串
int StrLength(Sstring*s);//返回串的长度
Sstring Strcat(Sstring*s, Sstring*t);//链接两个串
Sstring SubStr(Sstring* s, int i, int len);//取子串
Sstring InsStr(Sstring* s1, int i, Sstring* s2);//指定位置插入
Sstring DelStr(Sstring* s, int i, int len);//指定删除子串
void PrintStr(Sstring* s);//打印
void StrDestroy(Sstring* s);//销毁串
17.1.2. Sstring.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sstring.h"
void CheckCapacity(Sstring* s, int len)
{
	if (s->length + len > s->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * (s->length + len));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = MAXSIZE + len;
	}
}
void StrInit(Sstring* s)//初始化串
{
	char *arr = (char*)malloc(sizeof(char) * MAXSIZE);
	if (arr == NULL)
	{
		perror("malloc fail");
		return;
	}
	s->data = arr;
	s->length = 0;
	s->capacity = MAXSIZE;
}
void StrAssign(Sstring* s, char*str)//生成串
{
	assert(s && str);
	int i = 0;
	int len = strlen(str);
	CheckCapacity(s, len);
	for (i = 0; str[i] != '\0'; i++)
	{
		s->data[i] = str[i];
	}
	s->length = len;
}
void StrCopy(Sstring* s, Sstring* t)//复制串
{
	assert(s && t);
	if (s->capacity < t->capacity)
	{
		char* tmp = (char*)realloc(s->data, sizeof(char) * t->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		s->data = tmp;
		s->capacity = t->capacity;
	}
	for (int i = 0; i < t->length; i++)
	{
		s->data[i] = t->data[i];
	}
	s->length = s->length > t->length ? s->length : t->length;
}
int StrCmp(Sstring* s, Sstring* t)//比较两个串
{
	assert(s && t);
	char* p1 = s->data;
	char* p2 = t->data;
	int i = 0;
	while (i < s->length && i < t->length && p1[i] == p2[i])
	{
		i++;
	}
	if (i == s->length&&i==t->length)
	{
		return 0;
	}
	if (i == s->length && i != t->length)
	{
		return -1;
	}
	if (i != s->length && i == t->length)
	{
		return 1;
	}
	return p1[i] - p2[i];
}
int StrLength(Sstring* s)//返回串的长度
{
	assert(s);
	return s->length;
}
Sstring Strcat(Sstring* s, Sstring* t)//链接两个串
{
	assert(s && t);
	int len = t->length;
	CheckCapacity(s, len);
	for (int i = s->length; i < s->length + t->length; i++)
	{
		s->data[i] = t->data[i - s->length];
	}
	s->length = s->length + t->length;
	return *s;
}
Sstring SubStr(Sstring* s, int i, int len)//取子串
{
	assert(i < s->length);
	assert(s);
	Sstring str;
	str.data = (char*)malloc(sizeof(char) * s->capacity);
	if (str.data == NULL)
	{
		perror("malloc fail");
		return *s;
	}
	str.capacity = s->capacity;
	if (i + len >= s->length)
	{
		for (int pos = i; pos < s->length; pos++)
		{
			str.data[pos-i] = s->data[pos];
		}
		str.length = s->length - i;
	}
	else
	{
		for (int pos = i; pos < i+len; pos++)
		{
			str.data[pos - i] = s->data[pos];
		}
		str.length = len;
	}
	return str;
}
Sstring InsStr(Sstring* s1, int i, Sstring* s2)//指定位置插入
{
	assert(s1 && s2);
	assert(i < s1->length);
	int len = s2->length;
	CheckCapacity(s1, len);
	for (int pos = s1->length - 1; pos >= i; pos--)
	{
		s1->data[pos + len] = s1->data[pos];
	}
	for (int pos = i; pos < i + len; pos++)
	{
		s1->data[pos] = s2->data[pos - i];
	}
	s1->length += len;
	return *s1;
}
Sstring DelStr(Sstring* s, int i, int len)//指定删除子串
{
	assert(i < s->length);
	assert(s);
	if (i + len >=s->length)
	{
		s->length = i ;
	}
	else
	{
		for (int pos = i+len; pos <s->length; pos++)
		{
			s->data[pos-len] = s->data[pos];
		}
		s->length -= len;
	}
	return *s;
}
void PrintStr(Sstring* s)
{
	assert(s);
	char* p = s->data;
	for (int i = 0; i < s->length; i++)
	{
		printf("%c", p[i]);
	}
	printf("\n");
}
void StrDestroy(Sstring* s)//销毁串
{
	free(s->data);
	s->data = NULL;
	s->length = s->capacity = 0;
}

17.2. 链式串

17.2.1. Sstring.h
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
typedef struct snode 
{
	char data;
	struct snode* next;
}LinkStrNode;
void StrInit(LinkStrNode* s);//初始化串
void StrAssign(LinkStrNode**s, char str[]);//生成串
void StrCopy(LinkStrNode**s, LinkStrNode*t);//复制串
int StrCmp(LinkStrNode*s, LinkStrNode*t);//比较两个串
int StrLength(LinkStrNode*s);//返回串的长度
LinkStrNode*Strcat(LinkStrNode*s, LinkStrNode*t);//链接两个串
LinkStrNode*SubStr(LinkStrNode* s, int i, int len);//取子串
LinkStrNode*InsStr(LinkStrNode* s1, int i, LinkStrNode* s2);//指定位置插入
LinkStrNode*DelStr(LinkStrNode* s, int i, int len);//指定删除子串
void PrintStr(LinkStrNode* s);//打印
void DestroyStr(LinkStrNode* s);//销毁串
17.2.2. Sstring.c
#include"Sstring.h"
LinkStrNode* BuyListNode()
{
	LinkStrNode*tmp= (LinkStrNode*)malloc(sizeof(LinkStrNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	return tmp;
}
void StrAssign(LinkStrNode** s, char*str)
{
	assert(str);
	LinkStrNode* r, * p;
	*s = BuyListNode();
	r = *s;
	for (int i = 0; str[i] != '\0'; ++i)
	{
		p = BuyListNode();
		p->data = str[i];
		r->next = p;	
		r = p;
	}
	r->next = NULL;
}

void StrCopy(LinkStrNode** s, LinkStrNode* t)
{
	assert(t);
	DestroyStr(*s);
	LinkStrNode* r, * q;
	LinkStrNode* p = t->next;
	*s = BuyListNode();
	r = *s;
	while (p != NULL)
	{
		q = BuyListNode();
		q->data = p->data;		

		r->next = q;
		r = q;			

		p = p->next;
	}
	r->next = NULL;
}

int StrCmp(LinkStrNode* s, LinkStrNode* t)//比较两个串
{
	assert(s&&t);
	LinkStrNode* p = s->next, * q = t->next;
	while (p != NULL && q != NULL && p->data == q->data)
	{
		p = p->next;
		q = q->next;
	}
	if (p == NULL&&q == NULL)		
		return 0;
	if (p == NULL && q != NULL)
	{
		return -1;
	}
	if (p != NULL && q == NULL)
	{
		return 1;
	}
	return p->data - q->data;
}
int StrLength(LinkStrNode* s)//返回串的长度
{
	assert(s);
	int count = 0;
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		count++;
		p = p->next;
	}
	return count;
}
LinkStrNode*Strcat(LinkStrNode* s, LinkStrNode* t)//链接两个串
{
	assert(s && t);
	LinkStrNode* p = s->next, * q = t->next;
	while (p->next != NULL)
	{
		p = p->next;
	}
	LinkStrNode* str1 = p,*str2;
	while (q != NULL)
	{
		str2 = BuyListNode();
		str2->data =q->data;

		str1->next = str2;
		str1 = str2;

		q = q->next;
	}
	str1->next = NULL;
	return s;
}
LinkStrNode*SubStr(LinkStrNode* s, int i, int len)//取子串
{
	assert(s);
	assert(i <= StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;//跳过头节点
	r = BuyListNode();
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		p = p->next;
	}
	LinkStrNode* str1=r,*str2;
	while (len--&&p!=NULL)
	{
		str2 = BuyListNode();
		str2->data = p->data;
		str1->next = str2;
		str1 = str2;
		p = p->next;
	}
	str1->next = NULL;//末尾置空
	return r;
}
LinkStrNode*InsStr(LinkStrNode* s1, int i, LinkStrNode* s2)//指定位置插入
{
	assert(s1&&s2);
	assert(i <= StrLength(s1));
	int count = 0;
	LinkStrNode* r, * p,*q;
	q=p = s1->next;//q为i之前的位置
	while (p != NULL)//找到第i个位置
	{
		count++;
		if (count == i)
		{
			break;
		}
		q = p;//记录前一个位置
		p = p->next;
	}
	r = q;
	LinkStrNode* str;
	LinkStrNode* ptr=s2->next;//跳过头节点
	while (ptr != NULL)
	{
		str = BuyListNode();
		str->data = ptr->data;
		r->next = str;
		r = str;
		ptr = ptr->next;
	}
	r->next= p;//链接
	return s1;
}
LinkStrNode* DelStr(LinkStrNode* s, int i, int len)//指定删除子串
{
	assert(s);
	assert(i < StrLength(s));
	int count = 0;
	LinkStrNode* r, * p;
	p = s->next;
	r = p;//r为前一个节点
	while (p != NULL)
	{
		count++;
		if (count == i)
		{
			break;
		}
		r = p;
		p = p->next;
	}
	while (len-- && p != NULL)
	{
		LinkStrNode* str = p->next;
		free(p);
		p = str;
	}
	r->next = p;
	return s;
}
void PrintStr(LinkStrNode* s)//打印
{
	assert(s);
	LinkStrNode* p = s->next;
	while (p != NULL)
	{
		printf("%c", p->data);
		p = p->next;
	}
	printf("\n");
}
void DestroyStr(LinkStrNode* s)//销毁
{
	LinkStrNode* pre = s, * p = s->next;
	while (p != NULL)
	{
		free(pre);
		pre = p;
		p = p->next;
	}
	free(pre);
}

版权声明：本文为博主作者：Betty’s Sweet原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/Bettysweetyaaa/article/details/137759497

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐