如何在不使用内置函数的情况下颠倒句子中的单词？

问题描述 投票：0回答：6

这是面试问题：

如何将 

Dogs like cats
转换为 
cats like Dogs
 ?

我的代码显示：

cats like cats
。我哪里出错了？

#include <iostream>
using namespace std;

int main()
{
    char sentence[] = ("dogs like cats");
    cout << sentence << endl;

    int len = 0;

    for (int i = 0; sentence[i] != '\0'; i++)
    {
        len++;
    }
    cout << len << endl;

    char reverse[len];
    int k = 0;

    for (int j = len - 1; j >= 0; j--)
    {
        reverse[k] = sentence[j];
        k++;
    }

    cout << reverse << endl;

    int words = 0;
    char str[len];

    for (int l = 0; reverse[l] != '\0'; l++)
    {
        if (reverse[l] == ' ' || reverse[l] == '\0') // not sure about this part
        {
            for (int m = l; m >= 0; m--)
            {
                str[words] = reverse[m];
                words++;
            }
        }
    }

    cout << str;

    return 0;
}

我知道你可以使用指针、堆栈、向量来做到这一点......但面试官对此不感兴趣！

c++ arrays reverse sentence
6个回答
4
投票

这是示例代码的固定版本：

  • 您的主要问题是，每次找到 and 
    ' '
    或 
    '\0'
    时，您都会将反向字符串的字节从开头复制到该点。在 
    loop 5
    中的示例，您以相反的顺序从索引 0-5 (
    stac
    ) 从 
    reverse
    复制到 
    str
    ，但在 
    loop 10
    中，您从索引 0-10 (
    stac ekil
    ) 从 
    reverse 复制
    到 
    str
    以相反的顺序，直到这里您已经打印了结果字符串（'cats like cats'），并且在 
    loop 15
    中相同，所有这些都增加了 
    str
    的索引，在最后一个循环中，您是写入通过 
    str
    有效内存的末尾（因此不会打印为输出）。
  • 您需要跟踪最后一个单词何时反转，以仅反转实际单词，而不是从开头到实际索引的字符串。
  • 您不想在单词反转中计算特殊字符（' ' 和 ' '），您将以 
    cats like\0dogs
    • 结尾

提供修改后的示例代码：

#include <iostream>
using namespace std;

int main() {
    char sentence[] = ("dogs like cats");
    cout << sentence << endl;

    int len = 0;

    for (int i = 0; sentence[i] != '\0'; i++) {
        len++;
    }
    cout << len << endl;

    char reverse[len];
    int k = 0;

    for (int j = len - 1; j >= 0; j--) {
        reverse[k] = sentence[j];
        k++;
    }

    cout << reverse << endl;

    int words = 0;
    char str[len];

    // change here added last_l to track the end of the last word reversed, moved
    // the check of the end condition to the end of loop body for handling the \0
    // case
    for (int l = 0, last_l = 0; ; l++) {
        if (reverse[l] == ' ' || reverse[l] == '\0')
        {
            for (int m = l - 1; m >= last_l; m--) { // change here, using last_t to
                str[words] = reverse[m];            // only reverse the last word
                words++;                            // without the split character
            }
            last_l = l + 1;                         // update the end of the last
                                                    // word reversed
            str[words] = reverse[l];                // copy the split character
            words++;
        }
        if (reverse[l] == '\0')                     // break the loop
            break;
    }

    cout << str << endl;

    return 0;
}

一些代码是在限制使用该语言最简单的功能的情况下编写的。

#include <iostream>

// reverse any block of text.
void reverse(char* left, char* right) {
    while (left < right) {
        char tmp = *left;
        *left = *right;
        *right = tmp;

        left++;
        right--;
    }
}

int main() {
    char sentence[] = "dogs like cats";
    std::cout << sentence << std::endl;

    // The same length calculation as sample code.
    int len = 0;
    for (int i = 0; sentence[i] != '\0'; i++) {
        len++;
    }
    std::cout << len << std::endl;

    // reverse all the text (ex: 'stac ekil sgod')
    reverse(sentence, sentence + len - 1);

    // reverse word by word.
    char* end = sentence;
    char* begin = sentence;
    while (end < sentence + len) {
        if (*end != ' ')
            end++;

        if (end == sentence + len || *end == ' ') {
            reverse(begin, end - 1);
            begin = end + 1;
            end = begin;
        }
    }

    std::cout << sentence << std::endl;

    return 0;
}
2
投票

分解你的算法。首先，找到字符串的长度，不包括空字符终止符。这是正确的，但可以简化。

size_t len = 0;
for (int i = 0; sentence[i] != '\0'; i++) {
    len++;
}
cout << len << endl;

这可以很容易地写成：

size_t len = 0;
while (sentence[len])
    ++len;

接下来，反转整个字符串，但第一个缺陷出现。您在此处声明的 VLA（可变长度数组）（您不需要也不应该使用它，因为它是 C++ 扩展且非标准）不考虑也不设置终止空字符。

char reverse[len]; // !! should be len+1
int k = 0;
for (int j = len - 1; j >= 0; j--) {
    reverse[k] = sentence[j];
    k++;
}
// !! Should have reverse[k] = 0; here.
cout << reverse << endl; // !! Undefined-behavior. no terminator.

这个临时缓冲区字符串是根本不需要的。您没有理由不能就地完成整个操作。一旦我们正确计算 

len
，您只需执行类似以下操作即可反转整个序列，从而将空字符终止符保留在正确的位置：

// reverse entire sequence
int i = 0, j = len;
while (i < j--)
{
    char c = sentence[i];
    sentence[i++] = sentence[j];
    sentence[j] = c;
}

接下来我们将转向尝试反转每个内部单词的位置。同样，就像以前一样，缓冲区长度不正确。应该是

len+1
。更糟糕的是（很难想象），当你找到单词的结束点时，你永远不会记得你“离开”的地方。该位置应该是您开始检查并跳过空格的“下一个”点。在不保留的情况下，您可以从当前点一直复制到字符串的开头。这基本上将 cats 炸毁于 dogs。
int words = 0; char str[len]; // !! should be len+1 for (int l = 0; reverse[l] != '\0'; l++) { if (reverse[l] == ' ' || reverse[l] == '\0') // not sure about this part { for (int m = l; m >= 0; m--) { str[words] = reverse[m]; words++; } } } cout << str; //!! Undefined behavior. non-terminated string.
再一次，这可以毫无困难地就地完成。一种这样的算法如下所示（请注意，反转实际单词的循环与反转整个缓冲区的算法并非巧合相同）：

// walk again, reversing each word.
i = 0;
while (sentence[i])
{
    // skip ws; root 'i' at beginning of word
    while (sentence[i] == ' ') // or use std::isspace(sentence[i])
        ++i;

    // skip until ws or eos; root 'j' at one-past end of word
    j = i;
    while (sentence[j] && sentence[j] != ' ') // or use !std::isspace(sentence[j])
        ++j;

    // remember the last position
    size_t last = j;

    // same reversal algorithm we had before
    while (i < j--)
    {
        char c = sentence[i];
        sentence[i++] = sentence[j];
        sentence[j] = c;
    }

    // start at the termination point where we last stopped
    i = last;
}


将它们放在一起

虽然使用指针比所有这些索引变量要简单得多，但以下内容将就地完成您正在尝试的操作。 #include <iostream> int main() { char s[] = "dogs like cats"; std::cout << s << '\n'; size_t len = 0, i, j; while (s[len]) ++len; // reverse entire sequence i = 0, j = len; while (i < j--) { char c = s[i]; // or use std::swap s[i++] = s[j]; s[j] = c; } // walk again, reversing each word. i = 0; while (s[i]) { // skip ws; root 'i' at beginning of word while (s[i] == ' ') // or use std::isspace ++i; // skip until ws or eos; root 'j' at one-past end of word j = i; while (s[j] && s[j] != ' ') // or use !std::isspace ++j; // remember the last position size_t last = j; while (i < j--) { char c = s[i]; // or use std::swap s[i++] = s[j]; s[j] = c; } // start at last-left posiion i = last; } std::cout << s << '\n'; return 0; }

输出



dogs like cats
cats like dogs

    



我的建议是将原始字符串分解为单词数组，然后反转该数组。然后将这些单词添加到您的倒装句中，中间留一个空格。

    

    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        


因为他们没有要求任何库，所以我假设没有
std::string

    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        
vectors
，什么都没有，所以我用C编写了它。唯一使用的是
printf
。其他一切都是从头开始:l


这个想法是先反转数组。然后按空格分割数组并反转每个单词。


示例：
http://ideone.com/io6Bh9



代码：

#include <stdio.h>

int strlen(const char* s)
{
    int l = 0;
    while (*s++) ++l;
    return l;
}


void reverse(char* str)
{
    int i = 0, j = strlen(str) - 1;

    for(; i < j; ++i, --j)
    {
       str[i] ^= str[j];
       str[j] ^= str[i];
       str[i] ^= str[j];
    }
}

void nulltok(char* str, char tok, int* parts)
{
    int i = 0, len = strlen(str);
    *parts = 1;

    for (; i < len; ++i)
    {
        if (str[i] == tok)
        {
            str[i] = '\0';
            ++(*parts);
        }
    }
}

char* reverse_sentence(char* str)
{
    char* tmp = str;
    reverse(str);

    int i = 0, parts = 0, len = strlen(str);
    nulltok(str, 0x20, &parts);

    while(parts--)
    {
        reverse(str);
        str += strlen(str) + 1;
    }

    for(; i < len; ++i)
        if (tmp[i] == '\0')
            tmp[i] = 0x20;

    return tmp;
}


int main(void)
{
    char str[] = "dogs like cats";
    printf("%s", reverse_sentence(str));

    return 0;
}


    




我的解决方案




    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        



}

    


我的解决方案



    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        


}

    



    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.