INDICE: Chapter 1: Abstract Data Types 1 1.1 Introduction... 1 1.1.1 Abstractions.. 2 1.1.2 Abstract Data Types.. 4 1.1.3 Data Structures.. 5 1.2 The Date ADT.. 6 1.2.1 Preconditions and Postconditions... 8 1.2.2 Using the ADT.. 8 1.2.3 Implementing the ADT. 8 1.3 The Bag ADT.. 14 1.3.1 Using the ADT.. 15 1.3.2 Selecting a Data Structure... 16 1.3.3 The Class Definition.. 18 1.4 Iterators.. 19 1.5 The Set ADT.. 22 1.5.1 Using the ADT.. 24 1.5.2 Implementing theADT. 25 1.6 The Map ADT.. 28 1.6.1 Defining the ADT... 29 1.6.2 Implementing the Map ADT.. 30 1.6.3 Alternate Implementation.. 33 1.7 Application: Histograms. 35 1.7.1 Building a Histogram.. 37 1.7.2 Implementing the Histogram ADT.. 37 Programming Problems... 40 Chapter 2: Arrays and Vectors 43 2.1 The Array Structure.. 43 2.1.1 Simulating an Array.. 44 2.1.2 The Array ADT. 45 2.1.3 Implementing the ADT. 46 2.2 The Python List (Vector)... 47 2.3 Multi-DimensionalArrays... 54 2.3.1 The MultiArray ADT.. 54 2.3.2 Data Organization... 55 2.3.3 Variable Length Arguments.. 59 2.3.4 MultiArray Implementation.. 60 2.4 The Matrix ADT. 64 2.4.1 Matrix Operations... 65 2.4.2 Implementing the ADT. 67 2.5 Application: The Game of Life. 69 2.5.1 Rules of the Game... 70 2.5.2 Designing a Solution.. 72 2.5.3 ADT Implementation.. 74 Exercises... 77 Programming Problems... 78 Chapter 3: Algorithm Analysis 81 3.1 Complexity Analysis.. 82 3.1.1 Big-O Notation.. 83 3.1.2 Classes of Algorithms.. 87 3.1.3 Empirical Analysis... 88 3.2 Evaluating ADT Implementations.. 88 3.2.1 Evaluating the PythonList.. 89 3.2.2 Evaluating the Set ADT. 91 3.3 Searching. 92 3.3.1 Linear Search.. 92 3.3.2 Binary Search.. 95 3.4 Working with Ordered Lists.. 99 3.4.1 Building An Ordered List... 99 3.4.2 Merging Ordered Lists.. 100 3.5 The Set ADTRevisited. 106 3.6 Application: The Sparse Matrix. 112 3.6.1 Implementation..112 3.6.2 Analysis.. 116 Exercises... 118 Programming Problems... 120 Chapter4: The Linked List 123 4.1 A Linked Structure... 124 4.2 The Singly-Linked List.. 124 4.2.1 Basic Operations. 124 4.2.2 Evaluating the Linked List.. 124 4.3 The Bag ADT Revisited. 124 4.3.1 Implementation Details. 124 4.3.2 Linked List Iterator.. 124 4.4 Using a Tail Pointer.. 124 4.5 The Ordered Linked List. 124 4.6 The Sparse Matrix Revisited.. 124 4.6.1 The New Implementation... 124 4.6.2 Comparing Implementations.. 124 4.7 Application: Polynomials...
- ISBN: 978-0-470-61829-5
- Editorial: John Wiley & Sons
- Encuadernacion: Rústica
- Páginas: 540
- Fecha Publicación: 30/12/2010
- Nº Volúmenes: 1
- Idioma: Inglés