1、采用一个数组实现一个顺序线性表中添加元素、删除元素等基本操作
?
|
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
|
package com.ietree.basic.datastructure.Sequence;
import java.util.Arrays;
/**
* 顺序线性表
*
* @param <T>
* @author Dylan
*/
public class SequenceList<T> {
private final int DEFAULT_SIZE = 16;
// 保存数组的长度
private int capacity;
// 定义一个数组用于保存顺序线性表的元素
private Object[] elementData;
// 保存顺序表中元素的当前个数
private int size = 0;
// 以默认数组长度创建顺序线性表
public SequenceList() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
// 以一个初始化元素创建顺序线性表
public SequenceList(T element) {
this();
elementData[0] = element;
size++;
}
/**
* 以指定长度的数组来创建顺序线性表
* @param element 指定顺序线性表中第一个元素
* @param initSize 指定顺序线性表底层数组的长度
*/
public SequenceList(T element, int initSize) {
capacity = 1;
// 把capacity设为大于initSize的最小的2的n次方
while (capacity < initSize) {
capacity <<= 1;
}
elementData = new Object[capacity];
elementData[0] = element;
size++;
}
// 获取顺序线性表的大小
public int length() {
return size;
}
// 获取顺序线性表中索引为i处的元素
public T get(int i) {
if (i < 0 || i > size - 1) {
throw new IndexOutOfBoundsException("线性表索引越界");
}
return (T) elementData[i];
}
// 查找顺序线性表中指定元素的索引
public int locate(T element) {
for (int i = 0; i < size; i++) {
if (elementData[i].equals(element)) {
return i;
}
}
return -1;
}
// 向顺序线性表的指定位置插入一个元素
public void insert(T element, int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("线性表索引越界");
}
ensureCapacity(size + 1);
// 将指定索引处之后的所有元素向后移动一格
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
// 在插入元素之前需要确保顺序线性表的长度大于插入之后顺序线性表的长度
private void ensureCapacity(int minCapacity) {
// 如果数组的原有长度小于目前所需的长度
if (minCapacity > capacity) {
// 不断地将capacity * 2，直到capacity大于minCapacity
while (capacity < minCapacity) {
capacity <<= 1;
}
elementData = Arrays.copyOf(elementData, capacity);
}
}
// 在线性顺序表的开始处添加一个元素
public void add(T element) {
insert(element, size);
}
// 删除顺序线性表中指定索引处的元素
public T delete(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException("线性表索引越界");
}
T oldValue = (T) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
// 清空最后一个元素
elementData[--size] = null;
return oldValue;
}
// 删除顺序线性表中最后一个元素
public T remove() {
return delete(size - 1);
}
// 判断顺序线性表是否为空表
public boolean empty() {
return size == 0;
}
// 清空线性表
public void clear() {
Arrays.fill(elementData, null);
size = 0;
}
public String toString() {
if (size == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
sb.append(elementData[i].toString() + ",");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}
|
测试模拟线性表的基本操作：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
package com.ietree.basic.datastructure.Sequence;
/**
* 测试类
*
* @author Dylan
*/
public class SequenceListTest {
public static void main(String[] args) {
SequenceList<String> list = new SequenceList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");
list.add("ddd");
list.insert("eee", 1);
System.out.println(list);
list.delete(2);
System.out.println(list);
System.out.println("ccc在顺序线性表中的位置：" + list.locate("ccc"));
}
}
|
程序输出：
?
|
1
2
|
[aaa,eee,bbb,ccc,dd]
[aaa,eee,ccc,dd]
|
相关文章
猜你喜欢
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
- ASP.NET自助建站系统的数据库备份与恢复操作指南 2025-06-10
