• Stars
    star
    102
  • Rank 335,584 (Top 7 %)
  • Language
    Java
  • Created almost 6 years ago
  • Updated over 3 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

算法学习

  • 这个专栏是Hollis知识星球的朋友们练习算法的地方
  • 欢迎广大网友参与分享算法学习经验
  • 项目目前分为两部分
    • solutions 目录
      • 算法题解,格式是 md 格式文件,方便阅读
      • 包括
        • 算法平台的题解,如 Leetcode 等
        • 算法书籍的题解,如 《剑指 Offer》
    • codes 目录:
      • 数据结构和算法的实现代码
      • 包括
        • 各类网络公开课的代码
        • 各类算法书籍的代码
  • 备注
    • 本项目选取的资源都来自官方公开免费资源
    • 本项目所有内容不做商业用途
    • 本项目大部分代码由贡献者自己编写,如有引用则注明出处

学习方式

1. 面试刷题

适合短期面试突击或日常刷题练手

2. 基础知识

适合从零开始真正学习和掌握数据结构和算法知识

网络公开课

1) 数据结构与算法基础-java版(罗召勇)

2) 尚硅谷Java数据结构与java算法(Java数据结构与算法)

笔记

一、数据结构与算法基础-java版(罗召勇)

本课程为 DT 课堂颜群发布在 Bilibili 上的免费视频
《数据结构与算法基础-java版(罗召勇)》
https://www.bilibili.com/video/BV1Zt411o7Rn

  • 本项目中实现代码:
    codes/java_dataStructure_luozhaoyong

1. 数据结构概述

概念

  • 数据结构:数据与数据之间的关系
  • 两方面讨论:
    • 存储结构
      • 顺序存储:存储在连续的存储单元
      • 链式存储:不连续,每次存储都有数据和指针
    • 逻辑结构
      • 数据和数据本身之间的关系
        • 集合结构:数据同属于一个集合
        • 线性结构:元素之间一对一的关系
          • 数组
          • 队列
          • 单链表
          • 循环链表
          • 双链表
          • 递归
          • 排序算法
        • 树形结构:元素之间一对多的关系
        • 图形结构:元素之间多对多的关系

2. 算法概述

  • 算法定义:解决问题的思路
  • 算法的特性:
    • 输入:0 到多个输入
    • 输出:至少 1 个输出
    • 有穷性:有限的步骤里算出结果
    • 确定性:一个输入对应一个输出,结果确定
    • 可行性:能够解决实际问题
  • 算法的基本要求:
    • 正确性:能够得出正确的结果
    • 可读性:能够被看懂
    • 健壮性:对于各种情形算法都有效
    • 时间复杂度:消耗的时间
    • 空间复杂度:占用的内存

3. 数组的基本作用

顺序存储的线性结构称为数组

数组的使用

  • 下标从 0 开始,下标最大值为(数组长度-1)
  • 数组创建方式:
    • int[] arr = new int[3];
      • int 规定了数组中元素的类型
      • 3 规定了数组的长度
      • arr[0] = 1; // 为数组中指定位置赋值
    • int[] arr = new int[]{1, 2, 3 };
      • 创建数组的同时给数组赋值

4. 数组元素的添加

动态扩容

解决数组元素不可变的问题

    1. 新建一个数组,长度为原数组长度+1
    1. 将原数组中的元素逐个赋值到新数组
    1. 将目标元素添加到新数组的末尾
    1. 用新数组替换原数组

5. 数组元素的删除

    1. 创建一个新数组,长度为原数组长度-1
    1. 将原数组中除要删除元素之外的元素,逐个赋值给新数组
    1. 用新数组替换原数组

6. 面向对象的数组

  • 在对象数组中创建一个数组成员变量,实际操作都在这个成员变量中进行
  • 主要操作:
    • 向数组末尾添加元素
    • 删除指定位置的元素
    • 获取指定位置的元素
    • 插入一个元素到指定位置
    • 为数组中指定位置赋值

7. 查找算法之线性查找

  • 遍历每一个元素,依次与目标值对比

8. 查找算法之二分法查找

  • 适用范围:有序数组
  • 步骤:
      1. 数组开始位置为 0,结束位置为数组长度 -1
      1. 通过开始位置和结束位置获取中间位置的值
      1. 将中间值与目标值对比
      • 中间值 > 目标值:将结束位置左移到中间位置-1,继续向左查找更小的值
      • 中间值 < 目标值:将开始位置右移到中间位置+1,继续向右查找更小的值
      • 中间值 = 目标值:中间值就是要查找的值,返回中间值下标
      1. 重复步骤 2 和 3,直至找出目标位置或者遍历完数组

10. 栈

数组实现栈的思路

  • 向数组末尾添加元素
  • 从数组末尾取元素
  • 依次实现下列方法:
    • push
    • pop
    • peek
    • isEmpty

11. 队列

数组实现队列的思路

  • 在数组末尾加入元素
  • 在数组开头取出元素
  • 依次实现下列方法
    • add
    • poll
    • isEmpty

