|
A nondestructive function on a linked list is one that does not change the list. To emphasize that, we will mark list parameters that cannot be changed by const.
One way to discover an algorithm for a nondestructive function on a linked list is to start by treating the list in conceptual form, to find equations that define the function, and then to translate the equations to C++. Here are the equations that we derived for length(L).
length([]) = 0 length(L) = 1 + length(tail(L)) (when L is not empty)They immediately lead to the following definition of length in C++.
int length(const List L)
{
if(isEmpty(L))
{
return 0;
}
else
{
return = 1 + length(tail(L));
}
}
We found it more convenient to write the second equation by replacing
L by h:t, head(L) by h and
tail(L) by t, as follows.
length([]) = 0 length(h:t) = 1 + length(t)That translates to the same definition of length in C++. When converting the right-hand side to C++, just remember that h stands for head(L) and t stands for tail(L).
We derived the following facts about function member(x, L).
member(x, []) = false member(x, h:t) = h == x or member(x, t)Converting them to C++ yields the following.
bool member(int x, const List L)
{
if(isEmpty(L))
{
return false;
}
else
{
return head(L) == x || member(x, tail(L));
}
}
We derived the following equations for cat(A,B).
cat([], B) = B cat(h:t, B) = h:cat(t,B)Converting to C++ yields the following definition of cat.
const List cat(const List A, const List B)
{
if(isEmpty(A))
{
return B;
}
else
{
return cons(head(A), cat(tail(A), B));
}
}
Notice that cat returns a result of type const List. The reason is that B has type const List, so statement
return B;requires the result also to have type const List. This definition of cat uses memory sharing, discussed on the next page. If you want cat to return a list that the caller can modify, just return a copy of list B, as follows.
List cat(const List A, const List B)
{
if(isEmpty(A))
{
return copyList(B);
}
else
{
return cons(head(A), cat(tail(A), B));
}
}
Definition of copyList is left as an exercise.
We derived the following equations for evens(L).
evens([]) = [] evens(h:t) = h:evens(t) (when h is even) evens(h:t) = evens(t) (when h is odd)Converting to C++ yields the following definition of evens.
List evens(const List L)
{
if(isEmpty(L))
{
return emptyList;
}
else if(head(L) % 2 == 0)
{
return cons(head(L), evens(tail(L)));
}
else
{
return evens(tail(L));
}
}
Function evens(L) does not make use of memory sharing, so its result type can be List.
Write equations for copyList(L), which yields a copy of list L.
Write a definition of copyList(L) in C++ Parameter L should have type const List, but copyList should return a List.
AnswerWrite equations for function sum(L), which yields the sum of all members of list L. For example, sum([2,3,4]) = 2 + 3 + 4 = 9. The sum of an empty list is 0. Make sure that your equations contain enough information to determine the value of sum(L) for any list of integers L.
Write a definition of function sum(L) in C++. Follow your equations directly.
AnswerIf L has length n, how long does it take to compute sum(L)? Use big-O notation to express the answer. Answer
Write equations for function smallest(L), which yields the smallest member of nonempty list L. For example, smallest([2,3,4]) = 2 and smallest([6,4,8,7]) = 4. Your equations should not try to define smallest([ ]), since the list is required to be nonempty. You can use function min(x, y) to compute the smaller of two integers x and y.
Using your equations, write a definition of smallest(L) in C++.
AnswerWrite equations for function prefix(L, n), which yields the length n prefix of list L. For example, prefix([2,4,6,8,10], 3) = [2,4,6]. If n is larger than the length of L then prefix(L, n) should return L. For example, prefix([2,4,6,8,10], 50) = [2,4,6,8,10].
Using your equations, write a definition of prefix(L, n) in C++.
Answer
|