C++实现数据结构与算法分析（第4版）

需积分: 15 51 浏览量更新于2023-05-21 收藏 2.88MB PDF 举报

"《C++中的数据结构与算法分析》第四版是马克·艾伦·韦斯撰写的一本权威指南，专为深入理解并实践数据结构和算法在C++编程中的应用而设计。本书旨在帮助读者掌握各种基础到高级的数据结构，如数组、链表、树、图、堆栈、队列等，以及如何通过高效的算法实现这些结构的操作，例如排序、搜索和动态规划等。本书的特点在于其系统性，从基本概念入手，逐步引导读者掌握复杂的数据结构和算法的设计与实现。作者通过清晰的阐述和丰富的示例，确保理论知识与实际代码相结合，使读者能够理解和运用C++语言来优化程序性能。每一章都包含详尽的代码示例和分析，让学习者能够在实践中学习和提升。此外，书中还覆盖了数据结构和算法的时间和空间复杂度分析，这对于理解算法效率至关重要。通过对不同策略的比较，读者可以更好地选择适合特定场景的算法，并且学会如何进行优化，以适应大规模数据处理的需求。作为第四版，本书可能包含了对C++新特性的介绍，如C++11和C++14标准，以及对现代编程趋势的反映，比如内存管理和并发编程的最佳实践。同时，作者可能还提供了针对最新版本C++编译器的兼容性和优化建议。本书不仅适合计算机科学专业的学生和研究人员，也适用于经验丰富的软件开发人员寻求提升他们的数据结构和算法技巧。无论你是初学者还是资深开发者，这本书都能提供有价值的指导，帮助你在C++编程的世界里更高效地处理数据和解决问题。" 这是一本综合性的教程，涵盖了C++编程中至关重要的基础知识，是数据结构和算法学习者的理想参考书。通过阅读和实践本书，读者将能够构建更加健壮和高效的软件系统。

PREFACE

Purpose/Goals

The fourth edition of Data Structures and Algorithm Analysis in C

describes data structures,

methods of organizing large amounts of data, and algorithm analysis, the estimation of the

running time of algorithms. As computers become faster and faster, the need for programs

that can handle large amounts of input becomes more acute. Paradoxically, this requires

more careful attention to efﬁciency, since inefﬁciencies in programs become most obvious

when input sizes are large. By analyzing an algorithm before it is actually coded, students

can decide if a particular solution will be feasible. For example, in this text students look at

speciﬁc problems and see how careful implementations can reduce the time constraint for

large amounts of data from centuries to less than a second. Therefore, no algorithm or data

structure is presented without an explanation of its running time. In some cases, minute

details that affect the running time of the implementation are explored.

Once a solution method is determined, a program must still be written. As computers

have become more powerful, the problems they must solve have become larger and more

complex, requiring development of more intricate programs. The goal of this text is to teach

students good programming and algorithm analysis skills simultaneously so that they can

develop such programs with the maximum amount of efﬁciency.

This book is suitable for either an advanced data structures course or a ﬁrst-year

graduate course in algorithm analysis. Students should have some knowledge of inter-

mediate programming, including such topics as pointers, recursion, and object-based

programming, as well as some background in discrete math.

Approach

Although the material in this text is largely language-independent, programming requires

the use of a speciﬁc language. As the title implies, we have chosen C

for this book.

has become a leading systems programming language. In addition to ﬁxing many

of the syntactic ﬂaws of C, C

provides direct constructs (the class and template)to

implement generic data structures as abstract data types.

The most difﬁcult part of writing this book was deciding on the amount of C

include. Use too many features of C

and one gets an incomprehensible text; use too few

and you have little more than a C text that supports classes.

The approach we take is to present the material in an object-based approach. As such,

there is almost no use of inheritance in the text. We use class templates to describe generic

data structures. We generally avoid esoteric C

features and use the

vector and string

classes that are now part of the C

standard. Previous editions have implemented class

