数据结构-串-了解串-串的基本操作

一、了解串

串的定义

串（String）是由零个或多个字符组成的有限序列。串在计算机科学中是一个非常重要的概念，通常用于表示文本数据。根据字符的编码方式，串可以由 ASCII、Unicode 等编码格式表示。串的基本特性包括：

字符集：串中的字符来自于特定的字符集，如 ASCII、UTF-8 等。
长度：串的长度是指串中字符的数量，可以是零（空串）或正整数。
不可变性：在某些编程语言（如 Python）中，串是不可变的，即一旦创建，其内容不能被更改；而在其他语言（如 C++）中，串可以是可变的。

串的存储结构

1. 串的定长顺序存储表示

定义：使用一个固定长度的数组来存储串中的字符。数组的大小在定义时就确定，通常在数组的最后一个位置放置一个特殊字符（如空字符 '\0'）来标识串的结束。
特点：
- 优点：
  - 访问效率高：可以通过下标直接访问任意位置的字符，时间复杂度为 O(1)。
  - 实现简单：数据结构简单，易于实现和使用。
- 缺点：
  - 固定大小：在创建时需要指定数组的大小，若实际存储的字符数超过了数组大小，会导致溢出。
  - 空间浪费：如果实际字符数小于数组大小，会造成内存的浪费。
示例：

char str[100];  // 定义一个长度为100的字符数组

2. 堆分配存储表示

定义：使用动态内存分配（如 malloc 在 C 语言中）来存储串。可以根据实际需要分配内存，串的长度可以在运行时确定。
特点：
- 优点：
  - 灵活性高：可以动态地分配和释放内存，避免了固定大小的限制。
  - 没有空间浪费：只占用实际字符所需的内存，不会浪费空间。
- 缺点：
  - 访问效率低：由于需要通过指针访问，时间复杂度为 O(n)，并且可能会涉及到额外的内存管理开销。
  - 内存管理复杂：需要手动管理内存，容易导致内存泄漏或悬空指针。

示例：

char *str = (char *)malloc(n * sizeof(char));  // 动态分配长度为 n 的字符数组

3. 块链存储表示--暂时未写代码

定义：将串分成若干个块，每个块可以是一个固定长度的数组，通过链表将这些块连接起来。适合于较长的串，能够有效管理内存。
特点：
- 优点：
  - 灵活性高：可以根据需要增加或减少块的数量，避免了固定大小的限制。
  - 节省空间：通过块的方式，可以更好地管理内存，避免了过多的内存浪费。
- 缺点：
  - 访问效率低：访问某个字符需要遍历块，时间复杂度为 O(n)，相较于顺序存储结构较慢。
  - 实现复杂：需要实现块的管理和链表操作，增加了实现的复杂性。
示例：

typedef struct Block {char data[BLOCK_SIZE];  // 每个块的固定大小struct Block* next;      // 指向下一个块的指针
} Block;Block* head;  // 链表头指针

串的基本操作

1. 串的结构表示

2. 赋值操作

描述：将一个串的值赋给另一个串。
细节：
- 确保目标串有足够的空间来存放源串的内容。
- 将源串中的每个字符逐个复制到目标串中，直到遇到结束符（如 '\0'）。
- 可以使用循环或字符串处理函数来完成。

3. 判空操作

描述：检查串是否为空。
细节：
- 判断串的首字符是否为结束符（如 '\0'）。
- 如果是，则表示串为空；否则，串不为空。

4. 比较操作

描述：比较两个串的大小关系。
细节：
- 从第一个字符开始逐个比较两个串的字符。
- 如果某个字符不相同，则返回该字符的 ASCII 值差。
- 如果所有字符相同且都到达结束符，返回 0，表示两个串相等。

5. 求串长

描述：计算串的长度。
细节：
- 从串的首字符开始，逐个计数，直到遇到结束符（如 '\0'）。
- 返回计数的结果，即为串的长度。

