Univ. Indo Global Mandiri STRUKTUR DATA



Univ. Indo Global Mandiri

STRUKTUR DATA 

FAKULTAS ILMU KOMPUTER 2013

 1 




DAFTAR ISI HALAMAN DEPAN .........................................................................................

i

PRAKARTA ...........................…………………………………………….......................

ii

DAFTAR ISI ……………………………………………………..………..............................

iii

BAB I PENDAHULUAN I.1.

Dasar Pengetahuan Strukur Data ………………………………….............

1

BAB JENIS STRUKTUR DATA II.1

Jenis .....................................………………………………………................

5

II.2

Array ........................................……………………………………...............

4

II.3.

Record ………………………………………………..........................................

5

II.4.

Pointer ……………………………………....................................................

6

II.4.1

Operasi pada Pointer……………………………………................................

7

BAB III PENGURUTAN DATA (SORTING) III.1.

Pengurutan Internal dan Pengurutan Ekternal ..............................

9

III.2.

Pengurutan gelembung (Bubble sort) ..............................................

9

III.2.1

Algoritma Pengurutan gelembung ....................................................

9

III.3.

Pengurutan Maksimum dan minimum (Maks sort / Min Sort) ......

12

III.3.1

Algoritma Pengurutan Maksimum ..................................................

12

III.4.

Pengurutan Sisip ( Insertion Sort ) ...................................................

14

III.4.1

Algoritma pengurutan sisip menaik .................................................

14

BABA IV SENARAI BERANTAI (LINKED LIST) IV.1.

Defenisi Linked List ..........................................................................

16

IV.2

Penyajian Linked Llist secara logic didalam memori .....................

16

IV.3.

Operasi dasar pada linked list ...........................................................

18

IV.3.1

Penciptaan dan penghancuran simpul ............................................

18

IV.3.2

Penyisipan simpul ke linked list .......................................................

18

IV.3.3

Penghapusan simpul suatu linked list ..............................................

21

IV.3.4

Pembacaan Isi Linked List ................................................................

22

IV.3.5

Senarai Berantai Berkepala (Header Linked List ) ..........................

24

BAB V TUMPUKAN (STACK) V.1.

Pengertian .........................................................................................

26

V.2

Operasi pada Tumpukan (Stack) .......................................................

26

V.3.

Penyajian Tumpukan ........................................................................

27

V.4

Aplikasi pada tumpukan ..................................................................

28

BAB VI ANTRIAN (QUEUE)  2 




VI.1.

Pengertian antrian ............................................................................

30

VI.2.

Notasi Pada Queue ...........................................................................

30

VI.3.

Deklarasi Queue Dalam Link List ....................................................

30

VI.4.

Operasi Dasar Pada Queue ...............................................................

30

VI.5.

Jenis-jenis Antrian ............................................................................

33

BAB VII T R E E VII.1.

Pohon / tree ........................................................................................

34

VII.2.

Pohon binary (binary tree) ...............................................................

34

VII.3.

Pohon biner lengkap .........................................................................

35

VII.4.

Pohon 2 ..............................................................................................

35

VII.5.

Menyajikan pohon umum menjadi pohon biner ..............................

36

VII.6.

Traversal pohon biner ......................................................................

37

 3 




BAB I PENDAHULUAN Struktur data adalah cara menyimpan atau merepresentasikan data didalam komputer agar bisa dipakai secara efisien. Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol. Struktur data dapat di artikan juga sebagai representasi data pada memory secara logika dan meng-karakterisasikan setiap variabel dalam program secara eksplisit ataupun implisit, Untuk operasi yang dibolehkan/berlaku pada object data tersebut sehingga sangat diperlukan dalam perencanaan Algoritma dan penyusunan program sebagai dasar teknik dari Database Pemakaian struktur data yang tepat didalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data. Dalam pengertian lain, Struktur Data dapat juga di sebut sebagai suatu kumpulan objek-objek data yang memiliki aturan (terorganisir) yang kemudian di golongkan berdasarkan operasi-operasi untuk memanipulasinya. Contoh objek data tersruktur adalah Array, Record, shorting, linklist,Stack, Queue, Tree, graph..dll I.1. Dasar Pengetahuan Struktur data Dalam mempelajari struktur data hal-hal awal yang perlu kita ketahui adalah tentang indentifier, konstanta, variable, dan tipe data. a) Identifier Identifier merupakan nama yang digunakan untuk keperluan menyimpan suatu nilai, pendeklarasian variabel, konstanta, tipe dan nama program atau sub program. Identifier tidak boleh ditulis secara sembarangan. Aturan Penulisan Identifier Nama identifier harus dimulai dengan karakter huruf alfabet a-z atau A-Z. 1. Setelah karakter pertama, dapat dilanjutkan dengan karakter alfanumerik (angka maupun huruf) dan underscore (_).  4 




2. Dalam penulisan identifier tidak boleh menggunakan karakter-karakter berikut ini : ~ ! @ # $ % ^ & () * ) - + = `; : “ „ < > , . ? / { } [ ] | \ 3. Tidak boleh menuliskan identifier dengan nama yang sama pada kata kunci dari Pascal, seperti and, array, begin, case, const, div, do, downto, else, end, file, for, forward, function, goto, if, in, label, mod, nil, not, of, or, packed, procedure, program, record, repeat, set, then, to, type, until, var, while, with

4. Jika ingin tetap digunakan, maka kata tersebut harus dirangkai dengan kata/karakter yang lain. Misal program_if, begin1. b) Konstanta Suatu konstanta direferensikan lewat identifier dan dapat diberikan nilai tertentu. Nilai yang disimpan di dalam konstanta tidak dapat berubah. Kata kunci di dalam Pascal untuk mendeklarasikan konstanta adalah const. Contoh program konst; uses crt; const phi = 3.1415926535897932; (* real *) fakultas = „Teknologi Informasi‟; (* string *) begin clrscr; writeln(phi); writeln(fakultas); readln; end.

c) Variabel Varibel hampir mirip dengan konstanta. Nilai yang disimpan di dalam variabel dapat diubah kapan saja di dalam program. Kata kunci di dalam Pascal untuk mendeklarasikan konstanta adalah var. Setiap variabel yang dibuat di dalam satu baris harus dipisah dengan tanda koma. Contoh Variabel program vari; uses crt; var nama : string; nim : integer; nilai : char; begin nama := „Annisa Fitriani‟; nim := 12293678; nilai := „A‟; writeln(„NAMA : ‟,nama); writeln(„NIM : ‟,nim); writeln(„Nilai: ‟,nilai); end.

d) Type data Berdasarkan nilai yang disimpan di dlam variabel, terdapat 4 jenis tipe data.  5 




1) Integer Integer adalah tipe data nilainya merupakan bilangan bulat dan terbagi atas beberapa macam. Berikut ini adalaha tabelnya: Type

Range

Ukuran

Format

ShortInt Integer LongInt Byte Word

-128…127 -32768...32767 2147483648…2147483647 0…255 0…65535

1 2 4 1 2

Signed 8-bit Signed 16-bit Signed 32-bit Unsigned 8-bit Unsigned 16-bit

