TINDANAN & BARIS GILIR

UNIT

4 TINDANAN & BARIS GILIR Pengenalan kepada Tindanan Operasi Asas Tindanan Implementasi Tindanan Pengenalan kepada Baris Gilir Operasi Asas Baris Gilir Implementasi Baris Gilir

F4104 ALGORITMA & STRUKTUR DATA

TINDANAN 4.1 •

Pengenalan Tindanan merupakan satu struktur data di mana kemasukkan dan penghapusan berlaku pada satu hujung yang sama di panggil top.

•

Kemasukkan data dikenali sebagai Push dan penghapusan data Pop.

•

Struktur data ini berdasarkan konsep LIFO (Last in first out).

•

Tindanan boleh digambarkan seperti dalam Rajah (a) di mana penyusunan pinggan mangkuk di kafeteria dan juga penyusunan buku-buku di atas meja atau dalam kotak. Pinggan akan di susun dan kemudian pinggan yang teratas akan di ambil dahulu yang merupakan pinggan yang terakhir di letakkan dalam susunan tersebut. Keadaan ini juga sama bagi penyusunan buku-buku di atas meja atau dalam kotak.. 4 3 2 1

Rajah (a) Tindanan Pinggan

•

Rajah (a) menunjukkan susunan pinggan, di mana pinggan 1 di masukkan dahulu, di ikuti pinggan 2 dan seterusnya. Jika pinggan-pinggan tersebut hendak digunakan maka pinggan 4 akan dikeluarkan dahalu.

•

Keadaan yang ditunjukkan pada Rajah (b) di mana kemasukkan dan pengeluaran disket hanya dilakukan pada satu bahagian (atas) sahaja.

•

Konsep struktur data tindanan di aplikasi bagi mana-mana masalah yang memerlukan penyelesaian tindanan seperti penukaran nombor decimal kepada binari, infix kepada postfix dan sebagainya. Struktur data tindanan di implementasi secara tatasusunan dan senarai berpaut.

push

push

Tambah data

Tambah data

pop

Mengeluarkan data

Rajah (b) Operasi Push dan Pop Tindanan Disket

31


•

Terdapat 2 operasi asas timbunan iaitu :1.

‘Push’ merupakan istilah yang digunakan untuk memasukkan atau menambah suatu data ke atas timbunan sediaada. Push ini meletakkan data pada bahagian atas timbunan yang membuatkan data yang baru berada di bahagian teratas. Masalah yang mungkin dihadapi dengan operasi push ialah timbunan limpah-atas (overflow) dimana ia merupakan keadaan keputusan yang terhasil daripada percubaan untuk meletak data ke atas timbunan yang penuh.

2.

‘Pop’ merupakan istilah yang digunakan untuk memadam atau mengeluar data daripada timbunan. Ia mengeluarkan data teratas daripada timbunan dan data di bawahnya menjadi data yang teratas. Masalah yang munkin dihadapi dalam operasi pop adalah timbunan limpah-bawah (underflow) dimana ia merupakan keadaan keputusan yang dihasilkan daripada percubaan untuk pengurangan data daripada timbunan kosong.

•

4.2 •

Secara ringkasnya timbunan ini menggunakan konsep LIFO ( Last In First Out)

Operasi-Operasi Asas Tindanan Terdapat 5 operasi asas bagi tindanan iaitu 1. Mencipta tindanan 2. Menyemak tindanan kosong. 3. Menyemak tindanan penuh. 4. Memasukkan data ke dalam tindanan (push). 5. Menghapuskan data dari tindanan (pop).

Operasi-operasi di atas di perlu bagi sesuatu tindanan yang di implementasi secara tatasusunan. Jika tindanan di implementasi secara senarai berpuat maka operasi menyemak tindanan penuh tidak diperlukan. Ini kerana, dalam senarai berpaut kita tidak perlu nyatakan saiz bagi sesuatu tindanan. Tetapi dalam tatasusunan kita perlu nyatakan saiz bagi tatasusunan tersebut, dengan itu semakan ke atas tindanan diperlukan sama ada penuh atau tidak.

