Bild Referenz: 
Intro
Hallo, ich bin's @drifter2! Das heutige Thema sind wieder Warteschlangen und Stapel dieses mal aber implementiert mit Listen, die ich euch rate anzusehen. Dieser Artikel ist an zwei meiner englischen Artikel basiert, die ihr bei den Referenzen finden könnt. Da nichts neues in Theorie zu sagen ist und alles nur Code ist, dachte ich mir das eine deutsche Übersetzung der Kommentare und von den Beschreibungen mehr als genug ist. Deswegen mache ich auch einen Artikel für beides gleichzeitig! Also dann fangen wir dann mal an!
Verkettete Liste in C-Sprache
Eine Verkettete Liste ist eine dynamische Datenstruktur die aus Knoten (Nodes auf Englisch) besteht die miteinander verbunden sind. In C-Sprache wird einer solche Knote/Node als struct wie folgend definiert:
typedef struct Node{ int val; struct Node *next;}Node;Diese Ganzzahlen-Knote wird gleich bei beiden Datenstrukturen benutzt!
Warteschlange implementiert mit Verketteter Liste
Eine Warteschlange arbeitet nach dem FIFO-Prinzip. Wir können Elemente nur von dem Anfang (Front-Index) nehmen und Elemente nur am Ende (Rear-Index) hinzufügen. Mit Feldern-Arrays mussten wir Zeiger auf diese Indexe definieren. Mit Listen definieren zwei Knoten-Zeiger (Node pointers) die wir wieder mal auf NULL initialisieren müssen, so dass wir wissen wann die Warteschlange leer ist. Mit der Verwendung von einer Liste hat eine solche Warteschlange nun eine unendliche Kapazität (so viel wie in die RAM passt). Natürlich können wir auch eine gewisse Kapazität als Strukturelement definieren, die bei manchen Anwendung vielleicht von Nöten ist.
Die neue Struktur (struct) die nun eine Warteschlange definiert ist:
typedef struct Queue{ Node *front; Node *rear;}Queue;Wie ihr sehen könnt wurde das Feld und die Indexe mit zwei Zeigern ersetzt!
Bei den Funktionen werden wir wieder mal eine Zeiger-Struktur-Variable benutzen, so dass die Veränderungen abgespeichert werden. Die eigentliche Variable von der main() Funktion muss aber nicht unbedingt ein solcher Zeiger sein, wir können nämlich auch die Speicheradresse verwenden und diese als Parameter an die Funktionen abgeben..
Einfügen(Enqueue):
Wenn man eine Kapazität-Variable definiert hat muss man, wie bei der Feld-Implementierung, wieder mal kontrollieren ob die Warteschlange voll ist. Bei unserer Implementierung werden wir das auslassen.
Wie wir bereits von Listen wissen, müssen wir erstmal ein neues Knoten-Εlement erstellen was wie folgend aussieht:
Node *nn;nn = (Node*)malloc(sizeof(Node));nn->val = val;nn->next = NULL;Wenn die Warteschlange leer ist, dann setzen wir den Front- und Rear-Zeiger zu dieser neuen Knote. Bei jedem anderen Fall fügen wir diese neue Knote am Ende der Warteschlange eine, durch die Benutzung eines Derzeitiger Knoten-Zeigers. Die neue Knote wird dann der neue Rear-Zeiger.
Der Code dafür sieht wie folgend aus:
void enqueue(Queue *Q, int val){ Node *cur, *nn; // Neue Knote erstellen nn = (Node*)malloc(sizeof(Node)); nn->val = val; nn->next = NULL; // Kontrollieren ob Warteschlange leer ist if(Q->front == NULL){ Q->front = Q->rear = nn; } // Genereller Fall else{ // Jetzige Knote-Zeiger auf "Front" setzen cur = Q->front; // Letzte Knote finden while(cur->next != NULL){ cur = cur->next; } // Neue Ende am Ende hinzufuegen cur->next = nn; Q->rear = nn; }}Löschen (Dequeue):
Beim Entfernen eines Elements müssen wir erstmal kontrollieren ob die Warteschlange leer ist. Wenn diese leer ist werde ich '-1' zurückgeben, was uns sagt das die Warteschlange leer ist (natürlich müssen deswegen die Warteschlangen-Elemente nur positive Werte haben). Vor dem löschen müssen wir den Wert vom Front-Index erstmal temporär abspeichern. Wenn das Element das einzige Element der Warteschlange ist dann setzen wir beide Zeiger auf NULL, sonst wird der Front-Zeiger von seinem Nachfolge-Zeiger (next pointer) ersetzt. Am ende geben wir den Wert zurück.
Der Code sieht wie folgend aus:
int dequeue(Queue *Q){ int val; // Kontrollieren ob Warteschlange leer ist if(Q->front == NULL){ return -1; } // Wert von Front abspeichern val = Q->front->val; // Kontrollieren ob es sich um das einzige Element handelt if(Q->front == Q->rear){ Q->front = Q->rear = NULL; } // Einfachster Fall else{ // Front-Zeiger zeigt nun auf seinen Nachfolger Q->front = Q->front->>next; } // Wert zurueckgeben return val; }Ausdrucken (Print):
Wie bei der Implementierung mit Feldern, ist der leichteste Weg um durch die Ganze Warteschlange zu iterieren die Verwendung der dequeue() Funktion solange es Elemente in der Warteschlange gibt! Natürlich könnten wir die Liste auch normal durchlaufen, wie wir bereits von Listen können. Damit wir die Informationen nicht verlieren werden wir nur die Variable verwenden und keinen Zeiger, so dass die Warteschlange nur Lokal (in der Funktion) verändert wird.
Der Code sieht wie folgend aus:
void print(Queue Q){ int val; // Kontrollieren ob Warteschlange leer ist if(Q.front == NULL){ printf("Queue is Empty!\n"); return; } // dequeue() ausfuehren solange es Elemente gibt while((val= dequeue(&Q)) != -1){ printf("%d ", val); } printf("\n");}Komplettes Beispielprogramm:
Zuletzt hier noch ein komplettes Beispielprogramm:
int main(){ // Warteschlange initialisieren Queue Q; Q.front = Q.rear = NULL; print(Q); // 5 einfuegen enqueue(&Q, 5); print(Q); // 10 einfuegen enqueue(&Q, 10); print(Q); // Elemente rausnehmen int val; val = dequeue(&Q); if(val == -1){ printf("Queue is Empty!\n"); } else{ printf("%d\n", val); } print(Q); }Stapel implementiert mit Verketteter Liste
Ein Stapel arbeitet nach dem LIFO-Prinzip. Was also zuletzt hinzugefügt wird, wird als erstes wieder weggenommen. Man hat also nur Zugriff auf das oberste (top) Stapelobjekt. Ähnlich wie bei der Implementation mit Feldern-Arrays wo wir diesen Top-Index abspeichern mussten, werden wir hier einen Top-Zeiger haben, der auch das einzige Element der Struktur sein wird! Durch die Verwendung von einer Liste haben wir nun einen Stapel der unendlich viele Elemente abspeichern kann. Wenn eine Anwendung eine gewisse Kapazität benötigt dann können wir zusätzlich auch eine Kapazität-Variabel deklarieren.
Ohne diese zusätzliche Info sieht der struct des Stapels wie folgend aus:
typedef struct Stack{ Node *top;}Stack;Der Top-Zeiger muss natürlich auf NULL initialisiert werden (ähnlich wir top-Index auf -1 gesetzt wurde), so dass wir wissen ob der Stapel leer ist.
Bei den Funktionen werden wir wieder mal eine Zeiger-Struktur-Variable verwenden. Die eigentliche Struktur kann auch als normal Struktur-Variable definiert werden, da wir ja auch die Speicheradresse als Parameter abgeben können.
Einfügen (Push):
Beim hinzufügen eines neuen Elements müssen wir erstmal kontrollieren ob der Stapel voll ist. Das ist natürlich nur von Nöten wenn man eine gewisse Stapel-Kapazität definiert hat.
Zuerst, erstellen wir eine neue Knote, wie vorhin bei der Warteschlange (deswegen lasse ich das mal aus). Der spezial Fall hier ist wieder mal der leere Stapel, wo wir den Top-Zeiger durch den neuen Knoten-Zeiger ersetzen (Top-Zeiger auf Knoten-Zeiger setzen). Wenn es bereits Elemente gibt dann wird der Nachfolger-Zeiger der neuen Knote zu dem jetzigen Top-Zeiger gesetzt und die neue Knote der neue Top-Zeiger.
All das sieht mit Code wie folgend aus:
void push(Stack *S, int val){ Node *nn; // Neue Knote erstellen nn = (Node*)malloc(sizeof(Node)); nn->val = val; nn->next = NULL; // Wenn Stapel nicht leer ist if(S->top != NULL){ // make nn's next point to top nn->next = S->top; } // sonst wird nn->next NULL bleiben! // Neue Knote wird neuer Top-Zeiger S->top = nn; }Löschen-Entfernen (Pop):
Beim Löschen müssen wir kontrollieren ob der Stapel leer ist, wo wir wieder mal '-1' zurückgeben werden. Vor dem entfernen müssen wir den Wert vom Top erstmal temporär abspeichern. Danach wir dieser Zeiger einfach durch seinen Nachfolger-Zeiger (next pointer) ersetzt.
Der Code dafür ist:
int pop(Stack *S){ int val; // Kontrollieren ob Stapel leer ist if(S->top == NULL){ return -1; } // Wert von Top abspeichern val = S->top->val; // Top auf seinen Nachfolger zeigen lassen S->top = S->top->next; // Wert zurueckgeben return val; }Ausdrucken (Print):
Ähnlich wie bei der Feld-Implementierung, werden wir wieder mal die pop() Funktion ausführen solange der Stapel nicht leer ist. Damit wir den Stapel nicht verändern werden wir nun eine "normale" Struktur-Variable verwenden und nicht die eigentliche Adresse.
Das sieht in Code wie folgend aus:
void print(Stack S){ int val; // Kontrollieren ob Stapel leer ist if(S.top == NULL){ printf("Stack is Empty!\n"); return; } // pop() solange es Elemente im Stapel gibt while((val = pop(&S)) != -1){ printf("%d ", val); } printf("\n");}Komplettes Beispielprogramm:
Zuletzt hier noch ein Beispielprogramm:
int main(){ // Stapel initialisieren Stack S; S.top = NULL; print(S); // 3 hinzufuegen push(&S, 5); print(S); // 7 hinzufuegen push(&S, 10); print(S); // 2 hinzufuegen push(&S, 2); print(S); // Element vom Stapel entfernen int val; val = pop(&S); if(val == -1){ printf("Queue is Empty!\n"); } else{ printf("%d\n", val); } print(S); }Notiz:
Ihr habt vielleicht bemerkt das beide Beispielprogramme die gleichen sind die wir auch bei den "Feld-Artikeln" hatten. Das einzige das sich geändert hat ist die Initialisierung der Strukturen, da wir jetzt die Zeiger (front, rear und top) auf NULL setzen müssen. Bei Feldern wurden die Indexe ja auf '-1' initialisiert!
Referenzen:
- https://steemit.com/programming/@drifter1/programming-c-queues-using-linked-lists
- https://steemit.com/programming/@drifter1/programming-c-stacks-using-linked-lists
Vorherige Artikel
Grundlagen
Einführung -> Programmiersprachen, die Sprache C, Anfänger Programme
Felder -> Felder, Felder in C, Erweiterung des Anfänger Programms
Zeiger, Zeichenketten und Dateien -> Zeiger, Zeichenketten, Dateiverarbeitung, Beispielprogramm
Dynamische Speicherzuordnung -> Dynamischer Speicher, Speicherzuweisung in C, Beispielprogramm
Strukturen und Switch Case -> Switch Case Anweisung, Strukturen, Beispielprogramm
Funktionen und Variable-Gueltigkeitsbereich -> Funktionen, Variable Gueltigkeitsbereich
Datenstrukturen
Rekursive Algorithmen -> Rekursion, Rekursion in C, Algorithmen Beispiele
Verkettete Listen -> Datenstrukturen generell Verkettete Liste, Implementation in C (mit Operationen/Funktionen), komplettes Beispielprogramm
Binäre Suchbäume -> Baum Datenstruktur generell, Binärer Baum, Binärer Suchbaum, Implementation in C-Sprache (mit Operationen/Funktionen), komplettes Beispielprogramm
Warteschlangen implementiert mit Feldern -> Warteschlange als Datenstruktur, Implementation einer Warteschlange mit Feldern in C-Sprache, komplettes Beispielprogramm
Stapel implementiert mit Feldern -> Stapel als Datenstruktur, Implementation eines Stapels mit Feldern in C-Sprache, komplettes Beispielprogramm
Schlusswort
Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Νächstes mal werden wir über fortgeschrittene Listen und Warteschlangen reden!
Keep on drifting! ;)