remove spaces from a string and Complexity

[DanielJohnson]

I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters after
the space by one space to the left. I did this program using pointers
and then using array too and I get segmentation fault. What is going
wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;
}

[DanielJohnson]

On Feb 19, 5:08 pm, "DanielJohnson" <[e-mail]:

I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters after
the space by one space to the left. I did this program using pointers
and then using array too and I get segmentation fault. What is going
wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;

}

I want to keep the complexity of the program to the minimum. I have
heard the STL provides list data structure which does it for you but I
was not sure what is the running time of list. So I thought of writing
my own.

How to reduce complexity of such algorithm when you have to manipulate
the same string and keep it to a constant time. Here in the above
program if it works correctly it will be 2*O(n). Any comments ?

[jacob navia]

DanielJohnson a écrit :

I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters after
the space by one space to the left. I did this program using pointers
and then using array too and I get segmentation fault. What is going
wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;
}

If your string ends with a space, you will put a space in the
next character, erasing the zero that terminates the string...

Since the condition that you test for ending the iteration is

while(p[index] != '\0')

you will continue to read beyond the end of the string,
probably indefinitely... until a segmentation fault happens.

If you use two pointers, this can be done in a more simple way

void eraseAllBlanks(char *src)
{
char *dst = src;

while (*src != 0) {
if (*src != ' ') {
*dst++ = *src; // copy
}
src++;
}
*dst = 0;
}

If you want to use array notation:
void eraseAllBlanks(char *src)
{
int srcIndex=0;
int dstIndex=0;

while (src[srcIndex] != 0) {
if (src[srcIndex] != ' ') {
src[dstIndex++] = src[srcIndex]; // copy
}
srcIndex++;
}
src[dstIndex] = 0;
}

[Richard Heathfield]

DanielJohnson said:

On Feb 19, 5:08 pm, "DanielJohnson" <[e-mail]:

>I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters
after the space by one space to the left. I did this program using
pointers and then using array too and I get segmentation fault. What
is going wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;

}

Let's just look at " me", shall we? Or { ' ', 'm', 'e', '\0' } might be
clearer right now.

index = 0, p[index] = ' ', so we copy p[1] to p[0]:

{ 'm', 'm', 'e', '\0' }

p[index + 1] = ' ';

{ 'm', ' ', 'e', '\0' }

index++, so index is now 1.

p[index] = ' ', so we copy p[2] to p[1]:

{ 'm', 'e', 'e', '\0' }

p[index + 1] = ' ';

{ 'm', 'e', ' ', '\0' }

index++, so index is now 2.

p[index] = ' ', so we copy p[3] to p[2]:

{ 'm', 'e', '\0', '\0' }

p[index + 1] = ' ';

{ 'm', 'e', '\0', ' ' }

index++, so index is now 3, and p[index] = p[index + 1] constitutes an
illegal memory access. The problem is that you just assumed that the
while-control would protect you - but it didn't, because you moved the
terminator and the index past each other within the loop.

Even if that weren't a problem, I'm fairly sure the algorithm would
break with multiple spaces, although I haven't examined that too
closely.

What you want to do is fairly easy, actually, and - not surprisingly -
the answer is in K&R2, on page 47:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
int i, j;
for(i = j = 0; s[i] != '\0'; i++)
if(s[i] != c)
s[j++] = s[i];
s[j] = '\0';
}

Here's my own version:

void delchar(char *s, char c)
{
char *t = s;
for(;*s;(*s != c) ? *t++ = *s++ : *s++)
{
continue;
}
*t = '\0';
}

I want to keep the complexity of the program to the minimum.

You'll struggle to beat O(n), which is what I've shown you here.

I have
heard the STL provides list data structure which does it for you but

....but C doesn't have an STL. :-)

How to reduce complexity of such algorithm when you have to manipulate
the same string and keep it to a constant time. Here in the above
program if it works correctly it will be 2*O(n). Any comments ?

2 * O(n) is just O(n) - the trick is to find a computer that runs at
twice the speed. Constant factors can be ignored in O-notation.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[DanielJohnson]

On Feb 19, 5:30 pm, Richard Heathfield <[e-mail]:

DanielJohnson said:

On Feb 19, 5:08 pm, "DanielJohnson" <[e-mail]:

I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters
after the space by one space to the left. I did this program using
pointers and then using array too and I get segmentation fault. What
is going wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;

}

Let's just look at " me", shall we? Or { ' ', 'm', 'e', '\0' } might be
clearer right now.

