Struktur Data
Rabu, 29 Desember 2010
Tree
Ilustrasi struktur data tree:
Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.
Contoh : node E memiliki in degree 1 dan out degree 2
Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : node A adalah root
Subtree / child adalah bagian salah satu node dibawah root sampai ke bawah.
Contoh : tree C adalah right subtree dari A dan tree B merupakan left subtree dari A
node G dan F merupakan child dari node C
node F merupakan parent dari node J dan K
Ancestor adalah Node yang berada di atas node lain.
Contoh : node B adalah ancestor dari node E
Descendant adalah node yang berada di bawah node lain.
Contoh : node E adalah descendant dari node A.
Leaf (daun) adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.
Contoh : node D, H, I, J, K, dan G adalah leaf
Sibling adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A
Height (ketinggian) adalah level tertinggi dari tree ditambah 1.
Contoh : height dari tree A adalah 3 + 1 = 4
Weight (bobot) adalah jumlah leaf(daun) pada tree.
Contoh : weight dari tree A adalah 6
BINARY TREE
Sebuah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal 2 subtree yang disebut sebagai subpohon kiri(left subtree) dan subpohon kanan (right subtree) dan kedua subtree tersebut harus terpisah, atau dengan kata lain tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.
Binary tree terdiri dari :
1. Full Binary Tree : semua node (kecuali leaf pasti memiliki 2 anak dan tiap subtree memiliki panjang path yang sama)
2. Complete Binary Tree : mirip dengan full binary tree, tetapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf memiliki 2 anak)
3. Skewed Binary Tree : binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak
BINARY SEARCH TREE
Binary tree dengan sifat bahwa nilai dari semua left child harus lebih kecil daripada nilai dari right child dan parentnya.
Contoh :
42 77 60 90 85 97 50 25 35 15 10 5
Contoh Implementasi Binary Search Tree :
Graph
Graph adalah salah satu jenis struktur data, umumnya terdiri dari vertex dan edge. Vertex biasanya dihubungkan dengan edge sehingga menjadi suatu kesatuan yang disebut graph. Sebagai contohnya bisa dilihat pada peta kota, dimana kota disini menjadi sebagai vertex dan jalur yang menghubungkannya berlaku sebagai edge.
Terdapat 3 jenis graph, yaitu :
-Graph Berarah,
-Graph Berbobot, dan;
-Graph Tidak Berbobot.
Cara pengurutan elemen terdapat 3 cara, yakni :
1. Preorder : Node-Left-Right
2. Inorder : Left-Node-Right
3. Postorder : Left-Right-Node
Contoh Gambar Graph
Sifat-sifat Graph
· Sebuah graph mungkin hanya terdiri dari satu simpul.
· Sebuah graph belum tentu semuanya terhubung dengan simpul.
· Sebuah graph mungkin mempunyai simpul yang tak terbubung dengan simpul yang lain
· Sebuah graph mungkin semua simpulnya saling berhubungan.
Queue
Metode ini menggunakan konsep FIFO, dimana data yang pertama masuk, yang akan dihapus pertama kali juga data yang pertama.
Pengoperasian yang tersedia di metode ini adalah berikut ini :
Create : membuat antrian baru
Enqueue : menambah elemen ke antrian
Dequeue : menghapus elemen dari antrian.
Isempty : fungsi untuk mengecek antrian tersebut kosong atau tidak.
Isfull : fungsi unutk mengecek antrian tersebut penuh atau tidak.
Overflow : peringatan ini akan muncul jika elemen ditambah ke antrian yang sudah penuh.
Underflow : peringatan ini akan muncul jika elemen dihapus dari antrian yang masih kosong.
Head / Front : elemen antrian paling depan.
Tail / Back : elemen antrian paling belakang.
Stack
Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri Stack :
- Elemen TOP (puncak) diketahui
- penisipan dan penghapusan elemen selalu dilakukan di TOP
- LIFO
Pemanfaatan Stack :
- Perhitungan ekspresi aritmatika (posfix)
- algoritma backtraking (runut balik)
- algoritma rekursif
Operasi Stack yang biasanya :
- Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
- Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack
- IsEmpty ()
- IsFull ()
- dan beberapas selektor yang lain
Contohnya :
1 |
|
| 2 |
| 3 |
| 4 |
| 5 |
| ||||||||
|
|
|
|
|
| |||||||||||||
|
|
|
| c |
| |||||||||||||
|
|
| b | b | b | |||||||||||||
|
| a | a | a | a | |||||||||||||
create (s,5) | Push (s,a) | Push(s,b) | Push(s,c) | Pop(s) | ||||||||||||||
6 |
| 7 |
| 8 |
| 9 |
| 10 |
| |||||||||
|
|
| 9 |
| ||||||||||||||
|
| g | g | g | ||||||||||||||
| f | f | f | f | ||||||||||||||
a | a | a | a | a | ||||||||||||||
Pop(s) | Push(s,f) | Push(s,g) | Push(s,9) | Pop(s) |
Create : pembuatan suatu stack.
Push : pengisian data kedalam stack.
Pop : penghapusan data dari stack (dari paling atas)
Overflow : Stack sudah penuh, jika diisi lagi akan muncul peringatan ini.
Underflow : Stack masih kosong, namun jika ingin hapus lagi, akan muncul peringatan ini.
Himpunan Data
Himpunan data adalah suatu metode struktur data untuk menentukan apa yang perlu ditampilkan atau tidak pada suatu himpunan.
Umumnya pengoperasian himpunan data terdiri dari 3 jenis :
1 Intersection : menemukan nilai yang sama pada kedua himpunan, dan menampilkan hasil pengoperasian tersebut.
2 Union : menggabungkan nilai kedua himpunan, tanpa mengulangi nilai yang sama.
3 Difference B : menemukan nilai yang yang tersedia pada himpunan yang terpilih, namun tidak tersedia pada himpunan tujuan.
Contoh himpunan tersebut dapat dilihat dibawah ini :
Himpunan A : { A , B , C , D , E , F }
Himpunan B : { A , B , G , H , I , J }
Jadi, pengoperasian dapat dilakukan seperti ini :
Intersection : { A , B }
Union : { A , B , C , D , E , F , G , H , I , J }
A Difference B : { C , D , E , F }
B Difference A : { G , H , I , J }
Array
Array(1 dimensi)
array satu dimensi merupakan jenis array dasar dan jenis array yang paling sering digunakan, pemakaian array satu dimensi terutama dipakai dalam tipe data string (terutama dalam bahasa Pemograman C).
Terdapat 2 operasi array, adalah :
Pengoperasian terhadap satu elemen/posisi dari array
Pengoperasian terhadap array sebagai keseluruhan
Pengoperasian yang sering terjadi dalam array adalah proses pengambilan nilai elemen dari dank e posisi tertentu di array.
Berikut ini adalah contoh penyimpanan data kedalam array (satu dimensi) :
List[20] = 40, menyimpan nilai 40 kedalam posisi ke-20 dalam array List.
B[3] = “A”, menyimpan nilai “A” kedalam posisi ke-3 dalam array B.
Dan berikut ini adalah contoh pengambilan data dari array (dua dimensi):
Ambil = List[20], mengambil nilai dari posisi ke-20 dalam array List. (yakni : 40)
Txtnama.text = B[3], mengambil nilai dari posisi ke-3 dalam array B. (yakti : “A”)
Array (dua dimensi)
Array dua dimensi merupakan tipe array yang lain. A dua dimensi sering dipakai untuk merepresentasikan tabel dan matriks dalam pemrograman.
Perhatikan table berikut :
| 0 | 1 | 2 | 3 | 4 |
1 | A | B | C | D | E |
2 | F | G | H | I | J |
3 | K | L | M | N | O |
Contoh table Array dua dimensi.
Seperti yang anda dapat lihat, array dua dimensi sering digambarkan sebagai matriks, untuk mempermudah pengertian pada table tersebut. Perbedaan array satu dimensi dan dua dimensi adalah pada array satu hanya terdiri dari sebuah baris dan beberapa kolom, sedangkan array dua dimensi memiliki beberapa baris dan beberapa kolom yang bertipe sama.
Array dalam beberapa bahasa pemograman
1. Bahasa Pascal
array dalam bahasa Pascal dapat didefinisikan dengan indeks awal dan indeks akhirnya.
Contoh:
2. Bahasa C
Array dalam bahasa C selalu dimulai dari indeks 0. Array dapat didefinisikan secara statik atau dinamik. Jika didefinisikan statik, ukuran Array akan tetap dari awal program hingga akhir program. Jika didefinisikan dinamik, ukuran array dapat berubah selama program berjalan karena memesan tempat pada memori heap. Proses pemesanan tempat pada memori disebut dengan alokasi. Sedangkan proses pembebasan memori yang sudah dipesan disebut dengan dealokasi.
Contoh array statik:
Contoh Array dinamik:
3. Bahasa Java
Dalam bahasa Java tipe data array direpresentasikan sebagai sebuah objek khusus. Karena itu pada bahasa Java array yang dibuat selalu bersifat dinamik. Namun walaupun bersifat dinamik, array pada bahasa Java tidak perlu dihancurkan karena proes penghancuran dilakukan secara otomatis melalui suatu prosedur yang disebut denganPengumpulan sampah. Sama seperti bahasa C, indeks larik selalu dimulai dari 0.
Contoh:
4. PHP
Sama seperti di JAVA array di PHP juga merupakan sebuah object lebih tepatnya lagi map terorder. Ada dua tipe array di PHP, indexed array (simple array) dan associated array (key=>value array). Di PHP, element array bisa berupa string, Bilangan, boolean, dan semua tipe data primitive lainnya, termasuk larik juga bisa menjadi element larik lainnya.
Cara medefinisikan array:
Contoh indexed array (simple array):
Contoh associated array:
Penjelasan Struktur Data
Dalam istilah ilmu komputer, struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.
Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.
Struktur Data pada Umumnya
1. Array
3. Stack
4. Queue
5. Graph
6. Tree