Data Structures and Algorithms in C++

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 \316\251 AND \316\230 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 Jarn\303\255k-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