1

MODUL PRAKTIKUM

STRUKTUR DATA

Tim Penyusun:

Dosen Teknik Informatika

JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS PALANGKARAYA

2016

2

TATA TERTIB DAN TATA LAKSANA PRAKTIKUM

TATA TERTIB

1. Praktikan WAJIB mengikuti semua modul praktikum.

2. Praktikan hanya boleh tidak mengikuti praktikum 1 (satu) kali DENGAN

ATAU TANPA SURAT IZIN dari jumlah pertemuan praktikum.

3. Praktikan yang berhalangan mengikuti praktikum, diwajibkan melaporkan

ke dosen praktikum untuk menentukan jadwal praktikum sebagai

pengganti jadwal yang berhalangan.

4. Praktikan yang lebih dari 1 (satu) kali tidak mengikuti praktikum, tidak

diperbolehkan untuk mengikuti praktikum untuk modul-modul praktikum

selanjutnya dan NILAI AKHIR PRAKTIKUM adalah NOL.

5. Praktikan diberikan toleransi waktu keterlambatan selama 15 menit dan

tidak ada penambahan waktu praktikum.

6. Tidak diperbolehkan saling bekerja sama.

7. Dilarang menggunakan kaos oblong dan sendal selama praktikum. Bagi

yang melanggar poin ini, tidak diperbolehkan mengikuti praktikum.

TATA LAKSANA :

1. Sebelum praktikum di mulai, setiap praktikum wajib mengumpulkan

LAPORAN HASIL PRAKTIKUM modul sebelumnya.

2. Jika praktikan tidak melaksanakan Tata Laksana poin 1, maka tidak

diperbolehkan mengikuti praktikum.

3. Setiap modul praktikum, akan dilakukan Pre-Test.

4. Format laporan meliputi :

Laporan Hasil Praktikum :

Halaman Depan

BAB I. Tujuan dan Landasan Teori

BAB II. Langkah Kerja

BAB III. Pembahasan

BAB IV. Kesimpulan

BAB V. Daftar Pustaka

BAB VI. Lampiran (disertai laporan rencana praktikum modul

sebelumnya)

5. Format Penulisan

Spasi : 1,5

Font : Times New Roman

Font Size : 12

Margins : Top 3, Left 4, Right 3, Bottom 3

Kertas : A4

3

6. Penilaian Laporan Hasil Praktikum

BAB I. Tujuan dan Landasan Teori Nilai 20

BAB II. Langkah Kerja Nilai 10

BAB III. Pembahasan Nilai 40

BAB IV. Kesimpulan Nilai 15

BAB V. Daftar Pustaka Nilai 5

BAB VI. Lampiran Nilai 10

Total 100

7. Praktikan yang mengabaikan format penulisan poin 5, akan dikurangi 5

setiap kesalahan.

8. Penilaian Akhir Praktikum :

Pre-Test : 15 %

Praktikum : 30 %

Laporan Praktikum : 20 %

Responsi : 35 %

Total 100 %

9. Penilaian Akhir Mata Kuliah Struktur Data :

Tugas : 20 %

UTS : 30 % 50 %

Praktikum : 50 %

UAS : 50 %

Nilai Akhir : 100 %

4

MODUL 1

STACK

A. Tujuan Praktikum

1. Mahasiswa mampu memahami konsep stack.

2. Mahasiswa mampu mengimplementasikan stack untuk memecahkan masalah

tertentu.

B. Landasan Teori

Stack atau tumpukan bisa diartikan sebagai kumpulan data yang seolah-olah

diletakkan di atas data yang lain. Satu hal yang perlu diingat bahwa kita bisa

menambah (menyisipkan) data dan mengambil (menghapus) data melalui ujung

yang sama, yang disebut sebagai ujung atas stack. Secara sederhana, sebuah stack

bisa diillustrasikan seperti gambar dibawah ini :

F

E

D

C

B

A

Dari gambar diatas, bisa di lihat bahwa kotak B terletak di atas kotak A dan di

bawah kotak C. Kotak D terletak diatas kotak C, kotak E terletak diatas kotak D

