CS 102 Laboratory Session Seven

Dynamic Data and Algorithm Analysis

This is the week Eight Lab session, worth 5 points total. Thanks once again to Claire Bono for creating these exercises. Used with permission.

Goals and Background

This lab will give you some practice writing some more linked list code. It uses the same list operations and the same basic test program as we used in the last lab.

Note that the test program uses some of the command codes differently than in the last lab. Type an illegal command to see what the codes are.

This lab involves advance preparation.

Files

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

lab6listOps.h and .cc are header and implementation files for some of the list operations.
testlists7.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 . . .

Prior to lab you should prepare a hand-written solution to dupList and splitAt, described below. You should hand-trace your solution so you feel reasonably confident it is correct, drawing box-and-pointer diagrams to verify what your code does (you do not need to submit your diagrams). You should also prepare test data for each function that thoroughly tests your code.

dupList

Here is the header and comments:

// dupList
// PRE: list is a well-formed list
// POST: returns a list which duplicates all the elements from list
//     e.g., if list = (3 7 2), the routine returns (3 3 7 7 2 2)
// list' is undefined.
//
Node * dupList (Node * list);

Some more details: duplicating a list with no elements, gives you a list with no elements.

The parameter is passed by value, because we're returning the updated list. But here, since the first pointer never gets changed, this function will always return its parameter. The test program calls it as follows:

theList = dupList(theList);

splitAt

Here is the header and comments:

// splitAt
// PRE: theList is a well-formed list
// POST: if value occurs somewhere in theList
//         l1 is a list elements from theList that occurred before first
//          occurrence of value.
//         l2 is a list of elements from value to the end of theList.
//       if value doesn't occur in theList, 
//         l1 has all the elements from theList
//         l2 is empty
//       Original order of elements is maintained.
//       theList' is empty.
//  Ex1: BEFORE call   theList: (5 10 15 20 25)   value: 15 
//       AFTER call    l1: (5 10)    l2: (15 20 25)    theList': <empty>
//
void splitAt (Node * &theList, int value, Node * &l1, Node *&l2);

Note that one or both of the resulting lists (l1 and l2]) may be empty after the call, depending on where we're splitting. Its also legal to call it with an empty theList.

Your implementation must not create or destroy any nodes (i.e., all nodes get "recycled" from theList).

Exercise 1 & 2 (1 checkoff point each)

Show the t.a. your prepared code and test data for each of the two problems (one point for each). You will get the checkoff point if your code is reasonably close to correct, and your test data tests all cases.

Exercise 3 (1 checkoff point) & 4 (2 checkoff points)

Demonstrate for and show to the t.a. your correct solution to the problem. Run it on all your test cases.

This page established September 25, 1999; last updated October 15, 1999 by Rick Wagner.