상세정보

Data Structures and Problem Solving Using Java teaches data structures and algorithms from the perspective of abstract thinking and problem solving. In this text, experienced author and educator Mark Allen Weiss takes a unique approach by clearly separating the specification and implementation of data structures. Dr. Weiss presents the interface and running time of data structures in Part II of the book. Then, he provides the opportunity for students to use the data structures in a variety of practical examples before introducing the implementations in Part IV. By first gaining a familiarity with the interfaces and uses of data structures, readers will be able to think more abstractly about the subject matter. Features *Contains extensive sample code using Java 1.1, which is available over the Internet and has been tested and reviewed by a professional programmer for accuracy. *Provides an introduction to Java in Part I and also covers Graphical User Interfaces (GUI's) in an appendix. *Includes pedagogical aids such as margin notes and comprehensive end-of-chapter material to help readers grasp challenging concepts.* Offers flexibility in topic coverage by minimizing dependencies among the different chapters. 0201549913B04062001

정보제공 :

CONTENTS

Part Ⅰ : Tour of Java

 CHAPTER 1 Primitive Java = 3

  1.1 The General Environment = 3

  1.2 The First Program = 5

   1.2.1 Comments 5

   1.2.2 main = 6

   1.2.3 Terminal Output = 6

  1.3 Primitive Types = 6

   1.3.1 The Primitive Types = 6

   1.3.2 Constants = 7

   1.3.3 Declaration and Initialization Of Primitive types = 7

   1.3.4 Terminal Input and Ourput = 8

  1.4 Basic Operators = 8

   1.4.1 Assignment Operators = 10

   1.4.2 Binary Arithmetic Operators = 10

   1.4.3 Unary Operators = 10

   1.4.4 Type Conversions = 10

  1.5 Conditional Statements = 11

   1.5.1 Relational and Equality Operators = 11

   1.5.2 Logical Operators = 12

   1.5.3 The if Statement 13

   1.5.4 The while statement = 13

   1.5.5 The for Statement = 14

   1.5.6 The do Statement = 15

   1.5.7 break and continue = 16

   1.5.8 The switch Statement = 17

   1.5.9 The Conditional Operator = 17

  1.6 Methods 18

   1.6.1 Overloading of Method Names = 19

   1.6.2 Storage Classes = 20

  Summary = 20

  Objects of the Game = 20

  Common Errors = 22

  On the Internet = 23

  Exercises = 23

  References = 25

 CHAPTER 2 References = 27

  2.1 What Is a Reference? = 27

  2.2 Backs of Objects and References = 29

   2.2.1 The Dot Operator (.) = 30

   2.2.2 Declaration of Objects = 30

   2.2.3 Garbage Collection = 31

   2.2.4 The Meaning of = 31

   2.2.5 Parameter Passing = 32

   2.2.6. The Meaning of = 33

   2.2.7 Operator Overloading for Objects = 33

  2.3 Strings = 33

   2.3.1 Basics of String Manipulation = 34

   2.3.2 String Concatenation = 34

   2.3.3 Comparing Strings = 35

   2.3.4 Pther String Methods = 35

   2.3.5 Converting between Strings and Primitive Types = 35

  2.4 Arrays = 36

   2.4.1 Declaration, Assignment, and Methods = 35

   2.4.2 Dynamic Array Expansion = 39

   2.4.3 Multidimensional Arrays = 41

   2.4.4 Command-line Arguments = 41

  2.5 Exception Handling = 42

   2.5.1 Processing Exceptions = 42

   2.5.2 The finally Clause = 43

   2.5.3 Common Exceptions = 43

   2.5.4 The throw and Throw Clauses = 44

  2.6 Input and Output = 45

   2.6.1 Basic Stream Operations = 46

   2.6.2 The StringTokenizer Object = 46

   2.6.3 Sequential Files = 47

  Summary = 49

  Objects of the Game = 49

  Common Errors = 51

  On the Internet = 51

  Exercises = 51

  References = 52

 CHAPTER 3 Objects and Classes = 53

  3.1 What Is Object-oriented Programming? = 53

  3.2 A Simple Example = 55

  3.3 Javadoc = 57

  3.4 Basic Methods = 58

   3.4.1 Constructors = 58

   3.4.2 Mutators and Accessors = 60

   3.4.3 Output and toString = 60

   3.4.4 equals = 62

   3.4.5 static Methods = 62

   3.4.6 main = 62

  3.5 Packages = 62

   3.5.1 The import Directive = 63

   3.5.2 The package Statement = 64

   3.5.3 The CLASSPATH Environment Variable = 65

   3.5.4 Package-friendly Visibility Rules = 66

   3.5.5 Separate Compilation = 66

  3.6 Additional Constructs = 66

   3.6.1 The this Reference = 66

   3.6.2 The this Shorthand for Constructors = 67

   3.6.3 The instanceof Operator = 68

   3.6.4 Static Fields = 68

   3.6.5 Static Initializers = 69

  Summary = 70

  Objects of the Game = 70

  Common Errors = 71

  On the Internet = 72

  Exercises = 72

  References = 74

 CHAPTER 4 Inheritance = 75

  4.1 What Is Inheritance? = 75

  4.2 Basic Java Syntax = 78

   4.2.1 Visibility Rules = 79

   4.2.2 The Constructor and Super = 79

   4.2.3 final Methods and Classes = 80

   4.2.4 Overriding a Method = 81

   4.2.5 Abstract Methods and Classes = 82

  4.3 Example : Expanding the Shape Class = 84

   4.3.1 Digression : An Introduction to Sorting = 86

  4.4 Multiple Inheritance = 90

  4.5 The Interface = 90

   4.5.1 Specifying an Interface = 91

   4.5.2 Implementing an Interface = 91

   4.5.3 Multiple Interfaces = 94

  4.6 Implementing Generic Components = 94

  Summary = 97

  Objects of the Game = 98

  Common Errors = 99

  On the Internet = 100

  Exercises = 100

  References = 102

Part Ⅱ : Algorithms and Building Blocks

 CHAPTER 5 Algorithm Analysis = 107

  5.1 What Is Algorithm Analysis? = 107

  5.2 Examples of Algorithm Running Times = 111

  5.3 The Maximum Contiguous Subsequence Sum Problem = 113

   5.3.1 The Obvious O(N³) Algorithm = 114

   5.3.2 An Improved O(N²) Algorithm = 117

   5.3.3 A Linear Algorithm = 118

  5.4 General Big-Oh Rules = 121

  5.5 The Logarithm = 124

  5.6 Static Searching Problem = 127

   5.6.1 Sequential Search = 127

   5.6.2 Binary Search = 128

   5.6.3 Interpolation Search = 129

  5.7 Checking an Algorithm Analysis = 131

  5.8 Limitations of Big-Oh Analysis = 133

  Summary = 133

  Objects of the Game = 134

  Common Errors = 134

  On the Internet = 135

  Exercises = 135

  References = 139

 CHAPTER 6 Data Structures = 143

  6.1 Why do We Need Data Structures? = 143

  6.2 Stacks = 145

   6.2.1 Stacks ad Computer Languages = 147

  6.3 Queues = 148

  6.4 Linked Lists = 150

  6.5 General Trees = 155

  6.6 Binary Search Trees = 157

  6.7 Hash Tables = 161

  6.8 Priority Queues = 163

  Summary = 166

  Objects of the Game = 167

  Common Errors = 168

  On the Internet = 168

  Exercises = 169

  References = 172

 CHAPTER 7 Recursion = 173

  7.1 What Is Recursion? = 173

  7.2 Background : Proofs by Mathematical Induction = 174

  7.3 Basic Recursion = 177

   7.3.1 Printing Numbers in Any Base = 179

   7.3.2 Why It Works = 180

   7.3.3 How It Works = 182

   7.3.4 Too Much Recursion Can Be Dangerous = 183

   7.3.5 Additional Examples = 185

  7.4 Numerical Applications = 189

   7.4.1 Modular Arithmetic = 190

   7.4.2 Modular Exponentiation = 190

   7.4.3 Greatest Common Divisor and Multiplicative Inverses = 192

   7.4.4 The RSA Cryptosystem = 194

  7.5 Divide-and-Conquer Algorithms = 197

   7.5.1 The Maximum Contiguous Subsequence Sum Problem = 197

   7.5.2 Analysis of a Basic Divide-and-Conquer Recurrence = 199

   7.5.3 A General Upper Bound for Divide-and-Conquer Running Times = 204

  7.6 Dynamic Programming = 207

  7.7 Backtracking Algorithms = 211

  Summary = 214

  Objects of the Game = 215

  Common Errors = 217

  On the Internet = 217

  Exercises = 218

  References = 221

 CHAPTER 8 Sorting Algorithms = 223

  8.1 Why Is Sorting Important? 223

  8.2 Preliminaries = 225

  8.3 Analysis of the Insertion Sort and Other Simple Sorts = 225

  8.4 Shellsort = 227

   8.4.1 Performance of Shellsort = 229

  8.5 Mergesort = 231

   8.5.1 Linear-time Merging of Sorted Arrays = 231

   8.5.2 The Mergesort Algorithm = 234

  8.6 Quicksort = 235

   8.6.1 The Quicksort Algorithm = 235

   8.6.2 Analysis of Quicksort = 236

   8.6.3 Picking the Pivot = 240

   8.6.4 A Partitioning Strategy = 241

   8.6.5 Keys Equal to the Pivot = 244

   8.6.6 Median-of-three Partitioning = 244

   8.6.7 Small Arrays = 245

   8.6.8 Java Quicksort Routine = 246

  8.7 Quickselect = 248

  8.8 A Lower Bound for Sorting = 250

  Summary = 251

  Objects of the Game = 251

  Common Errors = 252

  On the Internet = 252

  Exercises = 253

  References = 256

 CHAPTER 9 Randomization = 259

  9.1 Why Do We Need Random Numbers? = 259

  9.2 Random-number Generators = 260

  9.3 Nonuniform Random Numbers = 265

  9.4 Generating a Random Permutation = 268

  9.5 Randomized Algorithms = 269

  9.6 Randomized Primality Testing = 271

  Summary = 275

  Objects of the Game = 275

  Common Errors = 276

  On the Internet = 277

  Exercises = 277

  References = 279

Part Ⅲ : Applications

 CHAPTER 10 Fun and Games = 283

  10.1 Word Search Puzzles = 283

   10.1.1 Theory = 283

   10.1.2 Java Implementation = 288

  10.2 The Game of Tic-Tac-Toe = 292

   10.2.1 Alpha-beta Pruning = 292

   10.2.2 Transposition Tables = 293

   10.2.3 Computer Chess = 298

  Summary = 299

  Objects of the Game = 299

  Common Errors = 300

  On the Internet = 300

  Exercises = 300

  References = 302

 CHAPTER 11 Stacks and Compilers = 303

  11.1 Balanced-symbol Checker = 303

   11.1.1 Basic Algorithm = 303

   11.1.2 Implementation 306

  11.2 A Simple Calculator = 313

   11.2.1 Postfix Machines = 314

   11.2.2 Infix to Postfix Conversion = 316

   11.2.3 Implementation = 318

   11.2.4 Expression Trees = 326

  Summary = 327

  Objects of the Game = 327

  Common Errors = 328

  On the Internet = 328

  Exercises = 329

  References = 330

 CHAPTER 12 Utilities = 331

  12.1 File Compression = 331

   12.1.1 Prefix Codes = 332

   12.1.2 Huffman's Algorithm = 334

   12.1.3 The Encoding Phase = 337

   12.1.4 Decoding Phase = 337

   12.1.5 Practical Considerations = 338

  12.2 A Cross-reference Generator = 338

   12.2.1 Basic Ideas = 339

   12.2.2 Java Implementation = 339

  Summary = 343

  Objects of the Game = 345

  Common Errors = 345

  On the Internet = 345

  Exercises = 345

  References = 348

 CHAPTER 13 Simulation = 349

  13.1 The Josephus Problem = 349

   13.1.1 The Simple Solution = 350

   13.1.2 A More Efficient Algorithm = 352

  13.2 Event-driven Simulation = 354

   13.2.1 Basic Ideas = 354

   13.2.2 Example : A Modem back Simulation = 356

  Summary = 363

  Objects of the Game = 363

  Common Errors = 364

  On the Internet = 364

  Exercises = 364

  References = 364

 CHAPTER 14 Graphs and Paths = 367

  14.1 Definitions = 367

   14.1.1 Representation = 369

  14.2 Unweighted Shortest-path Problem = 379

   14.2.1 Theory = 382

   14.2.2 Java Implementation = 386

  14.3 Positive-weighted, Shortest-path Problem = 387

   14.4.1 Theory = 393

   14.4.2 Java Implementation = 395

  14.5 Path Problems in Acyclic Graphs = 395

   14.5.1 Topological Sorting = 396

   14.5.2 Theory of the Acyclic Shortest-path Algorithm = 398

   14.5.3 Java Implementation = 399

   14.5.4 An Application : Critical-path Analysis = 399

  Summary = 403

  Objects of the Game = 403

  Common Errors = 405

  On the Internet = 405

  Exercises = 405

  References = 408

Part Ⅳ : Implementations

 CHAPTER 15 Stacks and Queues = 411

  15.1 Dynamic Array Implementations = 411

   15.1.1 Stacks = 411

   15.1.2 Queues = 416

  15.2 Linked-list Implementations = 421

   15.2.1 Stack = 422

   15.2.2 Queues = 426

  15.3 Comparison of the Two Methods = 428

  15.4 Double-ended Queues = 428

  Summary = 429

  Objects of the Game = 430

  Common Errors = 430

  On the Internet = 430

  Exercises = 430

 CHAPTER 16 Linked Lists = 433

  16.1 Basic Ideas = 433

   16.1.1 Header Nodes = 435

   16.1.2 Iterator Classes = 436

  16.2 Java Implementation = 437

  16.3 Doubly Linked Lists and Circular Linked Lists = 445

  16.4 Sorted Linked Lists = 447

  Summary = 450

  Objects of the Game = 450

  Common Errors = 450

  On the Internet = 451

  Exercises = 451

 CHAPTER 17 Trees = 455

  17.1 General Trees = 455

   17.1.1 Definitions = 455

   17.1.2 Implementation = 459

  17.2 Binary Trees = 463

  17.3 Recursion and tree468

  17.4 Tree traversal : Iterator Classes = 471

   17.4.1 Postorder Traversal = 474

   17.4.2 Inorder Traversal = 477

   17.4.3 Preorder traversal = 477

   17.4.4 Level-order Traversals = 481

  Summary = 483

  Objects of the Game = 483

  Common Errors = 484

  On the Internet = 484

  Exercises = 485

 CHAPTER 18 Binary Search Trees = 489

  18.1 Basic Ideas = 489

   18.1.1 The Operations = 490

   18.1.2 Java Implementation = 494

  18.2 Order Statistics = 500

   18.2.1 Java Implementation = 500

  18.3 Analysis of Binary Search Tree Operations = 504

  18.4 AVL Trees = 508

   18.4.1 Properties = 509

   18.4.2 Single Rotation = 511

   18.4.3 Double Rotation = 512

   18.4.4 Summary of AVA Insertion = 515

  18.5 Red-Black Trees = 517

   18.5.1 Bottom-up Insertion = 518

   18.5.2 Top-down Red-Black Trees = 520

   18.5.3 Java Implementation = 522

   18.5.4 Top-down Deletions = 526

  18.6 AA-Trees = 530

   18.6.1 Insertion = 532

   18.6.2 Deletion = 536

   18.6.3 Java Implementation = 537

  18.7 B-Tree = 540

  Summary = 545

  Objects of the Game = 546

  Common Errors = 547

  On the Internet = 547

  Exercises = 548

  References = 550

 CHAPTER 19 Hash Tables = 553

  19.1 Basic Ideas = 553

  19.2 Hash Function = 554

  19.3 Linear Probing = 557

   19.3.1 Naive Analysis of Linear Probing = 558

   19.3.2 What Really Happens : Primary Clustering = 560

   19.3.3 Analysis of the Find Operation = 560

  19.4 Quadratic Probing = 562

   19.4.1 Java Implementation = 568

   19.4.2 Analysis of Quadratic Probing = 572

  19.5 Separate Chaining Hashing 573

  Summary = 573

  Objects of the Game = 575

  Common Errors = 575

  On the Internet = 576

  Exercises = 576

  References = 578

 CHAPTER 20 A Priority Queue : The Binary Heap = 581

  20.1 Basic Ideas = 581

   20.1.1 Structure Property = 582

   20.1.2 Heap-order Property = 584

   20.1.3 Allowed Operations = 584

  20.2 Implementation of the Basic Operations = 588

   20.2.1 insert = 588

   20.2.2 deleteMin = 591

  20.3 fixHeap : Linear Time Heap Construction = 593

  20.4 Advanced Operations : decreasekey and Merge 598

  20.5 Internal Sorting : Heapsort = 598

  20.6 External Sorting = 601

   20.6.1 Why We Need New Algorithms = 601

   20.6.2 Model for External Sorting = 602

   20.6.3 The Simple Algorithm = 602

   20.6.4 Multiway Merge = 604

   20.6.5 Polyphase Merge = 604

   20.6.6 Replacement Selection = 607

  Summary = 608

  Objects of the Game = 608

  Common Errors = 609

  On the Internet = 610

  Exercises = 610

  References = 612

Part Ⅴ : Advanced Data Structures

 CHAPTER 21 Splay Trees = 617

  21.1 Self-adjustment and Amortized Analysis = 617

   21.1.1 Amortized Time Bounds = 618

   21.1.2 A Simple Self-adjusting Strategy (The Does Not Work) = 619

  21.2 The Basic Bottom-up Splay Tree = 621

  21.3 Basic Splay Tree Operations = 623

  21.4 Analysis of Bottom-up Splaying = 624

   21.4.1 Proof of the Splaying Bound = 627

  21.5 Top-Down Splay Trees 630

  21.6 Implementation of top-down Splay trees = 633

  21.7 Comparison of the Splay Tree with Other Searh Trees = 636

  Summary = 640

  Objects of the Game = 640

  Common Errors = 640

  On the Internet = 641

  Exercises = 641

  References = 642

 CHAPTER 22 Merging Priority Queues = 643

  22.1 The Skew Heap = 643

   22.1.1 Merging Is Fundamental = 643

   22.1.2 Simplistic Merging of Heap-ordered Trees = 644

   22.1.3 The Skew Heap : A Simple Modification = 645

   22.1.4 Analysis of the Skew Heap = 646

  22.2 The Pairing Heap = 648

   22.2.1 Pairing Heap Operations and Theory = 649

   22.2.2 Implementation of the Pairing Heap = 651

   22.2.3 Application : Dijkstra's Shortest Weighted Path Algorithm = 660

  Summary = 660

  Objects of the Game = 661

  Common Errors = 661

  On the Internet = 661

  Exercises = 661

  References = 662

 CHAPTER 23 The Disjoint Set Class = 665

  23.1 Equivalence Relations = 665

  23.2 Dynamic Equivalence and Two Applications = 666

   23.2.1 Application ＃1 : Minimum Spanning Trees = 667

   23.2.2 Application ＃2 : The Nearest Common Ancestor Problem = 669

  23.3 The Quick-find Algorithm = 672

  23.4 The Quick-union Algorithm = 674

   23.4.1 Smart Union Algorithms = 676

   23.4.2 Path compression = 677

  23.5 Java Implementation = 679

  23.6 Worst Case for Union-by-rank and Path Compression = 681

   23.6.1 Analysis of the Union／find Algorithm = 682

  Summary = 689

  Objects of the Game = 689

  Common Errors = 690

  On the Internet = 690

  Exercises = 690

  References = 692

APPENDICES

 APPENDIX A Java Platforms = 697

  A.1 Setting the Environment = 697

   A.1.1 Unix Instructions = 698

   A.1.2 Windows 95／NT Instructions = 699

  A.2 Sun's JDK = 700

  A.3 Visual Development Environments = 700

   A.3.1 Symantec Cafe = 701

   A.3.2 Microsoft Visual J＋＋ = 707

 APPENDIX B Operators = 713

 APPENDIX C Some Library Routines = 715

  C.1 Classes in Package Java.Lang = 715

   C.1.1 Character = 715

   C.1.2 Integer = 716

   C.1.3 Object = 717

   C.1.4 String = 718

   C.1.5 StringBuffer = 719

   C.1.6 System = 721

   C.1.7 Thread = 723

   C.1.8 Throwable = 723

  C.2 Classes in Package Java.io = 724

   C.2.1 BufferedReader = 725

   C.2.2 File = 725

   C.2.3 FileReader = 726

   C.2.4 InputStreamreader = 726

   C.2.5 PushbackReader = 727

  C.3 Classes in Package java.util = 727

   C.3.1 Random = 728

   C.3.2 StringTokenizer = 728

   C.3.3 Vector = 730

  On the Internet = 730

 APPENDIX D Grophical User Interfaces = 731

  D.1 The Abstract Window Toolkit = 713

  D.2 Basic Objects in the AWT = 732

   D.2.1 Component = 733

   D.2.2 Container = 734

   D.2.3 Top-level Windows = 734

   D.2.4 Panel = 736

   D.2.5 Important I／O Components = 736

  D.3 Basic AWT Principle = 741

   D.3.1 Layout Managers = 741

   D.3.2 Graphics = 745

   D.3.3 Events = 747

   D.3.4 Summary : Putting the Pieces Together = 750

  D.4 Animations and Threads = 750

  D.5 Applets = 753

   D.5.1 Hypertext Markup Language = 753

   D.5.2 Parameters = 756

   D.5.3 Applet Limitations = 756

   D.5.4 Making an Application an Applet = 758

   D.5.5 Applets with Animation = 760

  Summary = 762

  Objects of the Game = 762

  Common Errors = 764

  On the Internet = 765

  Exercises = 766

  References = 768

Index = 769