经典数据结构实现与分析:顺序表,单链表,

OldBowl 2020-03-28

本博客在在这里重新总结了一下,当前常用的经典数据结构;这里只针对链表,顺序表,简单树和图进行总结;具体实现请参考:https://github.com/yaowenxu/codes/tree/master/数据结构; 本文章,主要讨论数据结构的性质;以及对这些数据结构的性质;主要是用来知识整理与复习;

顺序表:顺序表是指,将元素顺序地存放在一块连续的内存中;元素间的顺序关系由他们的存储顺序自然表示;c++声明一个数组:int a[10]; 即构建了10个int内存大小(40bytes)的顺序表;

优点:顺序存储,O(1)的时间进行访问;

缺点:当容量不够用时,需要重新构建结构,产生大量内存拷贝;

经典数据结构实现与分析:顺序表,单链表,

链表:链表相对于顺序表可以充分利用计算机内存空间;顺序表是内存上连续的一块位置,其在构建时需要预先知道数据大小来申请连续的内存空间;而在顺序表进行扩充的时候,需要对顺序表进行拷贝迁移,并释放旧空间,产生较多的内存拷贝;而链表可以在空间不足的时候,可以直接声明节点并分配内存,放到链表的末尾;这样可以方便实现内存的灵活管理;

优点:节省内存,动态管理内存;

缺点:只能顺序访问,不能随机访问;

单链表:

保持更新,转载请注明出处;更多内容请关注cnblogs.com/xuyaowen; 

参考博客:

链表

顺序表

相关推荐