# 串

# 串的定义

1. 串：（String）零个或者多个任意字符组成的有限序列
2. 相关术语：
   1. 子串：一个串中任意个连续字符组成的子序列称为该串的子串
   2. 真子串：不包含自身的所有子串
   3. 主串：包含子串的串相应的称为主串
   4. 字符位置：字符在序列中的序号为该字符在串中的位置
   5. 空格串：由一个或者多个空格组成的串，与空串不同
   6. 串相等：当且仅当两个串的长度相等并且各个位置对应的字符都相等时，这两个串才是相等的

# 串的类型定义、存储结构及其运算

# 串的类型定义

ADT String {

​ 数据对象：

​ 数据关系：

​ 基本操作：

}

# 串的存储结构

1. 顺序存储结构：顺序串
2. 链式存储结构：链串

# 串的模式匹配算法

# BF 算法

1. BF 算法：称为简匹配算法，采用穷举法的思路
2. 算法思路：
   1. 将主串的第 pos 个字符和模式串的第一个字符比较
   2. 若相等，继续逐个比较后续字符
   3. 若不等，从主串的下一个字符起，重新与模式串的第一个字符进行比较
3. 时间复杂度：$O(n^2)$

# KMP 算法

1. KMP 算法：利用已经部分匹配的结果而加快模式串的滑动速度，且主串 S 的指针不必回溯，可使时间复杂度达到$O(n)$

# 数组

# 数组的定义

1. 数组：按照一定格式排列起来的，具有相同类型数据元素的集合
2. 一维数组：线性结构的数组
3. 二维数组：若一维数组中的元素有事一个一维数组结构，则称为二维数组
4. 二维数组的逻辑结构：
   1. 非线性结构：每个数据元素既在行表中，又在一个列表中
   2. 线性结构：该线性表的每个元素也是一个定长的线性表

# 广义表

# 定义

广义表：又称为 Lists，是 n 个元素的有限序列，其中每一个元素都是原子，或者是一个广义表

# 性质

1. 广义表中的数据元素有相对次序，一个直接前驱和一个直接后继
2. 广义表的长度定义为最外层所包含的元素个数
3. 广义表的深度定义为该广义表展开后的所包含括号的重数
4. 广义表是一个可以递归的表（类似树）