# Java算法和数据结构

**Repository Path**: linguochao/datastructures-algorithm

## Basic Information

- **Project Name**: Java算法和数据结构
- **Description**: 数据结构和算法,学习代码
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-05-08
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构和算法的关系
- 数据data结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。

- 要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.

- 程序 = 数据结构 + 算法

- 数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位。

# 线性结构和非线性结构

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

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


# 稀疏数组(sparsearray)

**实际的需求:** 
编写的五子棋程序中，有存盘退出和续上盘的功能。

**分析问题:** 
因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.->稀疏数组。

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

2. 稀疏数组的处理方法是:
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

# 队列(queue)
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，
   front 会随着数据输出而改变，而 rear则是随着数据输入而改变
- 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,
   这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 
**实际需求:**  银行排队

# 链表(Linked List)
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域， next 域：指向下一个节点.
- 链表的各个节点不一定是连续存储.
- 链表分带头节点的链表和没有头节点的链表

### 单链表
**实际需求:** 水浒英雄排行榜管理 --> 使用带head头的单向链表实现 
- 第一种方法在添加英雄时，直接添加到链表的尾部
- 第二种方式在添加英雄时，根据排名将英雄插入到指定位置

**单链表的常见面试题:**
- 求单链表中有效节点的个数  【遍历】
- 查找单链表中的倒数第k个结点 【总数-k】
- 单链表的反转【new新链表,遍历旧数据,头插法到新链表】
- 从尾到头打印单链表 【方式1：反转,遍历 。 方式2：Stack栈】
- 合并两个有序的单链表，合并之后的链表依然有序

### 双向链表
- 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
- 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，
  所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点.

### 单向环形链表和约瑟夫问题
**Josephu问题为：**
设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，
它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

**提示：** 
用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，
然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，
直到最后一个结点从链表中删除算法结束

# 栈(stack)
**基本概念**
- 栈的英文为(stack)
- 栈是一个先入后出(FILO-First In Last Out)的有序列表。
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。
   允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
- 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，
   而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

**栈的应用场景**
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。 	
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。
- 图形的深度优先(depth一first)搜索法。

**实际需求**
- 输入一个表达式:[7*2*2-5+1-5+3-3] 
- 思考: 计算机底层是如何运算得到结果的？ 
  注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 
  但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)

**使用栈完成表达式的计算思路**
1. 通过一个 index  值（索引），来遍历我们的表达式
2. 如果我们发现是一个数字, 就直接入数栈
3. 如果发现扫描到是一个符号,  就分如下情况
  - 如果发现当前的符号栈为空，就直接入栈
  - 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 
     就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，
     然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈.
4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行.
5. 最后在数栈只有一个数字，就是表达式的结果

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

- 中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，
   因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

**前缀表达式的计算机求值**
- 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算
 （栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

**后缀表达式的计算机求值**
- 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算
（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

**中缀表达式转换为后缀表达式**
1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压s2；
4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
- (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
- (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；	
5. 遇到括号时：
- (1) 如果是左括号“(”，则直接压入s1
- (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6. 重复步骤2至5，直到表达式的最右边
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

### 递归(Recursion) -- 迷宫问题(回溯)
递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

**递归用于解决什么样的问题**
- 各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
- 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
- 将用栈解决的问题-->递归代码比较简洁

**递归需要遵守的重要规则**
- 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
- 方法的局部变量是独立的，不会相互影响, 比如n变量
- 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
- 递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)
- 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

**递归-迷宫问题**