我們這週還會通過Google和高盛的面試題來介紹計算機科學的原理及其思維方式，不過我們需要先介紹點計算機的專業知識做鋪墊。這週要用到的專業知識是計算機的數據結構，它對於專業的計算機人士來講至關重要， 數據結構沒有學好，程序寫得再快，也是業餘水平。類似的做事方式可以推廣到其他領域， 掌握了它：就邁出了成為高級專業人士的第一步。

 

在介紹什麼是數據結構之前，先講兩個繪畫和攝影的例子。

 

我不知道你是否愛畫畫，或者曾經畫過畫，或者看過專業畫家創作的過程。一般人畫畫通常就直接畫了，比如要畫水裡的兩條金魚就直接從某一個部分開始，從外形畫起來了。這種畫法的結果經常是，畫到後來比例不對， 而且常常畫得不像。

 

專業畫家不是這麼畫的，他們會把金魚分解成幾個簡單的幾何圖形，比如頭是一個大圓和兩個小圓（即兩個眼睛），身子是一個橢圓，鰭和尾巴是幾個三角形。如果是幾條金魚，他會先把位置安排好，為了畫面美觀，主要景物的佈置可能要符合一些幾何圖形的形狀，這一點我等會還會舉例子。這些都用淡淡的鉛筆或者淡墨勾好了，才把圓、橢圓和三角形經過平滑過渡，畫成金魚。不掌握這種繪畫方法，永遠走不進專業的大門。

 

在繪畫和攝影中，這些基本的幾何圖形使用的遠比一般人想像的多得多，特別是在構圖上，只不過當最終的作品完成時，你看不太出來最早的構圖框架而已。在欣賞藝術品的時候，專業人士和一般人也是有區別的。前者很快能看出作品構圖的方法，各個部分之間的幾何關係，他們在學習時會琢磨先前那些大師們匠心獨運之處。而普通人看畫則看不出來，也很少在意，他們會更關注一幅畫畫得像不像， 顏色是否搶眼球。這也是很多人會覺得某幅畫或者藝術作品創作得特別好，但說不出理由的原因。

 

接下來我們看看兩個具體的例子。下面這張畫是浪漫主義的開山鼻祖「籍里柯」的代表作《梅杜莎之筏》( The Raft of the Medusa：梅杜薩之筏 )。

 

 

這裡我是要向你介紹它的構圖，它最高層的構圖設計就是兩個金字塔形狀，下圖就是靠著兩個三角形的金字塔，畫面保持了平衡。

 

 

類似地，在米開朗基羅代表作之一的雕塑《聖母冷子》中 ( 見下圖 ) ，他把聖母塑造成悲天憫人的少女形象，但是為了體現神聖莊重，他也採用了金字塔造型。

 

當然，大藝術家採用各種基本幾何結構構圖未必需要打稿時畫在圖上，而是了然於胸。對於幾何形狀不了解，不能從現實中的事物抽像出簡單的幾何形狀（骨架）的人，完成不了複雜的繪畫，即使畫簡單的東西，也畫不好。也就是說，不入門。

 

 

對於計算機科學來講，寫一個能夠完成特定功能的程序，就相當於是作一幅畫。因此，它也有兩種方法，一種是直接就用一行行代碼去實現功能，這是低水平的做法，有些時候看上去做得快，實際上漏洞百出 ( 用專業術語講就是Bug很多 )，回頭需要修補。另一種就是理解需求之後，抽像出具體的基本幾何形狀這樣的基礎塊，然後用算法將這些模塊進行組合，寫出符合需求的程序。

 

當然，這些基本模塊也像繪畫和雕塑中作為輪廓的幾何圖形一樣，需要根據畫面需求平滑過渡，而不是照搬照抄。這些程序中基本的幾何圖形，就是計算機的數據結構。如果說一幅畫是點的有機組合，幾何圖形反映出點之間常用具體的關係，那麼在計算機科學中，數據就等同於點，數據結構就是數據中常用的具體關係。這樣你就理解了什麼是數據結構。

 

世界著名計算機科學家、因為發明帕斯卡程序語言（PASCAL）而獲得圖靈獎的N．沃斯( N.Wirth ) 教授寫過一本書，叫做《數據結構+算法=程序》，很好地講清楚了這三者的關係。

 

在這一周，我們要介紹兩種最常用的數據結構，這樣大家會有些具體的感受。

 

第一種數據結構是線性表。

 

這相當於幾何圖形中的直線．它也是最基本的數據結構。

 

線性表這種抽象的數據結構並非起源於科學計算本身，而是計算機早期的應用 ー 辦公自動化。我們知道，雖然發明計算機的目的是為了科學計算，但是它最早期的商業應用則是在管理和商業方面。

 

在商業上，報表是一種最常見的數據組織形式，而在管理上，最多見的則是人員或者物資的記錄等等。它們都可以被抽象為線性的數據，然後按照 1、 2、3、4、5 的順序排列出來。

 

