We have seen the idea of top-down design. If you need a function, but it is not already available, then create it. The same idea works with types. If you need a particular type of data, but it is not already available, then you create it yourself, along with the functions that you need on it.
Our goal here is implement conceptual lists in C++. It is not possible to add notation [2,4,6], since we cannot add new notation to C++. But we can add functions and a type.
The first issue is how to represent the information in a list. One way to do that is to use a linked list, which consists of zero or more list cells linked together by pointers. Each cell holds one integer and one pointer to the next cell. The last cell in the linked list holds a null pointer, indicated by ----\ in the picture. Here is a picture of a linked list that represents [2,4,6].
____ ____ ____
| | | | | |
| -------->| ------->| -----\
|----| |----| |----|
| 2 | | 4 | | 6 |
|____| |____| |____|
Each cell has type ListCell, defined as follows.
struct ListCell
{
ListCell* next;
int item;
ListCell(int it, ListCell* nxt)
{
item = it;
next = nxt;
}
};
Now it is just a matter of defining the required things for the abstract data type. A list always has type ListCell*. To make that clear, we define type List.
typedef ListCell* List;
The empty list is represented by a null pointer. Here are implementations
of the head, tail and isEmpty functions and the emptyList constant. Remember
that a list is a pointer, so we use the C++
->
notation to select a part of the structure to which L points.
const List emptyList = NULL;
int head(List L)
{
return L->item;
}
List tail(List L)
{
return L->next;
}
bool isEmpty(List L)
{
return L == emptyList;
}
The : operator will need to be called something else since we cannot
define : to be an operator in C++.
Let's use cons(h,t) for h:t. (cons is
short for construct.)
List cons(int h, List t)
{
return new ListCell(h, t);
}
To build up a list such as [2,4,6], just notice that [2,4,6] = 2:4:6:[ ]. Replacing : by function cons yields
List twoFourSix = cons(2, cons(4, cons(6, emptyList)));
Write a statement that creates variable W and makes it hold list [5, 3]. Answer
What are the values of variables X, Y and k after performing the following sequence of statements? Express your answers in conceptual notation.
List X = cons(2, cons(4, cons(6, emptyList))); List Y = tail(X); int k = head(Y); tail(X);Answer
What happens if you do the following statements?
List X = emptyList; List Y = tail(X);Answer