Advanced Data Structures in C++ Long Table of Contents

Advanced Data Structures in C++ Long Table of Contents

Back to previous book promo page

(with page numbers)

Chapter 1 — A Review of Classes…… 1

Introduction……….. 1
Class Syntax……….. 2
The Three Access Qualifiers……….. 3
Constructors and Destructors……….. 4
The Implementation File……….. 6
Access Functions……….. 8
Instantiating Classes……….. 9
Initializing Arrays of Objects……….. 11
Assigning Instances……….. 12
Objects (Instances of a Class) Can Be Passed to Functions and Returned……….. 13
Constant Member Functions……….. 14
Default Arguments……….. 16
Operations Functions — Handling I/O Operations — A First Look……….. 17
Using Instances of Another Class as Data Members in Another Class……….. 19
Practical Example 1 — The Class Rectangle (Pgm01a)……….. 20
Practical Example 2 — The Interval Timer Class (Pgm01b)……….. 29
Review Questions……….. 33
Stop! Do These Exercises Before Programming……….. 35
Programming Problems……….. 37

 

Chapter 2 — Advanced Features of Classes…. 45

Introduction……….. 45
Using #ifndef-#define Logic in Class Header Files……….. 45
The this Pointer……….. 47
When Classes Contain References or Pointers or Instances of Other Classes — Forward references……….. 49
Using Class enums……….. 53
Friend Functions……….. 55
Constant Data Members……….. 56
The Copy Constructor and How to Forbid Certain Constructors……….. 58
Reference Variables as Data Members……….. 61
Static Data Members and Static Member Functions……….. 63
Static Member Data……….. 63
Static Member Functions……….. 66
Inline Functions……….. 70
Implicit Type Conversions……….. 72
Summary of Constructor and Destructor Functions……….. 73
Practical Example 1 — Dice and Die Rolling……….. 74
Making Production Libraries……….. 83
Review Questions……….. 83
Stop! Do These Exercises Before Programming 85
Programming Problems……….. 88

 

Chapter 3 — Operator Overloading….. 98

Introduction……….. 98
Overloading Binary Operators……….. 99
Overloading the Math Binary Operators (such as + and –)……….. 99
Using Friend Functions to Handle Overloading Normal Data Types……….. 103
The Subtraction Operator……….. 104
Overloading the += and Similar Operators……….. 106
Overloading the Relational Operators……….. 106
Overloading the Insertion and Extraction Operators — << and >>……….. 107
The Assignment Operator……….. 108
Overloading the Unary Operators……….. 108
Overloading the Inc and Dec Operators……….. 109
Overloading the Unary – Operator……….. 110
The Time Class — A Complete Programming Example……….. 110
Classes with Dynamic Memory Allocation……….. 124
Coding the Copy Constructor and Operator= Functions……….. 127
Overloading the [] Operator……….. 128
Overloading the & Address Operator……….. 129
Operator Conversion Functions……….. 130
Pgm03b — String Class Thus Far……….. 132
Reviewing the Basic Generic Growable Array Class……….. 137
Review Questions……….. 145
Stop! Do These Exercises Before Programming……….. 147
Programming Problems……….. 149

 

Chapter 4 — Inheritance 154

Introduction……….. 154
Principles of Inheritance……….. 156
Working With Inherited Member Functions……….. 160
Copy Constructors……….. 162
The Assignment Operator Implementation……….. 162
Problems When Client Programs Use Base Class Pointers……….. 163
Virtual Functions……….. 164
I/O Operations with Derived Classes Demand Virtual Functions……….. 169
Destructors……….. 174
How the Virtual Function Mechanism Is Implemented……….. 174
Early Binding and Late Binding……….. 175
Animals — A Complete Example with Dynamic Memory Allocation and Virtual Functions — Pgm04b……….. 176
Review Questions……….. 194
Stop! Do These Exercises Before Programming……….. 196
Programming Problems……….. 197

 

Chapter 5 — Abstract Base Classes.. 202

Abstract Base Class — Shapes — a Complete Example — Pgm05a……….. 202
The Abstract Base Class Shape and Its Derived Classes Development Steps……….. 202
Adding Operational Functions……….. 204
Handling Input and Output……….. 207
The Actual Implementation of Shape and Its Derived Classes……….. 213
Writing the Client Tester Program Pgm05a……….. 222
Multiple Inheritance……….. 227
Adding Multiple Base Classes to Shapes……….. 228
The Microsoft I/O Stream Classes……….. 229
Review Questions……….. 237
Stop! Do These Exercises Before Programming……….. 238
Programming Problems……….. 239

 

