算法與資料結構--向量

首先先弄清定義：ADT(Abstract Data Type)與DS（Data Structure）

抽象資料類型：隻需要知道外部邏輯與操作，而不需要内部定義細節的資料類型++

資料結構：某種特定的語言來實作ADT的一整套算法 ，内部的實作

實際上，向量隻是數組的一種抽象與泛化，由一組元素按線性次序封裝而成

向量中的一些ADT操作：

insert(para1,para2),put(para1,para2),get(para1),remove(para1),size()

disorder(),find(),search(),uniquify(),sort()

vector模闆類

typedef int Rank  ;   // 秩

#define DEFAULT_CAPACITY  3 //預設初始容量（實際可能更大）

template <typename  T> class Vector {private:Rank _size;int _capacity; T* _elem;//規模，容量，資料區

   protected:/内部函數/

   public:/各種外部結構（構造，析構，讀寫，周遊）/

          }

關于可擴充向量：

采用靜态空間管理時，_capacity<_size 出現上溢，裝填因子_size/_capacity<<50%出現下溢，根本無法預測空間的需求量。

采用動态空間管理時，出現上溢時，使用allocated适當地擴大内部數組的容量，而後released釋放之前的記憶體空間,可用擴容算法實作

得益于向量的封裝，盡管擴容之後資料區的實體位址有所改變，卻不會出現野指針

幾種增容的政策：

遞增增容：每次都追加強定大小的容量，分攤成本o(n)，裝填因子 ->100%

加倍增容：容量加倍，分攤成本o(1)，裝填因子>50%，剛出現擴容的時候就是50%

--------------------------------------------------------------------------------------------------------------------------

平均分析與分攤分析的最大差別：平均分析是獨立的處理，割裂了操作之間的相關性與連貫性,而分攤複雜度是連續地

實施多次操作，然後将所需總體成本分攤至單次操作

--------------------------------------------------------------------------------------------------------------

向量(有序與無序向量的差別)的一些操作算法：

循序通路，插入，區間删除，單元素删除，查找（有序向量的二分查找或Fibonacci查找），唯一化，周遊

對于二分查找，選取的lambda=0.5，Fibonacci查找，lambda=0.618