# dataStracture

**Repository Path**: fanyouwei/dataStracture

## Basic Information

- **Project Name**: dataStracture
- **Description**: 数据结构与算法学习
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2020-07-12
- **Last Updated**: 2024-11-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# dataStracture

### 介绍
数据结构与算法学习

### 软件架构
使用java语言完成对数据结构与算法的描述

### 数据结构

#### 数组

sparsearray 稀疏数组

```java
/**
 * 1. 使用二维数组完成对一个棋盘的保存 (如五子棋的棋盘，保存已下棋子的位置)
 * 2. 将二维数组转换为一个稀疏数组，压缩保存到硬盘上
 * 3. 从硬盘上读取稀疏数组的数据完成对棋盘的复原
 */
```

![稀疏数组](./data-structure/图片/稀疏数组转换.png)



#### 队列 

```java
/**
 * 队列是一种数据结构，我们规定它只能依顺序的入队出队
 * 这种方式就像生活中的排队，排在前面的人最快出去，在最后的人最后出去
 * 队列可以用数组实现也可以用链表实现，这里使用数组来实现
 */
```

queue 简单队列

```java
/**
 * 使用数组实现，就是给数组加上了规则,使这个数组只能从队列头部出队，只能从队列尾部入队
 * 队列中的最后一个数完成出队后，队列不能再被使用
 * 具体怎样标志队列为空，看具体的实现
 */
```

![image-20200712163705419](./data-structure/图片/队列.png)

CycleArrayQueue 循环队列 

```java
/**
 * 在简单队列中队列只可以使用一次，在完成一次队列安装满元素之后，就不能在使用；
 * 这样不能复用，就非常的不方便和浪费；所以我们要设计一个可以复用的队列，让队列可以重复的装入元素和释放 
 * 元素；同样使用数组实现，这是要在数组有可以存储数据的空间时，让数据入队；
 */
```

![循环队列](./data-structure/图片/循环队列.png)

#### 链表

```java
/**
 * 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现 
 * 的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部
 * 分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 
 */
```

SingleLinkedListDemo 单链表

```java
/**
 * 这里使用的是带头结点的单链表，链表的第一个节点为空，这是为了指向下一个有意义的节点所创建，方便操作
 * 对于带头节点的单链表的操作如下图示
 */
```

![单链表](./data-structure/图片/单链表.png)

![单链表的其它操作](./data-structure/图片/单链表2.png)



Josephus 约瑟夫问题 (循环单链表)

```java
/**
 * 循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，
 * 整个链表形成一个环。
 * 带头节点的循环链表
 * head = head.next; 
 * 单链表的一次遍历结束的条件是 node.next == head;
 * 插入删除的操作与不循环单链表并没什么不同，只是要注意最后一个node节点的next = head;
 */
```

![循环单链表](./data-structure/图片/循环单链表.png)

DoubleLinkedListDemo 双向链表

```java
/**
 * 双向链表
 * 双向链表是在单向链表的基础再加入了一个指向前一个节点的指针 pre
 * 此时链表就可通过next 向后移动，通过 pre向前移动
 * 	   如找到一个目标节点之后，我们需要再返回到目标节点之前，在单链表中只能从头开始在进行遍历查找
 *     而通过双向链表就可以直接使用 pre指针向前移动
 * 此时双向链表的空判断还是 next == null;
 * 添加节点时要标明pre 指针的指向
 * 而在删除时可以直接找到被删除的节点本身而不是它的前一个节点
 */
```

![双向单链表](./data-structure/图片/双向单链表.png)

- 删除操作就不演示了，和插入操作相同只不过是将指针从一个节点上移走而已



#### 栈

stack

```java
/**
 * 栈是一种特殊的数据结构，只能从一端进出
 */
```

ArrayStackDemo 使用数组来模拟stack

![栈](./data-structure/图片/栈.png)



- CalculatorStack.java 使用栈来模拟完成一个简单的综合计算器
- ReversePolishDemo 完成一个简单的逆波兰计算器
- ReversePolishDemo2  中缀表达式转换成后缀表达式,完成逆波兰计算器



### 算法

#### 递归

recursive

```java
/**
 * 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一
 * 个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，
 * 大大地减少了程序的代码量。
 * 
 * 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足
 * 时，递归返回；如果没有边界条件，则可能会导致一直递归调用，内存溢出
 * 如: 斐波那契数列
 * F(0)=0， F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
 */
public int fun(int n) {
    if (n <= 0){
        return 0;
    }
    if (n < 2){
        return 1;
    }
    return fun(n - 1) + fun(n - 2);
}
```

![递归](./data-structure/图片/递归.png)

- Labyrinth 迷宫寻路问题
- EightQueensProblem 八皇后问题



#### 排序算法

排序算法的实现在sort包中

##### 冒泡排序

BubbleSort

```java
/** 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把
 * 他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
 * 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中
 * 二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
 */
```

冒泡[排序算法](https://baike.baidu.com/item/排序算法/5399605)的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 
3. 针对所有的元素重复以上的步骤，除了最后一个。 
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

```java
/**
 * 如对 {0, 3, 1, 6, 5, 4} 进行排序
 */
```

![](./data-structure/图片/冒泡排序.png)

##### 选择排序

SelectSort

```java
/**
 * 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元
 * 素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
 * 选择排序是不稳定的排序方法。
 */
```

![](./data-structure/图片/选择排序.png)

##### 插入排序

InsertSort

```java
/**
 * 插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记
 * 录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前素
 * 前面有序表进行待插入位置查找，并进行移动
 */
```

![](./data-structure/图片/插入排序.png)

##### 希尔排序

ShellSort

```java
/**
 * 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直
 * 接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得
 * 名。
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关
 * 键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
 * 根据希尔排序实现的策略不同会有不同的效率
 * 1、交换排序
 * 2、移动排序
 */
```

![](./data-structure/图片/希尔排序.png)



##### 快速排序

QuickSort

```java
/**
 * 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部
 * 分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排
 * 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 */
```

![](./data-structure/图片/快速排序.png)

##### 归并排序

MergeSort

```java
/**
 * 归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide 
 * and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
 * 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
 */
```

![](./data-structure/图片/归并排序.png)

##### 基数排序

RadixSort

```java
/**
 * 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或
 * bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，
 * 基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某
 * 些时候，基数排序法的效率高于其它的稳定性排序法。
 *
 * 实现方法
 * 最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码
 * k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各
 * 子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先(Least Significant Digit first)
 * 法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
 */
```

![](./data-structure/图片/基数排序.png)



#### 查找

##### 线性查找

```java
/**
 * 如对一个数组进行查找
 * 简单的来说就是直接从头遍历数组查询，需要的数据
 */
```



##### 二分查找

BinarySearch

```java
/**
 * 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采
 * 用顺序存储结构，而且表中元素按关键字有序排列。
 * 
 * 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
 * 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一
 * 子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为
 * 止，此时查找不成功。
 */
```

![](./data-structure/图片/二分查找.png)

##### 插值查找

InsertValueSearch

```java
/**
 * 插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方
 * 法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。
 * 
 * 插值查找简单的来看就是对二分查找的寻找 mid 的方法进行了改变
 * 二分查找 每次获得 mid 就是使用 左边界加上右边界 然后除以二得到
 * 插值查找的 mid 变成了如下图所示的形式
 * 这里的high就是右边界，low就是左边界
 * 以如下的形式计算 mid 在分布均匀的序列中查询目标就会更为高效
 * 如对 {0,1,2,3,4,5,6,7,8,9} 查询数据1 只需要一次查询即可
 * 而二分查找2次递归
 * 但在数据不是分布的很均匀的时候插值查找的方法就不一定比二分查找的效率高
 * 如对下面这个数组 查询 2 的位置
 * int[] array2 = new int[]{1, 1, 1, 2, 8, 9};
 * 二分查找需要三次递归，插值查找需要 4次递归
 *
 * 代码的实现与二分查找没有什么不同，只是修改mid 的结算即可
 */
```

![img](./data-structure/图片/插值查找.png)

##### 斐波那契查找

FibonacciSearch

```java
/**
 * 斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表
 * 中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，直到满F[n]
 * 个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，
 * 找出要查找的元素在那一部分并递归，直到找到
 * 
 * 使用斐波那契查找，需要array.length < f[k] (f[k] 是斐波那契数列中的某一项)
 * 在找到那个 k 值后将 array.length 扩充为 f[k] - 1 (最后实际使用的大小) 
 * F[k]=F[k-1]+F[k-2] 
 * (F[k] - 1) = (F[k - 1] - 1)+(F[k - 2] - 1) + 1
 * mid = low + F(k - 1) - 1
 * value < mid; k --; 向左继续寻找
 * value > mid; k -= 2; 向右继续寻找
 * value == mid 找到
 * 最后没找到返回 -1
 */
```

![](./data-structure/图片/黄金分割.png)

#### 数据结构

##### 哈希表

HashTableDemo.java

```java
/**
 * 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，
 * 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的
 * 数组叫做散列表。
 
 */
```

![](./data-structure/图片/哈希表.png)

![img](./data-structure/图片/哈希表2.png)

### 二叉树

BinaryTreeDemo.java

#### 二叉树的实现 

[二叉树的百度百科](https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91/1602879?fr=aladdin)

```java
/**
 * 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即
 * 使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
 * 二叉树特点是每个结点最多只能有两棵子树，且有左右之分。
 */
```

BinaryTreeDemo.java

- 实现一个按照大小顺序排列存储的二叉树（二叉排序树）
  - 添加是无序的
  - 存储是有序的
  - 在一个结点的左边存储小于该结点的数
  - 在一个结点的右边存储大于该结点的数

![](./data-structure/图片/二叉树.png)

```java
/**
 * 二叉树的遍历：前序遍历，中序遍历，后序遍历
 * 如对上面的二叉树进行遍历
 * 前序遍历：先访问父结点 -> 左结点 -> 右结点，如果左结点下还有左结点则递归，此时左结点就是下一个左
 * 结点的父结点，右结点同样如此。遍历结果 5,2,1,3,4,7,6,8
 * 中序遍历：先访问左结点 -> 父结点 -> 右结点, 如果左结点下还有左结点则递归，此时左结点就是下一个左
 * 结点的父结点，右结点同样如此。遍历结果 1,2,3,4,5,6,7,8
 * 后序遍历：先访问左结点 -> 右结点 -> 父结点，如果左结点下还有左结点则递归，此时左结点就是下一个左
 * 结点的父结点，右结点同样如此。遍历结果 1,4,3,2,6,8,7,5
 * 
 * 对于上面的二叉树，在删除结点时候，同样要保证在删除完结点之后保持顺序性
 * 如删除 2，则再次前序遍历为 5,1,3,4,7,6,8  此时1为3结点的父节点
 */
```

#### 平衡二叉树

​       平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, [时间复杂度](https://baike.baidu.com/item/时间复杂度/1894057)和[空间复杂度](https://baike.baidu.com/item/空间复杂度/9664257)相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的[途径](https://baike.baidu.com/item/途径/9150896)



- 对于 array{0,1,2,3,4,5,6}，生成二叉树，按照上面的排序规则进行二叉树的生成就会出现如下的特殊情况

  单链表状，但是却使用二叉树入队结构生成，没有利用到二叉树的优势

  ![](./data-structure/图片/二叉树链表情况.png)

```java
/**
 * 对于这样的链表我们在满足条件的情况下进行结构的改变
 * 从根结点遍历判断左右子树的高度，如果左右两边的子树高度相差大于1就进行改变
 * 1. 左旋转
 *   对根结点左子树的高度大于右子树，就将根结点的左结点变成新的根结点，原来的根结点变成左结点的右结点
 * 并将它的左子结点指向原来左子结点的右结点
 * 2. 右旋转
 *   对于根结点右子树的高度大于左子树，就将根结点的右结点变成新的根结点，原来根结点变成右结点的左结点
 * 并将它的右子结点指向原来右子结点的左结点
 */
```

- 左旋转

  ![](./data-structure/图片/平衡二叉树的左旋转.png)

- 右旋转

![](./data-structure/图片/平衡二叉树的右旋转.png)

- 双旋转
  对于单次旋转不能使二叉树平衡的二叉树进行多次的旋转调整

  如上图右旋转之前的示意图，右子树的高度大于左子树要进行右旋转，但是以根结点的右结点为根结点的子树

  的右子树高度同样大于左子树，那我们就先对子树进行旋转操作，在对整个二叉树进行旋转

![](./data-structure/图片/平衡树的双旋转.png)

- 虽然上面的图解并没达到平衡状态，但是思路是正确的的，因为开始生成平衡树是在每次插入一个结点的时候进行平衡检验再插入

#### 顺序存储二叉树

```java
/**
 * 将一个数组转换成一个顺序存储的二叉树就是根据数组索引的关系，放入对应的二叉树的结点
 * 左子结点 i * 2 + 1
 * 右子结点 i * 2 + 2
 * 当前结点的父结点 (i - 1) / 2
 * 数组 array{1,2,3,4,5,6,7}
 * 根据公式得到如下的二叉树
 */
```

![](./data-structure/图片/顺序二叉树.png)

#### 线索化二叉树

ArrayBinaryTreeDemo.java

```java
/**
 * 在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）
 * 进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化
 * 
 * 线索化二叉树的本质是将二叉树的非线性结构，转成线性结构，但为了不增加存储空间的开销，使用结点的空闲的
 * 左右指针来完成
 *
 * 中序线索化二叉树，线索化之后的线性遍历结果与中序遍历的结果相同
 */
```

![](./data-structure/图片/线索化二叉树.png)



#### 堆排序

```java
/**
 * 堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，
 * 并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
 */
```

在堆的[数据结构](https://baike.baidu.com/item/数据结构)中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的[递归](https://baike.baidu.com/item/递归)运算



```java
/**
 * 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的
 * 值都小于或等于其左右孩子结点的值，称为小顶堆。
 */
```

![](./data-structure/图片/大顶堆和小顶堆.png)

**堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了**



- 假定给定如下序列

array[4,6,8,5,9]

![](./data-structure/图片/堆排序初始序列.png)

- 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

  ![](./data-structure/图片/大顶堆调整.png)

- 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

  ![](./data-structure/图片/大顶堆的生成.png)

- 此时，我们就将一个无需序列构造成了一个大顶堆。
- 再将第一个元素与最后一个元素交换，并将最后一个元素设为访问不可达的元素（length - 1）

![](./data-structure/图片/大顶堆的元素交换.png)

- 此时，大顶堆的结构被破坏，但此时其它的结点还是维持父结点大于两个子结点，在进行大顶堆调整

![](./data-structure/图片/再次调整大顶堆.png)

- 调整过后，结构再次被破坏，如此循环，最后就可得到一个有序序列

![](./data-structure/图片/大顶堆有序序列的生成.png)

#### 哈夫曼树

[百度百科](https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin)

```java
/**
 * 给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉
 * 树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近
 */
```

##### 哈夫曼树的构建

```java
/**
 * 对于给定数据序列的哈夫曼树构建
 * 1.首先对序列根据序列中数据的权重排序
 * 2.对排好序的每一个数据构建只有一个结点的二叉树
 * 3.对于排好序的序列，从中取出权重最小的两个二叉树生成一个新的等于权重等于两个二叉树之和的二叉树
 * 4.将使用过的两个最小的结点从序列中移除
 * 5.将重新生成的等于两个结点权重之和的二叉树放入序列，并重新对序列排序
 */
```

- 对数据 array[13, 7, 8, 3, 29, 6, 1] 进行哈夫曼树的构建

![](./data-structure/图片/哈夫曼树.png)

##### 哈夫曼编码的实践

HuffmanCode

- [**哈夫曼**](https://baike.baidu.com/item/哈夫曼)编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变[字长](https://baike.baidu.com/item/字长/97660)编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据[字符](https://baike.baidu.com/item/字符/4768913)出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）

```java
/**
 * 哈夫曼编码的实践：文件的压缩
 * 文件读取为 byte[] 进入内存操作
 * 1.首先根据指定的文件的数据构建哈夫曼树，每个哈夫曼树的叶节点保存的值是文件中出现的字符，权值是字出
 * 现的次数
 * 2.此时的哈夫曼树有两种结点：1只带权重的结点，2带权重并且带具体值的结点
 * 3.遍历每个节点对遍历路径进行标记，向左遍历记为 0，向右遍历记为 1，最后遍历完成就可以得到每个有具体
 * 意义的结点的编号，此时得到的编号就是哈夫曼编码，对于相同的数据根据排序方式的不同可能的得出的编号不
 * 相同；
 * 4.构建哈夫曼编码表：Map<Byte, String> codeTable, map 的key是字符，value是字符对应的哈夫曼
 * 编码
 * 5.对文件进行遍历处理，使用哈夫曼编码替换文件中的字符，文件按8个数字当成二进制生成十进制进行存储，
 * 以减少文件的存储空间，这样就完成了对文件的压缩
 * 
 * 具体的实现代码 见 tree 包下的 HuffmanCode.java，提醒文件压缩之后的压缩文件可能会比原文件更大是
 * 因为原文件的实现已经是非常紧凑没有必要压缩，而且压缩文件中保存的还有压缩文件解压需要的配置文件，当
 * 然有可能会比原文件更大（可以使用电脑自带的压缩软件先实验测试一下）
 */
```





### 图

[百度百科](https://baike.baidu.com/item/%E5%9B%BE/13018767?fr=aladdin)

- 以下使用邻接矩阵的方式来保存图，并代码实现

  我们给每个顶点从 0 开始编号

  对于有连接的两个顶点，将它们所对应的坐标置为 1

  ![](./data-structure/图片/图的邻接矩阵.png)

#### 图的遍历

- 对于一个图的结构，我们需要去遍历图中的所有顶点，无论是有联通的还是无联通的顶点

##### 图的深度遍历

- 首先选定一个开始遍历的顶点
- 以这个顶点开始，遍历它的第一个邻接顶点，遍历过的顶点设置标记已经遍历
- 以这个邻接顶点为当前顶点遍历这个顶点的第一个邻接顶点，递归遍历
- 当初先顶点的所有邻接顶点都已被遍历过，返回上一层，对上一个顶点的第二个邻接顶点开始遍历
- 直到所有的顶点都被遍历完成

##### 图的广度优先遍历

- 选定遍历开始的第一个顶点
- 遍历第一个顶点的所有邻接点，标记为已遍历
- 遍历第二个顶点的所有邻接点，已遍历的不再遍历
- 以此类推，遍历接下来的顶点，直到遍历完成

![](./data-structure/图片/图的遍历.png)



### 常用算法

- algorithm 模块下

#### 二分查找

非递归实现

binarysearch

BinarySearchNonRecursive

- 使用数组的下标以中间为判断界限，向两边查询



#### 分治思想

- 将问题分解成独立的小问题，得到每一个小问题的解，再将小问题的解合并即可得到最终问题的解

归并排序

汉诺塔问题  dac  HanoiTower

#### 动态规划

- 根据实际条件，得到对于当前问题的在条件限制下的最优解

dynamic

背包问题

KnapsackProblem

#### kmp算法

- 子串的查询算法，查询一串字符是否包含在另一串字符中的方法
-  通过建立子串的部分匹配表，在查询的过程中跳过已经查询但不匹配的字符串部分

Kmp

#### 贪心算法

greedy

- 贪心算法（又称贪婪算法）是指，在对[问题求解](https://baike.baidu.com/item/问题求解/6693186)时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解

Greedy 算法实践

#### 普利姆算法

prim

- 寻找图的最小生成树（从一个顶点出发，寻找到一条路径以最短的的距离通过所有的顶点）
- 1.首先，确定起点，将起点标记为已遍历
- 2.然后将图中的顶点分为已经遍历过的和没有遍历的
- 3.之后选出一条分别以这两种顶点作为起点和终点的距离（权值）最短的边，放入最小生成树
- 4.将那两点中的未遍历的点置为已遍历
- 重复上面 1-4 直至完成遍历所有的顶点

#### 克鲁斯卡尔算法

kruskal

- 寻找图的最小生成树
- 不确定起点，而是以边为参照
- 首先对图中所有的边进行从小到大排序放入一个集合中
- 1.选择权值最小的边加入最小生成树，移除集合
- 2.再次选择剩余的权值最小的边，并判断是否会与已经加入最小生成树的边形成回路
- 3.如果形成回路就不能添加，移除集合，没有形成回路就加入生成树，移除集合
- 重复上面 1-3 ，直至遍历所有的顶点

#### 迪杰斯特拉算法

dijkstra

- 寻找图中的某一个顶点分别到其它所有顶点的最短路径
- 如图中有 A B C D E F G
- 以 A 为起点 要求的就是 A->B 和 A->C->B 的距离那个短
- 将除A外所有的点进行进行如C的判断，更新A 到其它顶点的距离
- 就可以得到A到其它顶点的最短路径

#### 弗洛伊德算法

floyd

- 贪心思想，得出局部再来得出全局

- 寻找图所有顶点到其他所有顶点的最短路径
- 对图中所有的顶点就行如 A->B 和 A->C->B的距离比较操作
- A （所有顶点）起点 ，B（所有顶点）终点和C（所有顶点）
- 进行两两比较得出这三个顶点的中的最小距离
- 因为对所有的顶点都进行了如上操作，就可以得出各个顶点到各个顶点的最小距离

#### 骑士周游算法

horse

- 就是迷宫寻路，只不过是边界的不同，判定的方式不同而已