ADT Verkette Liste rückwärts ausgeben lassen

D

Dolphon

Erfahrenes Mitglied
Hi,

ich habe eine verkettete List, welche in umgekehrter Reihenfolge ausgegebn werden soll. Dabei soll diese Ausgabe max. O(n) haben.
Ich hab den Tip bekommen, dass dies unteranderem durch eine Rekursion möglich ist. Allerdigns habe ich keinen Plan, wie ich das umsetzten kann. Die normale Ausgabe habe ich hinbekommen.
Hier einmal die Klasse:

PHP: 
class liste{

private:

	struct knoten {
	  int info;
	  struct knoten *next;
	};
	                
	struct knoten *pos;      // Positionszeiger
	struct knoten *pre_pos;  // Vorgänger des Positionszeigers
	struct knoten *anfang;   // Zeiger auf den Anfang  der Liste

public:

	liste() {
		pos = pre_pos = anfang = NULL; // Leere Liste 
	}

	void ausgeben() {                            // ausgeben von Anfang bis Ende
			struct knoten *p = anfang;           // p zeigt auf aktuellen Knoten
			cout << "Liste: ";
			while (p != NULL) {                        
					cout << p->info << " ";      // Infoteil des aktuellen Knoten ausgeben
					p = p->next;                 // p auf Folgeelement setzen
			}
			cout << endl;
	}

	void ausgeben_umgekehrt() {              
			

/*if(p != NULL) {
        p->ausgeben_umgekehrt();
    }
    cout << p->info << 'n';*/


	}

	int get() {                    // liefere aktuelles Element
			return pos->info;
	}
	bool end() {                    // Ende erreicht?
			return (pos == NULL);                   
	}
	void adv() {                    // Positionszeiger vorrücken
			if (pos != NULL) {
					pre_pos = pos;
					pos = pos->next;
			}
	}
	void reset() {                  // Positionszeiger an den Anfang setzen
			pos = anfang;
			pre_pos = NULL;
	}

	void ins(int x) {
			struct knoten *p = new knoten;  // erzeuge neuen knoten
			p->info = x;        // Infowert wird x
			p->next = pos;      // next wird initialisiert mit alten P.-Zeiger
								// es wird also VOR dem aktuellen Element eingefügt
			if (anfang == NULL)     // Leere Liste
					anfang = p;
			if (pre_pos != NULL)            // Positionszeiger hat einen Vorgänger
					pre_pos->next = p;
			else                            // neues Element steht am Anfang
					anfang = p;
			pos = p;              // Positionszeiger zeigt nun auf das neue Element
	}

	void del() {                            // Aktuelles Element löschen
			if (pos != NULL) {                    // P.-Zeiger steht nicht am Ende
					if (pre_pos != NULL)          // P.-Zeiger steht nicht am Anfang
							pre_pos->next = pos->next;
					else
							anfang = pos->next;   // Anfang wird neu gesetzt
					delete pos;                   // Speicher aufräumen
					if (pre_pos != NULL)
							pos = pre_pos->next;  // P.-Zeiger steht auf ehemaligem Nachfolger
					else
							pos = anfang; // korrigiert!!
			}
	}
	

};
 
Hi,

Muss es denn eine einfach verkettete Liste sein?
Wenn du es in eine doppelt verkettete Liste umbauen würdest,
mit einem Zeiger der den Vorgänger kennt, dann wäre die Lösung denkbar einfacher.

MfG Turri
 
C++: 
void ausgeben_umgekehrt(knoten *a)
{
  if(a->next!=NULL)ausgeben_umgekehrt(a->next);
  //hier a->info irgendwie ausgeben
}

Damit das für die ganze Liste gemacht wird, das ganze mit anfang aufrufen
 
clevere Variante ;)

Mir stellt sich nur die Frage groß die Rekursionstiefe bei C++ ist, das weiß ich gerade nicht.
Wenn ich jetzt 50000 Werte in der Liste habe, dann krachts vermutlich.
Pro Wert einmal Rekursion.

MfG
 
Zuletzt bearbeitet:
warum "rekursionstiefe in c++"?
Kann ja sein, dass es sowas gibt, glaub ich aber eher nicht
Das Ganze ist (meines Wissens nach) eher durch Betriebssystem und RAM begrenzt
als durch die sprache

