C++ Verkettete Liste rückwärts ausgeben.

vs1

Grünschnabel
Hi Leute,

Ich muss eine Funktion einfügen ,die die Verkettete Liste
rückwärts ausgeben lässt. Hab vieles versucht, komme doch nicht drauf.

Hat jemand vielleicht Ideen?
Vielen Dank!

#include <iostream.h>


class listenelement {
char daten[30];
listenelement* next;
public:
void setdaten(char datenneu[30]);
void init();
void einfuegen(char datenneu[30]);
void ausgeben();
void ende();
void ausgaberueckwaerts();
};

void listenelement::setdaten(char datenneu[30]) {
strcpy(daten,datenneu);
}

void listenelement::init() {
next = NULL;
}

void listenelement::einfuegen(char datenneu[30]) {
if (next==NULL) {
next = new(listenelement);
next->init();
next->setdaten(datenneu);
} else {
next->einfuegen(datenneu);
}
}

void listenelement::ausgeben() {
cout << daten << "\n";
if (next != NULL) {
next->ausgeben();
}
}

void listenelement::ende() {
if (next != NULL) {
next->ende();
delete(next);
}
}

listenelement* liste;


void init() {

liste = new(listenelement);


liste->init();
liste->setdaten("Listenanfang Element 0");
}


void ende() {

liste->ende();


delete(liste);
liste = NULL;
}

void main () {
init();
liste->einfuegen("Element 1");
liste->einfuegen("Element 2");

liste->ausgeben();
ende();

char p[50];
cin.getline(p,50);
}
 
Ich komme spontan auf zwei Möglichkeiten...
1. Du nutzt eine DoppKet, also eine Doppelt-Verkettete-Liste ( Vorgänger und Nachfolger ) oder
2. du nutzt einen Array in den du die Werte schreibst ( wenn es zu viel Werte sind dann z.B. eine Datei ) und liest dann von hinten nach vorne...

So hätte ich es gelöst...

Gruß
 
  • Gefällt mir
Reaktionen: vs1
2. du nutzt einen Array in den du die Werte schreibst ( wenn es zu viel Werte sind dann z.B. eine Datei ) und liest dann von hinten nach vorne...
Die Array-Lösung krankt allerdings daran, dass man entweder schon vorher wissen muss, wie lang die Liste ist (müsste sie also einmal durchlaufen zum bestimmen der Größe, einmal zum Eintragen in das Array und ein drittes mal zum ausgeben) oder das Array immer wieder vergrößern, was auch nicht ideal ist.

Ich würde eine zweite verkettete Liste aufbauen, die die Elemente in umgekehrter Reihenfolge speichert und diese dann der Reihe nach ausgeben (dazu muss man also nur zweimal über die Liste laufen). Aber vielleicht bin ich auch nur zu laufzeitoptimierungswütig ;)

Grüße,
Matthias
 
ich hab einen Tipp bekommen und zwar, ich soll keine Doppelt Verkettete Liste machen sondern die Methode ausgaberuekwaerts() nach dem selben Prinzip arbeiten lassen wie die Merthode ende() nämlich die Methode ausrufen lassen durch die Methode selbst. Ich hab aber leider keine Ahnung wie es aussehen soll. Kann da vielleicht jemand helfen?
 
Hallo,

das ist natürlich auch keine schlechte Idee (wenn man mal die Nachteile der rekursiven Aufrufe ausblendet) :) In der Methode ausgeben() gibst du ja zuerst die Daten des aktuellen Knotens aus und gehst dann zum nächsten weiter. Wenn du jetzt umgekehrt ausgeben willst, müsstest du zuerst alle nachfolgenden Knoten ausgeben und dann den aktuellen. Hilft das weiter?

Grüße,
Matthias
 
  • Gefällt mir
