【原创】超强版 Trim 横空出世！

flw

昨天给一个同事讲 trim，一时豪情大发，一不小心编出了这段代码，后来仔细看看，确实是堪称精品，不过又怕有什么遗漏的地方，所以赶紧发到这里让大家帮我参详参详。

1. void trim( char *str )
   
2. {
   
3.         char *copied, *tail = NULL;
   
4. 
   
5.         if ( str == NULL )
   
6.                 return;
   
7. 
   
8.         for( copied = str; *str; str++ )
   
9.         {
   
10.                 if ( *str != ' ' && *str != '\t' )
    
11.                 {
    
12.                         *copied++ = *str;
    
13.                          tail = copied;
    
14.                 }
    
15.                 else
    
16.                 {
    
17.                          if ( tail )
    
18.                                  *copied++ = *str;
    
19.                 }
    
20.         }
    
21. 
    
22.         if ( tail )
    
23.              *tail = 0;
    
24.         else
    
25.              *copied = 0;
    
26. 
    
27.         return;
    
28. }

复制代码

flw

原帖由 "lenovo" 发表：
if ( str == NULL )
                return NULL;
原型是返回void哦。

哦，粗心了，改过。

flw

原帖由 "lenovo" 发表：
还有else
             *copied = 0;
是否也可以去掉。
因为你for循环结束时的条件就是*copied =＝ 0
还有应该是*str != 32 && *str != 9吧？

真的是太不好意思了。
今天没有带电脑，刚才的这段代码是默写出来的，所以有很多错误。
刚才又改了一下，循环的条件改正确了。

另：TAB 的键值我可能的确是记错了。
但是程序中不建议直接写 ASCII 码，我是因为怕空格看不清楚才这么写的，现在改回去了。

flw

原帖由 "w25" 发表：
从那说起这个是超强的trim阿，它能去掉中间的空格，前面的空格，后面的空格，是全部还是部分阿。
还有，str！等于8或9有什么区别么？我看只要不等于32就算满足要求了！

它能去掉前面的和后面的空格，中间的不会去掉。网络通讯中经常用到。

9 是 TAB，TAB 一般和空格做同样的解释。所以也要去掉。

之所以说“超强”是因为只用了一个循环两个变量，估计也不能更简洁了。

flw

原帖由 "FH" 发表：
不错！

但我觉得应该把所有控制符都去掉，举个例子：BS也应该处理吧？而且处理起来还很复杂。STX，ACK等等有意义吗？
我都是判<=空格的，又干净效率还高。

呵呵，这个就不好说了，比如我们公司的接口中，都用 \1 来当做字段的分隔符，所以是不能去掉的。
通常情况下，<32 的字符由于大多是不可见字符，实际应用中用不着，所以恰恰被很多接口采用为转义字符、分隔符、类型符、控制符等等，所以绝对是不可以去掉的。


再说了，要是想去掉，改一下我这个代码就可以了。
反正又不影响算法的效率：“时间复杂度”和“空间复杂度”，
所以我不会在意的。

我在意的是：我的这个算法有没有漏洞？有没有人能写出比我这个更好的算法？

flw

[quote]原帖由 "FH"]这个算法在尾部空格较多时有损失。 [/quote 发表：

有什么损失？这个损失可以避免吗？
要想知道字符串中有没有空格、有多少空格，至少要将字符串扫描一遍，
而我的程序就只扫描了一遍。
我想，还不至于有一种算法可以扫描一半就知道用不用去空格吧？

[quote]原帖由 "FH"]我再给你简化一下，主要是从效率角度考虑[/quote 发表：

你说的“简化”“效率”指的是“尽量少引用指针”吗？
我实在想不通，用 c 来代替 *str 有什么好。

flw

[quote]原帖由 "BingbingNorth"]如果该字符串前部没有空格（或空格串），只有尾部有，那么，if ( tail )这个条件判断就要进行O(n)次，这完全可以用分情况的办法解决[/quote 发表：

请问，如何“分情况”？
咱们先不考虑简洁不简洁的因素，就看效率。

[quote]原帖由 "BingbingNorth"]大家降低时间复杂性的方法是在到达字符串结尾后又折回来。flw兄的是利用了tail变量来记住应该赋'\0'值的位置，但是这样一来，每次都要进行tail = copied[/quote 发表：

这个不然，好象“赋值”运算似乎的确要比“循环碰到结尾再退回来”时的指针“减减”的效率要低些？不过，若是“循环碰到结尾再退回来”，还需要判断循环条件，按照平均情况来考虑，难道一个赋值语句的执行效率尚不如“减减”加上“判断循环条件”两个运算的效率？何况，我又不是每次都要赋值，只是当 *str 所指为“黑字符”时才赋值。卿之所言，甚难服众。

[quote]原帖由 "BingbingNorth"]串处理指令[/quote 发表：

愿闻其详，望不吝赐教！

flw

大家争论的结果正好说明了一个问题，
那就是说，简洁的程序未必运行得快，
而繁复的程序未必运行得慢。
而我们程序员们，通常有很多时间都在选择，到底是应该把程序写的更加简练一些，还是写的繁复一些呢？

正所谓仁者见仁，智者见智，不同的情况下，可能需要不同的策略，
比如说在某些受限系统中，可能多浪费一个变量的空间都会带来严重的后果，这时候呢，可能就需要空间复杂度低一些的代码。反过来，在其它的场合，可能需要其它的策略。


需要说明的一点是，由于我这个程序用的是指针来实现，而没有依赖字符串的任何特点（没有使用 strlen、strcpy、memcpy 等等），所以应该是可以移植到任何类似的数据类型中，比如链表。但是就目前而言，我还没有想到有什么其它地方能有类似的需求，所以也只是一句空话罢了。

还有一个观点需要说明，考虑到函数调用所需要的入栈、出栈的时间，所以我不习惯在循环中反复调用函数。就 isspace 而言，我虽然并不知道 isspace 内部是如何实现的（是不是又用了什么专用的指令？），但是直觉告诉我，isspace 并不会比直接比较的效率高。可能还会更低也说不定。

flw

原帖由 xiaonanln 于 2006-3-19 08:11 发表
楼主的程序在复制每一个字符时都要做至少一个比较，我觉得性能应该不如先确定两头，然后复制中间的算法

问题是，什么叫“两头”？你怎么知道“两头”？

flw

其实就这个问题来讲，57 楼之前已经把所有的细节都讨论清楚了，
当然了，这主要是因为这个帖子发表的时候，
前面还有几篇帖子已经较深入地讨论过这个问题了。

从 57 楼开始，水平就直接下降。
很多人开始讨论一楼的函数是否正确，再或者莫名其妙地附上自己的程序（不知目的何在？）
基本上可以说，从 57 楼开始，这个帖子就只剩下娱乐意义，而失去学术意义了。