440,929 Members | 1,245 Online Need help? Post your question and get tips & solutions from a community of 440,929 IT Pros & Developers. It's quick & easy.

# remove spaces from a string and Complexity

 P: n/a 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 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; } Feb 19 '07 #1
15 Replies

 P: n/a On Feb 19, 5:08 pm, "DanielJohnson" 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 ? Feb 19 '07 #2

 P: n/a 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 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; } Feb 19 '07 #3

 P: n/a DanielJohnson said: On Feb 19, 5:08 pm, "DanielJohnson" I am writing a program in which I am removing all the spaces from thestring. I thought that I could do it two ways. One was parsing thestring character by character and copying onto another output string.But this was trivial.The other option is to use pointers and shift all the charactersafter the space by one space to the left. I did this program usingpointers and then using array too and I get segmentation fault. Whatis going wrong in here ?#includeint 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 to p: { 'm', 'm', 'e', '\0' } p[index + 1] = ' '; { 'm', ' ', 'e', '\0' } index++, so index is now 1. p[index] = ' ', so we copy p to p: { 'm', 'e', 'e', '\0' } p[index + 1] = ' '; { 'm', 'e', ' ', '\0' } index++, so index is now 2. p[index] = ' ', so we copy p to p: { '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. Feb 19 '07 #4

 P: n/a On Feb 19, 5:30 pm, Richard Heathfield 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 to p: { 'm', 'm', 'e', '\0' } p[index + 1] = ' '; { 'm', ' ', 'e', '\0' } index++, so index is now 1. p[index] = ' ', so we copy p to p: { 'm', 'e', 'e', '\0' } p[index + 1] = ' '; { 'm', 'e', ' ', '\0' } index++, so index is now 2. p[index] = ' ', so we copy p to p: { '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. Feb 19 '07 #5

 P: n/a DanielJohnson said: On Feb 19, 5:30 pm, Richard Heathfield >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. Feb 19 '07 #6

 P: n/a Richard Heathfield wrote: DanielJohnson said: >On Feb 19, 5:08 pm, "DanielJohnson" >I am writing a program in which I am removing all the spaces from thestring. I thought that I could do it two ways. One was parsing thestring character by character and copying onto another output string.But this was trivial.The other option is to use pointers and shift all the charactersafter the space by one space to the left. I did this program usingpointers and then using array too and I get segmentation fault. Whatis 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. Feb 19 '07 #7

 P: n/a Joe Estock said: Richard Heathfield wrote: >DanielJohnson said: >>On Feb 19, 5:08 pm, "DanielJohnson" >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

 P: n/a "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 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 Feb 19 '07 #9

 P: n/a 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 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 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 --- Feb 22 '07 #10

 P: n/a Joe Wright said: DanielJohnson wrote: >I am writing a program in which I am removing all the spaces from thestring. I doubt it can work with only one index. Here's mine with pointers. #include 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. Feb 22 '07 #11

 P: n/a 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 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 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 For email, use 'apoelstra' at the above site. "You're only smart on the outside." -anon. Feb 22 '07 #12

 P: n/a Richard Heathfield wrote: Joe Wright said: >DanielJohnson wrote: >>I am writing a program in which I am removing all the spaces from thestring. >I doubt it can work with only one index. Here's mine with pointers.#include 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 --- Feb 22 '07 #13

 P: n/a In article <1172109525.10586.5.camel@abacus>, Andrew Poelstra 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 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 Feb 23 '07 #14

 P: n/a Joe Wright wrote: Richard Heathfield wrote: >Joe Wright said: >>DanielJohnson wrote:I am writing a program in which I am removing all the spacesfrom the string. >>I doubt it can work with only one index. Here's mine withpointers.#include 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, whichis 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 bigtrouble thereafter.Always Check Edge Cases! Right you are. Thanks. I think this works everywhere. #include 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. Feb 23 '07 #15

 P: n/a 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 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 Feb 27 '07 #16

### This discussion thread is closed

Replies have been disabled for this discussion. 