12. 单链表

  • 定义节点类 Node,包含以下成员变量
    • int data:节点内容/数据
    • Node next:下一个节点,类型也是节点
  • 为节点类添加下列方法
    • append // 向链表末尾添加
    • next // 获取当前节点的下一个节点
    • getData // 获取节点的数据
    • isLast // 判断当前节点是否为最后一个节点

13. 删除单链表中的节点

  • 删除当前节点的后继节点
    • 获取后继节点的后继节点
    • 将当前节点的后继节点指向新的后继节点
    • 原有后继节点与前置和后继节点都失去了联系,达到了删除效果

14. 在单链表中插入一个节点

  • 让当前节点的后继节点指向要插入的节点
  • 要插入的节点后继节点指向原后继节点
  • 新的连接关系:当前节点-->插入节点-->原后继节点

15. 循环链表

  • 链表最后一个节点的后继节点指向链表的头节点
  • 实现下列方法
    • next 获取后继节点
    • getData 获取当前节点值
    • after 插入一个新节点

16. 循环双链表

  • 每一个节点都会记录其前置节点和后继节点
  • 三个成员变量
    • 上一个节点
    • 下一个节点
    • 当前节点数据
  • 实现下列方法
    • after 新增节点
    • next 获取后继节点
    • pre 获取前驱节点
    • getData 获取当前节点值

17. 递归和斐波那契数列

  • 递归就是在函数内部调用该函数本身
  • 斐波那契数列:1 1 2 3 ...
    • 从第三项起,每一项的值都是前两项之和

18. 汉诺塔问题

  • 三根柱子 + n 个盘子
  • n 个盘子一开始都在第一根柱子上
  • 每次只能移动一个盘子
  • 用最少的步数将 n 个盘子从第一根柱子移动到第三根柱子
  • 解决思路
    • 求出只有 1 个盘子的情况
    • 求出只有 2 个盘子的情况
    • n 个盘子的情况都可以简化成 2 个盘子的情况

19. 算法的时间复杂度和空间复杂度

  • 时间复杂度:运行时占用时间
  • 空间复杂度:运行时占用内存
  • 一个算法中语句需要执行的次数,称为语句频度,记为 T(N)
  • 随着执行次数增多,时间复杂度估算时可以忽略以下内容
    • 忽略常数项
      • 在坐标轴上画出曲线
      • 随着 n 的增大
        • 2n+20 和 2n 两条曲线会趋向重合
        • 3n+10 和 3n 两条曲线会趋向重合
      • 在 n 较大时,常数项的影响可以忽略
    • 忽略低次项
      • 在坐标轴上画出曲线
      • 随着 n 的增大
        • 2n^2 + 3n + 10 和 2n^2 两条曲线都趋向 n^2
        • n^2 + 5n + 20 和 n^2 两条曲线都趋向 n^2
      • 在 n 较大时,低次项的影响可以忽略
    • 忽略系数
      • 在坐标轴上画出曲线
      • 随着 n 的增大
        • 3n^2 + 2n 和 5n^2 + 7n 两条曲线趋向重合
        • n^3 + 5n 和 6n^3 + 4n 两条曲线趋向重合
      • 在 n 较大时,稀疏的影响可以忽略
  • 大 O 表示法
    • T(n) 表示算法中基本操作语句的重复执行次数是问题规模 n 的函数
    • 如果有一个辅助函数 f(n)
    • 使得 n 趋近于无穷大时,T(n) 和 f(n) 的极限值为不等于 0 的常数
    • 则称 f(n) 是 T(n) 的同数量级函数,记做 T(n) = O(f(n))
    • O(f(n)) 称为算法的渐进时间复杂度,简称时间复杂度
  • 常见的时间复杂度
    • 常数阶 O(1)
    • 对数阶 O(log2n)
    • 线性阶 O(n)
    • 线性对数阶 O(nlog2n)
    • 平方阶 O(n^2)
    • 立方阶 O(n^3)
    • 次方阶 O(n^k)
    • 指数阶 O(2^n)
    • 随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法执行效率越低
  • 计算时间复杂度的方法
    • 常数 1 代替所有加法常数
    • 只保留最高阶项
    • 去掉最高阶项的系数
  • 平均时间复杂度和最坏时间复杂度
    • 通常只讨论最坏时间复杂度

20. 排序算法之冒泡排序

常见排序算法总结

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

冒泡排序

  • 第一轮
    • 从第 1 个元素开始,比较相邻两个元素,将较大的元素后移,直到最大的元素移动到数组末尾
  • 第二轮
    • 从第 1 个元素开始,比较相邻两个元素,将较大的元素后移,直到本轮最大的元素移动到数组倒数第二个位置
  • 第三轮
    • 从第 1 个元素开始,比较相邻两个元素,将较大的元素后移,直到本轮最大的元素移动到数组倒数第三个位置
  • 第 n 轮
    • 每轮都从第 1 个元素开始,比较相邻两个元素,将较大的元素后移
    • 前一轮的最大元素不再参与下一轮比较,所以每一轮参与比较的元素都比上一轮少 1 个
    • 每一轮中最大元素都会从前往后移,类似气泡冒出水面,所以称为冒泡排序

21. 排序算法之快速排序

    1. 从数组中找出一个基准数
    1. 数组定义左右两个指针分别向中间移动
    1. 数组左侧的值比基准值大,则移到数组右侧
    1. 数组右侧的值比基准值小,则移到数组左侧
    1. 当左右两个指针重合时,当前轮排序结束
    1. 指针重合的位置将数组分为两部分,分别对两部分递归调用快速排序
    1. 重复上述步骤,直到排序完成

22. 排序算法之插入排序

  • 将数组分为未排序和已排序两部分
  • 从数组第二个元素位置开始
  • 每次从未排序部分取出第一个数字
  • 将其按规定顺序插入已排序部分
  • 同时插入位置之后的数字依次后移 1 位
  • 重复上述步骤,已排序部分逐渐向右扩大,直到所有数字都正确排序为止

23. 排序算法之希尔排序

  • 插入排序的问题
    • 如果待插入的数字,比已排序部分所有数字都小
    • 那么已排序部分就要进行大量的元素后移操作,效率较低
  • 希尔排序
    • 取某个数字作为步长,按步长对数组进行插入排序
    • 排序完成后,步长按规律递减
    • 用新步长进行下一轮插入排序
    • 重复上述步骤,直到步长变成 1,进行最后一轮普通的插入排序为止

24. 排序算法之选择排序

  • 将数组看作有序和无序两部分
  • 从第一个元素开始,在无序部分找出最小的元素
  • 将最小的元素与无序部分的第一个元素交换位置
  • 重复上述步骤,直到数组完全有序为止

25. 排序算法之归并排序

  • 归并方法
    • 原数组已经被分为两部分,每部分都各自有序
    • 创建一个与原数组等长的临时数组
    • 依次从两部分中取出元素进行对比,按照顺序放入临时数组
    • 所有元素都放入新数组后,整个数组已经排好序
    • 将临时数组重新赋值给原有数组
  • 递归部分
    • 将原数组折半划分为两部分
    • 依次对两部分递归调用递归算法
    • 直到数组不可再分

26. 排序算法之基数排序

  • 思路
    • 第一轮按所有元素的个位数字排序
    • 第二轮按所有元素的十位数字排序
    • 以此类推
    • 当按照数组中元素的最大位数排序之后,最终得到 1 个有序的数组
  • 举例
    • 例如数组 [5, 1, 72, 36, 101]
    • 为便于理解,想象元素空缺的位数上都是 0
    • 把数组写成如下形式
    • 排序前的原始数组 [005, 001, 072, 036, 101]
    • 第一轮按个位排序 [001, 101, 072, 005, 036]
    • 第二轮按十位排序 [001, 101, 005, 036, 072]
    • 第三轮按百位排序 [001, 005, 036, 072, 101]
    • 每轮排序后,位数相同的数字,相对顺序不会改变
    • 如第一次按照个位排序后,两个个位数字 1 和 5
    • 1 在接下来的几轮排序过程中,总是位于 5 的前面
    • 所有排序结束后,就得到了按照数字整体大小排列的数组

27. 基数排序之队列实现

  • 26 节的基数排序中,我们使用二维数组来表示桶
  • 桶中的元素有先进先出的特点,可以将二维数组换成队列

28. 树结构概述

数据结构的特点:

  • 线性结构:
    • 顺序存储:添加删除耗时
    • 链式存储:查找耗时
  • 树结构:
    • 解决了顺序存储和链式存储的上述问题

树的基本概念:

  • 根结点:起始节点
  • 双亲节点(即父节点):有子节点的节点
  • 子节点:向上溯源,有双亲节点的节点
  • 路径:从根结点到指定节点所要经过的所有节点
  • 节点的度:子节点的个数
  • 节点的权:节点的数值
  • 叶子节点:没有子节点的节点,即度为 0 的树
  • 子树:树中包含的树
  • 层:把根结点看作第一层,根结点的子树为第二层,树有多少代,就有多少层
  • 树的高度:树的最大层数
  • 森林:多棵树组成一个森林

29. 二叉树概述:

  • 概念:

    • 任何一个节点,子节点的数量不超过 2,这棵树就是二叉树
    • 二叉树的左右节点顺序不同,视为不同的两棵树
  • 满二叉树:

    • 所有叶子节点都在最后一层
    • 且总的节点个数为 2^n-1
    • n 是树的高度
  • 完全二叉树:

    • 所有叶子节点都在最后一层或倒数第二层
    • 且最后一层的叶子节点在左边连续
    • 倒数第二层的叶子节点在右边连续
    • 数节点确认:
      • 从左向右从上到下数节点
      • 数到最后一个节点
      • 完全连续没有间断就是完全二叉树

30. 创建二叉树

二叉树的存储结构

  • 链式存储
    • 创建二叉树
    • 添加节点
    • 查找节点
    • 树的遍历
    • 删除节点
  • 顺序存储

二叉树的形态

  • 空树:无节点
  • 左斜树:所有节点都在左侧
  • 右斜树:所有节点都在右侧

31. 树的遍历

  • 三种遍历形式:
    • 根据根结点的位置确定顺序
    • 前序:根结点-->左节点-->右节点
    • 中序:左结点-->根节点-->右节点
    • 后序:左结点-->右节点-->根节点

32. 二叉树中节点的查找(链式存储)

  • 与二叉树遍历方法类似

33. 删除二叉树的子树(链式存储)

  • 递归删除

34. 顺序存储的二叉树介绍

  • 顺序存储二叉树通常只考虑完全二叉树

性质

  • 第 n 个元素的左子节点是 2*n+1
  • 第 n 个元素的右子节点是 2*n+2
  • 第 n 个节点的父节点是 (n-1)/2

35. 顺序二叉树的遍历

  • 与链式存储二叉树的遍历相似,以前序遍历为例
    • 双亲节点 index
    • 左子节点 2*index+1
    • 右子节点 2*index+2
  • 需要传入一个参数,确定遍历的起点

36. 常用排序算法之堆排序

堆的概念

  • 大顶堆:每个节点都大于等于其左右孩子节点的值
  • 小顶堆:每个节点都小于等于其左右孩子节点的值

堆排序的应用

  • 升序使用大顶堆
  • 降序使用小顶堆

如何将顺序存储的二叉树转成大顶堆

从左至右,从上至下调整

    1. 从最后一个非叶子节点开始调整
    1. 将这个非叶子节点与其子节点对比,检查是否最大
    1. 如果不是,交换二者位置
    1. 交换位置后原有的堆结构发生了变化
    1. 对调整后的最大非叶子节点重复步骤 1~3
    1. 循环遍历一个顺序存储的二叉树,对每一个非叶子节点执行步骤 1~4

堆排序的步骤(以大顶堆为例)

    1. 将大小为 n 的顺序存储二叉树调整成一个大顶堆
    1. 将数组第 0 个数和第 n 个数交换
    1. 将数组大小递减 1,对递减后的数组重复执行 1~2

37. 线索二叉树

  • 顺序存储二叉树遍历到某个节点时,无法知道它的前驱节点和后续节点
  • 利用二叉树节点的空链域存储前驱或者后继节点的指针,这些指针就称为线索
  • 当某个节点没有左子节点时,将左指针指向它的前一个节点
  • 当某个节点没有右子节点时,将右指针指向它的后一个节点
  • 线索化二叉树时,可以通过标记的方式,说明指向的是前驱/后继节点还是孩子节点

38. 线索二叉树的代码实现

    1. 创建两个变量,分别用于标识左子节点和右子节点的类型
    • 默认 0 表示指针指向孩子节点
    • 1 表示当前指针指向前驱或后继节点
    1. 创建一个变量,临时存储前驱节点
    1. 对左子节点和右子节点递归调用线索化方法
    1. 对当前节点的进行线索化:
    • 如果左子节点为空,将空指针指向前驱节点,左指针类型标识改为 1
    • 如果前驱节点的右子节点为空,将空指针指向当前节点,前驱节点的右指针类型标识改为 1
    1. 线索化结束后,让前驱节点指向当前节点,供下一轮使用

39. 线索化二叉树的遍历

思路:

  • 中序遍历,向左前溯,找到第一个被线索化的节点
  • 不断输出后继节点的值,直到没有后继节点
  • 找到最后一个后继节点的右子节点,继续下一轮查找和输出

步骤

    1. 不断前溯左子节点,直至找到第一个被线索化的节点
    1. 从这个节点开始,不断查找后继节点并输出节点的值
    1. 找到最后一个后继节点的右子节点,重复步骤 1 和 2,直到节点为空

40. 赫夫曼树概述

  • 赫夫曼编码是数据压缩的重要方法
  • 叶结点的带权路径:
    • 从根结点出发,到达某个叶结点时,经过的节点数量,乘以叶结点的权值
    • 如叶子节点 A 的权值为 9,从根结点到达 A 节点,经过了 2 个节点,A 的权值就是 2*9=18
  • 树的带权路径长度:
    • WPL:weighted path length
    • 树中所有叶子节点带权路径之和
  • 最优二叉树:
    • WPL 最小时,称为最优二叉树,也叫赫夫曼树
    • 权值越大的节点离根结点越近,这样才能保证带权路径尽可能小

41. 赫夫曼树的流程分析

    1. 将数组中的每个元素都转化为二叉树,初始状态每棵二叉树只有一个节点
    1. 将数组中的二叉树按根结点的权值正序排列
    1. 从数组中取出根结点权值最小的两棵二叉树
    • 将这两棵二叉树的根结点视为孩子节点,为它们创建一个父节点
    • 父节点的权值是两个孩子节点的权值之和
    • 新的父节点和原先的两棵二叉树组成了一棵新的二叉树
    1. 将新创建的二叉树插入数组
    1. 重复步骤 2~4,每次取出两个元素,放回一个元素,直到数组剩下一个元素为止
    • 剩下的这个元素,就是整棵赫夫曼树的根结点

