Array
| English | Bahasa Indonesia |
|---|---|
| array/əˈreɪ/ | array |
| element/ˈelɪmənt/ | unsur |
| index/ˈɪndeks/ | indeks |
| lower bound/ˈləʊə baʊnd/ | batas bawah |
| upper bound/ˈʌpə baʊnd/ | batas atas |
| dimension/daɪˈmenʃn/ | dimensi |
| nested loops/ˈnestɪd luːps/ | perulangan bersarang |
| linear search/ˈlɪnɪə sɜːtʃ/ | pencarian linear |
| bubble sort/ˈbʌbl sɔːt/ | bubble sort |
Kursi 14C
- Bioskop memiliki 300 kursi. Sistem pemesanannya tidak memiliki 300 variabel bernama
Seat1A,Seat1B,Seat1C. Ia memiliki satu array, dan tiket Anda adalah alamat di dalamnya: baris 14, kursi C. - Satu nama, ratusan nilai, masing-masing ditemukan dengan angka. Tambah baris dan kodenya tidak berubah; loop atas angka-angka dan Anda telah memeriksa setiap kursi.
- Hampir semua algoritma Paper 2 melintasi array: mencarinya, menjumlahkannya, mengurutkannya, menemukan nilainya terbesar.
- Pelajaran ini adalah kosakata, deklarasi, dan empat algoritma yang diminta penguji dalam pseudocode dan kata-kata.
Kosakata
- Sebuah array adalah struktur data yang menyimpan jumlah tetap elemen dari tipe data yang sama di bawah satu pengenal, masing-masing diakses oleh index.
- Batas bawah dan batas atas adalah index valid pertama dan terakhir. Jumlah elemen adalah batas atas − batas bawah + 1.
- Dimensi adalah berapa banyak index yang dibutuhkan elemen: satu untuk daftar, dua untuk tabel.
- Dalam
ThisArray[n] ← 42array memiliki satu dimensi, indeks adalah variabelINTEGERn, dan elemen pada indeks tersebut menerima42.
Satu pengenal, indeks untuk setiap elemen, batas di kedua ujung
Sebuah array menyimpan:
Array adalah koleksi terurut dari item bertipe yang sama yang diakses melalui indeks. (Rekombinasi mengelompokkan tipe berbeda.)
Array adalah struktur data yang menyimpan banyak nilai dari tipe ______ di bawah satu nama.
Setiap nilai dicapai melalui indeksnya.
DEKLARASI Nilai : ARRAY[0:99] OF INTEGER mendeklarasikan array dengan elemen ____.
Batas atas dikurangi batas bawah ditambah satu: 99 − 0 + 1 = 100. Kedua batas adalah indeks yang valid.
Contoh terpecahkan: mendeklarasikan array yang dibutuhkan tugas
- Deklarasi memerlukan pengenal, batas dan tipe data.
- 120 pembacaan yang mungkin memiliki desimal:
DECLARE Data : ARRAY[1:120] OF REAL - Tabel 150 baris dan dua kolom teks:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Sebutkan jumlahnya jika diminta:
[0:99]menyimpan 100 elemen, bukan 99.
Deklarasi mana yang menyimpan tabel dengan 150 baris dan 2 kolom teks?
Dua dimensi, masing-masing memiliki batas bawah dan batas atas, serta jenis elemen. Opsi kedua adalah satu daftar panjang; opsi ketiga tidak memiliki jenis; opsi keempat tidak memiliki batas bawah.
Memproses array 1-D
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- Loop
FORdari batas bawah hingga batas atas mengunjungi setiap elemen sekali. - Untuk penjumlahan, hitungan, maksimum, atau minimum, atur variabel running sebelum loop dan perbarui di dalamnya.
Array 2-D
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- Index pertama adalah baris, kedua adalah kolom. Loop bersarang mengunjungi setiap sel: loop luar atas baris, loop dalam atas kolom.
- Gunakan 1-D untuk urutan tunggal dan 2-D ketika data memiliki dua dimensi alami, seperti grid kursi atau tabel nilai menurut siswa dan mata pelajaran.
Grid[row, column], selalu dalam urutan itu
Indeks array 2-D dengan [baris, kolom]
Array 2-D adalah sebuah grid. Grid[baris, kolom] mencapai tepat satu sel — ubah baris dan kolom untuk melihat nilai mana yang Anda capai.
Dalam Grid[2, 3], sel mana yang diakses?
Indeks pertama adalah baris, indeks kedua adalah kolom — jadi baris 2, kolom 3.
Contoh terpecahkan: pencarian linear yang dapat mengatakan "tidak ditemukan"
- Pencarian linear memeriksa setiap elemen secara berurutan dari pertama hingga target ditemukan atau akhir tercapai.
FoundAt ← -1
FOR i ← 1 TO n
IF A[i] = Target THEN
FoundAt ← i
ENDIF
NEXT i
IF FoundAt = -1 THEN
OUTPUT "Not found"
ELSE
OUTPUT "Found at ", FoundAt
ENDIF
-1tidak pernah bisa menjadi index valid, jadi berarti "tidak ditemukan". Inisialisasi sebelum loop dan uji setelah. Pencarian yang tidak pernah mengatakan "tidak ditemukan" kehilangan poin.
Pencarian linear menemukan nilai dengan cara:
Pencarian linear memeriksa elemen satu per satu dari awal hingga menemu target (atau mencapai akhir).
Menetapkan FoundAt menjadi -1 sebelum pencarian linear memungkinkan program melaporkan "tidak ditemukan" setelah loop.
-1 tidak pernah menjadi indeks yang valid, jadi jika tidak berubah setelah loop, target tidak ada dalam array.
Nilai terbesar, dan di mana lokasinya
Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
IF A[i] > Largest THEN
Largest ← A[i]
Position ← i
ENDIF
NEXT i
OUTPUT Largest, " at ", Position
- Mulai
Largestpada elemen pertama, jangan pernah di 0: array mungkin berisi semua nilai negatif. - Bentuk yang sama menghitung atau menghasilkan elemen non-kosong: bandingkan setiap elemen dengan penanda untuk tidak terpakai,
""atau-1, dan hitung hanya yang berbeda.
Urut gelembung
- Urut gelembung melakukan beberapa kali perulangan melalui array dengan membandingkan pasangan bersebelahan dan menukar yang urutan salah, hingga suatu perulangan tidak melakukan pertukaran apa pun.
- Setelah setiap perulangan, nilai terbesar yang belum terurut telah bergerak ke akhir, sehingga perulangan berikutnya dapat berhenti satu tempat lebih awal.
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Limit - 1
IF Data[Index] > Data[Index + 1] THEN
Temp ← Data[Index]
Data[Index] ← Data[Index + 1]
Data[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Limit ← Limit - 1
UNTIL Swapped = FALSE
Setiap perulangan membawa nilai tersisa terbesar ke akhir
Susun langkah-langkah satu kali laluan bubble-sort, dan penutupnya, secara berurutan.
Reset flag, sapu dan tukar, kurangi batas, berhenti ketika seluruh laluan tidak melakukan penukaran.
Contoh dikerjakan: di mana tanda-tanda urut gelembung berada
- Perulangan luar yang berulang hingga sebuah kali jalan tidak melakukan pertukaran; bendera
Swappeddireset keFALSEdi awal setiap kali jalan dan diaturTRUEdi dalamIF. - Tukar tiga baris melalui variabel sementara. Dua baris kehilangan sebuah nilai.
- Batas menyusut, berkurang satu setiap perulangan, karena nilai terbesar sudah mencapai ujung.
- Secara kata-kata, untuk soal penyempurnaan bertahap: ulangi hingga terurut; pada setiap perulangan bandingkan pasangan bersebelahan; tukar pasangan yang urutan salah; setelah setiap perulangan nilai terbesar yang belum terurut berada di akhir.
Fitur mana yang mendapatkan nilai dalam bubble sort yang efisien? Pilih semua yang berlaku.
Flag, tukar dengan variabel sementara, kurangi batas: itu poin-poinnya. Menyalin array bukan bagian dari algoritma.
Contoh dikerjakan: menghapus dan menyisipkan
- Hapus item: temukan indeksnya dengan pencarian linear; geser setiap elemen selanjutnya satu tempat menuju awal agar celah tertutup; tandai elemen terakhir sebagai tidak terpakai, atau kurangi jumlah.
- Sisipkan ke dalam array terurut: temukan indeks pertama yang elemennya lebih besar; geser elemen itu dan setiap elemen selanjutnya satu tempat menuju akhir, dimulai dari yang terakhir; simpan nilai baru di celah.
- Gerakkan dari akhir saat membuka celah dan dari awal saat menutupnya, atau Anda akan menimpa nilai yang sedang dipindahkan.
Array menyimpan banyak item dari JENIS YANG SAMA yang diakses oleh indeks, sedangkan record mengelompokkan field dari (mungkin) JENIS BERBEDA yang diakses oleh nama.
Array 2-D cocok untuk grid (baris × kolom); record cocok untuk satu hal yang dijelaskan oleh beberapa field bernama.
⟦⟧ Nilai yang sering terlewat
[0:99]menampung 100 elemen. Hitung kedua batas.- Indeks adalah
INTEGER; deklaran memerlukan tipe serta batas. Grid[row, column]: baris terlebih dahulu. Menukarnya akan membaca sel yang salah di setiap loop bersarang.- Tukar memerlukan variabel sementara; pencarian memerlukan jalur "tidak ditemukan"; urut gelembung berakhir ketika suatu perulangan tidak melakukan pertukaran, bukan setelah jumlah perulangan tetap.
Anda telah memahaminya
- array menampung sejumlah tetap elemen bertipe sama di bawah satu pengenal, dicapai melalui indeks antara batas bawah dan batas atas; jumlah = batas atas − batas bawah + 1
- 1-D adalah daftar, 2-D adalah tabel
[row, column]dilalui oleh loop bersarang; deklarasikan dengan batas dan tipe - pencarian linear:
FoundAt ← -1, loop, simpan indeks, uji setelah loop; nilai terbesar: mulai dariA[1], simpan posisinya - urut gelembung: perbandingan dan tukar bersebelahan dengan variabel sementara, flag
Swapped, batas menyusut, hingga suatu perulangan tidak melakukan pertukaran