线性表可以用于顺序表或链表存储，试问：（1）两种存储

[问答题]

线性表可以用于顺序表或链表存储，试问：

（1）两种存储表示各有哪些主要优缺点？

（2）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？

（3）若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应选用哪种存储表示？为什么？

不忘初心201804220006548

1.两种存储表示各有哪些主要优缺点？

顺序存储：逻辑地址和物理地址都连续，存取效率高、不易扩充、修改效率低

链式存储：逻辑地址连续、物理地址不连续，存取效率低、动态分配扩缩、修改效率高。

查找、插入、删除操作：顺序表相当于数据可以采用下表的形式进行访问，因此它的查找元素的时间复杂度就是O（1），想找哪个数据直接按下标就可以直接查找；链表在查找一个元素的时候必须从头指针依次往下指，因此时间复杂度是O（n）；插入和删除：顺序表在插入或者删除一个元素的时候，时间复杂度为O（n），因为每插入一个元素，原顺序表这个位置后面的所有元素都要依次往后移动一位；链表：在插入或者删除一个元素的时间复杂度为O（1），因为是通过指针指向下一个元素；

空间复杂度：顺序表因为每分配一个空间，这个空间里面只存放对应大小的数据；链表因为每分配一个空间，里面除了存放数据以外还存放有指向下一个数据的指针，因此存储空间的利用效率没有顺序表的利用效率高，尤其是存放一些数据小的情况下。

2.如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变，在此情况下，应选用哪种存储表示？为什么？

链式存储，因为在处理过程中各表的长度会发生动态变化，顺序表在运行时是不支持动态的扩缩容的。同样，表的总数发生变化，采用链表存储的插入和删除的效率是比顺序表的插入和删除操作高。

3.若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应选用哪种存储表示？为什么？

与2回答的解释相反，此处应该采用顺序存储，因为顺序存储的存取速度快。

发表于 2019-09-08 21:17:37 回复(0)

提交观点

问题信息

上传者：小小

难度：

1条回答 11收藏 4564浏览

线性表可以用于顺序表或链表存储，试问：（1）两种存储

问题信息

热门推荐

相关试题

线性表可以用于顺序表或链表存储，试问： （1）两种存储

问题信息

热门推荐

相关试题

线性表可以用于顺序表或链表存储，试问：（1）两种存储