cannot understand strrev implementation

T

tuchka

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.

:(
 
R

Robert Stankowic

tuchka said:
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
 
R

Richard Heathfield

tuchka said:
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.
 
R

Robert Stankowic

Richard Heathfield said:
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
 
I

Irrwahn Grausewitz

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
 
T

tuchka

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.
:)
 
L

Lew Pitcher

tuchka said:
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top