408考研数据结构

根据书籍《大话数据结构》还有王道考研咸鱼学长网课总结，无论是希望夯实基础的自学者，还是备战考研的冲刺者，都能在这套“趣味教材+实战课程”的组合中，找到破解数据结构与算法难题的钥匙——正如书中那句掷地有声的结语：“最终的结果一定是，你对着别人很牛地说‘数据结构——就那么回事。’”

认识数据结构

• 认识数据
  • 数据
    • 描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
  • 数据对象
    • 是性质相同的数据元素的集合，是数据的子集。（eg：社交媒体）
  • 数据元素
    • 是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录，是数据对象的子集（eg：社交账号）
  • 数据项
    • —个数据元素可以由若干个数据项组成，是数据不可分割的最小单位（eg：账号内的：姓名、性别、年龄...）
  • 图形关系
• 数据结构
  • 是相互之间存在一种或多种特定关系的数据元素的集合，我们将这些关系称为数据结构（eg:特定门店的顾客排队关系信息）
  • 逻辑结构
    • 是指数据对象中数据元素之间的相互关系
    • 集合结构
      • 集合结构中的元素，除了同属一个元素集合之外，它们之间没有其他关系
        • 
    • 线性结构
      • 线性结构中的数据元素之间是一对一的关系
        • 
    • 树形结构
      • 树形结构中的数据元素之间存在 一种一对多的层次关系
        • 
    • 图状结构
      • 图状结构中的数据元素是多对多的关系
        • 
  • 物理结构
    • 是指数据的逻辑结构在计算机中的存储形式，是逻辑结构在计算机中的映射 在存储数据时，不仅要存储数据元素的值，而且要存储数据元素之间的关系
    • 顺序存储结构
      • 顺序存储结把数据存储在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
        • 
    • 链式存储结构
      • 把数据存放在任意的存储单元里，这组存储单元可以是连续的也可以不是连续的
        • 
    • 索引存储结构
      • 存储信息的同时还建立附加的索引表
        • 
    • 散列存储结构
      • 根据元素的关键字直接计算出元素的存储地址，又称哈希存储
  • 数据的运算
    • 施加在数据上的运算，包括运算的定义和实现
      • 运算的定义：针对逻辑结构，指出的运算功能
      • 运算的实现：针对物理结构，指出运算的具体操作步骤
  • 数据结构的三要素 讨论一个数据结构要关注的三个方面
• 数据类型
  • 定义
    • 数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都 有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。
    • 一个值的集合和定义在此集合上的一组操作的总称
  • 数据类型
    • 原子类型
      • 是不可以再分解的基本类型 （eg：int类型，bool类型）
    • 结构类型
      • 有若干个类型组合而成的，可以再分解。 （eg：struct类型）
  • 抽象数据类型
    • 一个数学模型及定义在该模型上的一组操作 (eg:游戏中控制人物前进后退等指令)
    • 通常是对数据的某种抽象，定义了数据的取值范围和结构形式，以及对数据的操作的集合

认识算法

• 定义
  • 是解决特定问题求解步骤的描述，它是指令的有序数列，并且每一条指令表示一个或多个操作。
• 算法特性
  • 输入输出
    • 算法具有零个或者多个输入，至少有一个或多个输出
  • 有穷性
    • 算法在执行有限步骤后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成。
  • 确定性
    • 算法的每一个步骤都具有确定的含义，不会有二义性
  • 可行性
    • 算法的每一步都必须是可行的，每一步都能通过执行有限次数完成
• 设计要求
  • 正确性
    • 算法至少有输入输出和加工处理无歧义性、能正确地反映问题的需求，能够得到问题的正确答案
  • 可读性
    • 便于阅读、理解和交流
  • 健壮性
    • 当输入数据不合法时、算法也能做出相应处理而不是产生异常或莫名其妙的结果
  • 时间效率高和存储量低
    • 算法要尽量满足时间效率高和存储量低的需求
• 算法效率计量
  • 效率计量方法
    • 事后计量法（不推荐）
      • 通过设计好的测试程序和数据，利用计算机计时器，对不同算法编制的程序运行时间进行比较，从而确定算法效率的高低
    • 事前分析估算方法
      • 在计算机程序编制前，依据统计方法对算法进行估算
      • 效率因素
        • 算法采用的策略和方法
        • 编程语言：编译产生的代码质量
        • 问题的输入规模
        • 机器性能：机器执行指令的速度
  • 时间复杂度
    • 定义
      • T(n)=O(f(n))
        • 全称：算法渐近时间复杂度 简称：时间复杂度 随着问题规模的增大，算法执行时间的增长率和f(n)的增长率相同
          • 函数的渐近增长
            • 定义
              • 给定两个函数f(n)和g(n)，如果存在一个整数N，使得所有的n>N,f(n)总是比g(n)大，我们说f(n)渐近增长快于g(n)
            • 判断方法
              • 判断一个算法的时间效率的时候，函数中的常数和其他次要项常常可以忽略，应该关注主要项（最高阶）阶数
        • n
          • 问题规模
        • O( )
          • 体现算法时间复杂度的记法(大O记法)
        • f(n)
          • 问题规模的某个函数
        • T(n)
          • 语句的总执行次数
    • 推导大O阶方法
      • 快速判断（代码）
        • 顺序执行的代码只会影响常数项，可以忽略
        • 只挑循环中的一个基本操作分析他的执行次数与n的关系
        • 如果有多层嵌套循环，只需关注最深层循环循环了几次
      • 公式判断（T(n)）
        • 用常数1取代运行时间中所有的加法常数
        • 在修改后的运行次数函数中，只保留最高阶项
        • 如果最高阶项存在，且系数不为1，去除这个项相乘的系数，得到最终结果
      • 常用技巧
        • 空间复杂度同样适用
        • 消耗时间大小排列
          • O(1)<O(logn)<O(n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)（常对幂指阶）
        • 加法规则
          • O(f(n))+O(g(n))=O(max(f(n),g(n)))
        • 乘法规则
          • O(f(n))×O(g(n))=O(f(n)×g(n))
    • 三种复杂度
      • 平均时间复杂度：考虑所有输入数据都等概率出现（期望运行时间）
      • 最坏时间复杂度：考虑所有输入数据“最坏情况”
      • 最好时间复杂度：考虑所有输入数据“最好情况”
      • 一般在没有特殊说明的情况下，都是指最坏时间复杂度。
    • 推导示例
      • O(1)
        • 常数阶
          • 没有最高项，所以O(n)
      • O(n)
        • 线性阶
          • 此循环体的代码需要执行n次
      • O(logn)
        • 对数阶
          • 设定循环次数为x，则得出公式2^x=n，即x=log₂n
      • O(n^2)
        • 平方阶
          • 嵌套循环，需要n*n次
      • 常见的时间复杂度
  • 空间复杂度
    • 概念
      • 算法的空间复杂度通过计算算法所需的存储空间实现
      • S(n)=O(f(n))
        • n
          • 问题规模
        • f(n)
          • 语句关于n所占存储空间的函数
      • 程序运行时需要哪些运算空间
        • 程序代码
          • 编译好放入内存，大小固定
        • 数据
          • 数组
            • int flag[n] (声明一个长度为n的数组，此时占用空间规模S(n))
            • int flag[n] [n] (长度为n*n的二维数组，此时占用空间规模S(n^2))
          • 局部变量i，参数c
    • 推导方法
      • 普通程序
        • 1. 找到空间大小与问题规模相关的变量
        • 2. 分析问题所占空间x与问题规模的关系x=f(n)
        • 3. x的数量级就是空间复杂度S(n)
      • 递归程序
        • 1. 找到递归调用的深度x与问题规模的关系x=f(n)
        • 2. x的数量级就是空间复杂度S(n)
        • 3. 注：有的算法各层函数所需存储空间不同，分析方法略有别
        • 递归内存开销原理
          • 
          • 栈帧的创建：每次递归调用 loveYou(n) 时，都会在内存中分配一个新的栈帧，用于存储当前调用的参数 n 和局部变量 a, b, c。
          • 内存开销：每个栈帧的大小是固定的，与问题规模 n 无关。但随着递归深度的增加，栈帧的数量会线性增长，导致内存开销增大。
          • 内存释放：当递归调用结束时，栈帧会被逐个释放，内存会被回收。

线性表

• 定义
  • 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列 其中n为表长，当n = 0时线性表是一个空表 若用L命名线性表，则其一般表示为L = (a1, a2, … , ai, ai+1, … , an)
  • 概念
    • ai是线性表中的“第i个”元素线性表中的位序
    • ai-1 是 ai 的直接前驱元素
    • ai+1 是 ai 的直接后继元素
    • a1是表头元素；an是表尾元素
    • 除第一个元素外，每个元素有且仅有一个直接前驱 除最后一个元素外，每个元素有且仅有一个直接后继
  • 抽象数据类型
    • 操作代码
      • InitList(*L)
        • 初始化操作，建立一个空的线性表L
      • ListEmpty(L)
        • 若线性表为空，返回true，否则返回false
      • ClearList(*L)
        • 将线性表清空
      • GetElem(L , i , *e)
        • 将线性表L中的第i个位置元素值返回给e
      • LocateElem(L, e)
        • 在线性表L中查找与给定值e相等的元素 查找成功，返回该元素在表中序号；否则，返回0
      • ListInsert(*L, i, e)
        • 在线性表L中的第i个位置插入新元素e
      • listDelete(*L, i, *e)
        • 删除线性表L中第i个位置元素，并用e返回其值
      • ListLength(L)
        • 返回线性表L的元素个数
    • 复杂案例举例
      • 实现两个线性表A和B并集（设La为集合A，Lb为集合B）
      • • 【*】：指针 通过传递指针，函数可以直接修改原始数据结构 如果不使用指针（即不使用星号），函数只能修改传入参数的副本，而不能修改原始数据结构。 【&】：获取变量内存地址 它表示传递的是变量 e 的地址，而不是 e 的值。 通常用于函数需要修改变量的值，或者需要通过指针来访问变量 【++i 】：前缀自增运算符 它首先将 i 的值增加1，然后返回 i 的新值。 这种写法通常用于需要新值的场景，比如在循环中使用 ++i 作为循环变量时。 【SqList】：自定义的数据结构类型 （Sequential List）顺序线性表的缩写 用于表示顺序线性表，包含一个数组和一个整数来存储元素和长度 【Elemtype】：类型标识符 它在定义数据结构时经常用作元素类型占位符。 在顺序线性表 SqList 的上下文中， ElemType 表示存储在数组中的元素的数据类型。
• 顺序存储结构（顺序表）
  • 定义
    • 线性表的顺序存储结构，指的是用一段地址连续的数据存储单元依次存储线性表中的数据元素
      • 
    • 实现方式
      • 静态分配
      • 动态分配
    • 属性
      • 1. 存储位置的起始位置
        • 数组data，他的存储位置就是存储空间的存储位置
      • 2. 线性表的最大存储容量
        • 数组长度MAXSIZE
      • 3. 线性表的当前长度
        • length
      • 线性表的顺序存储的结构代码
  • 基本操作
    • 插入操作
      • ListInsert(*L, i, e)
      • 思路
        • 
        • 1. 如果插入位置不合理，抛出异常
        • 2. 如果线性表长度大于或等于数组长度，抛出异常
        • 3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动—个位置
        • 4. 插入到元素填入位置i处
        • 5. 表长+1
      • 代码实现
        • 时间复杂度O(n)
    • 删除操作
      • listDelete(*L, i, *e)
      • 思路
        • 
        • 1. 如果删除位置不合理，抛出异常
        • 2. 取出删除元素
        • 3. 从删除元素位置遍历到最后一个元素位置，分别都向前移动一个位置
      • 代码实现
        • 时间复杂度O(n)
    • 查找操作
      • 按位查找 GetElem(L, i)
        • 思路
          • 存储地址
            • 每个存储单元都有自己的编号，这个编号称之为地址
            • 获取表L中第i个位置的元素值
            • 用数组下标就可以找到第i个元素data[i-1]
          • 随机存取结构
            • LOC(ai)=LOC(a1)+(i-1)*c
              • LOC
                • 存储位置的函数
              • c
                • 每个元素所占的存储单元个数
              • 图示
            • 用这个公式可随时计算线性表任意位置地址，存取时间恒定，即O(1)复杂度，称为随机存取结构
            • 根据起始地址加上元素的序号，可以很方便地访问任意一个元素
        • 代码实现
          • 时间复杂度O(1)
      • 按值查找 LocateElem(L, e)
        • 思路
          • 在元素表中查找第一个元素值等于e的元素并返回其位序
        • 代码实现
          • 时间复杂度O(n)
  • 优缺点
    • 时间复杂度分析
      • GetElem
        • O(1)
      • ListInsert(*L, i, e)
        • O(n)
      • listDelete(*L, i, *e)
        • O(n)
      • 线性表比较适合元素个数不太变化,而更多是存取数据的应用。
    • 优点
      • 存储密度大：无须为表示表中元素之间的逻辑关系而增加额外的存储空间
      • 可以快速地存取表中任一位置的元素
    • 缺点
      • 插入和删除操作需要移动大量元素
      • 当线性表长度变化较大时，难以确定存储空间的容量
      • 造成存储空间的“碎片”
• 链式存储结构（链表）
  • 定义
    • n个节点（ai的存储映像）链结成一个链表，即为线性表（a1，a2，……，an）的链式存储结构
      • 
    • 名称
      • 单链表
        • 此链表的每个节点中只包含一个指针域
      • 数据域
        • 存储数据元素信息的域
      • 指针域
        • 存储直接后继位置的域
        • 最后一个的指针指向空（NULL）
      • 节点
        • 这两部分信息组成数据元素【ai】的存储映像
        • 由存放数据的数据域和存放后继节点地址的指针域组成
      • 头指针
        • 
        • 链表中第一个节点的存储位置
        • ·头指针具有标志作用所以常用头指针冠以链表的名字 ·无论链表是否为空0头指针均不为空，头指针是链表的必要元素
      • 头节点
        • 
        • 在单链表的第个一节点前附设一个节点
        • ·为了操作的统一和方便而设立的，放在第一元素的节点之前 ·其数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息