Chapter 6 — C++ Error Handling 245

Introduction……….. 245
Typecasting — Static and Dynamic……….. 245
Invoking Derived Class Functions That Are Not Virtual or Defined in the Base Class……….. 246
To Use dynamic_cast with the Microsoft VC6.0 Compiler……….. 247
Run-Time Type Information……….. 247
The C++ Error Handling System……….. 248
Details of the try-catch-throw Mechanism……….. 253
Replacing the Default terminate Function and the Default unexpected Functions……….. 254
Overloading the new and delete Functions……….. 256
Throwing Class Instances……….. 257
Handling Error Situations Where Multiple Dynamic Memory Allocations Exist……….. 261
Review Questions……….. 264
Stop! Do These Exercises Before Programming……….. 266
Programming Problems……….. 268

 

Chapter 7 — A Review of the Basic Container Classes.. 270

Introduction……….. 270
Container Class Design Principles……….. 270
The Growable Array Container Class……….. 273
The Double Linked List Container……….. 281
Providing a Find Matching List Item Function……….. 284
Handling the Insertions into the List……….. 287
Deleting the Current Node……….. 291
The Stack Container……….. 305
The Queue Container Class……….. 311
Review Questions……….. 317
Stop! Do These Exercises Before Programming……….. 319
Programming Problems……….. 323

 

Chapter 8 — Templates 328

Introduction……….. 328
Specializing a Template……….. 331
Template Classes……….. 332
Pgm12a — a Linked List Practical Example of a Template Class……….. 333
Creating a Client Program Using the Template Double Linked List……….. 345
Review Questions……….. 362
Stop! Do These Exercises Before Programming……….. 362
Programming Problems……….. 364

 

Chapter 9 — Binary Files and Hashing Techniques… 365

Introduction……….. 365
Dealing with Binary Files……….. 365
C++ Mechanics of Binary File Operations……….. 366
Physical I/O Versus Logical I/O Operations………… 368
Example 1: Reading and Writing Several Arrays to/from One Binary File……….. 372
Example 2: Processing an Array of Cost Records Blazingly Fast……….. 373
Example 3: Using Dynamic Allocation for an Array of Unknown Number of Records……….. 374
Example 4: Binary File Processing — the StudentRoster Linked List — Pgm09a………. 375
Overview of Direct Access File Processing Operations……….. 389
The Relative Record Number Method……….. 389
The Remainder Method……….. 390
The Indexed Sequential Access Method (ISAM)……….. 392
Handling Variable Length Records……….. 393
Handling Update Files in C++……….. 394
Pgm09b — the Master File Update Program — Relative Record Method……….. 394
Structure Alignment……….. 401
Implementing the Remainder Method of Direct File Processing — Hashing Theory……….. 405
Hashing……….. 408
Pgm09c — Direct File Processing in Action……….. 410
A Final Thought on Direct File Processing……….. 422
Review Questions……….. 423
Stop! Do These Exercises Before Programming……….. 425
Programming Problems……….. 429

 

Chapter 10 — Trees… 432

Introduction……….. 432
Tree Notation……….. 432
Binary Trees……….. 435
Methods of Binary Tree Traversal……….. 437
Inorder Traversal……….. 437
The Preorder Traversal……….. 438
The Postorder Traversal 438
The ~BinaryTree Function……….. 438
Binary Search Trees……….. 439
The Heap Tree……….. 440
Building a Binary Search Tree……….. 442
Determine the Height and the Number of Nodes in a Tree……….. 444
Pgm10a — The BinaryTree Class and Tester Program……….. 445
Pgm10b – the Account Inquiry Application
Loading a Binary Search Tree from a Sorted ISAM Index File……….. 461
Multiple Projects in the Same Workspace……….. 474
Review Questions……….. 476
Stop! Do These Exercises Before Programming……….. 477
Programming Problems……….. 482

 

Chapter 11 — Sorting Algorithms… 485

