C语言实现串的基本操作
导读
大家好！很高兴又和大家见面啦！！！
在上一篇内容中，我们详细介绍了串的一些基本概念与重要术语，并提到了串的三要素——逻辑结构、存储结构和数据的运算。从这个介绍中，我们对串有了更加深刻的认知——串也是一种线性表。
在上一篇的末尾，我们还简单介绍了一下串的一些基本操作：赋值、复制、判空、比较、求串长、求子串、串联接、定位、清空和销毁。为了能够更加深刻的理解串和对应的基本操作的同时还能提高自身编程能力，我们将会在今天的内容中通过C语言来逐一实现这些基本操作。下面我们就来进入今天的正题吧……
一、串的存储结构
串作为一种线性表，它的存储结构同样是有顺序存储和链式存储两种存储方式。为了更好的理解串的不同存储方式，我们首先来复习一下内存分区的相关内容；
1.1 内存区域的划分
在内存空间中有三个存储区域的划分——栈区、堆区和静态区。如下所示：
我们之前介绍的静态顺序表它在内存空间中申请的实际上是栈区上的空间，而动态顺序表和链表申请的则是堆区上的空间。堆区的内容空间有一个特点——内存需要手动分配，且手动释放，或者等程序结束时操作系统自动回收。
串在内存中同样也能够向栈区和堆区申请空间，如果对其进行细致的划分，我们可以将串的存储结构分为三类：
- 在栈区的顺序存储：定长顺序存储
- 在堆区的顺序存储：堆分配存储
- 在堆区的链式存储：块链存储
下面我们就来分别介绍一下这三类存储。
1.2 定长顺序存储
定长顺序存储类似于线性表的顺序存储，都是在栈区申请一块连续的存储单元存储串中的字符。它对应的数据类型我们则可以参照静态顺序表的数据类型进行定义，如下所示：
//定长顺序存储表示
#define MAXSIZE 255//串的最大长度
typedef struct StackString {
char ch[MAXSIZE];//存储字符的字符数组
int length;//串的实际长度
}SString;//重命名后的数据类型名和顺序表一样，在定长顺序存储中，串的实际长度只能小于或等于串的最大长度，且在创建完定长顺序存储的串后，串的最大长度不能被修改。当串的实际长度超过串的最大长度时，超过预定义长度的串值会被舍去，这个过程称为截断。如下所示：
1.2.1 串长的表示方式
在串中，串长的表示有两种方式：
- 通过整型变量
length来记录串长。
- 优点：我们可以在创建字符串的同时能够明确知道当前字符串的长度；
- 缺点：在输出字符串时我们需要通过串长对串中的元素进行依次输出；
- 通过在串的末尾添加字符串结束标志
'\0'来结束字符串。
- 优点：在输出字符串是可以直接通过占位符'%s'进行字符串的输出；
- 缺点：我们需要通过寻找
'\0'的位置来求字符串的长度；
两种方式都是可行的，上面我们定义的定长字符串的数据类型就是采用的第一种方式，我们在之前接触到的字符串则是采用的第二种方式，在具体的实现过程中如何选择这个可以根据自己的需求来确定。
PS:在我们今天的演示中，我采用的是这二者的结合，不仅通过变量
length来记录串长，而且会在串的末尾添加字符结束标志'\0'
1.3 堆分配存储
当我们对串进行像插入、联接等这种会改变当前串长的基本操作时，在定长顺序存储中我们则会受到串的最大长度MAXSIZE的限制。当操作之后的串长大于最大长度，此时我们只能通过截断的方式将超出的串值舍弃，为了克服这种弊端，我们则需要不限定串的最大长度。这时我们就可以通过堆分配存储的方式来做到内存空间的动态存储。
堆分配存储和动态顺序表一样，也是通过malloc和calloc函数在堆区中申请一块连续的存储空间来存放串值的字符序列，因此我们可以参照动态顺序表的数据类型进行定义，如下所示：
//堆分配存储表示
#define INITSIZE 10//串的预定义最大长度
typedef struct HeapString {
char* ch;//指向串起始地址的指针
int length,//串的当前长度
maxsize;//串的最大长度
}HString;//重命名后的数据类型在王道书上展示的数据类型没有INITSIZE和maxsize，这是因为两种数据类型实现的方式不一样，我这里展示的是像动态顺序表那种进行实时增加与修改串的方式，王道书上展示的则是直接通过串长length来申请空间的方式，这个也是根据个人的喜好进行选择。
不管是定长顺序存储还是堆分配存储都是属于串的顺序存储结构，它们不同点在于定长顺序存储是不能进行最大串长的修改，而堆分配存储可以动态的修改串的最大长度，不过通过堆分配存储实现的串在进行销毁时需要手动free掉申请的空间。
1.4 块链存储
串的块链存储类似于线性表的链式存储，都是通过链表的方式来存储串值。但是在线性表的链式存储中，数据的存储密度并不高，每个结点只能存储一个数据，而串的每个元素所占空间大小为1个字节，如果知识简单的采用链式存储，这样会极大的增加内存空间的浪费。为了更好的利用每个结点的内存空间，我们可以在串的数据域中存放多个字符，如下所示：
在串中，我们通常用每个结点存储的字符数量来表示块的大小，就比如上图中的单链表存储模式，每个结点中只存储一个字符，这种就是结点大小为1的块链；同理，上图中演示的可以存储4个字符的结点就是结点大小为4的块链。
在块链存储中，当采用结点大小>1的块链进行存储时，可能会出现最后一个结点中的数据域无法占满的情况，这时空出来的内存空间通常用'#'补上。
块链存储的数据类型我们可以参照单链表结点的数据类型进行定义，如下所示：
//块链存储
#define SIZE 4//预设块链结点大小
typedef struct StringNode {
char ch[SIZE];//存储字符的字符数组
struct StringNode* next;//指向下一个块的后继指针
}StringNode, * LinkString;//重命名后的数据类型名
//StringNode——表示块链的每个块，类型为结构体类型
//LinkString——表示整个块链,类型为结构体指针类型介绍完了串的存储结构，下面我们就要开始来实现串的基本操作了，这里我会采用大家比较熟悉的顺序存储的方式来实现串的基本操作。为了让大家能够理解串的动态内存分配，这里我们采用对分配存储进行演示；
二、串的基本操作的实现
对C语言的库函数比较熟悉的朋友可能会知道在头文件<string.h>中会包含一些对字符串进行操作的库函数，这里我们需要注意的是我们此时实现的串的基本操作的数据类型可不是char*的类型，因此头文件中的库函数在这里我们不能够直接进行使用，这个一定要注意；
2.1 串的初始化
现在我们采用的是堆分配存储，因此在初始化阶段我们需要分别对指向对空间的指针、当前串长和最大串长进行初始化，对应代码如下所示：
//串的初始化
void InitString(HString* T) {
assert(T);//判断传参是否有问题
T->ch = (char*)calloc(INITSIZE, sizeof(char));//为串T申请出始最大串长的空间
assert(T->ch);//判断空间是否申请成功
T->length = 0;//将当前表长初始化为0
T->maxsize = INITSIZE;//将最大表长初始化为预定义最大表长
}2.2 串的判空
当我们要判断一个串是否为空串时，我们只需要看该串的当前串长是否为0即可，代码如下所示：
//串的判空
bool StrEmpty(HString T) {
if (T.length == 0)
return true;
return false;
}2.3 串长的修改
在修改串长时，我们修改的是最大串长，和动态顺序表一样，有两种修改方式：
- 通过
malloc/calloc重新申请一块连续空间，并将当前空间中的所有元素移动到新的空间中； - 通过
realloc在当前的空间上新增一块空间
为了让大家更能理解空间修改的过程，这里我选用第一种方式来时先串长的修改，如下所示：
//串长的修改
bool StrIncreaseSize(HString* T, int len) {
char* p = T->ch;//创建新的字符指针指向原先的空间
T->ch = (char*)calloc(T->maxsize + len, sizeof(char));//为串T申请新的空间
if (T->ch == NULL)
return false;//当新的空间申请失败时返回false
for (int i = 0; i < T->length; i++) {
T->ch[i] = p[i];//将原空间的内容复制到新的空间中
}
T->maxsize += len;//修改最大串长
free(p);//释放原空间的内存
return true;
}我们在使用堆区上的空间时，一定要养成随时释放无用空间的习惯，由于串的堆分配是申请的一块连续的堆空间，因此我们直接通过free函数将该空间的内存释放掉即可。
2.4 串的清空
当我们要清空一个串时，只需要将串的当前串长置为0即可，这个比较简单，如果我们想要做的完美一点，我们可以将串中的元素在清空的过程中全部置为0，如下所示：
//串的清空
void ClearString(HString* T) {
//简单处理
T->length = 0;//优点：此时的时间复杂度为O(1)；缺点：原先空间中存放的元素依旧还存在
//复杂处理
for (int i = T->length - 1; i >= 0; i--) {
T->ch[i] = 0;//将空间中的元素清除
T->length--;//当前串长-1
}
//优点：原先空间中的元素全部被清除
//缺点：时间复杂度为O(n)
}这两种处理方式都是可行的大家可以根据自己的需求进行选择。
2.5 串的销毁
串的销毁过程实际上就是释放内存空间的过程，对于定长存储的串而言，我们只能通过操作系统主动回收内存空间，因此只需要完成串的清空操作即可；而对堆分配存储的串而言，我们则可以直接通过free函数进行主动进行内存空间的回收，代码如下所示：
//串的销毁
void DestroyString(HString* T) {
free(T->ch);//直接释放串的内存空间
T->ch = NULL;//完成空间释放后将指针置空
}2.6 求串长
StrLength(S)——求串长这个功能其实就是我们熟知的一个库函数strlen的功能。记录串长的方式主要就是记录字符串中的字符个数，这里的字符是不包括字符串零终止符'\0'，也就是说我们要记录的就是'\0'之前的字符个数。具体的方式有以下三种：
- 通过计数器进行记录
- 通过指针地址的差值进行记录
- 通过函数递归进行记录
这三种实现方式在【C语言必学知识点五】指针篇章中有详细的介绍，这里我就不再重复赘述了，我们这里的实现通过最简单的也是最好理解的方式来实现——通过计数器进行记录，代码如下所示：
//求串长
int StrLength(char* S) {
int count = 0;
for (int i = 0; S[i] != '\0'; i++) {
count++;
}
return count;
}对于串的初始化、判空、串长的修改、清空、销毁、求串长等操作而言都是比较简单的内容，这里我就不再多加赘述，接下来我们要重点介绍的是赋值、复制、比较、求子串、串联接、定位等操作；
2.7 串的赋值
StrAssign(&T, chars)——赋值操作是将字符串chars赋值个串T。这个可能有点不好理解，下面我们看一段代码，大家应该就能明白什么是赋值操作了，如下所示：
int a = 10;//将10赋值给变量a
int b = a;//将a的值赋值给变量b赋值操作就是借助赋值操作符将右操作数的值赋给左操作数。因此我们要想将chars的值赋值给T，我们同样也是需要借助赋值操作符'='。
字符串的赋值实际上就是改变字符指针的指向对象，因此串T的字符指针需要是能够修改指向对象的指针，这个在定义数据类型时一定要注意，不能定义一个char* const ch；当然这个问题在咱们今天的介绍中是不存在的。
在完成赋值后，对串T来说，它不仅仅是字符指针指向的对象发生了变化，而且字符指针指向的空间大小、串T的当前串长都会有变化。因此，我们需要在完成赋值后同步修改串T的当前串长和最大串长。
在实际的操作中我们还可能会遇到一个问题——串T的空间中有存放元素，此时如果字符指针指向的空间还需要的话，我们需要创建新的指针来指向该空间，之后再改变串T的字符指针的指向；如果字符指针指向的空间不需要的话，我们需要释放该空间的内存，再进行赋值操作。
理清了赋值的思路，下面我们就可以编写代码来实现复制操作了。对应代码如下所示：
//串的赋值
bool StrAssign(HString* T, HString* chars) {
if (T == NULL || chars == NULL)//当串T或者串chars为空指针时，说明传参出现了问题
return false;//传参有问题则无法进行后续操作，因此返回false
char* tmp = T->ch;//通过创建临时指针指向原空间
T->ch = chars->ch;//完成赋值操作
free(tmp);//当原空间的内容不需要时，可以释放原空间的内存
T->length = chars->length;//修改当前串长
T->maxsize = chars->maxsize;//修改最大串长
return true;
}这里需要注意，为了不影响后续的操作，我们选择在进行赋值操作时两个串必须是同类型的串，如果出现了一个是HString*一个是char*那么就表示此时给串T赋值的空间可能会是栈区上的空间，而栈区的空间我们是不能通过free函数主动释放内容空间的。因此为了杜绝这种情况的发生，我们索性直接限制赋值时两个参数的数据类型。
2.8 串的复制
对于复制和赋值我相信有朋友和我刚开始一样没有将它们区分开来，因此在实现这个操作之前，我们先来区分一下复制与赋值这二者的区别。
2.8.1 复制与赋值的区别
我们以一个实际的例子来说明复制和赋值的区别。
就比如张三和李四这两个好朋友，张三最近新买了一本《数据结构》，李四看到了说他也想要这本书。这时张三就有两种选择：
- 和李四共用这本《数据结构》
- 将书上的内容复印一份给李四
在这个例子中，第一种方式就是赋值操作，两个人共用同一本书；第二种方式就是复制操作，两个人学习的都是同一本书，但是此时他们是人手一本。如果将这个例子转换成代码，则如下所示：
//串的复制与赋值的区别
void test2() {
//赋值
char* a = "abcd";//初始化的赋值过程
char* b = NULL;
b = a;//赋值操作
//复制
char c[5] = { 0 };
for (int i = 0; a[i]; i++) {
c[i] = a[i];//将a中的内容复制到c中
}
}在这个代码运行的结果就是a、b、c中存放的值都是同一个值，但是对于a和b来说，它们就是同一个指针，只不过名字不同而已，而c和a却是两个内容，如下所示：
从测试结果中我们可以看到，在进行字符串打印时，a、b、c打印出来的内容都是字符串"abcd"，但是当我们输出他们指向的地址时我们就会发现指针a和指针b指向的是同一块空间的地址，而数组c指向的是与a不相同的地址。
由这次测试我们可以得到一个结论：
- 赋值完的两个对象会变成同一个对象；而复制完的两个对象依旧是两个对象；
从指针的角度来理解就是：赋值时，地址相同；复制时，地址不同；
在理清了赋值与复制的区别后，现在我们就可以开始实现复制这个基本操作了。
2.8.2 复制的实现
StrCopy(&T,S)——将串S的内容拷贝到串T中。复制的实现还是比较简单的，我们只需要在串T的空间中存放串S中的每个字符即可，但是需要注意以下几点：
- 如果串
T的空间中存在元素的话，这个空间中的元素需要能够修改才行。因此串T中的字符指针指向的对象就不能是一个常量字符串； - 不管串
T中是否存在元素，串T的空间要保证能够存放串S中的所有元素。因此我们需要在复制前判断一下串T的最大串长与串S的串长的大小关系； - 在完成复制后我们还需要判断串
T的当前串长是否小于串S的串长，如果判断条件成立，那我们需要修改串T的当前串长；
明确了复制过程中可能出现的问题及其解决方案后，我们就可以进行代码编写了，如下所示：
//串的复制
void StrCopy(HString* T, char* S) {
assert(T);//当串T为空指针时，说明传参出现了问题
int len = StrLength(S);//获取串S的串长
if (T->maxsize < len + 1);//判断串T的最大串长是否小于串S的串长
StrIncreaseSize(T, len - T->maxsize + 1);//为串T申请足够的空间来存放串S中的元素
//复制串S
for (int i = 0; i < len; i++)
T->ch[i] = S[i];
if (T->length < len)//判断当前串长是否小于串S的串长
T->length = len;//条件满足则修改当前串长
}可以看到，在复制操作中，我们是可以选择char*类型的串S对串T进行复制操作的，因为复制操作仅仅是改变串T的字符指针指向的空间中的元素，并不会改变串T的字符指针指向的空间，所以此时不管是栈区上的字符串S还是堆区上的字符串S我们都是可以进行复制操作的。
2.9 串的比较
StrCompare(S,T)——串的比较操作就是依次将两个串中同位序的元素进行比较，这时会有三种情况：
- 串
S的元素>串T的元素，这时需要返回一个大于0的整型值； - 串
S的元素<串T的元素，这时需要返回一个小于0的整型值； - 串
S与串T的串长相等，且串S与串T中的所有元素都相等，这时需要返回0；
比较函数的主体功能我们已经明确了，下面就可以编写代码了，如下所示：
//串的比较
int StrCompare(char* S, char* T) {
for (int i = 0; S[i] || T[i]; i++) {
if (S[i] != T[i])
return S[i] - T[i];
}
return 0;
}2.9.1 串类型的选择问题
细心的朋友就会发现我们实现的这些基本操作从求串长开始，就会时不时的出现char*类型的串，但是大家如果观看王道的视频就会发现咸鱼学长在介绍串的比较操作时定义的是SString类型的串，为什么我这里的实现和咸鱼学长介绍的会有区别呢？
这里是因为咸鱼学长介绍串的基本操作时考虑的就是同类型的串之间的基本操作，但是我们在实际运用中，不一定都是遇到同类型的串，我们也可能遇到定义在堆区的串，还可能遇到定义在栈区的串。
在这种情况下，为了能够使这些存储区域不一致的串也能和我们定义的串进行求串长、串复制、串比较等这种基本操作，所以我选择的是将基本操作的参数类型设置为char*。
因此，在后续的操作中如果大家同样看到了char*的类型，那就说明该操作既适用于堆区上定义的串，也适用于栈区上定义的串。
2.10 求子串
SubString(&Sub,S,pos,len)——求子串操作中我们需要用Sub来返回串S中第pos个字符开始的长度为len的子串。既然这里有提到起始位置，那我们在实际操作的过程中必然会遇到以下几种情况：
pos的值小于1或者大于串S的长度- 从
pos个字符开始的子串长度小于len - 从
pos个字符开始的子串长度大于len
第一种情况肯定是需要我们避免的，因此在找子串前，我们需要对pos的取值合理性进行判断，当遇到不合理的pos时，我们应该直接返回false；
如果出现第二种情况，那么就是说明在串S中的第pos个位置开始并不存在长度为len的子串，此时我们也需要返回false；
只有在第三种情况下，我们才能够正确的获取长度为len的子串。
理清了该操作中可能出现的问题和解决方案后，我们就可以编写对应的代码来实现基本操作了，如下所示：
//求子串
bool SubString(char** Sub, char* S, int pos, int len) {
if (S == NULL)//当主串S为空指针时，无法执行后续操作
return false;
if (pos<1 || pos>StrLength(S))//当pos<1或者pos>S的串长时，说明pos的值不合理
return false;
if (StrLength(S + pos - 1) < len)//当从pos开始的串长<len，说明串S中没有满足条件的子串
return false;
//找子串
for (int i = 0; i < len; i++)
(*Sub)[i] = S[pos + i - 1];
return true;
}这里需要注意的是，我们传入的pos为字符的位序，而我们实现的串首元素下标是从0开始，因此，位序为pos的字符对应的下标为pos-1；
2.11 串联接
Concat(&T,S1,S2)——用串T返回由串S1和串S2联接而成的新串。在这个操作下，为了确保串T能够放入串S1和串S2中的所有元素，因此我们需要将串T的最大串长与串S1的串长和串S2的串长之和进行比较，从而确定是否进行空间的扩充。
在进行联接的过程，我们需要将串S1中的'\0'用串S2的首字符进行覆盖以确保得到的新串是连续的。而联接的实现，我们可以通过复制操作进行实现，将S1和S2的字符分别复制到串T中。
理清了思路后，就可以进行代码的编写了，具体实现如下所示：
//串联接
void Concat(HString* T, char* S1, char* S2) {
assert(T);
int len = StrLength(S1) + StrLength(S2);
if (T->maxsize < len + 1)//当串T的最大串长小于S1和S2的串长之和时
//为串T扩充空间，确保串T中的空间大于S1和S2的串长之和
StrIncreaseSize(T, len - T->maxsize + 1);
int i = 0;//串T的下标
//将串S1中的元素复制到串T中
for (i; S1[i]; i++)
T->ch[i] = S1[i];
//将串S2中的元素复制到串T中
for (int j =0; S2[j]; j++)
T->ch[i++] = S2[j];
T->length = len;//修改当前串长
}2.12 串的定位
Index(S,T)——若主串S中存在于串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数返回-1。
串定位实际上就是找子串，只不过我们需要将找到的子串与串T进行比较：
- 如果两个相等，那就说明主串中存在与串
T值相同的子串，此时就直接将找到的子串返回即可； - 如果不相等则说明该子串不是我们需要的子串，因此我们还需要继续寻找。当主串
S中与串T长度相同的子串全部找完后，还未找到与串T相等的子串，那就说明主串S中不存在与串T值相同的子串，此时就需要返回0；
因此串的定位操作我们可以借助求子串操作和串联接操作来共同实现，对应代码如下所示：
//串定位
int Index(HString S, char* T) {
if (!T)//判断串T是否为空指针
return -2;//串T为空指针时，无需执行定位操作
int len = StrLength(T);//获取串T的串长
if (len == 0)//判断子串T是否为空串
return -3;//子串T为空串，则无需查找
char* sub = (char*)calloc(len + 1, sizeof(char));//为子串申请空间
for (int i = 1; i <= S.length; i++) {
//从主串首元素开始寻找与串T长度相同的子串
if (SubString(&sub, S.ch, i, len))
//找到子串后判断子串sub与串T是否相同
if (StrCompare(sub, T) == 0)
return i + 1;//相同则返回子串的位序
}
return -1;//当找完串S中的所有子串都未找到，S中不存在与T相等的子串
}可以看到在具体的实现中，为了增加代码的健壮性，大家可以像我一样将串T为空指针、串T为空串和主串S中没有与串T相同的子串的情况通过不同的返回值来进行区分。
三、串的基本操作的演示
下面我们就来测试一下这些基本操作，如下所示：
可以看到现在这些功能是可以正常运行的，大家可能奇怪为什么没有串比较和找子串的演示，这是因为我们在实现串定位这个功能时就是借助的找子串和串比较这两个功能因此这里就没有额外的对这两个功能进行测试。
四、串的基本操作实现C语言代码
最后给大家附上串的基本操作的全部代码，需要的朋友自行拿取：
String.c文件
#include "String.h"
//串的初始化
void InitString(HString* T) {
assert(T);//判断传参是否有问题
T->ch = (char*)calloc(INITSIZE, sizeof(char));//为串T申请出始最大串长的空间
assert(T->ch);//判断空间是否申请成功
T->length = 0;//将当前表长初始化为0
T->maxsize = INITSIZE;//将最大表长初始化为预定义最大表长
}
//串的判空
bool StrEmpty(HString T) {
if (T.length == 0)
return true;
return false;
}
//串长的修改
bool StrIncreaseSize(HString* T, int len) {
char* p = T->ch;//创建新的字符指针指向原先的空间
T->ch = (char*)calloc(T->maxsize + len, sizeof(char));//为串T申请新的空间
if (T->ch == NULL)
return false;//当新的空间申请失败时返回false
for (int i = 0; i < T->length; i++) {
T->ch[i] = p[i];//将原空间的内容复制到新的空间中
}
T->maxsize += len;//修改最大串长
free(p);//释放原空间的内存
return true;
}
//串的清空
void ClearString(HString* T) {
//简单处理
T->length = 0;//优点：此时的时间复杂度为O(1)；缺点：原先空间中存放的元素依旧还存在
////复杂处理
//for (int i = T->length - 1; i >= 0; i--) {
// T->ch[i] = 0;//将空间中的元素清除
// T->length--;//当前串长-1
//}
////优点：原先空间中的元素全部被清除
////缺点：时间复杂度为O(n)
}
//串的销毁
void DestroyString(HString* T) {
free(T->ch);//直接释放串的内存空间
T->ch = NULL;//完成空间释放后将指针置空
}
//求串长
int StrLength(char* S) {
int count = 0;
for (int i = 0; S[i] != '\0'; i++) {
count++;
}
return count;
}
//串的赋值
bool StrAssign(HString* T, HString* chars) {
if (T == NULL || chars == NULL)//当串T或者串chars为空指针时，说明传参出现了问题
return false;//传参有问题则无法进行后续操作，因此返回false
char* tmp = T->ch;//通过创建临时指针指向原空间
T->ch = chars->ch;//完成赋值操作
free(tmp);//当原空间的内容不需要时，可以释放原空间的内存
T->length = chars->length;//修改当前串长
T->maxsize = chars->maxsize;//修改最大串长
return true;
}
//串的复制
void StrCopy(HString* T, char* S) {
assert(T);//当串T为空指针时，说明传参出现了问题
int len = StrLength(S);//获取串S的串长
if (T->maxsize < len + 1) //判断串T的最大串长是否小于串S的串长
StrIncreaseSize(T, len - T->maxsize + 1);//为串T申请足够的空间来存放串S中的元素
//复制串S
for (int i = 0; i < len; i++)
T->ch[i] = S[i];
if (T->length < len)//判断当前串长是否小于串S的串长
T->length = len;//条件满足则修改当前串长
}
//串的比较
int StrCompare(char* S, char* T) {
for (int i = 0; S[i] || T[i]; i++) {
if (S[i] != T[i])
return S[i] - T[i];
}
return 0;
}
//求子串
bool SubString(char** Sub, char* S, int pos, int len) {
if (S == NULL)//当主串S为空指针时，无法执行后续操作
return false;
if (pos<1 || pos>StrLength(S))//当pos<1或者pos>S的串长时，说明pos的值不合理
return false;
if (StrLength(S + pos - 1) < len)//当从pos开始的串长<len，说明串S中没有满足条件的子串
return false;
//找子串
for (int i = 0; i < len; i++)
(*Sub)[i] = S[pos + i - 1];
return true;
}
//串联接
void Concat(HString* T, char* S1, char* S2) {
assert(T);
int len = StrLength(S1) + StrLength(S2);
if (T->maxsize < len + 1)//当串T的最大串长小于S1和S2的串长之和时
//为串T扩充空间，确保串T中的空间大于S1和S2的串长之和
StrIncreaseSize(T, len - T->maxsize + 1);
int i = 0;//串T的下标
//将串S1中的元素复制到串T中
for (i; S1[i]; i++)
T->ch[i] = S1[i];
//将串S2中的元素复制到串T中
for (int j =0; S2[j]; j++)
T->ch[i++] = S2[j];
T->length = len;//修改当前串长
}
//串定位
int Index(HString S, char* T) {
if (!T)//判断串T是否为空指针
return -2;//串T为空指针时，无需执行定位操作
int len = StrLength(T);//获取串T的串长
if (len == 0)//判断子串T是否为空串
return -3;//子串T为空串，则无需查找
char* sub = (char*)calloc(len + 1, sizeof(char));//为子串申请空间
for (int i = 1; i <= S.length; i++) {
//从主串首元素开始寻找与串T长度相同的子串
if (SubString(&sub, S.ch, i, len))
//找到子串后判断子串sub与串T是否相同
if (StrCompare(sub, T) == 0)
return i + 1;//相同则返回子串的位序
}
return -1;//当找完串S中的所有子串都未找到，S中不存在与T相等的子串
}
//串打印
void StrPrint(HString T,char ret) {
printf("%c.ch = %s\n",ret, T.ch);//输出串S的内容
printf("%c.length = %d\n",ret, T.length);//输出串S的当前串长
printf("%c.maxsize = %d\n",ret, T.maxsize);//输出串S的最大串长
}
String.h文件
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//定长顺序存储表示
#define MAXSIZE 255//串的最大长度
typedef struct StackString {
char ch[MAXSIZE];//存储字符的字符数组
int length;//串的实际长度
}SString;//重命名后的数据类型名
//堆分配存储表示
#define INITSIZE 10//串的预定义最大长度
typedef struct HeapString {
char* ch;//指向串起始地址的指针
int length,//串的当前长度
maxsize;//串的最大长度
}HString;//重命名后的数据类型
//块链存储
#define SIZE 4//预设块链结点大小
typedef struct StringNode {
char ch[SIZE];//存储字符的字符数组
struct StringNode* next;//指向下一个块的后继指针
}StringNode, * LinkString;//重命名后的数据类型名
//StringNode——表示块链的每个块，类型为结构体类型
//LinkString——表示整个块链,类型为结构体指针类型
//串的初始化
void InitString(HString* T);
//串的判空
bool StrEmpty(HString T);
//串长的修改
bool StrIncreaseSize(HString* T, int len);
//串的清空
void ClearString(HString* T);
//串的销毁
void DestroyString(HString* T);
//求串长
int StrLength(char* S);
//串的赋值
bool StrAssign(HString* T, HString* chars);
//串的复制
void StrCopy(HString* T, char* S);
//串的比较
int StrCompare(char* S, char* T);
//求子串
bool SubString(char* Sub, char* S, int pos, int len);
//串联接
void Concat(HString* T, char* S1, char* S2);
//串定位
int Index(HString S, char* T);
//串打印
void StrPrint(HString T, char ret);test.c文件
#include "String.h"
//串的基本操作的演示
void test4() {
HString T;
HString S;
HString R;
HString K;
//串的初始化
if (1) {
printf("初始化操作测试:>\n");
InitString(&T);//初始化串T
if (T.maxsize == INITSIZE) {
printf("串T初始化成功\n");
StrPrint(T, 'T');//打印串T的内容、当前串长与最大串长
}
else {
printf("串T初始化失败\n");
return;
}
InitString(&S);//初始化串S
if (S.maxsize == INITSIZE) {
printf("串S初始化成功\n");
StrPrint(S, 'S');//打印串S的内容、当前串长与最大串长
}
else {
printf("串S初始化失败\n");
return;
}
InitString(&R);//初始化串R
if (R.maxsize == INITSIZE) {
printf("串R初始化成功\n");
StrPrint(R, 'R');//打印串R的内容、当前串长与最大串长
}
else {
printf("串R初始化失败\n");
return;
}
InitString(&K);//初始化串R
if (K.maxsize == INITSIZE) {
printf("串K初始化成功\n");
StrPrint(K, 'K');//打印串K的内容、当前串长与最大串长
}
else {
printf("串K初始化失败\n");
return;
}
}
//串复制
if (1) {
printf("串复制操作测试:>\n");
StrCopy(&S, "abcd");//将字符串"abcd"复制到串S中
if (StrEmpty(S)) {
printf("串S复制失败\n");
return;
}
else {
printf("串S复制成功\n");
StrPrint(S, 'S');//打印串S的内容、当前串长与最大串长
}
StrCopy(&R, "0123456789");//将字符串"0123456789"复制到串S中
if (StrEmpty(R)) {
printf("串R复制失败\n");
return;
}
else {
printf("串R复制成功\n");
StrPrint(R, 'R');//打印串S的内容、当前串长与最大串长
}
}
//串赋值
if (1) {
printf("串赋值操作测试:>\n");
StrAssign(&T, &S);//将串S的内容赋值给串T
if (StrEmpty(T)) {
printf("串S赋值给串T失败\n");
return;
}
else {
printf("串S赋值给串T成功\n");
StrPrint(T, 'T');//打印串T的内容、当前串长与最大串长
}
}
//联接串T与串R
if (1) {
printf("串联接操作测试:>\n");
printf("联接前:>\n");
StrPrint(K, 'K');
StrPrint(T, 'T');
StrPrint(R, 'R');
Concat(&K, T.ch, R.ch);
printf("联接后:>\n");
StrPrint(K, 'K');
StrPrint(T, 'T');
StrPrint(R, 'R');
}
//串定位
printf("串定位操作测试:>\n");
char* sub = "cd123";
printf("需要在串K中查找的子串sub = %s\n", sub);
int i = Index(K, sub);
switch (i) {
case -1:
printf("主串K中未找到子串sub\n");
break;
case -2:
printf("子串sub为空串\n");
break;
case -3:
printf("传入的参数为空指针\n");
break;
default:
printf("子串sub在主串K中的位序为：%d\n", i);
printf("子串sub在主串K中的下标为：%d\n", i - 1);
break;
}
//清空串
if (1) {
printf("串清空操作测试:>\n");
ClearString(&T);
if (StrEmpty(T))
printf("串T已清空\n");
ClearString(&S);
if (StrEmpty(S))
printf("串S已清空\n");
ClearString(&R);
if (StrEmpty(R))
printf("串R已清空\n");
ClearString(&K);
if (StrEmpty(K))
printf("串K已清空\n");
}
//销毁串
if (1) {
printf("串销毁操作测试:>\n");
DestroyString(&T);
if (T.ch == NULL)
printf("串T、串S已销毁\n");
DestroyString(&R);
if (R.ch == NULL)
printf("串R已销毁\n");
DestroyString(&K);
if (K.ch == NULL)
printf("串K已销毁\n");
}
}
int main() {
test4();
return 0;
}总结
在今天的内容中，我们详细介绍了串的三种存储：
- 在栈区申请连续空间的顺序存储方式——定长顺序存储；
- 在堆区申请连续空间的顺序存储方式——堆分配存储；
- 在堆区申请存储空间的链式存储方式——块链存储
之后，我们通过C语言实现了对分配存储的串的基本操作并对这些基本操作进行了测式，通过测试结果可以看到我们很好的通过C语言实现了串的基本操作。
