数据结构包括：线性结构和非线性结构。
线性结构
-
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
-
线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
-
链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
-
线性结构常见的有：数组、队列、链表和栈，后面我们会详细讲解.
一、稀疏数组
1. 实际需求
编写五子棋程序，有存盘退出和续盘的功能
二维数组记录棋盘，1代表黑子，2代表篮子
问题：二维数组中出现很多没有值都为0，记录了很多没有意义的数据，造成了很大的浪费
2.基本介绍
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
-
记录数组一共有几行几列，有多少个不同的值
-
把具有不同值的元素的行列及值记录在一个小规模的数组（稀疏数组）中，从而缩小程序的规模
| row | col | val | |
| [0] | 多少行 | 多少列 | 多少个值 |
| [1]第一行 | 0 | 对应值为几列 | 值为多少 |
| [k]以此类推 | 。。。。 | 。。。。 | 。。。。 |
-
二维数组转化稀疏数组思路
- 遍历原始的二维数组，得到有效数据的个数sum
- 根据sum可以创建稀疏数组sparseArr int[sum+1][3]
- 将二维数组有效数据存入到稀疏数组，稀疏数组保存到磁盘（因为需要存盘）
-
稀疏数组转原始二维数组的思路
- 将文件读取到稀疏数组中
- 先读取稀疏数组的第一行，根据第一行的数据，创建原始数组的行列
- 在读取稀疏数组后几行的数据，并赋给元数的二维数组
1. 二维数组与稀疏数组相互转化
package DataStructure.sparsearray;
import java.io.*;
/**
* @author Small_Tsk
* @create 2020-06-30
**/
public class SparseArray {
public static void main(String[] args) throws IOException {
// 先创建一个原始的二维数组 11*11
// 1表示黑子，2表示篮子
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
//输出二维数组
System.out.println("原始的二维数组");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
// 将二维数组转稀疏数组的私立
// 1.先遍历二维数组，得到非零的数组的个数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
sum++;
}
}
}
// 2.创建对应的稀疏数组
int sparseArray[][] = new int[sum + 1][3];
// 给稀疏数组赋值
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
// 遍历二维数组，将非零数值存入到稀疏数组中
int count = 1;// 用来记录是第几个非零数据
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
sparseArray[count][0] = i;// row 行数
sparseArray[count][1] = j;// col 列数
sparseArray[count][2] = chessArr1[i][j];// val 值
count++;
}
}
}
//将稀疏数组存入磁盘中
File file = new File("map.text");
Writer fw = new BufferedWriter(
new OutputStreamWriter(new FileOutputStream(file), "GBK")
);
for (int i = 0; i < sparseArray.length; i++) {
fw.write((sparseArray[i][0]) + "\t");
fw.flush();
fw.write((sparseArray[i][1]) + "\t");
fw.flush();
fw.write((sparseArray[i][2]) + "\t");
fw.flush();
}
fw.close();
//输出稀疏数组的形式
System.out.println();
System.out.println("得到的稀疏数组");
for (int i = 0; i < sparseArray.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
}
//读取磁盘
BufferedReader br = new BufferedReader(
new InputStreamReader(new FileInputStream(file))
);
System.out.println("读取");
String s = new String();
String s1;
while ((s1 = br.readLine()) != null) {
s += s1;
}
//"将读取的内容赋给新的稀疏数组"
String[] strings = s.split("\t");
System.out.println("strings:" + strings[0]);
int sparseArray2[][] = new int[strings.length / 3][3];
for (int i = 0; i < strings.length / 3; i++) {
sparseArray2[i][0] = Integer.valueOf(strings[i * 3]);
sparseArray2[i][1] = Integer.valueOf(strings[i * 3 + 1]);
sparseArray2[i][2] = Integer.valueOf(strings[i * 3 + 2]);
}
System.out.println();
System.out.println("新稀疏数组：\n");
for (int[] row : sparseArray2) {
for (int data : row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
// 稀疏数组转化二维数组
// 读取稀疏数组第一行，创建二维数组
int row = sparseArray2[0][0];
int col = sparseArray2[0][1];
//赋值
int newArray[][] = new int[row][col];
for (int i = 1; i < sparseArray2.length; i++) {
newArray[sparseArray2[i][0]][sparseArray2[i][1]] = sparseArray2[i][2];
}
System.out.println();
System.out.println("恢复后的二维数组");
for (int i = 0; i < newArray.length; i++) {
for (int j = 0; j < newArray.length; j++) {
System.out.printf("%d\t", newArray[i][j]);
}
System.out.println();
}
}
}
二、队列
1.队列介绍
-
队列是一个有序列表，可以用数组或是链表来实现。
-
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
-
示意图：(使用数组模拟队列示意图)
2.数组模拟队列
-
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
-
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
-
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
-
将尾指针往后移：rear+1 , 当front == rear 【空】
-
若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
-
数组模拟队列
package DataStructure.queue;
import java.security.Key;
import java.util.Scanner;
/**
* @author Small_Tsk
* @create 2020-07-01
* <p>
* 使用数组模拟队列
**/
public class ArrayQueueDemo {
public static void main(String[] args) {
//创建一个队列
ArrayQueue arrayQueue = new ArrayQueue(3);
//接受用户输入
Scanner sc = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show)：显示队列");
System.out.println("e(exit)：退出程序");
System.out.println("a(add：添加用户)");
System.out.println("g(get)：从队列中取出所有数据");
System.out.println("h(head)：从队列中取出头部数据");
char key = sc.next().charAt(0);
switch (key) {
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("请输入数值");
int i = sc.nextInt();
arrayQueue.addQueue(i);
break;
case 'g':
try {
int res = arrayQueue.getQueue();
System.out.printf("取出的数据%d\n", res);
} catch (Exception e) {
// TODO: 2020/7/1 handle Exception
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int h = arrayQueue.HeadQueue();
System.out.printf("取出头部数据是%d\n", h);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
sc.close();
loop = false;
break;
}
}
System.out.println("程序退出");
}
static class ArrayQueue {
private Integer maxSize;//表示数组的最大值
private Integer front;//队列头
private Integer rear;//队列尾
private int[] arr;//该数组用于存放数据，模拟队列
//chuangjianduilie的构造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1;//指向队列头部，只想队列头的前一个位置
rear = -1;//指向队列尾部具体数据
}
//判断队列是否满
public boolean isFull() {
return rear == maxSize - 1;
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//添加数列到队列
public void addQueue(int n) {
//判断队列是否满
if (isFull()) {
System.out.println("队列已满");
return;
}
rear++;//让rear后移
arr[rear] = n;
}
//数据出队列
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
front++;
return arr[front];
}
//显示队列的所有数据
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr["+i+"]=%d\n", arr[i]);
}
}
//显示队列的头部
public int HeadQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front + 1];
}
}
}
3.问题及优化
- 问题：目前数组只能使用一次，使用过的不能复用，
- 优化：将数组使用算法，改进一个环形的队列，循环利用
4.数组模拟环形队列
- 思路如下：
- front指针（变量）做出调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0
- rear变量的含义做调整：rear指向队列的最后一个元素的后一个位置，希望空留一个空间做出约定，rear的初始值=0
- 当队列满时，条件是**（rear +1）% maxSize=front【满】**
- 当队列为空的条件，rear==front 空
- 当我们这样分析中，队列中有效的数据的个数：（rear+maxSize-front）% maxSize,相当于rear-front，但是因为是环形，有可能rear比front小，出现负数，所以加上maxSize
代码实现：
public static void main(String[] args) {
//创建一个队列
// Explanation : 设置4，其实际数据大小为3
CircleArray arrayQueue = new CircleArray(4);
//接受用户输入
Scanner sc = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show)：显示队列");
System.out.println("e(exit)：退出程序");
System.out.println("a(add：添加用户)");
System.out.println("g(get)：从队列中取出所有数据");
System.out.println("h(head)：从队列中取出头部数据");
char key = sc.next().charAt(0);
switch (key) {
case 's':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("请输入数值");
int i = sc.nextInt();
arrayQueue.addQueue(i);
break;
case 'g':
try {
int res = arrayQueue.getQueue();
System.out.printf("取出的数据%d\n", res);
} catch (Exception e) {
// TODO: 2020/7/1 handle Exception
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int h = arrayQueue.HeadQueue();
System.out.printf("取出头部数据是%d\n", h);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
sc.close();
loop = false;
break;
}
}
System.out.println("程序退出");
}
static class CircleArray {
private Integer maxSize;//表示数组的最大值
// front 初始值=0
private Integer front;//含义调整，front指向队列第一个元素
//rear 初始值=0
private Integer rear;//队列尾
private int[] arr;//该数组用于存放数据，模拟队列
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = 0;
rear = 0;
}
//判断队列是否满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//添加数列到队列
public void addQueue(int n) {
//判断队列是否满
if (isFull()) {
System.out.println("队列已满");
return;
}
arr[rear] = n;
//让rear后移
rear = (rear + 1) % maxSize;
}
//数据出队列
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
// front是第一个元素
// 1.先把front保留到一个临时变量中
int value = arr[front];
// 2.将front后移
front = (front + 1) % maxSize;
// 3.返回临时变量
return value;
}
//显示队列的所有数据
public void showQueue() {
//遍历
if (isEmpty()) {
System.out.println("队列为空");
return;
}
// 思路：从front开始遍历，遍历多少元素
for (int i = front; i < front + (rear + maxSize - front) % maxSize; i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
//显示队列的头部
public int HeadQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front];
}
}
三、链表
1、单链表介绍
链表是有序的列表，但是它在内存中是存储如下：
小结:
-
链表是以节点的方式来存储,是链式存储
-
每个节点包含 data 域， next 域：指向下一个节点.
-
如图：发现链表的各个节点不一定是连续存储.
-
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
2、单链表介绍
单链表(带头结点) 逻辑结构示意图如下
1、单链表应用实例
使用带head头的单向链表实现 –水浒英雄排行榜管理
-
完成对英雄人物的增删改查操作， 注: 删除和修改、查找
-
第一种方法在添加英雄时，直接添加到链表的尾部
-
第二种方式在添加英雄时，根据排名将英雄插入到指定位置
(如果有这个排名，则添加失败，并给出提示)
代码实现
public static void main(String[] args) {
//先创建几个节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
//创建要给的链表
SingleLinkedList sl = new SingleLinkedList();
//加入
sl.addByOder(hero1);
sl.addByOder(hero4);
sl.addByOder(hero2);
sl.addByOder(hero3);
sl.addByOder(hero3);
//显示
sl.show();
System.out.println();
// 测试修改的节点
HeroNode newNode = new HeroNode(2, "玉麒麟", "```");
sl.update(newNode);
System.out.println("修改后的链表显示");
sl.show();
//测试删除节点
System.out.println();
System.out.println("删除后的链表显示");
sl.delNode(3);
sl.show();
}
}
//定义SingleLinkedList
class SingleLinkedList {
//先初始化头节点，头节点不能动,不存放具体数据
private HeroNode head = new HeroNode(0, "", "");
//添加节点到单向链表
//当不考虑编号顺序时，
// 1.找到当前链表的最后节点
// 2.将最后这个节点的next域指向新的节点
public void add(HeroNode heroNode) {
//因为head节点不能动，所以我们需要一个辅助变量
HeroNode temp = head;
//遍历链表
while (true) {
//找到链表的最后
if (temp.next == null) {
break;
}
//如果没有找到，将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后。
temp.next = heroNode;
}
//根据排名添加指定位置
//如果排名重复，则添加失败
public void addByOder(HeroNode heroNode) {
//头节点不能动，需要辅助变量找到添加的位置
//因为是单链表，因此我们找的temp，位于添加位置的前一个节点，否则加入不了
HeroNode temp = head;
boolean flag = false;//标识添加的编号是否存在，默认为false
while (true) {
if (temp.next == null) {//说明temp已经在链表的最后
break;
}
if (temp.next.no > heroNode.no) {//位置找到，就在temp的后面插入(因为是temp.next)
break;
} else if (temp.next.no == heroNode.no) {//希望添加的编号已经存在
flag = true;//说明编号存在
break;
}
temp = temp.next;//后移
}
//判断flag的值
if (flag) {
System.out.println("编号" + heroNode.no + "已经存在,不能重复添加");
} else {
//插入到链表中，tem的后面。见图解
heroNode.next = temp.next;
temp.next = heroNode;
}
}
// 修改节点信息，根据no修改，即no不可以改变
// 根据新节点的no修改即可
public void update(HeroNode newHeroNode) {
//判断是否为空
if (head.next == null) {
return;
}
//找到需要修改的节点，根据no编号
//定义辅助变量
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp == null) {
//已经遍历结束
break;
}
if (temp.no == newHeroNode.no) {
//找到了
flag = true;
break;
}
temp = temp.next;
}
//根据flag判断是否找到要修改的节点
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.println("需要修改的节点" + newHeroNode.no + "没有找到");
}
}
// 删除节点
public void delNode(int no) {
boolean flag = false;
HeroNode temp = head;
while (true) {
if (temp.next == null) {
break;
} else if (temp.next.no == no) {//找到对应的节点，即temp.next
flag = true;
break;
}
temp = temp.next;
}
//判断flag，即判断herNode是否找到
if (flag){
temp.next = temp.next.next;
}else{
System.out.println("未找到对应的节点:"+no);
}
}
//显示链表【遍历】
public void show() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//需要辅助变量，因为head的节点不能动
HeroNode temp = head.next;
while (true) {
//判断是否到链表的最后
if (temp == null) {
break;
}
//输出节点信息
System.out.println(temp);
//将next后移
temp = temp.next;
}
}
}
//定义HeroNode，每个HeroNode 对象就是一个节点
class HeroNode {
public int no;//指针域，域next相关联
public String name;
public String nickname;
public HeroNode next;//指向下一个节点
//构造器
public HeroNode(int No, String Name, String NickName) {
this.no = No;
this.name = Name;
this.nickname = NickName;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
", next=" + next +
'}';
}
思路分析：
- 需要先创建一个辅助变量，因为head节点是不能够被改变的
- 关于按照顺序添加节点、删除节点
- 都需要先找到需要添加、删除的节点的上一个节点，一次循环没有的话，需要将temp后移，再循环
- 找到之后跳出循环，实现对应的代码，如上图
2、单链表面试题
单链表的常见面试题有如下:
1)求单链表中有效节点的个数
/**
*
* @param head 链表的头节点
* @return 返回有效节点的个数
*/
public static int getLength(HeroNode head){
int length =0;
if (head == null){
return 0;
}
//当前节点
HeroNode current = head;
// 不包含头部节点
while (current.next != null){
length ++;
current = current.next;
}
return length;
}
2)查找单链表中的倒数第k个结点 【新浪面试题】
// 2) 查找单链表中的倒数第k个结点 【新浪面试题】
/*
* 思路：
* 1.编写一个方法，接受head节点，同时接受一个index
* 2.index表示倒数第index个节点
* 3.先把链表从头到尾遍历，得到链表的总长度L
* 4.得到L后，从链表的第一个开始遍历，第L-index即可*/
public static HeroNode findAllByEnd(HeroNode head, int k) {
int l = getLength(head);
int index = l - k;
if (head == null) {
return null;
} else if (k<1 ||k>l) {
System.out.println("不存在倒数第"+k+"个结点");
return null;
}
HeroNode current = head.next;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
3)单链表的反转【腾讯面试题，有点难度】
-
思路：
- 创建一个新的头节点
- 遍历旧链表，每遍历一个，就将放在新链表的最前端
- 最后，将旧头节点，链接到新链表即可
public static void ReverseLinked(HeroNode head) {
if (head.next.next == null || head.next == null) {
System.out.println("链表为空，无法反转");
return ;
}
HeroNode reverserHead = new HeroNode(0, "", "");
HeroNode current = head.next;//当前节点
HeroNode next = null;//当前结点的下一个节点
while (current != null) {
//先暂时保存当前结点的下一个结点
next = current.next;
current.next = reverserHead.next;//将current的下一个结点指向新链表的最前端
reverserHead.next = current;
current = next;
}
//将head.next指向reverse.next,实现单链表的反转
head.next = reverserHead.next;
}
4)从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
-
思路：
- 不可以用到反转操作，反转的问题是会破坏原来链表的结构。题目并无要求
- 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的特点
// 逆序打印各个节点（利用栈） public static void reversePrint(HeroNode head){ if (head.next==null){ System.out.println("此链表为空，无法打印"); return; } Stack<HeroNode> stack = new Stack<>(); HeroNode current = head.next; while (current != null){ stack.push(current); current = current.next; } System.out.println("\n逆序打印各个节点:\n"); while (stack.size()>0){ System.out.println(stack.pop()); } }
5)合并两个有序的单链表，合并之后的链表依然有序【课后练习.】
-
思路分析：类似于反转
- 创建一个新链表
- 比较谁小，谁就先加入到新链表
- 谁先为空，则把不为空的链表剩余部分全部加完
- 最后将旧链表头替换到新链表即可
public static void mergeLink(HeroNode head, HeroNode head2) {
if (head.next == null || head2.next == null) {
System.out.println("链表为空，无需合并");
return ;
}
HeroNode current = head.next;
HeroNode current2 = head2.next;
HeroNode next = null;
HeroNode mergeHead = new HeroNode(0, "", "");
HeroNode mergeCurrent = mergeHead;
while (true){
//谁小将谁加到新链表的后面
if (current.no< current2.no){
mergeCurrent.next =current;
current = current.next;
mergeCurrent =mergeCurrent.next;
}
else if (current.no>current2.no){
mergeCurrent.next = current2;
current2 = current2.next;
mergeCurrent = mergeCurrent.next;
}
//谁先为空，就将不为空的链表全部加入
if (current2 == null ){
while (current != null){
mergeCurrent.next = current;
current = current.next;
}
break;
}
if (current == null){
while (current2 != null){
mergeCurrent.next = current2;
current2 = current2.next;
}
break;
}
}
head.next = mergeHead.next;
}
3、双向链表
使用带head头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
1)单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2)单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).
3)示意图帮助理解删除
课堂作业和思路提示:
双向链表的第二种添加方式,按照编号顺序
按照单链表的顺序添加，稍作修改即可.
-
注意：
-
在排序的时候，一定注意逻辑，排序顺序倒换的话，很有可能出错。即temp.next指向null，将新元素添加到temp的后面，一定先让新元素的next域添加为null，才能指定temp.next的指向。
-
例如：
-
//正确示范 heroNode_double.next = temp.next; temp.next = heroNode_double; heroNode_double.pre =temp; temp.next.pre = temp; -
//错误示范 temp.next = heroNode_double; heroNode_double.pre =temp; heroNode_double.next = temp.next; temp.next.pre = temp;
-
public void addOrder(HeroNode_double heroNode_double) {
HeroNode_double temp = head_d;
boolean flag = false; //判断编号是否存在
while (true){
if (temp.next == null){//遍历到链表的最后
break;
}
if (temp.next.no > heroNode_double.no){//找到位置，在temp的后面插入
break;
}else if(temp.no == heroNode_double.no ){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
System.out.printf("编号[%d]已经存在，不能加入",heroNode_double.no);
}else{
//加入到后面
heroNode_double.next = temp.next;
temp.next = heroNode_double;
heroNode_double.pre =temp;
temp.next.pre = temp;
}
}
4、单向环形链表
1、约瑟夫问题
Josephu 问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示
用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。
public static void main(String[] args) {
Boys boy1 = new Boys(1);
Boys boy2 = new Boys(2);
Boys boy3 = new Boys(3);
Boys boy4 = new Boys(4);
Boys boy5 = new Boys(5);
SingleRingLink sl = new SingleRingLink();
sl.add(boy1);
sl.add(boy2);
sl.add(boy3);
sl.add(boy4);
sl.add(boy5);
sl.J_Question(2);
}
static class SingleRingLink {
private Boys firstBoy =null;
public void add(Boys boy) {
if (firstBoy == null){
firstBoy = boy;
boy.next = boy;
}
Boys current = firstBoy;
while (current.next != firstBoy) {//遍历到最后
//后移
current = current.next;
}
current.next =boy;
boy.next = firstBoy;
}
public void show(){
Boys temp = firstBoy;
while (temp != null){
System.out.println(temp);
temp = temp.next;
}
}
public void J_Question(int k){
Boys temp = firstBoy;
while (temp.next != temp){
int i = 1;
if (i == k-1){//正好是需要移除temp的上一个元素
System.out.println(temp.next.no);
temp.next = temp.next.next;
}
i++;
temp = temp.next;
}
System.out.println(temp.no);
}
}
static class Boys {
public int no;
public Boys next;
public Boys(Integer No) {
this.no = No;
}
@Override
public String toString() {
return "Boys{" +
"no=" + no +
'}';
}
}
四、栈
实际需求
请输入一个表达式
计算式:[7*2*2-5+1-5+3-3] 点击计算【如下图】
请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈
1、栈的介绍
-
栈的英文为(stack)
-
栈是一个先入后出(FILO-First In Last Out)的有序列表。
-
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
-
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
-
出栈(pop)和入栈(push)的概念(如图所示)
)
2、应用场景
-
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
-
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
-
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
-
二叉树的遍历。
-
图形的深度优先(depth一first)搜索法。
3、栈的快速入门
- 用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈，入栈等操作。
2 )实现思路分析,并画出示意图
-
对同学们加深栈的理解非常有帮助
-
课堂练习，将老师写的程序改成使用链表来模拟栈.
-
思路分析
-
1、使用数组模拟栈
-
定义一个top，初始值为-1
-
入栈的操作，当有数据加入到栈时，top++；stack[top]=data
-
出栈的操作，
int value = stack[top]; top–-; retrun value;
-
public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true;
Scanner sc = new Scanner(System.in);
System.out.println("s:显示栈");
System.out.println("e:展示栈");
System.out.println("pu:加入数据");
System.out.println("po:取出数据");
while (loop) {
System.out.println("操作完成，请继续您的指令");
key = sc.nextLine();
switch (key) {
case "s":
stack.show();
break;
case "e":
loop = false;
break;
case "pu":
System.out.println("请输入一个整数");
int value = sc.nextInt();
stack.push(value);
break;
case "po":
try {
int res = stack.pop();
stack.pop();
System.out.printf("出栈的数据%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
}
}
System.out.println("程序退出");
}
//定义 一个类表示栈
static class ArrayStack {
private int maxSize;//栈的大小
private int[] stack;//数组，模拟栈放数据
private int top = -1;//表示栈顶
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//栈满
public boolean isFull() {
return top == maxSize - 1;
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//入栈 push
public void push(int value) {
if (isFull()) {
System.out.printf("栈满无法存放[%d]数据", value);
return;
}
top++;
stack[top] = value;
}
//出栈,将栈顶的数据返回
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈空。。");
}
int value = stack[top];
top--;
return value;
}
//显示栈的情况[遍历栈],遍历时需要从栈顶看是显示
public void show() {
if (isEmpty()) {
System.out.println("栈空，无法遍历栈");
return;
}
for (int i = top; i > -1; i--) {
int value = stack[i];
System.out.printf("stack[%d] = %d\n", i, value);
}
}
}
}
?
4、综合计算器
-
实现思路：
-
使用栈完成表达式的计算思路
- 通过一个index值(索引) ,来遍历我们的表达式
- 如果我们发现是- -个数字，就直接入数栈
- 如果发现扫描到是一个符号,就分如下情况
- 如果发现当前的符号栈为空，就直接入栈
- 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，就需要 ，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈.
- 最后在数栈只有一个数字, 就是表达式的结果
创建栈的逻辑
//创建栈 //定义 一个类表示栈 class ArrayStack { private int maxSize;//栈的大小 private int[] stack;//数组，模拟栈放数据 private int top = -1;//表示栈顶 public ArrayStack(int maxSize) { this.maxSize = maxSize; stack = new int[this.maxSize]; } //栈满 public boolean isFull() { return top == maxSize - 1; } //栈空 public boolean isEmpty() { return top == -1; } //入栈 push public void push(int value) { if (isFull()) { System.out.printf("栈满无法存放[%d]数据", value); return; } top++; stack[top] = value; } //出栈,将栈顶的数据返回 public int pop() { if (isEmpty()) { throw new RuntimeException("栈空。。"); } int value = stack[top]; top--; return value; } //显示栈的情况[遍历栈],遍历时需要从栈顶看是显示 public void show() { if (isEmpty()) { System.out.println("栈空，无法遍历栈"); return; } for (int i = top; i > -1; i--) { int value = stack[i]; System.out.printf("stack[%d] = %d\n", i, value); } } //返回运算符的优先级，优先级是程序员来定义的 //数字越大，则有限级越高 public int priority(int oper) { if (oper == '*' || oper == '/') { return 1; } else if (oper == '+' || oper == '-') { return 0; } return -1; } //判断是不是一个运算符 public boolean isOper(char val) { return val == '+' || val == '-' || val == '*' || val == '/'; } //可以返回当前栈的值，但并不是pop出的值 public int peek() { return stack[top]; } //计算方法 public int cal(int num1, int num2, int oper) { int res = 0;//用于存放计算的结构 switch (oper) { case '+': res = num1 + num2; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; default: break; } return res; } }实现逻辑
public static void main(String[] args) {
//完成表达式的预算
String expression = "300+2*6-100";
//创建两个栈， 一个是数栈，一个是符号栈
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
//定义需要的相关变量
int index = 0;//用于扫描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' ';//将每次扫描的char保存到ch
String keepNum = "";
//开始用while语句扫描expression
while (true) {
//一次的到expression的每个字符
ch = expression.substring(index, index + 1).charAt(0);
//判断ch是什么，然后做相应的处理
if (operStack.isOper(ch)) {//如果是运算符
if (!operStack.isEmpty()) {
//如果不为空，就进行比较操作符的优先级
//如果当前的优先级小于或等于要栈中的优先级
//从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算,
//将得到结果，入数栈，然后将当前的操作符入符号栈
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = operStack.cal(num1, num2, oper);
//把当前结果入数栈
numStack.push(res);
//把当前的操作符入符号栈
operStack.push(ch);
} else {
operStack.push(ch);
}
} else {
//如果为空直接入栈
operStack.push(ch);// 1 +3
}
} else {//如果是数，则直接入数栈
//拼接多位数
keepNum += ch;
//如果ch是expression的最后以为，就直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
} else {
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
numStack.push(Integer.parseInt(keepNum));
//清空keepNum
keepNum = "";
}
}
}
//让index+1，并判断是否扫描到expression最后
index++;
if (index >= expression.length()) {
break;
}
}
// 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号,并运行
while (true) {
//如果符号栈为空，则计算到最后的结果，数栈中只有一个数字【结果】
if (operStack.isEmpty()) {
break;
} else {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = operStack.cal(num1, num2, oper);
numStack.push(res);
}
}
//将数栈的最后的数pop出，就是结果
System.out.printf("表达式%s = %d", expression, numStack.pop());
}
}
5、前缀、中缀、后缀表达式(逆波兰表达式)
前缀表达式**(波兰表达式)**
1)前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
2)举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6
前缀表达式的计算机求值
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下
-
从右至左扫描，将6、5、4、3压入堆栈
-
遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
-
接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
-
最后是-运算符，计算出35-6的值，即29，由此得出最终结果
6、中缀表达式
-
中缀表达式就是常见的运算表达式，如(3+4)×5-6
-
中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)
7、后缀表达式
-
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
-
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
-
再比如
| 正常的表达式 | 逆波兰表达式 |
|---|---|
| a+b | a b + |
| a+(b-c) | a b c - + |
| a+(b-c)*d | a b c – d * + |
| a+d*(b-c) | a d b c - * + |
| a=1+3 | a 1 3 + = |
1、后缀表达式的计算机求值
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如: , 针对后缀表达式求值步骤如下
-
从左至右扫描，将3和4压入堆栈；
-
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
-
将5入栈；
-
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
-
将6入栈；
-
最后是-运算符，计算出35-6的值，即29，由此得出最终结果
2、逆波兰计算器
我们完成一个逆波兰计算器，要求完成如下任务
1)输入一个逆波兰表达式(后缀表达式)，使用栈(Stack),计算其结果
2)括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
3)思路分析
4)代码完成
3、中缀表达式转换为后缀表达式
*具体步骤如下
-
初始化两个栈：运算符栈s1和储存中间结果的栈s2；
-
从左至右扫描中缀表达式；
-
遇到操作数时，将其压s2；
-
遇到运算符时，比较其与s1栈顶运算符的优先级：
? (1) 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
? (2) 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
? (3) 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
-
遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 -
重复步骤2至5，直到表达式的最右边
-
将s1中剩余的运算符依次弹出并压入s2
-
依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
举例说明:
将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
? [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZNZjuAee-1628087907862)(E:/Typora/upload/image-20200707143454636.png)]
因此结果为 “1 2 3 + 4 × + 5 –”
代码实现：
public static List<String> PrefixConvertSuffix(List<String> list) {
//定义两个栈，一个是符号栈，一个是储存后缀表达式的栈
//储存后缀表达式的栈可以用ArrayList来代替，因为只有存储的操作，无需再逆序
Stack<String> s1 = new Stack<String>();
ArrayList<String> s2 = new ArrayList<>();
for (String s : list) {
if (s.matches("\\d+") ) {//是数字，直接加入s2
s2.add(s);
}else if ( s.equals("(")){//是左括号，直接加入符号栈
s1.push(s);
}
else if (s.equals(")")) {//是右括号，遍历符号栈，将符号栈的符号移入到数栈，直到遍历到左括号
while (!s1.isEmpty() && !s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();
} else {//如果是运算符，则比较运算符优先级，大于栈中则直接入符号栈，小于的话，则将符号栈的符号pop到数栈中，直到符号栈的优先级小即可
while (!s1.isEmpty()&&priority(s) <= priority(s1.peek()) ) {
String pop = s1.pop();
s2.add(pop);
}
s1.push(s);
}
}
//将s1中的元素pop出加入到s2
while (!s1.isEmpty()) {
s2.add(s1.pop());
}
return s2;
}
五、递归
应用场景
1、概念
简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。
2、调用机制
我列举两个小案例,来帮助大家理解递归，部分学员已经学习过递归了，这里在给大家回顾一下递归调用机制
1)打印问题
2)阶乘问题
3、递归用处
递归用于解决什么样的问题
1)各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
2)各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
3)将用栈解决的问题–>第归代码比较简洁
4、递归遵守的规则
递归需要遵守的重要规则
-
执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
-
方法的局部变量是独立的，不会相互影响, 比如n变量
-
如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
-
递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了:)
-
当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
5、递归-迷宫问题
说明:
1)小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关
2)再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化
3)测试回溯现象
4)思考: 如何求出最短路径?
递归-八皇后问题（回溯算法）
1、八皇后问题介绍
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
2、算法思路分析
八皇后问题算法思路分析
-
第一个皇后先放第一行第一列
-
第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
-
继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
-
当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
-
然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤 【示意图】
说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
代码如下：
//定义一个max标识共有多少个皇后
int max = 8;
//定义数组array，保存皇后放置的结果，下标标识行，数值标识列
int[] array = new int[max];
static int count =0;
public static void main(String[] args) {
EightQueens queens = new EightQueens();
queens.check(0);
System.out.printf("一共有%d种解法",count);
}
//编写一个方法，放置第n个皇后
//特别注意：check每一次递归，进入check中都会有for循环，因此会有回溯
private void check(int n) {
if (n == max) {//n==8,其实八个皇后就已经放好了
print();
return;
}
//依次放入皇后，判断是否冲突
for (int i = 0; i < max; i++) {
//先把当前这个皇后，放到该行的第一列
array[n] = i;
//判断当前放置第n个皇后到i列时，是否冲突
if (judge(n)) {//不冲突
//接着放第n+1个皇后,即开始递归
check(n + 1);
}
//如果冲突，就继续执行这个循环，相当于执行array[n]=i+1,即将第n个皇后放置在本行后移的位置----i+1列
}
}
//查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
//说明
//array[i]==array[n] 表示判断第n个皇后是否和前面的n-1个皇后在同一列
//Math.abs(n-i)==Math.abs(array[n]-array[i] 表示是否在同一个斜线，因为n,i是正方形的对顶点
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
//写一个方法可以将最后的结果打印出来
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
六、哈希表
1、实际需求
google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的 所有信息.
要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
2、基本介绍
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
15 111 % 15
google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址…),当输入该员工的id时,要求查找到该员工的 所有信息.
- 要求:
- 不使用数据库,速度越快越好=>哈希表(散列)
- 添加时，保证按照id从低到高插入 [课后思考：如果id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?]
- 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
- 思路分析并画出示意图
- 代码实现[增删改查(显示所有员工，按id查询)]
思路：
- 先创建员工实体表
- 在创建存放员工的链表
- 创建存放链表集合的hashTab
- 任何方法需要先在链表中实现，然后hashTab再调用其方法
- 取模法 ，根据id可以确定要使用哪一个链表。即id%size
代码如下
//创建存放链表的集合
static class hashTabEmp {
private EmpLinkedList[] emps;
private int size;
public hashTabEmp(int size) {
this.size = size;
this.emps = new EmpLinkedList[size];
for (int i = 0; i < size; i++) {
emps[i] = new EmpLinkedList();
}
}
public void add(Emp emp) {
int hashTabNo = haveFun(emp.id);
emps[hashTabNo].add(emp);
}
public void show() {
for (int i = 0; i < size; i++) {
if (emps[i].isEmpty()) {
System.out.printf("第%d条链表为空\n", i + 1);
} else {
System.out.printf("第%d条链表的信息\t：", i + 1);
emps[i].show();
System.out.println();
}
}
}
//根据ID查找信息
public void findById(int id) {
//先找到对应的链表
int no = id % size;
Emp emp = emps[no].findById(id);
if (emp == null){
System.out.printf("\n 信息中没有id = %d的信息",id);
}else{
System.out.printf("\n 找到此信息：id = %d ,name = %s",emp.id,emp.name);
}
}
//删除信息
public void del(int id){
int no = id % size;
emps[no].del(id);
System.out.println("删除成功\n");
}
public int haveFun(int id) {
return id % size;
}
}
//雇员
static class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
//创建EmpLinkedList，标识链表
static class EmpLinkedList {
//头指针，指向第一个Emp
private Emp head = new Emp(0, "");
//添加信息
public void add(Emp emp) {
Emp current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Emp(emp.id, emp.name);
}
//展示信息
public void show() {
if (head.next == null) {
System.out.println("此链表为空");
return;
}
Emp current = head.next;
while (current != null) {
System.out.printf(" || => id = %d, name = %s", current.id, current.name);
current = current.next;
}
}
//根据id查找雇员信息
public Emp findById(int id) {
Emp current = head.next;
while (current != null) {
if (current.id == id) {
break;
}
}
return current;
}
//根据id删除信息
public void del(int id){
if (head.next == null){
System.out.println("此链表中没有匹配的信息");
return;
}
Emp current = head.next;
while (id != current.next.id){//找到需要删除的上一个节点
current = current.next;
}
//删除节点
current.next = current.next.next;
}
//判断链表是否为空
public boolean isEmpty() {
return head.next == null ? true : false;
}
}
算法
1、算法时间复杂度
1、度量一个程序(算法)执行时间的两种方法
-
事后统计的方法
这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。 -
事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优.
2、时间频度
基本介绍
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]
举例说明-基本案例
比如计算1-100所有数字之和, 我们设计两种算法
T(n)=n+1;
T(n)=1
1、举例说明-忽略常数项
| T(n)=2n+20 | T(n)=2*n | T(3n+10) | T(3n) | |
|---|---|---|---|---|
| 1 | 22 | 2 | 13 | 3 |
| 2 | 24 | 4 | 16 | 6 |
| 5 | 30 | 10 | 25 | 15 |
| 8 | 36 | 16 | 34 | 24 |
| 15 | 50 | 30 | 55 | 45 |
| 30 | 80 | 60 | 100 | 90 |
| 100 | 220 | 200 | 310 | 300 |
| 300 | 620 | 600 | 910 | 900 |
结论:
? 1) 2n+20 和 2n 随着n 变大，执行曲线无限接近, 20可以忽略
? 2) 3n+10 和 3n 随着n 变大，执行曲线无限接近, 10可以忽略
4、忽略低次项
| T(n)=2n^2+3n+10 | T(2n^2) | T(n^2+5n+20) | T(n^2) | |
|---|---|---|---|---|
| 1 | 15 | 2 | 26 | 1 |
| 2 | 24 | 8 | 34 | 4 |
| 5 | 75 | 50 | 70 | 25 |
| 8 | 162 | 128 | 124 | 64 |
| 15 | 505 | 450 | 320 | 225 |
| 30 | 1900 | 1800 | 1070 | 900 |
| 100 | 20310 | 20000 | 10520 | 10000 |
结论:
-
2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
-
n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20
3、忽略系数
| T(3n^2+2n) | T(5n^2+7n) | T(n^3+5n) | T(6n^3+4n) | |
|---|---|---|---|---|
| 1 | 5 | 12 | 6 | 10 |
| 2 | 16 | 34 | 18 | 56 |
| 5 | 85 | 160 | 150 | 770 |
| 8 | 208 | 376 | 552 | 3104 |
| 15 | 705 | 1230 | 3450 | 20310 |
| 30 | 2760 | 4710 | 27150 | 162120 |
| 100 | 30200 | 50700 | 1000500 | 6000400 |
结论:
1)随着n值变大，$5n^2+7n $和 n 2 + 2 n n^2 + 2n n2+2n ，执行曲线重合, 说明 这种情况下**, 5和3可以忽略。**
2)而 n 3 + 5 n n^3+5n n3+5n 和 6 n 3 + 4 n 6n^3+4n 6n3+4n ，执行曲线分离，说明多少次方式关键
2、时间复杂度
-
一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
-
T(n) 不同，但时间复杂度可能相同。 如：T(n)=n2+7n+6 与 T(n)=3n2+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n2)。
-
计算时间复杂度的方法：
-
用常数1代替运行时间中的所有加法常数 T(n)=n2+7n+6 => T(n)=n2+7n+1
-
修改后的运行次数函数中，只保留最高阶项 T(n)=n2+7n+1 => T(n) = n2
-
去除最高阶项的系数 T(n) = n2 => T(n) = n2 => O(n2)
1、常见的时间复杂度
-
常数阶 O(1) 对数阶 O(log2n**)** 线性阶 O(n) 线性对数阶 O(nlog2n) 平方阶 O(n^2) 立方阶 O(n^3) k次方阶 O(n^k) 指数阶 O(2^n) 
- 说明：
- 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
- 从图中可见，我们应该尽可能避免使用指数阶的算法
1、常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用**O(1)**来表示它的时间复杂度。
2、对数阶O(log2n)
说明：在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 n 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n) .
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ytJvQpB7-1628087907881)(E:/Typora/upload/image-20200708161343839.png)]
3、线性阶O(n)
说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用**O(n)**来表示它的时间复杂度
4、线性对数阶O(nlogN)
说明：线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
5、平方阶O(n2)
说明：平方阶O(n2) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n2)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n2) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(m*n)
6、立方阶O(n3)、K次方阶O(n^k)
说明：参考上面的O(n2) 去理解就好了，O(n3)相当于三层n循环，其它的类似
2、平均时间复杂度和最坏时间复杂度
1)平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
2)最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
3)平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:)。
3、算法空间复杂度简介
基本介绍
-
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
-
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
-
在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
4、排序算法
介绍
排序也称排序算法 (Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列 的过程。
排序的分类：
- 内部排序:
? 指将需要处理的所有数据都加载到内部存储器中进行排序。
- 外部排序法：
? 数据量过大，无法全部加载到内存中，需要借助外部存储进行
排序。
3) 常见的排序算法分类(见下图):
测试排序效率
public static void main(String[] args) throws Exception {
int n =10*10000;
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = (int) (Math.random()*n);
}
long start = System.currentTimeMillis();
Sort(array);
long end = System.currentTimeMillis();
System.out.printf("排序10^5次所用时间为：%d毫秒",end-start);
}
1、 冒泡排序
1、基本介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)
2、图解
3、实例
我们举一个具体的案例来说明冒泡法。我们将五个无序的数：3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。
代码如下
private static void Sort(int[] array){
boolean flag =false;//表示变量，表示是否进行过交换
for (int i = 0; i < array.length-1; i++) {//一共array.length-1次排序，不需要包含最后一个数
for (int j = 0; j < array.length-1-i; j++) {//每排完一次顺序的时候，排完的位置不需要进行比较，其他位置在比较
int temp = array[j];
if (array[j]>array[j+1]){
flag=true;
array[j] = array[j+1];
array[j+1] =temp;
}
}
if (!flag){//表示在一次排序中，所有位置都没有发生过交换。即顺序已经排好，可以跳出循环直接输出即可
System.out.println("已经排序完，无需再次排序！");
break;
}else{
flag = false;
}
System.out.printf("第%d次排序，数组为：%s\n",i, Arrays.toString(array));
}
}
2、选择排序
1、基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
2.选择排序思想:
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]~arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
3、选择排序思路分析图:
3、实例
有一群牛 , 颜值分别是 101, 34, 119, 1 请使用选择排序从低到高进行排序 [101, 34, 119, 1]
代码如下
private static void Sort(int[] array) {
int min;//最小值
int minIndex;//最小值的索引
for (int i = 0; i < array.length-1; i++) {//不需要排序最后一个数字
min = array[i];
minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minIndex =j;
}
}
if (minIndex != i){
array[minIndex] = array[i];
array[i] = min;
}
// System.out.printf("第%d次排序的数组为：%s\n", i, Arrays.toString(array));
}
}
3、插入排序法
1、介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
2、思想
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
3、思路图
| 初始状态 | 101 | 34 | 119 | 1 |
|---|---|---|---|---|
| 第一次排序 | 34 | 101 | 119 | 1 |
| 第二次排序 | 34 | 101 | 1 | 119 |
| 第三次排序 | 34 | 1 | 101 | 119 |
| 第四次排序 | 1 | 34 | 101 | 119 |
需要两个指针，一个指针位于value值的位置，便于获取下一个value。另一个指针则是value位置前面，便于比较大小
代码如下：
private static void Sort(int[] array) {
for (int i = 1; i < array.length; i++) {
int insertValue = array[i];//要插入的值
int insertIndex = i - 1;//要插入的位置
while (insertIndex >= 0 && insertValue < array[insertIndex]) {//找到插入的位置
array[insertIndex+1] = array[insertIndex];//将插入位置的后一个位置
insertIndex--;
}
array[insertIndex+1]=insertValue;//将要插入的后一个位置填充上插入的值
System.out.printf("第%d次排序的数组为：%s\n", i, Arrays.toString(array));
}
}
4、希尔排序
简单插入排序存在的问题
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
- {2,3,4,5,6,6}
-
{2,3,4,5,5,6}
-
{2,3,4,4,5,6}
-
{2,3,3,4,5,6}
-
{2,2,3,4,5,6}
-
{1,2,3,4,5,6}
结论： 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.
1、希尔排序法介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
2、希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
3、示意图
4、实例（含代码）
有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用
-
希尔排序时， 对有序序列在插入时采用交换法**, 并测试排序速度.**相对较慢
-
分组+冒泡
-
int temp; for (int gap = array.length/2 ; gap >0 ; gap/=2) {//分组 for (int i = gap; i < array.length; i++) { for (int j = i-gap; j >=0 ; j-=gap) { //冒泡 if (array[j]>array[j+gap]){ temp=array[j]; array[j] = array[j+gap]; array[j+gap] = temp; } } } System.out.printf("第%d次排序：%s",gap,Arrays.toString(array)); System.out.println(); }
-
-
希尔排序时， 对有序序列在插入时采用移动法, 并测试排序速度。较快，不好理解
-
分组+插入
-
private static void Sort(int[] array) { int step = array.length; while (step != 1) { step /= 2; // System.out.println(step); for (int i = step; i < array.length; i ++) { int insertIndex = i - step;//要插入的位置 int insertValue = array[i];//要插入的值 while (insertIndex >= 0 && insertValue < array[insertIndex]) { array[insertIndex+step] =array[insertIndex];//将数值大的数赋给后面 insertIndex -= step; } array[insertIndex + step] = insertValue;//将数值小的数赋给前面 } System.out.printf("分%d组排序后的结果：%s",step, Arrays.toString(array)); System.out.println(); }
-
5、快速排序
1、快速排序法介绍
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2、示意图
3、快速排序法应用实例
要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。【测试8w和800w】
-
说明[验证分析]:
- 如果取消左右递归，结果是 -9 -567 0 23 78 70
- *如果取消右递归,结果是 -567 -9 0 23 78 70
- *如果取消左递归,结果是 -9 -567 0 23 70 78
代码如下
public static void Sort(int[] array, int left, int right) { int l = left; int r = right; int median = array[(r + l) / 2]; int temp; while (l < r) {//判断是否扫描完毕 while (array[l] < median) { //如果未在中间值左边找到大于中间的值，则左指针右移，继续寻找，直至找到 l++; } while (array[r] > median) { //如果未在中间值右边找到小于中间的值，则右指针左移，继续寻找，直至找到 r--; } if (l >= r) { //如果左右指针遍历到右左才找到，则说明原本大小顺序分布正确 break; } //交换左右指针的值 temp = array[l]; array[l] = array[r]; array[r] = temp; if (array[l] == median) { // 如果左指针指到中间值的位置，则说明左边全是小于中间值的 // 将右指针左移，因为此时右指针指的是一个比中间值大的数 r--; } if (array[r] == median) { l++; } } System.out.println(Arrays.toString(array)); //如果l==r,必须要让l++,r--.否则会出现栈溢出 if (l==r){ l++; r--; } // 向左递归 if (left<r){ Sort(array, left, r); } //向右递归 if (right>l){ Sort(array,l, right); } }
6、归并排序
归并排序介绍:
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案修补在一起，即分而治之)。
示意图
说明:
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。
归并排序思想示意图2-合*并相邻有序子序列:
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IzoO6MR0-1628087907896)(E:/Typora/upload/image-20200708165731169.png)]!
归并排序的应用实例:
给你一个数组, val arr = Array(9,8,7,6,5,4,3,2,1), 请使用归并排序完成排序。
代码如下：
//分解
public static void Sort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
//向左递归分解
Sort(arr, left, mid, temp);
//向右递归分解
Sort(arr, mid + 1, right, temp);
//到合并
merge(arr, left, right, mid, temp);
}
}
/**
* @param arr 原始数组
* @param left 左边有序序列的初始索引
* @param right 右边索引
* @param mid 中间
* @param temp 临时数组
*/
public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
int i = left;//初始化i，左边有序序列的初始索引
int j = mid + 1;//初始化j，右边
int t = 0;//指向temp数组的当前索引
//先把左右两边(有序)的数据按照规则填充到temp数组
//直到左右两边的有序序列，右一边处理完毕为止
while (i <= mid && j <= right) {
//如果左边的有序序列的当前元素，小于/等于右边有序序列的数值
//则将元素放入到temp中，
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//把有剩余的数据的一边的数据全部填充到temp中
while (i <= mid) {//左边的元素还有剩余，则全部填充到temp
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
//将temp数组的元素拷贝到array
//注意，并不是每次都拷贝所有
t = 0;
int tempLeft = left;//第一次合并时，tempLeft=0，right=1
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
7、基数排序
1、基数排序(桶排序)介绍:
-
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
-
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
-
基数排序(Radix Sort)是**桶排序**的扩展
-
基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
2、基数排序基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤
3、基数排序图文说明
将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。
- 第1轮排序后：542 53 3 14 214 748
- 第1轮排序后：542 53 3 14 214 748
- 第2轮排序后： 3 14 214 542 748 53
第2轮排序 [按照十位排序]
(1) 将 各个数，按照十位大小 放入到 对应的 各个数组中
(2) 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出
- 第1轮排序后：542 53 3 14 214 748
- 第2轮排序后： 3 14 214 542 748 53
- 第3轮排序后：3 14 53 214 542 748 【ok】
- 第3轮排序 [按照百位排序]
- 将 各个数，按照百位大小 放入到 对应的 各个数组中
- 然后从 0-9 个数组/桶，依次，按照加入元素的先后顺序取出
- 第3轮排序 [按照百位排序]
4、基数排序代码实现
要求：将数组 {53, 3, 542, 748, 14, 214 } 使用基数排序, 进行升序排序
思路分析：前面的图文已经讲明确
-
基数排序的说明:
- 基数排序是对传统桶排序的扩展，速度很快.
- 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError
- 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
- 有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9
代码如下
//第一轮，针对每个元素的个位数进行排序处理 //定义一个二维数组，标识10个同，每个桶都是一维数组 //说明 //1.二维数组包含10个一位数组 //2.为了防止在放入数的时候，数据溢出，则每个一维数组（桶），大小为arr.length //3.基数排序是使用空间换时间的经典算法 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中实际存放了多少条数据，定义一个一维数组来记录各个桶每次放入的数据 //bucketElementCounts[0],记录的就是bucket[0]桶的数据 int[] bucketElementCounts = new int[10]; //获取数组最大值和最大长度 int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (max < arr[i]) { max = arr[i]; } } int maxLength = Integer.toString(max).length(); //桶排序 for (int k = 0, n = 10; k < maxLength; k++, n *= 10) { //第一轮，处理个位 for (int i = 0; i < arr.length; i++) { int Digits = arr[i] / n % 10; bucket[Digits][bucketElementCounts[Digits]] = arr[i]; bucketElementCounts[Digits]++; } //按照桶的顺序，依次取出数据放入到原来的数组 int index = 0; //遍历每个桶 for (int i = 0; i < bucketElementCounts.length; i++) { //如果该桶有数据，则取出 if (bucketElementCounts[i] != 0) { //取出的个数未每个桶对应数据的实际个数 for (int j = 0; j < bucketElementCounts[i]; j++) { //取出元素，放入到原数组 arr[index] = bucket[i][j]; index++; } //第一轮处理后，需要将计数bucketElementCounts所有数据归零 bucketElementCounts[i] = 0; } } } }
5、常用排序算法对比
非线性结构
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
1、树结构
1、为什么需要树这种数据结构
-
数组存储方式的分析优点：
- 通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
- 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图]
-
链式存储方式的分析优点：
- 在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
- 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 【示意图】
-
树存储方式的分析
- 能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。【示意图,后面详讲】案例: [7, 3, 10, 1, 5, 9, 12]
2、二叉树的概念
- 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
- 二叉树的子节点分为左节点和右节点。
- 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
- 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
我们重点讲解一下二叉树的前序遍历，中序遍历和后序遍历。
3、二叉树遍历的说明
使用前序，中序和后序对下面的二叉树进行遍历.
-
前序遍历: 先输出父节点，再遍历左子树和右子树
-
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
-
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
小结: 看输出父节点的顺序，就确定是前序，中序还是后序
4、应用案例
- 要求如下：
- 前上图的 3号节点 “卢俊” , 增加一个左子节点 [5, 关胜]
- 使用前序，中序，后序遍历，请写出各自输出的顺序是什么?
5、二叉树-查找指定节点
- 要求
- 请编写前序查找，中序查找和后序查找的方法。
- 并分别使用三种查找方式，查找 heroNO = 5 的节点
- 并分析各种查找方式，分别比较了多少次
- 思路
- 前序、中序、后序查找是根据根节点的位置来作出区别的
- 前序查找，则第一个则要比较根节点是否相同，不相同的左递归查找。其余相同，不同的是根节点的位置
6、二叉树-删除节点
- 要求
- 如果删除的节点是叶子节点，则删除该节点
- 如果删除的节点是非叶子节点，则删除该子树.
- 测试，删除掉 5号叶子节点 和 3号子树.
思考题(课后练习)
-
如果要删除的节点是非叶子节点，现在我们不希望将该非叶子节点为根节点的子树删除，需要指定规则, 假如规定如下:
-
如果该非叶子节点A只有一个子节点B，则子节点B替代节点A
-
如果该非叶子节点A有左子节点B和右子节点C，则让左子节点B替代节点A。
-
请大家思考，如何完成该删除功能, 老师给出提示.(课后练习)
-
后面在讲解 二叉排序树时，在给大家讲解具体的删除方法
-
2、顺序存储二叉树的概念
1、顺序存储二叉树的概念
-
基本说明
- 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看示意图。
-
要求:
- 右图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6]
- 要求在遍历数组 arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
顺序存储二叉树的特点:
- 顺序二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为 2 * n + 1
- 第n个元素的右子节点为 2 * n + 2
- 第n个元素的父节点为 (n-1) / 2
- n : 表示二叉树中的第几个元素(按0开始编号如图所示)
2、顺序存储二叉树遍历
需求: 给你一个数组 *{*1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7
课后练习：请同学们完成对数组以二叉树中序，后序遍历方式的代码.
3、线索化二叉树
先看一个问题
**将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. **n+1=7
- 问题分析:
- 当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
- 但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.
- 如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?
- 解决方案-线索二叉树
1、基本介绍
-
n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
-
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
-
一个结点的前一个结点，称为前驱结点
-
一个结点的后一个结点，称为后继结点
2、应用案例
应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
思路分析: 中序遍历的结果：{8, 3, 10, 1, 14, 6}
说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:
- left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
- right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.
3、遍历线索化二叉树
-
**说明：**对前面的中序线索化的二叉树， 进行遍历
-
**分析：**因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
-
代码：
课后作业:
我这里讲解了中序线索化二叉树，前序线索化二叉树和后序线索化二叉树的分析思路类似，同学们作为课后作业完成.