大話數(shù)據(jù)結(jié)構(gòu)

前言

前 言本書起因大家好！我是《大話設(shè)計(jì)模式》（2008年初出版）的作者，三年來，承蒙廣大讀者的厚愛，《大話設(shè)計(jì)模式》取得了較大的成功。僅在當(dāng)當(dāng)網(wǎng)，截止本文寫作時(shí)，就已經(jīng)有1073次評(píng)論，705次5星評(píng)價(jià)，位居五星圖書榜計(jì)算機(jī)/網(wǎng)絡(luò)類的累計(jì)總榜第二名。此書已經(jīng)成為國內(nèi)原創(chuàng)計(jì)算機(jī)類圖書最暢銷的書籍之一。對(duì)于這樣一個(gè)自己喜歡做、可以做得好，而且已經(jīng)得到了市場廣泛認(rèn)可，為很多朋友提供幫助的事情，我沒有理由不去繼續(xù)做下去。這就是我準(zhǔn)備再寫書的原因。我曾做過調(diào)查，數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)者大多都有這樣的感慨：數(shù)據(jù)結(jié)構(gòu)很重要，一定要學(xué)好，但數(shù)據(jù)結(jié)構(gòu)比較抽象，有些算法理解起來很困難，學(xué)得很累?？晌腋Ｍ麄鬟_(dá)這樣的信息：數(shù)據(jù)結(jié)構(gòu)非常有趣，很多算法是智慧的結(jié)晶，學(xué)習(xí)它是去感受計(jì)算機(jī)編程技術(shù)的魅力，在理解掌握它的同時(shí)，整個(gè)過程都是一種愉悅的精神感受，而非枯燥乏味的一門課程。因此我決定寫作一本關(guān)于數(shù)據(jù)結(jié)構(gòu)有趣的書。不過現(xiàn)實(shí)總比理想來得更“現(xiàn)實(shí)”。要想把書寫好，談何容易，我需要突破很多困難……嗐！不管如何，現(xiàn)在您看到了本書，那就說明我已經(jīng)克服了困難戰(zhàn)勝了自己。希望您可以喜歡上這本書。本書定位本書的定位就是一本適合讀者自學(xué)數(shù)據(jù)結(jié)構(gòu)的書籍，它有區(qū)別于教材，希望給大家另一種閱讀體驗(yàn)。通常講解數(shù)據(jù)結(jié)構(gòu)的圖書都是以教材的方式呈現(xiàn)。在寫作前，我購買或在圖書館借閱了十幾本非常好的數(shù)據(jù)結(jié)構(gòu)相關(guān)教材用來為寫作本書做準(zhǔn)備。但經(jīng)過認(rèn)真閱讀后，我發(fā)現(xiàn)，它們大多不是一本好的“自學(xué)讀物”。我沒有輕視這些好書的意思，不過教材和自學(xué)讀物，所面向的讀者是完全不同的。好的教材應(yīng)該是提綱挈領(lǐng)、重點(diǎn)突出，一定要留出思考的空間，否則就沒必要再聽老師上課了。很多內(nèi)容的講解是由老師在課堂完成，教材中有練習(xí)、課后習(xí)題、思考題等，這些大多可以通過老師來解答。比如我們中學(xué)時(shí)的語文、數(shù)學(xué)課本，很薄的一本書通常要用一學(xué)期、甚至一年的時(shí)間來學(xué)習(xí)，這就是因?yàn)樗鼈兪墙滩亩皇亲詫W(xué)讀物。如果是小說，可能一兩天就讀完了。好的自學(xué)讀物的目標(biāo)是讓初學(xué)者“獨(dú)自”全盤掌握知識(shí)，需要強(qiáng)調(diào)“獨(dú)自”一詞，這就說明讀者在閱讀時(shí)，是完全依靠自己的力量來向未知發(fā)出挑戰(zhàn)。因此書中內(nèi)容，要么不寫，寫了就應(yīng)該寫透。如果讀者在閱讀時(shí)總是疑惑重重，那么這本書就有很大的問題了。我也就是在基于這樣的認(rèn)識(shí)，決心將《大話數(shù)據(jù)結(jié)構(gòu)》真正寫成一本關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的自學(xué)讀物來展開寫作的。本書特色1．趣味引導(dǎo)大部分的編程類圖書，在內(nèi)容上基本都是直奔主題。但是尼采曾說過：“人們無法理解他沒有經(jīng)歷過的事情?！睋Q句話說，我們只接受過去早已理解的事物相關(guān)的信息。這是一種比較學(xué)習(xí)過程，在這個(gè)過程中，大腦尋找每條信息之間的聯(lián)系。所以教育專家普遍認(rèn)為，吸引學(xué)生的注意力，比較好的辦法是用他們比較熟知的知識(shí)開始。因此在本書中，我會(huì)用一個(gè)故事、一個(gè)趣味題目、一部電影的介紹等形式來作為每一章甚至很多小節(jié)的開頭，選擇的內(nèi)容也多多少少與要講的主題內(nèi)容相關(guān)。這并不是多余，而是有意為之。事實(shí)上，這樣的形式在我的前一本書中已經(jīng)得到了普遍認(rèn)可。2．圖文并茂西方有句諺語，“A picture is worth a thousand words.（一圖值千言）”。用上千個(gè)字描述不明白的東西，很可能一張圖就能解釋清楚。我非常認(rèn)可這個(gè)觀點(diǎn)，所以本書雖沒有達(dá)到每一頁都有圖，但基本做到了絕大部分講解都有相關(guān)圖示，關(guān)鍵算法更是通過多圖逐步分解剖析。盡管這帶來了寫作上的難度，但卻可以達(dá)到較好的效果。畢竟，讀者通過本書開始學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，要從一無所知或略知一二到完全理解，甚至掌握應(yīng)用，是需要一個(gè)比較艱苦的過程，用大量的圖示可以減少這個(gè)過程的長度。3．代碼詳解我在寫作中盡量摒棄了傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)教材的“重理論思想而輕代碼講解”的作法。在準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)寫作時(shí)我發(fā)現(xiàn)，很多教材對(duì)數(shù)據(jù)結(jié)構(gòu)理論和算法設(shè)計(jì)思想講得比較好，可一到實(shí)際代碼時(shí)，有的把代碼貼出來加少量注釋，有的直接用偽代碼形式。這對(duì)于上課的學(xué)生還好，畢竟有老師在課堂中去詳解代碼編寫原理，可是對(duì)于初學(xué)數(shù)據(jù)結(jié)構(gòu)和算法的自學(xué)者而言，如果書中不去解釋代碼某些細(xì)節(jié)為什么那樣編寫的原因，甚至代碼根本不可能在某個(gè)編譯器中運(yùn)行通過，其挫折感是很強(qiáng)烈的。比如即使理解了圖結(jié)構(gòu)中的最短路徑求解原理，也可能無法寫出最短路徑的算法。我把代碼在運(yùn)行過程中變量的變化融入到整個(gè)算法設(shè)計(jì)思想的講解中，配合相應(yīng)的示意圖，會(huì)幫助大家更加容易理解算法的實(shí)質(zhì)。這種講解模式在本書的第6、7、8、9章的很多復(fù)雜算法中有具體體現(xiàn)，越是復(fù)雜的代碼越是講解細(xì)致。這算是本書的一個(gè)特色，希望對(duì)讀者有幫助。4．形式新穎我把本書的內(nèi)容虛構(gòu)成了一個(gè)老師上課的場景，所有內(nèi)容都通過這位老師表達(dá)出來，書中的文字非?？谡Z化，這樣做的目的是為了更加直觀地讓讀者感覺，自己是在學(xué)習(xí)，是在上課。有人可能會(huì)說，現(xiàn)在的課堂大都是讓人昏昏欲睡，把讀者帶入上課場景，不是更加讓讀者犯困嗎？我覺得如果你的學(xué)習(xí)經(jīng)歷中聽過一些優(yōu)秀老師的課，你就不會(huì)下這樣的結(jié)論。好的老師講課，是可以做到引人入勝的。有人可能會(huì)問，我為什么不用《大話設(shè)計(jì)模式》中的對(duì)話形式，而采用講課形式呢？這是對(duì)數(shù)據(jù)結(jié)構(gòu)這門學(xué)問的特點(diǎn)考慮的。設(shè)計(jì)模式主要都是思想體現(xiàn)，通常會(huì)仁者見仁、智者見智，用對(duì)話展開比較容易；而數(shù)據(jù)結(jié)構(gòu)中更多的是定義、術(shù)語、經(jīng)典算法等，這些公認(rèn)的知識(shí)，可討論的地方并不多，更多的是需要把它講清楚。讓兩個(gè)人在一起討論某個(gè)設(shè)計(jì)模式的優(yōu)缺點(diǎn)，會(huì)非常合適，而討論數(shù)據(jù)結(jié)構(gòu)定義的好壞，就沒有太大意義了，不如讓一個(gè)老師告訴學(xué)生數(shù)據(jù)結(jié)構(gòu)的定義好在哪里更符合實(shí)際。因此用傳統(tǒng)的講課形式會(huì)好一些。另外，本書沒有習(xí)題，有思考的題目也一定會(huì)給出某種答案。但本書每個(gè)復(fù)雜知識(shí)點(diǎn)的末尾，都會(huì)提供另一本書的進(jìn)一步閱讀建議。這也是基于它是一本自學(xué)讀物的原則。讀者閱讀本書可能是任何時(shí)間任何地方，如果書中存在沒有解答的習(xí)題，碰到了困難是沒法及時(shí)找到老師來幫助的，因此本書盡量避免讓讀者有這樣的困惑存在。如果需要練習(xí)的同學(xué)，我覺得還是應(yīng)該考慮再去買本習(xí)題集來學(xué)習(xí)。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，做題和上機(jī)寫代碼非常有必要，從這個(gè)角度也說明，閱讀完本書其實(shí)也只是完成入門而已。本書既然是以老師上課的形式來進(jìn)行，那就免不了要融入一名教師除了授業(yè)解惑以外，還要傳達(dá)一些個(gè)人價(jià)值觀的體現(xiàn)。書中很多細(xì)微處，如對(duì)某位科學(xué)家的尊敬、對(duì)某個(gè)算法的推崇、對(duì)勤奮勵(lì)志故事的講述等都在表達(dá)著一個(gè)老師向?qū)W生傳遞真、善、美的意愿。我始終認(rèn)為，讀者拿到的雖然只是一本沒有表情、不會(huì)說話的書，但其實(shí)也是在隔空與另一個(gè)朋友交流。人與人的交流不可能只是就事論事，一定會(huì)有情感的溝通，這種情感如果能產(chǎn)生共鳴、達(dá)成互信，就會(huì)讓事情（比如學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法這件事）本身更容易理解和接受。本書內(nèi)容本書主要是按照教育部關(guān)于計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程大綱的要求略微增減來組織內(nèi)容的。主要包括：數(shù)據(jù)結(jié)構(gòu)介紹，算法推導(dǎo)大O階的方法，線性表結(jié)構(gòu)的介紹，順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)差異，棧與隊(duì)列的應(yīng)用，串的樸素模式匹配、KMP模式匹配算法，樹結(jié)構(gòu)的介紹，二叉樹前中后序遍歷，線索二叉樹，赫夫曼樹及應(yīng)用，圖結(jié)構(gòu)的介紹，圖的深度、廣度遍歷，最小生成樹兩種算法，最短路徑兩種算法，拓?fù)渑判蚺c關(guān)鍵路徑算法，查找應(yīng)用的相關(guān)介紹，折半查找、插值查找、斐波那契查找等靜態(tài)查找，稠密索引、分塊索引、倒排索引等索引技術(shù)，二叉排序樹、平衡二叉樹等動(dòng)態(tài)查找，B樹、B+樹技術(shù)，散列表技術(shù)，排序應(yīng)用的相關(guān)介紹，冒泡、選擇、插入等簡單排序，希爾、堆、歸并、快速等改進(jìn)排序，各位排序算法的對(duì)比等。本書讀者數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)軟件相關(guān)專業(yè)的基礎(chǔ)課程，幾乎可以說，要想從事編程工作，無論你是否是科班出身，都不可以繞過這部分知識(shí)。因此，適合閱讀本書的讀者非常廣泛，包括在讀的本?？?、中專職高技校等計(jì)算機(jī)專業(yè)學(xué)生、想轉(zhuǎn)行做開發(fā)的非專業(yè)人員、欲考計(jì)算機(jī)研究生的應(yīng)屆或在職人員，以及工作后需要補(bǔ)學(xué)或溫習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的程序員等各類讀者。本書對(duì)讀者的技術(shù)背影要求比較低，只要是學(xué)過一門高級(jí)編程語言，例如C、C++、Java、C#、VB等就可以開始閱讀本書。不過由于當(dāng)中涉及到比較復(fù)雜的算法知識(shí)，需要讀者有一定的數(shù)學(xué)修養(yǎng)和邏輯思維能力，否則可能書籍的后半部分閱讀起來會(huì)比較吃力。本書研讀方法事實(shí)上，任何有難度的知識(shí)和技巧，都不是那么容易被掌握的。我盡管已經(jīng)朝著通俗易懂的方向努力，可有些數(shù)據(jù)結(jié)構(gòu)，特別是經(jīng)典算法，是幾代科學(xué)家的智慧結(jié)晶，因此要掌握它們還是需要讀者的全力投入。美國暢銷書《如何閱讀一本書》中提到“閱讀可以是一件主動(dòng)的事，閱讀越主動(dòng)，效果越好。拿同樣的書給背景相近的兩個(gè)人閱讀，一個(gè)人卻比另一個(gè)人從書中得到了更多，這是因?yàn)椋紫仍谟谶@人的主動(dòng)，其次，在于他在閱讀中的每一種活動(dòng)都參與了更多的技巧。這兩件事是息息相關(guān)的。閱讀是一個(gè)復(fù)雜的活動(dòng)，就跟寫作一樣，包含了大量不同的活動(dòng)。要達(dá)成良好的閱讀，這些活動(dòng)都是不可或缺的。一個(gè)人越能良好運(yùn)作這些活動(dòng)，閱讀的效果也就越好?！蔽耶?dāng)然希望讀者在閱讀本書后收獲巨大，但這顯然是一廂情愿。要想獲得更多，您可能也需要付出類似我寫作一樣的力氣來閱讀，例如摘抄文字、眉批心得、稿紙演算、代碼輸入電腦，以及您自己在編程工作中的運(yùn)用等。這些相應(yīng)活動(dòng)的執(zhí)行，將會(huì)使您得到巨大的收獲。作為作者，建議本書的研讀方法為：1．復(fù)習(xí)C語言的基礎(chǔ)知識(shí)。如果你掌握的是別的語言也不要緊，適當(dāng)了解一些C語言和你掌握的編程語言的語法差異還是有必要的。甚至將本書代碼改造成另一種語言本身就是一種非常好的學(xué)習(xí)方法。2．閱讀第一遍時(shí)，建議從頭至尾進(jìn)行。如果你對(duì)前面的知識(shí)有足夠了解，當(dāng)然可以跳過直接閱讀后面的章節(jié)。不過若要學(xué)習(xí)一門完整的知識(shí)并形成體系。通讀本書，還是最好的學(xué)習(xí)方法。3．閱讀時(shí)，摘抄是非常好的習(xí)慣?！白畹哪矂儆谧顝?qiáng)的記憶！”有不少讀者會(huì)認(rèn)為摘抄了將來也不會(huì)再去看，有什么必要，但其實(shí)在寫字的過程就是大腦學(xué)習(xí)的過程，寫字在減緩你閱讀的速度，從而讓你更好地消化閱讀的內(nèi)容。相信大家都能理解，“囫圇吞棗”和“慢慢品味”的差異，學(xué)習(xí)同樣如此。4．閱讀每一章時(shí)，特別是在閱讀算法的推導(dǎo)過程時(shí)，一定要在電腦中運(yùn)行代碼（本書源碼的下載地址可以到http://cj723.cnblogs.com中的《大話數(shù)據(jù)結(jié)構(gòu)相關(guān)主題》中找到），了解代碼的運(yùn)行過程。本書的很多算法都做到了逐行講解，但單純閱讀可能真的很難達(dá)到理解的程度（這是紙質(zhì)書無法克服的缺陷），需要你通過開發(fā)工具調(diào)試，并設(shè)置斷點(diǎn)和逐行執(zhí)行，并參照書中的講解，觀察變量的變化情況來理解算法的編寫原理。5．閱讀完每一章時(shí)，一定要在理解基礎(chǔ)上記憶一些關(guān)鍵東西。最佳的效果就是你可以不看書也做到一點(diǎn)不錯(cuò)地默寫出相關(guān)算法。6．閱讀完每一章時(shí)，一定要適當(dāng)練習(xí)。本書沒有提供練習(xí)題，但市場上相關(guān)的數(shù)據(jù)結(jié)構(gòu)習(xí)題集比比皆是，可以選擇嘗試。另外互聯(lián)網(wǎng)上也可以獲得足夠的習(xí)題來給你練習(xí)。練習(xí)的目的是為了檢測自己是否真的完全理解了書中的內(nèi)容。事實(shí)上很多時(shí)候，閱讀中的人們只是自我感覺理解，而并非真正的明白。7．學(xué)習(xí)不可能一蹴而就，數(shù)據(jù)結(jié)構(gòu)和算法如果通過一本書就可以掌握，那本身就是笑話。本書附錄提供了本書寫作時(shí)的參考書目，基本都是最優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)或相關(guān)的中文書籍各有側(cè)重，建議大家可以適當(dāng)?shù)亻喿x。8．在之后的編程學(xué)習(xí)和工作中，盡量把已經(jīng)學(xué)到的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)運(yùn)用到現(xiàn)實(shí)開發(fā)中。遺忘時(shí)翻閱本書回顧相關(guān)內(nèi)容，最終達(dá)到精通數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的境界。編程語言說明本書是用C語言編寫，基于C90（ISO C）的標(biāo)準(zhǔn)。讀者可以選擇任何一款基于C90標(biāo)準(zhǔn)的C語言開發(fā)工具或更高版本的開發(fā)工具來學(xué)習(xí)本書中的代碼。本人一直習(xí)慣于用Visual Studio 2008作為開發(fā)工具，因此在寫作此書時(shí)，也是用此工具的Visual C++來編譯調(diào)試代碼，一切都相安無事，但寫作完成后，考慮到不同讀者應(yīng)用開發(fā)工具的習(xí)慣不同，最終在編輯的建議下，決定提供一份可在C90標(biāo)準(zhǔn)的C語言開發(fā)環(huán)境中編譯通過的代碼，結(jié)果發(fā)現(xiàn)錯(cuò)誤百出。例如C90標(biāo)準(zhǔn)的注釋要求是“/* 注釋文字 */”而不允許是“//注釋文字”：要求變量聲明必須要在函數(shù)的最前面，只能是“int i; for(i=0;i

