ALGORITMA

BAB 1

1.1 Struktur Data

Sebelum dibahas tentang pengertian dari Struktur Data, Tipe Data dan Abstraksi Data kita akan mendefinisikan kata Data dan Struktur terlebih dahulu, karena kedua kata itu akan banyak dipergunakan dalam buku ini.

Data adalah:

Bahan yang digunakan dalam perhitungan atau operasi untuk menghasilkan informasi yang berguna.

Sedangkan struktur mempunyai pengertian sebagai berikut:

Struktur adalah pengaturan atau hubungan

Maka struktur data dapat didefinisikan sebagai:

Pengaturan atau hubungan dari data di dalam suatu sistem.

Kita tentu sering bekerja dengan program, pertanyaan yang mungkin timbul adalah, “dimana letak kegunaan dari struktur data dalam hubungannya dengan program ?”.

Sebenarnya Struktur Data + Algoritma akan menjadi Program.

Gambar 1.1: Hubungan struktur data dengan program dan algoritma

1.2 Tipe Data

Tipe data adalah:

Identifikasi yang umum dari suatu kelompok data sehingga kelompok data tersebut dapat dibedakan dari kelompok lainnya.

Secara umum, tipe data dapat dikelompokkan ke dalam 2 kelas; tipe data atomik dan tipe data struktur. Suatu data disebut sebagai tipe atomic bila data tersebut tidak dapat diuraikan ke dalam bentuk yang lebih sederhana. Contohnya adalah: tipe data Integer, tipe data Char, dll. Sedangkan tipe data struktur atau tipe data atomik. Contohnya adalah : tipe data array, record, dll.

Dengan mengetahui tipe dari suatu data maka dapat ditentukan:

· Kumpulan (himpunan) yang berlaku dari data tersebut.

· Himpunan operasi yang dapat dilaksanakan dari data tersebut.

Berikut akan dikemukan contoh dari masing-masing tipe data dengan menggunakan deskripsi yang biasanya dilakukan dalam bahasa C.

Tipe Data Atomik

Tipe data : int A;

Besar memori : 16 bit

Jangkauan : -32768 sampai dengan 32768

Tipe Data Struktur

Tipe data : int X[5];

Jenis tipe data diatas adalah tipe data struktur, komponennya terdiri dari tipe data INTEGER (dapat diuraikan ke dalam tipe data atomic berbentuk INTEGER), struktur atau hubungan antara komponennya disusun dalam bentuk ARRAY.

Mengenai tipe data ARRAY akan dibahas lebih lanjut dalam modul 2.

1.3 Level Abstraksi Tipe Data

Kita dapat membedakan adanya beberapa level abstraksi dari suatu tipe data. Ada tipe data yang hanya berada di dalam imajinasi kita saja. Bayangkan kita mempunyai sekumpulan nama-nama orang, dan nama-nama itu diberi nomor urut. Dapat dibayangkan operasi yang dapat dilakukan terhadap kumpulan nama tersebut. Seperti mencetak nama-nama, menemukan nama dengan urutan ke tiga dst. Tipe data yang demikian dikatakan berada pada level abstrak.

Jika tipe data abstrak tersebut kita implementasikan dengan menggunakan bahasa pemrograman, maka kita dapat menuliskan program untuk melakukan operasi-operasi seperti yang telah disebutkan pada level abstrak di atas. Tipe data yang berada dalam bahasa pemrograman dikatakan berada pada level virtual.

Pada akhirnya, pada saat program dijalankan, tipe data virtual harus secara physic diload ke dalam memory/processor dari mesin computer yang dipergunakan untuk menjalankan program tersebut. Tipe data yang demikian dikatakan berada pada level physical.

Secara ringkas kita dapat membagi tipe data ke dalam 3 level abstraksi, yaitu:

E Tipe Data Abstrak

Adalah tipe data sebagai hasil dari imajinasi kita.

E Tipe Data Virtual

Adalah tipe data yang berada dalam virtual memory atau dalam bahasa pemrograman.

E Tipe Data Physical

Adalah tipe data yang secara physic atau nyata berada dalam memory / main processor.

NATIVE DATA TYPE

