Data Structures And Algorithms In C++

by Drozdek, Adam

• ISBN13: 9780534491826
• ISBN10: 0534491820
• Edition: 3rd
• Format: Hardcover
• Copyright: 2004-09-24
• Publisher: Cengage Learning

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

1 OBJECT-ORIENTED PROGRAMMING USING C++	1	(51)
1.1 Abstract Data Types	1	(1)
1.2 Encapsulation	1	(5)
1.3 Inheritance	6	(3)
1.4 Pointers	9	(12)
1.4.1 Pointers and Arrays	12	(2)
1.4.2 Pointers and Copy Constructors	14	(2)
1.4.3 Pointers and Destructors	16	(1)
1.4.4 Pointers and Reference Variables	17	(2)
1.4.5 Pointers to Functions	19	(2)
1.5 Polymorphism	21	(2)
1.6 C++ and Object-Oriented Programming	23	(1)
1.7 The Standard Template Library	24	(3)
1.7.1 Containers	24	(1)
1.7.2 Iterators	24	(1)
1.7.3 Algorithms	25	(1)
1.7.4 Function Objects	26	(1)
1.8 Vectors in the Standard Template Library	27	(8)
1.9 Data Structures and Object-Oriented Programming	35	(1)
1.10 Case Study: Random Access File	36	(11)
1.11 Exercises	47	(2)
1.12 Programming Assignments	49	(2)
Bibliography	51	(1)
2 COMPLEXITY ANALYSIS	52	(24)
2.1 Computational and Asymptotic Complexity	52	(1)
2.2 Big-O Notation	53	(2)
2.3 Properties of Big-O Notation	55	(2)
2.4 Ω and Θ Notations	57	(1)
2.5 Possible Problems	58	(1)
2.6 Examples of Complexities	59	(1)
2.7 Finding Asymptotic Complexity: Examples	60	(2)
2.8 The Best, Average, and Worst Cases	62	(3)
2.9 Amortized Complexity	65	(4)
2.10 NP-Completeness	69	(3)
2.11 Exercises	72	(3)
Bibliography	75	(1)
3 LINKED LISTS	76	(61)
3.1 Singly Linked Lists	76	(15)
3.1.1 Insertion	82	(2)
3.1.2 Deletion	84	(6)
3.1.3 Search	90	(1)
3.2 Doubly Linked Lists	91	(4)
3.3 Circular Lists	95	(2)
3.4 Skip Lists	97	(5)
3.5 Self-Organizing Lists	102	(5)
3.6 Sparse Tables	107	(3)
3.7 Lists in the Standard Template Library	110	(4)
3.8 Deques in the Standard Template Library	114	(5)
3.9 Concluding Remarks	119	(1)
3.10 Case Study: A Library	120	(11)
3.11 Exercises	131	(2)
3.12 Programming Assignments	133	(3)
Bibliography	136	(1)
4 STACKS AND QUEUES	137	(33)
4.1 Stacks	137	(8)
4.2 Queues	145	(9)
4.3 Priority Queues	154	(1)
4.4 Stacks in the Standard Template Library	155	(1)
4.5 Queues in the Standard Template Library	155	(2)
4.6 Priority Queues in the Standard Template Library	157	(2)
4.7 Case Study: Exiting a Maze	159	(7)
4.8 Exercises	166	(1)
4.9 Programming Assignments	167	(2)
Bibliography	169	(1)
5 RECURSION
5.1 Recursive Definitions	170	(3)
5.2 Function Calls and Recursion Implementation	173	(2)
5.3 Anatomy of a Recursive Call	175	(3)
5.4 Tail Recursion	178	(1)
5.5 Nontail Recursion	179	(6)
5.6 Indirect Recursion	185	(2)
5.7 Nested Recursion	187	(1)
5.8 Excessive Recursion	187	(4)
5.9 Backtracking	191	(7)
5.10 Concluding Remarks	198	(1)
5.11 Case Study: A Recursive Descent Interpreter	199	(9)
5.12 Exercises	208	(3)
5.13 Programming Assignments	211	(3)
Bibliography	214	(1)
6 BINARY TREES	215	(85)
6.1 Trees, Binary Trees, and Binary Search Trees	215	(5)
6.2 Implementing Binary Trees	220	(3)
6.3 Searching a Binary Search Tree	223	(2)
6.4 Tree Traversal	225	(16)
6.4.1 Breadth-First Traversal	226	(1)
6.4.2 Depth-First Traversal	227	(7)
6.4.3 Stackless Depth-First Traversal	234	(7)
6.5 Insertion	241	(3)
6.6 Deletion	244	(7)
6.6.1 Deletion by Merging	245	(2)
6.6.2 Deletion by Copying	247	(4)
6.7 Balancing a Tree	251	(11)
6.7.1 The DSW Algorithm	254	(3)
6.7.2 AVL Trees	257	(5)
6.8 Self-Adjusting Trees	262	(7)
6.8.1 Self-Restructuring Trees	263	(1)
6.8.2 Splaying	264	(5)
6.9 Heaps	269	(28)
6.9.1 Heaps as Priority Queues	271	(1)
6.9.2 Organizing Arrays as Heaps	272	(5)
6.10 Polish Notation and Expression Trees	277	(5)
6.10.1 Operations on Expression Trees	279	(3)
6.11 Case Study: Computing Word Frequencies	282	(8)
6.12 Exercises	290	(3)
6.13 Programming Assignments	293	(4)
Bibliography	297	(3)
7 MULTIWAY TREES	300	(76)
7.1 The Family of B-Trees	301	(48)
7.1.1 B-Trees	302	(10)
7.1.2 B*-Trees	312	(2)
7.1.3 B+-Trees	314	(3)
7.1.4 Prefix B+-Trees	317	(1)
7.1.5 Bit-Trees	318	(3)
7.1.6 R-Trees	321	(1)
7.1.7 2-4 Trees	322	(16)
7.1.8 Sets and Multisets in the Standard Template Library	338	(6)
7.1.9 Maps and Multimaps in the Standard Template Library	344	(5)
7.2 Tries	349	(9)
7.3 Concluding Remarks	358	(1)
7.4 Case Study: Spell Checker	358	(11)
7.5 Exercises	369	(1)
7.6 Programming Assignments	370	(4)
Bibliography	374	(2)
8 GRAPHS	376	(98)
8.1 Graph Representation	378	(2)
8.2 Graph Traversals	380	(3)
8.3 Shortest Paths	383	(10)
8.3.1 All-to-All Shortest Path Problem	390	(3)
8.4 Cycle Detection	393	(3)
8.4.1 Union-Find Problem	394	(2)
8.5 Spanning Trees	396	(4)
8.6 Connectivity	400	(6)
8.6.1 Connectivity in Undirected Graphs	400	(3)
8.6.2 Connectivity in Directed Graphs	403	(3)
8.7 Topological Sort	406	(2)
8.8 Networks	408	(15)
8.8.1 Maximum Flows	408	(10)
8.8.2 Maximum Flows of Minimum Cost	418	(5)
8.9 Matching	423	(48)
8.9.1 Stable Matching Problem	427	(3)
8.9.2 Assignment Problem	430	(2)
8.9.3 Matching in Nonbipartite Graphs	432	(2)
8.10 Eulerian and Hamiltonian Graphs	434	(10)
8.10.1 Eulerian Graphs	434	(4)
8.10.2 Hamiltonian Graphs	438	(6)
8.11 Graph Coloring	444	(3)
8.12 NP-Complete Problems in Graph Theory	447	(5)
8.12.1 The Clique Problem	447	(1)
8.12.2 The 3-Colorability Problem	448	(2)
8.12.3 The Vertex Cover Problem	450	(1)
8.12.4 The Hamiltonian Cycle Problem	451	(1)
8.13 Case Study: Distinct Representatives	452	(13)
8.14 Exercises	465	(5)
8.15 Programming Assignments	470	(1)
Bibliography	471	(3)
9 SORTING	474
9.1 Elementary Sorting Algorithms	475	(7)
9.1.1 Insertion Sort	475	(3)
9.1.2 Selection Sort	478	(2)
9.1.3 Bubble Sort	480	(2)
9.2 Decision Trees	482	(4)
9.3 Efficient Sorting Algorithms	486	(20)
9.3.1 Shell Sort	486	(3)
9.3.2 Heap Sort	489	(4)
9.3.3 Quicksort	493	(6)
9.3.4 Mergesort	499	(3)
9.3.5 Radix Sort	502	(4)
9.4 Sorting in the Standard Template Library	506	(4)
9.5 Concluding Remarks	510	(2)
9.6 Case Study: Adding Polynomials	512	(8)
9.7 Exercises	520	(1)
9.8 Programming Assignments	521	(2)
Bibliography	523	(3)
10 HASHING
10.1 Hash Functions	526	(2)
10.1.1 Division	526	(1)
10.1.2 Folding	526	(1)
10.1.3 Mid-Square Function	527	(1)
10.1.4 Extraction	527	(1)
10.1.5 Radix Transformation	528	(1)
10.2 Collision Resolution	528	(9)
10.2.1 Open Addressing	528	(6)
10.2.2 Chaining	534	(2)
10.2.3 Bucket Addressing	536	(1)
10.3 Deletion	537	(1)
10.4 Perfect Hash Functions	538	(6)
10.4.1 Cichelli's Method	539	(3)
10.4.2 The FHCD Algorithm	542	(2)
10.5 Hash Functions for Extendible Files	544	(6)
10.5.1 Extendible Hashing	545	(2)
10.5.2 Linear Hashing	547	(3)
10.6 Case Study: Hashing with Buckets	550	(10)
10.7 Exercises	560	(1)
10.8 Programming Assignments	561	(1)
Bibliography	562	(2)
11 DATA COMPRESSION	564	(1)
11.1 Conditions for Data Compression	564	(2)
11.2 Huffman Coding	566	(14)
11.2.1 Adaptive Huffrnan Coding	575	(5)
11.3 Run-Length Encoding	580	(1)
11.4 Ziv-Lempel Code	581	(3)
11.5 Case Study: Huffman Method with Run-Length Encoding	584	(12)
11.6 Exercises	596	(1)
11.7 Programming Assignments	596	(2)
Bibliography	598	(2)
12 MEMORY MANAGEMENT
12.1 The Sequential-Fit Methods	600	(1)
12.2 The Nonsequential-Fit Methods	601	(9)
12.2.1 Buddy Systems	603	(7)
12.3 Garbage Collection	610	(18)
12.3.1 Mark-and-Sweep	611	(7)
12.3.2 Copying Methods	618	(2)
12.3.3 Incremental Garbage Collection	620	(8)
12.4 Concluding Remarks	628	(1)
12.5 Case Study: An In-Place Garbage Collector	629	(9)
12.6 Exercises	638	(1)
12.7 Programming Assignments	639	(3)
Bibliography	642	(2)
13 STRING MATCHING
13.1 Exact String Matching	644	(45)
13.1.1 Straightforward Algorithms	644	(3)
13.1.2 The Knuth-Morris-Prat Algorithm	647	(8)
13.1.3 The Boyer-Moore Algorithm	655	(10)
13.1.4 Multiple Searches	665	(2)
13.1.5 Bit-Oriented Approach	667	(3)
13.1.6 Matching Sets of Words	670	(7)
13.1.7 Regular Expression Matching	677	(4)
13.1.8 Suffix Tries and Trees	681	(6)
13.1.9 Suffix Arrays	687	(2)
13.2 Approximate String Matching	689	(10)
13.2.1 String Similarity	690	(6)
13.2.2 String Matching with k Errors	696	(3)
13.3 Case Study: Longest Common Substring	699	(9)
13.4 Exercises	708	(2)
13.5 Programming Assignments	710	(1)
Bibliography	711	(2)
APPENDIXES
A Computing Big-O	713	(6)
A.1 Harmonic Series	713	(1)
A.2 Approximation of the Function lg(n!)	713	(2)
A.3 Big-O for Average Case of Quicksort	715	(2)
A.4 Average Path Length in a Random Binary Tree	717	(1)
A.5 The Number of Nodes in an AVL Tree	718	(1)
B Algorithms in the Standard Template Library	719	(9)
B.1 Standard Algorithms	719	(9)
C NP-Completeness	728	(13)
C.1 Cook's Theorem	728	(13)
Name Index	741	(4)
Subject Index	745