Practical Introduction to Data Structures and Algorithm Analysis (C++ Edition)

by Shaffer, Clifford A.

• ISBN13: 9780130284464
• ISBN10: 0130284467
• Edition: 2nd
• Format: Hardcover
• Copyright: 2001-01-01
• Publisher: Prentice Hall
• More Book Details
• Purchase Benefits

Summary

This practical text contains fairly "traditional" coverage of data structures with a clear and complete use of algorithm analysis, and some emphasis on file processing techniques as relevant to modern programmers. It fully integrates OO programming with these topics, as part of the detailed presentation of OO programming itself.Chapter topics include lists, stacks, and queues; binary and general trees; graphs; file processing and external sorting; searching; indexing; and limits to computation.For programmers who need a good reference on data structures.

Table of Contents

Preface	xi
I PRELIMINARIES	1	(84)
Data Structures and Algorithms	3	(18)
A Philosophy of Data Structures	4	(4)
The Need for Data Structures	4	(2)
Costs and Benefits	6	(2)
Abstract Data Types and Data Structures	8	(4)
Problems, Algorithms, and Programs	12	(3)
Further Reading	15	(2)
Exercises	17	(4)
Mathematical Preliminaries	21	(28)
Sets and Relations	21	(4)
Miscellaneous Notation	25	(1)
Logarithms	26	(2)
Recursion	28	(2)
Summations and Recurrences	30	(4)
Mathematical Proof Techniques	34	(7)
Proof by Contradiction	34	(1)
Proof by Mathematical Induction	35	(6)
Estimating	41	(2)
Further Reading	43	(1)
Exercises	43	(6)
Algorithm Analysis	49	(36)
Introduction	49	(6)
Best, Worst, and Average Cases	55	(2)
A Faster Computer, or a Faster Algorithm?	57	(2)
Asymptotic Analysis	59	(6)
Upper Bounds	60	(2)
Lower Bounds	62	(1)
Θ Notation	63	(1)
Simplifying Rules	64	(1)
Calculating the Running Time of a Program	65	(5)
Analyzing Problems	70	(1)
Common Misunderstandings	71	(1)
Multiple Parameters	72	(1)
Space Bounds	73	(3)
Some Practical Considerations	76	(2)
Further Reading	78	(1)
Exercises	79	(4)
Projects	83	(2)
II FUNDAMENTAL DATA STRUCTURES	85	(132)
Lists, Stacks, and Queues	87	(54)
Lists	88	(25)
Array-Based List Implementation	91	(4)
Linked Lists	95	(10)
Comparison of List Implementations	105	(2)
Element Implementations	107	(1)
Doubly Linked Lists	108	(5)
The Dictionary ADT	113	(6)
Stacks	119	(9)
Array-Based Stacks	121	(1)
Linked Stacks	122	(2)
Comparison of Array-Based and Linked Stacks	124	(1)
Implementing Recursion	125	(3)
Queues	128	(5)
Array-Based Queues	129	(4)
Linked Queues	133	(1)
Comparison of Array-Based and Linked Queues	133	(1)
Further Reading	133	(1)
Exercises	133	(5)
Projects	138	(3)
Binary Trees	141	(50)
Definitions and Properties	141	(5)
The Full Binary Tree Theorem	143	(2)
A Binary Tree Node ADT	145	(1)
Binary Tree Traversals	146	(3)
Binary Tree Node Implementations	149	(10)
Pointer-Based Node Implementations	149	(5)
Space Requirements	154	(3)
Array Implementation for Complete Binary Trees	157	(2)
Binary Search Trees	159	(8)
Heaps and Priority Queues	167	(7)
Huffman Coding Trees	174	(11)
Building Huffman Coding Trees	176	(6)
Assigning and Using Huffman Codes	182	(3)
Further Reading	185	(1)
Exercises	186	(3)
Projects	189	(2)
Non-Binary Trees	191	(26)
General Tree Definitions and Terminology	191	(4)
An ADT for General Tree Nodes	192	(1)
General Tree Traversals	193	(2)
The Parent Pointer Implementation	195	(7)
General Tree Implementations	202	(5)
List of Children	202	(1)
The Left-Child/Right-Sibling Implementation	203	(2)
Dynamic Node Implementations	205	(2)
Dynamic ``Left-Child/Right-Sibling'' Implementation	207	(1)
K-ary Trees	207	(1)
Sequential Tree Implementations	208	(3)
Further Reading	211	(1)
Exercises	211	(3)
Projects	214	(3)
III Sorting and Searching	217	(140)
Internal Sorting	219	(40)
Sorting Terminology and Notation	219	(2)
Three Θ(n2) Sorting Algorithms	221	(6)
Insertion Sort	221	(2)
Bubble Sort	223	(1)
Selection Sort	224	(2)
The Cost of Exchange Sorting	226	(1)
Shellsort	227	(2)
Quicksort	229	(6)
Mergesort	235	(3)
Heapsort	238	(3)
Binsort and Radix Sort	241	(6)
An Empirical Comparison of Sorting Algorithms	247	(2)
Lower Bounds for Sorting	249	(4)
Further Reading	253	(1)
Exercises	254	(3)
Projects	257	(2)
File Processing and External Sorting	259	(34)
Primary versus Secondary Storage	259	(3)
Disk Drives	262	(8)
Disk Drive Architecture	263	(5)
Disk Access Costs	268	(2)
Buffers and Buffer Pools	270	(5)
The Programmer's View of Files	275	(1)
External Sorting	276	(3)
Simple Approaches to External Sorting	279	(2)
Replacement Selection	281	(4)
Multiway Merging	285	(3)
Further Reading	288	(1)
Exercises	288	(3)
Projects	291	(2)
Searching	293	(34)
Searching Sorted Arrays	294	(1)
Self-Organizing Lists	295	(6)
Searching in Sets	301	(1)
Hashing	302	(19)
Hash Functions	303	(4)
Open Hashing	307	(1)
Closed Hashing	308	(13)
Further Reading	321	(1)
Exercises	321	(3)
Projects	324	(3)
Indexing	327	(30)
Linear Indexing	329	(2)
ISAM	331	(3)
Tree Indexing	334	(2)
2-3 Trees	336	(7)
B-Trees	343	(9)
B+-Trees	344	(6)
B-Tree Analysis	350	(2)
Further Reading	352	(1)
Exercises	353	(2)
Projects	355	(2)
IV Applications and Advanced Topics	357	(136)
Graphs	359	(34)
Terminology and Representations	360	(4)
Graph Implementations	364	(3)
Graph Traversals	367	(10)
Depth-First Search	370	(1)
Breadth-First Search	371	(4)
Topological Sort	375	(2)
Shortest-Paths Problems	377	(5)
Single-Source Shortest Paths	377	(4)
All-Pairs Shortest Paths	381	(1)
Minimum-Cost Spanning Trees	382	(5)
Prim's Algorithm	383	(3)
Kruskal's Algorithm	386	(1)
Further Reading	387	(1)
Exercises	388	(2)
Projects	390	(3)
Lists and Arrays Revisited	393	(30)
Skip Lists	393	(6)
Multilists	399	(3)
Matrix Representations	402	(4)
Memory Management	406	(12)
Dynamic Storage Allocation	407	(7)
Failure Policies and Garbage Collection	414	(4)
Further Reading	418	(1)
Exercises	419	(1)
Projects	420	(3)
Advanced Tree Structures	423	(28)
Tries	423	(5)
Balanced Trees	428	(6)
The AVL Tree	428	(3)
The Splay Tree	431	(3)
Spatial Data Structures	434	(13)
The K-D Tree	436	(5)
The PR quadtree	441	(4)
Other Spatial Data Structures	445	(2)
Further Reading	447	(1)
Exercises	447	(1)
Projects	448	(3)
Analysis Techniques	451	(18)
Summation Techniques	452	(3)
Recurrence Relations	455	(6)
Estimating Upper and Lower Bounds	455	(1)
Expanding Recurrences	456	(1)
Divide and Conquer Recurrences	457	(2)
Average-Case Analysis of Quicksort	459	(2)
Amortized Analysis	461	(3)
Further Reading	464	(1)
Exercises	464	(4)
Projects	468	(1)
Limits to Computation	469	(24)
Reductions	470	(5)
Hard Problems	475	(7)
NP-Completeness	476	(5)
Getting Around NP-Complete Problems	481	(1)
Impossible Problems	482	(7)
Uncountability	483	(3)
The Halting Problem Is Unsolvable	486	(2)
Determining Program Behavior Is Unsolvable	488	(1)
Further Reading	489	(1)
Exercises	489	(2)
Projects	491	(2)
V APPENDIX	493	(4)
A Utility Functions	495	(2)
Bibliography	497	(6)
Index	503

