haohao

数据结构与算法(Java 实现)之线性表(一)

Markdown

成年人学习的目的,应该是追求更好的思维模型,而不是更多的知识。


线性表

linearlist

线性表(Linear List)是由 n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1] 组成的有限序列。


线性表按照存储结构分为:顺序表和链表
顺序表:用一块地址连续的存储空间依次存储线性表中的数据元素
链表:链式存储结构的线性表,逻辑上相邻的元素在物理上可以不相邻,元素间的逻辑关系表现在节点的连接上。

抽象线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* Created by HaohaoChang on 2017/9/8.
* 抽象线性表操作
*/
public interface List {
int size();
void insert(int index, Object o);
Object delete(int index);
Object getData(int index);
boolean isEmpty();
}

顺序表

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
/**
* Created by HaohaoChang on 2017/9/8.
* 顺序表
* 数据元素存储在连续地址空间的内存单元
* 插入/删除操作时间复杂度O(n)
*/
public class SeqList implements List {
private static final String TAG = "SeqList";
final int defultSize = 10;
int maxSize;
int size;
Object[] array;
public SeqList() {
initiate(defultSize);
}
public SeqList(int size) {
initiate(size);
}
private void initiate(int sz) {
maxSize = sz;
size = 0;
array = new Object[sz];
}
@Override
public int size() {
return size;
}
@Override
public void insert(int index, Object o) throws IllegalArgumentException {
if (maxSize == index) {
throw new IllegalArgumentException("Seq list is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("argument error.");
}
for (int i = size; i > index; i--) {
array[i] = array[i-1];
}
array[index] = o;
size ++;
System.out.println("insert item : " + o);
}
public void add(Object o) throws IllegalArgumentException {
if (maxSize == size) {
throw new IllegalArgumentException("Seq list is full.");
}
array[size] = o;
size ++;
System.out.println("add item : " + o);
}
@Override
public Object delete(int index) {
if (size == 0) {
throw new IllegalArgumentException("Seq list is empty.");
}
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("argument error.");
}
Object o = array[index];
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size --;
System.out.println("delete item : " + o + ",index : " + index);
return o;
}
@Override
public Object getData(int index) {
if (size == 0) {
throw new IllegalArgumentException("Seq list is empty.");
}
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("argument error.");
}
return array[index];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (size == 0) {
return "null";
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < size; i++) {
stringBuilder.append("index : ").append(i).append(", value : ").append(array[i]).append("\n");
}
return stringBuilder.toString();
}
public static void main(String[] args) {
SeqList seqList = new SeqList();
seqList.insert(0, "Kotlin");
seqList.add("Android");
seqList.insert(2, "NodeJS");
System.out.println(seqList);
seqList.delete(0);
seqList.delete(0);
System.out.println(seqList);
}
}

代码运行结果:

1
2
3
4
5
6
7
8
9
10
insert item : Kotlin
add item : Android
insert item : NodeJS
index : 0, value : Kotlin
index : 1, value : Android
index : 2, value : NodeJS
delete item : Kotlin,index : 0
delete item : Android,index : 0
index : 0, value : NodeJS

可变容量的顺序表

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
/**
* Created by HaohaoChang on 2017/9/13.
* 可变容量顺序表
*/
public class VarSeqList implements List {
static final int defaultSize = 10;
int size;
int length;
Object[] array;
public VarSeqList() {
array = new Object[defaultSize];
size = defaultSize;
length = 0;
}
@Override
public int size() {
return length;
}
@Override
public void insert(int index, Object o) {
if (index < 0 || index > length) {
throw new IllegalStateException("参数错误");
}
if (length == size) {
extend();
}
for (int i = length; i > index; i--) {
array[i] = array[i -1];
}
array[index] = o;
length ++;
}
@Override
public Object delete(int index) {
System.out.println(index + " ," + length);
if (length == 0) {
throw new IllegalStateException("列表为空");
}
if (index < 0 || index > length - 1) {
throw new IllegalStateException("参数错误");
}
Object o = array[index];
for (int i = index; i < length - 1; i++) {
array[i] = array[i + 1];
}
length --;
return o;
}
@Override
public Object getData(int index) {
if (length == 0) {
throw new IllegalStateException("列表为空");
}
if (index < 0 || index > length - 1) {
throw new IllegalStateException("参数错误");
}
return array[index];
}
@Override
public boolean isEmpty() {
return length == 0;
}
@Override
public String toString() {
if (length == 0) {
throw new IllegalStateException("列表为空");
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < length; i++) {
stringBuilder.append(getData(i)).append("\n");
}
return stringBuilder.toString();
}
public void add(Object o) {
if (length == size) {
extend();
}
array[length] = o;
length ++;
}
private void extend() {
// 小心越界
size *= 2;
Object[] newArray = new Object[size];
for (int i = 0; i < length; i++) {
newArray[i] = array[i];
}
array = newArray;
}
private void clear() {
length = 0;
size = defaultSize;
array = new Object[size];
}
public static void main(String[] args) {
VarSeqList varSeqList = new VarSeqList();
for (int i = 0; i < 1000; i++) {
varSeqList.add(i);
}
for (int i = 0; i < 995; i++) {
varSeqList.delete(0);
}
System.out.println(varSeqList.toString());
}
}



联系我

Wechat ID

公众号

生活不止于眼前的苟且, 还有诗和远方的田野