2) Boolean Boolean digunakan untuk merepresentasikan logika. Boolean hanya dapat bernilai True(1) dan False(0). Di bawah ini adalah beberapa tipe data Boolean: Type

Range

Ukuran

Boolean ByteBool WordBool LongBool

Bytesized Byte-sized Wordsized Longsized

1 (8bit) 1 (8bit) 2 (16bit) 4 (32bit)

3) Real Real biasanya digunakan untuk merepresentasikan nilai pecahan. Jenis-jenis tipe data real seperti pada tabel berikut ini: Type Real Single Double Extended Comp

Range ±2.9×10-39 … 1.7×1038 ±1.5×10-45 ... 3.4×1038 ±5×10-324 ... 1.7×10308 ±3.4×10-4932 ... 1.1×104932 ±9.2×1018 ... 9.2×1018

Ukuran 6 4 8 10 8

Digit 11-12 7-8 15-16 19-20 19-20

4) Karakter Tipe data karakter hanya dapat menampung satu karakter saja dan mengalokasikan satu byte memori. 5) String String adalah tipe data gabungan (array) dari bebrapa karakter. e)

Operasi Aritmetika Macam-macam operator aritmetik pada Pascal Operator + * / div mod

Operation Penjumlahan Pengurangan Perkalian Pembagian Pembagian Integer

Operands real/integer real/integer real/integer real/integer integer integer

Result real/integer real/integer real/integer real integer integer

 6 



Univ. Indo Global Mandiri Modulus

f)

Operasi Aritmetika Operasi aritmetik dalam Pascal tidak dapat diterapkan pada variabel bertipe data boolean dan char. Untuk menyatakan tanda negatif dari suatu nilai digunakan tanda minus (-). Contoh operasi aritmetika. bilBulat := (2*15)+(-2) bilRiil := 37.5 * 3 - 9 Contoh Operasi Aritmetika program arit; uses crt; const phi = 3.14; var jari : integer; luas : real; begin clrscr; jari := 5; luas := phi * (jari*jari); writeln(„LUAS: ‟,luas); end.

BAB II JENIS STRUKTUR DATA  7 




II.1. Jenis Data dapat dikatagorikan menjadi : a) Type data sederhana terdiri atas  Data sedehana tunggal Contoh: integer, real,boolean,karakter  Data sederhana majemuk Contoh : string b) Struktur data terdiri atas  Struktur data sederhana Contoh type data sederhana, type terstruktur, matrik, array, record  Struktur data majemuk, terdiri atas :  Linier  Contoh linked list,stack (tumpukan), queue (antrian)  Non linier  Contoh pohon binary (binary tree), pohon cari binar (Binary search tree), pohon cari M Way (M Way search) , general tree, graph II.2. Array Array adalah suatu tipe data terstruktur yang terdapat didalam memori, yang mempunyai tipe data yang sama dengan jumlah komponen yang tetap. Digunakan untuk merepresentasikan sekumpulan informasi yang bertipe sama dan disimpan dalam urutan yang sesuai dengan defenisi indeks secara kontigue dalam memori komputer. Tipe data indeks yang dapat digunakan adalah tipe data yang memiliki keterurutan misalkan integer, karakter Penyimpanan array secara logik dlm memori komputer seperti dibawai ini

Deklarasi Array type = array[index array] of

Contoh Deklarasi array untuk nama hari Hari = (senin,selas,rabu,kamis,jumat,sabtu,minggu); Type namaHari : array[hari] of string;

Deklarasi array untuk nama bulan Type bulan : array[12] of string

Deklarsi array menggunakan konstanta untuk menentukan indeks array Const maks = 100; Type nilai : array[maks] of string;

Kekebihan Array Keunggulan array adalah sebagai berikut :  8 




1. Array sangat cocok untuk pengaksesan acak. Sembarang elemen di array dapat diacu secara langsung tanpa melalui elemen-elemen lain. 2. Jika berada di suatu lokasi elemen, maka sangat mudah menelusuri ke elemenelemen tetangga, baik elemen pendahulu atau elemen penerus. 3. Jika elemen-elemen array adalah nilai-nilai independen dan seluruhnya harus terjaga, maka penggunaan penyimpanannya sangat efisien. Kelemahan Array Array mempunyai fleksibilitas rendah, sehingga tidak cocok untuk berbagai aplikasi karena array mempunyai batasan sebagai berikut : 1. Array harus bertipe homogen. Kita tidak dapat mempunyai array dimana satu elemen adalah karakter, elemen lain bilangan, dan elemen lain adalah tipe-tipe lain. 2. Kebanyakan bahasa pemrograman mengimplementasikan array statik yang sulit diubah ukurannya di waktu eksekusi. Bila penambahan dan pengurangan terjadi terus-menerus, maka representasi array :  Tidak efisien dalam penggunaan memori  Menyiakan banyak waktu komputasi  Pada suatu aplikasi, representasi statis tidak dimungkinkan II.3. Record Record (rekaman) merupakan kumpulan data yang terdiri dari beberapa field yang memiliki tipe data berbeda ataupun sama. Penyimpanan Record secara logik dalam memori komputer seperti dibawah ini.

Kelemahan Record  Hanya dapat menginput satu set/baris data Record  Pada satu set/baris data dapat terdiri beberapa field yang memiliki tipe data yang berbeda. Pada implementasi ke bahasa pemrograman Array dan Record dapat di gabungkan dalam satu type data bentukan Record. II.4. Pointer Pointer adalah variabel yang berisi alamat memori sebagai nilainya. Pointer digunakan bersamaan dengan dynamic memory allocation. Data yang ditunjuk dengan variabel pointer merupakan alokasi dinamik, selama eksekusi program. Ini berarti program dapat mengciptakan dan menghapus data yang di tunjuk oleh variabel pointer. Larik dan record merupakan perubah statik (banyak data yang diolah terbatas).

 9 




Peubah Dinamis adalah peubah yang akan dialokasikan hanya pada saat diperlukan yaitu setelah program dieksekusi. Peubah dinamis menggunakan variabel Pointer Pointer adalah variabel yang sering dikatakan sebagai variabel yang menunjuk ke variabel yang lain.Perbedaan antara variabel bertipe array dan pointer

Deklarasi Pointer  Bentuk Umum Type = ^ = Var PI,P2 =

Contoh Type point = ^data; data = integer; Var PI,P2 = point;



Bentuk Umum Type

pointer> tipe data > tipe data1> tipe data2> tipedata n>

= ^ = record; = = =

Var PI,P2 =

Contoh Type point = ^data; data = record; nama : string[25]; alamat : string[35]; pekj : string[30]; end; Var PI,P2 = point; New(pI); New(p2);

II.4.1. Operasi Pada Pointer Ada 2 operasi dasar yang bisa kita lakukan data yg bertipe pointer yaitu  Pengkopian Pointer Contoh : New(p1); New(p2); P1^.nama := “Anisa “;

 10 



Univ. Indo Global Mandiri P1^.alamat := “Km. 5”; P1^.Pekj := “Wiraswasta” P2 := PI;



Pengkopian isi simpul Jika statemen yang diberikan adalah P2^ :=

P1^

maka hasil yang diperoleh

 11 




