数据结构与算法——C++版(第2版) (2008 年度畅销榜NO.7157 )

An Accessible Approach to Data Structrues
In data Structures and Algorithms in C++, Second Editoin, Adam Drozdek has successfully created a textbook that makes the subject accessible to students who are new to data structures, while providing an appealing scope of material for more advanced students.
This text:
● Emphasizes the connection between data structures and alogorithms
● Carefully presents the difficult subject of recursion
● Offers a case study in every chapter (execpt Chapter 2)
● Introduces the Standard Template Library and integrates it in the case studies
● Provides programming assignments in all but the first chapter
Drozdek amply illustrates his discussion fo data structures with figures and case studies, which strengthens student understanding of the power and utility of data structures.

Chapter 1 Object-Oriented Programming Using C++
1.1 Abstract Data Types
1.2 Encapsulation
1.3 Inheritance
1.4 Pointers
1.5 Polymorphism
1.6 C++ and Object-Oriented Programming
1.7 The Standard Template Library
1.8 Vectors in the Standard Template Library
1.9 Data Structures and Object-Oriented Programming
1.10 Case Study: Random Access File
1.11 Exercises
1.12 Programming Assignments

Chapter 2 Complexity Analysis
2.1 Computational and Asymptotic Complexity
2.2 Big-O Notation
2.3 Properties of Big-O Notation
2.4 Ω and Θ Notations
2.5 Possible Problems
2.6 Examples of complexities
2.7 Finding Asymptotic Complexity: Examples
2.8 the Best, Average, and Worst Cases
2.9 Amortized Complexity
2.10 Exercises

Chapter 3 Llinked Lis+s
3.1 Singly linked Lists
3.2 Doubyly linked Lists
3.3 Circular Lists
3.4 Skip Lists
3.5 Self-Organizing Lists
3.6 Sparse Tables
3.7 Lists in the Standard Template Library
3.8 Deques in the Standard Template Library
3.9 Concluding Remarks
3.10 Case Study: A Library
3.11 Exercises
3.12 Programming Assignements

Chapter 4 Stacks and Queues
4.1 Stacks
4.2 Queues
4.3 Priority Queues
4.4 Stacks in the Standard Template Library
4.5 Queues in the Standard Template Library
4.6 Priority Queues in the Standard Template Library
4.7 Case Study: Exiting a Maze
4.8 Exercises
4.9 Programming Assignments

Chapter 5 Recursion
5.1 Recursive Definitions
5.2 Function Calls and REcursion Implementation
5.3 Anatomy of a Recursive Call
5.4 Tail Recursion
5.5 Nontail Recursion
5.6 Indirect recursion
5.7 Nested Recursion
5.8 Excessive Recursion
5.9 Backtracking
5.10 Concluding Remarks
5.11 Case Study: A Recursive Descent Interpreter
5.12 Exercises
5.13 Programming Assignments

Chapter 6 Binary Tress
6.1 Trees, Bionary Trees, and Binary Search Trees
6.2 Implementing Binary Trees
6.3 Searching a Binary Search TRee
6.4 Tree Traversal
6.5 Insertion
6.6 Deletion
6.7 Balancing a Tree
6.8 Self-Adjusting TYrees
6.9 Heaps
6.10 Polish Notation and Expression Trees
6.11 Case Study: Computing Word Frequencies
6.12 Exercises
6.13 Programming Assignments

Chapter 7 Multiway Trees
7.1 The Family of B-Trees
7.2 Tires
7.3 Concluding Remarks
7.4 Case Study: Spell Checker
7.5 Exercises
7.6 Programming Assignments

Chapter 8 Graphs
8.1 Graph REpresentation
8.2 Graph Traversals
8.3 Shortest Path
8.4 Cycle Detection
8.5 Spanning Trees
8.6 Connectivity
8.7 Topological Sort
8.8 Networks
8.9 Matching
8.10 Eulerian and hamiltonian Graphs
8.11 Case Study: Distinct Representatives
8.12 Exercises
8.13 Programming Assignments

Chapter 9 Sorting
9.1 Elementary Sorting Algorithmns
9.2 Decision Trees
9.3 Efficient Sorting Algorithms
9.4 Sorting in the Standard Template Library
9.5 Concluding Remarks
9.6 Case Stuidy: Adding Polynomials
9.7 Exercises
9.8 Programming Assignments

Chapter 10 Hashing
10.1 Hash Functions
10.2 Collision Resolution
10.3 Deletion
10.4 Perfect Hash Functions
10.5 hash Functions for Extendible Files
10.6 Case Study: Hasing with Buckets
10.7 Exercises
10.8 Programming Assignments

Chapter 11 Data Compression
11.1 Conditions for Data Compression
11.2 huffman Coding
11.3 Shannon-Fano Code
11.4 Run-Length Encoding
11.5 Ziv-Lempel Code
11.6 Case Study: Huffman Method with Run-Length Encoding
11.7 Exercises
11.8 Programming Assignments

Chapter 12 Memory Management
12.1 The Sequential-Fit Methods
12.2 The Nonsequential-Fit Methods
12.3 Garbage Collection
12.4 Concluding REmarks
12.5 Case Study: An In-Place Garbage Collector
12.6 Exercises
12.7 Programming Assignments

