# data-structure-java

**Repository Path**: q-linyu/data-structure-java

## Basic Information

- **Project Name**: data-structure-java
- **Description**: 数据结构与算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-03-31
- **Last Updated**: 2021-07-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构和算法

### 含义

指的是相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成

（简单来说：就是数据和数据之间的关系）

### 数据结构包括

> 线性结构和非线性结构

> - 线性结构
>   - 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
>   - 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素的地址是连续的
>   - 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
>   - 线性结构常见的有：数组、队列、链表和栈

> - 非线性结构
>   - 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

### 稀疏数组

> 基本介绍

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

> 稀疏数组的处理方法

- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

> 例子

![image](https://raw.githubusercontent.com/q-linyu/images/master/sparseArr.png)

### 队列

> ![image](https://raw.githubusercontent.com/q-linyu/images/master/queue-img.png)
>
> 队列介绍
> 队列是一个有序列表，可以用数组或是链表来实现
> 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

### 链表

> 含义：是一种物理单元非连续，非顺序的存储结构，数据元素是通过指针次序实现的，链表是由一系列的节点组成，其中包含两部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域
>
> 和数组的的区别：
>
> ​			数组：需要一块连续的内存空间，对内存的要求比较高，比如我们要申请1000M的数组，如果内存中			没有1000M的内存空间就会申请失败，就算剩余可用的空间大于1000M，依然申请失败
>
> ​			链表：与数组相反，它并不需要一块连续的内存空间，它是通过指针将一组零散的内存块串联起来，			如果我们要申请1000M的大小的链表，就算剩余可用的空间大于1000M，依然申请成功
>
> ![image](https://raw.githubusercontent.com/q-linyu/images/master/arr-link.png)
>

> 类型

### 单链表

> ​		说明：第一个节点叫做头节点，最后一个节点叫做尾节点，尾节点通常设置为NULL，如果要查询，需要遍历全部数据，然后一个个来找，所以效率低
>
> ​		![image](https://raw.githubusercontent.com/q-linyu/images/master/single-link.png)
>
> ​		![](C:\Users\Administrator\Pictures\single-link-add-remove.png)

### 循环链表

> 一种特殊的单链表，最后一个指针指向的是头节点
>
> ![image](https://raw.githubusercontent.com/q-linyu/images/master/foreach-link.png)
>
> ​	

### 双向链表

> 单向链表只有一个指针，节点只有一个next指针指向后面的节点，而双向链表，持有两个方向，每个节点不仅只有一个后续next指针指向后面的节点，还有一个prev前驱指针指向前面的节点
>
> ![image](https://raw.githubusercontent.com/q-linyu/images/master/s-link.png)
>
> ​	说明：双向链表需要额外两个空间来存储后续节点和前驱节点的地址，所以，如果存储同样多的数据，双向链表比较占内存空间，虽然两个指针比较浪费存储空间，但可以持有双向遍历这样可也带来双向链表操作的灵活性

### 双向循环链表

> ![image](https://raw.githubusercontent.com/q-linyu/images/master/s-foreach-link.png)

### 栈

> 特点：先进后出，后进先出![image](https://raw.githubusercontent.com/q-linyu/images/master/stack-img.png)
>
> 说明
>
> ​	用数组实现的栈叫做顺序栈，用链表实现的栈叫做链表
>
> ​	在栈顶端插入一个元素，在栈的尾端删除一个元素
>
> ​	先进的时是栈低，出的时候是栈顶
>
> ​	使用数组实现的顺序栈，底层支持动态扩容
>
> ​	栈Stack的父类是Vector

### 算法

> 含义：计算的方法，实现问题的思路

> 特性

- 输入：比如输入0-多个数字
- 输出：结果至少一个
- 有穷性：在有限的时间内所执行的结果
- 确定性：一个输入对应着一个输出
- 可行性：算法能够解决实际的问题

> 基本要求

- 正确性：这个算法可以正确的解决实际问题
- 可读性
- 健壮性：合法的数字计算，不能非零除法以及非法字符计算
- 时间复杂度：算法在计算的时候，需要占用多长时间
  - 常见的时间复杂度
    - 常数阶
    - 对数阶
    - 线性阶
    - 线性对数阶
    - 平方阶
    - 立方阶
    - K次方阶
    - 指数阶
  - 随着问题规模的不断增大，上述时间复杂度不断增大，算法的执行效率越低
- 空间复杂度：算法在运行时， 需要占用多少内存

### 常见的5种数据运算

插入、删除、修改、查找、排序

### 线性表结构

含义：数据排成向一条长线一样的结构

#### 数组

> 含义：是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据
>
> 说明：
>
> ​	1.第一个元素是第二个元素的前驱，第二个元素是第一个元素的后驱
>
> ​	2.连续内存空间里有很多存储单元，计算机会给它编成编号，所谓的编号就是内存地址
>
> ​    3.数据访问时通过下标来访问的
>
> 特性：一块连续的存储空间
>
> 特点：高效的随机访问、低效插入和删除

> 

#### 递归

> 在一个函数的内部调用该函数本身的一种编程方式

### 堆

> 分为大顶推和小顶推，对于任何子树而言，父节点永远都大于子节点

### 查找算法

> 线性查找：在数组中查找某一个元素
>
> 二分查找：在一个有序的数组里，首先找中间的元素，然后根据中间的元素作为开始，往左还是往右找到想要的元素
>
> 插值查找
>
> 斐波那契（黄金分割法）

### 排序

> 排序算法

- 交换排序
  - 冒泡排序
  
  - 快速排序
  
- 插入排序
  - 直接插入排序
  - 希尔排序：改进的插入排序
  
- 选择排序
  - 简单选择排序
  - 堆排序
  
- 归并排序

- 基数排序

- 堆排序：升序排列，使用大顶堆，反之

  - 大顶堆

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/heap-max.png)

  - 小顶堆

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/heap-min.png)

### 树

> 基本概念

- 根节点
- 双亲节点
- 子节点
- 路径
- 节点的度：一个节点下有多少个子节点，叫做度
- 节点的权：每个节点赋予的内容或者值，叫做权
- 叶子节点：没有子节点的节点
- 子树
- 层
- 树的高度
- 森林

![image](https://raw.githubusercontent.com/q-linyu/images/master/two-fork-tree.png)

> 结构

- 二叉树

  - 含义：任何一个节点的子节点数量不超过两个

  - 要求：二叉树分为左节点和右节点，不能随意颠倒位置

  - 遍历方式

    - 前序遍历: 先输出父节点，再遍历左子树和右子树
    - 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
    - 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
    - 小结: 看输出父节点的顺序，就确定是前序，中序还是后序

  - 链式二叉树

    - 满二叉树：所有子节点都在最后一层，而且节点的总数为：2^n - 1

      ![image](https://raw.githubusercontent.com/q-linyu/images/master/full-two-fork-tree.png)

    - 完全二叉树：所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子在左边连续，倒数第二层的叶子节点在右边连续

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/completely-fork-tree.png)

- 顺序存储二叉树：是以数组的方式来存放

  - 特点
    - 顺序二叉树通常只考虑完全二叉树
    - 第n个元素的左子节点为  2 * n + 1 
    - 第n个元素的右子节点为  2 * n + 2
    - 第n个元素的父节点为  (n-1) / 2
    - n : 表示二叉树中的第几个元素
  - 线索二叉树

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/e-tree.png)

  - 赫夫曼树：权值越大的节点离根节点越近的并且WPL最小的二叉树才是最优二叉树，也叫做赫夫曼树

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/wpl-img.png)

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/huffmantree.png)

- 二叉排序树，也叫二叉查找树，二叉搜索树

  - 为了克服查找、删除、插入困难
  - 对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点值小，右子节点比当前节点值大

- 平衡二叉树：在二叉排序树的条件下，左子树和右子树的高度差的绝对值不超过1，也叫AVL树。保证查询效率较高

  ![image](https://raw.githubusercontent.com/q-linyu/images/master/avl-tree.png)

- 多叉树

  - B树：重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率
    - 特点
      - 所有叶子节点都在同一层（只有B树都能满足这个要求）
      - 有两个子节点的节点叫做二节点，二节点要么没有子节点，要么有两个子节点
      - 有三个子节点的节点叫做三节点，三节点要么没有子节点，要么有三个子节点
    - 说明
      - B树的阶：节点最多的节点个数
  - B+树：是B树的变体，也是一种多路搜索树，所有数据都在叶子节点

- 红黑树

### 哈希表

> 哈希表也叫散列表

> 设计

1. 直接定址法
   - 原则：计算简单，不符合分布均匀
2. 数字分析法
   - 原则：适合分布均匀
3. 平方取中法
4. 取余法
5. 随机数法

> 散列冲突问题

- 开放地址法
  - 线性探测法
  - 二次探测法
  - 再哈希法
- 链地址法

### 图

> 含义：是一种数据结构，其中节点可以具有零个或多个相邻元素，两个节点之间的连接称之为边

> 概念

- 顶点
- 边
- 路径
- 无向图
- 有向图
- 带权图

> 方式

- 二维数组（邻接矩阵）
- 链表（邻接表）