laporan praktikum struktur data dan algoritma

Click here to load reader

Post on 09-Jan-2017

52 views

Category:

Education

2 download

Embed Size (px)

TRANSCRIPT

  • 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