Struct Dinamis

Struct dapat ditempatkan pada heap seperti tipe lainnya, dan pola inilah yang menopang banyak struktur data klasik karena ukuran koleksinya baru diketahui saat program berjalan. Topik ini membahas alokasi struct tunggal lewat malloc beserta akses anggotanya lewat pointer, serta aturan struct yang anggotanya menunjuk ke tipe struct itu sendiri. Bagian akhir memperkenalkan rantai simpul sederhana sebagai pengenalan linked list. Setelah topik ini, prinsip yang sama dapat dipakai untuk union, enum, dan tipe bentukan lainnya.

Mengalokasikan struct pada heap#

Memesan satu struct sama persis dengan memesan tipe lain, yaitu malloc(sizeof(struct nama)), dan hasilnya diakses lewat operator -> karena pemegangnya berupa pointer. Ukuran yang dihitung sizeof sudah memperhitungkan penyelarasan (padding) antaranggota, sehingga idiom tersebut selalu memberi ruang yang cukup tanpa perlu menghitung sendiri. Isi struct hasil alokasi tidak diatur oleh malloc, sehingga anggotanya wajib diisi lebih dahulu. Gunakan calloc apabila keadaan nol diinginkan.

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

struct siswa {
    char nama[24];
    float nilai;
};

int main(void)
{
    struct siswa *s = malloc(sizeof(struct siswa));
    if (s == NULL) {
        return 1;
    }

    strcpy(s->nama, "Budi");
    s->nilai = 87.5f;

    printf("Ukuran struct siswa: %zu byte\n", sizeof(struct siswa));
    printf("Nama : %s\n", s->nama);
    printf("Nilai: %.1f\n", s->nilai);

    free(s);
    return 0;
}

Ukuran struct siswa: 28 byte
Nama : Budi
Nilai: 87.5

Ukuran 28 byte berasal dari 24 byte larik nama ditambah 4 byte nilai, dan angkanya dapat berbeda pada platform lain karena penyelarasan. Alasan memilih heap untuk struct tunggal biasanya bukan ukuran, melainkan masa hidup, yaitu data yang harus tetap ada setelah fungsi pembuatnya kembali atau data yang akan dioper antarbagian program. Apabila dibutuhkan banyak sekaligus, pola yang sama berlaku dengan malloc(n * sizeof(struct siswa)) untuk n struct berurutan dalam satu blok.

Koleksi struct pun mengikuti aturan akses yang serupa. Pada penampung berisi beberapa struct, elemen kelas[i] sudah berupa struct utuh sehingga anggotanya diakses dengan titik seperti kelas[i].nilai, sedangkan pointer tunggal seperti s di atas tetap memerlukan panah. Keduanya sering bercampur pada satu program, misalnya larik penunjuk yang setiap unsurnya dialokasikan terpisah, sehingga pemilihan titik atau panah cukup mengikuti tipe yang sedang dipegang, bukan sekadar meniru contoh.

Struct yang mereferensikan dirinya sendiri#

Anggota struct boleh berupa pointer ke tipe struct yang sedang didefinisikan, tetapi tidak boleh berupa struct utuh bertipe itu sendiri. Alasannya terletak pada perhitungan ukuran, yaitu struct yang memuat dirinya sendiri tidak pernah selesai dihitung karena setiap salinan memuat salinan lagi, sedangkan ukuran pointer sudah pasti di semua platform.

// tidak-dijalankan
struct simpul {
    int nilai;
    struct simpul berikut;   /* ditolak: ukuran tidak pernah selesai dihitung */
};

Bentuk yang sah menggunakan pointer, dan pola inilah fondasi dari linked list, yaitu rantai simpul yang setiap anggotanya menunjuk simpul berikutnya sampai penanda akhir.

// tidak-dijalankan
struct simpul {
    int nilai;                /* data yang disimpan */
    struct simpul *berikut;   /* alamat simpul berikutnya */
};

Definisi seperti ini sah karena pada saat anggota berikut dideklarasikan, yang dibutuhkan hanya ukuran pointer, bukan ukuran struct yang lengkap. Penggunaan kata kunci struct yang sama juga memungkinkan satu struct menunjuk struct lain yang definisinya baru muncul setelahnya.

Ukuran satu simpul kini dapat dihitung, yaitu ukuran int ditambah ukuran pointer ditambah kemungkinan penyelarasan, dan angkanya tetap wajar karena pointer berukuran tetap di satu platform. Setiap simpul nanti dipesan dengan malloc tersendiri, sehingga simpul-simpulnya boleh tersebar di heap tanpa harus berurutan. Keterhubungannya murni dibentuk oleh alamat yang tersimpan pada anggota berikut, bukan oleh letak fisiknya di memori.

