11

strcpyあるインタビューで、重複する文字列を適切に処理できるように の実装を作成し、修正するように依頼されました。私の実装は以下のとおりで、非常に素朴です。次のように修正するにはどうすればよいですか。

  1. 重なっている文字列を検出し、
  2. 検出後、オーバーラップをどのように処理して続行しますか?
char* my_strcpy(char *a, char *b) {

     if (a == NULL || b == NULL) {
         return NULL;
     }
     if (a > b) {
         //we have an overlap?
         return NULL;
     }
     char *n = a;

     while (*b != '\0') {
         *a = *b;
         a++;
         b++;
     }
     *a = '\0';
     return n;
}

int main(int argc, char *argv[])
{
    char str1[] = "wazzupdude";
    char *after_cpy = my_strcpy(str1 + 2, str1);
    return 0;
}

編集：

したがって、 @Secureの回答に基づく1つの可能な実装は次のとおりです。

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    memmove(a, b, strlen(b) + 1);
    return a;
}

に依存しない場合memmove、

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    if (a == b) {
        return a;
    }

    // case1: b is placed further in the memory
    if ( a <= b && a + strlen(a) > b ) {
        char *n = a;

        while(*b != '\0') {
            *a = *b;
            a++; b++;
        }
        *a = '\0';
        return n;
    }

    // case 2: a is further in memory
    else if ( b <= a && b + strlen(b) > a ) { 
        char *src = b + strlen(b) - 1; // src points to end of b
        char *dest = a;

        while(src != b) {
            *dest = *src;
            dest--; src--;  // not sure about this..
        }
        *a = '\0';
        return a;
    }
}
4

9 に答える 9

12

これを検出する移植可能な方法はありません。ポインター比較を行う必要があり、これらは同じオブジェクト内でのみ定義されます。つまり、2 つの文字列が重複しておらず、実際には異なるオブジェクトである場合、ポインターの比較によって未定義の動作が発生します。

を使用して、標準ライブラリにこれを処理させmemmove(a, b, strlen(b) + 1)ます。

編集：

コメントで Steve Jessop が指摘したように、実際には、この場合、重複を検出するための移植可能なが遅い方法があります。b 内の各アドレスを a の最初と最後のアドレスと比較して、等しいかどうかを確認します。との等価比較==は常に明確に定義されています。

したがって、次のようなものがあります。

l = strlen(b);
isoverlap = 0;
for (i = 0; i <= l; i++)
{
    if ((b + i == a) || (b + i == a + l))        
    {
        isoverlap = 1;
        break;
    }
}

編集 2: ケース 2 の可視化

次の配列とポインターのようなものがあります。

S t r i n g 0 _ _ _ _ _ _ _
^       ^
|       |
b       a

b + strlen(b)終端の \0 へのポインターになることに注意してください。1 つ遅れて開始します。そうしないと、エッジ ケースの追加処理が必要になります。そこにポインターを設定することは有効ですが、逆参照することはできません。

src = b + strlen(b) + 1;
dst = a + strlen(b) + 1;

S t r i n g 0 _ _ _ _ _ _ _
^       ^     ^       ^  
|       |     |       |
b       a     src     dst

\0 もコピーするコピー ループ。

while (src > b)
{
    src--; dst--;
    *dst = *src;
}

最初のステップはこれを与えます：

src--; dst--;

S t r i n g 0 _ _ _ _ _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

*dst = *src;

S t r i n g 0 _ _ _ 0 _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

等々、src最終的に と等しくなるまでb:

S t r i S t r i n g 0 _ _ _
^       ^              
|       |            
b       a          
src     dst

もう少しハックしたい場合は、さらに圧縮することもできますが、これはお勧めしません。

while (src > b)
    *(--dst) = *(--src);
于 2011-09-15T08:15:43.937 に答える
4

注: ここで、bはソース文字列aのアドレスで、 は宛先のアドレスです。

あなたa > bとは必ずしも重複するわけではありません。もしも

(a <= b && a+strlen(a) >= b) || (b <= a && b+strlen(b) >= a)