index = 0, p[index] = ' ', so we copy p[1] to p[0]:

{ 'm', 'm', 'e', '\0' }

p[index + 1] = ' ';

{ 'm', ' ', 'e', '\0' }

index++, so index is now 1.

p[index] = ' ', so we copy p[2] to p[1]:

{ 'm', 'e', 'e', '\0' }

p[index + 1] = ' ';

{ 'm', 'e', ' ', '\0' }

index++, so index is now 2.

p[index] = ' ', so we copy p[3] to p[2]:

{ 'm', 'e', '\0', '\0' }

p[index + 1] = ' ';

{ 'm', 'e', '\0', ' ' }

index++, so index is now 3, and p[index] = p[index + 1] constitutes an
illegal memory access. The problem is that you just assumed that the
while-control would protect you - but it didn't, because you moved the
terminator and the index past each other within the loop.

Even if that weren't a problem, I'm fairly sure the algorithm would
break with multiple spaces, although I haven't examined that too
closely.

What you want to do is fairly easy, actually, and - not surprisingly -
the answer is in K&R2, on page 47:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
int i, j;
for(i = j = 0; s[i] != '\0'; i++)
if(s[i] != c)
s[j++] = s[i];
s[j] = '\0';

}

Here's my own version:

void delchar(char *s, char c)
{
char *t = s;
for(;*s;(*s != c) ? *t++ = *s++ : *s++)
{
continue;
}
*t = '\0';

}

I want to keep the complexity of the program to the minimum.

You'll struggle to beat O(n), which is what I've shown you here.

I have
heard the STL provides list data structure which does it for you but

...but C doesn't have an STL. :-)

How to reduce complexity of such algorithm when you have to manipulate
the same string and keep it to a constant time. Here in the above
program if it works correctly it will be 2*O(n). Any comments ?

2 * O(n) is just O(n) - the trick is to find a computer that runs at
twice the speed. Constant factors can be ignored in O-notation.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999http://www.cpax.org.uk
email: rjh at the above domain, - www.

I have a questions on the above solution. Since you assigned chat *t=s
and then go on using *t++ = *s++, does it seem intuitive . I mean t
and s both point to the same array and you go on copying until you
parse a space upon which you skip. I want to catch up with all the
pointer jargons as it interests me and I keep making mistakes. But I
guess thats the right way to learn.

Thank you again for your wonderfully elegant solutions.

[Richard Heathfield]

DanielJohnson said:

On Feb 19, 5:30 pm, Richard Heathfield <[e-mail]:

<snip>

>Here's my own version:

void delchar(char *s, char c)
{
char *t = s;
for(;*s;(*s != c) ? *t++ = *s++ : *s++)
{
continue;
}
*t = '\0';

}

I have a questions on the above solution. Since you assigned chat *t=s
and then go on using *t++ = *s++, does it seem intuitive . I mean t
and s both point to the same array and you go on copying until you
parse a space upon which you skip.

t, the target, starts off at the same place as s, the source. Every time
s hits a space, no copying is done but s is bumped along, leaving t
trailing behind. Every time s hits a non-space, it is copied to
wherever t is pointing. Eventually, all the non-spaces have been
copied, and t is pointing just at the point where you want to nail the
terminator in place - so that's what happens after the loop.

I want to catch up with all the
pointer jargons as it interests me and I keep making mistakes. But I
guess thats the right way to learn.

If you can't make a mistake, you can't do anything.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Joe Estock]

Richard Heathfield wrote:

DanielJohnson said:

>On Feb 19, 5:08 pm, "DanielJohnson" <[e-mail]:

>>I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters
after the space by one space to the left. I did this program using
pointers and then using array too and I get segmentation fault. What
is going wrong in here ?

[snip op's code]
[snip Richard's explaination]

>
What you want to do is fairly easy, actually, and - not surprisingly -
the answer is in K&R2, on page 47:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
int i, j;
for(i = j = 0; s[i] != '\0'; i++)
if(s[i] != c)
s[j++] = s[i];
s[j] = '\0';
}

Here's my own version:

void delchar(char *s, char c)
{
char *t = s;
for(;*s;(*s != c) ? *t++ = *s++ : *s++)
{
continue;
}
*t = '\0';
}

I've seen functions written as above, however I'm still a little
confused about one point - C passes by value therefore with your above
function wouldn't the following behave incorrectly (incorrectly as in
not modify the contents referenced by the first parameter but instead
modify a copy of it):

