比较顺序存储结构和链式存储结构

1、1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答：顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（=1）,存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变

2、化较大，且其主要操作是插入、删除操作，则采用链表。顺序表与链表的比较基于空间的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度<1基于时间的比较存取方式顺序表可以随机存取，也可以顺序存取链表是顺序存取的插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针顺序表和链表的比较顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：顺序表丨链表11rII基I分丨静态分配。程序执行之前

3、必须明确丨动态分配只要内存空间尚有空闲，I于I配I规定存储规模。若线性表长度n变I就不会产生溢出。因此，当线性表I空I方I化较大，则存储规模难于预先确定I的长度变化较大，难以估计其存储I间I式I估计过大将造成空间浪费，估计太I规模时，以采用动态链表作为存储I考II小又将使空间溢出机会增多。I结构为好。虑II11I储I易于事先确定其大小时，为了节约I密I存储空间，宜采用顺序表作为存储I度I结构。基I存丨随机存取结构，对表中任一结点都顺序存取结构，链表中的结点，需于|取I可在O(1)时间内直接取得时I方I线性表的操作主要是进行查找，很间I法I少做插入和删除操作时，采用顺序考II表做存储结构为宜。虑

4、III插I在顺序表中进行插入和删除，平均I入I要移动表中近一半的结点，尤其是I删I当每个结点的信息量较大时，移动I除I结点的时间开销就相当可观。I操II作I于|取I可在O(1)时间内直接取得时I方I线性表的操作主要是进行查找，很间I法I少做插入和删除操作时，采用顺序考II表做存储结构为宜。虑III插I在顺序表中进行插入和删除，平均I入I要移动表中近一半的结点，尤其是I删I当每个结点的信息量较大时，移动I除I结点的时间开销就相当可观。I操II作II从头指针起顺着链扫描才能取得。II在链表中的任何位置上进行插入和II删除，都只需要修改指针。对于频II繁进行插入和删除的线性表，宜采II用链表做存储结构。若表的插入和I丨删除主要发生在表的首尾两端，则I采用尾指针表示的单循环链表为宜为什么在单循环链表中设置尾指针比设置头指针更好答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是0(1)。若用头指针来表示该链表，则查找终端结点的时间为0(n)。在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一