数据结构

1、绪论

知识框架

• 术语：数据、数据元素、数据对象、数据类型、数据结构
• 数据结构三要素：逻辑结构、存储结构、数据的运算(操作)
• 算法的五个特征：有穷性、稳定性、可行性、输入和输出

基本概术

• 数据：能输入到计算机并被程序识别处理的符号集合
• 数据元素：是数据的基本单位，作为整体考虑
  • 数据项(学号、姓名)，数据元素(学生记录)
  • 数据项是构成数据元素不可分割的最小单位
• 数据对象：具有相同性质的数据元素的集合
• 数据类型：一个值的集合和在此集合上的一组操作的总称，包括三种
  • 原子类型：不可拆分
  • 结构类型：可再拆分
  • 抽象数据类型：抽象数据组织与之相关的操作
• 数据结构：相互之间有关系的数据元素集合，关系称为结构，包括三方面：
  • 逻辑结构：从逻辑上描述数据，无存储
    • 线性结构：数组、栈、队列，一对一的关系
    • 非线性结构：集合、数、图，多对多的关系
  • 存储结构：数据结构在计算机中的表示
    • 顺序存储：逻辑相邻，物理位置也相邻，随机存取；
    • 链式存储：逻辑相邻，物理位置不要求相邻，顺序存取；
    • 索引存储：存储元素+索引表(索引项和地址)，删除时要删两处；
    • 散列存储：用关键词算出元素的存储地址，增删查改效率都快，存在hash冲突；
  • 数据的运算(操作)：
    • 运算的定义：针对逻辑结构，指出运算的功能；
    • 运算的实现：针对存储结构做出具体的操作步骤；

算法和算法的效率

• 算法是问题求解步骤的描述，有5个特性；
• 常见的渐进时间复杂度(从小到大)
  • 0(1) < O(logzn) < O(n) < O(nlog2n) < O(n²) < O(n3) < O(2^n) < O(n!) < o(n^n)
• 分析时间复杂度的两条规则：
  • 加法规则：取最大的时间
  • 乘法规则：两层循环就需要相乘，n * log2^n
• 算法的5个重要特性：
  • 有穷性：必须在指定步数后运行结束，每一步都在一定时间内完成；
  • 稳定性：对相同的输入得出相同的输出；
  • 可行性：基础运算执行用有限次数来实现；
  • 输入和输出：必须有输入和输出，而且二者有某种关系的量
• 好算法要达到的目标：
  • 正确性
  • 可读性
  • 健壮性
  • 高效率和低存储
• 算法效率的度量：
  • 时间复杂度
    • 语句的重复执行次数是频度，n是问题规模，频度之和记为T(n)
    • 算法的基本运算频度(最深层的循环语句)
    • O的含义是T(n)的数量级，T(n) = O(f(n))
  • 时间复杂度的三种情况：
    • 最坏时间复杂度：通常只考虑最坏情况下的时间复杂度
    • 最好时间复杂度
    • 平均时间复杂度
  • 空间复杂度
    • 算法运行时所耗费的存储空间S(n)，是问题规模n的函数，记为S(n) = O(g(n))
    • 耗费的存储空间包括：指令、常数、变量、实现计算的辅助空间；
    • 输入数据和算法无关，则按常量算O(1)；

2、线性表

知识框架-2

• 顺序存储：顺序表(数组实现)；
• 链式存储：指针实现(单链表、双链表、循环链表)，数组实现(静态链表)；
• 线性表是一种“逻辑结构”，表示元素之间是一对一的关系，顺序表和链表是指“存储结构”；

线性表的定义和基本操作

• 线性表定义：
  • 有相同数据类型的N个数据元素的有限序列；
  • 术语：表尾元素、表头元素、直接前驱、直接后驱；
  • 每个元素只有一个直接前驱(首元素除外)，每个元素只有一个直接后驱(最后一个元素除外)；
• 线性表的特点：
  • 元素个数有限
  • 表中元素有逻辑的顺序性，元素有先后次序
  • 表中元素都是数据元素，每个元素都是单个元素
  • 数据类型都相同，每个元素占相同大小的存储空间
  • 表中元素具有抽象性，仅讨论元素的逻辑关系，不考虑元素的内容
• 线性表的基本操作：
  • 基本操作是最核心的，其它复杂操作通过调用基本操作来完成；
  • InitList(L)，构造一个空的线性表
  • Length(L)
  • LocateElem(L, e)，按值查找
  • GetElem(L, i)，按位查找
  • ListInsert(&L, i, e)，在表中的i个位置插入元素e
  • ListDelete(&L, i, e)，删除表中的i个位置元素值，并返回e
  • PrintList(L)
  • Empty(L)
  • DestoryList(&L)，销毁线性表，释放所占用的内存

线性表的顺序表示

• 顺序表的定义
  • 用一组地址连续的存储单元依次存储数据元素；
  • 逻辑上相邻的元素，物理位置上也相邻
    • 位序（数组下标、游标）
  • 表中的任意一个数据元素都可以随机存取，存储结构称为随机存取的存储结构；
• 存储方式
  • 静态分配：适合固定大小的顺序表，例如学生表
  • 动态分配：分配空间大小在运行时动态决定，一旦空间占满，就开辟一块更大的空间，把原来空间的数据移到新空间来
  • 顺序表的存储密度高，每个节点只存储数据元素
  • 缺点：插入和删除需要移动后方元素位置
• 顺序表的基本操作的时间复杂度：
  • 插入操作
    • 最好情况O(1)，在表尾插入
    • 最坏情况O(n)，插入指定位置i，i之后的元素都要向后移动
    • 平均情况O(n)
  • 删除操作
    • 最好情况O(1)，删除的元素就在表尾
    • 最坏情况O(n)，删除指定位置i，i之后的元素都要向前移动
    • 平均情况O(n)
  • 按值查找
    • 最好情况O(1)，查找的元素就在表头
    • 最坏情况O(n)，查找的元素就在表尾，需要比较n次
    • 平均情况O(n)
  • *写代码实现这三种操作，用线性表的基本操作函数命名

线性表的链式表示

单链表

• 单链表的定义
  • 用任意存储单元来存储线性表中的数据元素；
  • 不要求逻辑上相邻的元素，物理位置上也相邻；
  • 通过访问地址建立起元素之间的逻辑关系，每个结点存放元素本身+指向后继的指针；
  • 不能随机存取，元素是离散地分布在存储空间中，单链表非随机存取的存储结构；
  • 用头指针来标识一个单链表，查找特定元素时，需要从表头开始遍历；
• 区分“头节点”和“头指针”
  • 头指针始终指向链表的第一个结点，不管带不带头节点；
  • 头节点是“带头节点”中链表的第一个结点，通常不存储信息；
  • 引入头节点的优点：
    • 数据结点的位置和逻辑结点的位置保持一致，操作时就无须特殊处理；
    • 空表和非空表的处理可以统一，不用单独针对头节点赋值写判断代码；
• 单链表的基本操作：
  • 用头插法建立单链表，将新结点插入到当前链表的表头
    • 这种方式不用记录需要插入的指针位置，但是链表中结点的次序和输入数据顺序不一致；
  • 用尾插法建立单链表，将新结点插入到当前链表的表头
    • 需要多建立一个始终指向链表尾结点的指针；
• 单链表的基本操作的时间复杂度：
  • 查找结点，按序号和按值都是O(n)
  • 插入结点时间复杂度是O(n)，具体操作是：
    • 找到待插入位置的前驱结点(i-1)，这个是查找操作时间复杂度是O(n)，
    • 将前驱结点的next指针指向插入节点，
    • 将原本这个位置的的节点指向插入结点的next指针；
  • 删除结点时间复杂度是O(n)，具体操作是：
    • 找到待删除结点的前驱结点(i-1)，这个是查找操作时间复杂度是O(n)，
    • 将前驱结点的next指针被删除节点的next指针，
    • 释放删除结点的存储空间free(q)
  • 获取表长度的时间复杂度是O(n)，需要遍历；
• 插入和删除的特殊操作，给点一个元素之后可以这样操作，
  • 特殊插入方式，交换数据，指向不变
    • 目标是新结点s插入到p结点前面，现在任然将s插入到p的后面，然后交换p和s的数据，这样也满足前后的逻辑关系；
    • 正常是找到待插入结点的前一个位置；
  • 删除一个节点也可以这样特殊操作
    • 删除给定节点，将当前结点下一个结点的数据和next节点都赋值给删除的节点；

双链表

• 单链表的定义：
  • 有两个指针，分别指向前驱结点(prior)和后继节点(next)；
  • 链变化的时候需要对prior指针做出修改；
  • 双链表的按值、按位查找时间复杂度也是O(n)；
  • 双链表可以方便的找到前驱结点，插入、删除的时间复杂度都是O(1)；
• 双链表的操作
  • 插入操作：
    • 在双链表中p结点后插入新结点s，需要改变p结点的next和p当前节点next的prior，步骤如下
    • p的next指向s的next
    • p的next的prior指向s
    • s的prior指向p
    • p的next指向s
  • 删除操作：
    • 删除双链表中p结点的后继结点q，步骤如下
    • p的next指向q的next
    • q的next的prior指向p
  • 创建操作
    • 也可采用单链表的头插法和尾插法

循环链表

• 循环单链表
  • 和单链表的区别是尾结点不是指向NULL，而改为指向头结点；
  • 获取链表长度时需要判断next是否指向头结点的指针；
  • 循环链表可以从表中的任意一个结点开始遍历整个链表；
  • 删除、插入操作和单链表几乎一样
    • 在表尾进行时，要让链表保持循环的属性；
    • 只是无需判断是否等于表尾；
• 循环双链表
  • 和循环单链表相似，唯一不同是头结点的prior指向表尾结点；
  • 循环双链表为空时，头结点prior和next都指向L；

静态链表

• 用数组来描述链式存储结构，结点也有数据域data和指针域next(和链表中的指针不同，是数组下标);
• 也需要预先分配一块连续的内存空间，和顺序表一样；
• 静态链表删除、插入操作和动态链表相同，只需要修改指针(数组下标);
• 静态链表用一个特殊数字标记表尾，例如把表尾的指针标记为-1；
• 用起来不方便，只在一些不支持指针的高级语言中使用

在实际应用中选取存储结构(从存储、操作、难易程度考虑)

• 难以估计存储长度和规模时选链表，不选顺序表；
• 只需要按元素位置访问数据时，选顺序表；
• 数据元素信息量较大时，需要频繁插入和删除操作时(动态性较强)，选链表；
• 容易实现时，选顺序表，高级语言都有数组，链表的操作是基于指针的；

3、栈、队列

知识框架-3

• 操作受限
  • 栈
    • 顺序栈
    • 链栈
    • 共享栈
  • 队列
    • 循环队列
    • 链式队列
    • 双端队列
• 推广
  • 数组
    • 一维数组
    • 多维数组：矩阵，稀疏矩阵，压缩存储

栈

• 栈的基本概念
  • 定义：是一种操作受限的线性表，只允许一端进行插入或删除(出栈)，栈顶、栈底、空栈，特点是后进先出；
  • 基本操作
    • InitStach(&S)
    • StachEmpty(S)：判断为空返回true，否则返回false；
    • Push(&S, x)：进栈
    • Pop(&S, &x)：出栈，非空就弹出栈顶元素，并用x返回；
    • GetTop(S, &x)：读出栈顶元素，如上；
    • DestoryStach(&S)
    • 做题时如题干未做出限制，则可直接使用这些基本的操作函数；
