Previous Section
 < Free Open Study > 
Next Section


3.2 Abstract Data Type Unsorted List

Logical Level

Programmers can provide many different operations for lists. For different applications we can imagine all kinds of things users might need to do to a list of elements. In this chapter we formally define a list and develop a set of general-purpose operations for creating and manipulating lists. By doing so, we build an abstract data type.

In the next section we design the specifications for a List ADT where the items in the list are unsorted; that is, no semantic relationship exists between an item and its predecessor or successor. Items simply appear next to one another in the list.

Abstract Data Type Operations

The first step in designing any abstract data type is to stand back and consider what a user of the data type would want it to provide. Recall that there are four kinds of operations: constructors, transformers, observers, and iterators. We begin by reviewing each type and consider each kind of operation with respect to the List ADT. We use a handwriting font for operation names at the logical level and change to a monospaced font when we refer to specific implementation.

Constructors A constructor creates an instance of the data type. It is usually implemented with a language-level declaration.

Transformers Transformers are operations that change the structure in some way: They may make the structure empty, put an item into the structure, or remove a specific item from the structure. For our Unsorted List ADT, let's call these transformers , , and .

needs only the list, no other parameters. As we implement our operations as member functions, the list is the object to which the function is applied. and need an additional parameter: the item to be inserted or removed. For this Unsorted List ADT, let's assume that the item to be inserted is not currently in the list and the item to be deleted is in the list.

A transformer that takes two sorted lists and merges them into one sorted list or appends one list to another would be a binary transformer. The specification for such an operation is given in the exercises, where you are asked to implement it.

Observers Observers come in several forms. They ask true/false questions about the data type (Is the structure empty?), select or access a particular item (Give me a copy of the last item.), or return a property of the structure (How many items are in the structure?). The Unsorted List ADT needs at least two observers: and . returns true if the list is full; tells us how many items appear in the list. Another useful observer searches the list for an item with a particular key and returns a copy of the associated information if it is found; let's call it .

If an abstract data type places limits on the component type, we could define other observers. For example, if we know that our abstract data type is a list of numerical values, we could define statistical observers such as , , and . Here, we are interested in generality; we know nothing about the type of the items on the list, so we use only general observers in our ADT.

In most of our discussions of error checking to date, we have put the responsibility of checking for error conditions on the user through the use of preconditions that prohibit the operation's call if these error conditions exist. In making the client responsible for checking for error conditions, however, we must make sure that the ADT gives the user the tools with which to check for the conditions. In another approach, we could keep an error variable in our list, have each operation record whether an error occurs, and provide operations that test this variable. The operations that check whether an error has occurred would be observers. However, in the Unsorted List ADT we are specifying, let's have the user prevent error conditions by obeying the preconditions of the ADT operations.

Iterators Iterators are used with composite types to allow the user to process an entire structure, component by component. To give the user access to each item in sequence, we provide two operations: one to initialize the iteration process (analogous to Reset or Open with a file) and one to return a copy of the "next component" each time it is called. The user can then set up a loop that processes each component. Let's call these operations and . Note that is not an iterator itself, but rather an auxiliary operation that supports the iteration. Another type of iterator takes an operation and applies it to every element in the list.

C++: Declarations and Definitions
Start example

In general programming terminology, a declaration associates an identifier with a data object, an action (such as a function), or a data type. C++ terminology distinguishes between a declaration and a definition. A declaration becomes a definition when it binds storage to the identifier. Hence, all definitions are declarations, but not all declarations are definitions. For example, a function prototype is a declaration, but a function heading with a body is a function definition. On the other hand, declarations such as typedef can never be definitions, because they are not bound to storage. Because of the way that C++ treats classes, their specification is also a definition. Because the ISO/ANSI C++ standard uses the term "definition" rather than "declaration" when referring to a class, we do the same here.

End example

Generic Data Types

Generic data type A type for which the operations are defined but the types of the items being manipulated are not

