数据结构实现 1.1：动态数组（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序实现

• 2.1 增加操作

• 2.2 删除操作

• 2.3 修改操作

• 2.4 查找操作

• 2.5 其他操作

• 3. 算法复杂度分析

• 3.1 增加操作

• 3.2 删除操作

• 3.3 修改操作

• 3.4 查找操作

• 4. 完整代码

1. 概念及基本框架

数组 是一种 线性结构 ，而且存储上属于 顺序存储（即内存的物理空间是连续的），也就是线性表中的 顺序表 。数组结构如下图所示：

下面以一个我实现的一个简单的数组类来进一步理解数组。

这里为了避免重复设计就可以兼容更多数据类型，引入了 泛型 ，即 模板 的概念。（模板的关键字是 class 或 typename）
这里的 数组容量 表示数组最多可存放空间的大小，而 数组大小 指的是数组实际占用空间的大小。为了保护数据，这两个变量以及 数组数据 都设置为 private 。
构造数组时，可以初始化数组的数组容量。（默认是10）
那么就会出现一个问题，如果这块内存被用完了怎么办？因为数组的物理空间必须连续，所以我们必须另外申请一块更大的内存，先把当前数组复制到新的内存上，然后释放掉旧的内存空间。同理，如果很多的内存都没有被利用，我们也可以适当缩小数组容量。所以，我们需要一个这样的 扩容（缩容）函数 去动态的实现数组。代码如下：

实现了前面的程序之后，接下来就是一个数组的增、删、改、查以及一些其他基本操作，接下来利用代码去实现。

2. 基本操作程序实现

2.1 增加操作

首先，在类体内进行增加操作函数的原型说明。这里包括三个函数：
add（添加到任意位置）
addFirst（添加到头部）
addLast（添加到尾部）
然后分别去实现它们。

由于这些函数在类体外，所以每个函数头部必须添加一行代码：

表示该函数使用模板，下面同理。

增加元素时可能会用到了扩容函数，当原空间已经使用完的时候进行扩容操作。这里我每次将容量扩展到原来的 2 倍，其实也可以扩展到原来的 1.5 倍。

2.2 删除操作

同理，在类体内进行删除函数的原型说明。这里包括四个函数：
remove（删除任意位置元素）：返回删除元素的值。
removeFirst（删除头部元素）：返回删除元素的值。
removeLast（删除尾部元素）：返回删除元素的值。
removeElement（删除特定元素）：这里我利用下面的 find 函数来实现的，所以删除的是第一个这样的元素，如果想把这样的元素都删掉，可以写一个新的函数来实现。
然后分别去实现它们。

删除时用到了缩容函数，当原空间被利用太少的话，就使用一块新的更小的空间。这里当空间利用率不足 1/4 时，我将内存缩至原空间的 1/2 ，即还有一些空间可以去添加。
这里需要注意的是，不要使用当空间利用率不足 1/2 时，就将内存缩至原空间的 1/2 ，这样可能会导致震荡。
例如当空间恰好被利用完了以后，增加了一个元素，这时空间变为 2 倍，然后又删除了一个元素，空间又降至原大小，然后又增加了一个元素，空间又变为 2 倍，再删除一个元素，空间又降至原大小……循环往复，造成震荡。
这里删除操作的“删除位置非法”后面返回的 NULL 也可以用 throw 抛异常来实现，这里只是为了方便。

2.3 修改操作

修改操作只有一个函数
set（修改指定位置的值）
同理，在类体内进行删除函数的原型说明，然后在类体外实现。

2.4 查找操作

查找函数有三个：
get（返回特定位置元素）
find（返回第一个特定元素位置）
contains（返回是否包含特定元素）
分别对它们进行实现。

同理，这里 get 函数的“访问位置非法”后面返回的 NULL 也可以用 throw 抛异常来实现，这里只是为了方便。

2.5 其他操作

数组还有一些其他的操作，这些函数我在类体内进行了实现。
包括 数组容量 、数组大小 的查询，还有 数组的打印 等操作。

3. 算法复杂度分析

3.1 增加操作

add 的最坏复杂度 O(n+n) 中第一个 n 是指元素移动操作，第二个 n 是指 resize 函数，以下同理。
增加可能会引发扩容操作，平均而言，每增加 n 个元素，会扩展一次，会发生 n 个元素的移动，所以平均下来是 O(1) 。

3.2 删除操作

同理，删除操作与增加操作类似。

3.3 修改操作

3.4 查找操作

总体情况：

由此可以看出，数组比较适用于已知索引情况下的数据存放，也就是说，适用于索引有意义的情况。

4. 完整代码

程序完整代码（这里使用了头文件的形式来实现类）如下：