32


Mencipta Tindanan •

Operasi mencipta tindanan adalah operasi pertama yang perlu dilakukan.

•

Di mana kita perlu mencipta tindanan terlebih dahulu sebelum operasi-operasi lain di lakukan.

•

Apa yang berlaku di gambarkan seoalah-olah kita mencipta satu ruang atau bekas untuk digunakan bagi kemasukkan data. Jika bekas tiada adalah mustahil untuk kita masukkan data.

•

Sebelum tindanan di cipta kita perlu mengistiharkan struktur data. Struktur data ini penting bagi menentukan bentuk data yang kita gunakan.

Menyemak Tindanan Kosong •

Menyemak tindanan kosong di perlukan sebelum data dihapuskan dari tindanan.

•

Jika tiada data dalam tindanan maka operasi menghapuskan data tidak boleh dilakukan.

•

Satu pembolehubah digunakan untuk menunjukkan data yang teratas. Biasanya di panggil top atau atas.

Menyemak Tindanan Penuh •

Menyemak tindanan penuh diperlukan sebelum data dimasukkan ke dalam tindanan.

•

Jika tindanan telah penuh, maka operasi memasukkan data tidak boleh dilakukan.

•

Bagi menentukan sama ada data telah penuh atau tidak, keadaan ini ditunjukkan oleh atas.

•

Sesuatu tindanan di katakan penuh jika kesemua ruangan dalam tatatusunan telah digunakan.

•

Walau bagaimanapun jka tindanan diimplementasi secara senarai berpaut maka operasi ini tidak diperlukan. Ini kerana penuding tidak mempunyai had dari segi saiz.

Memasukkan Data ke dalam Tindanan •

Sebelum operasi memasukkan data ke dalam tindanan, terlebih dahulu operasi menyemak tindanan penuh dilakukan.

•

Jika tindanan masih lagi kosong atau belum penuh maka operasi tersebut boleh diteruskan.

Menghapuskan Data dari Tindanan •

Sebelum operasi mengahapuskan data dari tindanan dilakukan, operasi menyemak tindanan kosong perlu dilakukan.

•

Jika tindanan masih lagi kosong maka operasi tersebut tidak boleh dilakukan.

•

Secara logiknya, jika sesuatu bekas masih kosong apakah yang dapat dikeluarkan. 33


4.3 •

Implementasi Tindanan Struktur data tindanan boleh diimplentasi dengan dua cara iaitu 1. Implementasi secara tatasusunan 2. Implementasi secara senarai berpaut

•

Perbezaan di antara cara implementasi ialah dari segi gaya pengkodan aturcara.

•

Implementasi secara senarai berpaut tidak memerlukan operasi menyemak tindanan penuh.

•

Ini kerana saiz bagi tindanan tidak perlu dinyatakan. Operasi-operasi lain diperlukan tetapi cara pengkodan yang berbeza.

4.3.1 •

Implementasi Secara Tatasusunan

Dalam implementasi secara tatasusunan kita mulakan pengkodan aturcara dengan mengistiharkan struktur data.

•

Pengistiharan ini penting bagi menentukan bentuk bagi data yang kita gunakan.

•

Contoh pengitiharan struktur data adalah seperti keratan aturcara di bawah. typedef struct TINDANAN { int atas; int senarai[4]; }tindanan;

•

Bagi pengistiharan struktur data tindanan memerlukan sekurang-kurangnya dua pembolehubah yang juga dikenali dengan nama medan.

•

Satu pembolehubah digunakan untuk menyimpan nilai atas bagi tindanan.

•

Nilai ini merupakan nilai indeks bagi tatasusunan senarai.

•

Nilai ini sentiasa berubah mengikut kemasukkan dan penghapusan data tindanan.

•

Jika data dimasukkan, nilai atas bertambah dan sebaliknya.

•

Pembolehubah senarai merupakan tatasusunan yang bersaiz 4.

•

Senarai ini menyimpan data berjenis integer sahaja yang dimasukkan ke dalam tindanan.

•

Pembolehubah tindanan merupakan pembolehubah bagi struct.

34


•

Di mana pembolehubah ini mengandungi 2 data iaitu atas dan senarai. Ini dapat digambarkan seperti Rajah (c). [3] [2] [1] [0] atas

senarai

Rajah (c) : Gambaran Pembolehubah tindanan Mencipta Tindanan •

Selepas pengitiharan struktur data, kita perlu mencipta tindanan. Contoh keratan ialah ; void cipta(tindanan *t) { t->atas = -1; }

•

Daripada keratan aturcara di atas, nilai awal bagi atas ialah -1. Ada juga nilai atas adalah 0. Ini terpulang kepada corak pengaturcaraan. Nilai awal perlu diberikan sebagai nilai awalan. Keadaan selepas mencipta tindanan adalah seperti Rajah (d).

[3] [2] [1] -1

[0]

atas

senarai

Rajah (d) : Gambaran Cipta tindanan

•

Setelah tindanan di cipta maka operasi-operasi lain boleh dilaksanakan. Kita boleh melakukan operasi pop atau push dahulu.


Sebelum operasi menghapuskan data, operasi menyemak tindanan kosong perlu dilakukan. int kosong(tindanan *t) { if(t->atas == -1) return (1); else return(0); }

35


•

Ini bertujuan menyemak tindanan. Jika kosong, maka tidak boleh mengeluarkan data.

•

Bagi menentukan tindanan kosong atau tidak ialah dengan menyemak adakah nilai atas adalah -1, jika ya maka fungsi kosong memulangkan nilai 1 dan jika tidak kosong memulangkan nilai 0.

Menyemak Tindanan Penuh •

Sebelum operasi memasukkan data, operasi menyemak tindanan penuh perlu dilakukan.

•

Ini bertujuan menyemak tindanan. Jika telah penuh, maka tidak boleh memasukkan data.

int penuh(tindanan *t) { if (t->atas == 3) return (1); else return (0); }

•

Bagi menentukan tindanan penuh atau tidak ialah dengan menyemak adakah nilai atas adalah 3, jika ya maka fungsi telah penuh dan memulangkan nilai 1 manakala jika tidak penuh memulangkan nilai 0.

•

Nilai atas perlu sama dengan 3 kerana di awal tadi saiz tatasusunan adalah 4 dan indeks tatasusunan di antara 0 hingga 3. Di mana 3 merupakan nilai indeks maksimum dalam tatasusunan tersebut.


Jika fungsi penuh memulangkan nilai 0 maka data boleh ditambah.

•

Contoh keratan aturcara adalah seperti di berikut; void push(tindanan *t) { int data; if (penuh(t)== 1) cout<<"Tindanan Penuh"; else { cin>>data; t->atas++; t->senarai[t->atas] = data; } }

36


•

Jika senarai telah penuh maka mesej “Tindanan Penuh” akan di paparkan jika tidak, satu data berjenis integer (data) perlu dimasukkan.

•

Setelah data di baca, pembolehubah atas akan bertambah sebanyak satu.

•

Andaikan sebelum data di masukkan nilai atas = -1, setelah data di masukkan nilai atas =0, dan nilai data dimasukkan pada kedudukan senarai[0].

•

Rajah (e) di bawah dengan andaian pada asalnya atas = -1 dan data = 10. [3] [2] [1] [0]

0

10 senarai

atas

Rajah (e) Gambaran Satu Data Dimasukkan


Jika fungsi kosong memulangkan nilai 0 maka data dalam tindanan boleh dihapuskan.

•

