数据结构（C语言版）严蔚敏课后习题答案_时间复杂度的计算例题及答案

数据结构

需积分: 50 115 浏览量更新于2023-06-03 评论 1 收藏 1.49MB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

第 2 章线性表

．算法设计题

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

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

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



用  的头结点作为  的头结点

 !"

#$%

"#%

"相等时取  的元素，删除  的元素



&"&%

%

'(插入剩余段

"释放  的头结点%

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

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

)

初始化

用  的头结点作为  的头结点

*+

 !",,

#-&%

"#-&%

"#$&%

"&%

&&插入

%

"释放  的头结点%

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

与 / 的交集，并存放于 . 链表中。



""0设工作指针  和 ；

用  的头结点作为  的头结点

while

if0交集并入结果表中。



)")%

elseif$)")%

else)")%

while)")%0释放结点空间

while)")%0释放结点空间

)""0置链表尾标记。

"0注：本算法中也可对 / 表不作释放空间的处理

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

个集合 . 和 /的差集（即仅由在 . 中出现而不在 / 中出现的元素所构成的集合），并以同

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

void12（.，/，3）

0. 和 / 均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差

集，存储于单链表 . 中，3 是结果集合中元素个数，调用时为 4

.； ∥ 和 & 分别是链表 . 和 / 的工作指针。

&/； .； ∥ 为 . 中  所指结点的前驱结点的指针。

while（-)""&-)""）

if（$&）；；355；%0. 链表中当前结点

指针后移。

elseif（&）&&； ∥/ 链表中当前结点指针后移。

else； ∥处理 .，/ 中元素值相同的结点，应删除。

)； ； ")；%0删除结点

（5）设计算法将一个带头结点的单链表 . 分解为两个具有相同结构的链表 /、6，其

中 / 表的结点为 . 表中值小于零的结点，而 6 表的结点为 . 表中值大于零的结点（链表 .

的元素类型为整型，要求 /、6 表利用 . 表的结点）。

（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

7"89:

#*+)*+

8假定第一个结点中数据具有最大值



!"-*+如果下一个结点存在

#88



)8

（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表

的存储空间。



逆置带头结点的单链表 

*+

 !"

&& 指向3 的后继



3 插入在头结点之后

&

%

（8）设计一个算法，删除递增有序链表中值大于 8 且小于 8 的所有元素

（8 和 8 是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

"88

首元结点

 !"$8

%查找第一个值8 的结点

#

 !"$8

查找第一个值 ≥8的结点

&修改指针

 !"&-

&"&&%释放结点空间

%#

（9）已知  指向双向循环链表中的一个结点，其结点结构为 、、 三

个域，写出算法 !交换  所指向的结点和它的前缀结点的顺序。

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

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

void7!（）

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

&""；

&"""； ∥ 的前驱的前驱之后继为 

""&""； ∥ 的前驱指向其前驱的前驱。

&""； ∥ 的前驱的后继为  的后继。

&""； ∥ 与其前驱交换

"""&； ∥ 的后继的前驱指向原  的前驱

"&； ∥ 的后继指向其原来的前驱

%0算法 ! 结束。

（10）已知长度为  的线性表 . 采用顺序存储结构，请写一时间复杂度为 O、空间

复杂度为 O;的算法，该算法删除线性表中所有值为 8 的数据元素。

<题目分析=在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第 

个元素，第 5; 至第  个元素要依次前移）。本题要求删除线性表中所有值为 8 的数

据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（;，>），

从两端向中间移动，凡遇到值 8 的数据元素时，直接将右端元素左移至值为 8 的数

据元素位置。

void1"（7"89:.<=，int ）

0. 是有  个元素的一维数组，本算法删除 . 中所有值为 8 的元素。

;；>；∥设置数组低、高端指针（下标）。

while（$>）

剩余45页未读，继续阅读

C1zyh

粉丝: 0
资源: 1

会员权益专享

数据结构（C语言版）严蔚敏课后习题答案

评论0

会员权益专享

最新资源

数据结构（C语言版）严蔚敏课后习题答案

评论0

严蔚敏教材 习题集答案\第五章 数组和广义表.

数据结构(C语言版)第2版习题答案—严蔚敏

数据结构（C语言版） 课后习题答案 严蔚敏

数据结构c语言版严蔚敏第一版

数据结构c语言版第二版课后答案

严蔚敏数据结构第二版课后题答案

数据结构严蔚敏课后题

数据结构课后题严蔚敏

数据结构 c语言第二版

数据结构严蔚敏第二版

数据结构严蔚敏pdf教材

严蔚敏数据结构第六章

数据结构线性表编程题

数据结构（严蔚敏）课后答案

数据结构习题集答案（C语言版严蔚敏）

数据结构题集严蔚敏课后答案

《数据结构c语言版》答案第二版严蔚敏

数据结构 课后答案 严蔚敏

严蔚敏《数据结构(c语言版)习题集》答案

数据结构（C版）-严蔚敏-课后习题答案.pdf

会员权益专享

最新资源

严蔚敏教材习题集答案\第五章数组和广义表.

数据结构（C语言版）课后习题答案严蔚敏

数据结构课后答案严蔚敏