DIKTAT KULIAH STRUKTUR DATA
Disusun oleh: Sri Primaini A.
FAKULTAS ILMU KOMPUTER UNIVERSITAS INDO GLOBAL MANDIRI PALEMBANG 2016
DAFTAR ISI
BAB 1 1.1 1.2 1.3 1.4
PENGANTAR KE STRUKTUR DATA........................... Mengapa Struktur Data Diperlukan?..................................... Tinjauan Algoritma................................................................ Tipe Data................................................................................ Instruksi..................................................................................
Halaman 1 1 1 2 4
BAB 2 2.1 2.2 2.3 2.4 2.5
LARIK.................................................................................. Deklarasi Larik...................................................................... Pemrosesan Larik Secara Sekuensial.................................... Larik Bertipe Terstruktur...................................................... Pencarian Pada Larik............................................................. Pengurutan Data.....................................................................
8 8 10 13 15 16
BAB 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9
SENARAI.............................................................................. Alasan Menggunakan Senarai................................................ Tipe Pointer............................................................................ Membuat Senarai Kosong...................................................... Traversal................................................................................ Penyisipan Elemen................................................................. Menghapus Elemen................................................................ Bekerja Dengan Dua atau Lebih Senarai............................... Senarai Yang Info-nya Terstruktur........................................ Multi Linked List....................................................................
18 18 21 21 22 27 32 36 41 43
BAB 4 4.1 4.2 4.3 4.4 4.5 4.6 4.7
ANTRIAN............................................................................. Pengertian Dasar.................................................................... Membuat Antrian Kosong...................................................... Memeriksa Apakah Antrian Kosong..................................... Menyisipkan Elemen (EnQueue)........................................... Menghapus Elemen................................................................ Representasi Fisik Antrian Dengan Larik.............................. Membuat Antrian Kosong, Representasi Fisik Larik............ Fungsi Untuk Memeriksa Antrian Kosong, Representasi Fisik Larik.............................................................................. Menyisipkan Elemen Antrian, Representasi Fisik Larik...... Menghapus Elemen Antrian, Representasi Fisik Larik......... Persoalan Head Maju, Menyisipkan Elemen.........................
47 47 48 48 49 50 51 51
4.8 4.9 4.10 4.11
52 52 56 59
BAB 5 5.1 5.2 5.3 5.4 5.5 5.5 5.6 5.7
TUMPUKAN........................................................................ Pengertian Dasar.................................................................... Membuat Stack Kosong......................................................... Menyisipkan Elemen............................................................. Menghapus Elemen Stack...................................................... Memeriksa Apakah Stack Kosong......................................... Representasi Fisik Tumpukan Dengan Larik......................... Menyisipkan Elemen Stack, Representasi Larik................... Menghapus Elemen Stack, Representasi Larik......................
Halaman 63 63 64 64 65 65 65 66 68
BAB 6 6.1 6.2 6.3 6.4
GRAF.................................................................................... Pengertian Dasar.................................................................... Istilah-Istilah Pada Graf......................................................... Representasi Graf................................................................... Penelusuran Graf....................................................................
71 71 72 76 77
BAB 7
POHON PENCARIAN BINER (BINARY SEARCH TREE, BST).......................................................................... Pendahuluan........................................................................... Hubungan Antar Simpul Pada BST....................................... Membuat BST Kosong.......................................................... Penelusuran Pada BST........................................................... Pencarian................................................................................ Menyisipkan Elemen............................................................. Menghapus Elemen................................................................ Menghitung Tinggi Pohon..................................................... Menghitung Jumlah Simpul................................................... Menghitung Jumlah Daun......................................................
7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10
DAFTAR PUSTAKA..........................................................................
82 82 83 84 84 86 86 87 90 90 91 92
BAB 1 PENGANTAR KE STRUKTUR DATA 1.1 Mengapa Struktur Data Diperlukan? Struktur data adalah cara mengorganisakan data di memori komputer. Bagaimana data diorganisasikan (struktur data) akan menentukan unjuk kerja program yang memroses data tersebut. Struktur data akan membuat program yang dibangun menjadi lebih efisien. Setiap tahun teknologi perangkat keras makin baik, unjuk kerja komputer makin baik, pemrosesan makin cepat, memori tersedia makin besar. Mengapa efisiensi diperlukan? Diskusikan! Struktur data selalu berkaitan dengan program. Membahas program berarti membahas algoritma. Sehingga dalam setiap bahasan struktur data pasti ada bahasan algoritma. Untuk lebih memudahkan belajar struktur data, berikut akan dibahas mengenai tinjauan instruksi dan notasi algoritma secara ringkas. 1.2 Tinjauan Algoritma Algoritma adalah urutan langkah untuk menyelesaikan masalah. Dalam konteks pemrograman algoritma adalah rancangan urutan instruksi yang nantinya akan diterjemahkan ke bahasa pemrograman dan dieksekusi oleh komputer. Secara sederhana algoritma terdiri dari tiga bagian, yaitu: 1.
Judul algoritma: memuat identitas algoritma berupa nama algoritma, keterangan mengenai proses apa yang dilakukan dalam algoritma. Jika algoritma tersebut berupa procedure atau function harus dinyatakan data yang berinteraksi dengan procedure atau function tersebut
2.
Bagian deklarasi memuat deklarasi nama dan tipe data serta subprogram (procedure dan atau function) yang digunakan di dalam algoritma.
3.
Bagian deksripsi berisi rancangan instruksi yang harus dieksekusi oleh komputer.
Struktur Data – 2 1.3 Tipe Data Tipe data menentukan himpunan nilai yang terkandung di dalam data tersebut serta operasi apa saja yang berlaku terhadap data tersebut, Secara garis besar ada dua macam tipe data, yaitu tipe data dasar dan tipe data bentukan. Tipe data dasar adalah tipe yang dapat langsung dipakai sedangkan tipe data bentukan harus didefinisikan terlebih dahulu dari tipe dasar yang ada. Tipe bentukan didefinisikan jika persoalan yang akan diprogram tidak dapat didefinisikan dengan tipe dasar yang ada. Tabel I memuat tipe data dasar secara ringkas. TABEL I TIPE DATA DASAR
Nama Tipe boolean
integer
Rentang Nilai
Operasi
benar (true), dinyatakan dengan angka 1 salah (false), dinyatakan dengan angka 0
Operasi logika:
Secara teoritis tidak terbatas, ditentukan oleh komputer dan compiler yang digunakan.
Operasi aritmatika:
and, or, not, xor
menghasilkan nilai bertipe boolean
+, -, *, div, mod
menghasilkan nilai bertipe integer
Operasi perbandingan: =, ≠, >, <, ≥, ≤
menghasilkan nilai bertipe boolean
Struktur Data – 3 Tabel I. Tipe Data Dasar (Lanjutan) Nama Tipe real
Rentang Nilai Secara teoritis tidak terbatas, ditentukan oleh komputer dan compiler yang digunakan.
Operasi Operasi aritmatika: +, -, *, /
menghasilkan nilai bertipe real Operasi perbandingan: ≠, >, <, ≥, ≤
menghasilkan nilai bertipe boolean character
string
Semua karakter yang dikenal oleh komputer. Lihat tabel kode ASCII
Operasi perbandingan:
Rangkaian karakter dengan panjang tertentu
Operasi penyambungan: + menghasilkan nilai bertipe
=, ≠, >, <, ≥, ≤
menghasilkan nilai bertipe boolean
string
Operasi perbandingan =, ≠, >, <, ≥, ≤
menghasilkan nilai bertipe boolean
Tipe Data Bentukan Didefinisikan sendiri oleh pemrogram (user defined data type), dibentuk dari satu atau lebih tipe dasar, disebut rekaman. Setiap rekaman terdiri dari satu atau lebih field. Tiap field menyimpan data dari tipe dasar atau tipe bentukan lain yang sudah didefinisikan.
Struktur Data – 4 Contoh 1.1: Tipe data bentukan type Date = record Algoritma 1.1 Contoh Tipe Data Bentukan 1.4 Instruksi Ada tiga macam instruksi di dalam algoritma, yaitu: runtunan (sequence), pemilihan dan pengulangan. Instruksi Runtunan Rangkaian instruksi yang diproses secara berurutan, mulai dari instruksi pertama sampai instruksi terakhir. Contoh 1.2: Algoritma menukar dua bilangan bulat X dengan Y. Algoritma MenukarXY {membaca masukan X dengan Y, kemudian mempertukarkan X dengan Y} Deklarasi: X,Y: integer temp: integer Deskripsi: read(X) read(Y) temp X X Y Y temp
Algoritma 1.2 Menukar Nilai Dua Bilangan
Struktur Data – 5 Instruksi Pemilihan Ada tiga macam, yaitu pemilihan dengan satu kasus, pemilihan dengan dua kasus komplementer, dan pemilihan dengan dua atau lebih kasus. Contoh 1.3: Pemilihan dengan satu kasus Algoritma untuk membaca sebuah bilangan bulat dan mencetak kata “kelipatan 3” jika bilangan yang dibaca tersebut merupakan kelipatan 3. Algoritma Kelipatan3 {membaca masukan X kemudian mencetak kata “kelipatan 3” jika bilangan tersebut merupakan kelipatan 3} Deklarasi: X: integer Deskripsi: read(X) if X mod 3 = 0 then write (“kelipatan 3”) endif
Algoritma 1.3 Mencetak “kelipatan 3” jika data masukan kelipatan tiga Contoh 1.4: Pemilihan dengan dua kasus komplementer. Algoritma untuk membaca sebuah bilangan bulat dan mencetak pesan “bilangan ganjil” jika bilangan yang dibaca tersebut bernilai ganjil dan mencetak pesan “bilangan genap” jika sebaliknya. Algoritma GanjilGenap {membaca masukan X kemudian mencetak kata “bilangan ganjil” jika bilangan tersebut bernilai ganjil dan mencetak “bilangan genap” jika sebaliknya} Deklarasi: X: integer Deskripsi: read(X) if X mod 2 = 1 then write (“bilangan ganjil”) else write(“bilangan genap”) endif
Algoritma 1.4 Menentukan ganjil atau genap
Struktur Data – 6 Contoh 1.5: Pemilihan dengan 2 atau lebih kasus Algoritma yang membaca bilangan bulat kemudian menentukan apakah bilangan tersebut positif atau negatif atau sama dengan nol. Algoritma ApakahPositif {membaca masukan X kemudian menentukan apakah bilangan tersebut positif, atau negatif atau sama dengan 0} Deklarasi: X: integer Deskripsi: read(X) if X > 0 then write (“positif”) else if X < 0 then write (“negatif”) else write (“nol”) endif endif
Algoritma 1.5 Menentukan apakah bilangan positif atau negatif atau nol Instruksi Pengulangan Ada 3 macam, yaitu dengan for-to-do, dengan while-do dan dengan repeat-until. Contoh 1.6: Pengulangan dengan for-to-do Algoritma untuk mencetak bilangan 1 sampai dengan 10 secara berurutan. Algoritma CetakFor {mencetak bilangan 1 s.d 10 secara berurutan dengan for-to-do} Deklarasi: k: integer Deskripsi: for k 1 to 10 do write(k) endfor
Algoritma 1.6 Mencetak 1 s.d. 10 dengan for-to-do Contoh 1.7: Pengulangan dengan while-do
Struktur Data – 7 Algoritma untuk mencetak bilangan 1 sampai dengan 10 secara berurutan. Algoritma CetakWhile {mencetak bilangan 1 s.d 10 secara berurutan dengan whiledo} Deklarasi: k: integer Deskripsi: k 1 while k ≤ 10 do write (k) k k + 1 endwhile
Algoritma 1.7 Mencetak 1 s.d.10 dengan while-do Contoh 1.8: Pengulangan dengan repeat-until Algoritma untuk mencetak bilangan 1 sampai dengan 10 secara berurutan. Algoritma CetakRepeat {mencetak bilangan 1 s.d 10 secara berurutan dengan repeatuntil} Deklarasi: k: integer Deskripsi: k 1 repeat write(k) k k + 1 until k > 10
Algoritma 1.8 Mencetak 1 s.d.10 dengan repeat-until
Struktur Data – 8
BAB 2 LARIK Salah satu alasan mengapa komputer digunakan untuk mengolah data adalah karena data yang diolah banyak dan dari tipe yang sama. Larik (array) adalah tempat menyimpan sekumpulan elemen data dengan tipe yang sama. Setiap elemen data diacu menggunakan indeks. Indeks menunjukkan posisi relatif elemen data tersebut di dalam kumpulannya. 2.1 Deklarasi Larik Sebelum dapat digunakan untuk menyimpan data, terlebih dulu larik harus dideklarasikan. Mendeklarasikan larik artinya memesan sejumlah tempat di memori sesuai dengan ukuran larik yang dideklarasikan. Larik bersifat statis, artinya ukuran larik harus sudah diketahui sebelum program dieksekusi dan ukuran larik tidak berubah selama program dieksekusi. Deklarasi larik artinya mendefinisikan nama lariknya, ukuran dan tipe elemen larik tersebut. Tipe elemen larik dapat bertipe dasar atau bertipe bentukan. Contoh 2.1: deklarasi larik sebagai variabel A: array[1..100] of
integer
Algoritma 2.1 Deklarasi larik sebagai variabel
Algoritma 2.1 menunjukkan deklarasi larik A dengan 100 elemen larik, semua elemen larik bertipe integer. Contoh 2.2: deklarasi larik sebagai tipe type Larik = array[1..100] of integer A: Larik
Algoritma 2.2 deklarasi larik sebagai tipe
Struktur Data – 9 Contoh 2.3: deklarasi larik menggunakan konstanta const NMAX = 100 type Larik = array[1..NMAX] of integer A: Larik
Algoritma 2.3 Deklarasi larik menggunakan konstanta Algoritma 2.1, Algoritma 2.2 dan Algoritma 2.3 sama-sama mendeklarasikan larik A bertipe integer dengan 100 elemen. Namun pada Algoritma 2.2 deklarasi larik melalui tipe bentukan, sedangkan pada Algoritma 2.3, banyak elemen larik tidak dideklarasikan secara langsung dengan angka melainkan menggunakan konstanta. Dengan deklarasi seperti Algoritma 2.3, jika diperlukan ukuran larik diubah maka kita hanya mengubah nilai konstanta NMAX. Setelah mendeklarasikan larik, komputer akan menyediakan lokasi memori sebanyak yang dideklarasikan. Gambar 2.1 mengilustrasikan lokasi memori untuk larik A. [1] [2] [3] [4] [5] [6] [7] ... ... ... ...
[99] [NMAX] Gambar 2.1 Larik A dengan NMAX elemen
Struktur Data – 10 Untuk mengacu elemen larik digunakan indeks. Nilai indeks harus terdefinisi. Indeks merupakan tipe yang memiliki keterurutan (integer atau karakter) Contoh 2.4: mengacu elemen larik A[17], artinya mengacu elemen ke-17 dari larik A A[k], artinya mengacu elemen ke-k dari larik A, tentu saja harga k harus sudah terdefinisi A[k+1], artinya mengacu elemen ke-k+2 dari larik A
2.2 Pemrosesan Larik Secara Sekuensial Pemrosesan terhadap elemen larik dilakukan secara berurutan (sekuensial) sesuai dengan indeksnya. Elemen larik diproses mulai dari elemen pertama sampai elemen terakhir (elemen dengan indeks terbesar) atau sampai elemen tertentu yang diinginkan secara berurutan. Skema umum pemrosesan larik adalah dapat dilihat pada Algoritma 2.4 Algoritma PemrosesanLarik {Skema pemrosesan larik secara beruntun} Deklarasi: const NMAX = 100 {maksimum elemen larik} type Larik = array[1..NMAX] of integer A: Larik k: integer
{indeks larik}
Deskripsi: for k 1 to NMAX do Proses(A[k]) endfor
Algoritma 2.4 Skema Umum Pemrosesan Larik Proses(A[k]) adalah aksi tertentu terhadap elemen A[k], tergantung persoalan yang akan diselesaikan.
Struktur Data – 11 Konstanta NMAX menyatakan maksimum banyaknya elemen larik. Terkadang banyak data yang akan disimpan tidak mencapai NMAX. Misalnya ada N elemen data yang akan disimpan di dalam larik, maka dari NMAX elemen larik yang efektif terpakai untuk menyimpan ada hanya N elemen. N disebut indeks efektif larik. Tentu saja N <= NMAX. Pada Gambar 2.2, bagian larik yang diarsir adalah bagian yang digunakan untuk menyimpan data. [1] [2] [3] [4] [5] [6] [7] ... ... ... ... [N]
[99] [NMAX] Gambar 2.2 Larik A[1..N] elemen Contoh 2.5: mengisi larik melalui pembacaan Larik yang sudah dideklarasi belum terdefinisi nilainya. Kita dapat menyimpan data ke dalam larik tersebut. Data yang akan disimpan dapat diperoleh dari operasi pembacaan melalui piranti masukan (keyboard). Algoritma 2.5 adalah proses mengisi larik melalui operasi pembacaan. Untuk menyederhanakan penulisan, maka pada contoh-contoh selanjutnya larik yang akan digunakan adalah larik seperti deklarasi pada Algoritma 2.4. Selain itu semua contoh algoritma pemrosesan larik akan disajikan dalam bentuk sub program baik dalam prosedur maupun fungsi.
Struktur Data – 12
procedure BacaLarik(output A: Larik, input N: integer) {mengisi elemen larik A[1..N] melalui pembacaan} {K. Awal: N terdefinisi, yaitu banyak elemen efektif larik} {K.Akhir: Larik A[1..N] terdefinisi Deklarasi: k: integer
{indeks larik}
Deskripsi: for k 1 to N do read(A[k]) endfor
Algoritma 2.5 Mengisi elemen larik melalui pembacaan Gambar 2.3 mengilustrasikan keadaan larik sebelum dan setelah pembacaan. Misalkan terdefinisi N = 10 [1] [2] [3] [4] [5] [6] [7] ....
[1] [2] [3] [4] [5] [6] [7] [8] [9] [N] ...
[NMAX]
67 75 56 89 45 66 77 69 59 72
[NMAX] (a)
(b)
Gambar 2.5 (a) K.Awal (b) Keadaan Akhir dari Algoritma 2.5
Struktur Data – 13
Contoh 2.6: menentukan harga maksimum larik Diketahui larik A[1..N] yang sudah terdefinisi nilainya. Algoritma akan menentukan harga maksimum elemen larik. procedure TentukanMaks(input A: Larik, input N: integer, output Maks: integer) {menentukan harga maksimum elemen larik A[1..N] } {K. Awal: Larik A[1..N] terdefinisi} {K.Akhir: Maks terdefinisi, yaitu harga maksimum larik} Deklarasi: k: integer
{indeks larik}
Deskripsi: Maks A[1] for k 2 to N do if A[k] > Maks then Maks A[k] endif endfor
Algoritma 2.6 Menentukan harga maksimum elemen larik 2.3 Larik Bertipe Terstruktur Pada contoh-contoh yang sudah dibahas digunakan larik bertipe sederhana, yaitu larik bertipe integer. Elemen larik juga dapat bertipe . Contoh 2.7: larik yang elemennya bertipe terstruktur const NMHS = 100 type DataMhs = record type LarikMhs = array[1..NMHS] of DataMhs AMhs: LarikMhs
Algoritma 2.7 Deklarasi larik bertipe terstruktur
Struktur Data – 14 Gambar 2.6 mengilustrasikan larik AMhs[1..N]. Misalkan terdefinisi N = 8
[1] [2] [3] [4] [5] [6] [7] [N]
6789 7890 5678 2345 1234 3456 8901 4567
Tiger Woods Ronaldo Roger Federer Serena Williams Taufik Hidayat Valentino Rossi Michael Jordan Schummacher
2.8 3.1 3.0 2.9 3.7 2.9 3.2 3.3
[NMAX]
Gambar 2.6 Contoh Larik Bertipe Terstruktur Contoh 2.7: mencari data mahasiswa dengan IPK tertinggi. Algoritma akan memberikan keluaran berupa data mahasiswa dengan IPK tertinggi. gunakan prinsip Algoritma 2.6. Jika mengacu ke Gambar 2.6, maka keluaran MhsTerbaik = <”1234”, “Taufik Hidayat”, 3.7> procedure CariMhsTerbaik(input AMhs: LarikMhs, input N: integer, output MhsTerbaik: DataMhs) {mencari data mahasiswa dengan IPK tertinggi } {K. Awal: Larik AMhs[1..N] terdefinisi} {K.Akhir: MhsTerbaik terdefinisi, yaitu data mahasiswa dengan IPK tertinggi} Deklarasi: k: integer Deskripsi:
{indeks larik}
Struktur Data – 15 MhsTerbaik A[1] for k 2 to N do if AMhs[k].IPK > MhsTerbaik.IPK then MhsTerbaik A[k] endif endfor
Algoritma 2.8 Mencari data mahasiswa dengan IPK tertinggi 2.4 Pencarian Pada Larik Proses sekuensial lain yang sering dilakukan adalah pencarian terhadap elemen data tersebut. Contoh 2.8: mencari keberadaan X di dalam larik integer A[1..N] versi 1. Jika diketahui larik A[1..N], algoritma akan mencari keberadaan X di dalam larik. Jika X ada di dalam larik maka algoritma akan memberikan keluaran true, jika tidak maka akan memberikan keluaran false. Mengacu ke Gambar 2.5(b), misalkan X yang dicari = 60, maka Found = false, misalkan X yang dicari = 77, maka Found = true procedure CariX(input A:: Larik, input N: integer, output Found: boolean) {mencari keberadaan X di dalam larik integer A[1..N] } {K. Awal: Larik A[1..N] terdefinisi, X terdefinisi} {K.Akhir: Jika X ditemukan maka Found = true, jika tidak maka Found = false} Deklarasi: k: integer
{indeks larik}
Deskripsi: Found false k 1 while not Found and k ≤ N do if A[k] = X then Found true else k k + 1 endif endwhile
Algoritma 2.9 Mencari keberadaan X di dalam larik integer A[1..N] versi 1
Struktur Data – 16
Contoh 2.9: mencari keberadaan X di dalam larik integer A[1..N] versi 2. Jika diketahui larik A[1..N], algoritma akan mencari keberadaan X di dalam larik. Jika X ada di dalam larik maka algoritma akan memberikan keluaran IdX berupa nilai integer yaitu indeks tempat X ditemukan.Jika tidak maka IdX = -1. Mengacu ke Gambar 2.5(b), misalkan X yang dicari = 60, maka IdX = -1, misalkan X yang dicari = 77, maka IdX = 7 procedure CariIdX(input A:: Larik, input N: integer, output IdX: integer) {mencari keberadaan X di dalam larik integer A[1..N] } {K. Awal: Larik A[1..N] terdefinisi, X terdefinisi} {K.Akhir: Jika X ditemukan maka IdX adalah tempat X ditemukan, jika tidak maka IdX = -1} Deklarasi: k: integer Found: boolean
{indeks larik}
Deskripsi: Found false k 1 while not Found and k ≤ N do if A[k] = X then Found true else k k + 1 endif if Found then IdX k else IdX -1 endif
Algoritma 2.10 Mencari keberadaan X di dalam larik integer A[1..N] versi 2
2.5 Pengurutan Data Mengurutkan data adalah pekerjaan yang sering dilakukan dalam pemrosesan data. Ada berbagai metode pengurutan data seperti metode gelembung, metode seleksi, metode sisip dan metode-metode lain yang memerlukan kajian struktur
Struktur Data – 17 data lanjutan. Pada buku ini akan dibahas metode pengurutan yang paling sederhana, yaitu metode gelembung. procedure Pengurutan(input/output A: Larik, input N: integer) {mengurutkan elemen larik A[1..N]dari kecil ke besar dengan metode gelembung } {K. Awal: Larik A[1..N] terdefinisi} {K.Akhir: Larik A[1..N] terurut dari kecil ke besar} Deklarasi: i,k: integer temp: integer Deskripsi: for i 1 to N-1 do for k N downto i+1 do if A[k] < A[k-1] then temp A[k] A[k] A[k-1] A[k-1] temp endif endfor endfor
Algoritma 2.11 Mengurutkan data dari kecil ke besar dengan metode gelembung Soal Latihan 1. Buat algoritma untuk mencari harga minimum larik A[1..N] 2. Buat algoritma untuk menentukan indeks tempat harga minimum larik A[1..N] berada. 3. Buat algoritma untuk mengurutkan elemen larik A[1..N] dari besar ke kecil 4. Buat algoritma untuk mengurutkan elemen larik mahasiswa dari kecil ke besar berdasarkan NIM
Struktur Data – 18
BAB 3 SENARAI Seringkali persoalan yang dihadapi terlalu sulit untuk direpresentasikan menggunakan struktur data yang tersedia, sehingga kita perlu membangun sendiri struktur data yang disebut user-defined data structured. Struktur data standard yang sering digunakan adalah senarai (list), tumpukan (stack), antrian (queue), graf (graph) dan pohon (tree). 3.1 Alasan Menggunakan Senarai Misalkan satu perusahaan besar akan mengadakan pertemuan antar kantor cabang perusahaan. Ada 500 orang yang akan menjadi peserta pertemuan yang akan tinggal di lima hotel yang berbeda. Setiap peserta diberi kebebasan untuk memilih hotel tempatnya menginap. Mungkin saja ke-500 peserta akan tinggal di satu hotel yang sama (ke-4 hotel lainnya kosong), atau 500 peserta tersebut akan tersebar di 5 hotel yang berbeda. Panitia pertemuan perlu membuat daftar peserta menurut hotel dan meminta kita untuk membuat program untuk keperluan tersebut. Kita dapat menggunakan larik untuk masing-masing hotel, jadi diperlukan lima larik yang masing-masing didefinisikan untuk menampung jumlah maksimum peserta. Penggunaan larik untuk setiap hotel akan menghabiskan tempat sia-sia, karena 5 hotel dikalikan 500 peserta = 2500 elemen larik. Akan data 2000 elemen larik yang tidak terpakai. Idealnya, informasi mengenai peserta harus disimpan sedemikian rupa sehingga hanya yang diperlukan saja yang dideklarasikan. Perhatikan Gambar 3.1. H1
H2
H3
H4
H5
[1] [2] [3]
[1]
[1]
[1]
[1]
[500]
[500]
[500]
[500]
[500]
Gambar 3.1. Lima larik untuk merepresentasi 5 hotel Jika persoalan tersebut direpresentasikan dengan senarai seperti terlihat pada Gambar 3.2.
Struktur Data – 19 H1 1
H2 2
3
H3 4
5
H4 6
7
8
9
10
H5 11
12
...
499
500
Gambar 3.2. Senarai dari Gambar 1 Dengan senarai cukup disediakan sebuah larik dengan 500 elemen yang digunakan untuk merepresentasikan lima daftar (list) peserta yang menginap di lima hotel. 3.2 Tipe Pointer Dari Gambar 3.2 terlihat bahwa setiap elemen larik, selain menyimpan data juga menyimpan “alamat” (dalam Gambar 3.2 berupa indeks) sebagai penunjuk (pointer) posisi elemen larik yang mengikutnya. Elemen yang menyimpan data dan “alamat” seperti ini disebut elemen senarai. Jadi senarai adalah sekumpulan elemen bertipe sama, setiap elemen terdiri dari dua bagian, yaitu bagian yang menyimpan informasi dan bagian yang menyimpan alamat elemen berikutnya. Gambar 3.3 menunjukkan senarai secara lojik
Info
Next
(a)Elemen Senarai First
(b) Senarai Kosong First
(c) Senarai Dengan 3 Elemen
Gambar 3.3. (a) Elemen Senarai, (b) Senarai Kosong, (c)Senarai Dengan 3 Elemen
Struktur Data – 20 Secara algoritmik, definisi senarai dapat dilihat pada Algoritma 3.1. Deklarasi global: type TInfo = integer {atau tipe terdefinisi lainnya} type Address = pointer to Elemen type Elemen = record type Senarai = record P: Address L: Senarai {First menyimpan alamat elemen pertama senarai} {P adalah variabel yang menyimpan alamat sebuah elemen} {Cara akses: Info(P): mengakses info elemen yang alamatnya P Next(P): mengakses alamat elemen setelah elemen dengan alamat P} procedure Alokasi(output P: Address) {memesan satu unit penyimpan untuk dijadikan elemen senarai} {K. Awal: - } {K.Akhir: P terdefinisi, siap digunakan sebagai elemen list} procedure DeAlokasi(input P: Address) {K. Awal: P terdefinisi} {K.Akhir: P dikembalikan ke sistem}
Algoritma 3.1. Deklarasi Senarai TInfo adalah tipe terdefinisi yang merepresentasikan informasi yang akan disimpan di dalam elemen . Tipe Address adalah tipe yang menyimpan alamat elemen, bisa berupa indeks larik ataupun alamat memori, tergantung nanti bagaimana senarai direpresentasikan. Senarai dikenali melalui alamat elemen pertamanya. Dengan demikian jika didefinisikan First adalah alamat elemen pertama, maka elemen berikut dapat diakses secara berurutan melalui Next. Mengapa harus senarai? Senarai adalah struktur data yang dinamis, ukurannya (banyak elemen) dapat berubah selama eksekusi program. Menghemat memori
Struktur Data – 21 Setiap elemen menyimpan “alamat” elemen berikutnya. Ada dua cara untuk merepresentasikan alamat. Jika senarai dibangun menggunakan larik, maka alamat adalah indeks larik. Jika senarai dibangun langsung dari memori, maka alamat adalah alamat memori. Tipe pointer adalah fasilitas bahasa yang digunakan untuk menangkap ekivalensi dari alamat memori. Notasi algoritmik untuk tipe pointer adalah sebagai berikut: Nama tipe: pointer to Rentang nilai: alamat sel memori Konstanta: Nil, untuk menyatakan alamat tidak terdefinisi Operator perbandingan: = dan ≠, menghasilkan nilai boolean
Operasi Dasar Terhadap Senarai 1. Create: membuat senarai kosong 2. Traversal: mengunjungi elemen senarai mulai dari elemen pertama sampai elemen terakhir atau elemen tertentu yang diinginkan dan melakukan pemrosesan 3. Insert: menyisipkan elemen 4. Delete: menghapus elemen 5. Bekerja dengan 2 senarai atau lebih 3.3 Membuat senarai kosong procedure Create(output L: Senarai) {membuat senarai kosong} {K. Awal: - } {K.Akhir: tercipta sebuah list kosong, L.First = Nil} Deklarasi: Deskripsi: L.First = Nil
Algoritma 3.2. Membuat Senarai Kosong
Struktur Data – 22 3.4 Traversal Ada dua skema, yaitu skema repeat-until yang memeriksa apakah senarai kosong dan skema while-do tidak memeriksa apakah senarai kosong atau tidak. Traversal dengan skema repeat - until procedure Traversal1(input L: Senarai) {traversal list dengan kasus senarai kosong} {K. Awal: L terdefinisi, mungkin kosong} {K.Akhir: Semua elemen senarai dikunjungi dan diproses} Deklarasi: P: Address Deskripsi: if L.First = Nil then write (“senarai kosong”) else Inisialisasi P L.First repeat Proses(P) P Next(P) until P = Nil endif
Algoritma 3.3. Traversal Dengan Kasus Kosong Traversal dengan skema while-do procedure Traversal2(input L: Senarai) {traversal list tanpa penanganan kasus senarai kosong} {K. Awal: L terdefinisi, mungkin kosong} {K.Akhir: Semua elemen senarai dikunjungi dan diproses} Deklarasi: P: Address Deskripsi: Inisialisasi P L.First while P ≠ Nil do Proses(P) P Next(P) endwhile P = Nil
Algoritma 3.4. Traversal Tanpa Kasus List Kosong
Struktur Data – 23 Contoh 3.1: Mencetak semua info elemen senarai Untuk mencetak semua info elemen senarai berarti harus dilakukan traversal terhadap senarai mulai dari elemen pertama sampai elemen terakhir. Proses yang dilakukan adalah pencetakan. procedure Cetak(input L: Senarai) {Mencetak semua info elemen senarai. Jika senarai kosong cetak pesan “senarai kosong”} {K. Awal: L terdefinisi, mungkin kosong} {K.Akhir: Semua elemen senarai dikunjungi dan info-nya dicetak} Deklarasi: P: Address Deskripsi: if L.First = Nil then write (“list kosong”) else P L.First repeat write (Info(P)) P Next(P) until P = Nil endif
Algoritma 3.5. Mencetak Info Semua Elemen Contoh 3.2: Menghitung banyak elemen Traversal senarai dan menghitung banyak elemen. Setiap kali sebuah elemen dikunjungi berarti banyak elemen bertambah 1. Perhatikan ilustrasi berikut: First
First
NEl = 0
NEl = 3
Gambar 3.4. Menghitung Banyak Elemen
Struktur Data – 24 procedure HitElemen(input L: Senarai, output NEl: integer) {Menghitung banyak elemen senarai} {K. Awal: L terdefinisi, mungkin kosong} {K.Akhir: NEl terdefinisi, yaitu banyak elemen senarai } Deklarasi: P: Address Deskripsi: NEl 0 P L.First while P ≠ Nil do NEl NEl + 1 P Next(P) endwhile
Algoritma 3.6. Menghitung Banyak Elemen Contoh 3.3 Buat algoritma untuk menghitung banyak elemen senarai yang info-nya ganjil Perhatikan ilustrasi berikut: First
NGj = -99 First
First
58
73
NGj = 2
47
74
60
NGj = 0
Gambar 3.5. Menghitung Banyak Elemen Ganjil
80
Struktur Data – 25 procedure HitGanjil(input L: Senarai, output NGj: integer) {Menghitung banyak elemen senarai yang info-nya ganjil} {K. Awal: L terdefinisi, mungkin kosong} {K.Akhir: NGj terdefinisi, yaitu banyak elemen senarai yang bernilai ganjil. Jika senarai kosong, maka NGj = -99 } Deklarasi: P: Address Deskripsi: if L.First = Nil then NGj -99 else NGj 0 repeat if Info(P) mod 2 = 1 then NGj NGj + 1 endif P Next(P) until P = Nil endif
Algoritma 3.7. Menghitung Banyak Elemen yang Info-nya Ganjil Contoh 3.4 : Pencarian Pencarian adalah menelusuri (traversal) elemen senarai mulai dari elemen pertama sampai elemen yang dicari ditemukan atau sampai elemen terakhir jika yang dicari tidak ditemukan. Proses yang dilakukan selama penelusuran adalah membandingkan apakah info elemen senarai yang dikunjungi sama dengan yang dicari. Jika sama berarti yang dicari ditemukan dan penelusuran dihentikan. Jika info elemen yang dikunjungi tidak sama dengan yang dicari maka penelusuran dilanjutkan ke elemen berikutnya. Ada dua macam algoritma pencarian, yaitu (1) hasil pencarian berupa nilai boolean, true jika yang dicari ditemukan dan false yang dicari tidak ditemukan. (2) Hasil pencarian berupa alamat elemen yang dicari tersebut ditemukan, nil jika yang dicari tidak ditemukan. Perhatikan ilustrasi pada Gambar 3.6.
Struktur Data – 26 (1) Keluaran berupa nilai boolean First Misalkan X yang dicari = 73 Found = false First
First
58
73
74
47
60
80
Found = false
Found = true
(2) Keluaran berupa alamat First Misalkan X yang dicari = 73 PX = Nil First
First PX
58
73
PX = Nil
47
74
60
80
Gambar 3.6. Pencarian procedure Search1(input L: Senarai, input X: TInfo, output Found: boolean) {Mencari apakah X ada di dalam elemen senarai} {K. Awal: L terdefinisi, mungkin kosong, X terdefinisi yaitu info yang dijadikan dasar pencarian} {K.Akhir: Jika X ditemukan maka Found = true, Jika X tidak ditemukan maka Found = false} Deklarasi: P: Address Deskripsi: Found false P L.First while not Found and P ≠ Nil do if Info(P) = X then Found true else P Next(P) endif endwhile
Algoritma 3.8. Pencarian Dengan Keluaran Boolean
Struktur Data – 27 procedure Search2(input L: Senarai, input X: TInfo, output PX: Address) {Mencari apakah X ada di dalam elemen senarai} {K. Awal: L terdefinisi, mungkin kosong, X terdefinisi yaitu info yang dijadikan dasar pencarian} {K.Akhir: Jika X ditemukan maka PX adalah alamat elemen tempat X ditemukan Jika X tidak ditemukan maka PX = Nil} Deklarasi: P: Address Deskripsi: Found false; P L.First while not Found and P ≠ Nil do if Info(P) = X then Found true else P Next(P) endif endwhile if Found then PX P else PX Nil endif
Algoritma 3.9. Pencarian Dengan Keluaran Alamat 3.5 Penyisipan Elemen 1. Penyisipan sebagai elemen pertama 2. Penyisipan sebagai elemen tengah 3. Penyisipan sebagai elemen terakhir Penyisipan Sebagai Elemen Pertama Sebelum Penyisipan
Setelah Penyisipan
First
First
58
73
60
58
60
P
Gambar 7. Penyisipan Sebagai Elemen Pertama
73
Struktur Data – 28 procedure InsertFirst(input/output L: Senarai, input P: Address) {Menyisipkan P sebagai elemen pertama senarai} {K. Awal: L terdefinisi, mungkin kosong, P terdefinisi yaitu alamat elemen yang akan disisipkan} {K.Akhir: P menjadi elemen pertama senarai} Deklarasi: Deskripsi: Next(P) L.First L.First P
Algoritma 3.10. Menyisipkan Sebagai Elemen Pertama Penyisipan Sebagai Elemen Tengah Sebelum Penyisipan
Setelah Penyisipan
First
First
Prev
Prev
60
73
60
58
73
P 58
P
Gambar 8. Penyisipan Sebagai Elemen Tengah procedure InsertAfter(input/output P, Prev: Address) {Menyisipkan P setelah elemen dengan alamat Prev} {K. Awal: Prev terdefinisi, P terdefinisi yaitu alamat elemen yang akan disisipkan} {K.Akhir: P menjadi elemen setelah elemen dengan alamat Prev} Deklarasi: Deskripsi: Next(P) Next(Prev) Next(Prev) P
Algoritma 3.11. Menyisipkan Sebagai Elemen Tengah
Struktur Data – 29 Penyisipan Sebagai Elemen Terakhir Sebelum Penyisipan
Setelah Penyisipan
First
First
Last
Last
60
73
60
50
73
P 58
P
Gambar 3.9. Penyisipan Sebagai Elemen Terakhir procedure InsertLast(input/output L: Senarai, input P: Address) {Menyisipkan P sebagai elemen terakhir} {K. Awal: L terdefinisi, mungkin kosong P terdefinisi yaitu alamat elemen yang akan disisipkan} {K.Akhir: P menjadi elemen terakhir senarai} Deklarasi: Last: Address Deskripsi: if L.First = Nil then L.First P else Last L.First while Next(Last) ≠ Nil do Last Next(Last) endwhile Next(Last) P endif
Algoritma 3.12. Menyisipkan Sebagai Elemen Terakhir
Struktur Data – 30 Contoh 3.5: Pencarian dan Penyisipan Buat algoritma untuk mencari keberadaan X di dalam senarai. Jika X tidak ditemukan, maka alokasikan sebuah elemen dengan alamat P, simpan X sebagai Info(P) dan sisipkan P sebagai elemen pertama senarai. Perhatikan Gambar 3.10. Kasus (1) jika X tidak ditemukan K.Akhir
K. Awal First
Mis. X = 60
58
First
73
60
58
58
73
73
P Kasus (2) jika X ditemukan K.Akhir
K. Awal First
Mis. X = 73
58
First
73
Gambar 3.10. Pencarian dan Penyisipan procedure CaridanSisip(input/output L: Senarai, input X: TInfo) {mencari keberadaan X, jika tidak ditemukan maka alokasikan sebuah elemen dengan alamat P, simpan X sebagai Info(P) dan sisipkan P sebagai elemen pertama senarai} {K. Awal: L terdefinisi, X terdefinisi} {K.Akhir: Jika X tidak ditemukan, maka X menjadi elemen pertama senarai} Deklarasi: P, Q: Address Found: boolean Deskripsi: Q L.First Found false while not Found and Q ≠ Nil do if Info(Q) = X then Found true else Q Next(Q) endif endwhile if not Found then
Struktur Data – 31 Alokasi(P) Info(P) X Next(P) Nil InsertFirst(L, P) endif
Algoritma 3.13. Pencarian dan Penyisipan Contoh 3.6: Penyisipan sebagai elemen ke-k Tulis algoritma untuk menyisipkan elemen sebagai elemen ke-k senarai L. Perhatikan Gambar 3.11. Kasus (1) Senarai kosong K. Awal L.First
K. Akhir L.First
58
58
P Kasus (2) Senarai tidak kosong, k = 1 K. Awal L.First
K. Akhir L.First
65
47
58
65
47
58
P Kasus (3) Senarai tidak kosong, k ≠ 1 K. Awal L.First
K. Akhir L.First
58
65
36
47
58
36
P
P, k =2
Gambar 3.11 Penyisipan Sebagai Elemen Ke-k
65
47
Struktur Data – 32 procedure SisipK(input/output L: Senarai, input P: Address, input k: integer) {menyisipkan P sebagai elemen ke-k pada senarai L} {K. Awal: L terdefinisi, P terdefinisi, k terdefinisi >= 1} {K.Akhir: P menjadi elemen ke-k senarai L} Deklarasi: Q, PrevQ: Address m: integer Deskripsi: if (L.First = Nil or k = 1 then InsertFirst(L,P) else Q L.First; PrevQ Nil m = 1 while Q ≠ Nil and m
Algoritma 3.14. Penyisipan Sebagai Elemen ke-k 3.6 Menghapus Elemen 1. Menghapus Elemen Pertama 2. Menghapus Elemen Tengah 3. Menghapus Elemen Terakhir Menghapus Elemen Pertama Setelah Penghapusan First
First
60
58
73
60
P
Gambar 3.12. Menghapus Elemen Pertama
58
73
Struktur Data – 33 procedure DeleteFirst(input/output L: Senarai, output P:Address) {menghapus elemen pertama senarai} {K. Awal: L terdefinisi, tidak kosong} {K.Akhir: P adalah alamat elemen yang dihapus} Deklarasi: Deskripsi: P L.First L.First Next(L.First)
Algoritma 3.14. Menghapus Elemen Pertama Menghapus Elemen Tengah Sebelum Penghapusan
Setelah Penghapusan
First
First
Prev
60
Prev
58
73
60
58
P
Gambar 3.13. Menghapus Elemen Tengah procedure DeleteAfter(input/output P, Prev: Address) {menghapus elemen setelah elemen dengan alamat Prev} {K. Awal: Prev terdefinisi} {K.Akhir: P adalah alamat elemen yang dihapus} Deklarasi: Deskripsi: P Next(Prev) Next(Prev) Next(Next(Prev))
Algoritma 3.14. Menghapus Elemen Tengah
73
Struktur Data – 34 Menghapus Elemen Terakhir Sebelum Penghapusan
Setelah Penghapusan
First
First
PrevLast
60
58
PrevLast
Last
73
60
58
Last
73
P
Gambar 3.14. Menghapus Elemen Terakhir procedure DeleteLast(input/output L: Senarai, output P:Address) {menghapus elemen terakhir senarai} {K. Awal: L terdefinisi, tidak kosong} {K.Akhir: P adalah alamat elemen yang dihapus} Deklarasi: Last, PrevLast: Address Deskripsi: PrevLast Nil Last L.First while Next(Last) ≠ Nil do PrevLast Last Last Next(Last) endwhile P Last Next(PrevLast) Nil
Algoritma 3.15. Menghapus Elemen Terakhir
Struktur Data – 35 Contoh 3.7: Hapus X Buat algoritma untuk elemen yang info-nya = X. Perhatikan Gambar 3.14. Kasus (1) jika X tidak ditemukan K.Akhir
K. Awal
First
First Mis. X = 70
60
58
73
60
58
73
60
58
73
Kasus (2) jika X ditemukan First
First Mis. X = 58
60
58
73
P
Gambar 3.15. Pencarian dan Penghapusan procedure HapusX(input/output L: Senarai, input X: TInfo, output P: Address) {mencari keberadaan X, jika ditemukan maka hapus elemen X} {K. Awal: L terdefinisi, X terdefinisi} {K.Akhir: Jika X ditemukan P adalah alamat elemen yang dihapus. Jika X ditemukan, maka P = Nil} Deklarasi: PrevQ, Q: Address Found: boolean Deskripsi: Q L.First; PrevQ Nil Found false while not Found Q ≠ Nil do if Info(Q) = X then Found true else PrevQ Q Q Next(Q) endif endwhile if Found then {X ditemukan} if PrevQ = Nil then DeleteFirst(L,P) else DeleteAfter(P, PrevQ) endif else {X tidak ditemukan} P Nil endif
Algoritma 3.17. Mencari dan Menghapus
Struktur Data – 36 3.7 Bekerja Dengan Dua atau Lebih Senarai 1. Penyambungan Senarai (Konkat) 2. Penggabungan Senarai (Merger) 3. Salin Senarai (Copy) 4. Balik Senarai (Reverse) 5. Mengambil Info Tertentu (Query)
Penyambungan Senarai (Konkat) Menyambung senarai L1 dengan senarai L2. Senarai L1 berada “di depan” K. Awal L2.First
L1.First
60
58
73
60
58
73
42
29
K.Akhir L1.First
42
29
Gambar 3.16. Penyambungan Senarai procedure Konkat(input/output L1: Senarai, input L2: Senarai) {menyambung senarai L1 dengan senarai L2, dengan senarai L1 berada di depan} {K. Awal: L1, L2 terdefinisi} {K.Akhir: L2 tersambung dengan L1} Deklarasi: P: Address Deskripsi: P L1.First while Next(P) ≠ Nil do P Next(P) endwhile Next(P) L2.First
Algoritma 3.18. Menghapus Elemen Tengah
Struktur Data – 37 Penggabungan Senarai (Merger) Menggabung senarai L1 dan L2 yang info-nya terurut dari kecil ke besar, L3 adalah hasil penggabungan dan info-nya tetap terurut. K. Awal L2.First
L1.First
45
60
80
45
50
60
50
75
K.Akhir L3.First
75
80
Gambar 3.16. Penggabungan Senarai procedure Merger(input L1,L2: Senarai, output L3: Senarai) {Menggabung senarai L1 dengan L2 yang info-nya terurut dari kecil ke besar. Senarai L3 merupakan penggabungan, tetap terurut} {K. Awal: L1, L2 terdefinisi, info-nya terurut dari kecil ke besar} {K.Akhir: L3 terdefinisi merupakan hasil penggabungan L1 dengan L2 dan tetap terurut}
Deklarasi: P1,P2,Q: Address Deskripsi: P1 L1.First P2 L2.First Create(L3) while P1 ≠ Nil and P2 ≠ Nil do Alokasi(Q) Next(Q) Nil if Info(P1) < Info(P2) then Info(Q) Info(P1) P1 Next(P1) else Info(Q) Info(P2) P2 Next(P2) endif InsertLast(L3,Q) endwhile while P1 ≠ Nil do
Struktur Data – 38 Alokasi(Q) Next(Q) Nil Info(Q) Info(P1) InsertLast(L3,Q) P1 Next(P1) endwhile while P2 ≠ Nil do Alokasi(Q) Next(Q) Nil Info(Q) Info(P1) InsertLast(L3,Q) P2 Next(P2) endwhile
Algoritma 3.19. Penggabungan Senarai Salin Senarai (Copy) Membuat salinan senarai L1 ke L2 K.Akhir
K. Awal
L2.First
L1.First
45
60
80
45
60
Gambar 3.17. Menyalin Senarai procedure {menyalin {K. Awal: {K.Akhir:
Copy(input L1: Senarai, output L2: Senarai) senarai L1 ke senarai L2} L1terdefinisi} L2 terdefinisi, merupakan salinan dari L1}
Deklarasi: P,Q: Address Deskripsi: Create(L2) P L1.First while P ≠ Nil do Alokasi(Q) Next(Q) Nil Info(Q) Info(P) InsertLast(L2,Q) P Next(P) endwhile
Algoritma 3.20. Penggabungan Senarai
80
Struktur Data – 39 Balik Senarai (Reverse) Membalik senarai L1, hasilnya adalah senarai L2 K.Akhir
K. Awal
L2.First
L1.First
45
60
80
80
60
45
Gambar 3.18. Balik Senarai procedure {menyalin {K. Awal: {K.Akhir:
Reverse(input L1: Senarai, output L2: Senarai) senarai L1 ke senarai L2 secara terbalik} L1terdefinisi} L2 terdefinisi, merupakan balikan dari L1}
Deklarasi: P,Q: Address Deskripsi: Create(L2) P L1.First while P ≠ Nil do Alokasi(Q) Next(Q) Nil Info(Q) Info(P) InsertFirst(L2,Q) P Next(P) endwhile
Algoritma 3.21. Membalik Senarai
Struktur Data – 40 Mengambil Info Tertentu (Query) Contoh 3.8: diketahui senarai L1, akan diambil elemen senarai yang info-nya < X, hasilnya disimpan di senarai L2 K. Awal L1.First Mis. X = 55
70
53
80
53
40
54
65
40
54
K.Akhir L2.First
Gambar 3.19. Mengambil Info Tertentu procedure QueryX(input L1: Senarai, input X: TInfo, output L2: Senarai) {menyalin senarai L1 yang info-nya < X ke senarai L2 } {K. Awal: L1terdefinisi} {K.Akhir: L2 terdefinisi, merupakan hasil query, semua infonya < X} Deklarasi: P,Q: Address Deskripsi: Create(L2) P L1.First while P ≠ Nil do if Info(P) < X then Alokasi(Q) Next(Q) Nil Info(Q) Info(P) InsertLast(L2,Q) endif P Next(P) endwhile
Algoritma 3.22. Mengambil informasi tertentu
Struktur Data – 41 3.8 Senarai yang Info-nya Terstruktur Tipe informasi yang disimpan di dalam elemen senarai dapat merupakan tipe terstruktur, seperti terlihat pada Algoritma 3.23. Deklarasi global: type DataMhs = record type Address = pointer to Elemen type Elemen = record type Senarai = record L: Senarai P: Address {First menyimpan alamat elemen pertama senarai} {P adalah variabel yang menyimpan alamat sebuah elemen} {Cara akses: Info(P).Nama: mengakses Nama dari elemen yang alamatnya P Info(P).NIM: mengakses NIM dari elemen yang alamatnya P Info(P).IPK: mengakses IPK dari elemen yang alamatnya P Next(P): mengakses alamat elemen setelah elemen dengan alamat P} procedure Alokasi(output P: Address) {memesan satu unit penyimpan untuk dijadikan elemen senarai} {K. Awal: - } {K.Akhir: P terdefinisi, siap digunakan sebagai elemen list} procedure DeAlokasi(input P: Address) {K. Awal: P terdefinisi} {K.Akhir: P dikembalikan ke sistem}
Algoritma 3.23. Deklarasi Senarai Terstruktur
Struktur Data – 42 Contoh 3.9: Diketahui senarai yang info elemennya bertipe data mahasiswa. Buat algoritma untuk mencetak semua data mahasiswa yang IPK-nya ≥3.0. Jika senarai kosong, cetak pesan “senarai kosong”. Jika tidak ada mahasiswa yang IPK-nya ≥3.0 maka cetak pesan “tidak ada mahasiswa yang IPK-nya≥3.0” procedure {mencetak {K. Awal: {K.Akhir:
Cetak3(input L: Senarai) semua data mahasiswa yang IPK-nya ≥ 3.0} L terdefinisi, mungkin kosong} Semua data mahasiswa yang IPK-nya ≥ 3.0 dicetak Jika senarai kosong cetak “senarai kosong” Jika tidak ada data mahasiswa yang IPK-nya ≥ 3.0, cetak “tidak ada mahasiswa yang IPK-nya ≥ 3.0” }
Deklarasi: P: Address Cetak: boolean Deskripsi: if L.First = Nil then write (“Senarai Kosong”) else P L.First Cetak false repeat if (Info(P).IPK ≥ 3.0) then write (Info(P)) Cetak true endif P Next(P) until P = Nil if not Cetak then write (“tidak ada mahasiswa yang IPK-nya≥ 3.0”) endif endif
Algoritma 3.24. Mencetak Data Mahasiswa Yang IPK-nya ≥ 3.0
Struktur Data – 43 3.9 Multi Linked List Senarai yang elemennya senarai Contoh 3.10: Senarai data pegawai dan anak-anaknya Deklarasi: type DataAnak = record type AddressA = pointer to CellA type CellA = record < InfoA: DataAnak, NextA: AddressA> type DataPeg = record type AddressP = pointer to CellP type CellP = record < InfoP: DataPeg, NextP: AddressP, NextA: AddressA> type ListPeg = record L: ListPeg
Algoritma 3.25 Deklarasi Senarai Pegawai Dengan Anak-Anaknya Gambar 3.20 memberikan ilustrasi mengenai senarai data pegawai dan anakanaknya. Untuk mengetahui data orang tua (pegawai) dari seorang anak, apakah identitas orang tua (NIP) perlu disimpan juga di dalam DataAnak? Diskusikan.
Struktur Data – 44 Elemen CellA
InfoP
NextP
Elemen CellP
InfoA NextA
NextA
Anak1Pegawai1
Pegawai3
NextP
Pegawai2
NextP
Pegawai1
NextP
FirstP
PegawaiN
NextA
NextA
Anak1Pegawai1
Anak1Pegawai1
NextA
NextA
Anak1Pegawai1
Anak1Pegawai1 NextA
Anak1Pegawai1
Gambar 3.20 Senarai Data Pegawai dan Anak-anaknya Soal Latihan Bab 3 1.
Buat algoritma untuk mencetak semua info elemen senarai yang bernilai genap. Jika senarai kosong, maka cetak pesan “tidak ada elemen”. Jika senarai tidak kosong maka semua info yang bernilai genap dicetak. Jika tidak ada info yang bernilai genap, maka cetak pesan “tidak ada info bernilai genap”.
2.
Buat algoritma untuk memperoleh info maksimum elemen senarai
3.
Sama seperti Soal No. 2, tetapi keluarannya adalah alamat tempat info maksimum berada.
4.
Buat algoritma untuk menukar info maksimum dengan info elemen pertama senarai.
5.
Buat algoritma untuk menghitung total info elemen senarai
6.
Buat algoritma untuk menghitung harga rata-rata info elemen senarai. Untuk menghitung harga rata-rata pastikan bahwa senarai tidak kosong, supaya tidak ada pembagian dengan 0. Gunakan skema repeat-until.
Struktur Data – 45 7.
Diketahui senarai yang info elemennya terurut dari kecil ke besar. Buat algoritma untuk menyisipkan sebuah elemen dengan tetap menjaga keterurutan.
8.
Buat algoritma untuk menghapus semua elemen senarai yang info-nya = X.
9.
Buat algoritma untuk menghapus elemen senarai yang menyimpan info terkecil (minimum)
10. Buat algoritma untuk menyambung senarai S1 dengan senarai S2, dengan senarai S2 berada” di depan” senarai S1. 11. Diketahui senarai S1 dan S2 yang info-nya terurut dari besar ke kecil. Buat algoritma untuk menggabung senarai S1 dengan S2, dan hasil penggabungan tetap terurut dari besar ke kecil. 12. Diketahui senarai S1 dan S2 yang info-nya terurut dari kecil ke besar. Buat algoritma untuk menggabung senarai S1 dengan S2, dan hasil penggabungan terurut dari besar ke kecil. 13. Buat algoritma untuk mengambil info yang bernilai ganjil dari senarai S1 dan menyimpannya di senarai S2 Untuk soal No. 14 s.d Soal No. 20, gunakan deklarasi Algoritma 3.23 14. Tulis algoritma untuk memperoleh data mahasiswa dengan IPK tertinggi. Keluaran bertipe DataMhs. 15. Buat algoritma untuk mencari keberadaan data mahasiswa yang NIM-nya = NIMX. Algoritma akan memberikan keluaran bertipe boolean, true jika data ditemukan dan false jika data tidak ditemukan. 16. Tulis algoritma untuk menghitung IPK rata-rata seluruh mahasiswa. 17. Diketahui senarai yang info elemennya bertipe mahasiswa, terurut dari kecil ke besar berdasarkan NIM. Buat algoritma untuk menyisipkan elemen yang alamatnya P, setelah penyisipan senarai tetap terurut. 18. Buat algoritma untuk menghapus elemen senarai mahasiswa yang NIM-nya = NIMX 19. Buat algoritma untuk menghapus semua elemen senarai mahasiswa yang IPK-nya < 2.0
Struktur Data – 46 20. Buat algoritma untuk mengambil semua data mahasiswa dengan IPK ≤ 2.0 dan menyimpannya di senarai L2. Untuk Soal No. 21 s.d. 23, gunakan deklarasi Algoritma 3.25 21. Tulis algoritma untuk mencetak data pegawai yang tidak punya anak 22. Tulis algoritma untuk mencetak data pegawai beserta anak-anaknya 23. Tulis algoritma untuk mencari data orang tuanya, jika diketahui data identitas anak
Struktur Data – 47
BAB 4 ANTRIAN 4.1 Pengertian Dasar Secara lojik antrian (queue) adalah senarai yang penyisipan elemen hanya dilakukan sebagai elemen terakhir dan penghapusan elemen hanya dilakukan terhadap elemen pertama. Struktur data antrian digunakan memodelkan antrian, misalnya antrian proses pada sistem multiprogramming, antrian nasabah di bank, antrian paket data yang akan dilewatkan di jaringan, antrian dokumen yang akan dicetak di printer bersama, dan sebagainya. Seperti layaknya antrian di dunia nyata, maka elemen baru disisipkan sebagai elemen terakhir dan elemen yang dihapus adalah elemen paling depan. Berlaku prinsip FIFO (first in first out). Secara algoritmik, deklarasi antrian seperti terlihat pada Algoritma 4.1. Deklarasi: type TInfo = integer {atau tipe terdefinisi lainnya} type Address = pointer to Elemen type Elemen = record type Antrian = record Q: Antrian
Algoritma 4.1 Deklarasi Antrian Antrian dikenali melalui alamat elemen pertama (Head) dan alamat elemen terakhir (Tail). Antrian kosong adalah antrian yang tidak memiliki elemen, Head = Nil dan Tail = Nil. Head
Tail
(a) Antrian Kosong Head
Tail
(b) Antrian Dengan 3 Elemen
Head
Tail
(c) Antrian Dengan 1 Elemen
Gambar 4.1. (a) Antrian Kosong, (b) Antrian Dengan 3 Elemen, (c) Antrian Dengan 1 Elemen Operasi Dasar Terhadap Antrian
Struktur Data – 48 1. 2. 3. 4.
Membuat Antrian Kosong (CreateQ) Menyisipkan Elemen (EnQueue) Menghapus Elemen (DeQueue) Memeriksa Apakah Antrian Kosong
4.2 Membuat Antrian Kosong Antrian kosong adalah Head = Nil, Tail = Nil procedure CreateQ(output Q: Antrian) {membuat antrian kosong} {K. Awal: - } {K.Akhir: Antrian Q terdefinisi} Deklarasi: Deskripsi: Q.Head Nil Q.Tail Nil
Algoritma 4.2. Membuat Antrian Kosong 4.3 Memeriksa Apakah Antrian Kosong Fungsi EmptyQ mengembalikan true jika antrian Q kosong function EmptyQ(input Q: Antrian) {mengembalikan true jika antrian Q kosong} Deklarasi: Deskripsi: return (Q.Head = Nil and Q.Tail = Nil)
Algoritma 4.3. Memeriksa Apakah Antrian Kosong
Struktur Data – 49 4.4 Menyisipkan Elemen Antrian (EnQueue)
Sebelum Penyisipan
Setelah Penyisipan
Head
Tail
58
73
Tail
Head
58
73
X
X
Gambar 4.2. Penyisipan Elemen Antrian (EnQueue) procedure EnQueue(input/output Q:Antrian, input X: TInfo) {menyisipkan X sebagai elemen antrian} {K. Awal: Q terdefinisi, mungkin kosong, X terdefinisi} {K.Akhir: X menjadi elemen antrian} Deklarasi: P: Address Deskripsi: Alokasi(P) Next(P) Nil Info(P) X if EmptyQ(Q) then Q.Head P Q.Tail P else Next(Q.Tail) P Q.Tail P endif
Algoritma 4.4. Menyisipkan Elemen Antrian (EnQueue)
Struktur Data – 50 4.5 Menghapus Elemen Antrian (DeQueue)
Setelah Penghapusan Tail
Head
58
73
60
Head
Tail
73
60
X = 58
Gambar 4.3. Menghapus Elemen Antrian (DeQueue) procedure DeQueue(input/output Q:Antrian, output X: TInfo) {menghapus elemen antrian} {K. Awal: Q terdefinisi, tidak kosong} {K.Akhir: X adalah elemen yang dihapus, antrian mungkin jadi kosong} Deklarasi: Deskripsi: X Info(Q.Head) if Q.Head = Q.Tail then Q.Head Nil Q.Tail Nil else Q.Head Next(Q.Head) endif
{antrian dengan satu elemen}
Algoritma 4.5. Menghapus Elemen Antrian (DeQueue)
Struktur Data – 51 4.6 Representasi Fisik Antrian Dengan Larik Antrian dapat direpresentasi secara fisik dengan dua cara, yaitu menggunakan pointer dan menggunakan larik Algoritma 4.6 menunjukkan antrian yang direpresentasi menggunakan larik Deklarasi: const NMAX = type TInfo = type Address type Antrian
100 {maksimum elemen larik} integer {atau tipe terdefinisi lainnya} = integer[0..NMAX] = record
Q: Antrian
Algoritma 4.6. Deklarasi Antrian Representasi Larik Q.Head = 1
75 [1]
56 [2]
Q.Tail = 4
68 [3]
48 82 ... [4] [5] (a) Antrian Dengan 4 Elemen
[99]
[100]
[99]
[100]
[99]
[100]
Q.Head = 4, Q.Tail = 4
75 [1]
56 [2]
68 [3]
48 82 ... [4] [5] (b) Antrian Dengan 1 Elemen
Q.Head = 0, Q.Tail = 0 75 [1]
56 [2]
68 [3]
48 [4]
82 ... [5] (c) Antrian Kosong
Gambar 4.4. Antrian Representasi Larik
Struktur Data – 52 4.7 Membuat Antrian Kosong, Representasi Fisik Larik procedure CreateQ(output Q: Antrian) {membuat antrian kosong, representasi fisik larik} {K. Awal: - } {K.Akhir: Q terdefinisi, Q.Head = 0, Q.Tail = 0} Deklarasi: Deskripsi: Q.Head 0 Q.Tail 0
Algoritma 4.7. Membuat Antrian Kosong, Representasi Fisik Larik 4.8 Fungsi Untuk Memeriksa Antrian Kosong, Representasi Fisik Larik function EmptyQ(input Q: Antrian) boolean {mengembalikan true jika antrian kosong, Q.Head = 0 and Q.Tail = 0} Deklarasi: Deskripsi: return (Q.Head = 0 and Q.Tail =0)
Algoritma 4.8. Memeriksa Antrian Kosong 4.9 Menyisipkan Elemen Antrian, Representasi Fisik Larik Kasus (1) K. Awal Q.Head = 0
Q.Tail = 0
X = 77 ...
[1]
[2]
K.Akhir Q.Head = 1
77 [1]
[3]
[4]
[5]
[99]
[100]
[99]
[100]
Q.Tail = 1
... [2]
[3]
[4]
[5]
Struktur Data – 53 Kasus (2) K. Awal Q.Head = 1
75 [1]
56 [2]
Q.Tail = 3
68 [3]
K.Akhir Q.Head = 1
75 [1]
56 [2]
Kasus (3) K. Awal Q.Head = 1
75 [1]
56 [2]
K.Akhir Q.Head = 1
75 [1]
56 [2]
X = 77
... [4]
[5]
[99]
[100]
[99]
[100]
...
82 [99]
37 [100]
...
82 [99]
37 [100]
Q.Tail = 4
68 [3]
77 [4]
Q.Tail = 100
68 [3]
72 [4]
Q.Tail = 100
68 [3]
72 [4]
... [5]
X = 77
54 [5]
Overflow
54 [5]
Gambar 4.5. Menyisipkan Elemen Antrian, Representasi Fisik Larik
Struktur Data – 54 procedure EnQueue(input/output Q: Antrian, input X: TInfo) {menyisipkan X sebagai elemen antrian yang direpresentasi secara fisik menggunakan larik} {K. Awal: Q terdefinisi, X terdefinisi} {K.Akhir: X menjadi elemen antrian} Deklarasi: Deskripsi: if EmptyQ(Q) then Q.Head 1 Q.Tail 1 Q.ArrQ[Q.Tail] X else if Q.Tail < NMAX then Q.Tail Q.Tail + 1 Q.ArrQ[Q.Tail] X else write (“overflow”) endif endif
Algoritma 4.9 Menyisipkan Elemen Antrian, Representasi Fisik Larik 4.10 Menghapus Elemen Antrian, Representasi Fisik Larik Ada dua alternatif, yaitu: 1. Elemen bergeser maju, seperti layaknya antrian 2. Head bergeser maju 4.10.1 Menghapus Elemen Antrian: Elemen bergeser maju Kasus (1) K. Awal Q.Head = 1 Q.Tail = 4
75 [1]
56 [2]
K.Akhir Q.Head = 1
56 [1]
68 [2]
68 [3]
48 [4]
Q.Tail = 3
48 [3]
82 [5]
... [99]
[100]
[99]
[100]
X = 75
... [4]
[5]
Struktur Data – 55 Kasus (2) K. Awal Q.Head = 1 Q.Tail = 1
57 [1]
... [2]
K.Akhir Q.Head = 0
[3]
[4]
Q.Tail = 0
[5]
[99]
[100]
[99]
[100]
X = 57
... [1]
[2]
[3]
[4]
[5]
Gambar 5. DeQueue, Elemen Bergeser Maju procedure DeQueue(input/output Q: Antrian, output X: TInfo) {menghapus elemen antrian yang direpresentasi dengan larik, elemen bergeser maju} {K. Awal: Q terdefinisi, tidak kosong} {K.Akhir: X adalah elemen yang dihapus, elemen bergeser maju, antrian mungkin jadi kosong} Deklarasi: k: integer Deskripsi: X Q.ArrQ[Q.Head] if (Q.Tail ≠ Q.Head) then {geser maju elemen} for k 2 to Q.Tail do Q.ArrQ[k-1] Q.ArrQ[k] endfor Q.Tail Q.Tail – 1 else {hanya memiliki satu elemen, antrian jadi kosong} Q.Tail 0 Q.Head 0 endif
Algoritma 4.10. Menghapus Elemen Antrian, Elemen Bergeser Maju
Struktur Data – 56 4.10.2 Menghapus Elemen Antrian: Head Bergeser Maju Kasus (1) K. Awal Q.Head = 1 Q.Tail = 4
75 [1]
56 [2]
68 [3]
K.Akhir Q.Head = 2
[1]
56 [2]
48 [4]
... [5]
[99]
[100]
[99]
[100]
[99]
[100]
[99]
[100]
Q.Tail = 4 X = 75
68 [3]
48 [4]
[5]
...
[4]
[5]
Kasus (2) K. Awal Q.Head = 3 Q.Tail = 3
[1]
[2]
K.Akhir Q.Head = 0
34 [3]
...
Q.Tail = 0,
X = 34
... [1]
[2]
[3]
[4]
[5]
Gambar 4.6. DeQueue, Head Bergeser Maju
Struktur Data – 57 procedure DeQueue(input/output Q: Antrian, output X: TInfo) {menghapus elemen antrian yang direpresentasi dengan larik, head bergeser maju} {K. Awal: Q terdefinisi, tidak kosong} {K.Akhir: X adalah elemen yang dihapus, Head bergeser maju, antrian mungkin jadi kosong} Deklarasi: k: integer Deskripsi: X Q.ArrQ[Q.Head] if (Q.Tail ≠ Q.Head) then Q.Head Q.Head + 1 else Q.Tail 0 Q.Head 0 endif
Algoritma 4.11. Menghapus Elemen Antrian, Head Bergeser Maju 4.11 Persoalan Head Maju, Menyisipkan Elemen Persoalan: pada saat penyisipan, mungkin terjadi Q.Tail > NMAX, tetapi masih ada elemen belum terpakai, Solusi: reorganisasi elemen pada saat penyisipan Q.Head =98 Q.Tail = 100
... [1]
[2]
[3]
[4]
[5]
[4]
[5]
43 [98]
78 [99]
56 [100]
[98]
[99]
[100]
Setelah reorganisasi Q.Head = 1 Q.Tail = 3
43 [1]
78 [2]
56 [3]
...
Gambar 4.7. Persoalan DeQueue Dengan Head Maju
Struktur Data – 58 procedure EnQueue(input/output Q: Antrian, input X: TInfo) {menyisipkan X sebagai elemen antrian yang direpresentasi fisik larik} {K. Awal: Q terdefinisi, X terdefinisi} {K.Akhir: X menjadi elemen antrian} Deklarasi: k: integer Deskripsi: if EmptyQ(Q) then Q.Head 1 Q.Tail 1 Q.ArrQ[Q.Tail] X else if (Q.Tail < NMAX) Q.Tail Q.Tail + 1 Q.ArrQ[Q.Tail] X else if (Q.Head ≠ 1) then {reorganisasi elemen} for k Q.Head to Q.Tail do Q.ArrQ[k - Q.Head + 1] Q.ArrQ[k] endfor Q.Tail Q.Tail – Q.Head + 2 Q.Head 1 Q.ArrQ[Q.Tail] X else write (“overflow”) endif endif endif
Algoritma 4.12. Menyisipkan Elemen Antrian, Reorganisasi Elemen
Struktur Data – 59 Soal Latihan 1. Untuk menyelesaikan soal, gunakan deklarasi antrian berikut: Deklarasi: const NMAX = type TInfo = type Address type Antrian
5 {maksimum elemen larik} integer {atau tipe terdefinisi lainnya} = integer[0..NMAX] = record
Q: Antrian
Catatan: Sebagian nilai di dalam larik mungkin bukan merupakan elemen antrian. Arsir yang bukan elemen antrian Penghapusan elemen dilakukan dengan “head maju” (a) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 2, Q.Tail = 4, X = 82 EnQueue(Q,X)
Keadaan akhir
(b) Keadaan awal 45 78 56 64 [1] [2] [3] [4] Q.Head = 1, Q.Tail = 4 DeQueue(Q,X)
Keadaan akhir 37 [5]
[1] [2] Q.Head = Overflow?
[1] [2] Q.Head = EmptyQ(Q)?
(c) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 1, Q.Tail = 4, X = 28 EnQueue(Q,X)
Keadaan akhir
(d) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 4, Q.Tail = 5, X = 12 EnQueue(Q,X)
Keadaan akhir
[1] [2] Q.Head = Overflow?
[1] [2] Q.Head = EmptyQ(Q)?
[3] [4] Q.Tail =
[5]
[3] [4] Q.Tail =
[5] X=
[3] [4] Q.Tail =
[5]
[3] [4] Q.Tail =
[5] X=
Struktur Data – 60 (e) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 1, Q.Tail = 5, X = 37 EnQueue(Q,X)
Keadaan akhir
(f) Keadaan awal 45 78 56 64 [1] [2] [3] [4] Q.Head = 2, Q.Tail = 2 DeQueue(Q,X)
Keadaan akhir 37 [5]
[1] [2] Q.Head = Overflow?
[1] [2] Q.Head = EmptyQ(Q)?
[3] [4] Q.Tail =
[5]
[3] [4] Q.Tail =
[5] X=
2. Gunakan deklarasi Soal No. 1 untuk menyelesaikan, penghapusan dengan elemen bergeser maju (g) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 1, Q.Tail = 4, X = 82 EnQueue(Q,X)
Keadaan akhir
(h) Keadaan awal 45 78 56 64 [1] [2] [3] [4] Q.Head = 1, Q.Tail = 1 DeQueue(Q,X)
Keadaan akhir 37 [5]
[1] [2] Q.Head = Overflow?
[1] [2] Q.Head = EmptyQ(Q)?
(i) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 1, Q.Tail = 4, X = 28 EnQueue(Q,X)
Keadaan akhir
(j) Keadaan awal 45 78 56 64 [1] [2] [3] [4] Q.Head = 1, Q.Tail = 5, DeQueue(Q,X)
Keadaan akhir 37 [5]
[1] [2] Q.Head = Overflow?
[1] [2] Q.Head = EmptyQ(Q)?
[3] [4] Q.Tail =
[5]
[3] [4] Q.Tail =
[5] X=
[3] [4] Q.Tail =
[5]
[3] [4] Q.Tail =
[5] X=
Struktur Data – 61 (k) Keadaan awal 45 78 56 64 37 [1] [2] [3] [4] [5] Q.Head = 1, Q.Tail = 5, X = 37 EnQueue(Q,X)
Keadaan akhir
(l) Keadaan awal 45 78 56 64 [1] [2] [3] [4] Q.Head = 1, Q.Tail = 2 DeQueue(Q,X)
Keadaan akhir 37 [5]
[1] [2] Q.Head = Overflow?
[1] [2] Q.Head = EmptyQ(Q)?
[3] [4] Q.Tail =
[5]
[3] [4] Q.Tail =
[5] X=
3. Buat algoritma untuk menyalin antrian Q1 ke antrian Q2 4. Buat algoritma untuk memecah (split) antrian Q menjadi antrian Q1 yang menyimpan info ganjil dan antrian Q2 yang menyimpan info genap.
Antrian Prioritas Pada antrian dengan prioritas setiap elemen menyimpan informasi prioritas yang menentukan urutan keberadaan elemen dalam antrian. Aturan penyisipan menjadi tidak murni sesuai dengan aturan penyisipan antrian, melainkan sesuai prioritas. Penghapusan elemen tetap dilakukan terhadap elemen yang ditunjuk oleh Head. Deklarasi antrian prioritas seperti terlihat pada Algoritma 11. Deklarasi: type TInfo = {tipe terdefinisi, sesuai dengan kebutuhan} type Address = pointer to Elemen type Elemen = record type AntrianP = record QPrio: AntrianP procedure EnQueueP(input/output QPrio: AntrianP, input PIns: Address) {Menyisipkan PIns sebagai elemen antrian QPrio sesuai dengan Prio(PIns)} {K. Awal: QPrio terdefinisi, PIns terdefinisi} {K.Akhir: PIns menjadi elemen antrian QPrio}
Algoritma 4.13 Deklarasi Antrian Prioritas
Struktur Data – 62 Proses penyisipan elemen antrian prioritas seperti terlihat pada Algoritma 4.14 procedure EnQueuePrio(input/output QPrio: AntrianP, input PIns: Address) {Menyisipkan PIns sebagai elemen antrian QPrio sesuai dengan Prio(PIns)} {K. Awal: QPrio terdefinisi, PIns terdefinisi} {K.Akhir: PIns menjadi elemen antrian QPrio} Deklarasi: P, Prev: Address Found: boolean Deskripsi: P QPrio.Head; Prev Nil Found false while (P ≠ Nil and not Found) do if (Prio(P) < Prio(PIns)) then Found true else Prev P P Next(P) endif endwhile if Prev = Nil then {disisipkan sebagai elemen ke-1} Next(PIns) QPrio.Head QPrio.Head PIns else if (Found) then {disisipkan di tengah} Next(PInst) Next(Prev) Next(Prev) PIns else {disisipkan sebagai elemen terakhir} Next(QPrio.Tail) PIns QPrio.Tail PIns endif endif
Algoritma 4.14. Penyisipan Elemen Antrian Prioritas Aturan penghapusan elemen antrian prioritas tidak mengalami perubahan, yaitu pada kepala antrian.
Struktur Data – 63 BAB 5 TUMPUKAN 5.1 Pengertian Dasar Secara lojik tumpukan (stack) adalah senarai yang penyisipan elemen hanya dilakukan sebagai elemen pertama dan penghapusan elemen hanya dilakukan terhadap elemen pertama. Struktur data tumpukan digunakan merepresentasi pemanggilan prosedur, perhitungan ekspresi aritmatika, penelusuran balik dan algoritma lanjut lainnya. Seperti layaknya tumpukan di dunia nyata, maka elemen baru disisipkan sebagai elemen paling atas dan elemen yang dihapus adalah elemen paling atas. Berlaku prinsip LIFO (last in first out). Secara algoritmik, deklarasi tumpukan seperti terlihat pada Algoritma 1. type TInfo = integer {atau tipe terdefinisi lainnya} type Address = pointer to Elemen type Elemen = record type Stack = record S: Stack
Algoritma 5.1. Deklarasi Tumpukan Stack dikenali melalui alamat elemen pertamanya Top. Stack kosong adalah stack yang tidak memiliki elemen, Top = Nil. Top
(a) Stack Kosong Top
(b) Stack Dengan 3 Elemen
Gambar 5.1. (a) Stack Kosong, (b) Stack Dengan 3 Elemen
Struktur Data – 64 Operasi dasar terhadap tumpukan: 1. Membuat stack kosong 2. Menyisipkan elemen pada stack 3. Menghapus elemen stack 4. Memeriksa apakah stack kosong 5.1 Membuat Stack Kosong procedure CreateStack(output S: Stack) {membuat stack kosong, S.Top = Nil} {K. Awal : - } {K.Akhir: Stack S terdefinisi, S.Top = Nil} Deklarasi: Deskripsi: S.Top Nil
Algoritma 5.2. Membuat Stack Kosong 5.2 Menyisipkan Elemen Pada Stack procedure Push(input/output S: Stack, input X: TInfo) {Menyisipkan X sebagai elemen pada puncak stack} {K. Awal: S terdefinisi, X terdefinisi} {K.Akhir: X menjadi elemen puncak stack} Deklarasi: P: Address Deskripsi: Alokasi(P); Next(P) Nil; Info(P) X Next(P) S.Top S.Top P
Algoritma 5.3. Menyisipkan Elemen Pada Stack
Struktur Data – 65 5.3 Menghapus Elemen Stack procedure Pop(input/output S: Stack, output X: TInfo) {Menghapus elemen stack} {K. Awal: S terdefinisi, tidak kosong} {K.Akhir: X adalah info elemen yang dihapus} Deklarasi: Deskripsi: X Info(S.Top) S.Top Next(S.Top)
Algoritma 5.4. Menghapus Elemen Stack 5.4 Memeriksa Apakah Stack Kosong function EmptyStack(input S: Stack) boolean {mengembalikan true jika stack S kosong} Deklarasi: Deskripsi: return (S.Top = Nil)
Algoritma 5.5 Memeriksa Apakah Stack Kosong 5.5 Representasi Fisik Tumpukan Dengan Larik Stack dapat direpresentasi secara fisik menggunakan larik dengan NMAX elemen, dimana NMAX merupakan konstanta yang diperkirakan sebagai jumlah maksimum tumpukan. Deklarasi tumpukan yang direpresentasi menggunakan larik seperti pada Algoritma 5.6. const NMAX = type TInfo = type Address type Stack =
100 integer {atau tipe terdefinisi lainnya} = integer [0..NMAX] record
S: Stack
Algoritma 5.6. Deklarasi Tumpukan Representasi Larik
Struktur Data – 66 S.Top = 4
75 [1]
56 [2]
68 [3]
48 82 ... [4] [5] (a) Tumpukan Dengan 4 Elemen
[99]
[100]
S.Top = 1
75 [1]
[2]
[3]
... [4] [5] (b) Tumpukan Dengan 1 Elemen
[99]
[100]
[3]
... [4] [5] (c) Tumpukan Kosong
[99]
[100]
S.Top = 0 [1]
[2]
Gambar 5.2. Tumpukan yang Direpresentasi Menggunakan Larik
5.6 Menyisipkan Elemen Stack, Representasi Larik Kasus (1) K. Awal S.Top = 4, X = 23
75 [1]
56 [2]
68 [3]
48 [4]
K. Akhir
75 [1]
... [5]
[99]
[100]
[99]
[100]
S.Top = 5
56 [2]
68 [3]
48 [4]
23 [5]
...
Struktur Data – 67 Kasus (2) K. Awal
75 [1]
X = 46, S.Top = 100
56 [2]
68 [3]
48 [4]
23 [5]
...
K. Akhir
75 [1]
73 [99] Overflow!
56 [2]
68 [3]
48 [4]
23 [5]
...
84 [100]
S.Top = 100
73 [99]
84 [100]
Gambar 5.3. Menyisipkan Elemen Tumpukan: Representasi Larik procedure Push(input/output S: Stack, input X: TInfo) {Menyisipkan X sebagai elemen tumpukan X} {K. Awal: S terdefinisi, mungkin kosong, X terdefinisi} {K.Akhir: Jika masih tersedia tempat maka X menjadi elemen paling baru dari stack S. Jika tidak tersedia tempat lagi maka tampilkan pesan “overflow”} Deklarasi: Deskripsi: if (S.Top < NMAX) then S.Top S.Top + 1 S.ArrStack[S.Top] X else write (“overflow”) endif
Algoritma 5.7. Menyisipkan Elemen Tumpukan: Representasi Larik
Struktur Data – 68 5.7 Menghapus Elemen Stack, Representasi Larik K. Awal S.Top = 4
75 [1]
56 [2]
K. Akhir
75 [1]
68 [3]
48 [4]
... [5]
[99]
[100]
[99]
[100]
S.Top = 3, X = 48
56 [2]
68 [3]
... [4]
[5]
Gambar 5.3. Menghapus Elemen Tumpukan: Representasi Larik procedure Pop(input/output S: Stack, output X: TInfo) {Menyisipkan X sebagai elemen tumpukan X} {K. Awal: S terdefinisi, tidak koson} {K.Akhir: X adalah elemen tumpukan yang dihapus S.Top berkurang 1} Deklarasi: Deskripsi: X S.ArrStack[S.Top] S.Top S.Top – 1
Algoritma 5.8. Menghapus Elemen Tumpukan: Representasi Larik Bagaimana algoritma untuk membuat stack kosong dan fungsi untuk memeriksa stack kosong dengan representasi larik? Selesaikan! Soal Latihan 1. Buat fungsi yang mengembalikan true jika stack kosong 2. Buat fungsi yang mengembalikan true jika stack penuh (overflow)
Struktur Data – 69 Untuk menyelesaikan Soal No. 3, gunakan deklarasi stack berikut: Deklarasi: const NMAX = 5 {maksimum elemen larik} type TInfo = integer {atau tipe terdefinisi lainnya} type Address = integer[0..NMAX] type Stack =record S: Stack
Catatan: Sebagian nilai di dalam larik mungkin bukan merupakan elemen stack. Arsir yang bukan elemen stack (a) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 4, X = 82 Push(S,X) (b) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 1 Pop(S,X) (c) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 1, X = 28 Push(S,X) (d) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 4, Pop(S,X) (e) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 1, X = 37 Push(S,X)
Keadaan akhir 64 [4]
37 [5]
64 [4]
37 [5]
64 [4]
37 [5]
64 [4]
37 [5]
64 [4]
37 [5]
[1] [2] S.Top = Overflow(S)?
[3]
[4]
[5]
[1] [2] [3] [4] S.Top= X= EmptyStack(S)?
[5]
Keadaan akhir
Keadaan akhir [1] [2] [3] S.Top = Overflow(S)?
[4]
[5]
[4]
[5]
[4]
[5]
Keadaan akhir [1] [2] S.Top = EmptyQ(Q)?
[3] X=
Keadaan akhir [1] [2] [3] S.Top = Overflow(S)?
Struktur Data – 70 (f) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 2 Pop(S,X)
Keadaan akhir 64 [4]
37 [5]
[1] [2] [3] S.Top = X= EmptyStack(S)?
[4]
[5]
5. Buat algoritma untuk menyalin antrian Q1 ke antrian Q2 6. Buat algoritma untuk memecah (split) antrian Q menjadi antrian Q1 yang menyimpan info ganjil dan antrian Q2 yang menyimpan info genap. 7. Buat algoritma untuk menyalin elemen stack ke antrian 8. Buat algoritma untuk menyalin elemen antrian ke stack
Struktur Data – 71 BAB 6 GRAF 6.1 Pengertian Dasar Graf adalah himpunan simpul (vertices) dan garis yang disebut sisi (edge) yang menghubungkan simpul yang berbeda. Himpunan simpul dinyatakan dalam notasi himpunan. Himpunan sisi dinyatakan dengan rangkaian sisi. Sisi ditunjukkan dengan menuliskan nama dua simpul yang dihubungkan oleh sisi tersebut. Jika graf berarah, maka arah sisi ditunjukkan oleh simpul yang pertama. Jika graf tidak berarah, relasi antar simpul tak terurut. Simpul yang pertama tidak menunjuk ke simpul lainnya. Definisi formal graf adalah sebagai berikut: G = (V, E) dimana: V(G) adalah himpunan simpul terbatas, tidak kosong E(G) adalah himpunan pasangan simpul Gambar 1 memperlihatkan contoh-contoh graf. B
A
P
J
D
C
S
M
R
U
C (b)
(a) 1
3
5
11
7
9
(c)
Gambar 6.1. Contoh Graf (a) G1 adalah graf tidak berarah, (b) G2 adalah graf berarah, (c) G3 adalah graf berarah
Struktur Data – 72 V(G1) = {A, B, C, D} E(G1) = {(A,B), (A,D), (B,C), (B,D)} V(G2) = {P ,J, S, C, M, R, U} E(G2) = {(P,J), (P,S), (J,C), (J,M), (S,R), (S,U)} V(G3) = {1, 3, 5, 7, 9, 11} E(G3) = {(1,3), (3,1), (5,7), (5,9), (9,11), (9,9), (11,1)} 6.2 Istilah-istilah Pada Graf Ketetanggaan (Adjacency) : Dua simpul dikatakan bertetangga jka keduanya terhubung langsung. Pada Gambar 1(a) simpul A bertetangga dengan simpul B dan simpul D, simpul A tidak bertetangga dengan simpul C Bersisian (Incidency): Untuk sembarang sisi e = (V1, V2) dikatakan e bersisian dengan simpul V1 dan V2. Pada Gambar 1(a) sisi (B,D) bersisian dengan simpul B dan simpul D. Derajat: derajat sebuah simpul adalah jumlah sisi yang bersisiaan (incident) dengan simpul tersebut, dilambangkan dengan d(v). Pada Gambar 1(a) d(A) = 2, d(B) = 3 Lintasan dari simpul Vi ke simpul Vj adalah rangkaian simpul yang menghubungkan Vi ke Vj. Untuk sebuah lintasan Vi ke Vj, ada sisi (Vi , Vk), (Vk1, Vk2), . . . , (Vkn, Vj). Jadi harus ada rangkaian garis tak terputus dari Vi melalui sejumlah simpul ke Vj. Graf Gambar 2 menunjukkan lintasan dari simpul A ke simpul G, tidak ada lintasan dari simpul A ke simpul C.
A
B
C
M
Y
R
G
Struktur Data – 73 Gambar 6.2. Graf yang menunjukkan lintasan dari simpul A ke simpul G, tidak ada lintasan dari simpul A ke simpul C Siklus (Cycle) atau Sirkuit: adalah lintasan dengan simpul pertama sama dengan simpul terakhir. Pada Gambar 1(a) B, A, D, B adalah sirkuit. Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Panjang lintasan B, A, D, B adalah 3. Keterhubungan (Connected). Dua buah simpul V1 dan V2 dikatakan terhubung jika terdapat lintasan dari V1 ke V2. Graf tidak berarah disebut terhubung jika untuk setiap pasang simpul Vi dan Vj dalam himpunan V terdapat lintasan dari Vi ke Vj (yang juga berarti ada lintasan dari Vj ke Vi ). Jika tidak maka G disebut graf tidak terhubung (disconnected). Gambar 3 adalah graf terhubung. Graf G2 dan G3 pada Gambar 1 adalah graf tidak terhubung. B
A
D
C
Gambar 6.3. Graf terhubung Graf lengkap adalah graf yang setiap simpul terhubung ke setiap simpul lainnya. Gambar 4 menunjukkan dua graf lengkap. Jika ada N simpul maka akan ada N * (N – 1) sisi pada graf lengkap berarah dan N * (N – 1) / 2 sisi pada graf lengkap tak berarah.
Struktur Data – 74 J
A
B
C
D
K
N
L
M (b)
(a)
Gambar 6.4. (a) Graf lengkap berarah, (b) Graf lengkap tidak berarah Graf berbobot adalah graf yang sisinya membawa nilai. Graf berbobot dapat digunakan untuk menyatakan pentingnya nilai hubungan antar simpul, bukan hanya keberadaan hubungan tersebut. Pada Gambar 5 simpul menyatakan kota dan sisi menyatakan jalan yang menghubungkan kota-kota tersebut. Bobot yang diletakkan pada sisi menyatakan jarak dari satu kota ke kota lainnya. Mungkin saja ada banyak lintasan yang menghubungkan satu simpul dengan simpul lainnya. A 23 B
38
16 C
20
M 17
14 Y
G 16
15 D
Gambar 6.5. Graf Berbobot Lintasan dan Sirkuit Euler Lintasan Euler adalah lintasan yang melalui masing-masing sisi tepat satu kali. Bila lintasan ini membentuk sirkuit maka sirkuitnya disebut sirkuit Euler. Jadi sirkuit Euler adalah sirkuit yang melalui masing-masing sisi tepat satu kali. Graf yang mempunyai sirkuit Euler disebut graf Euler. Graf yang mempunyai lintasan Euler disebut graf semi Euler.
Struktur Data – 75 Graf yang memiliki sirkuit Euler pasti memiliki lintasan Euler, tapi tidak sebaliknya A
A
B
B
E
D
C
F
D
C (b)
(a)
B
A
C
A
E
B
D
F
C
G
D
E
(c)
(d)
Gambar 6.6. (a) dan (b) Graf yang memiliki lintasan Euler, (c) Graf yang memiliki sirkuit Euler, (d) Graf yang tidak memiliki lintasan dan sirkuit Euler Contoh terapan sirkuit Euler adalah persoalan tukang pos. Seorang tukang pos harus melalui semua jalan yang adadan kembali ke tempat awal. Pada Gambar 7, salah satu sirkuit Euler yang harus dilalui tukang pos adalah A, B, C, D, E, F, C, E, B, F, A. B
8
C
2
1 8
A
4 4
3 6
D 1
F
5
E
(c)
Gambar 6.7. Graf Persoalan Tukang Pos Lintasan dan Sirkuit Hamilton Lintasan Hamilton adalah lintasan yang melalui setiap simpul hanya boleh satu kali. Bila lintasan tersebut membentuk sirkuit maka sirkuit tersebut disebut sirkuit Hamilton. Jadi sirkuit Hamilton adalah sirkuit yang melalui tiap simpul
Struktur Data – 76 tepat satu kali, kecuali simpul asal (sekaligus sebagai simpul akhir) yang dilalui dua kali. Graf yang memiliki sirkuit Hamilton disebut graf Hamilton, sedangkan graf yang memiliki lintasan Hamilton disebut graf semi Hamilton. A
B
A
B
A
D
C
D
C
D
(a)
(b)
B
C (c)
Gambar 6.8. (a) Graf yang tidak memilik lintasan Hamilton, (b) Graf yang memiliki lintasan Hamilton, (c) Graf yang memiliki sirkuit Hamilton. Setiap lintasan Hamilton pada graf dengan n simpul terdiri dari n – 1 sisi. Setiap sirkuit Hamilton pada graf dengan n simpul terdiri dari n sisi. Contoh terapat sirkuit Hamilton adalah persoalan pedagang keliling (travelling salesman problem, TSP). Seorang pedagang harus mengunjungi setiap kota tepat satu kali dan kembali ke kota asal dengan jarak tempuh terpendek.Jika graf yang dilalui seperti pada Gambar 7, maka kemungkinan sirkuit Hamilton-nya adalah: (a) A, B, E, D, C, F, A dengan panjang lintasan = 22 (b) A, B, C, D, E, F, A dengan panjang lintasan = 23 (c) A, F, C, D, E, B, A dengan panjang lintasan = 22 6.3 Representasi Graf Graf dapat direpresentasi dengan matriks ketetanggaan atau dengan senarai ketetanggaan. Jika ada N simpul pada graf G maka matriks ketetanggaan adalah larik dengan N baris dan N kolom. Jika matriksnya adalah A, maka berlaku: A[i,j] = 1 jika simpul i bertetangga dengan simpul j A[i,j] = 0 jika simpul i tidak bertetangga dengan simpul j
A B C D
A 0 1 0 1
B 1 0 1 1 (a)
C 0 1 0 0
D 1 1 0 0
A B C D
B A B A
D C B (b)
Gambar 6.9 (a) Representasi graf Gambar 1(a) dengan matriks, (b) dengan senarai ketetanggaan
D
Struktur Data – 77 Deklarasi graf dapat dilihat pada Algoritma 6.1 dan Algoritma 6.2. const N = . . . {jumlah simpul pada graf} type Graf = array [1..N, 1..N] of boolean {atau integer} G: Graf
Algoritma 6.1. Deklarasi graf representasi matriks const N = . . . {jumlah simpul pada graf} type Address = pointer to Elemen type Elemen = record type Kepala = array[1..N] of Address type Graf = record G: Graf
Algoritma 6.2. Deklarasi graf representasi senarai 6.4 Penelusuran Graf Penelusuran graf berarti mengunjungi setiap simpul di dalam graf dan memeriksa setiap sisi. Ada dua skema penelusuran, yaitu: Pencarian mendalam (depth first search, DFS) Pencarian melebar (breadth first search, BFS) Pencarian Mendalam Misalkan penelusuran dimulai dari simpul V, simpul berikutnya yang dikunjungi adalah simpul W yang bertetangga dengan V, lalu penelusuran dimulai lagi secara rekursif dari simpul W. Ketika mencapai simpul U sedemikian, sehingga semua simpul yang bertetangga dengannya telah dikunjungi, maka pencarian dirunut balik ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul W yang belum dikunjungi. Penelusuran berakhir jika tidak ada lagi simpul yang belum dikunjungi dan dicapai dari simpul yang telah dikunjungi. Algoritma DFS memerlukan larik tambahan untuk menyimpan simpul-simpul yang telah dikunjungi.
Struktur Data – 78 procedure DFS(input V: integer) {menelusuri semua simpul graf dengan skema DFS} {K. Awal: V terdefinisi, yaitu simpul awal penelusuran} {K.Akhir: Semua simpul yang dikunjungi dicetak ke layar} Deklarasi: W: integer write (V) dikunjungi[V] true for W 1 to N do if A[V,W] = 1 then if not dikunjungi[W] then DFS(W) endif endif endfor
Algoritma 6.3. Penelusuran Graf Secara DFS Jika graf tidak berarah, penelusuran dapat dimulai dari simpul manapun. Pemanggilan DFS dari program utama adalah sebagai berikut: Deklarasi: dikunjungi: array[1..N] of boolean V, k: integer for k 1 to N do dikunjungi[k] false endfor write (“Simpul awal”); read (V) DFS(V)
Algoritma 6.4. Contoh Pemanggilan DFS dari Program Utama
Contoh, misalkan graf G yang dikunjungi seperti terlihat pada Gambar 6.10 (a). Kunjungan dimulai dari simpul 1, maka urutan simpul yang dikunjungi secara DFS adalah: 1, 2, 4, 8, 5, 6, 3, 7. Jika graf G diubah sedikit seperti terlihat pada Gambar 6.10 (b), maka urutan simpul yang dikunjungi mulai dari simpul 1 adalah: 1, 2, 3, 6, 8, 4, 5, 7.
Struktur Data – 79 1
1
2
4
3
5
6
2
7
4
3
5
6
8
8
(a)
(b)
7
Gambar 6.10. (a) Graf G awal, (b) Graf G setelah ditambah dengan sisi (2,3) Pencarian Melebar (BFS) Jika penelusuran dimulai dari simpul V, maka semua simpul yang bertetangga dengan V dikunjungi terlebih dahulu. Selanjutnya simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul tersebut dikunjungi, demikian seterusnya. Jika graf G pada Gambar 6.10 (a) dikunjungi secara BFS mulai dari simpul 1, maka urutan penelusurannya adalah: 1, 2, 3, 4, 5, 6, 7, 8. Jika graf G pada Gambar 6.10 (b) dikunjungi secara BFS mulai dari simpul 1, maka urutan penelusurannya akan tetap sa,a seperti Gambar 10 (a) yaitu: 1, 2, 3, 4, 5, 6, 7, 8. Algoritma BFS memerlukan antrian untuk menyimpan simpul yang telah dikunjungi. Tiap simpul yang telah dikunjungi masuk ke dalam antrian tepat satu kali. procedure BFS(input V: integer) {menelusuri seluruh simpul graf dengan skema BFS} {K. Awal: V terdefinisi, yaitu simpul awal penelusuran} {K.Akhir: Semua simpul yang dikunjungi ditulis ke layar} Deklarasi: W:integer Q: Queue Deskripsi: write(V) dikunjungi[V] true CreateQ(Q)
Struktur Data – 80 EnQueue(Q,V) while not EmptyQ(Q) do DeQueue(Q,V) for W 1 to N do if A[V,W] = 1 then if not dikunjungi[W] then write(W) EnQueue(Q,W) dikunjungi[W] true endif endif endfor endwhile
Algoritma 6.5. Penelusuran graf secara BFS Pemanggilan DFS dari program utama adalah sebagai berikut: Deklarasi: dikunjungi: array[1..N] of boolean V, k: integer for k 1 to N do dikunjungi[k] false endfor write (“Simpul awal”); read (V) BFS(V)
Algoritma 6.6. Contoh pemanggilan BFS dari program utama Soal Latihan 1. Diketahui graf G1 berikut: A
B F
D
(a) (b)
E
Himpunan simpul graf G1, V(G1) = Himpunan sisi graf G1, E(G1) =
Struktur Data – 81 2. Diketahui graf G2 berikut: A
93
B
14
47
30
C
50
D
21
E
(a) Himpunan simpul graf G2, V(G2) = (b) Himpunan sisi graf G2, E(G2) = 3. Buat matriks ketetanggaan dari graf G1 dan graf G2 4. Buat senarai ketetanggaan dari graf G1 dan graf G2 5. Diketahui himpunan simpul dari graf G3 berikut: V(G3) = {X, Y, Z, W} E(G3) = {(X,Y), (X,Z), (Z,Z), (Z,W)} Gambarkan graf G3 6. Tuliskan urutan simpul jika graf G1 dikunjungi secara DFS mulai dari simpul A 7. Tuliskan urutan simpul jika graf G2 dikunjungi secara BFS mulai dari dari simpul A.
Struktur Data – 82 BAB 7 POHON PENCARIAN BINER (BINARY SEARCH TREE, BST) 7.1 Pendahuluan Setiap elemen senarai menunjuk ke satu elemen berikutnya, pada struktur data BST, setiap elemen (elemen BST sering disebut simpul) menunjuk ke dua simpul lainnya, yaitu menunjuk ke simpul yang mendahului (disebut simpul “kiri”) dan ke simpul yang mengikutinya (disebut simpul “kanan”). Simpul kiri menyimpan nilai informasi yang lebih kecil dibanding simpul yang menunjuk, sedang simpul kanan menyimpan nilai informasi lebih besar dibanding simpul yang menunjuknya. 1
2
3
...
9
10
Gambar 7.1. Senarai dengan 10 elemen Gambar 1 menunjukkan senarai denga 10 elemen. Gambar 7.2 adalah BST yang dibangun dari elemen senarai pada Gambar 7.1. Perhatikan bahwa elemen sebelah kiri dari suatu elemen menyimpan nilai informasi yang lebih kecil dan elemen sebelah kanan menyimpan informasi yang lebih besar. Seperti pada senarai, alamat elemen pertama BST disimpan pada penunjuk eksternal. Pada kuliah ini, alamat elemen pertama BST diberi nama Akar. Akses terhadap BST dilakukan melalui Akar. Mengacu ke Gambar 7.2, untuk mengakses simpul yang menyimpan nilai informasi 10, kita harus melalui Akar. Nilai yang tersimpan di Akar, Info (Akar) < 10, sehingga sesuai dengan aturan bahwa simpul yang menyimpan nilai informasi lebih besar selalu terletak di sebelah kanan, maka untuk menemukan 10 kita harus menelusuri sebelah kanan dari Akar, kemudian bandingkan lagi nilainya dengan 10, masih lebih kecil, sehingga kita ke kanan lagi dst., sampai kita tiba di simpul yang menyimpan informasi 10. Jadi untuk menemukan 10 hanya diperlukan 4 kali pembandingan. Bandingkan dengan senarai, untuk menemukan 10 harus dilakukan 10 kali pembandingan.
Struktur Data – 83 Akar
5
Level 0
3
2
Level 1
8
4
6
1
9
7
Level 2
10
Level 3
Gambar 7.2. BST dengan 10 simpul 7.2 Hubungan Antar Simpul Pada BST Gambar 2 menunjukkan hubungan antar simpul pada BST. Ada 10 simpul pada Gambar 2. Setiap BST memiliki simpul pertama yang unik disebut Akar. Akar dapat memiliki simpul di kirinya disebut anak kiri dan simpul di kanannya disebut anak kanan. Simpul yang tidak memiliki anak disebut simpul daun. Simpul daun pada Gambar 2 adalah 1, 4, 7 dan 10. Dua simpul disebut bersaudara jika induknya sama. Sebuah simpul adalah ancestor dari suatu simpul jika merupakan induk dari simpul. Jadi Akar adalah ancestor dari semua simpul lain pada BST. Sebuah simpul adalah descendant dari suatu simpul jika merupakan anak dari simpul. Descendant kiri dari suatu simpul disebut sub pohon kiri dan descendant kanan disebut sub pohon kanan. Level dari suatu simpul menunjukkan jaraknya dari Akar. Level Akar adalah 0. Jumlah maksimum simpul pada level N adalah 2N. Tinggi pohon adalah maksimum level + 1. Tinggi pohon pada Gambar 2 adalah 4. Deklarasi BST adalah sebagai berikut: type TInfo = integer {atau tipe terdefinisi lainnya} type BST = pointer to Simpul type Simpul = record Akar: BST
Algoritma 7.1 Deklarasi BST
Struktur Data – 84 Akses ke semua simpul BST dimulai dari Akar. Jika P bertipe BST, maka: Info(P) adalah mengakses informasi yang disimpan di simpul yang alamatnya P Kiri(P) adalah pointer ke kiri dari simpul yang alamatnya P Kanan(P) adalah pointer ke kanan dari simpul yang alamatnya P Operasi Terhadap BST Operasi sering dilakukan terhadap BST adalah: Menciptakan BST kosong, Create Penelusuran BST, ada 3 cara yaitu inorder, preorder dan postorder Pencarian informasi tertentu pada BST, SearchBST Penyisipan simpul, InsertBST Penghapusan simpul, DeleteBST Menghitung jumlah simpul Menghitung tinggi pohon Menghitung simpul daun 7.3 Membuat BST Kosong procedure Create(output Akar: BST) {membuat BST kosong} {K. Awal: - } {K.Akhir: Akar = Nil} Deklarasi: Deskripsi: Akar Nil
Algoritma 7.2. Membuat BST Kosong 7.4 Penelusuran BST Penelusuran secara inorder Penelusuran inorder adalah kiri, akar, kanan procedure InOrder(input Akar: BST) {menelusuri BST secara inorder} {K. Awal: Akar terdefinisi } {K.Akhir: semua simpul dikunjungi secara inorder} Deklarasi: Deskripsi: if Akar ≠ Nil then InOrder(Kiri(Akar)) Proses(Info(Akar)) InOrder(Kanan(Akar)) endif
Algoritma 7.3. Penelusuran Inorder
Struktur Data – 85 Penelusuran secara preorder Penelusuran preorder adalah akar, kiri, kanan procedure PreOrder(input Akar: BST) {menelusuri BST secara preorder} {K. Awal: Akar terdefinisi } {K.Akhir: semua simpul dikunjungi secara preorder} Deklarasi: Deskripsi: if Akar ≠ Nil then Proses(Info(Akar)) PreOrder(Kiri(Akar)) PreOrder(Kanan(Akar)) endif
Algoritma 7.4. Penelusuran Preorder Penelusuran secara postorder Penelusuran postorder adalah kiri, kanan, akar procedure PostOrder(input Akar: BST) {menelusuri BST secara postorder} {K. Awal: Akar terdefinisi } {K.Akhir: semua simpul dikunjungi secara postorder} Deklarasi: Deskripsi: if Akar ≠ Nil then PostOrder(Kiri(Akar)) PostOrder(Kanan(Akar)) Proses(Info(Akar)) endif
Algoritma 7.5. Penelusuran Postorder
Struktur Data – 86 7.5 Pencarian Mencari keberadaan X di dalam BST procedure SearchBST(input Akar: BST, input X: TInfo, output Found: boolean ) {mencari keberadaan X di dalam BST} {K. Awal: Akar terdefinisi, X terdefinisi } {K.Akhir: Jika X ditemukan maka Found = true Jika X tidak ditemukan maka Found = false} Deklarasi: Deskripsi: if Akar = Nil then Found false else if Info(Akar) = X then Found true else if X < Info(Akar) then SearchBST(Kiri(Akar),X,Found) else SearchBST(Kanan(Akar),X,Found) endif endif endif
Algoritma 7.6. Pencarian Pada BST 7.6 Menyisipkan Elemen Elemen baru selalu disisipkan sebagai elemen daun. Penyisipan elemen pada BST harus mengikuti aturan dasar bahwa info sebelah kiri selalu lebih kecil dari info induk dan info sebelah kanan lebih besar dari info induk. procedure InsertBST(input/output Akar: BST, input X: TInfo) {menyisipkan X ke dalam BST} {K. Awal: Akar terdefinisi, X terdefinisi } {K.Akhir: X menjadi elemen daun} Deklarasi: Deskripsi: if Akar = Nil then Alokasi(Akar) Info(Akar) = X Kiri(Akar) Nil Kanan(Akar) Nil else if Info(Akar) < X then
Struktur Data – 87 InsertBST(Kanan(Akar),X) else if Info(Akar)> X then InsertBST(Kiri(Akar),X) else write(X, “sudah ada”) endif endif endif
Algoritma 7.7 Penyisipan Elemen BST 7.7 Menghapus Elemen Operasi lain yang berguna dalam pemeliharaan BST adalah menghapus elemen tertentu. Menghapus tidak sesederhana menyisipkan simpul. Menghapus simpul daun lebih sederhana daripada menghapus simpul akar. Secara garis besar ada tiga kasus proses menghapus simpul BST, yaitu: 1. Menghapus simpul daun (simpul yang tidak punya anak), dapat dilakukan dengan me-Nil-kan Kiri atau Kanan induk simpul tersebut. Perhatikan Gambar 3. K. Awal
K. Akhir
Induk X
Induk X
X
X Dihapus
Gambar 7.3. Menghapus Simpul Daun 2.
Menghapus simpul yang memiliki satu anak atau satu sub pohon. Jika P adalah alamat simpul yang dihapus, maka pointer orang tua dari P diisi dengan pointer anak. Gambar 4.
Struktur Data – 88 K. Awal
K. Akhir
Induk X
Induk X
X
X Dihapus
Anak X
Anak X
Gambar 7.4. Menghapus simpul yang memiliki satu sub pohon 3. Menghapus elemen yang memiliki dua anak. Kasus ini paling sulit. Ada dua cara untuk menyelesaikan penghapusan: a. Simpul yang dihapus diganti dengan simpul paling kanan (terbesar) dari sub pohon kiri, atau b. Simpul yang dihapus diganti dengan simpul paling kiri (terkecil) dari sub pohon kanan. Misalkan digunakan pilihan (a), maka cara untuk menghapus simpul adalah: Cari simpul terbesar di sub pohon kiri dari simpul yang dihapus Ganti info simpul yang dihapus dengan simpul maksimum Hapus simpul maksimum dengan cara menghapus simpul daun Perhatikan Gambar 7.5. K. Awal
K. Akhir
Akar
Akar
J
J
B
Q
L
K
B
R
N
M
P
L
Z
P
K
R
N
M
Z
P
Gambar 7.5 Menghapus simpul yang memiliki dua sub pohon
Struktur Data – 89 procedure DeleteBST(input/output Akar: BST, input X: TInfo, output Found: boolean) {menghapus simpul BST yang info-nya = X} {K. Awal: BST terdefinisi, tidak kosong} {K.Akhir: Jika X ada maka simpul yang info-nya = X dihapus dari BST dan Found = true. Jika X tidak ada maka Found = false} Deklarasi: Temp: BST function Maks(input Akar: BST)BST {mengembalikan alamat simpul maksimum pada BST} Deskripsi: if Akar = Nil then Found false else if Info(Akar) > X then DeleteBST(Kiri(Akar),X,Found) else if X > Info(Akar) then DeleteBST(Kanan(Akar),X,Found) else {X ditemukan} Found true if Kiri(Akar) = Nil then {punya satu anak kanan} Temp Akar Akar Kanan(Temp) DeAlokasi(Temp) else if Kanan(Akar) = Nil then {punya satu anak kiri} Temp Akar Akar Kiri(Temp) DeAlokasi(Temp) else {Akar punya dua anak} Temp Maks(Kiri(Akar)) Info(Akar) Info(Temp) Found true DeleteBST(Kiri(Akar), Info(Temp),Found) endif endif endif endif endif
Algoritma 7.8. Menghapus Simpul BST
Struktur Data – 90 7.8 Menghitung Tinggi Pohon function Tinggi(input Akar: BST) integer {mengembalikan tinggi BST} Deklarasi: t1,t2: integer Deskripsi: if Akar = Nil then return 0 else t1 Tinggi(Kiri(Akar)) t2 Tinggi(Kanan(Akar)) if t1 > t2 then return t1 + 1 else return t2 + 1 endif endif
Algoritma 7.9. Menghitung Tinggi Pohon 7.9 Menghitung Jumlah Simpul function JumlahSimpul(input Akar: BST) integer {mengembalikan jumlah simpul BST} Deklarasi: Deskripsi: if Akar = Nil then return 0 else return (1 + JumlahSimpul(Kiri(Akar)) + JumlahSimpul(Kanan(Akar))) endif
Algoritma 7.10. Menghitung Jumlah Simpul
Struktur Data – 91 7.10 Menghitung Jumlah Daun function JumlahDaun(input Akar: BST) integer {mengembalikan tinggi BST} Deklarasi: t1,t2: integer Deskripsi: if Akar = Nil then return 0 else if (Kiri(Akar) = Nil and Kanan(Akar) = Nil) return 1 else return JumlahDaun(Kiri(Akar)) + JumlahDaun(Kanan(Akar)) endif endif
Algoritma 7.11. Menghitung Jumlah Daun Soal Latihan 1. Gunakan pohon berikut untuk menjawab setiap pertanyaan secara independen (jawab setiap pertanyaan berdasarkan pohon asal) Akar
43
9
2
1
49
20
4
47
33
57
55
31
a. b. c. d. e.
Berapa simpul pada pohon tersebut Berapa maksimum banyaknya simpul pada level dimana 55 berada? Tuliskan semua info pada simpul level 3 Berapa tinggi pohon? Berapa simpul daun? Tuliskan yang mana saja
Struktur Data – 92 f. g. h. i. j. k. l. m. n. o. p.
Bagaimana bentuk pohon setelah penyisipan 3 Bagaimana bentuk pohon setelah penyisipan 90 Bagaimana bentuk pohon setelah penyisipan 56 Bagaimana bentuk pohon setelah 55 dihapus Bagaimana bentuk pohon setelah 20 dihapus Bagaimana bentuk pohon setelah 43 dihapus Tuliskan semua ancestor 33 Tuliskan semua descendant 20 Bagaimana keluaran traversal postorder Bagaimana keluaran traversal preorder Bagaimana keluaran traversal inorder
2.
Informasi yang tersimpan pada simpul pohon terdiri dari 3 karakter. Bagaimana bentuk pohon jika urutan masukan adalah sebagai berikut: fox, dog, leg, hoe, egg, pig, elf, boy, box, zoo Asumsi: penyisipan dilakukan terhadap pohon kosong
3.
Bagaimana bentuk pohon, jika sebelum dilakukan penyisipan, informasinya sudah tersusun urut?
4.
Gambarkan BST jika diketahui urutan masukan sebagai berikut: 23, 10, 43, 52, 37, 58, 48
5.
Buat algoritma untuk menghitung total info pada BST
6.
Buat algoritma untuk menghitung banyak simpul yang info-nya bernilai genap
Struktur Data – 93 DAFTAR PUSTAKA Dale, Nell, C++ Plus Data Structures, Jones and Bartlett Publisher, Massachussets, 2003 Kernighan, Brian W. & Ritchie, Dennis M., Language, Prentice Hall, 1988
The ANSI
C Programming
Wirth, Niklaus, Algorithms + Data Structures = Programs, Prentice-Hall of India, 1996
