struktur data i

Download Struktur Data I

Post on 18-Jun-2015

169 views

Category:

Documents

17 download

Embed Size (px)

TRANSCRIPT

Struktur data I ABSTRACT DATA TYPESHermawan ST, Teknik Informatika Universitas Trunojoyo

DefinisiAbstract Data Type (ADT) dapat didefinisikan:1. Tipe penyimpanan data secara berkelompok yang mampu membungkus berbagai

tipe data baik homogen maupun heterogen2. Spesifikasi dari sekumpulan data termasuk operasi yang dapat dilakukan pada

data tersebut3. Sekumpulan data dan operasi terhadap data tersebut yang definisi-nya tidak

bergantung pada implementasi tertentu.

Data

Container

ADT dasar terdiri atas dua tipe: 1. ADT homogen Mampu menampung tipe data dasar yang homogen dengan pola list berindex

Indeks

1

2

3

4

Dalam hal ini disebut sebagai Array. Type ADT : Array [1..jumlah_index] of type data;

ADT dasar terdiri atas dua tipe: 1. ADT heterogen Mampu menampung tipe data dasar yang heterogen dengan pola record

Dalam hal ini disebut sebagai Record. Type ADT = record of I : integer; A : string; L : array [1..10] of real; end;

Kapan kita membutuh ADT? ADT diperlukan untuk membantu pemetaan data ADT membantu penentuan index data untuk mempermudah operasional pada data ADT membentuk obyek yang dapat digunakan ulang reusable.

OPERASIONAL DASAR ADTUntuk mempermudah operasional dalam ADT maka dapat dibuat operasional antrian, yang secara standar terdapat dua model, yakni STACK dan Queue. Sebuah Stack adalah kumpulan benda di mana hanya benda yang most recently inserted dapat diakses. (LIFO) Bayangkan setumpuk koran. Benda yang paling terakhir ditambahkan ditaruh di atas tumpukan (top). Operasi pada Stack membutuhkan waktu konstan (O(1)).

push

pop,top Contoh Interface stack : Most recent

void push(Benda x); Benda pop(); Benda top();

Least recent

OPERASIONAL DASAR ADTSedangkan Queue, Sebuah Queue adalah kumpulan benda di mana hanya benda yang least recently inserted dapat diakses. (FIFO) Bayangkan antrian printer job pada jaringan. Benda yang paling awal ditambahkan berada di depan antrian (front). Operasi pada Queue membutuhkan waktu konstan (O(1)).enqueue Most recent Contoh Interface queue : Least recent dequeue getFront

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 MAPNama: 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 QUEUEinsert deleteMin findMin Highest priorityPriority 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)

Contoh Implementasi:Jika Kelas struktur data adalah kumpulan data mahasiswa, dengan atribut adalah NIM, NAMA, ALAMAT, PRODI. Buatlah ADT list (array) dengan jumlah index jumlah mahasiswa dan mampu menampung data record mahasiswa dengan atributnya? NIM NAMA ALAMAT PRODI Index 1

Index n

Contoh Implementasi:NIM NAMA ALAMAT PRODI Deklarasi Type Mahasiswa = record nim : string; nama : string; alamat : string; prodi : integer; end; : array (1..n) of Mahasiswa; Kelas_SD : Data;

Data Var

TugasDari ADT contoh buatlah operasional: 1. STACK 2. QUEUE 3. Map Untuk input, baca dan cetak data.