Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Abstraction. . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Abstract Data Types . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 General Definitions . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 The Date Abstract Data Type . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Defining the ADT . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Using the ADT . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Preconditions and Postconditions . . . . . . . . . . . . . . . 9
1.2.4 Implementing the ADT . . . . . . . . . . . . . . . . . . . . . 10
1.3 Bags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 The Bag Abstract Data Type . . . . . . . . . . . . . . . . . 15
1.3.2 Selecting a Data Structure . . . . . . . . . . . . . . . . . . 17
1.3.3 List-Based Implementation . . . . . . . . . . . . . . . . . . 19
1.4 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.1 Designing an Iterator . . . . . . . . . . . . . . . . . . . . . 21
1.4.2 Using Iterators . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Application: Student Records . . . . . . . . . . . . . . . . . . . . . 23
1.5.1 Designing a Solution . . . . . . . . . . . . . . . . . . . . . . 23
1.5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 26