Array
数据结构基础
数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据.整体而言，数据结构可以分为三种结构: 线性结构、树结构、图结构.
- 线性结构：数组、栈、队列、链表、哈希表等
- 树结构：二叉树、二分搜索树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D树、并查集、哈夫曼树等
- 图结构：邻接表、邻接矩阵
这里图结构虽然是数据结构的一部分，但是存储图的这两种结构是非常简单的. 邻接矩阵本质上是一个二维数组，而邻接表本质是一个链表的数组，当然也有其他的方式实现邻接表比如红黑树数组等. 所以对于图这种数据结构来说，我们通常更关注图论领域的算法实现而不是数据结构本身的设计实现.
我们要根据实际应用的不同，灵活选择最合适的数据结构.
举一些数据结构实际应用的例子：
- 一个最典型的例子就是数据库，数据库本身就是用来存储数据的，所以要设计一个数据库的话一定要使用数据结构.只不过对于数据库来说我们是在外存上做数据存储.
- 另一个例子就是操作系统，在操作系统中，无论是优先队列还是内存管理还是文件管理都会使用到数据结构，这些功能本身就是为了组织存储数据.比如优先队列，操作系统所有执行的进程需要一个优先队列来决定在每一个时间片上运行哪一个进程，进程本身就是我们要组织存储的数据.
- 又比如文件压缩，文件压缩本身是一个算法，为了执行它需要合理的使用数据结构进行支撑，比如一种基础的压缩算法就需要使用哈夫曼树.
- 又如图论算法领域，在游戏中操纵角色从一点到另一点，这本身是一个寻路算法，寻路最为基础的两种算法DFS和BFS分别需要使用栈和队列这种数据结构.
对于数据结构我们关注的核心操作就是在内存世界的增删改查 .
数组基础
数组就是把数据码成一排进行存放. 比如下面数组有8个空间，可以存储8个元素，具体8个元素是什么类型？在 C++ 和 Java 中，数组是一种定类型数据结构，其中所有元素的数据类型必须相同，比如 int[] 数组中只能存放 int。而在 Python 中，列表可以同时存储不同类型的元素，例如整数、字符串、浮点数等，因为 Python 的列表是动态类型的容器。
□□□□□□□□0 1 2 3 4 5 6 7
数组存在一个很重要的概念即索引, 为每一个元素做一个编号.如上面索引从0开始到7.
代码示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Main {
public static void main(String[] args) {
int[] arr = new int[10];
for(int i = 0; i < arr.length; i++)
arr[i] = i;
int[] scores = new int[]{100, 99, 66};
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
for(int socre: scores)
System.out.print(socre + " ");
}
}
|
数组的索引可以是有语义的，也可以没有语义. 比如定义一个名为socres的数组，索引代表8个同学的学号0-7，取scores[2] 可以有实际的意义，代表看学号为2同学的分数, 这个索引2有实际的语义.当然也可以没有语义，就是单纯的一个分数存在索引为2的位置.
scores □□□□□□□□0 1 2 3 4 5 6 7
假如能存在8个元素数组只用到了3个元素，剩下的空间里没有元素.
scores 1009966□□□□□□□
- 此时索引没有语义，如何表示没有的元素？
- 如何添加和删除元素呢？
java使用的是静态数组，没有上面的功能. 因此我们必须基于java的数组来二次封装属于我们自己的数组类即动态数组.
首先实现Array的基本方法(构造、获取大小容量、判断非空)：
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
| public class Array {
private int[] data;
private int size;
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
public Array() {
this(10);
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
}
|
增-添加元素
向数组添加元素最简单的方式在数组的末尾添加元素：
scores size□□□□□□□□capacityscores 7size□□□□□□□capacity
初始时数组为空，size=0 ，接着在数组末尾添加一个元素比如数字7,此时size++ 变为1.
代码实现这个逻辑：
1
2
3
4
5
6
7
| public void addLast(int e){
if(size == data.length){
throw new RuntimeException("Array is full");
}
data[size] = e;
size++;
}
|
首先判断当前数组是否已满，已满就抛出异常；否则在数组末尾添加元素，size++.
那么思考如何向数组指定位置添加元素？假如有下面这一个数组，此时有一个新元素7需要添加到索引为1的位置形成一个有序的数组，这个操作如何实现？
scores 68910size□□□□capacityscores 6□89size10□□capacityscores 678910size□□□capacity
很简单，将8 9 10分别向右平移一位后空出索引为1的位置，接着将数字7插入即可，同时记得size++ .
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public void add(int index, int e){
if(size == data.length){
throw new RuntimeException("Array is full");
}
if(index < 0 || index > size){
throw new RuntimeException("Index out of bounds");
}
for(int i = size-1; i >= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
|
同样首先判断size是否已满，同时还要判断添加新元素的索引是否超出边界.
实现上面代码后在数组的末尾添加元素代码可以复用：
1
2
3
| public void addLast(int e){
add(size, e)
}
|
同理可得在数组头添加一个元素的代码：
1
2
3
| public void addFirst(int e){
add(0,e);
}
|
查改-查询和修改元素
上面实现了在数组中添加元素，有了元素之后，就可以查询和修改数组中的元素. 对于数组来说其数据真正存储在封装在Array类中的一个私有数组data，对于静态数组可以很方便通过[index] 查询相应的元素.
接下来写一个toString方法调用[index] 方式查询元素：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| @Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append("[");
for (int i = 0; i < size; i++) {
res.append(data[i]);
if(i != size - 1){
res.append(", ");
}
}
res.append("]");
return res.toString();
}
|
然后测试一下前面写的功能：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Main {
public static void main(String[] args) {
Array arr = new Array(20);
for (int i = 0; i < 10; i++) {
arr.addLast(i);
}
System.out.println(arr);
arr.add(1,100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
}
}
|
从打印结果可以发现add, addFirst,addLast方法实现均正确.
同时我们需要实际取出数据中的某一个元素，相应设计一个get方法：
1
2
3
4
5
6
7
| int get(int index){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
return data[index];
}
|
这样其实相当于对data进行了隐藏，用户只能通过get方法获得静态数组data某一个索引的元素而不能直接获得data这个静态数组，好处就是我们可以在这个函数中对用户传进来的index进行判断，保证索引合法. 这样用户永远无法查询没有使用的空间，通过封装的方式保证了整个数据的安全.
与get相应的是set方法，set方法用来进行数组元素的更新：
1
2
3
4
5
6
| void set(int index, int e){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
data[index] = e;
}
|
这样就实现了外部用户如何获取某个index以及修改index元素的功能.
包含、搜素、删除
很多时候我们在数据结构中存储了一些元素，我们需要查找是否在这些元素中包含某些元素.这种情况就需要设置一个接口，用来查找数组中是否存在某个元素e.
代码实现：
1
2
3
4
5
6
7
| public boolean contains(int e){
for(int i = 0; i < size; i++){
if(data[i] == e)
return true;
}
return false;
}
|
有些时候可能不止想要查找是否包含元素e, 如果存在元素e要查询一下元素e的索引是什么。相应可以设置一个方法：
1
2
3
4
5
6
7
| public int find(int e){
for(int i = 0; i < size; i++){
if(data[i] == e)
return i;
}
return -1;
}
|
接下来看下如何从数组中删除指定位置元素：
scores 678910size□□□□capacityscores 688910size□□□□capacityscores 689910size□□□□capacityscores 6891010size□□□□capacityscores 68910size10□□□□capacity
假设要删除索引为1的元素即数字7. 与给数组指定位置插入元素相反，将删除索引之后的元素全部向左移，这样相当于将待删除索引位置的元素给覆盖了.
具体操作流程如上面：
- 将data[1] = data[2]
- data[2] = data[3]
- data[3] = data[4]
- size –
此时size指向了10，这样是没问题的，因为用户访问数组想要从某个索引拿到某个元素会判断这个索引的合法性,是不会访问到data[size]的元素的.
1
2
3
4
5
6
7
8
9
10
11
| public int remove(int index){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
int removed = data[index];
for(int i=index+1; i < size; i++){
data[i-1] = data[i];
}
size--;
return removed;
}
|
在此基础上创建一些快捷的方法removeFirst 、removeLast、removeElement.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int removeFirst(){
return remove(0);
}
public int removeLast(){
return remove(size-1);
}
public void removeElement(int e){
int index = find(e);
if(index != -1){
remove(index);
}
}
|
测试：
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
| public class Main {
public static void main(String[] args) {
Array arr = new Array(20);
for (int i = 0; i < 10; i++) {
arr.addLast(i);
}
System.out.println(arr);
arr.add(1,100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
arr.remove(2);
System.out.println(arr);
arr.removeElement(4);
System.out.println(arr);
arr.removeFirst();
System.out.println(arr);
}
}
|
可见成功删除了元素100、4、-1.功能正确.
泛型
将前面的Array类改为泛型类. 修改方法方式同前面的内容.
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
| import java.util.Arrays;
public class Array <E> {
private E[] data;
private int size;
public Array(int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
public Array() {
this(10);
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void addLast(E e){
add(size,e);
}
public void addFirst(E e){
add(0,e);
}
public void add(int index, E e){
if(size == data.length){
throw new RuntimeException("Array is full");
}
if(index < 0 || index > size){
throw new RuntimeException("Index out of bounds");
}
for(int i = size-1; i >= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
public E get(int index){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
return data[index];
}
public void set(int index, E e){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
data[index] = e;
}
public boolean contains(E e){
for(int i = 0; i < size; i++){
if(data[i] .equals(e) )
return true;
}
return false;
}
public int find(E e){
for(int i = 0; i < size; i++){
if(data[i] .equals(e) )
return i;
}
return -1;
}
public E remove(int index){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
E removed = data[index];
for(int i=index+1; i < size; i++){
data[i-1] = data[i];
}
size--;
data[size] = null;
return removed;
}
public E removeFirst(){
return remove(0);
}
public E removeLast(){
return remove(size-1);
}
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append("[");
for (int i = 0; i < size; i++) {
res.append(data[i]);
if(i != size - 1){
res.append(", ");
}
}
res.append("]");
return res.toString();
}
}
|
使用自定义类Student测试：
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
| import java.util.ArrayList;
public class Student implements Comparable<Student>{
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student o) {
return o.score - this.score;
}
@Override
public boolean equals(Object student) {
if(this == student)
return true;
if(student == null)
return false;
if(this.getClass() != student.getClass())
return false;
Student another = (Student)student;
return this.name.equals(another.name);
}
@Override
public String toString() {
return String.format("Student [name=%s, score=%d]", name, score);
}
public static void main(String[] args) {
Array<Student> students = new Array<Student>();
students.addLast(new Student("A", 90));
students.addLast(new Student("B", 70));
students.addLast(new Student("C", 80));
System.out.println(students);
}
}
|
结果如下，成功打印出自定义Student类的三条数据.
动态数组
上面实现的数组还存在一个问题就是内部依旧使用的是java的静态数组，对于java静态数组来说，其容量是有限的.可是很多时候使用数组类可能无法事先预估往这个数组里放多少元素, 这种情况下如果容量太大会导致空间浪费，容量太小会导致不够用，这种情况需要数组的容量是可伸缩的，也就是动态数组.
那么如何实现动态数组呢？
如上图所示，原始数组只有四个元素(23、12、45、47)并且装满, 此时显然无法添加一个新元素了.在这种情况下就可以开辟一个新数组newData, 其空间为6比原数组data的空间要大. 接着将data数组的四个元素全都放到newData中，这一步实现需要循环data的所有元素，让后将data指向newData.
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public void add(int index, E e){
if(index < 0 || index > size){
throw new RuntimeException("Index out of bounds");
}
if(size == data.length){
resize(2 * data.length);
}
for(int i = size-1; i >= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size++;
}
|
1
2
3
4
5
6
7
| private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0; i < size; i++){
newData[i] = data[i];
}
data = newData;
}
|
测试结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Main {
public static void main(String[] args) {
Array arr = new Array();
for (int i = 0; i < 10; i++) {
arr.addLast(i);
}
System.out.println(arr);
arr.add(1,100);
System.out.println(arr);
arr.addFirst(-1);
System.out.println(arr);
}
}
|
初始时size=10 ，接下来执行add方法容量扩成了2倍变成了20.
同理对于remove操作也可以动态操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public E remove(int index){
if(index < 0 || index >= size){
throw new RuntimeException("Index out of bounds");
}
E removed = data[index];
for(int i=index+1; i < size; i++){
data[i-1] = data[i];
}
size--;
data[size] = null;
if(size == data.length/2){
resize(data.length/2);
}
return removed;
}
|
如上面代码，当数组减少到一定程度，执行resize动态减少数组容量.
此时实现了一个真正意义上的动态数组.
时间复杂度分析
添加操作：
- addLast(e): O(1)
- addFirst(e):O(n)
- add(index,e) : O(n/2)=O(n) 取到每个index的概率是1/n,相应操作期望(n+n−1+...+2+1)/n=O(n)
- resize:O(n)
综合来看添加操作为O(n) 级别的算法.
删除操作：
- removeLast(e):O(1)
- removeFirst(e):O(n)
- remove(index, e):O(n/2)=O(n)
- resize:O(n)
综合来看添加删除为O(n) 级别的算法.
修改操作：
- set(index, e):O(1)
查找操作：
- get(index): O(1)
- contains(e):O(n)
- find(e):O(n)
总结来说：
- 增：O(n)
- 删：O(n)
- 改: 已知索引O(1) ；未知索引O(n)
- 查: 已知索引O(1) ；未知索引O(n)
