Java Foundations

by Lewis, John; DePasquale, Peter; Chase, Joe

• ISBN13: 9780133370461
• ISBN10: 0133370461
• Edition: 3rd
• Format: Hardcover
• Copyright: 2013-02-26
• Publisher: Pearson

Summary

Inspired by the success of their best-selling introductory programming text, Java Software Solutions, authors Lewis, DePasquale, and Chase now release Java Foundations, Third Edition. This text is a comprehensive resource for instructors who want a two-or three-semester introduction to programming textbook that includes detail on data structures topics. Java Foundations introduces a Software Methodology early on and revisits it throughout to ensure students develop sound program development skills from the beginning. Control structures are covered before writing classes, providing a solid foundation of fundamental concepts and sophisticated topics.

Author Biography

John Lewis is the co-author of the best-selling introductory Java programming book Java Software Solutions , as well as Java Software Structures, Programming with Alice and Java , and books for AP computer science.  He teaches courses at both Virginia Tech and Radford University. He received his Ph.D. degree from Virginia Tech.

Peter DePasquale is an assistant professor of computer science at the College of New Jersey (TCNJ). He is the author of Addison-Wesley’s Java Backpack Reference Guide and Addison-Wesley’s C++ Backpack Reference Guide, as well as Programming with Alice and Java .

Joe Chase is an associate professor of computer science at Radford University. He is the co-author of Java Software Structures and Java Software Structures for AP* Computer Science AB.

Table of Contents

Preface vii

Chapter 1 Introduction 1

1.1 The Java Programming Language 2

A Java Program 3

Comments 5

Identifiers and Reserved Words 7

White Space 9

1.2 Program Development 11

Programming Language Levels 11

Editors, Compilers, and Interpreters 13

Development Environments 15

Syntax and Semantics 16

Errors 17

1.3 Problem Solving 18

1.4 Software Development Activities 20

1.5 Object-Oriented Programming 21

Object-Oriented Software Principles 22

 

Chapter 2 Data and Expressions 33

2.1 Character Strings 34

The print and println Methods 34

String Concatenation 36

Escape Sequences 40

2.2 Variables and Assignment 41

Variables 41

The Assignment Statement 44

Constants 46

2.3 Primitive Data Types 47

Integers and Floating Points 47

Characters 48

Booleans 50

2.4 Expressions 51

Arithmetic Operators 51

Operator Precedence 52

Increment and Decrement Operators 56

Assignment Operators 57

2.5 Data Conversion 58

Conversion Techniques 60

2.6 Reading Input Data 61

The Scanner Class 61

 

Chapter 3 Using Classes and Objects 75

3.1 Creating Objects 76

Aliases 78

3.2 The String Class 80

3.3 Packages 83

The import Declaration 84

3.4 The Random Class 86

3.5 The Math Class 89

3.6 Formatting Output 92

The NumberFormat Class 92

The DecimalFormat Class 94

The printf Method 96

3.7 Enumerated Types 97

3.8 Wrapper Classes 100

Autoboxing 102

 

Chapter 4 Conditionals and Loops 111

4.1 Boolean Expressions 112

Equality and Relational Operators 113

Logical Operators 114
4.2 The if Statement 116

The if-else Statement 119

Using Block Statements 121

The Conditional Operator 124

Nested if Statements 125

4.3 Comparing Data 127

Comparing Floats 127

Comparing Characters 127

Comparing Objects 128

4.4 The switch Statement 130

4.5 The while Statement 134

Infinite Loops 140

Nested Loops 141

Other Loop Controls 144

4.6 Iterators 145

Reading Text Files 146

4.7 The do Statement 148

4.8 The for Statement 151

Iterators and for Loops 156

Comparing Loops 157

 

Chapter 5 Writing Classes 169

5.1 Classes and Objects Revisited 170

Identifying Classes and Objects 171

Assigning Responsibilities 173

5.2 Anatomy of a Class 173

Instance Data 178

UML Class Diagrams 179

5.3 Encapsulation 181

Visibility Modifiers 182

Accessors and Mutators 183

5.4 Anatomy of a Method 188

The return Statement 194

Parameters 196

Local Data 197

Constructors Revisited 198

5.5 Static Class Members 199

Static Variables 199

Static Methods 200

5.6 Class Relationships 203

Dependency 203

Dependencies among Objects of the Same Class 204

Aggregation 206

The this Reference 211

5.7 Method Design 212

Method Decomposition 213

Method Parameters Revisited 218

5.8 Method Overloading 223

5.9 Testing 224

Reviews 225

Defect Testing 226

Unit Testing 227

Integration Testing 228

System Testing 228

Test-Driven Development 228

5.10 Debugging 229

Simple Debugging with print Statements 230

Debugging Concepts 230

 

Chapter 6 Graphical User Interfaces 245

6.1 GUI Elements 246

Frames and Panels 247

Buttons and Action Events 251

Determining Event Sources 253

6.2 More Components 256

Text Fields 257

Check Boxes 260

Radio Buttons 263

Sliders 267

Combo Boxes 272

Timers 277

6.3 Layout Managers 282

Flow Layout 285

Border Layout 288

Grid Layout 291

Box Layout 293

Containment Hierarchies 296

6.4 Mouse and Key Events 297

Mouse Events 297

Key Events 305

Extending Adapter Classes 310

6.5 Dialog Boxes 311

File Choosers 314

Color Choosers 316

6.6 Some Important Details 317

Borders 317

Tool Tips and Mnemonics 321

6.7 GUI Design 328

Chapter 7 Arrays 339

7.1 Array Elements 340

Overview of Arrays 341

7.2 Declaring and Using Arrays 341

Bounds Checking 344

Alternative Array Syntax 349

Initializer Lists 350

Arrays as Parameters 351

7.3 Arrays of Objects 351

7.4 Command-Line Arguments 361

7.5 Variable-Length Parameter Lists 363

7.6 Two-Dimensional Arrays 367

Multidimensional Arrays 370

 

Chapter 8 Inheritance 379

8.1 C reating Subclasses 380

The protected Modifier 385

The super Reference 386

Multiple Inheritance 390

8.2 Overriding Methods 391

Shadowing Variables 394

8.3 C lass Hierarchies 394

The Object Class 395

Abstract Classes 397

8.4 Visibility 399

8.5 Designing for Inheritance 401

Restricting Inheritance 402

 

Chapter 9 Polymorphism 411

9.1 Dynamic Binding 412

9.2 Polymorphism via Inheritance 413

9.3 Interfaces 425

Interface Hierarchies 430

The Comparable Interface 431

The Iterator Interface 431

9.4 Polymorphism via Interfaces 432

Event Processing 434

 

Chapter 10 Exceptions 441

10.1 Exception Handling 442

10.2 Uncaught Exceptions 443

10.3 The try-catch Statement 444

The finally Clause 447

10.4 Exception Propagation 448

10.5 The Exception Class Hierarchy 451

Checked and Unchecked Exceptions 455

10.6 I/O Exceptions 455

 

Chapter 11 Analysis of Algorithms 465

11.1 Algorithm Efficiency 466

11.2 Growth Functions and Big-Oh Notation 467

11.3 Comparing Growth Functions 469

11.4 Determining Time Complexity 471

Analyzing Loop Execution 471

Nested Loops 472

Method Calls 473

 

Chapter 12 Introduction to Collections–Stacks 479

12.1 Collections 480

Abstract Data Types 481

The Java Collections API 483

12.2 A Stack Collection 483

12.3 C rucial OO Concepts 485

Inheritance and Polymorphism 486

Generics 487

12.4 Using Stacks: Evaluating Postfix Expressions 488

Javadoc 496

12.5 Exceptions 497

12.6 A Stack ADT 498

12.7 Implementing a Stack: With Arrays 501

Managing Capacity 502

12.8 The ArrayStack Class 503

The Constructors 504

The push Operation 506

The pop Operation 508

The peek Operation 509

Other Operations 509

The EmptyCollectionException Class 510

Other Implementations 511

 

Chapter 13 Linked Structures–Stacks 519

13.1 References as Links 520

13.2 Managing Linked Lists 522

Accessing Elements 522

Inserting Nodes 523

