Verwenden von qsort mit einer definieren Struktur

Question

Ich lerne C und ich lösen this challenge, ich habe nicht vor, es auf die Uva-Plattform einzureichen und der Grund, warum ich diese Übung zum Lehnen ist, ist vielleicht nicht die bester Ansatz für das Problem, aber ich versuche es.

Der Eingang I in meinem Terminal drucken ist folgende:

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 

Die Antworten von jedem Eingangstest sind falsch, und ich glaube, der Grund ist die qsort Funktion. Ich bin verwirrt über die Verwendung der Qsort-Funktion mit einer Struktur, ich rufe meine Struktur, die Array genannt wird, gefolgt von der Größe meiner Eingabe, dann mit sizeof (int), aber muss ich int oder sizeof meine verwenden Struktur, schließlich rufe ich meine Vergleichsfunktion auf. Mein Code ist:

#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

Ihre cmp Funktion muss als int (*)(const void *, const void *) definiert werden es für qsort zu arbeiten.

Die Art, wie Sie die Vergleiche durchführen, ist auch nicht korrekt. Aus der Manpage für qsort:

Die Vergleichsfunktion für eine ganze Zahl kleiner als, gleich, oder größer als Null ist, wenn das erste Argument kleiner zu sein jeweili- betrachtet tiv zurückgeben muss als, gleich, oder größer als die Sekunde. Wenn zwei Mitglieder als gleich vergleichen, ist ihre Reihenfolge im sortierten Array undefined.

Die Vergleichen Sie das Ergebnis der < oder > Betreiber tun zurückkehren, die entweder 0 oder 1. Sie müssen explizit jeden Fall prüfen und den richtigen Wert zurück.

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; 
    } 
} 

Wie für den Anruf zu qsort, müssen Sie ihm die Größe eines Array-Element geben, dh die gesamte Struktur, nicht die Größe des Unterfeldes:

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

EDIT:

Der Fehler mit den Parameternamen wurde behoben. Außerdem wurde geändert, wie die Sortierung durchgeführt wird, um der Funktionsweise der Vergleichsfunktion zu entsprechen.