• 单链表
  • 定义
    • 每个节点除了存放数据元素之外，还要存储指向下一个节点的指针
    • 代码描述
      • 链式存储代码
        • LinkList —— 强调这是个单链表 LNode —— 强调这是一个节点
      • 初始化代码
        • 带头节点
          • 代码详解【L = (LNode *) malloc(sizeof(LNode));】 使用 sizeof(LNode) 计算 LNode 结构体在内存中所占的字节数。 调用 malloc 函数，请求分配 sizeof(LNode) 字节的内存。 将 malloc 返回的 void* 类型的指针转换为 LNode* 类型的指针。 将转换后的指针赋值给 L，使 L 指向新分配的内存。
        • 无头节点
      • 空表
        • 
        • 若线性表是空表则头节点的指针域为空（NULL）
          • 
      • 实例
        • 假设p是指向第i个元素的指针
        • ai的数据域
          • p -> data
        • ai的指针域
          • p -> next
        • ai+1的数据
          • p-> next -> data
  • 基本操作
    • 插入
      • 按位序插入 ListInsert(&L,i,e)
        • 概念
          • 设在节点p后面插入元素s 首先：将p的后继节点（指针）改为s的后继节点（指针）， 然后：将p的后继节点（指针）改为指向s （顺序不能反，否则就是s自己指自己）
            •  表中插入  表头插入  表尾插入
          • 思路
            • 1. 声明—指针p指向链表头节点，初始化j从1开始
            • 2. 当j＜i时，就遍历链表,让P的指针向后移动,不断指向下—节点,j累加1
            • 3. 若走到最后链表为空，证明i不存在，否则生成一个空节点s
            • 4. 将元素e赋值给s->data
            • 5. 插入语句s->next = p ->next; p -> next = s
            • 6. 返回成功
        • 代码
          • 带头节点【时间复杂度O(n)】
          • 无头节点
            • 
      • 节点后插 InsertNextNode(LNode *p,e)
        • 概念
          • 指定节点 p 之后插入一个新节点 s，其中包含元素 e，并更新链表的链接
        • 代码
          • 时间复杂度O(1)
            • 
      • 节点前插 InsertPriorNode(Lnode *p,e)
        • 概念
          • 偷梁换柱：在p后面生成一个新的节点s，二者数值互换
        • 代码
          • 时间复杂度O(1)
            • 另一种写法
              • 区别 1. 新节点数据的来源 另外代码：新节点 s 的数据是通过交换 p 节点的数据得到的。这意味着新节点 s 的数据原本就在 p 节点中。 第一段代码：新节点 s 的数据是直接从函数参数 e 中获取的。这意味着可以在插入新节点时直接指定新节点的数据。 2. 数据交换的有无 另外代码：涉及到数据交换的操作。它使用一个临时变量 temp 来交换 p 节点和新节点 s 的数据。 第一段代码：没有涉及到数据交换的操作。新节点 s 的数据直接从 p 节点复制，然后 p 节点的数据被覆盖为 e。
    • 删除
      • 按位序删除 ListDelete(&L,i,&e)
        • 概念
          • 把p的后继节点改为p的后继节点的后继节点
            • 
        • 思路
          • 1. 声明一指针p指向链表头节点，初始化j从1开始，i为需要删除的元素
          • 2. 当i＜j时,就遍历链表,让P的指针向后移动,不断指向下一个节点,j累加1
          • 3. 遍历到尾为空，证明i不存在，否则成功
          • 4. 将p->next赋值给q，随后p->next = q->next;
          • 5. 将q节点中的数据赋值给e，并作为返回
        • 代码
          • 时间复杂度O(n)
            • 为什么在这里用【ElemType &e】？ 在这个特定的函数中，e 被用来存储被删除节点的数据，然后这个数据被返回给调用者。 如果不使用引用，你可能需要使用指针的指针（ElemType **e）或者返回一个结构体来包含被删除的数据，这会使代码更复杂。
      • 节点删除 DeleteNode(LNode *p)
        • 概念
          • 偷天换日：令q为p的后继节点，p的值换成q的，然后把q删掉
        • 注意
          • 指定节点是最后一个节点时，需要特殊处理！（易错点）
          • 单链表的局限性：不能向前检索，找不到最后一个的后继
        • 代码
          • 时间复杂度O(1)
    • 查找
      • 按位查找 GetElem(LinkList L, int i)
        • 思路
          • 1. 声明一个指针p指向链表第一个节点,初始化j从0开始
          • 2. 当j＜i时,就遍历链表,让p的指针向后移动,不断指向下一节点,j累加1
          • 3. 若到链表末尾p为空，则说明第j个节点不存在，反则成功，返回p的数据
        • 代码
          • 时间复杂度O(n)
            • 另一种写法
              • 区别 另一种写法：跳过头节点直接从第一个节点开始遍历，计数器也从1开始遍历
      • 按值查找 LocateElem(LinkList L,ElemType e)
        • 思路
          • 声明一个指针p指向头节点的后继节点
          • 遍历链表直到找到数据域等于e的节点，若到链表末尾p为空，则说明节点不存在
        • 代码
          • 时间复杂度O(n)
    • 整表创建
      • 头插法 List_HeadInsert(LinkList &L)
        • 
        • 思路
          • 1. 声明一指针p和计数器变量i
          • 2. 初始化空链表L
          • 3. 让L头节点的指针指向NULL，及建立一个带头节点的单链表
          • 4. 循环
            • 生成一个新节点赋值给p
            • 随机生成一个数字赋值给p的数据域p->data;
            • 将p插入到头节点与前一新节点之间
        • 代码
          • 时间复杂度O(n)
      • 尾插法 List_TailInsert(LinkList &L)
        • 
        • 思路
          • r->next = s
          • r=s
          • r->next = NULL
        • 代码
          • 时间复杂度O(n)
      • 整表删除 clearList(LinkList *L)
        • 思路
          • 1. 声明两个指针p&q
          • 2. 将p指向第一个元素
          • 3. 循环
            • 将q指向下一个元素
              • q在里面的意义：一个节点里面含有数据域和指针域，释放将不知道下一个数据域的地址，所以需要提前找到下一个节点【皇帝死之前总要说一下下一个皇帝是谁吧】
            • 将p释放
            • 将q的元素传递给p
        • 代码
  • 单链表与顺序存储结构优缺点
    • 对比项
      • 存储分配方式
        • 单链表
          • 任意存储单元存储线性表
        • 顺序存储结构
          • 需要连续的存储单依次存储线性表
      • 时间复杂度
        • 查找
          • 单链表：O(n)
          • 顺序存储：O(1)
        • 插入与删除
          • 单链表：O(1)
          • 顺序存储: O(n)
      • 空间性能
        • 单链表
          • 只要有可以存储的单元就可以存储
        • 顺序存储结构
          • 需要预分配存储空间,容易浪费或溢出
    • 总结
      • 单链表
        • 线性表中元素变化过大,或根本不知道有多大时,适用单链表
      • 顺序存储结构
        • 当需要频繁的查找需求,很少进行插入与删除操作时,适用顺序存储结构
• 双链表
  • 概念
    • 如果单链表要找上一个节点的位置需要的时间复杂度为：O(n)；所以加一个指针域指向前驱节点速度更快(拿空间换时间)
    • 代码
      • 结构代码
      • 初始化
      • 判断空表
  • 插入和删除
    • 插入
      • 概念
        • 跟单链表插入概念一样,但要注意顺序（如注释）: 1. s节点前驱=p节点 2. s节点后驱=p节点后驱 3. p->next前驱=s节点 4. p节点的后驱=s节点 【注意】2和4的顺序不能反！！！
          • 
      • 代码
        • • 排序依据: 第四步先行的话，第三步和第四步的结果就是自己指向自己
    • 删除
      • 概念
        • 跟单链表插入概念一样
      • 代码
        • 时间复杂度O(n)
          • 另一种写法（令删除节点为p）
            • 
• 循环列表
  • 循环单链表
    • 定义
      • 尾节点不再指向 NULL，而是指向头节点（或第一个节点） 从一个节点出发可以找到其他任何一个节点
        • 
    • 快速访问最后一个节点
      • 因为最后一个节点的指针指向头节点，何尝不用最后一个节点当作“头节点”
      • 尾指针：rear
        • 第一个节点（非头节点）：rear->next->next
    • 代码
      • 初始化代码
  • 循环双链表
    • 定义
      • 表头节点的 prior 指向表尾节点 表尾节点的 next 指向头节点
      • "互相抓腮"
    • 代码
      • 定义
        • 初始化
        • 判断空表
          • "真让人摸不着头脑"
      • 基本操作
        • 插入
        • 删除
  • 合并
    • 概念
      • 设定有两个循环列表 rearA & rearB
      • 第一个尾链接第二个头，第二个尾链接第一个头
      • rearA->next = rearB->next->next
      • rearB->next = rearA->next->next
    • 代码表示
• 静态链表
  • 定义
    • 用数组来描述的链表叫静态链表
    • 元素
      • data
        • 用来存储数据元素
      • cur(游标)
        • 相当于单链表的next指针
      • 备用链表
        • 未被使用的数组元素
    • 代码表示
      • 建立静态链表数组
        • 另一种写法
    • 首尾特殊处理
      • 
      • 第一个元素和最后一个元素进行特殊元素处理,不存储数据
      • 第一个元素(下标为0)的cur存储第一个备用链表的下标
      • 最后一个元素存放第一个插入元素的下标,算是头节点
      • 备用首,尾对头
      • 最后一个元素的cur为0
      • 代码表示
        • 初始化数组
  • 插入
    • 
    • 概念
      • 单链表实现内存申请：malloc()
      • 将所有未被使用或已删除的分量用游标链成一个备用链表，每当插入新分量可以从备用链表的第一个节点作为插入节点
    • 代码
      • 内存申请【仿malloc()】
        • 【取第一个元素值】：第一个元素下标存储的是备用链表的第一个元素 【if判定】：第一个下标元素下标不为0 = 备用链表至少有一个元素 【判定动作】：将第一个元素下标改为备用链表第一个元素的下一个元素(因为备用列表第一元素征用了，所以整个列表的第一个元素指向备用列表新的第一个元素)
      • 插入
        • 【k首先为最后元素的下标】：因为最后一个元素相当于头节点，所以后续循环就从头节点开始
  • 删除
    • 
    • 概念
      • 单链表实现内存释放：free()
      • 同线性存储链表的删除
    • 代码
      • 内存释放【仿free()】
      • 删除元素
        •  删除元素详解
  • 优缺点和其他表的异同
    • 静态链表和其他存储结构的异同
      • 线性存储结构
        • 相同点
          • 二者都会进行预存储的操作
        • 不同点
          • 线性存储结构的元素是按照顺序依次排列的, 静态链表两个元素通过"指针链接"
      • 单链表
        • 相同点
          • 都用指针进行连接
        • 不同点
          • 静态链表进行预存储操作
        • 延伸一下
          • 静态链表里面的节点是不是也可以这样子排列：不是一个挨着一个的，可能一个后面跟着几个备用链表然后再跟着其他的不是上一个节点指向的节点
    • 优缺点
      • 优点
        • 插入和删除只需要移动游标，相比于线性存储结构需要移动大量元素有极大优势
      • 缺点
        • 表长难以确定，相比于链式存储的随机读取有劣势
• 两种表的比较
  • 逻辑结构
    • 都属于线性表，属于线性结构
  • 存储结构
    • 顺序表
      • 优点：支持随机存储，存储密度高
      • 缺点：大片连续空间分配不方便，改容量不方便
    • 链表
      • 优点：离散的小空间存储方便，改变容量方便
      • 缺点：不可随机存取，存储密度低
  • 基本操作
    • 创
      • 顺序表
        • 需要分配大片连续空间 若分配空间过小，之后不方便拓展容量； 若分配容量过大，则浪费内存资源。
      • 链表
        • 只需要分配一个头节点（甚者可以只申请头指针），之后方便拓展
    • 销
      • 顺序表
        • 只需做：Length=0，系统会自动回收空间（静态分配）
      • 链表
        • 需要一次删除各个节点，需要手动用free函数，malloc和free成对出现
    • 增删
      • 顺序表
        • 【O(n)】插入/删除元素要将后续元素都前移/后移
        • 【若数据元素很大则移动的时间代价很高】
      • 链表
        • 【O(n)】插入/删除元素只需要更改指针
        • 【查找元素的时间代价更低】

栈

• 定义
  • 栈是限制存取点的线性结构：限定仅在一端进行插入和删除操作的线性表
    • 例子：网页的后退，软件的撤销键
  • LIFO结构
    • 栈为先进后出（Last In First Out）的线性表
    • 栈顶（Top）：允许插入删除的一端
      • 操作在表尾
    • 栈底（Bottom）：另一端
    • 空栈：没有任何数据元素的
    • 插入操作 => 进栈、压栈、入栈
    • 删除操作 => 出栈、弹栈
    • 图示
      • 
  • 作用
    • 栈的引用简化了程序设计问题，划分了不同关注层次，缩小了思考范围跟家聚焦问题核心
  • 栈的出栈序列分析
    • 卡特兰数
      • （设有n个不同元素进栈）
  • 抽象数据类型
    • 进出栈
      • 进栈：push
      • 出栈：pop
    • 伪代码
• 栈的顺序存储结构（顺序栈）
  • 概念
    • 顺序栈
      • 站的顺序存储相当于线性表的顺序存储的简化
    • top
      • 栈顶元素在数组的位置
    • StackSize
      • 存储栈的大小
      • 栈顶位置（top）必须小于（StackSize）
        • StackSize = 5 
        • 空栈
          • top = -1
          • StackSize = 0
        • 只有一个元素
          • top = 0
          • StackSize = 1
  • 结构管理
    • 结构代码
    • 初始化
      • • 另一种方式（top初值0）
    • 判断栈空
      • • 另一种方式（top初值0）
  • 基本操作
    • 进栈（push）
      • 
      • • 另一种方式（top初值0）
    • 出栈（pop）
      • • 另一种方式（top初值0）
    • 读栈顶操作
      • • 另一种方式（top初值0）
  • 两栈共享空间
    • 概念
      • 
      • 顺序栈的缺点：事先确定存储空间的大小
      • 两个同类型的栈，一个将近溢出一个还有空间，完全可以用—个数组来存储两个栈
    • 思路
      • 将一个栈底设置为数组的始端，另一个设置为末端，向中间靠拢
      • 满栈：top1+1 == top2
        • 只要俩指针不碰面就证明还可以往里面塞
    • 使用限制
      • 通常用于两个栈的需求有相反关系的时候（一进一出）
      • 两个栈是同类型的
    • 代码
      • 结构代码
      • 初始化代码
      • 进栈（push）
      • 出栈（pop）
• 栈的链式存储结构（链栈）
  • 思路
    • 栈顶 = 链表头部
      • 1. 栈顶需要指针（top）
      • 2. 单链表有头指针
      • 3. 已经有栈顶在头部了就不需要头节点了
  • 代码
    • 结构代码
    • 进栈
      • e=新元素；s=新节点；top=栈顶指针
        •  时间复杂度O(1) 【相当于链表头插法（不带头结点）】
    • 出栈
      • •  时间复杂度O(1) 【相当于链表头插法（不带头结点）】
    • 思考题：上面的是不带头节点的，你能不能写一个带头结点的，此时栈顶结点top指向哪里呢？
      • 数据结构定义
        • #include <stdio.h> #include <stdlib.h> // 定义链栈的节点结构 typedef struct StackNode { int data; // 数据域 struct StackNode* next; // 指针域，指向下一个节点 } StackNode; // 定义链栈结构 typedef struct { StackNode* top; // 栈顶指针，指向栈顶节点 } LinkStack;
      • 初始化
        • // 初始化链栈 int InitStack(LinkStack* S) { if (S == NULL) { return 0; // 参数无效 } S->top = (StackNode*)malloc(sizeof(StackNode)); // 分配头结点 if (S->top == NULL) { return 0; // 内存分配失败 } S->top->next = NULL; // 初始化时栈为空，头结点的next指针指向NULL return 1; // 初始化成功 }
      • 判断栈空
        • // 判断链栈是否为空 int StackEmpty(LinkStack S) { return S.top->next == NULL; // 如果头结点的next指针为NULL，则栈为空 }
      • 入栈
        • // 入栈操作 int Push(LinkStack* S, int e) { if (S == NULL) { return 0; // 参数无效 } StackNode* newNode = (StackNode*)malloc(sizeof(StackNode)); // 创建新节点 if (newNode == NULL) { return 0; // 内存分配失败 } newNode->data = e; // 将数据存储到新节点的数据域 newNode->next = S->top->next; // 新节点的next指针指向当前栈顶节点 S->top->next = newNode; // 更新头结点的next指针，使其指向新节点 return 1; // 入栈成功 }
      • 出栈
        • // 出栈操作 int Pop(LinkStack* S, int* e) { if (S == NULL || StackEmpty(*S)) { return 0; // 栈为空或参数无效 } StackNode* temp = S->top->next; // 临时指针指向栈顶节点 *e = temp->data; // 将栈顶节点的数据存储到参数e中 S->top->next = temp->next; // 更新头结点的next指针，跳过栈顶节点 free(temp); // 释放栈顶节点的内存 return 1; // 出栈成功 }
