Struktur Data Queue

Queue

queue menggunakan system FIFO (first in first out)

pada queue data yang di dequeue adalah data yang paling awal ditambahkan

kita bisa menemukan  system Queue di loket pembelian ticket

operasi umum  yang digunakan di queue yaitu Create, Enqueue, Dequeue, Head, Tail

bahasa pemrograman untuk queue

Create

isi.Size = New Point(kolom, lebar)          misalnya     ---- >       isi.size = New Point(panjang*15,18)

15 dan 18 itu hanya lebar dan panjang yg diinginkan aja..

Enqueue

isi.Text = isi.Text + textBox2.Text

ini artinya kita menyanbungkan textbox isi dengan textbox2, sehinnga nomor yang telah dimasukan sebelumnya bisa digabungkan dengan nomor yang baru dimasukan.

Dequeue

 isi.Text = Microsoft.VisualBasic.Right(isi.Text, Len(isi.Text) - 2)

artinya kita mengeluarkan angka dari arah kanan karena -2 itu

Head

head = Microsoft.VisualBasic.Left(chr, 1)

artinya angka yang ada pada bagian paling kiri akan menjadi Head.

Tail

Tail = Microsoft.VisualBasic.Right(chr, 1)

angka pada bagian paling kanan akan menjadi Tail

berikut ini contoh Queue :

Struktur Data STACK

STACK

stack menggunakan system LIFO (last In First Out)

contoh stack

misalnya kita menumpuk buku setingi tingginya.. dan ingin mengambil buku yang ada pada bagian bawah.. tentu saja tidak kita tarik yang di bawah secara langsung, karena jika dilakukan itu maka semua buku akan tumbang dan jadi berantakan. Sehingga kita harus mengeluarkan dulu yang paling atas sampai ke paling bawah.

perintah yang ada pada Stack

Create, Push, Pop , Head , Tail

Create

isi.Size = New Point(kolom, lebar)         

kolom dan lebar diisi sesuai dengan keinginan kita

Push

isi.Text = isi.Text + textBox2.Text

menyisipkan atau memasukan data ke dalam stack

Pop

isi.Text = Microsoft.VisualBasic.Left(isi.Text, Len(isi.Text) - 1)

nah kalo yang ini angka akan dikurangi dari bagian kiri karena kita menggunakan Left pada query itu dan stack sendiri juga di pop dari bagian kiri ..

Head

head = Microsoft.VisualBasic.Left(chr, 1)

artinya angka yang ada pada bagian paling kiri akan menjadi Head.

Tail

Tail = Microsoft.VisualBasic.Right(chr, 1)

angka pada bagian paling kanan akan menjadi Tail

Contoh pada Stack :

Struktur Data Tree

Tree Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

• Prodecessor : node yang berada diatas node tertentu.

• Successor : node yang berada di bawah node tertentu.

• Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

• Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

• Parent : predecssor satu level di atas suatu node.

• Child : successor satu level di bawah suatu node.

• Sibling : node-node yang memiliki parent yang sama dengan suatu node.

• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

• Size : banyaknya node dalam suatu tree.

• Height : banyaknya tingkatan/level dalam suatu tree.

• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

• Leaf : node-node dalam tree yang tak memiliki seccessor.

• Degree : banyaknya child yang dimiliki suatu node.

  Beberapa jenis Tree yang memiliki sifat khusus :

1) Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.


 
Jenis-jenis Binary Tree :

a) Full Binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

 b) Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child. 

c) Skewed Binary Tree

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Implementasi Binary TreeBinary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :Type Tree = ^node;Node = recordIsi : TipeData;Left,Right : Tree;end;
Contoh ilustrasi Tree yang disusun dengan double linked list :

 (Ket: LC=Left Child; RC=Right Child)

Operasi-operasi pada Binary Tree :

v Create : Membentuk binary tree baru yang masih kosong.

v Clear : Mengosongkan binary tree yang sudah ada.

v Empty : Function untuk memeriksa apakah binary tree masih kosong.

v Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.
Langkah-Langkahnya Traverse :Ø PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

Ø InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
Ø PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

Untuk lebih jelasnya perhatikan contoh operasi-operasi pada Binary Tree berikut ini :

  2) Binary search 

Tree adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.

 Contoh binary search tree umum :

Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete. 

1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).

2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.


(Keadaan awal merupakan lanjutan gambar sebelumnya)

Pada operasi di samping, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.

Shell sort (Ascending)

Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan.

Proses pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :

Pertama-tama adalah menentukan jarak mula-mula dari data yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 2.

Demikian seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j + N / 2). Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N / 4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikianlah seterusnya hingga seluruh data dibandingkan sehingga semua data ke-j lebih kecil daripada data ke-(j + N / 4).

Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N / 8. Demikian seterusnya sampai jarak yang digunakan adalah 1.

Algoritma metode Shell dapat dituliskan sebagai berikut :

»       Jarak = N

»       Selama (Jarak > 1) kerjakan baris 3 sampai dengan 9

»       Jarak = Jarak / 2. Sudah = false

»       Kerjakan baris 4 sampai dengan 8 selama Sudah = false

»       Sudah = true

»        j = 0

»       Selama (j < N – Jarak) kerjakan baris 8 dan 9

»       Jika (Data[j] > Data[j + Jarak] maka tukar Data[j],
Data[j + Jarak].
Sudah = true

»       j = j + 1

Di bawah ini merupakan prosedur yang menggunakan metode Shell:

void ShellSort(int N)
{
int Jarak, i, j;
bool Sudah;
Jarak = N;
while(Lompat > 1)
{
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah)
{
Sudah = true;
for(j=0; j Data[i])
{
Tukar(&Data[j], &Data[i]);
Sudah = false;
} } } } }

Merge sort (Ascending)

Merge sort adalah metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut : mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut. Misalnya kumpulan data pertama (T1) adalah sebagai berikut :

3 11 12 23 31

Sedangkan kumpulan data kedua (T2) adalah sebagai berikut :

9 15 17 20 35

Proses penggabungan ini dapat dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3 akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari 11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya sehingga didapat hasil sebagai berikut :

3 9 11 12 15 17 20 23 31 35

Exchange sort (Ascending)

Exchange sort adalah perbandingan suatu pivot dengan elemen yang lainnya, dan melakukan pertukaran jika perlu. Letak pivot terurut dari awal sampai akhir.

Contoh :

Quick sort (Ascending)

Quick sort adalah membandingkan suatu elemen (pivot) dengan elemen yang lain dan menyusunnya sehingga elemen yang lebih kecil dari pivot berada di sisi kiri sedangkan yang lebih besar di sisi kanan. Suatu elemen tersebut bisa kita pilih secara acak maupun sesuka hati.

Contoh :

Insertion sort (Ascending)

Insertion sort adalah pengurutan yang dilakukan dengan membandingkan data dalam pemulaian urutan kedua dibanding data pertama, kemudian akan dimulai lagi dari data ketiga membanding data kedua sampai selanjutnya.  Data yang dibandingkan adalah data yang terkecil. Apabila terdapat urutan nilai yang kecil maka akan ditempatkan ke tempat yang seharusnya. Hingga data akan terurut secara teratur dari yang terkecil hingga ke yang terbesar.

Contoh : 

Selection sort (Ascending)

Pengurutan dilakukan dengan memilih elemen terkecil dan menempatkan pada posisinya, kemudian mencari elemen terkecil berikutnya dan menempatkan pada tempatnya dan seterusnya.

Proses pengurutan dengan menggunakan metode selection sort secara terurut naik adalah :

»       Mencari data terkecil dari data pertama sampai data terakhir, kemudian di tukar posisinya dengan data pertama.

»       Mencari data terkecil dari data kedua sampai data terakhir, kemudian di tukar dengan posisinya dengan data kedua.

