C++版数据结构与算法分析——外文经典解析

需积分: 9 112 浏览量更新于2024-07-19 收藏 4.44MB PDF 举报

"DSAA in C++ 4th ed_Weiss_2014.pdf" 是一本关于数据结构和算法分析的书籍，由Mark Allen Weiss撰写，是C++语言的第四版。这本书在数据结构和算法的教学方面享有盛誉，适合计算机科学的学生和专业人士学习。在数据结构部分，书中涵盖了各种基本和高级的数据组织方式，包括数组、链表、栈、队列、散列表（哈希表）、树（二叉树、平衡树如AVL树和红黑树）、图等。这些数据结构的实现、操作和复杂度分析是理解计算机如何高效存储和处理数据的关键。作者Weiss详细解释了每种数据结构的原理，并通过C++代码示例来演示其工作方式，帮助读者深入理解和应用。算法分析是本书的另一大重点，涵盖了排序（如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等）、搜索（线性搜索、二分搜索、图搜索）、图算法（如Dijkstra最短路径算法、Floyd-Warshall算法）以及动态规划等经典算法。每种算法的效率分析，如时间复杂度和空间复杂度的计算，有助于读者评估不同算法在特定问题上的适用性。此外，书中还可能涉及递归、分治策略、贪心算法、回溯法等通用算法设计技巧。这些方法对于解决复杂问题和设计高效的解决方案至关重要。C++编程语言的使用使得这些概念更加具体和实用，因为C++支持底层内存管理和模板，使得数据结构和算法的实现更为灵活和高效。书中的空白页可能是为了给读者提供做笔记的空间，或者是为了保持章节间的视觉间隔。封面设计由Bruce Kenselaar负责，而营销和出版团队的其他成员也对书籍的推广和制作做出了贡献。这本书的全球发行范围广泛，覆盖了许多主要城市，反映了其国际影响力和受众的广泛性。 "DSAA in C++ 4th ed_Weiss_2014.pdf" 是一本深入浅出的数据结构和算法分析教材，适合希望提升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页未读，继续阅读

f3069

粉丝: 1
资源: 1

C++版数据结构与算法分析——外文经典解析

Digital Image Processing （Third Edition） Rafael C. Gonzalez 原版电子文档-非扫描

digital image processing

数字图像处理Digital Image Processing（冈萨雷斯）英文PPT课件3

DSAA_堆排序java实现_源码

DSAA_SUSTechACM-main.rar

C-C++常用网址.pdf

DSAA_SUSTechACM：DSAA实践

DSAA

POTOS.zip_Windows编程_C/C++_

计算机网络安全试题.pdf

最新资源