python做的大型网站,临沂做网站电话,企业网站管理系统信得过y湖南岚鸿怎么样,网站建设收费流程小肥柴慢慢学习数据结构笔记#xff08;C篇#xff09;#xff08;5-4 中场小结#xff09; 目录5-14 再看数据结构的基础问题5-15 接下来关于Tree你还需要学习和了解的内容参考文献和资料 目录
5-14 再看数据结构的基础问题
假设前面讨论的所有内容大家都已经自己编码实… 小肥柴慢慢学习数据结构笔记C篇5-4 中场小结 目录5-14 再看数据结构的基础问题5-15 接下来关于Tree你还需要学习和了解的内容参考文献和资料 目录
5-14 再看数据结构的基础问题
假设前面讨论的所有内容大家都已经自己编码实现了一遍很容易作出以下推断 1数据结构底层的具体存储结构无外乎两种即“数组”和“链表”也就是很多资料/博客中描述的“顺序存储”和“链式存储”。 兜兜转转咱们的讨论还是回到了第一次讨论数据结构的一个点即“数据的存储与组织”算是扣题了。 2使用数组的优点检索和修改快使用数组的缺点插入和删除操作慢因为需要“挪位置”。 3使用链表的优点插入和删除操作快因为无需挪位置实用链表的缺点检索和修改慢。 【注】此处的“修改”可以看做一种形式的“计算”话说回来计算机科学与技术的核心不就是数据的“存储”与“计算”吗巧不巧哈哈哈…
而造成数组和链表优缺点相反的关键在于寻址机制的不同有兴趣的话可以自行研究一下两者的汇编实现引用他人的描述 数组可以用基地址和偏移量访问的有专门的汇编代码move指令。而链表对不起单周机器指令不存在。 由此可知数据结构在使用过程中应该根据实际需要选择合适的实现形式。但我们还是不禁要提出一个疑问
【Q】有没有可能存在一种数据结构它能够集合顺序存储和链式存储的优点呢 【A】有大家最熟悉的就是hash散列表且这个数据结构对应的数学理论研究和具体实现还在不断进化譬如在JDK源码中HashMap的实现就非常有意思 1它不仅能通过计算key值实现数据快速的查、取和尽可能的均匀、分散的存储。 2它还能根据同key节点上元素数量的变化动态地将存储模式在单链结构和树形结构之间灵活切换完全满足性能要求。
当然这是后续章节需要讨论的内容大家可以期待一下。
5-15 接下来关于Tree你还需要学习和了解的内容
主线任务先告一段落对初学者我个人建议先绕后面的章节学习散列、堆、并查集和图论初步因为从这儿开始之后的数据结构的复杂度包括具体实现和数学推导和学习难度陡增需要投入更多的精力反复琢磨但正式这些复杂的工具却往往是实际工程应用中最实用的基础部件且在面试中属于面试官摸底的必选题库属于典型的手搓费劲、用起来真香。以下有趣的高级数据结构我们会逐一开贴讨论莫急讲真数学推导已经把我捶打成小丑了。
1有趣的伸展树Splay Tree 2经典的红黑树RBTree 3B树、B树 4前缀树Trie Tree 字典树 5k-d树 6AA树 …待补充
【注】 1前四个是找工作的朋友必须掌握的因为它们真的非常经典。 2treap树放在Heap堆中学习、讨论。
欲速不达慢慢熟悉慢慢打磨。
参考文献和资料
[1] labuladong相关博客 [2] liuyubobo相关博客 [3] 黑皮书 [4] 为什么数组索引数据那么快速、有效 [5] 玩转《数据结构》顺序表和链表的比较 [6] 顺序存储和链式存储
