Struktur Self-referential dalam C

Hai sana, para ahli pengoding masa depan! Hari ini, kita akan mengemban sebuah perjalanan menarik ke dunia struktur self-referential dalam C. Jangan khawatir jika itu terdengar sedikit menakutkan - saya berjanji kita akan pecahnya menjadi bagian-bagian kecil yang bahkan nenek saya bisa mengerti (dan percayalah, dia masih berpikir bahwa mouse hanya adalah seekor hewan kecil yang berbulu).

C - Self-Referential Structures

Apa Itu Struktur Self-referential?

Imaginasikan Anda di sebuah pesta, dan Anda ingin mengenalkan teman Anda kepada seseorang. Anda mungkin akan katakan, "Ini adalah teman saya Alex, dan Alex juga seorang pengembang perangkat lunak." Dalam pengenalan ini, Anda merujuk kepada Alex dua kali - sekali dengan nama dan sekali dengan profesi. Ini mirip dengan bagaimana struktur self-referential bekerja dalam C!

Sebuah struktur self-referential adalah struktur yang mengandung pointer ke struktur yang sama jenisnya dalam definisinya. Itu seperti boneka Rusia beranak-anak, tapi bukan boneka kecil di dalamnya, melainkan jenis yang sama dari struktur sepanjang waktu.

Mendefinisikan Struktur Self-referential

Ayo masuk ke bagaimana kita sebenarnya mendefinisikan struktur ini. Ini adalah contoh sederhana:

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

Dalam contoh ini, kita mendefinisikan sebuah struktur yang disebut Node. Itu mengandung dua anggota:

Sebuah integer data untuk menyimpan beberapa informasi.
Sebuah pointer next yang menunjuk ke struktur Node lainnya.

Ini adalah esensi struktur self-referential - itu merujuk kepada dirinya sendiri dalam definisinya sendiri.

Contoh Struktur Self-referential

Sekarang, mari kita lihat beberapa contoh praktis di mana kita mungkin menggunakan struktur self-referential ini.

1. Node Linked List

Kita sudah melihat ini sebelumnya, tapi mari kita perincik lebih lanjut:

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

Struktur ini sempurna untuk membuat linked list. Setiap node mengandung beberapa data dan pointer ke node berikutnya dalam daftar.

2. Node Pohon

Pohon adalah kasus penggunaan lain yang umum untuk struktur self-referential:

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

Di sini, setiap node dalam pohon dapat memiliki hingga dua anak (kiri dan kanan), memungkinkan kita untuk membuat pohon biner.

3. Node Graf

Untuk yang berani, ini adalah bagaimana kita mungkin merepresentasikan node dalam graf:

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

Dalam kasus ini, kita memiliki array pointer ke struktur GraphNode lainnya, mewakili koneksi dalam graf kita.

Membuat Linked List dengan Struktur Self-referential

Sekarang kita mengerti dasarnya, mari kita buat linked list sederhana menggunakan struktur self-referential ini. Jangan khawatir jika Anda belum mengerti segalanya segera - Roma tidak dibangun dalam satu hari, dan pengalaman coding pun demikian!

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

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

// Fungsi untuk membuat node baru
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Fungsi untuk mencetak linked list
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("Linked list kita: ");
printList(head);

return 0;
}

mari kitauraikan ini:

Kita mendefinisikan struktur Node seperti sebelumnya.
Kita membuat fungsi createNode yang mengalokasikan memori untuk node baru dan menginisialisasi data.
Kita memiliki fungsi printList yang meng traversal list dan mencetak data setiap node.
Dalam main, kita membuat linked list dengan tiga node dan mencetaknya.

Ketika Anda menjalankan program ini, Anda seharusnya melihat:

Linked list kita: 1 -> 2 -> 3 -> NULL

Membuat Doubly Linked List dengan Struktur Self-referential

Sekarang, mari kita tingkatkan dan buat doubly linked list. Ini seperti linked list biasa, tapi setiap node juga memiliki pointer ke node sebelumnya. Itu seperti jalan dua arah bukan jalan satu arah!

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

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

// Fungsi untuk membuat node baru
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;
}

// Fungsi untuk mencetak linked list ke depan
void printForward(struct DoubleNode* head) {
struct DoubleNode* current = head;
printf("Maju: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

// Fungsi untuk mencetak linked list ke belakang
void printBackward(struct DoubleNode* tail) {
struct DoubleNode* current = tail;
printf("Mundur: ");
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;
}

Dalam contoh ini:

Struktur DoubleNode sekarang memiliki kedua pointer next dan prev.
Kita membuat fungsi untuk mencetak list ke depan dan ke belakang.
Dalam main, kita membuat doubly linked list dan mengatur kedua pointer next dan prev.

Menjalankan program ini seharusnya memberikan Anda:

Maju: 1 <-> 2 <-> 3 <-> NULL
Mundur: 3 <-> 2 <-> 1 <-> NULL

Membuat Pohon dengan Struktur Self-referential

Akhirnya, mari kita buat pohon biner sederhana menggunakan struktur self-referential ini. Pikirkan ini sebagai pohon keluarga, di mana setiap orang dapat memiliki hingga dua anak.

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

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

// Fungsi untuk membuat node baru
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;
}

// Fungsi untuk melakukan traversal in-order
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("Traversal in-order dari pohon: ");
inOrderTraversal(root);
printf("\n");

return 0;
}

Dalam contoh ini:

Struktur TreeNode memiliki left dan right pointer untuk anak node.
Kita membuat fungsi untuk melakukan traversal in-order, yang mengunjungi subtree kiri, kemudian root, kemudian subtree kanan.
Dalam main, kita membuat pohon biner sederhana dan melakukan traversal in-order.

Menjalankan program ini seharusnya mengeluarkan:

Traversal in-order dari pohon: 4 2 5 1 3

Dan begitu saja, teman-teman! Kita telah mengemban perjalanan ke dunia struktur self-referential, dari linked list sederhana hingga doubly linked list dan bahkan pohon biner. Ingat, latihan membuat sempurna, jadi jangan takut untuk mencoba struktur ini dan membuat variasi Anda sendiri. Siapa tahu? Anda mungkin adalah orang berikutnya yang menciptakan struktur data revolusioner baru!

Selamat coding, dan may the self-referential structures be with you!

Credits: Image by storyset

Tutorial Sebelumnya:

C - Array of Structures

Tutorial Seterusnya:

C - Jadual Carian