小肥柴慢慢手写数据结构（C篇）（5-4 中场小结）

目录

5-14 再看数据结构的基础问题

假设前面讨论的所有内容大家都已经自己编码实现了一遍，很容易作出以下推断：

（1）数据结构底层的具体存储结构无外乎两种，即：“数组”和“链表”，也就是很多资料/博客中描述的“顺序存储”和“链式存储”。

兜兜转转，咱们的讨论还是回到了第一次讨论数据结构的一个点，即：“数据的存储与组织”，算是扣题了。

（2）使用数组的优点：检索和修改快；使用数组的缺点：插入和删除操作慢，因为需要“挪位置”。

（3）使用链表的优点：插入和删除操作快，因为无需挪位置；实用链表的缺点：检索和修改慢。

【注】此处的“修改”，可以看做一种形式的“计算”；话说回来，计算机科学与技术的核心，不就是数据的“存储”与“计算”吗？巧不巧？哈哈哈…

而造成数组和链表优缺点相反的关键在于寻址机制的不同，有兴趣的话可以自行研究一下两者的汇编实现，引用他人的描述：

数组可以用基地址和偏移量访问的，有专门的汇编代码，move指令。而链表，对不起，单周机器指令不存在。

由此可知，数据结构在使用过程中应该根据实际需要选择合适的实现形式。但我们还是不禁要提出一个疑问：

【Q】有没有可能存在一种数据结构，它能够集合顺序存储和链式存储的优点呢？
【A】有，大家最熟悉的就是hash（散列表），且这个数据结构对应的数学理论研究和具体实现还在不断进化，譬如在JDK源码中HashMap的实现就非常有意思：
（1）它不仅能通过计算key值实现数据快速的查、取和尽可能的均匀、分散的存储。
（2）它还能根据同key节点上元素数量的变化，动态地将存储模式在单链结构和树形结构之间灵活切换，完全满足性能要求。

当然，这是后续章节需要讨论的内容，大家可以期待一下。

5-15 接下来关于Tree你还需要学习和了解的内容

主线任务先告一段落，对初学者我个人建议先绕后面的章节学习散列、堆、并查集和图论初步，因为从这儿开始之后的数据结构的复杂度（包括具体实现和数学推导）和学习难度陡增，需要投入更多的精力反复琢磨；但正式这些复杂的工具却往往是实际工程应用中最实用的基础部件，且在面试中属于面试官摸底的必选题库，属于典型的手搓费劲、用起来真香。以下有趣的高级数据结构，我们会逐一开贴讨论，莫急（讲真，数学推导已经把我捶打成小丑了）。

（1）有趣的伸展树（Splay Tree）
（2）经典的红黑树（RBTree）
（3）B树、B+树
（4）前缀树（Trie Tree 字典树）
（5）k-d树
（6）AA树
…（待补充）

【注】
（1）前四个是找工作的朋友必须掌握的，因为它们真的非常经典。
（2）treap树放在Heap（堆）中学习、讨论。

欲速不达，慢慢熟悉，慢慢打磨。

参考文献和资料

[1] labuladong相关博客
[2] liuyubobo相关博客
[3] 黑皮书
[4] 为什么数组索引数据那么快速、有效？
[5] 玩转《数据结构》顺序表和链表的比较
[6] 顺序存储和链式存储