C++编程的数据结构与算法分析第四版

需积分: 9 59 浏览量更新于2024-07-22 收藏 4.77MB PDF 举报

"Data.Structures And Algorithm Analysis in C++ 4e 是一本关于数据结构和算法分析的英文版书籍，由Mark Allen Weiss撰写，适合对C++编程有一定了解的读者深入学习数据结构和算法。" 本书《Data Structures And Algorithm Analysis in C++ 4e》是第四版，专注于使用C++语言探讨数据结构与算法分析的主题。作者Mark Allen Weiss是佛罗里达国际大学的教授，他在计算机科学领域有着深厚的造诣，尤其在数据结构和算法方面。这本书旨在帮助读者理解并掌握如何有效地设计、实现和评估数据结构及算法。书中涵盖了各种基本和高级的数据结构，如数组、链表、栈、队列、树（二叉树、平衡树如AVL和红黑树）、图以及散列表等。每种数据结构都详细讲解了其概念、操作、优缺点，并通过C++代码示例进行实现，帮助读者理解其实现机制。此外，书中还讨论了动态内存管理、对象导向编程在数据结构中的应用，以及如何利用模板来实现泛型编程。在算法分析部分，作者讲解了时间复杂度和空间复杂度的概念，以及如何分析和比较不同算法的效率。书中涵盖了排序（如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序）、搜索（如线性搜索、二分搜索和哈希搜索）等常见算法，同时涉及了图算法（如深度优先搜索、广度优先搜索、最短路径算法如Dijkstra和Floyd-Warshall）和递归问题的解决方案。除了理论知识，书中还强调了实际问题的解决策略，如如何选择合适的数据结构来优化问题的解决方案，以及如何使用算法来提升程序性能。此外，书中还包含了大量的练习题和案例研究，帮助读者巩固所学知识并提高解决实际问题的能力。《Data Structures And Algorithm Analysis in C++ 4e》是一本全面且深入的教材，适合计算机科学专业的学生、软件工程师或者任何希望通过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 Four th 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))boundinsteadoftheweakerO( M log

∗

N )boundinprioreditions.

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

.Includedisadiscussionoftemplates

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 exter nal 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

6andtheFibonacciheap,introducedinthischapter,areanalyzed.

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.

Asomewhatbetteralgorithmmightbetoreadtheﬁrstk 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页未读，继续阅读

baixiangguobing

粉丝: 0
资源: 1

C++编程的数据结构与算法分析第四版

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

Data Structures and Algorithm Analysis in C++, Third Edition.pdf

Data.Structures.and.Algorithm.Analysis.in.C

data structures and algorithm analysis in C++

Data structures and algorithm analysis in C++

Data.Structures.And.Algorithm.Analysis.In.C.1992.

\Data.Structures.and.Algorithm.Analysis.in.C.rar

Addison.Wesley.Data.Structures.and.Algorithm.Analysis.in.Java.3rd.Edition.2011

Data Structures and Algorithm Analysis in C++ 3rd edition

Data Structures and Algorithm Analysis in C++ Fourth Edition

最新资源