laporan praktikum struktur data dan algoritma informatika uns 2014
Post on 09-Jan-2017
76 Views
Preview:
TRANSCRIPT
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
RUNNING TIME
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. MUHAMMAD SAFRI JULIARDI (M0512038)2. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 18 MARET 2014
SOURCE CODE
Algoritma 1
package algoritma1;
import java.util.Random;
public class Algoritma1 {
public static int maxSubSum1(int[] a) {
long startTime = System.currentTimeMillis();
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int thisSum = 0;
for (int k = i; k <= j; k++) {
thisSum += a[ k];
}
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
long endTime = System.currentTimeMillis();
System.out.println("\nWaktu Eksekusi = " +(endTime - startTime) + " ms");
return maxSum;
}
public static void main(String[] args) {
int a[] = new int[10000];
Random rd = new Random();
int maxSum;
for (int j = 0; j < 500; j++) {
int angka = rd.nextInt(5) - rd.nextInt(5);
a[j] = angka;
System.out.println(angka + " ");
}
maxSum = maxSubSum1(a);
System.out.println("Max sum is " + maxSum);
}
}
Algoritma 2
package algoritma.pkg2;
import java.util.Random;
public class Algoritma2 {
public static int maxSubSum2(int[] a) {
long startTime = System.currentTimeMillis();
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
int thisSum = 0;
for (int j = i; j < a.length; j++) {
thisSum += a[ j];
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
long endTime = System.currentTimeMillis();
System.out.println("\nWaktu Eksekusi = " +
(endTime - startTime) + " ms");
return maxSum;
}
public static void main(String[] args) {
int a[] = new int[500000];
Random rd = new Random();
int maxSum;
for (int j = 0; j < 500; j++) {
int angka = rd.nextInt(5) - rd.nextInt(5);
a[j] = angka;
System.out.println(angka + " ");
}
maxSum = maxSubSum2(a);
System.out.println("Max sum is " + maxSum);
}
}
Algoritma 3
package algoritma3;
import java.util.Random;
public class Algoritma3 {
/**
* Recursive maximum contiguous subsequence sum
algorithm. Finds maximum sum
* in subarray spanning a[left..right]. Does not attempt
to maintain actual
* best sequence.
*/
private static int maxSumRec(int[] a, int left, int
right) {
long startTime = System.currentTimeMillis();
if (left == right) // Base case
{
if (a[ left] > 0) {
return a[ left];
} else {
return 0;
}
}
int center = (left + right) / 2;
int maxLeftSum = maxSumRec(a, left, center);
int maxRightSum = maxSumRec(a, center + 1, right);
int maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--) {
leftBorderSum += a[ i];
if (leftBorderSum > maxLeftBorderSum) {
maxLeftBorderSum = leftBorderSum;
}
}
int maxRightBorderSum = 0, rightBorderSum = 0;
for (int i = center + 1; i <= right; i++) {
rightBorderSum += a[ i];
if (rightBorderSum > maxRightBorderSum) {
maxRightBorderSum = rightBorderSum;
}
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
public static int maxSubSum3(int[] a) {
return maxSumRec(a, 0, a.length - 1);
}
/**
* Return maximum of three integers.
*/
private static int max3(int a, int b, int c) {
return a > b ? a > c ? a : c : b > c ? b : c;
}
public static void main(String[] args) {
int a[] = new int[10000000];
Random rd = new Random();
int maxSum;
for (int j = 0; j < 50; j++) {
int angka = rd.nextInt(5) - rd.nextInt(5);
a[j] = angka;
System.out.println(angka + " ");
}
}
}
Algoritma 4
package algoritma4;
import java.util.Random;
public class Algoritma4 {
public static int maxSubSum4(int[] a) {
long startTime = System.currentTimeMillis();
int maxSum = 0, thisSum = 0;
for (int j = 0; j < a.length; j++) {
thisSum += a[ j];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
long endTime = System.currentTimeMillis();
System.out.println("\nWaktu Eksekusi = " + (endTime
- startTime) + " ms");
return maxSum;
}
public static void main(String[] args) {
int a[] = new int[1000000];
Random rd = new Random();
int maxSum;
for (int j = 0; j < 500; j++) {
int angka = rd.nextInt(5) - rd.nextInt(5);
a[j] = angka;
System.out.println(angka + " ");
}
maxSum = maxSubSum4(a);
System.out.println("Max sum is " + maxSum);
}
}
DASAR TEORI
Di dalam menganalisa suatu algoritma, terdapat beberapa faktor yang selalu menjadi
pertimbangan di dalam menentukan baik tidaknya suatu algoritma, yaitu:
Efisiensi suatu algoritma di dalam penggunaan sumber daya suatu komputer; dalam hal
ini menyangkut banyaknya memori (space), dan lamanya waktu komputasi yang
diperlukan (running time).
Correctness dari algoritmanya sendiri. Yakni apakah algoritma tersebut selalu
menghasilkan hasil yang benar untuk semua input yang mungkin.
Kompleksitas dari algoritma. Dalam hal ini, baik faktor efisiensi maupun faktor
kesulitan dalam mengimplementasi algoritma tersebut menjadi pertimbangan yang
utama.
Running time dan penggunaan memori:
Analisa terhadap efisiensi suatu algoritma lebih ditekankan pada banyaknya sumber daya
yang diperlukan dan dinyatakan sebagai fungsi dari besarnya input algoritma tersebut.
Sedangkan pada analisa terhadap kompleksitas lebih pada identifikasi terhadap operasi
dasar dan berapa kali operasi dasar tersebut perlu dilakukan dalam suatu algoritma.
Dalam hal ini yang perlu diingat adalah bahwa analisa kompleksitas tidak bergantung
pada jenis komputer yang digunakan.
Contoh: efisiensi dapat ditentukan oleh banyaknya memori (space) yang diperlukan
dan/atau lamanya waktu komputasi (running time) yang dibutuhkan sesuai dengan
besarnya input algoritma tersebut.
Space: yang diperlukan oleh suatu algoritma, ditentukan dari jumlah dan ukuran variabel
dan struktur data yang digunakan:
Running Time: ditentukan oleh banyaknya operasi dasar yang dilakukan selama proses.
Space-Time Trade-off: dalam banyak hal, space dan time yang diperlukan suatu algoritma
selalu bersifat tolak belakang: “makin berkurang space, maka makin bertambah waktu
yang diperlukan, dan sebaliknya”. Contoh: POWER2( ) meskipun melakukan jumlah
operasi perkalian yang lebih sedikit, tetapi bersifat rekursif yang memerlukan space
besar.
Operasi-operasi dasar pada suatu algoritma adalah operasi yang waktu prosesnya dibatasi
oleh (memiliki batas atas) suatu nilai konstan dan hanya bergantung pada implementasi
yang digunakan.
Pada analisa algoritma, lebih diperhatikan pada banyaknya operasi dasar yang dilakukan
dari pada waktu sebenarnya yang diperlukan oleh masing-masing operasi dasar tersebut;
dengan perkataan lain setiap operasi dasar dapat dilihat sebagai satu satuan biaya (unit
cost).
ANALISA
Berikut disajikan tabel data perbandingan antara masukan jumlah nilai (N) dengan waktu
yang dibutuhkan (t).
Dari tabel Algoritma 1 dapat diketahui bahwa pada jumlah masukan 50-100 tidak
membutuhkan waktu (0s). Ketika masukan mulai bertambah jadi 500, barulah program
membutuhkan waktu untuk memprosesnya. Setelah dimasukkan jumlah masukan sebanyak
5.000, program mulai tidak dapat memproses. Ini menunjukkan bahwa program hanya mampu
memproses hingga 1.000 masukan saja.
-50
0
50
100
150
200
250
300
350
400
450
0 1000 2000 3000 4000 5000 6000
Wak
tu (t
)
Jumlah Data (N)
Algoritma 1
Dari tabel Algoritma 2 dapat diketahui bahwa pada awalnya, program tidak
membutuhkan waktu untuk memproses jumlah masukan 50 dan 100. Setelah jumlah masukan
menjadi 500, program membutuhkan waktu untuk memproses jumlah masukan. Proses ini
dapat berjalan sampai 5.000 masukan. Sedikit lebih baik dari Algoritma 1 yang hanya dapat
menampung 1.000 jumlah masukan saja.
-10
0
10
20
30
40
50
60
70
0 1000 2000 3000 4000 5000 6000
Wak
tu (t
)
Jumlah Data (N)
Algoritma 2
Pada tabel Algoritma 3 dapat dilihat bahwa pemrosesan data berjalan dengan sangat
cepat, tidak membutuhkan waktu sama sekali. Dalam sekejap semua data langsung diproses.
Mulai dari jumlah masukan 50 hingga 1.000.000, semuanya tidak membutuhkan waktu untuk
memprosesnya (0s).
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 200000 400000 600000 800000 1000000 1200000
Wak
tu (t
)
Jumlah Data (N)
Algoritma 3
Pada tabel Algoritma 4 dapat dilihat bahwa program memproses data dengan cepat dan
stabil. Namun algoritma ini masih kalah cepat oleh Algoritma 3 yang memproses data dengan
sangat cepat.
-5
0
5
10
15
20
0 200000 400000 600000 800000 1000000 1200000
Wak
tu (t
)
Jumlah Data (N)
Algoritma 4
KESIMPULAN
Dari keempat algoritma di atas dapat disimpulkan bahwa:
Algoritma 1 dalam hal kecepatan pemrosesannya termasuk yang paling tidak efektif di
antara keempat algoritma yang lain, karena tidak dapat memproses data dalam jumlah
banyak dan membutuhkan waktu yang lama dalam memproses data.
Algoritma 2 dalam hal kecepatan pemrosesan dan efisiensinya juga masih tergolong
sebagai algoritma yang tidak efisien, walaupun sudah sedikit lebih baik dari Algoritma
1. Itu karena algoritma ini masih memiliki banyak kekurangan dalam hal kecepatan
pemrosesan data dan penampungan data dalam jumlah besar.
Algoritma 3 dalam hal kecepatan pemrosesan dan efisiensinya adalah yang paling baik
di antara keempat algoritma di atas.
Algoritma 4 dalam hal kecepatan pemrosesan dan efisiensinya termasuk baik dan cepat,
walaupun masih tertinggal oleh Algoritma 3.
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
REKURSI
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. MUHAMMAD SAFRI JULIARDI (M0512038)
2. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 25 MARET 2014
Rekursi adalah konsep pengulangan yang penting dalam ilmu komputer. Konsep ini dapat
digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk
diselesaikan secara iteratif dengan menggunakan loop for dan if. Pada saat tertentu konsep ini
dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada
saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah
rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa.
Rekursi mempunyai arti suatu proses yang bisa memanggil dirinya sendiri. Dalam sebuah
rekursi sebenarnya tekandung pengertian sebuah prosedur atau fungsi. Perbedaannya
adalah bahwa rekursi bisa memanggil dirinya sendiri, kalau prosedur atau fungsi harus
diipanggil melalui pemanggil prosedur atau fungsi.
Saat menulis rutinitas rekursif, sangat penting untuk diingat empat aturan dasar rekursi:
1. Base Case. Anda harus selalu memiliki base case tertentu, yang dapat diselesaikan
tanpa rekursi.
2. Making progress. Untuk kasus yang harus dipecahkan secara rekursif, panggilan
rekursif harus selalu ada progress menuju base case.
3. Design Rule. Asumsikan bahwa semua panggilan rekursif bekerja.
4. Compound Interest Rule. Jangan menduplikasi pekerjaan dengan menyelesaikan
pekerjaan yang sama dari sebuah masalah dalam panggilan rekursif terpisah.
Contoh rekursi:
Dalam matematika, bilangan Fibonacci adalah barisan yang didefinisikan secara rekursif
sebagai berikut:
𝐹𝑛 {
0, 𝑗𝑖𝑘𝑎 𝑛 = 0;1, 𝑗𝑖𝑘𝑎 𝑛 = 1;
𝐹(𝑛 − 1) + 𝐹(𝑛 − 2) 𝑗𝑖𝑘𝑎 𝑡𝑖𝑑𝑎𝑘.
Penjelasan: barisan ini berawal dari 0 dan 1, kemudian angka berikutnya didapat dengan cara menambahkan kedua bilangan yang berurutan sebelumnya. Dengan aturan ini, maka
barisan bilangan Fibonaccci yang pertama adalah:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
Barisan bilangan Fibonacci dapat dinyatakan sebagai berikut:
𝐹𝑛 =(𝑥1𝑛 − 𝑥2𝑛)
√5
dengan
𝐹𝑛 adalah bilangan Fibonacci ke-𝑛
𝑥1 dan 𝑥2 adalah penyelesaian persamaan 𝑥2 − 𝑥1 = 0
Perbandingan antara 𝐹𝑛 + 1 dengan 𝐹𝑛 hampir selalu sama untuk sebarang nilai 𝑛 dan mulai
nilai 𝑛 tertentu, perbandingan ini nilainya tetap. Perbandingan itu disebut Golden Ratio yang
nilainya mendekati 1,618.
PERCOBAAN 1
1. run:
***ALGORITMA 1 FIBONACCI***
5
1: 1
2: 0
3: 0
4: 0
5: 0
BUILD SUCCESSFUL (total time: 0 seconds)
2. Pada program ini berjalan dengan cara iteratif. Proses untuk menampilkan tiap bilangan
fibonacci pada program ini adalah dengan menggunakan looping for untuk memberikan
urutannya yang disimbolkan sebagai variabel N dan untuk mendapat nilai integer
dilakukan dengan parseInt dari suatu string, kemudian untuk mendapatkan nilai
fibonaccinya dengan cara dimasukkan ke dalam objek fib1, objek fib1 berfungsi untuk
memberikan nilai fiboanccinya. Objek fib1 akan menerima nilai masukan dari proses
loop for dan nilai tersebut disimbolkan dengan variabel num yang bertipe long. Proses
dari objek fib1 adalah dengan menggunakan statemen if-else, if yang pertama memiliki
kondisi jika ternyata nilai num yang masuk bernilai 0 maka nilai yang dikembalikan
adalah 0, kemudian jika if pertama tidak terpenuhi (else) maka dilakukan statemen if
kedua yaitu jika nilai num adalah 1 maka nilai yang dikembalikan adalah 1, kemudian
jika tidak terpenuhi lagi (else) maka akan dilakukan statemen berikut:
long x = 0;
long y = 0;
for ( long k=2; k<= Num; k++) {
y = x+y;
x = y-x;
}
return y;
Variabel x dan y bertipe long digunakan sebagai nilai tetap untuk melengkapi statemen
for setelahnya. Dalam statemen for tersebut dilakukan sebanyak num-1 kali. Dan di setiap
kali loop dilakukan operasi y=x+y kemudian x=y-x agar diperoleh bilangan fibonacci
sesuai pada nilai num yang masuk. Setelah statemen tersebut selesai maka nilai yang
dikembalikan adalah nilai y.
3. package rekursi1;
import java.util.Scanner;
public class Rekursi1 {
public static long Rek1 (long Num) {
if (Num == 0) return 0;
else if (Num == 1) return 1;
else {
long x = 0;
long y = 0;
for ( long k=2; k<= Num; k++) {
y = x+y;
x = y-x;
}
return y;
}}
public static void main (String[] args) {
System.out.println("***ALGORITMA 1 FIBONACCI***");
Scanner scn = new Scanner (System.in);
long N = scn.nextLong();
long waktu= System.nanoTime();
for (long i = 1; i<= N; i++)
System.out.println(i + ": " + Rek1(i));
long akhir = System.nanoTime()-waktu;
System.out.println("Waktu eksekusi: "+akhir+" nano
detik");
}
}
4. N=10; Waktu eksekusi: 727304 nano detik
N=30; Waktu eksekusi: 1707762 nano detik
N=50; Waktu eksekusi: 6922731 nano detik
PERCOBAAN 2
5. run:
***ALGORITMA 2 FIBONACCI***
5
1: 1
2: 1
3: 2
4: 3
5: 5
BUILD SUCCESSFUL (total time: 0 seconds)
6. Program ini menggunakan for untuk menentukan urutan dari bilangan yang akan dicari
nilai fibonaccinya dan disimbolkan sebagai N yang untuk mendapat nilai integernya
dilakukan dengan cara parseInt dari suatu string, kemudain untuk menentukan nilai
fibonaccinya dilakukan dengan cara dimasukkan ke dalam objek fib2, objek fib 2
membawa nilai yang dimasukkan ke dalam for dengan disimbolkan sebagai variabel n
bertipe integer. Proses dari fib2 adalah menggunakan statemen if-else, if yang pertama
memiliki kondisi jika n kurang dari atau sama dengan 1 maka dikembalikan nilai sama
seperti nilai n tersebut, jika if yang pertama tidak terpenuhi (else) maka akan
dikembalikan nilai dari objek fib2 dengan kondisi n-1 ditambah dengan objek fib 2
dengan kondisi n-2 atau lebih singkatnya dilakukan penjumlahan antara nilai n-1 dan n-
2 tetapi dengan melakukan pemanggilan objek lagi sehingga akan jadi kurang efektif.
7. package rekursi1;
import java.util.Scanner;
public class Rekursi1 {
public static long Rek1 (long Num) {
if (Num == 0) return 0;
else if (Num == 1) return 1;
else {
long x = 0;
long y = 0;
for ( long k=2; k<= Num; k++) {
y = x+y;
x = y-x;
}
return y;
}}
public static void main (String[] args) {
System.out.println("***ALGORITMA 1 FIBONACCI***");
Scanner scn = new Scanner (System.in);
long N = scn.nextLong();
long waktu= System.nanoTime();
for (long i = 1; i<= N; i++)
System.out.println(i + ": " + Rek1(i));
long akhir = System.nanoTime()-waktu;
System.out.println("Waktu eksekusi: "+akhir+" nano
detik");
}
}
8. N=10; Waktu eksekusi: 732778 nano detik
N=30; Waktu eksekusi: 1826812 nano detik
N=50; Waktu eksekusi: 2814112 nano detik
PERCOBAAN 3
9. run:
***ALGORITMA 3 FIBONACCI***
5
1: 1
2: 1
3: 2
4: 3
5: 5
BUILD SUCCESSFUL (total time: 0 seconds)
10. Dalam program ini untuk menentukan urutan dari bilangan yang akan dicari nilai
fibonaccinya dilakukan dengan for yang pada tiap nilainya disimbolkan dengan variabel
N yang untuk mendapatkan nilai integer dilakukan dengan cara parseInt dari suatu string,
kemudian nilai tersebut akan dimasukkan ke dalam objek fib3 dengan disimbolkan
sebagai variabel n bertipe integer, setiap nilai dari for tersebut berfungsi untuk memberi
urutan nilai yang dicari. Proses di dalam objek fib3 adalah terdapat sebuah if dan sebuah
for, if memiliki kondisi jika besar n kurang dari atau sama dengan 1 maka akan
dikembalikan nilai sama dengan n. dan sebelum dilakukan statemen for akan
didefinisikan variabel fib1, fib2, dan result bertipe long yang fungsinya untuk
mendapatkan nilai fibonacci, variabel fib1 untuk menahan nilai 2 angka fibonacci
sebelum nilai yang dicari fibonaccinya, dan fib2 untuk menyimpan nilai dari 1 angka
sebelum nilai yang dicari fibonacinya, sedangkan result akan memiliki nilai fibonaccinya
yaitu jumlah dari fib1 dan fib2, dari penjelasan tersebut jika dilakukan proses for dengan
statemen di dalamnya adalah seperti yang telah dijelaskan mengenai fib1, fib2, dan result,
maka akan diperoleh nilai fibonacci yang disimpan dalam variabel result. Sehingga nilai
yang dikembalikan adalah nilai dari variabel result.
11. package fibonacci3;
import java.util.Scanner;
public class Fibonacci3 {
public static long Fibonacci3(int n) {
if (n<=1) return n;
long Fibonacci1 = 0;
long Fibonacci2 = 1;
long result = 0;
for (int ii = 2; ii <= n; ii++){
result = Fibonacci2 + Fibonacci1;
Fibonacci1 = Fibonacci2;
Fibonacci2 = result; }
return result;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
System.out.println("***ALGORITMA 3 FIBONACCI***");
Scanner scn = new Scanner (System.in);
long N = scn.nextLong();
long waktu = System.nanoTime();
for (int i=1; i<=N; i++)
System.out.println(i+": " + Fibonacci3(i));
long akhir= System.nanoTime()-waktu;
System.out.println("Waktu eksekusi : " +akhir+ "nano
detik");
}
}
12. N=10; Waktu eksekusi : 696515nano detik
N=30; Waktu eksekusi : 1728288nano detik
N=50; Waktu eksekusi : 2815481nano detik
PERCOBAAN 4
13. run:
***ALGORITMA 4 FIBONACCI***
5
1: 1
2: 1
3: 2
4: 3
5: 5
BUILD SUCCESSFUL (total time: 0 seconds)
14. Pada program ini untuk menentukan urutan dari nilai yang dicari fibonaccinya dilakukan
dengan for yang disimbolkan sebagai variabel N bertipe integer yang untuk mendapatkan
nilai integernya dilakukan dengan cara parseInt dari suatu string, kemudian setiap
nilainya akan dimasukkan ke dalam objek fib4 sebagai variabel n. Di dalam objek fib4
dilakukan pengembalian nilai dari objek fiboHelp, ini berarti di dalam objek fib4 juga
memanggil fiboHelp untuk dikembalikan nilainya, objek fibohelp memiliki variabel x
dan y bertipe long dan n bertipe integer. Dari objek fib4 akan dimasukkan ke objek
fiboHelp dengan nilai x=0, y=1, dan n sesuai dari nilai yang dibawa onjek fib4. Proses
di dalam objek fiboHelp adalah dengan menggunakan statemen if-else, kondisi if yang
pertama adalah jika nilai n adalah o maka akan dikembalikan nilai x, jika if pertama tidak
terpenuhi maka akan dilakukan if yang kedua yang memiliki kondisi jika n sama dengan
1 maka akan dikembalikan nilai dari y, jika if kedua tidak terpenuhi lagi maka akan
dialkukan pemanggilan terhadap fiboHelp lagi dengan nilai yang dimasukkan adalah
variabel x menjadi bernilai variabel y, dan variabel y menjadi bernilai x+y, sedangkan
variabel n menjadi bernilai n-1. Sehingga dengan proses tersebut akan diperoleh nilai
fibonaccinya.
15. package fibonacci4;
import java.util.Scanner;
public class Fibonacci4 {
public static long Fibonacci4(int n) {
return FibonacciHelp (0,1,n);
}
public static long FibonacciHelp (long x, long y, int
n) {
if (n==0) return x;
else if (n == 1) return y;
else return FibonacciHelp (y, x+y, n-1);
}
public static void main (String[] args) {
System.out.println("***ALGORITMA 4 FIBONACCI***");
Scanner scn = new Scanner (System.in);
long N = scn.nextLong();
long waktu = System.nanoTime();
for (int i=1; i<=N; i++)
System.out.println(i+": " + Fibonacci4(i));
long akhir= System.nanoTime()-waktu;
System.out.println("Waktu eksekusi : " +akhir+
"nano detik");
}
}
16. N=10; Waktu eksekusi : 838144nano detik
N=30; Waktu eksekusi : 1882233nano detik
N=50; Waktu eksekusi : 2973531nano detik
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
LINK LIST
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. MUHAMMAD SAFRI JULIARDI (M0512038)
2. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 1 APRIL 2014
SOURCE CODE
LinkList
package linklist;
import java.util.Scanner;
public class LinkList {
public static void main(String[] args) {
System.out.println("WELCOME!");
System.out.println("Pilih menu yang ingin anda gunakan : ");
System.out.println("1. Cek kosong ");
System.out.println("2. Menambah data di awal ");
System.out.println("3. Menambah data di akhir ");
System.out.println("4. Menghapus data di awal");
System.out.println("5. Menghapus data di akhir ");
System.out.println("6. Temukan data ");
System.out.println("7. Cetak semua data ");
System.out.println("8. Hapus semua data ");
System.out.println("9. Menghitung banyaknya data");
System.out.println("10. Hapus data ");
System.out.println("11. Mengganti data");
System.out.println("12. Menambah data di indeks ke- ");
System.out.println("13. Keluar ");
Method method = new Method();
int again;
do
{
//Method method = new Method();
System.out.println("What do you want to do?");
Scanner masukan = new Scanner (System.in);
int number = masukan.nextInt();
switch (number)
{
case 1 :
{
method.isEmpty();
System.out.println("Keluar sekarang?");
} break;
case 2 :
{
Scanner inputan = new Scanner (System.in);
System.out.println("Masukkan data yang ingin anda
tambahkan!");
int masuk = inputan.nextInt();
method.addFirst(masuk);
System.out.println("Keluar sekarang?");
} break;
case 3 :
{
Scanner inputan = new Scanner (System.in);
System.out.println("Masukkan data yang ingin anda
tambahkan!");
int masuk = inputan.nextInt();
method.addLast(masuk);
System.out.println("Keluar sekarang?");
} break;
case 4 :
{
method.removeFirst();
System.out.println("Keluar sekarang?");
} break;
case 5 :
{
method.removeLast();
System.out.println("Keluar sekarang?");
} break;
case 6 :
{
Scanner inputan = new Scanner (System.in);
System.out.println("Masukkan data yang ingin anda
cari!");
int masuk = inputan.nextInt();
method.find(masuk);
System.out.println("Keluar sekarang?");
} break;
case 7 :
{
System.out.println("Your data : ");
method.printNode();
System.out.println("Keluar sekarang?");
} break;
case 8 :
{
method.clear();
System.out.println("Keluar sekarang?");
} break;
case 9 :
{
method.length();
System.out.println("Keluar sekarang?");
} break;
case 10 :
{
Scanner inputan = new Scanner (System.in);
System.out.println("Masukkan data yang ingin
dihapus : ");
int masuk = inputan.nextInt();
method.remove(masuk);
System.out.println("Keluar sekarang?");
} break;
case 11 :
{
System.out.println("Masukkan data apa yang ingin
anda hapus?");
Scanner inputan = new Scanner (System.in);
int masuk = inputan.nextInt();
System.out.println("Masukkan data baru : ");
Scanner inputan2 = new Scanner (System.in);
int masuk2 = inputan2.nextInt();
method.replace(masuk, masuk2);
System.out.println("Keluar sekarang?");
} break;
case 12 :
{
System.out.println("Masukkan data apa yang ingin
anda tambahkan!");
Scanner inputan = new Scanner (System.in);
int masuk = inputan.nextInt();
System.out.println("Data tadi ingin dimasukkan ke
indeks ke berapa? ");
Node n=new Node();
Scanner inputan2 = new Scanner (System.in);
int masuk2 = inputan2.nextInt();
n.data=masuk;
method.insert (n, masuk2);
System.out.println("Keluar sekarang?");
} break;
case 13 :
{
System.out.println("Anda yakin ingin keluar?");
}
}
System.out.println("(1 = Yes, 0 = No)");
Scanner lagi = new Scanner (System.in);
again = lagi.nextInt();
} while (again==0);
System.out.println("Anda telah keluar!");
System.out.println("Terima kasih.");
}
}
Method package linklist;
public class Method implements NewInterface {
Node head;
Node tail;
@Override
public boolean isEmpty()
{
return (head==null);
}
@Override
public void addFirst(int input) {
Node baru = new Node (input);
if(isEmpty())
{
head = baru;
tail = baru;
}
else
{
baru.next = (Node) head;
head = baru;
}
System.out.println("Data : " + baru.data + " ditambahkan di
awal!");
}
@Override
public void addLast(int input) {
Node baru = new Node (input);
if(isEmpty())
{
head = baru;
tail = baru;
}
else
{
tail.next = baru;
tail = baru;
}
System.out.println("Data : " + baru.data + " ditambahkan di
akhir!");
}
@Override
public void removeFirst() {
Node temp = (Node) head;
if(!isEmpty())
{
if(head == tail)
{
head = tail = null;
}
else
{
head = temp.next;
temp.next = null;
//temp = null;
}
System.out.println("Data di awal sudah dihapus!");
}
else
System.out.println("Data kosong!");
}
@Override
public void removeLast() {
Node temp = (Node) head;
if(!isEmpty())
{
if (tail == head)
{
head = tail = null;
}
else
{
while (temp.next != tail)
{
temp = temp.next;
}
temp.next = null;
tail = temp;
//temp = null;
}
System.out.println("Data di akhir berhasil dihapus!");
}
else
System.out.println("Data kosong!");
}
@Override
public void find(int data) {
int i = 0;
boolean found = false;
Node temp = (Node) head;
while (temp != null)
{
if(temp.data == data)
{
found = true;
break;
}i++; temp = temp.next;
}
if (found)
{
System.out.println(data+" ditemukan di indeks ke-"
+ i);
}
else
System.out.println("Data tidak ditemukan!");
}
@Override
public void printNode() {
Node temp;
temp = (Node) head;
while (temp != null)
{
System.out.println("Data : " + temp.data);
temp = temp.next;
}
System.out.println("END");
}
@Override
public void clear () {
head = null;
System.out.println("SUDAH KOSONG!");
}
@Override
public void length () {
int i = 0;
Node temp;
temp = (Node) head;
while (temp!= null)
{
i++;
temp = temp.next;
}
System.out.println("Jumlah datanya : " + i);
}
@Override
public void remove (int data)
{
Node hm = (Node) head;
Node temp;
temp = (Node) head;
//boolean found = false;
while( temp.data!= data & temp != null ) {
hm = temp;
temp = temp.next;
}
if( temp.data == data ) {
hm.next = temp.next ;
System.out.println( "Data berhasil dihapus\n" );
}
else
System.out.println("Data tidak ditemukan!");
}
@Override
public void replace (int addData,int newData)
{
boolean found = false;
Node temp = (Node) head;
while (temp != null)
{
if(temp.data == addData)
{
found = true;
temp.data = newData;
break;
} temp = temp.next;
//System.out.println(head.next.data);
}
if(found)
System.out.println("Data sudah diganti!");
else
System.out.println("Data tidak ditemukan! Operasi tidak
dapat dilanjutkan!");
}
@Override
public void insert (Node data,int indeks){
Node temp = (Node) head;
//Node hm = (Node) head;
//boolean found=false;
int i=0;
int indek = indeks-1;
if (indeks == 0){
data.next = head;
head = data;
}
else{
do{
if (i == indek){
//found=true;
data.next=temp.next;
temp.next=data;
System.out.println("Data berhasil dimasukkan!");
break;
}
else{
i++;
temp = temp.next;
}
}
while (temp != null);
}
}
}
NewInterface package linklist;
public interface NewInterface {
boolean isEmpty();
void addFirst (int input);
void addLast (int input);
void removeFirst ();
void removeLast ();
void find (int data);
void printNode ();
void clear ();
void length ();
void remove (int data);
void replace (int addData,int newData);
void insert (Node data, int indeks);
}
Node
package linklist;
class Node {
public Node next;
public int num;
int data;
public Node previous;
public Node(int input) {
num = input;
data = input;
next = null;
}
Node() {
int data;
Node next;
}
}
JALANNYA PROGRAM
Menambah data di awal run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
Menambah data di akhir run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
3
Masukkan data yang ingin anda tambahkan!
3
Data : 3 ditambahkan di akhir!
Keluar sekarang?
(1 = Yes, 0 = No)
Cetak semua data run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
3
Masukkan data yang ingin anda tambahkan!
3
Data : 3 ditambahkan di akhir!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
7
Your data :
Data : 2
Data : 3
END
Keluar sekarang?
(1 = Yes, 0 = No)
Menghapus data di awal run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
3
Masukkan data yang ingin anda tambahkan!
3
Data : 3 ditambahkan di akhir!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
7
Your data :
Data : 2
Data : 3
END
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
4
Data di awal sudah dihapus!
Keluar sekarang?
(1 = Yes, 0 = No)
Menghapus data di akhir run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
3
Masukkan data yang ingin anda tambahkan!
3
Data : 3 ditambahkan di akhir!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
7
Your data :
Data : 2
Data : 3
END
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
4
Data di awal sudah dihapus!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
5
Data di akhir berhasil dihapus!
Keluar sekarang?
(1 = Yes, 0 = No)
Temukan data run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
6
Masukkan data yang ingin anda cari!
2
2 ditemukan di indeks ke-0
Keluar sekarang?
(1 = Yes, 0 = No)
Hapus semua data run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
6
Masukkan data yang ingin anda cari!
2
2 ditemukan di indeks ke-0
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
8
SUDAH KOSONG!
Keluar sekarang?
(1 = Yes, 0 = No)
Menghitung banyaknya data run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
6
Masukkan data yang ingin anda cari!
2
2 ditemukan di indeks ke-0
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
8
SUDAH KOSONG!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
9
Jumlah datanya : 0
Keluar sekarang?
(1 = Yes, 0 = No)
Mengganti data run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
11
Masukkan data apa yang ingin anda hapus?
2
Masukkan data baru :
3
Data sudah diganti!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
7
Your data :
Data : 3
END
Keluar sekarang?
(1 = Yes, 0 = No)
Menambah data di indeks ke-1 run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
12
Masukkan data apa yang ingin anda tambahkan!
3
Data tadi ingin dimasukkan ke indeks ke berapa?
1
Data berhasil dimasukkan!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
7
Your data :
Data : 2
Data : 3
END
Keluar sekarang?
(1 = Yes, 0 = No)
Keluar run:
WELCOME!
Pilih menu yang ingin anda gunakan :
1. Cek kosong
2. Menambah data di awal
3. Menambah data di akhir
4. Menghapus data di awal
5. Menghapus data di akhir
6. Temukan data
7. Cetak semua data
8. Hapus semua data
9. Menghitung banyaknya data
10. Hapus data
11. Mengganti data
12. Menambah data di indeks ke-
13. Keluar
What do you want to do?
2
Masukkan data yang ingin anda tambahkan!
2
Data : 2 ditambahkan di awal!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
12
Masukkan data apa yang ingin anda tambahkan!
3
Data tadi ingin dimasukkan ke indeks ke berapa?
1
Data berhasil dimasukkan!
Keluar sekarang?
(1 = Yes, 0 = No)
0
What do you want to do?
7
Your data :
Data : 2
Data : 3
END
Keluar sekarang?
(1 = Yes, 0 = No)
1
Anda telah keluar!
Terima kasih.
BUILD SUCCESSFUL (total time: 0 seconds)
Setelah program di-run, kita akan diminta akan memasukkan input untuk memilih menu apa yang ingin kita akses.
Jika input yang dimasukkan adalah angka ‘1’ :
Merupakan perintah untuk mengecek apakah linklist masih kosong atau tidak.
Jika input yang dimasukkan adalah angka ‘2’ :
Kita akan diminta untuk memasukkan angka untuk diproses ke perintah selanjutnya, di mana fungsi tersebut akan memanggil method ‘addFirst’ yang berada di class ‘method’ dan merupakan implementasi dari Interface yang bernama ‘addFirst’ pula. Pada method ‘addFirst’, angka yang sudah kita masukkan tadi akan diproses menjadi sebuah Node yang bernama ‘baru’. Ada 2 kondisi yang akan diperhatikan pada saat node ‘baru’ akan diproses, yaitu apakah link list yang ada masih kosong apa sudah terisi. Jika belum terisi sama sekali, nilai dari node ‘head’ akan diisikan oleh nilai dari node ‘baru’ (yang terisi oleh input yang tadi kita masukkan), dan nilai dari node ‘tail’ akan diisikan oleh nilai dari node ‘baru’ pula. Sedangkan jika link list sudah terisi, maka nilai dari node ‘baru.next’ sama dengan node ‘head’, dan nilai dari node ‘head’ akan terisi oleh nilai dari node ‘baru’ (yang bernilai inputan yang kita masukkan tadi). Maka nilai yang kita masukkan tadi akan menjadi ‘head’ dari link list, sehingga nilai tersebut ditambahkan di awal (add first).
Jika input yang dimasukkan adalah angka ‘3’ :
Kita akan diminta untuk memasukkan angka untuk diproses ke perintah selanjutnya, di mana fungsi tersebut akan memanggil method ‘addLast’ yang berada di class ‘method’ dan merupakan implementasi dari Interface yang bernama ‘addLast’ pula. Pada method ‘addLast’ angka yang sudah kita masukkan tadi akan diproses menjadi sebuah Node yang bernama ‘baru’. Ada 2 kondisi yang akan diperhatikan pada saat node ‘baru’ diproses, yaitu apakah link list yang ada masih kosong apa sudah terisi. Jika belum terisi sama sekali, nilai dari node ‘head’ akan diisikan oleh nilai dari node ‘baru’ (yang terisi oleh input yang tadi kita masukkan), dan nilai dari node ‘tail’ akan diisikan oleh nilai dari node ‘baru’ pula. Sedangkan jika link list sudah terisi, maka nilai dari node ‘tail.next’ akan sama dengan node ‘baru’, dan nilai dari node ‘tail’ juga akan terisi oleh nilai dari node ‘baru’ (yang bernilai inputan yang kita masukkan tadi). Maka nilai yang kita masukkan tadi akan menjadi ‘tail’ dari link list, sehingga nilai tersebut ditambahkan di akhir (add last).
Jika input yang dimasukkan adalah angka ‘4’ :
Maka yang akan terjadi adalah angka (input) yang kita masukkan pertama kali akan dihapus. Hal ini diperoleh dengan beberapa tahap. Pertama, akan dibuat sebuah node baru yang bernama ‘temp’ yang bertujuan untuk mempermudah operasi. Selanjutnya akan dicek apakah link list masih kosong atau tidak. Jika iya, maka akan diproses untuk menampilkan kalimat ‘Data kosong!’ karena tidak ada data yang bisa diproses. Jika tidak, maka akan dicek lagi apakah data yang ada adalah data tunggal (hanya satu buah data) atau tidak. Jika iya maka node ‘head’ dan node ‘tail’ akan bernilai jadi null, alias kosong, maka bisa disimpulkan bahwa sekarang link list kosong. Jika tidak maka node ‘head’ akan diisi oleh node ‘temp.next’ yang masih kosong. Oleh karena itu, nilai dari node ‘head’ akan bernilai kosong, karena ia menunjuk pada node ‘temp.next’ yang bernilai null.
Jika input yang dimasukkan adalah angka ‘5’ :
Maka yang akan terjadi adalah angka (input) yang kita masukkan terakhir kali akan dihapus. Hal ini diperoleh dengan beberapa tahap. Pertama, akan dibuat sebuah node baru yang bernama ‘temp’ yang bertujuan untuk mempermudah operasi. Selanjutnya akan dicek apakah link list masih kosong atau tidak. Jika iya, maka akan diproses untuk menampilkan kalimat ‘Data kosong!’ karena tidak ada data yang bisa diproses. Jika tidak, maka akan dicek lagi apakah data yang ada adalah data tunggal (hanya satu buah data) atau tidak. Jika iya maka node ‘head’ dan node ‘tail’ akan bernilai jadi null, alias kosong, maka bisa disimpulkan bahwa sekarang link list kosong. Jika tidak maka akan terjadi proses looping yang memiliki kondisi jika node ‘temp.next’ tidak sama dengan node ‘tail’ maka nilai dari node ‘temp’ akan bernilai sama dengan node ‘temp.next’. Ketika node ‘temp.next’ sudah bernilai sama dengan node ‘tail’ maka nilai dari node ‘temp.next’ akan menjadi null, dan node ‘tail’ akan ditunjuk ke variabel ‘temp’. Oleh karena itu, nilai terakhir yang dulunya menjadi ‘tail’ sudah dihapus.
Jika input yang dimasukkan adalah angka ‘6’ :
Merupakan perintah untuk mencari data yang kita inginkan. Kita akan diminta untuk memasukkan data yang kita ingin kita cari. Selanjutnya data tadi akan diproses di method ‘find’ (yang merupakan implementasi dari Interface yang bernama ‘find’ pula). Pada proses di method ini akan dibuat variabel ‘i’ yang bertipe integer dan variabel ‘found’ yang bertipe data boolean (yang bernilai awal ‘false’). Lalu juga akan dibuat node baru yang bernama ‘temp’ yang nilai awalnya sama dengan node ‘head’. Selanjutnya akan dilakukan looping untuk mengecek apakah node ‘temp’ bernilai null atau tidak. Selama nilai dari node ‘temp’ tidak bernilai 0, maka akan dicek apakah nilai dari node ‘temp.data’ bernilai sama dengan ‘data’ (angka yang kita masukkan tadi) atau tidak. Jika tidak, looping akan terus berjalan dengan nilai dari variabel ‘i’ akan terus bertambah, dan node ‘temp’ akan berubah menjadi ‘temp.next’. Jika iya, maka nilai dari variabel ‘found’ akan berubah menjadi true, dan looping dihentikan (akibat adanya statemen break). Lalu dilanjutkan dengan fungsi if untuk mengecek apakah nilai dari variabel ‘found’ sudah bernilai true apa belum. Jika sudah, maka masuk ke value if true nya di mana program akan mencetak data yang dicari dan indeks ke berapa data tersebut ditemukan. Jika variabel ‘found’ belum bernilai true, maka akan masuk ke value if false nya di mana program akan mencetak ‘Data tidak ditemukan!’.
Jika input yang dimasukkan adalah angka ‘7’ :
Merupakan perintah untuk mencetak semua data yang ada pada link list. Maka langsung ke method ‘printNode’ (yang merupakan implementasi dari Interface ‘printNode’ pula), yang selanjutnya akan dibuat Node baru bernama ‘temp’ yang nilai awalnya sama dengan node ‘head’. Lalu akan dilakukan looping yang memiliki kondisi ‘temp != null’ (node ‘temp’ tidak sama dengan null), artinya selama node ‘temp’ tidak bernilai kosong (yang artinya belum mencapai nilai akhir dari link list), maka akan dicetak data yang ada pada node tersebut (node ‘temp.data’), dan nilai dari node ‘temp’ akan berubah menjadi ‘temp.next’. Hal tersebut dilakukan sampai tidak memenuhi kondisi looping.
Jika input yang dimasukkan adalah angka ‘8’ :
Merupakan perintah untuk menghapus semua data yang ada pada link list. Maka langsung ke method ‘clear’ (yang merupakan implementasi dari Interface ‘clear’ pula), yang akan mengubah nilai dari node ‘head’ menjadi null. Hal tersebut akan mengosongkan link list yang ada.
Jika input yang dimasukkan adalah angka ‘9’ :
Merupakan perintah untuk menghitung berapa banyak data yang ada pada link list. Maka langsung ke method ‘length’ (yang merupakan implementasi dari Interface ‘length’ pula), yang akan membuat variabel baru bernama ‘i’ yang bertipe integer, dan node baru yang bernama ‘temp’ yang bernilai awal sama dengan node ‘head’. Lalu akan dilakukan looping yang memiliki kondisi ‘temp != null’, yang artinya selama node ‘temp’ belum mencapai nilai null (yang berarti akhir dari link list) maka looping while akan terus dilakukan. Selama looping while, nilai dari variabel ‘i’ akan bertambah 1 terus, dan nilai dari node ‘temp’ akan berubah menjadi ‘temp.next’. selanjutnya, setelah looping selesai, maka program akan mencetak nilai dari variabel ‘i’ yang nilainya sama dengan jumlah data yang ada pada link list tersebut.
Jika input yang dimasukkan adalah angka ‘10’ :
Merupakan perintah untuk menghapus data pada indeks tertentu. Maka kita akan diminta untuk memasukkan angka yang ingin kita hapus. Selanjutnya, data tersebut akan diproses ke method ‘remove’ (yang merupakan implementasi dari Interface bernama ‘remove’ pula). Akan dibuat node baru yang bernama ‘temp’ dan ‘hm’ yang nilai awal keduanya sama dengan node ‘head’. Selanjutnya akan dilakukan looping dengan kondisi ‘temp.data != data’ dan ‘temp != null’. Selama memenuhi kondisi tersebut, maka nilai dari node ‘hm’ akan berubah menjadi sama dengan node ‘temp’, dan node ‘temp’ akan berubah menjadi node ‘temp.next’. Selanjutnya, jika data yang dicari sudah ditemukan (dengan berhentinya looping while tadi), maka akan diproses ke value if true nya dari fungsi if ‘temp.data == data’, yaitu nilai dari node ‘hm.next’ akan sama dengan nilai dari ‘temp.next’, lalu akan dicetak ‘Data sudah dihapus!’ yang menandakan bahwa data yang tadi kita masukkan sudah dihapus. Namun jika nilai dari node ‘temp.data’ tidak sama dengan ‘data’ yang tadi kita masukkan, maka akan masuk ke value if false nya, dimana akan dicetak ‘Data tidak ditemukan!’ karena tidak ada data yang cocok dengan data yang kita cari.
Jika input yang dimasukkan adalah angka ‘11’ :
Merupakan perintah untuk merubah data apa yang kita inginkan, dan menggantinya dengan data baru. Untuk itu kita akan diminta untuk mengetikkan data apa yang ingin kita ganti, lalu mengetikkan data baru apa yang ingin kita masukkan untuk merubah data yang lama tadi. Selanjutnya data-data tersebut akan diproses ke method ‘replace’ (yang merupakan implementasi dari Interface bernama ‘replace’ pula). Akan dibuat node baru yang bernama ‘temp’ yang nilai awalnya sama dengan node ‘head’. Selanjutnya akan dilakukan looping dengan kondisi ‘temp != null’, artinya selama nilai dari node ‘temp’ belum mencapai null (belum mencapai akhir dari link list) maka looping akan terus dilakukan dan setiap kali looping nilai dari node ‘temp’ akan berubah menjadi ‘temp.next’. Selama looping pun juga dilakukan pengecekan apakah data yang tadi dimasukkan sama dengan ‘temp.data’. Jika sama, maka nilai dari variabel ‘found’ akan berubah menjadi true, dan nilai dari ‘temp.data’ akan berubah menjadi nilai dari ‘newData’ (data yang tadi kita masukkan), dan looping pun dihentikan (karena ada statemen break). Selanjutnya akan dilakukan pengecekan menggunakan fungsi if, dengan kondisi apakah nilai dari variabel ‘found’ sudah berubah menjadi true apa belum. Jika sudah, maka masuk ke value if true nya dimana akan dicetak kalimat ‘Data sudah diganti!’. Namun jika belum, maka masuk ke value if false nya dimana akan dicetak ‘Data tidak ditemukan!’ karena hingga looping tadi selesai, tidak ada data yang cocok, sehingga tidak bisa diganti.
Jika input yang dimasukkan adalah angka ‘12’ :
Merupakan perintah untuk menambahkan data pada indeks tertentu yang kita inginkan. Maka kita akan diminta untuk memasukkan data apa yang ingin kita tambahkan, dan pada indeks ke berapa data tadi ingin kita tambahkan. Selanjutnya data-data tadi akan diproses di method ‘insert’ (yang merupakan implementasi dari Interface yang bernama ‘insert’ pula). Akan dibuat node baru yang bernama ‘temp’ yang nilai awalnya sama dengan node ‘head’. Lalu akan dibuat pula variabel ‘i’ yang bertipe integer dan bernilai awal 0, dan juga variabel ‘indek’ yang bertipe integer dan bernilai awal ‘indeks-1’. Selanjutnya akan dicek apakah nilai dari ‘indeks’ bernilai 0 atau tidak. Jika iya, maka nilai dari node ‘data.next’ akan sama dengan node ‘head’, dan nilai dari ‘head’ akan sama dengan nilai dari node ‘data’. Namun jika variabel ‘i’ tidak bernilai 0, maka akan dilakukan looping dengan kondisi ‘temp!=null’, artinya selama nilai dari node ‘temp’ tidak bernilai null, maka looping akan terus dijalankan. Setiap kali looping akan dilakukan pengecekan apakah nilai dari ‘i’ sama dengan nilai dari ‘indek’. Jika sama, maka nilai dari node ‘data.next’ akan sama dengan nilai dari node ‘temp.next’, nilai dari node ‘temp.next’ akan sama dengan nilai dari node ‘data’, lalu akan dicetak kalimat ‘Data sudah dimasukkan!’, dan looping pun dihentikan (dengan adanya statemen break yang memutus looping). Namun jika nilai dari ‘i’ tidak sama dengan ‘indek’ maka akan masuk ke value if false nya dimana nilai dari ‘i’ akan bertambah satu, dan nilai dari node ‘temp’ akan diarahkan ke ‘temp.next’.
Jika input yang dimasukkan adalah angka ‘13’ :
Merupakan perintah untuk mengakhiri program. Program akan mencetak kalimat ‘Anda sudah keluar!’ dan ‘Terima kasih.’.
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
LINK LIST
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 10 APRIL 2014
PENDAHULUAN
Stack (tumpukan) adalah sebuah kumpulan data di mana data yang diletakkan di atas data yang lain. Dengan demikian stack adalah struktur data yang menggunakan konsep LIFO. Elemen terakhir yang disimpan dalam stack menjadi elemen pertama yang diambil. Dalam proses komputasi, untuk meletakkan sebuah elemen pada bagian atas stack disebut dengan push. Dan untuk memindahkan dari tempat teratas tersebut, kita melakukan pop.
Ada 2 operasi paling dasar dari stack yang dapat dilakukan, yaitu: 1. Operasi push yaitu operasi menambahkan elemen pada urutan terakhir (paling atas). 2. Operasi pop yaitu operasi mengambil sebuah elemen data pada urutan terakhir dan
menghapus elemen tersebut dari stack. Implementasi Stack dengan Array
Struktur data stack dapat diimplementasikan dengan menggunakan sebuah array dan
variabel tOs (topOfStack) bertipe integer untuk menyimpan indeks dari nilai tOs (antara stack
dan variabel tOs-nya terpisah). Untuk stack kosong dapat dikenali apabila nilai tOs = -1.
Implementasi Stack dengan Linked List
Struktur data stack dapat juga diimplementasikan dengan menggunakan linked list.
variabel tos bertipe reference objek untuk menunjuk node yang paling terakhir kali
ditambahkan ke dalam stack. Untuk stack kosong dapat dikenali apabila nilai tos = null.
SOURCE CODE
Stack in Array
package Stack_Array1;
import java.util.Scanner;
public class Stack_Array implements IStack_Array1
{
public Scanner dataIn = new Scanner (System.in);
protected int[] data;
protected int TOS = 0;
public Stack_Array (int mx)
{
data = new int[mx];
}
@Override
public int setData ()
{
int input;
System.out.println ("Masukkan data = ");
input = dataIn.nextInt();
return input;
}
@Override
public void isEmpty()
{
if (TOS == 0)
{
System.out.println("Maaf, stack kosong");
}
else
if (TOS == 9)
{
System.out.println("Maaf, stack penuh");
}
else
if (TOS > 0 && TOS < 9)
{
System.out.println("Stacks belum penuh");
System.out.println("============");
}
}
@Override
public void isFull()
{
if (TOS == 0)
{
System.out.println ("Maaf, stack kosong");
}
else
if (TOS == 9)
{
System.out.println("Maaf, stack penuh");
}
else
if (TOS > 0 && TOS < 9)
{
System.out.println("Stacks belum penuh");
System.out.println("============");
}
}
@Override
public void push(int result)
{
if( TOS!=9){
TOS++;
data[TOS] = result;
}
else {
System.out.println("Stack penuh");
}
}
@Override
public int pop()
{
int hasil = 0;
if (TOS == 0)
hasil = data [TOS];
TOS--;
return hasil;
}
@Override
public void makeEmpty()
{
TOS = 0;
System.out.println("Hapus semua data berhasil");
}
@Override
public void print()
{
if(TOS <= 0)
{
System.out.println("Maaf, stack kosong");
}
else
{
System.out.println("data :");
for (int a = TOS; a>0; a--)
{
System.out.println(""+data[a]);
}
}
}
@Override
public int top()
{
int result = data[TOS];
System.out.println("Top = " + result);
return result;
}
}
Interface
package Stack_Array1;
public interface IStack_Array1 {
int setData();
void isEmpty();
void isFull();
void push(int data);
int pop();
void makeEmpty();
void print();
int top();
}
Test
package Stack_Array1;
import java.util.Scanner;
public class TestAr {
public static void main(String[] args) {
Stack_Array proses = new Stack_Array(10);
Scanner dataIn = new Scanner(System.in);
for (int i = 1; i > 0; i++) {
{
System.out.println("=========================");
System.out.println("====== ARRAY STACK ======");
System.out.println("=========================");
System.out.println("[1] IsEmpty");
System.out.println("[2] IsFull");
System.out.println("[3] Push");
System.out.println("[4] Pop");
System.out.println("[5] Clear");
System.out.println("[6] Print");
System.out.println("[7] Top");
System.out.println("[8] KELUAR");
System.out.println("--------------------------");
System.out.print("Pilihan Anda = ");
int a;
a = dataIn.nextInt();
switch (a) {
case 1:
proses.isEmpty();
break;
case 2:
proses.isFull();
break;
case 3:
proses.push(proses.setData());
break;
case 4:
proses.pop();
break;
case 5:
proses.makeEmpty();
break;
case 6:
proses.print();
break;
case 7:
proses.top();
break;
case 8:
System.out.println("SELESAI (^_^)");
System.exit(0);
default:
System.out.println("MAAF PILIHAN SALAH");
}
}
}
}
}
Stack in List
package stack_list2;
public class Stack_List2 implements iStacklist {
Node TOS;
@Override
public boolean isEmpty() {
return (TOS == null);
}
@Override
public void push(int data) {
Node temp = new Node();
temp.data = data;
temp.next = null;
if (isEmpty()) {
TOS = temp;
} else {
temp.next = TOS;
TOS = temp;
}
}
@Override
public int pop() {
Node temp;
if (isEmpty()) {
System.out.println("Stack Kosong");
} else {
if (TOS.next == null) {
TOS = null;
} else {
temp = TOS;
TOS = TOS.next;
temp.next = null;
}
}
return 0;
}
@Override
public void makeEmpty() {
TOS = null;
}
@Override
public void print() {
if (!isEmpty()) {
System.out.println("Data dalam stack list : ");
Node temp;
temp = TOS;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
} else {
System.out.println("Stack List Kosong");
}
}
@Override
public void top() {
if (isEmpty()) {
System.out.println("Stack List Kosong");
} else {
System.out.println("Data terakhir : " + TOS.data);
}
}
}
Node
package stack_list2;
public class Node {
Integer data;
Node next;
}
Interface
package stack_list2;
public interface iStacklist {
boolean isEmpty();
void push(int data);
int pop();
void makeEmpty();
void print();
void top();
}
Test
package stack_list2;
import java.util.Scanner;
public class TestStackList {
public static void menu() {
System.out.println("===========================");
System.out.println("===== STACK LIST MENU =====");
System.out.println("=========d=================");
System.out.println("[1] Input Data [push]");
System.out.println("[2] Tampilkan Data");
System.out.println("[3] Hapus Data Terakhir [pop]");
System.out.println("[4] Hapus Semua Data");
System.out.println("[5] Top Data");
System.out.println("[6] Cek IsEmpty");
System.out.println("[7] KELUAR");
System.out.println("----------------------------");
System.out.print("Pilihan Anda = ");
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
Stack_List2 Call = new Stack_List2();
for (int i = 1; i > 0; i++) {
menu();
int p = scan.nextInt();
switch (p) {
case 1: {
System.out.println("Masukkan data : ");
int data = scan.nextInt();
Call.push(data);
break;
}
case 2: {
Call.print();
break;
}
case 3: {
Call.pop();
System.out.println("Data terakhir berhasil
dihapus");
break;
}
case 4: {
Call.makeEmpty();
System.out.println("Semua data berhasil
dihapus");
break;
}
case 5: {
Call.top();
break;
}
case 6: {
if (Call.isEmpty()) {
System.out.println("Maaf, Link List
kosong");
} else {
System.out.println("Link List tidak
kosong");
}
break;
}
default:
break;
}
if (p == 7) {
break;
}
}
}
}
ANALISIS
Stack in Array
Pada program ini menggunakan array. Sehingga data yang ditampung dalam
array. Berikut ini adalah beberapa operasi dalam stack array.
1. Jika mengetik angka 1, maka akan menuju menu IsEmpty, yaitu mengecek apakah
stack kosong. Jika tOs berisi 0, maka tidak ada data yang disimpan dalam stack
tersebut. Jika tOs bernilai 9, maka stack penuh.
2. Jika mengetik angka 2, maka akan menuju menu IsFull, yaitu mengecek apakah
stack sudah penuh. Jika tOs berisi 0, maka tidak ada data yang disimpan dalam
stack tersebut. Jika tOs bernilai 9, maka stack penuh.
3. Jika mengetik angka 3, maka akan menuju menu push, yaitu menu untuk
memasukkan data. Jika nilai tOs tidak sama dengan 9, maka nilai TOS akan di-
increment (menambah data dalam stack melalui penambahan nilai tOs). Jika
kondisinya tidak memenuhi, maka akan mencetak "Stack penuh"
4. Jika mengetik angka 4, maka akan menuju menu pop, yaitu menu untuk
menghapus data. Nilai hasil mula-mula = 0. Jika nilai tOs = 0, maka hasil = data
[tOs]. Selanjutnya nilai tOs di-decrement (menghapus data melalui pengurangan
dari nilai tOs), lalu akan mengembalikan nilai hasil.
5. Jika mengetik angka 5, maka akan menuju menu clear, yaitu menu untuk
menghapus semua data. Membuat nilai tOs = 0, maka akan menghapus semua
data dalam stack.
6. Jika mengetik angka 6, maka akan menuju menu print, yaitu menu untuk
menampilkan semua data. Jika tOs < = 0, maka menandakan bahwa stack kosong.
Jika kondisinya tidak memenuhi, maka akan dicetak semua data dalam stack
dengan konsep perulangan. Jika a = tOs; a > 0; a - -, maka akan mencetak data
sampai kondisinya tidak memenuhi lagi.
7. Jika mengetik angka 7, maka akan menuju menu top, yaitu menu untuk
menampilkan data teratas. Nilai result = data [tOs], maka akan mencetak data
teratas dari stack tersebut, dengan mengembalikan nilai result.
8. Jika mengetik angka 8, maka akan menuju menu keluar, yaitu menu untuk keluar
dari program.
Stack in List
1. Jika mengetik angka 1, maka akan menuju menu push, yaitu menu untuk
memasukkan data. Data yang dimasukkan akan menuju ke variabel data.
Selanjutnya mengecek, jika stack kosong maka tOs = temp. Jika kondisinya tidak
memenuhi maka temp.next = tOs dan tOs = temp.
2. Jika mengetik angka 2, maka akan menuju menu tampilkan data, yaitu menu
untuk memasukkan data. Jika kondisi stack tidak kosong, maka akan mencetak
data dalam stack. Dengan konsep perulangan, ketika nilai temp tidak sama
dengan null, data akan dicetak satu persatu. Jika kondisinya tidak memenuhi,
maka stack list kosong.
3. Jika mengetik angka 3, maka akan menuju menu pop, yaitu menu untuk
menghapus data terakhir. Jika kondisi stack kosong, maka akan mencetak ke layar
"stack kosong". Jika kondisinya tidak memenuhi, maka nilai tOs.next = null. Lalu
tOs = null memberikan perintah bahwa data terakhir yang dimasukkan akan
bernilai null (kosong). Jadi data terakhir akan terhapus.
4. Jika mengetik angka 4, maka akan menuju menu hapus semua, yaitu menu untuk
menghapus semua data. Dengan membuat nilai tOs = null, maka semua data
dalam stack list dihapus semua (kosong).
5. Jika mengetik angka 5, maka akan menuju menu top, yaitu menu untuk
menampilkan data teratas. Jika kondisi stack kosong, maka akan mencetak ke
layar "stack kosong". Jika kondisinya tidak memenuhi, maka akan mencetak data
teratas, yaitu dengan nilai tOs.data (data terakhir yang dimasukkan).
6. Jika mengetik angka 6, maka akan menuju menu IsEmpty, yaitu menu untuk
mengecek stack keadaan kosong atau tidak. Dengan membuat nilai kembalian tOs
= null, jika kondisi memenuhi, maka akan mencetak ke layar "maaf, link list
kosong" dan jika kondisi tidak memenuhi, maka akan mencetak ke layar "link list
tidak kosong".
7. Jika mengetik angka 7, maka akan menuju menu keluar, yaitu menu untuk keluar
dari program.
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
QUEUE
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 17 APRIL 2014
PENDAHULUAN
Queue (antrian) adalah barisan elemen yang apabila elemen ditambah maka
penambahannya berada di posisi belakang (rear) dan jika dilakukan pengambilan elemen
dilakukan di elemen paling depan (front). Oleh karena itu, queue bersifat FIFO (first in first
out). Operasi-operasi dasar dari sebuah queue adalah:
Enqueue: proses penambahan elemen di posisi belakang
Dequeue: proses pengambilan elemen di posisi depan
Selain operasi dasar di atas, ada pula operasi-operasi lain yang dapat dilakukan terhadap
sebuah queue yaitu :
Operasi pemeriksaan queue kosong (fungsi kosong)
Operasi pemeriksaan queue penuh (fungsi penuh)
Operasi inisialisasi queue (fungsi inisialisasi)
Representasi antrian secara sekuen relatif lebih sulit dibanding stack. Seperti dijelaskan
di atas bahwa antrian juga merupakan satu kumpulan data. Dengan demikian tipe data yang
sesuai untuk menyajikan antrian adalah menggunakan array atau linked list.
Implementasi Queue dengan Array
Struktur data queue dapat diimplementasikan dengan menggunakan sebuah array. 3 versi
implementasi queue dengan menggunakan array, yakni:
1. Versi 1: Implementasi queue dengan 1 variabel index, yakni back untuk me-maintain
jumlah elemen queue. Setiap ada proses dequeue harus dilakukan penggeseran elemen
sebanyak jumlah elemen array-1.
2. Versi 2: Implementasi queue dengan 2 variabel index, yakni back untuk me-maintain
elemen paling belakang dan front untuk me-maintain elemen paling depan.
3. Versi 3: Implementasi queue dengan circular array dengan mengorbankan 1 field array
yang digunakan untuk definisi queue kosong atau queue penuh.
Implementasi Queue dengan Linked List
Selain menggunakan array, queue juga dapat dibuat dengan linked list. Operasi-operasi
Queue dengan Linked List:
1. IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah
berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada
Null atau tidak. Jika benar berarti queue masih kosong.
2. IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa
menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan
MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
3. EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head
dan tail mula-mula meunjukkan ke NULL).
4. DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini
dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
SOURCE CODE
1. Queue Array 1 (Geser)
package sdaqueue1;
public class SDAQueue1 implements IQueue {
private int[] array;
private int front, back;
public SDAQueue1() {
array = new int[5];
front = back = -1;
}
@Override
public boolean isEmpty() {
return (back == -1);
}
@Override
public void makeEmpty() {
front = back = -1;
System.out.println("Queue berhasil dikosongkan");
}
@Override
public void enqueue(int data) {
if (isFull()) {
System.out.println("Queue sudah penuh");
} else {
if (isEmpty()) {
front++;
}
array[++back] = data;
System.out.println("Data berhasil dimasukkan");
}
}
@Override
public int dequeue() {
if (isEmpty()) {
return -1;
} else {
int awal = array[front];
if (front == back) {
front = back = -1;
} else {
geser();
back--;
}
return awal;
}
}
public boolean isFull() {
return (back == array.length - 1);
}
private void geser() {
for (int i = front + 1; i <= back; i++) {
array[i - 1] = array[i];
}
}
public void print() {
if (isEmpty()) {
System.out.println("Tidak ada data dalam Queue");
} else {
for (int i = front; i <= back; i++) {
System.out.println(array[i]);
}
}
}
}
o Interface
package sdaqueue1;
public interface IQueue {
boolean isEmpty();
boolean isFull();
void makeEmpty();
void enqueue(int data);
int dequeue();
void print();
}
o Test
package sdaqueue1;
import sdaqueue1.*;
import java.util.Scanner;
public class Test1 {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
SDAQueue1 IQ = new SDAQueue1();
boolean j = true;
while (j) {
Menu();
int p = scn.nextInt();
switch (p) {
case 1: {
System.out.print("Masukkan data angka : ");
p = scn.nextInt();
IQ.enqueue(p);
break;
}
case 2: {
p = IQ.dequeue();
if (p != -1) {
System.out.print("Data dengan nilai ");
System.out.print(p);
System.out.println(" telah berhasil dihapus");
} else {
System.out.println("Tidak ada data dalam Queue");
}
break;
}
case 3: {
IQ.makeEmpty();
break;
}
case 4: {
IQ.print();
break;
}
case 5: {
if (IQ.isEmpty()) {
System.out.println("Maaf, Queue kosong");
} else {
System.out.println("Queue tidak kosong");
}
break;
}
case 6: {
if (IQ.isFull()) {
System.out.println("Maaf, Queue Penuh");
} else {
System.out.println("Queue tidak Penuh");
}
break;
}
case 7: {
j = false;
break;
}
default: {
System.out.print("Masukan anda salah. ");
System.out.println("Masukkan angka antara 1-4");
}
}
}
}
public static void Menu() {
System.out.println("=============================");
System.out.println("===== QUEUE IMPL 1 MENU =====");
System.out.println("=============================");
System.out.println("1. Masukkan data (Enqueue)");
System.out.println("2. Hapus data (Dequeue)");
System.out.println("3. Kosongkan Queue (makeEmpty)");
System.out.println("4. Tampilkan Data");
System.out.println("5. Cek IsEmpty ");
System.out.println("6. Cek IsFull");
System.out.println("7. KELUAR");
System.out.println("------------------------------");
System.out.print("Pilihan Anda = ");
}
}
2. Queue Array 2 (Penggandaan Ukuran Array)
package sdaqueue2;
public class SDAQueue2 implements IQueue {
private int[] array;
private int front, back = -1;
public SDAQueue2() {
array = new int[5];
front = back = -1;
}
@Override
public boolean isEmpty() {
return (back == -1);
}
@Override
public void makeEmpty() {
front = back = -1;
System.out.println("Queue telah dikosongkan");
}
@Override
public void enqueue(int data) {
if (isFull()) {
doubleArray();
}
if (isEmpty()) {
front++;
}
array[++back] = data;
System.out.println("Data berhasil dimasukkan");
}
@Override
public int dequeue() {
if (isEmpty()) {
return -1;
} else if (front == back) {
int d = array[front];
front = back = -1;
return d;
} else {
return array[front++];
}
}
@Override
public boolean isFull() {
return (back == array.length - 1);
}
private void doubleArray() {
int[] arr = new int[2 * array.length];
if (!isEmpty()) {
for (int i = front; i <= back; i++) {
arr[i] = array[i];
}
array = arr;
}
}
public void print() {
if (isEmpty()) {
System.out.println("Tidak ada data dalam Queue");
} else {
for (int i = front; i <= back; i++) {
System.out.println(array[i]);
}
}
}
}
o Interface
package sdaqueue2;
public interface IQueue {
boolean isEmpty();
boolean isFull();
void makeEmpty();
void enqueue(int data);
int dequeue();
void print();
}
o Test
package sdaqueue2;
import sdaqueue2.*;
import java.util.Scanner;
public class Test2 {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
SDAQueue2 IQ = new SDAQueue2();
boolean j = true;
while (j) {
Menu();
int p = scn.nextInt();
switch (p) {
case 1: {
System.out.print("Masukkan data angka : ");
p = scn.nextInt();
IQ.enqueue(p);
break;
}
case 2: {
p = IQ.dequeue();
if (p != -1) {
System.out.print("Data dengan nilai ");
System.out.print(p);
System.out.println(" telah berhasil dihapus");
} else {
System.out.println("Tidak ada data dalam Queue");
}
break;
}
case 3: {
IQ.makeEmpty();
break;
}
case 4: {
IQ.print();
break;
}
case 5: {
if (IQ.isEmpty()) {
System.out.println("Maaf, Queue kosong");
} else {
System.out.println("Queue tidak kosong");
}
break;
}
case 6: {
if (IQ.isFull()) {
System.out.println("Maaf, Queue Penuh");
} else {
System.out.println("Queue tidak Penuh");
}
break;
}
case 7: {
j = false;
break;
}
default: {
System.out.print("Masukan anda salah. ");
System.out.println("Masukkan angka antara 1-4");
}
}
}
}
public static void Menu() {
System.out.println("=============================");
System.out.println("===== QUEUE IMPL 2 MENU =====");
System.out.println("=============================");
System.out.println("1. Masukkan data (Enqueue)");
System.out.println("2. Hapus data (Dequeue)");
System.out.println("3. Kosongkan Queue (makeEmpty)");
System.out.println("4. Tampilkan Data");
System.out.println("5. Cek IsEmpty ");
System.out.println("6. Cek IsFull");
System.out.println("7. KELUAR");
System.out.println("------------------------------");
System.out.print("Pilihan Anda = ");
}
}
3. Queue Array 3 (Circular Array)
package sdaqueue3;
public class SDAQueue3 implements IQueue {
private int[] array;
private int front, back;
public SDAQueue3() {
array = new int[5];
front = back = -1;
}
@Override
public boolean isEmpty() {
return (back == -1);
}
@Override
public void makeEmpty() {
front = back = -1;
System.out.println("Queue telah dikosongkan");
}
@Override
public void enqueue(int data) {
if (isFull()) {
System.out.println("Queue telah penuh");
} else {
if (isEmpty()) {
front = back = 0;
} else {
back = (back + 1) % array.length;
}
array[back] = data;
System.out.println("Data berhasil dimasukkan");
}
}
@Override
public int dequeue() {
if (isEmpty()) {
return -1;
} else {
int d = array[front];
if (front == back) {
front = back = -1;
} else {
front = (front + 1) % array.length;
}
return d;
}
}
public boolean isFull() {
return ((back + 1) % array.length == front);
}
@Override
public void print() {
if (isEmpty()) {
System.out.println("Tidak ada data dalam Queue");
} else {
for (int i = front; i <= back; i++) {
System.out.println(array[i]);
}
}
}
}
o Interface
package sdaqueue3;
public interface IQueue {
boolean isEmpty();
boolean isFull();
void makeEmpty();
void enqueue(int data);
int dequeue();
void print();
}
o Test
package sdaqueue3;
import sdaqueue3.*;
import java.util.Scanner;
public class Test3 {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
SDAQueue3 IQ = new SDAQueue3();
boolean j = true;
while (j) {
Menu();
int p = scn.nextInt();
switch (p) {
case 1: {
System.out.print("Masukkan data angka : ");
p = scn.nextInt();
IQ.enqueue(p);
break;
}
case 2: {
p = IQ.dequeue();
if (p != -1) {
System.out.print("Data dengan nilai ");
System.out.print(p);
System.out.println(" telah berhasil dihapus");
} else {
System.out.println("Tidak ada data dalam Queue");
}
break;
}
case 3: {
IQ.makeEmpty();
break;
}
case 4: {
IQ.print();
break;
}
case 5: {
if (IQ.isEmpty()) {
System.out.println("Maaf, Queue kosong");
} else {
System.out.println("Queue tidak kosong");
}
break;
}
case 6: {
if (IQ.isFull()) {
System.out.println("Maaf, Queue Penuh");
} else {
System.out.println("Queue tidak Penuh");
}
break;
}
case 7: {
j = false;
break;
}
default: {
System.out.print("Masukan anda salah. ");
System.out.println("Masukkan angka antara 1-4");
}
}
}
}
public static void Menu() {
System.out.println("=============================");
System.out.println("===== QUEUE IMPL 3 MENU =====");
System.out.println("=============================");
System.out.println("1. Masukkan data (Enqueue)");
System.out.println("2. Hapus data (Dequeue)");
System.out.println("3. Kosongkan Queue (makeEmpty)");
System.out.println("4. Tampilkan Data");
System.out.println("5. Cek IsEmpty ");
System.out.println("6. Cek IsFull");
System.out.println("7. KELUAR");
System.out.println("------------------------------");
System.out.print("Pilihan Anda = ");
}
}
4. Queue List
package sdaqueue4;
public class SDAQueue4 implements IQueue {
Node front, back;
public SDAQueue4() {
front = back = null;
}
@Override
public boolean isEmpty() {
return (front == null);
}
@Override
public void makeEmpty() {
if (isEmpty()) {
System.out.println("Queue kosong");
} else {
Node temp = front;
while (temp != null) {
front = front.next;
temp = null;
temp = front;
}
System.out.println("Queue telah dikosongkan");
}
}
@Override
public void enqueue(int data) {
Node temp = new Node();
temp.data = data;
if (isEmpty()) {
front = back = temp;
} else {
back.next = temp;
back = temp;
}
System.out.println("Data berhasil dimasukkan");
}
@Override
public int dequeue() {
if (isEmpty()) {
return -1;
} else {
int d = front.data;
if (front == back) {
front = back = null;
} else {
Node temp = front;
front = temp.next;
temp = null;
}
return d;
}
}
public void print() {
Node temp = front;
if (!isEmpty()) {
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
}
}
o Interface
package sdaqueue4;
public interface IQueue {
boolean isEmpty();
void makeEmpty();
void enqueue(int data);
int dequeue();
void print();
}
o Node
package sdaqueue4;
public class Node {
int data;
Node next;
}
o Test
package sdaqueue4;
import sdaqueue4.*;
import java.util.Scanner;
public class Test4 {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
SDAQueue4 IQ = new SDAQueue4();
boolean j = true;
while (j) {
Menu();
int p = scn.nextInt();
switch (p) {
case 1: {
System.out.print("Masukkan data angka : ");
p = scn.nextInt();
IQ.enqueue(p);
break;
}
case 2: {
p = IQ.dequeue();
if (p != -1) {
System.out.print("Data dengan nilai ");
System.out.print(p);
System.out.println(" telah berhasil dihapus");
} else {
System.out.println("Tidak ada data dalam Queue");
}
break;
}
case 3: {
IQ.makeEmpty();
break;
}
case 4: {
IQ.print();
break;
}
case 5: {
if (IQ.isEmpty()) {
System.out.println("Maaf, Queue kosong");
} else {
System.out.println("Queue tidak kosong");
}
break;
}
case 6: {
j = false;
break;
}
default: {
System.out.print("Masukan anda salah. ");
System.out.println("Masukkan angka antara 1-4");
}
}
}
}
public static void Menu() {
System.out.println("====================================")
;
System.out.println("===== QUEUE IMPL 4 (LIST) MENU =====");
System.out.println("====================================")
;
System.out.println("1. Masukkan data (Enqueue)");
System.out.println("2. Hapus data (Dequeue)");
System.out.println("3. Kosongkan Queue (makeEmpty)");
System.out.println("4. Tampilkan Data");
System.out.println("5. Cek IsEmpty ");
System.out.println("6. KELUAR");
System.out.println("------------------------------------
");
System.out.print("Pilihan Anda = ");
}
}
ANALISIS
1. Queue Array 1 (Geser)
Pada program ini menggunakan array. Sehingga data yang ditampung dalam array.
Array yang digunakan berbentuk linier. Linear array adalah suatu array yang dibuat
seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar.
Ukuran array sudah tidak bisa ditambah lagi.
2. Queue Array 2 (Penggandaan Ukuran Array)
Pada program ini menggunakan array. Sehingga data yang ditampung dalam array.
Array yang digunakan berbentuk linier. Linear array adalah suatu array yang dibuat
seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar.
Ukuran array masih bisa ditambah lagi jika array awal dalam kondisi sudah penuh.
3. Queue Array 3 (Circular Array)
Pada program ini menggunakan array. Sehingga data yang ditampung dalam array. Array
yang digunakan berbentuk circular. Circular array adalah suatu array yang dibuat seakan-
akan merupakan sebuah lingkaran dengan titik awal (front) dan titik akhir (back) saling
bersebelahan jika array tersebut masih kosong. Posisi front dan back adalah bebas
asalkan saling bersebelahan.
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
BINARY SEARCH TREE
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 29 APRIL 2014
Kelas Node
Kelas BinTree
Kelas MainTree
Hasil Kompilasi
Analisa
Program ini menggunakan pengimplementasian tree, bertujuan untuk menampilkan
pilihan menu kemudian user dapat memilih menu yang sudah tersedia. Program ini
menggunakan tiga kelas, yaitu Node, BinTree, dan MainTree. Kelas MainTree
mempunyai 1 method, yaitu method main. Kelas BinTree mempunyai 12 method, dan
Kelas Node isinya untuk membuat objek dan konstruktor.
Perjalanan program dimulai dari kelas MainTree karena di dalamnya terdapat method
main. Tanpa method main, maka program tidak akan bisa dieksekusi. Method main ini
memiliki acces modifier public, sifatnya static dan tipe kembaliannya void (tanpa
kembalian). Pertama kali yang dilakukan di dalam method main adalah membuat objek
bernama pohon. Nama kelas tempat objek adalah BinTree dan konstruktornya juga
bernama BinTree. Nama kelas dan nama konstruktor harus sama. Kemudian new artinya
membuat baru.
Setelah pembuatan objek diikuti dengan pembuatan variabel bernama input dengan kelas
Scanner. Hal ini berfungsi untuk memasukkan data dari user. Agar perintah Scanner ini
dapat bekerja, maka perlu mengimpor impor java.util.Scanner yang diletakkan di bawah
nama package program ini, yaitu praktikum_sda11.
Masuk ke perulangan do yang isinya adalah perintah System.out.println untuk
menampilkan pilihan menu seperti ini:
Pilihan Menu:
1. Memasukkan data
2. Kunjungan preOrder
3. Kunjungan inOrder
4. Kunjungan postOrder
5. Menghapus semua data
6. Menghapus data
7. Mencari data
8. Mencari data dan direktorinya
9. Nilai terbesar
10. Nilai terkecil
11. Jumlah daun
12. Exit
Di dalam perulangan do, kemudian dideklarasikan variabel pil bertipe integer yang
nilainya sama dengan nilai input yang dimasukkan user. Entah itu angka 1, 2, 3, 4, atau
hingga 12. Lalu diikuti perintah switch(pil) yang isinya jika user memilih angka 1 (case
1) yang bertujuan untuk mengisikan data pada tree, maka akan dibawa ke perintah
System.out.print untuk menampilkan tulisan “Masukkan data: ”.
Kemudian dilanjutkan dengan pembuatan objek bernama in bertipe data integer. Nilai in
ini adalah inputan dari user. Mengakses method insert melalui objek pohon yang berada
di kelas BinTree, dengan parameter membuat Node baru/new Node berparameter in.
Di dalam kelas Node terdapat pendeklarasian variabel/atribut bernama right yang bertipe
data Node, bernama left bertipe data Node juga, dan bernama data bertipe data int.
Kemudian pembuatan konstruktor yaitu int dt. Didalamnya terdapat perintah this.data=dt
agar parameternya sama, yaitu dt. Nilai dt kemudian masuk ke object data.
Di kelas BinTree, di deklarasikan variabel root bertipe Node, variabel leaf bertipe Node
juga. Method pertama yang ada di kelas ini adalah isEmpty. Tujuannya untuk mengecek
apakah tree masih kosong atau sudah terisi. Method isEmpty mempunyai acces modifier
public dan tipe kembalian boolean, dan tidak mempunyai parameter. Isinya
mengembalian nilai root sama dengan null. Sehingga belum terisi apa-apa.
Method kedua adalah insert. Method ini mempunyai acces modifier public dan tipe
kembalian void (tanpa kembalian), berparameter input bertipe Node. Nilai input ini
nilainya sama dengan nilai in pada saat berada di case1 method main. Di dalam method
insert, yang dilakukan pertama adalah mendeklarasikan variabel flag bertipe data boolean
dan diberi nilai true. Kemudian Node temp yang nilainya sama dengan root.
Memasuki pernyataan if dengan kondisi jika tree kosong (dilakukan dengan memanggil
method isEmpty), maka nilai root sama dengan input dan dilanjutkan perintah
System.out.println untuk menampilkan tulisan “Berhasil masuk^^”. Jika sudah tidak
kosong lagi maka masuk ke pernyataan else.
Di dalam pernyataan else, nilai variabel temp sama dengan root. Lalu mendeklarasikan
variabel baru bernama parent, nilainya null. Dilanjutkan dengan perulangan while dengan
kondisi nilai temp tidak sama dengan null. Di dalam perulangan while, nilai parent
berubah menjadi temp. Kemudian masuk ke pernyataan if dengan kondisi jika nilai data
dari input lebih besar dari nilai data dari data, maka nilai temp sama dengan right dari
temp tersebut. Sekarang temp mengarah ke anak sebelah kanannya. Jika kondisi if
tersebut tidak memenuhi, maka masuk pernyataan else. Di dalam else ada if lagi dengan
kondisi jika nilai data dari input lebih kecil dari nilai data dari temp, maka nilai temp sama
dengan left dari temp tersebut. Sekarang temp mengarah ke anak sebelah kirinya. Jika
kondisi kedua tersebut masih juga terpenuhi, masuk else. Isinya adalah perintah
System.out.println untuk menampilkan tulisan “data sudah ada”. Kemudian nilai temp
menjadi null, dan nilai flag menjadi false. Lalu keluar dari perulangan.
Setelah looping selesai, masuk ke pernyataan if dengan kondisinya flag, artinya jika nilai
flag true. Di dalam if ada pernyataan if lagi (nested if) dengan kondisi jika data dari input
lebih besar dari datanya parent, maka nilai right (anak sebelah kanan)nya parent sama
dengan input. Sehingga input adalah anak kanannya parent. Dilanjutkan dengan perintah
System.out.println untuk menampilkan tulisan “Berhasil masuk^^”. Jika kondisi nested
loop tadi tidak memenuhi, maka masuk pernyataan else. Dan nilai left (anak sebelah
kiri)nya parent sama dengan input. Sehingga input adalah anak kirinya parent. Dan
dilanjutkan dengan perintah System.out.println untuk menampilkan tulisan “Berhasil
masuk^^”.
Misalnya pada awalnya tree masih kosong. Lalu ingin memasukkan data pertama yaitu 5.
Maka angka 5 ini disimpan dalam variabel in dan menjadi parameter saat memanggi
method insert. Dalam method insert, parameter input bernilai 5 (sama dengan in). nilai
flag=true, temp=root. Kondisi tree masih kosong, sehingga root sama dengan input.
Lalu memasukkan data kedua, yaitu 3. Flag=true, temp=root=5. Karena tree sudah tidak
kosong, maka yang dijalankan pernyataan else. Nilai parent=null. Masuk perulangan
while, parent=temp= 5. karena 3 kurang dari 5, maka temp=null (anak sebelah kiri). Dan
anak sebelah kiri dari parent sama dengan input.
Lalu menginputkan data ketiga, yaitu 4. Flag=true, temp=root=5. Karena tree sudah tidak
kosong, maka yang dijalankan pernyataan else. Nilai parent=null. Masuk perulangan
while, parent=temp= 5. karena 4 kurang dari 5, maka temp=3 (anak sebelah kiri).
parent=temp=3. Dan karena 4 lebih dari 3, maka anak sebelah kanan dari parent (3) sama
dengan input=4.
Begitu seterusnya memasukkan data 7, 6, 8, lalu 2.
Setelah proses pada method insert selesai, kembali lagi ke method main case 1. Perintah
selanjutnya adalah break yang berguna untuk keluar dari case, keluar dari switch, dan
kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 2, maka akan dibawa ke case 2. Tujuan dari case ini adalah
untuk menampilkan tree dengan kunjungan pre order.
Di dalam case 2, langsung dibawa ke pernyataan if dengan kondisi jika tree kosong
(dilakukan dengan memanggil method isEmpty melalui objek pohon), maka
menampilkan tulisan “Tree kosong” dengan perintah System.out.println. Jika tree tidak
kosong, maka masuk ke pernyataan else. Isinya adalah perintah System.out.println untuk
menampilkan tulisan “Kunjungan pre order:” . Dilanjutkan dengan memanggil method
preorder yang berada di kelas BinTree menggunakan objek pohon. Pemangilan method
tersebut menggunakan parameter nilai root yang diakses menggunakan objek pohon.
Memasuki method preOrder yang berada di kelas BinTree. Method ini mempunyai acces
modifier public, tipe kembalian void (tanpa kembalian), dan parameter temp bertipe
Node. Nilai temp ini sama nilainya dengan root. Di dalam method preOrder, masuk ke
pernyataan if dengan kondisi jika nilai temp tidak sama dengan null, maka menjalankan
pernyataan di dalam if. Yaitu perintah System.out.println untuk menampilkan nilai data
dari temp, dilanjutkan dengan spasi. Lalu secara rekursi memanggil preOrder dengan
parameter nilai anak sebelah kiri dari temp untuk ditampilkan nilainya. Jika nilai anak
sebelah kiri temp mencapai null, maka secara rekursi akan memanggil preOrder dengan
parameter nilai anak sebelah kanan dari temp untuk ditampilkan nilainya. Jika nilai anak
sebelah kanan temp mencapai null, maka keluar dari perintah if.
Sesuai dengan prinsip dari kunjungan pre order, urutan menampilkan data pada tree
adalah akar-kiri-kanan.
Pada method preOrder, nilai temp sama dengan root=4. Kondisi if memenuhi.
Menampilkan data dari temp=4. Lalu secara rekursif memanggil preOrder dengan anak
kiri dari temp yaitu 3. Nilai temp=3, lalu ditampilkan. Lalu secara rekursif memanggil
preOrder dengan anak kiri dari temp yaitu 1. Nilai temp=1, lalu ditampilkan. Lalu secara
rekursif memanggil preOrder dengan anak kiri dari temp yaitu null. maka sudah tidak
memenuhi maka tidak dilanjutkan rekursi ini.
Masuk ke perintah selanjutnya secara rekursif memanggil preOrder dengan anak kanan
dari temp yaitu 2. Nilai temp=2, lalu ditampilkan. Nilai temp sebelumnya anak kanannya
tidak null adalah 4. Maka secara rekursif memanggil preOrder dengan anak kanan dari
temp(4) yaitu 5. Nilai temp=5, lalu ditampilkan. Lalu secara rekursif memanggil preOrder
dengan anak kanan dari temp yaitu null. maka sudah tidak memenuhi maka tidak
dilanjutkan rekursi ini dan keluar dari pernyataan if.
Maka yang ditampilkan secara pre order adalah 4, 3, 2,1 ,5.
Misal input dari data yang dimasukkan adalah 4, 3, 1, 2, 5 secara berturut-turut.
Kemudian kembali ke case 2 pada method main. Masih ada perintah System.out.println
untuk menampilkan enter. Keluar dari pernyataan if-else, menuju perintah break yang
berguna untuk keluar dari case, keluar dari switch, dan kembali ke perulangan do, yaitu
menampilkan pilihan menu lagi.
Jika user menginputkan angka 3, maka akan dibawa ke case 3. Tujuan dari case ini adalah
untuk menampilkan tree dengan kunjungan in order.
Masuk case 3, langsung menuju pernyataan if dengan kondisi jika tree kosong (dilakukan
dengan memanggil method isEmpty melalui objek pohon), maka menjalankan perintah
System.out.println untuk menampilkan tulisan “Tree kosong”. Jika tree tidak kosong,
maka menjalankan pernyataan else. Isinya adalah perintah System.out.println untuk
menampilkan tulisan “Kunjungan in order:”. Dilanjutkan dengan memanggil method
inOrder yang berada di kelas BinTree melalui objek pohon. Pemanggilan method ini
menggunakan parameter nilai root yang diakses menggunakan objek pohon.
Method inOrder mempunyai acces modifier public, tipe kembalian void (tanpa
kembalian), dan parameter temp dengan tipe Node. Nilai dari temp sama nilainya dengan
nilai root. Di dalam method ini langsung dibawa ke pernyataan if dengan kondisi jika nilai
temp tidak sama dengan null, maka menjalankan pernyataan di dalamnya. Yaitu, secara
rekursi memanggil method inOrder itu sendiri dengan parameter anak sebelah kiri dari
temp. kemudian ditampilkan. Setelah nilai anak sebelah kiri mencapai null, maka
menampilkan nilai dari temp. Dilanjutkan dengan secara rekursi memanggil method
inOrder dengan parameter anak sebelah kanan dari temp. kemudian ditampilkan. Jika
anak sebelah kanan sudah mencapai null, maka keluar dari pernyataan if.
Sesuai dengan prinsip dari kunjungan in order, urutan menampilkan data pada tree adalah
–kiri-akar-kanan.
Pada method inOrder, nilai temp sama dengan root=4. Kondisi if memenuhi. Lalu secara
rekursif memanggil inOrder dengan anak kiri dari temp yaitu 3. Nilai temp=3. Lalu secara
rekursif memanggil inOrder dengan anak kiri dari temp yaitu 1. Nilai temp=1. Lalu secara
rekursif memanggil inOrder dengan anak kiri dari temp yaitu null. maka pemanggilan
tidak dilanjutkan.
Dilanjutkan dengan menampilkan data dari temp=1. Lalu secara rekursif memanggil
inOrder dengan anak kanan dari temp yaitu 2. Dilanjutkan dengan menampilkan data dari
temp sebelumnya=3. Lalu secara rekursif memanggil inOrder dengan anak kanan dari
temp yaitu null, maka tidak dilanjutkan. Dilanjutkan dengan menampilkan data dari temp
sebelumnya=4. Lalu secara rekursif memanggil inOrder dengan anak kanan dari temp
yaitu 5.
Kemudian kembali ke case 3 pada method main. Masih ada perintah System.out.println
untuk menampilkan enter. Keluar dari pernyataan if-else, menuju perintah break yang
berguna untuk keluar dari case, keluar dari switch, dan kembali ke perulangan do, yaitu
menampilkan pilihan menu lagi.
Jika user menginputkan angka 4, maka akan dibawa ke case 4. Tujuan dari case ini adalah
untuk menampilkan tree dengan kunjungan post order.
Di dalam case 4, langsung dibawa ke pernyataan if dengan kondisi jika tree kosong
(dilakukan dengan memanggil method isEmpty melalui objek pohon), maka
menampilkan tulisan “Tree kosong” dengan perintah System.out.println. Jika tree tidak
kosong, maka masuk ke pernyataan else. Isinya adalah perintah System.out.println untuk
menampilkan tulisan “Kunjungan post order:” . Dilanjutkan dengan memanggil method
postorder yang berada di kelas BinTree menggunakan objek pohon. Pemangilan method
tersebut menggunakan parameter nilai root yang diakses menggunakan objek pohon.
Memasuki method postOrder yang berada di kelas BinTree. Method ini mempunyai acces
modifier public, tipe kembalian void (tanpa kembalian), dan parameter temp bertipe
Node. Nilai temp ini sama nilainya dengan root. Di dalam method postOrder, masuk ke
pernyataan if dengan kondisi jika nilai temp tidak sama dengan null, maka menjalankan
pernyataan di dalam if. Yaitu perintah secara rekursi memanggil postOrder dengan
parameter nilai anak sebelah kiri dari temp untuk ditampilkan nilainya. Jika nilai anak
sebelah kiri temp mencapai null, maka secara rekursi akan memanggil preOrder dengan
parameter nilai anak sebelah kanan dari temp untuk ditampilkan nilainya. Jika nilai anak
sebelah kanan temp mencapai null, maka baru menampilkan nilai data dari temp.
Kemudian keluar dari pernyataan if.
Sesuai dengan prinsip dari kunjungan post order, urutan menampilkan data pada tree
adalah kiri-kanan-akar.
Pada method postOrder, nilai temp sama dengan root=4. Kondisi if memenuhi. Lalu
secara rekursif memanggil postOrder dengan anak kiri dari temp yaitu 3. Nilai temp=3.
Lalu secara rekursif memanggil postOrder dengan anak kiri dari temp yaitu 1. Nilai
temp=1. Lalu secara rekursif memanggil postOrder dengan anak kiri dari temp yaitu null.
maka pemanggilan tidak dilanjutkan.
Dilanjutkan secara rekursif memanggil postOrder dengan anak kanan dari temp yaitu 2.
Kemudian ditampilkan. Dilanjutkan dengan menampilkan nilai dari temp sebelumnya
yaitu 1. Dilanjutkan dengan menampilkan nilai dari temp sebelumnya yaitu 3. Dilanjutkan
secara rekursif memanggil postOrder dengan anak kanan dari temp yaitu null. maka tidak
dilanjutkan. Dilanjutkan secara rekursif memanggil postOrder dengan anak kanan dari
temp sebelumnya yaitu 5. Lalu ditampilkan. Dan terakhir menampilkan nilai dari temp
sebelumnya yaitu root bernilai 4.
Kemudian kembali ke case 4 pada method main. Masih ada perintah System.out.println
untuk menampilkan enter. Keluar dari pernyataan if-else, menuju perintah break yang
berguna untuk keluar dari case, keluar dari switch, dan kembali ke perulangan do, yaitu
menampilkan pilihan menu lagi.
Jika user menginputkan angka 5, maka akan dibawa ke case 5. Tujuan dari case ini adalah
untuk menghapus semua data pada tree.
Pada case 5, langsung dilakukan dengan pemanggilan method removeAll yang berada di
kelas BinTree melalui objek pohon.
Method removeAll mempunyai acces modifier public, tipe kembalian void, dan tanpa
parameter. Di dalamnya terdapat pernyataan if dengan kondisi jika tree kosong (dilakukan
dengan memanggil method isEmpty), maka menjalankan perintah System.out.println
untuk menampilkan tulisan “Data kosong”. Jika tree ada isinya, maka menjalankan
pernyataan else, yaitu nilai root sama dengan null. Maka secara otomatis semua data
menjadi terputus dan tree menjadi kosong. Lalu dilanjutkan dengan perintah
System.out.println untuk menampilkan tulisan “Data sudah kosong”.
Setelah proses pada method removeAll selesai, kemudian kembali ke case 5 pada method
main. Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari
switch, dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 6, maka akan dibawa ke case 6. Tujuan dari case ini adalah
untuk menghapus data tertentu pada tree.
Pada case 6, terdapat perintah System.out.print untuk menampilkan tulisan “Masukkan
data yang akan dihapus: ” tanpa enter. Kemudian diikuti oleh perintah untuk
menginputkan data yang akan dihapus oleh user melalui input.nextInt yang berarti data
yang dimasukkan berupa integer. Inputan tersebut disimpan dalam variabel in bertipe data
int. Kemudian dilanjutkan oleh pemanggilan method remove berparameter in, melalui
objek pohon.
Method remove ini mempunyai acces modifier public, tipe kembalian void (tanpa
kembalian), dan parameter data bertipe int. Di dalam method ini terdapat pendeklarasian
variabel temp dengan tipe Node, diberi nilai sama dengan root. Lalu temp1 tipenya Node,
nilainya sama dengan null.
Masuk pernyataan if dengan kondisi jika tree kosong (dilakukan dengan memanggil
method isEmpty), maka menjalankan perintah System.out.println untuk menmapilkan
tulisan “Data kosong, tak ada yang dihapus”. Jika kondisi tersebut tidak memenuhi, maka
masuk pernyataan while dengan kondisi nilai temp tidak sama dengan null. isi pernyataan
while adalah pernyataan if dengan kondisi jika data dari temp kurang dari variabel data,
maka nilai temp1 sama dengan temp. dan nilai temp sama dengan anak kanan dari temp
tersebut. Jika kondisi tidak memenuhi, maka masuk pernyataan else. Isinya adalah
pernyataan if dengan kondisi jika nilai data dari temp lebih dari variabel data, maka nilai
temp1 sama dengan temp, dan nilai dari temp sama dengan anak kiri dari temp tersebut.
Jika kondisi masih belum memenuhi, maka masuk pernyataan else lagi. isinya adalah
pernyataan if dengan kondisi jika anak kanan dari temp sama dengan null, dan anak kiri
dari temp sama dengan null, maka nilai temp sama dengan null. jika kondisi masih tetepa
tidak memenuhi, maka masuk pernyataan else yang didalamnya terdapat pernyataan if.
Kondisinya, jika anak kanan dari temp sama dengan null dan anak kiri dari temp tidak
sama dengan null, maka menjalankan pernyataan di dalamnya yang ada if dengan kondisi
jika data dari temp1 lebih dari data dari temp, maka anak kiri temp1 sama dengan anak
kiri temp. jika kondisi tidak memenui,maka anak kanan temp1 sama dengan anak kiri dari
temp. keluar dari pernyataan if, nilai temp sama dengan null.
Dilanjutkan dengan pernyataan else jika kondisi if tidak memenuhi, isinya terdapat if lagi
dengan kondisi jika anak kanan dari temp tidak sama dengan null dan anak kiri dari temp
sama dengan null, maka menjalankan isi dari if. Isinya adalah pernyataan if lagi dengan
konsidi jika data dari temp1 lebih dari data dari temp, maka anak kiri dari temp1 sama
dengan anak kanan dari temp. jika kondisi tidak memenuhi, maka anak kanan dari temp1
sama dengan anak kanan dari temp. Keluar dari pernyataan if, nilai temp sama dengan
null.
Jika kondisi if tadi belum juga memenuhi, maka masuk else. Di dalamnya ada if lagi.
kondisinya jika anak kanan dari temp tidak sama dengan null dan anak kiri sari temp tidka
sama dengan null, maka menjalankan pernyataan di dalmnya. Yaitu, mendeklarasikan
variabel a dengan tipe data integer, diberikan nilai dengan cara melakukan pemanggilan
tergadap method findMax berparameter anak kiri dari temp. kemudian dilanjutkan dengan
memanggil method remove berparameter a. Kemudian data dari temp sama dengan a.
Setelah itu, keluar dari semua if, menampilkan tulisan “Data berhasil dihapus”
Setelah proses pada method remove selesai, kemudian kembali ke case 6 pada method
main. Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari
switch, dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 7, maka akan dibawa ke case 7. Tujuan dari case ini adalah
untuk mencari data tertentu pada tree.
Pada case 7, menuju perintah System.out.print untuk menampilkan tulisan “Data yang
akan dicari: ” tanpa enter. Kemudian diikuti oleh perintah untuk menginputkan data yang
akan dicari oleh user melalui input.nextInt yang berarti data yang dimasukkan berupa
integer. Inputan tersebut disimpan dalam variabel in bertipe data int. Kemudian
dilanjutkan oleh pemanggilan method find berparameter in, melalui objek pohon.
Pada method find, mempunyai acces modifier public, tipe kembalian void (tanpa
kembalian), dan variabel cari bertipe data int. Nilai variabel cari sama nilainya dengan
yang diinputkan user, yaitu nilai variabel in. Di dalam method find, dideklarasikan
variabel temp dengan tipe Node, diberi nilai sama dengan root. Variabel ketemu bertipe
data boolean diberi nilai false.
Kemudian masuk ke pernyataan if dengan kondisi jika tree kosong (dilakukan dengan
memanggil method isEmpty), maka menjalankan perintah System.out.println untuk
menampilkan tulisan “Tree kosong”. Jika tidak kosong, maka menjalankan pernyatan
else. Isinya adalah perulangan while dengan kondisi nilai temp tidak sama dengan null.
Isi dari pernyataan while adalah pernyataan if dengan kondisi jika nilai dari cari nilainya
lebih dari data dari temp, maka nilai temp sama dengan anak sebelah kanan dari temp
tersebut. Jika kondisi if itu tidak memenuhi, masuk ke else. Di dalam else juga terdapat
pernyataan if dengan kondisi jika nilai cari nilainya kurang dari data dari temp, maka nilai
temp sama dengan anak sebelah kiri dari temp tersebut. Jika kondisi if masih tetap tidak
memenuhi, masuk ke else lagi yang lebih dalam. Disana juga terdapat pernyataan if
dengan kondisi jika nilai dari cari sama dengan data dari temp, maka menjalankan
perintah System.out.println untuk menampilkan tulisan “Data” dilanjutkan penulisan nilai
data dari temp, dilanjutkan lagi dengan tulisan “ ditemukan”. Kemudian nilai variabel
ketemu yang tadinya false menjadi true. Dan menuju perintah break untuk keluar dari
looping.
Jika sampai pada pernyataan if yang paling dalam nilai dari cari tidak sama dengan nilai
dari temp, maka masuk pernyataan if jika kondisinya false, maka menampilkan tulisan
“Data tidak ditemukan”.
Nilai temp=root=4, cari=2, ketemu=false. Masuk pernyataan while, memenuhi. Nilai
cari(2)<data temp(4).
Nilai root=4, temp=3, cari=2, ketemu=false. Masuk pernyataan while, memenuhi. Nilai
cari(2)<data temp(3).
Nilai root=4, temp=1, cari=2, ketemu=false. Masuk pernyataan while, memenuhi. Nilai
cari(2)>data temp(1).
Nilai root=4, temp=1, cari=2, ketemu=false. Masuk pernyataan while, memenuhi. Nilai
cari(2)=data temp(2). Maka data telah ditemukan.
Setelah proses pada method find selesai, kemudian kembali ke case 7 pada method main.
Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari switch,
dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 8, maka akan dibawa ke case 8. Tujuan dari case ini adalah
untuk mencari data tertentu pada tree dan menampilkan data mana saja yang dilewati
selama pencarian.
Pada case 8, menuju perintah System.out.print untuk menampilkan tulisan “Data yang
akan dicari: ” tanpa enter. Kemudian diikuti oleh perintah untuk menginputkan data yang
akan dicari oleh user melalui input.nextInt yang berarti data yang dimasukkan berupa
integer. Inputan tersebut disimpan dalam variabel in bertipe data int. Kemudian
dilanjutkan oleh pemanggilan method findDir berparameter in, melalui objek pohon.
Method findDir mempunyai acces modifier public, tipe kembalian void (tanpa
kembalian), dan parameter cari dengan tipe data int. Dalam method ini dilakukan
pendeklarasian variabel ketemu dengan tipe data boolean dan diberi nilai false. Variabel
hasil dengan tipe data String diberi isi berupa “”. Kemudian membuat Node baru dengan
nama temp yang nilainya sama dengan root. Dilanjutkan dengan perulangan while dengan
kondisi nilai temp tidak sama dengan null. Isinya adalah nilai dari variabel hasil sama
dengan nilai hasil ditambah tanda garis miring kemudian diikuti oleh nilai data dari temp.
Masuk ke pernyataan if dengan kondisi jika data dari temp kurang dari nilai dari cari,
maka nilai temp sama dengan anak sebelah kiri dari temp. Jika kondisi tidak memenuhi,
masuk ke pernyataan else yang di dalamnya terdapat pernyataan if lagi dengan kondisi
jika nilai data dari temp kurang dari nilainya cari, maka nilai dari temp sama dengan anak
sebelah kanan dari temp tersebut. Jika kondisi masih belum memenuhi, maka masuk else
yang paling dalam. Isinya adalah nilai variabel ketemu yang tadinya bernilai false,
sekarang menjadi true. Kemudian diikuti perintah break untuk keluar dari looping.
Jika sampai pada pernyataan if yang paling dalam nilai dari cari tidak sama dengan nilai
dari temp, maka masuk pernyataan if jika kondisinya tidak ketemu, maka menampilkan
tulisan “Data tidak ditemukan”.
Analisa pada method ini sama prinsipnya dengan method find, hanya saja ketika melewati
Node-Node, menampilkan isinya.
Setelah proses pada method findDir selesai, kemudian kembali ke case 8 pada method
main. Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari
switch, dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 9, maka akan dibawa ke case 9. Tujuan dari case ini adalah
untuk mencari data yang nilainya paling besar.
Pada case 9, langsung masuk ke perintah System.out.println untuk menampilkan tulisan
“Data terbesar: ” dilanjutkan dengan pemanggilan method findMax yang berada di kelas
BinTree melalui objek pohon. Pemanggilan method ini berparameter nilai root yang
diakses menggunakan objek pohon.
Method findMax mempunyai acces modifier public, tipe kembalian int, dan parameter
temp bertipe Node. Isi dari method ini adalah pernyataan if dengan kondisi jika nilai temp
tidak sama dengan null, maka menjalankan pernyataan di dalamnya. Yaitu perulangan
while dengan kondisi anak sebelah kanan dari temp tidak sama dengan null. Isi dari
perulangan ini adalah temp sama dengan anak sebelah kanan dari temp. Keluar dari
pernyataan if, maka method ini memberikan nilai kembalian berupa nilai data dari temp.
Nilai temp=root=4. Karena anak kanannya bukan null, maka temp=5. Anak kanannya
null. sehingga nilai temp terakhir adalah 5. Sehingga nilai maksimalnya adalah 5.
Setelah proses pada method findMax selesai, kemudian kembali ke case 9 pada method
main. Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari
switch, dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 10, maka akan dibawa ke case 10. Tujuan dari case ini
adalah untuk mencari data yang nilainya paling kecil.
Pada case 10, langsung masuk ke perintah System.out.println untuk menampilkan tulisan
“Data terkecil: ” dilanjutkan dengan pemanggilan method findMin yang berada di kelas
BinTree melalui objek pohon. Pemanggilan method ini berparameter nilai root yang
diakses menggunakan objek pohon.
Method findMin mempunyai acces modifier public, tipe kembalian int, dan parameter
temp bertipe Node. Isi dari method ini adalah pernyataan if dengan kondisi jika nilai temp
tidak sama dengan null, maka menjalankan pernyataan di dalamnya. Yaitu perulangan
while dengan kondisi anak sebelah kiri dari temp tidak sama dengan null. Isi dari
perulangan ini adalah temp sama dengan anak sebelah kiri dari temp. Keluar dari
pernyataan if, maka method ini memberikan nilai kembalian berupa nilai data dari temp.
Nilai temp=root=4. Karena anak kirinya bukan null, maka temp=3. Anak kirinya bukan
null lagi, maka temp=1. Anak kirinya null. sehingga nilai temp terakhir adalah 1.
Sehingga nilai minimalnya adalah 1.
Setelah proses pada method findMin selesai, kemudian kembali ke case 10 pada method
main. Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari
switch, dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 11, maka akan dibawa ke case 11. Tujuan dari case ini
adalah untuk menampilkan jumlah daun pada tree.
Pada case 11 ini, dibawa ke perintah System.out.println untuk menampilkan tulisan
“Jumlah daun: ” dilanjutkan dengan memanggil method getLeaf yang berada di kelas
BinTree, tanpa parameter, melalui objek pohon.
Method getLeaf mempunyai acces modifier public, tipe kembalian int, dan tanpa
parameter. Didalam method ini diberikan nilai kembalian dengan memanggil method
getLeafCount berparameter root.
Method getLeafCount mempunyai acces modifier private, tipe kembalian int, dan
parameter data bertipe Node. Di dalam method ini, masuk pernyataan if dengan kondisi
jika data sama dengan null, maka mengembalikan nilai 0. Jika kondisi tersebut tidak
memenuhi, maka menjalankan pernyataan else.
Isi dari pernyataan else adalah pernyataan if dengan kondisi jika anak sebelah kiri dari
data sama dengan null dan anak sebelah kanan dari data sama dengan null juga, maka
mengembalikan nilai 1. Jika kondisi if ini belum juga memenuhi, maka masuk pernyataan
else yang isinya memberikan nilai kembalian secara rekursi memanggil method
getLeafCount dengan parameter anak sebelah kiri dari data, dan ditambah dengan secara
rekursi memanggil method getLeafCount dengan parameter anak sebelah kanan dari data.
Maka, untuk mengetahui jumlah daun pada method getLeafCount pernyataan if
kondisinya tidak memenuhi karena data=root=4, bukan null. Masuk ke else. Anak sebelah
kiri dari 4 bukan null. tidak memenuhi, masuk ke else. Mengembalikan nilai rekursi
memanggil method itu sendiri dengan parameter anak sebelah kiri dari data (3) dan
ditambah hasil dari rekursi memanggil method itu sendiri dengan parameter anak sebelah
kanan dari data (5). Karena 3 masih memiliki anak maka menelusuri kembali anaknya
apakah mempunyai anak atau tidak. Sedangkan 5 sudah tidak mempunyai anak (anak
sebelah kanan dan kirinya null), maka mengembalikan nilai 1.
Sedangkan anak dari 3 adalah 1. 1 masih mempunyai anak, yaitu 2 (anak sebelah kanan).
2 sudah tidak mempunyai anak sehinggan mengembalikan nilai 1. Sehingga method ini
memberikan nilai kembalian 1+1 sama dengan 2. Maka jumlah daun pada tree tersebut
adalah 2.
Setelah proses pada method getLeaf selesai, kemudian kembali ke case 11 pada method
main. Kemudian menuju perintah break yang berguna untuk keluar dari case, keluar dari
switch, dan kembali ke perulangan do, yaitu menampilkan pilihan menu lagi.
Jika user menginputkan angka 12, maka akan dibawa ke case 12. Tujuan dari case ini
adalah untuk memberhentikan program yang sedang berjalan.
Dibawa ke perintah System.out.println untuk menampilkan tulisan: Anda telah keluar.
Kemudian masuk ke perintah System.exit(0) untuk memberhentikan program (program
telah selesai berjalan).
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
AVL TREE
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 22 MEI 2014
1. SOURCE CODE
package AVLTree;
import java.util.Scanner;
public class AVLTree {
class AVLNode {
AVLNode(Comparable theElement) {
this(theElement, null, null);
}
AVLNode(Comparable theElement, AVLNode lt, AVLNode
rt) {
element = theElement;
left = lt;
right = rt;
height = 0;
}
Comparable element;
AVLNode left;
AVLNode right;
int height;
}
public AVLTree() {
root = null;
}
public void insert(Comparable x) {
root = insert(x, root);
}
public Comparable find(Comparable x) {
return elementAt(find(x, root));
}
public void remove(Comparable x) {
root = remove(x, root);
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public void printTree() {
if (isEmpty()) {
System.out.println("Pohon kosong");
} else {
printTree(root);
}
}
private Comparable elementAt(AVLNode t) {
return t == null ? null : t.element;
}
private AVLNode insert(Comparable x, AVLNode t) {
if (t == null) {
t = new AVLNode(x, null, null);
} else if (x.compareTo(t.element) < 0) {
t.left = insert(x, t.left);
if (height(t.left) - height(t.right) == 2) {
if (x.compareTo(t.left.element) < 0) {
t = rotateWithLeftChild(t);
} else {
t = doubleWithLeftChild(t);
}
}
} else if (x.compareTo(t.element) > 0) {
t.right = insert(x, t.right);
if (height(t.right) - height(t.left) == 2) {
if (x.compareTo(t.right.element) > 0) {
t = rotateWithRightChild(t);
} else {
t = doubleWithRightChild(t);
}
}
} else {
System.out.println("Data sudah ada");
}
t.height = max(height(t.left), height(t.right)) +
1;
return t;
}
private AVLNode find(Comparable x, AVLNode t) {
while (t != null) {
if (x.compareTo(t.element) < 0) {
t = t.left;
} else if (x.compareTo(t.element) > 0) {
t = t.right;
} else {
return t;
}
}
return null;
}
private AVLNode remove(Comparable x, AVLNode t) {
if (t == null) {
System.out.println("Data tidak terdapat di
pohon");
return t;
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.left = remove(x, t.left);
} else if (compareResult > 0) {
t.right = remove(x, t.right);
} else if (t.left != null && t.right != null) {
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
} else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
private void printTree(AVLNode t) {
if (t != null) {
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
private AVLNode findMin(AVLNode t) {
if (t == null) {
return null;
} else if (t.left == null) {
return t;
}
return findMin(t.left);
}
private static int height(AVLNode t) {
return t == null ? -1 : t.height;
}
private static int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
private static AVLNode rotateWithLeftChild(AVLNode k2)
{
System.out.println("Rotasi tunggal");
AVLNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max(height(k2.left), height(k2.right))
+ 1;
k1.height = max(height(k1.left), k2.height) + 1;
return k1;
}
private static AVLNode rotateWithRightChild(AVLNode k1)
{
System.out.println("Rotasi tunggal");
AVLNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max(height(k1.left), height(k1.right))
+ 1;
k2.height = max(height(k2.right), k1.height) + 1;
return k2;
}
private static AVLNode doubleWithLeftChild(AVLNode k3)
{
System.out.println("Rotasi ganda, terdiri dari:");
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
private static AVLNode doubleWithRightChild(AVLNode k1)
{
System.out.println("Rotasi ganda, terdiri dari:");
k1.right = rotateWithLeftChild(k1.right);
return rotateWithRightChild(k1);
}
private AVLNode root;
public static void main(String[] args) {
AVLTree t = new AVLTree();
System.out.println("Pohon AVL\nMenu");
System.out.println("1. Masukkan data\n2. Hapus
data");
System.out.println("3. Cetak data(inOrder)\n4.
Keluar\n");
while (true) {
System.out.print("Pilihan Anda: ");
Scanner scn = new Scanner(System.in);
int ch = scn.nextInt();
int num;
switch (ch) {
case 1:
System.out.print("Masukkan data yang
ingin dimasukkan: ");
num = scn.nextInt();
t.insert(num);
break;
case 2:
System.out.print("Masukkan data yang
akan dihapus: ");
num = scn.nextInt();
t.remove(num);
break;
case 3:
t.printTree();
break;
case 4:
return;
default:
return;
}
}
}
}
2. ANALISA
Program ini merupakan program implementasi dari AVL Tree. Terdapat 3 menu
untuk mengakses AVL Tree, yaitu memasukkan data, menghapus data, dan menampilkan
data. Dalam pengaksesan 3 menu di atas, program akan melibatkan banyak metode
seperti insert, single rotation, double rotation, height, makeEmpty, isEmpty, printTree,
max, dan find. Program ini menggunakan list karena diakses dengan node.
Memasukkan data
Pertama-tama kita memasukkan angka. Anggap angka itu menjadi variabel x.
Kemudian kita buat node baru bernama t yang akan dianggap sebagai root. Periksa dan
uji apakah node t (root) null atau tidak. Jika root-nya masih null, maka x akan dijadikan
sebagai root. Kemudian diuji lagi, jika x lebih kecil dari root, maka x menjadi berada di
sebelah kiri root dan menjadi bagian dari t.left. Kemudian diuji lagi, jika height kiri dan
height kanan sama dengan 2, maka akan diuji lagi namun dengan syarat yang berbeda.
Jika x lebih kecil dari t.left maka masuk ke method rotasi tunggal. Jika x lebih besar dari
t.left maka masuk ke method rotasi ganda. Di dalam method insert, rotasi tunggal
digunakan untuk membuat variabel x menjadi berada di sebelah kiri dari t.left. Sedangkan
untuk rotasi ganda digunakan untuk membuat variabel x berada di sebelah kanan t.left.
Input: 15 root
Input: 90 t.right
Input: 20 double rotation
Input: 75 anak kiri t.right
Input: 25 single rotation
Input: 65 double rotation
Input: 35 jadi di sebelah kiri root
Jika di print :
15
20
25
35
65
75
90
Menghapus data
Pertama-tama kita memasukkan data yang ingin dihapus. Anggap angka itu
menjadi variabel x. Kemudian kita buat node baru bernama t yang akan dianggap sebagai
root. Uji apakah root null atau tidak. Jika root masih null, maka akan dicetak ("Data tidak
terdapat di pohon"). Jika root tidak null maka selanjutnya pengujian akan dilakukan
untuk menentukan apakah x berada di kiri root atau di kanan root. Jika di kiri root, maka
pertama x yang sudah ada di pohon akan dihapus, kemudian setelah itu pohon akan diuji
apakah sudah balance. Jika terjadi ketidakseimbangan dalam pohon maka akan diproses
lagi dengan cara menggunakan rotasi tunggal dan rotasi ganda untuk menyeimbangkan-
nya. Begitu pula jika x di sebelah kanan root. Hal ini akan terus diulangi hingga pohon
seimbang.
Hapus: 15 karena lebih kecil dari root, maka yang ingin dihapus ada di sebelah
kiri root
Hapus : 10 karena lebih kecil dari root, maka yang ingin di hapus ada di sebelah
kiri root
Hapus: 60 karena lebih besar dari root, maka yang akan dihapus terletak di
sebelah kanan dari root alias bagian 2 dari t.right
Mencetak data
Yang kita cetak adalah node t atau yang dianggap sebagai root. Karena
mencetaknya secara inOrder (kiri-akar-kanan). Jadi yang dicetak pertama adalah t.left
kemudian t.element kemudian yang dicetak terakhir adalah t.right.
3. SCREEN SHOT
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
RED BLACK TREE
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 3 JUNI 2014
1. SOURCE CODE
a. Main package RBT;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
RBTree rbt = new RBTree(Integer.MIN_VALUE);
char ch;
System.out.println("RED BLACK TREE");
do {
System.out.println("\nRed Black Tree Menu");
System.out.println("1. Insert");
System.out.println("2. Search");
System.out.println("3. Hitung Jumlah Node");
System.out.println("4. Check Empty");
System.out.println("5. Clear Tree");
System.out.println("6. Tampilkan pre-order");
System.out.println("7. Tampilkan in-order");
System.out.println("8. Tampilkan post-order");
System.out.print("Masukkan pilihan Anda: ");
int choice = scan.nextInt();
System.out.print("\n");
switch (choice) {
case 1:
System.out.print("Masukkan nilai yang akan
disisipkan: ");
rbt.insert(scan.nextInt());
break;
case 2:
System.out.print("Masukkan nilai yang akan
dicari: ");
System.out.println("Hasil: " +
rbt.search(scan.nextInt()));
break;
case 3:
System.out.println("Nodes: " +
rbt.countNodes());
break;
case 4:
System.out.println("Empty status: " +
rbt.isEmpty());
break;
case 5:
System.out.println("RBT telah kosong");
rbt.makeEmpty();
break;
case 6:
System.out.print("Pre-order: ");
rbt.preorder();
break;
case 7:
System.out.print("In-order: ");
rbt.inorder();
break;
case 8:
System.out.print("Post-order: ");
rbt.postorder();
break;
default:
System.out.println("Maaf, pilihan Anda
salah!\n ");
break;
}
} while (true);
}
}
b. Tree package RBT;
public class RBTree {
private RedBlackNode current;
private RedBlackNode parent;
private RedBlackNode grand;
private RedBlackNode great;
private RedBlackNode header;
private static RedBlackNode nullNode;
static {
nullNode = new RedBlackNode(0);
nullNode.left = nullNode;
nullNode.right = nullNode;
}
static final int BLACK = 1;
static final int RED = 0;
public RBTree(int negInf) {
header = new RedBlackNode(negInf);
header.left = nullNode;
header.right = nullNode;
}
public boolean isEmpty() {
return header.right == nullNode;
}
public void makeEmpty() {
header.right = nullNode;
}
public void insert(int item) {
current = parent = grand = header;
nullNode.element = item;
while (current.element != item) {
great = grand;
grand = parent;
parent = current;
current = item < current.element ? current.left :
current.right;
if (current.left.color == RED && current.right.color
== RED) {
handleReorient(item);
}
}
if (current != nullNode) {
return;
}
current = new RedBlackNode(item, nullNode, nullNode);
if (item < parent.element) {
parent.left = current;
} else {
parent.right = current;
}
handleReorient(item);
}
private void handleReorient(int item) {
current.color = RED;
current.left.color = BLACK;
current.right.color = BLACK;
if (parent.color == RED) {
grand.color = RED;
if (item < grand.element != item < parent.element) {
parent = rotate(item, grand); // Start dbl
rotate
}
current = rotate(item, great);
current.color = BLACK;
}
header.right.color = BLACK;
}
private RedBlackNode rotate(int item, RedBlackNode parent) {
if (item < parent.element) {
return parent.left = item < parent.left.element ?
rotateWithLeftChild(parent.left) :
rotateWithRightChild(parent.left);
} else {
return parent.right = item < parent.right.element ?
rotateWithLeftChild(parent.right) :
rotateWithRightChild(parent.right);
}
}
private RedBlackNode rotateWithLeftChild(RedBlackNode k2) {
RedBlackNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
private RedBlackNode rotateWithRightChild(RedBlackNode k1) {
RedBlackNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
public int countNodes() {
return countNodes(header.right);
}
private int countNodes(RedBlackNode r) {
if (r == nullNode) {
return 0;
} else {
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
public boolean search(int val) {
return search(header.right, val);
}
private boolean search(RedBlackNode r, int val) {
boolean found = false;
while ((r != nullNode) && !found) {
int rval = r.element;
if (val < rval) {
r = r.left;
} else if (val > rval) {
r = r.right;
} else {
found = true;
break;
}
found = search(r, val);
}
return found;
}
public void inorder() {
inorder(header.right);
}
private void inorder(RedBlackNode r) {
if (r != nullNode) {
inorder(r.left);
char c = 'B';
if (r.color == 0) {
c = 'R';
}
System.out.print(r.element + "" + c + " ");
inorder(r.right);
}
}
public void preorder() {
preorder(header.right);
}
private void preorder(RedBlackNode r) {
if (r != nullNode) {
char c = 'B';
if (r.color == 0) {
c = 'R';
}
System.out.print(r.element + "" + c + " ");
preorder(r.left);
preorder(r.right);
}
}
public void postorder() {
postorder(header.right);
}
private void postorder(RedBlackNode r) {
if (r != nullNode) {
postorder(r.left);
postorder(r.right);
char c = 'B';
if (r.color == 0) {
c = 'R';
}
System.out.print(r.element + "" + c + " ");
}
}
}
c. Node package RBT;
public class RedBlackNode {
RedBlackNode left, right;
int element;
int color;
public RedBlackNode(int theElement) {
this(theElement, null, null);
}
public RedBlackNode(int theElement, RedBlackNode lt,
RedBlackNode rt) {
left = lt;
right = rt;
element = theElement;
color = 1;
}
}
2. ANALISA
Red-black tree adalah binary search tree yang memenuhi properti sebagai berikut:
Setiap node adalah red atau black
Node root adalah black
Setiap daun adalah black
Semua anak dari node red adalah black
Setiap jalur (path) dari sebuah node ke daun berisi node black yang jumlahnya sama
Insertion
Aturan insert pada Red Black Tree:
1. Setiap node baru yang disisipkan ke dalam tree akan diberi warna merah.
2. Jika kita memberi warna hitam pada node baru yang masuk, maka jumlah node dari
root akan berbeda.
3. Jika kita memasukkan node baru yang berwarna merah ke dalam parent yang
berwarna hitam tidak akan menjadi masalah, yang menjadi masalah adalah jika kita
menyisipkan node baru ke dalam parent yang berwarna merah
4. Jika parent berwarna merah kita akan membuat dua node merah yang berurutan,
jadi kita harus melakukan rotasi atau pewarnaan ulang.
5. Hal penting yang harus diingat adalah node yang tidak mempunyai daun harus
berwarna hitam.
Jika kita memasukkan angka dalam red black tree yang masih kosong, maka node
akan otomatis berwarna hitam dan digunakan sebagai root. Pada praktikum kali ini, kita
diperintahkan untuk memasukkan angka dari 1-50 serta dari 50 hingga 1.
Saat terjadi ketidakseimbangan pada penyisipan angka 1-50 ataupun 50-1, maka
nanti red black akan menggunakan 3 cara untuk menyeimbangkannya kembali.
Cara-canya adalah sebagai berikut:
1. Single rotation
Single Rotation terjadi jika sebuah parent memiliki anak satu buah kanan atau
kiri, dan anaknya tersebut memiliki anak lagi dan posisi kanan/kirinya sama dengan
posisi dari parent ke parent-nya.
Bentuk single rotation seperti berikut ini:
2. Double rotation
Double Rotation terjadi jika sebuah parent memiliki anak satu buah kanan
atau kiri, dan anaknya tersebut memiliki anak lagi dan posisi kanan/kirinya
berlainan dengan posisi dari parent ke parent-nya.
3. Flip colour
Flip colour adalah suatu method di red black tree yang digunakan untuk
mengganti warna saat terjadi ketidakseimbangan warna dalam tree.
Kasus penyeimbangan pertama
Untuk penyisipan 1-50
1. Masukkan angka 1, maka 1 menjadi root dan berwarna hitam
2. Masukkan angka 2, maka 2 akan berada di sebelah kanan 1 berwarna merah
3. Masukkan angka 3, maka 3 berada di sebelah kanan 2 karena lebih besar dari 2,
dan berwarna merah. Karena terjadi ketidakseimbangan, maka dilakukan single
rotation dan yang menjadikan 2 menjadi root, kemudian 1 menjadi anak kiri serta
3 menjadi anak kanan. Kemudian dilakukan flip colour. Dua berubah hitam, 1 dan
3 berubah merah.
Untuk penyisipan 50-1
1. Masukkan angka 50, maka 50 menjadi root dan berwarna hitam
2. Masukkan angka 49, maka 49 akan berada di sebelah kiri 50 berwarna merah
3. Masukkan angka 48, maka 48 berada di sebelah kiri 49 karena lebih kecil dari 49,
dan berwarna merah. Karena terjadi ketidakseimbangan, maka dilakukan single
rotation dan yang menjadikan 49 menjadi root, kemudian 50 menjadi anak kanan
serta 48 menjadi anak kiri. Kemudian dilakukan flip colour. 49 berubah hitam, 50
dan 48 berubah merah.
Hasil:
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
SORTING
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 3 JUNI 2014
1. SOURCE CODE
a. BUBBLE SORT public void bubbleSort(int n) {
int[] arr = generateRandom(n);
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
for (int x = 0; x < n; x++) {
System.out.print(arr[x] + " ");
}
}
b. SELECTION SORT public void selectionSort(int n) {
int i, j, minIndex, tmp;
int[] arr = generateRandom(n);
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
for (int x = 0; x < n; x++) {
System.out.print(arr[x] + " ");
}
}
c. INSERTION SORT public void insertionSort(int n) {
int i, j, newValue;
int[] arr = generateRandom(n);
for (i = 1; i < arr.length; i++) {
newValue = arr[i];
j = i;
while (j > 0 && arr[j - 1] > newValue) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = newValue;
}
for (int x = 0; x < n; x++) {
System.out.print(arr[x] + " ");
}
}
2. ANALISA
Sorting atau pengurutan data adalah proses yang sering harus dilakukan dalam
pengolahan data. Sort dalam hal ini diartikan mengurutkan data yang berada dalam suatu
tempat penyimpanan, dengan urutan tertentu baik urut menaik (ascending) dari nilai
terkecil sampai dengan nilai terbesar, atau urut menurun (descending) dari nilai terbesar
sampai dengan nilai terkecil. Sorting adalah proses pengurutan. Berikut ini beberapa
metode sorting yaitu:
1. BUBBLE SORT
Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara
berulang kali membandingkan dua elemen data pada suatu saat dan menukar
elemen data yang urutannya salah. Ide dari bubble sort adalah gelembung air yang
akan “mengapung” untuk tabel yang terurut menaik (ascending). Elemen bernilai
kecil akan “diapungkan” (ke indeks terkecil), artinya diangkat ke “atas” (indeks
terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan
cara membandingkan elemen-elemen data satu sama lain, maka bubble sort
termasuk ke dalam jenis algoritma comparison-based sorting.
2. SELECTION SORT
Algoritma selection sort memilih elemen maksimum/minimum array, lalu
menem-patkan elemen maksimum/minimum itu pada awal atau akhir array
(tergantung pada urutannya ascending/descending). Selanjutnya elemen tersebut
tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus
membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-
based sorting. Seperti pada algoritma bubble sort, proses memilih nilai
maksimum/minimum dilakukan pada setiap pass. Jika array berukuran N, maka
jumlah pass adalah N-1.
3. INSERTION SORT
Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua
elemen data pertama, mengurutkannya, kemudian mengecek elemen data
berikutnya satu persatu dan membandingkannya dengan elemen data yang telah
diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen
data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based
sort. Ide dasar dari algoritma insertion sort ini adalah mencari tempat yang “tepat”
untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian
menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya.
Proses dilakukan sebanyak N-1 tahapan (dalam sorting disebut sebagai “pass“),
dengan indeks dimulai dari 0.Proses pengurutan dengan menggunakan algoritma
insertion sort dilakukan dengan cara membandingkan data ke-i (di mana i dimulai
dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan
data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi
yang seharusnya.
PEMBAHASAN
1. Bubble sort (Metode Gelembung)
Cara kerja bubble sort adalah dengan berulang-ulang melakukan traversal
(proses looping) terhadap elemen-elemen struktur data yang belum diurutkan. Di
dalam traversal tersebut, nilai dari dua elemen struktur data dibandingkan. Jika
ternyata urutannya tidak sesuai dengan “pesanan”, maka dilakukan pertukaran
(swap). Algoritma sorting ini disebut juga dengan comparison sort dikarenakan
hanya mengandalkan perbandingan nilai elemen untuk mengoperasikan
elemennya. Algoritma bubble sort dapat diringkas sebagai berikut, jika N adalah
panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …,
TN-1, TN, maka:
a. Lakukan traversal untuk membandingkan dua elemen berdekatan. Traversal
ini dilakukan dari belakang.
b. Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak,
lanjutkan ke proses traversal berikutnya sampai bertemu dengan bagian
struktur data yang telah diurutkan.
c. Ulangi langkah di atas untuk struktur data yang tersisa.
2. Selection Sort (Metode Seleksi)
Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan
penyeleksian elemen struktur data. Untuk sorting ascending (menaik), elemen yang
paling kecil di antara elemen-elemen yang belum urut, disimpan indeksnya,
kemudian dilakukan pertukaran nilai elemen dengan indeks yang disimpan tersebut
dengan elemen yang paling depan yang belum urut. Sebaliknya, untuk sorting
descending (menurun), elemen yang paling. besar yang disimpan indeksnya
kemudian ditukar. Algoritma selection sort dapat dirangkum sebagai berikut:
a. Temukan nilai yang paling minimum (atau sesuai keinginan) di dalam
struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang
paling minimum. Jika descending, maka temukan nilai yang paling
maksimum.
b. Tukar nilai tersebut dengan nilai pada posisi pertama di bagian struktur data
yang belum diurutkan.
c. Ulangi langkah di atas untuk bagian struktur datayang tersisa
3. Insertion Sort (Metode Penyisipan)
Cara kerja insertion sort sebagaimana namanya. Pertama-tama, dilakukan
iterasi, di mana di setiap iterasi insertion sort memindahkan nilai elemen, kemudian
menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya
dilakukan. Dari proses iterasi, seperti biasa, terbentuklah bagian yang telah di-
sorting dan bagian yang belum di-sorting. Algoritma Insertion Sort dapat
dirangkum sebagai berikut:
1. Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
2. Bandingkan nilainya dengan elemen sebelumnya. Jika elemen sebelumnya
(Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-
1 tersebut. Decrement i (kurangi nilainya dengan 1).
3. Lakukan terus poin ketiga, sampai Ti-1 ≤ Ti.
4. Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang
disimpan sebelumnya.
5. Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).
LAPORAN PRAKTIKUM STRUKTUR DATA DAN ALGORITMA
GRAPH
DISUSUN OLEH
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. FAISAL DHARMA ADHINATA (M0511021)
2. MUHAMMAD SAFRI JULIARDI (M0512038)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
SELASA, 10 JUNI 2014
1. SOURCE CODE package graph;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.alg.KruskalMinimumSpanningTree;
import org.jgrapht.alg.PrimMinimumSpanningTree;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleGraph;
import org.jgrapht.graph.SimpleWeightedGraph;
public class Graph {
public static void main(String[] args) {
int vCount = 6;
// SimpleGraph<String, DefaultEdge> graph = new
SimpleGraph<>(DefaultEdge.class);
SimpleWeightedGraph<String, DefaultWeightedEdge> graph2 = new
SimpleWeightedGraph<>(DefaultWeightedEdge.class);
String vertex[] = new String[vCount];
for (int i = 0; i < vertex.length; i++) {
vertex[i] = "y" + i;
graph2.addVertex(vertex[i]);
}
// graph.addEdge(vertex[0], vertex[1]);
// graph.addEdge(vertex[0], vertex[4]);
// graph.addEdge(vertex[1], vertex[2]);
// graph.addEdge(vertex[1], vertex[3]);
// graph.addEdge(vertex[1], vertex[4]);
// graph.addEdge(vertex[3], vertex[4]);
// graph.addEdge(vertex[2], vertex[5]);
graph2.addEdge(vertex[0], vertex[1]);
graph2.setEdgeWeight(graph2.getEdge(vertex[0], vertex[1]),
9.0);
graph2.addEdge(vertex[0], vertex[4]);
graph2.setEdgeWeight(graph2.getEdge(vertex[0], vertex[4]),
5.0);
graph2.addEdge(vertex[1], vertex[2]);
graph2.setEdgeWeight(graph2.getEdge(vertex[1], vertex[2]),
3.0);
graph2.addEdge(vertex[1], vertex[3]);
graph2.setEdgeWeight(graph2.getEdge(vertex[1], vertex[3]),
10.0);
graph2.addEdge(vertex[1], vertex[4]);
graph2.setEdgeWeight(graph2.getEdge(vertex[1], vertex[4]),
1.0);
graph2.addEdge(vertex[3], vertex[4]);
graph2.setEdgeWeight(graph2.getEdge(vertex[3], vertex[4]),
7.0);
graph2.addEdge(vertex[2], vertex[5]);
graph2.setEdgeWeight(graph2.getEdge(vertex[2], vertex[5]),
4.0);
DijkstraShortestPath<String, DefaultWeightedEdge> dijkstra =
new DijkstraShortestPath<>(graph2, vertex[0], vertex[5]);
for (DefaultEdge de : dijkstra.getPathEdgeList()) {
System.out.println(de);
}
System.out.println("");
KruskalMinimumSpanningTree< String, DefaultWeightedEdge>
kruskal = new KruskalMinimumSpanningTree<>(graph2);
for (DefaultEdge de : kruskal.getMinimumSpanningTreeEdgeSet())
{
System.out.println(de);
}
System.out.println("Kruskal Total Weight : " +
kruskal.getMinimumSpanningTreeTotalWeight());
System.out.println("");
PrimMinimumSpanningTree< String, DefaultWeightedEdge> prim =
new PrimMinimumSpanningTree(graph2);
for (DefaultEdge de : prim.getMinimumSpanningTreeEdgeSet()) {
System.out.println(de);
}
System.out.println("Prim Total Weight : " +
prim.getMinimumSpanningTreeTotalWeight());
System.out.println("");
}
}
2. ANALISIS
Graph merupakan cabang kajian yang mempelajari sifat sifat graf. Secara informal,
suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang
terhubung oleh sisi (edge) atau bisa juga disebut busur (arc). Biasanya graff digambarkan
sebagai kumpulan titik- titik yang melambangkan simpul yang dihubungkan oleh
garis- garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi
dapat dihubungkan suatu simpul dengan simpul yang sama. Sisi tersebut dinamakan
gelang (loop).
Berikut penjelasan tentang program graph:
Dideklarasikan vCount-nya adalah 6, yaitu vertex dari 0 hingga vertex 5. Lalu
membuat graph dengan simple graph, tetapi karena graph yang ini tidak memiliki
weight maka menggunakan DefaultEdge.
Lalu membuat vertex. Deklarasikan dulu vertex dalam bentuk string. Lalu looping
for untuk membuat vertex dari 0 hingga 5.
Deklarasikan untuk membuat edge yang menghubungkan tiap-tiap vertex. Dari
deklarasi tersebut dapat digambarkan bentuk graph-nya yaitu:
Ini untuk menghitung atau menentukan path yang terpendek atau shortest path
dengan menggunakan algoritma Dijkstra. Lalu looping-nya menggunakan de yang
dideklarasikan untuk menghitung pathedgeList-nya. Jadi tidak perlu menggunakan
variabel bantuan lain.
Hasilnya adalah:
Yang bentuknya:
Ini merupakan hasil dari rute terpendeknya menggunakan Dijkstra. Karena tidak
terdapat weight, maka hanya dilihat rute terpendeknya tanpa memandang angka weight-
nya.
Lalu menggunakan cara Kruskal. Kruskal ini caranya yaitu dengan mencari weight
yang paling rendah terlebih dahulu, lalu mencari edge mana yang memiliki weight
tersebut. Lalu dideteksi apakah ada yang mengalami cyclic, yaitu rute yang melingkar.
Lalu setelah selesai, weight di-increase atau ditambah dan seterusnya.
Tampilan setelah perhitungan kruskal adalah :
Walaupun tidak memiliki weight, dihitung tiap edge yang dilewati adalah nilainya
satu. Totalnya 5 berarti yang ia lewati ada 5 edge.
Berikut gambarnya:
Lalu selanjutnya yaitu Prim. Prim ini caranya melihat nilai weight-nya dari yang
terkecil lalu hubungkan edge-nya. Lalu cari lagi yang berhubungan dengan vertex baru,
mana weight yang terkecil, bila mengalami dua weight kecil yang sama maka keduanya
diproses, terserah yang mana yang didahulukan. Jangan lupa untuk mengecek apakah akan
mengalami cyclic atau tidak.
Berikut hasilnya:
Gambarnya:
Total weight-nya adalah 5 juga.
Lalu program graph yang menggunakan weight, berikut penjelasannya:
Sama seperti graph yang tidak memiliki weight, bedanya menggunakan
DefaultWeightEdge.
Ini merupakan deklarasi dari vertex yang memiliki edge dengan vertex lain dan
mempunyai weight. Misal, vertex 0 dan 1, edgeWeight-nya adalah 9.
Dengan kotak adalah weight-nya.
Dijkstra ini sama seperti penjelasan di atas. Bedanya ada pada perintah
DefaultWeightedEdge, yang menandakan bahwa pada graph tersebut memiliki weight pada
masing-masing edge-nya.
Hasil pada program:
Gambarnya:
Mula-mula dari V0, memilih antara 5 atau 9, ia memilih 5. Lalu dari V4 memilih 1
atau 7, maka memilih 1. Dari V1 memilih 9,3, atau 10, maka memilih 3. Dari V2 langsung
ke V5.
Setiap memilih edge, diperhitungkan apakah akan mengalami cyclic atau tidak.
Kruskal sama seperti penjelasan sebelumnya. Jadi ia memilih edge yang terkecil
terlebih dahulu dari semua edge yang ada, misal diambil edge 1, lalu vertex apa saja yang
memiliki weight 1 akan dihubungkan, lalu weight 2, dan seterusnya.
Hasil jalannya program:
Gambarnya:
Jumlah dari weight-nya adalah 5+7+1+3+4=20.
Apabila mengambil edge yang bernilai 9, 10 atau 8 maka akan mengalami cyclic.
Maka dari itu, tidak diambil.
Lalu Prim, berikut hasilnya:
Gambarnya:
Hasil Prim dan Kruskal sama, tetapi urutannya berbeda. Memiliki total sama pula,
yaitu 20.
top related