牛骨文教育服务平台(让学习变的简单)

本章主要介绍了下线性表的两种存储结构——顺序存储和链式存储,然后引入了大量的练习题来巩固这两种存储方式。
继续使用第1章线性表 中的配图来比较下顺序表和链表。

线性表的分类

一.顺序表和链表的比较

1.1存取方式

  • 顺序表既可以顺序存取,又可以随机存取;
  • 链表只能从表头到表尾顺序存取。

1.2逻辑结构与物理结构(存储方式)

  • 顺序表中,逻辑上相邻的元素,其对应的物理位置亦相邻;
  • 链表中,逻辑上相邻的元素,物理位置不一定相邻,其对应的逻辑关系是通过指针链接形成的。
    注:此处应注意区别存储方式和存取方式的基本定义。
      存取方式指的是读取数据的方式,比如随机存取,离散存取等;
      存储方式指的是数据的物理结构,比如顺序存储,离散存储等。

1.3基本操作

1.3.1查找操作

  • 按值查找

顺序表无序的情况下,查找时间复杂度为O(n);若有序,查找时间复杂度为O(1)。
链表无论是否有序,查找时间复杂度均为O(n)。

  • 按序号查找

顺序表支持随机访问,时间复杂度为O(1);
链表需要从表头遍历到表尾,时间复杂度为O(n)。

1.3.2插入删除操作

顺序表需要移动大量元素,时间复杂度为O(n);
链表只需修改节点的指针域即可,时间复杂度为O(1)。

1.4空间分配

顺序表在创建时就要求分配足够大的存储空间。
 采用静态分配时,若分配空间过大,则会造成浪费严重;若分配过小,则会造成溢出;
 采用动态分配时,扩充需要移动大量元素,造成操作效率低下;
链表仅在需要的时候申请分配,只要内存空间足够便可完成分配。

二.顺序表和链表在现实生活中的选择

根据上述顺序表和链表的比较,使得我们更加熟悉了线性表的基本操作。对此我们变可以根据自身的需求来选择合适的线性表结构。下面说明几点参考标准:

2.1基于存储的考虑

对于线性表的长度或存储规模难以估计时,不宜采用顺序表;链表不用事先估计存储规模,但链表的存储密度比较低,显然采用链式存储的线性表存储密度是小于1的。

2.2基于运算的考虑

当我们在线性表操作中涉及到大量的按序号查找值的操作时,采用顺序表无疑是一种不错的选择,顺序表因为可以实现离散存取,时间复杂度仅为O(1);而链表因为必须使用顺序存取,时间复杂度为O(n)。
如果实际使用中使用到了大量的插入和删除操作时,顺序表平均需要移动表中一半的元素,最坏时间复杂度为O(1);而链表做相同的操作时,时间复杂度仅为O(1)。明显,我们会选择链表。

2.3基于环境的考虑

顺序表容易实现,任何高级语言中都有数组类型;而链表的操作是基于指针的,有些高级语言中并不具备指针。

总之,究竟选择顺序表还是链表还是需要根据自身需要来确定,只有合适的才是最好的。