e.g. input = "abcdef", output = "fedcba"
Idea 1:(iterative version)
observe...
0 1 2 3 4 5
a b c d e f
exchange the first character with the list character
0 1 2 3 4 5
f b c d e a
exchange the second with second to the last
0 1 2 3 4 5
f e c d b a
go on and on, until this two target meet
main concept:
- finding the string's end
- a pointer goes forward starting from beginning and another goes backward starting from the other end
- keep going and exchanging the characters until they meet
C++ code:
#include <iostream>
using namespace std;
void reverse(char *str){
// find the end of str
char *end = str;
while( *end != '\0' )
end++;
end--;// go back to the non-null character
while( str < end ) // not come across each other yet
{
char temp = *str;
*str++ = *end;
*end-- = temp;
}
}
int main( ){
char s[] = "Hello, my friend!";
reverse(s);
cout << s << endl;
return 0;
}
|
Idea 2:(recursive version)
observe carefully....
0 1 2 3 4 5
a b c d e f
exchange the first character with the list character
0 1 2 3 4 5
f b c d e a
sub-array with element 1 to 4 forms the input of a sub-problem
0 1 2 3 4 5
f b c d e a
(yellow part is a sub-problem!)
what's the base case? when the sub-array with element i to j, such that i > j
main concept:
- exchange front element with back element
- excluding front and back element, recurse on the remaining elements
- down to the base case
C++ code
#include <iostream>
using namespace std;
void reverser(char *str, int begin, int end){
// base case
if( begin >= end )
return;
else{ // recursive case
// exchange first char and last char
char temp = *(str + begin);
*(str + begin) = *(str + end);
*(str + end) = temp;
// recurse
reverser(str, ++begin, --end);
}
}
void reverse(char *str){
int strlen = 0;
while(str[strlen])
strlen++;
reverser( str, 0, strlen-1 );
}
int main( ){
char s[] = "Hello, my friend!";
reverse(s);
cout << s << endl;
return 0;
}
|
line 23: initial call
line 15: recursive call ; the main concept 2
line 10~12: the main concept 1
沒有留言:
張貼留言