MODUL I

TUMPUKAN (STACK)

A. MAKSUD DAN TUJUAN

1. MAKSUD

Memberikan pemahaman tentang tipe data tumpukan beserta oerasinya.

2. TUJUAN

Mahasiswa dapat menggunakan tipe data tumpukan (stack) serta operasi-

operasi yang dapat dilakukan dengan tipe data tersebut.

B. TEORI

Secara sederhana tumpukan bisa diartikan sebagai suatu kumpulan data

yang seolah-olah ada data yang diletakkan di atas data lain. Satu hal yang

perlu diingat adalah bahwa kita bisa menambahkan (menyisipkan) data,

mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai

ujung atas tumpukan (top of stack).

Implementasi tumpukan dengan larik

Penyajian tumbukan bisa menggunakan larik )array) walaupun

penyajian dengan menggunakan larik dianggap kurang tepat karena

banyaknya elemen dalam larik sudah tertentu (statis) sedangkan pada

tumpukan, banyaknya elemen bisa sangat bervariasi (dinamis). Meskupun

demikian , larik bisa digunakan dengan anggapan bahwa banyaknya elemen

maksimal dari tumpukan tersebut tidak akan melebihi batas maksimal dari

banyaknya elemen dalam larik.

Deklarasi tumpukan bisa menggunakan tipe data terstruktur yaitu tipe

rekaman (record) yang terdiri dari dua medan. Medan pertama berisi larik

untuk menyimpan elemen tumpukan yang bertipe, sedang medan kedua

bertipe integer untuk mencatat posisi ujung tumpukan, sebagai berikut:

Const max_elemen = 255;

Type tumpukan = record

Isi : array [1..max_elemen] of integer;

Atas : 0..max_elemen;

End;

Var t:tumpukan;

Operasi yang bisa dilakukan pada tumpukan adalah operasi push, dan operasi

pop.

Implementasi prosedur push:

Procedure push(var T:tumpukan; x:integer);

Begin

T.Atas := T.Atas + 1;

T.Isi[T.Atas] := x;

End;

Implementasi prosedur pop:

Procedure pop(var T:tumpukan);

Begin

T.Atas := T.Atas – 1;

End;

C. PRAKTIK

1. Cobalah program di bawah ini, amati untuk beberapa masukan yang

berbeda.

Program pop_push;

Uses crt;

Const elemen = 225; {batas maksmimum karakter}

Type s255 = string [elemen];

Tumpukan = record

Isi : s255;

Atas : 0 ..elemen;

End;

Var t : tumpukan;

W : char;

Kalimat:s255;

I,j : integer;

Procedure awalan(var : tumpukan);

Begin

T.atas := 0

End;

Procedure push(var T : tumpukan; x : char);

Begin

T.atas := t.atas+1;

T.isi[t.atas] := x;

End;

Function pop(var t:tumpukan): char;

Begin

Pop:=t.isi[t.atas];

t.atas := t.atas-1

end;

begin {program utama}

clrscr;

{melakukan proses push}

writeln(‘Masukkan kalimat = ‘);

read(kalimat);

for i:=1 to lenght(kalimat) do

push(t, kalimat[i]);

write(‘Elemen yang di-push = ‘,kalimat);

readln;

{melakukan proses pop}

for i:=1 to lenght(kalimat) do

push(t,kalimat[i]);

writeln;

writeln(‘Hasil akhir push dibaca dengan

pop = ‘);

{menampilkan hasil proses pop}

for j:= 1 to lenght(kalimat) do

begin

w:=pop(t);

write(w);

end;

readln;

end.

2. Modifikasi program diatas untuk menambahkan sebuah karakter dalam

tumpukan.

Contoh input : STMIK El Rahma

Tambahan karakter : q

Hasil akhir : q amhaR lE KIMTS

D. TUGAS

1. Pada prosedur push jika ada kondisi nitai T.atas sama dengan

max_elemen dan akan dilakukan operasi push, apa yang terjadi?

Kemudian tambahkan pernyataan pada prosedur push diatas untuk

menghindari kondisi tersebut.

2. Pada prosedur pop jika kondisi t.atas=0 kemudian dilakukan operasi

pop, apa yang terjadi? Kemudian tambahkan pernyataan pada prosedur

pop di atas untuk menghindari kondisi tersebut.

MODUL II

TIPE DATA POINTER

A. MAKSUD DAN TUJUAN

1. MAKSUD

Memberikan pemahaman tentang tipe data pointer beserta operasinya.

2. TUJUAN

Agar mahasiswa dapat menggunakan tipe data pointer dengan

melakukan operasi mengkopi pointer, mengkopi isi simpul, dan

menghapus pointer.

B. TEORI

Sampai saat ini tipe data baik yang sederhana maupun yang tersetruktur.

Struktur dari tipe-tipe tersebut mempunyai keterbatasan, yakni bersifat statis.

Sebagai akibatnya, ukuran dan urutannya sudah pasti. Pada suatu larik,

elemen yang satu mendahului elemen yang lain. Ukurannya sudah pasti, tidak

dapat melebihi ukuran maksimun dari yang sudah dideklarasikan. Kelemahan

lain dari variabel statis adalah ruang memori yang sudah digunakan tidak

dibebaskan.

Pointer merupakan tipe data yang bersifat dinamis yang bisa dipesan jika

diperlukan dan dapat dibebaskan kembali bila sudah tidak digunakan. Struktur

data yang menggunakan variabel dinamis disebut dengan struktur data

dinamis. Variabel dinamis tidak dapat dideklarasian secara langsung seperti

halnya variabel-variabel statik. Variabel dinamis hanya ditunjukkan oleh

variabel khusus yang berisi alamat memori yang digunakan oleh variabel

tersebut. Variabel khusus ini disebut dengan variabel pointer. Suatu tipe data

pointer dideklarasikan dengan menggunakan simbol ^.

Meskipun telah dideklarasikan suatu variabel pointer yang akan

menunjukkan kesuatu tipe data tertentu namun variabel dinamis tidak akan

dialokasikan selama belum ada perintah pengalokasian varibel dinamis.

Begitu pula saat variabel dinamis sudah tidak digunakan lagi.

C. PRAKTIK

1. Cobalah program dibawah ini, amati untuk beberapa masukan yang

berbeda.

Program pointer;

Uses crrt;

Type simpul = ^data;

Data = record

Nama: string;

Alamat: string;

Berikut: simpul;

End;

Var t1,t2,t3,t4,t5,t6 : simpul;

Begin

Clrscr;

New(t1);

New(t2);

New(t3);

New(t4);

New(t5);

New(t6);

T1^.nama := ‘kikir’;

T1.alamat := ‘jogja’;

Writeln;

