Data Structures and Algorithms in C++

by Michael T. Goodrich (Univ. of California, Irvine ); Roberto Tamassia (Brown Univ.); David M. Mount (Univ. of Maryland )

• ISBN13: 9780471202080
• ISBN10: 0471202088
• Edition: 1
• Format: Paperback
• Copyright: 2003-02-01
• Publisher: Wiley

Summary

* Provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation * Each data structure is presented using ADTs and their respective implementations * Helps provide an understanding of the wide spectrum of skills ranging from sound algorithm and data structure design to efficient implementation and coding of these designs in C++ Wiley Higher Education

Table of Contents

Preface	ix
Basic C++ Programming	1	(60)
Basic C++ Programming Elements	3	(14)
Expressions	17	(7)
Control Flow	24	(4)
Functions	28	(5)
Classes	33	(13)
C++ Program and File Organization	46	(6)
Writing a C++ Program	52	(5)
Exercises	57	(4)
Object-Oriented Design	61	(46)
Goals and Principles	63	(6)
Inheritance and Polymorphism	69	(20)
Templates	89	(3)
Exceptions	92	(5)
Recursion and Other Design Patterns	97	(6)
Exercises	103	(4)
Analysis Tools	107	(36)
Running Time and Pseudo-Code	109	(4)
A Quick Mathematical Review	113	(3)
Justification Techniques*	116	(4)
Analysis of Algorithms	120	(3)
Asymptotic Notation	123	(6)
Asymptotic Analysis	129	(6)
Exercises	135	(8)
Stacks, Queues, and Recursion	143	(60)
Using Recursion	145	(11)
Stacks	156	(13)
Queues	169	(7)
Linked Lists	176	(7)
Double-Ended Queues	183	(7)
Sample Case Study Application	190	(6)
Exercises	196	(7)
Vectors, Lists, and Sequences	203	(50)
Vectors	205	(10)
Lists	215	(13)
Sequences	228	(7)
Case Study: Bubble-Sort on a Sequence	235	(3)
Iterators	238	(4)
A Hierarchy of Sequence ADTs	242	(3)
Exercises	245	(8)
Trees	253	(58)
The Tree Abstract Data Type	255	(7)
Basic Algorithms on Trees	262	(11)
Binary Trees	273	(16)
Data Structures for Representing Trees	289	(12)
Exercises	301	(10)
Priority Queues	311	(52)
The Priority Queue Abstract Data Type	313	(10)
Implementing a Priority Queue with a Sequence	323	(7)
Heaps	330	(19)
The Locator Design Pattern	349	(8)
Exercises	357	(6)
Dictionaries	363	(48)
The Dictionary Abstract Data Type	365	(6)
Hash Tables	371	(17)
Ordered Dictionaries	388	(6)
Skip Lists	394	(9)
Locator-Based Dictionary Functions *	403	(2)
Exercises	405	(6)
Search Trees	411	(72)
Binary Search Trees	414	(12)
AVL Trees	426	(11)
Multi-Way Search Trees	437	(4)
(2,4) Trees	441	(8)
Red-Black Trees	449	(19)
Locator-Based Search Trees *	468	(2)
External Searching *	470	(5)
Exercises	475	(8)
Sorting, Sets, and Selection	483	(50)
Merge-Sort	485	(13)
The Set ADT	498	(6)
Quick-Sort	504	(11)
A Lower Bound on Comparison-Based Sorting	515	(2)
Bucket-Sort and Radix-Sort	517	(3)
Comparison of Sorting Algorithms	520	(2)
Selection	522	(4)
Exercises	526	(7)
Text Processing	533	(42)
String Operations	535	(3)
Pattern Matching Algorithms	538	(12)
Tries	550	(11)
Text Compression	561	(3)
Text Similarity Testing	564	(5)
Exercises	569	(6)
Graphs	575	(82)
The Graph Abstract Data Type	577	(8)
Data Structures for Graphs	585	(10)
Graph Traversal	595	(16)
Directed Graphs	611	(14)
Weighted Graphs	625	(1)
Shortest Paths	626	(11)
Minimum Spanning Trees	637	(10)
Exercises	647	(10)
A Useful Mathematical Facts	657	(8)
Bibliography	665	(6)
Index	671