Contoh keratan aturcara adalah seperti di bawah; void pop(tindanan *t) { if(kosong(t)== 1) cout<<"Tindanan Kosong"; else t->atas--; }

•

Jika senarai masih kosong maka mesej “Tindanan Kosong” akan di paparkan jika tidak, satu data akan dihapuskan.

•

Data dihapuskan dengan mengurangkan nilai atas sebanyak satu. Katakan pada asalnya nilai atas adalah 0, maka nilai atas yang baru ialah -1.

4.3.2 •

Implementasi Secara Senarai Berpaut

Dalam implementasi secara senarai berpaut kita juga perlu mulakan pengkodan aturcara dengan mengitiharkan struktur data.

•

Contoh pengitiharan struktur data adalah seperti keratan aturcara di bawah. typedef struct TINDANAN

tindanan

{

●

int data; struct TINDANAN *slps;

data

slps

}tindanan;

37


•

Bagi pengistiharan struktur data tindanan memerlukan sekurang-kurangnya dua medan data.

•

Pengitiharan struktur data ini juga dipanggil nod.

•

Satu medan menyimpan nilai bagi tindanan dan satu medan menyimpan nilai alamat bagi nod yang berada selepasnya.

•

Jika tiada nilai yang ditunding maka pembolehubah slps menyimpan nilai NULL.

Mencipta Tindanan •

Selepas pengistiharan struktur data, seterusnya tindanan dicipta dengan menggunkan kod seperti di bawah. tindanan *atas; atas = NULL;

•

Satu nod berjenis tindanan diistiharkan. Nod ini perlu bagi menuding kepada nod yang pertama di dalam tindanan.

•

Nod atas perlu di umpukkan nilai NULL sebagai nilai awalan. Gambaran mencipta tindanan seperti yang ditunjukkan pada berikut:-

NULL atas

38



Dengan senarai berpaut kita boleh gunakan keratan aturcara di bawah bagi menyemak tindanan kosong.

•

Semakan ini wujud di dalam fungsi pop.

•

Pembolehubah t digunakan untuk menerima senarai tindanan yang dihantar kepada fungsi pop.

•

Jika t adalah NULL maka tindanan masih lagi kosong. if(*t == NULL)


Keratan aturcara bagi memasukkan data ke dalam tindanan seperti di bawah.

•

Satu nod baru perlu diistiharkan bagi memasukkan data baru.

•

Gambaran selepas data baru di masukkan seperti berikut. Katakan nilai = 10. 10

●

atas

void push(tindanan **t) { int nilai; tindanan *nb,*cetak;

nb = (tindanan *) malloc(sizeof (tindanan));

peruntukan saiz memori

cout<<”Masukkan satu nilai ke dalam tindanan : ”; cin>>nilai; nb->data=nilai; nb->slps = *t; *t = nb;

masukkan nod baru dihadapan no datas sentiasa merujuk kepada nod yang baru dimasukkan atau nod berada di hadapan

}

39



Bagi menghapuskan kita perlu menyemak sama ada tindanan kosong atau tidak.

•

Keratan aturcara yang boleh digunakan adalah seperti di bawah.

•

Satu pembolehubah hp digunakan sebagai penuding sementara kepada tindanan bagi membolehkan pembolehubah t menuding kepada nod yang kedua dalam tindanan. void pop(tindanan **t) { tindanan *hp; if(*t == NULL) cout<<"\nTindanan Kosong"; else { hp=*t; *t=hp->slps; } }

40


BARIS GILIR 4.4

•

Pengenalan

Baris gilir merupakan struktur data di mana kemasukkan dan penghapusan berlaku pada hujung yang berlainan.

•

Bahagian kemasukkan data di panggil ekor dan bahagian berlaku penghapusan data di panggil kepala.

•

Struktur data ini berdasarkan konsep FIFO (First In First Out).

•

