Computer Science 2611
Fall 2000
Laboratory Assignment 12 (Last one)

Handed out: 11/16/00

Linked lists

To start this assignment, implement basic linked lists. But instead of lists of integers, use lists of strings. The list cell type should be 
  struct cell 
  {
    char* word;
    cell* next;

    cell(char* w, cell* nxt)
    {
      word = strnewdup(w);
      next = nxt;
    }
  };
where function strnewdup(w) uses the new operator to allocate memory, copies w into that new memory and returns a pointer to the new memory. (You will need to write strnewdup.)

Implement the following functions on lists.

  1. printlist(x): print the words in list x, one per line.

  2. member(s,x): return 1 when string s is a member of list x, and 0 otherwise.

  3. sort(s): return a sorted version of list x. Use the strcmp function to compare the words, not <.

Assignment

Write a program that reads words from a file, up to the end of the file, and then prints, to the standard output, all of the words that occur in the file, in alphabetical order. It should print each word only once. For example, if the file contains 
  The cat in the hat hit the rat
then the output should be 
  The
  cat
  hat
  hit
  in
  rat
  the
The name of the input file should be read from the user.

Words are defined as for assignment 8. That is, anything that the >> reads as a string is considered a word. A word that begins with a capital letter is not the same as a word that begins with a lower case letter. For example, "The" and "the" are considered different words for this assignment.

Use linked lists to implement this assigment. Keep a list of all words read so far. When you read a word, check whether it is already a member of the list. If so, skip that word. If it is not a member of the list, attach it to the front of the list.

After all words have been read, print a sorted version of the list.