|< Free Open Study >|
In this chapter, we created two abstract data types that represent lists. The Unsorted List ADT assumes that the list elements are not sorted by key; the Sorted List ADT assumes that the list elements are sorted by key. We viewed each ADT from three perspectives: the logical level, the application level, and the implementation level. The extended Case Study used the Sorted List ADT and the String ADT from Chapter 2 in a problem. Figure 3.15 shows the relationships among the three views of the list data in the Case Study.
To make the software as widely reusable as possible, the specification of each ADT states that its user must prepare a class that defines the objects included in each container class. A member function ComparedTo that compares two objects of this class must be included in the definition. This function returns one of the constants in RelationType: LESS, EQUAL, or GREATER. Because the user must provide this information about the objects on the list, the code of the ADTs is very general. The Unsorted List and Sorted List ADTs can process items of any kind; they are completely context independent. The Case Study demonstrated the value of this independence.
We compared the operations on the two ADTs using Big-O notation. Insertion into an unsorted list has order O(1); insertion into a sorted list has order O(N). Deletions from both types of lists have order O(N). Searching in the unsorted list has order O(N); searching in a sorted list has order O(log2N) if we use a binary search.
The relational operators can be overloaded, allowing us to compare values of different types using the standard symbols.
This chapter also described a four-stage object-oriented design methodology. Brainstorming involves coming up with a possible set of object classes for the problem solution. In filtering, we reexamine the tentative classes, eliminating those that are not appropriate, combining some classes, and creating additional classes if necessary. With scenarios, we examine the responsibilities of each proposed class and role play to see whether all situations are covered. In the responsibility algorithms phase, algorithms are derived to carry out the responsibilities. CRC cards are used as a visual means of recording classes and their responsibilities. This methodology was applied to the Case Study.
|< Free Open Study >|
|Converted from CHM to HTML with chm2web Pro 2.85 (unicode)|