- ホーム
- > 洋書
- > 英文書
- > Computer / General
Full Description
Using the latest features of Java, this unique object-oriented presentation introduces readers to data structures via short, manageable chapters. KEY TOPICS: This reader-friendly data structures text introduces ADTs in individual, brief chapters - each with pedagogical tools to help readers master each concept. MARKET: This title is suitable for programmers and software engineers interested in learning more about data structures and abstractions.
Contents
IntroductionPrelude: Designing Classes EncapsulationSpecifying MethodsCommentsPreconditions and PostconditionsAssertionsJava InterfacesWriting an InterfaceImplementing an InterfaceAn Interface as a Data TypeExtending an InterfaceInterfaces Versus Abstract ClassesNamed Constants Within an InterfaceChoosing ClassesIdentifying ClassesCRC CardsThe Unifed Modeling LanguageReusing ClassesChapter 1: BagsThe BagA Bag's BehaviorsSpecifying a BagAn InterfaceUsing the ADT BagUsing an ADT Is Like Using a Vending MachineThe ADT SetJava Interlude 1: Generics Generic Data TypesGeneric Types Within an InterfaceGeneric ClassesChapter 2: Bag Implementations That Use Arrays Using a Fixed-Size Array to Implement the ADT BagAn AnalogyA Group of Core MethodsImplementing the Core MethodsMaking the Implementation SecureTesting the Core MethodsImplementing More MethodsMethods That Remove EntriesUsing Array Resizing to Implement the ADT BagResizing an ArrayA New Implementation of a BagThe Pros and Cons of Using an Array to Implement the ADT BagJava Interlude 2: Exceptions The BasicsHandling an ExceptionPostpone Handling: The throws ClauseHandle It Now: The try-catch BlocksMultiple catch BlocksThrowing an ExceptionChapter 3: A Bag Implementation That Links Data Linked DataForming a Chain by Adding to Its BeginningA Linked Implementation of the ADT BagThe Private Class NodeAn Outline of the Class LinkedBagDefning Some Core MethodsTesting the Core MethodsThe Method getFrequencyOfThe Method containsRemoving an Item from a Linked ChainThe Methods remove and clearA Class Node That Has Set and Get MethodsThe Pros and Cons of Using a Chain to Implement the ADT BagChapter 4: The Effciency of AlgorithmsMotivationMeasuring an Algorithm's EffciencyCounting Basic OperationsBest, Worst, and Average CasesBig Oh NotationThe Complexities of Program ConstructsPicturing EffciencyThe Effciency of Implementations of the ADT BagAn Array-Based ImplementationA Linked ImplementationComparing the ImplementationsChapter 5: StacksSpecifcations of the ADT StackUsing a Stack to Process Algebraic ExpressionsA Problem Solved: Checking for Balanced Delimiters in an Infx Algebraic ExpressionA Problem Solved: Transforming an Infx Expression to a Postfx ExpressionA Problem Solved: Evaluating Postfx ExpressionsA Problem Solved: Evaluating Infx ExpressionsThe Program StackJava Class Library: The Class StackChapter 6: Stack Implementations A Linked ImplementationAn Array-Based ImplementationA Vector-Based ImplementationJava Class Library: The Class VectorUsing a Vector to Implement the ADT StackChapter 7: RecursionWhat Is Recursion?Tracing a Recursive MethodRecursive Methods That Return a ValueRecursively Processing an ArrayRecursively Processing a Linked ChainThe Time Effciency of Recursive MethodsThe Time Effciency of countDownThe Time Effciency of Computing xnA Simple Solution to a Diffcult ProblemA Poor Solution to a Simple ProblemTail RecursionIndirect RecursionUsing a Stack Instead of RecursionJava Interlude 3: More About GenericsThe Interface ComparableGeneric MethodsBounded Type ParametersWildcardsBounded WildcardsChapter 8: An Introduction to SortingOrganizing Java Methods That Sort an ArraySelection SortIterative Selection SortRecursive Selection SortThe Effciency of Selection SortInsertion SortIterative Insertion SortRecursive Insertion SortThe Effciency of Insertion SortInsertion Sort of a Chain of Linked NodesShell SortThe Java CodeThe Effciency of Shell SortComparing the AlgorithmsChapter 9: Faster Sorting MethodsMerge SortMerging ArraysRecursive Merge SortThe Effciency of Merge SortIterative Merge SortMerge Sort in the Java Class LibraryQuick SortThe Effciency of Quick SortCreating the PartitionImplementing Quick SortQuick Sort in the Java Class LibraryRadix SortPseudocode for Radix SortThe Effciency of Radix SortComparing the AlgorithmsJava Interlude 4: More About ExceptionsProgrammer-Defned Exception ClassesInheritance and ExceptionsThe finally BlockChapter 10: Queues, Deques, and Priority QueuesThe ADT QueueA Problem Solved: Simulating a Waiting LineA Problem Solved: Computing the Capital Gain in a Sale of StockJava Class Library: The Interface QueueThe ADT DequeA Problem Solved: Computing the Capital Gain in a Sale of StockJava Class Library: The Interface DequeJava Class Library: The Class ArrayDequeThe ADT Priority QueueA Problem Solved: Tracking Your AssignmentsJava Class Library: The Class PriorityQueueChapter 11: Queue, Deque, and Priority Queue ImplementationsA Linked Implementation of a QueueAn Array-Based Implementation of a QueueA Circular ArrayA Circular Array with One Unused LocationCircular Linked Implementations of a QueueA Two-Part Circular Linked ChainJava Class Library: The Class AbstractQueueA Doubly Linked Implementation of a DequePossible Implementations of a Priority QueueChapter 12: ListsSpecifcations for the ADT ListUsing the ADT ListJava Class Library: The Interface ListJava Class Library: The Class ArrayListChapter 13: A List Implementation That Uses an ArrayUsing an Array to Implement the ADT ListAn AnalogyThe Java ImplementationThe Effciency of Using an Array to Implement the ADT ListChapter 14: A List Implementation That Links DataOperations on a Chain of Linked NodesAdding a Node at Various PositionsRemoving a Node from Various PositionsThe Private Method getNodeAtBeginning the ImplementationThe Data Fields and ConstructorAdding to the End of the ListAdding at a Given Position Within the ListThe Methods isEmpty and toArrayTesting the Core MethodsContinuing the ImplementationA Refned ImplementationThe Tail ReferenceThe Effciency of Using a Chain to Implement the ADT ListJava Class Library: The Class LinkedListJava Interlude 5: Iterators What Is an Iterator?The Interface IteratorThe Interface IterableUsing the Interface IteratorIterable and for-each LoopsThe Interface ListIteratorThe Interface List RevisitedUsing the Interface ListIteratorChapter 15: Iterators for the ADT ListWays to Implement an IteratorA Separate Class IteratorAn Inner Class IteratorA Linked ImplementationAn Array-Based ImplementationWhy Are Iterator Methods in Their Own Class?An Array-Based Implementation of the Interface ListIteratorThe Inner ClassJava Interlude 6: Mutable and Immutable Objects Mutable ObjectsImmutable ObjectsCreating a Read-Only ClassCompanion ClassesChapter 16: Sorted ListsSpecifcations for the ADT Sorted ListUsing the ADT Sorted ListA Linked ImplementationThe Method addThe Effciency of the Linked ImplementationAn Implementation That Uses the ADT ListEffciency IssuesJava Interlude 7: Inheritance Further Aspects of InheritanceWhen to Use InheritanceProtected AccessAbstract Classes and MethodsPolymorphismChapter 17: Inheritance and ListsUsing Inheritance to Implement a Sorted ListDesigning a Base ClassCreating an Abstract Base ClassAn Effcient Implementation of a Sorted ListThe Method addChapter 18: SearchingThe ProblemSearching an Unsorted ArrayAn Iterative Sequential Search of an Unsorted ArrayA Recursive Sequential Search of an Unsorted ArrayThe Effciency of a Sequential Search of an ArraySearching a Sorted ArrayA Sequential Search of a Sorted ArrayA Binary Search of a Sorted ArrayJava Class Library: The Method binarySearchThe Effciency of a Binary Search of an ArraySearching an Unsorted ChainAn Iterative Sequential Search of an Unsorted ChainA Recursive Sequential Search of an Unsorted ChainThe Effciency of a Sequential Search of a ChainSearching a Sorted ChainA Sequential Search of a Sorted ChainA Binary Search of a Sorted ChainChoosing a Search MethodJava Interlude 8: Generics Once AgainMore Than One Generic TypeChapter 19: DictionariesSpecifcations for the ADT DictionaryA Java InterfaceIteratorsUsing the ADT DictionaryA Problem Solved: A Directory of Telephone NumbersA Problem Solved: The Frequency of WordsA Problem Solved: A Concordance of WordsJava Class Library: The Interface MapChapter 20: Dictionary ImplementationsArray-Based ImplementationsAn Unsorted Array-Based DictionaryA Sorted Array-Based DictionaryLinked ImplementationsAn Unsorted Linked DictionaryA Sorted Linked DictionaryChapter 21: Introducing HashingWhat Is Hashing?Hash FunctionsComputing Hash CodesCompressing a Hash Code into an Index for the Hash TableResolving CollisionsOpen Addressing with Linear ProbingOpen Addressing with Quadratic ProbingOpen Addressing with Double HashingA Potential Problem with Open AddressingSeparate ChainingChapter 22: Hashing as a Dictionary ImplementationThe Effciency of HashingThe Load FactorThe Cost of Open AddressingThe Cost of Separate ChainingRehashingComparing Schemes for Collision ResolutionA Dictionary Implementation That Uses HashingEntries in the Hash TableData Fields and ConstructorsThe Methods getValue, remove, and addIteratorsJava Class Library: The Class HashMapJave Class Library: The Class HashSetChapter 23: TreesTree ConceptsHierarchical OrganizationsTree TerminologyTraversals of a TreeTraversals of a Binary TreeTraversals of a General TreeJava Interfaces for TreesInterfaces for All TreesAn Interface for Binary TreesExamples of Binary TreesExpression TreesDecision TreesBinary Search TreesHeapsExamples of General TreesParse TreesGame TreesChapter 24: Tree ImplementationsThe Nodes in a Binary TreeA Class of Binary NodesAn Implementation of the ADT Binary TreeCreating a Basic Binary TreeThe Method privateSetTreeAccessor and Mutator MethodsComputing the Height and Counting NodesTraversalsAn Implementation of an Expression TreeGeneral TreesA Node for a General TreeUsing a Binary Tree to Represent a General TreeJava Interlude 9: Cloning Cloneable ObjectsCloning an ArrayCloning a ChainA Sorted List of ClonesCloning a Binary NodeChapter 25: A Binary Search Tree ImplementationGetting StartedAn Interface for the Binary Search TreeDuplicate EntriesBeginning the Class DefnitionSearching and RetrievingTraversingAdding an EntryA Recursive ImplementationAn Iterative ImplementationRemoving an EntryRemoving an Entry Whose Node Is a LeafRemoving an Entry Whose Node Has One ChildRemoving an Entry Whose Node Has Two ChildrenRemoving an Entry in the RootA Recursive ImplementationAn Iterative ImplementationThe Effciency of OperationsThe Importance of BalanceThe Order in Which Nodes Are AddedAn Implementation of the ADT DictionaryChapter 26: A Heap ImplementationReprise: The ADT HeapUsing an Array to Represent a HeapAdding an EntryRemoving the RootCreating a HeapHeap SortChapter 27: Balanced Search TreesAVL TreesSingle RotationsDouble RotationsImplementation Details2-3 TreesSearching a 2-3 TreeAdding Entries to a 2-3 TreeSplitting Nodes During Addition2-4 TreesAdding Entries to a 2-4 TreeComparing AVL, 2-3, and 2-4 TreesRed-Black TreesProperties of a Red-Black TreeAdding Entries to a Red-Black TreeJava Class Library: The Class TreeMapB-TreesChapter 28: GraphsSome Examples and TerminologyRoad MapsAirline RoutesMazesCourse PrerequisitesTreesTraversalsBreadth-First TraversalDepth-First TraversalTopological OrderPathsFinding a PathThe Shortest Path in an Unweighted GraphThe Shortest Path in a Weighted GraphJava Interfaces for the ADT GraphChapter 29: Graph ImplementationsAn Overview of Two ImplementationsThe Adjacency MatrixThe Adjacency ListVertices and EdgesSpecifying the Class VertexThe Inner Class EdgeImplementing the Class VertexAn Implementation of the ADT GraphBasic OperationsGraph AlgorithmsAppendix A: Documentation and Programming Style Naming Variables and ClassesIndentingCommentsSingle-Line CommentsComment BlocksWhen to Write CommentsJava Documentation CommentsAppendix B: Java Basics (online) IntroductionApplications and AppletsObjects and ClassesA First Java Application ProgramElements of JavaIdentifersReserved WordsVariablesPrimitive TypesConstantsAssignment StatementsAssignment CompatibilitiesType CastingArithmetic Operators and ExpressionsParentheses and Precedence RulesIncrement and Decrement OperatorsSpecial Assignment OperatorsNamed ConstantsThe Class MathSimple Input and Output Using the Keyboard and ScreenScreen OutputKeyboard Input Using the Class ScannerThe if-else StatementBoolean ExpressionsNested StatementsMultiway if-else StatementsThe Conditional Operator (Optional)The switch StatementEnumerationsScopeLoopsThe while StatementThe for StatementThe do-while StatementAdditional Loop InformationThe Class StringCharacters Within StringsConcatenation of StringsString MethodsThe Class StringBuilderUsing Scanner to Extract Pieces of a StringArraysArray Parameters and Returned ValuesInitializing ArraysArray Index Out of BoundsUse of = and == with ArraysArrays and the For-Each LoopMultidimensional ArraysWrapper ClassesAppendix C: Java Classes (online) Objects and ClassesUsing the Methods in a Java ClassReferences and AliasesDefning a Java ClassMethod DefnitionsArguments and ParametersPassing ArgumentsA Defnition of the Class NameConstructorsThe Method toStringMethods That Call Other MethodsMethods That Return an Instance of Their ClassStatic Fields and MethodsOverloading MethodsEnumeration as a ClassPackagesThe Java Class LibraryAppendix D: Creating Classes from Other Classes CompositionAdaptersInheritanceInvoking Constructors from Within ConstructorsPrivate Fields and Methods of the SuperclassOverriding and Overloading MethodsMultiple InheritanceType Compatibility and SuperclassesThe Class ObjectAppendix E: File Input and Output (online) PreliminariesWhy Files?StreamsThe Kinds of FilesFile NamesText FilesCreating a Text FileReading a Text FileChanging Existing Data in a Text FileDefning a Method to Open a StreamBinary FilesCreating a Binary File of Primitive DataReading a Binary File of Primitive DataStrings in a Binary FileObject SerializationGlossary (online)
