Verständnisproblem verkettete Listen

Hallo Leute,

ich hab echt ein Problem!
Hab mir grad Volkards tut durchgearbeitet!

Und ich hab echt ein Problem, verkettete Listen zu verstehen!

Kann das hier vielleicht mal jemand GANZ genau und auch für DAUs erklären??

Mit guten Beispieln und so?? Blick das irgendwie echt nicht!

GPC

Was GENAU verstehst du nicht? Stell konkrete Fragen!

Ansonsten: STFW und du findest z.B. http://de.wikipedia.org/wiki/Verkettete_Liste

Na zum Beispiel, wie die Klassen aufgebaut sein müssen!

Ich weiß net, hab mir das schon durchgelesen, und das prinzip versteh ich auch, aber bei der praktischen anwendung haperts!

Vielleicht könnt ihr mal ein erklärtes beispiel geben?

zum beispil interessiert mich auch wie ich auf spezielle elemente zugreifen kann!
Daten ausgeben etc...

CStoll

boahnee schrieb:

zum beispil interessiert mich auch wie ich auf spezielle elemente zugreifen kann!
Daten ausgeben etc...

Indem du dich stückweise durch die Liste durchhangelst (vom Start weg immer dem next-Zeiger folgen, bis du bei deinem Ziel angekommen bist).

Listen läuft man normalerweise komplett durch und macht für jedes Element etwas.

ok, wie gesagt, das theoretische prinzip hab ich verstanden, aber die praxis garnicht!

Könnt ihr mir mal ein gutes beispiel geben??

GPC

Also, ich zeig dir jetzt einen eher simplen Ansatz, wie man eine doppelt-verkettete Liste implementieren kann:

Das hier stellt ein Element in der Liste dar, wir machen's mal ohne Templates und nehmen eine Liste für ints. Ein Zeiger auf das nächste, einer auf das vorherige Element und natürlich die Daten:

struct ListElement {
  ListElement(int val) : next(0), prev(0), value(val) {}
  //Copy Ctor, Dtor, Zuweisung usw.

  ListElement *next;  //Zeiger auf das nächste Element
  ListElement *prev;  //Zeiger auf das vorherige Element

  int value;
};

Jetzt kommen wir zur Liste, die ListElemente verwaltet, der Zeiger first zeigt immer auf das erste Element und der last Zeiger zeigt auf das letzte Element. Diese Zeiger allokieren keinen dynamischen Speicher, sie verweisen nur auf Elemente, um die Liste abzugrenzen. Bei dieser Liste ist das Einfügen des ersten Elements ein Spezialfall, deshalb die Bedingung in der append und prepend Methode, gleiches gilt für die removeFirst Methode. Hier ist das Löschen des letzten verbleibenden Elements ein Spezialfall. Schau's dir einfach mal an.

class List {
  ListElement *first, *last;
  size_t size_;

  //Löscht alle Elemente
  void cleanup() {
    ListElement *toDie=last, *prev=0;
    while(size_) {
        prev = toDie->prev;
        delete toDie;
        toDie = prev;
        --size_;
    }
  }

  public:
    List() : first(0), last(0), size_(0) { }
    ~List() {
      cleanup();
    }
    //Copy Ctor und Zuweisung usw. ...

    const ListElement * getFirst() const { return first; };
    const ListElement * getLast() const { return last; };

    size_t size() const { return size_; }  //Anzahl der Elemente
    bool empty() const { return (size_) ? false : true; }  //Ist Liste leer?
    void clear() { cleanup(); }  //Alle Elemente löschen

    //Element anhägen
    void append(int val) {
        ListElement *elem = new ListElement(val);  //Neues Element erstellen
        if (last == 0) {  //Liste ist noch leer, d.h. wir fügen erstes Element ein
          first = last = elem;  //first und last zeigen beide auf elem

          //Damit klar ist, wo's losgeht und wo's aufhört ;-)
          first->prev = 0;
          last->next = 0;
        }
        else  {  //Liste nicht leer, diesmal hängen wir wirklich an
          last->next = elem;  //Altes letztes Element auf neues letztes zeigen lassen
          elem->prev = last;  //Rückwärts genauso

          last = elem;  //last zeigt auf neues letztes Element
        }
        ++size_;
    }

    //Element am Anfang einfügen
    void prepend(int val) {
        ListElement *elem = new ListElement(val);  //Neues Element erstellen
        if (first == 0) {  //Liste ist noch leer, d.h. wir fügen erstes Element ein
          first = last = elem;  //first und last zeigen beide auf elem

          //Damit klar ist, wo's losgeht und wo's aufhört ;-)
          first->prev = 0;
          last->next = 0;
        }
        else  {  //Liste nicht leer,
          first->prev = elem;  //Altes erstes Element auf neues erstes zeigen lassen
          elem->next = first;  //Vorwärts genauso

          first = elem;        //first zeigt jetzt auf neues erstes Element
        }
        ++size_;
    }

    //Löscht das erste Element
    void removeFirst() {
        ListElement *toDie = first;  //Erstes Element sichern
        first = first->next;  //Auf neues erstes Element zeigen
        if (first)
          first->prev = 0;
        else  //Wenn wir das einzige Element löschen --> Spezialfall
          first = last = 0;

        delete toDie;
        --size_;
    }

    //Gibt Liste auf os aus
    void print(ostream& os) {
      if(!size_)
        return;

      ListElement *it = first;
      for (int i=0;i<size_;++i) {
        os<<it->value<<'\n';
        it = it->next;
      }
    }
};

int main() {
  List l;

  //3 Elemente anhängen
  l.append(1);
  l.append(2);
  l.append(3);

  l.removeFirst();  //1 rausholen

  //1 am Anfang einfügen
  l.prepend(-1);
  l.print(cout);
  return 0;
};

Wie gesagt, ein eher spartanischer Ansatz (und ich hab mir auch nicht wirklich Mühe gegeben), aber vllt. hilft's dir ja...

boahnee schrieb:

Hallo Leute,
ich hab echt ein Problem!
Hab mir grad Volkards tut durchgearbeitet!
Kann das hier vielleicht mal jemand GANZ genau und auch für DAUs erklären??
Mit guten Beispieln und so?? Blick das irgendwie echt nicht!

Schau dir mal cbItemList aus cbccl an. Ist eine verkettete Liste
mit Cache: http://www.sf.net/projects/cbccl .

Du kannst Dir eine verkettete Liste wie eine Menge Briefkasten
vorstellen, wo Dir nur der erste Briefkasten bekannt ist und Du
den jeweils in einem Briefkasten findest, wo der nächste ist.

Panke

Du kannst Dir eine verkettete Liste wie eine Menge Briefkasten
vorstellen, wo Dir nur der erste Briefkasten bekannt ist und Du
den jeweils in einem Briefkasten findest, wo der nächste ist.

Oder als Wurstkette. Das geht auch.