数据结构和算法

经典算法题

字符串匹配问题： 暴力匹配 KMP算法 八皇后：回溯算法 汉诺塔：分治算法 马踏棋盘：图的深度优化遍历算法(DFS)+贪心算法

线性结构和非线性结构

数据结构包括线性结构和非线性结构

线性结构

最常用的线性结构

特点：数据之间存在==一对一==的线性关系

存储结构：

• 顺序存储结构（数组）：顺序存储的线性表称为顺序表，==顺序表中的存储元素是连续的（内存分配的地址是连续的）==

• 链式存储结构（链表）：链式存储的线性表称为链表，==存储元素不一定连续==

• 常见的线性结构：数组，队列，链表，栈

非线性结构

不是一对一的关系

常见的非线性结构：二维数组，多维数组，广义表，树结构，图结构

稀疏数组和队列

稀疏数组(sparseArray)

如：用二维数组记录棋盘数据，有很多0，记录了很多没有意义的数据

基本介绍： 当一个数组中大部分元素是0，或者为同一个值的数组时，可以使用稀疏数组来保存数组。

稀疏数组的处理方法：

• 1.记录数组一共有几行几列，有多少个不同的值

• 2.把具有不同值的元素的行列及值记录在一个小规模数组中，从而缩小程序的规模

稀疏数组转二维数组：

• 1.遍历原始二维数组，得到有效数据的个数sum

• 2.根据sum创建sum创建sparsearr int[sum + 1][3]

• 3.将二维数组的有效数据存到一维数组

二维数组转稀疏数组：

• 1.先读取稀疏数组的第一行，根据第一行的数据，创建原始二维数组

• 2.再读取稀疏数组后几行的数据，并赋给原始的二维数组

代码实现

package sparsearray;

public class SparsearrDemo1 {
	
	public static void main(String[] args) {
		
		int[][] arr = new int[11][11];
		
		arr[1][2] = 1;
		arr[2][3] = 2;
		
		System.out.println("----------遍历原始二维数组------------------------");
		
		for (int[] is : arr) {
			for (int is2 : is) {
				
				System.out.print(is2);
			}
			System.out.println();
		}
		
		System.out.println("-------------遍历稀疏数组-------------------");
		
		int[][] tmp = getSparsearr(arr);
		
		
		System.out.println("-------------遍历恢复了的二维数组--------------------------------");
		
		recoverArr(tmp);
		}
	
	public static int[][] getSparsearr(int[][] arr){
		
		int sum = 0;
		
		for (int i = 0; i < arr.length; i++) {
			
			for (int j = 0; j < arr[i].length; j++) {
				
				if(arr[i][j] != 0) {
					sum++;
					
				}
				
			}
			
		}
		
		int[][] sarr = new  int[sum + 1][3] ;
		
		int count = 0;
		
		sarr[0][0] = 11;
		sarr[0][1] = 11;
		sarr[0][2] = sum;
		
		
		for (int i = 0; i < arr.length; i++) {
			
			for (int j = 0; j < arr[i].length; j++) {
				
				if(arr[i][j] != 0) {
					sum++;
					count++;
					
					sarr[count][0] = i; //非0数据的行数
					sarr[count][1] = j; //非0数据的列数
					sarr[count][2] = arr[i][j]; //非0数据的结果值
					
				}	
			}	
		}
		
		for (int[] is : sarr) {
			for (int is2 : is) {
				System.out.print(is2+" ");
			}
			System.out.println();
		}	
		
		return sarr;
	}
	
	public static void recoverArr(int[][] sparsearr) {
		
		int[][] arr = new int[sparsearr[0][0]][sparsearr[0][1]];
		
		for (int i = 1; i < sparsearr.length; i++) {
			
			arr[sparsearr[i][0]][sparsearr[i][1]] = sparsearr[i][2];
		}
		
//		System.out.println("-------------恢复后的数组------------------------");
		
		for (int[] is : arr) {
			for (int is2 : is) {
				System.out.print(is2 + " ");
			}
			System.out.println();
		}
	}
}

队列

基本介绍

• 队列是一个==有序列表==，可以用==数组==或==链表==来实现

• 遵循==先入先出==的原则，即：先存入队列的数据要先取出，后存入的数据后取出

队列的一些特点：

1. 有序性：队列的元素是按照一定的顺序排列的，这种有序性使得队列能够被用来处理一些需要按照顺序进行的任务，比如打印机队列、计算机任务队列等。

2. 高效性：队列的先进先出特性使得队列能够高效地处理大量的数据。在处理数据时，队列能够保证数据的有序性，同时也能够保证数据的高效性。

3. 可扩展性：队列的特性使得它能够被轻松地扩展。如果需要处理更多的数据，只需要将数据添加到队列的末尾即可。

4. 并发性：队列的先进先出特性使得它非常适合用于并发编程。在并发编程中，队列可以被用来协调不同线程之间的执行顺序，从而避免出现竞争条件和死锁等问题。

数组模拟队列 Queue ：对象名 ，front ：初始值 -1，前端下标，rear ：初始值 -1，后端下标，最大容量 ：MaxSize

front 随着数据输入而改变 ， rear 随着数据输出而改变

• 将数据存入队列称为addQueue，addQueue有两个步骤

• 1.当front == rear（当前队列为空），尾指针往后移，rear + 1

• 2.当rear == MaxSize - 1,说明当前队列已满，不能再存入元素

(实现代码写在eclipse -> datastructure -> queue 中了)

优化：数组模拟环形队列

目前数组使用一次就不能用，没有复用的效果

将该数组使用算法，改造成环形队列 （通过取模的方式实现%）

1.front的含义调整 ：指向队列的第一个元素，front的初始值为0

2.rear的含义调整 ：指向队列的最后一个元素，需要在之后加一个置空位 （防止出现队列为空和满时，都是rear = front ，不好判断）

3.当队列为满时 ：（rear + 1）%MaxSize = front

4.当队列为空时 ：rear = front

5.队列中的有效元素个数 ：(rear + MaxSize - front) % MaxSize

链表（Linked List）

链表是有序的列表，在内存中的存储示意图：

• 链表是以结点的方式来存储的，==是链式存储==

• 每个节点包含 data域 ，next域 ，next域指向下一个节点

• 如图 ，==链表的各个节点不一定是连续存放的==

• 链表分带头节点的链表和没有头节点的链表，根据实际需求来确定

链表的特点：

1、插入删除效率高：.任意位置插入元素和删除元素效率较高，时间复杂度为O(1

2、灵活度高：链表不需要预先分配固定大小的空间，可以随着元素的增加自动扩容，因此不会出现内存不足的情况。

3、空间分散：在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续。

4、查找效率低：查找数据时效率低，时间复杂度为O(N)，因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到O(N)。

5、空间利用率高：空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高。

单链表的逻辑结构： 最后一个节点的next域为null

链表的应用：增删改查

单链表

（添加方法一）单链表按照加入顺序直接添加 通过遍历，直接加到尾部，比较简单 （添加方法二）单链表按顺序插入节点

• 通过遍历实现

• 新节点.next = temp.next

• temp.next = 新节点

注意：

• 如果使用这种方法添加节点，如果添加的两个节点是同一个元素，会导致temp.next = 新节点指向自身，从而进入死循环。

• bool类型的标识符很重要

单链表删除节点

注意：单链表只能从前往后找数据，不能从后往前找数据

单链表修改节点 1.通过遍历先找到该节点 2.根据temp.name = heronode.name修改

完成代码：存放在eclipse -> datastructure -> linkedlist

单链表常见练习题

• 1.求单链表中有效节点的个数
• 2.查找单链表的倒数第n个节点
• 3.单链表的反转 （使用辅助链表和辅助移动的节点）
  • 
• 4.从尾到头打印单链表 （使用栈）
  • 
  • stack.add(),进栈 ， stack.pop(),出栈
• 5.合并两个有序链表，并且合并后的链表依然有序

双向链表

单向链表的缺点：

• 查找的方向只能是一个方向，双向链表可以向前，向后查找
• 不能自我删除，需要找到前一个节点才能删除，需要靠辅助节点，而双向链表可以自我删除

双向链表的增删改查 注意点：双向链表可以直接找要删除的节点删除

关于双向链表按编号进行添加的作业

完成代码：存放在eclipse -> datastructure -> linkedlist -> DoubleLinkedList…

单向环形链表的应用

应用场景：josephu(约瑟夫，约瑟夫环问题)

单向环形链表的介绍

约瑟夫问题的解决思路

构建单向环形链表的思路

约瑟夫环出圈解决思路

完成代码：存放在eclipse -> datastructure -> linkedlist -> linkedlist.josephu

栈

栈的一个实际需求

栈的介绍 1.栈的英文：stack

2.栈是一个==先入后出==的有序列表（FILO-First in Last Out)

