CS 102 Laboratory Session Six

Dynamic Data and Algorithm Analysis

Goals and Background

This lab involves some advanced preparation.

Files

In ~csci102b/labs/lab6 is some code for manipulating lists:

• lab6listOps.h and .cc are header and implementation files for some list operations.
• testlists.cc is a file with the list functions shown below, and a test program. You will be modifying this in the course of this lab.
• A Makefile for compiling this multi-file program.

Prior to lab . . .

You should also come to lab with a solution to exercise 4 on paper that you can type in and debug it during the lab session.

Exercise 1 (1 checkoff point)

// BUGGY sumList
// PRE: list is a well-formed list
// POST: returns sum of elements in list
// NOTE: only works if ElmtType is a type for which we can do +=)
ElmtType sumList (Node *list)
{
  Node *p = list;
  int sum = 0;

  while (p!=NULL) {
    sum += p->data;
    p->next = p;
  }
  return sum;
}

Draw a box-and-pointer diagram showing the state of sumList on entry with a non-empty list, and after each of several iterations of the loop.

Use gdb (or ddd) to verify your box-and-pointer diagram for the buggy sumList function. HINT: if you print a pointer in gdb you get it's address (in hex). To see what a pointer, p, points to, you can print *p. If two pointers point to the same object, you will know this because they will have the same address.

For checkoff show the t.a. your diagram, what happens in gdb, and what the fix is.

Exercise 2 (1 checkoff point)

// BUGGY append routine
// PRE: list is a well-formed list
// POST: list' is same as list, but with item appended
void append (Node * &list, ElmtType item)
{
  Node *p = list;

  if (p == NULL) {
    insertFront(list, item);
    return;
  }

  while (p->next != NULL) {
    p = p->next;
  }

  p = getNode(item);

}

Create a box-and-pointer diagram for append of an empty list, and append of a non-empty list.

Compile and run the program to test append and verify your appraisal of what it currently does. Use gdb if necessary to get further information.

Fix the problem, and create a box-and-pointer diagram for the corrected version showing the values of the variables at the end of the function.

Exercise 3 (1 checkoff point)

/* 
 * BUGGY deleteKth
 * PRE: list is a well-formed list
 * POST: returns a list the same as list, but with the Kth element deleted.
 *  list' is undefined.
 *  If (k < 1 or k > (length of list)), returns list
 */
Node * deleteKth (Node * &list, int k)
{
  int i;
  Node * p = list;

  if ((list == NULL) || (k < 1)) {
    return list;
  }

  if (k == 1) {
    p = list->next;
    delete list;
    return p;
  }

  for (i = 0; p != NULL && i < k; i++) {
    p = p->next;
  }

  if (p != NULL) {
    p->deleteAfter();
  }

  return list;
}

Assume you create a list with 5 elements. Create box-and-pointer diagrams for deleteKth for various values of k on this list (assuming you always start out with the 5-element list). For each one, show the values of the variables right before you return from the routine.

HINT: As per post-condition, k = 1 means first element, etc. (we are not counting from zero, like we do with C arrays). Also, the function currently works correctly for k = 1, and out-of-bound k.

Compile and run the program to test deleteKth and verify your appraisal of what it currently does. Use gdb if necessary to get further information.

Fix the problem, and create box-and-pointers diagram for the corrected version showing the values of the variables right before returning from the function for the two cases: k = 3 and k = 6 on the 5-element list.

Exercise 4 (2 checkoff points)

Complete the implementation of the function printEveryOther (skeleton of body and call already appear in testlists.cc).

Your implementation must only do about n/2 iterations of the loop, where n is the length of the list. Your code must work for both even- and odd-lengthed lists. Here's the skeleton:

// printEveryOther: prints 1st, 3rd, 5th, ... elements in a list
// PRE: list is a well-formed linked list
void printEveryOther(Node * list)
{
  while (list != NULL) {
    cout << list->data << " ";

    // YOU COMPLETE THE BODY OF THE LOOP
  }
  cout << endl;
}