數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 1.1：動(dòng)態(tài)數(shù)組（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序?qū)崿F(xiàn)

• 2.1 增加操作

• 2.2 刪除操作

• 2.3 修改操作

• 2.4 查找操作

• 2.5 其他操作

• 3. 算法復(fù)雜度分析

• 3.1 增加操作

• 3.2 刪除操作

• 3.3 修改操作

• 3.4 查找操作

• 4. 完整代碼

1. 概念及基本框架

數(shù)組?是一種?線性結(jié)構(gòu)?，而且存儲(chǔ)上屬于?順序存儲(chǔ)（即內(nèi)存的物理空間是連續(xù)的），也就是線性表中的?順序表?。數(shù)組結(jié)構(gòu)如下圖所示：

下面以一個(gè)我實(shí)現(xiàn)的一個(gè)簡(jiǎn)單的數(shù)組類(lèi)來(lái)進(jìn)一步理解數(shù)組。

這里為了避免重復(fù)設(shè)計(jì)就可以兼容更多數(shù)據(jù)類(lèi)型，引入了?泛型?，即?模板?的概念。（模板的關(guān)鍵字是?class?或?typename）
這里的?數(shù)組容量?表示數(shù)組最多可存放空間的大小，而?數(shù)組大小?指的是數(shù)組實(shí)際占用空間的大小。為了保護(hù)數(shù)據(jù)，這兩個(gè)變量以及?數(shù)組數(shù)據(jù)?都設(shè)置為?private?。
構(gòu)造數(shù)組時(shí)，可以初始化數(shù)組的數(shù)組容量。（默認(rèn)是10）
那么就會(huì)出現(xiàn)一個(gè)問(wèn)題，如果這塊內(nèi)存被用完了怎么辦？因?yàn)閿?shù)組的物理空間必須連續(xù)，所以我們必須另外申請(qǐng)一塊更大的內(nèi)存，先把當(dāng)前數(shù)組復(fù)制到新的內(nèi)存上，然后釋放掉舊的內(nèi)存空間。同理，如果很多的內(nèi)存都沒(méi)有被利用，我們也可以適當(dāng)縮小數(shù)組容量。所以，我們需要一個(gè)這樣的?擴(kuò)容（縮容）函數(shù)?去動(dòng)態(tài)的實(shí)現(xiàn)數(shù)組。代碼如下：

實(shí)現(xiàn)了前面的程序之后，接下來(lái)就是一個(gè)數(shù)組的增、刪、改、查以及一些其他基本操作，接下來(lái)利用代碼去實(shí)現(xiàn)。

2. 基本操作程序?qū)崿F(xiàn)

2.1 增加操作

首先，在類(lèi)體內(nèi)進(jìn)行增加操作函數(shù)的原型說(shuō)明。這里包括三個(gè)函數(shù)：
add（添加到任意位置）
addFirst（添加到頭部）
addLast（添加到尾部）
然后分別去實(shí)現(xiàn)它們。

由于這些函數(shù)在類(lèi)體外，所以每個(gè)函數(shù)頭部必須添加一行代碼：

表示該函數(shù)使用模板，下面同理。

增加元素時(shí)可能會(huì)用到了擴(kuò)容函數(shù)，當(dāng)原空間已經(jīng)使用完的時(shí)候進(jìn)行擴(kuò)容操作。這里我每次將容量擴(kuò)展到原來(lái)的?2?倍，其實(shí)也可以擴(kuò)展到原來(lái)的?1.5?倍。

2.2 刪除操作

同理，在類(lèi)體內(nèi)進(jìn)行刪除函數(shù)的原型說(shuō)明。這里包括四個(gè)函數(shù)：
remove（刪除任意位置元素）：返回刪除元素的值。
removeFirst（刪除頭部元素）：返回刪除元素的值。
removeLast（刪除尾部元素）：返回刪除元素的值。
removeElement（刪除特定元素）：這里我利用下面的?find?函數(shù)來(lái)實(shí)現(xiàn)的，所以刪除的是第一個(gè)這樣的元素，如果想把這樣的元素都刪掉，可以寫(xiě)一個(gè)新的函數(shù)來(lái)實(shí)現(xiàn)。
然后分別去實(shí)現(xiàn)它們。

刪除時(shí)用到了縮容函數(shù)，當(dāng)原空間被利用太少的話，就使用一塊新的更小的空間。這里當(dāng)空間利用率不足?1/4?時(shí)，我將內(nèi)存縮至原空間的?1/2?，即還有一些空間可以去添加。
這里需要注意的是，不要使用當(dāng)空間利用率不足?1/2?時(shí)，就將內(nèi)存縮至原空間的?1/2?，這樣可能會(huì)導(dǎo)致震蕩。
例如當(dāng)空間恰好被利用完了以后，增加了一個(gè)元素，這時(shí)空間變?yōu)?2?倍，然后又刪除了一個(gè)元素，空間又降至原大小，然后又增加了一個(gè)元素，空間又變?yōu)?2?倍，再刪除一個(gè)元素，空間又降至原大小……循環(huán)往復(fù)，造成震蕩。
這里刪除操作的“刪除位置非法”后面返回的?NULL?也可以用?throw?拋異常來(lái)實(shí)現(xiàn)，這里只是為了方便。

2.3 修改操作

修改操作只有一個(gè)函數(shù)
set（修改指定位置的值）
同理，在類(lèi)體內(nèi)進(jìn)行刪除函數(shù)的原型說(shuō)明，然后在類(lèi)體外實(shí)現(xiàn)。

2.4 查找操作

查找函數(shù)有三個(gè)：
get（返回特定位置元素）
find（返回第一個(gè)特定元素位置）
contains（返回是否包含特定元素）
分別對(duì)它們進(jìn)行實(shí)現(xiàn)。

同理，這里?get?函數(shù)的“訪問(wèn)位置非法”后面返回的?NULL?也可以用?throw?拋異常來(lái)實(shí)現(xiàn)，這里只是為了方便。

2.5 其他操作

數(shù)組還有一些其他的操作，這些函數(shù)我在類(lèi)體內(nèi)進(jìn)行了實(shí)現(xiàn)。
包括?數(shù)組容量?、數(shù)組大小?的查詢，還有?數(shù)組的打印?等操作。

3. 算法復(fù)雜度分析

3.1 增加操作

add?的最壞復(fù)雜度?O(n+n)?中第一個(gè)?n?是指元素移動(dòng)操作，第二個(gè)?n?是指?resize?函數(shù)，以下同理。
增加可能會(huì)引發(fā)擴(kuò)容操作，平均而言，每增加?n?個(gè)元素，會(huì)擴(kuò)展一次，會(huì)發(fā)生?n?個(gè)元素的移動(dòng)，所以平均下來(lái)是?O(1)?。

3.2 刪除操作

同理，刪除操作與增加操作類(lèi)似。

3.3 修改操作

3.4 查找操作

總體情況：

由此可以看出，數(shù)組比較適用于已知索引情況下的數(shù)據(jù)存放，也就是說(shuō)，適用于索引有意義的情況。

4. 完整代碼

程序完整代碼（這里使用了頭文件的形式來(lái)實(shí)現(xiàn)類(lèi)）如下：