remove spaces from a string and Complexity

D

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;
}
 
D

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;

}
Click to expand...

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 ?
 
J

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;
}
Click to expand...

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;
}
 
R

Richard Heathfield

DanielJohnson said:
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;

}
Click to expand...
Click to expand...

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 != '\0'; i++)
if(s != c)
s[j++] = s;
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.
Click to expand...

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
Click to expand...

....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 ?
Click to expand...

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.
 
D

DanielJohnson

DanielJohnson said:


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;
}
Click to expand...
Click to expand...

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 != '\0'; i++)
if(s != c)
s[j++] = s;
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.
Click to expand...

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
Click to expand...

...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 ?
Click to expand...

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.
Click to expand...


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.
 
J

Joe Estock

Richard said:
DanielJohnson said:
Click to expand...

[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 != '\0'; i++)
if(s != c)
s[j++] = s;
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';
}
Click to expand...


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.
 
R

Richard Heathfield

DanielJohnson said:
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.
Click to expand...

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.
Click to expand...

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

Tim Hagan

DanielJohnson said:
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;
}
Click to expand...


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.
 
R

Richard Heathfield

Joe Estock said:
Richard said:
DanielJohnson said:
Click to expand...

[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 != '\0'; i++)
if(s != c)
s[j++] = s;
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';
}
Click to expand...


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):
Click to expand...

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

p = malloc(20);

strcpy(p, " me");

delchar(p, ' ');

return(0);
}
Click to expand...

Well, if you add <stdlib.h> and <string.h> and 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.
 
J

Joe Wright

DanielJohnson said:
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;
}
Click to expand...
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;
}
 
R

Richard Heathfield

Joe Wright said:

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++;
}
Click to expand...

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!
 
A

Andrew Poelstra

DanielJohnson said:
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;
}
Click to expand...
I doubt it can work with only one index. Here's mine :q
with pointers.
Click to expand...

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;
}
 
J

Joe Wright

Richard said:
Joe Wright said:

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++;
}
Click to expand...

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!
Click to expand...
Right you are. Thanks.
 
D

Dave Vandervies

Andrew Poelstra said:
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;
}
Click to expand...

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
 
C

CBFalconer

Joe said:
Richard said:
Joe Wright said:
DanielJohnson wrote:

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

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++;
}
Click to expand...

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!
Click to expand...
Right you are. Thanks.
Click to expand...

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;
}
 
P

pete

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++;
}
Click to expand...

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

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

Similar Threads

STRING - Remove small letters from string 1
Remove Space, Stuck on lab 1
How can I remove last * from each "organisations": value from the string without using JSON.parse() and remove last , from [] using javascript? 6
java.util.LinkedList.iterator().remove() time complexity 7
Ordenate and remove duplicate cases of an array passed as a c function argument 0
String and list error while running a Markov Chain 1
C code String And Comparison 2
Hi people.. I need help in the Pascal please 0

Members online

Total: 32 (members: 1, guests: 31)
Robots: 188

Forum statistics

Threads
473,755
Messages
2,569,534
Members
45,008
Latest member
Rahul737

Latest Threads

Top