42. 代码实现赫夫曼树

    1. 将数组中的所有元素转化为二叉树
    1. 取出数组中根结点权值最小的两棵二叉树
    1. 用两棵二叉树的根结点作为孩子节点,创建一棵新的二叉树
    • 二叉树根结点的权值是两棵孩子节点权值之和
    1. 移除数组中取出的两棵二叉树
    1. 将新创建的二叉树放入数组
    1. 当数组中的元素大于 1 时,循环执行步骤 2~5

43. 赫夫曼编码原理分析

  • 通信和压缩领域应用非常广泛
can you can a can as a can canner can a can
  • 通信领域中信息的处理
    • 定长编码:
      • 99 97 110 32 121 ... 32 97 32 99 97 110 46
      • 单词-->ASIIC 编码-->每个数字都转成 8 位的字节
      • 01100011 01100001 ... 00101110
      • 缺点:固定长度,传输内容太多
    • 非定长编码:
      • 计数:r:1 s:1 .. n:8 :11 a:11
      • 0=a, 1= , 10=n, 11=c ... 10=r
      • 将字符串中每个字符出现的次数表示出来
      • 编码:
        • 出现次数多的字符用较少位的字节来表示
        • 出现次数少的字符用较多位的字节来表示
      • 前缀编码:字符的编码都不能是其他字符编码的前缀
      • 前缀编码才能进行解码
    • 赫夫曼编码:
      • 将字符串中每个字符出现的次数表示出来
        *r:1 s:1 .. a:11
      • 将字符作为节点的数据,出现次数作为节点的权值
      • 出现次数多的字符靠近根结点,编码长度较短
      • 将左连接定义为 0,右连接定义为 1,树的路径就有了编码
      • 赫夫曼树的路径是唯一的,因此每个字符的编码都是唯一的

44~45. 数据压缩之创建赫夫曼树

创建节点类 Node:

  • 属性:
    • int weight 权值,某个字符出现了多少次
    • Node left 左子节点
    • Node right 右子节点
    • Byte data 当前节点对应的字符
      • 采用包装类 Byte 可以定义空值
  • 构造方法:
    *public Node(Byte data, int weight)

赫夫曼编码方法:

  • 共经历了 6 次形态转换
    1. 字符串 --> 未压缩的 byte 数组
    1. 未压缩的 byte 数组 --> 二叉树节点列表
    1. 二叉树节点列表 --> 赫夫曼树
    1. 赫夫曼树 --> 赫夫曼编码表
    1. 字符数组 + 赫夫曼编码表 --> 二进制字符串
    1. 二进制字符串 --> 压缩后的 byte 数组

1. 字符串 --> byte 数组

  • 调用 String 对象的 getBytes() 方法

2. byte 数组 --> 二叉树节点列表

  • 创建一个 HashMap,键类型是 Byte,值类型是 Integer
  • 遍历 byte 数组,通过 HashMap 存储并统计单个 byte 出现的次数
  • 从 HashMap 中取出对应的键值对
  • 以 Byte 值作为节点数据,出现次数作为节点权值
  • 每个键值对都转为一个二叉树根节点 Node
  • 将所有二叉树节点存入列表备用

3. 二叉树节点列表 --> 赫夫曼树

    1. 遍历 Node 列表
    1. 按 Node 权值 weight 降序对列表排序
    1. 取出列表中权值最小的两个元素,即列表倒数两个元素
    1. 将两个元素作为孩子节点创建一个父节点,父节点的权值是两个孩子节点权值之和
    1. 同时将父节点的左右指针指向两个孩子节点
    1. 从原列表中删除第 3 步中取出的两个权值最小的元素
    1. 将新建的节点存入列表
    1. 当列表中元素数量大于 1 时,重复步骤 2~6
    1. 最终列表中只剩下一个元素,这个元素就是赫夫曼树的根结点

4. 赫夫曼树 --> 赫夫曼编码表

    1. 新建一个 HashMap 对象记录赫夫曼编码表
    • 键:赫夫曼树上某个节点的键,即字符
    • 值:赫夫曼树根节点到达当前字符的路径
      • 到达左子树的路径用 0 表示,到达右子树的路径用 1 表示
      • 路径变成一个由 0 和 1 组成的二进制字符串
      • 这样每个节点得到的二进制字符串都是唯一的
    1. 遍历赫夫曼树,将赫夫曼树上节点的相关信息转录到赫夫曼编码表

5. 字符数组 + 赫夫曼编码表 --> 二进制字符串

    1. 遍历原字符数组
    1. 对照赫夫曼编码表,获取每个字符对应的赫夫曼编码
    1. 将获取到的编码拼接到单个字符串
    1. 最终字符数组转成了一个遵循赫夫曼编码表的二进制字符串

