3. Zeigerkonstruktion á la next->next

Zeigerkonstruktion á la next->next

  • ?

    ich probiers mal aus und sende mein Ergebnis dann...auf jeden Fall sind die Dinge, die du aufgezählt hast - also was man besser machen könnte - richtig....leider erfordert es die Aufgabenstellung so (ich persönlich würde es auch anders machen ;))

    Ich versteh jetzt aber immer noch nicht, was das mit zeiger->next->next bzw. zeiger->next->prev soll...Vielleicht kannst du mir das nochmal genauer erklären

    0
  • G

    naja, du benutzt ja eine Struktur für die Knoten, die die Membervariablen nicht selber mit NULL initialisiert, d.h. sie können irgendetwas enthalten (halt das, was zufällig an der Stelle im Speicher stand).

    Das bedeutet, dass man beide Zeiger (prev und next) intialisieren sollte, bzw. hier auch muss.
    "Muss" deshalb, weil in der Einfüge und der HoleKnoten Funktion überprüft wird, ob der nächste Knoten in der Liste gleich NULL ist, also ob er vorhanden ist. Wenn der Zeiger aber nicht initialisiert wurde, kann da irgendetwas stehen (0x0, 0x321e3564,...).

    Der Ausdruck "zeiger_vor->next->next" kann manchmal nötig sein. Wenn die Liste 5 Knoten hat, dann ist auch folgendes vollkommen erlaubt:

    anfang->next->next->next->next->name[0] = '\0';

    Nur muss man halt sicher sein, dass die Liste wirklich so lang ist.
    Aber so etwas ist eh nicht zu empfehlen, da keiner mehr nach 1 Woche weis, was das jetzt genau bedeutet (was ist das 5 next??).

    In meiner Einfüge Funktion wird ein neues Objekt auf dem Heap erstellt und dessen Adresse wird in "zeiger_vor->next"gespeichert, d.h. dieser "next" Zeiger zeigt auf das Objekt auf dem Heap.
    So, d.h. zeiger_vor->next ist jetzt definiert (erm, halt ungleich NULL).
    Als das Objekt auf dem Heap erstellt wurde, wurden allerdings die Membervariablen des neuen Objekts noch nicht initialisiert, was nun noch geschehen muss.

    zeiger_vor->next->next = NULL;

    Das initialisiert den next Zeiger des neuen Objekts.

    zeiger_vor->next->prev = zeiger_vor;

    Das initialisiert den prev Zeiger des neuen Objekts, und zwar mit der Addresse des vorhergehenden Objekts, also zeiger_vor.

    Oder, um es besser leserlich zu schreiben:

    Knoten* NeuerKnoten = new Knoten();
zeiger_vor->next = NeuerKnoten;
NeuerKnoten->next = NULL;
NeuerKnoten->prev = zeiger_vor;

    Durch das setzten von zeiger_vor->next und NeuerKnoten->prev wird die Verbindung zwischen beiden Objekten hergestellt, die das navigieren in der Liste ermöglicht.

    0
  • ?

    Ich denke, ich verstehe was du meinst..........Ich fass mal zusammen:

    eine Konstruktion wie zeiger->next->next=NULL bedeutet, dass das nächste Element NACH dem nächsten Element (sozusagen das übernächste) Element gleich NULL ist...
    Das bedeutet aber auch, dass zeiger->next bereits einen Wert erhalten haben muss, sonst sollte es zu einem Speicherüberlauf, Programmabsturz etc. kommen, richtig?...

    bei einer doppelten Liste könnte man jetzt auch sagen zeiger->next->prev...Das heißt dann, dass das nächste Element gleichzeitig im prev-Zeiger gespeichert wird...

    Ich hoffe, ich habs jetzt richtig wiedergegeben....

    0
  • Q

    ? prev steht für previous und bezeichnet das vorherige element in der liste.
    element->next->prev ist also gleich bedeutend mit "das element, das vor dem nächsten element liegt" und bezeichnet damit "element" selbst.
    /edit: doppelt verkettet heißt nicht, dass dieselbe information zweimal gespeichert ist, sondern dass die liste "nach vorne und nach hinten" verkettet ist.

    0
  • D

    "Speicherüberlauf, Programmabsturz" - nix Overflow, damit hat es nichts zu tun. Sowas nennt man NULLPOINTERDURCHGRIFF (punch-through) und führt zu unvorhersehbaren Ergebnissen (Schutzverletzung, Absturz, im besten Fall flasche Ergebnisse/keine Auswirkung)

    0

  • Also den Begriff "punch-through" hab ich in dem Zusammenhang noch nie gehört...
    Ich sag mal ich halte das für ein Gerücht dass das eine übliche Bezeichnung für das Dereferenzieren eines ungültigen Pointers bzw. Null-Pointers ist.

    NULLPOINTERDURCHGRIFF ist im Übrigen ein Wort welches du wohl gerade erfunden haben wirst. Zumindest Google findet dazu keine einzige Seite. Auch nicht für "NULLPOINTER DURCHGRIFF" oder "NULL POINTER DURCHGRIFF".

    0
  • D

    Das ist mir auch aufgefallen, aber unser Prof. benutzt es immerzu, und der ist Experte, außerdem klingt es auch logisch.

    Wie auch immer, jedenfalls handelt es sich nicht um einen Überlauf, sondern wie gesagt um Dereferenzierung eines NULLPOINTERs, wie auch immer man das nennen mag.

    0
  • ?

    "Speicherüberlauf, Programmabsturz" - nix Overflow, damit hat es nichts zu tun. Sowas nennt man NULLPOINTERDURCHGRIFF (punch-through) und führt zu unvorhersehbaren Ergebnissen (Schutzverletzung, Absturz, im besten Fall flasche Ergebnisse/keine Auswirkung)

    @dust:Kann ja sein, dass ich mich irre, aber hast du hier nicht grad dasselbe wie ich geschrieben?

    0
  • D

    Nein, ich habe dir mitgeteilt, dass es KEINEN overflow gibt, wenn man einen Zeiger dereferenziert, der ins Nirvana zeigt. Und ich habe geäußert wie man sowas wohl nennt (zumindest unser Prof. für Datenstrukturen^^), der müsstes ja eigentlich wissen.

    0
  • ?

    Is ja nich so wichtig........Auf jeden Fall meinen wir beide das Gleiche....ich habe mich da wohl etwas falsch ausgedrückt.....

    Um nochmal auf mein Problem zurückzukommen: Ich habe das mit zeiger_vor->next->last mal ausprobiert.........wenn ich das so ausführe, erhalte ich einen Speicherzugriffsfehler, sprich, es geht nicht weiter....

    Wenn ich allerdings sage zeiger_vor->last ist wieder alles in Ordnung....Hier nochmal der Quelltext zum Vergleich (nur Einfüge-Funktion):

    void einfuegen(char datenneu[30]) {
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) {
  hilfszeiger = hilfszeiger->next;
  hilfszeiger->last = hilfszeiger; // Verknüpfe das neuen Element mit dem Vorherigen
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 hilfszeiger->next = NULL;
 hilfszeiger->last = NULL;
}

    wie man gut sehen kann, hab ich lediglich die Zeiger anders verbunden...Dennoch führt das nicht zum gewünschten Ergebnis, die Elemente rückwärts auszugeben...

    Meine Ausgabefunktion:

    // Elemente rückwärts ausgeben
