# 第三章-編程進階-數據結構與算法 首先讓我們看看Wikipedia上對數據結構和算法的定義。 > 數據結構（Data Structure）是計算機中存儲、組織數據的方式。通常情況下，精心選擇的數據結構可以帶來最優效率的算法。 > 算法（Algorithm）是指完成一個任務所需要的具體步驟和方法。也就是說給定初始狀態或輸入數據，能夠得出所要求或期望的終止狀態或輸出數據。 算法和數據結構就是程序里的修辭手法和謀篇布局。人類編程雖然不過幾十年，但運用程序所解決的問題，已經覆蓋世界的每個角落各個方面。各種各樣的問題，被前輩和大師提煉歸納，有些人直接找出了解決的方法，有些人找到了尋找解決方法的途徑，還有些人索性證明了在現階段是不可能解決的，這些解決方案就被統稱為算法。學習算法就是學習前人的智慧，少走彎路。禪語有云：不走彎路就是捷徑！！！連牛頓爵士都是站在巨人的肩膀上的，除非你自我感覺比老牛還牛，憑空就能解決別人十幾年才想清楚的問題。為了更形象的說明這一關系，下面我們來玩一個經典的數學游戲： > 有三個瓶子，容量分別為兩升、三升、七升，現在要快速準確量出六升的水，請問該怎樣得到？ 顯然我們必須用這三個瓶子組合起來才能得到準確的六升水，那如何得到呢？我想聰明的你肯定很快就有了答案。接下來的問題就是怎么用算法表示出來呢？——這就是在考驗我們的數學思維能力了。瓶子裝水這一類問題抽象出來其實就是一個求整系數多項式方程整數解的問題。OK，點到為止。 按照Wikipedia上對數據結構的定義，我們可以把上邊裝水的瓶子類比為數據結構——瓶子在人的干預下干了裝水和倒水的工作，通過三個步驟——你的算法，最終實現了在七升的瓶子中裝了六升的水。通過三個瓶子才能得到六升水，這種事肯定不是聰明的人想出來的，那么聰明一點的人會怎么想呢？——找一個六升的瓶子不就一步完成了嘛！所以說有時找到了合適的數據結構該是多重要... 前輩們已經總結出很多算法和產生算法的方法，我們可以直接學習。如果你積極進取，總有一天，你會發現有需要自己開創新的算法的時候。這個時候，數學功底會幫你很大的忙。也許只是數學工具在起作用，但更有可能的是你的大腦受過的數學思想訓練在幫助你。總之，為了前途著想，提高數學素養是沒錯的。這不是說多背數學公式和多做數學題，而是指一種**數學的思維方式。** 學算法很簡單，也是找教材，做習題。教材容易找，但新手往往找不到合適的習題。可以嘗試在完成教材上的所有習題之后去找編程競賽的練習題來做,也就是所謂的 [Online Judge](http://en.wikipedia.org/wiki/Online_judge)，后續將深入討論這個東西。 ### 算法+數據結構=程序 > *Algorithms + Data Structures = Programs* is a 1976 book written by Niklaus Wirth covering some of the fundamental topics of computer programming, particularly that algorithms and data structures are inherently related. 算法與數據結構的基本概念已經在上文介紹過了，這里再稍微深入一步探討，對于新手來說不必在本小節糾結過多，本節的存在一方面是為了本章的完整性而充實的，另一方面可供有一定基礎的人參考。 實際上，數據結構與算法解決的問題是整個編程中最有限，最底層的那些問題，(它沒有涉及到設計，用戶等編程三層架構中的最重要的后二層)。它只解決對于計算機在組織內存,支持對這些內存中數據進行操作(排序，查找)等有限問題的問題，它僅僅能很好地解決這些問題，所以說它是面向計算機的功能性方案，是計算機的科學，解決對于計算機來說最為迫切要解決的那些問題，比如效益敏感類問題。如果放在整個大編程中來討論，那么它是頗為有限的那類東西。 承載計算機科學最最根本的東西，是數據結構跟算法，而不是語言(語言只是表達工具)。難怪宏大的 [TAOCP](http://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E8%89%BA%E6%9C%AF) 寫的幾乎全是數學和算法分析等內容，跟語言相比，語言本身并不能解決一個問題，它只是反映事物的工具，跟解決問題沒有絕對的聯系，數據結構與算法才是“真正能解決”計算機問題的手段與技術。你看路由器算法，這些底層的東西，都是數據結構與算法發揮作用的地方。 于是，當用數學和機器的眼光直面解決問題的時候，很自然地就產生了一門學科，即數據結構和算法。 **算法與數據結構實際上就是計算機編程界將應用問題離散化建模的方案，這樣，就可以將應用問題轉化為軟件上可用的抽象，而所有一切軟件上的問題，不過都是抽象。**[[1]](#) ### 不會Coding如何破？ 「能看懂別人的程序，但自己就是寫不出來，Why？」——這個問題其實每個剛開始學習編程的人都會遇到，你所見到的各位達人大牛都曾經有過這么一段經歷，所以完全不必為這種情況而懷疑自己的能力。為什么會有這樣的情況出現？——因為思維模式。 在小學的數學教材里，有一種題型，叫應用題。它會給出很多生活中的場景，然后讓你用數學知識來解決。在解這種題時，其實分為三個步驟，首先是要提取出數理模型，比如常見的追逐相遇這類問題，就要使用速度時間模型，然后把這個模型數學化，找出各個變量之間的關系，確定已知量和未知量，形成可求解的方程，最后求解。 編程的情況與此類似。首先要建立一個抽象描述模型，然后建立數學表達，接下來略有不同，不是親自求解，而是給出求解的方法——也就是算法，最后是把算法轉化為程序。而新手通常之所以會卡殼，是由于這個流程中有兩個難關。建立模型不是問題，數學表達也不難，但找出算法卻是非常艱難的事情，即使找到正確的算法，要把它寫成正確的代碼也不容易。新手常說我在學習XX語言,XX語言真復雜啊。其實學習語言本身只能保證你在最后一步，也就是翻譯代碼（又名coding）那里少出錯誤，即使你順利的學習了一萬種語言，你也會覺得編程很難，假如你沒有學習算法的話。讓我們找個具體的例子來說明，假設現在有個題目要找N個正整數中的最大值。顯然這個題目模型很清楚，本身就是數學問題，也不需要數學表達了。接下來就是解法，新手這時就卡在這個地方了。 剛接手這個題目，很多人就會想用一種類似人類的快捷操作，比如三個數，瞥一眼就可以找出最大值，四個數也毫無問題，甚至十個數也是一下子。這時我問你，你怎么把這個瞥一眼的動作表示成程序，另外如果N大于10000怎么辦？——啞口無言。原因是，人類的頭腦過于聰明，可以同時處理很多事務，也就是可以并行處理一定量的數據（當然大規模數據就要另外對待）。而計算機——很遺憾，這方面的能力有所欠缺。這個時候你肯定會說：「現在不是有多處理器多核多線程等各種各樣的并行處理的計算機了么？」我要告訴你，那些都是不同層次的概念。 目前這個時代的計算機，在出現革命性的變化之前，從CPU指令的層次來說，都是單線程單參數工作的。再說明白一點，這些機器任何時候只能一次處理兩個數，而且其中一個還必須已經在CPU內部了，任何N>=3個數相加都必須轉化成持續的兩個數相加，就是先把第一個第二個加起來得到結果之后，才能和第三個相加，照此重復求得所有的和——這是目前的科技無法改變的鐵律。這個時候我要請你記住一個重要的思想：編程中任何問題都要分解到足夠小，小到機器可以一次解決的程度！當然，這不是意味著我們每次編程都得從CPU執行一次指令的角度去解決問題。 回到剛才的那個題目：尋找N個正整數中的最大值。我們知道直接解決是不可能的。而按照剛才講過的鐵律，我們知道直接找到兩個數中的最大值是一次可以做到的。那怎樣從2個擴展到N個呢？這里就是算法的天下了。一種很常見的想法是，完全可以從兩個中找出最大值，再讓它和接下來的一個比較，這就是N=3的情況，再把三個中的最大值和第四個比較，這就解決了 N=4，依此類推，我們似乎找到了通用的算法。是的，找到前N-1個中的最大值，然后與第N個比較——不要懷疑，這個算法方向是正確的。接下來就是把它細化使他能變成代碼。 你注意到，首先要設法從1增加到N，而且每次前進一步都要做類似的操作，顯然可以用一個循環來實現。每一次循環中，都需要將保留的最大值和當前的這第n個數比較，如果最大值比它大，那就保留，否則就要把最大值替換成新的——這就是條件語句的作用了。寫完這個循環之后，還有些小細節，比如這個最大值在與第一個數比較之前應該是多少呢？太大的話，可能會比整個數列的數都大，這就會出問題。因此常用的做法是，就讓他等于第一個數。然后包括讀入那N個數，而輸出最大值這些瑣碎的細節就屬于收尾工作了，沒什么可多談的。當然，即使是這樣的小題，也不僅這一種算法。 你記不記得有一種叫做單淘汰賽的機制——最后頂點的就是最大值。用在這個地方正合適。不過，如果要把這個淘汰賽算法實現成程序的話，如何實現分組，如何表達這個淘汰過程和取出頂點的值，正是算法描述里要解決的。這個就是排序里很有名的最大堆排序。 一旦算法（偽代碼）描述齊備，程序編寫不過是打字校對的工作。 為什么你可以看懂別人的程序呢？——因為他的算法隱含在程序中已經被實現了。就像你讀王維的詩，總能在眼前浮現出一幅幅絕美的風景畫，但輪到自己寫，卻描繪不出那樣的畫面。一方面是因為你束手無策，不知道怎樣找到可實現的算法；另一方面是即使你找到了算法，也只是愛在心中口難開，不知道怎樣去表達。 算法總是從問題出發，通過一定的模式，逐漸細化再細化，直到可以直接轉成程序。新手很難一下子領會什么樣的算法是可以實現的，但好在新手接觸的問題一般不是很難，算法通常非常清楚明白，所以重點是要解決后面那個怎樣把算法表達出來的問題。因此在這里建議各位新手默寫教材上經典的例題程序。很顯然對于那些例題，只要你用心看過就會領會它的算法。那么，你再默寫一遍，即使和它的原程序樣子不一樣，也總算是把這個算法表達出來了。反復這樣練習，這個表達問題不就解決了么？而且在這個過程中，至少你學到了一個算法。基于此原則，任何你遇到的可以看懂的例程（當然要是好的例程才行），都建議你默寫它——尤其是開源的精品代碼。 ### Notes 1. [[1]]() 本小節內容引自 [算法+數據結構的本質 | 兮軟](http://dev.gameres.com/Program/Other/bcxszyforgameres/bcxszy/xisofts.sinaapp.com/@p=104.htm)，該書完整版見[編程新手真言Ver3.0](http://dev.gameres.com/Program/Other/bcxszyforgameres/bcxszy/xisofts.sinaapp.com/@p=5.htm)