Reaktionen: vs1
Hey geil, auf solch eine Idee wär ich jetzt spontan auch nicht gekommen...
auf die Laufzeit hab ich natürlich oben nicht geachtet und zwecks Array -> deshalb hab ich ja auch geschrieben man könnte auch eine Datei verwenden.... wären auch 2 Durchläufe...

Aber um zu der Rekursion zu kommen ->
( Ich wähle mal n bisschen Pseudo-Code das es nicht zu "extrem" aussieht )...
Code:
void Rekursion_Ausgabe( Zeiger )
{
    if( Zeiger->Nachfolger != NULL )
         Rekursion_Ausgabe( Zeiger->Nachfolger )
    Zeiger->AUSGABE_VON_ALLEM
}
sehr geile Idee, wirklich...

Gruß

//EDIT.... Habs noch kurz "optimiert" ;D.......
 
Vielen Dank!

Hab nur noch eine Frage.

Könnte ich es Codemäßig so aussehen lassen oder fehlt da noch etwas?


// Liste rückwärts ausgeben

void listenelement::ausgaberueckwaerts() {
do
if (next == NULL) {
cout << daten << 'n';
while next != liste
}
}

oder

void listenelement::ausgaberueckwaerts() {

if (next == NULL) {
cout << daten << 'n';
do
next -> ausgaberuekwaerts
while next != liste

}
}
 
Code:
void Rekursion_Ausgabe( Zeiger )
{
    if( Zeiger->Nachfolger != NULL )
         Rekursion_Ausgabe( Zeiger->Nachfolger )
    Zeiger->AUSGABE_VON_ALLEM
}

Also ich finde in diesem Beispiel (oben) sieht man es ganz schön, die ganzen Schleifen (while, do-while, for) fallen bei den Rekursiven Funktionsaufrufen weg.

Vielen Dank!

Hab nur noch eine Frage.

Könnte ich es Codemäßig so aussehen lassen oder fehlt da noch etwas?

Hast du dir das Beispiel überhaupt angeguckt? (ist nicht bös gemeint)


Code:
// Liste rückwärts ausgeben

void listenelement::ausgaberueckwaerts() {
    do 
        if (next == NULL) { //Hier öffnest du die Geschweifte Klammer
            cout << daten << 'n';
    while next != liste
} // Hier schließt du die

// es ist nicht möglich die zwei Anweisungsblöcke zu "kreuzen"
}

Der Code kann/muss syntaktisch so richtig(er) aussehen:

Code:
// Syntaktisch richtig

void listenelement::ausgaberueckwaerts() {
    do {
        if (next == NULL) { 
            cout << daten << 'n';
        } // Hier wir die if-Anweisung geschlossen
    } while(next != liste); //Hier die do-while-Schleife
}// Hier die Funktion
Code:
//Syntaktisch falsch
void listenelement::ausgaberueckwaerts() {

if (next == NULL) {
cout << daten << 'n';
do 
next -> ausgaberuekwaerts
while next != liste

}
}

Auch das ist hier total falsch.

Ich habe weiter oben geschrieben das man die Schleifen garnicht braucht da der Rekursiver Aufruf das so macht.

Der Quelltext syntaktisch richtig(er) währe:

Code:
 //Syntaktisch richtig
void listenelement::ausgaberueckwaerts() {
    if (next == NULL) {
        cout << daten << 'n';
        do {
            next -> ausgaberuekwaerts
        } while (next != liste); //Hier wird die do-while-Schleife geschlossen
    } //hier die if-Anweisung
} //Hier die Funktion
Du scheinst noch ziemliche Probleme mit if's und den Schleifen etc zu haben, du solltest die erstmal wiederholen, denn sonst kommst du noch irgendwann total durcheinander.

Der Code für den Rekursievenaufruf muss so aussehen (Achtung: ungetestet!)

Code:
void listenelement::ausgaberueckwaerts() 
{
    if(next != NULL) {
        next->ausgaberueckwaerts();
    }
    cout << next->daten << 'n';
}
Gruß
Rudolf Grauberger
 
Zurück