Membangun dan menelusuri rantai simpul#

Program berikut menyusun rantai tiga simpul dengan pola penyisipan di depan, yaitu setiap simpul baru menunjuk kepala lama lalu menjadi kepala yang baru. Setelah tersusun, rantai ditelusuri lewat pointer p yang berpindah dari simpul ke simpul, lalu setiap simpul dibebaskan satu per satu.

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

struct simpul {
    int nilai;
    struct simpul *berikut;
};

int main(void)
{
    struct simpul *kepala = NULL;

    int data[3] = {30, 20, 10};
    for (int i = 0; i < 3; i = i + 1) {
        struct simpul *baru = malloc(sizeof(struct simpul));
        if (baru == NULL) {
            return 1;
        }
        baru->nilai = data[i];
        baru->berikut = kepala;
        kepala = baru;
    }

    for (struct simpul *p = kepala; p != NULL; p = p->berikut) {
        printf("Simpul: %d\n", p->nilai);
    }

    while (kepala != NULL) {
        struct simpul *berikutnya = kepala->berikut;
        free(kepala);
        kepala = berikutnya;
    }
    printf("Rantai telah dibebaskan seluruhnya.\n");
    return 0;
}

Simpul: 10
Simpul: 20
Simpul: 30
Rantai telah dibebaskan seluruhnya.

Urutan keluaran menjadi 10, 20, 30 karena penyisipan selalu dilakukan di depan, sehingga nilai yang dimasukkan pertama justru berada paling akhir. Pola penyisipan di depan dipilih karena paling ringkas, yaitu dua penugasan tanpa perlu menelusuri ujung rantai. Penyisipan di akhir juga mungkin, tetapi menuntut perulangan yang mencari simpul terakhir terlebih dahulu atau pointer tambahan yang selalu menyimpan alamat ekornya. Keduanya memakai definisi struct yang sama, sehingga pilihannya murni keputusan desain dan bukan perubahan tipe data.

Pada perulangan pembebasan, alamat simpul berikutnya disimpan lebih dahulu ke berikutnya sebelum free dijalankan, karena setelah simpul dibebaskan, pembacaan kepala->berikut pada simpul yang sama tidak lagi sah. Pola menyimpan alamat dahulu sebelum membebaskan inilah yang berlaku untuk setiap penelusuran yang menghapus elemen di tengah jalan.

Kesalahan umum#

Empat kesalahan berikut paling sering muncul ketika struct dinamis baru pertama kali dipraktikkan, dan semuanya dapat dikenali dari pola pesannya.

• Mengakses anggota dengan operator titik pada pointer. Penulisan s.nilai ketika s bertipe pointer adalah error kompilasi, karena operator titik menuntut struct utuh. Gunakan s->nilai, atau dereferensikan lebih dahulu dengan (*s).nilai apabila bentuk panjangnya memang diinginkan.
• Menyimpan anggota bertipe struct itu sendiri. Definisi semacam ini ditolak kompilator karena ukurannya tidak pernah selesai dihitung. Ubah anggotanya menjadi pointer ke tipe tersebut, seperti struct simpul *berikut.
• Membebaskan rantai tanpa menyimpan alamat berikutnya. Pembacaan kepala->berikut setelah free(kepala) memakai simpul yang sudah dibebaskan, dan hasilnya tidak terdefinisi. Simpan alamat simpul berikutnya pada variabel lokal sebelum setiap pembebasan.
• Kehilangan kepala rantai saat menelusuri. Variabel kepala yang ikut berpindah membuat alamat awal rantai hilang, sehingga sisa simpulnya tidak dapat dibebaskan. Gunakan pointer kerja terpisah untuk menelusuri dan pertahankan kepala sebagai titik kembali.

Ringkasan#

• Struct dialokasikan di heap dengan malloc(sizeof(struct nama)) dan diakses lewat operator -> ketika pemegangnya pointer.
• Anggota bertipe struct yang sama tidak dimungkinkan standar, sedangkan anggota pointer ke tipe yang sama sah dan menjadi dasar linked list.
• Rantai simpul dibangun dengan menghubungkan setiap simpul baru ke kepala lama, ditelusuri hingga NULL, dan dibebaskan dengan menyimpan alamat berikutnya lebih dahulu.

Referensi#

• Struct declaration — cppreference.com — Aturan tipe struct yang belum lengkap beserta anggota penunjuk ke tipe yang sedang didefinisikan.
• malloc(3) — Linux man-pages project — Kontrak alokasi blok yang dipakai untuk setiap simpul pada rantai.