Guest User

orderedLinkedList.h

a guest
Jun 14th, 2011
431
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.75 KB | None | 0 0
  1. #ifndef H_orderedListType
  2. #define H_orderedListType
  3.  
  4. //***********************************************************
  5. // Author: D.S. Malik
  6. //
  7. // This class specifies the members to implement the basic
  8. // properties of an ordered doubly linked list.
  9. //***********************************************************
  10.  
  11. #include "linkedList.h"
  12.  
  13. using namespace std;
  14.  
  15. template <class Type>
  16. class orderedLinkedList: public linkedListType<Type>
  17. {
  18. public:
  19.     bool search(const Type& searchItem) const;
  20.       //Function to determine whether searchItem is in the list.
  21.       //Postcondition: Returns true if searchItem is in the list,
  22.       //    otherwise the value false is returned.
  23.  
  24.     void insert(const Type& newItem);
  25.       //Function to insert newItem in the list.
  26.       //Postcondition: first points to the new list, newItem
  27.       //    is inserted at the proper place in the list, and
  28.       //    count is incremented by 1.
  29.  
  30.     void insertFirst(const Type& newItem);
  31.       //Function to insert newItem at the beginning of the list.
  32.       //Postcondition: first points to the new list, newItem is
  33.       //    inserted at the beginning of the list, last points to the
  34.       //    last node in the list, and count is incremented by 1.
  35.  
  36.     void insertLast(const Type& newItem);
  37.       //Function to insert newItem at the end of the list.
  38.       //Postcondition: first points to the new list, newItem is
  39.       //    inserted at the end of the list, last points to the
  40.       //    last node in the list, and count is incremented by 1.
  41.  
  42.     void deleteNode(const Type& deleteItem);
  43.       //Function to delete deleteItem from the list.
  44.       //Postcondition: If found, the node containing deleteItem is
  45.       //    deleted from the list; first points to the first node
  46.       //    of the new list, and count is decremented by 1. If
  47.       //    deleteItem is not in the list, an appropriate message
  48.       //    is printed.
  49. };
  50.  
  51. template <class Type>
  52. bool orderedLinkedList<Type>::search(const Type& searchItem) const
  53. {
  54.     bool found = false;
  55.     nodeType<Type> *current; //pointer to traverse the list
  56.  
  57.     current = first;  //start the search at the first node
  58.  
  59.     while (current != NULL && !found)
  60.         if (current->info >= searchItem)
  61.             found = true;
  62.         else
  63.             current = current->link;
  64.  
  65.     if (found)
  66.        found = (current->info == searchItem); //test for equality
  67.  
  68.     return found;
  69. }//end search
  70.  
  71.  
  72. template <class Type>
  73. void orderedLinkedList<Type>::insert(const Type& newItem)
  74. {
  75.     nodeType<Type> *current; //pointer to traverse the list
  76.     nodeType<Type> *trailCurrent; //pointer just before current
  77.     nodeType<Type> *newNode;  //pointer to create a node
  78.  
  79.     bool  found;
  80.  
  81.     newNode = new nodeType<Type>; //create the node
  82.     newNode->info = newItem;   //store newItem in the node
  83.     newNode->link = NULL;      //set the link field of the node
  84.                                //to NULL
  85.  
  86.     if (first == NULL)  //Case 1
  87.     {
  88.         first = newNode;
  89.         last = newNode;
  90.         count++;
  91.     }
  92.     else
  93.     {
  94.         current = first;
  95.         found = false;
  96.  
  97.         while (current != NULL && !found) //search the list
  98.            if (current->info >= newItem)
  99.                found = true;
  100.            else
  101.            {
  102.                trailCurrent = current;
  103.                current = current->link;
  104.            }
  105.  
  106.         if (current == first)      //Case 2
  107.         {
  108.             newNode->link = first;
  109.             first = newNode;
  110.             count++;
  111.         }
  112.         else                       //Case 3
  113.         {
  114.             trailCurrent->link = newNode;
  115.             newNode->link = current;
  116.  
  117.             if (current == NULL)
  118.                 last = newNode;
  119.  
  120.             count++;
  121.         }
  122.     }//end else
  123. }//end insert
  124.  
  125. template<class Type>
  126. void orderedLinkedList<Type>::insertFirst(const Type& newItem)
  127. {
  128.     insert(newItem);
  129. }//end insertFirst
  130.  
  131. template<class Type>
  132. void orderedLinkedList<Type>::insertLast(const Type& newItem)
  133. {
  134.     insert(newItem);
  135. }//end insertLast
  136.  
  137. template<class Type>
  138. void orderedLinkedList<Type>::deleteNode(const Type& deleteItem)
  139. {
  140.     nodeType<Type> *current; //pointer to traverse the list
  141.     nodeType<Type> *trailCurrent; //pointer just before current
  142.     bool found;
  143.  
  144.     if (first == NULL) //Case 1
  145.         cout << "Cannot delete from an empty list." << endl;
  146.     else
  147.     {
  148.         current = first;
  149.         found = false;
  150.  
  151.         while (current != NULL && !found)  //search the list
  152.             if (current->info >= deleteItem)
  153.                 found = true;
  154.             else
  155.             {
  156.                 trailCurrent = current;
  157.                 current = current->link;
  158.             }
  159.  
  160.         if (current == NULL)   //Case 4
  161.             cout << "The item to be deleted is not in the "
  162.                  << "list." << endl;
  163.         else
  164.             if (current->info == deleteItem) //the item to be
  165.                                    //deleted is in the list
  166.             {
  167.                 if (first == current)       //Case 2
  168.                 {
  169.                     first = first->link;
  170.  
  171.                     if (first == NULL)
  172.                         last = NULL;
  173.  
  174.                     delete current;
  175.                 }
  176.                 else                         //Case 3
  177.                 {
  178.                     trailCurrent->link = current->link;
  179.  
  180.                     if (current == last)
  181.                         last = trailCurrent;
  182.  
  183.                     delete current;
  184.                 }
  185.                 count--;
  186.             }
  187.             else                            //Case 4
  188.                 cout << "The item to be deleted is not in the "
  189.                      << "list." << endl;
  190.     }
  191. }//end deleteNode
  192.  
  193.  
  194. #endif
Advertisement
Add Comment
Please, Sign In to add comment