不可一日無(wú)煙卷

數(shù)組
    數(shù)組不用多解釋了，都了解，這里再重復(fù)一些重要的。

    隨機(jī)這個(gè)詞經(jīng)常出現(xiàn)，在剛學(xué)的時(shí)候，都說(shuō)數(shù)組在內(nèi)存中是隨機(jī)訪問(wèn)的，然而隨機(jī)數(shù)又是隨機(jī)（不確定）的，這兩個(gè)概念總是搞不清楚。這里的隨機(jī)訪問(wèn)與隨機(jī)存儲(chǔ)器的概念一樣，google了也百度了，就是搞不到這個(gè)隨機(jī)是什么意思，就只能按random本意來(lái)理解了，只好意會(huì)。

    大家都知道數(shù)組在內(nèi)存中存放的方式，是順序的，也就是在訪問(wèn)某個(gè)元素的時(shí)候，比如訪問(wèn)第五個(gè)元素[5]，只需要在開(kāi)頭地址加上偏移量，即5，就是第五個(gè)元素了。因?yàn)閿?shù)組中存儲(chǔ)的數(shù)據(jù)類(lèi)型都是同一種的類(lèi)型，它們?cè)趦?nèi)存中的大小都是固定的，所以偏移量很好算。

    多維數(shù)組，很多人和我一樣，到這里都會(huì)迷茫一下，二維數(shù)組不難想象，就像一張表，如果三維的話(huà)，就想象成一個(gè)魔方，是立方體，如果三維以上，就難了，不能根據(jù)這種思維定式去想象它的結(jié)構(gòu)，了解它在內(nèi)存中的方式就行了。

    看幾個(gè)例子：
    

int[4] 內(nèi)存 地址 intArray[0] bffff4f0 bffff4f1 bffff4f2 bffff4f3 intArray[1] bffff4f4 bffff4f5 bffff4f6 bffff4f7 intArray[2] bffff4f8 bffff4f9 bffff4fa bffff4fb intArray[3] bffff4fc bffff4fd bffff4fe bffff4ff

int[2][2] 內(nèi)存 地址 intArray[0][0] bffff4f0 bffff4f1 bffff4f2 bffff4f3 intArray[0][1] bffff4f4 bffff4f5 bffff4f6 bffff4f7 intArray[1][0] bffff4f8 bffff4f9 bffff4fa bffff4fb intArray[1][1] bffff4fc bffff4fd bffff4fe bffff4ff

    上面是兩個(gè)一維整數(shù)數(shù)組和二維整數(shù)數(shù)組。從圖中可以看出每次讀取某個(gè)元素時(shí)只要加上某個(gè)偏移量就行了，偏移量就是就是這個(gè)元素類(lèi)型所占的內(nèi)存空間大小，上面是整形數(shù)組，一個(gè)整形占4個(gè)字節(jié)。

    可以看到，無(wú)論是多少維（稚）的數(shù)組，在內(nèi)存中都是線性的連續(xù)存儲(chǔ)，它是按行優(yōu)先順序放在內(nèi)存中的，即，如果有從n00開(kāi)始，其次是n01...然后是n10,n11.........以此類(lèi)推，三維的數(shù)組就是n000,n001.......n010,n011一直到n100.......。有些例外情況，比如fortran語(yǔ)言中，它是按列優(yōu)先順序存放的，順序是n10,n20,n30.....n11,n21......n12,n22 這樣的，以此類(lèi)推，不管多少維，都是這樣算的。

    數(shù)組的優(yōu)點(diǎn)就是訪問(wèn)速度快，缺點(diǎn)是在聲明時(shí)就已經(jīng)確定數(shù)組的大小，不能再擴(kuò)充了。

向量（vector容器）
    vector大家都經(jīng)常使用，其實(shí)向量是一個(gè)動(dòng)態(tài)數(shù)組，所謂動(dòng)態(tài)就是數(shù)組在聲明后還可以增長(zhǎng)，也可以插入元素，動(dòng)態(tài)數(shù)組在增長(zhǎng)的時(shí)候，其實(shí)也就是先分配好內(nèi)存，然后new 一個(gè)數(shù)組，一個(gè)個(gè)將原數(shù)組再拷貝進(jìn)去。向量使用完后再delete分配的內(nèi)存。

    向量的優(yōu)點(diǎn)和數(shù)組一樣，缺點(diǎn)就是增長(zhǎng)過(guò)快的時(shí)候比較耗資源。

