laporan praktikum struktur data dan algoritma informatika uns 2014

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;





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];


maxSum = thisSum;

}

}

}


System.out.println("\nWaktu Eksekusi = " +

(endTime - startTime) + " ms");

return maxSum;

}


int a[] = new int[500000];


int maxSum;

for (int j = 0; j < 500; j++) {


a[j] = angka;


}



}

}

Algoritma 3

package 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) {


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);

}


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;

}


int a[] = new int[10000000];


int maxSum;

for (int j = 0; j < 50; j++) {


a[j] = angka;


}

}

}

Algoritma 4

package algoritma4;





int maxSum = 0, thisSum = 0;

for (int j = 0; j < a.length; j++) {

thisSum += a[ j];


maxSum = thisSum;

} else if (thisSum < 0) {

thisSum = 0;

}

}


System.out.println("\nWaktu Eksekusi = " + (endTime

- startTime) + " ms");

return maxSum;

}


int a[] = new int[1000000];


int maxSum;

for (int j = 0; j < 500; j++) {


a[j] = angka;


}



}

}

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.


REKURSI

DISUSUN OLEH


M0513019

ASISTEN DOSEN:

1. MUHAMMAD SAFRI JULIARDI (M0512038)

2. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)

JURUSAN INFORMATIKA



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;


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


PERCOBAAN 2

5. run:


5

1: 1

2: 1

3: 2

4: 3

5: 5


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;


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;


y = x+y;

x = y-x;

}

return y;

}}





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



PERCOBAAN 3

9. run:


5

1: 1

2: 1

3: 2

4: 3

5: 5


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;


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

*/





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


PERCOBAAN 4

13. run:


5

1: 1

2: 1

3: 2

4: 3

5: 5


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;


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);

}





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




LINK LIST

DISUSUN OLEH


M0513019

ASISTEN DOSEN:



JURUSAN INFORMATIKA



SURAKARTA

SELASA, 1 APRIL 2014

SOURCE CODE

LinkList

package linklist;


public class LinkList {


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);


} break;

case 3 :

{



tambahkan!");


method.addLast(masuk);


} break;

case 4 :

{

method.removeFirst();


} break;

case 5 :

{

method.removeLast();


} break;

case 6 :

{



cari!");


method.find(masuk);


} break;

case 7 :

{

System.out.println("Your data : ");

method.printNode();


} break;

case 8 :

{

method.clear();


} break;

case 9 :

{

method.length();


} break;

case 10 :

{


System.out.println("Masukkan data yang ingin

dihapus : ");


method.remove(masuk);


} break;

case 11 :

{

System.out.println("Masukkan data apa yang ingin

anda hapus?");



System.out.println("Masukkan data baru : ");

Scanner inputan2 = new Scanner (System.in);

int masuk2 = inputan2.nextInt();

method.replace(masuk, masuk2);


} break;

case 12 :

{

System.out.println("Masukkan data apa yang ingin

anda tambahkan!");



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);


} 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() {


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;


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;


{

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)

{




{

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 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!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


3


3

Data : 3 ditambahkan di akhir!

Keluar sekarang?

(1 = Yes, 0 = No)

Cetak semua data run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


3


3


Keluar sekarang?

(1 = Yes, 0 = No)

0


7

Your data :

Data : 2

Data : 3

END

Keluar sekarang?

(1 = Yes, 0 = No)

Menghapus data di awal run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


3


3


Keluar sekarang?

(1 = Yes, 0 = No)

0


7

Your data :

Data : 2

Data : 3

END

Keluar sekarang?

(1 = Yes, 0 = No)

0


4

Data di awal sudah dihapus!

Keluar sekarang?

(1 = Yes, 0 = No)

Menghapus data di akhir run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


3


3


Keluar sekarang?

(1 = Yes, 0 = No)

0


7

Your data :

Data : 2

Data : 3

END

Keluar sekarang?

(1 = Yes, 0 = No)

0


4

Data di awal sudah dihapus!

Keluar sekarang?

(1 = Yes, 0 = No)

0


5

Data di akhir berhasil dihapus!

Keluar sekarang?

(1 = Yes, 0 = No)

Temukan data run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


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!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


6


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


8

SUDAH KOSONG!

Keluar sekarang?

(1 = Yes, 0 = No)

Menghitung banyaknya data run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


6


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


8

SUDAH KOSONG!

Keluar sekarang?

(1 = Yes, 0 = No)

0


9

Jumlah datanya : 0

Keluar sekarang?

(1 = Yes, 0 = No)

Mengganti data run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


11

Masukkan data apa yang ingin anda hapus?

2

Masukkan data baru :

3

Data sudah diganti!

Keluar sekarang?

(1 = Yes, 0 = No)

0


7

Your data :

Data : 3

END

Keluar sekarang?

(1 = Yes, 0 = No)

Menambah data di indeks ke-1 run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


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


7

Your data :

Data : 2

Data : 3

END

Keluar sekarang?

(1 = Yes, 0 = No)

Keluar run:

WELCOME!


1. Cek kosong





6. Temukan data

7. Cetak semua data

8. Hapus semua data


10. Hapus data

11. Mengganti data


13. Keluar


2


2


Keluar sekarang?

(1 = Yes, 0 = No)

0


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


7

Your data :

Data : 2

Data : 3

END

Keluar sekarang?

(1 = Yes, 0 = No)

1

Anda telah keluar!

Terima kasih.


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.


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).


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).


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.


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.


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!’.


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.


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.


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.


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.


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.


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’.


Merupakan perintah untuk mengakhiri program. Program akan mencetak kalimat ‘Anda sudah keluar!’ dan ‘Terima kasih.’.


LINK LIST

DISUSUN OLEH


M0513019

ASISTEN DOSEN:

1. FAISAL DHARMA ADHINATA (M0511021)



JURUSAN INFORMATIKA



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;


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


public interface IStack_Array1 {

int setData();

void isEmpty();

void isFull();

void push(int data);

int pop();

void makeEmpty();

void print();

int top();

}

Test



public class TestAr {


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


public class Node {

Integer data;

Node next;

}

Interface


public interface iStacklist {

boolean isEmpty();

void push(int data);

int pop();

void makeEmpty();

void print();

void top();

}

Test



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("----------------------------");


}


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.


QUEUE

DISUSUN OLEH


M0513019

ASISTEN DOSEN:




JURUSAN INFORMATIKA



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


return (back == -1);

}

@Override


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];

}

}


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.*;


