文件名称：Data Structure and Algorithms
文件大小：1.04MB
文件格式：PDF
更新时间：2017-03-13 08:31:30
数据结构
Data Structure and Algorithms,数据结构和算法，纯英文版，介绍了链表，二叉树等数据结构 Contents 1 Introduction 1 1.1 What this book is, and what it isn't . . . . . . . . . . . . . . . . 1 1.2 Assumed knowledge . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2.1 Big Oh notation . . . . . . . . . . . . . . . . . . . . . . . 1 1.2.2 Imperative programming language . . . . . . . . . . . . . 3 1.2.3 Object oriented concepts . . . . . . . . . . . . . . . . . . 4 1.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Tips for working through the examples . . . . . . . . . . . . . . . 6 1.5 Book outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.7 Where can I get the code? . . . . . . . . . . . . . . . . . . . . . . 7 1.8 Final messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 I Data Structures 8 2 Linked Lists 9 2.1 Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.4 Traversing the list . . . . . . . . . . . . . . . . . . . . . . 12 2.1.5 Traversing the list in reverse order . . . . . . . . . . . . . 13 2.2 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.3 Reverse Traversal . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 Binary Search Tree 19 3.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Finding the parent of a given node . . . . . . . . . . . . . . . . . 24 3.5 Attaining a reference to a node . . . . . . . . . . . . . . . . . . . 24 3.6 Finding the smallest and largest values in the binary search tree 25 3.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7.1 Preorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 I 3.7.2 Postorder . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.7.3 Inorder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.7.4 Breadth First . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4 Heap 32 4.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Sets 44 5.1 Unordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.1.1 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2 Ordered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 Queues 48 6.1 A standard queue . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.2 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.3 Double Ended Queue . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7 AVL Tree 54 7.1 Tree Rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 7.2 Tree Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 II Algorithms 62 8 Sorting 63 8.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 8.4 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.5 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 8.6 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 8.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 9 Numeric 72 9.1 Primality Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 9.2 Base conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 9.3 Attaining the greatest common denominator of two numbers . . 73 9.4 Computing the maximum value for a number of a speci¯c base consisting of N digits . . . . . . . . . . . . . . . . . . . . . . . . . 74 9.5 Factorial of a number . . . . . . . . . . . . . . . . . . . . . . . . 74 9.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 II 10 Searching 76 10.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 10.2 Probability Search . . . . . . . . . . . . . . . . . . . . . . . . . . 76 10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 11 Strings 79 11.1 Reversing the order of words in a sentence . . . . . . . . . . . . . 79 11.2 Detecting a palindrome . . . . . . . . . . . . . . . . . . . . . . . 80 11.3 Counting the number of words in a string . . . . . . . . . . . . . 81 11.4 Determining the number of repeated words within a string . . . . 83 11.5 Determining the ¯rst matching character between two strings . . 84 11.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 A Algorithm Walkthrough 86 A.1 Iterative algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 86 A.2 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 88 A.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 B Translation Walkthrough 91 B.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 C Recursive Vs. Iterative Solutions 93 C.1 Activation Records . . . . . . . . . . . . . . . . . . . . . . . . . . 94 C.2 Some problems are recursive in nature . . . . . . . . . . . . . . . 95 C.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 D Testing 97 D.1 What constitutes a unit test? . . . . . . . . . . . . . . . . . . . . 97 D.2 When should I write my tests? . . . . . . . . . . . . . . . . . . . 98 D.3 How seriously should I view my test suite? . . . . . . . . . . . . . 99 D.4 The three A's . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 D.5 The structuring of tests . . . . . . . . . . . . . . . . . . . . . . . 99 D.6 Code Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 D.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 E Symbol De¯nitions 101