用Java实现顺序表及其基本操作_编写一个java程序,实现顺序表的各种基本运算,并在此基础上设计一个主程序完成

package lwh.linearlist.seqlist;

import java.util.Arrays;

public class SeqList {

    private int maxLength = 10;
    private int[] a;
    private int size;

    public SeqList(){}

    public SeqList(int[] b){
        a = b;
        size = a.length;
    }

    public SeqList(int maxLength){
        this.maxLength = maxLength;
        a = new int[maxLength];
        size = 0;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int length(){
        return size;
    }

    //将元素x插到下标i的元素之后
    boolean insert(int i, int x){
        if(i < -1 || i > size - 1){
            System.out.println("Insert out of Bounds");
            return false;
        }
        if(size == maxLength){
            System.out.println("Overflow");
            return false;
        }
        for(int j = size - 1; j > i; j--){
            a[j+1] = a[j];
        }
        a[i+1] = x;
        size++;
        return true;
    }

    //删除i下标的元素
    public boolean delete(int i){
        if( i < 0 || i > size - 1){
            System.out.println("Index out of Bound");
            return false;
        }
        if(size == 0){
            System.out.println("No number to delete");
            return false;
        }
        for(int j = i; j <= size - 1; j++){
            a[j] = a[j+1];
        }
        size--;
        return true;
    }

    //按值查找第一个为x的元素下标
    public int find(int x){
        for(int i = 0; i < size - 1; i++){
            if(x == a[i])
                return i;
        }
        return -1;
    }

    //删除最小值(假设唯一)并返回该最小值,空出的位置由最后一个元素填补
    public int deleteMin(){
        if(size == 0){
            System.out.println("No number to delete");
            return Integer.MAX_VALUE;
        }
        int index = 0;
        for(int i = 1; i < size; i++){
            if(a[i] < a[index]){
                index = i;
            }
        }
        int min = a[index];
        a[index] = a[size-1];
        size--;
        return min;
    }

    //逆置顺序表,要求空间复杂度O(1)
    public void reverse(){
        for(int i = 0; i <= (size - 1)/2; i++){
            int temp = a[i];
            a[i] = a[size-1-i];
            a[size-1-i]=temp;
        }
    }

    //删除所有值为x的元素,时间复杂度O(n)，空间复杂度O(1)
    //用k统计顺序表中不等于x的个数,边扫描边统计,并将不等于x的元素放到k位置上,最后修改顺序表长度为k
    public boolean deleteAllx1(int x){
        if(size == 0){
            System.out.println("No number to delete");
            return false;
        }
        int k = 0;
        for(int i = 0; i < size; i++){
            if(a[i] != x){
                a[k] = a[i];
                k++;
            }
        }
        size = k;
        return true;
    }

    //删除有序顺序表中值在s与t之间的元素(s<t)
    public boolean deleteNums1(int s, int t){
        if(size == 0){
            System.out.println("No number to delete");
            return false;
        }
        if(s >= t){
            System.out.println("Please input s <= t");
            return false;
        }
        int start = 0;
        int end = 0;
        for(int i = 0; i < size; i++){
            if(a[i] < s){
                continue;
            }else{
                start = i;
                break;
            }
        }
        for(int i = size - 1; i >= 0; i--){
            if(a[i] > t){
                continue;
            }else{
                end = i;
                break;
            }
        }
        int k = end - start + 1;
        for(int i = start; i + k < size; i++){
            a[i] = a[i+k];
        }
        size = size - k;
        return true;
    }

    //删除顺序表中值在s与t之间的元素(s<t)
    public boolean deleteNums2(int s, int t){
        if(size == 0){
            System.out.println("No number to delete");
            return false;
        }
        if(s >= t){
            System.out.println("Please input s <= t");
            return false;
        }
        int k = 0;
        for(int i = 0; i < size; i++){
            if(a[i] < s || a[i] > t){
                a[k] = a[i];
                k++;
            }
        }
        size = k;
        return true;
    }

    //删除有序顺序表中所有其值重复的元素,不保留重复元素
    public void deleteRepeat1(){
        int k = 1;
        for(int i = 0; i < size - 1; i++){
            if(a[i] == a[i+1]){
                k++;
                continue;
            }
            if(k > 1){
                //从i+1向前移动k个位置
                for(int j = i + 1; j < size; j++){
                    a[j-k] = a[j];
                }
                size = size - k;
                k = 1;
                i = -1;
            }
        }
    }

    //删除有序顺序表中所有其值重复的元素,保留一个
    public boolean deleteRepeat2(){
        if(size == 0){
            System.out.println("No number to delete");
            return false;
        }
        int i,j;
        for(i = 0, j = 1; j < size; j++){
            if(a[i] != a[j]){
                a[++i] = a[j];
            }
        }
        size = i + 1;
        return true;
    }

    //将两个有序顺序表合成新的有序表
    public SeqList merge1(SeqList s1, SeqList s2){
        SeqList s3 = new SeqList(s1.maxLength + s2.maxLength);
        System.arraycopy(s1.a, 0, s3.a, 0, s1.a.length);
        System.arraycopy(s2.a, 0, s3.a, s1.a.length, s2.a.length);
        s3.size = s1.a.length + s2.a.length;
        Arrays.sort(s3.a, 0, s3.size);;
        return s3;
    }

    //将两个有序顺序表合成新的有序表
    public SeqList merge2(SeqList s1, SeqList s2){
        SeqList s3 = new SeqList(s1.maxLength + s2.maxLength);
        int i = 0, j = 0, k = 0;
        while(i < s1.a.length && j < s2.a.length){
            if(s1.a[i] <= s2.a[j])
                s3.a[k++] = s1.a[i++];
            else
                s3.a[k++] = s2.a[j++];
        }
        while(i < s1.a.length)
            s3.a[k++] = s1.a[i++];
        while(i < s2.a.length)
            s3.a[k++] = s2.a[j++];
        s3.size = k;
        return s3;
    }

    //线性表递增,查找x并将其与后继元素交换,不存在插入该元素使表中元素仍有序
    public boolean findOrinsert(int x, int left, int right){
        int mid = (left + right) / 2;
        if(left <= right){
            if(x == a[mid]){
                if(mid < size - 1){
                    a[mid] = a[mid+1];
                    a[mid+1] = x;
                }
                return true;
            }else if(x < a[mid]){
                return findOrinsert(x, left, mid-1);
            }else{
                return findOrinsert(x, mid+1, right);
            }
        }
        if(mid == 0){
            if(x <= a[mid]){
                insert(-1, x);
            }else{
                insert(0, x);
            }
        }else{
            insert(mid, x);
        }
        return false;
    }

    //将指定范围内的顺序表元素逆置
    public void reverse(int start, int end){
        for(int i = start; i <= start + (end - start) / 2; i++){
            int temp = a[i];
            a[i] = a[end-i+start];
            a[end-i+start] = temp;
        }
    }

    //将顺序表中两个数组互换位置,从[a,b,c,1,2,3,4]-->[1,2,3,4,a,b,c]
    //调用reverse(int start, int end)
    public void switchArray(){
        reverse(0, size-1);
        reverse(0, 4);
        reverse(5, 8);
    }

    public void print(){
        if(size == 0){
            System.out.println("No num");
            return;
        }
        System.out.print("[");
        for(int i = 0; i < size; i++){
            if(i < size - 1){
                System.out.print(a[i] + ",");
            }else{
                System.out.print(a[i] + "]");
            }
        }
        System.out.println();
    }
}
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
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303