• 栈的存储结构
  • 顺序存储结构
    • 实现：结构体中两个数据元素，数组和top指针；
    • 基本运算：数据元素进栈top++，出栈top--
    • 共享栈：
      • 可以让两个顺序栈共享一个一维数组空间，两个栈底分别指向共享空间的两端，两个栈顶向共享空间的中间延伸；
      • top0=-1时，0号栈为空，top1=MaxSize时1号栈为空，当两个栈顶指针相邻时，判断栈满，0号栈进栈top0加1，1号栈进栈top1减1，出栈时则相反；
      • 存储时间复杂度均为O(1)，能更有效的利用存储空间，注意栈溢出的情况；
  • 链式存储结构
    • 采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈溢出的情况，通常采用单链表实现；
    • 并规定所有操作都是在单链表的表头进行的，这里规定链栈没有头结点，对于带头和不带头结点的链栈，具体的实现会有所不同；
    • 便于插入和删除，链栈的操作与链表类似，入栈和出栈的操作都在表头进行；

队列

• 队列的基本概念
  • 定义：也是一种操作受限的线性表，只允许一端插入，而在另一端删除，有入队和出队两个操作，队头、队尾、空队列，特点是先进先出；
  • 基本操作
    • InitQueuq(&Q)
    • QueuqEmpty(Q)：判断为空返回true，否则返回false；
    • EnQueue(&Q, x)
    • DeQueue(&Q, &x)：出队，非空就删除对头元素，并用x返回；
    • GetHead(Q, &x)：读对头元素，如上；
• 队列的存储结构
  • 顺序存储结构
    • 顺序存储
      • 数组，设两个指针，对头指针front指向对头元素，队尾指针rear指向队尾元素的下一个位置；
      • 进队，队不满时，先送值到队尾元素，再将队尾指针加1；
      • 出队，队不空时，先取出队头元素，再将队头指针加1；
      • 判空，Q.front==Q.rear==0成立，则队列为空；
      • 队满，不能用Q.rear=MaxSize作为队列满的条件，可以加一个字段记录队列中元素的个数；
    • 循环队列
      • 把存储队列元素的表从逻辑上视为一个环，称为循环队列，利用取模法(%)来实现，当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0；
      • 初始时:Q.front=Q.rear=0
      • 队首指针进1：Q.front = (Q.front+1)%MaxSize，例如：(0+1)%10=1，(9+1)%10=0；
      • 队尾指针进1: Q.rear=(Q.rear+1)%MaxSize；
      • 队列长度：(Q.rear+MaxSize-Q.front)%qMaxSize；例如：(9+10-1)%10=8；
      • 出队入队时：指针都按顺时针方向进1，像一个圆一样循环的转；
      • 队空条件：队空的条件是，队满时Q.front==Q.rear。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针；
      • 队满条件：(Q.rear+1)%MaxSize=Q.front，例如：(9+1)%10=0，空一个位置，表示队满；
      • 队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize，例如：(6-3+10)%10=7；
      • 为了区分是队空还是队满的情况，有三种处理方式:
        • 1 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“对头指针在队尾指针的下一个位置作为队满标志”；
        • 2 类型中增设表示数据个数的数据成员size；
        • 2 类型中增设tag数据成员，用以区分是队满还是空，0空1满；
• 队列的链式存储结构
  • 队列的链式表示称为链队列，实际上是带有队头指针和队尾指针的单链表；
  • 不带头结点的链式队列在操作上比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了；
  • 用单链表表示的链式队列特别适合于数据元素变动比较大的情形。如果程序中要使用多个队列与多个栈的情形，最好使用链式队列；
• 双端队列
  • 无限制的双端队列：
    • 指两端都可以进行入队和出队的操作的队列，队列两端分别称为前端和后端，逻辑结构仍是线性结构；
    • 在进队时，前端进的元素排在队列中后端的元素的前面，后端进入的元素排在队列中前端进的元素的后面，
    • 在双端队列出队时，无论前后端出队，先出的元素排在后出的元素前面；
  • 受限的双端队列：
    • 输出受限的双端队列：允许在一端插入和删除，但在另一端只允许插入的双端队列；
    • 输入受限的双端队列：允许在一端插入和删除，但在另一端只允许删除的双端队列；
    • 一般会考受限的双端队列可能输出的N中情况：例如输入序列为1,2,3,4，如何分别从两端输入一端输入得到3,1,2,4或4,1,2,3等等，输入要按照给的序列来；

栈和队列的应用

• 栈在括号匹配中的应用

  • 1 初始设置一个空栈，顺序读入左括号入栈；
  • 2 若是右括号，则使用栈顶的左括号消解，或是不合法的情况(括号序列不匹配，退出程序)；
  • 3 若是左括号，则作为一个新的更急迫的期待压入栈中。算法结束时，栈为空，否则括号序列不匹配；

• 栈在表达式求值中的应用

  • 后缀表达式(逆波兰式)：
    • 运算符在操作符的后面，已经考虑了运算符的优先级，没有括号，只有操作树和运算符；
    • 顺序扫描表达式的每一项，然后根据它的类型做如下相应操作：
      • 手算：
        • 1 先确定中缀表达式中各个运算符的运算顺序，按左优先原则确定运算次序，标记处1、2、3的顺序；
        • 2 选择下一个运算符，按照[左数、右数、运算符]的方式组合成一个新的操作数；
        • 3 如果有运算符没被处理，就继续步骤2
        • 例如：中缀：a+b、a+b-c、a+b-cd，转成后缀：ab+、ab+c-、ab+cd-，转成前缀+ab、-+abc、-+ab*cd；
        • 注意：一种中缀表达式对应一个后缀表达式，确保算法中的确定性；
      • 机算：
        • 从左往右扫描，该项是操作数，则将其压入栈中，若该项是操作符，连续从栈中退出两个操作数x和y，让这两个合体为一个操作数;
        • 形成运算指令 X<op>Y，并将计算结果重新压入栈中，扫描完后，栈中存放的就是最后的计算结果表达式；
        • 例如：ABCD-*+EF/-求值的过程需要12步(89页)；
  • 前缀表达式(波兰式)：
    • 运算符在操作符的前面，已经考虑了运算符的优先级，没有括号，只有操作树和运算符，从右往左扫描；
    • 除了扫描顺序和表达式在操作数前面外，其它和后缀表达式一样；
  • 中缀表达式：这种是人能看懂的，可以和前、后缀表达式互换，依赖运算符的优先级，还要处理括号；
  • 中缀表达式的计算(用栈实现)：
    • 初始化两个栈，操作数栈和运算符栈；
    • 扫描到操作数，压入操作数栈；
    • 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈；
    • 若碰到运算符，压入运算符栈，同时在操作数栈弹出两个操作数和这个运算符执行相应运算符，运算结果再压回操作数栈，如此循环直到处理完成(王道视频)；

• 栈在递归中的应用

  • 在调用过程总，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归过多容易造成栈溢出；
  • 递归算法也可以转换成非递归算法，通常需要借助栈来实现这种转换，或者while这是好结束条件；

• 队列在层次遍历中的应用

  • 把当前层或当前行按处理顺序安排好，等当前行处理好之后就可以处理下一层。使用队列是为了保存下一步的处理顺序；
  • 二叉树的层次遍历就是用一个辅助队列入队和出队处理的，图的遍历也是差不多；

• 队列在计算机系统中的应用

  • 用队列解决主机与外部设备之间速度不匹配的问题，设置一个打印数据缓冲区，把主机要打印的先数据写入缓冲区，打印机从缓冲区取数据；
  • 解决由多用户引起的资源竞争问题，过个进程同时提出占用CPU的请求，操作系统按照一定规则把他们排成一个队列，每次让队首的经常使用CPU；

数组和特殊矩阵

• 数组的定义：每个数据元素称为一个数组元素，数组下标的取值范围称为数组的维界；
• 数组的存储结构：
  • 一维数组：
    • 在内存中占用一段连续的存储空间；
  • 二维数组的存储有两种方式，按行优先和按列优先
    • 按行优先的基本思想是：先行后列，先存储行号小的元素，行号相等先存储列号较小的元素；
    • 按列优先：先列后行，先存储列号小的元素，列号相等先存储行号较小的元素；
    • 在内存中也是连续的，用行列号取数据；
• 特殊矩阵的压缩存储
  • 压缩存储：多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节约内存；
  • 特殊存储：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分部有一定规律性的矩阵；
  • 特殊存储的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分部规律，把那些呈现规律性分部的、值相同的多个矩阵元素压缩存储到一个存储空间中；
  • 常见的三种特殊矩阵：
    • 对称矩阵：
      • 若对一个n阶矩阵A中的任意一个元素Aij都有Aij=Aji，则称其为对称矩阵；
      • 其中的元素可划分为3个部分：上三角区、主对角线和下三角区。上下三角区的所有元素都互相对应，用一维数组存储可以节省几乎一半的空间；
      • 考虑好存取的对应规则，判断取的是上三角区区域数据时的转换过程；
    • (上下)三角矩阵
      • 上下三角区中所有元素均为同一常量，其存储思想与对称矩阵类似，不同之处在于存储完下三角和主对角线上的元素之后，紧接着存储对角线上方的常量一次；
      • 只需标记n(n+1)/2区域内的值从一个固定数组下标中取常数项就行；
    • 三对角矩阵
      • 三对角矩阵也称为带状矩阵，对一个n阶矩阵A中的任意一个元素Aij，当|i-j|>1时，都有Aij=0(1小于等于i,j小于等于n)，则称为三对角矩阵；
      • 所有的非零元素都集中再以主对角线为中心的3条对角线的区域，其他区域的元素都为0；
      • 采用压缩存储，将三对角线上的元素按行优先方式存放在一维数组中；
  • 数组下标如果题目中没有特殊说明从1开始，则应该灵活应对；
• 稀疏矩阵
  • 三个字段标记稀疏矩阵中的数据，行数、列数、数据组成一个结构体，放在一维数组中，其余没有数据的位置用一个常量值存储以此来节省内存；
  • 仅存储非零元素，但通常非零元素的分布没有规律，将非零元素构成一个三元组(行标、列标、值)。按这种方式储存后便失去了随机存取特性；
• 矩阵：
  • 矩阵在计算机图形学、工程计算中经常使用；
  • 在数据结构中仅考虑如何用最小的内存空间来存储同样的一组数据，并能方便的提取矩阵中的元素，不涉及矩阵研究及其运算等；

4、串(字符串) -不考

知识框架-4

• 基本概率：主串、子串、串长
• 存储结构：定长顺序存储、堆分配存储、块链存储
• 模式匹配算法：
  • 暴力匹配法
  • KMP算法
    • 部分匹配值表
    • next数组
    • next函数的推理过程
  • KMP算法的改进：nextval数组

5、树与二叉树

知识框架-5

• 数的结构
  • 三种树
    • 树
    • 森林
    • 二叉树
      • 存储结构
      • 四种遍历
        • 深度优先：前、中、后序遍历
        • 广度有线：层序遍历
      • 应用
        • 哈夫曼树
      • 二叉树的种类
        • 满二叉树
        • 完全二叉树
        • 线索二叉树(带前驱、后继)
        • 最优二叉树(哈夫曼树)
• 树和二叉树的性质
  • 遍历操作
  • 相互转换
  • 存储结构
  • 操作特性

树的基本概术

• 树的定义

  • n个结点的有限集合，n = 0 时称为空树；
  • 只有一个特定的根结点
  • n > 1时，其余结点可以看做是互不相交的有限集合，可以称为根的子树；
  • 树是一种递归的数据结构，也是一种分层的逻辑结构，有两个特点：
    • 树的根结点没有前驱，其它结点都只有一个前驱(父结点的直接关系)；
    • 树中的所有结点都有零个或多个后继(子女结点的直接关系)；
  • n个结点的树有n-1条边；