public class Test1 {


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 {


}

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("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("------------------------------");


}

}

2. Queue Array 2 (Penggandaan Ukuran Array)

package sdaqueue2;



private int front, back = -1;


array = new int[5];

front = back = -1;

}

@Override



}

@Override


front = back = -1;

System.out.println("Queue telah dikosongkan");

}

@Override


if (isFull()) {

doubleArray();

}

if (isEmpty()) {

front++;

}

array[++back] = data;


}

@Override


if (isEmpty()) {

return -1;

} else if (front == back) {

int d = array[front];

front = back = -1;

return d;

} else {

return array[front++];

}

}

@Override


return (back == array.length - 1);

}

private void doubleArray() {

int[] arr = new int[2 * array.length];

if (!isEmpty()) {


arr[i] = array[i];

}

array = arr;

}

}


if (isEmpty()) {


} else {



}

}

}

}

o Interface

package sdaqueue2;


boolean isEmpty();

boolean isFull();

void makeEmpty();


int dequeue();

void print();

}

o Test

package sdaqueue2;

import sdaqueue2.*;






boolean j = true;

while (j) {

Menu();


switch (p) {

case 1: {


p = scn.nextInt();

IQ.enqueue(p);

break;

}

case 2: {

p = IQ.dequeue();

if (p != -1) {




} else {


}

break;

}

case 3: {

IQ.makeEmpty();

break;

}

case 4: {

IQ.print();

break;

}

case 5: {

if (IQ.isEmpty()) {


} else {


}

break;

}

case 6: {

if (IQ.isFull()) {


} else {


}

break;

}

case 7: {

j = false;

break;

}

default: {



}

}

}

}














}

}

3. Queue Array 3 (Circular Array)

package sdaqueue3;



private int front, back;


array = new int[5];

front = back = -1;

}

@Override



}

@Override


front = back = -1;


}

@Override


if (isFull()) {

System.out.println("Queue telah penuh");

} else {

if (isEmpty()) {

front = back = 0;

} else {

back = (back + 1) % array.length;

}

array[back] = data;


}

}

@Override


if (isEmpty()) {

return -1;

} else {

int d = array[front];


front = back = -1;

} else {

front = (front + 1) % array.length;

}

return d;

}

}


return ((back + 1) % array.length == front);

}

@Override


if (isEmpty()) {


} else {



}

}

}

}

o Interface

package sdaqueue3;


boolean isEmpty();

boolean isFull();

void makeEmpty();


int dequeue();

void print();

}

o Test

package sdaqueue3;

import sdaqueue3.*;






boolean j = true;

