本文，大家带来数据结构中串的存储结构之链串，了解其基本实现及算法
🌳结构声明
对于链串，与单链表比较类似，其结构声明如下
typedef struct snode {
char data;
struct snode* next;
}LinkStrNode;- 也是需要一个数据域，然后既然是链式结构，那一定有指针
🌳分步算法实现分析【⭐⭐⭐】
对于链串的算法实现，不像顺序串那样简便，你需要去开辟结点空间然后将一个个结点链接起来
🍃生成串
- 首先我们来看如何使用链式思维去实现一个串
- 参数的话还是一样，一个链串类型，一个字符数组，上面说了，形成一个链串需要链式思维，那对于链表我们是怎么构建的呢？大家还记得吗，使用尾插法会来的更加好一些，因此我们下面的算法操作都是基于尾插法的来实现的，我来一步步给大家说一下
- 首先你需要定义一个头结点指针，用于头结点的存储，然后在定义一个新生结点的指针，用于存放后续结点。接着就是尾插法的基本思路，使用【malloc】开辟空间，一开始只有一个头结点，因此它就是尾结点
- 接着取遍历这个字符数组，取出里面的每一个字符，为新的结点开辟空间，然后将字符一一放入data域，将此结点链在尾结点后，然后这个结点成为新的尾结点
- 最后不要忘了将尾结点的next域置为空哦，这很重要❗
void StrAssign(LinkStrNode*& s, char cstr[])
{
LinkStrNode* r, * p;
//为头结点开辟空间
s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
r = s;
for (int i = 0; cstr[i] != '\0'; ++i)
{
//为串s的后继结点开辟空间
p = (LinkStrNode*)malloc(sizeof(LinkStrNode));
p->data = cstr[i];
//尾插法
r->next = p; r = p;
}
r->next = NULL;
}🍃销毁串
- 然后来说说如何销毁一个串，这和销毁链表其实是一个道理。
- 你要销毁一个结点，那就要判断它的下一个结点是否为空，若是不为空，就进入循环，下一个结点不为空，就free掉这个结点，然后进行一个交替更换，直至扫描完所有的结点位置
- 最后别忘了当扫描到最后一个尾结点的时候，跳出循环要单独再做一个free
void DestroyStr(LinkStrNode*& s)
{
LinkStrNode* pre = s, * p = s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}🍃串的复制
- 首先一样，是基于尾插法的整体思路，可以看到，这里是给目标串s做了一个引用，所以是要将串t复制到串s中去。
- 接着取思考一下我们的需求，我们需要一个头结点现将串s放进去，然后需要一个结点指针去扫描复制串t的，然后对于新增加的结点，还需要一个新增结点指针
- 接下去就是算法思路，具体不做讲解，与生成串一致。就是这个【q->data = p->data】，就是将p中即扫描的串t的内容放到新生结点中
void StrCopy(LinkStrNode*& s, LinkStrNode* t)
{
LinkStrNode* r, * p = t->next, * q;
//为头结点开辟空间
s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
r = s;
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data; //将串t中的结点放入q中暂存
r->next = q;
r = q; //尾插法
p = p->next;
}
r->next = NULL;
}🍃判断两个串是否相等
- 然后去比较两个串是否相等，思路很简单，我们来看看
- 首先你需要两个指针，一个指向串s的内容，另一个指向串t的内容。接着将它们放到一个循环里分别去扫描即可，若是相等的话继续向下扫描，直至尾结点位置，其中若是发现 有不相同的元素，则跳出循环
- 在循环外面，可以看到我是有两个判断，一个是判断是否两个指针都扫描到了两个串的尾部，若是，则表明两个串是相等匹配的，返回true；若不是，则表明上面的循环是中途结束的，指针并没有扫描到结尾，返回false
bool StrEqual(LinkStrNode* s, LinkStrNode* 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 true;
else
return false;
}🍃求串的长度
- 求解串的长度一样是和链表一样，从首结点开始扫描，使用循环控制，直至尾结点即可，使用一个变量记录循环次数，最后返回
int StrLength(LinkStrNode* s)
{
int i = 0;
LinkStrNode* p = s->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}🍃连接两个串
- 连接串的思路其实和顺序串一致，也是先定一个存储串，然后先将串s放入，接着再将串t做一个链接
- 一样分析一下需求：存放结果串的指针、存放串s的指针、新建的结点指针以及尾指针
- 内部思路就是尾插法的思路，便不做过多叙述。这里的话就是将这个一开始存放串s的指针p做了一个再次利用
LinkStrNode* ConCat(LinkStrNode* s, LinkStrNode* t)
{
LinkStrNode* str, * p, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
r = str;
//先将s存放到str中
p = s->next;
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
//再循环利用变量将t也存入str中，即接在s之后
p = t->next;
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}接下去又开始了我们的“烧脑部分”，做好准备:ocean:
🍃取子串
- 然后是取子串的部分，一样需要先去判断要取出的子串是否合法，若不合法，直接返回定义出来的空串即可
- 这里也是一样先使用指针p存放串s的内容，接着使用循环去遍历，但这还是用到了一个技巧，因为要取的子串是从位置i开始，那么直接使用循环遍历到了这个地方，然后的话其实就又是一个尾插法的操作，从这个位置开始，将s串中的部分一一存放到串str中，最后将尾指针置为空，返回即可
LinkStrNode* SubStr(LinkStrNode* s, int i, int j)
{
LinkStrNode* str, * p, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL; //若不将str置为空串，则输入放入会出现异常
r = str;
if (i <= 0 || i > StrLength(s) || j < 0 || i - 1 + j > StrLength(s))
return str;
//利用指针p先行遍历到位置i
p = s->next;
for (int k = 1; k < i; ++k)
p = p->next;
//在从位置i开始遍历到位置j取出子串
for (int k = 1; k <= j; ++k)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}🍃在串1指定位置插入串2
- 一样，也是顺序串的思路，先将前半部分放到目标串中，然后在后插入串，接着将后半部分继续放入即可
- 指针数量还是一样，只是多了一个指针去遍历插入串t，细心的同学在看了上篇文章后，一定也发现了这里也使用了边界条件的判断，上次我们说过，这个插入串的话是可以插入到一个串的末尾的，所以是其长度length + 1，但是超出就不行了
- 接着三步走，完成插入操作
- 第一步，将串s的前半部分，也就是从1遍历到i - 1的位置，一样使用尾插法插入
- 第二步，串s的前半部分插入完成后，使用指针p1继续去遍历串t，一样的思路放入串str中
- 第三步，放入串s的后半部分，被忘了，此时这个指针p还在i的位置，只需要继续使用这个指针p，利用尾插法插入即可
LinkStrNode* InsStr(LinkStrNode* s, int i, LinkStrNode* t)
{
int k = 1;
LinkStrNode* str, * p, * p1, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
//判断下标i是否越界
if (i <= 0 || i > StrLength(s) + 1)
return str;
//利用指针p,先将前0~i-1个字符存入str
p = s->next;
for (int k = 1; k < i; ++k)
{
q= (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
//利用指针p1,将串t中的结点顺势放入str中
p1 = t->next;
while (p1 != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p1->data;
r->next = q; r = q;
p1 = p1->next;
}
//此时的指针p，已然移动到i的位置，开始将后面的剩余结点继续存入串str中
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}🍃删除一个串中指定长度的串
- 不要看代码越来越长，其实这就是【纸老虎】，实现的思路还是很简单，内部的原理都是使用尾插法，只需要在外层控制一下指针的移动即可
- 首先一样先来看一下这个边界的判断，顺序串中说过，插入串不需要判断长度，但是删除需要，还有就是这个边界条件，目标串的最后部分是不可以被删除的，因为根本没有内容可以给你删
- 删除操作，一样是现将前i个字符放入目标串中，接着我们再度利用指针p，通过一个循环，将这j个位置直接遍历过。循环结束时,p就处于j的位置，然后利用这个指针将剩余的内容放入目标串中即可
LinkStrNode* DelStr(LinkStrNode* s, int i, int j)
{
int k = 1;
LinkStrNode* str, * p, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
if (i <= 0 || i > StrLength(s) || i - 1 + j > StrLength(s))
return str;
//利用指针p,先将前0~i-1个字符存入str
p = s->next;
for (int k = 1; k < i; ++k)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
//再利用指针p，直接遍历过j个位置
for (k = 0; k < j; ++k)
p = p->next;
//此时的指针p，已然移动到j的位置，开始将后面的剩余结点继续存入串str中
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}🍃将一个串中从某一位置开始的指定长度替换为另一个串
- 一眼望去代码很长，你会怕吗？要记住这只是【纸老虎】罢了
- 顺序串里也说到过，替换串的操作和插入串很像，你也可以再拉上去看看，是不是真的很像
- 你可以进行一个对比，然后就可以发现，又是插入和删除两个算法操作的结合
- 对于替换串来说，和删除串一样，超过length + 1的位置是不可以替换的，替换串的话不想插入串那样，不要考虑长度，替换的话肯定是要考虑你所使用的替换串的长度
- 替换操作的整体思路也会差不多，利用指针做一个后移，内部实现逻辑还是尾插法，如果你认真看了上面的内容，相信你对这一个算法不会陌生，自己分析着试试吧😀
LinkStrNode* RepStr(LinkStrNode* s, int i, int j, LinkStrNode* t)
{
int k = 1;
LinkStrNode* str, * p, * p1, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
//判断下标i是否越界
if (i <= 0 || i > StrLength(s) || j<0 || i - 1 + j>StrLength(s))
return str;
//利用指针p,先将前0~i-1个字符存入str
p = s->next;
for (int k = 1; k < i; ++k)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data; q->next = NULL;
r->next = q; r = q;
p = p->next;
}
for (k = 0; k < j; ++k)
p = p->next; //直接删除原本串s中从第i位开始长度为j的那一子串
//利用指针p1,将串t中的结点顺势放入str中
p1 = t->next;
while (p1 != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p1->data; q->next = NULL;
r->next = q; r = q;
p1 = p1->next;
}
//此时的指针p，已然移动到i的位置，开始将后面的剩余结点继续存入串str中
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data; q->next = NULL;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}🍃输出串
- 如下是输出串的算法
void DispStr(LinkStrNode* s)
{
LinkStrNode* p = s->next;
while (p != NULL)
{
printf("%c", p->data);
p = p->next;
}
printf("\n");
}🌳测试运行结果
🐚测试1
测试这一块，也是一样，分为两部分，我们先来看第一部分的测试
void test1()
{
printf("*测试串的生成*\n");
LinkStrNode* s1;
char ch1[12] = "Hello World";
StrAssign(s1, ch1);
printf("串s初始化为：");
DispStr(s1);
printf("\n*测试串的复制*\n");
LinkStrNode* s2;
char ch2[6] = "Frank";
StrAssign(s2, ch2);
StrCopy(s1, s2);
printf("复制后的串s1为：");
DispStr(s1);
printf("\n*测试串是否相等*\n");
LinkStrNode* s3, * s4, * s5;
char ch3[6] = "apple";
char ch4[6] = "apple";
char ch5[7] = "banana";
StrAssign(s3, ch3);
StrAssign(s4, ch4);
StrAssign(s5, ch5);
if (StrEqual(s3, s4))
printf("s3与s4两串相等\n");
else
printf("s3与s4两串不相等\n");
if (StrEqual(s3, s5))
printf("s3与s5两串相等\n");
else
printf("s3与s5两串不相等\n");
printf("\n*测试串的长度*\n");
int len = StrLength(s5);
printf("显示一下串s5：");
DispStr(s5);
printf("串s5的长度为：%d\n", len);
printf("\n*测试串的连接*\n");
LinkStrNode* s6;
LinkStrNode* s7;
LinkStrNode* s8;
char ch6[3] = "so";
char ch7[6] = " good";
StrAssign(s6, ch6);
StrAssign(s7, ch7);
s8 = ConCat(s6, s7);
printf("串s6与串s7连接之后为：");
DispStr(s8);
}
- 还是一样，大家自己对照我的测试过程看，非常清晰
🐚测试2
然后开始第二个测试
void test2()
{
printf("*测试求子串*\n");
LinkStrNode* s1, * s2;
char ch1[10]= "wonderful";
StrAssign(s1, ch1);
printf("初始化的串s1为：");
DispStr(s1);
printf("串s1从第2个字符开始的连续4个字符的子串为：");
s2 = SubStr(s1, 2, 4);
DispStr(s2);
printf("\n*测试子串的插入*\n");
LinkStrNode* s3,* s4;
char ch3[10] = "ok";
StrAssign(s3, ch3);
printf("在串s1的第3个位置插入串s3之后为：");
s4 = InsStr(s1, 3, s3);
DispStr(s4);
printf("\n*测试子串的删除*\n");
LinkStrNode* s5, * s6;
char ch5[10] = "fantistic";
StrAssign(s5, ch5);
printf("将串s5的第5个字符开始的长度为2的子串删除后为：");
s6 = DelStr(s5, 5, 2);
DispStr(s6);
printf("\n*测试子串的替换*\n");
LinkStrNode* s7;
LinkStrNode* s8;
LinkStrNode* s9;
char ch7[15] = "accountability";
char ch8[3] = "le";
StrAssign(s7, ch7);
StrAssign(s8, ch8);
printf("将串s7从第10个字符开始的长度为2的子串替换成s8后为：");
s9 = RepStr(s7, 10, 5, s8);
DispStr(s9);
}
🌳整体代码展示
#include <stdio.h>
#include <malloc.h>
typedef struct snode {
char data;
struct snode* next;
}LinkStrNode;
/*生成串*/
void StrAssign(LinkStrNode*& s, char cstr[])
{
LinkStrNode* r, * p;
//为头结点开辟空间
s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
r = s;
for (int i = 0; cstr[i] != '\0'; ++i)
{
//为串s的后继结点开辟空间
p = (LinkStrNode*)malloc(sizeof(LinkStrNode));
p->data = cstr[i];
//尾插法
r->next = p; r = p;
}
r->next = NULL;
}
/*摧毁串*/
void DestroyStr(LinkStrNode*& s)
{
LinkStrNode* pre = s, * p = s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
/*串的复制*/
void StrCopy(LinkStrNode*& s, LinkStrNode* t)
{
LinkStrNode* r, * p = t->next, * q;
//为头结点开辟空间
s = (LinkStrNode*)malloc(sizeof(LinkStrNode));
r = s;
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data; //将串t中的结点放入q中暂存
r->next = q;
r = q; //尾插法
p = p->next;
}
r->next = NULL;
}
/*判断串相等*/
bool StrEqual(LinkStrNode* s, LinkStrNode* 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 true;
else
return false;
}
/*求串长*/
int StrLength(LinkStrNode* s)
{
int i = 0;
LinkStrNode* p = s->next;
while (p != NULL)
{
i++;
p = p->next;
}
return i;
}
/*串的连接*/
LinkStrNode* ConCat(LinkStrNode* s, LinkStrNode* t)
{
LinkStrNode* str, * p, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
r = str;
//先将s存放到str中
p = s->next;
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
//再循环利用变量将t也存入str中，即接在s之后
p = t->next;
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}
/*求子串*/
LinkStrNode* SubStr(LinkStrNode* s, int i, int j)
{
LinkStrNode* str, * p, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL; //若不将str置为空串，则输入放入会出现异常
r = str;
if (i <= 0 || i > StrLength(s) || j<0 || i - 1 + j>StrLength(s))
return str;
//利用指向p先行遍历到位置i
p = s->next;
for (int k = 1; k < i; ++k)
p = p->next;
//在从位置i开始遍历到位置j取出子串
for (int k = 1; k <= j; ++k)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}
/*子串的插入*/
LinkStrNode* InsStr(LinkStrNode* s, int i, LinkStrNode* t)
{
int k = 1;
LinkStrNode* str, * p, * p1, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
//判断下标i是否越界
if (i <= 0 || i > StrLength(s) + 1)
return str;
//利用指针p,先将前0~i-1个字符存入str
p = s->next;
for (int k = 1; k < i; ++k)
{
q= (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
//利用指针p1,将串t中的结点顺势放入str中
p1 = t->next;
while (p1 != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p1->data;
r->next = q; r = q;
p1 = p1->next;
}
//此时的指针p，已然移动到i的位置，开始将后面的剩余结点继续存入串str中
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}
/*子串的删除*/
LinkStrNode* DelStr(LinkStrNode* s, int i, int j)
{
int k = 1;
LinkStrNode* str, * p, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
if (i <= 0 || i > StrLength(s) || i - 1 + j > StrLength(s))
return str;
//利用指针p,先将前0~i-1个字符存入str
p = s->next;
for (int k = 1; k < i; ++k)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
//再利用指针p，直接遍历过j个位置
for (k = 0; k < j; ++k)
p = p->next;
//此时的指针p，已然移动到j+1的位置，开始将后面的剩余结点继续存入串str中
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}
/*子串的替换*/
LinkStrNode* RepStr(LinkStrNode* s, int i, int j, LinkStrNode* t)
{
int k = 1;
LinkStrNode* str, * p, * p1, * q, * r;
str = (LinkStrNode*)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
//判断下标i是否越界
if (i <= 0 || i > StrLength(s) + 1 || j<0 || i - 1 + j>StrLength(s))
return str;
//利用指针p,先将前0~i-1个字符存入str
p = s->next;
for (int k = 1; k < i; ++k)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data; q->next = NULL;
r->next = q; r = q;
p = p->next;
}
for (k = 0; k < j; ++k)
p = p->next; //直接删除原本串s中从第i位开始长度为j的那一子串
//利用指针p1,将串t中的结点顺势放入str中
p1 = t->next;
while (p1 != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p1->data; q->next = NULL;
r->next = q; r = q;
p1 = p1->next;
}
//此时的指针p，已然移动到i的位置，开始将后面的剩余结点继续存入串str中
while (p != NULL)
{
q = (LinkStrNode*)malloc(sizeof(LinkStrNode));
q->data = p->data; q->next = NULL;
r->next = q; r = q;
p = p->next;
}
r->next = NULL;
return str;
}
/*输出串*/
void DispStr(LinkStrNode* s)
{
LinkStrNode* p = s->next;
while (p != NULL)
{
printf("%c", p->data);
p = p->next;
}
printf("\n");
}🌳总结与提炼
看完了链串的基本算法实现，是不是觉得并没有顺序串那么烧脑，仔细看我在中途说的烧脑打上了双引号，链串的基本算法实现其实并不难，就是底层思路我在一开头就讲了，使用==尾插法==，可以看到，虽然代码很长，但是理解起来并不难，因此完全可以说是【纸老虎】，大家不要被各种数据结构的算法实现难住了，只要你去认真思考，然后动手打打代码，其实是没有那么困难的。包括在后续我们还会讲到二叉树、图的算法实现，比这些还要困难，所以学习编程还是要有一颗强大的内心有关链串的算法实现就说到这里，感谢您对本文的观看，如有问题请于评论区留言或者私信我:four_leaf_clover:
