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 2: Ngăn xếp
Chöông 2 – Ngaên xeáp
Phaàn 2 – CAÙC CAÁU TRUÙC DÖÕ LIEÄU
Chöông 2 – NGAÊN XEÁP
Chuùng ta seõ tìm hieåu moät CTDL ñôn giaûn nhaát, ñoù laø ngaên xeáp. Moät caùch nhaát
quaùn nhö phaàn giôùi thieäu moân hoïc ñaõ trình baøy, moãi CTDL ñeàu ñöôïc xaây döïng
theo ñuùng trình töï:
• Ñònh nghóa.
• Ñaëc taû.
• Phaân tích caùc phöông aùn hieän thöïc.
• Hieän thöïc.
2.1. Ñònh nghóa ngaên xeáp
Vôùi ñònh nghóa danh saùch trong chöông môû ñaàu, chuùng ta hieåu raèng trong
danh saùch, moãi phaàn töû, ngoaïi tröø phaàn töû cuoái, ñeàu coù duy nhaát moät phaàn töû
ñöùng sau noù. Ngaên xeáp laø moät tröôøng hôïp cuûa danh saùch, ñöôïc söû duïng trong caùc
öùng duïng coù lieân quan ñeán söï ñaûo ngöôïc. Trong CTDL ngaên xeáp, vieäc theâm hay
laáy döõ lieäu chæ ñöôïc thöïc hieän taïi moät ñaàu. Döõ lieäu theâm vaøo tröôùc seõ laáy ra sau,
tính chaát naøy coøn ñöôïc goïi laø vaøo tröôùc ra sau (First In Last Out - FILO).
Ñaàu theâm hay laáy döõ lieäu cuûa ngaên xeáp coøn goïi laø ñænh (top) cuûa ngaên xeáp.
Hình 2.1- Theâm phaàn töû vaøo vaø laáy phaàn töû ra khoûi ngaên xeáp.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
17
Chöông 2 – Ngaên xeáp
Vaäy chuùng ta coù ñònh nghóa cuûa ngaên xeáp döôùi ñaây, khoâng khaùc gì ñoái vôùi ñònh
nghóa danh saùch, ngoaïi tröø caùch thöùc maø ngaên xeáp cho pheùp thay ñoåi hoaëc truy
xuaát ñeán caùc phaàn töû cuûa noù.
Ñònh nghóa: Moät ngaên xeáp 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 moät ñoái töôïng ngaên xeáp roãng.
2. Ñaåy (push) moät phaàn töû môùi vaøo ngaên xeáp, giaû söû ngaên xeáp chöa ñaày (phaàn
töû döõ lieäu môùi luoân ñöôïc theâm taïi ñænh).
3. Laáy (pop) moät phaàn töû ra khoûi ngaên xeáp, giaû söû ngaên xeáp chöa roãng (phaàn
töû bò loaïi laø phaàn töû ñang naèm taïi ñænh).
4. Xem phaàn töû taïi ñænh ngaên xeáp (top).
Löu yù raèng ñònh nghóa naøy khoâng quan taâm ñeán caùch hieän thöïc cuûa kieåu döõ
lieäu tröøu töôïng ngaên xeáp. Chuùng ta seõ tìm hieåu moät vaøi caùch hieän thöïc khaùc nhau
cuûa ngaên xeáp vaø taát caû chuùng ñeàu phuø hôïp vôùi ñònh nghóa naøy.
2.2. Ñaëc taû ngaên xeáp
Ngoaøi caùc taùc vuï chính treân, caùc phöông thöùc khaùc coù theå boå sung tuyø vaøo nhu
caàu maø chuùng ta thaáy caàn thieát:
+ empty: cho bieát ngaên xeáp coù roãng hay khoâng.
+ full: cho bieát ngaên xeáp coù ñaày hay chöa.
+ clear: xoùa saïch taát caû döõ lieäu vaø laøm cho ngaên xeáp trôû neân roãng.
Chuùng ta löu yù raèng, khi thieát keá caùc phöông thöùc cho moãi lôùp CTDL, ngoaøi
moät soá phöông thöùc chính ñeå theâm vaøo hay laáy döõ lieäu ra, chuùng ta coù theå boå sung
theâm nhieàu phöông thöùc khaùc. Vieäc theâm döïa vaøo quan nieäm cuûa moãi ngöôøi veà söï
tieän duïng cuûa lôùp CTDL ñoù. Nhöng ñieàu ñaëc bieät quan troïng ôû ñaây laø caùc phöông
thöùc ñoù khoâng theå maâu thuaãn vôùi ñònh nghóa ban ñaàu cuõng nhö caùc chöùc naêng maø
chuùng ta ñaõ ñònh ra cho lôùp. Chaúng haïn, trong tröôøng hôïp ngaên xeáp cuûa chuùng ta,
ñeå baûo ñaûm quy luaät “Vaøo tröôùc ra sau” thì traät töï cuûa caùc phaàn töû trong ngaên xeáp
laø raát quan troïng. Chuùng ta khoâng theå cho chuùng moät phöông thöùc coù theå thay ñoåi
traät töï cuûa caùc phaàn töû ñang coù, hoaëc phöông thöùc laáy moät phaàn töû taïi moät vò trí
baát kyø naøo ñoù cuûa ngaên xeáp.
Treân ñaây laø nhöõng phöông thöùc lieân quan ñeán caùc thao taùc döõ lieäu treân ngaên
xeáp.
Ñoái vôùi baát kyø lôùp CTDL naøo, chuùng ta cuõng khoâng theå khoâng xem xeùt ñeán hai
phöông thöùc cöïc kyø quan troïng: ñoù chính laø hai haøm döïng lôùp vaø huûy lôùp:
constructor vaø destructor. Trong C++ caùc haøm constructor vaø destructor ñöôïc
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
18
Chöông 2 – Ngaên xeáp
trình bieân dòch goïi khi moät ñoái töôïng vöøa ñöôïc taïo ra hoaëc saép bò huûy. Chuùng ta
caàn baûo ñaûm cho moãi ñoái töôïng CTDL ñöôïc taïo ra coù traïng thaùi ban ñaàu laø hôïp leä.
Söï hôïp leä naøy seõ tieáp tuïc ñöôïc duy trì bôûi caùc phöông thöùc thao taùc döõ lieäu beân
treân.
Traïng thaùi ban ñaàu hôïp leä laø traïng thaùi roãng khoâng chöùa döõ lieäu naøo hoaëc
traïng thaùi ñaõ chöùa moät soá döõ lieäu theo nhö mong muoán cuûa ngöôøi laäp trình söû
duïng CTDL. Nhö vaäy, moãi lôùp CTDL luoân coù moät constructor maëc ñònh (khoâng coù
thoâng soá) ñeå taïo ñoái töôïng roãng, caùc constructor coù thoâng soá khaùc chuùng ta coù theå
thieát keá boå sung neáu thaáy hôïp lyù vaø caàn thieát.
Moät ñoái töôïng CTDL khi bò huûy phaûi ñaûm baûo khoâng ñeå laïi raùc trong boä nhôù.
Chuùng ta ñaõ bieát raèng, vôùi caùc bieán caáp phaùt tónh, trình bieân dòch seõ töï laáy laïi
nhöõng vuøng nhôù ñaõ caáp phaùt cho chuùng. Vôùi caùc bieán caáp phaùt ñoäng thì ngöôïc laïi,
vuøng nhôù phaûi ñöôïc chöông trình giaûi phoùng khi khoâng coøn söû duïng ñeán. Nhö
vaäy, ñoái vôùi moãi phöông aùn hieän thöïc cuï theå cho moãi lôùp CTDL maø coù söû duïng
vuøng nhôù caáp phaùt ñoäng, chuùng ta seõ xaây döïng destructor cho noù ñeå lo vieäc giaûi
phoùng vuøng nhôù tröôùc khi ñoái töôïng bò huûy.
Trong C++, constructor coù cuøng teân vôùi lôùp vaø khoâng coù kieåu traû veà. Constructor cuûa moät lôùp
ñöôïc goïi moät caùch töï ñoäng khi moät ñoái töôïng cuûa lôùp ñoù ñöôïc khai baùo.
Ñaëc taû constructor cho lôùp ngaên xeáp, maø chuùng ta ñaët teân laø lôùp Stack, nhö
sau:
template <class Entry>
Stack<Entry>::Stack();
pre: khoâng coù.
post: ñoái töôïng ngaên xeáp vöøa ñöôïc taïo ra laø roãng.
uses: khoâng coù.
Ñeå ñaëc taû tieáp cho caùc phöông thöùc khaùc, chuùng ta choïn ra caùc trò cuûa
ErrorCodeñuû ñeå söû duïng cho lôùp Stacklaø:
success, overflow, underflow
Caùc thoâng soá daønh cho caùc phöông thöùc döôùi ñaây ñöôïc thieát keá tuøy vaøo chöùc naêng
vaø nhu caàu cuûa töøng phöông thöùc.
Phöông thöùc loaïi moät phaàn töû ra khoûi ngaên xeáp:
template <class Entry>
ErrorCode Stack<Entry>::pop();
pre: khoâng coù.
post:neáu ngaên xeáp khoâng roãng, phaàn töû taïi ñænh ngaên xeáp ñöôïc laáy ñi, ErrorCodetraû veà laø
success; neáu ngaên xeáp roãng, ErrorCodetraû veà laø underflow, ngaên xeáp khoâng ñoåi.
uses: khoâng coù.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
19
Chöông 2 – Ngaên xeáp
Phöông thöùc theâm moät phaàn töû döõ lieäu vaøo ngaên xeáp:
template <class Entry>
ErrorCode Stack<Entry>::push(const Entry &item);
pre: khoâng coù.
post: neáu ngaên xeáp khoâng ñaày, itemñöôïc theâm vaøo treân ñænh ngaên xeáp, ErrorCodetraû veà laø
success; neáu ngaên xeáp ñaày, ErrorCodetraû veà laø overflow, ngaên xeáp khoâng ñoåi.
uses: khoâng coù.
Löu yù raèng item trong thoâng soá cuûa push ñoùng vai troø laø tham trò neân ñöôïc
khai baùo laø tham chieáu haèng (const reference). Trong khi ñoù trong phöông thöùc
top, itemlaø tham bieán.
Hai phöông thöùc top vaø empty ñöôïc khai baùo const vì chuùng khoâng laøm thay
ñoåi ngaên xeáp.
template <class Entry>
ErrorCode Stack<Entry>:: top(Entry &item) const;
pre: khoâng coù
post: neáu ngaên xeáp khoâng roãng, phaàn töû taïi ñænh ngaên xeáp ñöôïc cheùp vaøo item, ErrorCodetraû
veà laø success; neáu ngaên xeáp roãng, ErrorCodetraû veà laø underflow; caû hai tröôøng hôïp
ngaên xeáp ñeàu khoâng ñoåi.
uses: khoâng coù.
template <class Entry>
bool Stack<Entry>::empty() const;
pre: khoâng coù
post: neáu ngaên xeáp roãng, haøm traû veà true; neáu ngaên xeáp khoâng roãng, haøm traû veà false, ngaên
xeáp khoâng ñoåi.
uses: khoâng coù.
Sinh vieân coù theå ñaëc taû töông töï cho phöông thöùc full, clear, hay caùc
phöông thöùc boå sung khaùc.
Töø nay veà sau, chuùng ta quy öôùc raèng neáu hai phaàn precondition hoaëc uses khoâng
coù thì chuùng ta khoâng caàn phaûi ghi ra.
Chuùng ta coù phaàn giao tieáp maø lôùp Stack daønh cho ngöôøi laäp trình söû duïng
nhö sau:
template<class Entry>
class Stack {
public:
Stack();
bool empty() const;
ErrorCode pop();
ErrorCode top(Entry &item) const;
ErrorCode push(const Entry &item);
};
Vôùi moät ñaëc taû nhö vaäy chuùng ta ñaõ hoaøn toaøn coù theå söû duïng lôùp Stack trong
caùc öùng duïng. Sinh vieân neân tieáp tuïc xem ñeán phaàn trình baøy caùc öùng duïng veà
ngaên xeáp trong chöông 14. Döôùi ñaây laø chöông trình minh hoïa vieäc söû duïng ngaên
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
20
Chöông 2 – Ngaên xeáp
xeáp thoâng qua caùc ñaëc taû treân. Chöông trình giaûi quyeát baøi toaùn in caùc soá theo thöù
töï ngöôïc vôùi thöù töï nhaäp vaøo ñaõ ñöôïc trình baøy trong phaàn môû ñaàu.
Ví duï:
Chöông trình seõ ñoïc vaøo moät soá nguyeân n vaø n soá thöïc keá ñoù. Moãi soá thöïc
nhaäp vaøo seõ ñöôïc löu vaøo ngaên xeáp. Cuoái cuøng caùc soá ñöôïc laáy töø ngaên xeáp vaø in
ra.
#include
int main()
/*
<Stack>//Söû duïng lôùp Stack.
pre: Ngöôøi söû duïng nhaäp vaøo moät soá nguyeân n vaø n soá thöïc.
post: Caùc soá seõ ñöôïc in ra theo thöù töï ngöôïc.
uses: lôùp Stackvaø caùc phöông thöùc cuûa Stack.
*/
{
int n;
double item;
Stack<double> numbers;
cout <<"Type in an integer n followed by n decimal numbers."<< endl;
cout << " The numbers will be printed in reverse order." << endl;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> item;
numbers.push(item);
}
cout << endl << endl;
while (!numbers.empty()) {
numbers.top(item)
cout << item << " ";
numbers.pop();
}
cout << endl;
}
Che daáu thoâng tin: khi söû duïng lôùp Stack chuùng ta khoâng caàn bieát noù ñöôïc löu
tröõ trong boä nhôù nhö theá naøo vaø caùc phöông thöùc cuûa noù hieän thöïc ra sao. Ñaây laø
vaán ñeà che daáu thoâng tin (information hiding).
Moät CTDL coù theå coù nhieàu caùch hieän thöïc khaùc nhau, nhöng moïi caùch hieän
thöïc ñeàu coù chung phaàn ñaëc taû caùc giao tieáp ñoái vôùi beân ngoaøi. Nhôø ñoù maø caùc
chöông trình öùng duïng giöõ ñöôïc söï ñoäc laäp vôùi caùc hieän thöïc khaùc nhau cuûa cuøng
moät lôùp CTDL. Khi caàn thay ñoåi hieän thöïc cuûa CTDL maø öùng duïng ñang söû duïng,
chuùng ta khoâng caàn chænh söûa maõ nguoàn cuûa öùng duïng.
Tính khaû thi vaø hieäu quaû cuûa öùng duïng: Tuy öùng duïng caàn phaûi ñoäc laäp vôùi
hieän thöïc cuûa caáu truùc döõ lieäu, nhöng vieäc choïn caùch hieän thöïc naøo aûnh höôûng ñeán
tính khaû thi vaø hieäu quaû cuûa öùng duïng. Chuùng ta caàn hieåu caùc öu nhöôïc ñieåm cuûa
moãi caùch hieän thöïc cuûa caáu truùc döõ lieäu ñeå löïa choïn cho phuø hôïp vôùi tính chaát cuûa
öùng duïng.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
21
Chöông 2 – Ngaên xeáp
Tính trong saùng cuûa chöông trình: Öu ñieåm khaùc cuûa che daáu thoâng tin laø
tính trong saùng cuûa chöông trình. Nhöõng teân goïi quen thuoäc daønh cho caùc thao
taùc treân caáu truùc döõ lieäu giuùp chuùng ta hình dung roõ raøng giaûi thuaät cuûa chöông
trình. Chaúng haïn vôùi thao taùc treân ngaên xeáp, ngöôøi ta thöôøng quen duøng caùc töø:
push– ñaåy vaøo ngaên xeáp, pop– laáy ra khoûi ngaên xeáp.
Thieát keá töø treân xuoáng: Söï taùch rôøi giöõa vieäc söû duïng caáu truùc döõ lieäu vaø caùch
hieän thöïc cuûa noù coøn giuùp chuùng ta thöïc hieän toát hôn quaù trình thieát keá töø treân
xuoáng (top-down design) caû cho caáu truùc döõ lieäu vaø caû cho chöông trình öùng duïng.
2.3. Caùc phöông aùn hieän thöïc ngaên xeáp
Trong phaàn naøy chuùng ta seõ tìm hieåu caùc phöông aùn hieän thöïc cho lôùp ngaên
xeáp. Caùc öu nhöôïc ñieåm cuûa caùc caùch hieän thöïc khaùc nhau ñoái vôùi moät ñaëc taû
CTDL thöôøng lieân quan ñeán nhöõng vaán ñeà sau ñaây:
• Cho pheùp hay khoâng cho pheùp löu tröõ vaø thao taùc vôùi löôïng döõ lieäu lôùn.
• Toác ñoä xöû lyù cuûa caùc phöông thöùc.
Vì ngaên xeáp laø moät tröôøng hôïp ñaëc bieät cuûa danh saùch, neân ñaõ ñeán luùc chuùng
ta baøn ñeán caùch löu tröõ caùc phaàn töû trong moät danh saùch. Coù hai phöông aùn löu
tröõ chính:
• Caùc phaàn töû naèm keá nhau trong boä nhôù maø chuùng ta hay duøng töø lieân tuïc
(contiguous) ñeå noùi ñeán.
• Caùc phaàn töû khoâng naèm keá nhau trong boä nhôù maø chuùng ta duøng coâng cuï laø
caùc bieán kieåu con troû (pointer) ñeå quaûn lyù, tröôøng hôïp naøy chuùng ta goïi laø
danh saùch lieân keát (linked list).
Hieän thöïc lieân tuïc ñôn giaûn nhöng bò haïn cheá ôû choã kích thöôùc caàn ñöôïc bieát
tröôùc. Neáu duøng maûng lôùn quaù seõ bò laõng phí, nhöng nhoû quaù deã bò ñaày. Hieän thöïc
lieân keát linh ñoäng hôn, noù chæ bò ñaày khi boä nhôù thöïc söï khoâng coøn choã troáng nöõa.
2.4. Hieän thöïc ngaên xeáp
2.4.1.Hieän thöïc ngaên xeáp lieân tuïc
Ñeå hieän thöïc lôùp ngaên xeáp lieân tuïc (contiguous stack), chuùng ta duøng moät
maûng (array trong C++) ñeå chöùa caùc phaàn töû cuûa ngaên xeáp vaø moät thuoäc tính
countcho bieát soá phaàn töû hieän coù trong ngaên xeáp.
const int max = 10;
template <class Entry>
class Stack {
public:
// Duøng soá nhoû ñeå kieåm tra chöông trình.
Stack();
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
22
Chöông 2 – Ngaên xeáp
bool empty() const;
ErrorCode pop();
ErrorCode top(Entry &item) const;
ErrorCode push(const Entry &item);
private:
int count;
Entry entry[max];
};
Push, pop, vaø caùc phöông thöùc khaùc
YÙ töôûng chung cuûa caùc phöông thöùc naøy nhö sau:
• Vieäc theâm döõ lieäu môùi chæ thöïc hieän ñöôïc khi ngaên xeáp coøn choã troáng.
• Vieäc loaïi phaàn töû khoûi ngaên xeáp hoaëc xem phaàn töû treân ñænh ngaên xeáp chæ
thöïc hieän ñöôïc khi ngaên xeáp khoâng roãng.
• Do count laø soá phaàn töû hieän coù trong ngaên xeáp vaø chæ soá cuûa array trong
C++ ñöôïc baét ñaàu töø 0, neân count-1 chính laø chæ soá cuûa phaàn töû taïi ñænh
ngaên xeáp khi caàn xem hoaëc caàn loaïi boû khoûi ngaên xeáp.
• Khi caàn theâm phaàn töû môùi, count laø chæ soá chæ ñeán vò trí coøn troáng ngay
treân ñænh ngaên xeáp, cuõng laø chæ soá cuûa phaàn töû môùi neáu ñöôïc theâm vaøo.
• Khi ngaên xeáp ñöôïc theâm hoaëc laáy phaàn töû thì thuoäc tính count luoân phaûi
ñöôïc caäp nhaät laïi.
• Constructor taïo ñoái töôïng ngaên xeáp roãng baèng caùch gaùn thuoäc tính count
baèng 0. Löu yù raèng chuùng ta khoâng caàn quan taâm ñeán trò cuûa nhöõng phaàn
töû naèm töø vò trí count cho ñeán heát maûng (max -1), caùc vò trí töø 0 ñeán
count-1môùi thöïc söï chöùa nhöõng döõ lieäu ñaõ ñöôïc ñöa vaøo ngaên xeáp.
template <class Entry>
ErrorCode Stack<Entry>::push(const Entry &item)
/*
post: neáu ngaên xeáp khoâng ñaày, itemñöôïc theâm vaøo treân ñænh ngaên xeáp, ErrorCodetraû veà laø
success; neáu ngaên xeáp ñaày, ErrorCodetraû veà laø overflow, ngaên xeáp khoâng ñoåi.
*/
{
ErrorCode outcome = success;
if (count >= max)
outcome = overflow;
else
entry[count++] = item;
return outcome;
}
template <class Entry>
ErrorCode Stack<Entry>::pop()
/*
post: neáu ngaên xeáp khoâng roãng, phaàn töû taïi ñænh ngaên xeáp ñöôïc laáy ñi, ErrorCodetraû veà laø
success; neáu ngaên xeáp roãng, ErrorCodetraû veà laø underflow, ngaên xeáp khoâng ñoåi.
*/
{
ErrorCode outcome = success;
if (count == 0)
outcome = underflow;
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
23
Chöông 2 – Ngaên xeáp
else --count;
return outcome;
}
template <class Entry>
ErrorCode Stack<Entry>::top(Entry &item) const
/*
post:neáu ngaên xeáp khoâng roãng, phaàn töû taïi ñænh ngaên xeáp ñöôïc cheùp vaøo item, ErrorCodetraû
veà laø success; neáu ngaên xeáp roãng, ErrorCodetraû veà laø underflow; caû hai tröôøng hôïp
ngaên xeáp ñeàu khoâng ñoåi.
*/
{
ErrorCode outcome = success;
if (count == 0)
outcome = underflow;
else
item = entry[count - 1];
return outcome;
}
template <class Entry>
bool Stack<Entry>::empty() const
/*
post: neáu ngaên xeáp roãng, haøm traû veà true; neáu ngaên xeáp khoâng roãng, haøm traû veà false, ngaên
xeáp khoâng ñoåi.
*/
{
bool outcome = true;
if (count > 0) outcome = false;
return outcome;
}
Hình 2.2- Bieåu dieãn cuûa döõ lieäu trong ngaên xeáp lieân tuïc.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
24
Chöông 2 – Ngaên xeáp
Constructor seõ khôûi taïo moät ngaên xeáp roãng.
template <class Entry>
Stack<Entry>::Stack()
/*
post: ngaên xeáp ñöôïc khôûi taïo roãng.
*/
{
count = 0;
}
2.4.2.Hieän thöïc ngaên xeáp lieân keát
Caáu truùc lieân keát ñöôïc taïo bôûi caùc phaàn töû , moãi phaàn töû chöùa hai phaàn: moät
chöùa thoâng tin chính laø döõ lieäu cuûa phaàn töû, moät chöùa con troû tham chieáu ñeán
phaàn töû keá, vaø ñöôïc khai baùo trong C++ nhö sau:
template <class Entry>
struct Node {
// data members
Entry entry;
Node<Entry> *next;
// constructors
Node();
Node(Entry item, Node<Entry> *add_on = NULL);
};
Vaø ñaây laø hình aûnh cuûa moät phaàn töû trong caáu truùc lieân keát:
Hình döôùi ñaây bieåu dieãn moät caáu truùc lieân keát coù con troû chæ ñeán phaàn töû ñaàu
laø First_node.
Hình 2.3- Caáu truùc Nodechöùa con troû
Vaán ñeà ñaët ra laø chuùng ta neân choïn phaàn töû ñaàu hay phaàn töû cuoái cuûa caáu truùc
lieân keát laøm ñænh cuûa ngaên xeáp. Thoaït nhìn, döôøng nhö vieäc theâm moät node môùi
vaøo cuoái caáu truùc lieân keát laø deã hôn (töông töï nhö ñoái vôùi ngaên xeáp lieân tuïc).
Nhöng vieäc loaïi moät phaàn töû ôû cuoái laø khoù bôûi vì vieäc xaùc ñònh phaàn töû ngay tröôùc
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
25
Chöông 2 – Ngaên xeáp
phaàn töû bò loaïi khoâng theå thöïc hieän nhanh choùng. Lyù do laø caùc con troû trong caáu
truùc lieân keát chæ theo moät chieàu. Khi loaïi ñi moät phaàn töû ôû cuoái caáu truùc lieân keát,
chuùng ta phaûi baét ñaàu töø ñaàu, laàn theo caùc con troû, môùi xaùc ñònh ñöôïc phaàn töû
cuoái. Do ñoù, caùch toát nhaát laø vieäc theâm vaøo hay loaïi phaàn töû ñeàu ñöôïc thöïc hieän ôû
phaàn töû ñaàu cuûa caáu truùc lieân keát. Ñænh cuûa ngaên xeáp lieân keát ñöôïc choïn laø phaàn
töû ñaàu cuûa caáu truùc lieân keát.
Hình 2.4- Caáu truùc lieân keát
Moãi caáu truùc lieân keát caàn moät thaønh phaàn con troû chæ ñeán phaàn töû ñaàu tieân.
Ñoái vôùi ngaên xeáp lieân keát, thaønh phaàn naøy luoân chæ ñeán ñænh cuûa ngaên xeáp. Do
moãi phaàn töû trong caáu truùc lieân keát coù tham chieáu ñeán phaàn töû keá neân töø phaàn töû
ñaàu tieân chuùng ta coù theå ñeán moïi phaàn töû trong ngaên xeáp lieân keát baèng caùch laàn
theo caùc tham chieáu naøy. Töø ñoù, thoâng tin duy nhaát caàn thieát ñeå coù theå truy xuaát
döõ lieäu trong ngaên xeáp lieân keát laø ñòa chæ cuûa phaàn töû taïi ñænh. Phaàn töû taïi ñaùy
ngaên xeáp luoân coù tham chieáu laø NULL.
template <class Entry>
class Stack {
public:
Stack();
bool empty() const;
ErrorCode push(const Entry &item);
ErrorCode pop();
ErrorCode top(Entry &item) const;
protected:
Node<Entry> *top_node;
};
Do lôùp Stack giôø ñaây chæ chöùa moät phaàn töû döõ lieäu, chuùng ta coù theå cho raèng
vieäc duøng lôùp coù theå khoâng caàn thieát, thay vaøo ñoù chuùng ta duøng luoân moät bieán ñeå
chöùa ñòa chæ cuûa ñænh ngaên xeáp. Tuy nhieân, ôû ñaây coù boán lyù do ñeå söû duïng lôùp
Stack.
• Lyù do quan troïng nhaát laø söï duy trì tính ñoùng kín: neáu chuùng ta khoâng söû
duïng lôùp ngaên xeáp, chuùng ta khoâng theå xaây döïng caùc phöông thöùc cho ngaên
xeáp.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
26
Chöông 2 – Ngaên xeáp
• Lyù do thöù hai laø ñeå duy trì söï khaùc bieät luaän lyù giöõa lôùp ngaên xeáp, maø baûn
thaân ñöôïc taïo bôûi caùc phaàn töû laø caùc node, vôùi top cuûa ngaên xeáp laø moät con
troû tham chieáu ñeán chæ moät node. Vieäc chuùng ta chæ caàn naém giöõ top cuûa
ngaên xeáp, laø coù theå tìm ñeán moïi phaàn töû khaùc cuûa ngaên xeáp tuy laø hieån
nhieân, nhöng khoâng thích ñaùng vôùi caáu truùc luaän lyù naøy.
• Lyù do thöù ba laø ñeå duy trì tính nhaát quaùn vôùi caùc caáu truùc döõ lieäu khaùc cuõng
nhö caùc caùch hieän thöïc khaùc nhau cuûa moät caáu truùc döõ lieäu: moät caáu truùc döõ
lieäu bao goàm caùc döõ lieäu vaø moät taäp caùc thao taùc.
• Cuoái cuøng, vieäc xem ngaên xeáp nhö moät con troû ñeán ñænh cuûa noù khoâng ñöôïc
phuø hôïp vôùi caùc kieåu döõ lieäu. Thoâng thöôøng, caùc kieåu döõ lieäu phaûi coù khaû
naêng hoã trôï trong vieäc debug chöông trình baèng caùch cho pheùp trình bieân
dòch thöïc hieän vieäc kieåm tra kieåu moät caùch toát nhaát.
Chuùng ta haõy baét ñaàu baèng moät ngaên xeáp roãng, top_node == NULL, vaø xem
xeùt vieäc theâm phaàn töû ñaàu tieân vaøo ngaên xeáp. Chuùng ta caàn taïo moät node môùi
chöùa baûn sao cuûa thoâng soá item nhaän vaøo bôû phöông thöùc push. Node naøy ñöôïc
truy xuaát bôûi bieán con troû new_top. Sau ñoù ñòa chæ chöùa trong new_top seõ ñöôïc
cheùp vaøo top_node cuûa Stack (hình 2.5a):
Node *new_top = new Node<Entry>(item);
top_node = new_top;
Chuù yù raèng ôû ñaây, constructor khi taïo moät node môùi ñaõ gaùn next cuûa noù baèng
NULL, vaø chuùng ta hoaøn toaøn an taâm vì khoâng bao giôø coù con troû mang trò ngaãu
nhieân.
(a)
Hình 2.5- Theâm moät phaàn töû vaøo ngaên xeáp lieân keát.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
27
Chöông 2 – Ngaên xeáp
Neáu trung thaønh vôùi nguyeân taéc “Khoâng bao giôø ñeå moät bieán con troû mang trò
ngaãu nhieân”, chuùng ta seõ giaûm ñöôïc gaùnh naëng ñaùng keå trong coâng söùc laäp trình
vì khoâng phaûi maát quaù nhieàu thì giôø vaø ñau ñaàu do nhöõng loãi maø noù gaây ra.
Ñeå tieáp tuïc, xem nhö chuùng ta ñaõ coù moät ngaên xeáp khoâng roãng. Ñeå ñöa theâm
phaàn töû vaøo ngaên xeáp, chuùng ta caàn theâm moät node vaøo ngaên xeáp. Tröôùc heát
chuùng ta caàn taïo moät node môùi ñöôïc tham chieáu bôûi con troû new_top, node naøy
phaûi coù döõ lieäu laø item vaø lieân keát next tham chieáu ñeán top cuõ cuûa ngaên xeáp.
Sau ñoù chuùng ta seõ thay ñoåi top_node cuûa ngaên xeáp tham chieáu ñeán node môùi
naøy (hình 2.5b). Thöù töï cuûa hai pheùp gaùn naøy raát quan troïng: neáu chuùng ta laøm
theo thöù töï ngöôïc laïi, vieäc thay ñoåi top_nodesôùm seõ laøm maát khaû naêng truy xuaát
caùc phaàn töû ñaõ coù cuûa ngaên xeáp. Chuùng ta coù phöông thöùc pushnhö sau:
template <class Entry>
ErrorCode Stack<Entry>::push(const Entry &item)
/*
post: neáu ngaên xeáp khoâng ñaày, item ñöôïc theâm vaøo treân ñænh ngaên xeáp, ErrorCode traû veà laø
success; neáu ngaên xeáp ñaày, ErrorCodetraû veà laø overflow, ngaên xeáp khoâng ñoåi.
*/
{
Node *new_top = new Node<Entry>(item, top_node);
if (new_top == NULL) return overflow;
top_node = new_top;
return success;
}
Khi thay ñoåi caùc tham chieáu (caùc bieán con troû), thöù töï caùc pheùp gaùn luoân caàn
ñöôïc xem xeùt moät caùch kyõ löôõng.
.
Phöông thöùc push traû veà ErrorCode laø overflow trong tröôøng hôïp boä nhôù
ñoäng khoâng tìm ñöôïc choã troáng ñeå caáp phaùt cho phaàn töû môùi, toaùn töû new traû veà
trò NULL.
Vieäc laáy moät phaàn töû ra khoûi ngaên xeáp thöïc söï ñôn giaûn:
Hình 2.6- Laáy moät phaàn töû ra khoûi ngaên xeáp lieân keát.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
28
Chöông 2 – Ngaên xeáp
template <class Entry>
ErrorCode Stack<Entry>::pop()
/*
post: neáu ngaên xeáp khoâng roãng, phaàn töû taïi ñænh ngaên xeáp ñöôïc laáy ñi, ErrorCodetraû veà laø
success; neáu ngaên xeáp roãng, ErrorCodetraû veà laø underflow, ngaên xeáp khoâng ñoåi.
*/
{
Node *old_top = top_node;
if (top_node == NULL) return underflow;
top_node = old_top->next;
delete old_top;
return success;
}
Löu yù raèng trong phöông thöùc pop, chæ caàn gaùn top_node cuûa ngaên xeáp tham
chieáu ñeán phaàn töû thöù hai trong ngaên xeáp thì phaàn töû thöù nhaát xem nhö ñaõ ñöôïc
loaïi khoûi ngaên xeáp. Tuy nhieân, neáu khoâng thöïc hieän vieäc giaûi phoùng phaàn töû treân
ñænh ngaên xeáp, chöông trình seõ gaây ra raùc. Trong öùng duïng nhoû, phöông thöùc pop
vaãn chaïy toát. Nhöng neáu öùng duïng lôùn goïi phöông thöùc naøy raát nhieàu laàn, soá
löôïng raùc seõ lôùn leân ñaùng keå daãn ñeán khoâng ñuû vuøng nhôù ñeå chöông trình chaïy
tieáp.
Khi moät caáu truùc döõ lieäu ñöôïc hieän thöïc, noù phaûi ñöôïc xöû lyù toát trong moïi
tröôøng hôïp ñeå coù theå ñöôïc söû duïng trong nhieàu öùng duïng khaùc nhau.
2.4.3.Ngaên xeáp lieân keát vôùi söï an toaøn
Khi söû duïng caùc phöông thöùc maø chuùng ta vöøa xaây döïng cho ngaên xeáp lieân keát,
ngöôøi laäp trình coù theå voâ tình gaây neân raùc hoaëc phaù vôõ tính ñoùng kín cuûa caùc ñoái
töôïng ngaên xeáp. Trong phaàn naøy chuùng ta seõ xem xeùt chi tieát veà caùc nguy cô laøm
maát ñi tính an toaøn vaø tìm hieåu theâm ba phöông thöùc maø C++ cung caáp ñeå khaéc
phuïc vaán ñeà naøy, ñoù laø caùc taùc vuï huûy ñoái töôïng (destructor), taïo ñoái töôïng baèng
caùch sao cheùp töø ñoái töôïng khaùc (copy constructor) vaø pheùp gaùn ñöôïc ñònh nghóa
laïi (overloaded assignment). Hai taùc vuï ñaàu khoâng ñöôïc goïi töôøng minh bôûi
ngöôøi laäp trình, chuùng seõ ñöôïc trình bieân dòch goïi luùc caàn thieát; rieâng taùc vuï thöù
ba ñöôïc goïi bôûi ngöôøi laäp trình khi caàn gaùn hai ñoái töôïng. Nhö vaäy, vieäc boå sung
nhaèm baûo ñaûm tính an toaøn cho lôùp Stack khoâng laøm thay ñoåi veû beà ngoaøi cuûa
Stackñoái vôùi ngöôøi söû duïng.
2.4.3.1. Haøm huûy ñoái töôïng (Destructor)
Giaû söû nhö ngöôøi laäp trình vieát moät voøng laëp ñôn giaûn trong ñoù khai baùo moät
ñoái töôïng ngaên xeáp coù teân laø small vaø ñöa döõ lieäu vaøo. Chaúng haïn chuùng ta xem
xeùt ñoaïn leänh sau:
for (int i=0; i < 1000000; i++) {
Stack<Entry> small;
small.push(some_data);
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
29
Chöông 2 – Ngaên xeáp
Trong moãi laàn laëp, ñoái töôïng small ñöôïc taïo ra, döõ lieäu theâm vaøo thuoäc vuøng
boä nhôù caáp phaùt ñoäng, sau ñoù ñoái töôïng small khoâng coøn toàn taïi khi ra khoûi taàm
vöïc hoaït ñoäng cuûa noù (scope). Giaû söû chöông trình söû duïng ngaên xeáp lieân keát ñöôïc
hieän thöïc nhö hình 2.4. Ngay khi ñoái töôïng small khoâng coøn toàn taïi , döõ lieäu
trong ngaên xeáp trôû thaønh raùc, vì baûn thaân ñoái töôïng small chæ chöùa con troû
top_node, vuøng nhôù maø con troû naøy chieám seõ ñöôïc traû veà cho heä thoáng, coøn caùc
döõ lieäu maø con troû naøy tham chieáu ñeán thuoäc vuøng nhôù caáp phaùt ñoäng vaãn chöa
ñöôïc traû veà heä thoáng. Voøng laëp treân ñöôïc thöïc hieän haøng trieäu laàn, vaø raùc seõ bò
tích luõy raát nhieàu. Trong tröôøng hôïp naøy khoâng theå buoäc toäi ngöôøi laäp trình: do
voøng laëp seõ chaúng gaây ra vaán ñeà gì neáu ngöôøi laäp trình söû duïng hieän thöïc ngaên
xeáp lieân tuïc, moïi vuøng nhôù daønh cho döõ lieäu trong ngaên xeáp lieân tuïc ñeàu ñöôïc giaûi
phoùng khi ngaên xeáp ra khoûi taàm vöïc.
Moät ñieàu chaéc chaén raèng khi hieän thöïc ngaên xeáp lieân keát, chuùng ta caàn phaûi
caûnh baùo ngöôøi söû duïng khoâng ñöôïc ñeå moät ñoái töôïng ngaên xeáp khoâng roãng ra
khoûi taàm vöïc, hoaëc chuùng ta phaûi laøm roãng ngaên xeáp tröôùc khi noù ra khoûi taàm
vöïc.
Ngoân ngöõ C++ cung caáp cho lôùp phöông thöùc destructor ñeå giaûi quyeát vaán ñeà naøy. Ñoái vôùi moïi
lôùp, destructor laø moät phöông thöùc ñaëc bieät ñöôïc thöïc thi cho ñoái töôïng cuûa lôùp ngay tröôùc khi ñoái
töôïng ra khoûi taàm vöïc. Ngöôøi söû duïng khoâng caàn phaûi goïi destructor moät caùch töôøng minh vaø
thaäm chí cuõng khoâng caàn bieát ñeán söï toàn taïi cuûa noù. Ñoái vôùi ngöôøi söû duïng, moät lôùp coù destructor
coù theå ñöôïc thay theá moät caùch ñôn giaûn bôûi moät lôùp maø khoâng coù noù.
Destructor thöôøng ñöôïc söû duïng ñeå giaûi phoùng caùc ñoái töôïng caáp phaùt ñoäng maø
chuùng coù theå taïo neân raùc. Trong tröôøng hôïp cuûa chuùng ta, chuùng ta neân boå sung
theâm destructor cho lôùp ngaên xeáp lieân keát. Sau hieäu chænh naøy, ngöôøi söû duïng seõ
khoâng theå gaây ra raùc khi ñeå moät ñoái töôïng ngaên xeáp khoâng roãng ra khoûi taàm vöïc.
Destructor ñöôïc khai baùo nhö moät phöông thöùc cuûa lôùp, khoâng coù thoâng soá vaø
khoâng coù trò traû veà. Teân cuûa destructor laø teân lôùp coù theâm daáu ~ phía tröôùc.
Stack::~Stack();
Do phöông thöùc pop ñöôïc laäp trình ñeå loaïi moät phaàn töû ra khoûi ngaên xeáp,
chuùng ta coù theå hieän thöïc destructor cho ngaên xeáp baèng caùch laëp nhieàu laàn vieäc
goïi pop:
template <class Entry>
Stack::~Stack() // Destructor
/*
post: ngaên xeáp ñaõ ñöôïc laøm roãng.
*/
{
while (!empty())
pop();
}
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
30
Chöông 2 – Ngaên xeáp
Ñoái vôùi moïi caáu truùc lieân keát chuùng ta caàn vieát destructor ñeå doïn deïp caùc ñoái
töôïng tröôùc khi chuùng ra khoûi taàm vöïc.
2.4.3.2. Ñònh nghóa laïi pheùp gaùn
Ngay khi chuùng ta ñaõ boå sung destructor cho ngaên xeáp lieân keát, ngöôøi söû duïng
cuõng coù theå taïo raùc khi vieát voøng laëp töïa nhö ví duï sau.
Stack<Entry> outer_stack;
for (int i=0; i < 1000000; i++) {
Stack<Entry> inner_stack;
inner_stack.push(some_data);
inner_stack = outer_stack;
}
Ñaàu tieân laø ñoái töôïng outer_stack ñöôïc taïo ra, sau ñoù voøng laëp ñöôïc thöïc hieän.
Moãi laàn laëp laø moät laàn taïo moät ñoái töôïng inner_stack, ñöa döõ lieäu vaøo
inner_stack, gaùn outer_stack vaøo inner_stack. Leänh gaùn naøy gaây ra moät vaán ñeà
nghieâm troïng cho hieän thöïc ngaên xeáp lieân keát cuûa chuùng ta. Thoâng thöôøng, C++
thöïc hieän pheùp gaùn caùc ñoái töôïng baèng caùch cheùp caùc thuoäc tính cuûa caùc ñoái töôïng.
Do ñoù, outer_stack.top_node ñöôïc ghi ñeø leân inner_stack.top_node, laøm cho döõ lieäu
cuõ tham chieáu bôûi inner_stack.top_node trôû thaønh raùc. Cuõng gioáng nhö phaàn
tröôùc, neáu hieän thöïc ngaên xeáp lieân tuïc ñöôïc söû duïng thì khoâng coù vaán ñeà gì xaûy
ra. Nhö vaäy, loãi laø do hieän thöïc ngaên xeáp lieân keát coøn thieáu soùt.
Hình 2.7- ÖÙng duïng cheùp ngaên xeáp.
Hình 2.7 cho thaáy taùc vuï gaùn khoâng ñöôïc thöïc hieän nhö mong muoán. Sau pheùp
gaùn, caû hai ngaên xeáp cuøng chia xeû caùc node. Cuoái moãi laàn laëp, destructor cuûa
inner_stack seõ giaûi phoùng moïi döõ lieäu cuûa outer_stack. Vieäc giaûi phoùng döõ
lieäu cuûa outer_stack coøn laøm cho outer_stack.top_node trôû thaønh tham
chieáu treo, coù nghóa laø tham chieáu ñeán vuøng nhôù khoâng xaùc ñònh.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
31
Chöông 2 – Ngaên xeáp
Vaán ñeà sinh ra bôûi pheùp gaùn treân ngaên xeáp lieân keát laø do noù cheùp caùc tham
chieáu chöù khoâng phaûi cheùp caùc trò. Pheùp gaùn trong tröôøng hôïp naøy ñöôïc goïi laø
pheùp gaùn coù ngöõ nghóa tham chieáu (reference semantics) . Ngöôïc laïi, khi pheùp gaùn
thöïc söï cheùp döõ lieäu trong CTDL chuùng ta goïi laø pheùp gaùn coù ngöõ nghóa trò (value
semantics). Trong hieän thöïc lôùp ngaên xeáp lieân keát, hoaëc chuùng ta phaûi caûnh baùo
cho ngöôøi söû duïng raèng pheùp gaùn chæ laø pheùp gaùn coù ngöõ nghóa tham chieáu, hoaëc
chuùng ta phaûi laøm cho trình bieân dòch C++ thöïc hieän pheùp gaùn coù ngöõ nghóa trò.
Trong C++, chuùng ta hieän thöïc moät phöông thöùc ñaëc bieät goïi laø pheùp gaùn ñöôïc
ñònh nghóa laïi (overloaded assignment) ñeå ñònh nghóa laïi caùch thöïc hieän pheùp
gaùn. Khi trình bieân dòch C++ dòch moät pheùp gaùn coù daïng x = y, noù öu tieân choïn
pheùp gaùn ñöôïc ñònh nghóa laïi tröôùc neáu nhö lôùp x coù ñònh nghóa. Chæ khi khoâng coù
phöông thöùc naøy, trình bieân dòch môùi dòch pheùp gaùn nhö laø pheùp gaùn töøng bit ñoái
vôùi caùc thuoäc tính cuûa ñoái töôïng (neáu thuoäc tính laø con troû thì pheùp gaùn trôû thaønh
pheùp gaùn coù ngöõ nghóa tham chieáu). Chuùng ta caàn ñònh nghóa laïi ñeå pheùp gaùn cho
ngaên xeáp lieân keát trôû thaønh pheùp gaùn coù ngöõ nghóa trò.
Coù moät vaøi caùch ñeå khai baùo vaø hieän thöïc pheùp gaùn ñöôïc ñònh nghóa laïi. Caùch
ñôn giaûn laø khai baùo nhö sau:
void Stack<Entry>::operator= ( const Stack &original );
Pheùp gaùn naøy coù theå ñöôïc goïi nhö sau:
x.operator = (y);
hoaëc goïi theo cuù phaùp thöôøng duøng:
x = y;
Pheùp gaùn ñònh nghóa laïi cho ngaên xeáp lieân keát caàn laøm nhöõng vieäc sau:
• Cheùp döõ lieäu töø ngaên xeáp ñöôïc truyeàn vaøo thoâng qua thoâng soá.
• Giaûi phoùng vuøng nhôù chieám giöõ bôûi döõ lieäu cuûa ñoái töôïng ngaên xeáp ñang
ñöôïc thöïc hieän leänh gaùn.
• Chuyeån caùc döõ lieäu vöøa cheùp ñöôïc cho ñoái töôïng ngaên xeáp ñöôïc gaùn.
template <class Entry>
void Stack::operator = (const Stack<Entry> &original) // Overload assignment
/*
post:ñoái töôïng ngaên xeáp ñöôïc gaùn chöùa caùc döõ lieäu gioáng heät ngaên xeáp ñöôïc truyeàn vaøo qua
thoâng soá.
*/
{
Node<Entry> *new_top, *new_copy, *original_node = original.top_node;
if (original_node == NULL) new_top = NULL;
else {
// Taïo baûn sao caùc node.
new_copy = new_top = new Node<Entry>(original_node->entry);
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
32
Chöông 2 – Ngaên xeáp
while (original_node->next != NULL) {
original_node = original_node->next;
new_copy->next = new Node<Entry>(original_node->entry);
new_copy = new_copy->next;
}
}
while (!empty())
pop();
// Laøm roãng ngaên xeáp seõ ñöôïc gaùn.
top_node = new_top;
// Ngaên xeáp ñöôïc gaùn seõ naém giöõ baûn sao.
}
Löu yù raèng trong phöông thöùc treân chuùng ta taïo ra moät baûn sao töø ngaên xeáp
original tröôùc, roài môùi doïn deïp ngaên xeáp seõ ñöôïc gaùn baèng caùch goïi phöông
thöùc pop nhieàu laàn. Nhôø vaäy neáu trong öùng duïng coù pheùp gaùn x = x thì döõ lieäu
cuõng khoâng bò sai.
Pheùp gaùn ñöôïc ñònh nghóa laïi nhö treân thoûa yeâu caàu laø pheùp gaùn coù ngöõ nghóa
trò, tuy nhieân ñeå coù theå söû duïng trong tröôøng hôïp:
first_stack=second_stack=third_stack=..., pheùp gaùn phaûi traû veà
Stack&(tham chieáu ñeán lôùp Stack).
2.4.3.3. Copy constructor
Tröôøng hôïp cuoái cuøng veà söï thieáu an toaøn cuûa caùc caáu truùc lieân keát laø khi trình
bieân dòch caàn cheùp moät ñoái töôïng. Chaúng haïn, moät ñoái töôïng caàn ñöôïc cheùp khi
noù laø tham trò gôûi cho moät haøm. Trong C++, taùc vuï cheùp maëc nhieân laø cheùp caùc
thuoäc tính thaønh phaàn cuûa lôùp. Cuõng gioáng nhö minh hoïa trong hình 2.7, taùc vuï
cheùp maëc nhieân naøy seõ daãn ñeán vieäc caùc ñoái töôïng cuøng chia xeû döõ lieäu. Noùi moät
caùch khaùc, taùc vuï cheùp maëc ñònh coù ngöõ nghóa tham chieáu khi ñoái töôïng coù thuoäc
tính kieåu con troû. Ñieàu naøy laøm cho ngöôøi söû duïng coù theå voâ tình laøm maát döõ
lieäu:
void destroy_the_stack (Stack<Entry> copy)
{
…
}
int main()
{
Stack<Entry> vital_data;
destroy_the_stack(vital_data);
}
Haøm destroy_the_stack nhaän moät baûn sao copy cuûa vital_data. Baûn sao
naøy cuøng chia xeû döõ lieäu vôùi vital_data, do ñoù khi keát thuùc haøm, destructor thöïc
hieän treân baûn sao copyseõ laøm maát luoân döõ lieäu cuûa vital_data.
C++ cho pheùp lôùp coù theâm phöông thöùc copy constructor ñeå taïo moät ñoái
töôïng môùi gioáng moät ñoái töôïng ñaõ coù. Neáu chuùng ta hieän thöïc copy constructor
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
33
Chöông 2 – Ngaên xeáp
cho lôùp Stack thì trình bieân dòch C++ seõ öu tieân choïn taùc vuï cheùp naøy thay cho
taùc vuï cheùp maëc ñònh. Chuùng ta caàn hieän thöïc copy constructor ñeå coù ñöôïc ngöõ
nghóa trò.
Ñoái vôùi moïi lôùp, khai baùo chuaån cho copy constructor cuõng gioáng nhö khai baùo
constructor nhöng coù theâm thoâng soá laø tham chieáu haèng ñeán ñoái töôïng cuûa lôùp:
Stack<Entry>::Stack ( const Stack<Entry> &original );
Do ñoái töôïng goïi copy constructor laø moät ñoái töôïng roãng vöøa ñöôïc taïo môùi neân
chuùng ta khoâng phaûi lo doïn deïp döõ lieäu nhö tröôøng hôïp ñoái vôùi pheùp gaùn ñöôïc
ñònh nghóa laïi. Chuùng ta chæ vieäc cheùp node ñaàu tieân vaø sau ñoù duøng voøng laëp ñeå
cheùp tieáp caùc nodecoøn laïi.
template <class Entry>
Stack<Entry>::Stack(const Stack<Entry> &original) // copy constructor
/*
post: ñoái töôïng ngaên xeáp vöøa ñöôïc taïo ra coù döõ lieäu gioáng vôùi ngaên xeáp original
*/
{
Node<Entry> *new_copy, *original_node = original.top_node;
if (original_node == NULL) top_node = NULL;
else {
// Taïo baûn sao cho caùc node.
top_node = new_copy = new Node<Entry>(original_node->entry);
while (original_node->next != NULL) {
original_node = original_node->next;
new_copy->next = new Node<Entry>(original_node->entry);
new_copy = new_copy->next;
}
a(
}
Moät caùch toång quaùt, ñoái vôùi moïi lôùp lieân keát, hoaëc chuùng ta boå sung copy
constructor, hoaëc chuùng ta caûnh baùo ngöôøi söû duïng raèng vieäc cheùp ñoái töôïng coù
ngöõ nghóa tham chieáu.
2.4.4.Ñaëc taû ngaên xeáp lieân keát ñaõ hieäu chænh
Chuùng ta keát thuùc phaàn naøy baèng ñaëc taû ñaõ ñöôïc hieäu chænh döôùi ñaây cho ngaên
xeáp lieân keát. Phaàn ñaëc taû naøy coù ñöôïc moïi ñaëc tính an toaøn maø chuùng ta ñaõ phaân
tích.
template <class Entry>
class Stack {
public:
// Caùc phöông thöùc chuaån cuûa lôùp Stack:
Stack();
bool empty() const;
ErrorCode push(const Entry &item);
ErrorCode pop();
ErrorCode top(Entry &item) const;
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
34
Chöông 2 – Ngaên xeáp
// Caùc ñaëc taû ñaûm baûo tính an toaøn cho caáu truùc lieân keát:
~Stack();
Stack(const Stack<Entry> &original);
void operator =(const Stack<Entry> &original);
protected:
Node<Entry> *top_node;
};
Treân ñaây laø phaàn trình baøy ñaày ñuû nhaát veà nhöõng yeâu caàu caàn coù ñoái vôùi ngaên
xeáp lieân keát, nhöng noù cuõng ñuùng vôùi caùc caáu truùc lieân keát khaùc. Trong caùc phaàn
sau cuûa giaùo trình naøy seõ khoâng giaûi thích theâm veà 3 taùc vuï naøy nöõa, sinh vieân töï
phaûi hoaøn chænh khi hieän thöïc baát kyø CTDL naøo coù thuoäc tính kieåu con troû.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
35
Chöông 2 – Ngaên xeáp
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
36
20 trang
23760
Free
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 2: Ngăn xếp", để 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:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2_cac_cau_tru.pdf
