Change into your cps100e directory and create a lab7 subdirectory. Then change into this directory and copy files by typing what's below (don't forget the trailing dot).
cp ~ola/cps100e/lab7/* .
If you type "ls" you should see the following files: Makefile, sections.cc, and section.dat.
In this lab you'll work with linked lists and linked lists of linked lists. The problem we'll consider is the following. In large courses, students are usually placed in smaller sections, indicated by section numbers. For organizational purposes, each section will be represented by a linked list of students. The sections will also be linked together in a list. In particular sections will be represented by a SectionNode (shown below)
struct SectionNode
{
int secnum;
SectionNode * next;
StudentNode * list;
SectionNode(int val, SectionNode * ptr1 = NULL, StudentNode * ptr2 = NULL)
{
secnum = val;
next = ptr1;
list = ptr2;
}
};
This node stores the section number, a pointer to another section node,
and a pointer to a linked list of students. This struct contains a constructor
with default values for the pointers. A new SectionNode can be constructed
with just one argument, an integer, and the two pointers will automatically
be set to NULL.
A student is represented by a StudentNode (shown below), which contains
the first and last name of the student, and a pointer to another
student node. A constructor and a function Print are also part of the
struct. If ptr is a pointer to a StudentNode, then
ptr->Print() invokes the Print member function, printing the
name of the student in this node.
struct StudentNode
{
string first;
string last;
StudentNode * next;
StudentNode(string fname, string lname, StudentNode * ptr = NULL)
{
first = fname;
last = lname;
next = ptr;
}
void Print()
{
cout << "\t" << first << " " << last << endl;
}
};
In the example below, the course cps100e has sections 3 and 4 (both represented
by SectionNodes, in '*'s). Section
3 has two persons, and section 4 has 1 person. Students are represented by
StudentNodes, in '+'s.
***** *****
cps100e -> * 3 * -> * 4 * -> ||
***** *****
| |
v v
+++++++ +++++++
+Joe + +Marv +
+Black+ +Brown+
+++++++ +++++++
| |
v v
+++++++ _
+Joan + -
+ Low +
+++++++
|
v
_
-
You'll want to look at the file sections.cc at the same time as you run the program, so type emacs & to start emacs and then use C-xC-f to load the file sections.cc. Then compile and run the program sections.cc by typing make sections . It doesn't do much right now as this program has code missing for four of its functions. The program is intended to read in students from a file and create the linked list of sections each containing a linked list of students, and then traverse the structure and print a list of students in each section, but it has a bug in it.
This program reads input from standard input (cin). When running the program, you can redirect the input to come from a file by using the "<" symbol. To run this program with the data file section.dat type
sections < section.dat
Compile and execute the program. It prints out section 1 and the
students in section 1, then a Segmentation fault occurs. This is
a common error that occurs when working with pointers. The error
message is not very helpful.
To find out where the error occurred in your program, you'll need to use a debugger. We'll use the debugger gdb. To start it for this program, type:
gdb sections
Gdb will load in your program and give you the gdb prompt. To run your program, you normally just type run, but since we want to use a data file, this time you'll type:
(gdb) run < section.datYou'll see the same output as before (list of students in section 1) followed by a Segmentation fault, and its location, line 218 of file CPstring.h (your error might be a different place). Sometimes (as in this case) the error appears to be in a function that you did not write! But usually, the error is in your program, it was caught as you were calling another function, so the execution halted inside the other function.
Let's find out where in the program sections.cc the error occured. Type where at the gdb prompt. When your program "crashed", there were many function calls on the system stack. They are shown in reverse order. Somewhere near the bottom you'll see "main", line 137. On this line, main called the function PrintList, whose call is shown immediately above this line. PrintList was in the process of calling PrintSection. PrintSection must be a recursive function as it "calls itself" multiple times. With each call, the value of current is shown (current is a pointer, so its value is some address). In the topmost call, current has the value 0x0 which represents NULL at line 77 in the file sections.cc.
Take a look at line 77 in sections.cc (to move to a particular line, type "C-x g". If that doesn't work, type M-x goto-line, that is, press the ESC key once followed by "x goto-line", then return, and then a line number), it is:
current->Print();
What does this line do? The pointer current points to a StudentNode,
and current->Print invokes the Print function defined in the definition
of the StudentNode, printing the first and last name of the student.
In the debugger, above all the calls to PrintSection, there is a function
call to StudentNode::Print but the pointer to the student node is NULL
(0x0).
What happens when current has the value NULL? Then current->Print() doesn't make sense since there is no node. When a NULL pointer is dereferenced (try to access a field that doesn't exist), your program crashes and gives you a segmentation fault. It might not crash right away. In this case, as part of the dereferencing the Print function tried to print a string, so it tried to use the << operator in the string class, and it failed. That is why the first error message is from the CPstring.h file.
In the debugger, you can display the values of variables for functions that execution halts in. In your case execution halted in CPstring.h. It was called by lots of functions. Let's reverse steps to one of the functions in sections.cc. At the gdb prompt, type up . Execution is moved back to the function StudentNode::Print. Type up again. Execution is moved back to the function PrintList when current had the value 0x0 or NULL. You'll see something like:
#2 ..... PrintSection (current=0x0) at sections.cc: 77
Type up one more time, to the previous function call of PrintList. This time current will have an address instead of 0x0. Since this current is pointing to something, you can display values in its node. Type display current->first and you should see that current is pointing to a StudentNode with the first name of CHRISTOPHER. Type display current->last and you'll see the last name of this student is ALLARD.
When execution is halted in any function, you can display the current values of variables that have been assigned a value. This is useful when you think your program should do one thing, but it appears to be doing something else. To get more information on the debugger, type help at the gdb prompt.
Fix the error above by placing an "if" check around the body of the function PrintSection, executing the body of only if current is not null. Replace the body by
if (current != 0)
{
current->Print();
PrintSection(current->next);
}
To exit the debugger, type quit. Compile and run your program before moving on to the next part. The program should work correctly now, printing out the names of students by section number.
Before moving on, type ls to list your files. You probably have a file called core that was created when your program had a segmenation fault. This file takes up lots of space and should be removed, type rm core to remove it.
Complete the function InSec that has a pointer to a list of student nodes, and returns true if a particular student is in the list. The main function does not test whether or not this function works correctly. You'll need to add several calls to test it.
Compile and run your program before moving on to the next part.
Complete the function WhichSec, which has a parameter head that is a pointer to a list of SectionNodes, and returns the first section number a particular name appears in. You might want to call the function InSec that you wrote in the previous part. The main function has one call to test whether or not WhichSec works correctly. You should add additional tests.
Compile and run your program before moving on to the next part.
Complete the function Remove which has a parameter to a list of StudentNodes, and removes the student with the name that matches the parameters first and last. If the student is in the list, the student is removed, and true is returned. If the student is not in the list, the list is unchanged and false is returned. If the student appears more than once in the list, only the first occurrence of the student is removed. You'll need to test this function in your main function.
Compile and run your program before moving on to the next part.
Complete the function RemoveFirstOccur which has a parameter to a list of SectionNodes and removes the student with the name that matches the parameters first and last. You might want to use the function Remove that you wrote for the previous part. If the student is in the course, the student is removed. If the student is not in the course, the lists are unchanged. If the student appears more than once in the lists, only the first occurrence of the student is removed. Calls for testing this function appear in the main function, but you might want to add additional calls.
To turn in programs: When your modified program works, you can submit it, along with a README describing how long it took you and what your impressions of the lab are. Type (where N is your section number: 1, 2, or 3):
submit100e lab7secN README sections.cc
The README file should include your name, how long you worked on the program, and anyone you received significant help from. You should also include any comments you have about the lab.
You should receive a message telling you that the programs were submitted correctly.