MATERI KULIAH STRUKTUR DATA.
BAB I
jenis-jenis data
Suatu koleksi/ kelompok data yang dapat dikarakterisasikan oleh
organisasi serta operasi yang didefinisikan
terhadapnya.
Data di kategorikan menjadi
:
1. Tipe data tunggal (data primitif) :
Integer, Real, Boolean dan Karakter
2. Tipe data
majemuk (data campuran) : String (Untai)
Struktur data di kategorikan menjadi :
1. Struktur Data sederhana : Array
dan Record
2. Struktur Data majemuk :
Linier dan Non Linier
1.1
TIPE DATA TUNGGAL
1.1.1
INTEGER
Suatu integer adalah
anggota dari himpunan bilangan :
( ....., -(n+1), -n, ....., -2, -1, 0, 1, 2, ....., n, n+1, ..... )
Operasi-operasi dasar yang ada dalam integer antara lain :
·
Penjumlahan
·
Pengurangan
·
Perkalian
·
Pembagian
·
Perpangkatan, dsb
Masing-masing operator
pada operasi di atas, yang bekerja terhadap sepasang integer (operand) disebut
sebagai "binary operator". Sedangkan operator yang hanya bekerja
terhadap satu operand saja disebut sebagai "unary operator". Contoh dari
unary operator adalah operator negasi.
Operator ini berfungsi untuk mengubah tanda suatu operand.
1.1.2
REAL
Data numerik yang bukan termasuk integer, digolongkan dalam jenis
data real. Jenis data ini ditulis menggunakan titik desimal (atau koma
desimal). Bilangan real dimasukkan ke dalam memori komputer memakai sistem
floating point, merupakan versi yang disebut Scientific Notation. Disini penyajiannya terdiri atas dua
bagian, yaitu : mantissa (pecahan) &
eksponen.
Contoh :
Di dalam sistem desimal, bilangan 123000 = 0.123 *
106.
Disini 0.123 adalah
mantissa (pecahan), sedangkan 6 adalah eksponennya.
Secara umum suatu bilangan real X dituliskan M * RE
1.1.3
BOOLEAN
Jenis data ini disebut juga
jenis data "logical". Elemen
dari jenis data ini mempunyai nilai salah satu dari "true" atau "false".
Operator-operator yang dikenal pada jenis data ini terdiri atas:
1.
Operator Logika, yaitu : NOT,
AND dan OR.
·
Operator
OR akan menghasilkan nilai "true", jika salah satu atau kedua operand bernilai
"true".
·
Operator
AND akan menghasilkan nilai "true", jika kedua operand bernilai "true".
·
Sedangkan
operator NOT akan menghasilkan nilai "true",
jika operand bernilai "false", dan sebaliknya.
·
Operator NOT merupakan "precedence" dari operator AND dan
OR.
Dalam suatu
ekspresi yang tidak menggunakan tanda kurung, operator NOT harus dievaluasi
sebelum operator AND dan OR.
2.
Operator Relasional, yaitu :
>, <, >=, <=, <> dan =.
1.1.4
KARAKTER
Jenis data karakter merupakan elemen dari suatu himpunan simbol
aksara yang terdiri atas bilangan, abjad dan simbol-simbol khusus
1.1.5
STRING
Jenis data string
merupakan jenis data campuran, karena elemen-elemennya dibentuk dari
karakter-karakter di atas. String adalah barisan hingga simbol yang diambil
dari himpunan karakter. Karakter yang digunakan untuk membentuk suatu string
disebut sebagai alphabet. Dalam penulisannya, suatu string berada dalam tanda "aphosthrope".
Contoh :
Misal, diberikan himpunan alphabet A = { C, D, 1 }
String-string yang dapat dibentuk dari alphabet di atas antara lain adalah
:
'CD1', 'CDD', 'DDC',
'CDC1', ...dsb, termasuk "null string" atau "empty
string".
Himpunan yang anggotanya adalah semua string yang dapat dibentuk
dari suatu himpunan alphabet disebut sebagai "vocabulary". Suatu
vocabulary V yang dihasilkan dari himpunan alphabet A dinotasikan dengan VA atau A*.
Jika
suatu string dibentuk dari alphabet {0,1}, maka string yang terbentuk disebut
dengan "Bit String".
Secara umum, suatu string
S yang dibentuk dari himpunan alphabet A, dituliskan S = 'a1a2 ..... aN' , di mana setiap karakter
ai anggota A untuk, 1 £ i £ N.
Dalam suatu string
terdapat beberapa operasi utama, yaitu :
1.
Length
2.
Concatenation
3.
Substring
4.
Insert
5.
Delete
1.1.5.1
LENGTH
Nilai
dari operasi ini adalah suatu integer yang menunjukkan panjang dari suatu
string. Panjang dari string didefinisikan sebagai banyaknya karakter, atau
dapat ditulis : S = N atau Length (S) = N.
Contoh :
a.
Jika diberikan string S = 'a1a2 ..... aN'. Maka LENGTH(S) = N.
b.
Jika diberikan string S =
'ABCD13AB', maka LENGTH(S) = 8.
1.1.5.2
CONCATENATION
Operasi
ini bekerja terhadap dua string dan hasilnya merupakan resultan dari kedua
string tersebut. Operasi ini
hampir sama dengan operasi gabungan. Jika S1 dan S2 masing-masing adalah suatu string, maka bentuk
operasi concatenation dinotasikan dengna : CONCAT(S1,S2).
Contoh :
Misal S1 = 'a1a2 ..... aN' dan S2 = 'b1b2 ..... bM'
Maka CONCAT(S1,S2) = ' a1a2 ..... aNb1b2 ..... bM'
Panjang dari
string yang baru (resultan) merupakan jumlah panjang dari masing-masing string
atau :
LENGTH(CONCAT(S1,S2)) = LENGTH(S1) +
LENGTH(S2)
1.1.5.3
SUBSTRING
Operasi ini adalah operasi membentuk
string baru, yang merupakan bagian dari string yang diketahui. Notasinya adalah
: SUBSTR(S,i,j)
di
mana :
S = string yang
diketahui.
i dan j adalah integer
i
= posisi awal substring, 0 £ i £ LENGTH(S)
j
= banyak karakter yang diambil, 0 £ j £ LENGTH(S) dan 0 £ i+j-1£ LENGTH(S)
Contoh
:
Diberikan S = 'a1a2 ..... aN' ; i = 2 ; j = 4.
Maka
SUBSTR(S,i,j) = SUBSTR(S,2,4) = 'a2a3a4a5'
Catatan :
1. LENGTH(SUBSTR(S,i,j)) = j
2. SUBSTR(CONCAT(S1,S2),1,LENGTH(S1)) = S1
3. SUBSTR(CONCAT (S1,S2),LENGTH(S1)+1,LENGTH(S2)) = S2
1.1.5.4
INSERT
Operasi ini adalah untuk menyisipkan
suatu string ke dalam string lain. Bentuk umumnya
adalah : INSERT(S1,S2,i).
S1 dan S2 masing-masing adalah suatu string dan i adalah
posisi awal S2 pada S1.
Contoh :
Misalkan: S1 = 'a1a2 ..... aN'
S2 = 'b1b2..... bM'
INSERT(S1,S2,3)
= 'a1a2b1b2..... bMa3a4
..... aN'
1.1.5.5
DELETE
Operasi ini digunakan untuk
menghapuskan sebagian karakter dalam suatu string. Bentuk umumnya adalah : DELETE(S,i,j)
Maksudnya adalah
menghapuskan sebagian karakter dalam string S, mulai dari posisi i dengan panjang j.
Contoh
:
Diberikan string S = 'a1a2 ..... aN'
DELETE(S,3,4)
= 'a1a2a7a8 ..... aN'
Catatan :
INSERT(S1,S2,i) =
CONCAT(CONCAT (SUBSTR(S1,1,i-1),S2), SUBSTR(S1,i,LENGTH(S1)-(i-1)))
DELETE(S,i,j)=CONCAT(SUBSTR(S,1,i-1),SUBSTR(S,i+j,LENGTH(S)-(i+j-1)))
di mana : 1 £ i £ LENGTH(S1)
0 £ i £ LENGTH(S1)
0 £ i+j-1 £ LENGTH(S1)
Untuk i,j integer.
1.2
DEKLARASI DATA DALAM BAHASA PEMROGRAMAN
·
PASCAL
Var
Count : integer;
Switch
: boolean;
Betha : char;
Alamat : packed array[1..25] of
char;
1.3
PEMETAAN KE STORAGE
1.3.1
INTEGER
Bentuk mapping ke storage dari integer
dapat dilakukan dengan beberapa cara, yaitu :
1.
Skema Sign dan Magnitude
2.
Skema One's Complement
3.
Skema Two's Complement
a. Skema Sign and Magnitude
Cara ini
merupakan bentuk konvensional yang digunakan manusia untuk menyatakan suatu
bilangan dalam bentuk biner. Di sini representasi bilangan positif dan negatif
hanya dibedakan dengan tanda saja. Biasanya tanda positif atau negatif
ditunjukkan oleh digit terdepan dari bentuk binernya, untuk representasi dengan
jumlah digit tertentu.
Contoh :
+ 7
à + 111 à
representasi dengan 4 digit : 0111
- 7
à -
111 à
representasi dengan 4 digit : 1111
Dengan cara ini
kita akan mendapatkan kesulitan dalam menentukan tanda pada saat melakukan
operasi terhadap dua bilangan yang berbeda tandanya.
b. Skema Two's Complement dan
One's Complement
Kedua skema ini merupakan cara yang
digunakan untuk mengatasi kesulitan yang telah disebutkan di atas. Diberikan
bilangan integer non negatif X, X' dan R. Didefinisikan bahwa X' adalah
komplemen dari X relatif terhadap R, jika X
+ X' = R. X disebut sebagai bentuk true, sedangkan X' = R - X disebut bentuk komplemen. Bentuk komplemen X' = R - X menyatakan bilangan
integer negatif X. Sedangkan bentuk true
X menyatakan integer positif X.
Skema
Two's Complement menggunakan R = 2N.
Skema
One's Complement menggunakan R = 2N - 1.
Contoh :
Misal diberikan integer =
7, akan dicari bentuk binernya dengan skema Two's Complement untuk representasi
4 digit.
X = 7 ; R = 24 ; à
X + X' = R
X' = R - X
= 24 - 7
= 16 - 7
= 9
à dalam biner = 1001
1.3.2
KARAKTER
Saat ini banyak sekali
skema yang digunakan untuk merepresentasikan karakter dalam storage. Pada
umumnya skema yang paling banyak digunakan adalah :
1.
Extended Binary Coded Decimal
Interchange Code (EBCDIC)
2.
American Standard Code for
Information Interchange (ASCII)
Pada skema EBCDIC digunakan kode 8 bit untuk menyatakan sebuah karakter.
Jika dihitung, kemungkinan kombinasi seluruhnya adalah : 28. Sedangkan
skema ASCII menggunakan kode 7 bit untuk menyatakan suatu karakter. Skema ini
mempunyai jumlah kemungkinan kombinasi yang lebih sedikit jika dibandingkan
dengan skema EBCDIC. Selain dua skema tersebut di atas ada sebuah skema yang
disebut dengan kode Huffman. Pada cara ini, jumlah bit yang digunakan
tergantung dari frekuensi penggunaan suatu karakter.
1.3.3
STRING
Untuk mengetahui bentuk mapping pada storage
dari suatu string, perlu diketahui beberapa hal yang menyangkut ruang untuk
string yang bersangkutan, antara lain :
- letak posisi awal (start)
dan posisi akhir (terminal)
- suatu pointer yang menunjukkan lokasi pada storage
Ada tiga cara yang
umum digunakan untuk mapping suatu string ke dalam storage. Misal diberikan dua
string, yaitu : S1 = 'ABCDEFG' dan S2 = 'BCD'
Tidak ada komentar:
Posting Komentar