C语言版《数据结构与算法分析》习题答案详解

需积分: 39 199 浏览量更新于2024-07-22 收藏 247KB PDF 举报

《数据结构与算法分析：C语言版》（DataStructures and Algorithm Analysis in C, second edition）是一本由Mark Allen Weiss编著的教材，专为理解和掌握数据结构及算法设计提供详尽的指导。本书的第二版包含了书中大部分习题的答案，适用于那些在学习过程中寻求帮助的学生，特别是对于使用C语言进行实践的读者。答案反映了该书初次印刷时的内容，主要针对理论探讨和概念解析，而非深入的编程作业。课程内容涵盖了广泛的主题： 1. 第一章：介绍 - 这部分提供了对数据结构和算法分析的总体概述，包括其在计算机科学中的核心地位和应用背景。 2. 第二章：算法分析 - 着重于理解算法效率的关键指标，如时间复杂度和空间复杂度，以及如何评估不同算法的性能。 3. 第三章：列表、栈和队列 - 数据结构的基础构建块，介绍了顺序存储结构的实现和操作，如线性表、栈和队列的基本操作和应用场景。 4. 第四章：树 - 深入讨论了二叉树、二叉搜索树等，涉及节点组织、遍历和树形数据结构的应用。 5. 第五章：哈希（散列） - 学习如何利用哈希函数实现高效的数据查找和存储，以及解决冲突的方法。 6. 第六章：优先队列（堆） - 堆数据结构及其在实现优先级队列中的应用，如最小堆和最大堆的构造和操作。 7. 第七章：排序 - 探讨各种排序算法，如冒泡排序、快速排序和归并排序，以及它们的时间复杂度和适用场景。 8. 第八章：并查集（Disjoint Set ADT） - 描述了并查集作为一种抽象数据类型，常用于解决集合合并问题。 9. 第九章：图算法 - 针对有向图和无向图的遍历策略（如深度优先搜索和广度优先搜索）、最短路径算法（如Dijkstra和Floyd-Warshall）等进行讲解。值得注意的是，该手册中并未包含可能的编程练习题以及参考文献中给出的解决方案，而且提供的程序通常是伪C代码，旨在清晰地展示思路，而不是完整的实际可执行代码。如果你在阅读过程中发现任何错误，可以通过weiss@fiu.edu向作者报告。感谢Grigori Schwarz和Brian Harvey对前一版本的反馈。《数据结构与算法分析课后答案》是一份宝贵的参考资料，可以帮助学生巩固理论知识，提升编程技能，并通过实际练习来深化对数据结构和算法的理解。

_______________________________________________________________________________

/* This code can be made more abstract by using operations such as */

/* Retrieve and IsPastEnd to replace L1Pos->Element and L1Pos != NULL. */

/* We have avoided this because these operations were not rigorously deﬁned. */

List

Intersect( List L1, List L2 )

{

List Result;

Position L1Pos, L2Pos, ResultPos;

L1Pos = First( L1 ); L2Pos = First( L2 );

Result = MakeEmpty( NULL );

ResultPos = First( Result );

while( L1Pos != NULL && L2Pos != NULL )

{

if( L1Pos->Element < L2Pos->Element )

L1Pos = Next( L1Pos, L1 );

else if( L1Pos->Element > L2Pos->Element )

L2Pos = Next( L2Pos, L2 );

else

{

Insert( L1Pos->Element, Result, ResultPos );

L1 = Next( L1Pos, L1 ); L2 = Next( L2Pos, L2 );

ResultPos = Next( ResultPos, Result );

}

return Result;

}

_______________________________________________________________________________

3.5 Fig. 3.4 contains the code for Union.

3.7 (a) One algorithm is to keep the result in a sorted (by exponent) linked list. Each of the MN

multiplies requires a search of the linked list for duplicates. Since the size of the linked list

is O

(MN

), the total running time is O

(b) The bound can be improved by multiplying one term by the entire other polynomial, and

then using the equivalent of the procedure in Exercise 3.2 to insert the entire sequence.

Then each sequence takes O

(MN

), but there are only M

of them, giving a time bound of

(MN

log MN

) solution is possible by computing all MN

pairs and then sorting by

exponent using any algorithm in Chapter 7. It is then easy to merge duplicates afterward.

(d) The choice of algorithm depends on the relative values of M

and N

. If they are close,

then the solution in part (c) is better. If one polynomial is very small, then the solution in

part (b) is better.

-9-

then if M'

> N

/ 2, passing the potato appropriately in the alternative direction. This

requires a doubly linked list. The worst-case running time is clearly O

min

, N

)),

although when these heuristics are used, and M

and N

are comparable, the algorithm might

be signiﬁcantly faster. If M

= 1, the algorithm is clearly linear. The VAX/VMS C

compiler’s memory management routines do poorly with the particular pattern of

free

sin

this case, causing O

log N

) behavior.

3.12 Reversal of a singly linked list can be done nonrecursively by using a stack, but this

requires O

) extra space. The solution in Fig. 3.5 is similar to strategies employed in gar-

bage collection algorithms. At the top of the while

loop, the list from the start to Pre-

viousPos

is already reversed, whereas the rest of the list, from CurrentPos

to the end, is

normal. This algorithm uses only constant extra space.

_______________________________________________________________________________

/* Assuming no header and L is not empty. */

List

ReverseList( List L )

{

Position CurrentPos, NextPos, PreviousPos;

PreviousPos = NULL;

CurrentPos = L;

NextPos = L->Next;

while( NextPos != NULL )

{

CurrentPos->Next = PreviousPos;

PreviousPos = CurrentPos;

CurrentPos = NextPos;

NextPos = NextPos->Next;

}

CurrentPos->Next = PreviousPos;

return CurrentPos;

}

Fig. 3.5.

_______________________________________________________________________________

3.15 (a) The code is shown in Fig. 3.6.

(b) See Fig. 3.7.

the Chapter 11 references.

3.16 (c) Delete

takes O

) and is in two nested for loops each of size N

, giving an obvious

) bound. A better bound of O

) is obtained by noting that only N

elements can be

deleted from a list of size N

, hence O

) is spent performing deletes. The remainder of

the routine is O

), so the bound follows.

(d) O

-11-

剩余68页未读，继续阅读

lulubuhaore

粉丝: 0
资源: 1

C语言版《数据结构与算法分析》习题答案详解

西安电子科技大学《算法设计与分析》上机题

2019年杭州电子科技大学数据结构与组成原理考研真题

数据结构与算法分析习题答案

数据结构与算法分析 c++语言描述 课后答案

数据结构与算法分析 c语言描述(原书第2版)课后习题参考答案

数据结构与算法c语言课后习题

数据结构课后习题答案

怎样学习数据结构与算法这门课

数据结构(java语言描述)第三版课后习题答案

数据结构的习题在哪里

最新资源

数据结构与算法分析 c++语言描述课后答案