The Week in Review program for Week 2 brings together many of the skills you’ve acquired over the past fortnight and produces a powerful program.
This demonstration of linked lists utilizes virtual functions, pure virtual functions, function overriding, polymorphism, public inheritance, function overloading, pointers, references, and more.
On Day 13, “Managing Arrays and Strings,” linked lists were mentioned. In addition, Appendix E, “A Look at Linked Lists,” provides a robust example of using a linked list. If you haven’t looked at Appendix E, don’t fret, linked lists are composed of C++ code you have learned about already. Note that this is a different linked list from the one shown in the appendix; in C++, there are many ways to accomplish the same thing.
The goal of Listing R2.1 is to create a linked list. The nodes on the list are designed to hold parts, as might be used in a factory. Although this is not the final form of this program, it does make a good demonstration of a fairly advanced data structure. The code list is 298 lines. Try to analyze the code on your own before reading the analysis that follows the output.
Listing R2.1. Week 2 in Review Listing
(0)Quit (1)Car (2)Plane: 1
New PartNumber?: 2837
Model Year? 90
(0)Quit (1)Car (2)Plane: 2
New PartNumber?: 378
Engine Number?: 4938
(0)Quit (1)Car (2)Plane: 1
New PartNumber?: 4499
Model Year? 94
(0)Quit (1)Car (2)Plane: 1
New PartNumber?: 3000
Model Year? 93
(0)Quit (1)Car (2)Plane: 0
Part Number: 378
Engine No.: 4938
Part Number: 2837
Model Year: 90
Part Number: 3000
Model Year: 93
Part Number: 4499
Model Year: 94
The Week 2 in Review listing provides a linked list implementation for Part
objects. A linked list is a dynamic data structure; that is, it is like an array but it is sized to fit as objects are added and deleted. Linked lists also include pointers to objects of the same time in order to link the objects together.
This particular linked list is designed to hold objects of class Part
, where Part
is an abstract data type serving as a base class to any objects with a part number. In this example, Part
has been subclassed into CarPart
and AirPlanePart
.
Class Part
is declared on lines 27–37, and consists of a part number and some accessors. Presumably, this class could be fleshed out to hold other important information about the parts, such as what components they are used in, how many are in stock, and so forth. Part
is an abstract data type, enforced by the pure virtual function Display()
.
Note that Display()
does have an implementation, on lines 41–44. It is the designer’s intention that derived classes will be forced to create their own Display()
method, but can chain up to this method as well.
Two simple derived classes, CarPart
and AirPlanePart
, are provided on lines 48–60 and 70–82, respectively. Each provides an overridden Display()
method, which does, in fact, chain up to the base class Display()
method.
The class PartNode
on lines 90–101 serves as the interface between the Part
class and the PartList
class. It contains a pointer to a part and a pointer to the next node in the list. Its only methods are to get and set the next node in the list and to return the Part
to which it points.
The intelligence of the list is, appropriately, in the class PartsList
, whose declaration is on lines 133–148. PartsList
keeps a pointer to the first element in the list (pHead
) and uses that to access all other methods by walking the list. Walking the list means asking each node in the list for the next node, until you reach a node whose next pointer is NULL
.
This is only a partial implementation; a fully developed list would provide either greater access to its first and last nodes, or would provide an iterator object, which allows clients to easily walk the list.
PartsList
nonetheless provides a number of interesting methods, which are listed in alphabetical order. This is often a good idea, as it makes finding the functions easier.
Find()
takes a PartNumber
and an int
(lines 186–200). If the part corresponding to PartNumber
is found, it returns a pointer to the Part
and fills the int
with the position of that part in the list. If PartNumber
is not found, it returns NULL
, and the position is meaningless.
GetCount()
returns the number of elements in the list (line 140). PartsList
keeps this number as a member variable, itsCount
, though it could, of course, compute this number by walking the list.
GetFirst()
returns a pointer to the first Part
in the list, or returns NULL
if the list is empty (line 162–168).
On lines 212–258, the Insert()
method takes a pointer to a Part
, creates a PartNode
for it, and adds the Part
to the list, ordered by PartNumber
.
Iterate()
on lines 202–210 takes a pointer to a member function of Part
, which takes no parameters, returns void
, and is const
. It calls that function for every Part
object in the list. In the sample program, this is called on Display()
, which is a virtual function, so the appropriate Display()
method is called based on the runtime type of the Part
object called.
On lines 170–184, the bracket operator is overloaded. Operator[]
allows direct access to the Part
at the offset provided. Rudimentary bounds checking is provided; if the list is NULL
or if the offset requested is greater than the size of the list, NULL
is returned as an error condition.
Note that in a real program, these comments on the functions would be written into the class declaration.
The driver program starts on line 260. The PartList
object is created on line 263.
On line 277, the user is repeatedly prompted to choose whether to enter a car part or an airplane part. Depending on the choice, the right value is requested, and the appropriate part is created. After it is created, the part is inserted into the list on line 293.
The implementation for the Insert()
method of PartsList
is on lines 212–258. When the first part number is entered, 2837
, a CarPart
with that part number and the model year 90
is created and passed in to LinkedList::Insert()
.
On line 214, a new PartNode
is created with that part, and the variable New
is initialized with the part number. The PartsList
’s itsCount
member variable is incremented on line 220.
On line 222, the test that pHead
is NULL will evaluate true. Because this is the first node, it is true that the PartsList
’s pHead
pointer has zero. Thus, on line 224, pHead
is set to point to the new node and this function returns.
The user is prompted to enter a second part, and this time an AirPlane
part with part number 37
and engine number 4938
is entered. Once again, PartsList::Insert()
is called, and once again, pNode
is initialized with the new node. The static member variable itsCount
is incremented to 2
, and pHead
is tested. Because pHead
was assigned last time, it is no longer null and the test fails.
On line 230, the part number held by pHead
, 2837
, is compared against the current part number, 378
. Because the new one is smaller than the one held by pHead
, the new one must become the new head pointer, and the test on line 230 is true.
On line 232, the new node is set to point to the node currently pointed to by pHead
. Note that this does not point the new node to pHead
, but rather to the node to which pHead
was pointing! On line 233, pHead
is set to point to the new node.
The third time through the loop, the user enters the part number 4499
for a Car
with model year 94
. The counter is incremented and the number this time is not less than the number pointed to by pHead
, so the for
loop that begins on line 237 is entered.
The value pointed to by pHead
is 378
. The value pointed to by the second node is 2837
. The current value is 4499
. The pointer pCurrent
points to the same node as pHead
and so has a next value; pCurrent
points to the second node, and so the test on line 240 fails.
The pointer pCurrent
is set to point to the next node and the loop repeats. This time, the test on line 240 succeeds. There is no next item, so the current node is told to point to the new node on line 242, and the insert is finished.
The fourth time through, the part number 3000
is entered. This proceeds just like the previous iteration, but this time when the current node is pointing to 2837
and the next node has 4499
, the test on line 250 returns TRUE
and the new node is inserted into position.
When the user finally presses 0, the test on line 275 evaluates true and the while
loop breaks. Execution falls to line 296 where Iterate()
is called, branching to line 202 where on line 208 the PNode
is used to access the Part
and the Display()
method is called on that Part
object.
3.15.182.159