Selbstaufzählende Strukturen in C

Hallo da draußen, zukünftige Codierungszauberer! Heute begeben wir uns auf eine aufregende Reise in die Welt der selbstaufzählenden Strukturen in C. Keine Sorge, wenn das etwas einschüchternd klingt – ich verspreche, wir werden das in mundgerechte Stücke zerlegen, die sogar meine Großmutter verstehen könnte (und glaubt mir, sie denkt immer noch, ein Maus sei nur ein kleines pelziges Tier).

Was sind Selbstaufzählende Strukturen?

Stellen Sie sich vor, Sie sind auf einer Party und möchten Ihren Freund jemandem vorstellen. Sie könnten sagen: "Das ist mein Freund Alex, und Alex ist auch ein Softwareentwickler." In dieser Vorstellung beziehen Sie sich auf Alex zweimal – einmal durch den Namen und einmal durch den Beruf. Genau so funktionieren selbstaufzählende Strukturen in C!

Eine selbstaufzählende Struktur ist eine Struktur, die einen Zeiger auf eine Struktur desselben Typs in ihrer Definition enthält. Es ist wie eine russische Puppenstuben, aber anstatt kleiner Puppen innen, ist es die gleiche Art von Struktur bis zum Ende.

Definition einer Selbstaufzählenden Struktur

Lassen Sie uns einen Blick darauf werfen, wie wir diese faszinierenden Strukturen tatsächlich definieren. Hier ist ein einfaches Beispiel:

struct Node {
int data;
struct Node* next;
};

In diesem Beispiel haben wir eine Struktur namens Node definiert. Sie enthält zwei Member:

1. Eine Ganzzahl data, um einige Informationen zu speichern.
2. Einen Zeiger next, der auf eine andere Node-Struktur zeigt.

Dies ist das Wesen einer selbstaufzählenden Struktur – sie bezieht sich auf sich selbst in ihrer eigenen Definition.

Beispiele für Selbstaufzählende Strukturen

Nun schauen wir uns einige praktische Beispiele an, in denen wir selbstaufzählende Strukturen verwenden könnten.

1. Verkettete Listenknoten

Wir haben das bereits gesehen, aber lassen Sie uns es weiter aufschlüsseln:

struct ListNode {
int data;
struct ListNode* next;
};

Diese Struktur ist perfekt zum Erstellen einer verketteten Liste. Jeder Knoten enthält einige Daten und einen Zeiger zum nächsten Knoten in der Liste.

2. Baumknoten

Bäume sind eine andere häufige Verwendungszweck für selbstaufzählende Strukturen:

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

Hier kann jeder Knoten im Baum bis zu zwei Kinder (links und rechts) haben, was es uns ermöglicht, binäre Bäume zu erstellen.

3. Graphknoten

Für die Abenteuerlustigen unter Ihnen, hier ist, wie wir einen Knoten in einem Graphen darstellen könnten:

struct GraphNode {
int data;
struct GraphNode** neighbors;
int neighborCount;
};

In diesem Fall haben wir ein Array von Zeigern auf andere GraphNode-Strukturen, die die Verbindungen in unserem Graphen darstellen.

Erstellen einer Verketteten Liste mit Selbstaufzählender Struktur

Nun, da wir die Grundlagen verstehen, erstellen wir eine einfache verkettete Liste mit unserer selbstaufzählenden Struktur. Keine Sorge, wenn Sie nicht alles sofort verstehen – Rom wurde nicht an einem Tag erbaut, und auch Codierungskenntnisse nicht!

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

struct Node {
int data;
struct Node* next;
};

// Funktion zum Erstellen eines neuen Knotens
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Funktion zum Drucken der verketteten Liste
void printList(struct Node* head) {
struct Node* current = head;
printf("%d -> ", current->data);
current = current->next;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);

printf("Unsere verkettete Liste: ");
printList(head);

return 0;
}

Lassen Sie uns das aufschlüsseln:

1. Wir definieren unsere Node-Struktur wie zuvor.
2. Wir erstellen eine Funktion createNode, die Speicher für einen neuen Knoten alloziert und seine Daten initialisiert.
3. Wir haben eine printList-Funktion, die die Liste durchläuft und jede Knotendaten druckt.
4. In main erstellen wir eine verkettete Liste mit drei Knoten und drucken sie.

