struktur data

KATA PENGANTAR

Dengan memanjatkan syukur alhamdulillah, segala puji dipanjatkan kehadirat Allah Subhanahu Wa ta'ala. Karena hanya dengan bantuan dan rahmatnya akhirnya buku ini dapat terselesaikan.

Buku berjudul Struktur Data disusun dengan materi yang cukup padat namun berusaha disajikan dalam bahasa yang sederhana dan banyak contoh yang ditampilkan dengan menggunakan bahasa pemrograman Pascal dengan harapan pembaca dapat lebih mudah memahaminya. Mengingat cukup lengkapnya materi yang disajikan dalam buku ini, maka buku ini dapat dijadikan sebagai buku teks maupun buku referensi bagi mahasiswa maupun dosen untuk mata kuliah struktur data.

Penulis menyadari masih banyak kekurangan dalam penulisan buku ini baik dalam penyajian materi, dan tata bahasa. Semoga dihari hari mendatang ada kesempatan untuk membuat buku ini menjadi lebih baik lagi dan lebih berguna bagi pembaca.

Akhirnya penulis berharap agar buku ini benar-benar dapat bermanfaat.

Bulukumba januari 2017

Penulis

DAFTAR ISI

JUDUL ....................................................................................... i

KATA PENGANTAR ................................................................... ii

DAFTAR ISI ................................................................................ iii

BAB 1 : STRUKTUR DATA

A. PENGERTIAN DATA................................................................. 1

B. STRUKTUR DATA..................................................................... 2

BAB 2 : TYPE DATA PADA PASCAL ......................................

A. HIRARKI TYPE DATA PADA PASCAL .................................... 6

1. Type data sederhana ................................................ 6

2. Type data terstruktur .................................................. 9

3. Type data pointer....................................................... 21

BAB 3 : STACK (TUMPUKAN)

A. PENGERTIAN STACK(Tumpukan)........................................... 28

B. Representasi Stack Dengan Array........................... 31

BAB 4 : QUEUE (ANTRIAN)

A. PENGERTIAN QUEUE (ANTRIAN) ........................................ 43

B. Representasi Queue Dengan Array.......................... 45

BAB 5 :LINKED LIST

A. PENGERTIAN LINKED LIST .................................................... 47

B. Deklarasi single linked list ......................................... 49

C. OPERASI PADA SINGLE LINKED LIST .................................. 49

BAB 6 :SORTING

A. PENGERTIAN SORTING ......................................................... 55

B. Exchange Sort .................................................................. 56

C. Selection Sort ................................................................... 60

D. Insertion Sort .................................................................... 61

A. Non comparison sort...................................................... 62

BAB 7 : TREE

A. PENGERTIAN TREE ................................................................ 65

B. TERMINOLOGI TREE .............................................................. 65

C. BinaryTreE ............................................................................ 66

D. Binary Search Tree .......................................................... 68

E. Implementasi BinaryTree ............................................... 71

BAB 8 : POINTER

A. PENGERTIAN POINTER ........................................................ 79

B. Deklarasi variabel bertipe pointer ......................... 81

C. Inisialisasi Pointer ............................................................ 83

DAFTAR PUSTAKA ..............................................................................

riwayat penulis ..............................................................................

BAB 1

STRUKTUR DATA

A. PENGERTIAN DATA

Data adalah representasi dari dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol. pengertian data menyiratkan suatu nilai yang bisa dinyatakan dalam bentuk konstanta atau variabel. Konstanta digunakan untuk menyatakan nilai tetap sedangkan variabel digunakan dalam program untuk menyatakan nilai yang dapat berubah-ubah selang eksekusi berlangsung.Ada empat istilah data yaitu:

a. Tipe data merupakan jenis atau macam data di dalam suatu variabel dalam bahasa pemrograman.

b. Objek data, mengacu pada kumpulan elemen, D (Domain).

c. Representasi data, merupakan suatu mapping dari struktur data ‘d’ ke suatu set ke sruktur data ‘e’ (d = = = e) misal boolean direpresentasikan dalam 0 dan 1.

d. Struktur data, biasanya digunakan untuk mengelompokkan beberapa informasi yang terkait menjadi sebuah kesatuan.

B. STRUKTUR DATA

Struktur data adalah suatu koleksi /kelompok data yang dapat di karakteristikan oleh organisasi serta operasi yang di definisikan terhadapnya. Dalam teknik pemrograman, struktur data berarti tata letak yang berisi kolom-kolom data, baik itu kolom yang tampak oleh user ataupun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh user.

Struktur data meliputi struktur data sederhana, misalnya array dan record dan struktur data majemuk, yang terdiri dari linier ( yang terdiri atas stack, queue serta list dan multilist) dan non linier ( pohon biner dan graf). Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. Struktur data standar yang biasanya digunakan dibidang informatika adalah Array, Struk, list linier (linked list ) dan variasinya, multilist, stack (tumpukan), Queue (antrian), Binary Tree(pohon biner), graph (graf), dan juga pointer.

1. PEMBUATAN STRUKTUR DATA

Untuk membuat struktur data, kita harus melakukan beberapa aktivitas terhadap objek data, yaitu:

Ø Mendeskripsikan kumpulan operasi sah yang diterapkan ke elemen-elemen objek data.

Ø Menunjukkan mekanisme kerja operasi-operasi.

Ø Objek data integer ditambah operasi (+,-,*,/,mod,cell,floor,<,>,) dan operasi-operasi lain yang memanipulasi struktur data.

Ø Struktur data= objek data + {operasi manipulasi}.

Tahap pembuatan struktur data adalah:

Ø Tahap pertama: Spesifikasi

Pendeskripsian /spesifikasi struktur data menyatakan apa yang dapat dilakukan struktur data, bukan cara penerapannya. Pendeskripsian ini melibatkan level logic sehingga dapat digunakan konvensi matematika untuk menyatakan sifat-sifat struktur data yang dikehendaki. Spesifikasi dapat dilakukan dengan dua cara yaitu: spesifikasi secara formal dan spesifikasi secara informal.

Ø Tahap kedua :Implementasi

Implementasi menyatakan cara penerapan struktur data dengan struktur data yang telah ada. Implementasi struktur data adalah proses pendefinisian tipe data abstrak sehingga semua operasi dapat dieksekusi komputer. Implementasi struktur penyimpanan item-item data serta algoritma-algoritma untuk implementasi operasi-operasi sehingga menjamin terpenuhinya karakteristik struktur data, relasi item-item data atau invariant pada struktur data itu.

Ø Tahap ketiga:Pemrograman\

Pemrograman terstruktur adalah penerjemahan menjadi pernyataan di bahasa pemrograman tertentu. Prosesnya terdiri dari:

- Deklarasi yang mendefinisikan objek-objek data dan hubungannya.

- Pembuatan prosedur/rutin untuk operasi-operasi dasar yang menjaga invariant pada struktur data tersebut.

- Sesuai dengan relasi yang didefinisikan di spesifikasi perancangan harus memilih tipe-tipe data yang telah ada untuk merepresentasikan struktur data.

- Struktur data dibangun menggunakan fasilitas pembentukan atau pembuatan struktur data yang disediakan bahasa seperti array, record, dan sebagainya atau yang telah dibuat seperti stack, queue atau himpunan menggunakan linked list.

- Pembuatan struktur data adalah pembentukan tipe data lengkap yang mempunyai empat property berikut:

a) Nama: identifier tipe data

b) Domain: domain atau himpunan semesta nilai di tipe data.

c) Konstanta (penyebutan anggota-anggotanya): cara penyebutan anggota-anggota tipe data.

d) Operasi-operasi terhadap tipe data itu (operator): daftar operasi terhadap anggota tipe data sehingga kelakuan objek data sesuai spesifikasi.

BAB 2

Type Data Pada Pascal

A. Hirarki Type Data Pada Pascal

Pascal telah menyediakan beberapa tipe data yang sudah siap dipakai. Pada saat mendeklarasikan sebuah variabel secara otomatis harus mendeklarasikan tipe data yang dapat ditampung oleh variabel tersebut. Tipe data dalam pascal dibagi menjadi tiga bagian yaitu:

a. Tipe data sederhana

Tipe data sederhana merupakan tipe data yang paling kecil, yang hanya melibatkan satu item data, misalnya tipe data integer, string, real, Boolean, dan sebagainya. Kita dapat juga mendefinisikan sendiri tipe data ini. Tipe data yang didefinisikan sendiri tersebut diistilahkan enumerated data type

(1) Tipe bilangan bulat

Tipe data ini digunakan untuk menyimpan bilangan bulat. Macam-macam tipe bilangan bulat dalam Pascal dapat dilihat pada Tabel 1.1. Tabel 1.1. Macam-macam tipe bilangan bulat

Type jangkauan ukuran

Shortint -128....127 8 bit

Integer -32768 … 32767 16 bit

Longint -2147483648 … 2147483647 32 bit

Byte 0 … 255 8 bit

Word 0 … 65535 16 bit

Untuk memberi nilai pada tipe bilangan bulat dapat menggunakan basis decimal maupun heksadesimal yang ditandai dengan tanda $ Contoh :

