Catatan Kuliah
STRUKTUR DATA
Catatan Kuliah PAM 282 STRUKTUR DATA Oleh Narwen, M.Si Jurusan Matematika FMIPA Unand Narwen, M.Si / Jurusan Matematika FMIPA Unand
1
Catatan Kuliah
STRUKTUR DATA
BAB I PENDAHULUAN PENGERTIAN STRUKTUR DATA. Struktur data adalah cara menyimpan atau merepresentasikan data atau informasi di dalam komputer agar bisa dipakai secara efisien. Sedangkan data atau informasi itu sendiri adalah representasi kenyataan atau fakta dari dunia nyata. Fakta atau keterangan tentang kenyataan dari dunia nyata tersebut akan disimpan, direkam ataupun direpresentasikan dalam bentuk tulisan, suara, gambar, sinyal atau simbol-simbol. Narwen, M.Si / Jurusan Matematika FMIPA Unand
2
Catatan Kuliah
STRUKTUR DATA
Secara garis besar tipe data dapat dikategorikan menjadi dua kelompok, yaitu tipe data sederhana dan tipe data terstruktur. Tipe data sederhana dibedakan lagi atas tipe data sederhana tunggal dan tipe data sederhana majemuk. Contoh tipe data sederhana tunggal adalah integer, real, boolean dan karakter. Sedangan tipe data sederhana majemuk adalah string. Tipe data terstruktur dibedakan juga atas struktur data sederhana dan struktur data majemuk. Contoh struktur data sederhana adalah array dan record. Sedangkan struktur data majemuk dibedakan lagi atas struktur data majemuk Linier dan non linier. Narwen, M.Si / Jurusan Matematika FMIPA Unand
3
Catatan Kuliah
STRUKTUR DATA
Contoh dari struktur data majemuk linier adalah stack (tumpukan), queue (antrian), list dan multi list. Sedangkan contoh dari struktur data majemuk non Linier adalah pohon biner dan graph. Pemakaian struktur data yang tepat di dalam proses pemrograman akan menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadikan program secara keseluruhan lebih efisien dan sederhana. Struktur data yang ″standar″ yang biasanya digunakan di bidang informatika adalah list linier (linked List) dan variasinya, multi list, stack (tumpukan), queue (antrian), tree (pohon) dan graph (graf ). Narwen, M.Si / Jurusan Matematika FMIPA Unand
4
Catatan Kuliah
STRUKTUR DATA
INTEGER. Integer adalah bilangan yang tidak mengandung pecahan dan disajikan sebagai angka bulat. Integer memiliki representasi sederhana dalam komputer. Komputer memandang integer sebagai nilai dari serangkaian bilangan biner. Namun komputer tidak memproses per bit, tapi per blok bit yang umumnya terdiri dari 8 bit (dikenal sebagai 1 byte atau binary eight). Sebuah integer N disajikan dalam memory dengan rumusan N ← 2n-1 – 1, dengan n adalah jumlah bit dalam memory dan satu bit paling kiri sebagai sign (tanda). Bila bit tersebut bernilai 0, maka bilangannya adalah positif. Sebaliknya bila bit tersebut bernilai 1 maka bilangannya adalah negatif. Narwen, M.Si / Jurusan Matematika FMIPA Unand
5
Catatan Kuliah
STRUKTUR DATA
Metode menggambarkan bilangan biner negatif. 1. Ones Complement Notation. Bilangan negatif diperoleh dengan merubah setiap bit secara keseluruhan ke dalam kelompok bit lawannya. Contoh : (38)10 = 00100110. Maka (-38)10 = 11011001. Masalah dengan metode ini, (0)10 dapat digambarkan dengan 00000000 atau 1111111, pada hal untuk satu bilangan bulat dilambangkan oleh satu bilangan biner. 2. Twos Complement Notation. Bilangan negatif diperoleh dengan menambahkan 1 ke metode ones complement notation. Narwen, M.Si / Jurusan Matematika FMIPA Unand
6
Catatan Kuliah
STRUKTUR DATA
Contoh : (-38)10 = 11011001 (ones complement) 1+ (-38)10 = 11011010 (twos complement) Dengan metode ini (0)10 dapat digambarkan dengan 00000000 secara tunggal. Tipe Integer pada pascal. Tipe
Jangkauan
Ukuran
Shortint
-128 .. 127
8 bit
Byte
0 .. 255
8 bit
Word
0 .. 65535
16 bit
Integer
-32768 .. 32767
16 bit
Longint
-2147483648 .. 2147483647
32 bit
Narwen, M.Si / Jurusan Matematika FMIPA Unand
7
Catatan Kuliah
STRUKTUR DATA
Operasi dalam integer. 1. Operasi uner, yaitu operasi yang hanya mempunyai satu operand, yaitu - dan +. 2. Operasi biner, yaitu operasi yang mempunyai dua operand, yaitu penambahan (+), pengurangan (-), perkalian (*), pembagian bulat (div), dan sisa bagi bulat (mod). Bentuk umum dari tipe integer adalah: Var
: ;
Narwen, M.Si / Jurusan Matematika FMIPA Unand
8
Catatan Kuliah
STRUKTUR DATA
REAL. Bilangan Real adalah gabungan dari bilangan Rasional dengan Irrasional. Biasanya ditulis dalam bentuk bilangan berkoma. Dalam memori komputer, bilangan real memakai sistem floating point, merupakan versi dari notasi ilmiah atau scientific notation. Disini penyajian terdiri dari mantissa (pecahan) dan indeks (eksponen) atau karakter, sehingga untuk bilangan real X dapat dirumuskan sebagai X = M * RE, dengan M adalah pecahan, R adalah radix dan E adalah eksponen. Mantissa adalah bilangan bulat ≠ 0. Narwen, M.Si / Jurusan Matematika FMIPA Unand
9
Catatan Kuliah
STRUKTUR DATA
Penulisan floating point dengan 32 bit biner terdiri dari 24 bit merupakan mantissa dan 8 bit merupakan eksponen. Bilangan negatif dari mantissa atau eksponen menggunakan two complement notation. Operasi dalam Real. Semua operasi pada aritmatika dan trigonometri adalah operasi-operasi yang dapat dilakukan terhadap bilangan real. Bentuk umum dari tipe real adalah: Var : ;
Narwen, M.Si / Jurusan Matematika FMIPA Unand
10
Catatan Kuliah
STRUKTUR DATA
CHARACTER dan STRING. Karakter (Character) meliputi digit numerik, karakater alfabetik dan karakter khusus. Sebuah karakter dalam memori komputer akan menempati 8 bit biner yang merepresentasikan bilangan positif. Misalkan ‘A’ dalam memori ditulis 0100 0001 atau (65)10 . Jadi kode ASCII dari A adalah 65. ASCII = America Standart Code for Information Interchange. Ada juga mengembangkan EBCDIC = Extended Binary Coded Decimal Interchange Code, dengan 8 bit biner. String adalah barisan hingga simbol yang diambil dari sejumlah hingga karakter. String S dengan panjang n ditulis sebagai S ← a1 a2 a3… an. Narwen, M.Si / Jurusan Matematika FMIPA Unand
11
Catatan Kuliah
STRUKTUR DATA
Operasi dalam Karakter dan String. 1. Concat [fungsi], digunakan untuk menggabungkan dua atau lebih variable-variabel string. ConCat ( s1 <,s2,...,sn>: String) : String;
2. Copy [fungsi], digunakan untuk mengambil satu atau beberapa karakter dari sebuah string. Copy(S:String;Index,Count:integer) : String;
3. Delete [prosedur], digunakan untuk menghapus sebagian karakter dari sebuah string. Delete(S:String;Index,Count:integer);
4. Insert [prosedur], digunakan untuk menyisipkan satu atau beberapa karakter ke dalam sebuah string. Insert(source,S:string;Index:integer); Narwen, M.Si / Jurusan Matematika FMIPA Unand
12
Catatan Kuliah
STRUKTUR DATA
5. Length [fungsi], digunakan untuk menghitung banyaknya karakter dalam suatu string. Length(S:String): integer;
6. Pos [fungsi], digunakan untuk mencari posisi sebuah bagian string (substring) di dalam sebuah string. Pos(Substr,S:string): Byte;
7. Str [prosedur], digunakan untuk merubah nilai numerik ke dalam nilai string. Str(N:integer;S:string);
8. Val [prosedur], digunakan untuk merubah nilai string ke dalam nilai numerik. Val(S:String;N:Integer;P:byte); Narwen, M.Si / Jurusan Matematika FMIPA Unand
13
Catatan Kuliah
STRUKTUR DATA
9. Upcase [fungsi], digunakan untuk memberikan huruf kapital dari suatu argumen karakter. Upcase(C:char): char;
Operasi transfer tipe data. 1. Chr [fungsi], digunakan untuk merubah nilai dari byte ke bentuk karakter yang sesuai dengan kode ASCII. Chr(x : byte): char;
2. Ord [fungsi], digunakan untuk merubah nilai suatu variabel dari bentuk karakter ke bentuk longint. Ord(C : char): longint; Narwen, M.Si / Jurusan Matematika FMIPA Unand
14
Catatan Kuliah
STRUKTUR DATA
3. Round [fungsi], digunakan untuk membulatkan
data tipe real ke data tipe longint. Round(X:Real): Longint;
4. Trunc [fungsi], digunakan untuk membulatkan ke
bawah data tipe real ke data tipe longint. Trunc(X : Real): Longint;
Narwen, M.Si / Jurusan Matematika FMIPA Unand
15
Catatan Kuliah
STRUKTUR DATA
RECORD Disusun oleh satu atau lebih field.Tiap field menyimpan data dari tipe dasar tertentu atau dari tipe bentukan lain yang sudah didefinisikan sebelumnya. Nama record ditentukan oleh pemrogram. Record disebut juga tipe terstruktur. Bentuk umum dari record adalah: Type field1 : field2 : ... fieldn : end;
= record type1; type2; typen;
Narwen, M.Si / Jurusan Matematika FMIPA Unand
16
Catatan Kuliah
STRUKTUR DATA
Contoh 1. Type Titik = record x : real; y : real; end;
Jika variabel P dideklarasikan mempunyai tipe Titik maka field yang mengacu pada P adalah P.x dan P.y. Contoh 2. Didefinisikan tipe terstruktur yang mewakili Jam yang dinyatakan sebagai jam(hh), menit(mm) dan detik(ss), maka cara menulis type Jam adalah: Narwen, M.Si / Jurusan Matematika FMIPA Unand
17
Catatan Kuliah
STRUKTUR DATA
Type JAM = record hh : integer; mm : integer; ss : integer; end;
{0…23} {0…59} {0…59}
Jika variabel J dideklarasikan mempunyai tipe Jam maka cara mengacu tiap field adalah J.hh, J.mm dan J.ss. Operasi terhadap record adalah operasi per elemen, yaitu assignment, baca dan tulis. Akses elemen dari record adalah, . . Narwen, M.Si / Jurusan Matematika FMIPA Unand
18
Catatan Kuliah
STRUKTUR DATA
ARRAY (LARIK) Array adalah struktur data statik yang menyimpan sekumpulan elemen yang bertipe sama. Setiap elemen diakses langsung melalui indeksnya. Indeks dari array harus tipe data yang menyatakan keterurutan misalnya integer atau karakter. Banyaknya elemen array harus sudah diketahui sebelum program dieksekusi. Tipe elemen array dapat berupa tipe sederhana, tipe terstruktur atau tipe array lainnya. Nama lain array adalah Larik. Array satu dimensi disebut dengan vektor dan array dua dimensi disebut tabel. Narwen, M.Si / Jurusan Matematika FMIPA Unand
19
Catatan Kuliah
STRUKTUR DATA
Bentuk umum dari array satu dimensi adalah: Type = array[] of ;
Bentuk umum dari array dua dimensi adalah: Type = array[,] of ;
Tiga hal yang harus diperhatikan dalam mendeklarasikan suatu array yaitu, 1. Nama array, 2. Range dari Indeks, 3. Tipe data dari elemen array. Elemen terkecil dari indeks array disebut batas bawah (l) dan elemen terbesar disebut batas atas (u). Jumlah elemen dalam array disebut range, diberikan oleh ord(u) - ord(l) + 1. Narwen, M.Si / Jurusan Matematika FMIPA Unand
20
Catatan Kuliah
STRUKTUR DATA
Contoh 3. Definisikan suatu array dengan nama LarikA yang masing-masing elemennya adalah integer dan indeksnya dari -5 sampai dengan 200. Type LarikA = Array[-5..200] of integer;
Jika variabel A dideklarasikan sebagai LarikA, maka cara mengacu tiap elemennya adalah A[-5], A[-4], …, A[200]. Contoh 4. Type LarikB = Array[1..10,1..10] of integer;
Jika variabel A dideklarasikan sebagai LarikB, maka cara mengacu tiap elemennya adalah A[1,1],… A[1,10], …, A[10,1], …, A[10,10]. Narwen, M.Si / Jurusan Matematika FMIPA Unand
21
Catatan Kuliah
STRUKTUR DATA
Contoh 5. Const Nmaks = 100; Type mahasiswa = Record Nobp : integer; Nama : string; kodeMK : string; nilai : char; end; var TabMhs : Array[1..Nmaks] of Mahasiswa;
Cara mengacu elemen TabMhs adalah TabMhs[2]. Nobp mengacu field Nobp dari elemen kedua dari larik. Sedangkan Write(TabMhs[k].KodeMK); adalah menuliskan field KodeMK dari elemen ke k dari larik. Narwen, M.Si / Jurusan Matematika FMIPA Unand
22
Catatan Kuliah
STRUKTUR DATA
Operasi yang dapat dilakukan pada array adalah operasi per elemen untuk baca dan tulis, assignment, perhitungan dan perbandingan yang diakses melalui indeksnya. Banyaknya indeks menentukan dimensi dari array tersebut.
SET (HIMPUNAN) Set adalah kumpulan dari objek-objek. Dalam Pascal objek tersebut harus mempunyai tipe dasar yang sama. Tipe dasar ini adalah sembarang skalar atau tipe enumerasi. Bentuk umum set adalah : Type = Set of ;
Narwen, M.Si / Jurusan Matematika FMIPA Unand
23
Catatan Kuliah
STRUKTUR DATA
Keuntungan menggunakan Set adalah butuh tempat penyimpanan yang sedikit karena representasinya internal dalam bit. Sedangkan kerugiannya adalah anggota dari set tidak dapat dicetak dan hanya dapat dibaca keanggotaanya. Operasi pada Set adalah assignment (:=), union (+), inter-section (*), different (-), not equal (<>), equal (=), inclution (<=), exclution (>=) dan in. Contoh 6. Type Alfabet = Set of Char;
Jika variabel huruf dideklarasikan sebagai Alfabet, maka salah satu elemennya adalah huruf := [‘a’,’d’]. Sedang himpunan kosong ditulis dengan [ ]. Narwen, M.Si / Jurusan Matematika FMIPA Unand
24
Catatan Kuliah
STRUKTUR DATA
Latihan. Buatlah dalam bahasa pascal : 1. Definisikan sebuah tipe terstruktur untuk menyatakan data nasabah disebuah bank. Data nasabah terdiri atas field Nomor Account, Nama Nasabah, Alamat Nasabah, Kota Nasabah, dan Nomor Telpon Nasabah. Untuk setiap field definisikan tipe data yang cocok.
2. Dari soal nomor1 buatlah program dalam bahasa pemrograman berbasis bahasa Pascal, untuk memasukkan data nasabah sebanyak N, dengan N diinputkan dari papan ketik, kemudian menuliskan kembali semua data nasabah dalam bentuk matrik. Petunjuk: Gunakan notasi pengulangan untuk menyelesaikan permasalahan tersebut. Narwen, M.Si / Jurusan Matematika FMIPA Unand
25
Catatan Kuliah
STRUKTUR DATA
TIPE DATA ABSTRAK (ADT) Tipe Data Abstrak (Abstract Data Type) adalah definisi dari tipe dan sekumpulan primitif (operasi dasar) terhadap tipe tersebut. Tipe diterjemahkan menjadi tipe terdefinisi dalam bahasa pemrograman yang bersangkutan, misalnya menjadi record dalam Pascal. Primitif dalam konteks pemrograman prosedural, diterjemahkan menjadi fungsi (function) dan prosedur (procedure).
Narwen, M.Si / Jurusan Matematika FMIPA Unand
26
Catatan Kuliah
STRUKTUR DATA
Primitif dikelompokkan menjadi: 1. Konstruktor / Kreator, untuk pembentuk nilai tipe. Biasanya namanya di awali dengan Make. 2. Selektor, untuk mengakses komponen tipe. Biasanya namanya diawali dengan Get. 3. Prosedur Pengubah Nilai Komponen. 4. Validator komponen tipe, yang dipakai untuk menguji apakah dapat membentuk tipe sesuai batasan. 5. Destruktor / Dealokator, yaitu untuk menghancurkan nilai objek, sekaligus memori penyimpannya. 6. Baca/tulis, untuk interface dengan input/output device. Narwen, M.Si / Jurusan Matematika FMIPA Unand
27
Catatan Kuliah
STRUKTUR DATA
7. Operator Relasional terhadap tipe tersebut untuk mendefinisikan lebih besar, lebih kecil, sama dengan dan sebagainya. 8. Aritmatika terhadap tipe tersebut, dalam pemrograman biasanya hanya terdefinisi untuk bilangan numerik. 9. Konversi dari tipe tersebut ke tipe dasar dan sebaliknya.
Narwen, M.Si / Jurusan Matematika FMIPA Unand
28
Catatan Kuliah
STRUKTUR DATA
Tipe Data Abstrak biasanya diimplementasi menjadi dua buah modul, yaitu: 1. Definisi/spesifikasi type dan primitif - Spesifikasi type sesuai dengan bahasa yang dipakai. - Spesifikasi dari primitif sesuai dengan kaidah dalam konteks prosedural, yaitu: a. Fungsi: nama, domain, range, dan pre kondisi jika ada. b. Prosedur: Keadaan Awal, Keadaan Akhir dan proses yang dilakukan. 2. Body/realisasi dari primitif, berupa kode program dalam bahasa yang bersangkutan. Realisasi fungsi dan prosedur harus sedapat mungkin memanfaatkan Selektor dan Konstruktor. Narwen, M.Si / Jurusan Matematika FMIPA Unand
29
