C 認知結構中的自引用結構

你好，未來的編程巫師們！今天，我們將踏上一段令人興奮的旅程，探索 C 認知結構中的自引用結構。別擔心這聽起來有點令人卻步——我保證我們會把它分解成即使是我的祖母也能理解的碎片（相信我，她還認為老鼠就是一種小毛茸茸的動物）。

C - Self-Referential Structures

自引用結構是什麼？

想像你在一個派對上，你想向別人介紹你的朋友。你可能會說：「這是我的朋友 Alex，而且 Alex 也是一名軟件開發者。」在這個介紹中，你提到了 Alex 兩次——一次是名字，一次是職業。這與 C 認知結構中的自引用結構的工作原理相似！

自引用結構是一種在其定義中包含指向同類型結構的指針的結構。這就像一個俄羅斯套娃，但裡面不是更小的娃娃，而是同類型的結構一路到底。

定義自引用結構

讓我們深入了解一下我們如何實際定義這些引人入勝的結構。以下是一個簡單的例子：

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

在這個例子中，我們定義了一個名為 Node 的結構。它包含兩個成員：

一個整數 data 用於存儲一些信息。
一個指針 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;
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("我們的鏈表: ");
printList(head);

return 0;
}

讓我們分解這個過程：

我們像以前一樣定義我們的 Node 結構。
我們創建一個 createNode 函數，為新節點分配內存並初始化其數據。
我們有一個 printList 函數，遍歷列表並打印每個節點的數據。
在 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("Forward: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

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

在這個例子中：

我們的 DoubleNode 結構現在既有 next 指針也有 prev 指針。
我們創建了正向和反向打印列表的函數。
在 main 函數中，我們創建了一個雙向鏈表並設置了 next 和 prev 指針。

運行這個程序應該給你：

Forward: 1 <-> 2 <-> 3 <-> NULL
Backward: 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;
}

在這個最後的例子中：

我們的 TreeNode 結構有 left 和 right 指針，指向子節點。
我們創建了一個中序遍歷的函數，它先訪問左子樹，然後是根節點，最後是右子樹。
在 main 函數中，我們創建了一個簡單的二叉樹並進行了中序遍歷。

運行這個程序應該輸出：

樹的中序遍歷: 4 2 5 1 3

好了，各位！我們已經穿越了自引用結構的世界，從簡單的鏈表到雙向鏈表，甚至是二叉樹。記住，熟練使人完美，所以不要害怕嘗試這些結構並創造你自己的變種。誰知道呢？你可能就是下一個發明突破性數據結構的人！

快樂編程，願自引用結構與你同在！

Credits: Image by storyset