1. 线性表的定义
   1. 线性表是一种逻辑结构，表示元素间一对一的相邻关系，顺序表和链表指的是存储结构，两者属于不同层面
2. 线性表的特点
   1. 1.表中元素的个数有限
   2. 2.表中元素具有逻辑上的顺序性，表中元素又先后次序
   3. 3.表中元素都是数据元素，每个元素都是单个元素
   4. 4.表中元素的数据类型都相同，每一个元素占有相同大小的存储空间
   5. 5.表中元素具有抽象性，仅仅讨论元素间的逻辑关系，不考虑表示的内容
3. 线性表的基本操作
4. 线性表的顺序表示（顺序表）
   1. 顺序表示的定义
      1. 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数
      2. 顺序表的特点
         1. 优
            1. 顺序表中任意一个元素都可以随机存取，所以线性表的存储结构是一种随机存取的存储结构。
         2. 缺
            1. 顺序表逻辑上相邻的元素物理上也相邻，插入和删除元素需要大量移动元素
            2. 顺序表的存储密度高，每个节点只存储数据元素
      3. 线性表中元素的位序从1 开始，数组下标从0 开始
   2. 顺序表的实现
      1. 顺序表的静态分配
      2. 顺序表的动态分配
      3. 一维数组可以静态分配，也可以动态分配。静态分配时，数组的大小和空间事先固定，一旦空间占满，再加入新的数据会溢出，程序会崩溃；动态分配时，可以临时开辟存储空间
      4. 动态分配并不是链式存储，属于顺序存储结构，物理结构不变，随机存取，只是分配的空间大小可以在运行时动态决定
      5. 动态分配的molloc函数必须free掉
   3. 顺序表的基本操作
      1. 插入
         1. 具有健壮性的
         2. 时间复杂度
         3. 插入位置之后 的元素都要后移
      2. 删除
         1. 删除位置之后的元素都要前移
         2. 时间复杂度
      3. 查找
         1. 按值查找
            1. 时间复杂度
         2. 按位查找
            1. 时间复杂度
         3. 结构体类型的比较
      4. 修改
5. 线性表的链式表示（链表）
   1. 单链表
      1. 单链表的定义
         1. 通过一组任意的存储单元来存储线性表中的数据元素
         2. 为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息之外，还存储一个指向其后继的指针
         3. data数据域 next指针域
         4. 查找某个特定的结点，需要从表头开始遍历，依次查找
      2. 优点：不要求大片的连续存储空间，改变容量方便
      3. 缺点：不可随机存取，要耗费一定的空间存放指针
      4. 头结点和头指针
         1. 头结点
            1. 在单链表第一个结点之前附加一个结点
            2. 头结点的数据域可以不设置任何信息
            3. 头结点的指针域指向线性表第一个元素结点
         2. 头指针和头结点的区别
            1. 头指针始终指向链表的第一个结点
            2. 头结点是带头结点的链表中的第一个结点，结点内通常不存储信息
         3. 引入头结点的优点
            1. 由于第一个数据结点的位置被存放在头结点的指针域中，在链表的第一个位置上的操作和在表上的其他位置的操作一致，无法进行特殊处理
            2. 无论链表是否为空，其头指针都是指向头结点的非空指针，因此空表和飞控标的处理也得到统一
         4. 带头结点的单链表
         5. 不带头结点的单链表
      5. 单链表的定义
         1. 头插法建立单链表
            1. 可以用于链表的重置
         2. 尾插法建立单链表
            1. 将新结点插入到当前列表的表尾，为此必须增加一个尾指针r，使其始终指向当前列表的尾结点
   2. 单链表的基本操作
      1. 插入
         1. 按序号查找结点，按位查找
            1. 在单链表中从第一个结点出发，顺指针next指针域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个指针域NULL
            2. 时间复杂度
            3. O(n)
            4. 带头结点的按位序插入
            5. 不带头结点的按位序插入
         2. 指定结点的后插操作
         3. 指定结点的前插操作
      2. 删除
         1. 按位序删除
         2. 指定结点的删除
            2. 有坑：指定结点是最后一个结点时，需要特殊处
            3. 封装的好处：小功能模块化，代码逻辑清晰
      3. 单链表的查找
         1. 按位查找
         2. 按值查找
         3. GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
         4. LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的
         5. 单链表不能随机访问，只能依次扫描
      4. 求表长度
   3. 双链表
      1. 初始化
      2. 插入
      3. 删除
      4. 遍历
   4. 循环链表
      1. 循环单链表
         1. 表尾结点的next指针指向头结点，从一个结点出发 可以找到其他任何一个结点
      2. 循环双链表
         1. 表头结点的prior指向表尾结点；表尾结点的next指向头结点
         2. 双链表的初始化
         3. 双链表的插入
         4. 双链表的删除
   5. 静态链表
      1. 静态链表：用数组的方式实现的链表
      2. 静态链表的定义
         1. 分配一整片连续的内存空间，各个结点集中安置
         2. 初始化静态链表：把 a[0] 的 next 设为 -1，把其他结点的 next 设为一个特殊值用来表示结点空闲，如 -2
         3. 查找：从头结点出发挨个往后遍历结点
         4. 插入位序为 i 的结点： ①找到一个空的结点，存入数据元素 ②从头结点出发找到位序为 i-1 的结点 ③修改新结点的 next ④修改 i-1 号结点的 next
         5. 删除某个结点： ①从头结点出发找到前驱结点 ②修改前驱结点的游标 ③被删除结点 next 设为 -2
      3. 优点：增、删 操作不需要大量移动元素 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
      4. 适用场景：①不支持指针的低级语言；②数据元素数 量固定不变的场景（如操作系统的文件分配表FAT）