STRUKTUR
DATA – DASAR STRUKTUR UNTUK PEMROGRAMAN
Struktur data adalah
cara pengorganisasian data tertentu di komputer sehingga bisa digunakan secara
efisien. Data
struktur menyediakan sarana untuk mengelola sejumlah besar data secara efisien,
seperti besar database dan internet.
Struktur data pada
dasarnya berevolusi untuk mensurvei tujuan menyimpan, mengambil dan mengatur
data secara logis.
Struktur data
dasar.
Ø Struktur Data Linier
1) Array
Array adalah sejumlah
elemen dalam urutan tertentu. Mereka diakses menggunakan bilangan bulat
untuk menentukan elemen mana
Diperlukan (meskipun
unsur-unsurnya hampir sama dengan jenis apapun)
Komputer digital
pertama menggunakan bahasa pemrograman mesin untuk mengatur dan mengakses
struktur array untuk tabel data,
Perhitungan vektor dan
matriks, dan untuk banyak keperluan lainnya.
Aplikasi
Array digunakan untuk
menerapkan vektor matematis dan matriks, serta jenis tabel persegi panjang
lainnya. Banyak
Database, kecil dan
besar, terdiri dari (atau termasuk) array satu dimensi yang elemennya adalah
catatan.
Array digunakan juga
untuk menerapkan struktur data lainnya, seperti tumpukan, tabel hash, deques,
antrian, tumpukan, string, dan VLists.
Serta digunakan untuk
menentukan aliran kontrol parsial atau lengkap dalam program
2) List
linked list adalah
struktur data yang terdiri dari sekelompok node yang bersama-sama mewakili
suatu urutan. Di bawah bentuk yang paling sederhana, setiap node terdiri dari
data dan referensi (dengan kata lain, sebuah link) ke simpul berikutnya di
urutan; Varian yang lebih kompleks menambahkan link
tambahan. Struktur ini memungkinkan penyisipan atau pemindahan elemen yang
efisien dari posisi manapun dalam urutan.
Keuntungan:
• Linked list adalah
struktur data dinamis, mengalokasikan memori yang dibutuhkan saat program
dijalankan.
• Operasi penyisipan
dan penghapusan node mudah diimplementasikan dalam linked list.
Kekurangan:
• Mereka memiliki
kecenderungan untuk membuang memori karena adanya petunjuk yang membutuhkan
ruang penyimpanan ekstra.
• Node dalam linked
list harus dibaca secara berurutan sejak awal karena linked list secara inheren
berurutan
q Doubly Linked Lists
adalah struktur
data yang terdiri dari satu set berurutan terkait record disebut
node. Setiap node berisi dua bidang, yang disebut link, yang merupakan
referensi ke yang node link sebelumnya dan berikutnya, masing-masing,
arahkan ke beberapa jenis dari terminator, biasanya node sentinel
atau null, untuk memfasilitasi traversal dari daftar.
q Self Organizing List
daftar yang
mengingatkan elemen-elemennya berdasarkan heuristik pengorganisasian diri
sendiri untuk memperbaiki akses rata-rata
waktu. Tujuan
dari daftar pengorganisasian sendiri adalah untuk meningkatkan efisiensi
pencarian linier dengan memindahkan barang yang sering diakses
Ke arah kepala
daftar Daftar pengorganisasian mandiri mendekati waktu konstan untuk akses
elemen dalam kasus terbaik. Sebuah self-
Daftar
pengorganisasian menggunakan algoritma reorganisasi untuk menyesuaikan diri
dengan berbagai distribusi kueri saat runtime.
Aplikasi
Penerjemah bahasa
seperti compiler dan interpreter menggunakan daftar mengorganisir diri untuk
mempertahankan tabel simbol selama kompilasi Atau interpretasi kode
sumber program.
q Skip List
Merupakan struktur
data yang memungkinkan pencarian cepat dalam memerintahkan urutan elemen.
Aplikasi
Daftar aplikasi dan
framework yang menggunakan daftar skip:
• Cyrus IMAP
server menyediakan sebuah "skiplist" pelaksanaan backend DB
(source file)
• Lucene
menggunakan skip list untuk mencari daftar postingan delta-encoded dalam waktu
logaritmik.
•
QMap (sampai ke Qt 4) kelas template dari Qt yang menyediakan kamus
q Vlist
VList adalah struktur
data yang dirancang oleh Phil Bagwell pada tahun 2002 yang menggabungkan
Pengindeksan array dengan perpanjangan mudah dari daftar terkait cons-based
(atau tunggal terkait). Seperti array, VLists memiliki constant-time pencarian
rata-rata dan hanya membutuhkan penyimpanan O (log n) untuk petunjuk.
Operasi utama VList
adalah:
Cari elemen kth (O (1)
rata-rata, O (log n) worst-case)
Tambahkan elemen ke
depan rata-rata VList (O (1)
q Zipper
Merupakan teknik untuk
mewakili struktur data agregat sehingga memudahkan dalam penulisan program.
Aplikasi
sering digunakan
dimana ada beberapa konsep 'fokus' atau bergerak dalam beberapa rangkaian data.
zipper telah digunakan pada:
• Xmonad, untuk
mengelola fokus dan penempatan windows
• makalah Huet
ini mencakup editor struktural berdasarkan ritsleting dan prover teorema
Ø Binary Trees
Merupakan struktur
data pohon dimana masing-masing node memiliki paling banyak dua anak
q Red-Black Tree
adalah struktur data
yang merupakan jenis pohon pencarian biner self-balancing.
Aplikasi
Red-Black Tree
menawarkan jaminan terburuk untuk waktu penyisipan, waktu penghapusan, dan waktu
pencarian.
q Splay Tree
Adalah pohon pencarian
biner yang menyesuaikan diri dengan properti tambahan yang baru saja diakses
elemennya dengan cepat
Keuntungan
• Implementasi
sederhana - sederhana dari pohon pencarian biner, seperti Red-Black Tree
• Kinerja rata-rata
kinerja yang sebanding sama efisiennya dengan pohon lainnya.
• Tapak tapak memori
kecil tidak perlu menyimpan data pembukuan
q Splay Tree
Adalah pohon pencarian
biner yang menyesuaikan diri dengan properti tambahan yang baru saja diakses elemennya
dengan cepat
Keuntungan
• Implementasi
sederhana - sederhana dari pohon pencarian biner, seperti Red-Black Tree
• Kinerja rata-rata
kinerja yang sebanding sama efisiennya dengan pohon lainnya.
• Tapak tapak memori
kecil tidak perlu menyimpan data pembukuan
q Threaded Binary Tree
Sebuah pohon biner
dijalin dengan membuat semua petunjuk anak yang tepat yang normalnya akan
menjadi null menunjuk ke penerus inorder
Node (jika ada), dan
semua pointer anak kiri yang normalnya akan null menunjuk ke inorder pendahulu
dari node
q Treap
treap dan pohon
pencarian biner acak adalah dua bentuk pohon pencarian biner yang saling
terkait. Struktur data yang mempertahankan seperangkat kunci pesanan yang
dinamis dan memungkinkan pencarian biner di antara tombol.
Ø Application Binary
Trees
q Abstract Syntax Tree
Abstract Syntax Tree
atau hanya pohon sintaksis, adalah representasi pohon sintaksis abstrak
struktur kode sumber ditulis dalam bahasa pemrograman. Setiap simpul pohon
menunjukkan konstruksi yang terjadi di Kode sumber. Sintaksnya
"abstrak" tidak mewakili setiap detail yang muncul dalam sintaks
sebenarnya.
Aplikasi
Abstrak pohon
sintaksis adalah struktur data yang banyak digunakan pada kompiler, karena
sifatnya mewakili struktur, biasanya merupakan hasil dari fase analisis sintaks
kompilator.
q Parse tree
atau pohon derivasi
adalah pohon berurutan yang berakar yang mewakili
Struktur sintaksis
dari sebuah string sesuai dengan beberapa tata bahasa bebas konteks.
q Decision tree
adalah alat pendukung
keputusan yang menggunakan grafik mirip pohon atau model keputusan dan
kemungkinan akibatnya, Termasuk hasil kejadian kebetulan, biaya sumber daya,
dan utilitas. Ini adalah salah satu cara untuk menampilkan sebuah
algoritma. Pohon keputusan biasanya digunakan dalam penelitian operasi,
khususnya dalam analisis keputusan
Keuntungan
• Mudah dipahami dan
diinterpretasikan. Orang bisa memahami model pohon keputusan setelah
penjelasan singkat.
• Memiliki nilai
bahkan dengan sedikit data keras. Wawasan penting dapat dihasilkan berdasarkan
pakar yang menjelaskan situasi (its
Alternatif,
probabilitas, dan biaya) dan preferensi mereka untuk hasil
q Finger Tree
adalah struktur data
fungsional murni yang digunakan untuk menerapkan struktur data fungsional
secara efisien. Sebuah Pohon jari memberi waktu diam diamortisasi
diamortisasi ke "jari" (daun) pohon, tempat penyimpanan data
