通过递归反转字符串中的单词

Question

我正在尝试编写一个C函数，接受一个字符串，返回一个新的反转单词顺序后的字符串。例如，输入"How are you"应该返回"you are How"。以下是我的尝试：

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

char *reverseWords(char *str, char *ac)
{
    if (!ac)
    {
        ac = malloc(strlen(str) + 1);
        ac[0] = '\0';
    }

    char *word = strtok(str, " ");
    if (!word)
    {
        return ac;
    }
    reverseWords(NULL, ac);
    strcat(ac, word);
    //strcat(ac, " ");
}

int main()
{
    char s[] = "How are you";
    char *reversed = reverseWords(s, NULL);
    printf("%s\n", reversed);
}

之前的代码输出结果是："youareHow"，看起来思路是正确的，只是缺少了空格。如果我尝试取消函数中最后一行的注释，就没有任何输出。那么这是怎么回事呢？我无法理解为什么它没有起作用。

- Youssef13

---

我简直不敢相信这个函数没有发出警告，提醒你所有的代码路径都需要提供一个肯定的返回值。 - WhozCraig

我经常把这个作为面试问题！别忘了释放你的内存分配… - Edd Inglis

“该函数将始终返回一个值。” - 真的吗？当结果 strtok 不为空时它会返回什么？嗯... - WhozCraig

是的，我的断言不正确 :)。你必须在函数中单词之间添加一个空格，因为strtok删除了空格。在strcat(ac, word);之后添加strcat(ac, " ");...此外最好使用return ac终止函数（需要验证）。 - Sir Jo Black

如果需求规定字符串不能被修改，则动态分配是您唯一的选择。但如果可以就地修改字符串，则可以使用反向划分来实现此目的。可以在这里看到一个示例。 - WhozCraig

Answer 1

您忽略了reverseWords的返回值。我认为这没关系，因为您已经引用了ac。

在reverseWords函数的末尾，您没有返回保存拼接字符串的ac。

现在您需要取消注释strcat(ac, " ");，以便将空格添加到返回值中。

现在返回值将具有带有空格的反转字符串。

您忘记释放已分配的字符串。

- Shubham

---

仍然对我不起作用： https://onlinegdb.com/H1NtG3qoS 现在即使在最后一行被注释和未被注释的情况下都无法工作。 - Youssef13

由于添加了返回值，链接中的代码将无法正常工作，因为strcat不会被执行。 - Youssef13

Answer 2

当您递归调用reverseWords时，您忽略了返回代码，但这并不是问题，因为更高级别的调用已经引用了ac。

但是最高级别的调用将会在函数reverseWords的末尾离开该函数，而您忘记了返回值。

当您的程序通过打印“youareHow”部分工作时，实际上观察到了未定义的行为，因为main函数显然在它期望获得返回值的地方找到了预期字符串的地址。由于该函数没有返回值，这是来自先前执行的代码中剩余的内存或寄存器中的内容。

请像这样更改您的代码：

    char *word = strtok(str, " ");
    if (!word)
    {
        return ac;
    }
    reverseWords(NULL, ac);
    strcat(ac, word);
    strcat(ac, " ");
    return ac;
}

请注意，您的代码在每个单词后面添加了一个空格。 如果您将输出更改为以下内容，则可以看到这一点：

    printf("<%s>\n", reversed);

为了解决这个问题，您可以替换

    strcat(ac, word);
    strcat(ac, " ");

使用

    if(ac[0] != '\0')
    {
        strcat(ac, " ");
    }
    strcat(ac, word);

如果ac中的现有字符串不为空，这将在每个单词之前插入一个空格。

- Bodo

---

太好了！感谢您提供的修复最后一个空格问题的提示。 :) - Youssef13

Answer 3

我添加这个内容是因为迟早我在ideone.com上支持的替代方法链接将会失效，当它失效时，人们可能会想知道我在一般评论中在说什么。

可以在不使用动态分配或使用strtok的情况下完成此任务。该方法使用一种称为“反转分区”的技术，通过执行以下操作来完成：

1. 从字符串开始到结束标记（最初作为终止符提供，但每次递归时都会减少）中找到第一个空格。如果在该段中未找到任何空格，则完成操作。 2. 反转从字符串开头到（1）中发现的分隔空格之前的片段。 3. 反转整个序列从开头到结束标记。 4. 反转从字符串开头到移动片段之前的空格之前的位置的片段。 5. 使用不包括刚刚移动的数据及其前导空格的段进行递归。

就是这样。现在看看它与数据一起使用：

step 1,2. reverse the target sequence
"abc 123 xyz" ==> "cba 123 xyz"
 ^^^               ^^^

step 3. Reverse the entire sequence
"cba 123 xyz" ==> "zyx 321 abc"

step 3 Reverse the non-target sequence, not including the trailing space
"zyx 321 abc" => "123 xyz abc"
 ^^^^^^^           ^^^^^^^

对于非目标片段，重复执行此操作（递归或迭代均可），调整结束标记。第二次遍历应如下所示，注意结束标记*位于示例上方:

        *                *
"123 xyz abc" => "321 xyz abc"
 ^^^              ^^^

        *                *
"321 xyz abc" => "zyx 123 abc"
 ^^^^^^^          ^^^^^^^

        *                *
"zyx 123 abc" => "xyz 123 abc"
 ^^^              ^^^

一旦完成此步骤，请再次递归。现在，简介看起来像这样：

    *
"xyz 123 abc"

请注意，开始字符串和结束标记之间没有空格，所以我们完成了（如果你错过了）。

---

代码

实现这个功能的代码很简单，只是指针操作需要仔细理解。以下是代码：

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

void reverse_letters(char *beg, char *end)
{
    while (beg < --end)
    {
        char tmp = *beg;
        *beg++ = *end;
        *end = tmp;
    }
}

char *reverse_words(char *beg, char *end)
{
    // find whitespace. if none then we're done.
    char *p = beg;
    for (; p != end && !isspace((unsigned char)*p); ++p);

    if (p != end)
    {
        reverse_letters(beg, p);
        reverse_letters(beg, end);
        reverse_letters(beg, beg + (end - p - 1));
        reverse_words(beg, beg + (end - p - 1));
    }

    return beg;
}

int main()
{
    char words[] = "abc 123 xyz";
    reverse_words(words, words + strlen(words));
    puts(words);
    return 0;
}

输出

xyz 123 abc

显然，这是尾递归的极致，因此将其改为迭代解决方案将变得非常简单，这部分留给读者自己练习。

- WhozCraig