• 栈的应用——递归
  • 什么是递归
    • 递归就像是一个小朋友告诉另一个小朋友：“你去问问你后面的小朋友，我们还需要拿多少个玩具。”然后，每个小朋友都去问下一个小朋友，直到找到答案。
    • 简单来说，递归就是一个问题自己解决自己的方法，只要问题变得小一点或者简单一点，直到最后变得非常简单，可以直接解决。就像是一个接一个的问问题游戏，直到找到答案为止。
  • 递归的定义
    • 把直接调用自己或通过一系列的调用语句间接的调用自己的函数，称作递归函数
    • 每一个递归定义必须至少有一个条件，满足时递归不再进行，即不在引用自身而是返回值推出
  • 递归和栈的关系
    • 简单地说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。 当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳了。
    • 递归就像是你不断地从一堆杯子中拿杯子，而栈就像是你用来记住你拿过的所有杯子的地方。每次你拿一个杯子，你就把它放在栈上，当你不能再拿的时候，你就从栈上一个一个地把杯子放回去。这样，你就能记住你做了什么，也能回到你开始的地方。
    • 这就是递归和栈的联系：递归帮助你重复做同样的事情，而栈帮助你记住你做过的事情，这样你就能知道你什么时候停止，也能回到你开始的地方。
  • 递归例子：斐波那契数列
    • 例子
      • 裴老说如果兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出—对小兔子来。假设所有兔子都不死,那么—年以后可以繁殖多少对兔子呢?
      • 特征：前面相邻的两项之和，构成了后一项
        • 
    • 解法
      • 数学实现
      • 代码实现
        • 最简单办法
        • 递归办法
          • 代码含义【i == 0 ? 0 : 1;】 i == 0：这是条件，检查i是否等于0。 0：如果i等于0（条件为真），结果是0。 1：如果i不等于0（条件为假），结果是1。 三元运算符：是一种简洁的if-else语句，它允许你在一行内根据条件选择两个值中的一个。 一般形式：【condition ? value_if_true : value_if_false;】
          • 自己调用自己？听起来有些难以理解，不过你可以不要把—个递归函数中调用自己的函数看作是在调用自己,就当它是在调用另一个函数。只不过，这个函数和自己长得—样而已。
          • Fbi(i) 函数当 i = 5的执行过程图解
• 栈的应用——四则运算表达式求值
  • 后缀表达式（逆波兰）
    • 概念
      • 后缀表达式（逆波兰）：所有的符号都是在运算数字的后面
      • 中缀表达式（标准式）：所有的符号都是在两个数字的中间
      • 说人话就是A+B变为AB+ 进行运算的两个值（A、B）放一起 运算符放在两个值的后面
  • 中缀表达式转后缀表达式（逆波兰）
    • 逻辑步骤
      • 1. 遍历：从左到右遍历中缀表达式的每个符号
      • 2. 处理数字：直接输出
      • 3. 遇见算术表达式：
        • 推入栈中
          • 栈为空
          • 当前运算符优先级高于栈顶运算符
          • 栈顶运算符为左括号【 "(" 】
        • 从栈中弹出
          • 1. 弹出之前在栈中且比当前运算符优先级高于或等于栈顶运算符
          • 2. 直到遇到优先级更低的运算符或者为空停下
          • 3. 将当前运算符推入栈中
        • 优先级规则（从高到低）
          • 1. 括号：“(”和 “)”（左括号在栈内时优先级最低）
          • 2. 乘除/取模：*、/、%（优先级为2）
          • 3. 加减：+、-（优先级为1）
          • 4. 右结合运算符：如幂运算^（部分编程语言中需特殊处理）
      • 4. 遇见括号
        • 左括号（
          • 直接入栈
        • 右括号）
          • 弹出所有运算符直到遇见左括号”（“
    • 手动转换
      • A+B变为AB+，进行运算的两个值（A、B）放一起，运算符放在两个值的后面
      • 左右先：从左到右，遇见运算优先级相同的运算符，靠左边的优先转换
    • 例子
      • 中缀表达式
        • 9+(3-1)×3+10÷2
      • 后缀表达式
        • 9 3 1-3* + 10 2 / +
      • 计算过程
        • 1||| 读取 '9'（数字） ->添加到后缀表达式 栈: 空 后缀表达式: 9 中缀表达式: +(3-1)×3+10÷2
        • 2||| 读取 '+'（运算符） ->推入栈 栈: + 后缀表达式: 9 中缀表达式: (3-1)×3+10÷2
          • 
        • 3||| 读取 '('（左括号） ->推入栈 栈: + ( 后缀表达式: 9 中缀表达式: 3-1)×3+10÷2
        • 4||| 读取 '3'（数字） ->添加到后缀表达式 栈: + ( 后缀表达式: 9 3 中缀表达式: -1)×3+10÷2
          • 
        • 5||| 读取 '-'（运算符） ->栈顶为"(" ->推入栈 栈: + ( - 后缀表达式: 9 3 中缀表达式: 1)×3+10÷2
        • 6||| 读取 '1'（运算符） ->添加到后缀表达式 栈: + ( - 后缀表达式: 9 3 1 中缀表达式: )×3+10÷2
          • 
        • 7||| 读取 ')'（右括号） ->弹出栈顶运算符直到遇到 "(" (左括号) ->弹出 "-" 并添加到后缀表达式 栈: + 后缀表达式: 9 3 1 - 中缀表达式: ×3+10÷2
          • 
        • 8||| 读取 '×'（运算符） ->栈顶为 "+" , 优先级高于它 ->推入栈 栈: + × 后缀表达式: 9 3 1 - 中缀表达式: 3+10÷2
        • 9||| 读取 '3'（数字） ->添加到后缀表达式 栈: + × 后缀表达式: 9 3 1 - 3 中缀表达式: +10÷2
          • 
        • 10||| 读取 '+'（运算符） ->栈顶为 "×" ，优先级低于它 ->弹出 "×" 并添加到后缀表达式 ->新栈顶 "+" ，优先级相等 ->"+" 推入栈 栈: + 后缀表达式: 9 3 1 - 3 * + 中缀表达式: 10÷2
          • 
        • 11||| 读取 '10'（数字） ->添加到后缀表达式 栈: + 后缀表达式: 9 3 1 - 3 * + 10 中缀表达式: ÷2
        • 12||| 读取 '÷'（运算符） ->栈顶为 "+" ，优先级高于他 ->"÷" 推入栈 栈: ＋ ÷ 后缀表达式: 9 3 1 - 3 * + 10 中缀表达式: 2
        • 13||| 读取 '2'（数字） ->添加到后缀表达式 栈: ＋ ÷ 后缀表达式: 9 3 1 - 3 * + 10 2 中缀表达式:
          • 
        • 14||| 读取完毕 ->栈中所有符号依次弹出并添加到后缀表达式 栈: ＋ ÷ 后缀表达式: 9 3 1 - 3 * + 10 2 / + 中缀表达式:
          • 
  • 后缀（逆波兰）运算
    • 逻辑步骤
      • 1. 遍历元素
      • 2. 扫描到操作数压入栈，回到步骤1，否则到步骤3
      • 3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤1
    • 例子
      • 中缀表达式
        • 9+(3-1)×3+10÷2
      • 后缀表达式
        • 9 3 1-3* + 10 2 / +
      • 计算过程
        • 1||| 扫描 '9' -> 推入栈 栈: 9 - 当前表达式: 3 1-3* + 10 2 / +
        • 2||| 扫描 '3' - > 推入栈 栈: 9 3 - 当前表达式: 1-3* + 10 2 / +
        • 3||| 扫描 '1' -> 推入栈 栈: 9 3 1 - 当前表达式: -3* + 10 2 / +
        • 前三个数字进栈
          • 
        • 4||| 扫描 '-' -> 弹出 3 和 1 -> 执行 3 - 1 = 2 -> 推入结果 2 栈: 9 2 - 当前表达式: 3* + 10 2 / +
          • 
        • 5||| 扫描 '3' -> 推入栈 栈: 9 2 3 - 当前表达式: * + 10 2 / +
          • 
        • 6||| 扫描 '*' -> 弹出 2 和 3 -> 执行 2 * 3 = 6 -> 推入结果 6 栈: 9 6 - 当前表达式: + 10 2 / +
          • 
        • 7||| 扫描 '+' -> 弹出 9 和 6 -> 执行 9 + 6 = 15 -> 推入结果 5 栈: 15 - 当前表达式: 10 2 / +
          • 
        • 8||| 扫描 '10' -> 推入栈 栈: 15 10 - 当前表达式: 2 / +
        • 9||| 扫描 '2' -> 推入栈 栈: 15 10 2 - 当前表达式: / +
          • 
        • 10||| 扫描 '/' -> 弹出 10 和 2 -> 执行 10 / 2 = 5 -> 推入结果 5 栈: 15 5 - 当前表达式: +
          • 
        • 11||| 扫描 '+' -> 弹出 15和 5 -> 执行 15 + 5 = 20 -> 推入结果 20 栈: 20 - 当前表达式: NULL
          • 
        • 12||| 扫描结束 -> 弹出 20 栈: - 当前表达式: NULL
          • 
  • 中缀运算
    • 逻辑步骤
      • 1. 初始化两个栈，操作数栈和运算符栈
      • 2. 扫描到操作数：压入操作栈
      • 3. 到秒到运算符或界限符：按照中缀转后缀的逻辑进行
        • 期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈

队列

• 定义
  • 
  • 队列是操作受限的线性结构：只允许在一端进行插入操作，而在另一端进行删除操作的线性表
  • FIFO结构
    • 先进先出（First In First Out），允许插入的是队尾允许输出的是队头
  • 抽象数据类型
• 队列的顺序存储结构
  • 顺序存储队列
    • 概念
      • 
      • n个元素的队列，需要创建大于n的数组，排列在前n个位置，下标为0的是队头，最后一个元素是队尾。入队列往队尾插入，出队列每个元素都要向前移动（缺点所在）。
        •  入队列操作  出队列操作
      • 为了解决顺序存储队列的缺点所在，引入了队头（front）队尾（rear）两指针
      • front指向队头，rear指向队尾元素的下一个位置
      • 空队列
        • 
        • front = rear ：front和rear指向同一个元素置
      • 把队列这种循环存储结构成为循环队列
        • 为了解决假溢出现象：元素排入到最后一个位置冲突于rear指向队尾元素下一个位置 解决办法： rear可以指向空位置
    • 结构管理
      • 结构
      • 初始化
      • 判断空队
    • 基本操作
      • 入队
  • 循环队列
    • 更新逻辑
      • 1. 取模运算的核心作用
        • 当 Q.rear 到达数组末尾时（即索引 MaxSize-1），Q.rear+1 会超出数组物理边界。
        • 通过 % MaxSize 运算，将指针重置到数组起始位置（索引 0），实现循环队列的“环形”特性。
        • 不要害怕这个百分号和后面的一堆东西，他们只是队满的时候索引到0，其他情况等于Q.rear = Q.rear+1
      • 2. 存储结构与逻辑结构的映射
        • 物理存储：数组索引范围为 [0, MaxSize-1]
        • 逻辑循环：队列尾部指针在逻辑上视为从 1 到 MaxSize 的环形结构，与物理索引相差 1 位。
        • 取模运算通过数学映射，将逻辑上的“下一个位置”转换为物理数组的正确索引。
      • 3. 示例说明（设 MaxSize=10）
        • 初始 Q.rear=9（指向物理数组末尾） Q.rear+1=10 → 10 % 10 = 0 此时，指针跳转至数组头部，避免越界且实现空间复用。
      • 4. 性能优势
        • 相比条件判断（如 if(Q.rear==MaxSize) Q.rear=0 ），位运算实现的取模在硬件层面效率更高。
    • 入队
    • 出队
  • 判断队满
    • 方案1：牺牲一个存储单元
      • if 判断思路
        • 
        • rear取模的下一个位置是队头
        • 因为rear一直指向队尾的下一个位置，按此思路会牺牲一个存储单元
        • 如果不牺牲的话，判断标准为 Q.rear = Q.front 与判断队空冲突
      • 代码
      • 队列元素个数：(rear + MaxSize - front) % MaxSize
    • 方案2：添加计数器
      • if 判断思路
        • 计数器=MaxSize为队满
        • 创建队列之初添加一个计数器，出队-1，入队+1
        • 此方案相比于方案1不用牺牲一个存储单元
      • 代码
        • 结构代码：int count;
        • 初始化：count = 0;
        • 入队：count++;
        • 出队：count--;
        • 判断语句
      • 队列元素个数 = count
    • 方案3：添加状态
      • if 判断思路
        • 队头=队尾 且 状态为：插入成功状态
        • 创建队列之初添加一个状态，插入成功 = 1，删除成功 = 0
        • 此方案相比于方案1不用牺牲一个存储单元
      • 代码
        • 结构代码：int tag;
        • 初始化：tag = 0;
        • 入队：tag = 1;
        • 出队：tag = 0;
        • 判断语句
• 队列链式存储
  • 概念
    • 其实就是线性表的单链表，但只能尾进头出
    • 带头结点
      • 
      • 初始化时： front 和 rear 都指向头节点
    • 不带头结点
      • 初始化时：都指向NULL
  • 结构管理
    • 链队结构
    • 初始化(带头结点）
    • 判断空队 （带头结点）
    • 初始化（不带头结点）
    • 判断空队
  • 基本操作
    • 入队（带头结点）
    • 入队（不带头结点）
    • 出队（带头结点）
    • 出队（不带头结点）
• 双端队列
  • 概念
    • 只允许从连段插入、两端删除的线性表
  • 变种
    • 输出受限的双端队列（只允许从一端删除、两端插入的线性表）
      • 栈中合法的序列，双端队列中也一定合法
    • 输入受限的双端队列（只允许从一端插入、两端删除的线性表）
• 队列的应用
  • 树的层次遍历
  • 广度优先遍历
  • CPU资源分配

数组

• 数组的存储结构
  • 一维数组
    • 代码
    • 起始地址：LOC各数组元素大小相同，且物理上连续存放。
    • 各数组元素大小相同，且物理上连续存放。
    • 数组元素a[i] 的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)
  • 二维数组
    • 代码
      • ElemType b[2][4]
    • 存储地址
      • 因为存储地址是一维的，所以分为两种情况
      • 行优先
        • 先存储第一行的数组，后存储第二行的
        • b[i][j] 的存储地址 = LOC + (i*N + j) * sizeof(ElemType)
      • 列优先
        • 先存储第一列的数组，后存储第二列的
        • b[i][j] 的存储地址 = LOC + ( j*M+ i ) * sizeof(ElemType)
• 数组应用-矩阵存储
  • 普通矩阵
    •  描述矩阵元素时，行、列号通常从 1 开始； 而描述数组时通常下标从0开始 （具体看题目给的条件，注意审题！）
    • 直接用二维数组进行存储就可以
  • 对称矩阵压缩存储
    •  下三角区：i>j 上三角区：i<j 主对角线：i=j
    • 概念
      • 若 n 阶方阵中任意一个元素 ai,j都有 ai,j = aj,i则该矩阵为对称矩阵
      • 只存储主对角线+下三角区（或主对角线+上三角区）
    • 存储策略
      • 数组大小：(1+n)*n/2
      • 使用一维数组进行存储
      • 使用方案：实现一个映射函数：矩阵下标 → 一维数组下标
    • 下三角
      • 行优先存储
        • 
        • ai,j是第几个元素
          • 运算概念
            • 先算前 i-1 个完整的行：1+2+···+(i-1)=i*(i-1)/2
            • ai,j 在第 i 行的位置：j
          • i >= j
            • 逻辑位置：i * (i - 1) / 2 + j
            • 存储位置：i * (i - 1) / 2 + j - 1
          • i < j
            • 跟上面的逻辑一样，只需要j&i调换一下算术时候的位置
            • 逻辑位置：j * (j - 1) / 2 + i
            • 存储位置：j * (j - 1) / 2 + i - 1
      • 列优先存储
    • 上三角
      • 行优先存储
        •  除了主对角线和上三角区，其余的元素都相同
        • ai,j是第几个元素
          • 运算概念
            • 先算前 i-1 个完整的行：
            • ai,j 在第 i 行的位置：j - i + 1
          • i >= j
            • 逻辑位置：
            • 存储位置：
          • i < j
            • 跟上面的逻辑一样，只需要j&i调换一下算术时候的位置
      • 列优先存储
  • 三对角矩阵压缩存储
    • 
    • 概念
      • 三对角矩阵，又称带状矩阵：当 |i - j|>1 时，有 ai,j = 0 （1≤ i, j ≤ n)
      • 三对角：仅主对角线及其相邻上下对角线（|i-j|≤1）
    • 存储策略
      • 只存储带状部分
      • 行优先存储
        • k+1位置的元素在矩阵哪里
          • 运算概念
            • 前 i-1 行总和
  • 三角矩阵压缩存储
    • 
    • 概念
      • 下三角矩阵：除了主对角线和下三角区，其余的元素都相同
    • 存储策略
      • 将不重复元素所在三角区存入一维数组，在最后位置存储常量c
      • 行优先存储
        • ai,j是第几个元素
          • 运算概念
            • 总元素：n(n+1)/2
            • 前 i-1 行：同对称矩阵压缩存储
            • ai,j 在第 i 行的位置：同对称矩阵压缩存储
          • i<j
            • n(n+1)/2
  • 稀疏矩阵压缩存储
    • 
    • 概念
      • 非零元素远远少于矩阵元素的个数
    • 存储策略
      • 顺序存储
        • 三元组<行，列，值>
      • 链式存储
        • 十字链表法
          • • 向右域 right，指向第 i 行的第一个元素 向下域 down，指向第 j 列的第一个元素

串

• 定义
  • 由一个或多个字符组成的有限序列，又叫字符串
  • 术语
    • 空串：s='' 或 s=""
    • 空格串：s=" "
    • 主串：一般记为：s="a1 a2 ··· an"(n>=0)，s为名称，双（单）引号为串的值
• 串的存储结构
  • 串的顺序存储
    • 定义
      • 是用一组地址连续的存储单元来存储串中的字符序列的
      • 字符串的操作（插入、链接、替换）都有可能超过数组最大长度MAXSIZE 所以串值的存储空间可在程序执行过程中动态分配可得 计算机有一个自由存储区：“堆”可用C语言动态分配函数 malloc() & free()管理
    • 存储方案
      • 方案一（默认）
        • 概念
          • ch[0]废弃不用，最后存取length变量
      • 方案二
        • 概念
          • 最后存取length变量
        • 优缺点
          • 优点
            • 方便知道串长
          • 缺点
            • 逻辑位和存储位没有对齐
      • 方案三
        • 概念
          • 没有Length变量，以字符’\0’表示结尾（对应ASCII码的 0）
        • 优缺点
          • 优点
            • 存储量大
          • 缺点
            • 想知道串长需要遍历整个串
      • 方案四
        • 概念
          • ch[0]充当 Length
        • 优缺点
          • 优点
            • 逻辑位和存储位对其
          • 缺点
            • ch[0]只能存储8bit，也就是最大值只有255，遇见更长字串不能表达字长
    • 结构
      • 动态数组实现
      • 静态数组实现
    • 基本操作
      • 串的抽象数据类型
      • 求字串
        • 概念
          • 用 Sub 返回串 S 的第 pos 个字符起，长度为 len 的子串
        • 代码
      • 比较操作
        • 概念
          • 定义两个字符串“s = a1,a2 ... an”“t = b1,b2 ... bm"
          • 满足以下两个条件时s<t
            • n<m，且ai = bi (i = 1,2,3...n)
              • s = happ，t = happy
            • 存在某个k<=min(m,n), 使得ai=bi(i = 1,2...k-1), ak<bk
              • s = happen, t = happy
          • 算法方案
            • 若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0
        • 代码
          • 这段代码中的 return S.ch[i] - T.ch[i]; 是基于字符的 ASCII 码值进行比较的，而不是直接对字符串进行减法操作。
      • 定位操作
        • 概念
          • 若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0
        • 代码
  • 串的链式存储
    • 定义
      • 
      • 和线性表类似 由于串结构的特殊性：结构中的每个元素数据是—个字符 如果也简单使用链表存储：—个节点对应—个字符，就会存在空间浪费 解决办法：一个节点也可以放多个字符，最后—个节点未被占满时，可以用“#”或其他非串值字符补全
    • 结构
      • 低存储密度
      • 高存储密度
• 串的模式匹配
  • 朴素的模式匹配算法
    • 概念
      • 字符串模式匹配
        • 在主串中找到与模式相同的子串，并返回其位置
      • 主串
        • 被匹配的的串，在其中找到与模式串匹配的子串
      • 模式串
        • 需要匹配的串
        • 子串是主串的一部分，一定能匹配主串，但是模式串不一定
      • 算法理论
        • 将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。
    • 代码
      • 最坏时间复杂度O(mn)
    • 例子
      • 假设我们要从下面的主串S＝“goodgoogle”中找到T＝“google”这个子串的位置，进行如下操作↓
      • （1）主串S第—位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是 g。第一位匹配失败，如图所示，其中竖直连线表示相等
      • （2）主串S第二位开始,主串S首字母是o，要匹配的T首字母是g，匹配失败，如 图所示
      • （3）一直往后进行匹配直到匹配成功
      • （4）主串S第五位开始，S与T，6个字母全匹配，匹配成功，如图所示
      • 简单地说,就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。 对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成 为止
  • KMP模式匹配方法
    • 概念
      • 避免重复遍历的情况
      • 算法原理
        • 在需要查找字符串前，先对要童找的字符串做一个分析，这样可以大 大减少我们宣找的难度，提高查找的速度
    • next数组
      • 概念
        • 数组记录了最长公共前后缀
          • 前缀：包含第一个元素，且不包含最后一个元素的所有子串
          • 后缀：包含最后一个元素，且不包含第一个元素的所有子串
        • 算法
          • 当第 j 个字符匹配失败，由前 1 ~ j-1 个字符组成的串记为 S
          • next[j] = S 的最长相等前后缀长度+1
        • 和朴素算法的区别
          • 利用next数组进行匹配（主串指针不进行回溯）
      • 公式
        • • next[j]：表示在模式串 T 中，位置 j 处字符对应的 next 数组的值。 j：表示当前正在考虑的模式串 T 中的位置索引。 k：是一个辅助变量，用于遍历模式串 T 中从开始到位置 j 之前的所有字符。 P：表示模式串 T 中的字符。 1 < k < j：表示 k 的取值范围，从 2 到 j-1（不包括 j），因为我们要找的是 j 位置之前的前缀。 P_1...P_{k-1}：表示模式串 T 从第一个字符到第 k-1 个字符的子串，即前 k 个字符的前缀。 P_{j-k+1}...P_{j-1}：表示模式串 T 中从第 j-k+1 个字符到第 j-1 个字符的子串，即后缀，这个后缀的长度与前缀相同。
      • 代码
    • 代码
      • 最坏时间复杂度O(m+n)
  • KMP算法改进
    • 出现问题
      • 主串S=aaaabcde 字串T=aaaaax next数组=012345
      • 当i=5且j=5时发现不匹配，然后跳转4，在跳转3...最后跳到0
    • 改良代码(nextval数组)
    • nextveal 核心代码
    • 推导
      • j=2时，第二位字符“b”的next值为1，第一位值是a，二者不相等，所以维持原数值1
      • j=3时，第三位字符“a”的next值为1，第一位值时a，二者相同，所以nextval[3]=nextval[1]=0
      • 同理可得nextval[j]=0

树

• 树的定义
  • 基本概念
    • 树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况
    • 非空树
      • 
      • 任意一个非空树满足以下条件
        • 1. 有且仅有一个特定的成为根的节点
        • 2. 当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。
          • 
      • 特性
        • 
        • 1. 有且仅有一个根节点
        • 2. 叶子节点（终端节点）
          • 没有后继的节点
        • 3. 分支节点（非终端节点）
          • 有后继节点
        • 4. 除了根节点外，任何一个结点都有且仅有一个前驱
        • 5. 每个结点可以有0个或多个后继
      • 树的边
        • 指连接树中两个节点的线段
        • 对于一棵有 n 个节点的树，边的数量总是 n−1
    • 和线性结构对比
  • 基本术语
    • 节点间关系
      • 
      • 祖先节点
        • 某个节点的父节点、祖父节点等，沿着路径向上追溯的所有节点。
      • 子孙节点
        • 某个节点的子节点、孙节点等，沿着路径向下延伸的所有节点。
      • 双亲节点
        • 某个节点的直接上一级节点。
      • 孩子节点
        • 某个节点的直接下一级节点。
      • 兄弟节点
        • 同一个双亲的孩子间互称兄弟。
      • 堂兄弟节点
        • 具有相同祖先节点但不同父节点的节点。
    • 属性
      • 节点的层次（深度）
        • 从上往下数（默认从1开始）
      • 节点的高度
        • 从下往上数
      • 树的高度（深度）
        • 从共多少层
      • 树的路径长度
        • 树根到每个结点的路径长的总和
        • 根到每个结点的路径长度的最大值应是树的高度减 1。 注意与哈夫曼树的带权路径长度相区别。
      • 节点的度
        • 有几个孩子（分支）
      • 树的度
        • 树中每个节点度的最大值
      • 这棵树结点的度的最大值是结点D的度,所以 树的度也为3。
    • 有序无序
      • 有序树
        • 
        • 树中个节点的子树从左到右，是有次序的，不能互换
      • 无序树
        • 树中个节点的子树从左到右，是无次序的，可以互换
    • 森林
      • 森林是m（m≥0）棵互不相交的树的集合（eg：全国所有人的家谱）
  • 常考性质
    • 性质1
      • 节点数=总度数+1
        • 节点的度：节点有几个孩子（分支）
    • 性质2
      • 度为 m 的树 & m 叉树的区别
        • 度数为m的树
          • 
          • 树的度——各结点的度的最大值
          • 任意结点的度 ≤ m（最多m个孩子）
          • 至少有一个结点度 = m（有m个孩子）
          • 一定是非空树，至少有m+1个结点
        • m叉树
          • 
          • m叉树——每个结点最多只能有m个孩子的树
          • 任意结点的度 ≤ m（最多m个孩子）
          • 允许所有结点的度都 ＜ m
          • 可以是空树
            • 
    • 性质3
      • 度数为m的树的第i层最多节点个数：
        • 
        • m叉树的第i层最多节点个数：
    • 性质4
      • 高度为h的m叉树至多结点数：
        • 原理：等比数列求和公式
    • 性质5
      • 高度为为h、度为m的树至少有 h+m-1 个结点。
        • 
        • 高度为h的m叉树至少有 h 个结点。
          • 
    • 性质6
      • 具有n个结点的m叉树的最小高度为：
        • 符号 ⌈⋅⌉ 表示向上取整函数（ceiling function）。 这个函数的作用是将一个实数向上取整到最近的整数。 具体来说，对于任意实数 x，⌈x⌉ 是大于或等于 x 的最小整数。
        • 高度最小的情况——所有结点都有m个孩子
        • • 左边：前h-1层最多有几个结点
          • 右边：前h层最多有几个节点
        • 后续推理过程
• 树的存储结构
  • 双亲表示法
    • 
    • 概念
      • 用顺序存储
      • 用数组顺序存储各个节点
        • 数据元素
        • 指向双亲结点的“指针”
    • 代码
    • 存储森林
      • 
      • 每棵树的根节点双亲指针 = -1
    • 优缺点
      • 优点
        • 找双亲（父节点）很方便
        • 适用于：并查集
      • 缺点
        • 找孩子不方便，只能从头到尾遍历整个数组
  • 孩子表示法
    • 
    • 概念
      • 顺序存储+链式存储的集合
      • 把每个节点的孩子节点排列起来，用单链表进行存储
      • n个头指针组成一个线性表
    • 代码
    • 优缺点
      • 优点
        • 找孩子很方便
        • 适用于：服务流程树
      • 缺点
        • 找双亲（父节点）不方便，只能遍历每个链表
  • 孩子兄弟表示法
    • 
    • 概念
      • 树的结点的第一个孩子如果存在，就是唯一的
      • 树的右兄弟如果存在，也是唯一的
      • 设置两个指针
        • 指向第一个孩子的指针
        • 指向右兄弟的指针
    • 代码
    • 存储形态上看和二叉树很相似
    • 树、森林、二叉树的转换
      • 概念
        • 用孩子兄弟表示法进行转换
      • 树转二叉树
      • 森林转二叉树
      • 二叉树转树
      • 二叉树转森林
• 树和森林的遍历
  • 树的遍历
    • 先根遍历
      • 深度优先遍历
        • 若树非空，先访问根结点，再依次对每棵子树进行先根遍历
        • 树的先根遍历序列与这棵树相应二叉树的先序序列相同。
      • 代码
    • 后根遍历
      • 深度优先遍历
        • 若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
        • 树的后根遍历序列与这棵树相应二叉树的中序序列相同。
      • 代码
    • 层次遍历
      • 广度优先遍历
        • 用队列实现
        • ①若树非空，则根节点入队
        • ②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
        • ③重复②直到队列为空
  • 森林的遍历
    • 先序遍历
      • 遍历规则
        • 1. 访问森林中第一棵树的根结点。
        • 2. 先序遍历第一棵树中根结点的子树森林。
        • 3. 先序遍历除去第一棵树之后剩余的树构成的森林。
      • 效果
        • 遍历过程
          • 效果等同于依次对各个树进行先根遍历
        • 转换结果
          • 等同转换成的二叉树的先序遍历
    • 层序遍历
      • 遍历规则
        • 1. 中序遍历森林中第一棵树的根结点的子树森林。
        • 2. 访问第一棵树的根结点。
        • 3. 中序遍历除去第一棵树之后剩余的树构成的森林。
      • 效果
        • 遍历过程
          • 效果等同于依次对各个树进行后根遍历
        • 转换结果
          • 等同于转换成的二叉树的中序遍历
  • 回顾
• 哈夫曼树
  • 概念
    • 
    • 节点的权
      • 每一个节点的权重（某种特定的数值）
    • 节点的带权路径长度
      • 节点的权值 * 根节点到节点的路径长度
    • 树的带权路径长度（WPL）
      • 所有叶节点的带权路径长度之和
    • 哈夫曼树（最优二叉树）
      • 在含有给定的n个带权叶结点的二叉树中，WPL 最小的二叉树
      • 所有的节点的度只有0或者2
  • 构造哈夫曼树
    • 将权值最小的两个根节点合并，新的根节点的权值为这两个节点权值之和
    • 哈夫曼树不唯一，但是WPL之和一定是最小值
  • 哈夫曼编码
    • 将字符出现的频率作为权值，构造哈夫曼树，可得出哈夫曼编码，可用于数据压缩
    • 前缀编码
      • 没有一个编码是另一个编码的前缀
      • 例子：A（0）B（10）C（110）D（11）
        • ABC没有一个编码是其他编码的前缀
        • D是C编码的前缀
    • 固定长度编码
      • ASCII编码
      • 每一个字符都用等长度的二进制位表示
    • 可变长度编码
      • 哈夫曼编码
      • 允许对不同字符用不等长的二进制位表示
• 并查集
  • 三要素
    • 逻辑结构
      • 元素之间为集合关系
    • 存储结构
      • 
      • 用互不相交的树，表示多个“集合”
      • 用双亲表示法来进行存储
        • 方便查找双亲
        • 方便合并
    • 基本操作
      • 初始化
        • 将每一个节点都表示为孤立的根节点
      • Find
        • “查”操作，确定一个元素所属的集合（找到这个元素的跟节点）
        • 最坏时间复杂度O(n)
      • Union
        • “并”操作，将一个集合的根节点连接到了另一个根节点
        • 时间复杂度O(1)
  • 优化
    • Union 操作优化
      • 优化思路
        • 每一次合并的时候尽量不让树长高
        • 1. 用根节点的绝对值表示树的节点总数
          • 
        • 2. Union 操作让小树合并到大树
      • 最坏时间复杂度O(log₂n)
    • Find 操作优化
      • 优化思路
        • 
        • 1. 用find操作找到根节点
        • 2. 将查找路径上的所有节点都挂到跟节点下
      • 可使树的高度不超过O(a(n))
    • 优化比较

二叉树

• 定义
  • 二叉树是n（n≥0）个结点的有限集合
    • 1||| 或者为空二叉树，即n = 0。
    • 2||| 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。 左子树和右子树又分别是一棵二叉树。
  • 特点
    • 1||| 每个结点至多只有两棵子树
    • 2||| 左右子树不能颠倒（二叉树是有序树）
  • 区别
