Beginning Data Structures in C++ Full Table of Contents

(With page numbers)

Chapter 1

Functional Abstraction Review of Two-dimensional Arrays 1
Introduction 1
A Review of Two-dimensional Arrays 2
Functional Abstraction 4
Reusable Software 5
Functional Decomposition 6
Coding the Functions 10
Coding the Function Prototype 10
Use of the const Qualifier 12
The In/Out Aspects of a Function’s Parameters 13
The Optional Variable Names in a Prototype 13
Coding the Function Header 14
Documenting a Function 14
Stub Testing 16
Testing Oracles 17
The Complete Program 18
Additional Error Handling 22
Review Questions 24
Stop! Do These Exercises Before Programming 26
Programming Problems 28

 

Chapter 2 Mechanics of Functional Abstraction 29

Introduction 29
User Written Header Files 30
Mechanics of Header File Construction 31
Placement of Header File Includes in a Cpp File 33
#ifndef/#define or #pragma once Logic 34
#pragma once 37
Multiple Cpp Files in a Program 39
Application Header Files 40
An Example: Stock On-hand Analysis Program 40
A Set of Testing Oracles for Pgm02a 49
Abstraction Barriers, Information Hiding, and Locality of Variables 50
The Locality of a Variable 51
On Debugging a Larger Program Using the assert Macro 53
Review Questions 54
Stop! Do These Exercises Before Programming 57
Programming Problems 62
Matrix Math Operations Summary 64

 

Chapter 3 Pointers and Dynamic Memory Allocation 72

Introduction 72
Pointer Basics 73
Defining Pointer Variables 73
Initializing Pointers 74
Dereferencing a Pointer 75
The Rules of Pointer Arithmetic 76
The Impact of Pointers on a Program 81
The Use of Hybrids and Dual Incrementing 82
Arrays of Pointers 83
Handling Command Line Parameters in the main() Function 84
Dynamic Memory Allocation 85
The Location of the Heap 87
Do We Need to Check for Successful Allocation? 87
Dynamic Allocation of Arrays 88
Memory Leaks 90
Checking for Memory Leaks with Visual C++ 6 0 and NET 91
Checking for Memory Leaks with Borland C++ 5 0 91
The Use of the const Keyword with Pointers 92
A Complete Example Using Dynamic Memory Allocation 93
Review Questions 103
Stop! Do These Exercises Before Programming 106
Programming Problems 108

 

Chapter 4 Recursive Functions 111

Introduction 111
Recursive Definitions 111
Recursive Functions 113
Recursion to Calculate N! 113
Stack Overflow Infinite Recursion 115
Reversing Characters Entered by the User 115
Summing all Even Integers from 2 to N 116
Speed Issues 117
Using Recursive Functions to Handle Situations Not Easily Programmed Otherwise 117
Pgm04a Making Folders 117
Pgm04b Removing Empty Folders 122
Review Questions 125
Stop! Do These Exercises Before Programming 125
Programming Problems 127

 

Chapter 5 Data Abstraction an Overview 130

Introduction 130
Data Types and Data Structures the Relationship 131
An Overview of Data Structures 134
Arrays 136
Records 137
Lists 138
Stacks 140
Queues 142
Sets 144
Memory Limitations 145
Implementation Details 146
Review Questions 147
Stop! Do These Exercises Before Programming 148

 

Chapter 6 Structures 151

Introduction 151
Structures as a Record of Data 151
A Growable Array of Structures 155
Handling a Variable Number of Command Line Arguments 160
Pgm06a Acme Weekly Sales Summary Report 160
The String Stream Classes 169
Unions an Advanced Feature of Structures 170
Variant Records 171
Review Questions 190
Stop! Do These Exercises Before Programming 192
Programming Problems 194

 

Chapter 7 Classes (ADT) I 198

Introduction 198
C++ Class Syntax Summary 201
Constructor and Destructor Functions 203
The Implementation File 204
Access Functions 205
Instantiating Classes 206
Objects (Instances of a Class) Can Be Passed to Functions and Returned 207
Initializing Arrays of Objects 208
Function Overloading 208
Default Arguments 210
Constant Member Functions 212
Handling I/O Operations a First Look 214
A Practical Example The Class Rectangle 215
Practical Example 2 The Interval Timer Class (Pgm07b) 226
Review Questions 230
Stop! Do These Exercises Before Programming 231
Programming Problems 233

 

Chapter 8 Classes (ADT) II A Growable Array 236

Introduction 236
Using #ifndef-#define or #pragma once Logic in Class Header Files 236
The this Pointer 238
Operator Overloading 240
Overloading Binary Operators (such as + and ) 241
Using Friend Functions to Handle Overloading Normal Data Types 243
Overloading the Relational Operators 244
Overloading the I/O Insertion and Extraction Operators (<< and >>)244
Overloading the Assignment Operator 245
Using Class enums 249
Designing a Generic Growable Array Class 251
Inline Functions 267
Making Production Libraries 269
A Practical Example Illustrating How Client Programs Must Use the Array Class (Pgm08d) 269
Review Questions 276
Stop! Do These Exercises Before Programming 278
Programming Problems 281

 

