K&R2, exercise 5.4

[arnuld]

PURPOSE: see comments or the problem statement from the K&R2
GETTING: 1 as the only output


/* 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
*
*/


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

int strend( char*, char* );


/* main() will only call the function to do the necessary work. */
int main()
{
int arrsize_s, arrsize_t, arrdiff;
char *ps, *pt;
char s[] = "Like a Stone";
char t[] = "Stone";

arrsize_s = (int) sizeof(s) / sizeof(char);
arrsize_t = (int) sizeof(t) / sizeof(char);
arrdiff = arrsize_s - arrsize_t - 1;

/* we will start at the position in the 1st array, of same length as of
2nd array,
* so that we can compare from there till end. anything before that
length is * of no use to us.
*
*/
ps = s + arrdiff;
pt = t;

printf("\n%d\n", strend(ps,pt));


return EXIT_SUCCESS;
}


/* I amu sing pointers because, arrays are never passed to functions and I
* don't want to FAKE the array call
* outer for loop checks for each element of 1st array. * inner for loop
compares elements of both arrays. * if condition checks whether we have
compared the 2nd array till end. */
int strend( char* s, char* t )
{
char *pj;

for( ; *s != '\0'; *s++ )
{
printf("s --> %c\n--------------------\n\n", *s);
for( pj = s; *t == *pj; t++, pj++ )
{
printf("*t --> %c\n", *t);
printf("*pj --> %c\n", *pj);
}

if( *t == '\0' )
{
return 1;
}
}

return 0;
}

 

[arnuld]

PURPOSE: see comments or the problem statement from the K&R2
GETTING: 1 as the only output

...[SNIP]...

I have come up with following and it runs fine. Any of you finds a
run-time bug in it ?


/* 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
*
*/


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

int strend( char*, char* );


/* main() will only call the function to do the necessary work. */
int main()
{
char s[] = "Love";
char t[] = "ve";


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


return EXIT_SUCCESS;
}


/* I am using pointers because, arrays are never passed to functions and I
* don't want to FAKE the array call
*
* outer for loop checks for each element of 1st array.
* inner for loop compares elements of both arrays.
* if condition checks whether we have compared the 2nd array till end.
*/
int strend( char* s, char* t )
{
char *pj;

for( ; *s != '\0'; *s++ )
{
for( pj = s; *t == *pj && *t != '\0'; t++, pj++ )
{
printf("*t --> %c\n", *t);
printf("*pj --> %c\n", *pj);
}


if( *t == '\0' )
{
return 1;
}
}

return 0;
}

 

[arnuld]

I have come up with following and it runs fine. Any of you finds a
run-time bug in it ?

that has a bug , this is the newer version free of bugs. Do you have
any advice in this program:


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

int strend( char*, char* );



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


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


return EXIT_SUCCESS;
}


/* I am using pointers because, arrays are never passed to functions and I
* don't want to FAKE the array call
*
* outer for loop checks for each element of 1st array.
* inner for loop compares elements of both arrays.
* if condition checks whether we have compared the 2nd array till end.
*/
int strend( char* s, char* t )
{
char *pj;

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

if( *t == '\0' )
{
return 1;
}
}

return 0;
}

 

[Philip Potter]

PURPOSE: see comments or the problem statement from the K&R2
GETTING: 1 as the only output

/* 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
*
*/

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

int strend( char*, char* );

/* main() will only call the function to do the necessary work. */
int main()

Please declare main as int main(void) or int main (char argc, char
**argv). int main() is valid but poor style.

{
int arrsize_s, arrsize_t, arrdiff;

arrsize_t could be a confusing variable name, since so many type names
have the _t suffix: size_t, ptrdiff_t, fpos_t, etc. It's not wrong, just
something to be aware of.

char *ps, *pt;
char s[] = "Like a Stone";
char t[] = "Stone";

arrsize_s = (int) sizeof(s) / sizeof(char);
arrsize_t = (int) sizeof(t) / sizeof(char);
arrdiff = arrsize_s - arrsize_t - 1;

This is misleading. If you name a variable arrdiff, I expect it to
represent a difference. Here, I'd guess the difference between arrsize_s
and arrsize_t. But you instead store arrsize_s - arrsize_t - 1. Why?

/* we will start at the position in the 1st array, of same length as of
2nd array,
* so that we can compare from there till end. anything before that
length is * of no use to us.
*
*/
ps = s + arrdiff;
pt = t;

Now ps points to the first character of a string which is one character
longer than the one pointed to by pt. The '- 1' you added above has
introduced an off-by-one error here.

Also, strend()'s specification above doesn't say that it expects the
strings to be equal length. It should be able to handle arbitrary
lengths - even t longer than s!

printf("\n%d\n", strend(ps,pt));


return EXIT_SUCCESS;
}


