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

您的代碼無法成功編譯，因爲「N」不能爲vari int c [N];

Answer 2

爲了加速代碼，用Binary Search替換現有的搜索（）函數。

另外，請查看代碼行if((d[i].val<c[0])){f[d[i].ind]=0;}並確認您希望與c[0]而不是c[i]進行比較。

Answer 3

您的問題 - 如您的額外輸出文章中所述 - 是由打印循環的放置引起的。你應該把它移到最後的「else」聲明中。

您首先測試D中所有元素是否都在C中所有元素的外部（大於或小於）。如果是，則打印所有零。這很好，但最後再次打印F，這是額外輸出的來源。

現在，在您的代碼格式化工作......

Answer 4

閱讀你的描述，你提供的源代碼，似乎你正在做以下操作。

首先你讀了一個值列表，它是一種常數，你想知道它們是否出現在另一個列表中。這是SearchFor列表。

接下來，您閱讀您想知道第二個列表中的多少個以及哪些列表中的值也列在第一個列表中的值列表。這是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; 
}