Reading

None.

A problem to work on

We will work the following problem in class as a sort of minilab: Assuming you have files dbpoint.h and dbpoint.cpp that provide a nice implementation of a struct Point, write a program that reads a comma separated list of data points from the user (terminated by a semi-colon) and then repeatedly asks the user for a reference point, and responds by printing out average of the distances of the data points from the reference point.
Note: By all means look at the code from the previous lesson that shows how to build and traverse (to print) a linked list.
~/$ ./prog
(0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ;
(2,3)
average = 2.91075
(2,1.5)
average = 2.21384
(2,0.5)
average = 2.11915
(2,-0.5)
average = 2.38453

Recursion and linked lists

Let's look carefully at recursion and linked lists. An essential property of a recursive solution to a problem is that solving the initial problem involves solving a smaller version of the same problem. How does this fit with linked lists? Very nicely, actually. Remember that a list is represented by a variable L that is a pointer — a pointer to the first node in the list. Now, if you look at the next member of that first node (i.e. look at L->next), what is that? It's a pointer — a pointer that represents the list of everything after the first node. So, for example, in the following linked list The pointer L is the list 5,9,2,8,4, and just as much the pointer L->next is the list 9,2,8,4. This makes it natural for a recursive function called with argument L to make its recursive call with argument L->next. We saw the example of such a recursive call with the recursive version of length:
int length(Node* L)
{
  if (L == NULL)
    return 0;
  return 1 + length(L->next);
}
Hopefully this makes sense now that we see that L is the list L->next plus one extra node, the node with data value 5. Most other recursive functions with lists work the same way. For example, suppose we want to calculate the sum of the elements of list L. In the above example, it is 5 + the sum of 9,2,8,4. In other words, L->data plus the sum of the elements of the list L->next. So the recursive case is:
L->data + sum(L->next)
If you're printing out the list L from the example above recursively, you think of printing 5, then printing the list 9,2,8,4. So the recursive case for print(L) is
cout << L->data << ' ';
print(L->next);

Problems

  1. Build on the above problem code, and print the list out in the same format it was entered: comma-separated, semi-colon terminated.
  2. Build on the above problem code, and print the last element in the list.
  3. Build on the above problem code, and print the next-to-last element in the list.