大話數(shù)據(jù)結(jié)構(gòu)（ 溢彩加強(qiáng)版）

第1章  數(shù)據(jù)結(jié)構(gòu)緒論 1
1.1　開場白 2
如果你交給某人一個程序，你將折磨他一整天；如果你教某人如何編寫程序，你將折磨他一輩子。
1.2　你數(shù)據(jù)結(jié)構(gòu)怎么學(xué)的 3
他完成開發(fā)并測試通過后，得意地提交了代碼。項(xiàng)目經(jīng)理看完代碼后拍著桌子對他說：“你數(shù)據(jù)結(jié)構(gòu)是怎么學(xué)的？”
1.3　數(shù)據(jù)結(jié)構(gòu)起源 4
1.4　基本概念和術(shù)語 5
正所謂“巧婦難為無米之炊”，再強(qiáng)大的計(jì)算機(jī)，也要有“米”下鍋才可以干活，否則就是一堆破銅爛鐵。這個“米”就是數(shù)據(jù)。
1.4.1?數(shù)據(jù) 5
1.4.2?數(shù)據(jù)元素 6
1.4.3?數(shù)據(jù)項(xiàng) 7
1.4.4?數(shù)據(jù)對象 7
1.4.5?數(shù)據(jù)結(jié)構(gòu) 7
1.5　邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 8
1.5.1?邏輯結(jié)構(gòu) 8
1.5.2?物理結(jié)構(gòu) 9
1.6　數(shù)據(jù)類型 11
大家都需要房子住，但顯然沒錢考慮大房子是沒有意義的。于是商品房就出現(xiàn)了各種各樣的戶型，有幾百平米的別墅，也有僅兩平米的膠囊公寓……
1.6.1?數(shù)據(jù)類型定義 11
1.6.2?抽象數(shù)據(jù)類型 12
1.7　總結(jié)回顧 13
1.8　結(jié)尾語 14
終的結(jié)果一定是，你對著別人很牛地說“數(shù)據(jù)結(jié)構(gòu)——就那么回事。”
第2章　算法 15
2.1　開場白 16
2.2　數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系 16
計(jì)算機(jī)界的前輩們，是一幫很牛很牛的人，他們使得很多看似沒法解決或者很難解決的問題，處理得如此美妙和神奇。
2.3　兩種算法的比較 17
高斯在上小學(xué)的一天，老師要求每個學(xué)生都計(jì)算1 2 … 100的結(jié)果，誰先算出來誰先回家……
2.4　算法定義 18
現(xiàn)實(shí)世界中的算法千變?nèi)f化，沒有通用算法可以解決所有問題。甚至一個小問題，某個解決此類問題很優(yōu)秀的算法卻未必就適合它。
2.5　算法的特性 19
2.5.1?輸入輸出 19
2.5.2?有窮性 19
2.5.3?確定性 20
2.5.4?可行性 20
2.6　算法設(shè)計(jì)的要求 20
求100個人的高考成績平均分與求全省所有考生的成績平均分在占用時間和內(nèi)存存儲上有非常大的差異，我們自然追求高效率和低存儲的算法來解決問題。
2.6.1?正確性 21
2.6.2?可讀性 21
2.6.3?健壯性 21
2.6.4?時間效率高和存儲量低 22
2.7　算法效率的度量方法 22
隨著n值越來越大，它們在時間效率上的差異也就越來越大。好比有些人每天都在學(xué)習(xí)，而有些人，打打游戲、睡睡大覺，畢業(yè)后前者名企爭著要，后者求職處處無門。
2.7.1?事后統(tǒng)計(jì)方法 22
2.7.2?事前分析估算方法 23
2.8　函數(shù)的漸近增長 25
2.9　算法時間復(fù)雜度 27
理解大O階推導(dǎo)不算難，難的其實(shí)是對數(shù)列的一些相關(guān)運(yùn)算，這考查的更多是數(shù)學(xué)知識和能力。
2.9.1?算法時間復(fù)雜度定義 27
2.9.2?推導(dǎo)大O階方法 28
2.9.3?常數(shù)階 28
2.9.4?線性階 29
2.9.5?對數(shù)階 29
2.9.6?平方階 29
2.10　常見的時間復(fù)雜度 31
有些時候，告訴你某些東西不可以去嘗試，也是一種知識的傳遞?？偛荒芊且ケ欢旧咭б豢诓胖郎卟豢梢哉腥前?。
2.11　壞情況與平均情況 32
2.12　算法空間復(fù)雜度 33
事先建立一個有2050個元素的數(shù)組，然后把所有年份按下標(biāo)數(shù)字對應(yīng)，如果是閏年，此數(shù)組項(xiàng)的值就是1，如果不是就是0。這樣，所謂的判斷某一年是否是閏年就變成了查找這個數(shù)組的某一項(xiàng)的值是多少的問題。
2.13　總結(jié)回顧 34
2.14　結(jié)尾語 35
愚公移山固然可敬，但發(fā)明炸藥和推土機(jī)，可能更加實(shí)在和聰明。
第3章　線性表 37
3.1　開場白 38
門外家長都擠在大門口與門里的小孩子的井然有序，形成了鮮明對比。哎，有時大人的所作所為，其實(shí)還不如孩子。
3.2　線性表的定義 39
有時我們想知道某個小朋友（比如麥兜）是否是班級的同學(xué)，老師會告訴我說，沒有，麥兜是在春田花花幼兒園里。這種查找某個元素是否存在的操作很常用。
3.3　線性表的抽象數(shù)據(jù)類型 41
3.4　線性表的順序存儲結(jié)構(gòu) 43
他每次一吃完早飯就沖著去了圖書館，挑一個好地兒，把他書包里的書，一本一本地按座位放好，長長一排，九個座硬是被他占了。
3.4.1?順序存儲定義 43
3.4.2?順序存儲方式 43
3.4.3?數(shù)據(jù)長度與線性表長度的區(qū)別 44
3.4.4?地址計(jì)算方法 45
3.5　順序存儲結(jié)構(gòu)的插入與刪除 46
春運(yùn)時去買火車票，大家都排著隊(duì)好好的，這時來了一個美女：“可否讓我排在你前面？”這可不得了，后面的人像蠕蟲一樣，全部都得退后一步。
3.5.1?獲得元素操作 46
3.5.2?插入操作 46
3.5.3?刪除操作 47
3.5.4?線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn) 49
3.6　線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 49
反正也是要讓相鄰元素間留有足夠余地，那干脆所有元素都不要考慮相鄰位置了，哪有空位就到哪里。而只是讓每個元素知道它下一個元素的位置在哪里。
3.6.1?順序存儲結(jié)構(gòu)不足的解決辦法 49
3.6.2?線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義 50
3.6.3?頭指針與頭結(jié)點(diǎn)的異同 52
3.6.4?線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)代碼描述 52
3.7　單鏈表的讀取 53
3.8　單鏈表的插入與刪除 54
本來是爸爸左手牽著媽媽的手、右手牽著寶寶的手在馬路邊散步。突然迎面走來一美女，爸爸失神般地望著，此情景被媽媽逮個正著，于是扯開父子倆，拉起寶寶的左手就快步朝前走去。
3.8.1?單鏈表的插入 54
3.8.2?單鏈表的刪除 56
3.9　單鏈表的整表創(chuàng)建 58
3.10　單鏈表的整表刪除 60
3.11　單鏈表結(jié)構(gòu)與順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn) 61
3.12　靜態(tài)鏈表 62
對于一些語言，如Basic、Fortran等早期的編程高級語言，由于沒有指針，這鏈表結(jié)構(gòu)，按照前面我們的講法，它就沒法實(shí)現(xiàn)了。怎么辦呢？
3.12.1?靜態(tài)鏈表的插入操作 64
3.12.2?靜態(tài)鏈表的刪除操作 65
3.12.3?靜態(tài)鏈表的優(yōu)缺點(diǎn) 67
3.13　循環(huán)鏈表 67
這個輪回的思想很有意思。它強(qiáng)調(diào)了不管你今生是窮是富，如果持續(xù)行善積德，下輩子就會好過，反之就會遭到報應(yīng)。
3.14　雙向鏈表 70
就像每個人的人生一樣，欲收獲就得付出代價。雙向鏈表既然是比單鏈表多了如可以反向遍歷查找等的數(shù)據(jù)結(jié)構(gòu)，那么也就需要付出一些小的代價。
3.15　總結(jié)回顧 72
3.16　結(jié)尾語 73
如果你覺得上學(xué)讀書是受罪，假設(shè)你可以活到80歲，其實(shí)你多也就吃了20年苦。用人生四分之一的時間來換取其余時間的幸福生活，這點(diǎn)苦不算啥。
第4章　棧與隊(duì)列 75
4.1　開場白 76
想想看，在你準(zhǔn)備用槍的時候，突然這手槍明明有子彈卻打不出來，這不是要命嗎。
4.2　棧的定義 76
類似的很多軟件，比如Word、Photoshop等，都有撤銷（undo）的操作，也是用棧這種思想方式來實(shí)現(xiàn)的。
4.2.1?棧的定義 76
4.2.2?進(jìn)棧出棧變化形式 78
4.3　棧的抽象數(shù)據(jù)類型 78
4.4　棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn) 79
4.4.1?棧的順序存儲結(jié)構(gòu) 79
4.4.2?棧的順序存儲結(jié)構(gòu)——進(jìn)棧操作 80
4.4.3?棧的順序存儲結(jié)構(gòu)——出棧操作 81
4.5　兩棧共享空間 81
兩個大學(xué)室友畢業(yè)同時到北京工作，他們都希望租房時能找到獨(dú)自住的一室或一室一廳，可找來找去發(fā)現(xiàn)，價格實(shí)在是承受不起。
4.6　棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實(shí)現(xiàn) 83
4.6.1?棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 83
4.6.2?棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)——進(jìn)棧操作 84
4.6.3?棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)——出棧操作 85
4.7　棧的作用 85
4.8　棧的應(yīng)用——遞歸 86
當(dāng)你往鏡子前面一站，鏡子里面就有一個你的圖像。但你試過兩面鏡子一起照嗎？如果A、B兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個“化身”。
4.8.1?斐波那契數(shù)列的實(shí)現(xiàn) 86
4.8.2?遞歸的定義 88
4.9　棧的應(yīng)用——四則運(yùn)算表達(dá)式求值 89
4.9.1?后綴（逆波蘭）表示法的定義 89
4.9.2?后綴表達(dá)式的計(jì)算結(jié)果 90
4.9.3?中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式 92
4.10　隊(duì)列的定義 93
電腦有時會處于疑似死機(jī)的狀態(tài)。就當(dāng)你失去耐心，打算Reset時，突然它像酒醒了一樣，把你剛才單擊的所有操作全部都按順序執(zhí)行了一遍。
4.11　隊(duì)列的抽象數(shù)據(jù)類型 94
4.12　循環(huán)隊(duì)列 95
你上了公交車發(fā)現(xiàn)前排有兩個空座位，而后排所有座位都已經(jīng)坐滿，你會怎么做？立馬下車，并對自己說，后面沒座了，我等下一輛？沒這么笨的人，前面有座位，當(dāng)然也是可以坐的。
4.12.1?隊(duì)列順序存儲的不足 95
4.12.2?循環(huán)隊(duì)列的定義 96
4.13　隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實(shí)現(xiàn) 99
4.13.1?隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)——入隊(duì)
　　　   操作 100
4.13.2?隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)——出隊(duì)
　　　   操作 100
4.14　總結(jié)回顧 101
4.15　結(jié)尾語 102
人生，需要有隊(duì)列精神的體現(xiàn)。南極到北極，不過是南緯90°到北緯90°的隊(duì)列，如果你中途猶豫，臨時轉(zhuǎn)向，也許你就只能和企鵝相伴永遠(yuǎn)。可事實(shí)上，無論哪個方向，只要你堅(jiān)持到底，你都可以到達(dá)終點(diǎn)。
第5章　串 103
      
