Data Structures and Algorithms in C++

by DROZDEK

• ISBN13: 9780534375973
• ISBN10: 0534375979
• Format: Paperback
• Copyright: 2000-06-30
• Publisher: Course Technology

Summary

Using the C++ programming language, author Adam Drozdek highlights three important aspects of data structures and algorithms. First, the book places special emphasis on the connection between data structures and their algorithms, including an analysis of the algorithms' complexity. Second, the book presents data structures in the context of object-oriented program design, stressing the principle of information hiding in its treatment of encapsulation and decomposition. Finally, the book closely examines data structure implementation. Overall, this practical and theoretical book prepares students with a solid foundation in data structures for future courses and work in design implementation, testing, or maintenance of virtually any software system.

Table of Contents

Object-Oriented Programming Using C++	1	(52)
Abstract Data Types	1	(1)
Encapsulation	2	(4)
Inheritance	6	(3)
Pointers	9	(11)
Pointers and Arrays	12	(2)
Pointers and Copy Constructors	14	(2)
Pointers and Destructors	16	(1)
Pointers and Reference Variables	17	(2)
Pointers to Functions	19	(1)
Polymorphism	20	(2)
C++ and Object-Oriented Programming	22	(1)
The Standard Template Library	23	(4)
Containers	23	(1)
Iterators	24	(1)
Algorithms	25	(1)
Function Objects	25	(2)
Vectors in the Standard Template Library	27	(8)
Data Structures and Object-Oriented Programming	35	(1)
Case Study: Random Access File	35	(13)
Exercises	48	(2)
Programming Assignments	50	(3)
Complexity Analysis	53	(22)
Computational and Asymptotic Complexity	53	(1)
Big-O Notation	54	(3)
Properties of Big-O Notation	57	(1)
Ω and &OHgr; Notations	58	(1)
Possible Problems	59	(1)
Examples of Complexities	60	(1)
Finding Asymptotic Complexity: Examples	61	(2)
The Best, Average, and Worst Cases	63	(3)
Amortized Complexity	66	(5)
Exercises	71	(4)
Linked Lists	75	(62)
Singly Linked Lists	75	(15)
Insertion	81	(3)
Deletion	84	(6)
Search	90	(1)
Doubly Linked Lists	90	(5)
Circular Lists	95	(2)
Skip Lists	97	(5)
Self-Organizing Lists	102	(4)
Sparse Tables	106	(4)
Lists in the Standard Template Library	110	(4)
Deques in the Standard Template Library	114	(5)
Concluding Remarks	119	(1)
Case Study: A Library	120	(3)
Exercises	123	(10)
Programming Assignments	133	(4)
Stacks and Queues	137	(34)
Stacks	137	(8)
Queues	145	(9)
Priority Queues	154	(1)
Stacks in the Standard Template Library	155	(1)
Queues in the Standard Template Library	156	(1)
Priority Queues in the Standard Template Library	156	(4)
Case Study: Exiting a Maze	160	(6)
Exercises	166	(3)
Programming Assignments	169	(2)
Recursion	171	(45)
Recursive Definitions	171	(3)
Function Calls and Recursion Implementation	174	(2)
Anatomy of a Recursive Call	176	(3)
Tail Recursion	179	(2)
Nontail Recursion	181	(5)
Indirect Recursion	186	(2)
Nested Recursion	188	(1)
Excessive Recursion	189	(3)
Backtracking	192	(8)
Concluding Remarks	200	(1)
Case Study: A Recursive Descent Interpreter	201	(8)
Exercises	209	(4)
Programming Assignments	213	(3)
Binary Tress	216	(86)
Trees, Binary Trees, and Binary Search Trees	216	(5)
Implementing Binary Trees	221	(3)
Searching a Binary Search Tree	224	(2)
Tree Traversal	226	(16)
Breadth-First Traversal	227	(1)
Depth-First Traversal	227	(7)
Stackless Depth-First Traversal	234	(8)
Insertion	242	(3)
Deletion	245	(7)
Deletion by Merging	246	(3)
Deletion by Copying	249	(3)
Balancing a Tree	252	(12)
The DSW Algorithm	255	(3)
AVL Trees	258	(6)
Self-Adjusting Trees	264	(7)
Self-Restructuring Trees	264	(1)
Splaying	265	(6)
Heaps	271	(8)
Heaps as Priority Queues	272	(3)
Organizing Arrays as Heaps	275	(4)
Polish Notation and Expression Trees	279	(5)
Operations on Expression Trees	281	(3)
Case Study: Computing Word Frequencies	284	(7)
Exercises	291	(4)
Programming Assignments	295	(7)
Multiway Trees	302	(69)
The Family of B-Trees	303	(42)
B-Trees	304	(10)
B*-Trees	314	(2)
B+-Trees	316	(3)
Prefix B+-Trees	319	(1)
Bit-Trees	320	(3)
R-Trees	323	(1)
2-4 Trees	324	(8)
Sets and Multisets in the Standard Template Library	332	(7)
Maps and Multimaps in the Standard Template Library	339	(6)
Tries	345	(8)
Concluding Remarks	353	(1)
Case Study: Spell Checker	354	(10)
Exercises	364	(2)
Programming Assignments	366	(5)
Graphs	371	(81)
Graph Representation	373	(1)
Graph Traversals	373	(5)
Shortest Paths	378	(10)
All-to-All Shortest Path Problem	385	(3)
Cycle Detection	388	(3)
Union-Find-Problem	388	(3)
Spanning Trees	391	(5)
Boruvka's Algorithm	392	(1)
Kruskal's Algorithm	393	(1)
Jarnik-Prim's Algorithm	393	(3)
Dijkstra's Method	396	(1)
Connectivity	396	(6)
Connectivity in Undirected Graphs	397	(3)
Connectivity in Directed Graphs	400	(2)
Topological Sort	402	(2)
Networks	404	(13)
Maximum Flows	404	(10)
Maximum Flows of Minimum Cost	414	(3)
Matching	417	(11)
Assignment Problem	424	(2)
Matching in Nonbipartite Graphs	426	(2)
Eulerian and Hamiltonian Graphs	428	(4)
Eulerian Graphs	428	(1)
Hamiltonian Graphs	429	(3)
Case Study: Distinct Representatives	432	(12)
Exercises	444	(4)
Programming Assignments	448	(4)
Sorting	452	(52)
Elementary Sorting Algorithms	453	(7)
Insertion Sort	453	(3)
Selection Sort	456	(2)
Bubble Sort	458	(2)
Decision Trees	460	(3)
Efficient Sorting Algorithms	463	(25)
Shell Sort	463	(5)
Heap Sort	468	(3)
Quicksort	471	(7)
Mergesort	478	(2)
Radix Sort	480	(8)
Sorting in the Standard Template Library	488	(1)
Concluding Remarks	489	(2)
Case Study: Adding Polynomials	491	(7)
Exercises	498	(2)
Programming Assignments	500	(4)
Hashing	504	(39)
Hash Functions	505	(2)
Division	505	(1)
Folding	505	(1)
Mid-Square Function	506	(1)
Extraction	506	(1)
Radix Transformation	507	(1)
Collision Resolution	507	(10)
Open Addressing	508	(5)
Chaining	513	(2)
Bucket Addressing	515	(2)
Deletion	517	(1)
Perfect Hash Functions	518	(6)
Cichelli's Method	519	(2)
The FHCD Algorithm	521	(3)
Hash Functions for Extendible Files	524	(6)
Extendible Hashing	524	(3)
Linear Hashing	527	(3)
Case Study: Hashing with Buckets	530	(9)
Exercises	539	(1)
Programming Assignments	540	(3)
Data Compression	543	(38)
Conditions for Data Compression	543	(2)
Huffman Coding	545	(14)
Adaptive Huffman Coding	555	(4)
Shannon-Fano Code	559	(2)
Run-Length Encoding	561	(1)
Ziv-Lempel Code	562	(3)
Case Study: Huffman Method with Run-Length Encoding	565	(12)
Exercises	577	(1)
Programming Assignments	578	(3)
Memory Management	581	(62)
The Sequential-Fit Methods	582	(2)
The Nonsequential-Fit Methods	584	(8)
Buddy Systems	585	(7)
Garbage Collection	592	(18)
Mark-and-Sweep	593	(7)
Copying Methods	600	(2)
Incremental Garbage Collection	602	(8)
Concluding Remarks	610	(1)
Case Study: An In-Place Garbage Collector	611	(8)
Exercises	619	(2)
Programming Assignments	621	(6)
Appendixes
A Computing Big-O	627	(6)
A.1 Harmonic Series	627	(1)
A.2 Approximation of the Function lg(n!)	627	(2)
A.3 Big-O for Average Case of Quicksort	629	(2)
A.4 Average Path Length in a Random Binary Tree	631	(2)
B Algorithms in the Standard Template Library	633	(10)
B.1 Standard Algorithms	633	(10)
Name Index	643	(4)
Subject Index	647