Membangun Tumpukan Tertaut Dinamis di C: Implementasi dan Kesalahan

Kebanyakan pemula menganggap struktur data bersifat statis. Sebenarnya tidak. Tumpukan tertaut adalah binatang yang dinamis. Ia tumbuh dan menyusut dengan cepat. Anda tidak mengalokasikan memori terlebih dahulu. Anda mengambilnya saat Anda membutuhkannya. Lepaskan setelah Anda selesai.

Contoh ini menggunakan bilangan bulat. Ubah typedef int stack_data menjadi float atau char jika Anda mau. Logikanya tetap sama.

Antarmuka

Lihat headernya. Itu adalah kontrak.

stack_init menyiapkan kekacauan. stack_clear menghapusnya. stack_empty memberi tahu Anda jika masih ada yang tersisa. push memasukkan data. pop menariknya keluar.

Sederhana. Membersihkan.

Mesin

File kode menyembunyikan nyali.

top menunjuk ke item terbaru. NULL artinya kosong.

stack_init baru saja menyetel ulang top menjadi NULL. Selesai.

stack_clear muncul hingga kosong. Ini sebuah lingkaran. Itu murah.

stack_empty memeriksa apakah top adalah NULL. Mengembalikan 1 jika benar. 0 jika salah.

stack_push melakukan pekerjaan berat.

Ini mengalokasikan memori. Mengatur data. Tautkan ke atas yang lama. Pembaruan atas.

stack_pop membalikkan prosesnya.

Ini mengambil data. Memindahkan atas ke bawah. Membebaskan node lama. Mengembalikan nilainya.

Jika tumpukannya kosong? Ini mengembalikan sampah. Jangan keluar dari tumpukan kosong.

Penyembunyian Informasi

Ini adalah kuncinya.

Anda hanya melihat headernya saja. Anda tidak melihat kodenya.

Tumpukan bisa menggunakan array. Petunjuk. File. Daftar tertaut. Tidak masalah.

Selama antarmukanya berfungsi, Anda tidak peduli bagaimana antarmuka itu dibuat.

Itu adalah informasi yang disembunyikan. Ini bukan sekedar kata kunci. Begitulah cara Anda membangun perangkat lunak yang tidak rusak saat Anda mengubah internalnya.

C Gotcha

C tidak memaafkan kesalahan.

1. Tanda kurung penting. (*p).i tidak sama dengan *p.i. Seseorang mereferensikan penunjuknya terlebih dahulu. Yang lain mengakses anggota lalu melakukan dereferensi. Lakukan kesalahan dan Anda crash.
2. Memori bocor. Jangan pernah menyetel top = NULL saja. Anda menjadikan setiap node dalam daftar menjadi yatim piatu. Anda kehilangan datanya. Anda kehilangan ingatan. Gunakan gratis. Selalu.
3. Sertakan header. NULL berada di stdio.h. Jika Anda lupa, kode Anda mungkin dapat dikompilasi pada beberapa kompiler. Itu tidak akan terjadi pada orang lain. Atau itu akan mendefinisikan NULL sebagai nol dengan cara yang aneh. Sertakan jika Anda menggunakan pointer.

Apa Selanjutnya?

Tumpukan dasarnya sederhana. Tumpukan nyata membutuhkan lebih banyak.

Tambahkan dup. Gandakan elemen teratas. Tambahkan hitungan. Kembalikan jumlah item. Tambahkan tambah. Pop dua teratas, tambahkan, dorong hasilnya.

Membangun program driver. Tulis makefile. Kompilasi itu. Jalankan.

Jika crash, Anda melewatkan gratis. Atau Anda mengakses memori yang dibebaskan. Debug itu.

Pemeriksaan Realitas

Alokasi dinamis cepat. Sampai ternyata tidak.

malloc dan free memiliki overhead. Dalam putaran yang ketat, itu bertambah.

Tapi untuk penggunaan umum? Ini fleksibel. Itu standar. Ini adalah apa yang akan Anda lihat di sebagian besar basis kode C.

Tumpukan tertaut adalah blok penyusun.

Anda akan menggunakannya untuk panggilan fungsi. Untuk evaluasi ekspresi. Untuk tombol undo.

Itu ada dimana-mana.

Ingat saja: jika Anda mengalokasikannya, Anda membebaskannya. Atau.

“Kode itu seperti humor