次に、オーバーラップがあります。

ただし、インタビューのためにオーバーラップを検出する以外に、 に対してa > bはうまくいくはずですstrcpy。アイデアは次のとおりです。

bをさらにメモリ ( ) に配置すると、通常はにb > aコピーできます。の一部が上書きされますが、既にその部分を過ぎています。bab

aがメモリ ( a > b)のさらに先に配置されている場合は、おそらくの最初の場所に書き込むことによって、より高いインデックスでaの場所を既に上書きしていることを意味します。bこのような場合は、反対方向にコピーする必要があります。したがって、 index0からにコピーする代わりに、 からにコピーstrlen(b)-1する必要があります。strlen(b)-10

それがどのように役立つか混乱している場合は、2 つの重なり合う配列を紙に描き、配列の最初から 1 回、最後から 1 回コピーしてみてください。a > bケースとの両方で重複する配列でこれを試してくださいa < b。

a == bの場合、実際に何もコピーする必要はなく、単に戻ることができることに注意してください。

編集:よくわかりませんが、他のソリューションを読むと、この回答は完全に移植可能ではないようです。そのことに注意してください。

于 2011-09-15T08:23:09.573 に答える
4

文字列が重複することが予想される場合は、おそらく memmove() を使用できます。

char* my_strcpy(char *a, char *b)
{
    memmove(a, b, strlen(b) + 1);
    return a;
}
于 2011-09-15T08:16:26.120 に答える
3 
if a > b; then
    copy a from the beginning
else if a < b; then
    copy a from the ending
else // a == b
    do nothing

の実装を参照できますmemmove。これは、私が言ったこととまったく同じです。

于 2011-09-15T08:14:56.693 に答える
1

私は最近のインタビューでこれを尋ねられました。オーバーラップを「検出」する必要はありません。strcpy重複するアドレスが処理されるように書くことができます。重要なのは、ソース文字列の最初からではなく、最後からコピーすることです。

これが簡単なコードです。

void str_copy(const char *src, char *dst) 
{
    /* error checks */

    int i = strlen(a); /* may have to account for null character */

    while(i >= 0) 
    {
        dst[i] = src[i];  
        i--; 
    }
}

編集：これは、a<bの場合にのみ機能します。> bの場合、最初からコピーします。

于 2011-09-15T08:18:29.127 に答える
1

これらの 2 つの文字列が重複している場合、コピー中に元の文字列aまたはbポインターを超えてしまいます。

strcpy( a, b ) が a <- b を大まかに意味すると仮定すると、つまり、最初のパラメーターがコピーの宛先である場合、コピー ポインターがbの位置に到達するかどうかのみを確認します。

元の位置を保存するだけbでよく、コピー中に元の位置に到達していないことを確認してください。また、その位置に到達した場合は、末尾のゼロを書き込まないでください。

 char* my_strcpy(char *a, const char *b)
 {

    if ( a == NULL
      || b == NULL )
    {
        return NULL;
    }

    char *n = a;
    const char * oldB = b;

    while( *b != '\0'
       &&  a != oldB )
    {
        *a = *b;
        a++;
        b++;
    }

    if ( a != oldB ) {
        *a = '\0';
    }

    return n;
 }

このアルゴリズムは、コピーを停止するだけです。エラー状態をマークしたり、文字列の終わりマークを前の位置に追加したりするなど、何か他のことをしたいかもしれません (ただし、(アルゴリズムが現時点で行っているように) 黙って失敗することは最善の選択肢ではありません)。

お役に立てれば。

于 2011-09-15T08:24:21.247 に答える
1 
if (a>= b && a <= b+strlen(b))) || (b+strlen(b) >= a && b+strlen(b) <= a + strlen(b))

(*) パフォーマンスを向上させるために strlen(b) をキャッシュする必要があります

機能: [a のアドレス + 余分な len バイト] が文字列内にあるかどうか、または[a のアドレス] が文字列内にある
かどうかをチェックします。これらは文字列が重複する唯一の可能性です。a+lena

于 2011-09-15T08:17:06.603 に答える