CISC181 lab06, Spring 2007

Introduction

This lab introduces basic linked lists of ints, using structs

This lab is preparation for midterm exam 2, and project 2 .

Learning objectives

By the time you finish (lab06) you'll have demonstrated your ability to:

1. Understand code involving linked lists
2. Write code to add items to the beginning of a linked list

You'll also reinforce the following skills gained in earlier labs

1. Modifying an existing Makefile to add new files
2. Create a tar file to submit multiple files as a single file

Step-by-Step Instructions

Step 1: Read and understand the code in the lab06 directory

In the lab06 directory, there is a Makefile that compiles a program called searchList.

This program consists of three C++ source files, and one Makefile

• intLinkedList.h, a C++ header file (#include file) that defines a struct for a linked list node, and several function prototypes for functions that modify lists built with that struct
• intLinkedList.cc, a C++ source file that provides the function definitions for the functions that were prototyped in the header file intLinkedList.h
• searchList.cc, a C++ source file containing a main program that uses the intLinkedList.h/intLinkedList.cc routines to build a list from an external file (nums.dat) and then allows the user to search the list to see whether a given number is in the list or not.

Here is a sample run of this program. I do a cat on the nums.dat first, so that you can see what numbers are in the file. I've also enabled DEBUG output in the Makefile so that you can see that the linked list matches the numbers in the file.

> cd lab06
> ls
Makefile  intLinkedList.cc  intLinkedList.h  nums.dat  searchList.cc
> make
CC -DDEBUG -c searchList.cc
CC -DDEBUG -c intLinkedList.cc
CC -DDEBUG searchList.o intLinkedList.o -o searchList
> cat nums.dat 
4
76
2
867
3
> ./searchList
DEBUG: Here's the list: 4 76 2 867 3 
At each prompt, enter a number to search for, or q to quit,
 and the program will tell you whether
 that number is in the list 

number (or q to quit): 1
1 is not in the list
number (or q to quit): 2
2 is in the list
number (or q to quit): 3
3 is in the list
number (or q to quit): 4
4 is in the list
number (or q to quit): 5
5 is not in the list
number (or q to quit): 867
867 is in the list
number (or q to quit): 768
768 is not in the list
number (or q to quit): g
0 is not in the list
number (or q to quit): foo
0 is not in the list
number (or q to quit): q
> 

Step 2: Add a new file, searchList2.cc, and modify the Makefile accordingly.

Add a new file to the directory, called searchList2.cc.

At first, this will be a simple copy of the program searchList.cc.In this step all you need to do is

• copy the file searchList.cc to searchList2.cc
• edit the header comment in searchList2.cc to change the filename, and add your name
  • The comment should say something like this (assuming your name is Chris Jones)
    // searchList2.cc by Chris Jones, based on searchList.cc by P. Conrad
• modify the Makefile so that it compiles this program as an additional binary (along with searchList).

Note that:

• searchList.o should be linked together with intLinkedList.o to make the searchList binary, and
• searchList2.o will also be linked (in a separate linking step) with intLinkedList.o to create the searchList2 binary.

There is no need to create a separate intLinkedList2.cc or intLinkedList2.o and you should not do so.

• Doing so misses the point—the point that the routines in intLinkedList.h/intLinkedList.cc are reusable in many different main programs,
• This is similar to how we used the routines in drawings.h/drawings.cpp in many different main programs in Project 1.

Once you have a Makefile that creates two executables, searchList, and searchList2, and they both are identical (except for the file header comment,) you are finished with Step 2—go on to Step 3.

Step 3: Modify searchList2.cc

In searchList2.cc, change the line that says:

addIntsFromFileToEndOfLinkedList(head, tail, infile);

to this:

addEachIntFromFileToStartOfLinkedList(head, tail, infile);

Then try to compile the program. At first, you'll get an error like this:

> make
CC -DDEBUG -c searchList2.cc
"searchList2.cc", line 39: Error: The function "addEachIntFromFileToStartOfLinkedList" must have a prototype.
1 Error(s) detected.
*** Error code 1
make: Fatal error: Command failed for target `searchList2.o'
> 

Modify intLinkedList.h to add the necessary function prototype. As you make the modification, change the header comment to now indicate that the file is a collaboration—it contains some code by P. Conrad's code, and some code by you.

That will fix the compiling error, but then you'll get a linking error:

> make
CC -DDEBUG -c searchList.cc
CC -DDEBUG -c intLinkedList.cc
CC -DDEBUG searchList.o intLinkedList.o -o searchList
CC -DDEBUG -c searchList2.cc
CC -DDEBUG searchList2.o intLinkedList.o -o searchList2
Undefined                       first referenced
 symbol                             in file
void addEachIntFromFileToStartOfLinkedList(Node_S*&,Node_S*&,std::ifstream &) searchList2.o
ld: fatal: Symbol referencing errors. No output written to searchList2
*** Error code 1
make: Fatal error: Command failed for target `searchList2'
> 

So, add the function definition into intLinkedList.cc.

This will require you to think about the proper way to add to the beginning of a linked list. Your lecture notes may help!

As with intLinkedList.h, as you modify intLinkedList.cc, change the header comment to now indicate that the file is a collaboration—it contains some code by P. Conrad's code, and some code by you.

Step 4: Creating a tar file of your finished product.

Don't start this step until you have finished all your programming, and are ready to submit your work.

Follow the directions from lab05, step 7 to create a file called lab06.tar.

Follow the guidelines from lab05, step 7, including

• making sure that you do a make clean before you create your tar file
• changing to one directory higher (so that your tar file contains all its files inside a lab06 directory)
• testing the unpacking of your tar file in a temporary directory somewhere to make sure that when it is unpacked, you get a single lab06 directory containing all your stuff.
  

Finishing up and Submitting

1. Make a script called lab06.txt. In your script, you should
• cd into your lab06 directory
• cat the files that you modified (Makefile, searchList2.cc, intLinkedList.h and intLinkedList.cpp).
• Do make clean; make all
• cat the nums.dat file
• Run your searchList2 executable
2. Then, submit your lab06.txt and your lab06.tar file to WebCT.
3. If your TA typically requests paper output, print your lab06.txt file and give it to your TA.

Grading: 100 points total

End of lab06