• 特殊二叉树
  • 满二叉树
    • 
    • 一棵高度为h，且含有的节点为
    • 特点
      • 1. 只有最后一层有叶子结点
      • 2. 不存在度为1的节点
      • 3. 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 ⌊i/2⌋ （如果有的话）
  • 完全二叉树
    • 
    • 当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树
    • 特点
      • 1. 只有最后两层才有叶子节点
      • 2. 最多只有一个度为1的节点（某节点有一个孩子，那肯定是左孩子）
      • 3. 按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 ⌊i/2⌋ （如果有的话）
      • 4. ⌊i ≤ n/2⌋ 为分支结点，⌊i > n/2⌋为叶子结点
  • 二叉排序树
    • 
    • 二叉排序树可用于元素的排序、搜索
    • 特点
      • 1. 左子树上所有结点的关键字均小于根结点的关键字。
      • 2. 右子树上所有结点的关键字均大于根结点的关键字。
      • 3. 左子树和右子树又各是一棵二叉排序树。
  • 平衡二叉树
    • 树上任一结点的左子树和右子树的深度之差不超过1
    • 特点
      • 平衡二叉树能有更高的搜索效率
      • 游戏技能树都点一遍的全能选手而非专精选手
• 常考性质
  • 二叉树
    • 性质1
      • 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则 n0 = n2 + 1（叶子结点比二分支结点多一个）
        • 原理：假设书中的总结点为n
          • ① n = n0 + n1 + n2
          • ② n = n1 + 2n2 + 1
            • 总度数=节点数 - 1（根节点无父节点）
            • 节点的度：节点有几个孩子（分支）
            • 边数也等于所有结点的度数之和
          • 联立得n0 = n2 + 1
    • 性质2
      • 二叉树第i层节点个数
      • m叉树第i层节点个数
      • i ≥ 1
    • 性质3
      • 高度为h的m叉树至多结点数：
        • 原理：等比数列求和公式
  • 满二叉树
    • 性质1
      • 含有的节点为
  • 完全二叉树
    • 性质1
      • 具有n个结点的完全二叉树的高度h为：
        • 符号 ⌈⋅⌉ 表示向上取整函数（ceiling function）。 这个函数的作用是将一个实数向上取整到最近的整数。 具体来说，对于任意实数 x，⌈x⌉ 是大于或等于 x 的最小整数。
        • 原理
          • 节点最少的情况
            • • 左边：高为h层最少拥有的节点数
              • 右边：高为h层最多拥有节点数
            • 后续推理过程
          • 节点最多的情况
            • • 左边：高为 h-1 的满二叉树节点数
              • 右边：h层节点全满
            • 后续推理过程
    • 性质2
      • 可以由的结点数 n 推出度为0、1和2的结点个数为n0、n1和n2
      • n1 = 0 或 1
      • n0 = n2 +1（n0 + n2 一定是奇数）
      • 结论
        • 若完全二叉树有2k个（偶数）个结点，则必有 n1=1， n0 = k， n2 = k-1
        • 若完全二叉树有2k-1个（奇数）个结点，则必有 n1=0， n0 = k， n2 = k-1
    • 性质3
      • 
      • 结点 i 的左孩子为 2i
      • 右孩子为 2i+1
      • 结点 i 的父节点为 ⌊i/2⌋ （如果有的话）
      • 按层序从 1 开始编号
• 存储结构
  • 顺序存储结构
    • 定义
      • 就是用一维数组存储二叉树中的结点，并且结点的存储位 置，也就是数组的下标要能体现结点之间的逻辑关系
        • 二叉树样例
        • 可以让第一个位置空缺，保证数组下标和结点编号一致
        • 二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来
        • 缺点：如果不是完全二叉树，会浪费很多存储单位
    • 基本操作
      • i的左孩子
        • 2i
      • i的右孩子
        • 2i+1
      • i的父节点
        • ⌊i/2⌋
      • i所在的层次
        • ⌈log2(n+1)⌉或⌊log2 n⌋+1
    • 判断
      • i是否有左孩子
        • 2i <= n
      • i是否有右孩子
        • 2i +1 <= n
      • i是叶子/分支节点
        • i>⌊n + 2⌋
      • 完全二叉树有n个节点
    • 结构
  • 链式存储结构
    • 定义
      • 利用指针将树中各节点连接起来
        • 数据域（data）：用于存储节点值的数据元素。
        • 左孩子指针（lchild）：指向该节点的左子节点的指针。
        • 右孩子指针（rchild）：指向该节点的右子节点的指针。
        • n个结点的二叉链表共有 n+1 个空链域(可用于构造线索二叉树)
          • 原理
            • 二叉链表每个节点都有2个指针指向2个孩子
            • 一共有 2n 个指针域
            • 构成一个二叉树只需要 n-1 个指针域
            • 所以空链域 = 2n - (n - 1)
          • 拓展
            • m叉链表的空链域 = (m - 1)n + 1
    • 结构
      • • 为了方便找父节点——三叉链表 可以在定义孩子节点之后在写一行： struct BiTNode *parent;
    • 初始化
• 二叉树的遍历
  • 先中后序遍历
    • 思路
      • 1. 左边还有没走的路，优先往左边走走到路的尽头（空结点）就往回走
      • 2. 走到路的尽头（空结点）就往回走
      • 3. 如果左边没路了，就往右边走
      • 4. 如果左、右都没路了，则往上面走
      • 每个节点都会被路过三次
    • 遍历算式表达树
      • 先序遍历可得前缀表达式
      • 中序遍历可得中缀表达式（不带括号）
      • 后序遍历可得后缀表达式
    • 先序遍历
      • 
      • 概念
        • 遍历顺序
          • 根节点→左子树→右子树
          • 第一次路过时访问结点
      • 代码
        • 操作过程
          • 1. 空树什么都不干
          • 2. 若二叉树非空
            • 1||| 访问根节点
            • 2||| 先序遍历左子树
            • 3||| 先序遍历右子树
        • 空间复杂度O(h)
    • 中序遍历
      • 
      • 概念
        • 遍历顺序
          • 左子树→根节点→右子树
          • 第二次路过时访问结点
      • 代码
        • 操作过程
          • 1. 空树什么都不干
          • 2. 若二叉树非空
            • 1||| 先序遍历左子树
            • 2||| 访问根节点
            • 3||| 先序遍历右子树
        • 空间复杂度O(h)
    • 后序遍历
      • 
      • 概念
        • 遍历顺序
          • 左子树→右子树→根节点
          • 第三次路过时访问结点
      • 代码
        • 操作过程
          • 1. 空树什么都不干
          • 2. 若二叉树非空
            • 1||| 先序遍历左子树
            • 2||| 先序遍历右子树
            • 3||| 访问根节点
        • 空间复杂度O(h)
  • 层序遍历
    • 
    • 算法思想
      • 1||| 先初始化一个辅助队列
      • 2||| 根节点先入队
      • 3||| 对头结点出队，将该节点左右孩子插入队尾（如果有的话）
      • 4||| 重复③直至队列为空
    • 代码实现
• 遍历序列构造二叉树
  • 概念
    • 若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种，不能唯一确定一棵二叉树
    • 前序、后序、层序序列的两两组合无法唯一确定一科二叉树
    • Key：找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点
  • 前序+中序遍历序列
    • 左子树的前序遍历序列
      • 根节点
        • 右子树的前序遍历序列
      • 中序
    • 根节点
      • 左子树的前序遍历序列
        • 右子树的前序遍历序列
      • 前序
  • 后序+中序遍历序列
    • 左子树的中序遍历序列
      • 右子树的中序遍历序列
        • 根节点
      • 后序
  • 层序+中序遍历序列
    • 根节点
      • 左子树的根
        • 右子树的跟
      • 层序
• 线索二叉树
  • 概念
    • 指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树
    • 线索链表
      • • 去掉【 ltag 和 rtag 】后是二叉链表
      • tag==0，表示指针指向孩子
      • tag==1，表示指针是“线索”
    • 线索
      • 指向前驱/后继的指针称为线索
      • 中序线索二叉树线索指向
        • 中序前驱/中序后继
      • 前序线索二叉树线索指向
        • 前序前驱/前序后继
      • 后序线索二叉树线索指向
        • 后序前驱/后序后继
  • 存储结构
    • 概念
      • n个结点的二叉树，有n+1个空链域！可用来记录前驱、后继的信息
      • 前驱线索
        • 左孩子指针充当
      • 后继线索
        • 右孩子指针充当
    • 代码
  • 类型
    • 中序线索二叉树
      • 
      • 按照“中序遍历”进行线索化
    • 先序线索二叉树
      • 
      • 按照“先序遍历”进行线索化
    • 后序线索二叉树
      • 
      • 按照“后序遍历”进行线索化
    • 手推步骤
      • 1. 确定线索二叉树的类型——先序、中序、后续
      • 2. 按照对应遍历规则，确定各个结点的访问顺序并编号
      • 3. 将 n+1 个空链域连上前驱后继
  • 线索化
    • 中序线索化
      • 
      • 土办法
      • 中序遍历
      • visit函数
      • 线索化代码
    • 先序线索化
      • 先序遍历
        • 避免了转圈圈问题
          • 第四次遍历
            • 此时D->ltag = 1，跳过左遍历
            • 遇见G
      • 转圈圈问题
        • 修改前的遍历代码
          • 空间复杂度O(h)
        • 运行BUG
          • 二叉树
            • A / \ B C / \ \ D E F \ G
          • 第一次遍历
            • 遇见A
            • pre = A
          • 第二次遍历
            • 遇见B
            • pre = B
          • 第三次遍历
            • 遇见D
            • 左子树为空，建立前驱线索
              • q->lchild=B
              • q->ltag=1
            • pre = D
          • 第四次遍历
            • 遇见 B（进入循环）
    • 后续线索化
      • 线索化代码
  • 找前驱/后继
    • 中序线索二叉树
      • 找后继
        • 原理
          • 核心原理
            • 中序遍历遵循 左子树 → 根节点 → 右子树 的递归模式
            • 对于任意节点p
              • 1. 存在右子树（p->rtag == 0）：后继节点是右子树的最左下节点。
              • 2. 无右子树（p->rtag == 1）：直接通过线索指针 rchild 获取后继。
            • 核心目标
              • 实现中序线索二叉树的完整遍历，而不仅仅是孤立地查找单个节点的前驱或后继。
              • 它通过串联每个节点的后继关系，最终形成完整的中序遍历序列。
          • 步骤
            • 1. 若 p->rtag==1，则 next = p->rchild
            • 2. 若 p->rtag==0
              • 按照中序遍历的性质可知：next = p的右子树中最左下结点
                • 中序遍历—— 左 根 右 左 根 (左 根 右) 左 根 ((左 根 右) 根 右)
        • 代码
      • 找前驱
        • 原理
          • 核心原理
            • 中序遍历遵循 左子树 → 根节点 → 右子树 的递归模式
            • 对于任意节点p
              • 1. 存在左子树（p->ltag == 0）：前驱节点是左子树的最右下节点。
              • 2. 无左子树（p->ltag == 1）：直接通过线索指针 lchild 获取前驱。
          • 步骤
            • 1. 若 p->ltag==1，则 pre = p->lchild
            • 2. 若 p->ltag==0
        • 代码
    • 先序线索二叉树
      • 找后继
        • 核心原理
          • 先序遍历遵循 根节点 → 左子树 → 右子树 的递归模式
          • 有无左孩子
            • 有
              • 先序后继为左孩子
            • 没有
              • 先序后记为右孩子
          • 对于任意节点p
            • 对于任意节点p
              • 1. 存在右子树（p->rtag == 0）：后继节点是右子树的最左下节点。
              • 2. 无右子树（p->rtag == 1）：直接通过线索指针 rchild 获取后继。
        • 步骤
          • 1. 若 p->rtag==1，则 next = p->rchild
          • 2. 若 p->rtag==0
            • 按照中序遍历的性质可知：next = p的右子树中最左下结点
              • 中序遍历—— 左 根 右 左 根 (左 根 右) 左 根 ((左 根 右) 根 右)
      • 找前驱
        • 原理
          • 先序遍历中：左右子树中的节点只可能是根的后继，不可能是前驱
        • 土办法
          • 1. 找到p的父节点且p是左孩子
            • 
            • 根 左 右 根 (根 左 右) 右
            • p的父节点即为其前驱
          • 2. 如果能找到 p 的父节点，且p是右孩子，其左兄弟为空
            • 
            • 根 右 根 (根 左 右)
            • p的父节点即为其前驱
          • 3. 如果能找到 p 的父节点，且p是右孩子，其左兄弟非空
            • 
            • 根 左 右
            • p的前驱为左兄弟子树中最后一个被先序遍历的结点
          • 4. 如果p是根节点，则p没有先序前驱
    • 后序线索二叉树
      • 找后继
        • 原理
          • 后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继
        • 土办法
          • 1. 如果能找到 p 的父节点，且p是右孩子
            • 
            • 左 右 根 左 (左 右 根) 根
            • p的父节点即为其后继
          • 2. 如果能找到 p 的父节点，且p是左孩子，其右兄弟为空
            • 
            • 左 根 根(左 右 根)
            • p的父节点即为其后继
          • 3. 如果能找到 p 的父节点，且p是左孩子，其右兄弟非空
            • 
            • 左 右 根
            • p的后继为 右兄弟子树中第一个被后序遍历的结点
          • 4. 如果p是根节点，则p没有先序前驱
      • 找前驱
        • 原理
          • 核心原理
            • 后序遍历遵循 左子树 → 右子树 → 根节点的递归模式
            • 对于任意节点p
              • 1. 存在左子树（p->ltag == 0）：前驱节点是左子树的最右下节点。
              • 2. 无左子树（p->ltag == 1）：直接通过线索指针 lchild 获取前驱。
          • 步骤
            • 1. 若 p->ltag==1，则 pre = p->lchild
            • 2. 若 p->ltag==0
    • 不能线索化的
      • 前不能前后不能后
        • 先序遍历不能找前驱
        • 后序遍历不能找后继

图

• 基本概念
  • 图的基本定义
    • 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的 通常表示为：G(V,E)。
      • G表示一个图
      • V是图G中顶点的集合
        • 线性表中我们把数据元素叫元素, 树中将数据元素叫结点, 在图中数据元素则称之为顶点(Vertex)
      • E是图G中边的集合
        • 任意两个顶点之间都可能有关系, 顶点之间的逻辑关系用边来表示， 边集可以是空的。
  • 各种图的定义
    • 方向
      • 无向图
        • 
        • 如果图中任意两个顶点之间的边都是无向边,则称该图为无向图 (undirected graphs)
        • 无向边
          • 若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge)，
          • 用无序偶对(Vi , Vj)来表示。
        • 无向完全图
          • 
          • 任意两个顶点都存在边
          • n个顶点的无向完全图的边的数量：
      • 有向图
        • 
        • 如果图中任意两个顶 点之间的边都是有向边,则称该图为有向图(directed graphs)。
        • 有向边
          • 若从顶点 Vi ，到 Vj 的边有方向,则称这条边为有向边,也称为弧(Arc)。
          • 用有序偶对<Vi，Vj>来表示，Vi 称为弧尾(Tail)，Vj称为弧头(Head)， （箭头指谁谁是头）。
        • 有向完全图
          • 
          • 果任意两个顶点之间都存在方向相反的两条弧
          • n个顶点的无向完全图的边的数量：
    • 连通类
      • 连通图
        • 
        • 在无向图中，任意两个顶点都是连通的
        • 连通
          • 无向图中，两个顶点有路径存在，称作两个顶点联通
        • 边数
          • 若G是连通图，则最少有 n-1 条边
          • 若G是非连通图，则最多可能有的边数为：
        • 连通分量
          •  图1有两个连通分量：图2和图3。 图4尽管是图1的子图，但不满足连通子图的极大顶点数，所以不是图1的连通分量
          • 无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）
        • 生成树
          •  图1的生成树有：图2、图3 n-1条边不一定是生成树，如图四
          • 包含图中全部顶点的一个极小连通子图
          • 若图中顶点数为n，则它的生成树含有 n-1 条边
        • 生成森林
          • 
          • 在非连通图中，连通分量的生成树构成了非连通图的生成森林。
      • 强连通图
        • 
        • 在有向图中，任何一对顶点都是强连通的
        • 强联通
          • 有向图中，两个顶点都有路径存在（一来一回）
        • 边数
          • 最少有 n 条边（形成回路）
        • 强连通分量
          •  图2是图1的强连通分量
          • 有向图中的极大强连通子图（子图必须强连通，且包含尽可能多的顶点和边）
    • 边分类
      • 稀疏图
        • 有很少的边的图
      • 稠密图
        • 与稀疏图相反
      • 没有绝对的界限，一般来说|E| < |V|log|V|时，可以将G视为稀疏图
      • 简单图
        • 1. 不存在顶点到其自身的边
        • 2. 不存在重复边
      • 多重图
        •  
        • 和简单图相反，有到自身的边，有重复出现的边
    • 带数值的
      • 边的权
        • 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
      • 带权图、网
        • 边上带有权值的图
      • 带权路径长度
        • 当图是带权图时，一条路径上所有边的权值之和
    • 特殊形态
      • 树
        • 不存在回路，且连通的无向图
        • n个顶点的树，必有n-1条边
        • 若 |E|>n-1，则一定有回路
      • 有向树
        • 一个顶点的入度为0、其余顶点的入度均为1的有向图
  • 顶点与顶点的关系
    • 路径
      • 顶点vp到顶点vq之间的一条路径是指顶点序列，vp, v1,v2, ... ,vi,vq
    • 回路
      • 第一个顶点和最后一个顶点相同的路径称为回路或环（那不就是公共交通里的环线）
    • 简单路径
      • 在路径序列中，顶点不重复出现的路径称为简单路径
    • 简单回路
      • 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
    • 路径长度
      • 路径上边的数目
    • 点到点的距离
      • 从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。
      • 若不存在路径，则记该距离为无穷
  • 顶点与边的关系
    • 对于无向图
      • 度
        • 是指依附于该顶点的边的条数，记为TD(v)
      • n个顶点与e条边的关系：
    • 对于有向图
      • 入度
        • 以顶点v为终点的有向边的数目（v是箭头的头，被指的）
      • 出度
        • 以顶点v为起点的有向边的数目（v是箭头的尾，指出的）
      • 度
        • 等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
      • n个顶点与e条边的关系：
