《数据结构与算法分析(C++版)》采用程序员*爱用的面向对象C++语言来描述数据结构和算法,并把数据结构原理和算法分析技术有机地结合在一起,系统介绍广各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构不同存储方法及有关算法进行分析比较。书中还引入了一些比较**的数据结构与先进的算法分析技术,并介绍了可计算性理论的一般知识。
本版的重要改进在于引入了参数化的模板,从而提高了算法中数据类型的通用性,支持**的代码重用。
《数据结构与算法分析(C++版)》概念清楚、逻辑性强、内容新颖,可作为大专院校计算机软件专业与计算机应用专业学生的教材和参考书,也可供计算机工程技术人员参考。

I PRELIMINARIES

1 Data Structures and Algorithms
1.1 A Philosophy of Data Structures
1.1.1 The Need for Data Structures
1.1.2 Costs and Benefits
1.2 Abstract Data Types and Data Structures
1.3 Problems, Algorithms, and Programs
1.4 Further Reading
1.5 Exercises

2 Mathematical Preliminaries
2.1 Sets and Relations
2.2 Miscellaneous Notation
2.3 Logarithms
2.4 Recursion
2.5 Summations and Recurrences
2.6 Mathematical Proof Techniques
2.6.l Proof by Contradiction
2.6.2 Proof by Mathematical Induction
2.7 Estimating
2.8 Further Reading
2.9 Exercises

3 Algorithm Analysis
3.1 Introduction
3.2 Best, Worst, and Average Cases
3.3 A Faster Computer, or a Faster Algorithm?
3.4 Asymptotic Analysis
3.4.1 Upper Bounds
3.4.2 Lower Bounds
3.4.3 O Notation
3.4.4 Simplifying Rules
3.5 Calculating the Running Time of a Program
3.6 Analyzing Problems
3.7 Common Misunderstandings
3.8 Multiple Parameters
3.9 Space Bounds
3.10 Some Practical Considerations
3.11 Further Reading
3.12 Exercises
3.13 Projects

II FUNDAMENTAL DATA STRUCTURES

4 Lists, Stacks, and Queues
4.1 Lists
4.1.1 Array--Based List Implementation
4.1.2 Linked Lists
4.1.3 Comparison of List Implementations
4.1.4 Element Implementations
4.1.5 Doubly Linked Lists
4.2 The Dictionary ADT
4.3 Stacks
4.3.1 Array-Based Stacks
4.3.2 Linked Stacks
4.3.3 Comparison of Array--Based and Linked Stacks
4.3.4 Implementing Recursion
4.4 Queues
4.4.1 Array-Based Queues
4.4.2 Linked Queues
4.4.3 Comparison of Array-Based and Linked Queues
4.5 Further Reading
4.6 Exercises
4.7 Projects

5 Binary Trees
5.1 Definitions and Properties
5.1.1 The Full Binary Tree Theorem
5.1.2 A Binary Tree Node ADT
5.2 Binary Tree Traversals
5.3 Binary Tree Node Implementations
5.3.1 Pointer-Based Node Implementations
5.3.2 Space Requirements
5.3.3 Array Implementation for Complete Binary Trees
5.4 Binary Search Trees
5.5 Heaps and Priority Queues
5.6 Huffman Coding Trees
5.6.1 Building Huffman Coding Trees
5.6.2 Assigning and Using Huffman Codes
5.7 Further Reading
5.8 Exercises
5.9 Projects

6 Non-Binary Trees
6.1 General Tree Definitions and Terminology
6.1.1 An ADT for General Tree Nodes
6.1.2 General Tree Traversals
6.2 The Parent Pointer Implementation
6.3 General Tree Implementations
6.3.1 List of Children
6.3.2 The Left-Child/Right-Sibling Implementation
6.3.3 Dynamic Node Implementations
6.3.4 Dynamic ''Left--Child/Right-Sibling'' Implementation
6.4 K-ary Trees
6.5 Sequential Tree Implementations
6.6 Further Reading
6.7 Exercises
6.8 Projects

III Sorting and Searching

7 Internal Sorting
7.1 Sorting Terminology and Notation
7.2 Three O(n) Sorting Algorithms
7.2.1 Insertion Sort
7.2.2 Bubble Sort
7.2.3 Selection Sort
7.2.4 The Cost of Exchange Sorting
7.3 Shellsort
7.4 Quicksort
7.5 Mergesort
7.6 Heapsort
7.7 Binsort and Radix Sort
7.8 An Empirical Comparison of Sorting Algorithms
7.9 Lower Bounds for Sorting
7.10 Further Reading
7.11 Exercises
7.l2 Projects

8 File Processing and External Sorting
8.1 Primary versus Secondary Storage
8.2 Disk Drives
8.2.l Disk Drive Architecture
8.2.2 Disk Access Costs
8.3 Buffers and Buffer Pools
8.4 The Programmer's View of Files
8.5 External Sorting
8.6 Simple Approaches to External Sorting
8.7 Replacement Selection
8.8 Multiway Merging
8.9 Further Reading
8.10 Exercises
8.11 Projects

9 Searching
9.1 Searching Sorted Arrays
9.2 Self Organizing Lists
9.3 Searching in Sets
9.4 Hashing
9.4.1 Hash Functions
9.4.2 Open Hashing
9.4.3 Closed Hashing
9.5 Further Reading
9.6 Exercises
9.7 Projects

10 Indexing
10.1 Linear Indexing
10.2 ISAM
10.3 Tree Indexing
10.4 2-3 Trees
10.5 B-Trees
10.5.1 B+-Trees
10.5.2 B-Tree Analysis
10.6 Further Reading
10.7 Exercises
10.8 Projects

IV Applications and Advanced Topics

11 Graphs
11.1 Terminology and Representations
11.2 Graph Implementations
11.3 Graph Traversals
11.3.1 Depth-First Search
11.3.2 Breadth-First Search
11.3.3 Topological Sort
11.4 Shortest-Paths Problems
11.4.1 Single-Source Shortest Paths
11.4.2 All-Pairs Shortest Paths
11.5 Minimum-Cost Spanning Trees
11.5.1 Prim's Algorithm.
11.5.2 Kruskal's Algorithm
11.6 Further Reading
11.7 Exercises
11.8 Projects

12 Lists and Arrays Revisited
12.1 Skip Lists
12.2 Multilists
12.3 Matrix Representations
12.4 Memory Management
12.4.1 Dynamic Storage Allocation
12.4.2 Failure Policies and Garbage Collection
12.5 Further Reading
12.6 Exercises
12.7 Projects

13 Advanced Tree Structures
13.1 Tries
13.2 Balanced Trees
13.2.1 The AVL Tree
13.2.2 The Splay Tree
13.3 Spatial Data Structures
13.3.1 The K-D Tree
13.3.2 The PR quadtree
13.3.3 Other Spatial Data Structures
13.4 Further Reading
13.5 Exercises
13.6 Projects

14 Analysis Techniques
14.1 Summation Techniques
14.2 Recurrence Relations
14.2.1 Estimating Upper and Lower Bounds
14.2.2 Expanding Recurrences
14.2.3 Divide and Conquer Recurrences
14.2.4 Average-Case Analysis of Quicksort
14.3 Amortized Analysis
14.4 Further Reading
14.5 Exercises
14.6 Projects

15 Limits to Computation
15.1 Reductions
15.2 Hard Problems
15.2.1 NP--Completeness
15.2.2 Getting Around NP-Complete Problems
15.3 Impossible Problems
15.3.1 Uncountability
15.3.2 The Halting Problem Is Unsolvable
15.3.3 Determining Program Behavior Is Unsolvable
15.4 Further Reading
15.5 Exercises
15.6 Projects
V APPENDIX
A Utility Functions
Bibliography
Index
……

We study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we computerize more complex tasks.
The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with "programming tricks" but rather is based on good organization of information and good algorithms. A programmer who has not mastered the basic principles of clear design will not likely write efficient programs. Conversely, clear programs require
clear data organization and clear algorithms. Most computer science curricula recognize that good programming skills begin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and implementation, the next step is to study the effects of data organization and algorithms on program efficiency.
Approach: Many techniques for representing data are described in this book.
These techniques are presented within the context of the following principles:
1. Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation for the significant effects of the physical medium employed (e.g., data stored on disk versus main memory).
2. Related to costs and benefits is the notion of tradeoffs. For example, it is quite common to reduce time requirements at the expense of an increase in space requirements, or vice versa. Programmers face tradeoff issues regularly in all phases of software design and implementation, so the concept must become deeply ingrained.
3. Programmers should know enough about common practice to avoid reinventing the wheel. Thus, programmers need to learn the commonly used data structures and related algorithms.
4. Data structures follow needs. Programmers must learn to assess application needs first, then find a data structure with matching capabilities. To do this requires competence in principles 1, 2, and 3.
Using the Book in Class: Data structures and algorithms textbooks tend to fall into one of two categories : teaching texts or encyclopedias. Books that attempt to do both usually fail at both. This book is intended as a teaching text. I believe it is more important for a practitioner to understand the principles required to select or
design the data structure that will best solve some problem than it is to memorize a lot of textbook implementations. Hence, I have designed this as a teaching text that covers most standard data structures, but not all. A few data structures that are not widely adopted are included to illustrate important principles. Some relatively new data structures that should become widely used in the future are included.
This book is intended for a single-semester course at the undergraduate level, or for self study by technical professionals. Readers should have programming experience, typically two semesters or the equivalent of a structured programming language such as Pascal or C, and including at least some exposure to C++. Readers who are already familiar with recursion will have an advantage. Students of data structures will also benefit from having first completed a good course in Discrete Mathematics. Nonetheless, Chapter 2 attempts to give a reasonably complete survey of the prerequisite mathematical topics at the level necessary to understand their use in this book. Readers may wish to refer back to the appropriate sections as needed when encountering unfamiliar mathematical material.

In this eagerly anticipated revision,Clifford A.Shaffer provides a thorough and comprehensive treatment of fundamental data structures and the principles of algorithm analysis.The author focuses on teaching students and practitioners how to create efficient data structures and algorithms and to understand the principles required to select or design the data structure that will best solve the problem.The integrated treatment of algorithm analysis,file processing,and efficiency places this book in a class of its own.
Features:
Algorithm analysis techniques are presented throughout the text.Analysis is closely tied to the needs of practicing programmers and students.It is not presented as theory for theory’S sake.
C++ is used as a tool to illustrate data structure concepts with clear, simple-to-understand examples.All programming examples are actual C++ code.
This book presents each data structure and algorithm as having costs and benefits.and provides the reader with a thorough understanding of how to assess the costs and benefits,including space comparisons for data structures,space/time trade-offs,and special-purpose Users of data structures or algorithms.
New to this Edition:
Completely rewritten coding examples that are clear and illustrative.Extensive use of object- oriented programming techniques.
Expanded coverage of recursion,Dictionary ADT,balanced tress,and buffer pools.
More emphasis on techniques for object-oriented program design.
More exercises and examples.Close to 350 problems and projects.