From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001 From: Sven Eisenhauer Date: Fri, 10 Nov 2023 15:11:48 +0100 Subject: add new repo --- .../Codebeispiele/6_ch17/fig17_03_05/fig17_05.cpp | 105 ++++++++++ .../Prog2/Codebeispiele/6_ch17/fig17_03_05/list.h | 216 +++++++++++++++++++++ .../Codebeispiele/6_ch17/fig17_03_05/listnode.h | 56 ++++++ .../Codebeispiele/6_ch17/fig17_10_11/fig17_11.cpp | 72 +++++++ .../Prog2/Codebeispiele/6_ch17/fig17_10_11/list.h | 216 +++++++++++++++++++++ .../Codebeispiele/6_ch17/fig17_10_11/listnode.h | 56 ++++++ .../Prog2/Codebeispiele/6_ch17/fig17_10_11/stack.h | 57 ++++++ .../Codebeispiele/6_ch17/fig17_12/fig17_12test.cpp | 69 +++++++ .../Prog2/Codebeispiele/6_ch17/fig17_12/list.h | 216 +++++++++++++++++++++ .../Prog2/Codebeispiele/6_ch17/fig17_12/listnode.h | 56 ++++++ .../6_ch17/fig17_12/stackcomposition.h | 62 ++++++ .../Codebeispiele/6_ch17/fig17_13_14/fig17_14.cpp | 72 +++++++ .../Prog2/Codebeispiele/6_ch17/fig17_13_14/list.h | 216 +++++++++++++++++++++ .../Codebeispiele/6_ch17/fig17_13_14/listnode.h | 56 ++++++ .../Prog2/Codebeispiele/6_ch17/fig17_13_14/queue.h | 57 ++++++ .../6_ch17/fig17_13_14/queuecomposition.h | 59 ++++++ .../Prog2/Codebeispiele/6_ch17/fig17_17_19/Tree.h | 159 +++++++++++++++ .../Codebeispiele/6_ch17/fig17_17_19/Treenode.h | 54 ++++++ .../Codebeispiele/6_ch17/fig17_17_19/fig17_19.cpp | 76 ++++++++ 19 files changed, 1930 insertions(+) create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/fig17_05.cpp create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/list.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/listnode.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/fig17_11.cpp create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/list.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/listnode.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/stack.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/fig17_12test.cpp create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/list.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/listnode.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/stackcomposition.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/fig17_14.cpp create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/list.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/listnode.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queue.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queuecomposition.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Tree.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Treenode.h create mode 100644 Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/fig17_19.cpp (limited to 'Bachelor/Prog2/Codebeispiele/6_ch17') diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/fig17_05.cpp b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/fig17_05.cpp new file mode 100644 index 0000000..4ca0d87 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/fig17_05.cpp @@ -0,0 +1,105 @@ +// Fig. 17.5: fig17_05.cpp +// List class test program. +#include + +using std::cin; +using std::endl; + +#include + +using std::string; + +#include "list.h" // List class definition + +// function to test a List +template< class T > +void testList( List< T > &listObject, const string &typeName ) +{ + cout << "Testing a List of " << typeName << " values\n"; + + instructions(); // display instructions + + int choice; + T value; + + do { + cout << "? "; + cin >> choice; + + switch ( choice ) { + case 1: + cout << "Enter " << typeName << ": "; + cin >> value; + listObject.insertAtFront( value ); + listObject.print(); + break; + + case 2: + cout << "Enter " << typeName << ": "; + cin >> value; + listObject.insertAtBack( value ); + listObject.print(); + break; + + case 3: + if ( listObject.removeFromFront( value ) ) + cout << value << " removed from list\n"; + + listObject.print(); + break; + + case 4: + if ( listObject.removeFromBack( value ) ) + cout << value << " removed from list\n"; + + listObject.print(); + break; + + } // end switch + + } while ( choice != 5 ); // end do/while + + cout << "End list test\n\n"; + +} // end function testList + +// display program instructions to user +void instructions() +{ + cout << "Enter one of the following:\n" + << " 1 to insert at beginning of list\n" + << " 2 to insert at end of list\n" + << " 3 to delete from beginning of list\n" + << " 4 to delete from end of list\n" + << " 5 to end list processing\n"; + +} // end function instructions + +int main() +{ + // test List of int values + List< int > integerList; + testList( integerList, "integer" ); + + // test List of double values + List< double > doubleList; + testList( doubleList, "double" ); + + return 0; + +} // end main + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/list.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/list.h new file mode 100644 index 0000000..bf97eb2 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/list.h @@ -0,0 +1,216 @@ +// Fig. 17.4: list.h +// Template List class definition. +#ifndef LIST_H +#define LIST_H + +#include + +using std::cout; + +#include +#include "listnode.h" // ListNode class definition + +template< class NODETYPE > +class List { + +public: + List(); // constructor + ~List(); // destructor + void insertAtFront( const NODETYPE & ); + void insertAtBack( const NODETYPE & ); + bool removeFromFront( NODETYPE & ); + bool removeFromBack( NODETYPE & ); + bool isEmpty() const; + void print() const; + +private: + ListNode< NODETYPE > *firstPtr; // pointer to first node + ListNode< NODETYPE > *lastPtr; // pointer to last node + + // utility function to allocate new node + ListNode< NODETYPE > *getNewNode( const NODETYPE & ); + +}; // end class List + +// default constructor +template< class NODETYPE > +List< NODETYPE >::List() + : firstPtr( 0 ), + lastPtr( 0 ) +{ + // empty body + +} // end List constructor + +// destructor +template< class NODETYPE > +List< NODETYPE >::~List() +{ + if ( !isEmpty() ) { // List is not empty + cout << "Destroying nodes ...\n"; + + ListNode< NODETYPE > *currentPtr = firstPtr; + ListNode< NODETYPE > *tempPtr; + + while ( currentPtr != 0 ) { // delete remaining nodes + tempPtr = currentPtr; + cout << tempPtr->data << '\n'; + currentPtr = currentPtr->nextPtr; + delete tempPtr; + + } // end while + + } // end if + + cout << "All nodes destroyed\n\n"; + +} // end List destructor + +// insert node at front of list +template< class NODETYPE > +void List< NODETYPE >::insertAtFront( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + newPtr->nextPtr = firstPtr; + firstPtr = newPtr; + + } // end else + +} // end function insertAtFront + +// insert node at back of list +template< class NODETYPE > +void List< NODETYPE >::insertAtBack( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + lastPtr->nextPtr = newPtr; + lastPtr = newPtr; + + } // end else + +} // end function insertAtBack + +// delete node from front of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromFront( NODETYPE &value ) +{ + if ( isEmpty() ) // List is empty + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = firstPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else + firstPtr = firstPtr->nextPtr; + + value = tempPtr->data; // data being removed + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function removeFromFront + +// delete node from back of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromBack( NODETYPE &value ) +{ + if ( isEmpty() ) + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = lastPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else { + ListNode< NODETYPE > *currentPtr = firstPtr; + + // locate second-to-last element + while ( currentPtr->nextPtr != lastPtr ) + currentPtr = currentPtr->nextPtr; + + lastPtr = currentPtr; + currentPtr->nextPtr = 0; + + } // end else + + value = tempPtr->data; + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function removeFromBack + +// is List empty? +template< class NODETYPE > +bool List< NODETYPE >::isEmpty() const +{ + return firstPtr == 0; + +} // end function isEmpty + +// return pointer to newly allocated node +template< class NODETYPE > +ListNode< NODETYPE > *List< NODETYPE >::getNewNode( + const NODETYPE &value ) +{ + return new ListNode< NODETYPE >( value ); + +} // end function getNewNode + +// display contents of List +template< class NODETYPE > +void List< NODETYPE >::print() const +{ + if ( isEmpty() ) { + cout << "The list is empty\n\n"; + return; + + } // end if + + ListNode< NODETYPE > *currentPtr = firstPtr; + + cout << "The list is: "; + + while ( currentPtr != 0 ) { + cout << currentPtr->data << ' '; + currentPtr = currentPtr->nextPtr; + + } // end while + + cout << "\n\n"; + +} // end function print + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/listnode.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/listnode.h new file mode 100644 index 0000000..325d5f1 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_03_05/listnode.h @@ -0,0 +1,56 @@ +// Fig. 17.3: listnode.h +// Template ListNode class definition. +#ifndef LISTNODE_H +#define LISTNODE_H + +// forward declaration of class List +template< class NODETYPE > class List; + +template< class NODETYPE > +class ListNode { + friend class List< NODETYPE >; // make List a friend + +public: + ListNode( const NODETYPE & ); // constructor + NODETYPE getData() const; // return data in node + +private: + NODETYPE data; // data + ListNode< NODETYPE > *nextPtr; // next node in list + +}; // end class ListNode + +// constructor +template< class NODETYPE > +ListNode< NODETYPE >::ListNode( const NODETYPE &info ) + : data( info ), + nextPtr( 0 ) +{ + // empty body + +} // end ListNode constructor + +// return copy of data in node +template< class NODETYPE > +NODETYPE ListNode< NODETYPE >::getData() const +{ + return data; + +} // end function getData + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/fig17_11.cpp b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/fig17_11.cpp new file mode 100644 index 0000000..0571059 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/fig17_11.cpp @@ -0,0 +1,72 @@ +// Fig. 17.11: fig17_11.cpp +// Template Stack class test program. +#include + +using std::endl; + +#include "stack.h" // Stack class definition + +int main() +{ + Stack< int > intStack; // create Stack of ints + + cout << "processing an integer Stack" << endl; + + // push integers onto intStack + for ( int i = 0; i < 4; i++ ) { + intStack.push( i ); + intStack.printStack(); + + } // end for + + // pop integers from intStack + int popInteger; + + while ( !intStack.isStackEmpty() ) { + intStack.pop( popInteger ); + cout << popInteger << " popped from stack" << endl; + intStack.printStack(); + + } // end while + + Stack< double > doubleStack; // create Stack of doubles + double value = 1.1; + + cout << "processing a double Stack" << endl; + + // push floating-point values onto doubleStack + for ( int j = 0; j < 4; j++ ) { + doubleStack.push( value ); + doubleStack.printStack(); + value += 1.1; + + } // end for + + // pop floating-point values from doubleStack + double popDouble; + + while ( !doubleStack.isStackEmpty() ) { + doubleStack.pop( popDouble ); + cout << popDouble << " popped from stack" << endl; + doubleStack.printStack(); + + } // end while + + return 0; + +} // end main + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/list.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/list.h new file mode 100644 index 0000000..c6d2219 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/list.h @@ -0,0 +1,216 @@ +// Fig. 15.4: list.h +// Template List class definition. +#ifndef LIST_H +#define LIST_H + +#include + +using std::cout; + +#include +#include "listnode.h" // ListNode class definition + +template< class NODETYPE > +class List { + +public: + List(); // constructor + ~List(); // destructor + void insertAtFront( const NODETYPE & ); + void insertAtBack( const NODETYPE & ); + bool removeFromFront( NODETYPE & ); + bool removeFromBack( NODETYPE & ); + bool isEmpty() const; + void print() const; + +private: + ListNode< NODETYPE > *firstPtr; // pointer to first node + ListNode< NODETYPE > *lastPtr; // pointer to last node + + // utility function to allocate new node + ListNode< NODETYPE > *getNewNode( const NODETYPE & ); + +}; // end class List + +// default constructor +template< class NODETYPE > +List< NODETYPE >::List() + : firstPtr( 0 ), + lastPtr( 0 ) +{ + // empty body + +} // end List constructor + +// destructor +template< class NODETYPE > +List< NODETYPE >::~List() +{ + if ( !isEmpty() ) { // List is not empty + cout << "Destroying nodes ...\n"; + + ListNode< NODETYPE > *currentPtr = firstPtr; + ListNode< NODETYPE > *tempPtr; + + while ( currentPtr != 0 ) { // delete remaining nodes + tempPtr = currentPtr; + cout << tempPtr->data << '\n'; + currentPtr = currentPtr->nextPtr; + delete tempPtr; + + } // end while + + } // end if + + cout << "All nodes destroyed\n\n"; + +} // end ~List destructor + +// insert node at front of list +template< class NODETYPE > +void List< NODETYPE >::insertAtFront( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + newPtr->nextPtr = firstPtr; + firstPtr = newPtr; + + } // end else + +} // end function insertAtFront + +// insert node at back of list +template< class NODETYPE > +void List< NODETYPE >::insertAtBack( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + lastPtr->nextPtr = newPtr; + lastPtr = newPtr; + + } // end else + +} // end function insertAtBack + +// delete node from front of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromFront( NODETYPE &value ) +{ + if ( isEmpty() ) // List is empty + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = firstPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else + firstPtr = firstPtr->nextPtr; + + value = tempPtr->data; // data being removed + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function deleteFromFront + +// delete node from back of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromBack( NODETYPE &value ) +{ + if ( isEmpty() ) + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = lastPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else { + ListNode< NODETYPE > *currentPtr = firstPtr; + + // locate second-to-last element + while ( currentPtr->nextPtr != lastPtr ) + currentPtr = currentPtr->nextPtr; + + lastPtr = currentPtr; + currentPtr->nextPtr = 0; + + } // end else + + value = tempPtr->data; + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function deleteFromBack + +// is List empty? +template< class NODETYPE > +bool List< NODETYPE >::isEmpty() const +{ + return firstPtr == 0; + +} // end function isEmpty + +// return pointer to newly allocated node +template< class NODETYPE > +ListNode< NODETYPE > *List< NODETYPE >::getNewNode( + const NODETYPE &value ) +{ + return new ListNode< NODETYPE >( value ); + +} // end function getNewNode + +// display contents of List +template< class NODETYPE > +void List< NODETYPE >::print() const +{ + if ( isEmpty() ) { + cout << "The list is empty\n\n"; + return; + + } // end if + + ListNode< NODETYPE > *currentPtr = firstPtr; + + cout << "The list is: "; + + while ( currentPtr != 0 ) { + cout << currentPtr->data << ' '; + currentPtr = currentPtr->nextPtr; + + } // end while + + cout << "\n\n"; + +} // end function print + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/listnode.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/listnode.h new file mode 100644 index 0000000..7980786 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/listnode.h @@ -0,0 +1,56 @@ +// Fig. 15.3: listnode.h +// Template ListNode class definition. +#ifndef LISTNODE_H +#define LISTNODE_H + +// forward declaration of class List +template< class NODETYPE > class List; + +template< class NODETYPE > +class ListNode { + friend class List< NODETYPE >; // make List a friend + +public: + ListNode( const NODETYPE & ); // constructor + NODETYPE getData() const; // return data in node + +private: + NODETYPE data; // data + ListNode< NODETYPE > *nextPtr; // next node in list + +}; // end class ListNode + +// constructor +template< class NODETYPE > +ListNode< NODETYPE >::ListNode( const NODETYPE &info ) + : data( info ), + nextPtr( 0 ) +{ + // empty body + +} // end ListNode constructor + +// return copy of data in node +template< class NODETYPE > +NODETYPE ListNode< NODETYPE >::getData() const +{ + return data; + +} // end function getData + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/stack.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/stack.h new file mode 100644 index 0000000..bc883ea --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_10_11/stack.h @@ -0,0 +1,57 @@ +// Fig. 17.10: stack.h +// Template Stack class definition derived from class List. +#ifndef STACK_H +#define STACK_H + +#include "list.h" // List class definition + +template< class STACKTYPE > +class Stack : private List< STACKTYPE > { + +public: + // push calls List function insertAtFront + void push( const STACKTYPE &data ) + { + insertAtFront( data ); + + } // end function push + + // pop calls List function removeFromFront + bool pop( STACKTYPE &data ) + { + return removeFromFront( data ); + + } // end function pop + + // isStackEmpty calls List function isEmpty + bool isStackEmpty() const + { + return isEmpty(); + + } // end function isStackEmpty + + // printStack calls List function print + void printStack() const + { + print(); + + } // end function print + +}; // end class Stack + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/fig17_12test.cpp b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/fig17_12test.cpp new file mode 100644 index 0000000..3adb315 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/fig17_12test.cpp @@ -0,0 +1,69 @@ +// Fig. 17.11: fig17_11.cpp +// Template Stack class test program. +#include + +using std::endl; + +#include "stackcomposition.h" // Stack class definition + +int main() +{ + Stack< int > intStack; // create Stack of ints + int popInteger; + + cout << "processing an integer Stack" << endl; + + // push integers onto intStack + for ( int i = 0; i < 4; i++ ) { + intStack.push( i ); + intStack.printStack(); + + } // end for + + // pop integers from intStack + while ( !intStack.isStackEmpty() ) { + intStack.pop( popInteger ); + cout << popInteger << " popped from stack" << endl; + intStack.printStack(); + + } // end while + + Stack< double > doubleStack; // create Stack of doubles + double value = 1.1, popdouble; + + cout << "processing a double Stack" << endl; + + // push floating-point values onto doubleStack + for ( int j = 0; j< 4; j++ ) { + doubleStack.push( value ); + doubleStack.printStack(); + value += 1.1; + + } // end for + + // pop floating-point values from doubleStack + while ( !doubleStack.isStackEmpty() ) { + doubleStack.pop( popdouble ); + cout << popdouble << " popped from stack" << endl; + doubleStack.printStack(); + + } // end while + + return 0; + +} // end main + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/list.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/list.h new file mode 100644 index 0000000..c6d2219 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/list.h @@ -0,0 +1,216 @@ +// Fig. 15.4: list.h +// Template List class definition. +#ifndef LIST_H +#define LIST_H + +#include + +using std::cout; + +#include +#include "listnode.h" // ListNode class definition + +template< class NODETYPE > +class List { + +public: + List(); // constructor + ~List(); // destructor + void insertAtFront( const NODETYPE & ); + void insertAtBack( const NODETYPE & ); + bool removeFromFront( NODETYPE & ); + bool removeFromBack( NODETYPE & ); + bool isEmpty() const; + void print() const; + +private: + ListNode< NODETYPE > *firstPtr; // pointer to first node + ListNode< NODETYPE > *lastPtr; // pointer to last node + + // utility function to allocate new node + ListNode< NODETYPE > *getNewNode( const NODETYPE & ); + +}; // end class List + +// default constructor +template< class NODETYPE > +List< NODETYPE >::List() + : firstPtr( 0 ), + lastPtr( 0 ) +{ + // empty body + +} // end List constructor + +// destructor +template< class NODETYPE > +List< NODETYPE >::~List() +{ + if ( !isEmpty() ) { // List is not empty + cout << "Destroying nodes ...\n"; + + ListNode< NODETYPE > *currentPtr = firstPtr; + ListNode< NODETYPE > *tempPtr; + + while ( currentPtr != 0 ) { // delete remaining nodes + tempPtr = currentPtr; + cout << tempPtr->data << '\n'; + currentPtr = currentPtr->nextPtr; + delete tempPtr; + + } // end while + + } // end if + + cout << "All nodes destroyed\n\n"; + +} // end ~List destructor + +// insert node at front of list +template< class NODETYPE > +void List< NODETYPE >::insertAtFront( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + newPtr->nextPtr = firstPtr; + firstPtr = newPtr; + + } // end else + +} // end function insertAtFront + +// insert node at back of list +template< class NODETYPE > +void List< NODETYPE >::insertAtBack( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + lastPtr->nextPtr = newPtr; + lastPtr = newPtr; + + } // end else + +} // end function insertAtBack + +// delete node from front of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromFront( NODETYPE &value ) +{ + if ( isEmpty() ) // List is empty + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = firstPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else + firstPtr = firstPtr->nextPtr; + + value = tempPtr->data; // data being removed + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function deleteFromFront + +// delete node from back of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromBack( NODETYPE &value ) +{ + if ( isEmpty() ) + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = lastPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else { + ListNode< NODETYPE > *currentPtr = firstPtr; + + // locate second-to-last element + while ( currentPtr->nextPtr != lastPtr ) + currentPtr = currentPtr->nextPtr; + + lastPtr = currentPtr; + currentPtr->nextPtr = 0; + + } // end else + + value = tempPtr->data; + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function deleteFromBack + +// is List empty? +template< class NODETYPE > +bool List< NODETYPE >::isEmpty() const +{ + return firstPtr == 0; + +} // end function isEmpty + +// return pointer to newly allocated node +template< class NODETYPE > +ListNode< NODETYPE > *List< NODETYPE >::getNewNode( + const NODETYPE &value ) +{ + return new ListNode< NODETYPE >( value ); + +} // end function getNewNode + +// display contents of List +template< class NODETYPE > +void List< NODETYPE >::print() const +{ + if ( isEmpty() ) { + cout << "The list is empty\n\n"; + return; + + } // end if + + ListNode< NODETYPE > *currentPtr = firstPtr; + + cout << "The list is: "; + + while ( currentPtr != 0 ) { + cout << currentPtr->data << ' '; + currentPtr = currentPtr->nextPtr; + + } // end while + + cout << "\n\n"; + +} // end function print + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/listnode.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/listnode.h new file mode 100644 index 0000000..7980786 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/listnode.h @@ -0,0 +1,56 @@ +// Fig. 15.3: listnode.h +// Template ListNode class definition. +#ifndef LISTNODE_H +#define LISTNODE_H + +// forward declaration of class List +template< class NODETYPE > class List; + +template< class NODETYPE > +class ListNode { + friend class List< NODETYPE >; // make List a friend + +public: + ListNode( const NODETYPE & ); // constructor + NODETYPE getData() const; // return data in node + +private: + NODETYPE data; // data + ListNode< NODETYPE > *nextPtr; // next node in list + +}; // end class ListNode + +// constructor +template< class NODETYPE > +ListNode< NODETYPE >::ListNode( const NODETYPE &info ) + : data( info ), + nextPtr( 0 ) +{ + // empty body + +} // end ListNode constructor + +// return copy of data in node +template< class NODETYPE > +NODETYPE ListNode< NODETYPE >::getData() const +{ + return data; + +} // end function getData + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/stackcomposition.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/stackcomposition.h new file mode 100644 index 0000000..2a603d7 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_12/stackcomposition.h @@ -0,0 +1,62 @@ +// Fig. 17.12: stackcomposition.h +// Template Stack class definition with composed List object. +#ifndef STACKCOMPOSITION +#define STACKCOMPOSITION + +#include "list.h" // List class definition + +template< class STACKTYPE > +class Stack { + +public: + // no constructor; List constructor does initialization + + // push calls stackList object's insertAtFront function + void push( const STACKTYPE &data ) + { + stackList.insertAtFront( data ); + + } // end function push + + // pop calls stackList object's removeFromFront function + bool pop( STACKTYPE &data ) + { + return stackList.removeFromFront( data ); + + } // end function pop + + // isStackEmpty calls stackList object's isEmpty function + bool isStackEmpty() const + { + return stackList.isEmpty(); + + } // end function isStackEmpty + + // printStack calls stackList object's print function + void printStack() const + { + stackList.print(); + + } // end function printStack + +private: + List< STACKTYPE > stackList; // composed List object + +}; // end class Stack + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/fig17_14.cpp b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/fig17_14.cpp new file mode 100644 index 0000000..a5c24d5 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/fig17_14.cpp @@ -0,0 +1,72 @@ +// Fig. 17.14: fig17_14.cpp +// Template Queue class test program. +#include + +using std::endl; + +#include "queue.h" // Queue class definition + +int main() +{ + Queue< int > intQueue; // create Queue of ints + + cout << "processing an integer Queue" << endl; + + // enqueue integers onto intQueue + for ( int i = 0; i < 4; i++ ) { + intQueue.enqueue( i ); + intQueue.printQueue(); + + } // end for + + // dequeue integers from intQueue + int dequeueInteger; + + while ( !intQueue.isQueueEmpty() ) { + intQueue.dequeue( dequeueInteger ); + cout << dequeueInteger << " dequeued" << endl; + intQueue.printQueue(); + + } // end while + + Queue< double > doubleQueue; // create Queue of doubles + double value = 1.1; + + cout << "processing a double Queue" << endl; + + // enqueue floating-point values onto doubleQueue + for ( int j = 0; j< 4; j++ ) { + doubleQueue.enqueue( value ); + doubleQueue.printQueue(); + value += 1.1; + + } // end for + + // dequeue floating-point values from doubleQueue + double dequeueDouble; + + while ( !doubleQueue.isQueueEmpty() ) { + doubleQueue.dequeue( dequeueDouble ); + cout << dequeueDouble << " dequeued" << endl; + doubleQueue.printQueue(); + + } // end while + + return 0; + +} // end main + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/list.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/list.h new file mode 100644 index 0000000..c6d2219 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/list.h @@ -0,0 +1,216 @@ +// Fig. 15.4: list.h +// Template List class definition. +#ifndef LIST_H +#define LIST_H + +#include + +using std::cout; + +#include +#include "listnode.h" // ListNode class definition + +template< class NODETYPE > +class List { + +public: + List(); // constructor + ~List(); // destructor + void insertAtFront( const NODETYPE & ); + void insertAtBack( const NODETYPE & ); + bool removeFromFront( NODETYPE & ); + bool removeFromBack( NODETYPE & ); + bool isEmpty() const; + void print() const; + +private: + ListNode< NODETYPE > *firstPtr; // pointer to first node + ListNode< NODETYPE > *lastPtr; // pointer to last node + + // utility function to allocate new node + ListNode< NODETYPE > *getNewNode( const NODETYPE & ); + +}; // end class List + +// default constructor +template< class NODETYPE > +List< NODETYPE >::List() + : firstPtr( 0 ), + lastPtr( 0 ) +{ + // empty body + +} // end List constructor + +// destructor +template< class NODETYPE > +List< NODETYPE >::~List() +{ + if ( !isEmpty() ) { // List is not empty + cout << "Destroying nodes ...\n"; + + ListNode< NODETYPE > *currentPtr = firstPtr; + ListNode< NODETYPE > *tempPtr; + + while ( currentPtr != 0 ) { // delete remaining nodes + tempPtr = currentPtr; + cout << tempPtr->data << '\n'; + currentPtr = currentPtr->nextPtr; + delete tempPtr; + + } // end while + + } // end if + + cout << "All nodes destroyed\n\n"; + +} // end ~List destructor + +// insert node at front of list +template< class NODETYPE > +void List< NODETYPE >::insertAtFront( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + newPtr->nextPtr = firstPtr; + firstPtr = newPtr; + + } // end else + +} // end function insertAtFront + +// insert node at back of list +template< class NODETYPE > +void List< NODETYPE >::insertAtBack( const NODETYPE &value ) +{ + ListNode< NODETYPE > *newPtr = getNewNode( value ); + + if ( isEmpty() ) // List is empty + firstPtr = lastPtr = newPtr; + + else { // List is not empty + lastPtr->nextPtr = newPtr; + lastPtr = newPtr; + + } // end else + +} // end function insertAtBack + +// delete node from front of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromFront( NODETYPE &value ) +{ + if ( isEmpty() ) // List is empty + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = firstPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else + firstPtr = firstPtr->nextPtr; + + value = tempPtr->data; // data being removed + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function deleteFromFront + +// delete node from back of list +template< class NODETYPE > +bool List< NODETYPE >::removeFromBack( NODETYPE &value ) +{ + if ( isEmpty() ) + return false; // delete unsuccessful + + else { + ListNode< NODETYPE > *tempPtr = lastPtr; + + if ( firstPtr == lastPtr ) + firstPtr = lastPtr = 0; + else { + ListNode< NODETYPE > *currentPtr = firstPtr; + + // locate second-to-last element + while ( currentPtr->nextPtr != lastPtr ) + currentPtr = currentPtr->nextPtr; + + lastPtr = currentPtr; + currentPtr->nextPtr = 0; + + } // end else + + value = tempPtr->data; + delete tempPtr; + + return true; // delete successful + + } // end else + +} // end function deleteFromBack + +// is List empty? +template< class NODETYPE > +bool List< NODETYPE >::isEmpty() const +{ + return firstPtr == 0; + +} // end function isEmpty + +// return pointer to newly allocated node +template< class NODETYPE > +ListNode< NODETYPE > *List< NODETYPE >::getNewNode( + const NODETYPE &value ) +{ + return new ListNode< NODETYPE >( value ); + +} // end function getNewNode + +// display contents of List +template< class NODETYPE > +void List< NODETYPE >::print() const +{ + if ( isEmpty() ) { + cout << "The list is empty\n\n"; + return; + + } // end if + + ListNode< NODETYPE > *currentPtr = firstPtr; + + cout << "The list is: "; + + while ( currentPtr != 0 ) { + cout << currentPtr->data << ' '; + currentPtr = currentPtr->nextPtr; + + } // end while + + cout << "\n\n"; + +} // end function print + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/listnode.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/listnode.h new file mode 100644 index 0000000..7980786 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/listnode.h @@ -0,0 +1,56 @@ +// Fig. 15.3: listnode.h +// Template ListNode class definition. +#ifndef LISTNODE_H +#define LISTNODE_H + +// forward declaration of class List +template< class NODETYPE > class List; + +template< class NODETYPE > +class ListNode { + friend class List< NODETYPE >; // make List a friend + +public: + ListNode( const NODETYPE & ); // constructor + NODETYPE getData() const; // return data in node + +private: + NODETYPE data; // data + ListNode< NODETYPE > *nextPtr; // next node in list + +}; // end class ListNode + +// constructor +template< class NODETYPE > +ListNode< NODETYPE >::ListNode( const NODETYPE &info ) + : data( info ), + nextPtr( 0 ) +{ + // empty body + +} // end ListNode constructor + +// return copy of data in node +template< class NODETYPE > +NODETYPE ListNode< NODETYPE >::getData() const +{ + return data; + +} // end function getData + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queue.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queue.h new file mode 100644 index 0000000..84054c9 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queue.h @@ -0,0 +1,57 @@ +// Fig. 17.13: queue.h +// Template Queue class definition derived from class List. +#ifndef QUEUE_H +#define QUEUE_H + +#include "list.h" // List class definition + +template< class QUEUETYPE > +class Queue: private List< QUEUETYPE > { + +public: + // enqueue calls List function insertAtBack + void enqueue( const QUEUETYPE &data ) + { + insertAtBack( data ); + + } // end function enqueue + + // dequeue calls List function removeFromFront + bool dequeue( QUEUETYPE &data ) + { + return removeFromFront( data ); + + } // end function dequeue + + // isQueueEmpty calls List function isEmpty + bool isQueueEmpty() const + { + return isEmpty(); + + } // end function isQueueEmpty + + // printQueue calls List function print + void printQueue() const + { + print(); + + } // end function printQueue + +}; // end class Queue + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queuecomposition.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queuecomposition.h new file mode 100644 index 0000000..01c2ad4 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_13_14/queuecomposition.h @@ -0,0 +1,59 @@ +// Definition of Queue class composed of List object +#ifndef QUEUE_C +#define QUEUE_C + +#include "list.h" + +template< class QUEUETYPE > +class Queue { + +public: + // enqueue calls queueList object's insertAtBack function + void enqueue( const QUEUETYPE &data ) + { + queueList.insertAtBack( data ); + + } // end function enqueue + + // dequeue calls queueList object's removeFromFront function + bool dequeue( QUEUETYPE &data ) + { + return queueList.removeFromFront( data ); + + } // end function dequeue + + // isQueueEmpty calls queueList object's isEmpty function + bool isQueueEmpty() const + { + return queueList.isEmpty(); + + } // end function isQueueEmpty + + // printQueue calls queueList object's print function + void printQueue() const + { + queueList.print(); + + } // end function printQueue + +private: + List< QUEUETYPE > queueList; // composed List object + +}; // end class Queue + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Tree.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Tree.h new file mode 100644 index 0000000..d44276c --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Tree.h @@ -0,0 +1,159 @@ +// Fig. 17.18: tree.h +// Template Tree class definition. +#ifndef TREE_H +#define TREE_H + +#include + +using std::endl; + +#include +#include "treenode.h" + +template< class NODETYPE > +class Tree { + +public: + Tree(); + void insertNode( const NODETYPE & ); + void preOrderTraversal() const; + void inOrderTraversal() const; + void postOrderTraversal() const; + +private: + TreeNode< NODETYPE > *rootPtr; + + // utility functions + void insertNodeHelper( + TreeNode< NODETYPE > **, const NODETYPE & ); + void preOrderHelper( TreeNode< NODETYPE > * ) const; + void inOrderHelper( TreeNode< NODETYPE > * ) const; + void postOrderHelper( TreeNode< NODETYPE > * ) const; + +}; // end class Tree + +// constructor +template< class NODETYPE > +Tree< NODETYPE >::Tree() +{ + rootPtr = 0; + +} // end Tree constructor + +// insert node in Tree +template< class NODETYPE > +void Tree< NODETYPE >::insertNode( const NODETYPE &value ) +{ + insertNodeHelper( &rootPtr, value ); + +} // end function insertNode + +// utility function called by insertNode; receives a pointer +// to a pointer so that the function can modify pointer's value +template< class NODETYPE > +void Tree< NODETYPE >::insertNodeHelper( + TreeNode< NODETYPE > **ptr, const NODETYPE &value ) +{ + // subtree is empty; create new TreeNode containing value + if ( *ptr == 0 ) + *ptr = new TreeNode< NODETYPE >( value ); + + else // subtree is not empty + + // data to insert is less than data in current node + if ( value < ( *ptr )->data ) + insertNodeHelper( &( ( *ptr )->leftPtr ), value ); + + else + + // data to insert is greater than data in current node + if ( value > ( *ptr )->data ) + insertNodeHelper( &( ( *ptr )->rightPtr ), value ); + + else // duplicate data value ignored + cout << value << " dup" << endl; + +} // end function insertNodeHelper + +// begin preorder traversal of Tree +template< class NODETYPE > +void Tree< NODETYPE >::preOrderTraversal() const +{ + preOrderHelper( rootPtr ); + +} // end function preOrderTraversal + +// utility function to perform preorder traversal of Tree +template< class NODETYPE > +void Tree< NODETYPE >::preOrderHelper( + TreeNode< NODETYPE > *ptr ) const +{ + if ( ptr != 0 ) { + cout << ptr->data << ' '; // process node + preOrderHelper( ptr->leftPtr ); // go to left subtree + preOrderHelper( ptr->rightPtr ); // go to right subtree + + } // end if + +} // end function preOrderHelper + +// begin inorder traversal of Tree +template< class NODETYPE > +void Tree< NODETYPE >::inOrderTraversal() const +{ + inOrderHelper( rootPtr ); + +} // end function inOrderTraversal + +// utility function to perform inorder traversal of Tree +template< class NODETYPE > +void Tree< NODETYPE >::inOrderHelper( + TreeNode< NODETYPE > *ptr ) const +{ + if ( ptr != 0 ) { + inOrderHelper( ptr->leftPtr ); // go to left subtree + cout << ptr->data << ' '; // process node + inOrderHelper( ptr->rightPtr ); // go to right subtree + + } // end if + +} // end function inOrderHelper + +// begin postorder traversal of Tree +template< class NODETYPE > +void Tree< NODETYPE >::postOrderTraversal() const +{ + postOrderHelper( rootPtr ); + +} // end function postOrderTraversal + +// utility function to perform postorder traversal of Tree +template< class NODETYPE > +void Tree< NODETYPE >::postOrderHelper( + TreeNode< NODETYPE > *ptr ) const +{ + if ( ptr != 0 ) { + postOrderHelper( ptr->leftPtr ); // go to left subtree + postOrderHelper( ptr->rightPtr ); // go to right subtree + cout << ptr->data << ' '; // process node + + } // end if + +} // end function postOrderHelper + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Treenode.h b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Treenode.h new file mode 100644 index 0000000..a79cee9 --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/Treenode.h @@ -0,0 +1,54 @@ +// Fig. 17.17: treenode.h +// Template TreeNode class definition. +#ifndef TREENODE_H +#define TREENODE_H + +// forward declaration of class Tree +template< class NODETYPE > class Tree; + +template< class NODETYPE > +class TreeNode { + friend class Tree< NODETYPE >; + +public: + + // constructor + TreeNode( const NODETYPE &d ) + : leftPtr( 0 ), + data( d ), + rightPtr( 0 ) + { + // empty body + + } // end TreeNode constructor + + // return copy of node's data + NODETYPE getData() const + { + return data; + + } // end getData function + +private: + TreeNode< NODETYPE > *leftPtr; // pointer to left subtree + NODETYPE data; + TreeNode< NODETYPE > *rightPtr; // pointer to right subtree + +}; // end class TreeNode + +#endif + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file diff --git a/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/fig17_19.cpp b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/fig17_19.cpp new file mode 100644 index 0000000..3fb8def --- /dev/null +++ b/Bachelor/Prog2/Codebeispiele/6_ch17/fig17_17_19/fig17_19.cpp @@ -0,0 +1,76 @@ +// Fig. 17.19: fig17_19.cpp +// Tree class test program. +#include + +using std::cout; +using std::cin; +using std::fixed; + +#include +using std::setprecision; + +#include "tree.h" // Tree class definition + +int main() +{ + Tree< int > intTree; // create Tree of int values + int intValue; + + cout << "Enter 10 integer values:\n"; + + for( int i = 0; i < 10; i++ ) { + cin >> intValue; + intTree.insertNode( intValue ); + + } // end for + + cout << "\nPreorder traversal\n"; + intTree.preOrderTraversal(); + + cout << "\nInorder traversal\n"; + intTree.inOrderTraversal(); + + cout << "\nPostorder traversal\n"; + intTree.postOrderTraversal(); + + Tree< double > doubleTree; // create Tree of double values + double doubleValue; + + cout << fixed << setprecision( 1 ) + << "\n\n\nEnter 10 double values:\n"; + + for ( int j = 0; j < 10; j++ ) { + cin >> doubleValue; + doubleTree.insertNode( doubleValue ); + + } // end for + + cout << "\nPreorder traversal\n"; + doubleTree.preOrderTraversal(); + + cout << "\nInorder traversal\n"; + doubleTree.inOrderTraversal(); + + cout << "\nPostorder traversal\n"; + doubleTree.postOrderTraversal(); + + cout << endl; + + return 0; + +} // end main + +/************************************************************************** + * (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice * + * Hall. All Rights Reserved. * + * * + * DISCLAIMER: The authors and publisher of this book have used their * + * best efforts in preparing the book. These efforts include the * + * development, research, and testing of the theories and programs * + * to determine their effectiveness. The authors and publisher make * + * no warranty of any kind, expressed or implied, with regard to these * + * programs or to the documentation contained in these books. The authors * + * and publisher shall not be liable in any event for incidental or * + * consequential damages in connection with, or arising out of, the * + * furnishing, performance, or use of these programs. * + *************************************************************************/ \ No newline at end of file -- cgit v1.2.3