基于C语言的数据结构之串——带你熟练掌握串的基本操作！！超级详细！！

目录

前言

1. 数据结构——串

1.1 基本知识

主串、子串、模式串

1.2 对几个字符串库函数的简单介绍

1.2.1 strcmp

1.2.2 strcpy

1.2.3 strlen

1.2.4 strcat

1.3 串的分类

1.3.1 静态分配内存的串

1.3.2 动态分配内存的串

2. 串的基本操作

2.1 初始化串

2.2 输出字符

2.3 插入子串

2.4 删除子串

2.5 取子串操作

2.6 撤销删除操作

结束语

---

前言

掌握串之前最好先去学习好顺序表和单链表喔！串，也就是字符串。对这种数据结构的操作，相对比较简单，重点是要掌握好KMP算法哦！

顺序表传送门------>基于C语言的数据结构之顺序表——带你熟练掌握顺序表基本操作！！超级详细！！-CSDN博客

单链表传送门------>基于C语言的数据结构之单链表——带你熟练掌握单链表！！超级详细！！-CSDN博客

1. 数据结构——串

1.1 基本知识

串的本质就是字符串，但是我们是需要对串进行操作的，因此要用到结构体要存放一个字符串的更多信息。这里我们首选使用顺序表来实现串结构，链表实现在后面会讲喔！

主串、子串、模式串

我们可以把这三个词分为两组来理解：

主串和子串——主串里包含子串，比如主串abcdefg它的子串可以是abc，可以是def也可以是abcde等等

主串和模式串——模式串可以理解为一则寻人启事，它的作用是表示要在主串里查找的子串，他可能存在于主串里，也可能不在主串里。在的话，它就是主串的字串啦。

真子串——也就是于主串不相同的子串，比如主串abdcef，abcd，abcdef都是他的子串，但是只有abcd才是真子串。

1.2 对几个字符串库函数的简单介绍

对字符串进行操作离不开string.h这个库，先来简单学习或者复习一下吧！

1.2.1 strcmp

全称是string compare字符串比较。传入两个字符串地址，相同则返回0。

1.2.2 strcpy

全称是string copy字符串复制。传入两个字符串地址，把第二个地址的字符串复制到第一个里面去，跟变量赋值一样。

（可能新手都会想这用“=”给字符串赋值，其实是不可以的，要用strcpy哦！）

1.2.3 strlen

全称是string length字符串长度。传入一个字符串地址，返回一个类型为size_t类型（是无符号类型）的长度，长度是字符串里“\n”字符前面的元素个数。

（所以这里的长度不会把“\n”算进去）

1.2.4 strcat

全称是string concatenate字符串连接。传入两个字符串地址，把第二个地址的字符串连接在第一个地址的字符串后面。

（第一个字符串最后的“\n”会被去掉）

以上就是几个常用的string库函数了，想了解更多可以到这里去看看。<cstring> (string.h) - C++ Reference (cplusplus.com)

1.3 串的分类

以下两种类型的串都需要有存放字符串数组和元素个数的空间，分别为变量Str和length。

1.3.1 静态分配内存的串

​#define Maxsize 100
//串的顺序储存结构
typedef struct//静态数组
{
    char Str[Maxsize];
    int length;//元素个数
}SqString;
 
​

这是一个静态的字符数组，由代码开头define定义的宏常量Maxsize决定字符串的长度。内存分配不灵活，容易在串的插入，复制操作时造成溢出，所以我们优先使用动态数组的方式。

1.3.2 动态分配内存的串

typedef struct//动态数组
{
    char* Str;
    int MaxLength;//用于存储动态申请的内存空间大小
    int Length;//元素个数
}DSqString;

这个数组的空间需要在后续操作中申请内存，而且要将申请的内存空间大小保存，用于在其他操作时判断对数组的访问和操作会不会越界。由于内存申请灵活，下面的操作都会基于动态数组进行。（实际运用中，也是使用动态分配内存居多）

2. 串的基本操作

2.1 初始化串