templates by separating the class template interface from its implementation. Although

this is arguably the preferred approach, it exposes compiler problems that have made it

xvi Preface

difﬁcult for readers to actually use the code. As a result, in this edition the online code

represents class templates as a single unit, with no separation of interface and implementa-

tion. Chapter 1 provides a review of the C

features that are used throughout the text and

describes our approach to class templates. Appendix A describes how the class templates

could be rewritten to use separate compilation.

Complete versions of the data structures, in both C

and Java, are available on

the Internet. We use similar coding conventions to make the parallels between the two

languages more evident.

Summary of the Most Signiﬁcant Changes in the Fourth Edition

The fourth edition incorporates numerous bug ﬁxes, and many parts of the book have

undergone revision to increase the clarity of presentation. In addition,

Chapter 4 includes implementation of the AVL tree deletion algorithm—a topic often

requested by readers.

Chapter 5 has been extensively revised and enlarged and now contains material on

two newer algorithms: cuckoo hashing and hopscotch hashing. Additionally, a new

section on universal hashing has been added. Also new is a brief discussion of the

unordered_set and unordered_map class templates introduced in C

11.

Chapter 6 is mostly unchanged; however, the implementation of the binary heap makes

use of move operations that were introduced in C

11.

Chapter 7 now contains material on radix sort, and a new section on lower-bound

proofs has been added. Sorting code makes use of move operations that were

introduced in C

11.

Chapter 8 uses the new union/ﬁnd analysis by Seidel and Sharir and shows the

O( M α(M, N) ) bound instead of the weaker O( M log

∗

N ) bound in prior editions.

Chapter 12 adds material on sufﬁx trees and sufﬁx arrays, including the linear-time

sufﬁx array construction algorithm by Karkkainen and Sanders (with implementation).

The sections covering deterministic skip lists and AA-trees have been removed.

Throughout the text, the code has been updated to use C

11. Notably, this means

use of the new C

11 features, including the

auto keyword, the range for loop, move

construction and assignment, and uniform initialization.

Overview

Chapter 1 contains review material on discrete math and recursion. I believe the only way

to be comfortable with recursion is to see good uses over and over. Therefore, recursion

is prevalent in this text, with examples in every chapter except Chapter 5. Chapter 1 also

includes material that serves as a review of basic C

. Included is a discussion of templates

and important constructs in C

class design.

Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis

and its major weaknesses. Many examples are provided, including an in-depth explana-

tion of logarithmic running time. Simple recursive programs are analyzed by intuitively

converting them into iterative programs. More complicated divide-and-conquer programs

are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed

until Chapter 7, where it is performed in detail.

Preface xvii

Chapter 3 covers lists, stacks, and queues. This chapter includes a discussion of the STL

vector and list classes, including material on iterators, and it provides implementations

of a signiﬁcant subset of the

STL vector and list classes.

Chapter 4 covers trees, with an emphasis on search trees, including external search

trees (B-trees). The

UNIX ﬁle system and expression trees are used as examples. AVL trees

and splay trees are introduced. More careful treatment of search tree implementation details

is found in Chapter 12. Additional coverage of trees, such as ﬁle compression and game

trees, is deferred until Chapter 10. Data structures for an external medium are considered

as the ﬁnal topic in several chapters. Included is a discussion of the STL

set and map classes,

including a signiﬁcant example that illustrates the use of three separate maps to efﬁciently

solve a problem.

Chapter 5 discusses hash tables, including the classic algorithms such as sepa-

rate chaining and linear and quadratic probing, as well as several newer algorithms,

namely cuckoo hashing and hopscotch hashing. Universal hashing is also discussed, and

extendible hashing is covered at the end of the chapter.

Chapter 6 is about priority queues. Binary heaps are covered, and there is additional

material on some of the theoretically interesting implementations of priority queues. The

Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.

Chapter 7 covers sorting. It is very speciﬁc with respect to coding details and analysis.

All the important general-purpose sorting algorithms are covered and compared. Four

algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. New to

this edition is radix sort and lower bound proofs for selection-related problems. External

sorting is covered at the end of the chapter.

Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a

short and speciﬁc chapter that can be skipped if Kruskal’s algorithm is not discussed.

Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only

because they frequently occur in practice but also because their running time is so heavily

dependent on the proper use of data structures. Virtually all of the standard algorithms

are presented along with appropriate data structures, pseudocode, and analysis of running

time. To place these problems in a proper context, a short discussion on complexity theory

(including NP-completeness and undecidability) is provided.

Chapter 10 covers algorithm design by examining common problem-solving tech-

niques. This chapter is heavily fortiﬁed with examples. Pseudocode is used in these later

chapters so that the student’s appreciation of an example algorithm is not obscured by

implementation details.

Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and

6 and the Fibonacci heap, introduced in this chapter, are analyzed.

Chapter 12 covers search tree algorithms, the sufﬁx tree and array, the k-d tree, and

the pairing heap. This chapter departs from the rest of the text by providing complete and

careful implementations for the search trees and pairing heap. The material is structured so

that the instructor can integrate sections into discussions from other chapters. For example,

the top-down red-black tree in Chapter 12 can be discussed along with AVL trees (in

Chapter 4).

Chapters 1 to 9 provide enough material for most one-semester data structures courses.

If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis

could cover chapters 7 to 11. The advanced data structures analyzed in Chapter 11 can

easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9

CHAPTER 1

Programming: A General

Overview

In this chapter, we discuss the aims and goals of this text and brieﬂy review programming

concepts and discrete mathematics. We will ...

See that how a program performs for reasonably large input is just as important as its

performance on moderate amounts of input.

Summarize the basic mathematical background needed for the rest of the book.

Brieﬂy review recursion.

Summarize some important features of C

that are used throughout the text.

1.1 What’s This Book About?

Suppose you have a group of N numbers and would like to determine the kth largest. This

is known as the selection problem. Most students who have had a programming course

or two would have no difﬁculty writing a program to solve this problem. There are quite a

few “obvious” solutions.

One way to solve this problem would be to read the N numbers into an array, sort the

array in decreasing order by some simple algorithm such as bubble sort, and then return

the element in position k.

A somewhat better algorithm might be to read the ﬁrst k elements into an array and

sort them (in decreasing order). Next, each remaining element is read one by one. As a new

element arrives, it is ignored if it is smaller than the kth element in the array. Otherwise, it

is placed in its correct spot in the array, bumping one element out of the array. When the

algorithm ends, the element in the kth position is returned as the answer.

Both algorithms are simple to code, and you are encouraged to do so. The natural ques-

tions, then, are: Which algorithm is better? And, more important, Is either algorithm good

enough? A simulation using a random ﬁle of 30 million elements and k = 15,000,000

will show that neither algorithm ﬁnishes in a reasonable amount of time; each requires

several days of computer processing to terminate (albeit eventually with a correct answer).

An alternative method, discussed in Chapter 7, gives a solution in about a second. Thus,

although our proposed algorithms work, they cannot be considered good algorithms,

剩余653页未读，继续阅读

码农型柒

粉丝: 0
资源: 1

C++实现数据结构与算法分析（第4版）

Data Structure and Algorithm Analysis in C 习题答案

Data Structures & Algorithm Analysis in C++, Mark A. Weiss, 4th

Data Structures and Algorithms in C++, 4th edition.pdf

Clifford Shaffer's Data Structures and Algorithm Analysis in C++

SpringBoot入门与Data Structures and Algorithm Analysis解析

unordered_map and Algorithm Complexity Analysis: Search, Insertion, Deletion

data structures and algorithm analysis in c++ 第4版 源码

data structures and algorithm analysis in c++ pdf

mark allen weiss, data structures&algorithm analysis in c++

数据结构书籍和网课推荐

最新资源

data structures and algorithm analysis in c++ 第4版源码