BAB III PENGURUTAN DATA (SORTING) III.1. Pengurutan Internal dan Pengurutan Ekternal Pengurutan dibagi menjadi 2 kelompok :  Pengurutan Internal Pengurutan terhadap sekumpulan data yang disimpan di memori utama komputer. Bersifat sementara 2. Pengurutan Eksternal Pengurutan data yang disimpan didalam memori sekunder. Bersifat tetap. Banyaknya algoritma pengurutan yang tersedia menimbulkan pertanyaan : algoritma manakah yang memiliki kinerja paling baik?. Kinerja pengurutan data sangatlah menentukan kinerja sistem. Karena itu pemilihan Metode pengurutan yang cocok akan berperan penting dalam suatu aplikasi. Pada Bab ini metode pengurutan yang akan dibahas hanya tiga yaitu 1. Pengurutan Gelembung (Bubble Sort) 2. Pengurutan Maksimum/Minimun (Maximum / Minimum Sort) 3. Pengurutan Sisip (Inserrtion Sort) III.2. Pengurutan gelembung (Bubble sort) Metode pengurutan gelembung di inspirasi dari gelembung sabun yang berada di atas permukaan air. Karena berat jenis sabun lebih ringan dari pada berat jenis air, maka gelembung sabun akan selalu terapung diatas air. Prinsip pengapungan diatas digunakan pada pengurutan gelembung. Elemen larik yang berharga paling kecil “diapungkan” artinya diangkat keatas (atau ke ujung larik) melalui pertukaran Proses pengapungan ini dilakukan sebanyak N kali langkah. Pada akhir setiap langkah ke K, larik L[1..N] akan terdiri dari dua bagian yang sudah terurut yaitu L[1..K] dan bagian yang belum terurut L[K+1..N]. Setelah langkah terakhir diperoleh larik L[1..N] terurut menaik III.2.1. Algoritma Pengurutan gelembung Langkah 1 : Mulai dari elemen K = N, N-1,…2, bandingkan L[K] dengan L[K-1],  jika L[K] < L[K-1], tukar L[K] dengan L[K-1]  Pada akhir langkah 1, elemen L[1] berisi harga minimum pertama. Langkah 2 :  Mulai dari elemen K = N, N-1,…3, bandingkan L[K] dengan L[K-1], jika L[K] < L[K1] tukar L[K] dengan L[K-1] Pada akhir langkah 2, elemen L[2] berisi harga minimum kedua dari larik L[1..2] yang terurut. Langkah 3 :  12 




Mulai dari elemen K = N, N-1,…4, bandingkan L[K] dengan L[K-1], jika L[K] < L[K-1] tukar L[K] dengan L[K-1] Pada akhir langkah 3, elemen L[3] berisi harga minimum kedua dari larik L[1..3] yang terurut. Langkah N - 1 : Mulai dari elemen K = N, bandingkan L[K] dengan L[K-1],  jika L[K] < L[K-1] tukar L[K] dengan L[K-1]  Pada akhir langkah N, elemen L[N] berisi harga minimum dari larik L[1..N] yang terurut. Contoh : Terdapat larik berisi dengan 6 buah elemen ( N=6) yang belum terurut. Lakukan metode Bubble Sort untuk isi larik tersebut.

 13 




Akhir dari langkah 5 menghasilkan deretan data didalam larik L yang sudah terurut menaik. Untuk seluruh prosedur pengurutan pada Bab ini menggunakan Deklarasi Array sebagai berikkut : {**Mendefenisikan struktur data**} type larik = array[1..100] of integer; var l : larik; i,n,k,temp : integer; Prosedur untuk menginput data sebanyak N data adalah write('Banyak data yang di input : ');readln(n); for i :=1 to n do begin write ('Data ke ',i,' : ');readln(l[i]); end;

Prosedur untuk menampilkan data sebanyak data yang di input adalah writeln;writeln('Data yang sudah terurut adalah'); for k := 1 to n do write(l[k],' '); end.

Prosedur pengurutan gelembung Prosedur Pengurutan Gelembung for i := 1 to n-1 do begin for k :=n downto i+1 do begin if l[k] < l[k-1] then begin {pertukaran l[k] dengan l[k-1]} temp := l[k]; l[k] := l[k-1]; l[k-1] := temp; end; end; end;

 14 




III.3. Pengurutan Maksimum dan minimum (Maksimum sort / Minimum Sort) Metode pengurutan ini berdasarkan pada pemilihan nilai maksimum atau minimum didalam larik. Gagasannya adalah memilih elemen maksimum atau minimum yang di pertukarkan pada elemen ujung larik. Kemudian elemen ujung tersebut di isolasi untuk tidak disertakan lagi pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa sampai data telah terurut maksimum/minimum dan tidak dapat ditukar lagi. Metode pengurutan maksimum atau minimum disebut juga sebagai pegurutan berdasarkan pemilihan/seleksi (selection Sort) III.3.1. Algoritma Pengurutan Maksimum Secara ringkas, algoritma pengurutan maksimum dinyatakan dalam urutan langkah sebagai berikut : Langkah 1  Tentukan harga maksimum didalalam L[1..k]  Pertukarkan harga maksimum dengan elemen L[k] Langkah 2  Tentukan harga maksimum didalalam L[1..k-1]  Pertukarkan harga maksimum dengan elemen L[k-1] Langkah 3  Tentukan harga maksimum didalalam L[1..k-2]  Pertukarkan harga maksimum dengan elemen L[k-2] Langkah N - 1  Tentukan harga maksimum didalalam L[1.. K-2]  Pertukarkan harga maksimum dengan elemen L[N-2] Elemen yang tersisa adalah L[1], tidak perlu diurut lagi karena karna sudah terurut. Contoh : tinjau larik dengan k = 6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut menaik

 15 




Akhir dari langkah 5 menghasilkan deretan data didalam larik L yang sudah terurut menaik. Prosedur Pengurutan Maksimum Menaik u := n; for i := 1 to n-1 do begin maks := l[1]; imaks := 1; for j := 2 to u do begin if l[j] > maks then begin maks := l[j]; imaks := j; end; end; {pertukaran maks dengan l[u]} temp := l[u]; l[u] := l[imaks]; l[imaks] := temp; {larik l[u..n] terurut, larik l[1..u-1] belum terurut} u := u-1; end;

Untuk prosedur minimum, silakan anda lakukan sendiri sebagai latihan  16 




III.4. Pengurutan Sisip ( Insertion Sort ) Pengurutan sisip (Insertion sort) adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dapat dilakukan dengan cara melakukan pencarian beruntun didalam larik. Selama pencarian posisi yang tepat dilakukan pergeseran elemen larik. III.4.1. Algoritma pengurutan sisip menaik Andaikan : Misalkan L[1] dianggap sudah pada tempatnya Langkah 2 L[2] harus dicari tempatnya yang tepat pada L[1..2] dengan cara menggeser elemen L[1..1] kekanan,  bila L[1..1] > L[2]. Misalkan posisi yang tepat adalah K, sisipkan L[2] pada L[K] Langkah 3  L[3] harus dicari tempatnya yang tepat pada L[1..3] dengan cara menggeser elemen L[1..2] kekanan,  bila L[1..2] > L[3]. Misalkan posisi yang tepat adalah K, sisipkan L[3] pada L[K] Langkah N  L[N] harus dicari tempatnya yang tepat pada L[1..N] , dengan cara menggeserkan  elemen L[1…N-1] kekanan , bila L[1..N-1] > L[N]. Misalkan posisi yang tepat adalah K, sisipkan L[N] pada L[K] Contoh : tinjau larik dengan N = 6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut menaik

 17 