Var

x, y: integer;

begin

x := 16; { dengan decimal }

y := $0A; {dengan hexadecimal }

end.

(2) Tipe boolean

Tipe data ini hanya dapat bernilai benar dan salah. Tipe Boolean ukurannya 1 byte.

Contoh

Var B1: boolean;

Begin

b1 := true;

b1 := false;

end.

(3) Tipe karakter

Tipe data ini digunakan untuk menyimpan data alfanumeris seperti ‘A’, ‘Z’, ‘@’, dsb.. Tipe data char ukurannya 1 byte. Contoh :

Var

ch: char;

begin

ch := ‘A’;

ch := #65 { sama artinya dengan ch := ‘A’}

ch := chr(65); { sama artinya dengan ch := ‘A’}

end.

(4) Tipesubajangkauan

Tipe data ini memungkinkan Anda mendeklarasikan tipe yang berada pada jangkauan tertentu. Tipe ini hamper sama dengan tipe bilangan bulat, bedanya Anda bebas menentukan jangkauan dari tipe ini. Contoh :

Type

Bulan = 1 .. 12;

Var

Januari : Bulan;

Begin

Januari := 1;

End.

(5) Tipe data ini memungkinkan Anda memberi nama pada beberapa nilai tertentu. Contoh :

Type

TipeHari=(Minggu,Senin,Selasa,Rabu,Kamis,Jumat, Sabtu);

Var

hari: TipeHari;

begin

hari := Minggu;

hari := Senin;

end.

(6) Tipe real

Tipe data ini digunakan untuk menyimpan bilangan real. Macam-macamnya tipe bilangan real dalam Pascal dapat dilihat pada Tabel 1.2.

Tipe jangkauan digit penting ukuran

Real 2.9*10^-39 … 1.7*10³⁸ 11-12 8 byte

Single 1.5*10^-45 … 3.4*10³⁸7-84 byte

Double 5.0*10^-324 … 1.7*10³⁰⁸15-16 8 byte

Extended 3.4*10^-4932 … 1.1*10⁴⁹³²19-20 10 byte

Comp -2⁶³+1 … 2⁶³-1 19-20 8 byte

Contoh :

Var

x, y: real;

begin

x := 123.45; {menuliskan nilai dengan tanda titik}

y := 1.2345E+2 { menuliskan nilai dengan eksponen}

end.

(4) Type string

Tipe data ini digunakan untuk menyimpan data yang berupa untaian karakter. Contoh :

Var

kalimat: string;

begin kalimat := ‘ISTAKPRIND’;

end.

b. Tipe data terstruktur

Tipe data terstruktur merupakan tipe data yang menampung beberapa item data. Bentuk dari tipe data ini dapat berupa array (terdiri dari item-item yang memiliki tipe data yang sama) ataupun record (terdiri dari item-item yang boleh memiliki tipe data yang berbeda).

1. Type larik (array)

Array adalah suatu tipe data terstruktur yang terdapat dalam memori yang terdiri dari sejumlah elemen (tempat) yang mempunyai tipe data yang sama dan merupakan gabungan dari beberapa variabel sejenis serta memiliki jumlah komponen yang jumlahnya tetap.

Gambar 2.1

Array ( biasa juga disebut larik) merupakan tipe data terstruktur yang berguna untuk menyimpan sejumlah data yang bersifat sama. Bagian yang menyusun array biasa dinamakan elemen array. Masing-masing elemen dapat diakses tersendiri, melalui indeks array, seperti terlihat pada gambar 1.1.

a) Array berdimensi satu

Array berdimensi satu dapat digambarkan sebagai kotak panjang yang terdiri atas beberapa kotak kecil seperti terlihat pada Gambar 1.1. Dalam gambar tersebut, array memiliki 5 buah elemen. Untuk membentuk array seperti pada gambar 1.1, diperlukan pendeklarasian sebagai berikut:

const

maks_elemen = 5;

var

x :array [1 .. maks_elemen]ofreal;

Pada contoh ini, X dapat menampung 5 buah elemen bertipe Real. Yang menjadi kata-kata kunci pendeklarasian array adalah kata cadang ARRAY. Banyaknya komponen dalam suatu larik ditunjukkan oleh suatu indeks yang disebut dengan tipe indeks (index type). Tiap-tiap komponen larik dapat diakses dengan menunjukkan nilai indeksnya.

Bentuk umum :

Var nama : array[index] of tipe

dengan : var, array, of kata cadangan yang harus ada.

nama nama larik yang akandideklarasikan. Index batas yang akan ada pada larik yang

akandideklarasikan(cacah elemnya).

tipe tipe larik.

Array dapat bertipe data sederhana seperti byte, word, integer, real, bolean, char, string dan tipe data scalar atau subrange.

Contoh :

Var

x:array[1..10] of integer;

b :integer;

begin

b := 3;

x[1] :=39;

x[2] := 42;

x[3] := x[1] + 50;

x[4] := x[2] + b;

x[5] := x[3] + x[4];

end.

b) Array berdimensi dua

Sejauh ini struktur yang telah dibahas merupakan array yang bekerja dengan daftar linear yang dikases dengan satu subskrip, yang disebut array satu dimensi. Array satu dimensi sebagai item-item kolom tunggal yang semua itemnya bertipe sama. Kadang-kadang kita perlu membuat struktur yang lebih kompleks yang mempunyai dua dimensi yaitu berupa baris dan kolom.

Bentuk umum :

Var nama : array[index1,index2] of tipe

dengan :

var, array, of kata cadangan yang harus ada.

Nama nama larik yang akan dideklarasikan.

Index1 batas pertama yang akan ada pada larik yg akan

dideklarasikan(cacah elemen pada baris).

Index2 batas ke dua yang akan ada pada larik yg akan

dideklarasikan(cacah elemen pada kolom).

Tipe tipe larik.

Sebagai contoh, andaikata kita akan menyimpan 3 tes untuk 100 mahasiswa kita dapat membuat tabel sebagai berikut :

Subskrip pertama mewakili jumlah mahasiswa dan subskrip kedua mewakili jumlah tes. Jika nama arraynya TestMhs, maka TestMhs[1,2] berarti mengandung nilai untuk mahasiswa pertama, tes yang ke dua. TestMhs[3,1] mengandung nilai untuk mahasiswa ke tiga test yang pertama. Struktur ini dapat dideklarasikan :

Const

MakBaris = 100;

MakKolom =3;

Type

TipeArray=array[1..MakBaris,1..MakKolom] of Real;

Var

A :TipeArray;

N, M, indekBaris,indekKolom :integer;

Atau dengan menentukan maksimum baris dan kolom dituliskan dalam type array seperti contoh berikut :

Type

TipeArray=array[1..100,1..10] of Real;

Var

A :TipeArray;

N, M, indekBaris,indekKolom :integer;

Dua variabel N dan M mewakili jumlah baris dan jumlah kolom yang digunakan untuk menyimpan data.Dengan segmen program ini, kita dapat menulis prosedur untuk memuat data ke dalam array. Pemakai pertama kali memasukkan nilai untuk N dan M dan kemudian memasukkan dalam setiap posisi pada array tersebut, pada saat yang berbeda. Contoh Prosedur tersebut adalah :

Begin

Write(‘Masukkan jumlah Baris dan Kolom’);

Readln(N,M); {prosedur memasukkannilai tesurut baris}

for indek Baris :=1 to N do begin

for indekKolom := 1 to M do

begin

write(‘Masukkan nilaitesmahasiswake ‘,indekBaris,’Nilai

1Teske-‘,indekkolom);

readln(A[indekBaris,indekKolom]);

end;

c) Array Dengan Tiga Atau Lebih Dimensi

Bentuk umum :

Var nama : array[index1,index2,...,indexn] of tipe

dengan :

var, array, of kata cadangan yang harus ada.

nama nama larik yang akan dideklarasikan.

Index1 batas pertama yang akan ada pada larik yg

akan dideklarasikan

Index2 batas ke dua yang akan ada pada larik yg akan

dideklarasikan

Indexn batas ke n yang akan ada pada larik yg akan

dideklarasikan

tipe tipe larik.

Contoh :

Menghitung rata-rata nilai tes beasiswa untuk semua peserta di semua gelombang, jika diketahui Gel : menunjukkan gelombang tes yang terdiri dari 2 , Sn : jumlah peserta tes beasiswa tiap gelombang dan

Nt :Nilai tes yang terdiri dari 3 materi tes.

Var

Nilai :array[1..2,1..100,1..3] of Real;

Gel, Sn,jmlpeserta,Nt,N:integer;

Rata,ratanil,totnil,total :real;

Begin

Total := 0; N:=0;

For Gel:= 1 to2dobegin Write(΄Jumlah peserta

tes beasiswa gel ke-΄,Gel,΄adalah :΄); readln(jmlpeserta);

For Sn := 1 tojmlpeserta do Begin

Totnil := 0;

For Nt := 1 to 3 do

Write(΄Nilai Teske-΄,Nt,΄adalah :΄);readln(Nilai[Gel,Sn,Nt]);

