Product Cover Image

Data Structures Outside-In with Java, CourseSmart eTextbook

By Sesh Venugopal

Published by Prentice Hall

Published Date: Nov 28, 2006

More Product Info

Description

For courses in Java — Data Structures/CS2.

 

 

This innovative new text encourages students to utilize the “Outside-In” approach to learning the use, design and implementation of data structures. The author introduces every data structure by first narrating its properties and use in applications (the "outside" view) – enabling instructors to introduce a data structure in a realistic context where it is used. He then teaches how to build data structures (the "inside" view); students learn how to evaluate usability, flexibility, extensibility, and performance in designing and implementing classic data structures.

 

Table of Contents

Preface xv

1 Object-Oriented Programming in Java 1

1.1 Objects and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.2 Lifetime, State and Messages . . . . . . . . . . . . . . . . . . . . 2

1.1.3 Clients of an Object . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.4 Separation of Interface from Implementation . . . . . . . . . . . . 3

1.2 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 State and Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.2 Method Overloading . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 Object Creation, Constructors, Garbage Collection . . . . . . . . . 7

1.2.4 Method Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.5 Static Fields and Methods . . . . . . . . . . . . . . . . . . . . . . 12

1.2.6 Object References . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3.1 Superclass and Subclass . . . . . . . . . . . . . . . . . . . . . . . 17

1.3.2 Inherited and Specialized Fields . . . . . . . . . . . . . . . . . . . 19

1.3.3 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

ii CONTENTS

1.3.4 Object Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.3.5 Inherited and Specialized Methods . . . . . . . . . . . . . . . . . . 22

1.3.6 Method Overriding . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.4 The Object Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.4.1 The equals Method . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.4.2 The toString Method . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.4.3 The clone Method . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.5 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1.5.1 Interpreting an exception message . . . . . . . . . . . . . . . . . . 29

1.5.2 Homegrown error handling . . . . . . . . . . . . . . . . . . . . . . 31

1.5.3 Throwing an exception . . . . . . . . . . . . . . . . . . . . . . . . 37

1.5.4 Catching an exception . . . . . . . . . . . . . . . . . . . . . . . . 39

1.5.5 Exception class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

1.6 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

1.6.1 Terminal-driven IO . . . . . . . . . . . . . . . . . . . . . . . . . . 47

1.6.2 File-based IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

1.6.3 String tokenizing . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

1.6.4 Writing an exception class . . . . . . . . . . . . . . . . . . . . . . 55

1.7 Class Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

1.7.1 Java packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

1.7.2 Organizing packages . . . . . . . . . . . . . . . . . . . . . . . . . 58

1.7.3 Name conflict resolution . . . . . . . . . . . . . . . . . . . . . . . 62

1.8 Access control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

1.8.1 Private Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

1.8.2 Package Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

1.8.3 Protected Access . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

CONTENTS iii

1.8.4 Public Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

1.8.5 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

1.9 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

1.9.1 Polymorphic Reference . . . . . . . . . . . . . . . . . . . . . . . . 67

1.9.2 Casting Up the Class Hierarchy . . . . . . . . . . . . . . . . . . . 68

1.9.3 Casting Down the Class Hierarchy . . . . . . . . . . . . . . . . . . 69

1.9.4 The instanceof Operator . . . . . . . . . . . . . . . . . . . . . . . 70

1.10 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

1.10.1 Abstract Class Shape . . . . . . . . . . . . . . . . . . . . . . . . . 72

1.10.2 Abstract Class Properties . . . . . . . . . . . . . . . . . . . . . . . 73

1.11 A Game Park Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

1.12 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

1.12.1 The Java interface Construct . . . . . . . . . . . . . . . . . . . . . 78

1.12.2 Implementing an interface . . . . . . . . . . . . . . . . . . . . . . 78

1.12.3 Interface as a Type . . . . . . . . . . . . . . . . . . . . . . . . . . 79

1.12.4 The Need for Interfaces . . . . . . . . . . . . . . . . . . . . . . . 79

1.12.5 Extending Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 81

1.13 Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

1.13.1 Using java.util.ArrayList for Collections . . . . . . . . . . . . . . . 83

1.13.2 The java.util.ArrayList Public Interface . . . . . . . . . . . . . . . 85

1.13.3 Implementing a Generic Class . . . . . . . . . . . . . . . . . . . . 86

1.13.4 Implementing a Generic Interface . . . . . . . . . . . . . . . . . . 87

1.13.5 Static Template Methods . . . . . . . . . . . . . . . . . . . . . . . 91

1.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

1.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

1.16 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

iv CONTENTS

2 The Big Picture 103

2.1 What Are Data Structures? . . . . . . . . . . . . . . . . . . . . . . . . . . 104

2.2 What Data Structures Do We Study? . . . . . . . . . . . . . . . . . . . . . 104

2.3 What are Abstract Data Types? . . . . . . . . . . . . . . . . . . . . . . . . 108

2.4 Why OOP and Java for Data Structures? . . . . . . . . . . . . . . . . . . . 110

2.5 How Do I Choose the Right Data Structures? . . . . . . . . . . . . . . . . 112

3 Efficiency of Algorithms 115

3.1 Polynomial Arithmetic: A Running Example . . . . . . . . . . . . . . . . 116

3.2 Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

3.3 Input Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

3.4 Asymptotic Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . 121

3.5 Order and Big Oh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

3.5.1 Typical Running Time Orders . . . . . . . . . . . . . . . . . . . . 125

3.5.2 Multi-variable Order . . . . . . . . . . . . . . . . . . . . . . . . . 129

3.5.3 Relative Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

3.5.4 Order Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

3.6 Worst-case and Average . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

4 Unordered List 141

4.1 Unordered List Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

4.2 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.2.1 Average Case Analysis . . . . . . . . . . . . . . . . . . . . . . . . 144

4.2.2 Rearranging Data Based on Search Patterns . . . . . . . . . . . . . 146

4.3 A List Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

CONTENTS v

4.4 An ExpenseList Class Using List . . . . . . . . . . . . . . . . . . . . . . . 150

4.4.1 Expense Class Interface . . . . . . . . . . . . . . . . . . . . . . . 150

4.4.2 Expense Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

4.4.3 ExpenseList Class Interface . . . . . . . . . . . . . . . . . . . . . 153

4.4.4 ExpenseList Class Implementation . . . . . . . . . . . . . . . . . . 155

4.4.5 Equality of Objects and Searching . . . . . . . . . . . . . . . . . . 157

4.5 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

4.5.1 Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

4.5.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

4.5.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

4.5.4 Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

4.5.5 Circular Linked List . . . . . . . . . . . . . . . . . . . . . . . . . 167

4.6 A LinkedList class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

4.7 List Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 177

4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

4.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

4.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

5 Ordered List 187

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

5.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

5.2.1 Divide In Half . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

5.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

5.3 Ordering: Interface java.lang.Comparable . . . . . . . . . . . . . . 193

5.4 An OrderedList Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

5.5 Merging Ordered Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

5.5.1 Two-finger Merge Algorithm . . . . . . . . . . . . . . . . . . . . . 201

vi CONTENTS

5.6 List Consolidation Using OrderedList . . . . . . . . . . . . . . . . . . . . 205

5.6.1 Merger: A Utility Class . . . . . . . . . . . . . . . . . . . . . . . 205

5.6.2 A Consolidation Class . . . . . . . . . . . . . . . . . . . . . . . . 208

5.7 OrderedList Class Implementation . . . . . . . . . . . . . . . . . . . . . . 209

5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

5.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

6 Queue 223

6.1 Queue Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

6.2 UNIX Print Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

6.3 A Queue Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

6.4 A PrintQueue Class Using Queue . . . . . . . . . . . . . . . . . . . . . . . 228

6.5 Queue Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 234

6.5.1 Design 1: Using Array-based Storage . . . . . . . . . . . . . . . . 234

6.5.2 Design 2: Using Linked List . . . . . . . . . . . . . . . . . . . . . 237

6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

6.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

7 Stack 245

7.1 Stack Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

7.2 Stack Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

7.2.1 Parentheses Matching . . . . . . . . . . . . . . . . . . . . . . . . 247

7.2.2 Postfix Expression Evaluation . . . . . . . . . . . . . . . . . . . . 248

