Data Structures and Algorithms with Object-Oriented Design Patterns in C++

by Preiss, Bruno R.

• ISBN13: 9780471241348
• ISBN10: 0471241342
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-09-16
• Publisher: Wiley
• More Book Details
• Purchase Benefits

Summary

Students will learn data structures and algorithms from a modern, object-oriented perspective with this new text. It uses a single class hierarchy as a framework to present all of the data structures. This framework clearly shows the relationships between data structures and illustrates how polymorphism and inheritance can be used effectively.

Author Biography

About the Author Bruno R. Preiss is an Associate Professor in the Department of Electrical and Computer Engineering at the University of Waterloo, Canada. He is a member of the Parallel and Distributed Systems Group, the Computer Communications Networks Group, and the VLSI Research Group. Professor Preiss received an M.A.Sc. and Ph.D. in Electrical Engineering from the University of Toronto, Canada.

Table of Contents

CHAPTER 1 Introduction	1	(5)
1.1 What This Book Is About	1	(1)
1.2 Object-Oriented Design	1	(1)
1.3 Object Hierarchies and Design Patterns	2	(1)
1.4 The Features of C++ You Need to Know	3	(1)
1.5 How This Book Is Organized	4	(2)
CHAPTER 2 Algorithm Analysis	6	(28)
2.1 A Detailed Model of the Computer	7	(15)
2.2 A Simplified Model of the Computer	22	(9)
Exercises	31	(2)
Programming Projects	33	(1)
CHAPTER 3 Asymptotic Notation	34	(32)
3.1 An Asymptotic Upper Bound--Big Oh	34	(11)
3.2 An Asymptotic Lower Bound--Omega	45	(3)
3.3 More Notation--Theta and Little Oh	48	(1)
3.4 Asymptotic Analysis of Algorithms	49	(13)
Exercises	62	(2)
Programming Projects	64	(2)
CHAPTER 4 Foundational Data Structures	66	(29)
4.1 Dynamic Arrays	66	(7)
4.2 Singly-Linked Lists	73	(12)
4.3 Multidimensional Arrays	85	(8)
Exercises	93	(1)
Programming Projects	94	(1)
CHAPTER 5 Data Types and Abstraction	95	(31)
5.1 Abstract Data Types	95	(1)
5.2 Design Patterns	96	(26)
Exercises	122	(2)
Programming Projects	124	(2)
CHAPTER 6 Stacks, Queues, and Deques	126	(38)
6.1 Stacks	127	(15)
6.2 Queues	142	(10)
6.3 Deques	152	(8)
Exercises	160	(1)
Programming Projects	161	(3)
CHAPTER 7 Ordered Lists and Sorted Lists	164	(37)
7.1 Ordered Lists	164	(22)
7.2 Sorted Lists	186	(12)
Exercises	198	(1)
Programming Projects	199	(2)
CHAPTER 8 Hashing, Hash Tables, and Scatter Tables	201	(52)
8.1 Hashing--The Basic Idea	201	(3)
8.2 Hashing Methods	204	(4)
8.3 Hash Function Implementations	208	(10)
8.4 Hash Tables	218	(7)
8.5 Scatter Tables	225	(9)
8.6 Scatter Table using Open Addressing	234	(13)
8.7 Applications	247	(2)
Exercises	249	(2)
Programming Projects	251	(2)
CHAPTER 9 Trees	253	(45)
9.1 Basics	254	(3)
9.2 N-ary Trees	257	(4)
9.3 Binary Trees	261	(1)
9.4 Tree Traversals	262	(3)
9.5 Expression Trees	265	(2)
9.6 Implementing Trees	267	(28)
Exercises	295	(2)
Programming Projects	297	(1)
CHAPTER 10 Search Trees	298	(52)
10.1 Basics	298	(2)
10.2 Searching a Search Tree	300	(2)
10.3 Average Case Analysis	302	(6)
10.4 Implementing Search Trees	308	(7)
10.5 AVL Search Trees	315	(12)
10.6 M-Way Search Treees	327	(8)
10.7 B-Trees	335	(11)
10.8 Applications	346	(1)
Exercises	346	(3)
Programming Projects	349	(1)
CHAPTER 11 Heaps and Priority Queues	350	(42)
11.1 Basics	351	(2)
11.2 Binary Heaps	353	(9)
11.3 Leftist Heaps	362	(8)
11.4 Binomial Queues	370	(15)
11.5 Applications	385	(4)
Exercises	389	(1)
Programming Projects	390	(2)
CHAPTER 12 Sets, Multisets, and Partitions	392	(34)
12.1 Basics	393	(2)
12.2 Array and Bit-Vector Sets	395	(6)
12.3 Multisets	401	(7)
12.4 Partitions	408	(12)
12.5 Applications	420	(3)
Exercises	423	(1)
Programming Projects	424	(2)
CHAPTER 13 Dynamic Storage Allocation: The Other Kind of Heap	426	(37)
13.1 Basics	426	(6)
13.2 Singly-Linked Free Storage	432	(8)
13.3 Doubly-Linked Free Storage	440	(8)
13.4 Buddy System for Storage Management	448	(9)
13.5 Applications	457	(3)
Exercises	460	(1)
Programming Projects	461	(2)
CHAPTER 14 Algorithmic Patterns and Problem Solvers	463	(46)
14.1 Brute-Force and Greedy Algorithms	463	(4)
14.2 Backtracking Algorithms	467	(9)
14.3 Top-Down Algorithms: Divide-and-Conquer	476	(10)
14.4 Bottom-Up Algorithms: Dynamic Programming	486	(7)
14.5 Randomized Algorithms	493	(11)
Exercises	504	(3)
Programming Projects	507	(2)
CHAPTER 15 Sorting Algorithms and Sorters	509	(49)
15.1 Basics	509	(1)
15.2 Sorting and Sorters	510	(3)
15.3 Insertion Sorting	513	(5)
15.4 Exchange Sorting	518	(11)
15.5 Selection Sorting	529	(10)
15.6 Merge Sorting	539	(5)
15.7 A Lower Bound on Sorting	544	(2)
15.8 Distribution Sorting	546	(6)
15.9 Performance Data	552	(3)
Exercises	555	(1)
Programming Projects	556	(2)
CHAPTER 16 Graphs and Graph Algorithms	558	(61)
16.1 Basics	559	(8)
16.2 Implementing Graphs	567	(10)
16.3 Graph Traversals	577	(13)
16.4 Shortest-Path Algorithms	590	(10)
16.5 Minimum-Cost Spanning Trees	600	(9)
16.6 Application: Critical Path Analysis	609	(6)
Exercises	615	(3)
Programming Projects	618	(1)
APPENDIX A C++ and Object-Oriented Programming	619	(26)
A.1 Variables, Pointers, and References	619	(3)
A.2 Parameter Passing	622	(3)
A.3 Objects and Classes	625	(6)
A.4 Inheritance and Polymorphism	631	(10)
A.5 Templates	641	(1)
A.6 Exceptions	642	(3)
APPENDIX B Class Hierarchy Diagrams	645	(2)
APPENDIX C Character Codes	647	(1)
Bibliography	648	(3)
Index	651