Writeln(‘ nama : ‘,t1^.nama);

Writeln;

Writeln(‘ alamat : ‘,t1^.alamat);

T2:=t1;

Writeln;

Writeln(‘ nama : ‘,t2^.nama);

Writeln;

Writeln(‘ alamat : ‘,t2^.nama);

End.

Dari program diatas bisa dirinci sebagai berikut:

Operasi mengisi sampul t1

T1^.nama := ‘kikir’;

T1.alamat := ‘jogja’;

Operasi membaca simpul t1

Writeln(‘ nama : ‘,t1^.nama);

Writeln(‘ alamat : ‘,t1^.alamat);

Operasi copy pointer

T2:=t1;

Operasi copy isi sampul

T2^ := t1^

Operasi hapus simpul

Dispose(t1)

2. Isikan simpul t2 dengan data nama Joko dan alamat Solo kemudian

lakukan opeasi kopi pointer

T3 := t1;

T5 := t1;

Dan lakukan operasi kopi isi simpul

T4^ := t2^;

T6^ := t2^;

D. TUGAS

Buatlah program perpustakaan dengan masukan:

Nama buku

Pengarang

nomor indeks

Tampilan berupa

Menu pilihan

T : menambah buku

H : menghapus buku

S : Selesai

Pilih menu?

MODUL III

SENARAI 1

A. MAKSUD DAN TUJUAN

1. MAKSUD

Pengenalan senerai (linked list) dengan opeasi tambah simpul dan opeasi

baca isi simpul.

2. TUJUAN

Agar praktikan bisa membangun suatu senerai (linked list) dengan

melakukan operasi penambahan simpul dan bisa mengakses isi simpul

yang membentuk senerai berantai.

B. TEORI

Disebut senerai berantai karena satu elemen dengan elemen yang lain

bisa dihubungkan satu sama lain dengan bantuan pointer. Dengan demikian,

setiap simpul dalam suatu senerai berantai terbagi menjadi dua bagian. Bagian

pertama, disebut medan informasi, berisi informasi yang akan disimpan dan

diolah. Bagian kedua, disebut medan penyambung (link field), berisi alamat

simpul berikutnya.

Gambar di bawah ini menunjukkan skematis dari senerai berantai

dengan 4 buah simpul. Setiap simpul digambarkan dalam 2 bagian. Bagian

kiri adalah medan informasi. Bagian kanan berupa medan penyambung,

sehingga dalam diagram digambarkan sebagai anak panah. Perlu diingat

bahwa medan penyambung sebenarnya adalah suatu pointer yang menunjuk

ke simpul berikutnya, sehingga nilai dari medan ini adalah alamat suatu lokasi

tertentu dalam pengingat.

Awal

Medan penyampung dari simpulMedan informasi dari simpul

A B C D

Pada gambar di atas, pointer awal menunjuk ke simpul pertama dari senerai

tersebut. Medan penyambung (pointer) dari suatu simpul yang tidak menunjuk

simpul lain disebut pointer kosong, yang nilainya dinyatakan sebagai nil (nil

adalah kata baku Pascal yang berarti bahwa pointer 0 atau bilangan negatif).

Jadi kita bisa melihat bahwa dengan hanya sebuah pointer Awal saja maka

kita bisa membaca semua informasi yang tersimpan dalam senerai.

Menambah simpul

Sekarang kita akan mempelajari bagaimana menambah simpul baru ke dalam

senerai berantai. Kita anggap bahwa simpul baru yang akan ditambah selalu

menempati posisi setelah posisi yang terakhir dari senerai berantai yang

diketahui. Untuk menjelaskan operasi ini baiklah kita gunakan deklarasi

pointer dan simpul seperti di bawah ini:

Type simpul = ^ data;

Data = reecord

Info : char;

Berikut:simpul;

End;

Var elemen : char;

Awal, akhir, baru : simpul;

Ilustrasi penambahan simpul bru di akhir senerai berantai disajikan pada

gambar di bawah ini. Pointer Awal adalah pointer yang menunjuk ke simpul

pertama, pointer Akhir menunjnuk ke simpul terakhir dan yang ditunjuk oleh

pointer baru adalah simpul yang akan ditambah. Dianggap bahwa simpul

awal dan simpul akhir telah terbentuk.

Awal Akhir Baru

A B C D F

Awal Akhir Baru

Awal Akhir

Baru

Untuk menyambung simpul yg ditunjuk oleh akhir dan Baru, pointer pada

simpul yg ditunjuk oleh simpul akhir dibuat sama dengan baru kemudian

pointer akhir dibuat sama dengan pointer baru.

Dengan memperhatikan gambar di atas, maka kita bisa menyusun prosedur

untuk menambah simpul baru dibelakang senarai berantai. Dalam hal ini perlu

pula ditest apakah senarai berantai masih kosong atau tidak. Senarai berantai

yang masih kosong ditandai dengan nilai pointer Awal yang nilainya sama

dengan nil. Berdasarkan deklarasi simpul dan pointer di atas, maka prosedur

untuk menambah simpul di belakang senarai berantai bisa disusun seperti

berikut:

Procedure TAMBAH_BELAKANG (var Awal, Akhir : Simpul;

Elemen : char);

Var baru : simpul;

Begin

New (baru); baru^.info := elemen;

If awal = nil then{senarai masih kosong}

Awal := baru

Else

Akhir^.berikut := baru

Akhir := baru

Akhir^.beriku:=nil

End;

Menambah Simpul di tengah

A B C D F

A B C D F

Untuk menambah simpul baru ditengah, pertama kali ditenukan di

mana simpul baru akan ditambahkan pada poisi urutan simpul yang keberapa.

Hal ini dapat dilakukan dengan menempatkan simpul pointer bantu pada

posisi tertentu. Kemudian pointer yang ditunjuk oleh pointer simpul baru

dibuat sama dengan pada simpul yang ditunjuk oleh simpul bantu, selanjutnya

pointer pada simpul yang ditunjnuk oleh simpul bantu, selalnjutnya pointer

pada simpul yang ditunjuk pada simpul yang ditunjuk oleh simpul bantu

dibuat sama dengan baru. Perhatikan bahwa urutan ini tidak boleh dibalik.

Menghapus simpul

Operasi kedua yang akan dijelaskan adalah operasi menghapus simpul.

Dalam menghapus simpul simpul satu hal yang perlu diperhatikan, yaitu

bahwa simpul yang bisa dihapus adalah simpul yang berada sesuai simpul

yang ditunjuk oleh suatu pointer (dalam gambar adalah simpul yang berada di

sebelah kanan simpul yang ditunjuk oleh suatu pointer), kecuali untuk simpul

