Note: Supplemental materials are not guaranteed with Rental or Used book purchases.
Purchase Benefits
What is included with this book?
Abstract Data Types 1 | |
Introduction | p. 1 |
Abstractions | p. 2 |
Abstract Data Types | p. 4 |
Data Structures | p. 5 |
The Date ADT | p. 6 |
Preconditions and Postconditions | p. 8 |
Using the ADT | p. 8 |
Implementing the ADT | p. 8 |
The Bag ADT | p. 14 |
Using the ADT | p. 15 |
Selecting a Data Structure | p. 16 |
The Class Definition | p. 18 |
Iterators | p. 19 |
The Set ADT | p. 22 |
Using the ADT | p. 24 |
Implementing the ADT | p. 25 |
The Map ADT | p. 28 |
Defining the ADT | p. 29 |
Implementing the Map ADT | p. 30 |
Alternate Implementation | p. 33 |
Application: Histograms | p. 35 |
Building a Histogram | p. 37 |
Implementing the Histogram ADT | p. 37 |
Programming Problems | p. 40 |
Arrays and Vectors 43 | |
The Array Structure | p. 43 |
Simulating an Array | p. 44 |
The Array ADT | p. 45 |
Implementing the ADT | p. 46 |
The Python List (Vector) | p. 47 |
MultiâÇôDimensional Arrays | p. 54 |
The MultiArray ADT | p. 54 |
Data Organization | p. 55 |
Variable Length Arguments | p. 59 |
MultiArray Implementation | p. 60 |
The Matrix ADT | p. 64 |
Matrix Operations | p. 65 |
Implementing the ADT | p. 67 |
Application: The Game of Life | p. 69 |
Rules of the Game | p. 70 |
Designing a Solution | p. 72 |
ADT Implementation | p. 74 |
Exercises | p. 77 |
Programming Problems | p. 78 |
Algorithm Analysis 81 | |
Complexity Analysis | p. 82 |
BigâÇôO Notation | p. 83 |
Classes of Algorithms | p. 87 |
Empirical Analysis | p. 88 |
Evaluating ADT Implementations | p. 88 |
Evaluating the Python List | p. 89 |
Evaluating the Set ADT | p. 91 |
Searching | p. 92 |
Linear Search | p. 92 |
Binary Search | p. 95 |
Working with Ordered Lists | p. 99 |
Building An Ordered List | p. 99 |
Merging Ordered Lists | p. 100 |
The Set ADT Revisited | p. 106 |
Application: The Sparse Matrix | p. 112 |
Implementation | p. 112 |
Analysis | p. 116 |
Exercises | p. 118 |
Programming Problems | p. 120 |
The Linked List 123 | |
A Linked Structure | p. 124 |
The SinglyâÇôLinked List | p. 124 |
Basic Operations | p. 124 |
Evaluating the Linked List | p. 124 |
The Bag ADT Revisited | p. 124 |
Implementation Details | p. 124 |
Linked List Iterator | p. 124 |
Using a Tail Pointer | p. 124 |
The Ordered Linked List | p. 124 |
The Sparse Matrix Revisited | p. 124 |
The New Implementation | p. 124 |
Comparing Implementations | p. 124 |
Application: Polynomials | p. 124 |
Polynomial Operations | p. 124 |
The Polynomial ADT | p. 124 |
ADT Implementation | p. 124 |
Exercises | p. 124 |
Programming Problems | p. 124 |
Advanced Linked Lists 125 | |
DoublyâÇôLinked List | p. 126 |
Organization | p. 126 |
List Operations | p. 126 |
Circular Linked List | p. 126 |
Organization | p. 126 |
List Operations | p. 126 |
MultiâÇôLinked Lists | p. 126 |
Multiple Chains | p. 126 |
The Sparse Matrix | p. 126 |
Complex Iterators | p. 126 |
Application: Text Editor | p. 126 |
Typical Editor Operations | p. 126 |
The Edit Buffer ADT | p. 126 |
Implementing the ADT | p. 126 |
Exercises | p. 126 |
Programming Problems | p. 126 |
Stacks 127 | |
The Stack ADT | p. 128 |
Implementing the Stack | p. 128 |
Vector Based | p. 128 |
Linked List Version | p. 128 |
Stack Applications | p. 128 |
Balanced Delimiters | p. 128 |
Evaluating Postfix Expressions | p. 128 |
Application: Solving a Maze | p. 128 |
Backtracking | p. 128 |
Designing a Solution | p. 128 |
The Maze ADT | p. 128 |
ADT Implementation | p. 128 |
Exercises | p. 128 |
Programming Problems | p. 128 |
Queues 129 | |
The Queue ADT | p. 129 |
Implementing the Queue | p. 129 |
Vector Based | p. 129 |
Circular Array | p. 129 |
Linked List Version | p. 129 |
The Priority Queue | p. 129 |
Application: Computer Simulations | p. 129 |
Airline Ticket Counter | p. 129 |
Class Specifications | p. 129 |
Exercises | p. 129 |
Programming Problems | p. 129 |
Hash Tables 131 | |
Introduction | p. 131 |
Hash Functions | p. 131 |
Open Addressing | p. 131 |
Linear Probing | p. 131 |
Collision Resolution | p. 131 |
Bucket Hashing | p. 131 |
Hashing Efficiency | p. 131 |
The Map ADT Revisited | p. 131 |
Application: The Color Histogram | p. 131 |
Exercises | p. 131 |
Programming Problems | p. 131 |
Recursion 133 | |
Recursive Functions | p. 133 |
Properties of Recursion | p. 133 |
Classic Example: The Factorial Function | p. 133 |
Greatest Common Divisor | p. 133 |
Recursion and Stacks | p. 133 |
The Towers of Hanoi | p. 133 |
Backtracking Revisited | p. 133 |
The EightâÇôQueens Problem | p. 133 |
Solving the FourâÇôQueens | p. 133 |
Recursive Solution | p. 133 |
Application: Sudoku Puzzles | p. 133 |
Exercises | p. 133 |
Programming Problems | p. 133 |
Binary Trees and Heaps 135 | |
Tree Structure | p. 135 |
The Binary Tree | p. 135 |
Traversals | p. 135 |
Arithmetic Expresssions | p. 135 |
Tree Threading | p. 135 |
Heaps | p. 135 |
Insertions | p. 135 |
Removals | p. 135 |
Evaluating the Heap | p. 135 |
The Priority Queue Revisited | p. 135 |
Application: Morse Code | p. 135 |
Exercises | p. 135 |
Programming Problems | p. 135 |
Advanced Search Trees 137 | |
The Binary Search Tree | p. 138 |
Searching | p. 138 |
Insertions | p. 138 |
Deletions | p. 138 |
Evaluating the BST | p. 138 |
AVL Trees | p. 138 |
Insertions | p. 138 |
Deletions | p. 138 |
Evaluating the AVL Tree | p. 138 |
2âÇô3 Trees | p. 138 |
Splay Trees | p. 138 |
Application: Improved Map ADT | p. 138 |
Exercises | p. 138 |
Programming Problems | p. 138 |
Sorting Algorithms 139 | |
The Simple Algorithms | p. 140 |
Bubble Sort | p. 140 |
Selection Sort | p. 140 |
Insertion Sort | p. 140 |
Radix Sort | p. 140 |
Basic Algorithm | p. 140 |
Bucket Sorting | p. 140 |
Divide and Conquer | p. 140 |
Merge Sort | p. 140 |
Quick Sort | p. 140 |
Heap Sort | p. 140 |
Application: Empirical Analysis | p. 140 |
Exercises | p. 140 |
Programming Problems | p. 140 |
Python Review | p. 141 |
Basic Concepts | p. 141 |
Functions | p. 141 |
Sequence Types | p. 141 |
Classes | p. 141 |
Copying Objects | p. 141 |
Exceptions | p. 141 |
ObjectâÇôOriented Programming 143 | |
Introduction | p. 143 |
Encapsulation | p. 143 |
Inheritance | p. 143 |
Polymorphism | p. 143 |
Table of Contents provided by Publisher. All Rights Reserved. |