Reverse a char array

[thisisdarshan]

How to reverse a char array with single traversal in place and in memory?

My solution program:

void reverse_string(char str[])
{
    char c;
    char *p, *q;

    p = str;
    if (!p)
        return;

    q = p + 1;
    if (*q == '\0')
        return;

    c = *p;
    reverse_string(q);

    while (*q != '\0') {
        *p = *q;
        p++;
        q++;
    }
    *p = c;

    return;
}

Can anyone give me a better solution to this question?

[jsmith]

std::reverse( str, &str[ strlen( str ) ] );

or

if( strlen( str ) > 0 ) {
   char* first = &str[ 0 ];
   char* last = &str[ strlen( str ) - 1 ];
   while( first < last ) {
       char tmp = *first;
       *first = *last;
       *last = tmp;
      ++first;
      --last;
   }
}

[thisisdarshan]

I think that function "strlen" internally traverse through string once. I am looking for some solution which requires single traversal.

[Duthomhas]

Ooh ooh! Code! Looks fun!

#include <iostream>
using namespace std;

char* strrev( char* s )
  {
  char  c;
  char* s0 = s - 1;
  char* s1 = s;

  /* Find the end of the string */
  while (*s1) ++s1;

  /* Reverse it */
  while (s1-- > ++s0)
    {
    c   = *s0;
    *s0 = *s1;
    *s1 =  c;
    }

  return s;
  }

int main()
  {
  char message[] = "Hello world!";

  cout << "message = " << message << endl;
  cout << "egassem = " << strrev( message ) << endl;

  return 0;
  }

:-)

[edit]

I am looking for some solution which requires single traversal.

Impossible unless you know a priori the length of the string to reverse.

[thisisdarshan]

This code will traverse the array more than once. I do not think the solution is impossible. I was thinking the use of recursion and let the compiler use stack internally. This will also keep the solution in memory. Can any one try this approach?

[jsmith]

You can do it that way.

So is this a homework assignment or a challenge or what, because I'm pretty sure either of the above approaches will be just as fast if not faster.

[thisisdarshan]

This is just a thought. I am trying to clear some concepts on recursive programming. May be the solution with this approach will help me a bit.

[Duthomhas]

No offense, but whether or not you think it is impossible doesn't change the reality that it is "Impossible unless you know a priori the length of the string to reverse." Using recursion/stacks/whatever doesn't change the problem -- it only rearranges it. No amount of rearranging will enable you to escape first traversing the string to find its length and second reversing it. The reason is simple: reversing the string is predicated on knowing its length.

[helios]

There is one solution that can do this while traversing the array only once, but it only works with arrays shorter than a limit and is very wasteful memory-wise:
1. Allocate a sufficiently large string. Keep a pointer to the beginning for deallocation.
2. Set a pointer to the tail and zero the element. This is the terminator.
3. For every character in the input string, decrement the pointer and copy the character to the dereferenced pointer.
4. Return the head pointer and the string pointer.

char *reverse(const char *input,char *&head){
	head=new char[MAX_STRING];
	char *ret=head+MAX_STRING-1;
	*ret=0;
	while (*input)
		*--ret=*input++;
	return ret;
}

[Duthomhas]

Nice! Except it isn't in-place.

[helios]

Oh, I didn't see the "in-place" part.
Yeah, in that case it requires at least two passes or knowing the length.