數(shù)據(jù)結(jié)構(gòu)的本質(zhì)就在于：如何將現(xiàn)實(shí)世界中各種各樣的數(shù)據(jù)放入到內(nèi)存中锨用，并且如何在內(nèi)存中操作這些數(shù)據(jù)，如何評(píng)價(jià)這些存儲(chǔ)方案和操作方法隘谣。

數(shù)據(jù)結(jié)構(gòu)難學(xué)嗎增拥？是難學(xué)。

為什么難學(xué)寻歧？一開始上來就講空間復(fù)雜度掌栅、時(shí)間復(fù)雜度，就講抽象數(shù)據(jù)码泛，當(dāng)然難學(xué)了猾封。

1、生活噪珊、生產(chǎn)等現(xiàn)實(shí)世界的數(shù)據(jù)有各種各樣的組成形式晌缘。例如一個(gè)課程的所有學(xué)生的成績（一組數(shù)據(jù)）逾苫，一個(gè)班全部學(xué)生的所有課程的成績（一張表）、一個(gè)單位的人員結(jié)構(gòu)（樹）等等枚钓。

2铅搓、這些數(shù)據(jù)都要先加載到內(nèi)存中，再送到CPU中進(jìn)行計(jì)算搀捷。

3星掰、內(nèi)存的最基本單位叫做存儲(chǔ)單元，一個(gè)字節(jié)（不討論理論中的嫩舟、個(gè)別情況的）氢烘。存儲(chǔ)單元相當(dāng)于一個(gè)空盒子，可以放置數(shù)據(jù)家厌。為了便于管理播玖，盒子會(huì)給一個(gè)編號(hào)，當(dāng)然存儲(chǔ)單元也會(huì)有編號(hào)饭于，其實(shí)就是地址蜀踏。理論上地址的方案可以有多種（計(jì)算機(jī)組成原理和操作系統(tǒng)的任務(wù)），不過對于程序員來說掰吕，這些都跟我們無關(guān)果覆，為了簡單起見，我們把存儲(chǔ)單元的編號(hào)（地址）都編成0殖熟、1局待、2、3菱属、4钳榨，......這樣的，于是這些編號(hào)或地址的取值范圍纽门，我們就稱地址空間薛耻。這個(gè)地址空間，跟一維坐標(biāo)軸一樣膜毁，所以是一維線性空間昭卓。

4、很明顯瘟滨，數(shù)據(jù)就是一個(gè)個(gè)放入到這些存儲(chǔ)單元中候醒，就象我們把一個(gè)單位的物品放入盒子一樣。現(xiàn)在杂瘸，假設(shè)一個(gè)盒子只能裝入一個(gè)單位的物品倒淫。因而，一個(gè)存儲(chǔ)單元也只能放入一個(gè)單位的數(shù)據(jù)败玉。

5敌土、接下來镜硕，假設(shè)說，我們有很多很多的空盒子（X個(gè)）返干。有一天兴枯，我們要將若干單位物品（N個(gè)）放入盒子中，那么我們可以在一個(gè)盒子放入一個(gè)單位物品矩欠。依此類推财剖，我們可以在一個(gè)存儲(chǔ)單元中放置一個(gè)單位的數(shù)據(jù)。

6癌淮、再接下來躺坟，我們有兩種放置方案：一個(gè)挨一個(gè)地連續(xù)地放置物品；當(dāng)然乳蓄，也可以不連續(xù)地放置物品咪橙。依此類推，在內(nèi)存當(dāng)中放置數(shù)據(jù)虚倒，也有兩種方案美侦，連續(xù)地放置數(shù)據(jù)，或者不連續(xù)地放置數(shù)據(jù)裹刮。為什么會(huì)有不連續(xù)的放置方案呢音榜？原因很簡單，一個(gè)主要的原因是捧弃，內(nèi)存的空間利用率高，碎片少（操作系統(tǒng)的存儲(chǔ)管理的知識(shí)擦囊，且不用理會(huì)）违霞，刪除舊有的數(shù)據(jù)很容易（這個(gè)是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容）。

7瞬场、現(xiàn)在买鸽，可以把這兩個(gè)將數(shù)據(jù)放入到存儲(chǔ)單元的方案叫做物理存儲(chǔ)。對連續(xù)物理存儲(chǔ)方案來說贯被，事情比較好辦眼五，通過編號(hào)（索引、下標(biāo)）就可以找到物品彤灶，對于不連續(xù)的方案看幼，那么我們就要在一個(gè)物品上面標(biāo)記下一個(gè)物品的位置，這個(gè)標(biāo)記就是下一個(gè)物品的地址（指針）幌陕。當(dāng)然诵姜，在計(jì)算機(jī)中，指針的記錄本身也要占用內(nèi)存的存儲(chǔ)單元搏熄，所以我們在c語言中用結(jié)構(gòu)體把數(shù)據(jù)和指針組織成為一個(gè)單位棚唆。通過這個(gè)指向關(guān)系暇赤，我們可以在不連續(xù)的放置方案中依次地查找我們所需要的東西（物品或數(shù)據(jù)）。

8宵凌、接下來鞋囊，就象我們經(jīng)常進(jìn)行從盒子當(dāng)中查詢物品、取用物品或增加物品等操作一樣瞎惫，我們也要進(jìn)行從內(nèi)存當(dāng)中查詢數(shù)據(jù)溜腐、取用（刪除）數(shù)據(jù)或增加數(shù)據(jù)等操作。那么微饥，對于不同的物理存儲(chǔ)方案來說逗扒，其方法是不一樣的。這個(gè)想一想欠橘，我們?nèi)绾螌Ω墩鎸?shí)的物品矩肩，我們就如何對付內(nèi)存中的數(shù)據(jù)。這就是數(shù)據(jù)的物理存儲(chǔ)方案的數(shù)據(jù)操作肃续。

