如何將數據結構和演算法應用到實際之中？

12-31

一般來說，數據結構和演算法這本書上提到的任何演算法/數據結構，你都不會有機會重新實現一次。

因為，早有就各種各樣的庫，對外提供了工業級的、充分泛化的實現，只需拿來用就是了。

重寫的話，一個代碼質量/執行速度，顯然都極難超過經過千錘百鍊的、在無數項目中經過充分測試的庫實現；另一個，書上都是為了教學而做的簡化實現，實際使用中，需要對演算法做一定的泛化。（比如，c的qsort庫函數，只要保證數據是以指針數組索引的、對自定義數據須傳入比較大小的功能函數，那麼任何數據都可以用這個qsort演算法排序；C++裡面呢，則是和容器、迭代器之類東西結合通盤考慮的，可泛用於任何符合規範的容器和原生數據類型。而課本上的實現，僅能支持數組中的整數。想做到工業水平，沒有足夠的經驗是不可能的。）

但，另一方面，所有這些演算法/數據結構的設計思路，卻會貫穿於絕大部分項目之中。

比如說，簡單的冒泡演算法，它是不是只是「多次掃描一個數組，交換遇到的每一對相鄰的、順序反了的數字；當不再發生交換時，數組已完成排序」甚至」好不容易才死記硬背下來的一段代碼「？

如果你只學會了這個，那麼，你真就完全白學了。

作為一個表現一般的排序演算法，冒泡排序本身出場率就不高；何況還有各種提供了泛化的sort演算法的庫：如果僅僅記下了這個，那麼你一輩子都不會遇到」必須重寫冒泡演算法「的場合。

但，如果你把冒泡演算法記成：

就好象水中的氣泡一樣，每次只執行「相鄰的元素比較密度（或其它特徵），密度小的上浮，密度大的下沉」這個局部物理過程；多次進行後，局部有序就會變成（相關特徵上的）整體有序。

甚至：

模仿各種會導致整體有序現象的局部過程去處理數據，可以使得數據整體上滿足類似的排布。

甚至：

考察任何自然規律，看它會產生什麼有趣的後果；那麼當需要達到類似的效果時，不妨嘗試用程序模擬出這個規律，很可能就已經得到了想要的效果。

那，你這一生，可就受用不盡了。

比如說，」高大上「的」神經網路「」遺傳演算法「」蟻群演算法「等等等等，其實骨子裡不都是這個」冒泡思路「嗎？

類似的，各種樹都是鏈表的」鉤掛「思想+數組的」索引「思想的結合體；」模擬退火演算法「又是冒泡思路結出來的另一顆果子；音頻濾波演算法就是簡諧振動計算公式；面向對象的」繼承「不過是常見的」歸一化「手法的另一個表述方式……

可以說，如果能像對冒泡演算法的真正理解一樣，徹底弄明白各種演算法的設計思路並加以借鑒，那麼你對這個世界的各種規律了解的有多透徹，你的程序就可以寫的有多靈動。

一旦掌握這個，從此，你再不必像那些菜鳥一樣，絞盡腦汁敲出無數代碼去」湊「需求；而是只需用代碼編織出需要的規律，然後丟給CPU執行，你真正想要的東西就會自然」湧現「：現在，你只要找出」結果已經出現「的識別方法，用它來結束你的邏輯就行了。

（當然，達成一個目的往往可以有多個不同的途徑，不同途徑利用不同的規律；那麼哪個途徑最優呢？演算法課教過你：這就是所謂的「演算法複雜度」）

——冒泡演算法可不就是用代碼編織了一個」數值大者靠前（或靠後）「的規律，然後丟給CPU一跑，一大片數據就有序了？

——遺傳演算法呢，不正是」抄襲「了自然界的自然選擇規律嗎？把這個規律丟給CPU一跑，居然連AI都弄出來了！

這些只是一些特別經典、特別著名的案例而已。

實際工作中，也是時刻都可能遇到一些新鮮的需求/場景；要完成工作，除了出苦力一行行碼代碼外，一樣可以通過觀察找到其中的規律，然後用代碼編織規律，再讓這些規律去替你完成需求：後者往往會比前者簡潔的多得多，執行速度一般也會快得多得多。

這類隨時隨地「發明」的演算法實在不值一提，不能讓你像那些著名案例一樣一舉成名；但它們卻實實在在可以提高你的工作效率，讓其他人望塵莫及。

——經常有高手驕傲的宣稱，別人幾萬、幾十萬行代碼都解決不了的問題，他數百行代碼就清楚漂亮的解決了，執行效率還高出許多倍：他們就是這樣做到的。

