按单词反转字符串

题目要求：把字符串“I am a student”反转成为“student a am I”，不借助任何库函数。

字符串中单词顺序反转的方法有很多种，我们可以定义一个栈结构，根据栈的特性，先进后出。我们通过依次查找空格（在实际分析单词应用中这只是最简单的情况，单词之间可能直接用标点符号区分，但是使用标点符号并不意味着就是两个单词,西方世界计数方式喜欢使用三位数字加一个逗号形式比如“3,483,123”,虽然我们可以找到“,”但是不能把“3,483,123”作为三个单词来区分，应该看作一个单词。如果我们再考虑中英文等字符问题，区分单词将更加复杂，不过幸运的是，这里我们不用考虑这么复杂的情况）来区分单词，然后把每个单词依次压栈，然后再从栈中依次读出每个单词，这样实现整个字符串的单词顺序反转，但是在具体实现过程中我们不得不考虑三个问题：
1：我们要定义一个栈结构来保存每个单词，并在反转字符串的过程中要维护，管理，填充这个栈结构，我们还要为每次申请填充单词中字符数目的多少做出判断，以便动态申请空间保存这个单词，当我们使用完成后，要即使delete这个结构，防止内存泄漏。这样我们的主要精力将放在这个栈的维护上，而不是单词顺序反转上。
2：单词分析时，如果我们把直接分析出来的单词直接压栈，再输出时我们简单的在两个单词之间加空格，可能导致反转字符串和原来字符串不匹配，比如说“I am a student” a和student直接是两个空格，那么按上面的方式输出反转单词后的字符串就是“student a am I”student和a之间只有一个空格，这里可能不是很明显，如果原字符串用标点符号区分两个单词，而我们再填充空格，得到的字符串可能与原字符串真正意义的反转相差很大。比如“student a，am I”反转后为“I am a student”而不是“I am，a student”。面对这样问题，你不得不再定义一个栈结构保存两个单词的之间的关系，或者原来入栈的单词不是真正意义的单词，把空格或标点符号一并保存。
3：因为我们用栈保存反转单词数据，所以每使用完一次反转数据，栈就清空一次，下次再使用之前就必须再次分析单词，重新入栈。避免这个问题方法，可以使用数组意义的栈，即在栈中加一个索引操作，按入栈逆序索引出数据，但是不幸的是到这一步，你又不等不重新修改自己的栈结构。
综合考虑，使用栈结构，我们不得不花费过多的精力去考虑栈结构，以及使用过程中的栈维护，使用结束后，删除栈结构，防止资源泄漏。并且使用栈结构后，算法不属于“原地”算法。至少多使用字符串空间的一倍空间，在内存紧张的系统里（比如说嵌入时）这种方式是不可取的。但是这种方法并不是没有优点，优点就是：字符串（一段话）只需要遍历一遍，就可以得到反转后的字符串。
这里我们要讲解另外一种方法：使用反转字符串方法，来实现单词顺序反转。基本原理：首先我们把待反转字符串（一段话）整体反转，比如说“I am a student”反转为”tneduts a ma I”,然后再逐个单词反转，最后得到“student a am I”。使用这种方法，相对使用栈结构来说优点就是我们使用一个反转算法，代替栈结构，这个算法属于“原地”算法，不需要再申请空间，只要内存能够容纳字符串，就可以实现单词反转。缺点是：你不得不再写一个获得字符串长度的函数，并且几乎是遍历两次字符串。
下面是使用这种方法具体代码：

/************************************************************************/
// 函数名称: Ustrlen
// 输入参数: strSource,待求长度字符串；
// 输出参数: int，字符串的长度。
// 描 述: 通过判断字符’/0′来得到字符串的长度
/************************************************************************/
int Ustrlen(const char *strSource)
{
// 声明变量
int iLength(0);
// 遍历字符串，查找字符’/0′
while(*strSource++ != ‘/0′)
{
++iLength;
}
// 返回字符串的长度
return iLength;
}
/************************************************************************/
// 函数名称: _ReversalChar
// 输入参数: strSouce，待反转字符串；iStart，旋转字符串开始位置；iEnd，旋转字符串结束位置
// 输出参数: char*，反转后字符串的指针；
// 描 述: 反转iStart到字符串iEnd之间的字符串
/************************************************************************/
char* _ReversalChar(char *strSouce,int iStart,int iEnd)
{
// 反转字符串
for(;iEnd > iStart; ++iStart,–iEnd)
{
char ch;
ch = strSouce[iStart];
strSouce[iStart] = strSouce[iEnd];
strSouce[iEnd] = ch;
}
// 返回字符串指针
return strSouce;
}

/************************************************************************/
// 函数名称: ReversalChar
// 输入参数: strSource，待反转字符串
// 输出参数: char*，反转字符串后的指针
// 描 述: 按单词反转字符串
/************************************************************************/
char * ReversalChar(char *strSouce)
{
// 获取字符串的长度
int iLength = Ustrlen(strSouce);

// 反转整个字符串
_ReversalChar(strSouce,0,iLength-1);

// 声明变量（单词的开始以及结束默认从0开始）
int iStart(0),iEnd(0);

// 查找单词
// 像上面讨论的查找单词的情况，我们只需要修改这部分，就可以实现对不
// 同格式类型单词进行处理，为了更好的通用性，其实最好把查找单词这部分
// 作为单独一个函数，或者一个类来处理
for(int i = 0; i < iLength; ++i)
{
// 查找空格分割符号
if(strSouce[i] == ‘ ‘)
{
// 找到一个单词
iEnd = i-1;
// 对于只有一个字符的单词比如说（I）没有必要反转
if(iStart < iEnd)
{
// 反转单词
_ReversalChar(strSouce,iStart,iEnd);
}
// 记录下一个单词的开始位置
iStart = i+1;
}
// 特殊处理几种常见标点符号
else if(strSouce[i] == ‘!’ || strSouce[i] == ‘,’ || strSouce[i] == ‘.’)
{
iStart = i+1;
}
}
// 返回反转后的字符串
return strSouce;
}

测试上面的方法：
char ch[] =”I am a student!!”;
cout << “Source string: ” << ch << endl;
cout << “Reversal string: ” << ReversalChar(aa) << endl;
屏幕打印字符
Source string: I am a student!!
Reversal string: !!student a am I

以上代码测试环境：Windows2003＋VC7.1，如果直接在TC下使用，需要把int iStart(0)类型的变量赋值，修改为int iStart=0;类型。

解决这个问题的方法有很多，比方说可以使用二叉树来存储单词，然后采用不同方法后续遍历的方法，逆转单词顺序，通常也可以利用双向链表实现单词逆转，存在众多方法解决这种问题，这些方法本身并没有什么好坏之分，关键是如果这种算法适合我们的情况，那么这个算法就是最好的。比方说，传递给我们是一个双向链表结构的一段话，让我们逆序，那么只需要我们从后向前读取即可。
附源码：

[java] view plaincopy在CODE上查看代码片派生到我的代码片
package com.collonn.algorithm;

public class ReversalChar {
public static String reversalWord(String s) {
int len = s.length();
char[] reverChar = s.toCharArray();
int i, j;
// 反转原始字符串
for (i = 0, j = len – 1; i < j; i++, j–) {
char temp = reverChar[i];
reverChar[i] = reverChar[j];
reverChar[j] = temp;
}
int k = 0;
while (k < len) {
i = j = k;
while (j < len && reverChar[j] != ‘ ‘) {
j++;
}
k = j + 1;
j–;
// 反转字符串中的单词
for (; i < j; i++, j–) {
char temp = reverChar[i];
reverChar[i] = reverChar[j];
reverChar[j] = temp;
}
}
String reverStr = new String(reverChar);
return reverStr;
}

public static void main(String[] args) {
String s = “Here is www.msjl.net”;
// String s = “Here is”;
char[] chs = s.toCharArray();
System.out.println(reversalWord(s));
reverseWords(chs);
System.out.println(chs);
}

static void reverseWords(char[] sentence) {
// 先将整个句子反转，例如：“I am a student” => “tneduts a ma I”
reverseString(sentence, 0, sentence.length – 1);
int startIndex = 0, endIndex = 0;
int i = 0;
while (i < sentence.length) {
if (sentence[i] == ‘ ‘) {// Means the end of a word
endIndex = i – 1;
reverseString(sentence, startIndex, endIndex);
if (i + 1 < sentence.length) {
startIndex = i + 1;
endIndex = startIndex;
}
} else {
endIndex++;
if(i==sentence.length-1){//最后一个单词反转（java字符串没有结束符，所以添加判断）
reverseString(sentence, startIndex, i);
}
}
i++;

}

}

// 反转整个句子
static void reverseString(char[] str, int startIndex, int endIndex) {
int len = endIndex – startIndex + 1;
char temp;
for (int i = 0; i < len / 2; i++) {
temp = str[i + startIndex];
str[i + startIndex] = str[endIndex - i];
str[startIndex + len - i - 1] = temp;
}
}
}