|
|
|
|
|
|
|
While loop contains a compound condition: it stops when it either finds item or reaches the end of the list. We can insert a copy of item into list[length]-that is, into the array component beyond the end of the list-as a sentinel. By doing so, we are guaranteed to find item in the list. The condition that checks for the end of the list (index < length) can then be eliminated (see Figure 12-2). Eliminating a condition saves the machine time that would be required to test it. In this case, we save time during every iteration of the loop, so the savings add up quickly. (The time saving comes at a cost, however. We sacrifice one array position for the sentinel.) |
|
|
|
|
|
|
|
|
In storing a copy of item as a sentinel in list[length], we assume that length is always less than MAX_LENGTH. We must document this assumption in the function precondition. Also, we must document the fact that list[length] is modified by the function (even though list[length] is assumed to contain meaningless data initially). As well, we remove the word const in the declaration of the list parameter so that the compiler lets us modify the array. |
|
|
|
|
|
|
|
|
After the loop terminates, found can be set by checking to see if index is less than length. Function Search2 incorporates all of these changes. |
|
|
|
|
|
|
|
|
void Search2(
/* inout */ ItemType list[], // List to be searched
/* in */ ItemType item, // Item to be found
/* in */ int length, // Length of list
/* out */ int& index, // Location of item if found
/* out */ Boolean& found ) // True if item is found |
|
|
|
|
|
|
|
|
Figure 12-2
Generalized Sequential Search with Copy of item in list[length] |
|
|
|
|
|