dan seterusnya sampai kotak terakhir. Dari gambar diatas menunjukkan bahwa

kotak lewat satu ujung, yaitu bagian atas. Apabila ada kotak lain yang akan

disisipkan, maka kotak tersebut akan diletakkan diatas kotak F, dan jika ada kotak

yang akan diambil, maka kotak F yang akan diambil untuk pertama kali.

Dengan demikian stack adalah struktur data yang menggunakan konsep Last In

First Out (LIFO) dan bersifat dinamis dimana data bisa ditambah maupun

diambil.

Stack dapat dideklarasikan dengan sebuah record yang mempunyai elemen sebuah

array tabelemen untuk menyimpan elemen stack dan sebuah variabel top untuk

menunjuk elemen stack teratas. Deklarasi selengkapnya sebagai berikut :

Const NMAX = ....; {ukuran maksimum stack} NULL = 0; {penunjuk stack kosong} Type tipedata = ....; {tipe data yang disimpan dalam stack}

Stack = record

tabelemen : array[1 .. NMAX] of tipedata top : NULL ... NMAX; {top dari stack} End;

atas (top)

5

Operasi pada stack

Berdasarkan sifat khusus stack, maka ada 2 operasi terhadap stack, yaitu :

1. Pengambilan elemen dilakukan pada top, yang disebut sebagai POP.

2. Penambahan elemen dilakukan pada top, yang disebut sebagai PUSH.

Implementasi stack :

1. Inisialisasi, adalah proses untuk membuat stack dalam keadaan kosong.

Proses ini dilakukan dengan mengisi variabel top dengan nilai yang tidak

menunjuk salah satu elemen array.

Procedure Inisialisasi (var S : stack); Begin S.Top := Null;

End;

2. Empty/kosong, adalah operasi untuk mengetahui status stack, yaitu kosong

atau tidak.

Function Empty (S : stack) : Boolean; {Mengirim nilai true jika S adalah stack kosong} Begin Empty := (S.Top=Null);

End;

3. Full/penuh, adalah operasi untuk mengetahui status stack, yaitu penuh atau

tidak.

Function Full (S : stack) : Boolean; {Mengirim nilai true jika S sudah penuh} Begin Empty := (S.Top=NMAX);

End;

4. Pop, dengan mempertimbangkan seleksi awal terhadap kondisi stack yaitu

hanya berlaku untuk stack yang tidak kosong

Procedure POP (var S : stack; var data :tipedata); {IS : S adalah stack yang tidak kosong} {FS : elemen top dari stack S dihapus dan disimpan di data} Begin If Not Empty (S) Then Begin

data := S.tabelemen[S.Top];

S.Top := S.Top – 1; End; Else

data:=..; {isi suatu nilai yang kemungkinan bukan data}

End;

5. Push, dengan mempertimbangkan seleksi awal terhadap kondisi stack

yaitu untuk menghindari overflow.

6

Procedure Push (var S : stack; data : tipedata); {IS : S adalah stack yang belum penuh, data terdefinisi} {FS : data menjadi elemen top dari stack S} Begin If not Full(S) then

Begin S.Top := S.Top + 1;

S.tabelemen[S.Top] := data;

End; End;

C. Tugas Praktikum

1. Buatlah program menggunakan prinsip tumpukan (stack) dan beri tiga

pilihan : push, pop dan quit. Jika dipilih push program akan meminta user

menginputkan sebuah kata, dimana maksimal 6 karakter jika lebih dari 6

akan muncul pesan kesalahan. Jika dipilih pop maka karakter teratas akan

dikeluarkan, bila belum ada kata yang dimasukkan maka waktu memilih

pop akan tampil pesan kesalahan. Jika dipilih quit maka program selesai.

Output :

Pilihan :

1. Push

2. Pop

3. Quit

Pilihan [1/2/3] = 1

Masukkan kata = Data

Hasil Push : Data

7

MODUL 2

QUEUE

A. Tujuan Praktikum

1. Mahasiswa mampu memahami konsep queue.

2. Mahasiswa mampu mengimplementasikan queue untuk memecahkan masalah

