题目描述

给你一个英语的语句，比如”London bridge is falling down”，把它完全倒装过来，”down falling is bridge London”，如何不使用额外的存储空间完成这个倒装过程？
常学习计算机算法的人在解决这个问题时，首先会想到把这个句子切割成一个个单词，然后把它们存到一个数组里，把这个数组顺序存入，逆序取出来就可以完成语句倒装的问题。但是，这种算法要额外地使用存储空间，因此不符合题目的要求。

我们可以考虑这样解决问题：
第一步，先将整个句子看成是一个完整的字符串，以字母为单位头尾对调，这样上面的句子就变成了下面这样一个乱七八糟的字符串：
“nwod gnillaf si egdirb nodnoL”
第二步，把用空格分割的每一个字串以字母为单位，头尾对调。比如第一个字串是nwod，头尾对调后是down，也就是原来句子中的最后一个单词。第二个字串是gnillaf，字母头尾对调后是falling，原来句子中倒数第二个单词。这样一个个地做，直到最后一个字串里的字母对调完毕。这样就得到了下面的倒装句子：
“down falling is bridge London.”

基本思路

题目中已经给出了诱导式的方法：需要造两个轮子：句子倒置和单词倒置。

  • 单词倒置比较容易，可以在首尾各添一个指针逐渐向中间靠拢，每次两个指针各自指向的元素互换，从而达到倒置效果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void Word(char* start, char* end) {
        while (start < end) {
            char temp = *start;
            *start = *end;
            *end = temp;
            start++;
            end--;
        }
    }

  • 句子倒置也不算特别复杂，其根本原理是首先把整个句子倒置，再把句子拆分成为单词，以空格为分界，将每个单词再次倒置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void Sentence(char* sentence) {
        int length = strlen(sentence);
        char* start = sentence;
        Word(sentence, sentence + length - 1);
        for (int i = 0; i <=length; i++) {
            if (sentence[i] == ' ' || sentence[i] == '\0') {
                Word(start, sentence + i - 1);
                start = sentence + i + 1;
            }
        }
    }

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <string.h>

void Word(char* start, char* end) {
    while (start < end) {
        char temp = *start;
        *start = *end;
        *end = temp;
        start++;
        end--;
    }
}

void Sentence(char* sentence) {
    int length = strlen(sentence);
    char* start = sentence;
    Word(sentence, sentence + length - 1);
    for (int i = 0; i <=length; i++) {
        if (sentence[i] == ' ' || sentence[i] == '\0') {
            Word(start, sentence + i - 1);
            start = sentence + i + 1;
        }
    }
}
void input(char* string) {
    int i = 0;
    char c;
    while (1) {
        scanf("%c", &c);
        if (c == '\n' || c == EOF) {
            break;
        }
        string[i] = c;
        i++;
    }
    string[i] = '\0';
}
int main() {
    char sentence[] = "London bridge is falling down";
    printf("Original sentence: %s\n", sentence);
    Sentence(sentence);
    printf("Reversed sentence: %s\n", sentence);
//    char string[100]={};
//    input(string);
//    Sentence(string);
//    printf("%s",string);
//    这个是可以自己输入字符串的倒置程序
    return 0;
}

​