Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > cannot understand strrev implementation

Reply
Thread Tools

cannot understand strrev implementation

 
 
tuchka
Guest
Posts: n/a
 
      11-09-2003
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.


 
Reply With Quote
 
 
 
 
Robert Stankowic
Guest
Posts: n/a
 
      11-09-2003

"tuchka" <(E-Mail Removed)> schrieb im Newsbeitrag
news:(E-Mail Removed) om...
> 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


 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      11-09-2003
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 : http://www.velocityreviews.com/forums/(E-Mail Removed)
"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
 
Reply With Quote
 
Robert Stankowic
Guest
Posts: n/a
 
      11-09-2003

"Richard Heathfield" <(E-Mail Removed)> schrieb im Newsbeitrag
news:bokp9v$ef8$(E-Mail Removed)...
> 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


 
Reply With Quote
 
Irrwahn Grausewitz
Guest
Posts: n/a
 
      11-09-2003
(E-Mail Removed) (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
((E-Mail Removed))
 
Reply With Quote
 
tuchka
Guest
Posts: n/a
 
      11-09-2003
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.

 
Reply With Quote
 
Lew Pitcher
Guest
Posts: n/a
 
      11-09-2003
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.

 
Reply With Quote
 
tuchka
Guest
Posts: n/a
 
      11-10-2003
Thank you Irrwahn,
your program rewriting was also very helpful.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Insertion Sort : C++ implementation 100 times slower than C implementation sanket C++ 7 11-03-2011 05:00 AM
Knowing the implementation, are all undefined behaviours become implementation-defined behaviours? Michael Tsang C Programming 54 03-30-2010 07:46 AM
Knowing the implementation, are all undefined behaviours become implementation-defined behaviours? Michael Tsang C++ 32 03-01-2010 09:15 PM
I cannot understand why an object is created this way Shawn Java 1 09-28-2006 06:57 PM
Read all of this to understand how it works. then check around on otherRead all of this to understand how it works. then check around on other thelisa martin Computer Support 2 08-18-2005 06:40 AM



Advertisments