Deleting Nodes 524

13.3 Elements without Links 525

Doubly Linked Lists 525

13.4 Stacks in the Java API 526

13.5 Using Stacks: Traversing a Maze 527

13.6 Implementing a Stack: With Links 536

The LinkedStack Class 536

The push Operation 540

The pop Operation 542

Other Operations 543

 

Chapter 14 Queues 549

14.1 A Conceptual Queue 550

14.2 Queues in the Java API 551

14.3 Using Queues: Code Keys 552

14.4 Using Queues: Ticket Counter Simulation 556

14.5 A Queue ADT 561

14.6 A Linked Implementation of a Queue 562

The enqueue Operation 564

The dequeue Operation 566

Other Operations 567

14.7 Implementing Queues: With Arrays 568

The enqueue Operation 572

The dequeue Operation 574

Other Operations 575

14.8 Double-Ended Queues (Deque) 575

 

Chapter 15 Lists 581

15.1 A List Collection 582

15.2 Lists in the Java Collections API 584

15.3 Using Unordered Lists: Program of Study 585

15.4 Using Indexed Lists: Josephus 595

15.5 A List ADT 597

Adding Elements to a List 598

15.6 Implementing Lists with Arrays 603

The remove Operation 605

The contains Operation 607

The add Operation for an Ordered List 608

Operations Particular to Unordered Lists 609

The addAfter Operation for an

Unordered List 609

15.7 Implementing Lists with Links 610

The remove Operation 611

 

Chapter 16 Iterators 619

16.1 What’s an Iterator? 620

Other Iterator Issues 622

16.2 Using Iterators: Program of Study Revisited 622

Printing Certain Courses 626

Removing Courses 627

16.3 Implementing Iterators: With Arrays 629

16.4 Implementing Iterators: With Links 631

 

Chapter 17 Recursion 637

17.1 Recursive Thinking 638

Infinite Recursion 638

Recursion in Math 639

17.2 Recursive Programming 640

Recursion versus Iteration 643

Direct versus Indirect Recursion 643

17.3 Using Recursion 644

Traversing a Maze 644

The Towers of Hanoi 652

17.4 Analyzing Recursive Algorithms 657

 

Chapter 18 Searching and Sorting 665

18.1 Searching 666

Static Methods 667

Generic Methods 667

Linear Search 668

Binary Search 670

Comparing Search Algorithms 672

18.2 Sorting 673

Selection Sort 676

Insertion Sort 678

Bubble Sort 680

Quick Sort 682

Merge Sort 686

18.3 Radix Sort 689

 

Chapter 19 Trees 699

19.1 Trees 700

Tree Classifications 701

19.2 Strategies for Implementing Trees 703

Computational Strategy for Array

Implementation of Trees 703

Simulated Link Strategy for Array

Implementation of Trees 703

Analysis of Trees

19.3 Tree Traversals 706

Preorder Traversal 706

Inorder Traversal 707

Postorder Traversal 707

Level-Order Traversal 708

19.4 A Binary Tree ADT 709

19.5 Using Binary Trees: Expression Trees 713

19.6 A Backpain Analyzer 725

19.7 Implementing Binary Trees with Links 729

The find Method 734

The iteratorInOrder Method 736

 

Chapter 20 Binary Search Trees 743

20.1 A Binary Search Tree 744

20.2 Implementing Binary Search Trees: With Links 746

The addElement Operation 747

The removeElement Operation 750

The removeAllOccurrences Operation 753

The removeMin Operation 754

Implementing Binary Search Trees: With Arrays 756

20.3 Using Binary Search Trees: Implementing

Ordered Lists 756

Analysis of the BinarySearchTreeList

Implementation 759

20.4 Balanced Binary Search Trees 760

Right Rotation 761

Left Rotation 762

Rightleft Rotation 763

Leftright Rotation 763

20.5 Implementing Binary Search Trees: AVL Trees 764

Right Rotation in an AVL Tree 765

Left Rotation in an AVL Tree 765

Rightleft Rotation in an AVL Tree 765

Leftright Rotation in an AVL Tree 767

20.6 Implementing Binary Search Trees: Red/Black Trees 767

