Previous Section  < Free Open Study >  Next Section

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'';

                  }

         }

    }

}

    Previous Section  < Free Open Study >  Next Section