7.2.3 Infix to Postfix Conversion . . . . . . . . . . . . . . . . . . . . . . 251

7.3 A Stack Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

CONTENTS vii

7.4 A Postfix Expression Evaluation Package . . . . . . . . . . . . . . . . . . 252

7.4.1 Class PostfixEvaluator . . . . . . . . . . . . . . . . . . . . . . . . 254

7.4.2 Class StatusKeeper . . . . . . . . . . . . . . . . . . . . . . . . . . 256

7.4.3 Class StackKeeper . . . . . . . . . . . . . . . . . . . . . . . . . . 257

7.4.4 Class PostfixEvaluator Implementation . . . . . . . . . . . . . . . 260

7.5 Stack Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 262

7.5.1 Design 1: Array List for Storage . . . . . . . . . . . . . . . . . . . 262

7.5.2 Design 2: Linked List for Storage . . . . . . . . . . . . . . . . . . 263

7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

7.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

8 Recursion 271

8.1 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.1.1 List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.1.2 Ordered List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

8.1.3 Factorial Function . . . . . . . . . . . . . . . . . . . . . . . . . . 275

8.1.4 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . 275

8.2 Recursive Programs and Backing Out . . . . . . . . . . . . . . . . . . . . 276

8.2.1 Computing the Factorial . . . . . . . . . . . . . . . . . . . . . . . 277

8.2.2 Computing the Fibonacci Sequence . . . . . . . . . . . . . . . . . 279

8.2.3 Recursion with Linked Lists . . . . . . . . . . . . . . . . . . . . . 280

8.3 Recursion On An Array: Binary Search . . . . . . . . . . . . . . . . . . . 282

8.4 Towers of Hanoi: An Application . . . . . . . . . . . . . . . . . . . . . . 283

8.4.1 A Recursive Definition . . . . . . . . . . . . . . . . . . . . . . . . 284

8.4.2 A Recursive Program . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.5 Recursion and Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

viii CONTENTS

8.6 Drawbacks of Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

8.7 Tail Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

8.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

9 Binary Tree and General Tree 299

9.1 Binary Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

9.1.1 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

9.1.2 Position as Meaning . . . . . . . . . . . . . . . . . . . . . . . . . 301

9.1.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

9.1.4 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 304

9.2 Binary Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

9.3 A BinaryTree Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

9.4 Storing and Recreating a Binary Tree . . . . . . . . . . . . . . . . . . . . . 312

9.4.1 Signature of a Binary Tree . . . . . . . . . . . . . . . . . . . . . . 313

9.4.2 Building a Binary Tree From Its Signature . . . . . . . . . . . . . . 314

9.5 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

9.5.1 Statistical and Dictionary Coding . . . . . . . . . . . . . . . . . . 318

9.5.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

9.5.3 Average Code Length and Prefix Property . . . . . . . . . . . . . . 320

9.5.4 A Huffman Class Using BinaryTree . . . . . . . . . . . . . . . . . 321

9.6 BinaryTree Class Implementation . . . . . . . . . . . . . . . . . . . . . . 329

9.7 Stack-based Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

9.7.1 Inorder Traversal of Binary Tree . . . . . . . . . . . . . . . . . . . 333

9.7.2 A Visitor Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

9.8 General Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

CONTENTS ix

9.8.1 Example: Hierarchy in a University . . . . . . . . . . . . . . . . . 335

9.8.2 Example: UNIX Filesystem . . . . . . . . . . . . . . . . . . . . . 336

9.8.3 Space Issues in Implementation . . . . . . . . . . . . . . . . . . . 337

9.8.4 Correspondence with Binary Tree . . . . . . . . . . . . . . . . . . 338

9.8.5 Signature of General Tree . . . . . . . . . . . . . . . . . . . . . . 340

9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

9.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

9.11 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

10 Binary Search Tree and AVL Tree 351

10.1 Comparison Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

10.1.1 Search Time Using Comparison Tree . . . . . . . . . . . . . . . . 353

10.1.2 Height of Comparison Tree . . . . . . . . . . . . . . . . . . . . . . 355

10.2 Binary Search Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . 356

10.3 Binary Search Tree Operations . . . . . . . . . . . . . . . . . . . . . . . . 358