• 图的存储
  • 邻接矩阵
    • 概念
      • 将顶点列成一个矩阵，
      • 用一个一维数组存储图中顶点的信息
      • 用一个二维数组存储图中边的信息(各顶点之间的邻接关系)
        • 有向图，无向图：1代表两个顶点之间有路径，0代表两个顶点之间没有路径 有向网，无向网：有数值代表有路径，0代表连接本身，♾️代表没有路径
      • 存储顶点之间邻接关系的二维数组称为邻接矩阵。
    • 表现形式
      • 无向图
        • 
        • 特点
          • 数值关于对角线对称
        • 度
          • 第i个结点的度 = 第i行（或第i列）的非零元素个数
      • 有向图
        • 
        • 度
          • 第i个结点的出度 = 第i行的非零元素个数
          • 第i个结点的入度 = 第i列的非零元素个数
          • 第i个结点的度 = 第i行、第i列的非零元素个数之和
      • 无向网、有向网
        • 
        • 有数值代表有路径，0代表连接本身，♾️代表没有路径
    • 代码
      • 有向图、无向图：
      • 有向网、无向网：
    • 存储方式
      • 空间复杂度：O(|V|^2) ——只和顶点数相关，和实际的边数无关
      • 适用于存储稠密图
      • 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）
    • 性质的用法
      • 设图 G 的邻接矩阵为A（矩阵元素为0/1），则 A^n 的元素 A^n[i][j] 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目
  • 邻接表
    • 概念
      • 顺序存储+链式存储（形同树中的孩子兄弟表示法）
        • 顶点表
          • 边表的头指针和顶点的数据信息采用顺序存储,称为顶点表,
        • 边表
          • 对图G中的每个顶点vi建立一个单链表
          • 第i个单链表中的结点表示依附于顶点v的边(对于有向图则是以顶点vi为尾的弧)
      • 代码
        • 建立一个数组用来存储各个顶点和第一个跟他连接的顶点
        • 建立链表用来存储这与这个定点连接的顶点
    • 无向图
      • 
      • 空间复杂度
        • 边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)
        • 存储的度是有重复的，存储数据冗余
      • 操作
        • 便于查找一个定点的度：遍历所有链表，总数除以二
    • 有向图
      • 
      • 空间复杂度
        • 存储不重复
        • 边结点的数量是|E|，整体空间复杂度为O(|V| + |E|)
      • 操作
        • 查找出度很方便：直接找定点所在的数组后面的链表就可以了
        • 查找入度不是很方便
          • 解决方案：逆邻接表
            • 
            • 建立一个链接弧头的链表表
        • 查找度：遍历所有链表，得出的总数就是度
  • 十字链表
    •  在有向网、无向网中：弧节点可能还有一个权值域（info）
    • 概念
      • 只用于存储有向图
    • 空间复杂度
      • O(|V|+|E|)
    • 操作
      • 如何找到指定顶点的所有出边？——顺着绿色指针线路找
      • 如何找到指定顶点的所有入边？——顺着橙色指针线路找
  • 邻接多重表
    • 
    • 概念
      • 只用于存储无向图
    • 空间复杂度
      • O(|V|+|E|)
    • 操作
      • 删除边、删除节点等操作很方便
  • 基本操作
    • Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)
      • 邻接矩阵
        • 直接定位行和列
        • 时间复杂度：O(1)
      • 邻接表
        • 遍历边表
        • 时间复杂度：O(1)~O(|V|)
    • Neighbors(G,x)：列出图G中与结点x邻接的边。
      • 邻接矩阵
        • 遍历相对应的行
        • 时间复杂度：O(1)
      • 邻接表
        • 遍历边表
        • 时间复杂度
          • 无向图：O(1)~O(|V|)
          • 出边：O(1)~O(|V|)
          • 入边：O(|E|)
    • InsertVertex(G,x)：在图G中插入顶点x。
      • 邻接矩阵
        • 在数组后面多加一行在多加一列
        • 时间复杂度：O(1)
      • 邻接表
        • 在数组后面多加一个存储单位就可以了
        • 时间复杂度：O(1)
    • DeleteVertex(G,x)：从图G中删除顶点x。
      • 邻接矩阵
        • 在原本的结构设置一个布尔函数用来判断表这一行或列是不是空的
        • 顶点对应的邻接矩阵的行和列里面的所有数值全部变为0
        • 时间复杂度：O(|V|)
      • 邻接表
        • 在原本的结构设置一个布尔函数用来判断顶点表这一行是不是空的
        • 将顶点所在的数组后面跟的链表全部删除
        • 时间复杂度
          • 删出边：O(1)~O(|V|)
          • 删入边：O(|E|)
          • 无向图：O(1)~O(|E|)
    • AddEdge(G,x,y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
      • 邻接矩阵
        • 直接在矩阵的那个坐标进行赋值
        • 时间复杂度：O(1)
      • 邻接表
        • 在边表中头插或者尾插一个节点
        • 时间复杂度：O(1)
    • RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
      • 邻接矩阵
        • 直接在矩阵的那个坐标进行赋值
        • 时间复杂度：O(1)
      • 邻接表
        • 在相对应的边表遍历并删除
        • 时间复杂度：O(1)~O(|V|)
    • FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
      • 邻接矩阵
        • 遍历矩阵的行或者列
        • 时间复杂度：O(1)~O(|V|)
      • 邻接表
        • 直接找边表的第一个节点就可以了
        • 时间复杂度：O(1)
    • NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
      • 邻接矩阵
        • 同上
      • 邻接表
        • 同上
    • Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。
      • 邻接矩阵
        • 直接定位坐标
        • 时间复杂度：O(1)
      • 邻接表
        • 遍历边表找到权值
        • 时间复杂度：O(1)~O(|V|)
    • Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。
      • 邻接矩阵
        • 同上
      • 邻接表
        • 同上
• 图的遍历
  • BFS
    • 概念
      • 思路
        • 建立一个辅助队列
        • 建立找到顶点相邻的边的函数
        • 建立一个数组 visited 防止重复遍历
      • 代码
      • 进阶
        • 非联通问题
          • 考虑多重连通分量的连通图
          • 遍历防止重复数组，遍历到未被遍历的顶点再采用BFS
        • 代码
      • 特点
        • 邻接表
          • 邻接表的边表里面的先后顺序是可以进行调换的，所以BFS结果不是固定的
        • 邻接矩阵
          • 邻接矩阵是固定的，所以BFS的结果是固定的
    • 复杂度
      • 时间复杂度
        • 邻接表
          • 要先遍历整个顶点
          • 寻找边的时候只用便利一下边的表
          • |V|+|E|
        • 邻接矩阵
          • 遍历整个顶点
          • 寻找边的时候还要便利一整行，也就是还要遍历整个顶点
          • |V|^2|
      • 空间复杂度
        • O(|V|)——来自辅助队列
    • BFS生成树
      • BFS生成森林
        • BFS遍历非连通图
      • 将BFS遍历后确定的树
      • 邻接表存储方式不唯一生成树不同，邻接矩阵的生成树固定
  • DFS
    • 概念
      • 思路
        • 建立一个递归工作栈
        • 建立找到顶点相邻的边的函数
        • 建立一个数组 visited 防止重复遍历
      • 代码
      • 进阶
        • 非联通问题
          • 考虑多重连通分量的连通图
          • 遍历防止重复数组，遍历到未被遍历的顶点再采用BFS
        • 代码
      • 特点
        • 邻接表
          • 邻接表的边表里面的先后顺序是可以进行调换的，所以BFS结果不是固定的
        • 邻接矩阵
          • 邻接矩阵是固定的，所以BFS的结果是固定的
    • 复杂度
      • 时间复杂度
        • 邻接表
          • 要先遍历整个顶点
          • 寻找边的时候只用便利一下边的表
          • |V|+|E|
        • 邻接矩阵
          • 遍历整个顶点
          • 寻找边的时候还要便利一整行，也就是还要遍历整个顶点
          • |V|^2|
      • 空间复杂度
        • O(|V|)——来自递归工作栈
    • DFS生成树
      • DFS生成森林
        • DFS遍历非连通图
      • 将DFS遍历后确定的树
      • 邻接表存储方式不唯一生成树不同，邻接矩阵的生成树固定
  • 图的遍历和连通性的关系
    • 无向图
      • 取决于连通分量，连通图只需要调用一次DFS/BFS函数
    • 有向图
      • 取决于顶点和其他顶点有没有路径
      • 强连通图，任意一个顶点开始只需要调用一次 DFS/BFS 函数
  • 最小生成树
    • 概念
      • 将带权无向图简化成为一个生成树且带权路径最小
      • 设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树
    • 性质
      • 若图G存在权值相同的边，生成树可能不唯一；当权值互不相等，最小生成树唯一
      • 生成树不唯一但是权值之和唯一
      • 最小生成树边数 = 顶点数-1
    • 算法
      • Prim
        • 概念
          • 从某⼀个顶点开始构建生成树；
          • 每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
        • 复杂度
          • 时间复杂度：|V^2|
          • 实现原理
            • 循环遍历所有个结点，找到lowCost最低的，且还没加⼊树的顶点
            • is join[ ]数组
              • 标记各节点是否已加⼊树
            • low Cost[ ]数组
              • 各节点加⼊树的最低代价
          • 适用于边稠密图
      • Kruskal
        • 概念
          • 每次选择⼀条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
        • 复杂度
          • O(elog2e)
          • 实现原理
            • 列出三列表：权值、入度顶点、出度顶点；将各条边按权值排序
            • 遍历每条边的两个顶点是否连通（是否属于同⼀个集合）
            • 共执⾏ e 轮，每轮判断两个顶点是否属于同⼀集合，需要 O(log2e)
          • 适用于边稀疏图
  • 最短路径问题
    • 单源最短路径问题
      • BFS
        • 概念
          • 生成两个数组
            • d[ ]：用来记录源顶点到该经典的路径
            • Path[]：用来记录该顶点的前驱
          • 进行BFS算法
            • 找到下一个路径顶点，在原顶点路径数值基础上+1
            • 找到下一个路径顶点，在该顶点Path数组填上前驱
        • 代码
        • 适用范围
          • 无权图
      • Dijkstra
        • 概念
          • 生成三个数组
            • final[ ]：记录每个顶点是否找到最短路径
            • dist[ ]：记录目前每个顶点的最短路径长度
            • path[ ]：记录目前每个顶点的前驱顶点
          • 进行算法
            • 在数字中找到最短路径长度，并将该顶点标记为找到，更新最短路径
            • 循环遍历所有结点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。
            • 检查所有邻接⾃ Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息
          • 不适用于权值为负的带权图
          • 适用范围
            • 适用于带权图、不适用权值为负的图
        • 时间复杂度
          • V^2
          • 代码原理
            • 初始: 若从V0开始,令final[0]=ture;dist[0]=0; path[0] =- 1。 其余顶点final[k]=false;dist[k]=arcs[0][k]; path[k]=(arcs[0][k] == ∞) ?- 1:0
            • n-1轮处理： 循环遍历所有顶点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。并检查所有邻接⾃Vi 的顶点， 对于邻接⾃Vi 的顶点 Vj ，若 final[j]==false 且 dist[i]+arcs[i][j] < dist[j]，则令 dist[j]=dist[i]+arcs[i][j]; path[j]=i。（注：arcs[i][j]表示Vi 到Vj 的弧的权值）
    • 每对顶点间最短路径问题
      • Floyd
        • 概念
          • 生成两个矩阵
            • A(-1) ：记录目前来看各顶点间的最短路径长度
            • path(-1)：记录两个顶点之间的中转点
          • 进行算法
            • 对于n个顶点的图G，求任意⼀对顶点 Vi —> Vj 之间的最短路径可分为如下⼏个阶段：
            • #初始：不允许在其他顶点中转，最短路径是？
            • #n-1：若允许在 V0、V1、V2 …… Vn-1 中转，最短路径是？
            • 判断标准
          • 代码
          • 适用范围
            • 适用于带权图、权值为负的图，不适用于权值为负的回路图
        • 复杂度
          • 时间复杂度：n^3
          • 空间复杂度：n^2
  • 有向无环图的表示
    • 
    • 概念
      • 若⼀个有向图中不存在环，则称为有向⽆环图，
      • DAG（Directed Acyclic Graph）
    • 做题技巧
      • Step 1：把各个操作数不重复地排成⼀排
      • Step 2：标出各个运算符的⽣效顺序（先后顺序有点出⼊⽆所谓）
      • Step 3：按顺序加⼊运算符，注意“分层”
      • Step 4：从底向上逐层检查同层的运算符是否可以合体
  • 拓扑排序
    • AOV网
      • 概念
        • Activity On Vertex NetWork，⽤顶点表示活动的⽹
        • 一定是一个 DAG 图
      • 拓扑排序概念
        • 是一个有向无环图组成的序列
        • 序列满足的条件
          • 1. 每一个顶点出现且只出现一次
          • 2. 若顶点A在序列中排在顶点B的前⾯，则在图中不存在从顶点B到顶点A的路径。
        • 另一种解释
          • 是对有向⽆环图的顶点的⼀种排序
          • 若存在⼀条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后⾯。
          • 每个AOV⽹都有⼀个或多个拓扑排序序列。
        • 找到做事的先后顺序
    • 拓扑排序实现
      • 概念
        • 两个数组一个栈/队列
          • indegree[ ]：当前每个顶点的入度
          • print[ ]：记录拓扑节点序列
          • S：用于暂存存入拓扑节点数列
        • 思路
          • ① 从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。
          • ② 从⽹中删除该顶点和所有以它为起点的有向边。
          • ③ 重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。
          • 算法实现
            • 1. 找到存储入度数组里面入度为0的顶点，压入栈中
            • 2. 将以压入栈中的顶点为前驱的顶点删除入度数值
            • 3. 将栈里的顶点进行弹出
            • 4. 返回第一步
      • 代码
        • 初始化
        • 主程序
      • 时间复杂度
        • 邻接表
          • O(|V|+|E|)
        • 邻接矩阵
          • O(|V|^2)
    • 逆拓扑排序的实现
      • 概念
        • 跟拓扑排序实现差不多，只需要把入度改为出度（后继为0）就可以了
      • 代码
      • 各种图的应用
        • 邻接表：不推荐，因为需要遍历整个表才能找到所有以当前顶点为出度为0的
        • 邻接矩阵
        • 逆邻接表
    • 用DFS进行实现
      • 概念
        • 在顶点退栈前调用输出函数
      • 思考：如果存在回路，则不存在逆拓扑排序序列，如何判断回路？
      • 代码
      • 用代码实现拓扑结构
    • 性质
      • 拓扑排序、逆拓扑排序序列不可能唯一
      • 如果如中有环，不可能有拓扑排序、逆拓扑排序序列
  • 关键路径
    • AOE网
      • 概念
        • 以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络
      • 性质
        • ① 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
        • ② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。另外，有些活动是可以并⾏进⾏的
      • 术语
        • 源点
          • 仅有一个入度为0的顶点，代表整个工程的开始
        • 汇点
          • 仅有一个出度为0的顶点，代表整个工程的结束
        • 关键路径
          • 具有最大路径⻓度的路径
          • 完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个⼯程的完成时间就会延⻓
        • 关键活动
          • 关键路径上的活动
        • 事件vk的最早发生时间
          • 决定了所有从vk开始的活动能够开⼯的最早时间
        • 活动ai的最早开始时间
          • 指该活动弧的起点所表⽰的事件的最早发⽣时间
        • 最迟发生时间
          • 它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间。
        • 最迟开始时间
          • 它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。
    • 关键路径步骤
      • ① 求所有事件的最早发⽣时间 ve( )
        • ve(源点) = 0
        • ve(k) = Max{ve(j) + Weight(vj, vk)},vj为vk 的任意前驱
      • ② 求所有事件的最迟发⽣时间 vl( )
        • vl(汇点) = ve(汇点)
        • vl(k) = Min{vl(j) - Weight(vk, vj)} , vj为vk的任意后继
      • ③ 求所有活动的最早发⽣时间 e( )
        • 若边<vk, vj>表⽰活动ai，则有e(i) = ve(k)
      • ④ 求所有活动的最迟发⽣时间 l( )
        • 若边<vk, vj>表⽰活动ai，则有e(i) = ve(k)
      • ⑤ 求所有活动的时间余量 d( )
        • d(i)=0的活动就是关键活动, 由关键活动可得关键路径
        • d(i) = l(i) - e(i)
    • 关键活动、关键路径特性
      • 若关键活动耗时增加，则整个⼯程的⼯期将增⻓
      • 缩短关键活动的时间，可以缩短整个⼯程的⼯期
      • 当缩短到⼀定程度时，关键活动可能会变成非关键活动
      • 可能有多条关键路径，只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的

查找

• 定义
  • 术语
    • 查找
      • 寻找符合条件的数据元素（记录）
    • 查找表
      • 同一类型数据元素（记录）组成
      • 静态查找表
        • 只查找
      • 动态查找表
        • 增删改查
    • 关键字
      • 唯一标识该数据项的值
  • 评价指标
    • 平均查找长度ASL
      • 公式：
      • Pi
        • 是第 i 个元素被查找的概率。
      • Ci
        • 是查找第 i 个元素成功时所需要进行的比较次数
    • 查找成功ASL
    • 查找失败ASL
• 顺序查找
  • 算法思想
    • 按照顺序从头查到脚
    • 适用于顺序表、链表，表中元素有序无序都OK
  • 基本算法
    • 普通算法
    • 哨兵算法
      • 将需要查找的算法放到第0个位置，相比于上面的算法免去了判断是否越界
  • 改进算法
    • 如果序列有序
      • 思想
        • 当前关键字大于（或小于）目标关键字时，查找失败
        • 优点：查找失败时ASL更少
      • 查找判定树
        • 
        • 成功结点的关键字对比次数=结点所在层数
        • 失败结点的关键字对比次数=其父节点所在层数
    • 按照出现概率进行计算
      • 将概率大的放到前面
      • 优点查找成功时ASL更少
  • 时间复杂度
    • O(n)
• 二分查找
  • 算法思想
    • 在 [low, high] 之间找目标关键字， 每次检查 mid=(low+ high)/2
    • 根据 mid所指元素与目标关键字的大小调整 low或 high，不断缩小 low 和 high的范围
    • 若 low> high则查找失败
    • 适用范围：有序的顺序表！！！！！！！
      • 因为顺序表有随机存取的特性！！！！链表的话你还要在顺序读一遍，费时间
  • 算法实现
    • 代码：
  • 判定树
    •  如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等 如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素
    • 构造
      • 核心公式：
      • 由 mid所指元素将原有元素分割到左右子树中
      • 右子树结点数 - 左子树结点树 = 0 或 1
    • 特性
      • 折半查找的判定树是平衡的二叉排序树，一定是一颗二叉搜索树 （左<中<右）
      • 折半查找判定树，只有最下面一层是不满的
      • 若查找表有n个关键字，则失败结点有n+1个
      • 树高
        • 不包含失败节点
        • 计算方法同完全二叉树
  • ASL
    • 查找成功 = 查找失败 = ⌈log₂(n + 1)⌉
  • 时间复杂度
• 分块查找
  • 算法思想
    • 又称“索引顺序查找”，数据分块存储，块内无序、块间有序
    • 索引表记录每个分块的最大关键字、分块的区间
    • 先查索引表（顺序或折半）、再对分快内进行顺序查找
  • ASL
    • ASL = Li（查索引表的平均查找长度） + Ls（查分块的平均查找长度）
    • 设 n 个记录，均分为 b 块，每块 s 个记录
      • 顺序查找索引表
        • 将长度为 n 的查找表均匀地分为 b 块，每块有 s 个记录，在等概率情况下
      • 折半查找索引表
  • 易错点
    • 对索引表进行折半查表时，若索引表中不包含目标关键字，则折半查找最终在 low > high , 要在low所指分块中查找
• 二叉排序树 BST
  • 定义
    • 又称为：二叉查找树BST
    • 左子树节点值 < 根节点值 <右子树节点值
    • 进行中序遍历可以得到一个递增的有序序列
  • 查找操作
    • 非递归
      • 最坏空间复杂度O（1）
    • 递归
      • 最坏空间复杂度O(h)
  • 插入操作
    • 插入顺序不同，树的形状也会不同
    • 递归
      • 最坏空间复杂度O(h)
    • 非递归
      • 自己尝试一下
  • 删除操作
    • 叶结点
      • 直接删除，不会破坏二叉排序树的性质
    • 只有一棵左子树或右子树
      • 让子树成为z父结点的子树，替代z的位置
    • 有左、右两棵子树
      •  
      • 则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
      • 用后继节点顶替，删除后继节点
      • 用前驱结点顶替，删除前驱节点
      • 前驱：左子树最右下的节点
      • 后继：右子树最左上的节点
  • 查找效率分析
    • 查找长度
      • 在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
      • 若树高h，找到最下层的一个结点需要对比 h 次
      • 最好情况：n个结点的二叉树最小高度为⌊log_2 n⌋ + 1。平均查找长度= O(log_2 n)
      • 最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)
    • ASL
      • 查找成功
      • 查找失败
