数据结构理论知识
数据结构
数据结构
[TOC]
一、稀疏数组
1.1 介绍
常见于类似围棋、迷宫中，由于棋盘、地图很大，而状态少（黑棋，白棋，无；墙，非墙）。导致用以记录的二维数组中有太多重复的数据，比如刚开始游戏时五子棋的空位。这种时候如果要存档，就会造成很大的空间浪费，稀疏数组也就由此而来
- 稀疏数组的行数 = 源数组中有效元素的个数 + 1，列数 = 3
- 稀疏数组的第一行三个元素不存储数据，而是分别表示源数组的行数，列数，有效元素个数
- 从第二行开始，三个元素分别表示数据在源数组中的行号，列号；以及数据本身
1.2 特点
- 使用更小的空间存放数据
- 充分发挥了每一个数组元素的作用
- 易于存储
二、链表
2.1 介绍
是一种物理存储单元不连续，逻辑顺序连续的数据结构。由节点组成，一般每个节点都包含一个
next属性，用于指向下一个节点所在的地址
2.2 特点
- 因为地址不连续，所以在插入和删除时效率很高
- 随机访问不方便，需要从头开始匹配查找
- 长度不限定，也就是容量动态化
2.3 单向链表
- 需要提供增删查改等方法
- 采用泛型使存储的数据类型动态化
- 对外提供 Iterator 接口，便于遍历
三、队列
2.1 介绍
队列模拟的是一个排队的过程，常见的实现有如消息队列
2.2 特点
- 可以使用数组实现，也可以使用链表实现
- 插入时只能从末尾插入
- 删除/取出时只能从头部取出
- 会出现队列满的情况
2.3 普通队列（数组实现）
普通的队列最大的缺陷是无法回收复用元素
空队列：
添加元素：
满队列：
取出元素：
2.4 循环队列（数组实现）
在普通队列的基础上进行改进，通过取模的方式使数组的首位连接起来，形成一个环形数组，当 head 和 tail 指向同一个下标时为空，当 (tail + 1) % MAX_SIZE 和 head 指向同一个下标时为满。这里 +1 是为了和队列空的情况进行区分。
四、栈
4.1 介绍
栈模拟的是一种暂时存放的场景，栈就像一个盒子，当你向箱子里放物品时，第一个放入的在最下面，最后放入的在最上面。那么在取出的时候也会是最上面（最后）一个物品先取出。这种机制常用于方法调用中，如Java虚拟机中就有方法栈，每调用一个方法，就把该方法的信息放入栈中。每结束一个方法，就从栈中弹出该方法。
4.2 特点
- 效率高
- 遵循 FILO(First in Last out) 原则
附录
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
import java.io.*;
import java.util.Arrays;
public class SparseArray {
private int[][] data; // 稀疏数组
private int defaultValue; // 默认值
/**
* 根据已有数组创建
* @param defaultValue 默认值
* @param data 源数组
*/
public SparseArray(int defaultValue, int[][] data) {
this.defaultValue = defaultValue;
int size = this.count(data); // 计算元素个数
this.data = new int[size + 1][3]; // 创建数组
this.data[0][0] = data.length;
this.data[0][1] = data[0].length;
this.data[0][2] = size;
this.encode(data); // 转换
}
/**
* 从文件读取
* @param path 文件路径
*/
public SparseArray(String path) {
this.readFromFile(path);
}
/**
* 保存至文件
* @param path 文件路径
*/
public void saveToFile(String path) {
FileWriter fw = null;
try {
fw = new FileWriter(new File(path));
fw.write(defaultValue + "\r\n");
for (int[] line : data) {
String strLine = Arrays.toString(line);
strLine = strLine.substring(1, strLine.length() - 1);
fw.write(strLine + "\r\n");
}
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
assert fw != null;
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 从文件中解析
* @param path 文件路径
*/
private void readFromFile(String path) {
File file = new File(path);
BufferedReader br = null;
try {
br = new BufferedReader(new FileReader(file));
String strData;
int count = -1;
int size = 0;
while ((strData = br.readLine()) != null) {
if (count == -1) {
this.defaultValue = Integer.parseInt(strData);
} else {
String[] data = strData.replace(" ", "").split(",");
if (count == 0) {
size = Integer.parseInt(data[2]);
this.data = new int[size + 1][3];
}
this.data[count][0] = Integer.parseInt(data[0]);
this.data[count][1] = Integer.parseInt(data[1]);
this.data[count][2] = Integer.parseInt(data[2]);
}
if (count++ == size) {
break;
}
}
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
if (br != null) {
br.close();
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 计算源二维数组中的有效数据个数
* @param data 源数组
* @return 有效数据个数
*/
private int count(int[][] data) {
int size = 0;
for (int[] ints : data) {
for (int item : ints) {
if (item != defaultValue) {
size++;
}
}
}
return size;
}
/**
* 将源数组转为稀疏数组
* @param data 源数组
*/
private void encode(int[][] data) {
for (int i = 0, k = 1; i < data.length; i++) {
for (int j = 0; j < data[i].length; j++) {
if (data[i][j] != defaultValue) {
this.data[k][0] = i;
this.data[k][1] = j;
this.data[k][2] = data[i][j];
k++;
}
}
}
}
/**
* 将稀疏数组恢复成源数组
* @return 源数组
*/
public int[][] decode() {
int row = data[0][0];
int col = data[0][1];
int[][] target = new int[row][col];
for (int[] item : target) {
Arrays.fill(item, defaultValue);
}
for (int index = 1; index < data.length; index++) {
row = data[index][0];
col = data[index][1];
target[row][col] = data[index][2];
}
return target;
}
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 1; i < data.length; i++) {
String string = Arrays.toString(data[i]);
builder.append(string).append("\n");
}
return builder.toString();
}
}
2、链表
2.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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
public class SingleLinkedList<T> {
/**
* 节点
*/
static class SingleNode<E> {
private E value;
private SingleNode<E> next;
public SingleNode() {
}
public SingleNode(E value) {
this.value = value;
}
public SingleNode(E value, SingleNode<E> next) {
this.value = value;
this.next = next;
}
public String toString() {
return value.toString() + (next == null ? "" : " -> " + next.toString());
}
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
}
/**
* 节点添加的方式
*/
public enum Mode {
POSITIVE, // 正序（尾插法）
REVERSE, // 逆序（头插法）
ASC, // 升序
DES, // 降序
}
private SingleNode<T> head; // 头节点
private final Mode mode; // 添加模式
private final int maxSize; // 最大容量
private int length; // 已用容量
/**
* 默认最大容量为 2147483647
*/
public SingleLinkedList() {
this(Integer.MAX_VALUE);
}
/**
* 默认添加方式为 正序添加（尾插法）
* @param maxSize 最大容量
*/
public SingleLinkedList(int maxSize) {
this(maxSize, Mode.POSITIVE);
}
public SingleLinkedList(Mode mode) {
this(Integer.MAX_VALUE, mode);
}
public SingleLinkedList(int maxSize, Mode mode) {
this.maxSize = maxSize;
this.mode = mode;
this.head = new SingleNode<>();
}
/**
* 添加元素，根据添加的方式进行添加
* @param value 要添加的值
*/
public void add(T value) {
if (length >= maxSize) {
throw new RuntimeException("ListOverflow!");
}
switch (mode) {
case POSITIVE: addByPositive(value); break;
case REVERSE: addByReverse(value); break;
default: addByOrder(value); break;
}
}
/**
* 正序添加（尾插法）
* @param value 要添加的值
*/
private void addByPositive(T value) {
SingleNode<T> tmp = head;
for (;tmp.next != null; tmp = tmp.next);
tmp.next = new SingleNode<>(value);
}
/**
* 逆序添加（头插法）
* @param value 要添加的值
*/
private void addByReverse(T value) {
SingleNode<T> newNode = new SingleNode<>(value);
newNode.next = head.next;
head.next = newNode;
}
/**
* 有序添加
* @param value 要添加的值
*/
private void addByOrder(T value) {
// 元素类型应实现 Comparable 接口，否则无法进行比较，也就无法实现有序添加
if (!(Comparable.class.isAssignableFrom(value.getClass()))) {
throw new RuntimeException(value.getClass().getName() + " should implements interface Comparable");
}
Comparable<T> comparable = (Comparable<T>) value;
SingleNode<T> tmp = head;
// 升序：要插入的值 < 下一个节点的值
// 降序：要插入的值 > 下一个节点的值
while (tmp.next != null) {
T nextValue = tmp.next.getValue();
// 先按升序的比较方法拿到 flag
boolean flag = comparable.compareTo(nextValue) < 0;
// 再确定是不是升序，不是则取反
flag = (mode == Mode.ASC) == flag;
// 最后根据 flag 判断是否要退出
if (flag) {
break;
}
tmp = tmp.next;
}
SingleNode<T> newNode = new SingleNode<>(value);
newNode.next = tmp.next;
tmp.next = newNode;
}
/**
* 获取第一个节点的值
* @return value
*/
public T peekFirst() {
return head.next.getValue();
}
/**
* 弹出第一个节点的值
* @return value
*/
public T popFirst() {
T value = head.next.getValue();
head.next = head.next.next;
return value;
}
/**
* 链表反转
*/
public void reverse() {
SingleLinkedList<T> newList = new SingleLinkedList<>(Mode.REVERSE);
while (head.next != null) {
T t = popFirst();
newList.add(t);
}
head = newList.head;
}
/**
* 根据下标获取值
* @param index 下标
* @return value
*/
public T indexOf(int index) {
SingleNode<T> tmp = head.next;
while (tmp != null && index-- > 0) {
tmp = tmp.next;
}
if (tmp != null) {
return tmp.getValue();
}
return null;
}
/**
* 根据下标从后往前获取值
* @param index 下标
* @return vlue
*/
public T lastIndexOf(int index) {
SingleNode<T> element = head.next;
SingleNode<T> test = head.next;
while (test != null && index-- > 0) {
test = test.next;
}
if (test == null) {
return null;
}
while (test.next != null) {
test = test.next;
element = element.next;
}
return element.getValue();
}
public String toString() {
return head.next.toString();
}
}
3、队列
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
private final T[] data; // 数据
private final int maxSize; // 最大容量
private int tail = 0; // 头指针
private int head = 0; // 尾指针
public BaseQueue(int maxSize) {
this.maxSize = maxSize;
this.data = (T[]) new Object[maxSize];
}
/**
* 添加元素
*/
public void add(T value) {
if (isFull()) {
return;
}
data[tail++] = value;
}
/**
* 查看头部元素
*/
public T head() {
if (isEmpty()) {
return null;
}
return data[head];
}
/**
* 弹出一个元素
*/
public T get() {
if (isEmpty()) {
return null;
}
return data[head++];
}
/**
* 是否为空
*/
public boolean isEmpty() {
return tail == 0;
}
/**
* 是否已满
*/
public boolean isFull() {
return tail == maxSize;
}
}
3.2、循环队列
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
private final T[] data;
private final int maxSize;
private int head = -1;
private int tail = -1;
public CircularQueue(int maxSize) {
this.maxSize = maxSize;
this.data = (T[]) new Object[maxSize];
}
public void add(T value) {
if (isFull()) {
return;
}
data[(++head) % maxSize] = value;
}
public T head() {
if (isEmpty()) {
return null;
}
return data[(tail + 1) % maxSize];
}
public T get() {
if (isEmpty()) {
return null;
}
return data[(++tail) % maxSize];
}
public boolean isEmpty() {
return tail == head;
}
public boolean isFull() {
return (head + 1) % maxSize == tail;
}
}
4、栈
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
private final T[] data;
private final int capacity;
private int length;
public Stack() {
this(16);
}
public Stack(int initCapacity) {
this.capacity = initCapacity;
this.data = (T[]) new Object[initCapacity];
}
public T push(T value) {
if (full()) {
throw new RuntimeException("StackOverflow");
}
data[length++] = value;
return value;
}
public T pop() {
if (empty()) {
throw new RuntimeException("StackEmpty");
}
return data[--length];
}
public T peek() {
if (empty()) {
throw new RuntimeException("StackEmpty");
}
return data[length - 1];
}
private boolean full() {
return length == capacity;
}
public boolean empty() {
return length == 0;
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Cin's Home！
