編輯推薦

　　探秘算法世界、求索數據結構之道

　　匯集經典問題、暢享編程技法之趣

　　點撥求職熱點、敲開業界名企之門

　　探秘算法世界、求索數據結構之道

　　匯集經典問題、暢享編程技法之趣

　　點撥求職熱點、敲開業界名企之門

內容簡介

　　本書以現代計算機常用的十八種數據結構為綫索，結閤C++中的STL編程實踐，詳細介紹瞭四大算法設計思想(貪心法、動態規劃、分治法、迴溯法）、二十大經典問題和四十二個重要算法。具體涉及的數本書圍繞算法與數據結構這個話題，循序漸進、深入淺齣地介紹瞭現代計算機技術中常用的40餘個經典算法，以及迴溯法、分治法、貪婪法和動態規劃等算法設計思想。在此過程中，本書也係統地講解瞭鏈錶（包括單嚮鏈錶、單嚮循環鏈錶和雙嚮循環鏈錶）、棧、隊列（包括普通隊列和優先級隊列）、樹

　　（包括二叉樹、哈夫曼樹、堆、紅黑樹、AVL樹和字典樹）、圖、集閤（包括不相交集）與字典等常用數據結構。同時，通過對22個經典問題（包括約瑟夫環問題、漢諾塔問題、八皇後問題和騎士周遊問題等）的講解，逐步揭開隱匿在數據結構背後的算法原理，力圖幫助讀者夯實知識儲備，激活思維技巧，並最終衝破阻礙編程能力提升的重重藩籬。

作者簡介

　　左飛，服務於中國規模較大的移動通信運營商，業餘時間他撰寫瞭多部計算機方麵的著作，並譯有《編碼》、《提高C++性能的編程技術》等經典名著。

目錄

第1 章 從數據到算法 .................................................................. 1

本章參考文獻 ................................................................................................ 23

第2 章 指針與數組——也談中國古代兵製 ................................ 24

本章參考文獻 ................................................................................................ 61

第3 章 字符串與模式匹配——夢裏尋她韆百度 ......................... 62

本章參考文獻 ................................................................................................ 89

第4 章 鏈錶——老鷹捉小雞 ..................................................... 91

本章參考文獻 .............................................................................................. 126

第5 章 先進先齣與後進先齣——簡單而深刻 .......................... 127

本章參考文獻 .............................................................................................. 158

第6 章 遞歸——老和尚講故事 ................................................ 159

本章參考文獻 .............................................................................................. 183

第7 章 樹——從紅樓夢說起 ................................................... 184

本章參考文獻 .............................................................................................. 230

第8 章 圖——始於哥尼斯堡的七橋問題 .................................. 231

本章參考文獻 .............................................................................................. 283

第9 章 樹形搜索結構——做一名齣色的園藝師 ....................... 284

本章參考文獻 .............................................................................................. 320

第10 章 集閤與字典——再言搜索之話題 ............................... 321

本章參考文獻 .............................................................................................. 374

第11 章 排序——有序讓世界更美好 ....................................... 375

本章參考文獻 .............................................................................................. 407

附錄 經典求職麵試題目 .......................................................... 408

前言/序言

　　2014 年的鼕天，一部講述計算機科學之父艾倫?圖靈傳奇人生的傳記電影在美國上映，這部影片就是《模仿遊戲》。次年，該片榮獲第87 屆奧斯卡金像奬最佳改編劇本奬，以及包括最佳影片、最佳導演、最佳男主角、最佳女配角在內的7 項提名，一時風光無限。盡管現代計算機已經無處不在，但因圖靈的時代離我們過於久遠，現今人們對他的研究工作已經知之甚少。

　　要說起圖靈的貢獻，我們還得把時間再往前推。1900 年，德國數學傢大衛?希爾伯特在巴黎舉行的國際數學傢大會上做瞭題為《數學問題》的演講，在這篇重要的演講中，他提齣瞭著名的希爾伯特之23 個問題。盡管此後的數學發展遠遠超過瞭希爾伯特的預料，但他所提齣的23 個問題仍然對20 世紀的數學發展起到瞭非常積極的推動作用。

　　希爾伯特的第10 個問題是要設計一個算法來測試多項式是否有整數根。他沒有使用算法這個術語，而是采用瞭下麵這種錶述：“通過有限多次運算就可以決定的過程”。有意思的是，從希爾伯特對這個問題的陳述可以看齣，他明確地要求設計一個算法。因此，他顯然是假設這樣的算法是存在的，人們所要做的隻是找到它。現在我們知道，這個任務是無法完成的，即它是算法上不可解的。但對那個時期的數學傢來說，以他們對算法的直觀認識，得齣這樣的結論是不可能的。

　　非形式地說，算法是為實現某個任務而構造的簡單指令集。以日常用語來說，算法又稱為過程或者方法。算法在數學中也起著非常重要的作用。古代數學文獻中就包含有執行各種各樣計算任務的算法描述。例如，我國古代數學經典《九章算術》中就記述瞭包括求最大公約數、最小公倍數、開平方根、開立方根等在內的諸多算法。現代計算機科學中更是充滿瞭各種各樣的算法。例如，求解最短路徑的狄剋斯特拉算法，進行字符串匹配的KMP 算法等。

　　雖然算法在數學中已有很長的曆史，但在20 世紀之前，算法概念本身一直沒有精確的定義。數學傢們麵對希爾伯特的第10 個問題，顯得束手無策。由於缺乏對於算法本身的精確定義，所以要證明某個特定任務不存在算法則完全不可能。要想破解希爾伯特的第10 個問題，人們不得不等待算法之精確定義的齣現。

　　直到1936 年，曙光似乎齣現瞭。圖靈嚮倫敦的權威數學雜誌遞交瞭一篇題為《論數字計算在決斷難題中之應用》的論文。該文最終於1937 年正式發錶，並立即引起瞭廣泛的注意。在論文中，圖靈描述瞭一種可以輔助數學研究的機器，也就是後來被稱為“圖靈機”的抽象係統。與此同時，另外一位數學傢阿隆佐?丘奇也獨立地提齣瞭另外一套係統，即所謂的λ演算。圖靈采用他的圖靈機來定義算法，而丘奇則采用λ演算來定義算法，後來圖靈證明這兩個定義是等價的。由此，人們在算法的非形式概念和精確定義之間建立瞭聯係，即算法的直覺概念等價於圖靈機算法，這就是所謂的丘奇－圖靈論題。

　　丘奇－圖靈論題提齣的算法定義是解決希爾伯特第10 個問題所必需的。而第10 個問題的真正解決則要等到1970 年，藉助於丘奇與圖靈的傑齣貢獻，馬提亞塞維齊在戴維斯、普特納姆和羅賓遜等人工作的基礎上，最終證明檢查多項式是否有整數根的算法是不存在的。

　　從圖靈開始，算法已然同計算機科學之間産生瞭密不可分的聯係。當然，本書的內容並不打算從圖靈機開始講起。迴顧建立算法形式化定義和破解希爾伯特第10 個問題的那段風起雲湧的曆史，更多地是想說明算法之於我們的世界是多麼重要。

　　無論你是信息技術的從業人員，還是計算機專業的在校學生，再或者是從事相關專業的研究人員，熟練掌握一門計算機語言的重要性都不言而喻。但是不是掌握瞭這其中的語法規則就能寫齣漂亮的程序瞭呢？答案當然是否定的。因為你還需要另外一樣至少同等重要的工具——算法。算法和語言的關係，其實很像是“道”和“術”的關係。掌握一門語言，就如同習得一門技藝，可以成為一名工匠。但要想從工匠一躍成為大師，單單停留在“術”的層麵顯然不夠，更重要的是悟“道”。而算法無疑就是計算機程序設計中的“道”。

　　談到算法的重要性就不得不提及計算機科學傢安德魯?艾派爾在1985 年所開展的一項研究工作，這也是程序性能優化領域的經典案例。彼時，艾派爾編寫瞭一個用於計算重力場中天體間相互作用之問題的程序。給定場中物體質量、初始位置和速度等條件，該程序即可對10000 個天體相互作用時其中兩個天體的運行狀態進行模擬和仿真。由於計算量太大，最初的程序要完成該項計算大約需要耗時一年。在一係列的改進之後，艾派爾最終將程序耗時有效地縮短到瞭一天！而在這個改進過程中，算法和數據結構的調優占瞭主要比重。

　　再說一個發生在筆者身上的例子。曾經在上學的時候，老師布置瞭一道編程作業，用於模擬一個猜三和弦的遊戲。一個三和弦是指從A、B、C、D、E、F、G 這7 個音中任選3 個組成的一個鏇律，而每個音又有高音、中音、低音3 種情況（分彆用1、2、3 來錶示）。現在假設一名作麯傢心中有瞭一個心儀的鏇律，然後一個鋼琴演奏者試圖猜測這個答案。每當演奏者給齣一個猜測，例如“A1、B2、C3”。那麼作麯傢將隻能答復這其中完全猜中的音調（即音符和音高都猜對）有幾個，除瞭完全猜中的音調以外，音符猜中瞭幾個，音高猜中瞭幾個。然後演奏者繼續猜測，直到完全猜中為止。要知道，全部的組閤可能有1330 種之多！而我們希望用越少的次數猜中越好。不知道本書的各位讀者心中是否已想到什麼方法來解決這個問題。不過筆者最終實現的程序可以做到平均4.2 次便猜中答案。而在這個過程中，設計一個絕佳的算法無疑是不二之選。

　　說起算法又不得不提及數據結構，二者是相輔相成、密不可分的。一方麵，算法一定要藉助相應的數據結構纔能得以實現，另一方麵我們在定義一個數據結構的同時其實也已經定義瞭與之相關的操作。這些操作本身執行的步驟就是算法。

　　總的來說，本書圍繞算法與數據結構這個話題，循序漸進、深入淺齣地介紹瞭現代計算機技術中常用的40 餘個經典算法（包括模式匹配算法、排序算法、散列算法、最短路徑算法等），以及迴溯法、分治法、貪婪法和動態規劃等算法設計思想。本書也係統地講解瞭鏈錶（包括單嚮鏈錶、單嚮循環鏈錶和雙嚮循環鏈錶）、棧、隊列（包括普通隊列和優先級隊列）、樹（包括二叉樹、哈夫曼樹、堆、紅黑樹、AVL 樹和字典樹）、圖、集閤（包括不相交集等）與字典等常用數據結構。同時，通過對22 個經典問題（包括約瑟夫環問題、漢諾塔問題、八皇後問題和騎士周遊問題等）的講解，逐步揭開隱匿在數據結構背後的算法原理，力圖幫助讀者夯實知識儲備，激活思維技巧，並最終衝破阻礙編程能力提升的重重藩籬。

　　更值得一提的是，算法與數據結構知識是技術類求職過程中的必考內容。希望廣大讀者，尤其是處於求職應聘階段的畢業生，在夯實基礎、培養能力的同時，亦能設法將知識轉化為生産力，求得一份稱心如意的職位。若能事半功倍、一石二鳥，何樂而不為？為此，筆者特彆在附錄中整理齣瞭一些求職麵試中的經典題目，供有相關需求的讀者參考學習。該套題目主要以算法與數據結構問題為主綫，並穿插以C/C++相關的編程問題，具有較高的實用性，對提高應聘競爭力很有幫助。特彆地，在正文中涉及相關考點之處，筆者均采用旁注的形式點明瞭可以參考的題目編號，便於讀者在閱讀過程中，邊學邊練，知行閤一。

　　紙上得來終覺淺，絕知此事要躬行。錘煉數據結構的運用能力和深化算法思想的理解程度都有賴於編程實踐活動。本書采用C++作為描述語言，並提供有涉及的全部數據結構和算法之實現代碼，供讀者參考學習。這些代碼均在基於TDM-GCC 4.9.2 的DEV-C++ 5.11 和Visual Studio 2013 環境下編譯通過。本書特彆提供瞭一個在綫支持資源，地址http://blog.csdn.net/baimafujinji，從中讀者可以下載得到全書的配套代碼和附錄題庫的參考答案，本書的勘誤也將實時發布在此博客上。同時歡迎讀者就本書中的問題和不足與筆者展開討論，有關問題請在上述博客中留言。

　　最後，劉航、吳凱、薑萌、何鵬、鬍俊、李召恒、初甲林等人也參與瞭本書編寫工作，筆者在此錶示由衷的感謝。

　　自知論道須思量，幾度無眠一文章。由於時間和能力有限，書中紕漏在所難免，真誠地希望各位讀者和專傢不吝批評斧正。

很好 便宜實惠 比超市買更好

還可以

書還不錯，內容有參考價值

比預想快，價格不錯，非常方便！

錯漏百齣，我也是服氣的…

好評好評好好評好好評

挺好的書, 耐看,要求有點數學基礎吧, 值得擁有.

不錯，挺好。

看作者和目錄買的，應該不錯吧