[TOC]
寫在前面
本篇文章整理《數(shù)據(jù)結(jié)構(gòu)（C++語(yǔ)言版）》關(guān)于向量這種線性結(jié)構(gòu)知識(shí)點(diǎn)。
整個(gè)數(shù)據(jù)結(jié)構(gòu)部分章節(jié)列表如下:
1 向量
-- 1.1 遍歷
-- 1.2 唯一化
-- 1.3 查找
2 列表
-- 2.1 列表節(jié)點(diǎn)
---- 2.1.1前插入算法
-- 2.2 列表模板類
---- 2.2.1 列表初始化
3 棧
-- 3.1 棧應(yīng)用
---- 3.1.1 括號(hào)匹配
---- 3.1.2 棿雀瘢混洗甄別
---- 3.1.3 中綴表達(dá)式
4 隊(duì)列
0 線性表
線性表是最基本浴捆、最簡(jiǎn)單稿械、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系美莫，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的餐茵。
線性表有兩種存儲(chǔ)方式述吸，一種是順序存儲(chǔ)結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)道批。即入撒，一種是物理地址與邏輯地址均連續(xù)，另一種是只有邏輯地址連續(xù)茅逮。
1 向量
向量結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)沃饶，即其物理地址與邏輯地址均連續(xù)（數(shù)組array是一種無(wú)序向量實(shí)例）损痰。
向量可以通過(guò)尋秩訪問(wèn)進(jìn)行快速定位向量中某一元素舷暮，與此同時(shí)堡称，由于其物理地址連續(xù)性墙贱，向量在刪減或添加某個(gè)元素時(shí)贱傀，需對(duì)被修改位置之后的所有元素依次向前（后）移動(dòng)，以保證其物理地址連續(xù)性府寒。
1.1 遍歷
對(duì)向量中所有元素實(shí)施某種統(tǒng)一操作椰棘。
具體有兩種采用方式，前一種是借助函數(shù)指針*visit()指定某一函數(shù)邪狞；后者 借助函數(shù)對(duì)象機(jī)制帆卓，通過(guò)將操作符"()"重載后，使其調(diào)用方式可以如同函數(shù)一樣剑令。
template<typename T>
void Vector<T>::traverse(void (*visit) (T&) ) { //借助函數(shù)指針
for(int i = 0; i < _size; i++){
//函數(shù)指針調(diào)用可以為visit(),也可使用(*visit)()，但前者更合適
visit( _elem[i]);
}
}
template<typename T> template<typename VST>
void Vector<T>::traverse(VST& visit ) { //借助函數(shù)對(duì)象
for(int i = 0; i < _size; i++){
//函數(shù)指針調(diào)用可以為visit(),也可使用(*visit)()棚蓄，但前者更合適
visit( _elem[i]);
}
}
實(shí)例
template <typename T> struct Increase{ //函數(shù)對(duì)象
virtual void operator() (T& e) {e++;}
}
template <typename T>
void Vector<T>::increase( Vector<T>& V) {
V.traverse( Increase<T>() );
}
1.2 唯一化
無(wú)序向量
算法：從第二個(gè)元素開始，在其前綴中查找相同元素稍算，若存在雷同者役拴，刪除當(dāng)前（最后一個(gè)相同元素）。這種算法下科平，每次最多只有一個(gè)相同元素需要去除姜性。
template <typename T>
int Vector<T>::deduplicate(){
int oldSize = _size; //記錄原始長(zhǎng)度
Rank i = 1;
while(i < _size){
(find(_elem[i], 0, i) ) < 0 ? //查找當(dāng)前元素前綴中是否有雷同
i++ : remove( i );
}
return oldSize - _size;
}
有序向量
算法：對(duì)于有序向量，相同元素彼此相鄰汞贸。設(shè)置入選元素_elem[i]與待入選元素_elem[j]印机，比較二者，相同則忽略射赛，不同則將j對(duì)應(yīng)元素賦值i的后繼，以此類推竣灌。
template <typename T>
int Vector<T>::uniquify() { //有序向量去重
Rank i = 0, j = 1;
while(j<_size){
(_elem[i] == _elem[j]) ? j++ : _elem[++i] = _elem[j];
}
++i = _size;
shrink(); //截除多余元素
return j - i;
}
1.3 查找
無(wú)序向量
算法：從后往前初嘹，找到該元素對(duì)應(yīng)秩最大者沮趣。
代碼：略。
有序向量
對(duì)有序向量而言房铭，通常采用減而治之的策略。即將所查找的區(qū)間分段翁狐，分別核實(shí)待查元素是落入左區(qū)間還是右區(qū)間亦或是中點(diǎn)位置凌蔬，再反復(fù)迭代闯冷。
為了優(yōu)化算法隐锭。一種方法是增加代價(jià)小的一方深度，即將區(qū)間點(diǎn)不再設(shè)置為中點(diǎn)，轉(zhuǎn)而設(shè)置Fibonacci節(jié)點(diǎn)躁倒，使得左區(qū)間包含元素更多（代價(jià)小）褐桌；另一種方法象迎，即將中轉(zhuǎn)點(diǎn)包含入右區(qū)間中，使得左右區(qū)間代價(jià)相等（都只需經(jīng)過(guò)一次判斷）啦撮。
算法：
待續(xù)....
