Problem mit Strukturen

[deepthroat]

Glaube wir haben eine unterschiedliche Vorstellung von einem Queue

Das glaube ich nicht. Höchstens von der Verwendung einer Liste als Queue.

Ich würde neue Elemente immer ganz hinten einreihen und dementsprechend beim entfernen die "alten" ganz vorne sprich das erste Element entfernen auf welches man ja sofort mit der Struktur Zugriff hat.

Selbstverständlich werden bei einer Warteschlange die Element hinten eingereiht und vorne entfernt. Das ist ja der Sinn einer Warteschlange und entspricht allgemein dem was man sich unter einer Warteschlange vorstellt (vordrängeln gibt's nicht! ).

Bei einer einfach verketteten Liste hält man immer den Kopf der Liste und hat durch die Verknüpfung auch Zugriff auf den Rest.

Jetzt kommt es drauf an, welcher Teil der Liste nun der Anfang bzw. das Ende der Warteschlange sein soll. Im Grunde ist es ziemlich egal, eine der beiden Operationen enqueue/dequeue hat konstanten Aufwand, die andere linearen Aufwand. Bei mir würde sich das erste Element der Warteschlange das letzte Element in der Liste.

Man kann ja auch nur so ein Dummy Sentinel erzeugen der einmalig ist und den man immer ändern muss bei den Operationen einfügen und entfernen das wäre keine doppelt verkettete Liste.

Kannst du das nochmal näher erläutern? Ich weiß nicht was du meinst...

Gruß

 

[Online-Skater]

Bei mir würde sich das erste Element der Warteschlange das letzte Element in der Liste.

Kannst du das nochmal näher erläutern? Ich weiß nicht was du meinst...

Genau jetzt verstehen wir uns und ich würde es genau andersrum machen.

Das mit dem Sentinel mein ich so:

struct Element
{
        int element;                                /* Zahlenwerte */
        struct Element *n;                          /* Verweis auf Nachfolger */
};

struct Queue
{
        struct Element* first;               // Zeigt immer aufs erste Element
        struct Element* last;               // Zeigt immer aufs letzte Element
}

Somit haben beide Operationen konstanten Aufwand.

mfg

 

[deepthroat]

Genau jetzt verstehen wir uns und ich würde es genau andersrum machen.

Das mit dem Sentinel mein ich so:

struct Element
{
        int element;                                /* Zahlenwerte */
        struct Element *n;                          /* Verweis auf Nachfolger */
};

struct Queue
{
        struct Element* first;               // Zeigt immer aufs erste Element
        struct Element* last;               // Zeigt immer aufs letzte Element
}

Somit haben beide Operationen konstanten Aufwand.

Nein, haben sie nicht. Der Aufwand bleibt gleich. Du müßtest ja bei jeder Operation die first bzw. last Zeiger aktualisieren. Dazu muß bei einer der Operationen wieder die Liste bis zum letzen Element durchsucht werden. Allerdings hast du konstanten Zugriff auf das erste und letzte Element.

Gruß

 

[Online-Skater]

Stimmt du hast Recht, da habe ich wohl übersehen, dass wenn man ein Element am Ende der Liste löscht das Vorgänger Element bräuchte um darauf den LAST-Zeiger zeigen zu lassen.

Hast mich überzeugt -> doppelt verkettete Liste

mfg