Java教程
数据结构算法
本文主要是介绍数据结构算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
https://www.bilibili.com/video/BV1E4411H73v?p=6
数据结构包括:线性结构和非线性结构。
线性结构：
-
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
-
线性结构有两种不同的存储结构，即顺序存储结构（数组）和链式存储结构（链表）。顺序存储结构的线性表称为顺序表，顺序表中的存储元素是连续的。
-
链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
-
线性结构常见的有：数组、队列、链表和栈。
非线性结构：
- 非线性结构包括：二维数组、多维数组、广义表、树结构、图结构。
一、稀疏数组和队列
1、稀疏数组
基本介绍：
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法：
- 记录数组一共有几行几列，有多少个不同的值。
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
如图，把一个6X7的二维数组变为了一个9X3的稀疏数组。其中
- 第一行保存的是原二维数组的行、列以及非0值的个数
- 第二到九行保存的是每个非0值所在的位置及其数值
思路转换：
二维数组转稀疏数组：
- 遍历原始的二维数组，得到有效数据的个数sum
- 创建稀疏数组，有sum+1行，3列（固定）
- 将二维数组中的有效值存入稀疏数组中
稀疏数组转二维数组：
- 先读取稀疏数组的第一行根据第一行数据，创建原始的二维数组
- 读取稀疏数组后几行的数据，将值赋给二维数组的对应位置上的数
代码：
public static void main(String[] args) {
//创建一个二维数组
int[][] arr1 = new int[11][11];
//向二维数组里放值
arr1[1][2] = 1;
arr1[2][3] = 2;
arr1[3][4] = 3;
//打印二维数组
System.out.println("遍历二维数组");
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[0].length; j++) {
System.out.print(arr1[i][j] + " ");
}
System.out.println();
}
//二位数组----->稀疏数组
//遍历二维数组中有效值的个数,用sum来记录
int sum = 0;
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[0].length; j++) {
if (arr1[i][j] != 0) {
//二维数组中元素不为0即为有效值
sum++;
}
}
}
//创建稀疏数组
//行数为sum+1，第一行用于保存二维数组的行列及有效值个数，列数固定为3
int[][] sparseArr = new int[sum + 1][3];
//存入二维数组的行列及有效值个数
sparseArr[0][0] = arr1.length;
sparseArr[0][1] = arr1[0].length;
sparseArr[0][2] = sum;
//再次遍历二维数组，将有效值存入稀疏数组
//用于保存稀疏数组的行数
int count = 1;
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[0].length; j++) {
if (arr1[i][j] != 0) {
//将值存入稀疏数组
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = arr1[i][j];
count++;
}
}
}
//打印稀疏数组
System.out.println("遍历稀疏数组");
for (int i = 0; i < sparseArr.length; i++) {
for (int j = 0; j < sparseArr[0].length; j++) {
System.out.print(sparseArr[i][j] + " ");
}
System.out.println();
}
//稀疏数组------>二维数组
//先得到二位数组的行列数
int row = sparseArr[0][0];
int col = sparseArr[0][1];
int[][] arr2 = new int[row][col];
//遍历稀疏数组，同时给二维数组赋值
for (int i = 1; i < sparseArr.length; i++) {
row = sparseArr[i][0];
col = sparseArr[i][1];
//该位置上对应的值
int val = sparseArr[i][2];
arr2[row][col] = val;
}
//打印二维数组
System.out.println("遍历还原后的二维数组");
for (int i = 0; i < arr2.length; i++) {
for (int j = 0; j < arr2[0].length; j++) {
System.out.print(arr2[i][j] + " ");
}
System.out.println();
}
}
运行结果：
遍历二维数组 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 遍历稀疏数组 11 11 3 1 2 1 2 3 2 3 4 3 遍历还原后的二维数组 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2、队列
定义
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
数组模拟队列
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示
入队出队操作模拟
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：
- 将尾指针往后移：rear+1 , 当 front == rear 时，队列为空
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1时，队列满
注意：front指向的是队列首元素的前一个位置
代码
public class Demo3 {
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(5);
queue.addNum(1);
queue.addNum(2);
queue.addNum(3);
queue.addNum(4);
queue.addNum(5);
System.out.println(queue.getNum());
queue.showQueue();
}
}
class ArrayQueue {
//队列的大小
int maxSize;
//用数组来实现队列
int[] arr;
//指向队列首元素的前一个位置
int front;
//指向队列的尾元素
int rear;
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[this.maxSize];
//front指向队列首元素的前一个位置
front = -1;
rear = -1;
}
public boolean isFull() {
return rear == maxSize - 1;
}
public boolean isEmpty() {
return front == rear;
}
public void addNum(int num) {
if(isFull()) {
System.out.println("队列已满，无法在进行入队操作");
return;
}
//队尾标记后移，指向要放入的元素的位置
rear++;
arr[rear] = num;
}
public int getNum() {
if(isEmpty()) {
throw new RuntimeException("队列为空，无法出队");
}
//队首标记后移，指向队首元素
System.out.print("出队元素是：");
front++;
return arr[front];
}
public void showQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空，无法遍历");
}
System.out.println("遍历队列");
//从front+1开始读取元素
for(int start = front+1; start<=rear; start++) {
System.out.println(arr[start]);
}
}
}
运行结果：
出队元素是：1 遍历队列 2 3 4 5
环形队列
思路：
- front变量指向队首元素，front初值为0
- rear变量指向队尾元素的下一个元素，rear初值为0。规定空出一个位置
- 队列为空的判定条件：front == rear【空】
- 队列为满的判定条件：(rear + 1) % maxSize == front【满】
- 队列中有效元素的个数：(rear + maxSize- front ) % maxSize
- 入队和出队时，都需要让标记对maxSize取模
代码：
public class Demo4 {
public static void main(String[] args) {
ArrayAroundQueue aroundQueue = new ArrayAroundQueue(5);
aroundQueue.addNum(1);
aroundQueue.addNum(2);
aroundQueue.addNum(3);
aroundQueue.addNum(4);
int size = aroundQueue.size();
System.out.println("size:"+size);
aroundQueue.showQueue();
System.out.println(aroundQueue.getNum());
System.out.println(aroundQueue.getNum());
aroundQueue.addNum(5);
aroundQueue.addNum(6);
aroundQueue.showQueue();
aroundQueue.getHead();
}
}
class ArrayAroundQueue {
//队列的大小
int maxSize;
//用数组来实现队列
int[] arr;
//指向队列首元素的前一个位置
int front;
//指向队列的尾元素
int rear;
public ArrayAroundQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int[this.maxSize];
//front指向队列首元素的前一个位置
front = 0;
rear = 0;
}
public boolean isFull() {
return (rear+1)%maxSize == front;
}
public boolean isEmpty() {
return front == rear;
}
public void addNum(int num) {
if(isFull()) {
System.out.println("队列已满，无法在进行入队操作");
return;
}
//直接将数据加入
arr[rear] = num;
//将rear后移，这里必须考虑取模
rear = (rear+1)%maxSize;
}
public int getNum() {
if(isEmpty()) {
throw new RuntimeException("队列为空，无法出队");
}
//队首标记后移，指向队首元素
System.out.print("出队元素是：");
int num = arr[front];
//将front后移，考虑取模
front = (front+1)%maxSize;
return num;
}
public void showQueue() {
if(isEmpty()) {
throw new RuntimeException("队列为空，无法遍历");
}
System.out.println("遍历队列");
//当front + 1 == rear时停止遍历
int start = front;
while(start != rear) {
System.out.println(arr[start]);
//移动到下一个元素
start = (start+1)%maxSize;
}
}
public void getHead() {
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
System.out.println("队首元素为："+arr[front]);
}
//求出当前队列有效数据的个数
public int size() {
return ( rear + maxSize - front) % maxSize;
}
}
运行结果：
size4 遍历队列 1 2 3 4 出队元素是：1 出队元素是：2 遍历队列 3 4 5 6 队首元素为：3
二、链表
1、单向链表
链表介绍
链表是有序的列表，但是它在内存中的存储如下：
特点
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
- 链表的各个节点不一定是连续存储的
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
带头结点的逻辑示意图
实现思路
创建（添加）
- 先创建一个Head头节点，表示单链表的头
- 后面我们每添加一个节点，就放在链表的最后
遍历
- 通过一个辅助变量，来遍历整个链表
有序插入
- 先遍历链表，找到应该插入的位置
- 新的节点.next = temp.next
- 将temp.next = 新的节点
根据某个属性节点修改值
- 先遍历节点，找到修改的位置
- 如果未找到修改节点，则不修改
删除某个节点
- 先遍历节点，找到要删除节点的前一个节点temp
- temp.next = temp.next.next
- 被删除的节点将不会有其它引用指向，会被垃圾回收机制回收
求倒数第n个节点的信息
- 遍历链表，求出链表的有效长度length（不算头结点）
- 遍历链表到第length-n的节点
翻转链表
创建一个新的头结点，作为新链表的头
-
从头遍历旧链表，将遍历到的节点插入新链表的头结点之后
-
注意需要用到
两个暂存节点
- 一个用来保存正在遍历的节点
- 一个用来保存正在遍历节点的下一个节点
逆序打印
- 遍历链表，将遍历到的节点入栈 Stack
- 遍历完后，进行出栈操作，同时打印出栈元素
代码：
public class lianbiao {
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.traverseNode();
System.out.println();
//创建学生节点，并插入链表
StudentNode student1 = new StudentNode(1, "Nyima");
StudentNode student3 = new StudentNode(3, "Lulu");
linkedList.addNode(student1);
linkedList.addNode(student3);
linkedList.traverseNode();
System.out.println();
//按id大小插入
System.out.println("有序插入");
StudentNode student2 = new StudentNode(0, "Wenwen");
linkedList.addByOrder(student2);
linkedList.traverseNode();
System.out.println();
//按id修改学生信息
System.out.println("修改学生信息");
student2 = new StudentNode(1, "Hulu");
linkedList.changeNode(student2);
linkedList.traverseNode();
System.out.println();
//根据id删除学生信息
System.out.println("删除学生信息");
student2 = new StudentNode(1, "Hulu");
linkedList.deleteNode(student2);
linkedList.traverseNode();
System.out.println();
//获得倒数第几个节点
System.out.println("获得倒数节点");
System.out.println(linkedList.getStuByRec(2));
System.out.println();
//翻转链表
System.out.println("翻转链表");
SingleLinkedList newLinkedList = linkedList.reverseList();
newLinkedList.traverseNode();
System.out.println();
//倒叙遍历链表
System.out.println("倒序遍历链表");
newLinkedList.reverseTraverse();
}
}
/**
* 创建链表
*/
class SingleLinkedList {
//头节点，防止被修改，设置为私有的
private StudentNode head = new StudentNode(0, "");
/**
* 添加节点
* @param node 要添加的节点
*/
public void addNode(StudentNode node) {
//因为头节点不能被修改，所以创建一个辅助节点
StudentNode temp = head;
//找到最后一个节点
while (true) {
//temp是尾节点就停止循环
if(temp.next == null) {
break;
}
//不是尾结点就向后移动
temp = temp.next;
}
//现在temp是尾节点了，再次插入
temp.next = node;
}
/**
* 遍历链表
*/
public void traverseNode() {
System.out.println("开始遍历链表");
if(head.next == null) {
System.out.println("链表为空");
}
//创建辅助节点
StudentNode temp = head.next;
while(true) {
//遍历完成就停止循环
if(temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
/**
* 按id顺序插入节点
* @param node
*/
public void addByOrder(StudentNode node) {
//如果没有首节点，就直接插入
if(head.next == null) {
head.next = node;
return;
}
//辅助节点，用于找到插入位置和插入操作
StudentNode temp = head;
//节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移
while (temp.next!=null && temp.next.id < node.id) {
temp = temp.next;
}
//如果temp的下一个节点存在，则执行该操作
//且插入操作，顺序不能换
if(temp.next != null) {
node.next = temp.next;
}
temp.next = node;
}
/**
* 根据id来修改节点信息
* @param node 修改信息的节点
*/
public void changeNode(StudentNode node) {
if(head == null) {
System.out.println("链表为空，请先加入该学生信息");
return;
}
StudentNode temp = head;
//遍历链表，找到要修改的节点
while (temp.next!= null && temp.id != node.id) {
temp = temp.next;
}
//如果temp已经是最后一个节点，判断id是否相等
if(temp.id != node.id) {
System.out.println("未找到该学生的信息，请先创建该学生的信息");
return;
}
//修改学生信息
temp.name = node.name;
}
/**
* 根据id删除节点
* @param node 要删除的节点
*/
public void deleteNode(StudentNode node) {
if(head.next == null) {
System.out.println("链表为空");
return;
}
StudentNode temp = head.next;
//遍历链表，找到要删除的节点
if(temp.next!=null && temp.next.id!=node.id) {
temp = temp.next;
}
//判断最后一个节点的是否要删除的节点
if(temp.next.id != node.id) {
System.out.println("请先插入该学生信息");
return;
}
//删除该节点
temp.next = temp.next.next;
}
/**
* 得到倒数的节点
* @param index 倒数第几个数
* @return
*/
public StudentNode getStuByRec(int index) {
if(head.next == null) {
System.out.println("链表为空!");
}
StudentNode temp = head.next;
//用户记录链表长度，因为head.next不为空，此时已经有一个节点了
//所以length初始化为1
int length = 1;
while(temp.next != null) {
temp = temp.next;
length++;
}
if(length < index) {
throw new RuntimeException("链表越界");
}
temp = head.next;
for(int i = 0; i<length-index; i++) {
temp = temp.next;
}
return temp;
}
/**
* 翻转链表
* @return 反转后的链表
*/
public SingleLinkedList reverseList() {
//链表为空或者只有一个节点，无需翻转
if(head.next == null || head.next.next == null) {
System.out.println("无需翻转");
}
SingleLinkedList newLinkedList = new SingleLinkedList();
//给新链表创建新的头结点
newLinkedList.head = new StudentNode(0, "");
//用于保存正在遍历的节点
StudentNode temp = head.next;
//用于保存正在遍历节点的下一个节点
StudentNode nextNode = temp.next;
while(true) {
//插入新链表
temp.next = newLinkedList.head.next;
newLinkedList.head.next = temp;
//移动到下一个节点
temp = nextNode;
nextNode = nextNode.next;
if(temp.next == null) {
//插入最后一个节点
temp.next = newLinkedList.head.next;
newLinkedList.head.next = temp;
head.next = null;
return newLinkedList;
}
}
}
public void reverseTraverse() {
if(head == null) {
System.out.println("链表为空");
}
StudentNode temp = head.next;
//创建栈，用于存放遍历到的节点
Stack<StudentNode> stack = new Stack<>();
while(temp != null) {
stack.push(temp);
temp = temp.next;
}
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
/**
* 定义节点
*/
class StudentNode {
int id;
String name;
//用于保存下一个节点的地址
StudentNode next;
public StudentNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "StudentNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
输出：
开始遍历链表
链表为空
开始遍历链表
StudentNode{id=1, name='Nyima'}
StudentNode{id=3, name='Lulu'}
有序插入
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=1, name='Nyima'}
StudentNode{id=3, name='Lulu'}
修改学生信息
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=1, name='Hulu'}
StudentNode{id=3, name='Lulu'}
删除学生信息
开始遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=3, name='Lulu'}
获得倒数节点
StudentNode{id=0, name='Wenwen'}
翻转链表
开始遍历链表
StudentNode{id=3, name='Lulu'}
StudentNode{id=0, name='Wenwen'}
倒序遍历链表
StudentNode{id=0, name='Wenwen'}
StudentNode{id=3, name='Lulu'}
Process finished with exit code 0
2、双向链表
实现思路
遍历
- 和单向链表的遍历相同，只是可以向前也可以向后查找
添加 默认添加到双向链表的最后
- 先找到双向链表的最后这个节点
- temp.next = newHeroNode;
- newHeroNode.pre = temp;
修改
- 和单向链表的修改相同
删除
- 使用temp来保存要删除的节点
- temp.pre.next指向temp.next
- temp.next.pre指向temp.pre
代码：
public class shuangxianglianbiao {
public static void main(String[] args) {
BidirectionalList bidirectionalList = new BidirectionalList();
bidirectionalList.addNode(new PersonNode(1, "Nyima"));
bidirectionalList.addNode(new PersonNode(2, "Lulu"));
bidirectionalList.traverseNode();
System.out.println();
System.out.println("修改节点信息");
bidirectionalList.changeNode(new PersonNode(2, "Wenwen"));
bidirectionalList.traverseNode();
System.out.println();
//删除节点
System.out.println("删除节点");
bidirectionalList.deleteNode(new PersonNode(1, "Nyima"));
bidirectionalList.traverseNode();
}
}
class BidirectionalList {
private final PersonNode head = new PersonNode(-1, "");
/**
* 判断双向链表是否为空
* @return 判空结果
*/
public boolean isEmpty() {
return head.next == null;
}
/**
* 添加将诶点
* @param node 要被添加的节点
*/
public void addNode(PersonNode node) {
PersonNode temp = head;
if(temp.next != null) {
temp = temp.next;
}
//插入在最后一个节点的后面
temp.next = node;
node.front = temp;
}
public void traverseNode() {
System.out.println("遍历链表");
if (isEmpty()) {
System.out.println("链表为空");
return;
}
PersonNode temp = head.next;
while(temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
/**
* 修改节点信息
* @param node 要修改的节点
*/
public void changeNode(PersonNode node) {
if(isEmpty()) {
System.out.println("链表为空");
return;
}
PersonNode temp = head.next;
//用于判定是否做了修改
boolean flag = false;
while (temp != null) {
if(temp.id == node.id) {
//匹配到节点，替换节点
temp.front.next = node;
node.next = temp.next;
flag = true;
}
temp = temp.next;
}
if(!flag) {
System.out.println("未匹配到改人信息");
}
}
/**
* 删除节点
* @param node 要删除的节点
*/
public void deleteNode(PersonNode node) {
if(isEmpty()){
System.out.println("链表为空");
return;
}
PersonNode temp = head.next;
//查看是否删除成功
boolean flag = false;
while(temp != null) {
if(temp.id == node.id) {
temp.front.next = temp.next;
temp.next = null;
flag = true;
}
temp = temp.next;
}
if(!flag) {
System.out.println("未找到该节点");
}
}
}
class PersonNode {
int id;
String name;
//指向下一个节点
PersonNode next;
//指向前一个节点
PersonNode front;
public PersonNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "PersonNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
运行结果：
遍历链表
PersonNode{id=1, name='Nyima'}
PersonNode{id=2, name='Lulu'}
修改节点信息
遍历链表
PersonNode{id=1, name='Nyima'}
PersonNode{id=2, name='Wenwen'}
删除节点
遍历链表
PersonNode{id=2, name='Wenwen'}
Process finished with exit code 0
3、循环链表
循环链表
单链表的尾节点指向首节点，即可构成循环链表
遍历环形链表
- 先让一个辅助指针（变量）curBoy,指向first节点
- 然后通过一个while循环遍历该环形链表即可 curBoy.next = first结束
约瑟夫环
N个人围成一圈，从第S个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉，求出被杀顺序
- 例如N=6，M=5，S=1，被杀掉的顺序是：6，4，5，2，1，3
大致思路
- 遍历链表找到指定位置的节点
- 用一个front保存指定节点的前一个节点，方便删除
- 当count==time时，删除此时正在遍历的节点，放入数组中，并将count的值初始化
- 用一个变量loopTime记录已经出圈了几个人，当其等于length时则是最后一个节点，直接放入数组并返回数即可
代码:
public class yuesefuhuan {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);
circleSingleLinkedList.showBoy();
//小孩出圈 表示从第1个小孩开始数数 数2下 最初有5个小孩在圈中
circleSingleLinkedList.countBoy(1, 2, 5);
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList {
//创建一个first节点,当前没有编号
private Boy first = null;
//添加一个小孩节点,构建成一个环形的链表
public void addBoy(int nums) {
//nums做一个数据校验
if (nums < 1) {
System.out.println("nums的值不正确");
}
Boy curBoy = null;//辅助指针,帮助构建环形链表
//用for来创建我们的环形链表
for (int i = 1; i<=nums; i++) {
//根据编号创建小孩节点
Boy boy = new Boy(i);
//如果是第一个小孩
if (i == 1) {
first = boy;
first.setNext(first);//构成环
curBoy = first;//让curBoy指向第一个小孩
} else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
//遍历当前环形链表
public void showBoy() {
//判断链表是否为空
if (first == null) {
System.out.println("没有任何小孩~~~");
return;
}
//因为first不能动,因此我们仍然使用一个辅助指针来完成遍历
Boy curBoy = this.first;
while (true) {
System.out.printf("小孩的编号 %d \n", curBoy.getNo());
if (curBoy.getNext() == first) {//说明已经遍历完毕
break;
}
curBoy = curBoy.getNext();//curBoy后移
}
}
/**
* 根据用户的输入,计算出小孩出圈的顺序
* @param startNo 表示从第几个小孩开始数数
* @param countNum 表示数几下
* @param nums 表示最初有几个小孩在圈中
*/
public void countBoy(int startNo, int countNum, int nums) {
//先对数据进行校验
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("参数输入有误,请重新输入");
return;
}
//因为first不能动,因此我们仍然使用一个辅助指针来完成遍历
Boy helper = this.first;
while (true) {
if (helper.getNext() == first) {//说明已经遍历完毕
break;
}
helper = helper.getNext();//curBoy后移
}
//小孩报数前, 先让first 和 helper 移动k-1次
for (int j = 0; j < startNo - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时,让first 和 helper 移动m-1次,然后出圈
//这里是一个循环操作,知道圈中只有一个节点
while (true) {
if (helper == first) {//说明圈中只有一个节点
break;
}
//让first 和 helper 指针同时的移动countNum次
for (int j = 0; j < countNum - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
System.out.printf("小孩 %d 出圈\n", first.getNo());
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中小孩编号 %d \n", first.getNo());
}
}
//创建一个Boy类，表示一个节点
class Boy {
private int no;//编号
private Boy next;//指向下一个节点,默认null
public Boy(int no) {
this.no = no;
}
public Boy(int no, Boy next) {
this.no = no;
this.next = next;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
输出结果:
小孩的编号 1 小孩的编号 2 小孩的编号 3 小孩的编号 4 小孩的编号 5 小孩 2 出圈 小孩 4 出圈 小孩 1 出圈 小孩 5 出圈 最后留在圈中小孩编号 3 Process finished with exit code 0
三、栈
1、定义
- 栈是一个先入后出的有序列表
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
- 最先放入的元素在栈底，且最后出栈。最后放入的元素在栈顶，且最先出栈
2、应用场景
- 子程序递归调用。如JVM中的虚拟机栈
- 表达式转换（中缀转后缀）与求值
- 二叉树的遍历
- 图的深度优先遍历
3、实现
用数组实现
思路
- 定义top表示栈顶，初始值为-1
- 入栈的操作，先让top++，再放入数组stack[top] = data;
- 出栈操作，先取出元素 int value = stack[top]，再让top--
- top == -1时，栈空
- top == maxSize-1时，栈满
代码:
public class zhan {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5);
//压栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
//出栈
System.out.println(stack.pop());
stack.list();
}
}
class ArrayStack {
private final int maxSize;
int[] stack;
private int top;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int [this.maxSize];
top = -1;
}
private boolean isEmpty() {
return top == -1;
}
private boolean isFull() {
return top == maxSize-1;
}
public void push(int i) {
if(isFull()) {
throw new StackOverflowError("栈满");
}
//压栈
top++;
stack[top] = i;
}
public int pop() {
if(isEmpty()) {
throw new EmptyStackException();
}
int retNum = stack[top];
top--;
return retNum;
}
//显示栈的情况[遍历栈], 遍历时需要从栈顶开始显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空,没有数据~~~");
return;
}
//需要从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d] = %d \n", i, stack[i]);
}
}
}
运行结果:
5 stack[3] = 4 stack[2] = 3 stack[1] = 2 stack[0] = 1 Process finished with exit code 0
4、应用
表达式求值
思路
- 准备一个索引index来帮助我们遍历表达式
- 如果index位置上的元素是一个数字，就直接入栈
- 如果index位置上的元素是一个符号
- 如果符号栈为空，直接入栈
- 如果符号栈不为空
- index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，并将index位置上的符号压入符号栈
- index位置上的符号的优先级大于符号栈栈顶符号的优先级，则将该符号压入符号栈
- 当表达式遍历完毕后，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
- 最终数栈中只有一个值，这个值便是运算结果
- 注意：
- 读取的是字符，所以存入数字前需要减去0的ASCII码
- 如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈
代码:
public class Calculator {
public static void main(String[] args) {
String expression = "2+30*6-2";
//创建两个栈 数栈和符号栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//索引，用来读取字符串中的元素
int index = 0;
//保存读取到的数字和符号
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
int ch = ' ';//将每次扫描得到的char保存到ch
String keepNum = "";//用于拼接多位数
//开始循环扫描expression
while (true) {
//一次得到expression中的每一个字符
ch = expression.substring(index, index + 1).charAt(0);
//判断ch是什么 然后做相应处理
if (operStack.isOper((char) ch)) {//如果是运算符
//判断当前的符号栈是否为空
if (!operStack.isEmpty()) {
//如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
//再从符号栈中pop出一个符号,进行计算,将运算结果入数栈,然后将当前的操作符入符号栈
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, (char) oper);
//把运算的结果入数栈
numStack.push(res);
//然后把当前的操作符入符号栈
operStack.push(ch);
} else {
//如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈
operStack.push(ch);
}
} else {
//如果为空就直接入符号栈
operStack.push(ch);
}
} else {
//如果是数 直接入数栈
//numStack.push(ch - 48);
//处理多位数
keepNum += ch-48;
//如果ch已经是expression的最后一位,就直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
} else {
//判断下一个字符是不是数字,是数字则继续扫描,是运算符则入栈
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//如果后一位是运算符,则入栈 keepNum = "1" 或者 "123"
numStack.push(Integer.parseInt(keepNum));
//keepNum清空
keepNum = "";
}
}
}
//让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, (char) oper);
numStack.push(res);//入栈
}
//将数栈的最后数pop出 就是结果
int res2 = numStack.pop();
System.out.println("表达式:"+expression +"="+res2);
}
}
//先创建一个栈
class ArrayStack2 {
private final int maxSize;
int[] stack;
private int top;
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int [this.maxSize];
top = -1;
}
//返回当前栈顶的值
public int peek() {
return stack[top];
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == maxSize-1;
}
public void push(int i) {
if(isFull()) {
throw new StackOverflowError("栈满");
}
//压栈
top++;
stack[top] = i;
}
public int pop() {
if(isEmpty()) {
throw new EmptyStackException();
}
int retNum = stack[top];
top--;
return retNum;
}
//显示栈的情况[遍历栈], 遍历时需要从栈顶开始显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空,没有数据~~~");
return;
}
//需要从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d] = %d \n", i, stack[i]);
}
}
//返回运算符的优先级,优先级是程序员来确定,优先级使用数字表示
//数字越大 优先级越高
public int priority(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, char oper) {
int res = 0;//res用于存放计算的结果
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}
运行结果:
表达式:2+30*6-2=180
5、中缀转后缀
后缀表达式运算方法
- 从左向右读取表达式
- 遇到数字就压入栈中
- 遇到运算符就弹出栈顶和次顶元素。用次顶元素 运算符 栈顶元素，并将运算结果压入栈中，直到栈为空，最终结果就是运算结果
设计
中缀表达式转后缀表达式
-
从左向右读取中缀表达式，并且创建栈s和队列q
-
如果读到的元素的数字，就直接入队放入q中
-
如果读到的是
运算符
（运算符判定）
- 如果s为空，则将该运算符压入s
- 如果s不为空
- 如果该运算符为左括号，则直接压入s
- 如果该运算符为右括号，则将s中的元素依次出栈并入队到q中，直到遇见左括号为止（括号不放入q中）
- 如果该运算符的优先级高于s栈顶的运算符，则将该元素压入s
- 如果该运算符的优先级小于等于s栈顶的运算符，则弹出s栈顶的元素，并将其放入q中，该运算符重新判定入栈操作（运算符判定步骤）
-
如果中缀表达式已经读取完毕，则将s中的元素依次出栈，放入q中
-
q中的元素依次出队，该顺序即为后缀表达式
代码:
public class PolandNotation {
public static void main(String[] args) {
//完成将一个中缀表达式转成后缀表达式的功能
//1+((2+3)*4)-5 ==> 1 2 3 + 4 * + 5 -
//1.将 1+((2+3)*4)-5 放入list中 ArrayList[1,+,(,(,2,+,3,),*,4,),-,5]
//2.中缀转后缀 ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList [1,2,3,+,4,*,+,5,-]
String expression = "1+((2+3)*4)-5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println("中缀表达式对应的list:"+infixExpressionList);
List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
System.out.println("后缀表达式对应的list:"+suffixExpressionList);
System.out.println("计算结果:"+calculate(suffixExpressionList));
//先定义一个逆波兰表达式
//(3+4)*5-6 => 3 4 + 5 * 6 - =>29
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);
}
//将中缀表达式转成对应的list
public static List<String> toInfixExpressionList(String s) {
//定义list 存放中缀表达式对应的内容
ArrayList<String> list = new ArrayList<>();
int i = 0;//这时是一个指针,用于遍历中缀表达式字符串
String str;//对应多位数的拼接
char c;//每遍历到一个字符 就放入到c
do {
//如果c是一个非数字 需要接入到list
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
list.add("" + c);
i++;
} else {//如果是一个数 需要考虑多位数
str = "";//先将str置成"" '0'[48]->'9'[57]
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
str += c;//拼接
i++;
}
list.add(str);
}
} while (i < s.length());
return list;
}
//中缀转后缀 ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] => ArrayList [1,2,3,+,4,*,+,5,-]
public static List<String> parseSuffixExpressionList(List<String> ls) {
//定义两个栈
Stack<String> s1 = new Stack<>();
//因为s2栈没有pop操作而且后面还需逆序输出 所以直接用队列存储
ArrayList<String> s2 = new ArrayList<>();
//遍历
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();//将"("弹出s1栈
} else {
//当item的优先级小于等于s1栈顶运算符,将s1栈顶的运算符弹出并加入到s2中,再与s1中新的栈顶运算符比较
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
//还需要将item压入栈
s1.push(item);
}
}
//将s1中剩余的运算符依次弹出并加入s2
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;//因为是存放到list,因此按顺序输出就是对应的后缀表达式的list
}
//将一个逆波兰表达式, 依次将数据和运算符 放入到ArrayList中
public static List<String> getListString(String suffixExpression) {
//将suffixExpression分割
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<>();
for (String s : split) {
list.add(s);
}
return list;
}
//完成对逆波兰表达式的运算
/**
* 1.从左至右扫描,将3和4压入堆栈
* 2.遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈
* 3.将5入栈
* 4.接下来是x运算符, 因此弹出5和7, 计算出7x5等于35, 再将35入栈
* 5.将6入栈;
* 6.最后是-运算符,计算出35-6的值, 即29, 由此得出最终结果
* @return
*/
public static int calculate(List<String> ls) {
Stack<String> stack = new Stack<>();
//遍历ls
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 (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("*")) {
res = num1 * num2;
} else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
//把res 入栈
stack.push("" + res);
}
}
//最后留在stack中的数据是运算结果
return Integer.parseInt(stack.pop());
}
}
//编写一个Operation 可以返回一个运算符对应的优先级
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;
}
}
运行结果:
中缀表达式对应的list:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 不存在该运算符 不存在该运算符 后缀表达式对应的list:[1, 2, 3, +, 4, *, +, 5, -] 计算结果:16 rpnList=[3, 4, +, 5, *, 6, -] 计算的结果是:29 Process finished with exit code 0
四、递归
1、概念
递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。并且递归用到了虚拟机栈
2、能解决的问题
数学问题
- 八皇后问题
- 汉诺塔
- 求阶乘
- 迷宫问题
- 球和篮子
各种排序算法
3、规则
- 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
- 方法的变量是独立的，不会相互影响的
- 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据
- 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError
- 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕
4、迷宫问题
思路
- 用一个二维矩阵代表地图
- 1代表边界
- 0代表未做过该地点
- 2代表走过且能走得通
- 3代表走过但走不通
- 设置起点和终点以及每个地点的行走策略
- 行走策略指在该点所走的方向的顺序，如 下->右->上->左（调用寻找路径的方法，使用递归）
- 每次行走时假设该点能够走通，然后按照策略去判断，如果所有策略判断后都走不通，则该点走不通
图解
初始地图
行走路径
策略：下右上左
代码:
public class migong {
public static void main(String[] args) {
//得到地图
int length = 8;
int width = 7;
int[][] map = getMap(length, width);
//设置一些障碍
map[3][1] = 1;
map[3][2] = 1;
//打印地图
System.out.println("地图如下");
for(int i=0; i<length; i++) {
for(int j=0; j<width; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
//使用递归回溯给小球找路
getWay(map,1,1);
//输出新的地图 小球走过并标识过的递归
System.out.println("小球走过,并标识过的地图情况:");
for(int i=0; i<length; i++) {
for(int j=0; j<width; j++) {
System.out.print(map[i][j]+" ");
}
System.out.println();
}
}
/**
* 创建地图
* @param length 地图的长
* @param width 地图的宽
* @return 创建好的地图
*/
public static int[][] getMap(int length, int width) {
int[][] map = new int[length][width];
//先将第一行和最后一行设置为1（边界）
for(int i=0; i<width; i++) {
map[0][i] = 1;
map[length-1][i] = 1;
}
//再将第一列和最后一列设置为1
for(int i=0; i<length; i++) {
map[i][0] = 1;
map[i][width-1] = 1;
}
return map;
}
/**
* 1.map表示地图
* 2.i j 表示从地图的哪个位置开始出发(1,1)
* 3.如果小球能到map[6][5] 位置, 则说明通路找到
* 4.约定: 当map[i][j] 为0 表示该点没有走过 当为1表示墙; 2表示通路可以走; 3表示该点已经走过,但是走不通
* 5.在走迷宫时,需要确定一个策略(方法) 下->右->上->左, 如果该点走不通再回溯
* @param map 表示地图
* @param i 从哪个位置开始找
* @param j
* @return 如果找到通路返回true, 否则返回false
*/
public static boolean getWay(int[][] map, int i, int j) {
if (map[6][5] == 2) {//通路已经找到OK
return true;
} else {
if (map[i][j] == 0) {//如果当前点还没有走过
//按照策略 下->右->上->左 走
map[i][j] = 2;//假定该点是可以走通
if (getWay(map, i+1, j)) {
return true;
} else if (getWay(map, i, j+1)) {
return true;
} else if (getWay(map, i-1, j)) {
return true;
} else if (getWay(map, i, j-1)) {
return true;
} else {
//说明该点走不通 是死路
map[i][j] = 3;
return false;
}
} else { //如果map[i][j] != 0, 可能是1 2 3
return false;
}
}
}
}
输出:
地图如下 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 小球走过,并标识过的地图情况: 1 1 1 1 1 1 1 1 2 0 0 0 0 1 1 2 2 2 0 0 1 1 1 1 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 0 0 1 1 0 0 2 2 2 1 1 1 1 1 1 1 1 Process finished with exit code 0
5、八皇后问题
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在 8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法(92)。
思路
- 将第一个皇后放在第一行第一列
- 将第二个皇后放在第二行第一列，判断是否会和其他皇后相互攻击，若会相互攻击，则将其放到第二列、第三列、第四列…直到不会相互攻击为止
- 将第三个皇后放在第三行第一列，判断是否会和其他皇后相互攻击，若会相互攻击，则将其放到第二列、第三列、第四列…直到不会相互攻击为止，并以此类推，在摆放的过程中，有可能会改动前面所放的皇后的位置
- 当得到一个正确的解时，就会回溯到上一行，由此来找出第一个皇后在第一行第一列的所有解
- 再将第一个皇后放到第一行第二列，并重复以上四个步骤
- 注意：
- 棋盘本身应该是用二维数组表示，但是因为皇后所在的行数是固定的，所以可以简化为用一个一维数组来表示。arr[8] = {0,4,7,5,2,4,1,3}//对应arr下标表示第几行，即第几个皇后，arr[i] = val，val表示第i+1个皇后，放在第i+1行的第val+1列
- 数组下标代表皇后所在行数，所以判断是否在同一行列斜线上时，只需要判断是否在同一列和同一斜线上即可
- 是否同列判断：值是否相同
- 是否同一斜线：行号-行号是否等于列号-列号，且列号相减要取绝对值
代码:
public class Queue8 {
//定义一个max表示有多少个皇后
int max = 8;
//定义数组array 保存皇后放置位置的结果 比如:arr[8] = {0,4,7,5,2,4,1,3}
int[] array = new int[max];
static int count = 0;
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.println("一共"+count+"种");
}
//编写一个方法 放置第n个皇后
//特别注意 check是每一次递归时,进入到check中都有for (int i = 0;i < max; i++),因此会有回溯
private void check(int n) {
if (n == max) {//n=8 就是8个皇后就已经放好了
print();
return;
}
//依次放入皇后,并判断是否冲突
for (int i = 0;i < max; i++) {
//先判断当前这个皇后n,放到该行的第一列
array[n] = i;
//判断当放置第n个皇后到i列时,是否冲突
if (judge(n)) {//不冲突
//接着放n+1个皇后,即开始递归
check(n+1);
}
}
//如果冲突,就继续执行array[n] = i,即将第n个皇后,放置在本行的后移的一个位置
}
/**
* 查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
* @param n
* @return
*/
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
//1.array[i] == array[n] 判断第n个皇后是否和前面第i个皇后在同一列
//2.Math.abs(n-1) == Math.abs(array[n] - array[i])判断第n个皇后是否和前面第i个皇后在同一斜线
//n = 1 放置第2列1 n = 1 array[1] = 1
//Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1 - 0) = 1
//3.判断在同一行 没必要,n每次都在递增
if (array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
//皇后位置输出
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
五、排序
1、常见的排序算法
- 内部排序: 将需要处理的所有数据都加载到内部存储器(内存)中进行排序
- 外部排序法: 无法全部加载到内存中, 需要借助外部存储(文件等)进行排序
2、算法的时间复杂度
时间频度和时间复杂度
时间频度T(n)
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度O(n)
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)
- 对于不是只有常数的时间复杂度忽略时间频度的系数、低次项常数
- 对于只有常数的时间复杂度，将常数看为1
常见的时间复杂度
常数阶 O(1)
int i = 1; i++;Copy
无论代码执行了多少行，只要没有循环等复杂的结构，时间复杂度都是O(1)
对数阶O(log2n)
while(i<n) {
i = i*2;
}Copy
此处i并不是依次递增到n，而是每次都以倍数增长。假设循环了x次后i大于n。则2x = n，x=log2n
线性阶O(n)
for(int i = 0; i<n; i++) {
i++;
}Copy
这其中，循环体中的代码会执行n+1次，时间复杂度为O(n)
线性对数阶O(nlog2n)
for(int i = 0; i<n; i++) {
j = 1;
while(j<n) {
j = j*2;
}
}Copy
此处外部为一个循环，循环了n次。内部也是一个循环，但内部f循环的时间复杂度是log2n
所以总体的时间复杂度为线性对数阶O(nlog2n)
平方阶O(n2)
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
//循环体
}
}Copy
立方阶O(n3)
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
for(int k = 0; k<n; k++) {
//循环体
}
}
}Copy
可以看出平方阶、立方阶的复杂度主要是否循环嵌套了几层来决定的
k次方阶O(n^k)
指数阶O(2^n)
常见的算法时间复杂度由小到大依次为:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(n^k) < O(2^n), 随着问题规模n的不断增大, 上述时间复杂度不断增大, 算法的执行效率越低, 应尽可能避免使用指数阶的算法
3、排序算法的时间复杂度
| 排序算法 | 平均时间 | 最差时间 | 稳定性 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) | n较小时好 |
| 交换排序 | O(n2) | O(n2) | 不稳定 | O(1) | n较小时好 |
| 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) | n较小时好 |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已有序时好 |
| 基数排序 | O(n*k) | O(n*k) | 稳定 | O(n) | 二维数组（桶）、一维数组（桶中首元素的位置） |
| 希尔排序 | O(nlogn) | O(ns)(1<s<2) | 不稳定 | O(1) | s是所选分组 |
| 快速排序 | O(nlogn) | O(n2) | 不稳定 | O(logn) | n较大时好 |
| 归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n较大时好 |
| 堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n较大时好 |
4、冒泡排序
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 一共进行了数组元素个数-1次大循环，且每次大循环中需要比较的元素越来越少。
- 优化：如果在某次大循环，发现没有发生交换，则证明已经有序。
代码:
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {3,9,-1,10,20};
//冒泡排序
int temp = 0;
boolean flag = false;//标识变量 表示是否进行过交换
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] < arr[j+1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第"+i+"趟排序后的:");
System.out.println(Arrays.toString(arr));
if (!flag) {
break;//在一趟排序中 一次交换都没有发生过
} else {
flag = false;//重置flag!!! 进行下次判断
}
}
}
}
输出结果:
第1趟排序后的: [9, 3, 10, 20, -1] 第2趟排序后的: [9, 10, 20, 3, -1] 第3趟排序后的: [10, 20, 9, 3, -1] 第4趟排序后的: [20, 10, 9, 3, -1] Process finished with exit code 0
5、选择排序
算法步骤
- 遍历整个数组，找到最小（大）的元素，放到数组的起始位置。
- 再遍历剩下的数组，找到剩下元素中的最小（大）元素，放到数组的第二个位置。
- 重复以上步骤，直到排序完成。
- 一共需要遍历数组元素个数-1次，当找到第二大（小）的元素时，可以停止。这时最后一个元素必是最大（小）元素。
代码:
public class SelectSort {
public static void main(String[] args) {
int arr[] = {1,10,5,6,4,9,3};
//选择排序
for (int i = 0; i < arr.length-1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i+1; j <arr.length; j++) {
if (min > arr[j]) {
min = arr[j];//重置min
minIndex = j;//重置minIndex
}
}
//将最小值放到arr[i]位置
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
System.out.println("第"+(i+1)+"趟排序后的:");
System.out.println(Arrays.toString(arr));
}
}
}
输出:
第1趟排序后的: [1, 10, 5, 6, 4, 9, 3] 第2趟排序后的: [1, 3, 5, 6, 4, 9, 10] 第3趟排序后的: [1, 3, 4, 6, 5, 9, 10] 第4趟排序后的: [1, 3, 4, 5, 6, 9, 10] 第5趟排序后的: [1, 3, 4, 5, 6, 9, 10] 第6趟排序后的: [1, 3, 4, 5, 6, 9, 10] Process finished with exit code 0
6、插入排序
算法步骤
- 将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
代码:
public class InsertSort {
public static void main(String[] args) {
int arr[] = {344,101,119,1};
for (int i=1; i < arr.length; i++) {
//定义待插入的数
int insertVal = arr[i];
//arr[1]的前面这个数的下标
int insertIndex = i-1;
//给insetVal找到插入的位置
//1.保证insertIndex >= 0 保证给insertVal找插入位置,不越界
//2.insertVal <arr[insertIndex] 待插入的数,还没有找到插入位置
//3.就需将arr[insertIndex]后移
while(insertIndex >= 0 && insertVal <arr[insertIndex]) {
arr[insertIndex+1] = arr[insertIndex];
insertIndex--;
}
//退出while循环,说明插入位置找到 insertIndex+1
if (insertIndex+1 != i) {
arr[insertIndex+1] = insertVal;
}
System.out.println("第"+i+"趟排序后的:");
System.out.println(Arrays.toString(arr));
}
}
}
运行结果:
第1趟排序后的: [101, 344, 119, 1] 第2趟排序后的: [101, 119, 344, 1] 第3趟排序后的: [1, 101, 119, 344] Process finished with exit code 0
7、希尔排序
回顾：插入排序存在的问题
当最后一个元素为整个数组的最小元素时，需要将前面的有序数组中的每个元素都向后移一位，这样是非常花时间的。
所以有了希尔排序来帮我们将数组从无序变为整体有序再变为有序。
算法步骤
- 选择一个增量序列t1（一般是数组长度/2），t2（一般是一个分组长度/2），……，tk，其中 ti > tj, tk = 1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
示意图
代码:
public static void main(String[] args) {
int arr[] = {1,10,5,6,4,9,3,22};
//希尔排序 移位法
//增量gap 并逐步的缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第gap个元素,逐步对其所在的组进行直接插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动
arr[j] = arr[j - gap];
j -= gap;
}
if (j != i) {
arr[j] = temp;
}
}
System.out.println("每次排序后的:");
System.out.println(Arrays.toString(arr));
}
}
}
运行结果:
每次排序后的: [1, 9, 3, 6, 4, 10, 5, 22] 每次排序后的: [1, 6, 3, 9, 4, 10, 5, 22] 每次排序后的: [1, 3, 4, 5, 6, 9, 10, 22] Process finished with exit code 0
8、快速排序
算法步骤
- 从数列中挑出一个元素，称为 “基准”（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
代码:
public class QuickSort {
public static void main(String[] args) {
int arr[] = {-9,78,0,23,-567,70};
quickSort(arr, 0, arr.length - 1);
System.out.println("arr:"+ Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
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右边的值全部大于等于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;
}
}
//if 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);
}
}
}
输出结果:
arr:[-567, -9, 0, 23, 70, 78] Process finished with exit code 0
9、归并排序
算法步骤
归并排序用到了分而治之的思想，其难点是治
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复上一步 直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
代码:
public class MergetSort {
public static void main(String[] args) {
int arr[] = {8,4,5,7,1,3,6,2};
int temp[] = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
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数组的当前索引
//(1)
//先把左右两边(有序)的数据按照规则填充到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;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
运行结果:
归并排序后:[1, 2, 3, 4, 5, 6, 7, 8] Process finished with exit code 0
10、基数排序
算法步骤
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 从最低位排序一直到最高位（个位->十位->百位->…->最高位）排序完成以后, 数列就变成一个有序序列
- 需要我们获得最大数的位数
- 可以通过将最大数变为String类型，再求得它的长度即可
按照个位，放到对应的桶中
依次取出，同一个桶中有多个元素的，先放入的先取出
再按照十位，放到对应的桶中，个位数前面补0
再依次取出桶中元素
再按照百位，放到对应的桶中，个位数和十位数前面补0
再依次取出桶中元素
再按照千位，放到对应的桶中，个位数、十位数和百位数前面补0
当所有的数都在0号桶时，依次取出元素，这时顺序即为排好后的顺序
代码:
public class RadixSort {
public static void main(String[] args) {
int arr[] = {53,3,542,748,14,214};
raidxSort(arr);
}
//基数排序方法
public static void raidxSort(int arr[]) {
//得到数组中最大的数的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
//得到最大位数
int maxLength = (max + "").length();
//第1轮(针对每个元素的个位进行排序处理)
//定义一个二维数组表示10个桶,没个桶就是一个二维数组
//1.二维数组包含10个一维数组
//2.为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为arr.length
//3.基数排序是使用空间换时间的经典算法
int [][] bucket = new int[10][arr.length];
//为了记录每个桶中实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
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个桶
for (int l = 0; l < bucketElementCounts[k]; l++) {
//取出元素放入到arr
arr[index++] = bucket[k][l];
}
}
//第i+1轮后需要将每个bucketElementCounts[k]=0 桶中元素个数0
bucketElementCounts[k] = 0;
}
System.out.println("第" + (i+1) + "轮后:" + Arrays.toString(arr));
}
}
}
运行结果:
第1轮后:[542, 53, 3, 14, 214, 748] 第2轮后:[3, 14, 214, 542, 748, 53] 第3轮后:[3, 14, 53, 214, 542, 748] Process finished with exit code 0
11、堆排序
基本介绍
-
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序
-
堆是具有以下性质的完全二叉树：
-
每个结点的值都大于或等于其左右孩子结点的值，称为
大顶堆
注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系
-
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
-
-
一般升序排序采用大顶堆，降序排列使用小顶堆
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆，降序采用小顶堆)。原始的数组[4,6,8,5,9]
1.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始(叶节点自然不用调整，第一个非叶子结点arr.length/2-1=5/2-1=1，也就是下面的6结点)，从左至右，从上至下进行调整
3.找到第二个非叶子结点4，由于[4,9,8]中的9元素最大，4和9交换
4.这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6
此时，我们就将一个无序序列构造成一个大顶堆
步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
1.将堆顶元素9和末尾元素4进行交换
2.重新调整结构，使其继续满足堆定义
3.再将堆顶元素8和末尾5进行交换，得到第二大元素8
4.后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
排序思路
- 堆是一种树结构，但是排序中会将堆进行顺序存储（变为数组结构）
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
- 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端
- 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
代码:
public class Demo2 {
public static void main(String[] args) {
int[] arr = {4, 6, 8, 5, 9};
//堆排序
heapSort(arr);
System.out.println("堆排序后结果");
System.out.println(Arrays.toString(arr));
}
/**
* 堆排序（升序排序）
* @param arr 待排序数组
*/
public static void heapSort(int[] arr) {
for(int i=arr.length-1; i>=0; i--) {
//将数组调整为大顶堆，长度为未排序数组的长度
for(int j=arr.length/2-1; j>=0; j--) {
adjustHeap(arr, j, i+1);
}
//调整后，数组首元素就为最大值，与为元素交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
}
}
/**
* 将无序数组进行调整，将其调整为大顶堆
* @param arr 待调整的数组
* @param index 非叶子节点的索引
* @param length 待调整数组的长度
*/
public static void adjustHeap(int[] arr, int index, int length) {
//保存非叶子节点的值，最后需要进行交换操作
int temp = arr[index];
//进行调整操作
//index*2+1代表其左子树
for(int i = index*2+1; i<length; i = i*2+1) {
//如果存在右子树，且右子树的值大于左子树，就让索引指向其右子树
if(i+1<length && arr[i] < arr[i+1]) {
i++;
}
//如果右子树的值大于该节点的值就交换，同时改变索引index的值
if(arr[i] > arr[index]) {
arr[index] = arr[i];
index = i;
}else {
break;
}
//调整完成后，将temp放到最终调整后的位置
arr[index] = temp;
}
}
}
运行结果:
堆排序后结果 [4, 5, 6, 8, 9]
六、查找
1、线性查找
线性查找是一种非常简单的查找方式。查找思路是：从数组的一个元素出发，一个个地和要查找的值进行比较，如果发现有相同的元素就返回该元素的下标。反之返回-1（未找到）
public class Demo1 {
public static void main(String[] args) {
int[] arr = {1, 11, -1, 0, 55};
int result = seqSearch(arr, 1);
if(result == -1) {
System.out.println("数组中没有该元素");
}else {
System.out.println("该元素在数组的下标是：" + result);
}
}
/**
* 线性查找
* @param arr 查找的数组
* @param num 待查找的数字
* @return 数字的索引
*/
public static int seqSearch(int[] arr, int num) {
for(int i = 0; i<arr.length; i++) {
if(arr[i] == num) {
return i;
}
}
return -1;
}
}
2、二分查找
进行二分查找的数组必须为有序数组
- 设置一个指向中间元素下标的变量mid，mid=(left + right)/2
- 让要查找的元素和数组mid下标的元素进行比较
- 如果查找的元素大于arr[mid]，则left变为mid后面一个元素的下标
- 如果查找的元素小于arr[mid]，则right变为mid前一个元素的下标
- 如果查找的元素等于arr[mid]，则mid就是要查找元素所在的位置
- 当left > rigth时，说明元素不在该数组中
代码:
public class BinarySearch {
public static void main(String[] args) {
//使用二分查找 数组必须有序
int arr[] = {1,8,10,89,1000,1234};
int resIndex = binarySearch(arr, 0, arr.length - 1, 8);
System.out.println("resIndex = "+resIndex);
}
/**
* 二分查找算法
* @param arr 数组
* @param left 左边的索引
* @param right 右边的索引
* @param finaVal 要查找的值
* @return 如果找到就返回下标 没有找到返回-1
*/
public static int binarySearch(int[] arr, int left, int right, int finaVal) {
//当left > right 时,说明递归整个数组没有找到
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (finaVal > midVal) {//向右递归
return binarySearch(arr, mid + 1, right, finaVal);
} else if (finaVal < midVal){
return binarySearch(arr, left,mid - 1, finaVal);
} else {
return mid;
}
}
}
但是有可能要查找的元素有多个。这时就需要在找到一个元素后，不要立即返回，而是扫描其左边和右边的元素，将所有相同元素的下标保存到一个数组中，然后一起返回
public class BinarySearch {
public static void main(String[] args) {
//使用二分查找 数组必须有序
int arr[] = {1,8,10,89,1000,1000,1000,1234};
List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 100);
System.out.println("resIndex = "+resIndexList.toString());
}
/**
* {1,8,10,89,1000,1000,1000,1234}
* 当有多个相同的数值时,如何将所有数值的值都返回,比如1000
* 1.在找到mid索引值,不要马上返回
* 2.向mid索引值的左边扫描,将所有满足1000的元素的下标,加入到集合ArrayList
* 3.向mid索引值的右边扫描,将所有满足1000的元素的下标,加入到集合ArrayList
* 4.将ArrayList返回
*/
public static List<Integer> binarySearch2(int[] arr, int left, int right, int finaVal) {
//当left > right 时,说明递归整个数组没有找到
if (left > right) {
return new ArrayList<>();
}
int mid = (left + right) / 2;
int midVal = arr[mid];
if (finaVal > midVal) {//向右递归
return binarySearch2(arr, mid + 1, right, finaVal);
} else if (finaVal < midVal){
return binarySearch2(arr, left,mid - 1, finaVal);
} else {
ArrayList<Integer> resIndexList = new ArrayList<>();
//向mid索引值的左边扫描 将所有满足1000的元素的下标,加入到集合ArrayList
int temp = mid - 1;
while (true) {
if (temp < 0 || arr[temp] != finaVal) {
break;
}
//否则 就temp放入到ArrayList
resIndexList.add(temp);
temp -= 1;
}
resIndexList.add(mid);
//向mid索引值的右边扫描 将所有满足1000的元素的下标,加入到集合ArrayList
temp = mid + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != finaVal) {
break;
}
//否则 就temp放入到ArrayList
resIndexList.add(temp);
temp += 1;
}
return resIndexList;
}
}
}
3、插值查找
在二分查找中，如果我们 要找的元素位于数组的最前端或者最后段，这时的查找效率是很低的。所以在二分查找至上，引入了插值查找，也是一种基于有序数组的查找方式
插值查找与二分查找的区别是：插值查找使用了一种自适应算法，用这种算法来计算mid。
mid的值在两种查找算法中的求法：
-
二分查找：mid = (left + right)/2
-
插值查找：
mid = left + (right - left) * (num - arr[left]) / (arr[right] - arr[left])
- 其中num为要查找的那个值
插值查找注意事项:
- 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找速度较快
- 关键字分布不均匀的情况下,该方法不一定比折半查找要好
public class InsertValueSearch {
public static void main(String[] args) {
int arr[] = {1,8,10,89,1000,1000,1000,1234};
int resIndex = insertValueSearch(arr, 0, arr.length - 1, 89);
System.out.println("resIndex = "+resIndex);
}
/**
* 插值查找算法也要求数组有序
* @param arr 数组
* @param left 左边索引
* @param right 右边索引
* @param findVal 查找值
* @return 如果找到就返回下标 没有找到返回-1
*/
public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
return -1;
}
//求出mid
int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
int midVal = arr[mid];
if (findVal > midVal) {//说明应该向右边递归
return insertValueSearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return insertValueSearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
}
4、斐波那契(黄金分割法)查找
-
黄金分割点是指把一条线段分割成两部分, 使其中一部分与全长之比等于另一部分与这部分之比. 取其前三位数字的近似值是0.618,由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比.
-
斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618
斐波那契查找原理与前两种相似,仅仅改变了中间节点(mid)的位置, mid不再是中间或插值得到,而是位于黄金分割点附近,即 mid = low + F(k-1)-1 (F代表斐波那契数列),如下图所示:
对F(k-1)-1的理解:
-
由斐波那契数列F[k]=F[k-1]+F[k-2]的性质, 可以得到(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) + 1, 该式说明: 只要顺序表的长度为F[k]-1, 则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两端, 即如上图所示,从而中间位置为mid = low + F(k-1)-1
-
类似的,每一个字段也可以用相同的方式分割
-
但顺序表长度n不一定刚好等于F[k]-1, 所以需要将原来的顺序表长度n增加至F[k]-1,这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后, 新增的位置(从n+1到F[k]-1),都赋值为n位置的值即可
//获取到斐波那契分割数值的下标
while (high > f[k] - 1) {
k++;
}
public class FeibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int arr[] = {1,8,10,89,1000,1000,1000,1234};
System.out.println(fibSearch(arr, 1234));
}
//因为后面mid = low + F(k - 1) - 1,需要使用到斐波那契数列,因此需要创建一个
public static int[] fib() {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
//编写斐波那契查找算法
/**
*
* @param a 数组
* @param key 我们需要查找的关键码(值)
* @return 返回对应的下标 没有-1
*/
public static int fibSearch(int[] a, int key){
int low = 0;
int high = a.length - 1;
int k = 0;//表示斐波那契分割数值的下标
int mid = 0;//存放mid值
int f[] = fib();//获取到斐波那契数列
//获取到斐波那契分割数值的下标
while (high > f[k] - 1) {
k++;
}
//因为f[k]值可能大于a的长度,因此我们需要使用Arrays类,构建一个新的数组 并指向a[]
//不足的部分会使用0填充
int[] temp = Arrays.copyOf(a, f[k]);
//实际上需求使用a数组最后的数填充temp
//举例 temp={1,8,10,89,1000,1234,0,0} => {1,8,10,89,1000,1234,1234,1234}
for (int i = high + 1; i < temp.length; i++) {
temp[i] = a[high];
}
//使用while循环处理,找到我们的数key
while (low <= high) {
mid = low + f[k - 1] - 1;
if (key < temp[mid]) {//向数组左边查找
high = mid - 1;
k--;
} else if (key > temp[mid]) {//向数组右边查找
low = mid + 1;
k -= 2;
} else {
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
七、哈希表
1、基本介绍
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
代码:
public class HashTabDemo {
public static void main(String[] args) {
//创建学生
Student student1 = new Student(1, "Nyima");
Student student2 = new Student(2, "Lulu");
Student student6 = new Student(6, "WenWen");
HashTab hashTab = new HashTab(5);
hashTab.add(student1);
hashTab.add(student2);
hashTab.add(student6);
hashTab.traverse();
//通过id查找学生信息
hashTab.findStuById(6);
}
}
class Student {
int id;
String name;
Student next;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
class LinkedList {
private Student head = new Student(-1, "");
/**
* 插入学生信息
* @param student 插入学生的信息
*/
public void add(Student student) {
if(head.next == null) {
head.next = student;
return;
}
Student temp = head.next;
while(temp.next != null) {
temp = temp.next;
}
temp.next = student;
}
/**
* 遍历链表
*/
public void traverse() {
if(head.next == null) {
System.out.println("链表为空");
return;
}
Student temp = head;
while(temp.next != null) {
temp = temp.next;
System.out.print(temp + " ");
}
//换行
System.out.println();
}
/**
* 通过id查找学生信息
* @param id 学生id
*/
public void findStuById(int id) {
if(head.next == null) {
System.out.println("链表为空");
return;
}
Student temp = head;
while(temp.next != null) {
temp = temp.next;
if(temp.id == id) {
//找到学生，打印学生信息
System.out.println("该学生信息：" + temp);
return;
}
}
System.out.println("未找到该学生信息");
}
}
class HashTab {
private LinkedList[] linkedLists;
private final int size;
public HashTab(int size) {
this.size = size;
//初始化散列表
linkedLists = new LinkedList[size];
//初始化每个链表，不然会抛出空指针异常
for(int i=0; i<this.size; i++) {
//对每个链表进行初始化操作
linkedLists[i] = new LinkedList();
}
}
public void add(Student student) {
int hashId = getHash(student.id);
linkedLists[hashId].add(student);
}
public void traverse() {
for(int i=0 ; i<size; i++) {
linkedLists[i].traverse();
}
}
public void findStuById(int id) {
int hashId = getHash(id);
linkedLists[hashId].findStuById(id);
}
/**
* 散列函数，获得散列值
* @param id 学生的id
* @return 对应的散列值
*/
private int getHash(int id) {
return id % size;
}
}
运行结果:
链表为空
Student{id=1, name='Nyima'} Student{id=6, name='WenWen'}
Student{id=2, name='Lulu'}
链表为空
链表为空
该学生信息：Student{id=6, name='WenWen'}
Process finished with exit code 0
八、树结构
1、二叉树
为什么需要树
- 数组的查找效率高，但是插入效率低。
- 链表的插入效率高，查找效率低。
需要一种数据结构来平衡查找与插入效率，使得查找速度和插入速度都能得到提升，因此有了树这种数据结构。
树的基本概念
二叉树的基本概念
每个节点最多只能有两个子节点的一种形式称为二叉树
满二叉树
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2n -1 , n为层数，则我们称为满二叉树。
完全二叉树
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
二叉树的遍历
前序遍历
先遍历父节点，再遍历左子节点，最后遍历右子节点
中序遍历
先遍历左子节点，再遍历父节点，最后遍历右子节点
后序遍历
先遍历左子节点，再遍历右子节点，最后遍历父节点
可以看出，前中后的区别在于父节点遍历的时机
示意图
前序遍历结果：1、2、5、6、3
中序遍历结果：5、2、6、1、3
后序遍历结果：5、6、2、3、1
实际代码
此代码使用手动的方式创建二叉树，使用递归的方式遍历二叉树
public class BinaryTreeDemo {
public static void main(String[] args) {
//创建二叉树
BinaryTree binaryTree = new BinaryTree();
//手动创建节点，并放入二叉树中
StuNode stu1 = new StuNode(1, "A");
StuNode stu2 = new StuNode(2, "B");
StuNode stu3 = new StuNode(3, "C");
StuNode stu4 = new StuNode(4, "D");
stu1.setLeft(stu2);
stu1.setRight(stu3);
stu3.setRight(stu4);
binaryTree.setRoot(stu1);
//遍历二叉树
binaryTree.preTraverse();
binaryTree.midTraverse();
binaryTree.lastTraverse();
}
}
class BinaryTree {
/**
* 根节点
*/
private StuNode root;
public void setRoot(StuNode root) {
this.root = root;
}
public void preTraverse() {
if(root != null) {
System.out.println("前序遍历");
root.preTraverse();
System.out.println();
}else {
System.out.println("二叉树为空！");
}
}
public void midTraverse() {
if(root != null) {
System.out.println("中序遍历");
root.midTraverse();
System.out.println();
}else {
System.out.println("二叉树为空！");
} }
public void lastTraverse() {
if(root != null) {
System.out.println("后序遍历");
root.lastTraverse();
System.out.println();
}else {
System.out.println("二叉树为空！");
} }
}
/**
* 二叉树中的一个节点
* 保存了学生信息和左右孩子信息
*/
class StuNode {
int id;
String name;
StuNode left;
StuNode right;
public StuNode(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;
}
public void setName(String name) {
this.name = name;
}
public StuNode getLeft() {
return left;
}
public void setLeft(StuNode left) {
this.left = left;
}
public StuNode getRight() {
return right;
}
public void setRight(StuNode right) {
this.right = right;
}
@Override
public String toString() {
return "StuNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
/**
* 前序遍历
*/
public void preTraverse() {
//父节点的位置
System.out.println(this);
if(left != null) {
left.preTraverse();
}
if(right != null) {
right.preTraverse();
}
}
/**
* 中序遍历
*/
public void midTraverse() {
if(left != null) {
left.midTraverse();
}
//父节点的位置
System.out.println(this);
if(right != null) {
right.midTraverse();
}
}
public void lastTraverse() {
if(left != null) {
left.lastTraverse();
}
if(right != null) {
right.lastTraverse();
}
//父节点的位置
System.out.println(this);
}
}
运行结果:
前序遍历
StuNode{id=1, name='A'}
StuNode{id=2, name='B'}
StuNode{id=3, name='C'}
StuNode{id=4, name='D'}
中序遍历
StuNode{id=2, name='B'}
StuNode{id=1, name='A'}
StuNode{id=3, name='C'}
StuNode{id=4, name='D'}
后序遍历
StuNode{id=2, name='B'}
StuNode{id=4, name='D'}
StuNode{id=3, name='C'}
StuNode{id=1, name='A'}
Process finished with exit code 0
迭代实现
使用迭代对二叉树进行遍历与递归类似，不过需要自己维护一个栈用于存放节点
public class Demo5 {
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
node1.left = node2;
node1.right = node3;
List<Integer> integers = preTraverse(node1);
System.out.println("前序遍历结果");
for (Integer integer : integers) {
System.out.print(integer);
System.out.print(" ");
}
System.out.println();
List<Integer> integers2 = midTraverse(node1);
System.out.println("中遍历结果");
for (Integer integer : integers2) {
System.out.print(integer);
System.out.print(" ");
}
System.out.println();
List<Integer> integers3 = lastTraverse(node1);
System.out.println("后遍历结果");
for (Integer integer : integers3) {
System.out.print(integer);
System.out.print(" ");
}
System.out.println();
}
/**
* 使用迭代法对二叉树进行前序遍历
* @param root 二叉树根节点
* @return 遍历后的集合
*/
public static List<Integer> preTraverse(TreeNode root) {
// 用于存放结果的集合
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
// 栈，用于存放遍历的节点
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
// 遍历二叉树
while (!stack.isEmpty()) {
// 栈顶元素出栈，并放入集合中
root = stack.pop();
result.add(root.val);
// 先遍历右子树，将其压栈
if (root.right != null) {
stack.push(root.right);
}
// 遍历左子树,压栈
if (root.left != null) {
stack.push(root.left);
}
}
return result;
}
/**
* 使用迭代法对二叉树进行中序遍历
* @param root 二叉树根节点
* @return 中序遍历结果集合
*/
public static List<Integer> midTraverse(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
// 节点压栈，并遍历其左子树
while (root != null) {
stack.push(root);
root = root.left;
}
// 栈顶元素出栈，放入结果集合
root = stack.pop();
result.add(root.val);
// 遍历该节点的右子树
root = root.right;
}
return result;
}
/**
* 使用迭代法的后序遍历
* @param root 二叉树根节点
* @return 后序遍历集合
*/
public static List<Integer> lastTraverse(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
// 保存放入集合的右子树，避免重复放入
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
// 获取栈顶元素
root = stack.pop();
// 如果该元素没有右子树，或者右子树已近被遍历过了，就放入集合
if (root.right == null || root.right == pre) {
result.add(root.val);
pre = root;
root = null;
} else {
// 否则就继续遍历该节点的右子树
stack.push(root);
root = root.right;
}
}
return result;
}
}
运行结果:
前序遍历结果
1 2 3
中遍历结果
2 1 3
后遍历结果
2 3 1
二叉树的查找
前、中、后序查找的思路与遍历相似，当找到对应的元素时，直接返回即可。
代码:
public class Demo2 {
public static void main(String[] args) {
//创建根节点
BinarySearchTree tree = new BinarySearchTree();
//手动创建节点
Student student1 = new Student(1, "A");
Student student2 = new Student(2, "B");
Student student3 = new Student(3, "C");
Student student4 = new Student(4, "D");
Student student5 = new Student(5, "E");
student1.setLeft(student2);
student1.setRight(student3);
student2.setLeft(student4);
student3.setRight(student5);
//指定根节点
tree.setRoot(student1);
//查找
tree.preSearch(3);
tree.midSearch(4);
tree.lastSearch(7);
}
}
class BinarySearchTree {
private Student root;
public void setRoot(Student root) {
this.root = root;
}
public void preSearch(int id) {
System.out.println("前序查找");
if(root == null) {
System.out.println("树为空！");
return;
}
Student result = root.preSearch(id);
if(result == null) {
System.out.println("未找到该元素");
System.out.println();
return;
}
System.out.println(result);
System.out.println();
}
public void midSearch(int id) {
System.out.println("中序查找");
if(root == null) {
System.out.println("树为空！");
return;
}
Student result = root.midSearch(id);
if(result == null) {
System.out.println("未找到该元素");
System.out.println();
return;
}
System.out.println(result);
System.out.println();
}
public void lastSearch(int id) {
System.out.println("后序查找");
if(root == null) {
System.out.println("树为空！");
return;
}
Student result = root.lastSearch(id);
if(result == null) {
System.out.println("未找到该元素");
System.out.println();
return;
}
System.out.println(result);
System.out.println();
}
}
class Student {
int id;
String name;
Student left;
Student right;
public Student(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;
}
public void setName(String name) {
this.name = name;
}
public Student getLeft() {
return left;
}
public void setLeft(Student left) {
this.left = left;
}
public Student getRight() {
return right;
}
public void setRight(Student right) {
this.right = right;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
/**
* 前序查找
* @param id 要查找的学生id
* @return 查找到的学生
*/
public Student preSearch(int id) {
//如果找到了，就返回
if(this.id == id) {
return this;
}
//在左子树中查找，如果找到了就返回
Student student = null;
if(left != null) {
student = left.preSearch(id);
}
if(student != null) {
return student;
}
//在右子树中查找，无论是否找到，都需要返回
if(right != null) {
student = right.preSearch(id);
}
return student;
}
/**
* 中序查找
* @param id 要查找的学生id
* @return 查找到的学生
*/
public Student midSearch(int id) {
Student student = null;
if(left != null) {
student = left.midSearch(id);
}
if(student != null) {
return student;
}
//找到了就返回
if(this.id == id) {
return this;
}
if(right != null) {
student = right.midSearch(id);
}
return student;
}
/**
* 后序查找
* @param id 要查找的学生id
* @return 查找到的学生
*/
public Student lastSearch(int id) {
Student student = null;
if(left != null) {
student = left.lastSearch(id);
}
if(student !=null) {
return student;
}
if(right != null) {
student = right.lastSearch(id);
}
if(this.id == id) {
return this;
}
return student;
}
}
运行结果:
前序查找
Student{id=3, name='C'}
中序查找
Student{id=4, name='D'}
后序查找
未找到该元素
二叉树的删除
删除要求
- 如果删除的是叶子节点，则直接删除即可
- 如果删除的是非叶子节点，则删除该子树
删除思路
- 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点
- 如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
- 如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
- 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
- 如果 4步也没有删除结点，则应当向右子树进行递归删除
public class Demo3 {
public static void main(String[] args) {
//创建根节点
BinaryDeleteTree deleteTree = new BinaryDeleteTree();
//手动创建节点
StudentNode student1 = new StudentNode(1, "A");
StudentNode student2 = new StudentNode(2, "B");
StudentNode student3 = new StudentNode(3, "C");
StudentNode student4 = new StudentNode(4, "D");
StudentNode student5 = new StudentNode(5, "E");
student1.setLeft(student2);
student1.setRight(student3);
student2.setLeft(student4);
student3.setRight(student5);
//指定根节点
deleteTree.setRoot(student1);
//删除节点
deleteTree.deleteNode(3);
}
}
class BinaryDeleteTree {
StudentNode root;
public void setRoot(StudentNode root) {
this.root = root;
}
/**
* 删除节点
* @param id 删除节点的id
*/
public void deleteNode(int id) {
System.out.println("删除节点");
if(root.id == id) {
root = null;
System.out.println("根节点被删除");
return;
}
//调用删除方法
root.deleteNode(id);
}
}
class StudentNode {
int id;
String name;
StudentNode left;
StudentNode right;
public StudentNode(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;
}
public void setName(String name) {
this.name = name;
}
public StudentNode getLeft() {
return left;
}
public void setLeft(StudentNode left) {
this.left = left;
}
public StudentNode getRight() {
return right;
}
public void setRight(StudentNode right) {
this.right = right;
}
@Override
public String toString() {
return "StudentNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
/**
* 删除节点
* @param id 删除节点的id
*/
public void deleteNode(int id) {
//如果左子树不为空且是要查找的节点，就删除
if(left != null && left.id == id) {
left = null;
System.out.println("删除成功");
return;
}
//如果右子树不为空且是要查找的节点，就删除
if(right != null && right.id == id) {
right = null;
System.out.println("删除成功");
return;
}
//左递归，继续查找
if(left != null) {
left.deleteNode(id);
}
//右递归，继续查找
if(right != null) {
right.deleteNode(id);
}
}
}
顺序存储二叉树
基本说明
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
特点
- 顺序二叉树通常只考虑完全二叉树
- 第 n个元素的左子节点为 2 × n + 1
- 第 n个元素的右子节点为 2 × n + 2
- 第 n个元素的父节点为(n-1) ÷2
- 其中n 表示二叉树中的第几个元素(从0开始编号)
遍历过程和二叉树的遍历类似，只不过递归的条件有所不同
实现代码
public class Demo4 {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
//前序遍历
System.out.println("数组前序遍历");
arrBinaryTree.preTraverse();
System.out.println();
//中序遍历
System.out.println("数组中序遍历");
arrBinaryTree.midTraverse();
System.out.println();
//后序遍历
System.out.println("数组后序遍历");
arrBinaryTree.lastTraverse();
System.out.println();
}
}
class ArrBinaryTree {
int[] arr;
final int STEP = 2;
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
/**
* 数组的前序遍历
*/
public void preTraverse() {
preTraverse(0);
}
/**
* 数组的前序遍历
* @param index 遍历到的数组元素下标
*/
private void preTraverse(int index) {
if(arr == null || arr.length == 0) {
System.out.println("数组为空！");
return;
}
System.out.print(arr[index] + " ");
//向左递归
if((index * STEP) + 1 < arr.length) {
preTraverse((index * STEP) + 1);
}
//向右递归
if((index * STEP) + 2 < arr.length) {
preTraverse((index * STEP) + 2);
}
}
public void midTraverse() {
midTraverse(0);
}
private void midTraverse(int index) {
if(arr == null || arr.length == 0) {
System.out.println("数组为空!");
}
//左递归
if((index * STEP) + 1 < arr.length) {
midTraverse((index * STEP) + 1);
}
System.out.print(arr[index] + " ");
//右递归
if((index * STEP) + 2 < arr.length) {
midTraverse((index * STEP) + 2);
}
}
public void lastTraverse() {
lastTraverse(0);
}
private void lastTraverse(int index) {
if(arr == null || arr.length == 0) {
System.out.println("数组为空!");
}
//左递归
if((index * STEP) + 1 < arr.length) {
lastTraverse((index * STEP) + 1);
}
//右递归
if((index * STEP) + 2 < arr.length) {
lastTraverse((index * STEP) + 2);
}
System.out.print(arr[index] + " ");
}
}
运行结果:
数组前序遍历 1 2 4 5 3 6 7 数组中序遍历 4 2 5 1 6 3 7 数组后序遍历 4 5 2 6 7 3 1
线索化二叉树
基本概念
因为一般的二叉树，叶子节点的左右指针都为空，这样就会造成空间的浪费。为了减少浪费，便有了线索化二叉树
- n个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树，根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个节点的前一个节点，称为前驱结点
- 一个节点的后一个节点，称为后继结点
- 如果一个节点已经有了左右孩子，那么该节点就不能被线索化了，所以线索化二叉树后，节点的left和right有如下两种情况
- left可能指向的是左孩子，也可能指向的是前驱节点
- right可能指向的是右孩子，也可能指向的是后继节点
图解
中序线索化前
中序线索化后
实现代码
线索化思路
- 每个节点需要用两个变量来表示左右指针的类型（保存左右子树，还是前驱后继）
- 需要用两个变量来表示当前节点和当前节点的前驱节点
- 通过将当前节点的左指针指向前驱节点，来实现前驱节点的绑定
- 通过将前驱节点的右指针指向当前节点，来实现后继节点的绑定
遍历方式
- 各个节点可以通过线性的方式遍历，无需使用递归的方式遍历
- 首先有一个外循环，代替递归操作，循环条件的暂存节点不为空
- 第一个内循环用于找到第一个元素，然后打印
- 第二个循环用于找到节点的后继元素
- 最后将暂存节点令为右孩子
public class Demo1 {
public static void main(String[] args) {
//初始化节点
Student student1 = new Student(1, "1");
Student student2 = new Student(2, "3");
Student student3 = new Student(3, "6");
Student student4 = new Student(4, "8");
Student student5 = new Student(5, "10");
Student student6 = new Student(6, "14");
//手动创建二叉树
ThreadedBinaryTree tree = new ThreadedBinaryTree();
student1.setLeft(student2);
student1.setRight(student3);
student2.setLeft(student4);
student2.setRight(student5);
student3.setLeft(student6);
tree.setRoot(student1);
tree.midThreaded();
//得到第五个节点的前驱节点和后继节点
System.out.println("第五个节点的前驱节点和后继节点");
System.out.println(student5.getLeft());
System.out.println(student5.getRight());
//遍历线索化二叉树
System.out.println("遍历线索化二叉树");
tree.midThreadedTraverse();
}
}
class ThreadedBinaryTree {
private Student root;
/**
* 指向当前节点的前一个节点
*/
private Student pre;
public void setRoot(Student root) {
this.root = root;
}
/**
* 中序线索化
* @param node 当前节点
*/
private void midThreaded(Student node) {
if(node == null) {
return;
}
//左线索化
midThreaded(node.getLeft());
//线索化当前节点
//如果当前节点的左指针为空，就指向前驱节点，并改变左指针类型
if(node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
//通过前驱节点来将右指针的值令为后继节点
if(pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
//处理一个节点后，让当前节点变为下一个节点的前驱节点
pre = node;
//右线索化
midThreaded(node.getRight());
}
public void midThreaded() {
midThreaded(root);
}
/**
* 遍历线索化后的二叉树
*/
public void midThreadedTraverse() {
//暂存遍历到的节点
Student tempNode = root;
//非递归的方法遍历，如果tempNode不为空就一直循环
while(tempNode != null) {
//一直访问二叉树的左子树，直到某个节点的左子树指向前驱节点
while(tempNode.getLeftType() != 1) {
tempNode = tempNode.getLeft();
}
//找到了第一个节点
System.out.println(tempNode);
//再访问该节点的右子树，看是否保存了后继节点
//如果是，则打印该节点的后继节点信息
while(tempNode.getRightType() == 1) {
tempNode = tempNode.getRight();
System.out.println(tempNode);
}
tempNode = tempNode.getRight();
}
}
}
class Student {
private int id;
private String name;
private Student left;
private Student right;
/**
* 左、右指针的类型，0-->指向的是左右孩子，1-->指向的是前驱、后续节点
*/
private int leftType = 0;
private int rightType = 0;
public Student(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;
}
public void setName(String name) {
this.name = name;
}
public Student getLeft() {
return left;
}
public void setLeft(Student left) {
this.left = left;
}
public Student getRight() {
return right;
}
public void setRight(Student right) {
this.right = right;
}
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;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
运行结果:
第五个节点的前驱节点和后继节点
Student{id=2, name='3'}
Student{id=1, name='1'}
遍历线索化二叉树
Student{id=4, name='8'}
Student{id=2, name='3'}
Student{id=5, name='10'}
Student{id=1, name='1'}
Student{id=6, name='14'}
Student{id=3, name='6'}
2、树的应用
堆排序
赫夫曼树
基本介绍
- 给定 n个权值作为 n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)
- 哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近
重要概念
- 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为 L-1
- 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权
- 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积（W×L）
- 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和（W1×L1+W2×L2…），记为WPL(weighted pathlength) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
- WPL最小的就是哈夫曼树
创建思路及图解
创建思路
- 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树，以根节点的权值大小 再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
图解
以{3, 6, 7, 1, 8, 29, 13}为例
首先排序：{1, 3, 6, 7, 8, 13, 29}
赫夫曼树代码实现:
public class HuffmanTree {
public static void main(String[] args) {
int arr[] = {13,7,8,3,29,6,1};
Node node = createHuffmanTree(arr);
preOrder(node);
}
public static void preOrder(Node node) {
if (node != null) {
node.preOrder();
} else {
System.out.println("是空树,不能遍历");
}
}
/**
* 创建赫夫曼树的方法
* @param arr 需要创建成赫夫曼树的数组
* @return 创建好后的赫夫曼树的root节点
*/
public static Node createHuffmanTree(int[] arr) {
//遍历arr数组 将arr每个元素构成一个Node 并放入到ArrayList中
ArrayList<Node> nodes = new ArrayList<>();
for (int value : arr) {
nodes.add(new Node(value));
}
while (nodes.size() > 1) {
//排序 从小到大
Collections.sort(nodes);
System.out.println("nodes: = "+nodes);
//取出根节点权值最小的两颗二叉树
//1.取出权值最小的节点(二叉树)
Node leftNode = nodes.get(0);
//2.取出权值第二小的节点(二叉树)
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集合排序
//让Node实现Comparable接口
class Node implements Comparable<Node> {
int value;//节点权值
Node left;//指向左子节点
Node right;//指向右子节点
//前序遍历
public void preOrder() {
System.out.print(this.value + " ");
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
@Override
public int compareTo(Node o) {
//表示从小到大排序
return this.value - o.value;
}
}
运行结果:
nodes: = [Node{value=1}, Node{value=3}, Node{value=6}, Node{value=7}, Node{value=8}, Node{value=13}, Node{value=29}]
nodes: = [Node{value=4}, Node{value=6}, Node{value=7}, Node{value=8}, Node{value=13}, Node{value=29}]
nodes: = [Node{value=7}, Node{value=8}, Node{value=10}, Node{value=13}, Node{value=29}]
nodes: = [Node{value=10}, Node{value=13}, Node{value=15}, Node{value=29}]
nodes: = [Node{value=15}, Node{value=23}, Node{value=29}]
nodes: = [Node{value=29}, Node{value=38}]
67 29 38 15 7 8 23 10 4 1 3 6 13
Process finished with exit code 0
哈夫曼编码
原理及图解
前缀编码：任何一个字符的编码，都不会是其它的字符的前缀
- 统计需编码的字符串中，各个字符出现的次数：如helloworld
- h:1 e:1 w:1 r:1 d:1 o:2 l:3
- 将字符出现的次数作为权值，构建哈弗曼树。如下图
- 根据哈弗曼树进行编码，向左的路径为0，向右的路径为1
- 字符编码结果为：h:000 e:001 w:100 d:1010 r:1011 l:11 o:01
- 字符串编码结果为：000001111101100011011111010
数据解压(使用赫夫曼编码解码)
- 前面得到了哈夫曼编码和对应的编码byte[], 即:[-88,-65,-56,-65.......]
- 使用赫夫曼编码进行解码得到原来字符串
实现代码
此处代码只实现了哈弗曼树的创建与每个字符的编码
public class HuffmanCode {
public static void main(String[] args) {
String content = "i like like like java do you like a java";
final byte[] contentBytes = content.getBytes();
System.out.println(contentBytes.length);//40
List<Node> nodes = getNodes(contentBytes);
System.out.println(nodes);
//创建的二叉树
System.out.println("赫夫曼树");
Node heffmanTreeRoot = creatHuffmanTree(nodes);
preOrder(heffmanTreeRoot);
//对应的赫夫曼编码
//getCodes(heffmanTreeRoot, "", stringBuilder);
Map<Byte, String> codes = getCodes(heffmanTreeRoot);
System.out.println("生成的赫夫曼编码表:"+codes);
byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
System.out.println("huffmanCodeBytes"+Arrays.toString(huffmanCodeBytes));//17
//解码
byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes);
System.out.println("原来的字符串:"+new String(sourceBytes));
}
//完成数据的解压
// 1.将huffmanCodeBytes[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
// 重写 先转成赫夫曼编码对应的二进制的字符串"1010100010111..."
// 2.赫夫曼编码对应的二进制的字符串"1010100010111..." => 对照赫夫曼编码 =>"i like like like java do you like a java"
private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
//1.先得到huffmanBytes 对应的二进制的字符串,形式101010010111...
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
HashMap<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
System.out.println("反向map="+ map);
//创建一个集合, 存放byte
ArrayList<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'
String key = stringBuilder.substring(i, i + count); //i不动,让count移动,指定匹配到一个字符
b = map.get(key);
if (b == null) {//说明没有匹配到
count++;
} else {
//匹配到
flag = false;
}
}
list.add(b);
i += count;//i直接移动到count
}
//list中数据放到byte[]并返回
byte b[] = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/**
* 将一个byte 转成一个二进制的字符串
* @param flag 标志是否需要补高位 如果是true,表示需要补高位,false不需要补高位
* @param b 传入的byte
* @return 是该b 对应的二进制的字符串(注意是按补码返回)
*/
private static String byteToBitString(boolean flag, byte b) {
//使用变量保存b
int temp = b;//将b转成int
//如果是正数 我们还存在补高位
if (flag) {
temp |= 256; //按位或256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
* 编写一个方法,将字符串对应的byte[] 数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[]
* @param bytes 原始的字符串对应的 byte[]
* @param huffmanCodes 生成的赫夫曼编码map
* @return
*/
private static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCodes) {
//1.利用huffmanCodes将byte转成 赫夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
//遍历byte数组
for (byte b: bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//将"10101000101111111110..."转成byte[]
//统计返回 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;//记录是第几个byte
for (int i = 0; i < stringBuilder.length(); i += 8) {//因为是每8位对应一个byte,所以步长+8
String strByte;
if (i+8 > stringBuilder.length()) {
//不够8位
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i+8);
}
//将strByte 转成一个byte,放入到huffmanCopyBytes
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼树对应的编码
//1.将赫夫曼编码表存放在Map<Byte,String>形式
// 32 ->01 97 -> 100 100 -> 11000
static Map<Byte,String> huffmanCodes = new HashMap<>();
//2再生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径
static StringBuilder stringBuilder = new StringBuilder();
//为了调用方便
private static Map<Byte,String> getCodes(Node root) {
if (root == null) {
return null;
}
getCodes(root, "", stringBuilder);
return huffmanCodes;
}
/**
* 将传入的Node节点的所有叶子节点的赫夫曼编码得到,并放入到huffmanmanCode集合
* @param node 传入节点
* @param code 路径 左节点是0 有节点是1
* @param stringBuilder 用于拼接路径
*/
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
//将code加入到stringBuilder2
stringBuilder2.append(code);
if (node != null) {
//判断当前node是叶子结点还是非叶子结点
if (node.data == null) {//非叶子结点
//向左递归处理
getCodes(node.left, "0", stringBuilder2);
//向右递归
getCodes(node.right, "1", stringBuilder2);
} else {
//说明是叶子结点 就是找到某个叶子结点的最后
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//前序遍历
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空");
}
}
/**
*
* @param bytes 接收字节数组
* @return 返回的就是List
*/
private static List<Node> getNodes(byte[] bytes) {
//1.创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<>();
//2.遍历bytes, 统计每一个byte出现的次数 ->map[key,value]
HashMap<Byte, Integer> map = new HashMap<>();
for (byte b : bytes) {
Integer count = map.get(b);
if (count == null) {
map.put(b, 1);
} else {
map.put(b, count + 1);
}
}
//把每一个键值对转成一个Node对象,并加入到nodes集合中
//遍历map
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
//通过List 创建对应的赫夫曼树
private static Node creatHuffmanTree (List<Node> nodes) {
while (nodes.size() > 1) {
//排序 从小到大
Collections.sort(nodes);
//取出第一棵最小的二叉树
Node leftNode = nodes.get(0);
//取出第二棵最小的二叉树
Node rightNode = nodes.get(1);
//创建一棵新的二叉树, 它的根节点没有data,只有权值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//将已经处理的两棵二叉树从nodes中删除
nodes.remove(leftNode);
nodes.remove(rightNode);
//将新的二叉树加入到nodes
nodes.add(parent);
}
//nodes 最后的节点 就是赫夫曼树的根节点
return nodes.get(0);
}
}
class Node implements Comparable<Node>{
Byte data; //存放数据(字符本身),例如'a' => 97
int weight; //权值,表示字符出现的次数
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
//从小到大排序
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
//前序遍历
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
运行结果:
40
[Node{data=32, weight=9}, Node{data=97, weight=5}, Node{data=100, weight=1}, Node{data=101, weight=4}, Node{data=117, weight=1}, Node{data=118, weight=2}, Node{data=105, weight=5}, Node{data=121, weight=1}, Node{data=106, weight=2}, Node{data=107, weight=4}, Node{data=108, weight=4}, Node{data=111, weight=2}]
赫夫曼树
Node{data=null, weight=40}
Node{data=null, weight=17}
Node{data=null, weight=8}
Node{data=108, weight=4}
Node{data=null, weight=4}
Node{data=106, weight=2}
Node{data=111, weight=2}
Node{data=32, weight=9}
Node{data=null, weight=23}
Node{data=null, weight=10}
Node{data=97, weight=5}
Node{data=105, weight=5}
Node{data=null, weight=13}
Node{data=null, weight=5}
Node{data=null, weight=2}
Node{data=100, weight=1}
Node{data=117, weight=1}
Node{data=null, weight=3}
Node{data=121, weight=1}
Node{data=118, weight=2}
Node{data=null, weight=8}
Node{data=101, weight=4}
Node{data=107, weight=4}
生成的赫夫曼编码表:{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
huffmanCodeBytes[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
解码后赫夫曼字节数组对应的二进制字符串:1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
反向map={000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106}
原来的字符串:i like like like java do you like a java
Process finished with exit code 0
文件压缩解压
压缩: 读取文件 -> 得到赫夫曼编码表 -> 完成压缩
解压: 读取压缩文件(数据和赫夫曼编码表) -> 完成解压(文件恢复)
public class HuffmanCodeWenjian {
public static void main(String[] args) {
//测试压缩文件
//String srcFile = "E://123.txt";
//String dstFile = "E://dst.zip";
//zipFile(srcFile, dstFile);
//System.out.println("压缩文件ok");
//测试解压文件
String zipFile = "E://dst.zip";
String dstFile = "E://1232.txt";
unZipFiles(zipFile, dstFile);
System.out.println("解压成功");
}
//编写方法 完成对压缩文件的解压
/**
*
* @param zipFile 传入压缩文件路径
* @param dstFile 将文件解压到的路径
*/
public static void unZipFiles(String zipFile, String dstFile) {
//定义文件输入流
InputStream is = null;
//定义一个对象输入流
ObjectInputStream ois = null;
//定义文件输出流
OutputStream os = null;
try {
//创建文件输入流
is = new FileInputStream(zipFile);
//创建一个和is关联的对象输入流
ois = new ObjectInputStream(is);
//读取byte数组 huffmanBytes
byte[] huffmanBytes =(byte[]) ois.readObject();
//读取赫夫曼编码表
Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
//解码
byte[] bytes = decode(huffmanCodes, huffmanBytes);
//将bytes数组写入到目标文件
os = new FileOutputStream(dstFile);
//写数据到dstFile文件
os.write(bytes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
//编写方法 将一个文件进行压缩
/**
*
* @param srcFile 传入的要压缩文件的全路径
* @param dstFile 压缩后放入的目录
*/
public static void zipFile(String srcFile, String dstFile) {
//创建文件的输出流
FileOutputStream os = null;
ObjectOutputStream oos = null;
//创建文件的输入流
FileInputStream is = null;
try {
//创建文件的输入流
is = new FileInputStream(srcFile);
//创建一个和源文件大小一样的byte[]
byte[] b = new byte[is.available()];
//读取文件
is.read(b);
//直接对源文件压缩
byte[] huffmanBytes = huffmanZip(b);
//创建文件的输出流,存放压缩文件
os = new FileOutputStream(dstFile);
//创建一个和文件输出流关联的ObjectOutputStream
oos = new ObjectOutputStream(os);
//把赫夫曼编码后的字节数组写入压缩文件
oos.writeObject(huffmanBytes);
//这里以对象流的方式写入赫夫曼编码, 为了恢复源文件时使用
//注意一定要把赫夫曼编码写入压缩文件
oos.writeObject(huffmanCodes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
is.close();
oos.close();
os.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
//完成数据的解压
// 1.将huffmanCodeBytes[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
// 重写 先转成赫夫曼编码对应的二进制的字符串"1010100010111..."
// 2.赫夫曼编码对应的二进制的字符串"1010100010111..." => 对照赫夫曼编码 =>"i like like like java do you like a java"
private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
//1.先得到huffmanBytes 对应的二进制的字符串,形式101010010111...
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
HashMap<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
System.out.println("反向map="+ map);
//创建一个集合, 存放byte
ArrayList<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'
String key = stringBuilder.substring(i, i + count); //i不动,让count移动,指定匹配到一个字符
b = map.get(key);
if (b == null) {//说明没有匹配到
count++;
} else {
//匹配到
flag = false;
}
}
list.add(b);
i += count;//i直接移动到count
}
//list中数据放到byte[]并返回
byte b[] = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/**
* 封装成一个方法
* @param bytes 原始的字符串对应的字节数组
* @return
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
//根据nodes 创建赫夫曼树
Node heffmanTreeRoot = creatHuffmanTree(nodes);
//生成对应的赫夫曼编码
Map<Byte, String> codes = getCodes(heffmanTreeRoot);
//根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
return huffmanCodeBytes;
}
/**
* 将一个byte 转成一个二进制的字符串
* @param flag 标志是否需要补高位 如果是true,表示需要补高位,false不需要补高位
* @param b 传入的byte
* @return 是该b 对应的二进制的字符串(注意是按补码返回)
*/
private static String byteToBitString(boolean flag, byte b) {
//使用变量保存b
int temp = b;//将b转成int
//如果是正数 我们还存在补高位
if (flag) {
temp |= 256; //按位或256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
* 编写一个方法,将字符串对应的byte[] 数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte[]
* @param bytes 原始的字符串对应的 byte[]
* @param huffmanCodes 生成的赫夫曼编码map
* @return
*/
private static byte[] zip(byte[] bytes, Map<Byte,String> huffmanCodes) {
//1.利用huffmanCodes将byte转成 赫夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
//遍历byte数组
for (byte b: bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//将"10101000101111111110..."转成byte[]
//统计返回 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;//记录是第几个byte
for (int i = 0; i < stringBuilder.length(); i += 8) {//因为是每8位对应一个byte,所以步长+8
String strByte;
if (i+8 > stringBuilder.length()) {
//不够8位
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i+8);
}
//将strByte 转成一个byte,放入到huffmanCopyBytes
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼树对应的编码
//1.将赫夫曼编码表存放在Map<Byte,String>形式
// 32 ->01 97 -> 100 100 -> 11000
static Map<Byte,String> huffmanCodes = new HashMap<>();
//2再生成赫夫曼编码表示,需要去拼接路径,定义一个StringBuilder存储某个叶子结点的路径
static StringBuilder stringBuilder = new StringBuilder();
//为了调用方便
private static Map<Byte,String> getCodes(Node root) {
if (root == null) {
return null;
}
getCodes(root, "", stringBuilder);
return huffmanCodes;
}
/**
* 将传入的Node节点的所有叶子节点的赫夫曼编码得到,并放入到huffmanmanCode集合
* @param node 传入节点
* @param code 路径 左节点是0 有节点是1
* @param stringBuilder 用于拼接路径
*/
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
//将code加入到stringBuilder2
stringBuilder2.append(code);
if (node != null) {
//判断当前node是叶子结点还是非叶子结点
if (node.data == null) {//非叶子结点
//向左递归处理
getCodes(node.left, "0", stringBuilder2);
//向右递归
getCodes(node.right, "1", stringBuilder2);
} else {
//说明是叶子结点 就是找到某个叶子结点的最后
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//前序遍历
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空");
}
}
/**
*
* @param bytes 接收字节数组
* @return 返回的就是List
*/
private static List<Node> getNodes(byte[] bytes) {
//1.创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<>();
//2.遍历bytes, 统计每一个byte出现的次数 ->map[key,value]
HashMap<Byte, Integer> map = new HashMap<>();
for (byte b : bytes) {
Integer count = map.get(b);
if (count == null) {
map.put(b, 1);
} else {
map.put(b, count + 1);
}
}
//把每一个键值对转成一个Node对象,并加入到nodes集合中
//遍历map
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
//通过List 创建对应的赫夫曼树
private static Node creatHuffmanTree (List<Node> nodes) {
while (nodes.size() > 1) {
//排序 从小到大
Collections.sort(nodes);
//取出第一棵最小的二叉树
Node leftNode = nodes.get(0);
//取出第二棵最小的二叉树
Node rightNode = nodes.get(1);
//创建一棵新的二叉树, 它的根节点没有data,只有权值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//将已经处理的两棵二叉树从nodes中删除
nodes.remove(leftNode);
nodes.remove(rightNode);
//将新的二叉树加入到nodes
nodes.add(parent);
}
//nodes 最后的节点 就是赫夫曼树的根节点
return nodes.get(0);
}
}
class Node implements Comparable<Node>{
Byte data; //存放数据(字符本身),例如'a' => 97
int weight; //权值,表示字符出现的次数
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
//从小到大排序
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
//前序遍历
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
二叉排序树
基本介绍
二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大
- 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树为：
操作思路
添加
- 根据插入节点的值来寻找其应该插入的位置
- 新插入的节点都是叶子节点
删除
删除叶子节点（如删除值为2节点）
- 找到待删除的节点
- 找到待删除节点的父节点
- 判断待删除节点是其父节点的左孩子还是右孩子，然后让其令为空
删除只有一颗子树的节点（如删除值为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
-
删除有两颗子树的节点（如删除值为10的节点）
- 找到待删除的节点targetNode
- 找到targetNode的父节点parent
- 从targetNode的右子树找到最小的节点
- 用一个临时变量，将最小结点的值保存temp = 12
- 删除该最小节点
- targetNode.value = temp
删除根节点（如删除值为7的节点）
- 删除根结点的方法和删除有两个子树的方法相似
- 找到一个接近根节点值的节点
- 删除该节点，将该节点的值赋值给根节点即可
代码:
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {7,3,10,12,5,1,9};
BinarySortTree binarySortTree = new BinarySortTree();
//循环的添加节点到二叉排序树
for (int i = 0; i < arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
//中序遍历二叉排序树
System.out.println("中序遍历二叉排序树");
binarySortTree.infixOrder();
//删除叶子结点
//binarySortTree.delNode(5);
binarySortTree.delNode(7);
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);
}
}
//编写一个方法
//1.返回的以node为根节点的二叉排序树的最小节点的值
//2.删除node为根节点的二叉排序树的最小节点
/**
*
* @param node 传入的节点(当做二叉排序树的根节点)
* @return 返回的以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 delNode(int value) {
if (root == null) {
return;
} else {
//1.先去找到要删除的节点 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) {
if (parent != null) {
//如果targetNode是parent的左子节点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {//targetNode是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 {//targetNode是parent的右子节点
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
//添加节点的方法
public void add(Node node) {
if (root == null) {
//如果root为空则直接让root指向node
root = node;
} else {
root.add(node);
}
}
//中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序树为空,不能遍历");
}
}
}
//创建node节点
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//查找要删除的节点
/**
*
* @param value 希望要删除节点的值
* @return 如果找到返回该节点,否则返回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);
}
}
//查找要删除节点的父节点
/**
*
* @param value 要找到的节点的值
* @return 返回的是要删除的节点的父节点,没有就返回null
*/
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();
}
}
}
运行结果:
中序遍历二叉排序树
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=7}
Node{value=9}
Node{value=10}
Node{value=12}
删除节点后
Node{value=1}
Node{value=3}
Node{value=5}
Node{value=9}
Node{value=10}
Node{value=12}
Process finished with exit code 0
平衡二叉树(AVL树)
基本介绍
为什么需要平衡二叉树
- 如果由数组{1, 2, 3, 4}来构建一颗二叉排序树，得到的二叉树不仅没有体现其特点，反而还退化成了链表
简介
- 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高
- 具有以下特点：
- 它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树
- 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
- 下图所示的二叉树就是平衡二叉树
应用案例——左旋转
将由数列 {4,3,6,5,7,8}构建的二叉排序树，修改为一颗平衡二叉树
此处右子树的高度高于左子树，且差值大于1，所以需要进行左旋转，来降低右子树的高度
步骤
- 创建一个新节点newNode，值为当前节点的值（4），值等于当前根节点的值
-
把新节点的左子树设置成当前节点的左子树
newNode.left = left
-
把新节点的右子树设置为当前节点的右子树的左子树
newNode.right = right.left
-
将当前节点的值改为其右子树的值
value = right.value
-
将当前节点的右子树变为其右子树的右子树
right = right.right
-
让当前节点的左子树指向新节点
left = newLeft
整理后结果
应用案例——右旋转
当一颗二叉排序树的左子树高度大于右子树高度，且差值大于1时，需要进行右旋转，来降低左子树的高度
步骤
- 创建一个新节点，其值为当前节点的值
- 将新节点的右子树指向当前节点的右子树
- 将新节点的左子树指向当前节点的左子树的右子树
- 将当前节点的值改为其左子树的值
- 将当前节点的左子树指向其左子树的左子树
- 将当前节点的右子树指向新节点
应用案例——双旋转
某些时候，只进行左旋转或者右旋转，并不能将二叉排序树变为平衡二叉树。这时就需要进行双旋转，即同时进行左旋转和右旋转
- 进行左旋转时，如果当前节点右子树的左子树高于其右子树，需要对当前节点的右节点进行右旋转，再对当前节点进行右左旋转
- 进行右旋转时，如果当前节点左子树的右子树高于其左子树的左子树，需要对当前节点的左节点进行左旋转，再对当前节点进行右旋转
实现代码
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//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());
System.out.println("左子树的高度:" + avlTree.getRoot().leftHeight());
System.out.println("右子树的高度:" + avlTree.getRoot().rightHeight());
System.out.println("当前根节点:" + avlTree.getRoot());
}
}
//创建AVLTree
class AVLTree {
private Node root;
public Node getRoot() {
return 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);
}
}
//编写一个方法
//1.返回的以node为根节点的二叉排序树的最小节点的值
//2.删除node为根节点的二叉排序树的最小节点
/**
*
* @param node 传入的节点(当做二叉排序树的根节点)
* @return 返回的以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 delNode(int value) {
if (root == null) {
return;
} else {
//1.先去找到要删除的节点 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) {
if (parent != null) {
//如果targetNode是parent的左子节点
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {//targetNode是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 {//targetNode是parent的右子节点
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
//添加节点的方法
public void add(Node node) {
if (root == null) {
//如果root为空则直接让root指向node
root = node;
} else {
root.add(node);
}
}
//中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序树为空,不能遍历");
}
}
}
//创建node节点
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//返回左子树的高度
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;
}
//左旋转
private void leftRotate() {
//创建新的节点,以当前根节点的值
Node newNode = new Node(value);
//把新的节点的左子树设置成当前节点的左子树
newNode.left = left;
//把新节点的右子树设置为当前节点的右子树的左子树
newNode.right = right.left;
//将当前节点的值改为右子节点的值
value = right.value;
//将当前节点的右子树设置成当前节点右子树的右子树
right = right.right;
//把当前节点的左子树(左子节点)设置成新节点
left = newNode;
}
//右旋转
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
//查找要删除的节点
/**
*
* @param value 希望要删除节点的值
* @return 如果找到返回该节点,否则返回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);
}
}
//查找要删除节点的父节点
/**
*
* @param value 要找到的节点的值
* @return 返回的是要删除的节点的父节点,没有就返回null
*/
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.rightHeight() < right.leftHeight()) {
// 先对当前节点的右节点(右子树) -> 右旋转
right.rightRotate();
//再对当前节点左旋转
leftRotate();
} else {
//直接进行左旋转即可
leftRotate();
}
}
if (leftHeight() - rightHeight() > 1) {
//如果它的左子树的右子树高度大于它的左子树的左子树高度
if (left != null && left.rightHeight() > left.leftHeight()) {
//先对当前节点的左节点(左子树) -> 左旋转
left.leftRotate();
//再对当前节点右旋转
rightRotate();
} else {
//直接进行右旋转即可
rightRotate();
}
return;
}
}
//中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
运行结果:
中序遍历
Node{value=6}
Node{value=7}
Node{value=8}
Node{value=9}
Node{value=10}
Node{value=11}
在没有平衡处理前~~~
树的高度:3
左子树的高度:2
右子树的高度:2
当前根节点:Node{value=8}
Process finished with exit code 0
3、多叉树
基本介绍
在二叉树中，每个节点最多有一个数据项和两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）
多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化
2-3树
2-3树是最简单的B树结构，具有以下特点
- 2-3树的所有叶子节点都在同一层(只要是 B树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
- 2-3树是由二节点和三节点构成的树（2和3）
2-3树插入规则
- 2-3树的所有叶子节点都在同一层.(只要是 B树都满足这个条件)
- 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
- 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
- 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面 3个条件
- 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则
- 左边的子树值小于父节点的值
- 中间的子树值在父节点的值之间
- 右边子树的值大于父节点的值
B树、B+和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*树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为 2/3，而B+树的块的最低使用率为的1/2
- 从第 1个特点我们可以看出，B*树分配新结点的概率比B+树要低，空间使用率更高
九、图结构
1、基本介绍
定义
- 当我们需要表示多对多的关系时，我们就需要图
- 图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点
表示方法
邻接矩阵
- 邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和 col表示的是1…n个点
如上图的邻接矩阵就是
0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0
其中0表示没有连接，1表示有连接
邻接表
-
邻接矩阵需要为每个顶点都分配 n个边的空间，其实有很多边都是不存在,会造成空间的一定损失
-
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，
邻接表由数组+链表组成
- 数组的索引代表顶点
- 链表中元素的值代表与该顶点相连的顶点的值
如上图的进阶表就是
2、图的创建
邻接矩阵创建图
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges; //表示边的数目
public static void main(String[] args) {
//测试图是否创建OK
int n = 5;//节点的个数
String vertexs[] = {"A","B","C","D","E"};
//创建图对象
Graph graph = new Graph(n);
//循环的添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//添加边
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);
//显示邻接矩阵
System.out.println("邻接矩阵");
graph.showGraph();
}
//构造器
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
}
//图的常用方法
//返回节点的个数
public int getNumOfVertex() {
return vertexList.size();
}
//显示图对应的矩阵
public void showGraph() {
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
//返回边的数目
public int getNumOfEdges() {
return numOfEdges;
}
//返回节点i(下标)对应的数据0->"A" 1->"B" 2->"C"
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1和v2的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
//插入节点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
//添加边
/**
*
* @param v1 表示点的下标 即使第几个顶点"A"-"B" "A"->0 "B"->1
* @param v2 第二个顶点对应的下标
* @param weight 表示
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
运行结果:
邻接矩阵 [0, 1, 1, 0, 0] [1, 0, 1, 1, 1] [1, 1, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0] Process finished with exit code 0
3、图的遍历
所谓图的遍历，即是对节点的访问。对该图进行深度优先遍历和广度优先遍历
深度优先遍历（DFS）
- 深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
- 这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问
- 深度优先搜索是一个递归的过程
思路
- 访问初始结点v，并标记结点v为已访问
- 查找结点v的第一个邻接结点w
- 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续
- 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）
- 查找结点v的w邻接结点的下一个邻接结点，转到步骤 3
实现代码
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges; //表示边的数目
//定义给数组boolean[], 记录某个节点是否被访问
private boolean[] isVisited;
public static void main(String[] args) {
//测试图是否创建OK
int n = 5;//节点的个数
String vertexs[] = {"A","B","C","D","E"};
//创建图对象
Graph graph = new Graph(n);
//循环的添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//添加边
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(0, 3, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 4, 1);
//显示邻接矩阵
System.out.println("邻接矩阵");
graph.showGraph();
//深度优先遍历
System.out.println("进行深度优先遍历");
graph.dfs();
}
//构造器
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
isVisited = new boolean[5];
}
//得到第一个邻接节点的下标w
/**
*
* @param index
* @return 如果存在就返回对应的下标,否则就返回-1
*/
public int getFirstNeighbor(int index) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
//根据前一个邻接节点的下标来获取下一个邻接节点
public int getNextNeighbor(int v1, int v2) {
for (int j = v2 + 1; j < vertexList.size(); j++) {
if (edges[v1][j] > 0) {
return j;
}
}
return -1;
}
//深度优先遍历算法
//i 第一次就是0
public void dfs(boolean[] isVisited, int i) {
//首先我们访问该节点输出
System.out.print(getValueByIndex(i) + "->");
//将节点设置为已经访问
isVisited[i] = true;
//查找节点i的第一个邻接节点
int w = getFirstNeighbor(i);
while (w != -1) {//说明有
if (!isVisited[w]) {
dfs(isVisited, w);
}
//如果w节点已经被被访问过
w = getNextNeighbor(i, w);
}
}
//对dfs 进行一个重载,遍历我们所有的节点,并进行dfs
public void dfs() {
//遍历所有的节点,进行dfs[回溯]
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
//图的常用方法
//返回节点的个数
public int getNumOfVertex() {
return vertexList.size();
}
//显示图对应的矩阵
public void showGraph() {
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
//返回边的数目
public int getNumOfEdges() {
return numOfEdges;
}
//返回节点i(下标)对应的数据0->"A" 1->"B" 2->"C"
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1和v2的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
//插入节点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
//添加边
/**
*
* @param v1 表示点的下标 即使第几个顶点"A"-"B" "A"->0 "B"->1
* @param v2 第二个顶点对应的下标
* @param weight 表示
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
运行结果:
邻接矩阵 [0, 1, 1, 1, 0] [1, 0, 1, 0, 1] [1, 1, 0, 0, 0] [1, 0, 0, 0, 0] [0, 1, 0, 0, 0] 进行深度优先遍历 A->B->C->E->D-> Process finished with exit code 0
广度优先遍历（BFS）
- 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
思路
- 访问初始结点 v并标记结点 v为已访问
- 结点v入队列
- 当队列非空时，继续执行，否则算法结束
- 出队列，取得队头结点u
- 查找结点 u的第一个邻接结点 w。
- 若结点 u的邻接结点 w不存在，则转到步骤 3；否则循环执行以下三个步骤：
- 若结点 w尚未被访问，则访问结点 w并标记为已访问
- 结点 w入队列
- 查找结点 u的继 w邻接结点后的下一个邻接结点 w，转到步骤6
实现代码
public class Graph {
private ArrayList<String> vertexList;//存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges; //表示边的数目
//定义给数组boolean[], 记录某个节点是否被访问
private boolean[] isVisited;
public static void main(String[] args) {
//测试图是否创建OK
int n = 5;//节点的个数
String vertexs[] = {"A","B","C","D","E"};
//创建图对象
Graph graph = new Graph(n);
//循环的添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//添加边
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(0, 3, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 4, 1);
//显示邻接矩阵
System.out.println("邻接矩阵");
graph.showGraph();
//深度优先遍历
//System.out.println("进行深度优先遍历");
//graph.dfs();////A->B->C->D->E->
System.out.println();
System.out.println("进行广度优先遍历");
graph.bfs();//A->B->C->D->E->
}
//构造器
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
isVisited = new boolean[5];
}
//得到第一个邻接节点的下标w
/**
*
* @param index
* @return 如果存在就返回对应的下标,否则就返回-1
*/
public int getFirstNeighbor(int index) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
//根据前一个邻接节点的下标来获取下一个邻接节点
public int getNextNeighbor(int v1, int v2) {
for (int j = v2 + 1; j < vertexList.size(); j++) {
if (edges[v1][j] > 0) {
return j;
}
}
return -1;
}
//深度优先遍历算法
//i 第一次就是0
public void dfs(boolean[] isVisited, int i) {
//首先我们访问该节点输出
System.out.print(getValueByIndex(i) + "->");
//将节点设置为已经访问
isVisited[i] = true;
//查找节点i的第一个邻接节点
int w = getFirstNeighbor(i);
while (w != -1) {//说明有
if (!isVisited[w]) {
dfs(isVisited, w);
}
//如果w节点已经被被访问过
w = getNextNeighbor(i, w);
}
}
//对dfs 进行一个重载,遍历我们所有的节点,并进行dfs
public void dfs() {
//遍历所有的节点,进行dfs[回溯]
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
//对一个节点进行广度优先遍历的方法
private void bfs(boolean[] isVisited, int i) {
int u;//表示队列的头结点对应的下标
int w;//邻接节点w
//队列,记录节点访问的数据
LinkedList<Object> queue = new LinkedList<>();
//访问节点,输出节点信息
System.out.print(getValueByIndex(i) + "=>");
//将节点加入队列
isVisited[i] = true;
queue.addLast(i);
while (!queue.isEmpty()) {
//取出队列的头结点下标
u= (Integer) queue.removeFirst();
//得到第一个邻接节点的下标w
w = getFirstNeighbor(u);
while (w != -1) {//找到
//是否访问过
if (!isVisited[w]) {
System.out.print(getValueByIndex(w) + "=>");
//标记已经访问
isVisited[w] = true;
//入队
queue.addLast(w);
}
//以u为前驱点,找w后面的下一个邻接点
w = getNextNeighbor(u, w);//体现出我们的广度优先
}
}
}
//遍历所有的节点,都进行广度优先搜索
public void bfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}
}
//图的常用方法
//返回节点的个数
public int getNumOfVertex() {
return vertexList.size();
}
//显示图对应的矩阵
public void showGraph() {
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
//返回边的数目
public int getNumOfEdges() {
return numOfEdges;
}
//返回节点i(下标)对应的数据0->"A" 1->"B" 2->"C"
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1和v2的权值
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
//插入节点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
//添加边
/**
*
* @param v1 表示点的下标 即使第几个顶点"A"-"B" "A"->0 "B"->1
* @param v2 第二个顶点对应的下标
* @param weight 表示
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
运行结果:
邻接矩阵 [0, 1, 1, 1, 0] [1, 0, 1, 0, 1] [1, 1, 0, 0, 0] [1, 0, 0, 0, 0] [0, 1, 0, 0, 0] 进行广度优先遍历 A=>B=>C=>D=>E=> Process finished with exit code 0
十、算法
1、二分查找算法(非递归)
- 前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式
- 二分查找算法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后在进行查找
- 二分查找算法的运行时间为对数时间O(log2n)，即查找到需要的目标位置最多只需要log2n步，假设从[0，99]的队列(100个数，即n=100)中寻找目标数30，则需要查找步数为log2100，即最多需要查找7次(26 < 100 <2^7)
代码:
public class BinarySearchNoRecur {
public static void main(String[] args) {
//测试
int[] arr = {1,3,8,10,67,100};
int index = binarySearch(arr, 100);
System.out.println("index=" +index);
}
//二分查找的非递归实现
/**
*
* @param arr 待查找的数组 arr是升序排序
* @param target 需要查找的数
* @return 返回对应下标, -1表示没有找到
*/
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;//需要向左边查找
} else {
left = mid + 1;//需要向右边查找
}
}
return -1;
}
}
2、分治算法
算法介绍
分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
基本步骤
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解
应用——汉诺塔
思路
A、B、C三个塔
-
如果只有一个盘，直接A->C
-
如果大于等于两个盘，就分成两部分。
最下面的一个盘为一部分，上面的所有盘为一部分
- 将上面部分的盘A->B
- 最下面的盘A->C
- 再将B中的盘B->C
实现代码
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(3, 'A', 'B', 'C');
}
//汉诺塔的移动方法
//使用分治算法
public static void hanoiTower(int num, char a, char b, char c) {
//如果只有一个盘
if (num == 1) {
System.out.println("第1个盘从" + a + "->" + c);
} else {
//如果我们有 n>=2 情况, 我们总是可以看做是两个盘 1.最下边的一个盘 2.上面的所有盘
//1.先把最上面的所有盘 A->B, 移动过程会使用到C
hanoiTower(num-1, a, c, b);
//2.把最下边的盘 A->C
System.out.println("第" + num + "个盘从" + a + "->" + c);
//3.把B塔的所有盘从B->C, 移动过程使用到A塔
hanoiTower(num-1, b, a, c);
}
}
}
运行结果:
第1个盘从A->C 第2个盘从A->B 第1个盘从C->B 第3个盘从A->C 第1个盘从B->A 第2个盘从B->C 第1个盘从A->C Process finished with exit code 0
博客推荐
在刷leetcode时有幸看到了一位大佬写的关于递归的博客，在此转载贴出。
点此跳转
3、动态规划
算法介绍
- 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
- 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
- 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
- 动态规划可以通过填表的方式来逐步推进，得到最优解
算法应用——01背包问题
| 物品 | 重量 | 价值 |
|---|---|---|
| 吉他 | 1 | 1500 |
| 音响 | 4 | 3000 |
| 电脑 | 3 | 2000 |
一个背包最多装4kg的东西，求
- 装入物品使得背包的总价值最大，且不超出背包的容量
- 要求装入的物品不能重复（01背包）
解题思路
- 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)
- 这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
算法的主要思想，利用动态规划来解决。每次遍历到的第 i个物品，根据 w[i]和 v[i]来确定是否需要将该物品放入背包中。即对于给定的 n个物品，设 v[i]、w[i]分别为第 i个物品的价值和重量，C为背包的容量。再令二维数组 v [i] [j]表示在前 i个物品中能够装入容量为 j的背包中的最大价值。则我们有下面的结果
//表示填入表的第一行和第一列是 0，主要是为了方便表示物品和容量
(1) v[i][0]=v[0][j]=0;
// 当准备加入新增的商品的重量大于当前背包的容量时，就直接使用上一个单元格的装入策略（装入物品的价值）
(2) 当 w[i]>j 时：v[i][j]=v[i-1][j]
// 当准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
(3) 当 j>=w[i]时：v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
v[i-1][j]：上一个单元的装入的最大值
v[i] : 表示当前商品的价值
w[i] : 表示第i个商品的重量
v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值
简单来说：
-
装入物品的容量大于背包容量时，直接使用之前装入背包物品的最大价值
-
装入物品容量小于等于背包容量时，比较
- 装入该物品之前，背包物品的最大价值
- 装入该后，该物品的价值+剩余容量能放入物品的最大价值
选取较大者
实现代码
public class KnapsackProblen {
public static void main(String[] args) {
int[] w = {1, 4, 3};//物品的重量
int[] val = {1500, 3000, 2000};//物品的价值
int m = 4; //背包的容量
int n = val.length;//物品的个数
//为了记录商品放入的情况,定义一个二维数组
int[][] path = new int[n+1][m+1];
//创建二维数组
//v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
int[][] v =new int[n+1][m+1];
//初始化第一行和第一列, 这里在本程序中,可以不去处理,因为默认就是0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;//将第一列设置为0
}
for (int i = 0; i < v[0].length; i++) {
v[0][i] = 0;//将第一行设置0
}
//根据前面得到的公式进行动态规划处理
for (int i = 1; i < v.length; i++) {//不处理第一行 i是从1开始的
for (int j = 1; j<v[0].length; j++) {//不处理第一列,j是从1开始的
//公式
if (w[i-1] > j) {//因为我们程序i 是从1开始的, 因此原来公式中的w[i]修改成w[i-1]
v[i][j] = v[i-1][j];
} else {
//说明:因为我们程序i 是从1开始的,因此公式需要调整
//v[i][j] = Math.max(v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]);
//v[i][j] = Math.max(v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]);
//为了记录商品存放到背包的情况,我们不能直接使用上面的公式,需要使用if-else来体现公式
if (v[i-1][j] < val[i-1] + v[i-1][j-w[i-1]]) {
v[i][j] = val[i-1] + v[i-1][j-w[i-1]];
//把当前的情况记录到path
path[i][j] = 1;
} else {
v[i][j] = v[i-1][j];
}
}
}
}
//输出一下
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
//输出最后放入的商品
//存放方法的二维数组的最大下标，从最后开始搜索存放方法
int i = path.length - 1;//行的最大下标
int j = path[0].length - 1;//列的最大下标
while(i > 0 && j > 0) {
if(path[i][j] == 1) {
System.out.println("将第" + i + "个物品放入背包");
//背包剩余容量
j -= w[i-1];
}
i--;
}
}
}
运行结果:
0 0 0 0 0 0 1500 1500 1500 1500 0 1500 1500 1500 3000 0 1500 1500 2000 3500 将第3个物品放入背包 将第1个物品放入背包 Process finished with exit code 0
3、KMP算法
KMP是一个解决模式串在文本串是否出现过，如果出现过，找出最早出现的位置的经典算法
参考资料: https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
算法应用——字符串匹配
思路及图解
问题：有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
算法步骤
- 首先，用 str1的第一个字符和 str2的第一个字符去比较，不符合，关键词向后移动一位
- 重复第一步，还是不符合，再后移
- 一直重复，直到 Str1有一个字符与 Str2的第一个字符符合为止
- 接着比较字符串和搜索词的下一个字符，还是符合
- 遇到 Str1有一个字符与 Str2对应的字符不符合
重要步骤
-
这时候，想到的是继续遍历 str1的下一个字符，重复第 1步。(其实是很不明智的，因为此时 BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”
- KMP 算法的想法是：设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率
-
怎么做到把刚刚重复的步骤省略掉？可以对 str2计算出一张部分匹配表，这张表的产生在后面介绍
-
str2的部分匹配表如下
搜索词 A B C D A B D 部分匹配值 0 0 0 0 1 2 0
-
-
已知空格与 D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的部分匹配值为 2，因此按照下面的公式算出向后移动的位数：
- 移动位数 = 已匹配的字符数 - 对应的部分匹配值
- 因为 6 - 2 等于 4，所以将搜索词向后移动 4 位
- 因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2（”AB”），对应的部分匹配值为0。
所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位
- 因为空格与 A不匹配，继续后移一位
- 逐位比较，直到发现 C与 D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位
- 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了
部分匹配表的生成
前缀与后缀
- 前缀：ABCD的前缀为[A, AB, ABC]
- 后缀：ABCD的后缀为[BCD, CD, D]
部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，
- ”A”的前缀和后缀都为空集，共有元素的长度为 0；
- ”AB”的前缀为[A]，后缀为[B]，共有元素的长度为 0；
- ”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0；
- ”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；
- ”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为 1；
- ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为 2；
- ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD,D]，共有元素的长度为 0。
实现代码
public class KMPAlgorithm {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDC";
String str2 = "ABCDABDC";
int[] next = kmpNext(str2);
System.out.println("部分匹配值next:"+ Arrays.toString(next));
int index = kmpSearch(str1, str2, next);
System.out.println("下标位置index:"+index);
}
/**
* kmp搜索算法
* @param str1 原字符串
* @param str2 子串
* @param next 部分匹配表, 是子串对应的部分匹配表
* @return 如果是-1就是没有匹配到,否则返回第一个匹配的位置
*/
public static int kmpSearch(String str1, String str2, int[] next) {
//遍历
for (int i = 0, j=0; i < str1.length(); i++) {
//需要处理str1.charAt(i) != str2.charAt(j), 去调整j的大小
//kmp算法的核心点
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j-1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {//找到了
return i - j + 1;
}
}
return -1;
}
//获取到一个字符串(子串)的部分匹配值表
public static int[] kmpNext(String dest) {
//创建一个next数组保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0;//如果字符串的长度为1 部分匹配值就是0
for (int i = 1, j = 0; i < dest.length(); i++) {
//当dest.charAt(i) != dest.charAt(j),我们需要从next[j-1]获取新的j
//直到我们发现有dest.charAt(i) == dest.charAt(j)成立才退出
//这是kmp算法的核心点
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j-1];
}
//当dest.charAt(i) == dest.charAt(j)满足时,部分匹配值就是+1
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
运行结果:
部分匹配值next:[0, 0, 0, 0, 1, 2, 0, 0] 下标位置index:15 Process finished with exit code 0
4、贪心算法
算法简介
- 贪心算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利)的选择，从而
希望能够导致结果是最好或者最优的算法
- 贪心算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
算法应用——集合覆盖
假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号
| 电台 | 覆盖地区个数 | 覆盖地区 |
|---|---|---|
| K1 | 0 | 北京 上海 天津 |
| K2 | 0 | 广州 北京 深圳 |
| K3 | 0 | 成都 上海 杭州 |
| K4 | 0 | 上海 天津 |
| K5 | 0 | 杭州 大连 |
思路及图解
思路
- 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系
- 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
- 重复第 1步直到覆盖了全部的地区
图解
-
遍历电台的覆盖地区，发现K1覆盖的地区最多，将K1覆盖的地区从地区集合中移除。然后将K1放入电台集合中，并更新覆盖地区个数
-
遍历，发现K2覆盖的地区最多，将K2覆盖的地区从地区集合中移除。然后将K2放入电台集合中，并更新覆盖地区个数
-
遍历，发现K3覆盖的地区最多，将K3覆盖的地区从地区集合中移除。然后将K3放入电台集合中，并更新覆盖地区个数
- 遍历，发现K5覆盖的地区最多，将K5覆盖的地区从地区集合中移除。然后将K5放入电台集合中，并更新覆盖地区个数。所有区域都被覆盖，算法结束
5、普里姆算法
算法介绍
普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
最小生成树
- 给定一个带权的无向连通图，使树上所有边上权的总和为最小，这叫最小生成树。
- N个顶点，一定有N-1条边
- 包含全部顶点
- N-1条边都在图中
- 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
应用场景
-
胜利乡有7个村庄(A,B,C,D,E,F,G)，现在需要修路把7个村庄连通
-
各个村庄的距离用边线表示(权)，比如A-B距离5公里
-
问: 如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
思路: 将10条边连接即可，但是总的里程数不是最小
正确思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少
图解分析:
-
从顶点开始处理 ====> <A,G> 2
A-C[7] A-G[2] A-B[5] =>
-
<A,G>开始，将A和G顶点和他们相邻的还没有访问的顶点进行处理=><A,G,B>
A-C[7] A-B[5] G-B[3] G-E[4] G-F[6]
-
<A,G,B>开始，将A,G,B顶点和他们相邻的还没有访问的顶点进行处理=><A,G,B,E>
A-C[7] G-E[4] G-F[6] B-D[9]
...........
-
{A,G,B,E} ->F//第4次大循环，对应边<E,F>权值: 5
-
{A,G,B,E,F} ->D//第5次大循环，对应边<F,D>权值: 4
-
{A,G,B,E,F,D} ->C//第6次大循环，对应边<A,C>权值: 7 ===> <A,G,B,E,F,D,C>
代码实现:
public class PrimAlgorithm {
public static void main(String[] args) {
char[] data = new char[]{'A','B','C','D','E','F','G'};
int verxs = data.length;
//连接矩阵的关系使用二维数组表示,10000这个大数,表示连个点不连通
int [][]weight = new int[][] {
{10000,5,7,10000,10000,10000,2},
{5,10000,10000,9,10000,10000,3},
{7,10000,10000,10000,8,10000,10000},
{10000,9,10000,10000,10000,4,10000},
{10000,10000,8,10000,10000,5,4},
{10000,10000,10000,4,5,10000,6},
{2,3,10000,10000,4,6,10000}
} ;
//创建MGraph对象
MGraph graph = new MGraph(verxs);
//创建一个MinTree对象
MinTree minTree = new MinTree();
minTree.createGraph(graph, verxs, data, weight);
//输出
minTree.showGraph(graph);
//测试普利姆算法
minTree.prim(graph, 0);
}
}
//创建最小生成树->村庄的图
class MinTree {
//创建图的邻接矩阵
/**
*
* @param graph 图对象
* @param verxs 图对应的顶点个数
* @param data 图的各个顶点的值
* @param weight 图的邻接矩阵
*/
public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
int i, j;
for (i = 0; i < verxs; i++) {
graph.data[i] = data[i];
for (j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
//显示图的方法
public void showGraph(MGraph graph) {
for (int[] link : graph.weight) {
System.out.println(Arrays.toString(link));
}
}
//编写prim算法, 得到最小生成树
/**
*
* @param graph 图
* @param v 表示从图的第几个顶点开始生成'A'->0 'B'->1...
*/
public void prim(MGraph graph, int v) {
//visited[] 标记节点(顶点)是否被访问过
int visited[] = new int[graph.verxs];
//把当前这个节点标记为已访问
visited[v] = 1;
//h1 和h2记录两个顶点的下标
int h1 = -1;
int h2 = -1;
int minWeight = 10000;//将minWeight初始成一个大数, 后面在遍历过程中会被替换
for (int k = 1; k < graph.verxs; k++) {//因为有graph.verxs顶点,普利姆算法结束后, 有graph.verxs-1边
//这个是确定每一次生成的子图,和哪个节点的距离最近
for (int i = 0; i < graph.verxs; i++) {//i节点表示被访问过的节点
for (int j = 0; j < graph.verxs; j++) {//j节点表示还没有访问过的节点
if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
//替换minWeight(寻找已经访问过的节点和未访问过的节点间的权值最小的边)
minWeight = graph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
//找到一条边是最小
System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" +minWeight);
//将当前这个节点标记为已经访问
visited[h2] = 1;
//minWeight 重新设置为最大值10000
minWeight = 10000;
}
}
}
class MGraph {
int verxs; //表示图的节点个数
char[] data; //存放节点数据
int[][] weight; //存放边, 这是我们的邻接矩阵
public MGraph(int verxs) {
this.verxs = verxs;
data = new char[verxs];
weight = new int[verxs][verxs];
}
}
运行结果:
[10000, 5, 7, 10000, 10000, 10000, 2] [5, 10000, 10000, 9, 10000, 10000, 3] [7, 10000, 10000, 10000, 8, 10000, 10000] [10000, 9, 10000, 10000, 10000, 4, 10000] [10000, 10000, 8, 10000, 10000, 5, 4] [10000, 10000, 10000, 4, 5, 10000, 6] [2, 3, 10000, 10000, 4, 6, 10000] 边<A,G> 权值:2 边<G,B> 权值:3 边<G,E> 权值:4 边<E,F> 权值:5 边<F,D> 权值:4 边<A,C> 权值:7 Process finished with exit code 0
6、克鲁斯卡尔算法
算法介绍
- 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
- 基本思想: 按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
- 具体做法: 首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
应用场景-公交站问题
- 某城市新增7个站点(A,B,C,D,E,F,G)，现在需要修路把7个站点连通
- 各个站点的距离用边线表示(权)，比如A-B距离12公里
- 问: 如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
克鲁斯卡尔算法图解
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
例如: 对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
假设用数组R保存最小生成树结果
-
第1步: 将边<E,F>加入R中
边<E,F>的权值最小，因此将它加入到最小生成树结果R中
-
第2步: 将边<C,D>加入R中
上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中
-
第3步: 将边<D,E>加入R中
上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中
-
第4步: 将边<B,F>加入R中
上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路; 因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中
-
第5步: 将边<E,G>加入R中
上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中
-
第6步: 将边<A,B>加入R中
上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路; 因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中
此时，最小生成树构造完成，它包括的边依次是: <E,F> <C,D> <D,E> <B,F> <E,G> <A,B>
克鲁斯卡尔算法分析
根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到克鲁斯卡尔算法重点需要解决的以下两个问题:
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一很好解决，采用排序算法进行排序即可
问题二处理方式是: 记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。
在将<E,F> <C,D> <D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点:
- C的终点是F
- D的终点是F
- E的终点是F
- F的终点是F
关于终点的说明:
- 就是将所有顶点按照从小到大的顺序排列好之后，某个顶点的终点就是"与它连通的最大顶点"。
- 因此，接下来虽然<C,E>是权值最小的边，但是C和E的终点都是F，即他们的终点相同，因此，将<C,E>加入最小生成树的话会形成回路。这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路。
代码实现:
public class KruskalCase {
private int edgeNum;//边的个数
private char[] vertexs;//顶点数组
private int[][] matrix;//邻接矩阵
//使用INF表示两个顶点不能连通
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertexs = new char[]{'A','B','C','D','E','F','G'};
//克鲁斯卡尔算法的邻接矩阵
int matrix[][] = {
//'A','B','C','D','E','F','G'
{0, 12, INF, INF, INF, 16, 14},//A
{12, 0, 10, INF, INF, 7, INF},//B
{INF, 10, 0, 3, 5, 6, INF},//C
{INF, INF, 3, 0, 4, INF, INF},//D
{INF, INF, 5, 4, 0, 2, 8},//E
{16, 7, 6, INF, 2, 0, 9},//F
{14, INF, INF, INF, 8, 9, 0}//G,
};
//创建一个克鲁斯卡尔对象实例
KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
//输出
kruskalCase.print();
EData[] edges = kruskalCase.getEdges();
System.out.println("排序前=" + Arrays.toString(edges));
kruskalCase.sortEdges(edges);
System.out.println("排序后=" + Arrays.toString(edges));
//输出构建的
kruskalCase.kruskal();
}
//构造器
public KruskalCase(char[] vertexs, int[][] matrix) {
//初始化顶点数和边的个数
int vlen = vertexs.length;
//初始化顶点, 复制拷贝的方式
this.vertexs = new char[vlen];
for (int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexs[i];
}
//初始化边, 使用的是复制拷贝的方式
this.matrix = new int[vlen][vlen];
for (int i = 0; i < vlen; i++) {
for (int j = 0; j < vlen; j++) {
this.matrix[i][j] = matrix[i][j];
}
}
//统计边的条数
for (int i = 0; i < vlen; i++) {
for (int j = i + 1; j < vlen; j++) {
if (this.matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
public void kruskal() {
int index = 0;//表示最后结果数组的索引
int[] ends = new int[edgeNum];//用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
//创建结果数组,保存最后的最小生成树
EData[] rets = new EData[edgeNum];
EData[] edges = getEdges();
System.out.println("图的边的集合=" +Arrays.toString(edges) + " 共" +edges.length);//12
//按照边的权值大小进行排序(从小到大)
sortEdges(edges);
//遍历edges 数组,将边添加到最小生成树中时,判断是准备加入的边是否形成了回路,如果没有 就加入rets,否则不能加入
for (int i = 0; i < edgeNum; i++) {
//获取到第i条边的第一个顶点(起点)
int p1 = getPosition(edges[i].start);//p1=4
//获取到第i条边的第2个顶点
int p2 = getPosition(edges[i].end);//p2=5
//获取p1这个顶点在已有最小生成树中的终点
int m = getEnd(ends, p1);//m=4
//获取p2这个顶点在已有最小生成树中的终点
int n = getEnd(ends, p2);//n=5
//是否构成回路
if (m != n) {//没有构成回路
ends[m] = n;//设置m 在"已有最小生成树"中的终点<E,F>[0,0,0,0,5,0,0,0,0,0,0,0]
rets[index++] = edges[i];//有一条边接入到rets数组
}
}
//统计并打印"最小生成树",输出rets
System.out.println("最小生成树为:");
for (int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
//打印邻接矩阵
public void print() {
System.out.println("邻接矩阵为:");
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.printf("%12d", matrix[i][j]);
}
System.out.println();
}
}
/**
* 对边进行排序处理 冒泡排序
* @param edges 边的集合
*/
private void sortEdges(EData[] edges) {
for (int i = 0; i < edges.length - 1; i++) {
for (int j = 0; j < edges.length - 1; j++) {
if (edges[j].weight > edges[j+1].weight) {
EData tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
/**
*
* @param ch 顶点的值,比如'A','B'
* @return 返回ch顶点对应的下标,如果找不到,返回-1
*/
private int getPosition(char ch) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == ch) {//找到
return i;
}
}
//找不到,返回-1
return -1;
}
/**
* 功能: 获取图中边,放到EData[] 数组中,后面我们需要遍历数组
* 是通过matrix 邻接矩阵来获取
* EData[] 形式[['A','B',12],['B','F',7].....]
* @return
*/
private EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (matrix[i][j] != INF) {
edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges;
}
/**
* 获取下标为i的顶点的终点, 用于后面判断两个顶点的终点是否相同
* @param ends 数组就是记录了各个顶点对应的终点是哪个,ends数组是在遍历过程中,逐步形成
* @param i 表示传入的顶点对应的下标
* @return 返回的就是 下标为i的这个顶点对应的终点的下标
*/
private int getEnd(int[] ends, int i) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
}
//创建一个EData类, 它的对象实例就表示一条边
class EData {
char start;//边的一个点
char end;//边的另外一个点
int weight;//边的权值
//构造器
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
//输出边信息
@Override
public String toString() {
return "EData[<" +
start +
", " + end +
">=" + weight +
']';
}
}
运行结果:
邻接矩阵为:
0 12 2147483647 2147483647 2147483647 16 14
12 0 10 2147483647 2147483647 7 2147483647
2147483647 10 0 3 5 6 2147483647
2147483647 2147483647 3 0 4 2147483647 2147483647
2147483647 2147483647 5 4 0 2 8
16 7 6 2147483647 2 0 9
14 2147483647 2147483647 2147483647 8 9 0
排序前=[EData[<A, B>=12], EData[<A, F>=16], EData[<A, G>=14], EData[<B, C>=10], EData[<B, F>=7], EData[<C, D>=3], EData[<C, E>=5], EData[<C, F>=6], EData[<D, E>=4], EData[<E, F>=2], EData[<E, G>=8], EData[<F, G>=9]]
排序后=[EData[<E, F>=2], EData[<C, D>=3], EData[<D, E>=4], EData[<C, E>=5], EData[<C, F>=6], EData[<B, F>=7], EData[<E, G>=8], EData[<F, G>=9], EData[<B, C>=10], EData[<A, B>=12], EData[<A, G>=14], EData[<A, F>=16]]
图的边的集合=[EData[<A, B>=12], EData[<A, F>=16], EData[<A, G>=14], EData[<B, C>=10], EData[<B, F>=7], EData[<C, D>=3], EData[<C, E>=5], EData[<C, F>=6], EData[<D, E>=4], EData[<E, F>=2], EData[<E, G>=8], EData[<F, G>=9]] 共12
最小生成树为:
EData[<E, F>=2]
EData[<C, D>=3]
EData[<D, E>=4]
EData[<B, F>=7]
EData[<E, G>=8]
EData[<A, B>=12]
Process finished with exit code 0
7、迪杰斯特拉算法
算法介绍
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其它结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点位置。
算法过程
设置出发顶点为v，顶点集合V{v1,v2,vi...}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di...}，Dis集合记录着v到图中各顶点的距离(到自身可以看做0，v到vi距离对应为di)
- 从Dis中选择值最小的di并移出Dis集合，同时移出V集合中对应的顶点vi，此时的v到vi即为最短路径
- 更新Dis集合，更新规则为: 比较v到V集合中顶点的距离值，与v通过vi到V集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱结点为vi，表明是通过vi到达的)
- 重复执行两步骤，直到最短路径顶点为目标顶点即可结束
应用场景-最短路径问题
- 战争时期，胜利乡有7个村庄(A,B,C,D,E,F,G)，现在有6个邮差，从G出发，需要分别把邮件分别送到A,B,C,D,E,F,G六个村庄
- 各个村庄的距离用边线表示(权)，比如A-B距离为5公里
- 问: 如何计算出G村庄到其它各个村庄的最短距离?
- 如果从其它点出发到各个点的最短距离又是多少?
图解:
代码实现:
public class DijkstraAlgorithm {
public static void main(String[] args) {
char[] vertex = {'A','B','C','D','E','F','G'};
//邻接矩阵
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;//表示不可以连接
matrix[0] = new int[]{N,5,7,N,N,N,2};
matrix[1] = new int[]{5,N,N,9,N,N,3};
matrix[2] = new int[]{7,N,N,N,8,N,N};
matrix[3] = new int[]{N,9,N,N,N,4,N};
matrix[4] = new int[]{N,N,8,N,N,5,4};
matrix[5] = new int[]{N,N,N,4,5,N,6};
matrix[6] = new int[]{2,3,N,N,4,6,N};
//创建Graph对象
Graph graph = new Graph(vertex, matrix);
//输出图矩阵
graph.showGraph();
//测试地杰斯特拉算法
graph.dsj(6);
graph.showDijkstra();
}
}
class Graph {
private char[] vertex;//顶点数组
private int[][] matrix;//邻接矩阵
private VisitedVertex vv;//已经访问的顶点的集合
public Graph(char[] vertex, int[][] matrix) {
this.vertex = vertex;
this.matrix = matrix;
}
//显示结果
public void showDijkstra() {
vv.show();
}
//显示图
public void showGraph() {
for (int[] link: matrix) {
System.out.println(Arrays.toString(link));
}
}
//迪杰斯特拉算法
/**
*
* @param index 表示出发顶点对应的下标
*/
public void dsj(int index) {
vv = new VisitedVertex(vertex.length, index);
update(index);//更新index顶点到周围顶点的距离和前驱顶点
for (int j = 1; j < vertex.length; j++) {
index = vv.updateArr();//选择并返回新的访问顶点
update(index);//更新index顶点到周围顶点的距离和前驱顶点
}
}
//更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
private void update(int index) {
int len = 0;
//根据遍历我们的邻接矩阵的matrix[index]行
for (int j = 0; j < matrix[index].length; j++) {
//len含义是:出发顶点到index顶点的距离 + 从index顶点到j顶点的距离和
len = vv.getDis(index) + matrix[index][j];
//如果j顶点没有被访问过,并且len小于出发顶点到j顶点的距离,就需要更新
if (!vv.in(j) && len < vv.getDis(j)) {
vv.updatePre(j, index);//更新j顶点的前驱为index顶点
vv.updateDis(j, len);//更新出发顶点到j顶点的距离
}
}
}
}
//已访问顶点集合
class VisitedVertex {
//记录各个顶点是否访问过 1表示访问过,0未访问 会动态更新
public int[] already_arr;
//每个下标对应的值为前一个顶点下标,会动态更新
public int[] pre_visited;
//记录出发顶点到其它所有顶点的距离,比如G为出发顶点,就回记录G到其它顶点的距离,会动态更新,求的最短距离就回存放到dis
public int[] dis;
/**
*构造器
* @param length 表示顶点的个数
* @param index 出发顶点对应的下标, 比如G顶点, 下标就是6
*/
public VisitedVertex(int length, int index) {
this.already_arr = new int[length];
this.pre_visited = new int[length];
this.dis = new int[length];
//初始化dis数组
Arrays.fill(dis, 65535);
this.already_arr[index] = 1;
this.dis[index] = 0;//设置出发顶点的访问距离为0
}
/**
* 功能: 判断index顶点是否被访问过
* @param index
* @return 如果访问过就返回true, 否则访问false
*/
public boolean in(int index) {
return already_arr[index] == 1;
}
/**
* 更新出发顶点到index顶点距离
* @param index
* @param len
*/
public void updateDis(int index, int len) {
dis[index] = len;
}
/**
* 更新pre这个顶点的前驱为index节点
* @param pre
* @param index
*/
public void updatePre(int pre, int index) {
pre_visited[pre] = index;
}
/**
* 返回出发顶点到index顶点的距离
* @param index
*/
public int getDis(int index) {
return dis[index];
}
/**
* 继续选择并返回新的访问顶点, 比如这里的G完后, 就是A点作为新的访问顶点(注意不是出发顶点)
* @return
*/
public int updateArr() {
int min = 65535, index = 0;
for (int i = 0; i < already_arr.length; i++) {
if (already_arr[i] == 0 && dis[i] < min) {
min = dis[i];
index = i;
}
}
//更新index顶点被访问过
already_arr[index] = 1;
return index;
}
//显示最后的结果
//将三个数组的情况输出
public void show() {
System.out.println("=====================");
//输出already_arr
for (int i : already_arr) {
System.out.print(i + " ");
}
System.out.println();
//输出apre_visited
for (int i : pre_visited) {
System.out.print(i + " ");
}
System.out.println();
//输出dis
for (int i : dis) {
System.out.print(i + " ");
}
System.out.println();
//为了好看最后的最短距离 处理
char[] vertex = {'A','B','C','D','E','F','G'};
int count = 0;
for (int i : dis) {
if (i != 65535) {
System.out.print(vertex[count] + "(" + i + ")");
} else {
System.out.println("N ");
}
count++;
}
System.out.println();
}
}
运行结果:
[65535, 5, 7, 65535, 65535, 65535, 2] [5, 65535, 65535, 9, 65535, 65535, 3] [7, 65535, 65535, 65535, 8, 65535, 65535] [65535, 9, 65535, 65535, 65535, 4, 65535] [65535, 65535, 8, 65535, 65535, 5, 4] [65535, 65535, 65535, 4, 5, 65535, 6] [2, 3, 65535, 65535, 4, 6, 65535] ===================== 1 1 1 1 1 1 1 6 6 0 5 6 6 0 2 3 9 10 4 6 0 A(2)B(3)C(9)D(10)E(4)F(6)G(0) Process finished with exit code 0
8、弗洛伊德算法
算法介绍
- 和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特•弗洛伊德命名
- 弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
- 迪杰斯特拉算法用于计算图中某一个顶点到其它顶点的最短路径
- 弗洛伊德算法VS迪杰斯特拉算法: 迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其它顶点的最短路径；弗洛伊德算法中每一个顶点都是出发访问顶点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其它顶点的最短路径。
分析
- 设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为: min((Lik+Lkj),Lij)，vk的取值为图中所有顶点，则可获得vi到vj的最短路径
- 至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj,是以同样的方式获得
弗洛伊德(Floyd)算法最佳应用-最短路径
- 胜利乡有7个村庄(A,B,C,D,E,F,G)
- 各个村庄的距离用边线表示(权)，比如A-B距离为5公里
- 问: 如何计算出各村庄到其它各个村庄的最短距离?
代码实现:
public class FloryAlgorithm {
public static void main(String[] args) {
//测试图是否创建成功
char[] vertex = {'A','B','C','D','E','F','G'};
//创建邻接矩阵
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[]{0,5,7,N,N,N,2};
matrix[1] = new int[]{5,0,N,9,N,N,3};
matrix[2] = new int[]{7,N,0,N,8,N,N};
matrix[3] = new int[]{N,9,N,0,N,4,N};
matrix[4] = new int[]{N,N,8,N,0,5,4};
matrix[5] = new int[]{N,N,N,4,5,0,6};
matrix[6] = new int[]{2,3,N,N,4,6,0};
//创建Graph对象
Graph graph = new Graph(vertex.length, matrix, vertex);
//输出图矩阵
System.out.println("输出图矩阵:");
graph.show();
//调用弗洛伊德算法
System.out.println("调用弗洛伊德算法");
graph.floyd();
graph.show();
}
}
class Graph {
private char[] vertex;//存放顶点的数组
private int[][] dis;// 保存,从各个顶点出发到其它顶点的距离,最后的结果,也是保留在该数组
private int[][] pre;// 保存到达目标顶点的前驱结点
//构造器
public Graph(int length, int[][] matrix, char[] vertex) {
this.vertex = vertex;
this.dis = matrix;
this.pre = new int[length][length];
//对pre数组初始化,注意存放的是前驱顶点的下标
for (int i = 0; i < length; i++) {
Arrays.fill(pre[i], i);
}
}
//显示pre数组和dis数组
public void show() {
char[] vertex = {'A','B','C','D','E','F','G'};
for (int k = 0; k < dis.length; k++) {
//先将pre数组输出的一行
for (int i = 0; i < dis.length; i++) {
System.out.print(vertex[pre[k][i]] + " ");
}
System.out.println();
for (int i = 0; i < dis.length; i++) {
System.out.print("("+vertex[k] +"到" + vertex[i] + "的最短路径是:" + dis[k][i] + ") ");
}
System.out.println();
}
}
//弗洛伊德算法
public void floyd() {
int len = 0;//变量保存距离
//对中间顶点遍历, k就是中间顶点的下标[A,B,C,D,E,F,G]
for (int k = 0; k < dis.length; k++) {
//从i顶点开始出发[A,B,C,D,E,F,G]
for (int i = 0; i < dis.length; i++) {
//到达j顶点 [A,B,C,D,E,F,G]
for (int j = 0; j < dis.length; j++) {
len = dis[i][k] + dis[k][j];//=>求出从i顶点出发,经过k中间顶点,到达j顶点距离
if (len < dis[i][j]) {//如果len小于dis[i][j]
dis[i][j] = len;//更新距离
pre[i][j] = pre[k][j];//更新前驱顶点
}
}
}
}
}
}
运行结果:
输出图矩阵: A A A A A A A (A到A的最短路径是:0) (A到B的最短路径是:5) (A到C的最短路径是:7) (A到D的最短路径是:65535) (A到E的最短路径是:65535) (A到F的最短路径是:65535) (A到G的最短路径是:2) B B B B B B B (B到A的最短路径是:5) (B到B的最短路径是:0) (B到C的最短路径是:65535) (B到D的最短路径是:9) (B到E的最短路径是:65535) (B到F的最短路径是:65535) (B到G的最短路径是:3) C C C C C C C (C到A的最短路径是:7) (C到B的最短路径是:65535) (C到C的最短路径是:0) (C到D的最短路径是:65535) (C到E的最短路径是:8) (C到F的最短路径是:65535) (C到G的最短路径是:65535) D D D D D D D (D到A的最短路径是:65535) (D到B的最短路径是:9) (D到C的最短路径是:65535) (D到D的最短路径是:0) (D到E的最短路径是:65535) (D到F的最短路径是:4) (D到G的最短路径是:65535) E E E E E E E (E到A的最短路径是:65535) (E到B的最短路径是:65535) (E到C的最短路径是:8) (E到D的最短路径是:65535) (E到E的最短路径是:0) (E到F的最短路径是:5) (E到G的最短路径是:4) F F F F F F F (F到A的最短路径是:65535) (F到B的最短路径是:65535) (F到C的最短路径是:65535) (F到D的最短路径是:4) (F到E的最短路径是:5) (F到F的最短路径是:0) (F到G的最短路径是:6) G G G G G G G (G到A的最短路径是:2) (G到B的最短路径是:3) (G到C的最短路径是:65535) (G到D的最短路径是:65535) (G到E的最短路径是:4) (G到F的最短路径是:6) (G到G的最短路径是:0) 调用弗洛伊德算法 A A A F G G A (A到A的最短路径是:0) (A到B的最短路径是:5) (A到C的最短路径是:7) (A到D的最短路径是:12) (A到E的最短路径是:6) (A到F的最短路径是:8) (A到G的最短路径是:2) B B A B G G B (B到A的最短路径是:5) (B到B的最短路径是:0) (B到C的最短路径是:12) (B到D的最短路径是:9) (B到E的最短路径是:7) (B到F的最短路径是:9) (B到G的最短路径是:3) C A C F C E A (C到A的最短路径是:7) (C到B的最短路径是:12) (C到C的最短路径是:0) (C到D的最短路径是:17) (C到E的最短路径是:8) (C到F的最短路径是:13) (C到G的最短路径是:9) G D E D F D F (D到A的最短路径是:12) (D到B的最短路径是:9) (D到C的最短路径是:17) (D到D的最短路径是:0) (D到E的最短路径是:9) (D到F的最短路径是:4) (D到G的最短路径是:10) G G E F E E E (E到A的最短路径是:6) (E到B的最短路径是:7) (E到C的最短路径是:8) (E到D的最短路径是:9) (E到E的最短路径是:0) (E到F的最短路径是:5) (E到G的最短路径是:4) G G E F F F F (F到A的最短路径是:8) (F到B的最短路径是:9) (F到C的最短路径是:13) (F到D的最短路径是:4) (F到E的最短路径是:5) (F到F的最短路径是:0) (F到G的最短路径是:6) G G A F G G G (G到A的最短路径是:2) (G到B的最短路径是:3) (G到C的最短路径是:9) (G到D的最短路径是:10) (G到E的最短路径是:4) (G到F的最短路径是:6) (G到G的最短路径是:0) Process finished with exit code 0
这篇关于数据结构算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
栏目导航
