Data Structures and Algorithms in C++

Adam Drozdek0534375979, 9780534375973

Building on widespread use of the C++ programming language in industry and education, this book provides a broad-based and case-driven study of data structures — and the algorithms associated with them — using C++ as the language of implementation. This book places special emphasis on the connection between data structures and their algorithms, including an analysis of the algorithms complexity. It presents data structures in the context of object-oriented program design, stressing the principle of information hiding in its treatment of encapsulation and decomposition. The book also closely examines data structure implementation and its implications on the selection of programming languages.

---

Table of contents :
Cover……Page front.djvu
Data Structures an Algorithms in C++……Page 02_0001.djvu
Contents……Page 05_0001.djvu
Preface……Page out010_0001.djvu
1.1 ABSTRACT DATA TYPES……Page out015_0001.djvu
1.2 ENCAPSULATION……Page out016_0001.djvu
1.3 INHERITANCE……Page out020_0001.djvu
1.4 POINTERS……Page out023_0001.djvu
1.4.1 Pointers and Arrays……Page out026_0001.djvu
1.4.2 Pointers and Copy Constructors……Page out028_0001.djvu
1.4.3 Pointers and Destructors……Page out030_0001.djvu
1.4.4 Pointers and Reference Variables……Page out031_0001.djvu
1.4.5 Pointers to Functions……Page out033_0001.djvu
1.5 POLYMORPHISM……Page out034_0001.djvu
1.6 C++ AND OBJECT-ORENTED PROGRAMMING……Page out036_0001.djvu
1.7 THE STANDARD TEMPLATE LIBRARY……Page out037_0001.djvu
1.7.1 Containers……Page 40
1.7.2 Iterators……Page out038_0001.djvu
1.7.3 Algorithms……Page out039_0001.djvu
1.7.4 Function Objects……Page 42
1.8 VECTORS IN THE STANDARD TEMPLATE LIBRARY……Page out041_0001.djvu
1.9 DATA STRUCTURES AND OBJECT-ORIENTED PROGRAMMING……Page out049_0001.djvu
1.10 CASE STUDY: RANDOM ACCESS FILE……Page 52
1.11 EXERCISES……Page out062_0001.djvu
1.12 PROGRAMMING ASSIGNMENTS……Page out064_0001.djvu
2 Complexity Analysis……Page out067_0001.djvu
2.1 COMPUTATIONAL AND ASYMPTOTIC COMPLEXITY……Page 70
2.2 BIG-O NOTATION……Page out068_0001.djvu
2.3 PROPERTIES OF BIG-O NOTATION……Page out071_0001.djvu
2.4 316251 AND 316230 NOTATIONS……Page out072_0001.djvu
2.5 POSSIBLE PROBLEMS……Page out073_0001.djvu
2.6 EXAMPLES OF COMPLEXITIES……Page out074_0001.djvu
2.7 FINDING ASYMPTOTIC COMPLEXITY: EXAMPLES……Page out075_0001.djvu
2.8 THE BES, AVERAGE, AND WORST CASE……Page out077_0001.djvu
2.9 AMORTIZED COMPLEXITY……Page out080_0001.djvu
2.10 EXERCISES……Page out085_0001.djvu
3 Linked Lists……Page out089_0001.djvu
3.1 SINGLY LINKED LISTS……Page 92
3.1.1 Insertion……Page out095_0001.djvu
3.1.2 Deletion……Page out098_0001.djvu
3.1.3 Search……Page out104_0001.djvu
3.2 DOUBLY LINKED LISTS……Page 107
3.3 CIRCULAR LISTS……Page out109_0001.djvu
3.5 SELF-ORGANIZING LISTS……Page out115_0001.djvu
3.6 SPARSE TABLES……Page out119_0001.djvu
3.7 LISTS IN THE STANDARD TEMPLATE LIBRARY……Page out123_0001.djvu
3.8 DEQUES IN THE STANDARD TEMPLATE LIBRARY……Page out127_0001.djvu
3.9 CONCLUDING REMARKS……Page out132_0001.djvu
3.10 CASE STUDY: A LIBRARY……Page out133_0001.djvu
3.11 EXERCISES……Page out136_0001.djvu
3.12 PROGRAMMING ASSIGNMENTS……Page out146_0001.djvu
4 Stacks and Queues……Page out150_0001.djvu
4.1 STACKS……Page out151_0001.djvu
4.2 QUEUES……Page out158_0001.djvu
4.3 PRIORITY QUEUES……Page out167_0001.djvu
4.4 STACK IN THE STANDARD TEMPLATE LIBRARY……Page out168_0001.djvu
4.5 QUEUES IN THE STANDARD TEMPLATE LIBRARY……Page out169_0001.djvu
4.6 PRIORITY QUEUES IN THE STANDARD TEMPLATE LIBRARY……Page 172
4.7 CASE STUDY: EXITING A MAZE……Page out173_0001.djvu
4.8 EXERCISES……Page out179_0001.djvu
4.9 PROGRAMMING ASSIGNMENTS……Page out182_0001.djvu
5.1 RECURSIVE DEFINITIONS……Page out184_0001.djvu
5.2 FUNCTION CALLS AND RECURSION IMPLEMENTATOIN……Page out187_0001.djvu
5.3 ANATOMY OF A RECURSIVE CALL……Page out189_0001.djvu
5.4 TAIL RECURSION……Page out192_0001.djvu
5.5 NONTAIL RECURSION……Page out194_0001.djvu
5.6 INDIRECT RECURSION……Page out199_0001.djvu
5.7 NESTED RECURSION……Page out201_0001.djvu
5.8 EXCESSIVE RECURSIVE……Page out202_0001.djvu
5.9 BACKTRACKING……Page out205_0001.djvu
5.10 CONCLUDING REMARKS……Page out213_0001.djvu
5.11 CASE STUDY: A RECURSIVE DESCENT INTERPRETER……Page out214_0001.djvu
5.12 EXERCISES……Page out222_0001.djvu
5.13 PROGRAMMING ASSIGNMENTS……Page out226_0001.djvu
6.1 TREES, BINARY TREES, AND BINARY SEARCH TREES……Page out229_0001.djvu
6.2 IMPLEMENTING BINARY TREES……Page out234_0001.djvu
6.3 SEARCHING A BINARY SEARCH TREE……Page out237_0001.djvu
6.4 TREE TRAVERSAL……Page out239_0001.djvu
6.4.1 Breadth-First Traversal……Page out240_0001.djvu
6.4.2 Depfth-First Traversal……Page 224
6.4.3 Stackless Depth-First Traversal……Page out247_0001.djvu
6.5 INSERTION……Page out255_0001.djvu
6.6 DELETION……Page out258_0001.djvu
6.6.1 Deletion by Mergin……Page out259_0001.djvu
6.6.3 Deletion by Copying……Page out262_0001.djvu
6.7 BALANCING A TREE……Page out265_0001.djvu
6.7.1 The DSW Algorithm……Page out268_0001.djvu
6.7.2 AVL Trees……Page out271_0001.djvu
6.8 SELF-ADJUSTING TREES……Page out277_0001.djvu
6.8.1 Self-Restructuring Trees……Page 281
6.8.2 Slpaying……Page out278_0001.djvu
6.9 HEAPS……Page out284_0001.djvu
6.9.1 Heaps as Priority Queues……Page out285_0001.djvu
6.9.2 Organizing Arrays as Heaps……Page out288_0001.djvu
6.10 POLISH NOTATION AND EXPRESSION TREES……Page out292_0001.djvu
6.10.1 Operations on Expression Trees……Page out294_0001.djvu
6.11 CASE STUDY: COMPUTING WORD FREQUENCIES……Page out297_0001.djvu
6.12 EXERCISES……Page out304_0001.djvu
6.13 PROGRAMING ASSIGNMENTS……Page out308_0001.djvu
7 Multiway Trees……Page out315_0001.djvu
7.1 THE FAMILY OF B-TREES……Page out316_0001.djvu
7.1.1 B-Trees……Page out317_0001.djvu
7.1.2 B*-Trees……Page out327_0001.djvu
7.1.3 B+-Trees……Page out329_0001.djvu
7.1.4 Prefix B+-Trees……Page out332_0001.djvu
7.1.5 Bit-Trees……Page out333_0001.djvu
7.1.6 R-Trees……Page out336_0001.djvu
7.1.7 2-4 Trees……Page out337_0001.djvu
7.1.8 Sets and Multisets in the Standard Template Library……Page out345_0001.djvu
7.1.9 Maps and Multimaps in the Standard Template Library……Page out352_0001.djvu
7.2 TRIES……Page out358_0001.djvu
7.3 CONCLUDING REMARKS……Page out366_0001.djvu
7.4 CASE STUDY: SPELL CHECKER……Page out367_0001.djvu
7.5 EXERCISES……Page 381
7.6 PROGRAMMIN ASSIGNMENTS……Page 383
8 Graphs……Page out384_0001.djvu
8.2 GRAPH TRAVERSALS……Page out386_0001.djvu
8.3 SHORTEST PATHS……Page out391_0001.djvu
8.3.1 All-to-All Shortest Path Problem……Page out398_0001.djvu
8.4.1 Union-Find Problem……Page out401_0001.djvu
8.5 SPANNING TREES……Page out404_0001.djvu
8.5.1 Boruvka’s Algorithm……Page out405_0001.djvu
8.5.3 Jarn303255k-Prim’s Algorithm……Page out406_0001.djvu
8.6 CONNECTIVITY……Page out409_0001.djvu
8.6.1 Connectivity in Undirected Graphs……Page out410_0001.djvu
8.6.2 Connectivity in Directed Graphs……Page out413_0001.djvu
8.7 TOPOLOGICAL SORT……Page out415_0001.djvu
8.8.1 Maximum Flows……Page out417_0001.djvu
8.8.2 Maximum Flows of Minimum Cost……Page out427_0001.djvu
8.9 MATCHING……Page out430_0001.djvu
8.9.1 Assignment Problem……Page out429_0001.djvu
8.9.2 Matching in Nonbipartite Graphs……Page out439_0001.djvu
8.10.1 Eulerian Graphs……Page out441_0001.djvu
8.10.2 Hamiltonian Graphs……Page out442_0001.djvu
8.11 CASE STUDY: DISTINCT REPRESENTATIVES……Page out445_0001.djvu
8.12 EXERCISES……Page out457_0001.djvu
8.13 PROGRAMMING ASSIGNMENTS……Page out461_0001.djvu
9 Sorting……Page out465_0001.djvu
9.1.1 Insertion Sort……Page out466_0001.djvu
9.1.2 Selection Sort……Page out469_0001.djvu
9.1.3 Bubble Sort……Page out471_0001.djvu
9.2 DECISION TREES……Page out473_0001.djvu
9.3.1 Shell Sort……Page out476_0001.djvu
9.3.2 Heap Sort……Page out481_0001.djvu
9.3.3 Quicksort……Page out484_0001.djvu
9.3.4 Mergesort……Page out491_0001.djvu
9.3.5 Radix Sort……Page out493_0001.djvu
9.4 SORTING IN THE STANDARD TEMPLATE LIBRARY……Page out501_0001.djvu
9.5 CONCLUDING REMARKS……Page out502_0001.djvu
9.6 CASE STUDY: ADDING POLYNOMIALS……Page out504_0001.djvu
9.7 EXERCISES……Page out511_0001.djvu
9.8 PROGRAMMING ASSIGNMENTS……Page out513_0001.djvu
10 Hashing……Page out517_0001.djvu
10.1.3 Mid-Square Function……Page out518_0001.djvu
10.1.2 Folding……Page 521
10.1.4 Extraction……Page 522
10.1.5 Radix Transformation……Page out520_0001.djvu
10.2 COLLISOIN RESOLUTION……Page 523
10.2.1 Open Adressing……Page out521_0001.djvu
10.2.2 Chaining……Page out526_0001.djvu
10.2.3 Bucket Addressing……Page out528_0001.djvu
10.3 DELETION……Page out530_0001.djvu
10.4 PERFECT HASH FUNCTIONS……Page out531_0001.djvu
10.4.1 Cichelli’s Method……Page out532_0001.djvu
10.4.2 The FHCD Algorithm……Page out534_0001.djvu
10.5.1 Extendible Hashing……Page out537_0001.djvu
10.5.2 Linear Hashing……Page out540_0001.djvu
10.6 CASE STUDY: HASHING WITH BUCKETS……Page out543_0001.djvu
10.7 EXERCISES……Page out552_0001.djvu
10.8 PROGRAMMING ASSIGNMENTS……Page out553_0001.djvu
11.1 CONDITIONS FOR DATA COMPRESSION……Page out556_0001.djvu
11.2 HUFFMAN CODING……Page out558_0001.djvu
11.2.1 Adaptive Huffman Coding……Page out568_0001.djvu
11.3 SHANNON-FANO CODE……Page out571_0001.djvu
11.4 RUN-LENGHT ENCODING……Page out573_0001.djvu
11.5 ZIV-LEMPEL CODE……Page out574_0001.djvu
11.6 CASE STUDY: HUFFMAN METHOD WITH RUN-LENGTH ENCODING……Page out577_0001.djvu
11.7 EXERCISES……Page out589_0001.djvu
11.8 PROGRAMMING ASSIGNMENTS……Page out590_0001.djvu
12 Memory Management……Page out593_0001.djvu
12.1 THE SEQUENTIAL-FIT METHODS……Page out594_0001.djvu
12.2 THE NONSEQUENTIAL-FIT METHODS……Page out596_0001.djvu
12.3.2 Copying Methods……Page out612_0001.djvu
12.2.1 Buddy Systems……Page out597_0001.djvu
12.3 GARBAGE COLLECTION……Page out604_0001.djvu
12.3.1 Mark-and-Sweep……Page out605_0001.djvu
12.3.2 Copying Methods……Page 617
12.3.3 Incremental Garbage Collection……Page out614_0001.djvu
12.4 CONCLUDING REMARKS……Page out622_0001.djvu
12.5 CASE STUDY: AN IN-PLACE GARBAGE COLLECTOR……Page out623_0001.djvu
12.6 EXERCISES……Page out631_0001.djvu
12.7 PROGRAMMING ASSIGNEMTS……Page out633_0001.djvu
A.2 APPROXIMATION OF THE FUNCTION LG(N!)……Page out638_0001.djvu
A.3 BIG-O FOR AVERAGE CASE OF QUICKSORT……Page out640_0001.djvu
A.4 AVERAGE PATH LENTGH IN A RANDOM BINARY TREE……Page out642_0001.djvu
B.1 STANDARD ALGORITHMS……Page out643_0001.djvu
Name Index……Page out652_0001.djvu
Subject Index……Page out655_0001.djvu
BACK COVER……Page back.djvu