0x01：串
定义
由零个或者多个任意字符组成的有限序列。记作：
$$ S = "a_1a_2...a_n" (n\geq0) $$
- 串名为：$ S $
- 串值为用引号括起来的字符序列：$ "a_1a_2...a_n" $
- 串长(长度)即为串中字符的数目：$ n $
- 空串：含零个字符的串，一般用$ \varnothing $表示
- 空格串：由一个或者多个空格组成的串
- 子串：串中任意个连锁的字符组成的子序列；特别的，真子串是指不包括自身的所有子串
- 字符在串的位置：字符在序列中的序号
- 子串在串的位置：子串的第一个字符在主串中的序号
串的比较
通过比较俩个串中每一个组成串的字符来进行的
即，给定俩个串：$ X="x_1x_2...x_n" $和$ Y="y_1y_2...y_m" $，对这俩个串进行如下比较- 长度比较
- 串字符比较
故： - 当$ n<m $时，则称X串小于Y串，记为：$ X<Y$，反之亦然
- 当$ n=m $时，且存在$ k \leq min(m,n) $，使得$ x_i=y_i, (1 \leq i \leq k-1) $且$ x_k<y_k $，则称$ X<Y $
- 当$ n=m $时，且存在$ x_1=y_1,...,x_n=y_m $时，则称$ X=Y $即为串相等
- 串相等：当且仅当俩个串的长度相等并且各个对应位置上的字符都相等时，这俩个串才是相等的
空串与空格串的区别
- 空格串是由一个或者多个空格组成的串，而空串中什么都没有，连一个空格都没有。
串与线性表
区别
- 串的数据对象约束为字符集
串的基本操作与线性表有很大差别
- 线性表的基本操作中，大多以“单个元素”作为操作对象；例如查找某个元素、在某个位置上插入一个元素或者删除一个元素
- 串的基本操作中，通常以“串的整体”作为操作对象；例如在串中查找某个子串、在串的某个位置上插入一个子串或者在串中删除一个子串
串的表示
串的顺序存储结构
定长顺序存储结构和堆分配存储结构都是顺序存储结构，它们的主要区别是前者的串长是固定的，而后者的串长是动态的。
定长顺序存储表示
用一组地址连续的存储单元存储串值的字符序列- 非压缩形式：一个数组单元存储一个字符——浪费空间
- 压缩形式：一个数组单元存储多个字符——算法复杂
//串的顺序存储结构 #define MAXLEN 255 typedef struct{ char ch[MAXLEN + 1]; //存储串的一维数组 int length; //串的当前长度 }SString;- 堆分配存储表示
系统开辟一个串值存储空间（串值可利用空间），同时建立一个符号信息表：
建立一个新串时，在可利用空间分配，并在符号表中记录下串变量名、串值在可利用空间的位置、串长度等信息
串的链式存储结构
串的链式存储也称为串的块链式存储结构；用链表方式存储串值，每个结点大小相同。
- 结点分为俩个域：data域和next域
分为俩种存储形式：非压缩形式与压缩形式
- 结点大小为1的链表（非压缩形式）
- 结点大小为4的链表（压缩形式）
- 结点大小为1的链表（非压缩形式）
$$ 存储密度 = 串值所占的存储位 \div 实际分配的存储位 $$
块链结构的表示
#define CHUNKSIZE 80 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; typedef struct{ Chunk *head,*tail; int curlen; }LString;
串的模式匹配
定义
- 模式匹配
给定S串$ S="s_1s_2...s_n" $和T串$ T="t_1t_2...t_m" $，在$ S $中寻找$ T $的过程称为模式匹配。如果匹配成功，返回$ T $在$ S $中的位置，如果匹配失败，返回0。
通俗来讲，就是一种用来判断俩个串之间是否具有“主串与子串”关系的算法。
- 主串与子串
如果串A中包含有串B，则称串A为主串，串B为子串。主串与子串之间的关系可简单理解为一个串“包含”另一个串的关系。
BF算法
基本思路
从主串S的第一个字符开始和伪子串T的第一个字符进行比较；若相等，则继续比较俩者的后续字符；否则，从主串S的第二个字符开始和伪子串T的第一个字符进行比较... ...重复上述过程：- 直到伪子串T中的字符全部比较完毕，则说明本趟匹配成功；
- 或主串S中字符完全比较完，则说明匹配失败。
算法过程
- 在 主串S 和 伪子串T 中设比较的起始下标 i 和 j
循环直到 主串S 或 伪子串T 的所有字符比较完
- 如果存在
S[i] == T[j]成立，则继续比较 主串S 和 伪子串T 的下一个字符 - 否则，
i = i - j + 2（回溯）j = 1（从头开始）
- 如果存在
- 若 伪子串T 中的所有字符均比较完，则匹配成功，返回匹配的起始下标；否则，匹配失败，返回0
算法描述
int Index_BF(SString S, SString T, int pos){ i = pos, j = 1; while(i <= S.length && j <= T.length){ if(S[i] == T[j]){ i++; j++; }else{ i = i - j + 2; j = 1; } } if(j >= T.length){ return i - T.length; }else{ return 0; } }
KMP算法
- 基本思路
在匹配过程中，每趟匹配过程中出现字符比较不相等时，不回溯主串的主指针i，利用已得到的”部分匹配“结果将伪子串向右滑动尽可能远的一段距离后，继续进行比较。 算法过程
- 寻找前缀后缀最长公共元素长度
- 求NEXT数组（指导意见）
- 根据NEXT数组（指导意见）进行匹配
- 寻找前缀后缀最长公共元素长度
算法描述
void GetNext(int next[], SString t){ int j=0,k=-1; next[0] = -1; while(j < t.length -1){ if(k == -1 || t[j] == t[k]){ j++; k++; next[j] = k; }else{ k = next[k]; } } } int Index_KMP(SString S, SString T, int pos){ int next[MaxSize], i = pos, j = 0; GetNext(T, next); while(i < S.length && j < T.length){ if(j == -1 || S[i] == T[j]){ i++; j++; }else{ j = next[j]; // i不动，j回退 } } if(j >= T.length){ return i - T.length; // 匹配成功，返回子串位置 }else{ return -1; // 匹配失败 } }
0x02：数组
数组
数组的概念
- 数组是由一组个数固定、类型相同的数据元素组成阵列。
- 以二维数组为例：二维数组中每个元素都受到俩个线性关系的约束。即为行关系与列关系，每个关系中，每个元素$ a_{ij} $都有且仅有一个直接前驱，都有且仅有一个直接后继
$$ A_{m \times n}= \left\{ \begin{matrix} a_{00} & a_{01} & \cdots & a_{0 (n-1)}\\ a_{10} & a_{11} & \cdots & a_{1(n-1)} \\ \vdots & \vdots & \ddots & \vdots \\ a_{(m-1)0} & a_{(m-1)1} & \cdots & a_{(m-1)(n-1)} \end{matrix} \right\} $$
- 声明格式：数据类型 变量名称[长度];
例如：int num[5] = {0,1,2,3,4};
数组的特点
- 结构固定：数组在确定以后，维数与维界（数组长度、有上界与下界）不会再改变。
- 数组的数据元素具有相同的类型
- 数组的数据元素下标关系具有上下界的约束且下标有序
数组的存储
- 数组适合采用顺序存储结构。对于数组一旦确定了其维数与各维的长度，便可以为其分配存储空间。
二维数组的存储结构可以分为以行为主序存储与以列为主序存储俩种方式，以上面的$ A_{m \times n} $矩阵为例
- 以行为主序的方式
$$ A_{m \times n}=[[a_{00},a_{10},...a_{(m-1)0}],[a_{01},a_{11},...,a_{(m-1)1}],...[a_{0(n-1)},a_{1(n-1)},...,a_{(m-1)(n-1)}]] $$
- 以列为主序的方式
$$ A_{m \times n}=[[a_{00},a_{01},...a_{0(n-1)}],[a_{10},a_{11},...,a_{1(n-1)}],...[a_{(m-1)0},a_{(m-1)1},...,a_{(m-1)(n-1)}]] $$
假设二维数组$ A_{m \times n} $每个元素占用 size 个存储单元，$ Loc(a_{ij}) $为元素$ a_{ij} $的存储地址，$ Loc(a_{00}) $ 为 $ a_{00} $的存储位置，也是二维数组A的基址。故，元素$ a_{ij}$的存储位置可由以下公式获得：
- 以行为主序的情况下
$$ Loc(a_{ij})=Loc(a_{00}) + (n \times i +j) \times size $$
- 以列为主序的情况下
$$ Loc(a_{ij})=Loc(a_{00}) + (m \times i +j) \times size $$
矩阵
矩阵的压缩存储
第一类：特殊矩阵
- 定义：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵。
例如：对称矩阵、上三角矩阵、下三角矩阵、对角矩阵都是特殊矩阵 - 以下三角矩阵为例
- 定义：值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵。
$$ \left[ \begin{matrix} a_{00} & 0 & \cdots & 0\\ a_{10} & a_{11} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ a_{(m-1)0} & a_{(m-1)1} & \cdots & a_{(m-1)(n-1)} \end{matrix} \right] $$
对于下三角矩阵，只需存储下三角的非零元素。若以行序为主序进行存储，得到的序列就是
$$ a_{00},a_{10},a_{11},a_{20},...,a_{(n-1)0},a_{(n-1)1},...,a_{(n-1)(n-1)} $$
由于下三角矩阵的元素个数为$ n(n+1)/2 $，即第0行有1个元素、第1行有2个元素、...、第n-1行有n个元素，一共有$ 1+2+3+...+n = n(n+1) $个元素，所以可以将一个三角矩阵压缩到一个大小为$ n(n+1)/2 $的一维数组中
假设每个数据元素占 size 个存储单元，下三角矩阵中任意元素$ a_{ij} $在一维数据中的存储位置可以通过以下公式计算
$$ Loc[i,j] = Loc[0,0] + (\frac{i(i+1)}{2}+j) \times size (i\geq j) $$
第二类：稀疏矩阵
- 定义：有较多值相同元素或较多零元素，且值相同元素或零元素分布没有一定规律的矩阵称为稀疏矩阵。
- 压缩存储方式：采用三元组或者十字链表（TODO）
0x03：广义表
定义
广义表也称为列表，是线性表的一种拓展，也是数据元素的有序序列。记作：
$$ LS = (d_1,d_2,d_3,... ...,d_n) (n \geq 1) $$
其中，$ d_i $ 不仅可以是单个元素，也可以是广义表。
- 表名为$ LS $，$ n $ 为广义表的长度
- 在线性表中数据元素是单个元素；而在广义表中，元素可以是单个元素，称为单元素（原子），也可以是广义表，称为广义表的子表
- 一般用大写字母表示广义表，小写字母表示原子
当$ LS $ 非空时$ (n \geq 1) $，第一个元素$ d_1 $即为表头，记作：$ head(LS) = d_1 $
- 注：表头可以是原子，也可以是子表
当$ LS $ 非空时$ (n \geq 1) $，除了表头外其他元素就是表尾，记作：$ tail(LS) = (d_2,d_3,...d_n) $
- 注：表尾不是最后一个元素！！！而是一个子表
性质
- 广义表中的数据元素有相对次序：一个直接前驱和一个直接后继
- 广义表的长度定义为最外层所包含元素的个数
- 广义表的深度定义为该广义表展开后所含括号的重数
广义表可以为其他广义表共享
- 举个栗子，$ B=(A) $ 便是广义表B共享表A，在B中无须列出A的值，而是通过名称（表名）来引用
广义表可以是一个递归的表
- 栗如，$ F=(a,F)=(a,(a,(a,...))) $
- 递归表的深度是$ \infty $，长度是有限值
- 广义表是多层次结构，广义表的元素可以是原子，也可以是子表，而子表的元素也可以是子表，也可以是原子
广义表的存储结构
- 由于广义表中数据元素可以具有不同结构，故难以用顺序结构（数组）来表示广义表。通常采用链式存储结构来表示