Totnil := Totnil + Nilai[Gel,Sn,Nt];

End;

Total := Total + Totnil/3;

End;

N := N +jmlpeserta;

End;

Rata :=Total/N;

End.

2. Tipe rekaman

Seperti pada larik, rekaman (record) adalah kumpulan data. Perbedaan antara larik dengan rekaman adalah bahwa dalam larik semua elemennya harus bertipe sama, tetapi dalam rekaman setiap elemen dapat mempunyai tipe data yang berbeda satu sama lainnya. Untuk mendeklarasikan rekaman selalu diawali dengan nama record tanda sama dengan (=) dan kata kunci record serta diakhiri oleh kata kunci end. Field-field dari record tersebut diletakkan diantara kata kunci record dan end.

Bentuk umum :

type

pengenal1 = record

medan1 : tipe1; medan2 : tipe2;

medann : tipen;

end;

dimana :

pengenal : pengenal yang menunjukkan tipe data yang akan

dideklarasikan.

medan : nama medan yang akan digunakan.

tipe : sembarang tipe data yang telah dideklarasikan

sebelumnya.

Contoh :

Type

data=record

Nim :string[10];

Nama : string;

IPK :real;

End;

Var

Mhs1 :data;

Mhs2:array[1..3] ofdata;

Begin

Mhs1.nim :=΄1110710001΄;

Mhs1.nama :=΄MALECITA΄;

Mhs1.IPK := 3.89;

Mhs2[1].nim :=΄1110710005΄;

Mhs2[1].nama :=΄NOHAN΄;

Mhs2[1].IPK :=3.75;

Mhs2[2].nim := ΄1110710015΄;

Mhs2[2].nama := ΄SALSA΄;

Mhs2[2].IPK :=3.80;

End.

3. Tipe himpunan

Set merupakan tipe data terstruktur yang terdiri dari elemen yang disebut Anggota set. Anggota set ini tidak memiliki urutan dan tidak boleh ada dua anggota set yang sama. Sebuah set dalam Pascal hanya dapat memuat maksimal 255 anggota dan hanya mempunyai satu tipe.

Bentuk Umum :

Type

<namatipe> = set of <tipedata>;

Contoh :

Type

Karakter = set of char;

Tanggal = set of 1..31;

Hari = set of (Senin, Selasa, Rabu, Kamis, Jumat,Sabtu,

Minggu);

Var

Kar : karakter;

tgl : tanggal;

smg : hari;

nilai-nilai dalam suatu set dapat dituliskan dengan beberapa cara, yaitu disebutkan satu persatu(enumerasi), atau dituliskan dalam rentang tertentu.

a) Notasiset enumerasi

Elemen-elemen yang terdapat dalam set dinyatakan satu persatu

Contoh:

Angka := [1,2,3,4,5];

Huruf := [ ‘A’, ‘B’, ‘C’];

b) Notasiset rentang

Elemen-elemen yang dinyatakan secara rentang berdasarkan tipe dasar set tersebut.

Contoh :

Angka := [1..6];

Huruf := [ ‘A’.. ‘C’,’G’...’Z’];

Pascal menyediakan operator hubungan yang dapat digunakan untuk mengetahui (tes) keanggotaan himpunan. Contoh operator In yang berarti termasuk sebagai anggota. ‘a’ in [‘a’,’b’,’c’] adalah true.

Contoh :

( X >= 1 ) and ( X <= 10 )

hubungan ini true(benar) ketika x dalam jangkauan 1..10 sehingga dapat ditulis:

X in [1..10];

Tipe ini digunakan untuk menyimpan kumpulan nilai yang bertipe sama.

c. Type data pointer

1. Pengertian pointer

Tipe data pointer digunakan untuk menunjuk pada alamat memory suatu data yang lain. Jadi tipe data pointer pada dasarnya tidak menyimpan nilai data secara langsung,melainkan hanya menyimpan alamat dimana data berada. Dengan melihat sifat-sifat perubah statis, bisa kita katakan bahwa banyaknya data yang bisa diolah adalah terbatas. Sebagai contoh, misalnya kita mempunyai perubah yang kita deklarasikan sebagai : var Tabel : array[1..100, 1..50] of integer;

Cara pengaksesan data bisa diilustrasikan seperti gambar di bawah ini :

Gambar 1.2. Ilustrasi Perubah Statis

Gambar 2.2. Ilustrasi Perubah Dinamis

Pada gambar 1.2. perubah A adalah perubah statis. Dalam hal ini 1000 adalah nilai data yang sesungguhnya dan disimpan pada perubah (lokasi) A. Pada gambar 1.3. perubah A adalah perubah dinamis. Nilai perubah ini, misalnya adalah 10. Nilai ini bukan nilai data yang sesungguhnya, tetapi lokasi dimana data yang sesungguhnya berada. Jadi dalam hal ini nilai data yang sesungguhnya tersimpan pada lokasi 10. Dari ilustrasi di atas bisa dilihat bahwa nilai perubah dinamis akan digunakan untuk menunjuk ke lokasi lain yang berisi data sesungguhnya yang akan diproses. Karena alasan inilah perubah dinamis lebih dikenal dengan sebutan pointer yang artinya menunjuk ke sesuatu. Dalamperubah dinamis, nilai data yang ditunjuk oleh suatu pointer biasanya disebut sebagai simpul/node.

2. Deklarasi pointer

Pendeklarasian pointer hampir sama dengan pendeklarasian variabel biasa, bedanya hanya dengan menambahkan tanda ^ di depan tipe pointer. Bentuk umum deklarasi pointer adalah :

Type

pengenal = ^simpul;

simpul = tipe;

dengan

pengenal : nama pengenal yang menyatakan data

bertipe pointer

simpul : nama simpul

tipe : tipe data dari simpul

Tanda ^ di depan nama simpul harus ditulis seperti apa adanya dan menunjukkan bahwa pengenal adalah suatu tipe data pointer. Tipe data simpul yang dinyatakan dalam tipe bisa berupa sembarang tipe data, misalnya char, integer, atau real.

Sebagai contoh :

Type

Bulat = ^integer;

Dalam contoh di atas Bulat menunjukkan tipe data baru, yaitu bertipe pointer. Dalam hal ini pointer tersebut akan menunjuk ke suatu data yang bertipe integer. Dengan deklarasi diatas, maka kita bisa mempunyai deklarasi perubah, misalnya:

var

X, K : Bulat;

Yang menunjukkan bahwa X dan K adalah perubah bertipe pointer yang hanya bisa mengakses data yang bertipe integer. Dalam kebanyakan program-program terapan, biasanya terdapat sekumpulan data yang dikumpulkan dalam sebuah rekaman (record), sehingga anda akan banyak menjumpai tipe data pointer yang elemennya (data yang ditunjuk) adalah sebuah rekaman. Perhatikan contoh berikut :

type

Pmhs = ^Data;

Data = record

Nim : Str[10];

Nama : Str[30];

IPK : real;

end;

Dengan deklarasi tipe data seperti di atas, kita bisa mendeklarasikan perubah, misalnya :

var

P1,P2 : Pmhs;

A,B,C : String;

Pada contoh di atas, P1 dan P2 masing-masing bertipe pointer; A,

B dan C perubah statis yang bertipe string

Pada saat program dikompilasi, perubah P1 dan P2 akan menempati lokasi tertentu dalam memori. Kedua perubah ini masing-masing belum menunjuk ke suatu simpul. Pointer yang belum menunjuk ke suatu simpul lainnya dinyatakan sebagainil. Untuk mengalokasikan simpul dalam memori, statemen yang digunakan adalah statemennew, yang mempunyai bentuk umum

new (perubah);

dengan perubah adalah nama perubah yang bertipe pointer.

Sebagai contoh, dengan deklarasi perubah seperti di atas dan statemen:

new (P1);

new (P2);

contoh

Var

P1 : ^integer;

P2 : ^char;

3. Operasi pointer

Secara umum ada dua operasi dasar yang bisa kita lakukan menggunakan data yang bertipe pointer. ada 2 operasi dasar yang bisa dilakukan menggunakan data yang bertipe pointer yang mempunyai deklarasi yang sama :

a) Mengkopi pointer

mengakibatkan sebuah simpul akan ditunjuk oleh lebih dari sebuah pointer. Jika didalam statemen pemberian tanda ^ tidak ditulis, operasinya disebut operasi mengkopi pointer. Konsekuensinya simpul yang semula ditunjukkan oleh pointer akanterlepas

Gambar 2.3

b) Mengkopi isi simpul

mengakibatkan dua atau lebih simpul yang ditunjuk oleh pointer yang berbeda mempunyai isi yang sama. Jika statemen pemberian tanda ^ ditulis, operasinya merupakan mengkopi isi simpul pointer, konsekuensinya isi dua simpul atau lebih akan sama.

$Description: C:\Users\rahman\AppData\Local\Microsoft\Windows\INetCache\Content.Word\sswwwww.jpg$

Gambar 2.4

c) Menghapus pointer