6. 二进制字符串 --> 压缩后的 byte 数组

    1. 以 8 为步长遍历二进制字符串
    • 8 位二进制字符串 --> 十进制数字 --> byte 字符
    • 将新的 byte 字符存入新的字符数组中
    1. 最终得到一个按赫夫曼编码表压缩后的字符数组

46. 使用赫夫曼编码进行解码

  • 共进行了 2 次形态变化
    1. 字符数组 --> 二进制字符串
    • 1.1) 遍历字符数组
    • 1.2) 将每个字符都转为 8 位的二进制字符串
      • 如果正整数不够 8 位,数字前用 0 填充
    • 1.3) 将所有字符的二进制字符串拼接成一个完整的二进制字符串
    1. 二进制字符串 + 赫夫曼编码表 --> 原字符数组
    • 2.1) 将原赫夫曼编码表的键和值互换
      • 即原先键是 Byte,值是 String
      • 互换后键是 String,值是 Byte
    • 2.2) 遍历二进制字符串,以各种可能的组合在赫夫曼编码表中查找原 byte
    • 2.3) 将 byte 存入列表后转成数组

47 使用赫夫曼编码压缩文件

    1. 文件来源路径 --> 创建输入流
    • new FileInputStream(文件来源路径)
    1. 创建和输入流指向文件大小一致的 byte 数组
    • byte[] b = new byte[FileInputStream 对象.available()]
      • available() 在操作前得知数据流大小
    1. 读取文件,关闭输入流
    1. 调用赫夫曼编码方法对 byte 数组编码
    1. 文件输出路径 --> 创建输出流
    • new FileOutputStream(文件输出路径)
    • new ObjectOutputStream(FileOutputStream 对象)
    1. 将压缩后的 byte 数组写入文件
    1. 将赫夫曼编码表写入文件
    1. 关闭输出流

48. 文件的解压

    1. 创建一个输入流对象,读取压缩文件
    • new FileInputStream(压缩文件路径)
    • new ObjectInputStream(FileInputStream 对象)
    1. 读取压缩文件中的 byte 数组
    • byte[] b = (byte[]) ObjectInputStream 对象.readObject()
    1. 读取压缩文件中的赫夫曼编码
    • Map<Byte, String> codes = (Map<Byte, String>) ObjectInputStream 对象.readObject()
    1. 关闭输入流
    1. 通过赫夫曼编码将读取出来的 byte 数组解码为原 byte 数组
    1. 创建一个输出流对象
    • new FileOutputStream(输出文件路径)
    1. 将解码后的 byte 数组写入文件
    • FileOutputStream 对象.write(byte 数组)
    1. 关闭输出流

49. 二叉排序树

线性结构

  • 顺序存储,不排序
    • 查找困难
  • 顺序存储,排序
    • 二分查找效率高
    • 删除插入困难
  • 链式存储
    • 无论是否排序,查找都困难

树形结构

  • 二叉排序树,BST
    • 概念
      • 也叫二叉查找树,二叉搜索树
      • 对于排序树中的任何一个非叶子节点
      • 左子节点比当前节点小
      • 右子节点比当前节点大
    • 查找和插入删除性能都较高

50. 创建二叉排序树 & 添加节点

  • 待添加的节点
      1. 如果当前节点为空 --> 赋给当前节点
      1. 如果值比当前节点小
      • 左子节点为空 --> 赋给左子节点
      • 左子节点非空 --> 递归调用左子节点的添加方法
      1. 如果值比当前节点大
      • 右子节点为空 --> 赋给右子节点
      • 右子节点非空 --> 递归调用右子节点的添加方法
  • 二叉排序树的中序遍历正好是从小到大排列

51. 二叉排序树中查找节点

  • 要查找的值 == 当前节点的值 --> 返回当前节点
  • 要查找的值 < 当前节点的值 --> 递归调用左子节点的查找方法
  • 要查找的值 > 当前节点的值 --> 递归调用右子节点的查找方法

52. 删除叶子节点

  • 目标节点没有孩子节点
  • 查找目标节点
  • 查找目标节点的父节点
  • 将目标节点与父节点断开连接

53. 删除只有一棵子树的节点

  • 查找目标节点
  • 查找目标节点的父节点
  • 将目标节点的子树与父节点建立连接

54. 删除有两棵子树的节点

  • 查找目标节点
  • 查找目标节点的最小子树
  • 删除目标节点的最小子树,并返回最小子树的值
  • 用最小子树的值替换目标节点的值

55. 平衡二叉树概述

  • 二叉排序树的问题
    • 如果将连续递增或递减的数组转为二叉排序树
    • 二叉排序树的节点都在同一边,查询效率与链表差不多
  • 平衡二叉树
    • 首先平衡二叉树是一棵二叉排序树
    • 左子树和右子树高度差的绝对值不超过 1
    • 左子树和右子树也是平衡二叉树

