# 如何选择数据结构-电话薄的设计 现在大家都用手机，存储和查询电话号码十分方便。一个电话薄看似简单，这里面也能映射出选择合适的数据结构的重要性。 ### 方式一：顺次添加 当我们有一个纸质电话薄，在得到一个新号码时，只能从上往下记录，这种方式对写一条新数据来说十分方便，例如： 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)