Di atas telah dijelaskan bahwa pointer yang telah dialokasikan (dibentuk) bisa didealokasikan (dihapus) kembali pada saat program dieksekusi. Setelah suatu pointer dihapus, maka lokasi yang semula ditempati oleh simpul yang ditunjuk oleh pointer tersebut akan bebas, sehingga bisa digunakan oleh perubah lain.

Statemen untuk menghapus pointer adalah dispose, yang mempunyai bentuk umum :

dispose (perubah)

dengan perubah adalah sembarang perubah yang bertipe pointer. Sebagai contoh, dengan menggunakan deklarasi :

type

Pmhs = ^Data;

Data = record

Nim : Str[10];

Nama : Str[30];

IPK : real;

end;

var

Mhs,Mhs1 : Pmhs;

Kemudian kita membentuk simpul baru, yaiu :

new (Mhs);

Mhs1 := Mhs;

Pada suatu saat, simpul yang ditunjuk oleh pointer Mhs1 tidak digunakan lagi, maka bisa dihapus dengan menggunakan statemen

: dispose (Mhs1)

Demikian penjelasan tentang perubah dinamis yang lebih dikenal dengan sebutan pointer..

BAB 3

STACK (Tumpukan)

A. PENGERTIAN STACK(Tumpukan)

Stack adalah suatu kumpulan data yang seolah-olah ada data yang diletakkan di atas data yang lain. Di dalam stack, kita dapat menambahkan/menyisipkan dan mengambil/menghapus data melalui ujung yang sama yang disebut sebagai puncak stack (top of stack). Stack mempunyai sifat LIFO (Last In First Out), artinya data yang terakhir masuk adalah data yang pertama keluar. Contoh dalam kehidupan sehari-hari adalah tumpukan piring di sebuah restoran yang tumpukannya dapat ditambah pada bagian paling atas dan jika mengambilnya pun dari bagian paling atas pula. Lihat gambar 4.1

Gambar 3.1. Contoh stack

Ada 2 operasi paling dasar dari stack yang dapat dilakukan, yaitu :

1. Operasipush yaitu operasi menambahkan elemen pada urutan terakhir (paling atas). Dengan syarat tumpukan tidak dalam kondisi penuh, jika penuh penuh maka terjadi overflow

Gambar 3.2. Operasi Push (Sumber :

www.algonicox.blogspot.com )

2. Operasipop yaitu operasi mengambil sebuah elemen data pada urutan terakhir dan menghapus elemen tersebut dari stack. Dengan syarat tumpukan tidak dalam kondisi kosong, jika kososng akanterjadi underflow

Gambar 3.3. Operasi POP (Sumber :

www.algonicox.blogspot.com )

Contoh : ada sekumpulan perintah stack yaitu push(5), push(7), pop, push(3), pop. Jika dijalankan, maka yang akan terjadi adalah :

TOP 0 TOP 5 TOP 7 TOP 5 Top 3 Top 5 Top 0

kosong 5 5 kosong

push(5) push(7) pop push(3) pop pop

Selain operasi dasar stack (push dan stack), ada lagi operasi lain yang dapat terjadi dalam stack yaitu :

1. Proses deklarasi yaitu proses pendeklarasian stack.

2. Proses IsEmpty yaitu proses pemeriksaan apakah stack dalam keadaan kosong.

3. Proses IsFull yaitu proses pemeriksaan apakah stack telah penuh.

4. Proses inisialisasi yaitu proses pembuatan stack kosong, biasanya dengan pemberian nilai untuk top. Representasi stack dalam pemrograman, dapat dilakukan dengan 2 cara yaitu :

1. Representasi stack dengan array

2. Representasi stack dengan single linked list

B. Representasi Stack Dengan Array

Bentuk penyajian stack menggunakan tipe data array sebenarnya kurang tepat karena banyaknya elemen dalam array bersifat statis, sedangkan jumlah elemen stack sangat bervariasi atau dinamis. Meskipun demikian, array dapat digunakan untuk penyajian stack, tetapi dengan anggapan bahwa banyaknya elemen maksimal suatu stack tidak melebihi batas maksimum banyaknya array. Pada suatu saat ukuran stack akan sama dengan ukuran array. Bila diteruskan menambah data, maka akan terjadi overflow. Oleh karena itu, perlu ditambahkan data untuk mencatat posisi ujung stack. Ada dua jenis bentuk stack menggunakan array, yaitu single stack dan double stack.

1. Single Stack

Single stack dapat dianalogikan dengan sebuah wadah yang diisi benda melalui satu jalan keluar dan masuk.

Gambar 3.4. Ilustrasi Single Stack

Representasi stack dengan menggunakan array dengan maksimal data 9 dapat dilihat pada gambar 4.6

28
45
27
70
60
50
15
25
30
5

MAX 9

Gambar 3.5. Representasi stack menggunakan array

Dari gambar 4.6. terlihat bahwa indek array ke-0 digunakan untuk menyimpan posisi Top Of Stack (TOS). Karena isi dari array ke-0 adalah 5 maka untuk TOS = 5, sehingga isi stack sebenarnya adalah : 60, 50, 15, 25, 30. Yaitu posisi array ke-1 sampai dengan ke-5. Apabila dilakukan operasi Push(stack,IB), maka proses yang terjadi adalah :

1. Tambahkan nilai TOP

2. masukkan nilai IB pada posisi TOP

Sebagai contoh apabila dilakukan operasi: Push(stack,20), maka

1. TOP = 6, posisi 6 dari 70 berubah 20, dan

2. Isi stack menjadi : 20, 60, 50, 15, 25, 30

Apabila dilakukan operasi Pop(stack,IB), maka proses yang terjadi adalah

1. Ambil elemen pada posisi TOP

2. Turunkan nilai TOP

Sebagai contoh apabila dilakukan operasi: Pop(stack,X), maka

1. Maka posisi 6 diambil dan

2. TOP = 5

Operasi-operasi stack pada single stack secara lengkap adalah sebagai berikut

a) Pendeklarasian stack

Proses pendeklarasian stack adalah proses pembuatan struktur stack dalam memori. Suatu stack memiliki beberapa bagian yaitu

a. top yang menunjuk posisi data terakhir (TOP)

b. elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array.

c. maks_elemen yaitu variable yang menunjuk maksimal banyaknya elemen dalam stack.

Dalam bahasa Pascal, pendeklarasiannya adalah :

Const

Maks_elemen := 100;

Type

tstack = record

Elemen : array[1..maks_elemen] of integer;

Top : integer;

Maks : integer;

End;

b) Inisialisasi

Inisialisasi stack adalah proses pembuatan suatu stack kosong. Proses inisialisasi untuk stack yang menggunakan array adalah dengan mengisi nilai field top dengan 0 (nol) Implementasinya dalam bahasa Pascal adalah sebagai berikut.

Procedureinit(varstack: tstack);

Begin

Stack.top= 0;

Stack.maks =maks_elemen;

End;

c) Operasi IsEmpty

Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses pop tidak bisa dilakukan. Operasi ini dilakukan hanya dengan memeriksa field top. Jika top bernilai 0, maka berarti stack dalam keadaan empty (kosong) yang akan menghasilkan nilai true (1) pada function IsEmpty dan jika tidak berarti stack mempunyai isi dan menghasilkan nilai false (0) pada function IsEmpty

FunctionIsEmpty(stack: tstack) : Boolean;

Begin

Ifstack.top = 0 then

IsEmpty := true;

Else

IsEmpty := false;

End;

d) Operasi IsFull

Operasi ini berguna untuk memeriksa keadaan stack apakah sudah penuh atau belum. Operasi ini akan menghasilkan nilai true (1) jika stack telah penuh dan akan menghasilkan nilai false (0) jika stack masih bisa ditambah. Operasi ini akan memberikan nilai true (1) jika field top sama dengan field maks_elemen Implementasinya Function IsFull dalam bahasa Pascal adalah sebagai berikut

FunctionIsFull(stack: tstack) : Boolean;

Begin

Ifstack.top = maks_elemen then

IsFull := true;

Else

IsFull := false;

End;

e) Operasi Push

Operasi push adalah operasi dasar dari stack. Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah : a. Periksa apakah stack penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan. b. Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru. c. Untuk lebih jelas, perhatikan lagi gambar 4.4. mengenai representasistack dengan array. d. Implementasi operasi Push dalam bahasa Pascal adalah sebagai berikut

Procedurepush(varstack: tstack; baru : integer)

Begin

if(IsFull(stack)= false) then

begin

stack.top :=stack.top + 1;

stack.elemen[stack.top]:= baru;

end else

writeln(‘StackFull.PushGagal.’);

end;

f) Operasi Pop

Operasi pop adalah salah satu operasi paling dasar dari stack. Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus elemen tersebut sehingga posisi top akan berpindah. Operasi ini biasanya menghasilkan nilai sesuai data yang ada di top seperti diperlihatkan pada Gambar 4.6. Langkah operasi pop pada stack yang menggunakan array adalah

a. terlebih dahulu memeriksa apakah stack dalam keadaan keadaan kosong, jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top, kemudian simpan dalam variable baru dengan namadata, kemudian posisi top dikurangi 1,