void ausgaberueckwaerts() {
 hilfszeiger_rueck = listenende;

 cout << hilfszeiger_rueck->daten << '\n';

 // Durch die Liste gehen, bis das erste Element erreicht ist
 while(hilfszeiger_rueck->last != NULL) {
  hilfszeiger_rueck = hilfszeiger->last;

  cout << hilfszeiger_rueck->daten << '\n';
 }
}

    Jetzt wird vielleicht verständlich, wofür ich hilfszeiger_rueck bzw. zeiger_rück benötige

    0
  • G

    Ich glaube du hast immer noch nicht so ganz das Prinzip von eine doppelt verketteten Liste verstanden.

    Ich kommentiere mal deinen Code:

    void einfuegen(char datenneu[30]) 
{
 //-->Warum muss hilfszeiger global sein? Wäre besser, ihn lokal zu halten
 //--> Außerdem: listenanfang kann doch NULL sein, oder nicht? Das bedeutet, dass "hilfszeiger->next" nach der Schleife einen Fehler auslöst, weil ja hilfszeiger NULL ist.
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) 
 {
  hilfszeiger = hilfszeiger->next;

// -->Das hier ist völliger Schwachsinn^^. last zeigt jetzt auf hilfszeiger, d.h. auf das eigene Objekt (last == this, wenn man sich im Objekt befinden würde).
  hilfszeiger->last = hilfszeiger; // Verknüpfe das neuen Element mit dem Vorherigen
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 // -->Erm, hilfszeiger zeigt auf das neue Objekt. Warum setzt du last im neuen Objekt auf NULL? Das bedeutet, dass das Objekt zum vorherigen Objekt nicht verknüpft ist.
 hilfszeiger->next = NULL;
 hilfszeiger->last = NULL;
}

    In deiner Ausgabefunktion kann ich auch keinen Grund erkennen, warum hilfszeiger_rueck global sein sollte.

    Also, um nochmal zu der Theorie von verketteten Listen zurückzukommen:
    Eine verkettete Liste wird oft als erschaffen, wenn man ein dynamisches array benötigt.
    Eine verkettete Liste besteht aus Objekten, die miteinander (über Zeiger) verbunden sind.
    x1 -> x2 -> x3 -> NULL
    x1 ist mit x2 verbunden, dass heißt wenn man dem zeiger folgt, erhält man x2.
    Wenn es nicht weitergeht, wird der Zeiger normalerweise auf NULL gesetzt.

    Das eben war eine einfach verkettete Liste. Eine doppelt verkettete Liste ist eigtl. auch nichts anderes, also eine Reihe von Objekten, die miteinander verknüpt werden. Allerdings kann man sich in einer doppelt verketteten Liste nicht nur vorwärts, sondern auch rückwärts bewegen.
    NULL <- x1 <-> x2 <-> x3 -> NULL
    Man kann jetzt z.b. bei x1 beginnen und auf x2 kommen, oder man beginnt bei x3 und folgt dem rückwärts-Zeiger, um auf x2 zu kommen.

    Um es mal bildlich zu beschreiben: Stell mehrere Räume vor, die mit Türen verbunden sind.
    - Einfach verkettete Liste: Die Türen kann man nur von einer Seite öffnen, d.h. man kann beim ersten Raum anfangen und somit bis zum letzten Raum gelangen. Allerdings kommt man nicht wieder zurück, man muss "ausenrum" gehen und wieder am Anfang anfangen.
    - Doppelt v. L.: Die Türen gehen von beiden Seiten auf. D.h. man kann die Räume auch in umgekehrter Reihenfolge durchlaufen, oder in der Mitter einfach umdrehen.

    Die Räume sind die Objekte.
    Eine Tür, die nur von einer Seite aufgeht (d.h. nur 1 Türklinke hat), ist 1 Zeiger.
    Eine Tür, die von beiden Seiten aufgeht (d.h. sie hat beidseitig je 1 Türklinke), repräsentiert 2 Zeiger.

    0

  • dust schrieb:

    Das ist mir auch aufgefallen, aber unser Prof. benutzt es immerzu, und der ist Experte, außerdem klingt es auch logisch.

    Rofl.
    "Ja, er ist der einzige der das so nennt, aber er ist Experte"

    Dein Professor hält sich wohl für schlau. Ich halte ihn nicht für schlau.

    0
  • D

    lol, und ich halte deine omma für schlau ... es interessiert keinen ... nur weil man was nicht bei google findet, heißt es noch längst nicht, dass es das nicht gibt ... v.a. bei zusammengesetzen Wörtern (das man durch Pointer durchgreift ist doch wohl allgemein bekannt (findest du auch bei google), und wenn man durch einen Nullpointer druchgreift, dann ist das eben ein NULLPOINTERDURCHGRIFF .. was ist da so schwer dran zu raffen, das Wort "Tomatenventilator" findest du bei google auch nicht, aber es ist dochwohl denkbar, dass man einen Ventilator, der wie eine Tomate aussieht so nennt) ... und jetzt Schluss mit dem Gespamme!

    0
  • Q

    du unterhältst dich hier mit leuten, die teilweise schon deutlich länger und professioneller (z.b. beruflich) programmieren als du, und vielleicht sogar dein professor? das ist zwar eine schöne metapher, "durch" einen zeiger "durchzugreifen", aber wenn du dich einmal mit anderen leuten unterhalten willst, die programmieren, wirst du damit weniger weit kommen, als wenn du sagen würdest, du greifs mit einem zeiger auf etwas zu. und wenn du einmal hilfe per google suchst, dann wirst du mit der kombination zeiger und zugriff auch deutlich mehr treffer haben, als mit zeiger und "durchgriff". "nullpointerzugriff" sagt man aber IMO auch nicht unbedingt. der richtige begriff wäre das "dereferenzieren eines nullzeigers". einen zeiger dereferenziert man, man greift nicht durch.

    von daher lässt sich viel eher sagen: es interessiert keinen, dass du das nullpointerdurchgriff nennst. sei also lieber froh, dass du an dieser stelle darauf hingewiesen wirst, dass man das nicht so sagt, anstatt dich über die vermeintliche inkompetenz hier aufzuregen. sprich lieber deinen prof darauf an.

    0
  • ?

    Schön zu sehen, wie sehr ihr euch über das Dereferenzieren von Zeigern aufregt :D...

    @Gugi: Also von der Theorie her isses ja nich schwer nachzuvollziehen...das begreife ich ja........vermutlich versteif ich mich da in irgendetwas....

    Ich merke, ich muss wohl mal den gesamten Code posten, damit Ihr seht, warum die Zeiger global und nicht lokal sind.....

    Also nochmal:

    /*##########################
     Einsendeaufgabe 5.2
  ##########################*/