A generic data type is one for which the operations are defined but the types of the items being manipulated are not. Some programming languages have a built-in mechanism for defining generic data types; others lack this feature. Although C++ does have such a mechanism (called a template), we postpone its description until the next chapter. Here we present a simple, general-purpose way of simulating generics that works in any programming language. We let the user define the type of the items on the list in a class named ItemType and have our Unsorted List ADT include the class definition.

Two of the list operations (, and ) will involve the comparison of the keys of two list components (as does , if the list is sorted by key value). We could require the user to name the key data member "key" and compare the key data members using the C++ relational operators. However, this approach isn't a very satisfactory solution for two reasons: "key" is not always a meaningful identifier in an application program, and the keys would be limited to values of simple types. C++ does have a way to change the meaning of the relational operators (called overloading them), but for now we present a general solution rather than a language-dependent one.

We let the user define a member function in the class . This function compares two items and returns LESS, GREATER, or EQUAL depending on whether the key of one item comes before the key of the other item, the first key comes after it, or the keys of the two items are equal, respectively. If the keys are of a simple type such as an identification number, would be implemented using the relational operators. If the keys are strings, function would use the string-comparison operators supplied in <string>. If the keys are people's names, both the last name and the first name would be compared. Therefore, our specification assumes that is a member of .

Our ADT needs one more piece of information from the client: the maximum number of items on the list. As this information varies from application to application, it is logical for the client to provide it.

Let's summarize our observations in two CRC cards: one for and the other for . Note that collaborates with .

Click To expand
Click To expand

Now we can formalize the specification for the Unsorted List ADT.

Because we do not know the makeup of the key member in the ItemType, we must pass an entire object of ItemType as the parameter to both RetrieveItem and DeleteItem. Notice that the preconditions for both operations state that the key member of the parameter item is initialized. RetrieveItem fills in the rest of the members of item if a list component with the same key is found, and DeleteItem removes from the list the component whose key matches that of item.

The specifications of the operations are somewhat arbitrary. For instance, we specified in the preconditions of DeleteItem that the element to delete must exist in the list and must be unique. We could also specify an operation that does not require the element to be in the list and leaves the list unchanged if the item is not present. This decision is a design choice. If we were designing a specification for a specific application, then the design choice would be based on the requirements of the problem. In this case, we made an arbitrary decision. In the exercises, you are asked to examine the effects of different design choices.

The operations defined in this specification are a sufficient set to create and maintain an unsorted list of elements. Notice that no operation depends on the type of the items in the structure. This data independence makes the Unsorted List ADT truly abstract. Each program that uses the Unsorted List ADT defines ItemType within the context of the application and provides a comparison member function defined on two items of type ItemType.

Application Level

The set of operations provided for the Unsorted List ADT may seem rather small and primitive. In fact, this set of operations gives you the tools to create other special-purpose routines that require a knowledge of ItemType. For instance, we have not included a print operation. Why? Because to write a print routine, we must know what the data members look like. The user (who does know what the data members look like) can use the LengthIs, ResetList, and GetNextItem operations to iterate through the list, printing each data member in turn. In the code that follows, we assume that the user has defined a member function for ItemType that prints the data members of one item. We also assume that the Unsorted List ADT is itself implemented as a class with the operations as member functions.

void PrintList(std::ofstream& dataFile, UnsortedType list)
// Pre:  list has been initialized.
//       dataFile is open for writing.
// Post: Each component in list has been written to dataFile.
//       dataFile is still open.
{
  int length;
  ItemType item;

  list.ResetList();
  length = list.LengthIs();
  for (int counter = 1; counter <= length; counter++)
  {
    list.GetNextItem(item);
    item.Print(dataFile);
  }
}

Note that we defined a local variable length, stored the result of list.LengthIs () in it, and used the local variable in the loop. We did so for efficiency reasons: The function is called only once, saving the overhead of extra function calls.