9黍檩、好了，搞懂這些始锚，字符串之類的知識(shí)點(diǎn)就不難了刽酱。

10、記住一點(diǎn)瞧捌，只有兩種物理存儲(chǔ)結(jié)構(gòu)：連續(xù)的和不連續(xù)的棵里，因?yàn)閮?nèi)存的存儲(chǔ)單元的地址（編號(hào)）是0、1姐呐、2殿怜、3......（一維地址空間、或者線性地址空間）曙砂。

11头谜、是不是只有物理存儲(chǔ)結(jié)構(gòu)（方案）就可以了呢？在第1條中說過鸠澈，現(xiàn)實(shí)當(dāng)中的數(shù)據(jù)是有各種各樣的結(jié)構(gòu)的柱告。而在第10條，我們強(qiáng)調(diào)了物理放置方案只有2種：連續(xù)的和不連續(xù)的笑陈。

12际度、于是就產(chǎn)生一個(gè)問題，如何將現(xiàn)實(shí)世界當(dāng)中的關(guān)系各種各樣的數(shù)據(jù)放入到內(nèi)存之中新锈。

13甲脏、解決第12條中的問題，我們可以分兩步走，第1步是將現(xiàn)實(shí)世界的數(shù)據(jù)組織成為邏輯結(jié)構(gòu)块请，第2步再把邏輯結(jié)構(gòu)的數(shù)據(jù)映射到物理結(jié)構(gòu)中娜氏。

14、顯然墩新，在第1步中贸弥，我們拋去數(shù)據(jù)的其它屬性，只留下數(shù)據(jù)的兩個(gè)屬性就可以了：一個(gè)屬性是數(shù)據(jù)的值海渊，另一個(gè)屬性就是數(shù)據(jù)之間的關(guān)系绵疲。這兩個(gè)屬性就得到一個(gè)邏輯結(jié)構(gòu)：graph（圖），這就是離散數(shù)學(xué)中的圖論臣疑。那么盔憨，這就是科學(xué)家的事情，他們負(fù)責(zé)針對具體的問題讯沈，將現(xiàn)實(shí)世界的數(shù)據(jù)構(gòu)造出對應(yīng)的graph（圖）郁岩。

15、在第2步中缺狠，我們要做的事情问慎，把這個(gè)graph映射到物理存儲(chǔ)結(jié)構(gòu)中，這就是數(shù)據(jù)結(jié)構(gòu)要做的事情了挤茄。顯然如叼，我們可以用數(shù)組來存儲(chǔ)，也可以用鏈表來存儲(chǔ)穷劈，回憶一下最短路徑算法的兩個(gè)做法笼恰。ps.，二維數(shù)組歇终、三維數(shù)組也是一個(gè)連續(xù)存儲(chǔ)的結(jié)構(gòu)挖腰，在c語言debug下，看看地址就知道了练湿。那么，不連續(xù)的存儲(chǔ)結(jié)構(gòu)审轮，也就是鏈表肥哎，當(dāng)然有很多的衍生：雙向鏈表、十字鏈表疾渣、等等篡诽。

16、顯然榴捡，不管現(xiàn)實(shí)世界中的數(shù)據(jù)之間的關(guān)系如何杈女，我們都可以用graph來描述，只不過是，不同的數(shù)據(jù)關(guān)系有不同的結(jié)構(gòu)而已达椰，比如：樹翰蠢、森林、mesh啰劲，等等梁沧。

17、當(dāng)然蝇裤，我們要掌握一些常見的graph的操作方法廷支，最主要就是搜索方法。而且還要注意栓辜，這些方法是分兩個(gè)層次的恋拍，一個(gè)物理存儲(chǔ)結(jié)構(gòu)這個(gè)層次，一個(gè)是邏輯存儲(chǔ)結(jié)構(gòu)這個(gè)層次的藕甩。那么現(xiàn)在施敢，深度優(yōu)先搜索、廣度優(yōu)先搜索是哪個(gè)層次呢辛萍？

18悯姊、當(dāng)然，我們還要掌握一下存儲(chǔ)結(jié)構(gòu)的壓縮贩毕。

19悯许、到了這個(gè)時(shí)候，我們還要問一下辉阶，各種方案的優(yōu)劣性質(zhì)如何先壕，也就是空間復(fù)雜度和時(shí)間復(fù)雜度了。

20谆甜、當(dāng)然垃僚，我們這個(gè)時(shí)候，還要進(jìn)一步的問一問规辱，能不能將這些邏輯結(jié)構(gòu)給出一個(gè)統(tǒng)一的描述谆棺，那么，就是抽象數(shù)據(jù)了罕袋。

21改淑、當(dāng)然，我們還要掌握邏輯存儲(chǔ)結(jié)構(gòu)的各種樹的優(yōu)化浴讯，特別是針對不同的應(yīng)用朵夏，比如紅黑樹、B樹榆纽。

22仰猖、當(dāng)然捏肢，我們最后還要學(xué)習(xí)一下外存的存儲(chǔ)結(jié)構(gòu)。

23饥侵、當(dāng)然鸵赫，實(shí)驗(yàn)是少不了的。自己debug一下內(nèi)存單元的地址爆捞，并且在紙上手工的畫一下是最好了奉瘤。

24、最后煮甥，有了這些基礎(chǔ)盗温，剩下也就好辦了。

25成肘、不推薦教材卖局。尤其是國外的教材，先容許我默默地吐一下槽双霍，各種知識(shí)點(diǎn)零碎不堪砚偶，不成體系，不成系統(tǒng)洒闸。

編輯于 2015-09-14

作者保留權(quán)利