56. 构建二叉平衡树之单旋转

  • 根据左右节点高度差的绝对值,判断当前节点是否为平衡二叉树
  • 左左:(左子树高度 - 右子树高度) > 1
    • 顺时针右旋
        1. node --> newNode
        1. node.right --> newNode.right
        1. node.left.right --> newNode.left
        1. node.left.value --> node.value
        1. node.left.left --> node.left
        1. newNode --> node.right
  • 右右:(右子树高度 - 左子树高度) > 1
    • 顺时针左旋
        1. node --> newNode
        1. node.left --> newNode.left
        1. node.right.left --> newNode.right
        1. node.right.value --> node.value
        1. node.right.right --> node.right
        1. newNode --> node

57. 构建平衡二叉树之双旋转

  • node.left.left 高度 < node.left.right 高度
      1. left 左旋转
      1. node 右旋转
  • node.right.right 高度 < node.right.left 高度
      1. right 右旋转
      1. node 左旋转

58. 多路查找树-计算机数据的存储原理

  • 应用于内存,小数据量的树结构
    • 二叉树
    • 线索二叉树
    • 赫夫曼树
    • 二叉排序树
    • AVL 树
  • 应用于磁盘存储,数据量大的树结构
    • 多路查找树
      • 2-3 树和 2-3-4 树
      • B 树和 B+ 树

数据存储方式

  • 内存
    • 优点:
      • 电信号保存信息,不存在机器操作
      • 访问速度快
    • 缺点:
      • 造价高
      • 断电后数据丢失
      • 一般作为 CPU 告诉缓存
  • 磁盘:
    • 优点
      • 造价低,容量大
      • 断电数据不丢失
    • 缺点:
      • 存储介质特性和机械运动耗费时间,磁盘速度慢
    • 磁盘的预读
      • 为了减少 I/O 操作,磁盘通常不是按需读取
      • 每次都会预读,顺序向后读取一定长度的数据放入内存
        • 计算机科学中的局部性原理:一个数据被用到时,其附近的数据通常也会被用到
      • 预读的长度一般为页(page)的整数倍
      • 页是计算机管理存储的逻辑块
      • 硬件及操作系统将主存和磁盘存储区分割为连续的大小相等的块
      • 每个存储块为一页
      • 页的大小一般为 4k
      • 主存和磁盘以页为单位交换数据
    • B 树存储
      • 利用磁盘预读原理,将一个节点的大小设为一个页
        • 单个节点进行横向扩展
      • 每个节点只需一次 I/O 就可以完全载入
    • 二叉树与 B 树对比
      • 二叉树
        • 树高为 5 的二叉树
        • 节点数=2^5-1 = 31 个
      • B 树
        • 树高为 2
        • 第一层 1 个节点,横向扩展为 3 个节点
        • 第二层 4 个节点,每个节点横向扩展为 7 个节点
        • 节点树=1×3 + 4×7 = 31
      • 同样的节点树,B 树只需要两层即可
      • 如果将树的度,即子节点的个数,设为 1024
        • 树高 2:1024^2 = 1,048,576 ≈ 100 万
        • 树高 3:1024^3 = 1,073,741,824 ≈ 1 亿
        • 树高 4:1024^4 = 1,099,511,627,776 ≈ 1000 亿
        • 600 亿 < 1000 亿,至多 4 次 I/O 即可查询到

59. 2-3 树的插入原理

  • B 树中所有的叶节点都在同一层
  • 2-3 树是 B 树的一种特例
    • 有两个子节点的节点叫做二节点
    • 有三个子节点的节点叫做三节点
    • 二节点要么有两个子节点,要么没有子节点
    • 三节点要么有三个子节点,要么没有子节点
    • 2-3 树有二节点和三节点 2 种情况
    • 2-3-4 树有二节点、三节点和四节点 3 种情况
  • 添加新节点
    • 如果叶节点无法在同一层
    • 先向上一层拆解
    • 如果现有层都满了,则增加一层

60. B 树和 B+ 树原理

概念

  • 2-3 树、2-3-4 树、2-3-4-5 树,等等,统称为 B 树
  • B 树中最大节点的数字,称为 B 树的阶
  • 2-3 树是 3 阶 B 树,2-3-4 树是 4 阶 B 树

B+ 树

  • 在 B 树之上的改变
    • 非叶节点只存储索引信息,不存储数据
    • 叶子节点最右边的指针指向下一个相邻的叶节点
    • 所有叶节点组成一个有序链表
  • 设计原理
    • 更多的索引 --> 更快的查询

61. 哈希表概述

  • 线性查找
    • 逐个对比,数据量大时效率低
  • 二分查找:
    • 效率更高
    • 要求数组有序
  • 存储位置 <--> 关键字
    • 通过散列函数建立对应关系

62. 散列函数的设计

  • 设计原则
    • 计算简单
    • 分布均匀

