Selected C++ Example #10
// Example #10
// This example illustrates the necessary changes to Example
// #4a when adding a LinkedRing as a new derived class of
// LinkedList.
#include <iostream.h>
#include <new.h>
typedef int DATUM;
// The LinkedRing class requires that we abstract out the
// test for the end of a list into a separate, protected
// polymorphic ''at_end()''method. Since, in a LinkedRing,
// the beginning and end tests of a list are equivalent (i.e.,
// the pointer you have is equal to the head), the loops in
// the linked list methods had to be inverted from while to
// do-while. In addition to these changes, we had to add a
// protected polymorphic method to handle the different
// initialization of a node' s next pointer. LinkedList assigns
// it to NULL, while a LinkedRing assigns it to itself (to make
// a ring of one node).
// Requiring a change to the base class when a new derived
// class is added to an existing hierarchy occurs more often
// than not. This certainly has caused some reusability
// problems when inheritance is involved.
class LinkedList {
protected:
struct Node {
DATUM data;
Node* next;
public:
Node(const DATUM&);
};
virtual Node* ifind(const DATUM&) const;
virtual Node* rfind(const DATUM&) const;
virtual int at_end(const Node*) const;
virtual void set_next(Node*);
void cleanup();
Node* get_head() const;
private:
Node* head;
int length;
public:
LinkedList();
~LinkedList();
int insert(const DATUM&);
int remove(const DATUM&);
void traverse() const;
virtual char* type();
void test();
};
// The at_end method for the LinkedList simply checks the
// current_ptr against NULL.
int
LinkedList::at_end(const Node* current_ptr) const
{
return(current_ptr == NULL);
}
// The set_next method is used to distinguish the LinkedList
// versus LinkedRing behavior of creating nodes. The
// LinkedList wants a NULL next pointer, while the LinkedRing
// wants the next point to reference the object that owns
// it.
void
LinkedList::set_next(Node* new_node)
{
new_node->next = NULL;
}
LinkedList::Node*
LinkedList::get_head() const
{
return(head);
}
LinkedList::Node*
LinkedList::ifind(const DATUM&) const
{
Node* temp = head;
if (temp == NULL) {
return(NULL);
}
while (!at_end(temp->next)) {
temp = temp->next;
}
return(temp);
}
// The remove find method returns three possible values. A
// return of -1 implies that the object to be removed is at
// the head of the list, NULL implies the item is not in
// the list, any other value implies the pointer returned
// is a pointer to the preceding node in the list.
LinkedList::Node*
LinkedList::rfind(const DATUM& bad_item) const
{
Node* found = head, *pre_found = (Node*) -1;
if (head != NULL) {
do {
if (found->data == bad_item) {
return(pre_found);
}
pre_found = found;
found = found->next;
} while (!at_end(found));
}
return(NULL);
}
LinkedList::Node::Node(const DATUM& new_data)
{
data = new_data;
next = NULL;
}
LinkedList::LinkedList()
{
head = NULL;
length = 0;
}
LinkedList::~LinkedList()
{
if (head != NULL)
cleanup();
}
void
LinkedList::cleanup()
{
Node *temp, *current_ptr = head;
do {
temp = current_ptr;
current_ptr = current_ptr->next;
delete temp;
} while (!at_end(current_ptr));
head = NULL;
}
int
LinkedList::insert(const DATUM& new_item)
{
Node* temp = ifind(new_item);
Node* new_node = new Node(new_item);
if (head == NULL) { //Insertion into an empty list
set_next(new_node);
head = new_node;
}
else if (temp == NULL) { // Insertion at the head
new_node->next = head;
head = new_node;
}
else { //All others
new_node->next = temp->next;
temp->next = new_node;
}
return(++length);
}
// Remove gets more complicated because LinkedRings are a
// pain when you need to remove their head node. This
// method does not remove the head node until it is the last
// thing in the list. It will copy the second node' s data
// into the head node and delete the second node instead.
int
LinkedList::remove(const DATUM& bad_item)
{
Node* found = rfind(bad_item);
Node* temp;
if (found == NULL) { // The item is not in the list.
return(0);
}
// The item is in the list, so decrement the count. Then check
// if it is the head, which we want to delete. If it is, then
// check if it is the last item in the list. If so, then
// simply get rid of it. If not, we need to copy the second
// node's data and throw away the second node (to preserve the
// last node in the list's next pointer to the head).
length--;
if (found == (Node*) -1) {
if (!at_end(head->next)){
head->data = head->next->data;
temp = head->next;
head->next = head->next->next;
delete temp;
}
else {
delete head;
head = NULL;
}
return(1);
}
else {
temp = found->next;
found->next = found->next->next;
delete temp;
return(1);
}
}
void
LinkedList::traverse()const
{
Node* temp = head;
cout << ''('';
if (head != NULL) {
do {
cout << temp->data << '' '';
temp = temp->next;
} while(!at_end(temp));
}
cout << '')\n'';
}
char*
LinkedList::type()
{
return(''LinkedList'');
}
// Note the major reuse of the LinkedList abstraction in this
// class. The SortedLinkedList need only redefine three
// protected polymorphic methods from the LinkedList.
class SortedLinkedList:public LinkedList {
protected:
Node* ifind(const DATUM&) const;
Node* rfind(const DATUM&) const;
public:
char* type();
};
LinkedList::Node*
SortedLinkedList::ifind(const DATUM& new_item) const
{
Node *found = get_head(),*pre_found = NULL;
while (found != NULL && found->data < new_item) {
pre_found = found;
found = found->next;
}
return(pre_found);
}
LinkedList::Node*
SortedLinkedList::rfind(const DATUM& bad_item) const
{
Node* found = get_head(), *pre_found = (Node*)-1;
while (found != NULL && found->data <= bad_item) {
if (found->data == bad_item) {
return(pre_found);
}
pre_found = found;
found = found->next;
}
return(NULL);
}
char*
SortedLinkedList::type()
{
return(''SortedLinkedList'');
}
class LinkedRing:public LinkedList {
protected:
int at_end(const Node*) const;
void set_next(Node*);
public:
~LinkedRing();
char* type();
};
LinkedRing::~LinkedRing()
{
if (get_head() != NULL)
cleanup();
}
// The at_end method of a LinkedRing checks if the current
// pointer is equal to the head pointer.
int
LinkedRing::at_end(const Node* current_ptr) const
{
return(current_ptr == get_head());
}
void
LinkedRing::set_next(Node* new_node)
{
new_node->next = new_node;
}
char*
LinkedRing::type()
{
return(''LinkedRing'');
}
void
main()
{
LinkedList x;
SortedLinkedList y;
LinkedRing z;
cout << ''Testing the LinkedList.\n'';
x.test();
cout << ''\n\nTesting the SortedLinkedList.\n'';
y.test();
cout << ''\n\nTesting the LinkedRing.\n'';
z.test();
}
void
LinkedList::test()
{
char c='a';
DATUM num;
int size;
while (c != 'q') {
cout << ''Your '' << type() << '' looks like: '';
traverse();
cout << ''What's your pleasure i)nsert, d)elete, q)uit? '';
cin >> c;
if (c == 'i') {
cout << ''Number to insert: '';
cin >> num;
size = insert(num);
cout << ''Number of elements on the '' << type();
cout << '' is '' << size << -.\n"
}
else if (c == 'd') {
cout << ''Number to delete: '';
cin >> num;
size = remove(num);
if (size == 0) {
cout << ''Couldn't find the number
\'''' << num;
cout << ''\'' in the '' << type() <<
''.\n";
}
else {
cout << ''Found and deleted the
number \'''' << num;
cout << ''\'' from the '' << type()
<< ".\n";
}
}
}
}
|