10.3.1 Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

10.3.2 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

10.3.3 Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

10.4 A BinarySearchTree Class . . . . . . . . . . . . . . . . . . . . . . . . . . 362

10.5 Using Class BinarySearchTree . . . . . . . . . . . . . . . . . . . . . . . . 364

10.5.1 Example: Treesort . . . . . . . . . . . . . . . . . . . . . . . . . . 365

10.5.2 Example: Counting Keys . . . . . . . . . . . . . . . . . . . . . . . 366

10.6 BinarySearchTree Class Implementation . . . . . . . . . . . . . . . . . . . 367

10.6.1 Search Implementation . . . . . . . . . . . . . . . . . . . . . . . . 368

10.6.2 Insert Implementation . . . . . . . . . . . . . . . . . . . . . . . . 369

10.6.3 Delete Implementation . . . . . . . . . . . . . . . . . . . . . . . . 370

10.6.4 Convenience Methods and Traversals . . . . . . . . . . . . . . . . 373

x CONTENTS

10.7 AVL Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374

10.7.1 AVL Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 374

10.7.2 Search, Insert, Delete Overview . . . . . . . . . . . . . . . . . . . 376

10.7.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376

10.7.4 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

10.7.5 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

10.7.6 Running Times of AVL Tree Operations . . . . . . . . . . . . . . . 385

10.7.7 AVL Insert and Delete: Generalization . . . . . . . . . . . . . . . . 385

10.8 Binary Search: Average Number of Comparisons . . . . . . . . . . . . . . 389

10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

10.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

10.11Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

11 Heap 401

11.1 Heap as Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

11.2 Heap Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

11.2.1 Max and Min Heaps . . . . . . . . . . . . . . . . . . . . . . . . . 403

11.3 Heap Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

11.3.1 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

11.3.2 Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

11.4 A Heap Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

11.5 Priority Scheduling with Heap . . . . . . . . . . . . . . . . . . . . . . . . 408

11.5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

11.5.2 A Scheduling Package using Heap . . . . . . . . . . . . . . . . . . 410

11.6 Sorting with the Heap Class . . . . . . . . . . . . . . . . . . . . . . . . . 417

11.6.1 Example: Sorting Integers . . . . . . . . . . . . . . . . . . . . . . 418

11.7 Heap Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 419

CONTENTS xi

11.7.1 Array Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419

11.7.2 Implementation using ArrayList . . . . . . . . . . . . . . . . . . . 422

11.8 Updatable Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425

11.8.1 Designing an Updatable Heap . . . . . . . . . . . . . . . . . . . . 425

11.8.2 Handles to heap entries . . . . . . . . . . . . . . . . . . . . . . . . 425

11.8.3 Shared handle array . . . . . . . . . . . . . . . . . . . . . . . . . . 426

11.8.4 Encapsulating handles within heap . . . . . . . . . . . . . . . . . . 427

11.8.5 Recycling free handle space . . . . . . . . . . . . . . . . . . . . . 427

11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

11.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

11.11Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

12 Hash Table 433

12.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434

12.2 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

12.3 Collision Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436

12.3.1 Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437

12.3.2 Quadratic Probing . . . . . . . . . . . . . . . . . . . . . . . . . . 439

12.3.3 Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

12.3.4 Comparison of Runnning Times . . . . . . . . . . . . . . . . . . . 441

12.4 The java.util.HashMap Class . . . . . . . . . . . . . . . . . . . . . . . . . 442

12.4.1 Table and Load Factor . . . . . . . . . . . . . . . . . . . . . . . . 443

12.4.2 Storage of Entries . . . . . . . . . . . . . . . . . . . . . . . . . . . 444

12.4.3 Adding an Entry . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

12.4.4 Rehashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448

12.4.5 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449

12.5 Quadratic Probing: Repetition of Probe Locations . . . . . . . . . . . . . . 450

xii CONTENTS

12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450

12.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

12.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453

13 Sorting 455

13.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

13.2 Sorting by Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . 459

13.2.1 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

13.2.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466

13.3 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468

13.3.1 Building a Heap in Linear Time . . . . . . . . . . . . . . . . . . . 469

13.3.2 Sorting a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

13.4 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

