›
›

Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 3: Hàng đợi

Download
Chöông 3 – Haøng ñôïi  
Chöông 3 – HAØNG ÑÔÏI  
3.1. Ñònh nghóa haøng  
Trong caùc öùng duïng maùy tính, chuùng ta ñònh nghóa CTDL haøng laø moät danh  
saùch trong ñoù vieäc theâm moät phaàn töû vaøo ñöôïc thöïc hieän ôû moät ñaàu cuûa danh saùch  
(cuoái haøng), vaø vieäc laáy döõ lieäu khoûi danh saùch thöïc hieän ôû ñaàu coøn laïi (ñaàu haøng).  
Chuùng ta coù theå hình dung CTDL haøng cuõng gioáng nhö moät haøng ngöôøi laàn löôït  
chôø mua veù, ai ñeán tröôùc ñöôïc phuïc vuï tröôùc. Haøng coøn ñöôïc goïi laø danh saùch  
FIFO (First In First Out)  
Hình 3.1- Haøng ñôïi  
Caùc öùng duïng coù söû duïng haøng coøn phoå bieán hôn caùc öùng duïng coù söû duïng ngaên  
xeáp, vì khi maùy tính thöïc hieän caùc nhieäm vuï, cuõng gioáng nhö caùc coâng vieäc trong  
cuoäc soáng, moãi coâng vieäc ñeàu caàn phaûi ñôïi ñeán löôït cuûa mình. Trong moät heä thoáng  
maùy tính coù theå coù nhieàu haøng ñôïi caùc coâng vieäc ñang chôø ñeán löôït ñöôïc in, ñöôïc  
truy xuaát ñóa hoaëc ñöôïc söû duïng CPU. Trong moät chöông trình ñôn giaûn coù theå coù  
nhieàu coâng vieäc ñöôïc löu vaøo haøng ñôïi, hoaëc moät coâng vieäâc coù theå khôûi taïo moät soá  
coâng vieäc khaùc maø chuùng cuõng caàn ñöôïc löu vaøo haøng ñeå chôø ñeán löôït thöïc hieän.  
Phaàn töû ñaàu haøng seõ ñöôïc phuïc vuï tröôùc, thöôøng phaàn töû naøy ñöôïc goïi laø  
front, hay head cuûa haøng. Töông töï, phaàn töû cuoái haøng, cuõng laø phaàn töû vöøa  
ñöôïc theâm vaøo haøng, ñöôïc goïi laø rearhay tail cuûa haøng.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
37  
Chöông 3 – Haøng ñôïi  
Ñònh nghóa: Moät haøng caùc phaàn töû kieåu T laø moät chuoãi noái tieáp caùc phaàn töû cuûa T,  
keøm caùc taùc vuï sau:  
1. Taïo môùi moät ñoái töôïng haøng roãng.  
2. Theâm moät phaàn töû môùi vaøo haøng, giaû söû haøng chöa ñaày (phaàn töû döõ lieäu môùi  
luoân ñöôïc theâm vaøo cuoái haøng).  
3. Loaïi moät phaàn töû ra khoûi haøng, giaû söû haøng chöa roãng (phaàn töû bò loaïi laø phaàn  
töû taïi ñaàu haøng, thöôøng laø phaàn töû vöøa ñöôïc xöû lyù xong).  
4. Xem phaàn töû taïi ñaàu haøng (phaàn töû saép ñöôïc xöû lyù).  
3.2. Ñaëc taû haøng  
Ñeå hoaøn taát ñònh nghóa cuûa caáu truùc döõ lieäu tröøu töôïng haøng, chuùng ta ñaëc taû  
moïi taùc vuï maø haøng thöïc hieän. Caùc ñaëc taû naøy cuõng töông töï nhö caùc ñaëc taû cho  
ngaên xeáp, chuùng ta ñöa ra teân, kieåu traû veà, danh saùch thoâng soá, precondition,  
postcondition vaø uses cho moãi phöông thöùc. Entry bieåu dieãn moät kieåu toång quaùt  
cho phaàn töû chöùa trong haøng.  
template <class Entry>  
Queue<Entry>::Queue();  
post:ñoái töôïng haøng ñaõ toàn taïi vaø ñöôïc khôûi taïo laø haøng roãng.  
template <class Entry>  
ErrorCode Queue<Entry>::append(const Entry &item);  
post:neáu haøng coøn choã, itemñöôïc theâm vaøo taïi rear, ErrorCodetraû veà laø success; ngöôïc laïi,  
ErrorCodetraû veà laø overflow, haøng khoâng ñoåi.  
template <class Entry>  
ErrorCode Queue<Entry>::serve();  
post: neáu haøng khoâng roãng, phaàn töû taïi front ñöôïc laáy ñi, ErrorCode traû veà laø success; ngöôïc  
laïi, ErrorCodetraû veà laø underflow, haøng khoâng ñoåi.  
template <class Entry>  
ErrorCode Queue<Entry>::retrieve(const Entry &item) const;  
post: neáu haøng khoâng roãng, phaàn töû taïi front ñöôïc cheùp vaøo item, ErrorCode traû veà laø  
success; ngöôïc laïi, ErrorCode traû veà laø underflow; caû hai tröôøng hôïp haøng ñeàu khoâng  
ñoåi.  
template <class Entry>  
bool Queue<Entry>::empty() const;  
post: haøm traû veà trueneáu haøng roãng; ngöôïc laïi, haøm traû veà false.  
Töø append (theâm vaøo haøng) vaø serve (ñaõ ñöôïc phuïc vuï) ñöôïc duøng cho caùc taùc  
vuï cô baûn treân haøng ñeå chæ ra moät caùch roõ raøng coâng vieäc thöïc hieän ñoái vôùi haøng,  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
38  
Chöông 3 – Haøng ñôïi  
vaø ñeå traùnh nhaàm laãn vôùi nhöõng töø maø chuùng ta seõ duøng vôùi caùc caáu truùc döõ lieäu  
khaùc.  
Chuùng ta coù lôùp Queuenhö sau:  
template <class Entry>  
class Queue {  
public:  
Queue();  
bool empty() const;  
ErrorCode append(const Entry &item);  
ErrorCode serve();  
ErrorCode retrieve(Entry &item) const;  
};  
Ngoaøi caùc taùc vuï cô baûn nhö append, serve, retrieve, vaø empty ñoâi khi  
chuùng ta caàn theâm moät soá taùc vuï khaùc. Chaúng haïn nhö taùc vuï full ñeå kieåm tra  
xem haøng ñaõ ñaày hay chöa.  
Coù ba taùc vuï raát tieän lôïi ñoái vôùi haøng: clear ñeå doïn deïp caùc phaàn töû trong  
moät haøng coù saün vaø laøm cho haøng roãng, size cho bieát soá phaàn töû hieän coù trong  
haøng, cuoái cuøng laø serve_and_retrieve gom hai taùc vuï serve vaø retrieve  
laøm moät vì ngöôøi söû duïng thöôøng goïi hai taùc vuï naøy moät luùc.  
Chuùng ta coù theå boå sung caùc taùc vuï treân vaøo lôùp haøng ñaõ coù ôû treân. Tuy nhieân,  
chuùng ta coù theå taïo lôùp môùi coù theå söû duïng laïi caùc phöông thöùc vaø caùch hieän thöïc  
cuûa caùc lôùp ñaõ coù. Trong tröôøng hôïp naøy chuùng ta xaây döïng lôùp Extended_Queue  
ñeå boå sung caùc phöông thöùc theâm vaøo caùc phöông thöùc cô baûn cuûa lôùp Queue. Lôùp  
Extended_Queueñöôïc goïi laø lôùp daãn xuaát töø lôùp Queue.  
Khaùi nieäm daãn xuaát cung caáp moät caùch ñònh nghóa caùc lôùp môùi ñôn giaûn baèng  
caùch boå sung theâm caùc phöông thöùc vaøo moät lôùp coù saün. Khaû naêng cuûa lôùp daãn  
xuaát söû duïng laïi caùc thaønh phaàn cuûa lôùp cô sôû ñöôïc goïi laø söï thöøa keá. Söï thöøa keá  
(inheritance) laø moät trong caùc ñaëc tính cô baûn cuûa laäp trình höôùng ñoái töôïng.  
Chuùng ta minh hoïa moái quan heä giöõa lôùp Queue vaø lôùp daãn xuaát  
Extended_Queue bôûi sô ñoà thöøa keá (hình 3.2a). Muõi teân chæ töø lôùp daãn xuaát ñeán  
lôùp cô sôû maø noù thöøa keá. Hình 3.2b minh hoïa söï thöøa keá caùc phöông thöùc vaø caùc  
phöông thöùc boå sung.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
39  
Chöông 3 – Haøng ñôïi  
Hình 3.2- Söï thöøa keá vaø lôùp daãn xuaát  
Chuùng ta coù lôùp Extended_Queue:  
template <class Entry>  
class Extended_Queue: public Queue {  
public:  
bool full() const;  
int size() const;  
void clear();  
ErrorCode serve_and_retrieve(Entry &item);  
};  
Töø khoùa public trong khai baùo thöøa keá coù nghóa laø khaû naêng ngöôøi söû duïng  
nhìn thaáy ñoái vôùi caùc thaønh phaàn maø lôùp daãn xuaát coù ñöôïc qua söï thöøa keá seõ  
gioáng heät nhö khaû naêng ngöôøi söû duïng nhìn thaáy chuùng ôû lôùp cô sôû.  
Ñaëc taû cuûa caùc phöông thöùc boå sung:  
template <class Entry>  
bool Extended_Queue<Entry>::full() const;  
post:traû veà trueneáu haøng ñaày, ngöôïc laïi, traû veà false. Haøng khoâng ñoåi.  
template <class Entry>  
void Extended_Queue<Entry>::clear();  
post:moïi phaàn töû trong haøng ñöôïc loaïi khoûi haøng, haøng trôû neân roãng.  
template <class Entry>  
int Extended_Queue<Entry>::size() const;  
post:traû veà soá phaàn töû hieän coù cuûa haøng. Haøng khoâng ñoåi.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
40  
Chöông 3 – Haøng ñôïi  
template <class Entry>  
ErrorCode Extended_Queue<Entry>::serve_and_retrieve(const Entry &item);  
post:neáu haøng khoâng roãng, phaàn töû taïi frontñöôïc cheùp vaøo itemñoàng thôøi ñöôïc loaïi khoûi  
haøng, ErrorCodetraû veà laø success; ngöôïc laïi, ErrorCodetraû veà laø underflow, haøng  
khoâng ñoåi.  
Moái quan heä giöõa lôùp Extended_Queue vaø lôùp Queue thöôøng ñöôïc goïi laø moái  
quan heä is-a vì moãi ñoái töôïng thuoäc lôùp Extended_Queue cuõng laø moät ñoái töôïng  
thuoäc lôùp Queue maø coù theâm moät soá ñaëc tính khaùc, ñoù laø caùc phöông thöùc  
serve_and_retrieve, full, size vaø clear.  
3.3. Caùc phöông aùn hieän thöïc haøng  
3.3.1.Caùc phöông aùn hieän thöïc haøng lieân tuïc  
3.3.1.1. Moâ hình vaät lyù  
Töông töï nhö chuùng ta ñaõ laøm vôùi ngaên xeáp, chuùng ta coù theå taïo moät haøng  
trong boä nhôù maùy tính baèng moät daõy (kieåu döõ lieäu array) ñeå chöùa caùc phaàn töû  
cuûa haøng. Tuy nhieân, ôû ñaây chuùng ta caàn phaûi naém giöõ ñöôïc caû front vaø rear.  
Moät caùch ñôn giaûn laø chuùng ta giöõ front luoân laø vò trí ñaàu cuûa daõy. Luùc ñoù, ñeå  
theâm môùi moät phaàn töû vaøo haøng, chuùng ta taêng bieán ñeám bieåu dieãn rear y heät  
nhö chuùng ta theâm phaàn töû vaøo ngaên xeáp. Ñeå laáy moät phaàn töû ra khoûi haøng,  
chuùng ta phaûi traû moät giaù ñaét cho vieäc di chuyeån taát caû caùc phaàn töû hieän coù trong  
haøng tôùi moät böôùc ñeå laáp ñaày choã troáng taïi front. Maëc duø caùch hieän thöïc naøy raát  
gioáng vôùi hình aûnh haøng ngöôøi saép haøng ñôïi ñeå ñöôïc phuïc vuï, nhöng noù laø moät  
löïa choïn raát dôû trong maùy tính.  
3.3.1.2. Hieän thöïc tuyeán tính  
Ñeå vieäc xöû lyù haøng coù hieäu quaû, chuùng ta duøng hai chæ soá ñeå naém giöõ front vaø  
rear maø khoâng di chuyeån caùc phaàn töû. Muoán theâm moät phaàn töû vaøo haøng, ñôn  
giaûn chuùng ta chæ caàn taêng rear leân moät vaø theâm phaàn töû vaøo vò trí naøy. Khi laáy  
moät phaàn töû ra khoûi haøng chuùng ta laáy phaàn töû taïi vò trí front vaø taêng front  
leân moät. Tuy nhieân phöông phaùp naøy coù moät nhöôïc ñieåm lôùn, ñoù laø front vaø  
rear luoân luoân taêng chöù khoâng giaûm. Ngay caû khi trong haøng khoâng bao giôø coù  
quaù hai phaàn töû, haøng vaãn ñoøi hoûi moät vuøng nhôù khoâng coù giôùi haïn neáu nhö caùc  
taùc vuï ñöôïc goïi lieân tuïc nhö sau:  
append, append, serve, append, serve, append, serve, append,  
serve, append, ...  
Vaán ñeà ôû ñaây laø khi caùc phaàn töû trong haøng dòch chuyeån tôùi trong daõy thì caùc  
vò trí ñaàu cuûa daõy seõ khoâng bao giôø ñöôïc söû duïng ñeán. Chuùng ta coù theå hình dung  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
41  
Chöông 3 – Haøng ñôïi  
haøng luùc ñoù troâng nhö moät con raén luoân tröôøn mình tôùi. Con raén coù luùc daøi ra, coù  
luùc ngaén laïi, nhöng neáu cöù tröôøn tôùi maõi theo moät höôùng thì cuõng phaûi ñeán luùc noù  
gaëp ñieåm döøng cuûa boä nhôù.  
Tuy nhieân, cuõng caàn chuù yù raèng trong caùc öùng duïng maø coù luùc haøng trôû neân  
roãng (khi moät loaït caùc yeâu caàu ñang ñôïi ñaõ ñöôïc giaûi quyeát heát taïi moät thôøi ñieåm  
naøo ñoù), thì taïi thôøi ñieåm naøy haøng coù theå ñöôïc saép xeáp laïi, front vaø rear ñöôïc  
gaùn trôû laïi veà ñaàu daõy. Tröôøng hôïp naøy cho thaáy vieäc söû duïng moät sô ñoà ñôn giaûn  
goàm hai chæ soá vaø moät boä nhôù tuyeán tính nhö vöøa neâu laø moät caùch hieän thöïc coù  
hieäu quaû cao.  
3.3.1.3. Daõy voøng  
Veà yù nieäm, chuùng ta coù theå khaéc phuïc tính thieáu hieäu quaû trong vieäc söû duïng  
boä nhôù baèng caùch hình dung daõy coù daïng voøng thay vì tuyeán tính. Khi phaàn töû  
ñöôïc theâm vaøo hay laáy ra khoûi haøng, ñieåm ñaàu cuûa haøng seõ ñuoåi theo ñieåm cuoái  
cuûa haøng voøng theo daõy, vaø nhö vaäy con raén vaãn coù theå tröôøn tôùi voâ haïn nhöng  
vaãn bò nhoát trong moät voøng coù giôùi haïn. Taïi caùc thôøi ñieåm khaùc nhau, haøng seõ  
chieám nhöõng phaàn khaùc nhau trong daõy voøng, nhöng chuùng ta seõ khoâng bao giôø  
phaûi lo veà söï vöôït giôùi haïn boä nhôù tröø khi daõy thaät söï khoâng coøn phaàn töû troáng,  
tröôøng hôïp naøy ñöôïc xem nhö haøng ñaày, ErrorCodeseõ nhaän trò overflow.  
Hieän thöïc cuûa daõy voøng  
Vaán ñeà tieáp theo cuûa chuùng ta laø duøng moät daõy tuyeán tính ñeå moâ phoûng moät  
daõy voøng. Caùc vò trí trong voøng troøn ñöôïc ñaùnh soá töø 0 ñeán max-1, trong ñoù max  
laø toång soá phaàn töû trong daõy voøng. Ñeå hieän thöïc daõy voøng, chuùng ta cuõng söû duïng  
caùc phaàn töû ñöôïc ñaùnh soá töông töï daõy tuyeán tính. Söï thay ñoåi caùc chæ soá chæ ñôn  
giaûn laø pheùp laáy phaàn dö trong soá hoïc: khi moät chæ soá taêng vöôït qua giôùi haïn max-  
1, noù ñöôïc baét ñaàu trôû laïi vôùi trò 0. Ñieàu naøy töông töï vieäc coäng theâm giôø trong  
ñoàng hoà maët troøn, caùc giôø ñöôïc ñaùnh soá töø 1 ñeán 12, neáu chuùng ta coäng theâm 4 giôø  
vaøo 10 giôø chuùng ta seõ coù 2 giôø.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
42  
Chöông 3 – Haøng ñôïi  
Hình 3.3- Haøng trong daõy voøng  
Daõy voøng trong C++  
Trong C++, chuùng ta coù theå taêng chæ soá i trong moät daõy voøng nhö sau:  
i = ((i+1) == max) ? 0: (i+1);  
hoaëc  
hoaëc  
if ((i+1) == max) i = 0; else i = i+1;  
i = (i+1) % max;  
Caùc ñieàu kieän bieân  
Tröôùc khi vieát nhöõng giaûi thuaät theâm hoaëc loaïi phaàn töû ra khoûi haøng, chuùng ta  
haõy xem xeùt ñeán caùc ñieàu kieän bieân (boundary conditions), ñoù laø caùc daáu hieäu cho  
bieát haøng coøn roãng hay ñaõ ñaày.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
43  
Chöông 3 – Haøng ñôïi  
Neáu trong haøng chæ coù moät phaàn töû thì caû front vaø rear ñeàu chæ ñeán phaàn töû  
naøy (hình 3.4 a). Khi phaàn töû naøy ñöôïc loaïi khoûi haøng, front seõ taêng leân 1. Do  
ñoù haøng laø roãng khi rear chæ vò trí ngay tröôùc front (hình 3.4 b).  
Do reardi chuyeån veà phía tröôùc moãi khi theâm phaàn töû môùi, neân khi haøng saép  
ñaày vaø baèng caùch di chuyeån voøng thì rear cuõng seõ gaàn gaëp front trôû laïi (hình  
3.3 c). Luùc naøy khi phaàn töû cuoái cuøng ñöôïc theâm vaøo laøm cho haøng ñaày thì rear  
cuõng chæ vò trí ngay tröôùc front(hình 3.4 d).  
Chuùng ta gaëp moät khoù khaên môùi: vò trí töông ñoái cuûa front vaø rear gioáng  
heät nhau trong caû hai tröôøng hôïp haøng ñaày vaø haøng roãng.  
(a)  
(b)  
(c)  
(d)  
Hình 3.4- Hình aûnh minh hoïa haøng roãng vaø haøng ñaày  
Caùc caùch giaûi quyeát coù theå  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
44  
Chöông 3 – Haøng ñôïi  
Coù ít nhaát 3 caùch giaûi quyeát cho vaán ñeà neâu treân. Caùch thöù nhaát laø daønh  
laïi moät vò trí troáng khi haøng ñaày, rearseõ caùch frontmoät vò trí giöõa. Caùch  
thöù hai laø söû duïng theâm moät bieán, chaúng haïn moät bieán côø kieåu bool seõ coù  
trò true khi rear nhích ñeán saùt front trong tröôøng hôïp haøng ñaày (chuùng  
ta coù theå tuøy yù choïn tröôøng hôïp haøng ñaày hay roãng), hay moät bieán ñeám ñeå  
ñeám soá phaàn töû hieän coù trong haøng. Caùch thöù ba laø cho moät hoaëc caû hai chæ  
soá front vaø rearmang moät trò ñaëc bieät naøo ñoù ñeå chæ ra haøng roãng, ví duï  
nhö rear seõ laø -1 khi haøng roãng.  
3.3.1.4. Toång keát caùc caùch hieän thöïc cho haøng lieân tuïc  
Ñeå toång keát nhöõng ñieàu ñaõ baøn veà haøng, chuùng ta lieät keâ döôùi ñaây taát caû caùc  
phöông phaùp maø chuùng ta ñaõ thaûo luaän veà caùc caùch hieän thöïc haøng.  
• Moâ hình vaät lyù: moät daõy tuyeán tính coù front luoân chæ vò trí ñaàu tieân trong  
haøng vaø moïi phaàn töû cuûa haøng phaûi di chuyeån tôùi moät böôùc khi phaàn töû taïi  
frontñöôïc laáy ñi. Ñaây laø phöông phaùp raát dôû trong maùy tính noùi chung.  
• Moät daõy tuyeán tính coù hai chæ soá front vaø rear luoân luoân taêng. Ñaây laø  
phöông phaùp toát neáu nhö haøng coù theå ñöôïc laøm roãng.  
• Moät daõy voøng coù hai chæ soá front,rearvaø moät vò trí ñeå troáng.  
• Moät daõy voøng coù hai chæ soá front,rear vaø moät côø cho bieát haøng ñaày (hoaëc  
roãng).  
• Moät daõy voøng coù hai chæ soá front,rear vaø moät bieán ñeám soá phaàn töû hieän coù  
trong haøng.  
• Moät daõy voøng coù hai chæ soá front,rear maø hai chæ soá naøy seõ mang trò ñaëc  
bieät trong tröôøng hôïp haøng roãng.  
3.3.2.Phöông aùn hieän thöïc haøng lieân keát  
Baèng caùch söû duïng boä nhôù lieân tuïc, vieäc hieäc thöïc haøng khoù hôn vieäc hieän thöïc  
ngaên xeáp raát nhieàu do chuùng ta duøng vuøng nhôù tuyeán tính ñeå giaû laëp toå chöùc voøng  
vaø gaëp khoù khaên trong vieäc phaân bieät moät haøng ñaày vôùi moät haøng roãng. Tuy  
nhieân, hieän thöïc haøng lieân keát laïi thöïc söï deã daøng nhö hieän thöïc ngaên xeáp lieân  
keát. Chuùng ta chæ caàn naém giöõ hai con troû, front vaø rear ñeå tham chieáu ñeán  
phaàn töû ñaàu vaø phaàn töû cuoái cuûa haøng. Caùc taùc vuï theâm hay loaïi phaàn töû treân  
haøng ñöôïc minh hoïa trong hình 3.5.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
45  
Chöông 3 – Haøng ñôïi  
Hình 3.5 Caùc taùc vuï theâm vaø loaïi phaàn töû treân haøng lieân keát  
3.4. Hieän thöïc haøng  
3.4.1.Hieän thöïc haøng lieân tuïc  
Hieän thöïc voøng cho haøng lieân tuïc trong C++  
Phaàn naøy trình baøy caùc phöông thöùc cuûa caùch hieän thöïc haøng baèng daõy voøng  
coù bieán ñeám caùc phaàn töû. Chuùng ta coù ñònh nghóa lôùp Queue nhö sau:  
const int maxQueue = 10; // Giaù trò nhoû chæ ñeå kieåm tra CTDL Queue.  
template <class Entry>  
class Queue {  
public:  
Queue();  
bool empty() const;  
ErrorCode serve();  
ErrorCode append(const Entry &item);  
ErrorCode retrieve(Entry &item) const;  
protected:  
int count;  
int front, rear;  
Entry entry[maxQueue];  
};  
Caùc döõ lieäu thaønh phaàn trong lôùp Queue ñöôïc khai baùo protected. Ñoái vôùi ngöôøi söû duïng seõ  
khoâng coù gì thay ñoåi, nghóa laø chuùng vaãn khoâng ñöôïc ngöôøi söû duïng nhìn thaáy vaø vaãn ñaûm baûo söï  
che daáu thoâng tin. Muïc ñích ôû ñaây laø khi chuùng ta xaây döïng lôùp Extended_Queue daãn xuaát töø lôùp  
Queue thì lôùp daãn xuaát seõ söû duïng ñöôïc caùc döõ lieäu thaønh phaàn naøy. Khi caùc döõ lieäu thaønh phaàn  
cuûa lôùp cô sôû ñöôïc khai baùo laø privatethì lôùp daãn xuaát cuõng seõ khoâng nhìn thaáy chuùng.  
template <class Entry>  
Queue<Entry>::Queue()  
/*  
post:ñoái töôïng haøng ñaõ toàn taïi vaø ñöôïc khôûi taïo laø haøng roãng.  
*/  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
46  
Chöông 3 – Haøng ñôïi  
{
count = 0;  
rear = maxQueue - 1;  
front = 0;  
}
template <class Entry>  
bool Queue<Entry>::empty() const  
/*  
post: haøm traû veà trueneáu haøng roãng; ngöôïc laïi, haøm traû veà false.  
*/  
{
return count == 0;  
}
template <class Entry>  
ErrorCode Queue<Entry>::append(const Entry &item)  
/*  
post:neáu haøng coøn choã, itemñöôïc theâm vaøo taïi rear, ErrorCodetraû veà laø success; ngöôïc laïi,  
ErrorCode traû veà laø overflow, haøng khoâng ñoåi.  
*/  
{
if (count >= maxQueue) return overflow;  
count++;  
rear = ((rear + 1) == maxQueue) ? 0 : (rear + 1);  
entry[rear] = item;  
return success;  
}
template <class Entry>  
ErrorCode Queue<Entry>::serve()  
/*  
post:neáu haøng khoâng roãng, phaàn töû taïi frontñöôïc laáy ñi, ErrorCodetraû veà laø success;ngöôïc  
laïi, ErrorCode traû veà laø underflow, haøng khoâng ñoåi.  
*/  
{
if (count <= 0) return underflow;  
count--;  
front = ((front + 1) == maxQueue) ? 0 : (front + 1);  
return success;  
}
template <class Entry>  
ErrorCode Queue<Entry>::retrieve(Entry &item) const  
/*  
post: neáu haøng khoâng roãng, phaàn töû taïi front ñöôïc cheùp vaøo item, ErrorCodetraû veà laø  
success; ngöôïc laïi, ErrorCode traû veà laø underflow; caû hai tröôøng hôïp haøng ñeàu khoâng  
ñoåi.  
*/  
{
if (count <= 0) return underflow;  
item = entry[front];  
return success;  
}
Chuùng ta daønh phöông thöùc empty laïi nhö laø baøi taäp. Phöông thöùc size döôùi  
ñaây raát ñôn giaûn do lôùp Extended_Queue söû duïng ñöôïc thuoäc tính count cuûa lôùp  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
47  
Chöông 3 – Haøng ñôïi  
Queue, neáu nhö count ñöôïc khai baùo laø private thì phöông thöùc size cuûa lôùp  
Extended_Queue phaûi söû duïng haøng loaït caâu leänh goïi caùc phöông thöùc public  
cuûa Queuenhö serve, retrieve, appendmôùi thöïc hieän ñöôïc. Caùc phöông thöùc  
coøn laïi cuûa Extended_Queuecuõng töông töï, vaø chuùng ta daønh laïi phaàn baøi taäp.  
template <class Entry>  
int Extended_Queue<Entry>::size() const  
/*  
post:traû veà soá phaàn töû hieän coù cuûa haøng. Haøng khoâng ñoåi.  
*/  
{
return count;  
}
3.4.2.Hieän thöïc haøng lieân keát  
3.4.2.1. Caùc khai baùo cô baûn  
Vôùi moïi haøng, chuùng ta duøng kieåu Entry cho kieåu cuûa döõ lieäu löu trong haøng.  
Ñoái vôùi hieän thöïc lieân keát, chuùng ta khai baùo caùc node töông töï nhö ñaõ laøm cho  
ngaên xeáp lieân keát trong chöông 2. Chuùng ta coù ñaëc taû döôùi ñaây:  
template <class Entry>  
class Queue {  
public:  
// Caùc phöông thöùc chuaån cuûa haøng  
Queue();  
bool empty() const;  
ErrorCode append(const Entry &item);  
ErrorCode serve();  
ErrorCode retrieve(Entry &item) const;  
// Caùc phöông thöùc baûo ñaûm tính an toaøn cho haøng lieân keát  
~Queue();  
Queue(const Queue<Entry> &original);  
void operator =(const Queue<Entry> &original);  
protected:  
Node<Entry> *front, *rear;  
};  
Constructor thöù nhaát khôûi taïo moät haøng roãng:  
template <class Entry>  
Queue<Entry>::Queue()  
/*  
post:ñoái töôïng haøng ñaõ toàn taïi vaø ñöôïc khôûi taïo laø haøng roãng.  
*/  
{
front = rear = NULL;  
}
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
48  
Chöông 3 – Haøng ñôïi  
Phöông thöùc append theâm moät phaàn töû vaøo ñaàu rear cuûa haøng:  
template <class Entry>  
ErrorCode Queue<Entry>::append(const Entry &item)  
/*  
post:neáu haøng coøn choã, itemñöôïc theâm vaøo taïi rear, ErrorCodetraû veà laø success;ngöôïc  
laïi, ErrorCodetraû veà laø overflow, haøng khoâng ñoåi.  
*/  
{
Node *new_rear = new Node<Entry> (item);  
if (new_rear == NULL) return overflow;  
if (rear == NULL) front = rear = new_rear; // tröôøng hôïp ñaëc bieät: theâm vaøo haøng  
ñang roãng.  
else {  
rear->next = new_rear;  
rear = new_rear;  
}
return success;  
}
Tröôøng hôïp haøng roãng caàn phaân bieät vôùi caùc tröôøng hôïp bình thöôøng khaùc, do  
khi theâm moät node vaøo moät haøng roãng caàn phaûi gaùn caû front vaø rear tham  
chieáu ñeán node naøy, trong khi vieäc theâm moät node vaøo moät haøng khoâng roãng chæ  
coù rearlaø caàn ñöôïc gaùn laïi.  
Phöông thöùc loaïi moät phaàn töû ra khoûi haøng ñöôïc vieát nhö sau:  
template <class Entry>  
ErrorCode Queue::serve()  
/*  
post:neáu haøng khoâng roãng, phaàn töû taïi front ñöôïc laáy ñi, ErrorCodetraû veà laø success; ngöôïc  
laïi, ErrorCodetraû veà laø underflow, haøng khoâng ñoåi.  
*/  
{
if (front == NULL) return underflow;  
Node *old_front = front;  
front = old_front->next;  
if (front == NULL) rear= NULL;// tröôøng hôïp ñaëc bieät: loaïi phaàn töû cuoái cuøng cuûa haøng  
delete old_front;  
return success;  
}
Moät laàn nöõa tröôøng hôïp haøng roãng caàn ñöôïc xem xeùt rieâng. Khi phaàn töû ñöôïc  
loaïi khoûi haøng khoâng phaûi laø phaàn töû cuoái trong haøng, chæ coù front caàn ñöôïc gaùn  
laïi, ngöôïc laïi caû front vaø rear caàn phaûi gaùn veà NULL.  
Caùc phöông thöùc khaùc cuûa haøng lieân keát ñöôïc daønh laïi cho phaàn baøi taäp.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
49  
Chöông 3 – Haøng ñôïi  
Neáu so saùnh vôùi haøng lieân tuïc, chuùng ta seõ thaáy raèng haøng lieân keát deã hieåu  
hôn caû veà maët khaùi nieäm caû veà caùch hieän thöïc chöông trình.  
3.4.3.Haøng lieân keát môû roäng  
Hieän thöïc lieân keát cuûa lôùp Queue cung caáp moät lôùp cô sôû cho caùc lôùp khaùc.  
Ñònh nghóa döôùi ñaây daønh cho lôùp daãn xuaát Extended_Queue hoaøn toaøn töông töï  
nhö haøng lieân tuïc.  
template <class Entry>  
class Extended_queue: public Queue {  
public:  
bool full() const;  
int size() const;  
void clear();  
ErrorCode serve_and_retrieve(Entry &item);  
};  
Maëc duø lôùp Extended_Queue naøy coù hieän thöïc lieân keát, nhöng noù khoâng caàn caùc phöông thöùc  
nhö copy contructor, overloaded assignment, hoaëc destructor. Ñoái vôùi moät trong caùc phöông thöùc  
naøy, trình bieân dòch seõ goïi caùc phöông thöùc maëc ñònh cuûa lôùp Extended_Queue. Phöông thöùc maëc  
ñònh cuûa moät lôùp daãn xuaát seõ goïi phöông thöùc töông öùng cuûa lôùp cô sôû. Chaúng haïn, khi moät ñoái  
töôïng cuûa lôùp Extended_Queue chuaån bò ra khoûi taàm vöïc, destructor maëc ñònh cuûa lôùp  
Extended_Queue seõ goïi destructor cuûa lôùp Queue: moïi node caáp phaùt ñoäng cuûa Extended_Queue  
ñeàu ñöôïc giaûi phoùng. Do lôùp Extended_Queue cuûa chuùng ta khoâng chöùa theâm thuoäc tính con troû  
naøo ngoaøi caùc thuoäc tính con troû thöøa keá töø lôùp Queue, destructor maø trình bieân dòch goïi ñaõ laøm  
ñöôïc taát caû nhöõng ñieàu maø chuùng ta mong muoán.  
Caùc phöông thöùc ñöôïc khai baùo cho lôùp Extended_Queue caàn ñöôïc vieát laïi cho  
phuø hôïp vôùi caáu truùc lieân keát cuûa haøng. Chaúng haïn, phöông thöùc size caàn söû duïng  
moät con troû taïm window ñeå duyeät haøng (noùi caùch khaùc, con troû window seõ di  
chuyeån doïc theo haøng vaø laàn löôït chæ ñeán töøng node trong haøng).  
template <class Entry>  
int Extended_queue<Entry>::size() const  
/*  
post:traû veà soá phaàn töû hieän coù cuûa haøng. Haøng khoâng ñoåi.  
*/  
{
Node *window = front;  
int count = 0;  
while (window != NULL) {  
window = window->next;  
count++;  
}
return count;  
}
Caùc phöông thöùc khaùc cuûa Extended_Queuelieân keát xem nhö baøi taäp.  
Giaùo trình Caâu truùc döõ lieäu vaø Giaûi thuaät  
50  
pdf 14 trang baolam 21700 Free
Download
Bạn đang xem tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 3: Hàng đợi", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2_cac_cau_tru.pdf