3.4 线性表的顺序存储结构

• 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素
• 顺序存储结构的三个属性：
  • 存储空间的起始位置：数组data，他的存储位置就是存储空间的存储位置
  • 线性表的最大存储容量：数组长度MAXSIZE
  • 线性表的当前长度：length
• 数组长度与线性表长度的区别
  • 数组的长度时存放线性表的存储空间的长度，存储分配后这个量一般是不变的
    • 动态分配数组长度会带来性能上的损耗
  • 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，其长度可变
  • 在任意时刻，线性表的长度应该小于数组的长度，分配的数组空间要大于等于当前线性表的长度
• 假设每个数据元素占用c个存储单元，对于第i个数据元素$a_i$的存储位置为$LOC(a_i)=LOC(a_1)+(i-1)*c$
• 线性表的存取时间性能为O(1)，具有这一特点的存储结构称为随机存取结构
• 顺序存储结构的操作
  • 获得元素操作
  • 插入操作
    • 算法思路：
      1. 如果插入位置不合理，抛出异常
      2. 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量
      3. 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置
      4. 将要插入元素填入位置处
      5. 表长加1
  • 删除操作
    • 算法思路：
      1. 如果删除位置不合理，抛出异常
      2. 取出删除元素
      3. 从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置
      4. 表长加1
• 线性表的顺序存储结构，读数据时，时间复杂度为O(1);而插入或删除时，时间复杂度为O(n)
• 线性表的顺序存储结构的优缺点
  • 优点
    • 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
    • 可以快速地存取表中任一位置的元素
  • 缺点
    • 插入和删除元素需要移动大量元素
    • 当线性表长度变化大时，难以确定存储空间的容量
    • 造成存储空间的碎片

3.6 线性表的链式存储结构

• 链式线性表为解决顺序线性表插入和删除需要移动大量元素问题
• 链式存储结构的定义：
  • 为了表示数据元素$a_i$与数据元素$a_{i+1}$的逻辑关系
  • 数据元素$a_i$，除了存储本身的信息外，还需要存储一个指示其直接后继的信息
  • 存储数据元素信息的域称为数据域
  • 存储直接后继位置的域称为指针域，指针域中存储的信息称为指针或链
  • 这两部分信息组成数据元素$a_i$的存储映像，称为结点
• n个结点链结称一个链表，即为线性表的链式存储结构
  • 链表的每个结点中只包含一个指针域，所以叫做单链表
    • 链表的第一个结点的存储位置为头指针
    • 规定线性链表的最后一个结点指针为NULL
    • 为了方便操作，在单链表的第一个结点前附设一个结点，称为头结点
      • 头结点的指针域存储指向第一个结点的指针，其数据域可存线性表长度等公共信息
    • 头指针和头节点的异同
      • 头指针
        • 指链表指向第一个结点的指针，若链表包含头结点，则为指向头结点的指针
        • 具有标志作用
        • 无论链表是否为空，头指针均不为空，头指针时链表的必备元素
      • 头结点
        • 为了统一操作而设立的，放在第一元素之前，数据域一般无实际意义
        • 不一定是链表的必备元素
  • 结点由存放数据元素的数据域和存放后继结点的地址的指针域组成
• 单链表的读取：获得链表第i个数据的算法思路
  1. 声明一个指针p指向链表第一个结点，初始化j从1开始；
  2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
  3. 若到链表末尾p为空，则说明第i个结点不存在
  4. 否则查找成功，返回结点p的数据
• 单链表的插入：第i个数据插入结点的算法思路：
  1. 声明一指针p执行链表表头结点，初始化j从1开始
  2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
  3. 若到链表末尾p为空，则说明第i个结点不存在
  4. 否则查找成功，在系统生成一个空结点s
  5. 将数据元素e赋值给 s->data
  6. 单链表的插入标准语句：s->next=p->next;p->next=s;
  7. 返回成功
• 单链表的删除：第i个数据删除结点的算法思路：
  1. 声明一指针p执行链表表头结点，初始化j从1开始
  2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
  3. 若到链表末尾p为空，则说明第i个结点不存在
  4. 否则查找成功，将欲删除的结点 p->next 赋值给 q
  5. 单链表的删除标准语句 p->next = q->next;
  6. 将q结点中的数据赋值给e，作为返回
  7. 释放q结点
  8. 返回成功
• 单链表的整表创建：
  • 算法思路：
    1. 声明一指针p和计数器变量i
    2. 初始化一空链表L
    3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
    4. 循环
       1. 生成一新节点赋值给p
       2. 随机生成一数字赋值给p的数据域
       3. 将p插入到头结点与前一结点之间
  • 头插法：始终让新节点在第一的位置
  • 尾插法：每个新节点都插在终端结点的后面
• 单链表的整表删除：
  • 算法思路：
    1. 声明一指针p和q
    2. 将第一个结点赋值给p
    3. 循环
       1. 将下一个结点赋值给q
       2. 释放p
       3. 将q赋值给p
  • 在程序设计中，需要考虑到结点不仅仅包含指针域还有数据域

3.11 单链表结构与顺序存储结构的优缺点

• 对比
  • 时间性能
    • 查找：顺序存储结构O(n);单链表O(n)
    • 插入和删除：
      • 顺序存储结构需要平均移动表长一般的元素,时间复杂度为O(n)
      • 单链表在找出位置的指针后，插入和删除时间复杂度仅为O(1)
  • 存储分配方式
    • 顺序存储结构用一段连续存储单元依次存储线性表的数据元素
    • 单链表采用链表存储结构，用一组任意的存储单元存放线性表的元素
  • 空间性能
    • 顺序存储结构需要预分配存储空间
    • 单链表不需要分配存储空间
• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
• 当线性表中的元素个数变化较大或根本不知道有多大时，最好用单链表结构

3.12 静态链表

• 用数组代替指针描述单链表，用数组描述的链表叫做静态链表
  • 首先让数组的元素都是由两个数据域组成,data和cur
  • 数组的每个下标都对应一个data和cur。数据域data，用来存放数据元素；cur相当于单链表中的next指针，存放该元素的后继在数组中的下标
  • ==通常把未被使用的数组元素称为备用链表
    • 数组第一个元素，即下标为0的元素的cur存放备用链表的第一个结点的下标
    • 数组的最后一个元素cur存放第一个有数值的元素的下标，相当于单链表中的头结点
      • 当整个链表为空时，数组最后一个元素cur为0
• 静态链表的插入操作
  • 在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，需要自己实现
  • 为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新节点
• 静态链表的删除操作
• 静态链表的长度检测
• 静态链表的优缺点
  • 优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点
  • 缺点：没有解决连续存储分配带来的表长难以解决的问题；失去了顺序存储结构随机存取的特性

3.13 循环链表

• 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称为循环链表
• 循环链表和单链表的主要差异：在循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环结束

3.14 双向链表

• 双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域
• 在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱
• 双向链表可以是循环表

4 栈和队列

4.2 栈的定义

• 栈是限定仅在表尾进行插入和删除操作的线性表
  • 允许插入和删除一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈
  • 栈又称为后进先出的线性表，简称LIFO结构
• 注意事项：
  • 首先栈是一个线性表，定义中是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底
  • 栈底是固定的，最先进栈的只能在栈底
  • 栈的插入操作，叫做进栈，也称压栈，入栈
  • 栈的删除操作，叫做出栈，有的也叫做弹栈

4.3 栈的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13

ADT 栈
Data
  同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
  InitStack(*S):初始化操作,建立一个空栈S
  DestroyStack(*S):若栈存在，则销毁它
  ClearStack(*S):将栈清空
  StackEmpty(S):若栈为空，返回true，否则返回false
  GetTop(S,*e)：若栈存在且非空，用e返回S的栈顶元素
  Push(*S,e):若栈存在，插入新元素e到栈s中并称为栈顶元素
  Pop(*S,*e):删除栈S中的栈顶元素，并用e返回其值
  StackLength(S):返回栈S的元素个数
endADT

4.4 栈的顺序存储结构及实现

• 栈的顺序存储是线性表顺序存储的简化，简称为顺序栈
  • 下标为0的一端作为栈底比较好，因为首元素都在栈底，变化最小
• 定义top变量指示栈顶元素在数组中的位置
  • 若栈的空间为 $StackSize = n $
  • 空栈时$top = -1$
  • 栈满时$top = StackSize-1 = n-1$
• 栈的顺序存储结构，进栈操作和出栈操作时间复杂度为O(1)

4.5 两栈共享空间

• 数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n-1处。若两个栈如果增加元素，就是两端点向中间延伸
  • 栈1为空时，top1等于-1
  • 栈2为空时，top2等于n
  • 若栈2为空，栈1的top1等于n-1，栈1满栈
  • 若栈1为空，栈2的top2等于0，栈2满栈
  • top1+1=top2为满栈
• 使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况

4.6 栈的链式存储结构及实现

• 栈的链式存储结构，简称链栈
  • 栈顶放在单链表的头部，对于链表来说，是不需要头结点
  • 对于链栈来说，基本不存在栈满的情况
  • 对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候
