Selected C Example 9

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