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

第1章  數(shù)據(jù)結(jié)構(gòu)緒論 1
1.1　開場白 2
如果你交給某人一個(gè)程序，你將折磨他一整天；如果你教某人如何編寫程序，你將折磨他一輩子。
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ī)，也要有“米”下鍋才可以干活，否則就是一堆破銅爛鐵。這個(gè)“米”就是數(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é)的一天，老師要求每個(gè)學(xué)生都計(jì)算1 2 … 100的結(jié)果，誰先算出來誰先回家……
2.4　算法定義 18
現(xiàn)實(shí)世界中的算法千變?nèi)f化，沒有通用算法可以解決所有問題。甚至一個(gè)小問題，某個(gè)解決此類問題很優(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個(gè)人的高考成績平均分與求全省所有考生的成績平均分在占用時(shí)間和內(nèi)存存儲上有非常大的差異，我們自然追求高效率和低存儲的算法來解決問題。
2.6.1?正確性 21
2.6.2?可讀性 21
2.6.3?健壯性 21
2.6.4?時(shí)間效率高和存儲量低 22
2.7　算法效率的度量方法 22
隨著n值越來越大，它們在時(shí)間效率上的差異也就越來越大。好比有些人每天都在學(xué)習(xí)，而有些人，打打游戲、睡睡大覺，畢業(yè)后前者名企爭著要，后者求職處處無門。
2.7.1?事后統(tǒng)計(jì)方法 22
2.7.2?事前分析估算方法 23
2.8　函數(shù)的漸近增長 25
2.9　算法時(shí)間復(fù)雜度 27
理解大O階推導(dǎo)不算難，難的其實(shí)是對數(shù)列的一些相關(guān)運(yùn)算，這考查的更多是數(shù)學(xué)知識和能力。
2.9.1?算法時(shí)間復(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　常見的時(shí)間復(fù)雜度 31
有些時(shí)候，告訴你某些東西不可以去嘗試，也是一種知識的傳遞?？偛荒芊且ケ欢旧咭б豢诓胖郎卟豢梢哉腥前?。
2.11　壞情況與平均情況 32
2.12　算法空間復(fù)雜度 33
事先建立一個(gè)有2050個(gè)元素的數(shù)組，然后把所有年份按下標(biāo)數(shù)字對應(yīng)，如果是閏年，此數(shù)組項(xiàng)的值就是1，如果不是就是0。這樣，所謂的判斷某一年是否是閏年就變成了查找這個(gè)數(shù)組的某一項(xiàng)的值是多少的問題。
2.13　總結(jié)回顧 34
2.14　結(jié)尾語 35
愚公移山固然可敬，但發(fā)明炸藥和推土機(jī)，可能更加實(shí)在和聰明。
第3章　線性表 37
3.1　開場白 38
門外家長都擠在大門口與門里的小孩子的井然有序，形成了鮮明對比。哎，有時(shí)大人的所作所為，其實(shí)還不如孩子。
3.2　線性表的定義 39
有時(shí)我們想知道某個(gè)小朋友（比如麥兜）是否是班級的同學(xué)，老師會告訴我說，沒有，麥兜是在春田花花幼兒園里。這種查找某個(gè)元素是否存在的操作很常用。
3.3　線性表的抽象數(shù)據(jù)類型 41
3.4　線性表的順序存儲結(jié)構(gòu) 43
他每次一吃完早飯就沖著去了圖書館，挑一個(gè)好地兒，把他書包里的書，一本一本地按座位放好，長長一排，九個(gè)座硬是被他占了。
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)時(shí)去買火車票，大家都排著隊(duì)好好的，這時(shí)來了一個(gè)美女：“可否讓我排在你前面？”這可不得了，后面的人像蠕蟲一樣，全部都得退后一步。
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
反正也是要讓相鄰元素間留有足夠余地，那干脆所有元素都不要考慮相鄰位置了，哪有空位就到哪里。而只是讓每個(gè)元素知道它下一個(gè)元素的位置在哪里。
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
本來是爸爸左手牽著媽媽的手、右手牽著寶寶的手在馬路邊散步。突然迎面走來一美女，爸爸失神般地望著，此情景被媽媽逮個(gè)正著，于是扯開父子倆，拉起寶寶的左手就快步朝前走去。
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
這個(gè)輪回的思想很有意思。它強(qiáng)調(diào)了不管你今生是窮是富，如果持續(xù)行善積德，下輩子就會好過，反之就會遭到報(bào)應(yīng)。
3.14　雙向鏈表 70
就像每個(gè)人的人生一樣，欲收獲就得付出代價(jià)。雙向鏈表既然是比單鏈表多了如可以反向遍歷查找等的數(shù)據(jù)結(jié)構(gòu)，那么也就需要付出一些小的代價(jià)。
3.15　總結(jié)回顧 72
3.16　結(jié)尾語 73
如果你覺得上學(xué)讀書是受罪，假設(shè)你可以活到80歲，其實(shí)你多也就吃了20年苦。用人生四分之一的時(shí)間來換取其余時(shí)間的幸福生活，這點(diǎn)苦不算啥。
第4章　棧與隊(duì)列 75
4.1　開場白 76
想想看，在你準(zhǔn)備用槍的時(shí)候，突然這手槍明明有子彈卻打不出來，這不是要命嗎。
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
兩個(gè)大學(xué)室友畢業(yè)同時(shí)到北京工作，他們都希望租房時(shí)能找到獨(dú)自住的一室或一室一廳，可找來找去發(fā)現(xiàn)，價(jià)格實(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)你往鏡子前面一站，鏡子里面就有一個(gè)你的圖像。但你試過兩面鏡子一起照嗎？如果A、B兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個(gè)“化身”。
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
電腦有時(shí)會處于疑似死機(jī)的狀態(tài)。就當(dāng)你失去耐心，打算Reset時(shí)，突然它像酒醒了一樣，把你剛才單擊的所有操作全部都按順序執(zhí)行了一遍。
4.11　隊(duì)列的抽象數(shù)據(jù)類型 94
4.12　循環(huán)隊(duì)列 95
你上了公交車發(fā)現(xiàn)前排有兩個(gè)空座位，而后排所有座位都已經(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ì)列，如果你中途猶豫，臨時(shí)轉(zhuǎn)向，也許你就只能和企鵝相伴永遠(yuǎn)。可事實(shí)上，無論哪個(gè)方向，只要你堅(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個(gè)字。后8個(gè)字是“我恨你是不可能的”，點(diǎn)發(fā)送。后來得知對方收到的，只有70個(gè)字，短信結(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”，……在匹配時(shí)，每次都得將T中字符循環(huán)到后一位才發(fā)現(xiàn)，哦，原來它們是不匹配的。
5.7　KMP模式匹配算法 113
很多年前我們的科學(xué)家覺得像這種有多個(gè)0和1重復(fù)字符的字符串，卻需要挨個(gè)遍歷的算法，是非常糟糕的事情。
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í)就是我們在講解棧時(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
你人生的道路上，高考填志愿要面臨哪個(gè)城市、哪所大學(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)的時(shí)間或空間，都應(yīng)該考慮節(jié)約。
6.10.1?線索二叉樹的原理 159
6.10.2?線索二叉樹結(jié)構(gòu)的實(shí)現(xiàn) 162
6.11　樹、森林與二叉樹的轉(zhuǎn)換 165
有個(gè)鄉(xiāng)鎮(zhèn)企業(yè)也買了同樣的生產(chǎn)線，老板發(fā)現(xiàn)這個(gè)問題后找了個(gè)小工來說：你必須搞定，不然炒你魷魚。小工很快想出了辦法：他在生產(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
壓縮而不出錯(cuò)是如何做到的呢？簡單地說，就是把我們要壓縮的文本進(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
人受傷時(shí)會流下淚水。樹受傷時(shí)，天將不會哭。希望我們的未來不要僅僅是鋼筋水泥建造的高樓，也要有那郁郁蔥蔥的森林和草地，我們?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ā)事件，及時(shí)打電話給美國當(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)鑰匙不見了。一定是我兒子拿著玩，不知道丟到哪個(gè)犄角旮旯去了，你們說，我應(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)檫@個(gè)方案比后兩個(gè)方案一半還多的成本會讓老板氣暈過去的。
7.6.1?普里姆（Prim）算法 209
7.6.2?克魯斯卡爾（Kruskal）算法 213
7.7　短路徑 218
有人為了省錢，需路程短，但換乘站間距離長等原因并不省時(shí)間；另一些人，他為趕時(shí)間，的需求是總時(shí)間要短；還有一類人，他們不想多走路，關(guān)鍵是換乘要少，這樣可以在車上好好休息一下。
7.7.1?迪杰斯特拉（Dijkstra）算法 220
7.7.2?弗洛伊德（Floyd）算法 225
7.8　拓?fù)渑判?229
電影制作不可能在人員到位進(jìn)駐場地時(shí)，導(dǎo)演還沒有找到，也不可能在拍攝過程中，場地都沒有。這都會導(dǎo)致荒謬的結(jié)果。
7.8.1?拓?fù)渑判蚪榻B 229
7.8.2?拓?fù)渑判蛩惴?230
7.9　關(guān)鍵路徑 234
假如造一個(gè)輪子要0.5天、造一個(gè)發(fā)動機(jī)要3天、造一個(gè)車底盤要2天、造一個(gè)外殼要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ò)時(shí)代的新名詞，如 “蝸居”“蟻?zhàn)?rdquo;等，如果需要將它們收錄到漢語詞典中，顯然收錄時(shí)就需要查找它們是否存在，以及如果不存在時(shí)應(yīng)該收錄的位置。
8.3　順序表查找 249
8.3.1?順序表查找算法 249
8.3.2?順序表查找優(yōu)化 250
8.4　有序表查找 251
我在紙上已經(jīng)寫好了一個(gè)100以內(nèi)的正整數(shù)請你猜，問幾次可以猜出來。當(dāng)時(shí)已經(jīng)介紹了如何才可以快猜出這個(gè)數(shù)字。我們把這種每次取中間記錄查找的方法叫做折半查找。
8.4.1?折半查找 251
8.4.2?插值查找 253
8.4.3?斐波那契查找 255
8.5　線性索引查找 257
我母親年紀(jì)大了，經(jīng)常在家里找不到東西，于是她用一小本子，記錄了家里所有小東西放置的位置，比如戶口本放在右手床頭柜下面抽屜中，鈔票放在衣……咳，這個(gè)就不提了。
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
平板就是一個(gè)世界，當(dāng)誘惑降臨，人們心中的平衡被打破，世界就會混亂，后留下的只有孤獨(dú)寂寞失敗。這種單調(diào)的機(jī)械化的社會，禁不住誘惑的侵蝕，容易被侵蝕的，恰恰是空虛的心靈。
8.7.1?平衡二叉樹的實(shí)現(xiàn)原理 275
8.7.2?平衡二叉樹的實(shí)現(xiàn)算法 278
8.8　多路查找樹（B樹） 284
要觀察一個(gè)公司是否嚴(yán)謹(jǐn)，看他們?nèi)绾伍_會就知道了。如果開會時(shí)每一個(gè)人都只是帶一張嘴，即興發(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é)校有個(gè)叫張三豐的人打得特別好，于是到學(xué)校學(xué)生處找人，工作人員拿出學(xué)生名單，終告訴你，學(xué)校沒這個(gè)人，并說張三豐幾百年前就已經(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
我們每個(gè)人都希望身體健康，雖然疾病可以預(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
如果我是個(gè)喜歡汽車的人，時(shí)常搜汽車信息。那么當(dāng)我在搜索框中輸入“甲殼蟲”“美洲虎”等關(guān)鍵詞時(shí)，不要讓動物和人物成為搜索的頭條。
8.14　結(jié)尾語 306
第9章　排序 309
9.1　開場白 310
假如我想買一臺iPhone 4的手機(jī)，于是上了某電子商務(wù)網(wǎng)站去搜索?？伤阉骱蟀l(fā)現(xiàn)，有8863個(gè)相關(guān)的物品，如此之多，這叫我如何選擇。我其實(shí)是想買便宜一點(diǎn)的，但是又怕遇到騙子，想找信譽(yù)好的商家，如何做？
9.2　排序的基本概念與分類 310
比如我們某些大學(xué)為了選拔在主科上更優(yōu)秀的學(xué)生，要求對所有學(xué)生的所有科目總分倒序排名，并且在同樣總分的情況下將語數(shù)外總分做倒序排名。這就是對總分和語數(shù)外總分兩個(gè)次關(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ù)組時(shí)，通常都會介紹一種排序算法，而這個(gè)算法一般就是冒泡排序。并不是它的名稱很好聽，而是說這個(gè)算法的思路簡單，容易理解。
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
還有一種做股票的人，他們很少出手，只是在不斷觀察和判斷，等時(shí)機(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ā)明，使得我們終于突破了慢速排序的時(shí)代（超越了時(shí)間復(fù)雜度為O(n2)），之后，更為高效的排序算法也就相繼出現(xiàn)了。
9.6.1?希爾排序原理 324
9.6.2?希爾排序算法 325
9.6.3?希爾排序復(fù)雜度分析 328
9.7　堆排序 329
什么叫堆結(jié)構(gòu)呢？回憶一下我們小時(shí)候，特別是男同學(xué)，基本都玩過疊羅漢的惡作劇。通常都是先把某個(gè)要整的人按倒在地，然后大家就一擁而上撲了上去……后果？后果當(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
終于我們的高手要登場了，將來你工作后，你的老板讓你寫個(gè)排序算法，而你會的算法中竟然沒有快速排序，我想你還是不要聲張，偷偷去把快速排序算法找來敲進(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)別人做不到的時(shí)候，他們就想要告訴你，你也不能。如果你想要些什么，就得去努力爭取。就這樣！