• 平衡二叉树 AVL
  • 定义
    • 简称平衡树（AVL）
      • 树上任一结点的左子树和右子树的高度之差不超过1
    • 平衡因子
      • 结点的平衡因子 = 左子树高 - 右子树高。
      • 平衡二叉树结点的平衡因子的值只可能是−1、0或1
  • 插入操作
    • 从插入点往回找到第一个不平衡结点，调整以该结点为根的子树
    • 查找路径上的所有结点都有可能受到影响
    • 每一次进行调整的对象都是最小不平衡子树
  • 调整不平衡
    • LL
      • 
      • 在A的左孩子的左子树中插入导致不平衡
      • 右旋
        • 将A的左孩子B向右上旋转代替A成为根结点
        • 将A结点向右下旋转成为B的右子树的根结点
        • 而B的原右子树则作为A结点的左子树
      • 代码思路
        • 
        • 实现 f 向右下旋转， p 向右上旋转：其中 f 是爹，p 为左孩子，gf 为 f 他爹
        • ① f->lchild = p->rchild;
        • ② p->rchild = f;
        • ③ gf->lchild/rchild = p
    • RR
      • 
      • 在A的右孩子的右子树中插入导致不平衡
      • 左旋
        • 将A的右孩子B向左上旋转代替A成为根结点
        • 将A结点向左下旋转成为B的左子树的根结点
        • 而B的原左子树则作为A结点的右子树
      • 代码思路
        • 
        • 实现 f 向左下旋转， p 向左上旋转：其中 f是爹，p为右孩子，gf为f他爹
        • ① f->rchild = p->lchild;
        • ② p->lchild = f;
        • ③ gf->lchild/rchild = p;
    • LR
      • 
      • 在A的左孩子的右子树中插入导致不平衡
      • 先左后右双旋转
        • 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置
        • 然后再把该C结点向右上旋转提升到A结点的位置
    • RL
      • 
      • 在A的右孩子的左子树中插入导致不平衡
      • 先右后左双旋转
        • 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置
        • 然后再把该C结点向左上旋转提升到A结点的位置
  • 查找效率分析
    • 若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O(h)
    • 考点：高为h的平衡二叉树最少有几个结点————递推求解
    • 平衡二叉树最大深度为 O(log_2 n)，平均查找长度 / 查找的时间复杂度为 O(log_2 n)
  • 删除操作
    • 步骤
      • ①删除结点（方法同“二叉排序树”）
        • 若删除的结点是叶子，直接删
        • 若删除的结点只有一个子树，用子树顶替删除位置
        • 若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除
      • ②一路向北找到最小不平衡子树，找不到就完结撒花
      • ③找最小不平衡子树下，“个头”最高的儿子、孙子
        • 
      • ④根据孙子的位置，调整平衡（LL/RR/LR/RL）
        • • 孙子在LL：儿子右单旋
        • • 孙子在RR：儿子左单旋
        • • 孙子在LR：孙子先左旋，再右旋
        • • 孙子在RL：孙子先右旋，再左旋
      • ⑤如果不平衡向上传导，继续②
        • 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）
    • 时间复杂度
      • O(log2n)
• 红黑树 RBT
  • 定义
    • 比较
      • AVL
        • 插入/删除 很容易破坏“平衡”特性，需要频繁调整树的形态。 如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行 LL/RR/LR/RL 调整
        • 适用于以查为主、很少插入/删除的场景
      • RBT
        • 插入/删除 很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成
        • 适用于频繁插入、删除的场景，实用性更强
    • 要求
      • 红黑树是二叉排序树
        • 左子树结点值 ≤ 根结点值 ≤ 右子树结点值
      • ①每个结点或是红色，或是黑色的
      • ②根节点是黑色的
      • ③叶结点（外部结点、NULL结点、失败结点）均是黑色的
      • ④不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
      • ⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
      • 左根右，根叶黑 不红红，黑路同
    • 性质
      • 性质1：从根节点到叶结点的最长路径不大于最短路径的2倍
      • 性质2：有n个内部节点的红黑树高度 h ≤ 2log_2 (n + 1)
    • 黑高bh
      • 从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数
      • 内部节点最多的情况
        • h 层黑节点，每一层黑结点下面都铺满一层红结点。共2h层的满树形态
      • 若根节点黑高为h，内部结点数（关键字）最多有 2^{2h} -1 个
    • 查找操作时间复杂度
      • O(log_2 n)
      • 查找效率与AVL树同等数量级
  • 插入
    • 先查找，确定插入位置（原理同二叉排序树），插入新节点
    • 新节点是根
      • 染为黑色
    • 新节点是非根
      • 染为红色
    • 若插入新节点后依然满足红黑树定义，则插入结束
    • 若插入新结点后不满足红黑树定义，需要看新节点叔叔的脸色
      • 黑叔
        • • LL型：右单旋，父换爷+换色
        • • RR型：左单旋，父换爷+换色
        • • LR型：左、右双旋，儿换爷+换色
        • • RL型：右、左双旋，儿换爷+换色
      • 红叔
        • • 叔父爷染色，爷变为新结点
  • 删除
    • 时间复杂度
      • O(log_2 n)
    • 删除节点的处理方式和“二叉排序树的删除”一样
    • 删除结点后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满足“红黑树特性”。
• B 树
  • 概念
    • 
    • 又称为多路平衡查找树
    • 阶
      • B树中所被允许的孩子个数最大值，通常用 m 表示
    • 叶子节点
      • 失败节点
      • 关键字总数 = 叶节点数 - 1
    • 特性
      • 1. 个数
        • 根节点
          • 子树数∈[2, m]
          • 关键字数∈[1, m-1]
        • 其他结点
          • 子树数∈[⌈m/2⌉ , m]
          • 关键字数∈[ ⌈m/2⌉-1, m-1]
      • 2. 对任⼀结点，其所有子树⾼度都相同
      • 3. 关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2<….
        • (类⽐⼆叉查找树 左<中<右)
      • 4. 所有的叶结点都出现在同⼀层次上，并且不带信息
        • （可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）
    • 结构
      • 非叶节点：
      • Ki（i = 1, 2,…, n）
        • 结点的关键字，且满⾜K1 < K2 <…< Kn
      • Pi（i = 0, 1,…, n）
        • 指向子树根结点的指针
        • Pi-1所指子树中所有结点的关键字均小于Ki
        • Pi所指子树中所有结点的关键字均大于Ki
        • n（⌈m/2⌉- 1 ≤ n≤m - 1）为结点中关键字的个数
    • 高度
      • 最大高度
        • 分叉最小
          • 根节点两个分叉
          • 其他节点有 ⌈m/2⌉ 个分叉
      • 最小高度
        • 分差最多
          • 根节点 m 个分叉
          • 其他节点 m 个分叉
  • 操作
    • 插入
      • 通过“查找”确定插入位置（一定是在终端节点）
      • 插入关键字超出上限
        • 则从中间位置（ ⌈m/2⌉ ）将其中的关键字分为两部分
          • 左部分包含的关键字放在原结点中
          • 右部分包含的关键字放到新结点中
        • 中间位置（ ⌈m/2⌉ ）的结点插⼊原结点的⽗结点
    • 删除
      • 终端节点
        • 直接删除关键字（注意是否个数低于下限 ⌈m/2⌉-1 ）
      • 非终端节点
        • ⽤直接前驱或直接后继来替代被删除的关键字
          • 直接前驱：关键字左侧指针最右下元素
          • 直接后继：关键字右侧指针最左下元素
        • 结点删除前的关键字个数低于下限
          • 兄弟够借
            • 与此结点右（或左）兄弟结点的关键字个数还很宽裕
            • 则需要调整该结点、右（或左）兄弟结点及其双亲结点（⽗子换位法）
          • 兄弟不够借
            • 与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉ − 1
            • 则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进⾏合并
• B+树
  • 概念
    • 
    • 满足条件
      • 1. 每个分⽀结点最多有m棵子树（孩子结点）。
      • 2. 非叶根结点⾄少有两棵子树，其他每个分⽀结点⾄少有 ⌈m/2⌉ 棵子树。
        • 
      • 3. 结点的子树个数与关键字个数相等。
      • 4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。（支持顺序查找）
      • 5. 所有分⽀结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
    • 叶子节点
      • 最底层存储关键字的
      • 关键字数 = 分支数
  • 查找
    • 顺序
      • 根据指针进行顺序查找
    • 多路查找
      • 一层一层进行比较
      • 无论查找成功与否，最终一定都要走到最下面一层节点
  • 对比
