Overview

Data Structures and Abstractions with Java, 3e, is ideal for one- or two-semester courses in data structures (CS-2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems. This is the most student-friendly data structures text available that introduces ADTs in individual, brief chapters — each with pedagogical tools to help students master each concept.¿Using the latest features of Java, this unique object-oriented presentation makes a clear distinction between specification and implementation to simplify learning, while providing maximum classroom flexibility. Author Frank Carrano's Making it Real blog http://frank-m-carrano.com/blog/ extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science. Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano Find him on Facebook: https://www.facebook.com/makingitreal

Full Product Details

Author:   Frank M. Carrano
Publisher:   Pearson Education (US)
Imprint:   Pearson
Edition:   3rd edition
Dimensions:   Width: 20.30cm , Height: 3.80cm , Length: 25.40cm
Weight:   1.750kg
ISBN:  

9780136100911

ISBN 10:   0136100910
Pages:   1008
Publication Date:   16 December 2011
Audience:   College/higher education ,  Undergraduate
Replaced By:   9780133744057
Format:   Hardback
Publisher's Status:   Out of Print
Availability:   Awaiting stock  

Table of Contents

Introduction 1 Chapter 1 Bags 5 The Bag 6 A Bag’s Behaviors 6 Specifying a Bag 7 An Interface 13 Using the ADT Bag 15 Using an ADT Is Like Using a Vending Machine 20 Java Class Library: The Interface Set 21 Chapter 2 Bag Implementations That Use Arrays 27 Using a Fixed-Size Array to Implement the ADT Bag 28 An Analogy 28 A Group of Core Methods 29 Implementing the Core Methods 30 Testing the Core Methods 37 Implementing More Methods 40 Methods That Remove Entries 42 Using Array Resizing to Implement the ADT Bag 50 Resizing an Array 50 A New Implementation of a Bag 53 The Pros and Cons of Using an Array to Implement the ADT Bag 55 Chapter 3 A Bag Implementation That Links Data 61 Linked Data 62 Forming a Chain by Adding to Its Beginning 63 A Linked Implementation of the ADT Bag 65 The Private Class Node 65 An Outline of the Class LinkedBag 66 Defining Some Core Methods 67 Testing the Core Methods 71 The Method getFrequencyOf 72 The Method contains 73 Removing an Item from a Linked Chain 74 The Methods remove and clear 75 A Class Node That Has Set and Get Methods 78 The Pros and Cons of Using a Chain to Implement the ADT Bag 81 Chapter 4 The Efficiency of Algorithms 87 Motivation 88 Measuring an Algorithm’s Efficiency 89 Counting Basic Operations 91 Best, Worst, and Average Cases 93 Big Oh Notation 94 The Complexities of Program Constructs 97 Picturing Efficiency 98 The Efficiency of Implementations of the ADT Bag 102 An Array-Based Implementation 102 A Linked Implementation 103 Comparing the Implementations 104 Chapter 5 Stacks 113 Specifications of the ADT Stack 114 Using a Stack to Process Algebraic Expressions 118 A Problem Solved: Checking for Balanced Delimiters in an Infix Algebraic Expression 119 A Problem Solved: Transforming an Infix Expression to a Postfix Expression 123 A Problem Solved: Evaluating Postfix Expressions 128 A Problem Solved: Evaluating Infix Expressions 130 The Program Stack 132 Java Class Library: The Class Stack 133 Chapter 6 Stack Implementations 141 A Linked Implementation 141 An Array-Based Implementation 145 A Vector-Based Implementation 149 Java Class Library: The Class Vector 150 Using a Vector to Implement the ADT Stack 150 Chapter 7 Recursion 157 What Is Recursion? 158 Tracing a Recursive Method 162 Recursive Methods That Return a Value 166 Recursively Processing an Array 168 Recursively Processing a Linked Chain 171 The Time Efficiency of Recursive Methods 172 The Time Efficiency of countDown 172 The Time Efficiency of Computing xn 174 A Simple Solution to a Difficult Problem 175 A Poor Solution to a Simple Problem 180 Tail Recursion 182 Indirect Recursion 184 Using a Stack Instead of Recursion 185 Chapter 8 An Introduction to Sorting 195 Organizing Java Methods That Sort an Array 196 Selection Sort 198 Iterative Selection Sort 199 Recursive Selection Sort 201 The Efficiency of Selection Sort 202 Insertion Sort 203 Iterative Insertion Sort 204 Recursive Insertion Sort 206 The Efficiency of Insertion Sort 208 Insertion Sort of a Chain of Linked Nodes 208 Shell Sort 211 The Java Code 213 The Efficiency of Shell Sort 214 Comparing the Algorithms 214 Chapter 9 Faster Sorting Methods 221 Merge Sort 222 Merging Arrays 222 Recursive Merge Sort 223 The Efficiency of Merge Sort 225 Iterative Merge Sort 227 Merge Sort in the Java Class Library 227 Quick Sort 228 The Efficiency of Quick Sort 228 Creating the Partition 229 Java Code for Quick Sort 232 Quick Sort in the Java Class Library 234 Radix Sort 235 Pseudocode for Radix Sort 236 The Efficiency of Radix Sort 237 Comparing the Algorithms 237 Chapter 10 Queues, Deques, and Priority Queues 245 The ADT Queue 246 A Problem Solved: Simulating a Waiting Line 250 A Problem Solved: Computing the Capital Gain in a Sale of Stock 256 Java Class Library: The Interface Queue 259 The ADT Deque 260 A Problem Solved: Computing the Capital Gain in a Sale of Stock 262 Java Class Library: The Interface Deque 263 Java Class Library: The Class ArrayDeque 264 The ADT Priority Queue 265 A Problem Solved: Tracking Your Assignments 266 Java Class Library: The Class PriorityQueue 268 Chapter 11 Queue, Deque, and Priority Queue Implementations 273 A Linked Implementation of a Queue 274 An Array-Based Implementation of a Queue 278 A Circular Array 278 A Circular Array with One Unused Location 281 A Vector-Based Implementation of a Queue 286 Circular Linked Implementations of a Queue 288 A Two-Part Circular Linked Chain 289 Java Class Library: The Class AbstractQueue 294 A Doubly Linked Implementation of a Deque 295 Possible Implementations of a Priority Queue 299 Chapter 12 Lists 305 Specifications for the ADT List 306 Using the ADT List 312 Java Class Library: The Interface List 316 Java Class Library: The Class ArrayList 316 Chapter 13 List Implementations That Use Arrays 321 Using an Array to Implement the ADT List 322 An Analogy 322 The Java Implementation 324 The Efficiency of Using an Array to Implement the ADT List 331 Using a Vector to Implement the ADT List 332 Chapter 14 A List Implementation That Links Data 339 Operations on a Chain of Linked Nodes 340 Adding a Node at Various Positions 340 Removing a Node from Various Positions 344 The Private Method getNodeAt 345 Beginning the Implementation 346 The Data Fields and Constructor 347 Adding to the End of the List 348 Adding at a Given Position Within the List 349 The Methods isEmpty and toArray 350 Testing the Core Methods 353 Continuing the Implementation 354 A Refined Implementation 356 The Tail Reference 357 The Efficiency of Using a Chain to Implement the ADT List 360 Java Class Library: The Class LinkedList 362 Chapter 15 Iterators 369 What Is an Iterator? 370 The Interface Iterator 371 Using the Interface Iterator 372 A Separate Class Iterator 377 An Inner Class Iterator 381 A Linked Implementation 381 An Array-Based Implementation 385 Why Are Iterator Methods in Their Own Class? 388 The Interface ListIterator 390 Using the Interface ListIterator 393 An Array-Based Implementation of the Interface ListIterator 395 The Inner Class 397 Java Class Library: The Interface Iterable 402 Iterable and for-each loops 403 The Interface List Revisited 403 Chapter 16 Sorted Lists 411 Specifications for the ADT Sorted List 412 Using the ADT Sorted List 415 A Linked Implementation 416 The Method add 417 The Efficiency of the Linked Implementation 424 An Implementation That Uses the ADT List 424 Efficiency Issues 427 Chapter 17 Inheritance and Lists 433 Using Inheritance to Implement a Sorted List 434 Designing a Base Class 436 Creating an Abstract Base Class 441 An Efficient Implementation of a Sorted List 443 The Method add 443 Chapter 18 Searching 447 The Problem 448 Searching an Unsorted Array 448 An Iterative Sequential Search of an Unsorted Array 449 A Recursive Sequential Search of an Unsorted Array 450 The Efficiency of a Sequential Search of an Array 452 Searching a Sorted Array 452 A Sequential Search of a Sorted Array 452 A Binary Search of a Sorted Array 453 Java Class Library: The Method binarySearch 458 The Efficiency of a Binary Search of an Array 458 Searching an Unsorted Chain 460 An Iterative Sequential Search of an Unsorted Chain 460 A Recursive Sequential Search of an Unsorted Chain 461 The Efficiency of a Sequential Search of a Chain 462 Searching a Sorted Chain 462 A Sequential Search of a Sorted Chain 462 A Binary Search of a Sorted Chain 462 Choosing a Search Method 463 Chapter 19 Dictionaries 471 Specifications for the ADT Dictionary 472 A Java Interface 476 Iterators 477 Using the ADT Dictionary 478 A Problem Solved: A Directory of Telephone Numbers 479 A Problem Solved: The Frequency of Words 484 A Problem Solved: A Concordance of Words 488 Java Class Library: The Interface Map 490 Chapter 20 Dictionary Implementations 497 Array-Based Implementations 498 An Unsorted Array-Based Dictionary 498 A Sorted Array-Based Dictionary 503 Vector-Based Implementations 508 Linked Implementations 512 An Unsorted Linked Dictionary 514 A Sorted Linked Dictionary 514 Chapter 21 Introducing Hashing 523 What Is Hashing? 524 Hash Functions 527 Computing Hash Codes 527 Compressing a Hash Code into an Index for the Hash Table 530 Resolving Collisions 531 Open Addressing with Linear Probing 531 Open Addressing with Quadratic Probing 537 Open Addressing with Double Hashing 537 A Potential Problem with Open Addressing 539 Separate Chaining 539 Chapter 22 Hashing as a Dictionary Implementation 547 The Efficiency of Hashing 548 The Load Factor 548 The Cost of Open Addressing 549 The Cost of Separate Chaining 551 Rehashing 552 Comparing Schemes for Collision Resolution 553 A Dictionary Implementation That Uses Hashing 554 Entries in the Hash Table 554 Data Fields and Constructors 555 The Methods getValue, remove, and add 557 Iterators 562 Java Class Library: The Class HashMap 564 Java Class Library: The Class HashSet 564 Chapter 23 Trees 569 Tree Concepts 570 Hierarchical Organizations 570 Tree Terminology 572 Traversals of a Tree 576 Traversals of a Binary Tree 576 Traversals of a General Tree 579 Java Interfaces for Trees 579 Interfaces for All Trees 580 An Interface for Binary Trees 580 Examples of Binary Trees 582 Expression Trees 582 Decision Trees 584 Binary Search Trees 588 Heaps 590 Examples of General Trees 593 Parse Trees 593 Game Trees 593 Chapter 24 Tree Implementations 603 The Nodes in a Binary Tree 604 An Interface for a Node 605 An Implementation of BinaryNode 606 An Implementation of the ADT Binary Tree 607 Creating a Basic Binary Tree 608 The Method privateSetTree 609 Accessor and Mutator Methods 612 Computing the Height and Counting Nodes 613 Traversals 614 An Implementation of an Expression Tree 619 General Trees 621 A Node for a General Tree 621 Using a Binary Tree to Represent a General Tree 622 Chapter 25 A Binary Search Tree Implementation 629 Getting Started 630 An Interface for the Binary Search Tree 631 Duplicate Entries 633 Beginning the Class Definition 634 Searching and Retrieving 635 Traversing 637 Adding an Entry 637 A Recursive Implementation 638 An Iterative Implementation 642 Removing an Entry 643 Removing an Entry Whose Node Is a Leaf 644 Removing an Entry Whose Node Has One Child 644 Removing an Entry Whose Node Has Two Children 645 Removing an Entry in the Root 648 A Recursive Implementation 649 An Iterative Implementation 652 The Efficiency of Operations 656 The Importance of Balance 657 The Order in Which Nodes Are Added 658 An Implementation of the ADT Dictionary 659 Chapter 26 A Heap Implementation 673 Reprise: The ADT Heap 674 Using an Array to Represent a Heap 674 Adding an Entry 677 Removing the Root 680 Creating a Heap 683 Heap Sort 686 Chapter 27 Balanced Search Trees 695 AVL Trees 696 Single Rotations 696 Double Rotations 699 Implementation Details 703 2-3 Trees 707 Searching a 2-3 Tree 708 Adding Entries to a 2-3 Tree 709 Splitting Nodes During Addition 711 2-4 Trees 712 Adding Entries to a 2-4 Tree 713 Comparing AVL, 2-3, and 2-4 Trees 715 Red-Black Trees 716 Properties of a Red-Black Tree 717 Adding Entries to a Red-Black Tree 718 Java Class Library: The Class TreeMap 724 B-Trees 724 Chapter 28 Graphs 731 Some Examples and Terminology 732 Road Maps 732 Airline Routes 735 Mazes 736 Course Prerequisites 736 Trees 737 Traversals 737 Breadth-First Traversal 738 Depth-First Traversal 740 Topological Order 741 Paths 744 Finding a Path 744 The Shortest Path in an Unweighted Graph 744 The Shortest Path in a Weighted Graph 747 Java Interfaces for the ADT Graph 751 Chapter 29 Graph Implementations 761 An Overview of Two Implementations 762 The Adjacency Matrix 762 The Adjacency List 763 Vertices and Edges 764 Specifying the Class Vertex 765 The Inner Class Edge 767 Implementing the Class Vertex 768 An Implementation of the ADT Graph 772 Basic Operations 772 Graph Algorithms 775 Chapter 30 Mutable, Immutable, and Cloneable Objects Online Mutable and Immutable Objects 30-2 Creating a Read-Only Class 30-4 Companion Classes 30-6 Cloneable Objects 30-8 Cloning an Array 30-14 Cloning a Chain 30-16 A Sorted List of Clones 30-19 Appendices A. Java Essentials A-1 Introduction A-2 Applications and Applets A-2 Objects and Classes A-3 A First Java Application Program A-3 Java Basics A-5 Identifiers A-5 Reserved Words A-6 Variables A-6 Primitive Types A-7 Constants A-7 Assignment Statements A-8 Assignment Compatibilities A-9 Type Casting A-9 Arithmetic Operators and Expressions A-10 Parentheses and Precedence Rules A-11 Increment and Decrement Operators A-12 Special Assignment Operators A-13 Named Constants A-14 The Class Math A-15 Simple Input and Output Using the Keyboard and Screen A-15 Screen Output A-15 Keyboard Input Using the Class Scanner A-17 The if-else Statement A-19 Boolean Expressions A-20 Nested Statements A-23 Multiway if-else Statements A-24 The Conditional Operator (Optional) A-25 The switch Statement A-26 Enumerations A-28 Scope A-30 Loops A-30 The while Statement A-31 The for Statement A-32 The do-while Statement A-34 Additional Loop Information A-35 The Class String A-36 Characters Within Strings A-36 Concatenation of Strings A-37 String Methods A-38 The Class StringBuilder A-40 Using Scanner to Extract Pieces of a String A-42 Arrays A-44 Array Parameters and Returned Values A-46 Initializing Arrays A-47 Array Index Out of Bounds A-47 Use of = and == with Arrays A-47 Arrays and the For-Each Loop A-48 Multidimensional Arrays A-49 Wrapper Classes A-51 B. Java Classes B-1 Objects and Classes B-1 Using the Methods in a Java Class B-3 References and Aliases B-4 Defining a Java Class B-5 Method Definitions B-7 Arguments and Parameters B-9 Passing Arguments B-9 A Definition of the Class Name B-13 Constructors B-15 The Method toString B-17 Methods That Call Other Methods B-17 Methods That Return an Instance of Their Class B-19 Static Fields and Methods B-19 Overloading Methods B-21 Enumeration as a Class B-22 Packages B-25 The Java Class Library B-25 Generic Data Types B-26 C. Creating Classes from Other Classes C-1 Composition C-2 Adapters C-4 Inheritance C-5 Invoking Constructors from Within Constructors C-9 Private Fields and Methods of the Superclass C-10 Protected Access C-11 Overriding and Overloading Methods C-11 Multiple Inheritance C-16 Type Compatibility and Superclasses C-16 The Class Object C-18 Abstract Classes and Methods C-19 Polymorphism C-21 D. Designing Classes D-1 Encapsulation D-2 Specifying Methods D-4 Comments D-4 Preconditions and Postconditions D-5 Assertions D-6 Java Interfaces D-7 Writing an Interface D-8 Implementing an Interface D-10 An Interface as a Data Type D-11 Generic Types Within an Interface D-12 Extending an Interface D-14 Interfaces Versus Abstract Classes D-15 Named Constants Within an Interface D-17 Choosing Classes D-18 Identifying Classes D-20 CRC Cards D-20 The Unified Modeling Language D-21 Reusing Classes D-23 E. Handling Exceptions E-1 The Basics E-2 Handling an Exception E-4 Postpone Handling: The throws Clause E-4 Handle It Now: The try-catch Blocks E-5 Multiple catch Blocks E-6 Throwing an Exception E-8 Programmer-Defined Exception Classes E-9 Inheritance and Exceptions E-14 The finally Block E-15 F. File Input and Output F-1 Preliminaries F-2 Why Files? F-2 Streams F-2 The Kinds of Files F-3 File Names F-3 Text Files F-3 Creating a Text File F-3 Reading a Text File F-8 Changing Existing Data in a Text File F-12 Defining a Method to Open a Stream F-13 Binary Files F-13 Creating a Binary File of Primitive Data F-14 Reading a Binary File of Primitive Data F-18 Strings in a Binary File F-20 Object Serialization F-23 G. Documentation and Programming Style G-1 Naming Variables and Classes G-1 Indenting G-2 Comments G-2 Single-Line Comments G-3 Comment Blocks G-3 When to Write Comments G-3 Java Documentation Comments G-3 Running javadoc G-5 Glossary Online Index I-1

Reviews

Author Information

Frank M. Carrano is a professor emeritus of computer science at the University of Rhode Island. He received the Ph.D. degree in computer science from Syracuse University in 1969. His interests include data structures, computer science education, social issues in computing, and numerical computation. Professor Carrano is particularly interested in the design and delivery of undergraduate courses in computer science. He has authored several well-known computer science textbooks for undergraduates. Visit Frank Carrano's Making it Real blog -- a discussion with instructors and students about teaching and learning computer science. http://frank-m-carrano.com/blog/ Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano Find him on Facebook: https://www.facebook.com/makingitreal

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions