字符串 - 修改¶

翻转句子中单词的顺序¶

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。

char *revert_by_word(char *source);

思路：

原地逆序，字符串 2 边的字符逐个交换 , 再按单词逆序；
也可以先按单词逆序，再对整个句子逆序；

针对不允许临时空间的情况，也就是字符交换不用临时空间，可以使用的方法有：

异或操作
也就是 2 个整数相互交换一个道理

char a = 'a', b = 'b';
a = a + b;
b = a - b;
a = a - b;

最终示例代码：

//反转
void _reverse(char *start,char *end){
    if ((start == NULL) || (end == NULL)) return;
    while(start < end){
        char tmp = *start;
        *start = *end;
        *end = tmp;

        start++,
        end--;
    }
}

char *revert_by_word(char *source){
    char *end = source;
    char *start = source;
    if (source == NULL) return NULL;

    //end指针挪动到尾部
    while (*end != '\0') end++;
    end--;

    //先全部反转
    _reverse(start,end);

    //按单词反转
    start=end=source;
    while(*start != '\0'){
        if (*start == ' '){
            start++;
            end++;
        }else if(*end == ' ' || *end == '\0'){
            _reverse(start,end-1);
            start = end;            
        }else{
            end++;
        }
    }
    return source;
}

类似的题目还有：

不开辟用于交换数据的临时空间，如何完成字符串的逆序用 C 语言实现一个 revert 函数，它的功能是将输入的字符串在原串上倒序后返回。

替换空格¶

实现一个函数，把每个空格替换成 "%20",如输入“we are happy”,则输出“we%20are%20happy”

char *replce_blank(char *source)

主要问题是一个字符替换成 3 个字符，替换后的字符串比原串长。如果想要在原串上直接修改，就不能顺序替换。且原串的空间应该足够大，能容纳替换变长以后的字符串。如果空间不够，就要新建一块空间来保存替换的结果了。这里假设空间足够

第一遍扫描，统计空格个数 n, 替换后的字符串长度 = 原长度 +2*n
从后向前扫描字符串，挪动每个字符的位置。注意碰到空格的地方

char *replace_blank(char *source){
    int count = 0;
    char *tail = source;
    if (source == NULL) return NULL;
    while(*tail != '\0'){
        if (*tail == ' ') count++;
        tail++;
    }

    while(count){
        if(*tail != ' '){
            *(tail+2*count) = *tail;    
        }else{
            *(tail+2*count) = '0';
            *(tail+2*count-1) = '2';
            *(tail+2*count-2) = '%';
            count--;
        }
        tail--;
    }

    return source;
}

左旋转字符串¶

字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。

如把 字符串abcdef 左旋转 2 位得到 字符串cdefab 。请实现字符串左旋转的函数。要求时间对长度为 n 的字符串操作的复杂度为 O(n)，辅助内存为 O(1)。

char *left_rotate(char *str,int offset){

}

思路：我们可以 abcdef 分成两部分，ab 和 cdef，内部逆序以后，整体再次逆序，就可以得到想要的结果了。也就是跟上面的问题是同样的问题。

字符串原地压缩¶

题目描述：“abeeeeegaaaffa" 压缩为 "abe5ag3f2a"，请编程实现。

这道题需要注意： 1. 单个字符不压缩 2. 注意考虑压缩后某个字符个数是多位数 (超过 10 个) 3. 原地压缩最麻烦的地方就是数据移动

这是使用 2 个指针，一前一后，如果不相等，都往前移动一位；如果相等，后一位变为数字 2，且移动后面的指针一位，任然相等则数字加 1，不相等

char *compress(const char *src,char *dest){

}

上面的压缩算法可以看到，压缩算法的 效率 验证依赖 给定字符串的特性，如果 'aaaaaaaa....aaa' 这样特征的字符串，使用上面的压缩算法，压缩率接近 100%，相反，可能会的 0% 的压缩率。

编写 strcpy 函数¶

已知 strcpy 函数的原型是：

char *strcpy(char *strDest, const char *strSrc);

其中 strDest 是目的字符串，strSrc 是源字符串。不调用 C++/C 的字符串库函数