Chinaunix首页 | 论坛 | 博客
  • 博客访问: 990056
  • 博文数量: 102
  • 博客积分: 10120
  • 博客等级: 上将
  • 技术积分: 2754
  • 用 户 组: 普通用户
  • 注册时间: 2006-09-13 23:00
文章分类

全部博文(102)

文章存档

2011年(6)

2010年(55)

2009年(16)

2008年(25)

分类: C/C++

2008-09-09 15:40:05

这道题其实在《程序员面试攻略》上有,有两种解法,前一种比较常规,后一种比较优雅。我在做这道题的时候,还没有看到《程序员面试攻略》上的解法,因此采用的是常规思路。在gcc和mingw下测试过,帖出来权当是抛砖引玉,以后自己想重温一下也好找。

/*
 * reverse sentence word by word.
 * $Id$
 */


#include <stdio.h>
#include <stdlib.h>
#include <strings.h>


#if !defined(isblank)
static __inline__ int isblank(char c)
{
    if (c == ' ' || c == '\t')
        return (1);
    else
        return (0);
}
#endif


/*
 * Implement a function to reverse a sentence word by word in C language,
 * for example, reverse the sentence "we are good student"
 * to "student good are we"
 *
 * input:    'str', the string to be reversed, must be mutable, since
        reversed string will be stored in.
 * return:    a pointer to the reversed string.
 * NOTE:     1. 'str' must be mutable, say, it must be a char array;
 *        2. punctuation will be treated as non-blank characters.
 */

char * reverseSentenceByWords(char * str)
{
    int     len;
    char * tStr;
    char * p;
    char * q;
    
    /*
     * validate and handle special cases
     */

    if (!str)
        return (NULL);
    
    if ((len = strlen(str)) == 0)
        return (str);

    tStr = (char *)malloc((len + 1) * sizeof(char));
    if (!tStr)
        return (NULL);
    
    /*
     * parse and reverse, word by word, from end to beginning
     */

    memset(tStr, 0, len + 1);
    p = str + len - 1;
    q = tStr;
    while (1) {

        /*
         * split out blank substring and duplicate the
         * substring to proper position of tStr
         */

        if ((p >= str) && isblank(*p)) {
            for (;(p > str) && isblank(*p); p--)
                ;
         if (p == str) {
             strcpy(q, p);
             q += strlen(p);
                break;
         } else {
             strcpy(q, p+1);
                q += strlen(p+1);
                *(p+1) = '\0';
         }
        }
        
        /*
         * split out non-blank substring and duplicate
         * it to proper position of tStr
         */

        if ((p >= str) && (! isblank(*p))) {
            for (;(p > str) && (! isblank(*p)); p--)
                ;
         if (p == str) {
             strcpy(q, p);
             q += strlen(p);
                break;
         } else {
                strcpy(q, p+1);
                q += strlen(p+1);
                *(p+1) = '\0';
         }
        }
    }
    
    /*
     * terminating tStr, copy back to str, and free tStr
     */

    *(q+1) = '\0';
    strcpy(str, tStr);
    free(tStr);

    return (str);
}

阅读(1795) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~