• 基本术语

  • 叶子结点到根节点之间唯一路径上的结点，都称作叶子结点的祖先结点，祖先结点称叶子结点为子孙结点；
    • 祖先结点
    • 子孙结点
    • 双亲结点
    • 兄弟结点：有相同双亲结点的称为兄弟；
    • 堂兄弟结点：有相同根结点；
  • 度：树中孩子节点个数称为这个结点的度，树中结点最大的度称为“树的度”，这个度指的是几叉树；
  • 分支结点：树中度大于0的结点称为“分支结点”
  • 叶子结点：度为0(没有子女结点)
  • 结点深度、高度的区别
    • 结点深度：从根结点开始，自顶向下逐层累加；
    • 结点高度：从叶子节点开始，自底向上逐层累加；
    • 树的高度、深度，和上面两个概念一样；
  • 有序树和无序树
    • 有序树：树中各结点从左到右是有序的，不能互换；
    • 无序树：结点没有顺序，子结点位置可以互换；
  • 路径和路径长度
    • 路径：两个结点之间经过的所有结点序列；
    • 路径长度：路径上所经过的边的个数；
    • 树中的分支路劲是从上向下的，兄弟结点之间不存在路径，只有子孙结点有路径；
  • 森林：M棵互不相交的树的集合，和树的概念相近，把树的根结点删掉就成了森林，树和森林之间可以互相转换；

• 树的性质

  • 度为m的树中第i层上最多有m^i-1个结点，度=4，i=3, 4 * 4 = 16；
  • 高度为h的m叉树最多有((m^h)-1)/(m-1)个结点，h=3，m=3，(27-1)/2 = 13；
  • 具有n个结点的m叉树的最小高度为logm(n(m-1)+1);

二叉树

• 二叉树的概念

  • 二叉树的主要特征：
    • 二叉树的定义
      • 每个结点最多只有两颗子树，子树有左右之分，次序不能任意颠倒；
      • 二叉树是有序树，若将左右子树颠倒，将变成另一颗二叉树；
      • 二叉树也以递归的形式定义，即使树中只有一个结点也要区分它是左子树还是右子树；
      • 或者由一个根节点和两个互不相交的子树构成左子树和右子树分别是一颗二叉树；
      • 二叉树的5种形式
      • 空二叉树、只有根节点、只有左子树、只有右子树、左右子树都有；
      • 二叉树与度为2的有序树的区别：
        • 度为2的树至少有3个结点，而二叉树可以为空；
        • 度为2的有序树的孩子左右次序是相对另一个孩子而言的，某个结点只有一个孩子结点时，不用对比父结点区分左右次序，二叉树必须确定左右次序；
    • 几种特殊的二叉树
      • 满二叉树
        • 一颗高度为h，且有(2^h)-1个结点的二叉树称为满二叉树；
        • 除叶子结点外每个结点度数都为2；
        • 按数组表示满二叉树时，可以用[i/2]找到父结点，左孩子为2i，右孩子为2i+1，非叶子结点主要集中在数组前半部分；
      • 完全二叉树
        • 满二叉树肯定是完全二叉树，相对于满二叉树缺失最下层最右边的一些叶子节点；
        • 高度为h，有n个结点的二叉树，且当其每个结点都与高度为h的满二叉树中编号为1-n的结点一一对应时，称为完全二叉树；
        • 结点i小于[n/2]，则结点i为分支结点，否则为叶子结点；
        • 叶子结点只可能在层次最大的两层上出现，对于最大层次中的叶子结点，都依次排在该层最左边的位置上；
        • 若有度为1的结点，则只可能有一个，且该结点只有左孩子；
        • 若结点层序编号后，一旦出现某结点i为叶子结点或只有左孩子，则编号大于i的节点都是叶子节点(125页)；
        • 若全部结点n为奇数，则每个分支都有左右孩子节点，n为偶数，则编号最大的分支只有左子树；
      • 二叉排序树
        • 左子树上所有结点的关键字都小于根节点的关键字，右子树上所有结点关键词都大于根结点，左右子树也是一颗二叉排序树；
      • 平衡二叉树
        • 树上任意一个结点的左子树和右子树的深度之差不超过1；
        • 满二叉树和完全二叉树都是平衡二叉树；
    • 二叉树的性质
      • 非空二叉树上的叶子节点数量等于度为2的结点数加1，既n0 = n2 + 1，n0是叶子结点，n2是度为2的结点;
      • 拓展到任意一棵结点数量为n的树，则边的数量为n-1;
      • 高度为h的二叉树，最多有(2^h)-1个结点，等比数列求和的结果，用性质2求前h项的和；
      • 非空二叉树的第k层上，最多有(2^k)-1个结点，同上；
      • 完全二叉树找父子结点的方法：
        • 当2i小于等于n时，结点i的左孩子为2i，否则无左孩子
        • 当2i+1小于等于n时，结点i的左孩子为2i+1，否则无右孩子；
        • 节点i所在的层次(深度)为[log2i]+1；
        • 具有n个结点的完全二叉树层次(深度)为[log2n]+1；
        • 当i为偶数时，父节点为2i，i是父结点的左孩子，当i为奇数时，父节点为(i-1)/2，i是父结点的右孩子；
  • 二叉树的存储结构
    • 顺序存储
      • 完全二叉树和满二叉树用顺序存储比较合适，树中的结点序号可以唯一的反映结点之间的逻辑关系，用数组元素下标就可以确定结点在二叉树中的位置；
      • 对于一般的二叉树，需要用数组下标反应结点之间的逻辑关系，数组中的有些位置会为空值，空间利用率低，高度为h的二叉树需要占用(2^h)-1个存储单元；
      • 存在数组时，建议从数组下标1开始存储数的节点，这样方便计算父子节点在数组中的位置，少写减1的代码；
    • 链式存储
      • 二叉树一般用链表结点来存储二叉树中的每个结点，结点结构通常包含3个三个域，1个数据域(data)、左右子树指针各1个(lchild,rchild)；
      • 在实际应用场景中，还可以增加指向父结点的指针，变长三叉链表存储结构；
    • 选择合适的存储结构
      • 用不同的存储结构时，实现二叉树操作的算法也会不同，二叉树的形态和需要进行的运算；

• 二叉树的遍历

  • 遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列；
  • 遍历是按某条搜索路径访问树中的每个结点，使每个结点都被访问一次，仅被访问一次，按照先遍历左子树后右子树的原则，有以下几种方法
    • 三种遍历中，递归遍历左、右子树的顺序都是固定的(visit)，只是访问根节点的顺序不同，时间复杂度都是O(n)，空间复杂度也是O(n)；
      • 把前中后序遍历当作模板来记忆，很多题目都是基于这三个模板延伸出来的，这三种遍历去掉visit，遍历算法完全相同；
      • 先序遍历
        • 1访问根结点、2访问左子树、3访问右子树，PreOrder；
      • 中序遍历
        • 1访问左子树、2访问根结点、3访问右子树，左子树有子节点时会先输出子节点的左根右3个值，InOrder；
      • 后序遍历
        • 1访问左子树、2访问右子树、3访问根结点，左右子树有子节点时会先输出子节点的左右根3个值，PostOrder；
    • 递归算法和非递归算法的转换
      • 借助栈来遍历二叉树，示例中序遍历：
        • 沿着左子树依次入栈，直到左子树为空说明找到可以输出的结点了，每输出一个结点后都检测是否有右子树，有则将右子树入栈后继续栈的输出；
      • 先序遍历：
        • 和中序遍历的思路类似，只需要把访问结点操作放在入栈操作的前面；
      • 后序遍历：
        • 从根节点开始，沿着左子树依次入栈，直到左子树为空，但此时还不能出栈，
        • 还需要将右子树按照相同的规则将右子树入栈，想要出栈，要么右子树为空，要么右子树刚被访问完(此时左子树早已访问完)，136页；
    • 层序遍历
      • 要借助一个队列，首先将根结点入队后出队，出队时检测结点，将结点的左右子树入队，如此反复，直至队列为空；
      • 将二叉树层序遍历作为一个模板，才能应用于各种题目之中；
  • 二叉树的遍历是基础操作，在遍历过程中可以对结点进行各种操作，例如：
    • 对一颗已知树求结点的父结点；
    • 求结点的孩子结点；
    • 求二叉树的深度；
    • 求二叉树的叶子节点个数；
    • 判断两颗二叉树是否相等；
  • 由遍历序列构造二叉树(根据遍历后的结果还原成原本的二叉树)
    • 由先序遍历和中序遍历可以唯一确定一颗二叉树：
      • 在先序遍历结果中，第一个结点一定是二叉树的根结点，在中序遍历中，根节点必然在将中序序列分成两个子序列，
      • 1左2右子树的序列，根据这两个子序列，在先序序列中找到对应的左右子序列，在先序序列中，左右子序列的第一个结点分别是左右子树的根节点，
      • 如此递归，便能唯一地确定这颗二叉树
    • 由后序遍历和中序遍历可以唯一确定一颗二叉树：
      • 后序序列的最后一个结点如同先序序列的第一个结点，可以将中序序列分隔成两个子序列，采用如上类似的方法递归的进行划分就可以得到一颗二叉树；
    • 由层序遍历和中序遍历可以唯一确定一颗二叉树：
      • 根据遍历算法的特性思考一下；
    • 只知道二叉树的先序遍历和后序序列，无法唯一确定一颗二叉树；

• 线索二叉树

  • 基本概念
    • 传统的二叉链表存储仅能体现父子关系，不能直接得到结点在遍历中的前驱和后继；
    • n个结点的二叉树中有n+1个空指针，这是因为每个叶子结点都有两个空指针，把这些空指针利用起来，用于加快查找结点前驱和后继；
    • 在每个结点中增加两个标志域，用来指向左(右)孩子或前驱(后继)，(lchild、rchild)，(ltag、rtag)，tag = 0表示结点有孩子，为1表示指向前驱；
    • 若无左子树，让lchild指向其前驱结点，无右子树，让rchild指向其后继结点，
    • 以这种二叉树的存储结构构成的二叉树称为线索链表，线索二叉树，可以像遍历单链表一样遍历二叉树；
  • 中序线索二叉树的构造
    • 前驱和后继信息只有在遍历的时候才能得到，线索二叉树的实质是遍历一次二叉树；
    • 增加指针pre和p，p是当前正在访问的结点，pre指向p的前驱，在中序遍历过程中：
      • 检测p的左指针是否为空，若为空就将p的左指针指向pre，
      • 再检查pre的右指针是否为空，若为空就将pre的右指针指向p；
    • 可以在线索二叉树上增加一个头结点，这就好比二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历：
      • 让lchild的指针指向二叉树的根结点，rchild指向中序遍历时访问的最后一个结点，
      • 再让中序序列中的第一个结点lchild指针和最后一个结点rchild指向头结点。
  • 中序线索二叉树的遍历
    • 先找到序列中的第一个结点，然后依次找到结点的后继，直到其后继为空；
    • 在中序线索二叉树中找结点后继的规律是：有标志为1则右链为线索，指向其中后继，否则遍历右子树中第一个访问的节点为其后继；
  • 先序线索二叉树
    • 和建立中序线索二叉树类似，只需变动线索化改造的代码和调用线索化左右子树递归函数的位置；
    • 在先序线索二叉树中找结点的后继：
      • 如果有左孩子，则左孩子就是其后继，如果无左孩子有右孩子，则右孩子就是其后继；
      • 如果是叶子结点，则右链域直接指向结点的后继；
  • 后序线索二叉树(这个有点特殊)
    • 和建立中序线索二叉树类似，只需变动线索化改造的代码和调用线索化左右子树递归函数的位置；
    • 找后继分三种情况
      • 若结点x是二叉树的根，则其后继为空
      • 若结点x是父结点的右孩子，或x的父结点的左孩子且其父结点没有右子树，则其后继为父结点；(140页)
      • 若结点x是父结点的左孩子，且父结点有右子树，则其后继为父结点的右子树上按后续遍历列出的第一个结点；
      • 在后序线索二叉树上找后继需要知道结点的父结点，既需要采用带标志域的三叉链表作为存储结构

