tipe data abstrak

1. Tipe Data Abstract Abstract Data Type (ADT)
2. Pengantar • Tipe data dapat kaji dari sisi kelas maupun level abstraksinya. Terdapat dua kelas tipe data kalau kita lihat dari kompleksitasnya, yaitu : • Tipe data atomik Tipe data yang dipandang sebagai satu kesatuan tunggal dan tidak dapat dipecah-pecah lagi (nondecomposible entity). Contoh : Integer, Char, float/real. • Tipe data berstruktur Tipe data yang dipandang sebagai satu kesatuan tunggal dan dapat dipecah-pecah lagi(decomposable entity ). Contoh : Array, Struct/Record, dll.
3. Sedangkan atas level abstraksinya, tipe data dapat dikelompokkan ke dalam tiga level, yaitu :- • Tipe data abstrak/ADT Tipe data yang merupakan hasil imajinasi kita dengan memberikan beberapa batasan domain maupun operasinya. Contoh : usia, daftarnilai.- • Tipe data virtual Tipe data yang ada/dikenal oleh bahasapemrograman. Contoh : integer, array of integer. • Tipe data fisikal Tipe data yang nyata dalam main processor.
4. Defenisi • ADT adalah definisi dari TYPE dan sekumpulan operasi dasar (PRIMITIF) dari TYPE tersebut • Definisi TYPE dari sebuah ADT dapat mengandung definisi ADT lainnya. Contoh: ADT WAKTU terdiri atas ADT JAM dan ADT DATE ADT GARIS memiliki dua buah TITIK • TYPE diterjemahkan menjadi data type yang terdefinisi sesuai bahasa pemrograman, misalnya struct dalam C, record dalam Pascal, class dalam C++/Java • PRIMITIF, dalam konteks prosedural, diterjemahkan sebagai fungsi atau prosedur
5. PRIMITIF dikelompokkan menjadi: • Constructor/Creator, pembentuk nilai awal (inisialisasi). Biasanya diawali dengan make. • Selector/Accessor, untuk mengakses komponen ADT. Biasanya diawali dengan get. • Mutator, prosedur pengubah nilai komponen. Biasanya diawali dengan set. • Validator, penguji apakah nilai type sesuai batasan. • Destructor/Deallocator, untuk menghapus nilai obyek, sekaligus lokasi memori penyimpanannya • Read/Write, untuk antar-muka dengan input/output devices. • Relational Operator, untuk mendefinisikan hubungan relasi lebih besar, lebih kecil, dsb. • Arithmetic, karena biasanya operasi aritmatika hanya terdefinisi untuk bilangan numerik, bukan obyek sesuai ADT yang ada. • Convert, untuk konversi ke tipe data dasar, atau sebaliknya
6. Modul Program • Modul pada bahasa pemrograman berorientasi objek, diimplementasikan dengan kelas dengan sekumpulan layanan berupa metode publik yang dapat dipanggil oleh pemakai kelas • Pada bahasa prosedural, modul diimplementasikan sebagai struktur, dan sekumpulan operasi berupa prosedur dan fungsi yang dipanggil pemakai modul lewat pemanggilan prosedur dan fungsi.
7. Abstraksi Data (ADT) Persoalan abstraksi data, yaitu : • Struktur data seharusnya menjadi satu bagian internal yang tersembunyi • Pemakai modul tidak perlu mengetahui struktur data yang digunakan untuk mengimplementasikan suatu modul • Pemakai modul hanya diberikan gambaran perilaku, bukan struktur internal dari modul • Fokus pada prilaku objek, membentuk basis pemrograman berorientasi objek.
8. • Abstraksi data memungkinkan kitamemperluas bahasa pemrograman dengan tipe data baru • Abstraksi data memungkinkan kita mengabstraksikan rincian rincian cara data diimplementasikan, menjadi bagaimana objek-objek berprilaku • Abstraksi data berisi sekumpulan objek • Abstraksi data pada prinsipnya merupakan dasar pemrograman berorientasi objek(Object Oriented Programming /OOP)
9. Pengertian • ADT adalah kumpulan nilai dan kumpulan operasi yang diizinkan • ADT memungkinkan pendefinisian suatu himpunan nilai di variable disertai operasi-operasi yang izinkan padanya • ADT menyatakan prilaku suatu variabel.
10. ADT biasanya diimplementasikan menjadi dua modul: • Definisi/Spesifikasi dari TYPE dan PRIMITIF • Spesifikasi TYPE sesuai bahasa • Spesifikasi PRIMITIF sesuai konteks (fungsi ataukah prosedur) • Body, berupa kode program Supaya ADT dapat diuji tuntas, maka harus dilengkapi dengan program utama yang mengandung pemakaian (call) terhadap setiap PRIMITIF dalam ADT. Disebut sebagai DRIVER.
11. ADT dalam bahasa Pemrograman Realisasi ADT dalam beberapa bahasa pemrograman BAHASA SPESIFIKASI BODY PASCAL Unit Interface Implementasi C File header *.h File kode program (*.c) C++ File header *.h File kode program (*.cpp) JAVA Class Public Class
12. ADT dalam Struktur Data • Sering terjadi salah pengertian antara ADT dan Struktur Data. • Struktur data lebih kongkret, merupakan teknik atau strategi untuk mengimplementasikan sebuah ADT (ADT lebih merupakan deskripsi logika) • Struktur data merupakan cara membentuk, mengkonstruksi, mengaransemen, mengkomposisikan ataupun mengorganisasikan data (ADT) • ADT: stack, queue, priority queue, dictionary, sequence, set • Struktur Data: array, linked list, hash table (open, closed, circular hashing), trees (binary search trees, heaps, AVL trees, 2-3 trees, tries, red/black trees, B-trees)
13. Contoh Kasus Diketahui kumpulan bilangan bulat (1 s/d 1000) sebanyak maksimum 107 bilangan. Selanjutnya, buat program untuk mencari apakah suatu nilai bilangan ada ataukah tidak ada di dalam kumpulan data tersebut. • Contoh input : 5 9 8 7 6 8 7 6 2 3 4 5 1 -9 4 7 9 10 3 • Contoh output 7 ada 9 ada 10 tidak ada 3 ada
14. Solusi • Alternatif 1 (indeks array terlalu besar, error) 1. Baca semua data dan masukkan ke dalam array 2. Sort 3. Search • Alternatif 2 (optimum) 1. Karena nilai data bulat 1-1000, maka buat indeks array sebanyak 1000 (0- 999) 2. Baca data, dan isi nilai 1 ke array dengan indeks=data-1 Bagaimana kalau bilangan yang diketahui adalah riil (bukan bulat)? Tidak dapat menggunakan Alternatif 2. • Pada kasus ini, duplikasi bilangan tidak berpengaruh, sehingga sangat baik kalau kumpulan bilangan tersebut direpresentasikan sebagai suatu himpunan (set). Oleh karena itu, dapat menggunakan ADT set
15. Tujuan ADT • ADT memisah struktur penyimpanan (lokasi memori) dari perilaku. • ADT menyembunyikan informasi (information hiding) atau pengkapsulan (encapsulation), yaitu : • Perubahan implementasi ADT tidak mengubah teksprogram lain bila antarmuka (interface) tidakberubah • Pemakaian dan pembuatan ADT dapat dilakukan terpisah, hanya perlu kesepakatan antarmuka pemakaian ADT • ADT merupakan sarana pemrograman modular dan menjadi landasan pembentukan tim pemrograman
16. • ADT merupakan sarana untuk membuat modul-modul yang menyerupai dengan konsep-konsep yang ditemukan pada domain persoalan • Pada sistem akademik ditemukan konsep student, lecturer, room dll • Maka dapat dibuat ADT student, ADTlecturer, ADT Room dsb, yang serupa namanya dengan konsep konsep yang dijumpai pada domain persoalan.
17. Pembuatan ADT Tahap pembuatan ADT : •Spesifikasi •Implementasi •Pemrograman
18. Contoh Spesifikasi untuk tipe data abstrak letterstring : • Elements : Nilai elemennya adalah karakter ‘a’-’z’,’A’-’Z’, dan termasuk juga spasi. Kita sebut nilai-nilai tersebut sebagai kumpulan karakter(letters). • Structure : Terdapat hubungan secara linear diantara elemen letters di dalam suatu string. • Domain : letterstring berisi 0 sampai 80 karakter.Domain dari tipe letterstring adalah seluruh kemungkinan nilai yang memenuhi aturan- aturan tersebut.
19. Operations:letter leftletter( letterstring s) Kondisi awal :Jumlah karakter input s minimal 1. Kondisi akhir :leftletter berisi karakter awal (paling kiri) didalam string s. append( letter l; letterstring s) Kondisi awal : Jumlah karakter input s kurang dari 80. Kondisi akhir :String s lebih panjang dibandingkan sebelumnya, dan isi l adalah karakter terbaru dan berada paling kanan di dalam s. Boolean empty( letterstring s ) Kondisi awal :Tidak ada. Kondisi akhir :Jika s tidak berisi satupun karakter maka empty bernilai true selain itu empty bernilai false.
20. • Boolean full( letterstring s ) Kondisi awal :Tidak ada. Kondisi akhir :Jika s berisi 80 karakter maka full bernilai true selain itu full bernilai false. • reverse( letterstring s ) Kondisi awal :Tidak ada. Kondisi akhir :Urutan dari isi s dibalik, sehingga elemen pertama dan terakhir bertukar tempat, elemen kedua daria wal dan kedua dari akhir bertukar tempat, demikian seterusnya. Dengan memilih bahasa C sebagai bahasa yang akandigunakan untuk penulisan program, maka representasi danimplementasinya adalah sebagai berikut :
21. Representation struct letterstring { int n; letter str[80]; }; Implementation int empty( letterstring s ) { if (s.n<1) return(1); else return(0); }; int full( letterstring s ) { if (s.n>=80) return(1); else return(0); };
22. void append( letter l; letterstring *s) { if (s.n<80) s.str[++s.n] = l; }; letter leftletter( letterstring s) { if (s.n>0) return(s.str[0] ); }; void reverse ( letterstring *s ) { int i; letterstring temp; for(i=0;i<80;i++) temp.str[i] = temp.str[80-i+1]; for(i=0;i<80;i++) s.str[i] = temp.str[i]; };

(sumber) https://www.slideshare.net/