🔑数据结构_第四章：串

第四章、串

（一）串的定义和实现

1、定义

串，即字符串String，是由零个或多个字符组成的有限序列。一般记为：
$$
S=\ ‘a_1a_2…a_n’\ \ (n \ge 0)
$$

其中，S是串名，单引号或双引号括起来的是串的值。
a_i可以是字母、数字或其它字符。
串中字符的个数n称为串的长度。
n=0的串称为“空串”，用Φ表示。
相关定义：
- 子串：
  
  串中任意两个连续的字符组成的子序列。
- 主串：
  
  包含子串的串。
- 字符在主串中的位置：
  
  字符在串中的序号，一般都是从1开始。
- 子串在主串中的位置：
  
  子串中第一个字符在主串中的位置。
注意事项：
- 串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
- 串的基本操作——如增删改查——通常以子串为操作对象，而不是单个字符！

2、串的基本操作

（1）赋值

StrAssign(&T,chars)：把串T赋值为chars。

（2）复制

StrCopy(&T,S)：由串S复制得到串T。

（3）判空

StrEmpty(S)：若S为空串，则返回TRUE，否则返回FALSE。

（4）求串长

StrLength(S)：返回串S的元素个数。

（5）清空

ClearString(&S)：将S清空为空串。

（6）销毁

DestroyString(S)：将串S完全销毁——回收存储空间。

（7）联接

Concat(&T,S1,S2)：用T返回由S1和S2联接而成的新串。

（8）求子串

SubString(&Sub,S,pos,len)：用Sub返回串S的第pos个字符起长度为len的子串。

（9）定位

Index(S,T)：若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则返回0。

（10）比较

StrCompare(S,T)：若S>T则返回值>0，若S<T则返回值<0，且返回值为二者差值；若二者相等则返回0。

3、串的存储结构

也是有顺序存储和链式存储两种。

（1）顺序存储

#define MAXLEN 255      //预定义最大串长为255

//静态数组实现（定长顺序存储）
typedef struct{
    char ch[MAXLEN];    //每个分量存储一个字符
    int length;         //串的实际长度
}SString;

//动态数组实现（堆分配存储）
typedef struct{
    char *ch;           //按串长分配存储区，ch指向串的基地址
    int length;         //串的长度
}HString;

int main(){
    //初始化一个串
    HString S;
    S.ch = (char *)malloc(MAXLEN * sizeof(char));
    S.length = 0;
}

常见的记录串长的方法：

（2）链式存储

//********串的存储结构——链式存储********
//方式1
typedef struct StringNode{
    char ch;						//每个节点存储1个字符，导致存储密度低！
    struct StringNode * next;
}StringNode, * String;

//方式2
typedef struct StrngNode{
    char ch[4];						//每个节点存储多个字符，解救了存储密度低的问题
    struct StrinfNode * next;
}StringNode, * String;

（二）串的模式匹配

什么是字符串的模式匹配？

从字符串A里面搜寻B，A叫做主串，B叫做模式串。

字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

注：模式串不是子串，二者不是同一概念！
在408考试中需要掌握两种模式匹配算法：

朴素模式匹配算法和KMP算法。