我準備用迪傑斯特拉（dijkstra)演算法或者弗洛伊德(floyd-warshall)演算法寫個智能選路程序，先佔坑

寫一些程序，尤其是比較底層的程序。就明白它們的用處了。

列舉下我們當初的作業（其實是老師從UC Santa BarbaraUC Berkley CS作業直接copy來題目）

（1）實現一個簡單的 TCP 傳輸層的協議機制

自己去設計協議，不用照搬 RFC 的標準，其實就是數據結構的用場。

需要考慮到數據包丟失（Loss）、損壞（Corruption）、亂序（Disorder）這樣的情況。

（2）實現操作系統的虛擬內存機制（基於Nachos系統）

如何去設計頁表。如何使用置換演算法。以及應用程序請求頁的時候，發生缺頁，從而導致的中斷如何處理。

（3）實現一個簡單的編譯器（MiniJava）

詞法：字元串匹配，表達式求值等演算法；

語法：生成抽象語法樹；

語義：採用適當的設計模式（Visitor）來生成語義表、字典、然後轉化為目標代碼（可以是彙編、或者是類似的 Three-Address Code）

如果以上三個任務都完成並搞懂了，那麼恭喜：你不僅掌握了數據結構、演算法，而且也學習了計算機網路、操作系統、編譯原理中大部分的知識。

我來說一個數據結構的實際應用。

我認識一個大牛，他不喜歡洗襪子，又不喜歡襪子的臭味。他買了很多樣式一樣的襪子，把這些襪子放在地上，根據臭的程度，擺一個二叉堆。每天早上，他pop兩隻最「香」的襪子，穿上；晚上回到家，把襪子脫下來，push到堆里。某一天，top的襪子超過他的耐臭能力，全扔掉，買新的。

初級篇

記住都有哪些演算法，解決什麼問題
去試圖解決實際的問題，自然會碰到之前演算法解決的問題，使用這些演算法

中極篇

先完成初級篇
記住演算法的具體解決辦法
實際的問題如果有與標準演算法相似但是不完全一樣的，仔細分析差別，修改原有演算法

高級篇

先完成中極篇
分析一下演算法的解決辦法是如何才能想到，最核心和最精妙的地方在哪兒
實際的問題如果與標準演算法都不太象，仔細想想這個問題的本質，借鑒經典演算法精妙之處，自己設計自己要用的演算法

骨灰篇

先完成高級篇
忘掉所有演算法
解決實際問題

題主問的怎樣應用到實際之中，我就分享我怎麼用鏈表的吧~

本人比較懶，上課筆記本只帶一本，課又比較多，於是筆記就記成下面這樣了：

數據結構嘛，當然就是用來管理數據的~個人感覺這樣用鏈表記筆記挺不錯，充分利用存儲空間，讀取起來CPU開銷也不是很高。

...總感覺和前面幾位編程達人比起來有點弱= =||

如何將這些所學應用到實際之中? 一定要這樣想的話,就很是難辦了.

老實說,數據結構如紅黑樹,後綴樹, 演算法如快速傅里葉變換,網路流等.. 平時工作本來就很難碰上這些東西(如果確實從事尖端研究除外)... 個人經常碰到的也無非就是些搜索, 優化剪枝...

如果想著應用, 我建議還是先選好你要做的項目, 然後再考慮自己在數據結構演算法上的所學能否在其之上改進及優化, 再展開來學習.

如果是單單對數據結構和演算法有興趣, 拋開應用我推薦你先找些書籍來啃一下, 這方面的經典太多了... 如&<演算法導論&>等.

如果學完了一部分的只是後, 很迫不及待的想知道自己是否掌握, 應用實際來實踐一下.

那我只能推薦你到各個在線判題系統上來找相應的主題來練練手了,這樣的網站太多了~ 國內推薦 http://poj.org/ 運行速度內存代碼長度一覽無遺,外加單題排名,給你無限追求極致的樂趣.

很多前輩喜歡將數據結構及演算法一類知識比為內功心法. 招式相同,但是卻能發揮出無匹威力.

我以為, 將數據結構及演算法比為玄妙的招式也未嘗不可, 暴力的搜索不如動態規劃輕描淡寫地一矢中的. 數據結構演算法本身就有其迷人的地方. have fun~

我面試別人，常問的一個問題：如果讓你實現qq那種分組的好友列表，支持各種qq裡邊的好友操作，你會怎麼做？

為解決實際問題而設計演算法就可以了。