內(nèi)容概要

　　本書為超級(jí)暢銷書《大話設(shè)計(jì)模式》作者程杰潛心三年推出的扛鼎之作！以一個(gè)計(jì)算機(jī)教師教學(xué)為場景，講解數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的知識(shí)。通篇以一種趣味方式來敘述，大量引用了各種各樣的生活知識(shí)來類比，并充分運(yùn)用圖形語言來體現(xiàn)抽象內(nèi)容，對(duì)數(shù)據(jù)結(jié)構(gòu)所涉及到的一些經(jīng)典算法做到逐行分析、多算法比較。與市場上的同類數(shù)據(jù)結(jié)構(gòu)圖書相比，本書內(nèi)容趣味易讀，算法講解細(xì)致深刻，是一本非常適合自學(xué)的讀物。
　　本書以一個(gè)計(jì)算機(jī)教師教學(xué)為場景，講解數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的知識(shí)。通篇以一種趣味方式來敘述，大量引用了各種各樣的生活知識(shí)來類比，并充分運(yùn)用圖形語言來體現(xiàn)抽象內(nèi)容，對(duì)數(shù)據(jù)結(jié)構(gòu)所涉及到的一些經(jīng)典算法做到逐行分析、多算法比較。與市場上的同類數(shù)據(jù)結(jié)構(gòu)圖書相比，本書內(nèi)容趣味易讀，算法講解細(xì)致深刻，是一本非常適合自學(xué)的讀物。
　　本書主要內(nèi)容包含：數(shù)據(jù)結(jié)構(gòu)介紹、算法推導(dǎo)大O階的方法；順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)差異、棧與隊(duì)列的應(yīng)用；串的樸素模式匹配、KMP模式匹配算法；二叉樹前中后序遍歷、赫夫曼樹及應(yīng)用；圖的深度、廣度遍歷；最小生成樹兩種算法、最短路徑兩種算法；拓?fù)渑判蚺c關(guān)鍵路徑算法；折半查找、插值查找、斐波那契查找等靜態(tài)查找；稠密索引、分塊索引、倒排索引等索引技術(shù)；二叉排序樹、平衡二叉樹等動(dòng)態(tài)查找；B樹、B+樹技術(shù)，散列表技術(shù)；冒泡、選擇、插入等簡單排序；希爾、堆、歸并、快速等改進(jìn)排序……
本書適合學(xué)過一門編程語言的各類讀者，包括在讀的大中專計(jì)算機(jī)專業(yè)學(xué)生、想轉(zhuǎn)行做開發(fā)的非專業(yè)人員、欲考計(jì)算機(jī)研究生的應(yīng)屆或在職人員，以及工作后需要補(bǔ)學(xué)或溫習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的程序員等

