Data Structures
John Wiley & Sons Inc (Verlag)
978-1-119-00023-5 (ISBN)
- Titel ist leider vergriffen;
keine Neuauflage - Artikel merken
Preface iii
Chapter 1 Object–Oriented Programming and Class Hierarchies 1
1.1 ADTs, Interfaces, and the Java API 2
Interfaces 3
The implements Clause 6
Declaring a Variable of an Interface Type 7
Exercises for Section 1.1 7
1.2 Introduction to Object–Oriented Programming 8
A Superclass and Subclass Example 9
Use of this 10
Initializing Data Fields in a Subclass 11
The No–Parameter Constructor 12
Protected Visibility for Superclass Data Fields 13
Is–a Versus Has–a Relationships 13
Exercises for Section 1.2 14
1.3 Method Overriding, Method Overloading, and Polymorphism 14
Method Overriding 14
Method Overloading 16
Polymorphism 19
Methods with Class Parameters 20
Exercises for Section 1.3 20
1.4 Abstract Classes 21
Referencing Actual Objects 24
Initializing Data Fields in an Abstract Class 24
Abstract Class Number and the Java Wrapper Classes 24
Summary of Features of Actual Classes, Abstract Classes, and Interfaces 25
Implementing Multiple Interfaces 26
Extending an Interface 26
Exercises for Section 1.4 27
1.5 Class Object and Casting 27
The Method to String 28
Operations Determined by Type of Reference Variable 28
Casting in a Class Hierarchy 29
Using instance of to Guard a Casting Operation 31
The Class Class 33
Exercises for Section 1.5 33
1.6 A Java Inheritance Example—The Exception Class Hierarchy 34
Division by Zero 34
Array Index Out of Bounds 35
Null Pointer 35
The Exception Class Hierarchy 36
The Class Throwable 36
Checked and Unchecked Exceptions 37
Handling Exceptions to Recover from Errors 39
Using try–catch to Recover from an Error 40
Throwing an Exception When Recovery Is Not Obvious 41
Exercises for Section 1.6 42
1.7 Packages and Visibility 42
Packages 42
The No–Package–Declared Environment 43
Package Visibility 43
Visibility Supports Encapsulation 44
Exercises for Section 1.7 45
1.8 A Shape Class Hierarchy 46
Case Study: Processing Geometric Figures 46
Exercises for Section 1.8 52
Chapter Review, Exercises, and Programming Projects 52
Chapter 2 Lists and the Collections Framework 61
2.1 The List Interface and ArrayList Class 62
The ArrayList Class 63
Generic Collections 66
Specification of the ArrayList Class 68
Exercises for Section 2.1 69
2.2 Applications of ArrayList 69
A Phone Directory Application 70
Exercises for Section 2.2 70
2.3 Implementation of an ArrayList Class 71
The Constructor for Class KWArrayList 72
The add(E anEntry) Method 73
The add(int index, E anEntry) Method 74
The set and get Methods 75
The remove Method 75
The reallocate Method 76
Implementing KWArray List as a Collection of Objects 76
The Vector Class 77
Exercises for Section 2.3 77
2.4 Algorithm Efficiency and Big–O 77
Big–O Notation 80
Formal Definition of Big–O 81
Summary of Notation 83
Comparing Performance 84
Algorithms with Exponential and Factorial Growth Rates 86
Performance of the KWArray List Algorithms 86
Exercises for Section 2.4 87
2.5 Single–Linked Lists 88
A List Node 90
Connecting Nodes 92
A Single–Linked List Class 92
Inserting a Node in a List 93
Removing a Node 93
Traversing a Single–Linked List 95
Completing the SingleLinked List Class 95
The get and set Methods 96
The add Methods 97
Exercises for Section 2.5 98
2.6 Double–Linked Lists and Circular Lists 99
Inserting into a Double–Linked List 101
Removing from a Double–Linked List 101
A Double–Linked List Class 102
Circular Lists 102
Exercises for Section 2.6 103
2.7 The Linked List Class and the Iterator, ListIterator, and
Iterable Interfaces 104
The LinkedList Class 104
The Iterator 105
The Iterator Interface 106
The ListIterator Interface 108
Comparison of Iterator and ListIterator 110
Conversion between a ListIterator and an Index 110
The Enhanced for Statement 110
The Iterable Interface 111
Exercises for Section 2.7 112
2.8 Implementation of a Double–Linked List Class 112
Implementing the KWLinkedList Methods 113
A Class that Implements the ListIterator Interface 114
The Constructor 114
The hasNext and next Methods 115
The hasPrevious and previous Methods 116
The add Method 117
Inner Classes: Static and Nonstatic 120
Exercises for Section 2.8 121
2.9 The Collections Framework Design 121
The Collection Interface 121
Common Features of Collections 122
The AbstractCollection, AbstractList, and
AbstractSequentialList Classes 123
The List and RandomAccess Interfaces (Advanced) 124
Exercises for Section 2.9 124
2.10 Application of the LinkedList Class 125
Case Study: Maintaining an Ordered List 125
Exercises for Section 2.10 130
2.11 Testing 130
Preparations for Testing 132
Testing Tips for Program Systems 133
Developing the Test Data 133
Testing Boundary Conditions 134
Stubs 136
Preconditions and Postconditions 137
Drivers 137
Using JUnit and Debuggers 138
Testing Class OrderedList 138
Case Study: Maintaining an Ordered List (continued) 138
Exercises for Section 2.11 140
Chapter Review, Exercises, and Programming Projects 141
Chapter 3 Stacks 149
3.1 Stack Abstract Data Type 150
Specification of the Stack Abstract Data Type 150
Exercises for Section 3.1 152
3.2 Stack Applications 153
Case Study: Finding Palindromes 153
Case Study: Testing Expressions for Balanced Parentheses 156
Exercises for Section 3.2 161
3.3 Implementing a Stack 162
Implementing a Stack as an Extension of Vector 162
Implementing a Stack with a List Component 163
Implementing a Stack Using an Array 165
Implementing a Stack as a Linked Data Structure 167
Comparison of Stack Implementations 169
Exercises for Section 3.3 169
3.4 Additional Stack Applications 170
Case Study: Evaluating Postfix Expressions 171
Case Study: Converting from Infix to Postfix 176
Case Study: Converting Expressions with Parentheses 185
Tying the Case Studies Together 188
Exercises for Section 3.4 188
Chapter Review, Exercises, and Programming Projects 189
Chapter 4 Queues 195
4.1 Queue Abstract Data Type 196
A Print Queue 196
The Unsuitability of a “Print Stack” 197
A Queue of Customers 197
Using a Queue for Traversing a Multi–Branch Data Structure 197
Specification for a Queue Interface 198
Class LinkedList Implements the Queue Interface 199
Exercises for Section 4.1 199
4.2 Maintaining a Queue of Customers 200
Case Study: Maintaining a Queue 200
Exercises for Section 4.2 205
4.3 Implementing the Queue Interface 206
Using a Double–Linked List to Implement the Queue Interface 206
Using a Single–Linked List to Implement the Queue Interface 207
Using a Circular Array to Implement the Queue Interface 209
Comparing the Three Implementations 216
Exercises for Section 4.3 217
4.4 The Deque Interface 217
Classes that Implement Deque 217
Using a Deque as a Queue 219
Using a Deque as a Stack 219
Exercises for Section 4.4 220
4.5 Simulating Waiting Lines Using Queues 221
Case Study: Simulate a Strategy for Serving Airline Passengers 221
Exercises for Section 4.5 236
Chapter Review, Exercises, and Programming Projects 237
Chapter 5 Recursion 243
5.1 Recursive Thinking 244
Steps to Design a Recursive Algorithm 246
Proving that a Recursive Method Is Correct 248
Tracing a Recursive Method 249
The Run–Time Stack and Activation Frames 249
Exercises for Section 5.1 251
5.2 Recursive Definitions of Mathematical Formulas 252
Recursion versus Iteration 255
Efficiency of Recursion 256
Exercises for Section 5.2 259
5.3 Recursive Array Search 259
Design of a Recursive Linear Search Algorithm 260
Implementation of Linear Search 260
Design of a Binary Search Algorithm 262
Efficiency of Binary Search 262
The Comparable Interface 263
Implementation of Binary Search 264
Testing Binary Search 265
Method Arrays.binarySearch 265
Exercises for Section 5.3 267
5.4 Recursive Data Structures 267
Recursive Definition of a Linked List 267
Class LinkedListRec 268
Removing a List Node 271
Exercises for Section 5.4 272
5.5 Problem Solving with Recursion 273
Case Study: Towers of Hanoi 273
Case Study: Counting Cells in a Blob 278
Exercises for Section 5.5 283
5.6 Backtracking 283
Case Study: Finding a Path through a Maze 284
Exercises for Section 5.6 288
Chapter Review, Exercises, and Programming Projects 289
Chapter 6 Trees 295
6.1 Tree Terminology and Applications 297
Tree Terminology 297
Binary Trees 298
Some Types of Binary Trees 298
Full, Perfect, and Complete Binary Trees 301
General Trees 301
Exercises for Section 6.1 303
6.2 Tree Traversals 304
Visualizing Tree Traversals 304
Traversals of Binary Search Trees and Expression Trees 305
Exercises for Section 6.2 306
6.3 Implementing a BinaryTree Class 307
The Node Class 307
The BinaryTree Class 308
Exercises for Section 6.3 314
6.4 Binary Search Trees 315
Overview of a Binary Search Tree 315
Performance 316
Interface SearchTree 317
The BinarySearchTree Class 317
Insertion into a Binary Search Tree 319
Removal from a Binary Search Tree 323
Testing a Binary Search Tree 328
Case Study: Writing an Index for a Term Paper 329
Exercises for Section 6.4 331
6.5 Heaps and Priority Queues 332
Inserting an Item into a Heap 333
Removing an Item from a Heap 333
Implementing a Heap 334
Priority Queues 337
The PriorityQueue Class 338
Using a Heap as the Basis of a Priority Queue 338
The Other Methods 341
Using a Comparator 342
The compare Method 342
Exercises for Section 6.5 344
6.6 Huffman Trees 345
Case Study: Building a Custom Huffman Tree 346
Exercises for Section 6.6 353
Chapter Review, Exercises, and Programming Projects 354
Chapter 7 Sets and Maps 361
7.1 Sets and the Set Interface 362
The Set Abstraction 363
The Set Interface and Methods 364
Comparison of Lists and Sets 366
Exercises for Section 7.1 366
7.2 Maps and the Map Interface 367
The Map Hierarchy 368
The Map Interface 369
Exercises for Section 7.2 371
7.3 Hash Tables 372
Hash Codes and Index Calculation 372
Methods for Generating Hash Codes 373
Open Addressing 374
Table Wraparound and Search Termination 375
Traversing a Hash Table 376
Deleting an Item Using Open Addressing 377
Reducing Collisions by Expanding the Table Size 377
Reducing Collisions Using Quadratic Probing 378
Problems with Quadratic Probing 378
Chaining 379
Performance of Hash Tables 380
Exercises for Section 7.3 382
7.4 Implementing the Hash Table 384
Interface KWHashMap 384
Class Entry 384
Class HashtableOpen 386
Class HashtableChain 391
Testing the Hash Table Implementations 394
Exercises for Section 7.4 395
7.5 Implementation Considerations for Maps and Sets 396
Methods hashCode and equals 396
Implementing HashSetOpen 396
Writing HashSetOpen as an Adapter Class 397
Implementing the Java Map and Set Interfaces 398
Nested Interface Map.Entry 398
Creating a Set View of a Map 399
Method entrySet and Classes EntrySet and SetIterator 399
Classes TreeMap and TreeSet 400
Exercises for Section 7.5 401
7.6 Additional Applications of Maps 401
Case Study: Implementing a Cell Phone Contact List 401
Case Study: Completing the Huffman Coding Problem 404
Exercises for Section 7.6 408
7.7 Navigable Sets and Maps 408
Application of a NavigableMap 410
Exercises for Section 7.7 412
Chapter Review, Exercises, and Programming Projects 413
Chapter 8 Sorting 419
8.1 Using Java Sorting Methods 420
Exercises for Section 8.1 424
8.2 Selection Sort 425
Analysis of Selection Sort 426
Code for Selection Sort 426
Exercises for Section 8.2 427
8.3 Bubble Sort 428
Analysis of Bubble Sort 429
Code for Bubble Sort 430
Exercises for Section 8.3 431
8.4 Insertion Sort 431
Analysis of Insertion Sort 433
Code for Insertion Sort 434
Exercises for Section 8.4 435
8.5 Comparison of Quadratic Sorts 435
Comparisons versus Exchanges 436
Exercises for Section 8.5 436
8.6 Shell Sort: A Better Insertion Sort 437
Analysis of Shell Sort 438
Code for Shell Sort 439
Exercises for Section 8.6 440
8.7 Merge Sort 441
Analysis of Merge 442
Code for Merge 442
Algorithm for Merge Sort 443
Trace of Merge Sort Algorithm 444
Analysis of Merge Sort 444
Code for Merge Sort 445
Exercises for Section 8.7 446
8.8 Heapsort 446
First Version of a Heapsort Algorithm 446
Revising the Heapsort Algorithm 447
Algorithm to Build a Heap 449
Analysis of Revised Heapsort Algorithm 449
Code for Heapsort 449
Exercises for Section 8.8 451
8.9 Quicksort 451
Algorithm for Quicksort 452
Analysis of Quicksort 452
Code for Quicksort 453
Algorithm for Partitioning 454
Code for partition 455
A Revised Partition Algorithm 457
Code for Revised partition Method 458
Exercises for Section 8.9 460
8.10 Testing the Sort Algorithms 460
Exercises for Section 8.10 462
8.11 The Dutch National Flag Problem (Optional Topic) 462
Case Study: The Problem of the Dutch National Flag 462
Exercises for Section 8.11 466
Chapter Review, Exercises, and Programming Projects 466
Chapter 9 Self–Balancing Search Trees 471
9.1 Tree Balance and Rotation 472
Why Balance Is Important 472
Rotation 473
Algorithm for Rotation 473
Implementing Rotation 475
Exercises for Section 9.1 476
9.2 AVL Trees 477
Balancing a Left–Left Tree 477
Balancing a Left–Right Tree 478
Four Kinds of Critically Unbalanced Trees 479
Implementing an AVL Tree 481
Inserting into an AVL Tree 483
Removal from an AVL Tree 489
Performance of the AVL Tree 489
Exercises for Section 9.2 489
9.3 Red–Black Trees 490
Insertion into a Red–Black Tree 491
Removal from a Red–Black Tree 501
Performance of a Red–Black Tree 502
The TreeMap and TreeSet Classes 502
Exercises for Section 9.3 502
9.4 2–3 Trees 503
Searching a 2–3 Tree 503
Inserting an Item into a 2–3 Tree 504
Analysis of 2–3 Trees and Comparison with Balanced Binary Trees 508
Removal from a 2–3 Tree 508
Exercises for Section 9.4 510
9.5 B–Trees and 2–3–4 Trees 510
B–Trees 510
Implementing the B–Tree 512
Code for the insert Method 514
The insert Into Node Method 515
The split Node Method 516
Removal from a B–Tree 518
B+ Trees 520
2–3–4 Trees 520
Relating 2–3–4 Trees to Red–Black Trees 522
Exercises for Section 9.5 524
9.6 Skip–Lists 525
Skip–List Structure 525
Searching a Skip–List 526
Performance of a Skip–List Search 526
Inserting into a Skip–List 526
Increasing the Height of a Skip–List 527
Implementing a Skip–List 527
Searching a Skip–List 528
Insertion 529
Determining the Size of the Inserted Node 530
Completing the Insertion Process 530
Performance of a Skip–List 530
Exercises for Section 9.6 531
Chapter Review, Exercises, and Programming Projects 531
Chapter 10 Graphs 541
10.1 Graph Terminology 542
Visual Representation of Graphs 542
Directed and Undirected Graphs 543
Paths and Cycles 544
Relationship between Graphs and Trees 546
Graph Applications 546
Exercises for Section 10.1 547
10.2 The Graph ADT and Edge Class 547
Exercises for Section 10.2 549
10.3 Implementing the Graph ADT 550
Adjacency List 550
Adjacency Matrix 550
Overview of the Hierarchy 552
Class AbstractGraph 552
The ListGraph Class 555
The MatrixGraph Class 558
Comparing Implementations 558
Exercises for Section 10.3 559
10.4 Traversals of Graphs 560
Breadth–First Search 560
Depth–First Search 565
Exercises for Section 10.4 572
10.5 Applications of Graph Traversals 573
Case Study: Shortest Path through a Maze 573
Case Study: Topological Sort of a Graph 577
Exercises for Section 10.5 580
10.6 Algorithms Using Weighted Graphs 580
Finding the Shortest Path from a Vertex to All Other Vertices 580
Minimum Spanning Trees 584
Exercises for Section 10.6 588
Chapter Review, Exercises, and Programming Projects 589
Appendix A Introduction to Java 597
A.1 The Java Environment and Classes 598
The Java Virtual Machine 599
The Java Compiler 599
Classes and Objects 599
The Java API 600
The import Statement 600
Method main 600
Execution of a Java Program 601
Exercises for Section A.1 602
A.2 Primitive Data Types and Reference Variables 602
Primitive Data Types 602
Primitive–Type Variables 603
Primitive–Type Constants 604
Operators 604
Postfix and Prefix Increment 604
Type Compatibility and Conversion 606
Referencing Objects 607
Creating Objects 607
Exercises for Section A.2 608
A.3 Java Control Statements 608
Sequence and Compound Statements 608
Selection and Repetition Control 609
Nested if Statements 610
The switch Statement 612
Exercises for Section A.3 613
A.4 Methods and Class Math 613
The Instance Methods println and print 613
Call–by–Value Arguments 614
The Class Math 615
Escape Sequences 616
Exercises for Section A.4 617
A.5 The String, StringBuilder, and StringBuffer Classes 617
The String Class 617
Strings Are Immutable 620
The Garbage Collector 620
Comparing Objects 621
The String.format Method 622
The Formatter Class 623
The String.split Method 624
Introduction to Regular Expressions 624
Matching One of a Group of Characters 624
Qualifiers 624
Defined Character Groups 625
Unicode Character Class Support 626
The StringBuilder and StringBuffer Classes 627
Exercises for Section A.5 628
A.6 Wrapper Classes for Primitive Types 629
Exercises for Section A.6 630
A.7 Defining Your Own Classes 631
Private Data Fields, Public Methods 635
Constructors 635
The No–Parameter Constructor 636
Modifier and Accessor Methods 636
Use of this in a Method 637
The Method to String 637
The Method equals 637
Declaring Local Variables in Class Person 639
An Application that Uses Class Person 639
Objects as Arguments 640
Classes as Components of Other Classes 642
Java Documentation Style for Classes and Methods 642
Exercises for Section A.7 644
A.8 Arrays 645
Data Field length 647
Method Arrays.copyOf 648
Method System.arrayCopy 648
Array Data Fields 649
Array Results and Arguments 651
Arrays of Arrays 651
Exercises for Section A.8 653
A.9 Input/Output Using Class JOptionPane 655
Converting Numeric Strings to Numbers 656
GUI Menus Using Method showOptionDialog 657
Exercises for Section A.9 657
A.10 Input/Output Using Streams and the Scanner Class 658
Input Streams 658
Console Input 658
Output Streams 659
Passing Arguments to Method main 659
Closing Streams 659
Exceptions 660
A Complete File–Processing Application 660
The Scanner 662
Tokenized Input 664
Extracting Tokens Using Scanner.findInLine 664
Exercises for Section A.10 665
A.11 Catching Exceptions 665
Catching and Handling Exceptions 666
Exercises for Section A.11 672
A.12 Throwing Exceptions 672
The throws Clause 672
The throw Statement 674
Exercises for Section A.12 678
Appendix Review, Exercises, and Programming Projects 679
Appendix B Overview of UML 685
B.1 The Class Diagram 686
Representing Classes and Interfaces 686
Generalization 689
Inner or Nested Classes 690
Association 690
Aggregation and Composition 691
Generic Classes 692
B.2 Sequence Diagrams 692
Time Axis 692
Objects 693
Life Lines 694
Activation Bars 694
Messages 694
Use of Notes 694
Appendix C Event–Oriented Programming 695
C.1 Elements of an Event–Oriented Application 696
Components and Events 697
Event Listeners 698
The ActionListener Interface 698
Registering an Event Listener 699
Creating a User Interface 700
Exercises for Section C.1 703
C.2 Overview of the AWT and Swing Hierarchy 704
Example and Overview: TwoCircles 705
JFrame 709
JPanel 710
Graphics 711
Graphics Coordinates 712
Exercises for Section C.2 712
C.3 Layout Managers 712
Border Layout 713
Flow Layout 715
Box Layout 716
Grid Layout 717
Combining Layouts 718
Exercises for Section C.3 719
C.4 Components for Data Entry 719
Check Box 720
Radio Button 721
Combo Box 723
Text Field 724
Label 726
Text Area 726
Exercises for Section C.4 726
C.5 Using Data Entry Components in a GUI 727
Case Study: Liquid Volume Converter 727
Limiting the Number of Significant Digits 732
Formatting Currency for Different Locales 733
Exercises for Section C.5 734
C.6 Menus and Toolbars 735
The Classes JMenuItem, JMenu, and JMenuBar 735
Icons 737
Toolbars 737
Case Study: A Drawing Application 739
Exercises for Section C.6 747
C.7 Processing Mouse Events 747
MouseAdapter and MouseMotionAdapter 748
Case Study: A Drawing Application (continued) 749
Exercises for Section C.7 757
Appendix Review, Exercises, and Programming Projects 757
Appendix D Testing and Debugging 763
D.1 Testing Using the JUnit Framework 764
D.2 Debugging a Program 767
Using a Debugger 769
D.3 Visualizing Data Structures 772
Glossary 775
Index 785
| Erscheint lt. Verlag | 14.3.2016 |
|---|---|
| Verlagsort | New York |
| Sprache | englisch |
| Gewicht | 666 g |
| Themenwelt | Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge |
| Informatik ► Software Entwicklung ► Objektorientierung | |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Mathematik / Informatik ► Informatik ► Web / Internet | |
| ISBN-10 | 1-119-00023-8 / 1119000238 |
| ISBN-13 | 978-1-119-00023-5 / 9781119000235 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