tertentu.

B. Landasan Teori

Queue (antrian) adalah kumpulan objek data yang tipenya sama, tersusun sebagai

sebuah barisan linier. Elemen pertama disebut sebagai front/head dan elemen

terakhir disebut rear/tail. Penambahan data dilakukan pada akhir elemen,

sedangkan penghapusan data dilakukan pada elemen pertama. Sifat queue tersebut

dikenal dengan istilah FIFO (First In First Out).

Queue dapat dideklarasikan dengan sebuah record yang mempunyai elemen-

elemen sebagai berikut : variabel front untuk menunjuk elemen pertama, variabel

rear untuk menunjuk elemen terakhir, dan sebuah array tabelemen untuk

menyimpan elemen queue. Deklarasi selengkapnya sebagai berikut :

Const NMAX = ....; NULL = 0; Type tipedata = ....;

queue = record tabelemen : array[1 .. NMAX] of tipedata front,rear : NULL ... NMAX; End;

Berdasarkan sifatnya, maka ada 2 operasi terhadap queue, yaitu :

1. Penambahan data pada elemen akhir queue, disebut Enqueue

2. Penghapusan data pada elemen pertama queue, disebut Dequeue

Proses untuk membuat queue dalam keadaan kosong dapat didefinisikan sebagai

berikut:

Procedure Inisialisasi (var Q : queue); Begin Q.front := NULL;

Q.rear := NULL;

End;

Proses untuk mengetahui status queue dalam keadaan kosong atau tidak dapat

didefinisikan sebagai berikut:

Function EmptyQ (Q : queue) : Boolean; Begin EmptyQ := ((Q.front=Null) and (Q.rear=Null)); End;

8

Pada saat penambahan data apabila ingin mengetahui apakah queue sudah penuh

atau belum, maka perlu diperhitungkan junlah elemen data pada queue. Sebuah

queue penuh jika Q.rear = NMAX. Namun demikian tidak selamanya kondisi

Q.rear =NMAX menunjukkan bahwa queue telah penuh. Kondisi Q.rear = NMAX

akan menunjukkan queue telah penuh bila selama proses pengoperasian queue

belum pernah ada data yang keluar (Dequeue).

Bila telah pernah terjadi operasi Dequeue maka akan terjadi pergeseran penanda

front sebanyak data yang telah keluar. Hal ini terjadi karena operasi Dequeue

dengan array hanya memindahkan index penanda front ke index yang di atasnya.

Dalam hal ini penghapusan elemen di depan mengakibatkan array pada index

awal menjadi kosong dan tidak terpakai. Jika hal ini terjadi maka perlu dilakukan

setup ulang index front (consolidate) dengan memindahkan semua data ke bagian

awal dari tabel.

Procedure Consolidate (var Q : queue); {IS : Q.rear = NMAX dan Q.front <>1} {FS : Q.front = 1 dan Q.rear = banyaknya data} Var i, j : integer;

Begin j:=1;

for i:= Q.front to Q.rear do begin Q.tabelemen[j] := Q.tabelemen[i];

j:=j+1;

end; Q.front :=1;

Q.rear :=j;

End; Procedure Enqueue (var Q : queue; data : tipedata); Begin If EmptyQ(Q) then

Q.front := 1;

If Q.rear <> NMAX then Begin

Q.rear := Q.rear+1;

Q.tabelemen[Q.rear] := data;

End Else If Q.front <> 1 then Begin Consolidate(Q);

Q.rear := Q.rear+1;

Q.tabelemen[Q.rear] := data;

End; End; Procedure Dequeue (var Q : queue; var data : tipedata); Begin If not Empty(Q) then

Begin data := Q.tabelemen[Q.front];

Q.front := Q.front+1;

If (Q.front > Q.rear) then Begin

9

Q.front := NULL;

Q.rear := NULL;

End; Else

data := .... ; End;

C. Tugas Praktikum

1. Sebuah plasa mempunyai ruang parkir yang hanya bisa diisi sampai 5 mobil

saja pada satu jalur. Mobil yang datang lewat salah satu jalur (sebut saja A),

sedang mobil yang akan keluar lewat jalur lainnya (sebut saja B). Jika ada

sebuah mobil yang akan keluar dan kebetulan berada di tengah, maka mobil-

mobil lain yang berada didepannya harus dipindahkan dulu, setelah mobil

tersebut keluar maka mobil-mobil yang dipindahkan tadi disusun kembali

seperti semula. Jika mobil yang akan masuk, tetapi jalur parkir sudah penuh

maka ada pesan “Parkir penuh!”. Buatlah program dari kasus diatas.

10

MODUL 3

LINKED LIST

A. Tujuan Praktikum

1. Memahami struktur data linked list.

2. Mengetahui implementasi linked list dengan pointer.

3. Mampu menggunakan struktur data linked list dalam menyelesaikan masalah

pemrograman.

B. Landasan Teori

Linked list merupakan struktur data yang memiliki kelebihan dalam efisiensi

memori dan kecepatan dalam menyisipkan data. Linked list berguna untuk

menyimpan beberapa data dalam memori. Komponen dasar dari suatu list disebut

sebagai node. Sebuah node terdiri dari dua buah bagian. Bagian pertama adalah

bagian yang memuat informasi data, bagian kedua adalah bagian yang

menunjukkan alamat data berikutnya atau disebut juga dengan bagian penunjuk.

Linked List dengan Pointer

Pascal menyediakan prosedur standar untuk membuat dan menghapus sebuah

variabel dinamis, yaitu new dan dispose. Jika P telah dideklarasikan sebagai

sebuah variabel pointer bertipe node, maka pernyataan new(P) akan menciptakan

sebuah variabel dinamis baru bertipe node dan menandai lokasinya dengan pointer

P. Sedangkan pernyataan dispose(P) akan mengembalikan ruang yang digunakan

pada lokasi yang ditunjuk P ke sistem komputer; pointer P menjadi tidak

terdefinisikan lagi. Ilustrasi penggunaannya adalah sebagai berikut :

P:= nil P Nil

New(P) P ??

P^:=123 P 123

Dispose(P) P ??

Deklarasi Linked List dengan Pointer

Type tipeinfo = record nim : string;

nilai : integer;

end; tipeptr = ^tipenode; tipelist = tipeptr;

tipenode = record info : tipeinfo;

next : tipeptr;

11

end; var list : tipelist;

Elemen-elemen list berupa record yang memuat field berisi informasi data serta

sebuah field bertipe pointer yang berisi alamat elemen berikutnya.

Operasi pada Linked List

1. Membuat List

Prosedur ini berupa prosedur untuk membuat list pertama kali, yaitu

mengalokasikan pointer untuk head. Nilai awal dari list adalah kosong (nil).

procedure inisialisasi (var list : tipelist); begin new(list); list := nil; end;

2. Mengetahui Panjang List (Jumlah Elemen)

Mengetahui panjang list dilakukan dengan menghitung seluruh node. Caranya

adalah mengunjungi setiap node dan menaikkan nilai counter hingga

dijumpai node terakhir. Contoh fungsinya adalah :

function size (list : tipelist) : integer; var i : integer; begin i := 0;

while list <> nil do begin i := i + 1;

list := list^.next;

end; size := i;

end;

3. Menyisipkan Node Baru

Menyisipkan node baru pada list dilakukan dengan cara mencari lokasi

tempat node baru akan disisipkan, kemudian menyisipkan node baru tersebut.

Hal ini dapat dilakukan menggunakan bantuan sebuah pointer untuk mencari

sebuah node yang akan tersambung langsung dengan node baru. Kemudian,

node baru dapat disisipkan pada lokasi sebelum atau sesudah node tersebut.

Sebagai contoh, prosedur berikut adalah untuk menyisipkan node baru

sebelum node:

procedure sisipnode (var list : tipelist; IB : tipeinfo); var NB, ptr : tipeptr;

ketemu : boolean;

begin new(NB); NB^.info := IB;

NB^.next := nil; if list = nil then list := NB else

12

if IB.nim <= list^.info.nim then begin NB^.next := list;