pertama. Dengan demikian, kita tidak bisa menghapus simpul yang ditunjuk

oleh suatu pointer atau simpul sebelumnya. Untuk jelasnya perhatikan

ilustrasi pada gambar berikut.

Awal Bantu Akhir

Jika senarai berntai adalah seperti diatas, maka kita hanya bisa menghapus

simpul yang berisi ‘A’ dan simpul yang beisi ‘D’ supaya senarai tetap bisa

dipertahankan. Memang kita bisa menghapus simpul yang berisi ‘C’, tetapi

senarai yang kita miliki akan menjadi terputus, karena akan lebih sulit untuk

menyambung lagi simpul ‘B’ dengan simpul ‘D’.

Untuk menghapus simpul pertama, maka pointer Bantu kita buat sama dengan

pointer Awal. Kemudian pointer Awal kita pindah ke simpul yang ditunjjuk

oleh pointer pada simpul yang ditunjuk oleh pointer Bantu kita dispose.

Adapun prosedur menghapus simpul pertama adalah sebagai berikut:

Procedure Hapus_pertama (var awal : simpul);

A B C D

Var baru : simpul;

Begin

If awal = nil then {senerai masih kosong}

Writeln(‘Senarai masih kosong, tidak mungkin

dihapus’)

Else if awal^.berikut = nil then {senarai berisi

sebuah simpul }

Awal := nil

Else

Beginbantu := awal;

Awal :=bantu^.berikut;

Dispose(bantu);

End;

End;

Untuk menghapus simpul terakhir, tidak bisa dilakukan hanya dengan

mendispose simpul akhir. Karena dengan disposenya simpul akhir, maka

hanya simpul akhir saja yang dihapus, tetapi simpulnya masih tetap bisa

dimasup, karena masih ditunjuk oleh pointer dari simpul di sebeah kirinya.

Sehingga untuk bisa menghapus simpul terakhir, selain simpul akhir kita

hapus, maka pointer dari sebelah kirinya juga harus dijadikan nil.

Membaca Isi Senarai Berantai

Jika kita mempunyai senarai berantai seperti yang kita pelajari, maka dengan

cara biasa kita hanya bisa membaca isi simpul dimulai dari simpul paling kiri

sampai simpul paling kanan (membaca maju). Untuk membaca dari simpul

paling kanan ke simpul paling kiri, harus dilakukan dengan proses rekursif.

Pembacaan senarai berantai secara maju bisa dijelaskan sebagai berikut.

Pertama kali kita atur supaya pointer bantu menunjuk ke simpul yang ditunjuk

oleh pointer awal. Setelah isi simpul tsb dibaca, maka pointer bantu kita

gerakkan ke kanan untuk membaca simpul berikutnya. Proses ini kita ulang

sampai pointer bantu sama dengan pointer akhir. Ilustrasi embaca senarai

berantai dari kiri ke kanan dapat dilihat pada gambar di bawah ini.

Awal Bantu Akhir

C. PRAKTIK{Program tambah dan baca}

program senarai_berantai;

uses crt;

const garis =

‘------------------------------------------‘;

pesan = ‘Senerai berantai masih kosong’;

type simpul = ^data;

data = record

nama,

alamat : string;

berikut : simpul

end;

var awal,

akhir : simpul ;

pilih : char;

cacah : integer;

{fungsi untuk memilih menu}

function menu : char;

var p : char;

begin

clrscr;

gotoxy(30,3); writeln(‘DAFTAR MENU PILIHAN’);

gotoxy(20,8); writeln(‘A. MENAMBAH SIMPUL BARU DI

AWAL SENARAI’);

gotoxy(20,9); writeln(‘B. MENAMBAH SIMPUL BARU DI

AKHIR SENARAI’);

gotoxy(20,10); writeln(‘C. MENCETAK ISI SENARAI’);

gotoxy(20,11); writeln(‘D. SELESAI’);

repeat

gotoxy(48,15); writeln(‘ ’:10);

gotoxy(30,20); writeln(‘PILIH SALAH SATU’);

A B C D

p:= upcase (readkey);

until p in [‘A’ .. ‘D’];

menu :=p

end;

{fungsi alokasi simpul }

function simpul_baru : simpul;

var b : simpul;

begin

new(b);

with b^ do

begin

write(‘Nama :’); readln(nama);

write(‘Alamat : ‘);readln(alamat);

berikut :=nil

end;

simpul_baru:=b

end;

{fungsi tambah simpul baru di awal senarai}

procedure tambah_awal (n:integer);

var baru : simpul;

begin

if n <> o then

begin

writeln(‘menambah simpul baru di awal senarai’);

writeln(copy(garis,1,45))

end;

writeln;

baru:=simpul_baru;

if awal = nil then

akhir :=baru

else baru^.berikut := awal;

awal :=baru;

end;

{fungsi tambah simpul baru di akhir senarai}

procedure tambah_akhir (n:integer);

var baru : simpul;

begin

clrscr;

if n <> o then

begin

writeln(‘Menambah simpul baru di akhir senarai’);

writeln(copy(garis,1,46))

end;

writeln;

baru:=simpul_baru;

if awal = nil then

awal := baru

else

akhir^.berikut := baru

akhir:=baru;

end;

{prosedu baca isi senarai}

procedure baca_senarai;

var bantu:simpul;

i:integer;

begin

i:=1;

writeln(‘Membaca isi senarai’);

writeln(‘teken <enter> untuk kembali ke menu’);

writeln(copy(garis,1,42));

writeln;

if bantu = nil then

writeln(‘Data masih kosong’);

else

bantu := awal;

while bantu <> nil do

begin

writeln(‘simpul : ‘, i:3,’ - nama :

‘,bantu^.nama);

writeln(‘ ‘:17,’ alamat : ‘,bantu^.alamat);

bantu:=bantu^.berikut;

inc(i)

end;

repeat until keypressed

end;

{program utama}

cacah:=0;

awal:=nil;

akhir:=nil;

repeat

pilih:=menu;

clrscr;

case pilih of

‘A’ :tambah_awal(1);

‘B’ : tambah_akhir(1);

‘C’ :baca_senarai;

end;

if pilih in[‘A’,’B’] then inc(cacah)

until pilih = ‘D’

end.

Cobalah dengan simpul berikut:

Nama Alamat

Jeny-1 Solo-1

Jeny-2 Solo-2

Jeny-3 Solo-3

Jeny-4 Solo-4

Jeny-5 Solo-5

D. TUGAS

Pada program diatas tambahlah satu procecdure untuk menambah simpul

ditengah, dengan penambahan simpul baru bisa diatur pada posisi berapa simpul

baru akan diletakkan pada posisi senarai.

MODUL IV

SENARAI II

A. MAKSUD DAN TUJUAN

