【代码】线性表之顺序表

发表于 更新于 阅读次数：

前言

顺序表Java版的API实现

源代码

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;

public class SequenceList<T> {

    private T[] elements;
    private int elementsLength;

    public SequenceList(int capacity) {
        elements = (T[])(new Object[capacity]);
        elementsLength = 0;
    }

    /**
     * 清空线性表
     */
    public void clear() {
        elementsLength = 0;
    }

    /**
     * 判断线性表是否为空
     */
    public boolean isEmpty() {
        return elementsLength==0;
    }

    /**
     * 获取线性表中元素的个数
     */
    public int length() {
        return elementsLength;
    }

    /**
     * 获取线性表的总存储空间
     */
    public int size() {
        return elements.length;
    }

    /**
     * 获取并返回线性表中的指定索引的元素
     */
    public T get(int index) {
        return elements[index];
    }

    /**
     * 向线性表末尾添加一个元素
     */
    public void insert(T t) {
        elements[elementsLength++] = t;
        // 如果添加元素后，元素总数多于元素总长度的一半，那么扩容
        if (elementsLength >= elements.length/2) {
            expansion();
        }
    }

    /**
     * 向线性表指定索引处添加元素
     */
    public void insert(T t, int index) {
        // 先把指定索引的元素及其后面的元素向后移动一位
        for (int i = elementsLength-1; i >= index; i--) {
            elements[i+1] = elements[i];
        }
        // 再把元素添加到指定索引处
        elements[index] = t;
        elementsLength++;
        // 如果添加元素后，元素总数多于元素总长度的一半，那么扩容
        if (elementsLength >= elements.length/2) {
            expansion();
        }
    }

    /**
     * 删除并返回线性表中指定索引的元素
     */
    public T remove(int index) {
        // 创建一个元素，用于存放需要删除的元素
        T t = elements[index];
        for (int i = index; i < elementsLength-1; i++) {
            elements[i] = elements[i+1];
        }
        elementsLength--;
        // 如果删除元素操作后，存储的元素不足总长度四分之一，那么缩容
        if (elementsLength <= elements.length/4) {
            shrink();
        }
        return t;
    }

    /**
     * 在现象表中查找首次出现的指定元素，返回索引，如果不存在，返回-1
     */
    public int indexOf(T t) {
        for (int i = 0; i < elementsLength; i ++) {
            if (elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 线性表的2倍扩容
     */
    public void expansion() {
        // 创建一个新的顺序表，存储空间是原来的2倍
        T[] elementsNew = (T[])(new Object[elementsLength*2]);
        // 将所有数据转移到新顺序表
        for (int i = 0; i < elementsLength; i ++) {
            elementsNew[i] = elements[i];
        }
        // 把新的顺序表替换为以前的顺序表
        elements = elementsNew;
    }

    /**
     * 线性表的0.5倍缩容
     */
    public void shrink() {
        // 创建一个新的顺序表，存储空间是原来的0.5倍
        T[] elementsNew = (T[])(new Object[elementsLength/2]);
        // 将所有数据转移到新顺序表
        for (int i = 0; i < elementsLength; i++) {
            elementsNew[i] = elements[i];
        }
        // 把新的顺序表替换为以前的顺序表
        elements = elementsNew;
    }

    /**
     * 输出线性表
     */
    public String toString() {
        String str = "";
        for (int i = 0; i < elementsLength; i ++) {
            str += elements[i];
            if (i!=elementsLength-1) {
                str += " ";
            }
        }
        return str;
    }

}

完成

参考文献

哔哩哔哩——黑马程序员