Selected C++ Example #9
//Example #9
// This example illustrates the reuse of a linked list
// abstraction in the development of a sorted linked list.
// The linked list has insert and remove methods, which are
// monomorphic. They make use of two polymorphic, protected
// find functions to implemement the differences between the
// two abstractions. Example 4b will illustrate the problem
// with software reuse through inheritance by introducing a
// linked ring class to the design. None of this linked list's
// code will be reusable when we introduce the linked ring
// (the bad news). But with the introduction of a new
// protected abstraction for testing the end of a list, it will
// be able to reuse the abstraction (the good news).
# include <iostream.h>
# include <new.h>
// We show that this class is a good candidate for
// parameterization. We will turn it into a template in
// the selected C++ examples of Chapter 8.
typedef int DATUM;
// The linked list class contains a local, protected data
// type for the nodes. It is protected instead of private
// because the sorted linked list needs access to the type.
// The linked list class also provides two protected polymorphic
// methods for finding (insert and remove, respectively), which
// are used by the insert and remove methods. These will be
// overridden in the derived class ''sorted linked list.''
// The protected get_head method allows the hiding of the
// head pointer' s implementation within the base class ''linked
// list'' while still allowing the derived class to access the
// abstraction.
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;
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();
};
LinkedList::Node*
LinkedList::get_head() const
{
return(head);
}
LinkedList::Node*
LinkedList::ifind(const DATUM&) const
{
Node* temp = head;
if (temp == NULL) {
return(NULL);
}
while(temp->next != NULL) {
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;
while (found != NULL) {
if (found->data == bad_item) {
return(pre_found);
}
pre_found = found;
found = found->next;
}
return(NULL);
}
LinkedList::Node::Node(const DATUM& new_data)
{
data = new_data;
next = NULL;
}
LinkedList::LinkedList()
{
head = NULL;
length = 0;
}
LinkedList::~LinkedList()
{
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
delete temp;
}
}
int
LinkedList::insert(const DATUM& new_item)
{
Node* temp = ifind(new_item);
Node* new_node = new Node(new_item);
if (temp == NULL) {
new_node->next = head;
head = new_node;
}
else {
new_node->next = temp->next;
temp->next = new_node;
}
return(++length);
}
int
LinkedList::remove(const DATUM& bad_item)
{
Node* found = rfind(bad_item);
Node* temp;
if (found == NULL) {
return(0);
}
else if (found == (Node*) -1) {
length--;
temp = head;
head = head->next;
delete temp;
return(1);
}
else {
length--;
temp = found->next;
found->next = found->next->next;
delete temp;
return(1);
}
}
void
LinkedList::traverse()const
{
Node* temp = head;
cout << ''('';
while (temp != NULL) {
cout << temp->data << '' '';
temp = temp->next;
}
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'');
}
void
main()
{
LinkedList x;
SortedLinkedList y;
cout << ''Testing the LinkedList\n'';
x.test();
cout << ''\n\nTesting the SortedLinkedList\n'';
y.test();
}
void
LinkedList::test()
{
char c = 'a';
int size;
DATUM num;
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 num
ber \'' << num;
cout << ''\'' from the '' << type() <<
''.\n'';
}
}
}
}
|