顺序表与链表的异同点.ppt

《顺序表与链表的异同点.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、顺序表与链表的异同点顺序表顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定起长度，一旦分配内存，则在使用中不可以动态的更改。他的优点是访问数据是比较方便，可以随即的访问表中的任何一个数据。链表链表是通过指针来描述元素关系的一种数据结构，他可以是物理地址不连续的物理空间。不能随即访问链表元素，必须从表头开始，一步一步搜索元素。它的优点是：对于数组，可以动态的改变数据的长度，分配物理空间。存储空间的差异顺序表的存储空间是静态的，要求预先分配空间，程序执行之前必须明确规定

2、存储的规模。（即事先对MAXSIZE要有合适的设定）链表的存储空间是动态分配的，只要是有内存空间，就可动态申请空间，不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构较好运算时间的差异顺序存储结构是一种随机存取结构，便于元素的随机访问；链式结构是一种非随机存取结构，对任一结点的操作都必须是从头指针开始顺着链扫描才能取得;但是当插入、删除运算较多时，对顺序表而言意味着大量数据元素的移动，而在链表中的任意位置上进行插入和删除，只需修改指针变量值即可因此对于只进行

3、查找的运算而很少做到插入好删除运算的应用，宜采用顺序存储结构；而需要经常频繁地进行元素的插入和删除运算的线性表，应采用链式存储结构。程序设计语言顺序表容易实现，在任何高级语言中都有数组类型；链表的实现要依靠于指针类型，但并不是所有高级语言都能提供指针类型。两者的优点顺序表：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。链表(1)插入、删除时，只要找到对应前驱结点，修改指针即可，无需移动元素；(2)采用

4、动态存储分配，不会造成内存浪费和溢出。两者的缺点顺序表（1）在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出链表（1）在有些语言中，不支持指针，不容易实现；（2）需要用额外空间存储线性表的关系，存储密度小（3）不能随机访问，查找时要从头指针开始遍历。谢谢观看