最长公共子串

求两个字符串s1、s2（长度分别为m、n）最长公共子串长度

矩阵比较

• 将两个字符串分别以行、列组成矩阵M

• 对矩阵中每个元素$M[i, j]$，若对应行、列字符相同

  • 元素置为1，否则置0

  • 置元素$M[i,j] = M[i-1, j-1] + 1$，否则置0

• 则矩阵中最长的非0斜序列对应子串即为最长公共子串

算法特点

• 时间效率$\in \Theta(mn)$
• 输入增强

最长公共子序列

求两个序列X、Y的最长公共子序列

• 子序列：去掉给定序列中部分元素，子序列中元素在原始序列中 不必相邻
• 最长公共子序列可能有很多

动态规划

• 先使用动态规划确认最长子序列长度，构造动态规划表

  $$C[i,j] = \left \{ \begin{array}{l} 0 & i=0 或 j=0 \\ C[i-1, j-1] & i,j > 0 且 X[i] == Y[j] \\ max\{C[i-1, j], C[i, j-1]\} & i,j > 0 且 X[i] != Y[j] \\ \end{array} \right.$$

  • $C[i,j]$：序列X前i个元素子序列、序列Y前j个元素子序列 最大子序列长度

• 根据动态规划表找出最长公共子序列

  

  • 从动态规划表中首个格子开始，沿着某条格子路径达到 表中最后一个元素
  • 路径中值改变格子对应序列中元素即为最长公共子序列中 元素

  • 不同格子路径可能找到不同的最长公共子序列

算法特点

• 时间效率

  • 动态规划部分$\in \Theta(|X||Y|)$
  • 生成公共子序列部分$\in Theta(|X|+|Y|)$

• 动态规划

最长升/降序序列

寻找长度为N的序列L中最长单调自增子序列

最长公共子序列法

• 将原序列升序排序后得到$L^{ * }$
• 原问题转换为求$L, L^{ * }$最长公共子序列

算法特点

• 时间效率：$\in \Theta(|L|^2)$

动态规划法

• 使用动态规划法求出以$L[i]$结尾的最长升序子序列长度， 得到动态规划表

  $$C[i] = \left \{ \begin{array}{l} max\{C[j]\} + 1, j=1,\cdots,i-1, L[j]<L[i] & i \geq 2 \\ 1 & i=1 \end{array} \right.$$

  • $C[i]$：以$L[i]$结尾的最长升序子序列长度

• 则动态规划表中值最大者即为最长升序序列长度

算法特点

• 时间效率$\in O(|L|^2)$

动态规划2

使用线性表记录当前能够找到的“最长上升子序列”

• 若当前元素大于列表最后（大）元素：显然push进线性表

  • 则当前线性表长度就是当前子串中最长上升子序列

• 若当前元素不大于列表中最后元素

  • 考虑其后还有元素，可能存在包含其的更长上升序列
  • 使用其替换线性表中首个大于其的元素
    • 隐式得到以当前元素为结尾的最长上升子序列：其及 其之前元素
    • 更新包含其的上升子序列的要求：之后元素大于其
  • 不影响已有最长上升子序列长度，且若之后出现更长上升 子序列，则线性表被逐渐替换

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

lengthOfLIS(nums[0..n-1]):
	// 动态规划求解最上升子序列
	// 输入：序列nums
	// 输出：最长上升子序列长度
	if n == 0:
		return 0
	LIS = InitVector()
	for num in nums:
		if num > LIS.last()
			LIS.push(num)
		else:
			for idx=0 to LIS.len():
				if num <= LIS[idx]:
					break
			LIS[idx] = num
				// 更新上升子序列中首个大于当前元素的元素
	return LIS.len()

动态规划+二分

最长回文子串

中心扩展法

• 遍历串，以当前元素为中心向两边扩展寻找以回文串

• 为能找到偶数长度回文串，可以在串各元素间填充空位

  

  • 填充后元素位置$i = 2 i + 1$、填充符位置$2 i$
  • 两端也要填充：否则可能出现#为中心回文和端点回文 等长，但返回#中心回文
  • 填充后得到最长回文串肯定是原最长回文串扩展
    • 非#中心：原串不存在偶数长度回文串更长，则显然
    • #中心：显然

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

LongestSubParlidrome(nums[0..n-1]):
	// 中心扩展法求解最长回文子串
	// 输入：串nums[0..n-1]
	// 输出：最长回文串
	nnums = padding(nums)
	nn = len(nnums)
	max_shift, center = 0, -1
	for i=0 to nn:
		shift = 1
		while i >= shift and i + shift < nn:
			if nnums[i-shift] != nnums[i+shift]:
				break
			shift += 1

		// 越界、不匹配，均为-1得到正确、有效`shift`
		shift -= 1

		if shift > max_shift:
			max_shift, center = shift, i

	left = (center - max_shift + 1) // 2
	right = (center + max_shift) // 2
	return nums[left : right]

特点

• 算法效率
  • 时间复杂度$\in O(n^2)$
  • 空间复杂度$\in O(1)$

动态规划

Manacher算法

• 考虑已经得到的以$i$为中心、半径为$d$回文子串对称性

  • 则$[i-d, i+d+1)$范围内中回文对称
  • 即若$i-j, j<d$为半径为$dd$的回文串中心，则$2i - j$ 同样为半径为$dd$的回文串中心 （$[i-d, i+d-1)$范围内）

• 所以可以利用之前回文串信息减少之后回文串检测

• Manacher算法同样有中心扩展算法问题，要填充检测偶数长串

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

LongestSubParlidrome(nums[0..n-1]):
	// Manacher算法利用之前回文串信息求解最长回文子串
	// 输入：串nums[0..n-1]
	// 输出：最长回文串
	nnums = padding(nums)
	nn = len(nnums)
	shift_d = [0] * nn
	max_shift, center = 0, 0
	for i=0 to nn:

		// 利用之前信息初始化
		shift = shift_d[i]

		while shift <= i and shift < nn - i:
			if nnums[i+shift] != nnums[i - shift]:
				break
			shift += 1
		shift -= 1

		// 更新可利用信息
		for j=1 to shift:
			shift_d[i+j] = max(
				shift_d[i+j],
				min(shift_d[i-j], i+j-shift))

		if shift > max_shift:
			max_shift, center = shift, i

	left = (center - max_shift + 1) // 2
	right = (center + max_shift) // 2
	return nums[left: right]

特点

• 算法效率
  • 时间复杂度$\in \Theta(n)$
  • 空间复杂度$\in \Theta(n)$

矩阵分解

• 矩阵加法分解：将矩阵分解为三角阵、对角阵之和

  • 常用于迭代求解线性方程组

• 矩阵乘法分解：将矩阵分解为三角镇、对角阵、正交阵之积

• 以下分解均在实数域上，扩展至复数域需同样将相应因子矩阵 扩充至复数域上定义

矩阵加法分解

Jacobi分解

Jacobi分解：将矩阵分解为对角阵、非对角阵

Gauss-Seidel分解

Gauss-Seidel分解：将矩阵分解为上、下三角矩阵

Successive Over Relaxation

SOR：逐次超松弛迭代法，分解为对角、上三角、上三角矩阵，同时 增加权重$w$调整分解后比例

• 利用内在等式应用的平衡性、不动点收敛理论可以快速迭代
  • $x$拆分到等式左右两侧，可以视为$y=x$和另外函数交点
  • 根据不动点收敛理论可以进行迭代求解

LU系列分解

LU Decomposition

LU分解：将方阵分解为lower triangualr matrix、 upper triangluar matrix

• $L$：下三角矩阵
• $U$：上三角矩阵

• 特别的可以要求某个矩阵对角线元素为1
• 几何意义：由单位阵出发，经过竖直、水平切变

特点

• LU分解实际上不需要额外存储空间，矩阵L、U可以合并存储

• LU分解可以快速求解线性方程组，可以视为高斯消元法的矩阵 形式

  • 得到矩阵LU分解后，对任意向量b，可使用已有LU分解 求解

    • L为消元过程中的行系数和对角线全为1的下三角矩阵 （负系数在矩阵中为正值）
    • U为消元结果上三角矩阵

  • 则解方程组$Ax=b$等价于$LUx=b$

    • 先求解$Ly=b$
    • 再求解$Ux=x$

LDU Decomposition

LDU分解：将矩阵分解为下三角、上三角、对角矩阵

• LU分解可以方便的得到LDU分解：提取对角阵、然后对应矩阵 元素等比缩放

PLU[Q] Decomposition

• PLU分解：将方阵分解为置换矩阵、下三角、上三角矩阵
• PLUQ分解：将方阵分解为置换矩阵、下三角、上三角、置换矩阵

• 考虑$P^{-1}A=LU$，交换$A$行即可作普通LU分解，PLUQ分解 类似
• PLU分解数值稳定性好、实用工具

LL/Cholesky Decomposition

LL分解：将对称阵分解为下三角、转置

• Cholesky分解常用于分解$A^TA$

  • 常用于相关分析，分解相关系数阵、协方差阵

• 相较于一般LU分解，Cholesky分解速度更快、数值稳定性更好

• 类似的有LDL分解，同时提取对角线元素即可

Singular Value Decomposition

SVD奇异值分解：将矩阵分解为正交矩阵、对角矩阵、正交矩阵

• 特征值分解在任意矩阵上推广：相应的特征值、特征向量 被称为奇异值、奇异向量
• 几何意义：由单位阵出发，经旋转、缩放、再旋转

特点

• $\Sigma$对角线元素为$M^T M$、$M M^T$的奇异值

  • 可视为在输入输出间进行标量的放缩控制
  • 同$U$、$V$的列向量相对应

• $U$的列向量称为左奇异向量

  • $M M^T$的特征向量
  • 与$M$正交的“输入”或“分析”基向量

• $V$的列向量成为右奇异向量

  • $M^T M$的特征向量
  • 与$M$正交的“输出”基向量

低阶近似

• 对$m * n$阶原始矩阵$M$

  • 设其秩为$K \leq min(m, n)$，奇异值为 $d_1 \geq d_2 \geq \cdots \geq d_K > 0$
  • 不失一般性可以设其均值为0

• 根据Eckart and Young的结果

  $$\forall r \leq K, \sum_{k=1}^r d_k u_k v_k^T = \arg\min_{\bar M \in M(r)} \| M - \bar M \|_F^2$$

  • $u_k, v_k$：$U, V$的第$k$列向量
  • $|M|_F$：矩阵的Frobenius范数

QR Decomposition

QR分解：将矩阵分解为正交矩阵、上三角矩阵

• 几何意义：由单位阵出发，经旋转、切变

特点

• 正交矩阵逆为其转置，同样可以方便求解线性方程组

线性表综述

线性表：n个数据元素的有限序列

• 元素个数n定义为线性表长度，n=0时称为空表
• 非空表中每个元素都有确定的位置

顺序存储结构

顺序存储结构/映像：使用一组地址连续的存储单元依次存储数据 元素

• 具体参见algorithm/data_structure_intro

顺序表

顺序表：顺序存储结构的线性表

1
2
3
4
5

typedef struct{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

• 以元素在计算机内物理位置相邻表示线性表中数据元素之间 的逻辑关系

• 每个数据元素存储位置和线性表起始位置，相差和其在线性表中 位序成正比常数，所以顺序表时一种随机存取存储结构

  • 高级程序语言中数组类型也有随机存取特点，因此通常 用数组描述

时间效率

• 插入/删除：$O(n)$
  • 主要时间耗费在移动元素上
• 求表长：$O(1)$
• 取第n个元素：$O(1)$

链式存储结构

链式/非顺序存储结构/映像：用一组任意存储单元存储线性表 中数据元素，还需存储一个指示其直接后继的信息

• 具体参见algorithm/data_structure_intro

（线性/单）链表

线性链表：n个节点链接而成

1
2
3
4

typedef struct LNode{
	ElemType data;
	struct LNode * next;
}LNode, *LinkList;

• 链表中每个节点只包含一个指针域
  • 数据元素之间的逻辑关系由节点中指针指示，即指针为数据 元素之间的逻辑关系映像
• 整个链表存取必须从头指针开始
• 单链表中任何两个元素存储位置之间没有固定联系，是非随机 存取存储结构

• 头指针：指示链表中第一个节点的存储位置
• 头节点：在单链表第一个节点之前附设的节点，其数据域可以 不存储信息，也可以存储线性表长度、尾指针等附加信息

时间效率

• 插入、删除：$O(n)$
  • 已知插入、删除元素确切位置的情况下，仅需修改指针， 而不需要移动元素
• 取第n个元素：$O(n)$
  • 访问时间依赖元素在列表中位置

说明

• 在很多场合下，链表是线性表的首选结构

  • 链表不需要事先分配任何存储空间，空间利用合理
  • 插入、删除效率高，只需要重连相关指针

• 但是存在一些实现问题

  • 求线性表长不如顺序存储结构

• 链表中结点关系使用指针表示，数据元素在线性表中“位序” 概念淡化，被“位置”代替

因此重新定义带头结点的线性链表

1
2
3
4
5
6
7
8

typedef struct LNode{
	ElemType data;
	struct LNode * next;
}*Link, * Position;
typedef struct {
	Link head, tail;
	int len;
}

单链表注意事项

• 头结点/头指针：处理链表非常方便的技巧

  • 头指针指向链表首个结点：便于调整首个节点位置时，仍然 记住链表
  • 头指针不包含链表信息，本质不属于链表：有些情况下方便 统一代码，不需要特殊考虑链表首个节点

• 对链表进行可能改变链表的遍历操作：一般使用两个标记 结点/指针

  • 头结点/指针lstart：记住链表
  • 遍历标记指针cur：标记处理结点

• 交换节点：标记指针需要指向当前处理节点的前一个结点

  • 单链表中只有指向下个节点的指针，若标记指针指向当前 节点，则无法方便将链表同当前节点断开、重连
  • 注意待交换两个节点为同一节点的情况：不同于值交换 ，这种情况可能导致链表错误连接成环

• 无指针、纯引用对象语言（python）中：只能使用节点对象 遍历链表

  • 变量为链表中节点引用：使用类似普通指针，需要注意 别修改引用节点数据
  • 变量为额外节点引用：内存类似普通指针，使用时注意 解析引用次数

静态链表

静态链表：使用数组描述的链表

1
2
3
4

typedef struct{
	ElemType data;
	int cur;
}component, SLinkList[MAXSIZE];

• 数组分量表示节点
• 使用游标cur作为指针域指示节点在链表中的逻辑位置
• 第0个分量表示头节点，其指针域cur指向链表第一个节点

• 方便在无指针高级语言中使用链式结构
• 为确定未使用的数组分量，可以将未被使用的、删除的分量用 游标链成备用边表

Circular Linked List

循环链表：表中最后一个节点指针域指向头节点，整个链表形成环

• 循环链表和线性链表操作基本一致
  • 仅循环条件不再是指针域为空，而是是否等于头指针

Double Linked List

双向链表：链表中有两个指针域，分别指向直接后继、直接前驱

1
2
3
4
5

typedef struct DuLNode{
	ElemType data;
	Struct DulNode * prior;
	Struct DulNode * next;
}DuLNode, * DuLinkList;

• 双向链表克服线性链表寻找直接前驱时间$O(n)$的缺点
• 双向链表大部分操作和线性链表相同，指示有些操作需要同时 修改两个指针

• 字符串：数组实现的一种数据结构
  • 字符串常见操作不同于其他数组
    • 计算字符串长度
    • 按照字典序确定字符串排序时位置
    • 连接字符串构

综述

• 数组、广义表可以看作是线性表的扩展：线性表中数据元素本身 也是抽象数据结构

Array

对各维界分别为$b_i$的n维数组

• 数组中含有$\prod_{i=1}^n b_i$个数据元素，每个元素都受n个 关系约束

  • 每个关系中，元素都有直接后继
  • 就单个关系而言，这个n个关系仍然是线性关系

• n维数组可看作是线性表的推广，n=1时，数组退化为定长线性表

  • 和线性表一样，所有数据元素必须为同一数据类型

• 数组一旦被定义，其维数、维界就不再改变

  • 除了初始化、销毁之外，数组只有存储、修改元素值的操作
  • 采用顺序存储结构表示数组是自然的

• 几乎所有程序设计语言都把数组类型设定为固有类型

顺序存储表示

• 存储单元是一维结构，数组是多维结构，所有使用连续存储单元 存储数组的数据元素需要约定次序

  • BASIC、PL/1、COBOL、PASCAL、C语言中，以行序作主序
  • FORTRAN中，以列序作主序

• 数组元素存储地址

  $$\begin{align*} LOC(j_1, j_2, \cdots, j_n) & = LOC(0, 0, \cdots, 0) + (\sum_{i=1}^{n-1} j_i (\prod_{k=i+1}^n b_k + j_n))L & = LOC(0, 0, \cdots, 0) + \sum_{i=1}^n c_i_i \end{align}$$

  • $cn=L, c{i-1} = b_ic_i$

1
2
3
4
5
6
7
8
9

typedef struct{
	Elemtype * base;
	int dim;
		// 数组维数
	int * bounds;
		// 数组各维界（各维度长度）
	int * constants;
		// 数组各维度单位含有的数组元素数量，由`bounds`累乘
}

矩阵压缩

压缩存储：为多个值相同元只分配一个存储空间，对0元不分配空间

特殊矩阵

特殊矩阵：值相同元素、0元素在矩阵的分布有一定规律，将其压缩 至一维数组中，并找到每个非零元在一维数组中的对应关系

• 对称矩阵：为每对对称元分配一个存储空间
  • 一般以行序为主序存储其下三角（包括对角线）中的元
• 上/下三角矩阵：类似对称矩阵只存储上/下三角中的元，附加 存储下/三角常数
• 对角矩阵：同样可以按照行、列、对角线优先压缩存储

稀疏矩阵

稀疏矩阵：稀疏因子$\sigma = \frac t {mn} \leq 0.05$的矩阵

• 使用三元组（非零元值、其所属的行列位置）表示非零元

三元组顺序表

三元组顺序表/有序双下标法：以顺序结构表示三元组表

1
2
3
4
5
6
7
8
9

typedef struct{
	int i, j;
	ElemType e;
}Triple;
typedef struct{
	Triple data[MAXSIZE+1];
	int mu, nu, tu;
		// 行、列、非零元数
}TSMatrix;

• data域中非零元的三元组以行序为主序顺序排列，有利于进行 依行顺序处理的矩阵运算

行逻辑链接的顺序表

行逻辑链接的顺序表：带行链接信息的三元组表

1
2
3
4
5
6

typedef struct{
	Triple data[MAXSIZE+1];
	int rpos[MAXRC+1];
		// 各行首个非零元的位置表
	int mu, nu, tu;
}RLSMatrix;

• 为了便于随机存取任意行非零元，需要知道每行首个去非零元 在三元组表中的位置，即rpos

十字链表

十字链表：采用链式存储结构表示三元组的线性表

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct OLNode{
	int i,j;
		// 该非零元行、列下标
	ElemType e;
	struct OLNode, *right, *down;
		// 该非零元所在行表、列表的后继链域
}OLNode, *OLink;
typedef struct{
	OLink *rhead, *chead;
		// 行、列链表表头指针向量基址
	int mu, nu, tu;
}CrossList;

• 同一行非零元通过right域链接成一个线性链表
• 同一列非零元通过down域链接成一个线性链表

• 适合矩阵非零元个数、位置在操作过程中变化较大的情况

Lists

广义表/列表：线性表的推广

• $\alpha_i$：可以时单个元素，也可以是广义表，分别称为LS 的原子、子表
• head：表头，LS非空时的首个元素$\alpha$
• tail：表尾，LS除表头外的其余元素组成的表，必然是列表

• 列表是一个多层次结构：列表的元素可以是子表，子表元素 也可以是子表
• 列表可以为其他列表所共享
• 列表可以是一个递归的表：即列表自身作为其本身子表

• 广义表长度：广义表中元素个数
• 广义表深度：广义表中最大括弧重数

链式存储结构

广义表中数据元素可以具有不同结构，难以用顺序存储结构表示， 通常采用链式存储结构

头尾链表

• 数据元素可能是原子、列表，因此需要两种结构的结点
  • 表节点：表示列表，包括：标志域、指示表头的指针域、 指示表尾的指针域
  • 原子节点：表示原子，包括：标志域，值域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef enum{ATOM, LIST} ElemTag;

typedef struct GLNode{
	ElemTag tag;
		// 标志域，公用
	union{
		// 原子节点、表节点联合部分
		AtomType atom;
			// 值域，原子节点
		struct{
			struct GLNode *hp, *tp;
				// 两个指针域，表节点
		}ptr;
	};
}*GList;

• 除空表的表头指针为空外，任何非空列表的表头指针均指向 表节点，且该表节点
  • hp指针域指向列表表头
  • tp指针域指向列表表尾，除非表尾为空，否则指向表节点
• 容易分清列表中原子、子表所属层次
• 最高层的表节点个数即为列表长度

扩展线性链表

1
2
3
4
5
6
7
8
9
10

typedef enum {ATOM, LIST} ElemTag;

typedef struct GLNode{
	ElemTag tag;
	union{
		AtomType atom;
		struct GLNode *hp;
		};
	struct GLNode *tp;
}*GList;

• 从数据结构来看，栈和队列也是线性表，但其基本操作是线性表 操作的子集
• 从数据类型来看，栈和队列是和线性表不同的抽象数据类型

Stack

栈：限定在表尾/栈顶进行插入和删除、操作受限的线性表

• top：栈顶，表尾端
• bottom：栈底，表头端

• 栈的修改是按照LIFO的方式运转，又称后进先出的线性表

  • 入栈：插入元素
  • 出栈：删除栈顶元素

• last in first out/栈应用广泛，对实现递归操作必不可少

顺序存储结构

顺序栈

顺序栈：顺序映像存储栈底到栈顶的数据元素，同时附设指针指示 栈顶元素在顺序栈帧中的位置

1
2
3
4
5

typedef struct{
	SElemType * base;
	SElemType *top;
	int stacksize;
}SqStack;

• base永远指向栈底，top指向栈顶元素下个位置

  • base==NULL：栈不存在
  • top==base：表示空栈

• 栈在使用过程中所需最大空间难以估计，因此一般初始化设空栈 时不应限定栈的最大容量，应分配基本容量，逐渐增加

链式存储结构

Queue

队列：限定在表尾/队尾进行插入、在表头/队头进行删除的 受限线性表

• rear：队尾，允许插入的一端
• front：队头，允许删除的一端

• 队列是一种FIFO的线性表
• 队列在程序设计中经常出现
  • 操作系统作业排队
  • 图的广度优先遍历

链式存储结构

链队列

链队列：使用链表表示的队列

1
2
3
4
5
6
7
8

typedef struct QNode{
	QElemType data;
	struct QNode  * next;
}QNode, *QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

• front：头指针
• rear：尾指针

• 为方便同样给链队列添加头结点，令头指针指向头结点，此时 空队列判断条件为头、尾指针均指向头结点
• 链队列的操作即为单链表插入、删除操作的特殊情况的，需要 同时修改头、尾指针

顺序存储结构

循环队列

循环队列：使用顺序结构存储队列元素，附设两个指针分别指示对头 、队尾的位置

• 为充分利用数组空间，将数组视为环状空间

1
2
3
4
5

typedef struct{
	QElemType * base;
	int front;
	int rear;
}

• front：头指针
• rear：尾指针
• 循环队列时，无法通过rear==front判断队列空、满，可以在 环上、环外设置标志位判断

• C语言中无法用动态分配的一维数组实现循环队列，必须设置 最大队列长度，如果无法确定，应该使用链队列

Deque

双端队列：限定删除、插入操作在表两端进行的线性表

• 输出受限双端队列：一个端点允许删除、插入，另一个端点只 允许插入
• 输入受限双端队列：一个端点允许删除、插入，另一个端点只 允许删除
• 栈底邻接的两个栈：限定某个端点插入元素只能从该端点删除

• 看起了灵活，但是实际应用不多

Priority Queue优先队列

• 用于从一个动态改变的候选集合中选择一个优先级高的元素
• 主要操作
  • 查找、删除最大元素
  • 插入元素
• 实现
  • 可以基于数组、有序数组实现
  • 基于heap的优先队列实现更好

综述

串/字符串：零个或多个字符组成的有限序列

• 文本串：字母、数字、特殊符号构成
• 位串：0、1构成
• 基因序列：可以使用字符串模型表示，其字母表只包括4个 字母{A, C, G, T}

• $s$：串名，其后单引号括起是串的值
• $a_i$：字母、数字等字符
• $n$：串中字符的数目，串长度，零个字符的串称为空串

• 串的逻辑结构和线性表相似，只是串的数据对象约束为字符集
• 串的基本操作和线性表有很大差别
  • 线性表基本操作大多以“单个元素”作为操作对象
  • 串的基本操作通常以“串的整体”作为操作对象

串的存储表示

• 串只作为输入、输出常量出现，则只需要存储串的串值字符序列
• 在非数值处理中，串也以变量形式出现

定长顺序存储

• 类似线性表的顺序存储结构
• 按照预定义大小，为每个定义的串变量分配固定长度的存储区， 存储字符序列

1

typedef unsigned char SString[MAXSTRLEN+1]

• 串实际长度在预定义范围内随意，超过预定义长度的串值则被 舍去（截断）
• 串实际长度存储方式
  • 以下标为0的数组分量存放：Pascal
  • 在串值后面加入不计串长的结束标记字符：C以\0标记， 此时串长为隐含值，不利于某些操作
• 串操作的原操作为“字符序列的复制”，操作的时间复杂度基于 复制的字符序列长度

堆分配存储

• 仍然以地址连续的存储单元存储串字符序列，但存储空间是在 程序执行过程中动态分配得到

1
2
3
4

typdef struct{
	char *ch;
	int length;
}

• length：串长

• 既有顺序存储结构的特点，处理方便，对串长又没有任何限制
• 此存储结构的串操作仍是基于“字符序列的复制”进行

块链存储

• 使用链表的方式存储串值
• 但是串结构特殊的，需要设置节点大小

1
2
3
4
5
6
7
8

typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct CHUNK * next;
}Chunk;
typedef struct{
	Chunk *head, *tail;
	int curlen;
}

• CHUNKSIZE：节点大小，每个节点中最大存储字符数量
• curlen：当前串长度

• 节点大小不为1时，链表最后一个节点不一定全被串值占满， 此时通常补上非串值字符
• 一般情况下，对串进行操作时，只需要从头到尾扫描即可
  • 对串值不必简历双向链表
  • 设尾指针是为了方便进行联结操作（联结操作需要注意 串尾无效字符）
• 节点大小选择影响串处理效率
  • 存储效率 = 串值所占存储位/实际分配存储位
  • 存储密度小，运算处理方便，存储量占用大
• 块链结构对某些串操作有一定方便，但是总的来说不如另外两种 存储结构灵活，存储量大、操作复杂

串的模式匹配

模式匹配：子串定位操作