文件名称:
Data Structure and Algorithms
开发工具:
文件大小: 1mb
下载次数: 0
上传时间: 2014-02-21
详细说明： 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 workin g 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 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
