HeapSort mit binärer Suche

ProfiTipp schrieb:

Schau mal wie ein Debugger funktioniert und debugge deinen Code, bringt ne Menge Erleuchtung.

Wenn man am Compiler nich vorbeikommt hilft n Debugger auch nich übermässig.

@alibix: Versuche morgen moch was sinnvolles zum Thema zu lassen. Heut wirds eh nichts sinnvolles mehr. Aber das konnt ich mir nicht verkneifen.

ProfiTip an Profitip schrieb:

ProfiTipp schrieb:

Schau mal wie ein Debugger funktioniert und debugge deinen Code, bringt ne Menge Erleuchtung.

Wenn man am Compiler nich vorbeikommt hilft n Debugger auch nich übermässig.

Den Compilerfehler hat er erst nach meinem Post dazu editiert. Mal auf die Uhrzeiten schauen, du Schlaumeier.

Pointer auf arrays haben kein .length, nimmt std::vector, wenn du das willst.

unskilled

void mybinsearch(int* feld, int x, int &links){ 
    int l = 0, r = feld.length - 1, i = 0;

ProfiTipp schrieb:

Pointer auf arrays haben kein .length, nimmt std::vector, wenn du das willst.

Oder übergib die Länge einfach noch extra mit

bb

albix

Ich hab nun ein wenig den Code geändert. Hier die Ausschnitte, die eine Änderung beinhalten:

// Variablen zur Laufzeitberechnung
int vergleich2=0, tausch2=0;
// Feld zur Laufzeitrueckgabe;
int *rueck2 = new int[2];
int depth = 0;

int mybinsearch(int[], int, int);
void __swap (messdaten *, messdaten *);

inline void myreheap(messdaten *feld, int len, int i)
{

   const int laenge = len;
   /***
   * k == das linke Kind
   * rechts == hält den Index des Elements an dessen Stelle das Wurzelelement gesetzt wird
   * indizesWerte == ist das Array das die Indize der größten Söhne hält
   */
   int k=2*i+1, links = 0;  

   // Das Array, das die Indizes der größten Kinder festhält
   int indizesWerte[laenge];

   while(k + 1 < len)
   {
	   if (feld[k+1] > feld[k]){
		   vergleich2++;
		   indizesWerte[depth] = k++;
	   }
	   else {
		   indizesWerte[depth] = k;
	   }
      k=2*k+1;
      depth++;
    }
.....
.....
.....

UND:

int mybinsearch(int* feld, int x, int length){
	int l = 0, r = length, i = 0;
	do{
		i = (l + r)/2;
		if (feld[i] > x){
			vergleich2++;
			l = i + 1;
		}
		else
			r = i - 1;
		if (r < 0) break;
	}while(!(l > r) && r >= 0);
	return r;
}

Und das ergibt diese Fehlermeldung:

error C2057: Konstanter Ausdruck erwartet // Gilt für die Zeile 22 im ersten C++-Code Block
error C2466: Zuordnung eines Arrays der konstanten Größe 0 nicht möglich.
error C2133: 'indizesWerte': Unbekannte Größe

unskilled

albix schrieb:

...

Mal paar allg. Anmerkungen und die Lösung deines Problems:

// Feld zur Laufzeitrueckgabe;
int *rueck2 = new int[2];

wieso hier new[] ?
das delete[] seh ich auch nirgendwo -> speicherleck

allg. sind globale variablen nicht gerad hübsch...

int mybinsearch(int[], int, int);
void __swap (messdaten *, messdaten *);

1. In Prototypen müssen die Parameter zwar nicht benannt werden, aber es nicht zu machen ist hässlich - wenn ich mal schnell gucken will, wie ich die Fkt aufzurufen habe, will ich nicht erst die *.cpp suchen und dann dort gucken, was ich übergeben muss sondern es bequem im header nachgucken können!

2. bezeichner mit 2 unterstrichen am anfang sind lt. standard für den compiler reserviert - z.bsp. für makros - ist bei swap auch gar nicht mal sooo unwahrscheinlich.
außerdem klingt die fkt so, als ob es sie bereits geben würde ^^
hier hast du nen guten überblick über die c++ standard bibliothek
http://www.cplusplus.com/reference/
unter algorithm
gibt es beispielsweise auch std::swap...

inline void myreheap(messdaten *feld, int len, int i)
{
   const int laenge = len;
   int indizesWerte[laenge];

geht so nicht, da laenge nicht zur compilezeit bekannt ist...
also wirst du wohl entweder new[] / delete[] nutzen müssen oder nen Array nehmen müssen, was auf jeden Fall groß genug ist - int indizesWerte[MAX]
aber auch hier hat die standard-library wieder eine gute (bessere) alternative:
vector

bb

albix

Ich habe nun anstatt eines Arrays den std::vektor genommen. Allerdings habe ich damit noch so meine Probleme. Ich dachte vektor wäre dynamisch und wächst von alleine wenn man neue Werte einfügt. Der Code hier scheint aber nicht zu stimmen:

int depth = 0;
inline void myreheap(messdaten *feld, int len, int i)
{

   //const int laenge = len;
   /***
   * k == das linke Kind
   * rechts == hält den Index des Elements an dessen Stelle das Wurzelelement gesetzt wird
   * indizesWerte == ist das Array das die Indize der größten Söhne hält
   */
   int k=2*i+1, links = 0;  

   // Das Array, das die Indizes der größten Kinder festhält
   //int indizesWerte[laenge];
   std::vector<int> v(depth);

   while(k + 1 < len)
   {
	   if (feld[k+1] > feld[k]){
		   vergleich2++;
		   //indizesWerte[depth] = k++;
		   v[depth] = k++;
	   }
	   else {
		   //indizesWerte[depth] = k;
		   v[depth] = k;
	   }
      k=2*k+1;
      depth++;
    }
......
......
......

Die Compiler liefert direkt keine Fehlermeldung, aber sobald zum ersten mal etwas in den vektor eingefügt werden soll erscheint ein Debug-Fehler-Fenster:

Debug Assertion Failed!
......
Expression: vector subscript out of range

Wie füge ich nun Werte in den vektor ein? Ich weiß ja zuvor nicht wieviele Werte eingefügt werden, da von vornherein nicht klar ist, wieviele Kinder und Kindes-Kinder der Baum hat. Der vektor soll dynamisch wachsen und am Schluss die Anzahl der Elemente ausgeben....

Nexus

Schau doch mal in die Foren-Artikel oder auf www.cplusplus.com. Es macht nicht viel Sinn, wenn wir dir hier die Funktionsweise der STL erklären.

albix

Ok vielen Dank. Ich war wohl etwas voreilig. Habs nun geschnallt

std::vektor<int> v;
v.push_back(Wert);

unskilled

das hier hast du hoffentlich auch wieder geändert:
std::vector<int> v(depth);
macht zwar nix unerwartetes, aber ist unsinnig ^^

std::vector<int> name;
reicht völlig - wobei du als name hoffentlich nen aussagekräftigeren als v genommen hast?! ^^

bb

Nexus

Ich rate dir wirklich, dich ausführlich mit dem Artikel zu befassen. Die STL-Container sind etwas, das man in C++ ständig benötigt. Sie sind auch recht mächtig und komfortabel, es lohnt sich also durchaus, etwas Zeit zu investieren.

Übrigens: Es heisst std::ve c tor .