Data Structures and the Java Collections Framework / Edition 2
by William CollinsISBN-10: 0073022659
ISBN-13: 9780073022659
Pub. Date: 04/16/2004
Publisher: McGraw-Hill Osborne
Data Structures and the Java Collections Framework, 2/e by William Collins teaches the fundamentals of data structures using java. This student-friendly book focuses on teaching students how to apply the concepts presented. To that end many applications and examples are included throughout the book. Collins also provides programming projects at the end of each
Overview
Data Structures and the Java Collections Framework, 2/e by William Collins teaches the fundamentals of data structures using java. This student-friendly book focuses on teaching students how to apply the concepts presented. To that end many applications and examples are included throughout the book. Collins also provides programming projects at the end of each chapter, which get students hands on with code.
In the second edition, Collins has increased his coverage on teaching students to build data structures from scratch. He also continues to use the Java Collections Framework where appropriate. His goal is give students an excellent background in creating data structures themselves, as well as make them comfortable using the standard library.
On-line Labs accompany this book and make it easy to have students start practice what they are learning. These labs can be used as open-labs, closed labs, or homework assignments and are designed to give students hands-on experience in programming. .
Product Details
- ISBN-13:
- 9780073022659
- Publisher:
- McGraw-Hill Osborne
- Publication date:
- 04/16/2004
- Edition description:
- REV
- Pages:
- 761
- Product dimensions:
- 7.60(w) x 9.00(h) x 1.30(d)
Table of Contents
| Preface | xiv | |
| Chapter 1 | Important Features of Java | 1 |
| 1.1 | Classes | 2 |
| Summary | 33 | |
| Exercises | 33 | |
| Programming Project 1.1 | Developing and Using a Sequence Class | 37 |
| Chapter 2 | Interfaces and Collection Classes | 39 |
| 2.1 | Abstract Methods and Abstract Classes | 40 |
| 2.2 | Interfaces | 41 |
| 2.3 | Arrays | 45 |
| 2.4 | Collection Classes | 46 |
| 2.5 | Storage Structures for Collection Classes | 48 |
| Summary | 59 | |
| Exercises | 60 | |
| Programming Project 2.1 | Expanding the LinkedCollection Class | 62 |
| Chapter 3 | Introduction to Software Engineering | 65 |
| 3.1 | The Software Development Life Cycle | 66 |
| 3.2 | Problem Analysis | 66 |
| 3.3 | Program Design | 69 |
| 3.4 | Program Implementation | 73 |
| 3.5 | Program Maintenance | 86 |
| Summary | 87 | |
| Exercises | 88 | |
| Programming Project 3.1 | Further Expansion of the LinkedCollection Class | 91 |
| Chapter 4 | Recursion | 93 |
| 4.1 | Introduction | 94 |
| 4.2 | Factorials | 94 |
| 4.3 | Decimal to Binary | 98 |
| 4.4 | Towers of Hanoi | 102 |
| 4.5 | Backtracking | 111 |
| 4.6 | Binary Search | 120 |
| 4.7 | Indirect Recursion | 131 |
| 4.8 | The Cost of Recursion | 132 |
| Summary | 133 | |
| Exercises | 134 | |
| Programming Project 4.1 | Iterative Version of Towers of Hanoi | 142 |
| Programming Project 4.2 | Eight Queens | 144 |
| Programming Project 4.3 | A Knight's Tour | 146 |
| Chapter 5 | Array Lists | 149 |
| 5.1 | The List Interface | 150 |
| 5.2 | The ArrayList Class | 151 |
| 5.3 | The ArrayList Implementation | 162 |
| 5.4 | Application: High-Precision Arithmetic | 169 |
| 5.5 | The Vector Class | 175 |
| Summary | 175 | |
| Exercises | 175 | |
| Programming Project 5.1 | Extending the VeryLongInt Class | 179 |
| Programming Project 5.2 | The Deque Class | 180 |
| Chapter 6 | Linked Lists | 185 |
| 6.1 | The LinkedList Class | 186 |
| 6.2 | Application: A Line Editor | 211 |
| Summary | 223 | |
| Exercises | 224 | |
| Programming Project 6.1 | Extending the Line Editor | 226 |
| Programming Project 6.2 | Alternative Design and Implementation of the LinkedList Class | 231 |
| Chapter 7 | Queues and Stacks | 233 |
| 7.1 | Queues | 234 |
| 7.2 | Computer Simulation | 242 |
| 7.3 | Application: A Simulated Car Wash | 244 |
| 7.4 | Stacks | 251 |
| 7.5 | Application: How Compilers Implement Recursion | 254 |
| 7.6 | Application: Converting From Infix to Postfix | 257 |
| Summary | 267 | |
| Exercises | 267 | |
| Programming Project 7.1 | Extending Speedo's Car Wash | 270 |
| Programming Project 7.2 | Run-Time Evaluation of a Condition | 272 |
| Programming Project 7.3 | An Iterative Version of Maze-Search | 276 |
| Chapter 8 | Binary Trees and Binary Search Trees | 277 |
| 8.1 | Definition and Properties of Binary Trees | 278 |
| 8.2 | Binary Search Trees | 294 |
| Summary | 316 | |
| Exercises | 317 | |
| Programming Project 8.1 | An Alternative Design and Implementation of the Binary-Search-Tree Data Structure | 321 |
| Chapter 9 | Balanced Binary Search Trees | 323 |
| 9.1 | A Problem with Binary Search Trees | 324 |
| 9.2 | Rotations | 324 |
| 9.3 | AVL Trees | 329 |
| 9.4 | Red-Black Trees | 348 |
| Summary | 355 | |
| Exercises | 356 | |
| Programming Project 9.1 | Defining the remove Method in the AVLTree Class | 360 |
| Chapter 10 | Tree Maps and Tree Sets | 361 |
| 10.1 | The TreeMap Class | 362 |
| 10.2 | Application: TreeMap Objects: A Simple Thesaurus | 389 |
| 10.3 | The TreeSet Class | 395 |
| 10.4 | Application: A Simple Spell-Checker | 399 |
| Summary | 405 | |
| Exercises | 405 | |
| Programming Project 10.1 | Enhancing the SpellChecker Project | 408 |
| Programming Project 10.2 | Determining Word Frequencies | 410 |
| Programming Project 10.3 | Building a Concordance | 412 |
| Chapter 11 | Priority Queues | 415 |
| 11.1 | Introduction | 416 |
| 11.2 | Definition of the PriorityQueue Interface | 417 |
| 11.3 | Implementations of the PriorityQueue Interface | 417 |
| 11.4 | Application: Huffman Codes | 432 |
| Summary | 446 | |
| Exercises | 447 | |
| Programming Project 11.1 | Decoding a Huffman-Encoded Message | 450 |
| Chapter 12 | Sorting | 453 |
| 12.1 | Introduction | 454 |
| 12.2 | Insertion Sort | 454 |
| 12.3 | How Fast Can We Sort? | 457 |
| 12.4 | Fast Sorts | 459 |
| Summary | 482 | |
| Exercises | 482 | |
| Programming Project 12.1 | File Sorting | 491 |
| Chapter 13 | Searching and the Hash Classes | 495 |
| 13.1 | A Framework to Analyze Searching | 496 |
| 13.2 | Review of Searching | 496 |
| 13.3 | The HashMap Class | 499 |
| 13.4 | The HashSet Class | 517 |
| 13.5 | Open-Address Hashing | 517 |
| Summary | 533 | |
| Exercises | 534 | |
| Programming Project 13.1 | Comparing Chained Hashing and Open-Address Hashing | 538 |
| Chapter 14 | Graphs, Trees, and Networks | 539 |
| 14.1 | Undirected Graphs | 540 |
| 14.2 | Directed Graphs | 543 |
| 14.3 | Trees | 544 |
| 14.4 | Networks | 545 |
| 14.5 | Graph Algorithms | 547 |
| 14.6 | Developing a Network Class | 563 |
| 14.7 | Backtracking through a Network | 582 |
| Summary | 584 | |
| Exercises | 585 | |
| Programming Project 14.1 | Completing the Implementation of the Network Class under the Adjacency-Matrix Design | 589 |
| Programming Project 14.2 | A Network Search | 590 |
| Appendix 1 | Mathematical Background | 593 |
| A1.1 | Introduction | 593 |
| A1.2 | Functions and Sequences | 593 |
| A1.3 | Sums and Products | 594 |
| A1.4 | Logarithms | 595 |
| A1.5 | Mathematical Induction | 597 |
| Exercises | 605 | |
| Appendix 2 | The GUI and GUIListener Classes | 607 |
| A2.1 | Introduction | 607 |
| A2.2 | Threads | 608 |
| A2.3 | Implementing the Process Interface | 610 |
| A2.4 | The GUI Class | 611 |
| A2.5 | The GUIListener Class | 615 |
| A2.6 | Putting It All Together | 617 |
| Appendix 3 | The Java Collections Framework | 619 |
| A3.1 | Introduction | 619 |
| A3.2 | The Collection Interface | 619 |
| A3.3 | The List Interface | 621 |
| A3.4 | The Listlterator Interface | 623 |
| A3.5 | The Set Interface | 625 |
| A3.6 | The Map Interface | 627 |
| A3.7 | The ArrayList Class | 630 |
| A3.8 | The LinkedList Class | 643 |
| A3.9 | The TreeSet Class | 662 |
| A3.10 | The TreeMap Class | 674 |
| A3.11 | The HashSet Class | 689 |
| A3.12 | The HashMap Class | 698 |
| Bibliography | 709 | |
| Index | 711 |
Customer Reviews
Average Review: