Data Structures and Algorithms in Java

__Data Structures and Algorithms in Java, Second Edition__is designed to be easy to read and understand although the topic itself is complicated. Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate. In the second edition, the program is rewritten to improve operation and clarify the algorithms, the example programs are revised to work with the latest version of the Java JDK, and questions and exercises will be added at the end of each chapter making the book even more useful. Educational Supplement Data Structures & Algorithms in Java, Second Edition 2 Copyright © 2003 by Sams Publishing 3 Contents at a Glance 4 Table of Contents 5 About the Author 21 We Want to Hear from You! 24 Introduction 26 What’s New in the Second Edition 26 What This Book Is About 27 What’s Different About This Book 28 Who This Book Is For 30 What You Need to Know Before You Read This Book 30 The Software You Need to Use This Book 31 How This Book Is Organized 31 Enjoy Yourself! 33 CHAPTER 1 Overview 34 What Are Data Structures and Algorithms Good For? 34 Overview of Data Structures 36 Overview of Algorithms 37 Some Definitions 38 Object-Oriented Programming 39 Software Engineering 46 Java for C++ Programmers 47 Java Library Data Structures 54 Summary 55 Questions 55 CHAPTER 2 Arrays 58 The Array Workshop Applet 58 The Basics of Arrays in Java 64 Dividing a Program into Classes 69 Class Interfaces 71 The Ordered Workshop Applet 77 Java Code for an Ordered Array 81 Logarithms 87 Storing Objects 89 Big O Notation 95 Why Not Use Arrays for Everything? 97 Summary 98 Questions 99 Experiments 100 Programming Projects 101 CHAPTER 3 Simple Sorting 102 How Would You Do It? 103 Bubble Sort 104 Selection Sort 114 Insertion Sort 120 Sorting Objects 128 Comparing the Simple Sorts 133 Summary 133 Questions 134 Experiments 136 Programming Projects 137 CHAPTER 4 Stacks and Queues 140 A Different Kind of Structure 140 Stacks 141 Queues 157 Priority Queues 168 Parsing Arithmetic Expressions 174 Summary 198 Questions 199 Experiments 201 Programming Projects 201 CHAPTER 5 Linked Lists 204 Links 204 The LinkList Workshop Applet 208 A Simple Linked List 210 Finding and Deleting Specified Links 218 Double-Ended Lists 223 Linked-List Efficiency 227 Abstract Data Types 227 Doubly Linked Lists 246 Iterators 256 Summary 269 Questions 270 Experiments 272 Programming Projects 272 CHAPTER 6 Recursion 276 Triangular Numbers 276 Factorials 285 Anagrams 287 A Recursive Binary Search 293 The Towers of Hanoi 298 mergesort 304 Eliminating Recursion 319 Some Interesting Recursive Applications 328 Summary 333 Questions 335 Experiments 337 Programming Projects 337 CHAPTER 7 Advanced Sorting 340 Shellsort 340 Quicksort 358 Radix Sort 382 Summary 384 Questions 386 Experiments 388 Programming Projects 388 CHAPTER 8 Binary Trees 390 Why Use Binary Trees? 390 Tree Terminology 392 An Analogy 395 How Do Binary Search Trees Work? 396 Finding a Node 401 Inserting a Node 403 Traversing the Tree 406 Finding Maximum and Minimum Values 413 Deleting a Node 414 The Efficiency of Binary Trees 426 Trees Represented as Arrays 428 Duplicate Keys 429 The Complete tree.java Program 430 The Huffman Code 440 Summary 447 Questions 448 Experiments 450 Programming Projects 450 CHAPTER 9 Red-Black Trees 454 Our Approach to the Discussion 454 Balanced and Unbalanced Trees 455 Using the RBTree Workshop Applet 459 Experimenting with the Workshop Applet 462 Rotations 466 Inserting a New Node 470 Deletion 482 The Efficiency of Red-Black Trees 482 Red-Black Tree Implementation 483 Other Balanced Trees 483 Summary 484 Questions 485 Experiments 487 CHAPTER 10 2-3-4 Trees and External Storage 488 Introduction to 2-3-4 Trees 488 The Tree234 Workshop Applet 495 Java Code for a 2-3-4 Tree 500 2-3-4 Trees and Red-Black Trees 511 Efficiency of 2-3-4 Trees 516 2-3 Trees 517 External Storage 521 Summary 538 Questions 539 Experiments 541 Programming Projects 541 CHAPTER 11 Hash Tables 544 Introduction to Hashing 545 Open Addressing 553 Separate Chaining 577 Hash Functions 586 Hashing Efficiency 591 Hashing and External Storage 596 Summary 598 Questions 599 Experiments 601 Programming Projects 602 CHAPTER 12 Heaps 604 Introduction to Heaps 605 The Heap Workshop Applet 612 Java Code for Heaps 613 A Tree-based Heap 625 Heapsort 626 Summary 635 Questions 636 Experiments 637 Programming Projects 637 CHAPTER 13 Graphs 640 Introduction to Graphs 640 Searches 648 Minimum Spanning Trees 668 Topological Sorting with Directed Graphs 674 Connectivity in Directed Graphs 686 Summary 690 Questions 690 Experiments 692 Programming Projects 692 CHAPTER 14 Weighted Graphs 694 Minimum Spanning Tree with Weighted Graphs 694 The Shortest-Path Problem 712 The All-Pairs Shortest-Path Problem 733 Efficiency 735 Intractable Problems 735 Summary 738 Questions 738 Experiments 740 Programming Projects 740 CHAPTER 15 When to Use What 742 General-Purpose Data Structures 742 Special-Purpose Data Structures 747 Sorting 749 Graphs 750 External Storage 750 Onward 753 APPENDIX A Running the Workshop Applets and Example Programs 754 The Workshop Applets 754 The Example Programs 755 The Sun Microsystem’s Software Development Kit 755 Multiple Class Files 758 Other Development Systems 759 APPENDIX B Further Reading 760 Data Structures and Algorithms 760 Object-Oriented Programming Languages 761 Object-Oriented Design (OOD) and Software Engineering 761 APPENDIX C Answers to Questions 764 Chapter 1, Overview 764 Chapter 2, Arrays 764 Chapter 3, Simple Sorting 765 Chapter 4, Stacks and Queues 766 Chapter 5, Linked Lists 766 Chapter 6, Recursion 767 Chapter 7, Advanced Sorting 768 Chapter 8, Binary Trees 768 Chapter 9, Red-Black Trees 769 Chapter 10, 2-3-4 Trees and External Storage 770 Chapter 11, Hash Tables 770 Chapter 12, Heaps 771 Chapter 13, Graphs 771 Chapter 14, Weighted Graphs 772 Index 774 Data Structures And Algorithms In Java, Second Edition Is Designed To Be Easy To Read And Understand Although The Topic Itself Is Complicated. Algorithms Are The Procedures That Software Programs Use To Manipulate Data Structures. Besides Clear And Simple Example Programs, The Author Includes A Workshop As A Small Demonstration Program Executable On A Web Browser. The Programs Demonstrate In Graphical Form What Data Structures Look Like And How They Operate. In The Second Edition, The Program Is Rewritten To Improve Operation And Clarify The Algorithms, The Example Programs Are Revised To Work With The Latest Version Of The Java Jdk, And Questions And Exercises Will Be Added At The End Of Each Chapter Making The Book Even More Useful.--publisher's Website. 1. Overview -- 2. Arrays -- 3. Simple Sorting -- 4. Stacks And Queues -- 5. Linked Lists -- 6. Recursion -- 7. Advanced Sorting -- 8. Binary Trees -- 9. Red-black Trees -- 10. 2-3-4 Trees And External Storage -- 11. Hash Tables -- 12. Heaps -- 13. Graphs -- 14. Weighted Graphs -- 15. When To Use What -- App. A. Running The Workshop Applets And Example Programs. Robert Lafore. Rev. Ed. Of Sams Teach Yourself Data Structures And Algorithms In 24 Hours, 1999. Includes Bibliographical References (p. [735]-737) And Index. Data Structures and Algorithms in Java, Second Edition is designed to be easy to read and understand although the topic itself is complicated. Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate. In the second edition, the program is rewritten to improve operation and clarify the algorithms, the example programs are revised to work with the latest version of the Java JDK, and questions and exercises will be added at the end of each chapter making the book even more useful. Educational Supplement Suggested solutions to the programming projects found at the end of each chapter are made available to instructors at recognized educational institutions. This educational supplement can be found at (http://www.prenhall.com) www.prenhall.com , in the Instructor Resource Center. Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, this work includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate. This guy does a great job of balancing tech with down to earth understanding. I used this book in my second tier programming class (OOP data structures) and it was the first book that I could really dive into, read his text and then take the code apart and understand it. He has very nice code examples.