Pada level physical, semua data dinyatakan dalam binary digit (bit), yaitu berupa angka 0 dan 1. data tipe ini sangat menyulitkan manusia dalam membaca, menulis atau mengubahnya. Maka diciptakanlah bahasa pemrograman yang memudahkan manusia untuk berkomunikasi dengan computer. Bahasa pemrograman tingkat tinggi (high level language) merupakan bahasa pemrograman yang paling mudah dimengerti oleh manusia. Dalam bahasa pemrograman ini biasanya telah tersedia beberapa tipe data yang dapat langsung dipergunakan bila kita menulis program dengan bahasa ini. Tipe data ini disebut sebagai native data type.

Contoh native data type dalam C adalah:

* int

* char

* long

* float dan lain - lain

1.4 Tipe Data Abstrak

Sebelum kita membahas spesifikasi tipe data abstrak, ada baiknya dibahas terlebih dahulu dua terminologi / istilah yang akan dipergunakan dalam spesifikasi tipe data.

Terminologi yang pertama adalah pre, yang merupakan singkatan dari precondition; menyatakan kondisi yang harus dipenuhi agar operasi dapat menghasilkan hasil yang benar. Terminologi yang kedua adalah post, yang merupakan singkatan dari postcondition; kondisi yang merupakan hasil dari operasi.

Sebagai contoh akan didefinisikan tipe data abstrak yang disebut letterstring yang merupakan kumpulan huruf ‘a’ sampai ‘z’, ‘A’ sampai ‘Z’ dan spasi. Hasil dari letterstring bias berupa suatu kalimat yang mempunyai arti tertentu, atau juga bias hanya merupakan kumpulan huruf yang tidak mempunyai arti apa-apa.

Contoh:

1. UNIVERSITAS Mercu Buana

2. aaaaaiiiiieeeekkkkkk

3. Algoritma / Pseudocode

4. Perkalian 3 dengan 2 menghasilkan 6 (enam)

Berdasarkan definisi letterstring maka nomor 1 dan 2 dari contoh di atas adalah letterstring, sedangkan 3 dan 4 bukan letterstring karena mengandung elemen yang nilainya tidak diperkenankan dalam letterstring (/, angka 3,2,6, dan tanda () ).

Batasan lain yang dispesifikasikan adalah jumlah huruf dalam letterstring tidak boleh melebihi 80 huruf, dan letterstring dengan 0 huruf (tanpa huruf) diperkenankan.

Berikut adalah spesifikasi formal dari tipe data abstrak letterstring.

Elemen : Letterstring hanya boleh terdiri dari huruf ‘a’ sampai ‘z’, ‘A’ sampai ‘Z’ dan spasi.

Struktur : Terdapat hubungan / struktur linier antara huruf-huruf.

.

Domain : Hanya diperkenankan 0 – 80 huruf dalam letterstring.

Operasi :

Leftletter (var s:letterstring) : letter

{operasi untuk mengambil 1 huruf yang paling kiri dari letterstring}

pre - Jumlah huruf dalam letterstring harus lebih dari 0.

post - leftletter berisi huruf paling kiri dari letterstring, dan jumlah huruf dalam

letterstring akan berkurang 1.

Append (I:letter; var s:letterstring)

{operasi untuk menambahkan 1 huruf ke posisi paling kanan dari letterstring}

pre - Jumlah huruf dalam letterstring harus kurang dari 80.

post - leftletter bertambah 1 huruf pada posisi paling kanan.

empty (s:letterstring) : boolean

{operasi untuk mengecek apakah suatu string tidak berisi huruf (kosong)}

pre - tidak ada.

post - Jika letterstring tidak berisi huruf maka kondisi akan menghasilkan TRUE, selain itu FALSE.

full (s:letterstring) : boolean

{operasi untuk mengecek apakah suatu string sudah penuh}

pre - tidak ada.

post - Jika letterstring berisi 80 huruf maka kondisi akan menghasilkan TRUE, selain itu FALSE.

reverse (var s:letterstring)

{operasi untuk membalikan posisi huruf-huruf sehingga huruf pertama akan bertukar posisi

dengan huruf terakhir dst}

pre - tidak ada.

post - Urutan dari huruf-huruf akan merupakan kebalikan dari posisi awalnya.

1.5 Keuntungan Tipe Data Abstrak