Insertion into a Red/Black Tree 768

Element Removal from a Red/Black Tree 771

 

Chapter 21 Heaps and Priority Queues 781

21.1 A Heap 782

The addElement Operation 784

The removeMin Operation 785

The findMin Operation 786

21.2 Using Heaps: Priority Queues 786

The addElement Operation 790

The removeMin Operation 794

The findMin Operation 797

21.4 Implementing Heaps: With Arrays 797

The addElement Operation 799

The removeMin Operation 800

The findMin Operation 802

21.5 Using Heaps: Heap Sort 802

 

Chapter 22 Sets and Maps 809

22.1 Set and Map Collections 810

22.2 Sets and Maps in the Java API 810

22.3 Using Sets: Domain Blocker 813

22.4 Using Maps: Product Sales 816

22.5 Using Maps: User Management 820

22.6 Implementing Sets and Maps Using Trees 825

22.7 Implementing Sets and Maps Using Hashing 825

 

Chapter 23 Multi-way Search Trees 833

23.1 Combining Tree Concepts 834

23.2 2-3 Trees 834

Inserting Elements into a 2-3 Tree 835

Removing Elements from a 2-3 Tree 837

23.3 2-4 Trees 840

23.4 B-Trees 842

B*-Trees 843

B+-Trees 843

Analysis of B-Trees 844

23.5 Implementation Strategies for B-Trees 844

 

Chapter 24 Graphs 1

24.1 Undirected Graphs 2

24.2 Directed Graphs 3

24.3 Networks 5

24.4 Common Graph Algorithms 6

Traversals 6

Testing for Connectivity 10

Minimum Spanning Trees 12

Determining the Shortest Path 15

24.5 Strategies for Implementing Graphs 15

Adjacency Lists 16

Adjacency Matrices 16

24.6 Implementing Undirected Graphs with an

Adjacency Matrix 17

The addEdge Method 22

The addVertex Method 22

The expandCapacity Method 23

Other Methods 24

 

Chapter 25 Databases 781

25.1 Introduction to Databases 782

25.2 Establishing a Connection to a Database 784

Obtaining a Database Driver 784

25.3 Creating and Altering Database Tables 787

Create Table 787

Alter Table 788

Drop Column 789

25.4 Querying the Database 789

Show Columns 790

25.5 Inserting, Viewing, and Updating Data 792

Insert 793

SELECT . . . FROM 793

Update 798

25.6 Deleting Data and Database Tables 799

Deleting Data 799

Deleting Database Tables 800

 

Appendix A         Glossary 905

Appendix B Number Systems 939

Place Value 940

Bases Higher Than 10 941

Conversions 942

Shortcut Conversions 945

Appendix C         The Unicode Character Set 951

Appendix D Java Operators 955

Java Bitwise Operators 957

Appendix E Java Modifiers 961

Java Visibility Modifiers 962

A Visibility Example 962

Other Java Modifiers 963

Appendix F         Java Graphics 965

Coordinate Systems 966

Representing Color 966

Drawing Shapes 967

Polygons and Polylines 976

The Polygon Class 980

Appendix G Java Applets 985

Embedding Applets in HTML 988

More Applet Methods 988

GUIs in Applets 993

Appendix H Regular Expressions 1003

Appendix I Hashing 1005

I.1 A Hashing 1006

I.2 Hashing Functions 1007

The Division Method 1008

The Folding Method 1008

The Mid-Square Method 1009

The Radix Transformation Method 1009

The Digit Analysis Method 1009

The Length-Dependent Method 1010

Hashing Functions in the Java Language 1010

I.3 Resolving Collisions 1010

Chaining 1011

Open Addressing 1012

I.4 Deleting Elements from a Hash Table 1015

Deleting from a Chained Implementation 1015

Deleting from an Open Addressing

Implementation 1016

I.5 Hash Tables in the Java Collections API 1017

The Hashtable Class 1017

The HashSet Class 1019

The HashMap Class 1019

The IdentityHashMap Class 1020

I.6 The WeakHashMap Class 1021

LinkedHashSet and LinkedHashMap 1022

Appendix J Java Syntax 1029

Index 1043