Verkettete Listen
-
Hallo,
ich habe mal eine Frage zu diesem Quelltext (aus C++ von A bis Z):// list.cpp #include <iostream> using namespace std; struct Knoten { int daten; Knoten* next; }; // Anfang der Liste Knoten* Anfang = 0; // Funktionsprototypen Knoten* insertKnoten( int& val); void showKnoten( const Knoten* n ); Knoten* deleteKnoten( int dat ); int main(void) { Knoten* node; int auswahl, ival; do { cout << "Eine einfache verkettete Liste\n"; cout << "------------------------------\n"; cout << "-1- Neues Element hinzufügen\n"; cout << "-2- Alle Elemente ausgeben\n"; cout << "-3- Einzelnes Element löschen\n"; cout << "-4- Programm beenden\n\n"; cout << "Ihre Auswahl : "; cin >> auswahl; switch( auswahl ) { case 1 : cout << "Daten eingeben: "; cin >> ival; node = insertKnoten( ival ); break; case 2: showKnoten( node ); break; case 3: cout << "Wert zum Löschen eingeben: "; cin >> ival; node = deleteKnoten( ival ); break; case 4: break; default: cout << "Falsche Menüauswahl?\n"; } } while( auswahl != 4); return 0; } // Funktion zum Einfügen neuer Elemente Knoten* insertKnoten( int& val ) { // Ist noch kein Element in der Liste, // dann fügen wir das erste am Anfang ein if( Anfang == 0 ) { Knoten* node = new Knoten; node->daten = val; node->next = 0; Anfang = node; return Anfang; } // Es sind bereits Elemente in der Liste, // dann soll das neue hinten angehängt werden else { Knoten* node = Anfang; Knoten* newNode; while( node->next != 0 ) node=node->next; newNode = new Knoten; newNode->daten = val; newNode->next = 0; node->next = newNode; return Anfang; } } // Alle Elemente der Liste anzeigen void showKnoten( const Knoten* n ) { if ( Anfang == 0 ) { cout << "Die Liste ist leer\n"; } else { cout << "1. Element: " << n->daten << '\n'; for( int i = 2; n->next != 0; i++ ) { n=n->next; cout << i << ". Element: " << n->daten << '\n'; } } } // Das erste Element mit dem Wert dat aus der Liste löschen Knoten* deleteKnoten( int dat ) { if ( Anfang == 0 ) { cout << "Die Liste ist leer\n"; } // Ist das erste Element das von uns gesuchte? if( Anfang->daten == dat ) { Knoten* del = Anfang; if( Anfang->next != 0 ) Anfang = Anfang->next; delete del; } // Die komplette Liste nach dem gesuchten // Element durchlaufen else { Knoten* node = Anfang; while( node->next != 0 && node->next->daten != dat ) node=node->next; if( node->next == 0 ) cout << "Element zum Löschen kommt nicht" << " in der Liste vor!\n"; else { // das zu löschende Element an del zuweisen Knoten* del = node->next; // Einen Hilfszeiger hinter das zu löschende Element Knoten* help = del->next; // das zu löschende Element "aushängen" node->next = help; delete del; } } return Anfang; }Was bringt hier der globale Zeiger node? Er erhält ja von den Funktionen insertKnoten und deleteKnoten nach Ausführung stets den Wert von Anfang zugewiesen. Nur beim Aufruf der Funktion showKnoten wird der Zeiger übergeben. Dort wird er benötigt, da dessen Wert in der Funktion verändert wird. Aber warum wurde da nicht ein lokaler Zeiger verwendet, dem am Anfang der Funktion der Wert von Anfang zugewiesen wurde?
Des weiteren wird bei deleteKnoten, wenn noch keine existiert, nach der Ausgabe, das keiner existiert einfach fortgefahren, was ja jedoch zu einem Absturz führen würde. Muss da nicht noch um den kompletten Rest ein else{}?Viele Grüße tuxianer
-
Ich vermute, Du solltest das Buch löschen.
node bringt gar nichts. Anfang bringt alles.
-
naja ein zweiter Zeiger muss zur Ausgabe schon her,
n=n->next;hiermit zeigt er ja woanders hin und dann wäre das Anfangselement verloren oder?
-
Max123 schrieb:
naja ein zweiter Zeiger muss zur Ausgabe schon her,
n=n->next;hiermit zeigt er ja woanders hin und dann wäre das Anfangselement verloren oder?
ja, auch ein lokaler del in delKnoten muß sein. die main() muß keine kenntnis der knoten haben, sie muß nichtmal wissen, daß es überhaupt den typ Knoten gibt.
-
weils schon spät ist, mal etwas umgeschrieben
// list.cpp #include <iostream> using namespace std; struct Knoten { int daten; Knoten* next; }; // Funktionsprototypen Knoten* letzterKnoten( Knoten* liste ); Knoten* insertKnoten( Knoten* liste, int val); Knoten* deleteKnoten( Knoten* liste, int val ); void showKnoten( const Knoten* liste ); int main() { Knoten* liste = 0; int auswahl = 0, ival = 0; do { cout << "Eine einfache verkettete Liste\n" "------------------------------\n" "-1- Neues Element hinzufügen\n" "-2- Alle Elemente ausgeben\n" "-3- Einzelnes Element löschen\n" "-4- Programm beenden\n\n" "Ihre Auswahl : "; cin >> auswahl; switch( auswahl ) { case 1 : cout << "Daten eingeben: "; cin >> ival; liste = insertKnoten( liste, ival ); break; case 2: showKnoten( liste ); break; case 3: cout << "Wert zum Löschen eingeben: "; cin >> ival; liste = deleteKnoten( liste, ival ); break; case 4: break; default: cout << "Falsche Menüauswahl?\n"; } } while( auswahl != 4); return 0; } // gibt uns das letzte Element einer Liste zurück Knoten* letzterKnoten( Knoten* liste ) { if ( liste != 0 ) while ( liste->next != 0 ) liste = liste->next; return liste; } // Funktion zum Einfügen neuer Elemente Knoten* insertKnoten( Knoten* liste, int val ) { Knoten x = { val, 0 }; // wir fügen einen dummy-Knoten vorne ein, um // Sonderfälle zu vermeiden // dieser Knoten wird nicht per new angefordert und // verschwindet bequemerweise beim Verlassen der Funktion Knoten dummy = { 0, liste }; letzterKnoten( &dummy )->next = new Knoten( x ); return dummy.next; } // Das erste Element mit dem Wert val aus der Liste löschen Knoten* deleteKnoten( Knoten* liste, int val ) { // wir fügen einen dummy-Knoten vorne ein // damit sind keine Sonderfälle mehr zu beachten Knoten dummy = { 0, liste }; Knoten* node = &dummy; while( node->next != 0 && node->next->daten != val ) node=node->next; if( node->next == 0 ) cout << "Element zum Löschen kommt nicht in der Liste vor!\n"; else { // das zu löschende Element an del zuweisen Knoten* del = node->next; // das zu löschende Element "aushängen" node->next = node->next->next; delete del; } return dummy.next; } // Alle Elemente der Liste anzeigen void showKnoten( const Knoten* liste ) { if ( liste == 0 ) { cout << "Die Liste ist leer\n"; } else { for( int i = 1; liste != 0; i++ ) { cout << i << ". Element: " << liste->daten << '\n'; liste=liste->next; } } }Das Löschen des Buches ist wahrscheinlich trotzdem eine gute Idee.
-
ok und nochmal ne frage zum Anfangsquelltext. Also man kann die Anfangsposition ja notfalls auch global lassen oder? dann kann man sich aber den kompletten Rückgabewert der Funktion jeweils sparen und node, das in main lokale hat auch keinen Sinn, da man das hätte lokal lösen können.