稀疏数组与队列

稀疏数组与队列

稀疏数组

基本介绍

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来进行保存

处理方法

  1. 记录数组一共有几行几列,有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模数组中,从而缩小程序的规模

案例

image-20220602095921065

我们可以看出上面的图片中6*7的数组大小,存储之后可以编程9行3列的数组,缩小了数组的大小

代码

二维数组转稀疏数组

我们首先遍历二维数组,得到有效数据的个数和行列数,然后得到有效数组的位置存储到稀疏数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package 数据结构和算法.稀疏数组和队列;

import java.util.Arrays;

public class SpareArray {
public static void main(String[] args) {
//创建二维的原始数组
int [][]arrays=new int[6][7];
arrays[0][3]=22;
arrays[0][6]=15;
arrays[1][1]=11;
//输出原始二维数组
for (int[]row:arrays){
System.out.println(Arrays.toString(row));
}



//转化稀疏数组
//首先需要获得值的个数确定行数,同时收集二维数组的行与列
int count=0;
//二维数组的行
int row=0;
//二维数组的列
int col=0;
for (int []rows:arrays){
//获得行
row=arrays.length;
//获得列
col=rows.length;
for (int i:rows){
if(i!=0){
//获得稀疏数组的行数
count++;
}
}
}
int [][]spareArray=new int[count+1][3];
//开始赋值
spareArray[0][0]=row;
spareArray[0][1]=col;
spareArray[0][2]=count;
int flag=1;
for (int i=0;i<row;i++){
for (int j=0;j<col;j++){
if(arrays[i][j]!=0){
spareArray[flag][0]=i;
spareArray[flag][1]=j;
spareArray[flag][2]=arrays[i][j];
flag++;
}
}
}
for (int[]rows:spareArray){
System.out.println(Arrays.toString(rows));
}
}
}

image-20220602104331351

稀疏数组转二维数组

得到行和列,还原二维数组,将有效数据还原到二维数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
//稀疏数组转换为二维数组
int [][]newArray=new int[spareArray[0][0]][spareArray[0][1]];
//将有效值进行赋值,开始的行数
int flag1=1;
for (int i=0;i<spareArray[0][2];i++){
newArray[spareArray[flag1][0]][spareArray[flag1][1]]=spareArray[flag1][2];
flag1++;
}
for (int[]rows:newArray){
System.out.println(Arrays.toString(rows));
}

}

队列

队列是一个有序列表,可以用数组(有序数组)或者链表(有序链表)来实现,遵从先入先出的原则

image-20220604092742372

第一张图片没有存入数据的时候,rear与front都为-1,当我们加入数据的时候,rear+1,而front不变,当我们取出数据的时候,是从前面开始取出,那么front就开始+1

队列实现方法

数组方式普通实现

而数组队列需要一个front与rear还有maxsize表示最大的容量,当我们加入一个队列的时候,rear+1,而取出的时候,front+1,但是如果rear==maxsize-1的时候,就已经满了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package 数据结构和算法.稀疏数组和队列;

/**
* @author 21050
*/
public class ArrayQueue {
int maxSize=0;
int front;
int rear;
int []array;

public ArrayQueue(int maxSize){
this.maxSize=maxSize;
front=-1;
rear=-1;
array=new int[maxSize];
}
/**判断是否为空*/
public boolean isEmpty(){
return front==rear;
}

/**判断是否满了*/
public boolean isFull(){
return rear==maxSize-1;
}

/**取出一个数*/
public void takeNum(){
if (isEmpty()){
System.out.println("为空,没有数据可取出");
}else{
front++;
System.out.println("取出成功,取出了"+array[front]);
}
}

/**插入一个数*/
public void insertNum(int n){
if (isFull()){
System.out.println("队列已经满了,无法插入数据");
}else{
rear++;
array[rear]=n;
System.out.println("插入成功");
}
}

/**打印当前队列*/
public void show(){
for (int i=front;i<rear;){
System.out.println(array[++i]);
}
}
public static void main(String[] args) {
ArrayQueue arrayQueue=new ArrayQueue(3);
System.out.println(arrayQueue.isFull());
System.out.println(arrayQueue.isEmpty());

//插入数据
arrayQueue.insertNum(1);
arrayQueue.insertNum(2);
arrayQueue.insertNum(3);
arrayQueue.insertNum(4);
//展示列表
arrayQueue.show();

//取出数据
arrayQueue.takeNum();
arrayQueue.takeNum();
arrayQueue.takeNum();
arrayQueue.takeNum();
//展示列表
arrayQueue.show();
}

}

image-20220604100621473

当然我们这个也是存在错误的,因为我们这个实现方法并没有完成取模,形成环形队列,只能使用一次

数组方式环形队列实现

初始情况下front=rear=0,此时并没有插入数,但是一旦插入数,front指向当前数,即front=0,而rear指向最后一个数的下一个位置,此时我们需要预留出来一个位置给rear,也就是说最多存放maxSize-1个数据,方便我们进行判断满或者为空

image-20220604202326445

而当我们插入一个元素的时候

image-20220604202454858

此时我们对判断满的条件进行观察,查看两种情况

插入123

image-20220604203013169

插入123,取出12,插入45

image-20220604203538042

我们可以看出判断为满的条件为front=(rear+1)%maxsize

那么判断为空的条件也很明显即rear==front

其实这里不明白为什么要留出一个空来,这样做为了方便分别空还是满,如果不留出来这个空间,插入1234,rear为0,front=0,但是这也是判断空的条件,容易混淆,当然不留空也可以,但是需要我们进行多重判断,反而思路比较麻烦

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package 数据结构和算法.稀疏数组和队列;

/**
* @author 21050
*/
public class ArrayQueue2 {
int front;
int rear;
int maxSize;
int[] array;

public ArrayQueue2(int maxSize){
this.maxSize=maxSize;
front=0;
rear=0;
array=new int[maxSize];
}

/**判断为空*/
public boolean isEmpty(){
return front==rear;
}

/**判断是否满*/
public boolean isFull(){
return (rear+1)%maxSize==front;
}

/**添加一个数,但是添加数的时候,要注意rear的数是否等于了maxsize,大于就需要减去进行进行循环*/
public void insertNum(int n){
if (isFull()){
System.out.println("队列已经满了,无法插入数据");
}else{

array[rear]=n;
System.out.println("插入成功");
rear++;
if (rear==maxSize){
rear= 0;
}
}
}

/**取出一个数,这里也要注意front与maxsize的关系*/
public void takeNum(){
if (isEmpty()){
System.out.println("为空,没有数据可取出");
}else{

System.out.println("取出成功,取出了"+array[front]);
front++;
if (front==maxSize){
front=0;
}
}
}

/**按照顺序展示当前队列*/
public void show(){
for (int i=front;i!=rear;i++){
if (i==maxSize){
i=0;
}
System.out.print(array[i]);

}
}


public static void main(String[] args) {
//插入数据
ArrayQueue2 arrayQueue2=new ArrayQueue2(4);
arrayQueue2.insertNum(1);
arrayQueue2.insertNum(2);
arrayQueue2.insertNum(3);
arrayQueue2.insertNum(4);
arrayQueue2.show();

System.out.println();

//取出数据
arrayQueue2.takeNum();
arrayQueue2.takeNum();
arrayQueue2.show();

System.out.println();

//插入45
arrayQueue2.insertNum(4);
arrayQueue2.insertNum(5);
arrayQueue2.show();
}
}

image-20220604205453247