​
//初始化串
int StringInitiate(DSqString* str, int maxLength, char* string)
//str为串，maxLength为即将申请的空间大小，string用于给str赋值
{
    str->Str = (char*)malloc(sizeof(char) * maxLength);
    if (str->Str == NULL)
    {
        printf("内存分配失败！\n");
        return 0;
    }
    //赋值
    str->MaxLength = maxLength;
    str->Length = (int)strlen(string);
    strcpy(str->Str,string);
    return 0;
}
 
​

i.！！注意！！  malloc是为串结构里的数组申请 maxsize 大小的空间，不是给整个 DSqString 结构体申请空间。

（别和链表搞混了）

ii.判断是否分配成功。这里不进行判断的话VS2022会报警告，它会认为数组可能没有成功分配空间，容易导致安全问题。如果分配失败，就return跳出函数。VS2022警告如图：

iii.分别对结构体内各个变量进行赋值。在结构体DSqSting里存入申请的空间大小MaxLength，用strlen求得的字符串长度以及strcpy复制要存入的字符串。这里对strlen的返回值进行了（int）的强制类型转换，目的是消除警告。如图：

2.2 输出字符串

//输出字符串(旨在方便查看操作后的效果)
void StringPrint(DSqString str)
{
    for (int i = 0; i < str.Length; i++)
    {
        printf("%c", str.Str[i]);
    }
    printf("\n");
}

十分简单的操作，就是遍历字符串数组然后输出而已。

注意！！千万不可以这么做↓

printf("%s",str.Str);

如果想用%s格式化输出字符串，就会连刚刚开辟但是可能没有进行赋值的空间也一并输出，也就是在字符串索引的Length-1到MaxLength-1这一段可能没有元素的空间也会被一起输出，输出的就是乱码。

（小tips：如果我们在printf进行输出时发现输出了，绝大多数情况都是越界访问，或者打印把没有值或者没有使用过的空间给打印了，一般就会输出如“烫烫烫”、“屯屯屯”等莫名其妙的东西）

2.3 插入子串

！！重要！！

//插入子串
int StringInsert(DSqString* str, int pos, DSqString str_son)//插入位置默认为索引值
{
    
    //判断插入位置是否合法
    if (pos < 0 || pos > str->MaxLength)
    {
        printf("插入位置pos输入错误！\n");
        return 0;
    }
    //若插入后大小会超出原有空间，就重新申请空间
    int son_length = (int)strlen(str_son.Str);
    if (str->Length + son_length > str->MaxLength)
    {
        char* p = NULL;
        p = (char*)realloc(str->Str,sizeof(char)*(size_t)(son_length+str->Length));
        //没有指针接收返回值则警告C6031返回值被忽略:"realloc".
        if (p == NULL)
        {
            printf("内存扩展失败！\n");
            return 0;
        }  
        str->Str = p;
        str->MaxLength = str->Length + son_length;
    }
    memset(str->Str + str->Length, '0', str->MaxLength - str->Length);
    //先移动
    for (int i = str->Length - 1; i >= pos; i--)
    {
        str->Str[i + str_son.Length] = str->Str[i];//从最后一个索引为str->Length-1的字符开始，向后移动i+str_son.Length个单位
        //警告C6001使用未初始化的内存"* str->Str".
 
    }
    //再插入
    for (int i = 0; i < str_son.Length; i++)
    {
        str->Str[i+pos] = str_son.Str[i];
    }
    str->Length += str_son.Length;//元素个数改变
    return 1;
}

i.判断插入位置pos是否合法。避免造成越界或者访问无元素空间（字符串索引的Length-1到MaxLength-1位置）的不合理，不合法情况发生。

ii.判断主串的最大空间MaxLength是否足够插入一个子串。如果不够，就要扩展内存。

扩展内存，我们用realloc函数。用法是：

​指针变量 = (指针类型)realloc(要扩展内存的变量地址,扩展后内存空间大小);

