Programmieren in C - Stapel-Warteschlangen Übungsaufgabe mit Verketteten Listen
Bild Referenz: https://commons.wikimedia.org/wiki/File:QUEUE_VS_STACK.png
Intro
Hallo, ich bin's @drifter2! Der heutige Artikel ist wieder mal eine Übungsaufgabe rund um Stapel und Warteschlangen, die dieses mal an meinem englischen Artikel "C Stack-Queue Exercise using Linked Lists" basiert ist. Letztes mal hatten wir was sehr ähnliches mit Dynamischen Feldern implementiert. Natürlich solltet ihr euch erstmal die Artikel rund um Stapel und Warteschlangen anschauen, und vielleicht auch die vorherige Übungsaufgabe. Also dann fangen wir dann mal direkt an!
Aufgabenbeschreibung:
Ähnlich wie beider vorherigen Aufgabe haben wir wieder mal 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 wird jetzt aber nicht mehr eine Fähre auswählen, sondern die Autos werden erstmal in Fähre S und dann in Fähre Q eingefügt.
Der Dateiname ist eine Eingabe des Benutzers des Programms und muss die Auto-ID (Identifikationsnummer oder auch Nummernschild) enthalten. Damit wir die Resultate mit denen vom letztem mal vergleichen können, werden wir wieder in der Datei immer noch eine Boot-Präferenz abspeichern, die bei dieser Aufgabe hier eigentlich unnötig ist. 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
- Die Autos gehen erstmal in Boot S. Wenn diese 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 natürlich per Segel, indem wir den Stapel entleeren. Die Namen dieser Dateien sollten in der Form: s0, s1, s2, ... sein
- Bei dem entleeren von Boot S werden die Autos dann in Boot Q eingefügt und das bis S leer ist (das sollte natürlich vor dem Segeln von S anfangen!). Jedes mal wenn Q voll wird werden wir wieder mal mit dem "Segeln" anfangen, indem wir die Auto-ID's in einer neuen Datei schreiben, mit Namen der Form: qo, q1, q2, ... per Segel.
- Die Schritte 3-5 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. Natürlich sollten wir hier aufpassen das die Autos wiedermal erstmal in S reingehen und danach in Q!
Die eigentliche Veränderung ist also bei Schritt 4 (der jetzt in 4 und 5 eingeteilt wurde)
Die Stapel und Warteschlangen Operationen müssen als Funktionen implementiert werden.
Lösung-Implementation in C
Datenstrukturen
Da wir über Listen reden müssen wir natürlich einen Knoten (Node) definieren welcher eine Auto-ID und einen Zeiger auf den nächsten (next) Knoten enthält. Die Struktur des Knoten sieht also wie folgend aus:
typedef struct Node{
char car_id[10];
struct Node *next;
}Node;
Ich sollte hier vielleicht mal erwähnen das wir von der Autos-Datei wissen das die Auto-ID's aus 7 Zeichen bestehen. Das heißt also das diese als Zeichenkette ein 8er Feld brauchen (\0 am Ende). Wie ihr sehen könnt ist die maximale Länger aber ein wenig höher, so das ich eine "vollere" Nummer habe :P
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 7
- eine Segel Nummer (sailing number auf Englisch) um die richtige Nummer bei den Dateinamen zu verwenden
- Die Anzahl an Elementen die eingefügt wurden (numElements)
- Top-Zeiger für den Stapel und Front und Rear-Zeiger für die Warteschlange
Die Strukturen (structs) sehen also in Code wie folgend aus:
// Stapel Struktur
typedef struct Stack{
int sail_num;
int capacity;
int numElements;
Node *Top;
}Stack;
// Warteschlangen Struktur
typedef struct Queue{
int sail_num;
int capacity;
int numElements;
Node *front;
Node *rear;
}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 beim letzen mal werden wir die Struktur-Variablen wieder mal "ganz normal" und nicht als Zeiger definieren wie folgend:
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 (auch wenn diese nur gebraucht wird um beim Motiv der Datei zu bleiben). Natürlich sollten wir auch nicht vergessen eine Zeichenkette für den eigentlichen Dateinamen zu definieren.
Also brauchen wir:
char input_file[20]; // Dateiname
FILE *fp; // Datei Zeiger
// Lese-Puffer fuer die Datei
char 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:
- Den Top-Zeiger auf NULL initialisieren
- Nummer von Elementen (numElements) auf '0' setzen
- Segelnummer auf '0' setzen
Das ganze sieht in Code wie folgend aus:
S.Top=NULL;
S.numElements=0;
S.sail_num=0;
Da bei Listen kein Speicher zugewiesen werden muss und das automatisch bei der Ausfuhr passiert, ist die Initialisierung beider Strukturen sehr simple gehalten!
Die Warteschlange wird wie folgend initialisiert:
- Front und Rear-Zeiger auf NULL initialisieren
- Nummer von Elementen (numElements) auf '0' setzen
- Segelnummer auf '0' setzen
Der eigentliche Code sieht wie folgend aus:
Q.front=Q.rear=NULL;
Q.numElements=0;
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 müssen wir erstmal einen neuen Knoten erstellen. Danach kontrollieren wir erstmal ob der Stapel leer ist. Wenn ja dann wird das neue Element der neue Kopf der Liste, wenn nicht dann wird dieser wieder der neue Kopf der Liste aber zusätzlich die vorherige Liste sein next-Zeiger. Bei beiden Fällen inkrementieren wir auch die Anzahl an Elementen um zu wissen wann der Stapel voll ist. Wir ihr bereites verstehen könnt kontrollieren wir hier nirgends ob der Stapel voll ist, da das bei der main() Funktion bereits kontrolliert wird, so das die Entleerung erst nach dem Segeln von Boot Q stattfindet.
Das sieht in Code wie folgend aus:
void push(Stack *S, char x[]){
Node *cur, *nn;
// neuen Knoten erstellen
nn=(Node*)malloc(sizeof(Node));
strcpy(nn->car_id, x);
nn->next=NULL;
// wenn leer ist der der neue Kopf
if(S->Top==NULL){
S->Top=nn;
S->numElements++;
return;
}
// wenn bereits Elemente da sind, wird der next-Zeiger
// von "nn" auf diese zeigen und dann der neue Kopf werden
if(S->numElements < S->capacity){
nn->next=S->Top;
S->Top=nn;
S->numElements++;
}
// Wir koennten beides auch direkt vom Zweiten "if" machen
// da ja der Top-Zeiger beim ersten mal sowieso NULL waehre!
}
Vom Stapel rausnehmen
Beim rausnehmen kontrollieren wir erstmal ob der Stapel vielleicht leer ist. Das geht ganz leicht indem wir abchecken ob der Wert vom Top-Zeiger 'NULL' ist. Wenn nicht leer speichern wir den Wert im zweiten Parameter ab und lassen Top-Zeiger auf seinen "next" zeigen, so das wir im Stapel weitergehen!
Das ganze sieht in Code wie folgend aus:
void pop(Stack *S, char *car_id){
// kontrollieren ob Stapel leer ist (unnoetig)
if(S->Top==NULL){
printf("Stack is empty!\n");
}
// Wert in Parameter speichern und dann Top-Zeiger
// auf den naechsten (next) Knoten zeigen lassen
else{
strcpy(car_id, S->Top->car_id);
S->Top=S->Top->next;
}
}
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 mit pop() und schreiben bis der Top-Zeiger einen Wert von "NULL" 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. Damit die Daten vom Stapel nicht verloren gehen und dann von der Warteschlange benutzbar sind geben wir die Struktur diesem mal als Variable und nicht als Zeiger ein! Die erneute Initialisierung wir erst später von der main() Funktion kontrolliert!
Der Code sieht wie folgend aus:
void StacktoFile(Stack S){
FILE *fp;
Node *cur;
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!=NULL){
pop(&S, car_id);
fprintf(fp, "%s\n", car_id);
}
fclose(fp);
}
Das einzige neue ist also eigentlich nur das wir den Top-Zeiger nun mit NULL anstatt '-1' vergleichen, etwas das beim Top-Index verwendet wurden.
In Warteschlange einfügen
Um eine Auto-ID in die Warteschlange einzufügen müssen wir erstmal wieder mal einen neuen Knoten erstellen. Danach gibt es 3 gewisse Fälle die wir kontrollieren sollten. Wenn Liste/Warteschlange leer ist dann werden beider Zeiger (Front und Rear) mit "nn" gleichgesetzt. Wenn bereits Elemente da sind, iterieren wir durch die Liste mit einen Jetzige-Knote-Zeiger (cur pointer) und fügen das neue Element (den neuen Knoten) am Ende ein. Bei beiden Fällen sollten wir die Nummer von Elementen inkrementieren. Der letzte Fall den wir kontrollieren sollten ist ob die Warteschlange voll ist. Wenn voll führen wir das Segeln aus, im Gegensatz zum "darf" man das hier machen, da ja die Warteschlange von keinem "folgenden" Boot benutzt wird.
Der Code ist wie folgend:
void add(Queue *Q, char x[]){
Node *cur, *nn;
// neuen Knoten erstellen
nn=(Node*)malloc(sizeof(Node));
strcpy(nn->car_id, x);
nn->next=NULL;
// wenn leer ist wird "nn" neuer Front- und Rear-Zeiger
if(Q->front == NULL){
Q->front=Q->rear=nn;
Q->numElements++;
}
// wenn Elemente da wird "nn" am Ende eingefuegt
if(Q->numElements<Q->capacity){
cur=Q->front;
while(cur->next!=NULL){
cur=cur->next;
}
cur->next=nn;
Q->rear=nn;
Q->numElements++;
}
// wenn voll dann wird Segeln ausgefuehrt
else{
QueuetoFile(Q);
}
}
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 Zeiger auf 'NULL' initialisieren. Beim zweiten nur Front-Zeiger zum seinen nächsten Knoten zeigen lassen. 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==NULL){
printf("Queue is Empty!\n");
}
else{
// einziges Element - beides wird 'NULL'
if(Q->front==Q->rear){
strcpy(car_id, Q->front->car_id);
Q->front=Q->rear=NULL;
Q->numElements=0;
}
// es gibt noch andere Elemente - Front Zeiger -> next
else{
strcpy(car_id, Q->front->car_id);
Q->front=Q->front->next;
Q->numElements--;
}
}
}
Warteschlange Segeln ausführen
Ähnlich wie beim Stapel müssen 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 die Warteschlange erneut initialisieren, indem wir erstmals die Segelnummer inkrementieren und die Nummer der Elemente auf '0' setzen.
Der Code ist also:
void QueuetoFile(Queue *Q){
Node *cur;
FILE*fp;
int i;
char output_file[10];
char buffer[2];
char car_id[10];
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!=NULL){
delete(Q, car_id);
fprintf(fp, "%s\n", car_id);
}
Q->sail_num++;
Q->numElements=0;
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, auch wenn die zweite hier nicht gebraucht wird und nur benutzt wir um die gleiche Datei verwenden zu können. Danach fügen wir die jetzige Auto-ID bei Boot 'S' ein. Dabei kontrollieren wir ob das Boot voll ist. Wenn voll führen wir erstmal das Segeln aus, womit aber die Daten des Stapel nie verloren gehen, da wir ja nur die Struktur-Daten abgeben und nie die eigentliche Adresse dieser Daten! Danach iterieren wir durch den Stapel und fügen die Auto-ID's in der Warteschlange ein, solange wir nicht das Ende des Stapels erreicht haben. Jedes mal wo die Warteschlange voll wird müssen wir ein Segeln von Boot Q ausführen. Nachdem alle Elemente von dem Stapel durch-iteriert wurden inkrementieren wir die Segelnummer vom Stapel und setzen diesen zurück, indem wir Top-Zeiger wieder auf 'NULL' initialisieren und die Nummer der Elemente auf '0' setzen (indem wir also alles was nicht bei der Funktion StacktoFile() ausgeführt wurde nun ausführen).
Der Code sieht wie folgend aus:
// solange wir nicht das Ende der Datei (EOF) erreicht haben
while(fscanf(fp, "%9s %c", car_id, &ship)!=EOF){
// Auto-ID in Stapel einfuegen
push(&S, car_id);
// wenn Stapel voll wird in Datei schreiben
if(S.numElements==S.capacity){
StacktoFile(S);
// in naechste Faehre (Q) einfuegen
cur=S.Top;
while(cur!=NULL){
// Auto-ID in Warteschlange einfuegen
add(&Q, cur->car_id);
// wenn voll in Datei schreiben
if(Q.numElements==Q.capacity){
QueuetoFile(&Q);
}
cur=cur->next;
}
// Stapel zuruecksetzen
S.sail_num++;
S.Top=NULL;
S.numElements=0;
}
}
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 "numElements" Variablen anschaut. Wenn diese nicht '0' sind dann heißt "Mann über Bord"! Wir sollten dabei natürlich aufpassen das wir S entleeren und dabei Q füllen. Nachdem S fertig ist kann es natürlich immer noch sein das Boot Q immernoch Autos enthält, also kontrollieren wir danach auch noch Boot Q alleine! Danach noch die Datei schließen und das war's...
Der Code ist:
// kontrollieren ob S noch Autos hat
if(S.numElements!=0){
StacktoFile(S);
// in naechste Faehre (Q) einfuegen
cur=S.Top;
while(cur!=NULL){
add(&Q,cur->car_id);
// wenn voll Q in Datei schreiben
if(Q.numElements!=0){
QueuetoFile(&Q);
}
cur=cur->next;
}
}
// kontrollieren ob Q noch Autos hat
if(Q.numElements!=0) 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>
// Knoten Struktur fuer die Listen
typedef struct Node{
char car_id[10];
struct Node *next;
}Node;
// Stapel Struktur
typedef struct Stack{
int sail_num;
int capacity;
int numElements;
Node *Top;
}Stack;
// Warteschlangen Struktur
typedef struct Queue{
int sail_num;
int capacity;
int numElements;
Node *front;
Node *rear;
}Queue;
// Funktionen Deklarieren
void 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;
// Hilfs-Variablen
Node *cur;
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.Top=NULL;
S.numElements=0;
S.sail_num=0;
// Warteschlange initialisieren
Q.front=Q.rear=NULL;
Q.numElements=0;
Q.sail_num=0;
// solange wir nicht das Ende der Datei (EOF) erreicht haben
while(fscanf(fp, "%9s %c", car_id, &ship)!=EOF){
// Auto-ID in S einfuegen
push(&S, car_id);
// wenn voll in Datei schreiben
if(S.numElements==S.capacity){
StacktoFile(S);
// in naechste Faehre (Q) einfuegen
cur=S.Top;
while(cur!=NULL){
// Auto-ID in Q einfuegen
add(&Q, cur->car_id);
// wenn voll in Datei schreiben
if(Q.numElements==Q.capacity){
QueuetoFile(&Q);
}
cur=cur->next;
}
// Stapel zuruecksetzen
S.sail_num++;
S.Top=NULL;
S.numElements=0;
}
}
// kontrollieren ob S noch Autos hat
if(S.numElements!=0){
StacktoFile(S);
// in naechste Faehre (Q) einfuegen
cur=S.Top;
while(cur!=NULL){
add(&Q,cur->car_id);
// wenn voll Q in Datei schreiben
if(Q.numElements!=0){
QueuetoFile(&Q);
}
cur=cur->next;
}
}
// kontrollieren ob Q noch Autos hat
if(Q.numElements!=0) QueuetoFile(&Q);
fclose(fp);
return 0;
}
// Stapel Funktionen
void push(Stack *S, char x[]){
Node *cur, *nn;
nn=(Node*)malloc(sizeof(Node));
strcpy(nn->car_id, x);
nn->next=NULL;
if(S->Top==NULL){
S->Top=nn;
S->numElements++;
return;
}
if(S->numElements < S->capacity){
nn->next=S->Top;
S->Top=nn;
S->numElements++;
}
}
void pop(Stack *S, char *car_id){
if(S->Top==NULL){
printf("Stack is empty!\n");
}
else{
strcpy(car_id, S->Top->car_id);
S->Top=S->Top->next;
}
}
void StacktoFile(Stack S){
FILE *fp;
Node *cur;
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!=NULL){
pop(&S, car_id);
fprintf(fp, "%s\n", car_id);
}
fclose(fp);
}
// Warteschlangen Funktionen
void add(Queue *Q, char x[]){
Node *cur, *nn;
nn=(Node*)malloc(sizeof(Node));
strcpy(nn->car_id, x);
nn->next=NULL;
if(Q->front == NULL){
Q->front=Q->rear=nn;
Q->numElements++;
}
if(Q->numElements<Q->capacity){
cur=Q->front;
while(cur->next!=NULL){
cur=cur->next;
}
cur->next=nn;
Q->rear=nn;
Q->numElements++;
}
else{
QueuetoFile(Q);
}
}
void delete(Queue *Q, char *car_id){
if(Q->front==NULL){
printf("Queue is Empty!\n");
}
else{
if(Q->front==Q->rear){
strcpy(car_id, Q->front->car_id);
Q->front=Q->rear=NULL;
Q->numElements=0;
}
else{
strcpy(car_id, Q->front->car_id);
Q->front=Q->front->next;
Q->numElements--;
}
}
}
void QueuetoFile(Queue *Q){
Node *cur;
FILE*fp;
int i;
char output_file[10];
char buffer[2];
char car_id[10];
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!=NULL){
delete(Q, car_id);
fprintf(fp, "%s\n", car_id);
}
Q->sail_num++;
Q->numElements=0;
fclose(fp);
}
Ausführungsbeispiel
Sagen wir mal wir geben (wieder) 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
MIN5689
ZZA9896
q0.txt
MIN5689
q1.txt
ZZA9896
s1.txt
KNM4545
NHI9098
q2.txt
KNM4545
q3.txt
NHI9098
s2.txt
IPO8987
q4.txt
IPO8987
Damit ihr besser versteht was hier abgeht habe ich die Segel mit s-q Paaren geschrieben. Ihr könnt damit sehen wie S voll wird und dann seine Daten in Q eingeschrieben werden. Beim letzten mal reichen die Auto-ID's der Datei ja nicht aus um den Stapel voll zu machen, also sieht man wieso die Kontrolle nach der eigentlichen Lese-Schleife so wichtig ist! Die Kontrolle von Boot Q wird hier nicht verwendet da das Boot ja bereits bei dem Segeln von S voll wurde und somit ein Segeln ausgeführt wird. Diese letzte Kontrolle ist also nur von Nöten wenn S kleiner ist als Q (in Kapazität). Damit ihr die eigentliche Ausführungsreihenfolge besser versteht, solltet ihr diesen Code vielleicht auch selber mal ausführen! Aber ich glaub ich hab alles generell sehr gut und sehr präzise erklärt!
Referenzen:
Ja nur dieser "kleine" Englische Artikel...aber ich habe trotzdem versucht alles viel kompletter gestaltet als davor, da ich dort ja nur eine Beschreibung und dann den kompletten Code gegeben hatte!
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)
Stapel-Warteschlangen Übungsaufgabe mit Dynamischen Feldern -> Aufgabenbeschreibung, Lösung-Implementation in C (zutiefst) und Vollständiges Programm mit Ausführungsbeispiel
Schlusswort
Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Der nächste Artikel der Serie wird über die Vergleichung von Funktionen reden, wo wir dazu die Ausführungszeit und auch Iteration-Schritte verwenden werden. Das wird euch sehr dabei helfen die effizienteste Lösung zu finden wenn ihr einen Algorithmus oder generell die Implementation in Code optimieren wollt.
Keep on drifting! ;)
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!
![](https://steemitimages.com/640x0/https://codingforspeed.com/images/i-love-coding.jpg)
Reply !stop to disable the comment. Thanks!
Hallo ich bin Mikrobi,
dein Beitrag hat mir sehr gut gefallen und du bekommst von mir Upvote.
Ich bin ein Testbot, wenn ich alles richtig gemacht habe, findest du deinen Beitrag in meinem Report wieder.
LG
Mikrobi