1. 线性表
1.1 线性表的定义
线性结构的特点：数据元素之间呈现一种线性关系，即元素"一个接一个排序"。
1.2 线性表的存储结构
线性表的存储方式有两种：顺序存储和链式存储。
基本操作：插入、删除和查找。
顺序存储（顺序表）
线性表的顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻。
- 优点：可以随机存取表中的元素。
- 缺点：插入和删除操作需要移动元素。
链式存储（链表）
线性表的链式存储是用通过指针链接起来的结点来存储数据元素。
基本结点结构：
- 数据域：用于存储数据元素的值
- 指针域：存储当前元素的直接前驱或直接后继的位置信息，指针域中的信息称为指针（链）
单链表结点类型的定义（C++）：
typedef struct node{
int data; // 结点的数据域
struct node *next; // 结点的指针域
} NODE, *LinkList;
单链表的插入与删除关键代码（Java）：
// 先将p所指结点的后继结点指针赋给s所指结点的指针域，
// 然后将p所指结点的指针域修改为s所指结点
s.next = p.next;
p.next = s;
循环单链表：最后一个结点的指针域指向头结点，形成环。
双链表：每个结点有两个指针域，分别指向前驱和后继。
2. 栈
2.1 栈的定义
栈（LIFO，后进先出）是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
- 在栈中进行插入和删除操作的一端称为栈顶（Top）
- 另一端称为栈底（Bottom）
- 不含数据元素的栈称为空栈
2.2 栈的基本运算
2.3 栈的存储结构
顺序栈
顺序栈是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示栈顶元素的位置。
链栈
栈的链式存储（链栈）。
3. 队列
3.1 队列的定义
队列（FIFO，先进先出）只允许在表的一端插入元素，而在表的另一端删除元素。
- 允许插入元素的一端称为队尾（Rear）
- 允许删除元素的一端称为队头（Front）
3.2 队列的基本运算
3.3 队列的存储结构
顺序队列
顺序队列：利用一组地址连续的存储单元存放队列中的元素。设置队头指针和队尾指针，分别指向当前的队头和队尾。
在顺序队列中，元素入队时只修改队尾指针，元素出队时只修改队头指针。
循环队列
循环队列的类型定义：
为了解决顺序队列的"假溢出"问题，将存储队列的数组首尾相连，形成循环队列。
链队列
队列的链式存储（链队列）。
4. 串
4.1 串的定义
串（字符串）是一种特殊的线性表，其数据元素为字符。
4.2 串的基本概念
4.3 串的基本操作
4.4 串的模式匹配
朴素的模式匹配算法
基本思想：从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对字符进行后续的比较，否则从主串第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次和主串中的一个连续字符序列相等时为止，此时称为匹配成功。若不能在主串中找到与模式串相同的子串，则匹配失败。
改进的模式匹配算法（KMP算法）
改进之处：每当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的"部分匹配"结果将模式串向右"滑动"尽可能远的距离，再继续进行比较。
评论