CS- Minggu 5

Penjelasan terperinci mengenai struktur data: dari array ke pokok, dan kemudian ke jadual hash

Artikel ini membincangkan beberapa struktur data biasa secara mendalam, termasuk tatasusunan, senarai yang dipautkan, pokok carian binari (BSTs) dan jadual hash, dan menerangkan organisasi mereka dalam ingatan dan kelebihan dan kekurangannya.

Struktur maklumat dan struktur data abstrak

Struktur maklumat merujuk kepada cara maklumat dianjurkan dalam ingatan, sementara struktur data abstrak adalah pemahaman konseptual kami tentang struktur ini. Memahami struktur data abstrak membantu kami melaksanakan pelbagai struktur data dalam amalan.

---

Timbunan dan giliran

Beratur adalah struktur data abstrak yang mengikuti prinsip FIFO (pertama dalam, keluar pertama), sama seperti menunggu dalam barisan. Operasi utamanya termasuk enqueuing (menambahkan unsur ke ekor barisan) dan dequeuing (mengeluarkan elemen kepala barisan).

Tumpukan mengikuti prinsip LIFO (Terakhir dalam Pertama), sama seperti menyusun plat. Operasinya termasuk menolak (menambah unsur ke bahagian atas timbunan) dan muncul (mengeluarkan unsur -unsur atas timbunan).

---

Array

Arahan adalah struktur yang terus menyimpan data dalam ingatan. Seperti yang ditunjukkan dalam gambar di bawah, tatasusunan menduduki ruang penyimpanan berterusan dalam ingatan.

Program, fungsi, dan pembolehubah lain mungkin wujud dalam ingatan, serta data berlebihan yang telah digunakan sebelum ini. Jika anda perlu menambah elemen baru ke array, anda perlu menyusun semula memori dan menyalin keseluruhan array, yang boleh menjadi tidak cekap.

Walaupun pra-memperuntukkan memori terlalu banyak dapat mengurangkan operasi salinan, ia akan membazirkan sumber sistem. Oleh itu, adalah penting untuk memperuntukkan ingatan mengikut keperluan sebenar.

---

Senarai pautan

Senarai yang dipautkan adalah struktur data yang kuat yang membolehkan penggabungan nilai yang terletak di kawasan memori yang berbeza ke dalam senarai dan menyokong pengembangan atau pengurangan dinamik.

Setiap CS- Minggu 5 mengandungi dua nilai: nilai data dan penunjuk ke CS- Minggu 5 seterusnya. Nilai penunjuk CS- Minggu 5 terakhir adalah batal, menunjukkan akhir senarai yang dipautkan.

Dalam bahasa C, CS- Minggu 5 boleh ditakrifkan seperti berikut:

 <code class="c">typedef struct CS- Minggu 5e { int number; struct CS- Minggu 5e *next; } CS- Minggu 5e;</code>

Contoh berikut menunjukkan proses membuat senarai yang dipautkan:

Kekurangan senarai yang dipautkan termasuk keperluan untuk penunjuk penyimpanan memori tambahan dan ketidakupayaan untuk mengakses elemen secara langsung melalui indeks.

---

Pokok carian binari (BST)

Pokok carian binari adalah struktur pokok yang cekap menyimpan, mencari dan mengambil data.

Kelebihan BST adalah kecekapan dinamik dan carian (O (log n)), dan kelemahannya ialah kecekapan carian jatuh ke O (n) apabila pokok itu tidak seimbang dan memerlukan penunjuk penyimpanan memori tambahan.

---

Jadual Hash

Jadual hash adalah serupa dengan kamus dan mengandungi pasangan nilai utama. Ia menggunakan fungsi hash untuk memetakan kekunci untuk indeks array, dengan itu mencapai masa carian purata O (1).

Konflik hash (kekunci berganda yang dipetakan ke indeks yang sama) boleh diselesaikan dengan senarai yang dipautkan atau kaedah lain. Reka bentuk fungsi hash adalah penting untuk prestasi jadual hash. Contoh fungsi hash mudah adalah seperti berikut:

 <code class="c">#include <ctype.h> unsigned int hash(const char *word) { return toupper(word[0]) - 'A'; }</ctype.h></code>

Artikel ini disusun berdasarkan kod sumber CS50X 2024.

Atas ialah kandungan terperinci CS- Minggu 5. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!