5.1　開場白 104
“枯眼望遙山隔水，往來曾見幾心知？壺空怕酌一杯酒，筆下難成和韻詩。途路阻人離別久，訊音無雁寄回遲。孤燈夜守長寥寂，夫憶妻兮父憶兒。”……可再仔細(xì)一讀發(fā)現(xiàn)，這首詩竟然可以倒過來讀。
5.2　串的定義 104
我所提到的over、end、lie其實(shí)就是lover、friend、believe這些單詞字符串的子串。
5.3　串的比較 105
5.4　串的抽象數(shù)據(jù)類型 107
5.5　串的存儲結(jié)構(gòu) 108
感情上發(fā)生了問題，為了向女友解釋一下，我準(zhǔn)備發(fā)一條短信，一共打了75個字。后8個字是“我恨你是不可能的”，點(diǎn)發(fā)送。后來得知對方收到的，只有70個字，短信結(jié)尾是“……我恨你”。
5.5.1?串的順序存儲結(jié)構(gòu) 108
5.5.2?串的鏈?zhǔn)酱鎯Y(jié)構(gòu) 109
5.6　樸素的模式匹配算法 110
主串為S=“00000000000000000000000000000000000000000000000001”，而要匹配的子串為T=“0000000001”，……在匹配時，每次都得將T中字符循環(huán)到后一位才發(fā)現(xiàn)，哦，原來它們是不匹配的。
5.7　KMP模式匹配算法 113
很多年前我們的科學(xué)家覺得像這種有多個0和1重復(fù)字符的字符串，卻需要挨個遍歷的算法，是非常糟糕的事情。
5.7.1?KMP模式匹配算法的原理 113
5.7.2?next數(shù)組值的推導(dǎo) 116
5.7.3?KMP模式匹配算法的實(shí)現(xiàn) 117
5.7.4?KMP模式匹配算法的改進(jìn) 119
5.7.5?nextval數(shù)組值的推導(dǎo) 120
5.8　總結(jié)回顧 122
5.9　結(jié)尾語 122
《璇璣圖》共八百四十字，縱橫各二十九字，縱、橫、斜、交互、正、反讀或退一字、迭一字讀均可成詩，詩有三、四、五、六、七言不等，目前有人統(tǒng)計(jì)可組成七千九百五十八首詩。聽清楚哦，是7958首。
第6章　樹 125
6.1　開場白 126
無論多高多大的樹，那也是從小到大，由根到葉，一點(diǎn)點(diǎn)成長起來的。俗話說“十年樹木，百年樹人”，可一棵大樹又何止是十年這樣容易。
6.2　樹的定義 126
樹的定義其實(shí)就是我們在講解棧時提到的遞歸的方法。也就是在樹的定義之中還用到了樹的概念，這是比較新的一種定義方法。
6.2.1?結(jié)點(diǎn)的分類 127
6.2.2?結(jié)點(diǎn)間的關(guān)系 128
6.2.3?樹的其他相關(guān)概念 129
6.3　樹的抽象數(shù)據(jù)類型 129
6.4　樹的存儲結(jié)構(gòu) 130
6.4.1?雙親表示法 130
6.4.2?孩子表示法 133
6.4.3?孩子兄弟表示法 136
6.5　二叉樹的定義 137
蘇東坡曾說：“人有悲歡離合，月有陰晴圓缺，此事古難全”。意思就是完美是理想，不完美才是人生。我們通常舉的例子也都是左高右低、參差不齊的二叉樹。那是否存在完美的二叉樹呢？
6.5.1?二叉樹的特點(diǎn) 139
6.5.2?特殊二叉樹 140
6.6　二叉樹的性質(zhì) 142
6.6.1?二叉樹的性質(zhì)1 142
6.6.2?二叉樹的性質(zhì)2 143
6.6.3?二叉樹的性質(zhì)3 143
6.6.4?二叉樹的性質(zhì)4 144
6.6.5?二叉樹的性質(zhì)5 144
6.7　二叉樹的存儲結(jié)構(gòu) 145
6.7.1?二叉樹的順序存儲結(jié)構(gòu) 145
6.7.2?二叉鏈表 146
6.8　遍歷二叉樹 147
你人生的道路上，高考填志愿要面臨哪個城市、哪所大學(xué)、具體專業(yè)等選擇，由于選擇方式的不同，遍歷的次序就完全不同。
6.8.1?二叉樹的遍歷原理 147
6.8.2?二叉樹的遍歷方法 148
6.8.3?前序遍歷算法 150
6.8.4?中序遍歷算法 153
6.8.5?后序遍歷算法 156
6.8.6?推導(dǎo)遍歷結(jié)果 156
6.9　二叉樹的建立 158
6.10　線索二叉樹 159
我們現(xiàn)在提倡節(jié)約型社會，一切都應(yīng)該節(jié)約為本。對待我們的程序當(dāng)然也不例外，能不浪費(fèi)的時間或空間，都應(yīng)該考慮節(jié)約。
6.10.1?線索二叉樹的原理 159
6.10.2?線索二叉樹結(jié)構(gòu)的實(shí)現(xiàn) 162
6.11　樹、森林與二叉樹的轉(zhuǎn)換 165
有個鄉(xiāng)鎮(zhèn)企業(yè)也買了同樣的生產(chǎn)線，老板發(fā)現(xiàn)這個問題后找了個小工來說：你必須搞定，不然炒你魷魚。小工很快想出了辦法：他在生產(chǎn)線旁邊放了臺風(fēng)扇猛吹，空皂盒自然會被吹走。
6.11.1?樹轉(zhuǎn)換為二叉樹 166
6.11.2?森林轉(zhuǎn)換為二叉樹 167
6.11.3?二叉樹轉(zhuǎn)換為樹 168
6.11.4?二叉樹轉(zhuǎn)換為森林 169
6.11.5?樹與森林的遍歷 170
6.12　哈夫曼樹及其應(yīng)用 171
壓縮而不出錯是如何做到的呢？簡單地說，就是把我們要壓縮的文本進(jìn)行重新編碼，以達(dá)到減少不必要的空間的技術(shù)。壓縮和解壓縮技術(shù)就是基于哈夫曼的研究之上發(fā)展而來，我們應(yīng)該記住他。
6.12.1?哈夫曼樹 171
6.12.2?哈夫曼樹的定義與原理 173
6.12.3?哈夫曼編碼 176
6.13　總結(jié)回顧 177
6.14　結(jié)尾語 178
人受傷時會流下淚水。樹受傷時，天將不會哭。希望我們的未來不要僅僅是鋼筋水泥建造的高樓，也要有那郁郁蔥蔥的森林和草地，我們?nèi)祟惒趴赡芘c自然和諧共處。
第7章　圖 181
7.1　開場白 182
如果你不善于規(guī)劃，很有可能就會出現(xiàn)如玩好新疆后到海南，然后再沖向黑龍江這樣的荒唐決策。
7.2　圖的定義 182
現(xiàn)實(shí)中，人與人之間的關(guān)系非常復(fù)雜，比如我認(rèn)識的朋友，可能他們之間也互相認(rèn)識，這就不是簡單的一對一、一對多的關(guān)系了，這就是我們今天要研究的主題——圖。
7.2.1?各種圖的定義 183
7.2.2?圖的頂點(diǎn)與邊間的關(guān)系 185
7.2.3?連通圖的相關(guān)術(shù)語 187
7.2.4?圖的定義與術(shù)語總結(jié) 189
7.3　圖的抽象數(shù)據(jù)類型 190
7.4　圖的存儲結(jié)構(gòu) 191
因?yàn)槊绹暮谝咕褪侵袊陌滋?，利用互?lián)網(wǎng)，他的員工白天上班就可以監(jiān)控到美國倉庫夜間的實(shí)際情況，如果發(fā)生了像火災(zāi)、偷盜這樣的突發(fā)事件，及時打電話給美國當(dāng)?shù)叵嚓P(guān)人員進(jìn)行處理。
7.4.1?鄰接矩陣 192
7.4.2?鄰接表 195
7.4.3?十字鏈表 198
7.4.4?鄰接多重表 199
7.4.5?邊集數(shù)組 201
7.5　圖的遍歷 202
我有一天早晨準(zhǔn)備出門，發(fā)現(xiàn)鑰匙不見了。一定是我兒子拿著玩，不知道丟到哪個犄角旮旯去了，你們說，我應(yīng)該如何找？
7.5.1?深度優(yōu)先遍歷 203
7.5.2?廣度優(yōu)先遍歷 205
7.6　小生成樹 208
如果你加班加點(diǎn)，沒日沒夜設(shè)計(jì)出的結(jié)果是方案一，我想你離被炒魷魚應(yīng)該是不遠(yuǎn)了（同學(xué)微笑）。因?yàn)檫@個方案比后兩個方案一半還多的成本會讓老板氣暈過去的。
7.6.1?普里姆（Prim）算法 209
7.6.2?克魯斯卡爾（Kruskal）算法 213
7.7　短路徑 218
有人為了省錢，需路程短，但換乘站間距離長等原因并不省時間；另一些人，他為趕時間，的需求是總時間要短；還有一類人，他們不想多走路，關(guān)鍵是換乘要少，這樣可以在車上好好休息一下。
7.7.1?迪杰斯特拉（Dijkstra）算法 220
7.7.2?弗洛伊德（Floyd）算法 225
7.8　拓?fù)渑判?229
電影制作不可能在人員到位進(jìn)駐場地時，導(dǎo)演還沒有找到，也不可能在拍攝過程中，場地都沒有。這都會導(dǎo)致荒謬的結(jié)果。
7.8.1?拓?fù)渑判蚪榻B 229
7.8.2?拓?fù)渑判蛩惴?230
7.9　關(guān)鍵路徑 234
假如造一個輪子要0.5天、造一個發(fā)動機(jī)要3天、造一個車底盤要2天、造一個外殼要2天，造其他零部件2天，全部零部件集中到一處要0.5天，組裝成車要2天，請問，在汽車廠造一輛車，短需要多少天呢？
7.9.1?關(guān)鍵路徑算法的原理 236
7.9.2?關(guān)鍵路徑算法 237
7.10　總結(jié)回顧 242
7.11　結(jié)尾語 243
世界上遙遠(yuǎn)的距離，不是牛A與牛C之間的狹小空隙，而是你們當(dāng)中，有人在通往牛×的路上一路狂奔，而有人步入大學(xué)校園就學(xué)會放棄。
第8章　查找 245
8.1　開場白 246
當(dāng)你精心寫了一篇博文或者上傳一組照片到互聯(lián)網(wǎng)上，來自世界各地的無數(shù)“蜘蛛”便會蜂擁而至。所謂蜘蛛就是搜索引擎公司服務(wù)器上的軟件，它把互聯(lián)網(wǎng)當(dāng)成了蜘蛛網(wǎng)，沒日沒夜地訪問上面的各種信息。
8.2　查找概論 247
比如網(wǎng)絡(luò)時代的新名詞，如 “蝸居”“蟻?zhàn)?rdquo;等，如果需要將它們收錄到漢語詞典中，顯然收錄時就需要查找它們是否存在，以及如果不存在時應(yīng)該收錄的位置。
8.3　順序表查找 249
8.3.1?順序表查找算法 249
8.3.2?順序表查找優(yōu)化 250
8.4　有序表查找 251
我在紙上已經(jīng)寫好了一個100以內(nèi)的正整數(shù)請你猜，問幾次可以猜出來。當(dāng)時已經(jīng)介紹了如何才可以快猜出這個數(shù)字。我們把這種每次取中間記錄查找的方法叫做折半查找。
8.4.1?折半查找 251
8.4.2?插值查找 253
8.4.3?斐波那契查找 255
8.5　線性索引查找 257
我母親年紀(jì)大了，經(jīng)常在家里找不到東西，于是她用一小本子，記錄了家里所有小東西放置的位置，比如戶口本放在右手床頭柜下面抽屜中，鈔票放在衣……咳，這個就不提了。
8.5.1?稠密索引 258
8.5.2?分塊索引 258
8.5.3?倒排索引 260
8.6　二叉排序樹 262
后來老虎來了，一人拼命地跑，另一人則急中生智，爬到了樹上。而老虎是不會爬樹的，結(jié)果……。爬樹者改變了跑的思想，這一改變何等重要，撿回了自己的一條命。
8.6.1?二叉排序樹的查找操作 264
8.6.2?二叉排序樹的插入操作 266
8.6.3?二叉排序樹的刪除操作 267
8.6.4?二叉排序樹總結(jié) 272
8.7　平衡二叉樹（AVL樹） 273
平板就是一個世界，當(dāng)誘惑降臨，人們心中的平衡被打破，世界就會混亂，后留下的只有孤獨(dú)寂寞失敗。這種單調(diào)的機(jī)械化的社會，禁不住誘惑的侵蝕，容易被侵蝕的，恰恰是空虛的心靈。
8.7.1?平衡二叉樹的實(shí)現(xiàn)原理 275
8.7.2?平衡二叉樹的實(shí)現(xiàn)算法 278
8.8　多路查找樹（B樹） 284
要觀察一個公司是否嚴(yán)謹(jǐn)，看他們?nèi)绾伍_會就知道了。如果開會時每一個人都只是帶一張嘴，即興發(fā)言，這肯定是一家不嚴(yán)謹(jǐn)?shù)墓尽?br />8.8.1?2-3樹 285
8.8.2?2-3-4樹 289
8.8.3?B樹 290
8.8.4?B 樹 292
8.9　散列表查找（哈希表）概述 294
你很想學(xué)太極拳，聽說學(xué)校有個叫張三豐的人打得特別好，于是到學(xué)校學(xué)生處找人，工作人員拿出學(xué)生名單，終告訴你，學(xué)校沒這個人，并說張三豐幾百年前就已經(jīng)在武當(dāng)山作古了。
8.9.1?散列表查找定義 294
8.9.2?散列表查找步驟 295
8.10　散列函數(shù)的構(gòu)造方法 296
8.10.1?直接定址法 297
8.10.2?數(shù)字分析法 297
8.10.3?平方取中法 298
8.10.4?折疊法 298
8.10.5?除留余數(shù)法 298
8.10.6?隨機(jī)數(shù)法 299
8.11　處理散列沖突的方法 300
我們每個人都希望身體健康，雖然疾病可以預(yù)防，但不可避免，沒有任何人可以說，生下來到現(xiàn)在沒有生過一次病。
8.11.1?開放定址法 300
8.11.2?再散列函數(shù)法 302
8.11.3?鏈地址法 302
8.11.4?公共溢出區(qū)法 302
8.12　散列表查找的實(shí)現(xiàn) 303
8.12.1?散列表查找的算法實(shí)現(xiàn) 303
8.12.2?散列表查找的性能分析 305
8.13　總結(jié)回顧 305
如果我是個喜歡汽車的人，時常搜汽車信息。那么當(dāng)我在搜索框中輸入“甲殼蟲”“美洲虎”等關(guān)鍵詞時，不要讓動物和人物成為搜索的頭條。
8.14　結(jié)尾語 306
第9章　排序 309
9.1　開場白 310
假如我想買一臺iPhone 4的手機(jī)，于是上了某電子商務(wù)網(wǎng)站去搜索?？伤阉骱蟀l(fā)現(xiàn)，有8863個相關(guān)的物品，如此之多，這叫我如何選擇。我其實(shí)是想買便宜一點(diǎn)的，但是又怕遇到騙子，想找信譽(yù)好的商家，如何做？
9.2　排序的基本概念與分類 310
比如我們某些大學(xué)為了選拔在主科上更優(yōu)秀的學(xué)生，要求對所有學(xué)生的所有科目總分倒序排名，并且在同樣總分的情況下將語數(shù)外總分做倒序排名。這就是對總分和語數(shù)外總分兩個次關(guān)鍵字的組合排序。
9.2.1?排序的穩(wěn)定性 311
9.2.2?內(nèi)排序與外排序 312
9.2.3?排序用到的結(jié)構(gòu)與函數(shù) 313
9.3　冒泡排序 314
無論你學(xué)習(xí)哪種編程語言，在學(xué)到循環(huán)和數(shù)組時，通常都會介紹一種排序算法，而這個算法一般就是冒泡排序。并不是它的名稱很好聽，而是說這個算法的思路簡單，容易理解。
9.3.1?簡單排序的實(shí)現(xiàn) 314
9.3.2?冒泡排序算法 315
9.3.3?冒泡排序優(yōu)化 316
9.3.4?冒泡排序復(fù)雜度分析 317
9.4　簡單選擇排序 318
還有一種做股票的人，他們很少出手，只是在不斷觀察和判斷，等時機(jī)一到，果斷買進(jìn)或賣出。他們因?yàn)槔潇o和沉著，以及交易的次數(shù)少，而終收益頗豐。
9.4.1?簡單選擇排序算法 318
9.4.2?簡單選擇排序復(fù)雜度分析 319
9.5　直接插入排序 320
哪怕你是次玩撲克牌，只要認(rèn)識這些數(shù)字，理牌的方法都是不用教的。將3和4移動到5的左側(cè)，再將2移動到左側(cè)，順序就算是理好了。這里，我們的理牌方法，就是直接插入排序法。
9.5.1?直接插入排序算法 320
9.5.2?直接插入排序復(fù)雜度分析 322
9.6　希爾排序 323
不管怎么說，希爾排序算法的發(fā)明，使得我們終于突破了慢速排序的時代（超越了時間復(fù)雜度為O(n2)），之后，更為高效的排序算法也就相繼出現(xiàn)了。
9.6.1?希爾排序原理 324
9.6.2?希爾排序算法 325
9.6.3?希爾排序復(fù)雜度分析 328
9.7　堆排序 329
什么叫堆結(jié)構(gòu)呢？回憶一下我們小時候，特別是男同學(xué)，基本都玩過疊羅漢的惡作劇。通常都是先把某個要整的人按倒在地，然后大家就一擁而上撲了上去……后果？后果當(dāng)然就是一笑了之。
9.7.1?堆排序算法 331
9.7.2?堆排序復(fù)雜度分析 337
9.8　歸并排序 337
即使你是你們班級、甚至年級名，如果你沒有上分?jǐn)?shù)線，則說明你的成績排不到全省前1萬名，你也就基本失去了當(dāng)年上本科的機(jī)會了。
9.8.1?歸并排序算法 338
9.8.2?歸并排序復(fù)雜度分析 343
9.8.3?非遞歸實(shí)現(xiàn)歸并排序 343
9.9　快速排序 346
終于我們的高手要登場了，將來你工作后，你的老板讓你寫個排序算法，而你會的算法中竟然沒有快速排序，我想你還是不要聲張，偷偷去把快速排序算法找來敲進(jìn)電腦，這樣至少你不至于被大伙兒取笑。
9.9.1?快速排序算法 346
9.9.2?快速排序復(fù)雜度分析 349
9.9.3?快速排序優(yōu)化 350
9.10　總結(jié)回顧 354
目前還沒有十全十美的排序算法，有優(yōu)點(diǎn)就會有缺點(diǎn)，即使是快速排序法，也只是在整體性能上優(yōu)越，它也存在排序不穩(wěn)定、需要大量輔助空間、對少量數(shù)據(jù)排序無優(yōu)勢等不足。
9.11　結(jié)尾語 357
如果你有夢想的話，就要去捍衛(wèi)它。當(dāng)別人做不到的時候，他們就想要告訴你，你也不能。如果你想要些什么，就得去努力爭取。就這樣！