Previous Section
 < Free Open Study > 
Next Section


Changes in the Third Edition

The third edition incorporates the following changes:

Object-oriented constructs moved forward: In the last five years, object-oriented programming has become part of the first-year curriculum, as demonstrated by its inclusion in all variations of the first year outlined in the Computing Curricula 2001 developed by the Joint Task Force of the IEEE Computer Society and the Association for Computing Machinery. Accordingly, the class concept has moved into the first semester. Because of this, we assume that students have had experience using classes, and we therefore moved much of the discussion of how to define and access classes to a sidebar. We have kept a small discussion in the main text. Many students have already seen inheritance and polymorphism, but the concepts are too important to move to a sidebar, so we have moved them from Chapter 6 to Chapter 2.

More emphasis on object-oriented design: Object-oriented design is a hard topic for most students, because people usually think procedurally in their lives. Because of this, we introduce a methodology with four phases: brainstorming, during which the possible objects in a problem are isolated; filtering, during which the set of possible objects are reexamined to look for duplicates and/or missing objects; scenarios, during which hand simulations of the processing take place asking "what if" questions and assigning responsibilities to classes; and responsibility algorithms, during which the algorithms for the classes are designed. We use CRC cards to capture the results of the four-phase process. The output from the scenarios phase is a CRC card for each class. The CRC card lists the responsibilities of the class and any other classes with which the class must collaborate, hence the name CRC: class, responsibility, collaboration.

More practical emphasis on testing: The concept of a multipurpose test driver is introduced in Chapter 1. After a test plan has been designed, it is implemented as input to the test driver. Throughout the rest of the book, this technique is used to test the ADTs. The drivers, the input data, and the output data are available on the book's web site: http://computerscience.jbpub.com/cppDataStructures

Reduced use of templates: The concept of generic data types, as implemented in C++ using templates, is very important. Making every ADT a class template after templates are introduced in Chapter 4, however, inserts an unnecessary complexity into already complex code. Thus, when introducing a new construct such as a linked list or a binary search tree, we have chosen to use classes rather than class templates. Subsequent implementations of a construct are often in the form of class templates, or the student is asked to transform a class into a class template in the exercises.

Nonlinked binary tree representation covered with binary trees: The nonlinked representation of a binary tree is an important concept within its own right, not just as an implementation for a heap. This implementation, therefore, is covered in Chapter 8 with other tree implementation techniques.

Removal of material on binary expression trees: Although interesting applications of trees, binary expression trees do not fit into the discussion of abstract data types. Thus, we have moved this discussion to the web site.

Inclusion of the ADT set: The exclusion of the ADT set has been an omission from previous editions. Not only is a set an interesting mathematical object, but there are interesting implementation issues. We propose two implementations, one explicit (bit vector) and one implicit (list-based).



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)