SHARE
TWEET

Untitled

a guest Dec 6th, 2019 102 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. main.cpp
  2. ---------------------------------------
  3. #include <iostream>
  4.  
  5. using std::cin;
  6. using std::endl;
  7.  
  8. #include <string>
  9.  
  10. using std::string;
  11.  
  12. #include "list.h" // List class definition
  13.  
  14. void instructions();
  15.  
  16. // function to test a List
  17. template< class T >
  18. void testList( List< T > &listObject, const string &typeName )
  19. {
  20.     cout << "Testing a List of " << typeName << " values\n";
  21.  
  22.     instructions(); // display instructions
  23.  
  24.     int choice;
  25.     T value;
  26.     int pos;
  27.  
  28.     do {
  29.         cout << "? ";
  30.         cin >> choice;
  31.  
  32.         switch ( choice ) {
  33.             case 1:
  34.                 cout << "Enter " << typeName << ": ";
  35.                 cin >> value;
  36.                 listObject.insertAtFront( value );
  37.                 listObject.print();
  38.                 break;
  39.  
  40.             case 2:
  41.                 cout << "Enter " << typeName << ": ";
  42.                 cin >> value;
  43.                 listObject.insertAtBack( value );
  44.                 listObject.print();
  45.                 break;
  46.  
  47.             case 3:
  48.                 cout << "Enter " << typeName << ": ";
  49.                 cin >> value;
  50.                 cout << "Enter position to insert: ";
  51.                 cin >> pos;
  52.                 listObject.insertMiddle( value , pos );
  53.                 listObject.print();
  54.                 break;
  55.  
  56.             case 4:
  57.                 if ( listObject.removeFromFront( value ) )
  58.                     cout << value << " removed from list\n";
  59.  
  60.                 listObject.print();
  61.                 break;
  62.  
  63.             case 5:
  64.                 if ( listObject.removeFromBack( value ) )
  65.                     cout << value << " removed from list\n";
  66.  
  67.                 listObject.print();
  68.                 break;
  69.  
  70.             case 6:
  71.                 cout << "Enter position to delete: ";
  72.                 cin >> pos;
  73.                 if ( listObject.removeMiddle( value, pos ) )
  74.                     cout << value << " removed from list\n";
  75.  
  76.                 listObject.print();
  77.                 break;
  78.  
  79.         } // end switch
  80.  
  81.     } while ( choice != 7 ); // end do/while
  82.  
  83.     cout << "End list test\n\n";
  84.  
  85. } // end function testList
  86.  
  87. // display program instructions to user
  88. void instructions()
  89. {
  90.     cout << "Enter one of the following:\n"
  91.          << " 1 to insert at beginning of list\n"
  92.          << " 2 to insert at end of list\n"
  93.          << " 3 to insert at middle in the list\n"
  94.          << " 4 to delete from beginning of list\n"
  95.          << " 5 to delete from end of list\n"
  96.          << " 6 to delete from middle in the list\n"
  97.          << " 7 to end list processing\n";
  98.  
  99. } // end function instructions
  100.  
  101. int main()
  102. {
  103.     // test List of int values
  104.     List< int > integerList;
  105.     testList( integerList, "integer" );
  106.  
  107.     // test List of double values
  108.     List< double > doubleList;
  109.     testList( doubleList, "double" );
  110.  
  111.     return 0;
  112.  
  113. } // end main
  114.  
  115. -------------------------------------------------------------
  116. list.h
  117. --------------------------------
  118. #ifndef LIST_H
  119. #define LIST_H
  120.  
  121. #include <iostream>
  122.  
  123. using std::cout;
  124.  
  125. #include <new>
  126. #include "listnode.h" // ListNode class definition
  127.  
  128. template< class NODETYPE >
  129. class List {
  130.  
  131. public:
  132.     List();      // constructor
  133.     ~List();     // destructor
  134.     void insertAtFront( const NODETYPE & );
  135.     void insertMiddle( const NODETYPE &, int);
  136.     void insertAtBack( const NODETYPE & );
  137.     bool removeFromFront( NODETYPE & );
  138.     bool removeMiddle(NODETYPE &, int);
  139.     bool removeFromBack( NODETYPE & );
  140.     bool isEmpty() const;
  141.     void print() const;
  142.  
  143. private:
  144.     ListNode< NODETYPE > *firstPtr; // pointer to first node
  145.     ListNode< NODETYPE > *lastPtr;   // pointer to last node
  146.  
  147.     // utility function to allocate new node
  148.     ListNode< NODETYPE > *getNewNode( const NODETYPE & );
  149.  
  150. }; // end class List
  151.  
  152. // default constructor
  153. template< class NODETYPE >
  154. List< NODETYPE >::List()
  155.         : firstPtr( 0 ),
  156.           lastPtr( 0 )
  157. {
  158.     // empty body
  159.  
  160. } // end List constructor
  161.  
  162. // destructor
  163. template< class NODETYPE >
  164. List< NODETYPE >::~List()
  165. {
  166.     if ( !isEmpty() ) {    // List is not empty
  167. //      cout << "Destroying nodes ...\n";
  168.  
  169.         ListNode< NODETYPE > *currentPtr = firstPtr;
  170.         ListNode< NODETYPE > *tempPtr;
  171.  
  172.         while ( currentPtr != 0 )         // delete remaining nodes
  173.         {
  174.             tempPtr = currentPtr;
  175.  
  176. // commented out the output -- no need to print what we are deallocating
  177. //         cout << tempPtr->data << '\n';
  178.  
  179.             currentPtr = currentPtr->nextPtr;
  180.             delete tempPtr;
  181.  
  182.         }
  183.  
  184.     }
  185.  
  186. //   cout << "All nodes destroyed\n\n";
  187.  
  188. } // end List destructor
  189.  
  190. // insert node at front of list
  191. template< class NODETYPE >
  192. void List< NODETYPE >::insertAtFront( const NODETYPE &value )
  193. {
  194.     ListNode< NODETYPE > *newPtr = getNewNode( value );
  195.  
  196.     if ( isEmpty() ) // List is empty
  197.         firstPtr = lastPtr = newPtr;
  198.  
  199.     else { // List is not empty
  200.         newPtr->nextPtr = firstPtr;
  201.         firstPtr = newPtr;
  202.  
  203.     } // end else
  204.  
  205. } // end function insertAtFront
  206.  
  207. // insert node at back of list
  208. template< class NODETYPE >
  209. void List< NODETYPE >::insertAtBack( const NODETYPE &value )
  210. {
  211.     ListNode< NODETYPE > *newPtr = getNewNode( value );
  212.  
  213.     if ( isEmpty() ) // List is empty
  214.         firstPtr = lastPtr = newPtr;
  215.  
  216.     else { // List is not empty
  217.         lastPtr->nextPtr = newPtr;
  218.         lastPtr = newPtr;
  219.  
  220.     } // end else
  221.  
  222. } // end function insertAtBack
  223.  
  224. // delete node from front of list
  225. template< class NODETYPE >
  226. bool List< NODETYPE >::removeFromFront( NODETYPE &value )
  227. {
  228.     if ( isEmpty() ) // List is empty
  229.         return false; // delete unsuccessful
  230.  
  231.     else
  232.     {
  233.         ListNode< NODETYPE > *tempPtr = firstPtr;
  234.  
  235.         if ( firstPtr == lastPtr )
  236.             firstPtr = lastPtr = 0;
  237.         else
  238.             firstPtr = firstPtr->nextPtr;
  239.  
  240.         value = tempPtr->data; // data being removed
  241.         delete tempPtr;
  242.  
  243.         return true; // delete successful
  244.  
  245.     } // end else
  246.  
  247. } // end function removeFromFront
  248.  
  249. // delete node from back of list
  250. template< class NODETYPE >
  251. bool List< NODETYPE >::removeFromBack( NODETYPE &value )
  252. {
  253.     if ( isEmpty() )
  254.         return false; // delete unsuccessful
  255.  
  256.     else {
  257.         ListNode< NODETYPE > *tempPtr = lastPtr;
  258.  
  259.         if ( firstPtr == lastPtr )
  260.             firstPtr = lastPtr = 0;
  261.         else {
  262.             ListNode< NODETYPE > *currentPtr = firstPtr;
  263.  
  264.             // locate second-to-last element
  265.             while ( currentPtr->nextPtr != lastPtr )
  266.                 currentPtr = currentPtr->nextPtr;
  267.  
  268.             lastPtr = currentPtr;
  269.             currentPtr->nextPtr = 0;
  270.  
  271.         } // end else
  272.  
  273.         value = tempPtr->data;
  274.         delete tempPtr;
  275.  
  276.         return true; // delete successful
  277.  
  278.     } // end else
  279.  
  280. } // end function removeFromBack
  281.  
  282. // is List empty?
  283. template< class NODETYPE >
  284. bool List< NODETYPE >::isEmpty() const
  285. {
  286.     return firstPtr == 0;
  287.  
  288. } // end function isEmpty
  289.  
  290. // return pointer to newly allocated node
  291. template< class NODETYPE >
  292. ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
  293.         const NODETYPE &value )
  294. {
  295.     return new ListNode< NODETYPE >( value );
  296.  
  297. } // end function getNewNode
  298.  
  299. // display contents of List
  300. template< class NODETYPE >
  301. void List< NODETYPE >::print() const
  302. {
  303.     if ( isEmpty() ) {
  304.         cout << "The list is empty\n\n";
  305.         return;
  306.  
  307.     } // end if
  308.  
  309.     ListNode< NODETYPE > *currentPtr = firstPtr;
  310.  
  311.     cout << "The list is: ";
  312.  
  313.     while ( currentPtr != 0 ) {
  314.         cout << currentPtr->data << ' ';
  315.         currentPtr = currentPtr->nextPtr;
  316.  
  317.     } // end while
  318.  
  319.     cout << "\n\n";
  320.  
  321. } // end function print
  322.  
  323. ////////////////////////////////////////////////////////////////////////////////////////////////
  324. //my functions
  325.  
  326. template< class NODETYPE >
  327. bool List< NODETYPE >::removeMiddle( NODETYPE &value, int spot )
  328. {
  329.     if ( isEmpty() || spot <= 0)                                   //when the list is empty or spot is invalid return flase
  330.         return false;
  331.     else
  332.     {
  333.         ListNode< NODETYPE > *tempPtr = firstPtr;                   //creates temp ptr that intially is the same as the first pointer
  334.         if(spot==1)                                                 //if spot is one call remove from front
  335.         {
  336.             removeFromFront(value);
  337.         }
  338.         else
  339.         {
  340.             for(int i=0; i <spot-2;i++)                            //runs til less than index -2
  341.             {
  342.                 //tempptr now points to whatever the next pointer is
  343.                 if(tempPtr->nextPtr==lastPtr)                      //returns false when spot is beyond list capacity
  344.                 {
  345.                     return false;
  346.                 }
  347.  
  348.                 tempPtr=tempPtr->nextPtr;                          //tempptr points to the (n-1th) node after completion
  349.             }
  350.             ListNode< NODETYPE > *tempPtr2=tempPtr->nextPtr;       //tempptr2 points to the nth node
  351.             tempPtr->nextPtr=tempPtr2->nextPtr;                    //tempptrs next pointer points to (n+1)th node
  352.             return true;
  353.         }
  354.     }
  355. }
  356.  
  357. template< class NODETYPE >
  358. void List< NODETYPE >::insertMiddle( const NODETYPE &value, int spot )
  359. {
  360.     ListNode< NODETYPE > *newPtr = getNewNode( value );         //newptr is a new dynamically allocated ptr to the paramater
  361.     ListNode< NODETYPE > *newPtr2 = firstPtr;                   //newptr2 is now the same as first point
  362.     newPtr->data=value;                                         //the paramaters data is the paramaters data
  363.     newPtr->nextPtr=NULL;                                       //it's next value points to the 0
  364.  
  365.     if ( isEmpty() )                                            // if the List is empty the first ptr, newptr and last ptr are the same
  366.     {
  367.         insertAtFront(value);
  368.         return;
  369.     }
  370.     if(spot <= 1)                                               //if index is <= to first spot then set as index 1
  371.     {
  372.         insertAtFront(value);
  373.         return;
  374.     }
  375.     for(int i=0;i<spot-2;i++)                                   //runs til less than index -2
  376.     {
  377.         //newptr2 now points to whatever the next pointer is
  378.         if(newPtr2->nextPtr==lastPtr)                           //inserts at end when spot is beyond list capacity
  379.         {
  380.             insertAtBack(value);
  381.             return;
  382.         }
  383.         newPtr2= newPtr2->nextPtr;                              //newPtr2 points to the (n-1th) node after completion
  384.     }
  385.     newPtr->nextPtr=newPtr2->nextPtr;                           //newptr's next pointer is the paramater
  386.     newPtr2->nextPtr=newPtr;                                    //newptr2's next ptr is newptr;
  387. }
  388.  
  389. #endif
  390.  
  391.  
  392. -----------------------------------------------------
  393. listnode.h
  394. ------------------------
  395. #ifndef LISTNODE_H
  396. #define LISTNODE_H
  397.  
  398. // forward declaration of class List
  399. template< class NODETYPE > class List;
  400.  
  401. template< class NODETYPE >
  402. class ListNode {
  403.     friend class List< NODETYPE >; // make List a friend
  404.  
  405. public:
  406.     ListNode( const NODETYPE & ); // constructor
  407.     NODETYPE getData() const;      // return data in node
  408.  
  409. private:
  410.     NODETYPE data;                 // data
  411.     ListNode< NODETYPE > *nextPtr; // next node in list
  412.  
  413. }; // end class ListNode
  414.  
  415. // constructor
  416. template< class NODETYPE >
  417. ListNode< NODETYPE >::ListNode( const NODETYPE &info )
  418.         : data( info ),
  419.           nextPtr( 0 )
  420. {
  421.     // empty body
  422.  
  423. } // end ListNode constructor
  424.  
  425. // return copy of data in node
  426. template< class NODETYPE >
  427. NODETYPE ListNode< NODETYPE >::getData() const
  428. {
  429.     return data;
  430.  
  431. } // end function getData
  432.  
  433. #endif
  434. ---------------------------------------------------------------------------
  435. stack.h
  436. ------------------------------------------
  437. #ifndef STACK_H
  438. #define STACK_H
  439. #include "list.h" // List class definition
  440.  
  441. template< class STACKTYPE >
  442. class Stack : private List< STACKTYPE > {
  443.  
  444. public:
  445.     // push calls List function insertAtFront
  446.     void push( const STACKTYPE &data )
  447.     {
  448.         this->insertAtFront(data);
  449.  
  450.     } // end function push
  451.  
  452.     // pop calls List function removeFromFront
  453.     bool pop( STACKTYPE &data )
  454.     {
  455.         return this->removeFromFront( data );
  456.  
  457.     } // end function pop
  458.  
  459.     // isStackEmpty calls List function isEmpty
  460.     bool isStackEmpty() const
  461.     {
  462.         return this->isEmpty();
  463.  
  464.     } // end function isStackEmpty
  465.  
  466.     // printStack calls List function print
  467.     void printStack() const
  468.     {
  469.         this->print();
  470.  
  471.     } // end function print
  472.  
  473. }; // end class Stack
  474.  
  475. #endif
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
Top