Liste umdrehen (einfach verkettete)

MarcR

Hallo, ich möchte gerne die Liste umdrehen, also das erste Element soll nun das letzte sein und das letzte Element das erste.

Es gibt zwar die STL-Funktion aber die wollte ich erstmal nicht benutzen.

const int MAX = 10;

struct Puffer {
  char D[MAX];
  int Anfang, Ende;
};

void leere (Puffer& P) {            // Referenzparameter (wird verändert)
  P.Anfang = P.Ende = 0;
}

boolean istLeer (Puffer P) {        // Wertparameter (wird nur abgefragt)
  return P.Anfang == P.Ende;
}

boolean istVoll (Puffer P) {
  return P.Anfang == (P.Ende + 1) % MAX;
}

void lege (Puffer& P, char c) {     // Einschränkung:
  if (istVoll (P)) return;          // Fehler wird ignoriert!
  P.D[P.Ende++] = c;
  if (P.Ende >= MAX) P.Ende = 0;
}

char entnimm (Puffer& P) {
  if (istLeer (P)) return '\0';     // dto.
  char z = P.D[P.Anfang++];
  if (P.Anfang >= MAX) P.Anfang = 0;
  return z;
}

Öh, und wo ist nun die einfach verkettete Liste?!? Oder willst Du den C-String umdrehen?

MarcR

also die Anordnung der Elemente des Puffers sind in einem Vektor der Länge MAX, das ist richtig. ^^ Nun möchte wollte ich zusätzlich noch eine funktion schreiben die diese Liste halt umdreht, und zwar so das die einzelnen Elemente des vektors vertauscht werden.

XaTrIxX

Gut:

du musst halt anfangen auf eine Lösungsidee zu kommen.

Also du könntest sagen: ok ich vertausch immer die 2 aneinanderliegenden:

a->b = b->a

geht hier aber nicht mehr:

a->b->c->d = d->a->b->c

jetzt könnte man sagen: gut, je mehr elemente desto öfter werd ich das wohl machen müssen.
also muss die anzahl der schleifendurchläufe wohl mit anzahl der listenelemente zusammenhängen.

Übrigends:

ich nehme an die Elemente sollen auch auf die neu angeordneten richtig zeigen.

also aus a->b->c->d wird d->c->b->a richtig?

also könntest du es so machen, dass der pointer auf das nächste element in der vertauschten liste zeigt.

Das ist einmal ein so selbst zusammengefädelter lösungsansatz.
Bin auf deine antwort gespannt.

Werner Salomon

Hier ist es meines Erachtens sinnvoll, das Problem in zwei Teile zu zerlegen.
1.) es muss eine Möglichkeit geschaffen werden, über alle Elemente des Puffers zu laufen
2.) der eigentliche Algorithmus reverse zum Vertauchen der Reihenfolge der Elemente im Puffer

Zu 1.) eignet sich ein Iterator - etwa so was:

struct PufferIterator
{
    Puffer* m_puffer;
    int m_idx;
};

Ein Objekt dieser Struktur zeigt auf genau ein Element in einem Puffer - also in diesem Fall auf m_puffer->D[m_idx].

Zum Traversieren muss man diesen Iterator hoch- und runterzählen können. Ich mache jetzt mal in dem Stil weiter, wie Du den Puffer aufgebaut hast. Dann ergeben sich zwei Funktionen zum inkrementieren (inc: hochzählen) und Dekrementieren (dec: runterzählen).

PufferIterator& inc( PufferIterator& pi )
{
    if( ++pi.m_idx >= MAX )
        pi.m_idx = 0;
    return pi;
}
PufferIterator& dec( PufferIterator& pi )
{
    if( pi.m_idx-- == 0 )
        pi.m_idx = MAX-1;
    return pi;
}

Für den Zugriff auf das aktuelle Element und für den Vergleich zweier Iteratoren - wird im Algorithmus benötigt - braucht man noch einen !=-Operator und das Dereferenzieren (deref) - also den Zugriff auf das aktuelle Element.

bool operator!=( const PufferIterator& a, const PufferIterator& b )
{
    return a.m_idx != b.m_idx || a.m_puffer != b.m_puffer;
}
char& deref( const PufferIterator& pi )
{
    return pi.m_puffer->D[ pi.m_idx ];
}

Das hat bisher zunächst gar nichts mit dem gesuchten Algorithmus zu tun; erleichtert aber dessen Erstellung ganz enorm.

Wegen der besseren Übersichtlichkeit im Code verpasst man dem Iterator noch einen Konstruktor. Dann ändert sich die struct PufferIterator zu:

struct PufferIterator
{
    PufferIterator( Puffer& P, int idx )
        : m_puffer( &P )
        , m_idx( idx )
    {}
    Puffer* m_puffer;
    int m_idx;
};

Bevor ich jetzt zu reverse komme, zunächst ein Beispiel, wie der Iterator angewendet wird:

#include <iostream>
// Puffer & PufferIterator (s.o.)

int main()
{
    using namespace std;
    Puffer buf;
    leere( buf );   // notwendig, da Default-Konstruktor fehlt

    // --   ein wenig Puffer-Aktion
    for( char c = 'a'; c != 'e'; ++c )
        lege( buf, c );
    while( !istLeer( buf ) )
        entnimm( buf );
    for( char c = '1'; c != '9'; ++c )
        lege( buf, c );

    // --   Puffer ausgeben
    for( PufferIterator i( buf, buf.Anfang ); i != PufferIterator( buf, buf.Ende ); inc( i ) )
        cout << deref( i );
    cout << endl;
    return 0;
}

Man sieht jetzt, dass in der Schleife keine Rücksicht mehr darauf genommen werden muss, dass der interne Index 'm_idx' beim Inkrementieren am Ende des Arrays D[] wieder auf 0 gesetzt werden muss. Dies ist in den Funktionen inc bzw. dec versteckt.

Der Iterator ist zwar nicht Standard-konform , aber trotzdem ein echter Iterator.

Zu 2.): Der Algorithmus reverse beginnt von beiden Seiten - also Anfang und Ende - und tauscht einfach die Elemente aus, bis die beiden Iteratoren sich in der Mitte treffen.

void reverse( PufferIterator von, PufferIterator bis )
{
    for( ; von != bis && von != dec( bis ); inc( von ) )
    {
        // swap( *von, *bis );
        char tmp = deref( von );
        deref( von ) = deref( bis );
        deref( bis ) = tmp;
    }
}

Der Aufruf ist Dank des Konstruktors von PufferIterator ganz einfach (vor Zeile 18 im main() einfügen):

// --   Reihenfolge im Puffer 'buf' umdrehen
    reverse( PufferIterator( buf, buf.Anfang ), PufferIterator( buf, buf.Ende ) );

Das, was Du programmierst hast, ist übrigens keine Liste sondern eine Queue bzw. Pipe. Das leere heißt clear(), istLeer ist empty(), lege heißt push() bzw. push_back() und entnimm heißt pop() bzw. pop_front() bzw. der Zugriff auf das erste Element heißt top() bzw. front().

Noch ein Tipp: mache die Konstante MAX zu einer statischen Variablen in der Klasse Puffer.

Gruß
Werner