3.栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端为==变化的一端，称为栈顶（Top),另一端为固定的一端，称为栈底(Bottom)==

4.根据栈的定义，最先放入栈中元素在栈底，最后放入元素元素在栈顶，而删除元素刚好相反

5.出栈(pop)和入栈(push)的示意图：

栈的应用场景

• 子程序的调用
• 处理递归调用
• 表达式的转换与求值：中缀转后缀
• 二叉树的遍历
• 图形的深度优先(depth-first)搜索法

栈的快速入门 用数组模拟栈的入栈，出栈等操作

课堂练习 ： 用链表模拟栈

使用栈实现综合计算器（中缀表达式）

思路：

代码实现： 1.先实现一位数的运算 2.拓展到多位数运算

完成代码：存放在eclipse -> datastructure -> stack -> Calculator

课后练习：给表达式加入()

前缀，中缀，后缀（逆波兰）表达式

前缀表达式(波兰表达式)

• 前缀表达式又称波兰表达式，==前缀表达式的运算符位于操作数之前==
• 举例说明 ： (3 + 4) x 5 - 6 对应的前缀表达式是 - x + 3 4 5 6
• 

中缀表达式

• 中缀表达式就是常见的运算表达式，如 ：(3 + 4) x 5 - 6
• 中缀表达式的求值是我们人最熟悉的，但是对计算机来说不好操作（需要判断优先级），因此，在计算结果时，往往把中缀表达式转成其他表达式（一般是后缀表达式）

后缀表达式（逆波兰表达式）

• 后缀表达式又称逆波兰表达式，与前缀表达式类似，只是运算符位于操作数之后
• 举例说明 ： (3 + 4) x 5 - 6 对应的后缀表达式是 3 4 + 5 x 6 -
• 

逆波兰计算器 思路分析：

中缀表达式转后缀表达式 后缀表达式适合进行计算，但是不方便人阅读，因此在开发中需要将中缀表达式转换成后缀表达式

思路分析： 需要考虑的两个优先：

• 1.符号优先级
• 2.算式的顺序优先级
• 根据栈先入后出的特点，能够很好的实现顺序优先顺序的排序
• 再加上相应的比较方法就行了

递归

递归应用场景 迷宫回溯问题 : 小球能找到一条路，走到指定的终点

递归的概念 ==方法自己调用自己，每次调用时传入不同的变量==，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁

递归的调用机制

• 打印问题
• 阶乘问题 递归调用规则：
• 当程序执行到一个方法时，就会开辟一个独立的空间（栈）
• 每个空间的数据（局部变量）是独立的

递归能解决的问题类型 1.各种数学问题：八皇后，汉诺塔，阶乘，迷宫，球和篮子…

2.各种算法：快排，归并排序，二分查找，分治算法…

3.将用栈解决的问题 -> 递归代码比较简洁

递归需要遵守的重要规则 1.执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

2.方法的局部变量是独立的，不会相互影响（比如上面的例子中的n）

3.如果方法中使用的是引用类型变量( 比如数组 )，就会共享该引用类型的数据

4.==递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError，死龟了==

5.当一个方法执行完毕，或者遇到return，就会返回。==遵守谁调用，就将结果返回给谁==，同时当方法执行完毕或者返回时，该方法也就执行完毕

递归——迷宫问题 分析思路:

使用递归回溯给小球找路 1.map表示地图

2.i，j表示从地图的哪个位置出发(1,1)

3.如果小球能到map[6][5]的位置，说明通路找到了

4，找到通路返回true，没找到返回false

5.约定 ： 当map[i][j] 为0表示该点没有走过， 1表示墙，2表示为通路 ，3表示走不通的路

6.走迷宫制定的策略：下 -> 右 ->上 ->左，走不通就回溯到前一个点

代码实现 ：datastructure -> recursion -> MiGong

对迷宫问题的讨论 1.小球得到的路径，和程序员设置的找路策略有关 2.测试回溯现象 3.如何求出最短路径？

