c - C中的排序程序

Question

我是 C 新手，我没有使用像“struct”这样的对象的习惯。我正在尝试提高一个简单程序的速度：假设输入由两个列表组成：一个是 N 个元素，另一个是 M 个元素。我想知道第二个列表的每个元素，如果它出现在第一个列表中，则输出为 1，否则返回为 0。最后，输出按第二个列表元素的输入顺序出现。

所以我首先尝试使用 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");
    }

}

有人可以帮忙吗？

Answer 1

您的问题 - 正如您在额外输出的帖子中所述 - 是由打印循环的放置引起的。您应该将它移到最后一个“else”语句中。

您首先测试 D 的所有元素是否在 C 中的所有元素之外（更大或更小）。如果是，则打印所有零。这很好，但最后你再次打印 F ，这是额外输出的来源。

现在，开始处理您的代码格式......

Answer 2

阅读您的描述和您提供的源代码，您似乎正在执行以下操作。

首先，您读入一个值列表，这些值是一种常量，您想知道它们是否出现在另一个列表中。这是搜索列表。

接下来，您读入一个值列表，您想知道第二个列表中有多少以及其中哪些也在第一个列表中。这是 ValueExist 列表。

为了使搜索过程更容易，您对 SearchFor 值列表进行排序，以便在比较 ValueExist 列表中的特定项目时，只要找到匹配项，或者您发现 SearchFor 列表中的当前项目与您进行比较ValueExist 列表中的当前项目小于 ValueExist 列表中的当前项目 您找到了匹配项，如果它们相等，或者 ValueExist 列表中的值不在 SearchFor 列表中，因为 SearchFor 中的当前比较项目list 小于 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;
}

Answer 3

要加快代码速度，请将现有的 search() 函数替换为Binary Search。

此外，请查看代码行if((d[i].val<c[0])){f[d[i].ind]=0;}并验证您希望比较的c[0]不是c[i].

Answer 4

您的代码无法编译成功，因为“N”不能是 vari int c[N];