1. MAKSUD

Pengenalan senarai (linked list) dengan operasi penambahan simpul

baru pada poisi yang dipilih dan penghapusan simpul pada posisi yang

dipilih, operasi pencarian simpul tertentu, dan operasi baca isi simpul

yang membentuk senarai.

2. TUJUAN

Agar praktikan dapat membangun suatu senarai dengan menerapkan

operasi penambahan simpul baru pada posisi yang dipilih dan juga operasi

penghapusan pada posisi simpul yang dikehendaki, operasi pencarian

simpul tertentu, dan dapat memanfaatkan operasi baca dalam rangka

mengakses isi simpul.

B. TEORI

Disebut senerai berantai karena satu elemen dengan elemen yang lain

bisa dihubungkan satu sama lain dengan bantuan pointer. Dengan demikian,

setiap simpul dalam suatu senerai berantai terbagi menjadi dua bagian. Bagian

pertama, disebut medan informasi, berisi informasi yang akan disimpan dan

diolah. Bagian kedua, disebut medan penyambung (link field), berisi alamat

simpul berikutnya.

Gambar di bawah ini menunjukkan skematis dari senerai berantai

dengan 4 buah simpul. Setiap simpul digambarkan dalam 2 bagian. Bagian

kiri adalah medan informasi. Bagian kanan berupa medan penyambung,

sehingga dalam diagram digambarkan sebagai anak panah. Perlu diingat

bahwa medan penyambung sebenarnya adalah suatu pointer yang menunjuk

ke simpul berikutnya, sehingga nilai dari medan ini adalah alamat suatu lokasi

tertentu dalam pengingat.

Awal

Medan penyampung dari simpul

Medan informasi dari simpul

Pada gambar di atas, pointer awal menunjuk ke simpul pertama dari senerai

tersebut. Medan penyambung (pointer) dari suatu simpul yang tidak menunjuk

simpul lain disebut pointer kosong, yang nilainya dinyatakan sebagai nil (nil

adalah kata baku Pascal yang berarti bahwa pointer 0 atau bilangan negatif).

Jadi kita bisa melihat bahwa dengan hanya sebuah pointer Awal saja maka

kita bisa membaca semua informasi yang tersimpan dalam senerai.

Menambah simpul

Sekarang kita akan mempelajari bagaimana menambah simpul baru ke dalam

senerai berantai. Kita anggap bahwa simpul baru yang akan ditambah selalu

menempati posisi setelah posisi yang terakhir dari senerai berantai yang

diketahui. Untuk menjelaskan operasi ini baiklah kita gunakan deklarasi

pointer dan simpul seperti di bawah ini:

Type simpul = ^ data;

Data = reecord

Info : char;

Berikut:simpul;

End;

Var elemen : char;

Awal, akhir, baru : simpul;

A B C D

Ilustrasi penambahan simpul bru di akhir senerai berantai disajikan pada

gambar di bawah ini. Pointer Awal adalah pointer yang menunjuk ke simpul

pertama, pointer Akhir menunjnuk ke simpul terakhir dan yang ditunjuk oleh

pointer baru adalah simpul yang akan ditambah. Dianggap bahwa simpul

awal dan simpul akhir telah terbentuk.

Awal Akhir Baru

Awal Akhir Baru

Awal Akhir

Baru

Untuk menyambung simpul yg ditunjuk oleh akhirdan Baru, pointer pada

simpul yg ditunjuk oleh simpul akhir dibuat sama dengan baru kemudian

pointer akhir dibuat sama dengan pointer baru.

Dengan memperhatikan gambar di atas, maka kita bisa menyusun prosedur

untuk menambah simpul baru dibelakang senarai berantai. Dalam hal ini perlu

pula ditest apakah senarai berantai masih kosong atau tidak. Senarai berantai

yang masih kosong ditandai dengan nilai pointer Awal yang nilainya sama

dengan nil. Berdasarkan deklarasi simpul dan pointer di atas, maka prosedur

untuk menambah simpul di belakang senarai berantai bisa disusun seperti

berikut:

A B C D F

A B C D F

A B C D F

Procedure TAMBAH_BELAKANG (var Awal, Akhir : Simpul;

Elemen : char);

Var baru : simpul;

Begin

New (baru); baru^.info := elemen;

If awal = nil then{senarai masih kosong}

Awal := baru

Else

Akhir^.berikut := baru

Akhir := baru

Akhir^.beriku:=nil

End;

Menambah Simpul di tengah

Untuk menambah simpul baru ditengah, pertama kali ditenukan di mana

simpul baru akan ditambahkan pada poisi urutan simpul yang keberapa. Hal

ini dapat dilakukan dengan menempatkan simpul pointer bantu pada posisi

tertentu. Kemudian pointer yang ditunjuk oleh pointer simpul baru dibuat

sama dengan pada simpul yang ditunjuk oleh simpul bantu, selanjutnya

pointer pada simpul yang ditunjnuk oleh simpul bantu, selalnjutnya pointer

pada simpul yang ditunjuk pada simpul yang ditunjuk oleh simpul bantu

dibuat sama dengan baru. Perhatikan bahwa urutan ini tidak boleh dibalik.

Menghapus simpul

Operasi kedua yang akan dijelaskan adalah operasi menghapus simpul. Dalam

menghapus simpul simpul satu hal yang perlu diperhatikan, yaitu bahwa

simpul yang bisa dihapus adalah simpul yang berada sesuai simpul yang

ditunjuk oleh suatu pointer (dalam gambar adalah simpul yang berada di

sebelah kanan simpul yang ditunjuk oleh suatu pointer), kecuali untuk simpul

pertama. Dengan demikian, kita tidak bisa menghapus simpul yang ditunjuk

oleh suatu pointer atau simpul sebelumnya. Untuk jelasnya perhatikan

ilustrasi pada gambar berikut.

Awal Bantu Akhir

Jika senarai berntai adalah seperti diatas, maka kita hanya bisa menghapus

simpul yang berisi ‘A’ dan simpul yang beisi ‘D’ supaya senarai tetap bisa

dipertahankan. Memang kita bisa menghapus simpul yang berisi ‘C’, tetapi

senarai yang kita miliki akan menjadi terputus, karena akan lebih sulit untuk

menyambung lagi simpul ‘B’ dengan simpul ‘D’.

Untuk menghapus simpul pertama, maka pointer Bantu kita buat sama dengan

pointer Awal. Kemudian pointer Awal kita pindah ke simpul yang ditunjjuk

oleh pointer pada simpul yang ditunjuk oleh pointer Bantu kita dispose.

Adapun prosedur menghapus simpul pertama adalah sebagai berikut:

Procedure Hapus_pertama (var awal : simpul);