数和森林

• 树的存储结构：有顺序和链式存储，不管采用哪一种存储都要求能唯一的反映出各结点之间的逻辑关系；
  • 双亲表示法
    • 采用一组连续空间来存储每个结点，同时在每个结点中增加一个伪指针指向其父结点在数组中的位置；
    • 可以很快的找到结点的父结点，但找孩子结点时要遍历整个数组
  • 孩子表示法
    • 将每个结点的孩子结点都用单链表链接起来形成一个线性结构，有n个结点就有n个孩子链表，叶子结点的链表为空；
  • 孩子兄弟表示法
    • 这种存储表示比较灵活：
      • 优点：最大优点是可以方便地实现转换为二叉树的操作，易于查找结点的孩子结点；
      • 缺点：从当前结点查找其父结点比较麻烦，若为每个结点增加一个parent域指向父结点，则就没有这个麻烦了；
    • 孩子兄弟表示法就是二叉树表示法，用二叉链表作为树的存储结构，每个结点包含三个内容：
      • 结点值
      • 结点指向第一个孩子结点的指针
      • 以及指向结点下一个兄弟结点的指针(沿此域可以找到结点的所有兄弟结点)
• 树和二叉树在顺序存储上的区别：
  • 树的存储结构中，数组下标只代表结点编号，下标中的内容指示结点之间的关系；
  • 二叉树的存储结构中，数组下标既代表了结点的编号，又指示了二叉树各结点的关系；
  • 二叉树属于树，因此二叉树都可以用树的存储结构来存储，但反过来却不行；
• 树、森林、二叉树的转换
  • 由于树和二叉树都可以用二叉链表作为存储结构，因此用二叉链表作为媒介可以导出树与二叉树的对应关系；
  • 给定一棵树，可以找到唯一的一颗二叉树与之对应，从物理结构上看，他们的二叉链表是相同的，只是解释不同；
  • 树转换成二叉树的规则：
    • 每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则称为左孩子右兄弟；
    • 由于根节点没有兄弟，所以对应的二叉树没有右子树；
  • 树转换成二叉树的画法：
    • 在兄弟结点之间加一根连线，对每个结点只保留它与第一个孩子的连线，以树根为轴心顺时针旋转45度；
  • 森林转换成二叉树的规则：
    • 与树转换成二叉树的规则类似，先将森林中的每棵树转换成二叉树，由于树转换成二叉树之后右子树为空，
      • 可以将第二课树对应的二叉树当作第一颗二叉树根的右子树，将第三课树对应的二叉树当作第二颗二叉树的右子树，
      • 以此类推就可以将森林转换为二叉树；
    • 森林转换成二叉树的画法：
      • 每棵树的根可视作兄弟关系，在每棵树的根之间加一根连线，以第一棵树的根为轴心顺时针旋转45度；
  • 二叉树转换为森林的规则：
    • 非空二叉树，则二叉树的根及其左子树为第一颗树的二叉树形式，将根的右子树链接断开，
      • 二叉树根的右子树又可视为一个由第一颗树外的森林转换后的二叉树，
      • 应用同样的方法，直到最后只剩一颗没有右子树的二叉树为止，最后依次将每颗二叉树转换成树，就得到了森林；
• 树和森林的遍历
  • 树的遍历，访问树中的每一个结点，主要有两种方式：
    • 先根遍历：
      • 若树非空，先访问根结点，再依次遍历根结点的每颗子树，遍历子树时仍然遵循先根后子树的规则，其遍历序列与这棵树的二叉树的先序序列相同；
    • 后根遍历：
      • 若树非空，先依次遍历根结点的每颗子树，再访问根结点，遍历子树时仍然遵循先子树后根的规则，其遍历序列与这棵树的二叉树的中序序列相同；
    • 树也有层序遍历，与二叉树的层序遍历基本相同，按层次依次访问各结点；
  • 森林的遍历，按照森林和树相互递归的定义，森林也有两种遍历方法
    • 先序遍历森林：
      • 若森林非空，先访问森林中第一棵树的根结点，先序遍历第一颗树中根结点的子树森林，先序遍历除去第一颗树之后剩余的树构成的森林；
    • 中序遍历森林
      • 若森林非空，先访问森林中第一棵树的根结点的子树森林，访问第一颗树的根结点，中序遍历除去第一颗树之后剩余的树构成的森林；
    • 森林的先序和中序遍历是其对应二叉树的先序和中序遍历
      • 因为森林转换成二叉树时，其第一颗子树转换成左子树，森林中剩余的树转换成右子树；
• 树、森林、二叉树遍历关系
  • 二叉树的先序遍历对应：树的先根遍历、森林的先序遍历
  • 二叉树的后序遍历对应：树的后根遍历、森林的后序遍历(中序遍历)

树和二叉树的应用

• 哈夫曼树(带权二叉树)和哈夫曼编码
  • 哈夫曼树的定义
    • 树中的结点被赋予某种意义的数值，称为该结点的权值；
    • 从树根到任意结点的路径长度与该结点上权值的乘积(路径长度为2，权值为7)，称为该结点的带权路径长度(为14)；
    • 树中所有叶子结点的带权路径之和称为该树的带权路径长度；weight path length
    • 带权结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称“最优二叉树”；权值越低，到根结点的层级越高；
    • 带权路径长度计算规则，WPL = 72 + 52 + 22 + 42 = 36，这是一颗高度为3的二叉树，叶子结点权值为 7、5、2、4
  • 哈夫曼树的构造
    • 给定n个权值分别为w1,w2...wn的结点，构造哈夫曼树的算法如下：
      • 1、将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F
      • 2、构造一个新结点，从F中选取两颗根结点权值最小的树作为新结点的左、右子树，将新结点的权值置为左右子树上根结点的权值之和；
      • 3、从F中删除刚才选出这两个结点，同时将这两个结点构成的树加入到F中；
      • 重复步骤2和3，直到F中只剩下一棵树为止；
  • 哈夫曼树的特点
    • 每个初始结点最终都成为叶子结点，且权值越小的结点到根结点的路径越长度越大；
    • 构造过程中新建了n-1个结点(双分支结点)，因此哈夫曼树的结点总数为2n-1；
    • 每次构造都选择2棵树作为新结点的孩子，因此哈夫曼树中不存在度为1的结点
  • 哈夫曼编码
    • 固定长度编码：每个字符以相等长度的二进制位表示
    • 可变长度编码：每个字符以不等长度的二进制位表示，可变长度编码比固定长度编码要好得多；
    • 对频率较高的字符以短编码，而对频率较低的字符以较长一些的编码，从而使字符的平均编码长度缩减，起到压缩的效果；
    • 哈夫曼编码是一种被广泛应用且非常有用的数据压缩编码；
    • 前缀编码：没有一个编码是另一个编码的前缀；
    • 用哈夫曼编码可以设计出总长度最短的二进制前缀编码；
  • 由哈夫曼树构造哈夫曼编码
    • 将出现的字符当做一个独立的结点，其权值为它出现的次数，所有的字符结点都出现在叶子结点中；
    • 将字符编码解释为从根结点到该字符的路径上边标记的序列，其中边标记为0表示转向左孩子，标记为1表示转向右孩子；

6、图

知识框架-6

• 图
  • 图的定义
  • 图结构的存储
    • 邻接矩阵法、邻接表法
    • 邻接多重表、十字链表
  • 图的遍历
    • 深度优先遍历
    • 广度优先遍历
  • 图的相关应用
    • 最小生成树：Prim算法、Kruskal算法
    • 最短路径：Dijkstra算法、Floyd算法
    • 拓扑排序：AOV网
    • 关键路径：AOE网

图的基本概念

• 图的定义
  • 定义：图G由顶点集V和边集E组成，记为G =（V,E），用|V|表示图中顶点的个数，用|E|表示图中顶点的边数；
  • 1 有向图：有向边，若E为有向边的有向集和时，v邻接到w，称为从v到w的弧(边)，v指向w;
  • 2 无向图：无向边，若E为无向边的有向集和时，则称图为无向图，v和w互为邻接点，称边v和w相关联；
  • 3 简单图、多重图：
    • 简单图：不存在重复的边，不存在顶点到自身的边；
    • 多重图：图中两个顶点之间的变数大于1条，又允许顶点通过一条边和自身关联；
    • 简单图和多重图的定义是相对的，数据结构中仅讨论简单图；
  • 4 完全图（简单完全图）：
    • 无向完全图：有n(n-1)/2条边的无向图称为完全图，在完全图中任意两点之间都存在边。
    • 有向完全图：有n(n-1)条边的有向图称为有向完全图，在有向完全图中任意两点之间都存在方向相反的两条弧，a->b,b<-a。
  • 5 子图：
    • 子图：两个图G=(V,E)和G2=(V1,E2)，V1和E2是V和E的子集，则称G2是G的子图；
    • 生成子图：若有V(G2)=V(G)的子图G，则称G2是G的生成子图；
  • 6 联通、连通图和联通分量
    • 联通：在无向图中，若从顶点v到顶点w有路径存在，则称v和w是联通的；
    • 连通图：若图G中任意两个顶点都是联通的，则称图G为联通图，否则称为非联通图(图有n个顶点，边数小于n-1，此图必是非连通图)；
    • 联通分量：指的不相连的图，无向图中的极大联通子图称为联通分量，例如图有三个顶点，且有三条边连接，则称图G有3个联通分量(189页)；
  • 7 强联通图、强联通分量
    • 强联通图：在有向图中，顶点v到w都有路径，则称这两个顶点是强联通的，若图中任意一对顶点都是强联通的，则称此图是强连通图；
    • 强联通分量：在有向图中的极大强连通子图称为有向图的强连通分量
    • 在有向图中讨论强连通性，在无向图中讨论连通性；
  • 8 生成树、生成森林
    • 连通图的生成树是包含图中全部顶点的一个极小联通子图，若图中有n个顶点，则它的生成树有n-1条边，
    • 包含图中全部顶点的极小联通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非联通图；
    • 在非联通图中，联通分量的生成树构成了非连通图的生成森林；
    • 区分极大连通子图和极小联通子图
      • 极大连通子图是无向图的连通分量，极大既要求该联通子图包含其所有的边；
      • 极小联通子图是既要保持图的连通性，又要使得边数最少的子图；
  • 9 顶点的度、入度和出度
    • 在无向图中，
      • 顶点v的度是指依附于顶点v的边的条数，记为TD(v)，n个顶点，e条边的无向图为2e，
      • 无向图全部顶点的度的和等于边数的2倍，每条边和两个顶点项关联；
    • 在有向图中：
      • 顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，出度是以顶点v为起点的有向边的数目，顶点v的度等于入度+出度；
      • 有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点，记为TD(v) = ID(v) + OD(v)；
  • 10 边的权和网：图中每条边都可以标记具有某种含义的数值，该数值称为该边的权值，这种边上带有权值的图称为带权图，也称网；
  • 11 稠密图、稀疏图
    • 边数很少的图称为稀疏图，反之称为稠密图，稠密图和稠密图是相对而言的，一般当图G满足|E| < |V|log|V|时， 称图为稀疏图；
  • 12 路径、路径长度和回路
    • 路径：顶点到顶点之间的一条路径；
    • 路径长度：路径上边的数目称为路径长度；
    • 回路：第一个顶点和最后一个顶点相同的路径称为回路或环，若一个图有n个顶点，并且边大于n-1条边，则此图一定有环。
  • 13 简单路径、简单回路
    • 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径；
    • 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
  • 14 距离：两个顶点之间的最短路径若存在，则此路径的长度称为这两个顶点的距离，若两个顶点根本不存在路径，则记该距离为无穷（∞）；
  • 15 有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树；

图的存储和基本操作

