C语言中的自引用结构

你好，未来的编程巫师们！今天，我们将踏上一段激动人心的旅程，探索C语言中的自引用结构。别担心，如果这听起来有点吓人——我保证我们会将其分解成即使是我奶奶也能理解的小块（相信我，她仍然认为鼠标只是一个毛茸茸的小动物）。

自引用结构是什么？

想象你在聚会上，你想向某人介绍你的朋友。你可能会说：“这是我的朋友Alex，Alex也是一个软件开发者。”在这个介绍中，你提到了Alex两次——一次是名字，一次是职业。这就是C语言中自引用结构的工作原理！

自引用结构是一个在其定义中包含指向同类型结构体的指针的结构体。这就好比俄罗斯套娃，但里面不是越来越小的娃娃，而是同类型的结构体一直嵌套。

定义自引用结构

让我们深入了解如何定义这些迷人的结构。这里有一个简单的例子：

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

在这个例子中，我们定义了一个名为Node的结构体。它包含两个成员：

1. 一个整数data用于存储信息。
2. 一个指针next指向另一个Node结构体。

这就是自引用结构的本质——它在自己的定义中引用自己。

自引用结构的示例

现在，让我们看看一些我们可能会使用自引用结构的实际示例。

1. 链表节点

我们已经看到了这个例子，让我们进一步分解：

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

这个结构体非常适合创建链表。每个节点包含一些数据和指向列表中下一个节点的指针。

2. 树节点

树是自引用结构的另一个常见用例：

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

在这里，树中的每个节点可以有最多两个子节点（左和右），允许我们创建二叉树。

3. 图节点

对于敢于冒险的人，下面是如何在图中表示节点的：

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

在这种情况下，我们有一个指向其他GraphNode结构体的指针数组，表示图中的连接。

使用自引用结构创建链表

现在我们了解了基础知识，让我们使用自引用结构创建一个简单的链表。如果你一开始不理解，不用担心——罗马不是一天建成的，编程技能也不是！

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

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

// 创建新节点的函数
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// 打印链表的函数
void printList(struct Node* head) {
struct Node* current = head;
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("我们的链表: ");
printList(head);

return 0;
}

让我们分解一下：

1. 我们像之前一样定义了Node结构体。
2. 我们创建了一个createNode函数，用于分配新节点的内存并初始化其数据。
3. 我们有一个printList函数，用于遍历链表并打印每个节点的数据。
4. 在main函数中，我们创建了一个包含三个节点的链表并打印它。

运行这个程序，你应该会看到：

我们的链表: 1 -> 2 -> 3 -> NULL

使用自引用结构创建双向链表

现在，让我们升级一下，创建一个双向链表。这就像一个普通的链表，但每个节点还包含一个指向前一个节点的指针。这就像一条双向街道，而不是单向街道！

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

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

// 创建新节点的函数
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;
}

// 正向打印双向链表的函数
void printForward(struct DoubleNode* head) {
struct DoubleNode* current = head;
printf("正向: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

// 反向打印双向链表的函数
void printBackward(struct DoubleNode* tail) {
struct DoubleNode* current = tail;
printf("反向: ");
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;
}

在这个例子中：

1. 我们的DoubleNode结构体现在有next和prev两个指针。
2. 我们创建了用于正向和反向打印链表的函数。
3. 在main函数中，我们创建了一个双向链表并设置了next和prev指针。

运行这个程序应该会给你：

正向: 1 <-> 2 <-> 3 <-> NULL
反向: 3 <-> 2 <-> 1 <-> NULL

使用自引用结构创建树

最后，让我们使用自引用结构创建一个简单的二叉树。把这个想象成一个家族树，每个人最多有两个孩子。

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

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

// 创建新节点的函数
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;
}

// 中序遍历的函数
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("树的中序遍历: ");
inOrderTraversal(root);
printf("\n");

return 0;
}

在这个最后的例子中：

1. 我们的TreeNode结构体有left和right指针指向子节点。
2. 我们创建了一个中序遍历的函数，它先访问左子树，然后是根节点，最后是右子树。
3. 在main函数中，我们创建了一个简单的二叉树并进行了中序遍历。

运行这个程序应该输出：

树的中序遍历: 4 2 5 1 3

至此，各位！我们已经穿越了自引用结构的领域，从简单的链表到双向链表，甚至是二叉树。记住，熟能生巧，所以不要害怕尝试这些结构并创造你自己的变体。谁知道呢？你可能就是下一个发明突破性数据结构的人！

快乐编程，愿自引用结构与你同在！

Credits: Image by storyset