严蔚敏版数据结构课后习题重点算法.docx

课后算法

线性表

（）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来

两个链表的存储空间不另外占用其它的存储空间。表中不允许有重复的数据。

题目分析

合并后的新表使用头指针  指向， 和  分别是链表  和  的工作指针初始化

为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表  和  均为到达表

尾结点时，依次摘取其中较小者重新链接在  表的最后。如果两个表中的元素相等，只摘

 和  分别是链表  和  的工作指针初始化为相应链表的第一个结点

用  的头结点作为  的头结点

 !"

#$%

取较小者  中的元素，将  链接在  的后面， 指针后移

"#%

取较小者  中的元素，将  链接在  的后面， 指针后移

"相等时取  中的元素，删除  中的元素



&"&

原来两个链表的存储空间不另外占用其它的存储空间。表中允许有重复的数据。

题目分析

合并后的新表使用头指针  指向， 和  分别是链表  和  的工作指针初始化

为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表  和  均为到达表

尾结点时，依次摘取其中较小者重新链接在  表的表头结点之后，如果两个表中的元素相

等，只摘取  表中的元素，保留  表中的元素。当一个表到达表尾结点，为空时，将非

空表的剩余元素依次摘取，链接在  表的表头结点之后。

算法描述



合并链表  和 ，合并后的新表使用头指针  指向

#,&%

 表为空，用 & 指向 ， 指针后移

"#,&%

 表为空，用 & 指向 ， 指针后移

"#$&%

取较小者（包括相等） 中的元素，用 & 指向 ， 指针后移

"&%

取较小者  中的元素，用 & 指向 ， 指针后移

&&

将 & 指向的结点插在 表的表头结点之后

只有同时出现在两集合中的元素才出现在结果表中 合并后的新表使用头指针  指向。

 和  分别是链表  和  的工作指针初始化为相应链表的第一个结点，从第一个结

点开始进行比较，当两个链表  和  均为到达表尾结点时，如果两个表中相等的元素时，

摘取  表中的元素，删除  表中的元素；如果其中一个表中的元素较小时，删除此表中

较小的元素，此表的工作指针后移。当链表  和  有一个到达表尾结点，为空时，依次

删除另一个非空表中的所有元素。

算法描述





 和  分别是链表  和  的工作指针初始化为相应链表的第一个结点



.

/".

%

"#$

.".

%

.".

%

%

!".".%-释放结点空间

!".".%-释放结点空间

.""-置链表尾标记。

"释放  的头结点

%

（）已知两个链表  和  分别表示两个集合，其元素递增排列。请设计算法求出两

同样的形式存储，同时返回该集合的元素个数。

表中的所有元素。

算法描述

/2（3）

-差集的结果存储于单链表  中，3 是结果集合中元素个数，调用时为 4

- 和  分别是链表  和  的工作指针初始化为相应链表的第一个结点

- 为  中  所指结点的前驱结点的指针

#（$&）355%

-0 链表中当前结点指针后移

"-处理 0，1 中元素值相同的结点，应删除

.".%-删除结点

%

（）设计算法将一个带头结点的单链表  分解为两个具有相同结构的链表 、，

其中  表的结点为  表中值小于零的结点，而  表的结点为  表中值大于零的结点（链

表  中的元素为非零整数，要求 、 表利用  表的结点）。

题目分析

1 表的头结点使用原来 0 表的头结点，为 6 表新申请一个头结点。从 0 表的第一个结

点开始，依次取其每个结点 ，判断结点  的值是否小于 4，利用前插法，将小于 4 的结

点插入 1 表大于等于 4 的结点插入 6 表。

/670

1)*-1 表初始化

0- 为工作指针

 !",)*

-暂存  的后继

#$4

11%-将小于 4 的结点链入 1 表前插法

插法

7假定第一个结点中数据具有最大值

!",)*如果下一个结点存在

#77如果  的值大于 7

的值，则重新赋值

%

.7

表的存储空间。

题目分析

算法描述

逆置带头结点的单链表 

)*

 !"

&& 指向3 的后继



3 插入在头结点之后

&

%

（）设计一个算法，删除递增有序链表中值大于  且小于  的所有元素

分别查找第一个值7 的结点和第一个值 ≥7 的结点，再修改指针，删除值

大于 7 且小于 7 的所有元素。

算法描述

"77

首元结点

 !"$7

%查找第一个值7 的结点

#

%#

%

三个域，写出算法 交换  所指向的结点和它的前缀结点的顺序。

题目分析

知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（ 结点，前驱结点，

前驱的前驱结点，后继结点）六条链。

算法描述

8!（）

- 是双向循环链表中的一个结点，本算法将  所指结点与其前驱结点交换。

&"""； ∥ 的前驱的前驱之后继为 

""&""； ∥ 的前驱指向其前驱的前驱。

&""； ∥ 与其前驱交换

"""&； ∥ 的后继的前驱指向原  的前驱

%-算法 ! 结束。

（ ）已知长度为  的线性表  采用顺序存储结构，请写一时间复杂度为 !、空

间复杂度为 !的算法，该算法删除线性表中所有值为  的数据元素。

题目分析