Java集合框架与数据结构第三版精华解读

下载需积分: 10 | PDF格式 | 4.56MB | 更新于2024-07-18 | 22 浏览量 | 举报

"Data Structures and the Java Collections Framework, 3rd Edition" 是一本关于数据结构和Java集合框架的专业书籍，作者是William J. Collins，由John Wiley & Sons, Inc.出版社出版。本书深入探讨了数据结构这一核心计算机科学概念，同时结合了Java编程语言中的集合框架，帮助读者理解如何在实际编程中有效地组织和操作数据。Java集合框架是Java平台标准版（Java SE）的一部分，提供了各种数据结构和算法的实现，如列表、队列、堆、映射等，使得开发人员能够高效地处理数据。在书中，作者可能详细介绍了以下知识点： 1. **数据结构基础**：涵盖线性结构（如数组、链表）、树结构（如二叉树、堆）、图结构以及队列、栈等基本数据结构的概念、操作和应用。 2. **Java集合接口**：如List、Set、Queue和Map接口，它们定义了各种数据结构的行为，以及ArrayList、LinkedList、HashSet、TreeSet、LinkedList、PriorityQueue和HashMap等具体实现类的使用。 3. **泛型**：在Java中使用泛型来实现类型安全的数据结构，提高代码的可读性和可维护性。 4. **迭代器与流**：介绍如何通过Iterator接口遍历集合，以及Java 8引入的Stream API，用于对集合进行高效的操作和函数式编程。 5. **并发编程**：讨论如何在多线程环境中安全地使用集合，包括同步容器（如Vector、Hashtable）和并发容器（如ConcurrentHashMap、CopyOnWriteArrayList）。 6. **性能优化**：分析不同数据结构和算法的性能特性，指导读者根据具体需求选择合适的数据结构，并提供优化策略。 7. **实用工具类**：介绍Collections类和Arrays类提供的静态方法，用于集合和数组的操作，如排序、查找、复制等。 8. **枚举类型和枚举集**：如何使用枚举类型来增强程序的类型安全性和可读性，以及与集合框架的交互。 9. **Java集合框架的设计模式**：书中可能会讲解集合框架背后的设计模式，如工厂模式、适配器模式、装饰器模式等。 10. **实战示例**：通过实例代码展示如何在实际项目中应用数据结构和集合框架，帮助读者巩固理论知识并提升编程技能。本书适合Java程序员、软件工程师、计算机科学学生和教师阅读，它不仅能提供理论知识，还能为实际开发提供有价值的指导。通过学习本书，读者将能够更好地理解和利用Java集合框架，提升编程效率和代码质量。

xiv CONTENTS

Programming Exercises 594

Programming Project 13.1: Decoding a

Huffman-Encoded Message 595

Programming Project 13.2: An Integrated Web

Browser and Search Engine, Part 5 597

CHAPTER 14

Hashing 599

Chapter Objectives 599

14.1 A Framework to Analyze Searching 599

14.2 Review of Searching 600

14.2.1 Sequential Search 600

14.2.2 Binary Search 601

14.2.3 Red-Black-Tree Search 602

14.3 The

HashMap Implementation of the Map

Interface 603

14.3.1 Hashing 604

14.3.2 The Uniform Hashing

Assumption 609

14.3.3 Chaining 609

14.3.4 Implementation of the

HashMap

Class 612

14.3.5 Analysis of the

containsKey

Method 614

14.3.6 The

HashIterator

Class 615

14.3.7 Creating a Symbol Table by

Hashing 617

14.4 The

HashSet Class 625

14.5 Open-Address Hashing (optional) 626

14.5.1 The

remove

Method 627

14.5.2 Primary Clustering 631

14.5.3 Double Hashing 632

Summary 635

Crossword Puzzle 636

Concept Exercises 637

Programming Exercises 639

Programming Project 14.1: The Double Hashing

Implementation of the

HashMap Class 640

Programming Project 14.2: An Integrated Web

Browser and Search Engine, Part 6 640

CHAPTER 15

Graphs, Trees, and Networks 643

Chapter Objectives 643

15.1 Undirected Graphs 643

15.2 Directed Graphs 647

15.3 Trees 648

15.4 Networks 649

15.5 Graph Algorithms 650

15.5.1 Iterators 650

15.5.2 Connectedness 658

15.5.3 Generating a Minimum Spanning

Tree 659

15.5.4 Finding the Shortest Path through a

Network 663

15.5.5 Finding the Longest Path through a

Network? 667

15.6 A

Network Class 669

15.6.1 Method Speciﬁcations and Testing

of the

Network

Class 671

15.6.2 Fields in the Network Class 680

15.6.3 Method Deﬁnitions in the

Network

Class 681

15.7 Backtracking Through A Network 686

Summary 689

Crossword Puzzle 690

Concept Exercises 691

Programming Exercises 693

Programming Project 15.1: The Traveling

Salesperson Problem 694

Programming Project 15.2: Backtracking through a

Network 695

Programming Project 15.3: Determining Critical

Activities in a Project Network 697

Programming Project 15.4: An Integrated Web

Browser and Search Engine, Part 7 698

PREFACE

This book is intended for an object-oriented course in data structures and algorithms. The implementation

language is Java, and it is assumed that students have taken a ﬁrst course in programming, not necessarily

in Java. That course should have covered the fundamental statements and data types, as well as arrays.

Chapter 0 supplies the material on Java that is fundamental to the remaining chapters, so it serves as a

review for those with previous experience in Java, and brings Java novices up to speed.

WHAT’S NEW IN THE THIRD EDITION

This edition presents two major changes from the second edition. First, the Scanner class has replaced