Akhir dari langkah 5 menghasilkan deretan data didalam larik L yang sudah terurut menaik. Prosedur Pengurutan Sisip Menaik for k := 1 to n do begin temp := l[k]; j := k-1; while (temp <= l[j])and (j>1) do begin l[j+1] := l[j];j := j-1; end; if temp >= l[j] then l[j+1] := temp else begin l[j+1] := l[j]; l[j] := temp; end; end;

QUIZ Lakukanlah pengurutan pada data dibawah ini : 19 12 33 9

17

Dengan metode : (pilih 2 metode pengurutan saja) 1. Bubble Sort (menaik dan menurun ) 2. Max Sort (menaik dan menurun ) 3. Min Sort (menaik dan menurun ) 4. Insertion Sort (menaik dan menurun )

 18 




BABA IV SENARAI BERANTAI (LINKED LIST) IV.1. Defenisi Linked List Adalah struktur berupa rangkaian elemen saling berkait dimana tiap elemen dihubungkan dengan elemen lain dengan menggunakan Pointer. Penggunaan pointer untuk mengacu elemen, mengakibatkan elemen bersebelahan secara logik namun tidak secara fisik dimemori. Senarai Berantai sering disebut juga dengan Linked List. Perhatikan gambar linked list dibawah ini

Terdapat dua simpul yaitu: 1. Start : merupakan variabel penuding list 2. Data/ info : berisikan informasi dari suatu simpul 3. Nextpointer/link/penuding : berisikan alamat untuk menuju ke berikutnya.

simpul

Bagian pointer yang berisikan nilai nil, maka simpul tidak menuding kemanapun. IV.2 Penyajian Linked Llist secara logic didalam memori Contoh 1 : Data Larik Info(K) adalah sebuah karakter tunggal. Kita ingin membentuk Linked list yang elemennya membentuk sebuah string atau untai. String yang dimaksud adalah NO EXIT

Contoh 2: Pada sebuah bangsal Rumah Sakit terdapat 12 tempat tidur. 9 diantaranya telah ditempati pasien. Kita ingin membuat List nama pasien secara alpabetik. Untuk itu kita

 19 




buat sebuah linked List dengan Penuding Next. Varaibel Start kita gunakan untuk menyatakan Lokasi Pasien petama dalam List

Contoh 3 : Diperlukan dua buah Linked List ALGO dan GEOM yang berturut-turut berisi nilai testing mahasiswa Agoritma dan Geometri. Tersimpan dalam larik TEST dan link yang sama. Perhatikan nama dari List sekaligus digunakan sebagai variabel penuding. Disini penuding ALGO berisi nilai 11, yakni lokasi simpul pertama list ALGO, sedangkan penuding GEOM berisi bernilai 5, yakni lokasi simpul pertama dari list GEOM. Mengikuti penuding tersebut dapat dilihat bahwa List ALGO dan GEOM berisi nilainilai

 20 




IV.3. Operasi dasar pada linked list IV.3.1. Penciptaan dan penghancuran simpul Untuk menjelaskan operasi tersebut, kita gunakan deklarasi pointer berikut ini : type simpul = ^ data Data = record Info : char; Berikut : simpul; end; Var elemen : chart; awal,akhir,baru : simpul;

Perintah penciptaan simpul adalah New(nama_simpul), Perintah penghancuran simpul adalah dispose(nama_simpul) IV.3.2 . Penyisipan simpul ke linked list Dalam Penyisipan simpul pada saat simpul awal belum menunjuk ke simpul manapun (linklist belum ada) maka untuk penyisipan simpul di awal, akhir dan tengah diperlakukan sama. 1) Pernyataan New (Baru) adalah pernyataan untuk membuat simpul baru.

2) Pada kondisi tersebut maka simpu baru merupakan simpul awal dan akhir

a) Penyisipan sebagai simpul pertama ( Insert_First) 1) Pointer awal adalah pointer yang menunjuk ke simpul pertama. Pointer akhir adalah pointer yang menunjuk ke simpul terakhir dan simpul yang ditunjuk oleh simpul baru adalah simpul yang akan ditambahkan ke gambar (a). 2) Berikut dari simpul baru dibuat menunjuk ke simpul awal. 3) Pointer awal dibuat sama menunjuk ke simpul baru. Dengan cara ini simpul baru selalu diperlakukan sebagai simpul awal.

 21 




Prosedur insert first Procedure insert_first; Var baru : simpul; begin New(baru); Baru^.info := elemen; If awal = nil then Akhir := baru; Awal := baru; Akhir^.berikut = nil; Else baru^.berikut := awal; Awal := baru;

b) Penyisipan setelah simpul tertentu (insert after linked list) 1) Untuk menambah simpul ditengah senarai kita perlu bantuan sebuah pointer lain, misalnya pointer bantu. Dalam hal ini simpul baru akan diletakkan setelah simpul yang ditunjuk oleh pointer bantu. 2) Secara garis besar operasi penambahan simpul tertentu dapat dijelaskan sebagai berikut : 3) Pertama tentukan dimana simpul baru akan ditambahkan, lalu letakkan pointer bantu sebelum simpul baru. 4) Berikut pada simpul baru dibuat sama menunjuk pada berikut simpul bantu. Berikut pada simpul bantu dibuat menunjuk ke simpul baru

Procedure insert_after (var awal,akhir : simpul; elemen : char) Var baru ,bantu: simpul; begin new(baru);

 22 



Univ. Indo Global Mandiri baru^.info := elemen; If awal = nil then akhir := baru; awal := baru; akhir^.berikut = nil; Else Begin {*mencari lokasi yang sesuai*} Bantu := awal; While elemen >= bantu.^info do Bantu := bantu^.berikut; {*menyisipkan elemen baru *} baru^.berikut := bantu^.berikut; bantu^.berikut := baru; end; end;

c) Penyisipan pada simpul terakhir ( insert last) 1) Dalam hal ini simpul baru akan ditambahkan menjadi simpul terakhir; 2) Berikut pada simpul akhir menunjuk ke simpul baru. 3) Pointer akhir dibuat sama menunjuk ke simpul baru.

Procedure insert_last; var baru : simpul; begin New(baru); Baru^.info := elemen; If awal = nil then begin akhir := baru; awal := baru; akhir^.berikut= nil; end else begin akhir^.berikut:=baru; akhir := baru; akhir^.berikut:=nil; end; end;

 23 




IV.3.3. Penghapusan simpul suatu linked list Dalam penghapusan simpul ada hal yang perlu diperhatikan yaitu simpul yang bisa dihapus adalah simpul yang berada sesudah simpul yang ditunjuk oleh suatu pointer. a) Penghapusan simpul pertama (delete first) Penghapusan di awal dapat dijelaskan sebagai berikut 1) Pointer Hapus kita buat sama dengan pointer Awal. 2) Pointer Awal menunjuk ke simpul setelah Hapus. 3) Dispose (hapus) simpul hapus.

