Figure 2. A sorted list graphical representation
Spring Quarter 2003 / Class webpage
Remember:
Chapter 3* introduced the ADT sorted list, which mantains its data in sorted order. For example, a sorted list of names would be maintained in alphabetical order, and a sorted list of number would be maintained either in increasing or decreasing order. The operations for a sorted list are summarized on figure 1.
// ListItemType is the type of the items stored in the list.
+createSortedList()
// Creates an empty sorted list.
+destroySortedList ()
// Destroys a sorted list.
+sortedIsEmpty():boolean { query }
// Determines whether a sorted list is empty.
+sortedGetLength(): integer { query }
// Returns the number of items that are in a sorted list
+sortedInsert(in newItem:ListItemType,
out success:boolean)
// Inserts newItem into its proper sorted position in a
// sorted list. The success flag indicates whether the
// insertion was successful.
+sortedRemove(in anItem:ListItemType,
out success:boolean)
// Deletes anItem from a sorted list. The success flag
// indicates whether the deletion was successful.
+sortedRetrieve(in index:integer,
out dataItem:ListItemType,
out success:boolean) { query }
// Sets dataItem to be item at position index of a sorted
// list, if 1 <= index <= sortedGetLength(). The list is left
// unchanged by this operation. The success flag indicates
// whether the retrieval was successful.
+locatePosition(in anItem:ListItemType,
out isPresent:boolean):integer { query }
// Returns the position where the item belongs or exists
// in a sorted list. The isPresent flag indicates whether
// anItem is currently in the list. The item anItem and the
// list are unchanged.
|
Some operations - sortedIsEmpty, sortedLength, and sortedRetrieve, for example - are just like those for the ADT list. Insertion and deletion operations, however, are by value, not by position as they are for a list. For example, when you insert an item into a sorted list, you do not specify where in the list the item belongs. Instead, the insertion operation determines the correct position of the item by comparing its value with those of the existing items on the list. A new operation, locatePosition, determines from the value of an item its numerical position within the sorted list.
Note that the specifications given in Chapter 3* do not say anything about duplicate entries in the sorted list. Depending on your application, you might allow duplicates, or you might want to prevent duplicates from entering the list. For example, a sorted list of social security numbers probably should disallow duplicate entries. In this example, an attempt to insert a social security number that already exists in the sorted list would fail.
* CARRANO, F.M., PRICHARD, J.J. Data Abstraction and Problem Solving with C++. 3rd edition, Addison Wesley, 2002.
9 points. Write a nonrecursive, pointer-based implementation of the ADT sorted list of integers as a C++ class such that duplicates are not allowed, and operations must prevent duplicates from entering the list. So, you will have two files: ListItemType.h (header) and ListItemType.cc (implementation).
For example, Figure 2 shows a sorted list of integers.
Figure 2. A sorted list graphical representation
Table 1 presents some requested operations and their results based on this sorted list.
Table 1. Operations and graphical representation of results in the list
Requested operation |
Graphical result |
|
sortedRemove
|
 |
|
sortedInsert
|
 |
|
sortedInsert
|
DENIED: DUPLICATIONS NOT ALLOWED |
|
sortedIsEmpty |
FALSE |
|
locatePosition
|
2 |
1 point. Write a main program (lists.cc) that has a variable with datatype ListItemType. Ask the user to enter the values for one list. Create this sorted list (using createSortedList and sortedInsert). Print the result. Note that the user will enter the values in a random sequence, and your program has to define the sorted list with these values.
Define two list variables with the function createSortedList. Ask the user to enter the values for each list. Add these values to each of your variables using sortedInsert. Add a function (in your main program) that merges these two sorted lists into a third list. Print all lists: the two original lists, and the third one.
About bonus credit. This part of your work has two main purposes:
1. Let you use and test the data structure you have defined in an application.
2. Give you a chance to increase your grade. If you already have an A, this may help you to add a beautiful A+ in your records.
1. Read chapter 4* section A Pointer-Based Implementation of the ADT List, pages 185-193.
2. Keep in mind the following considerations:
Linked lists are used in a wide range of applications. Here are some papers that enforce this statement.