Chapter 12
APPLIED ARRAYS: LISTS AND STRINGS
EXERCISE ANSWERS
Exam Preparation Exercises
1. The three factors are:
• The length of the list to be searched
• Whether or not the list already is ordered
• The number of times the list is to be searched
2. Search Item Comparisons
28 1
32 10
196 7
194 10
3. Search Item Comparisons
28 1
32 2
196 7
194 7
4.
item first last middle114 0 9 4
5 9 7
8 9 8
found = TRUE5. False
8. The following solutions require the program to
a.
strcpy(mammal, "Moose");b.
strcpy(mammal, rodent);c.
if (strcmp(mammal, "Opossum") > 0)count++;
d.
if (strcmp(mammal, "Jackal") <= 0)count--;
e. Not possible—the
rodent array can hold only 20 characters plus '\0'.f.
cout << strlen(rodent);10. Assume
numberOut is the number of books borrowed.a.
for (i = 0; i < numberOut; i++)if (strcmp(borrower[i], name) == 0)
cout << bookOut[i] << endl;
b.
booksBorrowed = 0;
for (i = 0; i < numberOut; i++)
if (strcmp(borrower[i], name) == 0)
booksBorrowed++;
c.
numCopies = 0;for (i = 0; i < numberOut; i++)
if (strcmp(bookOut[i], bookIn) == 0)
numCopies++;
d.
numCopies = 0;for (i = 0; i < numberOut; i++)
if (strcmp(bookOut[i], bookIn) == 0 &&
strcmp(borrower[i], name) == 0)
numCopies++;
Programming Warm-Up Exercises
1.
int Index( /* in */ const int list[],/* in */ int item,
/* in */ int length )
// Precondition:
// length <= MAX_LENGTH
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// IF item is in list
// Function value == position in list where item was found
// ELSE
// Function value == -1
{
int index = 0; // Loop control and index variable
while (index < length && item != list[index])
// Invariant (prior to test):
// item is not in list[0..index-1]
// && 0 <= index <= length
index++;
if (index < length)
return index;
else
return -1;
}
3.
int Product( /* in */ const int arr1[],/* in */ const int arr2[],
/* in */ int length )
// Precondition:
// length <= MAX_LENGTH
// && arr1[0..length-1] are assigned
// && arr2[0..length-1] are assigned
// Postcondition:
// Function value == product of all components of arr2 for which
// the corresponding components of arr1 are
// negative
// Note:
// Integer overflow may result from too large a product
{
int index; // Loop control and index variable
int prod = 1; // Holds partial products
for (index = 0; index < length; index++)
// Invariant (prior to test):
// prod == product of components in arr2[0..index-1]
// for which the corresponding components of
// arr1 are negative
// && 0 <= index <= length
if (arr1[index] < 0)
prod = prod * arr2[index];
return prod;
}
4.
Boolean Found( /* in */ const float list[],/* in */ float item,
/* in */ int length )
// Precondition:
// length <= MAX_LENGTH
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// Function value == TRUE, if some component of list has a value
// greater than item
// == FALSE, otherwise
{
int index = 0; // Loop control and index variable
while (index < length && item >= list[index])
// Invariant (prior to test):
// item >= every value in list[0..index-1]
// && 0 <= index <= length
index++;
return (index < length);
}
5.
void SearchOrd( /* inout */ ItemType list[],/* in */ ItemType item,
/* in */ int length,
/* out */ int& index,
/* out */ Boolean& found,
/* out */ Boolean& overflow )
// Precondition:
// list[0..length-1] are in ascending order <-
Precondition for length
// && item is assigned
deleted// Postcondition:
// IF length >= MAX_LENGTH
// overflow == TRUE && An error message has been printed
// ELSE
// overflow == FALSE
// && ... (same as original postcondition)
{
overflow = (length >= MAX_LENGTH);
if (overflow)
{
cout << "Function SearchOrd cannot be executed; "
<< "length >= MAX_LENGTH." << endl;
return;
}
index = 0;
.
. // Same as in original function body
.
}
6.
void SearchOrd(/* inout */ ifstream& list, // File to be searched
/* in */ ItemType item, // Item to be found
/* out */ int& index, // Location of item if found
/* out */ Boolean& found ) // True if item is found
// Precondition:
// Values in file "list" are in ascending order
// && item is assigned
// Postcondition:
// IF item is in list
// found == TRUE
// && index == position (0, 1, 2, ...) in list
// where item was found
// ELSE
// found == FALSE
// Note:
// ItemType must be a simple type
{
ItemType inputVal; // Current input value being tested
index = 0;
list >> inputVal;
// Exit loop when item is either found or not there
while (list && item > inputVal ) // While NOT EOF &&
// item > inputVal...
{
// Invariant (prior to test):
// item is not in position 0..index-1 of list
index++;
list >> inputVal;
}
// Determine whether item was found or not there
found = (list && item == inputVal);
}
7. The following solution includes an outgoing Boolean parameter,
void Delete( /* inout */ ItemType list[],
/* in */ ItemType item,
/* inout */ int& length,
/* out */ Boolean& found )
// Precondition:
// length <= MAX_LENGTH
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// IF item is in list@entry
// found == TRUE
// && First occurrence of item is no longer in list
// && length == length@entry - 1
// ELSE
// found == FALSE
{
int index = 0; // Loop control and index variable
while (index < length && item != list[index])
// Invariant (prior to test):
// item is not in list[0..index-1]
// && 0 <= index <= length
index++;
found = (index < length);
if (found)
{
for (index = index + 1; index < length; index++)
// Invariant (prior to test):
// Assuming item was found at some position k,
// list[k+1..index-1] have been shifted up
// && k+1 <= index <= length
list[index-1] = list[index];
length--;
}
}
8. Place the directive
#include <string.h> near the top of the program. Then modify the solution to Exercise 7 as follows.
Change the function heading to
void Delete( /* inout */ StrType list[],
/* in */ const StrType item,
/* inout */ int& length,
/* out */ Boolean& found )
Change the While condition to
while (index < length && strcmp(item, list[index]) != 0)
Change the body of the For loop to
strcpy(list[index-1], list[index]);
9. The following solution invokes the
Delete function written as the answer to exercise 7. There are quicker solutions in terms of machine time but not in terms of programmer time. (For an alternative implementation of the DeleteAll function, see the solution to Exercise 14e.)void DeleteAll( /* inout */ ItemType list[],
/* in */ ItemType item,
/* inout */ int& length )
// Precondition:
// length <= MAX_LENGTH
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// All occurrences of item in list@entry are no longer in list
// && length == length@entry - (no. of occurrences of item
// in list@entry)
{
Boolean found; // TRUE if item is in list
do
Delete(list, item, length, found);
// Invariant at end of iteration number n:
// IF found is TRUE
// n occurrences of item have been deleted from list
// ELSE
// n-1 occurrences of item have been deleted from list
while (found);
}
10.
void SetScores( /* in */ const Boolean isAbsent[],/* inout */ float score[],
/* in */ int length )
// Precondition:
// length <= MAX_STUD
// && isAbsent[0..length-1] are assigned
// Postcondition:
// For all i, where 0 <= i <= length-1,
// IF NOT isAbsent[i], THEN score[i] == 0.0
{
int index; // Loop control and index variable
for (index = 0; index < length; index++)
// Invariant (prior to test):
// For all i, where 0 <= i <= index-1,
// IF NOT isAbsent[i], THEN score[i] == 0.0
// && 0 <= index <= length
if ( !isAbsent[index] )
score[index] = 0.0;
}
11.
int SumOfProducts( /* in */ const int data[],/* in */ const int weight[],
/* in */ int length )
// Precondition:
// length <= MAX_LENGTH
// && data[0..length-1] are assigned
// && weight[0..length-1] are assigned
// Postcondition:
// Function value == data[0]*weight[0] + data[1]*weight[1] + ...
// + data[length-1]*weight[length-1]
// Note:
// Integer overflow may result from too large a sum of products
{
int index; // Loop control and index variable
int sum = 0; // Sum of the products
for (index = 0; index < length; index++)
// Invariant (prior to test):
// sum == data[0]*weight[0] + data[1]*weight[1] + ...
// + data[index-1]*weight[index-1]
// && 0 <= index <= length
sum = sum + data[index] * weight[index];
return sum;
}
14. a.
Boolean Empty( /* in */ int length ) // Length of a list// Precondition:
// length <= MAX_LEN
// Postcondition:
// Function value == TRUE, if the list is empty
// == FALSE, otherwise
{
return (length == 0);
}
b.
Boolean Full( /* in */ int length ) // Length of a list// Precondition:
// length <= MAX_LEN
// Postcondition:
// Function value == TRUE, if the list is full
// == FALSE, otherwise
{
return (length == MAX_LEN);
}
c.
Boolean Equal(/* in */ const ItemType list1[], // First list
/* in */ int length1, // Length of first list
/* in */ const ItemType list2[], // Second list
/* in */ int length2 ) // Length of second list
// Precondition:
// length1 <= MAX_LEN && length2 <= MAX_LEN
// && list1[0..length1-1] are assigned
// && list2[0..length2-1] are assigned
// Postcondition:
// Function value == TRUE, if length1 == length2
// && the corresponding elements of
// list1 and list2 are equal
// == FALSE, otherwise
{
if (length1 != length2)
return FALSE;
int index = 0; // Loop control and index variable
while (index < length1 && list1[index] == list2[index])
// Invariant (prior to test):
// For all i, where 0 <= i <= index-1,
// list1[i] == list2[i]
// && 0 <= index <= length1
index++;
return (index == length1);
}
d.
void Delete( /* inout */ ItemType list[], // List of items/* in */ ItemType item, // Item to delete
/* inout */ int& length ) // Length of list
// Precondition:
// length <= MAX_LEN
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// IF item is in list@entry
// First occurrence of item is no longer in list
// && length == length@entry - 1
{
int index; // Loop control and index variable
Boolean found = FALSE; // TRUE if item is found
for (index = 0; index < length; index++)
// Invariant (prior to test):
// IF item was found at some position k
// list[k+1..index-1] have been shifted up
// && 0 <= index <= length
if ( !found )
found = (list[index] == item);
else
list[index-1] = list[index];
if (found)
length--;
}
e.
void DeleteAll( /* inout */ ItemType list[], // List of items/* in */ ItemType item, // Item to delete
/* inout */ int& length ) // Length of list
// Precondition:
// length <= MAX_LEN
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// All occurrences of item in list@entry are no longer in list
// && length == length@entry - (no. of occurrences of item
// in list@entry)
{
int index; // Loop control and index variable
int numFound = 0; // Number of items found
for (index = 0; index < length; index++)
{
// Invariant (prior to test):
// IF list[index-1] != item
// list[0..index-1]@entry have been compacted
// into list[0..(index-1)-numFound] by
// eliminating occurrences of item
// ELSE
// list[0..index-1]@entry have been compacted
// into list[0..(index-1)-(numFound-1)] by
// eliminating occurrences of item
// && 0 <= index <= length
list[index-numFound] = list[index];
if (list[index] == item)
numFound++;
}
length = length - numFound;
}
f.
void Component(
/* in */ const ItemType list[], // List of items
/* in */ int length, // Length of list
/* in */ int index, // Desired position
/* out */ ItemType& item, // Item retrieved
/* out */ Boolean& valid ) // TRUE if index is valid
// Precondition:
// length <= MAX_LEN
// && list[0..length-1] are assigned && index is assigned
// Postcondition:
// IF 0 <= index < length
// valid == TRUE
// && item == list[index]
// ELSE
// valid == FALSE
{
valid = (index >= 0 && index < length);
if (valid)
item = list[index];
}
15. Simply use the reserved word
ANSWERS TO QUESTIONS
True/False
Multiple Choice
Fill-In
31. homogeneous
32. linear
33. list
34. length
35. sequential
36. sorting
37. selection(straight selection)
38. insertion
39. binary
40. null
41. string
42. lexicographic
42.
temp = x[i];43.
strcpy(yourString, myString)44.
strlen(someString)45.
typedef int ArrType[25];