递归 - 八皇后问题（回溯算法） 问题描述：

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题（92种）。

思路分析：

• 理论上应该创建一个二维数组来代表棋盘，但是实际上可以通过算法，用一个一维数组解决问题
  • arr[8] = {0 , 4 , 7 , 5 , 2 , 6 , 1 , 3}
  • arr[i] = val : i+1表示第几个皇后（所处的行）, val+1 代表该皇后在该行处在第几列 代码实现 ： datastructure -> recursion -> Queue8

排序算法

介绍：

• 排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程

排序的分类:

• 内部排序：指将需要处理的所有数据都加载到内部存储器（内存）进行排序
• 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序
• 常见的排序算法 ：

算法的时间复杂度：

度量一个程序执行时间的两种方法

1.事后统计法：

• 先运行一遍程序，再计算该程序运行的时间
• 问题：
  • 要想对设计的算法的运行性能进行评估，需要实际运行该程序
  • 所得时间的统计量依赖于计算机硬件，软件等环境因素，==这种方式，需要同一台计算机在相同环境下运行，才能比较算法速度的快慢==

2.事前估算法：

• 通过分析某个算法的==时间复杂度==来判断哪个算法更优

时间频度 基本介绍: 一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。==一个算法中的语句执行次数称为语句频度或时间频度==，记为T(n)

举例：

举例：忽略常数项：

举例：忽略低次项：

举例：忽略系数：

时间复杂度

• 1.一般情况下，==算法中的基本操作语句的重复执行次数是问题规模n的某个函数==，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同量级函数。==记作T(n)=O(f(n))==,称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

• 2.T(n)不同，但时间复杂度可能相同。如T(n) = n^2 + 7n + 6 与T(n) = 3n^2 + 2n + 2 ，它们的T(n)不同，但时间复杂度相同都为O(n^2)

• 3.计算时间复杂度的方法：

  • 用常数1代替运行时间中的所有加法常数 T(n) = n^2 + 7n + 6 -> T(n) = n^2 + 7n + 1
  • 修改后的运行次数函数中，只保留最高阶项 T(n) = n^2 + 7n + 1 -> T(n) = n^2
  • 去除最高阶项的系数 T(n) = n^2 -> O(n^2)

常见的时间复杂度

平均时间复杂度和最坏时间复杂度

• 一般讨论时间复杂度均是最坏情况下的时间复杂度

算法的空间复杂度

• 实际开发中，用户是看程序执行的速度，一般都会用空间换时间，不会过多的考虑

冒泡排序(Bubble sorting)

基本介绍：

思路：

代码实现 ：/datastructure/sort/BubbleSort.java

选择排序(select sorting)

基本介绍： 选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的

基本思想:

选择排序思路分析图:

应用实例： 给牛排颜值

代码实现 ：datastructure/sort/SelectSort.java

插入排序(Insertion Sorting)

基本介绍： 插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的

基本思想:

思路图:

应用实例： 给小牛排成绩

代码实现 ：datastructure/sort/InsertSort.java

希尔排序(ShellSort)

简单插入排序的缺点： 如果要插入的元素是最后一个，就需要把把前面的数全部都移动一遍找到插入的位置

基本介绍： 希尔排序是希尔(Donald Shell)在1959年提出的一种排序算法。==希尔排序也是一种插入排序，是简单插入排序经过改进后的一个更高效版本，也称为缩小增量排序==

基本思想：

希尔排序法示意图：

两种实现方法 交换法（速度较慢） 移动法（速度较快）

快速排序(QuickSort)

基本介绍

• 通过左指针，右指针，pivot（中轴值），递归 来完成

归并排序(MergeSort)

基数排序

• 注意：基数排序是稳定排序

• 稳定排序 ： 需要排序的数组里存在两个相同的数，先后不同，排序完成后仍然遵循开始时的先后顺序

• 基数排序是经典的空间换时间的方法，占用内存很大，如果对海量数据排序时，容易造成OutofMemoryError

• 如果是有负数的数组，不能用基数排序，如果要用，需要进行改进

常用排序算法对比

查找算法

Java中常用的四种查找算法：

• 顺序（线性）查找
  • 使用的带查找的数组可以有序，也可以无序
  • 用循环遍历就行了，简单
• 二分/折半 查找
  • 只能对有序数组进行
  • 二分查找的思路分析：
• 插值查找

  • 原理介绍 ：

    • key:要查找的值(findVal)

  • 举例说明 ：

  • 注意事项 ： 关键字分布不均匀 ： 数值之间跳跃很大

• 斐波那契(黄金分割法)查找
  • 原理介绍 ： 还是在有序数组中才能用

哈希表（散列表）

• 基本介绍
  • 散列表（Hash table,也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
  • 哈希表的由来 ：
  • 数组 + 链表 构成的哈希表 ：
• 例题 : 有一个公司，当有新的员工来报道时，要求将该员工的信息（id，性别，年龄，名字）加入，当输入该员工的id时，要求查找到该员工的所有信息。
  • 要求 ：不使用数据库，速度越快越好（哈希表）
  • 实现思路 ：

树结构

• 二叉树 为什么需要树这种存储结构

• 数组存储方式分析

  • 优点 ： 可以通过==下标访问==，速度快。对于有序数组，还可使用二分查找提高检索速度
  • 缺点 ： 如果要检索某个具体值，或插入值会==整体移动==，效率较低
  • 分析 ：

• 链式存储方式的分析

  • 优点 ：在一定程度上对数组存储方式有优化（比如 ：插入一个数值节点，只需要将==插入==节点，链接到链表中即可，==删除效率也很好==）
  • 缺点 ： 在进行==检索时，效率依然较低==，比如（检索某个值，需要从头节点开始遍历）
  • 示意图 ：

• 树存储方式的分析

  • 能提高数据存储，读取的效率，比如二叉排列树（Binary Sort Tree）,既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度
  • 示意图 ：

• 树示意图

  • 树的常用术语 ：

• 二叉树

  • 二叉树的概念 ：
    • 树有很多种，每个节点==最多只能有两个子节点==的一种形式称为二叉树
    • 二叉树的子节点分为左节点和右节点
    • 
    • 如果该二叉树的==所有叶子节点都在最后一层==，并且节点总数 = ==2^n -1==,n为层数，则我们称为满二叉树
    • 完全二叉树 ： 叶子节点不一定在最后一层，但是从左到右连续
    • 
  • 二叉树的遍历
    • 使用前序，中序，后序对二叉树进行遍历
      • 前序遍历 ： 先输出==父节点==，再遍历左子树和右子树
      • 中序遍历 ： 左子树 -> ==父节点== -> 右子树
      • 后序遍历 ： 左子树 -> 右子树 -> ==父节点==
      • 小结 ： 看父节点的顺序确定
      • 实现思路 ：
  • 使用前序，中序，后序对二叉树节点进行查询
    • 实现思路 ：
    • 注意比较语句在程序中执行的顺序
  • 二叉树删除节点
    • 思路分析 ：
    • 思考题 ：

• 顺序存储二叉树

  • 从数据存储来看，数组存储方式和树的存储方式可以互相转化，即数组可以转化成树，树可以转化成数组 ：

  • 

  • 要求 : 以数组形式存储二叉树节点 ： arr : [1,2,3,4,5,6,7],在遍历数组arr时，以前，中，后序的方式进行节点的遍历

  • ==顺序存储二叉树的特点==：

    • 顺序二叉树通常只考虑完全二叉树
    • 第n个元素的左子节点为2 * n + 1
    • 第n个元素的右子节点为2 * n + 2
    • 第n个元素的父节点为(n - 1) / 2
    • n : 表示二叉树的第几个元素（从0开始编号，跟数组保持一致）

  • 应用场景 ： 堆排序

• 线索化二叉树

  • 基本介绍 ：

    • n个节点的二叉链表中含有 n + 1 (公式 : 2n - (n - 1) = n + 1) 个空指针域。利用二叉链表中的空指针域，存放指向该节点的在某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为 线索）

    • 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）.根据线索性质的不同，分为前序，中序，后序线索二叉树三种。

    • 一个节点的前一个节点称为前驱节点

    • 一个节点的下一个节点称为后继节点

  • 应用案例 ：
    • 
  • 思路分析 ：
    • 
  • 遍历线索化二叉树
    • 通过leftType和RightType找到头尾节点，进行线性遍历（类似双向链表）
    • 用原来的遍历方式可能会出问题，陷入死循环

