2.1向量vector

1、接口与实现

2、Abstract Data Type vs. Data Structure

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

定义与实现复杂度存储方式抽象数据类型抽象定义，一种定义外部的逻辑特性，不考虑时间复杂性操作&语义，不涉及数据存储方式数据结构具体实现，多种实现内部的表示与实现与复杂度密切相关完整算法，考虑数据的具体存储机制

3、从数组到向量

在c/c++语言中数组中每个元素都有编号一一对应，反之，每个元素均有非负编号唯一指代，并可直接访问 A[i]的物理地址=A+i×s，s为单个元素占用的空间量。（linear array） 向量是数组的抽象与泛化，由一组元素按照线性次序封装而成，各元素与[0，n)内的秩（rank）一一对应，元素类型不限于基本类型，操作、管理维护更加简化、同意与安全。 可更为便捷地参与复杂数据结构的定制与实现。

向量ADT接口(图片来自与课程截图)： Vector模板类

typedef int Rank;//秩 #define DEFAULT_CAPACITY 3//默认初始容量 template <typename T> class Vector{//向量模板类 private: Rank_size;//规模 int _capacity;//容量 T* _ELEM;//数据区 protected: /*内部函数*/ public: /*构造、析构函数，只读、可写、遍历接口*/ }

构造与析构

Vector (int c=DEFAULT_CAPACITY) {_elem=new T[_capacity=c];size=0;}//长度为c，首地址为_elem Vector(T const *A,Rank lo,Rank hi)//数组区间复制 {copyFrom(A,lo,hi);}

向量区间复制和向量整体复制用Vector const& V，依旧采用copyFrom函数

4、可扩充向量

静态空间管理： 开辟内部数组_elem[]并使用一段地址连续的物理空间： _capacity:总容量 _size：当前的实际规模n 若采用静态空间，总容量固定，会出现上溢或者下溢（元素寥寥无几） 更糟糕的是，一般的应用环境中难以预测空间的需求量。 动态空间管理 由上述缺点，可采用动态空间管理，当即将发生上溢时，适当扩大内部数组容量。 扩容算法实现：

template <typename T> void Vector<T>::expand(){//向量空间不足时扩容 if(_size<_capacity)return;//尚未满员时，不必扩容 _capacity=max(_capacity,DEFAULT_CAPACITY)//不低于最小容量 T* oldElem=_elem; _elem=new T[_capacity<<=1]//容量加倍 for(int i=0;i<_size;i++){//复制原向量内容 _elem[i]=oldElem[i]; } delete [] oldElem;//释放原空间 }

上述算法为容量加倍，是否可采取容量递增策略呢？每次递增n。这种按理说可行，但效率极低，不建议采用，其总体耗时o（n²）倍增则为o（n）。

5、平均分析 vs. 分摊分析

平均复杂度或期望复杂度，根据数据结构各种操作出现概率分布，将对应成本加权平均。 但各种操作孤立考察，割裂了操作的相关性和连贯性，往往不准确。 分摊复杂度，对数结构连续的实施足够多次的操作，所需总体成本分摊到单次操作，更实际可行，更重视的刻画了可能出现的操作序列。