# 如何選擇數據結構-電話薄的設計
現在大家都用手機,存儲和查詢電話號碼十分方便。一個電話薄看似簡單,這里面也能映射出選擇合適的數據結構的重要性。
### 方式一:順次添加
當我們有一個紙質電話薄,在得到一個新號碼時,只能從上往下記錄,這種方式對寫一條新數據來說十分方便,例如:
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)