BAB I 1. Pendahuluan. Struktur data adalah cara menyimpan atau merepresentasikan data di dalam komputer agar bisa dipakai secara efisien Sedangkan data adalah representasi dari fakta dunia nyata. Fakta atau keterangan tentang kenyataan yang disimpan, direkam atau direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau symbol. Secara garis besar type data dapat dikategorikan menjadi : 1. Type data sederhana a. Type data sederhana tunggal, misalnya Integer, real, boolean dan karakter b. Type data sederhana majemuk, misalnya String 2. Struktur Data, meliputi a. Struktur data sederhana, misalnya array dan record b. Struktur data majemuk, yang terdiri dari Linier : Stack, Queue, serta List dan Multilist Non Linier : Pohon Biner dan Graph Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. Struktur data yang ″standar″ yang biasanya digunakan dibidang informatika adalah : List linier (Linked List) dan variasinya Multilist Stack (Tumpukan) Queue (Antrian) Tree ( Pohon ) Graph ( Graf ) 2. ARRAY dan SET A. ARRAY (LARIK) Array (Larik) adalah tipe terstruktur yang mempunyai komponen dalam jumlah yang tetap dan setiap komponen mempunyai tipe data yang sama. Posisi masing-masing dalam larik dinyatakan sebagai index. Bentuk umum dari deklarasi tipe larik adalah : var pengenal = array [tipe_index] of tipe;
Keterangan : pengenal : nama variabel. tipe_index : jumlah larik. tipe : tipe data. Parameter tipe_index menentukan banyaknya komponen larik tersebut. Parameter ini boleh berupa sembarang tipe ordinal kecuali longint dan subjangkauan longint. Contoh : Var larik1 = array[1..5] of char; larik2 = array[1..5,1..5] of string; larik3 = array[1..5,1..5,1..5] of integer; Dari contoh diatas ditampilkan beberapa cara pendeklarasian larik (array). Variabel larik1 adalah larik dengan satu dimensi, larik2 adalah larik dengan dua dimensi atau dimensi banyak, demikian juga dengan larik3.
1
Latihan-latihan : Var nil
: array[1..3] of integer;
Begin nil[1] := 105; nil[2] := 202; nil[3] := 727; writeln (nil[1]); writeln (nil[2]); writeln (nil[3]); End. Var nama
: array[1..3] of string;
Begin nama[1] nama[2] nama[3] writeln writeln writeln End.
:= ‘BUDI’; := ‘IWAN’; := ‘TUTY’; (‘Nama 1 : ’,nama[1]); (‘Nama 2 : ’,nama[2]); (‘Nama 3 : ’,nama[3]);
Const awal = 1; akhir = 5; Var nim : array[awal..akhir] of string; nama : array[awal..akhir] of string; n : integer; Begin Writeln (‘Isi NIM dan Nama dengan Array’); For n := 1 to 5 do Begin Write (‘NIM - ’,n,’ : ‘); readln(nim[n]); Write (‘Nama - ’,n,’ : ‘); readln(nama[n]); Writeln; End; Writeln; Writeln (‘Hasil dari inputan adalah :’); For n := 1 to 5 do Begin Writeln (‘NIM - ’,n,’ : ‘,nim[n]); Writeln (‘Nama - ’,n,’ : ‘,nama[n]); Writeln; End; End.
2
Var nilai : array[1..5] of integer; Jm, rata : real; Begin Writeln (‘Menghitung rata-rata 5 buah nilai’); Write (‘nilai1 = ‘); readln(nilai[1]); Write (‘nilai2 = ‘); readln(nilai[2]); Write (‘nilai3 = ‘); readln(nilai[3]); Write (‘nilai4 = ‘); readln(nilai[4]); Write (‘nilai5 = ‘); readln(nilai[5]); Jm := nilai[1]+nilai[2]+nilai[3]+nilai[4]+nilai[5]; Rata := jm / 5; Writeln; Writeln (‘Jumlah = ‘,jm:9:2); Writeln (‘Rata-rata = ‘,rata:9:2); End. Var Dim1 : array[1..3] of integer; Dim2 : array[1..3,1..3] of integer; Dim3 : array[1..3,1..3,1..3] of integer; i,j,k : integer; Begin {input elemen array} For i := 1 to 3 do Dim1[i] := 2 * i – 1; For i := 1 to 3 do Begin For j := 1 to 3 do Dim2[i,j] := 4 * i – j; End; For i := 1 to 3 do Begin For j := 1 to 3 do Begin For k := 1 to 3 do Dim3[i,j,k] := j * k – i; End; End; {cetak elemen array} for i := 1 to 3 do Begin Writeln; Writeln (‘1 dimensi[‘,i,’] = ’,dim1[i]); For j := 1 to 3 do Begin Writeln (‘2 dimensi[‘,i,’,’,j,’] = ’,dim2[I,j]); For k := 1 to 3 do Writeln (‘3 dimensi[‘,i,’,’,j,’,’,k,’]=’,dim2[i,j,k]); End; End; End. 3
B. SET Set adalah kumpulan objek yang mempunyai tipe data sama dalam urutan yang tidak diperhatikan. Setiap elemen dalam set disebut dengan anggota atau elemen set. Tipe data dari anggota set dapat berupa nilai skalar atau himpunan bagian dari tipe data lain yang ada dalam pascal. Bentuk umum dari deklarasi set adalah : Type pengenal = set of tipe;
Keterangan : pengenal tipe
: nama variabel atau nama type. : type data buatan sendiri maupun bawaan pascal.
Pendeklarasian set tidak hanya dapat dilakukan pada Type saja tapi terkadang juga di deklarasikan pada bagian var (deklarasi variabel). Contoh : Type hari = (‘senin’,’selasa’,’rabu’,’kamis’,’jumat’, ’sabtu’,’minggu’); HariDlmMgg = set of hari; Bilangan = set of 1..10; Karakter = set of char; Setiap tipe yang dideklarasikan di bagian type, untuk dapat digunakan di dalam program harus di deklarasikan di bagian variabel (var) yang mengarah ke nama tipe yang telah dibentuk. Contoh : Var namahari : HariDlmMgg; Angka : Bilangan; Huruf : Karakter; Type Tvokal = set of char; Var Vokal : Tvokal; Kar : char; Begin Vokal := [‘A’,’I’,’U’,’E’,’O’]; Write (‘Ketik sebuah karakter dan tekan Enter: ‘); Readln (Kar); If Kar in Vokal then Writeln (‘Huruf Vokal’) Else Writeln (‘Huruf Konsonan’); End.
4
type hari=(senin,selasa,rabu,kamis,jumat,sabtu,minggu); namahari = set of hari; var harian,harikerja,harilibur : namahari; nhari : array[hari] of string; i : hari; Begin nhari[senin] := 'senin'; nhari[selasa] := 'selasa'; nhari[rabu] := 'rabu'; nhari[kamis] := 'kamis'; nhari[jumat] := 'jumat'; nhari[sabtu] := 'sabtu'; nhari[minggu] := 'minggu'; harian :=[senin,selasa,rabu,kamis,jumat,sabtu,minggu]; harikerja := [senin,selasa,rabu,kamis]; harilibur := harian - harikerja; writeln ('NAMA HARI KERJA'); for i := senin to minggu do begin if i in harikerja then write (nhari[i],' - '); end; writeln; writeln; writeln ('NAMA HARI LIBUR'); for i := senin to minggu do begin if i in harilibur then write (nhari[i],' - ' ); end; End.
5
BAB II RECORD dan ITERASI A. RECORD Record adalah kumpulan elemen-elemen dalam pascal dimana setiap elemen dapat memiliki tipe data yang saling berbeda. Cara mengakses record mirip dengan cara mengakses array, perbedaannya adalah jika pada array untuk mengakses dengan cara menyebut nama array disertai dengan nomor indeks, maka pada record adalah dengan menyebut nama record disertai dengan nama field (elemen) yang akan diakses. Bentuk umum pendeklarasian record : Type namarec = Var1 Var2 Varn End; Var nama_var :
record : tipe; : tipe; : tipe; namarec;
Keterangan : namarec : nama record. var1,var2,varn : nama variable pada type nama_var : nama variable untuk tipe namarec. tipe : tipe data. Bentuk umum pemanggilan record : Begin nama_var.var1 := . . . . nama_var.var2 := . . . . nama_var.varn := . . . . With nama_var Begin var1 := . . var2 := . . varn := . . End; End.
Cara pertama
do . . . . . .
Cara kedua
Latihan : Type data = record No : integer; Nama : string; End; Var datamhs : data; Begin Datamhs.no := 1; Datamhs.nama := ‘Budi’; Writeln (‘Nomor : ‘,datamhs.no); Writeln (‘Nama : ‘,datamhs.nama); End.
6
type matkul = record id : integer; namamk : string; end; data = record nim : string; nama : string; dtmk : matkul; end; var datamhs : array[1..20] of data; n,i : integer; Jwb : char; begin n := 0; Jwb := 'Y'; writeln ('Inputkan data Mahasiswa'); writeln; while Jwb = 'Y' do begin n := n + 1; with datamhs[n] do begin writeln ('Data ke - ',n,' :'); write ('NIM : '); readln(nim); write ('Nama : '); readln(nama); write ('kode MK : '); readln(dtmk.id); write ('Nama MK : '); readln(dtmk.namamk); write ('Tambah lagi [Y/N] ? : '); readln (Jwb); writeln; end; end; clrscr; writeln ('NIM','Nama Mhs':10,'Kode MK':10,'Nama MK':10); for i := 1 to n do begin with datamhs[i] do writeln (nim,nama:10,dtmk.id:10,dtmk.namamk:10); end; end.
7
B. ITERASI Iterasi merupakan proses pengulangan suatu statemen atau blok statemen sebanyak jumlah tertentu yang diberikan. Dalam pascal proses iterasi dapat dilakukan dengan memanfaatkan perintah for … do, repeat … until, while … do. Bentuk umum penulisan : For namavar := a to z do Repeat . . . . until namavar > z; while namavar <= z do
Keterangan : namavar a z
: nama variable. : nilai awal perulangan. : nilai akhir tujuan perulangan.
Latihan : var n : integer; k : string; begin k := ''; for n := 1 to 10 do begin k := k + '*'; writeln (k); end; end. var n,i : integer; k : string; begin k := '*'; i := 5; while i >= 1 do begin for n := 1 to i do write (k); i := i - 1; writeln; end; readln; end.
8
var n : word; function faktorial(n : word) : word; var i : integer; xfaktorial : word; begin xfaktorial := n; if n = 0 then faktorial := 1 else begin for i := n - 1 downto 1 do xfaktorial := xfaktorial * i; faktorial := xfaktorial; end; end; begin clrscr; write ('Bil. int. positif untuk dicari faktorialnya : '); readln (n); writeln; writeln ('faktorial dari ',n,' adalah ',faktorial(n)); end.
9
BAB III REKURSI Rekursi adalah sebuah proses yang bisa memanggil diri sendiri. Dalam rekursi sebenarnya terkandung pengertian prosedur atau fungsi. Perbedaannya adalah bahwa rekursi bisa memanggil dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi. Dalam prosedur atau fungsi, pemanggilan ke dirinya sendiri bisa berarti proses berulang yang tidak bisa diketahui kapan akan berakhir. Dalam pemakaian sehari-hari, rekursi merupakan teknik pemrograman yang berdayaguna untuk digunakan pada pekerjaan pemrograman dengan mengekspresikannya kedalam suku-suku dari program lain dengan menambahkan langkah-langkah sejenis. Contoh bentuk Rekursi : Function namaFunc (n : integer) : integer; Begin Nama function If n = 0 then namaFunc := 1 Else namaFunc := n * namaFunc(N – 1); End; Pemanggilan nama function di dalam tubuh sendiri. Karena function memanggil diri sendiri di dalam tubuh function mengakibatkan proses akan terus berulang sampai pernyataan yang ada didalam blok program itu sendiri terpenuhi. var input : integer; function jumgenap (n : integer) : integer; begin if n < 2 then jumgenap := 0 //pemberian nilai nol untuk n < 2 else if (n mod 2) = 0 then jumgenap := n + jumgenap(n-1) //penjumlahan bil. genap else jumgenap := 0 + jumgenap(n-1); //penjumlahan bil. ganjil end; begin clrscr; writeln ('Program menjumlah bilangan genap'); write ('Batas nilai yang ingin dihitung : '); readln (input); writeln; writeln ('Jumlah Bilangan Genap antara 0-',input, ' = ',jumgenap(input)); readln; end.
10
var kalimat : string; procedure karakter(kal : string); var n : integer; begin n := length(kal); writeln (kal[n]); if n >= 1 then begin karakter(copy(kal,1,n-1)); end; end; begin clrscr; writeln ('Pembalik Kalimat Secara Vertikal'); writeln ('Masukkan Kalimat : '); readln (kalimat); karakter(kalimat); readln; end.
function funkalimat (n : integer) : string; var kal : string; begin kal := 'test '; if n = 1 then funkalimat := kal else funkalimat := kal + funkalimat(n - 1); end; begin writeln (funkalimat(10)); readln; end.
Blok program function
Program Utama
11
BAB IV STACK (TUMPUKAN) Secara sederhana, tumpukan bisa diartikan sebagai suatu kumpulan data yang seolah-olah ada data yang diletakkan diatas data yang lain. Satu hal yang perlu dingat adalah bahwa kita bisa menambah data, dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukan (top of stack). Untuk menjelaskan pengertian diatas kita ambil contoh sebagai berikut. Misalnya kita mempunyai dua buah kotak yang kita tumpukkan, sehingga kotak kita letakkan diatas kotak yang lain. Jika kemudian tumpukan dua buah kotak itu kita tambah dengan kotak ketiga, kempat, kelima dan seterusnya, maka akan kita peroleh sebuah tumpukan kotak, yang terdiri dari N kotak.
F E D C B A
atas
Secara sederhana, sebuah tumpukan (stack) dapat digambarkan seperti diatas. Dari gambar ini kita bisa mengatakan bahwa kotak B ada diatas kotak A dan ada dibawah kotak C. Dari gambar juga ditunjukkan bahwa dalam tumpukkan kita hanya bisa menambah atau mengambil sebuah kotak lewat satu ujung, yaitu uung bagian atas. Dapat dilihat pula bahwa tumpukan merupakan kumpulan data yang sifatnya dinamis, artinya kita bisa menambah dan mengambil data darinya. Penggambaran tumpukan juga tidak harus seperti diatas. Kita bisa menggambarkan tumpukan dengan cara lain. menambah
A B C
A
B
C
D
E
F
D E F
menambah
atas
menghapus
menghapus 12
Dari gambar diatas menunjukkan pengertian bahwa kotak yang terakhir dimasukkan bukan berarti memiliki posisi paling atas, tapi lebih ditekankan pada kotak yang paling dekat pada pintu masuk. Dengan memperhatikan ilustrasi-ilustrasi yang disebutkan maka kita bisa melihat bahwa tumpukan merupakan suatu senarai (list) yang mempunyai pengertian “masuk terakhir keluar pertama” (Last In First Out - LIFO). Operasi Pada Tumpukan Ada dua operasi dasar yang bisa kita lakukan pada sebuah tumpukan, yaitu operasi menambahkan data, atau mempush data, dan operasi menghapus data atau mempop data. Karena ke dalam tumpukan kita bisa mempush data, maka tumpukan juga sering disebut dengan pushdown list, Operasi Push Sekarang kita akan menyusun sebuah prosedur untuk operasi push. Dengan menyajikan tumpukan seperti diatas, maka operasi push dengan mudah kita implementasikan sebagai berikut : Procedure PUSH (var T : Tumpukan; X : integer); Begin T.Atas := T.Atas + 1; T.Isi[T.Atas] ;= x; End; Prosedur diatas akan menyiapkan tempat untuk x yang akan dipush ke dalam tumpukan, yaitu dengan menambah nilai medan T.Atas dengan 1 dan kemudian menyisipkan x ke dalam larik T.Isi, Prosedur diatas belum cukup sempurna untuk melakukan operasi push, karena bila data yang dimasukkan (T.Atas) sama dengan Batas maximum (MaxElemen) dan kita akan mempush lagi maka akan terjadi overflow (melebihi batas maximum). Dengan demikian perlu ada penambahan untuk mengatasi overflow tersebut, agar presedur selalu mengecek keadaan lokasi (T.Isi) sebelum suatu data dipush, apakah MaxElemen sudah tercapai atau belum, jika belum tercapai maka operasi push akan dilakukan, tetapi bila sudah mencapai MaxElemen operasi push akan ditolak. Bentuk perubahan prosedurnya adalah : Prosedure PUSH (var T : Tumpukan; X : integer); Begin If T.Atas = MaxElemen then Writeln (‘TUMPUKAN SUDAH PENUH’) Else Begin T.Atas := T.Atas + 1; T.Isi[T.Atas] := X; End; End;
13
Operasi Pop Operasi Pop adalah operasi untuk menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan. Sama halnya dengan operasi push, maka dengan deklarasi tumpukan seperti diatas, prosedur untuk operasi pop bisa dengan mudah kita implementasikan sebagai berikut : Procedure POP (var T : tumpukan); Begin T.Atas := T.Atas – 1; End; Prosedur diatas juga masih sangat sempurna, dan belum dapat digunakan untuk operasi pop, namun sudah mencakup pengertian dari pop. Hal yang terjadi bila kita menggunakan prosedur diatas adalah bila data dalam larik sudah kosong, karena adalah hal yang tidak mungkin melakukan operasi pop bila data sudah kosong. Maka perlu ada tambahan pada procedure untuk mengecek keberadaan data dalam antrian, jika data masih ada maka dapat dilakukan operasi pop, namun bila sebaliknya akan ditolak. Penambahan dari prosedur pop adalah : Procedure POP (var T : Tumpukan); Begin If T.Atas = 0 then Writeln (‘TUMPUKAN SUDAH KOSONG’) Else T.Atas := T.Atas – 1; End;
14
Contoh Pemakaian Tumpukan Dalam Program Untuk lebih memahami operasi yang terjadi pada tumpukan, berikut disajikan contoh program yang menggunakan metode tumpukan untuk membalik kalimat. Dalam hal ini yang dibalik adalah seluruh kalimat dan bukan perkata. program Balik_Kalimat; uses wincrt; const Elemen = 255; type s255 = string[Elemen]; tumpukan = record isi : s255; atas : 0..Elemen; end; var t : tumpukan; i : integer; kalimat : s255;
Batas maximum karakter.
Nama tumpukan pencacah Kalimat yang dibalik
procedure awalan (var t : tumpukan); begin t.atas := 0; end;
Inisialisasi tumpukan
procedure push (var t : tumpukan; x : char); begin t.atas := t.atas + 1; t.isi[t.atas] := x; end;
Prosedure untuk memasukkan elemen ke dalam tumpukan
function pop (var t : tumpukan) : char; begin pop := t.isi[t.atas]; t.atas := t.atas - 1; end;
Fungsi untuk mengambil elemen dari tumpukan
{ Program Utama } Begin clrscr; awalan(t); writeln ('Tumpukan untuk membalik kalimat'); writeln ('*******************************'); writeln; write (‘Ketik kalimat : '); readln (kalimat); clrscr; writeln ('Kalimat asli : ',kalimat); writeln; writeln ('Setelah operasi push dan pop'); for i := 1 to length(kalimat) do push(t, kalimat[i]); for i := 1 to length(kalimat) do write (pop(t)); readln; End.
Kalimat yang akan dibalik
Mempush kalimat ke dalam tumpukan Mempop isi tumpukan sehingga terlihat kalimat yg terbalik
15
program Balik_Kalimat; uses wincrt; const Elemen = 255; type s255 = string[Elemen]; tumpukan = record isi : s255; atas : 0..Elemen; end; var t : tumpukan; i : integer; kalimat : s255;
Batas maximum karakter.
Nama tumpukan pencacah Kalimat yang dibalik
procedure awalan (var t : tumpukan); begin t.atas := 0; end;
Inisialisasi tumpukan
procedure push (var t : tumpukan; x : char); begin t.atas := t.atas + 1; t.isi[t.atas] := x; end;
Prosedure untuk memasukkan elemen ke dalam tumpukan
function pop (var t : tumpukan) : char; begin pop := t.isi[t.atas]; t.atas := t.atas - 1; end;
Fungsi untuk mengambil elemen dari tumpukan
{ Program Utama } Begin clrscr; awalan(t); writeln ('Tumpukan untuk membalik kalimat'); writeln ('*******************************'); writeln; write (‘Ketik kalimat : '); readln (kalimat); clrscr; writeln ('Kalimat asli : ',kalimat); writeln; writeln ('Setelah operasi push dan pop'); for i := 1 to length(kalimat) do push(t, kalimat[i]); for i := 1 to length(kalimat) do write (pop(t)); readln; End.
Kalimat yang akan dibalik
Mempush kalimat ke dalam tumpukan
Mempop isi tumpukan sehingga terlihat kalimat yg terbalik
Hasil eksekusi dari contoh progam : Tumpukan untuk membalik kalimat ******************************* Ketik kalimat : Budi Kalimat asli : Budi Setelah operasi push dan pop
16
iduB Ilustrasi cara kerja contoh program :
Kalimat yang di input
iduB
Budi i
Kalimat hasil keluaran Yang terbalik
iB d
Karakter yang pertama di push (dumasukkan).
u Karakter yang pertama di pop (dikelurkan).
Penjelasan :
B
Misalkan kalimat yang diinput adalah Budi, maka urutan karakter yang di push (dimasukkan) adalah B – u – d – i , maka tampak di gambar ilustrasi, B berada pada paling bawah dan i berada paling atas. Sehingga pada saat ingin melakukan proses pop (mengeluarkan) maka urutan karakter yang dikeluarkan adalah karakter i – d – u – B.
17
BAB V POINTER Pemakaian array tidak selalu tepat untuk program-program terapan dikarenakan kebutuhan memory yang selalu bertambah selama program dijalankan. Untuk megatasi hal ini diperlukan struktur data yang dapat mengalokasikan dan mendealokasi memori secara dinamis sesuai dengan kebutuhan program saat dijalankan. Nama variabel yang digunakan untuk mewakili suatu nilai data, sebenarnya merupakan atau menunjukkan suatu lokasi tertentu didalam memori komputer dimana data tersebut disimpan. Pada saat sebuah program dikopolasi, kompiler akan memriksa bagian deklarasivariabeluntuk mengetahui nama-nama variabel apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam pengingat untuk menyimpan nilai data tersebut. Dari sini kita bisa melihat bahwa sebelum program dieksekusi (harap dibedakan antara kompilasi dan eksekusi program), lokasi-lokasi data dalam pengingat sudah ditentukan dan tidak bisa diubah selama program tersebut di eksekusi. Perubah-perubah yang demikian ini dinamakan dengan perubah statis (static variabel). Dari pengertian ini bisa kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama variabel, maka dalam program tersebut variabel yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin berubah.. Dengan demikian dapat dikatakan bahwa banyaknya data yang bisa diolah adalah terbatas. Sebagai contoh, misalnya kita mempunyai variabel yang kita deklarasikan sebagai berikut : Var kode : array[1..100] of integer; Variabel kode diatas hanya mampu untuk menyimpan data sebanyak 100 buah data. Jika kita tetap akan menambah data pada variabel tersebut, eksekusi program akan terhenti karena deklarasinya kurang. Sebaliknya jika ternyata data yang disimpan sedikit jumlahnya, akan mengakibatkan pemborosan pemakaian memori yang tidak perlu. Untuk megatasi hal ini maka dibuatlah suatu variabel dinamis yang dapat dialokasi dan didialokasikan sehingga jumlah penggunaan memori dapat sesuai kebutuhan saat program dijalankan. Variabel dinamik (dynamic variabel) adalah variabel yang dialokasikan hanya pada saat program dijalankan. Pada saat dikompilasi, lokasi variabel ini belum ditentukan, kompiler hanya mencatat bahwa ada variabel yang akan diperlakukan secara dinamis. Pada variabel statis, isi memori pada lokasi tertentu adalah data sesungguhnya yang akan diolah. Pada variabel dinamis, nilai variabel adalah alamat lokasi yang menyimpan data sesungguhnya. Untuk memperjelas pengertian tentang Pointer perhatikan ilustrasi berikut :
A
1000 a.
B
5
5
1000
b.
Pada ilustrasi diatas terdapat 2 gambar a dan b. Gambar a mengilustrasikan variabel A dengan variabel statis. Dalam hal ini 1000 adalah nilai data yang sesungguhnya dan disimpan pada variabel A. Sedangkan pada gambar b mengilustrasikan variabel B yang dinamis. Nilai variabel b dimisalkan adalah 5,
18
nilai ini bukan data yang sesungguhnya, tetapi lokasi yang menyimpan data sesungguhnya berada. Jadi dalam hal ini nilai data yang sesungguhnya tersimpan berada pada lokasi 5 didalam memori. Dari ilustrasi diatas bisa dilihat bahwa nilai variabel dinamis akan digunakan untuk menunjuk kelokasi lain yang berisi data sesungguhnya yang akan diproses. Karena alasan inilah variabel dinamis lebih dikenal dengan sebutan pointer yang artinya kira-kira menunjuk ke sesuatu. Dalam variabel dinamis nilai data yang ditunjuk oleh suatu pointer biasanya disebut sebagai simpul/node. Bentuk umum deklarasi pointer : Type variabel = ^simpul; simpul = TipeData; Tanda ^ (ceret) didepan nama simpul menunjukkan bahwa variabel tersebut adalah tipe data pointer. TipeData dapat berupa sembarang tipe data, tetapi umumnya dalam program terapan TipeData ini biasanya berupa record. Contoh penulisan pointer dengan bentuk record; Type dataMhs = ^Data; Data = record Nama : string[25]; Nomor : string[10]; Alamat : string[25]; End; Var mhs1,mhs2 : dataMhs;
Variabel mhs1 dan mhs2 masing-masing bertipe pointer. Ketika program dikompilasi, kedua variabel ini akan menempati lokasi memori tertentu, tetapi belum menunjuk kesuatu simpul (lokasi memori) yang berisi data. Pointer yang belum menunjuk kesuatu lokasi akan bernilai nil. Untuk mengalokasikan simpul didalam memori digunakan statemen new, yang bentuk umumnya sebagai berikut : New (variabel); Untuk mendealokasikan simpul yang sudah tidak terpakai, maka digunakan statemen dispose. Dsipose (variabel); Untuk mengisi data kedalam pointer (yang memiliki tipe data record) caranya sama dengan pemakaian record, hanya saja setelah nama variabel lebih dulu diikuti dengan tanda ceret. Contoh : Mhs1^.nama := ‘Alung’; Mhs2.alamat := ‘Jln. BimaSakti’;
Pemakaian alokasi memori dinamik sangat banyak digunakan oleh program. Program-program grafik akan mengalokasikan sejumlah memori untuk menyimpan gambar yang terdapat pada layar. Program yang menggunakan popup dan pulldown menu juga memanfaatkan alokasi memori dinamik. Bagian layar yang ditutupi oleh menu disimpan dibagian memori yang telah dialokasikan. Setelah menu tidak digunakan, bagian yang ditutupi dikembalikan lagi. Karena
19
tidak digunakan, bagian bagian memori yang telah dialokasikan tersebut dikembalikan (dealokasi) ke sistem untuk menghemat pemakaian memori. Latihan : type n = ^integer; var k : n; i : integer; begin i := 20; clrscr; writeln (k^); new (k); k^ := i; writeln (k^); readln; end.
type point = ^data; data = record nama : string; alamat : string; end; var dt1,dt2 : point; begin clrscr; new (dt1); new (dt2); dt1^.nama := 'Alung SiDraco'; dt1^.alamat := 'Yogyakarta'; writeln ('Data yang terdapat di dt1^'); writeln (dt1^.nama); writeln (dt1^.alamat); writeln; dt2^ := dt1^; writeln ('Data yang terdapat di dt2^'); writeln (dt2^.nama); writeln (dt2^.alamat); writeln; dispose (dt1); writeln ('dt1 setelah di dispose'); writeln (dt1^.nama); writeln (dt1^.alamat); writeln; dispose (dt2); writeln ('dt2 setelah di dispose'); writeln (dt2^.nama); writeln (dt2^.alamat); readln; end.
20
BAB VI LINKED LIST ( SENARAI BERANTAI ) A. Single Linked List. Salah satu struktur data dinamis yang paling sederhana adalah Senarai Berantai (Linked List), atau senarai satu arah. Senarai Berantai sendiri punya makna sebagai kumpulan komponen yang disusun secara berurutan dengan menggunakan bantuan pointer. Komponen-komponen yang tersusun tersebut akan disebut sebagai simpul, sehingga pada senarai akan terdapat banyak simpul, dan tiap simpulnya dapat dibagi menjadi dua bagian. Bagian pertama dari simpul disebut dengan medan informasi, yang berisi informasi/data yang fapat berupa record yanag akan diolah. Sedangkan bagian yang kedua disebut sebagai medan penyambung (link field), yang berisi alamat simpul berikutnya. simpul
simpul^.medan_informasi
simpul^.medan_penyambung
Medan informasi
Medan penyambung
Untuk memudahkan setiap pembahasan selanjutnya, maka akan kita tetapkan untuk sebelah kiri simpul disebut sebagai medan informasi dan sebelah kanan simpul disebut sebagai medan penyambung. Perlu diketahui bahwa medan penyambung sebenarnya adalah suatu pointer yang akan menunjuk ke simpul berikutnya, sehingga nilai dari medan ini dapat berupa alamat lokasi simpul berikutnya ataupun dapat bernilai nil. Perlu diingat bahwa setiap simpul terakhir dari linked list medan penyambung harus bernilai nil.
Contoh dari senarai berantai dengan 5 simpul : Pointer yg menunjuk ke awal senarai
awal
akhir
Pointer yg menunjuk ke akhir senarai
A
B
Medan informasi
C
D
Medan penyambung yg menunjuk ke simpul berikutnya
E
Medan penyambung yg bernilai nil
Tampak dari gambar bahwa medan penyambung menunjuk ke simpul berikutnya, dan medan penyambung pada simpul terakhir akan bernilai nil karena medan penyambung tersebut tidak menunjuk kemanapun. Pada senarai berantai 21
juga terdapat 2 buah pointer awal dan akhir, kedua pointer ini berfungsi untuk mempermudah dalam melakukan operasi pengolahan data pada senarai berantai, seperti : pembacaan, pencarian, pengeditan, serta penghapusan data, pengertian kedua pointer ini mungkin akan lebih jelas pada pembahasan selanjutnya. Bentuk umum pendeklarasian single linked list : Type nmlist = ^nmrecord; nmrecord = record; nmvar1 : tipe; nmvarn : nmlist;
Medan penghubung yg bertipe data pointe.
end; Var node : list; Penjelasan : nmlis
: sebuah pointer yang menunjuk ke sebuah record.
nmrecord : nama record yang berisi variabel penyimpan data dan berisi medan penyambung. nmvar1 : variabel yang akan berfungsi sebagai penyimpan data nmvarn : variabel yang berfungsi sebeagai media penyambung. Contoh penulisan Single Linked List : Type simpul = ^data; data = record info : char; kait : simpul; end; var awal,akhir,baru : simpul; Dengan contoh pendeklarasian sederhana tersebut, maka operasi-operasi pengolahan data dapat dilakukan seperti pada contoh program berikut yang berfungsi untuk menambah dan menampilkan data menggunakan linked list.
22
program SingleLinkedList; uses wincrt; type simpul = ^data; data = record Deklarasi simpul nama : string[25]; kait : simpul; end; var awal,akhir,bantu : simpul; ya : char; begin clrscr; Pembuatan nilai awal= nil, pada awal := nil; saat program pertama dijalankan ya := 'y'; while ya in ['y','Y'] do begin new (bantu); write ('Masukkan Nama : '); readln (bantu^.nama); write ('Tambah data lagi [Y/N]: ?'); readln (ya); writeln; if awal = nil then begin bantu^.kait := nil; Proses 1: awal := bantu; Proses yg dilakukan saat akhir := bantu; penginputan data yang pertama end else begin akhir^.kait := bantu; Proses 2 : bantu^.kait := nil; Proses penambahan data akhir := bantu; selanjutnya. end; end; bantu := awal; writeln (bantu^.nama); Proses 3 : while bantu^.kait <> nil do Proses untuk menampilkan data begin bantu := bantu^.kait; writeln (bantu^.nama); end; readln; end.
Program diatas pertama kali setelah pendeklarasian simpul adalah melakukan pemberian nilai nil terhadap variabel awal, karena pada saat program pertama dijalankan data belum ada sehingga variabel awal belum menunjuk kesuatu tempat. Tampak pada program terdapat 3 proses, demikian ilustrasi ke 3 proses tersebut : Proses 1 : Proses untuk memberikan nilai pada variabel awal dan akhir saat pertama penginputan data. bantu
bantu
a.
b.
awal
akhir
c. 23
Tampak bahwa medan penyambung dari bantu (bantu^.kait) dibuat nilainya nil karena data masih satu sehingga berperan sebagai awal dan akhir linked list. Proses 2 : Proses untuk memberikan nilai pada akhir untuk menunjuk kebantu yang baru saja diinputkan. awal
akhir
bantu
awal
a.
akhir
bantu
b. awal
akhir Niliai nil
c. Pada gambar a simpul bantu baru dibentuk. Gambar b menjelaskan akhir akan menunjuk ke bantu yang baru. Gambar c menjelaskan peberian nilai nil kepada bantu^.kait, karena bantu tersebut berada pada posisi terakhir. Tampak pada gambar bahwa yang berpindah arah hanya akhir dan bukan awal, hal ini menandakan bahwa penambahan dilakukan di belakang linked list. Perlu diingat bahwa dalam linked list terdapat peraturan-peraturan sebagai berikut : 1. awal akan selalu menunjuk ke awal linked list, dan akhir akan selalu menunjuk ke akhir linked list, sekalipun penambahan data dilakukan. 2. Setiap simpul yang terakhir dari linked list nilai dari medan penyambung harus selalu bernilai nil. Proses 3 : Pada proses ini bantu akan membaca simpul dan menampilkan hasilnya dari awal sampai akhir linked list. Operasi pada Senarai Berantai (Single Linked List) 1. Menambah simpul di belakang. Untuk contoh dan ilustrasi menambah dibelakang sudah dijelaskan pada contoh program Proses 2. 2. Menambah simpul di depan. Ilustrasi : bantu
awal
akhir
Simpul baru
a. bantu
awal
bantu^.kait := awal
akhir
b. awal
akhir
awal := bantu
24 c.
Bentuk penulisan dalam bentuk program : new(bantu); bantu^.nama := ‘Alung’; bantu^.kait := awal; awal := bantu; 3. Menambah simpul di tengah. Ilustrasi : awal
akhir
a.
bantu
awal
bantu2
Simpul baru
akhir
b.
bantu bantu^.kait:= bantu2^.kait tbanbantu2^.berikut
awal
bantu2
akhir
c. Bentuk penulisan dalam bentuk program : new(bantu); bantu^.nama := ‘Alung’; bantu^.kait := bantu2^.kait; bantu2^.kait := bantu;
bantu2^.kait := bantu
25
4. Menghapus simpul di awal. Ilustrasi : bantu awal
akhir
bantu := awal
a. bantu
awal
akhir
awal := bantu^.kait
b. : Bentuk penulisan dalam bentuk program bantu bantu := awalawal; awal := bantu^.kait; dispose(bantu);
akhir
c.
dispose(bantu)
5. Menghapus simpul di tengah. Ilustrasi : awal
bantu2
bantu2^.kait := bantu
awal
bantu2
bantu
akhir
a. bantu
akhir
b. bantu2^.kait := bantu^.kait
awal
bantu2
dispose(bantu)
akhir
c.
26
Bentuk penulisan dalam bentuk program : While (bantu^.kait<>nil) or (bantu^.nama<>‘Budi’) do bantu := bantu^.kait; If (bantu <> nil) then Begin bantu2^.kait := bantu; bantu2^.kait := bantu^.kait; dispose(bantu); End; bantu := akhir
6. Menghapus simpul di akhir. Ilustrasi : awal
akhir
bantu
a. akhir^.kait := bantu
awal
akhir
awal
bantu
akhir dispose(bantu)
b. c. Bentuk penulisan dalam bentuk program : bantu := akhir; akhir^.kait := bantu; dispose(bantu); akhir^.kait := nil;
akhir^.kait := nil
B. Double Linked List, Double Linked List menggunakan tekhnik yang sama dengan Single Linked List. Perbedaan utamanya adalah simpul pada Double Linked List dapat menunjuk kedapan atau kebelakang. Hal ini akan mempermudah pembacaan (bisa dilakukan dari kiri ke kanan atau sebalinya), penambahan simpul baru atau penghapusan simpul bisa dilaksanakan untuk simpul-simpul yang terletak disebelah kiri atau kanan dari pointer yang diketahui. simpul
simpul^.belakang
simpul^.depan
27
Contoh pendeklarasian Double Linked List : Type simpul = ^data; data = record nama : string; depan,belakang : simpul; End; Var awal,akhir,baru : simpul; Tampak dari contoh pendeklarasian tersebut pada bagian record terdapat dua buah variabel yang bertipe pointer (simpul) yaitu depan dan belakang. Hal inilah yang mengakibatkan Senarai Berantai tersebut disebut sebagai Double Linked List. Pada deklarasi di atas pointer blakang adalah pointer untuk menunjuk ke simpul sebelumnya, atau simpul sebelah kiri, pointer depan adalah pointer untuk menunjuk ke simpul sesudahnya atau simpul sebelah kanan. Operasi pada Senarai Berantai Ganda (Double Linked List). Simpul baru 1. Menambah Data Ilustrasi : awal
akhir A
baru
C
B
nil
D nil
a. awal
akhir A
baru
C
B
D
nil akhir^.depan:=baru; baru^.belakang:=akhir
b. akhir := baru;
awal
akhir A
B
nil
C
baru D nil baru^.belakang := nil
Bentuk penulisan dalam bentukc.program : akhir^.depan := baru; baru^.belakang := akhir; baru^.depan := nil; akhir := baru;
28
2. Membaca simpul/data Karena memiliki pointer yang dapat menunjuk ke depan dan ke belakang, operasi pembacaan data dilakukan dari kedua arah, yaitu dari depan dan belakang. Membaca dari belakang : bantu
awal A
bantu
akhir C
B
D
nil
nil
a. Penulisan dalam bentuk program : bantu := awal; While bantu <> nil do Begin Writeln (‘nama : ‘,bantu^.nama); bantu := bantu^.depan; End; Fungsi dari penulisan program ini adalah untuk menjalankan pointer bantu dari awal hingga akhir list serta menampilkan isi dari simpul yang dilewati. Membaca dari depan : bantu
awal
akhir
bantu
A C D B nil dalam bentuk program : bantu := akhir; While bantu <> nil do a. Begin Writeln (‘nama : ‘,bantu^.nama); bantu := bantu^.belakang; End;
nil Penulisan
Perintah-perintah di atas adalah untuk menjalankan pointer bantu dari akhir hingga ke awal senarai, serta menampilkan isi dari variabel nama pada setiap simpul yang dilewatinya.
29
Contoh Program : program doule_linked_list; uses wincrt; type simpul = ^data; data = record Deklarasi simpul double linked nama : string; list. depan,belakang : simpul; end; var awal,akhir,bantu : simpul; pil : char; Procedure untuk menambah procedure buatlist (var bantu : simpul); data begin if awal = nil then begin Penambahan data/simpul yang awal := bantu; pertama awal^.depan := nil; awal^.belakang := nil; akhir := awal; end else begin akhir^.depan := bantu; Penambahan data/simpul untuk kebantu^.depan := nil; sekian kali. bantu^.belakang := akhir; akhir := bantu; end; end; Procedure untuk mencetak data dari awal procedure cetakawal; list. var bantu : simpul; begin clrscr; writeln ('Cetak Data Dari Awal'); bantu := awal; while bantu <> nil do Perintah untuk mencetak data begin dari awal. writeln ('Nama : ',bantu^.nama); bantu := bantu^.depan; end; readln; end;
30
procedure cetakakhir; Procedure untuk mencetak data dari akhir var bantu : simpul; list begin clrscr; writeln ('Cetak Data Dari Akhir'); bantu := akhir; while bantu <> nil do begin Perintah untuk mencetak data writeln ('Nama : ',bantu^.nama); dari akhir. bantu := bantu^.belakang; end; readln; end; Procedure untuk menghapus seluruh data procedure hapuslist; dari awal. var bantu : simpul; begin clrscr; while awal <> nil do begin Perintah untuk menghapus data dari awal bantu := awal; list. awal := awal^.depan; dispose(bantu); end; writeln ('Data telah dihapus'); readln; end; Begin Awal program utama awal := nil; repeat clrscr; writeln ('Program Double Linked List'); writeln ('**************************'); writeln ('1. Tambah Data'); writeln ('2. Cetak Data Dari Awal'); writeln ('3. Cetak Data Dari Akhir'); writeln ('4. Hapus Seluruh Data'); writeln ('5. Keluar'); write ('Pilihan Anda [1/2/3/4/5] : '); readln (pil); case pil of '1' : begin clrscr; new(bantu); Perintah untuk menambah writeln ('Tambah Data'); data dan memanggil write ('Masukkan Nama : '); procedure buatlist. readln (bantu^.nama); buatlist(bantu); end; '2' : cetakawal; Pemanggilan procedure cetakawal '3' : cetakakhir; Pemanggilan procedure cetakakhir '4' : hapuslist; Pemanggilan procedure hapuslist end; until (pil >= '5'); readln; End.
31
BAB VII ANTRIAN (QUEUE) Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung (belakang/rear), dan penghapusan dilakukan lewat ujung lainnya (depan/front). Sebagai contoh dapat kita ibaratkan dengan antrian membeli karcis di sebuah bioskop, para pengantri yang ingin membeli karcis hanya masuk ke antrian melalui satu pintu saja, demikian bagi yang telah selesai membeli karcis akan keluar melalui satu pintu/ujung yang lain. Seperti pada Stack/Tumpukan yang mengenal istilah masuk terakhir keluar pertama (LIFO – Last In First Out). Berbeda dengan Antrian yang mengenal istilah masuk pertama keluar pertama (FIFO – Fisrt In First Out) Ilustrasi Antrian : depan
A
keluar
B
C
D
E
F
masuk
belakang Hal yang perlu diingat pada operasi Antrian adalah bahwa setiap penambahan data akan selalu dilakukan dari belakang, dan pengurangan/penghapusan data akan selalu dilakukan dari depan. Sehingga berdasarkan gambar bila ingin menambahkan suatu data harus diletakkan pada bagian sebelah kanan F, dan bila akan menghapus suatu data, maka akan dilakukan pada bagian sebelah kiri, dalam hal ini A. Antrian dapat disajikan dalam bentuk larik/array. Berikut contoh pendeklarasian Antrian dengan array. Type antri = array[1..100] of integer; Var antrian : antri; depan,belakang : integer; Pada deklarasi diatas, elemen antrian dinyatakan dalam tipe integer. Variabel depan menunjukkan posisi elemen pertama dalam larik, variabel belakang menunjukkan posisi elemen terakhir dalam larik. Dalam suatu permasalahan saat antrian sudah penuh, sementara kita masih ingin terus menambahan data lagi, maka akan terjadi offerflow (kelbihan kapasitas). Dengan mengabaikan akan terjadinya offerflow, maka penambahan data pada antrian dalam bentuk programnnya adalah sebagai berikut : Belakang := belakang + 1; Antrian[belakang] := x; {x : variabel untuk mengisi antrian} Ilustrasi : depan = 1
A. 1 belakang = 0
2
3
4
5
6
32
Program pada saat pertama kali dijalankan antrian masih dalam keadaan kosong, sehingga depan bernilai 1 dan belakang bernilai 0. depan = 1
B.
A
B
C
D
1
2
3
4
5
6
belakang = 4 Pada saat dilakukan penambahan data maka belakang akan dijumlahkan dengan 1, kemudian antrian pada posisi belakang (antrian[belakang]) akan disi dengan elemen x. Masih dengan mengabaikan akan terjadinya offerflow, untuk pengurangan / penghapusan pada antrian adalah sebagai berikut : X := antrian[depan]; Depan := depan + 1; depan = 3
1
2
C
D
3
4
E
F
5 6 belakang = 6
Pada saat dilakukan pengurangan data maka x akan diisi nilainya dengan kedudukan depan saat itu, kemudian depan dimajukan sebanyak 1 (depan + 1). Dengan keadaan seperti diatas tentu saja dapat terjadi suatu keadaan dimana penambahan elemen baru tidak dapat dilakukan, misalnya karena nilai belakang sudah mencapai nilai maksimal akan tetapi antrian yang sesungguhnya masih banyak yang kosong karena nilai depan lebih besar dari 1, seperti pada gambar di atas. Kemungkinan penyelesaian yang dapat dilakukan adalah dengan menggeser elemen-elemen lain maju ke depan jika ada elemen yang keluar (dihapus) seperti antrian manusia yang membeli karcis pada umumnya. depan belakang depan belakang
1
2
C
D
E
F
3
4
5
6
C
D
E
F
1 2 3 4 5 6 Akan tetapi hal ini akan sangat tidak efisien dilakukan pada elemn array, kalu jumlah elemen array yang sedikit mungkin tidak terlalu jadi masalah, tetapi akan jadi masalah bila elemen array-nya sampai sebanyak seratus bahkan ribuan elemen, data akan dipindahkan satu-persatu sebanyak seribu elemen, hal ini akan memperlambat kinerja komputer. 33
Cara yang paling baik untuk memecahkan masalah ini adalah dengan menyimpan elemen larik seolah-olah larik berbentuk lingkaran. depan X
C
D
belakang E
Elemen baru selalu dapat ditambahkan selama masih ada tempat kosong (terdapat tempat kosong antara belakang dan depan). Pada kenyataan yang sebenarnya larik tidak benar-benar memutar melainkan masih seperti biasa yang memiliki ujung, namun perlakuannya di dalam penulisan program dibuat seakan-akan melingkar/memutar. Berikut adalah ilustrasi serta penulisan program untuk operasi pada antrian yang dibuat seakan-akan memutar : 6
E
5
D
4
C
belakang=6
Pada keadaan awal antrian disi dengan dua elemen : belakang := 6; depan := 4;
depan=4
3 2 1 6
E
5
D
4
C
depan=4
1
F
belakang=1
6
E
5
D
Hal berikut adalah proses penambahan elemen, karena masih ada tempat yang kosong (perlu diingat antrian diperlakukan sebagai lingkaran).
3 2
depan=5
4
Hal berikut menjelaskan proses penghapusan data, selama masih data belum kosong : X := antrian[depan]; If depan = maximal then Depan := 1; Else Depan := depan + 1;
3 2 1
if belakang = maximal then belakang := 1 else belakang := belakang + 1;
F
belakang=1
34
Contoh program : program antrian_; uses wincrt; const maximum = 10; Pembuatan array untuk type antri = array[1..maximum] of char; antrian var antrian : antri; depan,belakang,pilih : integer; elemen : char; function Kosong(Q : antri) : boolean; Function untuk mencek isi antrian begin Jika depan = belakang, berarti Kosong := (depan = belakang); antrian sedang kosong end; procedure tambah(var antrian : antri; x : char); begin Jika belakang berada pada posisi antrian if belakang = maximum then teratas, maka belakang dipindah ke 1 belakang := 1 else Jika tidak berada diatas maka belakang := belakang + 1; belakang dinaikkan 1 if not(Kosong(antrian)) then Jika antrian tidak kosong maka, antrian begin ditambah dengan nilai x pada posisi antrian[belakang] := x; belakang write (x); end else begin write ('Antrian Sudah Penuh'); repeat { } until keypressed; belakang := belakang - 1; Pengembalian posisi belakang ke tempat if belakang = 0 then sebelumnya saat antrian sudah penuh dan belakang := maximum; tidak dapat ditambah lagi. end; end;
35
Function untuk function Hapus(var antrian : antri) : char; menghapus elemen begin if depan = maximum then depan := 1 Untuk memindahkan depan ke 1 saat depan else berada di posisi maximum. begin depan := depan + 1; Memindahkan depan sebanyak 1 elemen, Hapus := antrian[depan]; dan menghapus elemen. end; end; Awal program utama Begin clrscr; Penempatan posisi depan dan belakang di posisi 0 saat awal depan := 0; program dimulai. belakang := 0; repeat clrscr; writeln ('Daftar Menu Pilihan'); writeln ('-------------------'); writeln ('1. Menambah Elemen'); writeln ('2. Menghapus Elemen'); writeln ('3. Selesai'); write ('Pilih Salah Satu : '); readln (pilih); case pilih of Pemanggilan procedure tambah 1 : begin saat menambah elemen writeln ('Menambah Elemen'); writeln ('---------------'); write ('Isikan Elemennya : '); readln (elemen); tambah (antrian,elemen); end; 2 : begin if not(Kosong(antrian)) then Pengecekan isi antrian saat akan elemen := hapus(antrian) menghapus elemen. Jika antrian else tidak kosong maka data akan begin writeln ('Antrian Kosong'); dihapus, sebaliknya jika antrian kosong akan ada pesan ‘Antrian elemen := readkey; Kosong’. end; end; end; until pilih = 3 End.
Program diatas tidak akan menampilkan data yang telah diinput, sehingga untuk pengujiannya adalah dengan cara : Inputkanlah data sebanyak tiga kali dengan memilih menu 1, kemudian hapuslah data tersebut dengan memilih menu 2 sebanyak tiga kali. Jika ada pesan : “Antrian Kosong”, berarti program anda sudah benar. Hal ini disebabkan data yang kita masukkan sebanyak 3 buah, akan dihapus dari antrian, sehingga pada penghapusan yang keempat ditampilkan sebuah pesan.
36
Implementasi Antrian Dengan Pointer. Kita telah mempelajari bagaimana membuat antrian dengan menggunakan array. Dari pelajaran tersebut kita dapat mengetahui bahwa dengan menggunakan array, antrian punya beberapa kekurangan antara lain : jumlah elemen antrian sangat dibatasi oleh elemen array, sehingga tidak memungkinkan bila ingin memproses data yang sangat banyak dan belum dapat di ketahui jumlah maximalnya. Sehingga dalam hal ini diperlukan bantuan pointer untuk menerapkan pembuatan antrian. Dengan menggunakan pointer maka jumlah data yang dapat di inputkan ke antrian bisa sangat banyak. Penerapan pointer dalam antrian hampir sama dengan senarai berantai, sehingga bila anda sudah memahami senarai berantai maka tidak sulit untuk memahami antrian dengan pointer. Berikut implementasi antrian dengan pointer menggunakan ilustrasi : 1. Inisialisasi kepala ekor New(kepala); kepala^.info := chr(0); kepala^.kait := kepala; ekor := kepala 2. Penambahan di belakang (masuk ke dalam antrian). kepala ekor baru Penambahan antrian dengan data baru
kepala
ekor
baru
baru^.kait := kepala
kepala
ekor
baru
ekor^.kait := baru
kepala
ekor ekor := baru
37
3. Penghapusan di depan (Keluar dari antrian). bantu
kepala
ekor
bantu := kepala bantu kepala
ekor
kepala := bantu^.kait bantu
kepala
ekor
ekor^.kait := kepala kepala
ekor
dispose(bantu)
38
BAB VIII SORT Pengurutan data (sorting) secara umum dapat didefinisikan sebagai suatu proses untuk menyusun kembali himpunan objek menggunakan aturan-aturan tertentu. Berdasarkan cara pengurutan dapat dibedakan menjadi dua bagian, yang pertama adalah pengurutan secara urut naik (ascending), yaitu data diurutkan mulai dari yang terkecil hingga yang terbesar, yang kedua adalah pengurutan secara urut turun (descending), yaitu pengurutan dari data yang besar hingga ke data yang paling kecil. Pengurutan merupakan suatu hal yang penting sekali dalam ilmu komputer, praktik-praktik yang sering menggunakan pengurutan biasanya sering terjadi dalam operasi basis data, dimana pengurutan data sangat dibutuhkan untuk memudahkan dalam pencarian data yang diinginkan dari sekian banyak data yang tersimpan. Untuk melakukan proses pengurutan data pada saat ini telah banyak dikembangkan methode-methode untuk lebih mengefisienkan pengurutan data, diantara methode-methode itu adalah dengan cara : Methode Penyisipan Langsung, Penyisipan Biner, Methode Seleksi, Methode Gelembung, Methode ShellShort, Methode QuickShort, dan masih ada beberapa methode lagi. Dari banyaknya methode yang dapat melakukan pengurutan ini, maka disinilah kita dituntut untuk dapat memilih methode yang sesuai dengan apa yang sedang kita kerjakan dengan memikirkan efisiensinya. Hal yang paling berpengaruh dalam pemilihan methode adalah dilihat dari segi banyaknya data yang akan diurut, dan dari segi lama waktu yang dibutuhkan untuk mengurutkan data. Karena banyaknya methode yang dapat dilakukan untuk mengurutkan data, maka untuk pembahasan ini kita hanya akan membahas pengurutan data dengan Methode Gelembung (Buble Sort). Namun diharapkan setiap mahasiswa juga mempelajari methode-methode lain. Pada pembahasan Methode Gelembung, kita akan membahasnya pada pengurutan data yang tersimpan pada senarai berantai (single linked list). Berikut langkah-langkahnya, dengan data dianggap sudah diinputkan : Langkah 1 : awal A
B
Langkah pertama adalah dengan memberikan nilai pada pointer A untuk menunjuk pada data awal, dan pointer B menunjuk pada data sesudahnya. Pada saat posisi seperti gambar, nilai pada pointer B akan dibandingkan dengan nilai pada pointer A, jika nilai pada B < A, maka nilainya akan ditukar (untuk pengurutan ascending). Langkah 2 : awal
A
B
B
39
Langkah kedua adalah dengan menjalankan pointer B sampai ke ujung dari senarai, dengan catatan setiap kali melewati sebuah simpul, nilainya akan selalu dibandingkan dengan nilai yang ada pada pointer A, jika nilai B < A, maka nilainya akan ditukar. Langkah 3 : awal
A
B
Langkah ketiga adalah, setelah langkah kedua diatas selesai dilakukan, maka pointer A maju satu simpul, dan pointer B mengambil posisi di depan pointer A, kemudian membandingkan nilai yang ada di pointer B ke pointer A. Langkah 4 : awal
A
B
B
Langkah keempat adalah sama seperti langkah kedua dengan menjalankan pointer B sampai ke simpul terakhir sambil membandingkan nilainya dengan yang ada dipointer A. Demikian seterusnya sampai pointer A sampai pada ujung senarai berantai atau simpul terakhir.
40
Dari langkah-langkah tersebut diatas maka diperolehlah data yang sudah diurutkan secara ascending. Untuk memperjelas pengertian tentang pengurutan dengan Methode Gelembung (Buble Short), berikut contoh programnya : program tes_sortir; uses crt; type simpul = ^data; data = record dt : char; Pendeklarasian simpul untuk senarai berantai kait : simpul; end; var awal,A,B,baru,akhir,bantu : simpul; huruf : string; i : integer; car : char; begin clrscr; new(awal); awal := nil; write ('Inputkan karakter : '); readln (huruf); for i := 1 to length(huruf) do begin new(baru); baru^.dt := huruf[i]; if awal = nil then begin baru^.kait := nil; Proses yang dilakukan untuk awal := baru; memasukkan atau menambah data akhir := awal; kedalam senarai berantai end else begin akhir^.kait := baru; akhir := baru; akhir^.kait := nil; end; end;
41
A := awal; while not(A = nil) do begin B := A^.kait; while not(B = nil) do begin if B^.dt < A^.dt then begin car := B^.dt; B^.dt := A^.dt; A^.dt := car; end; B := B^.kait; end; A := A^.kait; end; writeln ('Hasil Pengurutan'); bantu := awal; while not(bantu = nil) do begin writeln (bantu^.dt); bantu := bantu^.kait; end; readln end.
Perintah yang dilakukan untuk mengurutkan data yang terdapat di dalam senarai berantai secara ascending.
Perintah yang dilakukan untuk menampilkan data yang terdapat pada senarai berantai hasil sortiran/pengurutan.
Program diatas adalah program untuk mengurutkan seluruh karakter yang dimasukkan dari keyboard secara ascending.
42