Kita boleh gambarkan di kaunter bayaran, kaunter bank, pelajar menunggu giliran menaiki bas dan pelbagai keadaan yang berbentuk barisan.

•

Perhatikan gambaran struktur data baris gilir pada Rajah (a)

Kaunter bayaran

Keadaan 1 (asal)

A

B

C

E

D

kepala

Kaunter bayaran

Keadaan 2 ( A keluar )

ekor

C

B

E

D

A kepala

Kaunter bayaran

Keadaan 3 (F masuk)

B

ekor

C

D

E

kepala

F

ekor

Rajah (a) Operasi masuk dan keluar bagi satu baris-gilir •

Rajah (a) menunjukkan sebaris individu yang menunggu untuk mendapat perkhidmatan di kaunter bayaran.

•

Dalam keadaan 1, pelanggan A adalah kepala dan individu E merupakan ekor.

•

Pada keadaan 2, pelanggan A telah mendapat perkhidmatan dan keluar dari barisan.

•

Kini, pelanggan B menjadi kepala tetapi pelanggan E tetap menjadi ekor.

•

Pada keadaan 3, ada pelanggan yang baru sampai.

•

Pelanggan tersebut berada di akhir barisan dengan itu menjadi ekor.

41


•

Terdapat dua bentuk baris gilir. Bentuk yang pertama ialah baris gilir linear yang biasa di panggil baris gilir dan baris gilir membulat. Perbezaan di antara kedua-dua bentuk ini ialah pada cara perlaksanaan operasi-operasinya manakala konsep adalah sama

4.5 •

Operasi-Operasi Asas Baris-Gilir Terdapat 5 operasi asas bagi tindanan iaitu 1. Mencipta baris gilir 2. Menyemak baris gilir kosong. 3. Menyemak baris gilir penuh. 4. Memasukkan data ke dalam baris gilir. 5. Menghapuskan data dari baris gilir.

Operasi-operasi di atas di perlu bagi sesuatu baris gilir yang di implementasi secara tatasusunan. Jika baris gilir di implementasi secara senarai berpaut maka operasi menyemak baris gilir penuh tidak diperlukan. Ini kerana, dalam senarai berpaut kita tidak perlu nyatakan saiz bagi sesuatu tindanan. Tetapi dalam tatasusunan kita perlu nyatakan saiz bagi tatasusunan tersebut, dengan itu semakan ke atas tindanan diperlukan sama ada penuh atau tidak. Senarai berpaut tidak boleh diimplementasi ke atas baris gilir membulat. Mencipta Baris-Gilir •

Operasi mencipta baris gilir adalah operasi pertama yang perlu dilakukan.

•

Di mana kita perlu mencipta baris gilir terlebih dahulu sebelum operasi-operasi lain di lakukan.

•

Apa yang berlaku di gambarkan seperti kita mencipta satu ruang atau bekas untuk digunakan bagi kemasukkan data.

•

Jika bekas tiada adalah mustahil untuk kita masukkan data.

•

Sebelum baris gilir di cipta kita perlu mengistiharkan struktur data. Struktur data ini penting bagi menentukan bentuk data yang kita gunakan.

Menyemak Baris-Gilir Kosong •

Menyemak baris gilir kosong diperlukan sebelum data dihapuskan dari baris gilir .

•

Jika tiada data dalam baris gilir

maka operasi menghapuskan data tidak boleh

dilakukan. •

Satu pembolehubah digunakan untuk menunjukkan data di hadapan, biasanya di panggil kepala

42


Menyemak baris-Gilir Penuh •

Menyemak baris gilir penuh diperlukan sebelum data dimasukkan ke dalam baris gilir .

•

Jika baris gilir telah penuh, maka operasi memasukkan data tidak boleh dilakukan.

•

Satu pembolehubah digunakan untuk menunjukkan data di belakang, biasanya di panggil ekor.

•

Sesuatu baris gilir

