›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 15: Ứng dụng của hàng đợi

Download
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
Chöông 15 – ÖÙNG DUÏNG CUÛA HAØNG ÑÔÏI  
CTDL haøng ñôïi ñöôïc söû duïng raát roäng raõi trong caùc chöông trình maùy tính.  
Ñaëc bieät laø trong coâng vieäc cuûa heä ñieàu haønh khi caàn xöû lyù caùc coâng vieäc moät caùch  
tuaàn töï. Haøng ñôïi trong chöông 3 laø moät khaùi nieäm FIFO ñôn giaûn. Trong thöïc  
teá, ngöôøi ta thöôøng raát hay söû duïng caùc haøng ñôïi öu tieân ñöôïc trình baøy trong  
chöông 11. Chöông naøy minh hoïa moät soá öùng duïng ñôn giaûn cuûa haøng ñôïi.  
15.1. Caùc dòch vuï  
Chuùng ta coù theå vieát moät chöông trình moâ phoûng vieäc cung caáp caùc dòch vuï.  
Chaúng haïn taïi quaày baùn veù caùc tuyeán bay, coù nhieàu ngöôøi ñang ñeán vaø ñang saép  
haøng chôø ñeå mua veù. Coù khaû naêng chæ coù moät nhaân vieân baùn veù, hoaëc coù nhieàu  
nhaân vieân baùn veù ñoàng thôøi. Sinh vieân haõy xem ñaây nhö laø moät gôïi yù ñeå vieát  
thaønh moät öùng duïng cho CTDL haøng ñôïi. Nhöõng ñieàu thöôøng ñöôïc quan taâm laø:  
• Thôøi gian chôø ñôïi trung bình (queue time) cuûa moät khaùch haøng töø luùc ñeán cho  
ñeán luùc ñöôïc baét ñaàu ñöôïc phuïc vuï.  
• Thôøi gian phuïc vuï trung bình (service time) maø moät dòch vuï ñöôïc thöïc hieän.  
• Thôøi gian ñaùp öùng trung bình (response time) cuûa moät khaùch haøng töø luùc ñeán  
cho ñeán luùc rôøi khoûi quaày (chính baèng toång hai thôøi gian treân).  
• Taàn suaát ñeán cuûa khaùch haøng.  
Döïa vaøo nhöõng ñieàu treân ngöôøi ta coù theå ñieàu chænh caùc keá hoaïch phuïc vuï cho  
thích hôïp hôn.  
15.2. Phaân loaïi  
Moät ví duï veà phaân loaïi laø vieäc söû duïng nhieàu haøng ñôïi cuøng moät luùc. Tuøy theo  
ñaëc ñieåm cuûa caùc yeâu caàu coâng vieäc, moãi haøng ñôïi chæ nhaän caùc coâng vieäc cuøng ñaëc  
ñieåm maø thoâi. Nhö vaäy ñaàu ra cuûa moãi haøng ñôïi seõ laø nhöõng coâng vieäc coù chung  
ñaëc ñieåm. Vieäc söû duïng haøng ñôïi ôû ñaây giuùp ta phaân loaïi ñöôïc coâng vieäc, ñoàng thôøi  
trong caùc coâng vieäc cuøng loaïi, chuùng vaãn giöõ nguyeân thöù töï ban ñaàu giöõa chuùng.  
Hình aûnh deã thaáy nhaát chính laø ví duï treân vôùi moãi haøng ngöôøi ñôïi seõ ñöôïc mua veù  
ñi cuøng moät tuyeán bay naøo ñoù (moät oâ cöûa chæ baùn cho moät tuyeán bay nhaát ñònh).  
Moät ví duï khaùc veà söï phaân loaïi caùc böu kieän taïi moät trung taâm chuyeån phaùt: caùc  
böu kieän seõ ñöôïc phaân loaïi vaøo caùc haøng ñôïi döïa vaøo theå tích, troïng löôïng, nôi  
ñeán,…., maø thöù töï giöõa chuùng trong moät haøng ñôïi laø khoâng thay ñoåi.  
15.3. Phöông phaùp saép thöù töï Radix Sort  
ÖÙng duïng haøng lieân keát trong phöông phaùp saép thöù töï Radix Sort ñöôïc trình  
baøy trong chöông 8.  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
377  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
15.4. Tính trò cho bieåu thöùc prefix  
Ñeå tính trò cho bieåu thöùc daïng prefix ngöôøi ta duøng haøng ñôïi. Vieäc tính ñöôïc  
thöïc hieän laëp laïi nhieàu laàn, moãi laàn luonâ xöû lyù cho bieåu thöùc töø traùi sang phaûi nhö  
döôùi ñaây:  
-
+
+
+
*
9
+
2
8
*
+
4
8
6
3
-
*
9
10 *  
12 6  
3
-
90 72 3  
-
162 3  
159  
Moãi laàn duyeät bieåu thöùc, chuùng ta thay theá moïi toaùn töû maø coù ñuû hai toaùn  
haïng ñöùng ngay sau baúng keát quaû cuûa pheùp tính cho toaùn töû ñoù. Do thöù töï duyeät  
qua bieåu thöùc luoân laø töø traùi sang phaûi, neân chuùng ta coù theå löu bieåu thöùc vaøo  
haøng ñôïi vaø söû duïng caùc phöông thöùc cuûa haøng ñôïi ñeå laáy töøng phaàn töû cuõng nhö  
ñöa töøng phaàn töû vaøo haøng. Hieän thöïc chöông trình ñöôïc xem nhö baøi taäp cho  
sinh vieân.  
15.5. ÖÙng duïng pheùp tính treân ña thöùc  
Ñaây laø moät öùng duïng coù söû duïng CTDL ngaên xeáp vaø haøng ñôïi. Trong öùng duïng  
naøy chuùng ta coù dòp nhìn thaáy coâng duïng cuûa caùc CTDL ñaõ ñöôïc thieát keá hoaøn  
chænh. Coù nhieàu baøi toaùn coù theå söû duïng caùc CTDL hoaøn chænh ñeå phaùt trieån theâm  
caùc lôùp thöøa keá raát tieän lôïi. Ngoaøi ra, phöông phaùp phaùt trieån daàn thaønh moät  
chöông trình hoaøn chænh ñöôïc trình baøy döôùi ñaây cuõng laø moät tham khaûo raát toát  
cho sinh vieân khi laøm quen vôùi caùc kyõ naêng thieát keá vaø laäp trình.  
15.5.1.Muïc ñích cuûa öùng duïng  
Trong phaàn 14.3 chuùng ta ñaõ vieát chöông trình moâ phoûng moät maùy tính ñôn  
giaûn thöïc hieän caùc pheùp coäng, tröø, nhaân, chia vaø moät soá pheùp tính khaùc töông töï.  
Phaàn naøy seõ moâ phoûng moät maùy tính töông töï thöïc hieän caùch tính Balan ngöôïc  
cho caùc pheùp tính treân ña thöùc. YÙ töôûng chính cuûa giaûi thuaät laø söû duïng ngaên xeáp  
ñeå löu caùc toaùn haïng. Coøn haøng ñôïi seõ ñöôïc söû duïng ñeå moâ phoûng ña thöùc.  
15.5.2.Chöông trình  
Chuùng ta seõ hieän thöïc moät lôùp ña thöùc (Polynomial) ñeå söû duïng trong chöông  
trình. Vieäc hieän thöïc chöông trình seõ trôû neân raát ñôn giaûn. Chöông trình chính  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
378  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
caàn khai baùo moät ngaên xeáp ñeå chöùa caùc ña thöùc, nhaän caùc yeâu caàu tính vaø thöïc  
hieän.  
int main()  
/*  
post: Chöông trình thöïc hieän caùc pheùp tính toaùn soá hoïc cho caùc ña thöùc do ngöôøi söû duïng nhaäp  
vaøo.  
uses: Caùc lôùp Stack,Polynomial vaø caùc haøm introduction, instructions,  
do_command, get_command.  
*/  
{
Stack<Polynomial> stored_polynomials;  
introduction();  
instructions();  
while (do_command(get_command(), stored_polynomials));  
}
Chöông trình naøy haàu nhö töông töï vôùi chöông trình chính ôû phaàn 14.3, haøm  
phuï trôï get_commandtöông töï haøm ñaõ coù.  
15.5.2.1. Caùc phöông thöùc cuûa lôùp Polynomial  
Töông töï phaàn 14.3, thay vì nhaäp moät con soá, daáu ? chôø ngöôøi söû duïng nhaäp  
vaøo moät ña thöùc.  
Phaàn lôùn caùc vieäc caàn laøm trong chöông trình naøy laø vieäc hieän thöïc caùc  
phöông thöùc cuûa Polynomial. Chaúng haïn chuùng ta caàn phöông thöùc equals_sum  
ñeå coäng hai ña thöùc. Cho p, q, r laø caùc ñoái töôïng ña thöùc, p.equals_sum(q,r) seõ  
thay p bôûi ña thöùc toång cuûa hai ña thöùc q vaø r. Töông töï chuùng ta coù caùc phöông  
thöùc equals_difference, equals_product, vaø equals_quotient ñeå thöïc  
hieän caùc pheùp tính soá hoïc khaùc treân ña thöùc.  
Ngoaøi ra, lôùp Polynomial coøn hai phöông thöùc khoâng thoâng soá laø print vaø  
readñeå xuaát vaø ñoïc ña thöùc.  
15.5.2.2. Thöïc hieän caùc yeâu caàu  
Haøm do_command nhaän ñoái töôïng ngaên xeáp laø tham bieán do ngaên xeáp caàn  
ñöôïc bieán ñoåi trong haøm.  
bool do_command(char command, Stack<Polynomial> &stored_polynomials)  
/*  
pre: command chöùa kyù töï hôïp leä bieåu dieãn yeâu caàu cuûa ngöôøi söû duïng.  
post: Yeâu caàu cuûa ngöôøi söû duïng ñöôïc thöïc hieän ñoái vôùi caùc ña thöùc trong ngaên xeáp, haøm traû veà  
truengoaïi tröø tröôøng hôïp command='q' thì haøm traû veà false.  
uses: Caùc lôùp Stack vaø Polynomial.  
*/  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
379  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
{
Polynomial p, q, r;  
switch (command) {  
case '?':  
p.read();  
if (stored_polynomials.push(p) == overflow)  
cout << "Warning: Stack full, lost polynomial" << endl;  
break;  
case '=':  
if (stored_polynomials.empty())  
cout << "Stack empty" << endl;  
else {  
stored_polynomials.top(p);  
p.print();  
}
break;  
case '+':  
if (stored_polynomials.empty())  
cout << "Stack empty" << endl;  
else {  
stored_polynomials.top(p);  
stored_polynomials.pop();  
if (stored_polynomials.empty()) {  
cout << "Stack has just one polynomial" << endl;  
stored_polynomials.push(p);  
}
else {  
stored_polynomials.top(q);  
stored_polynomials.pop();  
r.equals_sum(q, p);  
if (stored_polynomials.push(r) == overflow)  
cout << "Warning: Stack full, lost polynomial" << endl;  
}
}
break;  
//  
}
Caàn boå sung caùc doøng leänh ñeå thöïc hieän caùc pheùp tính coøn laïi.  
case 'q':  
cout << "Calculation finished." << endl;  
return false;  
return true;  
}
15.5.2.3. Caùc maåu chöông trình vaø coâng vieäc kieåm tra  
Caùch laøm sau ñaây minh hoïa yù töôûng söû duïng caùc maåu taïm trong chöông trình  
nhö ñaõ trình baøy trong phaàn 1.5.3 (caùc kyõ naêng laäp trình).  
Hieän taïi chuùng ta chæ phaùt trieån chöông trình vöøa ñuû ñeå coù theå dòch, chænh söûa  
loãi, vaø kieåm tra tính ñuùng ñaén cuûa nhöõng phaàn ñaõ vieát.  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
380  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
Ñeå dòch thöû chöông trình, chuùng ta caàn taïo caùc maåu cho moïi phaàn töû coøn thieáu  
cuûa chöông trình. Phaàn töû coøn thieáu ôû ñaây laø lôùp Polynomial. Do chuùng ta coøn  
chöa quyeát ñònh seõ hieän thöïc caùc ñoái töôïng ña thöùc nhö theá naøo, chuùng ta haõy  
chaïy chöông trình nhö moät maùy tính Balan ngöôïc daønh cho caùc soá thöïc. Thay vaøo  
choã caàn khai baùo döõ lieäu cho lôùp Polynomial, chuùng ta khai baùo soá thöïc.  
class Polynomial {  
public:  
void read();  
void print();  
void equals_sum(Polynomial p, Polynomial q);  
void equals_difference(Polynomial p, Polynomial q);  
void equals_product(Polynomial p, Polynomial q);  
ErrorCode equals_quotient(Polynomial p, Polynomial q);  
private:  
double value; // maåu taïm duøng ñeå thöû chöông trình.  
};  
Phöông thöùc equals_quotient caàn kieåm tra pheùp chia 0 neân caàn traû veà  
ErrorCode. Haøm sau ñaây laø moät ñieån hình cho maåu phöông thöùc duøng ñeå thöû  
chöông trình.  
void Polynomial::equals_sum(Polynomial p, Polynomial q)  
{
value = p.value + q.value; //Chæ vieát taïm, sau seõ vieát laïi ñuùng cho ña thöùc.  
}
Vieäc taïo ra moät boä khung chöông trình taïi thôøi ñieåm naøy cho pheùp chuùng ta  
kieåm tra xem ngaên xeáp vaø caùc goùi tieän ích (chöùa caùc haøm phuï trôï) ñaõ ñöôïc keát noái  
moät caùch ñuùng ñaén trong chöông trình hay chöa. Chöông trình, cuøng caùc maåu thöû  
cuûa noù, phaûi thöïc thi moät caùch chính xaùc caû vôùi hieän thöïc ngaên xeáp lieân tuïc laãn  
ngaên xeáp lieân keát.  
15.5.3.Caáu truùc döõ lieäu cuûa ña thöùc  
Chuùng ta haõy quay laïi nhieäm vuï chính cuûa chuùng ta laø choïn löïa caùch bieåu dieãn  
ña thöùc vaø vieát caùc phöông thöùc xöû lyù cho chuùng. Caùc ña thöùc coù daïng sau  
3x5 – 2x3 + x2 + 4  
Thoâng tin quan troïng trong moät ña thöùc laø caùc heä soá vaø caùc soá muõ cuûa x, coøn  
baûn thaân x chæ laø moät bieán. Chuùng ta xem ña thöùc ñöôïc taïo thaønh töø caùc soá haïng  
(term), moãi soá haïng chöùa moät heä soá vaø moät soá muõ. Trong maùy tính coù theå xem ña  
thöùc laø moät danh saùch caùc caëp goàm heä soá vaø soá muõ. Chuùng ta duøng struct ñeå  
khai baùo soá haïng  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
381  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
struct Term {  
int degree;  
double coefficient;  
Term (int exponent = 0, double scalar = 0);  
};  
Term::Term(int exponent, double scalar)  
/*  
post: Term ñöôïc khôûi taïo bôûi heä soá vaø soá muõ nhaän ñöôïc, neáu khoâng coù thoâng soá truyeàn vaøo thì  
hai soá naøy ñöôïc gaùn maëc ñònh laø 0.  
*/  
{
degree = exponent;  
coefficient = scalar;  
}
Chuùng ta chöa löu taâm veà thöù töï cuûa caùc soá haïng trong ña thöùc, tuy nhieân neáu  
cho pheùp caùc soá haïng coù moät thöù töï tuøy yù thì chuùng ta seõ gaëp khoù khaên trong vieäc  
nhaän ra caùc ña thöùc baèng nhau cuõng nhö trong vieäc tính toaùn treân caùc ña thöùc.  
Chuùng ta choïn phöông aùn buoäc caùc soá haïng trong moät ña thöùc phaûi coù thöù töï giaûm  
daàn theo soá muõ, ñoàng thôøi cuõng khoâng cho pheùp hai soá haïng coù cuøng soá muõ hoaëc  
soá haïng coù heä soá baèng khoâng. Vôùi söï raøng buoäc naøy, khi thöïc hieän moät pheùp tính  
soá hoïc naøo ñoù treân hai ña thöùc, chuùng ta thöôøng laàn löôït xöû lyù cho töøng caëp soá  
haïng cuûa hai ña thöùc töø traùi sang phaûi. Caùc soá haïng cuûa ña thöùc keát quaû cuõng  
ñöôïc ghi vaøo ña thöùc theo thöù töï naøy. Moät ña thöùc ñöôïc bieåu dieãn baèng moät danh  
saùch caùc Term. Nhö vaäy, caùc pheùp tính soá hoïc coù theå xem ña thöùc nhö laø moät  
Queue, hay chính xaùc hôn, nhö laø Extended_queue, vì chuùng ta thöôøng xuyeân  
caàn ñeán caùc phöông thöùc clearvaø serve_and_retrieve.  
Chuùng ta thöû hoûi neân duøng haøng lieân tuïc hay haøng lieân keát. Neáu bieát tröôùc baäc  
cuûa ña thöùc vaø caùc ña thöùc ít coù heä soá baèng khoâng thì chuùng ta neân duøng haøng  
lieân tuïc. Ngöôïc laïi, neáu khoâng bieát tröôùc baäc, hoaëc ña thöùc coù raát ít heä soá khaùc  
khoâng thì haøng lieân keát thích hôïp hôn. Hình 15.1 minh hoïa ña thöùc hieän thöïc  
baèng haøng lieân keát.  
Moãi phaàn töû trong haøng chöùa moät soá haïng cuûa ña thöùc vaø chæ coù nhöõng soá haïng coù  
heä soá khaùc khoâng môùi ñöôïc löu vaøo haøng. Ña thöùc baèng 0 bieåu dieãn bôûi haøng roãng.  
Vôùi caáu truùc döõ lieäu ñöôïc choïn cho ña thöùc nhö treân chuùng ta xaây döïng lôùp  
Polynomial laø lôùp daãn xuaát töø lôùp Extended_Queue, chuùng ta chæ vieäc boå sung  
caùc phöông thöùc rieâng cuûa ña thöùc.  
Ñeå hieän thöïc cuï theå cho lôùp daãn xuaát Polynomial, chuùng ta caàn ñaët caâu hoûi:  
moät ña thöùc coù haún laø moät Extended_Queuehay khoâng?  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
382  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
Hình 15.1- Bieåu dieãn ña thöùc bôûi moät haøng lieân keát caùc soá haïng  
Moät Extended_Queue cung caáp caùc phöông thöùc nhö serve chaúng haïn,  
phöông thöùc naøy khoâng nhaát thieát vaø cuõng khoâng neân laø phöông thöùc cuûa  
Polynomial. Seõ laø moät ñieàu khoâng hay khi chuùng ta cho pheùp ngöôøi söû duïng goïi  
phöông thöùc serve ñeå loaïi ñi moät phaàn töû cuûa Polynomial. Ña thöùc neân laø moät  
ñoái töôïng ñoùng kín. Vì vaäy moät Polynomialkhoâng haún laø moät Extended_Queue.  
Maëc duø raát coù lôïi khi söû duïng laïi caùc thuoäc tính vaø caùc phöông thöùc töø  
Extended_Queuecho Polynomial, nhöng chuùng ta khoâng theå söû duïng pheùp thöøa  
keá ñôn giaûn, vì quan heä cuûa hai lôùp naøy khoâng phaûi laø quan heä “is-a”.  
Quan heä “is-a” laø daïng thöøa keá public trong C++. Neáu khai baùo thöøa keá public thì ngöôøi söû  
duïng coù theå xem moät ña thöùc cuõng laø moät haøng ñôïi. C++ cung caáp moät daïng thöøa keá thöù hai, goïi laø  
thöøa keá rieâng (private inheritance), ñaây chính laø ñieàu chuùng ta mong muoán. Söï thöøa keá rieâng cho  
pheùp lôùp daãn xuaát ñöôïc hieän thöïc baèng caùch söû duïng laïi lôùp cô sôû, nhöng ngöôøi söû duïng khoâng goïi  
ñöôïc caùc phöông thöùc cuûa lôùp cô sôû thoâng qua ñoái töôïng cuûa lôùp daãn xuaát. Quan heä naøy coøn ñöôïc  
goïi laø quan heä “is implemented of”. Chuùng ta seõ ñònh nghóa lôùp Polynomial thöøa keá rieâng töø lôùp  
Extended_Queue: caùc thuoäc tính vaø caùc phöông thöùc cuûa Extended_Queue coù theå ñöôïc söû duïng  
trong hieän thöïc cuûa lôùp Polynomial, nhöng chuùng khoâng ñöôïc nhìn thaáy bôûi ngöôøi söû duïng.  
class Polynomial: private Extended_queue<Term> { // Thöøa keá rieâng.  
public:  
void read();  
void print() const;  
void equals_sum(Polynomial p, Polynomial q);  
void equals_difference(Polynomial p, Polynomial q);  
void equals_product(Polynomial p, Polynomial q);  
Error_code equals_quotient(Polynomial p, Polynomial q);  
int degree() const;  
private:  
void mult_term(Polynomial p, Term t);  
};  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
383  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
Ñònh nghóa treân boå sung theâm caùc phöông thöùc nhö degree traû veà baäc cuûa ña  
thöùc vaø mult_termñeå nhaân moät ña thöùc vôùi moät term.  
15.5.4.Ñoïc vaø ghi caùc ña thöùc  
Vieäc in ña thöùc ñôn giaûn chæ laø duyeät qua caùc phaàn töû cuûa haøng vaø in döõ lieäu  
trong moãi phaàn töû. Phöông thöùc döôùi ñaây in ña thöùc vôùi moät soá xöû lyù cho caùc  
tröôøng hôïp ñaëc bieät nhö loaïi boû daáu + (neáu coù) ôû ñaàu ña thöùc, khoâng in heä soá hoaëc  
soá muõ neáu baèng 1 vaø khoâng in x0.  
void Polynomial::print() const  
/*  
post: Ña thöùc ñöôïc in ra cout.  
*/  
{
Node *print_node = front;  
bool first_term = true;  
while (print_node != NULL) {  
Term &print_term = print_node->entry;  
if (first_term) {  
// Khoâng in daáu ‘+’ ñaàu ña thöùc.  
first_term = false;  
if (print_term.coefficient < 0) cout << "- ";  
}
else if (print_term.coefficient < 0) cout << " - ";  
else cout << " + ";  
double r = (print_term.coefficient >= 0)  
? print_term.coefficient : -(print_term.coefficient);  
if (r != 1) cout << r;  
if (print_term.degree > 1) cout << " X^" << print_term.degree;  
if (print_term.degree == 1) cout << " X";  
if (r == 1 && print_term.degree == 0) cout << " 1";  
print_node = print_node->next;  
}
if (first_term)  
cout << "0"; // Print 0 for an empty Polynomial.  
cout << endl;  
}
Phöông thöùc ñoïc ña thöùc thöïc hieän viecä kieåm tra ñeå caùc soá haïng nhaäp vaøo thoûa  
ñieàu kieän soá muõ giaûm daàn vaø moät soá raøng buoäc trong vieäc bieåu dieãn ña thöùc nhö  
ñaõ neâu treân. Vieäc nhaäp keát thuùc khi heä soá vaø soá muõ ñeàu nhaän trò 0.  
void Polynomial::read()  
/*  
post: Ña thöùc ñöôïc ñoïc töø cin.  
*/  
{
clear();  
double coefficient;  
int last_exponent, exponent;  
bool first_term = true;  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
384  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
cout << "Enter the coefficients and exponents for the polynomial, "  
<< "one pair per line. Exponents must be in descending order."  
<< endl  
<< "Enter a coefficient of 0 or an exponent of 0 to terminate." <<  
endl;  
do {  
cout << "coefficient? " << flush;  
cin >> coefficient;  
if (coefficient != 0.0) {  
cout << "exponent? " << flush;  
cin >> exponent;  
if ((!first_term && exponent >= last_exponent) || exponent < 0) {  
exponent = 0;  
cout << "Bad exponent: Polynomial terminates without its last  
term."  
<< endl;  
}
else {  
Term new_term(exponent, coefficient);  
append(new_term);  
first_term = false;  
}
last_exponent = exponent;  
}
} while (coefficient != 0.0 && exponent != 0);  
}
15.5.5.Pheùp coäng ña thöùc  
Phaàn naøy chuùng ta chæ hieän thöïc pheùp coäng ña thöùc, caùc pheùp tính khaùc xem  
nhö baøi taäp.  
Do caùc soá haïng trong caû hai ña thöùc coù soá muõ giaûm daàn neân pheùp coäng raát ñôn  
giaûn. Chuùng ta chæ caàn duyeät qua moät laàn vaø ñoàng thôøi ñoái vôùi caû hai ña thöùc. Neáu  
gaëp hai soá haïng cuûa hai ña thöùc coù soá muõ baèng nhau, chuùng ta coäng hai heä soá vaø  
keát quaû ñöa vaøo ña thöùc toång, ngöôïc laïi, soá haïng cuûa ña thöùc naøo coù soá muõ cao  
hôn ñöôïc ñöa vaøo toång, pheùp duyeät chæ dòch chuyeån tôùi moät böôùc treân ña thöùc naøy.  
Chuùng ta chæ phaûi löu yù ñeán tröôøng hôïp toång hai heä soá cuûa hai soá haïng baèng 0 thì  
seõ khoâng coù phaàn töû môùi ñöôïc ñöa vaøo ña thöùc toång. Ngoaøi ra, vì phöông thöùc naøy  
seõ phaù huûy caùc ña thöùc toaùn haïng ñöôïc ñöa vaøo neân chuùng ñöôïc gôûi baèng tham trò.  
void Polynomial::equals_sum(Polynomial p, Polynomial q)  
/*  
post: Ñoái töôïng ña thöùc seõ coù trò baèng toång hai ña thöùc nhaän vaøo töø thoâng soá.  
*/  
{
clear();  
while (!p.empty() || !q.empty()) {  
Term p_term, q_term;  
if (p.degree() > q.degree()) {  
p.serve_and_retrieve(p_term);  
append(p_term);  
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
385  
Chöông 15 – ÖÙng duïng cuûa haøng ñôïi  
else if (q.degree() > p.degree()) {  
q.serve_and_retrieve(q_term);  
append(q_term);  
}
else {  
p.serve_and_retrieve(p_term);  
q.serve_and_retrieve(q_term);  
if (p_term.coefficient + q_term.coefficient != 0) {  
Term answer_term(p_term.degree,  
p_term.coefficient + q_term.coefficient);  
append(answer_term);  
}
}
}
}
Phöông thöùc treân baét ñaàu baèng vieäc doïn deïp moïi soá haïng trong ña thöùc seõ  
chöùa keát quaû cuûa pheùp coäng. Phöông thöùc degree ñöôïc goïi ñeå traû veà baäc cuûa ña  
thöùc, neáu ña thöùc roãng, degreeseõ traû veà -1.  
15.5.6.Hoaøn taát chöông trình  
15.5.6.1. Caùc phöông thöùc coøn thieáu  
Pheùp tröø hai ña thöùc hoaøn toaøn töông töï pheùp coäng. Ñoái vôùi pheùp nhaân, tröôùc  
heát chuùng ta phaûi vieát haøm nhaân moät ña thöùc vôùi moät soá haïng, sau ñoù keát hôïp vôùi  
phöông thöùc coäng hai ña thöùc ñeå hoaøn taát pheùp nhaân. Pheùp chia ña thöùc phöùc taïp  
hôn raát nhieàu, pheùp chia ña thöùc cho moät keát quaû laø ña thöùc thöông vaø moät laø ña  
thöùc soá dö.  
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät  
386  
pdf 10 trang yennguyen 13/04/2022 2660
Download
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 15: Ứng dụng của 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_15_ung_dung.pdf