|
|
|
|
|
|
|
Figure 12-5
Inserting into an Ordered List |
|
|
|
|
|
|
|
|
skip the insertion, as we choose, as long as we clearly document what is done. Inserting a second copy seems more reasonable. Therefore, index is the insertion point, whether or not item already exists in the list. |
|
|
|
|
|
|
|
|
This function needs three parameters: the array containing the list, the number of components in the list, and the item being inserted. Again, we use the variable names list, item, and length. This time, both list and length must be incoming/outgoing parameters because they are changed each time the function is invoked. |
|
|
|
|
|
|
|
|
void Insert( /* inout */ ItemType list[], // List to be changed
/* inout */ int& length, // Length of list
/* in */ ItemType item ) //Item to be inserted
// Inserts item into its proper place in the sorted list
// Precondition:
// length < MAX_LENGTH
// && list[0..length-1] are in ascending order
// && item is assigned
// Postcondition:
// item is in list
// && length == length@entry + 1
// && list[0..length-1] are in ascending order
// && IF item was already in list@entry
// item has been inserted before the one that was there |
|
|
|
|
|