Another operation that depends on the application reads data (of type ItemType) from a file and creates a list containing these elements. Without knowing how the list is implemented, the user can write a function CreateListFromFile, using the operations specified in the Unsorted List ADT. We assume a function GetData, which accesses the individual data members from the file and returns them in item.

void CreateListFromFile(std::ifstream& dataFile, UnsortedType& list)
// Pre:  dataFile exists and is open.
// Post: list contains items from dataFile.
//       dataFile is in the fail state due to end-of-file.
//       Items read after the list becomes full are discarded.
{
  ItemType item;

  list.MakeEmpty();
  GetData(dataFile, item); // Reads one item from dataFile.
  while (dataFile)
  {
    if (!list.IsFull())
      list.InsertItem(item);
    GetData(dataFile, item);
  }
)

In these two functions we have made calls to the list operations specified for the UnsortedList ADT, creating and printing a list without knowing how the list is implemented. At an application level, these tasks are logical operations on a list. At a lower level, these operations are implemented as C++ functions that manipulate an array or other data-storing medium holding the list's elements. Multiple functionally correct ways are available to implement an abstract data type. Between the user picture and the eventual representation in the computer's memory, intermediate levels of abstraction and design decisions are possible. For instance, how is the logical order of the list elements reflected in their physical ordering? We address questions like this as we now turn to the implementation level of our ADT.

Implementation Level

The logical order of the list elements may or may not mirror the way that we actually store the data. If we implement a list in an array, the components are arranged so that the predecessor and the successor of a component are physically before and after it, respectively. In Chapter 5, we introduce a way of implementing a list in which the components are sorted logically rather than physically. However, the way that the list elements are physically arranged certainly affects the way that we access the elements of the list. This arrangement may have implications for the efficiency of the list operations. For instance, nothing in the specification of the Unsorted List ADT requires us to implement the list with the elements stored in random order. If we stored the elements in an array, completely sorted, we could still implement all of the Unsorted List operations. Does it make a difference if the items are stored unsorted or sorted? At the end of this chapter, we introduce Big-O notation as a way of comparing the efficiency of algorithms, and we answer this question then.

There are two ways to implement a list that preserves the order of the list items-that is, that stores the elements physically in such a way that, from one list element, we can access its logical successor directly. We look at a sequential array-based list representation in this chapter. The distinguishing feature of this implementation is that the elements are stored sequentially, in adjacent slots in an array. The order of the elements is implicit in their placement in the array.

The second approach, which we introduce in Chapter 5, is a linked-list representation. In a linked implementation, the data elements are not constrained to be stored in physically contiguous, sequential order; rather, the individual elements are stored "somewhere in memory," and explicit links between them maintain their order.

Before we go on, let's establish a design terminology that we can use in our algorithms, independent of the eventual list implementation.

List Design Terminology Assuming that location "accesses" a particular list element,

Node(location)

refers to all data at location, including implementation-specific data.

Info(location)

refers to the user's data at location.

Info(last)

refers to the user's data at the last location in the list.

Next(location)

gives the location of the node following Node(location).

What, then, is location? For an array-based implementation, location is an index, because we access array slots through their indexes. For example, the design statement

Print element Info(location)

means "Print the user's data in the array slot at index location"; eventually it might be coded in C++ as

list.info[location].Print(dataFile):

When we look at a linked implementation in a later chapter, the translation is quite different but the algorithms remain the same. That is, our code implementing the operations changes, but the algorithms do not. Thus, using this design notation, we define implementation-independent algorithms for our List ADT.

But what does Next(location) mean in an array-based sequential implementation? To answer this question, consider how we access the next list element stored in an array: We increment the location, which is the index. The design statement

Set location to Next(location)

might, therefore, be coded in C++ as

location++:  // location is an array index.

