C语言版数据结构与算法分析解题指南（Mark Allen Weiss）

需积分: 10 63 浏览量更新于2024-07-06 1 收藏 233KB PDF 举报

"Data Structures and Algorithm Analysis in C (2nd Edition) Solutions Manual by Mark Allen Weiss" 本书是Mark Allen Weiss编写的《数据结构与算法分析》第二版的解答手册，主要针对该教材中的练习题提供了答案。解答反映了书中第一次印刷时的状态。书中涵盖了一到九章的主要内容，包括但不限于： 1. 第一章：引言这部分可能介绍了数据结构和算法分析的基本概念，以及学习这些主题的重要性。通常，引言会激发读者对后续章节的兴趣，并为后续的学习提供背景知识。 2. 第二章：算法分析算法分析是理解算法效率的关键，本章可能涉及时间复杂度和空间复杂度的概念，以及如何通过大O记法来描述算法的运行时间。可能会讨论如何分析循环和其他基本操作的效率。 3. 第三章：列表、栈和队列这些是基础数据结构，列表可能包含线性表和链表的讨论，栈（后进先出LIFO）和队列（先进先出FIFO）则涉及它们的操作和应用，如递归、回溯、缓冲区等。 4. 第四章：树树数据结构包括二叉树、平衡树（如AVL树和红黑树）、堆等。这部分可能会讨论树的插入、删除、查找操作，以及它们在搜索和排序问题中的应用。 5. 第五章：哈希哈希表允许快速查找和存储元素，本章可能探讨了哈希函数的设计、冲突解决策略（开放寻址法和链地址法）以及哈希表的性能分析。 6. 第六章：优先队列（堆）堆是一种能高效执行最大或最小元素提取的结构，常用于实现优先队列。本章会介绍堆的构造、插入、删除等操作，以及如何用堆实现heapify算法。 7. 第七章：排序涵盖各种排序算法，如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等，分析它们的效率和适用场景。 8. 第八章：不相交集合ADT（Disjoint Set）不相交集合数据结构用于处理元素分组的问题，本章可能包括并查集的路径压缩和按秩合并优化。 9. 第九章：图算法图算法涵盖Dijkstra算法、Floyd-Warshall算法、拓扑排序、Prim算法（最小生成树）和Kruskal算法等，用于解决网络流、最短路径等问题。解答手册没有包含编程作业和那些答案已经在章节末尾引用的问题。程序示例用的是伪C代码，而不是完全规范的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页未读，继续阅读

頎祐

粉丝: 0
资源: 1

C语言版数据结构与算法分析解题指南（Mark Allen Weiss）

Data Structures and Algorithm Analysis in C++ 4th 原版pdf by Weiss

Data Structures and Algorithm Analysis in C++ (Mark Allen Weiss)

Data Structures and Algorithm Analysis in C - Mark Allen Weiss

data structures and algorithm analysis in c.pdf

[]_Abaqus_analysis_user's_manual,_volume_1,_versio(z-lib.org).pdf

Data Structures and Algorithm Analysis in C(2nd) Problem Solution

[]_Dassault_Systemes_Inc._Modeling_Fracture_and_Fa(z-lib.org).pdf

[]_Dassault_Systemes_Inc._Introduction_to_Abaqus(z-lib.org).pdf

Source Code for "Data Structures and Algorithm Analysis in C(2nd)"

Data-Structures-and-Algorithm-Analysis-Solutions:Mark Allen Weiss撰写的C ++第四版中的数据结构和算法分析解决方案

最新资源