Setelah kita membahas spesifikasi dari tipe data abstrak dan melihat bagaimana mudahnya menerjemahkan spesifikasi tersebut ke dalam bahasa pemrograman, dapat disimpulkan beberapa keuntungan dari tipe data abstrak diantaranya kebebasan implementasi (implementation independence), integritas dan penyederhanan masalah (simplicity).

1.6 Tipe Data Physical

Seperti telah dibahas pada bab 1.3 bahwa tipe data physical adalah tipe data yang secara physic atau nyata berada dalam memory / main processor. Tipe data ini perlu dipelajari lebih rinci mengingat hal ini mempengaruhi pertimbangan antara besarnya tempat yang dibutuhkan untuk menyimpan data dengan kecepatan / efesiensi pengambilan data untuk menghasilkan design yang efektif.

Dua hal penting yang harus diperhatikan bila kita berbicara mengenai tipe data physical adalah: memory dan processor yang dipergunakan.

1.6.1 Memory

Pada masa di mana perkembangan teknologi perangkat kelas telah sedemikian canggihnya, memory yang tersedia di pasaran juga sangat beragam. Ada yang berkapasitas besar atau kecil, ada yang kecepatannya sangat tinggi atau rendah, ada yang bersifat volatile (memerlukan aliran listrik untuk menyimpan data) atau yang non-volatile, portable (mudah dibawa) atau non-portable, cara accessnya ada yang random access, direct access atau sequential access.

SEQUENTIAL ACCESS MEMORY (SAM)

Bentuk SAM yang umum ditemukan adalah magnetic tape, kecepatan accessnya sangat rendah, kapasitasnya sangat besar (walaupun sekarang dapat ditemukan magnetic disk yang mempunyai kapasitas sebesar magnetic tape), selalu non-volatile dan portable. Karena sifat tersebut di atas maka memory jenis ini biasanya dipergunakan untuk memback-up data.

DIRECT ACCESS MEMORY (DAM)

Memory jenis ini biasanya ditemukan dalam bentuk magnetic disk (piringan magnet), bias berupa diskette atau hard disk. DAM ini accessnya cukup cepat (walaupun kalau dibandingkan dengan RAM masih kalah cepat), kapasitasnya cukup besar (dari Megabyte hingga GigaByte), non-volatile, dan sangat mudah dibawa (portable) karena ukurannya yang kecil.

RANDOM ACCESS MEMORY (RAM)

Memory jenis ini sangat cepat, relative lebih kecil, pada umumnya bersifat volatile (walaupun ada beberapa tipe yang bersifat non-volatile) dan non-portable.

CACHE MEMORY

Memory ini jauh lebih cepat dibandingkan dengan RAM, kapasitasnya lebih kecil dan harganya cukup tinggi.

REGISTERED

Walaupun memory jenis ini sangat tinggi harganya, kapasitasnya sangat kecil tetapi register mutlak diperlukan untuk melakukan operasi di dalam computer. Kecepatan dari register adalah yang tertinggi dibandingkan dengan semua jenis yang ada.

Jenis Memory	Kecepatan	Kapasitas	Harga
Register	Cepat	Kecil	Mahal
Cache
RAM
DAM
SAM	Lambat	Besar	Murah

Tabel 1.1 : Jenis Memory

1.6.2 Processor

Processor yang dipergunakan sangat menentukan range/batasan dari native data type. Ambil contoh Personal Computer (PC), dengan processor yang berbeda, jumlah bit yang diproses juga akan berbeda. Misalkan processor 8088 dan 80286 hanya memproses data 8 bit, 80386 memproses 16 bit dan 80486 memproses 32 bit.

Soal Latihan

1. Apa yang dimaksud dengan struktur data?

2. Sebutkan 3 level abstraksi data.

3. Ada berapa jenis memori, jelaskan dengan singkat dan jelas

4. Jelaskan hubungan antara struktur data, algortima dan program

Referensi

1. Daniel F Stubbs & Neil W. Webre (1985). Data Structures with Abstract Data Type and Pascal. Brook/ Cole Publishing Company

2. Bambang, Wirawan (2004), Struktur Data dengan C, Pernerbit Andi Jogyakarta.

3. Maria, Anna (1998), Struktur Data, Buku Ajar Universitas Bina Nusantara Jakarta.

4. Kristanto, Andri (2003), Struktur Data dengan C++, Penerbit Graha Ilmu