数据结构大致可分为：线性结构、半线性结构和非线性结构。线性结构中最基本的称为序列（sequence），根据其中数据项的逻辑次序与其物理存储地址的对应关系不同，又可分为向量（vector）和列表（list）。
1. 从数组到向量
数组：集合 S 由 n 个元素组成，且各元素之间具有一个线性次序，则可以将它们存放于起始地址 A，物理位置连续的一段存储空间。记为：
A[0,n) = { A[0], A[1], ..., A[n-1] }
将它们存放于起始地址 A，若每个元素占用 s 个单位的空间，则元素 A[i] 的物理地址为：A + i * s，所以被称作线性数组。
向量：V[0,n) = { v[0], v[1], ..., v[n-1] }是线性数组的一种抽象和泛化，由具有线性次序的一组元素构成的集合，其中的元素由秩区分。各元素秩互异，且均为 [0, n) 内的整数。采用“寻秩访问”。经过抽象，不限定同一向量中元素都属于同一数据类型，故而不保证它们之间可以相互比较大小。
2. 接口
作为一种抽象数据类型，向量对象应支持如下操作接口：
| 操作接口 | 功能 | 适用对象 |
|---|---|---|
| size() | 元素总数 | 向量 |
| get(r) | 获取秩为 r 的元素 | 向量 |
| put(r, e) | 用 e 代替秩为 r 的元素 | 向量 |
| insert(r, e) | e 作为秩为 r 的元素插入，原后继元素依次后移 | 向量 |
| remove(r) | 删除秩为 r 的元素，返回该元素中原存放的对象 | 向量 |
| disordered() | 判断所有元素是否已按非降序排列 | 向量 |
| sort() | 非降序排序 | 向量 |
| find(e) | 查找等于 e 且秩最大的元素 | 向量 |
| search(e) | 查找目标元素 e，返回不大于 e 且秩最大的元素 | 有序向量 |
| deduplicate() | 剔除重复元素 | 向量 |
| uniquify() | 剔除重复元素 | 有序向量 |
| traverse() | 遍历向量并统一处理所有元素，处理方法由函数对象指定 | 向量 |
3. Vector 模板类
typedef int Rank; //秩
#define DEFAULT_CAPACITY 3 //默认的初始容量（实际应用中可设置为更大）
template <typename T> class Vector { //向量模板类
protected:
Rank _size; int _capacity; T* _elem; //规模、容量、数据区
void copyFrom(T const* A, Rank lo, Rank hi); //复制数组区间A[lo,hi)
void expand(); //空间不足时扩容
void shrink(); //装填因子过小时压缩
bool bubble(Rank lo, Rank hi); //扫描交换
void bubbleSort()Rank lo, Rank hi); //气泡排序算法
Rank max(Rank lo, Rank hi); //选取最大元素
void selectionSort(Rank lo, Rank hi); //选择排序算法
void merge(Rank lo, Rank mi, Rank hi); //归并算法
void mergeSort(Rank lo, Rank hi); //归并排序算法
Rank partition(Rank lo, Rank hi); //轴点构造算法
void quickSort(Rank lo, Rank hi); //快速排序算法
void heapSort(Rank lo, Rank hi); //堆排序
public:
//构造函数
//容量为 c，规模为 s，所有元素初始化为 v，s<=c
Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0)
{ _elem = new T[_capacity = c]; for(_size = 0; _size < s; _elem[_size++] = v); }
Vector(T const* A, Rank n) { copyFrom(A, 0, n); } //数组整体复制
Vector(T const* A, Rank lo, Rank hi) { copyFrom(A, lo, hi); } //区间
Vector(Vector<T> const& V) { copyFrom(V._elem, 0, V._size); } //向量整体复制
Vector(Vector<T> const& V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); } //区间
//析构函数
~Vector() { delete [] _elem; } //释放内部空间
//只读访问接口
Rank size() const { return _size; } //规模
bool empty() const { return !_size; } //判空
int disordered() const; //判断向量是否已排序
Rank find(T const& e) const { return find(e, 0, _size); } //无序向量整体查找
Rank find(T const& e, Rank lo, Rank hi) const; //无序向量区间查找
Rank search(T const& e) const //有序向量整体查找
{ return (0 >= _size) ? -1 : search(e, 0, _size); }
Rank search(T const& e, Rank lo, Rank hi) const //有序向量区间查找
//可写访问接口
T& operator[](Rank r) const; //重载下标运算符，可以类似于数组形式引用各元素
Vector<T> & operator=(Vector<T> const&); //重载赋值运算符，以便直接克隆向量
T remove(Rank r); //删除秩为 r 的元素
int remove(Rank lo, Rank hi); //删除秩在区间 [lo,hi) 之内的元素
Rank insert(Rank r, T const& e); //插入元素
Rank insert(T const& e) { return insert(_size, e); } //默认作为尾元素插入
void sort(Rank lo, Rank hi); //对 [lo,hi) 排序
void sort() { sort(0, _size); } //整体排序
void unsort(Rank lo, Rank hi); //对 [lo,hi) 置乱
void unsort() { unsort(0, _size); } //整体置乱
int deduplicate(); //无序去重
int uniquify(); //有序去重
//遍历
void traverse(void (*)(T&)); //遍历（使用函数指针，只读或局部性修改）
template <typename VST> void traverse(VST&); //遍历（使用函数对象，可全局性修改）
};//Vector
4. 构造与析构
约定：向量中秩为 r 的元素，对应于内部数组中的 _elem[r]，其物理地址为：_elem + r
4.1 默认构造函数
整个默认构造过程顺序进行，没有任何迭代，故忽略用于分配数组空间的时间，需要常数时间。
4.2 基于复制的构造函数
在模板的实现中，我们将基于数组或者向量的复制操作（局部或整体的）都转交给如下的copyFrom函数处理：
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++]; //
}
需要 O(_size) 时间。
需要强调的是，由于向量内部含有动态分配的空间，默认的“=”运算符不足以支持向量之间的直接赋值。故要重建“=”：
template <typename T> Vector<T>& Vector<T>::operator=(Vector<T> const& V) {
if( _elem ) delet [] _elem;
copyFrom(V._elem, 0, V.size());
return *this;
}
4.3 析构
若不计系统用于空间回收的时间，整个析构过程只需常数时间。
5. 动态空间管理
5.1 扩容
template <typename T> void Vector<T>::expand() {
if(_size < _capacity) return; //尚未满员，不必扩容
if(_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY; //不低于最小容量
T *oldElem = _elem; _elem = new T[_capacity << 1]; //容量加倍
for( int i = 0; i < _size; i++)
_elem[i] = oldElem[i]; //复制原向量内容（T为基本类型，或以重载赋值运算符
delete [] oldElem; //释放原空间
}
分摊运行时间为 O(1)
5.2 缩容
template <typename T> void Vector<T>::shrink() {
if(_capacity < DEFAULT_CAPACITY << 1) return; //不至收缩到DEFAULT_CAPACITY
if(_size << 2 > _capacity) return; //以25%为界
T *oldElem = _elem; _elem = new T[_capacity >> 1]; //容量减半
for( int i = 0; i < _size; i++)
_elem[i] = oldElem[i]; //复制原向量内容（T为基本类型，或以重载赋值运算符
delete [] oldElem; //释放原空间
}
就单次扩容或缩容操作而言，所需时间的确会高达 O(n)，因此在对单次操作的执行速度及其敏感的应用场合以上策略并不适用，其中缩容操作甚至可以完全不予考虑。
6. 常规向量
6.1 直接引用元素
与数组直接通过下标访问元素的形式相比，向量 ADT（abstract data type）所设置的get()和put()接口都显得不甚自然。
template <typename T> T& Vector<T>::operator[](Rank r) const
{ return _elem[r]; } //assert: 0 <= r < _size
6.2 置乱器
重载后[]返回的是对数组元素的引用，这就意味着它既可以取代get()操作（通常作为赋值表达式的右值），也可以取代set()操作（通常作为左值）。采用这种形式，可以很清晰地实现如下的向量置乱器：
template <typename T> void permute(Vector<T>& V) {
for(int i = V.size(); i > 0; i--)
swap(V[i-1], V[rand() % i]); //V[i-1] 与 V[0,i) 中某一随机元素交换
}
从理论上讲，上述算法可以枚举出同一向量所有可能的排列，而且能够保证生成各种排列的概率均等。
为便于对各种向量算法的测试与比较，不妨将上述算法封装到向量 ADT 中，并对外提供向量的置乱接口操作：
template <typename T> void Vector<T>::unsort(Rank lo, Rank hi) {
T* V = _elem + lo;
for(Rank i =hi -lo; i > 0; i--)
swap(V[i-1], V[rand() % i]);
}
上述两段代码的细微差异：上面的代码通过重载“[]”，利用秩间接访问向量元素，下面的代码通过下标直接访问内部数组的元素。
6.3 判等器和比较器
template <typename T> static bool lt(T* a, T* b) { return lt(*a, *b); } //less than
template <typename T> static bool lt(T& a, T& b) { return a < b; } //less than
template <typename T> static bool eq(T* a, T* b) { return eq(*a, *b); } //equal
template <typename T> static bool eq(T& a, T& b) { return a == b; } //equal
在一些复杂的数据结构中，内部元素本身的类型可能就是指向其他对象的指针，从而外部更多关注的，往往是其所指向对象的大小如直接比较指针，则结果毫无意义，故上面的代码分别出了了指针和引用的情况。
6.4 无序查找
6.4.1 判等器
Vector模板中的find接口的语义为“查找与数据对象 e 相等的元素”。这暗示向量元素可以通过相互“比对”判断是否相等。这类仅支持比对，但未必支持比较的向量，称为无序向量（unsorted vector）。
6.4.2 顺序查找
由于find函数查找相等的最大秩元素，故从后往前比对：
template <typename T> Rank Vector<T>::find(T const& e, Rank lo, Rank hi) const {
while( (lo < hi--) && (e != _elem[hi]) ); //assert: 0 <= lo < hi <= _size
return hi;
}
最坏情况：O(n)；最好情况：O(1)。为输入敏感（input sensitive）算法。
6.5 插入
//assert: 0 <= r <= size
template <typename T> Rank Vector<T>::insert(Rank r, T const& e) {
expan(); //如有必要，扩容
for(int i = _size; i > r; i--) _elem[i] = _elem[i-1];
_elem[r] = e; _size++; //插入并更新容量
return r;
}
注意从后往前搬移数据，以防覆盖。复杂度：若插入位置等概论分布，则平均运行时间为O(_size)=O(n)。
6.6 删除
应将单元素删除视为区间删除的特例，并基于后者来实现前者。
6.6.1 区间删除
//删除区间[lo, hi)
template <typename T> int Vector<T>::remove(Rank lo, Rank hi) {
if(lo === hi) return 0;
while(hi < _size) _elem[lo++] = _elem[hi++];
_size = lo;
shrink();
return hi - lo; //返回被删除元素个数
}
6.6.2 单元素删除
template <typename T> T Vector<T>::remove(Rank r) {
T e = _elem[r];
remove(r, r + 1);
return e;
}
被删除元素在向量中的位置越靠后（前）所需时间越短（长），最好为O(1)，最坏为O(n)。
6.7 唯一化
template <typename T> int Vector<T>::deduplicate() {
int oldSize = _size;
Rank i = 1;
while(i < _size)
(find(_elem[i], 0, i) < 0) ? i++ : remove(i);
return oldSize - _size;
}