6. 求子串

描述：从一个串中提取出指定位置和长度的子串。
细节：
- 确定起始位置和长度，确保起始位置在串的有效范围内。
- 创建一个新的串来存放子串。
- 从起始位置开始，逐个复制指定长度的字符到新串中。

7. 串联接

描述：将两个串连接成一个新的串。
细节：
- 确保目标串有足够的空间来存放两个串的内容。
- 将第一个串的内容复制到目标串中，然后在目标串的末尾添加第二个串的内容。
- 在连接后，确保新串以结束符（如 '\0'）结束。

8. 定位操作

描述：查找一个子串在主串中的位置。
细节：
- 从主串的每个字符开始，逐个检查是否与子串的首字符匹配。
- 如果匹配，则逐个比较后续字符，直到子串的所有字符都匹配或到达主串的末尾。
- 如果找到匹配，返回位置索引；如果未找到，返回 -1。

9. 清空操作

描述：将串的内容清空，变为一个空串。
细节：
- 将串的首字符设置为结束符（如 '\0'）。
- 可选：释放与串相关的内存（如果使用动态分配），以避免内存泄漏。

10. 销毁操作

描述：释放串所占用的内存。
细节：
- 对于动态分配的串，使用相应的内存释放函数（如 free）。
- 确保所有指向该串的指针都被清空，以避免悬空指针问题。

二、串的定长顺序存储表示（C语言）

1. 定长顺序存储结构


#define MAXLEN 255  // 定义字符串最大长度
typedef struct {char ch[MAXLEN]; // 存储字符串的字符数组int length;      // 字符串的当前长度
} SString;// 初始化字符串
void InitString(SString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;S->ch[S->length] = '\0'; // 确保字符串结束}
}

2. 赋值操作


// 赋值操作
void StrAssign(SString* dest, const SString* src) {if (dest == NULL || src == NULL) return; // 检查指针有效性// 复制长度dest->length = src->length;// 复制字符数组for (int i = 0; i < src->length; i++) {dest->ch[i] = src->ch[i];}// 添加结束符dest->ch[dest->length] = '\0';
}

3. 判空操作


// 判空操作
bool StrEmpty(SString S) {return S.length == 0; // 如果长度为0，则字符串为空
}

4. 比较操作


// 比较操作
int StrCompare(const SString* S, const SString* T) {int lengthDiff = S->length - T->length; // 先比较长度if (lengthDiff != 0) return lengthDiff; // 长度不同，返回差值// 长度相同，逐个字符比较for (int i = 0; i < S->length; i++) {if (S->ch[i] > T->ch[i]) return 1; // S 大于 Tif (S->ch[i] < T->ch[i]) return -1; // S 小于 T}return 0; // 相等
}

5. 求串长


// 求串长
int StrLength(SString* S) {return S->length; // 返回字符串的长度
}

6. 求子串


// 求子串
bool SubString(SString* Sub, SString* S, int pos, int len) {if (pos < 1 || pos > S->length || len < 1) return false; // 检查位置和长度的有效性if (pos + len - 1 > S->length) return false; // 检查是否超出原字符串范围// 复制子串for (int i = 0; i < len; i++) {Sub->ch[i] = S->ch[pos - 1 + i]; // 逐个字符复制}Sub->length = len; // 设置子串长度return true; // 复制成功
}

7. 串联接


// 串联接
bool Concat(SString* T, SString* S1, SString* S2) {if (S1->length + S2->length >= MAXLEN) return false; // 检查是否超出最大长度int i = 0;// 复制第一个字符串for (i = 0; i < S1->length; i++) {T->ch[i] = S1->ch[i];}// 复制第二个字符串for (i = 0; i < S2->length; i++) {T->ch[S1->length + i] = S2->ch[i];}T->length = S1->length + S2->length; // 设置新字符串的长度T->ch[T->length] = '\0';return true; // 串联成功
}

