Mercurial > Algorithms__Sedgewick
changeset 10:8af1a61be7c1
Added some of the exercises from chapter 1
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Mon, 08 Jun 2015 17:52:54 -0500 |
parents | 0f99a5ae6cd4 |
children | 846aeab17939 |
files | algs4-c++/src/Stack.cpp algs4-c++/src/Stack.hpp |
diffstat | 2 files changed, 112 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- a/algs4-c++/src/Stack.cpp Fri May 29 21:34:18 2015 -0500 1.2 +++ b/algs4-c++/src/Stack.cpp Mon Jun 08 17:52:54 2015 -0500 1.3 @@ -106,6 +106,86 @@ 1.4 return this->curr != other.curr; 1.5 } 1.6 1.7 +//////////////////////////////////////////////////////////////////////////////// 1.8 + 1.9 + 1.10 +#ifdef EXERCISES 1.11 + 1.12 +// 1.3.19 1.13 +// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 1.14 +template <typename T> 1.15 +T Stack<T>::delete_bottom( void ) { 1.16 + Node *prev, *curr; 1.17 + T item; 1.18 + 1.19 + prev = nullptr; 1.20 + curr = list; 1.21 + if ( curr ) { 1.22 + while ( curr->next ) { 1.23 + prev = curr; 1.24 + curr = curr->next; 1.25 + } 1.26 + 1.27 + item = curr->item; 1.28 + delete curr; 1.29 + if ( prev ) 1.30 + prev->next = nullptr; 1.31 + else 1.32 + list = nullptr; 1.33 + 1.34 + N--; 1.35 + } 1.36 + 1.37 + return item; 1.38 + } 1.39 + 1.40 + 1.41 +// 1.3.20 1.42 +// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 1.43 +template <typename T> 1.44 +T Stack<T>::remove( size_t k ) { 1.45 + Node *prev, *curr; 1.46 + size_t i=0; 1.47 + T item; 1.48 + 1.49 + prev = nullptr; 1.50 + curr = list; 1.51 + while ( curr && (i < k) ) { 1.52 + prev = curr; 1.53 + curr = curr->next; 1.54 + ++i; 1.55 + } 1.56 + 1.57 + if ( curr &&( i == k) ) { 1.58 + item = curr->item; 1.59 + if ( prev ) 1.60 + prev->next = curr->next; 1.61 + else 1.62 + list = curr->next;; 1.63 + delete curr; 1.64 + N--; 1.65 + } 1.66 + 1.67 + return item; 1.68 + } 1.69 + 1.70 +// 1.3.21 1.71 +// Returns true if the specified key is in the stack. 1.72 +template <typename T> 1.73 +bool Stack<T>::find( T key ) { 1.74 + Node *curr = list; 1.75 + 1.76 + while ( curr ) { 1.77 + if ( curr->item == key ) 1.78 + return true; 1.79 + curr = curr->next; 1.80 + } 1.81 + 1.82 + return false; 1.83 + } 1.84 + 1.85 +#endif 1.86 + 1.87 1.88 //////////////////////////////////////////////////////////////////////////////// 1.89 1.90 @@ -130,6 +210,30 @@ 1.91 std::cout << *iter << std::endl; 1.92 } 1.93 1.94 +#ifdef EXERCISES 1.95 + std::cout << "Looking for 3: " << ( stack.find( 3 ) ? "found" : "not found" ) << std::endl; 1.96 + std::cout << "Looking for 9999: " << ( stack.find( 9999 ) ? "found" : "not found" ) << std::endl; 1.97 + 1.98 + std::cout << "Removing bottom entry: "; 1.99 + i = stack.delete_bottom(); 1.100 + std::cout << i << std::endl; 1.101 + std::cout << "Stack has " << stack.size() << " entries." << std::endl; 1.102 + 1.103 + for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) { 1.104 + std::cout << *iter << std::endl; 1.105 + } 1.106 + 1.107 + std::cout << "Removing entry 2: "; 1.108 + i = stack.remove( 2 ); 1.109 + std::cout << i << std::endl; 1.110 + std::cout << "Stack has " << stack.size() << " entries." << std::endl; 1.111 + 1.112 + for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) { 1.113 + std::cout << *iter << std::endl; 1.114 + } 1.115 + 1.116 +#endif 1.117 + 1.118 std::cout << "Popping entries..." << std::endl; 1.119 1.120 while ( ! stack.is_empty() ) {
2.1 --- a/algs4-c++/src/Stack.hpp Fri May 29 21:34:18 2015 -0500 2.2 +++ b/algs4-c++/src/Stack.hpp Mon Jun 08 17:52:54 2015 -0500 2.3 @@ -54,6 +54,14 @@ 2.4 iterator begin( void ); 2.5 iterator end( void ); 2.6 2.7 +#ifdef EXERCISES 2.8 + 2.9 + T delete_bottom( void ); // 1.3.19 2.10 + T remove( size_t k ); // 1.3.20 2.11 + bool find( T key ); // 1.3.21 2.12 + 2.13 +#endif 2.14 + 2.15 private: 2.16 2.17 size_t N;