We have not introduced this list design terminology just to force you to learn the syntax of another computer "language." Rather, we want to encourage you to think of the list, and the parts of the list elements, as abstractions. We have intentionally made the design notation similar to the syntax of function calls to emphasize that, at the design stage, the implementation details can be hidden. A lower level of detail is encapsulated in the "functions" Node, Info, and Next. Using this design terminology, we hope to record algorithms that can be coded for both array-based and linked implementations.

Data Structure In our implementation, the elements of a list are stored in an array of class objects.

ItemType info[MAX_ITEMS];

We need a length data member to keep track of both the number of items we have stored in the array and the location where the last item was stored. Because the list items are unsorted, we place the first item put into the list into the first slot, the second item into the second slot, and so forth. Because our language is C++, we must remember that the first slot is indexed by 0, the second slot by 1, and the last slot by MAX_ITEMS - 1. Now we know where the list begins-in the first array slot. Where does the list end? The array ends at the slot with index MAX_ITEMS - 1, but the list ends in the slot with index length - 1.

Is there any other information about the list that we must include? Both operations ResetList and GetNextItem refer to a "current position." What is this current position? It is the index of the last element accessed in an iteration through the list. Let's call it currentPos. ResetList initializes currentPos to -1. GetNextItem increments currentPos and returns the value in info [currentPos]. The ADT specification states that only ResetList and GetNextItem affect the current position. Figure 3.1 illustrates the data members of our class UnsortedType.

Click To expand
Figure 3.1: Data members of class UnsortedType
#include "ItemType.h"
// File ItemType.h must be provided by the user of this class.
//  ItemType.h must contain the following definitions:
//  MAX_ITEMS:     the maximum number of items on the list
//  ItemType:      the definition of the objects on the list
//  RelationType:  {LESS, GREATER, EQUAL}
//  Member function ComparedTo(ItemType item), which returns
//       LESS, if self "comes before" item
//       GREATER, if self "comes after" item
//       EQUAL, if self and item are the same

class UnsortedType
{
public :
  UnsortedType () ;
  bool IsFull() const;
  int LengthIs() const;
  void RetrieveItem(ItemType& item, bool& found);
  void InsertItem(ItemType item);
  void DeleteItem(ItemType item);
  void ResetList();
  void GetNextItem(ItemType& item);
private:
  int length:
  ItemType info[MAX_ITEMS];
  int currentPos;
};

Now let's look at the operations that we have specified for the Unsorted List ADT.

Constructor Operations is an initialization, or constructor, operation. We said earlier that such an operation is often a language-level operation. C++ provides a language-level construct called a class constructor that performs this initialization automatically when a variable of the class is declared. A class constructor is a member function having the same name as the class but no return type. A constructor initializes class members and, if necessary, allocates resources (usually memory) for the object being constructed. Like any other member function, a constructor has access to all members, public and private, both data members and function members. Also like all other member functions, class constructors can have an empty parameter list (called a default constructor) or have one or more parameters.

Class constructor A special member function of a class that is implicitly invoked when a class object is defined

If we are implementing the operation with the class constructor, what must the UnsortedType class constructor do? The postcondition states that the list is empty. Any array cannot be "empty"; after all, the slots still exist. A list, however, consists of only those values that we have stored in the array, that is, from location zero through location length - 1. An empty list, then, is one where the length is 0.

UnsortedType::UnsortedType()
{
  length = 0;
}

Notice that we do not have to do anything to the array that holds the list items to make a list empty. If length is zero, the list is empty. If length is not zero, we must have stored items in the array through the length - 1 position, covering up what was there. What is present in the array from the length position to the end is of no interest to us. This distinction is very important: The list is between positions 0 and length -1; the array is between positions 0 and MAX_ITEMS - 1.

C++: Rules for Using Class Constructors
Start example