b. kemudian nilai pada variabledata dikembalikan ke function.

c. Implementasi operasi POP dalam bahasa Pascal adalah sebagai berikut

Procedurepop(varstack: tstack; var data : integer);

Begin

if(IsEmpty(stack)= false) then

begin

data=stack.elemen[stack.top];

stack.top :=stack.top-1;

else

writeln(‘StackEmpty. Pop Gagal.’);

end;

2. Single Stack

Double stack merupakan bentuk pengembangan single stack dengan maksud untuk menghemat memori. Dalam double stack terdapat dua stack dalam satu array. Stack 1 bergerak ke kanan dan stack 2 bergerak ke kiri. Double stack dikatakan penuh apabila puncak stack 1 bertemu dengan puncak stack 2.

1 2

Stack 1 stack 2

1 max

Gambar 4.7. Ilustrasi double stack

Operasi-operasi stack pada single stack secara lengkap adalah sebagai berikut :

1) Pendeklarasian stack

a. Top1 yang menunjuk posisi data terakhir (top1)

b. Top2 yang menunjuk posisi data terakhir (top2)

c. elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array.

d. maks_elemen yaitu variable yang menunjuk maksimal banyaknya elemen dalam stack. Dalam bahasa Pascal, pendeklarasiannya adalah sebagai berikut

Const

Maks_elemen := 100;

Type

tstack = record

Elemen : array[1..maks_elemen] of integer;

Top1 : integer;

Top2 : integer

End;

Var

Stack : tstack;

2) Inisialisasi

Inisialisasi double stack adalah proses pembuatan suatu double stack kosong. Proses inisialisasi untuk double stack yang menggunakan array adalah dengan mengisi nilai field top1 dengan 0 (nol) dan mengisi nilai field top2 dengan nilai maksimum ditambah 1. Implementasi proses inisialisasi dalam bahasa Pascal adalah sebagai berikut

Procedureinit(varstack: tstack);

Begin

Stack.top1= 0;

Stack.top2 =maks_elemen + 1;

End;

3) Operasi IsEmpty

Operasi ini digunakan untuk memeriksa apakah double stack dalam keadaan kosong. Operasi ini penting dilakukan dalam proses pop. Ketika suatu double stack dalam keadaan kosong, maka proses pop tidak bisa dilakukan. Operasi ini dilakukan hanya dengan memeriksa field top1 dan top2. Jika top1 bernilai 0 dan top2 bernilai maks_elemen ditambah 1, maka berarti stack dalam keadaan empty (kosong) yang akan menghasilkan nilai true (1) dan jika tidak berarti stack mempunyai isi dan menghasilkan nilai false (0). Implementasi operasi IsEmpty dalam bahasa Pascal adalah sebagai berikut.

FunctionIsEmpty(stack: tstack; nostack: integer) : Boolean;

Begin

Case nostack of

1 : If (stack.top1 = 0) then

IsEmpty := true;

Else

IsEmpty := false;

2 : if (stack.top2 = maks_elemen + 1) then

IsEmpty := true;

Else

IsEmpty := false;

Else

Writeln(‘Nomorstacksalah’):

End;

4) Operasi IsFull

Implementasinya dalam bahasa Pascal adalah :

FunctionIsFull(stack: tstack) : Boolean;

Begin

Ifstack.top1 >=stack.top2 then

IsFull := true;

Else IsFull := false;

End;

5) Operasi Push

Operasi push pada stack yang menggunakan single linked list adalah sama dengan proses tambahawal pada operasi linked list. Langkah-langkahnya adalah :

a. Periksa apakah memori penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.

b. Proses push-nya sendiri adalah dengan cara mengalokasikan suatu elemen linked list (disebut variable baru), kemudian periksa jika stack dalam keadaan kosong maka pointer yang menunjuk ke awal stack diisi dengan pointer baru, dan jika dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru. Tetapi jika pointer penunjuk stack sudah menunjuk ke suatu data, maka sambungkan field pointer link (penunjuk ke data sebelumnya) dari pointer baru ke pointer penunjuk posisi akhir stack (top) dan kemudian pindahkah pointer penunjuk posisi akhir stack ke pointer baru.

Untuk lebih jelas perhatikan kembali gambar 4.8 mengenai representasi stack dengan linked linst.

Implementasinya dalam bahasa Pascal adalah :

Procedurepush(stack: pstack; isi : integer)

var

Baru : pstack;

Begin

if(isfull(stack)=false) ten

begin new(baru);

baru^.link=Nil;

baru^.data=isi;

if(isempty(stack)=true) then

stack=baru;

else

begin

baru^.link :=stack;

stack:= baru;

end;

end else

wrieln(‘Memory Full.PushGagal’);

end;

6) Operasi Pop

Langkah operasi pop pada stack yang menggunakan single linked list adalah sama dengan proses hapus awal pada operasi single linked list. Prosesnya adalah :

a. Periksa apakah.stack kosong (isempty), jika kosong maka proses pop tidak bisa dilakukan. Jika stack tidak kosong maka proses pop dijalankan.

b. Proses pop-nya sendiri adalah mengambil elemen yang ditunjuk oleh pointer stack kemudian simpan dalam variable data. Kemudian buat variable pointer bantu yang diisi dengan pointer penunjuk stack yang nantinya akan dihapus dari memori. Kemudian pointer penunjuk stack dipindahkan ke posisi yang ditunjuk oleh field pointer bawah dari variable bantu.

Implementasi operasi ini dalam bahasa Pascal adalah :

Procedure pop(stack: tstack; var elemen : integer);

var

bantu : PStack;

begin

f(isempty(stack)= false) then

begin

elemen=stack^.data;

bantu=stack;

stack=bantu^.link;

dispose(bantu);

end else

writeln(‘Stack dalam kondisi kosong’);

end.

BAB 4

QUEUE(ANTRIAN)

A. PENGERTIAN QUEUE (ANTRIAN)

secara harfiah queue dapat diartikan sebagai antrian. Queue merupakan kumpulan data dengan penambahan data hanya melalui satu sisi, yaitu belakang (tail) dan penghapusan data hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO(First In First Out), yaitu data yang pertama masuk akan keluar terlebih dahulu dan data yang terakhir masuk akan keluar terakhir. Berikut ini adalah gambaran struktur data queue.

Keluar awal akhir masuk

Gambar 4.1. Ilustrasi queue

Elemen yang pertama kali masuk ke dalam queue disebut elemen depan (front/head of queue), sedangkan elemen yang terakhir kali masuk ke queue disebut elemen belakang (rear/tail of queue). Perbedaan antara stack dan queue terdapat pada aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas tersebut akan dihapus paling awal, sifat demikian dikenal dengan LIFO. Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung, menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan. Sifat yang demikian dikenal dengan FIFO.

Gambar 4.2. Contoh model antian

Contoh antrian dalam kehidupan sehari– hari :

a. Mobil yang antri membeli karcis di pintu jalan tol akan membentuk antrian

b. Pembelian tiket pada loket tiket

c. Antrian pasien

Gambar 4.3. Contoh model antian pasien

