第1章
數據結構

1-1 什么是數據結構

數據存儲于計算機的內存中。內存如右圖所示，形似排成1列的箱子，1個箱子里存儲1個數據。

數據存儲于內存時，決定了數據順序和位置關系的便是“數據結構”。

舉個簡單的例子。假設我們有1個電話簿——雖說現在很多人都把電話號碼存在手機里，但是這里我們考慮使用紙質電話簿的情況——每當我們得到了新的電話號碼，就按從上往下的順序把它們記在電話簿上。

假設此時我們想給“張偉”打電話，但是因為數據都是按獲取順序排列的，所以我們并不知道張偉的號碼具體在哪里，只能從頭一個個往下找（雖說也可以“從后往前找”或者“隨機查找”，但是效率并不會比“從上往下找”高）。如果電話簿上號碼不多的話很快就能找到，但如果存了500個號碼，找起來就不那么容易了。

接下來，試試以聯系人姓名的拼音順序排列吧。因為數據都是以字典順序排列的，所以它們是有“結構”的。

使用這種方式給聯系人排序的話，想要找到目標人物就輕松多了。通過姓名的拼音首字母就能推測出該數據的大致位置。

那么，如何往這個按拼音順序排列的電話簿里添加數據呢？假設我們認識了新朋友“柯津博”并拿到了他的電話號碼，打算把號碼記到電話簿中。由于數據按姓名的拼音順序排列，所以柯津博必須寫在韓宏宇和李希之間，但是上面的這張表里已經沒有空位可供填寫，所以需要把李希及其以下的數據往下移1行。

此時我們需要從下往上執行“將本行的內容寫進下一行，然后清除本行內容”的操作。如果一共有500個數據，一次操作需要10秒，那么1個小時也完成不了這項工作。

總的來說，數據按獲取順序排列的話，雖然添加數據非常簡單，只需要把數據加在最后就可以了，但是在查詢時較為麻煩；以拼音順序來排列的話，雖然在查詢上較為簡單，但是添加數據時又會比較麻煩。

雖說這兩種方法各有各的優缺點，但具體選擇哪種還是要取決于這個電話簿的用法。如果電話簿做好之后就不再添加新號碼，那么選擇后者更為合適；如果需要經常添加新號碼，但不怎么需要再查詢，就應該選擇前者。

我們還可以考慮一種新的排列方法，將二者的優點結合起來。那就是分別使用不同的表存儲不同的拼音首字母，比如表L、表M、表N等，然后將同一張表中的數據按獲取順序進行排列。

表L

表M

表N

這樣一來，在添加新數據時，直接將數據加入到相應表中的末尾就可以了，而查詢數據時，也只需要到其對應的表中去查找即可。

因為各個表中存儲的數據依舊是沒有規律的，所以查詢時仍需從表頭開始找起，但比查詢整個電話簿來說還是要輕松多了。

數據結構方面的思路也和制作電話簿時的一樣。將數據存儲于內存時，根據使用目的選擇合適的數據結構，可以提高內存的利用率。

本章將會講解7種數據結構。如本節開頭所述，數據在內存中是呈線性排列的，但是我們也可以使用指針等道具，構造出類似“樹形”的復雜結構（樹形結構將在4-2節詳細說明）。

參考：4-2 廣度優先搜索