Struktur Data

Berbagai jenis struktur data yang cocok untuk berbagai jenis aplikasi, dan beberapa sangat khusus untuk tugas-tugas tertentu. Sebagai contoh, B-pohon yang sangat cocok untuk implementasi database, sementara compiler implementasi biasanya menggunakan tabel hash untuk mencari pengidentifikasi.

Struktur data menyediakan sarana untuk mengelola data dalam jumlah besar secara efisien, seperti besar database dan layanan pengindeksan internet . Biasanya, struktur data yang efisien adalah kunci untuk merancang efisien algoritma . Beberapa metode desain formal dan bahasa pemrograman menekankan struktur data, bukan algoritma, sebagai faktor kunci dalam pengorganisasian perancangan perangkat lunak. Menyimpan dan mengambil dapat dilakukan pada data yang tersimpan di kedua memori utama dan memori sekunder .

Sekilas

Sebuah array yang menyimpan sejumlah elemen dalam urutan tertentu. Mereka diakses menggunakan sebuah integer untuk menentukan elemen diperlukan (meskipun elemen mungkin hampir semua jenis). Array dapat tetap-panjang atau diupgrade.

Catatan (juga disebut tupel atau struct) adalah salah satu struktur data yang paling sederhana. Record A adalah nilai yang berisi nilai-nilai lain, biasanya dalam jumlah tetap dan berurutan dan biasanya diindeks oleh nama. Unsur-unsur catatan biasanya disebut ladang atau anggota.

Sebuah tabel hash (juga disebut kamus atau peta ) adalah variasi yang lebih fleksibel pada catatan, di mana pasangan nama-nilai dapat ditambahkan dan dihapus secara bebas.

Sebuah serikat jenis menentukan mana dari sejumlah tipe primitif diizinkan dapat disimpan dalam kasus, misalnya "mengambang atau integer panjang" nya. Kontras dengan catatan , yang dapat didefinisikan mengandung float dan integer, padahal dalam serikat, hanya ada satu nilai pada satu waktu.

Sebuah serikat tag (juga disebut varian , varian record, diskriminasi serikat, atau serikat disjoint) berisi lapangan tambahan yang menunjukkan jenisnya saat ini, untuk ditingkatkan keselamatan jenis.

Sebuah set adalah struktur data abstrak yang dapat menyimpan nilai-nilai tertentu, tanpa tertentu agar , dan tanpa nilai-nilai diulang. Nilai sendiri tidak diambil dari set, bukan satu tes nilai untuk keanggotaan untuk mendapatkan boolean "dalam" atau "tidak".

Grafik dan pohon-pohon yang terkait struktur data abstrak terdiri dari node . Setiap node berisi nilai dan juga satu atau lebih pointer ke node lain. Grafik dapat digunakan untuk mewakili jaringan, sedangkan pohon biasanya digunakan untuk menyortir dan mencari , memiliki node mereka diatur dalam beberapa urutan relatif berdasarkan nilai-nilai mereka.

Sebuah objek berisi bidang data, seperti catatan, dan juga berisi fragmen kode program untuk mengakses atau memodifikasi bidang tersebut. Struktur data tidak mengandung kode, seperti yang di atas, disebut struktur data tua polos .

Banyak orang lain yang mungkin, tetapi mereka cenderung variasi lebih lanjut dan senyawa di atas.

Prinsip-prinsip dasar

Struktur data umumnya didasarkan pada kemampuan komputer untuk mengambil dan menyimpan data di setiap tempat di memori, yang ditentukan oleh alamat-a bit string yang dapat disimpan dalam memori sendiri dan dimanipulasi oleh program. Dengan demikian catatan dan berbagai struktur data didasarkan pada menghitung alamat item data dengan operasi aritmatika , sedangkan struktur data terkait didasarkan pada menyimpan alamat dari item data dalam struktur itu sendiri. Banyak struktur data menggunakan kedua prinsip, kadang-kadang dikombinasikan dengan cara non-sepele (seperti di XOR menghubungkan ).

Pelaksanaan struktur data biasanya memerlukan menulis satu set prosedur yang membuat dan memanipulasi contoh struktur itu. Efisiensi struktur data tidak dapat dianalisis secara terpisah dari operasi tersebut. Pengamatan ini memotivasi konsep teoritis dari tipe abstrak Data , struktur data yang didefinisikan secara tidak langsung dengan operasi yang dapat dilakukan di atasnya, dan sifat-sifat matematika dari operasi-operasi (termasuk ruang mereka dan biaya waktu).

Dukungan bahasa

Kebanyakan bahasa assembly dan beberapa bahasa tingkat rendah, seperti BCPL (Basic Combined Programming Language), dukungan kurangnya untuk struktur data. Banyak bahasa pemrograman tingkat tinggi dan beberapa bahasa assembly-tingkat yang lebih tinggi, seperti MASM , di sisi lain, memiliki sintaks khusus atau lainnya built-in dukungan untuk struktur data tertentu, seperti vektor (satu dimensi array ) di C bahasa atau array multi-dimensi di Pascal .

Kebanyakan bahasa pemrograman memiliki semacam perpustakaan mekanisme yang memungkinkan implementasi struktur data yang akan digunakan kembali oleh program yang berbeda. Bahasa modern biasanya datang dengan perpustakaan standar yang mengimplementasikan struktur data yang paling umum. Contohnya adalah + + C Standard Template Library , yang Java Collections Framework , dan Microsoft 's . NET Framework .

Bahasa modern juga umumnya mendukung pemrograman modular , pemisahan antara antarmuka modul perpustakaan dan pelaksanaannya. Beberapa menyediakan tipe data buram yang memungkinkan klien untuk menyembunyikan rincian implementasi. bahasa pemrograman berorientasi objek , seperti C + + , Java dan Smalltalk dapat menggunakan kelas untuk tujuan ini.

Banyak struktur data yang dikenal memiliki bersamaan versi yang memungkinkan beberapa benang komputasi untuk mengakses struktur data secara bersamaan.