Special Offers see all
More at Powell'sRecently Viewed clear list 
$157.60
New Hardcover
Ships in 1 to 3 days
available for shipping or prepaid pickup only
Available for Instore Pickup
in 7 to 12 days
More copies of this ISBNThis title in other editionsData Structures and Abstractions with Javaby Frank M. Carrano
Synopses & ReviewsPublisher Comments:Data Structures and Abstractions with Java, 3e, is ideal for one or twosemester courses in data structures (CS2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems.
This is the most studentfriendly 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 objectoriented 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://frankmcarrano.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 About the AuthorFrank 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 wellknown 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://frankmcarrano.com/blog/
Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano Find him on Facebook: https://www.facebook.com/makingitreal Table of ContentsIntroduction 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 FixedSize 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 ArrayBased 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 ArrayBased Implementation 145 A VectorBased 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 ArrayBased Implementation of a Queue 278 A Circular Array 278 A Circular Array with One Unused Location 281 A VectorBased Implementation of a Queue 286 Circular Linked Implementations of a Queue 288 A TwoPart 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 ArrayBased Implementation 385 Why Are Iterator Methods in Their Own Class? 388 The Interface ListIterator 390 Using the Interface ListIterator 393 An ArrayBased Implementation of the Interface ListIterator 395 The Inner Class 397 Java Class Library: The Interface Iterable 402 Iterable and foreach 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 ArrayBased Implementations 498 An Unsorted ArrayBased Dictionary 498 A Sorted ArrayBased Dictionary 503 VectorBased 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 23 Trees 707 Searching a 23 Tree 708 Adding Entries to a 23 Tree 709 Splitting Nodes During Addition 711 24 Trees 712 Adding Entries to a 24 Tree 713 Comparing AVL, 23, and 24 Trees 715 RedBlack Trees 716 Properties of a RedBlack Tree 717 Adding Entries to a RedBlack Tree 718 Java Class Library: The Class TreeMap 724 BTrees 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 BreadthFirst Traversal 738 DepthFirst 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 302 Creating a ReadOnly Class 304 Companion Classes 306 Cloneable Objects 308 Cloning an Array 3014 Cloning a Chain 3016 A Sorted List of Clones 3019
Appendices A. Java Essentials A1 Introduction A2 Applications and Applets A2 Objects and Classes A3 A First Java Application Program A3 Java Basics A5 Identifiers A5 Reserved Words A6 Variables A6 Primitive Types A7 Constants A7 Assignment Statements A8 Assignment Compatibilities A9 Type Casting A9 Arithmetic Operators and Expressions A10 Parentheses and Precedence Rules A11 Increment and Decrement Operators A12 Special Assignment Operators A13 Named Constants A14 The Class Math A15 Simple Input and Output Using the Keyboard and Screen A15 Screen Output A15 Keyboard Input Using the Class Scanner A17 The ifelse Statement A19 Boolean Expressions A20 Nested Statements A23 Multiway ifelse Statements A24 The Conditional Operator (Optional) A25 The switch Statement A26 Enumerations A28 Scope A30 Loops A30 The while Statement A31 The for Statement A32 The dowhile Statement A34 Additional Loop Information A35 The Class String A36 Characters Within Strings A36 Concatenation of Strings A37 String Methods A38 The Class StringBuilder A40 Using Scanner to Extract Pieces of a String A42 Arrays A44 Array Parameters and Returned Values A46 Initializing Arrays A47 Array Index Out of Bounds A47 Use of = and == with Arrays A47 Arrays and the ForEach Loop A48 Multidimensional Arrays A49 Wrapper Classes A51
B. Java Classes B1 Objects and Classes B1 Using the Methods in a Java Class B3 References and Aliases B4 Defining a Java Class B5 Method Definitions B7 Arguments and Parameters B9 Passing Arguments B9 A Definition of the Class Name B13 Constructors B15 The Method toString B17 Methods That Call Other Methods B17 Methods That Return an Instance of Their Class B19 Static Fields and Methods B19 Overloading Methods B21 Enumeration as a Class B22 Packages B25 The Java Class Library B25 Generic Data Types B26
C. Creating Classes from Other Classes C1 Composition C2 Adapters C4 Inheritance C5 Invoking Constructors from Within Constructors C9 Private Fields and Methods of the Superclass C10 Protected Access C11 Overriding and Overloading Methods C11 Multiple Inheritance C16 Type Compatibility and Superclasses C16 The Class Object C18 Abstract Classes and Methods C19 Polymorphism C21
D. Designing Classes D1 Encapsulation D2 Specifying Methods D4 Comments D4 Preconditions and Postconditions D5 Assertions D6 Java Interfaces D7 Writing an Interface D8 Implementing an Interface D10 An Interface as a Data Type D11 Generic Types Within an Interface D12 Extending an Interface D14 Interfaces Versus Abstract Classes D15 Named Constants Within an Interface D17 Choosing Classes D18 Identifying Classes D20 CRC Cards D20 The Unified Modeling Language D21 Reusing Classes D23
E. Handling Exceptions E1 The Basics E2 Handling an Exception E4 Postpone Handling: The throws Clause E4 Handle It Now: The trycatch Blocks E5 Multiple catch Blocks E6 Throwing an Exception E8 ProgrammerDefined Exception Classes E9 Inheritance and Exceptions E14 The finally Block E15
F. File Input and Output F1 Preliminaries F2 Why Files? F2 Streams F2 The Kinds of Files F3 File Names F3 Text Files F3 Creating a Text File F3 Reading a Text File F8 Changing Existing Data in a Text File F12 Defining a Method to Open a Stream F13 Binary Files F13 Creating a Binary File of Primitive Data F14 Reading a Binary File of Primitive Data F18 Strings in a Binary File F20 Object Serialization F23
G. Documentation and Programming Style G1 Naming Variables and Classes G1 Indenting G2 Comments G2 SingleLine Comments G3 Comment Blocks G3 When to Write Comments G3 Java Documentation Comments G3 Running javadoc G5 Glossary Online Index I1 What Our Readers Are SayingBe the first to add a comment for a chance to win!Product Details
Related Subjects
Computers and Internet » Computer Languages » Java


