Terminologi
Array merupakan tipe data komposit yang dapat digunakan untuk menyimpan lebih dari satu nilai homogen. Homogenitas nilai yang disimpan dibatasi oleh tipe data elemen-elemennya. Hubungan antar elemen dalam array bersifat linier, artinya setiap elemen hanya berelasi satu adn hanya satu dengan elemen lainnya, baik predecessor maupun successor, kecuali untuk elemen pertama dan terakhir. Penempatan array di memory secara fisikal serupa dengan logikalnya, sehingga dengan suatu mekanisme mapping function dapat diketahui lokasi setiap lemen-elemennya.

Indeks

Setiap elemen array memiliki indek unik yang dapat digunakan untuk akses nilainya. Pengaksesan dapat dilakukan secara random(acak).Jumlah indek menunjukkan besarnya dimensi array. Secara konseptual, array dapat memiliki banyak dimensi, akan tetapi dengan pertimbangan waktu akses pada ranah praktisnya hanya dipakai pada batas tertentu.

Operasi

Array memiliki operasi dasar anatar lain Create, Read/Retrieve, Update/Store.Create digunakan untuk menciptakan array baru yang masih kosong. Dalam kondisi ini, jika dilakukan pengecekan jumlah elemen akan dihasilkan nilai kosong(Empty).Read digunakan untuk membaca elemen array pada indek tertentu. Operasi ini akan berhasil jika array tidak kosong. Sebaliknya, jika tidak kosong maka operasi read akan menghasilkan satu nilai(elemen) array.Update digunakan untuk mengubah nilai array. Opeasi inipun akan berhasil jika array tidak kosong.

Array Mapping Function (AMF)

AMF digunakan untuk memetakan nilai indek tertentu ke alamat (address) dari suatu elemen/komponen.

Parameter yang digunakan pada AMF meliputi :

  • Base Address (b) : alamat(byte) pertama daru array yang di-assign pada saat binding time. Binding time adalah waktu dimana array dialokasikan pada memory, bisa saat compile maupun execute.
  • Component Length(L) : panjangnya memory yang diperlkan untuk menyipan setiap komponen array. Untuk setiap bahasa pemrograman memiliki kapasitas yang berbeda untuk setiap tipe datanya. Contoh tipe data integer, pada Turbo PAscal 7.0 dan Turbo C 2.0 diperlukan 2 byta, sedangkan pada Visual C++ 5.0 diperlukan 4 byta.
  • Lower Bond (Lk) & Upper Bond (Uk) : Lk adalah nilai indek terkecil, sedangkan Uk adalah nilai indek terbesar. Contoh pada Turbo C 2.0 didefinisikan int S[10]; Maka nilai Lk=0, dan Uk=9.
  • Dimension (d) : besarnya dimensi dari suatu array. Contoh :
    • Array 1 dimensi : int S[10]; Besarnya d adalah 1.
    • Array 2 dimensi : int S[10][5]; Besarnya d adalah 2.

Rumus yang digunakan pada AMF (Daniel, 54) :

Lokasi komponen

addr(S[i1][i2]…[id] = c0 + c1 x i1 + c2 x i2 + … + cd x id, dimana :

cd = L

ct-1 = (ut – lt + 1) x ct dan 1 < t <= d

c0 = b – (c1 x l1) – … (cd x ld)

Perhitungan besarnya memory (M) yang diperlukan : L x (u1 – l1 +1) x … x (ud – ld + 1)

AMF untuk Array Khusus

  • Array segi tiga (Triangular Array)
    • Lower Triangular Array : array dua dimensi berbentuk bujur sangkar (u1=u2), dimana semua komponen di atas diagonal berisi 0.
    • Upper Triangular Array : array dua dimensi berbentuk bujur sangkar (u1=u2), dimana semua komponen di bawah diagonal berisi 0.
      Memerlukan lebih sedikit memory karena anga 0 tidak perlu disimpan.

Rumus AMF :

addr(S[i,j] = c0 + c1 x (i x (i – 1) + c2 x j, dimana c0=b, c1=L/2, c2=L

Jumlah elemen = (u x (u + 1))/2

Jumlah memory(M) = L x jumlah elemen

  • Array Jarang (Sparse Array)
    Adalah array yang kebanyakan komponennya mempunyai satu nilai yang sama, misalkan 0. Hanya sebagian kecil yang nil;ainya tidak sama dengan 0.

Referensi :

Daniel F.Stubbs & Neil W. Webre (1985), Data Structure with Abstract Data Types and Pascal, Book / Cole Publishing Company

Paul J. Deitel. (2016). C how to program : with an introduction to C++. 08. Pearson Education. Hoboken. ISBN: 9780133976892.