467,184 Members | 1,298 Online

# How can i Right Trim all the spaces of a very long (2000 chars) Charecter string ?

 Hi All, Pleas help me .I am a starter as far as C Language is concerned . How can i Right Trim all the white spaces of a very long (2000 chars) Charecter string ( from the Right Side ) ? or how can i make a fast Right Trim Function in c,using Binary search kind of fast algorithm ? Offcourse...I can use the classical approach too. like : Start from the right most charecter of the string to the left of the string and stop where we find the first none-whitespace charecter and insert a NULL charecter,after increasing one place.It is working fine.But problem is that suppose my string can hold 2000 charecters,but in a particular case i have only 1 charecter in my string ,then i will have to sequentially traverse from charecter position 2000 to 1 (1999 sequential searches) to put a NULL char at position number 2. String is of varying length sometime it can be of 2 charecters long and other time it can have 2000 charecters too. How can i use Binary search kind of fast search mechanism in the above scenario in my function. Please help me. Thanks in advance. Regards, Durgesh Sharma Nov 14 '05 #1
• viewed: 5945
Share:
9 Replies
 On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote: Hi All, Pleas help me .I am a starter as far as C Language is concerned . How can i Right Trim all the white spaces of a very long (2000 chars) Charecter string ( from the Right Side ) ? or how can i make a fast Right Trim Function in c,using Binary search kind of fast algorithm ? Offcourse...I can use the classical approach too. like : Start from the right most charecter of the string to the left of the string and stop where we find the first none-whitespace charecter and insert a NULL charecter,after increasing one place.It is working fine.But problem is that suppose my string can hold 2000 charecters,but in a particular case i have only 1 charecter in my string ,then i will have to sequentially traverse from charecter position 2000 to 1 (1999 sequential searches) to put a NULL char at position number 2. String is of varying length sometime it can be of 2 charecters long and other time it can have 2000 charecters too. How can i use Binary search kind of fast search mechanism in the above scenario in my function. Please help me. Thanks in advance. Regards, Durgesh Sharma I don't think there is any better way to solve your problem in general. But if the string satisfies some special constraints, it may be possible. Is the string allowed to contain white spaces in the significant part? If so, I don't see any way to find the last white space except to start from the end of the string and work backwards as you are currently doing. If the string is NOT allowed to contain white spaces in the significant part, then you can use a binary search algorithm. Something like the following, which I threw together far too fast and didn't test: #include void right_trim(char *s, long len) { long part_len, current; part_len = len; current = len/2; while(part_len > 1) { part_len /= 2; if (isspace(s[current])) current -= part_len; else { if ((current < len) { if (isspace(s[current+1])) { s[current + 1] = '\0'; return; } else current += part_len; } } } } Like I said, it is untested and probably won't work as written, but you will hopefully get the idea. --Mac Nov 14 '05 #2
 On 4 Dec 2004 04:10:33 -0800, du******@compucomtech.co.in (Durgesh Sharma) wrote: Hi All,Pleas help me .I am a starter as far as C Language is concerned .How can i Right Trim all the white spaces of a very long (2000 chars)Charecter string ( from the Right Side ) ? or how can i make a fastRight Trim Function in c,using Binary search kind of fast algorithm ? ....String is of varying length sometime it can be of 2 charecters longand other time it can have 2000 charecters too. Just some ideas.. Assuming you know the length of the string already: copy the string pointer to to a pointer to ints (32 bits). Then you can test the majority of the 2000 chars as <500 ints (each int will be 0x20202020 if all spaces), which should be faster. You may have to test some 1..3 odd chars at the end first, then 1..3 odd chars as soon as the ints values aren't 0x20202020. Also it is best if the int pointer is aligned to a 32-bit boundary. Generally very messy and only worth doing for the longest strings. You may want to test the trivial cases first of empty string and whether the first char is a space. Then your loop doesn't need to count, it is guaranteed to meet a non-space at some point. If you don't already know the string length, create your own strlen(0 function that notes the last non-space character encountered. Then trimming is trivial. Bart Nov 14 '05 #4
 On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote: Hi All, Pleas help me .I am a starter as far as C Language is concerned . How can i Right Trim all the white spaces of a very long (2000 chars) Charecter string ( from the Right Side ) ? or how can i make a fast Right Trim Function in c,using Binary search kind of fast algorithm ? Binary searches work on sorted data. Since you don't have sorted data here the approach is not applicable. Offcourse...I can use the classical approach too. like : Start from the right most charecter of the string to the left of the string and stop where we find the first none-whitespace charecter and insert a NULL charecter,after increasing one place.It is working fine.But problem is that suppose my string can hold 2000 charecters,but in a particular case i have only 1 charecter in my string ,then i will have to sequentially traverse from charecter position 2000 to 1 (1999 sequential searches) to put a NULL char at position number 2. A non-whitespace character in any of those 1999 positions would affect the result, and since there isn't any ordering in the data an algorithm that didn't end up checking every position beyond the actual last non-whitespace character would be broken. Any character it didn't check might contain a non-whitespace character. .... How can i use Binary search kind of fast search mechanism in the above scenario in my function. Not usefully. Lawrence Nov 14 '05 #5
 Greetings, Lawrence Kirby wrote: On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote:Hi All,Pleas help me .I am a starter as far as C Language is concerned .How can i Right Trim all the white spaces of a very long (2000 chars)Charecter string ( from the Right Side ) ?or how can i make a fastRight Trim Function in c,using Binary search kind of fast algorithm ? Binary searches work on sorted data. Since you don't have sorted data here the approach is not applicable. Not entirely true, but we've not enough information to determine if it's true or not. If the string cannot contain spaces except for padding on the right then it is sorted where space is greater than any other character, and a binary search is possible. Also, if it's known that the string can have at most one space between any non-space characters, then a binary search can also be implemented. If an unknown number of spaces can occur between non-space characters, then a binary search is not feasible. -- Kyle A. York Sr. Subordinate Grunt Nov 14 '05 #6
 kyle york wrote: Greetings, Lawrence Kirby wrote: On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote: Hi All, Pleas help me .I am a starter as far as C Language is concerned . How can i Right Trim all the white spaces of a very long (2000 chars) Charecter string ( from the Right Side ) ? or how can i make a fast Right Trim Function in c,using Binary search kind of fast algorithm ? Binary searches work on sorted data. Since you don't have sorted data here the approach is not applicable. Not entirely true, but we've not enough information to determine if it's true or not. If the string cannot contain spaces except for padding on the right then it is sorted where space is greater than any other character, and a binary search is possible. Sorted? The spaces to the right of the non-spaces would be of course less that the non-spaces. The task would be to find not just any, but the first space after the last non-space. The binary search would be a little perverse. Also the problem it is trying to solve is contrived. Nobody has asked to trim "maryhadalittlelamb " of its trailing spaces. Also, if it's known that the string can have at most one space between any non-space characters, then a binary search can also be implemented. Not that I doubt you, but I don't know exactly how I would do that. Plase code it up and show me how. If an unknown number of spaces can occur between non-space characters, then a binary search is not feasible. -- Joe Wright mailto:jo********@comcast.net "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Nov 14 '05 #7
 "Joe Wright" wrote in message news:tr********************@comcast.com... kyle york wrote: Lawrence Kirby wrote: On Sat, 04 Dec 2004 04:10:33 -0800, Durgesh Sharma wrote: How can i Right Trim all the white spaces of a very long (2000 chars) Charecter string ( from the Right Side ) ? or how can i make a fast Right Trim Function in c,using Binary search kind of fast algorithm ? Binary searches work on sorted data. Since you don't have sorted data here the approach is not applicable. Not entirely true, but we've not enough information to determine if it's true or not. If the string cannot contain spaces except for padding on the right then it is sorted where space is greater than any other character, and a binary search is possible. Sorted? The spaces to the right of the non-spaces would be of course less that the non-spaces. It doesn't really matter, but I think Kyle meant "It is sorted in ascending order if you consider space greater than any other character". The task would be to find not just any, but the first space after the last non-space. The binary search would be a little perverse. How would /you/ find the first of the set of equal items in a sorted array? Or are you saying you'd never want to do that? Also the problem it is trying to solve is contrived. That I agree with. Also, if it's known that the string can have at most one space between any non-space characters, then a binary search can also be implemented. Not that I doubt you, but I don't know exactly how I would do that. Plase code it up and show me how. I'm sure you can write something very much like a binary search (not complete and almost certainly not quite correct, but hopefully illustrates the idea): low = 0; high = strlen(s); for (;;) { mid = (low + high) / 2; if (mid == low) break; if (s[mid] == ' ') { for (i = mid + 1; i < high; ++i) if (s[i] != ' ') break; if (i < high) low = i + 1; else high = mid; } else { low = mid + 1; } } Alex Nov 14 '05 #8
 Joe Wright wrote: kyle york wrote: Also, if it's known that the string can have at most one space between any non-space characters, then a binary search can also be implemented. Not that I doubt you, but I don't know exactly how I would do that. Plase code it up and show me how. Search on two-character chunks. Chunks with zero or one space are low, two spaces are high. No order within the low range is necessary. Once you've found either the first two-space chunk or none at all, check whether the last non-two-space chunk end in an odd space. This is not likely to be very useful, especially since... If an unknown number of spaces can occur between non-space characters, then a binary search is not feasible. ....this is very probably the case. Richard Nov 14 '05 #9
 On Mon, 06 Dec 2004 08:52:11 -0800, kyle york wrote: .... Binary searches work on sorted data. Since you don't have sorted data here the approach is not applicable. Not entirely true, but we've not enough information to determine if it's true or not. Specifically there is nothing in the problem specification that allows us to consider the data "sorted" for our purposes. So I stand by my statement. :-) Lawrence Nov 14 '05 #10

### This discussion thread is closed

Replies have been disabled for this discussion.