试题详情
简答题线性表的两种存储结构各有哪些优缺点?
  • 线性表分为“数组,静态存储结构”和“链表,动态存储结构”。
    数组,静态存储结构,可以随机访问任意一个成员,具有访问效率高,访问结点的时间复杂度为O(1)。还有对于固定元素个数的场合下占用空间小的优点。但是插入及删除数组元素,需要大量移动数据,维护效率低,时间复杂度为O(n)。元素个数不确定时需要以上限申请数组,会造成浪费。
    链表,动态存储结构,具有适合元素个数不确定且变化大的场合,可以随时申请或归还存储空间,且插入或删除结点时,只要修改链接的指针,不需移动数据结点,时间复杂度为O(1)。但是不能随机访问数据结点,需要遍历链表,时间复杂度为O(n)。
  • 关注下方微信公众号,在线模考后查看

热门试题