/* I amu sing pointers because, arrays are never passed to functions and I
* don't want to FAKE the array call
* outer for loop checks for each element of 1st array. * inner for loop
compares elements of both arrays. * if condition checks whether we have
compared the 2nd array till end. */
int strend( char* s, char* t )
{
char *pj;

for( ; *s != '\0'; *s++ )

You discard the result of dereferencing s. Although '*s++' is not wrong,
it's confusing. Just say 's++'. My compiler gave a warning for this.

{
printf("s --> %c\n--------------------\n\n", *s);
for( pj = s; *t == *pj; t++, pj++ )
{
printf("*t --> %c\n", *t);
printf("*pj --> %c\n", *pj);
}

if( *t == '\0' )
{
return 1;
}
}

return 0;
}

It seems (I guess) your algorithm is to compare t against &s[0], then
&s[1], then &s[2], and stop until you get a total match. If you reach
the end of s, you don't have a match.

There are several problems here:

The reason your strend() always returns 0 (or it does on my machine,
contrary to your complaint) is that the inner string-comparison loop
doesn't terminate when t or pj reach '\0' - so long as they equal each
other, the loop continues merrily along until it finds somewhere they
/don't/ equal. This means you skip right past the '\0' in t so by the
time you test for it, you've missed it. Even worse, you access beyond
the end of the array - which is undefined behaviour. Move the if test
into the loop.

You don't reset the value of t between outer loop iterations. This means
the second time you execute the pj loop, t no longer points to the first
character of the original t string, and you've lost the thing you're
supposed to be looking for. This means that, for example, if we correct
the above problem, you will wrongly match the following:
s = "sxtring", t = "string"
because the first 's' will be matched in the first iteration, and the
remainder of the string ("tring") will be matched in the third.

Finaly, consider your program's efficiency. To compare whether two
strings are equal, as you do in the inner 'pj' loop, is an O(n) problem.
You do this once for each character in s, making the whole algorithm
O(n^2) (or it would, if the above problems are all corrected).

There is an O(n) solution to this problem, which involves finding the
end of both strings and working backwards. This way you only need one
string compare operation.

[Note that the worst case efficiency of O(n^2) requires fairly
pathological conditions, for example, s = "xxxxxxxxxxxxxxxxxxx" and t =
"xxxxxxxxxxxxxxxxA".]

Philip

 

[arnuld]

that has a bug , this is the newer version free of bugs. Do you have
any advice in this program:

I had to add "n > 1" because even the empty string has size = 1.

 

[Philip Potter]

I had to add "n > 1" because even the empty string has size = 1.

You are confusing arrays and strings. A string is a sequence of
characters terminated by '\0'. A string has length equal to the number
of characters before (and not including) '\0'. The empty string contains
one character '\0' and has length 0.

 

[Philip Potter]

You are confusing arrays and strings.

may be.

A string is a sequence of
characters terminated by '\0'. A string has length equal to the number
of characters before (and not including) '\0'. The empty string contains
one character '\0' and has length 0.

no. see:

char a[] = "";
int i;

i = (int) sizeof(a) / sizeof(char);

if you print the vale of i, it will be equal to 1.

sizeof(a) tells you the size of the array, and correctly tells you this
array has size 1. It holds one character, which is the null character '\0'.

You need strlen(a) to tell you the length of the string, which rightly
tells you it is 0.

The string is held in the array, but they are different concepts. The
size of the array is how much storage is available. The length of the
string is how many characters are in the string (where the '\0' doesn't
count as being "in" the string).

As an example:

char a[42] - "";
size_t i;
i = sizeof a; /* i now equals 42 */
i = strlen(a); /* i now equals 0 */

Note that sizeof(char) is guaranteed to be 1.

Incidentally, strlen() works just as well on strings which are
referenced by a char * as on those contained in a char [], because
arrays and pointers are indistinguishable to functions, while they are
different beasts to the sizeof operator. For example:

const char *p = "My lovely string";
size_t i;
i = sizeof p; /* i equals sizeof(char *), which is often 4 */
i = strlen(p); /* i equals 16 if I've counted correctly */

Note that the value of 'sizeof p' tells you nothing about the length of
the string.

Philip

 

[arnuld]

You are confusing arrays and strings.

may be.

A string is a sequence of
characters terminated by '\0'. A string has length equal to the number
of characters before (and not including) '\0'. The empty string contains
one character '\0' and has length 0.

no. see:

char a[] = "";
int i;

i = (int) sizeof(a) / sizeof(char);

if you print the vale of i, it will be equal to 1.

 

[arnuld]

This is misleading. If you name a variable arrdiff, I expect it to
represent a difference. Here, I'd guess the difference between arrsize_s
and arrsize_t. But you instead store arrsize_s - arrsize_t - 1. Why?

I have removed this code. see down below.

The reason your strend() always returns 0 (or it does on my machine,
contrary to your complaint) is that the inner string-comparison loop
doesn't terminate when t or pj reach '\0' - so long as they equal each
other, the loop continues merrily along until it finds somewhere they
/don't/ equal. This means you skip right past the '\0' in t so by the
time you test for it, you've missed it. Even worse, you access beyond
the end of the array - which is undefined behaviour. Move the if test
into the loop.

that doe snot make the difference at all.

[Note that the worst case efficiency of O(n^2) requires fairly
pathological conditions, for example, s = "xxxxxxxxxxxxxxxxxxx" and t =
"xxxxxxxxxxxxxxxxA".]

