用c语言实现——一个动态顺序存储的串结构

一、思路概要

①动态顺序存储的串结构：

动态应该使用动态内存分配，也就是用指针来存储字符数组，同时记录长度和当前容量。

这样结构体应该包含三个成员：一个char*指针，一个int表示当前长度，另一个int表示总容量。这样可以方便扩展，当字符串变长时，可以重新分配更大的内存。

②初始化函数：

需要分配初始内存，比如默认大小可以设为一定值，比如20或者根据需要调整。

③赋值操作：

需要将一个字符串复制到结构体中，这时要注意检查容量是否足够，不够的话需要扩容。

④清空操作：

将长度设为0，但不释放内存。

⑤销毁操作：

完全释放内存，并将指针置空。

⑥求串长度：

直接返回长度，判空检查长度是否为0。

⑦显示操作：

直接打印当前字符串内容。

⑧串联接：

将另一个串连接到当前串后面，这时候需要考虑容量是否足够，不够的话需要扩容。

⑨子串提取：

需要用户给出起始位置和长度，然后提取出来形成新的串。这里要注意边界条件，比如起始位置是否合法，长度是否超过原串的范围。

⑩子串定位：

用的是朴素模式匹配算法，也就是逐个字符比较，主串和子串的指针移动，如果发现不匹配就回溯。需要注意索引的范围，避免越界。

子串定位的朴素算法实现需要注意循环的条件，主串从0到len - sublen的位置，每个位置检查子串是否匹配。例如，主串长度是len，子串长度是sublen，那么主串最多只能到 len - sublen的位置开始匹配，否则子串长度不够。

次数最多为n-m+1次。n为主串长，m为模式串长。

比较操作：

需要比较两个串的字典序，逐个字符比较直到不同或者结束。

户交互界面：

需要设计一个菜单，让用户可以选择不同的操作。比如用循环显示选项，然后根据输入调用对应的函数。

这里可能需要处理的错误：

①用户的输入错误，比如输入非数字选项，或者操作时输入无效的参数。

②提取子串时的位置和长度不正确。这时候程序应该给出提示，而不是崩溃。

③每个函数都应该检查参数的合法性，比如索引是否在有效范围内，指针是否为空等

2. 库函数

①perror 函数

是标准库函数，定义在<stdio.h>头文件中。

作用 ：输出系统错误信息到标准错误输出流（通常是屏幕）。它会将最近一次系统调用或库函数调用失败时产生的错误信息以字符串形式输出，帮助开发者快速定位问题。

语法 ：void perror(const char *s)。参数s是一个字符串，通常用于指定错误发生的上下文描述。如果s不是NULL，函数会先输出这个字符串，接着输出一个冒号和空格，然后输出错误信息。

使用场景 ：当系统调用或库函数返回失败时，可以使用perror输出具体的错误原因。例如，文件打开失败时，使用perror("File open failed");能帮助快速了解失败原因。I）里的部分是程序员自行输入的。

②exit函数

是标准库函数，定义在<stdlib.h>头文件中。

作用 ：终止程序的执行，并向宿主环境返回一个整数作为程序的退出状态。这可以用来告知调用者（例如操作系统或父进程）程序是否正常结束或因错误而终止。

语法 ：void exit(int status)。status是退出状态码，通常EXIT_SUCCESS（宏，表示成功）、EXIT_FAILURE（宏，表示失败）或数字0表示成功，非0值表示失败。

执行过程 ：当调用exit时，会先调用所有通过atexit注册的清理函数，完成程序中的一些收尾工作（如关闭文件、释放资源等），然后终止程序。

使用场景 ：在程序关键步骤失败（如内存分配失败、文件打开失败等）时，使用exit函数可以立即终止程序执行，避免程序继续运行导致更严重的后果。

二、代码阐释

1.动态字符串结构体定义

char* data ：一个字符指针，用于指向存储字符串的字符数组。这个指针允许字符串在内存中动态分配和扩展，以适应不同长度的字符串。

int length ：这个整数变量记录了当前字符串的实际长度，即字符串中有效字符的数量（不包括终止符'\0'）。

int capacity ：这个整数变量表示当前分配给字符串存储的容量，也就是data指针所指向的内存区域的大小。它通常大于或等于length，以提供额外的空间供字符串扩展时使用。

 

2.初始化字符串

 

设置初始容量：

str->capacity = 20;：将String结构体的capacity成员变量设置为20，表示最初为字符串分配的内存空间可以存储20个字符。

动态内存分配以及内存分配失败检查 ：

str->data = (char*)malloc(str->capacity * sizeof(char));：

使用malloc函数为String结构体的data成员变量分配内存。malloc函数根据str->capacity的值（即20）乘以sizeof(char)（通常为1字节）来确定要分配的内存大小。(char*)是类型转换，确保分配的内存被正确地视为字符指针。

if (!str->data)：检查malloc函数是否成功分配内存。如果str->data为NULL，表示内存分配失败。

perror("Memory allocation failed");：

输出错误信息，perror函数会打印一条系统错误消息，说明内存分配失败的原因。

exit(EXIT_FAILURE);：终止程序执行，并返回一个表示失败的退出状态码。这是一个宏，通常定义在头文件stdlib.h中。

初始化字符串：

str->data[0] = '\0';：将分配的内存空间的第一个字符设置为字符串结束符'\0'，这样字符串的初始状态就是一个空字符串。

str->length = 0;：将String结构体的length成员变量设置为0，表示当前字符串的长度为0。

3.销毁字符串

 if (str->data)：检查String结构体的data成员是否为非空指针。只有当data指向有效的内存区域时，才需要进行释放操作。

free(str->data);：调用free函数释放data所指向的动态分配的内存。free函数是C语言标准库中的函数，用于释放用malloc、calloc或realloc分配的内存。

str->data = NULL;：将data指针设置为NULL。这一步是为了防止出现悬空指针（dangling pointer），即指向已经被释放的内存的指针。将指针设置为NULL后，可以明确地表示该指针不再指向有效的内存区域。

str->length = 0;：将String结构体的length成员设置为0，表示字符串的长度为0。这一步是为了将字符串重置为初始状态，即使得结构体中的各个成员变量都处于未分配或空状态。

str->capacity = 0;：将String结构体的capacity成员设置为0，表示字符串的存储容量也为0。

4.清空字符串

if (str->data)：检查String结构体的data成员是否指向有效的内存区域（即是否非空）。只有当data非空时，才需要进行清空操作。

 str->data[0] = '\0';：将data所指向的字符数组的第一个字符设置为字符串结束符'\0'，这使得字符串在逻辑上变成空字符串，但原来的内存空间仍然被保留。

str->length = 0;：将String结构体的length成员设置为0，表示字符串的长度变为0。

5.赋值操作

函数定义： 

定义了一个名为 AssignString 的函数，该函数将一个普通字符串赋值给 String 结构体实例。函数的参数包括一个指向 String 结构体的指针 str 和一个指向普通字符串的指针 source，返回类型是 bool，表示赋值是否成功。

参数检查：

 

检查参数 str 和 source 是否为 NULL。如果任何一个指针为 NULL，则返回 false，表示赋值失败。

获取字符串长度：

使用 strlen 函数获取 source 字符串的长度，并将其存储在变量 new_len 中。

检查存储容量：

判断 new_len 是否大于或等于 str->capacity，以检查当前 String 结构体实例的存储容量是否足够容纳 source 字符串。

计算新容量：

计算新的存储容量 new_capacity，即 new_len 加 1（额外 1 字节用于存储字符串结束符 '\0'）。

重新分配内存：

使用 realloc 函数重新分配内存空间，尝试将 str->data 指向的内存区域的大小调整为 new_capacity。realloc 函数返回一个新的指针，指向重新分配的内存区域。

内存重新分配失败检查：

 检查 realloc 函数返回的指针是否为 NULL。如果返回 NULL，说明内存重新分配失败，函数返回 false。

更新数据指针和容量：

将 str->data 更新为重新分配后的内存区域的指针，并更新 str->capacity 为新的存储容量 new_capacity。 

复制字符串：

使用 strcpy 函数将 source 字符串的内容复制到 str->data 指向的内存区域中。strcpy 函数会自动复制包括字符串结束符 '\0' 在内的所有字符。

更新字符串长度：

更新 str->length 为 new_len，即当前字符串的长度。

最后返回成功信息。

6. 获取长度函数

定义了一个名为 GetLength 的函数，该函数接收一个指向 String 结构体的常量指针 str，返回类型是 int，表示字符串的长度。

使用三元运算符检查 str 是否为非空指针。

如果 str 不是空指针，则返回 str->length，即 String 结构体的 length 成员变量的值。

如果 str 是空指针，则返回 0，表示字符串长度为0。

7. 判空函数

使用三元运算符检查 str 是否为非空指针。

如果 str 不是空指针，则进一步检查 str->length 是否为0。如果 str->length 为0，返回 true（表示字符串为空）；否则返回 false。

如果 str 是空指针，则直接返回 true，表示字符串为空。这种处理方式是出于安全考虑，避免访问空指针。

8.显示函数

检查指针有效性：

检查 str 是否为非空指针，以及 str->data 是否为非空指针。

如果 str 或 str->data 为 NULL，则不执行后续操作，避免访问无效内存。

打印字符串内容：

使用 printf 函数输出字符串的内容。

格式化字符串 "%s" 用于输出 str->data 指向的字符串内容。

打印字符串长度和容量：

使用 printf 函数输出字符串的长度和容量。

格式化字符串 "%d" 用于输出整数值 str->length 和 str->capacity。

9.字符串的连接

检查指针是否为空：

检查 dest、src 和 src->data 是否为非空指针。如果任何一个指针为 NULL，函数返回 false，表示连接失败。

计算新长度

计算连接后的长度：

计算连接后的字符串长度，即目标字符串 dest 的长度与源字符串 src 的长度之和。

检查存储容量

判断是否需要扩展容量：

判断连接后的字符串长度 new_len 是否大于或等于目标字符串 dest 的当前存储容量 capacity。

扩展存储容量

计算新的存储容量：

计算新的存储容量，为连接后的字符串长度加1（用于存储字符串结束符 '\0'）。

重新分配内存：

使用 realloc 函数尝试将目标字符串 dest 的存储容量扩展到 new_capacity。

内存重新分配失败检查：

检查 realloc 是否成功。如果返回的指针为 NULL，表示内存重新分配失败，函数返回 false。

更新数据指针和容量：

更新目标字符串 dest 的数据指针和容量。

 字符串连接

连接字符串：

使用 strcat 函数将源字符串 src 的内容连接到目标字符串 dest 的末尾。

更新字符串长度

更新目标字符串长度：

更新目标字符串 dest 的长度为连接后的长度。

最后返回成功

10.提取字符串

检查指针是否为空：

检查 sub 和 src 是否为非空指针，以及起始位置和长度是否合法。如果任何一个条件不满足，函数返回 false，表示提取失败。

判断是否需要扩展容量：

判断提取的子串长度 length 是否大于或等于目标字符串 sub 的当前存储容量。

计算新的存储容量：

计算新的存储容量，为子串长度加1（用于存储字符串结束符 '\0'）。

重新分配内存：

 使用 realloc 函数尝试将目标字符串 sub 的存储容量扩展到 new_capacity。

内存重新分配失败检查：

检查 realloc 是否成功。如果返回的指针为 NULL，表示内存重新分配失败，函数返回 false。

更新数据指针和容量：

更新目标字符串 sub 的数据指针和容量。

复制子串内容：

使用 strncpy 函数从源字符串 src 的指定起始位置 start 开始，复制 length 个字符到目标字符串 sub 的数据区域。

添加字符串结束符：

在目标字符串 sub 的数据区域的末尾添加字符串结束符 '\0'。

更新字符串长度：

更新目标字符串 sub 的长度为提取的子串长度。

11.算法函数

检查指针是否为空：

检查主字符串 mainStr 和子字符串 subStr 是否为非空指针，以及子字符串长度是否为0或大于主字符串长度。如果任何一个条件满足，函数返回 0，表示未找到子字符串。

遍历主字符串

外层循环：

 遍历主字符串的每个可能的起始位置 i，确保从位置 i 开始有足够的长度容纳子字符串。

遍历子字符串

内层循环：

遍历子字符串的每个字符，与主字符串从位置 i 开始的字符进行比较。

字符比较

字符不匹配处理：

如果主字符串和子字符串在位置 j 的字符不匹配，则跳出内层循环，移动到主字符串的下一个起始位置继续比较。

匹配成功处理

返回匹配位置：

如果内层循环完整执行（即子字符串所有字符都匹配），返回匹配的起始位置 i + 1（因为返回值采用1-based索引）。

匹配失败处理

返回未找到：

