微软面试100题（10）：翻转句子中单词的顺序

第10题 翻转句子中单词的顺序。

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。

为简单起见，标点符号和普通字母一样处理。

例如输入“I am a student.”，则输出“student. a am I”。

这个题比较常见。写了一个自以为比较简练的实现。这个实现主要是就地反转。

这里需要注意的是因为是就地反转，那么这个字符串必须是个变量(char i[] = "abcd"，不能使用常量声明（形如 char * i= "abcd").

1.首先将这个句子反转。

2.以空格为分界，以单词为单位反转。

另外一个是利用两个栈，word栈存储单词,sentence存储句子

如果读到的不是空格，说明正在处理单词，那么入word栈。

如果读到的是空格或者'\0',那么说明单词终结，吧word中内容一一出栈再压入sentence。这就相当与在sentence栈中，保持了单词正序。接着再将空格压入sentence.

当所有字符串处理完毕后，将sentence出栈构建一个字符串。

结果就是反转后的结果。

这个题很可惜，本来应该一次过，结果最后出栈的时候本来应该是sentence--写成++, 可惜。另外头一次编译也忘记了释放两个栈的内存。

/*
 * =====================================================================================
 *
 *       Filename:  revwords.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/03/2012 09:31:26 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>



char* revwords(char* input, int len){
    char *head = input;
    char *tail = input + len -1;
    while(head<tail){
        //swap here
        *head ^=*tail;
        *tail ^=*head;
        *head ^=*tail;
        head++;
        tail--;
    }
    return input;
}

char* revsentence(const char* input, int len){
    char * sen = (char*)malloc(sizeof(char)*len + 1);
    char * word = (char*)malloc(sizeof(char)*len + 1);
    *sen = '\0';
    *word = '\0';
    while(1){
        if(*input == ' ' || *input == '\0'){
            //word --> sen
            while(*word){
                sen++;
                *sen = *word;
                word --;
            }
            if(*input == ' '){
                sen++;
                *sen = *input;
            }
            else if(*input == '\0') break;
        }
        else{
            word++;
            *word = *input;
        }
        input++;

    }
    char *result = (char*) malloc(sizeof(char) * (len + 1));
    int i = 0;
    for(;i<len+1; i++){
        result[i] = *sen;
        sen--;
    }
    free(sen);
    free(word);
    return result;
}

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    char str[] = "I am here!";
    revwords(str, sizeof(str)-1);
    char *head= str;
    int len = 0;
    while(*head){
        if(*head != ' ') len++;
        if(*head == ' ' && len>0){
            revwords(head-len, len);
            len = 0;
        }
        head++;
    }
    printf ( "result = %s\n",str );
    printf ( "-----------using stack--------------\n" );
    printf ( "%s\n", revsentence("Here I am!",sizeof("Here I am!")-1 ));

    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */