Hermawan ST,

Teknik Informatika

Universitas Trunojoyo

Struktur data IABSTRACT DATA TYPES

� Definisi

Abstract Data Type (ADT) dapat didefinisikan:

1. Tipe penyimpanan data secara berkelompok yang mampu membungkus berbagaitipe data baik homogen maupun heterogen

2. Spesifikasi dari sekumpulan data termasuk operasi yang dapat dilakukan padadata tersebut

3. Sekumpulan data dan operasi terhadap data tersebut yang definisi-nya tidakbergantung pada implementasi tertentu.

Container

Data

ADT dasar terdiri atas dua tipe:

1. ADT homogenMampu menampung tipe data dasar yang homogen dengan pola list berindex

1 2 3 4Indeks

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

ADT dasar terdiri atas dua tipe:

1. ADT heterogenMampu menampung tipe data dasar yang heterogen dengan pola record

Dalam hal ini disebut sebagai Record.TypeADT = 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 operasionalpada data• ADT membentuk obyek yang dapat digunakan ulang reusable.

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

Leastrecent

Mostrecent

push pop,top

Contoh Interface stack :

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

Contoh Interface stack :

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

OPERASIONAL DASAR ADTSedangkan Queue,• Sebuah Queue adalah kumpulan benda di mana hanya benda yangleast 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 Least recent

dequeuegetFront

Contoh Interface queue :

void enqueue(Benda x);Benda dequeue();Benda getFront();

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 yangsama.Bayangkan peserta kuliah ini: Setiap peserta unik, tidak ada yang terdaftar duakali!

Contoh Interface set :

void add(Benda x);void remove(Benda x);boolean isMember(Benda x);

Contoh Interface set :

void add(Benda x);void remove(Benda x);boolean isMember(Benda x);

ADT MAP

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)?

Abdul Betty Chairul DianNama:

Nilai:

Contoh Interface sebuah Map :

void put(Kunci id, Nilai x);void remove(Kunci id);Nilai get(Kunci id);

Contoh Interface sebuah Map :

void put(Kunci id, Nilai x);void remove(Kunci id);Nilai get(Kunci id);

ADT PRIORITY QUEUE

Priority Queue adalah struktur data queue yang tiap elemen data dapat miliki nilaiprioritas. Data dengan nilai prioritas tertinggilah yang dapat diakses terlebih dulu.Bayangkan sebuah antrian pada printer jaringan. Misalkan ada sebuah permintaan cetakuntuk 100 halaman hanya beberapa detik lebih awal dari permintaan cetak selembarhalaman.

Highestpriority

insert deleteMin

findMin

Contoh Interface sebuah Priority Queue :

void insert(Benda x); (Menambahkan)void deleteMin(); (menghapus)Benda findMin(); (meng-akses)

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, denganatribut adalah NIM, NAMA, ALAMAT, PRODI.Buatlah ADT list (array) dengan jumlah index jumlah mahasiswa danmampu menampung data record mahasiswa dengan atributnya…?

NIM

NAMA

ALAMAT

PRODI

Index 1 Index n

Contoh Implementasi:NIM

NAMA

ALAMAT

PRODI

Deklarasi

TypeMahasiswa = recordnim : string;nama : string;alamat : string;prodi : integer;end;

Data : array (1..n) of Mahasiswa;Var

Kelas_SD : Data;

TugasDari ADT contoh buatlah operasional:1. STACK2. QUEUE3. Map

Untuk input, baca dan cetak data.