# DataStructure

**Repository Path**: leiyuee/DataStructure

## Basic Information

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

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-11-02
- **Last Updated**: 2024-08-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# DataStructure

## 介绍

数据结构与算法学习

### 一、稀疏数组
      当一个数组中大部分元素是0或者为同一个值的时候，可以使用稀疏数组来保存该数组；
#### 处理方法：
      记录数组一共有几行几列，有多少个不同的值
      把具有不同的值的元素的行列以及值记录在一个小数组中
#### 应用实例：
      使用稀疏数组，来保留类似棋盘，地图这样的二维数组
      把稀疏数组存盘，可以重新恢复原来的二维数组
####  转换思路：
      遍历原始的二维数组，得到有效数据的个数 sum
      根据sum 可以创建稀疏数组 sparseArray int[sum+1][3]
      将二维数组的有效数据存到稀疏数组


###  二、队列 queue
    有序列表，可以通过数组或者链表来实现
    遵循先入先出的原则：先入先出，后入后出

### 三、链表
    有序的列表：以节点的方式存储，是链式存储，每个节点包含 data域，next域：指向下一节点
    节点存储时不一定是连续存储的
    分为带头节点的链表和没有头节点的链表
    头节点不存放具体的数据，只是表示单链表的头
    以next域 为【null】判断链表的最后一个

### 四、栈（stack）
    栈是一个先入后出的有序列表
    限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表；
    允许插入和删除的一端 是变化的一端称为栈顶（Top）,固定的另一端，称为栈底（Bottom）
    出栈pop ,入栈push
#### 应用场景
    1、计算（表达式的转换）：中缀表达式转后缀表达式
    2、子程序的调用：在跳往子程序前，会先将下一个指令的地址存放到堆栈中，知道子程序执行完成后再将地址取出以回到原来的程序中
    3、递归调用：将下一个指令的地址和 参数，区域变量等数据存入堆栈中
    4、二叉树的遍历
    5、图形的深度优先（depth→first）搜索法

### 五、递归
    递归就是方法自己调用自己。每次调用时传入不同的变量；

#### 能解决什么问题
    1、8皇后问题，汉诺塔，阶乘，迷宫，球和篮子
    2、算法：快排，并归排序，二分查找，分治算法
    3、递归比栈更简介
#### 规则
    1、执行一个方法的时候，就创建一个新的受保护的独立空间(栈空间)
    2、方法的局部变量是独立的，不会互相影响
    3、如果方法中使用的二十引用类型变量(如数组)，就会共享该引用类型的数据
    4、必须向退哦出递归的条件逼近，否则就会无线递归了，出现StackOverflowError
    5、 谁调用就将结果返回给谁

### 树
什么是树？
- 每个节点最多只能有两个子节点的树成为二叉树；
- 如果二叉树的所有叶子节点都在最后一层，就是满二叉树；
- 如果二叉树的叶子节点在最后一层或者是倒数第二层，而且最后一层左边连续，倒数第二层右边连续，则是完全二叉树
遍历
- 前序：先输出父节点，再左，再右
- 中序：先遍历输出左，再中，再右
- 后续：先遍历左，再右，再输出父  

### 图

#### 遍历
对节点的访问：深度优先遍历和广度优先遍历

##### 深度优先遍历
   - 从初始访问节点出发，初始访问节点可能有多个邻接节点，深度的策略是访问第一个邻接节点，再以第一个邻接节点为初始点，访问它的第一个连接节点，
  即：每次都在访问当前节点后首先访问当前节点的第一个邻接节点
   - 往纵向深入访问 是一个递归的过程

##### 广度优先算法
   - 需要使用一个队列来保持访问过的节点的顺序，以便按照这个顺序来访问这些节点的邻接节点