# 如何選擇數據結構-電話薄的設計 現在大家都用手機，存儲和查詢電話號碼十分方便。一個電話薄看似簡單，這里面也能映射出選擇合適的數據結構的重要性。 ### 方式一：順次添加 當我們有一個紙質電話薄，在得到一個新號碼時，只能從上往下記錄，這種方式對寫一條新數據來說十分方便，例如： name|tel ---|---| Jack|123xxx Emma|456xxx Colin|789xxx Leon|132xxx ChaoChao|132xxx ...|... 假如我們要給『Tommy』打電話，在上面的排序中，我們不知道Tommy具體在哪，只能從上往下翻，膽子野一些說不定『隨機查找』更快些。但是無論怎樣，當這種存儲很大時，我們找起電話來就不容易了。 ### 方式二：按姓名首字母排序 無論中文名還是英文名，我們都可以找到其首字母。如果以聯系人姓名首字母排序，數據都會是以字典順序排列的，他們就是有『結構』的，例如： name|tel ---|---| ChaoChao|132xxx Colin|789xxx Emma|456xxx Jack|123xxx Leon|132xxx ...|... 這時，如果我們要給『Tommy』打電話，就可以很輕松確認Tommy的大致位置。 但是，如果我們要添加一條數據呢？比如我們新認識一個朋友『Fred』，要將他的手機號寫到電話薄里。由于我們的電話薄是按照姓名首字母排序的，所以需要將其寫在`Emma`和`Jack`的中間，但是上面已經沒有空位可以寫，所以需要將`Jack`的『內容寫到下一行，并清空本行』，相對應的，后面所有的數據都要執行『將本行內容寫到下一行，并清空本行』的操作。如果一次操作耗時10s，當我們的電話薄很大時，添加一個人進來可能要花費好幾個小時。 ### 方式三：將順序添加和按首字母排序結合 通過上面的研究，我們發現： * 順序添加方式的新增速度快、成本小 * 按首字母排序方式的查詢速度快 如果我們將電話薄分成多個部分呢？我們將每一個部分記為一個表，每一個表對應一個首字母：表A、表B、 表C... 例如： **表C** name|tel ---|---| ChaoChao|132xxx Colin|789xxx ...|... **表E** name|tel ---|---| Emma|456xxx Elin|256xxx Elfa|356xxx ...|... **表J** name|tel ---|---| Jack|123xxx Jonny|632xxx ...|... 這樣一來，我們每次添加新數據就可以找到對應的表往后面順序寫就行了，而查詢時也可以快速定位到大概位置。 雖說各個表中的存儲還是無規律的，每次都要從表頭開始往下查找，但是也要比從整個電話薄中查找要快得多了！ # 代碼庫地址 [https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)