线性结构
- 二元组
B = (K, R) , K = {a0, a1, …, an-1 }, R = {r}，其中 r 为前驱后继关系，具有反对称性和传递性 - 唯一的开始结点（表头）：没有前驱，只有一个唯一的后继
- 唯一的终止结点（表尾）：没有后继，只有一个唯一的前驱
- 内部结点：一个唯一的前驱和一个唯一的后继
线性表
线性表简称表，是零个或多个元素的有穷序列
- 表目：线性表中的元素
- 文件：含有大量记录的线性表又称为文件
- 索引（下标）
- 表的长度
- 空表：长度为零的线性表(n=0)
线性表分类
-
按访问方式划分：
- 直接访问型
- 顺序访问型
- 目录索引型
-
按存储方式：
- 顺序表（数组）
- 链表
-
按操作：
- 线性表：不限操作
- 栈：在同一端操作，在深度优先搜索、递归等算法中有很好的应用
- 队列：在两端操作，在宽度优先搜索、层次化处理中有很好的应用
顺序表
- 顺序表俗称向量，是用数组实现的（固定长度的一维数组）
- 按索引值从小到大存放在一片相邻的连续区域
- 结构紧凑，存储密度为1（存储密度 = 数据本身所占存储 / 整个数据结构所占存储）
- 物理存储关系就能表示逻辑关联关系
链表
- 链表需要指针表示逻辑关联关系，存储效率不如顺序表
- 有头链表和无头链表
- 在一些边界处理的时候，要注意头结点（head）和尾结点（tail）的特殊处理
讨论
-
线性表的分类方法有哪些？各种线性表名称中，哪些跟存储结构相关？哪些跟运算相关？
- 线性表可按访问方式分为直接访问型、顺序访问型和目录索引型；按存储方式分为顺序存储（数组，向量）和链接存储（单链表、双链表、循环链表）；按操分为普通线性表、栈（单口进出）、队列（一端进，另一端出）；
- 顺序表（数组）、链表（单链表、双链表、循环链表）跟存储结构相关，分别是顺序存储和链接存储；
- 栈、队列跟运算相关，栈是单口操作，后进先出，队列是先进先出，两者都可以用顺序存储实现，也可以用链表（链接存储）实现；
-
顺序表的操作和优缺点？在顺序表中插入和删除操作各需要考虑哪些问题？顺序表有哪些优缺点？
- 首先要检查顺序表是否上溢或下溢，其次要检查插入或删除的位置是否合法，最后为保证顺序存储的特性，要对插入或删除位置后的元素进行移位，并更新表的长度属性；
- 优点：结构紧凑，存储密度高，支持在 $\mathcal{O}(1)$ 时间内随机访问；
- 缺点：插入和删除元素需要频繁移位，效率较低，是 $\mathcal{O}(n)$ 时间复杂度。
-
顺序表和链表的特点以及在应用场景中的选择？线性表的顺序和链接两种实现方法的特点，其的插入、删除、查找等操作的代价？顺序表和链表分别适用于什么样的应用场景？
-
求数组最大子数组之和，数组 [1, -2, 3, 10, -4, 7, 2, -5]，和最大的子数组为 [3, 10, -4, 7, 2]，输出该子数组的和18，请分别思考分治法、动态规划法及其效率。
连续子数组最大和
动态规划法和线性扫描法相似，时间复杂度是 $\mathcal{O}(n)$，不过动态规划法有 $\mathcal{O}(n)$ 的空间占用；分治递归法如何记录最大子数组的区间下标呢？暴力算法时间复杂度是 $\mathcal{O}(n^3)$，前缀和算法时间复杂度 $\mathcal{O}(n^2)$，但是有 $\mathcal{O}(n)$ 的空间占用； -
如何判断单链表中是否有回路？提示，可以多想几种方法，允许改变链表结构。
- 在链表中添加一个标识，未被访问过为 false，访问过就改为 true。初始状态都设为 false，如果遍历的时候遇到标识为 true 的，说明有环路
- 可以使用Floyd判圈法(快慢指针问题)，使用 slow 和 fast 双指针，起始位置都在链表开头，fast 每次前进 2 步，slow 前进 1步，如果 fast==slow 说明有环路，此时将 fast 移动到链表开头，先判断两个指针是否相同（有在环路开始地方重合的可能性），让双指针每次都前进 1 步，最终相遇的地方就是环路的开始节点