BAB I ALGORITMA DAN STRUKTUR DATA 1.1 Pendahuluan Deskripsi singkat : Bab ini menjelaskan tentang konsep dasar algoritma dan struktur data meliputi: definisi algoritma dan struktur data, struktur data statis dan dinamis serta tipe data abstrak. Manfaat : Mahasiswa mampu memahami tentang konsep dasar algoritma dan struktur data serta implementasinya. Relevansi : Konsep dasar algoritma merupakan dasar yang penting untuk materi materi selanjutnya. Learning Outcomes : Mahasiswa Memiliki pengetahuan mengenai teori dan konsep dasar algoritma dan struktur data. Alokasi dan waktu : Bahan yang ada pada bab ini membutuhkan alokasi waktu kurang lebih 150 menit, dan disampaikan pada minggu pertama perkuliahan. Definisi : Algoritma dan Struktur Data Algoritma adalah urutan logis langkah-langkah untuk menyelesaikan masalah. Algoritma memiliki lima ciri penting : 1. Algoritma harus berhenti setelah mengerjakan sejumlah langkah terbatas. 2. Setiap langkah harus didefinisikan dengan tepat dan tidak ambigu (definite). 3. Algoritma memiliki nol atau lebih masukan. 4. Algoritma memiliki satu atau lebih keluaran. 5. Algoritma harus efektif. Struktur data: susunan atau cara merepresentasikan data agar efisien dalam penyimpanan (RAM) dan pengolahannya. Struktur data seharusnya dapat diterapkan pada algoritma yang didesain secara efisien Jadi mata kuliah Algoritma & Struktur Data adalah suatu disiplin ilmu yang mempelajari bagaimana merepresentasikan data secara efisien dan desain pengolahannya secara efisien pula. 1
Ide pemrograman terstruktur pertama kali disampaikan oleh Profesor Edsger Djikstra dari Universitas Eidenhower sekitar tahun 1965. Djikstra mengusulkan tidak dipergunakannya pernyataan GOTO yang dapat menyebabkan timbulnya “spaghetti logic”, yang akan menjadikan sulitnya dilakukan perbaikan ataupun pengembangan program. Kemudian HD Millis menanggapi dengan mengemukakan bahwa pemrograman terstruktur tidak hanya dihubungkan dengan tidak digunakannya pernyataan GOTO, akan tetapi juga dengan struktur dari program. Struktur program yang akan menentukan program yang terstruktur menggunakan pernyataan GOTO atau tidak. Prinsip utama dari pemrograman terstruktur ialah bahwa jika suatu proses telah sampai pada suatu titik tertentu, maka proses selanjutnya tidak boleh melompat ke baris sebelumnya, kecuali untuk proses berulang. Pemrograman terstruktur dimaksud untuk mendapatkan program yang didefinikan dengan baik, jelas, mudah dipahami, mudah ditelusuri, dan mudah dimodifikasi. Langkah-langkah penyelesaian masalah dengan algoritma dan pemrograman adalah sebagai berikut : 1. Analisis masalah 2. Desain algoritma, meliputi : Deskripsi (cara penulisan): o natural language o pseudo-code o diagram (seperti flowchart) Kriteria algoritma: o Input: nol atau lebih o Output: satu atau lebih o Definisi/terjemahan/interprestasi: jelas, tepat untuk tiap instruksi o Batasan: sebuah algoritma harus berhenti setelah sejumlah langkah, walaupun jumlah langkah boleh banyak tapi harus terbatas Efektifitas: tiap instruksi harus berupa perintah dasar bukan merupakan bentukan dari beberapa perintah 3. Analisis Algoritma 2
Space complexity o Berapa banyak space yang dibutuhkan Time complexity o Berapa lama waktu running algoritma 4. Implementasi Pemutusan bahasa pemrograman yang akan digunakan o C, C++, Lisp, Java, Perl, Prolog, assembly, dll. Penulisan koding harus terdokumentasi dengan baik dan jelas. 5. Ujicoba Mengintegrasikan feedback dari user, perbaiki bug, penjaminan kompatibelitas pada berbagai platform 6. Pemeliharaan
1.2 Struktur Data Statis dan Dinamis Struktur data dilihat dari kebutuhan memorynya dapat dikelompokan menjadi 2 macam yaitu struktur data statis dan dinamis, dimana
Struktur data statis : Struktur data yang kebutuhan/alokasi memorinya tetap (fixed size), tidak dapat dikembangkan atau diciutkan, biasanya menggunakan tipe data array
Struktur data dinamis : Struktur data yang kebutuhan memorynya sesuai data yang ada, dimana dapat dikembangkan atau diciutkan sesuai dengan
kebutuhan. Pengelolaan
alamat secara dinamis (dynamic address) dapat dilakukan dengan menggunakan tipe data pointer.
Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama eksekusi program tersebut. Untuk itu diperlukan satu tipe data yang dapat digunakan untuk mengalokasikan (membentuk) dan mendealokasikan (menghapus) pengingat secara dinamis, yaitu sesuai dengan kebutuhan pada saat suatu program dieksekusi. Oleh karena itu akan dijelaskan suatu tipe data yang dinamakan sebagai tipe Data Pointer.
3
Nama peubah yang kita gunakan untuk mewakili suatu nilai data sebenarnya merupakan / menunjukkan suatu lokasi tertentu dalam RAM di mana data yang diwakili oleh tipe data tersebut disimpan. Pada saat sebuah program dikompilasi maka compiler akan melihat pada bagian deklarasi peubah untuk mengetahui nama-nama peubah apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam memory untuk menyimpan nilai data tersebut. Dari sini kita bisa melihat bahwa sebelum program dieksekusi, maka lokasi-lokasi data dalam memory sudah ditentukan dan tidak dapat diubah selama program tersebut dieksekusi. Peubah-peubah yang demikian itu dinamakan sebagai Peubah Statis (Static Variable). Dari pengertian diatas kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama peubah maka dalam program tersebut peubah yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin diubah. Dengan melihat pada sifat-sifat peubah statis maka bisa dikatakan bahwa banyaknya data yang bisa diolah adalah sangat terbatas. Misalnya peubah dalam bentuk Array yang dideklarasikan sbb : int matriks[100][100], maka peubah tersebut hanya mampu menyimpan data sebanyak 100x100=10000 buah data. Jika kita tetap nekat memasukkan data pada peubah tersebut setelah semua ruangnya penuh maka eksekusi program akan terhenti dan muncul error. Memang kita dapat mengubah deklarasi program diatas dengan memperbesar ukurannya. Tetapi jika setiap kali kita harus mengubah deklarasi dari tipe daa tersebut sementara, banyaknya data tidak dapat ditentukan lebih dahulu, maka hal ini tentu merupakan pekerjaan yang membosankan. Sekarang bagaimana jika kita ingin mengolah data yang banyaknya kita tidak yakin sebelumnya bahwa larik yang telah kita deklarasikan sebelumnya mampu menampung data yang kita miliki ? Untuk menjawab pertanyaan di atas maka pascal menyediakan satu fasilitas yang memungkinkan kita untuk menggunakan suatu peubah yang disebut dengan Peubah Dinamis (Dynamic Variable). Peubah dinamis adalah peubah yang dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi. Dengan kata lain, pada saat program dikompilasi, lokasi
untuk peubah belum ditentukan sebagai peubah dinamis. Hal ini
membawa keuntungan pula, bahwa peubah-peubah dinamis tersebut dapat dihapus pada saat
4
program dieksekusi sehingga ukuran memory selalu berubah. Hal inilah yang menyebabkan peubah tersebut dinamakan sebagai peubah dinamis. Pada peubah statis, isi dari peubah adalah data sesungguhnya yang akan diolah. Pada peubah dinamis nilai peubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya tidak dapat dimasup secara langsung. Oleh karena itu, peubah dinamis dikenal dengan sebutan POINTER yang artinya menunjuk ke sesuatu, yang berisi adress/alamat dalam RAM. Deklarasi variabel bertipe pointer : tipe data *namavariabel; Contoh : int *p Maka variabel p menunjuk suatu alamat pada memori. Jika ada variabel A bertipe integer, maka alamat variabel tersebut pada memori bisa diketahui dengan pernyataan &A. Variabel pointer p, bisa menunjuk ke alamat variabel A, yaitu dengan pernyataan : p = &A; atau dengan memesan sendiri memory baru yaitu dengan perintah p = new int; Sedangkan untuk mengetahui isi dari variabel yang alamatnya ditunjuk oleh p, dengan pernyataan *p; Contoh Program menuliskan alamat dan nilai dari suatu variabel pointer :
#include
using namespace std; main(){ int a,*b; a=10; b=&a; c=new int; *c=25; cout<
5
1.3 Tipe Data Abstrak Menurut Wikipedia, Tipe data abstrak (TDA) atau lebih dikenal dalam bahasa Inggris sebagai Abstract data type (ADT) merupakan model matematika yang merujuk pada sejumlah bentuk struktur data yang memiliki kegunaan atau perilaku yang serupa; atau suatu tipe data dari suatu bahasa pemrograman yang memiliki sematik yang serupa. Tipe data abstrak umumnya didefinisikan tidak secara langsung, melainkan hanya melalui operasi matematis tertentu sehingga membutuhkan penggunaan tipe data tersebut meski dengan resiko kompleksitas yang lebih tinggi atas operasi tersebut. Dengan kata lain Tipe data abstrak (ADT) dapat didefinisikan sebagai model matematika dari objek data yang menyempurnakan tipe data dengan cara mengaitkannya dengan fungsi-fungsi yang beroprasi pada data yang bersangkutan. Merupakan hal yang sangat penting untuk mengenali bahwa operasi-operasi yang akan dimanipulasi data pada objek yang bersangkutan termuat dalam spesifikasi ADT. Sebagai contoh, ADT HIMPUNAN didefinisikan sebagai koleksi data yang diakses oleh operasi-operasi himpunan seperti penggabungan (UNION), irisan (INTERSECTION), dan selisih antar-himpunan (SET DIFFERENCE). Implementasi dari ADT harus menyediakan cara tertentu untuk merepresentasikan unsur tipe data (seperti matrix) dan cara untuk mengimplementasikan operasi -operasi matrix. Secara
tipikal,
kita
akan
mendeskripsikan
operasi-operasi
pada
ADT
dengan algoritma (logika berfikir) tertentu. Algoritma ini biasanya berupa urutan instruksi yang menspesifikasi secara tepat bagaimana operasi-operasi akan dilakukan/dieksekusi oleh komputer. Kita sekarang akan membahas lebih konkret tentang apa itu ADT. Pada dasarnya, ADT adalah tipe data tertentu yang didefinisikan oleh pemrogram untuk kemudahan pemrograman serta untuk mengakomodasi tipe-tipe data yang tidak secara spesifik diakomodasi oleh bahasa pemrograman yang digunakan. Maka, secara informal dapat dinyatakan bahwa ADT adalah : 1. Tipe data abstrak ADT pertama kali ditemukan oleh para ilmuan komputer utuk memisahkan struktur penyimpanan dari perilaku tipe data yang abstrak seperti misalnya, Tumpukan(Stack) serta antrian(Queue). Seperti kita duga, pemrogram tidak perlu tahu bagaimana 6
Tumpukan(Stack)
perubahan
inplementasi
ADT
tidak
mengubah
program
yang
menggunakannya secara keseluruhan, dengan catatan bahwa interface ADT tersebut dengan ‘dunia luar’ tetap dipertahankan. 2. Pemakaian dan pembuatan ADT dapat dilakukan secara terpisah. yang perlu dibicarakan antara pembuat dan pengguna ADT adalah interface ADT yang bersangkutan. 3. ADT merupakan sarana pengembangan sistem yang bersifat modular, memungkinkan suatu sistem dikembangkan oleh beberapa orang anggota tim kerja dimana masing-masing anggota tim bisa melakukan bagiannya sendiri-sendiri dengan tetap mempertahankan keterpaduannya dengan anggota tim yang lain. Dalam hal ini perlu dibedakan antara pengertian struktur data dan ADT. Struktur data hanya memperlihatkan bagaimana data-data di organisir, sedangkan ADT bercakupan lebih luas, yaitu memuat/mengemas struktur data tertentu sekaligus dengan operasi-operasi yang dapat dilakukan pada struktur data tersebut. Dengan demikian, definisi umum tentang ADT di atas dapat diperluas sebagai berikut : Implementasi ADT= {Struktur Data (Operasi-operasi yang dapat dilakukan terhadap Struktur Data)} Contoh ADT Tipe jadi (built-in): boolean, integer, real, array, dll Tipe buatan (user-defined): stack, queue, tree, dll ADT Built-in: Boolean Nilai: true dan false Operasi: and, or, not, xor, dll Integer Nilai: Semua bilangan Operasi: tambah, kurang, kali,bagi, dll
7
ADT buatan (user-defined) : Stack (tumpukan) Nilai : elemen dalam stack Operasi: Initstack, Push, Pop
Queue (antrian) Nilai: elemen dalam Queue Operasi: InitQueue, Enqueue, Dequeue.
Tree (pohon) Nilai: elemen dalam pohon Operasi: insert, delete, find, traverse
8
1.4 Latihan Soal 1. Tulislah output dari cuplikan program berikut : #include using namespace std; main(){ int a,*b, *c; a=10; b=&a; cout<<*b<<endl; c=new int; *c=25; b=c; cout<<*b<<endl; getchar(); } 2. Diketahui subprogram berikut : void buatA(list &l) { int i,n; list b,t; n=10; for (i=1;i<=n;i++){ b=new node; b->next=NULL; b->data=(i+i*i*2)%40; cout<data<<" "; if (l==NULL) l=b; else if (b->data%2==0) {b->next=l;l=b;} else { t=l; while (t->next!=NULL) t=t->next; t->next=b; } } } Jika dipanggil list p; BuatA(p); cetakdata(p); Maka tulis outputnya. 9
BAB II STRUKTUR DATA LINEAR 2.1 Pendahuluan Deskripsi singkat : Bab ini menjelaskan tentang struktur data linear yang meliputi: larikan, single linked list, doubly linked list serta stack dan queue. Manfaat : Mahasiswa memahami tentang berbagai macam struktur data linear dan dapat mengimplementasikan pada beberapa permasalahan. Relevansi :
Struktur data linear paling banyak digunakan dalam menyelesaikan
masalah pemrograman dan akan merupakan dasar dari struktur data yang lebih kompleks. Learning
Outcomes
:
Mahasiswa
Dapat
menganalisis,
merancang
dan
mengimplementasikan struktur data linear seperti linked list, stack dan queue. Alokasi dan waktu : Bahan yang ada pada bab ini membutuhkan alokasi waktu kurang lebih 600 menit, dan disampaikan pada minggu kedua sampai minggu kelima perkuliahan. Definisi : Struktur data linear adalah kumpulan komponen-komponen yang tersusun membentuk satu garis linear. Bila komponen-komponen ditambahkan (atau dikurangi), maka struktur-struktur tersebut berkembang (atau menyusut). Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat , sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. Struktur data linear yang akan dibahas adalah Larikan, yaitu menggunakan array 1 dimensi, linear linked list serta stack dan queue.
2.2 Larikan, Array Satu Dimensi Array adalah suatu struktur yang terdiri dari sejumlah elemen yang memiliki tipe data yang sama. Elemen-elemen array tersusun secara sekuensial dalam memori komputer. Array dapat berupa satu dimensi, dua dimensi, tiga dimensi ataupun banyak dimensi (multi dimensi). Larikan dibentuk menggunakan Array Satu dimensi, yaitu tidak lain adalah kumpulan elemen-elemen identik yang tersusun dalam satu baris. Elemen-elemen tersebut memiliki tipe data yang sama, tetapi isi dari elemen tersebut bisa berbeda.
10
Elemen ke-
0
1
2
3
4
5
6
7
8
9
Nilai
23
34
32
12
25
14
23
12
11
10
Berikut contoh program mengisi larik X dengan bilangan random kemudian menentukan maximum dan minimum. #include #include<stdlib.h> #include using namespace std; main() { int i, n, max, min, x[100]; cout<<"masukkan banyak data : ";cin>>n; srand((unsigned)time(NULL)); for (i=1;i<=n;i++) { x[i]=rand()%100+1; cout<<x[i]<<" "; if (i%10==0) cout<<endl; } cout<<endl; max=x[1];min=x[1]; for (i=2;i<=n;i++){ if (x[i]>max) max=x[i]; else if(x[i]<min) min=x[i]; } cout<<"data max adalah : "<<max<<endl; cout<<"data min adalah : "<<min<<endl; }
2.3 Linear Linked List Pada bab sebelumnya telah dijelaskan mengenai variabel array yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai olehnya tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah di atas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat direlokasikan kembali. Setiap ingin menambahkan data, Anda selalu menggunakan variabel pointer yang baru, akibatnya Anda akan membutuhkan banyak sekali pointer. Oleh karena itu, ada baiknya 11
jika Anda hanya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan metode yang kita sebut Linked List. Linked list adalah sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian. Untuk dapat menyimpan data yang banyak dan untuk menunjukan sifat dinamisnya, maka variabel pointer harus dikombinasikan dengan tipe data struct, yaitu membentuk struktur data linked list (senarai berantai), berikut contoh deklarasi dan subprogram untuk membentuk linked list dari data random dengan menggunakan metode insert di depan, sebagai berikut :
typedef struct node { int data; struct node *next; } *list; list L; void buatD(list &l) { int i,n; list b; cout<<"banyak data : ";cin>>n; srand((unsigned)time(NULL)); for (i=1;i<=n;i++){ b=new node; b->next=NULL; b->data=rand()%100+1; cout<data<<" "; if (l==NULL) l=b; else {b->next=l; l=b;} } } void cetakdata(list l) { list p; if (l!=NULL) { p=l; while (p!=NULL) {cout<data<<" ";p=p->next;} } else cout<<"kosong"; } int main() { int x; list p; p=NULL; 12
buatD(p); cetakdata(p); getch(); return 0; } Pembuatan Linear Linked List dapat menggunakan beberapa cara yaitu : 1. Insert depan, yaitu data yang baru masuk menjadi data atau node paling depan 2. Insert Belakang, yaitu data yang baru masuk menjadi data atau node paling belakang. 3. Insert Terurut, yaitu data yang baru masuk disisipkan pada tempatnya sehingga keseluruhan data dijaga selalu terurut. Linear linked list dari banyaknya linked ada 2 macam, yaitu single linked list dan double linked list. 1. Single Linked List
Pada gambar di atas adalah contoh gambaran tentang single linked list L, setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List, NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL. 2. Double Linked List Salah satu kelemahan single linked list adalah pointer (penunjuk) hanya dapat bergerak satu arah saja, maju/ mundur, atau kanan/kiri sehingga pencarian data pada single linked list hanya dapat bergerak dalam satu arah saja. Untuk mengatasi kelemahan tersebut, anda dapat menggunakan metode double linked list. Linked list ini dikenal dengan nama Linked list berpointer Ganda atau Double Linked List, sehingga dalam mengaksesnya bisa bergerak 2 arah (maju atau mundur), berikut adalah gambaran double linked list
13
Operasi-Operasi yang ada pada Linked List antara lain adalah sebagai berikut : Insert Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list. IsEmpty Fungsi ini menentukan apakah linked list kosong atau tidak. Find First Fungsi ini mencari elemen pertama dari linked list. Update Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu. Delete Now Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut. Delete Head Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
2.4 Stack dan Queue. 1. Stack Stack atau tumpukan adalah struktur data yang berbentuk linear list dengan menggunakan konsep utamanya adalah LIFO (Last In First Out), data yang terakhir masuk dalam stack akan menjadi data pertama yang dikeluarkan dari stack (TOP). Stack ini sering disebut dengan list dengan satu pintu akses. Berikut adalah gambaran tentang Stack.
14
Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut. Push
Untuk menambahkan item pada tumpukan paling atas
Pop
Untuk mengambil item teratas
InitStack
Untuk memulai atau mengosongkan stack
IsEmpty
Untuk memeriksa apakah stack kosong
IsFull
Untuk memeriksa apakah stack sudah penuh
Implementasi stack dalam program dapat digunakan dua cara, yakni dengan array dan linked list. a. Stack dengan Array Sesuai dengan sifat stack, pengambilan / penghapusan di elemen dalam stack harus dimulai dari elemen teratas. Berikut contoh program tentang stack dengan array. #include #include<stdio.h> #include using namespace std; const int maxs = 5; typedef struct { char isi[maxs+1]; int top; } stack; void initstack(stack &S) { S.top = 0; } 15
void push(stack &S,char x) { if (S.top<maxs) { S.top++; S.isi[S.top]=x; } else cout<<"Full"; } void pop(stack &S,char &x) { if (S.top>0) { x=S.isi[S.top]; S.top--; } else cout<<"Empty"; } void PrintStack(stack S) { if (S.top>0) for(int i=S.top;i>0;i--) cout<<S.isi[i]<<endl; else cout<<"kosong"; } main() {stack S; int i,n; char x; cout<<"The Number of data : ";cin>>n; initstack(S); for (i=1;i<=n;i++) { x=(65+rand()%26); cout<<x<<" "; push(S,x); } cout<<endl; PrintStack(S); cout<<endl; pop(S,x); PrintStack(S); cout<<endl; pop(S,x); PrintStack(S); cout<<endl; x='X'; push(S,x); PrintStack(S); pop(S,x); PrintStack(S); } 16
b. Stack dengan Single Linked List Selain implementasi stack dengan array seperti telah dijelasnkan sebelumnya, ada cara lain untuk mengimplementasi stack dalam C++, yakni dengan single linked list. Keunggulannya dibandingkan array tentu saja adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori. Misalnya saja pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Oleh karena itu pula dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia. Berikut contoh Program Stack dengan linked list: #include #include #include<string.h> using namespace std; typedef struct node { char data; struct node *next; } *stack; void initstack(stack &S) { S = NULL; } void push(stack &S,char x) { stack b; b=new node; b->next=NULL; b->data=x; if (S==NULL) S=b; else {b->next=S; S=b;} } 17
void pop(stack &S,char &x) {stack t; if (S!=NULL) { x=S->data; t=S; S=t->next; free(t); } else cout<<"Empty"; } void balikkalimat() {int i,pk;char st[20]; stack S; cout<<"masukkan sebuah kalimat : "; gets(st); pk=strlen(st); initstack(S); for(i=0;idata=='{'))|| ((st[i]==']')&&(S->data=='['))|| ((st[i]==')')&&(S->data=='('))) pop(S,x);else if ((st[i]=='}')||(st[i]==']')||(st[i]==')')) {cek=0;i=pk;} } 18
i++; } if ((S=NULL)||(cek==0)) cout<<"error"; else cout<<"valid"; } main() { balikkalimat(); cekbalance(); getch(); } 2. Queue Queue atau antrian adalah struktur data yang berbentuk linear list dengan menggunakan konsep utamanya adalah FIFO (First In First Out), data yang pertama masuk dalam queue akan menjadi data pertama yang dikeluarkan dari queue. Queue ini sering disebut dengan list dengan dua pintu akses, yaitu pintu depan (front) dan belakang (rear atau back). Berikut adalah gambaran tentang Queue :
Struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut : EnQueue
Memasukkan data ke dalam antrian
DeQueue
Mengeluarkan data terdepan dari antrian
IsEmpty
Memeriksa apakah antrian kosong
IsFull
Memeriksa apakah antrian penuh
Implementasi queue dalam program juga dapat digunakan dua cara, yakni dengan array dan linked list. 19
a. Implementasi Queue dengan Linear Array Linear array adalah suatu array yang dibuat seakan-akan merupakan suatu garis lurus dengan satu pintu masuk dan satu pintu keluar. Berikut ini diberikan deklarasi kelas Queue Linear sebagai implementasi dari Queue menggunakan linear array. Dalam prakteknya, anda dapat menggantinya sesuai dengan kebutuhan Anda. Data diakses dengan field data, sedangkan indeks item pertama dan terakhir disimpan dalam field, berikut contoh program tentang queue dengan linear array. #include #include<stdio.h> #include using namespace std; const int maxq = 5; typedef struct { char isi[maxq+1]; int front, rear } queue; void initqueue(queue &Q){ Q.front =1 ;Q.rear =0 ; } void enqueue(queue &Q,char x) { if(Q.rear < maxq) { Q.rear++; Q.isi[Q.rear]=x ; } else cout<<"full\n"; } void dequeue(queue &Q,char &x) { if(Q.front<=Q.rear) { x=Q.isi[Q.front] ; Q.front++; } else cout<<"EMPTY\n"; } void dequeue1(queue &Q,char &x) { if(Q.rear>0) { x=Q.isi[1] ; Q.rear--; for(int i=1;i<=Q.rear;i++) Q.isi[i]=Q.isi[i+1]; } } void PrintQueue(queue Q) { if(Q.front<=Q.rear) { for(int i=Q.front;i<=Q.rear;i++) cout<
main(){ queue Q; int i,n; char x; cout<<"banyak data : ";cin>>n; initqueue(Q); for (i=1;i<=n;i++) { x=(65+rand()%26); enqueue(Q,x); } cout<<endl; cetakqueue(Q); dequeue(Q1,x); x='X'; enqueue(Q,x); } Pada program di atas, terdapat kelemehan yaitu queue mudah penuh, untuk itu dequeue diganti dengan dequeue1, yaitu dengan menggeser array, hal ini kurang efisien karena menggeser elemen array memerlukan waktu, sehingga yang paling efisien adalah implementasi queue dengan Circular array. b. Implementasi Queue dengan Circular Array Circular array adalah suatu array yang dibuat seakan-akan merupakan sebuah lingkaran dengan titik awal (front) dan titik akhir (rear) saling bersebelahan jika array tersebut masih kosong. Berikut contoh program tentang queue dengan Circular array. #include #include using namespace std; const int maxq = 5; struct queue { char isi[maxq]; int front,rear; }; void initqueue(queue &Q) { Q.front =0 ;Q.rear =-1; for(int i=0;i<maxq;i++) Q.isi[i]=48;} void enqueue(queue &Q,char x) { if((Q.isi[(Q.rear+1)%maxq])==48) { Q.rear++; Q.rear=Q.rear % maxq;Q.isi[Q.rear ]=x ;}} void dequeue(queue &Q,char &x) { if(Q.isi[Q.front]!=48){ Q.front=Q.front % maxq; x=Q.isi[Q.front] ; Q.isi[Q.front]=48;Q.front=(Q.front++)%maxq;}} 21
main() { queue Q;int i,n; char x,y[5]={'U','J','I','A','N'}; initqueue(Q); for (i=0;i<5;i++) enqueue(Q,y[i]); dequeue(Q,x);dequeue(Q,x); x='B';enqueue(Q,x); x='D'; enqueue(Q,x); dequeue(Q,x);dequeue(Q,x); x='C';enqueue(Q,x); x='E'; enqueue(Q,x); for (i=0;i<5;i++) cout< #include #include<string.h> using namespace std; typedef struct node { char data; struct node *next; } *tipequeue; typedef struct { tipequeue front,rear; } queue; void initqueue(queue &Q) { Q.front = NULL; Q.rear=NULL; } void enqueue(queue &Q,char x) { tipequeue b; b=new node; b->next=NULL; b->data=x; if (Q.rear==NULL) {Q.front=b;Q.rear=b;} else { Q.rear->next=b; Q.rear = b;} } void dequeue(queue &Q,char &x) {tipequeue t; if (Q.front!=NULL) { x=Q.front->data; t=Q.front; Q.front=t->next; delete t; if(Q.front==NULL) Q.rear=NULL; } else cout<<"Empty\n"; } void PrintQueue(queue Q) { tipequeue t; 22
if (Q.front!=NULL) { t=Q.front; while(t!=NULL) { cout<data<<" "; t=t->next; } cout<<endl; } } void buatdata(char x[1000],int &n) { cout<<"banyak data : ";cin>>n; for(int i=1;i<=n;i++){ x[i]=65+rand()%26; cout<<x[i]<<" "; } cout<<endl; } void BucketSort(char x[1000],int n) { queue AQ[26];char k;int i; for(k='A';k<='Z';k++) initqueue(AQ[k-65]); for(i=1;i<=n;i++) enqueue(AQ[x[i]-65],x[i]); i=1; for(k='A';k<='Z';k++){ while (AQ[k-65].front!=NULL){ dequeue(AQ[k-65],x[i]); i++; } } for(int i=1;i<= n;i++) cout<<x[i]<<" "; } main() { char x[1000]; int n; buatdata(x,n); BucketSort(x,n); }
2.5 Latihan Soal 1. Sebutkan apa saja keuntungannya membuat struktur data dengan tipe data array dan keuntungannya membuat struktur data dengan tipe data pointer, kemudian mengapa implementasi queue dengan array ada sedikit masalah sehingga harus menggunakan array melingkar. 23
2. Dengan menggunakan stack buatlah subprogram untuk melakukan konversi notasi infix ke notasi postfix, sebagai gambaran : Input berupa ekspresi aritmatika dalam notasi infix sebagai berikut : ((A * B) + C / D – E^F) * G ( dengan prioritas operasi : ^ , * atau / , + atau - ) Output yg dihasilkan ekspresi aritmatika dalam notasi postfix: AB*CD/+EF^–G* (Saudara boleh langsung menggunakan subprogram standar pada stack) 3. Berikut adalah subprogram untuk menghapus node-node dimulai dari node dengan data = x hingga node terakhir pada doubly linked list, lengkapilah subprogram tersebut dengan mengisi statemen/variable yang sesuai pada .......... void DeleteNode(Dlist &L) { int x; Dlist t,r; cout<<"data awal yg mau dihapus :";cin>>x; if ( L->data == x ) { while ( L != NULL ) { r = L ; L = L->next ; delete r ; } } else { t = L; while ( t != NULL && t->data != x ) t = t->next ; if ( t == NULL) cout<<" data tidak ada"<<endl; else { t->prev->next = NULL; while ( t != NULL ) { r = t ; t = t->next ; delete r ; } } } } 4. Dengan menggunakan stack buatlah subprogram untuk membalik urutan elemen matrik, sebagai gambaran berikut contoh matrik input dan outputnya. Input
:
7
5
2
1
7
3
2
8
9
4
3
3
7
4
8
7
Output :
2
7
8
4
7
3
5
5
3
4
9
8
2
2
3
7
1
2
5
7
24
BAB III STRUKTUR DATA NON LINEAR 3.1 Pendahuluan Deskripsi singkat : Bab ini menjelaskan tentang struktur data non linear yang meliputi: matriks, multiple linked list, tree (BST dan AVL Tree) dan graf. Manfaat : Mahasiswa memahami tentang berbagai macam struktur data non linear dan dapat mengimplementasikan pada beberapa permasalahan yang sesuai. Relevansi : Struktur data non linear banyak digunakan dalam menyelesaikan masalah pemrograman yang lebih kompleks dan akan merupakan dasar dari struktur data lanjut. Learning Outcomes : Mahasiswa Dapat menganalisis, merancang dan mengimplementasikan struktur data non linear seperti matriks, multiple linked list, tree dan graf. Alokasi dan waktu : Bahan yang ada pada bab ini membutuhkan alokasi waktu kurang lebih 450 menit, dan disampaikan pada minggu keenam sampai minggu kedelapan perkuliahan. Definisi : Struktur data non linear adalah struktur data yang tidak linear, yaitu antara lain yang akan dibahas dalam bab ini adalah matriks, menggunakan array 2 dimensi, multiple linked list dan struktur data Tree atau pohon terutama pohon biner.
3.2 Matriks, Array Dua Dimensi Array dua dimensi sering digambarkan sebagai sebuah matriks, merupakan perluasan dari array satu dimensi. Jika array satu dimensi hanya terdiri dari sebuah baris dan beberapa kolom elemen, maka array dua dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertipe sama sehingga dapat digambarkan sebagai berikut:
0
1
2
3
4
5
6
0
10
21
23
43
45
78
65
1
45
43
65
12
21
12
21
2
32
34
23
56
54
34
45
3
11
12
32
23
56
76
45 25
Bentuk umum: NamaArray [m][n]; Atau NamaArray [m][n] = { {a,b,..z},{1,2,...,n-1} }; Contoh: double matrix[4][7]; Pendeklarasian array dua dimensi hampir sama dengan pendeklarasian array satu dimensi, kecuali bahwa array dua dimensi terdapat dua jumlah elemen yang terdapat di dalam kurung siku dan keduanya boleh tidak sama.
Elemen array dua dimensi diakses dengan menuliskan kedua indeks elemennya dalam kurung siku seperti pada contoh berikut: matrix[1][2] = 65; matrix[3][6] = 45; Berikut contoh program tentang penggunaan array 2 dimensi. #include #include #include<stdio.h> using namespace std; int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p; int shortest(int v,int n) {int min; for(i=1;i<=n;i++) { S[i]=0; dist[i]=cost[v][i]; } path[++p]=v; S[v]=1; dist[v]=0; for(i=2;i<=n-1;i++) { k=-1; min=9999; 26
for(j=1;j<=n;j++) { if(dist[j]<min && S[j]!=1) { min=dist[j]; k=j; } } if(cost[v][k]<=dist[k]) p=1; path[++p]=k; for(j=1;j<=p;j++) cout<<path[j]<<" "; // cout <<"\n"; // cout <=dist[k]+cost[k][j] && S[j]!=1) dist[j]=dist[k]+cost[k][j]; cout<> n; cout <<"enter no of edges :"; cin >>m; cout <<"\nenter\nEDGE Cost\n"; for(k=1;k<=m;k++) { cin >> i >> j >>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0 && i!=j) cost[i][j]=9999; cout <<"enter initial vertex :"; cin >>v; cout << v<<"\n"; shortest(v,n); getch(); }
27
3.3 Multipe Linked list Multiple linked list adalah linked list dengan linked field lebih dari satu dan bentuknya tidak linear. Sebagai ilustrasi dari multiple linked list dapat dilihat pada gambar berikut.
Berikut contoh program tentang multiple linked list, yaitu untuk menyimpan data peserta pelatihan dimana banyak pelatihan dan pesertanya bisa dinamis. #include #include using namespace std; typedef struct nodep { char nama[20]; struct nodep *next; } *peserta; typedef struct node { char pelatihan[20]; struct node *next; peserta down; } *list; list L; void InsertPelatihan(list &l) { int i,n; list b; cout<<"banyak pelatihan : ";cin>>n; for (i=1;i<=n;i++){ b=new node; b->next=NULL;b->down=NULL; cout<<"Nama Pelatihan : ";cin>>b->pelatihan; if (l==NULL) l=b; else {b->next=l; l=b;} } } 28
void cetakdata(list l) {list p;peserta q; if (l!=NULL) { p=l;cout<<endl; while (p!=NULL) { cout<pelatihan<<" : "; q=p->down; while (q!=NULL) { cout<nama<<", ";q=q->next;} p=p->next;cout<<endl; } } else cout<<"kosong"; } void InsertPeserta(list &l) { int i,n;char namapelatihan[20]; list p;peserta b; cout<<"Insert Peserta "<<endl; cout<<"Nama pelatihan: ";cin>>namapelatihan; p=l; while (p!=NULL && strcmp(p->pelatihan,namapelatihan)!=0) p=p->next; if (p==NULL) cout<<"nama pelatihan belum ada\n"; else if(strcmp(p->pelatihan,namapelatihan)==0) { cout<<"banyak peserta : ";cin>>n; for (i=1;i<=n;i++){ b=new nodep; b->next=NULL; cout<<"Nama peserta : ";cin>>b->nama; if (p->down==NULL) p->down=b; else {b->next=p->down; p->down=b; } } } } void HapusPeserta(list &l) { char namapelatihan[20],namapeserta[20]; list p;peserta b,c; cout<<"Hapus Peserta "<<endl; cout<<"Nama pelatihan: ";cin>>namapelatihan; p=l; while (p!=NULL && strcmp(p->pelatihan,namapelatihan)!=0) p=p->next; if (p==NULL) cout<<"nama pelatihan tidak ada\n"; 29
else if(strcmp(p->pelatihan,namapelatihan)==0) { b=p->down; if(b==NULL)cout<<"tidak ada pesertanya"; else{ cout<<"masukkan nama peserta: "; cin>>namapeserta; if (strcmp(b->nama,namapeserta)==0) {c=p->down;p->down=c->next;free(c);} else { while(b->next!=NULL&&strcmp(b->next->nama,namapeserta)!=0) b=b->next; if (b->next==NULL) cout<<"peserta tidak ada"; else if(strcmp(b->next->nama,namapeserta)==0){ c=b->next;b->next=c->next;free(c); } } } } } main() { int x; L=NULL; InsertPelatihan(L); InsertPeserta(L); cetakdata(L); HapusPeserta(L); cetakdata(L); HapusPeserta(L); cetakdata(L); getch(); }
3.4 Struktur Data Tree Struktur data Tree atau pohon adalah struktur data yang tidak linear dan berbentuk herarki, atau dapat didefinisikan sebagai kumpulan node atau simpul (mulai pada simpul akar), di mana setiap node adalah struktur data yang terdiri dari nilai, bersama dengan daftar referensi ke node anak-anaknya atau cabang-cabangnya. 30
Sebagai tipe data, pohon memiliki nilai dan anak-anak, dan anak-anak itu sendiri bisa berupa pohon, nilai dan anak-anak dari pohon diinterpretasikan sebagai nilai dari simpul akar dan subpohon anak-anak dari simpul akar. dalam hal ini daftar anak-anak dapat menjadi ukuran tetap (percabangan faktor, terutama 2 atau "biner"), jika diinginkan. Sebagai struktur data, pohon adalah sekelompok node, dimana setiap node memiliki nilai dan daftar referensi ke node lain (anak-anaknya). Struktur data Tree yang akan dibahas adalah struktur data binary tree (pohon biner). Pohon biner merupakan pohon yang memiliki ketentuan setiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak.
Berikut ini adalah ilustrasi pohon biner :
Implementasi Tree dalam program, ada beberapa hal yang perlu diperhatikan yaitu : 1. deklarasi pohon 2. membuat pohon 3. memeriksa apakah pohon kosong 4. membuat node baru 5. menambah node ke pohon 6. membaca sebuah node 31
7. mengunjungi pohon secara In Order
(Kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child) 8. mengunjungi pohon secara Pre Order
(Cetak isi node yang dikunjungi, kunjung Left Child, kunjungi Right Child) 9. mengunjungi pohon secara Post Order
(Kunjungi Lift Child, kunjungi Right Child, cetak node yang dikunjungi) 10. mencari node tertentu dalam pohon
Berikut contoh implementasi program tentang Pohon Biner. #include #include<stdio.h> #include using namespace std; typedef struct node { char data; struct node *kanan,*kiri; } simpul; typedef simpul *tree; tree T; void BST(tree *T,char x) { tree b; if (*T==NULL) { b=new simpul; b->data=x;b->kanan=NULL;b->kiri=NULL; *T=b;} else if(x<(*T)->data) BST(&(*T)->kiri,x); else BST(&(*T)->kanan,x); } void PRE(tree T) { if (T!=NULL) { cout<data<<" "; PRE(T->kiri); PRE(T->kanan); } } 32
void IN(tree T) { if (T!=NULL) { IN(T->kiri); cout<data<<" "; IN(T->kanan); } } void POST(tree T) { if (T!=NULL) { POST(T->kiri); POST(T->kanan); cout<data<<" "; } } main (){ tree P;char x;int i,n; P=NULL; cout<<"banyak data : ";cin>>n; for (i=1;i<=n;i++) { x=(65+rand()%26); cout<<x<<" "; BST(&P,x); } cout<<"pre : "; PRE(P); cout<<endl; cout<<"In : "; IN(P); cout<<endl; cout<<"post : "; POST(P); getch(); } Sebuah binary search tree (BST) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing – masing subpohon tersebut (kiri&kanan) itu sendiri adalah juga BST. Sebagai gambaran berikut adalah sebuah BST.
33
Operasi penambahan node/insert pada BST :
BST sebelum dilakukan Insert
BST setelah dilakukan Insert node 120
Sebuah BST, pada dasarnya adalah sebuah pohon biner (binary tree), oleh karena itu, kita dapat melakukan traversal pada setiap node dengan metode inorder, preorder maupun postorder. dan jika kita melakukan traversal dengan metode inorder, pada dasarnya kita telah melakukan traversal valuenya secara terurut dari kecil ke besar, jadi ini sebagai sorting algoritma. Struktur data BST sangat penting dalam struktur pencarian, misalkan, dalam kasus pencarian dalam sebuah larik, jika larik sudah dalam keadaan terurut maka proses pencarian akan sangat cepat, jika kita menggunanan pencarian biner. Akan tetapi, jika kita ingin melakukan perubahan isi larik (insert atau delete), menggunakan larik/array akan sangat lambat, karena proses insert dan delete dalam larik butuh memindahkan banyak elemen setiap saat. Sebaliknya binary tree memberikan jawaban sempurna atas semua permasalahan ini, dengan memanfaatkan binary tree kita dapat melakukan pencarian elemen/node value dalam kompleksitas algorimta O(n log n) langkah saja. Kebanyakan aplikasi saat ini melakukan operasi penambahan dan penghapusan elemen secara terus-menerus tanpa urutan yang jelas urutannya. Oleh karena itu sangatlah penting untuk mengoptimasi waktu pencarian dengan menjaga agar pohon tersebut mendekati seimbang/balance sepanjang waktu. Dan hal ini telah diwujudkan oleh 2 orang matematikawan Russia , G.M. Adel’son-Vel’skii dan E.M. Landis. Oleh karena itu Binary Search Tree ini disebut AVLtree yang diambil dari nama kedua matematikawan Russia 34
tersebut. Tujuan utama dari pembuatan AVL-Tree ini adalah agar operasi pencarian, penambahan, dan penghapusan elemen dapat dilakukan dalam waktu O(log n) bahkan untuk kasus terburuk pun. Tidak seperti Binary Search Tree biasa yang dapat mencapai waktu O(1.44 log n) untuk kasus terburuk. Dalam pohon yang benar-benar seimbang, subpohon kiri dan kanan dari setiap node mempunyai tinggi yang sama. Walaupun kita tidak dapat mencapai tujuan ini secara sempurna, setidaknya dengan membangun Binary Search Tree dengan metode penambahan elemen yang nantinya akan kita bahas, kita dapat meyakinkan bahwa setiap subpohon kiri dan kanan tidak akan pernah berselisih lebih dari 1. Jadi, sebuah AVL-Tree merupakan Binary Search Tree yang subpohon kiri dan kanan dari akarnya tidak akan berselisih lebih dari 1 dan setiap subpohon dari AVL-Tree juga merupakan AVL-Tree. Dan setiap simpul di AVL-Tree mempunyai faktor penyeimbang (balance factor) yang bernilai left-higher (subpohon kiri > kanan), equal-height (subpohon kiri = kanan), righthigher (subpohon kiri < kanan).
Proses balancing pada AVL-Tree dilakukan dengan cara :
Single Rotation (kiri dan kanan)
Double Rotation (kiri dan kanan)
Berikut contoh kedua proses tersebut :
BST sebelum dilakukan insert 20
BST setelah insert 20 dan single rotation kanan
35
BST sebelum dilakukan insert 95
BST setelah insert 95 dan double rotation kanan
Aplikasi dari struktur data pohon, antara lain yaitu untuk kompresi data string menggunakan huffman tree yaitu pohon biner yang disusun berdasarkan frekuensi kemunculan huruf pada string, aplikasi yang lain adalah konversi dari notasi infix ke notasi prefix atau postfix dan aplikasi pada pengurutan data dengan algoritma heapsort yang akan dibahas pada Bab IV.
3.5 Struktur Data Graf Graf banyak digunakan untuk merepresentasikan suatu permasalahan, sehingga perlu dibahas bagaimana menyimpan graf di RAM, yaitu struktur data graf. Graf adalah kumpulan dari simpul atau vertex dan busur atau edge yang secara matematis dinyatakan sebagai : G = (V, E) Dimana G = Graph V = Simpul, atau Vertex, atau Node, atau Titik E = Busur, atau garis, atau Edge, atau arc Contoh graf :
36
Graph Berarah dan Graph Tak Berarah : e8
B
e9 e1
e3 e1
v1
v2
v2
B
e4
A
v3
C
v1
e10 e2
e5
D
A e2
e7
E v5
e6
v4
e3 e4
e5
v4 D
Directed graph
C v3 e7
E
e6
v5
Undirected graph
Dapat dilihat dari bentuk busur yang artinya urutan penyebutan pasangan 2 simpul.
Graph tak berarah (undirected graph atau non-directed graph) : •
Urutan simpul dalam sebuah busur tidak dipentingkan. Mis busur e1 dapat disebut busur AB atau BA
Graph berarah (directed graph) : •
Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah e8.
Graph Berbobot (Weighted Graph) •
Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
•
Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll. Graph Berbobot : B
4 5 v1
A
v2
v2
B
7 3
12
5
C
v3
10 e2
6
v1
3
12
A 4
C v3
8
6
8
D v4
3
E v5
Directed graph
v4 D
3
E
v5
Undirected graph
Panjang busur (atau bobot) mungkin tidak digambarkan secara panjang yang proposional dengan bobotnya. Misal bobot 5 digambarkan lebih panjang dari 7.
37
Representasi Graph dalam bentuk matrix • Adjacency Matrix Graph tak berarah Urut abjad
B
A
C
D
E
A 0
B 1
C 2
D 3
E 4
0
1
0
1
0
1
0
1
0
1
A
0
B
1
C
2
D
3
0
1
0
1
1
E
4
1
0
1
0
1
0
1
1
1
0
Graph
Degree simpul : 3
Representasi Graph dalam bentuk matrix • Adjacency Matrix Graph berarah ke
B
dari
A
C
D
E
Graph
A 0
B 1
C 2
D 3
E 4
0
1
0
1
0
1
0
1
0
1
A
0
B
1
C
2
D
3
0
1
0
1
1
E
4
0
0
1
0
1
0
0
0
0
0
out
in
38
Graph berarah dan berbobot A 0
B
6
3 5
A
12
12
D
7
0
B
1
C
2
D
3
E
4
C
14
2
A
E
B 1
0 5 6 0 0 0 0 0 0 14
C 2
D 3
E 4
0 3 0 12 0
2 0 0 0 0
0 0 9 7 0
Perhatikan pemilihan nilai 0.
Representasi Graph dalam bentuk Linked List • Adjency List graph tak berarah • Digambarkan sebagai sebuah simpul yang memiliki 2 pointer. • Simpul vertex : Simpul edge : left
info
right
left
info
Menunjuk ke simpul edge pertama Menunjuk ke simpul vertex berikutnya, dalam untaian simpul yang ada.
Menunjuk ke simpul vertex tujuan yang berhubungan dengan simpul vertex asal.
right
Menunjuk ke simpul edge berikutnya, bila masih ada.
39
Contoh : untuk vertex A, memiliki 2 edge yang terhubung yaitu e1 dan e2.
B e1
Urut abjad
A
e3
e1
e2
e4
A e2
e5
D
e6
C
B
e7
C
E
D
Graph E
Algoritma Minimum Spanning Tree Problem Tree sebenarnya adalah suatu graf terhubung tanpa cycle. Spanning tree dari suatu graf G adalah tree yang memuat semua vertek dari G. Contoh : 1
6
2
Graf G :
4
3
3
2
5
4
Maka minimum spanning tree dari G adalah :
40
Spanning tree yang total costnya minimum (10) adalah :
1
2
3
3
2
5
4
Suatu contoh aplikasi dari masalah minimum spanning tree adalah misalkan titik dari graf G adalah kota dan cost dari suatu garis (u,v) adalah biaya pemasangan telephone line dari kota u ke v. Maka minimum spanning tree dari G adalah merepresentasikan biaya total minimal untuk memasang telephone line n kota. Problem : Bagaimana menentukan spanning tre dari suatu graf (terhubung) yang total costnya minimum?. Catatan : Spanning tree dari suatu graf G dengan n titik mempunyai tepat n-1 garis. Ada 2 algoritma untuk menentukan minimum spanning tree yaitu Prim dan Kruskal. Prim bekerja berdasarkan titik, Sedangkan Kruskal bekerjannya berdasar garis.
41
PRIM Input : Graf G(V,E), V: himpunan titik dan E himpunan garis. Output: Minimum spanning tree T : himpunan garis. (himpunan B untuk mencatat titik yang sudah didapat) Algoritma : Begin T = {} B = { sembarang titik dari G, misalkan titik 1 } While B V do begin Tentukan garis e =(u,v) dengan cost minimum dimana u B dan v V-B T = T {e} B = B {v} End End KRUSKAL Input : Graf G(V,E), V: himpunan titik dan E himpunan garis. Output
: Minimum spanning tree T : himpunan garis.
(sebagai bantuan digunakan himpunan C1,C2, …,Cn yang berisi titik) Algoritma : Begin SORT hinpunan E secara acending. T = {};C1 = {1}, C2 ={2}, …,Cn ={n}. Repeat e =(u,v) tanpa menentukan yang costnya minimum karena E sudah sorted. Cari himpunan C yang memuat u Cu Cari himpunan C yang memuat v Cv If Cu Cv then begin Gabung Cu dan Cv menjadi satu himpunan. T = T {e} End Until T memuat n-1 garis End 42
Untuk lebih jelasnya diberikan contoh sebagai berikut: Perhatikan graf G di atas :
1
6
2
Graf G :
4
3
3
2
5
4
Maka proses mendapatkan minimum spanning tree sebagai berikut :
PRIM
KRUSKAL
(problem size n )
(problem size m (banyak garis))
Step
(u,v)
B
Step
Awal --
{1}
Awal --
{1},{2},{3},{4}
1
(1,4)
{1,4}
1
(3,4)
{1},{2},{3,4}
2
(3,4)
{1,4,3}
2
(1,4)
{1,3,4},{2}
3
(2,4)
{1,4,3,2}
3
(1,3)
ditolak (Cu=Cv)
4
(2,4)
{1,2,3,4}
T={ (1,4), (3,4), (2,4) }
e=(u,v)
Himpunan C
T={ (3,4), (1,4), (2,4) }
3.6 Latihan Soal 1. Mengapa implementasi Tree dengan array kurang efisien sehingga harus menggunakan pointer, kemudian untuk menyimpan data menu (menu utama, submenu, subsubmenu) suatu aplikasi mengapa sebaiknya menggunakan multiple linked list? 2. Berikut adalah subprogram untuk melakukan find and replace dari suatu BST, dimana data x diganti dengan data y dengan syarat setelah diganti harus tetap BST, lengkapilah subprogram tersebut dengan mengisi statemen yang seharusnya pada ......... 43
void FindReplace(tree &T,char x,char y) {tree p,q; if(T!=NULL) { q=T; p=q; while (q!=NULL && x!=q->data) { p=q; if (xdata) {q=p->kiri;} else {q=p->kanan;} } if (x == q->data) if (.....) {q->data=y; cout<<"true";} else cout<<"false"; else cout<<"data tidak ada"; } } 3. Jika diketahui informasi sebagai berikut : Preorder
U
L
I
K
H
E
V
O
B
A
M
T
Inorder
I
L
H
K
E
U
B
O
A
V
T
M
Gambarlah pohon biner yang memenuhi informasi di atas, kemudian tentukan hasil kunjungan postordernya 4. Buatlah AVL Tree berdasarkan urutan data berikut: 20, 85, 39, 58, 13, 95, 98, 55, 80, 69, 46, 10, 74 Buatlah Binary Search Tree berdasarkan urutan data tersebut. Buatlah AVL Tree berdasarkan urutan data tersebut. 5. Pada implementasi BST dengan array satu dimensi, buatlah subprogram untuk menghapus suatu node daun tertentu x, sedemikian sehingga hasil treenya masih tetap BST. (Buat subprogram tentang multiple linkedlist atau tree atau hasing/searching) 6. Dengan menggunakan queue, buatlah subprogram untuk melakukan kunjungan secara level order pada pohon biner. (Saudara boleh langsung menggunakan subprogram standar pada queue) 44
BAB IV ALGORITMA SORTING 4.1 Pendahuluan Deskripsi singkat : Bab ini menjelaskan tentang algoritma sorting yang optimal baik sorting internal maupun sorting eksternal yang meliputi: QuickSort, MergeSort, HeapSort, Hybrid Mergesort quicksort dan Multiway Mergesort. Manfaat : Mahasiswa memahami tentang berbagai algoritma sorting yang optimal baik sorting internal (RAM) maupun sorting eksternal (File). Relevansi :
Algoritma sorting sering digunakan dalam penyelesaian masalah
pemrograman dan biasanya melibatkan data yang cukup besar. Learning Outcomes : Mahasiswa memiliki pengetahuan mengenai sorting serta dapat mengimplementasikan dalam program komputer. Alokasi dan waktu : Bahan yang ada pada bab ini membutuhkan alokasi waktu kurang lebih 300 menit, dan disampaikan pada minggu kesembilan dan kesepuluh perkuliahan. Pada bab ini dijelaskan beberapa algoritma pengurutan data (sorting), yaitu : Merge Sort, Quick Sort (review) dan Heap Sort. Pengurutan atau sorting merupakan proses untuk menyusun kembali kumpulan entri-entri yang telah dimasukkan dengan suatu aturan tertentu. Secara umum ada 2 macam pengurutan yaitu pengurutan secara menaik (ascenden) dan pengurutan secara menurun (descenden).
4.2 Algoritma Quick Sort dan Merge Sort Algoritma Quick Sort dan algoritma Merge Sort dirancang dengan teknik devide and conquer, merupakan algoritma sorting yang optimal dan sangat efisien. Quick Sort adalah algoritma yang proses pembagian data dengan cara partisi, sehingga diharapkan lebih menghemat memory. Teknik devide and conquer yang digunakan yaitu dengan mempartisi data yang disimpan di array X menjadi 2 subarray, yaitu subarray1 berisi data yang ≤ bound dan subarray2 berisi data yang ≥ bound, dimana bound (pivot) adalah suatu elemen yang diharapkan bisa membagi X menjadi 2 subarray yang banyak datanya
45
seimbang, kemudian terhadap masing-masing subarray dilakukan dengan cara yang sama secara rekursif. Algoritma QuickSort secara rekursif dapat dinyatakan sebagai berikut : Subprogram QuickSort (X[ ], n) { If ( n>1) then { Pilih bound; Partisi (X, bound); QuickSort(subarray1, j-1); QuickSort(subarray2, j+1); } } Sedangkan subprogram Partisi adalah sebagai berikut : Subprogram Partisi (X[ ], first, last ) { bound = X[first]; i = first +1; j=last; while ( i<j ) { while (X[ i ] < bound ) i = i + 1; while (X[ j ] > bound ) j = j – 1; if ( i < j ) Swap(X[ i ], X[ j ]); } Swap( X[ first ], X[ j ]); } Algoritma QuickSort mempunyai kelemahan yaitu untuk keadaan worstcase, salah satu subarray selalu kosong, kompleksitas waktunya O(n2), hal ini karena sangat sulit untuk mengontrol proses partisi. Algoritma MergeSort membagi data yang disimpan di larik X menjadi 2 subarray yang berukuran sama dan mengurutkan masing-masing subarray dengan cara rekursif kemudian melakukan merge kedua subarray yang sudah terurut tersebut.
46
Implementasi dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah di bagi dua dan satu untuk menyimpan elemen yang telah terurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Subprogram MergeSort secara rekursif adalah sebagai berikut : Subprogram MergeSort (X[ ], first, last) { If ( first < last) then { mid = ( first + last ) / 2 ; MergeSort(X[ ], first, mid); MergeSort(X[ ], mid + 1, last); Merge(X[ ], first, mid, last); } } Sedangkan subprogram Merge adalah sebagai berikut : Subprogram Merge (X[ ], first, mid, last ) { I = first; j = mid + 1;k = 0; while ( i ≤ mid or j ≤ last ) { if ( X[ i ] < X[ j ] ) {Temp[k] = X[ i ]; i = i + 1;} else {Temp[k] = X[ j ]; j = j + 1;} } Masukkan data yang tersisa ke dalam Temp; Copy Temp ke array X; }
Berikut adalah program tentang Merge Sort dan Quick Sort. #include #include<stdlib.h> #include using namespace std; typedef int larik[250001]; long long c=0; 47
int n,cc=0; void cetakdata(larik x,int n) {int i; for (i=1;i<=n;i++) { cout<<x[i]<<" "; } cout<<endl; cout<<endl;getch(); } void partisi(larik x,int aw,int ak,int &j) { int i,t,pivot; pivot=x[aw]; i=aw;j=ak; while (i<j){ while ((iaw)&&(x[j]>pivot)) {j--;cc++;}if(j>aw) cc++; if (i<j) {t=x[i];x[i]=x[j];x[j]=t;} } x[aw]=x[j];x[j]=pivot; } void qsort(larik x,int aw,int ak) {int j; if (awmid) for (l=j;l<=ak;l++) {z[k]=x[l];k++;} else for (l=i;l<=mid;l++) {z[k]=x[l];k++;} for (k=aw;k<=ak;k++) x[k]=z[k]; } 48
void mergesort(larik x,int aw,int ak) {int mid; if(aw>n; // srand(time(NULL)); for (i=1;i<=n;i++) { x[i]= rand()%100+1; // cout<<x[i]<<" "; } cout<<endl; // cout<<endl; } main() { int i,j; larik x; buatdata(x,n); cetakdata(x,n); clock_t begin_time = clock(); mergesort1(x,1,n); cout << float( clock () - begin_time )/CLOCKS_PER_SEC; cetakdata(x,n); }
4.3 Algoritma Hybrid MergeQuick Algoritma pengurutan internal dalam pengurutan eksternal biasanya digunakan algoritma quicksort karena algoritma quicksort untuk data dalam jumlah yang kecil lebih cepat dibanding mergesort sedangkan untuk jumlah data yang besar Mergesort lebih cepat. Pada penelitian ini dirancang algoritma hybrid yang memanfaatkan kelebihan dari algoritma mergesort dan quicksort, algoritma hybrid tersebut diberi nama MergeQuick, yang algoritmanya sebagai berikut : 49
Subprogram MergeQuick (X[ ], first, last) { If ( last-first < 1000) then Quicksort(X[ ], first, last) else { mid = ( first + last ) / 2 ; MergeSort(X[ ], first, mid); MergeSort(X[ ], mid + 1, last); Merge(X[ ], first, mid, last); } } Dimana subprogram Quicksort dan subprogram Merge sama persis dengan yang sudah dibahas pada sebelumnya. Berikut hasil perbandingan antara algoritma MergeQuick dengan algoritma Mergesort dan Quicksort untuk jumlah data 1 juta, 2 juta hingga 5 juta, selengkapnya dapat dilihat pada Tabel 4.1. Tabel 4.1 Perbandingan Waktu Proses MergeQuick dengan Mergesort dan Quicksort Banyak data
Waktu Proses (dalam detik) MergeQuick
MergeSort
QuickSort
N=1 juta
0,354
0,419
0,464
N=2 juta
0,743
0,88
1,346
N=3 juta
1,137
1,348
2,684
N=4 juta
1,536
1,815
4,380
N=5 juta
1,957
2,342
6,584
50
Dari Tabel 4.1 menunjukkan bahwa algoritma MergeQuick lebih cepat dibanding dengan algoritma Mergesort dan Quicksort, sehingga pada penelitian ini akan digunakan algoritma MergeQuick untuk pengurutan internalnya.
4.4 Algoritma Heap Sort HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n. Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue. Algoritma pengurutan heap dimulai dari membangun sebuah heap dari kumpulan data yang ingin diurutkan, dan kemudian menghapus data yang mempunyai nilai tertinggi dan menempatkan dalam akhir dari larik yang telah terurut.
Heap Setelah memindahkan data dengan nilai terbesar, proses berikutnya adalah membangun ulang heap dan memindahkan nilai terbesar pada heap tersebut dan menempatkannya dalam tempat terakhir pada larik terurut yang belum diisi data lain.
51
Proses ini berulang sampai tidak ada lagi data yang tersisa dalam heap dan larik yang terurut penuh. Dalam implementasinya kita membutuhkan dua larik – satu untuk menyimpan heap dan satu lagi untuk menyimpan data yang sudah terurut. Tetapi untuk optimasi memori, kita dapat menggunakan hanya satu larik saja. Yaitu dengan cara menukar isi akar dengan elemen terakhir dalam heap tree. Jika memori tidak menjadi masalah maka dapat tetap menggunakan dua larik yaitu larik masukan dan larik hasil. Heap Sort memasukkan data masukan ke dalam struktur data heap. Nilai terbesar (dalam max-heap) atau nilai terkecil (dalam min-heap) diambil satu per satu sampai habis, nilai tersebut diambil dalam urutan yang terurut. Algoritma untuk heap sort : function heapSort(a, count) input: sebuah larik tidak terurut a dengan panjang length (pertama letakkan a dalam max-heap) heapify(a, count) end = count -1 while end > 0 { remove ( ) reheapify ( ) end = end – 1 } Algoritma Heapify Algoritma Heapify adalah membangun sebuah heap dari bawah ke atas, secara berturut-turut berubah ke bawah untuk membangun heap. Permasalahan pertama yang harus kita pertimbangkan dalam melakukan operasi heapify adalah dari bagian mana kita harus memulai. Bila kita mencoba operasi heapify dari akar maka akan terjadi operasi runut-naik seperti algoritma bubble sort yang akan menyebabkan kompleksitas waktu yang ada akan berlipat ganda. Sebuah versi lain adalah membangun heap secara atas-bawah dan berganti-ganti ke atas untuk secara konseptual lebih sederhana untuk ditangani. Versi ini mulai dengan sebuah heap kosong dan secara berturut-turut memasukkan data. 52
Versi lainnya lagi adalah dengan membentuk pohon heap-pohon heap mulai dari subtree-subtree yang paling bawah. Jika subtree-subtree suatu simpul sudah membentuk heap maka pohon dari simpul tersebut mudah dijadikan pohon heap dengan mengalirkannya ke bawah. Setelah diuji, maka ide yang paling efisien adalah versi yang terakhir, yang kompleksitas algoritmanya pada kasus terburuk adalah O(n), sedangkan versi membentuk heap tree-heap tree dari atas ke bawah kompleksitas nya O(n log n). Jadi, algoritma utama heapify adalah melakukan iterasi mulai dari internal simpul paling kanan bawah (pada representasi larik, adalah elemen yang berada di indeks paling besar) hingga akar, kemudian kearah kiri dan naik ke level di atasnya, dan seterusnya hingga mencapai akar (sebagai larik [0..N-1]). Oleh karena itu, iterasi dilakukan mulai dari j= N/2 dan berkurang satu-satu hingga mencapai j=0. Pada simpul internal tersebut, pemeriksaan hanya dilakukan pada simpul anaknya langsung (tidak pada level-level lain di bawahnya). Pada saat iterasi berada di level yang lebih tinggi, subtree subtree selalu sudah membentuk heap. Jadi, kasus akan mengalirkan simpul tersebut kearah bawah. Dengan demikian, heapify versi ini melakukan sebanyak N/2 kali iterasi, dan pada kasus yang paling buruk akan melakukan iterasi sebanyak log (N) kali. Algoritma Remove Algoritma remove ini menukar akar (yang berisi nilai maksimum) dari heap dengan elemen terakhir. Secara logika, simpul yang berada paling kanabawah dipindahkan ke akar untuk menggantikan simpul akar yang akan diambil. Algoritma Reheapify Algoritma reheapify ini melakukan pembuatan ulang heap dari atas ke bawah seperti halnya iterasi terakhir dari algoritma metoda heapify. Perbedaan antara metode heapify dengan metode reheapify ada pada iterasi yang dilakukan oleh kedua algoritma tersebut. Algoritma metode reheapify ini hanya melakukan iterasi terakhir dari algoritma heapify. Hal ini disebabkan baik subtree kiri maupun subtree kanannya sudah merupakan heap, sehingga tidak perlu dilakukan iterasi lengkap seperti algoritma heapify. Dan setelah reheapify maka simpul yang akan diiterasikan berikutnya akan berkurang satu. 53
Perbandingan Dengan Algoritma Pengurutan Lain Heapsort hampir setara dengan quick sort, algoritma pengurutan data lain berdasarkan perbandingan yang sangat efisien. Quick sort sedikit lebih cepat, karena cache dan faktorfaktor lain, tetapi pada kasus terburuk kompleksitasnya O(n), yang sangat lambat untuk data yang berukuran sangat besar. Lalu karena heap sort memiliki (N log N) maka sistem yang memerlukan pengamanan yang ketat biasa memakai heap sort sebagai algoritma pengurutannya.
Heap
sort
juga
sering
dibandingkan
dengan
merge
sort,
yang
mempunyaikompleksitas algoritma yang sama, tetapi kompleksitas ruang nya (n) yang lebih besar dari heap sort. Heap sort juga lebih cepat pada mesin dengancache data yang kecil atau lambat. Dengan memanfaatkan struktur data pohon, kita bisa mendapatkan algoritma pengurutan data yang mangkus yang bisa dimanfaatkan untuk membangun program aplikasi yang baik. Algoritma pengurutan heap sort bisa dimasukkan ke dalam algoritma divide and conquer yang disebabkan pembagian dilakukan dengan terlebih dahulu menerapkan algoritma metoda heapify sebagai inisialisasi untuk mentransformasi suatu tree menjadi heap tree, dan pada setiap tahapan diterapkan algoritma metoda reheapify untuk menyusun ulang heap tree.
4.5 Pengurutan Eksternal Pengurutan eksternal (External sorting) adalah pengurutan yang dapat menangani data dalam jumlah besar. Pengurutan Eksternal diperlukan ketika data yang diurutkan tidak dapat masuk ke dalam memori utama dari komputer / RAM, sementara kalau diurutkan langsung pada memori eksternal (hardisk) lebih lambat. Pengurutan eksternal biasanya menggunakan strategi hybrid. Dalam tahap pengurutan, potongan data cukup kecil yang dapat dimuat di memori utama dibaca dan diurutkan, kemudian ditulis ke subfile atau file sementara. Pada tahap penggabungan, semua subfile yang sudah terurut digabungkan menjadi sebuah file tunggal yang lebih besar dan juga terurut. Salah satu algoritma pengurutan eksternal adalah algoritma mergesort eksternal, dimana potongan data yang masing-masing masuk dalam RAM diurutkan kemudian digabungkan bersama-sama, Sebagai contoh, untuk mengurutkan 900 MB data 54
menggunakan RAM dengan ukuran 100 MB, langkah-langkahnya adalah sebagai berikut : 1. Dibaca 100 MB data masukkan dalam memori utama dan diurutkan menggunakan metode pengurutan konvensional, antara lain quicksort. 2. Menuliskan data hasil pengurutan ke disk (file) . 3. Ulangi langkah 1 dan 2 sampai semua data diurutkan dalam bentuk potongan data 100 MB ( ada 900MB / 100MB = 9 potongan ) 4. Langkah selanjutnya adalah penggabungan Ke 9 potongan file tersebut menjadi satu file output tunggal dengan menggunakan strategi tertentu agar proses pengurutan secara keseluruhan efisien. ada beberapa algoritma untuk mengurutkan data yang tersimpan pada variabel RAM, antara lain QuickSort dan MergeSort. Pengurutan Eksternal diperlukan ketika data yang diurutkan cukup besar dan tidak dapat masuk ke dalam memori utama dari komputer, sementara jika diurutkan langsung pada memori eksternal (hardisk) akan sangat lambat. Misalkan banyak data yang akan diurutkan adalah n, banyak data yang dapat diurutkan di RAM misalkan M, sehingga terdapat s=n/M subfile yang masing-masing bisa diurutkan dengan
pengurutan
internal
(QuickSort),
permasalahannya
adalah
bagaimana
menggabungkan s subfile terurut menjadi satu file terurut. Cara penggabungan yang sering dilakukan adalah dengan metode Multiway MergeSort dan sample sort. a. Multiway Mergesort Secara umum, k-way mergesort menggabungkan s subfile dengan cara merge secara bertahap sebanyak k blok dari subfile, sebagai contoh misalkan akan diurutkan data sebanyak n=4.000.000 sehingga akan terdapat 16 subfile berukuran 250.000 data dan digunakan 4-way mergesort maka 16 subfile akan digabung secara bertahap per 4 blok subfile berukuran 25.000 data, sehingga setiap iterasi akan terjadi 4 kali proses merge yang menghasilkan 4 subarray masing-masing 100.000 data, kemudian dilakukan merge sekali 55
lagi sehingga didapat subarray berukuran 400.000, iterasinya akan dilakukan 10 kali sehingga terakhir akan didapat satu file berukuran 4.000.000 data yang sudah terurut. b. Sample Sort Algoritma pengurutan internal yang lebih populer adalah algoritma Quicksort bukan Mergesort. Jadi adalah wajar untuk merancang algoritma pengurutan eksternal berdasarkan quicksort bukan mergesort, algoritma pengurutan eksternal ini disebut sample sort, yang mempunyai kinerja yang sama seperti multiway mergesort untuk kasus rata-rata dan bukan untuk kasus terburuk. Quicksort biasanya menggunakan satu elemen pivot sebagai dasar untuk melakukan partisi, pada simple sort ini, digunakan k-1 pivot untuk mempartisi menjadi k bucket. selanjutnya k bucket diurutkan secara rekursif menghasilkan k subfile yang proses penggabungannya sangat sederhana. Proses pada pengurutan eksternal, dapat dikelompokan menjadi 2 tahap, yaitu : 1. Tahap internal, yaitu tahapan pembacaan data di file data (eksternal memory) , mengurutkan secara internal menggunakan MergeQuick, kemudian menuliskan dalam subfile-subfile. 2. Tahap Mergefile, yaitu tahapan penggabungan subfile-subfile menjadi satu file data yang terurut menggunakan multiway Mergesort. a. Tahap Internal Pada tahap ini, misalkan akan diurutkan data yang disimpan pada file data text berisi 5 juta data bilangan bulat dengan nama file “data5juta.txt” dan misalkan kemampuan maksimum yang dapat diurutkan secara internal di RAM adalah M = 250.000, maka tahap internal dapat dinyatakan dengan algoritma berikut : Subprogram Internal() { openfile(f, "data5juta.txt"); M=250000; while (not(eof(f))) { larik x = {0}; i=0; 56
while(i<M and not(eof(f))){ readfile(f,x[i]); i = i +1; } MergeQuick(x,0,i-1); switch (k) { case 1: createfile(g,"data1.txt"); case 2: createfile(g,"data2.txt"); case 3: createfile(g,"data3.txt"); case 4: createfile(g,"data4.txt"); case 5: createfile(g,"data5.txt"); case 6: createfile(g,"data6.txt"); case 7: createfile(g,"data7.txt"); case 8: createfile(g,"data8.txt"); case 9: createfile(g,"data9.txt"); case 10: createfile(g,"data10.txt"); case 11: createfile(g,"data11.txt"); case 12: createfile(g,"data12.txt"); case 13: createfile(g,"data13.txt"); case 14: createfile(g,"data14.txt"); case 15: createfile(g,"data15.txt"); case 16: createfile(g,"data16.txt"); case 17: createfile(g,"data17.txt"); case 18: createfile(g,"data18.txt"); case 19: createfile(g,"data19.txt"); case 20: createfile(g,"data20.txt"); } for(j=0; j
digunakan 2-way Mergesort, dimana proses merge dilakukan bertahap setiap 2 subfile, tahap Mergefile untuk jumlah data 5 juta (20 subfile) dapat dinyatakan dengan algoritma berikut : Subprogram Mergefile() { larik x[ ], y[ ], z[ ];int k,i,j,kk=1; for (i=1;i<=20;i++) openfile(f[i], “data”+ i +”.txt”); B =25.000; createfile(h,"data5jutaSorted.txt"); do { j = 1; k=1; do { i=0; while(in-1) for (l=j;l<=n-1;l++) {z[k]=y[l];k++;} else for (l=i;l<=n-1;l++) {z[k]=x[l];k++;} } 58
Subprogram merge4way(int *x1,int *x2, int *x3, int *x4, int *z,int n) { int i=0,j=0,k=0,l=0,ii=0,id,min; do { min=x1[i];id=1; if (x2[j]<min) {min=x2[j];id=2;} if (x3[k]<min) {min=x3[k];id=3;} if (x4[l]<min) {min=x4[l];id=4;} if (id==1){z[ii]=x1[i];i++;} else if (id==2){z[ii]=x2[j];j++;} else if (id==3){z[ii]=x3[k];k++;} else if (id==4){z[ii]=x4[l];l++;} ii++;} while ((i<=n-1)||(j<=n-1)||(k<=n-1)||(l<=n-1)); }
4.6 Latihan Soal 1. Algoritma mergesort dan quicksort sama sama menggunakan teknik devide and conquer, jelaskan apa saja perbedaan dari kedua algoritma sorting tersebut. 2. Jelaskan kelebihan dan kekurangan dari Algoritma mergesort dan quicksort. 3. Dengan menggunakan data input di bawah ini, Tuliskan urutan data sampai terurut (acending) dan hitung berapa kali operasi perbandingan dilakukan, jika digunakan algoritma mergesort, juga tentukan set data tsb termasuk best, worst atau avaragecase? 74, 21, 65, 35, 4, 96, 10, 32,
89, 62, 85, 32,
68, 89, 81
4. Dengan menggunakan data input di bawah ini, Tuliskan urutan data sampai terurut (acending) dan hitung berapa kali operasi perbandingan dilakukan, jika digunakan algoritma quicksort, juga tentukan set data tsb termasuk best, worst atau avaragecase? 74, 21, 65, 35, 4, 96, 10, 32,
89, 62, 85, 32,
68, 89, 81
5. Mengapa algoritma heapsort lebih lambat dibanding quicksort.
6. Buatlah algoritma merge4-way pada sorting eksternal
59
BAB V ALGORITMA SEARCHING
5.1 Pendahuluan Deskripsi singkat : Bab ini menjelaskan tentang algoritma pencarian data (searching) yang meliputi: pencarian sekuensial, pencarian biner (review) dan searching dengan menggunakan fungsi hashing. Manfaat : Mahasiswa memahami berbagai macam algoritma searching dan sehingga diharapkan dapat memilih algoritma searching mana yang paling cocok untuk digunakan. Relevansi : Searching secara umum, termasuk searching dengan fungsi hashing, adalah suatu konsekuensi dari penyimpanan data secara terstruktur dimana proses pencarian kembalinya juga harus efisien. Learning Outcomes : Mahasiswa memiliki pengetahuan mengenai berbagai algoritma searching serta dapat mengimplementasikan dalam program komputer. Alokasi dan waktu : Bahan yang ada pada bab ini membutuhkan alokasi waktu kurang lebih 300 menit, dan disampaikan pada minggu kesebelas dan keduabelas perkuliahan. Pada Bab ini, pertama akan dibahas 2 algoritma pencarian data (Searching) yang biasa dilakukan, yaitu pencarian sekuensial (sequential search) dan pencarian biner (binary search). Pencarian sekuensial lebih cocok digunakan untuk mencari data pada sejumlah data yang belum terurut sedangkan pencarian biner digunakan pada sejumlah data yang sudah terurut. Kemudian dibahas metode pencarian yang sangat efisien yaitu searching dengan fungsi hashing.
5.2 Pencarian Sekuensial Pada pencarian sekuensial, data yang dicari, dibandingkan satu per satu dengan data pada suatu larik data. Algoritma globalnya adalah sebagai berikut : Misalkan dimiliki N data integer yang disimpan pada larik X, dan data yang dicari adalah a.
60
1. Ketemu = 0, indeks = 1. 2. Selama data belum ketemu (ketemu = 0) dan indeks
N:
a. Jika X[indeks] = a, maka data ketemu, lalu nilai ketemu =1. b. Jika X[indeks]
, maka indeks = indeks +1
Kode programnya sebagai berikut : while ((ketemu == 0) && (indeks <= N){ if ( X[indeks]=a){ ketemu=1;} else { indeks = indeks +1;} }
5.3 Pencarian Biner Pencarian biner adalah metode pencarian data pada sekumpulan N data (larik) yang sudah urut dengan prinsip membagi dua larik tersebut, kemudian data dicari pada salah satu dari pecahan larik tadi. Jika data yang dicari nilainya lebih besar dari nilai tengah larik awal, maka data dicari pada pecahan larik indeks tengah+1 sampai indeks N, jika tidak, maka data dicari mungkin berada pada lariks indeks 1 sampai tengah-1. Algoritma globalnya sebagai berikut : Akan dicari data a pada larik X yang berjumlah N elemen. Larik X terurut naik (ascending). 1. Ketemu = 0, awal =1, akhir = N. 2. Selama ketemu = 0 dan awal
akhir , maka tengah = (awal +akhir) / 2 :
Jika X[tengah]=a, maka ketemu =1.
Jika a < X[tengah], maka akhir =tengah- 1
Jika a > X[tengah], maka awal =tengah+1
Kode programnya sebagai berikut : awal =1; akhir = N while ((ketemu == 0) && (awal
akhir){ 61
tengah = (awal + akhir) /2; if (X[tengah]=a){ ketemu=1;} else if (a < X[tengah]){ akhir = tengah-1;} else awal = tengah +1; }
5.4 Pencarian Dengan Fungsi Hashing Pada metode-metode pencarian yang telah kita bahas di atas, secara umum banyaknya pembandingan untuk mencari data atau rekaman yang diinginkan tergantung dari banyaknya data atau rekaman yang diketahui. Jika setiap data atau rekaman bisa ditemukan dengan sekali pemasupan terhadap tabel yang digunakan untuk menyimpan data atau rekaman tersebut, maka lokasi data atau rekaman dalam tabel hanya tergantung dari kunci yang digunakan dan tidak tergantung dari kunci yang lain, seperti dalam pohon. Cara yang paling efisien untuk mengorganisir tabel ini adalah dengan menggunakan larik. Jika kunci berupa integer, kunci tersebut sekaligus bisa digunakan sebagai subskrip dari larik yang dimaksud. Suatu fungsi untuk mengkonversikan suatu data ke nomor posisi dari larik yang diketahui. Fungsi ini disebut dengan fungsi hash. Metode pencarian yang memanfaatkan fungsi hash disebut hashing atau hash addressing. Tujuan utama dalam penentuan fungsi hash adalah agar dua buah kunci yang berbeda tidak mempunyai nilai hash yang sama. Jika hal ini terjadi, akan menyebabkan terjadinya tabrakan (hash collision / hash clash). 1. Fungsi Hash Secara umum fungsi hash (H) adalah fungsi untuk mengkonversikan himpunan kunci rekaman (K) menjadi himpunan alaman pengingat (posisi subskrib dalam larik / L) dan bisa dituliskan dengan menggunakan notasi H:K→L Dua aspek penting yang perlu dipertimbangkan dalam pemilihan fungsi hash adalah sebagai berikut. Pertama, fungsi H harus mudah dan cepat dicari atau dihitung. Kedua, fungsi H sebisa mungkin mendistribusikan posisi yang dimaksud secara uniform sepanjang himpunan L, sehingga banyaknya tabrakan yang mungkin terjadi bisa diminimalkan. Secara 62
alamiah, tidak ada garansi yang memungkinkan bahwa aspek kedua bisa dipenuhi tanpa terlebih dahulu mengetahui kunci-kunci yang ada. Meskipun demikian, ada beberapa metode untuk memotong-motong kunci dalam himpunan K menjadi kombinasi tertentu yang akan dipakai sebagai fungsi H. Berikut disajikan beberapa cara untuk memotong-motong kunci sehingga bisa diperoleh fungsi hash yang dengan mudah bisa dihitung. a. Metode Pembagian Dalam cara ini kita bisa memlih suatu perubah m yang nilainya lebih besar dibanding banyaknya kunci dalam K, misalnya n, dan biasanya dipilih suatu bilangan prima. Fungsi hashnya ditentukan sebagai : H(k) = k mod m atau H(k) = k mod m + 1 Persamaan pertama dipilih apabila diinginkan alamat kunci adalah 0 sampai m – 1. Persamaan kedua dipilih jika diinginkan alamat kunci adalah 1 sampai m. Sebagai contoh, nomor mahasiswa terdiri dari 5 buah digit. Misalkan L terdiri dari 100 buah alamat yang masingmasing alamat terdiri dari 2 karakter : 00...99. Nomor mahasiswa yang diketahui misalnya 10347, 87492, 34212 dan 88688. Untuk menentukan alamat dari keempat nomor mahasiswa ini kita pilih suatu bilangan prima yang dekat dengan 99, misalnya m = 97. Dengan menggunakan fungsi H(k) = k mod m, diperoleh H(10347) = 65, H(87492) = 95, H(34212) = 68, H(88688) = 30 Dengan demikian, nomor mahasiswa 10347 akan disimpan dalam alamat 65, nomor mahasiswa 87492 akan disimpan dalam alamat 95, nomor mahasiswa 34212 akan disimpan dalam alamat 68 dan nomor mahasiswa 88688 akan disimpan dalam alamat 30. Jika dipilih fungsi H(k) = k mod m + 1, maka keempat nomor mahasiswa diatas masing masing akan disimpan dalam alamat 66, 96, 69 dan 31. b. Metode Midsquare Dalam metode ini, kunci yang diketahui dikuadratkan dan fungsi hash yang dipilih adalah : H(k) = l Nilai l diperoleh dengan menghapus digit-digit pada kedua sisi dari k2, dengan catatan bahwa banyaknya digit di sebelah kiri dan sebelah kanan harus sama. Jika tidak sama, maka pada digit di sebelah kiri seolah-olah ditambahkan sejumlah trailing zero, sehingga 63
akan menghasilkan alamat yang benar. Dengan menggunakan contoh yang sama dengan diatas, maka alamat dari masing-masing nomor mahasiswa diatas adalah : k:
10347
87492
k :
107060409
76548500564 1170460944
7865561344
H(k):
06
85
56
2
34212
46
88688
c. Penjumlahan Digit Dalam penjumlahan digit, kunci yang diketahui bisa dipecah menjadi beberapa kelompok yang masing-masing terdiri dari beberapa buah digit, misalnya dua buah. Kemudian digit-digit dari kelompok-kelompok yang ada dijumlahkan. Pemecahan dan penjumlahan terus dilakukan jika jumlah keseluruhan kelompok yang ada masih lebih besar dari banyaknya alamat yang akan dipakai. Dengan menggunakan nomor mahasiswa diatas, maka alamat dari masingmasing nomor mahasiswa bisa ditentukan sebagai berikut (dalam hal ini digunakan kelompok dengan dua buah digit, karena alamatnya diketahui dari 00 sampai 99) : H(10347) = 1 + 03 + 47 = 51 H(87492) = 8 + 74 + 92 = 174 = 1 + 74 = 75 H(34212) = 3 + 42 + 12 = 57 H(88688) = 8 + 86 + 88 = 182 = 1 + 82 = 83 2. Cara Mengatasi Tabrakan Tujuan dari pemilihan fungsi hash adalah untuk menempatkan rekaman pada alamat tertentu, sehingga bisa dihindari adanya tabrakan, yaitu suatu keadaan dimana dua buah atau lebih rekaman yang mempunyai data kunci yang berbeda mampunyai alamat hash yang sama. Meskipun demikian, kemungkinan adanya tabrakan selalu tetap saja terjadi, meskipun kita sudah menentukan fungsi hash yang cukup baik. Dengan demikian, kita harus mempunyai satu cara untuk mengatasi tabrakan yang mungkin terjadi, yang disebut dengan collision resolution. Prosedur yang baik untuk mengatasi adanya tabrakan gayut antara lain terhadap perbandingan banyaknya data kunci (n) dalam K, dan banyaknhya alamat hash (m) dalam L. Perbandingan ini, λ = n/m, disebut faktor beban. Lebih lanjut, efisiensi fungsi hash yang dilengkapi
dengan
prosedur
untukmengatasi
tabrakan
diukur
dengan
banyaknya
pembandingan kunci (probe) yang diperlukan untuk mencari alamat dari rekaman yang 64
mempunyai kunci k. Efisiensi ini gayut terhadap faktor beban dan diukur menggunakan dua besaran berikut ini : B(λ) = rata-rata probe untuk pencarian yang berhasil G(λ) = rata-rata probe untuk pencarian yang gagal a. Pengalamatan Terbuka (closed hashing) Secara umum, cara mengatasi tabrakan dengan pengalamatan terbuka (open addressing) bisa dijelaskan sebagai berikut. Dimisalkan sebuah rekaman dengan kunci k akan disisipkan ke dalam tabel alamat hash. Berdasarkan fungsi hash yang dipakai, alamat untuk kunci k tersebut dihitung, misalnya pada alamat h. Jika kemudian ternyata bahwa alamat h sudah terisi, maka harus dicari alamat lain yang masih kosong. Cara yang termudah adalah dengan mencari alamat berikutnya yang kosong. Cara ini disebut dengan linear probing. Dari gambaran diatas kita bisa melihat, bahwa untuk mencari rekaman dengan kunci k, harus dilakukan pencarian pada alamat h, h + 1, h + 2, ... dan seterusnya. Berdasarkan hal ini, rata-rata pencarian yang berhasil dan tidak berhasil adalah : B(λ) = ½ (1 + 1/(1 - λ)) G(λ) = ½ (1 + 1/(1 - λ)2) Dari gambaran diatas bisa dilihat satu kerugian yang utama dari linear probing ini adalah data cenderung untuk mengumpul pada satu tempat. Hal ini bisa dipahami karena jika ada suatu data yang akan disisipkan pada suatu alamat dan alamat yang dimaksud sudah dipakai, maka data baru tersebut akan ditempatkan pada lokasi berikutnya yang letaknya berurutan. Kedua cara ini disebut dengan quadratic probing atau double hashing. Dalam quadratic probing, jika alamat untuks uatu data baru yang akan disisipkan sudah dipakai (misalnya alamat h), maka data baru tersebut tidak ditempatkan pada posisi h + 1 atau h + 2 (alamat h + 1 juga sudah dipakai) dan seterusnya, tetapi data baru akan diletakkan pada alamat dengan urutan h, h + 1, h + 4, h + 9, ... Dengan demikian, pencarian akan dilaksanakan pada alamat diatas. Hal ini membawa keuntungan, bahwa jika banyaknya alamat yang tersedia adalah merupakan bilangan prima, cara diatas akan melakukan pencarian pada separuh dari seluruh alamat yang ada dalam doubel hashing yang digunakan dua buah fungsi hash untuk menghindari adanya tabrakan. 65
Secara sederhana cara ini bisa dijelaskan sebagai berikut. Dari kunci k ditentukan alamat hash-nya yang pertama, misalnya H(k) = h. Kemudian ditentukan alamat hash yang kedua, misalnya H’(k) = h’ ≠ m (denga m adalah banyaknya alamat hash yang dihasilkan darifungsi hash yang pertama). Dengan demikian, pencarian dilakukan secara urut pada alamat alamat : h, h + h’, h + 2h’, h + 3h’, ... Satu kerugian yang cukup mendasar dalam sistem pengalamatan terbuka adalah sebagai berikut. Dimisalkan bahwa kita akan menyisipkan sebuah rekaman baru, misalnya rek2, yang akan menempati alamat x pada tabel hash. Tetapi karena alamat x sudah terisi, maka rekaman rek2 ini akan ditempatkan pada lokasi kosong yang pertama sesudah alamat x, misalnya x1. Sekarang misalnya rekaman yang ada pada alamat x dihapus. Dengan demikian, maka alamat x sekarang menjadi kosong. Jika kemudian kita akan mencari rekaman rek2 kita akan mendapatkan kenyataan bahwa program mungkin tidak akan mendapatkan kenyataan bahwa program mungkin tidak akan menemukan rekaman tersebut meskipun sesungguhnya ada. Sebabnya adalah bahwa pada saat rekaman rek2 akan dicari, maka berdasar fungsi hash yang dipakai, rekaman tersebut akan menempati alamat x. Tetapi karena sekarang alamat x sudah kosong, maka program tidak akan meneruskan pencariannya ke alamat-alamat yang lain. Salah satu cara untuk mengatasi persoalan diatas adalah dengan memberi tanda khusus pada alamat-alamat yang isi sesungguhnya sudah dihapus. Dengan demikian program akan meneruskan pencarian jika program membaca alamat yang diberi tandai “dihapus”. Tetapi persoalan lain bisa timbul, yaitu jika hampir semua alamat diisi dengan tanda “dihapus”. Dengan cara ini, maka pencarian bisa menjadi pencarian berurutan. b. Penggandengan (open hashing) Penggandengan (Separate chaining) merupakan metode lain yang digunakan untuk mengatasi kemungkinan adanya tabrakan alamat hash. Metode ini pada prinsipnya memanfaatkan senarai berantai (yang juga bisa diimplementasikan menggunakan larik) yang dipasang pada setiap alamat hash yang diketahui. Dengan demikian, kita melihat pada sebuah alamat hash lengkap dan senarai yang menyimpan rekaman rekaman yang mempunyai alamat hash yang sama, maka kita akan melihat adanya sebuah senarai berantai tunggal berkepala denga kepalanya adalah alamat hash.
66
Sebagai contoh, jika kita mempunyai rekaman-rekaman yang kunci rekamannya bisa dituliskan sebagai 34 56 123 78 93 70 100 21 11 77 28 dan fungsi hash yang dipilih adalah k mod 10. Dengan demikian, alamat hash akan terdiri dari sepuluh buah alamat yang bernomor 0 samapi 9 sebagai berikut : 0 : 70 100 1 : 21 11 2: 3 : 123 93 4 : 34 5: 6 : 56 7 : 77 8 : 78 28 9: Hal ini menunjukkan bahwa alamat hash sebaiknya menggunakan senarai berantai untuk menyimpan rekaman-rekaman diatas, yaitu kita bisa menyusun struktur data untuk menyajikan metode penggandengan dengan menggunakan link list. 3. Fungsi Hashing untuk Data String Fungsi hash untuk data yang berupa string diperlukan nilai dari suatu karakter, yang biasanya digunakan berdasar kode ASCII. ASCII singkatan dari American Standard Code for Information Interchange. Komputer hanya dapat memahami bilangan, sehingga kode ASCII adalah representasi numerik dari karakter seperti 'a' atau '@' atau beberapa macam tindakan. Di bawah ini adalah tabel karakter ASCII dan ini termasuk deskripsi dari 32 karakter pertama non-cetak. Tabel ASCII selengkapnya dapat dilihat pada Tabel 5.1 Ada berbagai cara untuk mengkonversi suatu string menjadi suatu bilangan bulat, fungsi hash untuk data string memerlukan konversi tersebut. Misalkan metode hash yang dipilih adalah metode pembagian (modulo atau mod) dengan menggunakan beberapa rumus fungsi hash dari suatu data string, secara umum fungsi hashnya dinyatakan dalam bentuk : H(string) = nilai_hash mod P + 1 dengan nilai_hash adalah bilangan bulat positif yang ditentukan berdasar stringnya. P adalah ukuran tabel hash yaitu bilangan prima ≥ banyak data key. 67
Tabel 5.1 Tabel ASCII (http://www.asciitable.com)
Nilai_hash di atas dapat ditentukan dengan berbagai rumus, pada penelitian ini digunakan 3 rumus penentuan nilai_hashnya, yaitu antara lain : a. Fungsi Hash H1 Fungsi hash H1 dihitung berdasarkan rumus berikut : Nilai_hash = (nilai_string[0] + nilai_string[1] + ... + nilai_string[n-1]) dengan n adalah panjang dari string, nilai_string[i] ditentukan dengan menggunakan Tabel 5.1 Tabel ASCII Sebagai gambaran : Jika string = ‘byte’ maka nilai_hash = 98 + 121 + 116 + 101 = 436 Jika string = ‘RAM’ maka nilai_hash = 82 + 65 + 77 = 224 b. Fungsi Hash H2 Fungsi hash H2 dihitung berdasarkan rumus berikut : Nilai_hash = (((nilai_string[0] + nilai_string[n-1])/2) * n) dengan n adalah panjang dari string, nilai_string[i] ditentukan dengan menggunakan Tabel 5.1 Tabel ASCII. 68
Sebagai gambaran : Jika string = ‘byte’ maka nilai_hash = ((98 + 101)/2 ) * 4 = 398 Jika string = ‘RAM’ maka nilai_hash = ((82 + 77 )/2) * 3) = 238 c. Fungsi Hash H3 Fungsi hash H3 dihitung berdasarkan rumus iterasi sebagai berikut : nilai_hash = 0; for i = 0 to n-1 do nilai_hash = (nilai_hash *3 + nilai_string[i]) mod P; dengan n adalah panjang dari string, P adalah ukuran tabel hash yaitu bilangan prima ≥ banyak data key, nilai_string[i] ditentukan dengan menggunakan Tabel 5.1 Tabel ASCII Sebagai gambaran : Dengan nilai P = 239, Jika string = ‘byte’ maka nilai_hash = 121 Jika string = ‘RAM’ maka nilai_hash = 54 Tujuan dari pemilihan fungsi hash adalah untuk menempatkan rekaman pada alamat tertentu, sehingga bisa dihindari terjadinya tabrakan (collision resolution), yaitu suatu keadaan dimana dua buah atau lebih rekaman yang mempunyai data kunci yang berbeda mampunyai alamat hash yang sama. Meskipun demikian, kemungkinan adanya tabrakan selalu tetap saja terjadi, meskipun fungsi hashnya sudah dipilih yang cukup baik. Dengan demikian, diperlukan satu cara untuk mengatasi tabrakan yang mungkin terjadi. Terdapat 2 metode atau cara untuk mengatasi tabrakan, dimana kedua cara tersebut mempunyai kelebihan dan kekurangan, yaitu antara lain : a. Closed hashing (Open Addressing) Metode Open adressing baik yang Linear Probing, Quadratic Probing maupun Double hashing mempunyai kelebihan yaitu penggunaan memorynya lebih sedikit, akan tetapi kelemahannya adalah waktu pencariannya lebih lambat b. Open hashing (Separate Chaining) Metode Separate Chaining atau linked mempunyai kelebihan yaitu waktu pencariannya lebih cepat, sedangkan kekurangannya penggunaan memorynya lebih banyak. Misalkan digunakan metode Separate Chaining, yaitu dengan membuat struktur data untuk tabel hash menggunakan linked list (pointer), yang dapat digambarkan sebagai berikut : 69
1
Account Akun
2
Byte
browse
cancel
Bita
jelajah
batal
RAM
copy
Memory
salin
. . .
P
utama
Gambar 5.1 Struktur Data untuk Tabel Hash Pada studi kasus data kamus, untuk menyimpan ke dalam tabel hash diperlukan langkah-langkah sebagai berikut : 1. Menentukan ukuran tabel hash, yaitu nilai P merupakan bilangan prima yang lebih besar atau sama dengan banyaknya data key. 2. Untuk setiap data key X[i].key Hitung nilai indeks IH, yaitu nilai fungsi hash H untuk data key X[i].key Tempatkan data key X[i].key pada tabel hash H[i].data.key Jika terjadi tabrakan tempatkan pada linkednya yang masih kosong. Kode program untuk menyimpan data kamus pada tabel hash adalah sebagai berikut : // Menentukan bilangan prima P, ukuran tabel hashnya long prima(int N) {long p; bool prima; do { if ((N==2)||(N==3)) prima=true; else if ((N%2==0)||(N<2)) prima=false; 70
else { p=3;prima=true; do { if ((N%p)==0) prima=false; else p=p+2; } while ( prima && p<=(sqrt(N)+1));} if (!prima) N++; } while (!prima); return N; } //Menentukan nilai fungsi hash, ada 3 macam fungsi hash int nilai1(strg s,int p) { int sum=0; for(int i=0;i<strlen(s);i++) sum +=s[i]; return sum%p+1; } int nilai2(strg s,int p) { int sum=0; sum =((s[0]+s[strlen(s)-1])*strlen(s))/2; return sum%p+1; } int nilai3(strg s,int p) { int sum=0; for(int i=0;i<strlen(s);i++) { sum = (sum*3 + s[i])%p;} return sum%p+1;} //Menempatkan data kamus pada tabel hash H void hashing(datakamus X[1000], int N, larik H, int &p) { int IH,I,t=0;list Q,b; p=prima(N); for(int i=1;i<=p;i++) { 71
strcpy(H[i].data.key,"");H[i].next=NULL; } for(int i=1;i<=N;i++) { IH = nilai1(X[i].key,p); if (strcmp(H[IH].data.key,"")==0) H[IH].data=X[i]; else { b=new node;b->data=X[i];b->next=NULL; if (H[IH].next==NULL) H[IH].next=b; else { Q=H[IH].next; while (Q->next!=NULL) Q=Q->next; Q->next=b; } } } } Sedangkan cuplikan program untuk menampilkan isi tabel hash sekaligus menghitung rerata probe adalah sebagai berikut : cout<<"TABEL HASH : \n"; for (int I=1;I<=p;I++) { cout<data.key<<" , "; Q=Q->next; } } cout<<"Rerata probe : "<<(float)s/n; 72
Untuk mencari data kamus tertentu pada tabel hash diperlukan langkah-langkah sebagai berikut : 1. Membaca data key tertentu, misalkan a 2. Menghitung nilai indeks IH dari data key a, kemudian mencari data key a di tabel hash dengan indeks IH. Kode program untuk mencari data kamus pada tabel hash adalah sebagai berikut : void cari(larik H,int p) {int lokasi,i,k=1;list q;bool ada;strg a=""; cout<<"\nmasukkan data yg dicari : ";gets(a);cout<<endl; i= nilai1(a,p); ada=false; if (strcmp(a,"")!=0 && strcmp(H[i].data.key,a)==0) {ada=true;lokasi=i;cout<data.key,a)==0) { ada=true;lokasi=i;k++; cout<data.info<<endl<<endl;} else {q=q->next;k++;} } } else ada=false; if (ada) {cout<<"data ada di "<
73
5.5 Latihan Soal 1. Buatlah program untuk menyimpan sejumlah N data mahasiswa yang terdiri dari NIM, Nama, dan IPK, lalu buatlah fungsi untuk menampilkan data mahasiswa dengan NIM tertentu. 2. Buatlah program pencarian biner secara rekursif. 3. Jika diketahui data key adalah :
70, 89, 92, 17, 71, 86, 24, 3, 34, 75, 21, 77, 7, 74, 35
Menggunakan fungsi hash dengan metode sisa pembagian (key mod P1) + 1, tempatkan key tersebut pada larik H1, jika terjadi tabrakan gunakan metode linked dan kemudian tentukan rata-rata pencariannya. {P1: bilangan prima terkecil yang >= n}
selanjutnya tempatkan key tersebut pada larik H2, jika terjadi tabrakan gunakan linear probing dan kemudian tentukan rata-rata pencariannya. 4. Buatlah sebuah program untuk menyelesaikan proses mapping pada nomor telepon yang ada di Telkom dengan menggunakan metode Hashing. Data yang ada berupa struktur yang terdiri dari no telpon, nama, alamat pelanggan. Program memberikan pilihan berupa menampilkan data, menambah data, menghapus data. 5. Buatlah sebuah program untuk menyelesaikan proses mapping pada sistem jaringan komputer yang ada di PENS dengan menggunakan metode Hashing. Data yang ada berupa struktur yang terdiri dari no IP, nama komputer, letak komputer. Program memberikan pilihan berupa menampilkan data, menambah data, menghapus data.
74
BAB VI PENGENALAN OOP
6.1 Pendahuluan Deskripsi singkat : Bab ini menjelaskan tentang pengenalan bahasa pemrograman java dan teori serta konsep dasar object oriented programming (OOP). Manfaat : Mahasiswa memahami tentang paradigma OOP dan teori serta konsep dasar OOP yang semakin banyak digunakan untuk menyelesaikan masalah pemrograman. Relevansi : Paradigma pemrograman OOP yang merupakan paradigma pemrograman yang dikembangkan dari fasilitas tipe data turunan di dalam pemrograman terstruktur Learning Outcomes : Mahasiswa memiliki pengetahuan mengenai teori dan konsep Object Oriented Programming. Alokasi dan waktu : Bahan yang ada pada bab ini membutuhkan alokasi waktu kurang lebih 300 menit, dan disampaikan pada minggu ketigabelas dan keempatbelas perkuliahan. Pemrograman berorientasi objek (OOP) adalah suatu metode pemrograman yang berorientasi kepada objek. Tujuan dari OOP diciptakan adalah untuk mempermudah pengembangan program dengan cara mengikuti model yang telah ada di kehidupan seharihari. Jadi setiap bagian dari suatu permasalahan adalah objek, nah objek itu sendiri merupakan gabungan dari beberapa objek yang lebih kecil lagi. Sebagai contoh misalkan Mobil, Mobil adalah sebuah objek, yang terbentuk dari beberapa objek yang lebih kecil lagi seperti mesin, roda, bodi, kursi, dll. Mobil sebagai objek yang terbentuk dari objek-objek yang lebih kecil saling berhubungan, berinteraksi, berkomunikasi dan saling mengirim pesan kepada objekobjek yang lainnya. Begitu juga dengan program, sebuah objek yang besar dibentuk dari beberapa objek yang lebih kecil, objek-objek itu saling berkomunikasi, dan saling berkirim pesan kepada objek yang lain. Sebelum dilanjutkan lebih jauh tentang teori dan konsep dasar OOP terlebih dahulu kita bahas tentang bahasa pemrograman Java.
75
6.2 Pengenalan Bahasa Pemrograman Java Java adalah satu dari beberapa kemajuan terpenting di bidang software komputer dalam 20 tahun terakhir. Sama pentingnya dengan HyperText Markup Language(HTML) yang sangat sukses dalam penerbitan homepage statik di World Wide Web (WWW), Java menjadikan internet dengan isi yang lebih menarik dan interaktif. Ada tiga kombinasi kunci yang membuat Java menjadi teknologi yang secara fundamental berbeda dari yang lain yang ada saat ini. Pertama dan yang paling menarik adalah semua orang dapat menggunakan applet yang kecil, aman, dinamik, lintas platform, aktif dan siap dijalankan di jaringan. Sejak awal, Applet dapat disusun dan didstribusikan secara aman dalam bentuk homepage semudah aspek-aspek HTML. Kedua, Java adalah bahasa pemrograman yang ampuh dan memiliki kekuatan desain berorientasi objek dengan sintaks yang sederhana dan mudah dikenal disertai dukungan lingkungan yang kokoh serta enak digunakan. Java memungkinkan programmer untuk membuat program dan komponen dan applet baru yang lebih menarik. Ketiga, Java adalah kumpulan class objek yang ampuh sehingga dapat melayani programmer dengan uraian yang jelas untuk menerangkan berbagai fungsi sistem yang umum seperti pembuatan window, penggunaan jaringan dan input / output. Kunci class-class ini adalah kemampuannya yang dapat melayani aplikasi lintas platform untuk beragam variasi yang umum digunakan sebagai antarmuka sistem. 1. Sejarah Java Java mulai dirilis pada tahun 1990 sebagai bahasa program yang disebut Oak, Kemudian Sun MycroSystem mendirikan kelompok kerja yang terdiri atas para programmer handal untuk membuat produk baru dan memperluas pasar Sun. Oak didesain pertama kali untuk personal digital assistance yang disebut *7 yang akan dipasrkan Sun dengan fasilitas Graphical User Interface. Ternyata *7 tidak pernah dipasarkan dan secara kebetulan Sun membentuk suatu perusahaan yang disebut Firstperson untuk mengembangkan *7 dalam bentuk TV set-top boxes untuk televisi interaktif. Karena persaingan yang begitu ketat akhirnya prospek TV interaktif menurun dan akhirnya Oak tidak laku di pasaran. Akan tetapi semenjak FirstPerson dan Oak mengalami kegagalan bermunculanlah para perintis internet khususnya World Wide 76
Web seperti Netscape yang mulai membuat software yang memungkinkan terjadinya koneksi antara Internet dengan WWW. Sun akhirnya menyadari bahwa Oak memiliki kemungkinan besar untuk membuat jalur akses ke dunia Web. Tidak lama kemudian Oak diluncurkan di Internet dengan nama baru, yaitu Java. Sekarang ini Java masih dalam taraf pengembangan dan sudah mulai mempengaruhi arah pemrogaman komputer dan internet. Bahasa pemrograman Java dirilis secara gratis di internet dan Sun memberikan lisensi penuh terhadap implementasi Java dan segala komponennya untuk digunakan di berbagai vendor software Internet dengan harapan supaya dapat menciptakan standard bagi pemrograman web Modul objek Java adalah sederhana dan mudah dikembangkan namun sejalan dengan itu, bilangan dan tipe data sederhana lain dianggap sebagai non objek berkinerja tinggi. Kebanyakan sistem berorientasi objek lain memilih hirarki objek yang kaku dan susah diatur atau memilih menggunakan model objek dinamik yang tidak memiliki kinerja tinggi dan kelengkapan . Java sekali lagi memiliki keseimbangan yang menyediakan mekanisme pengclass-an sederhana dengan model antarmuka dinamik yang intuitif hanya jika diperlukan. Memahami gaya pemrograman berorientasi objek sangat penting dan membantu mempelajari bagaimana membuat program dengan Java. 2. Contoh Program Java Seperti pada umumnya belajar bahasa pemrograman, kita akan langsung menulis, mengcompile dan menjalankan program "Hello World" yang banyak digunakan sebagai contoh, kemudian kita akan menelusuri contoh sederhana ini baris demi baris untuk mengenal dasar pemrograman Java. Setelah itu, kita akan mendefinisikan semua unsur penting tata bahasa yang diterima oleh compiler Java termasuk spasi kosong (whitespace), komentar (comment), kata kunci (keywords), pengenal (identifier), literal, operator dan pemisah (separator). Di akhir bab, kita telah melengkapi bangunan fondasi bahasa Java sehingga anda mungkin telah mampu mengenal dan menemukan cara sendiri untuk membuat program Java yang baik.
77
Hello World class HelloWorld { public static void main ( String args[] ) { System.out.println ( "Hello World ") ; } } Java membutuhkan semua program berada dalam suatu class yang diberi nama tertentu. Anda harus menyimpan file teks ini dalam file dengan nama HelloWorld.java; pastikan besar kecilnya huruf nama file sama dengan nama class. Peraturan penggunaan nama file yang sama dengan nama class ini nantinya akan membantu saat anda menjalankan program. Java memiliki delapan tipe data sederhana, yaitu: byte, short, int, long, char, float, double dan Boolean. Berikut ini adalah pembahasan masing-masing tipe data : Berikut ini adalah contoh program mengenai tipe data class SimpleType { public static void main (String args[] ) { byte b=100; short s=30000; int i = 1000000; long l = 4123456789; char c = 'a'; double d = .00001234; boolean bool = true; System.out.println("byte b = "+b); System.out.println("short s = "+s); System.out.println("int i = "+i); System.out.println("long l = "+l); System.out.println("char c = "+c); System.out.println("double d = "+d); System.out.println("boolean bool = "+bool); } } 78
Hasilnya adalah : byte b
= 100
short s
= 30000
int i
= 1000000
long l
= 4123456789
char c
=a
double d
= 1.234E-005
boolean bool = true
6.3 Prinsip dasar OOP 1. Enkapsulasi Semua program pada tingkat paling sederhana terdiri dari dua hal: program dan data. Pada model pemrograman tradisional data dialokasikan pada memori dan diolah oleh program yang ada dalam subrutin atau fungsi. Enkapsulasi program yang mengolah data dengan deklarasi dan penyimpanan data adalah kunci dari rancangan berorientasi objek. Enkapsulasi dapat dipikirkan sebagai bungkusan pelindung program dan data yang sedang diolah. Pembungkus ini mendefinisikan perilaku dan melindungi program dan data agar tidak diakses sembarangan oleh program lain Pada Java, dasar enkapsulasi adalah class. Anda membuat suatu class yang menyatakan abstraksi dari sekelompok objek yang berbagi struktur dan sifat yang sama. Objek adalah keadaan tertentu suatu class yang memepertahankan struktur dan sifat sebagaimana didefinisikan oleh class tersebut seolah-olah keluar dari cetakan class yang sama. Objek-objek ini sering di sebut sebagai instan dari class. Struktur tertentu atau representasi data dari suatu class didefinisikan oleh sekumpulan variabel instan. Variabel-variabel ini menyimpan keadaan dinamis setiap instan suatu class. Sifat dan antarmuka suatu class didefinisikan dengan methods yang beroperasi pada data instan tersebut. Method adalah perintah untuk melakukan beberapa aksi terhadap sebuah objek. Perintah ini sangat mirip dengan pemanggilan subrutin dalam bahasa prosedural. Karena tujuannya mengkapsulasi kesulitan ada mekanisme untuk menyembunyikan kerumitan implementasi dari class. Setiap method atau variable dalam class menunjukkan semua yang perlu atau harus diketahui oleh pemakai. Anda dapat menyatakan method dan 79
data instan sebagai private sehingga tidak dapat diakses oleh program lain di luar implementasi class anda. Interface public harus dipilih dengan hati-hati supaya tidak terlalu banyak membuka bagian dalam class. Enkapsulasi ini bekerja dua arah karena anda yakin tidak akan secara tidak sengaja mempengaruhi bagian lain system dengan program dan data private anda dapat membuat program dan dengan bebas dan nyaman dan menelusuri program dengan penuh kepastian. Apa beda class dengan instan? Class adalah sesuatu yang menjelaskan atribut dan umum sebuah objek termasuk tipe setiap atribut method yang dapat mengoperasikan objek tersebut . Sebuah instance adalah keadaan tertentu sebuah class objek. 2. Inheritansi Sebagian besar kita melihat lingkungan kita sebagai objek yang saling terhubung secara hirarkis, misalnya binatang, mamalia dan anjing. Jika kita ingin menggambarkan binatang secara garis besar kita dapat mengatakan binatang memiliki ciri-ciri tertentu misalkan ukuran kecerdasan dan jenis sistem kerangka tulangnya. Binatang juga memiliki aspek perilaku tertentu mereka makan bernafas dan tidur. Penjelasan tentang struktur tubuh dan perilaku ini adalah penjelasan class binatang. Jika anda ingin menjelaskan lebih terinci suatu class binatang misalkan mamalia maka harus dirinci ciri-ciri lain misalkan jenis gigi dan periode kehamilan. Ini dikenal sebagai subclass binatang di mana binatang adalah super class mamalia. Karena mamalia secara sederhana lebih tepat dikhususkan sebagai suatu kelompok binatang maka mamalia mewarisi (inherit) semua ciri-ciri binatang. Secara lebih mendalam penurunan subclass diturunkan dari setiap moyang-nya dalam hirarki class. Inheritansi juga berinteraksi dengan enkapsulasi. Jika suatu class tertentu mengenkapsulasi sejumlah atribut. maka subclass manapun akan memiliki atribut yang sama ditambah dengan bagian dari spesialisasinya. Ini adalah konsep kunci yang membuat kerumitan program berorientasi objek berkembang secara linier tidak geometris. Sub-class yang baru mencakup semua perilaku dan spesifikasi moyangnya. Sub-class tersebut tidak memiliki interaksi tak terduga dengan sebagian besar bagian program di sistem.
80
3. Polimorfisme Methode pada objek adalah informasi yang dilewatkan sebagai parameter untuk permintaan method / parameter ini mewakili nilai yang dimasukkan ke suatu fungsi dan harus dikerjakan oleh suatu method. Pada bahasa pemrograman fungsional yang lain untuk melengkapi dua pekerjaan yang berbeda diperlukan dua fungsi terpisah dengan nama yang berbeda. Polimorfisme yang berarti satu objek dengan banyak bentuk adalah konsep sederhana yang memperbolehkan method memiliki beberapa implementasi yang dipilih berdasarkan tipe objek yang dilewatkan pada pengerjaan metode. Ini dikenal sebagai overloading method.
6.4 Pengertian dan implementasi instance dalam Java CLASS : Referensi Objek Class mendefinisikan bentuk dan sifat suatu objek.setiap class baru yang anda dapat buat menambahkan tipe lain yang dapat diperlakukan sebagai tipe sederhana. Jadi, jika Anda mendeklarasikan variabel baru, Anda dapat menggunakan nama suatu class sebagai tipenya. Variabel seperti itu kemudian merujuk pada instans atau objek class tersebut. Variabelvariabel ini dikenal sebagai referensi objek. Semua referensi objek juga cocok dengan instan sub-class dari tipe-tipe yang dideklarasikannya. Seperti kita menyatakan byte untuk variabel yang dideklarasikan int, Anda boleh juga mendeklarasikan sebuah variabel sebagai Object dan menyimpan sebuah referensi ke suatu instans dari sembarang sub-class Object. Variabel Instans Data dienkapsulasi dalam suatu class dengan mendeklarasikan variabel di antara tanda kurung kurawal deklarasi class. Variabel yang dideklarasikan dalam cakupan ini dikenal sebagai variabel instans. Cara mendeklarasikan variabel instans sama persis dengan cara yang kita lakukan untuk mendeklarasikan variabel lokal dalam contoh-contoh sebelumnya, kecuali Anda mendeklarasikannya di luar cakupan method tertentu, seperti main. Contohnya berikut ini adalah program yang mendeklarasikan class dengan nama Point dengan dua variabel instans integer bernama x dan y. class Point { int x , y; } 81
Operator new Operator new menghasilkan instans tunggal dari suatu class dan menghasilkan referensi ke objek tersebut. Berikut ini contoh sebuah instans baru dari Point yang dibuat dan disimpan dalam variabel p. point p = new point() Di sini p adalah referensi ke sebuah instans dari Point. Berikut ini contoh yang menghasilkan objek Point tunggal , tetapi menciptakan dua variabel yang merujuk kepadanya. Point p = new point(); Pointp2 = p; Perubahan apapun ke objek yang dirujuk p2 akan mempengaruhi objek yang sama yang dirujuk oleh p. Pernyataan p ke p2 tidak mengalokasikan memori atau menyalin bagian apapun dari objek asli. Kenyataannya , pernyataan untuk p pada baris kedua contoh di atas akan melepaskan kaitan p dari objek asli tanpa mempengaruhi objeknya, seperti contoh berikut Point p = new point(); Point p2 = p ; P = null; Meskipun p telah dibuat null , p2 tetap menunjuk ke objek yang dibuat dengan operator new. Operator Dot (.) Operator dot (.) digunakan untuk mengakses variabel instans dan method di dalam objek. Berikut ini bentuk umum untuk mengakses variabel instans dengan operator dot. 0bjectreference . variablename Di sini objectreference adalah referensi ke suatu objek dan variablename adalah nama variabel instans di dalam objek yang ingin anda akses. Cuplikan program berikut ini menunjukkan bagaimana operator dot dapat digunakan untuk menyimpan suatu ke dalam variabel instan. p.x = 10 ; p.y = 20 ;
82
Baris program berikut ini menunjukkan bagaimana merujuk ke suatu nilai variabel instans dengan operator dot. System.out.println("x = " + p.x + " y = " + p.y); Deklarasi method Method dideklarasikan di dalam definisi class di tingkat yang sama dengan variabel instans. Anda harus memanggil method dalam konteks instans tertentu class tersebut. Method dapat merujuk langsung ke variabel instans tanpa menggunakan operator dot seakan-akan mereka itu variabel local yang dideklarasikan di luar cakupan. Method dideklarasikan untuk memiliki nilai keluaran dengan tipe tertentu dan sekumpulan parameter masukan.. Bentuk umum deklarasi method adalah : type method name (formal-parameter-list) { method-body; } type adalah tipe besaran yang akan dikeluarkan oleh method, termasuk void jika tidak ada nilai yang akan dikeluarkan. Method name adalah sembarang identifier yang berlaku selain yang telah dipakai untuk nama class di dalam cakupan yang bersangkutan. formal-parameter-list adalah urutan pasangan tipe dan identifier yang dipisahkan dengan koma. Pemanggilan method Method dipanggil pada instans suatu class dengan menggunakan operator dot (.). Bentuk umum pemanggilan method ditunjukkan di bawah ini ; Objectreference.methodname (parameter-list) Objectreference adalah sembarang variabel yang merujuk ke suatu objek , method name adalah nama suatu method dalam class yang dideklarasikan sebagai objectreference, dan parameter-list adalah besaran atu pernyataan yang dipisahkan dengan koma yang jumlah dan tipenya cocok dengan method yang dideklarasikan sebagai method name dalam class yang bersangkutan. Point p = new (Point); p.init(10 , 20) ; 83
Contoh ini membuat instan baru dari Point , menyimpan referensinya dalam p. Kemudian operator dot digunakan untuk memanggil method init pada instans yang bersangkutan, melewatkan 10 dan 20 secara berurutan untuk parameter a dan b . Pernyataan x ke 10 dan y ke 20 dilakukan dan method menghasilkan nilai. this Java memasukkan suatu besaran referensi khusus yang disebut this yang digunakan di dalam method yang dirujuk untuk objek yang sedang berlaku. Nilai this merujuk pada objek dimana method yang sedang berjalan dipanggil. Anda dapat menggunakan this disembarang tempat dimana dibutuhkan referensi ke suatu objek dari class yang berlaku. Pada contoh sebelum ini kita menggunakan p.init tetapi saat kita berada pada method init, this akan menunjuk ke objek yang sama dengan p. Jika objek lain mnggunakan program yang sama dikirim melalui instans lainnya maka masing-masing objek tersebut akan memiliki hasil this-nya sendiri. Di dalam Java tidak diperbolehkan mendeklarasikan dua variabel lokal dengan nama yang sama di dalam cakupan yang sama. Yang menarik, diperbolehkan untuk mendeklarasikan variabel lokal termasuk parameter formal suatu method yang tumpang tindih dengan nama variabel instan. Anda akan melihat bahwa kita tidak menggunakan x dan y sebagai nama parameter untuk method init karena mereka akan menyembunyikan variabel instan x dan y sebnarnya untuk cakupan method tersebut. Jika kita lakukan, maka x akan merujuk pada parameter formal, menyembunyikan variabel instan x. this justru memperbolehkan kita merujuk langsung ke objeknya sendiri bukannya membiarkan cakupan yang berlaku mendefinisikan aturan-aturan resolusi variabel kita. Berikut ini versi lain init yang menggunakan x dan y untuk nama parameter formal dan kemudian menggunakan this untuk mengakses variabel instans objek yang berlaku pada saat itu. void init (int x, int y) { this.x = x ; this.y = y; } Contoh TwoPoints dapat memanfaatkan method inisialisasi baru untuk init seperti ditunjukkan di bawah ini 84
class Point { int x; int y; void init (int x, int y) { this.x = x; this.y = y; } } class TwoPointsInit { public static void main( String args[] ) { Point p1 = new Point(); Point p2 = new Point(); p1.init(10, 20); p2.init(42, 99); System.out.println("x = "+ p1.x + " y = "+ p1.y); System.out.println("x = "+ p2.x + " y = "+ p2.y); } } Contoh ini menunjukkan pembuatan dua objek Point dan method init mereka yang terkait yang dipanggil dengan pasangan nilai yang berbeda. Keluaran program ini sama dengan contoh program TwoPoints sebelumnya. Konstruktor Menginisialisasi semua variabel dalam class setiap kali instans dibuat sangatlah membosankan. Bahkan jika anda membuat fungsi yang sederhana seperti init dia atas tetap lebih sederhana dan singkat jika semua yang diperlukan telah siap saat objek dibuat. Untuk alasan ini, class dapat mengimplementasikan method khusus yang disebut konstruktor. Konstruktor adalah method yang menginisialisasi objek segera setelah pembuatannya. Konstruktor tersebut memiliki nama yang sama persis dengan class tempatnya. Sebenarnya anda tidak dapat membuat method yang bernam sama dengan class-nya. Sekali didefinisikan, konstruktor secara otomatis segera dipanggil sebelum operator new selesai bekerja. Konstruktor kelihatan agak aneh karena tidak memiliki tipe keluaran, bahkan tidak memiliki void sekalipun. Ini karena tipe hasil implisit konstruktor adalah menginisialisasi semua keadaan internal suatu objek sehingga program yang menghasilkan instan dengan operator new akan segera memiliki objek yang baik dan berguna. 85
Berikut ini adalah class point, di sini dapat kita lihat bagaimana cara menginisialisasi kedua variabel instans sambil membentuk objek. Disini method init dari contoh terakhir digantikan dengan method yang kelihatannya sangat mirip tetapi berbagi nama dengan class-nya dan tidak memiliki tipe hasil. class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } } class PointCreate { public static void main(String args[] ) { Point p = new Point( 10, 20); System.out.println("x = " + p.x +" y = " + p.y); } } Method konstruktor dipanggil tepat setelah instans dibuat dan sebelum new menghasilkan nilai untuk pemanggilnya. Daftar parameter yang dispesifikasikan setelah nama class dalam pernyataan new digunakan untuk melewatkan parameter ke konstruktor yang tepat. Contoh sebelumnya yang menggunakan newPoint() memanggil konstruktor Point(), yang dibuat default oleh konstruktor object () superclass. Overloading Method Dalam pemrograman Java, mungkin kita seringkali menginginkan pembuatan lebih dari satu method dengan nama sama tetapi dengan daftar parameter yang berbeda. Ini disebut overloading method. Overloading method digunakan untuk melayani sifat polimorfik Java. Contoh berikut ini adalah versi class Point yang menggunakan overloading method untuk menghasilkan konstuktor alternatif yang membuat beberapa nilai default untuk koordinat x dan y. class Point { int x; int y; Point(int x, int y) { this.x = x; 86
this.y = y; } Point() { x = -1; y = -1; } } class PointCreateAlt { public static void main(String args[] ) { Point p = new Point(); System.out.println("x = " + p.x +" y =" + p.y); } } Contoh ini menghasilkan sebuah objek Point yang memanggil konstruktor kedua tanpa parameter, berbeda dengan yang pertama. Ini adalah keluarannya. x = -1 y = -1 This pada Konstruktor Pengembangan dan perbaikan lebih lanjut menunjukkan bagaimana satu konstruktor dapat memanggil konstruktor lainnya untuk menghasilkan instan yang jelas. Seringkali sangat baik untuk membangun konstruktor terhadap konstruktor lainnya sehingga class yang anda buat dapat brkembang lebih lancar dalam siklus pengembangan. Contohnya: class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } Point() { this(-1,-1); } } Konstruktor kedua sekarang memanggil yang pertama untuk menyelesaikan inisialisasi instans. Anda juga dapat membuat method non-konstruktor yang menggunakan overloading. Berikut ini adalah contoh yang menambahkan dua versi dari suatu method yang distance untuk class 87
Point. Fungsi distance menghasilkan jarak Eucleidean antara dua Points. Satu method membutuhkan pasangan x dan y dan yang lainnya membutuhkan objek Point yang lain. Pada contoh ini, method sqrt di class Math digunakan untuk menghitung akar kuadrat parameternya. class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } float distance (int x, int y) { } double distance(int x, int y) { int dx = this.x - x; int dy = this.y - y; return Math.sqrt (dx*dx + dy*dy); } double distance(Point p) { return distance(p.x, p.y); } } class Point Dist { public static void main(String args[] ) { Point p1 = new Point(0, 0); Point p2 = new Point(30, 40); System.out.println("p1 = "+ p1.x +", "+ p1.y); System.out.println("p2 = "+ p2.x +", "+ p2.y); System.out.println("p1.distance(p2) = " +p1.distance(p2)); System.out.println("p1.distance(60, 80) = "+ p1.distance(60, 80)); } } Contoh ini menunjukkan bagaimana suatu method dapat dioverload agar memiliki dua cara alternatif untuk menjalankan proses komputasi yang sama. Perhatikan bahwa bentuk kedua dari distance memanggil bentuk pertama untuk nilai keluarannya. Berikut ini keluaran contoh tersebut. p1 = 0, 0 p2 = 30, 40 88
p1.distance(p2) = 50 p1.distance(60, 80) = 100 Inheritansi Dasar kedua mekanisme berorientasi objek adalah inheritansi. Inheritansi adalah konsep yang memetakan hubungan class dengan class lainnya secara hirarkis. Ini memungkinkan turunan dari suatu class mewarisi semua variabel dan method dari moyangnya dan juga membuat miliknya sendiri. Turunan ini disebut sub-class. Moyang langsung suatu class disebut superclass. Sekali anda membuat class seperti Point, sangat mudah untuk membuat subclass darinya subclass adalah versi khusus suatu class yang mewarisi semua variabel instns dan metodenya. Pada contoh ini, kita mengembangkan class Point untuk mengikutkan komponen ketiga yang disebut z. class Point3D extends Point { int z; Point3D(int x, int y, int z) { this.x = x; this.y = y; this.z = z; } Point3D0() { this(-1, -1, -1); } } kata kunci extends digunakan untuk menegaskan bahwa kita ingin membuka sub-class dari point. Seperti yang anda dapat lihat, variabel x dan y tidak perlu dideklarasikan dalam Point3D karena sudah diwarisi dari Point. Java memungkinkan kita untuk mendeklarasikan variabel x dan y dalam Point3D yang akan menyembunyikan x dan y dari Point. Akan tetapi ini akan tetapi ini akan merusak tujuan pengsub-class-an dan sebaiknya dihindari. Ada perlakuan khusus untuk x dan y berkaitan dengan z. Mereka semua ada dalam cakupan yang sama dari sudut instans Point3D. Super Pada contoh Point3D ada bagian program dari superclass yang diulang oleh Point yaitu bagian yang menginisialisasi x dan y ada pada kedua class. 89
this.x
=
x;
this.y = y; Mirip dengan cara kita menggunakan this untuk merujuk ke konstruktor pertama pada contoh Point, ada variabel khusus lain dalam Java yang disebut super yang merujuk langsung ke konstruktor superclassnya. Berikut ini adalah contoh program yang mendsfinisikan versi baru Point3D yang menggunakan konstruktor super untuk menginisialisasi variabel x dan y lalu mencetak hasil keluaran Point3D. class Point3D extends Point{ int x; Point3D(int x, int y, int z) { super(x, y); //memanggil konstruktor Point(x, y) this.z = z; } public static void main (String args[] ) { Point3D p = new Point3D(10, 20, 30); System.out.println("x = "+p.x + "y =" +p.y +" z = " +p.z); } } keluaran program ini adalah seperti berikut : x = 10, y = 20, z =30 Rferensi super juga dapat digunakan untuk langsung mengirim method dengan nama tertentu seperti mengirim konstruktor. Anda dapat memperlakukan super sebagai suatu versi dari this yang merujuk ke superclsnya. Jadi suatu pernytaan seperti super.translate(x, y) berarti memanggil method translate milik superclass untuk instans this. Overidding method Subclass baru Point ini mewarisi implementasi method distance dari superclassnya. Katakanlah bahwa untuk mengukur jarak antara titik 3D dengan 2D, komponen x dan y 3D harus dibagi dulu dengan z. masalahnya Point sudah mendefinisikan satu versi distance (int x, int y) yang secara sederhana menghasilkan jark euclidean 2D. kita harus meng-override dfinisi trsbut dengan yang baru untuk 3D. Contoh berikut ini mengimplementasikan ovrloading distance 3D dan overriding distance 2D. class Point { int x, y; 90
Point(int x, int y) { this.x = x; this.y = y; } double distance (int x, int y) { int dx = this.x - x; int dy = this.y - y; return math.sqrt(dx*dx + dy*dy); } double distance(Point p) { return distance(p.x, p.y); } } class Point3D extends Point { int z ; Point3D(int x, int y, int z) { super(x, y); this.z = z ; } double distance(int x, int y, int z) { int dx = this.x - x; int dy = this.y - y; int dz = this.z -z; return Math.sqrt(dx*dx + dy*dy + dz*dz); } double distance(Point3D other) { return distance(other.x, other.y, other.z); } double distance(int x, int y) { double dx = (this.x / z) - x; double dy = (this.y / z)- y; return math.sqrt(dx*dx + dy*dy); } } class Point3DDist { public static void main(String args[] ) { Point3D p1 = new Point3D(30,40, 10); Point3D p2 = new Point3D(0, 0, 0); Point p = new Point (4, 6); 91
System.out.println("p1 = " + p1.x + ", "+ p1.y + ", " +p1.y); System.out.println("p2 = " + p2.x + ", "+ p2.y + ", " +p2.y); System.out.println("p = " + p.x + ", "+ p.y + ", " +p.y); System.out.println ("p1.distance(p2) = "+ p1.distance(p2)); System.out.println ("p1.distance(4, 6) = "+ p1.distance(4, 6)); System.out.println ("p1.distance(p)= "+ p1.distance(p)); } } Hasilnya adalah p1 = 30, 40, 10 p2 = 0, 0, 0; p = 4, 6 p1.distance(p2) = 50.9902 p1.distance(4, 6) = 2.23607 p1.distance(p) = 2.23607 Keluaran program tersebut menunjukkan sesuatu yang sangat penting. Perhatikan bahwa kita mengharapkan jarak antara dua titik 3D dan pasangan 2D (4, 6). Saat kita panggil distance pada objek Point3D dengan Point2D maka kita akan mengeksekusi method distance yang diturunkan dalam class Point karena Point3D tidak meng-override method distance (Point p) dalam Point. Bagian yang mengejutkan adalah kita selanjutnya memanggil method distance (int x, int y) dalam Point3D bukan dalam Point. Method dipilih berdasarkan tipe instan saat program berjalan bukan berdasarkan class dimana method yang brjalan dieksekusi. Ini disebut pengiriman mthod dinamis (dynamic method dispatch ). Pengiriman Method Dinamis Saat anda memanggil method dengan operator dot pada sebuah referensi obyek. Tipe referensi objek yang dideklarasikan diperiksa saat dicompile untuk memastikan bahwa method yang dipanggil ada di dalam class yang dideklarasikan. Saat dijalankan referensi objek dapat merujuk ke suatu instan dari subclass peda tipe yang dideklarasikan. Dalam kasus ini Java ,menggunakan instans yang ada untuk memutuskan method mana yang dipanggil. Sebagai contoh ambil dua class ini yang memiliki method tunggal yang dioverride dalam subclass tersebut. class a { void callme() { System.out.println("inside A's callme method "); } 92
} class b extends a { void callme() { System.out.println("inside B's callme method "); } } class Dispatch { public static void main(String args [] ) { a a = new b(); a.callme(); } } Yang menrik disini adalah di dalam method main kita mendeklarasikan variabel sebagai tipe a, kemudian di dalamny disimpan suatu referensi ke suatu instans dari class b. pada baris selanjutnya dimana kita memanggil method callme pada a, compiler Java memastikan apakah a tersebut memiliki method callme. Tetapi runtime Java melihat bahwa referensinya sebenarnya adalah instans dari b jadi runtime kan mmanggil method callme milik b, bukan milik b. Keluaran program tersebut ditunjukkan di bawah ini : Inside B's callme method Bentuk polimorfisme runtime dinamis ini adalh salah satu mekanisme paling ampuh yang dimiliki oleh rancangan berorientasi objek untuk menangani penggunaan kembali program. Kemampuan library program untuk memanggil method pada instans class baru tanpa melakukan compile ulang merupakan sarana yang terbukti sangat ampuh. Final Semua method dan variabel instan dapat di-override secara default. Jika anda ingin mendeklarasikan bahwa anda ingin subclass mengoverride variabel atau method anda, anda dapat mndeklarasikannya sebagai final. Pengubah tipe final mengakibatkan semua refrensi selanjutnya
untuk
unsur
ini
akan
bergantung
pada
definisi
ini.
Contoh : Final int FILE_NEW =1; Final int FILE_OPEN = 2; 93
Final int FILE_SAVE = 3; Final int FILE_SAVEAS = 4; Final int FILE_QUIT = 5; Anda dapat menggunakan final sebagai pengubah deklarasi method jika anda ingin subclass tidak mengoverride method tertentu. Method yang dideklarasikan sebagai final kadangkadang dapat menghasilkan peningkatan kinerja karena compiler bebas untuk memanggil mereka secara in-line, tidak mungkin method-method tersebut dioverride secara tidak diduga oleh suatu subclass. Sudah menjadi kesepakatan umum pemrograman bahwa semua identifier ditulis dengn huruf besar semua untuk variabel final. Variabel final tidak mengambil ruang sedikitpun dalam basis per instan. Dalam hal ini penggunaan final sama dengan static yang akan dijelaskan selanjutnya. Finalize Finalisasi sangatlah sederhana. Anda tinggal mnambahkan ke semua class sebuah method yang disebut finalize. Dan runtime Java memanggil method tersebut ketika waktunya untuk mengambil ruang untuk objek tersebut. Method finalize harus secara eksplisit mengambil tindakan yang diperlukan untuk membebaskan sumber dari luar. Pengmpul sampah (garbage collector method) berjalan secara periodik memerikasa objek mana yang tidak lagi dirujuk oleh keadaan yang sedang berjalan atau secara tidak langsung melalui objek yang dirujuk. Tepat sebelum suatu bagian dibebaskan Java memanggil method finalize pada suatu objek. Static Kadang-kadang anda ingin membuat suatu method yang digunakan di luar konteks semua instan. Seperti method main pada contoh-contoh awal yang perlu anda lakukan adalah mendeklarasikan method ini sebagai static dan semua akan berjalan semestinya. Method static hanya boleh memanggil method static lain ecara langsung dan mereka tidak boleh merujuk ke this atau super dengan cara apapun. Variabel boleh saja dideklarsikan static tetapi anda harus memperhatikan bahwa ini menjadi deklarasi varibel global yang dapt diakses oleh sembarang bagian program. Jika anda ingin melakukan komputasi untuk menginisialisasi variabel static anda dapat mendeklarasikan blok static yang akan dijalankan hanya sekali, saat class pertama
94
kali diambil. Contoh berikut ini menunjukkan sebuah class yang memiliki sebuah method static sejumlah variabel static dan blok inisialisasi. class static { static int b; static int a = 3; static void method(int x) { System.out.println("x = " +x); System.out.println("a = " + a); System.out.println("b = " + b); } static { System.out.println("static block initialized"); b = a * 4; } public static void main(String args[] ) { method(42); } } Segera setelah class diambil, semua penginisialisasi variabel static berjalan yang mengisi a dengan 3 lalu menjalankan block static yang mencetak pesan dan mengisis b dengan a * 4 atau 12. Kemudian interpreter memanggil method main yang memanggil method untuk mengisikan 42 pada x. println merujuk pada dua variabel static a dan b serte variabel lokal x. Tidak diperbolehkan untuk merujuk variabel instan apapun di dalam method static. Keluaran program adalah sebagai berikut: Static block initialized x = 42 a=3 b = 12 Cara lain di mana static bermanfaat adalah untuk menghasilkan method yang dapat memanggil langsung dengan merujuk nama suatu class di mana mereka dideklarasikan. Mirip dengan bagaimana anda memanggil method dalam instan melalui variabel referensi objek, anda dapat memanggil method static apapun atau merujuk ke sejumlah variabel static menggunakan operator dot pada nama clasnya. Beginilah cara Jav mengimplementasikan fungsi dan variabel global. Keunggulan utama method dan variabel adalah class yang berisi 95
cakupan nama untuk menghindari tabrakan. Pada contoh dibawajh ini kita menghasilkan sebuah class dengan method static dan sejumlah variabel static. Class kedua dapat memanggil method static dengan namanya dan juga merujuk ke variabel static dengan langsung menyebut classnya. class StaticClass { static int a = 42; static int b = 99; static void callme () { System.out.println("a = " + a); } } class StaticByName { public static void main (String args[] ) { StaticClass.callme(); System.out.println("b = " +staticClass.b); } } inilah keluaran dari program tersebut a = 42; b = 99; Abstract Ada keadaan dimana anda perlu mendefinisikan class yang mendeklarasikan struktur abstraksi tertentu tanpa menyediakan implementasi lengkap daris setiap method. Anda dapat mendeklarasikan method yang perlu dioverride tersebut dengan subclass yang mnggunakan pengubah tipe abstract. Method ini kadang disebut tanggung jawab pengsubclassan (subclasser responsibility). Semua class yang berisi method yang dideklarasikan abstract juga harus dideklarasikn abstract. Anda tinggal menambahkan kata kunci abstract di depan deklarasi class. Class seperti itu tidak dapat mendeklarasikan konstruktor abstract juga method abstract static. Semua subclass pada class abstract harus mengimplementasikan semua method abstract. Berikut ini adalah contoh sebuah class dengan method abstract diikuti dengan sebuah class yang mengimplementasikan method tersebut. abstract class a { abstract void callme(); void metoo() { System.out.println("inside A's metoo method"); 96
} } class b extends a { void callme() { System.out.println("inside B's callme method "); } } class abstract { public static void main(String args[] ) { a a = new b(); a.callme(); a.metoo(); } } Perhatikan bagaimana class abstract mengimplementasikan method secara konkret. Class abstract dapat berisi sebanyak mungkin implementasi yang dianggap cocok. Contoh ini menggunakan pengiriman method dinamik yang telah dibahas sebelumnya untuk memanggil implementasi method callme abstract, juga method abstract metoo superclassnya. Keluaran program adalah sebagai berikut : Inside B's callme method Inside A's metoo method. Package Package adalah container class yang digunkn untuk menjaga ruang nama class tetap terbagibagi. Contohnya package memungkinkan anda dapat membuat sebuah class brnama List dimana anda dapat menyimpan package tanpa harus memikirkan apakah akan terjadi tabrakan dengan class List yang dibuat oleh orang lain. Package disimpan secara hirarkis dan secara eksplisit diimpor ke dalam definisi class baru. Jika anda melewatkan pernyataan package class dianggap berada dalam package default yang tidak mempunyai nama. Compiler Java menggunakan direktori sistem file untuk berada dalam package yang disebut myPackage, maka file sumber untuk class itu harus disimpan dalam direktori My Package. Ingat bahwa besar-kecil huruf diperhatikan dan nama direktori harus benar-benar cocok dengan nama package. Berikut ini adalah bentuk umum pernytaan package. Package pkg1[ . pkg2 [ . pkg3] ]; 97
Perhatikan bahwa anda dapat membuat hirarki package dalam package dengan cara memisahkan tiap tingkatan dengan titik. Hirarki package ini harus tergambar pad sistem file sistem pengembangan Java anda. Package yang dideklarasikan sebagai : Package java.awt.image; Harus disimpan dlam jav/awt/image atau java\awt\image atau java:awt:image masing-masing untuk sistem file UNIX, windows dan Macintosh. Interface Interface adalah spesifikasi eksplisit suatu kumpulan method yang dapat diimplementasikan class tanpa implementasi sesungguhnya yang berhubungan dengan spesifikasi tersebut. Mirip dengan class yang betul-betul abstrak, interface memiliki kemampuan tambahan sehingga dapat secara efektif diturunkan berulang-ulang. Suatu class dapat mengimplementasikan interface dengan jumlah tak terbatas meskipun hanya diturunkan dari satu superclass. Interface didefinisikan seperti class tetapi tanpa mendeklarasikan data variabel atau konstruktor apapun. Bentuk umum interface adalah interface name { return-type method-name1(parameter-list); type final-varname = value; } Di sini name adalah sembarang identifier sama seperti nama class. Perhatikan bahwa method yang dideklarasikan tidak memiliki isi method diakhiri dengan titik koma setelah daftar parameter. Hal ini terjadi karena tidak ada implementasi default untuk sebuah interface yang ada hanya daftar method. Sebuah class harus mengimplementasikan setiap method dengan pengenal tipe yang benar-benar cocok. Semua method yang mengimplementasikan interface yang dinyatakan dalam public. Variable dapat dideklarasikan di dalam deklarasi interface dan secra implisit bersifat final artinya tidak dapat diubah oleh class yang mengimplementasikan dan harus dininsialisasi dengan suatu konstanta. Berikut ini contoh definisi interface yang mendefinisikan interface sederhana yang berisi satu method yang disebut callback ayng membutuhkan satu parameter integer. interface callback { void callback(int param) 98
} class client implements callback { void callback(int p) { system.out.println("callback called with " +p); } } class testIface { public static oid main(String args[] ) { callback c =new client(); c.callback(42); } } Hasilnya adalah Callback called with 42 Perhatikan contoh diatas, variabel c dideklarasikan sebagai interface Callback dan juga dinyatakan sebagai instan dari client. Dengan cara ini, c hanya dapat digunakan untuk mengakses method callback dan tidak dapat digunakan untuk spek lain dari clas client. Contoh berikut ini menyimpan sejumlah bilangan besar ke dalam x dan y untuk menunjukkan bagaimana bilangan-bilangan tersebut disusun ulang dari byte-byte. Perhatikan bahwa x diisi 123456789 dan y diisi dengan integer posistif terbesar yang samaa dengan urutan 7f ff ff ff dalam array byte di sini interface Packable { byte[] pack(); void unpack(byte raw[] ); } class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } } class NewPoint extends Point implements Packable { 99
newPoint( int x, int y) { super(x, y); } newPoint() { this(0, 0); } private byte p(int t, int n) { return (byte) ((t >> n) & 0xff); } public byte pack()[] { byte ret[] = new byte[8]; ret[0] = p(x, 24); ret[1] = p(x, 16); ret[2] = p(x, 8); ret[3] = p(x, 0); ret[4] = p(y, 24); ret[5] = p(y, 16); ret[6] = p(y, 8); ret[7] = p(y, 0); return ret; } private int u(byte b, int n) { return (b & 0xff) << n; } public void unpack(byte raw[] ) { x = u(raw[0], 24) u(raw[1], 16) u(raw[2], 8) u(raw[3], 0); y = u(raw[4], 24) u(raw[5], 16) u(raw[6], 8) u(raw[7], 0); } public String toString() { return "NewPoint [" + x +", "+ y +"]" ; } public Pointpack { public static void main(String args[]) { Packable p = new NewPoint(123456789, 2147483647); Byte packed[] = p.pack(); NewPoint thawed = new NewPoint(); Thawed.unpack(packed); System.out.println("p = "+ thawed); } } 100
Hasilnya adalah 07 5b cd 15 7f ff ff ff = NewPoint (123456789, 2147483647)
6.5 Latihan Soal 1. Buatlah program (OOP) untuk menentukan minimum spanning tree dari graf tak berarah dengan n vertek, dengan menggunakan algoritma Prim. 2. Buatlah program (OOP) untuk menentukan minimum spanning tree dari graf tak berarah dengan n vertek, dengan menggunakan algoritma Kruskal. 3. Buatlah program (OOP) untuk menempatkan n data random (integer) kedalam table hash/array 1 dimensi dengan menggunakan fungsi hash mod prima, jika terjadi tabrakan/collision gunakan metode open addressing dengan double hashing.
101
DAFTAR PUSTAKA Adam Drozdek, 2008, Data Structures and Algorithms in Java Alfred V. Aho,dkk., 1988, Data Structures and Algorithms, Cay S. Horstmann, 2009, C++ for everyone Data Structures Using C , Tenenbaum, A., Y. Langsam, and M. Augenstein, 1990, Prentice-Hall Munir, R., 2004, Algoritma dan Pemrograman, Informatika, Bandung.
102
