本文，大家带来数据结构中串的存储结构之顺序串，了解其基本实现及算法
🌳结构声明
对于顺序串，其实和顺序表类似，其结构声明如下
- 这里的MAX值尽量设大一些，不要这么吝啬😀，不然你会感受到【栈溢出】一直调试的痛苦😟
#define MAX 100
typedef struct {
char data[MAX];
int length;
}SqString;- 需要一个数据域和一个长度
🌳分步算法实现分析【⭐⭐⭐】
🍃生成串
- 第一个算法比较简易，只需要将一个字符串常量赋给顺序串即可
- 首先去遍历这个字符串，一一做赋值操作，最后更新一个顺序串s的长度即可
void StrAssign(SqString& s, char cstr[])
{
int i = 0;
for (i = 0; cstr[i] != '\0'; ++i)
s.data[i] = cstr[i];
s.length = i; //串的长度为遍历完cstr所需的i的大小
}🍃销毁串
- 因为顺序串是直接采用这个串本身来表示的，而不是顺序串指针。
- 所以它的存储空间由操作系统管理，即由操作系统为其分配存储空间，并在超出作用域时释放其存储空间。==因此这里的销毁顺序串不需要包含任何操作==
void DestroyStr(SqString& s) {}
//自动分配，自动销毁🍃串的复制
- 对于串的复制，不新增一个串，直接将串t的内容给到串s,因此串s需要做引用才可以
- 循环遍历串t的内容，一一做赋值给到串s即可，然后将串s的长度更新为串t的长度
void StrCopy(SqString& s, SqString t)
{
for (int i = 0; i < t.length; ++i)
s.data[i] = t.data[i];
s.length = t.length;
}🍃判断两个串是否相等
- 要判断两个串是否相等，首先应该要去判断两个串的长度是否相同，若是长度不相同，直接返回false即可
- 当这个长度相同之后，再去判断内容是否相同，若是内容不相同，返回false，跳出当前循环的判断
- 最后当不同的条件都判断完后，跳出循环，说明两个串是相同的，这时返回开头定义的布尔类型same
bool StrEqual(SqString s, SqString t)
{
bool same = true;
if (s.length != t.length) //先判断两个串的长度是否相同
return false;
else
{ //若串相同，则判断两个串的内容是否相同
for (int i = 0; i < s.length; ++i)
{
if (s.data[i] != t.data[i])
{
return false;
break;
}
}
return same; //若相等，则返回same本身的值
}
}🍃求串的长度
int StrLength(SqString s)
{
return s.length;
}🍃连接两个串
- 连接两个串的，需要在函数内部新建一个串，用于存储连接后的串，
- 首先设置这个串的长度，为串s和串t的长度和，然后通过循环，首先将串s中的内容放到str中；然后在通过一个循环，将串t放入str中，此时要注意【str.data[s.length + j]】，是在串s长度的基础上进行的添加，意思就是添加在串s的后面
- 最后看到函数的返回类型，直接返回这个串即可
SqString Concat(SqString s, SqString t)
{
SqString str; //新建一个串，用于存放连接后的串
str.length = s.length + t.length;
for (int i = 0; i < s.length; ++i)
str.data[i] = s.data[i]; //先将串s中的数据放入str
for (int j = 0; j < t.length; ++j)
str.data[s.length + j] = t.data[j]; //然后在串str后接上串t
//从串s的长度开始计算
return str;
}接下去开始烧脑部分，做好准备:ocean:
🍃取子串
- 对于取子串，对于参数，肯定是需要一个顺序串，然后要取子串的起始位置，以及需要取多长的子串
- 我们来看一下，首先是需要创建一个新的串来保存取到的子串，首先要初始化其长度，设置为0。然后就要去判断你需要取的这个子串是否合法起始位置<=0或者是>串s的长度都是不可以的，【i - 1 + j】值得就是你所取到的子串长，因为是子串，所以不可以和这个串相同，更不可以比这个串长。若是上述满足其一，则直接返回这个空串即可
- 若是上述不满足，说明要取的子串是合法的，说一下为什么从i - 1开始，因为传入的是一个==逻辑位置==，比如说要从第二个位置开始取，去三个，那么这个第二个位置在数组中的下标位置对应的就是1，因此需要i - 1,这个叫做==物理位置==
- 然后来解释一下为什么是【k - i + 1】,看循环结束位置是【i - 1 + j】,做一个等式变换就是j = k - i + 1，这也就是需要截取的子串长，也就是在str中需要放置的是这个长度，所以【str.data[k - i + 1] = s.data[k];】就是将串s中符合条件的子串起始位置到终止位置一一放入串str中，并且它们的长度都是规定好的
- 最后更新str的长度为j，也就是需要取的子串长度，返回即可
SqString SubStr(SqString s, int i, int j)
{ //会创建一个新的串来保存，故而不需引用
SqString str;
str.length = 0; //创建新串并初始化
//对传入的i与j的值进行判断
if (i <= 0 || i > s.length || i - 1 + j > s.length)
return str; //若不符合则返回空串
else
{
for (int k = i - 1; k < i - 1 + j; ++k)
str.data[k - i + 1] = s.data[k];
str.length = j; //取了多少个字符即长度为多少
return str;
}
}🍃在串1指定位置插入串2
- 从这个算法开始，你要了解什么是边界条件的判断，这个实现一些数据结构的时候很为重要
- 这里的参数是目标串s1，插入串s2，以及要插入的位置，无需插入串的长度，直接获取即可
- 开头定义同理，然后进行一个条件判断，说一下这里为什么没有去判断长度问题，==因为在插入一个串的时候，在前面中间或者是后面插入都可以，无需进行判断==。然后这里对于插入位置的判断【i > s1.length + 1】里面的i为什么要>length + 1而不是length呢，举个例子
- 看下图，箭头指向的位置就是i，也就是将要插入的位置，在【length】位置插入是可以的，然后刚才说过，在【length + 1】位置插入也是可以的，因为是在这个串的后面，相当于接上一个串，但是这个i > length + 1就不可以了，从图中看出，就无法去作出一个连接了。这就是我要强调的第一个边界条件
- 接下来就要开始正式的插入了，分为三个步骤
- 第一步，首先将串s分为两段，由插入位置作为分隔标记，首先将前半部分放入串str，这里的参数不需要做任何改进，直接放入即可
- 第二步，将要插入的串s2接在插入后的前半部分的串s。对于遍历还是去遍历串s2的长度，然后【i - 1 + y】就是需要放入str的长度，赋值放入即可
- 第三步，去遍历从i - 1到s1的长度，然后【s2.length + z】便是前面在前面s2的基础上取插入这一段s1后半部分的长度
- 最后计算一下str的长度即可，为串s1和串s2的长度。最后返回即可
SqString InsStr(SqString s1, int i, SqString s2)
{ //无需传入长度，插入的是一个串，长度已经在那了
SqString str;
str.length = 0;
//判断要插入的位置是否合法
if (i <= 0 || i > s1.length + 1)
return str;
//先将串s1的前半部分放入空串
for (int x = 0; x < i - 1; ++x)
str.data[x] = s1.data[x];
//接着将串s2插入到传入的位置i
for (int y = 0; y < s2.length; ++y)
str.data[i - 1 + y] = s2.data[y];
//最后将s1的后半部分拼接在插入完的s2之后
for (int z = i - 1; z < s1.length; ++z)
//z要从i-1的位置开始遍历，前半部分已入str
str.data[s2.length + z] = s1.data[z];
str.length = s1.length + s2.length;
return str;
}🍃删除一个串中指定长度的串
- 删除一个指定长度的串，顾名思义，就是要传入删除的位置以及要删除串的长度，然后对于删除的串也是要进行一个判断
- 这里说一下【i > s.length】而不是子串插入中的【i > s.length + 1】。看下图，对于删除一个串，它和插入不同，对于插入的话，你在【i > s.length + 1】是没有问题的，但是删除的话，这个位置是没有内容给你删的，这一点你要搞清楚，就可以一目了然了，这里就是我要说的第二个边界条件
- 然后开始删除串，这里只需要两步
- 第一步，因为是要删除从i开始的后面的串，所以【0 ~ i - 1】是需要被保留下来的，我们将其放入串str中
- 第二步，直接将删除完后的串s放入串str中即可，这里的循环初始条件本来是i + j - 1，为了大家能够更好地理解，我将其改为了i - 1 + j，也就是在i - 1这个带删除的起始位置，延伸j个位置，那么这j个位置就自然被删除了，然后在赋值的时候【y - j】也就是将这j段位置的长度删去
- 最后计算一下str的长度，因为是删除了j个字符，所以直接将s的长度减去j即可
SqString DelStr(SqString s, int i, int j)
{ //此时需要传入要删除的长度
SqString str;
str.length = 0;
//判断要插入的位置是否合法
if (i <= 0 || i > s.length || i + j > s.length + 1)
return str;
else //删除一部分串，不要那一部分，只要他的前和后
{
//从i开始删，故0~i-1个字符均保留
for (int x = 0; x < i - 1; ++x)
str.data[x] = s.data[x]; //无需修改索引，这一部分直接直接放入str即可
//i+j-1为删除完的位置，一直到串s的长度，将要删的串之后的剩余内容放入str
for (int y = i - 1 + j; y < s.length; ++y)
str.data[y - j] = s.data[y];
//y - j是因为少了j个长度
str.length = s.length - j; //-j是因为删除了j个字符
return str;
}
}🍃将一个串中从某一位置开始的指定长度替换为另一个串
最后一个，也是我认为最烧脑的一块，Are you ready:tiger:
- 这个算法你仔细看，其实和插入串那一段是非常类似的，但也是有几个小细节需要你去把控，因为一旦出了一个小错误，那么整段程序将会运行不起来，我们一起来看看
- 开头也是同理，定义一个存放串str。接着也是去判断是否合法，这里要注意，对于替换串的话这里就有小细节了。首先还是下面这张图，对于替换串的话，它是删除串其实是一个道理对于这个length + 1的位置，是没有字符去给你替换的，因此不可以到达此处
- 然后的话就是这个插入串不需要去考虑插入的长度是否合法，但是替换串的话就需要了，假设你有一个目标串是5个长度，你从2开始替换，替换长度为6，那目标串的长度就不够了，因此这也是一个边界条件
- 然后便开始了正式的替换，思路也是类似，三步走
- 第一步，首先是将替换边界的前半部分放入str中，无需考虑长度，直接放入
- 第二步，遍历所要替换的串t，【i - 1 + y】遍历所要放入str中的长度，赋值放入
- 第三步，也是尤为重要的一步，【i - 1 + j】是替换完后的位置，一直遍历到s串的后半部分，【t.length + z - j】为什么在后面还要- j呢，仔细观察，插入串是【s2.length + z】，删除串是【y - j】，替换串更像是它们的结合，这是为什么呢？我来解释一下
- 其实应该写成这样最通俗易懂【- j + t.length + z】，首先减去那段需要替换的长度，因为我们我替换的长度和原本的长度不一定时一样的，选出来是3个长度需要替换，然后替换串的长度为5，那你怎么办呢，所以干脆减去这一段需要替换的长度，后面就是需要从替换串t中拿过来拷贝的数据了，这么说你懂了吗❓
- 最后去计算str的长度其实也是运用了这个思想，直接减去这个需要替换的长度，然后加上替换串的长度，再加上前后两部分串s的长度，便是str的长度
SqString RepStr(SqString s, int i, int j, SqString t)
{ //-----与插入串类似-----
SqString str;
str.length = 0;
//判断要插入的位置是否合法
if (i <= 0 || i > s.length || i + j > s.length + 1)
return str;
else
{
//先将串s的前半部分放入空串
for (int x = 0; x < i - 1; ++x)
str.data[x] = s.data[x];
//将串t替换到指定的位置
for (int y = 0; y < t.length; ++y)
str.data[i - 1 + y] = t.data[y];
//将串s的后半部分继续放入串str
for (int z = i - 1 + j; z < s.length; ++z)
str.data[t.length + z - j] = s.data[z];
str.length = s.length - j + t.length;
//-j是因为在串s1中长度为j的这一部分被t替换调了，但不一定与t的长度一致
//所以干脆减去这一段长度并加上t的长度
//与前面的插入不同的是插入一个串只是会增加原串的长度，但是替换不一样，可能会修改原串的结构
return str;
}
}怎么样，没有骗你吧，还是有【亿些】烧脑的:ocean:
🍃输出串
- 输出串具体算法如下
void DisStr(SqString s)
{
if (s.length > 0) //只有串的长度不为0，才可输出
{
for (int i = 0; i < s.length; ++i)
{
printf("%c", s.data[i]);
}
printf("\n");
}
}🌳测试运行结果
🐚测试1
void test1()
{
SqString s;
char ch[12] = "China Daily"; //12是因为还要存放'\0'
//测试串的初始化
printf("初始化后的串s为：\n");
StrAssign(s, ch);
DisStr(s);
int len = StrLength(s);
printf("此时串的长度为：%d\n", len);
//测试串的相等
SqString s2;
SqString s3;
char ch2[12] = "Daily China";
StrAssign(s2,ch2);
char ch3[12] = "China Daily";
StrAssign(s3, ch3);
printf("s2:");
DisStr(s2);
printf("s3:");
DisStr(s3);
if (StrEqual(s, s2)) //s与s2不相等
printf("s与s2两个串相等\n");
else
printf("s与s2两个串不相等\n");
if (StrEqual(s, s3)) //s与s2相等
printf("s与s3两个串相等\n");
else
printf("s与s3两个串不相等\n");
//测试串的复制
SqString s4;
char ch4[12] = "Hello World";
StrAssign(s4, ch4);
printf("s4:");
DisStr(s4);
printf("再一次显示复制前的串s：");
DisStr(s);
StrCopy(s, s4);
printf("被s4复制后的串s为：");
DisStr(s);
//测试串的连接
SqString s5,s6,s7;
char ch5[10] = " I'm Fire";
char ch6[10] = " cloud";
char ch7[15] = "dfjhdskj";
StrAssign(s5, ch5);
StrAssign(s6, ch6);
StrAssign(s7, ch7);
printf("串s5为：");
DisStr(s5);
printf("串s6为：");
DisStr(s6);
s7 = Concat(s5, s6);
printf("串s5与串s6拼接之后为：");
DisStr(s7);
}
- 就不作过多解释，大家一步步自己去试就行，接下来我们看下一阶段的测试，由于代码过于冗长，因此我分开测试
🐚测试2
void test2()
{
SqString s1;
char ch1[12] = "Hello World";
StrAssign(s1, ch1);
//测试其一个串的子串
SqString s2;
s2 = SubStr(s1, 7, 3);
printf("从串s的第7个字符开始的连续3个字符组成的子串为：");
DisStr(s2);
//测试子串的插入
SqString s3;
SqString s4;
char ch2[6] = "river";
char ch3[20] = "ldflgjdrgjddmkj";
StrAssign(s3, ch2);
StrAssign(s4, ch3);
printf("插入子串前的s1为：");
DisStr(s1);
s4 = InsStr(s1, 12, s3); //此处专门测试了尾部边界值
printf("插入子串后的s1为：");
DisStr(s4);
//测试子串的删除
SqString s5;
SqString s6;
char ch4[12] = "countryside";
StrAssign(s5, ch4);
printf("串s5为 ：");
DisStr(s5);
printf("删去从第二个字符开始的长度为3的子串之后为：");
s6 = DelStr(s5, 2, 3);
DisStr(s6);
//测试子串的替换
SqString s7;
SqString s8;
SqString s9;
char ch5[12] = "countryside";
char ch6[4] = "man";
StrAssign(s7, ch5);
StrAssign(s8, ch6);
s9 = RepStr(s7, 8, 4, s8);
printf("将串s7从第8个字符开始的连续4个字符替换成串s8后为：");
DisStr(s9);
}
🌳整体代码展示
#include <stdio.h>
#define MAX 100
typedef struct {
char data[MAX];
int length;
}SqString;
/*生成串*/
void StrAssign(SqString& s, char cstr[])
{
int i = 0;
for (i = 0; cstr[i] != '\0'; ++i)
s.data[i] = cstr[i];
s.length = i; //串的长度为遍历完cstr所需的i的大小
}
/*销毁串*/
void DestroyStr(SqString& s){}
/*串复制*/
void StrCopy(SqString& s, SqString t)
{
for (int i = 0; i < t.length; ++i)
s.data[i] = t.data[i];
s.length = t.length;
}
/*判断串是否相等*/ //长度与内容均要相同
bool StrEqual(SqString s, SqString t)
{
bool same = true;
if (s.length != t.length) //先判断两个串的长度是否相同
return false;
else
{ //若串相同，则判断两个串的内容是否相同
for (int i = 0; i < s.length; ++i)
{
if (s.data[i] != t.data[i])
{
return false;
break;
}
}
return same; //若相等，则返回same本身的值
}
}
/*求串的长度*/
int StrLength(SqString s)
{
return s.length;
}
/*连接两个串*/
SqString Concat(SqString s, SqString t)
{
SqString str; //新建一个串，用于存放连接后的串
str.length = s.length + t.length;
for (int i = 0; i < s.length; ++i)
str.data[i] = s.data[i]; //先将串s中的数据放入str
for (int j = 0; j < t.length; ++j)
str.data[s.length+j] = t.data[j]; //然后在串s后接上串t
//从串s的长度开始计算
return str;
}
//高能预警！！！！！！
/*取子串*/
SqString SubStr(SqString s, int i, int j)
{ //会创建一个新的串来保存，故而不需引用
SqString str;
str.length = 0; //创建新串并初始化
//对传入的i与j的值进行判断
if (i<=0 || i>s.length || i + j - 1 > s.length)
return str; //若不符合则返回空串
else
{
for (int k = i - 1; k < i - 1 + j; ++k)
str.data[k - i + 1] = s.data[k];
str.length = j; //取了多少个字符即长度为多少
return str;
}
}
/*在串1指定位置插入串2*/
SqString InsStr(SqString s1, int i, SqString s2)
{ //无需传入长度，插入的是一个串，长度已经在那了
SqString str;
str.length = 0;
//判断要插入的位置是否合法
if (i <= 0 || i > s1.length + 1)
return str;
//else
//{
//先将串s1的前半部分放入空串
for (int x = 0; x < i - 1; ++x)
str.data[x] = s1.data[x];
//接着将串s2插入到传入的位置i
for (int y = 0; y < s2.length; ++y)
str.data[i - 1 + y] = s2.data[y];
//最后将s1的后半部分拼接在插入完的s2之后
for (int z = i - 1; z < s1.length; ++z)
//z要从i-1的位置开始遍历，前半部分已入str
str.data[s2.length + z] = s1.data[z];
str.length = s1.length + s2.length;
return str;
// }
}
/*删除一个串中指定长度的串*/
SqString DelStr(SqString s, int i, int j)
{ //此时需要传入要删除的长度
SqString str;
str.length = 0;
//判断要插入的位置是否合法
if (i <= 0 || i > s.length || i + j > s.length + 1)
return str;
else //删除一部分串，不要那一部分，只要他的前和后
{
//从i开始删，故0~i-1个字符均保留
for (int x = 0; x < i - 1; ++x)
str.data[x] = s.data[x]; //无需修改索引，这一部分直接直接放入str即可
//i+j-1为删除完的位置，一直到串s的长度，将要删的串之后的剩余内容放入str
for (int y = i - 1 + j; y < s.length; ++y)
str.data[y - j] = s.data[y];
str.length = s.length - j; //-j是因为删除了j个字符
return str;
}
}
/*将一个串中从某一位置开始的指定长度替换为另一个串*/
SqString RepStr(SqString s, int i, int j, SqString t)
{ //-----与插入串类似-----
SqString str;
str.length = 0;
//判断要插入的位置是否合法
if (i <= 0 || i > s.length || i + j > s.length + 1)
return str;
else
{
//先将串s的前半部分放入空串
for (int x = 0; x < i - 1; ++x)
str.data[x] = s.data[x];
//将串t替换到指定的位置
for (int y = 0; y < t.length; ++y)
str.data[i - 1 + y] = t.data[y];
//将串s的后半部分继续放入串str
for (int z = i - 1 + j; z < s.length; ++z)
str.data[t.length + z - j] = s.data[z];
str.length = s.length - j + t.length;
//-j是因为在串s1中长度为j的这一部分被t替换调了，但不一定与t的长度一致
//所以干脆减去这一段长度并加上t的长度
//与前面的插入不同的是插入一个串只是会增加原串的长度，但是替换不一样，可能会修改原串的结构
return str;
}
}
/*输出串*/
void DisStr(SqString s)
{
if (s.length > 0) //只有串的长度不为0，才可输出
{
for (int i = 0; i < s.length; ++i)
{
printf("%c", s.data[i]);
}
printf("\n");
}
}🌳总结与提炼
看完了顺序串的基本算法实现，确实是感觉其比较烧脑，对于一些循环初始的边界的控制，以及我说的边界条件的细节问题，都是大家在编写程序过程中会犯的错，这需要你去多思考、多打代码实践一下，做到孰能生巧就好了有关顺序串的算法实现就说到这里，感谢您对本文的观看，如有问题请于评论区留言或者私信我:four_leaf_clover:
