如何在不使用额外数组或字符串的情况下交换字符串中的两个单词？

限制条件 #

• 禁止使用额外数组或字符串（教授指定规则）
• 需求示例：输入 "Apple and pear"，期望输出 "pear and Apple"

当前问题 #

我写的代码只能在两个单词长度相同时完成交换，一旦单词长度不同，逻辑就会出错。

现有代码 #

#include <stdio.h>
#include <string.h>

#define max 255
// 示例输入：pear meat
void swapWords(char* string, int start, int end){
    int nstart, nend; // 下一个单词的起始、结束下标
    int z = 0;
    char temp;
    for(int i = end + 1; string[i] != 0; i++){
        if(string[i-1] == ' '){
            nstart = i;
        }
        if(string[i+1] == 0 || string[i + 1] == ' '){
            nend = i;
            for(int j = start; j <= end; j++){
                temp = string[j];
                string[j] = string[nstart + z];
                string[nstart + z] = temp;
                z++;
            }
            
        }
    }
}

int main(){
    char string[max];
    fgets(string,max,stdin);
    
    string[strlen(string) - 1] = 0; // 移除换行符
    
    int start,end; // 每个单词的起始、结束下标
    
    for(int i = 0; string[i] != 0; i++){
        if(i == 0 || string[i-1] == ' '){
            start = i;
        }
        if(i == string[strlen(string)-1] || string[i+1] == ' '){
            end = i;
            swapWords(string, start, end);
        }
    }
    
    
    fputs(string,stdout);
}

问题分析与修正方案 #

你的代码核心问题是直接按原单词长度交换字符，当两个单词长度不同时，要么覆盖多余字符，要么无法完成完整交换。要在不使用额外空间的前提下实现任意长度单词交换，可通过三次反转操作实现：

1. 分别反转需要交换的两个单词
2. 反转两个单词及中间空格组成的整体区间
3. 再次反转这两个单词

修正后的代码示例：

#include <stdio.h>
#include <string.h>

#define max 255

// 反转字符串中[start, end]区间的字符
void reverse(char* str, int start, int end) {
    char temp;
    while (start < end) {
        temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }
}

// 找到字符串中最后一个单词的起始下标
int findLastWordStart(char* str) {
    int len = strlen(str);
    for (int i = len - 1; i >= 0; i--) {
        if (str[i] == ' ') {
            return i + 1;
        }
    }
    return 0; // 只有一个单词的情况
}

int main() {
    char string[max];
    fgets(string, max, stdin);
    int len = strlen(string);
    if (len > 0 && string[len - 1] == '\n') {
        string[len - 1] = '\0';
        len--;
    }

    // 找到第一个单词的结束下标
    int firstEnd = 0;
    while (firstEnd < len && string[firstEnd] != ' ') {
        firstEnd++;
    }
    firstEnd--; // 调整为单词最后一个字符的下标

    // 找到最后一个单词的起始和结束下标
    int lastStart = findLastWordStart(string);
    int lastEnd = len - 1;

    // 反转第一个单词
    reverse(string, 0, firstEnd);
    // 反转最后一个单词
    reverse(string, lastStart, lastEnd);
    // 反转从第一个单词开头到最后一个单词结尾的整个区间
    reverse(string, 0, lastEnd);

    fputs(string, stdout);
    return 0;
}

测试示例：输入 "Apple and pear"，输出 "pear and Apple"，无论单词长度是否相同都能正常工作。

内容的提问来源于stack exchange，提问作者Sava Majic