线性结构
线性表
定义及特点
n个元素的有序队列
特点：
- 存在唯一一个被称为第一个的元素
- 存在唯一一个被称为最后一个的元素
- 除第一个元素外，集合中的每个元素均只有一个直接前驱
- 除最后一个元素外，集合中的每个元素只有一个直接后继
存储结构
-
顺序存储
- 用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻
- 优点：可以随机存取表中元素，读取和查找比较方便
- 缺点：必须按最大可能长度与分配存储空间，存储空间的利用率低，表的容量难以扩容，是一种
静态存储结构，插入和删除需要移动大量元素，平均移动次数文 n/2
-
链式存储
- 存储各元素的节点的地址并不要求是连续的，逻辑上相邻的数据元素，物理上不一定相邻。
- 优点：插入与删除不需要移动元素，较为方便，只需要
修改指针即可，存储空间不需要提前确定，可以动态改变，是一种动态存储结构 - 缺点：不能对数据元素进行随机访问; 需要存储指针，有空间浪费存在
栈和队列
栈
栈是限定仅在表尾进行插入或删除的线性表。表尾称为栈顶，表头称为栈底，是一种先进后出(LIFO)的线性结构，栈的应用：括号匹配，迷宫求解，汉诺塔。
队列
队列只允许在表的一段进行插入，在另一端进行删除操作的线性表，允许插入的一端称为队尾，允许删除的一端称为队头，是一种先进先出(FIFO)的线性结构,队列的应用：操作系统中的作业排队
循环队列
循环队列是一种顺序表示的队列，用一组地址连续的存储单元依次存放从队头到队尾的元素，由于队列中队头和队尾的位置是动态变化的，要附设两个指针 front 和 rear，分别表示队头元素和队尾元素的位置。
串
串是仅由字符构成的有限序列，是一种线性表。
- 空串：长度为0的串称为空串，空串不包含任何字符
- 空格串：由一个或多个空格组成的串
- 子串：由串中任意长度的连续字符构成的序列称为子窜，含有子串的串称为主串。空串是任意串的子串
匹配算法
子串的定位操作，用于查找子串在主串中第一次出现的位置的算法
- 布鲁特-福斯算法：基本的模式匹配算法。其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等则继续逐个字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续序列相等为止，此时称为匹配成功，否则称为匹配失败。
- KMP算法：对基本匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要再回溯主串的字符位置指针，而是利用已经得到部分匹配结果，将模式串向右“滑动”尽可能远的距离，再继续比较即可