#include <iostream>

using namespace std;

// Definition des Typs für die Elemente der Liste als Struktur
struct listenelement {
 char daten[10];
 listenelement* next; // vorwärts
 listenelement* last; // rückwärts
};

// Zeiger auf Anfang der Liste
listenelement* listenanfang;

// Zeiger auf Ende der Liste
listenelement* listenende;

// Hilfszeiger, um in der Liste "vorwärts wandern" zu können
listenelement* hilfszeiger;

// Hilfszeiger, um in der Liste "rückwärts wandern" zu können
listenelement* hilfszeiger_rueck;

// Funktion zum Einfügen von Elementen in die Liste
void einfuegen(char datenneu[30]) {
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;
 hilfszeiger_rueck = NULL;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) {
  hilfszeiger = hilfszeiger->next;
  hilfszeiger_rueck->last = hilfszeiger; // Verknüpfe das neue Element mit dem Vorherigen
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 hilfszeiger->next = NULL;
 hilfszeiger_rueck->last = NULL;
}

// Alle Elemente der Liste ausgeben
void ausgeben() {
 // hilfszeiger auf den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // erstes Element ausgeben
 cout << hilfszeiger->daten << '\n';

 // Solange das Ende noch nicht erreicht ist:
 while(hilfszeiger->next != NULL) {
  // hilfszeiger auf nächstes Element setzen
  hilfszeiger = hilfszeiger->next;
  // Daten ausgeben
  cout << hilfszeiger->daten << '\n';
 }
}

// Initialisieren der Liste
void init() {
 // erstes Element erzeugen
 listenanfang = new(listenelement);

 // Daten in das erste Element schreiben
 listenanfang->next   = NULL;
 listenanfang->last   = NULL;
 strcpy(listenanfang->daten, "Element 0");
}

// Liste leeren und Speicher freigeben
void ende() {
 // Solange noch Elemente in der Liste sind
 while(listenanfang != NULL) {
  // hilfszeiger auf das erste Element der Liste
  hilfszeiger = listenanfang;

  // Zeiger für den Listenanfang auf das nächste Element setzen
  listenanfang = listenanfang->next;

  // Das herausgenommene Element löschen
  delete(hilfszeiger);
 }
}

// Elemente rückwärts ausgeben
void ausgaberueckwaerts() {
 hilfszeiger_rueck = listenende;

 cout << hilfszeiger_rueck->daten << '\n';

 // Durch die Liste gehen, bis das erste Element erreicht ist
 while(hilfszeiger_rueck->last != NULL) {
  hilfszeiger_rueck = hilfszeiger_rueck->last;

  cout << hilfszeiger_rueck->daten << '\n';
 }
}

int main() {
 init();
 einfuegen("Element 1");
 einfuegen("Element 2");
 einfuegen("Element 3");
 ausgeben();
 ausgaberueckwaerts();
 ende();

 return 0;
}
    0
  • C
    Mod

    unwichtig schrieb:

    Ich merke, ich muss wohl mal den gesamten Code posten, damit Ihr seht, warum die Zeiger global und nicht lokal sind.....

    Das ist allerdings daraus nicht zu erkennen. Überflüssig und störend (störend deshalb, weil es den Lesefluss unterbricht) sind zunächst einmal die Kommentare - die sagen nur, was der Code macht. Das geht aber aus ihm selbst hervor. Was dem Code nicht zu entnehmen ist und Gegenstand der Kommentare sein müsste, ist das warum eines bestimmten Konstrukts (und in Fällen, in denen das selbstevident ist, heißt das eben: nicht kommentieren).

    Was die eigentliche Implementation angeht, stelle ich fest, dass weder listenende noch hilfszeiger_rueck noch last wirklich (jedenfalls nicht systematisch und konsequent) verwendet werden: damit ist das
    a) keine doppelt verkette Liste, und
    b) der Grund für ihre Existenz gerade nicht dem Code zu entnehmen und noch weniger, weshalb diese nun global sein müssen.

    0
  • ?

    Könnt ich denn theoretisch auch nur einen "hilfszeiger" nutzen? Ist sowas möglich?

    0
  • ?

    das dürfte ja nicht funktionieren oder?

    0
  • G

    xD kann man das nicht schon langsam flamewar nennen?^^

    also, meine Code-Fassung:

    /*##########################
     Einsendeaufgabe 5.2
  ##########################*/
#include <iostream>

using namespace std;

// Definition des Typs für die Elemente der Liste als Struktur
struct listenelement {
 char daten[10];
 listenelement* next; // vorwärts
 listenelement* last; // rückwärts
};

// Zeiger auf Anfang der Liste
listenelement* listenanfang;
listenelement* listenende;

// Funktion zum Einfügen von Elementen in die Liste
void einfuegen(char datenneu[30]) 
{
 // Es wird angenommen, dass listenanfang ungleich NULL ist!!!!
 listenelement* hilfszeiger = listenanfang;
 listenelement* hilfszeiger_rueck = NULL;

 while(hilfszeiger->next != NULL)
   hilfszeiger = hilfszeiger->next;

 listenelement* NeuesListenelement = new(listenelement);

 hilfszeiger->next = NeuesListenelement;

 // listenende erhält das aktuelle (letzte) Element
 listenende = NeuesListenelement;

 // Daten im neuen Element eintragen
 strcpy(NeuesListenelement->daten, datenneu);

 hilfszeiger->next = NULL;
 NeuesListenelement->last = hilfszeiger; // Verknüpfe neues Objekt mit altem
}

// Alle Elemente der Liste ausgeben
void ausgeben() 
{
 if (listenanfang == NULL)
   return;

 listenelement* hilfszeiger = listenanfang;

 while(hilfszeiger != NULL)
 {
  cout << hilfszeiger->daten << '\n';
  hilfszeiger = hilfszeiger->next;
 }
}

// Initialisieren der Liste
void init() 
{
 // erstes Element erzeugen
 listenanfang = new(listenelement);

 // Daten in das erste Element schreiben
 listenanfang->next   = NULL;
 listenanfang->last   = NULL;
 strcpy(listenanfang->daten, "Element 0");
}

// Liste leeren und Speicher freigeben
void ende() 
{
 listenelement* hilfszeiger = NULL;

 // Solange noch Elemente in der Liste sind
 while(listenanfang != NULL) 
 {
  // hilfszeiger auf das erste Element der Liste
  hilfszeiger = listenanfang;

  // Zeiger für den Listenanfang auf das nächste Element setzen
  listenanfang = listenanfang->next;

  // Das herausgenommene Element löschen
  delete(hilfszeiger);
 }
}

// Elemente rückwärts ausgeben
void ausgaberueckwaerts() 
{
 listenelement* hilfszeiger_rueck = listenende;

 while(hilfszeiger_rueck != NULL)
 {
  cout << hilfszeiger_rueck->daten << '\n';
  hilfszeiger_rueck = hilfszeiger_rueck->last;
 }
}

int main() 
{
 init();
 einfuegen("Element 1");
 einfuegen("Element 2");
 einfuegen("Element 3");
 ausgeben();
 ausgaberueckwaerts();
 ende();

 return 0;
}

    Wichtigste Änderungen:
    - Die 2 globalen Variablen wurden entfernt (warum brauchst du die???? warum MÜSSEN die global sein, warum können sie nicht lokal sein, was besser wäre).
    - Zeile 26: Schleife wurde korrigiert
    - Zeile 40: last wird jetzt korrekt initialisiert
    - Die Schleifen in ausgeben() und ausgaberueckwaerts() wurden geändert, so dass die gesamte Ausgabe innerhalb der Schleife erfolgt (nicht wie bei deiner Version, wo das 1. Element vorher ausgegeben wurde).

    Aber warum erstellst du den Listenanfang in der Init() Funktion? Warum nicht einfach den Fall, dass der Listenanfang == NULL ist, in der Einfüge() Funktion behandeln? Dann bräuchtest du die Init() funktion gar nicht, die meines erachtens eh unsinnig ist (du musst dann nur dann am Beginn von main() listenanfang und listenende gleich NULL setzten!).

    Also entweder verstehst du die Theorie nicht, oder du verstehst den Code nicht, den du geschrieben hast^^ Eines von beiden, weil, und da bin ich mir ziemlich sicher, dein jetziger Code falsch ist. 😉

    0
  • F

    Gugi schrieb:

    Übrigens nennt man ein Element einer solchen Liste Knoten (also ist eigtl. deine struktur-Bezeichnung falsch).

    Wie kommst du denn auf diese unsinnige Idee?

    0
Anmelden zum Antworten