作者簡介

　　一個(gè)被讀者譽(yù)為很適合寫IT技術(shù)書的家伙?！洞笤捲O(shè)計(jì)模式》作者。此書07年末出版至今已經(jīng)簡體版印刷9次、繁體版印刷6次，取得了較好的成績，開創(chuàng)了一種適合國人閱讀的趣味講解IT知識(shí)的風(fēng)格模式。其本人參與過政府、證券、游戲、交通等多種行業(yè)的軟件開發(fā)及項(xiàng)目管理工作，也曾做過軟件培訓(xùn)的教師。因曾有過兩年半高中數(shù)學(xué)教學(xué)的獨(dú)特經(jīng)歷，使得其書作當(dāng)中處處以初學(xué)者視角考慮和分析問題，他成為了當(dāng)前很受歡迎的IT技術(shù)圖書作者之一。

書籍目錄

第1章 數(shù)據(jù)結(jié)構(gòu)緒論
　1.1 開 場 白
　1.2 你數(shù)據(jù)結(jié)構(gòu)怎么學(xué)的？
　1.3 數(shù)據(jù)結(jié)構(gòu)起源
　1.4 基本概念和術(shù)語
　　1.4.1 數(shù)據(jù)
　　1.4.2 數(shù)據(jù)元素
　　1.4.3 數(shù)據(jù)項(xiàng)
　　1.4.4 數(shù)據(jù)對(duì)象
　　1.4.5 數(shù)據(jù)結(jié)構(gòu)
　1.5 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
　　1.5.1 邏輯結(jié)構(gòu)
　　1.5.2 物理結(jié)構(gòu)
　1.6 抽象數(shù)據(jù)類型
　　1.6.1 數(shù)據(jù)類型
　　1.6.2 抽象數(shù)據(jù)類型
　1.7 總結(jié)回顧
　1.8 結(jié) 尾 語
第2章 算法
　2.1 開 場 白
　2.2 數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系
　2.3 兩種算法的比較
　2.4 算法定義
　2.5 算法的特性
　　2.5.1 輸入輸出
　　2.5.2 有窮性
　　2.5.3 確定性
　　2.5.4 可行性
　2.6 算法設(shè)計(jì)的要求
　　2.6.1 正確性
　　2.6.2 可讀性
　　2.6.3 健壯性
　　2.6.4 時(shí)間效率高和存儲(chǔ)量低
　2.7 算法效率的度量方法
　　2.7.1 事后統(tǒng)計(jì)方法
　　2.7.2 事前分析估算方法
　2.8 函數(shù)的漸近增長
　2.9 算法時(shí)間復(fù)雜度
　　2.9.1 算法時(shí)間復(fù)雜度定義
　　2.9.2 推導(dǎo)大O階方法
　　2.9.3 常數(shù)階
　　2.9.4 線性階
　　2.9.5 對(duì)數(shù)階
　　2.9.6 平方階
　2.10 常見的時(shí)間復(fù)雜度
　2.11 最壞情況與平均情況
　2.12 算法空間復(fù)雜度
　2.13 總結(jié)回顧
　2.14 結(jié) 尾 語
第3章 線性表
　3.1 開 場 白
　3.2 線性表的定義
　3.3 線性表的抽象數(shù)據(jù)類型
　3.4 線性表的順序存儲(chǔ)結(jié)構(gòu)
　　3.4.1 順序存儲(chǔ)定義
　　3.4.2 順序存儲(chǔ)方式
　　3.4.3 數(shù)據(jù)長度與線性表長度區(qū)別
　　3.4.4 地址計(jì)算方法
　3.5 順序存儲(chǔ)結(jié)構(gòu)的插入與刪除
　　3.5.1 獲得元素操作
　　3.5.2 插入操作
　　3.5.3 刪除操作
　　3.5.4 線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)
　3.6 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
　　3.6.1 順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法
　　3.6.2 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義
　　3.6.3 頭指針與頭結(jié)點(diǎn)的異同
　　3.6.4 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼描述
　3.7 單鏈表的讀取
　3.8 單鏈表的插入與刪除
　　3.8.1 單鏈表的插入
　　3.8.2 單鏈表的刪除
　3.9 單鏈表的整表創(chuàng)建
　3.10 單鏈表的整表刪除
　3.11 單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)
　3.12 靜態(tài)鏈表
　　3.12.1 靜態(tài)鏈表的插入操作
　　3.12.2 靜態(tài)鏈表的刪除操作
　　3.12.3 靜態(tài)鏈表優(yōu)缺點(diǎn)
　3.13 循環(huán)鏈表
　3.14 雙向鏈表
　3.15 總結(jié)回顧
　3.16 結(jié) 尾 語
第4章 棧與隊(duì)列
　4.1 開 場 白
　4.2 棧的定義
　　4.2.1 棧的定義
　　4.2.2 進(jìn)棧出棧變化形式
　4.3 棧的抽象數(shù)據(jù)類型
　4.4 棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
　　4.4.1 棧的順序存儲(chǔ)結(jié)構(gòu)
　　4.4.2 棧的順序存儲(chǔ)結(jié)構(gòu)進(jìn)棧操作
　　4.4.3 棧的順序存儲(chǔ)結(jié)構(gòu)出棧操作
　4.5 兩棧共享空間
　4.6 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
　　4.6.1 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
　　4.6.2 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)棧操作
　　4.6.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)出棧操作
　4.7 棧的作用
　4.8 棧的應(yīng)用——遞歸
　　4.8.1 斐波那契數(shù)列實(shí)現(xiàn)
　　4.8.2 遞歸定義
　4.9 棧的應(yīng)用——四則運(yùn)算表達(dá)式求值
　　4.9.1 后綴（逆波蘭）表示法定義
　　4.9.2 后綴表達(dá)式計(jì)算結(jié)果
　　4.9.3 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
　4.10 隊(duì)列的定義
　4.11 隊(duì)列的抽象數(shù)據(jù)類型
　4.12 循環(huán)隊(duì)列
　　4.12.1 隊(duì)列順序存儲(chǔ)的不足
　　4.12.2 循環(huán)隊(duì)列定義
　4.13 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
　　4.13.1 隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)入隊(duì)操作
　　4.13.2 隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)出隊(duì)操作
　4.14 總結(jié)回顧
　4.15 結(jié) 尾 語
第5章 串
　5.1開場白
　5.2 串的定義
　5.3 串的比較
　5.4 串的抽象數(shù)據(jù)類型
　5.5 串的存儲(chǔ)結(jié)構(gòu)
　　5.5.1 串的順序存儲(chǔ)結(jié)構(gòu)
　　5.5.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
　5.6 樸素的模式匹配算法
　5.7 KMP模式匹配算法
　　5.7.1 KMP模式匹配算法原理
　　5.7.2 next數(shù)組值推導(dǎo)
　　5.7.3 KMP模式匹配算法實(shí)現(xiàn)
　　5.7.4 KMP模式匹配算法改進(jìn)
　　5.7.5 nextval數(shù)組值推導(dǎo)
　5.8 總結(jié)回顧
　5.9 結(jié) 尾 語
第6章 樹
　6.1 開 場 白
　6.2 樹的定義
　　6.2.1 結(jié)點(diǎn)分類
　　6.2.2 結(jié)點(diǎn)間關(guān)系
　　6.2.3 樹的其他相關(guān)概念
　6.3 樹的抽象數(shù)據(jù)類型
　6.4 樹的存儲(chǔ)結(jié)構(gòu)
　　6.4.1 雙親表示法
　　6.4.2 孩子表示法
　　6.4.3 孩子兄弟表示法
　6.5 二叉樹的定義
　　6.5.1 二叉樹特點(diǎn)
　　6.5.2 特殊二叉樹
　6.6 二叉樹的性質(zhì)
　　6.6.1 二叉樹性質(zhì)1
　　6.6.2 二叉樹性質(zhì)2
　　6.6.3 二叉樹性質(zhì)3
　　6.6.4 二叉樹性質(zhì)4
　　6.6.5 二叉樹性質(zhì)5
　6.7 二叉樹的存儲(chǔ)結(jié)構(gòu)
　　6.7.1 二叉樹順序存儲(chǔ)結(jié)構(gòu)
　　6.7.2 二叉鏈表
　6.8 遍歷二叉樹
　　6.8.1 二叉樹遍歷原理
　　6.8.2 二叉樹遍歷方法
　　6.8.3 前序遍歷算法
　　6.8.4 中序遍歷算法
　　6.8.5 后序遍歷算法
　　6.8.6 推導(dǎo)遍歷結(jié)果
　6.9 二叉樹的建立
　6.10 線索二叉樹
　　6.10.1 線索二叉樹原理
　　6.10.2 線索二叉樹結(jié)構(gòu)實(shí)現(xiàn)
　6.11 樹、森林與二叉樹的轉(zhuǎn)換
　　6.11.1 樹轉(zhuǎn)換為二叉樹
　　6.11.2 森林轉(zhuǎn)換為二叉樹
　　6.11.3 二叉樹轉(zhuǎn)換為樹
　　6.11.4 二叉樹轉(zhuǎn)換為森林
　　6.11.5 樹與森林的遍歷
　6.12 赫夫曼樹及其應(yīng)用
　　6.12.1 赫夫曼樹
　　6.12.2 赫夫曼樹定義與原理
　　6.12.3 赫夫曼編碼
　6.13 總結(jié)回顧
　6.14 結(jié) 尾 語
第7章 圖
　7.1 開 場 白
　7.2 圖的定義
　　7.2.1 各種圖定義
　　7.2.2 圖的頂點(diǎn)與邊間關(guān)系
　　7.2.3 連通圖相關(guān)術(shù)語
　　7.2.4 圖的定義與術(shù)語總結(jié)
　7.3 圖的抽象數(shù)據(jù)類型
　7.4 圖的存儲(chǔ)結(jié)構(gòu)
　　7.4.1 鄰接矩陣
　　7.4.2 鄰接表
　　7.4.3 十字鏈表
　　7.4.4 鄰接多重表
　　7.4.5 邊集數(shù)組
　7.5 圖的遍歷
　　7.5.1 深度優(yōu)先遍歷
　　7.5.2 廣度優(yōu)先遍歷
　7.6 最小生成樹
　　7.6.1 普里姆（Prim）算法
　　7.6.2 克魯斯卡爾（Kruskal）算法
　7.7 最短路徑
　　7.7.1 迪杰斯特拉（Dijkstra）算法
　　7.7.2 弗洛伊德（Floyd）算法
　7.8 拓?fù)渑判?br />　　7.8.1 拓?fù)渑判蚪榻B
　　7.8.2 拓?fù)渑判蛩惴?br />　7.9 關(guān)鍵路徑
　　7.9.1 關(guān)鍵路徑算法原理
　　7.9.2 關(guān)鍵路徑算法
　7.10 總結(jié)回顧
　7.11 結(jié) 尾 語
第8章 查找
　8.1 開 場 白
　8.2 查找概論
　8.3 順序表查找
　　8.3.1 順序表查找算法
　　8.3.2 順序表查找優(yōu)化
　8.4 有序表查找
　　8.4.1 折半查找
　　8.4.2 插值查找
　　8.4.3 斐波那契查找
　8.5 線性索引查找
　　8.5.1 稠密索引
　　8.5.2 分塊索引
　　8.5.3 倒排索引
　8.6 二叉排序樹
　　8.6.1 二叉排序樹查找操作
　　8.6.2 二叉排序樹插入操作
　　8.6.3 二叉排序樹刪除操作
　　8.6.4 二叉排序樹總結(jié)
　8.7 平衡二叉樹（AVL樹）
　　8.7.1 平衡二叉樹實(shí)現(xiàn)原理
　　8.7.2 平衡二叉樹實(shí)現(xiàn)算法
　8.8 多路查找樹（B樹）
　　8.8.1 2-3樹
　　8.8.2 2-3-4樹
　　8.8.3 B樹
　　8.8.4 B+樹
　8.9 散列表查找（哈希表）概述
　　8.9.1 散列表查找定義
　　8.9.2 散列表查找步驟
　8.10 散列函數(shù)的構(gòu)造方法
　　8.10.1 直接定址法
　　8.10.2 數(shù)字分析法
　　8.10.3 平方取中法
　　8.10.4 折疊法
　　8.10.5 除留余數(shù)法
　　8.10.6 隨機(jī)數(shù)法
　8.11 處理散列沖突的方法
　　8.11.1 開放定址法
　　8.11.2 再散列函數(shù)法
　　8.11.3 鏈地址法
　　8.11.4 公共溢出區(qū)法
　8.12 散列表查找實(shí)現(xiàn)
　　8.12.1 散列表查找算法實(shí)現(xiàn)
　　8.12.2 散列表查找性能分析
　8.13 總結(jié)回顧
　8.14 結(jié) 尾 語
第9章 排序
　9.1 開 場 白
　9.2 排序的基本概念與分類
　　9.2.1 排序的穩(wěn)定性
　　9.2.2 內(nèi)排序與外排序
　　9.2.3 排序用到的結(jié)構(gòu)與函數(shù)
　9.3 冒泡排序
　　9.3.1 最簡單排序?qū)崿F(xiàn)
　　9.3.2 冒泡排序算法
　　9.3.3 冒泡排序優(yōu)化
　　9.3.4 冒泡排序復(fù)雜度分析
　9.4 簡單選擇排序
　　9.4.1 簡單選擇排序算法
　　9.4.2 簡單選擇排序復(fù)雜度分析
　9.5 直接插入排序
　　9.5.1 直接插入排序算法
　　9.5.2 直接插入排序復(fù)雜度分析
　9.6 希爾排序
　　9.6.1 希爾排序原理
　　9.6.2 希爾排序算法
　　9.6.3 希爾排序復(fù)雜度分析
　9.7 堆 排 序
　　9.7.1 堆排序算法
　　9.7.2 堆排序復(fù)雜度分析
　9.8 歸并排序
　　9.8.1 歸并排序算法
　　9.8.2 歸并排序復(fù)雜度分析
　　9.8.3 非遞歸實(shí)現(xiàn)歸并排序
　9.9 快速排序
　　9.9.1 快速排序算法
　　9.9.2 快速排序復(fù)雜度分析
　　9.9.3 快速排序優(yōu)化
　　　1．優(yōu)化選取樞軸
　　　2．優(yōu)化不必要的交換
　　　3．優(yōu)化小數(shù)組時(shí)的排序方案
　　　4．優(yōu)化遞歸操作
　9.10 總結(jié)回顧
　9.11 結(jié) 尾 語
附錄 參考文獻(xiàn)

編輯推薦

《大話數(shù)據(jù)結(jié)構(gòu)》為超級(jí)暢銷書《大話設(shè)計(jì)模式》作者程杰潛心三年推出的扛鼎之作！以一個(gè)計(jì)算機(jī)教師教學(xué)為場景，講解數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的知識(shí)。通篇以一種趣味方式來敘述，大量引用了各種各樣的生活知識(shí)來類比，并充分運(yùn)用圖形語言來體現(xiàn)抽象內(nèi)容，對(duì)數(shù)據(jù)結(jié)構(gòu)所涉及到的一些經(jīng)典算法做到逐行分析、多算法比較。與市場上的同類數(shù)據(jù)結(jié)構(gòu)圖書相比，本書內(nèi)容趣味易讀，算法講解細(xì)致深刻，是一本非常適合自學(xué)的讀物。

名人推薦

超級(jí)暢銷書《大話設(shè)計(jì)模式》作者的新作！用戶群更為廣泛，寫作風(fēng)格一如既往，技術(shù)沉淀更加深厚，勢必掀起全民數(shù)據(jù)結(jié)構(gòu)的熱潮！

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    大話數(shù)據(jù)結(jié)構(gòu) PDF格式下載

---