STRUKTUR DATA
POKOK BAHASAN - 5 ABSTRACT DATA TYPE
Oleh : NAZARUDDIN AHMAD, S.T, M.T
Design By mytemplate 2013
Abstract Data Types • Pada saat membuat program, biasanya digunakan untuk mencari solusi suatu problem • Problem dalam ‘real life’ – Kompleks – Perlu mengerti problem dengan baik untuk memisahkan bagian yang penting dari rinci yang tidak penting – Abstraksi
2
Abstract Data Types Contoh : Penanganan administrasi dalam sebuah fakultas Mahasiswa … ? Pegawai …. ? Informasi apa yang harus dicatat .. ?
3
Abstract Data Types Abstraksi menghasilkan model Model menaruh fokus pada hal-hal penting pada problem Mendefiniskan property problem
1. Data yang dipengaruhi 2. Operasi yang teridentifikasi
4
Abstract Data Type (ADT) adalah ... • Spesifikasi dari sekumpulan data termasuk operasi yang dapat dilakukan pada data tersebut. (Wikipedia) • Sekumpulan data dan operasi terhadap data tersebut yang definisi-nya tidak bergantung pada implementasi tertentu. (/www.nist.gov/dads/) • Definisi TYPE dan sekumpulan PRIMITF (operasi dasar) terhadap TYPE tersebut (Ingriani Liem, ITB)
5
Konsep ADT ADT membungkus (encapsulates) data dan operasi yang memanipulasi data tersebut. Data tersebut juga hanya bisa diakses lewat operasi tersebut.
r e
p o data
s n
a t i o
6
Modul ADT • ADT biasanya diimplementasikan menjadi 2 modul: – Definisi/Spesifikasi Type dan Primitif (Interface) • Spesifikasi type sesuai bahasa yang bersangkutan • Spesifikasi dari primitif sesuai kaidah prosedural: – Fungsi – Prosedur
– Body/realisasi dari primitif • Berupa kode program dalam bahasa yang bersangkutan.
• Agar ADT dapat dites, maka biasanya disertai program utama yang memanggil setiap fungsi/prosedur. Program utama ini disebut sebagai driver.
7
Interface • Spesifikasi Abstract Data Type biasa disebut sebagai interface. • Interface menyatakan apa yang dapat dilihat dan digunakan oleh programmer. • Dalam pemrograman, hal tersebut dinyatakan sebagai public method. • Operasi-operasi yang dapat dilakukan pada abstract data type dituliskan dalam interface dan dinyatakan public.
8
Pemisahan interface dengan implementasi • Pengguna dari sebuah abstract data type hanya perlu memikirkan dan mempelajari interface yang diberikan tanpa perlu mengetahui banyak bagaimana implementasi dilakukan. (prinsip: enkapsulasi) • Implementasi dapat saja berubah namun interface tetap. • Dengan kata lain, implementasi dari sebuah abstract data type dapat saja berbeda-beda namun selama masih mengikuti interface yang diberikan maka program yang menggunakan abstract data type tersebut tidak akan terpengaruh.
9
Struktur data = container
Container
• Sebuah struktur data dapat dipandang sebagai tempat penyimpanan benda (container). • Beberapa hal yang dapat dilakukan: – Menaruh benda – Mengambil benda – Mencari benda tertentu – Mengosongkannya (atau periksa apakah kosong) Contoh Interface struktur data :
Data
void add(Benda x); void remove(Benda x); Benda access(Benda x); void makeEmpty(); boolean isEmpty(); 10
ADT: List
Indeks
1
2
3
4
• Sebuah List adalah kumpulan benda di mana setiap benda memiliki posisi. • Setiap benda dalam List dapat diakses melalui indeks-nya. • Contoh paling gampang: array! Contoh Interface list :
void insert(int indeks, Benda x); void append(Benda x); void remove(int indeks); void remove(Benda x); Benda get(int indeks);
ADT: Stack push
• Sebuah Stack adalah kumpulan benda pop,top di mana hanya benda yang most recently inserted dapat diakses. • Bayangkan setumpuk koran. • Benda yang paling terakhir Most ditambahkan ditaruh di atas tumpukan recent (top). • Operasi pada Stack membutuhkan waktu konstan (O(1)). Contoh Interface stack : Least recent
void push(Benda x); Benda pop(); Benda top();
ADT: Queue enqueue
dequeue getFront
Most recent
Least recent
• Sebuah Queue adalah kumpulan benda di mana hanya benda yang least recently inserted dapat diakses. • Bayangkan antrian printer job pada jaringan. • Benda yang paling awal ditambahkan berada di depan antrian (front). • Operasi pada Queue membutuhkan waktu konstan (O(1)). Contoh Interface queue :
void enqueue(Benda x); Benda dequeue(); Benda getFront();
ADT: Set
tambah
• Set adalah struktur data yang tidak mengizinkan duplikasi data. • Bandingkan dengan struktur data lain yang mengizinkan kita menyimpan dua data yang sama. • Bayangkan peserta kuliah ini: Setiap peserta unik, tidak ada yang terdaftar dua kali! Contoh Interface set :
void add(Benda x); void remove(Benda x); boolean isMember(Benda x);
ADT: Map Nama:
Abdul
Betty
Chairul
Dian
Nilai:
• Map adalah struktur data yang berisi sekumpulan pasangan nama (keys) dan nilai (values) dari nama tersebut. • Nama (Keys) harus unik, tapi nilai (values) tidak. • Bayangkan basis-data yang berisi informasi peserta kuliah. Apa yang menjadi “nama” (keys)? Contoh Interface sebuah Map : void put(Kunci id, Nilai x); void remove(Kunci id); Nilai get(Kunci id);
ADT: Priority Queue insert
deleteMin findMin
Highest priority • Priority Queue adalah struktur data queue yang tiap elemen data dapat miliki nilai prioritas. Data dengan nilai prioritas tertinggilah yang dapat diakses terlebih dulu. • Bayangkan sebuah antrian pada printer jaringan. Misalkan ada sebuah permintaan cetak untuk 100 halaman hanya beberapa detik lebih awal dari permintaan cetak selembar halaman. Contoh Interface sebuah Priority Queue : void insert(Benda x); (Menambahkan) void deleteMin(); (menghapus) Benda findMin(); (meng-akses)
API vs doing it yourself Jika anda menggunakan framework atau software component, programmer lain dapat lebih mudah mengadaptasi program anda. Jika anda membuat implementasi sendiri, maka programmer lain belum tentu dapat dengan mudah mempelajari program anda. Namun demikian, sebagai mahasiswa/i ilmu komputer, perlu memahami bagaimana data tersusun dalam memory dan perlu memahami konsep-konsep apa yang mendasarinya. Tidak menutup kemungkinan untuk meng-extend/meng-implement Collections
Pemecahan Masalah dengan Tipe Terstruktur • Untuk memanipulasi data, C menyediakan semua operasi dasar yang dapat digunakan untuk memecahkan masalah dengan menggunakan tipe data standar • Kombinasian type tertentu yang didefinisikan user dengan sekumpulan operasi-operasi dasar yang membolehkan satu kebenaran untuk melihat tipe sebagai konsep kesatuan disebut
Abstract Data Type (ADT) • Contoh tipe data planet_t dan operasi-operasi dasarnya digambarkan sbb:
Contoh Studi Kasus untuk ADT • Tipe yang didefinisikan user untuk angka yang komplek • Analisa: – Angka yang komplek adalah angka dengan bagian real dan imaginer – Contoh : a+bi (a: real, b:imaginer) – Definisikan fungsi untuk melakukan operasi aritmetika dasar (penjumlahan, pengurangan, perkalian dan pembagian)
Desain • 2 aspek utama dari solusi masalah ini adalah : – Mendefinisikan struktur dari tipe yang didefinisikan user – Menentukan nama fungsi, parameter, dan tujuan dari tiap operasi
Desain (cont..) • Nama struktur yang didefinisikan sendiri : complex_t • Fungsi : – – – – –
Multiply_complex (untuk perkalian bil. komplek) Divide_complex (untuk pembagian bil. kompleks Abs_complex (untuk mendapatkan nilai absolut) Print_complex (untuk menampilkan hasil) Scan_complex (untuk melakukan pembacaan thd bil. Kompleks) – Add_complex (untuk menjumlahkan bil. Kompleks) – Substract_complex (untuk mengurangkan bil. Kompleks)
Spesifikasi dari Tipe complex_t dan operasi-operasi yang berlaku STRUCTURE: Angka kompleks adalah suatu object dari tipe complex_t yang terdiri dari sepasang nilai bertipe double . OPERATOR: /*Complex number input fuction returns standard scanning*/ int scan_complex(complex_t *c) /*output-address of complex variable to fill*/ /* Complex output fuction displays value as a+bi or a-bi Displays only a if imaginary part is 0 Display only bi if real part is 0 */ void print_complex(complex_t c) /* input-complex number to display */
Spesifikasi dari Tipe complex_t dan operasi-operasi yang berlaku (cont.) /*Returns sum of complex value c1 and c2*/ complex_t add_complex(complex_t c1,complex_t c2) /*input*/ /*Returns difference c1-c2*/ complex_t subtract_complex(complex_t c1,complex_t c2) /*input*/ /*Returns product of complex values c1 and c2*/ complex_t multiply_complex(complex_t c1,complex_t c2) /*input*/ /*Returns quotient of complex values(c1/c2)*/ complex-t divide-complex(complex_t c1,complex_t c2) /*input*/ /*Returns absolute value of complex number c*/ abs_complex(complex_t c) /*input*/
Latihan • Modifikasi kedua program sebelumnya dengan menggunakan ADT Jam, yang spefisikasinya seperti berikut: typedef struct { int Jam; int Menit; int Detik } jam; /* prototype */ int IsJamValid(int j, int m, int d); /* mengembalikan 1 jika valid dan 0 jika tidak valid */ jam MakeJam(int j, int m, int d); /* Konstruktor, membentuk jam dari komponen yang valid*/
Latihan (cont.) void SetJam(jam *J, int j, int m, int d); /* mengeset jam sesuai dengan parameter input */ void ResetJam(jam *J); /* mengisi sebuah jam dengan 00:00:00 */ void TulisJam(jam J); /* menulis sebuah jam */
int JamKeDetik(jam J); /* konversi jam ke detik */ jam DetikKeJam(int d); /* konversi dari detik ke jam */
jam JPlus(jam J1, jam J2); /* menghasilkan J1+J2, dalam bentuk jam */ jam JMinus(jam J1, jam J2); /* menghasilkan J1-J2, dalam bentuk jam */
Contoh : Titik Koordinat #include <stdio.h> #include <math.h> #include
typedef struct { int sumbu_x; int sumbu_y; }Titik; Titik Make_Titik (int x, int y) { Titik t; t.sumbu_x = x; t.sumbu_y = y; return t; }
Contoh : Titik Koordinat (Lanj.) void Display(Titik T) // merupakan fungsi untuk menampilkan Titik di layar { printf("koordinat x = %d ", T.sumbu_x); printf("koordinat y = %d \n", T.sumbu_y); } float Jarak(Titik T1, Titik T2) //fungsi untuk menghitung jarak antara dua titik T1 dan T2 { int A, B; float jarak; A = (T2.sumbu_y - T1. sumbu_y); B = (T2.sumbu_x - T1. sumbu_x); jarak = sqrt(A*A + B*B); return jarak; }
Contoh : Titik Koordinat (Lanj.) int main() { Titik T1; // menciptakan instans dari titik T1 = Make_Titik(1,1); Titik T2; // menciptakan titik T2 T2 = Make_Titik(4,3);
Display(T1); Display(T2); printf("jarak = %f", Jarak(T1, T2)); getch (); return 0; }
Contoh : Titik Koordinat (Lanj.) Outputnya :
