qsort與定義結構

Question

我正在學習C和我正在解決this challenge，我不打算將它提交給uva平臺，我編碼這個練習的原因是爲了傾斜，也許不是這個問題的最佳方法，但我試着。

我在終端打印，輸入如下：

4 
3 
20 30 40 50 30 40 
Res: 2 
4 
20 30 10 10 30 20 40 50 
Res: 4 
3 
10 30 20 20 30 10 
Res: 2 
4 
10 10 20 30 40 50 39 51 
Res: 3 

從每個輸入測試的答案是不正確的，我相信原因是qsort函數。我很困惑如何使用結構使用qsort函數，我調用我的結構稱爲數組，然後是我的輸入大小，然後使用sizeof（int），但我需要使用int或sizeof我結構，最後我打電話給我的比較功能。我的代碼是：

#include <stdio.h> 
#include <string.h> 

struct Dolls{ 
    int w; 
    int h; 
}array[20005]; 

int cmp(struct Dolls a, struct Dolls b){ 
    if(a.w==b.w){ 
    return a.h < b.h; 
    }else{ 
    return a.w > b.w; 
    } 
} 

int arr[20005]; 
int dp[20005]; 
int n; 

int bSearch(int num, int k){ 
    int low=1; 
    int high = k; 
    int mid; 
    while(low<= high){ 
    mid = (low+high)/2; 
    if(num>=dp[mid]){ 
     low=mid+1; 
    }else{ 
     high=mid-1; 
    } 
    } 
    return low; 
} 

int res_dolls(){ 
    int k=1; 
    int i,pos; 
    dp[i]=arr[1]; 
    for(i=2;i<=n;i++){ 
    if(arr[i]>=dp[k]){ 
     dp[++k] = arr[i]; 
    }else{ 
     pos = bSearch(arr[i],k); 
     dp[pos] = arr[i]; 
    } 
    } 
    return k; 
} 

int main(){ 
    int t,j; 
    scanf("%d",&t); 
    while(t--){ 
    memset(array,0,sizeof(array)); 
    scanf("%d",&n); 
    for(j=1;j<=n;j++){ 
     scanf("%d %d",&array[j].w, &array[j].h); 
    } 
    qsort(array,n,sizeof(int),cmp); 
    for(j=1;j<=n;j++){ 
     arr[j] = array[j].h; 
    } 
    printf("%d\n",res_dolls()); 
    } 
    return 0; 
} 

Answer 1

你cmp功能需要被定義爲int (*)(const void *, const void *)它爲qsort工作。

您執行比較的方式也不正確。從快速排序的手冊頁：

如果第一個參數被認爲是 respec- tively小於，等於用比較函數必須返回一個整數小於，等於 或大於零，或者大於第二。如果 兩個成員比較相等，則它們在排序數組中的順序是 未定義。

你做返回<或>運營商，這是0或1。你需要明確檢查每個案件，並返回正確的值的結果的比較。

int cmp(const void *va, const void *vb){ 
    const struct Dolls *a = va; 
    const struct Dolls *b = vb; 

    if(a->w > b->w) { 
     return 1; 
    } else if(a->w < b->w){ 
     return -1; 
    } else if(a->h > b->h) { 
     return 1; 
    } else if(a->h < b->h){ 
     return -1; 
    } else { 
    return 0; 
    } 
} 

至於調用qsort，你需要給它一個數組元素的大小，即整個結構，而不是子字段的大小：

qsort(array,n,sizeof(struct Dolls),cmp); 

編輯：

修復了參數名稱的錯誤。還改變了如何執行排序以符合比較函數的行爲方式。