dikatakan penuh jika kesemua ruangan dalam tatatusunan telah

digunakan atau ekor bersamaan dengan saiz tatasusunan. •

Walau bagaimanapun jka baris gilir diimplementasi secara penuding maka operasi ini tidak diperlukan. Ini kerana penuding tidak mempunyai had dari segi saiz.

Memasukkan Data ke dalam Baris-Gilir •

Sebelum operasi memasukkan data ke dalam baris gilir , terlebih dahulu operasi menyemak baris gilir penuh dilakukan.

•

Jika baris gilir

masih lagi kosong atau belum penuh maka operasi tersebut boleh

diteruskan.

Menghapuskan Data dari Baris-Gilir •

Sebelum operasi menghapuskan data dari baris gilir dilakukan, operasi menyemak baris gilir kosong perlu dilakukan.

•

Jika baris gilir masih lagi kosong maka operasi tersebut tidak boleh dilakukan.

•

Secara logiknya, jika sesuatu bekas masih kosong apakah yang dapat dikeluarkan.

4.6 •

Implementasi Baris-Gilir Struktur data baris gilir boleh diimplentasi dengan dua cara iaitu 1. Implementasi secara tatasusunan •

Baris gilir linear

•

Baris gilir membulat

2. Implementasi secara senarai berpaut 4.6.1 •

Implementasi Secara Tatasusunan – Baris-Gilir Linear

Dalam implementasi secara tatasusunan kita mulakan pengkodan aturcara dengan mengistiharkan struktur data.

•

Pengistiharan ini penting bagi menentukan bentuk bagi data yang kita gunakan.

•

Contoh pengitiharan struktur data adalah seperti keratan aturcara di bawah. typedef struct BARISGILIR { int kepala,ekor; int senarai[4]; }barisgilir; 43


•

Selepas pengisytiharan, baris-gilir digambarkan seperti Rajah (b). Dua pembolehubah digunakan bagi menyimpan nilai indek data di hadapan dan belakang senarai.

[3] [2] [1] [0]

kepala

ekor

senarai

Rajah (b) : Gambaran Pemblolehubah Baris-Gilir Rajah Mencipta Baris-Gilir • Selepas pengisytiharan struktur data, cipta baris gilir dengan memberikan nilai 0 kepada pembolehubah kepala dan ekor. Keratan aturcara yang berkenaan adalah seperti di berikut: void cipta(barisgilir *bg) { bg->kepala = 0; bg->ekor = 0; } •

Gambaran baris-gilir selepas proses di atas adalah seperti Rajah (c). 0 ekor 0

[3] [2] [1] [0]

senarai kepala

Rajah (c) : Gambaran Cipta Baris-Gilir Menyemak Baris-Gilir Kosong •

Operasi ini perlu sebelum data di hapuskan. Keratan aturcara yang digunakan adalah seperti berikut: int kosong(barisgilir *bg) { if(bg->ekor == 0) return (1); else return(0); }

•

Jika nilai ekor = 0 maka baris gilir masih lagi kosong, di mana belum ada data di masukkan.

44


Menyemak Baris-Gilir Penuh •

Operasi ini dilakukan sebelum data di masukkan. Keratan aturcara yang digunakan adalah seperti berikut: int penuh(barisgilir *bg) { if (bg->ekor == 4) return (1); else return (0); }

•

Jika nilai ekor = 4, iaitu merupakan saiz tatasusunan dalam contoh ini maka baris gilir telah penuh.


Keratan aturcara di bawah digunakan untuk memasukkan data.

•

Jika fungsi penuh tidak memulangkan nilai 1 maka data boleh di tambah ke dalam baris gilir. Nilai ekor akan bertambah sebanyak satu selepas data dimasukkan. void masuk(barisgilir *bg) { int i,data; if (penuh(bg) == 1) printf("\nBaris Gilir Penuh"); else { cout<<"\nNilai Integer : "; cin>>data; bg->senarai[bg->ekor] = data; bg->ekor++; } }

•

Andaikan data yang dimasukkan ialah 10, maka gambaran baris gilir selepas data dimasukkan ditunjukkan pada Rajah (d). 1 ekor 0 kepala

[3] [2] [1] [0]

10 senarai

Rajah (d) Gambaran Satu Data Dimasukkan

45



Keratan aturcara di bawah digunakan untuk menghapuskan data.

•

Jika fungsi kosong tidak memulangkan nilai 1 maka data boleh di keluarkan dari baris gilir. Nilai kepala akan bertambah sebanyak satu selepas data dikeluarkan. void hapus(barisgilir *bg) { int i; if(kosong(bg) == 1) cout<<"\n Baris Gilir Kosong"; else { bg->kepala++; cout<<"\nNilai kepala\n"<kepala; } }

•

Andaikan menggunakan senarai yang sama. Dengan itu data yang dikeluarakan ialah 10 pada indek 0. Maka gambaran baris gilir selepas data dimasukkan ditunjukkan pada Rajah (e). 1 ekor 0 kepala

[3] [2] [1] [0]

10 senarai

Rajah (e) : Gambaran Satu DataDihapuskan

46


4.6.2 •

Implementasi Secara Tatasusunan – Baris-Gilir Membulat

Daripada Rajah (e), nilai ekor ialah 1. Andaikan jika 4 data di masukkan ke dalam baris gilir tersebut.

•

Apakah yang berlaku pada data ke 4. Data ke 4 tidak dapat di masukkan kerana baris gilir telah penuh.

•

Pada masa ini fungsi penuh memulangkan nilai 1 kerana nila ekor = 4. Kita dapati masih ada satu ruang kosong pada indek 0 dalam baris gilir.

•

Keadaan ini menyebabkan pembaziran di mana ruangan tidak dapat digunakan sepenuhnya. Bagi mengatasi masalah ini, kita menganggap baris gilir adalah membulat.

Mencipta Baris-Gilir Membulat •

Bagi mencipta baris-gilir membulat, keratan aturcara digunakan. void cipta(barisgilir *bg) { bg->kepala = 0; bg->ekor = 0; bg->bilangan = 0; }

•

Pembolehubah bilangan digunakan bagi menyimpan bilangan data yang ada dalam senarai baris gilir membulat. Gambaran selepas mencipta baris gilir seperti di tunjukkan pada Rajah (f).

0

1

ekor kepala

3

2

Rajah (f) : Gambaran Baris-Gilir Membulat Menyemak Baris-Gilir Membulat Kosong •

Operasi ini perlu sebelum data di hapuskan. Keratan aturcara yang digunakan adalah seperti berikut. int kosong(barisgilir *bg) { if(bg->ekor == bg->kepala) return (1); else return(0); }

47


Menyemak Baris-Gilir Membulat Penuh •

Operasi ini perlu sebelum data di hapuskan. Keratan aturcara yang digunakan adalah seperti berikut. int penuh(barisgilir *bg) { if (((bg->ekor + 1)% 4) == bg->kepala) return (1); else return (0); }

Memasukkan Data ke dalam baris-Gilir •

Keratan aturcara di bawah digunakan untuk memasukkan data.

•

Jika fungsi penuh tidak memulangkan nilai 1 maka data boleh di tambah ke dalam baris gilir.

•

Nilai ekor akan bertambah sebanyak satu selepas data dimasukkan. void masuk(barisgilir *bg) { int i,data; if (penuh(bg) == 1) cout<<"\nBaris Gilir Penuh"; else { cout<<"\nNilai Integer : "; cin>>data; bg->senarai[bg->ekor] = data; bg->ekor = (bg->ekor + 1) % 4; bg->bilangan++; } }

•

Andaikan data yang dimasukkan ialah 10, maka gambaran baris gilir selepas data dimasukkan ditunjukkan pada Rajah (g)

