【Java数据结构和算法】00
【Java数据结构和算法】00
一、稀疏数组sparsearray1、一个实际的应用场景编写的五子棋程序中，有存盘退出和续上盘的功能：问题分析：因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据，我们这个时候可以使用稀疏数组实现对二维数组的压缩；2、稀疏数组基本介绍当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组；稀疏数组的处理方法：①记录数组一共有
【Java数据结构和算法】00
1、一个实际的应用场景
编写的五子棋程序中，有存盘退出和续上盘的功能：
问题分析：
因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据，我们这个时候可以使用稀疏数组实现对二维数组的压缩；
2、稀疏数组基本介绍
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组；
稀疏数组的处理方法：
①记录数组一共有几行几列，有多少个不同的值 把具有不同值的元素的行列及值；
②记录在一个小规模的数组（稀疏数组）中，从而缩小程序的规模；
、稀疏数组案例
（这个真不错，只是在对数组进行读写的时候需要额外的一步转换操作，这是值得的！）
代码语言：javascript代码运行次数：0运行复制//首元素 ：行数、列数、元素个数
//其他元素：第几行、第几列、值是什么4、稀疏数组转换的思路
①使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)；
②把稀疏数组存盘，并且可以重新恢复原来的二维数组数；
③整体思路分析：
5、二维数组与稀疏数组互转
二维数组转稀疏数组思路分析：
第一步：遍历原二维数组，得到有效数据的个数sum（用来确定首元素的行、列、有效值数量）；
第二步：根据sum创建稀疏数组，行为sum+1行，列为列；
第三步：将二位数组的有效数据，存到稀疏数组；
稀疏数组转二维数组思路分析：
第一步：根据稀疏数组的首元素确定二维数组的行、列和稀疏数组的长度；
第二步：根据已知的行列创建二维数组；
第三步：根据稀疏数组的长度遍历稀疏数组，确定二维数组的元素，赋值给二维数组；
6、稀疏数组与二位数组互转代码实现
二维数组转稀疏数组：
代码演示：
代码语言：javascript代码运行次数：0运行复制package com.zb.ds;
//二维数组转稀疏数组
public class SparseArray {
public static void main(String[] args) {
//创建并初始化二维数组
int[][] nums = new int[4][4];
nums[0] = new int[]{0,0,0,0};
nums[1] = new int[]{0,2,0,0};
nums[2] = new int[]{0,0,7,0};
nums[] = new int[]{0,0,0,0};
//将这个二维数组转换成稀疏数组
//1、获得二维数组有效元素的个数
int sum = 0;
for (int[] num : nums) {
for (int i : num) {
if (i != 0) {
//有效数据
sum++;
}
}
}
//2、创建稀疏数组
int[][] sparseArray = new int[sum+1][];
//、将二维数组的有效元素存到稀疏数组
//首元素
sparseArray[0] = new int[]{nums.length,nums[0].length,sum};
int sum = 0;
//其他元素
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[i].length; j++) {
if(nums[i][j]!=0){
sum++;
sparseArray[sum] = new int[]{i,j,nums[i][j]};
}
}
}
//输出二维数组
println("二维数组：");
for (int[] num : nums) {
for (int i : num) {
print(i + " ");
}
println();
}
//输出稀疏数组
println("稀疏数组：");
for (int[] ints : sparseArray) {
for (int anInt : ints) {
print(anInt + " ");
}
println();
}
}
}运行结果：
稀疏数组转二维数组：
代码演示：
代码语言：javascript代码运行次数：0运行复制package com.zb.ds;
//二维数组转稀疏数组
public class SparseArray {
public static void main(String[] args) {
//创建并初始化二维数组
int[][] nums = new int[4][4];
nums[0] = new int[]{0,0,0,0};
nums[1] = new int[]{0,2,0,0};
nums[2] = new int[]{0,0,7,0};
nums[] = new int[]{0,0,0,0};
//将这个二维数组转换成稀疏数组
//1、获得二维数组有效元素的个数
int sum = 0;
for (int[] num : nums) {
for (int i : num) {
if (i != 0) {
//有效数据
sum++;
}
}
}
//2、创建稀疏数组
int[][] sparseArray = new int[sum+1][];
//、将二维数组的有效元素存到稀疏数组
//首元素
sparseArray[0] = new int[]{nums.length,nums[0].length,sum};
int sum = 0;
//其他元素
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[i].length; j++) {
if(nums[i][j]!=0){
sum++;
sparseArray[sum] = new int[]{i,j,nums[i][j]};
}
}
}
//好的，上面已经将二维数组转化成稀疏数组了，我们就利用这个稀疏数组来演示稀疏数组转化成二维数组的操作
//1、通过稀疏数组的第一行元素，创建二维数组
int[][] nums1 = new int[sparseArray[0][0]][sparseArray[0][1]];
//2、遍历稀疏数组，将对应的值存入二维数组
for (int i = 1; i < sparseArray.length; i++) {
nums1[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
//输出二维数组
println("二维数组：");
for (int[] num : nums) {
for (int i : num) {
print(i + " ");
}
println();
}
//输出稀疏数组
println("稀疏数组：");
for (int[] ints : sparseArray) {
for (int anInt : ints) {
print(anInt + " ");
}
println();
}
//再次输出二维数组
println("二维数组：");
for (int[] num : nums1) {
for (int i : num) {
print(i + " ");
}
println();
}
}
}运行结果：
1、队列的一个使用场景：银行排队
2、队列介绍
①队列是一个有序列表，可以用数组或是链表来实现；
②遵循先入先出的原则；
示意图：
(使用数组模拟队列示意图：空——>添加数据——>取出数据)
添加数据是在队列的尾部添加，取数据是在队列的首部取，也即是先入先出；
、数组模拟队列的思路分析
数组模拟队列：
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量；
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示：
思路分析：
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：
第一步：将尾指针往后移：rear+1 , 当front == rear 【空】（判断当前队列是否是空队列，如果是就没办法存入）；
第二步：若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]（如果但钱队列已经满了，那也无法存入数据）；
代码演示：
代码语言：javascript代码运行次数：0运行复制package com.zb.ds;
//数组模拟队列
public class ArrayQueue {
public static void main(String[] args) {
//创建队列
ArrayQ q = new ArrayQ();
//判断队列是否为空
println(q.isEmpty());
//添加元素到队列
q.addQueue(100);
q.addQueue(99);
q.addQueue(1000);
//判断队列是否满
println(q.isFull());
//取出一个元素
println(q.getQueue());
//偷窥首元素：首元素从100变成了99，因为上面已经把100取出来了！
println(q.headQueue());
//显示队列所有元素
q.show();
//再添加一个元素
q.addQueue(101);
//再取三个元素
println(q.getQueue());
println(q.getQueue());
println(q.getQueue());
}
}
class ArrayQ{
private final int maxSize;//数组最大容量
private int front;//队首
private int rear;//队尾
private final int[] arr;//数组
//队列的构造器
public ArrayQ(int maxSize) {
= maxSize;
arr = new int[maxSize];
front = -1;//队首前面那个下标
rear = -1;//队尾下标
}
//判断队列是否满
public boolean isFull(){
return rear == maxSize-1;
}
//判断队列是否空
public boolean isEmpty(){
return front == rear;
}
//添加数据到队列
public void addQueue(int num){
//判断队列是否满
if(isFull()){
//队列满了
println("添加数据失败，队列满了！");
return;
}
rear++;
arr[rear] = num;
}
//从队列取出数据
public int getQueue(){
//判断是否为空
if(isEmpty()){
throw new RuntimeException("队列为空！");
}
front++;
return arr[front];
}
//显示队列的所有数据
public void show(){
//遍历
if(isEmpty()){
println("队列为空！");
return;
}
for (int value : arr) {
println(value);
}
}
//显示队列头数据
public int headQueue(){
if(isEmpty()){
throw new RuntimeException("队列为空！");
}
return arr[front+1];
}
}运行结果：
代码语言：javascript代码运行次数：0运行复制true
true
100
99
100
99
1000
添加数据失败，队列满了！
99
1000
Exception in thread "main" java.lang.RuntimeException: 队列为空！
at com.zb.ds.ArrayQ.getQueue(ArrayQueue.java:71)
at com.zb.ds.(ArrayQueue.java:27)4、数组模拟环形队列的思路分析
数组模拟环形队列：
前面的数组模拟队列里面的数组只用了一次，很浪费，数组模拟环形队列是对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的(通过取模的方 式来实现即可)；
分析说明：
①尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front+1 [满]（这个要在非空的基础上才成立，如果为空直接返回false）；
②rear == front [空]；
③front和rear默认为-1，front为队首元素的前一个下标，rear为队尾元素下标；
图示：
代码演示：
（我们在之前代码的基础上进行修改，被坑了，但还是解决了！）
代码语言：javascript代码运行次数：0运行复制package com.zb.ds;
//数组模拟队列
public class ArrayQueue {
public static void main(String[] args) {
//创建队列
ArrayQ q = new ArrayQ();
//判断队列是否为空
println(q.isEmpty());
//添加元素到队列
println("添加一个元素：100");
q.addQueue(100);
println("添加一个元素：99");
q.addQueue(99);
println("添加一个元素：1000");
q.addQueue(1000);
println("添加一个元素：2000，这个时候会添加失败，因为满了！");
q.addQueue(2000);
//判断队列是否满
println("这个时候该满了：" + q.isFull());
//取出一个元素
println("取出一个元素：" + q.getQueue());
//偷窥首元素：首元素从100变成了99，因为上面已经把100取出来了！
println("偷窥首元素：" + q.headQueue());
//显示队列所有元素
println("显示队列所有元素：");
q.show();
//再添加一个元素
println("再添加一个元素：101");
q.addQueue(101);
//显示队列所有元素
println("显示队列所有元素：");
q.show();
//这个时候是满的了
println("这个时候是满的了：" + q.isFull());
//再取三个元素
println("再取一个元素：" + q.getQueue());
//此时队列中有效数据的个数
println("此时队列中有效数据的个数为：" + q.getVD());
println("再取一个元素：" + q.getQueue());
println("再取一个元素：" + q.getQueue());
println("再取一个元素：这个时候会取失败，因为空了");
println(q.getQueue());
//这个时候是空的了
println("这个时候是空的了：" + q.isEmpty());
}
}
class ArrayQ{
private final int maxSize;//数组最大容量
private int front;//队首
private int rear;//队尾
private boolean next;//rear领先front1圈
private final int[] arr;//数组
//队列的构造器
public ArrayQ(int maxSize) {
= maxSize;
arr = new int[maxSize];
front = -1;//队首前面那个下标
rear = -1;//队尾下标
next = false;
}
//判断队列是否满
public boolean isFull(){
if(front==-1 && rear==2){
return true;
}
return front == rear && next;
}
//判断队列是否空
public boolean isEmpty(){
if(front==-1 && rear==-1){
return true;
}
return front == rear && !next;
}
//添加数据到队列
public void addQueue(int num){
//判断队列是否满
if(isFull()){
//队列满了
println("添加数据失败，队列满了！");
return;
}
//如果队尾是2了，还要往后面+1，就理解为已经在下一圈了
if(rear==2){
next = true;
}
rear++;
rear%=maxSize;
arr[rear] = num;
}
//从队列取出数据
public int getQueue(){
//判断是否为空
if(isEmpty()){
throw new RuntimeException("getQueue队列为空！front：" + front + "；rear：" + rear);
}
//如果此时front是2了，还要往后取，就认为这一圈追平了
if(front==2){
next = false;
}
front++;
front%=maxSize;
return arr[front];
}
//显示队列的所有数据
public void show(){
//遍历
if(isEmpty()){
println("队列为空！front：" + front + "；rear：" + rear);
return;
}
for (int value : arr) {
println(value);
}
}
//显示队列头数据
public int headQueue(){
if(isEmpty()){
throw new RuntimeException("headQueue队列为空！front：" + front + "；rear：" + rear);
}
return arr[front+1];
}
//获取有效数据的个数
public int getVD(){
return (rear+maxSize-front)%maxSize;
}
}运行结果：
代码语言：javascript代码运行次数：0运行复制true
添加一个元素：100
添加一个元素：99
添加一个元素：1000
添加一个元素：2000，这个时候会添加失败，因为满了！
添加数据失败，队列满了！
这个时候该满了：true
取出一个元素：100
偷窥首元素：99
显示队列所有元素：
100
99
1000
再添加一个元素：101
显示队列所有元素：
101
99
1000
这个时候是满的了：true
再取一个元素：99
此时队列中有效数据的个数为：2
再取一个元素：1000
再取一个元素：101
再取一个元素：这个时候会取失败，因为空了
Exception in thread "main" java.lang.RuntimeException: getQueue队列为空！front：0；rear：0
at com.zb.ds.ArrayQ.getQueue(ArrayQueue.java:102)
at com.zb.ds.(ArrayQueue.java:4)#感谢您对电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格的认可，转载请说明来源于"电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格
上传时间： 2025-07-23 10:21:00
下一篇：【Java数据结构和算法】002
推荐阅读
| 留言与评论（共有 20 条评论） |
| 本站网友 馍菜汤 | 16分钟前 发表 |
| 遍历稀疏数组 | |
| 本站网友 2010年诺贝尔奖 | 25分钟前 发表 |
| 数组模拟环形队列的思路分析数组模拟环形队列：前面的数组模拟队列里面的数组只用了一次 | |
| 本站网友 厦门信达福特 | 20分钟前 发表 |
| 0 | |
| 本站网友 高龄产妇 | 7分钟前 发表 |
| 只是在对数组进行读写的时候需要额外的一步转换操作 | |
| 本站网友 火箭猪 | 24分钟前 发表 |
| 来保留类似前面的二维数组(棋盘 | |
| 本站网友 陈光标发钱 | 13分钟前 发表 |
| 如图所示：思路分析：当我们将数据存入队列时称为”addQueue” | |
| 本站网友 设备之家 | 25分钟前 发表 |
| 0 | |
| 本站网友 中国动车事故 | 8分钟前 发表 |
| 2 | |
| 本站网友 一居室小户型装修图 | 16分钟前 发表 |
| num) { if (i != 0) { //有效数据 sum++; } } } //2 | |
| 本站网友 环氧地坪施工 | 18分钟前 发表 |
| nums1) { for (int i | |
| 本站网友 生姜红茶 | 15分钟前 发表 |
| 则队列数组的声明如下图 | |
| 本站网友 通州北苑二手房 | 27分钟前 发表 |
| 二维数组与稀疏数组互转二维数组转稀疏数组思路分析：第一步：遍历原二维数组 | |
| 本站网友 上有青冥之长天 | 1分钟前 发表 |
| 从而缩小程序的规模； | |
| 本站网友 达因伊可新 | 1分钟前 发表 |
| 因此记录了很多没有意义的数据 | |
| 本站网友 蓝月 | 14分钟前 发表 |
| 上面已经将二维数组转化成稀疏数组了 | |
| 本站网友 flash转换王 | 3分钟前 发表 |
| 地图等等)；②把稀疏数组存盘 | |
| 本站网友 世界银行行长金墉 | 22分钟前 发表 |
| 数组模拟环形队列的思路分析数组模拟环形队列：前面的数组模拟队列里面的数组只用了一次 | |
| 本站网友 鑫淼 | 12分钟前 发表 |
| 27)4 | |
| 本站网友 孩子气的神 | 13分钟前 发表 |
| 队列介绍①队列是一个有序列表 | |