8. 定位操作


// 8. 定位操作  
// 函数功能：在字符串S中查找子串T，返回T在S中首次出现的位置。如果T不是S的子串，则返回0。  
// 优化算法后续提供
int INdex(SString* S, SString* T) {// 如果T的长度大于S的长度，则T不可能是S的子串，直接返回0。  if (T->length > S->length) return 0;int cnt = 0; // 用于记录当前匹配的字符数量  // 外层循环，遍历S字符串，直到S中剩余的长度小于T的长度，此时无需继续比较。  for (int i = 0; i <= S->length - T->length; i++) {cnt = 0; // 每次开始新的匹配时，重置计数器  // 内层循环，遍历T字符串，进行字符匹配  for (int j = 0; j < T->length; j++) {// 如果S和T中的字符不匹配，则跳出内层循环  if (S->ch[i + j] != T->ch[j]) {break;}cnt++; // 如果字符匹配，计数器加1  }// 如果计数器值等于T的长度，说明T是S的子串，返回T在S中的起始位置（位置从1开始计数）  if (cnt == T->length) return i + 1;}// 如果遍历完S仍未找到T，则返回0  return 0;
}

9. 清空操作


// 9. 清空操作
void ClearString(SString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;S->ch[S->length] = '\0'; // 确保字符串结束}
}

10. 销毁操作


// 9. 清空操作
void ClearString(SString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;S->ch[S->length] = '\0'; // 确保字符串结束}
}

11. 复制操作


// 复制操作
bool StrCopy(SString* S, const char chars[]) {if (S == NULL || chars == NULL) return false; // 检查指针是否有效int i = 0;S->length = 0;while (chars[i] != '\0') {if (S->length >= MAXLEN - 1) { // 最后一位用来标志结束return false;}S->ch[S->length] = chars[i];i++;S->length++;}S->ch[S->length] = '\0'; // 确保字符串结束return true;
}

12. 打印字符串


// 打印字符串
void PrintString(const SString* S) {if (S != NULL) {printf("字符串内容: %s\n", S->ch);printf("字符串长度: %d\n", S->length);}
}

三、堆分配存储表示（C语言）

1. 堆分配存储表示


#define AddCh  10
typedef struct {char* ch;int length;
}HString;// 初始化字符串  
bool InitString(HString* S) {// 检查S是否为NULL，应该使用==而不是=  if (S == NULL) return false;// 为S->ch分配内存  S->ch = (char*)malloc(sizeof(char) * (AddCh + 1)); // 分配AddCh个字符加上一个空字符'\0'的空间  if (S->ch == NULL) {// 如果内存分配失败，返回false  return false;}// 初始化字符串为空字符串  S->ch[0] = '\0';S->length = 0;// 初始化成功，返回true  return true;
}

2. 赋值操作


// 赋值操作  
bool StrAssign(HString* dest, HString* src) {if (dest == NULL || src == NULL) return false;// 如果dest->ch已经指向了内存，先释放它  if (dest->ch != NULL) {free(dest->ch);}// 为dest->ch分配内存  dest->ch = (char*)malloc(sizeof(char) * (src->length + 1 + AddCh)); // 分配src->length + 1 + AddCh个字符的空间  if (dest->ch == NULL) return false; // 检查malloc是否成功  // 复制字符串内容  for (int i = 0; i < src->length; i++) {dest->ch[i] = src->ch[i];}dest->ch[src->length] = '\0'; // 设置字符串结束符  // 更新dest的length  dest->length = src->length;return true;
}

3. 判空操作


// 判空操作
bool StrEmpty(HString S) {return S.length == 0; // 如果长度为0，则字符串为空
}

4. 比较操作


