laporan praktikum struktur data dan algoritma

LAPORAN PRAKTIKUM

STRUKTUR DATA DAN ALGORITMA

BINARY HEAP

DISUSUN OLEH:

FEMBI REKRISNA GRANDEA PUTRA

M0513019

ASISTEN DOSEN:

1. DIAN SUPRABA (M0512012)

2. DWI PUTRI PERTIWI (M0512015)

3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)

4. RIZAL KUSUMAJATI NUGROHO (M0512050)

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

KAMIS, 25 SEPTEMBER 2014

SOAL

1. Print Screen

2. Penjelasan Program

public class BinaryHeap Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu

objek.

{} Pembuka dan penutup suatu class/method.

private int size; Pendeklarasian variabel size dengan tipe data integer.

public BinaryHeap() Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu

objek.

public BinaryHeap (Comparable[] array) Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu

objek dengan menambahkan array untuk pemilihan pada menu saat

program dijalankan.

public boolean isEmpty() Keadaan saat heap kosong.

public boolean isFull() Keadaan saat heap penuh.

public void buildHeap() Pembuatan heap baru.

for(int x = size/2; x > 0; x--) { perculateDown(x); }

Untuk x=size/2,maka x>0 dan nilai x dikurangi satu.

private void perculateDown(int x) {Comparable temp = heap[x];int child;

Pembuatan anak/cabang pada heap.

for(; 2*x

int arr[] = new int[500]; Pendeklarasian array dengan tipe data integer serta penetapan batas

karakter input sebanyak 500.

int swap, p, q, r; Pendeklarasian variabel swap,p,q,r dengan tipe data integer.

for( p = 0; p < size; p++) Untuk p=0,p

case 1: {System.out.println("\n");System.out.println("--

Insert--");System.out.print("Masukkan Element =

");jalan.insert(input.nextInt());System.out.printl

n("Elemen Berhasil Dimasukkan");break;

Pada menu pertama program akan menampilkan pilihan menu insert,yaitu

menu yang berfungsi untuk memasukkan angka yang akan diurutkan

dengan menggunakan algoritma binary heap.

case 2: { System.out.println("\n");System.out.println("--

Delete-Min --"); jalan.deleteMin();

System.out.println("Elemen terkecil Berhasil

dihapus"); break;

Pada menu kedua program akan menampilkan pilihan menu Delete-

Min,yang berfungsi untuk menghapus input yang dilakukan pengguna

sebelumnya.

case 3: { System.out.println("\n"); System.out.println("--Heap Sort--");

jalan.heapSort(); System.out.println("\n"); break;

Pada menu ketiga program akan menampilkan pilihan menu Heap Sort

yang berfungsi untuk mengurutkan input yang dimasukkan oleh pengguna

yang sebelumnya telah diproses dengan menggunakan algoritma binary

heap.

case 4: { System.out.println("\n");System.out.println("--

Heap--"); jalan.printHeap(); break;

Pada menu keempat program akan menampilkan menu Print Heap yang

berfungsi untuk mencetak heap yang telah diproses oleh program dengan

mengunakan algoritma binary heap.

case 5: {System.out.println("\n");System.out.println("Stat

us Empty = " + jalan.isEmpty());break;

Menu ini digunakan untuk menghapus semua input yang dilakukan oleh

pengguna.

case 6: { System.err.println("Program Telah Berhenti"); System.exit(0);

Menu ini digunakan untuk keluar dari program.

Program binary heap ini digunakan untuk mengolah input data berupa

angka yang diolah menjadi heap dengan menggunakan algoritma binary heap.

Program ini selain memiliki kemampuan mengolah angka menjadi heap juga dapat

melakukan sorting binary heap.

Mula-mula dibentuk kelas BinaryHeap sebagai awal dari pembuatan

program.Lalu untuk batas karakter inputnya dibuat melalui source code private

static final int CAPACITY = 500;.

Pembuatan heap baru dilakukan oleh program melalui

public BinaryHeap() {

size = 0;

heap = new Comparable [CAPACITY];

}

Untuk membandingkan antara input angka yang satu dengan yang

lain,program ini menggunakan

public BinaryHeap (Comparable[] array) {

size = array.length;

heap = new Comparable[array.length+1];

}

Untuk menyatakan keadaan bahwa heap dalam keadaan kosong maka

program menggunakan

public boolean isEmpty() {

return size == 0;

}

Untuk menyatakan keadaan bahwa heap dalam keadaan penuh maka

program menggunakan

public boolean isFull() {

return size == heap.length;

}

Untuk membangun heap baru maka program menggunakan

public void buildHeap() {

for(int x = size/2; x > 0; x--) {

perculateDown(x);

}

}

Untuk menyatakan fungsi deletemin maka program ini menggunakan

public Comparable deleteMin() {

if(size == 0);

Comparable min = heap[1];

heap[1] = heap[size--];

perculateDown(1);

return min;

}

Untuk melakukan sorting pada heap dilakukan melalui

public void heapSort() {

int arr[] = new int[500];

int swap, p, q, r;

for( p = 0; p < size; p++) {

arr[p+1] = (int) heap[p+1];

}

for (q = 0; q < size-1; q++) {

for (r = 0; r < size-q-1; r++) {

if(arr[r+1] > arr[r+2]) {

swap = arr[r+1];

arr[r+1] = arr[r+2];

arr[r+2] = swap;

}

}

}

for(p = 0; p < size; p++) {

heap[p+1] = arr[p+1];

}

for(int s = 0; s < size; s++) {

System.out.print(heap[s+1]+ " ");

}

}

Untuk mencetak heap yang telah diproses menggunakan

public void printHeap() {

System.out.println("\nHeap : ");

for (int i = 0; i < size; i++)

System.out.println(heap[i+1]+ " ");

System.out.println();

}

Setelah semua source code diproses, maka hasil run program adalah

Mula-mula dilakukan pemilihan menu no.1 (insert). Angka yang

dimasukkan adalah 20, 37, 25, 63, 61, 92, 17, 21, 12, 55, 47, 45, 64, 83, 73. Setelah

di-input-kan semua data-datanya, maka yang harus dilakukan setelahnya adalah

melakukan heap sort. Untuk melakukan heap sort, dilakukan pemilihan menu no.3.

Setelah dilakukan pemilihan menu heap sort, maka program akan menampilkan

Output yang dikeluarkan adalah 12, 17, 20, 21, 25, 37, 45, 47, 55, 61, 63,

64, 73, 83, 92. Setelah menggunakan program, jika ingin keluar dari program,

maka yang harus dilakukan adalah memilih menu no.6 (exit). Setelah dipilih menu

exit, maka program akan berhenti bekerja.

LAPORAN PRAKTIKUM

STRUKTUR DATA DAN ALGORITMA

SPLAY TREE

DISUSUN OLEH:

FEMBI REKRISNA GRANDEA PUTRA

M0513019

ASISTEN DOSEN:

1. DIAN SUPRABA (M0512012)

2. DWI PUTRI PERTIWI (M0512015)

3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)

4. RIZAL KUSUMAJATI NUGROHO (M0512050)

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

KAMIS, 9 OKTOBER 2014

SOAL

1. Print Screen

2. Analisis

Program ini berguna untuk mengimplementasikan splay tree pada Java.

Program ini terdiri dari beberapa kelas, yaitu SplayNode, SplayTree, dan

Test_SplayTree. Di kelas SplayNode, terdapat konstruktor SplayNode dengan

objek left, right, dan parent dan variabel elemen bertipe integer.

Di kelas SplayTree, terdapat metode-metode yang dirujuk oleh menu pada

program ini. Metode SplayTree mengubah nilai variabel root menjadi null. Metode

isEmpty bertipe boolean, akan menentukan apakah splay tree berisi data atau null.

Metode clear berguna untuk menghapus seluruh data. Metode insert berguna untuk

menyisipkan data. Metode remove bertipe boolean berguna untuk mengecek

ketersediaan data yang akan dihapus. Metode remove bertipe void berguna untuk

menghapus data. Metode countNodes berguna untuk menghitung jumlah node

yang ada. Metode search berguna untuk mencari ketersediaan node di dalam splay

tree dengan mengembalikan kepada metode findNode. Metode findNode berguna

untuk menemukan node di dalam splay tree. Metode inorder berguna untuk

menampilkan urutan node dalam inorder. Metode preorder berguna untuk

menampilkan urutan node dalam preorder. Metode postorder berguna untuk

menampilkan urutan node dalam postorder.

Di dalam kelas Test_SplayTree berisi perintah untuk memindai masukan

dari pengguna dan mencetak tulisan ke layar. Menu 1 untuk memasukkan data dan

memanggil metode insert. Menu 2 untuk menghapus data, dengan memanggil

metode isEmpty terlebih dahulu, jika node masih null, maka menampilkan tulisan

Tree Kosong. Jika data sudah terisi, maka pengguna dapat memasukkan data

yang akan dihapus, kemudian program memanggil metode search untuk

mencarinya dan memanggil metode remove untuk menghapusnya. Jika data

berhasil dihapus oleh metode remove, maka muncul pesan bahwa data telah

dihapus. Jika metode search tid