Frage zu Listen

blurry333

Habe folgende Funktion zum einfügen eines Elements:

void insertAfter(ListeDopVerkZahlen_t *list, int val)
  {
   KnotenDopVerkZahlen_t *neuerKnoten=(KnotenDopVerkZahlen_t *)malloc(sizeof(*neuerKnoten));

   neuerKnoten->dat=val;

   if (list->curr!=NULL)
     {
      neuerKnoten->prev=list->curr;
      neuerKnoten->next=list->curr->next;

      if (list->curr->next!=NULL) list->curr->next->prev=neuerKnoten;
      if (list->tail==list->curr) list->tail=neuerKnoten;
     }
   else
     {
      neuerKnoten->prev=NULL;
      neuerKnoten->next=NULL;

      list->tail=list->curr=neuerKnoten;
       if (list->head==NULL)list->head=neuerKnoten; //Warum diese if Prüfung ??
     }
   list->curr=neuerKnoten;
   if (list->curr->prev!=NULL) list->curr->prev->next=neuerKnoten;
  }

Es geht also darum ein Element nach einem aktuellen einzufügen.
Der else Zweig wird durchlaufen wenn der aktuelle Zeiger auf dem Pseudoknoten
steht. d.h also die Liste ist noch leer. Dort wo ich den Kommentar hingeschrieben habe , frage ich mich warum man den Zeiger, der auf das 1.Listenelement zeigen soll, noch auf Null prüfen muss, wo doch die liste
eh leer ist, er also auf Null zeigt.

Nimm doch C++ (new) statt C (malloc)

Was soll denn ->curr und ->tail sein? ->dat, ->prev, ->next ist ja klar.

Pseudoknoten? Wozu das denn? Braucht man nicht!

struct Knoten
{
  Knoten* prev;
  Knoten* next;
  int dat;

  explicit Knoten(int z) : prev(0),next(0),dat(z) {}
};

/*
 *                  +------+    +------+
 * liste.start ---> |     ====> |     -+-->   nil
 *         nil   <--+-     | <--+-     | <--- liste.ende
 *                  +------+    +------+
 *                     A            A
 *                     |  +[neu]-+  |
 *                     |  |     -+--+
 *                     +--+-     |
 *                        +------+
 *
 * zeigerVLNR = von links nach rechts (===>)
 */
void pack_dazwischen(Knoten*& zeigerVLNR, int zahl)
{
  Knoten* pn = new Knoten(zahl);
  pn->next = zeiger;
  if (zeiger) pn->prev = zeiger->prev;
  if (pn->next) pn->next = pn;
  if (pn->prev) pn->prev = pn;
  zeigerVLNR = pn;
}

class Liste
{
  Knoten *start, *ende;
public:
  Liste() : start(0), ende(0) {}
  ...
};

(ungetestet)

Beachte: zeigerVLNR ist eine Referenz -- entweder auf einen next-Zeiger eines Knotens oder auf den start-Zeiger der Liste.

kruemelkacker schrieb:

void pack_dazwischen(Knoten*& zeigerVLNR, int zahl)
{
  Knoten* pn = new Knoten(zahl);
  pn->next = zeiger;
  if (zeiger) pn->prev = zeiger->prev;
  if (pn->next) pn->next = pn;
  if (pn->prev) pn->prev = pn;
  zeigerVLNR = pn;
}

Mist! Das muss heißen:

if (pn->next) pn->next->prev = pn;
  if (pn->prev) pn->prev->next = pn;

Aber da ist sicherlich noch etwas falsch bei diesen vielen Zeigern.
Das Prinzip sollte aber klar sein. So kommt man auch ohne Pseudoknoten aus.

blurry333

pseudoknoten sind knoten ohne daten.

Ist schon hilfreich. Man hat einen head der auf den Anfang der Liste zeigt
und einen tail zeiger der eben auf das Ende zeigt. So kann man schnell
zum anfang bzw Ende navigieren.

pumuckl

blurry333 schrieb:

Ist schon hilfreich. Man hat einen head der auf den Anfang der Liste zeigt
und einen tail zeiger der eben auf das Ende zeigt. So kann man schnell
zum anfang bzw Ende navigieren.

Dazu braucht man eigentlich trotzdem keinen Pseudoknoten.

DocShoe

Diese Pseudoknoten (habe ich unter dem Namen Sentinels kennengelernt) erfüllen noch einen weiteren Zweck: Sie eliminieren die Sonderfälle für das Einfügen/Löschen am Anfang/Ende der Liste.

Sebastian Pizer

DocShoe schrieb:

Diese Pseudoknoten (habe ich unter dem Namen Sentinels kennengelernt) erfüllen noch einen weiteren Zweck: Sie eliminieren die Sonderfälle für das Einfügen/Löschen am Anfang/Ende der Liste.

Mit Referenzen auf Zeigern, wie sie kruemelkacker benutzt hat, lässt sich die Sonderbehandlung reduzieren. Ich finde, die Sonderbehandlung hält sich da in Grenzen und lässt sich bestimmt noch ein wenig vereinfachen. Ich sehe nicht, wie "Pseudoknoten" einen richtigen Vorteil bieten. Im Gegenteil, wo und wie soll man sie denn anlegen -- so ohne Inhalt und dass man auch noch drauf Zeigen kann? Wo spare ich denn da Sonderbehandlung? Zeig mal ...