UNIT
3 SENARAI & SENARAI BERPAUT Pengenalan kepada Senarai Definisi Senarai Menggunakan Senarai Pengenalan kepada Senarai Berpaut Definisi Senarai Berpaut Menggunakan Senarai Berpaut
F4104 ALGORITMA & STRUKTUR DATA
3.1 • • •
3.2 • • •
3.3 • •
Pengenalan kepada senarai Struktur data yang tidak boleh menukarkan saiznya semasa program dilaksanakan dinamakan struktur data statik. Struktur data jenis ini perlu ditetapkan saiznya terlebih dahulu. Kelebihannya adalah ia menyediakan cara mencapai ahli-ahli dalam struktur ini dengan mudah. Definisi senarai Senarai adalah satu kumpulan koleksi data, elemen, komponen atau objek yang sama jenis Senarai selalunya berbentuk seperti satu rekod. Operasi-operasi yang boleh dilakukan ke atas senarai adalah : - Menambah (insertion) menambah item baru ke dalam senarai - Menghapus (deletion) menghapuskan satu item daripada senarai. Operasi ini melibatkan proses mengenalpasti lokasi item seterusnya menghapuskan item tersebut. Selepas itu, item yang berada di bawah perlu dianjakkan ke atas. - Mencari (retrieval) mengenalpasti item dari senarai dan memaparkannya - Menyenarai (traversal) Semua item akan disenaraikan secara tersusun. Operasi ini memerlukan satu algoritma ulangan.
Mengimplementasikan operasi senarai secara tatsusunan Senarai boleh diimplementasi secara tatasusunan yang mempunyai item yang berjujukan Jujukan tersebut adalah berdasarkan kepada susunan dimana, item yang pertama dimasukkan akan berada pada kedudukan pertama dalam tatasusunan, begitulah turutan kedudukan item seterusnya. senarai
P0
P1
P2
P3
X[0]
X[1]
X[2]
X[3]
....
Pn
tatasusunan
3.4
....
X[n]
Menggunakan operasi senarai
•
Operasi yang terlibat dalam mengimplementasi senarai secara tatasusunan adalah mencipta, menyemak, menambah dan menghapus item-item dalam senarai.
•
Mencipta senarai - Akan melibatkan proses menentukan bilangan maksimum bagi item yang hendak digunakan dalam senarai - Proses yang seterusnya ialah mengenalpasti jenis-jenis item yang diperlukan - Input : Bilangan item dan jenis item - Proses : Mencipta satu senarai kosong - Output : Senarai tercipta
•
Menyemak senarai - Proses ini adalah untuk mengenalpasti sama ada senarai kosong atau penuh
24
F4104 ALGORITMA & STRUKTUR DATA
-
Terbahagi kepada dua cara iaitu: a) Proses menentukan senarai kosong atau tidak - Input : Menerima satu senarai - Proses : Mengenalpasti sama ada item pertama wujud atau tidak - Output : Jika terdapat item pertama, senarai tidak kosong b)
Proses menentukan senarai penuh atau tidak - Input : Menerima satu senarai - Proses : Mengenalpasti sama ada item terkahir wujud atau tidak - Jika terdapat item terakhir, senarai penuh
•
Menambah item-item dalam senarai - Melibatkan penerimaan item baru - Item terakhir dalam senarai dikenalpasti kedudukannya untuk proses menambah item dalam senarai - Input : Menerima satu senarai - Proses : Pastikan senarai tidak penuh. Terima item baru. Tentukan kedudukan item terakhir. Masukkan item baru. - Output : Senarai yang telah dikemaskinikan (item baru ditambah)
•
Menghapuskan ahli dalam senarai - Proses menghapuskan item yang terdapat di dalam satu senarai - Senarai yang diterima perlu disemak untuk menentukan senarai tidak kosong. - Item yang hendak dihapuskan perlu dikenalpasti - Input : Menerima satu senarai - Proses : Pastikan senarai tidak kosong. Kenalpasti item. Item disemak dalam senarai untuk menentukan kedudukan. Proses hapus dan anjak item dilaksanakan - Output : senarai yang telah dikemaskini (item telah dihapuskan)
25
F4104 ALGORITMA & STRUKTUR DATA
3.5 • •
3.6 • • •
Pengenalan kepada senarai berpaut Senarai berpaut adalah sejenis struktur data di mana setiap itemnya mempunyai hubungkait antara item yang lain dalam satu senarai Segala operasi yang hendak dilaksanakan ke atas sesuatu item perlulah mengambilkira item yang berada bersebelahannya Definisi senarai berpaut Senarai berpaut adalah satu kumpulan item yang dinamik di mana saiznya akan bertambah dan berkurang bergantung kepada jumlah itemnya. Item di dalam senarai berpaut mempunyai dua medan iaitu medan data dan medan pautan. Operasi-operasi yang boleh dilakukan ke atas senarai berpaut adalah :-
•
Mencipta senarai berpaut - Menghasilkan satu senarai berpaut baru
•
Mencipta nod dalam senarai berpaut - Menghasilkan satu punca baru untuk menghubungkan antara item-item dalam senarai berpaut
•
Menyemak senarai berpaut : penuh / kosong - Mengenalpasti sama ada senarai berpaut kosng atau penuh
•
Menghapuskan nod dalam senarai berpaut - Mengenalpasti nod (hubungan item) - Menghapuskan satu item daripada senarai berpaut - Operasi melibatkan proses mengenalpasti lokasi item seterusnya memutuskan pautan - Selepas itu, item yang berada sebelumnya perlu dipautkan kepada item berikutnya.
•
Menambah nod dalam senarai berpaut - Mengenalpasti nod (hubungan item) - Menambah satu item ke dalam senarai berpaut - Operasi melibatkan proses mengenalpasti lokasi item, seterusnya menyelitkan item baru ke dalam senarai berpaut
3.7 • •
3.8 • • •
Mengimplementasikan operasi senarai berpaut linear Senarai berpaut linear ialah dimana data disusun secara bersiri Item-item disusun dalam bentuk mengikut susunan dimana item kedua berada dibelakang item pertama, item ketiga berada dibelakang item kedua dan seterusnya. Menggunakan operasi senarai berpaut linear Senarai berpaut adalah satu jenis senarai yang dinamik, bermakna mengimplementasikannya, penuding adalah perlu. Operasi yang terlibat dalam mengimplementasi senarai berpaut adalah :Mencipta senarai - Proses mencipta senarai berpaut memerlukan pengisytiharan struct - Jenis-jenis item yang perlu dimasukkan perlu dikenalpasti terlebih dahulu - Input : Jenis-jenis item - Proses : Cipta satu senarai kosong
untuk
26
F4104 ALGORITMA & STRUKTUR DATA
-
Output : Senarai tercipta
•
Mencipta nod dalam senarai berpaut - Perlu diimplementasikan dengan menggunakan penuding yang dapat menyediakan ruang ingatan untuk nod secara dinamik - Untuk tujuan mencipta nod secara dinamik, fungsi malloc( ) perlu digunakan - Ini perlu kerana apabaila hendak menambah satu otem baru, item baru tersebut perlu dipautkan kepada item sebelumnya (item lama) dalam senrai dimana proses ini dilakukan melalui nod - Input : Menerima satu senarai - Proses : Mencipta satu nod baru - Output : Satu senarai yang boleh menerima item baru
•
Menyemak senarai berpaut - Untuk mengenalpasti sama ada senarai kosong atau tidak - Melibatkan pengujian pembolehubah dalam senarai berpaut sama ada ianya kosong (null) atau tidak - Input : Menerima satu senarai berpaut - Proses : Mengenalpasti sama ada pembolehubah null wujud atau tidak - Output : Jika null, senrai berpaut adalah kosong
•
Menambah nod dalam senarai berpaut - Menambah nod ke dalam senarai berpaut boleh terdiri daripada menambah di bahagian hujung senarai atau di bahagain tengah senarai. - Input : Menerima satu senrai berpaut - Proses : Menyemak pembolehubah. Kenalpasti lokasi. Terima item baru. Masukkan item baru - Output : Senarai yang telah dikemaskinikan (item baru ditambah)
•
-
Menambah nod di hujung senarai o Untuk menambah nod pada hujung senarai, perlu semak sama ada pembolehubah Null atau tidak o Jika pembolehubah Null, ini bermaksud senarai kosong dan item akan ditambah pada lokasi pertama. o Jika pembolehubah tidak Null atau mempunyai nilai, ini bermaksud senrai mengandungi item, maka penambahan dilakukan di lokasi terakhir dalam senarai.
-
Menambah nod di tengah senarai o Lokasi yang hendak ditambah perlu dikenalpasti o Nod pada lokasi tersebut diputuskan untuk membuat penyambungan nod item baru
Menghapuskan item dalam senarai berpaut - Menghapuskan item bermaksud item yang tidak diperlukan akan dibuang atau dikeluarkan daripada senarai - Proses menghapuskan item terbahagi kepada 3 iaitu menghapus item tunggal, menghapus item di tengah senarai dan menghapus item di hujung senarai. - Senarai yang diterima perlu disemak untuk menentukan ianya bukan satu senarai kosong - Item yang hendak dihapuskan perlu dikenalpasti - Item perlu dihapuskan dan dikemaskini - Input : Menerima satu senarai
27
F4104 ALGORITMA & STRUKTUR DATA
-
Proses : Pastikan senarai tidak kosong. Kenalpasti item. Item disemak dalam senarai untuk menentukan kedudukannya. Proses hapus dan anjakitem dilaksanakan. Output : Senarai yang telah dikemaskini (item telah dihapuskan) Menghapus item tunggal ○ Item dalam senarai diuji untuk mengenalpasti pembolehubah x wujud, ini bermakna item berada di penghujung senarai ○ Pautan pada item diputuskan dan disambung pada pembolehubah Null DATA DATA
NULL
X
Selepas proses hapus
Sebelum proses hapus -
X
Menghapus item dihujung senarai ○ Item dalam senarai diuji untuk mengenalpasti pembolehubah x wujud, ini bermakna item berada di penghujung senarai. ○ Pepaut pada item di[utuskan dan disambung pada pembolehubah x
DATA1
DATA2
DATA3
DATA4
X
Sebelum proses hapus DATA4 DATA1
DATA2
DATA3
X
X
Selepas proses hapus -
Menghapus item di tengah senarai ○ Item sebelum dan selepas dikenalpasti ○ Pautan pada item sebelum dan selepas diputuskan dan disambung DATA1
DATA2
DATA3
DATA4
X
Sebelum proses hapus
DATA2
DATA1
DATA3
DATA4
X
Selepas proses hapus
28
F4104 ALGORITMA & STRUKTUR DATA
•
Keberkesanan penggunaan senarai berpaut
Kebaikan Saiz senarai yang dinamik Proses tambah dan hapus item tidak perlukan pergerakan item yang banyak Masa digunakan untk proses tambah dan hapus lebih singkat Sesuai digunakan untuk senarai yang besar (saiz tidak diketahui)
Kelemahan Proses pengaturcaraan lebih kompleks Penggunaan ingatan dan masa pengkomputeran yang tinggi Tidak sesuai untuk senarai yang ringkas Proses pengemaskinian aturcara lebih rumit
29
