数据结构课后习题答案第二章 线性表.pdf
版权申诉
123 浏览量
2022-11-12
13:10:47
上传
评论
收藏 710KB PDF 举报
第二章 线性表
2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
并说明头指针和头结点的作用。
答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识
一个链表。如链表 H，链表 L 等，表示链表中第一个结点的地址存放在 H、L 中。
头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表
表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该
指针域为空。
开始结点指第一个元素结点。
头指针的作用是用来惟一标识一个单链表。
头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链
表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2.2 填空题
1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移
动的元素个数与（表长和该元素在表中的位置）有关。
2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻
的元素的物理位置（不一定）相邻。
3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的
链域的值）指示。
4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。
2.3 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性
表的存储结构，通常有以下几方面的考虑：
1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小
时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计
其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作
时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删
除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在
1
剩余29页未读，继续阅读
资源评论
