数据结构笔记（其五）--串

目录

12.串

12.1 基本操作

12.2 串的存储结构

12.3 字符串的模式匹配算法

（1）.朴素模式匹配算法

（2）.KMP算法

        i.next[]数组的求解

        ii.next[]数组的优化——nextval数组

        iii.手算nextval数组

        iiii.机算nextval数组 + KMP函数

---

12.串

        串，即字符串（string），由零个或多个字符组成的有限序列。串也是线性表。

        子串，串中任意个连续的字符组成的序列。

        主串，包含子串的串。

        空串，没有字符的串，空格串不是空串。

        字符在串中位置的描述，S = "a1a2a3..."，其编号由1开始，另外，一般都是指的该字符首次出现的位置，另外的另外，空格也算作字符。

        子串在主串中的位置，以子串第一个字符在主串中的位置来代替。

12.1 基本操作

        串的操作一般作用于子串，而非单个的字符。

        StrAssign(&T, chars)：赋值，把chars 赋值给T.

        StrCopy(&T, S)：复制，把S 复制给T.

        StrEmpty(S)：判空，判断S 是否为空串，为空，返回true；未空，返回false.

        StrLength(S)：求串长。

        ClearString(&S)：清空，将S串变为空串。（内存空间并没有收回）（所以直接length = 0，在逻辑上清除就可以了）

        DestoryString(&S)：销毁，回收串的存储内存空间。

        Concat(&T, S1, S2)：串的联接，用T 返回S1与S2 联接成的新串。

        SubString(&Sub, S, pos, len)：求子串，用Sub返回S串的从第pos个字符起往后len个的字符子串。

        Index(S, T)：定位，尝试寻找子串T在主串S中的位置，返回首次出现的位置，若没有，则返回0.

        StrCompare(S, T)：比较大小，从各串的第一个字符开始依次比较，字符的ASCll码值，值相同，则比较各串的下一位字符，先出现更大的字符的串，更大。

        当串中含有空格字符，且串中非空格字符都相等，则更长的串更大，比较时是先忽略空格的。

        只有当串的字符、长度都相等时，串才相等。

12.2 串的存储结构

        以下代码是串的存储结构以及一些重要的基本操作

//顺序
#define MAXSIZE 255		//预先定义的最大串长
class SString
{
public:char ch[MAXSIZE];	//对字符的储存int length;			//记录串的实际长度//也可以省去此变量，用ch[0]储存长度//为了使下标统一和变量分离，所以之后会将ch[0]废弃不用，并继续使用length
};
//顺序（动态分配）（堆分配存储）
class HString
{
public://构造函数HString(){ch = new char();length = 0;}char* ch;int length;
};
//链式
class StringNode
{
public:char ch[4];				//如果只是ch ，不是数组的话，单个节点的储存密度非常低，为了提高内存利用率，所以采用每个结点都存储一个小数组的方法StringNode* next;
};
using LString = StringNode*;//求串长
int StrLength(SString S)
{return S.leng