Rent 9780132370455 | Data Structures And Abstractions With Java

Summary Table of Contents

For one- or two-semester courses in data structures (CS-2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems. This is the most student-friendly data structures text available that introduces ADTs in individual, brief chapters each with pedagogical tools to help students master each concept. Using the latest features of Java 5, this unique object-oriented presentation makes a clear distinction between specification and implementation to simplify learning, while providing maximum classroom ... MORE

Introduction

(4)

Java Classes

(34)

Objects and Classes

(2)

... MORE

Using the Methods in a Java Class

(2)

References and Aliases

(1)

Defining a Java Class

(16)

Method Definitions

(2)

Arguments and Parameters

(1)

Passing Arguments

(4)

A Definition of the Class Name

(1)

Constructors

(2)

The Method to String

(1)

Methods That Call Other Methods

(1)

Methods That Return an Instance of Their Class

(1)

Static Fields and Methods

(1)

Overloading Methods

(1)

Enumeration as a Class

(3)

Packages

(10)

The Java Class Library

(9)

Creating Classes from Other Classes

(38)

Composition

(6)

Generic Types

(2)

Adapters

(1)

Inheritance

(12)

Invoking Constructors from Within Constructors

(2)

Private Fields and Methods of the Base Class

(1)

Protected Access

(1)

Overriding and Overloading Methods

(5)

Multiple Inheritance

(1)

Type Compatibility and Base Classes

(5)

The Class Object

(2)

Abstract Classes and Methods

(2)

Polymorphism

(14)

Designing Classes

(30)

Encapsulation

(2)

Specifying Methods

(4)

Assertions

(2)

Java Interfaces

(11)

Writing an Interface

(2)

Implementing an Interface

(1)

An Interface as a Data Type

(1)

Generic Types Within an Interface

(1)

The Interface Comparable

(2)

Extending an Interface

(1)

Interfaces Versus Abstract Classes

(1)

Named Constants

(2)

Choosing Classes

(5)

Identifying Classes

(1)

CRC Cards

(3)

Reusing Classes

100

(7)

Lists

107

(20)

Specifications for the ADT List

108

(8)

Refining the Specifications

113

(3)

Using the ADT List

116

(4)

Using a List Is Like Using a Vending Machine

120

(2)

Java Class Library: The Interface List

122

(5)

List Implementations That Use Arrays

127

(24)

Using a Fixed-Size Array to Implement the ADT List

128

(10)

An Analogy

128

(2)

The Java Implementation

130

(8)

Using Array Expansion to Implement the ADT List

138

(4)

Expanding an Array

138

(2)

A New Implementation of a List

140

(2)

Java Class Library: The Classes ArrayList and Vector

142

(4)

Using a Vector to Implement the ADT List

143

(3)

The Pros and Cons of Using an Array to Implement the ADT List

146

(5)

A List Implementation That Links Data

151

(28)

Linked Data

152

(8)

Forming a Chain by Adding to Its Beginning

153

(2)

Forming a Chain by Adding to Its End

155

(2)

Forming a Chain by Adding at Various Positions

157

(3)

A Linked Implementation of the ADT List

160

(13)

The Private Class Node

160

(2)

The Data Fields and Constructor

162

(1)

Choosing a Core Group of Methods to Implement

163

(1)

Adding to the End of the List

164

(2)

Adding at a Given Position Within the List

166

(4)

The Private Method getNodeAt

170

(1)

Assertions and the Method isEmpty

171

(1)

The Method display

172

(1)

Testing the Incomplete Implementation

173

(6)

Completing the Linked Implementation of a List

179

(22)

Removing an Item from a Linked Chain

180

(3)

Completing the Linked Implementation of the ADT List

183

(5)

The Method remove

183

(3)

The Method replace

186

(1)

The Method getEntry

186

(1)

The Method contains

187

(1)

The Remaining Methods

187

(1)

A Class Node That Has Set and Get Methods

188

(3)

Tail References

191

(5)

A Revised Implementation of the List

192

(4)

The Pros and Cons of Using a Chain to Implement the ADT List

196

(1)

Java Class Library: The Class LinkedList

196

(5)

Iterators

201

(42)

What Is an Iterator?

202

(1)

The Interface Iterator

203

(7)

Using the Interface Iterator

204

(6)

A Separate Class Iterator

210

(3)

An Inner Class Iterator

213

(8)

A Linked Implementation

213

(4)

An Array-Based Implementation

217

(4)

Why Are Iterator Methods in Their Own Class?

221

(1)

The Interface ListIterator

222

(6)

Using the Interface ListIterator

226

(2)

An Array-Based Implementation of the Interface ListIterator

228

(7)

The Inner Class

229

(6)

Java Class Library: The Interface Iterable

235

(8)

Iterable and for-each loops

236

(1)

The Interface List Revisited

237

(6)

The Efficiency of Algorithms

243

(26)

Motivation

244

(2)

Measuring an Algorithm's Efficiency

246

(6)

Big Oh Notation

249

(3)

Formalities

252

(3)

Picturing Efficiency

255

(3)

The Efficiency of Implementations of the ADT List

258

(11)

An Array-Based Implementation

258

(2)

A Linked Implementation

260

(2)

Comparing the Implementations

262

(7)

Recursion

269

(36)

What Is Recursion?

270

(5)

Tracing a Recursive Method

275

(2)

Recursive Methods That Return a Value

277

(3)

Recursively Processing an Array

280

(2)

Recursively Processing a Linked Chain

282

(2)

The Time Efficiency of Recursive Methods

284

(3)

The Time Efficiency of countDown

284

(1)

The Time Efficiency of Computing xn

285

(2)

A Simple Solution to a Difficult Problem

287

(5)

A Poor Solution to a Simple Problem

292

(2)

Tail Recursion

294

(2)

Mutual Recursion

296

(9)

An Introduction to Sorting

305

(26)

Organizing Java Methods That Sort an Array

306

(2)

Selection Sort

308

(5)

Iterative Selection Sort

309

(3)

Recursive Selection Sort

312

(1)

The Efficiency of Selection Sort

312

(1)

Insertion Sort

313

(9)

Iterative Insertion Sort

314

(2)

Recursive Insertion Sort

316

(2)

The Efficiency of Insertion Sort

318

(1)

Insertion Sort of a Chain of Linked Nodes

318

(4)

Shell Sort

322

(3)

The Java Code

323

(1)

The Efficiency of Shell Sort

324

(1)

Comparing the Algorithms

325

(6)

Faster Sorting Methods

331

(24)

Merge Sort

332

(6)

Merging Arrays

332

(1)

Recursive Merge Sort

333

(3)

The Efficiency of Merge Sort

336

(1)

Iterative Merge Sort

337

(1)

Merge Sort in the Java Class Library

338

(1)

Quick Sort

338

(8)

The Efficiency of Quick Sort

339

(1)

Creating the Partition

340

(3)

Java Code for Quick Sort

343

(3)

Quick Sort in the Java Class Library

346

(1)

Radix Sort

346

(3)

Pseudocode for Radix Sort

348

(1)

The Efficiency of Radix Sort

348

(1)

Comparing the Algorithms

349

(6)

Sorted Lists

355

(22)

Specifications for the ADT Sorted List

356

(4)

Using the ADT Sorted List

359

(1)

A Linked Implementation

360

(8)

The Method add

361

(7)

The Efficiency of the Linked Implementation

368

(1)

An Implementation That Uses the ADT List

368

(9)

Efficiency Issues

372

(5)

Inheritance and Lists

377

(14)

Using Inheritance to Implement a Sorted List

378

(2)

Designing a Base Class

380

(7)

Creating an Abstract Base Class

385

(2)

An Efficient Implementation of a Sorted List

387

(4)

The Method add

387

(4)

Mutable, Immutable, and Cloneable Objects

391

(26)

Mutable and Immutable Objects

392

(6)

Creating a Read-Only Class

395

(1)

Companion Classes

396

(2)

Cloneable Objects

398

(19)

Cloning an Array

404

(3)

Cloning a Chain

407

(3)

A Sorted List of Clones

410

(7)

Searching

417

(22)

The Problem

418

(1)

Searching an Unsorted Array

419

(3)

An Iterative Sequential Search of an Unsorted Array

419

(1)

A Recursive Sequential Search of an Unsorted Array

420

(2)

The Efficiency of a Sequential Search of an Array

422

(1)

Searching a Sorted Array

422

(7)

A Sequential Search of a Sorted Array

422

(1)

A Binary Search of a Sorted Array

423

(5)

Java Class Library: The Method binarySearch

428

(1)

The Efficiency of a Binary Search of an Array

428

(1)

Searching an Unsorted Chain

429

(3)

An Iterative Sequential Search of an Unsorted Chain

430

(1)

A Recursive Sequential Search of an Unsorted Chain

430

(1)

The Efficiency of a Sequential Search of a Chain

431

(1)

Searching a Sorted Chain

432

(1)

A Sequential Search of a Sorted Chain

432

(1)

A Binary Search of a Sorted Chain

432

(1)

Choosing a Search Method

433

(6)

Dictionaries

439

(24)

Specifications for the ADT Dictionary

440

(6)

A Java Interface

444

(1)

Iterators

445

(1)

Using the ADT Dictionary

446

(12)

A Directory of Telephone Numbers

447

(5)

The Frequency of Words

452

(3)

A Concordance of Words

455

(3)

Java Class Library: The Interface Map

458

(5)

Dictionary Implementations

463

(24)

Array-Based Implementations

464

(10)

An Unsorted Array-Based Dictionary

464

(5)

A Sorted Array-Based Dictionary

469

(5)

Vector-Based Implementations

474

(4)

Linked Implementations

478

(9)

An Unsorted Linked Dictionary

479

(1)

A Sorted Linked Dictionary

480

(7)

Introducing Hashing

487

(24)

What Is Hashing?

488

(3)

Hash Functions

491

(4)

Computing Hash Codes

491

(3)

Compressing a Hash Code into an Index for the Hash Table

494

(1)

Resolving Collisions

495

(16)

Open Addressing with Linear Probing

495

(6)

Open Addressing with Quadratic Probing

501

(1)

Open Addressing with Double Hashing

501

(2)

A Potential Problem with Open Addressing

503

(1)

Separate Chaining

503

(8)

Hashing as a Dictionary Implementation

511

(22)

The Efficiency of Hashing

512

(4)

The Load Factor

512

(1)

The Cost of Open Addressing

513

(2)

The Cost of Separate Chaining

515

(1)

Rehashing

516

(1)

Comparing Schemes for Collision Resolution

517

(1)

A Dictionary Implementation That Uses Hashing

518

(10)

Entries in the Hash Table

518

(1)

Data Fields and Constructors

519

(2)

The Methods getValue, remove, and add

521

(6)

Iterators

527

(1)

Java Class Library: The Class HashMap

528

(5)

Stacks

533

(32)

Specifications of the ADT Stack

534

(4)

Using a Stack to Process Algebraic Expressions

538

(17)

Checking for Balanced Parentheses, Brackets, and Braces in an infix Algebraic Expression

539

(5)

Transforming an Infix Expression to a Postfix Expression

544

(7)

Evaluating Postfix Expressions

551

(1)

Evaluating Infix Expressions

552

(3)

The Program Stack

555

(2)

Recursive Methods

556

(1)

Using a Stack Instead of Recursion

557

(2)

An Iterative Binary Search

557

(2)

Java Class Library: The Class Stack

559

(6)

Stack Implementations

565

(14)

A Linked Implementation

566

(3)

An Array-Based Implementation

569

(4)

A Vector-Based Implementation

573

(6)

Queues, Deques, and Priority Queues

579

(26)

Specifications of the ADT Queue

580

(4)

Using a Queue to Simulate a Waiting Line

584

(6)

The Classes WaitLine and Customer

585

(5)

Using a Queue to Compute the Capital Gain in a Sale of Stock

590

(3)

The Classes StockLedger and StockPurchase

590

(3)

Java Class Library: The Interface Queue

593

(1)

Specifications of the ADT Deque

594

(2)

Using a Deque to Compute the Capital Gain in a Sale of Stock

596

(1)

Specifications of the ADT Priority Queue

597

(1)

Using a Priority Queue to Track Your Assignments

598

(7)

Queue, Deque, and Priority Queue Implementations

605

(34)

A Linked Implementation of a Queue

606

(4)

An Array-Based Implementation of a Queue

610

(9)

A Circular Array

610

(3)

A Circular Array with One Unused Location

613

(6)

A Vector-Based Implementation of a Queue

619

(1)

Circular Linked Implementations of a Queue

620

(8)

A Two-Part Circular Linked Chain

621

(7)

Java Class Library: The Class AbstractQueue

628

(1)

A Doubly Linked Implementation of a Deque

628

(4)

Possible Implementations of a Priority Queue

632

(1)

Java Class Library: The Class PriorityQueue

633

(6)

Trees

639

(32)

Tree Concepts

640

(7)

Hierarchical Organizations

640

(2)

Tree Terminology

642

(5)

Traversals of a Tree

647

(3)

Traversals of a Binary Tree

647

(3)

Traversals of a General Tree

650

(1)

Java Interfaces for Trees

650

(3)

Interfaces for All Trees

651

(1)

An Interface for Binary Trees

651

(2)

Examples of Binary Trees

653

(10)

Expression Trees

653

(2)

Decision Trees

655

(4)

Binary Search Trees

659

(2)

Heaps

661

(2)

Examples of General Trees

663

(8)

Parse Trees

664

(1)

Game Trees

664

(7)

Tree Implementations

671

(26)

The Nodes in a Binary Tree

672

(3)

An Interface for a Node

673

(1)

An Implementation of BinaryNode

674

(1)

An Implementation of the ADT Binary Tree

675

(12)

Creating a Basic Binary Tree

676

(1)

The Method privateSetTree

677

(3)

Accessor and Mutator Methods

680

(1)

Computing the Height and Counting Nodes

681

(1)

Traversals

682

(5)

An Implementation of an Expression Tree

687

(2)

General Trees

689

(8)

A Node for a General Tree

689

(1)

Using a Binary Tree to Represent a General Tree

690

(7)

A Binary Search Tree Implementation

697

(40)

Getting Started

698

(5)

An Interface for the Binary Search Tree

699

(2)

Duplicate Entries

701

(1)

Beginning the Class Definition

702

(1)

Searching and Retrieving

703

(2)

Traversing

705

(1)

Adding an Entry

705

(7)

A Recursive Implementation

706

(4)

An Iterative Implementation

710

(2)

Removing an Entry

712

(13)

Removing an Entry Whose Node Is a Leaf

712

(1)

Removing an Entry Whose Node Has One Child

713

(1)

Removing an Entry Whose Node Has Two Children

713

(4)

Removing an Entry in the Root

717

(1)

A Recursive Implementation

717

(4)

An Iterative Implementation

721

(4)

The Efficiency of Operations

725

(3)

The Importance of Balance

726

(1)

The Order in Which Nodes Are Added

727

(1)

An Implementation of the ADT Dictionary

728

(9)

A Heap Implementation

737

(20)

Reprise: The ADT Heap

738

(1)

Using an Array to Represent a Heap

738

(3)

Adding an Entry

741

(3)

Removing the Root

744

(3)

Creating a Heap

747

(3)

Heap Sort

750

(7)

Balanced Search Trees

757

(34)

AVL Trees

758

(12)

Single Rotations

758

(3)

Double Rotations

761

(4)

Implementation Details

765

(5)

Trees

770

(5)

Searching a 2-3 Tree

771

(1)

Adding Entries to a 2-3 Tree

772

(2)

Splitting Nodes During Addition

774

(1)

2-4 Trees

775

(4)

Adding Entries to a 2-4 Tree

776

(2)

Comparing AVL, 2-3, and 2-4 Trees

778

(1)

Red-Black Trees

779

(8)

Properties of a Red-Black Tree

780

(1)

Adding Entries to a Red-Black Tree

781

(5)

Java Class Library: The Class TreeMap

786

(1)

B-Trees

787

(4)

Graphs

791

(30)

Some Examples and Terminology

792

(5)

Road Maps

792

(3)

Airline Routes

795

(1)

Mazes

796

(1)

Course Prerequisites

796

(1)

Trees

797

(1)

Traversals

797

(4)

Breadth-First Traversal

798

(2)

Depth-First Traversal

800

(1)

Topological Order

801

(2)

Paths

803

(8)

Finding a Path

803

(1)

The Shortest Path in an Unweighted Graph

803

(4)

The Shortest Path in a Weighted Graph

807

(4)

Java Interfaces for the ADT Graph

811

(10)

Graph Implementations

821

(22)

An Overview of Two Implementations

822

(2)

The Adjacency Matrix

822

(1)

The Adjacency List

823

(1)

Vertices and Edges

824

(8)

Specifying the Class Vertex

825

(2)

The Inner Class Edge

827

(1)

Implementing the Class Vertex

828

(4)

An Implementation of the ADT Graph

832

(11)

Basic Operations

832

(4)

Graph Algorithms

836

(7)

Appendix A Java Essentials

843

(60)

Appendix B Exception Handling

903

(12)

Appendix C File Input and Output

915

(22)

Appendix D Documentation and Programming Style

937

(6)

Appendix E Answers to Self-Test Questions

943

(40)

Index

983

RENT TEXTBOOKS

Data Structures And Abstractions With Java

Why Rent from Knetbooks?

Top 5 reasons to order all your textbooks from Knetbooks:

Related Products