Pemakaian array tidak selalu tepat untuk program-program terapan yang kebutuhan pengingatnya selalu bertambah selama eksekusi program tersebut. Untuk itu diperlukan satu tipe data yang dapat digunakan untuk mengalokasikan (membentuk) dan mendealokasikan (menghapus) pengingat secara dinamis, yaitu sesuai dengan kebutuhan pada saat suatu program dieksekusi. Oleh karena itu akan dijelaskan suatu tipe data yang dinamakan sebagai tipe Data Pointer.
Nama peubah yang kita gunakan untuk mewakili suatu nilai data sebenarnya merupakan / menunjukkan suatu lokasi tertentu dalam pengingat computer di mana data yang diwakili oleh tipe data tersebut disimpan. Pada saat sebuah program dikompilasi maka compiler akan melihat pada bagian deklarasi peubah (Var) untuk mengetahui nama-nama peubah apa saja yang digunakan, sekaligus mengalokasikan atau menyediakan tempat dalam memory untuk menyimpan nilai data tersebut. Dari sini kita bisa melihat bahwa sebelum program dieksekusi, maka lokasi-lokasi data dalam memory sudah ditentukan dan tidak dapat diubah selama program tersebut dieksekusi. Peubah-peubah yang demikian itu dinamakan sebagai Peubah Statis (Static Variable).
Dari pengertian diatas kita perhatikan bahwa sesudah suatu lokasi pengingat ditentukan untuk suatu nama peubah maka dalam program tersebut peubah yang dimaksud akan tetap menempati lokasi yang telah ditentukan dan tidak mungkin diubah. Dengan melihat pada sifat-sifat peubah statis maka bisa dikatakan bahwa banyaknya data yang bisa diolah adalah sangat terbatas. Misalnya peubah dalam bentuk Array yang dideklarasika sbb : Var matriks: array[1..100,1..100] of integer; maka peubah tersebut hanya mampu menyimpan data sebanyak 100x100=10000 buah data. Jika kita tetap nekat memasukkan data pada peubah tersebut setelah semua ruangnya penuh maka eksekusi program akan terhenti dan muncul error. Memang kita dapat mengubah deklarasi program diatas dengan memperbesar ukurannya. Tetapi jika setiap kali kita harus mengubah deklarasi dari tipe daa tersebut sementara, banyaknya data tidak dapat ditentukan lebih dahulu, maka hal ini tentu merupakan pekerjaan yang membosankan.
Sekarang bagaimana jika kita ingin mengolah data yang banyaknya kita tidak yakin sebelumnya bahwa larik yang telah kita deklarasikan sebelumnya mampu menampung data yang kita miliki ?
Untuk menjawab pertanyaan di atas maka pascal menyediakan satu fasilitas yang memungkinkan kita untuk menggunakan suatu peubah yang disebut dengan Peubah Dinamis (Dynamic Variable). Peubah dinamis adalah peubah yang dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi. Dengan kata lain, pada saat program dikompilasi, lokasi untuk peubah belum ditentukan sebagai peubah dinamis. Hal ini membawa keuntungan pula, bahwa peubah-peubah dinamis tersebut dapat dihapus pada saat program dieksekusi sehingga ukuran memory selalu berubah. Hal inilah yang menyebabkan peubah tersebut dinamakan sebagai peubah dinamis.
Pada peubah statis, isi dari peubah adalah data sesungguhnya yang akan diolah. Pada peubah dinamis nilai peubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya tidak dapat dimasup secara langsung. Oleh karena itu, peubah dinamis dikenal dengan sebutan POINTER yang artinya menunjuk ke sesuatu. Dalam peubah dinamis, nilai dari data yang ditunjuk oleh suatu pointer biasanya disebut Simpul / node.
Dekarasi Pointer dan Alokasi Tempat
Bentuk umum deklarasi pointer :
Type Pengenal = ^simpul ;
Simpul = tipe data ;
dengan pengenal : nama pengenal yang menyatakan tipe data pointer
simpul : nama simpul
tipe data : tipe data dari simpul
Tanda ^ di depan simpul harus ditulis apa adanya karena itu menunjukkan bahwa pengenal bertipe pointer. Tipe data dari simpul dapat berupa tipe data sebarang, misalnya char, integer, atau real.
Contoh :
Type Str30 = string[30] ;
Point = ^Data ;
Data = record
Nama_Peg : Str30 ;
Alamat : Str30 ;
Pekerjaan : Str30 ;
End ;
Var
P1, P2 : Point ;
A, B, C : Str30 ;
Mengakses Data Dalam Tipe Data Pointer
Pada saat program dikompilasi maka P1 dan P2 akan menempati lokasi tertentu dalam memory. Kedua peubah ini masing-masing belum menunjuk ke suatu simpul atau nilainya dinyatakan dengan NIL. Oleh karena itu sebelum diakses varabel yang bertipe pointer harus dipersiapkan terlebih dahulu, yaitu dengan menggunakan perintah NEW.
Deklarasi : NEW(peubah bertipe pointer);
Contoh :
New(P1); New(P2);
Maka sekarang kita mempunyai dua buah simpul yang ditunjuk oleh P1 dan P2. Setelah itu kita dapat melakukan pengaksesan data, yaitu dengan menuliskan :
P1^.Nama_Peg := ‘Ariswan’;
P1^.Alamat := ‘Semarang’;
P1^.Pekerjaan := ‘Pengajar’;
Jika statemen New(P1)diulang beberapa kali maka hanya simpul yang terakhir yang bisa dimasup. Hal ini terjadi karena setiap kali kita memberikan statemen New(P1) maka nilai P1 yang lama akan terhapus. Dengan terhapusnya nilai P1 maka secara otomatis simpul yang ditunjuk oleh P1 tidak ditunjuk lagi dan tidak ditunjuk pula oleh pointer yang lain sehingga karena alamatnya tidak dapat ditentukan maka simpul tersebut tidak dapat dimasup lagi.
Dari sini dapat dilihat bahwa sifat kedinamisan pointer agak tersamar, disebabkan apabila kita menghendaki sejumlah simpul aktif dalam pengingat maka kita perlu menyediakan sejumlah pointer yang sesuai untuk masing-masing simpul. Oleh karena itu, apabila kita hendak mempunyai sebuah peubah yang benar-benar dinamis maka peubah itu harus mampu memasup sejumlah lokasi tertentu.
Untuk itu akan diperkenalkan apa yang dinamakan sebagai Senarai Berantai (Linked List).
Operasi Pada Pointer
Secara umum ada 2 operasi yang dapat dilakukan dengan tipe data pointer, yaitu :
1. Mengkopy pointer, sehingga sebuah simpul akan ditunjuk oleh lebih dari sebuah pointer
2. Mengkopy isi dari simpul, sehingga dua atau lebih simpul yang ditunjuk oleh pointer yang berbeda mempunyai isi yang sama
Catatan :
Syarat yang harus dipenuhi oleh kedua operasi tersebut adalah bahwa pointer-pointer yang akan dioperasikan harus mempunyai deklarasi yang sama.
· Jika dalam statemen pemberian tanda ^ tidak diberikan maka operasinya dinamakan sebagai mengkopi pointer, dengan konsekuensi simpul yang ditunjuk oleh suatu pointer akan bisa terlepas dan tidak dapat dimasup lagi.
Contoh : P1 := P2 ;
· Jika tanda ^ diberikan maka operasinya dinamakan sebagai operasi mengkopi isi simpul pointer, dengan konsekuensi bahwa isi dua buah simpul atau lebih akan menjadi sama.
Contoh : P1^ := P2^ ;
Menghapus Pointer
Statement yang digunakan untuk menghapus pointer adalah Dispose, yang mempunyai bentuk umum :
Dispose(peubah) ;
dengan : peubah = sebarang peubah yang bertipe pointer.
Catatan :
Setelah suatu pointer dihapus maka lokasi yang semula ditempati oleh simpul yang ditujuk oleh pointer tersebut akan bebas, sehingga bisa digunakan oleh peubah yang lain.
SENARAI BERANTAI ( LINKED LIST )
Cara lain untuk menyimpan sekumpulan data selain dengan menggunakan record adalah dengan menggunakan bantuan tipe data pointer. Dalam hal ini, masing-masing data dengan sebuah medan yang bertipe pointer perlu digunakan.
Salah satu struktur data dinamis yang paling sederhana adalah Senarai Berantai (Linked List). Yaitu kumpulan komponen (node) yang disusun secara berurutan dengan menggunakan bantuan pointer. Node ini terbagi menjadi dua bagian yaitu bagian medan informasi, yang berisi informasi yang akan disimpan atau diolah dan bagian penyambung (link field), yang berisi alamat simpul selanjutnya.
Operasi Pada Senarai Berantai :
1. Menambah Simpul di Belakang
Misal dideklarasikan:
Type Point = ^Data ;
Data = record
Info : char ;
Berikut : Simpul
End;
Var Elemen : char ;
Awal, Akhir, Baru : Simpul ;
Untuk menyambung simpul yang ditunjuk oleh Akhir dan Baru maka pointer pada simpul yang ditunjuk oleh Akhir dibuat sama dengan Baru , kemudian diubah pointer Akhir sama dengan Baru.
Procedure Tambah_Belakang(Awal,Akhir,Elemen: Data);
Var Baru : point;
Begin
New(Baru); Baru^.Info := elemen;
If Awal = NIL then
Awal:= Baru
Else Akhir^.Berikut := Baru;
Akhir:= Baru; Akhir^.Berikut:= NIL;
End;
2. Menambah Simpul di Depan
Pertama kali pointer pada simpul yang ditunjuk oleh pointer Baru dibuat sama dengan Awal. Kemudian Awal dibuat sama dengan Baru. Dengan cara ini maka simpul baru akan selalu diperlakukan sebagai simpul pertama dalam senarai.
Procedure Tambah_Depan(var Awal,Akhir: point; Elemen:Data);
Var Baru : point;
Begin
New(Baru); Baru^.Info :=Elemen;
If Awal= NIL then Akhir:= Baru
Else Baru^.Berikut:= Awal;
Awal := Baru;
End;
3. Menambah/ menyisipkan Simpul di Tengah
Untuk menambah simpul ditengah maka kita perlu sebuah pointer lain misal dinamakan Bantu. Dalam hal ini simpul baru akan diletakkan setelah simpul yang ditunjuk oleh pointer Bantu. Pertama kali ditentukan dimana simpul baru akan ditempatkan. Kemudian pointer pada simpul yang ditunjuk oleh Baru dibuat sama dengan pointer pada simpul yang ditunjuk oleh Bantu. Selanjutnya pointer pada simpul yang ditunjuk oleh simpul Bantu dibuat sama dengan Baru. Urutan kedua proses ini tidak boleh dibalik.
Procedure Tambah_Tengah(Var Awal,Akhir: point; Elemen: Dat);
Var Baru,Bantu : point;
Begin
New(Baru); Baru^.Berikut:= Elemen;
If Awal = NIL then
Begin
Awal:= Baru; Akhir:= Baru;
End
Else
Begin
Bantu:= Awal;
While (Elemen > Bantu^.Berikut^.Info) and (Bantu <> NIL) then
Bantu:= Bantu^.Berikut;
Baru^.Berikut:= Bantu^.Berikut;
Bantu^.Berikut:= Baru;
End;
End;
4. Menghapus Simpul Pertama
Simpul yang dapat dihapus oleh operasi penghapusan simpul adalah simpul yang berada sesudah simpul yang ditunjuk oleh suatu pointer, kecuali untuk simpul pertama.
Untuk menghapus simpul pertama, maka pointer Bantu kita buat sama dengan pointer Awal. Kemudian pointer Awal kita pindah dari simpul yang ditunjuk oleh pointer Bantu. Selanjutnya, simpul yang ditunjuk oleh pointer Bantu kita Dispose.
Procedure Hapus_Awal_Simpul(var Awal, Akhir: point; Elemen: Dat);
Var Hapus: point;
Begin
Awal:= Awal^.Berikut;
Dispose(Hapus);
End;
5. Menghapus Simpul di Tengah atau Terakhir
Pertama kita letakkan pointer Bantu pada simpul di sebelah kiri simpul yang akan dihapus. Simpul yang akan dihapus kita tunjuk dengan pointer lain, misalnya Hapus. Kemudian pointer pada simpul yang ditunjuk oleh Bantu kita tunjukkan pada simpul yang ditunjuk oleh pointer pada simpul yang akan dihapus. Selanjutnya simpul yang ditunjuk oleh pointer Hapus kita Dispose.
Procedure Hapus_Awal_Simpul(var Awal, Akhir: point; Elemen: Dat);
Var Bantu, Hapus : point;
Begin {senarai masih kosong}
If awal= NIL then
Writeln(‘Searai berantai masih kosong !’)
Else
Begin {menghapus simpul diawal}
Hapus:= Awal;
Awal:= Hapus^.Berikut;
Dispose(Berikut);
End
Else {menghapus simpul ditengah atau akhir}
Begin
Bantu:= Awal;
While (Elemen <> Bantu^.info) and (Bantu^.Next <> NIL) do
Bantu:= Bantu^.Berikut;
Hapus:= Bantu^.Berikut;
If Hapus <> NIL then
Begin
If Hapus = Akhir then
Begin
Akhir:= Bantu;
Akhir^.Berikut:= NIL;
End
Else Bantu^.Berikut:= Hapus^.Berikut;
Dispose(Hapus);
End
Else writeln(‘Tidak ketemu yang dihapus !!’);
End;
End;
6. Membaca Isi Senarai Berantai secara Maju
Pertama kali kita atur supaya pointer Bantu menunjuk ke simpul yang ditunjuk oleh pointer Awal. Setelah isi simpul itu dibaca, maka pointer Bantu kita gerakkan ke kanan untuk membaca simpul berikutnya. Proses ini kita ulang sampai pointer Bantu sama dengan pointer Akhir.
Procedure Baca_Maju(Awal,Akhir : point);
Var Bantu : point;
Begin
Bantu:= Awal;
Repeat
Write(Bantu^.info:2);
Bantu:= Bantu^.Berikut;
Until Bantu = NIL;
Writeln;
End;
7. Membaca Isi Senarai Berantai secara Mundur
Ada 2 cara membaca mundur isi dari Senarai Berantai, yaitu dengan cara biasa seperti diatas atau dengan memanfaatkan proses rekursi. Cara pertama yaitu kita atur pointer Bantu sama dengan pointer Awal. Berikutnya, pointer awal kita arahkan ke simpul Akhir dan kita pakai pointer lain misalkan Bantu1 untuk bergerak dari simpul pertama sampai simpul sebelum simpul terakhir. Langkah selanjutnya adalah mengarahkan medan pointer dari simpul terakhir ke simpul Bantu1. Langkah ini diulang sampai pointer Akhir Berimpit dengan pointer Bantu. Cara kedua dengan rekursi. Caranya hampir sama dengan cara membaca senarai berantai secara maju hanya saja pencetakan isi simpul ditunda sampai pointer Bantu sama dengan pointer akhir.
Procedure Baca_Terbalik(var Awal,Akhir: point);
Var Bantu,Bantu1 : point;
Begin
Bantu:= Awal;
Awal:= Akhr;
Repeat
Bantu1:=Bantu;
While Bantu1^.Berikut <> Akhir do
Bantu1:= Bantu1^.Berikut;
Akhir^.Berikut:= Bantu1;
Akhir:= Bantu1;
Until Akhir = Bantu;
Akhir^.Berikut:= NIL;
End;
Dengan cara rekursi :
Procedure Terbalik(Bantu: point);
Begin
If Bantu <> NIL then
Begin
TERBALIK(Bantu^.Berikut);
Write(Bantu^.Info:2);
End;
End;
8.Mencari Data dalam Senarai Berantai
Misalkan data yang dicari disimpan dalam peubah Elemen. Pertama kali, pointer Bantu dibuat sama dengan pointer Awal. Kemudan isi simpul yang ditunjuk oleh pointer Bantu dibandingkan dengan Elemen. Jika belum sama, maka pointer Bantu dipindah ke simpul disebelah kanannya dan proses perbandingan diulang lagi sampai bisa ditentukan apakah Elemen ada dalam senarai berantai yang dimaksud atau tidak.
Function Cari_Data(Awal: point; Elemen : Dat): Boolean;
Var ketemu: Boolean;
Begin
Ketemu: false;
Repeat
If Awal^.info = Elemen then
Ketemu:= true
Else
Awal:= Awal^.Berikut;
Until (ketemu) or (Awal = NIL);
Cari_Data:= ketemu;
end;
Tidak ada komentar:
Posting Komentar