right now, I don't care about efficiency. I wan the program to work. My
boss, who is standing above my head, keeps on saying, "you should resign
if you can't make such a simple C program in 2 days"

 

[arnuld]

I have removed this code. see down below.

sorry, here is the new code:


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

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; *t == *ps; t++, ps++ )
{
if ( n <= 1)
{
return 0;
}
else if ( *t == '\0' && *ps != '\0' )
{
return 1;
}
}

}

return 0;
}

 

[Philip Potter]

Right. The empty string, "", contains one element, one character, with the
value '\0'. That's why the code prints 1. The string's *length* is 0,
because we define the length of a string as the number of characters
*before* the terminating null character. Thus, in your example, the string
contained in the a array has length 0, but the array has size 1.

okay, that's a new thing I got. Now the problem is finding the
semantic-bug in my code:


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



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

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; *t == *ps; t++, ps++ )
{
if ( n <= 1)
{
return 0;
}
else if ( *t == '\0' && *ps != '\0' )
{
return 1;
}
}

}

return 0;
}

If you had a compiler which gave decent warnings, it would tell you that
pt is assigned a value which you don't then go on to use. That should be
a clue.

An example for gcc is "gcc -ansi -pedantic -W -Wall".

 

[arnuld]

Right. The empty string, "", contains one element, one character, with the
value '\0'. That's why the code prints 1. The string's *length* is 0,
because we define the length of a string as the number of characters
*before* the terminating null character. Thus, in your example, the string
contained in the a array has length 0, but the array has size 1.

okay, that's a new thing I got. Now the problem is finding the
semantic-bug in my code:


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



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

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; *t == *ps; t++, ps++ )
{
if ( n <= 1)
{
return 0;
}
else if ( *t == '\0' && *ps != '\0' )
{
return 1;
}
}

}

return 0;
}

 

[Martin]

right now, I don't care about efficiency. I wan the program to work. My
boss, who is standing above my head, keeps on saying, "you should resign
if you can't make such a simple C program in 2 days"

Am I to understand that you're being paid to write C?

 

[Ben Bacarisse]

<snip>

Stand back and look at the logic a bit...

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

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

In this loop you know (until they change) that *t == *ps, OK?

if ( n <= 1)
{
return 0;
}
else if ( *t == '\0' && *ps != '\0' )
{

This is the only place you can return 1. You know that *t == *ps so
if *t == 0 then you also know that *ps == 0 also so this whole test is
never true. You can't return 1. Ever.

return 1;
}
}

}

return 0;
}

That can be fixed, but I'd:

Find the length of s and t.
If t longer than s return 0.
else return string @ s + (len(s) - len(t)) == t?

translate into C.

 

[Barry Schwarz]

I have removed this code. see down below.




that doe snot make the difference at all.

Undefined behavior always makes a difference.


Remove del for email

 

[Barry Schwarz]

okay, that's a new thing I got. Now the problem is finding the
semantic-bug in my code:

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.

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



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

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 )

n is 2 since t contains 'e' and '\0'.

{
char *ps, *pt;

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

When does n ever change?

{
return 0;
}
else if ( *t == '\0' && *ps != '\0' )
{
return 1;
}
}

}

return 0;
}

Remove del for email

 

[Richard]

You are confusing arrays and strings. A string is a sequence of

You dispute that the size needed to store the empty string is 1?

 

[Philip Potter]

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. The sizeof operator cannot accept strings as an
argument (though it can tell you the size of a char[] or a char *). As a
result, it is meaningless to talk about the size of a string, only the
length.

 

[Hallvard B Furuseth]

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.

OTOH it's not much use to apply it to a pointer variable which has been
assigned a string.

 

[Philip Potter]

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

Let's give it a go:

char a[59] = "String 1";
char b[] = "String 2";
char *p = "String 3";

Now, sizeof a tells me the size of the array a, which is 59. The fact
that a contains, in its first 9 bytes, a string of length 8, is neither
here nor there.

sizeof b tells me the size of the array b, which is 9. The fact that it
contains, in its entirety, a string of length 8, is no more relevant
than it was before. The value of the object has no effect on the size of
the object.

sizeof p tells me the size of the pointer p, which is
implementation-defined, but certainly doesn't depend on the length of
the string literal it points to.

I really can't think of anything else which I might try to put into
sizeof to get the size of a string. Perhaps sizeof "String 4" - but
that's the size of a string literal, which is not a string, but a char
[] which contains a string. Besides, once you've used sizeof on a string
literal, you've lost the only reference you had to it.

If I am mistaken, and there is some obscure syntax which will get the
/string itself/ as the operand of sizeof, and not some object which
contains the string or points to the string, please enlighten me.

OTOH it's not much use to apply it to a pointer variable which has been
assigned a string.

A string, according to the Standard, is a contiguous sequence of
characters terminated by and including the first null character.

The sizeof operator operates on types, whether directly or indirectly.
'sizeof(type_t)' tells you the size, in bytes, of an object of type
type_t. 'sizeof x' tells you the size, in bytes, of the object x, which
is determined purely by its type. A string is not a type. Therefore, the
sizeof operator cannot operate on strings.