C++ 数据结构 (二) 向量 (1) 接口与实现

ADT VS DS

• 抽象数据类型 (Abstract Data Type) ：数据模型 + 定义在该模型上的一组操作

  抽象定义	外部的逻辑特性	操作 & 语义
  一种定义	不考虑时间复杂度	不涉及数据的存储方式

• 数据结构 (Data Structure) ：基于某种特定语言, 实现 ADT 的一整套算法

  具体实现	内部的表示与实现	完整的算法
  多种实现	与复杂度密切相关	要考虑数据的具体存储机制

向量 ADT

从数组到向量

• 在 C/C++ 等高级语言中, 数组 A[] 中的元素与 [0, n) 内的编号一一对应

  

• 反之, 每个元素均由 (非负) 编号唯一指代, 并可直接访问

  A[i] 的物理地址 = A + i * s, s 为单个元素占用的空间量

  故亦称作线性数组 (linear array)

• 向量是数组的抽象与泛化, 由一组元素按线性次序封装而成

  1. 循秩访问 (call-by-rank): 各元素与 [0, n) 内的秩 (rank) 一一对应

  2. 元素的类型不限于基本类型

  3. 操作、管理维护更加简化、统一与安全

  4. 可更为便捷地参与复杂数据结构的定制与实现

向量接口

Vector 模板类

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef int Rank;          // 秩
#define DEFAULT_CAPACITY 3 // 默认初始容量 (实际应用中可设置为更大)

template <typename T> class Vector { // 向量模板类
  private: Rank _size; int _capacity; T *_elem; // 规模、容量、数据区
  protected:
      /* ... 内部函数 */
  public:
      /* ... 构造函数 */
      /* ... 析构函数 */
      /* ... 只读接口 */
      /* ... 可写接口 */
      /* ... 遍历接口 */
};

构造与析构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 构造器 ========================
// 默认
Vector(int c = DEFAULT_CAPACITY) {
  _elem = new T[_capacity = c];
  _size = 0;
}
// 数组区间复制
Vector(T const *A, Rank lo, Rank hi) {
  copyFrom(A, lo, hi);
}
// 向量区间复制
Vector(Vector<T> const &V, Rank lo, Rank hi) {
  copyFrom(V._elem, lo, hi);
}
// 向量整体复制
Vector(Vector<T> const &V) {
  copyFrom(V._elem, 0, V._size);
}
// 析构器 =========================
~Vector() {
  delete [] _elem; // 释放内部空间
}

基于复制的构造

1
2
3
4
5
6
7

template <typename T> // T 为基本类型, 或已重载赋值操作符 '='
void Vector<T>::copyFrom(T* const A, Rank lo, Rank hi) {
  _elem = new T[_capacity = 2 * (hi - lo)]; // 分配空间
  _size = 0; // 规模清零
  while (lo < hi)               // A[lo, hi) 内的元素逐一
      _elem[_size++] = A[lo++]; // 复制到 _elem[0, hi - lo)
}

本文由 Oscaner 创作, 采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名

• Previous
  PHP - LCS
• Next
  C++ 数据结构 (二) 向量 (2) 扩容向量