java数据结构
稀疏数组
将一个二维数组chess[][] 转换成稀疏数组sparseArray[][3]:
sparseArray[0][0]和sparseArray[0][1]分别存放chess的行数和列数, sparseArray[0][2]存放有效值的个数.
sparseArray[m][0]和sparseArray[m][1] 表示有效值的行数和列数,sparseArray[m][2]存放有效值的值
原始数组chess[][]:
稀疏数组sparseArray[][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
|
public static int[][] sparse(int[][] array, int invalid) {
int count = 1;
int sum = traverse(array, invalid);
int[][] sparseArray = new int[sum+1][3];
sparseArray[0][0] = array.length;
sparseArray[0][1] = array[0].length;
sparseArray[0][2] = sum;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if(array[i][j] != invalid) {
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = array[i][j];
count++;
}
}
}
return sparseArray;
}
|
稀疏数组转普通数组代码实现:
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
|
public static int[][] chess(int[][] array, int invalid) {
int[][] chessArray = new int[array[0][0]][array[0][1]];
if(invalid != 0) {
for (int i = 0; i < array[0][0]; i++) {
for (int j = 0; j < array[0][1]; j++) {
chessArray[i][j] = invalid;
}
}
}
for (int i = 1; i <= array[0][2]; i++) {
chessArray[array[i][0]][array[i][1]] = array[i][2];
}
return chessArray;
}
|
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作,先进先出.
称进入队列的一端为“队尾”；出队列的一端为“队头”。数据元素全部由队尾陆续进队列，由队头陆续出队列。
顺序队列
用数组实现顺序队列(用数组索引代替c++中的指针):
初始化队
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
| public class QueueArray {
private int maxSize;
private int rear;
private int front;
private int[] array;
public QueueArray(int maxSize) {
this.maxSize = maxSize;
this.rear = -1;
this.front = -1;
this.array = new int[maxSize];
}
|
判断队列是否为空
1
2
3
4
5
6
7
|
public boolean isEmpty() {
return front == rear;
}
|
判断是否队列已满
1
2
3
4
5
6
7
|
public boolean isFull() {
return rear == maxSize - 1;
}
|
入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public void enter(int data) {
if(isFull()) {
System.out.println("队列已满,入队失败");
return;
}
rear++;
array[rear] = data;
}
|
出队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public int leave() {
if(isEmpty()) {
throw new RuntimeException("队列为空,出队失败");
}
front++;
return array[front];
}
|
遍历队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public void traverse() {
if(isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = front+1; i <= rear; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
|
主函数对代码进行测试
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
| public static void main(String[] args) {
QueueArray queueArray = new QueueArray(3);
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while(loop) {
System.out.println("入队:in, 出队:out, 判空:empty, 判满:full, 查看:check, 退出:exit");
String next = scanner.next();
switch (next) {
case "in" :
System.out.println("请输入数据");
queueArray.enter(scanner.nextInt());
break;
case "out" :
try {
System.out.println("出队数据为: " + queueArray.leave());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "empty" :
if(queueArray.isEmpty()) {
System.out.println("队列为空");
break;
}
System.out.println("队列非空");
break;
case "full" :
if(queueArray.isFull()) {
System.out.println("队列已满");
break;
}
System.out.println("队列未满");
break;
case "check" :
queueArray.traverse();
break;
case "exit" :
System.out.println("已退出");
loop = false;
break;
}
}
scanner.close();
}
|
