0

私は C に不慣れで、「構造体」などのオブジェクトを使用する習慣がありません。単純なプログラムの速度を改善しようとしています: 入力が 2 つのリストで構成されているとします: N 要素の 1 つと M 要素のもう 1 つです。2 番目のリストの各要素について知りたいのですが、最初のリストに表示される場合、出力は 1 になり、そうでない場合は戻り値が 0 になります。最後に、出力は 2 番目のリストの要素が入力された順序で表示されます。

そのため、最初に両方のリストを qsort() で並べ替えてから、各リストを比較しようとしましたが、私のプログラムは異常な結果を出力します。たとえば、M を 2 に固定すると、4 つの数値が出力されます。だからここに私のコードがあります：

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

//this function detects if the element 'input' is appears in the 
//first list called 'c'
//The output returns 0 if not, and the '(i+1)th' place 'input' 
//appears in 'c'

int search(int input,int a, int N,int c[N]){
    int i;
    int res=0;



for(i=a;i<N;i++){
        if(input==c[N-1-i]){res=i+1;break;}
        else{}
    }
    return res;
}

//Since we sort each list and since we want the output to appear 
//in the order each element  the second list's elements were input,
//we define a 'Spec' to keep in mind each index of the second list's 
//elements
struct Spec{
    int val;
    int ind;
};

//function qsort() uses to sort the first list 'c'
int compare (int* a, int* b)
{
    return ( *a - *b );
}

//function qsort() uses to sort the second list called 'd'
int comp(const void* a, const void* b)
{

    const struct Spec *A = (const struct Spec*) a;
    const struct Spec *B = (const struct Spec*) b;
    return A->val - B->val;
}

int main()
{
    int i;

    //the size of the first list 'c'
    int N;
    scanf("%d",&N);
    int rank=0;

    //declaring and sorting the first list 'c'
    int c[N];
    for(i = 0; i < N; ++i)
    {scanf("%d", &c[i]);}
    qsort (c, N, sizeof(int),compare);

    //the size of the second list 'd'
    int M;
    scanf("%d",&M);

    //declaring and sorting the second list 'd'
    struct Spec* d;
    d = (struct Spec*)calloc(M, sizeof(struct Spec));
    for(i = 0; i < M; i++)
    {scanf("%d", &d[i].val);}

    //initialize the index of the input's elements order 
    for(i = 0; i < M; i++)
    {d[i].ind=i;}

    qsort (d, N, sizeof(struct Spec), comp);

    //the output will be stored in 'f'
    int f[M];


    //if the following condition is verified, the the output must 
    //always be 0
    if((d[0].val>c[N-1])||(d[M-1].val<c[0])){
        for(i=0;i<M;i++){printf("0");printf("\n");}
    }


    else{
    for (i=0;i<M;i++){

        //the output is stored in 'f', and the index to respect 
        //input's order is then 'd[i].ind'
        if((d[i].val<c[0])){f[d[i].ind]=0;}
        //if the following condition is verified, the the output must always be 0 for the last 'M-i' outputs


        else if((d[i].val>c[N-1]))
             {
             int j;
             for(j=i;j<M;j++)
                {
                f[d[j].ind]=0;
                }
             break;
             }


        else{
                //if an element 'd[i]' of the second list 'd' 
                //appears in the first list 'c', then the output 
                //stored in 'f' will be '1' and the size of the 
                //matching (betwenn 'c' and 'd') search can be 
                //truncated from the first 'rank-1' elements
                if(search(d[i].val,rank,N,c)>0){
                rank=search(d[i].val,rank,N,c)-1;
                f[d[i].ind]=1;
                }
            else{f[d[i].ind]=0;}
            }
       }
    }

    //printing the output
    for(i=0;i<M;i++){
        printf("%d",f[i]);
        printf("\n");
    }

}

誰でも助けることができますか？

4

4 に答える 4

1

あなたの問題は、余分な出力の投稿に記載されているように、印刷ループの配置が原因です。最後の「else」ステートメント内に移動する必要があります。

最初に、D のすべての要素が C のすべての要素の外側 (大きいか小さいか) であるかどうかをテストします。そうであれば、すべてゼロを出力します。それは問題ありませんが、最後に再び F を出力します。これが余分な出力の元です。

さて、コードのフォーマットに取り掛かります......

于 2012-08-31T15:43:27.707 に答える
0

あなたの説明とあなたが提供したソースコードを読むと、あなたは次の行動をとっているように見えます。

まず第一に、別のリストに現れるかどうかを知りたい一種の定数である値のリストを読み込みます。これが SearchFor リストです。

次に、2 番目のリストに含まれる値のうちどれが最初のリストにも含まれているかを知りたい値のリストを読み込みます。これは ValueExist リストです。

検索手順を簡単にするために、SearchFor 値のリストを並べ替えて、ValueExist リスト内の特定の項目を比較しているときに、一致する項目が見つかるか、比較対象の SearchFor リスト内の現在の項目が見つかるとすぐに見つけられるようにします。 ValueExist リスト内の現在の項目が ValueExist リスト内の現在の項目よりも小さい 一致する場合 (それらが等しい場合)、または ValueExist リスト内の値が SearchFor リスト内にないかのいずれかです。これは、SearchFor 内の現在の比較項目がリストは、ValueExist リスト内の現在の項目の値よりも小さいです。

したがって、マッチングを行うためのルーチンは次のようになります。

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

//this function detects if the element 'input' is appears in the 
//first list called 'c'
//The output returns 0 if not, and the '(i+1)th' place 'input' 
//appears in 'c'

//Since we sort each list and since we want the output to appear 
//in the order each element  the second list's elements were input,
//we define a 'Spec' to keep in mind each index of the second list's 
//elements
struct Spec {
    int iValue;
    int iIndex;
};

//function qsort() uses to sort the first list 'c'
int compare (void *a, void *b)
{
    return ( *(int *)a - *(int *)b );
}

//function qsort() uses to sort the second list called 'd'
int comp(const void* a, const void* b)
{

    const struct Spec *A = (const struct Spec*) a;
    const struct Spec *B = (const struct Spec*) b;
    return (A->iValue - B->iValue);
}

int main()
{
    int i, iExist;

    //the size of the first list 'c'
    int N;
    printf ("Enter number of values for SearchFor list\n");
    scanf("%d",&N);
    int rank=N;

    //declaring and sorting the first list 'c'
    int SearchFor[N];
    for(i = 0; i < N; ++i)
    {
        printf ("Enter value for index %d\n", i);
        scanf("%d", &SearchFor[i]);
    }
   qsort (SearchFor, N, sizeof(int), compare);

    //the size of the second list 'd'
    int M;
    printf ("\nEnter number of values to search for\n");
    scanf("%d",&M);

    //declaring and sorting the second list 'd'
    struct Spec* ValueExist = (struct Spec*)calloc(M, sizeof(struct Spec));
    for (i = 0; i < M; i++) {
        // remember the original index for this value
        ValueExist[i].iIndex = i;
        // get the value for this index
        printf ("Enter value for index %d\n", i);
        scanf("%d", &ValueExist[i].iValue);
    }

    qsort (ValueExist, M, sizeof(struct Spec), comp);

    for (iExist = 0; iExist < M; iExist++) {
       for (i = 0; i < N; i++) {
          if (ValueExist[iExist].iValue == SearchFor[i]) {
             // value found
             printf ("Value of %d at index %d found.\n", ValueExist[iExist].iValue, ValueExist[iExist].iIndex);
             break;
           } else if (ValueExist[iExist].iValue < SearchFor[i]) {
              break;
           }
        }
     }
     return 0;
}
于 2012-08-31T16:07:33.097 に答える
0

コードを高速化するには、既存の search() 関数をBinary Searchに置き換えます。

また、コード行を見て、ではなく とif((d[i].val<c[0])){f[d[i].ind]=0;}比較したいことを確認してください。c[0]c[i]

于 2012-08-31T14:42:23.230 に答える
-1

"N" を vari int c[N] にすることはできないため、コードを正常にコンパイルできません。

于 2012-08-31T14:40:32.860 に答える