1.1開場白2
如果妳給壹個人壹個程序，妳會折磨他壹整天；如果妳教壹個人怎麽寫程序，妳會折磨他壹輩子。
1.2妳是怎麽學會數據結構的？三
在他完成開發並通過測試後，他自豪地提交了代碼。看完代碼，項目經理拍著桌子對他說:“妳是怎麽學會數據結構的？”
1.3數據結構4的原點
1.4基本概念和術語5
俗話說“巧婦難為無米之炊”，再強大的電腦也只能和米壹起工作，否則就是壹堆垃圾。這個“米”就是數據。
1.4.1數據5
1.4.2數據元素5
1.4.3數據項6
1.4.4數據對象6
1.4.5數據結構6
1.5邏輯結構和物理結構7
1.5.1邏輯結構7
1.5.2物理結構9
1.6抽象數據類型11
每個人都需要房子住，但是沒錢考慮大房子顯然沒有意義。因此有各種類型的商品房，包括幾百平方米的別墅和只有兩平方米的膠囊公寓...
1.6.1數據類型11
. 1.6.2抽象數據類型12
1.7匯總審核14
1.8結尾15
最終結果壹定是妳說“數據結構——僅此而已。”
第二章算法17
2.1開場白18
2.2數據結構與算法18的關系
計算機領域的前輩都是壹群牛逼的人，他們把很多看似無解或者困難的問題變得如此奇妙神奇。
2.3兩種算法的比較19
高斯上小學的壹天，老師讓每個學生計算1+2+…+100的結果，誰先算出來誰就先回家…
2.4算法定義20
現實世界中的算法千變萬化，沒有壹個萬能的算法可以解決所有的問題。哪怕是很小的問題，解決這類問題的優秀算法也不壹定適合它。
2.5算法的特點21
2.5.1輸入/輸出21
2.5.2缺乏性21
2.5.3確定性21
2.5.4可行性21
2.6算法設計要求22
高考100人的平均分和全省所有考生的平均分在占用時間和內存存儲上有很大的差異，自然追求壹種高效率低存儲的算法來解決問題。
2.6.1正確性22
可讀性23
穩健性23
2.6.4高時間效率和低存儲容量23
2.7算法效率的測量方法24
隨著n值的增大，兩者在時間效率上的差距越來越大。比如有的人天天在學習，有的人在打遊戲睡覺。畢業後，前者名企爭搶，後者無處找工作。
2.7.1事後統計法24
2.7.2事前分析和估計方法25
2.8函數的漸近增長27
2.9算法時間復雜度29
大O的推導不難理解，其實就是對數列的壹些相關運算，更多的是數學知識和能力。
2.9.1算法時間復雜度定義29
2.9.2推導大O階的方法30
2.9.3常量順序30
2.9.4線性順序31
2.9.5對數階32
2.9.6平方階32
2.10常見時間復雜度35
有時候，告訴妳不能嘗試的東西，也是壹種知識的傳遞。不壹定要被毒蛇咬過才知道蛇是不能惹的。
2.11最壞情況和平均情況35
2.12算法空間復雜度36
事先建立壹個大小為2050的數組，然後根據下標數字對應所有年份。如果是閏年，這個數組項的值就是1，如果不是，就是0。這樣，所謂判斷壹年是不是閏年就變成了求這個數組中某壹項的值的問題。
2.13總結回顧37
後記38
愚公移山是可敬的，但發明炸藥和推土機可能更實際、更聰明。
第3章線性表41
3.1開場白42
門外的家長擠在大門口，與裏面秩序井然的孩子形成鮮明對比。嗯，有時候大人做的事情其實比孩子還不如。
3.2線性表的定義42
3.3線性表格的抽象數據類型45
有時候我們想知道壹個孩子(比如麥兜)是不是班裏的同學，老師會告訴我，不是，麥兜在春田花花幼兒園。這種確定元素是否存在的操作非常常見。
3.4線性表的順序存儲結構47
每次吃完早飯，他就沖到圖書館，挑好位置，把書按座位壹本壹本地放進書包裏。他在壹長排中占了九個座位。
3.4.1順序存儲定義47
順序存儲模式47
3.4.3數據長度和線性表長度之間的差異48
地址計算方法49
3.5順序存儲結構50的插入和刪除
當我在春運高峰去買火車票時，每個人都排好了隊。這時，壹個美女走過來:“妳能把我放在妳面前嗎？”這太可怕了。後面的人就像蟲子壹樣，都要退壹步。
3.5.1獲取元素操作50
3.5.2插入操作51
刪除操作52
3.5.4線性表順序存儲結構的優缺點54
3.6線性表的鏈式存儲結構55
反正相鄰元素之間要留有足夠的空間，所以幹脆不要考慮所有元素的相鄰位置，有空間就去哪裏。但是只要讓每個元素知道它的下壹個元素在哪裏。
3.6.1解決順序存儲結構不足
方法55
3.6.2線性表鏈式存儲結構定義56
3.6.3頭指針和頭節點的異同58
3.6.4線性表鏈式存儲結構代碼描述58
3.7單鏈表的讀取60
3.8單鏈表的插入和刪除61
原來爸爸左手牽著媽媽的手，右手牽著寶寶的手，沿著馬路散步。突然，迎面走來壹個美女，父親心不在焉地看著。這壹幕被我媽抓住了，我就把這對父子拉開，拉著寶寶的左手，快步往前走。
3.8.1插入單鏈表61
3.8.2刪除單鏈表64
3.9全表的單鏈表創建66
3.10刪除單鏈表69的整個表
3.11單鏈表結構和順序存儲結構的優缺點70
3.12靜態鏈表71
對於壹些語言，比如basic、fortran等早期的高級編程語言，因為沒有指針，這種鏈表結構是無法按照我們前面說的來實現的。我們做什麽呢
3.12.1靜態鏈表的插入操作73
3.12.2靜態鏈表的刪除操作75
3.12.3靜態鏈表的優缺點77
3.13循環鏈表78
輪回的想法很有意思。它強調的是不管妳這輩子是富是窮，如果妳繼續行善，下輩子會更好，反之亦然。
3.14鏈表81
就像每個人的人生壹樣，想要有所收獲就要付出代價。由於雙向鏈表比單向鏈表有更多的數據結構，比如反向遍歷搜索，所以也需要付出很小的代價。
3.15總結回顧84
尾聲85
如果妳覺得上學是壹種痛苦，假設妳能活到80歲，其實妳最多會痛苦20年。用四分之壹的人生換來余生的幸福生活，這不算什麽。
第4章堆棧和隊列87
4.1開場白88
妳想想，當妳準備用槍的時候，突然這把手槍明明有子彈卻打不開。那不是致命的嗎？
4.2堆棧的定義89
很多類似的軟件，比如word，photoshop，都有撤銷的操作，也是通過堆棧實現的。
4.2.1堆棧定義89
4.2.2堆棧入和堆棧出變化90
4.3堆棧91的抽象數據類型
4.4堆棧順序存儲結構和實現92
4.4.1堆棧順序存儲結構92
4.4.2堆棧93的順序存儲結構的堆棧操作
4.4.3從堆棧中取出堆棧的順序存儲結構94。
4.5兩層* * *享受空間94
兩個大學室友畢業後同時去了北京工作。他們倆在租房的時候都希望找壹個壹居室或者壹居室，但是都買不起。
4.6棧鏈存儲結構及其實現97
4.6.1棧鏈存儲結構97
4.6.2堆棧鏈存儲結構堆棧操作98
4.6.3棧鏈存儲結構出棧操作99
4.7堆棧的作用100
4.8堆棧的應用-遞歸100
當妳站在鏡子前，鏡子裏有妳的影像。但是妳試過壹起看兩面鏡子嗎？如果鏡子A和鏡子B面對面放置，妳站在中間。嘿，兩個鏡子裏都有成千上萬個妳的“化身”。
4.8.1斐波那契數列實現101
遞歸定義103
4.9四個算術表達式的堆棧評估的應用104
4.9.1後綴(逆波蘭語)表示定義104
4.9.2後綴表達式106的計算結果
4.9.3中綴表達式到後綴表達式108
4.10隊列111的定義
計算機有時會處於疑似崩潰的狀態。就在妳失去耐心打算重置的時候。突然，它像喝醉了壹樣，按順序執行了妳剛才點擊的所有操作。
4.11隊列的抽象數據類型112
4.12循環隊列113
妳上了車，發現前排有兩個空座位，後排的座位都滿了。妳會怎麽做？馬上下車，對自己說，後面沒座位了，我等下壹趟？沒那麽傻的人，前面有座位，當然能坐。
4.12.1隊列112中順序存儲不足
4.12.2循環隊列定義114
4.13隊列的鏈式存儲結構及其實現
4.13.1隊列鏈存儲結構入隊操作118
4.13.2隊列鏈存儲結構出列操作119
4.14匯總審核120
4.15結尾121
生活需要隊列精神的體現。從南極到北極，不過是從南緯90度到北緯90度的隊列。如果妳半途而廢，臨時轉彎，也許妳就只能永遠和企鵝在壹起了。但其實無論哪個方向，只要堅持，都是可以到達終點的。
第五章字符串123
5.1開場白124
“幹澀的眼睛望著水對面的遠山，妳見過幾顆心？空壺怕喝壹杯酒，和諧難寫壹首詩。方式阻止人久離，消息發回晚無鵝。孤燈長留夜孤，夫記妻父。”.....但細讀發現，這首詩是可以倒著讀的。
5.2字符串124的定義
我說的“結束”、“結束”、“謊言”這幾個詞，其實就是“愛人”、“朋友”、“相信”這幾個詞串的子串。
5.3字符串比較126
5.4抽象數據類型字符串127
5.5字符串存儲結構128
我的感覺有問題。為了給女朋友解釋，我準備發壹條75字打字的短信。最後八個字是“我討厭妳是不可能的”，點擊發送。後來才知道對方收到的只有70個字，短信結尾是“...我討厭妳”。
5.5.1序列存儲結構129
5.5.2字符串的鏈式存儲結構131
5.6樸素模式匹配算法131
主字符串是S = " 000000000000000000000000000000000000000000000000000000000000001 "，匹配的子字符串是T = " 000000000000001 "...匹配時，T中的字符每次都要循環。
5.7kmp模式匹配算法135
很多年前，我們的科學家認為，壹個包含多個0和1重復字符的字符串需要逐個遍歷，這是壹件非常糟糕的事情。
5.7.1kmp模式匹配算法原理135
5 . 7 . 2下壹個數組值派生139
5.7.3kmp模式匹配算法實現141。
5 . 7 . 4 KP模式匹配算法改進142
5 . 7 . 5 Nextval數組值144的推導
5.8總結回顧146
5.9結尾146
《玄寂地圖》有840個字* * *，縱橫29個字。通過縱讀、橫讀、斜讀、交互讀、正讀、反讀或倒讀、疊字等方式，可組成7958首詩。詩中有三、四、五、六、七言。仔細聽，是7958。
第六章樹149
6.1開場白150
壹棵樹再高，也是從小到大，從根到葉，壹點壹點長大的。俗話說十年栽樹，百年育人，可壹棵大樹十幾年就這麽容易。
6.2樹150的定義
tree的定義其實就是我們解釋棧的時候提到的遞歸方法。也就是說在樹的定義中也使用了樹的概念，這是壹種比較新的定義方法。
6.2.1節點分類152
6.2.2節點之間的關系152
6.2.3樹153的其他相關概念
6.3樹的抽象數據類型154
6.4 155樹的存儲結構
6.4.1父母代表155
6.4.2兒童代表158
6.4.3子女兄弟的代表權162
6.5二叉樹的定義163
蘇東坡曾說:“人有悲歡離合，月有沈浮。此事永不圓滿。”意思是完美是理想，不完美是生活。我們平時舉的例子也是左高右低的非均勻二叉樹。有沒有完美的二叉樹？
6.5.1二叉樹特性164
6.5.2特殊二叉樹166
6.6二叉樹169的性質
6.6.1二叉樹屬性1 169
6.6.2二叉樹屬性2 169
6.6.3二叉樹屬性3 169
6.6.4二叉樹屬性4 170
6.6.5二叉樹屬性5 171
6.7二叉樹172的存儲結構
6.7.1二叉樹順序存儲結構172
6.7.2二進制鏈表173
6.8遍歷二叉樹174
在妳人生的道路上，高考要選擇填哪個城市，哪個大學，具體哪個專業。因為選擇方式的不同，遍歷的順序也完全不同。
6.8.1二叉樹遍歷原理174
6.8.2二叉樹遍歷方法175
6.8.3前序遍歷算法178
6.8.4序列遍歷算法181
6.8.5後序列遍歷算法184
6.8.6得出遍歷結果184
6.9二叉樹的建立187
6.10線索二叉樹188
我們現在提倡節約型社會，壹切都要以節約為前提。當然，我們的程序也不例外，我們應該考慮節省不能浪費的時間或空間。
6.10.1線索二叉樹原理188
6.10.2線索二叉樹結構的實現191
6.11樹、森林和二叉樹之間的轉換195
壹家鄉鎮企業也買了同樣的生產線。老板發現這個問題，就找了壹個苦力說，妳壹定要修好，不然就炒妳魷魚。小工很快想出了壹個辦法:他在生產線旁邊放了壹個風扇，猛吹，空肥皂盒自然會被吹走。
6.11.1樹轉換成二叉樹196
6.11.2森林轉換為二叉樹197
6.11.3二叉樹轉換為樹197
6.11.4二叉樹轉換為森林199
6.11.5遍歷樹和森林199
6.12赫夫曼樹及其應用200
如何壓縮不出錯？簡單來說，就是為了減少不必要的空間，對我們想要壓縮的文本進行重新編碼的技術。壓縮和解壓縮技術是在Hoeffmann的研究基礎上發展起來的，我們應該記住他。
赫夫曼樹200
6.12.2赫夫曼樹定義和原理203
6.12.3霍夫曼編碼205
6.13總結回顧208
尾聲209
人在受傷的時候會流淚。當樹受傷了，天空再也不會哭泣。我希望我們的未來不僅僅是鋼筋混凝土建造的高樓大廈，還有郁郁蔥蔥的森林和草原，讓我們人類與自然和諧相處。
第七章圖211
7.1開場白212
如果妳不善於規劃，很可能會做出荒唐的決定，比如玩好新疆就去海南，然後再趕往黑龍江。
7.2圖形213的定義
現實中，人與人之間的關系很復雜。比如我認識的朋友可能也認識。這不是簡單的壹對壹或者壹對多的關系。這就是我們今天要學習的主題——圖形。
7.2.1各種圖形的定義214
7.2.2圖217的頂點與邊的關系
7.2.3連通圖相關術語219
7.2.4圖形定義和術語概述222
7.3圖形的抽象數據類型222
7.4圖表223的存儲結構
因為美國的夜晚是中國的白天，利用互聯網，他的員工可以在白天上班的時候，在晚上監控美國倉庫的實際情況。如果出現類似火災或盜竊的緊急情況，他們應該及時呼叫美國當地的相關人員進行處理。
7.4.1鄰接矩陣224
鄰接表228
7.4.3交叉鏈表232
7.4.4鄰接多表234
7.4.5邊集陣列236
7.5圖237的遍歷
壹天早上我正要出門，發現鑰匙不見了。我兒子肯定是拿著玩的，我也不知道它去哪了。妳認為我應該如何找到它？
7.5.1深度第壹遍歷238
寬度優先遍歷242
7.6最小生成樹245
如果妳日夜加班，結果就是計劃壹。我覺得妳應該在不遠處被開除(同學笑)。因為這個方案的成本是後兩個方案的壹半以上，會讓老板暈頭轉向。
7.6.1 prim算法247
7.6.2克魯斯卡爾算法251
7.7最短路徑257
有的人為了省錢需要最短的距離，但是換乘站之間的距離太遠並不節省時間；其他的，為了趕時間，最大的需求就是總時間要短；還有壹種人是不想多走路的。關鍵是少換乘，讓他們能在車上好好休息。
dijkstra算法259
弗洛伊德算法265
7.8拓撲排序270
人員到位了導演還沒找到是不可能拍電影的，拍攝過程中也不可能沒有場地。這將導致荒謬的結果。
7.8.1拓撲排序介紹271
拓撲排序算法272
7.9關鍵路徑277
如果造壹個輪子需要0.5天，造壹個發動機需要3天，造壹個汽車底盤需要2天，造壹個外殼需要2天，組裝其他零件需要2天，在壹個地方組裝所有零件需要0.5天，組裝壹輛汽車需要2天，那麽壹個汽車工廠造壹輛汽車需要多少天？
7.9.1關鍵路徑算法原理279
關鍵路徑算法280
7.10總結回顧287
7.11結尾289
世界上最遙遠的距離，不是牛A和牛C的差距很小，而是妳們中的壹些人在牛逼的路上，而另壹些人在踏入大學校園的時候，學會了放棄。
第八章找到291
8.1開場白292
當妳認真寫壹篇博文或者上傳壹組照片到網上，無數來自世界各地的“蜘蛛”就會湧向妳。所謂蜘蛛，就是搜索引擎公司服務器上的軟件。它把互聯網當成壹張蜘蛛網，日日夜夜在上面訪問各種信息。
8.2搜索簡介293
比如網絡時代的新名詞，比如“蝸居”、“蟻族”等，如果需要收錄到漢語詞典中，顯然在收錄的時候，就要弄清楚它們是否存在，如果不存在，應該收錄到哪裏。
8.3序列表查找295
8.3.1序列表查找算法296
8.3.2序列表搜索優化297
8.4有序表格查找298
我在紙上寫了壹個100以內的正整數。請猜猜看。問幾次就能猜到了。當時介紹了如何最快猜出這個數字。我們稱這種壹次查找中間記錄的方法為半查找法。
8.4.1半搜索298
8.4.2插值搜索301
8.4.3斐波那契搜索302
8.5線性索引查找306
我媽年紀大了，經常在家裏找不到東西，就用小本子記錄家裏所有小東西的位置，比如右邊床頭櫃下抽屜裏的戶口本，衣服裏的錢...嗯，我就不提了。
8.5.1密集指數307
8.5.2塊索引308
8.5.3倒排索引311
8.6二叉排序樹313
後來，老虎來了。壹個人拼命跑，而另壹個人則急中生智爬上了樹。老虎不會爬樹，因此...爬樹人改變了對跑步的想法，這個改變有多重要，他救了自己壹命。
8.6.1二叉排序樹查找操作316
8.6.2二叉排序樹插入操作318
8.6.3二叉排序樹刪除操作320
8.6.4二叉排序樹摘要327
8.7平衡二叉樹(avl樹)328
平板電腦是壹個世界。當誘惑來臨，人們心中的平衡被打破，世界就會混亂，只剩下孤獨和失敗。這個單調機械化的社會，難免會被誘惑侵蝕。恰恰是最空虛的心靈最容易被侵蝕。
8.7.1平衡二叉樹實現原理330
8.7.2平衡二叉樹實現算法334
8.8多路徑搜索樹(B樹)341
觀察壹個公司是否嚴謹，只要看他們開會的方式就可以了。如果開會的時候大家都只是壹張嘴即興發言，那壹定是壹個松懈的公司。
樹343
樹348
8.8.3b樹349
8.8.4b+樹351
8.9哈希表查找(哈希表)概述353
妳真的要學太極拳。聽說學校裏有個叫張三豐的玩得很好，就去學校的學生處找人。工作人員拿出學生名單，最後告訴妳學校裏沒有這個人，還說張三豐幾百年前就死在武當山了。
8.9.1散列表查找定義354
8.9.2哈希表查找步驟355
8.10哈希函數構造方法356
8.10.1直接尋址方法357
8.10.2數字分析方法358
8.10.3平方取中法359。
8.10.4折疊方法359
8.10.5除以余數法359
8.10.6隨機數法360
8.11處理哈希沖突的方法360
我們每個人都想健康。雖然疾病是可以預防的，但卻是不可避免的。誰也不能說他生下來就沒生過病。
8.11.1開放式尋址方法361
8.11.2哈希函數方法363
8.11.3鏈地址法363
8.11.4 * * *溢出面積法364
8.12散列表搜索實現365
8.12.1哈希表查找算法的實現
8.12.2哈希表查找性能分析367
8.13總結回顧368
尾聲369
如果我是壹個喜歡汽車的人，我會經常搜索汽車信息。然後當我在搜索框輸入“甲蟲”“美洲虎”等關鍵詞時，不要讓動物和人成為搜索的頭條。
第九章排序373
9.1開場白374
想買iphone4手機，就去某電商網站搜索。搜了壹下，發現有8863個相關條目，這麽多，告訴我怎麽選。我其實想買便宜點的，但是怕遇到騙子，想找信譽好的商家。我該怎麽辦？
9.2排序的基本概念和分類375
比如，有的大學為了選拔主科比較好的學生，要求所有學生所有科目都要倒序排列，語言以外的總分在相同總分下也要倒序排列。這是總分和字數外總分的組合排序。
排序的穩定性376
9.2.2內部排序和外部排序377
9.2.3分類中使用的結構和功能378
9.3氣泡排序378
無論學習哪種編程語言，在學習循環和數組的時候，壹般都會引入壹種排序算法，而這種算法壹般就是冒泡排序。不是它的名字好聽，而是這個算法的思想最簡單，最容易理解。
9.3.1最簡單排序實現379
氣泡分類算法380
9.3.3氣泡排序的優化382
9.3.4氣泡排序復雜性分析383
9.4簡單選擇排序384
還有壹類人是做股票的。他們很少出手，但他們在不斷觀察判斷，時機壹到，就會果斷買入或賣出。因為他們的從容淡定，加上交易次數不多，最終收獲頗豐。
簡單選擇排序算法384
9.4.2簡單選擇排序復雜性分析385
9.5直接插入排序386
即使是第壹次玩撲克，只要知道這些數字，也不需要教妳分牌的方法。將3和4移到5的左邊，再將2移到最左邊，順序就排序了。這裏我們的卡片排序方式是直接插入排序方式。
9.5.1直接插入排序算法386。
9.5.2直接插入排序復雜性分析388
9.6希爾分揀389
無論如何，Hill排序算法的發明讓我們終於突破了慢排序的時代(超越了o(n2)的時間復雜度)，隨後更高效的排序算法陸續出現。
9.6.1希爾排序原則391
9.6.2希爾排序算法391
9.6.3希爾排序復雜性分析395
9.7堆排序396
什麽是堆結構？回想我們小的時候，尤其是男同學，基本都是在金字塔上惡作劇。通常是先把想被擰的人推倒在地，然後大家都撲到他身上...會有什麽後果？當然，後果是壹笑置之。
堆排序算法398
9.7.2堆排序的復雜性分析405
9.8合並排序406
就算妳是班裏第壹，甚至年級第壹，如果妳沒考上，也就意味著妳的成績不在全省前10000，基本上失去了當年上本科的機會。
合並排序算法407
9.8.2歸並排序的復雜度分析413
9.8.3合並排序的非遞歸實現413
9.9快速排序417
最後，我們的主人會出現。將來妳工作後，老板讓妳寫壹個排序算法，但妳知道的算法裏沒有快速排序。我覺得妳還是低調點，偷偷找個quick sort輸入電腦吧，這樣至少不會被大家取笑。
9.9.1快速排序417
9.9.2快速排序421的復雜度分析
9.9.3快速排序優化422
9.10總結回顧428
目前還沒有完善的排序算法，有優點就會有缺點。即使是快速排序法也只是在整體性能上更勝壹籌，也存在排序不穩定、需要大量輔助空間、對少量數據排序沒有優勢等缺點。
9.11結尾430
如果妳有夢想，妳必須捍衛它。別人做不到的時候，就想告訴妳，妳也不行。如果妳想要什麽，妳必須為之奮鬥。就是這樣！
附錄參考435