دانلود کتاب Fundamentals of Data Structures in C

فهرست مطالب :

CONTENTS\n PREFACE\n USING THIS TEXT FOR A COURSE\n c ‘\n • . *»» 01 . I\n ■ ■.\n CHAPTER 1\n BASIC CONCEPTS\n OVERVIEW: SYSTEM LIFE CYCLE\n 1.2.1\n Introduction\n 1.2.2\n Recursive Algorithms\n EXERCISES\n 1.3\n DATA ABSTRACTION\n else return x - y\n EXERCISES\n 1.4\n PERFORMANCE ANALYSIS\n 1.4.1\n Space Complexity\n EXERCISES\n 1.4.2\n Time Complexity\n EXERCISES\n 2\n Summary\n 1.4.3 Asymptotic Notation (O, Q, 0)\n EXERCISES\n 1.4.4\n Practical Complexities\n 1.5\n PERFORMANCE MEASUREMENT\n 1\n J\n */\n Generating Test Data\n */\n EXERCISES\n SELECTED READINGS AND REFERENCES\n CHAPTER 2\n ARRAYS AND STRUCTURES\n THE ARRAY AS AN ABSTRACT DATA TYPE\n */\n 2.2.1\n Structures\n 2.2.2\n Unions\n Internal Implementation of Structures\n Self-Referential Structures\n EXERCISES\n THE POLYNOMIAL ABSTRACT DATA TYPE\n */\n EXERCISES\n THE SPARSE MATRIX ABSTRACT DATA TYPE\n 2.4.1\n Introduction\n 2.4.2 Transposing a Matrix\n /*\n */\n /\n */\n */\n /*\n /*\n */\n */\n */\n 2.4.3\n Matrix Multiplication\n n 0 01 fl 1 11\n n 1 11\n /*\n */\n */\n EXERCISES\n REPRESENTATION OF MULTIDIMENSIONAL ARRAYS\n +\n EXERCISES\n 2.6.1\n Introduction\n 2.6.2\n Pattern Matching\n nr\n */\n */\n EXERCISES\n REFERENCES AND SELECTED READINGS\n 2.8\n ADDITIONAL EXERCISES\n CHAPTER 3\n STACKS AND QUEUES\n THE STACK ABSTRACT DATA TYPE\n (b)\n */\n /*\n EXERCISES\n THE QUEUE ABSTRACT DATA TYPE\n era\n era\n jg\n EXERCISES\n 3.3\n A MAZING PROBLEM\n EXERCISES\n 3.4.1\n Introduction\n 3.4.2 Evaluating Postfix Expressions\n 0 []\n 3.4.3\n Infix To Postfix\n +\n +\n 4-\n +\n EXERCISES\n 9.\n MULTIPLE STACKS AND QUEUES\n EXERCISES\n REFERENCES AND SELECTED READINGS\n 3.7\n ADDITIONAL EXERCISES\n CHAPTER 4\n LISTS\n 4.1\n POINTERS\n Pointers Can Be Dangerous\n 4.1.2 Using Dynamically Allocated Storage\n 4.2\n SINGLY LINKED LISTS\n 11\n EXERCISES\n 1 I\n 4.3\n DYNAMICALLY LINKED STACKS AND QUEUES\n I\n EXERCISES\n Representing Polynomials As Singly Linked Lists\n 4.4.2 Adding Polynomials\n 4.4.3 Erasing Polynomials\n Representing Polynomials As Circularly Linked Lists\n 4.4.5 Summary\n EXERCISES\n 4.5.1\n Operations For Chains\n Operations For Circularly Linked Lists\n EXERCISES\n 4.6\n EQUIVALENCE RELATIONS\n 4.7\n SPARSE MATRICES\n EXERCISES\n 4.8\n DOUBLY LINKED LISTS\n EXERCISES\n ◄-\n REFERENCES AND SELECTED READINGS\n -►\n 4.10\n ADDITIONAL EXERCISES\n CHAPTER 5\n TREES\n 5.1.1\n Terminology\n Leuel\n List Representation\n Left Child-Right Sibling Representation\n Representation As A Degree Two Tree\n 5.2.1\n The Abstract Data Type\n Properties Of Binary Trees\n Leuel\n (a)\n (b)\n Proof:\n 10\n Array Representation\n Linked Representation\n EXERCISES\n (a)\n 5.3\n BINARY TREE TRAVERSALS\n 1\n HA\n ■ilO\n Inorder Traversal\n Preorder Traversal\n /\n printf\n Postorder Traversal\n Iterative Inorder Traversal\n */\n */\n */\n Level Order Traversal\n ADDITIONAL BINARY TREE OPERATIONS\n Testing For Equality Of Binary Trees\n The Satisfiability Problem\n */\n 5.5\n THREADED BINARY TREES\n root\n G}\n Inorder Traversal of a Threaded Binary Tree\n Inserting A Node Into A Threaded Binary Tree\n f = FALSE t = TRUE\n (a)\n . ( 9\n 20\n (90\n EXERCISES\n 5.9\n FORESTS\n Transforming A Forest Into A Binary Tree\n 5.9.2\n Forest Traversals\n EXERCISES\n 5.10\n SET REPRESENTATION\n Union And Find Operations\n n\n 2;; = O(n2)n\n Figure 5.43 : Degenerate tree\n 5.10.2\n Equivalence Classes\n EXERCISES\n COUNTING BINARY TREES\n 5.11.1\n Distinct Binary Trees\n 5.11.2\n Stack Permutations\n 5.11.3\n Matrix Multiplication\n Number Of Distinct Binary Trees\n EXERCISES\n REFERENCES AND SELECTED READINGS\n ADDITIONAL EXERCISES\n mH\n * on\n CHAPTER 6\n GRAPHS\n 6.1.1\n Introduction\n ST\n A\n 6.1.2\n Definitions\n I y\n Adjacency Matrix\n Adjacency Lists\n Adjacency Multilists\n +-\n Weighted Edges\n EXERCISES\n Z\n ELEMENTARY GRAPH OPERATIONS\n 6.2.1\n Depth First Search\n 6.2.2\n Breadth First Search\n Ml\n Ml\n M,\n 6.2.3\n Connected Components\n */\n 6.2.4 Spanning Trees\n 0-0\n Mt\n Mt\n Mv\n Mo\n Mo\n Mt\n Ms\n Ms\n Mt\n M.\n Biconnected Components And Articulation Points\n EXERCISES\n */\n */\n MINIMUM COST SPANNING TREES\n Kruskal’s Algorithm\n (b)\n Prim’s Algorithm\n */\n lx\n \"^X\n lx\n Soilin’s Algorithm\n EXERCISES\n SHORTEST PATHS AND TRANSITIVE CLOSURE\n Single Source All Destinations\n */\n */\n i + +) {\n 6,4.2\n All Pairs Shortest Paths\n ’ ld[71 = cMz]f7]\n 6.4.3\n Transitive Closure\n 0-*0-» ($-(?>©\n EXERCISES\n Activity On Vertex (AOV) Networks\n Ml\n Ma\n Ml\n Vs\n Ml\n 6.5.2 Activity On Edge (AOE) Networks\n Calculation Of Earliest Tinies\n Calculation Of Latest Times\n EXERCISES\n REFERENCES AND SELECTED READINGS\n CHAPTER 7\n SORTING\n 7.1.1\n Introduction\n 7.1.2 Sequential Search\n 7.1.3\n Binary Search\n 7.1.4\n List Verification\n 17\n 46\n 48\n 58\n 90\n (15\n 30\n 56\n fsz\n 95\n EXERCISES\n 7.2\n DEFINITIONS\n 7.3\n INSERTION SORT\n 1\n 2\n 3\n 4\n 5\n 1\n 3\n 3\n 4\n 5\n EXERCISES\n 7.4\n QUICK SORT\n EXERCISES\n 7.5\n OPTIMAL SORTING TIME\n TIT\n 7.6.1\n Merging\n 7.6.2\n Iterative Merge Sort\n 7.6.3\n Recursive Merge Sort\n EXERCISES\n 7.7\n HEAP SORT\n 15\n 61\n 48 19\n 59\n EXERCISES\n 48\n 15\n 7.8\n RADIX SORT\n A < ♦ < V < A\n 48\n 15\n 15\n 48\n 19\n 26\n 19\n 15\n 15\n 19\n tioi\n 26\n 11\n Figure 7.13 (continued): Heap sort example\n 4*\n 4’\n EXERCISES\n 7.9\n LIST AND TABLE SORTS\n ~7\n ~7\n ”7\n 1\n \"7\n ”7\n \"5\n ~7\n ”7\n ^7\n R2 11\n 77\n \"7\n ~3\n ~T\n \"7\n 1\n \"3\n \"7\n ”7\n 15\n 26\n 19\n EXERCISES\n 7.10\n SUMMARY OF INTERNAL SORTING\n T\n \"7\n ”7\n EXERCISES\n WHAT TO TURN IN\n Sorts\n Input Data Patterns\n 7.11.1\n Introduction\n 7.11.2\n Buffer Handling For Parallel Operation\n o co\n 7.11.4\n Run Generation\n 7.11.5 Optimal Merging Of Runs\n EXERCISES\n REFERENCES AND SELECTED READINGS\n ADDITIONAL EXERCISES\n CHAPTER 8\n HASHING\n THE SYMBOL TABLE ABSTRACT DATA TYPE\n 8.2.1\n Hash Tables\n exp float\n floor\n 8.2.2 Hashing Functions\n Division\n Folding\n Digit Analysis\n Linear Open Addressing\n if\n Chaining\n [0] -> acos -> atoi -> atol\n Theoretical Evaluation of Overflow Techniques\n EXERCISES\n 8.3\n DYNAMIC HASHING\n 8.3.1 Dynamic Hashing Using Directories\n 8.3.2 Analysis of Directory Dynamic Hashing\n Simulation\n 8.3.3 Directoryless Dynamic Hashing\n EXERCISES\n References And Selected Readings 429\n CHAPTER 9\n HEAP STRUCTURES\n 9.1.1\n Definition\n 12\n Insertion Into A Min-Max Heap\n 12\n 9.1.3\n Deletion Of Min Element\n EXERCISES\n 9.2.1\n Definition\n 9.2.2\n Insertion Into A Deap\n iO\n 9.2.3\n Deletion Of Min Element\n 30\n EXERCISES\n 93\n LEFTIST TREES\n EXERCISES\n 9.4.1\n Cost Amortization\n Definition Of Binomial Heaps\n Insertion Into A Binomial Heap\n 9.4.4\n Combine\n 9.4.5\n Deletion Of Min Element\n 9.4.6 Analysis\n EXERCISES\n 9.5.1\n Definition\n 9.5.2\n Deletion From An F-heap\n 9.5.3\n Decrease Key\n 9.5.4 Cascading Cut\n 9.5.5 Analysis\n 9.5.6 Application Of F-heaps\n EXERCISES\n REFERENCES AND SELECTED READINGS\n CHAPTER 10\n SEARCH STRUCTURES\n OPTIMAL BINARY SEARCH TREES\n if\n while\n if\n while\n if\n if\n while\n if\n Z Uogzd = O(niog2n)\n do\n do\n while\n if\n while\n if\n do\n while\n EXERCISES\n 10.2\n AVL TREES\n >\n B\n Bu\n Figure 10.12 (continued): Rebalancing rotations\n /*\n */\n 10.3.3\n Insertion Into A 2-3 Tree\n 95\n EXERCISES\n Definition And Properties\n 50\n 60\n Deletion From A 2-3-4 Tree\n Program 10.10: Insertion into a 2-3-4 tree\n 10.5.3 Top Down Insertion\n 10.5.4\n Bottom Up Insertion\n Deletion Fron A Red-Black Tree\n Searching An w-way Search Tree\n Definition And Properties Of A B-tree\n Number Of Key Values In A B-Tree\n Choice Of m\n 10.6.5\n Deletion From A B-tree\n 10.8.1\n Digital Search Tree\n Insertion\n ■moT\n 4X ^^ooT\n EXERCISES\n 10.9.1\n Definition\n 10.9.2 Searching A Trie\n 10.9.3\n Sampling Strategies\n Insertion Into A Trie\n 10.9.5\n Deletion From A Trie\n EXERCISES\n 10.10\n DIFFERENTIAL FILES\n EXERCISES\n REFERENCES AND SELECTED READINGS\n APPENDIX\n ANSI C AND K&R C\n ANSI C Is Bigger Than K&R C\n */\n */\n */\n 10;\n */\n */\n */\n Dangerous Practices\n INDEX