(sumber :http://bopax.wordpress.com/2011/02/14/terjadinya-antrian/)

B. Representasi Queue Dengan Array

Disebut juga queue dengan model fisik, yaitu bagian depan queue selalu menempati posisi pertama array.

depaN

Kelua A B C D E F masuk

Belakang

Gambar 4.4. Contoh antrian dengan 6 elemen

Gambar 5.4. di atas menunjukkan contoh penyajian antrian menggunakan larik. Antrian di atas berisi 6 elemen, yaitu A,B,C,D,E dan F. Elemen A terletak di bagian depan antrian dan elemen F terletak dibagian belakang antrian. Dengan demikian, jika ada elemen yang baru masuk, maka ia akan diletakkan disebelah kanan F (pada gambar diatas). Jika ada elemen yang akan dihapus, maka A akan dihapus lebih dahulu. Gambar 5.5. menunjukkan antrian di atas setelah berturut-turut dimasukkan G dan H.

Depan

Keluar A B C D E F G H masuk

Belakang

Untuk menyajikan antrian, menggunakan larik, maka kita membutuhkan deklarasi antrian, misalnya, sebagai berikut :

Const nmax = 100;

Type typeinfo = …………. { bisa tipe data apa saja }

Typearray = array[1..nmax] of typeinfo

Typequeue = record

Elemen : typearray

Depan, Belakang : integer;

End;

Var

Antrian :

typequeue;

BAB 5

LINKED LIST

A. PENGERTIAN LINKED LIST

Linked list adalah koleksi dari obyek-obyek homogen dengan sifat setiap obyek (kecuali terakhir) punya penerus dan setiap obyek (kecuali yang pertama) punya pendahulu. Masing-masing data dalam Linked list disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. Kumpulan komponen obyekobyek ini disusun secara berurutan dengan bantuan pointer.

Linked list dikembangkan tahun 1955-1956 oleh Allen Newell, Cliff Shaw & Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa information processing language (IPL). IPL adalah pengembangan dari program AI dengan bahasa pemrogaman COMMIT. Linked list merupakan struktur data dinamis yang paling sederhana yang berlawanan dengan array, yang merupakan struktur statis.

Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori. Masing-masing linked list terbagi menjadi 2 bagian :

1. Medan informasi Berisi informasi yang akan disimpan dan diolah.

2. Medan penyambung

Berisi alamat simpul berikutnya

Gambar 5.1

Operasi pada Linked list

1. Menambah simpul Bisa dipecahkan berdasarkan posisi simpul yaitu simpul baru :

 ditambahkan dibelakang simpul terakhir

 selalu diletakkan sebagai simpul pertama

 menyisip diantara dua simpul yang sudah ada.

2. Menghapus simpul Dapat dilakukan dengan menghapus didepan, dibelakang atau ditengah dan harus berada sesudah simpul yang ditunjuk oleh suatu pointer.

3. Mencari Informasi pada suatu Linked list Sama dengan membaca isi simpul hanya ditambah dengan test untuk menentukan ada tidaknya data yang dicari

4. Mencetak Simpul Dengan cara membaca secara maju dan secara mundur

B. Deklarasi single linked list

Manipulasi Linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama dalam Linked list (dalam hal ini adalah head/kepala).

Bentuk umum :

Type typeinfo = ……;

simpul = ^typenode;

Typenode = record

Info : typeinfo;

Next : simpul;

End;

Var elemen : typeinfo;

Awal, akhir, baru : simpul;

Dimana :

nfo : sebuah tipe terdefinisi yang menyimpan informasi sebuah

simpul

Next : alamat dari elemen berikutnya (suksesor)

C. OPERASI PADA SINGLE LINKED LIST

Ada sejumlah operasi yang bisa kita lakukan pada sebuah Linked list, yaitu operasi menambah simpul dan menghapus simpul pada sebuahLinked list.

1. Menambah simpul Operasi menambah simpul bisa dipecah berdasarkan posisi simpul baru yang akan disisipkan, yaitu simpul baru selalu ditambahkan dibelakang simpul terakhir, simpul baru selalu diletakkan sebagai simpul pertama, dan simpul baru menyisip diantara dua simpul yang ada.

a) Menambah simpul di belakang

adalah proses penambahan data baru dimana data baru disimpan di posisi terakhir. Setelah proses penambahan selesai, maka variable akhir akan menunjuk ke data baru tersebut. Ada 2 kondisi yang harus diperiksa yaitu kondisi penambahan akhir pada linked list yang masih kosong dan kondisi penambahan akhir pada linked list yang sudah mempunyai elemen.

Ø Menambah simpul dibelakang ketika linked list masih kosong Fungsi menambah simpul di belakang, apabila linked list masih kosong. Langkahlangkahnya:

- membuat simpul baru kemudian diisi info baru.

- simpul paling akhir dihubungkan ke simpul baru.

- penunjuk pointer akhir dan pointer awal diarahkan ke simpul baru.

Gambar 5.2

Ø Implementasi dalam program

Dari langkah-langkah di atas, maka dapat diimplementasikan ke dalam bahasa Pascal

b) Menambah simpul di awal

Penambahan elemen di posisi awal adalah menambahkan data baru pada posisi awal, sehingga data baru tersebut akan menjadi awal. Ada 2 kondisi yang harus diperhatikan ketika kita melakukan proses penambahan elemen baru di awal yaitu kondisi Linked list sedang kosong dan kondisi Linked list sudah mempunyai elemen.

(1) Penambahan elemen di awal ketika linked list masih

Kosong. Fungsi menambah simpul diawal, apabila Linked list masih kosong. Langkah-langkahnya:

Ø membuat simpul baru, kemudian diisi info baru.

Ø simpul baru dihubungkan ke simpul awal.

Ø penunjuk pointer awal diarahkan ke simpul baru.

Gambar 5.3 Ilustrasi penambahan simpul di awal pada saat linked list masih kosong

(2) Penambahan di awal ketika linked list sudah mempunyai

elemen. Fungsi menambah simpul di belakang, langkah-langkahnya:

Ø membuat simpul baru kemudian diisi info baru.

Ø Kemudian variable/pointer awal dipindahkan ke pointer baru.

Ø Kemudian variable/pointer awal dipindahkan ke pointer baru.

Ø Implementasi dalam program

TypePoint = ^Data ;

Data = record

Info : integer ;

next : point;

End;

Var Elemen : integer ;

Awal, Akhir : point ;

ProcedureTambah_Depan(varAwal,Akhir: point;Elemen:integer);

VarBaru : point;

Begin

New(Baru);

Baru^.Info :=Elemen;

If Awal= NIL then

Akhir:= Baru

Else

Baru^.next:= Awal;

Awal := Baru;

End;

BAB 5

LINKED LIST

A. PENGERTIAN LINKED LIST

Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori. Masing-masing linked list terbagi menjadi 2 bagian :

1. Medan informasi Berisi informasi yang akan disimpan dan diolah.

2. Medan penyambung

Berisi alamat simpul berikutnya

Gambar 5.1

Operasi pada Linked list

1. Menambah simpul Bisa dipecahkan berdasarkan posisi simpul yaitu simpul baru :

 ditambahkan dibelakang simpul terakhir

 selalu diletakkan sebagai simpul pertama

 menyisip diantara dua simpul yang sudah ada.

2. Menghapus simpul Dapat dilakukan dengan menghapus didepan, dibelakang atau ditengah dan harus berada sesudah simpul yang ditunjuk oleh suatu pointer.

3. Mencari Informasi pada suatu Linked list Sama dengan membaca isi simpul hanya ditambah dengan test untuk menentukan ada tidaknya data yang dicari

4. Mencetak Simpul Dengan cara membaca secara maju dan secara mundur

B. DEKLARASI SINGLE LINKED LIST

Manipulasi Linked list tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama dalam Linked list (dalam hal ini adalah head/kepala).

Bentuk umum :

Type typeinfo = ……;

simpul = ^typenode;

Typenode = record

Info : typeinfo;

Next : simpul;

End;

Var elemen : typeinfo;

Awal, akhir, baru : simpul;

Dimana :

nfo : sebuah tipe terdefinisi yang menyimpan informasi sebuah

simpul

Next : alamat dari elemen berikutnya (suksesor)

C. OPERASI PADA SINGLE LINKED LIST

Ada sejumlah operasi yang bisa kita lakukan pada sebuah Linked list, yaitu operasi menambah simpul dan menghapus simpul pada sebuahLinked list.

a) Menambah simpul di belakang

Ø Menambah simpul dibelakang ketika linked list masih kosong Fungsi menambah simpul di belakang, apabila linked list masih kosong. Langkahlangkahnya:

- membuat simpul baru kemudian diisi info baru.

- simpul paling akhir dihubungkan ke simpul baru.

- penunjuk pointer akhir dan pointer awal diarahkan ke simpul baru.

Gambar 5.2

Ø Implementasi dalam program

Dari langkah-langkah di atas, maka dapat diimplementasikan ke dalam bahasa Pascal

b) Menambah simpul di awal

(1) Penambahan elemen di awal ketika linked list masih

Kosong. Fungsi menambah simpul diawal, apabila Linked list masih kosong. Langkah-langkahnya:

Ø membuat simpul baru, kemudian diisi info baru.

Ø simpul baru dihubungkan ke simpul awal.

Ø penunjuk pointer awal diarahkan ke simpul baru.

Gambar 5.3 Ilustrasi penambahan simpul di awal pada saat linked list masih kosong

(2) Penambahan di awal ketika linked list sudah mempunyai

elemen. Fungsi menambah simpul di belakang, langkah-langkahnya:

Ø membuat simpul baru kemudian diisi info baru.

Ø Kemudian variable/pointer awal dipindahkan ke pointer baru.

Ø Kemudian variable/pointer awal dipindahkan ke pointer baru.

Ø Implementasi dalam program

TypePoint = ^Data ;

Data = record

Info : integer ;

next : point;

End;

Var Elemen : integer ;

Awal, Akhir : point ;

ProcedureTambah_Depan(varAwal,Akhir: point;Elemen:integer);

VarBaru : point;

Begin

New(Baru);

Baru^.Info :=Elemen;

If Awal= NIL then

Akhir:= Baru

Else

Baru^.next:= Awal;

Awal := Baru;

End;

BAB 6

SORTING

A. PENGERTIAN SORTING

Sorting adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu ataupun secara acak, sehingga menjadi tersusun secara teratur menurut aturan tertentu. Pada umumnya ada 2 macam pengurutan, yaitu: pengurutan secara ascending (urut naik) dan pengurutan secara descending (urut turun).

Banyak klasifikasi yang dapat digunakan untuk mengklasifikasikan algoritma-algoritma pengurutan, misalnya secara kompleksitas, teknik yang dilakukan, stabilitas, memori yang digunakan, rekursif atau tidak ataupun proses yang terjadi. Secara umum, metode pengurutan dapat dikelompokkan dalam 2 kategori yaitu

1. Metode pengurutan sederhana (elementary sorting methods) Metode pengurutan sederhana meliputi bubble sort, selection sort dan insertion sort.