• 要求：图的存储必须要完整、准确的反应顶点集和边集的信息，所选的存储结构应适应于待求解的问题；
• 邻接矩阵法
  • 用一个一维数组存储图中顶点的信息，再用一个二维数组存储图中边的信息(各顶点之间的邻接关系)，这个二维数组称为邻接矩阵；
• 邻接表法
  • 为图中的每个结点建立一个单链表，
• 十字链表
  • 十字链表是有向图的一种链式存储结构，在十字链表中，
• 邻接多重表
  • 邻接多重表是无向图的另一种链式存储结构，在十邻接表中，
• 图的基本操作，只需要掌握基本思想和实现步骤
  • 对于不同的存储结构，操作的具体实现会有着不同的性能，在实现时，应考虑用何种存储方式的算法效率更高；
  • 图的主要操作包括：
    • Adjacent(G, x, y)，判断图G是否存在边<x,y>或(x,y)，"<>"有向，“()”无向
    • Neighbors(G, x)，列出图G中与结点x邻接的边；
    • InsertVertex(G, x)，在图G中插入顶点x；
    • DeleteVertex(G, x)，从图G中删除顶点x；
    • AddEdge(G, x, y)，若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边；
    • RemoveEdge(G,x,y)，若无向边(x,y)或有向边<x,y>存在，则从图G中删除该边；
    • FirstNeighbor (G, x)，求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1；
    • NextNeighbor (G, x, y)，假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点 x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1；
    • Get_edge_value (G, x, y)，获取图G中边(x,y)或<x,y>对应的权值；
    • Set_edge_value(G, x, y, v)，设置图G中边(x,y)或<x,y>对应的权值为v。
• 存储结构之间的转化

图的遍历

• 图的遍历指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的顶点有且仅有一次的访问；

• 树是一种特殊的图，所以树的遍历实际也可以视为一种特殊图的遍历；

• 图的遍历是求解图的联通性问题，和求关键路径等算法的基础；

• 广度优先搜索

  • 搜索过程：
    • 和二叉树的层序遍历完全一样，首先访问起始顶点v，然后由v出发依次访问v的各个未访问过的邻接顶点，直到图中未被访问的邻接点都被访问为止；
    • 如果找到未被访问的顶点，则选择这个顶点作为起始点，重复上述步骤，直到图中所有的顶点都被访问为止，(这是有顶点不相邻的情况，类似于森林)；
    • 用一个辅助队列，起始点先入队，出队时把相邻的顶点都放入队列中，如此重复。Dijkstra单源最短路径和Prim最小生成树算法也应用了这样的思想；
    • 广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点。不像深度优先搜索那样有往回退的情况，因此它不是一个递归算法；
    • 辅助数组visited[]标记顶点是否被访问过，是个bool值，防止一个顶点被多次访问；
  • BFS算法的性能分析
    • 不看for的层级，只看顶点vertex和边edge的访问次数；
    • 空间复杂度：
      • 最坏情况：空间复杂度为O(|V|)，无论邻接表还是邻接矩阵的存储方式，BFS都需要借助一个辅助队列，n个顶点都需要入队一次；
    • 时间复杂度
      • 采用邻接表时：总的时间复杂度为O(|V|+|E|)，每个顶点都需要搜索一次时间为O(|V|) + 搜索任意一个顶点的邻接，每条边最少被访问一次时间为O(|E|)；
      • 采用邻接矩阵时：算法总的时间复杂度为O(|V|^2)，查找每个顶点的邻接时所需要的时间为O(|V|)，横纵相乘；
  • BFS算法的求解单源最短路径问题
    • 非带权图的顶点u到顶点v的最短路径公式为d(u,v)，是求u到v的任何路径中最少的边数。若u到v没有通路则d(u,v) = 无穷；
    • 使用BFS可以求解一个满足上述定义的非带权图的单源最短路径问题，由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定；
  • 广度优先生成树
    • 在遍历过程中得到的一颗遍历树，就称为广度优先生成树；
    • 用邻接表存储的图，生成的广度优先生成树是唯一的，用邻接表存储的图，广度优先生成树是不唯一的，因为邻接表存储次序表示不唯一；

• 深度优先搜索

  • 搜索过程：
    • 与树的先序遍历一样，基本思想是，首先访问图中某一起始顶点v，然后由v出发依次访问与v相邻且未访问过的任意邻接顶点，重复这个过程，
    • 当不能向下访问时，依次回退到最近被访问的顶点，如果还有未被访问的邻接顶点，则选择这个顶点作为起始点，重复上述步骤，
    • 直到图中所有的顶点都被访问为止(这是有顶点不相邻的情况，类似于森林)；
    • 也需要辅助数组visited[]标记顶点是否被访问过；
  • DFS算法的性能分析
    • 空间复杂度为：O(|V|)，DFS算法是一个递归过程，需要借助一个递归工作栈；
    • 时间复杂度为：和广度优先搜索完全一样，也是邻接表为O(|V|+|E|)，邻接矩阵为O(|V|^2)；
  • 深度优先的生成树和生成森林
    • 与广度优先搜索一样，搜索也会产生一颗深度优先生成树，当时，对连通图调用DFS生成的是树，不连通则是深度优先生成森林；
    • 与BFS一样，基于邻接表存储的深度优先生成树是不唯一的，邻接矩阵唯一；

• 图的遍历与图的连通性

  • 图的遍历算法可以用来判断图的连通性；
  • 对于无向图来说：
    • 若连通，则一次遍历就可以访问图中的所有结点,
    • 若不连通，则从某一个顶点出发，一次遍历只能访问到该顶点所有连通分量的所有顶点；
  • 对于有向图来说：
    • 若从初始点到图中的每个顶点都有路径，则能够访问到图中的所用顶点，否则不能访问到所有顶点；
  • 多个连通分量的处理情况
    • 添加第二个for循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点；
    • 对于无向图来说：调用BFS(G, i)或DFS(G, i)的次数等于该图的连通分量数；
    • 对于有向图来说：一个连通的有向图分为强连通和非强连通分量，一次调用BFS(G, i)或DFS(G, i)无法访问到该连通分量的所有顶点；

图的应用

• 最小生成(代价)树
  • 一个连通图的生成树包含图的所有顶点，并且只含有尽可能少的边；
  • Prim算法和Kruskal算法都是基于贪心的策略
  • 最小生成树的特性如下：
    • 对应边的权值之和是所有可能的路径中最小的；
    • 最小生成树的边数为顶点数减1，若无向联通图的边数比顶点本来就少1，既G本书是一颗树时，则G的最小生成树就是它本身；
    • 最小生成树不是唯一的，尽管树的边的权值之和可能都是最小的，走的路径不一样生成的树就不一样；
  • Prim(普里姆)算法
    • 普里姆算法是从顶点开始扩展最小生成树；
    • 构造最小生成树的过程如下：
      • 假设：G = {V,E}是连通图，其最小生成树是T = (U, Et)；
      • 初始化：向空树中添加图G的任意一个顶点u0，此时树中只包含有一个顶点，之后选择一个与当前顶点距离最近的顶点，依次类推，直到树中有n-1条边；
      • 循环：从图中选择满足(指定条件)且具有最小权值的边，加入树T中。(217页)
    • Prim的算法时间复杂度为O(|V|^2)，不依赖于|E|，因此它适用于求解边稠密的图的最小生成树；
  • Kruskal(克鲁斯卡尔)算法
    • 克鲁斯卡尔算法是一种按权值的递增次序，来选择合适的边来构造最小生成树的方法；
    • 构造最小生成树的过程如下：
      • 假设：G = {V,E}是连通图，其最小生成树是T = (U, Et)；
      • 初始化：图G的每个顶点构成一颗独立的树，初始时是无边的非连通图，每个顶点自成一个连通分量，按权值从小到大的顺序，T此时是一个仅含|V|个顶点的森林；
      • 循环(重复直至T是一棵树)：按G的边的权值递增顺序依次从森林中选择一条边，若这条边加入T之后不构成回路，则将其加入Et中，否则舍弃，直到树中有n-1条边；
      • 不断选取当前未被选取过且权值最小的边，选择一个后连通分量数减1，直到森林中所有顶点都在一个连通分量上；
      • 解释：一条边连接了两颗不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入到森林中，完成这两棵树的合并，直到森林合并成一棵树；
    • Kruskal的算法时间复杂度：
      • Kruskal算法采用堆来存放边的集合，因此每次选择最小权值的边只需O(log2|E|)的时间，可以采用并查集来描述T，从而构造T的时间复杂度为O(|E|log2|E|),
      • 克鲁斯卡尔算法适用于求解边稀疏而顶点较多的图；
• 最短路径
  • 主要思想：
    • 广度优先搜素算法查找最短路径只适用于无权图，带权图可用杰斯特拉、弗洛伊德算法；
    • 把从一个顶点到图中任意一个顶点的一条路径(可能不止一条)所经过边上的权值之后，定义为该路径的带权路径长度，最短那条称为最短路径；
    • 主要依赖的一种性质：两点之间的最短路径，也包含了路径上其他顶点间的最短路径。显然迪杰斯特拉算法也是基于贪心策略的；
    • 带权有向图的最短路径一般分为两类：
      • 单源最短路径：既求图中某一顶点到其他各项顶点的最短路径，可通过Dijkstra(迪杰斯特拉)算法求解；
      • 求每个顶点间的最短路径：可通过Floyd(弗洛伊德)算法来求解；
  • Dijkstra(迪杰斯特拉)算法求单源最短路径长度
    • 设置一个集合S记录已求得的最短路径的顶点，初始时把源点v0放入集合S，集合中每放入一个新顶点，都需要修改源点v0到集合中V-S中顶点当前的最短路径长度值；
    • 在构造的过程中设置两个辅助数组：
      • dist[]记录从源点到其它各个顶点当前的最短路径长度，初始状态为v0到vi各个顶点上自己边的权值，否则设置为∞无穷;
      • path[]表示从源点到顶点i之间最短路径的前驱结点，可以溯源这个数组里面的值得到源点v0到顶点vi的最短路径；
    • 迪杰斯特拉算法步骤如下：
      • pre：arch表示带权有向图，arcs[i][j]表示有向边<i,j>的权值，若不存在有向边<i,j>，则arcs[i][j]为∞；
      • 1 初始化：集合S初始值为{0}，dist的初始值为dist[i]=arcs[0][i],i=1,2...n-1的这个范围；
      • 2 从顶点集和V-S中选出vj，满足dist[j]的最短路径，vj就是当前求得的一条从v0出发的最短路径的终点；
      • 3 修改从v0出发到集合V-S上任意一点vk可达的最短路径长度，若dist[j]+ dist[j][k] < dist[k]，则更新dist[k]的值为前者；
      • 4 重复2-3操作共n-1次，直到所有的顶点都包含在S中；
      • 思考：Dijkstra(迪杰斯特拉)算法与Prim算法有何相似之处？
    • 性能分析：
      • 用邻接矩阵表示时，时间复杂度为O(|V|^2)；
      • 使用带权邻接表表示时，虽然修改的dist[]时间可以减少，单由于dist[]中选择最小分量的时间不变，时间复杂度为仍为O(|V|^2)；
    • 注意：边上带有负权值时，Dijkstra(迪杰斯特拉)的算法并不适用；
  • Floyd(弗洛伊德)算法求各顶点之间最短路径问题
    • 求所有顶点之间的最短路径问题描述：已知一个各边权值均大于0的带权有向图，求出vi与vj之间的最短路径和最短路径长度；
    • 弗洛伊德算法基本思想是：
      • 递推产生一个n阶方阵序列，A（-1到n-1），其中A^(k)[i][j]表示从顶点vi到顶点vj的路径长度，k表示绕行到第k个顶点的运算步骤；
      • 初始时，若vi到顶点vj它们之间存在边，则以此边的权值作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点k(0到n-1个顶点)作为中间顶点；
      • 若增加中间顶点后，检测到的路径比原来的路径长度减少了，则以此新路径代替原路径；
    • 执行过程如下：
      • pre：带权有向图G用邻接矩阵表示，用弗洛伊德算法求所有顶点之间的最短路径长度；
      • 初始化：方阵A^(-1)[i][j] = arcs[i][j]
      • 第一轮：将v0作为中间顶点，对于所有顶点对{i,j}，,比较方阵中的某些值大小后，更新之后的方阵标记为A^0；
      • 第二轮：将v1作为中间顶点，继续检测全部顶点对{i,j}，比较方阵中的某些值大小后，更新之后的方阵标记为A^1；
      • 第三轮：将v2作为中间顶点，继续检测全部顶点对{i,j}，比较方阵中的某些值大小后，更新之后的方阵标记为A^2，此时A^2保存的就是任意顶点的最短路径长度；
    • 性能分析：
      • 时间复杂度为O(|V|^3)，单层for，代码也简单，但是没有复杂的数据结构，常数项也很小，对于中等规模的输入来说，它仍然是相当有效的；
      • 弗洛伊德算法允许带有负权值的边，但是不允许有回路，算法也适用于带权无线图，因为无向图可以视为有两个边的有向图
      • 也可以用Dijkstra(迪杰斯特拉)算法来解决每对顶点之间的最短路径问题，轮流将每个顶点作为源点，时间复杂度也是O(|V|^3)；