常用方法

  • 直接定址法
    • 直接把关键字作为存储地址
    • 可能有空间分布不均匀的问题
    • 如果数字过大,甚至会超出编程语言的有效整数范围
  • 数字分析法
    • 通过特定规律,将数字转换成更方便存储的格式作为关键字
    • 需要事先知道数字的格式
    • 如手机号码只存后四位
  • 平方取中法
    • 将数字平方后取结果中间的数字作为关键字
    • 如 13*13 = 169,取中间数字 6
  • 取余法
    • 对数字取余数作为关键字
    • 按预计压缩范围来确定模数
  • 随机数法
    • 随机数函数产生数字作为关键字
    • 一般不用,数字随机,不便归类

63. 散列冲突的解决方案

开放地址法

  • 遇到冲突时,从当前地址后面查找合适的位置
  • 三种方式
    • 线性探测法
      • 在紧邻的位置放冲突的元素
      • 举例
        • x 位置已有元素,向后查找 x+1
        • x+1 位置有元素,再向后找 x+2
      • 问题:元素容易聚集在相邻的内存地址
    • 二次探测法
      • 第一次探测紧邻的位置
      • 第二次探测地址数字的平方
      • 举例:
        • x 位置被占用,向后查找 x+1
        • x+1 位置被占用,再向后找 (x+1)^2
        • 拓宽了探测步长,元素不容易聚集在一起
    • 再哈希法
      • 多个散列函数
      • 通常 3 个散列函数可以解决大部分的冲突
      • 如果仍然有冲突,可以再使用探测法

链地址法

  • 将冲突的元素在同个地址上存储为链表形式
    • 节点内容:元素本身
    • 节点指针:下一个元素的地址
  • 优点:存储地址就是散列表计算结果,更为直观
  • 实际应用中更多采用链地址法

64. 图结构

  • 点和线构成
  • 顶点 Vertex
    • 可以存储数据
  • 边 edge
    • 连接顶点,表示点之间的关系
  • 邻接顶点
    • 两个顶点通过一条边就可以连接
  • 路径
    • 从某一个顶点出发,经过的所有顶点
  • 无向图
    • 边没有方向
  • 有向图
    • 边有方向
  • 带权图
    • 边加上有意义的值
    • 如 A 城市到 B 城市的距离
    • A --> B 是一个有向带权图

65. 图结构代码实现

图的存储方式

  • 链表
    • 如果数据是对象,指针很难定义
  • 数组
    • 用列表存储顶点
    • 用邻接表存储顶点之间的关系
      • 类似链表的实现
        • 节点内容代表顶点
        • 指针指向下一个顶点
      • 类似矩阵的实现
        • 将顶点放到行列式中,任意两个顶点都能在矩阵中找到交叉点
        • 用数字表示两个顶点之间的关系
        • 如 0 表示不通,1 表示连通

66. 图的遍历原理

深度优先

  • 顺着路径一直查找,直到路径不通,再返回从第一个分叉的顶点处继续查找
  • 栈实现
      1. A 入栈,A 标记为已访问
      1. 按顺序查找连接
      • A --> B,连通,B 入栈,B 标记为已访问
        • B --> C,连通,C 入栈,C 标记为已访问
          • C --> D,不通,查找下一个
          • C --> E,不通,E 之后没有其他顶点
          • C 是栈顶元素,出栈
        • B --> D,连通,D 标记为已访问,D 入栈
          • D --> E,不通,E 之后没有其他顶点
          • D 是栈顶元素,出栈
        • B --> E,连通,E 入栈,E 标记为已访问
          • E 之后没有其他元素
          • E 是栈顶元素,出栈
        • B 是栈顶元素,检查 B 有无其他可能的连接
        • B 没有其他连接,出栈
      • A 是栈顶元素,检查 A 有无其他可能的连接
        • A 没有其他连接,出栈

广度优先

  • 把一个顶点所有的连接都找出来,再继续下一个顶点
  • 队列实现
      1. A 入队
      1. 查找 A 的所有连接,按顺序入队
      • A --> B,连通,B 入队
      • A --> C,连通,C 入队
      • A 无其他连接,A 出队
      1. A 出队后,B 是队首元素,从 B 开始查找
      1. 重复步骤 2~3,依次查找 B、C、D、E 所有顶点的所有连接

67. 图的遍历代码实现

    1. 从第 0 个顶点开始查找
    • 将第 0 个顶点标记为已访问
    • 将第 0 个顶点压入栈中
    1. 遍历顶点数组,按序检查邻近两个顶点之间的连通关系
    • 如果邻近顶点连通
      • 将目标顶点压入栈中,标记为已访问
      • 出发顶点和目标顶点同时后移 1 位
        • 如 A --> B 连通
        • 将出发顶点从 A 顺延到 B,检查 B --> C 是否连通
    • 如果邻近两个顶点不通,出发顶点不变,将目标顶点的指针后移一位
      • 如 C --> D 不通,将目标顶点 D 后移一位,检查 C --> E 是否连通
    1. 如果单条路径检查完毕,则弹出栈顶元素
    1. 如果栈此时非空,将出发顶点指针指向新的栈顶元素
    1. 重复执行步骤 2~4,直到栈为空