The purpose of this lab is to introduce students to dynamic
memory allocation in C++, and to the linked list data structure.
As you follow the steps below, you will modify an existing Student
class to create a StudentNode class. As we will see, this class will
enable you to store and retrieve information for an arbitrary number of students.
- Dynamic Memory Allocation
Copy the student.cpp file to your computer
and create a NetBeans project to compile and run this program.
As you will see, the main program calls a subset of the Student class
methods to verify they are working correctly.
Remove the code in the main program and replace it with the following.
This code creates a pointer variable called ptr. When the program
is run, space to store a float is dynamically allocated on the heap.
To access this floating point value we use a "*ptr".
float *ptr = new float;
*ptr = 3.14159;
cout << *ptr << endl;
Now add the following code to the main program. This code creates a
pointer variable called john. Now when the program is run, space
to store a Student object is dynamically allocated on the heap. To
access the methods of this object, we can either use "(*john)." or "john->".
The second version is 1/2 the typing and easier to remember, so we will
use this notation for the remainder of the lab.
Student *john = new Student();
Create a second Student pointer called fred in the main program,
and add code to test all of the remaining methods in the Student class.
Cut and paste your main program below when you have it debugged.
- Create StudentNode Class
As you have seen, pointer variables can be used allocate and
access Student objects. What if we want to store 5, 10 or 25 students?
We do not want to declare separate pointers for each student. That
would be too many variables to keep track of. The solution is to create
a linked list of Student objects, where each object contains a
pointer to the next student in the list.
Rename your Student class to StudentNode. Now add one more
private variable called "Next" that is a pointer to a StudentNode.
The syntax to do this is "StudentNode *Next;". Notice that we did not
call "new StudentNode()". Don't worry, we will do this later below.
Your next step is to add some code in the constructor functions to
initialize the Next pointer to its default value. In C++ we use the
"Next = NULL;" to indicate that a pointer variable is currently
pointing to nothing. When you have tested and debugged your code,
copy and paste your new constructor functions below:
- Adding More Methods to StudentNode
Your next task is to add two new methods, getNext and setNext
to the StudentNode class to provide access to Next field. These methods should
be similar to your other get and set methods, except the data type you
are storing this time is of type StudentNode* instead of string or float.
This may take a few minutes. Cut and paste your two new methods below:
- Creating a Linked List of StudentNodes
Now we are finally ready to use the StudentNode class to create a small
linked list of student records. Remove your old code from the main program
and cut and paste the following code. This will create three students for
us to work with.
StudentNode *ptr1 = new StudentNode("John", "Johnson, AR", 2.5);
StudentNode *ptr2 = new StudentNode("Fred", "Fayetteville, AR", 3.5);
StudentNode *ptr3 = new StudentNode("Sam", "Springdale, AR", 2.9);
Now to link these students together, we need to store ptr2 in the Next field of
the ptr1 object, and we need to store ptr3 in the Next field of the ptr2 object.
We do this as follows:
At this point, you can probably visualize the three student records linked together,
with "John" first, "Fred" second, and "Sam" third. In order to get your program to
print these records out for us, edit your "print" method and add the following at the
bottom of the method. This will cause the print method to call itself recursively
to print out the next node in the linked list.
if (Next != NULL)
Once you have made all of these changes, compile and run your new program.
Cut and paste your output below:
- Modifying Your Linked List
Now edit your main program to change the order of the linked
list nodes and add two more students to the linked list of students.
Be very careful that your list does not "loop back on itself".
If this happens, your print command will go into an infinite loop
printing student information, and you will have to kill the program to stop it.
When your code is working, cut and paste your main program below:
- The Final Step
From the previous step, you now know that adding data to a linked list
manually can get tedious very quickly. This is why loops were invented.
Consider the following code. It prompts the user for the name, address and
gpa of 5 students. Cut and paste this code into your main program and
add the code necessary to add each student's information into the linked list.
Hint: you will need to create a StudentNode and connect the pointers somehow.
StudentNode *list = NULL;
for (int i=0; i<5; i++)
cout << "Enter name: ";
cin >> name;
cout << "Enter address: ";
cin >> address;
cout << "Enter GPA: ";
cin >> gpa;
// ADD HERE
Once you have your program working, cut and paste your entire program
into the text box below. You are finished!
- Submit Work
This lab assignment will be submitted electronically
to the TAs once you fill in the fields below and
click on the "submit" button. You do NOT need to print
a copy of this document to hand in.