• 有向无环图描述表达式(DAG图)
  • 若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic graph)；
  • 有向无环图是描述含有公共子式的表达式的有效工具，例如(a+b)(a+b)+(b(a+b))，其中a+b就是公共子式，在用图表达式只需要一份，相同的上级指向这个子式就行；
  • 在描述二叉树来表示时，会有很多类似公共子式的子树，可以合并这些子树，有相同子树的结点可以同时指向这个子式，实现对相同子式的共享，从而节省存储空间；
• 拓扑排序
  • 每个AOV网都有一个或多个拓扑排序序列，例如：番茄炒鸡蛋，先买菜(起点)，打鸡蛋 or 切番茄哪个先都行，然后吃饭(端点)；
  • 概念描述：
    • AOV网，用顶点表示活动的网络，将这种有向图称为顶点表示活动的网络，记为AOV网(Activity on Vertex network)；
    • 若用DAG图表示一个市政路网工程，其顶点表示为活动，用有向边<Vi,Vj>表示活动，Vi活动必须先于活动Vj进行的这样一种关系称为AOV网；
    • 在AOV网中，活动Vi是Vj的直接前驱，活动Vj是Vi的直接后继，这种前驱后继的关系具有传递性，且任何顶点(活动)都不能以自己作为自己的前驱或后继；
  • 由一个有向无环图的顶点组成的序列，满足以下条件时，则为图的一个拓扑排序：
    • 1 每个顶点有且仅出现一次；
    • 2 若顶点A在序列中排在B的前面，则在图中不存在从顶点B到A的路径，或定义为：拓扑排序是对有向无环图的顶点的一种排序，他使得顶点A到B存在一条路径；
  • AOV网进行拓扑排序的算法有很多种，下面是比较常用的一种方法的步骤：
    • 1 从AOV网中选择一个没有前驱的顶点并输出(一般是起点0)；
    • 2 从网中删除该顶点的所有以他为起点的有向边；像不像层序遍历？
    • 3 重复1-2直到当前AOV网为空，或当前网中不存在无前驱的顶点为止(这种说明有向图中有环)；
  • 性能分析：
    • 采用邻接表存储拓扑排序：时间复杂度为O(|V|+|E|)，因为输出每个顶点的同时还要删除以他为起点的边；
    • 采用邻接矩阵存储拓扑排序：时间复杂度为O(|V|^2)。对于一个图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列，反之则不一定成立；
    • 用深度优先也可以实现拓扑排序，可思考实现方法；
• 关键路径
  • 概念描述
    • AOE网，称之为用边表示活动的网络，在带权图中，以顶点表示事件，已有向边表示活动，以边上的权值表示完成该活动的所需的时间；
    • AOE网和AOV网都是有向无环图，不同之处是他们的边和顶点所代表的含义是不同的，AOE网中的边有权值，而AOV网中的边无权值(仅表示顶点之间的前后关系)；
    • AOE网的两个性质：
      • 只有在某顶点所代表的事件(打鸡蛋or切番茄)发生后，从该顶点出发的各有向边所代表的活动才能开始；
      • 只有在进入某顶点的各有向边所代表的活动都已结束时(出栈)，该顶点所代表的事件才能发生；
    • 称源点(出度为0的顶点，网中仅存在一个)为开始顶点，它表示整个工程的开始，汇点(结束顶点)，它表示整个工程的结束；
    • 关键路径、关键活动的解释：
      • 在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。
      • 完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。
      • 因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动；
    • 关键路径的长度：
      • 完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，
      • 即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。
  • 寻找关键活动时所用到的几个参量的定义如下：
    • 1 事件vk的最早发生时间ve(k)：从源点v1到顶点vk的最长路径长度，事件vk的最早发生时间决定了所有从vk开始的的活动能够开工的最早时间(+1)；
    • 2 事件vk的最迟发生时间vl(k)：在不推迟整个工期的前提下，该事件最迟必须发生的时间；
    • 3 活动ai的最早开始时间e(i)：该活动弧的起点所表示的事件最早发生时间。若边<vk，vj>表示活动ai，则有e(i) = ve(k)；
    • 4 活动ai的最迟开始时间l(i)：该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差；
    • 5 一个活动ai的最迟开始时间l(i)和其最早开始时间e(i)的差额d(i)=l(i) - e(i)
      • 是指该活动完成的时间余量，在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间。若时间为零，则说明该活动必须要如期完成，否则可以拖延；
    • 求关键路径的算法步骤如下：
      • 1 从源点出发，按拓扑有序求其余顶点的最早发生时间ve()；
      • 2 从汇点出发，令以(汇点)=ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl()；
      • 3 根据各顶点的ve()值求所有弧的最早开始时间e()；
      • 4 根据各顶点的vl()值求所有弧的最迟开始时间l()；
      • 5 求AOE网中所有活动的差额dO，找出所有d()=0的活动构成关键路径；
    • 关键路径需要注意以下几点：
      • 关键路径上所有活动都是关键活动，它是决定整个工程的关键因素，因此可以加快关键活动来缩短整个活动周期，单不能任意缩短关键活动；
      • 网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快所有关键活动才能缩短工期；

7、查找

知识框架-7

• 查找
  • 基本概念
    • 静态查找
    • 动态查找
  • 线性结构
    • 顺序查找
    • 折半查找
    • 分块查找
  • 树形结构
    • 二叉排序树
    • 二叉平衡树
  • 散列结构-散列表
    • 性能分析
    • 冲突处理
  • 效率指标-平均查找长度
    • 查找成功
    • 查找失败

查找的基本概念

• 查找表
  • 对查找表经常进行的操作一般有4种
    • 查找某个特定的数据元素是否在查找表中
    • 检索满足条件的某个特定的数据元素的各种属性
    • 在查找表中插入一个数据元素
    • 在查找表中删除一个数据元素
• 静态查找表
  • 若一个查找表的操作只有查询，无序动态地修改查找表；
  • 适合静态查找表的查询方法有：顺序查找、折半查找、分块查找
• 动态查找表
  • 需要动态的插入、删除的查找表
  • 适合动态查找表的查询方法有：二叉排序表、散列查找
• 关键字：数据元素中唯一标识该元素的某个数据项的值，用关键字查找的结果是唯一的，例如“学号”
• 平均查找长度
  • 一次查找长度是指需要比较关键字的次数；
  • 平均查找长度是所有查找过程中进行关键字比较次数的平均值，一般认为每个数据元素的查找概率相同；
  • 平均查找长度是衡量查找算法效率的最主要指标

静态查找表

• 顺序查找(线性查找)
  • 适用于：顺序表和链表
    • 顺序表：可通过数组下标递增来顺序扫描每个元素
    • 链表：可通过指针next来依次扫描每个元素
    • 顺序查找通常分为对无序线性表、和按关键字有序的线性表的顺序查找，如下两种
      • 一般线性表的顺序查找
        • 从线性表的一端开始，逐个检测关键字是否满足给定的条件，查找成功，返回该元素的位置，查找失败返回失败的信息
        • 用数组第一个位置标记为哨兵，就可以不用写没查找时的if返回值了；
        • 优点：对表中记录的有序性没有要求
        • 缺点：数据规模n较大时，平均查找长度较大，效率低
        • 注意：对线性表的链表只能进行顺序查找
      • 有序表的顺序查找
        • 查找之前已经知道表是关键字有序的，可以降低查找失败的平均查找长度；
        • 比如查找关键字key，当查找到第i个元素时发现第i个元素对应的关键字小于key，但i+1个元素对应的关键字大于key，这时可返回查找失败；
        • 线性表的查找过程：若有n个结点，则查找失败地有n+1个查找失败的结点；
        • 比一般的顺序查找算法好一些，且顺序性表的顺序查找的线性表可以是链式存储结构；
• 折半查找(二分查找)
  • 仅适用于有序的顺序表；
  • 基本思想：
    • 首先将给定值key与表中间位置的元素比较，若大于或者小于中间位置元素，则查找的元素只可能是另一边的部分；
    • 在缩小的范围内继续上述的步骤，如此重复调整low/high/mid的值，直到找到为止，或确定表中没有需要查找的元素，返回查找失败信息；
    • 指针low和high分别之前首尾部分，mid指向表的中间位置(low+high)/2，floor时n是奇数，左边比右边多一个，upper时相反；
    • 判定树
      • 折半查找的过程可以用二叉树来描述，称为判定树，每个结点的值均大于左子结点，均大于右子结点，显然判定树是一颗平衡二叉树；
      • 从判定树可以看出来，查找成功时查找长度为从根结点到目的结点的路径上的结点数；
      • 查找不成功时，查找长度为从根结点到对应失败结点的父结点的路径上的结点数；
    • 时间复杂度为O(log2n)，平均情况下比顺序查找的效率高；
• 分块查找(索引顺序查找)
  • 吸取了顺序查找和折半查找各自的优点，既有动态结构，又适合快速查找；
  • 基本思想：
    • 将查找表分成若干块，块内的元素可以无序，但块与块之间的元素是有序排列的，前一个块中的关键字大于后一块中的所有记录；
    • 是新建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址；
    • 分块查找的过程分两步：
      • 第一步在索引表中确定待查记录所在块，可以顺序查找or折半查找；
      • 第二步只能在块内顺序查找；
    • 平均查找长度为：索引查找O(log2n)+块内查找的平均O(n);

动态查找表-树形查找

