proggen.org

Verfasst: **Fr Feb 21, 2014 3:57 pm**

Tach,

Ich versuch in letzter Zeit ein paar Algorithmen zu verstehen und anschließend auch nachzuprogrammieren. Gerade bin ich dabei, Merge-Sort zu implementieren, allerdings stellen sich mir einige Fragen.
Wer nicht weiß worum es dabei geht, siehe Wikipedia: http://de.wikipedia.org/wiki/Mergesort
Mir geht es weniger um die Logik, sondern um das Aufspalten der Liste.

Angenommen man hat n Elemente in einer Liste. Wie soll ich dann die Liste zur Hälfte aufspalten wenn ich nicht weiß was n ist.
Die einzige Möglichkeit, die ich mir überlegt habe ist beim Hinzufügen eines Knotens einen Zähler mitzählen zu lassen. Danach soll mit einer Zählschleife

Code: Alles auswählen

for(i = 0; i < (listSize+1)/2; i++) // +1 im Falle einer ungeraden Anzahl

bis zur Hälfte von n gezählt werden um dann den Anfang der zweiten Liste zu bestimmen.
Ist das die einzige Möglichkeit? Das erscheint mir bei einer großen Anzahl von n ein wenig unsinnig, auch wenn Rechner das heutzutage schnell hinbekommen.

Grüße Chris

Verfasst: **Fr Feb 21, 2014 4:09 pm**

Angenommen man hat n Elemente in einer Liste. Wie soll ich dann die Liste zur Hälfte aufspalten wenn ich nicht weiß was n ist.
Die einzige Möglichkeit, die ich mir überlegt habe ist beim Hinzufügen eines Knotens einen Zähler mitzählen zu lassen. Danach soll mit einer Zählschleife

Du musst die Anzahl der Elemente zählen. Entweder zählst du alle Elemente durch, oder hast einen Zähler der beim Anlegen und hinzufügen der Elemente mitzählt.
Die Angabe, wie viele Elemente du in einer Datenstruktur hast, ist sowieso eine essentielle, du wirst dieses Attribut immer haben.

bis zur Hälfte von n gezählt werden um dann den Anfang der zweiten Liste zu bestimmen.
Ist das die einzige Möglichkeit? Das erscheint mir bei einer großen Anzahl von n ein wenig unsinnig, auch wenn Rechner das heutzutage schnell hinbekommen.

Wieso musst du zählen? Hast du eine verkettet Liste?
Im Grunde musst du auf Element n/2 zugreifen. Wenn du keine Möglichkeit hast das direkt zu machen, dann musst du iterieren.

Verfasst: **Fr Feb 21, 2014 4:40 pm**

cloidnerux hat geschrieben:Du musst die Anzahl der Elemente zählen. Entweder zählst du alle Elemente durch, oder hast einen Zähler der beim Anlegen und hinzufügen der Elemente mitzählt.
Die Angabe, wie viele Elemente du in einer Datenstruktur hast, ist sowieso eine essentielle, du wirst dieses Attribut immer haben.

Oke dann komme ich da wohl nicht drum herum.

cloidnerux hat geschrieben:Wieso musst du zählen? Hast du eine verkettet Liste?
Im Grunde musst du auf Element n/2 zugreifen. Wenn du keine Möglichkeit hast das direkt zu machen, dann musst du iterieren.

Ja, ich benutze eine linked list. Na Die Zählschleife zählt ja bis zum n/2 ten Element, also genau das was ich haben möchte. Für mich ist das zählen.

Code: Alles auswählen

for(i = 0; i < ((listSize+1)/2); i++)
        {
            node = node->next;
        }

Danke

proggen.org

Merge-Sort

Merge-Sort

Re: Merge-Sort

Re: Merge-Sort