ARRAY
Array merupakan bagian dasar pembentukan suatu struktur data yang lebih
kompleks. Hampir setiap jenis struktur data kompleks dapat disajikan secara
logik oleh array.
q
Array : Suatu himpunan
hingga elemen yang terurut dan homogen, atau dapat didefinisikan juga sebagai
pemesanan alokasi memory sementara pada komputer.
q
Terurut :
elemen tersebut dapat diidentifikasi sebagai element pertama, kedua, dan
seterusnya sampai elemen ke-n.
q
Homogen
:
setiap elemen data dari sebuah array tertentu haruslah mempunyai tipe data yang
sama.
Karakteristik
Array :
1.
Mempunyai batasan dari pemesanan
alokasi memory ( bersifat statis)
2.
Mempunyai type data sama ( bersifat
Homogen)
3.
Dapat diakses secara acak.
4.
Berurutan ( terstruktur ).
Array
mempunyai dimensi :
- Array Dimensi Satu (Vektor)
- Array Dimensi Banyak.
-
Dimensi Dua (Matriks/Tabel)
-
Dimensi Tiga (Kubik).
ARRAY DIMENSI SATU
Ø
Merupakan bentuk yang sangat sederhana
dari array.
Ø
Setiap elemen array mempunyai subskrip/indeks.
Ø
Fungsi indeks/subskrip ini antara lain
:
1.
Menyatakan posisi elemen pada array tsb.
2.
Membedakan dengan elemen lain.
Penggambaran
secara fisik Array A(1:N) :
|
A(1)
|
A(2)
|
A(3)
|
A(4)
|
…
|
A(N)
|
Ket : A : nama array
1,2,3,4,…,N :
indeks / subskrip
Ø
Secara umum Array Dimensi Satu A dengan
tipe T dan subskrip bergerak dari L sampai U ditulis : A(L:U) = (A(I)); I =L , L+1, L+2, …, U
Keterangan
: L : batas bawah indeks / lower
bound
U : batas atas indeks / upper bound
A : nama Array
Ø
Banyaknya elemen array disebut Rentang atau Range A(L:U) = U – L + 1
Ø
Range khusus untuk array Dimensi Satu
yang mempunyai batas bawah indeks L=1 dan batas atas U=N, maka Range A adalah A(1:N) =( N – 1) + 1 = N
Contoh :
Data hasil pencatatan suhu suatu ruangan setiap satu jam, selama periode 24
jam ditulis dalam bentuk Array Dimensi Satu menjadi
Misal :
nama
arraynya Suhu, berarti elemennya dapat kita tulis sebagai Suhu(I), dengan batas
bawah 1 dan batas atas 24.
Suhu(I):menyatakan
suhu pada jam ke-I dan 1<=I<=24
Range
Suhu(1:24)=(24-1)+1=24
ARRAY
DIMENSI BANYAK
Ø
Array Dimensi Banyak (Multi-Dimensional
ARRAY) :
suatu
array yang elemen –elemennya berupa array juga.
Ø
Array
Dimensi Dua perlu dua subskrip/indeks :
a.
Indeks pertama untuk menyatakan posisi baris
b.
Indeks kedua untuk menyatakan posisi kolom
Ø
Secara umum Array Dimensi Dua B dengan
elemen-elemen bertype data T dinyatakan sbb : B(L1:U1,L2:U2)={B(I,J)}
L1<=1<=U1,
L2<=1<=U2, dan setiap elemen B(I,J) bertype data T
Keterangan
: B
= nama array
L1 = batas bawah indeks baris
L2 = batas bawah indeks kolom
U1 = batas atas indeks baris
U2 = batas atas indeks kolom
Ø
Jumlah elemen baris dari array B adalah
(U2 - L2 + 1)
Ø
Jumlah elemen kolom dari array B adalah
(U1 – L1 + 1)
Ø
Jumlah total elemen array adalah (U2 – L2 + 1) * (U1 – L1 + 1)
Ø
Suatu array B yang terdiri atas M
elemen dimana elemennya berupa array dengan N elemen, maka dapat digambarkan
sbb:
1 2 3
…… J ….. N
·
Array diatas dituliskan :
B(1:M,
1:N) = B(I,J) ;
Untuk
I = 1,2,3,………….,M dan
J = 1,2,3,……….., N
·
Jumlah elemen array B : M * N
·
Array B berukuran / berorder : M * N
CROSS SECTION
Ø
Cross
Section dari array berdimensi dua adalah suatu himpunan yang
anggotanya adalah elemen-elemen dlm satu baris saja atau satu kolom saja.
Ø
Notasinya : *
Misal
Array
B(1:M ;1:N) = {B(I,J)} ;
I =
1,2,3,……..,M dan
J =
1,2,3,…….,N
Maka
suatu Cross Section :
B(5,*)
= {B(5,1), B(5,2), B(5,3),………, B(5,N)}
B(*,5) = {B(1,5), B(2,5), B(3,5),………,
B(M,5)}
TRANSPOSE
Ø
Transpose dari
suatu array berdimensi dua adalah menukar posisi indeksnya ( menukar posisi
baris menjadi kolom atau kolom menjadi baris).
Ø
Transpose suatu array dari B dinotasikan BT
Ø
B
adalah array dua dimensi, B(I,J) maka BT (J,I)
Ø
A adalah array dua dimensi yang
berorder M x N memepunyai transpose ( AT) N x M
ARRAY DIMENSI TIGA
Ø
Banyaknya indeks yang diperlukan array
dimensi tiga adalah 3
Ø
Pada umumnya, suatu array berdimensi N
memerlukan N indeks untuk setiap elemennya.
Ø
Secara
acak array berdimesi N ditulis sbb:
A(L1:U1,
L2:U2, …….., LN:UN ) = (A(I1,I2,……,IN)) dengan LK <= IK<=UK
, k = 1,2,3,…, N
Contoh :
Penyajian
data mengenai jumlah mahsiswa Manajemen Informatika
Universitas Gunadarma berdasarkan tingkat, untuk kelas pagi dan malam dan jenis
kelamin.
Jawab :
MHS =
nama array
I =
1,2,3,4,5 (tingkat 1/5)
J =
1,2 (1 = pagi; 2 = malam )
K =
1,2 (1 = pria; 2= wanita)
MHS
(1:5, 1:2,1:2)
Jadi :
§
MHS(3,2,2)
jumlah
mahasiswa tingkat 3 MI kelas malam untuk jenis kelamin wanita
§
Cross Section MHS (1,*,2)
jumlah
mahasiswa tingkat 1 MI kelas pagi atau malam dan berjenis kelamin wanita.
MAPPING KE STORAGE DARI ARRAY
Skema penyajian
dapat dievaluasi berdasarkan 4 karakteristik yaitu :
1. Kesederhanaan
dari akses elemen
2. Mudah ditelusuri
3. Efisiensi dari
utilitas storage
4. Mudah
dikembangkan
ARRAY SATU DIMENSI
Misal:
Diberikan array
dengan nama B yang mempunyai indeks 1 s/d N yaitu A(1:N). Cara untuk menyimpan
array tersebut adalah sedemikian sehingga urutan secara fisik dari elemen-elemen adalah sama dengan urutan
logik dari elemen.
Untuk mengetahui Address Awal (
Starting Address) dari elemen suatu array A(I) perlu diketahui :
1. Address Awal
dari array yang bersangkutan
2. Ukuran dari
masing-masing elemen array
Ø
Address Awal dari array dinyatakan
dengan notasi Address Awal yaitu B (
Base Location)
Ø
Masing-masing elemennya menggunakan
ruang sebanyak S byte.
Ø
Address awal dari elemen ke-I dari
array A(1:N) adalah :
B + (I – 1 ) * S
Ø
Address Awal yang mempunyai batas bawah
tidak sama dengan satu, elemen ke-I dari
array A(L:U) adalah : B + ( I– L) * S
Misal :
A ( 1:7), address
awal dari elemen A(5) adalah : B + ( 5 –1) * S
A ( 3:8), address
awal dari elemen A(6) adalah : B + (6 - 3 ) * S
A (-3:4), address
awal dari elemen A(2) adalah : B + (2 –(- 3) ) * S
ARRAY MULTI DIMENSI
Memori komputer linier, maka untuk memetakan array dimensi banyak ke
storage harus dilinierkan.
Alternatif untuk pelinieran tersebut adalah :
q
Row Major
Biasanya
digunakan COBOL, PASCAL
Menyimpan
pertama kali baris pertama dari array, kemudian baris kedua, ketiga dst
Array
Rate ( 1:3 , 1:5)
|
|
1
|
2
|
3
|
4
|
5
|
|
1
|
|
|
|
|
|
|
2
|
|
|
Rate(2,3)
|
|
|
|
3
|
|
|
|
|
|
Menjadi
Rate(2,3)
Baris 1
Baris 2 Baris 3
Ø
Array A(I,J) dari array yang didefinisikan
sebagai array
A(L1:U1 , L2:U2), mempunyai
Address awal : B + (I – L1) * (U2 – L2
+1) * S + ( J – L2) * S
Contoh :
·
Array A(1:3, 1:5) dan elemen A(2,3)
mempunyai address awal :
B
+ (2-1) * (5-1+1) * S + (3-1) * S
B
+ 5 * S + 2 * S
B
+ 7 * S
·
Array A(2:4, 3:5) dan elemen A(3,4)
mempunyai address awal :
B
+ (3-2) * (5-3+1) * S + (4-3) * S
B
+ 1 * 3 * S + 1 * S
B + 4 * S
q
Column Major
Biasanya
digunakan FORTRAN
Menyimpan Kolom pertama dari array
kemudian kolom kedua, ketiga, dst
Menjadi
Rate ( 2,3)
Kolom 1 Kolom 2 Kolom 3 Kolom 4
Kolom 5
Ø
Array A(I,J) dari array yang
didefinisikan sebagai array
A(L1:U1 , L2:U2) mempunyai
Address awal : B + (J – L2) * (U1 – L1
+1) * S + ( I – L1) * S
Contoh :
·
Array A(1:3, 1:5) dan elemen A(2,3)
mempunyai address awal :
B
+ (3-1) * (3-1+1) * S + (2-1) * S
B + 6 * S + 1 * S
B
+ 7 * S
·
Array A(2:4, 3:5) dan elemen A(3,4)
mempunyai address awal :
B
+ (4-3) * (4-2+1) * S + (3-2) * S
B
+ 1 * 3 * S + 1 * S
B
+ 4 * S
ARRAY
SEGITIGA (TRINGULAR ARRAY)
Ada 2 macam
1. Upper Tringular
Elemen
dibawah diagonal utama adalah 0
2. Lower Tringular
Elemen
diatas diagonal utama adalah 0
Ø
Suatu array dimana elemen diagonalnya
juga nol disebut Strictly (upper/lower)
Tringular.
Ø
Pada array Lower Tringular dengan N
baris, jumlah maksimum elemen <> 0 pada baris ke-I adalah I
N
Ø
Total
elemen <> 0 adalah å I = ( N * ( N+1)) /2
K=1
Ø
Untuk N kecil : tidak ada masalah
Ø
Untuk N besar :
1.
Elemen yang sama dengan nol tidak usah
disimpan dalam memori
2.
Pendekatan terhadap masalah ini adalah
dengan pelinieran array dan hanya menyimpan array yang tidak nol.
1. Misal
A
array segitiga atas berorder N x N
B array bersegitiga bawah dengan
order ( N-1) x ( N-1)
A dan B dapat disimpan sebagai array
C berorder N x N
C (I,J) = A(I,J) untuk I <= J
C(I+1,J) = B(I,J) untuk I >= J
2. Misal
A
array segitiga atas berorder N x N
B array bersegitiga bawah dengan
order N x N
A dan B dapat disimpan sebagai array
C berorder N x ( N + 1 )
C (I,J+1) = A(I,J) untuk I <= J
C(I,J) = B(I,J) untuk I >= J
3. Misal
A dan
B keduanya merupakan array segitiga atas
Maka
untuk menyimpannya secara bersama-sama dengan melakukan transpose terhadap
salah satu array tersebut.
Array C berorder N x (N+1)
C (I,J+1) = A(I,J) untuk I <= J
C(J,i) = B(I,J) untuk I >= J
SPARSE ARRAY
Ø
Suatu type khusus yang lain dari array
Ø
Dikatakan Sparse atau jarang karena
elemen-elemen yang tidak nolnya relatif lebih sedikit jumlahnya
Ø
Setiap elemen bukan nol pada sparse
array dua dimensi dapat direpresentasikan dalam format (Row-Subscript, Column-subscript, value).
Ø
Triple ini dapat diurut berdasarkan
Row-Subscript Major dan Colum-Subscript Minor dan disimpan dalam bentuk vektor.
Ø
Penyajian lain dari Sparse Array adalah
dengan menggunakan daftar berkait/ Linked List.