»       Mencari data terkecil dari data ketiga sampai data terakhir, kemudian di tukar posisinya dengan data ketiga

Bubble sort

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan.

Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar (untuk pengurutan ascending).

Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar (untuk pengurutan descending). Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses.

Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Contoh pengurutan data yang dilakukan dengan metode Bubble Sort sebagai berikut:

Proses 1:

22 10 15 3 8 2

22 10 15 3 2 8

22 10 15 2 3 8

22 10 2 15 3 8

22 2 10 15 3 8

2 22 10 15 3 8

Pengecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya, jika data di depannya lebih besa rmaka akan ditukar.

Proses 2:

2 22 10 15 3 8

2 22 10 15 3 8

2 22 10 3 15 8

2 22 3 10 15 8

2 3 22 10 15 8

Pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil. 

Proses 3:

2 3 22 10 15 8

2 3 22 10 8 15

2 3 22 8 10 15

2 3 8 22 10 15

Proses 4:

2 3 8 22 10 15

2 3 8 22 10 15

2 3 8 10 22 15

Proses 5:

2 3 8 10 22 15

2 3 8 10 15 22

Pengurutan berhenti.

Set Himpunan

Operasi Gabungan (Union), adalah operasi yang menggabungkan dua set menjadi satu, dan tidak terjadi duplikat.

Operasi Irisan (Intersection), adalah operasi yang membentuk set dengan keanggotaan dari dua set yang memiliki anggota yang sama.

Operasi Selisih (Difference), adalah operasi pada dua set, apabila elemen set pertama ada pada set keduamaka elemen pertama akan dihapus. Sehingga menghasilkan set pertama setelah penghapusan 

Yang Difference (A,B) kita cumen tinggal cari angka yang ada di A dan tidak ada di B dan sebaliknya

 (B,A).

matriks

Hai-Hai..

salam kenal ini baru pertama kali gw buat blog jd agak begok-begok... (●⌒∇⌒●)

Ada yang tau matriks itu apa gak?

hehe

matriks adalah kumpulan bilangan, simbol, atau eksperi, berbentuk persegi panjang yang di susun menurut baris dan kolom. bilangan2 yang terdapat di suatu matriks disebut dengan elemen atau anggito matriks.

<<<<< Matriks 2 x 2 (ngerti kan??? Baris 2 Kolom 2

ke contoh aja agar lebih ngerti..

( Ipad neh...)

Dari Ipad di atas kita bisa lihat 2 Matriks 2x2 ya.. yang satu anggotanya ad 1 , 2 , 3, 4 yang satunya lagi 5, 6, 7, 8

dari perkalian matriks  2 x 2  X  2 x 2 ...

kelihatan angka yang di warnain merah?? itu kolom dari matriks yang pertama , dan yang angka 2 terakhir adalah baris dari Matriks yang kedua (Baca : Cara baca bentuk Matriks Baris x Kolom)

itu kolom dan baris itu kan sama" angka 2 kan??? itu kalo sama dihapus aja.. dan digabung jadi satu..

sehingga jadi  2 x 2  kan??? Artinya, perkalian Matriks 2 x2 dan Matriks 2 x 2 akan menghasilkan Matriks 

2 x 2..

Nah sekarang berapa nilai kolom hasilnya??

Kita cari dulu kolom yang Atas Kiri << Inget ya ini Atas Kiri, jadi yang perlu kita kalikan adalah baris yang Atas dan kolom yang Kiri. kemudian dijumlahkan..

Dan hasilnya sudah bisa dihitung kan??

Itu uda dapet 1 ya.. sekarang untuk yang di Atas Kanan <<< Baca Atas Kanan, jadi yang perlu kita kalikan adalah baris yang Atas dan kolom Kanan.

dan hasilnya.

Gimana??? Sekarang tinggal cari yang masi kotak biru..

Semoga berguna bagi yang perlukan dan yang baca..

hoho |◔◡◉|

see you...