定义

• 线性表的顺序存储，即逻辑上相邻且物理位置上也相邻。

存储结构

• 设顺序表起始内存地址为 。

修改

要求

• 更改第 位的元素 。

实现

1
2#include <iostream>
3using namespace std;
4
5class Vector
6{
7private:
8/// @brief length of the vector
9int length = 0;
10/// @brief data container
11int *data;
12
13public:
14// constructor & deconstructor
15Vector(int length);
16~Vector();
17// methods
18void insertAt(int index, int value);
19void removeAt(int index);
20// getters & setters
21int lenth();
22// operator overload
23int &operator[](int i);
24};
25
26/// @brief constructor
27/// @param length vector length
28Vector::Vector(int length)
29{
30// set the length of the vector
31this->length = length;
32// allocate memory & return the address
33data = new int[length];
34// initialize the vector
35for (int i = 0; i < length; i++)
36data[i] = 0;
37}
38
39/// @brief deconstructor
40Vector::~Vector()
41{
42delete[] data;
43}
44
45/// @brief vector accessor
46/// @param index index of the element
47/// @return element at index
48int &Vector::operator[](int index)
49{
50return data[index];
51}
52

插入

要求

• 在第 位前插入一个元素 。

预想

1. 将第 位到表尾的元素全部向后移动。
2. 将第 位修改成 。
3. 表长加 1 。

实现

1
2/// @brief insert the value after the index
3/// @param index insert position
4/// @param value the value to be inserted
5void Vector::insertAt(int index, int value)
6{
7// vaildate index
8if (index < 0 || index > length)
9return;
10// create a new int array
11int *temp = new int[++length];
12// copy first part of data
13for (int i = 0; i < index - 1; i++)
14temp[i] = data[i];
15// assign the new value at index
16temp[index - 1] = value;
17// copy remaining data
18for (int i = index; i < length - 1; i++)
19temp[i] = data[i];
20// release old ptr
21delete[] data;
22// point to new space
23data = temp;
24}
25

删除

要求

• 删除第 位的元素 。

预想

1. 将第 位到表尾的元素全部向前移动 1 个位置。
2. 表长减 1 。

实现

1
2/// @brief remove element at index
3/// @param index element index
4void Vector::removeAt(int index)
5{
6// vaildate index
7if (index < 0 || index > length)
8return;
9// create a new int array
10int *temp = new int[--length];
11// copy data ∈ [a_0, a_index)
12for (int i = 0; i < index; i++)
13temp[i] = data[i];
14// copy data ∈ (a_index, a_length)
15for (int i = index; i < length; i++)
16temp[i] = data[i + 1];
17// release old ptr
18delete[] data;
19// point to new space
20data = temp;
21}
22