CS – Woche 5

Datenstrukturen

Informationsstrukturen sind Formen der Organisation von Informationen im Gedächtnis. Es gibt viele Möglichkeiten, Daten im Speicher zu organisieren.

Abstrakte Datenstrukturen sind Strukturen, die wir uns konzeptionell vorstellen. Die Vertrautheit mit diesen abstrakten Strukturen erleichtert die zukünftige Implementierung von Datenstrukturen in die Praxis.

---

Stapel und Warteschlange

Warteschlange ist eine Form abstrakter Datenstrukturen.
Die Warteschlangendatenstruktur funktioniert nach der FIFO (First In First Out, „das erste hinzugefügte Element kommt zuerst heraus“)-Regel.
Man kann es sich als Beispiel für Menschen vorstellen, die vor einer Attraktion in der Schlange stehen: Die erste Person in der Schlange kommt als Erste rein, und die Letzte kommt als Letzte rein.

Die folgenden Vorgänge können mit

Warteschlangen:

ausgeführt werden

• Enqueue: Füge ein neues Element am Ende der Warteschlange hinzu.
• Aus der Warteschlange entfernen: Entfernt ein Element vom Anfang der Warteschlange.

Stapel Datenstruktur funktioniert nach der LIFO (Last In First Out, „das zuletzt hinzugefügte Element kommt zuerst heraus“) Zum Beispiel beim Tellerstapeln in der Küche: Der letzte Teller wird zuerst genommen.

Stack hat die folgenden Operationen:

• Push: Lege ein neues Element auf den Stapel.
• Pop: Entferne ein Element vom Stapel.

---

Array

Array ist eine Methode zum sequentiellen Speichern von Daten im Speicher. Ein Array kann wie folgt visualisiert werden:

Der Speicher kann andere Werte enthalten, die von anderen Programmen, Funktionen und Variablen gespeichert wurden, sowie redundante Werte, die zuvor verwendet wurden und nicht mehr verwendet werden:

Wenn wir dem Array ein neues Element – ​​4 – hinzufügen möchten, müssen wir neuen Speicher zuweisen und das alte Array hinein verschieben. Dieser neue Speicher ist möglicherweise voller Müllwerte

:

Wenn wir Elemente in das Array verschieben und einen neuen Wert hinzufügen, werden die neuen Werte über die alten unnötigen Werte im neu zugewiesenen Speicher geschrieben:

Der Nachteil dieses Ansatzes besteht darin, dass das gesamte Array jedes Mal kopiert werden muss, wenn ein neues Element hinzugefügt wird.
Was wäre, wenn wir 4 an einer anderen Stelle im Speicher ablegen würden? Dann ist dies per Definition kein Array mehr, da 4 nicht an Array-Elemente im Speicher angrenzt.

Manchmal weisen Programmierer mehr Speicher zu als nötig (z. B. 300 für 30 Elemente). Dies ist jedoch ein schlechtes Design, da dadurch Systemressourcen verschwendet werden und der zusätzliche Speicher in den meisten Fällen unnötig ist. Daher ist es wichtig, den Speicher entsprechend dem spezifischen Bedarf zuzuweisen.

---

Verlinkte Liste

Verknüpfte Liste ist eine der leistungsstärksten Datenstrukturen in der Programmiersprache C. Sie ermöglichen die Kombination von Werten, die sich in verschiedenen Speicherbereichen befinden, in einer einzigen Liste. Außerdem können wir die Liste nach Belieben dynamisch erweitern oder verkleinern.

Jeder Knoten speichert zwei Werte:

• Wert;
• ist ein Zeiger, der die Speicheradresse des nächsten Knotens enthält. Und der letzte Knoten enthält NULL, um anzuzeigen, dass danach kein weiteres Element vorhanden ist.

Wir speichern die Adresse des ersten Elements der verknüpften Liste in einem Zeiger (Zeiger).

In der Programmiersprache C können wir node wie folgt schreiben:

typedef struct node
{
    int number;
    struct node *next;
}
node;

Schauen wir uns den Prozess der Erstellung einer

verknüpften Liste an:

• Wir deklarieren den Knoten *list:

• Speicher für Knoten zuweisen:

• Geben Sie den Wert des Knotens ein: n->Nummer = 1:

• Wir setzen den nächsten Index des Knotens auf NULL: n->next = NULL:

• Vergleichen wir die Liste mit:

• In der gleichen Reihenfolge erstellen wir einen neuen Knoten mit dem Wert 2:

• Um beide Knoten zu verbinden, setzen wir den nächsten Index von n auf list:

• Und schließlich setzen wir die Liste auf n. Jetzt haben wir eine verknüpfte Liste, die aus zwei Elementen besteht:

In der Programmiersprache C können wir den Code dieses Prozesses wie folgt schreiben:

typedef struct node
{
    int number;
    struct node *next;
}
node;

Bei der Arbeit mit einer verknüpften Liste gibt es mehrere Nachteile:

• Mehr Speicher: Für jedes Element muss nicht nur der Wert des Elements selbst, sondern auch ein Zeiger auf das nächste Element gespeichert werden.
• Elemente nach Index aufrufen: In Arrays können wir ein bestimmtes Element nach Index aufrufen, in verknüpften Listen ist dies jedoch nicht möglich. Um die Position eines bestimmten Elements zu finden, ist es notwendig, alle Elemente der Reihe nach durchzugehen, beginnend mit dem ersten Element.

---

Baum

Binärer Suchbaum (BST) ist eine Informationsstruktur, die ein effizientes Speichern, Suchen und Abrufen von Daten ermöglicht.
Lassen Sie uns eine Folge sortierter Zahlen geben:

Wir platzieren das Element in der Mitte oben, kleinere Werte als das Element in der Mitte links und größere Werte rechts:

Wir verbinden jedes Element mithilfe von Zeigern miteinander:

Der folgende Code zeigt, wie BST implementiert wird:

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(int argc, char *argv[])
{
    // Linked list'ni e'lon qilamiz
    node *list = NULL;

    // Har bir buyruq qatori argumenti uchun
    for (int i = 1; i < argc; i++)
    {
        // Argumentni butun songa o‘tkazamiz
        int number = atoi(argv[i]);

        // Yangi element uchun xotira ajratamiz
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->number = number;
        n->next = NULL;

        // Linked list'ning boshiga node'ni qo‘shamiz
        n->next = list;
        list = n;
    }

    // Linked list elementlarini ekranga chiqaramiz
    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr->next;
    }

    // Xotirani bo‘shatamiz
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

Wir weisen jedem Knoten Speicher zu und sein Wert wird in Zahlen gespeichert, sodass jeder Knoten Links- und Rechtsindikatoren hat. Die Funktion print_tree druckt jeden Knoten in sequentieller Rekursion von links nach rechts. Die Funktion free_tree gibt alle Knoten der Datenstruktur rekursiv aus dem Speicher frei.

Vorteile von

BST:

• Dynamik: Wir können Elemente effizient hinzufügen oder entfernen.
• Sucheffizienz: Die Zeit, die für die Suche nach einem bestimmten Element in BST benötigt wird, beträgt O(log n), da bei jeder Suche die Hälfte des Baums von der Suche ausgeschlossen wird.

Nachteile von

BST:

• Wenn das Gleichgewicht des Baums gestört ist (z. B. wenn alle Elemente in einer Reihe platziert sind), sinkt die Sucheffizienz auf O(n).
• Erfordert das Speichern sowohl des linken als auch des rechten Zeigers für jeden Knoten, was den Speicherverbrauch auf dem Computer erhöht.

---

Wörterbuch

Wörterbuch ist wie ein Wörterbuchbuch, es enthält ein Wort und seine Definition, seine Elemente Schlüssel (Schlüssel) und Wert hat (Wert).

Wenn wir

Dictionary nach einem Element abfragen, gibt es das Element in O(1)-Zeit an uns zurück. Wörterbücher können durch Hashing genau diese Geschwindigkeit bereitstellen.

Hashing ist der Prozess der Umwandlung der Daten im Eingabearray in eine Folge von Bits mithilfe eines speziellen Algorithmus.

Eine Hash-Funktion ist ein Algorithmus, der aus einer Zeichenfolge beliebiger Länge eine Folge von Bits fester Länge generiert.

Hash-Tabelle ist eine großartige Kombination aus Arrays und verknüpften Listen. Wir können es uns wie folgt vorstellen:

Kollision (Kollisionen) liegt vor, wenn zwei verschiedene Eingaben einen Hashwert erzeugen. Im Bild oben sind die kollidierenden Elemente als verknüpfte Liste verbunden. Durch die Verbesserung der Hash-Funktion kann die Kollisionswahrscheinlichkeit verringert werden.

Ein einfaches Beispiel für eine Hash-Funktion ist:

typedef struct node
{
    int number;
    struct node *next;
}
node;

Dieser Artikel verwendet die CS50x 2024-Quelle.

Das obige ist der detaillierte Inhalt vonCS – Woche 5. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!