13.5 Implementation: A Quicksort Class . . . . . . . . . . . . . . . . . . . . . 474

13.6 Heap Build: Linear Running Time . . . . . . . . . . . . . . . . . . . . . . 477

13.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478

13.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

13.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483

14 Graphs I: Algorithms 485

14.1 Modeling Relationships using Graphs . . . . . . . . . . . . . . . . . . . . 486

14.1.1 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 486

14.1.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

14.1.3 Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 490

14.2 Graph Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

14.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

14.3.1 Depth-first Search for Undirected Graphs . . . . . . . . . . . . . . 494

CONTENTS xiii

14.3.2 Breadth-first Search for Undirected Graphs . . . . . . . . . . . . . 495

14.3.3 Traversal Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . 497

14.3.4 Traversals for Directed Graphs . . . . . . . . . . . . . . . . . . . . 498

14.4 Topological Sort on a Directed Graph . . . . . . . . . . . . . . . . . . . . 499

14.4.1 Partial and Total Order . . . . . . . . . . . . . . . . . . . . . . . . 500

14.4.2 Topological Numbering . . . . . . . . . . . . . . . . . . . . . . . 501

14.4.3 Topological Sorting Using Depth-first Search . . . . . . . . . . . . 502

14.4.4 Topological Sorting Using Breadth-first Search . . . . . . . . . . . 503

14.5 Connected Components of an Undirected Graph . . . . . . . . . . . . . . . 504

14.6 Shortest Paths in a Weighted Directed Graph . . . . . . . . . . . . . . . . . 505

14.6.1 Dijkstra’s Single-Source Algorithm . . . . . . . . . . . . . . . . . 506

14.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513

14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

15 Graphs II: Implementation 519

15.1 A Directed Graph Class: DirGraph . . . . . . . . . . . . . . . . . . . . . . 520

15.1.1 Vertex numbering . . . . . . . . . . . . . . . . . . . . . . . . . . . 520

15.1.2 Neighbor class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522

15.1.3 Exercising the DirGraph Class . . . . . . . . . . . . . . . . . . . . 524

15.2 An Undirected Graph Class: UndirGraph . . . . . . . . . . . . . . . . . . 525

15.3 A Depth-first Search Class: DFS . . . . . . . . . . . . . . . . . . . . . . . 527

15.3.1 Design and Interface . . . . . . . . . . . . . . . . . . . . . . . . . 528

15.3.2 Visitor Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

15.3.3 DFS Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 531

15.4 A Topological Sort Class: DFSTopsort . . . . . . . . . . . . . . . . . . . . 532

15.4.1 TopVisitor: Extending the Visitor Class . . . . . . . . . . . . . . . 532

15.4.2 DFSTopsort Implementation . . . . . . . . . . . . . . . . . . . . . 534

xiv CONTENTS

15.5 A Connected Components Class: DFSConncomp . . . . . . . . . . . . . . 534

15.5.1 ConnVisitor: Extending the Visitor Class . . . . . . . . . . . . . . 535

15.5.2 DFSConncomp Implementation . . . . . . . . . . . . . . . . . . . 536

15.6 A Shortest Paths Class: ShortestPaths . . . . . . . . . . . . . . . . . . . . 536

15.6.1 WeightedNeighbor: Extending the Neighbor Class . . . . . . . . . 538

15.6.2 ShortestPaths Implementation . . . . . . . . . . . . . . . . . . . . 538

15.7 Graph Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

15.7.1 DirGraph Implementation . . . . . . . . . . . . . . . . . . . . . . 543

15.7.2 UndirGraph Class Implementation . . . . . . . . . . . . . . . . . . 548

15.7.3 Implementation of Weighted Graphs . . . . . . . . . . . . . . . . . 549

15.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549

15.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550

Purchase Info ?

With CourseSmart eTextbooks and eResources, you save up to 60% off the price of new print textbooks, and can switch between studying online or offline to suit your needs.

Once you have purchased your eTextbooks and added them to your CourseSmart bookshelf, you can access them anytime, anywhere.

Buy Access

Data Structures Outside-In with Java, CourseSmart eTextbook
Format: Safari Book

$48.99 | ISBN-13: 978-0-13-242928-3