Programmieren in C - Warteschlangen und Stapel implementiert mit Verketteten Listen

in #programmieren6 years ago

Bild Referenz: https://commons.wikimedia.org/wiki/File:C_language_linked_list.png

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:

  1. https://steemit.com/programming/@drifter1/programming-c-queues-using-linked-lists
  2. 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! ;)

Sort:  

Hello! Your post has been resteemed and upvoted by @ilovecoding because we love coding! Keep up good work! Consider upvoting this comment to support the @ilovecoding and increase your future rewards! ^_^ Steem On!

Reply !stop to disable the comment. Thanks!

@drifter2, I gave you a vote!
If you follow me, I will also follow you in return!
Enjoy some !popcorn courtesy of @nextgencrypto!



This post has been voted on by the steemstem curation team and voting trail.

There is more to SteemSTEM than just writing posts, check here for some more tips on being a community member. You can also join our discord here to get to know the rest of the community!

Hi @drifter2!

Your post was upvoted by utopian.io in cooperation with steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

Contribute to Open Source with utopian.io

Learn how to contribute on our website and join the new open source economy.

Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV

Congratulations @drifter2! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

Award for the number of upvotes received

Click on the badge to view your Board of Honor.
If you no longer want to receive notifications, reply to this comment with the word STOP

Do not miss the last post from @steemitboard:

SteemitBoard - Witness Update

Support SteemitBoard's project! Vote for its witness and get one more award!