3. Baumstruktur

Baumstruktur

  • O

    Hi Leute,

    versuche zur zeit eine dynamische baumstruktur zu programmieren und bin auch (dachte ich) zu einer eigendlich ganz guten idee gekommen und hab sie gleich programmiert:

    void initialisiereBaum(int **a,int nr,int b)
{
    for (int i=0;i<b;i++)
    {
        a[nr][i]=i;
        //printf("%d,",a[nr][i]);
    } 
 }

int main()
{
    int **a;
    a=new int*[2];
    a[0]=new int[20];
    a[1]=new int[1];
    initialisiereBaum(a,0,20);
    initialisiereBaum(a,1,1);
    printf("%d",a[1][0]);
    getchar();
    return 0;
}

    zuerst hat eigendlich alles gut funktioniert, bis ich dachte: "versuch mal über das hinaus zu gehen was du eigendlich deklariert hast (müsste ja zu einem programmabsturz kommen)" und was ist passiert? der hat das sogar gemacht
    wenn ich 200 bei initialisiereBaum(a,0,200) bzw. intitialisiereBaum(a,1,200) angegeben hab und den auskommentierten code einkommentiert hab. dann konnte ich zum schluss vor getchar auch über printf draufzugreifen aber wenn ich den auskommentierten text auskommentiert lasse stürzt wie erwartet beim zugriff das programm ab.
    Nun kann mir DAS jemand erklären???

    PS: ich endschuldige mich für die mischung von c und c++

    0
  • C

    Kurzfassung: "undefined behaviour" != "Absturz" 😉

    Langfassung: Zugriffe auf nicht initialisierte oder fremdgenutzte Speicherbereiche gelten als "undefined behaviour" - wenn du sowas machst, kann theoretisch alles mögliche passieren, von (scheinbar) korrektem Verhalten bis zum Formatieren deiner Festplatte. Du kannst dich nur darauf verlassen, daß du nicht vorhersagen kannst, was passiert. (vielleicht klappt auch der init-Aufruf reibungslos und zerschießt dir nur unbemerkt den Heap - was du dann erst beim delete bemerken würdest)

    0
  • O

    ok, danke, ich habs verstanden. aber generell ist das deklarieren, wie ich es gemacht hab, unproblematisch und so auch als baumstruktur möglich zu nutzen?

    0
  • C

    Ich denke mal schon, besser wäre es natürlich, die blanken Zeiger hinter einer Kontrollklasse zu verstecken, die sich um die Speicherverwaltung und ähnliches kümmert. Und ich würde den Speicher für die einzelnen Zeilen in der initialisiereBaum()-Funktion reservieren.

    PS: Und du darfst nicht vergessen, den angeforderten Speicher wieder freizugeben.

    PPS: Übrigens würde ich dieses Gebilde nicht als "Baum" bezeichnen, sondern als zweidimensionales Array 😉

    0
  • O

    hätte ein zweidimensionales array nicht in der 2. dimension immer die gleiche anzahl an werten? ich hab das hier ja so gemacht das a[0] z.B 20 werte hat und a[1] z.B. nur 1 wert. ich dachte immmer das wäre der unterschied zwischen einem array und einem baum.
    und das freigeben des speichers ist ja so weit ich weis nur dann notwendig, wenn der speicher innerhalb des programms wieder freigegeben werden muss (bei anwendung in einen großen projekt sicherlich notwendig) aber sonst wird der speicher bei beendigung des programms freigegeben, oder?

    0
  • C

    Oermel schrieb:

    hätte ein zweidimensionales array nicht in der 2. dimension immer die gleiche anzahl an werten? ich hab das hier ja so gemacht das a[0] z.B 20 werte hat und a[1] z.B. nur 1 wert.

    Nicht unbedingt, auch wenn das mitunter vorteilhaft ist. Unter einem Baum stelle ich mir auf jeden Fall etwas vor, was tiefer verschachtelt sein kann als nur über zwei Ebenen.

    und das freigeben des speichers ist ja so weit ich weis nur dann notwendig, wenn der speicher innerhalb des programms wieder freigegeben werden muss (bei anwendung in einen großen projekt sicherlich notwendig) aber sonst wird der speicher bei beendigung des programms freigegeben, oder?

    Wenn du schon so an die Sache heran gehst, wirst du nie in einem größeren Projekt eingesetzt (sorry, das mußte mal gesagt werden). Ja, die meisten heutigen Betriebssysteme geben Speicher wieder frei, den das gerade beendete Programm vergessen hat, aber:

    • Es gibt Anwendungen, die Monatelang am Stück laufen können. Und wenn die ständig Speicher anfordern, ohne ihn wieder freizugeben, zwingen sie dein System recht schnell in die Knie.
    • delete[] macht mehr als nur Speicher freizugeben. Es ruft vorher noch den Destruktor des zu löschenden Objekts auf. Für int ist das unkritisch, aber wenn Objekte weitere Ressourcen belegen, die der Dtor wieder freigeben sollte (File-Handles, Mutexe oder Window-Handles), dann bleiben die auf ewig blockiert (und nicht für alle Ressourcentypen übernimmt Windows die Aufäumarbeiten).

    (wenn du eine Sprache sucht, bei der du so verschwenderisch mit Speicher umgehen kannst, nimm C++/CLI, C# oder Java - die haben einen Garbage Collector)

    0
  • O

    danke für die ausfühliche aufklärung, das wusste ich noch nicht (das internet als einzige informationsquelle ist oft sehr bruchstückhaft). und so problematisch ist das nun auch wieder nicht delete aufzurufen (das auslassen beruhte nur auf faulheit ^^).

    0
  • O

    sry, ich muss doch noch mal stören ^^.
    kann es sein, dass wenn ich in der 2. dimension meines "baums" "bin"(dafür also speicher reservieren möchte), nur noch begrensten speicher zur verfügung hab, weil ich die darüberliegende dimension schon dynamisch erzeugt hab? weil ich kann in der ersten dimension 6000000 integer variablen reservieren, aber wenn ich in der ersten 100 und dann in der zweiten dann je 60000
    reservieren möchte, stürzt mal wieder das programm ab. (nach meiner rechnung dürfte das aber nicht mehr speicher verbrauchen) kann ich das umgehen?

    0
Anmelden zum Antworten