Data Structures
Class 4 – Arrays Pengampu : TATI ERLINA, M.I.T.
McGraw-Hill Technology Education
Copyright © 2006 by The McGraw-Hill Companies, Inc. All rights reserved.
DESKRIPSI Bayangkan jika kita memiliki 100 buah nilai. Kita perlu : membaca, memproses dan mencetak nilai tersebut. menyimpan 100 nilai tsb dalam memori. Apa pilihan yang dapat dilakukan?
1. Gunakan variable sebanyak yang dibutuhkan.
Gambar 3.1
2. Gunakan array struktur data yang mengacu pada sekumpulan elemen yang diakses melalui indeksnya.
Gambar 3.3 :Arrays with indexes
Gunakan loop untuk memproses elemen pada array.
Gambar 3.4 : penggunaan array dengan loop
Compare the number of instructions needed to handle 100 individual elements in Gambar 3.2 and the array with 100 in Gambar 3.4. 3.4 Assume that processing each score needs only one instruction.
Solution???
The number of cycles (fetch, decode, and execute phases) the computer needs to perform is not reduced if we use an array. The number of cycles is actually increased, because we have the extra overhead of initializing, incrementing and testing the value of the index. But our concern is not the number of cycles: it is the number of lines we need to write the program.
big issues in CS : reusability Assume we have written two programs to process the scores as shown in Figure 3.2 and Figure 3.4 If the number of scores changes from 100 to 1000, how many changes do we need to make in each program? Solutions?
• jenis struktur data yang paling sederhana dan mudah digunakan. • Terdiri dari array satu dimensi (linear array), dan array multidimensi. • Merupakan metode yang ringkas dan efisien untuk bekerja dengan koleksi nilai data yang besar.
HOW ARRAYS ARE STORED IN THE MEMORY Size/Length : jumlah elemen dalam array. Type
: jenis data yang diizinkan pada array.
Base : alamat dari lokasi memori dimana elemen pertama array pertama terletak. Index : semua elemen array dapat diakses dengan menggunakan subscript seperti Word
0
: ukuran dari sebuah elemen.
1
2
3
4
5
6
7
indeks
value
alamat
21da
21db
21dc
21dd
21de
21df
21e0
21e1
11
Karakteristik Array 1. Homogen (homogeneous) :
semua elemen array mempunyai tipe yang sama.
2. Tersusun berurutan (ordered) :
semua elemen tersimpan satu persatu pada lokasi memori yang berdekatan/berdampingan dengan urutan yang linear.
3. Terbatas (finite):
hanya berisi jumlah elemen yang terbatas.
4. Semua elemen dapat diakses secara acak. 12
• Contoh ; • sebuah array bertipe integer untuk menyimpan umur semua mahasiswa kelas A. • Sebuah array ber-tipe string untuk menyimpan semua nama penduduk sebuah kampung.. .
13
• Kelebihan : 1. Pengoperasiannya mudah 2. Ekonomis dalam pemakaian memori, jika semua elemen terisi. 3. Akses ke setiap elemen memerlukan waktu yang sama
•
Kekurangan : 1. Ukuran array harus diketahui sebelumnya. 2. Boros ruang memori jika banyak elemen yang tidak digunakan.
• Aplikasi : • matrix • Spreadsheet • String yang terdiri atas karakter
15
Array Dimensi Satu • Adalah : • array yang hanya membutuhkan satu indeks untuk mengacu pada tiap elemennya.
16
Contoh : array dimensi satu
• Latihan : • modifikasi program array dimensi satu diatas sehingga nilai array tidak didefinisikan terlebih dahulu, tetapi diisi satu persatu secara terpisah dengan 1. menggunakan statement scanf(); 2. Tidak menggunakan statement scanf();
Inisialisasi array dengan sebuah string (cara-1): • Strings dalam bahasa C bukanlah apa-apa tetapi serangkaian karakter yang diikuti oleh null byte. • Untuk menyimpan string, dibutuhkan sebuah array yang terdiri atas karakter diikuti oleh sebuah null byte. • Inisialisasi string : char arr[] = {'c','o','d','e','\0'};
• null byte dibutuhkan sebagai byte tempat berhenti ketika string dibaca sebagai satu kesatualn.
Inisialisasi array dengan sebuah string (cara-2): • Tidak dibutuhkan petik tunggal secara eksplisit disetiap karakter. • Tidak juga null character. • Akan tetapi dibuat dengan kutip ganda. char arr[] = "code";
Multi-dimensional arrays The arrays discussed so far are known as onedimensional arrays because the data is organized linearly in only one direction. Many applications require that data be stored in more than one dimension. Figure below shows a table, which is commonly called a two-dimensional array.
A two-dimensional array 11.21
Memory layout
The indexes in a one-dimensional array directly define the relative positions of the element in actual memory. Figure below shows a two-dimensional array and how it is stored in memory using row-major or column-major storage. Rowmajor storage is more common.
11.22
Contoh : Array dimensi dua
