ADT
adalah definisi TYPE dan sekumpulan PRIMITIF (operasi dasar) terhadap TYPE
tersebut. Selain itu, dalam sebuah ADT yang lengkap, disertakan pula definisi
invarian dari TYPE dan aksioma yang berlaku. ADT merupakan definisi statik. Definisi type dari sebuah ADT
dapat mengandung sebuah definisi ADT lain.
Misalnya
:
Ø ADT
Waktu yang terdiri dari ADT JAM dan ADT DATE
Ø GARIS
yang terdiri dari dua buah POINT
Ø SEGI4
yang terdiri dari pasangan dua buah POINT (Top, Left) dan (Bottom, Right)
Pentingnya
sebuah ADT (Abstract Data Type) :
Ø Struktur yang
besar memungkinkan sistem menjadi komponen berlapis.
Ø Memungkinkan
kode program menjadi lebih generik / reusable.
Ø Biarkan
fokus apa (spesifikasi) untuk dipisahkan dari bagaimana (implementasi)
Ø Digunakan
modularitas untuk perubahan lokal
Type
diterjemahkan menjadi type terdefinisi dalam bahasa yang bersangkutan, misalnya
menjadi record
dalam bahasa Ada/Pascal atau struct dalam bahasa C.
Dua jenis tipe data :
1. Opaque data types
Yaitu
di mana representasi tidak
diketahui pengguna.
2. Transparent data types
Yaitu
di mana representasi yang
menguntungkan diketahui pengguna: - yaitu encoding diakses secara langsung dan
/ atau dimodifikasi oleh pengguna.
Bagaimana
merancang sebuah data type :
Langkah
1 : Specification
Ø Buatlah daftar operasi (hanya sebuah nama) pikirkan apa
keperluannya. Meninjau dan memperbaiki daftar.
Ø Tentukan setiap konstanta yang mungkin diperlukan.
Ø Jelaskan parameter operasional
secara rinci.
Ø Jelaskan semantik operasi (apa yang akan dilakukan) setepat
mungkin.
Langkah
2 : Application
Ø Mengembangkan aplikasi nyata atau imajiner untuk menguji
spesifikasi.
Ø Hilang atau operasi lengkap yang ditemukan sebagai efek
samping mencoba untuk menggunakan spesifikasi.
Langkah
3 : Implementation
Ø Tentukan representasi yang sesuai.
Ø Melaksanakan operasi.
Ø Test, debug, dan merevisi.
Primitif,
dalam konteks prosedural, diterjemahkan menjadi fungsi atau prosedur. Primitif
dikelompokkan menjadi :
Ø Konstruktor/Kreator,
pembentuk nilai type. Semua objek
(variabel) bertype tersebut harus melalui konstruktor. Biasanya namanya diawali
Make.
Ø Selektor,
untuk mengakses komponen tye (biasanya namanya diawali dengan Get)
Ø Prosedur,
pengubah nilai komponen (biasanya namanya diawali Get)
Ø Validator
komponen type, yang dipakai untuk meng_test apakah dapat membentuk type sesuai
dengan batasan.
Ø Destruktor/Dealokator,
yaitu untuk “menghancurkan” nilai objek (sekaligus memori penyimpanannya)
Ø Baca/Tulis,
untuk interface dengan input/output device.
Ø Operator
relational, terhadap type tersebut untuk mendefinisikan lebih besar, lebih
kecil, sama dengan, dan sebagainya.
Ø Aritmatika,
terhadap type tersebut karena biasanya aritmatika dalam bahasa pemrograman
hanya terdefinisi untuk bilangan numerik.
Ø Konversi,
dari type tersebut ke type dasar dan sebaliknya.
ADT
biasanya diimplementasi menjadi dua buah modul, yaitu :
1. Definisi/Spesifikasi
Type dan Primitif.
a. Spesifikasi
type sesuai dengan bahasa yang bersangkutan.
b. Spesifikasi
dari primitif sesuai dengan kaidah dalam konteks prosedural, yaitu :
Ø Fungsi
: nama, domain, range dan prekondisi
jika ada.
Ø Prosedur
: Initial State, Final State dan Proses
yang dilakukan.
2. Body/realisasi
dari primitif, berupa kode program dalam bahasa yang bersangkutan. Realisasi
fungsi dan prosedur harus sedapat mungkin memanfaatkan selektor dan
konstruktor.
Supaya
ADT dapat di-test secara tuntas, maka dalam hal ini setiap kali membuat sebuah
ADT, harus disertai dengan sebuah program utama yang dibuat khusus untuk
meng_test ADT tersebut, yang minimal mengandung pemakaian (call) terhadap setiap fungsi dan prosedur dengan mencakup semua
kasus parameter. Program utama yang khusus dibuat untuk test ini disebut
sebagai driver. Urutan pemanggilan
harus diatur sehingga fungsi/prosedur yang memakai fungsi/prosedur lain harus
sudah ditest dan direalisasikan terlebih dulu.
Di
dalam modul ADT tidak terkandung definisi variabel. Modul ADT biasanya
dimanfaatkan oleh modul lain, yang akan mendeklarasikan variabel bertype ADT
tersebut dalam modulnya. Jadi ADT bertindak sebagai Supplier (penyedia type dan primitif), sedangkan modul pengguna
berperan sebagai Client (pengguna)
dari ADT tersebut. Biasanya ada sebuah pengguna yang khusus yang disebut
sebagai main program (program utama) yang memanfaatkan langsung type
tersebut.
Contoh
ADT :
Complex
Number
ADT
Example :
Class Complex
{
private …
minus(Complex
c); // this.minus(c) mutator
times(Complex
c); // this.times(c)
getImajiner();
// return this.i asseccor
}
|
Implementasi
ADT JAM dalam bahasa Algoritmik :
{
Definisi TYPE JAM <HH:MM:SS> }
TYPE Hour
: integer [0..23]
TYPE
Minute : integer [0..59]
TYPE
Second : integer [0..59]
TYPE JAM
: < HH: Hour, {Hour [0..23]}
MM: Minute, {Minute [0..59]}
SS: Second, {Second [0..59]} >
{*** **}
{DEFINISI PRIMITIF}
{*** **}
{
KELOMPOK VALIDASI TERHADAP TYPE }
{*** **}
Function IsJValid (H,M,S:integer)->boolean
{Mengirim true jika H,M,S dapat membentuk J yang
valid}
{Konstruktor: Membentuk sebuah JAM dari
Komponen-komponen}
Function MakeJam (HH:integer, MM:integer,
SS:integer)->JAM
{Membentuk sebuah JAM dari komponen-komponennya
yang valid}
{Pre cond: HH,MM,SS valid untuk membentuk JAM}
{**
Operasi terhadap komponen : selektor Get dan Set **}
{**
Selektor **}
Function
Hour(J:JAM)->integer
{Mengirimkan
bagian HH(Hour) dari JAM}
Function
Minute(J:JAM)->integer
{Mengirimkan
bagian MM(Minute) dari JAM}
Function
Second(J:JAM)->integer
{Mengirimkan
bagian SS(Second) dari JAM}
{**
Pengubah nilai komponen **}
Procedure
SetHH(Input/Output J:JAM, Input newHH:integer)
{Mengubah
nilai komponen HH dari J}
Procedure
SetMM(Input/Output J:JAM, Input newMM:integer)
{Mengubah
nilai komponen MM dari J}
Procedure
SetSS(Input/Output J:JAM, Input newSS:integer)
{Mengubah
nilai komponen SS dari J}
{*** **}
{ KELOMPOK
BACA/TULIS }
Procedure
BacaJam (Input/Output J:JAM)
{I.S.
: J tidak terdefinisi}
{F.S.
: J terdefinisi dan merupakan jam yang valid}
{Proses
: mengulangi membaca komponen H,M,S sehingga membentuk J yang valid}
{***
**}
Procedure
TulisJam (Input J:JAM)
{I.S.
: J sembarang}
{F.S.
: Nilai J ditulis dengan format HH:MM:SS}
{Proses
: menulis nilai ke layar}
{***
**}
{KELOMPOK
KONVERSI TERHADAP TYPE}
{*** **}
Function
JamToDetik (J:JAM)-> integer
{Diberikan
sebuah JAM, mengkonversi menjadi Detik}
{Rumus
: detik = 3600*hour+60*minute+second}
{nilai
maksimum = 3600*23+59*60+59*60}
{hati-hati
dengan representasi integer pada bahasa implementasi}
{kebanyakan
sistem mengimplementasi integer,bernilai maksimum kurang dari nilai maksimum
hasil konversi}
{***
**}
Function
DetikToJam (N:integer)-> JAM
{Mengirim
konversi detik ke JAM}
{pada
beberapa bahasa, representasi integer tidak cukup untuk menampung N}
{***
**}
{
KELOMPOK OPERASI TERHADAP TYPE }
{*** **}
{**
Kelompok Operator Relational }
Function
JEQ(J1:JAM, J2:JAM)-> boolean
{Mengirimkan
true jika J1=J2, false jika tidak}
Function
JNEQ(J1:JAM, J2:JAM)-> boolean
{Mengirimkan
true jika J1 tidak sama dengan J2}
Function
JLT(J1:JAM, J2:JAM)-> boolean
{Mengirimkan
true jika J1<J2, false jika tidak}
Function
JGT(J1:JAM, J2:JAM)-> boolean
{Mengirimkan
true jika J1>J2, false jika tidak}
{*****
Operator Aritmatika JAM *****}
Function
JPlus(J1:JAM, J2:JAM)-> JAM
{Menghasilkan
J1+J2, dalam bentuk JAM}
Function
JMinus(J1:JAM, J2:JAM)-> JAM
{Menghasilkan
J1-J2, dalam bentuk JAM}
{Precond
: J1>=J2}
Function
NextDetik(J:JAM)-> JAM
{Mengirim
1 detik setelah J dalam bentuk JAM}
Function
NextDetik(J:JAM, N:integer)-> JAM
{Mengirim
N detik setelah J dalam bentuk JAM}
Function
PrevDetik(J:JAM)-> JAM
{Mengirim
1 detik sebelum J dalam bentuk JAM}
Function
PrevDetik(J:JAM, N:integer)-> JAM
{Mengirim
N detik sebelum J dalam bentuk JAM}
Function
Durasi(Jaw:JAM, Jakh:JAM)-> integer
{Mengirim
Jakh-Jaw dalam Detik, dengan kalkulasi}
{Hasilnya
negatif jika Jaw > Jakh}
|
Catatan
Implementasi :
Di
dalam implementasi dengan bahasa C, di mana representasi integer ada
bermacam-macam, maka harus berhati-hati, misalnya :
1. Dalam
menentukan range dari fungsi Durasi,
karena nilai detik dalam dua puluh empat jam melebihi representasi int.
2. Representasi
Hour, Minute dan Second terpaksa harus dalam bentuk int dan tidak mungkin
dibatasi dengan angka yang persis. Itulah sebabnya fungsi validitas terhadap
type diperlukan.
Banyak
juga contoh ADT di dalam Data Structure :
-
ADT Integer
-
ADT Primitive
-
Linked
List ADT
-
Linked
List Iteration ADT
-
Ordered
List ADT
-
Sorted
List ADT
-
Double
Linked List ADT
-
Circular
Linked List ADT
