Algoritma dan Struktur Data : 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 halaman 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.

sda 1

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:

 Tipe Data Abstrak
Adalah tipe data sebagai hasil dari imajinasi kita.
 Tipe Data Virtual
Adalah tipe data yang berada dalam virtual memory atau dalam bahasa pemrograman.
 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.

sda 2
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.

 

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s