SHARE
TWEET

Untitled

a guest Apr 18th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***************************************************************
  2. Author:     Dr. Daniel Spiegel, Updated by: Trisha Badlu
  3. Creation Date:  19 April 2017                            
  4. Due Date:   26 April 2017
  5. Assignment:     #4
  6. Filename:       LinkedList.cpp                                  
  7. Course:     CSC136 - 020                                    
  8. Professor Name: Dr. Spiegel  
  9. Purpose:    The purpose of this file is to construct each
  10.         template function of the LinkedList class and
  11.         to create an iterator from the List Iterator
  12.         class.
  13. ***************************************************************/
  14. // File: LinkedList.h
  15. // Linked List class with List Iterator class
  16.  
  17. #include <assert.h>
  18. #include <iostream>
  19. #include "LinkedList.h"
  20.  
  21. using namespace std;
  22.  
  23. // Construct empty LinkedList
  24. template <typename eltType> LinkedList<eltType>::LinkedList() : head(NULL)
  25. {}
  26.  
  27. // Copy constructor. copy() does the deep copy
  28. template <typename eltType>
  29. LinkedList<eltType>::LinkedList(LinkedList<eltType> &cl)
  30. {head = copy( cl.head );}
  31.  
  32. // Free all nodes
  33. template <typename eltType> LinkedList<eltType>::~LinkedList()
  34. {destroy(head);}
  35.  
  36. // Assignment operator: copy() does the deep copy
  37. template <typename eltType>
  38.     LinkedList<eltType>&LinkedList<eltType>::operator =(const LinkedList<eltType>& cl)
  39. {   if (this != &cl)
  40.     {  destroy(head);
  41.        head = copy(cl.head);
  42.     }
  43.   return *this;
  44. }
  45.  
  46. // ************** Must write new version of this function *******************
  47. // Place elt into the list in alphanumeric order
  48. // If element is a duplicate, do not insert, return pointer to element
  49. //  (allowing handling of duplicate)
  50. // Otherwise, return NULL to signify it was the first copy in the list
  51. template <typename eltType> eltType *LinkedList<eltType>::orderedInsert(const eltType &elt)
  52. { node<eltType>* p = head;
  53.   node<eltType>* trailp = NULL;
  54.  
  55.   if(head == NULL){
  56.     head = new node<eltType>(elt);
  57.     head->data = elt;
  58.   }
  59.   if(find(elt) != NULL)
  60.     return &p->data;
  61.   while(p != NULL && p->data < elt){
  62.     trailp = p;
  63.     p = p->next;
  64.   }
  65.     if(trailp == NULL){
  66.       head = new node<eltType>(elt);
  67.       head->next = p;
  68.     }
  69.     else{
  70.       trailp->next = new node<eltType>(elt);
  71.       trailp->next->next = p;
  72.     }
  73.   return NULL;
  74. }
  75.  
  76. // ************** Must write new version of this function *******************
  77. // Is this element in the linked list?
  78. //  If so, return a pointer to the element type
  79. //  Otherwise, return NULL to signify not found
  80. template <typename eltType>
  81. eltType *LinkedList<eltType>::find(const eltType &elt)
  82. { node<eltType>* p = head;
  83.   node<eltType>* trailp = NULL;
  84.   while(p != NULL && p->data != elt){
  85.     trailp = p;
  86.     p = p->next;
  87.     if(trailp->data > elt)
  88.        return NULL;
  89.   }
  90.   if(p == NULL)
  91.     return NULL;
  92.   else
  93.     return &p->data;
  94. }
  95.  
  96. // Inline: Look into this.
  97. template <typename eltType> inline bool LinkedList<eltType>::empty()
  98. {return (head == NULL);}
  99.  
  100.  
  101. // ********************** Must update this function *******************
  102. // *** Make it match the prerequisite that the item will be found ******
  103. // Remove a node in an ordered list
  104. // Pre: Node will be found
  105. template <typename eltType> void LinkedList<eltType>::remove(const eltType &elt)
  106. {   node<eltType>*  p = head;
  107.     node<eltType>*  trailp = NULL;
  108.     while ( p != NULL && p->data != elt )
  109.     {   trailp = p;
  110.         p = p->next;
  111.     }
  112.     if (p == head)
  113.         head = head->next;  // x is first in the LinkedList
  114.     else
  115.         trailp->next = p->next; // x is farther down in the LinkedList
  116.     delete p;
  117. }
  118.  
  119. // Remove all nodes in the linked list, starting at l
  120. template <typename eltType> void LinkedList<eltType>::destroy(node<eltType> *l)
  121. {   while (l != NULL)
  122.     { node<eltType> *doomed = l;
  123.       l = l->next;
  124.       delete doomed;
  125.     }
  126. }
  127.  
  128. // The deep copy. Copy the source list l, one node at a time
  129. template <typename eltType>
  130. node<eltType>* LinkedList<eltType>::copy(node<eltType> *l)
  131. { node<eltType>* first = NULL;    // ptr to beginning of copied LinkedList
  132.   node<eltType>* last = NULL;     // ptr to last item insert in the copy
  133.   if (l != NULL)
  134.   { assert((first=last=new node<eltType>(l->data,NULL)) != NULL);
  135.     for (node<eltType>* source=l->next;source!=NULL;
  136.        source=source->next,last=last->next)
  137.     { last->next = new node<eltType>(source->data,NULL);
  138.       assert(last->next);
  139.     }
  140.   }
  141.   return first;
  142. }
  143. // Output a linked list, using a list iterator
  144. template <typename eltType> ostream& operator<<(ostream &os, const LinkedList<eltType> &l)
  145. { listItr<eltType> lt(l);
  146.   for (lt.start();lt.more();lt.next())
  147.     os << lt.value() << endl;
  148.   return os;
  149. }
  150.  
  151. // Count nodes in a linked list, starting at l
  152. template <typename eltType> int LinkedList<eltType>::countNodes(node<eltType> *p) const
  153. {return ((p) ?  1+countNodes(p->next) : 0);}
  154.  
  155. // Return number of nodes in *this' list
  156. template <typename eltType> int LinkedList<eltType>::countNodesInList() const
  157. {return(countNodes(head));}
  158.  
  159.  
  160. /* ****************************************************************
  161. ************** List Iterator Implementations *******************
  162. ****************************************************************/
  163.  
  164. // Construct a list iterator. It consists of:
  165. //       a reference to a linked list object
  166. //       a pointer to the actual list, initially pointing to its head
  167. template <typename eltType>
  168. listItr<eltType>::listItr(LinkedList<eltType> &l): itr(l),curr(l.head)
  169. {}
  170.  
  171. template <typename eltType>
  172. listItr<eltType>::listItr(const LinkedList<eltType> &l) : itr(l),curr(l.head)
  173. {}
  174.  
  175. // Set curr to point at itr's head
  176. template <typename eltType> void listItr<eltType>::start()
  177. {curr = itr.head;}
  178.  
  179. // Is curr at the end of the list?
  180. template <typename eltType> bool listItr<eltType>::more() const
  181. {return curr != NULL;}
  182.  
  183. // Move curr to next node
  184. template <typename eltType> void listItr<eltType>::next()
  185. {assert( curr != NULL );
  186.   curr = curr->next;
  187. }
  188.  
  189. // Return data in curr's node. Regardless of assert(), this
  190. //      function shouldn't be called until making sure more() returns true
  191. template <typename eltType> eltType &listItr<eltType>::value()
  192. {assert( curr != NULL );
  193.   return curr->data;
  194. }
  195.  
  196. // Return data in curr's node. Regardless of assert(), this
  197. //      function shouldn't be called until making sure more() returns true
  198. template <typename eltType> const eltType &listItr<eltType>::value() const
  199. {assert( curr != NULL );
  200.   return curr->data;
  201. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top