BAB 1 PENGANTAR KE STRUKTUR DATA

Struktur Data - 1 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.

Struktur Data - 2 3.

Bagian deksripsi berisi rancangan instruksi yang harus dieksekusi oleh komputer.

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-todo} 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

Struktur Data - 7 Contoh 1.7: Pengulangan dengan while-do 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] ....

[NMAX]

[1] [2] [3] [4] [5] [6] [7] [8] [9] [N] ...

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.4 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: MhsTerbaik  A[1]

{indeks larik}

Struktur Data - 15 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

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

Struktur Data - 19 Jika persoalan tersebut direpresentasikan dengan senarai seperti terlihat pada Gambar 3.2. 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 Definisi Senarai Dari Gambar 2 terlihat bahwa setiap elemen larik, selain menyimpan data juga menyimpan “alamat” (dalam Gambar 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 3.2 Tipe Pointer 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

3.3 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.1 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.3.2 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 (“senarai 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; P  L.First 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

Struktur Data - 27 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 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.3.3 Penyisipan Elemen 1. Penyisipan sebagai elemen pertama 2. Penyisipan sebagai elemen tengah 3. Penyisipan sebagai elemen terakhir

Struktur Data - 28 Penyisipan Sebagai Elemen Pertama Sebelum Penyisipan

Setelah Penyisipan

First

First

58

60

73

73

58

60

P

Gambar 3.7. Penyisipan Sebagai Elemen Pertama

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 3.8. Penyisipan Sebagai Elemen Tengah

Struktur Data - 29

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

Struktur Data - 30 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 3.3.4 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

58

P

Gambar 3.13. Menghapus Elemen Pertama 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.13. Menghapus Elemen Pertama

73

Struktur Data - 31 Menghapus Elemen Tengah Sebelum Penghapusan

Setelah Penghapusan

First

First

Prev

60

Prev

58

73

60

58

73

P

Gambar 3.11. 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

Menghapus Elemen Terakhir Sebelum Penghapusan

Setelah Penghapusan

First

First

PrevLast

60

58

PrevLast

Last

73

60

58

Last

73

P

Gambar 3.12. Menghapus Elemen Terakhir

Struktur Data - 32

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 Contoh 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.13. Kasus (1) jika X tidak ditemukan K.Akhir

K. Awal First

Mis. X = 60

58

First

73

60

58

58

73

P Kasus (2) jika X ditemukan K.Akhir

K. Awal First

Mis. X = 73

58

First

73

Gambar 3.13. Pencarian dan Penyisipan

73

Struktur Data - 33 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 Alokasi(P) Info(P)  X Next(P)  Nil InsertFirst(L, P) endif

Algoritma 3.16. Pencarian dan Penyisipan Contoh 6: 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.14. Pencarian dan Penghapusan

Struktur Data - 34

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 and 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 3.3.5 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)

Struktur Data - 35 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.15. 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 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.

Struktur Data - 36 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 Alokasi(Q) Next(Q)  Nil

Struktur Data - 37 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

80

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

Struktur Data - 38 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 Mengambil Info Tertentu (Query) Contoh: diketahui senarai L1, akan diambil elemen senarai yang info-nya < X, hasilnya disimpan di senarai L2

Struktur Data - 39 K. Awal L1.First Mis. X = 55

70

53

80

53

40

54

65

40

54

K.Akhir L2.First

Gambar 3.20. 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 - 40 3.3.6 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 - 41 Contoh 3.6: 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 - 42 3.4 Multi Linked List Senarai yang elemennya senarai. Contoh 3.7: senarai data pegawai anak-anaknya type DataAnak = record type AddressA = pointer to CellAnak type CellA = record type DataPeg = record type AddressP = pointer to CellP type CellP = record type ListPeg = record L: ListPeg

{L adalah senarai pegawai}

Algoritma 3.25 Deklarasi senarai pegawai dengan anak-anaknya Gambar 3.21 memberikan ilustrasi mengenai senarai pegawai dan anak-anaknya. Bahan diskusi: Apakah identitas orang tua (NIP) perlu disimpan juga di dalam DataAnak? Berikan alasannya

Struktur Data - 43 Elemen CellA

NextP

Elemen CellP InfoP

InfoA

NextA

NextA

Anak1Pegawai1

Anak2Pegawai1

Pegawai3

NextP

Pegawai2

NextP

Pegawai1

NextP

FirstP

Anak1Pegawai3

...

PegawaiN

Anak1PegawaiN

Anak2PegawaiN

Anak3PegawaiN

Gambar 3.21 Senarai Pegawai Dengan Anak-anaknya

Struktur Data - 44 Soal Latihan 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.

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 menyisipkan sebuah elemen sebagai elemen ke-k dari senarai.

9.

Buat algoritma untuk menghapus semua elemen senarai yang info-nya = X.

10. Buat algoritma untuk menghapus elemen senarai yang menyimpan info terkecil (minimum) 11. Buat algoritma untuk menyambung senarai S1 dengan senarai S2, dengan senarai S2 berada” di depan” senarai S1. 12. 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. 13. 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.

Struktur Data - 45 14. Buat algoritma untuk mengambil info yang bernilai ganjil dari senarai S1 dan menyimpannya di senarai S2 15. Diketahui senarai yang info elemennya bertipe DataMhs (deklarasi Algoritma 20), buat algoritma untuk memperoleh data mahasiswa dengan IPK tertinggi. Keluaran bertipe DataMhs. 16. 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. 17. Dengan deklarasi yang sama seperti Soal No. 15, buat algoritma untuk menghitung IPK rata-rata seluruh mahasiswa. 18. 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. 19. Buat algoritma untuk menghapus elemen senarai mahasiswa yang NIM-nya = NIMX 20. Buat algoritma untuk menghapus semua elemen senarai mahasiswa yang IPK-nya < 2.0 21. Buat algoritma untuk mengambil semua data mahasiswa dengan IPK ≤ 2.0 dan menyimpannya di senarai L2. 22. Berdasarkan deklarasi data pegawai beserta anak-anaknya (Gambar 3.21), tuliskan algoritma untuk mencetak data pegawai beserta anak-anaknya. 23. Tuliskan algoritma untuk mencetak semua data pegawai yang tidak memiliki anak. 24. Buat algoritma untuk menentukan data orang tua jika diberi masukan identitas anaknya.

Struktur Data - 46 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

Struktur Data - 47 4.2 Operasi Dasar Terhadap Antrian 1. Membuat Antrian Kosong (CreateQ) 2. Menyisipkan Elemen (EnQueue) 3. Menghapus Elemen (DeQueue) 4. Memeriksa Apakah Antrian Kosong 4.2.1 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.2.2 Memeriksa Apakah Antrian Kosong Fungsi IsEmptyQ mengembalikan true jikaantrian Q kosong function IsEmptyQ(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 - 48 4.2.3 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 IsEmptyQ(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 - 49 4.2.4 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 - 50 4.3 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 - 51 4.3.1 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.3.2 Fungsi Untuk Memeriksa Antrian Kosong function EmptyQ(input Q: Antrian) boolean {mengembalikan true jika antrian kosong, Q.Tail = 0}

Q.Head = 0 and

Deklarasi: Deskripsi: return (Q.Head = 0 and Q.Tail =0)

Algoritma 4.8. Memeriksa Antrian Kosong 4.3.3 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 - 52 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 - 53

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.4.4 Menghapus Elemen Antrian, Representasi Fisik Larik Ada dua alternatif, yaitu: 1. Elemen bergeser maju, seperti layaknya antrian 2. Head bergeser maju 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 - 54 Kasus (2) K. Awal Q.Head = 1

57 [1]

Q.Tail = 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 - 55 5.4.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 - 56

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

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 Empty(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 - 58 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 [1] [2] [3] [4] Q.Head = 4, 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 - 59 (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. Buat algoritma untuk menyalin antrian Q1 ke antrian Q2 3. 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 4.13. 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 - 60

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 - 61 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 - 62 5.2 Operasi dasar terhadap tumpukan: 1. Membuat stack kosong 2. Menyisipkan elemen pada stack 3. Menghapus elemen stack 4. Memeriksa apakah stack kosong 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 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 - 63 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 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.3 Representasi Fisik Tumpukan Dengan Larik Stack dapat drepresentasi 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 - 64

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

Menyisipkan Elemen Tumpukan: 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 - 65 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 - 66 Menghapus Elemen Tumpukan: 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) 3. 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

Struktur Data - 67

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) (f) Keadaan awal 45 78 56 [1] [2] [3] S.Top = 2 Pop(S,X)

Keadaan akhir 64 [4]

37 [5]

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] S.Top = Overflow(S)?

[3]

[4]

[5]

[3] X=

[4]

[5]

[3]

[4]

[5]

[4]

[5]

Keadaan akhir [1] [2] S.Top = EmptyQ(Q)? Keadaan akhir [1] [2] S.Top = Overflow(S)? Keadaan akhir [1] [2] [3] S.Top = X= EmptyStack(S)?

Struktur Data - 68 4. Buat algoritma untuk menyalin antrian Q1 ke antrian Q2 5. Buat algoritma untuk memecah (split) antrian Q menjadi antrian Q1 yang menyimpan info ganjil dan antrian Q2 yang menyimpan info genap. 6. Buat algoritma untuk menyalin elemen stack ke antrian 7. Buat algoritma untuk menyalin elemen antrian ke stack

Struktur Data - 69 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 - 70 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

Gambar 6.2. Graf yang menunjukkan lintasan dari simpul A ke simpul G, tidak ada lintasan dari simpul A ke simpul C

Struktur Data - 71 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. J

A

B

C

D (a)

K

N

L

M (b)

Gambar 6.4. (a) Graf lengkap berarah, (b) Graf lengkap tidak berarah

Struktur Data - 72 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. Graf yang memiliki sirkuit Euler pasti memiliki lintasan Euler, tapi tidak sebaliknya

Struktur Data - 73 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 tepat satu kali, kecuali simpul asal (sekaligus sebagai simpul akhir) yang dilalui

Struktur Data - 74 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

C

(b)

(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 (b)

D C

D

B

Gambar 6.9 (a) Representasi graf Gambar 1(a) dengan matriks, (b) dengan senarai ketetanggaan

Struktur Data - 75 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 - 76

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 - 77 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 - 78 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 - 79 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 - 80 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 - 81 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 - 82 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 7.3 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.1 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.3.2 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 - 83 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 - 84 7.3.3 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.3.4 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

Struktur Data - 85 if Info(Akar) < X then 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.3.5 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 7.4.

Struktur Data - 86 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 - 87

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

Struktur Data - 89 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 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

Struktur Data - 90 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. f. g. h. i. j. k. l. m. n. o. p. 2.

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

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

Struktur Data - 91 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 - 92 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

Liem, Inggriani, Diktat Kuliah Algoritma dan Pemrograman Prosedural, Jurusan Teknik Informatika ITB, 1996 Wirth, Niklaus, Algorithms + Data Structures = Programs, Prentice-Hall of India, 1996