< Free Open Study > |
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''; } } } } |
< Free Open Study > |