Carian linear melihat senarai dari item pertama sehingga menjumpai sasaran atau kehabisan item. Dalam peperiksaan, anda biasanya diberi algoritma dan sedikit data, lalu diminta melengkapkan jadual jejak dan menyatakan hasilnya.
Pelajaran ini sebahagian daripada carian, isihan dan fail. Ia bergantung pada idea gelung dan tatasusunan daripada pengulangan dan tatasusunan.
Bagaimana menjejak algoritma langkah demi langkah?
Jadual jejak mempunyai satu lajur untuk setiap pemboleh ubah dan satu baris setiap kali nilai berubah. Anda bertindak sebagai komputer: baca satu baris, kemas kini hanya apa yang diubah oleh baris itu, dan tulis nilai baharu.
Tiga tabiat menjadikannya boleh dipercayai:
- Senaraikan setiap pemboleh ubah yang muncul dalam kod, termasuk bendera seperti
Found. - Nilai syarat gelung setiap kali, sebelum masuk ke dalam badan gelung.
- Salin nilai yang tidak berubah ke bawah supaya setiap baris menunjukkan keadaan penuh.
Contoh berlangkah
Sebuah kedai rekaan menyimpan enam kod produk dalam tatasusunan. Tatasusunan itu mempunyai kedudukan 1 hingga 6.
| Kedudukan | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Codes | 14 | 9 | 27 | 9 | 31 | 5 |
Found ← FALSE
Index ← 1
WHILE Index <= 6 AND Found = FALSE
IF Codes[Index] = Target THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Found at position ", Index
ELSE
OUTPUT "Not found"
ENDIFJejak dengan Target = 27.
| Langkah | Index | Codes[Index] | Codes[Index] = Target? | Found |
|---|---|---|---|---|
| Mula | 1 | FALSE | ||
| Pusingan 1 | 1 | 14 | Tidak | FALSE |
| Pusingan 2 | 2 | 9 | Tidak | FALSE |
| Pusingan 3 | 3 | 27 | Ya | TRUE |
Selepas pusingan 3, Found ialah TRUE, maka syarat gagal dan gelung berakhir. Outputnya ialah Found at position 3, selepas tiga perbandingan.
Jejak dengan Target = 8. Tiada kod yang sama dengan 8, jadi gelung berjalan untuk Index = 1, 2, 3, 4, 5, 6 dengan enam perbandingan yang gagal. Selepas yang keenam, Index menjadi 7. Syarat Index <= 6 kini palsu, maka gelung berakhir dan Found masih FALSE. Outputnya ialah Not found, dan carian membuat enam perbandingan.
Kesilapan yang perlu diawasi
Berikut ialah versi yang menggerakkan indeks walaupun selepas padanan:
WHILE Index <= 6 AND Found = FALSE
IF Codes[Index] = Target THEN
Found ← TRUE
ENDIF
Index ← Index + 1
ENDWHILEDengan Target = 27, padanan berlaku pada Index = 3, tetapi baris penambahan masih berjalan, jadi Index menjadi 4 sebelum gelung berakhir. Output akan menyatakan kedudukan 4, sedangkan Codes[4] ialah 9, bukan 27.
Pembetulannya ialah meletakkan Index ← Index + 1 dalam cabang ELSE supaya ia hanya berjalan apabila item tidak sepadan. Semasa menjejak, tanya pada setiap baris: “baris mana yang mengubah pemboleh ubah ini, dan adakah ia dibenarkan berjalan?”
Semak sendiri
Gunakan tatasusunan dan algoritma yang sama.
1. Target = 31. Apakah outputnya dan berapa perbandingan dibuat?
Lihat jawapan
Index bergerak 1, 2, 3, 4, 5. Codes[5] = 31 sepadan pada perbandingan kelima. Output: Found at position 5, lima perbandingan.
2. Target = 9. Kedudukan mana yang dilaporkan, dan mengapa kedudukan 4 tidak pernah dilaporkan?
Lihat jawapan
Codes[2] = 9 sepadan pada perbandingan kedua, maka Found menjadi TRUE dan gelung berhenti. Output: Found at position 2. Kedudukan 4 juga menyimpan 9 tetapi gelung berhenti sebelum sampai ke sana.
3. Target = 5. Berapa perbandingan dibuat, dan adakah ini kes terbaik atau terburuk bagi sasaran yang ada?
Lihat jawapan
Nombor 5 berada paling akhir, pada kedudukan 6, maka enam perbandingan. Ini kes terburuk bagi sasaran yang ada, kerana setiap item disemak.
Ke mana selepas ini
Apabila jejak sudah mantap, cuba terangkan satu pusingan isihan, iaitu algoritma yang menukar nilai dalam senarai semasa berjalan. Pelatih jejak pseudokod terhad membolehkan anda menggerakkan algoritma seperti ini dan membandingkan jadual anda dengan jadual mesin.
Sesetengah pelajar boleh membaca kod tetapi kehilangan markah kerana satu baris jejak terlepas satu perubahan. Guru dalam tuisyen Computer Science dalam talian satu dengan satu boleh memerhati jejak anda dan menunjukkan baris yang terlepas itu.