Struktur data Materi dan Tugas ~ Only Studying

MODUL PRAKTIKUM

STRUKTUR DATA

MODUL I

TUMPUKAN (STACK)

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.

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;

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.

Modifikasi program diatas untuk menambahkan sebuah karakter dalam tumpukan.

Contoh input : STMIK El Rahma

Tambahan karakter : q

Hasil akhir : q amhaR lE KIMTS

TUGAS

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.

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

MAKSUD DAN TUJUAN

MAKSUD

Memberikan pemahaman tentang tipe data pointer beserta operasinya.

TUJUAN

Agar mahasiswa dapat menggunakan tipe data pointer dengan melakukan operasi mengkopi pointer, mengkopi isi simpul, dan menghapus pointer.

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.

PRAKTIK

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)

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

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

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.

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;

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

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

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;

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

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’);

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

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

MAKSUD DAN TUJUAN

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.

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.

TEORI

Awal

Medan penyampung dari simpul

Medan informasi dari simpul

Menambah simpul

Type simpul = ^ data;

Data = reecord

Info : char;

Berikut:simpul;

End;

Var elemen : char;

Awal, akhir, baru : simpul;

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.

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

Menghapus simpul

Awal Bantu Akhir

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;

Membaca Isi Senarai Berantai

Awal Bantu Akhir

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’);

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;

{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

Jelaskan perbedaan tambah simpul di awal, di akhir dan di tengah pada suatu senarai dan bagaimana ilustrasinya.
Jelaskan perbedaan hapus simpul diawal, diakhir dan ditengah pada suatu senarai dan bagaimana ilustrasinya.

TUGAS

Pada program diatas tambahlah procedure

Hapus simpul ditengah dan penghapusan simpul bisa diatur pada posisi berapa simpul tersebut dihapus.
Hapus simpul diakhir.

MODUL V

ANTRIAN (QUEUE)

A. MAKSUD DAN TUJUAN

MAKSUD

Memberikan pemahaman tentang tipe data antrian beserta operasinya.

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

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.

Modifikasi program diatas sehingga bisa menerima masukkan dalam bentuk string.

Contoh input : stmik el rahma

Hasil akhir : stmik el rahma

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;

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;

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;

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;

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

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:tipedata);

Begin

If pointerakar=nil then

Begin

New(pointerakar);

With pointerakar^ do

Begin

Data:=entri;

Kiri:=nil;

Kanan:=nil;

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;

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;

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):pointerpohon;

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:

Ujialah dengan data yang telah tersedia pada ilustrasi di tas.
Model urutan di atas diganti

D. TUGAS

Pada program di atas procedure metode seleksi gantilah

dengan metode penyisipan langsung.
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

Only Studying

Monday, October 17, 2016

Struktur data Materi dan Tugas

0 comments:

Post a Comment

Popular Posts

Daftar Judul

Penerjemah

Tentang Aku