Question

叙述线性表两种存储结构各自的优缺点。

Answer 1

【答案】：线性表有两种存储结构，它们是顺序存储结构(简称顺序表)和链式存储结构(简称链表)。
顺序表有如下特点：因为顺序表中各元素物理位置隐含其逻辑关系，所以不需要额外的存储空间来维系线性表的逻辑结构；又因为顺序表是用数组来存放线性表中各元素的(即连续存储)，所以对线性表的存取很容易，但对线性表进行插入或删除操作时需移动大量元素，消耗时间较多。另外，顺序表需事先分配存储空间，若线性表最大长度较难确定，则必须按线性表最大可能长度分配空间。若线性表长度变化较大，则使存储空间不能得到充分利用；如果存储空间分配过小，又可能导致溢出。
链表有如下特点：它不要求逻辑上相邻的元素在物理位置上也相邻，为了表示出每个元素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示其直接后继存储位置的信息，因此，链表占有较多的存储空间。线性链表的插入或删除操作较为容易，不需要移动大量元素。另外，链表结点的存取总是从表头开始。