list := NB;

end else begin ketemu := false;

ptr := list;

while (ptr^.next <> nil) and not (ketemu) do begin if ptr^.next^.info.nim >= IB.nim then ketemu := true

else ptr := ptr^.next end; NB^.next := ptr^.next;

Ptr^.next := NB

end end;

4. Mengganti Nilai Informasi pada Suatu Node dalam List

Mengganti nilai informasi hanya akan mengganti info pada suatu node tanpa

menghapus node tersebut. Hal ini dapat dilakukan dengan mencari node yang

sesuai dengan nilai yang akan diganti, selanjutnya mengganti nilai lama

dengan nilai yang baru.

Berikut ini contoh prosedur untuk mengganti nilai pada suatu list :

a. Mengganti nilai mahasiswa berdasarkan nomor mahasiswa,

b. Mengganti semua node yang mempunyai nilai tertentu (nilai lama) dengan

nilai yang baru.

procedure gantinode1 (var list : tipelist; KunciGanti :

string; nilaibaru : integer);

var ptr : tipeptr; begin new(ptr); ptr := list;

while (ptr <> nil) and (ptr^.info.nim <> KunciGanti) do ptr := ptr^.next;

if ptr <> nil then ptr^.info.nilai := nilaibaru

end;

procedure gantinode2 (var list : tipelist; nlama, nbaru : integer);

var ptr : tipeptr; begin new(ptr); ptr := list;

while (ptr <> nil) do begin if ptr^.info.nilai := nlama then ptr^.info.nilai := nbaru;

ptr := ptr^.next

end; end;

13

5. Menghapus Node dari Suatu List

Menghapus node adalah menghapus sebuah elemen dari list. Hal ini dapat

dilakukan dengan mencari/menandai node yang akan dihapus, yaitu node

yang memuat nilai seperti yang akan dihapus, kemudian mengarahkan pointer

pada node sebelumnya ke arah node sesudah node yang akan dihapus, dan

kemudian menghapus node yang dimaksud.

procedure hapusnode (var list : tipelist; KunciHapus :

string);

var ptr1, ptr2 : tipeptr; begin new(ptr1); new(ptr2); ptr1 := nil; ptr2 := nil; while (ptr2^.info.nim <> KunciHapus) do begin ptr1 := ptr2;

ptr2 := ptr2^.next

end; if ptr1 = nil then list := list^.next

else ptr1^.next := ptr2^.next

dispose(ptr2) end;

C. Tugas Praktikum

Buatlah program untuk menambah, menghapus dan menampilkan data dengan

linier linked list dan data tersebut harus urut.

14

MODUL IV

PENGURUTAN DATA

A. Tujuan Praktikum

1. Mengetahui implementasi beberapa metode pengurutan data.

2. Mampu menerapkan metode pengurutan data pada sebuah program.

3. Mengetahui perbandingan kompleksitas beberapa metode pengurutan data.

B. Landasan Teori

Pengurutan data adalah proses yang dilakukan terhadap himpunan data,

disusun sedemikian rupa sehingga diperoleh data baru terurut. Pada umumnya ada

dua macam pengurutan, yaitu: (1) pengurutan secara ascending (urut naik) dan (2)

Pengurutan secara descending (urut turun). Proses pengurutuan seluruh data

berada dalam memori disebut internal sorting. Sedangkan bila data tidak berada

di dalam memori disebut external sorting.

Masalah utama dalam pengurutan adalah bagaimana mendapatkan metode

terbaik yang akan memberikan jumlah operasi pemindahan data paling minimum.

Kedua operasi tersebut akan mempengaruhi algoritma pengurutan data. Umumnya

kompleksitas algoritma biasa dilihat dari waktu (time complexity) atau ruang

(space complexity).

Algoritma pengurutan data yang akan diuraikan dan dilakukan dalam

praktikum sturktur data ini hanya mencakup tiga metode pengurutan data yaitu:

(1) Insertion Sort (Pengurutan Penyisipan), (2) Selection Sort (Pengurutan

Pemilihan), dan (3) Bubble Sort (Pengurutan Gelembung). Berikut ini merupakan

