Reverse a char array

This is a discussion on Reverse a char array within the C Programming forums, part of the General Programming Boards category; How to reverse a char array with single traversal in place and in memory? Hint: Use of recursion...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Location
    New York, NY
    Posts
    7

    Post Reverse a char array

    How to reverse a char array with single traversal in place and in memory?
    Hint: Use of recursion

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Hint: Do your own homework. Post code and specific questions if you get stuck.

  3. #3
    Registered User
    Join Date
    Oct 2009
    Location
    New York, NY
    Posts
    7

    Post solution take

    My solution program:

    Code:
    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;
    }
    I am looking for the best solution possible for the question. I was thinking the use of recursion and let compiler use the stack internally. This will also make solution in memory. Can anyone try this approach?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    If the char array is of a known length then you don't need recursion for it as it can be solved with a trivial loop over half the items performing swaps as you go. That would make the hint stupid, as you don't need (or bennefit from) recursion.

    If however the length is unknown then I'm going to suggest that this technically isn't possible as you first traverse the array in one direction looking for the end, and then you perform a second traversal to perform the reversing. Whether there is recursion involved or not, it's still two passes, no matter how you look at it. You just cant call a pass over the array one direction then the other, a single traversal IMHO.

    I therefore declare the question to be faulty.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I prefer using two pointers or indexes, and a single return line, when startIndex >= endIndex. With every recursion, the values of the array that startIndex and endIndex point to, (or reference), are swapped, and startIndex incremented Also, endIndex is decremented with every recursive call.

    Then you are reversing the string, in one pass, and the code is crystal clear. Try that.
    Code:
    //before this function is called, startIndex and endIndex refer to the first and last char's
    void reverseString(char *string, startIndex, endIndex) {
      //if the index variables have met or crossed, then return, here
    
      reverseString(string, startIndex+1, endIndex-1);
    }

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    size_t rev( char s[], size_t x )
    {
        if( s && s[x] )
        {
            size_t y = rev( s, x+1 );
            if( x < y / 2 )
            {
                char t = s[x];
                s[x] = s[y-1-x];
                s[y-1-x] = t;
            }
            x = y;
        }
        return x;
    }
    ...
    rev( myarray, 0 );
    In place, one pass, unknown size.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 11-17-2008, 11:36 AM
  2. C++ ini file reader problems
    By guitarist809 in forum C++ Programming
    Replies: 7
    Last Post: 09-04-2008, 06:02 AM
  3. Sorting Linked Lists
    By DKING89 in forum C Programming
    Replies: 6
    Last Post: 04-09-2008, 07:36 AM
  4. Creating 2D arrays on heap
    By sundeeptuteja in forum C++ Programming
    Replies: 6
    Last Post: 08-16-2002, 11:44 AM
  5. Strings are V important...
    By NANO in forum C++ Programming
    Replies: 15
    Last Post: 04-14-2002, 11:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21