3. Probleme mit Speicherplatzfreigabe bei Rekursion:

Probleme mit Speicherplatzfreigabe bei Rekursion:

  • A

    Hallo, ich habe dies zwar auch unter dem Thema "c++" gepostet aber hier passt es wohl besser!

    Ich möchte MergeSort schreiben und soweit funktioniert es auch, jedoch schaffe ich es nicht allen angeforderten speicher wieder freizugeben, da MergeSort ja Rekursiv ist und ich delete irgendwie entweder zu selten oder zu oft aufrufe.

    Das Problem ist in der Methode MergeMerge welche 2 jeweils sortierte Folgen zusammenfägt. Da das ergebnis eine Folge von doppeltr Länge ist habe ich hierfür dynamisch ein Array erzeugt welches dieses Array aufnimmt.

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

    Jedoch ist dies bei jeder Rekursion nötig.

    Jetzt wollte ich diesen Speicher wieder freigeben, da ich mir logisch gedacht habe: Das neu erzeugte array wird ja sofort zurückgegeben und auch MergeSort liefert es wieder sofort zurück, weil es ja das ergebnis bei der jeweiligen rekursionstife ist. Wenn ich jedoch in MergeSort

    delete (a)

    vor der unteren returnanweisung einfüge stürtzt das Programm ab.

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

    Wie(und vor allem wo) kann ich den Speicherplatz elegant wieder freigeben?

    0
  • S

    Andreas XXL schrieb:

    delete (a)

    wenn du einen array allokierst musst du auch einen array wieder freigeben und nich nur das erste element

    also

    delete [] a;
    0
  • A

    Aber wenn ich den code so ändere

    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)
		   //delete[laenge] a;    Hier erfolgt der Absturz

    stürtzt er immer noch ab!

    Was kann ich das richtig machen?

    0
  • P

    Nimm doch die Vector-Klasse aus der STL

    #include <vector>

using std::vector;

typedef vector<int> IntVector;

...

IntVector iv;

iv.push_back(3); // Zahl ans Ende des Arrays einfügen
iv[0] = 7;       // bestehendes Element ändern (ungeprüft)
int j = iv[0];   // bestehendes Element auslesen (ungeprüft)
int s = iv.size(); // Größe des Arrays
iv.at(0) = 7;     // bestehendes Element ändern (geprüft)
int j = iv.at(0); // bestehendes Element auslesen(geprüft)

IntVector func( const IntVector& a ) { // Array als (konstanter, nicht änderbarer) Parameter

   return a; // Kopie von a zurückgeben
}

    Damit sparst Du Dir sämtliche Probleme mit der manuellen Speicherverwaltung.

    Bei Deiner jetzigen Vorgehensweise beispielsweise hast Du das Problem, daß am Ende nur ein Array zurückgeliefert werden soll, obwohl Du ständige neue Arrays allokierst. Neben "x" und "y" mußt Du auch "d" und "f" freigeben:

    delete [] f;
delete [] d;
delete [] y;
delete [] x;

    Du mußt außerdem sicherstellen, daß Du keine Elemente außerhalb Deiner Arrays ansprichst.

    Nimm lieber die Vektor-Klasse und benutz die at() Methode.

    0
Anmelden zum Antworten