Bild Referenz:
Intro
Hallo, ich bin's @drifter2! Der heutige Artikel ist eine kleine Übungsaufgabe rund um Stapel und Warteschlangen, die ich von meinem englischen Artikel "C Stack-Queue Exercise using Dynamic Arrays" übersetzen werde. Bei dieser Aufgabe werden diese Datenstrukturen mit Dynamischen Feldern implementiert. Nächstes mal werden wir eine sehr ähnliche Aufgabe mit Verketteten Listen implementieren. Natürlich solltet ihr euch erstmal die Artikel rund um Stapel und Warteschlangen anschauen, denn ich werde nur auf die eigentliche Lösung des Problems zutiefst eingehen. Also dann fangen wir dann mal direkt an!
Aufgabenbeschreibung:
Sagen wir mal wir haben 2 Fähren Boote. Die erste Fähre heißt 'S', weil sie wie eine Stapel (Stack auf Englisch) funktioniert. Die zweite 'Q', weil sie wie eine Warteschlange (Queue auf Englisch) funktioniert. Diese Funktionalität zeigt uns in welcher Reihenfolge Autos in diese Fähren reingesetzt und wieder weggenommen werden können. Jedes Auto muss sich zwischen einer der zwei Fähren entscheiden (wird also nur auf eine "einsteigen"), etwas das wir von einer Datei lesen werden.
Der Dateiname ist eine Eingabe des Benutzers des Programms und muss die Auto-ID (Identifikationsnummer oder auch Nummernschild) und Bootpräferenz enthalten. Eine solche Datei die 5 Autos mit dessen Präferenz enthält kann wie folgend aussehen:
ZZA9896 S
MIN5689 Q
NHI9098 S
KNM4545 Q
IPO8987 Q
Das Programm das ihr implementiert muss folgendes machen:
- Die Kapazität der Boote und den Namen der Autos-Datei als Eingabe des Benutzers bekommen
- Die Boote, oder besser gesagt, dessen Datenstrukturen, initialisieren
- Von der Autos-Datei lesen und das Segeln beider Boote verwalten, indem man diese füllt bis sie voll sind
- Wenn ein Boot voll wird, dann fangen wir mit dem "Segeln" an, welches bedeutet das wir die Auto-ID's in einer Neuen Datei schreiben und das per Segel, indem wir den Stapel oder die Warteschlange entleeren. Die Namen dieser Dateien sollten in der Form: s0, s1, s2, ... beim Stapel und q0, q1, q2, ... bei der Warteschlange sein.
- Die Schritte 3 und 4 werden wiederholt bis kein neues Auto in der Autos-Datei ist (EOF)
- Danach müssen wir nochmals kontrollieren ob es Autos in den Booten gibt, welches bedeutet das wir auch die "nicht-vollen" Segel ausführen, indem wir auch diese normal in Dateien schreiben
Die Stapel und Warteschlangen Operationen müssen als Funktionen implementiert werden.
Lösung-Implementation in C
Datenstrukturen
Die Boot-Strukturen müssen folgendes enthalten:
- eine gewisse Kapazität (capacity auf Englisch) Variable so das wir kontrollieren ob Boot voll ist oder auch leer für Schritt 6
- eine Segel Nummer (sailing number auf Englisch) um die richtige Nummer bei den Dateinamen zu verwenden
- ein Dynamisches Auto-ID Feld-Array
- Top-Index für den Stapel und Front und Rear-Index für die Warteschlange
Die Strukturen (structs) sehen also in Code wie folgend aus:
// Stapel Strukturtypedef struct Stack{ int sail_num; int capacity; int top; char **car_id;}Stack;// Warteschlangen Strukturtypedef struct Queue{ int sail_num; int capacity; int front; int rear; char **car_id; }Queue;Wie ihr sehen könnt ist diese Definition nicht so ganz abweichend von der die wir bei den Artikeln erwähnt haben. Wir haben einfach ein paar Variablen ergänzt die bei der Anwendung hilfreich sind. Fangen wir dann mal mit der Implementierung von den verschiedenen Funktionen und Schritten an...
Benutzer-Eingabe und Lesen der Autos-Datei
Wie wir bereits wissen können wir die Stapel und Warteschlangen Variablen ganz normal als Struktur-Variablen definieren, aber auch als Zeiger. Bei dem heutigen Problem werden wir die Variablen ganz normal definieren und nicht als Zeiger, obwohl hier kein "Lese-Trick" gebraucht wird (wo wir die Variable ohne Adresse abgeben so das diese nur temporär in der Funktion verändert wird, um das Iterieren der Struktur zu verleichtern).
Also werden die Variablen wie folgend definiert:
Stack S;Queue Q;Die Kapazität kann dann sehr leicht wie folgend als Eingabe genommen werden:
printf("Capacity of S: "); scanf("%d", &S.capacity);printf("Capacity of Q: ");scanf("%d", &Q.capacity);Um von einer Datei lesen zu können brauchen wir erstmals einen Datei-Zeiger (file pointer - fp auf Englisch). Zusätzlich werden auch temporäre Lese-Puffer gebraucht für die Auto-ID und die Boot-Präferenz. Natürlich sollten wir auch nicht vergessen eine Zeichenkette für den eigentlichen Dateinamen zu definieren.
Also brauchen wir:
char input_file[20]; // DateinameFILE *fp; // Datei Zeiger// Lese-Puffer fuer die Dateichar car_id[10];char ship;Der Dateiname kann sehr leicht genommen werden:
printf("Input File: ");scanf("%19s", input_file);Das öffnen der Datei zum Lesen sieht wie folgend aus:
if(!(fp=fopen(input_file, "r"))){ perror("fopen"); return 1;} Wir kontrollieren natürlich auch ob es vielleicht einen Datei-Fehler gab, da sonst die Programmausführung nicht weitergehen kann. Die Datei könnte z.B nicht existieren oder der Zugriff könnte verweigert sein.
Datenstrukturen initialisieren
Um den Stapel zu initialisieren müssen wir folgendes machen:
- Speicher an das dynamische Auto-ID Feld zuweisen
- Top-Index auf '-1' setzen
- Segelnummer auf '0' setzen
Das ganze sieht in Code wie folgend aus:
S.car_id=(char**)malloc(S.capacity*sizeof(char*)); // linesfor(i=0;i<S.capacity;i++){ S.car_id[i]=(char*)malloc(10*sizeof(char)); // rows} S.top=-1;S.sail_num=0;Wie ihr sehen könnt hat jede Auto-ID eine maximale Länge von 10 (9 wenn man \0 dazuzählt), welches für unsere Autodatei ausreicht. Bei einer anderen Datei könnte das anders sein. Da könnte man z. B. auch die maximale Länge der Auto-ID am Anfang der Datei hinzufügen. Das selbe wird gleich auch bei der Warteschlange der Fall sein.
Die Warteschlange wird wie folgend initialisiert:
- Speicher an das dynamische Auto-ID Feld zuweisen
- Front und Rear Index auf '-1' setzen
- Segelnummer auf '0' setzen
Der eigentliche Code sieht wie folgend aus:
Q.car_id=(char**)malloc(Q.capacity*sizeof(char*)); // linesfor(i=0;i<Q.capacity;i++){ Q.car_id[i]=(char*)malloc(10*sizeof(char)); // rows}Q.front=Q.rear=-1;Q.sail_num=0;Sehr ähnlich mit der Stapel-Initialisierung.
Datenstruktur-Operationen
Bevor wir weitermachen sollten wir jetzt die eigentlichen Funktionen für die Verwaltung der Boot-Strukturen implementieren, damit wir diese dann direkt bei der Lesungs-While-Schleife verwenden können...
Die Funktionen-Operationen die wir brauchen sind:
- Auto-ID in Stapel einfügen (push)
- Auto-ID vom Stapel rausnehmen (pop)
- Stapel in Datei einspeichern - Segeln von 'S' ausführen (StackToFile)
- Auto-ID in Warteschlange einfügen (add)
- Auto-ID von der Warteschlange rausnehmen (delete)
- Warteschlange in Datei einspeichern - Segeln von 'Q' ausführen (QueueToFile)
Implementieren wir mal jede alleine...
In Stapel einfügen
Beim einfügen kontrollieren wir erstmal ob der Stapel voll ist. Wenn ja dann führen wir das Segeln aus. WEnn nicht dann inkrementieren wir den Top-Index und fügen das neue Element ein.
Das sieht in Code wie folgend aus:
void push(Stack *S, char x[]){ // wenn nicht voll einfuegen if(S->top < (S->capacity - 1)){ S->top++; strcpy(S->car_id[S->top], x); } // wenn voll in Datei schreiben else{ StacktoFile(S); }}Vom Stapel rausnehmen
Beim rausnehmen sollten wir kontrollieren ob der Stapel leer ist, etwas das aber ein wenig unnötig ist da wir das auch vor der ausführen kontrollieren können. Werde ich aber trotzdem wie üblich kontrollieren. Bei dieser Implementation geben ich nicht direkt einen Wert zurück, sonder mache das direkt durch einen Parameter der Funktion, was heißt das ich den Wert dort abspeichere und das den Top-Index dekrementiere.
Das ganze sieht in Code wie folgend aus:
void pop(Stack *S, char *car_id){ // kontrollieren ob Stapel leer ist (unnoetig) if(S->top==-1){ printf("Stack is empty!\n"); } // Wert in Parameter speichern und dann Top-Index dekrementieren else{ strcpy(car_id, S->car_id[S->top]); S->top--; }}Stapel Segeln ausführen
Beim Segeln müssen wir natürlich erstmal den Dateinamen "erschaffen". Das kann leicht mit Hilfe von den Funktionen:
- itoa(), welche eine Funktion ist die Ganzzahlen in Zeichenketten konvertiert
- strcpy(), welche eine Funktion ist die eine Zeichenkette kopiert (copy)
- strcat(), welche eine Funktion ist die Zeichenketten "verkettet" (concatenate)
gemacht werden.
Natürlich werden wir dann eine Datei zum schreiben öffnen die diesen Namen hat und dann mit einer While-Schleifen so lange von dem Stapel rausnehmen und schreiben bis der Top-Index einen Wert von "-1" hat. Wie ihr sehen könnt kann man damit sehr leicht kontrollieren ob der Stapel voll ist, etwas das hier sonst nicht ging, da wir nicht den Wert zurückgeben, da dieser ja keine Nummer ist. Man könnte eine gewisse Auto-ID als "Leer-Zeichen" benutzen aber ich glaub das ist hier eh unnötig. Nachdem das Segeln fertig ist sollten wir auch nicht vergessen die Segelnummer zu inkrementieren...
Der Code sieht wie folgend aus:
void StacktoFile(Stack *S){ FILE*fp; int i; char output_file[10]; char buffer[2]; char car_id[10]; // Dateinamen "erschaffen" itoa(S->sail_num, buffer, 10); strcpy(output_file, "s"); strcat(output_file, buffer); strcat(output_file, ".txt"); // in Datei schreiben fp=fopen(output_file, "w"); while(S->top>-1){ // solange nicht leer ist pop(S, car_id); fprintf(fp, "%s\n", car_id); } // Segelnummer inkrementieren S->sail_num++; fclose(fp);}In Warteschlange einfügen
Um eine Auto-ID in die Warteschlange einzufügen müssen wir 3 gewisse Fälle kontrollieren. Erstmal, wenn voll wird dann direkt das Segeln ausgeführt. Wenn ganz leer müssen beide Indexes auf '0' initialisiert werden, sonst nur der Rear-Index inkrementiert werden. Nach dieser Initialisierung oder Inkrementierung fügt man dan bei dem Rear-Index das neue Element ein.
Der Code ist wie folgend:
void add(Queue *Q, char x[]){ // wenn voll in Datei schreiben if(Q->rear == Q->capacity -1){ QueuetoFile(Q); return; } // wenn leer beide Indexe initialisieren else if(Q->front == -1){ Q->front=Q->rear=0; } // wenn nicht leer und nicht voll Rear++ else{ Q->rear++; } // Einfuegung der neuen Auto-ID strcpy(Q->car_id[Q->rear], x);}Von der Warteschlange rausnehmen
Beim rausnehmen können wir wieder mal kontrollieren ob die Warteschlange vielleicht leer ist, etwas das aber wieder mal von dem Segeln kontrolliert werden kann. Danach gibt es zwei Fälle: das zulöschende Element ist das einzige Element oder es gibt mehrere. Beim ersten Fall müssen wir beide Indexe auf '-1' initialisieren. Beim zweiten nur Front-Index inkrementieren. Bei beiden sollten wir den Wert wieder mal beim zweiten Parameter abspeichern.
Der Code dafür ist:
void delete(Queue *Q, char *car_id){ // kontrollieren ob leer ist (unnoetig) if(Q->front==-1){ printf("Queue is Empty!\n"); } else{ // einziges Element - beides '-1' if(Q->front==Q->rear){ strcpy(car_id, Q->car_id[Q->front]); Q->front=Q->rear=-1; } // es gibt noch andere Elemente - Front++ else{ strcpy(car_id, Q->car_id[Q->front]); Q->front++; } }}Warteschlange Segeln ausführen
Ähnlich wie beim Stapel werden wir erstmal den Dateinamen "erschaffen". Danach können wir ganz normal eine Datei mit diesen Dateinamen zum schreiben öffnen und mit einer While-Schleife ganz normal die Auto-ID's rausnehmen und schreiben, solange die Warteschlange nicht leer ist. Zuletzt sollten wir auch die Segelnummer inkrementieren.
Der Code ist also:
void QueuetoFile(Queue *Q){ FILE*fp; int i; char output_file[10]; char buffer[2]; char car_id[20]; // Dateinamen "erschaffen" itoa(Q->sail_num, buffer, 10); strcpy(output_file, "q"); strcat(output_file, buffer); strcat(output_file, ".txt"); // In Datei schreiben fp=fopen(output_file, "w"); while(Q->front!=-1){ delete(Q, car_id); fprintf(fp, "%s\n", car_id); } // Segelnummer inkrementieren Q->sail_num++; fclose(fp);}Lese-Schleife
Das Lesen geht mit einer While-Schleife, welche aufhört wenn es in der Datei keine Elemente (Auto-ID's) mehr gibt, also solange mann nicht das Ende der Datei (EOF) erreicht hat. Bei dieser Kontrolle lesen wir natürlich auch immer die Auto-ID und die Boot-Präferenz. Danach werden die jetzige Auto-ID immer in das richtige Boot je nach Präferenz einsortieren. Nach dem einfügen kontrollieren wir auch ob das Boot vielleicht schon voll ist.
Der Code sieht wie folgend aus:
// solange wir nicht das Ende der Datei (EOF) erreicht habenwhile(fscanf(fp, "%9s %c", car_id, &ship) != EOF){ // Boot-Praefernz ist 'S' if(ship=='S'){ // Auto-ID einfuegen push(&S, car_id); // wenn voll in Datei schreiben if(S.top == S.capacity - 1){ StacktoFile(&S); } } // Boot-Praefernz ist 'Q' else{ // Auto-ID einfuegen add(&Q, car_id); // wenn voll in Datei schreiben if(Q.rear == Q.capacity -1){ QueuetoFile(&Q); } }}Kontrollieren ob Boote (wirklich) leer sind
Nach dieser Schleife sollten wir nochmal kontrollieren ob es noch Autos (oder Auto-ID's) in den Booten gibt, da unser Code ja nur einschreibt wenn die maximale Kapazität erreicht wurde. Das kann man sehr leicht machen indem man sich die Top und Front Index Werte "anschaut". Wenn '-1' ist bereits leer, wenn nicht dann sollte man ein Segeln ausführen. Danach noch die Datei schließen und das war's...
Der Code ist:
if(S.top!=-1) StacktoFile(&S);if(Q.front!=-1) QueuetoFile(&Q);fclose(fp);return 0;Das vollständige Programm:
Hier noch mal das komplette Programm...
#include <stdio.h>#include <stdlib.h>#include <string.h>// Stapel Strukturtypedef struct Stack{ int sail_num; int capacity; int top; char **car_id;}Stack;// Warteschlangen Strukturtypedef struct Queue{ int sail_num; int capacity; int front; int rear; char **car_id; }Queue;// Funktionen Deklarierenvoid push(Stack *S, char *x);void pop(Stack *S, char *car_id);void StacktoFile(Stack *S);void add(Queue *Q, char *x);void delete(Queue *Q, char *car_id);void QueuetoFile(Queue *Q);int main(){ // Boot Variablen Stack S; Queue Q; char input_file[20]; int i; FILE *fp; // Temporaere Datei-Puffer char car_id[10]; char ship; // Kapazitaet Eingabe printf("Capacity of S: "); scanf("%d", &S.capacity); printf("Capacity of Q: "); scanf("%d", &Q.capacity); // Dateinamen Eingabe printf("Input File: "); scanf("%19s", input_file); // Datei zum lesen oeffnen if(!(fp=fopen(input_file, "r"))){ perror("fopen"); return 1; } // Stapel initialisieren S.car_id=(char**)malloc(S.capacity*sizeof(char*)); // lines for(i=0;i<S.capacity;i++){ S.car_id[i]=(char*)malloc(10*sizeof(char)); // rows } S.top=-1; S.sail_num=0; // Warteschlange initialisieren Q.car_id=(char**)malloc(Q.capacity*sizeof(char*)); // lines for(i=0;i<Q.capacity;i++){ Q.car_id[i]=(char*)malloc(10*sizeof(char)); // rows } Q.front=Q.rear=-1; Q.sail_num=0; // solange wir nicht das Ende der Datei (EOF) erreicht haben while(fscanf(fp, "%9s %c", car_id, &ship) != EOF){ // Boot-Praefernz ist 'S' if(ship=='S'){ // Auto-ID einfuegen push(&S, car_id); // wenn voll in Datei schreiben if(S.top == S.capacity - 1){ StacktoFile(&S); } } // Boot-Praefernz ist 'Q' else{ // Auto-ID einfuegen add(&Q, car_id); // wenn voll in Datei schreiben if(Q.rear == Q.capacity -1){ QueuetoFile(&Q); } } } // Kontrollieren ob Boote (wirklich) leer sind if(S.top!=-1) StacktoFile(&S); if(Q.front!=-1) QueuetoFile(&Q); fclose(fp); return 0; }// Stapel Funktionenvoid push(Stack *S, char x[]){ if(S->top < (S->capacity - 1)){ S->top++; strcpy(S->car_id[S->top], x); } else{ StacktoFile(S); }}void pop(Stack *S, char *car_id){ if(S->top==-1){ printf("Stack is empty!\n"); } else{ strcpy(car_id, S->car_id[S->top]); S->top--; }}void StacktoFile(Stack *S){ FILE*fp; int i; char output_file[10]; char buffer[2]; char car_id[10]; itoa(S->sail_num, buffer, 10); strcpy(output_file, "s"); strcat(output_file, buffer); strcat(output_file, ".txt"); fp=fopen(output_file, "w"); while(S->top>-1){ pop(S, car_id); fprintf(fp, "%s\n", car_id); } S->sail_num++; fclose(fp);}// Warteschlangen Funktionenvoid add(Queue *Q, char x[]){ if(Q->rear == Q->capacity -1){ QueuetoFile(Q); return; } else if(Q->front == -1){ Q->front=Q->rear=0; } else{ Q->rear++; } strcpy(Q->car_id[Q->rear], x);}void delete(Queue *Q, char *car_id){ if(Q->front==-1){ printf("Queue is Empty!\n"); } else{ if(Q->front==Q->rear){ strcpy(car_id, Q->car_id[Q->front]); Q->front=Q->rear=-1; } else{ strcpy(car_id, Q->car_id[Q->front]); Q->front++; } }}void QueuetoFile(Queue *Q){ FILE*fp; int i; char output_file[10]; char buffer[2]; char car_id[20]; itoa(Q->sail_num, buffer, 10); strcpy(output_file, "q"); strcat(output_file, buffer); strcat(output_file, ".txt"); fp=fopen(output_file, "w"); while(Q->front!=-1){ delete(Q, car_id); fprintf(fp, "%s\n", car_id); } Q->sail_num++; fclose(fp);}Ausführungsbeispiel
Sagen wir mal wir geben folgendes ein:
- Kapazität für S : 2
- Kapazität für Q : 1
- Autos-Datei mit namen "cars.txt" und den vorherigen 5 AutoID-Präferenz Paaren
Diese Ausführung würde folgende Dateien erzeugen:
s0.txt
NHI9098
ZZA9896
q0.txt
MIN5689
q1.txt
KNM45454
q2.txt
IPO8987
Wie ihr sehen könnt sind die zwei Autos vom Stapel in der inversen Reihenfolge wieder raus gekommen. Bei der Warteschlange ist es immer nur 1 Auto, also sind diese nur in der Reihenfolge in der sie in der Datei drin waren wieder raus gekommen.
Referenzen:
Ja nur dieser "kleine" Englische Artikel...aber ich habe trotzdem alles viel kompletter gestaltet als davor, da ich ja alles viel analytischer erklärt habe!
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
Warteschlangen und Stapel implementiert mit Verketteten Listen -> Liste, Warteschlange und Stapel mit Liste implementieren in C-Sprache.
Fortgeschrittene Listen und Warteschlangen -> Doppelt verkettete Listen (mit Implementation), Zirkuläre Listen, Vorrangwarteschlange (mit Implementation)
Fortgeschrittene Bäume -> Βinärer Suchbaum (Zusammenfassung), AVL-Baum (mit Implementation), Rot-Schwarz (ohne Code) und 2-3-4 Bäume (ohne Code)
Schlusswort
Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Wie bereits bei dem Intro erwähnt wurde werden wir nächstes mal in eine ähnliche Aufgabe rund um Stapel und Warteschlangen eingehen, bei der wir dann Verkettete Listen für die Implementierung der Datenstrukturen verwenden werden.
Keep on drifting! ;)