diff options
| author | Sven Eisenhauer <sven@sven-eisenhauer.net> | 2023-11-10 15:11:48 +0100 |
|---|---|---|
| committer | Sven Eisenhauer <sven@sven-eisenhauer.net> | 2023-11-10 15:11:48 +0100 |
| commit | 33613a85afc4b1481367fbe92a17ee59c240250b (patch) | |
| tree | 670b842326116b376b505ec2263878912fca97e2 /Bachelor/Prog2/SortedList | |
| download | Studium-33613a85afc4b1481367fbe92a17ee59c240250b.tar.gz Studium-33613a85afc4b1481367fbe92a17ee59c240250b.tar.bz2 | |
Diffstat (limited to 'Bachelor/Prog2/SortedList')
| -rw-r--r-- | Bachelor/Prog2/SortedList/Ref.cpp | 23 | ||||
| -rw-r--r-- | Bachelor/Prog2/SortedList/list.h | 266 | ||||
| -rw-r--r-- | Bachelor/Prog2/SortedList/listnode.h | 41 | ||||
| -rw-r--r-- | Bachelor/Prog2/SortedList/sortedList1.cpp | 80 |
4 files changed, 410 insertions, 0 deletions
diff --git a/Bachelor/Prog2/SortedList/Ref.cpp b/Bachelor/Prog2/SortedList/Ref.cpp new file mode 100644 index 0000000..49547a5 --- /dev/null +++ b/Bachelor/Prog2/SortedList/Ref.cpp @@ -0,0 +1,23 @@ +template< class NODETYPE >
+void Tree< NODETYPE >::insertNode( const NODETYPE &value )
+ { insertNodeHelper( rootPtr, value ); }
+
+// This function receives a reference to a pointer so the
+// pointer itself (not a copy of it!) can be modified.
+template< class NODETYPE >
+void Tree< NODETYPE >::insertNodeHelper(
+ TreeNode< NODETYPE >*& ptr, const NODETYPE &value )
+{
+ if ( ptr == 0 ) { // tree is empty
+ ptr = new TreeNode< NODETYPE >( value );
+ assert( ptr != 0 );
+ }
+ else // tree is not empty
+ if ( value < ptr->data )
+ insertNodeHelper( ptr->leftPtr, value );
+ else
+ if ( value > ptr->data )
+ insertNodeHelper( ptr->rightPtr, value );
+ else
+ cout << value << " dup" << endl;
+}
\ No newline at end of file diff --git a/Bachelor/Prog2/SortedList/list.h b/Bachelor/Prog2/SortedList/list.h new file mode 100644 index 0000000..f50f6db --- /dev/null +++ b/Bachelor/Prog2/SortedList/list.h @@ -0,0 +1,266 @@ +// Template List class definition
+
+#ifndef LIST_H
+#define LIST_H
+
+#include <iostream>
+using std::cout;
+
+#include <new>
+
+#include "listnode.h" // ListNode class definition
+
+template< class NODETYPE >
+class List {
+
+public:
+ List();
+ ~List();
+ void insertInOrder( const NODETYPE &value );
+ bool removeFromFront( NODETYPE & );
+ bool removeFromBack( NODETYPE & );
+ bool deleteNode( const NODETYPE &, NODETYPE & );
+ bool isEmpty() const;
+ void print() const;
+
+private:
+ void insertAtFront( const NODETYPE & );
+ void insertAtBack( const NODETYPE & );
+
+ ListNode< NODETYPE > *firstPtr; // pointer to first node
+ ListNode< NODETYPE > *lastPtr; // pointer to last node
+
+}; // 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 = new ListNode< NODETYPE >( 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 = new ListNode< NODETYPE >( 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
+
+
+// insert node in sorted order
+template< class NODETYPE >
+void List< NODETYPE >::insertInOrder( const NODETYPE &value )
+{
+ if ( isEmpty() ) {
+ ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );
+ firstPtr = lastPtr = newPtr;
+ }
+ else {
+ if( firstPtr->data >= value)
+ insertAtFront( value );
+ else if( lastPtr->data < value)
+ insertAtBack( value );
+ else {
+ ListNode< NODETYPE > *currentPtr = firstPtr->nextPtr,
+ *previousPtr = firstPtr,
+ *newPtr = new ListNode< NODETYPE >( value );
+
+ // locate element before new node gets inserted
+ while ( currentPtr != lastPtr && currentPtr->data < value ) {
+ previousPtr = currentPtr;
+ currentPtr = currentPtr->nextPtr;
+ }
+
+ previousPtr->nextPtr = newPtr;
+ newPtr->nextPtr = currentPtr;
+
+ } // end else
+
+ } // end else
+
+} // end function insertInOrder
+
+// delete a node from anywhere in the list
+template< class NODETYPE >
+bool List< NODETYPE >::deleteNode( const NODETYPE &value, NODETYPE &deletedVal )
+{
+ if ( isEmpty() )
+ return false; // delete unsuccessful
+ else {
+ if ( firstPtr->data == value ) {
+ removeFromFront( deletedVal );
+ return true; // delete successful
+ }
+ else if ( lastPtr->data == value ) {
+ removeFromBack( deletedVal );
+ return true; // delete successful
+ }
+ else {
+ ListNode< NODETYPE > *currentPtr = firstPtr->nextPtr,
+ *previousPtr = firstPtr;
+
+ while ( currentPtr != lastPtr && currentPtr->data < value ) {
+ previousPtr = currentPtr;
+ currentPtr = currentPtr->nextPtr;
+ }
+
+ if ( currentPtr->data == value ) {
+ ListNode< NODETYPE > *tempPtr = currentPtr;
+ deletedVal = currentPtr->data;
+ previousPtr = currentPtr->nextPtr;
+ delete tempPtr;
+ return true; // delete successful
+ }
+ else
+ return false; // delete unsuccessful
+
+ } // end else
+
+ } // end else
+
+} // end function deleteNode
+
+// is List empty?
+template< class NODETYPE >
+bool List< NODETYPE >::isEmpty() const
+{
+ return firstPtr == 0;
+
+} // end function isEmpty
+
+// 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
\ No newline at end of file diff --git a/Bachelor/Prog2/SortedList/listnode.h b/Bachelor/Prog2/SortedList/listnode.h new file mode 100644 index 0000000..fd51ef4 --- /dev/null +++ b/Bachelor/Prog2/SortedList/listnode.h @@ -0,0 +1,41 @@ +// 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
\ No newline at end of file diff --git a/Bachelor/Prog2/SortedList/sortedList1.cpp b/Bachelor/Prog2/SortedList/sortedList1.cpp new file mode 100644 index 0000000..f0b548b --- /dev/null +++ b/Bachelor/Prog2/SortedList/sortedList1.cpp @@ -0,0 +1,80 @@ +// List class test program for sorted list
+
+#include <iostream>
+using std::cin;
+using std::endl;
+
+#include <string>
+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.insertInOrder( value );
+ listObject.print();
+ break;
+
+ case 2:
+ if ( listObject.removeFromFront( value ) )
+ cout << value << " removed from list\n";
+
+ listObject.print();
+ break;
+
+ case 3:
+ 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 in sorted order into the list\n"
+ << " 2 to delete from beginning of list\n"
+ << " 3 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
\ No newline at end of file |