• 栈的链式存储结构
  • 进栈操作,出栈操作的时间复杂度均为O(1)
  • 假设变量p用来存储要删除的栈顶结点，将栈顶指针下移移位，最后释放p即可
• 顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位方便，而链栈则要求每个元素都有指针域，这同时也增加一些内存开销，但对于栈的长度无限制
• 如果栈的使用过程中元素变化不可预料，最好用链栈，反之如果变化在可控范围内，建议使用顺序栈

4.7 栈的作用，应用

• 栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦需要解决的问题核心
• 应用
  • 递归：斐波那契数列
  • 四则运算表达式求值：
• 后缀表达式
  • 规矩：从左到右遍历中缀表达式的每个数字和符号，若是数组就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止
  • 最重要的两部：
    • 将中缀表达式转化为后缀表达式
    • 将后缀表达式进行运算得出结果

4.10 队列的定义

• 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
  • 队列是一种先进先出的线性表，简称FIFO，允许插入的一端称为队尾，允许删除的一端称为队头

4.12 循环队列

• 为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，==front指针指向队头元素，rear指针指向队尾元素的下一个位置，当front等于rear时，此队列是空队列
• 但仍然存在假溢出问题，解决的办法就是后面满了，从头开始，也就是头尾相接的循环
  • 把队列头尾相接的顺序存储结构称为循环队列
• 若队列的最大尺寸为QueueSize，循环列表的队列满的条件：$(rear+1)\%QueueSiza==front$
  • 通用的计算队列长度公式：$(rear-front+QueueSize)\% QueueSize$

4.13 队列的链式存储结构及实现

• 队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列
  • 队头指针指向链队列的头结点，而队尾指针指向终端结点
• 队列的链式存储结构——入队操作
  • 在链表尾部插入结点
• 队列的链式存储结构——出队操作
  • 出队操作时，就是在头结点的后继节点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素，则需将rear指向头结点
  • 循环队列与链队列的比较
    • 时间上，其实它们的基本操作都是常数时间，即都为O(1)的，循环队列是实现申请好空间，使用期间不释放；链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者有细微差异
    • 空间上，循环队列必须有一个固定的长度，所以有存储元素个数和空间浪费的问题；链队列，需要一个指针域，会有一定的空间开销，链队列更加灵活

5 串

• 串的定义：串是由零个或多个字符组成的有限序列，又叫字符串
  • 串中的字符数目n称为串的长度，零个字符的串称为空串，它的长度为零，可以直接用双引号表示
• 串的大小比较：
  • 给定两个串：$s=a_1a_2...a_n, t=b_1b_2...b_m$，当满足以下条件之一时，$s<t$
    • $n<m$,且$a_i<b_i(i=1,2,...n)$
    • 存在某个$k<=min(m,n)$,使得$a_i=b_i(i=1,2,...k-1)$,$a_k<b_k$
• 串的存储结构：
  • 串的顺序存储是用一组地址连续的存储单元来存储串中的字符序列的
    • 按照预定的大小，为每个定义的串变量分配一个固定长度的存储区，一般是用定长数组来定义
    • 定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置
  • 串的链式存储结构，与线性表相似，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单地应用链表存储串值，一个结点对应一个字符，会存在很大的浪费。
    • 一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用"#"或其他非串值字符补全
    • 一个结点存放多少个字符才合适就变得很重要，直接影响着串处理的效率，需要根据实际情况做出选择
    • 串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好

5.6 朴素的模式匹配算法

• 对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配，对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止
• 时间复杂度为O(n+m),其中n为主串长度,m为要匹配的子串长度，根据等概率原则，平均是(n+m)/2次查找，时间复杂度为O(n+m)

5.7 KMP模式匹配算法

