C++算法基础与数据结构深度解析

5星 · 超过95%的资源需积分: 35 130 浏览量更新于2024-07-20 1 收藏 11.47MB PDF 举报

"Algorithms in C++, Parts 1-4" 是一本由Robert Sedgewick撰写，Christopher Van Wyk合著的书籍，该书全面覆盖了重要的算法和数据结构，并针对C++进行了深入的更新和扩展。这本书是Sedgewick系列作品的第一半，主要关注基础数据结构和算法，如排序、搜索及其相关应用。本书的特点和亮点包括： 1. 全面的数据结构：书中详细介绍了数组、链表、字符串、树等基本数据结构，以及它们在实际编程中的应用。 2. 强调抽象数据类型（ADT）和模块化编程：相比于之前的版本，此版更加强调ADT、模块化编程、面向对象编程和C++类的使用。 3. 丰富的算法实现：提供了超过100种排序、选择、优先队列ADT实现和符号表ADT（搜索）实现的算法。 4. 新算法：包含新的实现，如二项队列、多路基数排序、随机化BSTs、摆动树、跳跃列表、多路查找树、B树、可扩展哈希等。 5. 定量信息：对算法进行了更多的定量分析，以便读者比较不同算法的性能。 6. 大量练习：超过1000个新练习，帮助读者理解和掌握算法的特性。第一部分：基础 - 第一章：介绍：引入了算法的概念，通过一个连接性问题展示算法的使用，并探讨了联合-查找算法的背景和目的。 - 第二章：算法分析原理：讨论了实现与经验分析，算法分析的方法，函数的增长，大O表示法，以及基本递归方程的解决方法。书中每个章节末尾都提供了解决方案和注释，便于读者深入理解算法的工作原理和性能。无论是初学者还是经验丰富的程序员，都可以从本书中找到宝贵的算法知识和实践指导。这本《Algorithms in C++, Parts 1-4》不仅是一本教学用书，也是专业人士的重要参考资源，结合了理论和实践，使读者能够掌握并应用各种算法，提升编程能力。

Figure 1.6. Example of quick union (not-too-quick find)

This sequence depicts the contents of the id array after each of the pairs at left

are processed by the quick-find algorithm (Program 1.1). Shaded entries are those

that change for the union operation (just one per operation). When we process the

pair p q, we follow pointers from p to get an entry i with id[i] == i; then,

we follow pointers from q to get an entry j with id[j] == j; then, if i and j

differ, we set id[i] = id[j]. For the find operation for the pair 5-8 (final

line), i takes on the values 5 6 9 0 1, and j takes on the values 8 0 1.

Part One: Fundamentals 11

The connected components depicted in Figure 1.5 are called trees; they are

fundamental combinatorial structures that we shall encounter on numerous

occasions throughout the book. We shall consider the properties of trees in detail

in Chapter 5. For the union and find operations, the trees in Figure 1.5 are useful

because they are quick to build and have the property that two objects are

connected in the tree if and only if the objects are connected in the input. By

moving up the tree, we can easily find the root of the tree containing each object,

so we have a way to find whether or not they are connected. Each tree has

precisely one object that points to itself, which is called the root of the tree. The

self-pointer is not shown in the diagrams. When we start at any object in the tree,

move to the object to which it points, then move to the object to which that object

points, and so forth, we eventually end up at the root, always. We can prove this

property to be true by induction: It is true after the array is initialized to have

every object point to itself, and if it is true before a given union operation, it is

certainly true afterward.

The diagrams in Figure 1.4 for the quick-find algorithm have the same properties

as those described in the previous paragraph. The difference between the two is

that we reach the root from all the nodes in the quick-find trees after following

just one link, whereas we might need to follow several links to get to the root in a

quick-union tree.

Program 1.2. Quick-union solution to connectivity problem

If we replace the body of the while loop in Program 1.1 by this code,

we have a program that meets the same specifications as Program 1.1,

but does less computation for the union operation at the expense of

more computation for the find operation. The for loops and

subsequent if statement in this code specify the necessary and

sufficient conditions on the id array for p and q to be connected. The

assignment statement id[i] = j implements the union operation.

for (i = p; i != id[i]; i = id[i]) ;

for (j = q; j != id[j]; j = id[j]) ;

12 Part One: Fundamentals

if (i == j) continue;

id[i] = j;

cout << " " << p << " " << q << endl;

Program 1.2 is an implementation of the union and find operations that comprise

the quick-union algorithm to solve the connectivity problem. The quick-union

algorithm would seem to be faster than the quick-find algorithm, because it does

not have to go through the entire array for each input pair; but how much faster is

it? This question is more difficult to answer here than it was for quick find,

because the running time is much more dependent on the nature of the input. By

running empirical studies or doing mathematical analysis (see Chapter 2), we can

convince ourselves that Program 1.2 is far more efficient than Program 1.1, and

that it is feasible to consider using Program 1.2 for huge practical problems. We

shall discuss one such empirical study at the end of this section. For the moment,

we can regard quick union as an improvement because it removes quick find's

main liability (that the program requires at least NM instructions to process M

union operations among N objects).

This difference between quick union and quick find certainly represents an

improvement, but quick union still has the liability that we cannot guarantee it to

be substantially faster than quick find in every case, because the input data could

conspire to make the find operation slow.

Property 1.2. For M > N, the quick-union algorithm could take more than MN/2

instructions to solve a connectivity problem with M pairs of N objects

Suppose that the input pairs come in the order 1-2, then 2-3, then

3-4, and so forth. After N – 1 such pairs, we have N objects all in the

same set, and the tree that is formed by the quick-union algorithm is a

straight line, with N pointing to N – 1, which points to N – 2, which

points to N – 3, and so forth. To execute the find operation for object

N, the program has to follow N – 1 pointers. Thus, the average number

of pointers followed for the first N pairs is

(0 + 1 + ... + (N – 1))/N = (N – 1)/2.

Now suppose that the remainder of the pairs all connect N to some

other object. The find operation for each of these pairs involves at least

(N – 1) pointers. The grand total for the M find operations for this

sequence of input pairs is certainly greater than MN/2.

Fortunately, there is an easy modification to the algorithm that allows us to

guarantee that bad cases such as this one do not occur. Rather than arbitrarily

connecting the second tree to the first for union, we keep track of the number of

nodes in each tree and always connect the smaller tree to the larger. This change

requires slightly more code and another array to hold the node counts, as shown

in Program 1.3, but it leads to substantial improvements in efficiency. We refer to

this algorithm as the weighted quick-union algorithm.

Figure 1.7 shows the forest of trees constructed by the weighted union–find

algorithm for the example input in Figure 1.1. Even for this small example, the

Part One: Fundamentals 13

剩余652页未读，继续阅读

十字青城

粉丝: 0
资源: 1

C++算法基础与数据结构深度解析

algorithmsinC++-RobertSedgewick.rar_VC书籍_Visual_C++_

Algorithms in C++, Parts 1–4 Fundamentals, Data Structure, Sorting, Searching, Third Edition

Algorithms.in.C++.Part.5.Graph.Algorithms

algorithms in c++pdf

most graph algorithms that take an adjacency-matrix representation as input

链表的研究意义和发展，并引用参考文献

In Defense of Color-based Model-free Tracking

最新资源