本文關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)　　

  更多相關(guān)文章： 大話 數(shù)據(jù) 結(jié)構(gòu)

《大話數(shù)據(jù)結(jié)構(gòu)》以一個計算機教師教學(xué)為場景，講解數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的知識。通篇以一種趣味方式來敘述，大量引用了各種各樣的生活知識來類比，并充分運用圖形語言來體現(xiàn)抽象內(nèi)容，對數(shù)據(jù)結(jié)構(gòu)所涉及到的一些經(jīng)典算法做到逐行分析、多算法比較。與市場上的同類數(shù)據(jù)結(jié)構(gòu)圖書相比，《大話數(shù)據(jù)結(jié)構(gòu)》內(nèi)容趣味易讀，算法講解細致深刻，是一本非常適合自學(xué)的讀物。
　　《大話數(shù)據(jù)結(jié)構(gòu)》主要內(nèi)容包含：數(shù)據(jù)結(jié)構(gòu)介紹、算法推導(dǎo)大o階的方法；順序結(jié)構(gòu)與鏈式結(jié)構(gòu)差異、棧與隊列的應(yīng)用；串的樸素模式匹配、kmp模式匹配算法；二叉樹前中后序遍歷、赫夫曼樹及應(yīng)用；圖的深度、廣度遍歷；最小生成樹兩種算法、最短路徑兩種算法；拓撲排序與關(guān)鍵路徑算法；折半查找、插值查找、斐波那契查找等靜態(tài)查找；稠密索引、分塊索引、倒排索引等索引技術(shù)；二叉排序樹、平衡二叉樹等動態(tài)查找；b樹、b+樹技術(shù)，散列表技術(shù)；冒泡、選擇、插入等簡單排序；希爾、堆、歸并、快速等改進排序……
　　《大話數(shù)據(jù)結(jié)構(gòu)》適合學(xué)過一門編程語言的各類讀者，包括在讀的大中專計算機專業(yè)學(xué)生、想轉(zhuǎn)行做開發(fā)的非專業(yè)人員、欲考計算機研究生的應(yīng)屆或在職人員，以及工作后需要補學(xué)或溫習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的程序員等。
前言　本書起因
　　大家好！我是《大話設(shè)計模式》（2008年初出版）的作者，三年來，承蒙廣大讀者的厚愛，《大話設(shè)計模式》取得了較大的成功。僅在當當網(wǎng)，截止本文寫作時，就已經(jīng)有1073次評論，705次5星評價，位居五星圖書榜計算機/網(wǎng)絡(luò)類的累計總榜第二名。此書已經(jīng)成為國內(nèi)原創(chuàng)計算機類圖書最暢銷的書籍之一。
　　對于這樣一個自己喜歡做、可以做得好，而且已經(jīng)得到了市場廣泛認可，為很多朋友提供幫助的事情，我沒有理由不去繼續(xù)做下去。這就是我準備再寫書的原因。
　　我曾做過調(diào)查，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)者大多都有這樣的感慨：數(shù)據(jù)結(jié)構(gòu)很重要，一定要學(xué)好，但數(shù)據(jù)結(jié)構(gòu)比較抽象，有些算法理解起來很困難，學(xué)得很累。可我更希望傳達這樣的信息：數(shù)據(jù)結(jié)構(gòu)非常有趣，很多算法是智慧的結(jié)晶，學(xué)習(xí)它是去感受計算機編程技術(shù)的魅力，在理解掌握它的同時，整個過程都是一種愉悅的精神感受，而非枯燥乏味的一門課程。因此我決定寫作一本關(guān)于數(shù)據(jù)結(jié)構(gòu)有趣的書。
　　不過現(xiàn)實總比理想來得更“現(xiàn)實”。要想把書寫好，談何容易，我需要突破很多困難……嗐！不管如何，現(xiàn)在您看到了本書，那就說明我已經(jīng)克服了困難戰(zhàn)勝了自己。希望您可以喜歡上這本書。
　　本書定位
　　本書的定位就是一本適合讀者自學(xué)數(shù)據(jù)結(jié)構(gòu)的書籍，它有區(qū)別于教材，希望給大家另一種閱讀體驗。
　　通常講解數(shù)據(jù)結(jié)構(gòu)的圖書都是以教材的方式呈現(xiàn)。在寫作前，我購買或在圖書館借閱了十幾本非常好的數(shù)據(jù)結(jié)構(gòu)相關(guān)教材用來為寫作本書做準備。但經(jīng)過認真閱讀后，我發(fā)現(xiàn)，它們大多不是一本好的“自學(xué)讀物”。
　　我沒有輕視這些好書的意思，不過教材和自學(xué)讀物，所面向的讀者是完全不同的。
　　好的教材應(yīng)該是提綱挈領(lǐng)、重點突出，一定要留出思考的空間，否則就沒必要再聽老師上課了。很多內(nèi)容的講解是由老師在課堂完成，教材中有練習(xí)、課后習(xí)題、思考題等，這些大多可以通過老師來解答。比如我們中學(xué)時的語文、數(shù)學(xué)課本，很薄的一本書通常要用一學(xué)期、甚至一年的時間來學(xué)習(xí)，這就是因為它們是教材而不是自學(xué)讀物。如果是小說，可能一兩天就讀完了。
　　好的自學(xué)讀物的目標是讓初學(xué)者“獨自”全盤掌握知識，需要強調(diào)“獨自”一詞，這就說明讀者在閱讀時，是完全依靠自己的力量來向未知發(fā)出挑戰(zhàn)。因此書中內(nèi)容，要么不寫，寫了就應(yīng)該寫透。如果讀者在閱讀時總是疑惑重重，那么這本書就有很大的問題了。
　　我也就是在基于這樣的認識，決心將《大話數(shù)據(jù)結(jié)構(gòu)》真正寫成一本關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的自學(xué)讀物來展開寫作的。
　　本書特色
　　1．趣味引導(dǎo)
　　大部分的編程類圖書，在內(nèi)容上基本都是直奔主題。但是尼采曾說過：“人們無法理解他沒有經(jīng)歷過的事情。”換句話說，我們只接受過去早已理解的事物相關(guān)的信息。這是一種比較學(xué)習(xí)過程，在這個過程中，大腦尋找每條信息之間的聯(lián)系。所以教育專家普遍認為，吸引學(xué)生的注意力，比較好的辦法是用他們比較熟知的知識開始。
　　因此在本書中，我會用一個故事、一個趣味題目、一部電影的介紹等形式來作為每一章甚至很多小節(jié)的開頭，選擇的內(nèi)容也多多少少與要講的主題內(nèi)容相關(guān)。這并不是多余，而是有意為之。事實上，這樣的形式在我的前一本書中已經(jīng)得到了普遍認可。
　　2．圖文并茂
　　西方有句諺語，“A picture is worth a thousand words.（一圖值千言）”。用上千個字描述不明白的東西，很可能一張圖就能解釋清楚。
　　我非常認可這個觀點，所以本書雖沒有達到每一頁都有圖，但基本做到了絕大部分講解都有相關(guān)圖示，關(guān)鍵算法更是通過多圖逐步分解剖析。盡管這帶來了寫作上的難度，但卻可以達到較好的效果。畢竟，讀者通過本書開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時，要從一無所知或略知一二到完全理解，甚至掌握應(yīng)用，是需要一個比較艱苦的過程，用大量的圖示可以減少這個過程的長度。
　　3．代碼詳解
.　　我在寫作中盡量摒棄了傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)教材的“重理論思想而輕代碼講解”的作法。在準備數(shù)據(jù)結(jié)構(gòu)寫作時我發(fā)現(xiàn)，很多教材對數(shù)據(jù)結(jié)構(gòu)理論和算法設(shè)計思想講得比較好，可一到實際代碼時，有的把代碼貼出來加少量注釋，有的直接用偽代碼形式。這對于上課的學(xué)生還好，畢竟有老師在課堂中去詳解代碼編寫原理，可是對于初學(xué)數(shù)據(jù)結(jié)構(gòu)和算法的自學(xué)者而言，如果書中不去解釋代碼某些細節(jié)為什么那樣編寫的原因，甚至代碼根本不可能在某個編譯器中運行通過，其挫折感是很強烈的。比如即使理解了圖結(jié)構(gòu)中的最短路徑求解原理，也可能無法寫出最短路徑的算法。
　　我把代碼在運行過程中變量的變化融入到整個算法設(shè)計思想的講解中，配合相應(yīng)的示意圖，會幫助大家更加容易理解算法的實質(zhì)。這種講解模式在本書的第6、7、8、9章的很多復(fù)雜算法中有具體體現(xiàn)，越是復(fù)雜的代碼越是講解細致。這算是本書的一個特色，希望對讀者有幫助。
　　4．形式新穎
　　我把本書的內(nèi)容虛構(gòu)成了一個老師上課的場景，所有內(nèi)容都通過這位老師表達出來，書中的文字非�？谡Z化，這樣做的目的是為了更加直觀地讓讀者感覺，自己是在學(xué)習(xí)，是在上課。有人可能會說，現(xiàn)在的課堂大都是讓人昏昏欲睡，把讀者帶入上課場景，不是更加讓讀者犯困嗎？我覺得如果你的學(xué)習(xí)經(jīng)歷中聽過一些優(yōu)秀老師的課，你就不會下這樣的結(jié)論。好的老師講課，是可以做到引人入勝的。
　　有人可能會問，我為什么不用《大話設(shè)計模式》中的對話形式，而采用講課形式呢？這是對數(shù)據(jù)結(jié)構(gòu)這門學(xué)問的特點考慮的。設(shè)計模式主要都是思想體現(xiàn)，通常會仁者見仁、智者見智，用對話展開比較容易；而數(shù)據(jù)結(jié)構(gòu)中更多的是定義、術(shù)語、經(jīng)典算法等，這些公認的知識，可討論的地方并不多，更多的是需要把它講清楚。讓兩個人在一起討論某個設(shè)計模式的優(yōu)缺點，會非常合適，而討論數(shù)據(jù)結(jié)構(gòu)定義的好壞，就沒有太大意義了，不如讓一個老師告訴學(xué)生數(shù)據(jù)結(jié)構(gòu)的定義好在哪里更符合實際。因此用傳統(tǒng)的講課形式會好一些。
　　另外，本書沒有習(xí)題，有思考的題目也一定會給出某種答案。但本書每個復(fù)雜知識點的末尾，都會提供另一本書的進一步閱讀建議。這也是基于它是一本自學(xué)讀物的原則。讀者閱讀本書可能是任何時間任何地方，如果書中存在沒有解答的習(xí)題，碰到了困難是沒法及時找到老師來幫助的，因此本書盡量避免讓讀者有這樣的困惑存在。如果需要練習(xí)的同學(xué)，我覺得還是應(yīng)該考慮再去買本習(xí)題集來學(xué)習(xí)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，做題和上機寫代碼非常有必要，從這個角度也說明，閱讀完本書其實也只是完成入門而已。
　　本書既然是以老師上課的形式來進行，那就免不了要融入一名教師除了授業(yè)解惑以外，還要傳達一些個人價值觀的體現(xiàn)。書中很多細微處，如對某位科學(xué)家的尊敬、對某個算法的推崇、對勤奮勵志故事的講述等都在表達著一個老師向?qū)W生傳遞真、善、美的意愿。我始終認為，讀者拿到的雖然只是一本沒有表情、不會說話的書，但其實也是在隔空與另一個朋友交流。人與人的交流不可能只是就事論事，一定會有情感的溝通，這種情感如果能產(chǎn)生共鳴、達成互信，就會讓事情（比如學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法這件事）本身更容易理解和接受。
　　本書內(nèi)容
　　本書主要是按照教育部關(guān)于計算機專業(yè)數(shù)據(jù)結(jié)構(gòu)課程大綱的要求略微增減來組織內(nèi)容的。
　　主要包括：數(shù)據(jù)結(jié)構(gòu)介紹，算法推導(dǎo)大O階的方法，線性表結(jié)構(gòu)的介紹，順序結(jié)構(gòu)與鏈式結(jié)構(gòu)差異，棧與隊列的應(yīng)用，串的樸素模式匹配、KMP模式匹配算法，樹結(jié)構(gòu)的介紹，二叉樹前中后序遍歷，線索二叉樹，赫夫曼樹及應(yīng)用，圖結(jié)構(gòu)的介紹，圖的深度、廣度遍歷，最小生成樹兩種算法，最短路徑兩種算法，拓撲排序與關(guān)鍵路徑算法，查找應(yīng)用的相關(guān)介紹，折半查找、插值查找、斐波那契查找等靜態(tài)查找，稠密索引、分塊索引、倒排索引等索引技術(shù)，二叉排序樹、平衡二叉樹等動態(tài)查找，B樹、B+樹技術(shù)，散列表技術(shù)，排序應(yīng)用的相關(guān)介紹，冒泡、選擇、插入等簡單排序，希爾、堆、歸并、快速等改進排序，各位排序算法的對比等。
　　本書讀者
　　數(shù)據(jù)結(jié)構(gòu)是計算機軟件相關(guān)專業(yè)的基礎(chǔ)課程，幾乎可以說，要想從事編程工作，無論你是否是科班出身，都不可以繞過這部分知識。因此，適合閱讀本書的讀者非常廣泛，包括在讀的本�？�、中專職高技校等計算機專業(yè)學(xué)生、想轉(zhuǎn)行做開發(fā)的非專業(yè)人員、欲考計算機研究生的應(yīng)屆或在職人員，以及工作后需要補學(xué)或溫習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的程序員等各類讀者。
　　本書對讀者的技術(shù)背影要求比較低，只要是學(xué)過一門高級編程語言，例如C、C++、Java、C#、VB等就可以開始閱讀本書。不過由于當中涉及到比較復(fù)雜的算法知識，需要讀者有一定的數(shù)學(xué)修養(yǎng)和邏輯思維能力，否則可能書籍的后半部分閱讀起來會比較吃力。
　　本書研讀方法
　　事實上，任何有難度的知識和技巧，都不是那么容易被掌握的。我盡管已經(jīng)朝著通俗易懂的方向努力，可有些數(shù)據(jù)結(jié)構(gòu)，特別是經(jīng)典算法，是幾代科學(xué)家的智慧結(jié)晶，因此要掌握它們還是需要讀者的全力投入。
　　美國暢銷書《如何閱讀一本書》中提到“閱讀可以是一件主動的事，閱讀越主動，效果越好。拿同樣的書給背景相近的兩個人閱讀，一個人卻比另一個人從書中得到了更多，這是因為，首先在于這人的主動，其次，在于他在閱讀中的每一種活動都參與了更多的技巧。這兩件事是息息相關(guān)的。閱讀是一個復(fù)雜的活動，就跟寫作一樣，包含了大量不同的活動。要達成良好的閱讀，這些活動都是不可或缺的。一個人越能良好運作這些活動，閱讀的效果也就越好。”
　　我當然希望讀者在閱讀本書后收獲巨大，但這顯然是一廂情愿。要想獲得更多，您可能也需要付出類似我寫作一樣的力氣來閱讀，例如摘抄文字、眉批心得、稿紙演算、代碼輸入電腦，以及您自己在編程工作中的運用等。這些相應(yīng)活動的執(zhí)行，將會使您得到巨大的收獲。
　　作為作者，建議本書的研讀方法為：
　　1．復(fù)習(xí)C語言的基礎(chǔ)知識。如果你掌握的是別的語言也不要緊，適當了解一些C語言和你掌握的編程語言的語法差異還是有必要的。甚至將本書代碼改造成另一種語言本身就是一種非常好的學(xué)習(xí)方法。
　　2．閱讀第一遍時，建議從頭至尾進行。如果你對前面的知識有足夠了解，當然可以跳過直接閱讀后面的章節(jié)。不過若要學(xué)習(xí)一門完整的知識并形成體系。通讀本書，還是最好的學(xué)習(xí)方法。
　　3．閱讀時，摘抄是非常好的習(xí)慣。“最淡的墨水也勝于最強的記憶！”有不少讀者會認為摘抄了將來也不會再去看，有什么必要，但其實在寫字的過程就是大腦學(xué)習(xí)的過程，寫字在減緩你閱讀的速度，從而讓你更好地消化閱讀的內(nèi)容。相信大家都能理解，“囫圇吞棗”和“慢慢品味”的差異，學(xué)習(xí)同樣如此。
　　4．閱讀每一章時，特別是在閱讀算法的推導(dǎo)過程時，一定要在電腦中運行代碼（本書源碼的下載地址可以到中的《大話數(shù)據(jù)結(jié)構(gòu)相關(guān)主題》中找到），了解代碼的運行過程。本書的很多算法都做到了逐行講解，但單純閱讀可能真的很難達到理解的程度（這是紙質(zhì)書無法克服的缺陷），需要你通過開發(fā)工具調(diào)試，并設(shè)置斷點和逐行執(zhí)行，并參照書中的講解，觀察變量的變化情況來理解算法的編寫原理。
　　5．閱讀完每一章時，一定要在理解基礎(chǔ)上記憶一些關(guān)鍵東西。最佳的效果就是你可以不看書也做到一點不錯地默寫出相關(guān)算法。
　　6．閱讀完每一章時，一定要適當練習(xí)。本書沒有提供練習(xí)題，但市場上相關(guān)的數(shù)據(jù)結(jié)構(gòu)習(xí)題集比比皆是，可以選擇嘗試。另外互聯(lián)網(wǎng)上也可以獲得足夠的習(xí)題來給你練習(xí)。練習(xí)的目的是為了檢測自己是否真的完全理解了書中的內(nèi)容。事實上很多時候，閱讀中的人們只是自我感覺理解，而并非真正的明白。
　　7．學(xué)習(xí)不可能一蹴而就，數(shù)據(jù)結(jié)構(gòu)和算法如果通過一本書就可以掌握，那本身就是笑話。本書附錄提供了本書寫作時的參考書目，基本都是最優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)或相關(guān)的中文書籍各有側(cè)重，建議大家可以適當?shù)亻喿x。
　　8．在之后的編程學(xué)習(xí)和工作中，盡量把已經(jīng)學(xué)到的數(shù)據(jù)結(jié)構(gòu)和算法知識運用到現(xiàn)實開發(fā)中。遺忘時翻閱本書回顧相關(guān)內(nèi)容，最終達到精通數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的境界。
　　編程語言說明
　　本書是用C語言編寫，基于C90（ISO C）的標準。讀者可以選擇任何一款基于C90標準的C語言開發(fā)工具或更高版本的開發(fā)工具來學(xué)習(xí)本書中的代碼。
　　本人一直習(xí)慣于用Visual Studio 2008作為開發(fā)工具，因此在寫作此書時，也是用此工具的Visual C++來編譯調(diào)試代碼，一切都相安無事，但寫作完成后，考慮到不同讀者應(yīng)用開發(fā)工具的習(xí)慣不同，最終在編輯的建議下，決定提供一份可在C90標準的C語言開發(fā)環(huán)境中編譯通過的代碼，結(jié)果發(fā)現(xiàn)錯誤百出。
　　例如C90標準的注釋要求是“/* 注釋文字 */”而不允許是“//注釋文字”：要求變量聲明必須要在函數(shù)的最前面，只能是“int i; for(i=0;i[n;i++)……”，而不允許如“for (int i=0;i[n;i++)”這樣的方式：再比如C++中函數(shù)的參數(shù)可以傳遞如“void CreateBiTree(BiTree &T)”的地址變量，但在C語言中，只能傳遞如“void CreateBiTree(BiTree *T)”的指針變量。因此當你看到書中的有些代碼到處都是“*”時，就用不著奇怪了。
　　出于為了讓代碼可以在低端編譯環(huán)境通過的考慮，犧牲一些代碼的簡捷性和優(yōu)雅性也是無可奈何和必要的。最終我將書中全部代碼都改成C90標準的代碼。
　　C語言初學(xué)者可能會因為剛接觸編程語言，特別是對指針的理解不深，而擔心閱讀困難。我個人感覺，單純學(xué)習(xí)指針是很難理解它的真正用途和好處，而通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，特別是像鏈式存儲結(jié)構(gòu)在各種結(jié)構(gòu)算法中的運用，反而可以讓讀者進一步的理解指針的優(yōu)越之處。從這個角度說，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)可以反過來加強讀者對C語言，特別是指針概念的理解。
　　編程語言差異
　　C語言是一門古老的高級語言，它的應(yīng)用范圍非常廣泛，因此我選擇它作為本書的算法展示語言。如果讀者之前學(xué)過它，那么閱讀本書就不存在語言障礙。懂得C++語言的讀者，同樣也不會有任何語言上的問題。
　　像掌握Java、C#、VB等面向?qū)ο笳Z言的讀者，當面對書中大量的C語言式的結(jié)構(gòu)（struct）聲明和針對結(jié)構(gòu)的參數(shù)傳遞的代碼時，都可以理解為是類的定義和由類生成對象的傳遞。盡管的確存在差異，但是并不影響整體對數(shù)據(jù)結(jié)構(gòu)知識和算法原理的理解。
　　我個人感覺，哪怕是對C語言不熟悉，也不妨利用學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的機會，學(xué)習(xí)一下C語言的編程方法，這對于將來應(yīng)用其他高級語言也是有很大幫助的。
　　不是一個人在戰(zhàn)斗
　　首先要感謝我的妻子李秀芳對我寫作本書期間的全力支持，我辭職寫作，沒有她精神上的理解鼓勵和生活上的悉心照顧，是不可能走出這一步并順利完成書稿的。我們的兒子程晟涵如今已經(jīng)三周歲，我是在他每日的歡聲笑語和哭哭啼啼中進行每一章節(jié)的構(gòu)思和寫作，希望他可以茁壯成長。我的父母已經(jīng)年邁，他們?yōu)槲业娜殑?chuàng)作也甚為擔心和憂慮，這里也要說一聲抱歉。
　　本人數(shù)據(jù)結(jié)構(gòu)的知識，是源自清華大學(xué)出版社出版的《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（嚴蔚敏、吳偉民編著）一書，嚴老師和吳老師算是我在數(shù)據(jù)結(jié)構(gòu)方面的啟蒙老師，本書的不少內(nèi)容和代碼也是參考了此書。機械工業(yè)出版社的《算法導(dǎo)論》對于本人的算法知識提高幫助很大，寫作中也大量吸收了書中的精華。寫作過程中，本人購買和借閱了與數(shù)據(jù)結(jié)構(gòu)相關(guān)的大量書籍，詳細書目見附錄。沒有前輩的貢獻，就沒有本書的出版，也希望本書能成為這些書籍的前期讀物。在此向這些圖書作者表示衷心的感謝。
　　僅有作者是不可能完成圖書的出版的，本人要非常感謝清華大學(xué)出版社的朋友們，他們是本書的最初讀者，也是協(xié)助本人將此書由毛糙變精良的最有力幫手。
　　本書的封面設(shè)計程瑜、插圖設(shè)計周翔，都是在反反復(fù)復(fù)的修改中完成創(chuàng)作的。
　　寫作中，還得到了周筠、盧鶇翔、張伸、胡文佳、Milo、陳鋼、劉超、劉唯一、楊繡國、戚嫵婷、雷順、楊詩盈、高宇翔、林健的友情幫助，他們都在本人的書稿創(chuàng)作中提出了寶貴建議。
　　在此向所有幫助與支持我的朋友道一聲：謝謝！
　　程 杰
　　
《大話數(shù)據(jù)結(jié)構(gòu)》
第1章數(shù)據(jù)結(jié)構(gòu)緒論 1
1.1開場白 2
如果你交給某人一個程序，你將折磨他一整天；如果你教某人如何編寫程序，你將折磨他一輩子。
1.2你數(shù)據(jù)結(jié)構(gòu)怎么學(xué)的？ 3
他完成開發(fā)并測試通過后，得意地提交了代碼。項目經(jīng)理看完代碼后拍著桌子對他說：“你數(shù)據(jù)結(jié)構(gòu)是怎么學(xué)的？”
1.3數(shù)據(jù)結(jié)構(gòu)起源 4
1.4基本概念和術(shù)語 5
正所謂“巧婦難為無米之炊”，再強大的計算機，也要有“米”下鍋才可以干活，否則就是一堆破銅爛鐵。這個“米”就是數(shù)據(jù)。
1.4.1數(shù)據(jù) 5
1.4.2數(shù)據(jù)元素 5
1.4.3數(shù)據(jù)項 6
1.4.4數(shù)據(jù)對象 6
1.4.5數(shù)據(jù)結(jié)構(gòu) 6
1.5邏輯結(jié)構(gòu)與物理結(jié)構(gòu) 7
1.5.1邏輯結(jié)構(gòu) 7
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é)回顧 14
1.8結(jié)尾語 15
最終的結(jié)果一定是，你對著別人很牛的說“數(shù)據(jù)結(jié)構(gòu)——就那么回事。”
第2章算法 17
2.1開場白 18
2.2數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系 18
計算機界的前輩們，是一幫很牛很牛的人，他們使得很多看似沒法解決或者很難解決的問題，變得如此美妙和神奇。
2.3兩種算法的比較 19
高斯在上小學(xué)的一天，老師要求每個學(xué)生都計算1+2+…+100的結(jié)果，誰先算出來誰先回家……
2.4算法定義 20
現(xiàn)實世界中的算法千變?nèi)f化，沒有通用算法可以解決所有問題。甚至一個小問題，某個解決此類問題很優(yōu)秀的算法卻未必就適合它。
2.5算法的特性 21
2.5.1輸入輸出 21
2.5.2有窮性 21
2.5.3確定性 21
2.5.4可行性 21
2.6算法設(shè)計的要求 22
求100個人的高考成績平均分與求全省所有考生的成績平均分在占用時間和內(nèi)存存儲上有非常大的差異，我們自然追求高效率和低存儲的算法來解決問題。
2.6.1正確性 22
2.6.2可讀性 23
2.6.3健壯性 23
2.6.4時間效率高和存儲量低 23
2.7算法效率的度量方法 24
隨著n值越來越大，它們在時間效率上的差異也就越來越大。好比有些人每天都在學(xué)習(xí)，而另一些人，打打游戲、睡睡大覺，畢業(yè)后前者名企爭著要，后者求職處處無門。
2.7.1事后統(tǒng)計方法 24
2.7.2事前分析估算方法 25
2.8函數(shù)的漸近增長 27
2.9算法時間復(fù)雜度 29
理解大o推導(dǎo)不算難，難的其實是對數(shù)列的一些相關(guān)運算，這考察的更多的是數(shù)學(xué)知識和能力。
2.9.1算法時間復(fù)雜度定義 29
2.9.2推導(dǎo)大o階方法 30
2.9.3常數(shù)階 30
2.9.4線性階 31
2.9.5對數(shù)階 32
2.9.6平方階 32
2.10常見的時間復(fù)雜度 35
有些時候，告訴你某些東西不可以去嘗試，也是一種知識的傳遞�？偛荒芊且ケ欢旧咭б豢诓胖郎卟豢梢匀フ腥前�。
2.11最壞情況與平均情況 35
2.12算法空間復(fù)雜度 36
事先建立一個有2050大的數(shù)組，然后把所有年份按下標數(shù)字對應(yīng)，如果是閏年，此數(shù)組項的值就是1，如果不是就是0。這樣，所謂的判斷某一年是否是閏年就變成了查找這個數(shù)組的某一項的值是多少的問題。
2.13總結(jié)回顧 37
2.14結(jié)尾語 38
愚公移山固然可敬，但發(fā)明炸藥和推土機，可能更加實在和聰明。
第3章線性表 41
3.1開場白 42
門外家長都擠在大門口與門里的小孩子的井然有序，形成了鮮明對比。哎，有時大人的所作所為，其實還不如孩子。
3.2線性表的定義 42
3.3線性表的抽象數(shù)據(jù)類型 45
有時我們想知道某個小朋友（比如麥兜）是否是班級的同學(xué)，老師會告訴我說，沒有，麥兜是在春田花花幼兒園里。這種查找某個元素是否存在的操作很常用。
3.4線性表的順序存儲結(jié)構(gòu) 47
他每次一吃完早飯就沖著去了圖書館，挑一個好地兒，把他書包里的書，一本一本的按座位放好，長長一排，九個座硬是被他占了。
3.4.1順序存儲定義 47
3.4.2順序存儲方式 47
3.4.3數(shù)據(jù)長度與線性表長度區(qū)別 48
3.4.4地址計算方法 49
3.5順序存儲結(jié)構(gòu)的插入與刪除 50
春運時去買火車票，大家都排隊排著好好的，這時來了一個美女：“可否讓我排在你前面？”這可不得了，后面的人像蠕蟲一樣，全部都得退后一步。
3.5.1獲得元素操作 50
3.5.2插入操作 51
3.5.3刪除操作 52
3.5.4線性表順序存儲結(jié)構(gòu)的優(yōu)缺點 54
3.6線性表的鏈式存儲結(jié)構(gòu) 55
反正也是要讓相鄰元素間留有足夠余地，那干脆所有元素都不要考慮相鄰位置了，哪有空位就到哪里。而只是讓每個元素知道它下一個元素的位置在哪里。
3.6.1順序存儲結(jié)構(gòu)不足的解決
辦法 55
3.6.2線性表鏈式存儲結(jié)構(gòu)定義 56
3.6.3頭指針與頭結(jié)點的異同 58
3.6.4線性表鏈式存儲結(jié)構(gòu)代碼描述 58
3.7單鏈表的讀取 60
3.8單鏈表的插入與刪除 61
本來是爸爸左牽著媽媽的手、右牽著寶寶的手在馬路邊散步。突然迎面走來一美女，爸爸失神般地望著，此情景被媽媽逮個正著，于是扯開父子倆，拉起寶寶的左手就快步朝前走去。
3.8.1單鏈表的插入 61
3.8.2單鏈表的刪除 64
3.9單鏈表的整表創(chuàng)建 66
3.10單鏈表的整表刪除 69
3.11單鏈表結(jié)構(gòu)與順序存儲結(jié)構(gòu)優(yōu)缺點 70
3.12靜態(tài)鏈表 71
對于一些語言，如basic、fortran等早期的編程高級語言，由于沒有指針，這鏈表結(jié)構(gòu)，按照前面我們的講法，它就沒法實現(xiàn)了。怎么辦呢？
3.12.1靜態(tài)鏈表的插入操作 73
3.12.2靜態(tài)鏈表的刪除操作 75
3.12.3靜態(tài)鏈表優(yōu)缺點 77
3.13循環(huán)鏈表 78
這個輪回的思想很有意思。它強調(diào)了不管你今生是窮是富，如果持續(xù)行善積德，下輩子就會好過，反之就會遭到報應(yīng)。
3.14雙向鏈表 81
就像每個人的人生一樣，欲收獲就得付代價。雙向鏈表既然是比單鏈表多了如可以反向遍歷查找等的數(shù)據(jù)結(jié)構(gòu)，那么也就需要付出一些小的代價。
3.15總結(jié)回顧 84
3.16結(jié)尾語 85
如果你覺得上學(xué)讀書是受罪，假設(shè)你可以活到80歲，其實你最多也就吃了20年苦。用人生四分之一的時間來換取其余時間的幸福生活，這點苦不算啥。
第4章棧與隊列 87
4.1開場白 88
想想看，在你準備用槍的時候，突然這手槍明明有子彈卻打不出來，這不是要命嗎。
4.2棧的定義 89
類似的很多軟件，比如word、photoshop等，都有撤消（undo）的操作，也是用棧這種思想方式來實現(xiàn)的。
4.2.1棧的定義 89
4.2.2進棧出棧變化形式 90
4.3棧的抽象數(shù)據(jù)類型 91
4.4棧的順序存儲結(jié)構(gòu)及實現(xiàn) 92
4.4.1棧的順序存儲結(jié)構(gòu) 92
4.4.2棧的順序存儲結(jié)構(gòu)進棧操作 93
4.4.3棧的順序存儲結(jié)構(gòu)出棧操作 94
4.5兩棧共享空間 94
兩個大學(xué)室友畢業(yè)同時到北京工作，他們都希望租房時能找到獨自住的一室戶或一室一廳，可找來找去發(fā)現(xiàn)，實在是承受不起。
4.6棧的鏈式存儲結(jié)構(gòu)及實現(xiàn) 97
4.6.1棧的鏈式存儲結(jié)構(gòu) 97
4.6.2棧的鏈式存儲結(jié)構(gòu)進棧操作 98
4.6.3棧的鏈式存儲結(jié)構(gòu)出棧操作 99
4.7棧的作用 100
4.8棧的應(yīng)用——遞歸 100
當你往鏡子前面一站，鏡子里面就有一個你的像。但你試過兩面鏡子一起照嗎？如果a、b兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個“化身”。
4.8.1斐波那契數(shù)列實現(xiàn) 101
4.8.2遞歸定義 103
4.9棧的應(yīng)用——四則運算表達式求值 104
4.9.1后綴（逆波蘭）表示法定義 104
4.9.2后綴表達式計算結(jié)果 106
4.9.3中綴表達式轉(zhuǎn)后綴表達式 108
4.10隊列的定義 111
電腦有時會處于疑似死機的狀態(tài)。就當你失去耐心，打算了reset時。突然它像酒醒了一樣，把你剛才點擊的所有操作全部都按順序執(zhí)行了一遍。
4.11隊列的抽象數(shù)據(jù)類型 112
4.12循環(huán)隊列 113
你上了公交車發(fā)現(xiàn)前排有兩個空座位，而后排所有座位都已經(jīng)坐滿，你會怎么做？立馬下車，并對自己說，后面沒座了，我等下一輛？沒這么笨的人，前面有座位，當然也是可以坐的。
4.12.1隊列順序存儲的不足 112
4.12.2循環(huán)隊列定義 114
4.13隊列的鏈式存儲結(jié)構(gòu)及實現(xiàn) 117
4.13.1隊列鏈式存儲結(jié)構(gòu)入隊操作118
4.13.2隊列鏈式存儲結(jié)構(gòu)出隊操作 119
4.14總結(jié)回顧 120
4.15結(jié)尾語 121
人生，需要有隊列精神的體現(xiàn)。南極到北極，不過是南緯90度到北緯90度的隊列，如果你中途猶豫，臨時轉(zhuǎn)向，也許你就只能和企鵝相伴永遠。可事實上，無論哪個方向，只要你堅持到底，你都可以到達終點。
第5章串 123
5.1開場白 124
“枯眼望遙山隔水，往來曾見幾心知？壺空怕酌一杯酒，筆下難成和韻詩。途路阻人離別久，訊音無雁寄回遲。孤燈夜守長寥寂，夫憶妻兮父憶兒。”……可再仔細一讀發(fā)現(xiàn)，這首詩竟然可以倒過來讀。
5.2串的定義 124
我所提到的“over”、“end”、“lie”其實就是“lover”、“friend”、“believe”這些單詞字符串的子串。
5.3串的比較 126
5.4串的抽象數(shù)據(jù)類型 127
5.5串的存儲結(jié)構(gòu) 128
感情上發(fā)生了問題，為了向女友解釋一下，我準備發(fā)一條短信，一共打了75個字。最后八個字是“我恨你是不可能的”，點發(fā)送。后來得知對方收到的，只有70個字，短信結(jié)尾是“……我恨你”。
5.5.1串的順序存儲結(jié)構(gòu) 129
5.5.2串的鏈式存儲結(jié)構(gòu) 131
5.6樸素的模式匹配算法 131
主串為s=”00000000000000000000000000000000000000000000000001”，而要匹配的子串為t=”0000000001”，……在匹配時，每次都得將t中字符循環(huán)到最后一位才發(fā)現(xiàn)，哦，原來它們是不匹配的。
5.7kmp模式匹配算法 135
很多年前我們的科學(xué)家覺得像這種有多個0和1重復(fù)字符的字符串，卻需要挨個遍歷的算法，是非常糟糕的事情。
5.7.1kmp模式匹配算法原理 135
5.7.2next數(shù)組值推導(dǎo) 139
5.7.3kmp模式匹配算法實現(xiàn) 141
5.7.4kmp模式匹配算法改進 142
5.7.5nextval數(shù)組值推導(dǎo) 144
5.8總結(jié)回顧 146
5.9結(jié)尾語 146
《璇璣圖》共八百四十字，縱橫各二十九字，縱、橫、斜、交互、正、反讀或退一字、迭一字讀均可成詩，詩有三、四、五、六、七言不等，目前有人統(tǒng)計可組成七千九百五十八首詩。聽清楚哦，是7958首。
第6章樹 149
6.1開場白 150
無論多高多大的樹，那也是從小到大的，由根到葉，一點點成長起來的。俗話說十年樹木，百年樹人，可一棵大樹又何止是十年這樣容易。
6.2樹的定義 150
樹的定義其實就是我們在講解棧時提到的遞歸的方法。也就是在樹的定義之中還用到了樹的概念，這是比較新的一種定義方法。
6.2.1結(jié)點分類 152
6.2.2結(jié)點間關(guān)系 152
6.2.3樹的其他相關(guān)概念 153
6.3樹的抽象數(shù)據(jù)類型 154
6.4樹的存儲結(jié)構(gòu) 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二叉樹的性質(zhì) 169
6.6.1二叉樹性質(zhì)1 169
6.6.2二叉樹性質(zhì)2 169
6.6.3二叉樹性質(zhì)3 169
6.6.4二叉樹性質(zhì)4 170
6.6.5二叉樹性質(zhì)5 171
6.7二叉樹的存儲結(jié)構(gòu) 172
6.7.1二叉樹順序存儲結(jié)構(gòu) 172
6.7.2二叉鏈表 173
6.8遍歷二叉樹 174
你人生的道路上，高考填志愿要面臨哪個城市、哪所大學(xué)、具體專業(yè)等選擇，由于選擇方式的不同，遍歷的次序就完全不同。
6.8.1二叉樹遍歷原理 174
6.8.2二叉樹遍歷方法 175
6.8.3前序遍歷算法 178
6.8.4中序遍歷算法 181
6.8.5后序遍歷算法 184
6.8.6推導(dǎo)遍歷結(jié)果 184
6.9二叉樹的建立 187
6.10線索二叉樹 188
我們現(xiàn)在提倡節(jié)約型社會，一切都應(yīng)該節(jié)約為本。對待我們的程序當然也不例外，能不浪費的時間或空間，都應(yīng)該考慮節(jié)省。
6.10.1線索二叉樹原理 188
6.10.2線索二叉樹結(jié)構(gòu)實現(xiàn) 191
6.11樹、森林與二叉樹的轉(zhuǎn)換 195
有個鄉(xiāng)鎮(zhèn)企業(yè)也買了同樣的生產(chǎn)線，老板發(fā)現(xiàn)這個問題后找了個小工來說：你必須搞定，不然炒你魷魚。小工很快想出了辦法：他在生產(chǎn)線旁邊放了臺風扇猛吹，空皂盒自然會被吹走。
6.11.1樹轉(zhuǎn)換為二叉樹 196
6.11.2森林轉(zhuǎn)換為二叉樹 197
6.11.3二叉樹轉(zhuǎn)換為樹 197
6.11.4二叉樹轉(zhuǎn)換為森林 199
6.11.5樹與森林的遍歷 199
6.12赫夫曼樹及其應(yīng)用 200
壓縮而不出錯是如何做到的呢？簡單的說，就是把我們要壓縮的文本進行重新編碼，以達到減少不必要的空間的技術(shù)。壓縮和解壓縮技術(shù)就是基于赫夫曼的研究之上發(fā)展而來，我們應(yīng)該記住他。
6.12.1赫夫曼樹 200
6.12.2赫夫曼樹定義與原理 203
6.12.3赫夫曼編碼 205
6.13總結(jié)回顧 208
6.14結(jié)尾語 209
人受傷時會流下淚水。樹受傷時，天將再不會哭。希望我們的未來不要僅僅是鋼筋水泥建造的高樓，也要有那郁郁蔥蔥的森林和草地，我們?nèi)祟惒趴赡芘c自然和諧共處。
第7章圖 211
7.1開場白 212
如果你不善于規(guī)劃，很有可能就會出現(xiàn)如玩好新疆后到海南，然后再沖向黑龍江這樣的荒唐決策。
7.2圖的定義 213
現(xiàn)實中，人與人之間關(guān)系就非常復(fù)雜，比如我的認識的朋友，可能他們之間也互相認識，這就不是簡單的一對一、一對多的關(guān)系了，那就是我們今天要研究的主題——圖。
7.2.1各種圖定義 214
7.2.2圖的頂點與邊間關(guān)系 217
7.2.3連通圖相關(guān)術(shù)語 219
7.2.4圖的定義與術(shù)語總結(jié) 222
7.3圖的抽象數(shù)據(jù)類型 222
7.4圖的存儲結(jié)構(gòu) 223
因為美國的黑夜就是中國的白天，利用互聯(lián)網(wǎng)，他的員工白天上班就可以監(jiān)控到美國倉庫夜間的實際情況，如果發(fā)生了像火災(zāi)、偷盜這樣的突發(fā)事件，及時電話到美國當?shù)叵嚓P(guān)人員處理
7.4.1鄰接矩陣 224
7.4.2鄰接表 228
7.4.3十字鏈表 232
7.4.4鄰接多重表 234
7.4.5邊集數(shù)組 236
7.5圖的遍歷 237
我有一天早晨準備出門，發(fā)現(xiàn)鑰匙不見了。一定是我兒子拿著玩，不知道丟到哪個犄角旮旯去了，你們說，我應(yīng)該如何找？
7.5.1深度優(yōu)先遍歷 238
7.5.2廣度優(yōu)先遍歷 242
7.6最小生成樹 245
如果你加班加點，沒日沒夜設(shè)計出的結(jié)果是方案一，我想你離被炒魷魚應(yīng)該是不遠了（同學(xué)微笑）。因為這個方案比后兩個方案一半還多的成本會讓老板氣暈過去的。
7.6.1普里姆（prim）算法 247
7.6.2克魯斯卡爾（kruskal）算法 251
7.7最短路徑 257
有人為了省錢，需路程最短，但換乘站間距離長等原因并不省時間；另一些人，他為趕時間，最大的需求是總時間要短；還有一類人，他們都不想多走路，關(guān)鍵是換乘要少，這樣可以在車上好好休息一下。
7.7.1迪杰斯特拉（dijkstra）算法 259
7.7.3弗洛伊德（floyd）算法 265
7.8拓撲排序 270
電影制作不可能在人員到位進駐場地時，導(dǎo)演還沒有找到，也不可能在拍攝過程中，場地都沒有。這都會導(dǎo)致荒謬的結(jié)果。
7.8.1拓撲排序介紹 271
7.8.2拓撲排序算法 272
7.9關(guān)鍵路徑 277
假如造一個輪子要0.5天、造一個發(fā)動機要3天、造一個車底盤要2天、造一個外殼要2天，其它零部件2天，全部零部件集中到一處要0.5天，組裝成車要2天，請問，在汽車廠造一輛車，最短需要多少天呢？
7.9.1關(guān)鍵路徑算法原理 279
7.9.2關(guān)鍵路徑算法 280
7.10總結(jié)回顧 287
7.11結(jié)尾語 289
世界上最遙遠的距離，不是牛a與牛c之間狹小空隙，而是你們當中，有人在通往牛逼的路上一路狂奔，而有人步入大學(xué)校園就學(xué)會放棄。
第8章查找 291
8.1開場白 292
當你精心寫了一篇博文或者上傳一組照片到互聯(lián)網(wǎng)上，來自世界各地的無數(shù)“蜘蛛”便會蜂擁而至。所謂蜘蛛就是搜索引擎公司服務(wù)器上軟件，它把互聯(lián)網(wǎng)當成了蜘蛛網(wǎng)，沒日沒夜的訪問上面的各種信息。
8.2查找概論 293
比如網(wǎng)絡(luò)時代的新名詞，如“蝸居”、“蟻族”等，如果需要將它們收錄到漢語詞典中，顯然收錄時就需要查找它們是否存在，以及找到如果不存在時應(yīng)該收錄的位置。
8.3順序表查找 295
8.3.1順序表查找算法 296
8.3.2順序表查找優(yōu)化 297
8.4有序表查找 298
我在紙上已經(jīng)寫好了一個100以內(nèi)的正整數(shù)請你猜，問幾次可以猜出來。當時已經(jīng)介紹了如何才可以最快的猜出這個數(shù)字。我們把這種每次取中間記錄查找的方法叫做折半查找。
8.4.1折半查找 298
8.4.2插值查找 301
8.4.3斐波那契查找 302
8.5線性索引查找 306
我母親年紀大了，經(jīng)常在家里找不到東西，，于是她用一小本子，記錄了家里所有小東西放置的位置，比如戶口本放在右手床頭柜下面抽屜中，鈔票放在衣……咳，這個就不提了。
8.5.1稠密索引 307
8.5.2分塊索引 308
8.5.3倒排索引 311
8.6二叉排序樹 313
后來老虎來了，一人拼命地跑，另一人則急中生智，爬到了樹上。而老虎是不會爬樹的，結(jié)果……。爬樹者改變了跑的思想，這一改變何等重要，撿回了自己的一條命。
8.6.1二叉排序樹查找操作 316
8.6.2二叉排序樹插入操作 318
8.6.3二叉排序樹刪除操作 320
8.6.4二叉排序樹總結(jié) 327
8.7平衡二叉樹（avl樹） 328
平板就是一個世界，當誘惑降臨，人心中的平衡被打破，世界就會混亂，最后留下的只有孤獨寂寞失敗。這種單調(diào)的機械化的社會，禁不住誘惑的侵蝕，最容易被侵蝕的，恰恰是最空虛的心靈。
8.7.1平衡二叉樹實現(xiàn)原理 330
8.7.2平衡二叉樹實現(xiàn)算法 334
8.8多路查找樹（b樹） 341
要觀察一個公司是否嚴謹，看他們?nèi)绾伍_會就知道了。如果開會時每一個人都只是帶一張嘴，即興發(fā)言，這肯定是一家不嚴謹?shù)墓尽?
8.8.12-3樹 343
8.8.22-3-4樹 348
8.8.3b樹 349
8.8.4b+樹 351
8.9散列表查找（哈希表）概述 353
你很想學(xué)太極拳，聽說學(xué)校有個叫張三豐的人打得特別好，于是到學(xué)校學(xué)生處找人，工作人員拿出學(xué)生名單，最終告訴你，學(xué)校沒這個人，并說張三豐幾百年前就已經(jīng)在武當山作古了。
8.9.1散列表查找定義 354
8.9.2散列表查找步驟 355
8.10散列函數(shù)的構(gòu)造方法 356
8.10.1直接定址法 357
8.10.2數(shù)字分析法 358
8.10.3平方取中法 359
8.10.4折疊法 359
8.10.5除留余數(shù)法 359
8.10.6隨機數(shù)法 360
8.11處理散列沖突的方法 360
我們每個人都希望身體健康，雖然疾病可以預(yù)防，但不可避免，沒有任何人可以說，生下來到現(xiàn)在沒有生過一次病。
8.11.1開放定址法 361
8.11.2再散列函數(shù)法 363
8.11.3鏈地址法 363
8.11.4公共溢出區(qū)法 364
8.12散列表查找實現(xiàn) 365
8.12.1散列表查找算法實現(xiàn) 365
8.12.2散列表查找性能分析 367
8.13總結(jié)回顧 368
8.14結(jié)尾語 369
如果我是個喜歡汽車的人，時常搜汽車信息。那么當我在搜索框中輸入“甲殼蟲”、“美洲虎”等關(guān)鍵詞時，不要讓動物和人物成為搜索的頭條。
第9章排序 373
9.1開場白 374
假如我想買一臺iphone4的手機，于是上了某電子商務(wù)網(wǎng)站去搜索。可搜索后發(fā)現(xiàn)，有8863個相關(guān)的物品，如此之多，這叫我如何選擇。我其實是想買便宜一點的，但是又怕遇到騙子，想找信譽好的商家，如何做？
9.2排序的基本概念與分類 375
比如我們某些大學(xué)為了選拔在主科上更優(yōu)秀的學(xué)生，要求對所有學(xué)生的所有科目總分倒序排名，并且在同樣總分的情況下將語數(shù)外總分做倒序排名。這就是對總分和語數(shù)外總分兩個次關(guān)鍵字的組合排序。
9.2.1排序的穩(wěn)定性 376
9.2.2內(nèi)排序與外排序 377
9.2.3排序用到的結(jié)構(gòu)與函數(shù) 378
9.3冒泡排序 378
無論你學(xué)習(xí)哪種編程語言，在學(xué)到循環(huán)和數(shù)組時，通常都會介紹一種排序算法，而這個算法一般就是冒泡排序。并不是它的名稱很好聽，而是說這個算法的思路最簡單，最容易理解。
9.3.1最簡單排序?qū)崿F(xiàn) 379
9.3.2冒泡排序算法 380
9.3.3冒泡排序優(yōu)化 382
9.3.4冒泡排序復(fù)雜度分析 383
9.4簡單選擇排序 384
還有一種做股票的人，他們很少出手，只是在不斷觀察和判斷，等時機一到，果斷買進或賣出。他們因為冷靜和沉著，以及交易的次數(shù)少，而最終收益頗豐。
9.4.1簡單選擇排序算法 384
9.4.2簡單選擇排序復(fù)雜度分析 385
9.5直接插入排序 386
哪怕你是第一次玩撲克牌，只要認識這些數(shù)字，理牌的方法都是不用教的。將3和4移動到5的左側(cè)，再將2移動到最左側(cè)，順序就算是理好了。這里，我們的理牌方法，就是直接插入排序法。
9.5.1直接插入排序算法 386
9.5.2直接插入排序復(fù)雜度分析 388
9.6希爾排序 389
不管怎么說，希爾排序算法的發(fā)明，使得我們終于突破了慢速排序的時代（超越了時間復(fù)雜度為o(n2)），之后，更為高效的排序算法也就相繼出現(xiàn)了。
9.6.1希爾排序原理 391
9.6.2希爾排序算法 391
9.6.3希爾排序復(fù)雜度分析 395
9.7堆排序 396
什么叫堆結(jié)構(gòu)呢？回憶一下我們小時候，特別是男同學(xué)，基本都玩過疊羅漢的惡作劇。通常都是先把某個要整的人按倒在地，然后大家就一擁而上撲了上去……后果？后果當然就是一笑了之。
9.7.1堆排序算法 398
9.7.2堆排序復(fù)雜度分析 405
9.8歸并排序 406
即使你是你們班級第一、甚至年級第一名，如果你沒有上分數(shù)線，則說明你的成績排不到全省前1萬名，你也就基本失去了當年上本科的機會了。
9.8.1歸并排序算法 407
9.8.2歸并排序復(fù)雜度分析 413
9.8.3非遞歸實現(xiàn)歸并排序 413
9.9快速排序 417
終于我們的高手要登場了，將來你工作后，你的老板讓你寫個排序算法，而你會的算法中竟然沒有快速排序，我想你還是不要聲張，偷偷去把快速排序算法找來敲進電腦，這樣至少你不至于被大伙兒取笑。
9.9.1快速排序算法 417
9.9.2快速排序復(fù)雜度分析 421
9.9.3快速排序優(yōu)化 422
9.10總結(jié)回顧 428
目前還沒有十全十美的排序算法，有優(yōu)點就會有缺點，即使是快速排序法，也只是在整體性能上優(yōu)越，它也存在排序不穩(wěn)定、需要大量輔助空間、對少量數(shù)據(jù)排序無優(yōu)勢等不足。
9.11結(jié)尾語 430
如果你有夢想的話，就要去捍衛(wèi)它。當別人做不到的時候，他們就想要告訴你，你也不能。如果你想要些什么，就得去努力爭取。就這樣！
附錄參考文獻 435