@maetimmae: 1) Hab ich ja gesagt
2) Hab mich Schlecht ausgedrückt-natürlich kriegt nicht ein Programm alles vom Ram-zumindest in den gängigen OS.
"Verfügbarer Speicher" hätte da besser gepasst
 
Zuletzt bearbeitet:
sheel hat gesagt.:
Kann ja sein, dass es sowas gibt, glaub ich aber eher nicht
Zum Vergrößern anklicken....
C++ läuft nicht wie beispielsweise Java oder C# in einer VM, welche die Resourcen verwaltet, sondern kann (theoretisch) sämtliche ansprechbare Resourcen verwenden.

sheel hat gesagt.:
Das Ganze ist (meines Wissens nach) eher durch Betriebssystem und RAM begrenzt
Zum Vergrößern anklicken....
Die maximale Rekursionstiefe einer rekursiven Funktion hängt maßgeblich von der Größe des Stapelspeichers ab - und der ist implementationsabhängig (wesentlich) kleiner als der zur Verfügung stehende Arbeitsspeicher.
Häufig lässt sich eine rekursive Lösung in eine iterative umbauen. In diesem Fall könnte man in der entsprechenden Methode ein weiteres Collection-Objekt instanziieren, in welches man das jeweils nächste Element unten reinschiebt, und es dann sequentiell ausgibt, oder die einfache Liste in eine doppel verkettete (oder ähnliches) überführt, und dann entsprechend über den Helfer rückwärts iteriert.

Das wäre wohl aber dann doch zu viel des Guten, und stellt auch nicht das dar, was du erreichen sollst / möchtest. Da ich nicht annehme, dass du mit derart vielen Daten in einem solchen Listenkonstrukt arbeiten musst, ist es zwar nett, dass du über sowas nachdenkst, aber an dieser Stelle nicht allzu kritisch.
Für solide Implemtierungen in konkreten Anwendungen bietet es sich immer an auf die vorgefertigten Klassen aus der STL zurückzugreifen. :)
 
Danke für Eure Antworten.
Eine doppelt Verketteteliste haben wir noch nicht behandelt. Daher auch nur die einfach.

@sheel
Deine gepostete Methode gibt die Liste ganz normal aus, wie die Methode "ausgeben" auch.

C++: 
	void ausgeben_umgekehrt(knoten *a){

	  if(a->next!=NULL)ausgeben_umgekehrt(a->next);
	  cout << a->info << " ";
	}


Aufruf:
C++: 
L.ausgeben_umgekehrt(L.anfang);
 
Zuletzt bearbeitet von einem Moderator:
Ok, wenn ihr die doppelt verkettete Liste noch nicht hattet, dann würde ich die Idee von maeTimmae aufgreifen und eine 2. Liste anlegen.

Die erste Liste ganz normal durchgehen und dabei die Elemente immer wieder in die 2. Liste am Anfang einfügen. Dadurch hast du die Elemente in verkehrter Reihenfolge in der 2. Liste.

Und die 2. Liste gibst du dann "normal" aus.
 
Zuletzt bearbeitet:
Hab mal was gebastelt :)

Code: 
    void ausgeben_umgekehrt()
    {
            struct knoten *p    = anfang;           // p zeigt auf aktuellen Knoten
            struct knoten *last = NULL;
            cout << "Liste umgekehrt: ";
            if (anfang == NULL)
            {
                cout << "liste ist leer" << endl;
                return;
            }
            while (last != anfang)
            {
                p = anfang;
                while (p->next != last)
                {
                    p = p->next;                 // p auf Folgeelement setzen
                }

                if (last != NULL)
                {
                    cout << last->info << " ";
                }
                last = p;           // da p ein Element vor last steht,
                                    // rücken wir last jetzt eins nach vorn
            }
            cout << anfang->info << " ";
    }

Iterative Variante:
Ich leg mir ein "last" knoten an, und bei jedem Durchlauf schieb ich "last" weiter richtig anfang.

MfG Turri
 
Zuletzt bearbeitet:
@Dolphon: Das ist vollkommener Unsinn.
Probiers aus, bevor du sowas schreibst

Es macht einen Unterschied, ob die Ausgabe VOR oder NACH dem If ist...in deiner normalen Ausgabe steht sie vorn
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück