modul praktikum struktur dataif.ummu.ac.id/images/download/090316-modul struktur data.pdf ·...

1

MODUL PRAKTIKUM

“STRUKTUR DATA”

BAHASA PEMOGRAMAN : JAVA

SOFTWARE : NETBEANS-8.0.2

Di susun oleh

DOSEN PENGEMPUH : JUNAIDI NOH,ST.MT

ASISTEN DOSEN : CATUR SURANTO,S.T

LABORATORIUM

UNIVERSITAS MUHAMMADIYAH MALUKU UTARA

PROGRAM STUDI TEKNIK INFORMATIKA

2017

i

DAFTAR ISI

DAFTAR ISI....................................................................................................................... i

BAB 1. Overview Struktur Data ......................................................................................... 1

1.1 Pengenalan Struktur Data .................................................................................... 1

1.2 Revew.................................................................................................................. 2

1.2.1 Tipe Data................................................................................................. 3

1.2.2 Struktur Kontrol ...................................................................................... 4

BAB II. Dasar-dasar Larik dalam Java ............................................................................... 4

2.1 Mendeklarasikan Array ....................................................................................... 4

2.2 Array Satu Dimensi ............................................................................................. 4

2.3 Array Dua Multidimensi...................................................................................... 5

2.4 Type Data Abstrak............................................................................................... 6

BAB III. Rekursi ................................................................................................................. 9

3.1 Penegertian Rekursi............................................................................................. 9

3.2 Bilangan Triangular............................................................................................. 9

3.3 Bilangan Faktorial ............................................................................................... 10

BAB IV. Algoritma Pengurutan/Sorting............................................................................. 12

4.1 Sorting ................................................................................................................. 12

4.2 Bublle Sort........................................................................................................... 12

4.3 Quick Sort............................................................................................................ 14

BAB V.Stack dan Queue .................................................................................................... 16

5.1 Penertian Stack dan Queue.................................................................................. 16

5.2 Stack .................................................................................................................... 16

5.3 Queue................................................................................................................... 18

BAB VI. Senerai/List.......................................................................................................... 21

6.1 Penertian List....................................................................................................... 21

STRUKTUR DATA-UMMU ii

6.2 Single Linked List ............................................................................................... 21

6.3 Double Linked List.............................................................................................. 22

BAB VII. Binary Tree......................................................................................................... 28

7.1 Penertian Tree...................................................................................................... 28

7.2 Contoh Program................................................................................................... 28

BAB VIII. Pencarian Data dalam Array ............................................................................. 30

8.1 Sekuensial Search................................................................................................ 30

8.2 Pencarian dalam Array Acak............................................................................... 30

BAB IX. Graph ................................................................................................................... 33

9.1 Pengertian Graph ................................................................................................. 33

9.2 Algoritma DFS .................................................................................................... 34

DAFTAR PUSTAKA ......................................................................................................... 35

ii

STRUKTUR DATA-UMMU 1

BAB 1

Overview Struktur Data

Tujuan Pembelajaran Mahasiswa memahami representasi data dan dapat mendeklarasikan struktur data

secara lengkap

1.1 Pengenalan Struktur Data

Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan,penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga datatersebut dapat digunakan secara efisien.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanyadigunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap barisdari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk datadapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuaimasukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini,sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untukkeperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnyaberubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat(dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan strukturdata.

1.2 ReviewSebelum kita melangkah ke bab berikutnya ada baiknya untuk mengingat kembali

apa yang kita ketahui tentang bahasa pemrograman java yang telah di tempuh sebelumnya.Maka perlu untuk mereview sekilas tentang beberapa struktur bahasa pemrograman javayang akan sering kita gunakan nanti pada saat kuliah praktikum struktur data. Perhatikandengan seksama tiap-tiap bagian struktur bahasa pemrograman java berikut ini.

1.2.1 Tipe Data

String, yakni suatu variabel yang menampung data kumpulan huruf ataukarakter. Cara pendeklarasiannya sebagai berikut. Stringnama_var]=”[value]”;

Contoh : String alamat=”Jl. Sumatra 45”

Integer, suatu variabel yang menangani tipe data bilangan bulat. Carapendeklarasiannya sebagai berikut. int [nama_var]=[value];

Contoh : int bilangan=300;


Boolean, adalah tipe data yag paling sederhana. Tipe data ini hanya berisi duanilai yakni true atau false. Tipe data ini sering digunakan untuk menyatakansuatu kondisi. Cara pendeklarasiannya sebagai berikut. boolean[nama_var]=[value];

Contoh : boolean lulus=true;

Array adalah suatu struktur data dalam bentuk deret data. Jadi arraymenyimpan suatu himpunan data yang tersusun dalam bentuk deretan data.Dalam java array direpresentasikan dalam suatu varibel yang bernama variabelarray. Ada dua cara mendeklarasikan variabel array. Cara pertama adalahdengan memberikan value pada saat kita mendeklarasikan variabel array.Perhatikan struktur pendeklarasiannya sebagai berikut :

<tipe_data>[]<nama_var>={<value1>,<value2>};

Contoh : String []data={“Susan”,”Santi”,”Santo”};

Kode diatas berarti kita membuat suatu variabel array yang bernama “data”dengan tipe data string yang berisikan tiga buah data yakni Susan, Santi, danSanto.

Cara yang kedua adalah dengan tanpa melakukan inisaialisasi(pemberian valueawal) terlebih dahulu tetapi jika kita melakukan cara ini maka kita diharuskanuntuk mengisikan panjang array. Perhatikan struktur berikut.

<tipe_data>[]<nama_var>=new <tipe_data>[<panjang_array>];

Contoh : int[]bilangan=new int[100];

kode diatas berarti kita membuat suatu variabel array yang bernama “bilangan”dengan tipe data integer dan dengan panjang data 100.

1.2.2 Struktur Kontrol

Struktur percabangan : dalam java salah satunya direpresentasikan dalamsuatu struktur “IF” yang biasanya dikombinasikan dengan “ELSE” apabilaproses memiliki lebih dari satu cabang. Perhatikan struktur if-else berikut.

If(<kondisi>){

<statement 1>

}else{

<statement 2>

}


Penjelasan.

Kondisi: berisi suatu operasi(biasanya perbandingan) yang memberikan suatunilai boolean yakni true atau false.

Statement 1: adalah suatu statement atau baris program yang akan dieksekusiapabila kondisi memberikan nilai true.

Statement 2: satement atau baris program yang akan dieksekusi apabila kondisimemberikan nilai false.

Perlu ditekankan disini bahwa apabila suatu kondisi telah memberikan nilaitrue maka statement 1 akan dieksekusi dan statement 2 akan diabaikan. Begitupula apabila kondisi memberikan nilai false maka statemen 2 yang akandieksekusi sedangkan statement 1 akan diabaikan. Perhatikan cantohpenerapannya dalam suatu class java.

Struktur Perulangan : Dalam bahasa pemrograman java struktur perulanganbiasanya direpresentasikan dengan menggunakan struktur “FOR”. Blok kodeyang berada pada kalang/scope for inilah yang akan dilakukan eksekusiberulang kali sesuai dengan kondisi tertentu. Perhatikan struktur for berikut.

for(<inisialisasi>;<kondisi>;<update>){

<statement>;

}

Penjelasan

Inisialisasi : berisi proses pemberian nilai awal pada variabel yang digunakansebagai kontrol perulangan(biasanya variabel integer) contoh: int i = 0

Kondisi : biasanya berisi proses pembandingan nilai variabel kontrol dengannilai tertentu. Kondisi ini akan memberikan nilai boolean yakni true atau false.Contoh: i < 100

Update : berisi proses update nilai variabel kontrol. Update variabel kontrol inidigunakan agar suatu perulangan akan berhenti pada suatu kondisi tertentu.Update variabel ini biasanya menggunakan operasi increment dan decrement.Contoh: i++


BAB 2

Dasar – dasar Larik dalam Java

Tujuan Pembelajaran Menjelaskan fitur-fitur teknologi dari java Menjelaskan perbedaan fase pada pemrograman java

2.1 Mendeklarasikan Aray

Array merupakan kemampuan untuk menggunakan satu variabel yang dapatmenyimpan beberapa data dan memanipulasinya dengan lebih efektif. Array harusdideklarasikan seperti layaknya sebuah variabel. Pada saat mendeklarasikan array,anda harus membuat sebuah daftar dari tipe data, yang diikuti oleh sepasang tandakurung [], lalu diikuti oleh nama identifier-nya. Sebagai contoh,

int []ages;

atau Anda dapat menempatkan sepasang tanda kurung [] sesudah nama identifier.Sebagai contoh,

int ages[];

2.2 Aray Satu Dimensi

contoh program array satu diimensi:


Output :

2.2 Aray Dua Multidimensi

Array multidimensi diimplementasikan sebagai array yang terletak di dalamarray. Array multidimensi dideklarasikan dengan menambahkan jumlah tanda kurungsetelah nama array. Sebagai contoh,

int[][] twoD = new int[512][128];

char[][][] threeD = new char[8][16][24];

String[][] dogs = {{ "terry", "brown" },

{ "Kristin", "white" },

{ "toby", "gray"},

{ "fido", "black"}

};


Contoh Program :

Output :

2.4 Tipe Data Abstrak

Tipe data abstrak (TDA) atau lebih dikenal dalam bahasa Inggris sebagai Abstractdata type (ADT) merupakan model matematika yang merujuk pada sejumlah bentukstruktur data yang memiliki kegunaan atau perilaku yang serupa; atau suatu tipe data darisuatu bahasa pemrograman yang memiliki sematik yang serupa. Tipe data abstrakumumnya didefinisikan tidak secara langsung, melainkan hanya melalui operasimatematis tertentu sehingga membutuhkan penggunaan tipe data tersebut meski denganresiko kompleksitas yang lebih tinggi atas operasi tersebut.

contoh tipe data abstrak :

Tipe jadi (built-in): boolean, integer, real, array, dll Tipe buatan (user-defined): stack, queue, tree, dll


I. PELAKSANAAN PRAKTIKUM

PERCOBAAN 1.

Langkah 1 :buat class 3 baru dan ketikkan potongan source-source berikut:


Langkah 2 : run mainTestClass dan amati hasilnya

Langkah3 :Buatlah kesimpulan dari Class tersebut.


BAB 3

Rekursi

Tujuan Pembelajaran Memahami konsep dari bilangan triangular dan faktorial

Mampu memahami dan mengimplementasikan konsep rekursi ke dalam program

Mampu memecahkan masalah sederhana menggunakan rekursi

3.1 Pengertian Rekursi

Rekursi adalah fungsi yang melakukan proses perulangan dengan cara memanggildirinya sendiri. Selain itu Rekursi merupakan konsep pengulangan yang penting dalamilmu komputer. Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalamsebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakanloop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikanpermasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapatmembantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikantampilan algoritma tersebut mudah untuk dianalisa.

3.2 Bilangan Triangular

Bilangan triangular adalah bilangan yang didapatkan dari menambahkan n denganbentuk sebelumnya. Dalam hal ini bilangan triangular ini menerapkan konsep rekursi.

Contoh : bilangan triangular dari 5 adalah 15

n=5 n+(n-1) = 5+((5-1)) = 5 +(4+3+2+1)=15

berikut source bilangan triangular :


Output :

3.3 Bilangan Faktorial

Bilangan factorial sama konsepnya dengan bilangan triangular, kecuali bahwa yangdigunakan adalah perkalian dan bukan penjumlahan. Bilangan factorial didapat dariperkalian n dengan bentuk sebelumnya.


Contoh : bilangan factorial dari 5 adalah 120

n=5 n*(n-1) = 5*(4!) = 5*(4*3*2*1) = 120

Berikut source dari bilangan Faktorial :

Output :


BAB 4

Algoritma Pengurutan/Sorting

Tujuan Pembelajaran Memahami konsep dari algoritma bubble sort

Memahami konsep dari algoritma quicksort

Memahami tentang perbandingan kinerja dari masing-masing algoritma sorting

4.1 Sorting

Sorting adalah sebuah teknik pemrograman untuk mengurutkan suatu data. Teknikini bisa menjadi langkah awal untuk melakukan pencarian karena sebuah pencarian daridata yang telah diurutkan sangat lebih cepat dibandingkan dengan pencarian linier.Banyak sekali teknik-teknik dari algoritma pencarian ini ,antara lain : Bubble Sort,Selection Sort, Insertion Sort, Merge Sort, Shellsort, Quicksort dan lain sebagainya.Namun dalam pertemuan kali ini kita akan membahas Bubble Sort dan Qiucksort saja.

4.2 Bubble Sort

Bubble Sort adalah sebuah algoritma pengurutan yang sangat lamban, tapi secarakonseptual algoritma ini merupakan yang paling sederhana dan karena itu merupakan awalyang bagus untuk mengeksplorasi kita mengenai teknik pengurutan.

Berikut source dari Bubble Sort :

//Implementasi dari Class Bubble Sort :


Output :


4.3 Quicksort

Quicksort adalah algoritma yang beroperasi dengan membagi sebuah larik/array kedalam sub larik dan kemudian memanggil dirinya sendiri secara rekrusif. Kita harusmemilih pivot untuk membagi ke dalam sub larik.

Berikut source Quicksort :

//Implementasi dari class QuickSort


Output :


BAB 5

Stack dan Queue

Tujuan Pembelajaran Mahasiswa memahami tentang stack dan queue Mahasiswa dapat membuat suatu program menggunakan Stack dan Queue Mahasiswa memahami perbedaan Stack dan Queue

5.1 Stack and Queue

Struktur kontrol pemilihan adalah pernyataan dari Java yang mengijinkan user

untuk memilih dan mengeksekusi blok kode spesifik dan mengabaikan blok kode yang

lain. Stack adalah suatu bentuk khusus dari linear list di mana operasi penyisipan dan

penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yang

disebut sebagai “TOP”. Cara ini dapat disebut dengan sistem LIFO (Last In First Out)

yaitu item yang terakhir masuk merupakan item yang pertama keluar.

Queue adalah suatu linear list di mana operasi DELETE terjadi pada sisi depan

(FRONT) dan operasi INSERT terjadi pada sisi belakang (REAR). Jika diberikan suatu

Queue Q dengan elemen-elemennya yang terdiri atas Q1, Q2, ....., QT maka queue Q

dituliskan Q = [ Q1, Q2, .........., QT ]

FRONT(Q) = Q1

REAR(Q) = QT

Selanjutnya untuk menyatakan jumlah elemen dalam suatu queue Q digunakan notasiNOEL(Q).

5.2 Stack

Misal diberikan Stack S sebagai berikut :

S = [ S1, S2, .........., ST ] maka TOP(S) = ST

Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL. Dari stack di atas,

maka NOEL(S) = T. Selanjutnya, jika diberikan sebuah stack S = [A,B,C,D], maka stack

S ini dapat digambarkan sebagai berikut :


Ada empat operasi dasar yang didefinisikan pada stack, yaitu :

o CREATE(stack)

o ISEMPTY(stack)

o PUSH(elemen,stack)