C++ has intricate rules governing the use of constructors. The following guidelines are especially pertinent:

  1. A constructor cannot return a function value, so the function is declared without a return value type. Although not necessary, return statements with no expressions are allowed at the end of a constructor. Thus return; is legal in a constructor, but return 0; is not.

  2. Like any other member function, a constructor may be overloaded. Hence, a class may provide several constructors. When a class object is declared, the compiler chooses the appropriate constructor based on the number and data types of the parameters to the constructor, just as in any other call to overloaded functions.

  3. Arguments to a constructor are passed by placing the argument list immediately after the name of the class object being declared:

    SomeType myObject(argument1, argument2);
    
  4. If a class object is declared without a parameter list, as in the statement

    SomeType myObject:
    

    then the effect depends on the constructors (if any) provided by the class. If the class has no constructors, the compiler generates a default constructor that does nothing. If the class does have constructors, then the default (parameterless) constructor is invoked if there is one. If the class has constructors but no default constructor, a syntax error occurs.

  5. If a class has at least one constructor, and an array of class objects is declared as in the statement

    SomeType myObject[5];
    

    then one of the constructors must be the default (parameterless) constructor. This constructor is invoked for each element in the array.

End example

Observer Operations The observer function IsFull checks whether length is equal to MAX_ITEMS.

bool UnsortedType::IsFull() const
{
  return (length == MAX_ITEMS);
}

The body of the observer member function LengthIs is also just one statement.

int UnsortedType::LengthIs() const
{
  return length;
}

So far we have not used our special design terminology. The algorithms have all been one (obvious) statement long. The next operation, RetrieveItem, is more complex. The RetrieveItem operation allows the list user to access the list item with a specified key, if that element exists in the list. item (with the key initialized) is input to this operation; item and a flag (found) are returned. If the key of item matches a key in the list, then found is true and item is set equal to the element with the same key. Otherwise, found is false and item remains unchanged. Notice that item is used for both input to and output from the function. Conceptually, the key member is input; the other data members are output because the function fills them in.

To retrieve an element, we must first find it. Because the items are unsorted, we must use a linear search. We begin at the first component in the list and loop until either we find an item with the same key or there are no more items to examine. Recognizing a match is easy: item.ComparedTo (info [location]) returns EQUAL. But how do we know when to stop searching? If we have examined the last element, we can stop. Thus, in our design terminology, we continue looking as long as we have not examined Info(last). Our looping statement is a while statement with the expression (moreToSearch AND NOT found). The body of the loop is a switch statement based on the results of function ComparedTo. We summarize these observations in the following algorithm:

Before we code this algorithm, let's look at the cases where we find the item in the list and where we examine Info(last) without finding it. We represent these cases in Figure 3.2 in an honor roll list. First, we retrieve Sarah. Sarah is in the list, so moreToSearch is true, found is true, and location is 3. That's as it should be (see Figure 3.2a). Next, we retrieve Susan. Susan is not in the list, so moreToSearch is false, found is false, and location is equal to length (see Figure 3.2b).

Click To expand
Figure 3.2: Retrieving an item in an unsorted list

Now we are ready to code the algorithm, replacing the general design notation with the equivalent array notation. The substitutions are straightforward except for initializing location and determining whether we have examined Info(last). To initialize location in an array-based implementation in C++, we set it to 0. We know we have not examined Info(last) as long as location is less than length. Be careful: Because C++ indexes arrays starting with 0, the last item in the list is found at index length - 1. Here is the coded algorithm:

void UnsortedType::RetrieveItem(ItemType& item, bool& found)
// Pre:  Key member(s) of item is initialized.
// Post: If found, item's key matches an element's key in the
//       list and a copy of that element has been stored in item;
//       otherwise, item is unchanged.
{
  bool moreToSearch;
  int location = 0;
  found = false;

  moreToSearch = (location < length);

  while (moreToSearch && !found)
  {
    switch (item.ComparedTo(info[location]))
    {
      case LESS    :
      case GREATER : location++:
                     moreToSearch = (location < length);
                     break;
      case EQUAL   : found = true;
                     item =  info[location];
                     break;
    }
  }
}

Note that a copy of the list element is returned. The caller cannot access directly any data in the list.

