Question

如何去掉字符串或变量里的空格

Answer 1

这是今天无意看到的一个字符串处理小问题。详细点说，假设有这么一个字符串char str[]=" hello world !! ! "现在需要实现一个算法ClearSpace来去除这个字符串中的所有空格。即最后的str应为"helloworld!!!"函数声明如下void ClearSpace(char *str)要求：不用其他变量，只能用形参str。也不准用正则表达式。其实这个算法还有些深度。不用些巧妙的方法似乎很难解决。刚刚拿到这个问题的时候，大部分人都会这么思考：要去掉空格，就是找到空格的位置，然后将后面的字符整体往前移动以填补这些个空格。但是关键在于只能用str这一个指针变量。如何办到呢？首先可以试试一般思路，如果用三个左右的变量这个问题将会非常容易解决，因为我们需要一些标志指针，记住某些位置。比如说：定位到第一个空格的位置，将其指针保存到p中，然后在找到p后面第一个不为空格的字符，将其指针保存到q，以p为起点，来个整体移动，便可将p和q之间的空格消灭。目前的状况只有一个指针str，还是用上面的思路的话将无解。第一个思路实则可以给我们些提示，就是说，我们需要“记忆”，什么“记忆”？不论如何，我们需要知道两个信息，一个从哪儿开始移动，二是移到哪儿。显然，一个str变量是做不到这一点的，但是我们可以借用c语言的特性来完成这项工作。那这个特性究竟是什么呢？没错，就是递归！递归实际上就是利用栈的特性解决问题，而栈是由系统内部处理的，并且具有“记忆”的特性，所以很适合这个算法。当然上述分析只是一个感性些的认识，不是说，这类问题就一定要用栈或者递归来解决。好了，我们决定用递归完成这个算法，但是具体怎么做呢？去除字符串的问题实际上是一个递归的过程。何解？首次调用ClearSpace函数的时候，实际上就表明了我们解决问题的对象是以str为开头的字符串。这是最开始的母串，源串。那么划分下去，还有众多的小问题。也就是说，我们将递归的解决子串的问题。子串是相互嵌套的关系。首先，定位到第一个空格的位置，然后递归的解决后续的各个子串的去除空格的问题。之后，再把后面已经去除空格的子串整体往前移动一个位子，也就是填补当前的空格。根据这个思路，算法描述如下：void ClearSpace(char* str){while(*str && *str++ != ' ' ); //找到第一个为空格的位置str
if( !*str ) return ; //如果到了字符串尾，返回
else ClearSpace(str); //否则就是找到了为空格的位置。接着，从该空格的后一位置起，递归的去除空格
while( (*(str-1) = *str++)!='\0' ); //str后续的空格解决ok了，还要将后续的子串往前移动一格，以填补当前空格str
}这个算法实现效率并不算高，递归的大量调用不仅本身会耗费时间，而且也会耗费栈空间，另外，频繁的移动字符也是不可避免。但是至少给出了一种实现吧。由此看来，递归的思路无处不在，哪怕是遇到这类很小的问题。往往，我们要么不知道去利用递归解决问题，要么不会实现具体的递归。在常用的各种搜索，回溯法，分治法等算法中，递归可谓是最重要的一环，所以即便递归会耗费时间空间，但对于简化解决问题的思路而言是具有重大作用的。要学算法，先学好递归！也许这个主题已经有人探讨过，或大家还能给出更好的方案。不过我相信肯定还有些和我一样的初学者并未接触过这个问题，所以写此文，以飨同我一样的初学者。