• 二叉排序树(二叉查找树)

  • 定义
    • 构造一颗二叉树的目的不是为了排序，而是为了提高查找、插入、删除关键字的速度；
    • 二叉排序树有以下特性：
      • 若左子树非空，则左子树上所有结点的值都小于根结点的值；
      • 若右子树非空，则右子树上所有结点的值都大于根结点的值；
      • 左、右子树也分别是一颗二叉排序树；
      • 左子树 < 根结点 < 右子树，因此对二叉排序树进行中序遍历可以得到一个递增的有序序列；
  • 查找
    • 从根结点开始，沿某个分支逐层向下比较的过程。如果小于根结点的关键字，则在根结点的左子树上找，否则在右子树上找；
    • 可以用两种方式实现：
      • 1、递归实现，比较简单，但执行效率较低；
      • 2、也可以用while移动指针比对；
  • 插入
    • 关键字不存在树中是在进行插入；
    • 插入过程如下：
      • 若原来二叉树为空，则直接插入；
      • 若关键字k小于根结点的值，则插入到左子树，大于根结点的值，则插入到右子树。
      • 插入的结点一定是新添加的叶结点，递归调用，可能退化成链表；
  • 构造
    • 从一颗空树出发，依次插入元素，将它们插入到二叉排序树中的合适位置，同插入过程一样；
  • 删除
    • 当删除的结点有子结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失；
    • 删除过程按以下3种情况来处理：
      • 1、删除的是叶子结点，直接删除
      • 2、若z只有一颗左子树或者右子树，则让z的子树替代z的位置；
      • 3、若z有左右两颗子树，则让z的直接后继(或直接前驱)替代z，然后从二叉排序树中删除这个直接后继(或直接前驱)，这样就转换成了第一或第二情况；
  • 查找效率分析
    • 平均情况：查找效率主要取决于树的高度，若左右子树高度之差不超过1，则它的平均查找长度为O(log2n)；
    • 最坏情况：若只有左or右单支树(类似于有序的单链表)，平均查找长度为O(n)；
    • 二叉排序树与二分查找的比较：
      • 从查找过程来看，二叉排序树与二分查找相似，从平均性能而言，二者差不多，
      • 区别是二分查找的判定树唯一，而二叉查找树查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树(符合左<根<右就行)；
      • 静态表，查找的是有序顺序表时，宜用顺序表作为存储结构，采用二分查找；
      • 有序表分静态和动态，静态用链表和线性存储都可以，动态用链表效率高；

