探索数据结构：顺序串与链式串的深入理解-Toy模板网

这篇具有很好参考价值的文章主要介绍了探索数据结构：顺序串与链式串的深入理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

1. 串的定义

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

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

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

下面是与串相关概念：

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

2. 串的实现方式

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

顺序实现

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

链式实现

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

3. 串的功能

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

4. 串的声明

4.1. 顺序串

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

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

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

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

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

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

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

添加为结构体成员。

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

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

同时为了方便扩容，我们可以再增加一个结构体成员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个单位。

探索数据结构：顺序串与链式串的深入理解,数据结构与算法：C/C++全解析,c语言,数据结构,学习,串,链式串,顺序串

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. 应用

串在计算机领域有着广泛的应用：文章来源地址https://www.toymoban.com/news/detail-854263.html

**文本处理：**文本编辑器或处理器中，文本被表示为一个字符串，可以进行查找、替换、插入、删除等操作

加密和安全：加密算法中经常使用字符串表示数据，例如对称加密和非对称加密中的密钥和明文。

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);
}