线性结构

最多只有一个出度和一个入度

线性表

• 最基本最常用的线性结构
• 是零个或多个元素的有穷序列，通常可以表示为k₀, k₁, ... k_n-1(n>=1)
• 线性表中的元素叫表目或者记录
• i 称为表目 k_i 的 索引 或 下标
• n是表的长度
• 长度为零的线性表叫空表

特点

• 灵活，长度可增长、缩短

1. 顺序存储结构(顺序表)

一组地址 连续的存储单元 依次存储线性表中的数据元素，逻辑上相邻的两个元素在物理位置上也相邻

• 优点：可以随机存取表中的元素
• 缺点：插入和删除需要移动元素

2. 链式存储结构(链表)

通过指针链接起来的结点（地址不要求连续）存储数据元素，有一个数据域和一个指针域，指针域中的信息称为指针(或链)

结点空间只在需要的时候才申请，无须事先分配

• 单链表
• 双向链表： 每个结点包含两个指针
• 循环链表： 表尾指针纸箱链表第一个结点
• 静态链表： 借助数组来描述线性表的链式存储结构

栈

• LIFO last in first out
• 插入和删除操作都限制在表的同一端进行
• 不含数据的栈叫空栈
• 应用：深搜
• 可以用数组来实现堆栈，也可以用链表（单向链尾不能找到前一个）来实现堆栈

// 抽象数据结构
// 通常由一个一维数组和一个记录栈顶元素位置的变量组成

1. 中缀表达式转换为后缀表达式

1. 从头到尾读取中缀表达式的每个对象
2. 假如是运算符：直接输出
3. 假如是左括号：压入堆栈
4. 假如是右括号，将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
5. 运算符：
   • 若优先级大于栈顶运算符时，则把它压栈；
   • 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；
   • 再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈
6. 若各对象处理完毕，则把堆栈中存留的运算符一并输出

队列

• FIFP first in first out
• 插入操作在表的一端，删除操作在另一端；队头（Front），队尾（Rear）
• 应用：宽搜
• 也是一种受限制的线性表

1. 顺序队列

2. 循环队列

串

• 由字符构成的有限序列

模式匹配算法