数据结构与算法教程 习题答案作者 朱明方 吴及 第3章习题解答.doc

《数据结构与算法教程 习题答案作者 朱明方 吴及 第3章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第3章习题解答3.1与顺序表相比线性链表有哪些优点？又有哪些局限？若线性表为空，对应的链表是否一定没有结点？[解答]与顺序表相比线性链表的明显优点是：①能够灵活利用存储空间，因为它不是依靠线性表中的数据元素在内存中的相互位置关系来表示数据元素间的逻辑关系，因此它的存储空间可以不连续，从而有利于离散空间的充分利用；②由于在线性链表中是通过结点中的指针来指示数据元素之间的逻辑关系的，因此在作插入、删除等操作的时候避免了数据元素平移的操作，从而可以提高运算实现的效率。③由于线性链表所占的存储空间完全由表结点的个数决定，当需要增加或减少表中的数据元素时，表空间很容易扩充和缩小。当然也就不会出现顺序表

2、中存在的表空间扩充困难或者是表空间利用不充分的问题。线性链表的局限主要是：因为它是依靠跟在数据元素后边的指针来表示数据元素之间的逻辑关系的，因此每个数据元素除了本身的存储空间之外还需要有存放指针的空间，即它比顺序表要付出更多的空间代价。当约定线性链表不带表头结点的情况下，线性表为空时，对应的链表也没有结点。3.2链式栈和顺序栈在操作上的主要差别是什么？为什么说对于空闲存储空间的管理适宜采用链式栈来实现？[解答]由顺序栈和链式栈的结构特点可知，顺序栈是顺序存储结构，对其实现基本操作是在连续的存储空间上进行的，因此顺序栈的入栈、出栈、读栈顶元素等操作主要是通过控制栈顶指针的位置来实现的，也就是说

3、，移动栈顶指针是实现顺序栈的基本运算的主要操作。链式栈是一种链式存储结构，因此它具有链式存储结构的基本特点，它的基本运算主要是通过控制栈顶指针和修改栈顶结点的指针域的值来实现，也就是说，链式栈的基本运算主要是通过改变栈顶指针和栈顶结点中的指针来实现的。对于链式存储结构来说，空闲的存储空间为各链表所共享，当有新元素要加入链表时，需要从空闲空间取得结点，再把新元素放入空闲结点，然后把新结点加入到链表中；相反地，当从链表中删除元素时，要释放被删除结点到空闲空间。由于链表中结点的变化是由应用需要决定的，具有明显的随机性，因此在程序运行过程中空闲存储单元的物理位置不一定是连续的，显然要统一管理这些空闲

4、存储单元适合采用链式结构；又因为从空闲存储空间取得结点和向空闲存储空间释放空闲单元，实际上是对空闲存储空间链表执行无条件的删除和插入操作，显然这种不指定结点位置的插入、删除操作在链头进行是最方便的。基于上述原因，在链式存储方式下，对空闲存储空间的管理适合采用链式栈来实现。3.3链式队列与顺序队列在基本操作上的主要差别是什么？你能举出适宜采用链式队列结构的应用例子吗？[解答]顺序队列是一种顺序存储结构，它的数据元素入队和出队等基本运算的主要操作是队尾指针和队头指针的平移；链式队列是一种链式存储结构，它实现基本运算的主要操作是改变队尾指针、队尾结点中的指针和队头指针、队头结点中的指针。16由链式

5、队列的结构特点可知，对于需要采用队列结构而数据元素又不是存放在连续的存储空间中的情况适合采用链式队列结构。例如，一个大型实验室的计算机管理系统，假设上机者采用刷卡方式进入和离开实验室，实验室中的每个机位有唯一的编号，由计算机系统为新进入实验室的上机者分配机位并对上机者信息及其相应的机位进行管理，若没有空闲机位则给出提示信息。当有读者离开实验室时，系统收回该机位并将其管理起来。上述管理要求中涉及到对现场上机者信息和座席信息的管理，实现这些管理所采用的数据结构与管理的具体要求有关。如果对上机者信息的管理按照进入实验室的时间先后来组织，对空闲机位的管理也按照收回的时间顺序来组织，且以“先收回先分配

6、”的原则使用空闲机位，那么可以对机位和上机者信息以结点形式进行管理；以机位编号为关键词组织成存储结点，结点中还包含有上机者信息和其它信息。将仅含空闲机位编号的结点组织成链队列，把含有现场上机者信息的结点构成链表；当有上机者来到时，若链队列不空则从队列头取得一个空闲机位结点，同时把上机者信息填入结点，然后把该结点链入上机者链表的链头；当有人下机离开实验室时，将相应的结点从上机者链表中取下，并将其置为空闲机位再链入空闲机位队列尾。这样的资料组织方式，一方面可以满足以时间为序的要求，另一方面避免了经常的资料移动，可以提高程序执行的效率。3.4仿照循环链表的结构，对线性链表加上表头结点会带来什么好处

7、？试写出实现带表头结点的线性链表的插入与删除运算的算法。[解答]由循环链表的结构特点可知，线性链表带有表头结点的好处是：实现运算时可以使空表和非空表的处理统一，从而使算法简单。这是因为表头结点不存放数据元素，无论线性表是否为空，线性链表中的表头结点总是存在的，因此对线性链表中第一个结点位置的插入、删除操作和在其它位置上的操作是一样的，不必分别处理。在不带表头结点的情况下，因为对表头位置执行插入、删除操作时都涉