2. Pengurutan lanjut (advanced sorting methods)

Metode pengurutan lanjut diantaranya shell sort, quick sort, merge sort dan radix sort. Algoritma-algoritma ini tentu saja akan mempunyai efek yang berbeda dalam setiap prosesnya

B. EXCHANGE SORT

Dalam prosesnya, algoritma-algoritma pengurutan yang diklasifikasikan sebagai exchange sort melakukan pembandingan antar data, dan melakukan pertukaran apabila urutan yang didapat belum sesuai. Contohnya adalah : Bubble sort, dan Quicksort

1. Bubble sort

Keuntungan dari algoritma sorting ini adalah karena paling mudah, dan dapat dijalankan dengan cukup cepat dan efisien untuk mengurutkan list yang urutannya sudah hampir benar. Namun algoritma ini paling lambat dan termasuk sangat tidak efisien untuk dilakukan dibandingkan dengan algoritma yang lain apalagi pengurutan dilakukan terhadap elemen yang banyak jumlahnya. Untuk itu biasanya bubble sort hanya digunakan untuk mengenalkan konsep dari algoritma sorting.

a) Konsep algoritma bubble sort

Ø Algoritma dimulai dari elemen paling awal.

Ø 2 buah elemen pertama dari list dibandingkan. Jika elemen pertama lebih besar dari elemen kedua atau sebaliknya (urut secara ascending atau descending),dilakukan pertukaran.

Ø Langkah 2 dan 3 dilakukan lagi terhadap elemen kedua dan ketiga, seterusnya sampai ke ujung elemen

Ø Bila sudah sampai ke ujung dilakukan lagi ke awal sampai tidak ada terjadi lagi pertukaran elemen.

Ø Bila tidak ada pertukaran elemen lagi, maka list elemen sudah terurut.

Ø Setiap pasangan data: x[j] dengan x[j+1], untuk semua j=1,...,n-1 harus memenuhi

keterurutan, yaitu untuk pengurutan:

o Ascending : x[j] < x[j+1]

o Descending : x[j] > x[j+1]

b) Procedure bubble sort

Type

Type array = array[1..100] of integer;

Var

Adatukar : boolean;

i, j,temp : integer;

Procedurebuble_sort(var x:typearray; n : integer);

begin

adatukar := true;

i := 1;

while ( i<n ) and (adatukar) do

begin

J:=1;

adatukar :=false;

while j <= (n-i) do

begin

If x[j] > x[j+1]then

begin

adatukar:=true;

temp :=x[j];

x[j] :=x[j+1];

x[j+1]:=temp;

end;

j:=j+1;

end

i:=i+1;

end;

2. Quick sort

Algoritma Quicksort bersifat divide and conquer. Quick sort banyak digunakan untuk proses sorting,karena:

· Merupakan proses sorting yang umum digunakan

· Mudah untuk diimplementasikan

· Algoritma ini merupakan algoritma pencarian yang sangat cepat (saat ini tercepat).

Kelemahan dari algoritma quicksort adalah apabila algoritma ini digunakan untuk mengurutkan elemen-elemen yang hanya ada sedikit atau sudah hampir terurut, karena jika menggunakan algoritma ini justru akan melakukan perulangan yang tidak berguna dan lama. Selain itu algoritma ini mempunyai algoritma dan program yang cukup kompleks.

a) Konsep algoritma quick sort

Pertama-tama deret dibagi menjadi dua bagian, misal, semua elemen pada bagian b (bagian pertama) mempunyai kurang dari atau sama dengan semua elemen pada bagaian c (bagian kedua). Kemudian kedua bagian tersebut dilakukan proses sorting dengan rekursif secara terpisah dengan prosedur yang sama(coquer). Kemudian gabungkan lagi kedua bagian terpisah tersebut

Gambar 6.1. Ilustrasi algoritma quick Sort

· Select : Pertamakita pilih elemen yang ditengah sebagai pivot, misalkan X.

· Partition : kemudian semua elemen tersebut disusun dengan menempatkan X pada posisi j sedemikian rupa sehingga elemen disebelah kiri1 lebih < X dan elemen sebelah kanan >X.

· Rekursif : kemudian proses diulang untuk bagian kiri dan kanan elemen X dengan cara yg sama dengan langkah 1 sampai kondisi terurut

b) Procedure quick sort

Procedurequicksort(data,L,R: integer);

Var i,j,x : integer;

Begin

x = data[(L+R) div 2];

i = L;

j = R;

while (i< =j) do

begin

while (data[I] < x ) do inc( I );

while ( data[J] > x ) do dec( J );

If( I < = J ) then

tukar(data[I],data[j]);

inc( I );

Dec( J );

End;

If ( L < J ) then quicksort(data,L, J );

If ( I < R ) then quicksort(data,i, R );

End;

C. SELECTION SORT

Selection Sort merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.

Kelebihan dan kekurangan Selection Sort:

Ø Kompleksitas selection sort relatif lebih kecil

Ø Mudah menggabungkannya kembali, tetapi sulit membagi masalah

Ø Membutuhkan meteode tambahan

1. Konsep algoritma selection sort

Untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[1]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[2]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. Tehnik pengurutan dgn cara pemilihan elemen atau proses kerja dgn memilih elemen data terkecil untuk kemudian dibandingkan & ditukarkan dgn elemen pada data awal, dan seterusnya sampai dengan seluruh elemen sehingga akan menghasilkan pola data yg telah disort.

2. Procedure selection sort

Procedureselection_sort(var x: typearray;n: integer);

Var I,J,mindex: integer;

Begin

I := 1;

While I < n do

Begin

Mindex := I;

J := J+1;

While J <= n do

Begin

If x[ J ] < x[ mindex ] then

Mindex := J;

J := J+1;

End;

If mindex <> I then

Tukar(x[ I ], x[ mindex ]);

I := I+1;

End;

D. INSERTION SORT

Algoritma pengurutan yang diklasifikasikan kedalam kategori ini mencari tempat yang tepat untuk suatu elemen data yang telah diketahui kedalam subkumpulan data yang telah terurut, kemudian melakukan penyisipan (insertion) data di tempat yang tepat tersebut.

1. Konsep algoritma insertion sort

Prinsip dasar Insertion adalah secara berulang-ulang menyisipkan/ memasukan setiap elemen ke dalam posisinya/tempatnya yang benar. Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang

2. Procedure Insertion sort

Proceduresisip_langsung (var A : larik; N : integer);

Var i, j : integer; T : real;

Begin

For I := 2 to N do begin

T := A[ i ];

J := I–1;

A[0] := T;

While T < A[J] do Begin

A[J+1] := A[J];

Dec (J);

End;

A[J+1] := T;

End;

E. NON COMPARISON SORT

Non comparison sort adalah algoritma pengurutan di mana dalam prosesnya tidak melakukan pembandingan antar data. Secara umum proses yang dilakukan dalam algoritma ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan dalam tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai dengan kebutuhan, kemudian subkategori-subkategori tersebut digabungkan kembali, yang dilakukan dengan algoritma sederhana concatenation.

Salah satu algoritma sorting non comparison sort adalah algoritma Radix sort.

1. Konsep algoritma radix sort

Ide dasar dari algoritma Radix sort ini adalah mengkategorikan data-data menjadi sub kumpulan subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix lainnya.

2. Proceduer algoritma radixsort

Implementasi dari algoritma pada Gambar 2.25 dapat direalisasikan dengan menggunakan queue sebagai representasi tiap kategori radix untuk pengkategorian. Array A adalah array input, dan array B adalah array A yang sudah terurut.

ProcedureRadixSort (A : TArray;varB :TArray; d : byte);

var

KatRadix :array[0..9]ofQueue;

i, x, ctr : integer;

pembagi : longword;

begin

{---mengkopi A ke B---}

for i:=1 tondo

B[i] := A[i];

pembagi := 1;

for x:=1 toddo begin

{---inisialisasi KatRadix---}

For i:=0 to 9 do

InitQueue (KatRadix[i]);

{---dikategorikan---}

fori:=1 to n do

Enqueue (KatRadix [(B[i]divpembagi)mod 10], B[i]);

B[i] := 0;

{---dikonkat---}

ctr := 0;

fori:=0to9 do begin

while(NOTIsQueueEmpty (KatRadix[i]))do begin

ctr := ctr +1;

B[ctr]:=DeQueue (KatRadix [i]);

end;

pembagi := pembagi *10;

end;

BAB 7

TREE

A. PENGERTIAN TREE

Tree adalah kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tidak berhubungan satu sama lain (disebut subTree).

Sebelumnya kita sudah mengenal struktur data list, yang berupa obyek-obyek yang saling terkait. Dalam list, satu obyek hanya terkait dengan satu obyek berikutnya melalui sebuah pointer. List dapat dikembangkan menjadi struktur data yang lebih kompleks, misalnya dengan menambah jumlah pointer dalam obyek. Misal dengan penambahan satu pointer lagi. Artinya bahwa jika masing-masing obyek memiliki dua pointer, ada dua obyek lain yang ditunjuknya. Struktur yang demikian dikenal sebagai binary Trees atau dikenal juga sebagai Tree Node. Oleh karena itu Tree merupakan salah satu bentuk struktur data tidak linier yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen

B. TERMINOLOGI TREE

Predecessor : Node yang berada diatas node tertentu.

Successor : Node yang berada dibawah node tertentu Ancestor : Seluruh node yang terletak sebelum node

ertentu dan terletak pada jalur yang sama.

Descendant : Seluruh node yang terletak sesudah node

tertentu

dan terletak pada jalur yang sama

Parent : predecessor satu level diatas suatu node

Child : successor satu level dibawah suatu node

Sibling : node-node yang memiliki parent yang sama

dengan suatu node

SubTree : bagian dari Tree yang berupa suatu node

beserta descendant nya dan memiliki semua

karakteristik dari Tree tersebut

Size : banyaknya node dalam suatu Tree Height :

banyaknya tingkatan / level dalam suatu Tree

Root : Node khusus dalam Tree yang tidak punya

predecessor

Leaf : node-node dalam Tree yang tak memiliki

successor

Degree : banyaknya child yang dimiliki suau node

C. BinaryTree

Binary Tree adalah Tree dengan syarat bahwa tiap node hanya boleh memiliki dua subTree dan kedua subTree tersebut harus terpisah. Sehingga setiap node hanya boleh memiliki paling banyak 2 child

1. Jenis binaryTree

a) Full binary Tree

Binary Tree yang tiap nodenya (kecuali leaf) memiliki 2 child dan tiap subTree harus mempunyai panjang path yang sama

Gambar 7.1. Contoh full binary Tree

b) Complete binaryTree

Mirip dengan Full Binary Tree, namun tiap sub tree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child

Gambar 7.2. Contoh Complete binary Tree

c) Skewed binary Tree

Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child

Gambar 7.3. Contoh skewed binary Tree

D. Binary Search Tree

Binary Tree dengan sifat bahwa semua left child harus lebih kecil dari pada right child dan parent. Juga semua right child harus lebih besar dari left child serta parentnya. Hal ini digunakan untuk menutupi kelemahan dari binary Tree biasa, sehingga memudahkan proses searching.

Gambar 7.4 Sifat binary search Tree

1. Operasi pada binary search Tree

a) Operasi Insert

Operasi insert dilakukan setelah ditemukan lokasi yang tepat yaitu bila node baru > parent maka diposisikan sebagairight child dan bila node baru < parent diposisikan sebagai left child Penyisipan sebuah elemen baru dalam binary search tree, elemen tersebut pasti akan menjadi leaf

Sebagai contoh apabila kita akan menyisipkan nilai 5 pada pohon biner pada gambar 6.8b, maka langkah penyisipannya adalah sebabagi berikut

a) pertama data yang akan disisipkan akan dibandingkan dengan node pada root yang bernilai 6 apakah data < dari nilai root,

b) karena benar maka selanjutnya data yang akan disisipkan akan dibandingkan dengan data yang merupakan left child dari root

c) selanjutnya ulangi lagi langkah tersebut sampai data menjadi leaf

Gambar 7.5 Operasi insert pada binary search Tree

b) Operasi Delete

Delete dalam binary search tree mempengaruhi struktur dari tree tersebut. Sehingga apabila node yang dihapus mempunyai child maka posisi node yang dihapus digantikan dengan leaf yang berada pada posisi terakhir

Gambar 7.7

2. Notasi Prefix, Infix, dan Postfix

Ø Prefix

Sebuah binary tree apabila dikunjungi secara preorder akan menghasilkan notasi prefix Bila diketahui pohon biner seperti terlihat pada gambar 6.16. maka hasil Notasi Prefix adalah : ^ - * + A B C –D E + F G

Ø InFix

Sebuah binary Tree apabila dikunjungi secara inorder akan menghasilkan notasi Infix Bila diketahui pohon biner seperti terlihat pada gambar 6.16. maka hasil notasi Infix adalah : ((A + B) * C –(D – E)) ^ (F + G)

Ø PostFix

Sebuah binary Tree apabila dikunjungi secara postorder akan menghasilkan notasiPostfix Bila diketahui pohon biner seperti terlihat pada gambar 6.16. maka hasil notasi Postfix adalah : A B + C * D E - - F G + ^

E. Implementasi BinaryTree

Implementasi dalam pemrograman ini akan digunakan untuk pohon biner saja. Sebagai contoh data yang digunakan untuk implementasi binary Tree adalah data bertipe data char. Masingmasing obyek atau node dalam binary Tree memiliki dua pointer yang biasa disebut left dan right. Pointer left dan right sebuah obyek dapat bernilai nil (tidak menunjuk ke obyek lain) atau dapat menunjuk ke obyek lain. Node atau obyek yang menunjuk ke node lain disebut sebagai parent, sedangkan node yang ditunjuk disebut sebagai child. Tidak semua struktur data berantai yang tersusun atas Tree adalah binary Tree. Bisa disebut binary Tree jika ada satu node dalam Tree yang tidak memiliki parent (disebut root) dan setiap node dalam Tree mempunyai satu parent. Dengan demikian tidak mungkin terjadi loop dalam binary Tree, dengan kata lain tidak mungkin mengikuti rantai pointer dan kemudian kembali lagi ke node yang sama

Gambar 7.8. Implementasi Binary Tree

Pada gambar ilustrasi binary Tree di atas, terdapat node yang tidak menunjuk ke obyek manapun. Node ini disebut sebagai leaf . Ciri-ciri leaf adalah kedua pointernya bernilai nil , karena tidak menunjuk ke node manapun.

1. DeklarasiTree

Tree tersusun atas node-node, sehingga perlu kita deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita namaiNode. Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi node ke dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki susunan berikut ini:

kiri

data

kanan

pointer int pointer

Berikut ini adalah contoh deklarasi obyek dalam binaryTree (dalam Pascal):

Type tipedata = integer;

Tree = ^node;

Node = record;

data : tipedata;

kiri, kanan : Tree;

End;

Variabel data digunakan untuk menyimpan nilai angka node tersebut, sedangkan kiri dan kanan, bertipe pointer, masing-masing mewakili vektor yang akan menunjuk ke node anak kiri dan kanan.

2. Inisialisasi Tree

Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum memilikinode sama sekali, sehingga masih kosong.

Pohon := Nil;

Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita buat, dengan nama Pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka pointer Pohon ditunjukkan ke Nil.

3. Menambahkan Node Pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner: Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon. Jika pohon tidak kosong, maka dimulai darinode akar, dilakukan proses pengecekan berikut:

a) Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

b) Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:

Procedure sisip_node(d : typedata; var pohon : Tree);

Begin

If pohon = nil then

Begin

New(pohon);

Pohon^.data := d;

Pohon^.kiri := nil;

Pohon^.kanan := nil;

End

else if pohon^.isi < d then sisip_node(d,Pohon^.kanan)

else if pohon^.isi > d then sisip_node(d,Pohon^.kiri);

end;

4. Membaca dan Menampilkan Node PadaTree

Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif

a) Kunjungan Pre-Order

Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

(1) Cetak isi (data) node yang sedang dikunjungi

(2) Kunjungi kiri node tersebut,

Ø Jika kiri bukan kosong (tidak NIL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

Ø Jika kiri kosong (NIL), lanjut ke langkah ketiga.

(3) Kunjungi kanan node tersebut,

Ø Jika kanan bukan kosong (tidak NIL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

Ø Jika kanan kosong (NIL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

Implementasi dalam bahasa Pascal :

Procedure Preorder(Pohon : Tree);

Begin

If pohon <> nil then begin

Write(pohon^.isi);

Preorder(pohon^.kiri);

Preorder(pohon^.kanan);

End;

b) Kunjungan In-Order

(1) Kunjungi kiri node tersebut,

Ø Jika kiri bukan kosong (tidak NIL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

Ø Jika kiri kosong (NIL), lanjut ke langkah kedua.

(2) Cetak isi (data) node yang sedang dikunjungi

(3) Kunjungi kanan node tersebut,

Ø Jika kanan bukan kosong (tidak NIL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

Ø Jika kanan kosong (NIL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

Implementasi dalam bahasa Pascal :

Procedure Inorder(Pohon : Tree);

Begin

If pohon <> nil then begin

Inorder(pohon^.kiri);

Write(pohon^.isi);

Inorder(pohon^.kanan);

End;

c) Kunjungan Post-Order.

(1) Kunjungi kiri node tersebut,

Ø Jika kiri bukan kosong (tidak NIL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

Ø Jika kiri kosong (NIL), lanjut ke langkah kedua.

(2) Kunjungi kanan node tersebut,

Ø Jika kanan bukan kosong (tidak NIL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

Ø Jika kanan kosong (NIL), lanjut ke langkah ketiga.

(3) Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya. Implementasi dalam bahasa Pascal :

Procedure Postorder(Pohon : Tree);

Begin

If pohon <> nil then

Begin

Postorder(pohon^.kiri);

Postorder(pohon^.kanan);

Write(pohon^.isi);

End;

struktur data

Jumat, 08 Desember 2017

struktur data sistem komputer