Data Structures With C++

Abstract Data Types -- Adt Format -- C++ Classes And Abstract Types -- Encapsulation And Information Hiding -- Message Passing -- Objects In C++ Applications -- Application: The Circle Class -- Object Design -- Objects And Composition -- C++ Geometric Classes -- Objects And Inheritance -- Inheritance In Programming -- Ordered Lists And Inheritance -- Software Reusability -- Seqlist And Orderedlist Class Specifications -- Applications With Class Inheritance -- Object-oriented Program Design -- Problem Analysis/program Definition -- Design -- Coding -- Testing -- Program Design Illustration: A Dice Graph -- Program Testing And Maintenance -- Object Testing -- Control Module Testing -- Program Maintenance And Documentation -- The C++ Programming Language -- Abstract Base Classes And Polymorphism -- Polymorphism And Dynamic Binding -- Written Exercises -- Basic Data Types -- Integer Types -- Computer Storage Of Integers -- Data In Memory -- C++ Representation Of Integers -- Character Types -- Ascii Characters -- Real Data Types -- Real Number Representations -- Enumerated Types -- Implementing C++ Enumerated Types -- Pointers -- Pointer Adt -- Pointer Values -- The Array Type -- The Built-in C++ Array Type -- Storage Of One-dimensional Arrays -- Array Bounds -- Two-dimensional Arrays -- Storage Of Two-dimensional Arrays -- String Literals And Variables -- C++ Strings -- Application: Reversing Names -- Records -- C++ Structures -- Files -- C++ Stream Hierarchy -- Array And Record Applications -- Sequential Search. Exchange Sort -- Counting C++ Reserved Words -- Written Exercises -- Programming Exercises -- Abstract Data Types And Classes -- The User Type Class -- Class Declaration -- Constructor -- Object Declaration -- Class Implementation -- Implementing A Constructor -- Building Objects -- Sample Classes -- The Temperature Class -- The Random Number Class -- Objects And Information Passing -- An Object As A Return Value -- An Object As A Function Parameter -- Arrays Of Objects -- The Default Constructor -- Multiple Constructors -- Case Study: Triangular Matrices -- Upper Triangular Matrix Properties -- Written Exercises -- Programming Exercises -- Collection Classes -- Describing Linear Collections -- Direct Access Collections -- Sequential Access Collections -- Generalized Indexing -- Describing Nonlinear Collections -- Group Collections -- Analysis Of Algorithms -- Performance Criteria -- Common Orders Of Magnitude -- The Sequential And Binary Search -- Binary Search -- The Basic Sequential List Class -- List Modification Methods -- Written Exercises -- Programming Exercises -- Stacks And Queues -- Stacks -- The Stack Class -- Expression Evaluation -- Postfix Evaluation -- Application: A Postfix Calculator -- Queues -- The Queue Class -- Priority Queues -- A Priority Queue Class -- Case Study: Event-driven Simulation -- Written Exercises -- Programming Exercises -- Abstract Operators -- Describing Operator Overloading -- Client-defined External Functions -- Class Members -- Friend Functions -- Rational Number System. Representing Rational Numbers -- Rational Number Arithmetic -- Rational Number Conversion -- The Rational Class -- Rational Operators As Member Functions -- Implementing The Rational Operators -- The Rational Stream Operators As Friends -- Implementing Rational Stream Operators -- Converting Rational Numbers -- Conversion To Object Type -- Conversion From Object Type -- Using Rational Numbers -- Written Exercises -- Programming Exercises -- Generic Data Types -- Template Functions -- Template-based Sort -- Template Classes -- Defining A Template Class -- Declaring Template Class Objects -- Defining Template Class Methods -- Template List Classes -- Infix Expression Evaluation -- Written Exercises -- Programming Exercises -- Classes And Dynamic Memory -- Pointers And Dynamic Data Structures -- The Memory Allocation Operator New -- Dynamic Array Allocation -- The Memory Deallocation Operator Delete -- Dynamically Allocated Objects -- Deallocating Object Data: The Destructor -- Assignment And Initialization -- Assignment Issues -- Overloading The Assignment Operator -- The This Pointer -- Initialization Issues -- Creating A Copy Constructor -- Safe Arrays -- The Array Class -- Memory Allocation For The Array Class -- Array Bounds Checking And The Overloaded [] Operator -- Converting An Object To A Pointer -- Using The Array Class -- A String Class -- String Class Implementation -- Pattern Matching -- The Find Process -- Pattern Matching Algorithm -- Analysis Of The Pattern Matching Algorithm -- Integral Sets. Sets Of Integral Types -- C++ Bit Handling Operators -- Representing Set Elements -- The Sieve Of Eratosthenes -- Set Class Implementation -- Written Exercises -- Programming Exercises -- Linked Lists -- Describing A Linked List -- Chapter Overview -- The Node Class -- Declaring A Node Type -- Implementing The Node Class -- Building Linked Lists -- Creating A Node -- Inserting A Node: Insertfront -- Traversing A Linked List -- Inserting A Node: Insertrear -- Application: Student Graduation List -- Creating An Ordered List -- Application: Sorting With Linked Lists -- Designing A Linked List Class -- Linked List Data Members -- Linked List Operations -- The Linkedlist Class -- Implementing The Linkedlist Class -- Implementing Collections With Linked Lists -- Linked Queues -- Implementing Queue Methods -- Linked Seqlist Class -- Implementing Seqlist Data Access Methods -- Application: Comparing Seqlist Implementations -- Case Study: A Print Spooler -- Implementing The Spooler Update Method -- Spooler Evaluation Methods -- Circular Lists -- Circular Node Class Implementation -- Application: Solving The Josephus Problem -- Doubly Linked Lists -- Application: Doubly Linked List Sort -- Dnode Class Implementation -- Case Study: Window Management -- The Window List -- Windowlist Class Implementation -- Written Exercises -- Programming Exercises -- Recursion -- The Concept Of Recursion -- Recursive Definitions -- Recursive Problems -- Designing Recursive Functions -- Recursive Code And The Runtime Stack -- The Runtime Stack. Problem-solving With Recursion -- Binary Search -- Combinatorics: The Committee Problem -- Combinatorics: Permutations -- Maze Handling -- Maze Class Implementation -- Evaluating Recursion -- Written Exercises -- Programming Exercises -- Trees -- Tree Terminology -- Binary Trees -- Binary Tree Structure -- Designing A Treenode Class -- Building A Binary Tree -- Designing Treenode Functions -- Recursive Tree Traversals -- Using Tree Scan Algorithms -- Application: Visiting Tree Nodes -- Application: Tree Print -- Application: Copying And Deleting Trees -- Application: Upright Tree Printing -- Binary Search Trees -- The Key In A Binary Search Tree Node -- Operations On A Binary Search Tree -- Declaring A Binary Search Tree Adt -- Using Binary Search Trees -- Duplicate Nodes -- The Binstree Implementation -- List Operations -- Case Study: Concordance -- Written Exercises -- Programming Exercises -- Inheritance And Abstract Classes -- A View Of Inheritance -- Class Inheritance Terminology -- Inheritance In C++ -- Constructors And Derived Classes -- What Cannot Be Inherited -- Polymorphism And Virtual Functions -- Demonstrating Polymorphism -- Application: Geometric Figures And Virtual Methods -- Virtual Methods And The Destructor -- Abstract Base Classes -- Abstract Base Class -- List -- Deriving Seqlist From Abstract Base Class List -- Iterators -- The Iterator Abstract Base Class -- Deriving List Iterators -- Building The Seqlist Iterator -- Array Iterator -- Application: Merging Sorted Runs -- Arrayiterator Implementation. Ordered Lists -- Orderedlist Class Implementation -- Heterogeneous Lists -- Heterogeneous Arrays -- Heterogeneous Linked Lists -- Written Exercises -- Programming Exercises -- Advanced Nonlinear Structures -- Array-based Binary Trees -- Application: The Tournament Sort -- Heaps -- The Heap As A List -- The Heap Class -- Implementing The Heap Class -- Application: Heap Sort -- Priority Queues -- Application: Long Runs -- Avl Trees -- Avl Tree Nodes -- The Avl Tree Class -- Memory Allocation For The Avltree -- Evaluating Avl Trees -- Tree Iterators -- The Inorder Iterator -- Inorderiterator Class Implementation -- Application: Treesort -- Graphs -- Connected Components -- The Graph Class -- Declaring A Graph Adt -- Graph Class Implementation -- Graph Traversals -- Applications -- Reachability And Warshall's Algorithm -- Written Exercises -- Programming Exercises -- Organizing Collections -- Basic Array Sorting Algorithms -- The Selection Sort -- The Bubble Sort -- The Insertion Sort -- Quicksort -- Quicksort Description -- Quicksort Algorithm -- Comparison Of Array Sort Algorithms -- Hashing -- Keys And A Hash Function -- Hashing Functions -- Other Hash Methods -- Collision Resolution -- Hash Table Class -- Application: String Frequency -- Hashtable Class Implementation -- Hashtableiterator Class Implementation -- The Performance Of Searching Methods -- Binary Files And External Data Operations -- Binary Files -- The Binfile Class -- External File Searching -- External File Sort -- Long Run Mergesort. Dictionaries -- Written Exercises -- Programming Exercises -- Answers To Selected Exercises. By William Ford/william Topp. Includes Bibliographical References And Index. Includes Bibliographical References (pages 882-883) And Index.