2016-03-22 14 views
0

meine Aufgabe ist es, den Code zu einem Heapsort nach Pseudocode schreiben. Es sollte den Input-Array (4 3 2 5 6 7 8 9 12 1) heapsort und dann mit der printHeap-Methode drucken. Ich weiß in der Tat, dass der printHeap funktioniert, weil ich ihn bereits mit einer Methode namens buildHeap benutzt habe (um Max heap binary builds zu erstellen, aber ihr alle wisst das schon :)) und dort funktioniert es einwandfrei, mein Problem liegt also in heapSort .Probleme mit HeapSort

Es sortiert richtig und druckt es so, wie es soll (Eltern - Kind 1, Eltern - 2, etc.), nur Ausgabe ist, dass der größte und letzte Wert, der 12 ist, plötzlich wird 24 und ich habe keine Ahnung warum.

Der Code ist der folgende:

void heapSort(int a[], int n){ 
int x = n+1; 
int i; 
int temp; 
buildMaxHeap(a, n); 
for (i = n; i >= 1; i--){ 
    temp = a[i]; 
    a[i] = a [0]; 
    a [0] = temp; 
    x--; 
    heapify(a, 0, x); 
} 

void printHeap(int a[], int n){ 

int i; 
printf("graph g { \n"); 
for (i = 0; i < n/2; i++){ 
    printf("%d -- %d\n", a[i], a[left(i)]); 
    if (right(i) < n){ 
     printf("%d -- %d\n", a[i], a[right(i)]); 
    } 
} 
printf("}\n"); 

Ausgang folgt:

1 2 3 4 5 6 7 8 9 24 
graph g { 
1 -- 2 
1 -- 3 
2 -- 4 
2 -- 5 
3 -- 6 
3 -- 7 
4 -- 8 
4 -- 9 
5 -- 24 
} 

nur damit Sie wissen, was genau habe ich getan, ich werde die während anhängen .c-Datei hier: https://onedrive.live.com/redir?resid=8BC629F201D2BC63!26268&authkey=!AFqVlm9AptiZ_xM&ithint=file%2cc

Wirklich dankbar für Ihre Hilfe!

Prost Arik

+0

Ich sehe keinen Grund zu der Annahme, dass Ihre 'heapSort()' Funktion dazu führt, dass sich die im Array enthaltenen Werte ändern, obwohl Sie nicht den vollständigen Code präsentiert haben Frage selbst *). Ich schlage vor, dass Sie einen Debugger verwenden, um dies zu beheben, aber wenn Sie Hilfe von uns wollen, dann sehen wir normalerweise einen [mcve]. –

+0

In 'buildMaxHeap' verwenden Sie einen Index' i' in Array 'a', dessen Wert so hoch wie' n' sein kann. Wenn "a" "n" -Werte enthält, sollte "i" nicht "n-1" überschreiten. –

+0

Wenn Sie die Quelldaten eingeben, beginnt Ihr Zähler 'n' bei Null und wird nach Eingabe jeder Zahl inkrementiert. Wenn Sie zehn Zahlen eingeben, werden sie in die Array-Elemente 0 bis 9 eingegeben, aber n ist 10. Fügen Sie 'n -;' hinzu, nachdem Sie die while-Schleife verlassen haben. Korrigieren Sie nun die printArray-Schleife mit 'i <= n;' und korrigieren Sie schließlich die printHeap-Schleifensteuerung 'i <(n + 1)/2;'. – anita2R

Antwort

0

Nun, Sie auf ein nicht definiertes Verhalten beobachten. (Ich persönlich auf einer Online-IDE bekam 0 anstelle des 12 (24).)

Versuchen:

void heapSort(int a[], int n) 
{ 
    int x = n; /* changed from n+1 */ 
    int i; 
    int temp; 

    buildMaxHeap(a, n); 
    for (i = n-1; i >= 0; i--){ /*<-- changed*/ 
     temp = a[i]; 
     a[i] = a[0]; 
     a[0] = temp; 
     x--; 
     heapify(a, 0, x); 
    } 
} 

Ihre Arrays in fast allen Allzweck-Sprachen von heute beginnen mit dem Index 0 [Für ausführliche Informationen siehe wiki.] Sie loopen Ihr Array for (i = n; i >= 1; i--) falsch und da der Heap maximal ist, verarbeiten Sie nicht das erste Element und gehen Sie mit dem letzten außer Grenzen. Obwohl die Arithmetik mit dem nth Element im Standard definiert ist, ist es nicht so gemeint, sondern eher ein Zeiger.

Nebenbei bemerkt, können Sie Makros (#define s) für die , right usw. Funktionen verwenden, um die Leistung zu verbessern und das Lesen zu erleichtern.

Ich hoffe, dass spart den Tag und die AlgoDat Übung.

+0

Vielen Dank! Deine Lösung hat funktioniert :) –