專欄說明：

該專欄為學(xué)習(xí)筆記，內(nèi)容是c++實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法，代碼主要copy自大黑書《數(shù)據(jù)結(jié)構(gòu)與算法分析——c++語言描述》。閱讀需要c++基礎(chǔ)（包括模板類的使用）

原文發(fā)布于個人網(wǎng)站www.gislxz.com，歡迎各位交流。

線性表是最簡單的數(shù)據(jù)結(jié)構(gòu)（各種數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)概念我就不寫了，網(wǎng)上一搜一大把圖文并茂的，我只分享一下代碼實現(xiàn)），一般有數(shù)組實現(xiàn)和鏈?zhǔn)矫枋鰞煞N（正如所有數(shù)據(jù)結(jié)構(gòu)的底層都是數(shù)組或鏈表），數(shù)組實現(xiàn)可以用基礎(chǔ)數(shù)組，也可以用vector等結(jié)構(gòu)來實現(xiàn)。?

c++數(shù)組本身限制是很多的，必須提前設(shè)置好數(shù)據(jù)類型和長度。

這樣的靜態(tài)數(shù)組顯然功能局限，因而在實現(xiàn)數(shù)據(jù)結(jié)構(gòu)時往往使用動態(tài)數(shù)組。

接著我們需要實現(xiàn)一個更改數(shù)組長度的函數(shù)

changeLength1D這個函數(shù)首先是一個模板函數(shù)，需要注意第一個參數(shù)類型是T*&，即引用一個T指針。如果不加引用，那我們相當(dāng)于復(fù)制了外部調(diào)入的指針，可以正常修改該指針指向的對象，但沒法改變這個外部指針的指向（只是把函數(shù)內(nèi)這個指針指向了新數(shù)組，函數(shù)運行結(jié)束這個指針就釋放了）。

通過指針的指針也可以達(dá)到類似效果

有了變長函數(shù)我們就可以來實現(xiàn)線性表了

構(gòu)造函數(shù)和拷貝構(gòu)造函數(shù)的具體實現(xiàn)

構(gòu)造函數(shù)的賦值有一個細(xì)節(jié)，像上面這么寫就是先創(chuàng)建arraylength這個變量，等執(zhí)行到arrayLength = initialCapacity;這行代碼在進(jìn)行賦值，如果寫成arrayList<T>::arrayList(int initialCapacity):arrayLength(initialCapacity)那就是創(chuàng)建變量時直接賦值，這樣節(jié)省一點效率，另外如果arraylength是const修飾的話，那么只能這樣在初始化時就賦值。

查找和獲取指定位置的元素都很簡單，刪除和插入稍微復(fù)雜一些。刪除需要把刪除后的元素向左移，插入不僅要平移，還得提前判斷一下長度夠不夠了。