线性表存储结构的选择

  1.从存储的角度考虑:

  • 顺序表的存储空间是静态分布的,在程序执行之前必须明确规定它的规模,也就是说事先对MAXSIZE要有合适的设计,过大造成浪费,过小容易溢出。
  • 点线性表的长度或存储规模难以估计时,不易采用顺序表;链表不用事先估计存储规模,链表存储密度低,(存储密度是指一个节点中数据元素所占的存储单元和整个节点所占存储单元之比。
  • 链式存储结构的存储密度小于1。

  2.从运算的角度考虑:

  • 在顺序表中按序号访问ai的时间复杂度是O(1),而链表中按序号查找的时间复杂度是O(n),如果经常做的运算是按顺序查找的,则顺序表优于链表;在顺序表中中插入删除运算时平均移动表中一半的元素,档数据量大且表较长,这一点哼重要;在链表中做插入、删除操作,虽然要找插入删除的位置,但操作主要是比较操作,所以从运算的角度考虑选用链表更为合适。

  3.从环境的角度考虑:

  • 顺序表容易实现,任何高级语言中都有数组类型,链表的操作时基于指针的,相对来讲,链表更简单

通常较稳定的顺序表选择顺序存储结构,而需要做复杂插入删除(动态性)较强的线性表应选择链式存储结构

原文地址:https://www.cnblogs.com/zhang-jiao/p/9647763.html