b) Penghapusan simpul Akhir (delete Last Linked List ) Penghapusan di Akhir dapat dijelaskan sebagai berikut 1) Kita letakkan pointer bantu sebelum simpul akhir. 2) Kemudian Pointer Hapus buat sama dengan Pointer Akhir . 3) Pointer Akhir menunjuk ke simpul Bantu 4) Dispose (hapus) simpul hapus.

 24 




c) Penghapusan simpul Tengah (delete after linked list ) Penghapusan di Tengan atau dikhir dapat dijelaskan sebagai berikut 1) Kita letakkan pointer bantu menunjuk ke simpul sebelum simpul yang akan dihapus. Simpul yang akan dihapus kita tunjuk dengn Pointe Hapus. 2) Kemudian Simpul Bantu menunjuk ke simpul setelah simpul Hapus (yang ditunjuk simpul hapus). 3) Dispose (hapus) simpul hapus.

Prosedur untuk menghapus simpel didepan atau diakhir linked list (Delete After and Last LinkedList ) Silakan anda coba sebagai latihan. IV.3.4. Pembacaan Isi Linked List Dapat dilakukan dengan 2 cara a) Membaca Maju Membaca Linked List dari simpul awal sampai simpul akhir Dapat diselesaikan sebagai berikut : 1) Pointer Bantu menunjuk ke simpul Awal 2) Lakukan Kunjungan di setiap simpul sambil membaca isi simpul. 3) Pada saat Pointer Bantu telah membaca isi simpul Akhir, maka proses berhenti.

 25 



Univ. Indo Global Mandiri Procedure baca_maju(awal,akhir, simpu); Var bantu : simpul; begin Bantu= := awal; repeat write (bantu^.info:2); Bantu := bantu^.berikut; Until bantu^.berikut = nil; Writeln; End;

b) Membaca Mundur Membaca Mundur Linked List dilakukan dengan cara merubah arah Pointer, dimana simpul akhir nantinya menjadi simpul Awal dan simpul Awal menjadi Simpul Akhir. Prosedurnya adalah sebagai berikut 1) Pointer Bantu menunjuk ke simpul Awal 2) Pointer Awal menunjuk ke simpul Akhir. 3) Proses ini adalah proses merubah arah pointer. Dengan cara : Pakai Pointer Bantu1 yang juga menunjuk ke Pointer Bantu. 4) Lakukan kunjungan ke simpul-simpul menuju simpul sebelum simpul akhir. 5) Lakukan perubah arah pointer, dengan cara simpul Akhir menunjuk ke simpul bantu1. 6) Rubah pointer Akhir menunjuk ke simpul bantu1 7) Ulangi langkah c sampai simpul Akhir = simpul Bantu. 8) Lakukan Pembacaan dari Simpul Awal sampai simpul Akhir dengan cara pembacaan maju

 26 




Procedure baca_mundur(var awal,akhir : bantu); Var bantu : simpul; begin Bantu= := awal; Awal := akhir; repeat {*Proses membalik Pointer*} Bantu1 := bantu; {*Mencari letak simpul bantu1*} While bantu1^.berikut <> akhir do Bantu1 := bantu1^.berikut; Akhir^.berikut := bantu1; Akhir := bantu1; Until akhir = bantu; Akhir^.berikut := nil; End;

IV.3.5. Senarai Berantai Berkepala (Header Linked List ) Adalah senarai yang memiliki simpul kepala, dimana simpul kepala tersebut bertipe data sama dengan simpul yang lain, tetapi tidak memiliki info didalamnya.

 27 



Univ. Indo Global Mandiri Procedure initial_header(var kepala,ekor: simpul); Begin new(kepala); ekor := kepala; kepala^.berikut := nil; End;

Dengan adannya simpul header maka prosedur dan fungsi yang telah dijelaskan diatas perlu dimodifikasi. Untuk memodifikasi diserahkan kepada anda untuk membuatnya sekaligus sebagai latihan. Tugas 1. Buatlah program Header Linked List untuk operasi penambahan dan penghapusan simpul dan pembacaan simpul. 2. Buatlah program Circular linked List untuk operasi penambahan dan penghapusan dan pembacaan simpul.

 28 




BAB V TUMPUKAN (STACK) V.1. Pengertian Tumpukan(Stack) adalah bentuk khusus dari list linier, penghapusan dan pemasukan elemen hanya dapat dilakukan pada satu posisi yaitu akhir list. Posisi ini disebut posisi puncak (Top) Jelas maka bila stack S = [S1, S2,… St] maka Top (S) = t V.2 Operasi pada Tumpukan (Stack) Ada 2 operasi dasar yang bisa dilakukan pada tumpukan yaitu menyisipkan data (Push) dan mengeluarkan data (Pop). Ilustrasi dibawah ini mengambarkan kerja kedua operator tersebut Push (A,B) 4 3 2 B 1 A Larik A

Push (C,D) 4 D 3 C 2 B 1 A Larik A

Pop 1 data 4 3 2

Pop 2 data D C B

4

D

3 2

1

1

Larik A

Larik A

V.3. Penyajian Tumpukan Ada 2 cara dalam menyajikan tumpukan ke dalam bahasa pemrograman yaitu 1. Penyajian Tumpukan dengan menggunakan Larik (array) Pemakaian larik dalam menyajikan tumpukan memiliki kekurangan banyaknya elemen larik terbatas.

yaitu

Pada suatu saat ukuran tumpukan akan sama dengan ukuran larik. Bila terus ditambahkan akan menyebabkan overflow. Dalam penyajian Tumpukan yang menggunakan tipe data larik dapat digabungkan dengan tipe data terstruktur (record) sehingga larik dapat terdiri dari beberapa field. Deklarasi array-record { Mendefenisiakan Struktur data } Const maxelemen – 225; Type tumpukan = record Isi : array[1..maxelemen] of integer; Atas : 0.. maxelemen; end var t : tumpukan;

Dengan deklarasi diatas elemen tumpukan disimpan dalam dua field, filed pertama untuk menyimpan elemen tumpukan, field yang kedua untuk mencatat posisi ujung tumpukan Implementasi Operasi Push, Implementasi Procedure Push adalah Procedure PUSH; Begin {* dengan kontrol data bertipe boolean *}

 29 



Univ. Indo Global Mandiri If t.atas = maxelemen then {* tumpukan sudah penuh *} Penuh := true; else begin penuh := false; t.atas := t.atas + 1; t.isi[t.atas] := x end; end;

Dengan ditambahnya testing prosedur diatas lebih sempurna untuk mencegah terjadinya overflow Operasi Pop, implementasi prosedur Pop adalah Procedure POP; Begin If t.atas <> 0 then t.atas := t.atas-1; else writeln(„Tumpukan Kosong‟); end;

Operasi Pop ditambahkan kondisi agar prosedur tidak melakukan pengurangan T.atas terus menerus saat data pada tumpukan sudah kosong 2. Penyajian Tumpukan dengan menggunakan Pointer. Kita dapat Menyajikan tumpukan dengan senarai berantai Linier (Linked List). Elemen pertama dalam senarai berantai diperlakukan sebagai elemen teratas dari tumpukan dengan mengacu pada prosedur Push dan Pop Untuk menjelaskan kedua operasi ini, maka terlebih dahulu dideklarasikan tipe data yang diperlukan Type tumpukan = ^elemen; Elemen = record; Info : char; Nerikut : tumpukan; End; Var atas : tumpukan;

Karna senarai berantai kita tentukan sebagai senarai berantai berkepala, maka terlebih dahulu kita mulai dengan initialisasi tumpukan untuk simpul kepala. Procedure initialisasi_tumpukan(var atas : tumpukan) Begin New(atas); Atas^.berikut := nil; end;

Bila senarai berantai hanya berisi simpul kepala berarti tumpukan masih kosong Implementasi Operasi Push Procedure Push(var atas : tumpukan; data : char); Var baru : tumpukan; Begin

 30 



Univ. Indo Global Mandiri {*push data kedalam stack*} New(baru); With baru do Begin If := data; Berikut := nil; If atas^.berikut <> nil then {*Tumpukan sudah ada*} Begin Baru^.berikut := atas^.berikut; Atas^.berikut := baru; End; Else {*tumpukan masih kosong*} Begin Atas^.berikut := baru; Atas := baru; End; End; End;

Implementasi Prosedur Pop Procedure Pop(var atas : tumpukan; data : char); Var baru : tumpukan; Begin If atas^.berikut := nil; {*tumpukan kosong*} Writeln(„Tumpukan Kosong‟); Else Begin Bantu := atas^.berikut; Data := bantu^.info; Atas^.berikut := bantu^.berikut; Dispose(bantu); End; End;

V.4 Aplikasi pada tumpukan Salah satu aplikasi yang menggunakan konsep tumpukan adalah perjodohan tanda kurung (Matching parantheses). Aplikasi ini digunakan untuk merubah notasi Infix menjadi notasi Posfix Algoritma untuk merubah notasi Infix menjadi notasi Posfix Untuk Operand 1) Seluruh operand tidak dimasukkan kedalam stack langsung menjadi output 2) Jika Top Stack adalah simbol “ ) “ maka simbol Push kedalam Stack 3) Jika Top Stack adalah simbol “ ( “ maka Pop seluruh simbol didalam stack sampai bertemu dengan „)‟ pertama Operator Level Top Stack >= simbol 1) Pop elemen Top Stack, lakukan terus sampai elemen Top Stack adalah „(„ atau elemen Top stack < simbol 2) Apabila elemen Top Stack dan simbol adalah „^‟ maka Push simbol kedalam  31 




Stack Level Top Stack < simbol 1) Push simbol kedalam stack dan akhir ekspresi notasi infix diberi tanda „ ; ‟, bila stack membaca tanda „ ; ‟ tersebut maka Pop semua elemen didalam stack Contoh : Notasi Infix : ( ( A + B ) * C / D + E ^ F ) / G , rubahlah menjadi notasi Posfix.

Menghasilkan notasi Posfix : AB+C*D/EF^+G/ Tugas : 1. 2. 3. 4. 5.

Buatlah program tumpukan dengan tipe data array Buatlah program tumpukan dengan tipe data pointer Buatlah program pembalikan kalimat Buatlah program untuk deret Polindrom Buatlah program konversi basis 10 ke basis 2

 32 




BAB VI ANTRIAN (QUEUE) VI.1. Pengertian antrian 

 





Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi depan atau front). Antrian menggunakan prinsip Pertama Masuk Pertama Keluar, First In First Out (FIFO). Antrian banyak dijumpai dalam kehidupan sehari-hari, seprti Mobil-mobil yang mengantri digerbang tol untuk membeli karcis tol; orang-orang yang mengantri di loket untuk membeli karcis film juga membentuk antrian Pada antrian kita tidak menentukan batasan seberapa banyak antrian itu akan berakhir tapi jika kita menggunakan array untuk mengimplementasikan queue/tumpukan kita harus membatasi jumlah antrian yang dapat masuk. Ini dikarenakan array memiliki batasan (upperbound) yang menjadi penghambat jika kita menggunakan antrian. Oleh sebab itu kita dapat mengimplementasikan antrian ini dengan menggunakan link list. Dengan menggunakan link list tepatnya Single Link List maka elemen dapat dimasukkan secara tidak terbatas. Implementasi Link list menngunakan Header Single Link List

VI.2. Notasi Pada Queue Notasi yang dapat digunakan didalam Queue Q adalah : 1. FRONT(Q) menunjukkan posisi terdepan dari suatu antrian. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka FRONT(Q) = A. 2. REAR(Q) menunjukkan posisi terakhir dari suatu antrian. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka REAR(Q) = E. 3. NOEL(Q) menunjukkan jumlah elemen di dalam Antrean Q. Contoh jika kita mempunyai antrian Q = [A,B,C,D,E] maka NOEL(Q) = 5. VI.3. Deklarasi Queue Dalam Link List Pendeklarasian Queue di dalam link list sama seperti kita mendeklarasikan link list. Deklarasi Queue menggunakanHeader Linked List Type Queue = ^Simpul Simpul = Record Info : Char; Next : Queue; End; Var Head, Tail : Queue; Max : Byte;

VI.4. Operasi Dasar Pada Queue Ada 4 operasi dasar yang dapat dilakukan pada struktur data antrian, yaitu:  CREATE(Q) : CREATE(Q) adalah suatu operator yang digunakan untuk membentuk dan menunjukkan suatu antrian hampa.  33 




Contoh : NOEL(CREATE(Q)) = 0 , FRONT(CREATE(Q)) = Tidak Terdefinisi REAR(CREATE(Q)) = Tidak Terdefinisi Berikut ini merupakan procedure CREATE simpul pada Pascal : Procedure CREATE(Var Head, Tail : Queue); Begin New(Head); Head^.Info := 0; Head^.Next := Head; Tail := Head; End;

 ISEMPTY(Q) : ISEMPTY(Q) adalah operator yang menentukan apakah antrian Q hampa atau tidak. ISEMPTY(Q) di terapkan di dalam pascal menjadi sebuah function yang bertipe boolean sehingga hasil dari function ini akan bernilai True jika antrian dalam keadaan kosong / hampa (NOEL(Q) = 0) dan akan bernilai False jika antrian dalam keadaan terisi / tidak kosong (NOEL(Q) > 0). Contoh : ISEMPTY(CREATE(Q)) = True Berikut ini merupakan procedure ISEMPTY simpul pada Pascal : Function ISEMPTY(Head : Queue); Begin ISEMPTY := (Head^.Next = Head); End;

 INSERT(E,Q) : INSERT(E,Q) adalah operator yang digunakan untuk memasukkan elemen E pada antrian Q di posisi depan dari antrian. Hasil dari operator ini adalah antrian yang lebih panjang. Berikut ini merupakan procedure INSERT : Procedure INSERT(Elemen : Byte; Var Head, Tail : Queue); Var Temp : Queue; Begin New(Temp); Temp^.Info := Elemen; Temp^.Next := Head; Tail := Temp; Inc(Head^.Info); End

 REMOVE(Q) : REMOVE(Q) adalah operator yang menghapus elemen bagian depan dari antrian Q. Hasilnya merupakan antrian yang lebih pendek. Pada setiap operasi ini, harga dari NOEL(Q) berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan. Jika NOEL(Q) = 0, maka REMOVE(Q) memberikan suatu kondisi error, yakni suatau UNDERFLOW. Contoh : REMOVE(CREATE(Q)) = UNDERFLOW.  34 




