微软算法题第5题

5.编写反转字符串的程序，要求优化速度、优化空间。

最简单的解法就是遍历字符串，第一个字符和最后一个交换，第二和倒数第二交换，依此类推次，即Reverse1函数。其中元素交换可以不用辅助变量，直接用异或实现，这种优化措施在嵌入式开发中经常使用，因此可修改为Reverse2函数。

void Reverse1(char *str)
{
　　int len = 0;
　　while ('\0' != str[len])
　　　　len++;

　　char temp;
　　for (int j = 0; j < len/2; j++)
　　{
　　　　temp = str[j];
　　　　str[j] = str[len-j-1];
　　　　str[len-j-1] = temp;
　　}
}

void Reverse2(char *str)
{
　　int len = 0;
　　while ('\0' != str[len])
　　　　len++;
　　for (int j = 0; j < len/2; j++)
　　{
　　　　str[j] ^= str[len-j-1];
　　　　str[len-j-1] ^= str[j];
　　　　str[j] ^= str[len-j-1];
　　}
}

void Reverse3(char *str)
{
　　char *s = str;
　　char *e = str;

　　while (*e++)
　　　　;
　　e -= 2;
　　while (s < e)
　　{
　　　　*s ^= *e;
　　　　*e ^= *s;
　　　　*s++ ^= *e--;
　　}
}

不过有人说微软的意思是 I love you 反转后是 you love I。那这就是下面的算法了。
首先将整个字符串反转，然后每个单词反转。这样简单，不过效率不高，还有优化的算法没？

void Reverse(char* pStart, char* pEnd)
{
　　while (pStart < pEnd)
　　{
　　　　*pStart ^= *pEnd;
　　　　*pEnd ^= *pStart;
　　　　*pStart++ ^= *pEnd--;
　　}
}

void ReverseString(char* str)
{
　　int length = 0;
　　while (str[length])
　　　　length++;
　　Reverse(str, str + length - 1);

　　char *p = str;
　　for (int i = 0; '\0' != *p; p++)
　　{
　　　　if ( ' ' != *p )
　　　　　　i++;
　　　　else if (i > 0)
　　　　{
　　　　　　Reverse(p - i, p - 1);
　　　　　　i = 0;
　　　　}
　　}
}

完整程序见 ：程序员讨论组