如果遍历完所有可能的起始位置仍未找到匹配的子字符串，返回 0。

12. 字符串比较函数

检查指针是否为空：

检查传入的两个字符串指针s1和s2是否为非空。如果任意一个指针为空，函数返回-1，表示比较失败或参数无效。

计算最小长度

确定比较范围：

计算两个字符串长度中的较小值，确定字符比较的范围。这一步确保了不会因为超出较短字符串的长度而引发访问越界错误。

逐字符比较

循环比较对应字符：

在循环中依次比较两个字符串对应位置的字符：

如果发现不匹配的字符，立即返回这两个字符的ASCII值的差。这表示在第一个不匹配的位置上，哪个字符串的字符更大。

如果所有比较范围内的字符都相同，则继续执行后续操作。

比较长度

返回长度差：

如果两个字符串在较短长度范围内完全相同，则通过比较它们的长度来确定最终结果。较长的字符串被认为较大，返回两个字符串长度的差值。

13.清理缓冲区函数

1. 定义变量：定义一个整型变量 c，用于存储从标准输入读取的字符。

2. 循环清理：使用 while 循环持续读取标准输入中的字符：

   • getchar()：读取一个字符。

   • 条件判断：当读取的字符 c 不是换行符 \n 且不是文件结束标志 EOF 时，继续循环读取。

   • 效果：该循环会一直读取并丢弃输入缓冲区中的字符，直到遇到换行符或文件结束标志，从而实现清理输入缓冲区的目的。