Berikut ini merupakan procedure REMOVE : Procedure REMOVE(Var Head : Queue); Var Temp : Queue; Begin If Not (ISEMPTY(Head)) Then Begin Temp := Head^.Next; Head^.Next := Temp^.Next; Dispose(Temp); Dec(Head^.Info); End; End;

Untuk memahami pengertian antrian sekaligus penerapan operator-operator queue dan notasi-notasinya perhatikan ilustrasi berikut :

 35 




VI.5. Jenis-jenis Antrian Queue memiliki dua variasi yang penggunaannya juga banyak di dalam kehidupan sehari hari atau dalam dunia komputer itu sendiri, diantaranya adalah :  DEQUE : DEQUE adalah antrian dimana elemennya bisa masuk dan keluar lewat kedua ujungnya (berbeda dengan queue yang hany bisa masuk lewat ujung belakang dan keluar lewat ujung depan). Biasanya DEQUE disajikan dengan menggunakan Double link list yang memiliki dua buah pointer yang menunjuk ke posisi sebelumnya dan sesudahnya. Gambar dibawah ini menunjukkan struktur umum dari sebuah DEQUE.

DEQUE juga mempunyai dua jenis variasi yaitu : a. Deque input terbatas : suatu deque yang membatasi pemasukkan elemen hanya pada satu ujung dari list, sementara penghapusan elemen boleh dilakukan pada kedua ujung list. b. Deque output terbatas : merupakan kebalikan dari deque input terbatas yaitu suatu deque yang membatasi penghapusan elemen hanya pada satu ujung dari list, sementara pemasukkan elemen boleh dilakukan pada kedua ujung list.  ANTRIAN BERPRIORITAS Antrian berprioritas adalah suatu queue yang setiap elemennya telah diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah berdasarkan aturan berikut : a. Elemen yang prioritasnya lebih tinggi, diproses lebih dahulu dibandingkan dengan elemen yang prioritas lebih rendah. b. Dua elemen dengan prioritas yang sama, diproses sesuai dengan urutan mereka sewaktu dimasukkan ke dalam priority queue. Salah satu contoh antrian berprioritas ini adalah sistem berbagi waktu (time sharing system), dimana program yang mempunyai prioritas tinggi akan dikerjakan lebih dahulu dan program-program yang berprioritas sama akan membentuk antrian yang biasa. Anda bisa mencoba prosedur antrian beprioritas sebagai latihan.

 36 




BAB VII TREE VII.1. Pohon / tree Pohon (tree) adalah salah satu bentuk graph terhubung yang tidak mengandung sirkuit. Karena merupakan graph terhubung , maka pohon selalu terdapat path atau jalur yang menghubungkan setiap dua simpul dalam pohon. Pohon yang dilengkapi dengan akar atau Root, disebut pohon berakar atau rooded tree. Contoh pohon berakar T adalah sebagai berikut P

Q

T U

R

S V

W

Sifat utama pohon berakar adalah 1. Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-). Pada pohon T, banyaknya simpul adalah n=8, maka banyaknya edge = 7. 2. Mempunyai simpul khusus yang dinamakan root, jika simpul tersebut memiliki derajat keluar =0, dan derajak masuk = 1. Simpul P merupakan root pada pohon T 3. Mempunyai simpul yang dinamakan Daun atau leaf, jika simpul tersebut berderajat keuar = 0 dan derajat masuk = 1. Simpul R, S, V dan W merupakan daun pada pohon T. 4. Setiap simpul mempunyai ketinggian atau level, yang dimulai dari root dengan level = 0, smapai level n pada daun paking bawah. Pada pohon T : simpul P berlevel 0, Q dan T berlevel 1, R, S, dan U berlevel 2, V dan W berlevel 3. 5. Mempunyai ketinggian atau kedalaman atau height, yang merupakan level tertinggi + 1. Pohon T mempunyai ketinggian = 4. 6. Pohon mempunyai weight atau berat atau bobot, yang merupakan banyknya daun pohon. Pohon T mempunyai bobot = 4. VII.2. Pohon binary (binary tree) Sebuah pohon T didefenisikan sebagai pohon biner jika a. T hampa (disebut pohon null) atau b. T mengandung simpul R yang dapat dibedakan dari yang lain dimana akar (root) adalah T, dan simpul sisanya membentuk 2 pohon binar (T1 subpohon kiri dan T2 subpohon kanan dari T) yang saling lepas. a)

T

b)

T

T1

T2  37 




Perhatikan bahwa pendefenisian pohon biner diatas adalah rekursif. Jika T1 tidak hampa, maka simpul akarnya disebut sukesor kiri dari T. Hal serupa untuk akar dari T2 (tidak hampa) disebut sukesor kanan dari T. VII.3. Pohon biner lengkap Setiap simpul dari pohon biner banyak mempunyai dua anak. Dapat dilihat bahwa simpul akar bertingkat = 0, hanya terdiri dari 1 simpul. Anak bertingkat = 1, terdiri paling banyak 2 simpul. Demikian seterusya, simpul dengan tingkat = r paling banyak ada 2n. Dan bila semua simpul yang pada tingkatan terakhir muncul bagian kiri pohon. Dapat dicatat bahwa beberapa buku mendefeniskan pohon biner lengkap harus mengandung semua simpul untuk semua tingkat, pohon biner menurut pendefenisian pohon biner hampir lengkap disebut almost complate binery. Kita dapat menggunakan label pada pohon biner dengan menggunakan bilangan 1,2,3..n dari kiri ke kanan pohon biner. Pemberian label seperti ini memudahkan untuk mengetahui label pada suatu simpul. Untuk mencari posisi sukesor kiri menggunakan rumus 2 x K dari simpul K dan sukesor kanan dari simpul K adalah 2 x K+1, sedangkan predesor dari K menggunaan rumus INT(K/2). Contoh : Tentukan label untuk simpul a, b, c, d pada pohon T dibawah ini .

5

Q

B

A

V

S

W

D

T

S

T

U

Z

G

H

VII.4. Pohon 2 Pohon biner T dikatakan pohon-2 atau pohon biner yang dikembangkan (extended binary tree) bila setiap simpul mempunyai 0 atau 2 anak. Dalam kasus ini simpul dengan dua anak disebut simpul internal sedangkan simpul tanpa anak disebut simpul eksternal. Dalam diagram , sering diadakan perbedaan antara simpul internal dan eksternal . simpul internal menggunakan simbol lingkaran sedangkan simpul eksternal menggunakan simbol bujursangkar Istilah pohon biner yang dikembangkan datang dari pengoperasian berikut. Perhatikan pohon biner dibawah ini dapat dikembangkan menjadi pohon-2

 38 