• 平衡二叉树

  • 定义
    • 在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，高度之差为该结点的平衡因子，可以避免树的高度增长过快；
    • 将这样的二叉树称为平衡二叉树(Balanced Binary Tree)或AVL树(他们三个人发明的)；平衡因子只可能是-1、0、1；
    • 空树，或者左右子树都是平衡二叉树，且左右子树高度之差不超过1；
  • 插入
    • 二叉排序树保证平衡因子的基本思想如下：
      • 每当删除或插入一个结点时，首先要检查其插入路径上的结点是否因此操作破坏平衡，检查祖先的平衡因子有没有大于1的；
      • 若导致不平衡，则先找到插入路径上离插入结点最近的平衡因子大于1的结点A，再对以A为根的子树调整各结点的位置关系，以保持平衡二叉排序树的特性；
      • 注意：每次调整对象都是最小不平衡子树；
      • 调整的规律有以下4种情况：
        • LL平衡旋转(右单旋转)：
          • 由于以A为根的左子树(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去了平衡，需要进行一次向右的旋转操作；
          • 将A的左子树B向上旋转代替A称为根结点，将A结点向右下旋转称为B的右子树的根结点，而B的原右子树则作为A结点的左子树；
        • LR平衡旋转(先左后右双旋转)；
          • 由于在A的左孩子(L)的右子树(R)上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。
          • 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后把该C结点向右上旋转提升到A结点的位置；
        • RR平衡旋转(左单旋转)；
          • 由于在结点A的右孩子(R)的右子树(R)上插入了新结点, A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作，
          • 将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根接单，而B的原左子树则作为A结点的右子树；
        • RL平衡旋转(先右后左双旋转)；
          • 由于在A的右孩子(R)的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。
          • 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后把该C结点向左上旋转提升到A结点的位置；
        • 注意：LR和RL旋转时，新结点究竟是插入C的左子树还是C的右子树不影响旋转过程(267页)；
  • 删除
    • 与插入操作类似，若删除导致了不平衡，则从结点W开始向上回溯，找到第一个不平衡的结点；
  • 查找
    • 平衡二叉树查找的过程与二叉排序树的相同，在查找过程中，查找比较的次数不超过树的深度；

散列表(哈希表)

• 基本概念
  • 散列表：根据关键词进行直接访问的数据结构，关键字和存储地址之间是一种直接映射关系，是一种以空间换时间的方法；
  • 散列函数：把查找表中关键字映射成该关键字对应的地址的函数，这个地址可以是数组下标、索引或内存地址；
  • 散列函数可能会把相同关键映射到同一个地址，称这种情况为冲突，这些发生碰撞的不同关键词称为同义词；
  • 这种冲突是不可避免的，但是可以设计好的散列函数尽量减少这样的冲突；
• 构造方法
  • 在构造散列函数时，要注意一下3点：
    • 散列函数的定义域必须包含全部需要存储的关键字，而值域访问依赖于散列表的地址访问；
    • 散列函数计算出来的地址应该等概率，均匀地分布在整个地址空间，从而减少冲突发送；
    • 散列函数应尽量简单，能在较短时间内计算出任意一个关键字对应的散列地址；
  • 有四种散列函数构造方法：都是把关键字当作数字
    • 直接定址法
      • 直接取关键字的某个线性函数值为散列地址，H(key)=key*a + b，a和b是常数，这种方法计算最简单，且不会发送冲突，
      • 适合关键字分布基本连续的情况，若关键字不连续，空位较多，则会造成存储空间的浪费；
    • 除留余法
      • 这是一种最简单、最常用的方法，取一个不大于散列表长度或最接近的质数p，把关键字换成散列函数，H(key) = key % p;
      • 关键是要选好质数p，是每个关键字等概率的隐射到散列空间上的任意地址；
    • 数字分析法
      • ？看不懂，没啥关系
    • 平方取中法
      • 取关键字平方值的中间几位作为散列地址，具体取多少位要视实际情况而定，例如：1024 * 1024 = 1048576，取中间3位；
      • 这种方法可以使散列地址分布比较均匀，适用于关键字的每位取值不够均匀或小于散列地址所需的位数；
    • 散列函数的比较：
      • 在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统的说哪个散列函数最好，
      • 选用哪种散列函数，取决于关键字集合的情况，目标是尽可能降低冲突；
• 处理冲突两种的方法
  • 为产生冲突的关键字寻找下一个空的hash地址，散列地址发生冲突时继续求下一个地址，以此类推，直到不发生冲突为止；
  • 开放地址法
    • 所谓开放地址法，是指可存放新表项的空闲地址既向它的同义词开发，也向它的非同义词表项开放；
    • 在开放地址的情况下，不能随便物理删除表中的已有元素，物理删除会影响其它相同散列地址的元素查找地址，删除元素采用标记删除(300页)；
    • 根据散列表的长度，设置一个增量序列，确定增量序列后，对应的处理方法就是确定的，通常有以下4中方法：
      • 线性探测法：
        • 当冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元(当表未填充满时一定能找到一个空闲地址)，
        • 这样本应该存入第i+1的地址就存到了i+2上，造成了大量元素在相邻的散列地址上堆积，大大降低了查找效率；
      • 平方探测法：
        • 又称二次探测法，k^2，k小于或等于m/2，散列表长度m必须是一个可以表示成4k+3的素数；
        • 是一种处理冲突的较好方法，可以避免堆积的问题，它的缺点是不能探测到散列表上的所有单元，但至少可以探测到一半的单元；
      • 双散列法：
        • 用两次散列函数，当发生冲突时，再用第二个散列函数计算这个关键字的增量地址；
      • 伪随机序列法：
        • 当di=伪随机序列时，称为伪随机序列法；
  • 拉链法(链接法)
    • 把所有冲突的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识；
    • 冲突之后的查找、插入和删除操作主要在这个同义词线性链表中进行；
    • 拉链法适用于经常进行插入和删除的情况，也是实际项目中经常使用的方法；
• 查找及性能分析
  • 查找过程与构造散列表的过程基本一致，查找过程如下：
    • 用Hash(key)查找表中指定位置上的记录，无记录直接查找失败；
    • 有记录且与其它key冲突，则用给定处理冲突方法计算“下一个散列地址”，用这个新计算的地址取值；
  • 查找过程：散列函数直接映像，发生冲突后任然是一个给定值和关键字进行比较的过程，仍需要以平均查找长度作为衡量散列表的查找效率；
  • 散列表的查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子；

8、排序

知识框架-8

• 排序

  • 基本概念

    • 稳定性
    • 衡量标准：时、空复杂度

  • 内部排序

    • 插入排序
      • 直接插入排序
      • 折半插入排序
      • 希尔排序
    • 交换排序
      • 冒泡
      • 快速排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 归并排序
    • 基数排序

  • 不同算法之间的对比

    • 特征：初态的影响、复杂度、稳定性、适用性
    • 手动模拟排序过程

• 排序的定义

  • 重排列表中的元素，使表中的元素按关键字有序排列的过程，为了查找方便；
  • 算法的稳定性，排序表中有两个相同元素，用排序算法排序之后，Ri仍然在Rj前面，则称这个排序算法是稳定的；
    • 稳定性只是对算法的性质进行描述，并不能衡量一个算法的优劣；
  • 内部排序：排序期间数据元素全部存放在内存中排序；
    • 内部排序在执行过程中都要进行“比较、移动”这两种操作，确定对应元素的前后关系，只有基数排序不用比较；
    • 性能取决于算法的时间和空间复杂度，时间复杂度一般由“比较、移动”的次数决定；
    • 大多数内部排序算法只适用于顺序存储的线性表；
  • 外部排序：在排序期间数据元素无法全部同时存放在内存中，在排序过程中根据要求不断的在内、外存之间移动的排序；

插入排序

• 这三个排序的总结：直接比较后交换位置、找mid优化比较次数、分组成多个子表排序；
• 简单直观的排序方法，每次将一个待排序的记录按其关键词大小插入前面已排好的子序列中，直到全部记录插入完成；
• 直接插入排序
  • 从前面的有序子表中查找待插入元素应该插入的位置，找到后给插入位置腾出空间，将待插入元素复制到表中的插入位置，边比较边移动；
  • 找出L(i)在表中要插入的位置k，向前一个比较大小获得位置k；
  • 将表中所有元素依次向后移动一个位置；
  • 将L(i)复制到L(k)
  • 在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位置，为新元素提供插入空间；
  • 数组的第0个位置不存数据或者标记为哨兵；
  • 性能分析：
    • 空间效率：通常采用就地排序，空间复杂度为O(1)；
    • 时间效率：逐个就得插入元素操作需要进行n-1趟，每趟需要进行比较和移动元素
      • 最好情况：表中元素已经有序，时间复杂度为O(n)；
      • 最坏情况：表中元素正好与元素顺序相反，总的比较和移动次数最大，时间复杂度为O(n^2);
      • 平均情况：表中待排序元素是随机的，，取最好与最坏情况下的平均值作为平均情况，总的移动和比较次数约为(n^2)/4
    • 稳定性：是一个稳定的排序方法，每次都是先比较再移动，所以不会出现相同元素相对位置发生变化的情况；
    • 适用性：
      • 适用线性存储和链式存储的线性表，为链式存储时，可以从前往后查找指定元素的位置；
      • 适用基本有序的排序表和数据量不大的排序表；
• 折半插入排序
  • 和直接插入排序基本一样，只有优化了边比较边移动的策略；
  • 将比较和移动分离，先折半查找出元素待插入位置，然后再移动到待插入位置；low/high/mid
  • 折半插入排序减少了比较元素的次序，而元素的移动次数并未发生改变，任然依赖待排序表的初始状态；
  • 比较次数与待排序表的初始状态无关，任取决于表中的元素个数n
  • 性能分析：
    • 最好情况：O(nlog2n)
    • 最坏情况：O(n^2)
    • 稳定性：是一个稳定的排序方法；
• 希尔排序(缩小增量排序)
  • 对直接插入排序进行改进得来；
  • 基本思想是先将待排序表按“d1倍数”距离分割成若干个子表，对分割之后的子表进行直接插入排序，待整个表基本有序之时对全体记录进行一次直接插入排序；
  • 排序过程：
    • 先取一个小于n的步长d1，然后把表中的全部记录分成d1组，所有距离为“d1倍数”的记录放在同一个组，在各组内进行直接插入排序，
    • 然后取第二个步长d2 < d1，重复前面的过程，直到所取到的d1=1，既所有记录已放在同一组中，
    • 此时排序表已经具有较好的局部有序性，再进行直接插入排序就可以很快得到最终结果；
  • 性能分析：
    • 空间效率：空间复杂度为O(1)；
    • 时间效率：
      • 最好情况：当n在特定范围时，时间复杂度约为O(n^1.3)；
      • 最坏情况：时间复杂度为O(n^2);
    • 稳定性：不稳定，相同关键字记录被划分到不同的子表时，可能会改变相同元素相对次序；
    • 适用性：适用于线性表为顺序存储的情况；

交换排序

• 冒泡排序
  • 基本思想是：从后往前(或从前往后)两两比较相邻元素的值，比较大小后交换他们，直到序列比较完；
  • 第一趟冒泡后，最小的元素交换到待排序列的第一个位置，下一趟冒泡时，前一趟确定最小元素的不再参与排序；
  • 每趟冒泡的结果都是把序列中最小(或最大)元素放到序列的最终位置，这样最多n-1趟冒泡就能把所有元素排好序；
  • 性能分析：
    • 空间效率：空间复杂度为O(1)；
    • 时间效率：
      • 最好情况：表中元素已经有序，比较次数为n-1，移动次数为0，时间复杂度为O(n)；
      • 最坏情况：表中元素正好与元素顺序相反，需要进行n-1趟排序，需要进行n-i次比较，时间复杂度为O(n^2);;
    • 稳定性：稳定，相同关键字记录比较大小不会进行交换；
    • 适用性：适用于线性表为顺序存储的情况；
• 快速排序
  • 基本思想是分治，三个变量pivot、low和high；
    • 取待排序表中取任意一个元素pivot作为基准(通常取首元素)，通过一趟将待排序分成独立的两部分，
    • 左边所有元素小于pivot，右边所有元素大于等于pivot，然后分别递归地对左右两个子表重复上述划分的过程，直到每部分内只有一个元素为止；
    • 每趟快速排序过程都是一个交替搜索和交换的过程，有两个指针i和j，初始值分别为low和high；
    • 在数组中交换位置，不用开辟新数组存放左右两个数组；
    • 递归的调用快排进行排序，每次传递指定数组范围；
    • 快排的关键在于划分操作Partition，快排的性能也取决于划分操作的好坏，有多个划分操作版本，以严蔚敏的教材为主；
  • 性能分析：
    • 空间效率：
      • 最好情况：空间复杂度为O(log2n)，快排是递归的，需要借助一个递归工作栈来保存每次递归的必要信息，容量是递归调用的最大深度；
      • 平均情况：栈的深度为O(log2n)；
      • 最坏情况：空间复杂度为O(n)，需要进行n-1次调用；
    • 时间效率：
      • 最好情况：表中元素已经有序，比较次数为n-1，移动次数为0，时间复杂度为O(n)；
      • 平均情况：时间复杂度为O(nlog2n)，平均情况接近最好情况的运行时间，快排是“所有内部排序中平均性能最优”的排序方法；
      • 最坏情况：时间复杂度为O(n^2)，与划分是否对称有关，最大限度的不对称发生在基数取数组中第一个，且已经有序的排序表中;
    • 稳定性：不稳定，相同关键字记录的相对位置会发生变化；
    • 适用性：适用于线性表为顺序存储的情况；
  • Partition可能做到最平衡的划分的几种方法：
    • 随机在表中选取基准元素；
    • 选取头尾和中间这三个元素，把这三个元素的中间值作为基准元素；

选择排序

• 简单选择排序
  • 基本思想是：
    • 每一趟在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到n-1趟做完，待排序元素只剩1个，就不用再选了；
    • 第i趟从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟可以确定一个元素的最终位置(和冒泡一样)，这样经过n-1趟就排序好了；
  • 性能分析：
    • 空间效率：空间复杂度为O(1)；
    • 时间效率：
      • 时间复杂度为O(n^2)，元素移动的操作次数很少，不会超过3(n-1)次，最好的情况是移动0次，此时对应表已经是有序的情况，比较次数始终是n(n-1)/2次;
    • 稳定性：不稳定；
• 堆排序(考察重点)
  • 可以将堆视为一颗完全二叉树，有最大堆(大根堆)和最小堆(小根堆)，大根堆的任意一个非根结点的值小于或等于其父结点，小根堆相反；
  • 排序步骤：
    • 首先将个元素建成初始堆，由堆本身的特点，堆顶元素就是最大值，输出堆顶元素后，通常将堆底元素送入堆顶，
    • 堆顶元素会“向下调整”保持最大堆的性质，如此重复，直到堆中仅剩下一个元素为止；
    • 调整的时间与树的高度有关，为O(n)在建有n个元素的堆时，关键字的比较总次数不超过4n，时间复杂度为O(n)
    • 可以在线性的时间内将一个无序数组建成一个堆，堆也支持插入操作，插入新结点放在对的末端，再对这个新结点“向上调整”操作；
  • 性能分析：
    • 空间效率：空间复杂度为O(1)，不用创建新内存，每次堆顶元素在数组中的位置在下一轮排序中会被隐藏；
    • 时间效率：逐个就得插入元素操作需要进行n-1趟，每趟需要进行比较和移动元素
      • 最好、最坏、平均情况：时间复杂度都为O(nlog2n)，建堆时间为O(n)，之后有n-1次向下调整操作，每次调整时间为O(h)；
    • 稳定性：不稳定，在进行筛选时，有可能会把后面相同关键字元素调整到前面；
    • 适用性：
      • 堆排序适合关键字较多的情况，例如从1亿个数中选出前100个最大(或最小)值，首先用100个元素建立最小堆，
      • 然后依次读入余下数和堆顶元素比较，大于堆顶元素则取代堆顶并重新调整堆，数据读取完毕堆中就是100个最大数；

归并排序和基数排序

• 归并的思路：
  • 将两个或两个以上的有序表合并成一个新的有序表；
  • 2路归并排序：可以将一个待排序表视为n个有序的子表，每个子表长度为n，然后两两归并，如此重复，直到合并merge()成一个长度为n的有序表为止；
  • merge()的功能是将前后相邻的两个有序表归并为一个有序表
    • 创建一个辅助数组B，然后将两段有序表A[low...mid]、A[mid+1...high]复制到B中(存放在同一顺序表的相邻位置);
    • 每次从对应B中的两个段取出一个记录进行关键字比较，将较小者放入A中，B数组为空时，再将另一段剩余部分直接复制到A中；
  • 递归形式的2路归并排序算法是基于分治的，过程如下：
    • 将含有n个元素的待排序表分成各含有n/2个元素的子表，采用2路归并排序算法对两两个子表递归地进行排序；
    • 合并两两已排序的子表得到排序结果；
  • 将N个元素进行k路归并排序，排序的趟数m满足k^m = N；
• 归并排序
  • 性能分析：
    • 空间效率：空间复杂度为O(n)，merge()操作，辅助空间刚好为n个单元；
    • 时间效率：时间复杂度为O(nlog2n)，每趟归并的时间复杂度为O(n)，需要进行[log2n]趟归并；
    • 稳定性：稳定，merge()操作不会改变相同关键字记录的相对次序；
  • 改进后的归并排序：
    • 可以将归并排序和直接插入排序结合在一起使用，先利用直接插入排序求得较长有序子文件，然后两两归并，最后归并排序结构仍是稳定的；
• 基数排序
  • 思路：
    • 不基于比较和移动进行排序，而基于关键字各个位数(996按个十百位)的大小进行排序；
    • 基数排序是一种需要借助多关键字排序的思想对多逻辑关键字进行排序的方法；
    • 实现多关键字排序的通常有两种方法：
      • 最高位优先法(MSD)：
        • 按关键字位权重递减逐层划分成若干更小的子序列，然后将所有子序列依次排成一个有序序列；
      • 最低位优先法(LSD)：
        • 按关键字位权重递增依次进行排序，最后形成一个有序序列；
    • 基数排序过程(最低位优先法)：
      • 使用r个队列Q0,Q1...Qr-1，0-9一共10个队列，阿拉伯数组各自对应一个队列，对记录依次做一次“分配”和“收集”；
      • 例如：930、008、083按个位、十位、百位，一共需要进行三趟分配和收集，第一趟个位、第二趟十位、第三趟百位，把相等的记录分配到同一个队列；
      • 分配：
        • 把Q0,Q1...Qr-1各个队列配置成空队列，然后依次考察线性表中的每个结点Aj(对应位数和队列数相等)，若Aj的关键字k(j^i)=k，就把Aj放入Qk队列中；
      • 收集：
        • 把Q0,Q1...Qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而形成新的线性表；
  • 性能分析：
    • 空间效率：空间复杂度为O(r)，一趟排序需要的辅助空间为r（r个队列，r个对头指针和r个队尾指针），之后的排序会重复使用这些队列；
    • 时间效率：时间复杂度为O(d(n+r))，需要进行d趟分配和收集，一趟分配需要O(n)，一趟分配需要O(r)
    • 稳定性：稳定的排序方法，对于基数排序算法而言，按位排序时必须是稳定的；

各种内部排序算法的比较及应用

• 内部排序算法比较
  • 一般基于三个因素进行对比；
    • 从时间复杂度看：
      • 简单选择排序与序列的初始状态无关，而直接插入排序和冒泡排序的最好状态与序列的初始状态有关O(n)，这三个实现过程较为简单，但时间复杂度都是O(n^2);
      • 希尔排序作为插入排序的扩展，在较大规模的数据都可以达到很高的效率，好坏时间复杂度分别是约O(n^1.3)、O(n^2)
      • 堆排序基于堆的数据结构，可以在线性的时间内完成建堆，且在O(nlog2^n)时间内完成排序；
      • 快速排序基于分治的思想，平均复杂度是O(nlog2^n)，但待排序正好呈现相反序列是最坏时间复杂度都是O(n^2)，实际应用由于其它算法；
      • 归并排序也基于分治的思想，单由于其分割子序列与初始序列的排列无关，它最好、最坏、平均时间复杂度都是O(nlog2^n)；
    • 从空间复杂度看：
      • 简单选择排序、直接插入排序、冒泡排序、希尔排序、堆排序都是O(1);
      • 快速排序平均大小为O(log2^n)，需要借助一个递归工作栈，最坏情况会增长到O(n)；
      • 2路归并排序大小为O(n)，在合并merge操作中需要借助较多的空间用于元素复制，虽然能克服，但是时间复杂度会增加；
    • 从稳定性看：
      • 插入排序、冒泡排序、归并排序、基数排序是稳定的排序方法，平均时间复杂度为O(nlog2^n)的稳定排序只有“归并排序”；
    • 从算法的过程特征看：
      • 冒泡排序、堆排序在每趟处理后都能产生当前最大或最小的值，快速排序一趟处理至少能确定一个元素的最终位置；
      • 给出一个待排序的初始序列和已经部分排序的序列，问其采用何种算法；
• 内部排序算法的应用
  • 通常情况比较应考虑以下情况：
    • 待排序序列规模、初始分布状态、对稳定性、时间和空间的要求，如果都是平均，那就用堆排序、快速排序、归并排序；
    • n较小采用：简单选择排序、直接插入排序(移动次数比简单选择排序多)；
    • 初始状态基本有序时采用：直接插入 or 冒泡；
    • n较大采用：堆排序、快速排序、归并排序，快排被认识是内部排序中最好的方法，但堆排序的空间复杂度最少也不会出现最坏情况，归并排序是稳定排序；
    • n很大时采用：表中的数据位数较少且可以分解时，用基数排序，比如10位数以内的数字或26个字母；
    • 记录本身信息量较大时：用链表作为存储结构可以避免大量时间移动记录；
    • 基于比较的排序方法中：
      • 每次比较两个关键字大小且只有两种可能的移动，可以采用一颗二叉树来描述比较判定过程，
      • 由此可知任何有“比较”的排序算法，至少需要O(nlog2^n)的时间；