数据结构624624

数据结构思维导图，其中顺序表 SqList是逻辑上相邻的元素物理上也一定要相邻，顺序表的下标从1开始，本图内容丰富。

数据结构

• 第一章 绪论
  • 时间复杂度
• 第二章 线性表
  • 顺序表 SqList
    • 定义
      • 逻辑上相邻的元素物理上也一定要相邻，顺序表的下标从1开始
    • 优点
      • 随机存取
    • 缺点
      • 1.插入和删除要移动大量元素以维持物理相邻 2.必须分配一段连续的存储空间，不灵活
    • 插入ListInsert（SqList &L,int i ,ElemenType e）i位以及之后的元素全部向后移(n-i+1)，length++
      • 最好情况：插表尾，不用后移O(1)
      • 最坏情况：插表头，全部后移O(n）
      • 平均时间复杂度：O(n) 概率*移动次数
      • 1<=i<=length+1
    • 删除ListDelete（SqList &L,int i ,ElemenType e）i位之后的元素全部向前移(n-i)，length - -
      • 最好情况：删表尾，不用前移O(1)
      • 最坏情况：删表头，全部后移O(n）
      • 平均时间复杂度：O(n) 概率*移动次数
      • 1<=i<=length
    • 按值查找 LocateElem(SqList L,ElemenType e）从头开始一一比较，找出第一个等于e的值
      • 最好情况：e在表头，比较一次O(1)
      • 最坏情况：e在表尾，比较n次O(n）
      • 平均时间复杂度：O(n) 平均比较次数：概率*比较次数（1/n * n（n+1)/2=(n+1)/2
    • 按序号查找 LocateElem(SqList L,int i） 直接返回L【i-1】
      • 平均时间复杂度：随机存取，一次性找到O(1)
    • 计数排序：给定一堆整数里，统计各个数字出现的次数，再对次数进行排序
  • 单链表 LinkList
    • 定义
      • 每个链表结点包括元素信息和指向后继的指针
        • 头指针：用头指针来标识一个单链表L，L指向该链表第一个结点（有头结点时指向不存信息的头结点）
    • 优点
      • 无需占用连续的内存
    • 缺点
      • 1.插入和删除要移动大量元素以维持物理相邻 2.必须分配一段连续的存储空间，不灵活
    • 头插法创建单链表List_HeadInsert(LinkList &L） 创建头结点L，L—>next为null，把新结点s插到表头
      • 核心代码：s—>next=L—>next（头指针指向的结点（头结点）的下一位） L—>next=s
      • 平均时间复杂度：O(n)
      • 读入数据的顺序与生成链表中元素的顺序是相反的
    • 尾插法创建单链表List_TailInsert(LinkList &L） 创建头结点L和尾指针r，把新结点s插到表尾
      • 核心代码：r—>next=s r=s
      • 平均时间复杂度：O(n)
      • 读入数据的顺序与生成链表中元素的顺序是相同的
    • 按值查找 *LocateElem(LinkList L,ElemenType e） 从头开始一一比较，找出第一个等于e的值，返回p
      • 最好情况：e在表头，比较一次O(1)
      • 最坏情况：e在表尾，比较n次O(n）
      • 平均时间复杂度：O(n) 平均比较次数：概率*比较次数（1/n * n（n+1)/2=(n+1)/2
    • 按序号查找 *GetElem(LinkList L,int i） 从头开始遍历到第i-1位，返回p=p—>next
      • 最好情况：e在表头，比较一次O(1)
      • 最坏情况：e在表尾，比较n次O(n）
      • 平均时间复杂度：O(n) 平均比较次数：概率*比较次数（1/n * n（n+1)/2=(n+1)/2
    • 插入结点：将新结点插入到链表的第i个位置 遍历到i-1位，在其后面插入新结点s
      • 核心代码：p=GetElem（L，i-1） s—>next=p—>next p—>next=s
      • 平均时间复杂度：O(n） 开销在于查找第i-1个结点
    • 删除结点：删除第i个结点（检查删除位置的合法性i>0）遍历到i-1位，修改其next指针
      • 核心代码：p=GetElem（L，i-1） s=p—>next p—>next=s—>next
      • 平均时间复杂度：O(n） 开销在于查找第i-1个结点
    • 求单链表表长：判断是否非空，设置计数器，当p—>next=null时停止。注意带头结点时无需另外判断非空，不带头结点时需要。
• 第三章 栈和队列
  • 栈 Sqstack
    • 先进后出
    • 栈顶指针：S.top 栈空时S.top=-1，栈满时S.top=MaxSize-1 元素序号范围0～Maxsize-1 元素存在顺序表里 栈长：S.top+1
    • 考点：给定进栈顺序，选择可能的出栈顺序 给定进栈出栈顺序，判断该栈的最小容量
    • 出栈：返回栈顶元素x=S.data[S.top]，S.top- - 入栈：S.top++,写入新元素S.data[S.top]=x 栈顶指针指的位置有元素
  • 队列SqQueue
    • 先进先出，队尾进队头出
    • 队头指针:Q.front 队尾指针:Q.rear
    • 顺序队列
      • 队空时：Q.front=Q.rear 入队：Q.front不动，S.data[Q.rear]=x,Q.rear++ 出队：Q.rear不动，x=S.data[Q.front],Q.front++
      • 当front大于0时，无法用Q.rear=Maxsize判断队满，假溢出引入循环队列
    • 循环队列
      • 元素序号范围0～Maxsize-1 队空时：Q.front=Q.rear 队满时：Q.front=Q.rear 入队：S.data[Q.rear]=x. PppppQ.rear=(Q.rear+1)%Maxsize 出队：x=S.data[Q.front] Q.rear=(Q.rear+1)%Maxsize 队长：(Q.rear+Maxsize-Q.front)%Maxsize 由于牺牲一个元素判断队满 所以最大队长为Maxsize-1 队头指针指的位置有元素，队尾指的位置无元素
      • 区分队空队满1. 牺牲一个元素不能填入数据 队空Q.front==Q.rear 队满(Q.rear+1)%Maxsize==Q.front 2. 设置size表示队列元素个数 size=0时队空；size=Maxsize时队满 3.设置tag标记上一次操作是删除0还 是插入1。 hhhjjjnnnn。 kfjejdfjjjj。 队空tag==0&&Q.front==Q.rear好多好多。 队满tag==1&&Q.front==Q.rear
    • 双端队列
      • 两端都可以进行输入输出操作的队列 进队时，前端进的元素在后端进的元素的前面 出队时，无论从哪端出，先出队的排在前面
      • 输入受限的双端队列：一端只允许输出，另一端允许输入输出
      • 输出受限的双端队列：一端只允许输入，另一端允许输入输出
  • 栈和队列的应用
    • 队列的应用
      • 1.层序遍历二叉树 2.解决主机与外部设备直接速度不匹配-缓冲区 3.解决多用户的资源竞争问题-进程就绪队列
    • 栈的应用
      • 1.括号匹配 eg：([]());[([][])];[(]);(()] 遇到左括号就入栈，遇到右括号就与栈顶左括号匹配，若匹配弹出栈顶，若不匹配报错。最后栈为空才是匹配成功
      • 2.中缀转后缀 eg：（a+b）*c/d —>（（（a+b）*c）/d） —> ab+c*d/ （1）按运算优先级给表达式加括号 （2）把右括号替换成该层的运算符，去掉左括号
        • 后缀表达式手算：从左往右扫描，操作数入栈，没遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，运算结果入栈
      • 递归调用，数制转换
  • 用数组存储n阶矩阵
    • 行优先存储 列优先存储 告诉你用什么存储方式，给定数组下标，判断该元素在矩阵的几行几列
    • 特殊矩阵压缩存储
      • 对称矩阵 只存放上（下）三角的元素
        • 数组元素个数：n(n+1)/2
        • 存下三角时行优先 存上三角时列优先
      • 上（下）三角矩阵 把常量部分合并成一个元素放在末尾
        • 数组元素个数：（n(n+1)/2）+1
        • 存下三角时行优先 存上三角时列优先
      • 三对角矩阵 零元素不放在数组中
        • 数组元素个数：3n-2
        • 行优先存储
      • 默认矩阵第一个元素是a1,1 数组第一个元素下标为0，要注意题目是否有改动
• 第八章排序
  • 插入排序
    • 直接插入排序
      • 依次将待排序序列中的元素插入到前面已排好序的子序列当中从后往前比较大小，交换位置，若大于等于排好序的序列的最后一个元素，不用移动。
      • 性能
        • 时间复杂度
          • 最好情况：给定序列有序，每次都只跟已排好序列的最后一个比较O（n）
          • 最坏情况：给定序列逆序，每次都要遍历一整个已排序表O（n^2）
          • 平均情况：O（n^2）
        • 空间复杂度
          • O（1）
        • 稳定性
          • 稳定
        • 存储结构
          • 链表/顺序表
      • 是否每趟排序都确定一个元素的最终位置
        • 不是
      • 在待排序列基本有序的情况下，直接插入排序的效率最高
    • 折半插入排序
      • 依次将待排序序列中的元素插入到前面已排好序的子序列当中，用折半查找确定插入的位置
      • 性能
        • 时间复杂度
          • 最好情况：给定序列有序，仍需进行一次从中间开始的折半查找，所以效率比直接插入排序还低 O（nlog2n）
          • 最坏情况：给定序列逆序，每次都要遍历一整个已排序表O（n^2）
          • 平均情况：O（n^2）
        • 空间复杂度
          • O（1）
        • 稳定性
          • 稳定
        • 存储结构
          • 顺序表（折半查找不能用链表）
      • 是否每趟排序都确定一个元素的最终位置
        • 不是
    • 希尔排序
      • 将待排序序列以d为增量分成若干组，分别对这些组同时进行直接插入排序，每一趟排序后都按一定方式缩小d的值，再次分组排序直到d等于1
      • 性能
        • 时间复杂度
          • 无
        • 空间复杂度
          • O（1）
        • 稳定性
          • 不稳定 相同的值可能在不同的分组排序的时候交换了前后关系
        • 存储结构
          • 顺序表（链表实现分组困难）
      • 是否每趟排序都确定一个元素的最终位置
        • 不是
  • 交换排序
    • 冒泡排序
      • 从前往后（或从后往前）两两比较相邻元素的值，若为逆序，则交换位置
      • 性能
        • 时间复杂度
          • 最好情况：给定序列有序，只需要一趟两两比较O（n）
          • 最坏情况：给定序列逆序，需要n-1趟两两比较O（n^2）
          • 平均情况：O（n^2）
        • 空间复杂度
          • O（1）
        • 稳定性
          • 稳定
        • 存储结构
          • 顺序表/链表
      • 是否每趟排序都确定一个元素的最终位置
        • 是，每次确定一个最大/小的元素
    • 快速排序
      • 选定一个枢轴pivot（一般是第一个或最后一个）指针i指向low，j指向high，假设第一个元素为pivot，i往后扫描，当i遍历到一个大于pivot的元素时，将该值替换到j所指的位置，j往前扫描，当j扫描到一个小于pivot的元素时，将该值替换到i所指的位置，直到i和j指向同一个位置时，把pivot的值放到该位置。 以刚刚确定好的位置为分界点，对左右两边的序列同时进行上述操作，直到待排序序列只剩下一个元素。
      • 性能
        • 时间复杂度
          • 最好情况：每次选的枢轴划分两边足够平均，同时进行排序的组数就越多O（nlog2n）
          • 最坏情况：给定序列基本有序/逆序O（n^2）
          • 平均情况：O（nlog2n）
        • 空间复杂度
          • O（log2n）～O（n），需要借助递归栈来同时进行两边的排序
        • 稳定性
          • 不稳定 比如abc，a=b，low扫描到a大，换到high指向c的位置
        • 存储结构
          • 顺序表
      • 是否每趟排序都确定一个元素的最终位置
        • 是，每次确定一个随机选中的枢轴的位置
      • 元素基本有序时不适合用快排，就平均性能而言，快排是最好的算法
  • 选择排序
    • 简单选择排序
      • 每一趟在待排元素序列中遍历选取关键字最小/最大的元素加入有序子序列（与L【i】位置元素进行交换）
      • 性能
        • 时间复杂度
          • 平均情况：O（n^2）比较次数与初始序列次序无关，都是n(n-1)/2
        • 空间复杂度
          • O(1)
        • 稳定性
          • 不稳定 比如第i趟找到最小元素后和第i个元素交换，可能会导致第i个元素和其相等元素的相对位置发生变化
        • 存储结构
          • 顺序表 链表
    • 堆排序
      • 大根堆：所有结点的值都大于其左右子树 小根堆：所有结点的值都小于其左右子树
      • 堆顶元素一定是所有元素里最大/小的元素，因此，每轮输出堆顶元素后调整堆得到新的堆顶元素，再输出，再调整堆，直到所有元素都在堆顶输出，得到有序序列
      • 构造堆：把初始序列当成完全二叉树层序遍历的序列构造完全二叉树，找到最后一个叶结点的父结点（n/2」），以该结点为根，调整这颗子树，根结点与左右子结点关键字比较，选取大的一个交换位置（交换后检查是否影响了下层的堆）；然后同理从右到左从下到上依次调整每个非叶结点为根结点的子树，每次根结点仅与其左右结点比较，即可调整完成 输出堆顶元素后调整堆：把最后一个元素放到堆顶，与左右结点比较，与较大者互换位置，再跟其左右结点比较…从上往下直到换到他所在的位置，调整完成，再次输出堆顶元素
      • 插入操作，把新元素放到完全二叉树的最后一个位置，与其父结点比较交换位置，从下往上调整
      • 堆排序适用于待排序元素个数很多的情况，找出前n个最值就很方便
      • 性能
        • 时间复杂度：建堆O（n），调整O（h），调整n-1次，时间复杂度最好最坏平均都为nlog2n
        • 空间复杂度 O（1）
        • 稳定性
          • 不稳定
  • 归并排序
    • 二路归并排序
      • 给定序列n个元素，两两为一组排序，排序好的序列为一个整体，再跟相邻的序列归并排序，直到合成一个长度为n的有序表 如何把两个有序表合并成一个：ij分别指向两个待排序表的元素，k指向长度为n的顺序表待存放位置，ij指向的两个元素之间进行比较，小的放到k指向的位置，k向后移，i/j向后移。直到其中有一个表遍历完成，另一个表直接把剩下的元素放到最后。
      • 性能
        • 归并算法
          • 每趟归并算法的时间复杂度为O（n）无论如何，把关键字放到辅助空间这句代码都是要运行的，需要进行「log2n趟排序
        • 时间复杂度
          • 最好最坏平均都为O（nlog2n） 即初始序列任何情况都不影响其效率
        • 空间复杂度
          • O（n）新开一个顺序表存放比较过后的值
        • 稳定性
          • 稳定
        • 存储结构
          • 顺序表
        • 最多比较次数：m+n-1 最少比较次数min（m，n）
      • 是否每趟排序都确定一个元素的最终位置
        • 否
  • 基数排序
    • 给定一个链表A，里面有元素，假设都是三位数。准备10个链表，分别存放关键字为0～9的元素。 第一轮先按照个位的数值放到对应0～9的链表中，在从链表0的第一个元素开始遍历到链表9，形成一个个位数有序的链表A'，按照A'的顺序把十位数对应的数值按值放到十个链表中，再从链表0开始遍历组成一个A‘’，再对百位的数值进行同样的操作，最后得到的A‘’‘就是排好序的链表，整个过程没有比较
    • 可以解决给学生按年龄大小排序的问题，对日分配1～31的链表，对月分配1～12的链表，对年分配例如2000～2015的链表
    • 每趟排序的空间复杂度为所需链表的个数 总时间复杂度为O（d（n+r））d为排序次数，n为元素个数，r平均需要链表数
    • 稳定性
      • 稳定
  • 子主题
  • 对于任意n个关键字进行基于比较的排序，至少要进行「log2n！次关键字的比较
• 第六章 查找
  • 顺序查找
    • 过程：从头开始逐个比较，直到比较成功或比较到表尾结束不要求元素有序
    • 等概率的情况下，平均查找长度： ASL成功=（n+1）/2 ASL失败=n+1
    • 注意，有序表顺序查找失败的ASL是不同的
  • 折半查找
    • 过程：将Key与位于中间的元素进行比较 Key小则high=中间元素位置-1 Key大则low=中间元素位置+1 只用于有序表
    • n/2 向上取整
    • 平均查找长度 ASL成功=log2(n+1)-1 ASL失败=各方块*比较次数之和/判定树的方块结点个数 时间复杂度O(log2n)
    • 二叉判定树
      • 以中间元素为根结点，左边元素在左子树，右边元素在右子树。顺序表的元素用圆圈表示，不在表中的元素以区间的形式用方框表示 要查找的元素在判定树的层树就是比较次数，树的高度「log2(n+1)即为最大比较次数
    • 顺序存储
  • 分块查找
    • 块内无序，块间有序，第一个块的元素的最大值要小于第二个块的所有元素，索引指向分块的第一个元素
    • 块间和块内元素的查找都可以用顺序查找或折半查找，如果给定序列有序，用折半查找
    • 分块大小：若元素个数为n个，则分块数=根号n
  • 二叉排序树 二叉搜索树
    • 左子树关键字小于根结点，右子树关键字大于根结点二叉排序树二叉遍历的结果一定是递增的
    • 查找操作：关键字比根结点小就去左子树，比根结点大就去右子树
      • 树的第N个结点 当树长得像平衡二叉树时（即每层都尽量填满）查找效率最好为O(log2(N)) 当树一层一个结点时，查找效率最差为O(N)
    • 插入操作：关键字比根结点小插入到左子树，比根结点大插入到右子树插入的新结点一定是叶子结点
    • 删除操作： 1、若该结点为叶结点直接删除 2、若该结点只有左子树或右子树，则让子树的根结点取代它本身 3、若该结点x有左右子树，则找到该结点的中序后继结点y替代x，然后对y进行删除操作
  • 平衡二叉树AVL
    • 左右高度差不超过1的二叉排序树
    • 插入操作： 1、把新结点x根据关键字大小插到适当位置 2、找到最小不平衡子树，其根结点为y 3、找到x和y之间的路径上离y最近的三个结点（包括y），对这三个结点根据关键字大小进行调整
    • 考点：n个结点的最大深度为h=具有h层结点的平衡二叉树至少有n个结点 只要保证每个结点的平衡因子不越界即可，h-1层在这种情况下一般都是不会满的
  • m阶B树与B+树
    • m阶B树
      • 1、根结点至少有两个子树 2、其他分支结点， 最多m个子树，最多m-1个关键字， 最少「m/2个子树，最少「m/2 - 1个关键字 所有结点平衡因子都为0，因此他的每层的结点都是满的 B树的叶结点不含关键字，叶子结点不占高度
      • 非叶结点结构： n｜P0｜K1｜P1｜K2｜P2｜…｜Kn｜Pn P是指针，K是关键字。关键字值的大小从K1到Kn递增。在 K左边的P指向的子树关键字都小于K，在K右边的P指向的子树关键字都大于K
    • B+树
      • 1、根结点至少有两个子树 2、其他分支结点 最多m个子树，最多m个关键字 最少「m/2个子树，最少「m/2 个关键字 3、叶结点按关键字大小顺序排列，所有关键字都在叶结点中，非叶结点仅起索引作用 4、非叶结点只包含每个子结点的关键字的最大值，从下往上构建 因此，B+树有两种查找方式，从根结点开始的多路查找（随机查找），从最小关键字开始的顺序查找，而B树只有前者，考纲对B+树之考察概念和定义，不会考操作
    • B树的查找
      • 1、先在磁盘中找结点，查找到叶结点则查找失败 2、找到结点后，在内存中查找该结点的有序表关键字序列 a.对顺序表进行查找，对关键字进行比较 b.比较失败则根据对应指针所指的磁盘位置寻找下一个结点 随机查找：根据给定要查找的值，每次跟二叉树的根结点关键字做比较，来判断往左还是往右从而进行查找。查找路径是根据要查找的值实时变化的，所以叫随机查找。
      • 影响查找效率的因素主要是树的高度即I/O次数 关键字所在层树即I/O次数
    • B树的插入
      • 1、根据关键字的大小用查找算法找出该关键字应该放置的非叶结点 2、若插入后该结点的关键字数量不超过m-1，则直接插入；若关键字个数大于m-1，则对结点进行分裂 分裂：把待插入元素放到该结点位置后，把该结点中间（向上取整）的关键字放到父结点对应位置，以这个关键字为界左右分成两个结点，若移到父结点后，父结点因为关键字个数增加需要分裂，就分裂父结点分裂到最后可能会使根结点分裂，树的高度+1
    • B树的删除
      • 当K不在最底层结点时，用K的子树中的前驱/后继关键字K‘替代K的位置，然后在K’所在的结点中对K'进行删除，最后总能把问题转换成对最底层结点的删除： 1、当结点P的关键字个数大于「m/2 - 1时，直接删除 2、当结点P的关键字个数小于等于「m/2 - 1时: a.若兄弟结点的关键字个数大于「m/2 - 1，则把左/右兄弟结点最边边的关键字换上父结点，父结点对应关键字换到结点P所删除的位置上 b.若兄弟结点的个数都等于「m/2 - 1，则把关键字删除，把与兄弟夹着的父结点的关键字移下来，两结点合并
  • 散列表（哈希表）
    • 散列函数：key值和数组下标的映射关系。记为Hash（key） 冲突：不同key值带入Hash函数计算出来相同结果，这些key称为同义词 冲突处理方法：开放定址法；拉链法 聚集：处理冲突后非同义词争夺地址 装填因子：表中记录数n/散列表长度m
    • 散列函数构造方法：除留余数法，散列表表长为m则取一个最接近但不大于m的质数p H（key）=key%p
    • 开放定址法： 1、线性探测法，从计算所得的下标开始往后遍历找到一个空闲的位置存放key 2、平方探测法，依次找计算的下标+1^2，-1^2，+2^2，-2^2，…+k^2，-k^2，找到空闲的位置就存下。k<m/2 ，m必须是一个可以表示成4k+3的质数
    • 拉链法，把计算结果相同的key值存放到同一个链表中拉链法适用于经常插入删除的情况
    • 平均查找长度： ASL成功：每个元素比较次数乘概率之和除以元素个数 ASL失败：从0～p-1开始遇到空 （与空也要比较一次）的比较次数之和除以p
• 第五章 图
  • 基本概念
    • 有向图<v弧尾，w弧头>
      • 强连通图：任意两个结点之间有往返路径
    • 无向图（v，w）
      • 连通图：任意两个结点都存在路径
    • 完全图：边最多的图 无向 n(n-1)/2 有向 n(n-1)
    • 生成树(无向图)：边最少的连通图n-1
    • 简单回路：路径上只有头和尾结点是重复的
    • 简单路径：路径上没有重复的结点
    • 回路：路径的头和尾结点是同一个结点
  • 图的存储
    • 邻接矩阵法
      • 用二维数组存储 对于有向图：打横看是这个点的出度，竖看是入度 对于无向图：这是一个对称矩阵，可以用压缩存储
      • 缺点：无论边多还是少，确定图中有多少条边时要遍历整个矩阵，代价很大O（n^2）
      • 适用于稠密图
    • 邻接表法
      • 为每个结点创建一个链表，链表后面是该结点指向的结点
      • 特点
        • 1、若无向图有n个顶点，e条边，其邻接表仅需n个头结点，2e个表结点
        • 2、对无向图，结点i的度就是第i个链表的结点个数，对有向图要求i的度就要遍历所有链表
        • 3、要确定两个结点是否相连必须搜索相应的链表，而邻接矩阵只需访问两个数组元素看看是否为1
        • 4、邻接表的表示并不唯一
  • 图的遍历
    • 广度优先遍历BFS
      • 借助一个队列 和一个一维数组（用于标记已访问的元素）
      • 每访问一个队头元素，就把其所有的邻接结点入队，直到队空（类似于树的层序遍历，也是用了队列）
      • 空间复杂度O(V)V为结点个数
      • 时间复杂度：用邻接矩阵时O(V^2) 用邻接表时O(E+V) V为结点个数，E为边数
    • 深度优先遍历DFS
      • 借助一个栈 和一个一维数组（用于标记已访问的元素）
      • 每访问一个元素就访问其其中一个领接结点入栈，若当前结点已经没有领接结点了就出栈一个元素，访问上一个元素的另一个邻接结点，直到栈空（类似于先序遍历
      • 空间复杂度O(V)V为结点个数
      • 时间复杂度：用邻接矩阵时O(V^2) 用邻接表时O(E+V) V为结点个数，E为边数
    • 注意：当使用邻接矩阵时遍历序列是唯一的，使用邻接表时序列是不唯一的
  • 最小生成树：所有生成树中边的代价之和最小的生成树
    • 性质
      • 1、最小生成树不是唯一的 2、当图中每条边的权值都不一样，则最小生成树是唯一的
    • 给定一个图计算最小生成树的算法
      • 普里姆算法：任选一个点，找出与之连接的代价最小的边将其所连的点纳入点集合里，从未选择的边中找出与这两个点相连的最小代价的边，把所连对点并入点集合里…以此类推，直到结点都在集合中
        • 时间复杂度O（V^2） 时间代价与边的数量无关，适用于边稠密的图
      • 克鲁斯卡尔算法：把边按照权值从小到大排好，每次都选择最小的边，若选取的边两端顶点已经在同一个连通分量中，则舍弃这条边，往下选取，直到选择了n-1条边
        • 时间复杂度：O（Elog2E） 时间代价与顶点数量无关，不适用于稠密图
  • 求最短路径的算法
    • 迪杰斯特拉算法：求某个顶点到其他所有顶点到最短路径
      • 时间复杂度O(V^2)
      • 不允许图中有带负权值的边
      • 从源点出发，写下该原点到其相邻结点的代价，选出最小代价的边对应的结点，将其加入序列中，再从新结点出发，写下该结点可以到达的相邻结点的代价，若源点经过该结点与之前相比到达相同结点所需代价更小，则修改对应的值，再次找到当前最小代价的边对应的结点，加入序列中…
    • Floyd算法：求所有顶点之间最短路径的算法
      • 时间复杂度O(V^3)
      • 允许图中带负权值的边，但不允许存在带负权值的边的回路
      • 迭代一个矩阵，初始时先写出图的邻接矩阵，然后从第一个顶点开始，设可以以该顶点作为中转结点，那么其余点之间到达所需的代价会不会变小，如果会就修改对应位置的值
  • 拓扑排序
    • 给不带权有向无环图的AOV网的顶点(活动)排序，找到做事的先后顺序
      • AOV网：顶点表示活动，边的指向表示活动的先后关系
      • 每次都访问一个无前驱的结点，删除该结点和它连接的边，直到AOV网为空或找不到没有前驱的结点（说明图中有环）
      • 时间复杂度： 用领接表时O（V+E） 用邻接矩阵时O(V^2)
  • 求关键路径
    • 带权有向图AOE网从源点到汇点的最长路径
      • AOE网：顶点表示事件，边表示活动，权值表示完成活动的开销
      • 1、关键路径长度是完成工程所需的缩短时间 2、通过缩短关键路径上的活动来缩短工期，但不能无限缩短，因为缩短到一定程度，可能这条路径已经不是关键路径了 3、关键路径不唯一时，缩短一条关键路径的时间并不能缩短工期
      • 从源点出发，对于每个点，每次都选择到达这个点需要花的最长代价，记录每个点的最长路径前驱，这些点组成的路径就是关键路径
• 第四章树与二叉树
  • 满二叉树
    • 最后一层的叶结点是满的，即除叶结点外所有结点的度都为2。若高度为h，则有2^h -1个结点。编号为1～2^h -1
  • 完全二叉树
    • 编号与完全二叉树保持一致，在满二叉树的基础上少了最后一层，右边的连续的叶子结点。
    • 性质
      • 1、从上到下，从左到右依次编号1、2、3、…n； 最后一个分支节点的编号为n/2」(取下界) 因为当最后一个叶节点的编号为n时，其父结点的编号为n/2」如2和3的父结点是1
      • 2、若编号为k的结点为叶子结点或只有左子树（说明他是最后一个分支结点）则i>k的结点都是叶子结点
      • 3、若n为奇数，则所有分支结点都有左右孩子；若n为偶数，则最后一个分支结点之后左孩子
      • 4、结点i所在的层次（深度）为log2( i)」+1 第一层的编号为1 第二层为2～3 第三层为4～7 第四层为8～15…
      • 5、有n个结点的完全二叉树的高度为 「log2（n+1）或log2(n)」+1
  • 二叉排序树
    • 左子树关键字小于根结点，右子树关键字大于根结点二叉排序树二叉遍历的结果一定是递增的
    • 查找操作：关键字比根结点小就去左子树，比根结点大就去右子树
      • 树的第N个结点 当树长得像平衡二叉树时（即每层都尽量填满）查找效率最好为O(log2(N)) 当树一层一个结点时，查找效率最差为O(N)
    • 插入操作：关键字比根结点小插入到左子树，比根结点大插入到右子树插入的新结点一定是叶子结点
    • 删除操作： 1、若该结点为叶结点直接删除 2、若该结点只有左子树或右子树，则让子树的根结点取代它本身 3、若该结点x有左右子树，则找到该结点的中序后继结点y替代x，然后对y进行删除操作
  • 平衡二叉树AVL
    • 左右高度差不超过1的二叉排序树
    • 插入操作： 1、把新结点x根据关键字大小插到适当位置 2、找到最小不平衡子树，其根结点为y 3、找到x和y之间的路径上离y最近的三个结点（包括y），对这三个结点根据关键字大小进行调整
  • 二叉树的遍历
    • 用递归实现先序遍历根左右；中序遍历左根右；后序遍历左右根；用队列实现层序遍历
    • 由遍历序列构造二叉树： 中序+前序 中序+后序 中序+层序 前序的第一个，后序的最后一个为根结点，在中序序列中以根结点划分左右子树
  • 哈夫曼树
    • 叶节点带权路径长度之和最小的二叉树 带权路径长度：叶节点的权重x到根结点的路径长度
    • 如何构造：给定一堆带权重的结点，每次权重最小的两个作为左右孩子，其根结点权值为孩子权值之和
    • 哈夫曼树用于解决开销问题，权值（访问次数多的）大的离根结点要近，权值小（不怎么使用）的离根结点远，从而降低平均开销
    • 哈夫曼编码：左1右0或左0右1，按照构造哈夫曼树的方法给带权值的字符编码，字符的编码为从根结点到该字符叶节点的01编码每个字符的编码都不是另一个编码的前缀
  • 树、森林、二叉树的转换
    • 树转换成二叉树
      • 右兄弟变成右孩子
    • 森林转换成二叉树
      • 每棵树的根结点相连，第一棵树的根结点为二叉树的根结点。再把每棵树各自转换成二叉树
  • 线索二叉树
    • 每个结点都有两个指针，有左右孩子的结点指针指向左右孩子，没有孩子时，其空指针指向线索，左指针指向中序遍历前驱结点，右指针指向后驱结点。含有n个结点的二叉树中，有n+1个空指针
    • 结点结构
      • lchild ltag data rtag rchild
      • ltag
        • 1时，ltag指向其前驱结点 0时，ltag指向左孩子
      • rtag
        • 1时，rtag指向其后继结点 0时，rtag指向其右孩子
    • 分为前序线索二叉树，中序线索二叉树，后序线索二叉树，中序考的比较多
  • 树的基本性质
    • 总度数=1*n1+2*n2
    • 结点总数n=n0+n1+n2
    • 结点总数n=总度数B+1（根结点没有被度指着）
    • 叶结点等于度为二的结点数加一 n0=n2+1
  • 当m<n/2，度为1的结点个数不可能是2m（偶数），只能是奇数