Java数据结构与算法
冷环渊
2022年04月02日 · 阅读 91
数据结构与算法
稀疏数组
二维数组创建方法
int arr[][] = new int[1][1];
第一个【】内存放有多少个一维数组
第二个【】存放一维数组的长度
arr[0][0] = 1
arr[0][1] =2
arr[0][2] =3
[输出]
[1,2,3]
二维数组的遍历
int arr[][] = new int[2][2];
for (int[] row : arr) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
棋盘案例
稀疏 sparsearray 数组，编写的五子棋程序中，有存盘退出和续上盘的功能。
分析问题:
因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据.->稀疏数组。
稀疏数组介绍
使用场景
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。 
我们创造的稀疏数组，
- 也是一个二维数组 他的【0】【n】会用来存放原来的二维数组的大小和长度
- 接下来的【n】【n】都会用放每一个值和他的二维数组坐标
应用实例
- 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
- 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
- 整体思路分析
编写实例思路操作图
代码实现
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.SarseArray
* @className: sarseArray
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2021/12/15 16:14
* @version: 1.0
*/
public class sarseArray {
public static void main(String[] args) {
/*创建原始的二维数组 11*11*/
//0：表示没有棋子，1表示黑子，2表示白字
int chessArr[][] = new int[11][11];
chessArr[1][2] = 1;
chessArr[2][3] = 2;
chessArr[4][6] = 3;
System.out.println("输出原始的二维数组");
for (int[] row : chessArr) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
//遍历二维数组所有非0 的数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr[i][j] != 0) {
sum++;
}
}
}
System.out.println("sum = " + sum);
//将二维数组转化成 稀疏数组，创建对应的稀疏数组
int sparseArr[][] = new int[sum + 1][3];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
// 完成了上述的步骤我们就拿到了 稀疏数组的第一行 就是我们存放数组大小和值的
//接下来我们需要将二维数组的值放到 稀疏数组中
/*
* sparseArr[?][0] = i
* sparseArr[?][1] = j
* sparseArr[?][2] = chessArr[i][j];
* 我们通过这种方式将 二维数组的坐标和值存到稀疏数组中
* */
// 我们用一个int 变量来记录是第几个
int count = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr[i][j] != 0) {
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr[i][j];
}
}
}
// 输出稀疏数组
System.out.println();
System.out.println("得到的稀疏数组为");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
}
// 将稀疏数组回复成原始的二维数组
/*
* 1.先从稀疏数组的第一列 读取出 有关原始数组长度和有多少非0的值
* 2.之后读取稀疏数组的后几行数据，并且赋值给原始的二维数组即可
* */
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println("输出恢复之后的二维数组");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
输出结果
队列
队列的一个使用场景
银行排队的案例:
队列介绍
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
- 示意图：(使用数组模拟队列示意图)
数组模拟队列
数组模拟队列思路：思路图
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示
新增思路
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
- 将尾指针往后移：rear+1 , 当 front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
根据队列思路实现数组模拟队列
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Queue
* @className: ArrayQueueDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2021/12/16 14:24
* @version: 1.0
*/
public class ArrayQueueDemo {
public static void main(String[] args) {
//创建一个队列
ArrayQueue queue = new ArrayQueue(3);
char key = ' '; //接收用户输入
Scanner scanner = 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): 查看队列头的数据");
key = scanner.next().charAt(0);//接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出数据
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
/* 根据 数组来实现的队列*/
class ArrayQueue {
//队列最大上限
private int MaxSize;
//队列尾部
private int rear;
//队列头部
private int front;
//存放队列数据的数组
private int[] ArrayQueue;
/**
* @author 冷环渊 Doomwatcher
* @context: 初始化构造队列，初始化队列和头尾值向
* @date: 2021/12/16 14:30
* @param maxSize
* @return:
*/
public ArrayQueue(int maxSize) {
// 获取最大值
this.MaxSize = maxSize;
//初始化 队列
ArrayQueue = new int[MaxSize];
//设置最大最小值
rear = -1;
front = -1;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 判断是否队列是否达到存储上限
* @date: 2021/12/16 14:30
* @param
* @return: boolean
*/
public boolean isfull() {
return rear == MaxSize - 1;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 判断队列是否是空的
* @date: 2021/12/16 14:32
* @param
* @return: boolean
*/
public boolean isemity() {
return rear == front;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 向队列插入一条数据
* @date: 2021/12/16 14:34
* @param value
* @return: void
*/
public void addQueue(int value) {
if (isfull()) {
System.out.println("队列已满 不能加入更多的数据");
return;
}
//++ 是后赋值，意思是执行完当前赋值，rear向后移动一位
rear++;
ArrayQueue[rear] = value;
}
/**
* @author 冷环渊 Doomwatcher
* @context:获取队列的值
* @date: 2021/12/16 14:37
* @param
* @return: void
*/
public int getQueue() {
if (isemity()) {
throw new RuntimeException("该队列是空的 无法获取到内容");
}
front++;
return ArrayQueue[front];
}
/**
* @author 冷环渊 Doomwatcher
* @context:遍历队列输出 注意是遍历 不会更改队列的指向
* @date: 2021/12/16 14:42
* @param
* @return: void
*/
public void showQueue() {
if (isemity()) {
System.out.println("队列没有可以遍历的数值");
}
for (int i = 0; i < ArrayQueue.length; i++) {
System.out.printf("arrQueue[%d]: %d\n", i, ArrayQueue[i]);
}
}
/**
* @author 冷环渊 Doomwatcher
* @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据
* @date: 2021/12/16 14:45
* @param
* @return: void
*/
public int headQueue() {
if (isemity()) {
throw new RuntimeException("没有头数据");
}
return ArrayQueue[front + 1];
}
}
问题分析并优化
- 目前数组使用一次就不能用， 没有达到复用的效果
- 将这个数组使用算法，改进成一个环形的队列 取模：%
数组模拟环形队列
对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明：
- 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 满]
- rear == front [空]
根据思路实现数组模拟环形队列
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Queue
* @className: CircleArrayQueueDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2021/12/16 16:28
* @version: 1.0
*/
public class CircleArrayQueueDemo {
public static void main(String[] args) {
System.out.println("测试环形队列");
//创建一个队列 这里空间为4 最大有效空间为3 留出一个空间作为约定
CircleArrayQueue queue = new CircleArrayQueue(4);
char key = ' '; //接收用户输入
Scanner scanner = 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): 查看队列头的数据");
key = scanner.next().charAt(0);//接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出数据
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
/** 环形队列
* 思路变化：
* 之前的队列有问什么问题所在
* 问题分析并优化
*1) 目前数组使用一次就不能用， 没有达到复用的效果
*2) 将这个数组使用算法，改进成一个环形的队列 取模：%
* 思路如下 ：
* 1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr(front]就是队列的第一个元素
* front的初始值
* 2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.
* rear的初始值=0
* 3.当队列满时，条件是（rear+1)%maxSize=front【满】
* 4.对队列为空的条件，rear==front空
* 5.当我们这样分析，队列中有效的数据的个数（rear+maxSize-front)%maxSize//rear=1front=0
* 6.我们就可以在原来的队列上修改得到，一个环形队列
*
* */
class CircleArrayQueue {
//队列最大上限
private int MaxSize;
//队列尾部 思路发生变化这次我们的队尾值变化为0指向队列最后一位的前一位
private int rear;
//队列头部 思路变化 指向队头的第一位 也就是下标 为 0
private int front;
//存放队列数据的数组
private int[] ArrayQueue;
/**
* @author 冷环渊 Doomwatcher
* @context: 初始化构造队列，初始化队列和头尾值向
* 这里为什么没有初始化队头队尾，因为默认 = 0
* @date: 2021/12/16 14:30
* @param maxSize
* @return:
*/
public CircleArrayQueue(int maxSize) {
// 获取最大值
this.MaxSize = maxSize;
//初始化 队列
ArrayQueue = new int[MaxSize];
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 这里思路变化，因为我们要做环形队列这里我们有一个位置是动态变化的所以我们需要更新计算是否队列已满的方法
* @date: 2021/12/16 14:30
* @param
* @return: boolean
*/
public boolean isfull() {
return (rear + 1) % MaxSize == front;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 判断队列是否是空的
* @date: 2021/12/16 14:32
* @param
* @return: boolean
*/
public boolean isemity() {
return rear == front;
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 加入数据我们也要发生变化 这里我们用的是环形了
* rear 的后移不再是最后一位，可能会出现越界的问题
* （rear+1）%maxSize
* @date: 2021/12/16 14:34
* @param value
* @return: void
*/
public void addQueue(int value) {
if (isfull()) {
System.out.println("队列已满 不能加入更多的数据");
return;
}
//赋值
ArrayQueue[rear] = value;
//考虑用取模来后移 rear
rear = (rear + 1) % MaxSize;
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 为什么不用 ++了呢 因为我们是环形 一定会出现越界，这里考虑取模动态的算出后移的位置
* @date: 2021/12/16 14:37
* @param
* @return: void
*/
public int getQueue() {
if (isemity()) {
throw new RuntimeException("该队列是空的 无法获取到内容");
}
/*
* 1，我们这次的思路是front代表的是队列的第一个下标
* 2. 用临时变量来拿出 当前的值
* 3.后移front 返回值
* */
int value = ArrayQueue[front];
front = (front + 1) % MaxSize;
return value;
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 遍历环形队列 输出 这里我们不再是遍历数组长度了
* 我们需要求出有效的数量
* @date: 2021/12/16 14:42
* @param
* @return: void
*/
public void showQueue() {
if (isemity()) {
System.out.println("队列没有可以遍历的数值");
}
//这里我们因该是从 front 开始遍历
for (int i = front; i < front + Size(); i++) {
//这里下标我们选择取模 应为是环形的会出现越界的情况，所以我们使用取模运算
System.out.printf("arrQueue[%d]: %d\n", i % MaxSize, ArrayQueue[i % MaxSize]);
}
}
/*编写一个求出队列有效数据数量的放啊*/
public int Size() {
/* 取模思路套用
* 1. rear = 1
* 2. front = 0
* 3. maxSize = 3
* （1+3-0）%3 = 1 应为算出来是下标 所以我们这里有两个有效数据 0，1
* */
return (rear + MaxSize - front) % MaxSize;
}
/**
* @author 冷环渊 Doomwatcher
* @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据
* 这里不再是 front-1 应为 front此时默认就是0
* @date: 2021/12/16 14:45
* @param
* @return: void
*/
public int headQueue() {
if (isemity()) {
throw new RuntimeException("没有头数据");
}
return ArrayQueue[front];
}
}
代码执行效果
链表
链表(Linked List)介绍 :
链表是有序的列表，但是它在内存中是存储如下
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域， next 域：指向下一个节点.
- 如图：发现链表的各个节点不一定是连续存储.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单向链表
单向链表存储节点思路图
单链表的应用实例
使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作
我们都知道 水浒传里有108位英雄吧
我们这里随便举例四个，我们想用链表的方式把他们放入我们的英雄榜里（单向链表）
新增，修改，删除的思路
添加英雄:
根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:
修改节点功能
古时候，有武功的人士逗喜欢为了排名去争斗，所以我们制作英雄榜需要有更换排名的功能
排名是固定的，他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可
- 先找到该节点，通过遍历，
- temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname
删除节点
这个功能呢可以理解为，有英雄不想争夺排名了，退休回家种田耕地享受生活了，我们需要把不需要位置的英雄占有的位置腾出来。
单向链表的增删改查
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.LinkedList
* @className: LinkedlistDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2021/12/17 16:24
* @version: 1.0
*/
public class LinkedlistDemo {
public static void main(String[] args) {
// 设置一些英雄对象
HeroNode heroNode = new HeroNode(1, "宋江", "及时雨");
HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星");
HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头");
// 声明单向链表
SingleLinkedlist linkedlist = new SingleLinkedlist();
//加入我们的英雄节点
//linkedlist.add(heroNode);
//linkedlist.add(heroNode1);
//linkedlist.add(heroNode2);
//linkedlist.add(heroNode3);
//加入按照编号
linkedlist.addByOrder(heroNode);
linkedlist.addByOrder(heroNode3);
linkedlist.addByOrder(heroNode2);
linkedlist.addByOrder(heroNode1);
//输出节点信息
linkedlist.List();
System.out.println("更新数据后");
linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师"));
//输出节点信息
linkedlist.List();
System.out.println("删除数据后输出");
linkedlist.DeleteNode(1);
linkedlist.List();
}
}
class SingleLinkedlist {
//创建一个头结点
HeroNode head = new HeroNode(0, "", "");
//加入链表
public void add(HeroNode node) {
//头节点不能动 这里我们用一个临时指针来记录
HeroNode temp = head;
//遍历链表
while (true) {
//遍历为空就代表找了最后一个节点
//不为空就后移一位继续找
if (temp.next == null) {
break;
}
//没有找到最后就后移 temp
temp = temp.next;
}
//跳出while证明找到了最后的节点，将我们的新节点加入到最后的节点的next即可
temp.next = node;
}
//添加节点 第二种方法
public void addByOrder(HeroNode node) {
/*
* 因为头结点不能动，我们通过指针来记录头节点来帮助找到添加的位置
*因为是单链表我们找的是 Temp是位于添加位置的前一个节点，否则插入不了
* */
//创建一个临时变量
HeroNode temp = head;
//用来标识 英雄是否存在 默认为不存在（false）
boolean flag = false;
while (true) {
//找到最后为空的位置
if (temp.next == null) {
break;
}
//如果temp的下一个no 大于 我们加入的节点，就往temp加入
if (temp.next.No > node.No) {
break;
}
//如果下一个节点等于 加入节点的No 那么就代表已经存在了节点
else if (temp.next.No == node.No) {
//将flag 修改为 true 代表已经存在
flag = true;
break;
}
//如果上面的都没达成就代表当前节点位置不对，向后继续遍历
temp = temp.next;
}
// 判断 flag的值
if (flag) {
//如果为 true 代表节点已经存在
System.out.printf("当前节点%d已经存在了，不能加入\n", node.No);
} else {
// 如果为false 那代表符合插入条件并且不存在与当前链表
node.next = temp.next;
temp.next = node;
}
}
//修改节点信息
public void updateNode(HeroNode newHeroNode) {
if (head.next == null) {
System.out.println("链表是空的");
}
//这里是头节点不能修改，我用 temp 来指向头结点
HeroNode temp = head.next;
// 是否找到了no的标识
boolean flag = false;
while (true) {
//找到最后一个
if (temp == null) {
break;
}
if (temp.No == newHeroNode.No) {
//如果等于 那么代表可以修改
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
// true 修改信息
temp.NickName = newHeroNode.NickName;
temp.Name = newHeroNode.Name;
} else {
System.out.printf("没有找到 %d 这个节点", newHeroNode.No);
}
}
//删除节点信息
public void DeleteNode(int no) {
HeroNode temp = head;
// 用来标注 是不是可以删除
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.No == no) {
flag = true;
break;
}
temp = temp.next;
}
//根据flag 删除Node
if (flag) {
//找到的话就删除，这里我们只需要指向空 GC会回收
temp.next = temp.next.next;
} else {
System.out.printf("要删除的 %d 没有找到", no);
}
}
//遍历链表
public void List() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
//头节点不能动 这里我们用一个临时指针来记录
HeroNode temp = head.next;
while (true) {
//遍历为空就代表找了最后一个节点
if (temp == null) {
break;
}
//输出节点
System.out.println(temp);
//后移一位
temp = temp.next;
}
}
}
/**
* 编写 水浒传英雄 节点
* 用于存放每个英雄的属性
* */
class HeroNode {
//排名
public int No;
// 姓名
public String Name;
//昵称
public String NickName;
// 下一个是哪位好汉
public HeroNode next;
public HeroNode(int hNo, String hName, String hNickName) {
this.No = hNo;
this.Name = hName;
this.NickName = hNickName;
}
//方便输出语句输出
@Override
public String toString() {
return "HeroNode{" +
"No=" + No +
", Name='" + Name + '\'' +
", NickName='" + NickName + '\'' +
'}';
}
}
链表使用效果
总结
我们这次制作了属于自己的英雄榜（单向链表）,我们收货了什么呢？
- 节点之间联系的思路
- 逐渐适应数据结构的一些思想
- 动手实操实现的习惯
单向链表各大厂面试题
新浪
/**
* @author 冷环渊 Doomwatcher
* @context:
* 新浪链表面试题 查找链表中的第k个节点
* 思路：
* 1.编写一个方法，接收head 节点，同时接收一个index
* 2，index表示的是倒数第index 个节点
* 3. 先把链表从头到尾遍历 得到链表的总长度 getlength
* 4。得到Size之后 我们从链表的第一个开始遍历（Size-index）个，就可以得到
* 5. 如果找到了 则返回该节点否则返回null
* @date: 2021/12/18 15:12
* @param head
* @param index
* @return: com.hyc.DataStructure.LinkedList.HeroNode
*/
public static HeroNode getLastIndexNode(HeroNode head, int index) {
// 如果除去头节点之后没有新的节点就代表链表是空的，返回空对象
if (head.next == null) {
return null;
}
// 获取到链表的长度
int Size = SingleLinkedlist.getlength(head);
//声明一个零时变量指向第一个有效的节点
HeroNode cur = head.next;
//假设 我们的例子是一共有三个有效节点 3 这里我们index 为 2 那么3-2 = 1 找到了倒数第二个的节点
for (int i = 0; i < Size - index; i++) {
cur = cur.next;
}
//找到节点之后我们直接返回即可
return cur;
}
腾讯
/**
* @author 冷环渊 Doomwatcher
* @context: 腾讯面试题 反转链表
* 思路:
* 1.先定义一个节点 reverseHead = new HeroNode();
* 2.从头遍历原来的链表，每次遍历一个节点就将其取出并且放到信的链表的最前端，
* 3.原来的链表head.next = reverseHead.Next
* @date: 2021/12/18 15:38
* @param head
* @return: void
*/
public static void reverseList(HeroNode head) {
if (head.next == null || head.next.next == null) {
return;
}
//需要新的一个空的头
HeroNode reverseHead = new HeroNode(0, "", "");
// 获得第一个有效的节点
HeroNode cur = head.next;
//指向[cur]的下一个的节点
HeroNode next = null;
while (cur != null) {
//保存当前的节点的下一个位置 有用
next = cur.next;
// 将cur的下一个指向 新的链表的最前端
cur.next = reverseHead.next;
//将新链表的最前端为cur
reverseHead.next = cur;
//cur 继续向后遍历
cur = next;
}
head.next = reverseHead.next;
}
百度
/**
* @author 冷环渊 Doomwatcher
* @context: 百度面试题， 在不破坏链表结构的情况下 反向输出链表
* 这里我们利用 一个 即将学到的 数据结构叫 栈
* 栈结构的特点就是 先进后出
* 将链表的节点按顺序遍历压入栈
* 利用栈先进后出的特质，就可以保证性能的情况下输出不改变结构的倒序链表
* @date: 2021/12/19 13:48
* @param
* @return: void
*/
public static void showreverseList(HeroNode node) {
if (node.next == null) {
return;
}
Stack<HeroNode> stack = new Stack<>();
HeroNode cur = node.next;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
课后练习
/**
* @author 冷环渊 Doomwatcher
* @context: 合并两个链表 并且有序
* @date: 2021/12/19 14:15
* @param list1
* @param list2
* @return: com.hyc.DataStructure.LinkedList.SingleLinkedlist
*/
public static HeroNode mergeList(HeroNode list1, HeroNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
HeroNode head = new HeroNode(0, "", "");
HeroNode temp = head;
while (list1 != null && list2 != null) {
if (list1.No < list2.No) {
temp.next = list1;
list1 = list1.next;
} else {
temp.next = list2;
list2 = list2.next;
}
temp = temp.next;
}
if (list1 == null) {
temp.next = list2;
}
if (list2 == null) {
temp.next = list1;
}
return head.next;
}
双向链表
双向链表应用实例,双向链表的操作分析和实现
管理单向链表的缺点分析:
-
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
-
向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
-
分析了双向链表如何完成遍历，添加，修改和删除的思路
双向链表实现思路
分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现
- 遍历 方和 单链表一样，只是可以向前，也可以向后查找
- 添加 (默认添加到双向链表的最后)
- (1) 先找到双向链表的最后这个节点
- (2) temp.next = newHeroNode
-
newHeroNode.pre = temp;
-
修改 思路和 原来的单向链表一样. 4) 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
实现链表节点
/**
* 双向链表要用的节点
* */
class ListNode {
//排名
public int No;
// 姓名
public String Name;
//昵称
public String NickName;
// 下一个节点
public ListNode next;
//上一个节点
public ListNode pre;
public ListNode(int hNo, String hName, String hNickName) {
this.No = hNo;
this.Name = hName;
this.NickName = hNickName;
}
//方便输出语句输出
@Override
public String toString() {
return "HeroNode{" +
"No=" + No +
", Name='" + Name + '\'' +
", NickName='" + NickName + '\'' +
'}';
}
}
双向链表实现
class DoubleLinkedList {
//创建一个头结点
ListNode head = new ListNode(0, "", "");
public ListNode getHead() {
return head;
}
public void setHead(ListNode head) {
this.head = head;
}
//遍历链表
public void List() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
//头节点不能动 这里我们用一个临时指针来记录
ListNode temp = head.next;
while (true) {
//遍历为空就代表找了最后一个节点
if (temp == null) {
break;
}
//输出节点
System.out.println(temp);
//后移一位
temp = temp.next;
}
}
//加入双向链表
public void add(ListNode node) {
//头节点不能动 这里我们用一个临时指针来记录
ListNode temp = head;
//遍历链表
while (true) {
//遍历为空就代表找了最后一个节点
//不为空就后移一位继续找
if (temp.next == null) {
break;
}
//没有找到最后就后移 temp
temp = temp.next;
}
//指向下一个节点
temp.next = node;
//指向上一个节点
node.pre = temp;
}
//修改双向链表，和单向链表基本一致不需要过多的修改
//修改节点信息
public void updateNode(ListNode newlistnode) {
if (head.next == null) {
System.out.println("链表是空的");
}
//这里是头节点不能修改，我用 temp 来指向头结点
ListNode temp = head.next;
// 是否找到了no的标识
boolean flag = false;
while (true) {
//找到最后一个
if (temp == null) {
break;
}
if (temp.No == newlistnode.No) {
//如果等于 那么代表可以修改
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
// true 修改信息
temp.NickName = newlistnode.NickName;
temp.Name = newlistnode.Name;
} else {
System.out.printf("没有找到 %d 这个节点", newlistnode.No);
}
}
/*
* 双向链表删除
* 对于双向链表来说就不需要找到上一个节点来删除了，
* 可以找到自己删除
* */
public void DeleteNode(int no) {
if (head.next == null) {
System.out.println("链表为空 不需要删除");
return;
}
ListNode temp = head.next;
// 用来标注 是不是可以删除
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.next.No == no) {
flag = true;
break;
}
temp = temp.next;
}
//根据flag 删除Node
if (flag) {
//找到的话就删除，这里我们只需要指向空 GC会回收
//temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了
/*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/
temp.pre.next = temp.next;
/*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点，相当于向前的pre 直接快过当前的节点指向上一个
* 如果当前节点是最后一节点，就不执行后面这个将下一个节点的指向更改，不然会出现空指针
* */
if (temp.next != null) {
temp.next.pre = temp.pre;
}
/*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/
} else {
System.out.printf("要删除的 %d 没有找到", no);
}
}
}
总结
双向链表在之前的基础上：
- 对比单向链表 双向链表可以自己删除，
- 双线链表正反遍历更加的容易
环形链表
认识单向环形链表
这里我们以单向环形链表为例子
就是我们最后一个节点的next域指向头结点，形成闭环
引用场景以及问题
Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由
此产生一个出队编号的序列。
思路提示：
提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。
Josephu 问题解题思路
认识约瑟夫问题，以及我们想要实现的场景，
- 编写实现 单向环形链表
- 约瑟夫问题的要求 根据区间报数 报数的小孩出列
- coding 出我们需要的需求
实现单向循环链表
思路
大体上和我们的单向链表有雷同的地方，区别在于：
- 我们需要在创建链表的时候将尾结点的最后一个指向头结点，这也就意味着我们需要有至少两个指针来记录头尾节点。
- 遍历的方式也要有些许的变化，结束循环的条件从
head.next = null改变成CurBoy.next(指向尾部节点的指针) = first;最后为头节点的时候遍历为第二个
我们简单的先创建一个实现链表需要的节点对象
约瑟夫问题环形链表的节点
//环形链表 约瑟夫问题 节点
class Boy {
private int No;
private Boy Next;
public Boy(int no) {
this.No = no;
}
public int getNo() {
return No;
}
public void setNo(int no) {
No = no;
}
public Boy getNext() {
return Next;
}
public void setNext(Boy next) {
Next = next;
}
}
创建环形链表对象实现生成链表和遍历链表，以及解决约瑟夫问题的方（具体的实现思路见代码注释）
// 环形单向链表
class CircleSingleLinkeList {
Boy first = null;
/**
* @author 冷环渊 Doomwatcher
* @context: 一个环形链表 参数是这个链表有多少节点
* @date: 2021/12/21 15:47
* @param nums
* @return: void
*/
public void CreateListNode(int nums) {
if (nums < 1) {
System.out.println("无法开始游戏，因为链表小于最小的游戏节点数量");
return;
}
// 创建一个 辅助之间用于遍历和指向节点
Boy curBoy = null;
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
//如果只有一个节点的话 也可以生成环形链表
if (i == 1) {
first = boy;
first.setNext(first);
curBoy = first;//将辅助指针指向链表的第一个节点 形成闭环
} else {
// 如果不是一个的话就生成多个节点
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
public void showListBoy() {
if (first == null) {
System.out.println("链表为空，不能遍历");
return;
}
// frist 节点不能移动 我们创建一个指针
Boy curboy = first;
while (true) {
System.out.printf("小孩的编号是： %d \n", curboy.getNo());
// 说明已经遍历完毕
if (curboy.getNext() == first) {
break;
}
//后移 curboy
curboy = curboy.getNext();
}
}
/**
* @author 冷环渊 Doomwatcher
* @context: 这里我们以小孩做游戏来解决约瑟夫问题，
* @date: 2021/12/22 21:16
* @param nums 一共有多少个小孩
* @param start 从那个小孩开始报数
* @param index 每隔几个小孩报数一次
* @return: void
*/
public void JosephuFunc(int nums, int start, int index) {
if (first == null || start < 1 || start > nums) {
System.out.println("参数不对，请重新输入参数");
return;
}
Boy helper = first;
//将 helper遍历到最后一个节点
while (true) {
if (helper.getNext() == first) {
break;
}
helper = helper.getNext();
}
// 小孩子 报数之前，要遍历指针到从start开始的小孩的节点
for (int i = 0; i < start - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数的时候 让 first和helper 同时移动m-1次 然后出圈
//这里循环操作 知道圈中的一个节点
while (true) {
//说明列表只有一个节点
if (helper == first) {
break;
}
//循环之后将 指针后移
for (int i = 0; i < index - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
// 这个时候 first选中的节点就是要出圈的小孩
System.out.printf("小孩 %d 出圈\n", first.getNo());
//出圈操作
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后剩下的小孩 %d \n", first.getNo());
}
}
实现结果
栈
我们这里将一个场景带入学习
请输入一个表达式
计算式:[722-5+1-5+3-3] 点击计算 计算出结果
请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。----> 栈
栈的介绍
-
栈的英文为(stack)
-
栈是一个先入后出(FILO-First In Last Out)的有序列表。
-
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的 一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
-
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元 素最先删除，最先放入的元素最后删除
-
图解方式说明出栈(pop)和入栈(push)的概念
入栈与出栈 ： 栈 数据结构的特性 先入后出
栈的应用场景
-
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以 回到原来的程序中。
-
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆 栈中。
-
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
-
二叉树的遍历。
-
图形的深度优先(depth 一 first)搜索法。
栈 快速入门（数组模拟栈）
实现思路
详细的每一部分的思路 都在代码的注释当中，想要详细理解可以参考代码中的注释
package com.hyc.DataStructure.Stack;
import java.util.Scanner;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: ArrayStackDemo
* @author: 冷环渊 doomwatcher
* @description: TODO 用数组来模拟栈
* @date: 2021/12/23 18:08
* @version: 1.0
*/
public class ArrayStackDemo {
public static void main(String[] args) {
//测试一下 ArrayStack 是否正确
//先创建一个 ArrayStack 对象->表示栈
ArrayStack stack = new ArrayStack(4);
String key = "";
boolean loop = true; //控制是否退出菜单
Scanner scanner = new Scanner(System.in);
while (loop) {
System.out.println("show: 表示显示栈");
System.out.println("exit: 退出程序");
System.out.println("push: 表示添加数据到栈(入栈)");
System.out.println("pop: 表示从栈取出数据(出栈)");
System.out.println("请输入你的选择");
key = scanner.next();
switch (key) {
case "show":
stack.list();
break;
case "push":
System.out.println("请输入一个数");
int value = scanner.nextInt();
stack.push(value);
break;
case "pop":
try {
int res = stack.pop();
System.out.printf("出栈的数据是 %d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~~");
}
}
class ArrayStack {
//栈的最大长度
private int MaxSize;
//模拟栈 数据就放在这个数组里
private int[] stack;
// 等于栈顶 默认等于-1 代表最底部分
private int top = -1;
public ArrayStack() {
}
// 初始化栈
public ArrayStack(int maxSize) {
MaxSize = maxSize;
stack = new int[maxSize];
}
//返回栈顶 只是显示 并不是 pop 不会改变栈的结构
public int peek() {
return stack[top];
}
//判断栈是否是满的
public boolean isFull() {
return top == MaxSize - 1;
}
//判断栈 是否是空的
public boolean isempty() {
return top == -1;
}
//将数据压入栈
public void push(int data) {
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = data;
}
// 将数据取出栈
public int pop() {
if (isempty()) {
throw new RuntimeException("栈是空的 无法取出");
}
int value = stack[top];
top--;
return value;
}
//遍历栈 遍历的时候需要从栈顶开始显示数据
public void list() {
if (isempty()) {
System.out.println("栈是空的");
}
// 从栈顶开始输出 其实就是倒序的输出数组
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
小总结
- 这里我们用数组模拟了栈的一些基础操作，入栈出栈遍历内容，
- 除了使用数组，我们还可以使用链表来实现栈，这里我也写了这种写法有详细的注释，代码如下
package com.hyc.DataStructure.Stack;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: ListStackDemo
* @author: 冷环渊 doomwatcher
* @description: TODO 用链表来模拟栈
* @date: 2021/12/23 18:23
* @version: 1.0
*/
public class ListStackDemo {
public static void main(String[] args) {
listStack listStack = new listStack();
listStack.push(5);
listStack.push(6);
listStack.push(9);
System.out.println("出栈前");
listStack.list();
System.out.println("出栈后");
System.out.println("出栈：" + listStack.pop());
System.out.println("出栈：" + listStack.pop());
listStack.list();
}
}
class listStack {
//创建一个头结点
StackNode head = new StackNode(0);
StackNode temp = head;
//判断是否为空
public boolean isempty() {
return head.next == null;
}
//压入栈
public void push(int value) {
//创建节点对象
StackNode newnode = new StackNode(value);
//改变头节点指针的指向
temp.next = newnode;
//指针后移
temp = temp.next;
}
//出栈
public int pop() {
if (isempty()) {
throw new RuntimeException("栈空");
}
StackNode Before = head;
//将 before 节点遍历到 temp也就是最后一个节点的上一个节点，让temp指针想前遍历
while (true) {
if (Before.next == temp) {
break;
}
Before = Before.next;
}
//将before的下一个节点为空相当于出栈之后 删除引用
Before.next = null;
//取值
int value = temp.data;
//此时 before指向的这个节点就是上一个节点的位置，将temp前移动，重复操作实现出栈
temp = Before;
return value;
}
//遍历栈
public void list() {
// 判断非空
if (isempty()) {
System.out.println("栈是空的");
return;
}
StackNode temp = head;
while (true) {
if (temp.next == null) {
break;
}
System.out.println(temp.next.data);
temp = temp.next;
}
}
}
//单向链表节点
class StackNode {
// 数据
public int data;
//下一个节点
public StackNode next;
public StackNode(int data) {
this.data = data;
}
//方便输出语句输出
@Override
public String toString() {
return "StackNode{" +
", data='" + data + '\'' +
", next=" + next +
'}';
}
}
中缀表达式计算器
使用栈来实现综合计算器
计算机底层是如何处理这种公式的呢，思路如下
我们需要使用两个栈，一个记录数字，一个记录符号，根据这个栈的数据特性来通过符号和数据的出现规则来实现公式的计算
思路
- 1.通过一个index值（素引）,来遍历我们的表达式
- 2.如果我们发现是一个数字，就直接入数栈
- 3.如果发现扫描到是一个符号，就分如下情况
- 3.1如果发现当前的符号栈为空，就直接入栈
- 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
- 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
- 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
- 于栈中的操作符，就直接入符号找。
- 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
- 5.最后在数栈只有一个数字，就是表达式的结果
- 验证：3+2*6-2=13
- 这里我们就根据上面的思路实现接下来的思路
代码实现
package com.hyc.DataStructure.Stack;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: Calculator
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2021/12/24 20:39
* @version: 1.0
*/
public class Calculator {
public static void main(String[] args) {
// 根据文章的思路 我们这里完成对一串计算只包含加减乘除的表达式运算操作
String expression = "3+2*6-2";
/** 计算思路 使用栈完成表达式的计算思路
* 1.通过一个index值（素引）,来遍历我们的表达式
* 2.如果我们发现是一个数字，就直接入数栈
* 3.如果发现扫描到是一个符号，就分如下情况
* 3.1如果发现当前的符号栈为空，就直接入栈
* 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
* 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
* 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
* 于栈中的操作符，就直接入符号找。
* 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
* 5.最后在数栈只有一个数字，就是表达式的结果
* 验证：3+2*6-2=13
* 这里我们就根据上面的思路实现接下来的思路
* */
// 创建两个栈 一个存放需要计算的数字 一个存放需要运算的符号
ArrayCalStack numStack = new ArrayCalStack(10);
ArrayCalStack operStack = new ArrayCalStack(10);
// 定义相关变量
int index = 0; //用于指针扫描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
//将每次扫描得到的char保存到ch
char ch;
//用于萍姐多位数
String keepNums = "";
//开始while 循环扫描表达式 expression
while (true) {
// 一次得到expression的每一个字符
ch = expression.substring(index, index + 1).charAt(0);
// 判断ch 是什么（数字或者符号）之后进行操作
if (operStack.isOper(ch)) {
/* 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
* 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
* 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
* 于栈中的操作符，就直接入符号找。*/
//非空判断
if (!operStack.isempty()) {
if (operStack.priotrity(ch) <= operStack.priotrity(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
// 把运算结果压入 数字栈
numStack.push(res);
// 之后将当前的符号压入栈 不然会缺失一个运算符号
operStack.push(ch);
} else {
//如果当前的操作符的优先级别大于栈中的操作符 就直接进入符号栈
operStack.push(ch);
}
} else {
// 如果为空直接入符号栈
operStack.push(ch);
}
} else {
// 如果是数字 就直接进入数字栈
/*思路
* 这里我们要考虑到多位数 在处理多位数的时候
* 我们需要扫描这个数的下一位一直到找到下一个符号
* 这个时候我们定义一个字符串用于拼接找到的数
* */
// 处理多位数
keepNums += ch;
// 如果ch已经是 expression 最后一位name就直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNums));
} else {
// 判断下一个字符是不是数字 ，如果是就继续向下判断 是运算符则入栈，这里我们要看的是结束的地方是不是符号
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//如果最后一位事原酸父则如入栈 这里我们的操作变化就是 keepnums =1 或者是 keepnums = 123
numStack.push(Integer.parseInt(keepNums));
// 加入之后能讲 keepnunms清空 用于下一位的判断
keepNums = "";
}
}
}
// 让 index +1 并判断是否扫描到expression 最后
index++;
if (index >= expression.length()) {
break;
}
}
// 当表达式扫描完毕，就循序的从数栈和符号栈中 pop出相应的数和符号，并且运行
while (true) {
// 如果符号为空，则计算到最后的结果，数栈中只有一个数字【结果】
if (operStack.isempty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
//入栈
numStack.push(res);
}
// 将数栈最后的数，pop出，就是结果
int res2 = numStack.pop();
System.out.printf("表达式%s = %d", expression, res2);
}
}
/*
* 应为要实现计算器 我们需要编写一些新的功能，
* */
class ArrayCalStack {
//栈的最大长度
private int MaxSize;
//模拟栈 数据就放在这个数组里
private int[] stack;
// 等于栈顶 默认等于-1 代表最底部分
private int top = -1;
public ArrayCalStack() {
}
// 初始化栈
public ArrayCalStack(int maxSize) {
MaxSize = maxSize;
stack = new int[maxSize];
}
//返回栈顶 只是显示 并不是 pop 不会改变栈的结构
public int peek() {
return stack[top];
}
//判断栈是否是满的
public boolean isFull() {
return top == MaxSize - 1;
}
//判断栈 是否是空的
public boolean isempty() {
return top == -1;
}
//将数据压入栈
public void push(int data) {
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = data;
}
// 将数据取出栈
public int pop() {
if (isempty()) {
throw new RuntimeException("栈是空的 无法取出");
}
int value = stack[top];
top--;
return value;
}
//遍历栈 遍历的时候需要从栈顶开始显示数据
public void list() {
if (isempty()) {
System.out.println("栈是空的");
}
// 从栈顶开始输出 其实就是倒序的输出数组
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
/* 返回运算符的优先级 这个规则我们可以自己来设定 优先级使用数字来表示
* 数字越大优先级约高
* */
public int priotrity(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1;
}
}
// 判断是不是一个字符
public boolean isOper(char val) {
return val == '*' || val == '/' || val == '+' || val == '-';
}
// 计算操作 用于执行运算
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 = num1 * num2;
break;
default:
break;
}
return res;
}
}
这里我们实现了基础的表达式运算，但是我们没有考虑的事
- 我们实现了基本计算，但是没有考虑小括号等
- 中缀表达式对我们来说是十分的好算的，但是对于计算机计算是不方便的，之后会给大家更新适合计算机计算的后缀表达式
中缀转后缀表达式 逆波兰计算器实现
什么是前缀，什么中缀，什么是后缀？（理论加举例）
前缀
前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
我们完成一个逆波兰计算器，要求完成如下任务:
-
输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
-
支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
中缀
（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。
与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。
与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。
例：
（1）8+4-6*2用后缀表达式表示为：
8 4+6 2*-
（2）2*（3+5）+7/1-4用后缀表达式表示为**：**
235+*71/+4-
后缀
这种表示方式把运算符写在运算对象的后面，例如，把a+b写成ab+，所以也称为后缀式。这种表示法的优点是根据运算对象和算符的出现次序进行计算，不需要使用括号，也便于用械实现求值。对于表达式x:=(a+b)(c+d)，其后缀式为xab+cd+:=。
原表达式：a*(b*(c+d/e)-f)# /* # 为表达式结束符号*/
后缀式：abcde/+f-#
为运算符定义优先级：# ( + - * / **
-1 0 1 1 2 2 3
从原表达式求后缀式的规则为：
思路分析
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
1．从左至右扫描，将 3 和 4 压入堆栈；
2．遇到+运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得 7，再将 7 入栈；
3．将 5 入栈；
4．接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；
5．将 6 入栈；
6．最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果
代码实现
public static void main(String[] args) {
//定义逆波兰表达式
// 测试
String suffixExpression = "3 4 + 5 * 6 -";
// 思路
// 1. 先将 3 4 + 5 * 6 - 方法哦 ArrayList中
// 2. 将 Arraylist 传递一个方法 遍历ArrayList 配合栈完成计算
List<String> list = getListString(suffixExpression);
System.out.println("rpnlist = " + list);
int res = calculate(list);
System.out.println("计算的结果是 = " + res);
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将一个逆波兰表达式的数据和运算符 依次放入Arraylist中
* @date: 2021/12/25 18:09
* @param suffixExpression
* @return: java.util.List<java.lang.String> 将分割好的字符List 返回
*/
public static List<String> getListString(String suffixExpression) {
// 分割字符串 将后缀表达式的每一个字符取出
String[] split = suffixExpression.split(" ");
// 我们用list 来存储分割出来的表达式，这样之后我们就需要遍历即可
List<String> list = new ArrayList<>();
for (String ele : split) {
list.add(ele);
}
return list;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 这个方法就是 逆波兰表达式的运算处理方法
* * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 -
* * 1） 从左至右扫描，将3和4压入栈
* * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈
* * 3） 将5 入栈
* * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5 = 35 将结果入栈
* * 5） 将6 入栈
* @date: 2021/12/25 18:14
* @param ls
* @return: int 返回的是一个运算结果
*/
public static int calculate(List<String> ls) {
//创建栈 只需要一个栈即可
Stack<String> stack = new Stack<>();
// 遍历处理
for (String item : ls) {
// 这里我们用正则表达式来取出数字 和符号 如果是数字进行处理，如果符号做另外的处理
if (item.matches("\\d+")) {
//匹配的是数字
stack.push(item);
} else {
// 如果是符号就 pop出两个数 运算之后结果入栈
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if ("+".equals(item)) {
res = num1 + num2;
} else if ("-".equals(item)) {
res = num1 - num2;
} else if ("*".equals(item)) {
res = num1 * num2;
} else if ("/".equals(item)) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
// 把 res 入栈
stack.push("" + res);
}
}
//最后留在stack 中的数据是运算结果
return Integer.parseInt(stack.pop());
}
这里我们用list加栈的方式实现了表达式的运算
需要注意的几点：
- 从中体会 后缀表达式和中缀表达式的转换
- 计算上，后缀与中缀的区别
中缀转后缀表达式
大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发 中，我们需要将 中缀表达式转成后缀表达式。 所以我们需要用代码将中缀表达式处理成后缀表达式之后运算一劳永逸
思路
1.初始化两个栈 元素安抚栈 s1 和存储中间结果的栈2
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中的元素并且输出，结果逆序就是中缀表达式对应的后缀的表达式
思路举例
将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
因此结果为 :"1 2 3 + 4 × + 5 –"
编码
跟着思路来实现代码
代码实现
package com.hyc.DataStructure.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.Stack
* @className: PolandExpression
* @author: 冷环渊 doomwatcher
* @description: TODO
* 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 -
* 1） 从左至右扫描，将3和4压入栈
* 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈
* 3） 将5 入栈
* 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5 = 35 将结果入栈
* 5） 将6 入栈
* 最后 是 - 运算符 计算出 35-6 = 29 由此得出最后的结果
*
* 使用技术 这里我们用 java给我们提供的 Stack 和 ArrayList组合来实现计算器
* @date: 2021/12/25 18:00
* @version: 1.0
*/
public class PolandExpression {
public static void main(String[] args) {
//定义中缀表达式 ，转成后置表达式之后运算
String expression = "1+((2+3)*4)-5";
//拆成链表
List<String> infixExpressionList = toinfixExpression(expression);
System.out.println("中缀表达式对应的list=" + infixExpressionList);
List<String> suffixexpression = parseSuffixExpressionList(infixExpressionList);
System.out.println("后缀表达式对应的List" + suffixexpression);
System.out.printf("expression=%d", calculate(suffixexpression));
//定义逆波兰表达式
// 测试
String suffixExpression = "3 4 + 5 * 6 -";
// 思路
// 1. 先将 3 4 + 5 * 6 - 方法哦 ArrayList中
// 2. 将 Arraylist 传递一个方法 遍历ArrayList 配合栈完成计算
List<String> list = getListString(suffixExpression);
System.out.println("rpnlist = " + list);
int res = calculate(list);
System.out.println("计算的结果是 = " + res);
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将 Arraylist[1,+,(,(,2,+,3,),*,4,),-,5] 转化成 Arraylist[1,2,3,+,4,*,5,-]
* 转换思路：
* 1. 初始化两个栈 元素安抚栈 s1 和存储中间结果的栈2
* 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中的元素并且输出，结果逆序就是中缀表达式对应的后缀的表达式
*
* @date: 2021/12/27 17:48
* @param
* @return: java.util.List<java.lang.String>
*/
public static List<String> parseSuffixExpressionList(List<String> ls) {
// 定义两个栈
/*符号栈*/
Stack<String> s1 = new Stack<>();
/* S2 思路说明
* 这里我们使用栈 在转换过程中我们不需要pop操作，而且这个s2 之后我们需要逆序输出操作很麻烦
* 于是这里使用List来当作 s2 的数据存储结构
* */
List<String> s2 = new ArrayList<>();
// 遍历 ls
for (String item : ls) {
// 如果是一个数字 那么就加入 S2（这里我们字符串加入 正则表达式来判断是不是一个数字）
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
// 如果是 ）右括号 则一次弹出 s1栈顶的运算符 并且压入 s2 知道遇到左括号为止，完成前置的一系列操作之后将这一对括号丢弃
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
// 弹出（ 消除掉一组括号
s1.pop();
} else {
/* 当 item 优先级小于等于s1 栈顶运算符的时候 将s1栈顶的运算符淡出并且加入到s2 中，再次重复思路中的第四个环节，与s1中的新栈顶运算符比较
*问题 我们缺少一个比较优先级高低的方法
* */
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
// 之后将 itea 压入栈
s1.push(item);
}
}
// 将s1中剩余的运算符一次弹出加入s2
while (s1.size() != 0) {
s2.add(s1.pop());
}
// 注意应为存放的是list 这里我们顺序不需要改变 直接输出就是对应的后缀表达式
return s2;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将中缀表达式 转换成对应的list
* @date: 2021/12/27 17:32
* @param s
* @return: java.util.List<java.lang.String>
*/
public static List<String> toinfixExpression(String s) {
/*定义一个List 存放中缀表达式的对应内容*/
List<String> ls = new ArrayList<>();
//定义一个指针 用于遍历 中缀表达式的字符串
int i = 0;
// 用于拼接字符串
String str;
//用于存放遍历的字符
char c;
do {
// 如果c是一个非数字 那么我们需要加入到 ls 中去 ，这里的判断条件是 ASCLL值
if ((c = s.charAt(i)) < 48 || ((c = s.charAt(i)) > 57)) {
ls.add("" + c);
// 指针后移
i++;
} else {
/*
* 如果是一个数字 那么我们还需要考虑是不是多位数
* 这里我们将 str 置空
* */
str = "";
while (i < s.length() && (c = s.charAt(i)) >= 48 && ((c = s.charAt(i)) <= 57)) {
//拼接数字字符串
str += c;
i++;
}
ls.add(str);
}
} while (i < s.length());
return ls;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将一个逆波兰表达式的数据和运算符 依次放入Arraylist中
* @date: 2021/12/25 18:09
* @param suffixExpression
* @return: java.util.List<java.lang.String> 将分割好的字符List 返回
*/
public static List<String> getListString(String suffixExpression) {
// 分割字符串 将后缀表达式的每一个字符取出
String[] split = suffixExpression.split(" ");
// 我们用list 来存储分割出来的表达式，这样之后我们就需要遍历即可
List<String> list = new ArrayList<>();
for (String ele : split) {
list.add(ele);
}
return list;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 这个方法就是 逆波兰表达式的运算处理方法
* * 实现思路 : 我们以 （3+4）*4-6 对应的后缀表达式 => 3 4 + 5 * 6 -
* * 1） 从左至右扫描，将3和4压入栈
* * 2） 遇到+运算符号 因此弹出 4 和 3 （4为栈顶元素 3 为次顶元素） 计算出3+4的值，将计算的结果加入栈
* * 3） 将5 入栈
* * 4） 接下来将 * 是运算符 弹出 5和7 计算出 7*5 = 35 将结果入栈
* * 5） 将6 入栈
* @date: 2021/12/25 18:14
* @param ls
* @return: int 返回的是一个运算结果
*/
public static int calculate(List<String> ls) {
//创建栈 只需要一个栈即可
Stack<String> stack = new Stack<>();
// 遍历处理
for (String item : ls) {
// 这里我们用正则表达式来取出数字 和符号 如果是数字进行处理，如果符号做另外的处理
if (item.matches("\\d+")) {
//匹配的是数字
stack.push(item);
} else {
// 如果是符号就 pop出两个数 运算之后结果入栈
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if ("+".equals(item)) {
res = num1 + num2;
} else if ("-".equals(item)) {
res = num1 - num2;
} else if ("*".equals(item)) {
res = num1 * num2;
} else if ("/".equals(item)) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
// 把 res 入栈
stack.push("" + res);
}
}
//最后留在stack 中的数据是运算结果
return Integer.parseInt(stack.pop());
}
}
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
// 写一个方法 返回对应的数字
public static int getValue(String operation) {
int result = 0;
switch (operation) {
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("不存在该运算符");
break;
}
return result;
}
}
总结
- 计算的思路和我们先前写的逆波兰计算器事一样的
- 这里我们考虑中缀转后缀的几个要点，运算符优先级和运算符的位置
- 动手之后，debug看看栈和List的变化加深理解
排序算法
快速排序
==快速排序法介绍==：
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两 部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序思路图：
快速排序的思路由上图所示：
- 首先是找到一个基准点，这个不一定非要是中位数，也可以是任意一位，可以自主分割，在什么位置都可以，这里我们以中位来学习
- 根据中位数为基准，将需要排序的数组分为两份，之后分别交换位置，保证比中位数小的都在左边，比中位数的都在右边，此时左右两边虽然无序，但是都保证一定规则
- 之后按照递归，再次将左边选出中位数，右边选出中位数，递归到不能交换为止
快速排序案例
要求: 对 [-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 quickSort(int[] arr, int left, int right) {
// left index
int l = left;
int r = right;
// pivot 中轴值
int pivot = arr[(left + right) / 2];
//临时变量
int temp = 0;
// while 循环的目的是比比中轴的pivot值小的放在左边
// 比pivot 值大的放在右边
while (l < r) {
// 在pivot的左边一直寻找 找到大于等于pivot 的值才退出
while (arr[l] < pivot) {
l += 1;
}
// 在pivot的右边一直寻找 找到小于等于pivot 的值才退出
while (arr[r] > pivot) {
r -= 1;
}
// 如果 l>=r说明pivot的左右两个值已经按照左边全都是小于等于pivot，右边去哪不是大于等于pivot排列好了
if (l >= r) {
break;
}
// 交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 如果交换玩发现这个arr[l]==pivot值 相等r--前移
if (arr[l] == pivot) {
r -= 1;
}
//如果交换玩发现 arr[r] == pivot值 相等l++ 后移
if (arr[r] == pivot) {
l += 1;
}
}
// 如果l==r 必须是 l++ r-- 否则会出现栈溢出
if (l == r) {
l += 1;
r -= 1;
}
//向左递归
if (left < r) {
quickSort(arr, left, r);
}
//向右递归
if (right > l) {
quickSort(arr, l, right);
}
}
排序过程断点调试
int arr[] = {-9, 78, 0, 23, -567};
我们的测试数组是一个五位数的数组，
进入循环，此时我们看到，中位数和左右两边的索引，0和4
这里我们可以看第一组数据，
下标0 arr[l] =- 9, -9小于0于是 左边下标后移继续寻找，找到78，此时l = 1 是78对应的数组下标 此时的78 比中位 0 要大，进入右侧比对
显然 arr[r] = -567 比中位数小，不需要改变下标，跳出循环，
此时我们对比因为我们之后需要重复的递归，这里就是我们递归的跳出条件，如果左边大于右边了，代表左边已经没有大于中位数的数了，反之右边也一定没有小于中位数的
此时，交换两边不符合条件的数字，将比0大的七十八交换到右边吗，将比0小的-567交换到左边
交换完成之后，判断左右两边此时小标的数字是否与中位数相等，如果相等就后移，不需要重复比对
此时我们的第一次循环就结束了，可以看到，数组已经被交换到了，我们的思路第一步的样子，
比中位数0 小的都在左边，比中位数0大的都在右边，之后我们需要重复递归，一直到交换不了为止
此时 r 与l相等，就代表都到中位数了，左右两边都递归有序了，此时我们需要将l后一位，r前移一位，防止栈溢出，并且再继续向下，再最后一次递归之前会结束，
后面的递归就是重复的分组重复的交换，一直到左索引小于又索引，代表还可以继续分组排序，直到左边递归完毕
右索引大于左索引代表可以继续向右边递归，一直到右边递归完毕
快速排序测速
八十万长度存放0-80w的随机数
可以看到，效率是十分的快速
有兴趣的小伙伴可以自己试试写一个冒泡排序测试一下，再拿小冷的快速排序测试一下，算法的精妙之处一下就能感受到了
归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer） 策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修 补"在一起，即分而治之)。
基本思想:
分开 ： 将数组递归拆分成最小子序列，之后分组排序
合并相邻有序子序列
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将
[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]
动态图
思路实现
给你一个数组, val arr = Array(8, 4, 5, 7, 1, 3, 6, 2 ), 请使用归并排序完成排序。
package com.hyc.DataStructure.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergetSort {
public static void main(String[] args) {
int arr[] = {8, 4, 5, 7, 1, 3, 6, 2}; //
//测试快排的执行速度
// 创建要给80000个的随机的数组
//int[] arr = new int[8000000];
//for (int i = 0; i < 8000000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
//}
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
int temp[] = new int[arr.length]; //归并排序需要一个额外空间
mergeSort(arr, 0, arr.length - 1, temp);
Arrays.toString(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
//System.out.println("归并排序后=" + Arrays.toString(arr));
}
//分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2; //中间索引
//向左递归进行分解
mergeSort(arr, left, mid, temp);
//向右递归进行分解
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr, left, mid, right, temp);
}
}
//合并的方法
/**
*
* @param arr 排序的原始数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 做中转的数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 初始化i, 左边有序序列的初始索引
int j = mid + 1; //初始化j, 右边有序序列的初始索引
int t = 0; // 指向temp数组的当前索引
//(一)
//先把左右两边(有序)的数据按照规则填充到temp数组
//直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {//继续
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，填充到 temp数组
//然后 t++, i++
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else { //反之,将右边有序序列的当前元素，填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//把有剩余数据的一边的数据依次全部填充到temp
while (i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp数组的元素拷贝到arr
//注意，并不是每次都拷贝所有
t = 0;
int tempLeft = left; //
//第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
//最后一次 tempLeft = 0 right = 7
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
速度测试
长度为 8000000，每个内容为0-800000的随机数，
可以很稳定，两秒左右，同样是排序，思想不同带来的优化肉眼可见的，以上就是归并排序的内容啦
基数排序
经典空间换时间的思想流排序算法
基数排序(桶排序)介绍
- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾 名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
- 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
- 基数排序(Radix Sort)是桶排序的扩展
- 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个
位数分别比较。
基数排序基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
创建一个二维数组，arr[10][n] 10是作为的桶，n是每个桶要装的数，按照个位数取出放到桶里，之后再按照十位数，分桶，一般来说排序的次数和最大数的位数一致，但是空间占用会越来越大，金典的空间换时间的算法
第二轮
最后
动图演示
代码思路实验
要求：将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
package com.hyc.DataStructure.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class RadixSort {
public static void main(String[] args) {
int arr[] = {53, 3, 542, 748, 14, 214};
// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
// int[] arr = new int[8000000];
// for (int i = 0; i < 8000000; i++) {
// arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
// }
System.out.println("排序前");
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是=" + date1Str);
radixSort(arr);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间是=" + date2Str);
System.out.println("基数排序后 " + Arrays.toString(arr));
}
//基数排序方法
public static void radixSort(int[] arr) {
//根据前面的推导过程，我们可以得到最终的基数排序代码
//1. 得到数组中最大的数的位数
int max = arr[0]; //假设第一数就是最大数
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大数是几位数
int maxLength = (max + "").length();
//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
//说明
//1. 二维数组包含10个一维数组
//2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
//3. 名明确，基数排序是使用空间换时间的经典算法
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
//可以这里理解
//比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
int[] bucketElementCounts = new int[10];
//这里我们使用循环将代码处理
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
//(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
for (int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
//遍历每一桶，并将桶中是数据，放入到原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中，有数据，我们才放入到原数组
if (bucketElementCounts[k] != 0) {
//循环该桶即第k个桶(即第k个一维数组), 放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
//System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
}
/*
//第1轮(针对每个元素的个位进行排序处理)
for(int j = 0; j < arr.length; j++) {
//取出每个元素的个位的值
int digitOfElement = arr[j] / 1 % 10;
//放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
//遍历每一桶，并将桶中是数据，放入到原数组
for(int k = 0; k < bucketElementCounts.length; k++) {
//如果桶中，有数据，我们才放入到原数组
if(bucketElementCounts[k] != 0) {
//循环该桶即第k个桶(即第k个一维数组), 放入
for(int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));
//==========================================
//第2轮(针对每个元素的十位进行排序处理)
for (int j = 0; j < arr.length; j++) {
// 取出每个元素的十位的值
int digitOfElement = arr[j] / 10 % 10; //748 / 10 => 74 % 10 => 4
// 放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
index = 0;
// 遍历每一桶，并将桶中是数据，放入到原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
// 如果桶中，有数据，我们才放入到原数组
if (bucketElementCounts[k] != 0) {
// 循环该桶即第k个桶(即第k个一维数组), 放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第2轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));
//第3轮(针对每个元素的百位进行排序处理)
for (int j = 0; j < arr.length; j++) {
// 取出每个元素的百位的值
int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
// 放入到对应的桶中
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
index = 0;
// 遍历每一桶，并将桶中是数据，放入到原数组
for (int k = 0; k < bucketElementCounts.length; k++) {
// 如果桶中，有数据，我们才放入到原数组
if (bucketElementCounts[k] != 0) {
// 循环该桶即第k个桶(即第k个一维数组), 放入
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第3轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
bucketElementCounts[k] = 0;
}
System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr)); */
}
}
速度测试
八百万长度，内容为 0-8000000的随机数只需要一秒钟
我们简单计算一下用来多少内容
8000000 * 11 * 4 / 1024 / 1024 / 1024 =1G
从公式可以看出我们排序八百万 使用到了1g的内存，从各方面都可以看出，基数排序是经典的空间换时间的算法
基数排序的说明:
-
基数排序是对传统桶排序的扩展，速度很快.
-
基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
-
基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些 记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前， 则称这种排序算法是稳定的；否则称为不稳定的]
-
有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9
哈希表
哈希表的基本介绍
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通 过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组 叫做散列表。
技术前景：在还没有缓存产品的时候是如何解决的
图形化实现后的散列表
实现思路就是以数组来做为映射唯一标识，每一个数组内的索引对饮一条链表
举例 部门编号 就可以理解为 数组的值
部门编号：姓名（链表保存的值）
google 上机题
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的 id 时, 要求查找到该员工的 所有信息.
要求:
-
不使用数据库,,速度越快越好=>哈希表(散列)
-
添加时，保证按照 id 从低到高插入 [课后思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到 高，怎么解决?
-
使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息
思路分析并画出示意图
思路实现
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.hashtable
* @className: hashtebDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/1 3:01
* @version: 1.0
*/
public class hashtebDemo {
public static void main(String[] args) {
//创建哈希表
hashtable hashTab = new hashtable(7);
//写一个简单的菜单
String key = "";
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("add: 添加雇员");
System.out.println("list: 显示雇员");
System.out.println("find: 查找雇员");
System.out.println("exit: 退出系统");
key = scanner.next();
switch (key) {
case "add":
System.out.println("输入id");
int id = scanner.nextInt();
System.out.println("输入名字");
String name = scanner.next();
//创建 雇员
Emp emp = new Emp(id, name);
hashTab.add(emp);
break;
case "list":
hashTab.list();
break;
case "find":
System.out.println("请输入要查找的id");
id = scanner.nextInt();
hashTab.findEmpById(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}
//创建 hashtab 管理多条链表，就是用数组来映射， 哈希表的实现方式有两种
//1. 数组+ 链表
//2。 二叉树
class hashtable {
//用于映射链表的数组
private EmpLinkedList[] empLinkedListArrays;
// 用来 记录长度
private int size;
// 构造器 初始化
public hashtable(int size) {
this.size = size;
// 初始化 Emplinkedlistarrays
empLinkedListArrays = new EmpLinkedList[size];
// 此处 这个时候不要分开初始化每一个链表，我们一次性初始化好
for (int i = 0; i < size; i++) {
empLinkedListArrays[i] = new EmpLinkedList();
}
}
// 添加成员
public void add(Emp emp) {
// 根据员工id 得到员工应该添加再那个链表
int emplinkedlistNo = hashFun(emp.id);
// 将emp 添加对应的链表
empLinkedListArrays[emplinkedlistNo].add(emp);
}
//遍历所有的链表 遍历hashtab
public void list() {
for (int i = 0; i < size; i++) {
empLinkedListArrays[i].list(i);
}
}
//查找id
public void findEmpById(int id) {
// 使用散列函数，确定到那条链表
int empLinkedListNo = hashFun(id);
Emp empByid = empLinkedListArrays[empLinkedListNo].findEmpByid(id);
if (empByid == null) {
System.out.println("并没有找到雇员");
} else {
System.out.println("在" + (empLinkedListNo + 1) + "链表中找到雇员,id为=>" + empByid.id);
}
}
// 用取模法来根据id 来算出链表对应映射的id数组
public int hashFun(int id) {
return id % size;
}
}
class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
}
class EmpLinkedList {
//头指针，执行第一个EMP 因此我们这个链表 的head是直接指向第一个emp
private Emp head;
// 添加雇员到列表
// 1. 假定 当添加雇员的时候 id 自增长 即是id的分配总是从小到大，所以我们不需要处理id是否有序的判断，
// 直接添加到当前链表的最后即可
public void add(Emp emp) {
//如果头节点是空的那么就将头节点添加，因为是第一个雇员
if (head == null) {
head = emp;
return;
}
// 如果头节点不是空的那代表不是第一个，我们需要一个指针指向head节点
Emp curEmp = head;
// 之后循环链表到末尾添加
while (true) {
//如果进入这个if 那么代表链表到了最后
if (curEmp == null) {
break;
}
//每次循环将curEmp 后移一直到触发if 执行 break
curEmp = curEmp.next;
}
// 退出循环代表curEmp 已经是最后一个了，这里我们将next 指向参数的 emp即可
curEmp.next = emp;
}
// 遍历链表,参数是为了确定是属于那个链表
public void list(int no) {
if (head == null) {
// 进入这个判断说明链表为空
System.out.println("第" + (no + 1) + "链表为空");
return;
}
System.out.print("第" + (no + 1) + "当前链表信息为");
Emp curEmp = head;
while (true) {
System.out.printf("=>id%dname=%s\t", curEmp.id, curEmp.name);
if (curEmp.next == null) {
break;
}
curEmp = curEmp.next;
}
System.out.println();
}
//根据id 查找链表
public Emp findEmpByid(int id) {
if (head == null) {
System.out.println("该链表为空");
return null;
}
Emp curemp = head;
while (true) {
if (curemp.id == id) {
break;
}
if (curemp.next == null) {
System.out.println("此链表没有要查找的雇员");
break;
}
//后移
curemp = curemp.next;
}
return curemp;
}
}
效果演示
新增与遍历
查找
树的结构学习
二叉树简介
为什么需要树这种数据结构 ？
二叉树的概念
-
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
-
二叉树的子节点分为左节点和右节点
-
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
-
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数二
层的叶子节点在右边连续，我们称为完全二叉树
数组
数组存储方式的分析
优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
画出操作示意图：
链表
链式存储方式的分析
优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，
删除效率也很好)。
缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
操作示意图：
二叉树
树存储方式的分析
能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也
可以保证数据的插入，删除，修改的速度
案例: [7, 3, 10, 1, 5, 9, 12]
认识树结构
树的常用术语(结合示意图理解:
1) 节点
2) 根节点
3) 父节点
4) 子节点
5) 叶子节点 (没有子节点的节点) 6) 节点的权(节点值) 7) 路径(从 root 节点找到该节点的路线) 8) 层
6) 子树
7) 树的高度(最大层数)
8) 森林 :多颗子树构成森林
二叉树遍历的说明
- 前序遍历: 先输出父节点，再遍历左子树和右子树
- 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
- 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
- 小结: 看输出父节点的顺序，就确定是前序，中序还是后序
二叉树遍历应用实例(前序,中序,后序)
二叉树遍历代码实例
public static void main(String[] args){
// 测试，先创建一颗二叉树
BinaryTree binaryTree = new BinaryTree();
heroNode root = new heroNode(1, "宋江");
heroNode node1 = new heroNode(2, "吴用");
heroNode node2 = new heroNode(3, "卢俊义");
heroNode node3 = new heroNode(4, "林冲");
heroNode node4 = new heroNode(5, "关胜");
//设置头节点
binaryTree.setHead(root);
// 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
root.setLeftNode(node1);
root.setRightNode(node2);
node2.setRightNode(node3);
node2.setLeftNode(node4);
//测试
//// 前序遍历
//binaryTree.PreOrder();
////中序遍历
//System.out.println();
//binaryTree.InfixOrder();
////后序遍历
//System.out.println();
//binaryTree.PostOrder();
}
class BinaryTree {
//确定根节点
private heroNode head;
public void setHead(heroNode head) {
this.head = head;
}
// 前序遍历
public void PreOrder() {
if (this.head != null) {
this.head.PreOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//中序遍历
public void InfixOrder() {
if (this.head != null) {
this.head.infixOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//后续遍历
public void PostOrder() {
if (this.head != null) {
this.head.postOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
}
class heroNode {
private int id;
private String name;
private heroNode leftNode;
private heroNode rightNode;
public heroNode getLeftNode() {
return leftNode;
}
public void setLeftNode(heroNode leftNode) {
this.leftNode = leftNode;
}
public heroNode getRightNode() {
return rightNode;
}
public void setRightNode(heroNode rightNode) {
this.rightNode = rightNode;
}
public heroNode(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "heroNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
public void setName(String name) {
this.name = name;
}
// 前序遍历
public void PreOrder() {
System.out.println(this);
if (this.getLeftNode() != null) {
this.leftNode.PreOrder();
}
if (this.getRightNode() != null) {
this.rightNode.PreOrder();
}
}
// 中序遍历
public void infixOrder() {
if (this.leftNode != null) {
this.leftNode.infixOrder();
}
System.out.println(this);
if (this.rightNode != null) {
this.rightNode.infixOrder();
}
}
// 后序遍历
public void postOrder() {
if (this.leftNode != null) {
this.leftNode.postOrder();
}
if (this.rightNode != null) {
this.rightNode.postOrder();
}
System.out.println(this);
}
}
二叉树查找思路
- 请编写前序查找，中序查找和后序查找的方法。
- 并分别使用三种查找方式，查找 heroNO = 5 的节点
- 并分析各种查找方式，分别比较了多少次
思路图解
二叉树查找代码示例
为了方便更好的阅读代码，就把节点和树类的查找代码专门的写出来，后面会有全代码的部分
class BinatyTree{
//前序查找
public heroNode preOrderSearch(int no) {
if (this.head != null) {
return this.head.PreOrderSearch(no);
} else {
return null;
}
}
//中序查找
public heroNode infixOrderSearch(int no) {
if (this.head != null) {
return this.head.infixOrderSearch(no);
} else {
return null;
}
}
//后序查找
public heroNode postOrderSearch(int no) {
if (this.head != null) {
return this.head.postOrderSearch(no);
} else {
return null;
}
}
}
class heroNode{
//前序查找
public heroNode preOrderSearch(int no) {
if (this.head != null) {
return this.head.PreOrderSearch(no);
} else {
return null;
}
}
//中序查找
public heroNode infixOrderSearch(int no) {
if (this.head != null) {
return this.head.infixOrderSearch(no);
} else {
return null;
}
}
//后序查找
public heroNode postOrderSearch(int no) {
if (this.head != null) {
return this.head.postOrderSearch(no);
} else {
return null;
}
}
}
二叉树-删除节点
- 如果删除的节点是叶子节点，则删除该节点
- 如果删除的节点是非叶子节点，则删除该子树.
- 测试，删除掉 5 号叶子节点 和 3 号子树.
思路分析
有关二叉树的，遍历，查找，删除的全代码
package com.hyc.DataStructure.tree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.tree
* @className: BinaryTreeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/3 16:47
* @version: 1.0
*/
public class BinaryTreeDemo {
public static void main(String[] args) {
// 测试，先创建一颗二叉树
BinaryTree binaryTree = new BinaryTree();
heroNode root = new heroNode(1, "宋江");
heroNode node1 = new heroNode(2, "吴用");
heroNode node2 = new heroNode(3, "卢俊义");
heroNode node3 = new heroNode(4, "林冲");
heroNode node4 = new heroNode(5, "关胜");
//设置头节点
binaryTree.setHead(root);
// 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
root.setLeftNode(node1);
root.setRightNode(node2);
node2.setRightNode(node3);
node2.setLeftNode(node4);
//测试
//// 前序遍历
//binaryTree.PreOrder();
////中序遍历
//System.out.println();
//binaryTree.InfixOrder();
////后序遍历
//System.out.println();
//binaryTree.PostOrder();
//System.out.println("前中后查找");
//System.out.println("开始前序查找");
//heroNode resNode = binaryTree.preOrderSearch(5);
//if (resNode != null) {
// System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
//} else {
// System.out.println("查找失败");
//}
//System.out.println("开始中序查找");
//heroNode resNode = binaryTree.infixOrderSearch(5);
//if (resNode != null) {
// System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
//} else {
// System.out.println("查找失败");
//}
//System.out.println("开始后序查找");
//heroNode resNode = binaryTree.postOrderSearch(5);
//if (resNode != null) {
// System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
//} else {
// System.out.println("查找失败");
//}
// 删除测试
System.out.println("删除前");
binaryTree.PreOrder();
System.out.println("删除后");
binaryTree.deleteNode(5);
binaryTree.PreOrder();
}
}
class BinaryTree {
//确定根节点
private heroNode head;
public void setHead(heroNode head) {
this.head = head;
}
// 前序遍历
public void PreOrder() {
if (this.head != null) {
this.head.PreOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//中序遍历
public void InfixOrder() {
if (this.head != null) {
this.head.infixOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//后续遍历
public void PostOrder() {
if (this.head != null) {
this.head.postOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//前序查找
public heroNode preOrderSearch(int no) {
if (this.head != null) {
return this.head.PreOrderSearch(no);
} else {
return null;
}
}
//中序查找
public heroNode infixOrderSearch(int no) {
if (this.head != null) {
return this.head.infixOrderSearch(no);
} else {
return null;
}
}
//后序查找
public heroNode postOrderSearch(int no) {
if (this.head != null) {
return this.head.postOrderSearch(no);
} else {
return null;
}
}
// 删除节点
public void deleteNode(int no) {
if (head != null) {
if (head.getId() == no) {
head = null;
return;
} else {
head.deleteNode(no);
}
} else {
System.out.println("空树,无法删除");
}
}
}
class heroNode {
private int id;
private String name;
private heroNode leftNode;
private heroNode rightNode;
public heroNode getLeftNode() {
return leftNode;
}
public void setLeftNode(heroNode leftNode) {
this.leftNode = leftNode;
}
public heroNode getRightNode() {
return rightNode;
}
public void setRightNode(heroNode rightNode) {
this.rightNode = rightNode;
}
public heroNode(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "heroNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
public void setName(String name) {
this.name = name;
}
// 前序遍历
public void PreOrder() {
System.out.println(this);
if (this.getLeftNode() != null) {
this.leftNode.PreOrder();
}
if (this.getRightNode() != null) {
this.rightNode.PreOrder();
}
}
// 中序遍历
public void infixOrder() {
if (this.leftNode != null) {
this.leftNode.infixOrder();
}
System.out.println(this);
if (this.rightNode != null) {
this.rightNode.infixOrder();
}
}
// 后序遍历
public void postOrder() {
if (this.leftNode != null) {
this.leftNode.postOrder();
}
if (this.rightNode != null) {
this.rightNode.postOrder();
}
System.out.println(this);
}
// 前序查找
public heroNode PreOrderSearch(int no) {
System.out.println("前序查找");
//比较当前节点的no 是不是我们要搜索的
if (this.id == no) {
return this;
}
//要返回的节点
heroNode resNode = null;
// 判断左边节点是不是空 如果不是空的话 那么就递归前序查找
// 如果找到的话 就返回找到的节点
if (this.leftNode != null) {
resNode = this.leftNode.PreOrderSearch(no);
}
//如果不为null 那么代表左边找到了直接返回即可
if (resNode != null) {
return resNode;
}
// 判断右边节点是不是空 如果不是空的话 那么就递归前序查找
// 如果找到的话 就返回找到的节点
if (this.rightNode != null) {
resNode = this.rightNode.PreOrderSearch(no);
}
return resNode;
}
// 中序查找
public heroNode infixOrderSearch(int no) {
//要返回的节点
heroNode resNode = null;
// 判断左边节点是不是空 如果不是空的话 那么就递归中序查找
// 如果找到的话 就返回找到的节点
if (this.leftNode != null) {
resNode = this.leftNode.infixOrderSearch(no);
}
//如果不为null 那么代表左边找到了直接返回即可
if (resNode != null) {
return resNode;
}
//比较当前节点的no 是不是我们要搜索的
System.out.println("中序查找");
if (this.id == no) {
return this;
}
// 判断右边节点是不是空 如果不是空的话 那么就递归中序查找
// 如果找到的话 就返回找到的节点
if (this.rightNode != null) {
resNode = this.rightNode.infixOrderSearch(no);
}
return resNode;
}
// 后序查找
public heroNode postOrderSearch(int no) {
//要返回的节点
heroNode resNode = null;
// 判断左边节点是不是空 如果不是空的话 那么就递归后序查找
// 如果找到的话 就返回找到的节点
if (this.leftNode != null) {
resNode = this.leftNode.postOrderSearch(no);
}
//如果不为null 那么代表左边找到了直接返回即可
if (resNode != null) {
return resNode;
}
// 判断右边节点是不是空 如果不是空的话 那么就递归后序查找
// 如果找到的话 就返回找到的节点
if (this.rightNode != null) {
resNode = this.rightNode.postOrderSearch(no);
}
//如果不为null 那么代表右边找到了直接返回即可
if (resNode != null) {
return resNode;
}
System.out.println("后序查找");
//左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
if (this.id == no) {
return this;
}
return resNode;
}
// 删除
public void deleteNode(int no) {
// 向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
if (this.leftNode != null && this.leftNode.id == no) {
this.leftNode = null;
return;
}
// 向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
if (this.rightNode != null && this.rightNode.id == no) {
this.rightNode = null;
return;
}
// 如果上面两步都不成功那么我们先向左边递归删除
if (this.leftNode != null) {
this.leftNode.deleteNode(no);
}
// 如果递归删除左子树也没有成功删除，那么就递归删除右边子树
if (this.rightNode != null) {
this.rightNode.deleteNode(no);
}
}
}
顺序存储二叉树
顺序存储二叉树的概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，
上图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 2) 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
顺序存储二叉树的特点:
- 顺序二叉树通常只考虑完全二叉树
- 第 n 个元素的左子节点为 2 * n + 1（计算公式）
- 第 n 个元素的右子节点为 2 * n + 2 （计算公式）
- 第 n 个元素的父节点为 (n-1) / 2
- n : 表示二叉树中的第几个元素
顺序存储二叉树遍历
需求
给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。
前序遍历的结果应当为 1,2,4,5,3,6,7
编码思路
这里判断的思路首先是有一个数组转变成树看待的思想，
数组 ： 1,2,3,4,5,6,7
树 （如下图）
- 第 n 个元素的左子节点为 2 * n + 1（计算公式）
- 第 n 个元素的右子节点为 2 * n + 2 （计算公式）
我们可以用这个公式来证明一下，数组转树的正确性
比如我们要计算二的位置，2是1的左子节点，1是下标为0的元素 2*0+1 套用公式 = 1，之后的节点同理
代码实现
package com.hyc.DataStructure.tree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.tree
* @className: ArrayTreeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/4 19:07
* @version: 1.0
*/
public class ArrayTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrayTree arrayTree = new ArrayTree(arr);
//452 6731
arrayTree.postOrder(0);
}
}
class ArrayTree {
private int[] arr;
public ArrayTree(int[] arr) {
this.arr = arr;
}
// 顺序存储树的前序遍历
// 遍历公式 找到n的第n个左结点 n*2+1 找到n的第n个右节点 n*2+2
// 输入参数 int index 为开始遍历到根节点 即为 数组下标0
public void preOrder(int index) {
//非空判断 避免空指针
if (arr == null || arr.length == 0) {
System.out.println("该树 为空 不能遍历");
}
// 前序遍历先输出自己
System.out.println(arr[index]);
// 之后递归遍历左结点
//判断index 是否越界
if ((2 * index + 1) < arr.length) {
preOrder(index * 2 + 1);
}
// 之后递归遍历右边结点
//判断index 是否越界
if ((2 * index + 2) < arr.length) {
preOrder(index * 2 + 2);
}
}
public void infixOrder(int index) {
//非空判断 避免空指针
if (arr == null || arr.length == 0) {
System.out.println("该树 为空 不能遍历");
}
// 递归遍历左结点
//判断index 是否越界
if ((2 * index + 1) < arr.length) {
infixOrder(index * 2 + 1);
}
// 中序遍历输出自己
System.out.println(arr[index]);
// 递归遍历右边结点
//判断index 是否越界
if ((2 * index + 2) < arr.length) {
infixOrder(index * 2 + 2);
}
}
public void postOrder(int index) {
//非空判断 避免空指针
if (arr == null || arr.length == 0) {
System.out.println("该树 为空 不能遍历");
}
// 递归遍历左结点
//判断index 是否越界
if ((2 * index + 1) < arr.length) {
postOrder(index * 2 + 1);
}
// 递归遍历右边结点
//判断index 是否越界
if ((2 * index + 2) < arr.length) {
postOrder(index * 2 + 2);
}
// 后序遍历输出自己
System.out.println(arr[index]);
}
}
这里我们先了解顺序存储二叉树，并且掌握他的节点计算思路和遍历思路，小冷之后的文章堆排序的时候会进行知识点的使用，提前预热
线索化二叉树
通过一个问题来引入线索化二叉树
将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7
问题分析:
- 当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
- 但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.
- 如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?
- 解决方案-线索二叉树
线索二叉树基本介绍
- n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向 该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质 的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个结点的前一个结点，称为前驱结点
- 一个结点的后一个结点，称为后继结点
线索二叉树应用案例
将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
说明: 当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:
-
left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的
就是前驱节点.
-
right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩ 节点的 right 指向 的是后继节点.
代码实现
package com.hyc.DataStructure.tree.ThreadedBinaryTree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.tree.ThreadedBinaryTree
* @className: ThreadedBinaryTreeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/5 16:38
* @version: 1.0
*/
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
//测试一把中序线索二叉树的功能
heroNode root = new heroNode(1, "tom");
heroNode node2 = new heroNode(3, "jack");
heroNode node3 = new heroNode(6, "smith");
heroNode node4 = new heroNode(8, "mary");
heroNode node5 = new heroNode(10, "king");
heroNode node6 = new heroNode(14, "dim");
//二叉树，后面我们要递归创建, 现在简单处理使用手动创建
root.setLeftNode(node2);
root.setRightNode(node3);
node2.setLeftNode(node4);
node2.setRightNode(node5);
node3.setLeftNode(node6);
//测试中序线索化
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setHead(root);
threadedBinaryTree.postThreadedNodes(root);
//测试: 以10号节点测试
heroNode leftNode = node5.getLeftNode();
heroNode rightNode = node5.getRightNode();
System.out.println("10号结点的前驱结点是 =" + leftNode); //3
System.out.println("10号结点的后继结点是=" + rightNode); //1
//当线索化二叉树后，能在使用原来的遍历方法
//threadedBinaryTree.infixOrder();
System.out.println("使用线索化的方式遍历 线索化二叉树");
threadedBinaryTree.preThreaddeList(); // 8, 3, 10, 1, 14, 6
}
}
class ThreadedBinaryTree {
//确定根节点
private heroNode head;
//递归的时候用来存放上一个节点的变量用于线索化树的遍历和线索化节点
private heroNode pre;
public void setHead(heroNode head) {
this.head = head;
}
//线索化遍历
public void ThreaddeList() {
// 这里我们需要一个变量，存储当前的节点
heroNode tempNode = head;
while (tempNode != null) {
/* 开始循环遍历
* 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
* 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
* 之后只需要处理线索化之后的有效节点即可
* */
while (tempNode.getLefttype() == 0) {
tempNode = tempNode.getLeftNode();
}
// 因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
System.out.println(tempNode);
/* 如果当前节点的右指针指向的是后继节点那么就一直输出
* */
while (tempNode.getRighttype() == 1) {
tempNode = tempNode.getRightNode();
System.out.println(tempNode);
}
// 替换这个遍历的节点
tempNode = tempNode.getRightNode();
}
}
public void preThreaddeList() {
// 这里我们需要一个变量，存储当前的节点
heroNode tempNode = head;
while (tempNode != null) {
/* 开始循环遍历
* 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
* 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
* 之后只需要处理线索化之后的有效节点即可
* */
while (tempNode.getLefttype() == 0) {
System.out.println(tempNode);
tempNode = tempNode.getLeftNode();
}
// 因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
System.out.println(tempNode);
// 替换这个遍历的节点
tempNode = tempNode.getRightNode();
}
}
//线索化节点
public void ThreadedNodes(heroNode node) {
// 非空判断
if (node == null) {
return;
}
// 线索化左子树
ThreadedNodes(node.getLeftNode());
// 线索化节点
//不太好理解这里以 8 举例子
// 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
if (node.getLeftNode() == null) {
//如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
//以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
node.setLeftNode(pre);
// 指向之后 将type改变为1
node.setLefttype(1);
}
//处理后继节点
//这里判断的前置节点非空并且前置节点没有后继结点
if (pre != null && pre.getRightNode() == null) {
//这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre = 8这里指向的意思是 8 的rightnode为3
pre.setRightNode(node);
//此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
pre.setRighttype(1);
}
//每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
//否则会造成死递归
pre = node;
// 线索化右子树
ThreadedNodes(node.getRightNode());
}
//线索化节点
public void preThreadedNodes(heroNode node) {
// 非空判断
if (node == null) {
return;
}
// 线索化节点
//不太好理解这里以 8 举例子
// 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
if (node.getLeftNode() == null) {
//如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
//以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
node.setLeftNode(pre);
// 指向之后 将type改变为1
node.setLefttype(1);
}
//处理后继节点
//这里判断的前置节点非空并且前置节点没有后继结点
if (pre != null && pre.getRightNode() == null) {
//这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre = 8这里指向的意思是 8 的rightnode为3
pre.setRightNode(node);
//此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
pre.setRighttype(1);
}
//每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
//否则会造成死递归
pre = node;
if (node.getLefttype() == 0) {
// 线索化左子树
preThreadedNodes(node.getLeftNode());
}
if (node.getRighttype() == 0) {
// 线索化右子树
preThreadedNodes(node.getRightNode());
}
}
//线索化节点
public void postThreadedNodes(heroNode node) {
// 非空判断
if (node == null) {
return;
}
// 线索化左子树
ThreadedNodes(node.getLeftNode());
// 线索化右子树
ThreadedNodes(node.getRightNode());
// 线索化节点
//不太好理解这里以 8 举例子
// 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
if (node.getLeftNode() == null) {
//如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
//以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
node.setLeftNode(pre);
// 指向之后 将type改变为1
node.setLefttype(1);
}
//处理后继节点
//这里判断的前置节点非空并且前置节点没有后继结点
if (pre != null && pre.getRightNode() == null) {
//这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre = 8这里指向的意思是 8 的rightnode为3
pre.setRightNode(node);
//此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
pre.setRighttype(1);
}
//每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
//否则会造成死递归
pre = node;
}
// 前序遍历
public void preOrder() {
if (this.head != null) {
this.head.PreOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//中序遍历
public void InfixOrder() {
if (this.head != null) {
this.head.infixOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//后续遍历
public void PostOrder() {
if (this.head != null) {
this.head.postOrder();
} else {
System.out.println("二叉树没有根节点，无法遍历");
}
}
//前序查找
public heroNode preOrderSearch(int no) {
if (this.head != null) {
return this.head.PreOrderSearch(no);
} else {
return null;
}
}
//中序查找
public heroNode infixOrderSearch(int no) {
if (this.head != null) {
return this.head.infixOrderSearch(no);
} else {
return null;
}
}
//后序查找
public heroNode postOrderSearch(int no) {
if (this.head != null) {
return this.head.postOrderSearch(no);
} else {
return null;
}
}
// 删除节点
public void deleteNode(int no) {
if (head != null) {
if (head.getId() == no) {
head = null;
return;
} else {
head.deleteNode(no);
}
} else {
System.out.println("空树,无法删除");
}
}
}
class heroNode {
private int id;
private String name;
private heroNode leftNode;
private heroNode rightNode;
//如果type 为 0 那么代表还有子树，如果type为1代表是前驱节点/后置节点
private int lefttype;
private int righttype;
public int getLefttype() {
return lefttype;
}
public void setLefttype(int lefttype) {
this.lefttype = lefttype;
}
public int getRighttype() {
return righttype;
}
public void setRighttype(int righttype) {
this.righttype = righttype;
}
public heroNode getLeftNode() {
return leftNode;
}
public void setLeftNode(heroNode leftNode) {
this.leftNode = leftNode;
}
public heroNode getRightNode() {
return rightNode;
}
public void setRightNode(heroNode rightNode) {
this.rightNode = rightNode;
}
public heroNode(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
@Override
public String toString() {
return "heroNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
public void setName(String name) {
this.name = name;
}
// 前序遍历
public void PreOrder() {
System.out.println(this);
if (this.getLeftNode() != null) {
this.leftNode.PreOrder();
}
if (this.getRightNode() != null) {
this.rightNode.PreOrder();
}
}
// 中序遍历
public void infixOrder() {
if (this.leftNode != null) {
this.leftNode.infixOrder();
}
System.out.println(this);
if (this.rightNode != null) {
this.rightNode.infixOrder();
}
}
// 后序遍历
public void postOrder() {
if (this.leftNode != null) {
this.leftNode.postOrder();
}
if (this.rightNode != null) {
this.rightNode.postOrder();
}
System.out.println(this);
}
// 前序查找
public heroNode PreOrderSearch(int no) {
System.out.println("前序查找");
//比较当前节点的no 是不是我们要搜索的
if (this.id == no) {
return this;
}
//要返回的节点
heroNode resNode = null;
// 判断左边节点是不是空 如果不是空的话 那么就递归前序查找
// 如果找到的话 就返回找到的节点
if (this.leftNode != null) {
resNode = this.leftNode.PreOrderSearch(no);
}
//如果不为null 那么代表左边找到了直接返回即可
if (resNode != null) {
return resNode;
}
// 判断右边节点是不是空 如果不是空的话 那么就递归前序查找
// 如果找到的话 就返回找到的节点
if (this.rightNode != null) {
resNode = this.rightNode.PreOrderSearch(no);
}
return resNode;
}
// 中序查找
public heroNode infixOrderSearch(int no) {
//要返回的节点
heroNode resNode = null;
// 判断左边节点是不是空 如果不是空的话 那么就递归中序查找
// 如果找到的话 就返回找到的节点
if (this.leftNode != null) {
resNode = this.leftNode.infixOrderSearch(no);
}
//如果不为null 那么代表左边找到了直接返回即可
if (resNode != null) {
return resNode;
}
//比较当前节点的no 是不是我们要搜索的
System.out.println("中序查找");
if (this.id == no) {
return this;
}
// 判断右边节点是不是空 如果不是空的话 那么就递归中序查找
// 如果找到的话 就返回找到的节点
if (this.rightNode != null) {
resNode = this.rightNode.infixOrderSearch(no);
}
return resNode;
}
// 后序查找
public heroNode postOrderSearch(int no) {
//要返回的节点
heroNode resNode = null;
// 判断左边节点是不是空 如果不是空的话 那么就递归后序查找
// 如果找到的话 就返回找到的节点
if (this.leftNode != null) {
resNode = this.leftNode.postOrderSearch(no);
}
//如果不为null 那么代表左边找到了直接返回即可
if (resNode != null) {
return resNode;
}
// 判断右边节点是不是空 如果不是空的话 那么就递归后序查找
// 如果找到的话 就返回找到的节点
if (this.rightNode != null) {
resNode = this.rightNode.postOrderSearch(no);
}
//如果不为null 那么代表右边找到了直接返回即可
if (resNode != null) {
return resNode;
}
System.out.println("后序查找");
//左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
if (this.id == no) {
return this;
}
return resNode;
}
// 删除
public void deleteNode(int no) {
// 向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
if (this.leftNode != null && this.leftNode.id == no) {
this.leftNode = null;
return;
}
// 向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
if (this.rightNode != null && this.rightNode.id == no) {
this.rightNode = null;
return;
}
// 如果上面两步都不成功那么我们先向左边递归删除
if (this.leftNode != null) {
this.leftNode.deleteNode(no);
}
// 如果递归删除左子树也没有成功删除，那么就递归删除右边子树
if (this.rightNode != null) {
this.rightNode.deleteNode(no);
}
}
}
遍历线索化二叉树
-
说明：对前面的中序线索化的二叉树， 进行遍历
-
分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历
线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
public void preThreaddeList() {
// 这里我们需要一个变量，存储当前的节点
heroNode tempNode = head;
while (tempNode != null) {
/* 开始循环遍历
* 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
* 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
* 之后只需要处理线索化之后的有效节点即可
* */
while (tempNode.getLefttype() == 0) {
System.out.println(tempNode);
tempNode = tempNode.getLeftNode();
}
// 因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
System.out.println(tempNode);
// 替换这个遍历的节点
tempNode = tempNode.getRightNode();
}
}
红黑树
是一种特殊的平衡二叉树
满足如下几个条件：
1、结点是红色或黑色的
2、根结点始终是黑色的
3、叶子结点也都是黑色的 （当红色结点无左右孩子时，补足空结点是黑色的）
4、红色结点的子结点都是黑色的
5、对任一结点，到叶子结点的所有路径，都包含相同数目的黑色结点
特征： 从根结点到叶子结点的最长路径，不会超过最短路径的两倍
当插入新结点使红黑树失去平衡时，通过两种方式恢复平衡：
旋转和变色 （红变黑 黑变红）
可视化网站
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
插入结点到红黑树的逻辑
约定 新插入的结点都设为红色的，可以简化树的平衡过程
假设要插入的结点是X 父结点是P 祖父结点是G 叔父结点是U
1）X是根结点
放入根结点中，将颜色变为黑色
2）X的父结点是黑色的
3）X的父结点是红色的
a) 如果叔父结点U也是红色的，可以推断出祖父结点G必是黑色的
当增加新结点时 造成两个红色结点相邻 此时使用变色处理
P和U由从红色变为黑色 G由黑色变为红色 如果G是根结点 再次恢复为黑色
b) 如果叔父结点U是黑色的，并且X在左侧
以P为中心，向右旋转，G和U下移，此时如果P有右孩子，右孩子R移动到G的左孩子处
将P变为黑色 将G变为红色
此为举例 插入16的场景
c) 如果叔父结点U是黑色的，并且X在右侧
先通过左旋 恢复成第二种情况 然后再右旋和变色
以插入19举例
线段树
认识线段树
序列 【1,4,2,3】
- 给序列的第i个数,加上X A[i]=A[I]+X O(1)
- 取序列的最大的数,遍历最大值 O(N)
- 遍历的时候 时间复杂度高,怎么处理呢?
线段树Segment Tree
"区间" 线段树是根据区间的性质来构造的
特点:
每次将区间的长度一分为二,区间存储的左右边界 [[start,end]/[left,right]]
如果假设数组的长度 = n 线段树的高度就是 log(n)
将区间中的最大值加入进来,线段树加入值之后就是如下状态
除此之外,可以存储的区间内的最小值,区间求和等等
线段树的节点个数为 n+n/2+n/4... = (1+1/2+1/4...)*n ≈ 2n
构造线段树的时间复杂度和空间复杂度均为 O(n)
线段树创建代码实现
package com.hyc.DataStructure.SegmentTree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.SegmentTree
* @className: SegmentTree
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/26 10:15
* @version: 1.0
*/
public class SegmentTree {
@Override
public String toString() {
return "SegmentTree{" +
"start=" + start +
", end=" + end +
", val=" + val +
", left=" + left +
", right=" + right +
'}';
}
public static void main(String[] args) {
int[] arr = {1, 4, 2, 3};
SegmentTree root = SegmentTree.build(arr);
System.out.println(root);
}
//节点区间范围
public int start, end;
// 存储节点值
public int val;
// 左右子树
public SegmentTree left;
public SegmentTree right;
public SegmentTree(int start, int end, int val) {
this.start = start;
this.end = end;
this.val = val;
}
public static SegmentTree build(int[] A) {
return buildByRecu(0, A.length - 1, A);
}
public static SegmentTree buildByRecu(int start, int end, int[] A) {
if (start > end) {
return null;
}
SegmentTree root = new SegmentTree(start, end, A[start]);
// 如果是叶子节点 直接返回
if (start == end) {
return root;
}
// 如果不是那么就以二分的形式来递归创建树
int mid = (start + end) / 2;
root.left = buildByRecu(start, mid, A);
root.right = buildByRecu(mid + 1, end, A);
//求出区间内最大值为父节点的val
root.val = Math.max(root.left.val, root.right.val);
return root;
}
}
单点更新
public static void modify(SegmentTree root, int index, int value) {
// 先找到叶子节点,然后逐渐上层
if (root.start == root.end && root.start == index) {
root.val = value;
return;
}
int mid = (root.start + root.end) / 2;
// 判断index 在左子树的区间,还是 右子树的区间,二分思路
if (index <= mid) {
modify(root.left, index, value);
root.val = Math.max(root.left.val, root.right.val);
return;
}
modify(root.right, index, value);
root.val = Math.max(root.left.val, root.right.val);
}
搜索线段树
搜索线段树返回索引值
public static int searchByIndex(SegmentTree root, int index) {
// 先找到叶子节点,然后逐渐上层
if (root.start == root.end && root.start == index) {
return root.val;
}
int mid = (root.start + root.end) / 2;
// 判断index 在左子树的区间,还是 右子树的区间,二分思路
if (index <= mid) {
searchByIndex(root.left, index);
return root.val;
}
searchByIndex(root.right, index);
return root.val;
}
树结构实际应用
堆排序
堆排序基本介绍
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复 杂度均为 O(nlogn)，它也是不稳定排序。
- 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有 要求结点的左孩子的值和右孩子的值的大小关系。
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
大顶堆
小顶堆
堆排序基本思想
- 将待排序序列构造成一个大顶堆
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
堆排序步骤图解说明
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。 原始的数组 [4, 6, 8, 5, 9]
-
假设给定无序序列结构如下
-
此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点
arr.length/2-1=5/2-1=1，也就是下面的 6 结点），从左至右，从下至上进行调整。
-
找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大，4 和 9 交换。
-
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6。
此时，我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换.
得到第二大元素。如此反复进行交换、重建、交换。
-
.将堆顶元素 9 和末尾元素 4 进行交换
-
重新调整结构，使其继续满足堆定义
-
再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8
-
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
总结下堆排序的基本思路：
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
- 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
- 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤， 直到整个序列有序.
代码实现
要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。
- 堆排序不是很好理解，老师通过 Debug 帮助大家理解堆排序
- 堆排序的速度非常快，在我的机器上 8 百万数据 3 秒左右。O(nlogn)
package com.hyc.DataStructure.tree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.tree
* @className: HeapSort
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/6 23:52
* @version: 1.0
*/
public class HeapSort {
public static void main(String[] args) {
int[] test = new int[8000000];
//测试数据
for (int i = 0; i < 8000000; i++) {
test[i] = (int) (Math.random() * 800000);
}
long time = System.currentTimeMillis();
heapsort(test);
long end = System.currentTimeMillis();
long t = ((end - time) / 1000);
System.out.println("一共用时 " + t + "秒");
int arr[] = {4, 6, 8, 5, 9};
}
public static void heapsort(int[] arr) {
int temp = 0;
//按照 大顶堆的方式调整堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
/*将最大元素和末尾元素交换，将最大元素放入数组末尾
*重新调整结构，满足堆的定义
* */
for (int j = arr.length - 1; j > 0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
//System.out.println("排序后的数组是 = " + Arrays.toString(arr));
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 大顶堆交换思路， 判断左右节点大小，之后判断左右节点的比对结果，与父节点判断，将最大值交还给父节点
* @date: 2022/2/6 23:54
* @param arr 存放需要将交换节点的数组
* @param i 需要做调整的父节点索引
* @param length 有多少节点需要调整
* @return: void
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
// 开始调整
/* 说明
* k =i*2+1按照之前线索查找树的公式，找出左子树的节点位置
* */
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
//判断条件 k（节点索引）首先不能大于我们要遍历的结点索引总数，之后判断左右节点的大小，交换
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
//找出最大的子节点，与父节点的值比对，
if (arr[k] > temp) {
//将较大的值放入到父节点
arr[i] = arr[k];
i = k; //i指向k ， 继续循环比较
} else {
break;
}
}
// for 循环结束之后 我们i已经是父节点以及最大值的索引了
// 将 temp 调整到最后免得位置
arr[i] = temp;
}
}
赫夫曼树
基本介绍
- 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为 最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
- 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近
赫夫曼树几个重要概念和举例说明
-
路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路 中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1
-
结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结 点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积
-
树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL(weighted path
length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
-
WPL 最小的就是赫夫曼树
赫夫曼树创建思路图解
给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.
构成赫夫曼树的步骤：
-
从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
-
取出根节点权值最小的两颗二叉树
-
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
-
再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数
据都被处理，就得到一颗赫夫曼树
赫夫曼树的代码实现
package com.hyc.DataStructure.HuffmanTree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.HuffmanTreeDemo
* @className: HuffmanTreeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/8 0:21
* @version: 1.0
*/
public class HuffmanTreeDemo {
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node manTree = createHuffManTree(arr);
// 测试
preOrder(manTree);
}
//编写一个前序遍历的方法
public static void preOrder(Node root) {
if (root != null) {
root.PreOrder();
} else {
System.out.println("空树无法遍历");
}
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* @date: 2022/2/8 0:42
* @param arr 需要创建赫夫曼树的数组
* @return: com.hyc.DataStructure.HuffmanTree.Node 返回已经创建好的赫夫曼树的根节点
*/
public static Node createHuffManTree(int[] arr) {
List<Node> nodes = new ArrayList<>();
//（1）为了方便操作 我们先遍历数组生成对应节点 放入 arrayList
for (int value : arr) {
nodes.add(new Node(value));
}
//循环处理
while (nodes.size() > 1) {
// 先用接口的sort 排序
Collections.sort(nodes);
System.out.println("nodes = " + nodes);
// （2） 取出根节点权值最小的两颗二叉树
// 取出权值最小的结点
Node leftnode = nodes.get(0);
//取出根节点第二最小的二叉树
Node rightnode = nodes.get(1);
// （3） 构建出一颗新的二叉树
Node parent = new Node(leftnode.value + rightnode.value);
parent.left = leftnode;
parent.right = rightnode;
// (4)从 ArrayList删除处理过的二叉树
nodes.remove(leftnode);
nodes.remove(rightnode);
// (5)将parent加入到 nodes
nodes.add(parent);
}
// 返回赫夫曼树的root节点
return nodes.get(0);
}
}
/* 为了Node对象排序，我们实现collections集合排序
* 这里我们实现 compareble
* */
class Node implements Comparable<Node> {
//赫夫曼树 权重值
int value;
Node left;
Node right;
// 构造方法 创建节点的时候只需要有权重值就可以了
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
//这里我们按照权重从小到大排序
//从大到小只需要置负 -(this.value - o.value)
return this.value - o.value;
}
// 前序遍历
public void PreOrder() {
System.out.println(this);
if (this.left != null) {
this.left.PreOrder();
}
if (this.right != null) {
this.right.PreOrder();
}
}
}
赫夫曼编码
基本介绍
- 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
- 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
- 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间
- 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码
原理剖析
定长编码
变长编码
赫夫曼编码
传输的 字符串 ,按照字符的出险次数出现权重
- i like like like java do you like a java
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
- 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
步骤：
- 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理， 就得到一颗赫夫曼树
根据赫夫曼树，给各个字符,规定编码 (前缀编码)， 向左的路径为 0 向右的路径为 1 ， 编码
如下:
按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)
10101001101111011110100110111101111010011011110111101000011000011100110011110000110
01111000100100100110111101111011100100001100001110
长度为：133
原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性
赫夫曼编码是无损处理方案
注意事项
最佳实践-数据压缩(创建赫夫曼树)
将给出的一段文本，比如 "i like like like java do you like a java" ， 根据前面的讲的赫夫曼编码原理，对其进行数 据 压 缩 处 理 ，形 式 如 :
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
步骤 1：
根据赫夫曼编码压缩数据的原理，需要创建 "i like like like java do you like a java" 对应的赫夫曼树
思路：前面已经分析过了，而且我们已然讲过了构建赫夫曼树的具体实现。
public static Node createHuffManTree(List<Node> nodes) {
while (nodes.size() > 1) {
//首先从小到大排序 list
Collections.sort(nodes);
// 找到list中最小的子树
Node leftnode = nodes.get(0);
//找到倒数第二小的
Node rightnode = nodes.get(1);
Node parent = new Node(null, leftnode.wight + rightnode.wight);
parent.left = leftnode;
parent.right = rightnode;
// 删除两个被处理过的子树
nodes.remove(leftnode);
nodes.remove(rightnode);
// 之后将parent 加入到list
// 这样遍历到最后只剩下一个节点 就是我们需要的赫夫曼树
nodes.add(parent);
}
return nodes.get(0);
}
最佳实践-数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)
我们已经生成了 赫夫曼树, 下面我们继续完成任务
生成赫夫曼树对应的赫夫曼编码 , 如下表:
=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like a java"
字符串生成对应的编码数据, 形式如下:
1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
思路：前面已经分析过了，而且我们讲过了生成赫夫曼编码的具体实现。
/* 生成赫夫曼树对应的赫夫曼编码
* 思路 ：
* 1. 将赫夫曼编码存放在map<byte,string>的形式的map里
* 2。在生成赫夫曼编码表示，需要去拼接一些路径 定一个一个 stringbuilder 存放叶子节点的路径
* */
static Map<Byte, String> huffmanCodes = new HashMap<>();
//存放叶子节点的路径的 stringbuilder
static StringBuilder stringBuilder = new StringBuilder();
//为了调用方便 重载getcode
public static Map<Byte, String> getCodes(Node root) {
if (root == null) {
return null;
}
// 处理左子树
getCodes(root.left, "0", stringBuilder);
//处理右子树
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将传入的node节点的所有子节点的赫夫曼编码得到，并且放入huffmanCodes集合中
* @date: 2022/2/12 15:07
* @return: void
* @param node 传入的节点
* @param code 路径，左子节点是 0 右子节点事 1
* @param stringBuilder 用于拼接路径
*/
public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
//将code 加入到 string builder1
stringBuilder1.append(code);
if (node != null) {
// 如果为null 不处理
//判断是否为叶子结点
if (node.data == null) {
//如果data不为空那么代表非叶子节点
// 向左继续递归
getCodes(node.left, "0", stringBuilder1);
// 向右边递归
getCodes(node.right, "1", stringBuilder1);
} else {
//如果进入到这里说明是一个叶子结点
// 存入到 huffmanCodes这个集合中
huffmanCodes.put(node.data, stringBuilder1.toString());
}
}
}
最佳实践-数据解压(使用赫夫曼编码解码)
使用赫夫曼编码来解码数据，具体要求是
- 前面我们得到了赫夫曼编码和对应的编码 byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77 , -57, 6, -24, -14, -117, -4, -60, -90, 28]
- 现在要求使用赫夫曼编码， 进行解码，又重新得到原来的字符串"i like like like java do you like a java"
- 思路：解码过程，就是编码的一个逆向操作。
/**
* @author 冷环渊 Doomwatcher
* @context: 将一个byte 转成 一个二进制的字符串
* @date: 2022/2/12 23:14
* @param flag 标志是否需要不高位，如果是ture 表示需要补高位，如果是false表示不需要
* @param b 传入的 byte
* @return: java.lang.String 返回的b 对应的二进制的字符串（注意事按照补码返回）
*/
public static String byteToBitString(boolean flag, byte b) {
//使用变量保存 b
int temp = b;
//如果是正数我们还需要补高位
if (flag) {
//按位与 256 1 0000 0000| 00000 0001 => 1 0000 0001
temp |= 256;
}
String str = Integer.toBinaryString(temp);
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
* @author 冷环渊 Doomwatcher
* @context: 完成对数据的解压
* 思路：
* 1. 其实这就是我们之前压缩思路的逆向，
* 2.我们先需要将 byte数组形式的转成二进制的心态，
* 3. 之后转成赫夫曼编码，之后转换成字符
* @date: 2022/2/12 21:49
* @param huffmanBytes 赫夫曼编码对应的byte数组
* @param huffmanCodes 赫夫曼编码表
* @return: void
*/
public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
//1. 先得到huffmancodebytes 对应的 二进制字符串，如 1010100010111
StringBuilder stringBuilder = new StringBuilder();
//将byte 数组转成二进制字符串
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
//System.out.println("赫夫曼字节数组解码二进制=>" + stringBuilder.toString());
// 按照置顶的赫夫曼编码把字符串进行解码
// 把赫夫曼编码进行转换 a ->100 100->a
Map<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
map.put(stringByteEntry.getValue(), stringByteEntry.getKey());
}
//创建一个集合 里面存放byte
List<Byte> list = new ArrayList<>();
// i可以理解成为索引，扫描stringbuilder
for (int i = 0; i < stringBuilder.length(); ) {
//得到编码的计数器
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
//取出一个 ‘1’或者‘0’,i不动 让 count移动直到匹配到一个字符,递增取出
String key = stringBuilder.substring(i, i + count);
b = map.get(key);
if (b == null) {
// 说明没有匹配到
count++;
} else {
//匹配到就退出循环
flag = false;
}
}
list.add(b);
//匹配到之后 i 直接移动步长为count位，就可以继续匹配了，
i += count;
}
//当for循环结束后我们的list存放了所有的字符
// 之后把list 中的数据放入byte[]并且返回
byte[] b = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
最佳实践-文件压缩
我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压， 具体要求：
给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何。
思路：读取文件-> 得到赫夫曼编码表 -> 完成压缩
/**
* @author 冷环渊 Doomwatcher
* @context: 编写方法 完成对压缩文件的解压
* @date: 2022/2/13 0:33
* @param zipFile 准备解压的文件路径
* @param dstFile 将文件解压到什么路径
* @return: void
*/
public static void unZipFile(String zipFile, String dstFile) {
//定义文件输入流
InputStream is = null;
//定义对象输入流
ObjectInputStream ois = null;
//输出流
OutputStream os = null;
try {
// 创建文件输入流
is = new FileInputStream(zipFile);
// 创建对象输入流
ois = new ObjectInputStream(is);
byte[] huffmanbytes = (byte[]) ois.readObject();
// 读取赫夫曼编码表
Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
// 解码
byte[] bytes = decode(huffmanCodes, huffmanbytes);
//将byte 数组写入目标文件
os = new FileOutputStream(dstFile);
// 写数据到fstFile文件
os.write(bytes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
最佳实践-文件解压(文件恢复)
具体要求：将前面压缩的文件，重新恢复成原来的文件。
思路：读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)
/**
* @author 冷环渊 Doomwatcher
* @context: 编写方法 完成对压缩文件的解压
* @date: 2022/2/13 0:33
* @param zipFile 准备解压的文件路径
* @param dstFile 将文件解压到什么路径
* @return: void
*/
public static void unZipFile(String zipFile, String dstFile) {
//定义文件输入流
InputStream is = null;
//定义对象输入流
ObjectInputStream ois = null;
//输出流
OutputStream os = null;
try {
// 创建文件输入流
is = new FileInputStream(zipFile);
// 创建对象输入流
ois = new ObjectInputStream(is);
byte[] huffmanbytes = (byte[]) ois.readObject();
// 读取赫夫曼编码表
Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
// 解码
byte[] bytes = decode(huffmanCodes, huffmanbytes);
//将byte 数组写入目标文件
os = new FileOutputStream(dstFile);
// 写数据到fstFile文件
os.write(bytes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
代码汇总
package com.hyc.DataStructure.huffmanCode;
import java.io.*;
import java.util.*;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.huffmanCode
* @className: huffmanCodeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/9 19:06
* @version: 1.0
*/
public class huffmanCodeDemo {
public static void main(String[] args) {
// 压缩文件测试
// String srcfile = "D:\\JavaEngineer\\algorithm\\code\\DataStructure\\src.bmp";
// String dstfile = "D:\\JavaEngineer\\algorithm\\code\\DataStructure\\srcdst.zip";
// zipFile(srcfile, dstfile);
// 解压文件测试
String zipfile = "D:\\\\JavaEngineer\\\\algorithm\\\\code\\\\DataStructure\\\\srcdst.zip";
String dstFile = "D:\\\\JavaEngineer\\\\algorithm\\\\code\\\\DataStructure\\\\src1.bmp";
unZipFile(zipfile, dstFile);
/* String content = "i like like like java do you like a java";
byte[] contentbytes = content.getBytes();
System.out.println("压缩之前的长度 =>" + contentbytes.length); // 40
byte[] huffmanCodesBytes = huffmanZip(contentbytes);
System.out.println("压缩之后的长度 =>" + huffmanCodesBytes.length);
byte[] decode = decode(huffmanCodes, huffmanCodesBytes);
System.out.println("输出解码之后的字符串" + new String(decode));*/
}
/**
* @author 冷环渊 Doomwatcher
* @context: 编写方法 完成对压缩文件的解压
* @date: 2022/2/13 0:33
* @param zipFile 准备解压的文件路径
* @param dstFile 将文件解压到什么路径
* @return: void
*/
public static void unZipFile(String zipFile, String dstFile) {
//定义文件输入流
InputStream is = null;
//定义对象输入流
ObjectInputStream ois = null;
//输出流
OutputStream os = null;
try {
// 创建文件输入流
is = new FileInputStream(zipFile);
// 创建对象输入流
ois = new ObjectInputStream(is);
byte[] huffmanbytes = (byte[]) ois.readObject();
// 读取赫夫曼编码表
Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
// 解码
byte[] bytes = decode(huffmanCodes, huffmanbytes);
//将byte 数组写入目标文件
os = new FileOutputStream(dstFile);
// 写数据到fstFile文件
os.write(bytes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* @author 冷环渊 Doomwatcher
* @context: 文件压缩
* @date: 2022/2/13 0:17
* @param srcFile 传入的希望压缩的文件的全路径
* @param dstFile 压缩之后需要输出的文件路径
* @return: void
*/
public static void zipFile(String srcFile, String dstFile) {
// 创建文件输出流
// 创建文件输入流
FileInputStream is = null;
FileOutputStream os = null;
ObjectOutputStream oos = null;
try {
is = new FileInputStream(srcFile);
// 创建一个和源文件大小一样的byte数组 当做缓冲区
byte[] bytes = new byte[is.available()];
// 读取文件
is.read(bytes);
//获取到文件对应的赫夫曼编码
byte[] huffmanBytes = huffmanZip(bytes);
// 创建文件的输出流，存放压缩文件
os = new FileOutputStream(dstFile);
// 创建一个和文件输出流关联的objoutputstream
oos = new ObjectOutputStream(os);
//把赫夫曼编码后的字节数组写入压缩文件
oos.writeObject(huffmanBytes);
//这里我们用对象流的方式写入赫夫曼编码，目的是为了回复文件的时候使用
oos.writeObject(huffmanCodes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
os.close();
oos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* @author 冷环渊 Doomwatcher
* @context: 完成对数据的解压
* 思路：
* 1. 其实这就是我们之前压缩思路的逆向，
* 2.我们先需要将 byte数组形式的转成二进制的心态，
* 3. 之后转成赫夫曼编码，之后转换成字符
* @date: 2022/2/12 21:49
* @param huffmanBytes 赫夫曼编码对应的byte数组
* @param huffmanCodes 赫夫曼编码表
* @return: void
*/
public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
//1. 先得到huffmancodebytes 对应的 二进制字符串，如 1010100010111
StringBuilder stringBuilder = new StringBuilder();
//将byte 数组转成二进制字符串
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
//System.out.println("赫夫曼字节数组解码二进制=>" + stringBuilder.toString());
// 按照置顶的赫夫曼编码把字符串进行解码
// 把赫夫曼编码进行转换 a ->100 100->a
Map<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
map.put(stringByteEntry.getValue(), stringByteEntry.getKey());
}
//创建一个集合 里面存放byte
List<Byte> list = new ArrayList<>();
// i可以理解成为索引，扫描stringbuilder
for (int i = 0; i < stringBuilder.length(); ) {
//得到编码的计数器
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
//取出一个 ‘1’或者‘0’,i不动 让 count移动直到匹配到一个字符,递增取出
String key = stringBuilder.substring(i, i + count);
b = map.get(key);
if (b == null) {
// 说明没有匹配到
count++;
} else {
//匹配到就退出循环
flag = false;
}
}
list.add(b);
//匹配到之后 i 直接移动步长为count位，就可以继续匹配了，
i += count;
}
//当for循环结束后我们的list存放了所有的字符
// 之后把list 中的数据放入byte[]并且返回
byte[] b = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将一个byte 转成 一个二进制的字符串
* @date: 2022/2/12 23:14
* @param flag 标志是否需要不高位，如果是ture 表示需要补高位，如果是false表示不需要
* @param b 传入的 byte
* @return: java.lang.String 返回的b 对应的二进制的字符串（注意事按照补码返回）
*/
public static String byteToBitString(boolean flag, byte b) {
//使用变量保存 b
int temp = b;
//如果是正数我们还需要补高位
if (flag) {
//按位与 256 1 0000 0000| 00000 0001 => 1 0000 0001
temp |= 256;
}
String str = Integer.toBinaryString(temp);
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
*
* @author 冷环渊 Doomwatcher
* @context: 封装 赫夫曼编码压缩
* @date: 2022/2/12 20:12
* @param bytes
* @return: byte[]
*/
public static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
Node huffManTreeroot = createHuffManTree(nodes);
Map<Byte, String> codes = getCodes(huffManTreeroot);
byte[] huffmanCodeBytes = zip(bytes, codes);
return huffmanCodeBytes;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 编写一个方法，将字符串转成对应的 Byte[] 数组，通过生成的哈夫曼编码表，返回一个赫夫曼编码压缩后的Byte[]
* 举例子： string content = i like like like java do you like java
* 返回的字符串应该是一大串 八位的byte
* 比如 huffmanCodeBytes[0] = 10101000(补码) => byte[推导 推成反码 10101000 -1 => 10100111（反码）] 原码就是符号位不变，其他取反 [11011000]
* @date: 2022/2/12 15:35
* @param bytes 原始字符串对应的byte
* @param huffmanCodes 生成赫夫曼编码的map
* @return: java.lang.Byte[]
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
// 首先利用 huffmanCode是将 bytes 转成赫夫曼编码的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//System.out.println(stringBuilder);
// 将对应的字符串 转成 byte[]数组
// 返回 数组 huffmancodeBytes的长度
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
// 创建存储压缩后的byte数组
byte[] huffmanCodeBytes = new byte[len];
int index = 0;
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if (i + 8 > stringBuilder.length()) {
// 进入这里代表后面的最后一位数 不够八位了
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i + 8);
}
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/* 生成赫夫曼树对应的赫夫曼编码
* 思路 ：
* 1. 将赫夫曼编码存放在map<byte,string>的形式的map里
* 2。在生成赫夫曼编码表示，需要去拼接一些路径 定一个一个 stringbuilder 存放叶子节点的路径
* */
static Map<Byte, String> huffmanCodes = new HashMap<>();
//存放叶子节点的路径的 stringbuilder
static StringBuilder stringBuilder = new StringBuilder();
//为了调用方便 重载getcode
public static Map<Byte, String> getCodes(Node root) {
if (root == null) {
return null;
}
// 处理左子树
getCodes(root.left, "0", stringBuilder);
//处理右子树
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
/**
* @author 冷环渊 Doomwatcher
* @context: 将传入的node节点的所有子节点的赫夫曼编码得到，并且放入huffmanCodes集合中
* @date: 2022/2/12 15:07
* @return: void
* @param node 传入的节点
* @param code 路径，左子节点是 0 右子节点事 1
* @param stringBuilder 用于拼接路径
*/
public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
//将code 加入到 string builder1
stringBuilder1.append(code);
if (node != null) {
// 如果为null 不处理
//判断是否为叶子结点
if (node.data == null) {
//如果data不为空那么代表非叶子节点
// 向左继续递归
getCodes(node.left, "0", stringBuilder1);
// 向右边递归
getCodes(node.right, "1", stringBuilder1);
} else {
//如果进入到这里说明是一个叶子结点
// 存入到 huffmanCodes这个集合中
huffmanCodes.put(node.data, stringBuilder1.toString());
}
}
}
//前序遍历
public static void PreOrder(Node node) {
if (node != null) {
node.PreOrder();
} else {
System.out.println("空树无法遍历");
}
}
/**
*
* @author 冷环渊 Doomwatcher
* @context: 用来生成每一个节点的出现次数的list集合
* @date: 2022/2/10 2:40
* @param bytes 存放每一个字母的数组
* @return: java.util.List<com.hyc.DataStructure.huffmanCode.Node> 返回一个带着字母出现权重的list
*/
public static List<Node> getNodes(byte[] bytes) {
// 创建一个 arraylist
ArrayList<Node> nodes = new ArrayList<>();
// 遍历bytes 统计每一个bytes 出现的次数 用 map 来统计
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {
// map 还没有这个字符 证明是第一次
counts.put(b, 1);
} else {
// 进入到这里说明之前有加入过了
counts.put(b, count + 1);
}
}
//把每个键值对转换成一个 Node 对象 并且进入到Nodes集合
//遍历map
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
public static Node createHuffManTree(List<Node> nodes) {
while (nodes.size() > 1) {
//首先从小到大排序 list
Collections.sort(nodes);
// 找到list中最小的子树
Node leftnode = nodes.get(0);
//找到倒数第二小的
Node rightnode = nodes.get(1);
Node parent = new Node(null, leftnode.wight + rightnode.wight);
parent.left = leftnode;
parent.right = rightnode;
// 删除两个被处理过的子树
nodes.remove(leftnode);
nodes.remove(rightnode);
// 之后将parent 加入到list
// 这样遍历到最后只剩下一个节点 就是我们需要的赫夫曼树
nodes.add(parent);
}
return nodes.get(0);
}
}
class Node implements Comparable<Node> {
//用于存放字符的ascll值
Byte data;
//出现的次数 权重
int wight;
Node left;
Node right;
public Node(Byte data, int wight) {
this.data = data;
this.wight = wight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", wight=" + wight +
'}';
}
// 前序遍历
public void PreOrder() {
System.out.println(this);
if (this.left != null) {
this.left.PreOrder();
}
if (this.right != null) {
this.right.PreOrder();
}
}
@Override
public int compareTo(Node o) {
return this.wight - o.wight;
}
}
赫夫曼编码压缩文件注意事项
- 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
- 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml 文件]
- 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显.
二叉排序树
先看一个需求:
给你一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加
使用数组
数组未排序， 优点：直接在数组尾添加，速度快。 缺点：查找速度慢.
数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位
置后，后面的数据需整体移动，速度慢。
链式存储-链表
不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。
二叉排序树介绍
二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当 前节点的值小，右子节点的值比当前节点的值大。
特别声明
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：
二叉排序树创建和遍历
一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树，比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ， 创
建成对应的二叉排序树为 :
二叉排序树的删除
二叉排序树的删除情况比较复杂，有下面三种情况需要考虑
- 删除叶子节点 (比如：2, 5, 9, 12)
- 删除只有一颗子树的节点 (比如：1)
- 删除有两颗子树的节点. (比如：7, 3，10 )
对删除结点的各种情况的思路分析:
第一种情况: 删除叶子节点 (比如：2, 5, 9, 12)
思路：
- 需求先去找到要删除的结点 targetNode
- 找到 targetNode 的 父结点 parent
- 确定 targetNode 是 parent 的左子结点 还是右子结点
- 根据前面的情况来对应删除
左子结点 parent.left = null
右子结点 parent.right = null;
第二种情况: 删除只有一颗子树的节点 比如 1
思路 :
- 需求先去找到要删除的结点 targetNode
- 找到 targetNode 的 父结点 parent
- 确定 targetNode 的子结点是左子结点还是右子结点
- targetNode 是 parent 的左子结点还是右子结点
- 如果 targetNode 有左子结点
- 如果 targetNode 是 parent 的左子结点 parent.left = targetNode.left;
- 如果 targetNode 是 parent 的右子结点 parent.right = targetNode.left;
- 如果 targetNode 有右子结点
- 如果 targetNode 是 parent 的左子结点 parent.left = targetNode.right
- 如果 targetNode 是 parent 的右子结点 parent.right = targetNode.right
情况三 ： 删除有两颗子树的节点. (比如：7, 3，10 )
思路 :
- 需求先去找到要删除的结点 targetNode
- 找到 targetNode 的 父结点 parent
- 从 targetNode 的右子树找到最小的结点
- 用一个临时变量，将 最小结点的值保存 temp = 11
- 删除该最小结点
- targetNode.value = temp
二叉排序树代码实现
package com.hyc.DataStructure.binarysorttree;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.binarysorttree
* @className: BinarySortDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/15 16:33
* @version: 1.0
*/
public class BinarySortDemo {
public static void main(String[] args) {
int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
BinarySortTree binarySortTree = new BinarySortTree();
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
// 中序要遍历
binarySortTree.infixOrder();
// 测试删除节点
binarySortTree.delNode(2);
binarySortTree.delNode(7);
binarySortTree.delNode(3);
binarySortTree.delNode(12);
binarySortTree.delNode(5);
binarySortTree.delNode(1);
binarySortTree.delNode(9);
binarySortTree.delNode(10);
System.out.println("删除节点后");
// 中序要遍历
binarySortTree.infixOrder();
}
}
class BinarySortTree {
private Node root;
//查找要删除的节点
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
//查找父节点·
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
//删除节点方法
public void delNode(int value) {
if (root == null) {
return;
} else {
// 需要先去找到要删除的节点，targetNode
Node targetNode = search(value);
// 如果没有找到要删除的节点
if (targetNode == null) {
return;
}
// 如果我们发现当前这个颗树 只有一个节点
if (root.left == null && root.right == null) {
root = null;
return;
}
// 找到targetNode的父节点
Node parent = searchParent(value);
// 如果需要删除的节点是叶子节点
if (targetNode.left == null && targetNode.right == null) {
// 判断targetNode是父节点的左子节点还是右子节点
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {
// 删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else {
// 删除有一颗子树
// 如果要删除的节点有左子节点
if (targetNode.left != null) {
//判断 parent 的非空判断
if (parent != null) {
// 如果targetNode是Parent的左子节点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {
//targentNode 是parent右子节点
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else {
if (parent != null) {
// 如果要删除的节点有右子节点
// 如果targetNode 是parent的右子节点
if (parent.left.value == value) {
parent.left = targetNode.right;
} else {
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 返回的以node为根节点的二叉树的最小节点值
* 删除node 为根节点的二叉排序树的最小节点
* @date: 2022/2/17 22:19
* @param node 传入的节点 （当前二叉排序树树的根节点）
* @return: int 返回的以node为根节点的二叉排序树的最小节点值
*/
public int delRightTreeMin(Node node) {
Node target = node;
// 循环查找左节点 就会找到最小值
while (target.left != null) {
target = target.left;
}
//这个target就指向了最小的节点
//删除最小节点
delNode(target.value);
return target.value;
}
// 添加节点的方法
public void add(Node node) {
//如果能空的话
if (root == null) {
root = node;
} else {
root.add(node);
}
}
// 中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("空树 无法遍历");
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 找到想要查到要删除的节点
* @date: 2022/2/17 14:15
* @param value 想要删除的节点的值
* @return: com.hyc.DataStructure.binarysorttree.Node 如果找到了就返回节点，如果没找到那就返回null
*/
public Node search(int value) {
if (value == this.value) {
//如果相同就返回自己
return this;
} else if (value < this.value) {
//如果查找的值 小于当前节点就向左子树递归查找
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
// 如果查找的值不下节点，向右子树递归查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
/**
* @author 冷环渊 Doomwatcher
* @context: 查找要删除节点的父节点
* @date: 2022/2/17 14:23
* @param value value 要找的节点值
* @return: com.hyc.DataStructure.binarysorttree.Node 返回的事要删除的节点
*/
public Node searchParent(int value) {
// 判断当前节点的两个子节点的值是不是等于我们要查找的值，如果是的话当前节点就是我们要寻找的父节点
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小于当前的节点值，并且当前节点的左子节点不等于空
if (value < this.value && this.left != null) {
//向左子树递归查找
return this.left.searchParent(value);
} else if (value >= this.value && this.right != null) {
//向右子树递归查找
return this.right.searchParent(value);
} else {
//没有找到
return null;
}
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public void add(Node node) {
if (node == null) {
return;
}
// 判断传入接待你值是否大于当前节点
if (node.value < this.value) {
//如果当前节点左子节点为null
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
// 判断节点如果大于当前节点的值
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
//中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
平衡二叉树(AVL 树)
给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在. ：
- 左子树全部为空，从形式上看，更像一个单链表.
- 插入速度没有影响
- 查询速度明显降低(因为需要依次比较), 不能发挥 BST 的优势，因为每次还需要比较左子树，其查询速度比
解决方案-平衡二叉树(AVL)
基本介绍
- 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树， 可以保证查询效率较高。
- 具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵 平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
- 举例说明, 看看下面哪些 AVL 树, 为什么?
应用案例-单旋转(左旋转)
给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}
左旋转代码
//左旋转方法
public void leftRotate() {
// 创建新节点 以当前节点的值
Node newnode = new Node(value);
// 把新节点的左子树这只成当前节点的左子树
newnode.left = left;
// 把新节点的右子树设置成当前节点的右子树的左子树
newnode.right = right.left;
//把当前节点的值 替换成右子节点的值
value = right.value;
// 把当前节点右子树设置成下一个节点的右子树
right = right.right;
// 把当前节点的左子树设置成新的节点
left = newnode;
}
应用案例-单旋转(右旋转)
给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}
右旋转代码
//右旋转方法
public void rightRotate() {
Node newnode = new Node(value);
newnode.right = right;
newnode.left = left.right;
value = left.value;
left = left.left;
right = newnode;
}
应用案例-双旋转
前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转 不能完成平衡二叉树的转换。比如数列
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL 树.
int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL 树
- 当符号右旋转的条件时
- 如果它的左子树的右子树高度大于它的左子树的高度
- 先对当前这个结点的左节点进行左旋转
- 在对当前结点进行右旋转的操作即可
代码汇总
package com.hyc.DataStructure.AVL;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.AVL
* @className: avlTreeDemo
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/18 23:30
* @version: 1.0
*/
public class avlTreeDemo {
public static void main(String[] args) {
//左旋转demo实例
//int[] arr = {4, 3, 6, 5, 7, 8};
//右旋转demo实例
int[] arr = {10, 12, 8, 9, 7, 6};
//int[] arr = {10, 11, 7, 6, 8, 9};
//创建一个 AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for (int i = 0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("在平衡处理~~");
System.out.println("树的高度=" + avlTree.getRoot().height()); //3
System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("当前的根结点=" + avlTree.getRoot());//8
}
}
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
//查找要删除的节点
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
//查找父节点·
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
//删除节点方法
public void delNode(int value) {
if (root == null) {
return;
} else {
// 需要先去找到要删除的节点，targetNode
Node targetNode = search(value);
// 如果没有找到要删除的节点
if (targetNode == null) {
return;
}
// 如果我们发现当前这个颗树 只有一个节点
if (root.left == null && root.right == null) {
root = null;
return;
}
// 找到targetNode的父节点
Node parent = searchParent(value);
// 如果需要删除的节点是叶子节点
if (targetNode.left == null && targetNode.right == null) {
// 判断targetNode是父节点的左子节点还是右子节点
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {
// 删除有两颗子树的节点
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else {
// 删除有一颗子树
// 如果要删除的节点有左子节点
if (targetNode.left != null) {
//判断 parent 的非空判断
if (parent != null) {
// 如果targetNode是Parent的左子节点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {
//targentNode 是parent右子节点
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else {
if (parent != null) {
// 如果要删除的节点有右子节点
// 如果targetNode 是parent的右子节点
if (parent.left.value == value) {
parent.left = targetNode.right;
} else {
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 返回的以node为根节点的二叉树的最小节点值
* 删除node 为根节点的二叉排序树的最小节点
* @date: 2022/2/17 22:19
* @param node 传入的节点 （当前二叉排序树树的根节点）
* @return: int 返回的以node为根节点的二叉排序树的最小节点值
*/
public int delRightTreeMin(Node node) {
Node target = node;
// 循环查找左节点 就会找到最小值
while (target.left != null) {
target = target.left;
}
//这个target就指向了最小的节点
//删除最小节点
delNode(target.value);
return target.value;
}
// 添加节点的方法
public void add(Node node) {
//如果能空的话
if (root == null) {
root = node;
} else {
root.add(node);
}
}
// 中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("空树 无法遍历");
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//左旋转方法
public void leftRotate() {
// 创建新节点 以当前节点的值
Node newnode = new Node(value);
// 把新节点的左子树这只成当前节点的左子树
newnode.left = left;
// 把新节点的右子树设置成当前节点的右子树的左子树
newnode.right = right.left;
//把当前节点的值 替换成右子节点的值
value = right.value;
// 把当前节点右子树设置成下一个节点的右子树
right = right.right;
// 把当前节点的左子树设置成新的节点
left = newnode;
}
//右旋转方法
public void rightRotate() {
Node newnode = new Node(value);
newnode.right = right;
newnode.left = left.right;
value = left.value;
left = left.left;
right = newnode;
}
//返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
//返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
public int height() {
//加一是因为需要算上当前节点
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
/**
* @author 冷环渊 Doomwatcher
* @context:
* 找到想要查到要删除的节点
* @date: 2022/2/17 14:15
* @param value 想要删除的节点的值
* @return: Node 如果找到了就返回节点，如果没找到那就返回null
*/
public Node search(int value) {
if (value == this.value) {
//如果相同就返回自己
return this;
} else if (value < this.value) {
//如果查找的值 小于当前节点就向左子树递归查找
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
// 如果查找的值不下节点，向右子树递归查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
/**
* @author 冷环渊 Doomwatcher
* @context: 查找要删除节点的父节点
* @date: 2022/2/17 14:23
* @param value value 要找的节点值
* @return: Node 返回的事要删除的节点
*/
public Node searchParent(int value) {
// 判断当前节点的两个子节点的值是不是等于我们要查找的值，如果是的话当前节点就是我们要寻找的父节点
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小于当前的节点值，并且当前节点的左子节点不等于空
if (value < this.value && this.left != null) {
//向左子树递归查找
return this.left.searchParent(value);
} else if (value >= this.value && this.right != null) {
//向右子树递归查找
return this.right.searchParent(value);
} else {
//没有找到
return null;
}
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public void add(Node node) {
if (node == null) {
return;
}
// 判断传入接待你值是否大于当前节点
if (node.value < this.value) {
//如果当前节点左子节点为null
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
// 判断节点如果大于当前节点的值
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
// 当前添加玩一个节点之后 判断（ 右子树的高度 - 左子树的高度 >1 ）就代表需要左旋转
if (rightHeight() - leftHeight() > 1) {
//如果他的右子树的左子树高度大于它的右子树的右子树的高度
if (right != null && right.leftHeight() > right.leftHeight()) {
// 先对右子节点，进行右旋转
right.rightRotate();
leftHeight();
} else {
// 直接进行左旋转即可
leftRotate();
}
return;
}
// 当添加完一个节点后，如果(左子树的高度-右子树的高度)>1 右旋转
if (leftHeight() - rightHeight() > 1) {
if (left != null && left.rightHeight() > left.leftHeight()) {
// 先对当前节点的左结点（左子树） - 》左旋转
left.leftRotate();
//再对当前节点进行右旋转
rightRotate();
} else {
//直接进行右旋转即可
rightRotate();
}
}
}
//中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
多路查找树
二叉树与 B 树
二叉树的问题分析
-
二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如 1 亿)， 就 存在如下问题:
-
问题 1：在构建二叉树时，需要多次进行 i/o 操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时， 速度有影响
-
问题 2：节点海量，也会造成二叉树的高度很大，会降低操作速度
多叉树
- 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点， 就是多叉树（multiway tree）
- 后面我们讲解的 2-3 树，2-3-4 树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化。
2-3树是一种多叉树
B 树的基本介绍
B 树通过重新组织节点，降低树的高度，并且减少 i/o 读写次数来提升效率。
- 如图 B 树通过重新组织节点， 降低了树的高度.
- 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为 4k)， 这样每个节点只需要一次 I/O 就可以完全载入
- 将树的度 M 设置为 1024，在 600 亿个元素中最多只需要 4 次 I/O 操作就可以读取到想要的元素, B 树(B+)广泛 应用于文件存储系统以及数据库系统中
2-3 树
2-3 树是最简单的 B 树结构, 具有如下特点:
- 2-3 树的所有叶子节点都在同一层.(只要是 B 树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点.
- 2-3 树是由二节点和三节点构成的树。
2-3 树应用案例
将数列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成 2-3 树，并保证数据插入的大小顺序。(演示一下构建 2-3 树的过程.)
插入规则:
- 2-3 树的所有叶子节点都在同一层.(只要是 B 树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点.
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
- 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层， 拆后仍然需要满足上面 3 个条件。
- 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则
除了 23 树，还有 234 树等，概念和 23 树类似，也是一种 B 树。
B 树、B+树和 B*树
B-tree 树即 B 树，B 即 Balanced，平衡的意思。有人把 B-tree 翻译成 B-树，容易让人产生误解。会以为 B-树 是一种树，而 B 树又是另一种树。实际上，B-tree 就是指的 B 树。
前面已经介绍了 2-3 树和 2-3-4 树，他们就是 B 树(英语：B-tree 也写成 B-树)，这里我们再做一个说明，我们在学 习 Mysql 时，经常听到说某种类型的索引是基于 B 树或者 B+树的，如图:
对上图的说明:
- B 树的阶：节点的最多子节点个数。比如 2-3 树的阶是 3，2-3-4 树的阶是 4
- B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询 关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
- 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据
- 搜索有可能在非叶子结点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
B+树的介绍
B+树是 B 树的变体，也是一种多路搜索树。
对上图的说明:
- B+树的搜索与 B 树也基本相同，区别是 B+树只有达到叶子结点才命中（B 树可以在非叶子结点命中），其性 能也等价于在关键字全集做一次二分查找
- 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据) 恰好是有序的。
- 不可能在非叶子结点命中
- 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
- 更适合文件索引系统
- B 树和 B+树各有自己的应用场景，不能说 B+树完全比 B 树好，反之亦然
B*树的介绍
B*树是 B+树的变体，在 B+树的非根和非叶子结点再增加指向兄弟的指针。
B*树的说明:
-
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为 2/3，而 B+树的块的最低使用率为的
1/2。
-
从第 1 个特点我们可以看出，B*树分配新结点的概率比 B+树要低，空间使用率更高
Trie树
又称为: 前缀树,字典树
取名来自 retrieval
什么是Trie树!??
比如我们一串字符串需要检查拼写错误
数据: code cook Five File Fat
根据匹配这串字符生成的字典树
特点:
- 根节点不包括字符,除去根节点外 每个节点只包含一个字符
- 从根节点到叶子节点,路径上经过的字符,对应的字符串
- 每个节点的子节点包含不同的字符(相同字符在下一层节点分裂)
此时演示特点三的情况
插入规则:
- 先查看节点是否存在,存在i向下遍历,不存咋创建新的节点
查找规则:
- 从根节点开始遍历,如查找goodbye Good 找到前缀字符,但是此时字典树遍历完成,而单词并没有完成,结果任然不存在
删除规则
- 先要遍历出当前字符串路径,从叶子节点向上删除,除去叶子节点外的节点,如果有其他节点,此节点保留,删除子树
并查集
从一个逻辑题来给大家介绍并查集
现在有十个强盗
一号强盗与二号强盗是同伙
三号强盗与四号强盗是同伙
五号强盗与二号强盗是同伙
四号强盗与六号强盗是同伙
二号强盗与六号强盗是同伙
八号强盗与七号强盗是同伙
九号强盗与七号强盗是同伙
一号强盗与六号强盗是同伙
二号强盗与四号强盗是同伙
有一点需要注意 强盗同伙的同伙也是同伙,你能找出来有多少独立的犯罪团伙吗?
根据题目分析出逻辑上三个情况
part1 1 2 5 3 4 6
part 2 7 8 9
part 10
数组理解
这里数组下标按照从1开始理解;
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
一号和二号一组
| 1 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
三号和四号
| 1 | 1 | 3 | 3 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
五号和二号
| 5 | 5 | 3 | 3 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
四号和六号
| 5 | 5 | 3 | 3 | 5 | 3 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
二号和六号
| 5 | 5 | 3 | 3 | 5 | 5 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
八号和七号
| 5 | 5 | 5 | 5 | 5 | 5 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
九号和七号
| 5 | 5 | 3 | 3 | 5 | 5 | 9 | 9 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
以上是我们用数组变化的方式来理解的并查集逻辑题目,接下来是树的理解
树结构理解
并查集
其实就是 合并和查询的集合
合并:把两个不相交的集合合并为一个集合
查询,查询两个元素是否在同一个集合中
用一个元素代表集合,成为集合首领,判断是否在集合中,让元素存储首领来判断,合并需选出新的首领,将被合并的集合元素首领改成新的首领
另一种角度上说,并查集是将一个集合以树结构进行组合的数据结构.
优先级队列
PriocrityQueue, 根据优先级的顺序排队,
如果想要自定义规则需要自定义比较其 : conparator
简单使用优先级队列
package com.hyc.DataStructure.PriorityQueue;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.PriorityQueue
* @className: PriorityQueueTest
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/26 12:25
* @version: 1.0
*/
public class PriorityQueueTest {
public static void main(String[] args) {
//PriorityQueue<String> queue = new PriorityQueue<>();
//queue.offer("1");
//queue.offer("2");
//queue.offer("3");
//queue.offer("4");
//System.out.println(queue.poll());
//System.out.println(queue.poll());
//System.out.println(queue.poll());
//System.out.println(queue.poll());
PriorityQueue<student> studentQueue = new PriorityQueue<>(new Comparator<>() {
@Override
public int compare(student o1, student o2) {
if (o1.score == o2.score) {
return o1.name.compareTo(o2.name);
}
return o1.score - o2.score;
}
private static final long serialVersionUID = -2730510067769567346L;
}
);
studentQueue.offer(new student("atuo", 80));
studentQueue.offer(new student("dmc", 60));
studentQueue.offer(new student("amc", 60));
studentQueue.offer(new student("yqing", 100));
System.out.println(studentQueue.poll());
System.out.println(studentQueue.poll());
System.out.println(studentQueue.poll());
System.out.println(studentQueue.poll());
}
}
class student {
@Override
public String toString() {
return "student{" +
"name='" + name + '\'' +
", score=" + score +
'}';
}
public String name;
public int score;
public student(String name, int score) {
this.name = name;
this.score = score;
}
}
实战题目
面试题 17.14. 最小K个数
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例
输入: arr = [1,3,5,7,2,4,6,8] k = 4
输出 [1,2,3,4]
没有使用优先级队列的时候
public static int[] smallestK(int[] arr, int k) {
Arrays.sort(arr);
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = arr[i];
}
return result;
}
使用了队列的
public static int[] smallestKByQueue(int[] arr, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
int[] result = new int[k];
for (int i = 0; i < arr.length; i++) {
queue.offer(arr[i]);
}
for (int j = 0; j < k; j++) {
result[j] = queue.poll();
}
return result;
}
使用了大顶堆
public static int[] smallestByHeap(int[] arr, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
int[] result = new int[k];
for (int i = 0; i < arr.length; i++) {
queue.offer(arr[i]);
}
for (int i = 0; i < arr.length - k; i++) {
queue.poll();
}
for (int j = 0; j < k; j++) {
result[j] = queue.poll();
}
return result;
}
这里主要是学习实战优先级队列的使用,最后提交会发现速度最快的是第一种方法
图
图基本介绍
- 前面我们学了线性表和树
- 线性表局限于一个直接前驱和一个直接后继的关系
- 树也只能有一个直接前驱也就是父节点
- 当我们需要表示多对多的关系时， 这里我们就用到了图。
图的举例说明
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为
顶点。
图的常用概念
-
顶点(vertex)
-
边(edge)
-
路径
-
无向图(下图
-
有向图
-
带权图
图的表示方式
图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。
邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于 n 个顶点的图而言，矩阵是的 row 和 col 表示的是 1....n 个点。
邻接表
- 邻接矩阵需要为每个顶点都分配 n 个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
- 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成
图的快速入门案例
代码实现如下图结构.
思路:存储顶点 String 使用 ArrayList (2) 保存矩阵 int[][] edges存储顶点 String 使用 ArrayList (2) 保存矩阵 int[][] edges
图的深度优先遍历介绍
所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种
访问策略: (1)深度优先遍历 (2)广度优先遍历
深度优先遍历基本思想
图的深度优先搜索(Depth First Search) 。
- 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问 第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解： 每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
- 我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
- 显然，深度优先搜索是一个递归的过程
深度优先遍历算法步骤
- 访问初始结点 v，并标记结点 v 为已访问。
- 查找结点 v 的第一个邻接结点 w。
- 若 w 存在，则继续执行 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个结点继续。
- 若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当做另一个 v，然后进行步骤 123）。
- 查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3。
深度优先代码实现
//深度优先遍历方法
public void dfs(boolean[] isVisted, int i) {
// 首先输出该节点
System.out.print(getValueByindex(i) + "->");
// 将该节点设置为已经访问过
isVisted[i] = true;
//查找节点i 的第一个邻结节点
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isVisted[w]) {
dfs(isVisted, w);
}
// 如果w节点已经被访问过了，那么我
w = getNexttNeighbor(i, w);
}
}
//对dfs进行重载，遍历我们所有的节点并且进行dfs
public void dfs() {
for (int i = 0; i < getNumOFVertex(); i++) {
if (!isVisted[i]) {
dfs(isVisted, i);
}
}
}
图的广度优先遍历
广度优先遍历基本思想:
- 图的广度优先搜索(Broad First Search) 。
- 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来 访问这些结点的邻接结点
广度优先遍历算法步骤
- 访问初始结点 v 并标记结点 v 为已访问。
- 结点 v 入队列
- 当队列非空时，继续执行，否则算法结束。
- 出队列，取得队头结点 u。
- 查找结点 u 的第一个邻接结点 w。
- 若结点 u 的邻接结点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤：
- 若结点 w 尚未被访问，则访问结点 w 并标记为已访问。
- 结点 w 入队列
- 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤 6。
广度优先算法的代码实现
//对一个节点进行广度优先搜索遍历
public void bfs(boolean[] isVisted, int i) {
//表示队列的头节点的对应下标
int u;
//邻节点w
int w;
//模拟队列记录节点访问的顺序
LinkedList<Object> queue = new LinkedList<>();
//输出节点信息
System.out.print(getValueByindex(i) + "->");
// 标记为已访问
isVisted[i] = true;
// 将节点加入队列
queue.addLast(i);
//判断只要非空就一直找
while (!queue.isEmpty()) {
// 取出队列头节点下标
u = (Integer) queue.removeFirst();
w = getFirstNeighbor(u);
while (w != -1) {
// 是否访问过
if (!isVisted[w]) {
System.out.print(getValueByindex(w) + "->");
// 标记已经访问
isVisted[w] = true;
// 入队
queue.addLast(w);
}
// 如果访问过 以u 为前驱点 找w后面的第一个节点
w = getNexttNeighbor(u, w);//体现出广度优先
}
}
}
//遍历所有的节点都进行广度优先搜索
public void bfs() {
for (int i = 0; i < getNumOFVertex(); i++) {
if (!isVisted[i]) {
bfs(isVisted, i);
}
}
}
代码汇总
package com.hyc.DataStructure.garph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
/**
* @projectName: DataStructure
* @package: com.hyc.DataStructure.garph
* @className: Graph
* @author: 冷环渊 doomwatcher
* @description: TODO
* @date: 2022/2/22 17:52
* @version: 1.0
*/
public class Graph {
//存储顶点结合
private ArrayList<String> vertexList;
//存储图对应的邻结矩阵
private int[][] edges;
//表示边的数目
private int numOFEdges;
private boolean[] isVisted;
public static void main(String[] args) {
//测试一把图是否创建ok
int n = 8; //结点的个数
//String Vertexs[] = {"A", "B", "C", "D", "E"};
String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
//创建图对象
Graph graph = new Graph(n);
//循环的添加顶点
for (String vertex : Vertexs) {
graph.insertVertex(vertex);
}
//添加边
//A-B A-C B-C B-D B-E
// graph.insertEdge(0, 1, 1); // A-B
// graph.insertEdge(0, 2, 1); //
// graph.insertEdge(1, 2, 1); //
// graph.insertEdge(1, 3, 1); //
// graph.insertEdge(1, 4, 1); //
//更新边的关系
graph.insertEdges(0, 1, 1);
graph.insertEdges(0, 2, 1);
graph.insertEdges(1, 3, 1);
graph.insertEdges(1, 4, 1);
graph.insertEdges(3, 7, 1);
graph.insertEdges(4, 7, 1);
graph.insertEdges(2, 5, 1);
graph.insertEdges(2, 6, 1);
graph.insertEdges(5, 6, 1);
//显示 邻结矩阵
graph.showGarph();
//// 测试深度遍历
System.out.println("深度遍历");
graph.dfs();
System.out.println();
//测试广度优先搜索
//System.out.println("广度遍历");
//graph.bfs();
}
//构造器
public Graph(int n) {
// 初始化矩阵和VertexList
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOFEdges = 0;
isVisted = new boolean[n];
}
/**
* @author 冷环渊 Doomwatcher
* @context: 得到第一个邻节点的下标
* @date: 2022/2/22 18:22
* @param index 如果存在就是返回对应的下标 否则返回-1
* @return: int
*/
public int getFirstNeighbor(int index) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
public int getNexttNeighbor(int v1, int v2) {
for (int j = v2 + 1; j < vertexList.size(); j++) {
if (edges[v1][j] > 0) {
return j;
}
}
return -1;
}
//深度优先遍历方法
public void dfs(boolean[] isVisted, int i) {
// 首先输出该节点
System.out.print(getValueByindex(i) + "->");
// 将该节点设置为已经访问过
isVisted[i] = true;
//查找节点i 的第一个邻结节点
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isVisted[w]) {
dfs(isVisted, w);
}
// 如果w节点已经被访问过了，那么我
w = getNexttNeighbor(i, w);
}
}
//对dfs进行重载，遍历我们所有的节点并且进行dfs
public void dfs() {
for (int i = 0; i < getNumOFVertex(); i++) {
if (!isVisted[i]) {
dfs(isVisted, i);
}
}
}
//对一个节点进行广度优先搜索遍历
public void bfs(boolean[] isVisted, int i) {
//表示队列的头节点的对应下标
int u;
//邻节点w
int w;
//模拟队列记录节点访问的顺序
LinkedList<Object> queue = new LinkedList<>();
//输出节点信息
System.out.print(getValueByindex(i) + "->");
// 标记为已访问
isVisted[i] = true;
// 将节点加入队列
queue.addLast(i);
//判断只要非空就一直找
while (!queue.isEmpty()) {
// 取出队列头节点下标
u = (Integer) queue.removeFirst();
w = getFirstNeighbor(u);
while (w != -1) {
// 是否访问过
if (!isVisted[w]) {
System.out.print(getValueByindex(w) + "->");
// 标记已经访问
isVisted[w] = true;
// 入队
queue.addLast(w);
}
// 如果访问过 以u 为前驱点 找w后面的第一个节点
w = getNexttNeighbor(u, w);//体现出广度优先
}
}
}
//遍历所有的节点都进行广度优先搜索
public void bfs() {
for (int i = 0; i < getNumOFVertex(); i++) {
if (!isVisted[i]) {
bfs(isVisted, i);
}
}
}
//图中常用的方法
//返回节点的数目
public int getNumOFVertex() {
return vertexList.size();
}
//返回节点i 对应的下标数据
public String getValueByindex(int i) {
return vertexList.get(i);
}
//返回v1和v2的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
//显示矩阵
public void showGarph() {
for (int[] edge : edges) {
System.out.println(Arrays.toString(edge));
}
}
// 插入顶点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
/**
* @author 冷环渊 Doomwatcher
* @context: 添加边
* @date: 2022/2/22 18:01
* @param v1 表示点的下标 即使 第几个顶点 a-b a ->0 b->1
* @param v2 和v1同理是第二个顶点的下标
* @param weight 表示矩阵里面用什么来表示他们是关连的 0 表示没有连接 1 表示连接了
* @return: void
*/
public void insertEdges(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOFEdges++;
}
}
图的深度优先 VS 广度优先
分类:
无
标签:
Java | 算法 | 数据结构