表（list)
    一個(gè)簡(jiǎn)單的單向鏈表：

A

→

B

→

C

→

D

→

E

→

F

    鏈表的每個(gè)元素稱(chēng)為節(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都有兩個(gè)單元，第一個(gè)就是數(shù)據(jù)項(xiàng)，存放數(shù)據(jù)，第二個(gè)稱(chēng)為鏈（或next鏈），它指向第二個(gè)元素的地址，以此類(lèi)推，最后的一個(gè)元素指向NULL。
    
    這種單項(xiàng)列表，如果給表頭或表尾添加元素的時(shí)候會(huì)有些不便，最好的辦法就是加上表頭和表尾了。

    一個(gè)帶表頭和表尾的單向鏈表：

head

→

A

→

B

→

C

→

D

→

E

→

F

→

end

    表頭的數(shù)據(jù)元素是這個(gè)表的名字，例如上面那個(gè)表名是head，表頭的鏈指向第一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)則指向尾節(jié)點(diǎn)。

    給表添加一個(gè)元素的時(shí)，以上邊的head表為例，在A和B中間插入一個(gè)節(jié)點(diǎn)Y，則首先把A節(jié)點(diǎn)的鏈指向Y，然后將Y的鏈指向B。如果是刪除一個(gè)結(jié)點(diǎn)的話(huà)，假設(shè)刪除D節(jié)點(diǎn)，則只要將C節(jié)點(diǎn)鏈指向D節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即E節(jié)點(diǎn)。是不是很簡(jiǎn)單，但問(wèn)題又來(lái)了，每次插入或刪除一個(gè)結(jié)點(diǎn)的時(shí)候，尤其是刪除最后一個(gè)結(jié)點(diǎn)的時(shí)候，都得尋找它前面的節(jié)點(diǎn)，這就比較麻煩了，而雙向鏈表則解決了這種問(wèn)題。

    雙向鏈表：

n A

← →

B

← →

C

← →

D

← →

E

← →

F n

    可以看出，每個(gè)都在數(shù)據(jù)區(qū)前面都多了一個(gè)指向它前面節(jié)點(diǎn)的指針。我們把一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)叫做直接后驅(qū)，它前面的一個(gè)結(jié)點(diǎn)叫做直接前驅(qū)。第一個(gè)節(jié)點(diǎn)沒(méi)有直接前驅(qū)，所以為NULL，末尾節(jié)點(diǎn)沒(méi)有直接后驅(qū)，也為NULL，這樣在插入或刪除一個(gè)節(jié)點(diǎn)的時(shí)候的就可以直接找到它的前后兩個(gè)節(jié)點(diǎn)了。

    有時(shí)候?yàn)榱朔奖悴樵?xún)，會(huì)讓最后一個(gè)節(jié)點(diǎn)的后驅(qū)的next鏈指向第一個(gè)節(jié)點(diǎn)，這樣的鏈表就叫做循環(huán)鏈表。

    當(dāng)然，表不止有鏈表，還有別的，以后會(huì)學(xué)習(xí)到的。

    鏈表的優(yōu)點(diǎn)就是可以不受內(nèi)存單元的線性限制（比如數(shù)組），可以充分利用空間，缺點(diǎn)就是鏈表的存儲(chǔ)密度不如數(shù)組或向量的高，密度當(dāng)然是質(zhì)量除以體積了，這里質(zhì)量就是實(shí)際數(shù)據(jù)的大小，體積就是鏈表的大小，因?yàn)槊總€(gè)節(jié)點(diǎn)要額外存儲(chǔ)鏈，所以鏈表的存儲(chǔ)密度就相對(duì)小了 ，另外在鏈表很長(zhǎng)時(shí)，操作一個(gè)節(jié)點(diǎn)就比較麻煩了，因?yàn)樗趦?nèi)存中不是連續(xù)的，所以得從頭開(kāi)始一個(gè)個(gè)找，效率就低了。


    大致算是解了數(shù)組、向量和鏈表，可以根據(jù)它們的特點(diǎn)再不同場(chǎng)合使用。

ps:如有錯(cuò)誤，還請(qǐng)不吝指正，謝謝~！