Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
25.07.2006, 14:33 Uhr
Yadgar

Hallo!

Folgende Aufgabe:

Zu einer dynamischen Liste, deren Elemente nur in main() bekannt sind, soll eine Funktion geschrieben werden, die am Anfang dieser Liste ein neues Element hinzufügt. Ich frage mich, wie das funktionieren soll...

Hier ist der Code:

C++:

// Lineare Liste mit dynamischer Speicherverwaltung
// (AUPPERLE, S. 299ff)

#include <iostream>
using namespace std;

struct Element
{
   double wert;
   Element* next;
};

Element* head; // global

void insertFirst(Element* f)
{
   f->next=ep1;
}



int main()
{
   Element* ep1 = new Element;
   ep1->wert=1;
   ep1->next=0;

   Element* ep2 = new Element;
   ep2->wert=2;
   ep2->next=0;

   Element* ep3 = new Element;
   ep3->wert=3;
   ep3->next=0;

   head = ep1;
   ep1->next = ep2;
   ep2->next = ep3;

   // Ausgabe
   Element* p = head;
   while (p)
   {
      cout << p->wert << " ";
      p = p->next;
   }
   cout << endl;

   // neues Element
   Element* first = new Element;
   insertFirst(first);

   getchar();
}

Es ist klar, dass ich für die Zeile f->next = ep1 in der Definition von "insertFirst" eine Fehlermeldung bekomme... ist es überhaupt möglich, eine solche Funktion zu schreiben?
Ich könnte mir allenfalls vorstellen, dass ich den Namen des nächsten Objektes in der Liste mit übergebe...

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
25.07.2006, 15:21 Uhr
Yadgar

High!

Die erste Aufgabenstellung habe ich noch hinbekommen, indem ich das folgende Objekt mit übergab... aber jetzt wird es richtig haarig:

"Schreiben Sie eine Funktion, die alle Elemente einer linearen Liste mit delete freigibt!"

Wie soll das denn gehen, es sei denn, ich übergebe der Funktion explizit alle Elemente der Liste... aber das ist sicherlich nicht gemeint!

Mit

C++:

void delList(Element* h)
{
   Element* q;
   Element* p=h->next;
   while(p)
   {
      q=p;
      delete q;
      p=p->next;
   }
   delete h;
}

bekomme ich nur das erste Objekt der Liste tatsächlich zerstört, alle anderen bleiben erhalten (weil p und q ja nur innerhalb der Funktion existieren). Gibt es eine Möglichkeit, Referenzen auf Zeiger (!) zu übergeben?

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
25.07.2006, 16:35 Uhr
0xdeadbeef
Gott
(Operator)

Ah, Moment, da hast du was falsch verstanden. delete zerstört nicht den Zeiger, sondern das Objekt, auf das er zeigt. Daher ist

C++:

q = p;
delete q;
p = p->next;

auch nicht zulässig, weil

C++:

p->next

zu einem Zeitpunkt referenziert wird, als p schon nicht mehr gültig ist. (Klassischer Heisenbug, das)

An dieser Stelle heißt das Zauberwort Rekursion - wenn man einmal sieht, dass, wenn p eine Liste ist, p->next ebenfalls eine Liste ist, ist es ganz simpel:

C++:

void delList(Element *h) {
  if(h) {
    delList(h->next);
    delete h;
  }
}

Versuch mal nachzuvollziehen, was da passiert, das wird dir schon gut weiterhelfen

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
26.07.2006, 12:04 Uhr
Yadgar

High!

Zitat von 0xdeadbeef:

An dieser Stelle heißt das Zauberwort Rekursion - wenn man einmal sieht, dass, wenn p eine Liste ist, p->next ebenfalls eine Liste ist, ist es ganz simpel:

C++:

void delList(Element *h) {
  if(h) {
    delList(h->next);
    delete h;
  }
}

Versuch mal nachzuvollziehen, was da passiert, das wird dir schon gut weiterhelfen

Das nützt leider überhaupt nichts - auch nach der vermeintlichen Zerstörung sind die Elemente der Liste noch ansprechbar!

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
26.07.2006, 13:18 Uhr
BoBtheREapER
kein job für nen BoB

Rekursion
aus Wikipedia, der freien Enzyklopädia

Als Rekursion (auch Rekurrenz oder Rekursivität), von lateinisch recurrere = zurücklaufen, bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. Die gegenseitige Rekursion bildet sich durch den gegenseitigen Verweis zweier oder mehrerer Funktionen auf einander.

kurz eine funktion ruft sich selver auf:
das läuft in dem fall so ab:

C++:

void delList(Element *h) {
  if(h) {
    delList(h->next);
    delete h;
  }
}

bevor dasElement(h) zerstört wird wird die funktion delList() ein wieteres mal aufgerufen um das folgende elemnt zu zerstören. bevor das folgende elemnt allerdings zerstört wird wird ein weiteres mal die funktion delList() auf das wieder nächste element aufgerufen.
irgendwann ist die liste dann mal zu ende, das letzte element der liste erreicht damit dann nicht weiterhin delList() aufd nicht existierende elemente aufgerufen wird ist das if(h) wichtig.
angenommen du hast 20 elemente in deiner liste. dann wurde die funktion delList() insgesamt auch 20 mal aufgerufen ein 21stes mal muss sie nicht also wird endlich mal das delete h ausgefürt und die funktion delList() beendet. darauf wird das delete h vom 19. auruf ausgeführt uind so weiter.