Var baru : simpul;

Begin

If awal = nil then {senerai masih kosong}

Writeln(‘Senarai masih kosong, tidak mungkin

dihapus’)

Else if awal^.berikut = nil then {senarai berisi

sebuah simpul }

Awal := nil

Else

Beginbantu := awal;

Awal :=bantu^.berikut;

Dispose(bantu);

End;

End;

Untuk menghapus simpul terakhir, tidak bisa dilakukan hanya dengan

mendispose simpul akhir. Karena dengan disposenya simpul akhir, maka

hanya simpul akhir saja yang dihapus, tetapi simpulnya masih tetap bisa

dimasup, karena masih ditunjuk oleh pointer dari simpul di sebeah kirinya.

Sehingga untuk bisa menghapus simpul terakhir, selain simpul akhir kita

hapus, maka pointer dari sebelah kirinya juga harus dijadikan nil. Program di

A B C D

bawah ini secara lengkap akan menyajikan cara menghapus simpul di

belakang atau di tengah.

Membaca Isi Senarai Berantai

Jika kita mempunyai senarai berantai seperti yang kita pelajari, maka dengan

cara biasa kita hanya bisa membaca isi simpul dimulai dari simpul paling kiri

sampai simpul paling kanan (membaca maju). Untuk membaca dari simpul

paling kanan ke simpul paling kiri, harus dilakukan dengan proses rekursif.

Pembacaan senarai berantai secara maju bisa dijelaskan sebagai berikut.

Pertama kali kita atur supaya pointer bantu menunjuk ke simpul yang ditunjuk

oleh pointer awal. Setelah isi simpul tsb dibaca, maka pointer bantu kita

gerakkan ke kanan untuk membaca simpul berikutnya. Proses ini kita ulang

sampai pointer bantu sama dengan pointer akhir. Ilustrasi embaca senarai

berantai dari kiri ke kanan dapat dilihat pada gambar di bawah ini.

Awal Bantu Akhir

C. PRAKTIK{Program tambah dan baca}

program senarai_berantai;

uses crt;

const garis =

‘------------------------------------------‘;

pesan = ‘Senerai berantai masih kosong’;

type simpul = ^data;

data = record

nama,

alamat : string;

berikut : simpul

end;

var awal,

akhir : simpul ;

A B C D

pilih : char;

cacah : integer;

{fungsi untuk memilih menu}

function menu : char;

var p : char;

begin

clrscr;

gotoxy(30,3); writeln(‘DAFTAR MENU PILIHAN’);

gotoxy(20,8); writeln(‘A. MENAMBAH SIMPUL BARU DI

AWAL SENARAI’);

gotoxy(20,9); writeln(‘B. MENAMBAH SIMPUL BARU DI

AKHIR SENARAI’);

gotoxy(20,10); writeln(‘C. MENCETAK ISI SENARAI’);

gotoxy(20,11); writeln(‘D. SELESAI’);

repeat

gotoxy(48,15); writeln(‘ ’:10);

gotoxy(30,20); writeln(‘PILIH SALAH SATU’);

p:= upcase (readkey);

until p in [‘A’ .. ‘D’];

menu :=p

end;

{fungsi alokasi simpul }

function simpul_baru : simpul;

var b : simpul;

begin

new(b);

with b^ do

begin

write(‘Nama :’); readln(nama);

write(‘Alamat : ‘);readln(alamat);

berikut :=nil

end;

simpul_baru:=b

end;

{fungsi tambah simpul baru di awal senarai}

procedure tambah_awal (n:integer);

var baru : simpul;

begin

if n <> o then

begin

writeln(‘menambah simpul baru di awal senarai’);

writeln(copy(garis,1,45))

end;

writeln;

baru:=simpul_baru;

if awal = nil then

akhir :=baru

else baru^.berikut := awal;

awal :=baru;

end;

{fungsi tambah simpul baru di akhir senarai}

procedure tambah_akhir (n:integer);

var baru : simpul;

begin

clrscr;

if n <> o then

begin

writeln(‘Menambah simpul baru di akhir senarai’);

writeln(copy(garis,1,46))

end;

writeln;

baru:=simpul_baru;

if awal = nil then

awal := baru

else

akhir^.berikut := baru

akhir:=baru;

end;

{fungsi tambah simpul baru pada posisi tertentu}

procecdure tambah_tengah)n:integer);

var baru, bantu : simpul;

posisi,i:integer;

begin

writeln(‘Menambah simpul baru di tengah pada posisi

berapa ‘);

writeln(garis); writeln;

write(‘senarai berantai berisi : ‘, cacah:2,’

simpul’);

repeat

gotoxy(52,5);

writeln(‘ ‘);

gotoxy(1,5);

write(‘simpul baru ditempatkan sebagai nomer

berapa : ‘);

readln(posisi);

until posisi in [1..cacah+1];

if posisi = 1 then tambah_awal(0)

else if posisi = cacah+1 then tambah_akhir(0)

else begin

writeln;

baru:=simpul_baru;

bantu:=awal;

for i:=1 to posisi – 2 do

bantu:=bantu^.berikut;

baru^.berikut:=bantu^.berikut;

bantu^.berikut:=baru

end;

end;

{proceedure hapus depan}

procedure hap[us_depan;

var bantu :simpul;

begin

if awal = nil; then

writeln(‘senarai masih kosong’);

else

bantu:= awal;

awal:=bantu^.berikut;

bantu^.berikut:=nil

end;

{prosedur mencari simpul tertentu}

proceedure cari_simpul;

var bantu,

bantu : simpul;

i:integer;

begin

i:=1;

writeln(‘mencari simpul tertentu’);

if awal = nil then writeln(‘senarai masih kosong’);

else

writeln(‘mencari simpul tertentu’);

bantu:=awal;

if baru^.no_mhs = bantu^.no_mhs then begin

writeln(‘no mahasiswa :’, bantu^.no_mhs:5);

writeln(‘nama : ‘, bantu^.nama);

writeln(‘alamat : ‘,bantu^.alamat);

end;

else

writeln(‘mahasiswa dengan no ‘,baru^.no_mhs:5,’

tidak ada’);

end;

{prosedu baca isi senarai}

procedure baca_senarai;

var bantu:simpul;

i:integer;

begin

i:=1;

writeln(‘Membaca isi senarai’);

writeln(‘teken <enter> untuk kembali ke menu’);

writeln(copy(garis,1,42));

writeln;

if bantu = nil then

writeln(‘Data masih kosong’);

else

bantu := awal;

while bantu <> nil do

begin

writeln(‘simpul : ‘, i:3,’ - nama :

‘,bantu^.nama);

writeln(‘ ‘:17,’ alamat : ‘,bantu^.alamat);

bantu:=bantu^.berikut;

inc(i)

end;

repeat until keypressed

end;

{program utama}

cacah:=0;

awal:=nil;

akhir:=nil;

repeat

pilih:=menu;

clrscr;

case pilih of

‘A’ :tambah_awal(1);

‘B’ : tambah_akhir(1);

‘C’ :baca_senarai;

end;

if pilih in[‘A’,’B’] then inc(cacah)

until pilih = ‘D’

end.

Cobalah untuk simpul berikut:

Nomor Nama Alamat

0001 Dian-1 Jogja-1

0002 Dian-2 Jogja-2

0003 Dian-3 Jogja-3

0004 Dian-4 Jogja-4

0005 Dian-5 Jogja-5

1. Jelaskan perbedaan tambah simpul di awal, di akhir dan di tengah pada suatu

senarai dan bagaimana ilustrasinya.

2. Jelaskan perbedaan hapus simpul diawal, diakhir dan ditengah pada suatu

senarai dan bagaimana ilustrasinya.

D. TUGAS

Pada program diatas tambahlah procedure

1. Hapus simpul ditengah dan penghapusan simpul bisa diatur pada

posisi berapa simpul tersebut dihapus.

2. Hapus simpul diakhir.

MODUL V

ANTRIAN (QUEUE)

A. MAKSUD DAN TUJUAN

1. MAKSUD

Memberikan pemahaman tentang tipe data antrian beserta operasinya.

2. TUJUAN

Agar mahasiswa menggunakan tipe data antrian dengan melakukan operasi

menambah dan menghapus elemen.

B. TEORI

Antrian (queue) sering digunakan untuk mensimulasikan keadaan pada

dunia nyata. Antrian adalah suatu kumpulan data yang penambahan elemen hanya

bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan

penghapusan (pengambilan elemen) dilakukan lewat ujung lain (disebut dengan

sisi depan atau front).

Prinsip pada antrtian adalah FIFO (First In First Out) atau’masuk pertama

keluar pertama”. Dengan kata lain, urutan keluar elemen akan sama dengan

urutan masuknya.

Dalam antrian dikenal 2 operasi dasar yaitu menambah elemen baru yang

akan ditempatkan di belakang antrian dan menghapus elemen yang terletak di

depan antrian. Disamping itu juga sering dilihat apakah antrian mempunyai isi

atau dalam keadaan kosong.

Implementasi Antrian dengan Larik

Untuk menyajikan antrian menggunakan larik, maka deklarasi antrian adalah:

Const max_elemen = 100;

Type antri = array [1..max_elemen] of integer;

Var

Antrian : antri;

Depan, belakang: integer;

Di bawah ini disajikan gambar antrian dengan menggunakan larik. Antrian

mempunyai 6 elemen, yaitu A, B, C, D, E, dan F. Elemen A terletak dibagian

depan antrian dan elemen F terletak di belakang antrrian. Dengan demikian, jika

ada elemen baru yang akan masuk ia akan diletakkan disebelah kanan F. Jika ada

elemen yang akan dihapus maka A akan dihapus lebih dulu.

Implementasi Antrian dengan Senarai Berantai

Jika dilihat pada penambahan dan penghapusan elemen pada antrian,

maka antrian sebenarnya juga merupakan bentuk khusus dari suatu senarai

berantai. Dengan demikian apa yang telah dipelajari pada senarai berantai bisa

digunakan pada antrian.

Untuk memanipulasi sebuah antrian akan digunakan 2 perubah yang

menyimpan posisi elemen paling depan dan elemen yang paling belakang.

Dengan cara yang sama, apabila ingin diimplementasikan antrtaian menggunakan

senarai berantai maka digunakan 2 pointer yang diletakkan pada elemen paling

depan (kepala) dan elemen paling belakang (ekor). Dalam hal ini bisa digunakan

senarai bernatai tunggal atau senarai berantai ganda baik yang bisa memutar atau

tidak. Disisni akan digunakan senarai berantai tunggal berkepala dan memutar,

sehingga deklarasi simpul sebagai berikut:

Type antri = ^simpul;

Simpul = record

Info : char;

Berikut : antrti;

End;

Var kepala, ekor : antri;

Pada waktu inisialisasi bentuk dari simpul kepala sebagai berikut:

Kepala

Ekor

Dengan memperhatikan gambar diatas maka prosedur inisialisasi adalah

Procedure init_antrian (var kepala, ekor : antri);

Begin

New(kepala);

Kepala^.info:=chr(0);

Kepala^.berikut:=kepala;

Ekor := kepala;

End;

C. PRAKTIK

1. Cobalah program dibawah ini, amati untuk beberapa masukan yang berbeda.

Program queue_contoh;

Uses crt;

Const max = 10;

Type antri = array [1..max] of char;

Var antrian:antri;

Depan, belakang, pilih, i : integer;

Elemen :char;

Function kosong (q:antri) :boolean;

Begin

Kosong:=(depan=belakang);

End;

Procedure tambah(var antrian:antri; x:char);

Begin

{menambah elemen baru}

if belakang = max then belakang := 1

else

belakang := belakang-1;

if not (kosong(antrian)) then

begin

antrian[belakang] := x;

write(‘hasil antrian = ‘,x)

end;

else

{antrian penuh}

begin

write(‘antrian penuh’);

repeat

until keypressed;

write(‘ ‘:30);

belakang:=belakang-1;

if belakang=0 then belakang:= max;

end;

End;

Begin {program utama}

Clrscr;

Depan:=0;

Belakang:=0;

Writeln(;menambah elemen’);

I:=1;

Write(‘isikan elemen =’);

Readln(elemen);

Tambah(antrian,elemen);

readln

End.

2. Modifikasi program diatas sehingga bisa menerima masukkan dalam bentuk

string.

Contoh input : stmik el rahma

Hasil akhir : stmik el rahma

3. Diberikan suatu fungsi untuk menghapus elemen dari antrian sebagai berikut :

Function hapus(var antrian:antri):char;

Begin

If depan = max then depan:=1

Else

Begin

Depan:=depan+1;

Hapus:=antrian[depan]

End;

End;

D. TUGAS

Implementasikan program queue_contoh diatas dengan menggunakan senarai

berantai.

MODUL VI

POHON (TREE)

A. MAKSUD DAN TUJUAN

1. MAKSUD

Memberikan pemahaman tentang tipe data pohon (khususnya pohon biner)

serta sifat-sifat dari pohon biner.

2. TUJUAN

Agar mahasiswa mampu membuat pohon biner, mencari data dan membaca data

dengan cara inorder, preorder,dan postorder.

B. TEORI

Pohon (tree) merupakan struktur data tak linier yang mempunyai sifat-

sifat dan ciri-ciri khusus. Struktur ini biasanya digunakan untuk menggambarkan

huubungan yang bersifat hirarkis antara lemen-elemen yang ada.

Pohon biner (binary tree) bisa didefinisikan sebagai suatu kumpulan

simpul yang mungkin kosong atau mempunyai akar dan dua sub pohon yang

saling terpisah yang disebut dengan subpohon kiri (left subtree) dan sub pohon

kanan (right subtree). Sub pohohn juga disebut dengan cabang. Karakteristik yang

dimiliki oleh pohon biner adalah bahwa setiap simpul paling banyak hanya

mempunyai dua bauh anak. Dengan kata lain, derajat tertinggi dari setiap simpul

dalam pohon adalah dua. Karakteristik yang lain adalah pohon biner

dimungkinkan tidak mempunyai simpul.

Mendeklarasikan Struktur Pohon Biner

Setiap simpul pada pohon terdiri 2 komponen utama:

1. data

2. Pointer yang menunjuk ke anak

Pointer anak ada 2 macam, yaitu:

1. Pointer yang menunjuk ke anak kiri

2. pointer yang menunjuk ke anak kanan

Sebuah contoh struktur untuk menyatakan simpul pohon biner dapat dilihat

dibawah ini:

Type

Tipedata = char;

Pointerpohon = ^simpulpohon

Simpulpohon = record

Data : tipedata;

Kiri,kanan : pointerpohon

End;

Menampilkan Data

Ada berbagai cara untuk menampilkan data pada setiap simpul. Pada pohon biner

terdapat cara yang disebut preorder, inorder, dan postorder. Cara ini bertumpu

pada cara mengunjungi setiap simpul.

Dengan cara inorder (LNR = Left Node Right), data akan ditampilkan dengan

cara urut naik. Kunjungan dilakukan dari posisi kiri simpul. Bila posisi kiri tidak

memiliki anak, maka isi simpul ditampilkan. Kemudian dilanjutkan dengan

kunjungan di posisi kanan.

Implementasi dari metode ini dapat dilihat sebagai berikut :

Procedure inorder (pointerakar : pointerpohon);

Begin

If pointerakar <> nil then

Begin

With pointerakar^ do

Begin

Inoder(kiri);

If data <> ‘0’ then write (data)

Inorder (kanan)

End;

End;

End;

Dengan cara preorder prosesnya dilakukan dengan cara NLR (Node Left Right).

Pada setiap simpul yang dikunjungi, data pada simpul akan ditampilkan terlebih

dahulu, kemudian mengarah ke simpul kiri dan akhirnya ke simpul kanan.

Implementasi dari metode ini dapat dilihat sebagai berikut :

Procedure preorder(pointerakar : pointerpohon);

Begin

If pointerakar <> nil then

Begin

With pointerakar^ do

Begin

If data <> ‘0’ then write(data);

Inorder(kiri);

Inorder(kanan)

End;

End;

End;

Dengan cara postorder, prosesnya dilakukan secara LNR (Left Node Right). Pada

setiap simpul yang dikunjnjungi, data pada simpul akan ditampilkan terlebih

dahulu kemudian mengarah ke simpul kiri dan akhirnya ke simpul kanan.

Implementasi dari metode ini dapat dilihat sebagai berikut :

Procedure postorder(pointerakar : pointerpohon);

Begin

If pointerakar <> nil then

Begin

With pointerakar^ do

Begin

Inorder(kiri);

Inorder(kanan)

If data <> ‘0’ then write(data);

End;

End;

End;

Selain ketiga metode diatas, masih ada satu metode yaitu metode levelorder.

Dalam hal ini akan ditampilkan simpul dari tingkat 1 (akar) diteruskan dengan

simpul-simpul pada tingkat 2,3, dst. Untuk mengimplementasikan prosedurnya

maka digunakan struktur antrian.

C. PRAKTIK

1. Cobalah program dibawah ini, dan amati untuk beberapa masukan yang

berbeda.

Program pohon;

Uses crt;

Type tipedata=char;

Pointerpohon=^simpulpohon;

Simpulpohon=record

Data:tipedata;

Kiri, kanan:pointerpohon;

End;

Var pointerakar:pointerpohon;

Entri:tipedata;

Procedure

sisipkankepohon(varp[ointerakar:pointerpohon;entri:tip

edata);

Begin

If pointerakar=nil then

Begin

New(pointerakar);

With pointerakar^ do

Begin

Data:=entri;

Kiri:=nil;

Kanan:=nil;

End;

End;

Else

If entri<pointerakar^.data then

Sisipkankepohon(pointerakar^.kiri,entri)

Else

Sisipkankepohon(pointerakar^.kanan,entri)

End;

Procedure inorder(pointerakar:pointerpohon);

Begin

If pointerakar <> nil then

Begin

With pointerakar^ do

Begin

Inorder(kiri);

If data <> ‘0’ then write(data);

Inorder(kanan);

End

End;

End;

Begin{program utama}

Clrscr;

Pointerakar:=nil;

Writeln(‘buat pohon’);

Repeat

Read(entri);

Sisipkankepohon(pointerakar,entri);

Until entrti=’0’;

Writeln(;penulisan inorder’);

Inorder(pointerakar);

Writeln;

Readln;

2. Lengkapilah program diatas sehingga bisa digunakan untuk mencek sebuah

karakter ada di pohon atau tidak. (Petunjuk : gunakan fungsi di bawah ini)

Function

cari(pointerakar:pointerpohon;entri:tipedata):pointerp

ohon;

Begin

if pointerakar = nil then cari := nil

else

with pointerakar^ do

if entri = data then cari := pointerakar

else

if entri < data then cari := cari(kiri,entri)

else

cari:=cari(kanan,entrri);

end;

D. TUGAS

Buatlah prosedur untuk menampilkan data pada pohon secara preorder dan

postorder.

MODUL VII

PENGURUTAN DATA NUMERIS (SORTING)

A. MAKSUD DAN TUJUAN

1. MAKSUD

Pengenalan proses pengurutan data numeris (sorting)

2. TUJUAN

Agar praktikan bisa memahami proses pengurutan data numeris dan bisa

memanfaatkan pada penerapannya.

B. TEORI

Secara umum ada dua macam model/bentuk urutan data numeris, yaitu

model uruitan membesar (ascending) dan model urutan mengecil yaitu

descending. Untuk melakukan proses pengurutan data numeris ada beberapa

metode, misal metode seleksi, metode penyisipan langsung dan metode

gelembung.

Cara kerja metode seleksi didasarkan pada pencarian elemen dengan

nilai terkecil, kemudian dilakukan penukaran dengan elemen ke 1. Secara

ssingkat, metode ini bisa dijelaskan sebagai berikut. Pada langkah pertama, dicari

data terkecil tersebut kita tukar dengan data pertama. Dengan demikian, data

pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Pada

langkah kedua, data terkecil kita cari mulai data kedua. Demikian seterusnya

sampai seluruh vektor dalam keadaan terurutkan. Untuk lebih memperjelas proses

pengurtan dengan metode seleksi, berrikut disajikan contoh metode ini.

Iterasi ke A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

I=1, lok=3

I=2, lok=9

I=3, lok=3

I=4, lok=8

I=5, lok=8

I=6, lok=7

I=7, lok=7

I=9, lok=9

23

12

12

12

12

12

12

12

45

45

16

16

16

16

16

19

12

23

23

23

23

23

23

23

24

24

24

23

23

23

23

23

56

56

56

56

56

24

24

24

34

34

34

34

34

34

27

27

27

27

27

27

27

27

34

34

23

23

23

23

23

56

56

56

16

16

45

45

45

45

45

45

Akhir 12 16 23 23 24 27 34 45

Metode ini secara garis besar merupakan kebalikan dari metode penyisipan

langsung. Dalam setiap langkah pada metode penyisipan langsung kita hanya

memperhatikan satu elemen dari sumber dan semua elemen dari larik tujuan

untuk menentukan posisinya yang tepat. Sehingga sering disebut dengan one

source multiple destinations. Dalam metode seleksi terjadi sebaliknya, yakni kita

memperhatikan semua elemen dalam larik sumber untuk menentukan elemen

terkecil yang akan kita tempatkan pada tujuan, sehingga sering disebut dengan

multiple source one destination.

C. PRAKTIK

Program sorting1;

Uses crt;

Tuype larik = array [1..100] of real;

Var vektor:larik;

I,cacah:integer;

Bantu:real;

Procedure sort_sleksi(var x : larik;n:integer);

Var i,j,lokasi:integer;

Bantu:real;

Begin

For i:=1 to n do

Begin

Lokasi := i;

For j:= i+1 to n do

If x[lokasi]>x[j] then

Lokasi:=j;

Bantu:=x[i];

X[i]:=x[lokasi];

X[lokasi]:=bantu

End

End;

Procedure cetak_larik(x:larik;n:integer);

Var i:integer;

Begin

For i:=1 to n do

Begin

Writeln(x[i]:8:2);

If i mod 8 = 0 then

Writeln;

End

End;

Begin

Clrscr;

Writeln(mensorttir bilangan dengan metode seleksi’);

Writeln(cacah data :’);

Readln(cacah);

Writeln;

Writeln(‘masukan data 8 data per baris;);

Bantu:=1;

For i:=1 to cacah do

Begin

Read (vektor[i]);

Goptoxy(wherex+(i mod 8)*8, wherey-i);

Id i mod 8 = 0 then

Writeln;

End;

Clrscr;

Writeln(‘ data sebelum disorttir’);

Writeln;

Ctak_larik(vektor,cacah);

Writeln(writeln;

Sort_seleksi(vektor,cacah);

Writeln(‘data setelah disoprtir’);

Writel;n;

Cetak_larik(vektor,cacah);

End.

Pertanyaan:

1. Ujialah dengan data yang telah tersedia pada ilustrasi di tas.

2. Model urutan di atas diganti

D. TUGAS

Pada program di atas procedure metode seleksi gantilah

1. dengan metode penyisipan langsung.

2. dengan metode gelembung.

MODUL VIII

PENCARIAN (SEARCHING)

A. MAKSUD DAN TUJUAN

1. MAKSUD

Memberikan pemahaman tentang cara pencarian data dalam vektor terurut

maupun vektor tidak terurut.

2. TUJUAN

Agar mahasiswa mampu mecari data dalam vektor dengan metode pencarian

berurutan (sequential searching) dan metode pencarian biner (binery searching).

B. TEORI

Pencarian data sering juga disebut dengan table look up atau storage and rerievel

information adalah suatu proses untuk mengumpulkan sejumlah informasi di

pengingat komputer dan mencari kembali informasi yang diperlukan secepat

mungkin.

Pencarian data bisa dikelompokkan 2 cara yaitu pencarian internal dan

pencarian eksternal. Efisiensi pencarian data dipengaruhi struktur data yang

digunakan untuk menyimpan data. Dalam hal ini akan digunakan struktur data

vektor dengan deklarasi tipe array dimensi 1. Adapun vektor yang digunakan

mempunyai deklarasi sebagai berikut :

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

SEQUENTIAL SEARCHING

Metode yang paling sederhana dari sejumlah pencarian adalah metode pencartian

berurutan (sequential searching). Secara garus besar metode ini bisa dijelaskan

sebagai berikut. Dari vektor yang diketahui, data yang dicari dibandingkan satu

per satu sampai data tersebut ditemukan atau tidak. Pada saat data yang dicari

sudah ketemu maka proses pencarian dihentikan. Tetapi jika tidak, pencarian akan

diteruskan smpai seluruh data dibandingkan.

Implementasi dari metode ini adalah:

Procedure cari_vektor_urut (var ada : boolean; var n,

posisi : integer; var A : larik: data : integer);

Var i : integer;

Begin

{dianggap tidak ada data}

ada := false;

for i := 1 to n do

if A[i] = data then

begin

posisi := i;

ada := true;

exit;

end;

if not ada then

{data yang dicari tidak ketemu, sisipkan ke vektor}

begin

inc(n);

a[n] := data;

end;

End;

PENCARIAN BINER

Metode pencarian biner yang dapat dijelaskan sebagai berikut. Setelah yang

diketahui diurutkan, vektor dibagi menjadi 2 sub vektor yang mempunyai jumlah

elemen sama. Kemudian data dibandingkan dengan data terakhir dari sub vektor

pertama. Jika data yang dicari lebih kecil, pencarian diteruskan pada su vektor

pertama dengan terlebih dahulu membagi dua sub vektor tersebut. Tetapi jika data

yang dicari lebih besar dari data terakhir dari sub vektor pertama berarti data

terletak pada sub vektor kedua. Dengan demikian pencarian dilakukan pada sub

vektor kedua. Proses di atas diulang sampai data yang dicari ketemu atau tidak

ketemu.

C. PRAKTIK

1. Buatlah program untuk mencari elemen / data pada suatu vektor yang sudah terurut

dengan menggunakan procedure car_vektor_urut di atas.

2. Buatlah program untuk mencari data / elemen pada suatu vektor yang belum

terurut (dengan pencarian biner)

D. TUGAS

Bandingkan kedua metode diatas. Metode mana yang lebih efisien? Buktikan dalam

bentuk program