[TOC]

寫在前面

本篇文章整理《數(shù)據(jù)結構（C++語言版）》關于向量這種線性結構知識點。
整個數(shù)據(jù)結構部分章節(jié)列表如下:
1 向量
-- 1.1 遍歷
-- 1.2 唯一化
-- 1.3 查找
2 列表
-- 2.1 列表節(jié)點
---- 2.1.1前插入算法
-- 2.2 列表模板類
---- 2.2.1 列表初始化
3 棧
-- 3.1 棧應用
---- 3.1.1 括號匹配
---- 3.1.2 ?；煜凑鐒e
---- 3.1.3 中綴表達式
4 隊列

0 線性表

線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結構。線性表中數(shù)據(jù)元素之間的關系是一對一的關系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。
線性表有兩種存儲方式，一種是順序存儲結構，另一種是鏈式存儲結構。即，一種是物理地址與邏輯地址均連續(xù)，另一種是只有邏輯地址連續(xù)。

線性表兩種形式

1 向量

向量結構是一種順序存儲結構，即其物理地址與邏輯地址均連續(xù)（數(shù)組array是一種無序向量實例）。
向量可以通過尋秩訪問進行快速定位向量中某一元素，與此同時，由于其物理地址連續(xù)性，向量在刪減或添加某個元素時，需對被修改位置之后的所有元素依次向前（后）移動，以保證其物理地址連續(xù)性。

向量添加元素示例

1.1 遍歷

對向量中所有元素實施某種統(tǒng)一操作。
具體有兩種采用方式，前一種是借助函數(shù)指針*visit()指定某一函數(shù)；后者 借助函數(shù)對象機制，通過將操作符"()"重載后，使其調(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ù)對象
    for(int i = 0; i < _size; i++){
    //函數(shù)指針調(diào)用可以為visit(),也可使用(*visit)()，但前者更合適
    visit( _elem[i]);  
    }
}

實例

template <typename T> struct Increase{  //函數(shù)對象
    virtual void operator() (T& e) {e++;}
}

template <typename T> 
void Vector<T>::increase( Vector<T>& V) {
    V.traverse( Increase<T>() );
}

1.2 唯一化

無序向量
算法：從第二個元素開始，在其前綴中查找相同元素，若存在雷同者，刪除當前（最后一個相同元素）。這種算法下，每次最多只有一個相同元素需要去除。

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;
}

有序向量
算法：對于有序向量，相同元素彼此相鄰。設置入選元素_elem[i]與待入選元素_elem[j]，比較二者，相同則忽略，不同則將j對應元素賦值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 查找

無序向量
算法：從后往前，找到該元素對應秩最大者。
代碼：略。
有序向量
對有序向量而言，通常采用減而治之的策略。即將所查找的區(qū)間分段，分別核實待查元素是落入左區(qū)間還是右區(qū)間亦或是中點位置，再反復迭代。
為了優(yōu)化算法。一種方法是增加代價小的一方深度，即將區(qū)間點不再設置為中點，轉而設置Fibonacci節(jié)點，使得左區(qū)間包含元素更多（代價小）；另一種方法，即將中轉點包含入右區(qū)間中，使得左右區(qū)間代價相等（都只需經(jīng)過一次判斷）。

減而治之