the

BufferedReader and StringTokenizer classes. The Scanner class’s versatility supports pattern

matching as well as keyboard input and ﬁle input. Second, there is an increased emphasis on testing. In

particular, the unit-testing features of JUnit 4 are introduced in Chapter 2 and integrated in applications

throughout the remaining chapters.

THE JAVA COLLECTIONS FRAMEWORK

One of the distinctive features of this text is its emphasis on the Java Collections Framework, part of

the

java.util package. Basically, the framework is a hierarchy with interfaces at each level except the

lowest, and collection classes that implement those interfaces at the lowest level. The collection classes

implement most of the data structures studied in a second computer-science course, such as a resizable array

class, a linked-list class, a stack class, a queue class, a balanced binary-search-tree class, a priority-queue

class, and a hash-map class.

There are several advantages to using the Java Collections Framework. First, students will be working

with code that has been extensively tested; they need not depend on modules created by the instructor or

textbook author. Second, the framework is available for later courses in the curriculum and beyond. Third,

although the primary emphasis is on using the Java Collections Framework, the framework classes are not

treated simply as “black boxes.” For each such class, the heading and ﬁelds are provided, and one method

deﬁnition is dissected. This exposition takes away some of the mystery that would otherwise surround the

class, and allows students to see the efﬁciency and succinctness of professionals’ code.

The version of the Java Collections Framework we will be working with includes type parameters.

Type parameters, sometimes called “generic types,” “generics,” or “templates,” were added to the Java

language starting with Java 5.0. With type parameters, there is no need to downcast the return value from

a collection, and many errors can be detected at compile-time that previously were discoverable only at

run-time.

To complement generics, three other features have been added: boxing, unboxing, and an enhanced

for statement. The elements in generic collections must be objects, often from a wrapper class such as

Integer. If a primitive value appears where a collection method requires a wrapper element as an argu-

ment, boxing automatically converts the primitive value to the corresponding wrapper element. Conversely,

xvii

xviii PREFACE

if a wrapper-class element appears where a primitive value is needed, unboxing automatically converts

that element to the corresponding primitive value. Finally, the enhanced

for statement—often called a

“for-each” statement—has a sleek structure for iterating through a collection. The net effect of these new

features of Java is to improve productivity by relegating to the compiler many of the “boiler-plate” details

related to casting and iterating.

OTHER IMPLEMENTATIONS CONSIDERED

As important as the Java Collections Framework implementations are, they cannot be the exclusive focus

of such a fundamental course in data structures and algorithms. Approaches that differ from those in the

framework deserve consideration. For example, the

HashMap class utilizes chaining, so there is a separate

section on open addressing, and a discussion of the trade-offs of one design over the other. Also, there is

coverage of data structures (such as a weighted digraph class) and algorithms (such as Heap Sort) that are

not yet included in the Java Collections Framework.

Sometimes, the complexity of the framework classes is mitigated by ﬁrst introducing simpler

versions of those classes. For example, the

SinglyLinkedList class—not in the Java Collections

Framework—helps to pave the way for the more powerful

LinkedList class, which is in the framework.

And the

BinarySearchTree class prepares students to understand the framework’s TreeMap class,

based on red-black trees.

This text satisﬁes another important goal of a data structures and algorithms course: Students have the

opportunity to develop their own data structures. There are programming projects in which data structures

are either created “from the ground up” or extended from examples in the chapters. And there are many

other projects to develop or extend applications that use the Java Collections Framework.

JUNIT AND TEST-FIRST DEVELOPMENT

Students realize that methods with no compile-time errors may still be a long way from correct, but they

often need help in learning how to systematically test their methods. As described in Chapter 2, JUnit is

an Open Source platform for the testing of units, that is, methods. For example, to test a

findMedian

method, a FindMedianTest class is developed. The FindMedianTest class consists mainly of methods

that test

findMedian. When all the test methods in FindMedianTest have been passed, the student’s

conﬁdence in the correctness of

findMedian is increased.

Instead of writing the tests after a method has been deﬁned, we employ a “test-ﬁrst” strategy. As

soon as a method’s speciﬁcations have been written, the tests for that method are coded. This ensures

that the tests are based on the speciﬁcations only, not on the deﬁnition of the method. These tests are run

on a “stub” version of the method to be tested, and all of the tests will fail. Then the method deﬁnition

is written, and the tests are run on that version of the method. Corrections to the method are made as

necessary until, eventually, all tests succeed. The test-ﬁrst paradigm is introduced in Chapter 2 and utilized

in subsequent chapters.

PEDAGOGICAL FEATURES

This text offers several features that may improve the teaching environment for instructors and the learning

environment for students. Each chapter starts with a list of objectives, and most chapters conclude with

several major programming assignments. Each chapter also has a crossword puzzle, from Crossword

www.allitebooks.com

剩余759页未读，继续阅读

kernelkoder

粉丝: 57
资源: 317

Java集合框架与数据结构第三版精华解读

Java Collections Framework详解：第三版数据结构指南

C++ Data Structures 3rd Edition eBook: Jones & Bartlett's Genuine Guide

《Java 3版数据结构与算法详解》：高效Java编程与算法分析权威指南

Data Structures and the Java Collections Framework(3rd) 无水印pdf

数据结构和Java集合框架《Data Structures and the Java Collections Framework》

Data Structures and Algorithm Analysis in C++ 3rd edition

Data Structures And Algorithms in Java 4th edition

Data Structures and Algorithms in Java (2nd Edition)

Data Structures and Algorithms in Java 4th edition by Goodrich

Data Structures and Algorithm Analysis in Java Third Edition

最新资源