1

これが私が解決しようとしている質問ですが、より簡単な方法がわかりません:-

文字列 s2 の任意の文字に一致する s1 の各文字を削除する関数 squeez を作成します。

私がこれまでに行ったことは、次のコードです:-

#include<stdio.h>
#include<string.h>
char *mysqueeze(char *a, char *b);
int main(void)
{
    int j = 0;
    char s1[100] = "krishna";
    char s2[100] = "kareem";
    char real[100];
    char *t = mysqueeze(s1,s2);
    for (int i = 0; i <= strlen(t); i++)  //1
        if (t[i] != '*')
    real[j++] = t[i];
    real[j] = '\0';        //4

    printf("%s\n", real);
}

char *mysqueeze(char *a, char *b)
{
    int i = 0, k;
    do
    {
        k = 0;
        while (b[k] != '\0')
        {
            if (a[i] == b[k]) {
                a[i] = '*';
                break;
            }
            k++;
        }
        i++;
    }
    while (a[i]);
    return a;
}

このコードを改善するにはどうすればよいですか?コードのループ部分に 1 から 4 を移動するにはどうすればよいですか?

4

2 に答える 2

1

これが宿題の質問に答えていないことを願っていますが、たとえそうであったとしても、あなたはすでに実用的な解決策を持っているので、技術的には誰の宿題もしていないと思います.

以下の私のソリューションは両方とも、その場で折りたたむアルゴリズムを実装しています。これは、問題に適用できる場合、確かに最も効率的なアプローチです。問題が別のバッファーへの折りたたみソリューションを必要とする場合、必要な変更は最小限ですみます。Paul Griffiths が彼のソリューションで述べたように、最も効率的なソリューション (大規模な干し草の山) には、ニードル ブールのルックアップ テーブルを事前に計算することが含まれます。以下にそのようなソリューションを実装しましたmysqueeze3()。同じ針のセットを繰り返し使用する場合は、関数を 2 つの別個の関数に分割し、1 つは針配列を初期化する方がよいことに注意してくださいmysqueeze。文字列へのポインタ。

ソリューションを実装する際には、繰り返される針文字が正しく処理されることを確認する必要があります。これをテストするために、干し草の山文字列を 4 つの同一文字のシーケンスに拡張しました。元の投稿のソリューションは、このケースを正しく処理します。私のソリューションは両方とも、そのケースを正しく処理します。

mysqueeze3()は よりも効率的ですがmysqueeze2()、前者は一般的な解決策ではありませんが、後者は一般的な解決策であることに注意してください。ルックアップ テーブルのソリューションはchar、サイズが 8 ビット (またはそれ以下) であることに依存します。つまり、最大 256 個の針の値があります。システムの が 9 ビット以上の場合char、そのソリューションをそれに応じて変更する必要があります。またchar、システムの a が 16 ビット以上 (おそらくユニコード!) の場合、ルックアップ テーブル ソリューションは実用的ではなくなります。

#include<stdio.h>
#include<string.h>
typedef enum {false=0, true=1} bool;
char *mysqueeze(char *a, char *b);
char *mysqueeze2(char *haystack, const char *needles);
char *mysqueeze3(char *haystack, const char *needles);
void mysqueeze_griffiths(const char * first, const char * second, char * result);

int main(void)
{
    int j = 0;
    char s1[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s2[100] = "kareem";
    char real[100];
    char *t = mysqueeze(s1,s2);
    for (int i = 0; i <= strlen(t); i++)  //1
        if (t[i] != '*')
           real[j++] = t[i];
    real[j] = '\0';        //4

    printf("mysqueeze:           %s\n", real);

    char s3[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s4[100] = "kareem";
    printf("mysqueeze2:          %s\n", mysqueeze2(s3,s4));

    char s5[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s6[100] = "kareem";
    printf("mysqueeze3:          %s\n", mysqueeze3(s5,s6));

    char s7[100] = "kkkkrrrriiiisssshhhhnnnnaaaa";
    char s8[100] = "kareem";
    char result[100];
    mysqueeze_griffiths(s7,s8, result);
    printf("mysqueeze_griffiths: %s\n", result);

}

char *mysqueeze(char *a, char *b)
{
    int i = 0, k;
    do
    {
        k = 0;
        while (b[k] != '\0')
        {
            if (a[i] == b[k]) {
                a[i] = '*';
                break;
            }
            k++;
        }
        i++;
    }
    while (a[i]);
    return a;
}

void mysqueeze_griffiths(const char * first, const char * second, char * result) {
    while ( *first ) {
        bool found = false;
        while ( *second ) {
            if ( *first == *second++ ) {
                found = true;
                break;
            }
        }
        if ( !found ) {
            *result++ = *first;
        }
        ++first;
    }

    *result = '\0';
}

char *mysqueeze2(char *haystack, const char *needles)
{
    char *dest=haystack, *src=haystack;
    while (*src)
    {
        const char* n;
        for (n=needles; *n; ++n)
        {
            if (*n==*src)
            {
                ++src;
                break;
            }
        }
        if (!*n)
           *dest++ = *src++;
    }
    *dest = '\0';
    return haystack;
}

char *mysqueeze3(char *haystack, const char *needles)
{
    char *dest=haystack, *src=haystack;
    bool needleArray[256];
    memset(needleArray,0,sizeof(needleArray));
    for (const char* n=needles; *n; ++n)
        needleArray[(unsigned char)*n] = true;
    while (*src)
    {
        if (needleArray[(unsigned char)*src])
            ++src;
        else
           *dest++ = *src++;
    }
    *dest = '\0';
    return haystack;
}
于 2013-09-17T18:10:55.503 に答える
0

実際にあなたの質問に答えるには、1 から 4 を関数に移動する最も明白な方法はreal、3 番目の引数として渡すことです。ただし、文字を に置き換えてから他の文字をaコピー'*'するのは不要な手順です。このようなものが良いです：

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

void mysqueeze(const char * first, const char * second, char * result);

int main(void) {
    char first[] = "krishna";
    char second[] = "kareem";
    char result[100];

    mysqueeze(first, second, result);

    printf("Result: %s\n", result);

    return EXIT_SUCCESS;
}

void mysqueeze(const char * first, const char * second, char * result) {
    while ( *first ) {
        const char * t_second = second;
        bool found = false;
        while ( *t_second ) {
            if ( *first == *t_second++ ) {
                found = true;
                break;
            }
        }
        if ( !found ) {
            *result++ = *first;
        }
        ++first;
    }

    *result = '\0';
}

このアルゴリズムを実装するより時間効率の良い方法があります。たとえば、2 番目の文字列を 1 回通過させ、存在する各文字の配列にフラグを設定することで、最初の文字列との各比較を 1 つの定数で行うことができます。時間ルックアップ。

t_second編集: phonetagger のコメントに応答する変数を追加しました。

于 2013-09-17T17:31:13.767 に答える