邓俊辉<<数据结构>>-公开课-02-A

接口与实现

如何根据同一接口规范，定制ADT和实现implementation一个数据结构?
如何通过更有效的算法，使得对外接口更高效的工作?

• search

• sort

  Abstract Data Type vs. Data Structure

  抽象数据类型 = 数据模型 + 定义在该模型上的一组操作
  数据结构 = 基于某种特定语言，实现ADT的一套算法

向量ADT

数组到向量

数组是连续的内存空间，均匀划分成若干个单元，而每一个单元都与[0, n)的编号一一对应

A[i] = A + i * s, s为单个元素所占空间量, 故亦称作线性数组(linear array)

向量是数组的抽象和泛化， 由一组元素按照线性次序封装而成
与[0, n)内的秩(rank)一一对应 // 循秩访问(call-by-rank)
元素类型不限于基本类型
操作，管理维护更加简化安全。
可更为简便的参与更复杂的数据结构的定制。

操作实例

Vector模板类

typedef int Rank;             // 秩
#define DEAFAULT_CAPACITY 3   // 默认初始容量

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

应用和实现相互分离;
实现对内部数据项的封装。

构造和析构

template <typename T> class Vector {   // 向量模板类
 private:
  Rank _size; int _capacity; T* _elem;   // 规模, 容量, 数据区
 protected:
  /* ... 内部函数*/
 public:
  // /* ... 构造函数
  void copyFrom(T* const A, Rank lo, Rank hi);
  Vector(int c = DEAFAULT_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, lo, hi);}
  Vector(Vector<T> const& V)                     // 向量整体复制
  {copyFrom(V._elem, 0, V._size);}
  //  */
  // /* ... 析构函数
  ~Vector() {delete [] _elem;}                   // 释放内部空间
  // */
  /* ... 只读函数*/
  /* ... 可写函数*/
  /* ... 遍历函数*/
};

template <typename 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++];
}