3. Hab nen Fehler in Heapsort

Hab nen Fehler in Heapsort

  • J

    Moin,

    und zwar bekomme ich beim kompilieren immer einen Fehler, nach dem ich schon gegoogelt hab, aber nix zu gefunden hab, was mir hilft...

    non-lvalue in decrement"

    Die Zeile hab ich mal fett gemacht...

    Wäre nett wenn jemand helfen könnte...

    #include<iostream>
#include<time.h>
#include<stdlib.h>

#define MAX 5000

using namespace std;

class CSort
{
private:
int zahl[MAX];
int originalzahl[MAX];
public:
void ziehen();
void kopieren();

void adjustheap();
void heap();

};

void CSort::ziehen()
{
for(int i=0; i<MAX;i++)
originalzahl[i]=rand()%MAX;
}
void CSort::kopieren()
{
for(int i=0; i<MAX;i++)
zahl[i]=originalzahl[i];
}

void CSort::adjustheap()
{
int j;
int i=1;
int speicher = zahl[i];
while(i < MAX/2)
	{
	j=2*i+1;
	if((j<MAX-1)&&(zahl[j+1]))
	 j++;
	if(speicher>=zahl[j])
	 break;

	zahl[i] = zahl[j];
	i=j;
	}
 zahl[i] = speicher;
}

void CSort::heap()
{
int i,t;

for (i = MAX/2;i;)
	adjustheap();
[b]while (--MAX)[/b]
{
 t=zahl[0];
 zahl[0]=zahl[MAX];
 zahl[MAX]=t;
 adjustheap();
}
}

int main()
{
double zeitdauer_q;
clock_t anfang, ende;
srand((unsigned)time(NULL));
time_t timer=time(NULL);
CSort meineZahlen;

/* Hier wird die Funktion zum Zahlen ziehen aufgerufen */
meineZahlen.ziehen();
/* Hier werden die gezogenen Zahlen kopiert */
meineZahlen.kopieren();
/* Hier wird der Zeitzähler gestartet */
anfang=clock();
/* Hier wird die Funktion Quicksort aufgerufen */
meineZahlen.heap();
/* Hier wird der Zeitzähler beendet */
ende=clock();
zeitdauer_q=(double)(ende-anfang)/CLOCKS_PER_SEC;

cout<<"Heap dauert"<<zeitdauer_q<<endl;
}
    0
  • B
     

    void CSort::heap()
{
int i,t;
int max = MAX;
for (i = max/2;i;)
    adjustheap();
while (--max)
{
 t=zahl[0];
 zahl[0]=zahl[max];
 zahl[max]=t;
 adjustheap();
}
}

    der preprocessor ersetzt das MAX vorm compilieren durch 5000. --5000 ist aber nicht definiert.

    0
  • J

    Hm, nun bekomme ich keinen Fehler mehr *freu*

    Aber das Progg funktioniert immer noch nicht *heul*
    Bricht immer ab

    0
  • V

    die meisten heap-sorts für c oder c++ in büchern sind fehlerhaft. das liegt daran, daß sie zuerst für sprachen mit 1-basierten arrays veröffentlich wurden (nachdem aus dem code pseudocode gemacht wurde). dieser pseudocode wird dann ohne indextransformation nach c oder c++ übersetzt und damit ist das c- oder c++-programm dann einfach falsch.
    um genau zu sein, ist es sogar als durchaus schwierig zu bezeichnen, einfachen und korrekten code für heapsort sich zu besorgen.

    0
  • H

    um genau zu sein, ist es sogar als durchaus schwierig zu bezeichnen, einfachen und korrekten code für heapsort sich zu besorgen

    Man lege sich John Bentleys "Programming Pearls" zu. Da ist nicht nur eine hübsche Heapsort-Implementation (inklusive Invarianten-Beschreibung) drin sondern auch eine große Menge andere Informationen zum Thema Herangehensweisen für die geschickte Implementation von Algorithmen und Datenstrukturen.
    Defintiv ein must-have-Buch für alle die auf den Spuren Volkards wandeln wollen.

    0
  • V

    HumeSikkins schrieb:

    Man lege sich John Bentleys "Programming Pearls" zu.

    jo, da war ich heftig froh, als ich das gefunden hatte.

    aber daß sein heapsort irgendwas besonderes sein sollte, war mir nie aufgefallen. mal gucken...

    John Bently schrieb:

    With the functions we've already built, the complete Heapsort algorithm requires just five lines of code.

    jo, sieht sehr nach c++-stil aus und nicht so einem pascal-monster.
    aber wenn ich mir die sprüche wie "root=1", "if i==1 break" und "for i = [2, n]" anschaue, sehe ich exakt meine these bestätigt, daß schon wieder einer ein 1-basiertes heap-sort gebastelt und veröffentlicht hat.

    macht aber nix, wer heap sort echt kapiert, und das geht wohl mit diesem buch besser als mit jedem anderen, das ich über sowas gelesen habe, der kann die grenzen leicht umsetzen und sich dann sogar über noch ein wenig mehr speed freuen.

    Defintiv ein must-have-Buch für alle die auf den Spuren Volkards wandeln wollen.

    ja, definitiv. ich hab's erst einmal hier empfohlem, weil ich nicht dachte, daß die leser hier schon weit genug dafür sind.

    0
Anmelden zum Antworten