o POP(stack

Berikut source Dari Stack:

//Implementasi dari class Tumpukan :

A

B

C

D TopA

B

C

D Top

A B C D

Top

ABCD

Top


Output :

5.3 Queue

Untuk menggambarkan suatu queue dapat dilakukan beberapa cara , Misal : diberikan

Queue Q = [A, B, C, D, E, F], maka Queue Q dapat digambarkan sebagai berikut :


A B C D E F

F E D C B A

atau dapat pula digambarkan dengan posisi tegak. Prinsip kerja Queue adalah FIFO (First

In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.

Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu :

CREATE

ISEMPTY

INSERT

REMOVE

Berikut source dari queue :

//Implementasi class Queue :


Output :


BAB 6

Senarai/List

Tujuan Pembelajaran Memahami perbedaan array dan list

Memahami konsep dasar list

Mampu mengimplementasikan list dalam program

6.1 Pengertian List

Senarai(list) adalah struktur data/ADT yang mendasar, yang seringkali digunakanuntuk menyimpan koleksi dari data-data dan digunakan pada implementasi programcomputer sehingga masuk akal kalau kita saat ini harus membahas ADT List. ADT Listdapat digunakan sebagai basis untuk mengimplementasikan ADT-ADT lainnya. ADT listdapat dianggap bangunan dasar untuk mengembangkan ADT lain yang lebih rumit.

6.2 Single Linked List

Dalam contoh program ini kita akan membuat beberapa class untukpengimplementasian list pada program.

Class LinkedList :

Class Node :


Output :

6.3 Double Linked List

Sama seperti Single linked list , disini kita akan membuat beberapa class .

Class berikutnya TestDouleLinkedList digunakan untuk mengimplementasikan clas-clasyang akan kita buat :


Class DoubleLinkedList :


Class TwoChildNode :


Output :


BAB 7

Binary Tree

Tujuan Pembelajaran Mahasiswa memahami tentang binary Tree Mahasiswa memahami konsep tree Mahasiswa mampu mengimplementasikan tree dalam sebuah program

7.1 Apa itu tree?

Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkanbentuk hierarki antara elemen-elemen. Tree biasanya terdiri dari root (akar) dan node-node (simpul-simpul) yang berada di bawah root. Struktur seperti tree sangat banyaksekali dgunakan dalam dunia nyata, misalnya: struktur organisasi suatu perusahaan,pengaturan filesystem, daftar isi sebuah buku, dan masih banyak lagi. Ilustrasistruktur data tree:

Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.Contoh : node E memiliki in degree 1 dan out degree 2 Root (akar) adalah node yangmemiliki derajat keluar >=0 dan derajat masuk = 0. Contoh : node A adalah root Subtree/ child adalah bagian salah satu node dibawah root sampai ke bawah. Contoh : tree Cadalah right subtree dari A dan tree B merupakan left subtree dari A node G dan Fmerupakan child dari node C node F merupakan parent dari node J dan K Ancestoradalah Node yang berada di atas node lain.

7.2 Contoh Program


Output :


BAB 8

Pencarian Data Dalam Array

Tujuan Pembelajaran Mahasiswa memahami tentang konsep searching Mahasiswa memahami algoritma dari searching Mahasiswa mampu mengimplementasikan algoritma searching dalam sebuah

program

8.1 Sekuensial Search

Sequential search / pencarian beruntun atau banyak pula yang menyebutnya linearsearch (pencarian lurus), adalah salah satu metode algoritma pencarian yang palingsederhana. Para programmer pemula pasti akan menggunakan algoritma ini saatmenghadapi kasus pencarian untuk pertama kali. Konsep dari algoritma ini tak terlalusulit, yakni seluruh data akan dicek satu persatu sampai data yang dicari ditemukan.

Ada 2 macam pencarian beruntun,yaitu pencarian pada array yang sudah terurut, danpencarian pada array yang belum terurut.

8.2 Pencarian Dalam Array Acak

Contoh program :


Output :

8.3 Pencarian Dalam Array Acak

Contoh program :


Output :

Perbedaan dari kedua metode diatas adalah ketika kita mencari data pada array yangacak itu memakan waktu yang lebih lama dalam proses pencariannya contohnya padaprogram diatas kita akan mencari data 2, pada pencarian array yang acak data 2ditemukan pada indeks ke tiga sedangkan jika kita mengurutkanya dulu yaitu padametode pencarian terurut maka data 2 ditemukan pada indeks ke dua


BAB 9

GRAPH

Tujuan Pembelajaran Menangani exeption menggunakan blok tyr-catch-finally Mahasiswa memahami

konsep dari graph Mahasiswa memahami konsep dari algoritma DFS (Depth First Search)

Mahasiswa memahami konsep dari Algoritma (Breadth-First-serch)

9.1 Graph

Algoritma DFS (Depth First Search) merupakan salah satu jenis algoritma greedyyang digunakan untuk men-scan karakter yang ada pada sebuah petak. Penerapanalgoritma ini cukup banyak digunakan pada bidang sains dan teknologi, terutama padapiranti cerdas. Penjelasan algoritma DFS bisa dibaca di Wikipedia – Depth First Search.Penerapan dalam source code, algoritma DFS bisa menggunakan fungsi rekursi yangmemanggil dirinya sendiri ataupun menggunakan stack (tumpukan). Salah satupenggunaan algoritma DFS adalah digunakan untuk permainan tebak jumlah dadu.

Algoritma Breadth-first search adalah algoritma yang melakukan pencarian secaramelebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpulkemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebutterlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengansimpul-simpul yang tadi di kunjungi , demikian seterusnya. Jika graf berbentuk pohonberakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada aras d+1. Algoritma ini memerlukan sebuah antrian q untuk menyimpansimpul yang telah dikunjungi. Simpul-simpul ini diperlukan sebagai acuan untukmengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telahdikunjungi masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkantable Boolean untuk menyimpan simpul yang telah dikunjungi sehingga tidak adasimpul yang dikunjungi lebih dari satu kali.


9.2 Algoritma DFS (Depth First Search)

Berikut source dari Algoritma (Depth-first-search):

Implementasi dari class-class yang Akan kita buat :

Class DFSGraph :


Class DFSStack :

Class DFSVertex :


Output :

9.3 Algoritma Breadth-first search

Berikut source Algoritma (Breadth-First-serch) :


Output :


DAFTAR PUSTAKA

L.N. Harnaningrum. 2010. Struktur Data Menggunakan Java, Yogyakarta:Penerbit Graha Ilmu.

Heriyanto, Imam, Budi Raharjo (2003). Pemrograman Borland C++ Builder. InformatikaBandung.

modul praktikum struktur dataif.ummu.ac.id/images/download/090316-modul struktur data.pdf ·...

Documents