For week beginning Monday 21 February 2000
From: T. Naughton
In this laboratory you will learn to write linked list applications using classes. There are two programs to write, Problems 5.1 and 5.2. Show a demonstrator a working solution to each problem to get a credit.
Back to CS211 home
In Laboratory 4 you had to implement a linked list solution to the following problem.
Repeat of Problem 4.1 A computer program is required that reads positive integers, one per line, from the keyboard into a list. The user indicates that they are finished by entering any negative integer (the negative integer itself is not stored). The computer program then prints out the list of numbers, on a single line, separated with blank spaces. Write this program using a linked list.
You should have started off by solving Problems 3.2 and 3.4. Below is a solution to Problem 4.1 (text version here). Read it carefully. Make sure you understand all of it.
#include<iostream>
/* This program reads positive integers, one per line, from the
** keyboard into a list. The user indicates that they are finished
** by entering any negative integer (the negative integer itself is
** not stored). The computer program then prints out the list of
** numbers, on a single line, separated with blank spaces. This
** program uses a linked list.
*/
struct ListElement {
int element;
ListElement * next;
};
ListElement * AddtoFront(ListElement * head, int newdata);
ListElement * PrintList(ListElement * list);
ListElement * AddtoFront(ListElement * head, int newdata){
/*
** This function takes a linked list and a piece of data and creates
** a new node with that data, adding it to the front of the list.
*/
ListElement * temp; // Create a pointer to a new node
temp = new ListElement; // Allocate memory for the node
temp->element = newdata; // Put the data in the node
/* Put this node at the top of the list by (a) pointing it at the
** head of the list and (b) repointing the head of the list at this
** node.
** Can you see that the first time we add a node to the list
** (i.e. when head==NULL) that we end up marking the end of the
** list with a NULL?
*/
temp->next = head;
head = temp;
return head;
}
ListElement * PrintList(ListElement * list){
/*
** This function prints out the list. It does so by printing out the
** contents of the head of the list and then repointing the head to
** the next element in the list. It repeats this until the end of the
** list (a NULL) is found. The function returns a pointer to the
** head of the list. Note: this function will work if an empty
** list is passed to it.
*/
ListElement * temp;
temp = list; /* store a pointer to the head of the list
** to keep a record of it while we are
** traversing the list.
*/
cout << endl << endl << "Here's the list:" << endl;
while (list != NULL) {
cout << list->element << ' ';
list = list->next;
}
return temp; /* Return the head of the list again (remember 'list'
** will be pointing to the end of the list).
*/
}
void main(void){
ListElement * list; // a pointer to the head of the list
int tempint; // temporary storage for ints from user
list = NULL; /* Initialise the list (mark the end of the list
** with NULL).
*/
cout << endl << endl << "Please enter positive integers (one ";
cout << "per line). Terminate with any negative integer:" << endl;
cin >> tempint;
while (tempint >= 0) {
list = AddtoFront(list, tempint);
cin >> tempint;
}
list = PrintList(list);
}
The functions to add elements to the list (AddtoFront()) and print out the list (PrintList()) seem to be an integral part of the list structure. In fact, it is possible to build them into the struct definition for ListElement. This makes it clear that they are functions acting on that data structure. For example, here's a struct containing data on a student and functions to process that data:
struct StudentRecord {
int studentId;
char surname[50];
char firstNames[50];
char email[50];
int grades[12];
// functions/procedures
void ReadDetails();
void PrintRecord();
int GradeAverage();
};
An extension to this is to use classes. A class is very like a struct with functions/procedures. However, it also allows us to hide some data from the user of our data structure. In a class, the functions/procedures are called methods, and the function prototypes are called method signatures. For the full story on classes, review your CS100 and CS210 lecture notes. Below is an implementation of Problem 4.1 using classes (text version here).
#include<iostream>
/* This program reads positive integers, one per line, from the
** keyboard into a list. The user indicates that they are finished
** by entering any negative integer (the negative integer itself is
** not stored). The computer program then prints out the list of
** numbers, on a single line, separated with blank spaces. This
** program uses classes and a linked list.
*/
class ListElement {
// A very simple class describing each node of the list
public:
int element;
ListElement * next;
};
class IntList {
ListElement * head; // a pointer to the head of the list (private)
public:
IntList(); // constructor
~IntList(); // destructor
// methods that act on IntList
void AddtoFront(int newdata);
void PrintList();
};
IntList::IntList() {
head = NULL; // Initialise the list (mark the end of the list
// with NULL).
}
IntList::~IntList() {
// The entire list should be deleted here
}
void IntList::AddtoFront(int newdata){
// This function creates a new node with that data that is passed to
// it, adding the node to the front of the list.
ListElement * temp; // Create a pointer to a new node
temp = new ListElement; // Allocate memory for the node
temp->element = newdata; // Put the data in the node
// Put this node at the top of the list by (a) pointing it at the
// head of the list and (b) repointing the head of the list at this
// node.
// Can you see that the first time we add a node to the list
// (i.e. when head==NULL) that we end up marking the end of the
// list with a NULL?
temp->next = head;
head = temp;
}
void IntList::PrintList(){
// This function prints out the list. It does so by printing out the
// contents of the head of the list and then each subsequent element
// in turn. It repeats this until the end of the
// list (a NULL) is found. The function returns a pointer to the
// head of the list. Note: this function will work if an empty
// list is passed to it.
ListElement * current;
current = head; // set current to point to the head of the list
cout << endl << endl << "Here's the list:" << endl;
while (current != NULL) {
cout << current->element << ' ';
current = current->next;
}
}
void main(void){
IntList list;
int tempint; // temporary storage for ints from user
cout << endl << endl << "Please enter positive integers (one ";
cout << "per line). Terminate with any negative integer:" << endl;
cin >> tempint;
while (tempint >= 0) {
list.AddtoFront(tempint);
cin >> tempint;
}
list.PrintList();
}
Some things to notice about this class implementation of Problem 4.1:
The head of the list becomes part of the data structure, and so its declaration can be taken out of main().
Initialising the list becomes the job of the constructor, so that can be taken out of main() also.
Because the head of the list is now a variable within the class, it does not need to be passed to and from AddtoFront() and PrintList(), making these method signatures much neater than the equivalent function prototypes of the struct implementation above.
Right so, here are the problems. As you can see, they are very similar to last week's problems. Those students who do work outside lab time will be well rewarded!
Problem 5.1 Update the solution to Problem 4.1 (above) that uses classes and a linked list by adding the following functionality:
return true/false if a given integer is in the list,
add a node to the end of the list,
delete the entire list,
count the number of elements in the list.
Problem 5.2 Update your solution to Problem 5.1 by adding the following functionality:
delete a given integer from the list,
print the list out in the opposite direction to PrintList() given above.
You can test the functions by calling them in main().
As soon as you are finished a problem, please show your solution to a demonstrator and they will mark you down for a credit (one credit per problem). Good luck!
End of Lab Sheet