penjelasannya.

1. Insertion Sort (Pengurutan Penyisipan)

Metode ini dilakukan dengan cara menyisipkan elemen larik pada posisi

yang tepat. Prinsip kerja metode ini membagi dua data sedemikian rupa sehingga

pada bagian pertama menampung data yang sudah terurut dan bagian kedua

menampung data yang belum terurut. Selanjutnya diambil satu data dari bagian

yang belum terurut dan dilakukan penyisipan ke bagian yang sudah terurut. procedure insertionSort (var A: Tabel; N: integer); {IS : Tabel A terdefinisi dengan N adalah banyaknya data} {FS : Tabel A terurut membesar} var pass, i: integer; {counter} temp : integer; {variabel untuk nilai sementara} begin for pass := 2 to N do begin

temp := A[pass];

I := pass-1;

while ((temp < A[i]) and (i > 1)) do begin

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

i := i-1;

end;

15

if (temp < A[i]) then begin A[i+1] :=A [i];

i := i-1;

end; A[i+1] := temp;

end; end;

2. Selection Sort (Pengurutan Pemilihan)

Metode minimum dan maximum sort merupakan metode yang tergolong

dalam selection sort. Pada minimum sort, untuk meletakkan data pada posisi ke-i

dilakukan dengan mencari niai minimum data mulai dari posisi ke-i sampai

dengan posisi ke-N dengan N adalah banyaknya data. Untuk maximum sort

dilakukan dengan menggunakan nilai maksimum. procedure switch (var A,B: Tabel); {IS : Tabel A dan B berisi nilai missal A = x dan B = y} {FS : A = y dan B = x } var temp: integer; {variabel untuk nilai sementara} begin

temp := A; A := B; B := temp;

end; procedure minimumSort (var A: Tabel; N: integer); {IS : Tabel A terdefinisi dengan N adalah banyaknya data} {FS : Tabel A terurut membesar} var pass, i: integer; {counter} imin : integer; {variabel untuk indeks nilai minimum} begin for pass := 1 to N-1 begin

imin := pass;

for i := pass + 1 to N do begin

if (A[imin] > A[i]) then imin := i; if (imin <> pass) then switch(A[pass], A[imin]);

end; end;

end;

3. Bubble Sort (Pengurutan Gelembung)

Prinsip dari bubble sort adalah meletakkan nilai pada posisi ke-i dengan

menggelembungkan atau mengangkat nilai minimum dari i+1 sampai dengan N. procedure bubbleSort (var A: Tabel; N: integer); {IS : Tabel A terdefinisi dengan N adalah banyaknya data} {FS : Tabel A terurut membesar} var pass, i: integer; {counter} tukar : boolean; {true jika untuk satu kali pass terjadi

pertukaran}

begin tukar := true; pass := 1;

16

while ((tukar) and (pass < N)) do begin

tukar := false; for i := N downto pass+1 do begin

if (A[i] < A[i-1]) then begin switch (A[i], A[i-1])); tukar := true; end;

end; end;

end;

Implementasi dari ketiga metode sorting tersebut dilakukan menggunakan data

sebagai berikut. Const NMax = 100;

Type Tabel = array[1..NMax] of integer;

C. Tugas Praktikum

Buatlah sebuah program dengan ketentuan sebagai berikut :

1. Pengurutan (sorting) menggunakan ketiga metode :

a. Insertion sort

b. Selection Sort

c. Bubble Sort

2. Masukan awal adalah data bertipe record mahasiswa dengan elemen : NIM : integer; Nama : string[30]; Alamat : string[50];

3. Proses pengurutan bisa dipilih berdasarkan NIM atau Nama secara ascending.

4. Keluaran adalah data yang telah diurutkan.

17

MODUL V

PENCARIAN DATA

A. Tujuan Praktikum

1. Mengetahui beberapa metode pencarian data.

2. Mampu menggunakan metode pencarian data pada sebuah program untuk

menyelesaiakan masalah.

B. Landasan Teori

Pencarian merupakan proses fundamental dalam pegelolaan data. Proses