• KMP匹配算法：一个模式匹配算法，可以避免重复遍历的情况
  • 在朴素的模式算法中，主串的i值是不断地回溯来完成的。分析后，这种回溯其实可以省略
  • T串的首字符与自身后面字符的比较，发现如果有相等字符，j值的变化就会不同。j值的变化与主串其实没有什么关系
  • j值的大小取决于当前字符之前的串的前后缀的相似度
  • 在需要查找字符串之前，先对要查找的字符串进行分析，可以减少查找的难度，提高查找的速度
  • T串各个位置j值的变化定义为一个数组next，next的长度就是T串的长度
    • $next[j]=\{\begin{array}{l}-1, \quad j=0 \\\max \{k \mid 1 \leq k \leq j { 且 } t[0] \ldots t[k-1]=t[j-k] \ldots t[j-1]\}, \quad { 集合非空 } \\0, \quad { 其他情况 }\end{array}.$
  • 算法实现整个算法的时间复杂度为O(n+m),相较于朴素模式匹配算法的O((n-m+1)*m)较好
  • ==KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才会具有较大优势
• KMP算法进行改进，用首位next[i]的值代替与它相等的字符后续next[j]的值
  • 改进的KMP算法，是在计算出next值得同时，如果a位字符与它next值指向的b位字符相等，则a位的nextval就指向b位的nextval值，如果不等则该a位的值就是它自己的next值

6 树

6.2 树的定义

• 树是n个结点的有限集。n=0时称为空树。在任意一颗非空树中，有且仅有一个特定的称为根的结点；当n>1时，其他结点可分为m个互不相交的有限集，其中每一个集合本身优势一棵树，并且称为根的子树
  • n>0时，根节点是唯一的
  • m>0时，子树的个数没有限制，但它们一定时不相交的
• 结点拥有的子树称为结点度(degree)，度为0的结点称为终端结点；度不为0的结点称为非终端结点或分支结点。除根节点之外，分支结点也称为内部结点。树的度是树内各节点的度的最大值。
  • 结点的子树的根称为该结点的孩子，相应，该结点称为孩子的双亲
  • 同一个双亲的孩子之间互称兄弟
  • 结点的祖先是从根到该结点所经历分支上的所有结点
  • 以某结点为根的子树中的任一结点都称为该结点的子孙
• 树的层次从根开始定义起，根为第一层，树的孩子为第二层，双亲在同一层的结点互称为堂兄弟。树中结点的最大层次称为树的深度(depth)
  • 如果将树中结点的各个子树看成从左到右有次序，不能互换的，则称概述为有序树
  • 森林是m棵互不相交的树的集合

6.3 树的存储结构

• 双亲表示法
  • 假设以一组连续空间存储树的结点，同时在每个节点中，附设一个指示器指示其双亲结点在数组中的位置，也就是说，每个结点除了知道自己是谁外，还知道它的双亲在什么位置。
    • data,parent data是数据域，存储结点的数据信息；parent是指针域，存储该结点的双亲在数组中的下标
    • 根节点没有双亲，约定根节点的位置域(双亲的位置)设置为-1，根节点的下标为0开始
    • 可以增加其他的域，如最左的孩子的域(长子域)，若没有长子域就设置为-1；右兄弟域等
• 孩子表示法
  • 使用多重链表，每个结点有多个指针域，其中每个指针指向一棵子树的根节点，这种方法称为多重链表表示法
    • 方案一：指针域的个数等于树的度(各个结点度的最大值)，浪费空间
    • 方案二：将每个结点放到一个顺序存储结构的数组中，每个结点的孩子建立一个单链表
      • 把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，若是叶子结点，则该单链表为空。然后n个头指针组成一个线性表，用顺序存储结构，存放进一个一维数组中
        • 孩子结点 child next ,child为数据域用来存储某个结点在表头数组中的下标，next是指针域，用来存储下一个孩子结点的指针
        • 表头结点：data firstchild ,data数据域存储某结点的数据信息,firstchild是头指针，存储该结点孩子链表的头指针
• 双亲孩子表示法：将双亲表示法和孩子表示法结合，在表头结点增加域
• 孩子兄弟表示法：
  • 任何一个树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟存在即唯一，可以设置两个指针分别指向该结点的第一个孩子和此结点的兄弟
  • data firstchild rightsib
  • 好处，将一个复杂的树转换为二叉树

6.5 二叉树的定义

• 二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根节点和两棵互不相交的,分别为根节点的左子树和右子树的二叉树组成
• 特点：
  • 每个结点最多由两棵子树，所以二叉树不存在度大于2的结点
  • 左子树和右子树是有顺序的，次序不能任意颠倒
  • 即使树中某结点只有一颗子树，也要区分他是左子树还是右子树
• 特殊的二叉树：
  • 斜树：所有的结点都只有左子树的二叉树称为左斜树
  • 满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树为满二叉树
  • 完全二叉树：对于一颗具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树成称为完全二叉树
    • 特点
      • 叶子结点只能出现在最下两层
      • 最下层的叶子一定集中在左部连续位置
      • 倒数第二层，若有叶子结点，一定都在右部连续位置
      • 如果结点度为1，则该结点只有左孩子，不存在只有右孩子的情况
      • 同样结点数的二叉树，完全二叉树的深度最小
• 二叉树的性质
  1. 在二叉树的第i层至多有$2^{i-1}$个结点
  2. 深度为k的二叉树至多有$2^k-1$个结点
  3. 对于任何一棵二叉树T，如果其终端结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$
  4. 具有n个结点的完全二叉树的深度为$ |\log_2n |+1,|x|表示不大于x的最大整数$
  5. 如果有一棵n个结点的完全二叉树有
     1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1其双亲是结点$|i/2|$
     2. 如果2i>n，则结点i无左孩子；否则其左孩子的结点是2i
     3. 如果2i+1>n，则该结点i无右孩子；否则其右孩子是结点2i+1

6.7 二叉树的存储结构

• 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系
  • 对于一般的二叉树，尽管层序编号不能反映其逻辑关系，但可以将其按照完全二叉树编号，将不存在的点设置为"^"
  • 顺序结构一般只用于完全二叉树
• 二叉链表
  • 二叉树的每个结点最多有两个孩子，所以设计一个数据域和两个指针域，将这样的链表称为二叉链表

6.8 遍历二叉树

• 二叉树的遍历是指从根节点触发，按照某种次序依次访问二叉树中的所有结点，使得每个结点都被访问一次且仅被访问一次
• 前序遍历
  • 规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树
• 中序遍历
  • 规则是若二叉树为空，则空操作返回，否则从根节点开始，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树
• 后序遍历
  • 规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历左右子树，最后是访问根节点
• 层序遍历
  • 规则是若二叉树为空，则空操作返回，否则从根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问
• 遍历算法在实现时按照递归算法进行实现，推导访问顺序时注意递归的思想
  • 中序遍历将访问左孩子的递归函数提前
  • 后序遍历先递归左子树
• 性质
  • 已知前序遍历序列和中序遍历序列，可以唯一确定一个二叉树
  • 已知后序遍历序列和中序遍历序列，可以唯一确定一个二叉树
  • 已知前序遍历序列和后序遍历序列，不可以唯一确定一个二叉树
• 建立二叉树，利用递归原理

6.10 线索二叉树

• 将指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表。相应的二叉树为线索二叉树
• ==中序遍历之后，将所有的空指针域中的rchild指向后继结点，lchild指向当前结点的前驱，添加两个标志位ltag和rtag，为0时指示指向的是孩子，为1时指示后继或前驱
• 如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继，宜采用线索二叉链表结构

6.11 树,森林与二叉树的转换

• 树转换为二叉树，步骤
  • 加线，在所有兄弟结点之间加一条线
  • 去线，对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
  • 层次调整，以树的根节点为轴心，将整棵树顺时针旋转一定的角度。注意第一个孩子是二叉树的左孩子，兄弟转换过来的孩子是结点的右孩子
• 森林转换为二叉树(森林的每一个树都是兄弟)
  • 将每个树转换为二叉树
  • 第一棵二叉树不懂，从第二可二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子
• 二叉树转换为树
  • 加线
  • 去线
  • 层次调整
• 二叉树转换为森林
  • 二叉树的根节点有右孩子，有就是森林，否则为树
• 树的遍历
  • 先根遍历树，先访问树的根节点，然后依次先根遍历根的每棵子树
  • 后根遍历树，先依次后根遍历每棵子树，然后再访问根结点
• 森林的遍历
  • 前序遍历：先访问森林中第一棵树的根节点，然后再依次先根遍历根的每棵子树，再依次用同样的方式遍历出去第一棵树的剩余树构成的森林
  • 后序遍历：先访问森林中第一颗树，后根遍历的方式遍历每棵子树，然后再访问根节点，再依次用同样方式遍历除去第一棵树的剩余树构成的森林

6.12 哈夫曼树及其应用

• 从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度
• 树的路径长度就是从树根到每一结点的路径长度之和
• 带权路径长度WPL最小的二叉树称为哈夫曼树(最优二叉树)
• 构造哈夫曼树的算法流程
  1. 根据给定的n个权值构成n棵二叉树的集合F，其中每棵二叉树T中只有一个带权为w的根节点，其左右子树都为空
  2. 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左右子树上根节点权值之和
  3. 在F中删除这两棵树，同时将新得到的二叉树加入F中
  4. 重复步骤2和3，直到F只含一棵树位置

7 图

7.4 图的定义

• 图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G(V,E),其中G表示一个图,V是图G中顶点的集合,E是图G中边的集合
  • 线性表中数据元素叫元素，树中数据元素叫结点，图中数据元素叫顶点
  • 定义强调顶点集合V的有穷非空
  • 任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集是可空
• 无向边：若顶点$V_i$到$V_j$之间的边没有方向，则称这条边为无向边，用无序偶对$(V_i,V_j)$表示
  • 无向图：任意两个顶点之间的边都是无向边
• 有向边：若从顶点$V_i$到$V_j$的边有方向，则称这条边为有向边，也称为弧。==用有序偶数对$< V_i,V_j >$表示，$V_i$称为弧尾，$V_j$称为弧头
  • 有向图：任意两个顶点之间的边都是有向边
• 无向边用小括号表示，有向边用尖括号表示
• 简单图：在图中若不存在顶点到其自身的边，且同一条边不重复出现
• 无向完全图：在无向图中，任意两个顶点之间都存在边(含有n个顶点的无向完全图有$\frac{n*(n-1)}{2}$条边)
• 有向完全图：在有向图中，任意两个顶点之间都存在方向相反的两条弧(含有n个顶点的有向完全图有$n*(n-1)$条边)
• 权：与图的边或弧相关的数
• 网：带权的图
• 子图：假设有两个图$G=(V,{E}),G^{\prime}=(V^{\prime},{E^{\prime}})$，如果$V^{\prime} \subseteq V ,E^{\prime}\subseteq E$，则称$G^{\prime}$为$G$的子图
• 对于无向图$G=(V,{E})$,如果边$(v^{\prime},v^{\prime}) \in E$,则称顶点$v$和$v^{\prime}$互为邻接点
  • 边$(v, v^{\prime})$ 依附于顶点 $v$ 和 $v^{\prime}$
  • 顶点 $v$ 的度是和 $v$ 相关联的边的数目, 记为 TD (v)
  • 边数和顶点度数和的关系:$e=\frac{1}{2} \sum_{i=1}^{n} T D(v_{i})$
• 对于有向图$G=(V,{E})$,如果边$<v^{\prime},v^{\prime}> \in E$,则称顶点$v^{\prime}$邻接自顶点$v$
  • 以顶点$v$为头的弧的数目称为v的入度,即为$ID(v)$；以$v$为尾的弧的数目称为v的出度,即为$OD(v)$
  • 顶点 $v$ 的度$TD (v) = ID(v) + OD(v)$,$e=\sum_{i=1}^{n} I D\left(v_{i}\right)=\sum_{i=1}^{n} O D\left(v_{i}\right)$
• 路径的长度是路径上的边或弧的数目
  • 回路(环)：第一个顶点和最后一个顶点相同的路径
  • 简单路径：序列中顶点不重复出现的路径称为简单路径
  • 简单回路：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
• 连通：在无向图G中，如果从顶点V到顶点$V^\prime$有路径，则称V和$V^\prime$连通
  • 连通图：图中任意两个顶点之间都是连通的
• 连通分量：无向图中的极大连通子图
  • 子图
  • 子图要连通
  • 连通子图含有极大顶点数
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边
• 强连通图：在有向图 ${G}$ 中, 如果对于每一对 ${v}_, {v}_ \in {V} 、 {v}_ \neq {v}_$, 从 ${v}_{\mathrm{i}}$ 到 ${v}_$ 和从 ${v}_$ 到 ${v}_$ 都存 在路径
• 有向图的强连通分量：有向图中的极大强连通子图
• 连通图的生成树：一个连通图的生成树是一个极小的连通子图，含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边
• 如果一个有向树恰有一个顶点的入度为0，其余顶点的入度为1，则是一个有向树
  • 一个有向树的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

7.4 图的存储结构

• 对于图而言，任意两个顶点之间都可能存在联系，故不可以使用简单的顺序结构实现
• 多重链表实现时，一个数据域和多个指针域组成的结点表示一个顶点，可以实现图结构，但是若各个顶点的度相差很大，按度最大的顶点设计会造成存储空间的浪费；但按照每个顶点自己的度进行设计，操作不便

7.4.1 邻接矩阵

• 图的邻接矩阵：是用两个数组来表示图。一个一维数组存储图中的顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息
  • 邻接矩阵的计算方法(图G有n个顶点，邻接矩阵为n*n方阵)
    • $\operatorname{arc[i][i]}=\{\begin{array}{l}1, { 若 }\left(v_{i}, v_{j}\right) \in E { 或 }\left\langle v_{i}, v_{j}\right\rangle \in E \\ 0, { 其他 }\end{array}$
  • 可设置顶点数组和边数组
    • 无向图的边数组为一个对称矩阵
    • 某个顶点的度其实就是这个顶点在邻接矩阵中第i行的元素之和
    • 顶点的所有邻接点就是将矩阵中的第i行元素扫描一遍
  • 有向图讲究入度和出度，入度为第i列的各数之和，出度为第i行的个数之和
• 网(每条边上带权的图)
  • 设G为网图，有n个结点，则邻接矩阵为一个n*n的方阵
    • $\operatorname{arc}[i][j]= \begin{cases}W_{i}, & { 若 }\left(v_{i}, v_{j}\right) \in E { 或 }<v_{i}, v_{j}>\in E \\ 0, & { 若 } i=j \\ \infty, & { 其他 }\end{cases}$
• 有了结构的i当以，构造一个图就是给顶点表和边表输入数据的过程
• n个顶点和e条边的无向网图的创建，时间复杂度为$O(n+n^2+e)$,其中对邻接矩阵的初始化花费了$O(n^2)$

7.4.2 邻接表

• 数组与链表相结合的存储方式称为邻接表
• 邻接表的处理办法
  • 图中顶点用一个一维数组存储；当然顶点可以用单链表存储，不过数组比较容易读取顶点信息，更加方便，对于顶点数组中每个元素需要存储指向第一个邻接点的指针，便于查找该顶点的边信息
  • 图中每个顶点$V_i$的所有邻接点构成一个线性表，由于邻接点的个数不定，使用单链表存储，无向图称为顶点$V_i$的边表，有向图则称为顶点$V_i$作为弧尾的出边表
• 顶点表的各个结点有data和firstedge两个域表示,data是数据域存储顶点的信息,firstedge是指针域，指向边表的第一个结点
• 边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针
• 以顶点作为弧尾来存储边表，可以容易得到每个顶点的出度
• 逆邻接表：一个有向图的逆邻接表，对每个顶点$V_i$都建立一个链接为$V_i$为弧头的表
• 网图：可以在边表结点定义中增加一个weight的数据域，存储权值信息

7.4.3 十字链表

• 将邻接表和逆邻接表结合起来，形成十字链表
  • 顶点表结点的结构：data firstin firstout ;firstin表示入边表头指针，指向该顶点的入边表中第一个结点；firstout表示出边表头指针，指向该顶点的出边表中的第一个结点
  • 边表结点的结构：tailvex headvex headlink taillink; tailvex指弧起点在顶点表中的下标；headvex指弧终点在顶点表中的下标；headlink指入边表指针域，指向终点相同的下一条边；taillink指边表指针域，指向起点相同的下一条边；如果是网还可以增加weight域存储权值
• 十字链表的好处就是因为把邻接表和逆邻接表整合在一起，容易找到以$V_i$为尾的弧，也容易找到以$V_i$为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一些，其实创建图算法的时间复杂度和邻接表相同

7.4.4 邻接多重表

• 更加关注边的操作
• 边表结点重新定义：ivex ilink jvex jlink ；ivex和jvex是与某条边依附的两个顶点在顶点表中的下标;ilink和jlink指向依附顶点ivex的下一条边：jlink指向依附顶点jvex的下一条边
  • ilink指向的结点的jvex一定要和它本身的ivex相同
• 邻接多重表与邻接表的差别
  • 邻接表同一条边在邻接表中用两个结点表示，而邻接表多重表中只有一个结点

7.4.5 边集数组

• 边集数组是由两个一维数组构成的。一个存储顶点的信息；另一个存储边的信息，这个边数组每个数据元素由一条边的起点下标,终点下标和权构成。
  • 边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。更适合对边依次进行处理的操作，不适合对顶点相关的操作
  • 边数组结构: begin end weight ;begin存储起点下标，end存储终点下标，weigth存储权值

7.5 图的遍历

• 图的遍历：从图中某一顶点出发访问图中其余顶点，且使每一个顶点仅被访问一次

7.5.1 深度优先遍历(DFS)

• 从图中某一顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度有限遍历图，直至图中所有和v有路径相通的顶点都被访问到
  • 实际这里讲的是连通图，对于非连通图，只需要对它的连通分量分别进行深度有限遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问为止
• 邻接矩阵方式和邻接表结构方式，邻接矩阵是二维数组，要查找每个顶点需要访问矩阵中的所有元素，因此时间复杂度为$O(n^2)$；而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，时间复杂度为$O(n+m)$
  • 显然，对于点多边少的稀疏图，邻接表结构使得算法在时间效率上大大提高

7.5.2 广度优先遍历(BFS)

• 图的广度优先遍历类似树的层序遍历
  • 图的深度优先遍历类似树的前序遍历
• 图的深度优先遍历和广度优先遍历，在时间复杂度上一致，不同的是对顶点访问的顺序不同
  • 深度优先更适合目标比较明确，以找到目标为主要目的的情况，广度优先适合在不断扩大遍历范围时找到最优解的情况

7.6 最小生成树

• 最小生成树：构造连通网的最小代价生成树
• 普利姆(Prim)算法：
  • 假设 $\mathrm{N}=(\mathrm{P},\{\mathrm{E}\})$ 是连通网, $\mathrm{TE}$ 是 $\mathrm{N}$ 上最小生成树中边的集合。算法从 $\mathrm{U}=\left\{\mathrm{u}_{0}\right\}$ $\left(u_{0} \in V\right), T E=\{\}$ 开始。重复执行下述操作: 在所有 $u \in U, v \in V-U$ 的边 ( $\left.u, v\right) \in E$ 中 找一条代价最小的边 $\left(u_{0}, v_{0}\right)$ 并入集合 $T E$, 同时 $v_{0}$ 并入 $U$, 直至 $U=V$ 为止。此时 $T E$ 中必有 $n-1$ 条边, 则 $T=(V,\{T E\})$ 为 $N$ 的最小生成树
  • 算法的时间复杂度为$O(n^2)$
• 克鲁斯卡尔(Kruskal)算法：
  • 假设 $\mathrm{N}=(\mathrm{V},\{\mathrm{E}\})$ 是连通网, 则令最小生成树的初始状态为只有 $\mathrm{n}$ 个顶点而无边的 非连通图 $\mathrm{T}=\{\mathrm{V},\{\}\}$, 图中每个顶点自成一个连通分量。在 $\mathrm{E}$ 中选择代价最小的边, 若 该边依附的顶点落在 $T$ 中不同的连通分量上, 则将此边加入到 $T$ 中, 否则舍去此边而 选择下一条代价最小的边。依次类推, 直至 $\mathrm{T}$ 中所有顶点都在同一连通分量上为止
  • 算法的FIND函数由变数e决定，时间复杂度为$O(log e)$，外面有一个for循环e次,故整个算法的时间复杂度为$O(elog e)$
• 克鲁斯卡尔算法针对边展开，边数较少时效率高，对稀疏图有很大优势；普利姆算法针对于稠密图，边数非常多的情况更好

7.7 最小路径

• 非网图的最小路径：指两个顶点之间经过边数最小的路径
• 网图：两顶点之间经过边上权值之和最少的路径，并且称路径上第一个顶点为源点，最后一个顶点为终点
• 迪杰斯拉特算法：一步步求出顶点之间的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到结果
• 弗洛伊德算法：D代表顶点到顶点的最短路径权值和矩阵，P代表对应顶点的最短路径的前驱矩阵
  • 在未分析任何顶点之前，将D命名为$D^{-1}$，其实它就是初始的图的邻接矩阵。将P命名为$P^{-1}$
  • 面临需要求所有顶点到所有顶点的最短路径问题，弗洛伊德算法较好

7.8 拓扑排序

• 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，为AOV图
  • 设 $\mathbf{G}=(\mathbf{V}, \mathrm{E})$ 是一个具有 $n$ 个顶点的有向图, $V$ 中的顶点序列 $\mathbf{v}_{\mathbf{1}}, \mathbf{v}_{\mathbf{2}}, \cdots \cdots, \mathbf{v}_{\mathrm{n}}$, 满足若从顶点 $\mathbf{v}_{\mathbf{i}}$ 到 $\mathbf{v}_{\mathbf{j}}$ 有一条路径，则在顶点序列中顶点 $\mathbf{v}_{\mathbf{i}}$ 必在顶点 $\mathbf{v}_{\mathbf{i}}$ 之前。则我们 称这样的顶点序列为一个拓扑序列
  • 所谓拓扑排序, 其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结 果, 如果此网的全部顶点都被输出, 则说明它是不存在环（回路）的 AOV 网; 如果输 出顶点数少了, 哪怕是少了一个, 也说明这个网存在环（回路）, 不是 AOV 网
• 对 AOV 网拓扑排序算法：从 AOV 网中选择一个入度为 0 的顶点输 出, 然后删去此顶点, 并删除以此顶点为尾的弧, 继续重复此步骤, 直到输出全部顶 点或者 AOV 网中不存在入度为 0 的顶点为止

7.9 关键路径

• 在一个表示工程的有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，为AOE图
  • AOE网中，没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点
  • 把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫做关键路径，在关键路径上的活动称为关键活动
• 关键路径算法
  • 参数：事件的最早发生时间etv,即顶点v的最早发生时间；事件的最晚发生时间ltv,即顶点v的最晚发生时间；活动的最早发生时间ete,即弧a的最早发生时间；活动的最晚发生时间lte,即弧a的最晚发生时间；
  • 顶点$V_k$即etv[k]的最早发生时间公式
    • $e t v[k]=\left\{\begin{array}{l}0, ，当k=0时 \\ \max \left\{e t v[i]+l e n<v_{i}, v_{k}>\right\}, { 当 } k \neq 0 { 且 }<v_{i}, v_{k}>\in P[k] { 时 }\end{array}\right.$
  • 顶点$V_k$即ltv[k]的最晚发生时间公式
    • $l t v[k]=\left\{\begin{array}{l}e t v[k] ，当 k=n-1时 \\ \min \left\{l t v[j]+l e n<v_{k}, v_{j}>\right\}, 当k<n-1且<v_{k}, v_{j}> \in[k]时\end{array}\right.$

8 查找

8.2 查找概论

• 查找表：由同一个类型的数据元素（或记录）构成的集合
  • 关键字：数据元素中某个数据项的值，又称为键值；用它可以标志一个数据元素
  • 关键码：标志一个记录的某个数据项
  • 主关键字：此关键字可以唯一地标志一个记录
  • 主关键码：主关键字所在的数据项
  • 次关键字：可以识别多个数据元素的关键字
  • 次关键码：次关键字对应的数据项
• 查找按操作方式分为两大类：静态查找表和动态查找表
  • 静态查找表：只做查找操作的查找表
    • 查找某个“特定的”数据元素是否在查找表中
    • 检索某个特定的数据元素和属性
  • 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素
    • 查找时插入数据元素
    • 查找时删除数据元素
  • 面向查找的数据结构为查找结构
    • 从逻辑上上，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。但需要获得更高的查找性能，需要改变数据结构，在查找时将集合组织成表,树等结构

8.3 顺序表查找

• 顺序查找：线性查找
  • 查找过程为：从表中第一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功
• 顺序表查找的优化：
  • 利用哨兵：在查找方向的尽头放置哨兵，免去了在查找过程中每一次比较后都要判断查找位置是否越界
    • 在数据量较大时，效率有所提高
• 时间复杂度为O(n)

8.4 有序表查找

• 折半查找
  • 折半查找技术，又称为二分查找。前提是线性表中的记录必须是关键字有序，线性表必须采用顺序存储
  • 折半查找的基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找，若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述操作，直到查找成功，过所有查找区域无记录，查找失败为止
  • 折半查找的时间复杂度为$O(logn)$
  • 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，但对于频繁执行插入或删除操作的数据集，维护有序的排列成本较高
• 插值查找
  • 根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，核心在于插值的计算，$mid=\frac{key-a[low]}{a[high]-a[low]}$
  • 时间复杂度为O(log n)
  • 对于表长较大，而关键字分布比较均匀的查找表插值查找性能较好；极端不均匀的数据，效率不高
• 斐波那契查找
  • 利用黄金分割的原理
  • 算法的核心：(F[k]为斐波那契数列)
    1. 当key = a[mid]时，查找成功
    2. 当key < a[mid]时，新范围为第low个到第mid-1个，此时范围个数为F[k-1]-1个
    3. 当key > a[mid]时，新范围为第m+1个到第high个，此时范围个数为F[k-2]-1个
• 折半查找是加法和除法运算$mid=\frac{low+high}{2}$；插值查找是进行复杂的四则运算$mid=\frac{key-a[low]}{a[high]-a[low]}$；斐波那契查找是进行简单的加减运算$mid = low+F[k-1]-1$

8.5 线性索引查找

• 数据结构的最终目的就是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构
• 索引：把关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引至少包含关键字和其对应的记录在存储器中的位置信息
  • 索引按照结构分为线性索引,树形索引和多级索引
    • 线性索引就是将索引项集合组织为线性结构，也称索引表
• 三种线性索引结构：稠密索引,分块索引和倒排索引
• 稠密索引
  • 稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项
  • 对于稠密索引这个索引表说，索引项一定是按照关键码有序排列的
• 分块索引
  • 对于分块有序的数据集，将每块对应一个索引项，该索引方法称为分块索引，(为了减少索引项的个数，可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数)
  • 分块有序是把数据集的记录分成了若干块，并且块满足：
    • 块内无序，每一块内的记录不要求有序
    • 块间有序
  • 分块索引的索引项结构
    • 最大关键码，存储每一块中的最大关键字
    • 存储了块中的记录个数
    • 用于指向块首数据元素的指针
• 倒排索引
  • 索引项的通用结构，次关键码和记录表号，其中记录表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或者该记录的主关键字)。这样的索引方法就是倒排索引
  • 倒排索引根据属性的值查找记录，这种索引表中的每一项都包括一个属性值和具有该属性值的各记录地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因此称为倒排索引

8.6 二叉排列树

• 动态查找表的数据结构之一
• 二叉排序树(二叉查找树)：或者是一棵空树，或者是具有以下性质的二叉树
  • 若它的左子树不空，则左子树上的所有结点的值均小于它的根结点的值
  • 若它的右子树不空，则右子树上的所有结点的值均大于它的根结点的值
  • 它的左,右子树也分别为二叉排序树
• 前提是二叉树，采用递归的定义方式，结点之间满足次序关系，左子树结点一定比双亲结点小，右子树结点一定比其双亲节点大
• 二叉树的查找操作,二叉树的插入操作和二叉树的删除操作
  • 对于二叉树的查找，走的就是从根节点到查找的结点的路径，其比较次数等于给定值的结点在二叉排序树中的层数
    • 极端情况，最少为1次，即根节点到要找到的结点最多不会超过树的深度，二叉排序树的查找性能取决于二叉排序树的形状
• 二叉排序树以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需要修改链接指针即可
  • 希望二叉排序树是平衡的，即深度与完全二叉树相同，都为$[log_2n]+1$，时间复杂度为$O(logn)$,近似于折半查找

8.7 平衡二叉树(AVL树)

• 平衡二叉树：是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1
  • 平衡因子BF：二叉树上的结点的左子树高度减右子树高度的值
  • 最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树
• 实现原理：
  • 构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中个结点之间的连接关系，进行相应的旋转，使之称为新的平衡子树
• 当最小平衡子树根结点平衡因子BF大于1时，右旋，小于-1就左旋
  • 当最小不平衡子树的BF与它的子树的BF符号相反时，就需要对结点先进行一次旋转使得符号相同后，再反向旋转一次完成平衡操作
• 二叉排序树是平衡二叉树，查找的时间复杂度为$O(logn)$，插入和删除操作为$O(logn)$

8.8 多路查找树(B树)

• 多路查找树，其每一个结点的孩子数可以多余两个，且每一个结点处可以存储多个元素
• 每一个结点存储多少个元素，以及它的孩子树的多少是非常关键的，四种特殊结构：2-3树,2-3-4树,B树,B+树
• 2-3树：其中每个结点都具有两个孩子(2结点)或三个孩子(3结点)
  • 一个2结点包含一个元素和两个孩子(或没有孩子),且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素
  • 一个3结点包含一小一大两个元素和三个孩子(或没有孩子)，左子树包含小于较小元素的元素，右子树包含大于该元素的元素
• 2-3树复杂的地方在于新节点的插入和已有结点的删除
• 插入分为3种情况：
  1. 对于空树，插入一个2结点即可
  2. 插入结点到一个2结点的叶子上
  3. 要往3结点种插入元素
     • 2-3树插入的传播效应导致根节点的拆分，则树的高度会增加
• 删除的3种情况
  1. 所删除元素位于一个3结点的叶子结点上
  2. 所删除元素位于一个2结点上，即要删除的是一个只有一个元素的结点
     1. 此结点的双亲也是2结点，且拥有一个3结点的孩子
     2. 此结点的双亲是2结点，它的右孩子也是2结点
     3. 此结点的双亲是一个3结点
     4. 若当前树是一个满二叉树的情况，此时删除任何一个叶子都会是整棵树不能满足2-3树的定义
  3. 所删除的元素位于非叶子的分支结点，通常将树按中序遍历后得到此元素的前驱或后继元素，考虑让它们来补位即可
• 2-3-4树
  • 2-3树的概念扩展，包括了4结点的使用；一个4结点包含小中大三个元素和4个孩子(或没有孩子)
• B树
  • B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例
  • B树的阶：结点最大的孩子数目称为B树的阶
  • m阶B树具有的属性：
    • 如果根节点不是叶结点，则其至少有两棵子树
    • 每一个非根的分支节点都有k-1个元素和k个孩子，其中$[\mathrm{m} / 2] \leqslant \mathrm{k} \leqslant \mathrm{m}$。每一个叶子结点结点n都有k-1个元素，其中$[\mathrm{m} / 2] \leqslant \mathrm{k} \leqslant \mathrm{m}$
    • 所有叶子结点都位于同一层次
    • 所有分支结点包含下列信息数据$\left(\mathrm{n}, \mathrm{A}_{0}, \mathrm{~K}_{1}, \mathrm{~A}_{1}, \mathrm{~K}_{2}, \mathrm{~A}_{2}, \cdots, \mathrm{K}_{\mathrm{n}}, \mathrm{A}_{\mathrm{n}}\right)$
  • 在B树上查找是一个顺指针查找结点和在结点中查找关键字的交叉过程
  • 外存是将所有的信息分割称相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是21-214B
    • B树的一个典型应用：要处理的硬盘数据量很大，无法一次全部装入内存
      • 将B树进行调整，使B树的阶数与硬盘存储的页面大小相匹配
      • 一棵B树的阶为1001，高度为2，可以存储超过10亿个关键字，只要让根节点持久的保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读写
    • B树的数据结构就是为内外存的数据交互准备的
  • 在含有n个关键字的B树上查找时，从根节点到关键字结点的路径上涉及的点数不超过$\log _{[\frac{m}{2}]}\left(\frac{n+1}{2}\right)+1$
• B+树
  • 为了解决所有元素遍历等问题，我们在原有B树结构基础上，加上了新的元素组织方式，形成B+树
  • 在B+树中，出现在分支节点中的元素会被当做它们在该分支结点位置的中序后继者中再次列出。另外，每一个叶子结点都会存储一个指向后一叶子结点的指针
  • m阶B+树和m阶B树的差别
    • 有n棵子树的结点中含有n个关键字
    • 所有的叶子结点包含全部关键字信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
    • 所有分支结点可以看成索引，结点中仅含有其子树中的最大（或最小）关键字
  • 好处：
    • 如果是要随机查找，从根结点触发，与B树的查找方式相同，只不过即使在分支结点找到了待查找的关键字，也只是用来索引的，不能提供实际记录的访问，还是需要到达包含次关键字的终端结点
    • 如果需要从最小关键字进行从小到大的顺序查找，可以从最左侧的叶子结点出发，不经过分支结点，而是沿着指向下一叶子的指针就可遍历所有的关键字
  • B+树的插入，删除过程都与B树类似，只不过插入和删除的元素都是在叶子结点上进行而已

8.9 散列表查找(哈希表)概述

• 散列技术：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)
  • 对应关系f称为散列函数，又称为哈希(Hash)函数
  • 采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表
• 查找步骤：
  • 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录
  • 当查找记录时，通过同样的散列函数计算记录的散列函数，按此散列地址访问该记录
• 散列技术最适合求解的问题是查找与给定值相等的记录
• 冲突：两个关键字$key_1 \not ={ key_2 }$,但是却有$f(key_1) = f(key_2)$，并且将$key_1,key_2$称为这个散列函数的同义词
• 散列函数的构造函数
  • 直接定址法：
    • 取关键字的某个线性函数为散列函数,$f(key)=a \times key +b(a,b为常数)$
    • 散列函数的优点简单,均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况
  • 数学分析法
    • 抽取方法是使用关键字的一部分来计算散列存储位置的方法
    • 数学分析法通常适合处理关键字位数比较多的情况，事先知道关键字的分布且关键字的若干位分布较均匀，可以使用该方法
  • 平方取中法
    • 平方取中法比较适合不知道关键字的分布，而位数又不是很多的情况
  • 折叠法
    • 折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
    • 折叠法实现不需要知道关键字的分布，适合关键字位数较多的情况
  • 除留余数法(最常用的构造散列函数的方法)
    • 散列表长为m的散列函数$f(key)=mod(key,p)$，对key取模
    • 不仅可以对关键字直接取模，也可在折叠,平方取中后再取模
    • 若散列表表长为m，通常p为小于或等于表长的最小质数或不包含小于20质因子的合数
  • 随机数法
    • $f(key)=random(key)$
    • 当关键字的长度不等时，采用这个方法构造散列函数是比较适合的

8.11 处理散列冲突的办法

• 开放定址法
  • 开放定址法是一旦发生了冲突，就取寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存下
  • 线性探测法：公式：$f_i(key) = MOD(f(key)+d_i,m),(d_i=1,2,3...m-1)$
  • 本身不是同义词却需要争夺一个地址的情况称为堆积
  • 二次探测法：公式：$f_i(key) = MOD(f(key)+d_i,m),(d_i=1^2,-1^2,2^2,-2^2...q^2,-q^2,q \leqslant m/2)$
    • 增加平方运算的目的是为了不让关键字都聚集在某一个区域
  • 随机探测法：$f_i(key) = MOD(f(key)+d_i,m),(d_i为随机数列$
    • $d_i$为伪随机数
• 再散列函数法
  • $f_i(key) = RH_i(key)$,RH为不同的散列函数
• 链地址法
  • 将所有关键字为同义词的记录存储在一个单链表中，这种表为同义词子表
  • 链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障，查找时需要遍历单链表，性能损耗
• 公共溢出区法
  • 在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表取进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说非常高
• 散列表查找的性能分析
  • ==若没有冲突，散列查找的性能最高，时间复杂度为O(1)
  • 散列函数是否均匀
  • 处理冲突的方法
  • 散列表的装填因子
    • 所谓的装填因子a=填入表中的记录个数/散列表长度
    • a标志着散列表的装满程度，填入表中的记录越多，a越大，产生冲突的可能性越大

9 排序

9.2 排序的基本概念与分类

• 排序：假设含有 $\mathbf{n}$ 个记录的序列为 $\left\{\mathbf{r}_{1}, \mathbf{r}_{2}, \cdots \cdots, \mathbf{r}_{\mathbf{n}}\right\}$, 其相应的关键字分别为 $\left\{\mathbf{k}_{1}, \mathbf{k}_{2}, \cdots \cdots\right.$, $\left.\mathbf{k}_{\mathbf{n}}\right\}$, 需确定 $1,2, \cdots \cdots, \mathbf{n}$ 的一种排列 $\mathbf{p}_{\mathbf{1}}, \mathbf{p}_{2}, \cdots \cdots, \mathbf{p}_{\mathbf{n}}$, 使其相应的关键字满足 $\mathbf{k}_{\mathbf{p} 1} \leqslant$ $\mathbf{k}_{\mathrm{p} 2} \leqslant \cdots \cdots \leqslant \mathbf{k}_{\mathrm{pn}}$ (非递减或非递增) 关系, 即使得序列成为一个按关键字有序的序列 $\left\{\mathbf{r}_{\mathbf{p} 1}, \mathbf{r}_{\mathbf{p} 2}, \cdots \cdots, \mathbf{r}_{\mathbf{p n}}\right\}$, 这样的操作就称为排序
• 排序的稳定性：假设 $k_{\mathbf{i}}=k_{\mathbf{j}}\left(1 \leqslant i \leqslant n, 1 \leqslant \mathbf{j} \leqslant n, i \neq j\right.$ ), 且在排序前的序列中 $r_{i}$ 领先于 $r_{\mathbf{j}}$ （即 $\mathbf{i}<\mathbf{j}$ )。如 果排序后 $\mathbf{r}_{\mathbf{i}}$ 仍领先于 $\mathbf{r}_{\mathbf{j}}$, 则称所用的排序方法是稳定的; 反之, 若可能使得排序后的 序列中 $r_{j}$ 领先 $r_{1}$, 则称所用的排序方法是不稳定的
• 排序分为内排序和外排序
  • 内排序：内排序是在排序整个过程中, 待排序的所有记录全部被放置在内存中。外排序是 由于排序的记录个数太多, 不能同时放置在内存, 整个排序过程需要在内外存之间多 次交换数据才能进行
• 内排序的排序算法性能：
  1. 时间性能
  2. 辅助空间
  3. 算法的复杂性

9.3 冒泡排序

• 冒泡排序是一种交换排序,基本思想是：两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止
• 最简单排序的实现
  • 思路：让每一个关键字都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字就在一次循环后一定变成最小值，(效率低)
• 冒泡排序算法
• 冒泡排序算法优化
  • 使用flag标记变量实现算法改进，避免重复比较
• 复杂度分析：
  • 最好的情况O(n)，最坏的情况，逆序时需要比较$\sum_{i=2}^{n}(i-1)=1+2+3+\cdots+(n-1)=\frac{n(n-1)}{2}$
  • 时间复杂度为$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// 最简单排序的实现
// 对顺序表L左交换排序(冒泡排序初级版)
void BubbleSort0(SqList *p){
  int i,j;
  for(i=1;i < L->length;i++){
    for(j=i+1;j < L->length;j++){
      if(L->r[i] > L->r[j])
        swap(L,i,j);    //交换L->r[i]和L->r[j]的值
    }
  }
}

// 冒泡排序算法
void BubbleSort1(SqList *p){
  int i,j;
  for(i=1;i < L->length;i++){
    for(j=L->length-1;j >= i;j--){  //注意j时从后向前循环
      if(L->r[i] > L->r[j+1])       //若前置大于后者
        swap(L,j,j+1);    //交换L->r[j]和L->r[j+1]的值
    }
  }
}

// 冒泡排序的优化版本
void BubbleSort2(SqList *p){
  int i,j;
  Status flag = TRUE;             //flag作为标记
  for(i=1;i < L->length && flag;i++){   //若flag为TRUE则有数据交换，否则退出循环
    flag = FALSE;                 //初始化为false
    for(j=L->length-1;j >= i;j--){  //注意j时从后向前循环
      if(L->r[i] > L->r[j+1]){       //若前置大于后者
        swap(L,j,j+1);    //交换L->r[j]和L->r[j+1]的值
        flsg = TRUE;
      }
    }
  }
}

9.4 简单选择排序

• 选择排序的基本思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列的第i个记录
• 简单选择排序：通过n-i次关键字间的比较，从n-i+1个数据中选出关键字最小的记录，并在第i个记录交换
• 复杂度分析
  • 最大特点时交换移动数据次数相当少
  • 无论最好最差的情况，其比较的次数时一样多的，第i趟排序需要进行n-i次关键字的比较，需要进行$\sum_{i=1}^{n-1}(n-i)=1+2+3+\cdots+(n-1)=\frac{n(n-1)}{2}$次比较
  • 交换而言，最好的时候交换次数为0,最差的情况(初始降序)，交换次数为n-1
  • 基于最终的排序时间是比较与交换的次数总和，总的时间复杂度为$O(n^2)$
  • 简单选择排序的性能比冒泡排序高

1
2
3
4
5
6
7
8
9
10
11
12
13

// 简单排序
void SelectSort(SqList *L){
  int i,j,min;
  for(i=1;i<L->length;i++){
    min = i;        //将当前下标定义为最小值下标
    for(j = i+1;j<=L->length;j++){  //循环之后的数据
      if(L->r[min] > L->r[j])     //如果有小于当前最小值的关键字
        min=j;      //将此下标赋值给min
    }
    if(i!=min)      //若min不等于i，说明找到最小值，交换
      swap(L,i,min);    //交换
  }
}

9.5 直接插入排序

• 直接插入排序：基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的,记录数增1的有序表
• 复杂度分析：
  • 空间上只需要一个记录的辅助空间
  • 最好的情况下没有移动的记录，比较了n-1次，时间复杂度为O(n)
  • 最坏的情况下(逆序)，比较$\sum_{i=2}^{n} i=2+3+\cdots+n=\frac{(n+2)(n-1)}{2}$次，移动了$\sum_{i=2}^{n}(i+1)=\frac{(n+4)(n-1)}{2}$次
  • 等概率原则，平均比较和移动次数约为$\frac{n^2}{4}$次
  • 直接插入排序的时间复杂度为$O(n^2)$,但性能比冒泡和简单排序好

1
2
3
4
5
6
7
8
9
10
11

void InsertSort(SqList *L){
  int i,j;
  for(i = 2;i<=L->length;i++){
    if(L->r[i] < L->r[i-1]){    //需要将L->r[i]插入到有序表中
      L->r[0] = L->r[i];        //设置哨兵
      for(j=i-1;L->r[j]>L->r[0];j--)
        L->r[j+1] = L->r[j];    //记录后移
      L->r[j+1] = L->r[0];      //插入到正确位置
    }
  }
}

9.6 希尔排序算法

• 思想：大量数据时，将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，再对全体记录进行一次直接插入排序
  • 基本有序：小的关键字基本在前面，大的基本在后面，不大不小的基本在中间
• 问题的关键，分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展
  • 跳跃分割策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
• 复杂度分析：
  • 关键并不是随便分组后各自排序，而是将相隔某个增量的记录组成一个子序列，实现跳跃式的移动，使得排序效率提高
  • 研究表明，当增量序列为$\operatorname{dlta}[k]=2^{\mathrm{t}-\mathrm{k}+1}-1 \quad\left(0 \leqslant \mathrm{k} \leqslant \mathrm{t} \leqslant\left\lfloor\log _{2}(\mathrm{n}+1)\right\rfloor\right)$时，效率不错，==其时间复杂度为$O(n^{3/2})$
  • 需要注意，增量序列的最后一个增量必须等于1才可以
  • 由于记录时跳跃式的移动，希尔排序不是稳定排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 希尔排序(传入的r[10]={0,9,1,5,8,3,7,4,6,2},length=9(第一位0不算长度))
void ShellSort(SqList *L){
  int i,j,k=0;
  int increment = L->length;
  do{
    increment = increment/3+1;    //增量序列
    for(i=increment+1;i<=L->length;i++){
      if(L->r[i] < L->r[i-increment]){    //将L->r[i]插入有序增量子表
        L->r[0] = L->r[i];    //暂存在L->r[0]
        for(j=i-increment;j>0 && L->r[0] < L->r[j]; j-=increment)
          L->r[j+increment] = L->r[j];    //记录后移,查找插入位置
        L->r[j+increment] = L->r[0];    //插入
      }
    while(increment>1)
    }
  }
}

9.7 堆排序

• 堆排序做到每次在选择最小记录的同时，并根据比较结果对其他记录做出相应的调整，排序的总体效率非常高
• 堆是具有以下性质的二叉树
  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
  • 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
• 根结点一定是堆中所有结点最大(小)者，较大(小)的结点靠近根结点
• 按照层序遍历的方式给结点从1开始编号，结点之间满足的关系
  • $\left\{\begin{array}{l}k_{i} \geqslant k_{2 i} \\ k_{i} \geqslant k_{2 i+1}\end{array}\right.$ 或 $\left\{\begin{array}{l}k_{i} \leqslant k_{2 i} \\ k_{i} \leqslant k_{2 i+1}\end{array} 1 \leqslant i \leqslant \frac{n}{2}\right\rfloor$
  • $i<[n/2]$的原因
    • 二叉树性质的第五条跳转:一棵完全二叉树,如果i=1,则根结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]。对于有n个结点的二叉树，i值自然小于等于[i/2]
• 堆排序算法
  • 基本思想：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列
  • 整个排序过程分为两个for循环，第一个循环完成将现在的待排序序列构建成一个大顶堆。第二个循环完成逐步将每个最大值的根结点与末尾元素交换，并且再调整其成为大顶堆
    • 待排序的序列构建成一个大顶堆，其实就是从下往上，从右往左，将每个非终端结点当作根节点，将其和其子树调整成大顶堆
• 复杂度分析
  • 运行时间主要小号在初始构建堆和在重建堆时的反复筛选上
  • 在构建堆的过程中，因为是完全二叉树从最下层最右边的非终端结点开始构建的，将它与其孩子进行比较，若有必要进行互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，整个堆构建的时间复杂度为O(n)
  • 在正式排序时，第i次取堆顶记录重建堆需要用$O(log i)$的时间(完全二叉树的某个结点到根节点的距离为$[log_2 i]+1$)，并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为$O(n log n)$
  • 总体堆排序的时间复杂度为$O(n log n)$
    • 由于堆排序对原始记录的排序状态不敏感，因此最好,最坏和平均时间复杂度为$O(n log n)$.性能上优于冒泡,简单选择,直接插入排序
  • 空间复杂度上，只有一个用来交换的暂存空间
  • 由于初始构建堆所需的比较次数较多，不适合待排序个数较少的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// 堆排序
void HeapSort(SqList *L){
  int i;
  for(i = L->length/2;i>0;i--)
    HeapAdjust(L,i,L->length);  //构建大顶堆
  for(i=L->length;i>1;i--){
    swap(l,1,i);    //将堆顶元素和当前未经排序子序列的最后一个交换
    HeapAdjust(l,1,i-1)     //重新调整L->r[1..i-1]位大顶堆
  }
}

// 大顶堆生成
void HeapAdjust(SqList *L, int s, int m){
  int temp,j;
  temp=L->r[s];
  for(j=2*s;j<=m;j*=2){     //沿关键字较大的孩子结点向下筛选
    if(j<m && L->r[j] < L->r[j+1])
      ++j;        //j为关键字中较大的记录的下标
    if(temp >= L->r[j])
      break;      //rc应插入在位置s上
    L->r[s] = L->r[j];
    s=j;
  }
  L->r[s] = temp;   //插入
}

//
j变量为什么是从2*s开始？为什么是j*2递增？
原因在于二叉树的性质5,因为是完全二叉树，当前结点序号是s，其左孩子的序号一定是2s，右孩子的序号一定是2s+1，它们的孩子当然也是以2的位数序号增加
*/

9.8 归并排序

• 堆排序用到了完全二叉树，充分利用了完全二叉树的深度$[log_2 n]+1$的特性，效率较高
• 归并：在数据结构中的定义是将两个或两个以上的有序表合成一个新的有序表
• 归并排序：利用归并思想实现的排序方法
  • 原理：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……,如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序
• 复杂度分析：
  • 一趟归并需要将SR[1]~SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]~TR1[n]中，需要将带排序序列中的所有记录扫描一遍，耗费**O(n)**的时间
  • 由完全二叉树的深度可知,整个归并排序需要进行$log_2 n$次，因此总的时间复杂度为$O(n logn)$(归并算法最好,最坏,平均的时间性能)
  • 由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为$log_2 n$的栈空间,空间复杂度为$O(n+logn)$
  • 归并排序是稳定的排序算法，但比较占用内存，效率较高且稳定
• 非递归实现归并排序
  • 非递归的迭代方法，避免了递归时深度为$log_2 n$的栈空间,空间只是用到申请归并临时用的TR数组,因此空间复杂度为$O(n)$,并且避免递归在时间性能上有所提升
  • 使用归并排序时优先考虑使用非递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

// 对顺序表L作归并排序
void MergeSort(SqList *L){ 
  MSort(L->r,L->r,1,L->length);
}

// 将SR[s..t]归并排序为TR1[s..t]
void MSort(int SR[],int TR1[],int s, int t){
  int m;
  int TR2[MAXSIZE+1];
  if(s==t)
  TR1[s]=SR[s];
  else
  {
  m=(s+t)/2;    // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
  MSort(SR,TR2,s,m);  // 递归地将SR[s..m]归并为有序的TR2[s..m]
  MSort(SR,TR2,m+1,t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
  Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
  }
}

void Merge(int SR[],int TR[],int i,int m,int n){ // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
  int j,k,l;
  for(j=m+1,k=i;i<=m && j<=n;k++) // 将SR中记录由小到大地并入TR
  {
  if (SR[i]<SR[j])
   TR[k]=SR[i++];
  else
   TR[k]=SR[j++];
  }
  if(i<=m)
  {
  for(l=0;l<=m-i;l++)
   TR[k+l]=SR[i+l];  // 将剩余的SR[i..m]复制到TR
  }
  if(j<=n)
  {
  for(l=0;l<=n-j;l++)
   TR[k+l]=SR[j+l];  // 将剩余的SR[j..n]复制到TR
  }
}

//非递归实现
// 对顺序表L作归并非递归排序
void MergeSort2(SqList *L){
  int* TR=(int*)malloc(L->length * sizeof(int)); // 申请额外空间
    int k=1;
  while(k<L->length)
  {
  MergePass(L->r,TR,k,L->length);
  k=2*k;          // 子序列长度加倍
  MergePass(TR,L->r,k,L->length);
  k=2*k;          // 子序列长度加倍       
  }
}


void MergePass(int SR[],int TR[],int s,int n){// 将SR[]中相邻长度为s的子序列两两归并到TR[]
  int i=1;
  int j;
  while(i <= n-2*s+1)     // 两两归并
  {
  Merge(SR,TR,i,i+s-1,i+2*s-1);
  i=i+2*s;        
  }
  if(i<n-s+1)       // 归并最后两个序列
  Merge(SR,TR,i,i+s-1,n);
  else         // 若最后只剩下单个子序列
  for(j =i;j <= n;j++)
   TR[j] = SR[j];
}

9.9 快速排序

• 希尔排序为直接插入排序的升级版，都属于插入排序类
• 堆排序为选择排序的升级版，都属于选择排序类
• 快速排序为冒泡排序的升级版，都属于交换排序类
• 快速排序的基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续排序，以达到整个序列有序的目的
• 算法中Partition()函数的作用就是先选取当中的一个关键字，想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值都比它大，将这样的关键字称为枢轴(pivot)
• 复杂度分析:
  • 快速排序的时间性能取决于快速排序递归的深度,可以使用递归树描述递归算法的执行情况
  • 在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度为$[log_2 n]+1$([x]表示不大于x的最大整数),仅需递归$log_2 n$次，需要的时间为T(n)的话，第一次Partition应该时需要对整个数组扫描一遍，做n次比较。然后获得的枢轴将数组一分为二，那么各自需要T(n/2)的时间，归纳可得，最优情况下，快速排序算法的时间复杂度为$O(nlog n)$
  • 最坏的情况下,待排序的序列为正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。递归树为一棵斜树。需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，比较的次数为$\sum_{i=1}^{n-1}(n-i)=1+2+3+\cdots+(n-1)=\frac{n(n-1)}{2}$次比较,最终的时间复杂度为$O(n^2)$
  • 平均情况,枢轴位置在第k个位置,$T(n)=\frac{1}{n} \sum_{k=1}^{n}(T(k-1)+T(n-k))+n=\frac{2}{n} \sum_{k=1}^{n} T(k)+n$,数学归纳法可得其时间复杂度为$O(nlogn)$
  • 空间复杂度：
    • 主要是递归导致的栈空间的使用
    • 最好情况下，递归树的深度为$log_2 n$，其空间复杂度为$O(logn)$
    • 最坏的情况下，需要n-1次递归调用，空间复杂度为O(n)
    • 平均情况下，空间复杂度为$O(logn)$
  • 关键字的比较和交换是跳跃进行的，故是一种不稳定的排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// 对顺序表L作快速排序
void QuickSort(SqList *L){ 
  QSort(L,1,L->length);
}

// 对顺序表L中的子序列L->r[low..high]作快速排序
void QSort(SqList *L,int low,int high){ 
  int pivot;
  if(low<high)
  {
    // 将L->r[low..high]一分为二，算出枢轴值pivot
    pivot=Partition(L,low,high); 
    QSort(L,low,pivot-1);   //  对低子表递归排序
    QSort(L,pivot+1,high);   //  对高子表递归排序
  }
}

int Partition(SqList *L,int low,int high){
  // 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置，此时在它之前(后)均不大(小)于它。*/
  int pivotkey;

  pivotkey=L->r[low];  // 用子表的第一个记录作枢轴记录
  while(low<high)     //从表的两端交替地向中间扫描
  { 
    while(low<high&&L->r[high]>=pivotkey)
    high--;
    swap(L,low,high);   // 将比枢轴记录小的记录交换到低端
    while(low<high&&L->r[low]<=pivotkey)
    low++;
    swap(L,low,high);   // 将比枢轴记录大的记录交换到高端
  }
  return low;     // 返回枢轴所在位置
}

9.9.3 快速排序优化

• 优化选取枢轴
  • 随机选取枢轴法
  • 三数取中法：取三个关键字先进行排序，将中间数作为枢轴，一般是取左端，右端和中间三个数
  • 九数取中法，从数组中分别三次取样，每次取三个数，三个样品各取出中数，然后将这三个中数当中再取出一个中数作为枢轴
• 优化不必要的交换
• 优化小数组时的排序方法
• 优化递归操作
  • QSort()函数在其尾部有两次递归操作
  • 如果待排序的序列划分极端不平衡，递归深度将趋于n，而不是平衡时的$log_2 n$，不仅仅是速度快慢的问题
  • 栈的大小是有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多；若递归减少，将会大大提高性能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

// 优化选择枢轴
int pivotkey;
int m = low + (high - low) / 2;  // 计算数组中间的元素的下标
if (L->r[low]>L->r[high])   
  swap(L,low,high);    // 交换左端与右端数据，保证左端较小
if (L->r[m]>L->r[high])
  swap(L,high,m);     // 交换中间与右端数据，保证中间较小
if (L->r[m]>L->r[low])
  swap(L,m,low);     // 交换中间与左端数据，保证左端较小
// 此时L.r[low]已经为整个序列左中右三个关键字的中间值
pivotkey=L->r[low];     // 用子表的第一个记录作枢轴记录

// 优化不必要的交换
// 快速排序优化算法
int Partition1(SqList *L,int low,int high)
{ 
  int pivotkey;

  int m = low + (high - low) / 2; // 计算数组中间的元素的下标  
  if (L->r[low]>L->r[high])   
    swap(L,low,high);   // 交换左端与右端数据，保证左端较小
  if (L->r[m]>L->r[high])
    swap(L,high,m);    // 交换中间与右端数据，保证中间较小
  if (L->r[m]>L->r[low])
    swap(L,m,low);    // 交换中间与左端数据，保证左端较小

  pivotkey=L->r[low];    // 用子表的第一个记录作枢轴记录
  L->r[0]=pivotkey;      // 将枢轴关键字备份到L->r[0]
  while(low<high)     //  从表的两端交替地向中间扫描
  { 
    while(low<high&&L->r[high]>=pivotkey)
      high--;
      L->r[low]=L->r[high];  // 采用替换而不是交换的方式进行操作
      while(low<high&&L->r[low]<=pivotkey)
        low++;
      L->r[high]=L->r[low];  // 采用替换而不是交换的方式进行操作
  }
  L->r[low]=L->r[0];    // 将枢轴数值替换回L.r[low]
  return low;      // 返回枢轴所在位置
}

//优化小数组时的排序
#define MAX_LENGTH_INSERT_SORT 7 // 用于快速排序时判断是否选用插入排序阙值
// 对顺序表L中的子序列L.r[low..high]作快速排序
void QSort1(SqList *L,int low,int high)
{ 
  int pivot;
  if((high-low)>MAX_LENGTH_INSERT_SORT)
  {
    pivot=Partition1(L,low,high);  // 将L->r[low..high]一分为二，算出枢轴值pivot
    QSort1(L,low,pivot-1);   // 对低子表递归排序
    QSort1(L,pivot+1,high);   // 对高子表递归排序
  }
  else
    InsertSort(L);     // 当high-low小于等于常数时用直接插入排序
}

// 优化递归操作
// 尾递归
void QSort2(SqList *L,int low,int high)
{ 
  int pivot;
  if((high-low)>MAX_LENGTH_INSERT_SORT)
  {
    while(low<high)
    {
      pivot=Partition1(L,low,high); // 将L->r[low..high]一分为二，算出枢轴值pivot
      QSort2(L,low,pivot-1);  // 对低子表递归排序
      low=pivot+1;    // 尾递归
    }
  }
  else
    InsertSort(L);     // 当high-low小于等于常数时用直接插入排序
}

9.10 总结回顾

• 算法概念

• 算法性能指标

• 三种简单排序算法移动次数比较