比如一所大學所有學生的檔案，就是這樣一個個按照順序排列的，而他們的編號就是學號。因此，很有必要設計一種抽象的數據結構概括所有這些順序排列和儲存的數據，它就是線性表。當然，隨著計算機數據規模的擴張， 未必能夠給所有的數據都賦予一個編號順序， 結構化地存儲，但是它們依然遵循一個順序的特徵。比如一個電商交易的日誌記錄，它是按照所發生的時間順序，一條條線性地記錄下來，因此，線性表的性質它們也有。

 

線性表本身是一個抽象的概念，在計算機中則是通過很多種具體的方法實現的。最常見的一種實現方法就是所謂的數組，學習計算機的讀者朋友對此都非常熟悉。

 

數組這個概念很簡單．就是一組編了號的固定大小的單元。比如我們說一個具有 1,000 個整數的數列，從 a0, a1, a2, …….，一直到 a999。這就是數組。數組的好處是給定一個序號，可以直接找出裡面的內容。比如，一個數組存著一個單位員工的信息，只要給出員工的工號，就能調出他的信息並且編輯修改。

 

但是，數組這種數據結構有一個大的缺陷，就是在其中插入一個新的數據非常困難。比如客戶經理用一個數組來存放這週要去拜訪的所有客戶，如果他突然有一個未在計劃中的客戶必須要拜訪，他打必把這個人插入到原來第五個客戶和第六個客戶之間。那麼要在數組中塞進去這個新的客戶其實並不容易，因為他需要把第六個客戶從數組中的第六個位置挪到第七個，留出位置給這個新的客戶。當然，也就需要把第七個挪到第八個的位置，第八個挪到第九個的位置，以此類推。如果一個數組有上百萬個記錄，這麼挪實在是太浪費時間了。

 

第二種數據結構是鏈表。

 

為了彌補這個不足，科學家們發明了一種被稱為鏈表的線性數據結構。所謂鏈表其實就如同我們買東西時排隊一樣，每個人只要記得前面或者後面的一個人是誰就可以了，彼此沒有編號一說。

 

比如要記錄下這週造訪的客戶名單，王二之後是張三，張三之後是李四，李四之後是趙六……，如果要把新加入的王五安排在李四和趙六之間，很簡單，只要修改一下這個鏈表，把李四後面的指針指向王五，把王五後面的指針指向趙六即可。這樣一來，插入一個新的數表就是一件很容易的事了。

 

但是，凡事有一利就有一弊，如果我們要找出列表中第五個造訪的客戶是誰，因為沒有編號一說，因此必須要從頭數一遍，一直數到第五個。如果一個列表有幾百萬個記錄單元， 數一遍可是很花時間的事情。

 

 

那麼對線性的數據，是否有更好一點，能夠兼有前面的優點，而沒有其缺點的數據結構呢？到目前來講還沒有，而且估計以後也不會有，因為世界上凡事都不是十全十美的。對於這樣簡單、有用卻不完美的數據結構，應該怎樣彌補它的不足呢？這就是搞算法的人的工作了。

 

為了便於大家理解線性表，我再做一個類比：

 

數組相當於蓋房子的磚頭，一塊塊整整齊齊地碼著。鏈表則相當於一個沒有頁號的活頁夾筆記本，拿走一頁紙，加入一頁紙都很容易。它們都是搭建計算機科學這個大廈的基本幾何形狀。

 

最後總結一下今天的內容：

 

1. 專業人士和業餘人士做東西的一個重要差別在於，前者掌握瞭如何使用基本圖形、 結構和組成部分來構建複雜設計和產品的方法，後者很據自己腦子裡的構思和直覺，直接構建最終的產品和設計。要想完成複雜的工作，必須掌握所謂科班出身人士掌握的工具和方法。另外，專業人士會把複雜的東西分解為簡單的基本單元。

 

2. 在計算機領域，數據結構則相當於設計中的基本幾何圖形，它們大多是從具體的應用中抽像出來的，一個從業者水平的高下，首先在於靈活使用這些數據結構的本領。

 

3. 凡事有一利就有一弊，在計算機方面幾乎任何設計都是如此，好的工程師並不是不切實際地追求沒有弊病的設計，而是想其它辦法補救相應的問題。

 

明天我會介紹計算機科學中另一個重要的數據結構一二叉樹，有了這個概念，我們就可以講解幾道面試題了。為了方便你預習，我今天提前把兩個面試題和一道思考題，留給大家。

 

1. 高盛面試題：有二十五名短跑選手比賽競爭金銀銅牌，賽場上有五條賽道，因此一次可以有五個人同時比賽。比賽並不計時，只看相應的名次。假如選手的發揮是穩定的，也就是說如果約翰比張三跑得快，張三比凱利跑得快，那麼約翰一定比凱利跑得快。最少需要幾組比賽才能決出前三名？

 

2. Google面試題：如何設計一個地圖的功能，找到離當前位置最近的5個加油站？

 

來源：《吳軍-什麼是計算機的數據結構？》