pencarian menemukan nilai tertentu dalam himpunan data yang bertipe sama.

Apabila data yang dicari terdapat dalam himpunan data tersebut, ditentukan pula

posisi dari data yang dicari pada himpunan.

Pada himpunan data tidak terurut, dapat digunakan metode pencarian

sekuensial (Sequensial Search) untuk mencari data. Sedangkan pada himpunan

data tidak terurut dapat digunakan metode pencarian sekuensial (Sequensial

Search) dan biner (Binary Search). Berikut ini merupakan penjelasan dari metode

pencarian tersebut.

1. Pencarian Sekuensial (Sequensial Search)

Metode pencarian sekuensial merupakan proses membandingkan setiap

eleman dalam himpunan satu per satu secara terurut, mulai dari elemen pertama

sampai dengan elemen yang dicari ditemukan atau seluruh elemen sudah

dibandingkan. Sebagai contoh, misalkan data terurut membesar. Pencarian

dimulai dari data pertama sampai dengan data terakhir. Pencarian dihentikan

apabila data yang dicari ditemukan atau data yang dibandingkan pada proses

pencarian sudah lebih besar dari data yang dicari. procedure sequensialSort (var A: Tabel; N: integer; x: tipedata; var iSearch:integer); {IS : A adalah tabel dengan banyaknya data N. x adalah data yang dicari dan beritpe sama dengan elemen tabel} {FS : iSearch <> 0 bila A[iSearch] = x, iSearch = 0 bila x tidak ditemukan di A} var i: integer; {counter} begin if (N = 0) then iSearch := 0{tabel berisi data 0}

else begin i := 1;

while ((A[i].NIM < x) and (i < N)) do i := i + 1;

if (A[i].NIM = x) then iSearch := i;

else iSearch := 0;

end; end;

18

2. Pencarian Biner (Binary Search)

Pencarian biner hanya berlaku untuk data yang sudah terurut. Bila data

terurut membesar. Pencarian dilakukan pada posisi data yang di tengah (misal :

posisi m).

Ada tiga kemungkinan yang akan terjadi, yaitu: (1) data di tengah = data

yang dicari : pencarian selesai, data ditemukan, (2) data di tengah < data yang

dicari : pencarian di sebelah “kanan”, dan (3) data di tengah > data yang dicari :

pencarian di sebelah “kiri”. Proses dilakukan berulang-ulang sampai data

ditemukan atau himpunan data tidak bias dibagi lagi.

procedure binarySort (var A: Tabel; N: integer; x: tipedata; var iSearch:integer); {IS : A adalah tabel dengan banyaknya data N. x adalah data yang dicari dan beritpe sama dengan elemen tabel} {FS : iSearch <> 0 bila A[iSearch] = x, iSearch = 0 bila x tidak ditemukan di A} var bawah, atas, tengah: integer;

found : boolean; begin if (N = 0) then iSearch := 0{tabel berisi data 0}

else begin bawah := 1;

atas := N;

found := false; while ((not found) and (atas > bawah)) do

begin tengah := (bawah + atas) div 2;

if (A[tengah].NIM = x) then found := true;

else if (A[tengah].NIM = x) then

atas := tengah - 1;

else bawah := tengah + 1;

end;

if found then iSearch := tengah;

else iSearch := 0;

end; end;

19

C. Tugas Praktikum

Buatlah sebuah program dengan ketentuan sebagai berikut :

1. Pencarian (searching) data dengan menggunakan kedua metode :

a. Pencarian Sekuensial

b. Pencarian Biner

2. Masukan awal adalah data bertipe record Pegawai Perusahaan yang telah

terurut membesar (ascending) dengan elemen : Nomor_pegawai : integer; Nama_pegawai : string[30]; Bagian : string[20]; Gaji : integer;

3. Pencarian data didasakan pada Nomor_induk pegawai yang dicari.

Perintah untuk melakukan pencarian tidak hanya sekali, bisa dilakukan

beulang-ulang sesuai keinginan pengguna/user.

4. Keluaran/hasil berupa data yang dicari untuk setiap perintah pencarian.