Skip to main content

02A 抽象数据结构

抽象数据类型 = 数据模型 + 定义在该模型上的一组操作

数据结构 = 基于某种特定语言,实现ADT的一整套算法

Application = Interface x Implementation

如: 汽车司机 <----> 汽车手册 <---> 汽车零部件

循秩访问​

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

  • 各元素与[0, n)内的秩(rank)一一对应: using Rank = int; //call-by-rank
  • 操作、管理维护更加简化、统一与安全
  • 元素类型可灵活选取,便于定制复杂数据结构

向量ADT接口​

size(), get(r), put(r, e), insert(r, e), remove(r) ...

ADT操作实例​

略

STL Vector​

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

构造 + 析构:重载​

重载操作符 =

基于复制的构造​

分配空间，复制