Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > K&R2, exercise 5.4

Reply
Thread Tools

K&R2, exercise 5.4

 
 
Hallvard B Furuseth
Guest
Posts: n/a
 
      04-09-2008
Philip Potter writes:
>Hallvard B Furuseth wrote:
>>Philip Potter writes:
>>> No. I dispute that "the empty string has size = 1", which is a
>>> different statement entirely. The sizeof operator cannot accept
>>> strings as an argument

>>
>> What gave you that idea? Yes it can. Try.

>
> Let's give it a go:
>
> char a[59] = "String 1";
> (...)


Duh, of course. I was thinking "string literal", not "string".

--
Hallvard
 
Reply With Quote
 
 
 
 
Anand Hariharan
Guest
Posts: n/a
 
      04-10-2008
On Wed, 09 Apr 2008 18:47:00 +0100, Philip Potter wrote:

> Richard wrote:
>> You dispute that the size needed to store the empty string is 1?

>
> No. I dispute that "the empty string has size = 1", which is a different
> statement entirely.


ITYM "I /contend/ that \"the empty string has size = 1\"". Or am I
splitting hairs here?


--
ROT-13 email address to reply
 
Reply With Quote
 
 
 
 
arnuld
Guest
Posts: n/a
 
      04-10-2008
>On Wed, 09 Apr 2008 08:20:45 -0700, Barry Schwarz wrote:

> In two hours you published six versions of this program. This is the
> latest according to my news server but I have no idea if it is the
> latest you published. Keeping the title the same is good but maybe
> you should put a version number in the code.



ok here is the final working version


/* Exercise 5.4 from K&R2, page 107
*
* write the function strend(s, t) which returns 1 if the
* string t occurs at the end of string s and zero otherwise.
*
* Final-Version of code
*/


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

int strend( char*, char*, int );



int main( void )
{
int arrsize;
char s[] = "Love";
char t[] = "ve";

arrsize = (int) sizeof(t) / sizeof(char);

printf("\n%d\n", strend(s,t, arrsize));


return EXIT_SUCCESS;
}



int strend( char* s, char* t, int n )
{
char *ps, *pt;

for( ; *s != '\0'; s++ )
{
for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
{
;
}

if( n > 1 && *pt == '\0' && *ps == '\0' )
{
return 1;
}

}

return 0;
}




--
http://lispmachine.wordpress.com/

Please remove capital 'V's when you reply to me via e-mail.

 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      04-10-2008
> On Thu, 10 Apr 2008 11:41:18 +0500, arnuld wrote:

> ok here is the final working version


The only thing I did not understand in my final version is if I remove
these 2 pieces of code:

1.) *pt != '\0' from inner <for> loop
2.) *pt == '\0' && *ps == '\0' , from <if> condition

then the program gives strange results


removing (1) will force code to compare for '\0' in the inner for loop and
hence there is no need to compare for NULL in <if> condition. Then why
program gives wrong results ?




--
http://lispmachine.wordpress.com/

Please remove capital 'V's when you reply to me via e-mail.

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      04-10-2008
arnuld <(E-Mail Removed)> writes:

>> On Thu, 10 Apr 2008 11:41:18 +0500, arnuld wrote:

>
>> ok here is the final working version

>
> The only thing I did not understand in my final version is if I remove
> these 2 pieces of code:
>
> 1.) *pt != '\0' from inner <for> loop
> 2.) *pt == '\0' && *ps == '\0' , from <if> condition
>
> then the program gives strange results
>
>
> removing (1) will force code to compare for '\0' in the inner for loop and
> hence there is no need to compare for NULL in <if> condition. Then why
> program gives wrong results ?


You need to just work though what happens. Mod no 1 allows ps and pt
to run off the end of the strings. In fact, most string loops like
this are wrong:

for (<setup>; *s1 == *s2; s1++, s2++) <stuff>;

Why? Because you might look at the characters after the nulls and
there may be no such character -- anything at all might happen.

Mod 2 is just daft (sorry!). Regardless of whether you do 1 or not,
that just leaves: if (n > 1) so you return result simply depends on
getting into the loop at all and nothing at all about the strings.
See my other post about the n parameter.

--
Ben.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      04-10-2008
arnuld <(E-Mail Removed)> writes:

> ok here is the final working version


Not quite!

> /* Exercise 5.4 from K&R2, page 107
> *
> * write the function strend(s, t) which returns 1 if the
> * string t occurs at the end of string s and zero otherwise.
> *
> * Final-Version of code
> */


<snip>

> int strend( char* s, char* t, int n )


You need to loose the n. The question as posed (see above) can be
answered knowing only s and t. No further data is needed, so any
other parameters you give must come from some misunderstanding or the
problem.

> {
> char *ps, *pt;
>
> for( ; *s != '\0'; s++ )
> {
> for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
> {
> ;
> }
>
> if( n > 1 && *pt == '\0' && *ps == '\0' )


Even when you loose the n, this test is over complex. Write down what
you know when the loop above ends.

> {
> return 1;
> }
>
> }
>
> return 0;
> }


--
Ben.
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      04-10-2008
> Ben Bacarisse <(E-Mail Removed)> writes:

>> arnuld <(E-Mail Removed)> writes:


>> int strend( char* s, char* t, int n )


> You need to loose the n. The question as posed (see above) can be
> answered knowing only s and t. No further data is needed, so any
> other parameters you give must come from some misunderstanding or the
> problem.



ok, I removed "n". I have to use my_strlen - to find the length of the string:



/* Exercise 5.4 from K&R2, page 107
*
* write the function strend(s, t) which returns 1 if the
* striing t occurs at the end of string s and zero otherwise
*
* Final Version 2
*/


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

int strend( char*, char*);
int my_strlen( char* s);



int my_strlen( char* s )
{
char* ps;

ps = s;
while( *ps != '\0' )
{
++ps;
}

return ps - s;
}


int main( void )
{
char s[] = "Love";
char t[] = "ee";


printf("\n%d\n", strend(s,t));


return EXIT_SUCCESS;
}



int strend( char* s, char* t )
{
char *ps, *pt;
int len_of_t;

len_of_t = my_strlen( t );


for( ; *s != '\0'; s++ )
{
for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
{
;
}

if( len_of_t && *pt == '\0' && *ps == '\0' )
{
return 1;
}

}

return 0;
}






>> if( n > 1 && *pt == '\0' && *ps == '\0' )


> Even when you loose the n, this test is over complex. Write down what
> you know when the loop above ends.


<if> follows from the inner <for> loop:

for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )

lets say s = "Love" and t = "ee"

then *pt == *ps will go false and hence the NULL checking in the if condition
is required otherwise it will always print 1. I am not able to find a
replacement for this.


 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      04-10-2008
arnuld <(E-Mail Removed)> writes:

>> Ben Bacarisse <(E-Mail Removed)> writes:

>
>>> arnuld <(E-Mail Removed)> writes:

>
>>> int strend( char* s, char* t, int n )

>
>> You need to loose the n. The question as posed (see above) can be
>> answered knowing only s and t. No further data is needed, so any
>> other parameters you give must come from some misunderstanding or
>> the problem.


I meant "of the problem", but that was not one of my worst typos!

> ok, I removed "n". I have to use my_strlen - to find the length of
> the string:


That's one way, but having found the length you could put it to much
more use (I posted an outline elsewhere).

<snip>
>>> if( n > 1 && *pt == '\0' && *ps == '\0' )

>
>> Even when you loose the n, this test is over complex. Write down what
>> you know when the loop above ends.

>
> <if> follows from the inner <for> loop:
>
> for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
>
> lets say s = "Love" and t = "ee"
>
> then *pt == *ps will go false and hence the NULL checking in the if condition
> is required otherwise it will always print 1. I am not able to find a
> replacement for this.


I don't think I am wrong, but the logic is a bit hairy, so lets just
tabulate the cases:

*ps *pt *ps == *pt
0 0 0 logically impossible
0 0 1 match found
0 x 0 no match
0 x 1 logically impossible
x 0 0 no match
x 0 1 logically impossible
x y 0 impossible (loop won't have ended)
x x 1 impossible (loop won't have ended)

The last two can't occur because the loop won't have terminated.
Three other cases are not possible due to simple logic (e.g. in the
first line, if both *pt and *pt are 0 the last entry must be 1 not
0). That leaves:

*ps *pt *ps == *pt
0 0 1 match found
0 x 0 no match
x 0 0 no match

so you could just test *ps == *pt. What this means is that loop must
have ended because *pt == 0, so there is no point in test in both.
Now, I agree this not obvious, but when you start to think this way it
does become clearer. You would, absolutely, have to have a comment
saying:

if (*ps == *pt) {
/* The for loop must have ended because *pt == 0. */
return 1;
}

--
Ben.
 
Reply With Quote
 
Philip Potter
Guest
Posts: n/a
 
      04-10-2008
arnuld wrote:
> int strend( char* s, char* t )
> {
> char *ps, *pt;
> int len_of_t;
>
> len_of_t = my_strlen( t );
>
>
> for( ; *s != '\0'; s++ )
> {
> for( ps = s, pt = t; *pt == *ps && *pt !='\0'; pt++, ps++ )
> {
> ;
> }
>
> if( len_of_t && *pt == '\0' && *ps == '\0' )


You're saying that if t is length zero then it can't be the end of any
other string. I would argue that a string of length zero is /always/ the
end of another string.

If I have two nonempty strings a and b, and I know b is a suffix of a
(ie strcmp(&a[i],b) == 0 for some value of i), then surely if I chop a
character off the end of a and b then b will still be a suffix of a?

Similarly, if two strings are equal, then each is a suffix of the other.
Therefore "" is a suffix of "".

With all this in mind, you don't need a special case for the empty
string because it Just Works.

As Ben (and I) have said, you can use len_of_t to make a far more
efficient algorithm.

> {
> return 1;
> }
>
> }
>
> return 0;
> }

 
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
tree functions daily exercise: Range Xah Lee Java 12 06-22-2005 08:51 AM
Cisco Student VPN exercise problem : gen_unrfrag: fail to generate unreachable, unexpected args robert Cisco 0 06-02-2004 07:33 PM
2154 module 4 Exercise 2 Drew Brown MCSE 0 10-22-2003 02:47 AM
Exercise needed for java 2 programmer test lonelyplanet999 Java 1 09-30-2003 10:37 AM
Re: Development best practices and knowing when to exercise control over development Kevin Spencer ASP .Net 2 08-06-2003 09:33 PM



Advertisments