前言
数组实现线性表,并完成所有关于线性表的基本操作,实现了线性表添加数据时的自动扩容.
线性表函数接口
接口中定义了线性表所有需要实现的功能及操作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
46public interface SLInterface<E> {
//是否为空
boolean isEmpty(SeqList<E> SL);
//初始化
void SListInit(SeqList<E> SL,int cap);
//销魂
void SListDestroy(SeqList<E> SL);
//头插
void SListPushFront(SeqList<E> SL,Object data);
//头删
void SListPopFront(SeqList<E> SL);
//尾插
void SListPushTail(SeqList<E> SL,Object data);
//尾删
void SListPopTail(SeqList<E> SL);
//在pos所在的下标做数据插入
void SListInsert(SeqList<E> SL,int pos, Object data);
//删除pos所在下标的数据
void SListErase(SeqList<E> SL, int pos);
// 找从 0 开始的第一个，如果找到了，返回数据所在的下标
// 如果没找到返回 -1
int SeqListFind(SeqList<E> SL, Object data);
// 删除第一个遇到的 data
void SeqListRemove(SeqList<E> SL, Object data);
// 删除所有遇到的 data
void SeqListRemoveAll(SeqList<E> SL, Object data);
// 修改，pos 所在的下标
void SeqListModify(SeqList<E> SL, int pos, Object data);
// 打印
void SeqListPrint(SeqList<E> SL);
// 内部接口,判断是否需要进行扩容
void CheckCapacity(SeqList<E> SL);
// 冒泡排序
void SeqListBubbleSort(SeqList<E> SL);
// 二分查找（前提是数据有序）
// 如果找到，返回数据所在下标，如果没找到，返回 -1
int SeqListBinarySearch(SeqList<E> SL, Object data);
}
接口的函数实现
所有的接口中的方法都需要通过他的子类来一一实现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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258public class SeqList<E> implements SLInterface<E> {
private Object[] array;
//线性表容量
private int capacity;
//实际所用大小
private int length;
public boolean isEmpty(SeqList<E> SL) {
if(SL.array == null){
System.out.println("静态顺序表未创建");
return false;
}
if(SL.capacity == 0){
System.out.println("静态顺序表容量初始化为0");
}
System.out.println("顺序表不为空");
return true;
}
public void SListInit(SeqList<E> SL,int cap) {
SL.array = new Object[cap];
this.capacity = cap;
this.length = 0;
}
public void SListDestroy(SeqList<E> SL) {
SL.array =null;
SL.length = SL.capacity = 0;
}
public void SListPushFront(SeqList<E> SL,Object data) {
try{
CheckCapacity(SL);
for(int i=SL.length; i>=1; i--){
SL.array[i] = SL.array[i-1];
}
SL.array[0] = data;
SL.length++;
}catch(Exception E){
throw new NullPointerException();
}
}
public void SListPopFront(SeqList<E> SL) {
try{
if(SL.length>0){
for(int i=1; i<SL.length; i++){
SL.array[i-1] = SL.array[i];
}
SL.length--;
}else{
System.out.println("顺序表已经为空,不能进行删除操作");
}
}catch(Exception e){
throw new NullPointerException();
}
}
public void SListPushTail(SeqList<E> SL,Object data) {
try{
CheckCapacity(SL);
SL.array[SL.length] = data;
SL.length++;
}catch(Exception e){
throw new NullPointerException();
}
}
public void SListPopTail(SeqList<E> SL) {
try{
SL.length--;
}catch(Exception e){
throw new NullPointerException();
}
}
public void SListInsert(SeqList<E> SL,int pos, Object data){
//此处i表示的是元素的位置
try{
CheckCapacity(SL);
if(!(pos>=0 && pos<= SL.length-1)){
System.out.println("指定插入位置不合法");
return;
}
for(int i=SL.length; i>=pos; i--){
SL.array[i] = SL.array[i-1];
}
SL.array[pos] = data;
SL.length++;
}catch(Exception e){
throw new NullPointerException();
}
}
public void SListErase(SeqList<E> SL, int pos) {
try{
if(!(pos>=0 && pos<=SL.length)){
return;
}
for(int i=pos; i<SL.length; i++){
SL.array[i] = SL.array[i+1];
}
SL.length--;
}catch(Exception e){
throw new NullPointerException();
}
}
public int SeqListFind(SeqList<E> SL, Object data) {
try{
for(int i=0; i<SL.length; i++){
if(SL.array[i] == data || SL.array[i].equals(data)){
System.out.println("找到了指定的元素: " +data+"他的下标为: "+i);
return i;
}
}
System.out.println("没有找到指定元素");
}catch(Exception e){
throw new NullPointerException();
}
return -1;
}
public void SeqListRemove(SeqList<E> SL, Object data) {
try{
for(int i=0; i<SL.length; i++){
if(SL.array[i] == data || SL.array[i].equals(data)){
for(int j=i; j<SL.length-1; j++){
SL.array[j] = SL.array[j+1];
}
}
}
SL.length--;
}catch(Exception e){
throw new NullPointerException();
}
}
public void SeqListRemoveAll(SeqList<E> SL, Object data) {
try{
for(int i=0; i<SL.length; i++){
if(SL.array[i] == data || SL.array[i].equals(data)){
for(int j=i; j<SL.length-1; j++){
SL.array[j] = SL.array[j+1];
}
i--;
SL.length--;
}
}
}catch(Exception e){
throw new NullPointerException();
}
}
public void SeqListModify(SeqList<E> SL, int pos, Object data) {
try{
SL.array[pos] = data;
}catch(Exception e){
throw new NullPointerException();
}
}
public void SeqListPrint(SeqList<E> SL) {
for(int i=0; i<SL.length; i++){
System.out.print(SL.array[i]+" ");
}
System.out.println();
}
public void CheckCapacity(SeqList<E> SL) {
try{
if(SL.length < SL.capacity){
return;
}
int newCapacity = SL.capacity*2;
Object[] newArray = new Object[newCapacity];
for(int i=0; i<SL.length; i++){
newArray[i] = SL.array[i];
}
SL.array = newArray;
SL.capacity = newCapacity;
newArray = null;
}catch(Exception e){
throw new NullPointerException();
}
}
public void SeqListBubbleSort(SeqList<E> SL) {
try {
int i,j;
for (i = 0; i < SL.length-1; i++){
int flag = 1;
for(j=0; j<SL.length-1-i; j++){
if((Integer)SL.array[j] > (Integer) SL.array[j+1]){
Integer tmp = (Integer) SL.array[j];
SL.array[j] = SL.array[j+1];
SL.array[j+1] = tmp;
flag = 0;
}
}
if(flag == 1){
break;
}
}
} catch (Exception e) {
throw new NullPointerException();
}
}
// 二分查找的前提是已经排好序的数列
public int SeqListBinarySearch(SeqList<E> SL, Object data) {
try{
int left = 0;
int right = SL.length-1;
while(left <= right){
int mid = (left-right)/2+right;
if(SL.array[mid] == data){
return mid;
}
if((Integer)SL.array[mid] > (Integer) data){
right = right-mid;
}
if((Integer)SL.array[mid] < (Integer) data){
left = left+mid;
}
}
}catch(Exception e){
throw new NullPointerException();
}
return -1;
}
}
以上便是数组实现线性表~