Zeiger auf int in stack puschen

[jsdhfhdgb]

Hallo, ich möchte die Zeiger auf ein Array von int in ein stack packen, habe aber probleme damit:

int main (){

int *pArray = new int[8]; 

	pArray[0]=11;
	pArray[1]=5;
	pArray[2]=19;
	pArray[3]=12;

	pArray[4]=13;
	pArray[5]=100;
	pArray[6]=7;
	pArray[7]=9;

	stack<int> *s = new stack<int> ();

	s->push(s);    ///Fehler

return 0;
}

Fehler: error C2664: 'push' : Konvertierung des Parameters 1 von 'int *' in 'const int &' nicht moeglich

Wie geht sowas?

[miller_m]

du möchtest ja den stack auf den stack pushen, das geht nicht.

int main ()
{
    // so wäre doch bestimmt besser, oder was hast du mit den array vor
    stack<int> s;

    s.push(11);
    s.push(5);
    s.push(19);
    s.push(12);
    // usw
    return 0;
}

[jsdhfhdgb]

Es geht eigentlich um was anderes. Ich habe versucht MergheSort selbst zu schreibn. Diese Methode ist rekursiv und erzugt dabei dynamisch neue Arrays mit

int *c = new int[gr1 + gr2]; // Platz fuer Array c besorgen

Das Problem ist, dass ich es nicht schaffe bei der rekusion alle neu erzeugten Array wieder zu löschen. (Ich rufe delete entweder zu wenig oder zu oft auf).

Jetzt habe ich mir gedacht, ich könnte Zeiger aller erzeugten Arrays auf den Stack legen und zum Schluß komplett löschen.

Aber vieleicht findet jemand eine elegantere Möglichkeit. Ich Poste mal den gesamten code:

class sortieren 
{ 

private:  static int*  MergeMerge(int a[],int b[], int gr1, int gr2) {

			  int i=0, j=0, k=0; // Laufindizes
			  int *c = new int[gr1 + gr2]; // Platz fuer Array c besorgen

			  while ((i<gr1) && (j<gr2)) { // mischen, bis ein Array leer
				  if (a[i] < b[j]) // jeweils das kleinere Element
					  c[k++] = a[i++]; // wird nach c uebernommen
				  else
					  c[k++] = b[j++];
			  }
			  while (i<gr1) c[k++] = a[i++]; // ggf.: Rest von Folge a
			  while (j<gr2) c[k++] = b[j++]; // ggf.: Rest von Folge b

			  return c; // Ergebnis abliefern

			  		  }

public:static int* MergeSort(int a[], int laenge) {

		   int *x;
		   int *y;
		   int *c;
		   int halb_laenge=(int)(laenge/2.0);		//Mitte bestimmen

		   if  (laenge==1){							//Wenn nichts zu tun a zurückgeben (Element wird kopiert)
			   c = new int [laenge];				//direktes zurückgeben ohne die Objektkopie erzeugt nochmehr probleme,
			   c[0]=a[0];							//dann einige Rekursive Aufrufe Echte kopiel lieferten und andere nicht

			   return a;								//Rückgabe	
		   }

		   x = new int[halb_laenge];			//lege 2 neue Arrays an
		   y = new int[halb_laenge+(laenge%2)];

		   int i;	
		   for (i=0; i<halb_laenge; i++) {		// Kopiere die 1. Hälfte von a[] nach x[]
			   x[i]=a[i];
		   }

		   for (i=halb_laenge; i<laenge; i++) {	// Kopiere die 2. Hälfte von a[] nach y[]

			   y[i-halb_laenge]=a[i];
		   }

		   int *d= MergeSort(x,halb_laenge);		//Rekursiver Aufruf für die 2 Teilfolgen
		   int *f= MergeSort(y,halb_laenge+(laenge%2));

		   c= MergeMerge(d,f,halb_laenge,halb_laenge+(laenge%2));	//Beide Sortierte Teilfolgen "zusammenmischen"

		   delete(x);  //Hier wird x wieder freigegeben (in der selben Methode oben erzeugt)
		   delete(y);  //Hier wird x wieder freigegeben (in der selben Methode oben erzeugt)

		   return c;								//Rückgabe 
	   }

};

Und hier der Code der Hauptklasse:

int main (void) {

	int *pArray = new int[8]; 

	pArray[0]=11;
	pArray[1]=5;
	pArray[2]=19;
	pArray[3]=12;

	pArray[4]=13;
	pArray[5]=100;
	pArray[6]=7;
	pArray[7]=9;

	int *eArray=	sortieren::MergeSort(pArray,5);

	for (int i=0; i<5; i++ ) {
		cout <<eArray[i]<< endl;
	}

	return 0;
}

Das Problem ist in der Methode MergeMerge bei der Zeile

int *c = new int[gr1 + gr2]; // Platz fuer Array c besorgen (Hier liegt das Problem)

Da diese nicht wieder freigegeben werden

Setze ich nun ein Delete(a) unter die beiden anderen delete Aufrufe stürtzt das Programm ab! Das ist ja auch klar, weil das Programm MergeSort sich 2 mal selbst rekursiv aufruft und dadurch zuviele Delete(a) da sind!

[MBCS-CITP]

jsdhfhdgb schrieb:

Setze ich nun ein Delete(a) unter die beiden anderen delete Aufrufe stürtzt das Programm ab! Das ist ja auch klar, weil das Programm MergeSort sich 2 mal selbst rekursiv aufruft und dadurch zuviele Delete(a) da sind!

Nee, daran liegt es nicht, da bei jedem Aufruf von MergeSort eine Instanz des Arrays erzeugt, die auch wieder zum Ende der Methode zerstoert wird.

Aber: In Deinem main-Prg. rufst Du zweimal den new-Operator auf:

int *pArray = new int[8];

Hier den Default-new-Operator fuer int und hier

int *eArray=    sortieren::MergeSort(pArray,5);

ebenfalls ueber

int *c = new int[gr1 + gr2]; // Platz fuer Array c besorgen

die Aufrufe von MergeMerge und MergeSort. Dieser Speicher wird nirgentwo wieder freigeben. Ich vermute, dass hierin die Ursache des Crashs liegt.

[jsdhfhdgb]

Ja das Problem ist genau hier, im MergeMerge

int *c = new int[gr1 + gr2]; // Platz fuer Array c besorgen

Aber dies wird ja mit return c zurückgegeben und kommt so wieder in MerGeSort an und wird auch dort sofort zurückgegeben. Das ist ja genau die Rekursion.

Aber wie kann ich dieses löschen? Es müsste ja sozusagen eine ebene höher passieren (bei der Rekursion), weil erst dort dfas neu erzeugte Array unnötig wird. (Deswegen wollte ich delete(a) machen weil es eine Ebene höher wieder in MergeSort ankommt. Aber da stürtzt das Programm ab!

[jsdhfhdgb]

PS so wie es ist ist das programm lauffähig. Jedoch belegt es immer mehr speicher der nicht mehr freigegeben wird!

[MBCS-CITP]

Ich bin zu faul, Dir Deine Arbeit zu machen, aber Du hast doch eine Abbruchbedingung:

if  (laenge==1)

Die Struktur der Rekursion muss so aussehen, dass der Speicher vor dem Verlassen der Methode (Aufruf von return) freigegeben wird, wenn die Abbruchbedingung falsch ist, ansonsten gibts Du den allocierten Speicher als Zeiger zurueck. Ich denke, dass Du die gesamte Struktur der Rekursion ueberarbeiten musst.

[jsdhfhdgb]

Die Struktur der Rekursion muss so aussehen, dass der Speicher vor dem Verlassen der Methode (Aufruf von return) freigegeben wird, wenn die Abbruchbedingung falsch ist, ansonsten gibts Du den allocierten Speicher als Zeiger zurueck. Ich denke, dass Du die gesamte Struktur der Rekursion ueberarbeiten musst.

Genau! Ich habe es jetzt so gemacht:

public:static int* MergeSort(int a[], int laenge) {

		   int *x;
		   int *y;
		   int *c;
		   int halb_laenge=(int)(laenge/2.0);		//Mitte bestimmen

		   if  (laenge==1){							//Wenn nichts zu tun a zurückgeben (Element wird kopiert)
			   c = new int [laenge];				//direktes zurückgeben ohne die Objektkopie erzeugt nochmehr probleme,
			   c[0]=a[0];							//dann einige Rekursive Aufrufe Echte kopiel lieferten und andere nicht

			   return a;								//Rückgabe	
		   }

		   x = new int[halb_laenge];			//lege 2 neue Arrays an
		   y = new int[halb_laenge+(laenge%2)];

		   int i;	
		   for (i=0; i<halb_laenge; i++) {		// Kopiere die 1. Hälfte von a[] nach x[]
			   x[i]=a[i];
		   }

		   for (i=halb_laenge; i<laenge; i++) {	// Kopiere die 2. Hälfte von a[] nach y[]

			   y[i-halb_laenge]=a[i];
		   }

		   int *d= MergeSort(x,halb_laenge);		//Rekursiver Aufruf für die 2 Teilfolgen
		   int *f= MergeSort(y,halb_laenge+(laenge%2));

			c= MergeMerge(d,f,halb_laenge,halb_laenge+(laenge%2));	//Beide Sortierte Teilfolgen "zusammenmischen"
			for (i =0; i<laenge;i++) {
					a[i]=c[i];
			}

		   delete [laenge] c;
		   delete[halb_laenge] x ;  //Hier wird x wieder freigegeben (in der selben Methode oben erzeugt)
		   delete[halb_laenge+(laenge%2)] y;  //Hier wird x wieder freigegeben (in der selben Methode oben erzeugt)

		   return a;								//Rückgabe 
	   }

};

Das scheint zu funktionieren!
Die Idee in jeder Rekursionstiefe alles dort erstelle auch sofort zu löschen hat geholfen!