Introduction to Data Abstraction, Algorithms and Data Structures ++ With C and the STL Solutions to Exercises Fall 2016 Alexis Maciel Department of Computer Science Clarkson University Copyright (cid:13)c 2016 Alexis Maciel ii Contents Preface vii 1 Abstraction 1 1.1 A Pay Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.5 Modularity and Abstraction . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Data Abstraction 15 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Classes to Enforce Data Abstraction . . . . . . . . . . . . . . . . . . . 16 2.3 Classes to Support Object-Oriented Programming . . . . . . . . . . 19 2.4 Constant Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5 Inline Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.7 Get and Set Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.8 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.9 Compiling Large Programs . . . . . . . . . . . . . . . . . . . . . . . . 53 iii iv CONTENTS 2.10 The make Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3 Strings and Streams 57 3.1 C Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2 C++ Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3 I/O Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.4 String Streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4 Error Checking 69 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3 Input Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5 Vectors 75 5.1 A Simple File Viewer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2 Vectors in the STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.3 Design and Implementation of the File Viewer . . . . . . . . . . . . 81 5.4 Vectors and Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.5 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6 Generic Algorithms 83 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.3 Iterator Types and Categories . . . . . . . . . . . . . . . . . . . . . . . 86 6.4 Vectors and Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.5 Algorithms in the STL . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.6 Implementing Generic Algorithms . . . . . . . . . . . . . . . . . . . . 87 6.7 Initializer Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6.8 Function as Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 CONTENTS v 6.9 Function Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 7 Linked Lists 95 7.1 A Simple Text Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.2 Vector Version of the Text Editor . . . . . . . . . . . . . . . . . . . . . 95 7.3 Vectors and Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.4 Linked Lists in the STL . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.5 List Version of the Text Editor . . . . . . . . . . . . . . . . . . . . . . . 98 8 Maps 99 8.1 A Phone Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 8.2 Maps in the STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8.3 Design and Implementation of the Phone Book . . . . . . . . . . . . 101 9 Object-Oriented Design 103 10 Dynamically Allocated Arrays 105 10.1 The Size of Ordinary Arrays . . . . . . . . . . . . . . . . . . . . . . . . 105 10.2 The Dynamic Allocation of Arrays . . . . . . . . . . . . . . . . . . . . 105 10.3 Programming with Dynamically Allocated Arrays . . . . . . . . . . 106 11 Implementation of Vectors 109 11.1 A Basic Class of Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 109 11.2 Growing and Shrinking Vectors. . . . . . . . . . . . . . . . . . . . . . 111 11.3 Destroying and Copying Vectors . . . . . . . . . . . . . . . . . . . . . 113 11.4 Growing and Shrinking Vectors Efficiently . . . . . . . . . . . . . . . 116 12 Implementation of Linked Lists 117 12.1 Nodes and Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 12.2 Some Basic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 vi CONTENTS 12.3 Iterators, Insert and Erase . . . . . . . . . . . . . . . . . . . . . . . . . 124 12.4 Destroying and Copying Linked Lists . . . . . . . . . . . . . . . . . . 127 13 Analysis of Algorithms 129 13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 13.2 Measuring Exact Running Times . . . . . . . . . . . . . . . . . . . . . 129 13.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 13.4 Asymptotic Running Times . . . . . . . . . . . . . . . . . . . . . . . . 130 13.5 Some Common Running Times . . . . . . . . . . . . . . . . . . . . . . 131 13.6 Basic Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 13.7 Worst-Case and Average-Case Analysis . . . . . . . . . . . . . . . . . 134 13.8 The Binary Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . 135 14 Recursion 137 14.1 The Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 14.2 When to Use Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . 141 14.3 Tail Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 15 Sorting 145 15.1 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 15.2 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 15.3 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 15.4 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Preface This document contains solutions to the exercises of the course notes Introduc- tiontoDataAbstraction,AlgorithmsandDataStructures: WithC++andtheSTL. ThesenoteswerewrittenforthecourseCS142IntroductiontoComputerScience II taught at Clarkson University. The solutions are organized according to the same chapters and sections as the notes. Here’s some advice. Whether you are studying these notes as a student in a course or in self-directed study, your goal should be to understand the material well enough that you can do the exercises on your own. Simply studying the solutionsisnotthebestwaytoachievethis. Itismuchbettertospendareason- ableamountoftimeandefforttryingtodotheexercisesyourselfbeforelooking at the solutions. WhenanexerciseasksyoutowriteC++code,youshouldcompileitandtest it. In the real world, programmers don’t have solutions against which to check theircode. Testingisacriticaltoolforensuringthatcodeiscorrect,soyouneed practice it. Now, if you can’t do an exercise on your own, you should study the notes some more. If that doesn’t work, seek help from another student or from your instructor. Look at the solutions only to check your answer once you think you know how to do an exercise. vii viii PREFACE If you needed help doing an exercise, try redoing the same exercise later on your own. And do additional exercises. If your solution to an exercise is different from the official solution, take the time to figure out why. Did you make a mistake? Did you forget something? Did you discover another correct solution? If you’re not sure, ask for help from another student or the instructor. If your solution turns out to be incorrect, fix it, after maybe getting some help, then try redoing the same exercise later on your own and do additional exercises. Feedback on the notes and solutions is welcome. Please send comments to [email protected]. Chapter 1 Abstraction 1.1 A Pay Calculator There are no exercises in this section. 1.2 Design There are no exercises in this section. 1.3 Names There are no exercises in this section. 1 2 CHAPTER 1. ABSTRACTION 1.4 Implementation 1.4.5. bool is_later_than(const Time & t1, const Time & t2) { return difference(t1, t2) > 0; } 1.4.6. void add_minutes(Time & t, int num_minutes) { int t_in_minutes = t.hours ∗ 60 + t.minutes; t_in_minutes += num_minutes; t_in_minutes %= 1440; // 1440 = 24 ∗ 60 if (t_in_minutes < 0) t_in_minutes += 1440; t.hours = t_in_minutes / 60; t.minutes = t_in_minutes % 60; }