[資料結構 C++(3)]：向量

@[TOC](目錄)
           

1. 數組到向量

資料結構按照邏輯次序的複雜程度可以分為線性結構、半線性結構以及非線性結構。最為基本的線性結構統稱為序列(sequence)，序列又可以分為向量(vector)和清單(list)。

1.1. 數組

數組(array)是C++和Java裡的一種内置的資料類型，從0開始編号。若數組A[]存放空間的起始位址為A，且每個元素占用s個機關的空間，那麼A[i]對應的實體位址為 A + i × s A + i \times s A+i×s

1. 2. 向量

向量是線性數組的泛化和抽象，是具有線性次序的一組元素構成的集合，各元素的秩互異。

2. 接口

2.1. ADT 結構

3. 構造和析構

3.1. 基于複制的構造方法

1 template <typename T> //元素類型
2 void Vector<T>::copyFrom(T const* A, Rank lo, Rank hi) { //以數組匙間A[lo, hi)為藍本複刢向量
3 _elem = new T[_capacity = 2 * (hi - lo)]; _size = 0; //配置設定空間，觃模清零
4 while (lo < hi) //A[lo, hi)内癿元素逐一
5 _elem[_size++] = A[lo++]; //複刢至_elem[0, hi - lo)
6 }
           

由于向量内部含有動态配置設定的空間，預設的運算符"="不足以支援向量之間的直接指派。重載向量的指派運算符。

1 template <typename T> Vector<T>& Vector<T>::operator=(Vector<T> const& V ) { //重載指派操作符
2 if (_elem) delete [] _elem; //釋放原有内容
3 copyFrom(V._elem, 0, V.size()); //整體複刢
4 return *this; //迒回弼前對象癿引用，以便鍊式指派
5 }
           

4. 動态空間管理

4.1. 靜态空間管理

内部數組所占實體空間的容量，若在向量的生命期内不允許調整，則稱作靜态空間管理政策。

向量實際規模與其内部數組容量的比值（即_size/_capacity），亦稱作裝填因子（load

factor），它是衡量空間使用率的重要名額。

4.2 可擴充向量

當容量溢出時，另行申請一個容量更大的數組。

4.3 縮容

當裝填因子低于某一門檻值時，我們稱數組發生了下溢（underflow）。

1 template <typename T> void Vector<T>::shrink() { //裝填因子過小時壓縮向量所占空間
2 if (_capacity < DEFAULT_CAPACITY << 1) return; //丌緻收縮刡DEFAULT_CAPACITY以下
3 if (_size << 2 > _capacity) return; //以25%為界
4 T* oldElem = _elem; _elem = new T[_capacity >>= 1]; //容量減半
5 for (int i = 0; i < _size; i++) _elem[i] = oldElem[i]; //複刢原向量内容
6 delete [] oldElem; //釋放原空間
7 }
           

每次删除操作之後，一旦空間使用率已降至某一門檻值以下，該算法随即申請一個容量減半的新數組，将原數組中的元素逐一搬遷至其中，最後将原數組所占空間交還作業系統.

5. 正常向量、有序向量

唯一化

1 template <typename T> int Vector<T>::uniquify() { //有序向量重複元素剔除算法（高效版）
2 	Rank i = 0, j = 0; //各對互異“相鄰”元素癿秩
3 	while (++j < _size) //逐一掃描，直至末元素
4 		if (_elem[i] != _elem[j]) //跳過雷同者
5 			_elem[++i] = _elem[j]; //収現丌同元素時，向前秱至緊鄰亍前者右側
6 		_size = ++i; shrink(); //直接截除尾部夗餘元素
7 	return j - i; //向量觃模發化量，即被初除元素總數
8 }
           

二分查找

1 // 二分查找算法（版本A）：在有序向量癿匙間[lo, hi)内查找元素e，0 <= lo <= hi <= _size
2 template <typename T> static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
3 	while (lo < hi) { //殏步疊代可能要做兩次比較刞斷，有三個分支
4 		Rank mi = (lo + hi) >> 1; //以中點為軸點
5 		if (e < A[mi]) hi = mi; //深入前半殌[lo, mi)繼續查找
6 		else if (A[mi] < e) lo = mi + 1; //深入後半殌(mi, hi)繼續查找
7 		else return mi; //在mi處命中
8 	} //成功查找可以提前終止
9 	return -1; //查找失敗
10 } //有多個命中元素時，丌能保證迒回秩最大者；查找失敗時，簡單地迒回-1，而丌能訓示失敗癿位置