Implementierung der Warteschlangen-Datenstruktur in C

CCBeginner
Jetzt üben

💡 Dieser Artikel wurde von AI-Assistenten übersetzt. Um die englische Version anzuzeigen, können Sie hier klicken

Einführung

In diesem Projekt lernst du, wie du eine Warteschlange (Queue) als Datenstruktur in C implementierst. Warteschlangen werden in der Informatik weit verbreitet eingesetzt, beispielsweise in Nachrichtenwarteschlangen, die zum Übertragen von Daten in einem Computer verwendet werden.

👀 Vorschau

$ gcc queue.c -o queue
$./queue
11250

🎯 Aufgaben

In diesem Projekt wirst du lernen:

  • Wie du die front()-Methode implementierst, um den Wert des vordersten Elements in der Warteschlange zurückzugeben
  • Wie du die pop()-Methode implementierst, um das vorderste Element aus der Warteschlange zu entfernen und zurückzugeben
  • Wie du die count()-Methode implementierst, um die Anzahl der derzeit in der Warteschlange befindlichen Elemente zurückzugeben
  • Wie du die is_empty()-Methode implementierst, um zu überprüfen, ob die Warteschlange leer ist

🏆 Errungenschaften

Nach Abschluss dieses Projekts wirst du in der Lage sein:

  • Die grundlegenden Operationen einer Warteschlangen-Datenstruktur zu verstehen
  • Die Kernmethoden einer Warteschlange in C zu implementieren
  • Dein Wissen über Warteschlangen anzuwenden, um reale Probleme zu lösen

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL c(("C")) -.-> c/CompoundTypesGroup(["Compound Types"]) c(("C")) -.-> c/PointersandMemoryGroup(["Pointers and Memory"]) c(("C")) -.-> c/FunctionsGroup(["Functions"]) c(("C")) -.-> c/BasicsGroup(["Basics"]) c(("C")) -.-> c/ControlFlowGroup(["Control Flow"]) c/BasicsGroup -.-> c/variables("Variables") c/ControlFlowGroup -.-> c/if_else("If...Else") c/ControlFlowGroup -.-> c/for_loop("For Loop") c/CompoundTypesGroup -.-> c/structures("Structures") c/PointersandMemoryGroup -.-> c/pointers("Pointers") c/FunctionsGroup -.-> c/function_declaration("Function Declaration") subgraph Lab Skills c/variables -.-> lab-301501{{"Implementierung der Warteschlangen-Datenstruktur in C"}} c/if_else -.-> lab-301501{{"Implementierung der Warteschlangen-Datenstruktur in C"}} c/for_loop -.-> lab-301501{{"Implementierung der Warteschlangen-Datenstruktur in C"}} c/structures -.-> lab-301501{{"Implementierung der Warteschlangen-Datenstruktur in C"}} c/pointers -.-> lab-301501{{"Implementierung der Warteschlangen-Datenstruktur in C"}} c/function_declaration -.-> lab-301501{{"Implementierung der Warteschlangen-Datenstruktur in C"}} end

Implementiere die front()-Methode

In diesem Schritt lernst du, wie du die front()-Methode der Warteschlange implementierst.

Die front()-Methode sollte den Wert des vordersten Elements in der Warteschlange zurückgeben. Wenn die Warteschlange leer ist, sollte die Methode das Programm mit exit(-1) beenden.

Folgende Schritte, um diesen Schritt abzuschließen:

  1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
  2. Locate die front()-Methode im Code.
  3. Implementiere die front()-Methode wie folgt:
static int front() {
    if(!phead) {
        exit(-1);
    }
    return phead->val;
}

Die front()-Methode überprüft zunächst, ob der Zeiger phead NULL ist, was auf eine leere Warteschlange hinweist. Wenn die Warteschlange leer ist, beendet die Methode das Programm mit exit(-1).

Wenn die Warteschlange nicht leer ist, gibt die Methode den in der phead-Knoten gespeicherten Wert zurück, der das vorderste Element der Warteschlange darstellt.

Implementiere die pop()-Methode

In diesem Schritt lernst du, wie du die pop()-Methode der Warteschlange implementierst.

Die pop()-Methode sollte das vorderste Element aus der Warteschlange entfernen und zurückgeben. Wenn die Warteschlange leer ist, sollte die Methode das Programm mit exit(-1) beenden.

Folgende Schritte, um diesen Schritt abzuschließen:

  1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
  2. Locate die pop()-Methode im Code.
  3. Implementiere die pop()-Methode wie folgt:
static int pop() {
    if(!phead) {
        exit(-1);
    }
    int val = phead->val;
    phead = phead->next;
    return val;
}

Die pop()-Methode überprüft zunächst, ob der Zeiger phead NULL ist, was auf eine leere Warteschlange hinweist. Wenn die Warteschlange leer ist, beendet die Methode das Programm mit exit(-1).

Wenn die Warteschlange nicht leer ist, speichert die Methode den Wert des phead-Knotens, der das vorderste Element der Warteschlange darstellt. Anschließend aktualisiert sie den phead-Zeiger auf den nächsten Knoten, was effektiv das vorderste Element aus der Warteschlange entfernt. Schließlich gibt die Methode den gespeicherten Wert zurück.

Implementiere die count()-Methode

In diesem Schritt lernst du, wie du die count()-Methode der Warteschlange implementierst.

Die count()-Methode sollte die Anzahl der derzeit in der Warteschlange befindlichen Elemente zurückgeben.

Folgende Schritte, um diesen Schritt abzuschließen:

  1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
  2. Locate die count()-Methode im Code.
  3. Implementiere die count()-Methode wie folgt:
static int count() {
    int cnt = 0;
    for(struct node* p = phead; p; p=p->next) {
        cnt++;
    }
    return cnt;
}

Die count()-Methode initialisiert eine Variable cnt mit 0. Anschließend läuft sie die Warteschlange entlang, indem sie die next-Zeiger des phead-Knotens und seiner Nachfolger folgt. Für jeden begegneten Knoten erhöht sie die Variable cnt. Schließlich gibt die Methode den cnt-Wert zurück, der die Anzahl der Elemente in der Warteschlange darstellt.

Implementiere die is_empty()-Methode

In diesem Schritt lernst du, wie du die is_empty()-Methode der Warteschlange implementierst.

Die is_empty()-Methode sollte 1 zurückgeben, wenn die Warteschlange leer ist, und 0 sonst.

Folgende Schritte, um diesen Schritt abzuschließen:

  1. Öffne die Datei queue.c, die sich im Verzeichnis /home/labex/project/queue.c befindet.
  2. Locate die is_empty()-Methode im Code.
  3. Implementiere die is_empty()-Methode wie folgt:
static int is_empty() {
    return phead == NULL;
}

Die is_empty()-Methode überprüft einfach, ob der Zeiger phead NULL ist, was auf eine leere Warteschlange hinweist. Wenn phead NULL ist, gibt die Methode 1 zurück, was bedeutet, dass die Warteschlange leer ist. Andernfalls gibt sie 0 zurück, was bedeutet, dass die Warteschlange nicht leer ist.

Herzlichen Glückwunsch! Du hast jetzt alle erforderlichen Methoden für die Warteschlangen-Datenstruktur implementiert. Du kannst jetzt das Programm kompilieren und ausführen, um die Funktionalität der Warteschlange zu testen.

  1. Kompilieren und ausführen:
$ gcc queue.c -o queue
$./queue
00000

Die erwartete Ausgabe lautet wie folgt:

$ gcc queue.c -o queue
$./queue
11250
✨ Lösung prüfen und üben

Zusammenfassung

Herzlichen Glückwunsch! Du hast dieses Projekt abgeschlossen. Du kannst in LabEx weitere Übungen absolvieren, um deine Fähigkeiten zu verbessern.