Wenn Sie dieses Programm ausführen, sollten Sie sehen:

Unsere verkettete Liste: 1 -> 2 -> 3 -> NULL

Erstellen einer Doppeltketteten Liste mit Selbstaufzählender Struktur

Nun, lassen wir uns steigern und eine doppeltkettete Liste erstellen. Das ist wie eine reguläre verkettete Liste, aber jeder Knoten hat auch einen Zeiger auf den vorherigen Knoten. Es ist wie eine zweispurige Straße anstatt einer einbahnigen Straße!

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

struct DoubleNode {
int data;
struct DoubleNode* next;
struct DoubleNode* prev;
};

// Funktion zum Erstellen eines neuen Knotens
struct DoubleNode* createDoubleNode(int data) {
struct DoubleNode* newNode = (struct DoubleNode*)malloc(sizeof(struct DoubleNode));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// Funktion zum Drucken der doppeltketteten Liste nach vorne
void printForward(struct DoubleNode* head) {
struct DoubleNode* current = head;
printf("Vorne: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

// Funktion zum Drucken der doppeltketteten Liste nach hinten
void printBackward(struct DoubleNode* tail) {
struct DoubleNode* current = tail;
printf("Hinten: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->prev;
}
printf("NULL\n");
}

int main() {
struct DoubleNode* head = createDoubleNode(1);
head->next = createDoubleNode(2);
head->next->prev = head;
head->next->next = createDoubleNode(3);
head->next->next->prev = head->next;

struct DoubleNode* tail = head->next->next;

printForward(head);
printBackward(tail);

return 0;
}

In diesem Beispiel:

1. Unsere DoubleNode-Struktur hat jetzt sowohl next- als auch prev-Zeiger.
2. Wir erstellen Funktionen zum Drucken der Liste nach vorne und hinten.
3. In main erstellen wir eine doppeltkettete Liste und setzen sowohl die next- als auch die prev-Zeiger.

Wenn Sie dieses Programm ausführen, sollten Sie sehen:

Vorne: 1 <-> 2 <-> 3 <-> NULL
Hinten: 3 <-> 2 <-> 1 <-> NULL

Erstellen eines Baumes mit Selbstaufzählender Struktur

Last but not least, erstellen wir einen einfachen binären Baum mit unserer selbstaufzählenden Struktur. Stellen Sie sich das als Familiengeschlecht vor, bei dem jede Person bis zu zwei Kinder haben kann.

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

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

// Funktion zum Erstellen eines neuen Knotens
struct TreeNode* createTreeNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Funktion zur In-Ordnung-Durchlauf
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}

int main() {
struct TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->left = createTreeNode(4);
root->left->right = createTreeNode(5);

printf("In-Ordnung-Durchlauf des Baumes: ");
inOrderTraversal(root);
printf("\n");

return 0;
}

In diesem letzten Beispiel:

1. Unsere TreeNode-Struktur hat left und right-Zeiger für die Kindknoten.
2. Wir erstellen eine Funktion für den In-Ordnung-Durchlauf, die den linken Zweig besucht, dann die Wurzel und schließlich den rechten Zweig.
3. In main erstellen wir einen einfachen binären Baum und führen einen In-Ordnung-Durchlauf durch.

Wenn Sie dieses Programm ausführen, sollte die Ausgabe sein:

In-Ordnung-Durchlauf des Baumes: 4 2 5 1 3

Und das war's, Leute! Wir haben die Welt der selbstaufzählenden Strukturen durchquert, von einfachen verketteten Listen bis hin zu doppeltketteten Listen und sogar binären Bäumen. Erinnern Sie sich daran, dass Übung den Meister macht, also experimentieren Sie mit diesen Strukturen und erstellen Sie Ihre eigenen Variationen. Wer weiß? Vielleicht entwickeln Sie ja die nächste bahnbrechende Datenstruktur!

Frohes Coden und möge die selbstaufzählenden Strukturen mit Ihnen sein!

Credits: Image by storyset