【字符串的定义】

1.字符集

一个字符集 $\Sigma$ 是一个建立了全序关系的集合，也就是说，$\Sigma$ 中的任意两个不同的元素 $\alpha$ 和 $\beta$ 都可以比较大小，要么 $\alpha<\beta$，要么 $\alpha>\beta$

字符集 $\Sigma$ 中的元素称为字符

2.字符串

一个字符串 $S$ 是将 $n$ 个字符顺次排列形成的序列，$n=|S|$ 称为字符串的长度

当 $i$ 从 $0$ 开始，$S$ 的第 $i$ 个字符记为 $S[i-1]$；当 $i$ 从 $1$ 开始，则 $S$ 的第 $i$ 个字符记为 $S[i]$

当 $n=0$ 时，$S$ 称为空串，而当两字符串长度相等且对应位置字符相同时，称两个字符串相等

3.子序列

字符串 $S$ 的子序列是从 $S$ 中将若干元素提取出来并不改变相对位置形成的序列，即：

$S[p_1],S[p_2],...,S[p_k],1\leq p_1 \leq p_2 \leq ... \leq p_k\leq n$

4.子串

字符串 $S$ 的子串 $S[i..j],i\leq j$，表示 $S$ 中从 $i$ 到 $j$ 的位置

即字符串中任意个连续的字符组成的子序列被称为子串，同时，包含子串的字符串被称为主串

5.回文串

回文串是正着写与倒着写都相同的字符串，即：

$S[i]=S[n+1-i], 1\leq i\leq n$

6.字典序

以第 $i$ 个字符作为第 $i$ 关键字进行大小比较，空字符小于字符集内任何字符

例如，有：$a<aa$

【字符串的逻辑结构】

字符串的逻辑结构与线性表相似，区别仅在于字符串的数据对象限定为字符集

在基本操作上，线性表主要以单个元素为操作对象，如查找、插入、删除某个元素等；字符串的基本操作则是以子串为操作对象，如查找、插入一个子串等

字符串的基本操作，被称为最小操作子集，分别为：串赋值、串比较、求串长、串联接、求子串，这些操作不可能利用其它串操作来实现，但其他串操作可以在最小操作子集上实现

定长顺序存储类似于线性表的顺序存储结构，其用一组连续的存储单元存储字符序列

在字符串的定长顺序存储中，会为每个串分配一个固定长度的存储区，这个存储区被称为定长数组，而这个固定长度是预定义的最大串长 MAX_LEN ，对于超过预定义长度的串值将会被舍去，这个过程被称为截断

在 C/C++ 中，字符数组的尾部会默认加入一个不计入串长的标记字符 \0，此时串长为隐含值，但有时希望能够将串长在字符串中显示的表示出来，常见的方法有以下两种：

#define MAX_LEN 255
typedef struct { //使用len记录串长
    char ch[MAX_LEN];
    int len;
} Str;

堆分配存储，同样是以一组地址连续的存储单元来存放字符序列，但其存储空间是通过在程序执行时动态分配得到的

在 C/C++ 中，存在一个被称为堆的自由存储区，其通过 malloc()/free() 或 new/delete 来完成动态存储管理

堆分配存储一般会利用 malloc() 为每个新产生的串分配一块实际串长所需的存储空间，并返回一个指向起始地址的指针，以作为串的基地址

typedef struct {
    char *ch; //串的基地址
    int len;
} Str;

块链分配存储，是类似于线性表的链式存储结构

由于串的特殊性，每个元素只有一个字符，即每个字符 1B，而每个指针占 4B，存储密度极低

为解决这种问题，令每个结点存储多个字符，称为块，同时，进行串尾块填充，即当最后一块存不满时，使用 \0 进行填充

块链分配存储的存储结构如下

#define PIECE 4
typedef struct SNode {
    char ch[PIECE];
    struct SNode *next;
} SNode,* LinkString;