// 比较操作
int StrCompare(const HString* S, const HString* T) {int lengthDiff = S->length - T->length; // 先比较长度if (lengthDiff != 0) return lengthDiff; // 长度不同，返回差值// 长度相同，逐个字符比较for (int i = 0; i < S->length; i++) {if (S->ch[i] > T->ch[i]) return 1; // S 大于 Tif (S->ch[i] < T->ch[i]) return -1; // S 小于 T}return 0; // 相等
}

5. 求串长


// 求串长
int StrLength(const HString* S) {return S->length; // 返回字符串的长度
}

6. 求子串


// 求子串
bool SubString(HString* Sub, HString* S, int pos, int len) {if (pos < 1 || pos > S->length || len < 1) return false; // 检查位置和长度的有效性if (pos + len - 1 > S->length) return false; // 检查是否超出原字符串范围// 为Sub分配空间if (Sub->ch != NULL)free(Sub->ch);Sub->ch = (char*)malloc(sizeof(char) * (len + 1 + AddCh));if (Sub->ch == NULL) return false;// 复制子串for (int i = 0; i < len; i++) {Sub->ch[i] = S->ch[pos - 1 + i]; // 逐个字符复制}Sub->length = len; // 设置子串长度Sub->ch[Sub->length] = '\0';return true; // 复制成功
}

7. 串联接


// 串联接
bool Concat(HString* T, HString* S1, HString* S2) {if (T->ch != NULL) {free(T->ch);}T->ch = (char*)malloc(sizeof(char) * (S1->length+S2->length + 1 + AddCh));if (T->ch == NULL) return false;int i = 0;// 复制第一个字符串for (i = 0; i < S1->length; i++) {T->ch[i] = S1->ch[i];}// 复制第二个字符串for (i = 0; i < S2->length; i++) {T->ch[S1->length + i] = S2->ch[i];}T->length = S1->length + S2->length; // 设置新字符串的长度T->ch[T->length] = '\0';return true; // 串联成功
}

8. 定位操作


// 8. 定位操作  
// 函数功能：在字符串S中查找子串T，返回T在S中首次出现的位置。如果T不是S的子串，则返回0。  
// 优化算法后续提供
int INdex(HString* S, HString* T) {// 如果T的长度大于S的长度，则T不可能是S的子串，直接返回0。  if (T->length > S->length) return 0;int cnt = 0; // 用于记录当前匹配的字符数量  // 外层循环，遍历S字符串，直到S中剩余的长度小于T的长度，此时无需继续比较。  for (int i = 0; i <= S->length - T->length; i++) {cnt = 0; // 每次开始新的匹配时，重置计数器  // 内层循环，遍历T字符串，进行字符匹配  for (int j = 0; j < T->length; j++) {// 如果S和T中的字符不匹配，则跳出内层循环  if (S->ch[i + j] != T->ch[j]) {break;}cnt++; // 如果字符匹配，计数器加1  }// 如果计数器值等于T的长度，说明T是S的子串，返回T在S中的起始位置（位置从1开始计数）  if (cnt == T->length) return i + 1;}// 如果遍历完S仍未找到T，则返回0  return 0;
}

9. 清空操作


// 9. 清空操作
void ClearString(HString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;}
}

10. 销毁操作


// 10. 销毁操作、
void DestroyString(HString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;if (S->ch != NULL)free(S->ch);}
}

11. 复制操作


// 复制操作  
bool StrCopy(HString* S,const char chars[]) {// 检查S和chars指针是否有效  if (S == NULL || chars == NULL) return false;// 计算源字符串的长度（不包括结尾的空字符）  int cnt_length = 0;while (chars[cnt_length] != '\0') cnt_length++;// 如果S->ch已经指向了内存，则释放它  if (S->ch != NULL) {free(S->ch);}// 为S->ch分配足够的内存来存储源字符串（包括结尾的空字符）和额外的AddCh字节  S->ch = (char*)malloc(sizeof(char) * (cnt_length + 1 + AddCh));// 检查malloc是否成功分配了内存  if (S->ch == NULL) return false;// 初始化S->length为0，准备开始复制字符串  S->length = 0;// 复制字符串到S->ch，并更新S->length  int i = 0;while (chars[i] != '\0') {S->ch[i] = chars[i];i++;S->length++;}// 在字符串的末尾添加空字符（虽然这通常是多余的，因为从chars复制时它已经包含了空字符）  // 但为了代码的清晰性和一致性，这里还是显式地添加了它  S->ch[S->length] = '\0';// 复制成功  return true;
}

12. 打印字符串


// 打印字符串
void PrintString(const HString* S) {if (S != NULL) {printf("字符串内容: %s\n", S->ch);printf("字符串长度: %d\n", S->length);}
}

四、总代码（C语言）

1、串的定长顺序存储表示-示例

#include <stdio.h>
#include <stdbool.h>#define MAXLEN 255  // 定义字符串最大长度
typedef struct {char ch[MAXLEN]; // 存储字符串的字符数组int length;      // 字符串的当前长度
} SString;// 初始化字符串
void InitString(SString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;S->ch[S->length] = '\0'; // 确保字符串结束}
}// 赋值操作
void StrAssign(SString* dest, const SString* src) {if (dest == NULL || src == NULL) return; // 检查指针有效性// 复制长度dest->length = src->length;// 复制字符数组for (int i = 0; i < src->length; i++) {dest->ch[i] = src->ch[i];}// 添加结束符dest->ch[dest->length] = '\0';
}// 复制操作
bool StrCopy(SString* S, const char chars[]) {if (S == NULL || chars == NULL) return false; // 检查指针是否有效int i = 0;S->length = 0;while (chars[i] != '\0') {if (S->length >= MAXLEN - 1) { // 最后一位用来标志结束return false;}S->ch[S->length] = chars[i];i++;S->length++;}S->ch[S->length] = '\0'; // 确保字符串结束return true;
}// 打印字符串
void PrintString(const SString* S) {if (S != NULL) {printf("字符串内容: %s\n", S->ch);printf("字符串长度: %d\n", S->length);}
}// 判空操作
bool StrEmpty(SString S) {return S.length == 0; // 如果长度为0，则字符串为空
}// 比较操作
int StrCompare(const SString* S, const SString* T) {int lengthDiff = S->length - T->length; // 先比较长度if (lengthDiff != 0) return lengthDiff; // 长度不同，返回差值// 长度相同，逐个字符比较for (int i = 0; i < S->length; i++) {if (S->ch[i] > T->ch[i]) return 1; // S 大于 Tif (S->ch[i] < T->ch[i]) return -1; // S 小于 T}return 0; // 相等
}// 求串长
int StrLength(SString* S) {return S->length; // 返回字符串的长度
}// 求子串
bool SubString(SString* Sub, SString* S, int pos, int len) {if (pos < 1 || pos > S->length || len < 1) return false; // 检查位置和长度的有效性if (pos + len - 1 > S->length) return false; // 检查是否超出原字符串范围// 复制子串for (int i = 0; i < len; i++) {Sub->ch[i] = S->ch[pos - 1 + i]; // 逐个字符复制}Sub->length = len; // 设置子串长度Sub->ch[Sub->length] = '\0';return true; // 复制成功
}// 串联接
bool Concat(SString* T, SString* S1, SString* S2) {if (S1->length + S2->length >= MAXLEN) return false; // 检查是否超出最大长度int i = 0;// 复制第一个字符串for (i = 0; i < S1->length; i++) {T->ch[i] = S1->ch[i];}// 复制第二个字符串for (i = 0; i < S2->length; i++) {T->ch[S1->length + i] = S2->ch[i];}T->length = S1->length + S2->length; // 设置新字符串的长度T->ch[T->length] = '\0';return true; // 串联成功
}// 8. 定位操作  
// 函数功能：在字符串S中查找子串T，返回T在S中首次出现的位置。如果T不是S的子串，则返回0。  
// 优化算法后续提供
int INdex(SString* S, SString* T) {// 如果T的长度大于S的长度，则T不可能是S的子串，直接返回0。  if (T->length > S->length) return 0;int cnt = 0; // 用于记录当前匹配的字符数量  // 外层循环，遍历S字符串，直到S中剩余的长度小于T的长度，此时无需继续比较。  for (int i = 0; i <= S->length - T->length; i++) {cnt = 0; // 每次开始新的匹配时，重置计数器  // 内层循环，遍历T字符串，进行字符匹配  for (int j = 0; j < T->length; j++) {// 如果S和T中的字符不匹配，则跳出内层循环  if (S->ch[i + j] != T->ch[j]) {break;}cnt++; // 如果字符匹配，计数器加1  }// 如果计数器值等于T的长度，说明T是S的子串，返回T在S中的起始位置（位置从1开始计数）  if (cnt == T->length) return i + 1;}// 如果遍历完S仍未找到T，则返回0  return 0;
}// 9. 清空操作
void ClearString(SString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;S->ch[S->length] = '\0'; // 确保字符串结束}
}// 10. 销毁操作、
void DestroyString(SString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;S->ch[S->length] = '\0'; // 确保字符串结束}
}int main() {SString s1, s2, result, sub;// 初始化字符串  InitString(&s1);InitString(&s2);InitString(&result);InitString(&sub);StrCopy(&s1, "Hello, World!"); // 复制操作  StrCopy(&s2, "Copy of Hello, World!");// 打印字符串  PrintString(&s1);PrintString(&s2);// 判空操作  printf("s1 是否为空: %s\n", StrEmpty(s1) ? "是" : "否");// 比较操作  int cmpResult = StrCompare(&s1, &s2);printf("比较结果: %d\n", cmpResult);// 求串长  printf("s1 的长度: %d\n", StrLength(&s1));// 求子串  if (SubString(&sub, &s1, 8, 5)) { // 从第8个字符开始取5个字符  PrintString(&sub);}else {printf("子串提取失败\n");}// 串联接  if (Concat(&result, &s1, &s2)) {PrintString(&result);}else {printf("串联失败\n");}SString WW;char d[5] = "World";for (int i = 0; i < 5; i++) WW.ch[i] = d[i];WW.length = 5;// 定位操作  int index = INdex(&result, &WW); // 查找 "World"  printf("\"World\" 在 s1 中的位置: %d\n", index);// 清空操作  ClearString(&s1);PrintString(&s1);// 销毁操作（对于顺序存储，实际上只是清空）  // 注意：在顺序存储中，DestroyString 应该只是 ClearString  // 如果是动态分配的内存，则需要释放内存  //  return 0;
}

2、堆分配存储表示 - 案例

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define AddCh  10
typedef struct {char* ch;int length;
}HString;// 初始化字符串  
bool InitString(HString* S) {// 检查S是否为NULL，应该使用==而不是=  if (S == NULL) return false;// 为S->ch分配内存  S->ch = (char*)malloc(sizeof(char) * (AddCh + 1)); // 分配AddCh个字符加上一个空字符'\0'的空间  if (S->ch == NULL) {// 如果内存分配失败，返回false  return false;}// 初始化字符串为空字符串  S->ch[0] = '\0';S->length = 0;// 初始化成功，返回true  return true;
}// 赋值操作  
bool StrAssign(HString* dest, HString* src) {if (dest == NULL || src == NULL) return false;// 如果dest->ch已经指向了内存，先释放它  if (dest->ch != NULL) {free(dest->ch);}// 为dest->ch分配内存  dest->ch = (char*)malloc(sizeof(char) * (src->length + 1 + AddCh)); // 分配src->length + 1 + AddCh个字符的空间  if (dest->ch == NULL) return false; // 检查malloc是否成功  // 复制字符串内容  for (int i = 0; i < src->length; i++) {dest->ch[i] = src->ch[i];}dest->ch[src->length] = '\0'; // 设置字符串结束符  // 更新dest的length  dest->length = src->length;return true;
}// 复制操作  
bool StrCopy(HString* S,const char chars[]) {// 检查S和chars指针是否有效  if (S == NULL || chars == NULL) return false;// 计算源字符串的长度（不包括结尾的空字符）  int cnt_length = 0;while (chars[cnt_length] != '\0') cnt_length++;// 如果S->ch已经指向了内存，则释放它  if (S->ch != NULL) {free(S->ch);}// 为S->ch分配足够的内存来存储源字符串（包括结尾的空字符）和额外的AddCh字节  S->ch = (char*)malloc(sizeof(char) * (cnt_length + 1 + AddCh));// 检查malloc是否成功分配了内存  if (S->ch == NULL) return false;// 初始化S->length为0，准备开始复制字符串  S->length = 0;// 复制字符串到S->ch，并更新S->length  int i = 0;while (chars[i] != '\0') {S->ch[i] = chars[i];i++;S->length++;}// 在字符串的末尾添加空字符（虽然这通常是多余的，因为从chars复制时它已经包含了空字符）  // 但为了代码的清晰性和一致性，这里还是显式地添加了它  S->ch[S->length] = '\0';// 复制成功  return true;
}// 打印字符串
void PrintString(const HString* S) {if (S != NULL) {printf("字符串内容: %s\n", S->ch);printf("字符串长度: %d\n", S->length);}
}// 判空操作
bool StrEmpty(HString S) {return S.length == 0; // 如果长度为0，则字符串为空
}// 比较操作
int StrCompare(const HString* S, const HString* T) {int lengthDiff = S->length - T->length; // 先比较长度if (lengthDiff != 0) return lengthDiff; // 长度不同，返回差值// 长度相同，逐个字符比较for (int i = 0; i < S->length; i++) {if (S->ch[i] > T->ch[i]) return 1; // S 大于 Tif (S->ch[i] < T->ch[i]) return -1; // S 小于 T}return 0; // 相等
}// 求串长
int StrLength(const HString* S) {return S->length; // 返回字符串的长度
}// 求子串
bool SubString(HString* Sub, HString* S, int pos, int len) {if (pos < 1 || pos > S->length || len < 1) return false; // 检查位置和长度的有效性if (pos + len - 1 > S->length) return false; // 检查是否超出原字符串范围// 为Sub分配空间if (Sub->ch != NULL)free(Sub->ch);Sub->ch = (char*)malloc(sizeof(char) * (len + 1 + AddCh));if (Sub->ch == NULL) return false;// 复制子串for (int i = 0; i < len; i++) {Sub->ch[i] = S->ch[pos - 1 + i]; // 逐个字符复制}Sub->length = len; // 设置子串长度Sub->ch[Sub->length] = '\0';return true; // 复制成功
}// 串联接
bool Concat(HString* T, HString* S1, HString* S2) {if (T->ch != NULL) {free(T->ch);}T->ch = (char*)malloc(sizeof(char) * (S1->length+S2->length + 1 + AddCh));if (T->ch == NULL) return false;int i = 0;// 复制第一个字符串for (i = 0; i < S1->length; i++) {T->ch[i] = S1->ch[i];}// 复制第二个字符串for (i = 0; i < S2->length; i++) {T->ch[S1->length + i] = S2->ch[i];}T->length = S1->length + S2->length; // 设置新字符串的长度T->ch[T->length] = '\0';return true; // 串联成功
}// 8. 定位操作  
// 函数功能：在字符串S中查找子串T，返回T在S中首次出现的位置。如果T不是S的子串，则返回0。  
// 优化算法后续提供
int INdex(HString* S, HString* T) {// 如果T的长度大于S的长度，则T不可能是S的子串，直接返回0。  if (T->length > S->length) return 0;int cnt = 0; // 用于记录当前匹配的字符数量  // 外层循环，遍历S字符串，直到S中剩余的长度小于T的长度，此时无需继续比较。  for (int i = 0; i <= S->length - T->length; i++) {cnt = 0; // 每次开始新的匹配时，重置计数器  // 内层循环，遍历T字符串，进行字符匹配  for (int j = 0; j < T->length; j++) {// 如果S和T中的字符不匹配，则跳出内层循环  if (S->ch[i + j] != T->ch[j]) {break;}cnt++; // 如果字符匹配，计数器加1  }// 如果计数器值等于T的长度，说明T是S的子串，返回T在S中的起始位置（位置从1开始计数）  if (cnt == T->length) return i + 1;}// 如果遍历完S仍未找到T，则返回0  return 0;
}// 9. 清空操作
void ClearString(HString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;}
}// 10. 销毁操作、
void DestroyString(HString* S) {if (S != NULL) { // 检查指针有效性S->length = 0;if (S->ch != NULL)free(S->ch);}
}int main() {HString str1, str2, str3, substr, concatStr;// 初始化字符串  if (!InitString(&str1)) {printf("初始化str1失败\n");return 1;}if (!InitString(&str2)) {printf("初始化str2失败\n");DestroyString(&str1);return 1;}if (!InitString(&str3)) {printf("初始化str3失败\n");DestroyString(&str1);DestroyString(&str2);return 1;}if (!InitString(&substr)) {printf("初始化substr失败\n");DestroyString(&str1);DestroyString(&str2);DestroyString(&str3);return 1;}if (!InitString(&concatStr)) {printf("初始化concatStr失败\n");DestroyString(&str1);DestroyString(&str2);DestroyString(&str3);DestroyString(&substr);return 1;}// 赋值  if (!StrAssign(&str1, &str2)) {printf("赋值失败\n");// 清理资源...  return 1;}// 复制操作  if (!StrCopy(&str3, "Hello, World!")) {printf("复制操作失败\n");// 清理资源...  return 1;}// 打印字符串  PrintString(&str1);PrintString(&str3);// 比较操作  int result = StrCompare(&str1, &str3);printf("比较结果: %d\n", result);// 求子串  if (StrLength(&str3) >= 7) {if (SubString(&substr, &str3, 1, 5)) {PrintString(&substr);}else {printf("求子串失败\n");}}// 串联接  if (Concat(&concatStr, &str1, &str3)) {PrintString(&concatStr);}else {printf("串联接失败\n");}// 销毁所有字符串  DestroyString(&str1);DestroyString(&str2);DestroyString(&str3);DestroyString(&substr);DestroyString(&concatStr);return 0;
}

数据结构-串-了解串-串的基本操作

一、了解串

串的定义

串的存储结构

1. 串的定长顺序存储表示

2. 堆分配存储表示

3. 块链存储表示--暂时未写代码

串的基本操作

1. 串的结构表示

2. 赋值操作

3. 判空操作

4. 比较操作

5. 求串长

6. 求子串

7. 串联接

8. 定位操作

9. 清空操作

10. 销毁操作

二、串的定长顺序存储表示（C语言）

1. 定长顺序存储结构

2. 赋值操作

3. 判空操作

4. 比较操作

5. 求串长

6. 求子串

7. 串联接

8. 定位操作

9. 清空操作

10. 销毁操作

11. 复制操作

12. 打印字符串

三、堆分配存储表示（C语言）

1. 堆分配存储表示

2. 赋值操作

3. 判空操作

4. 比较操作

5. 求串长

6. 求子串

7. 串联接

8. 定位操作

9. 清空操作

10. 销毁操作

11. 复制操作

12. 打印字符串

四、总代码（C语言）

1、串的定长顺序存储表示-示例

2、堆分配存储表示 - 案例

相关文章