1

0

10

ekor

kepala

2 3

Rajah (g) : Data dimasukkan Dalam Baris-Gilir Membulat

48


Menghapus Data dari Baris-Gilir Membulat •

Keratan aturcara di bawah digunakan untuk menghapuskan data.

•

Jika fungsi kosong tidak memulangkan nilai 1 maka data boleh di keluarkan dari baris gilir.

•

Nilai kepala akan bertambah sebanyak satu selepas data dihapuskan. void hapus(barisgilir *bg) { int i; if(kosong(bg) == 1) cout"\n Baris Gilir Kosong"; else { bg->kepala = (bg->kepala + 1) % 4; bg->bilangan--; } }

4.6.3 •

Implementasi Secara Senarai Berpaut

Seperti struktur data tindanan, kita juga boleh mengimplementasikan struktur data baris gilir secara senarai berpaut. Di sini, fungsi menyemak baris gilir penuh tidak diperlukan

•

Pengisytiharan struktur data baris-gilir secara senarai berpaut adalah seperti berikut: typedef struct BARISGILIR { int data; struct BARISGILIR *slps; } barisgilir;

Mencipta Baris-Gilir •

Keratan aturcara dan keadaan yang berlaku selepas perlaksanaan pernyataan adalah seperti berikut: kepala =NULL; ekor = NULL;

NULL kepala

NULL ekor

Menyemak Baris-Gilir Kosong •

Semakan ke atas senarai perlu dilakukan kerana jika belum ada data di masukkan maka tidak boleh melakukan operasi hapus.

•

Semakan baris gilir kosong boleh dilakukan dengan keratan aturcara berikut.

•

Jika kepala masih lagi kosong bermakna senarai belum mempunyai data.

•

Kepala merujuk kepada nod di awal senarai. if(*kepala == NULL)

49



Pembolehubah nb digunakan untuk memasukkan data. Peruntukkan memori menerusi fungsi malloc ke atas nod nb perlu dilakukan sebelum data di masukkan. Sebelum nod nb berada dalam senarai baris gilir, ujian ke atas baris gilir perlu dilakukan.

•

Jika baris gilir masih lagi kosong maka *ekor dan *kepala terus merujuk kepada nod nb. Jika data di masukkan pada senarai yang telah mempunyai data, kita perlu ada nod sementara ne bagi menghubungkan senarai dengan nod nb. Aturcara berikut digunakan untuk memasukkan data.

•

Gambaran yang berlaku ke atas baris gilir setelah data di masukkan boleh di lihat pada Rajah 7.8. Daripada rajah tersebut, di andaian 2 data di masukkan iaitu nilai 10 dan 20. *kepala menuding kepada nod yang bernilai 10 manakala *ekor menuding kepada nod yang bernilai 20. void masuk(barisgilir **kepala,barisgilir **ekor) { nb = (barisgilir *) malloc(sizeof (barisgilir)); scanf("%d",&nilai); if(*ekor!=NULL) { nb->data=nilai; nb->slps = NULL; ne = *ekor; ne->slps = nb; *ekor= nb; } else { nb->data=nilai; nb->slps = NULL; *kepala = nb; *ekor = *kepala; }

10

●

kepala

20

●

ekor

}


Sebelum data dihapuskan, baris gilir perlu disemakan sama ada kosong atau tidak.

•

Keratan aturcara berikut digunakan untuk menghapus data dari baris gilir.

•

Satu nod tambahan hp diperlukan bagi menuding nilai yang hendak dihapuskan dan membolehkan *kepala menuding kepada nod yang seterusnya. void hapus(barisgilir **kepala, barisgilir **ekor) { barisgilir *hp; if(*kepala == NULL) cout<<"\nbarisgilir Kosong"; else { hp=*kepala; *kepala=hp->slps; } } 50

TINDANAN & BARIS GILIR

Recommend Documents