Introduction……….. 485
The Straight Selection Sort……….. 486
The Bubble Sort……….. 488
The Quicksort Method……….. 490
Shellsort……….. 495
Heapsort……….. 496
Pgm11a — Tester Program for the Different Sorting Methods……….. 498
Benchmarks……….. 504
Review Questions……….. 513
Stop! Do These Exercises Before Programming……….. 514
Programming Problems……….. 515

 

Chapter 12 — B-trees and AVL Trees… 517

Introduction……….. 517
The B-Tree……….. 518
The 2-3 Tree as a Simplification of the B-tree Process……….. 518
The B-tree Algorithm……….. 520
Inserting a Node……….. 521
The Process of Deleting a Key……….. 524
Deleting a Key from a Leaf……….. 524
Deleting a Key from a Non-leaf……….. 526
The Complete Algorithm for Key Deletion……….. 526
Summary of B-trees……….. 527
AVL Trees……….. 527
Designing an AVL Tree……….. 532
Using an INL Header File……….. 532
The AVLTree Class Definition……….. 533
The Value of Instruction Comments……….. 549
Review Questions……….. 566
Stop! Do These Exercises Before Programming……….. 567
Programming Problems 568

 

Chapter 13 — Heaps, Priority Queues, and Graphs… 570

Introduction……….. 570
Heaps……….. 571
Implementation of a Heap……….. 575
A Priority Queue Based Upon a Heap……….. 582
Graphs……….. 590
Basic Graph Terminology……….. 590
Graph Basic Operations……….. 592
Data Structures to Represent Graphs……….. 595
How Do We Design a Graph Data Structure?……….. 597
The Graph Basic Functions’ Implementation……….. 605
Advanced Graph Functions……….. 617
Pgm13b — A Sample Application — Airline Routes……….. 644
Review Questions……….. 664
Stop! Do These Exercises Before Programming……….. 665
Programming Problems……….. 668

 

Chapter 14 — Of Sets and Maps… 670

Introduction……….. 670
Implementations of a Set……….. 672
The Set as an Array Implementation……….. 673
A Set Implemented as a Bit Vector……….. 686
The Map Data Structure……….. 698
Putting a Map to Use — the Beginnings of Data Compression Theory……….. 705
Review Questions……….. 716
Stop! Do These Exercises Before Programming……….. 717
Programming Problems……….. 718

 

Chapter 15 — An Introduction to the STL — Standard Template Library… 719

Introduction……….. 719
The Container Classes……….. 720
The vector STL Class……….. 721
Iterators……….. 725
Details of the begin and end Functions……….. 726
Using a Range of Iterators……….. 727
The list Container……….. 728
Algorithms……….. 734
The deque Container……….. 736
Review Questions……….. 740
Stop! Do These Exercises Before Programming……….. 741
Programming Problems……….. 744

 

Chapter 16 — Complex Analysis 747

Introduction 747
Beginning Axioms of Program Execution Efficiency……….. 748
Linear Loops……….. 748
Logarithmic Loops……….. 749
Nested Linear Loops……….. 750
Nested Linear Logarithmic Loops……….. 750
Dependent Quadratic Loops……….. 751
Big O Notation……….. 751
Matrix Algebra……….. 753
Matrix Math Operations Summary……….. 753
Matrix Addition……….. 755
Matrix Multiplication……….. 755
A Pitfall of Big-O Analysis……….. 756
Applications of Big-O……….. 756
Review Questions……….. 763
Stop! Do These Exercises Before Programming……….. 764

 

Appendix

Using Microsoft’s VC 7 (.NET) Compiler 768
C++ DOS Console Applications……….. 768
Making a New Programming Solution —
I Am Building a New Program……….. 769
Continue to Work on an Existing Program — Starting Visual Studio……….. 773
Bringing Files From Home to School……….. 774
Building a New Project in Which the Cpp Files Already Exist……….. 774
Compiling and Running Your Program……….. 775
Executing a DOS Console Program……….. 777
Getting Source File Printouts……….. 777
Getting a Printed Copy of the Program Execution Output……….. 778
Case 1: The Entire Output Fits on One Screen Without Scrolling……….. 778
Case 2: Using cout and There Are Too Many Lines To Capture With a Screen Shot……….. 778
Case 3: Using an Output File Stream……….. 779
Visual Studio Operational Tips……….. 780
Debug Versus Release Builds……….. 783
A Primer on Using the Debugger……….. 784
Index.. 791

Back to previous book promo page

Share Button