數據結構和算法 · 程序猿之知識體系

>算法虐我千百遍，我待算法如初戀 ## 基本數據結構和算法 ### 鏈表 * 鏈表 * 雙向鏈表 ### 哈希表/散列表 (Hash Table) * 散列函數 * 碰撞解決 ### 字符串算法 * 排序 * 查找 * BF算法 * KMP算法 * BM算法 * 正則表達式 * 數據壓縮 ### 二叉樹 * 二叉樹 * 二叉查找樹 * 伸展樹(splay tree 分裂樹) * 平衡二叉樹AVL * 紅黑樹 * B樹,B+,B* * R樹 * Trie樹(前綴樹) * 后綴樹 * 最優二叉樹(赫夫曼樹) * 二叉堆（大根堆，小根堆） * 二項樹 * 二項堆 * 斐波那契堆(Fibonacci Heap) ### 圖的算法 * 圖的存儲結構和基本操作（建立，遍歷，刪除節點，添加節點） * 最小生成樹 * 拓撲排序 * 關鍵路徑 * 最短路徑: Floyd,Dijkstra,bellman-ford,spfa ### 排序算法 **交換排序算法** * 冒泡排序 * 插入排序 * 選擇排序 * 希爾排序 * 快排 * 歸并排序 * 堆排序 **線性排序算法** * 桶排序 ### 查找算法 * 順序表查找：順序查找 * 有序表查找：二分查找 * 分塊查找：塊內無序，塊之間有序；可以先二分查找定位到塊，然后再到`塊`中順序查找 * 動態查找: 二叉排序樹，AVL樹，B- ，B+ （這里之所以叫 `動態查找表`，是因為表結構是查找的過程中動態生成的） * 哈希表： O(1) ### 15個經典基礎算法 * Hash * 快速排序 * 快遞選擇SELECT * BFS/DFS （廣度/深度優先遍歷） * 紅黑樹（一種自平衡的`二叉查找樹`） * KMP 字符串匹配算法 * DP (動態規劃 dynamic programming) * A*尋路算法：求解最短路徑 * Dijkstra：最短路徑算法（八卦下：Dijkstra是荷蘭的計算機科學家,提出”信號量和PV原語“,"解決哲學家就餐問題",”死鎖“也是它提出來的） * 遺傳算法 * 啟發式搜索 * 圖像特征提取之SIFT算法 * 傅立葉變換 * SPFA(shortest path faster algorithm) 單元最短路徑算法 ## 海量數據處理 * Hash映射/分而治之 * Bitmap * Bloom filter(布隆過濾器) * Trie樹 * 數據庫索引 * 倒排索引(Inverted Index) * 雙層桶劃分 * 外排序 * simhash算法 * 分布處理之Mapreduce ## 算法設計思想 * 迭代法 * 窮舉搜索法 * 遞推法 * 動態規劃 * 貪心算法 * 回溯 * 分治算法 --- ## 算法問題選編這是一個算法題目合集，題目是我從網絡和書籍之中整理而來，部分題目已經做了思路整理。問題分類包括： * 字符串 * 堆和棧 * 鏈表 * 數值問題 * 數組和數列問題 * 矩陣問題 * 二叉樹 * 圖 * 海量數據處理 * 智力思維訓練 * 系統設計還有部分來自算法網站和書籍： * 九度OJ * leetcode * 劍指offer ## 開源項目中的算法 * YYCache * cocos2d-objc * ... ## 推薦閱讀 ### 刷題必備《劍指offer》《編程之美》《編程之法:面試和算法心得》 ? 《算法謎題》都是思維題 ### 基礎《編程珠璣》Programming Pearls 《編程珠璣(續)》《數據結構與算法分析》《Algorithms》這本近千頁的書只有6章,其中四章分別是排序，查找，圖，字符串，足見介紹細致 ### 算法設計《算法設計與分析基礎》《算法引論》告訴你如何創造算法斷貨《Algorithm Design Manual》算法設計手冊紅皮書《算法導論》是一本對算法介紹比較全面的經典書籍《Algorithms on Strings,Trees and Sequences》《Advanced Data Structures》各種詭異高級的數據結構和算法如元胞自動機、斐波納契堆、線段樹 600塊 ### 延伸閱讀《深入理解計算機系統》《TCP/IP詳解三卷》《UNIX網絡編程二卷》《UNIX環境高級編程：第2版》《The practice of programming》 Brian Kernighan和Rob Pike 《writing efficient programs》優化《The science of programming》證明代碼段的正確性 800塊一本 ## 參考鏈接和學習網站 ### [July 博客](http://blog.csdn.net/v_july_v) 《數學建模十大經典算法》《數據挖掘領域十大經典算法》《十道海量數據處理面試題》《數字圖像處理領域的二十四個經典算法》《精選微軟等公司經典的算法面試100題》 [The-Art-Of-Programming-By-July](https://github.com/julycoding/The-Art-Of-Programming-By-July) [微軟面試100題](http://blog.csdn.net/column/details/ms100.html) [程序員編程藝術](http://blog.csdn.net/v_JULY_v/article/details/6460494) ### 基本算法演示 http://sjjg.js.zwu.edu.cn/SFXX/sf1/sfys.html http://www.cs.usfca.edu/~galles/visualization/Algorithms.html ### 編程網站 [leetcode](http://leetcode.com/) [openjudge](http://openjudge.cn/) 開放在線程序評測平臺，可以創建自己的OJ小組 ? [九度OJ](http://ac.jobdu.com/index.php) 這有個[ACM訓練方案](http://www.java3z.com/cwbwebhome/article/article19/res041.html) ### 其它 [高級數據結構和算法](https://www.coursera.org/learn/gaoji-shuju-jiegou/) 北大教授張銘老師在coursera上的課程。完成這門課之時，你將掌握多維數組、廣義表、Trie樹、AVL樹、伸展樹等高級數據結構，并結合內排序、外排序、檢索、索引有關的算法，高效地解決現實生活中一些比較復雜的應用問題。當然coursera上也還有很多其它算法方面的視頻課程。 [算法設計與分析 Design and Analysis of Algorithms](https://class.coursera.org/algorithms-001/lecture) 由北大教授Wanling Qu在coursera講授的一門算法課程。首先介紹一些與算法有關的基礎知識，然后闡述經典的算法設計思想和分析技術，主要涉及的算法設計技術是：分治策略、動態規劃、貪心法、回溯與分支限界等。每個視頻都配有相應的講義（pdf文件）以便閱讀和復習。 ## 聯系 [@移動開發小冉](http://weibo.com/ranwj)