树结构的实际应用

• 堆排序

  • 基本介绍 ：

    • 堆排序是利用堆这种数据结构设计的一种排序算法，==堆排序是一种选择排序==，它的最好，最坏，平均时间复杂度均为O(nlogn),它也是不稳定排序

    • 堆是具有以下性质的完全二叉树 ：每个节点的值都大于等于其左右子节点的值，称为大顶堆（注意：没有要求左子节点和右子节点的值的大小关系）

    • 每个节点的值都小于或等于其左右子节点的值，称为小顶堆

    • 大顶堆举例说明 ：

    • 小顶堆举例说明 ：

    • 一般升序采用大顶堆，降序采用小顶堆

  • 堆排序基本思想 ：
    • 
    • 第一个非叶子节点的索引 ： arr.length /2 - 1
    • 

• 赫夫曼树

  • 基本概念 ：
    • 给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的==带权路径长度(wpl ： weighted path length)达到最小==，称这样的二叉树为==最优二叉树==，也称为哈夫曼树/霍夫曼树
    • 赫夫曼树是带权路径长度最短的树，权值较大的节点离根较近
  • 几个重要概念和举例说明 ：
    • 
    • 
  • 实现思路 ：

• 赫夫曼编码

  • 基本介绍 ：
    • 赫夫曼编码也翻译成哈夫曼编码(Huffman Coding),是一种编码方式，属于一种程序算法
    • 赫夫曼编码是赫夫曼树在电讯通信中的经典应用之一
    • 赫夫曼编码广泛的用于数据文件压缩，压缩率达到20%~90%
    • 赫夫曼码是可变字长编码的一种，称之为最佳编码
  • 原理刨析
    • 通信领域的处理方式1 - 定长编码
    • 通信领域的处理方式1 - 变长编码（会造成多义性）
    • 赫夫曼编码 ：
    • 
    • 注意，这个赫夫曼树根据排序方法不同（可能排序时有几个相同权值的节点的情况），也可能不太一样，==这样对应的赫夫曼编码也不完全一样，但是wpl是一样的，都是最小的，编码处理后的长度也是一样的==。
    • 第四步的注意事项 ：
    • 第五步的注意事项
  • 解码过程注意事项 :
  • 对文件的压缩和解压（涉及IO,没看，留着之后看）
  • 赫夫曼编码的注意事项

    • 如果文件本身本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显的变化，如视频，ppt等

    • 赫夫曼编码是按字节处理的，因此可以处理所有的文件（二进制文件，文本文件..）

    • 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显

• 二叉排序树(BST ：Binary Sort Tree)

  • 介绍 ： 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点（子节点的父节点）的值小，右子节点的值比当前节点的值大。
    • 特别说明 ：如果有相同的值，可以放在左或右
    • 
  • 创建和遍历 ：使用递归和判断，比较简单，注意中序遍历就是按顺序的
  • 删除 ：删除需要考虑三种情况 ：
    • 删除叶子节点
    • 删除只有一棵子树的节点
    • 删除有两颗子树的节点
    • 实现代码 ： /text1/datastructure/binarysorttree/BinarySortTreeDemo.java

• 平衡二叉树（AVL树）

  • 引入 :
  • 基本介绍 ：
  • 注意，平衡二叉树的前提是它是一棵二叉排序树
  • • 核心 ： 找到以指定节点为根节点的树的高度，根节点的左子树，右子树的高度
  • 应用案列 ： 单旋转（左旋转）
    • 
    • 条件 ： 右子树的高度 - 左子树的高度 > 1
  • 应用案列 ： 单旋转（右旋转）
    • 
    • 条件 ： 左子树的高度 - 右子树的高度 > 1
  • 应用案列 ： 双旋转
    • 有些二叉排序树经过单旋转平衡处理后，仍然不是AVL树
    • 
    • 如果直接单旋转 ， 仍然不是AVL树
    • 需要进行上面的四步操作
  • AVL树完整代码 ： /text1/datastructure/avl/AVLTreeDemo.java