三、完整代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<stdbool.h>typedef struct 
{char* data;      // 存储字符串的字符数组int length;      // 当前字符串长度int capacity;    // 当前分配的存储容量   
} String;// 函数声明
void InitString(String* str);
void DestroyString(String* str);
void ClearString(String* str);
bool AssignString(String* str, const char* source);
int GetLength(const String* str);
bool IsEmpty(const String* str);
void DisplayString(const String* str);
bool ConcatString(String* dest, const String* src);
bool SubString(String* sub, const String* src, int start, int length);
int Index(const String* mainStr, const String* subStr);
int CompareString(const String* s1, const String* s2);// 初始化字符串
void InitString(String* str) 
{str->capacity = 20;str->data = (char*)malloc(str->capacity * sizeof(char));if (!str->data){perror("Memory allocation failed");exit(EXIT_FAILURE);}str->data[0] = '\0';str->length = 0;
}// 销毁字符串
void DestroyString(String* str)
{if (str->data){free(str->data);str->data = NULL;}str->length = 0;str->capacity = 0;
}// 清空字符串
void ClearString(String* str) 
{if (str->data){str->data[0] = '\0';str->length = 0;}
}// 赋值操作
bool AssignString(String* str, const char* source)
{if (!str || !source){return false;}int new_len = strlen(source);if (new_len >= str->capacity){int new_capacity = new_len + 1;char* new_data = (char*)realloc(str->data, new_capacity);if (!new_data){return false;}str->data = new_data;str->capacity = new_capacity;}strcpy(str->data, source);str->length = new_len;return true;
}// 获取长度
int GetLength(const String* str) 
{return str ? str->length : 0;
}// 判断空串
bool IsEmpty(const String* str) 
{return str ? (str->length == 0) : true;
}// 显示字符串
void DisplayString(const String* str)
{if (str && str->data){printf("String content: %s\n", str->data);printf("Length: %d, Capacity: %d\n", str->length, str->capacity);}
}// 字符串连接
bool ConcatString(String* dest, const String* src)
{if (!dest || !src || !src->data){return false;}int new_len = dest->length + src->length;if (new_len >= dest->capacity){int new_capacity = new_len + 1;char* new_data = (char*)realloc(dest->data, new_capacity);if (!new_data){return false;}dest->data = new_data;dest->capacity = new_capacity;}strcat(dest->data, src->data);dest->length = new_len;return true;
}// 提取子串
bool SubString(String* sub, const String* src, int start, int length)
{if (!sub || !src || start < 1 || start > src->length || length < 0 || (start + length - 1) > src->length){return false;}if (length >= sub->capacity) {int new_capacity = length + 1;char* new_data = (char*)realloc(sub->data, new_capacity);if (!new_data){return false;}sub->data = new_data;sub->capacity = new_capacity;}strncpy(sub->data, src->data + start - 1, length);sub->data[length] = '\0';sub->length = length;return true;
}// 朴素模式匹配
int Index(const String* mainStr, const String* subStr) 
{if (!mainStr || !subStr || subStr->length == 0 || mainStr->length < subStr->length){return 0;}for (int i = 0; i <= mainStr->length - subStr->length; i++){int j;for (j = 0; j < subStr->length; j++){if (mainStr->data[i + j] != subStr->data[j]){break;}}if (j == subStr->length){return i + 1; // 返回1-based位置}}return 0;
}// 字符串比较
int CompareString(const String* s1, const String* s2) 
{if (!s1 || !s2) return -1;int min_len = s1->length < s2->length ? s1->length : s2->length;for (int i = 0; i < min_len; i++) {if (s1->data[i] != s2->data[i]){return s1->data[i] - s2->data[i];}}return s1->length - s2->length;
}// 清理输入缓冲区
void CleanInputBuffer()
{int c;while ((c = getchar()) != '\n' && c != EOF);
}int main() 
{String str, temp;InitString(&str);InitString(&temp);int choice;char buffer[1024];while (1) {printf("\n===== 字符串操作菜单 =====\n");printf("1. 字符串赋值\n");printf("2. 清空字符串\n");printf("3. 判空操作\n");printf("4. 获取长度\n");printf("5. 显示字符串\n");printf("6. 连接字符串\n");printf("7. 提取子串\n");printf("8. 查找子串位置\n");printf("9. 比较字符串\n");printf("10. 退出程序\n");printf("请输入选项：");if (scanf("%d", &choice) != 1){while (getchar() != '\n');printf("输入错误！请重新输入数字\n");continue;}switch (choice){case 1: {printf("请输入新字符串：");CleanInputBuffer();// 清除输入缓冲区fgets(buffer, sizeof(buffer), stdin);buffer[strcspn(buffer, "\n")] = '\0';if (AssignString(&str, buffer))printf("赋值成功\n");elseprintf("赋值失败！\n");break;}case 2:ClearString(&str);printf("字符串已清空\n");break;case 3:printf("字符串状态：%s\n", IsEmpty(&str) ? "空" : "非空");break;case 4:printf("字符串长度：%d\n", GetLength(&str));break;case 5:DisplayString(&str);break;case 6:{printf("请输入要连接的字符串：");CleanInputBuffer();fgets(buffer, sizeof(buffer), stdin);buffer[strcspn(buffer, "\n")] = '\0';if (AssignString(&temp, buffer) && ConcatString(&str, &temp))printf("连接成功\n");elseprintf("连接失败！\n");ClearString(&temp);break;}case 7: {int start, length;printf("请输入起始位置和长度：");if (scanf("%d %d", &start, &length) != 2){printf("参数无效！\n");while (getchar() != '\n');break;}String sub;InitString(&sub);if (SubString(&sub, &str, start, length)){printf("提取的子串：");DisplayString(&sub);}else{printf("参数错误！\n");}DestroyString(&sub);break;}case 8: {printf("请输入要查找的子串：");CleanInputBuffer();fgets(buffer, sizeof(buffer), stdin);buffer[strcspn(buffer, "\n")] = '\0';if (AssignString(&temp, buffer)) {int pos = Index(&str, &temp);if (pos > 0)printf("找到子串，位置：%d\n", pos);elseprintf("未找到子串！\n");}ClearString(&temp);break;}case 9:{printf("请输入比较字符串：");CleanInputBuffer();fgets(buffer, sizeof(buffer), stdin);buffer[strcspn(buffer, "\n")] = '\0';if (AssignString(&temp, buffer)) {int result = CompareString(&str, &temp);if (result < 0)printf("当前字符串小于输入字符串\n");else if (result > 0)printf("当前字符串大于输入字符串\n");elseprintf("字符串相同\n");}ClearString(&temp);break;}case 10:DestroyString(&str);DestroyString(&temp);printf("正在退出程序...\n");exit(0);default:printf("无效选项！请重新选择\n");}}return 0;
}

编译器环境为VS2022！！！

用c语言实现一个动态顺序存储的串结构，支持用户输入交互界面、初始化、赋值、清空、销毁、求串长、判空、显示串表等基本操作、同时也要包含更高级的操作，比如串联接、子串提取、子串定位、比较等。子串定位采用朴素模式匹配算法，注意代码的健壮性

数据结构学习者参考。