# 數據結構與算法類 ### 教材及MOOCs ### The Art of Computer Programming Author: Donald E. Knuth 中文書名：計算機程序設計藝術，簡稱 **TAOCP** ，號稱是經典中的經典，每一個想要掌握算法精髓的人都必須看的書，算法書中的圣經。**鎮樓專用，新手請勿當作入門書去讀，會吐血的。** 說到這本書就忍不住想多介紹下高爺爺的生平。 1938年初，高德納出生于美國威斯康辛州。畢業于加州理工學院的他，目前是美國著名的計算機科學家，并且是斯坦福大學計算機系榮譽退休教授。高德納的英文全名為：Donald Ervin Knuth。他的中文名是1977年到中國來之前，姚儲楓為他取的。Knuth從此用高德納作為其在Unicode世界的名字。 TAOCP這套關于算法分析的多卷論著已經長期被公認為經典計算機科學的定義性描述。迄今已出版的完整的三卷(第四卷已有部分出版)已經組成了程序設計理論和實踐的惟一的珍貴資源，無數讀者都贊揚Knuth的著作對個人的深遠影響，科學家們為他的分析的美麗和優雅所驚嘆，而從事實踐的程序員已經成功地將他的「菜譜式」的解應用到日常問題上，所有人都由于Knuth在書中表現出的博學、清晰、精確和高度幽默而對他無比敬仰。 他因這些成就以及大量富于創造力和具有深遠影響的著作（19部書，160篇論文）而譽滿全球。這么說吧，目前你所能聽說過或者還活著的那些計算機軟件大牛，沒有哪個不直接或間接的受過Knuth的教導。他強悍的程度只用一件小事就可以說明，在撰寫這套《計算機程序設計藝術》的過程中，由于感到原有排版系統的不足，他特地重新制作了一套新的計算機排版系統，這套稱為TEX的東西目前已經是出版界的標準系統。 1968年，剛剛進入Stanford的高德納開始準備出版經典巨著《計算機程序設計藝術》，據說當時他一口氣寫了3000頁，自此他計劃寫七卷（目前已經完成四卷）。這七卷分別為：基礎算法、半數值算法、排序與查找、組合算法、造句算法、與上下文無關語言理論、編譯器技術。1999年底，該書被美國科學家期刊列為20世紀最佳12部學術專著之一。 建議到豆瓣和Amazon上仔細看看評論或者看看印刷版，這一套書雖然很多人都極力推崇，但并不見得他們都看過，個人覺得中文翻譯的看起來有點別扭，建議還是看英文原版的好了。**紙上得來終覺淺，絕知此事要躬行。** ### [Introduction to Algorithms - 算法導論 (豆瓣)](http://book.douban.com/subject/20432061/) 麻省理工學院計算機系的算法教材，已經成為世界范圍內廣泛使用的大學教材和專業人員的標準參考書。書很厚，適合當作工具書來使，看的時候可以結合MIT的課程講義和視頻。具體的講義視頻鏈接后再補充。 以上兩本都是重量級的算法書，下面推薦一些輕量級的書。 ### [Algorithms - 算法（第4版） (豆瓣)](http://book.douban.com/subject/19952400/)</dt> Robert Sedgewick在算法方面寫了不少好書，這本是他最近在算法書方面的大作，也是他所有算法書中讀者評價最好的一本了，使用Java實現，之前有寫過用C/C++實現的算法書。Coursera上將該書的內容分為了兩個部分，[Algorithms, Part I | Coursera](https://www.coursera.org/course/algs4partI) 和 [Algorithms, Part II | Coursera](https://www.coursera.org/course/algs4partII) ，書中內容極其詳細，中文版的沒看過，但是英文原版的排版超級贊！ ### [Problem Solving with Algorithms and Data Structures using Python](http://interactivepython.org/courselib/static/pythonds/index.html) Python黨的福利，作者免費在網上發布了電子版供大家閱讀。用Python來寫算法書的目前還不多，有其他好書推薦的可以發PR。 下面介紹一些用C/C++來寫算法書的教材。 ### [Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching](http://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Structure/dp/0201350882/ref=sr_1_2?ie=UTF8&qid=1412603287&sr=8-2&keywords=Algorithms+Robert+Sedgewick) ### [算法I～IV（C++實現）――基礎、數據結構、排序和搜索 (豆瓣)](http://book.douban.com/subject/1143801/) ### [Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching](http://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Structures/dp/0201314525/ref=sr_1_2?ie=UTF8&qid=1412603571&sr=8-2&keywords=Algorithms+in+C) ### [算法：C語言實現 (豆瓣)](http://book.douban.com/subject/4065258/) C和C++的算法實現是 Robert Sedgewick較為早期的大作，雖然名氣不及Java實現的那本，但如果看C或C++實現的算法書的話這兩本還是不錯的。Robert Sedgewick 在Princeton教了蠻久的書了。 ### OJ - [一些主流的編程競賽網站 - 靈魂機器](http://cn.soulmachine.me/blog/20130322/) - 對各OJ進行了對比。 - [USA Computing Olympiad](http://www.usaco.org/) - [qiwsir/algorithm](https://github.com/qiwsir/algorithm) - 老齊收集的一些算法題，大量使用Python **待完善** Online Judge系統（簡稱OJ）是一個在線的判題系統。用戶可以在線提交程序多種程序（如C、C++、Pascal）源代碼，系統對源代碼進行編譯和執行，并通過預先設計的測試數據來檢驗程序源代碼的正確性。[2] OJ的題目大部分是關于算法的。題目的輸入輸出通常是命令行方式，而非圖形界面。也就是說，要關注的不是平臺的兼容性、文件的格式抑或窗口的布置這種無關緊要的細節，而是問題本身的邏輯實現。 一個用戶提交的程序在Online Judge系統下執行時將受到比較嚴格的限制，包括運行時間限制，內存使用限制和安全限制等。用戶程序執行的結果將被Online Judge系統捕捉并保存，然后再轉交給一個裁判程序。該裁判程序或者比較用戶程序的輸出數據和標準輸出樣例的差別，或者檢驗用戶程序的輸出數據是否滿足一定的邏輯條件。最后系統返回給用戶一個狀態：通過（Accepted, AC）、答案錯誤(Wrong Answer, WA)、超時(Time Limit Exceed, TLE)、超過輸出限制（Output Limit Exceed, OLE)、超內存（Memory Limit Exceed, MLE）、運行時錯誤（Runtime Error, RE）、格式錯誤（Presentation Error, PE)、或是無法編譯（Compile Error, CE），并返回程序使用的內存、運行時間等信息。 Online Judge系統最初使用于ACM-ICPC國際大學生程序設計競賽和OI信息學奧林匹克競賽中的自動判題和排名。現廣泛應用于世界各地高校學生程序設計的訓練、參賽隊員的訓練和選拔、各種程序設計競賽以及數據結構和算法的學習和作業的自動提交判斷中。 以下幾個OJ都很不錯，請隨意進入，也可以自行搜索，國內很多學校的OJ正在熱火朝天的建設中，有的甚至直接作為了考試用系統。 搜搜百科上有一篇文章介紹得不錯,[OJ](http://baike.soso.com/v708668.htm) 一個人孤單做題的滋味是很郁悶的，尤其是當你確實絞盡腦汁也搞不定的時候。幸好線上還是有很多同樣在做題的朋友，他們通常會在論壇BBS或郵件列表之類的地方集中討論解題心得，甚至有可用的答案。建議用OI (Olympiad in Informatics 信息學奧林匹克)[3]為關鍵字搜索。 哪里有代碼示例可看？這個可以自己Google, 如果你已經能夠做一些OJ的題了，那么可以考慮看一些開源軟件的代碼。[http://sourceforge.net](http://sourceforge.net)[http://github.com](http://github.com)[http://code.google.com](http://code.google.com) 上有很多開源軟件，確定一個應用主題上去找就會有收獲。不過說實話，從OJ到項目是有一定的跨越，所以要找到適合自己的項目來看是不容易的。可以嘗試和他人合作做一些小型的項目[4]，邊學邊用，或者是找一些知名的但又比較小規模的項目，然后找他的早期版本的代碼，會比較清晰，比如 vim1.0/2.0 lua1.0 apache1.0這種。