• 多路查找树

  • 二叉树的问题分析 ：
    • 
  • 多叉树介绍 ：
    • 在二叉树中，每个节点有数据项，最多有两个子节点。如果==允许每个节点可以有更多的数据项和更多的子节点，就是多叉树(multiway tree)==
    • 2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化
    • 举例说明 ：有三个子树的节点 ： 3节点，两个子树的节点 ： 2节点
  • B树介绍 ：
  • 2-3 树 ：
    • 2-3 树是最简单的 B树，具有如下特点 ：
      • 2-3树的叶子节点都在同一层（只要是B树都满足这个条件）
      • 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
      • 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
      • 2-3树是由二节点和三节点构成的树
    • 2-3 树应用案列 ：
  • B树，B+树和B*树
    • B树的介绍 ： B-tree树即B树，B即balanced ：
    • B+树介绍 ：切割了链表，查找起来性能很好
    • B*树介绍 ：

图

• 图的基本介绍 ：

  • 为什么要有图 ：

  • 线性表局限于一个直接前驱和一个直接后继的关系

  • 树也只能有一个直接前驱也就是父节点

  • 当我们需要==表示多对多关系时，就用到了图==

• 图的举例说明 ：
• 图的常用概念 ：
• 图的表示方式 ：
  • 邻接矩阵 ：
  • 邻接表 ：
• 图的快速入门案列 ：
  • 图的创建和常用方法 ：/text1/datastructure/graph/Graph.java
    • 添加节点，添加边，返回节点数目，边数目，返回索引的值，打印邻结矩阵
• 图的深度优先遍历 ：

  • 图的遍历即是对节点的访问，一个图有很多节点，遍历需要对应的策略，一般有两种策略（1）深度优先遍历（2）广度优先遍历

  • 深度优先搜索(Depth First Search DFS) :

    • 
    • 深度优先遍历算法步骤和举例说明 ：
    • 注意，深度优先是每次从下一个邻结节点找下一个（往x轴方向向下），直到找不到，再换下一个节点开始

  • 图的广度优先遍历(Broad First Search) ：

    • 基本思想 ： ：
    • 广度优先搜索遍历步骤和举例说明 ：
    • 
    • • 注意，广度优先是每次从同一个节点找下一个（往y轴方向向下）,直到找不到，再换下一个节点开始

  • 区别 ： 深度优先是用递归，栈实现的，广度优先是用队列实现的

    • 代码实现 ：/text1/datastructure/graph/Graph.java

常用算法

• 二分查找（非递归）

  • 基本介绍
    • 
  • 代码实现 ： /Algorithm/src/binarysearchnorecursion/BinarySearchNoRecur.java

• 分治算法

  • 基本介绍
    • 
  • 基本步骤
    • 
  • 算法设计模式
    • 
  • 分治算法的最佳实践 - 汉诺塔
    • 汉诺塔介绍 ：
    • 汉诺塔思路分析 ：

• 动态规划算法（Dynamic Programming）

  • 应用场景 - 背包问题 ：
  • 算法介绍 ：
  • 思路分析 ：
  • 填表过程 ：

• KMP算法

  • 应用场景 ：

  • 暴力匹配算法 ：

  • KMP算法介绍 ：参考资料 ：https://blog.csdn.net/v_july_v/article/details/7041827#t10

  • KMP算法应用-字符串匹配问题 ：

• 贪心算法

  • 算法介绍 ：

  • 应用场景 ：

  • 思路分析 ：

  • 思路图解 ：

  • 注意事项 ：

• 普利姆(Prim)算法

  • 应用场景 ：
  • 最小生成树 ：
  • 思路图 ：

• 克鲁斯卡尔算法

  • 应用场景 ：
  • 算法介绍 ：
  • 算法图解 ：
    • 添加边 ：
    • 判断回路 ：

• 迪杰斯特拉算法(Dijkstra)

  • 应用场景 ：

  • 算法介绍 ：Dijkstra算法是==典型的最短路径算法==，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层层扩展（广度优先搜索思想），直到扩展到终点为止

  • 算法过程 ：

  • 算法图解 ：

• 弗洛依德算法（Floyd）

  • 算法介绍 ：
  • 算法图解 ：三层for循环

• 马踏棋盘算法（骑士周游问题）

  • 算法介绍 :
  • 代码实现 :
  • 解决思路 ：
  • 使用贪心算法对代码优化 ：通过找到下一步能走的最少的步数集合，减少回溯的可能性，从而优化了算法