Recitation notes for 9/8/97

* Linked lists: pointers, structs and memory
* constructors and destructors

(Note:  Most recitations discussed a subset or variation on these outlines.)
=========================================================================

Problems with the assignment?

There were some problems on the assignment with issues related to
linked lists and pointers, so let's talk about them some more.  Also
this will bring us to a couple of related important topics.

Say we wanted to make a linked list of chars using structs.  We could
do it like this:

struct ListElement {
  char item;
  ListElement *next;
};

typedef ListElement *List;       // a "List" means a pointer to a 
			         // "ListElement".  You can think of the
                                 // syntax of a typedef as
                                 // "definition by example" 

Let's write an insert function that takes a List and a char and returns a new
List with the char inserted.

List insert(List l, char c)
{
  List newlist;
  newlist = new ListElement;   // what would happen if we removed this line?
  newlist->item = c;
  newlist->next = l;
  return newlist;
}

Suppose we do:
List p = NULL;
p = insert(p, 'a');
p = insert(p, 'b');

what does this look like in memory?
    +---+        +---+
p-->| b |    ,-->| a |
    +---+    |   +---+
    | -------'   | / |
    +---+        +---+

A "struct" is just a block of memory broken up into different fields for 
the different parts.


Let's write a routine to delete all elements of a List.  

Here is one nice way. Idea: to free up list,
 (1) free up rest of list, then (2) free up head.

void delete_list(List l)
{
  if (l == NULL) return;      // base case
  delete_list(l->next);       // delete rest of list first
  delete l;                   // then delete the head.
}

Say a programmer looks at the code and says: well, I'm never going to call 
this with NULL, so let's remove the if() test.

--> problem: NEED BASE CASE IN RECURSION

what about if we: replace delete_list(l->next) by delete_list(l)??

--> when write recursive procedure, make sure you get closer to
    base case with each recursive call.

What would happen if we ran this on p, BUT we had forgotten to initialize p 
to NULL at the very beginning?  Answer: we might go running off into weird
parts of memory and get a segmentation violation.



Suppose we have a List and we want to remove the first occurence of a given 
letter (or do nothing if the letter is not in the list) and return the new 
List.



List remove_first(List l, char c)
{
  if (l == NULL) return l;              // base case
  if (l->item != c) {                   // c is not here.
    l->next = remove_first(l->next, c);
    return l;
  } else {                              // c is here.
    List temp = l->next;
    delete l;
    return temp;
  }
}

Say you wanted to remove *all* occurences of c.  Can you do this by
just changing one line?  

=========================================================================
Now, let's do this with classes. 
First: a few words about constructors and destructors.

Say we have a class Foo, and we write

  Foo *p;
  p = new Foo;

What happens is that "new" allocates space (on the heap/free-store) for one 
shiny new Foo, 
      +---------+
1372: |?????????|
      +---------+

and then calls the Foo constructor to initialize that space,
      +---------+
1372: |000000000|
      +---------+
and then returns a pointer to (i.e., the address of) that space.

If we did
  Foo *p;
  p = new Foo[10];
then "new" would allocate space for 10 Foo's in a row, call the constructor
to initialize each one, and return a pointer to the beginning of that space.

delete and destructors work together similarly, but in the other order.

E.g.,

  delete []p;

will first call the destructor (if there is one) for each of the 10 Foos,
and then will deallocate the array.

A few words about "this":  Inside a member function, "this" is a
pointer to the current element.  Can use it for various things.

Let's do an example.  Let's make a list of strings instead of a list
of chars.  There are many different ways of doing this. 
------------------------------list.h----------------------------------------

// ListElement class. handles copying and freeing up of strings.
// to save writing, putting small pieces of code into class definition.

class ListElement {
public:                         // let's make these public for convenience
  char *item;
  ListElement *next;

public:
  // constructor. makes a COPY of str.
  ListElement(char* str) { item = strdup(str); next=NULL; }

  ~ListElement()  {delete item;}    // destructor. Frees up item. Doesn't
                                    // free up entire list, though.
};    

// Let's make a "List" like this.
class List {
private:
  ListElement *head;
  ListElement * removeFirstRecursive(ListElement *l, char *str); // helper
public:
  List() { head = NULL;}
  ~List();                     // delete the whole thing.
  void insert(char *str);      // insert a copy of str
  void print();                // print out the list
  void removeFirst(char *str) {head = removeFirstRecursive(head, str);}
};

--------------------list.C--------------------------------------------------

#include<iostream.h>
#include<string.h>
#include "list.h"

#define SAME 0

List::~List()
{
  ListElement *temp;
  while(head) {              // head is the same as this->head
    temp = head->next;
    delete head;
    head = temp;
  }
}

void List::insert(char *str)
{
  ListElement *temp = new ListElement(str);
  temp->next = head;
  head = temp;
}

void List::print()
{
  for(ListElement *temp = head; temp != NULL; temp = temp->next) {
    cout << temp->item << " ";
  }
  cout << endl;
}

// remove first occurence of str. recursive helper. Basically same as before
ListElement * List::removeFirstRecursive(ListElement *l, char *str)
{
  if (l == NULL) return NULL;
  if (strcmp(l->item, str) != SAME) {      // str is not here.
    l->next = removeFirstRecursive(l->next, str);
    return l;
  } else {                                 // str is here.
    ListElement *temp = l->next;
    delete l;
    return temp;
  }
}