从全局视角看数据结构

从全局视角看数据结构

计算机的本质就是为了处理数据，数据运算的时候是放在内存中的，由于计算机的特性，储存只有两种方式：

顺序结构：存储在连续的内存上。链式结构：存储在不连续的内存上。

物理结构

顺序结构

顺序结构的原始模型就是数组，由于存放的都是同一种数据，比如int，每个数据占用的内存单元是一致的，那么当我们知道首地址之后就可以推导出任意位置的地址（等差数列）。这就是随机访问。

顺序结构的优势在于随机访问很快。

但是由于需要连续内存，当我们插入、删除一个元素的时候，就要移动后面的元素。

顺序结构的劣势就在于插入删除比较慢。

链式结构

链式结构的原始模型是链表，我们增加一个指针记录下一个元素的地址，这样就不用放在连续的内存上，当我们插入删除的时候，只需要处理前后元素即可。

链式结构的优势在于新增、删除很快。

但是由于不连续，我们无法用公式推导出第N个元素的位置，随机访问只能通过遍历。

链式结构的劣势在于随机访问很慢。

小结

由于计算机设计的限制，我们只有两种物理结构去存储数据，如果有一天我们的计算机模型变化了，一切都会跟着变。

逻辑结构

怎么放内存是一回事，怎么处理他们又是一回事，怎么处理就叫逻辑结构。

比如：

栈：先进后出。队列：先进先出。树：将链表从一维拉到了二维，是一对多。图：也是拉到了二维，是多对多。

逻辑结构都可以用两种物理结构去实现，只是有优劣之分。

为了解决物理结构的劣势，人们也发明了很多算法去优化数据结构。

数据结构是为算法服务的，算法要作用在特定的数据结构之上。

比如，为了解决链表的遍历慢，发明了跳跃表、二叉树等。为了解决数组的插入快慢问题，发明了散列表+拉链法。

总之，都是充分利用数组的随机访问快，链表的插入、删除快。

总结

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。