Chapter 9 Linked Lists Single 285

Introduction 285
Maintaining a Student Class Roster as a Single Linked List 287
The Revised Student Roster Class Pgm09b 303
Adding Support for the Copy Constructor and Assignment Operator Pgm09c 312
A Linked List Written for a Specific Program Versus a Generic
Reusable Single Linked List Container 316
Review Questions 318
Stop! Do These Exercises Before Programming 319
Programming Problems 322

 

Chapter 10 Linked Lists Double 326

Introduction 326
Designing a Double Linked List Class 326
Methods of Storing the Client Data in a Node 327
Method A Storing a Copy of the Client’s Data in the Node 327
Method B Storing a Pointer to the Client’s Data in the Node 328
Method C Storing a void Pointer to the Client’s Data in the Node329
Designing the Reusable Double Linked List Class 330
Providing a Find Matching List Item Function 330
Handling the Insertions into the List 333
Deleting the Current Node 337
Adding a Debugging Feature 339
The Generic DoubleLinkedList Class 340
A Testing Oracle and Program 352
Writing Client Programs that Use the Double Linked List Class 361
Review Questions 375
Stop! Do These Exercises Before Programming 376
Programming Problems 378

 

Chapter 11 Stacks 382

Introduction 382
The Palindrome Analysis Program and a Simple Letter Stack 384
The LetterStack Class 385
Traversing a Maze Problem A More Complicated Stack Example 392
A Generic Stack Class 402
Review Questions 411
Stop! Do These Exercises Before Programming 412
Programming Problems 413

 

Chapter 12 Queues 418

Introduction 418
Designing a Reusable Generic Queue Class 419
The Queue Class Implementation 422
A Modification to the Queue Class A Priority Queue 427
The Full-Course Waiting List Client Program, Pgm12a 429
Review Questions 435
Stop! Do These Exercises Before Programming 436
Programming Problems 440

 

Chapter 13 Binary Files and Hashing Techniques 443

Introduction 443
Dealing with Binary Files 443
C++ Mechanics of Binary File Operations 444
Physical I/O Versus Logical I/O Operations 446
Example 1: Reading and Writing Several Arrays to/from One Binary File 450
Example 2: Processing an Array of Cost Records Blazingly Fast 451
Example 3: Using Dynamic Allocation for an Array of Unknown Number of Records 452
Example 4: Binary File Processing the StudentRoster Single Linked List Pgm13a 453
Overview of Direct Access File Processing Operations 458
The Relative Record Number Method 458
The Remainder Method 460
The Indexed Sequential Access Method (ISAM) 462
Handling Variable Length Records 463
Handling Update Files in C++ 463
Pgm13b the Master File Update Program Relative Record Method464
Structure Alignment 471
Implementing the Remainder Method of Direct File Processing Hashing Theory 474
Hashing 477
Pgm13c Direct File Processing in Action 479
Review Questions 492
Stop! Do These Exercises Before Programming 494
Programming Problems 498

 

Chapter 14 Trees 501

Introduction 501
Tree Notation 501
Binary Trees 504
Methods of Binary Tree Traversal 506
Inorder Traversal 506
The Preorder Traversal 507
The Postorder Traversal 507
The ~BinaryTree() Function 507
Binary Search Trees 508
The Heap Tree 509
Building a Binary Search Tree 511
Determine the Height and the Number of Nodes in a Tree 513
Pgm14a The BinaryTree Class and Tester Program 514
Pgm14b the Account Inquiry Application Loading a Binary Search Tree from a Sorted ISAM Index File 529
Multiple Projects in the Same Workspace 540
Review Questions 542
Stop! Do These Exercises Before Programming 543
Programming Problems 548

 

Chapter 15 Sorting Algorithms 551

Introduction 551
The Straight Selection Sort 552
The Bubble Sort 554
The Quicksort Method 556
Shellsort 561
Heapsort 562
Pgm15a Tester Program for the Different Sorting Methods 564
Benchmarks 570
Review Questions 578
Stop! Do These Exercises Before Programming 579
Programming Problems 580

 

Appendix A A Review of Array and Structure Processing 581

A Review of Single Dimensioned Array Operations 581
Using an Array for Direct Lookup Operations 581
Parallel Arrays and Sequential Searches Inquiry Programs 582
Inserting Another Element into an Unsorted Array 583
Ordered (Sorted) Lists 585
The Binary Search Method 585
Inserting New Data into a Sorted List 586
A Review of Two-dimensional Array Processing 588
Defining Multidimensional Arrays 588
Physical Memory Layout Versus Logical Layout 589
Initialization of Multidimensional Arrays 590
Passing Multidimensional Arrays to Functions 591
Loading a Multidimensional Array from an Input File 592
Working with Multidimensional Arrays 593
A Review of Structures 597
Defining Structures 597
Creating Instances of a Structure 598
A Structure Can Contain Instances of Other Structures 599
How are Structure Instances Initialized? 600
How are Structure Members Accessed? 600
Rules of Use for Structure Variables 601
Appendix B How to Use Microsoft’s Visual C++ 6 605
Appendix C How to Use Microsoft’s ( NET) Visual C++ 7 0 Compiler 624
Index 647