数据结构之向量

发表于 | 更新于: | 分类于 |
字数统计: 1,241 | 阅读时长 ≈ 7

什么是向量(vector)

向量（vector）是一个抽象数据结构，为一组数据模型，定义一组操作，不涉及具体的储存方式，可以用不同的数据类型来实现，多数使用数组来实现，所以也可以认为，向量是数组的抽象与泛化。
向量（Vector）和列表（List）都属于序列，所谓序列就是以某种规律依次排列的一组对象，是数据结构设计的基础。

点击这里查看博客对应的完整代码

基于数组的简单实现

下面是一个简单的向量接口，包含一些常用的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public interface VectorTemp<E> {
    int size();

    boolean isEmpty();

    boolean contains(E e);

    int indexOf(E e, int index);

    int lastIndexOf(E e);

    int lastIndexOf(E e, int index);

    E get(int index) throws VectorViolationException;

    E set(int index, E e) throws VectorViolationException;

    boolean add(E e);

    E insert(int index, E obj);

    E remove(int index) throws VectorViolationException;

}

下面是上面我们定义的操作实现

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

public class MyVector<E> implements VectorTemp<E> {

    private int capacityIncrement;

    private int elementCount;

    private Object[] elementData;



    public MyVector(int initialCapacity) {
        if (initialCapacity < 0){
            throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = initialCapacity;
    }

    public MyVector(){
        this(10);
    }

    public MyVector(Collection<? extends E> c) {
        elementData = c.toArray();
        elementCount = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class){
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
        }
    }

    @Override
    public synchronized int size() {
        return elementCount;
    }

    @Override
    public synchronized boolean isEmpty() {
        return elementCount == 0;
    }

    @Override
    public boolean contains(E e) {
        return indexOf(e, 0) >= 0;
    }

    @Override
    public synchronized int indexOf(Object o, int index) {
        if (o == null) {
            for (int i = index ; i < elementCount ; i++){
                if (elementData[i]==null) {
                    return i;
                }
            }
        } else {
            for (int i = index ; i < elementCount ; i++) {
                if (o.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public synchronized int lastIndexOf(Object o) {
        return lastIndexOf(o, elementCount-1);
    }

    @Override
    public synchronized int lastIndexOf(Object o, int index) {
        if (index >= elementCount) {
            throw new IndexOutOfBoundsException(index + " >= " + elementCount);
        }

        if (o == null) {
            for (int i = index; i >= 0; i--) {
                if (elementData[i] == null){
                    return i;
                }
            }

        } else {
            for (int i = index; i >= 0; i--) {
                if (o.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public synchronized E get(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        return elementData(index);
    }

    @Override
    public synchronized E set(int index, Object element) throws VectorViolationException {
        rankValid(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    @Override
    public synchronized boolean add(Object e) {
        if(elementCount + 1 >= capacityIncrement){
            capacity();
        }
        elementData[elementCount] = e;
        elementCount++;
        return true;
    }

    @Override
    public synchronized E insert(int index, E obj) {
        if(index < 0 || index > elementCount){
            throw new VectorViolationException("rankOutOfBound");
        }
        if(elementCount + 1 >= capacityIncrement){
            capacity();
        }
        for (int i = elementCount; i > index; i--) {
            elementData[i] = elementData[i - 1];
        }
        elementData[index] = obj;
        elementCount++;
        return obj;
    }

    private E elementData(int index) {
        return (E) elementData[index];
    }

    @Override
    public synchronized E remove(int index) throws VectorViolationException {
        rankValid(index);
        E bak = elementData(index);
        for (int i = index; i < elementCount - 1; i++){
            elementData[i] = elementData[i + 1];
        }
        elementCount--;
        return bak;
    }

    public synchronized void capacity() {
        capacityIncrement *= 2;
        Object[] arrObj = new Object[capacityIncrement];
        System.arraycopy(elementData, 0, arrObj, 0, elementCount);
        elementData = arrObj;
    }

    private void rankValid(int index){
        if(index < 0 || index >= capacityIncrement){
            throw new VectorViolationException("rankOutOfBound");
        }
    }

}

下面是测试代码

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
VectorTemp<String> myVector = new MyVector<String>(2);
System.out.println("是否为空：" + myVector.isEmpty());
System.out.println("增加元素,当前大小：" + myVector.size());
myVector.add("A");
myVector.add("B");
myVector.add("C");
for (int i = 0; i < myVector.size(); i++){
    System.out.println(myVector.get(i));
}

System.out.println("是否为空：" + myVector.isEmpty());
System.out.println("插入元素,当前大小：" + myVector.size());
myVector.insert(2,"I");
for (int i = 0; i < myVector.size(); i++){
    System.out.println(myVector.get(i));
}
System.out.println("删除元素,当前大小：" + myVector.size());
myVector.remove(3);
for (int i = 0; i < myVector.size(); i++){
    System.out.println(myVector.get(i));
}
System.out.println("是否存在元素R：" + myVector.contains("R"));
System.out.println("替换元素,当前大小：" + myVector.size());
myVector.set(1,"R");
System.out.println("是否存在元素R：" + myVector.contains("R"));
for (int i = 0; i < myVector.size(); i++){
    System.out.println(myVector.get(i));
}


//执行结果
是否为空：true
增加元素,当前大小：0
A
B
C
是否为空：false
插入元素,当前大小：3
A
B
I
C
删除元素,当前大小：4
A
B
I
是否存在元素R：false
替换元素,当前大小：3
是否存在元素R：true
A
R
I

到这里，一个完整的向量实现就结束了，感兴趣的可以看看java中的向量（java.util.Vector）源码。

总结

  • 向量是一个抽象数据结构，为一组数据模型，定义一组操作，不涉及具体的储存方式，可以用不同的数据类型来实现。
  • 向量属于序列的一种，以某种规律依次排列的一组对象。
  • 向量是是数据结构设计的基础。
Choice wechat
关注公众号，获取文章更新通知。
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！