Excerpts

PrefaceWe study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we computerize more complex tasks.The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with "programming tricks" but rather is based on good organization of information and good algorithms. A programmer who has not mastered the basic principles of clear design will not likely write efficient programs. Conversely, clear programs require clear data organization and clear algorithms. Most computer science curricula recognize that good programming skills begin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and implementation, the next step is to study the effects of data organization and algorithms on program efficiency.Approach:Many techniques for representing data are described in this book. These techniques are presented within the context of the following principles: Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation for the significant effects of the physical medium employed (e.g., data stored on disk versus main memory). Related to costs and benefits is the notion of tradeoffs. For example, it is quite common to reduce time requirements at the expense of an increase in space requirements, or vice versa. Programmers face tradeoff issues regularly in all phases of software design and implementation, so the concept must become deeply ingrained. Programmers should know enough about common practice to avoid reinventing the wheel. Thus, programmers need to learn the commonly used data structures and related algorithms. Data structures follow needs. Programmers must learn to assess application needs first, then find a data structure with matching capabilities. To do this requires competence in principles 1, 2, and 3.Using the Book in Class:Data structures and algorithms textbooks tend to fall into one of two categories: teaching texts or encyclopedias. Books that attempt to do both usually fail at both. This book is intended as a teaching text. I believe it is more important for a practitioner to understand the principles required to select or design the data structure that will best solve some problem than it is to memorize a lot of textbook implementations. Hence, I have designed this as a teaching text that covers most standard data structures, but not all. A few data structures that are not widely adopted are included to illustrate important principles. Some relatively new data structures that should become widely used in the future are included.This book is intended for a single-semester course at the undergraduate level, or for self-study by technical professionals. Readers should have programming experience, typically two semesters or the equivalent of a structured programming language such as Pascal orC,and including at least some exposure toC++. Readers who are already familiar with recursion will have an advantage. Students of data structures will also benefit from having first completed a good course in Discrete Mathematics. Nonetheless, Chapter 2 attempts to give a reasonably complete survey of the prerequisite mathematical topics at the level necessary to understand their use in this book. Readers may wish to refer ba