ich weiß besonders schön ist die erklärung nicht aber ich hoffe du steigst da durch
--
"Zwei Dinge sind unendlich: Das Universum und die menschliche Dummheit. Aber beim Universum bin ich mir nicht ganz sicher." - Albert Einstein
www.blue-xenon.de.vu

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
26.07.2006, 13:34 Uhr
Yadgar

High!

Zitat von BoBtheREapER:

Rekursion
bevor dasElement(h) zerstört wird wird die funktion delList() ein wieteres mal aufgerufen um das folgende elemnt zu zerstören. bevor das folgende elemnt allerdings zerstört wird wird ein weiteres mal die funktion delList() auf das wieder nächste element aufgerufen.
irgendwann ist die liste dann mal zu ende, das letzte element der liste erreicht damit dann nicht weiterhin delList() aufd nicht existierende elemente aufgerufen wird ist das if(h) wichtig.
angenommen du hast 20 elemente in deiner liste. dann wurde die funktion delList() insgesamt auch 20 mal aufgerufen ein 21stes mal muss sie nicht also wird endlich mal das delete h ausgefürt und die funktion delList() beendet. darauf wird das delete h vom 19. auruf ausgeführt uind so weiter.

So habe ich sie auch in meinen Code eingebaut, trotzdem funktioniert es nicht so, wie es soll... hier ist der Code:

C++:

// Lineare Liste mit dynamischer Speicherverwaltung
// (AUPPERLE, S. 299ff)

#include <iostream>
using namespace std;

struct Element
{
   double wert;
   Element* next;
};

void insertFirst(double v, Element* f, Element* n)
{
   f->wert=v;
   f->next=n;
}

void insertLast(double v, Element* l, Element* p)
{
   l->wert=v;
   l->next=0;
   p->next=l;
}

void delList(Element *h)
{
  if(h)
  {
    delList(h->next); // rekursiver Aufruf!
    delete h;
  }
}



int main()
{
   Element* ep1 = new Element;
   ep1->wert=1;
   ep1->next=0;

   Element* ep2 = new Element;
   ep2->wert=2;
   ep2->next=0;

   Element* ep3 = new Element;
   ep3->wert=3;
   ep3->next=0;

   Element* head;

   head = ep1;
   ep1->next = ep2;
   ep2->next = ep3;

   // neues Element am Beginn der Liste
   Element* first = new Element;
   insertFirst(8.785, first, ep1);
   head=first;

   // neues Element am Ende der Liste
   Element* last = new Element;
   insertLast(-60.4, last, ep3);

   // Ausgabe
   Element* p = head;
   while (p)
   {
      cout << p->wert << " ";
      p = p->next;
   }
   cout << endl;

   // Zerstören der Liste
   delList(head);

   p = head;
   while (p)
   {
      cout << p->wert << " ";
      p = p->next;
   }
   cout << endl;

   getchar();
}

Bis bald im Khyberspace!

Yadgar
--
Flagmaker - ein Programmier-Blog

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
26.07.2006, 14:03 Uhr
0xdeadbeef
Gott
(Operator)

Das ist schon i.O. so, delete überschreibt ja nichts im Speicher, sondern gibt ihn lediglich wieder frei. Das bedeutet, das nächste new kann den Speicher wieder benutzen, muss es aber nicht. Und da hier zwischendurch nichts auf dem Heap gemacht wird, steht an den entsprechenden Stellen im Speicher zufällig noch das selbe wie vorher, so dass man noch drauf zugreifen kann. Eigentlich bewegst du dich aber im Niemandsland.

Wenn der Effekt dich sehr stört, schreib halt

C++:

void delList(Element *h)
{
  if(h)
  {
    delList(h->next); // rekursiver Aufruf!
    h->next = 0;
    delete h;
  }
}

oder so. Allerdings ist das ziemlich schlechter Stil und im Grunde nichts anderes als Rechenzeitverschwendung. Lass mal valgrind drüber, dann wirste schon sehen, dass es da keine Speicherlecks gibt.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
26.07.2006, 14:39 Uhr
~Yadgar
Gast

High!

Zitat von 0xdeadbeef:

Das ist schon i.O. so, delete überschreibt ja nichts im Speicher, sondern gibt ihn lediglich wieder frei.

Das hatte ich mir auch schon fast gedacht...

Zitat von 0xdeadbeef:

Lass mal valgrind drüber, dann wirste schon sehen, dass es da keine Speicherlecks gibt.

Valgrind? Wo finde ich das (unter Windows?)

Bis bald im Khyberspace!

Yadgar

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
26.07.2006, 14:43 Uhr
0xdeadbeef
Gott
(Operator)

valgrind gibts auf www.valgrind.org - allerdings nur für Linux. Für Windows - gute Frage. Möglicherweise läufts in cygwin oder so (würd aber nicht drauf wetten). Vielleicht bringt dein Compiler auch was vergleichbares mit, musste mal kucken. Ansonsten, knoppix aus dem Netz ziehen und damit mal ausprobieren.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: