cannot understand strrev implementation

Discussion in 'C Programming' started by tuchka, Nov 9, 2003.

  1. tuchka

    tuchka Guest

    Hi, guys!
    I am very new here and just started to learn C. I have previous java
    exp. however.
    I'm abs. stuck on pointers and i'm unable comprehend algorithm of
    simple program that reverses chars in string no matter how long I'm
    staring at it.

    This is the method(I printed out some lines for better
    understanding(by me)):

    char *strrev(char *string) {
    char *original = string;
    char *forward = string;
    char temp;
    printf("\nInside strrev method:");

    printf("\n*string %c", *string);
    printf("\n*original %c", *original);
    printf("\n*forward %c", *forward);

    printf("\nstring %s", string);
    printf("\noriginal %s", original);
    printf("\nforward %s\n", forward);

    printf("\nFirst while:");

    while(*string){
    printf("\n*string %c ", *string);
    printf("\nstring %s ", string);
    string++;
    }
    printf("\nSecond while:");
    while(forward<string) {
    printf("\n*string %c", *string);
    printf("\n*original %c", *original);
    printf("\n*forward %c", *forward);

    printf("\nstring %s", string);
    printf("\noriginal %s", original);
    printf("\nforward %s\n\n", forward);

    temp=*(--string);
    *string=*forward;
    *forward++=temp;
    }
    return (original);
    }


    Results:

    //////////////
    First while:
    *string h
    string hello
    *string e
    string ello
    *string l
    string llo
    *string l
    string lo
    *string o
    string o
    Second while:
    *string
    *original h
    *forward h
    string
    original hello
    forward hello

    *string h
    *original o
    *forward e
    string h
    original oellh
    forward ellh

    *string e
    *original o
    *forward l
    string eh
    original olleh
    forward leh

    Reverse hello is olleh
    ////////////////////////////

    I CANNOT UNDERSTAND IT. PLEASE,PLEASE, KINDLY, IF YOU HAVE TIME, WHAT
    IS GOING ON????
    Why i need first loop?
    Where 'string' dissapeared?
    how come the original is being modified?
    Maybe it is very abbreviated version?maybe there is more detailed
    version?
    i'm dumb.

    :(
    tuchka, Nov 9, 2003
    #1
    1. Advertising

  2. "tuchka" <> schrieb im Newsbeitrag
    news:...
    > Hi, guys!
    > I am very new here and just started to learn C. I have previous java
    > exp. however.
    > I'm abs. stuck on pointers and i'm unable comprehend algorithm of
    > simple program that reverses chars in string no matter how long I'm
    > staring at it.


    OK, here is an attempt to explain how it works

    Be aware, that given
    char *something = string;
    ++something; yields the value of something + 1 and increments something,
    while
    something++; yields the original value of something and increments something

    --something; yields the value of something - 1 and decrements something,
    while
    something--; yields the original value of something and decrements something

    #include <stdlib.h>
    #include <stdio.h>

    char *my_strrev(char *string)
    {
    char *original = string;
    char *forward = string;
    char temp;

    /*string points to the first character ('h' in our example)*/
    while(*string)/* *string yields the content of the location where string
    points*/
    {
    string++;
    /*this makes string point to the next character,
    and the loop is repeated until the terminating '\0' is found
    ^ shows where string points during the loop
    'h' 'e' 'l' 'l' 'o' '\0'
    ^
    'h' 'e' 'l' 'l' 'o' '\0'
    ^
    'h' 'e' 'l' 'l' 'o' '\0'
    ^
    'h' 'e' 'l' 'l' 'o' '\0'
    ^
    'h' 'e' 'l' 'l' 'o' '\0'
    ^
    'h' 'e' 'l' 'l' 'o' '\0'
    ^
    *string is now 0,
    which terminates the loop
    */
    }
    /*string now points to the terminating '\0'
    (immidiately after the 'o' in "hello"), and forward still points to
    the beginning of the string (the 'h')*/
    while(forward < string)/*this loop decrements string and increments
    forward
    until the pointers meet in the middle of the
    original string*/
    {
    /*now our pointers point as shown below
    'h' 'e' 'l' 'l' 'o' '\0'*/
    ^ ^
    temp=*(--string);
    *string=*forward;
    *forward++=temp;
    /*the statements above swap the contents of where (string - 1)
    and forward point. the result, step by step is:
    pass 1
    --string points to the 'o' and decrements string:
    'h' 'e' 'l' 'l' 'o' '\0'
    ^ ^
    *(--string) is 'o', *forward is 'h'
    temp becomes 'o', *string becomes 'h', *forward becomes 'o'
    string is now "oellh"
    pass 2
    'o' 'e' 'l' 'l' 'h' '\0'
    ^ ^
    *(--string) is 'l', *forward is 'e'
    temp becomes 'l', *string becomes 'e', *forward becomes 'l'
    string is now "olleh"
    now we have
    'o' 'l' 'l' 'e' 'h' '\0'
    ^^
    and string as well as forward point to the same location - we are
    done*/
    }
    return (original);
    }

    int main(void)
    {
    char string[] = "hello";

    puts(my_strrev(string));
    return EXIT_SUCCESS;
    }

    HTH
    Robert
    Robert Stankowic, Nov 9, 2003
    #2
    1. Advertising

  3. tuchka wrote:

    > Hi, guys!
    > I am very new here and just started to learn C. I have previous java
    > exp. however.
    > I'm abs. stuck on pointers and i'm unable comprehend algorithm of
    > simple program that reverses chars in string no matter how long I'm
    > staring at it.
    >
    > This is the method(I printed out some lines for better
    > understanding(by me)):


    I've taken them out, to reduce clutter in this article (that doesn't mean
    they're a bad idea, if they help you to understand, but in this case they
    may have been misleading you). I've also changed the layout slightly, to
    emphasise the loops.

    > char *strrev(char *string) {


    Choose a better name. This one invades implementation namespace.

    > char *original = string;
    > char *forward = string;
    > char temp;
    >
    > while(*string)
    > {
    > string++;
    > }


    This loop finds the last character in the string.

    > while(forward<string)
    > {
    > temp=*(--string);
    > *string=*forward;
    > *forward++=temp;
    > }


    This loop swaps the contents of the bytes pointed to by the 'forward' and
    'string' pointers, and then moves them towards each other, stopping when
    they meet.

    > return (original);
    > }
    >
    > I CANNOT UNDERSTAND IT. PLEASE,PLEASE, KINDLY, IF YOU HAVE TIME, WHAT
    > IS GOING ON????
    > Why i need first loop?


    To move one of the pointers to the end of the string.

    > Where 'string' dissapeared?


    It was never there. The original string was "hello", and your debugging
    statements were confusing you.

    > how come the original is being modified?


    Cool, huh? That's what you get when you pass a pointer into a function - the
    possibility that the original object will be changed. It is of course
    possible to write a version that leaves the original alone, but if that's
    what you want then you must somehow provide storage for the reversed copy,
    either by passing it in, or through a static buffer (ech!), or through
    dynamic memory allocation, or in some other fiendishly ghastly way.

    > Maybe it is very abbreviated version?maybe there is more detailed
    > version?


    Here's a more detailed illustration of what's happening.

    Take one suit, and the joker, from a pack of playing cards. You will need an
    assistant or a good memory. Lay them out like this:

    A 2 3 4 5 6 7 8 9 T J Q K JOKER


    At the beginning, point at A, with both the index finger of your left hand
    AND the index finger of your right hand.

    First loop:

    Until your right finger points at the joker
    {
    keep moving your right hand to the right
    }

    Second loop:

    Whilst your left hand is to the left of your right hand:
    {
    Move your right hand to point to the card just to the left
    of the one it's pointing to right now.
    Ask your assistant to swap the cards that you are pointing to.
    Move your left hand to point to the card just to the right
    of the one it's pointing to right now.
    }

    Do this with real playing cards, and you will understand what the function
    is doing and how it is doing it. The JOKER is the "null terminating
    character", and is (correctly) not moved by the operation.

    --
    Richard Heathfield :
    "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
    C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
    K&R answers, C books, etc: http://users.powernet.co.uk/eton
    Richard Heathfield, Nov 9, 2003
    #3
  4. "Richard Heathfield" <> schrieb im Newsbeitrag
    news:bokp9v$ef8$...
    > tuchka wrote:

    [....]

    > Here's a more detailed illustration of what's happening.
    >
    > Take one suit, and the joker, from a pack of playing cards. You will need

    an
    > assistant or a good memory. Lay them out like this:

    [great explanation snipped]

    Richard, that's great! much better than my attempt :)
    Robert
    Robert Stankowic, Nov 9, 2003
    #4
  5. (tuchka) wrote:

    > I'm abs. stuck on pointers and i'm unable comprehend algorithm of
    > simple program that reverses chars in string no matter how long I'm
    > staring at it.

    <snip>

    Others have already explained the algorithm itself, but in the
    code shown the variable names are still confusing and the 'packed'
    operations make it hard to see what happens in which order. Maybe
    looking at the rewritten code below will help a bit:

    #include <stdio.h>

    char *Strrev( char *string )
    {
    char *backward = string;
    char *forward = string;
    char temp;

    /*
    ** Set 'backward' to the null byte
    ** terminating the string:
    */
    while ( *backward )
    backward++;

    /*
    ** Move 'forward' towards end of string
    ** and 'backward' towards start of string
    ** until 'forward' and 'backward' meet,
    ** swapping characters as we go:
    */
    while ( forward < backward )
    {
    --backward;
    temp = *backward;
    *backward = *forward;
    *forward = temp;
    ++forward;
    }
    return string;
    }

    int main( void )
    {
    char s[] = "Reverse me!";
    puts( Strrev( s ) );
    return 0;
    }

    HTH
    Regards
    --
    Irrwahn
    ()
    Irrwahn Grausewitz, Nov 9, 2003
    #5
  6. tuchka

    tuchka Guest

    Thank you guys! Your explanations were great. Meanwhile i also read
    chapter from "Practical C" taken from internet and hammered those
    concepts into my brain. Now i am going to look at it until i
    understand completely, but already after cursory glance at your
    articles understanding is coming to me slowly.
    :)
    tuchka, Nov 9, 2003
    #6
  7. tuchka

    Lew Pitcher Guest

    tuchka wrote:
    > Hi, guys!
    > I am very new here and just started to learn C. I have previous java
    > exp. however.
    > I'm abs. stuck on pointers and i'm unable comprehend algorithm of
    > simple program that reverses chars in string no matter how long I'm
    > staring at it.
    >
    > This is the method(I printed out some lines for better
    > understanding(by me)):
    >
    > char *strrev(char *string) {
    > char *original = string;
    > char *forward = string;
    > char temp;
    > printf("\nInside strrev method:");
    >
    > printf("\n*string %c", *string);
    > printf("\n*original %c", *original);
    > printf("\n*forward %c", *forward);
    >
    > printf("\nstring %s", string);
    > printf("\noriginal %s", original);
    > printf("\nforward %s\n", forward);
    >
    > printf("\nFirst while:");
    >
    > while(*string){
    > printf("\n*string %c ", *string);
    > printf("\nstring %s ", string);
    > string++;
    > }
    > printf("\nSecond while:");
    > while(forward<string) {
    > printf("\n*string %c", *string);
    > printf("\n*original %c", *original);
    > printf("\n*forward %c", *forward);
    >
    > printf("\nstring %s", string);
    > printf("\noriginal %s", original);
    > printf("\nforward %s\n\n", forward);
    >
    > temp=*(--string);
    > *string=*forward;
    > *forward++=temp;
    > }
    > return (original);
    > }
    >
    >
    > Results:
    >
    > //////////////
    > First while:
    > *string h
    > string hello
    > *string e
    > string ello
    > *string l
    > string llo
    > *string l
    > string lo
    > *string o
    > string o
    > Second while:
    > *string
    > *original h
    > *forward h
    > string
    > original hello
    > forward hello
    >
    > *string h
    > *original o
    > *forward e
    > string h
    > original oellh
    > forward ellh
    >
    > *string e
    > *original o
    > *forward l
    > string eh
    > original olleh
    > forward leh
    >
    > Reverse hello is olleh
    > ////////////////////////////
    >
    > I CANNOT UNDERSTAND IT. PLEASE,PLEASE, KINDLY, IF YOU HAVE TIME, WHAT
    > IS GOING ON????
    > Why i need first loop?


    You need the first loop to find the length of the string. In C, a string is
    not a primative type; it is an array of characters, terminated by a
    character of \0. This means that the string "hello" is actually
    char String[6] = { 'h', 'e', 'l', 'l', 'o', '\0'};
    The first loop looks through the array for the '\0' character. This way it
    knows where the end of the string is.

    > Where 'string' dissapeared?


    It didn't disappear; it's contents were replaced by the reverse of it's
    contents.

    You started with an array that contained
    's', 't', 'r', 'i', 'n', 'g', '\0''
    and ended with the same array now containing
    'g', 'n', 'i', 'r', 't', 's', '\0'

    > how come the original is being modified?


    You modified it in the second loop.

    Since pointers seem to be confusing you, let's deal with this as operations
    on arrays.

    You started by giving your strrev() function the array
    string[0] = 's'
    string[1] = 't'
    string[2] = 'r'
    string[3] = 'i'
    string[4] = 'n'
    string[5] = 'g'
    string[6] = '\0'

    You looped through this array, looking for the '\0' character. When you
    found it, you noted it's position

    You then started going through the array with two index variables: forward,
    which was set to 0, and string, which was set to 6
    Each iteration of the loop
    copied the character at the [forward] position of the array out to a safe
    place,
    copied the character at the [string] position of the array to the
    [forward] position,
    copied the character out of the safe place to the [string] position
    moved forward one entry forward
    moved string one entry backward
    and tested if forward had passed string

    The first time through, you exchanged the 's' and 'g' characters, so the
    array looked like
    string[0] = 'g'
    string[1] = 't'
    string[2] = 'r'
    string[3] = 'i'
    string[4] = 'n'
    string[5] = 's'
    string[6] = '\0'

    The second time through, you exchanged the 't' and 'n' characters, making
    the array look like
    string[0] = 'g'
    string[1] = 'n'
    string[2] = 'r'
    string[3] = 'i'
    string[4] = 't'
    string[5] = 's'
    string[6] = '\0'

    The third time through, you exchanged the 'r' and 'i' characters, making the
    array look like
    string[0] = 'g'
    string[1] = 'n'
    string[2] = 'i'
    string[3] = 'r'
    string[4] = 't'
    string[5] = 's'
    string[6] = '\0'

    With me so far?

    Now, think of pointers as fast ways to access arrays.

    Given
    char String[6] = { 'h', 'e', 'l', 'l', 'o', '\0'};

    *(String+0)
    is just another way to say
    String[0],

    *(String+1)
    is just another way to say
    String[1], and

    *(String+index)
    is just another way to say
    String[index]

    So, the code fragment

    while (*string) ++string;

    does a similar job to

    int index;
    while (string[index]) ++index;

    and the later code fragment

    while (forward < string)
    {
    temp=*(--string);
    *string=*forward;
    *forward++=temp;
    }

    does a similar job to

    forward = 0;
    while (forward < index)
    {
    temp = string[--index];
    string[index] = string[forward];
    string[forward++] = temp;
    }


    > Maybe it is very abbreviated version?maybe there is more detailed
    > version?
    > i'm dumb.
    >
    > :(



    --
    Lew Pitcher

    Master Codewright and JOAT-in-training
    Registered Linux User #112576 (http://counter.li.org/)
    Slackware - Because I know what I'm doing.
    Lew Pitcher, Nov 9, 2003
    #7
  8. tuchka

    tuchka Guest

    Thank you Irrwahn,
    your program rewriting was also very helpful.
    :)
    tuchka, Nov 10, 2003
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shawn
    Replies:
    1
    Views:
    305
    Mike Schilling
    Sep 28, 2006
  2. rashmi

    compiling errors cannot understand

    rashmi, Sep 9, 2005, in forum: C Programming
    Replies:
    5
    Views:
    303
    Irrwahn Grausewitz
    Sep 9, 2005
  3. rashmi

    compiling errors cannot understand

    rashmi, Sep 20, 2005, in forum: C Programming
    Replies:
    1
    Views:
    327
    SM Ryan
    Sep 20, 2005
  4. Gladiator
    Replies:
    17
    Views:
    455
    Keith Thompson
    Jan 5, 2006
  5. L.W.C. Nirosh

    I cannot understand this???

    L.W.C. Nirosh, Apr 11, 2007, in forum: ASP .Net
    Replies:
    5
    Views:
    384
    Bryce
    Apr 11, 2007
Loading...

Share This Page