アルゴリズムを細かく分析します。最初に、ヌル文字ターミネータを含まない文字列の長さを見つけます。これは正しいですが、単純化できます。
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++ 拡張機能であり、非標準であるため、不要であり、使用すべきではありません) は、終端の null-char を考慮したり、設定したりしません。
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.
繰り返しますが、これはまったく問題なくインプレースで実行できます。そのようなアルゴリズムの 1 つが次のようになります (実際の単語を逆にするループは、偶然にも、バッファー全体を逆にするのと同じアルゴリズムではないことに注意してください)。
// 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