int main(void)
{
char *p = NULL;

p = malloc(20);

strcpy(p, " me");

delchar(p, ' ');

return(0);
}

That being said, shouldn't the above function be written as such (i
added 'ptr' to make it a little easier to read, at least in my perspective):

void delchar(char **s, char c)
{
char *t = *s;
char *ptr = *s;
for(;*ptr;(*ptr != c) ? *t++ = *ptr++ : *ptr++)
{
continue;
}
*t = '\0';
}

[snip]

The above has confused me since day 1 of learning the language. I've
long since learned to accept that in order to modify the original
contents from another function a pointer to that data is needed.

[Richard Heathfield]

Joe Estock said:

Richard Heathfield wrote:

>DanielJohnson said:

>>On Feb 19, 5:08 pm, "DanielJohnson" <[e-mail]:
I am writing a program in which I am removing all the spaces from
the string. I thought that I could do it two ways. One was parsing
the string character by character and copying onto another output
string. But this was trivial.
The other option is to use pointers and shift all the characters
after the space by one space to the left. I did this program using
pointers and then using array too and I get segmentation fault.
What is going wrong in here ?

[snip op's code]
[snip Richard's explaination]

>>
What you want to do is fairly easy, actually, and - not surprisingly
- the answer is in K&R2, on page 47:

/* squeeze: delete all c from s */
void squeeze(char s[], int c)
{
int i, j;
for(i = j = 0; s[i] != '\0'; i++)
if(s[i] != c)
s[j++] = s[i];
s[j] = '\0';
}

Here's my own version:

void delchar(char *s, char c)
{
char *t = s;
for(;*s;(*s != c) ? *t++ = *s++ : *s++)
{
continue;
}
*t = '\0';
}

I've seen functions written as above, however I'm still a little
confused about one point - C passes by value therefore with your above
function wouldn't the following behave incorrectly (incorrectly as in
not modify the contents referenced by the first parameter but instead
modify a copy of it):

int main(void)
{
char *p = NULL;

p = malloc(20);

strcpy(p, " me");

delchar(p, ' ');

return(0);
}

Well, if you add <stdlib.hand <string.hand a check for p != NULL,
it'll work fine. The *pointer* is passed by value, yes, but a copy of a
pointer is just as good for finding the object pointed to as the
original pointer. The purpose of delchar() is to modify the *string*,
not the pointer.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Tim Hagan]

"DanielJohnson" <di********@gmail.comwrote in message
news:11********************@j27g2000cwj.googlegrou ps.com...

>I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters after
the space by one space to the left. I did this program using pointers
and then using array too and I get segmentation fault. What is going
wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;
}

Your algorithm is flawed. Instead of shifting all of the characters to
the left, you only shift one and then insert a space. When you hit the
second space in the string you wind up with two consecutive spaces.
Also, things go haywire at the end of the string when the last space
marches off the end and the '\0' is not detected. Hence the seq fault.
Move the puts(p); inside the loop and see what happens at each pass.
Or try working it out the old-fashioned way with pencil and paper.

--
Tim Hagan

[Joe Wright]

DanielJohnson wrote:

I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters after
the space by one space to the left. I did this program using pointers
and then using array too and I get segmentation fault. What is going
wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;
}

I doubt it can work with only one index. Here's mine with pointers.

#include <stdio.h>

int main(void) {
char *d, *s;
char p[] = "please remove spaces from me";
d = s = p;
puts(p);
while (*s) {
while (*s == ' ') ++s;
*d++ = *s++;
}
*d = '\0';
puts(p);
return 0;
}

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Richard Heathfield]

Joe Wright said:

DanielJohnson wrote:

>I am writing a program in which I am removing all the spaces from the
string.

<snip>

I doubt it can work with only one index. Here's mine with pointers.

#include <stdio.h>

int main(void) {
char *d, *s;
char p[] = "please remove spaces from me";
d = s = p;
puts(p);
while (*s) {
while (*s == ' ') ++s;
*d++ = *s++;
}

Consider a string that ends in a space.

while(*s == ' ') ++s; will move s onto the null terminator, which is
then copied to the place pointed to by d, with *d++ = *s++ - but now s
has moved *past* the null terminator, and you're in big trouble
thereafter.

Always Check Edge Cases!

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Andrew Poelstra]

On Wed, 2007-02-21 at 19:25 -0500, Joe Wright wrote:

DanielJohnson wrote:

I am writing a program in which I am removing all the spaces from the
string. I thought that I could do it two ways. One was parsing the
string character by character and copying onto another output string.
But this was trivial.
The other option is to use pointers and shift all the characters after
the space by one space to the left. I did this program using pointers
and then using array too and I get segmentation fault. What is going
wrong in here ?

#include<stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;

while(p[index] != '\0')
{
if (p[index] == ' '){
p[index] = p[index+1];
p[index+1] =' ';
}
index++;
}
puts(p);
return 0;
}

I doubt it can work with only one index. Here's mine :q
with pointers.

I can make it work with only one index. I've tested the special cases:
1. String ends in space
2. String starts in space
3. String is empty ("")
4. String has multiple consecutive spaces

#include <stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;
int spaces = 0;

while(p[index + spaces] != '\0') {
while (p[index + spaces] == ' ')
++spaces;
p[index] = p[index + spaces];
++index;
}
p[index] = '\0';

puts(p);
return 0;
}

--
Andrew Poelstra <http://www.wpsoftware.net>
For email, use 'apoelstra' at the above site.
"You're only smart on the outside." -anon.

[Joe Wright]

Richard Heathfield wrote:

Joe Wright said:

>DanielJohnson wrote:

>>I am writing a program in which I am removing all the spaces from the
string.

<snip>

>I doubt it can work with only one index. Here's mine with pointers.

#include <stdio.h>

int main(void) {
char *d, *s;
char p[] = "please remove spaces from me";
d = s = p;
puts(p);
while (*s) {
while (*s == ' ') ++s;
*d++ = *s++;
}

Consider a string that ends in a space.

while(*s == ' ') ++s; will move s onto the null terminator, which is
then copied to the place pointed to by d, with *d++ = *s++ - but now s
has moved *past* the null terminator, and you're in big trouble
thereafter.

Always Check Edge Cases!

Right you are. Thanks.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Dave Vandervies]

In article <1172109525.10586.5.camel@abacus>,
Andrew Poelstra <ap*******@wpsoftware.netwrote:

>I can make it work with only one index. I've tested the special cases:
1. String ends in space
2. String starts in space
3. String is empty ("")
4. String has multiple consecutive spaces

#include <stdio.h>

int main(void)
{
char p[] = "please remove space from me";
int index = 0;
int spaces = 0;

while(p[index + spaces] != '\0') {
while (p[index + spaces] == ' ')
++spaces;
p[index] = p[index + spaces];
++index;
}
p[index] = '\0';

puts(p);
return 0;
}

You're still using two indices, you're just giving them funny names
("index" and "index+spaces").

(You could, I suppose, quibble about whether index+offset really counts as
an index, but your solution is still isomorphic to a two-index solution.)
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca
When I was learning C, I didn't find too much difficulty in explaining
to my C tutor how it worked.
--Richard Heathfield in comp.lang.c

[CBFalconer]

Joe Wright wrote:

Richard Heathfield wrote:

>Joe Wright said:

>>DanielJohnson wrote:

I am writing a program in which I am removing all the spaces
from the string.

<snip>

>>I doubt it can work with only one index. Here's mine with
pointers.

#include <stdio.h>

int main(void) {
char *d, *s;
char p[] = "please remove spaces from me";
d = s = p;
puts(p);
while (*s) {
while (*s == ' ') ++s;
*d++ = *s++;
}

Consider a string that ends in a space.

while(*s == ' ') ++s; will move s onto the null terminator, which
is then copied to the place pointed to by d, with *d++ = *s++ -
but now s has moved *past* the null terminator, and you're in big
trouble thereafter.

Always Check Edge Cases!

Right you are. Thanks.

I think this works everywhere.

#include <stdio.h>

int main(void) {
char *p;
char s[] = " please remove spaces from me ";
int delta;

p = s; delta = 0;
puts(p);
while (*p) {
while (' ' == *p) {
++p; ++delta;
}
*(p - delta) = *p;
if (*p) ++p;
}
*p = '\0';
puts(s);
return 0;
}

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[pete]

Joe Wright wrote:

>
DanielJohnson wrote:

I am writing a program in which
I am removing all the spaces from the string.

Here's mine with pointers.

#include <stdio.h>

int main(void) {
char *d, *s;
char p[] = "please remove spaces from me";
d = s = p;
puts(p);
while (*s) {
while (*s == ' ') ++s;
*d++ = *s++;
}

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

*d = '\0';
puts(p);
return 0;
}

--
pete