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

需积分: 15 123 浏览量更新于2024-07-19 收藏 4.31MB PDF 举报

《数据结构与Java集合框架》(Data Structures and the Java Collections Framework)是William J. Collins撰写的一本计算机科学领域的著作，于2004年出版。该书第三版详细探讨了数据结构在Java编程中的应用以及Java集合框架的设计与使用。作者以其丰富的经验和深入理解，为读者揭示了如何利用Java的集合类库（如ArrayList、LinkedList、HashMap等）来管理和操作各种数据结构，如数组、链表、树和图等。书中内容涵盖了基础的数据结构概念，包括线性数据结构（顺序和链式）、树形数据结构（二叉树、平衡树等）、图算法等，这些都是计算机科学的核心组成部分。此外，Java集合框架是Java SE平台的重要特性，它提供了一套高度抽象的接口，使得开发者能够方便地处理大量数据的存储和操作，无需关心底层实现细节，有助于提升代码的可读性和维护性。书中还可能涉及如何设计高效的搜索、排序和遍历算法，以及如何利用并发工具（如Concurrent Collections）处理多线程环境下的数据。此外，随着版本的更新，书中可能还会包含对Java SE新版本中集合框架的改进和优化，如lambda表达式和Stream API的使用，这对于现代Java开发者来说具有很高的实用价值。对于学习者而言，这本书不仅是一本技术指南，还是一本实践手册，通过阅读和实践，读者可以掌握数据结构的基本原理，提高程序设计技巧，并能熟练运用Java集合框架进行高效的数据处理。同时，书中强调的编程原则和最佳实践，也有助于培养良好的编程习惯。《数据结构与Java集合框架》是计算机科学特别是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

剩余759页未读，继续阅读

qq_40433942

粉丝: 0
资源: 2

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

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

Java Collections Framework

Sprinthall, N. A., & Collins, W. A. (1984). Adolescent psychology: A developmental view. Reading, MA: Addison-Wesley, 548 pp., [dollar]22.00

casey-collins.github.io

Cre8ive-collins.github.io

Collins, R. The Credential Society: An Historical Sociology of Education and Stratification. New York: Academic Press, 1979, 222 pp., [dollar]13.50

Emma-M-Collins.github.io：数据科学项目组合

完整的电子书 Marva Collins Way.pdf

Collins, R. 证书协会：教育和分层的历史社会学。 纽约：学术出版社，1979 年，222 页，[美元]13.50

Collins-v1.1.ipa

最新资源

Collins, R. 证书协会：教育和分层的历史社会学。纽约：学术出版社，1979 年，222 页，[美元]13.50