1.数组介绍



数组就是内存中一段连续的存储空间,并且存储的内容必须数据类型相同。
数组坐标从 0 开始,因为是在 c 语言中的计算数组的地址位置时,这样计算的:

arr[i]_address = base_addrress + i * sizeof(data)

如果从 1 开始,cpu 就会多执行了一次减法计算,对人类也不友好

arr[i]_address = base_addrress + (i-1) * sizeof(data)

其他语言也是和向 c 学习的,因为这样可以减轻大家的学习成本(我猜的)

2.什么时候用数组



当一组数据需要经常对数据进行查询和改变元素的值,这个时候就可以使用数组,因为数组是一段连续的存储空间,这就有利于根据地址来查找某一个位置的元素或者进行改变,这两个操作都是 O(1)。

比如英雄联盟中的商店,那个装备位置都是固定的,你就可以根据地址快速找出装备来进行查看,这个就可以用数组来实现。

但是你的装备栏就不可以了,因为需要经常回家更新装备,需要进行大量的插入和删除,这个时候再用数组来存储的话,就显得效率很低了,因为这两个的时间复杂度都是 O(n)。但是另一种数据结构就非常合适,就是链表。这个以后再说。

数组的插入和删除操作也是可以通过适当改变也可以让其时间复杂度变小点的。比如在对数组进行删除时,我们可以先把需要删除的元素记录下来暂不处理,当数组的容量装不下来的时候,这个时候再触发真正的删除操作,这样子就可以大大地减少对数据的迁移以及申请内存空间的操作。

还有插入的时候我们也可以先把需要插入位置的元素(初始元素)先把其放进数组尾部,然后把元素插入该位置,然后记录下这些元素的位置,当数组容量满的时候,再进行一次数据迁移,这样也可大大减少数据迁移工作。

这两个可以说是通过空间换时间吧。

3. 基本方法



数组结构:1.数组声明 2.数组当前长度

方法:

  • boolean isEmpty():判断数组是否为空,时间复杂度为 O(1)
  • int get(int index):根据 index 获取元素,时间复杂度为 O(1)
  • set(int index, int e):改变 index 位置的元素,时间复杂度为 O(1)
  • int find(int e):查找该元素是否存在在数组,存在就返回该元素的位置,反之返回 -1,时间复杂度为 O(1)
  • void add(int index, int e):添加元素,时间复杂度为 O(n)
  • int remove(int index):删除元素,时间复杂度为 O(n)

4.方法的实现



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
import java.util.Random;

public class ArrayList {
int length; // 当前数组的长度
int[] array; // 暂时存储int类型

// 初始化数组
public ArrayList(int capacity){
this.array = new int[capacity];
}
//空参数的就默认容量为10
public ArrayList(){
this(10);
}

// 获取当前数组长度
public int getLength(){
return this.length;
}

// 判断数组是否为空
public boolean isEmpty(){
return this.length == 0;
}

// 根据index获取线性表的值
public int get(int index){
if(index < 0 || index >= length){
throw new IllegalArgumentException("index 不存在");
}
return array[index];
}

// 改变 index 位置的元素
public int set(int index, int e){
if(index < 0 || index >= length){
throw new IllegalArgumentException("改变元素失败,index 不存在");
}

int k = array[index];
array[index] = e;
return k;
}

// 根据所给的值查找该元素在数组的位置,不存在就返回 -1
public int find(int e){
// for(int i = 0; i < length; i++){
// if(array[i] == e)
// return i;
// }
// return -1;

// 需要先判断数组是否为空
if(length == 0)
return -1;

if(array[length - 1] == e)
return length -1;
int key = array[length - 1]; // 记录最后一个元素
array[length - 1] = e; // 当哨兵
int i = 0;
while(array[i] != e) // 这个比上面的方法少了个判断,当数组过大时,效率就会有差别
i++;
// 再把最后一个元素复原
array[length - 1] = key;
if(i == length - 1)
return -1;
return i;
}

// 向index位置插入元素
public void add(int index, int e){
if(index > length || index < 0)
throw new IllegalArgumentException("添加元素失败,index非法");

if(length >= array.length)
throw new IllegalArgumentException("添加元素失败,容量已达到最大");

for(int i = length; i > index; i--){
array[i] = array[i - 1];
}
array[index] = e;
length ++;
}

// 删除当前数组的index位置的元素
public int remove(int index){
if(index > length || index < 0)
throw new IllegalArgumentException("删除元素失败,index非法");
int e = array[index];
for(int i = index; i < length - 1; i++){
array[i] = array[i + 1];
}

length --;
return e;
}

@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("capacity: %d, length: %d\n", array.length, length));
res.append("Array: [ ");
for (int i = 0; i < length; i++) {
res.append(array[i]);
if(i == length - 1)
res.append(']');
else
res.append(", ");
}
return res.toString();
}


5. 以后再补充别的扩展