0%
线性表、栈和队列
线性表
1.链表头结点的作用
- 如果没有头结点，那么在头部插入一个 节点和在中间插入一个节点的操作是不一样的，如果加上头结点就可以去除这样的判断，代码更加简化了。
2.线性表最开始的节点没有前驱，最后一个节点没有后继
3.循环链表的优点
4.循环链表不同于循环队列，循环队列如果头指针和尾指针在最后重叠到了一起，无法判断队列已满，所以决定牺牲一个位置，让尾指针实际上为尾后指针
5.顺序表和链表的比较
栈和队列
1.栈的定义
- 限定仅在表尾进行插入和删除操作的线性表。
- 允许插入和删除的一端称为栈顶，另一端称为栈底。
- 空栈：不含任何数据元素的栈
- 栈的操作特性：后进先出
2.队列的定义
- 只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
- 允许插入的一端称为队尾，允许删除的一端称为队头。
- 空队列：不含任何数据元素的队列。
3.链栈的表示
- 运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针。
4.涉及到表达式的题目，关键就在于考虑运算符的优先级，当前符号会把符号栈中优先级更高的元素全部执行完，然后自己进栈，这是不难理解的
5.队列删除元素是在队首，添加元素是在队尾
6.尾递归和单向递归可以使用循环来消除递归。
- 尾递归就是递归语句在最后，当前环境的情况不需要保留。即使保留了也没什么用，所以不需要单独开辟堆栈来进行下一次递归，下一次的递归直接在本次递归的空间进行即可。
- 注意这里说的是能够用循环消除递归的条件。不是说消除递归的条件，事实上任何递归都可以转化为非递归
7.假溢出
- 指针没有指向最开始的位置，尾指针指向最后位置，呈现出队满的假象，所以引入循环队列
8.循环队列应该是用顺序存储机构，所以头尾指针的变化都是通过数的运算得来的，没有什么next指针
9.循环队列中
- 队头指针表示真正的队头，队尾指针表示真正队尾的下一位置。
- 初始化: front = rear = 0
- 入队时，rear = (rear + 1) % Maxsize
- 出队时，front = (front + 1) % Maxsize
- 队空的条件：front = = rear
- 队满的条件： front = = (rear + 1) % Maxsize
串、数组和广义表
1.串的定义
- 即字符串，由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表
- 串长: 串中字符个数（n ≥ 0）。 n = 0 时称为空串。
- 空白串: 由一个或多个空格符组成的串。
2.串的术语
- 子串: 串中任意个连续的字符组成的子序列
- 主串: 包含子串的串
- 字符位置: 字符在串中的序号
- 子串的位置: 子串的第一个字符在主串中的序号
- 串相等: 串长度相等，且对应位置上字符相等。
3.广义表常用术语
- 长度: 广义表中元素的个数n 。n=0 时称为空表。
- 深度: 定义为括号嵌套的最深层次。(a, (b，c，d))
- 表头: 对于任意一个非空广义表LS=(a1,a2,…,an)，它的第一个数据元素a1被称为广义表的表头。
- 表尾: 对于任意一个非空广义表，除表头外，由剩余数据元素构成的广义表(a2,a3,…,an)被称为广义表的表尾。
4.数组一旦被定义，它的维数和维界就不再改变。
- 二维数组的行序优先表示:行列索引下标为i和j对应的元素首地址为：LOC( i , j) = a + i * n + j