ATOS - Around The Operating System Das ATOS-Magazin 3/96

Dynamische Datenstrukturen 5-6

Einträge einfügen

Möchten wir nun einen Eintrag einfügen, müssen wir folgende Schritte durchführen:

einen Speicherblock beantragen (malloc/new)
den Speicherblock mit den Daten füllen
die richtige Position in der Liste suchen, in der das neue Element eingefügt werden soll.
die Kette an der richtigen Position aufbrechen (alten Zeiger speichern!!)
das neue Element einhängen
den Rest der Kette an das neue Element hängen.

Der neue Eintrag soll zwischen Eintrag 2 und 3 eingefügt werden:

Der Zeiger von Eintrag 2 muß auf den neuen Eintrag gesetzt werden, und der Zeiger des neuen Eintrags muß auf Eintrag 3 gesetzt werden.

Der Quelltext (in C):

Es wird ein Element in eine sortierte Liste eingefügt. Die Liste ist nach CD-Titel geordnet.

int einfuegen(Eintrag **anfang, Eintrag *neuesElement)
{
    Eintrag *neu;         /* zeigt auf den neuen Speicherblock */
    Eintrag *vorgaenger;  /* Zeiger auf den Vorgänger */
    Eintrag *fokus;       /* Zeiger auf das betrachtete Element */
    int ergebnis;         /* das Ergebnis des Stringvergleichs */

    neu = malloc(sizeof(Eintrag));  /* Speicher holen */

    if (!neu)             /* Fehlschlag? (malloc liefert NULL zurück) */
        return(FALSE);    /* Dann konnte es nicht eingefügt werden */

        /* Eintrag übernehmen */
    memcpy(neu, neuesElement, sizeof(neuesElement));

        /* ist der neue Titel der kleinste? */
    if (strcmp((*anfang)->titel, neu->titel) < 0) {
            /* dann neues Element vor den Anfang
               setzen */
        neu->next = *anfang;
            /* neuen Anfang setzen */
        anfang = &neu;
    }
    else {
        vorgaenger = *anfang;     /* Hilfszeiger auf Anfang setzen */

            /* solange der neue Titel größer ist, als der
               aktuelle... */
        do {
            fokus = vorgaenger->next;

            if (fokus != NULL)
            {
                ergebnis = strcmp(fokus->titel, neu->titel);
                vorgaenger = fokus;
            }
        } while (fokus != NULL && ergebnis >= 0);
    } /* else */

        /* nun steht fokus auf dem nächst größeren
           Element und vorgaenger auf dem Element,
           direkt davor. Unser Element muß also genau
           dazwischen. */

    vorgaenger->next = neu;  /* dem Vorgaenger unser neues Element
                                als nächstes geben */
    neu->next = fokus;       /* und den Rest hinter das neue Element
                                hängen */
    return(TRUE);
}

Dieser Quelltext hat keinen Anspruch auf die beste Lösung, aber ich hoffe, daß er einigermaßen gut nachzuvollziehen ist.

Nun werden Sie sagen: "Das ist aber wohl kaum schnell beim Suchen!" - Stimmt. Aber es ist dynamisch, d.h. es faßt soviele Einträge, wie Speicherplatz vorhanden ist und beim Einfügen muß nicht ein einziges Element eines Feldes (Array) verschoben werden.

Anmerkung: Die Zeiger mögen Sie vielleicht etwas verwirren, wenn Sie Pascal kennen, ersetzen Sie einfach alle '->' durch '^.'!

Gebrauch

Hat man sich erst mal an die etwas kompliziert erscheinende Schreiberei gewöhnt, sind diese verketteten Listen wirklich sehr gut und leicht zu benutzen.

Diese verketteten Listen werden wirklich viel verwendet, denn es bietet gegenüber Feldern den erheblichen Vorteil, unbekannte Mengen aufnehmen zu können.

Und wie sieht es mit der Geschwindigkeit aus?