Appendix A Computing Big-O

Appendix B Algorithms in the Standard Template Library

The study of data structures, a fundamental component of a computer science education, serves as the foundation upon which many other computer science fields are built. Some knowledge of data structures is a must for students who wish to do work in design implementation, testing, or maintenance of virtually any software system. The scope and presentation of material in Data Structures and Algorithms in C++ provide students with the necessary knowledge to perform such work. This book highlights three important aspects of data structures. First, a very strong emphasis is placed on the connection between data structures and their algorithms, including arfalyzing algorithms' complexity. Second, data structures are presented in the object-oriented setting in accordance with the current design and implementation paradigm. In particular, the information-hiding principle to advance encapsulation and decomposition is stressed. Finally, an important component of the book is data structure implementation, which leads to the choice of C++ as the programming language. The language C++, an object-oriented descendant of C, is widespread in industry and academia as an excellent programming language. It is also useful and natural for introducing data structures. Traditionally, Pascal has been used to teach data structures, although Modula-2 and Ada have also been used. However, because of the wide use of C++ in application programming and the object-oriented characteristics of the language, using C++ to teach a data structures and algorithms course, even on the introductory level, is well justified. This book provides the material for a course that includes the topics listed under CS2 and CS7 of the old ACM curriculum. It also meets the requirements for most of the courses CA 202, CD 202, and Cf 204 of the new ACM curriculum. Most chapters include a case study that illustrates a complete context in which certain algorithms and data structures can be used. These case studies were chosen from different areas of computer science such as interpreters, symbolic computation, and file processing, to indicate the wide range of applications to which topics under discussion may apply. Brief examples of C++ code are included throughout the book to illustrate the practical importance of data structures. However, theoretical analysis is equally important, so presentations of algorithms are integrated with analyses of efficiency. Great care is taken in the presentation of recursion because even advanced students have problems with it. Our experience has shown that recursion can be explained best ifthe run-time stack is taken into consideratiofi. Changes to the stack are shown when tracing a recursive function not only in the chapter on recursion but in other chapters as well. For example, a surprisingly short function for tree traversal may remain a mystery if work done by the system on the run-time stack is not included in the explanation. Standing aloof from the system and retaining only a purely theoretical perspective when discussing data structures and algorithms are not necessarily helpful. The thrust of this book is data structures, and other topics are treated here only as much as necessary to ensure a proper understanding of this subject. Algorithms are discussed from the perspective of data structures so that the reader will not find a comprehensive discussion of different kinds of algorithms and all the facets that a full presentation of algorithms requires. However, as mentioned, recursion is covered in depth. In addition, complexity analysis of algorithms is presented in some detail. Chapters l-8 present a number of different data structures and the algorithms that operate on them. The efficiency of each algorithm is analyzed, and improvements to the algorithm are suggested. ◆ Chapter 1 presents the basic principles of object-oriented programming, an introduction to dynamic memory allocation and the use of pointers, and a rudimentary presentation of the Standard Template Library (STL). ◆ Chapter 2 describes some methods used to assess the efficiency of algorithms. ◆ Chapter 3 presents different types of linked lists with an emphasis on their implementation with pointers. ◆ Chapter 4 presents stacks and queues and their applications. ◆ Chapter 5 contains a detailed discussion of recursion. Different types of recursion are discussed and a recursive call is dissected. ◆ Chapter 6 discusses binary trees, including implementation, traversal, and search. Balanced trees are also included in this chapter. ◆ Chapter 7 details more generalized trees such as tries, 2-4 trees, and B-trees. ◆ Chapter 8 presents graphs. ◆ Chapters 9-12 show different applications of data structures introduced in the previous chapters. They emphasize the data structure aspects of each topic under consideration. ◆ Chapter 9 analyzes sorting in detail, and several elementary and nonelementary methods are presented. ◆ Chapter 10 discusses hashing, one of the most important areas in searching. Various techniques are presented with an emphasis on the utilization of data structures. ◆ Chapter 11 discusses data compression algorithms and data structures. ◆ Chapter 12 presents various techniques and data structures for memory management. ◆ Appendix A discusses in greater detail big-O notation, introduced in Chapter 2. ◆ Appendix B presents standard algorithms in the Standard Template Library. Each chapter contains a discussion of the material illustrated with appropriate diagrams and tables. Except for Chapter 2, all chapters include a case study, which is an extended example using the features discussed in that chapter. All case studies have been tested using the Visual C++ compiler on a PC except the von Koch snowflake, which runs on a PC under Turbo C++. Following the text of the chapters is a set of exercises of varying degrees of difficulty. Except for Chapter 2, all chapters also include programming assignments and up-to-date bibliography of relevant literature. Chapters 1-6 (excluding Sections 2.9, 3.4, 6.4.3, 6.7, and 6.8) contain the core material that forms the basis of any data structures course. These chapters should be studied in sequence. The remaining six chapters can be taken in any order. A onesemester course could include Chapters 1-6, 9, and Sections 10.1 and 10.2. The entire book could also be part ora two-semester sequence. The source code for the text example programs is available via the WWW site at http://www.mathcs.duq.edu/drozdek/DSinCpp.