while (j) {

Menu();


switch (p) {

case 1: {


p = scn.nextInt();

IQ.enqueue(p);

break;

}

case 2: {

p = IQ.dequeue();

if (p != -1) {




} else {


}

break;

}

case 3: {

IQ.makeEmpty();

break;

}

case 4: {

IQ.print();

break;

}

case 5: {

if (IQ.isEmpty()) {


} else {


}

break;

}

case 6: {

if (IQ.isFull()) {


} else {


}

break;

}

case 7: {

j = false;

break;

}

default: {



}

}

}

}














}

}

4. Queue List

package sdaqueue4;


Node front, back;


front = back = null;

}

@Override


return (front == null);

}

@Override


if (isEmpty()) {

System.out.println("Queue kosong");

} else {

Node temp = front;


front = front.next;

temp = null;

temp = front;

}


}

}

@Override


Node temp = new Node();

temp.data = data;

if (isEmpty()) {

front = back = temp;

} else {

back.next = temp;

back = temp;

}


}

@Override


if (isEmpty()) {

return -1;

} else {

int d = front.data;


front = back = null;

} else {

Node temp = front;

front = temp.next;

temp = null;

}

return d;

}

}


Node temp = front;

if (!isEmpty()) {


System.out.println(temp.data);

temp = temp.next;

}

}

}

}

o Interface

package sdaqueue4;


boolean isEmpty();

void makeEmpty();


int dequeue();

void print();

}

o Node

package sdaqueue4;

public class Node {

int data;

Node next;

}

o Test

package sdaqueue4;

import sdaqueue4.*;






boolean j = true;

while (j) {

Menu();


switch (p) {

case 1: {


p = scn.nextInt();

IQ.enqueue(p);

break;

}

case 2: {

p = IQ.dequeue();

if (p != -1) {




} else {


}

break;

}

case 3: {

IQ.makeEmpty();

break;

}

case 4: {

IQ.print();

break;

}

case 5: {

if (IQ.isEmpty()) {


} else {


}

break;

}

case 6: {

j = false;

break;

}

default: {



}

}

}

}


System.out.println("====================================")

;

System.out.println("===== QUEUE IMPL 4 (LIST) MENU =====");

System.out.println("====================================")

;







System.out.println("------------------------------------

");


}

}

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.


BINARY SEARCH TREE

DISUSUN OLEH


M0513019

ASISTEN DOSEN:




JURUSAN INFORMATIKA



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.


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.






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.






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.


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




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).


cari(2)>data temp(1).


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.


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




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



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




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




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).


AVL TREE

DISUSUN OLEH


M0513019

ASISTEN DOSEN:




JURUSAN INFORMATIKA



SURAKARTA

KAMIS, 22 MEI 2014

1. SOURCE CODE

package AVLTree;


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);

}


root = null;

}


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;


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: ");


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


RED BLACK TREE

DISUSUN OLEH


M0513019

ASISTEN DOSEN:




JURUSAN INFORMATIKA



SURAKARTA

SELASA, 3 JUNI 2014

1. SOURCE CODE

a. Main package RBT;


public class Main {


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;

}


return header.right == nullNode;

}


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) {


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) {


char c = 'B';

if (r.color == 0) {

c = 'R';

}


preorder(r.left);

preorder(r.right);

}

}

public void postorder() {

postorder(header.right);

}

private void postorder(RedBlackNode r) {


postorder(r.left);

postorder(r.right);

char c = 'B';

if (r.color == 0) {

c = 'R';

}


}

}

}

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:


SORTING

DISUSUN OLEH


M0513019

ASISTEN DOSEN:




JURUSAN INFORMATIKA



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;


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++) {


}

}

c. INSERTION SORT public void insertionSort(int n) {

int i, j, newValue;


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++) {


}

}

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).


GRAPH

DISUSUN OLEH


M0513019

ASISTEN DOSEN:




JURUSAN INFORMATIKA



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 {


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]);







graph2.addEdge(vertex[0], vertex[1]);

graph2.setEdgeWeight(graph2.getEdge(vertex[0], vertex[1]),

9.0);



5.0);



3.0);



10.0);



1.0);



7.0);



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("Kruskal Total Weight : " +

kruskal.getMinimumSpanningTreeTotalWeight());


PrimMinimumSpanningTree< String, DefaultWeightedEdge> prim =

new PrimMinimumSpanningTree(graph2);

for (DefaultEdge de : prim.getMinimumSpanningTreeEdgeSet()) {


}

System.out.println("Prim Total Weight : " +

prim.getMinimumSpanningTreeTotalWeight());


}

}

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.

laporan praktikum struktur data dan algoritma informatika uns 2014

Education