• 散列表
  • 概念
    • 散列表
      • 又称哈希表，可以根据数据元素的关键字计算出它在散列表中存储的地址
    • 散列函数
      • 建立了“关键字”->“存储地址”的映射关系
    • 同义词
      • 若不同的关键字通过散列函数映射到了同一个存储地址，则称他们为“同义词”
    • 冲突（碰撞）
      • 在散列表中插入一个数据元素时，若插入的位置已经存储了其他元素
  • 构造
    • 除留余数法
      • 散列地址
        • 其中 p 通常为不大于散列表表长的最大质数
      • 使用场景
        • 较为通用，只要关键字是整数就可以
    • 直接定址法
      • 散列地址
        • 其中，a 和 b 都是常数
      • 使用场景
        • 关键字分布基本连续
        • （存储一班学生的学号，a = 1 ，b = 第一个学生的学号）
    • 数字分析法
      • 选取码分布均匀的若干位作为散列地址
      • 使用场景
        • 关键字集合已知，且关键字的某几个数码位分布均匀
        • （通讯公司存储电话号码使用尾号作为地址）
    • 平方取中法
      • 散列地址
        • 计算关键字的平方，取中间几位作为散列地址
      • 使用场景
        • 关键字的每位取值都不够均匀
        • 汽车型号按照每个零件型号进行组合的情况
  • 拉链法
    • 概念
      • 处理散列表冲突的时候，把所有同义词存储到一个链表中
    • 插入
      • 1. 根据散列函数计算新元素的散列地址
      • 2. 将新元素插入散列地址对应的链表（默认头插法，也可用尾插法）
      • 优化：可以将链表内的元素顺序排列，略微提高查找效率
    • 查找操作
      • 1. 根据散列函数计算目标元素的散列地址
      • 2. 顺序查找散列地址对应的链表，直到查找成功或者查找失败
      • 再分析查找长度时，通常只统计“关键字的对比次数”，而“链表空指针的对比次数”不计入查找长度
    • 删除操作
      • 1. 根据散列函数计算目标元素的散列地址
      • 2. 顺序查找散列地址对应的链表，若查找成功，将目标元素从链表中删除
  • 开放定址法
    • 基本原理
      • 当初始散列地址发生冲突时，根据“探测序列”di 探测下一个地址
    • 元素的操作
      • 插入
        • 1. 根据散列函数算出初始散列地址
        • 2. 发生冲突，“探测”下一个地址
        • 3. 找到空闲地址，即可插入元素
      • 查找
        • 1. 根据散列函数算出初始散列地址
        • 2. 对比关键字，不匹配就“探测”下一个地址
        • 3. 最终找到关键字匹配（成功）/ 探测到空位置（失败）
      • 删除
        • 按照“查找操作”的规划找到目标元素
        • 若查找成功，把目标元素“逻辑删除”，不能进行物理删除
    • 常用的探测序列
      • 线性探测法
        • 覆盖率：经过m-1次冲突，一定能探测到列表的所有单元
      • 平方探测法
        • 覆盖率：一般来说，探测序列至少能覆盖到散列表的一半—单元。
        • 优化：若能保证表长 m 是一个可以表示成4X+3的素数，则可以探测到散列表的所有单元
      • 双散列法
        • 覆盖率：若能保证hash2(key)的值和表长m互质，则经过m-1次冲突，一定能探测到散列表的所有单元
      • 伪随机法
        • 覆盖率：只要伪随机序列设计合理，就能探测到全部单元
  • 性能分析（线性查找法）
    • 计算散列表的ASL
      • 成功
        • • n：散列表中已存在的元素个数
          • Ci：成功查找第 i 元素所需的比较次数
      • 失败
        • • r：散列函数取值的个数【H(key) = key % p 里面的 p 】
          • 特别注意：散列函数取值的个数、列表长度可能不相同
    • 装填因子
      • 反应了一个散列表满的程度
      • 装填因子越大，越容易发生冲突。从而导致插入、查找效率降低，ASL增大
    • 聚集（堆积现象）
      • 在处理冲突的过程中，几个初始散列地址不同的元素争夺同一个后继散列地址的现象称作“聚集”（或称作“堆积”）
      • 现象会影响查找效率，导致ASL提升
      • 采用线性探测法处理冲突更容易导致“聚集（堆积）现象”，用其他方法处理冲突可以将元素“打散”，从而减少“聚集（堆积）现象”

排序

• 概念
  • 排序（Sort），就是重新排列表中的元素，使表中的元素满⾜按关键字有序的过程。
  • 评价指标
    • 稳定性
      • 关键字相同的元素经过排序后相对顺序是否会改变
    • 时间复杂度、空间复杂度
  • 分类
    • 内部排序
      • 数据都在内存中
    • 外部排序
      • 数据太多，无法全部放入内存
• 插入排序
  • 算法思想
    • 每次将一个待排序的记录按其关键字大小插入到前面已排好的序列中
  • 直接插入排序
    • 顺序查找到应插入的位置，适用于顺序表、链表
    • 常规：
    • 带哨兵：
  • 折半插入排序
    • 折半查找到插入的位置，仅适用于顺序表
    • 代码：
    • 注意
      • 一直到 low>high 时才停止折半查找
      • 当 mid 所指元素等于当前元素时，应该继续令 low=mid+1 ，以保证“稳定性”
      • 最终应将当前元素插入到 low 所指位置（即 high+1）
  • 性能
    • 空间复杂度
      • O(1)
    • 时间复杂度
      • 最好：原本有序O(n)
      • 最坏：原本逆序O(n^2)
      • 平均：O(n^2)
    • 稳定性
      • 稳定
  • 希尔排序
    • 
    • 概念
      • 先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。
    • 代码
    • 性能
      • 空间复杂度：O(1)
      • 时间复杂度：未知，但优于直接插入排序
      • 稳定性：不稳定
      • 适用性：仅可用于顺序表（因为需要使用到随机存取的性质）
• 交换排序
  • 冒泡排序
    • 算法原理
      • 从后往前（回从前完后）两两比较元素值，两个元素值若为逆序，则交换他们，知道序列比较完。这样的过程成为“一趟”冒泡排序。最多只需 n-1 趟排序。
      • 每一趟排序都可以是一个元素的移动到最终位置，已经确定最终位置的元素在之后的处理中无需再对比
      • 如果一趟排序过程中未发生“交换”，则算法可提前结束
    • 代码
      • • 每次交换都需要移动元素三次
    • 性能
      • 空间复杂度：O(1)
      • 时间复杂度
        • 最好（有序）：O(n)
        • 最差（逆序）：O(n^2)
        • 平均：O(n^2)
    • 稳定性
      • 稳定
    • 适用性
      • 顺序表、链表都可以
  • 快速排序
    • 算法思想
      • 在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]
      • 使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。
      • 然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
      • 算法表现主要取决于递归深度，若每次“划分”越均匀，则递归深度越低。“划分”越不均匀，递归深度越深
      • 注：408原题中说，对所有尚未确定最终位置的所有元素进⾏⼀遍处理称为“⼀趟”排序，因此⼀次“划分”≠⼀趟排序
        • ⼀次划分可以确定⼀个元素的最终位置
        • ⼀趟排序也许可以确定多个元素的最终位置
    • 代码：
    • 性能
      • 空间复杂度
        • 最好：O(log n)
        • 最坏：O(n)
      • 时间复杂度
        • 最好（每次划分很均匀）：O(n log n)
        • 最坏（原本正序或逆序）：O(n)
      • 稳定性
        • 不稳定
• 选择排序
  • 简单选择排序
    • 算法原理
      • 每一趟在待排序元素中选取关键字最小的元素加入有序子序列
      • 必须进行总共 n-1 趟处理
    • 代码：
    • 性能
      • 空间复杂度
        • O(1)
      • 时间复杂度
        • O(n^2)
      • 稳定性
        • 不稳定
      • 适用性
        • 顺序表、链表都可以
  • 堆排序
    • 堆
      • 顺序存储的完全二叉树
        • 节点 i 的左孩子是 2i；右孩子是 2i+1；父节点是 i/2
        • 编号 ≤ n/2 的结点都是分支节点
      • 大根堆（根 ≥ 左、右）；小根堆（根≤左、右）
    • 算法思想（以大根堆为例）
      • 建堆
        • 编号 ≤ n/2 的所有节点依次“下坠”调整（自底向上处理各分支节点）
        • 调整规则：小元素逐层“下坠”（与关键字最大的孩子交换）
        • 将这个数组变成堆的排列方式
        • 代码：
      • 排序
        • 思路
          • 类同选择排序：每⼀趟在待排序元素中选取关键字最⼤的元素加⼊有序⼦序列
          • 将堆顶元素加入有序子序列（堆顶元素与堆底元素交换）
          • 堆底元素交换到堆顶后，需要进行“下坠”调整，恢复“大根堆”的特性
          • 上述过程重复 n-1 趟
          • 将这个堆变成层序遍历后的样子
        • 代码：
    • 特性
      • 空间复杂度
        • O(1)
      • 时间复杂度
        • 建堆O(n)
        • 排序O(n log_2 n)
        • 总的时间复杂度=O(n log_2 n)
      • 稳定性
        • 不稳定
      • 基于大跟堆排序得到“递增序列”，基于小根堆的堆排序得到“递减序列”
    • 基本操作
      • 插入
        • 新元素放到表尾（堆底）
        • 根据大、小根堆的要求，新元素不断上升，知道无法继续上升为止
        • 关键字比对次数
          • 每次“上升”调整秩序对比关键字1次
          • 每次“下坠”调整可能需要对比关键字 2 次，也可能只需对比一次
      • 删除
        • 被删除元素用表尾（堆底）元素替代
        • 根据大小根堆的要求，替代元素不断下坠，直到无法继续下坠为止
      • 定位
        • i 的左孩子 —— 2i
        • i 的右孩子 —— 2i+1
        • i 的父节点 —— ⌊i/2⌋
• 归并排序
  • 归并
    • 把两个或多个有序的子序列合并为一个
    • k 路归并 —— k 合一
  • 归并排序算法
    • ①若 low < high , 则将序列分从中间 mid = ( low + high ) / 2 分开
    • ②对左半部分 [ low, mid ] 递归地进行归并排序
    • ③对右半部分 [ mid +1, high ] 递归地进行归并排序
    • ④将左右两个有序子序列 Merge 为一个
  • 代码：
  • 性能
    • 空间复杂度
      • O(n)
        • 辅助数组
    • 时间复杂度
      • O(nlog n)
        • 2路归并的“归并树”—— 形态上就是一颗倒立的二叉树归并趟数 = 树高
        • 每趟归并的时间复杂度为O(n)
    • 稳定性
      • 稳定
• 基数排序
  • 算法思想
    • 将整个关键字拆分为d位（或“组”）
      • 将三位数拆成“个”、“十”、“百”三组
    • 按照各个关键字位权重递增的次序（如：个、十、百），做d趟“分配”和“收集”，若当前处理的关键字位可能取得r个值，则需要建立r个队列
    • 分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列。一趟分配耗时O(n)
    • 收集：把各个队列中的结点依次出队并链接。一趟收集耗时O(r)
    • 两种排序方式
      • MSD：最高有效位优先（从最高位开始）
      • LSD：最低有效位优先（从个位开始）
  • 性能
    • 空间复杂度
      • O(r)
    • 时间复杂度
      • O(d(n+r))
    • 稳定性
      • 稳定
  • 擅长处理
    • ①数据元素的关键字可以方便地拆分为d组，且d较小
    • ②每组关键字的取值范围不大，即r较小
    • ③数据元素个数n较大
• 计数排序
  • 适用条件
    • 待排序元素的关键字是整数型
    • 待排序元素的取值范围是 [0, k)，且k值较小，k 与 O(n) 同数量级
      • 注意：若 O(k) > O(n log₂ n)，就不用计数排序，改用快速排序、堆排序。
  • 算法实现
    • 创建一个长度为 k 的辅助数组 C[k]
    • Step 1：遍历待排序数组 A[n]，用辅助数组 C[i] 统计 A[] 中每个元素值 i 出现的次数（元素值只可能是 0~k-1，与辅助数组下标一一对应）
    • Step 2：再次处理辅助数组 C，最终用 C[i] 统计 ≤i 的元素个数
    • Step 3：从后往前依次处理各个待排序元素，结合辅助数组 C[] 实现排序 （注意：从后往前处理各个元素可确保排序的稳定性，详细过程建议自己手绘复习）
  • 算法性能
    • 时间复杂度：
      • O(n + k)
      • 当 k 与 O(n) 同数量级时，时间复杂度 = O(n)
    • 空间复杂度：
      • O(n + k)
        • O(n) 由输出数组 B[n] 导致
        • O(k) 由辅助数组 C[k] 导致
      • 当 k 与 O(n) 同数量级时，空间复杂度 = O(n)
  • 稳定性
    • 稳！
  • 代码：
• 外部排序
  • 若要进行k路归并排序，则需要在内存中分配k个输入缓冲区和1个输出缓冲区
  • 步骤
    • 生成r个初始归并段 （对L个记录进行内部排序，组成一个有序的初始归并段）
    • 进行 S 趟 k 路归并
  • 如何进行k路归并
    • 把k个归并段的块读入k个输入缓冲区
    • 用“归并排序”的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中
    • 当输出缓冲区满时，写出外存
    • 概念
      • 最多只能有 k 个段归并为一个
      • 没一趟归并中，有 m 个归并段参与归并，则经过这一趟处理得到⌈m/k⌉个新的归并段
  • 外部排序时间开销
    • 读写外存的时间+内部排序的时间+内部归并所需的时间
  • 优化
    • 增加归并路数 k，进行多路平衡归并
      • 代价1：需要增加相应的输入缓冲区
      • 代价2：每次从k歌归并段中选一个最小元素需要（k-1）次关键字对比
    • 减少初始归并段数量 r
• 败者树
  • 概念
    • 
    • 败者树是一种特殊的完全二叉树（多了一个头头），它用于组织多个有序序列的归并过程。
    • 每个有序序列的首元素（即当前待比较的最小元素）参与比较，败者树的叶子节点存储这些有序序列的首元素，而非叶子节点存储比较过程中的“败者”（即较大的元素）。
  • 结构特点
    • 叶子节点：败者树的叶子节点数量等于有序序列的数量。每个叶子节点存储一个有序序列的首元素。
    • 非叶子节点：非叶子节点存储比较过程中的“败者”元素。在每一轮比较中，较小的元素继续向上比较，较大的元素（败者）存储在非叶子节点中。
    • 完全二叉树：败者树是一棵完全二叉树，其高度为 O(logk)，其中 k 是有序序列的数量。
  • 在多路平衡归并中的应用
    • 使⽤多路平衡归并可减少归并趟数，但是⽤⽼⼟⽅法从 k 个归并段选出⼀个最⼩/最⼤元素需要对⽐关键字 k-1 次，构造败者树可以使关键字对⽐次数减少到 ⌈log2k⌉
    • 每个叶⼦结点对应⼀个归并段
    • 分⽀结点记录失败败者来⾃哪个归并段
    • 根节点记录冠军来⾃哪个归并段
• 置换-选择排序
  • 1. 从FI输⼊w个记录到⼯作区WA。
  • 2. 从WA中选出其中关键字取最⼩值的记录，记为MINIMAX记录。
  • 3. 将MINIMAX记录输出到FO中去。
  • 4. 若FI不空，则从FI输⼊下⼀个记录到WA中。
  • 5. 从WA中所有关键字⽐MINIMAX记录的关键字⼤的记录中选出最⼩关键字记录，作为新的MINIMAX记录。
  • 6. 重复3）～5），直⾄在WA中选不出新的MINIMAX记录为⽌，由此得到⼀个初始归并段，输出⼀个归并段的结束标志到FO中去。
  • 7. 重复2）～6），直⾄WA为空。由此得到全部初始归并段。
  • 概要
    • 设初始待排⽂件为FI，初始归并段输出⽂件为FO，内存⼯作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。
• 最佳归并树
  • 理论基础
    • 每个初始归并段对应一个叶子结点，把归并段的块数作为叶子的权值
    • 归并树的WPL=树中所有叶结点的带权路径长度之和
    • 归并过程中的磁盘I/O次数 =归并树的WPL*2
  • 注意：k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点
  • 如何构造
    • 补充虚段
      • ①若（初始归并段数量-1)\%(k-1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段
      • ②若（初始归并段数量-1)\%(k-1)=u≠0，则需要补充(k-1)-u个虚段
    • 构造k叉哈夫曼树
      • 每次选择k个根节点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值