注意上面代码的指针类型要相同喔！realloc对内存的扩展是在原先的内存空间上再向高地址申请空间。

这里你可能会有疑惑，为什么要多此一举把扩展后的空间地址先赋值给p再赋值回去str->Str呢？要是这么做，VS2022可就要报警告了。如图：

因为如果扩展失败，那么会返回一个空指针，要是str->Str接受了空指针，那么所有的串里的所有字符都丢失了，这样的程序可不太安全。

iii.使用memset函数，目的是要对扩展后的内存进行初始化。如果不初始化，VS2022就会报警告：

这个报错就是说你刚申请的内存空间没有初始化，你在这里就要使用这些空间了，这样不安全。所以用memset函数对其空间初始化全都赋值为“0”，就可以消除警报了，还不会影响后续操作。

iiii.然后插入子串即可，逻辑和顺序表的插入是一样的，先后移挪出位置，再插入。不懂的话可以到前言的传送门那里跳转到顺序表的文章哦！（有目录，查找学习很快的！）

2.4 删除子串

//删除字串
int StringDelete(DSqString* str, int pos, int len)//传入开始删除的位置，删除长度
{
    if (pos<0 || pos>str->Length - 1)//判断pos是否合法
    {
        printf("删除位置pos输入错误！\n");
        return 0;
    }
    if (len<0 || len + pos>str->Length)//判断len是否合法
    {
        printf("删除长度len输入错误！\n");
        return 0;
    }
    if (str->Length <= 0)//判断字符串是否有字符
    {
        printf("无字符可删除！\n");
        return 0;
    }
    for (int i = pos + len ; i < str->Length; i++)//条件允许删除，直接将不删的元素前移
    {
        str->Str[i - len] = str->Str[i];
    }
    str->Length -= len;//长度减小
    return 1;
}

i.判断开始删除位置pos，和删除长度len是否合法，判断是否有字符可以删。避免造成越界或者访问无元素空间（字符串索引的Length-1到MaxLength-1的位置）的不合理，不合法情况发生。

ii.先删除，再将后面元素前移补空。代码逻辑同顺序表的删除操作，不懂的话可以到前言的传送门那里跳转到顺序表的文章哦！（有目录，查找学习很快的！）

2.5 取子串操作

int SubString(DSqString str, int len, int pos, DSqString* str_son)
{
    if (len<0 || len + pos>str.Length)
    {
        printf("取子串长度len输入错误！\n");
        return 0;
    }
    if (pos<0 || pos>str.Length - 1)
    {
        printf("取子串位置pos输入错误！\n");
        return 0;
    }
    if (str_son->MaxLength < len)
    {
        char* p = (char*)realloc(str_son, sizeof(char) * (size_t)len);
        if (p == NULL)
        {
            printf("内存扩展失败！\n");
            return 0;
        }
        free(p);
        str_son->MaxLength = len;
    }
    for (int i = 0; i < pos + len; i++)
    {
        str_son->Str[i] = str.Str[i + pos];
    }
    str_son->Length = len;
    return 1;
}

i.判断取子串位置pos和取子串长度len是否合法。原因同上，不多赘述。

ii.子串要放入另一个串结构里，因此放之前要判断新的串结构能不能放下取出的子串。如果不能就要realloc扩展内存，同插入子串操作的realloc。

iii.for循环一个一个字符赋值进去新的串结构里。完成取子串。

2.6 撤销删除操作

//撤销删除
void Destory(DSqString* str)
{
    free(str->Str);
    str->Length = 0;
    str->MaxLength = 0;
}

这是要把整个串结构都删掉，就先把字符串数组给free释放掉，再把字符串长度Length和字符数组最大申请空间Maxlength归零。比较简单。

结束语

串的基本操作就是这么多，是不是十分简单？然而真正难的还在后头，也就是字符串模式匹配算法：Brute-Force暴力查找算法和KMP算法。可以说难倒了许多算法新手，刚好我有文章详细介绍了呢！快去学习吧！最后求个三连支持！！ （正在写啦