一、稀疏数组
1. 样式
解析: 第一行 代表整个矩阵的行/列/非0数值个数
第二行 代表第0行非0数值的坐标和值
2. 思路分析
3. 代码实现
package com.atguigu.sparseArray;
public class sparseArray {
public static void main(String[] args){
// 创建二维数组,11*11
// 0代表没有,1代表黑子,2代表篮子
int[][] chessArray= new int[11][11];
chessArray[1][2]=1;
chessArray[2][3]=2;
// 输出原始的二维数组
System.out.println("原始的二维数组:");
for(int[] row:chessArray){
for(int data:row){
System.out.printf("%d\t",data);
}
System.out.println();
}
// 把二维数组转为稀疏数组
// 1. 先遍历二维数组得到非0数据的个数
int sum=0;
for (int i = 0; i < chessArray.length; i++) {
for (int j = 0; j < chessArray[i].length; j++) {
if(chessArray[i][j]!=0){
sum++;
}
}
}
// 2. 创建对应的稀疏数组
int[][] sparseArr = new int[sum+1][3];
// 3. 给稀疏数组赋值
sparseArr[0][0]=11;
sparseArr[0][1]=11;
sparseArr[0][2]=sum;
// 4. 遍历二维数组,将非0的值传入稀疏数组中
int count=0; // 用于记录第几个非0数据
for (int i = 0; i < chessArray.length; i++) {
for (int j = 0; j < chessArray[i].length; j++) {
if(chessArray[i][j]!=0){
count++;
sparseArr[count][0]=i;
sparseArr[count][1]=j;
sparseArr[count][2]=chessArray[i][j];
}
}
}
// 5. 输出稀疏数组的形式
System.out.println("得到的稀疏数组为如下形式:");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}
// 6. 将稀疏数组恢复为原始的二维数组
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
// 7. 打印恢复后的原数组
System.out.println("打印恢复后的原数组:");
for(int[] row:chessArr2){
for(int data:row){
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
4. 扩充:把数据保存在磁盘上(IO)
二、队列
0. 常用的场景及处理逻辑
0.1 使用场景
一般情况下,如果是对一些及时消息的处理,并且处理时间很短的情况下是不需要队列的,直接阻塞式的方法调用就可以了。但是如果在消息处理的时候特别费时间,这个时候如果有新消息来了,就只能处于阻塞状态,造成用户等待。这个时候便需要引入队列了。当接收到消息后,先把消息房贷队列中,然后再用行的线程进行处理,这个时候就不会有消息阻塞了。
0.2 队列主要应用在下面几种场景
• 队列用于异步数据传输(例如,数据不以两个进程之间的相同速率传输)。 管道,文件IO,套接字。
• 队列在大多数应用程序中用作缓冲区,如MP3媒体播放器,CD播放器等。
• 队列用于维护媒体播放器中的播放列表,以便添加和删除播放列表中的歌曲。
• 队列在操作系统中用于处理中断。
[
](https://blog.csdn.net/weixin_49561445/article/details/113752408)
1. 基本介绍
2. 数组模拟队列
获取键盘输入:
Scanner scan= new Scanner(System.in)
key = scan.next().charAt(0); //接收一个字符
package com.atguigu.queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
// 测试新建的类
// 创建实例
ArrayQueue queue = new ArrayQueue(3);
// 接收用户输入
char key = ' ';
Scanner scanner = new Scanner(System.in);
boolean loop = true;
// 输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列中获取数据");
System.out.println("h(head):查找队列头的数据");
key = scanner.next().charAt(0); //接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出数据
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
// 使用数组模拟队列--编写一个ArrayQueue类
class ArrayQueue {
private int maxSize; //表示数组的最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 该数据用于存储数据,模拟队列
// 创建队列的构造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; // 初始化,指向队列头部的前一个位置
rear = -1; // 初始化,指向队尾的数据(即:队列最后一个数据)
}
// 判断队列是否满
public boolean isFull() {
return rear == maxSize-1;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
// 添加数据到队列
public void addQueue(int n) {
// 首先判断队列是否满
if (isFull()) {
System.out.println("队列满,不能添加数据!");
return;
}
rear++; //让rear后移,添加数据
arr[rear] = n;
}
// 出队列,从前端获取数据
public int getQueue() {
// 判断队列是否为空
if (isEmpty()) {
// 通过抛出异常来处理
throw new RuntimeException("队列为空,不能获取数据");
}
front++;
return arr[front];
}
// 显示队列的所有数据
public void showQueue() {
// 遍历
if (isEmpty()) {
System.out.println("队列空的,没有数据~~");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// 显示队列的头数据,注意不是取出数据
public int headQueue() {
// 判断
if (isEmpty()) {
throw new RuntimeException("队列空的,没有数据~~");
}
return arr[front + 1];
}
}
2.1 当前问题
当数组填充完数据,取完值之后,数据不可以再次使用,因为front和rear都到了maxSize的下标处,添加数据时,会显示数据已满;
2.2 解决办法—-环形数列
文章链接:https://blog.csdn.net/victor_cindy1/article/details/46604575
思路如下:
1. front变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
2. rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.rear 的初始值 = 0
3. 当队列满时,条件是 (rear + 1) % maxSize == front 【满】
4. 对队列为空的条件, rear == front 空
5. 当我们这样分析, 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
6. 我们就可以在原来的队列上修改得到,一个环形队列
2.3 环形数列的代码实现
package com.atguigu.queue;
import java.util.Scanner;
public class CircleArrayQueue {
public static void main(String[] args) {
System.out.println("测试数组模拟环形队列的案例");
CircleArray queue = new CircleArray(3);
// 接收用户输入
char key;
Scanner scanner = new Scanner(System.in);
boolean loop = true;
// 输出一个菜单
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列中获取数据");
System.out.println("h(head):查找队列头的数据");
key = scanner.next().charAt(0); //接收一个字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': //取出数据
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': //查看队列头的数据
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': //退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
class CircleArray{
private int maxSize; //表示数组的最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 该数据用于存储数据,模拟队列
public CircleArray(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// 判断是否满
public boolean isFull() {
return (rear+1) % maxSize==front;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
// 添加数据到队列
public void addQueue(int n) {
// 首先判断队列是否满
if (isFull()) {
System.out.println("队列满,不能添加数据!");
return;
}
arr[rear] = n;
rear=(rear+1)%maxSize;
}
// 出队列,从前端获取数据
public int getQueue() {
// 判断队列是否为空
if (isEmpty()) {
// 通过抛出异常来处理
throw new RuntimeException("队列为空,不能获取数据");
}
// 这里的front是指向队列的第一个元素
// 1. 先把front的对应的值保存到一个临时变量
// 2. 将front后移,考虑取模
// 3. 将临时保存的变量返回
int value=arr[front];
front=(front+1)%maxSize;
return value;
}
// 显示队列的所有数据
public void showQueue() {
// 遍历
if (isEmpty()) {
System.out.println("队列空的,没有数据~~");
return;
}
// 思路:从front开始遍历,遍历多少个元素?
for (int i = front; i < front+size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// 求出当前队列有效数据的个数
public int size(){
return (rear+maxSize-front)%maxSize;
}
// 显示队列的头数据,注意不是取出数据
public int headQueue() {
// 判断
if (isEmpty()) {
throw new RuntimeException("队列空的,没有数据~~");
}
return arr[front]; // 由-1的下标移向下标为0的地方
}
}
三、链表(Linked list)
1. 不考虑顺序的单链表代码实现
package com.atguigu.LinkedList;
public class SingleLinkedListDemo {
public static void main(String[] args) {
// 进行测试
// 先创建节点
HeroNode hero1=new HeroNode(1, "宋江", "及时雨");
HeroNode hero2=new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3=new HeroNode(3, "吴用", "智多星");
HeroNode hero4=new HeroNode(4, "林冲", "豹子头");
// 创建链表
SingleLinkedList list=new SingleLinkedList();
list.add(hero1);
list.add(hero2);
list.add(hero3);
list.add(hero4);
// 显示数据
list.list();
}
}
// 定义一个SingleLinkedList来管理HeroNode
class SingleLinkedList{
// 先初始化头节点,不要动
private HeroNode head = new HeroNode(0,"","");
// 添加节点到单向链表
// 思路: 当不考虑编号顺序的时候:
// 1. 找到当前链表的最后一个节点 2. 令最后一个节点的next指向新的节点
public void add(HeroNode heroNode){
// 因为head节点不能动,因此需要一个辅助变量
HeroNode temp=head;
// 遍历链表,找到最后
while(true){
// 找到链表的最后
if(temp.next==null){
break;
}
// 如果没有找到最后,就将temp后移
temp=temp.next;
}
// 当退出while循环时,temp就指向了链表的最后
temp.next=heroNode;
}
// 显示链表【遍历】
public void list(){
if(head.next==null){
System.out.println("链表为空");
return;
}
// 因为头节点不能动,需要引入新的临时变量node
HeroNode temp=head.next;
while(true){
// 判断是否到了链表最后
if(temp==null){
break;
}
// 输出节点信息
System.out.println(temp);
// 将next后移
temp = temp.next;
}
}
}
// 定义一个HeroNode类,每个heroNode就是一个节点
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode next; //指向下一个节点
// 构造器
public HeroNode(int hNo,String hName,String hNickName){
this.name=hName;
this.nickName=hNickName;
this.no=hNo;
}
// 为了显示方便,重写toString方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
2. 按按照英雄编号要求,添加新的英雄
// 第二种添加方法:根据排名将英雄添加到指定顺序
// 如果有这个排名,则添加失败,并给出提示信息
public void addByOrder(HeroNode node){
// 因为头节点不能动,所以需要一个辅助变量帮助
// 因为是单链表,我们找的temp是位于添加位置的前一个节点,否则加不进去
HeroNode temp=head;
boolean flag=false; //标识添加的编号是否存在,默认是false
while(true) {
if(temp.next == null) {
//说明temp已经在链表最后
break;
}
if (temp.next.no > node.no) {
// 说明temp指向的节点在目标节点之前,那么就在temp后面添加
break;
} else if (temp.no == node.no) {
flag = true;
// System.out.println("当前节点已存在,无法添加!");
}
temp=temp.next;
}
// 判断flag
if(flag){
System.out.println("想添加的英雄编号已存在,不能再添加!");
}else{
//插入到链表中,在当前节点之后
node.next=temp.next;
temp.next=node;
}
}
3. 修改英雄信息
// 根据编号修改节点信息
public void update(HeroNode node){
// 判断列表是否为空
if(head.next==null){
System.out.println("链表为空,不能修改");
return;
}
// 找到需要修改的节点,编号为no
// 定义一个辅助变量
HeroNode temp=head;
boolean flag=false;
while(true){
if(temp.next==null){
break; //已经遍历完列表
}
if(temp.no==node.no){
// 说明找到了
flag=true;
break;
}
temp=temp.next;
// 根据flag判断是否找到了要修改的节点
if(flag){
temp.name=node.name;
temp.no=node.no;
}else{
System.out.printf("没有找到编号为%d 的节点,其对应的节点名为:%d",node.no,node.name);
}
}
}
4. 删除节点
// 删除节点的代码
public void delete(HeroNode node){
HeroNode temp=head;
boolean flag=false;
while(true){
if(temp.next==null){
// 说明已经到了链表最后了
break;
}
if(temp.next.no==node.no){
// 说明找到了待删节点的前一个节点temp
flag=false;
break;
}
temp=temp.next;
}
// 判断flag
if(flag){
temp.next=temp.next.next;
}else {
System.out.printf("要删除的节点%d 不存在",node.no);
}
}
5. 统计节点个数
// 获取单链表的节点的个数
// 如果是带头节点的链表,需要不统计头节点
/**
*
* @param head
* @return 返回的就是有效节点的个数
*/
public int getLength(HeroNode head){
if(head.next==null){
return 0;
}
int length=0;
// 定义一个辅助标量
HeroNode cur =head.next;
while (cur!=null){
length++;
cur=cur.next;
}
return length;
}
6. 查找单链表中倒数第n个节点
/**
* 查找单链表中倒数第n个节点
* @param head:head节点
* @param index:倒数第n个节点
* @return
*/
public HeroNode getTargetNode(HeroNode head,int index){
/**
* 思路:1. 先得到length 2. 遍历length-index次
* */
if(head.next==null){
return null;
}
// 第一次遍历得到长度(size)
int size=getLength(head);
// 第二次遍历size-index次,就是倒数第index个节点
// 先做index校验
if(index<=0||index>size){
return null;
}
// 定义辅助变量
HeroNode temp=head;
for (int i = 0; i < size-index; i++) {
temp=temp.next;
}
return temp;
}
7. 单链表的反转
//将单链表反转
public static void reversetList(HeroNode head) {
//如果当前链表为空,或者只有一个节点,无需反转,直接返回
if(head.next == null || head.next.next == null) {
return ;
}
//定义一个辅助的指针(变量),帮助我们遍历原来的链表
HeroNode cur = head.next; // cur初始化指向原链表第一个节点
HeroNode next = null;// 指向当前节点[cur]的下一个节点
HeroNode reverseHead = new HeroNode(0, "", "");
//遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表reverseHead 的最前端
//动脑筋
while(cur != null) {
next = cur.next;//先暂时保存当前节点的下一个节点,因为后面需要使用
cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
reverseHead.next = cur; //将cur 连接到新的链表上
cur = next;//让cur后移
}
//将head.next 指向 reverseHead.next , 实现单链表的反转,要把原链表的head绑定到新的反转链表中
head.next = reverseHead.next;
}
8. 从尾到头打印单链表
解析: 逆序打印单链表
方式一:先将单链表反转操作,然后再遍历即可。问题是会破坏原来的单链表结构,不建议
方式二:可以利用栈数据结构,将各个节点压入到栈中,然后利用栈的先进后出的特点实现逆序打印效果。
// 方法2:创建一个栈,将各个节点压入栈中
public void reverseByStack(HeroNode head){
if(head.next==null||head.next.next==null){
return;
}
Stack<HeroNode> reverseStack = new Stack<HeroNode>();
HeroNode cur = head.next;
// 将链表的所有节点压入栈中
while (cur!=null){
reverseStack.push(cur);
cur=cur.next;
}
while (reverseStack.size()>0) {
System.out.println(reverseStack.pop());
}
}
四、双向链表
// 删除节点的代码
public void delete(HeroNode2 node){
HeroNode2 temp=head;
boolean flag=false;
while(true){
if(temp==null){
// 说明已经到了链表最后了
break;
}
if(temp.no==node.no){
// 说明找到了待删节点的前一个节点temp
flag=false;
break;
}
temp=temp.next;
}
// 判断flag
if(flag){
temp.pre.next=temp.next;
// 加入删除的是最后一个节点
if(temp.next!=null){
temp.next.pre=temp.pre;
}
}else {
System.out.printf("要删除的节点%d 不存在",node.no);
}
}
// 添加节点到单向链表
// 思路: 当不考虑编号顺序的时候:
// 1. 找到当前链表的最后一个节点 2. 令最后一个节点的next指向新的节点
public void add(HeroNode2 heroNode){
// 因为head节点不能动,因此需要一个辅助变量
HeroNode2 temp=head;
// 遍历链表,找到最后
while(true){
// 找到链表的最后
if(temp.next==null){
break;
}
// 如果没有找到最后,就将temp后移
temp=temp.next;
}
// 当退出while循环时,temp就指向了链表的最后
temp.next=heroNode;
heroNode.pre=temp;
}
五、单向环形链表和约瑟夫问题
1. 问题构建及描述
构建一个单向的环形链表思路
1. 先创建第一个节点, 让 first 指向该节点,并形成环形
2.后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可.
遍历环形链表
1. 先让一个辅助指针(变量) curBoy,指向first节点
2.然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束
Josephu 问题为:设编号为1,2,… n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m 的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下
2. 过程详解
package com.atguigu.LinkedList;
public class Josepfu {
public static void main(String[] args) {
}
}
// 创建环形的单项链表
class CircleSingleLinkedList{
// 创建一个first节点,当前没有编号
private Boy first=new Boy(-1);
// 添加小孩节点,构建成一个环形链表
public void addBoy(int nums){
//给nums做数据校验
if(nums<1){
System.out.println("nums数值不正确");
return;
}
Boy curBoy=null; //帮助构建环形链表
for (int i = 1; i < nums; i++) {
// 根据编号创建小孩儿节点
Boy boy = new Boy(i);
// 如果是第一个小孩儿
if(i==1){
first=boy;
first.setNext(first); // 构建环,第一个next指向自身
curBoy=first; //为了后续的持续添加,first不能动
}else {
curBoy.setNext(boy);
boy.setNext(first); // 尾节点指向第一个节点,形成环
curBoy=boy;
}
}
}
public void showBoy(){
// 判断链表是否为空
if(first==null){
System.out.println("空链表!");
return;
}
// first不能动,因此仍然使用辅助指针进行遍历
Boy curBoy = first;
while (true){
System.out.printf("小孩儿的编号:%d \n",curBoy.getNo());
if(curBoy.getNext()==first){
System.out.println("已经遍历完毕!");
break;
}
curBoy=curBoy.getNext();
}
}
}
// 先创建一个boy类,表示一个节点
class Boy{
private int no;
private Boy next;
public Boy(int no){
this.no=no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
3. 出圈的问题
// 根据用户输入,计算出出圈的顺序
/**
* 根据用户输入,计算出出圈的顺序
* @param startNo 表示从第几个小孩儿开始数
* @param countNum 表示数几下
* @param totalNums 表示最初有几个小孩儿在圈
*/
public void countBoy(int startNo,int countNum,int totalNums){
// 先对数据进行校验
if(first==null|startNo<1||startNo>totalNums){
System.out.println("参数输入有误,请重新输入!");
}
// 创建辅助指针,帮助小孩儿完成出圈
Boy helper = first;
while (true){
if(helper.getNext()==first){
break;
}
helper=helper.getNext();
}
// 报数之前,让helper指向起始位置,即从first位置移动startNo-1次
for (int i = 0; i < startNo-1; i++) {
first=first.getNext();
helper=helper.getNext();
}
// 报数开始后,让helper移动countNum-1次
while(true){
if(helper==first){
break;
}
for (int j = 0; j < countNum-1; j++) {
first=first.getNext();
helper=helper.getNext();
}
// 此时first指向的节点就是要出圈的节点
System.out.printf("小孩儿%d出圈\n",first.getNo());
// 出圈后修改链表
first=first.getNext();
helper.setNext(first);
}
}