Transformer Operations Where do we insert a new item? Because the list elements are unsorted by key value, we can put the new item anywhere. A straightforward strategy is to place the item in the length position and then to increment length.

This algorithm is translated easily into C++.

void UnsortedType::InsertItem(ItemType item)
// Post: item is in the list.
{
  info[length] = item;
  length++;
}

The DeleteItem function takes an item with the key member indicating which item to delete. This operation clearly has two parts: finding the item to delete and removing it. We can use the RetrieveItem algorithm to search the list: When ComparedTo returns GREATER or LESS, we increment location; when it returns EQUAL, we exit the loop and remove the element.

How do we "remove the element from the list"? Let's look at the example in Figure 3.3. Removing Sarah from the list is easy, for hers is the last element in the list (see Figures 3.3a and 3.3b). If Bobby is deleted from the list, however, we need to move up all the elements that follow to fill in the space-or do we? If the list is sorted by value, we would have to move all elements up, as shown in Figure 3.3(c). Because the list is unsorted, however, we can just swap the item in the length - 1 position with the item being deleted (see Figure 3.3d). In an array-based implementation, we do not actually remove the element; instead, we cover it up with the element that previously followed it (if the list is sorted) or the element in the last position (if the list is unsorted). Finally, we decrement length.

Click To expand
Figure 3.3: Deleting an item in an unsorted list

Because the preconditions for DeleteItem state that an item with the same key is definitely present in the list, we do not need to test for the end of the list. This choice simplifies the algorithm so much that we give the code with no further discussion.

void UnsortedType::DeleteItem(ItemType item)
// Pre:  item's key has been initialized.
//       An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
  int location = 0;

  while (item.ComparedTo(info[location]) != EQUAL)
    location++;

  info[location] = info[length - 1];
  length--;
}

Iterator Operations The ResetList function is analogous to the open operation for a file in which the file pointer is positioned at the beginning of the file so that the first input operation accesses the first component of the file. Each successive call to an input operation gets the next item in the file. As a consequence, ResetList must initialize currentPos to point to the predecessor of the first item in the list.

The GetNextItem operation is analogous to an input operation; it accesses the next item by incrementing currentPos and returning Info(currentPos).

currentPos remains undefined until ResetList initializes it. After the first call to GetNextItem, currentPos is the location of the last item accessed by GetNextItem. Therefore, to implement this algorithm in an array-based list in C++, currentPos must be initialized to - 1. These operations are coded as follows:

void UnsortedType::ResetList()
// Post: currentPos has been initialized.
{
  currentPos = - 1;
}

What would happen if a transformer operation is executed between calls to GetNextItem? The iteration would be invalid. We should add a precondition to prevent this from happening.

void UnsortedType::GetNextItem(ItemType& item)
// Pre:  No transformer has been executed since last call
// Post: item is current item.
//       Current position has been updated.
{
  currentPos++;
  item = info [currentPos] ;
}

ResetList and GetNextItem are designed to be used in a loop in the client program that iterates through all items in the list. The precondition in the specifications for GetNextItem protects against trying to access an array element that is not present in the list. This precondition requires that, before a call to GetNextItem, the element at the current position not be the last item in the list. Notice that this precondition places the responsibility for accessing only defined items on the client rather than on GetNextItem.

Notes on the Array-Based List Implementation In several of our list operations, we have declared the local variable location, which contains the array index of the list item being processed. The values of array indexes are never revealed outside of the list operations; this information remains internal to the implementation of the Unsorted List ADT. If the list user wants an item in the list, the RetrieveItem operation does not give the user the index of the item; instead, it returns a copy of the item. If the user wants to change the values of data members in an item, those changes are not reflected in the list unless the user deletes the original values and inserts the modified version. The list user can never see or manipulate the physical structure in which the list is stored. These details of the list implementation are encapsulated by the ADT.