Univ. Indo Global Mandiri Q

A

V

S

W

D

S

Disini simpul V, W, D, S akan menjadi simpul internal, sementara simpul yang baru akan menjadi simpul eksternal dari pohon-2. Sebuah pemakaian pentng dari pohon-2 adalah untuk menyajikan operasi aritmatika yang mengandung operasi biner. Disini simpul internal menyajkan operand (variabel) sedangkan simpul ekternal menyajikan operator yang bekerja terhadap kedua subpohonnya. Sebagai contoh adalah pohon -2 berikut yang menyajikan ekspresi (a-b) / ( (c + d) * e) /

a

*

b

e

+

c

d

VII.5. Menyajikan pohon umum menjadi pohon biner Bila kita memilik sebuah pohon umum (general tree), maka ada sebuah algoritma yang dapat menyajikan pohon tersebut menjadi pohon biner. Pohon biner selalu terdiri atas paling banyak dua subpohon yakni subpohon kiri dan subpohon kanan, pendefnisian ini berlaku secara rekursif. Tetapi pohon berakar dibawah ini bukanlah pohon biner, karena pohon simpul D mempunyai 3 anak yakni simpul H, I dan J. A

B

E

D

C

F

G

K

H

I

J

L

 39 




Algoritma yang digunakan untuk menyajika pohon umum menjadi pohon biner adalah 1. Tambahkan ruas (edge) baru, menghubingkan 2 simpul bersaudara yang berdampingan , lalu kita hapus ruas dari simpul predesor kesimpul anak bersaudara tersebut, kecuali ruas kesimpul anak paling kiri. A

B

C

E

D

F

G

H

I

J

L

K

2. Lakukan rotasi sebesar 45 derajat searah jarum jam terhadap pohon hasil langkah 1. A B E

C

D

F

G

H I

K J L

VII.6. Traversal pohon biner Struktur poho digunakan untuk menempatkan data guna memudahkan pencarian (search). Pohon juga berguna untuk menyajikan data yang mempunyai struktur logik bercabang sebagai contoh perhatikan pohon biner dibawah ini, menyajikan suatu ekspresi aritmatika : (a+d)*e , ((a+b)*c/d)+e^f)/g dan untai ABDELMTVZNP, adapun bentuk pohon binernya adalah sebagai berikut

 40 



Univ. Indo Global Mandiri * + C

E

+

D

A

B

^ E

/ B

E

G

* +

Gambar a (a+d)*e

M

/

C

F

A

P L

V

N

D T

Z

D

Gambar b ((a+b)*c/d)+e^f)/g

Gambar c ABDELMTVZNP

Gambar 2 menyajikan koleksi elemen data yang disusun sedemikian rupa, yakni bila K adalah label/nama suatu simpul, maka label dari semua simpul subpohon kirinya lebih kecil atau sama dengan K (secara alfabetik), dan label semua simpul subpohon kanannya lebih besar dari K. Traversal pohon adalah mengunjungi setiap simpul pohon tepat hanya satu kali. Ketika melakukan traversal pohon, koleksi simpul dari pohon urut secara linier. Suatu simpul dikatakan dikunjungi bila simpul tersebut kita masukkan kedalam urutan linier tersebut. Tiga kegiatan yang terdapat dalam traversal pohon biner adalah 1. Mengunjungi simpul akar (root) 2. Melakukan traversal subpohon kiri 3. melakukan traversal subpohon kanan. Kita mengenal tiga macam traversal pohon, yang berbeda satu dengan yang lainnya dengan tiga cara pengurutan yaitu traversal pre-order, in-order dan post-order. 1) Traversal Pre-order Pada traversal pre-order yang dilakukan berturut-turut : 1. Kunjungi simpul akar 2. Lakukan traversal subpohon kiri secara pre-order 3. Lakukan traversal subpohon kanan secara pre-order Kalau kita lakukan traversal pre-order terhadap pohon gambar (a), (b) dan (c), maka berturut-turut diperoleh deretan urutan linier : Gambar (a) : + * C D E Gambar (b) : / + * + A B / C D ^ E F G Gambar (c) : M E B A D L P N V T Z 2) Traversal In-order Pada traversal in-order yang dilakukan berturut-turut : 1. Lakukan traversal subpohon kiri secara in-order 2. Kunjungi simpul akar 3. Lakukan traversal subpohon kanan secara in-order maka berturut-turut diperoleh deretan urutan linier : Gambar (a) : E + D * E Gambar (b) : A + B * C / D + E ^ F / G  41 




Gambar (c) : A B D E L M N P T V Z 3) Traversal Post-order Pada traversal Post-order yang dilakukan berturut-turut : 1. Lakukan traversal subpohon kiri secara Post-order 2. Lakukan traversal subpohon kanan secara Post-order 3. Kunjungi simpul akar maka berturut-turut diperoleh deretan urutan linier : Gambar (a) : C D * E + Gambar (b) : A B + C D / * E F ^ + G / Gambar (c) : A D B E L N T Z V P M Terlihat bahwa hasil yang diperoleh leh traversal pohon yang menyajikan ekspresi aritmatika merupakan ekspresi aritmatika secara notasi prefix, infix serta postfix. Hanya disini urutan operasi berdasarkan hirarki operator, tanda kurung yang diberikan tidak terjaga pada traversal in order. Ekpresi ( ( a + b ) * c / d ) + e ^ f ) / g dapat mempunyai arti yang berbeda bila kita berikan tanda kurung. Dalam kasus ini, traversal in post order dapat mempertahankan fungsi tanda kurung yang diberikan secara hirarki operator, juga keunggulan post-order dapat lebih mudah dikomputasi. Keunggulan traversal in-order adalah hasil untai yang dihasilkan urut secara alpabetik. Pre-order sering digunakan dalam Information Management System (IMS) dari IBM, traversal pre-order ekivalen dengan hirarchy sequence order dari IMS. Jadi ketiga metode traversal tersebut sama-sama penting, sehingga perlu kita ketahui denga baik.

 42 




BERITA ACARA PENGAJARAN No Teori 1 Dasar Pengetahuan struktur data 2 Jenis Struktur data 3 Pengurutan data 4 5 6

Linked list, Insert first, after last Delete firrs, after, last, pembacaan maju, pembacaan mundur

7 8 9

Header Linked list, Double linked list Mid Semester Tumpukan (Stack), Matching parantheses Antrian (queue)

10 11 12 13 14 15

Quiz General Tree, Binary Tree, Terminologi pohon binar Pohon 2, Penyajian pohon general menjadi pohon binar Traversal Pohon Binar Reviuw Bahan ajar

Praktikum Ulas balik Prog. Sederhana Penggunaan Array dan record Bubble short, Max sort, min sort, insertion sort Linked list, Insert first, after last Delete firrs, after, last, pembacaan maju, pembacaan mundur Header Linked list, Double linked list Mid Semester Stack dengan array, stack dengan pointer Queue dengan arrau, Queue dengan Pointer, Deque, antrian berprioritas Quiz General tree, binary tree Traversal Pohon Reviuw Bahan ajar

 43 

Univ. Indo Global Mandiri STRUKTUR DATA

Recommend Documents