Selected C Example 10

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";                      }         }     } }