Test Plan The class UnsortedType has a constructor and seven other member functions: InsertItem and DeleteItem (transformers); IsFull, LengthIs, and RetrieveItem (observers); and ResetList and GetNextItem (iterators). Because our operations are independent of the type of the objects on the list, we can define ItemType to be int and know that if our operations work with these data, they work with any other ItemType. Here, then, is the definition of ItemType that we use in our test plan. We set the maximum number of items to 5. We include a member function to print an item of the class ItemType to an ofstream object (a file). We need this function in the driver program to see the value in a list item.

// The following declarations and definitions go into file ItemType.h.
#include <fstream>

const int MAX_ITEMS = 5;
enum RelationType {LESS, GREATER, EQUAL};

class ItemType
{
public:
  ItemType();
  RelationType ComparedTo(ItemType) const;
  void Print(std::ofstream&) const;
  void Initialize(int number);
private:
  int value;
};

// The following definitions go into file ItemType.cpp.
#include <fstream>
#include "ItemType.h"
ItemType::ItemType()
{
  value = 0;
}

RelationType ItemType::ComparedTo(ItemType otherItem) const
{
  if (value < otherItem.value)
    return LESS;
  else if (value > otherItem.value)
    return GREATER;
  else return EQUAL;
}

void ItemType::Initialize(int number)
{
  value = number;
}

void ItemType::Print(std::ofstream& out) const
// Pre:   out has been opened.
// Post: value has been sent to the stream out.
{
  out << value << " ";
}

The preconditions and postconditions in our specification determine the tests necessary for a black-box testing strategy. The code of the functions determines a clear-box testing strategy. To test the ADT Unsorted List implementation, we use a combination of the two strategies. Because a precondition on all other operations is that the list has been initialized, we test the constructor by checking whether the list is empty initially (a call to LengthIs returns 0).

LengthIs, InsertItem, and DeleteItem must be tested together. That is, we insert several items and check the length; we delete several items and check the length. How do we know that InsertItem and DeleteItem work correctly? We write an auxiliary function PrintList that uses LengthIs, ResetList, and GetNextItem to iterate through the list, printing out the values. We call PrintList to check the status of the list after a series of insertions and deletions. To test the IsFull operation, we insert four items and print the result of the test, and then insert the fifth item and print the result of the test. To test RetrieveItem, we search for items that we know are present in the list and for items that we know are not found in the list.

How do we choose the values used in our test plan? We look at the end cases. What are the end cases in a list? The item is in the first position in the list, the item is in the last position in the list, and the item is the only one in the list. We must be sure that DeleteItem can correctly delete items in these positions. We must also confirm that RetrieveItem can find items in these same positions and correctly determine that values that are less than the one in the first position or greater than the one in the last position are not found. Notice that this test plan involves a black-box strategy. That is, we look at the list as described in the interface, not the code.

These observations are summarized in the following test plan. The tests are shown in the order in which they should be performed.

Operation to Be Tested and Description of Action

Input Values

Expected Output

Constructor

   
  • print LengthIs

 

0

InsertItem

   
  • Insert four items and print

5, 7, 6, 9

5 7 6 9

  • Insert item and print

1

5 7 6 9 1

RetrieveItem

   
  • Retrieve 4 and print whether found

 

Item is not found

  • Retrieve 5 and print whether found

 

Item is found

  • Retrieve 9 and print whether found

 

Item is found

  • Retrieve 10 and print whether found

 

Item is not found

IsFull

   
  • Invoke (list is full)

 

List is full

  • Delete 5 and invoke

 

List is not full

DeleteItem

   
  • Delete 1 and print

 

7 6 9

  • Delete 6 and print

 

7 9

What about testing LengthIs, ResetList, and GetNextItem? They do not appear explicitly in the test plan, but they are tested each time we call the auxiliary function PrintList to print the contents of the list.

On the Web, the file listType.in contains the input to listDr.cpp (the test driver) that reflects this test plan; listType.out and listTest.screen contain the output.



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