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 --- Bachelor/Prog2/SortedList/Ref.cpp | 23 +++ Bachelor/Prog2/SortedList/list.h | 266 ++++++++++++++++++++++++++++++ Bachelor/Prog2/SortedList/listnode.h | 41 +++++ Bachelor/Prog2/SortedList/sortedList1.cpp | 80 +++++++++ 4 files changed, 410 insertions(+) create mode 100644 Bachelor/Prog2/SortedList/Ref.cpp create mode 100644 Bachelor/Prog2/SortedList/list.h create mode 100644 Bachelor/Prog2/SortedList/listnode.h create mode 100644 Bachelor/Prog2/SortedList/sortedList1.cpp (limited to 'Bachelor/Prog2/SortedList') 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 +using std::cout; + +#include + +#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 +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.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 -- cgit v1.2.3