Resource icon

[C] Deque (Doppelschlange) für beliebige Typen als doubly-linked list (doppelt verkettete Liste) 1.0

No permission to download
Programmiersprache(n)
C
Betriebssystem(e)
unspezifisch
Ein Deque vereint die Funktionalität von einem Stack (Stapelspeicher) und einem Queue (Warteschlange). Das Deque hält also einen Pointer auf das erste Element (head) und einen Pointer auf das letzte Element (tail) eines Containers mit den zu speichernden Werten. In dieser Implementierung wird zusätzlich die Anzahl der gespeicherten Werte (size) und ein Fehlerindikator (err) verwaltet. Als Schnittstelle wird lediglich ein Pointertyp (ud_t) benötigt, der auf das erstellte Deque zeigt.
Schema:
deque.png


Der Container für die Werte ist eine doppelt verkettete Liste. Die Elemente halten neben dem Pointer auf das vorherige Element (previous) und dem Pointer auf das nachfolgende Element (next), den Pointer data auf den eigentlichen zu speichernden Wert. Dieser Wert kann ein beliebiger Datentyp sein, sollte aber für das gesamte Deque einheitlich sein, da keine Information darüber gespeichert wird, wie groß der Speicherbereich ist, auf den data zeigt.
Schema für die verkettete Liste:
list_detail.png


Auch wenn das Deque die beste Performance mit einer Zeitkomplexität von O(1) nur dann zeigt, wenn wie vorgesehen auf den Anfang oder das Ende der Liste zugegriffen wird, enthält diese Lib auch Funktionen die es erlauben auf beliebige Positionen zuzugreifen, Werte sequenziell zu verarbeiten, Werte zu suchen, sowie die Liste umzukehren, zu sortieren und Elemente sortiert einzufügen.

Um die Benutzung zu vereinfachen, gibt es bereits spezialisierte Funktionen für Basistypen (Zeichen, Ganzzahlen, Fließkommazahlen) und nullterminierte Strings (char* und wchar_t*). Durch die Definition des Makros UD_TYPE kann ein Typ für das Deque festgelegt und Macros mit einheitlichen Macronamen statt den spezialisierten Funktionsnamen verwendet werden. Siehe hierzu die Kommentare Zeile 128 ff. in "uni_deque.h".

Funktionsnamen zur Verarbeitung der Daten folgen einer vereinheitlichten Nomenklatur mit folgenden Schlüsselbegriffen:
- Push
Anfügen eines neuen Listenelements am Anfang oder Ende der Liste.
- Insert
Einfügen eines neuen Listenelementes in den Verlauf der Liste.
- Pop
Entfernen eines Listenelements am Anfang oder Ende der Liste.
- Erase
Entfernen eines Listenelementes im Verlauf der Liste.
- Remove
Entfernen eines Listenelementes anhand seines Wertes.
- Front
Zugriff auf den Beginn der Liste.
- Back
Zugriff auf das Ende der Liste.
- At
Zugriff auf ein Element im Verlauf der Liste.
- Sort
Sortieren der Liste.
- Asc
Aufsteigende Reihenfolge.
- Desc
Absteigende Reihenfolge.
- Find
Suche des Index eines Listenelementes in der Liste anhand seines Wertes.

Die ersten 250 Zeilen in "uni_deque.h" enthalten eine Reihe weiterer Informationen in den Kommentaren. Natürlich gibt es auch ein Beispiel in der "main.c", bei dem dieselbe Funktionalität einmal mit Werten vom Typ long int und einmal mit Strings aufgezeigt wird.

Der Code findet sich auf GitHub und wird dort aktualisiert:
https://github.com/german-one/uni_deque
Gefällt mir: lano
Autor
German
Downloads
1
First release
Last update
Bewertung
0,00 Stern(e) 0 Bewertungen
Oben