本书使用c++作为教学语言，讲授了数据结构及其实现的基础知识。书中引导学生通过对方法接口、示例和应用的学习，逐渐理解和掌握如何高效地使用数据结构。适合课堂教学和自学参考。
本书特色
大多数数据结构用STL(标准模板库)提供，并详细探究了STL数据结构的规范实现，同时讨论了一些数据结构的其他实现方式，可以使学生尽早接触工程实践，为未来的课程设计和实际工作打下坚实基础。
每章都包括一个程序设计项目，学生可以自己开发和实现数据结构，或者扩展和应用这一章介绍的数据结构。
配套网站WWW.mhhe.com/collins中有配套实验、PowerPoint文稿、习题解答等丰富的资源，大大方便教学。
This book is intended for a course in data structures and algorithms. The implementation language is C++, and it is assumed that students have taken an introductory course in which that language was used. That course need not have been object-oriented, but it should have covered the fundamental statementsand data types, as well as arrays and the basics of file processing.
THE STANOARD TEMPLATE LIBRARY
One of the distinctive features of this text is its reliance on the Standard Template Library-specifically, the implementation of that library provided by the HewlettPackard Company. There are several advantages to this approach. First, students will be working with code that has been extensively tested; they need not depend on modules created by the instructor or textbook author. Second, students will have the opportunity to study professionals' code, which is substantially more efficient-and succinct-than what students have seen before. Third, the library is available for later courses in the curriculum, and beyond!
For the most part, the library does not prescribe an implementation of these data structures. This has the advantage that we can initially focus on the services provided to users rather than on implementation details. For the definitions of these classes, we turn to the original implementation by Stepanov and others (see Stepanov and Lee,1994) at Hewlett-Packard Research Labs. This Hewlett-Packard implementation is the basis for all implementations the author is aware of.
OTHER IMPLEMENTATIONS CONSIDERED
As imponant as the Hewlett-Packard implementation of the Standard Template Library is, it cannot be the exclusive focus of such a fundamental course in data structures and algorithms. Approaches that differ from those in the Hewlett-Packard implementation also deserve consideration. For example, the implementation of the list class utilizes a doubly linked list with a header node, so there is a separate section on singly linked lists and doubly linked lists with head and tail fields. There is also a discussion of the trade-offs of one design over the other. Also, there is coverage of data structures (such as graphs) and algorithms (such as backtracking) that are not yet included in the Standard Template Library.
This text also satisfies another essential need of a data structures and algorithms course: Students practice developing their own data structures. There are programming projects in which data structures are either created "from the ground up" or extended from examples in the chapters. And there are other projects to develop or extend applications that use the Standard Template Library.
STANDARD C++
AII the code presented is based on ANSI/ISO Standard C++ and has been tested both on a Windows platform (C++Builder and Visual C++) and on a Unix platform (G++). The Standard Template Library specincations-but no particular implementation-are part of ANSI/ISO C++ .
PEDAGOGICAL FEATURES
This text offers several features that may improve the teaching environment for instructors and the learning environment for students. Each chapter starts with a list of objectives and concludes with at least one major programming assignment. Each data structure is carefully described, with a precondition and postcondition for each method. In addition, most qf the methods include examples of how to call the method, and the results of that call.
The details, especially of the Hewlett-Packard implementation of the Standard Template Library, are carefully investigated in the text and reinforced in a suite of 29 labs. See the "Organization of the Labs" section of this preface for more information about these labs. Each chapter has a variety of exercises, and the answers to all the exercises are available to the instructor.
SUPPORT MATERIAL
The website for all the support material is www.mhhe.com/collins
That website has links to the tollowing information for students:An overview of the labs and how to access them The source code for all projects developed in the text Applets for projects that have a strong visual component Additionally, instructors can obtain the following from the website:
Instructors' options with regard to the labs PowerPoint slides for each chapter(approximately 1500 slides)Answers to every chapter exercise, PowerPoint-presentation exercise, and
lab experiment
SYNOPSES OF THE CHAPIERS
Chapter I presents those features of C++ that serve as the foundation for subsequent chapters. Most of the material reflects an object orientation: classes, inheritance. constructors, destructors, and operator overloading. There are lab experiments to review classes, as well as on inheritance and operator overloading.
Chapter 2 introduces container classes and issues related to the storage of containers. Pointers are needed both for contiguous and linked storage. As an illustration of linked storage, a singly-linked-list class is created. This oversimplified Linked class provides a backdrop for presenting several key features of the Standard Template Library, such as templates, iterators, and generic algorithms. The associated lab experiments are on pointers, iterators, operator overloading, and generic algorithms.
Chapter 3, an introduction to software engineering, outlines the four stages of the software-development life cycle: analysis, design, implementation, and maintenance. The Unitied Modeling Language is introduced as a design tool to depict inheritance, composition, and aggregation. Big-O notation, which pervades subsequent chapters, allows environment-independent estimates of the time requirements for methods. Both ran-time validation, with drivers, and timing are discussed, and for each of those topics there is a follow-up lab.
Chapter 4, on recursion, represents a temporary shift in emphasis from data structares to algorithms. Backtracking is introduced, as a general technique for problem solving. And the same BackTrack class is used for searching a maze; placing eight queens on a chessboard, where none is under attack by another queen; and illustrating that a knight can traverse every square in a chessboard without landing on any square more than once. Other applications of recursion, sach as for the Towers ot Hanoi game and generating permutations, further highlight the elegance of recursion, especially when compared to the comesponding iterative methods. Recursion is also encountered in later chapters, notably in the implementation of Quick Sort and in the definition of binary trees. Moreover, recursion is an indispensableeven if seldom used-tool for every computing professional.
In Chapter5, we begin our study of the Standard Template Library with the vector and deque classes. A vector is a smart array: automatically resizable, and with methods to handle insertions and deletions at any index. Furthermore, vectors are templated, so the method to insert an int item into a vector of int items is the same method used to insert a string item into a vector of string items. The design starts with the method interface-precondition, postcondition, and method heading-of the most widely used methods in the vector class. There follows an outline of the Hewlett-Packard implementation, and further details are available in a lab. The application of the vector class, high-precision arithmetic, is essential for public-key cryptography.This application is extended in a lab and in a programming project. A deqae is similar to a vector, at least from a data structures perspective. But the implementation details are considerably different, and some of these details are investigated in a lab.
Chapter 6 presents the list data structure and class, characterized by linear-time methods for inserting, removing, or retrieving at an arbitrary position. This property makes a compelling case for the use of list iterators; objects that traverse a list object and have constant-time methods for inserting, removing, or retrieving at the "current" iterator position. The doubly linked, circular implementation is introduced in this chapter, and additional details are covered in a lab. The application is a small line editor, for which list iterators are well suited. This application is extended in a programming project. There is a lab experiment on iterator categories, and another to perform a run-time comparison of vectors, deques, and lists.The queue and stack classes are the subjects of Chapter 7. Both of these classes are container adaptors: They adapt the method interfaces of some other class. For both the queue and stack classes, the default "other" class is the deque class. The resulting method definitions for the stack and queue classes are one-liners. The specific application of queues-calculating the average waiting time at a car washfalls into the general category of computer simulation. There are two applications of the stack class: the implementation of recursion, and the conversion from infix to postfix. This latter application is expanded in a lab, and forms the basis for a project on evaluating a condition.
Chapter 8 focuses on binary trees in general, and binary search trees in particular. The essential features of binary trees are presented; these are important for understanding later material on AVL trees, red-black trees, heaps, Huffman trees,and decision trees. The binary-search-tree class is a monochromatic version of the Hewlett-Packard implementation of red-black trees.
In Chapter 9, we look at AVL trees. Rotations are introduced as the mechanism by which rebalancing is accomplished. With the help of Fibonacci trees, we establish that the height of an AVL tree is always logarithmic in the number of items in the tree. The AVLTree class is not part of the Standard Template Library, but includes several important features, such as function objects; there is a follow-up lab on this difficult topic. The entire class is implemented, except for the erase method(Project 9.1 ). The application of AVL trees. is a simple spell-checker. Red-black trees are investigated in Chapter 10. The algorithms for inserting and deleting in a red-black tree are carefully studied, and there are associated lab experiments. Red-black trees are not in the Standard Template Library, but they are the basis for most implementations of four associative-container classes that are in the Standard Template Library: the set, map, multiset, and multimap classes. In a set, each item consists of a key only, and doplicate keys are not allowed. A multiset allows duplicate keys. In a map, each item has a unique key part and also another part. A multimap allows duplicate keys. There is an application to count the frequency of each word in a file, and lab experiments on the four associative-container classes.
Chapter 11 introduces the priority_queue class, which is another container adaptor. The default is the vector class, but behind the scenes there is a heap, allowing insertions in constant average time, and removal of the highest-priority element in logarithmic time, even in the worst case. Implementations that are list-based and setbased are also considered. The application is in the area of data compression, specifically, Huffman encodings: Given a text file, generate a minimal, prefix-free encoding. The project assignment is to convert the encoding back to the original text file.
The lab experiment incorporates fairness into a priority queue, so that ties for the highest-priority item are always resolved in favor of the item that was on the priority queue for the longest time.
Sorting is the topic of Chapter 12. Estimates of the minimum lower bounds for comparison-based sons are developed. Four "fast" Sorts are investigated: Tree Sort (for multisets), Heap Sort (for random-access containers), Merge sort (for lists). and Quick sort (for random-access containers). The chapter's lab experiment compares these sorts on randomly generated values. The project assignment is to sort a file of names and social security numbers.
Chapter 13 starts with a review of sequential and binary searching, and then investigates hashing. Currently there are no hash classes supported by either Standard C++ or the Hewlett-Packard implementation of the Standard Template Library. A hash_ map class is developed. This class has method interfaces that are identical to those in the map class, except that the average time for inserting, deleting, or searching is constant instead of logarithmic! Applications include the creation and maintenance of a symbol table, and a revision of the spell-checker application from Chapter 9. There is also a comparison of chained hashing and open-address hashing; this comparison is further explored in a programming project.The speed of the hash_map class is the subject of a lab experiment.The most general data structures-graphs, trees, and networks-are presented in Chapter 14. There are outlines of the essential algorithms: breadth-first iteration,depth-first iteration, connectedness, finding a minimum spanning tree, and finding the shortest path between two vertices. The only class developed is the (directed) network class, with an adjacency-list implementation. Other classes, such as undi.rected_graph and undirected_network, can be straightforwardly defined as subclasses of the network class. The Traveling Salesperson problem is investigated in a lab, and there is a programming project to complete an adjacency-matrix version of the network class. Another backtracking application is presented, with the same BackTrack class that was introduced in Chapter 4.With each chapter, there is an associated web page that includes all programs developed in the chapter, and applets, where appropriate, to animate the concepts presented.
APPENDICES
Appendix 1 contains the background that will allow students to comprehend the mathematical aspects of the chapters. Sammation notation and the rudimentary properties of logarithms are essential, and the material on mathematical induction will lead to a deeper appreciation of the analysis of binary trees and open-address hashing.
The string class is the sobject of Appendix 2. This powerful class is an important part of the Standard Template Library and allows students to avoid the drudgery of character arrays.
Polymorphism, the ability of a pointer to refer to different objects in an object bierarchy, is introduced in Appendix 3. Polymorphism is an essential feature of object-oriented programming, but has been relegated to appendix status because it is not a necessary topic in an introduction to data structures and algorithms.
ORGANIZATION OF THE LABS
There are 29 website labs associated with this text. For both students and instructors, the Uniform Resource Locator (URL) is www.mhhe.com/collins
The labs do not contain essential material, but provide reinforcement of the text material. For example, after the vector, deque, and list classes have been investigated, there is a lab to perform some timing experiments on those three classes.
The labs are self-contained, so the instructor has considerable flexibility in assigning the labs. They can be assigned as
1. Closed labs
2. Open labs
3. Ungraded homework
In addition to the obvious benefit of promoting active learning, these labs also encourage use of the scientific method. Basically, each lab is set up as an experiment. Students observe some phenomenon, such as the organization of the Standard Template Library's list class. They then formulate and submit a hypothesis-with their own code-about the phenomenon. After testing and, perhaps, revising their hypothesis, they submit the concions they drew from the experiment.
ACKNOWLEDGMNTS
Chun Wai Liew initiated the study of the Standard Template Library at Lafayette College, and also contributed his general expertise in C++. The following reviewers made many helpful suggestions:
Moe Bidgoli, Saginaw Valley State University
Scott Cannon, Utah State University
Jiang-Hsing Chu, Southern llIinois University, Carbondale
Karen C. Davis, University of Cincinnati
Matthew Evett, Florida Atlantic University
Eduardo B. Fernandez, Florida Atlantic State University
Sheila Foster, California State University, Long Beach
Mahmood Haghighi, Bradley University
Jack Hodges, San Francisco State University
Robert A. Hogue, Youngsfown State University
Christopher Lacher, Florida State University
Gopal Lakhani, Texas Tech University
Tracy Bradley Maples, California State University, Long Beach
Nancy E. Miller, Mississippi State University
G. M. Prabhu, lowa State University
Zhi-Li Zhang, University of Minnesota
It was a pleasure to work with the McGraw-Hill team: Emily Lupash, Betsy Jones,Jane Mohr, Lucy Mullins, and Philip Meek.
Several students from Lafayette College made important contributions. Eric Panchenko created all the applets and many of the driver programs. And Eric, along with Yi Sun and Xenia Taoubina, developed the overall format of the labs. Finally, I am indebted to all the students at Lafayette College who participated in the class testing of the book and endured earlier versions of the labs.
Bill Collins
CHAPTER l
Classes in C++ 1
1. 1 Classes 2
CHAPTER 2
Storage Structures for Container
Classes 3s
2. 1 Pointers 36
2. 2 Arrays 41
2. 3 Container Classes 42
CHAPIER 3
Introduction to Software
Engineering 63
3. 1 The Software Developmental Life Cycle 64
3. 2 Problem Analysis 64
3. 3 Program Design 67
3. 4 Program Implementation 71
3 .5 Program Maintenance 87
CHAPTER 4
4. 1 Introduction 94
4. 2 Factorials 94
4. 3 Decimal-to-Binary 99
4. 4 Towers of Hanoi 103
4. 5 Backtracking 112
4. 6 Binary Search 125
4. 7 Generating Permutations 135
4. 8 Indirect Recursion 144
4. 9 The Cost of Recursion 145
Summary 146
Exercises 147
Programming Project 4.1 : An Iterative Version of
Towers of Hanoi 154
Programming Project 4.2: The Eight-Queens Problem 156
Programming Project 4.3: A Knight's Tour 158
CHAPTER 5
5. 1 The Standard Template Library 164
5. 2 Vectors 165
5. 3 A Vector Application: High-Precision Arithmetic 184
5. 4 Deques 190
5. 5 A Deque Application: Very Long Integers 198
Summary 199
Exercises 199
Programming Project 5.1: Extending the very_long_int Class 203
Programming Project 5.2: An Alternative
Implementation of the deque Class 204
CHAPTER 6
Lists 205
6. 1 Lists 206
6. 2 List Application: A Line Editor 228
Summary 240
Exercises 241
Programming Project 6.1: Extending the Editor Class 244
Programming Project 6.2: An Alternate Design and
Implementation of the list Class 251
CHAPTER 7
Queues and Staeks 253
7. 1 Queues 254
7. 2 Computer Simulation 261
7. 3 A Queue Application: A Simulated Car Wash 264
7. 4 Stacks 274
7. 5 Stack Application 1: How Recursion Is Implemented 277
7. 6 Stack Application 2: Conveting Infix to Postfix 285
Summary 295
Exercises 295
Programming Project 7.1:Extending the Car Wash Application 298
Programming Project 7.2: Evaluating a Condition 300
Programming Project 7.3: An Iterative Maze Search 304
Programming Project 7.4: An Alternate Design of the queue Class 305
CHAPTER 8
Binary Trees and Binary Search
8. 1 Definition and Properties 308
8. 2 Binary Search Trees 324
Summary 345
Exercises 346
Programming Project 8. 1 : Alternative
Implementation of the BinSearch Tree Class 350
CHAPTERg 9
AVL Ttees 353
9. 1 Balanced Binary Search Trees 354
9. 2 Rotations 354
9. 3 AVL Trees 358
9. 4 AVL Tree Application: A Simple Spell-Checker 380
Summary 383
Exercises 384
Programming Project 9.1: The erase Method in the AVLTree Class 388
Programming Project 9.2: Enhancing the SpeIIChecker
Project 389
CHAPTER 10
Red-Black Trees 391
10. 1 Red-Black Trees 392
10. 2 The Standard Template Library's Associative
Containers 422
10. 3 Set Application: Spell-Checker, Revisited 425
Summary 432
Exercises 432
Programming Project 10.1: A Simple Thesauras 436
Programming Project 10.2: Building a Concordance 437
CHAPTER 11
Priority Queues
11.1 Introduction 440
11.2 Application of Priority Queues: Huffman Codes 456
Summary 469
Exercises 469
Programming Project 11.1: Decoding a Message 473
CHAPTER 12
Sorting 477
12.1 Introduction 478
12.2 How Fast Can We son 481
12.3 Fast Sorts 483
Summary 501
Exercises 501
Programming Project 12.1: Sorting a File 509
CHPTER 13
Searehing and the Hash
Classe
13.1 A Framework to Analyze Searching 514
13.2 Review of Searching 514
13.3 The hash_map Class 517
13.4 The hash set Class 540
13.5 Open-Address Hashing 540
Summary 557
Exercises 558
Programming Project 13.1: A Run-Time
Comparison of Chaining and Double Hashing in Building a Symbol Table 561
CHAPTER 14
14. 1 Undirected Graphs 564
14. 2 Directed Graphs 567
14. 3 Trees 568
14. 4 Networks 569
14. 5 Oraph Algorithms 571
14. 6 Developing a Network Class 588
14. 7 The network Class 589
14.8 Backtracking through a Network 607
Summary 610
Exercises 610
Programming Project 14.1 : Completing the
Adjacency-Matrix Implementation 614
Programming Project 14.2: Backtracking through a Network 615
APPENDIX 1
A1. 1 Introduction 619
A1. 2 Functions and Sequences 619
A1. 3 Sums and Products 620
A1. 4 Logarithms 621
A1. 5 Mathematical Induction 623
A1. 6 Induction and Recursion 630
APPENDIX 2
The string
A2. 1 Introduction 633
A2. 2 Declaration of the string Class 633
A2. 3 Fields and Implementation of the string Class 644
APPENDIX 3
Polymorphism 647
A3. 1 Introduction 647
A3. 2 The Importance of Polymorphism 648
A3. 3 Dynamic Binding 649
References 651
Index 653
