第1页 / 共653页
第2页 / 共653页
第3页 / 共653页
第4页 / 共653页
第5页 / 共653页
第6页 / 共653页
第7页 / 共653页
第8页 / 共653页
Algorithms in C++, Parts 1-4.pdf
TeamUnknown
Table of Contents
Copyright.................................................................................................................................................1
Dedication.........................................................................................................................................1
Preface......................................................................................................................................................2
Scope.................................................................................................................................................3
Use in the Curriculum.......................................................................................................................7
Algorithms of Practical Use............................................................................................................21
Programming Language..................................................................................................................22
Acknowledgments...........................................................................................................................24
C++ Consultant's Preface................................................................................................................25
Notes on Exercises..........................................................................................................................28
Part One: Fundamentals..................................................................................................................................30
Chapter One. Introduction.....................................................................................................................43
1.1. Algorithms................................................................................................................................48
1.2. A Sample Problem: Connectivity.............................................................................................48
1.3. Union–Find Algorithms...........................................................................................................49
1.4. Perspective................................................................................................................................49
1.5. Summary of Topics..................................................................................................................49
Chapter Two. Principles of Algorithm Analysis....................................................................................50
2.1. Implementation and Empirical Analysis..................................................................................50
2.2. Analysis of Algorithms............................................................................................................50
2.3. Growth of Functions.................................................................................................................51
2.4. Big-Oh Notation.......................................................................................................................51
2.5. Basic Recurrences....................................................................................................................53
Solution..................................................................................................................................................58
Formula 2.2. This recurrence arises for a recursive program that halves the input in one step......61
Solution..................................................................................................................................................61
Figure 2.6. Integer functions and binary representations..................................................................1
Solution....................................................................................................................................................1
Formula 2.4. This recurrence arises for a recursive program that has to make a linear pass
through the input, before, during, or after splitting that input into two halves..........................2
Solution..................................................................................................................................................12
Formula 2.5. This recurrence arises for a recursive program that splits the input into two
halves and then does a constant amount of other work (see Chapter 5)..................................19
Solution..................................................................................................................................................26
2.6. Examples of Algorithm Analysis.............................................................................................36
2.7. Guarantees, Predictions, and Limitations.................................................................................39
References for Part One..................................................................................................................44
...............................................................................................................................................................53
Part Two: Data Structures...............................................................................................................................54
Chapter Three. Elementary Data Structures..........................................................................................61
3.1. Building Blocks........................................................................................................................63
3.2. Arrays.......................................................................................................................................64
3.3. Linked Lists..............................................................................................................................67
3.4. Elementary List Processing......................................................................................................74
3.5. Memory Allocation for Lists....................................................................................................78
3.6. Strings.......................................................................................................................................84
3.7. Compound Data Structures......................................................................................................92
Chapter Four. Abstract Data Types.......................................................................................................97
Definition 4.1. An abstract data type (ADT) is a data type (a set of values and a collection of
operations on those values) that is accessed only through an interface. We refer to a
program that uses an ADT as a client, and a program that specifies the data type as an
i
TeamUnknown
Table of Contents
Part Two: Data Structures
implementation.............................................................................................................................107
4.1. Abstract Objects and Collections of Objects..........................................................................112
4.10. Perspective............................................................................................................................113
4.2. Pushdown Stack ADT............................................................................................................119
4.3. Examples of Stack ADT Clients............................................................................................136
4.4. Stack ADT Implementations..................................................................................................144
4.5. Creation of a New ADT.........................................................................................................152
4.6. FIFO Queues and Generalized Queues..................................................................................156
4.7. Duplicate and Index Items......................................................................................................162
4.8. First-Class ADTs....................................................................................................................167
4.9. Application-Based ADT Example..........................................................................................174
Chapter Five. Recursion and Trees......................................................................................................175
5.1. Recursive Algorithms.............................................................................................................175
5.2. Divide and Conquer....................................................................................................................1
5.3. Dynamic Programming..............................................................................................................1
5.4. Trees...........................................................................................................................................2
5.5. Mathematical Properties of Binary Trees...................................................................................7
5.6. Tree Traversal.............................................................................................................................9
5.7. Recursive Binary-Tree Algorithms..........................................................................................11
5.8. Graph Traversal........................................................................................................................14
5.9. Perspective................................................................................................................................16
References for Part Two..................................................................................................................22
...............................................................................................................................................................31
Part Three: Sorting...........................................................................................................................................35
Chapter Six. Elementary Sorting Methods............................................................................................42
6.1. Rules of the Game....................................................................................................................46
6.10. Key-Indexed Counting...........................................................................................................47
6.2. Selection Sort...........................................................................................................................51
6.3. Insertion Sort............................................................................................................................55
6.4. Bubble Sort...............................................................................................................................58
6.5. Performance Characteristics of Elementary Sorts....................................................................61
6.6. Shellsort....................................................................................................................................65
6.7. Sorting of Other Types of Data................................................................................................68
6.8. Index and Pointer Sorting.........................................................................................................70
6.9. Sorting of Linked Lists.............................................................................................................74
Chapter Seven. Quicksort......................................................................................................................75
7.1. The Basic Algorithm................................................................................................................76
7.2. Performance Characteristics of Quicksort................................................................................78
7.3. Stack Size.................................................................................................................................82
7.4. Small Subfiles...........................................................................................................................84
7.5. Median-of-Three Partitioning...................................................................................................89
7.6. Duplicate Keys.........................................................................................................................91
7.7. Strings and Vectors..................................................................................................................94
7.8. Selection...................................................................................................................................95
Chapter Eight. Merging and Mergesort.................................................................................................95
8.1. Two-Way Merging...................................................................................................................98
8.2. Abstract In-Place Merge.........................................................................................................102
8.3. Top-Down Mergesort.............................................................................................................104
8.4. Improvements to the Basic Algorithm...................................................................................113
8.5. Bottom-Up Mergesort............................................................................................................121
8.6. Performance Characteristics of Mergesort.............................................................................125
ii
TeamUnknown
Table of Contents
Part Three: Sorting
8.7. Linked-List Implementations of Mergesort...........................................................................129
8.8. Recursion Revisited................................................................................................................140
Chapter Nine. Priority Queues and Heapsort.......................................................................................142
Definition 9.1. A priority queue is a data structure of items with keys that supports two basic
operations: insert a new item, and remove the item with the largest key..............................142
9.1. Elementary Implementations..................................................................................................145
9.2. Heap Data Structure...............................................................................................................150
9.3. Algorithms on Heaps..............................................................................................................158
9.4. Heapsort..................................................................................................................................162
9.5. Priority-Queue ADT...............................................................................................................167
9.6. Priority Queues for Index Items.............................................................................................170
9.7. Binomial Queues....................................................................................................................176
Chapter Ten. Radix Sorting.................................................................................................................177
Figure 10.1. MSD radix sorting.....................................................................................................183
10.1. Bits, Bytes, and Words.........................................................................................................192
10.2. Binary Quicksort..................................................................................................................197
10.3. MSD Radix Sort...................................................................................................................203
10.4. Three-Way Radix Quicksort................................................................................................206
10.5. LSD Radix Sort....................................................................................................................207
10.6. Performance Characteristics of Radix Sorts.............................................................................1
10.7. Sublinear-Time Sorts................................................................................................................1
Chapter Eleven. Special-Purpose Sorting Methods.................................................................................1
11.1. Batcher's Odd–Even Mergesort................................................................................................2
11.2. Sorting Networks......................................................................................................................7
11.3. External Sorting......................................................................................................................10
11.4. Sort–Merge Implementations.................................................................................................16
11.5. Parallel Sort–Merge................................................................................................................21
References for Part Three................................................................................................................28
...............................................................................................................................................................32
Part Four: Searching........................................................................................................................................37
Chapter Twelve. Symbol Tables and Binary Search Trees...................................................................43
Definition 12.1. A symbol table is a data structure of items with keys that supports two basic
operations: insert a new item, and return an item with a given key........................................52
12.1. Symbol-Table Abstract Data Type.........................................................................................52
12.2. Key-Indexed Search...............................................................................................................54
12.3. Sequential Search...................................................................................................................61
12.4. Binary Search.........................................................................................................................68
12.5. Binary Search Trees (BSTs)...................................................................................................74
12.6. Performance Characteristics of BSTs.....................................................................................83
12.7. Index Implementations with Symbol Tables..........................................................................91
12.8. Insertion at the Root in BSTs.................................................................................................94
12.9. BST Implementations of Other ADT Functions....................................................................95
Chapter Thirteen. Balanced Trees........................................................................................................104
Figure 13.1. A large BST that is perfectly balanced.....................................................................108
13.1. Randomized BSTs................................................................................................................113
13.2. Splay BSTs...........................................................................................................................119
13.3. Top-Down 2-3-4 Trees.........................................................................................................122
13.4. Red–Black Trees..................................................................................................................125
13.5. Skip Lists..............................................................................................................................126
13.6. Performance Characteristics.................................................................................................133
Chapter Fourteen. Hashing..................................................................................................................141
iii
TeamUnknown
Table of Contents
Part Four: Searching
14.1. Hash Functions.....................................................................................................................153
14.2. Separate Chaining.................................................................................................................168
14.3. Linear Probing......................................................................................................................171
14.4. Double Hashing....................................................................................................................173
14.5. Dynamic Hash Tables..........................................................................................................175
14.6. Perspective............................................................................................................................178
Chapter Fifteen. Radix Search.............................................................................................................188
15.1. Digital Search Trees.............................................................................................................198
15.2. Tries......................................................................................................................................200
15.3. Patricia Tries.........................................................................................................................201
15.4. Multiway Tries and TSTs.....................................................................................................202
15.5. Text-String–Index Algorithms.............................................................................................title
Chapter Sixteen. External Searching...................................................................................................title
16.1. Rules of the Game................................................................................................................title
16.2. Indexed Sequential Access...................................................................................................title
16.3. B Trees.................................................................................................................................title
16.4. Extendible Hashing..............................................................................................................title
16.5. Perspective...........................................................................................................................title
References for Part Four...............................................................................................................title
.............................................................................................................................................................title
Index....................................................................................................................................................title
iv
Part One: Fundamentals
[ Team Unknown ]
C++ Programming Robert Sedgewick - Princeton University Addison Wesley Professional Algorithms
in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching, Third Edition
Chapter One. Introduction
The objective of this book is to study a broad variety of important and useful algorithms: methods for
solving problems that are suited for computer implementation. We shall deal with many different areas
of application, always concentrating on fundamental algorithms that are important to know and
interesting to study. We shall spend enough time on each algorithm to understand its essential
characteristics and to respect its subtleties. Our goal is to learn a large number of the most important
algorithms used on computers today, well enough to be able to use and appreciate them.
The strategy that we use for understanding the programs presented in this book is to implement and test
them, to experiment with their variants, to discuss their operation on small examples, and to try them
out on larger examples similar to what we might encounter in practice. We shall use the C++
programming language to describe the algorithms, thus providing useful implementations at the same
time. Our programs have a uniform style that is amenable to translation into other modern programming
languages, as well.
We also pay careful attention to performance characteristics of our algorithms, to help us develop
improved versions, compare different algorithms for the same task, and predict or guarantee
performance for large problems. Understanding how the algorithms perform might require
experimentation or mathematical analysis or both. We consider detailed information for many of the
most important algorithms, developing analytic results directly when feasible, or calling on results from
the research literature when necessary.
To illustrate our general approach to developing algorithmic solutions, we consider in this chapter a
detailed example comprising a number of algorithms that solve a particular problem. The problem that
we consider is not a toy problem; it is a fundamental computational task, and the solution that we
develop is of use in a variety of applications. We start with a simple solution, then seek to understand
that solution's performance characteristics, which help us to see how to improve the algorithm. After a
few iterations of this process, we come to an efficient and useful algorithm for solving the problem.
This prototypical example sets the stage for our use of the same general methodology throughout the
book.
We conclude the chapter with a short discussion of the contents of the book, including brief descriptions
of what the major parts of the book are and how they relate to one another.
[ Team Unknown ]
Part One: Fundamentals
1
2
2
Part One: Fundamentals
C++ Programming Robert Sedgewick - Princeton University Addison Wesley Professional Algorithms
in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching, Third Edition
1.1. Algorithms
When we write a computer program, we are generally implementing a method that has been devised
previously to solve some problem. This method is often independent of the particular computer to be
used—it is likely to be equally appropriate for many computers and many computer languages. It is the
method, rather than the computer program itself, that we must study to learn how the problem is being
attacked. The term algorithm is used in computer science to describe a problem-solving method suitable
for implementation as a computer program. Algorithms are the stuff of computer science: They are
central objects of study in many, if not most, areas of the field.
Most algorithms of interest involve methods of organizing the data involved in the computation.
Objects created in this way are called data structures, and they also are central objects of study in
computer science. Thus, algorithms and data structures go hand in hand. In this book we take the view
that data structures exist as the byproducts or end products of algorithms, and thus that we must study
them in order to understand the algorithms. Simple algorithms can give rise to complicated data
structures and, conversely, complicated algorithms can use simple data structures. We shall study the
properties of many data structures in this book; indeed, the book might well have been called
Algorithms and Data Structures in C++.
When we use a computer to help us solve a problem, we typically are faced with a number of possible
different approaches. For small problems, it hardly matters which approach we use, as long as we have
one that solves the problem correctly. For huge problems (or applications where we need to solve huge
numbers of small problems), however, we quickly become motivated to devise methods that use time or
space as efficiently as possible.
The primary reason for us to learn about algorithm design is that this discipline gives us the potential to
reap huge savings, even to the point of making it possible to do tasks that would otherwise be
impossible. In an application where we are processing millions of objects, it is not unusual to be able to
make a program millions of times faster by using a well-designed algorithm. We shall see such an
example in Section 1.2 and on numerous other occasions throughout the book. By contrast, investing
additional money or time to buy and install a new computer holds the potential for speeding up a
program by perhaps a factor of only 10 or 100. Careful algorithm design is an extremely effective part
of the process of solving a huge problem, whatever the applications area.
When a huge or complex computer program is to be developed, a great deal of effort must go into
understanding and defining the problem to be solved, managing its complexity, and decomposing it into
smaller subtasks that can be implemented easily. Often, many of the algorithms required after the
decomposition are trivial to implement. In most cases, however, there are a few algorithms whose
choice is critical because most of the system resources will be spent running those algorithms. Those
are the types of algorithms on which we concentrate in this book. We shall study a variety of
fundamental algorithms that are useful for solving huge problems in a broad variety of applications
areas.
The sharing of programs in computer systems is becoming more widespread, so, although we might
expect to be using a large fraction of the algorithms in this book, we also might expect to have to
implement only a smaller fraction of them. For example, the C++ Standard Template Library contains
implementations of a host of fundamental algorithms. However, implementing simple versions of basic
algorithms helps us to understand them better and thus to more effectively use and tune advanced
Part One: Fundamentals
Part One: Fundamentals
versions from a library. More important, the opportunity to reimplement basic algorithms arises
frequently. The primary reason to do so is that we are faced, all too often, with completely new
computing environments (hardware and software) with new features that old implementations may not
use to best advantage. In other words, we often implement basic algorithms tailored to our problem,
rather than depending on a system routine, to make our solutions more portable and longer lasting.
Another common reason to reimplement basic algorithms is that, despite the advances embodied in
C++, the mechanisms that we use for sharing software are not always sufficiently powerful to allow us
to conveniently tailor library programs to perform effectively on specific tasks.
Computer programs are often overoptimized. It may not be worthwhile to take pains to ensure that an
implementation of a particular algorithm is the most efficient possible unless the algorithm is to be used
for an enormous task or is to be used many times. Otherwise, a careful, relatively simple
implementation will suffice: We can have some confidence that it will work, and it is likely to run
perhaps five or 10 times slower at worst than the best possible version, which means that it may run for
an extra few seconds. By contrast, the proper choice of algorithm in the first place can make a
difference of a factor of 100 or 1000 or more, which might translate to minutes, hours, or even more in
running time. In this book, we concentrate on the simplest reasonable implementations of the best
algorithms.
The choice of the best algorithm for a particular task can be a complicated process, perhaps involving
sophisticated mathematical analysis. The branch of computer science that comprises the study of such
questions is called analysis of algorithms. Many of the algorithms that we study have been shown
through analysis to have excellent performance; others are simply known to work well through
experience. Our primary goal is to learn reasonable algorithms for important tasks, yet we shall also pay
careful attention to comparative performance of the methods. We should not use an algorithm without
having an idea of what resources it might consume, and we strive to be aware of how our algorithms
might be expected to perform.
[ Team Unknown ]
C++ Programming Robert Sedgewick - Princeton University Addison Wesley Professional Algorithms
in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching, Third Edition
1.2. A Sample Problem: Connectivity
Suppose that we are given a sequence of pairs of integers, where each integer represents an object of
some type and we are to interpret the pair p-q as meaning "p is connected to q." We assume the
relation "is connected to" to be transitive: If p is connected to q, and q is connected to r, then p is
connected to r. Our goal is to write a program to filter out extraneous pairs from the set: When the
program inputs a pair p-q, it should output the pair only if the pairs it has seen to that point do not
imply that p is connected to q. If the previous pairs do imply that p is connected to q, then the program
should ignore p-q and should proceed to input the next pair. Figure 1.1 gives an example of this
process.
Figure 1.1. Connectivity example
Part One: Fundamentals
3
3
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
