Computer Science 2611
Fall 2004
Laboratory Assignment 9

Date assigned: November 20, 2004

Linked lists

An array is one way to represent a sequence of things. There is a first one, as second one, etc. An array is stored in consecutive locations in memory.

A linked list is another way to represent a sequence of things. But instead of storing the members of the sequence in consecutive memory locations, each one tells where the next one can be found. Each has a pointer to the next one.

The last item holds a NULL pointer (the X) indicating the end of the list.

Each box in the linked list is called a list cell. It needs to hold some information and a pointer to the next item in the list. A linked list that holds integers (similar in spirit to an array of integers) might look as follows.

To group the parts of a list cell together, you can use a struct. For example, a linked list of integers might be build from the following type of cells.

  struct listcell
  {
    int item;
    listcell* next;
  };

A linked list is always represented by a pointer to the first list cell. So it has type listcell*. If a list is empty (so has no cells) then the pointer to the first list cell is a NULL pointer.

Lists containing strings

You can store a string in a linked list by storing a pointer to the string. Here is a picture of a list of strings, using the list cell type

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

You can store more than one piece of information in a list cell. For example, the following can store two strings in each cell.

  struct listcell2
  {
    char* item1;
    char* item2;
    listcell2* next;
  };

Assignment, part 1: A list module

Write a module that provides support for linked lists, where each list cell has two strings, called the key and the data. This requires creating two files, a header file (list.h) that contains the cell type and function prototypes; and an implementation file (list.cpp) that contains the function implementations. Be sure to include list.h in list.cpp, using

#include "list.h"

Your list module should provide the following functions.

find(L,k,d) searches list L for a cell that contains a key that is the same as string k. It stores the data from that cell into d. So L and k are information coming into this function, and d is information coming out. Function find should return true if it found a cell with key k, and false if there was no such cell. The heading for find should be
```
   bool find(const listcell* L, const char* k, char*& d)
  
```
Notice that d has type char*, but is a reference parameter so that you can change it. You will pass a variable of type char* as the third parameter of find.
attach(L,k,d) creates a new list cell and attaches it to the front of list L. As a result, list L becomes longer. The new list cell should contain key k and data d. The strings k and d must be copied, using strcpy. Do not store pointers to the arrays pointed to by k and d. So if L starts out as

and if k points to "c" and d points to "de", then, after doing attach(L,k,d) you would get the following.

Notice that the pointers in the new list cell do not point to the same arrays k and d that were passed to attach. The heading for attach should be
```
   void attach(listcell*& L, const char *k, const char* d)
  
```
Notice that you need to construct a new list cell to do an attach.
destroy(L) deletes all of the cells in linked list L, and all of the strings that the cells point to. The heading should be
```
   void destroy(listcell* L)
  
```

Test your list module by adding a function that prints the contents of a linked list, for debugging. Then write a small main program that builds a list and prints its contents. Check whether some keys are in the list, and see whether find is working. Look at the results. Are they correct?

Assignment, part 2: A telephone book

Write a program that uses the linked list module as follows. It should read a file called phonebook.txt. Each line contains two strings, a name and a phone number. Assume neither the name nor the number contains any blanks. Read the file. As you read it, construct a linked list, where each cell represents one entry in the phone book. The key should be the name, and the data should be the phone number.

After reading the phone book information, your program should read a name from the user. It should look up the name and print the corresponding phone number. If there is no such name in the list, then your program should show a meaningful message indicating that the name is not in the book.

Your program should then read another name from the user. It should continue reading names until the user types name quit. Then the program should stop.

Warning

Do not compare strings using ==. If you do, you are comparing the pointers to the strings, not the contents of the strings. Instead, use strcmp to compare strings. For example, if you read a name from the user into array name, and then do

  if(name == "quit") {
    return 0;
  }

then you will find that name is never quit. You are asking whether the array name and the string constant "quit" are stored in the same place in memory. They are not. What you want is

  if(strcmp(name, "quit") == 0) {
    return 0;
  }