Chöông 4 – Danh saùch
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 51
Chöông 4 – DANH SAÙCH
Chuùng ta ñaõ laøm quen vôùi caùc danh saùch haïn cheá nhö ngaên xeáp vaø haøng, trong
ñoù vieäc theâm/ bôùt döõ lieäu chæ thöïc hieän ôû caùc ñaàu cuûa danh saùch. Trong chöông
naøy chuùng ta tìm hieåu caùc danh saùch thoâng thöôøng hôn maø trong ñoù vieäc theâm,
loaïi hoaëc truy xuaát phaàn töû coù theå thöïc hieän taïi baát kyø vò trí naøo trong danh saùch.
4.1. Ñònh nghóa danh saùch
Chuùng ta baét ñaàu baèng vieäc ñònh nghóa kieåu caáu truùc döõ lieäu tröøu töôïng goïi laø
danh saùch (list). Cuõng gioáng nhö ngaên xeáp vaø haøng, danh saùch bao goàm moät chuoãi
noái tieáp caùc phaàn töû döõ lieäu. Tuy nhieân, khaùc vôùi ngaên xeáp vaø haøng, danh saùch
cho pheùp thao taùc treân moïi phaàn töû.
Ñònh nghóa: Danh saùch caùc phaàn töû kieåu T laø moät chuoãi noái tieáp höõu haïn caùc
phaàn töû kieåu T cuøng caùc taùc vuï sau:
1. Taïo moät danh saùch roãng.
2. Xaùc ñònh danh saùch coù roãng hay khoâng.
3. Xaùc ñònh danh saùch coù ñaày hay chöa.
4. Tìm soá phaàn töû cuûa danh saùch.
5. Laøm roãng danh saùch.
6. Theâm phaàn töû vaøo moät vò trí naøo ñoù cuûa danh saùch.
7. Loaïi phaàn töû taïi moät vò trí naøo ñoù cuûa danh saùch.
8. Truy xuaát phaàn töû taïi moät vò trí naøo ñoù cuûa danh saùch.
9. Thay theá phaàn töû taïi moät vò trí naøo ñoù cuûa danh saùch.
10. Duyeät danh saùch, thöïc hieän moät coâng vieäc cho tröôùc treân moãi phaàn töû.
Ngoaøi ra coøn moät soá taùc vuï khaùc coù theå aùp leân moät chuoãi noái tieáp caùc phaàn töû.
Chuùng ta coù theå xaây döïng raát nhieàu daïng khaùc nhau cho caùc kieåu caáu truùc döõ lieäu
tröøu töôïng töông töï baèng caùch söû duïng caùc goùi taùc vuï khaùc nhau. Baát kyø moät trong
caùc daïng naøy ñeàu coù theå ñöôïc ñònh nghóa cho teân goïi CTDL danh saùch. Tuy nhieân,
chuùng ta chæ taäp trung vaøo moät danh saùch cuï theå maø caùc taùc vuï cuûa noù coù theå ñöôïc
xem nhö moät khuoân maãu ñeå minh hoïa yù töôûng vaø caùc vaán ñeà caàn giaûi quyeát treân
danh saùch.
4.2. Ñaëc taû caùc phöông thöùc cho danh saùch
Khi baét ñaàu tìm hieåu ngaên xeáp, chuùng ta nhaán maïnh vieäc che daáu thoâng tin
baèng caùch phaân bieät giöõa vieäc söû duïng ngaên xeáp vaø vieäc laäp trình cho caùc taùc vuï
treân ngaên xeáp. Ñoái vôùi haøng, chuùng ta tieáp tuïc yù töôûng naøy vaø ñaõ nhanh choùng
tìm ñöôïc raát nhieàu caùch hieän thöïc coù theå coù. Caùc danh saùch thoâng duïng cho pheùp
truy xuaát vaø thay ñoåi baát kyø phaàn töû naøo. Do ñoù nguyeân taéc che daáu thoâng tin ñoái
Chöông 4 – Danh saùch
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 52
vôùi danh saùch caøng quan troïng hôn nhieàu so vôùi ngaên xeáp vaø haøng. Chuùng ta haõy
ñaëc taû cho caùc taùc vuï treân danh saùch:
Constructor caàn coù tröôùc khi danh saùch ñöôïc söû duïng:
template <class Entry>
List<Entry>::List();
post: ñoái töôïng danh saùch roãng ñaõ ñöôïc taïo.
Taùc vuï thöïc hieän treân moät danh saùch ñaõ coù vaø laøm roãng danh saùch:
template <class Entry>
void List<Entry>::clear();
post: Moïi phaàn töû cuûa danh saùch ñaõ ñöôïc giaûi phoùng, danh saùch trôû neân roãng.
Caùc taùc vuï xaùc ñònh traïng thaùi cuûa danh saùch:
template <class Entry>
bool List<Entry>::empty() const;
post: traû veà true neáu danh saùch roãng, ngöôïc laïi traû veà false. Danh saùch khoâng ñoåi.
template <class Entry>
bool List<Entry>::full() const;
post: traû veà true neáu danh saùch ñaày, ngöôïc laïi traû veà false. Danh saùch khoâng ñoåi.
template <class Entry>
int List<Entry>::size() const;
post: traû veà soá phaàn töû cuûa danh saùch. Danh saùch khoâng ñoåi.
Chuùng ta xem xeùt tieáp caùc taùc vuï truy xuaát caùc phaàn töû cuûa danh saùch. Töông
töï nhö ñoái vôùi ngaên xeáp vaø haøng, caùc taùc vuï naøy seõ traû veà ErrorCode khi caàn
thieát.
Chuùng ta duøng moät soá nguyeân ñeå chæ vò trí (position) cuûa phaàn töû trong danh
saùch. Vò trí ôû ñaây ñöôïc hieåu laø thöù töï cuûa phaàn töû trong danh saùch. Caùc vò trí
trong danh saùch ñöôïc ñaùnh soá 0, 1, 2, ...Vieäc xaùc ñònh moät phaàn töû trong danh
saùch thoâng qua vò trí raát gioáng vôùi söï söû duïng chæ soá trong daõy, tuy nhieân vaãn coù
moät soá ñieåm khaùc nhau quan troïng. Neáu chuùng ta theâm moät phaàn töû vaøo moät vò
trí naøo ñoù trong danh saùch thì vò trí cuûa taát caû caùc phaàn töû phía sau seõ taêng leân 1.
Neáu loaïi moät phaàn töû thì vò trí caùc phaàn töû phía sau giaûm 1. Vò trí cuûa caùc phaàn
töû trong danh saùch ñöôïc xaùc ñònh khoâng xeùt ñeán caùch hieän thöïc. Ñoái vôùi danh
saùch lieân tuïc, hieän thöïc baèng daõy, vò trí phaàn töû roõ raøng laø chæ soá cuûa phaàn töû
trong daõy. Nhöng chuùng ta cuõng vaãn thoâng qua vò trí ñeå tìm caùc phaàn töû trong
danh saùch lieân keát duø raèng danh saùch lieân keát khoâng coù chæ soá.
Chöông 4 – Danh saùch
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 53
Chuùng ta seõ ñaëc taû chính xaùc caùc phöông thöùc lieân quan ñeán chæ moät phaàn töû
cuûa danh saùch döôùi ñaây.
template <class Entry>
ErrorCode List<Entry>::insert(int position, const Entry &x);
post: Neáu danh saùch chöa ñaày vaø 0 ≤ position ≤ n, n laø soá phaàn töû hieän coù cuûa danh saùch,
phöông thöùc traû veà success: moïi phaàn töû töø position ñeán cuoái danh saùch seõ coù vò trí
taêng leân 1, x ñöôïc theâm vaøo taïi position; ngöôïc laïi, danh saùch khoâng ñoåi, ErrorCode seõ
cho bieát loãi cuï theå.
Phöông thöùc insert chaáp nhaän position baèng n vì noù chaáp nhaän theâm phaàn
töû môùi ngay sau phaàn töû cuoái. Tuy nhieân, caùc phöông thöùc sau chæ chaáp nhaän
position<n, vì chuùng chæ thöïc hieän treân nhöõng phaàn töû ñaõ coù saün.
template <class Entry>
ErrorCode List<Entry>::remove(int position, Entry &x);
post: Neáu 0 ≤ position < n, n laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà
success: phaàn töû taïi position ñöôïc loaïi khoûi danh saùch, trò cuûa noù ñöôïc cheùp vaøo x, caùc
phaàn töû phía sau giaûm vò trí bôùt 1; ngöôïc laïi, danh saùch khoâng ñoåi, ErrorCode seõ cho bieát
loãi cuï theå.
template <class Entry>
ErrorCode List<Entry>::retrieve(int position, Entry &x) const;
post: Neáu 0 ≤ position < n, n laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà
success: phaàn töû taïi position ñöôïc cheùp vaøo x, danh saùch khoâng ñoåi; ngöôïc laïi,
ErrorCode seõ cho bieát loãi cuï theå. Caû hai tröôøng hôïp danh saùch ñeàu khoâng ñoåi.
template <class Entry>
ErrorCode List<Entry>::replace(int position, const Entry &x);
post: Neáu 0 ≤ position < n, n laø soá phaàn töû hieän coù cuûa danh saùch, phöông thöùc traû veà
success: phaàn töû taïi position ñöôïc thay theá bôûi x; ngöôïc laïi, danh saùch khoâng ñoåi,
ErrorCode seõ cho bieát loãi cuï theå.
Phöông thöùc duyeät danh saùch ñeå thöïc hieän moät nhieäm vuï naøo ñoù cho töøng
phaàn töû cuûa danh saùch thöôøng toû ra coù lôïi, ñaëc bieät cho muïc ñích kieåm tra. Ngöôøi
söû duïng goïi phöông thöùc naøy khi muoán thöïc hieän moät coâng vieäc gì ñoù treân töøng
phaàn töû cuûa danh saùch. Chaúng haïn, ngöôøi söû duïng coù hai haøm
void update(List_Entry &x) vaø void modify(List_Entry &x),
vaø moät ñoái töôïng the_list cuûa lôùp List, coù theå söû duïng leänh
the_list.traverse(update) hoaëc the_list.traverse(modify)
Chöông 4 – Danh saùch
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 54
ñeå thöïc hieän moät trong hai haøm treân leân moãi phaàn töû cuûa danh saùch. Neáu ngöôøi
söû duïng muoán in moïi phaàn töû cuûa danh saùch thì goïi nhö sau:
the_list.traverse(print)
vôùi void print(Entry &x) laø moät haøm duøng ñeå in moät phaàn töû cuûa danh saùch.
Khi goïi phöông thöùc traverse, ngöôøi söû duïng gôûi teân cuûa haøm laøm thoâng soá.
Trong C++, teân cuûa haøm maø khoâng coù caëp daáu ngoaëc chính laø con troû chæ ñeán haøm. Thoâng soá hình
thöùc visit döôùi ñaây cuûa phöông thöùc traverse caàn ñöôïc khai baùo nhö moät con troû chæ ñeán haøm.
Ngoaøi ra, khai baùo con troû haøm laøm thoâng soá phaûi coù kieåu traû veà laø void vaø coù thoâng soá tham
chieáu ñeán Entry.
template <class Entry>
void List<Entry>::traverse(void(*visit)(Entry &x));
post: Coâng vieäc ñaëc taû bôûi haøm *visit ñöôïc thöïc hieän laàn löôït treân töøng phaàn töû cuûa danh saùch,
baét ñaàu töø phaàn töû thöù 0.
Cuõng gioáng nhö moïi thoâng soá khaùc, visit chæ laø teân hình thöùc vaø chæ ñöôïc
gaùn bôûi moät con troû thöïc söï khi traverse baét ñaàu thöïc thi. Bieåu dieãn *visit
thay maët cho haøm seõ ñöôïc söû duïng ñeå xöû lyù cho töøng phaàn töû cuûa danh saùch khi
traverse thöïc thi.
Trong phaàn keá tieáp chuùng ta seõ hieän thöïc caùc phöông thöùc naøy.
4.3. Hieän thöïc danh saùch
Chuùng ta ñaõ ñaëc taû ñaày ñuû caùc taùc vuï mong muoán ñoái vôùi danh saùch. Phaàn naøy
seõ hieän thöïc chi tieát chuùng trong C++. Ngaên xeáp vaø haøng ñaõ ñöôïc hieän thöïc caû
hai daïng lieân tuïc vaø lieân keát. Chuùng ta cuõng seõ laøm töông töï cho danh saùch.
4.3.1. Hieän thöïc danh saùch lieân tuïc
Trong hieän thöïc danh saùch lieân tuïc (contiguous list), caùc phaàn töû cuûa danh
saùch coù kieåu laø Entry ñöôïc chöùa trong daõy kích thöôùc laø max_list. Cuõng gioáng
nhö hieän thöïc ngaên xeáp lieân tuïc, ôû ñaây chuùng ta caàn moät bieán count ñeám soá phaàn
töû hieän coù trong danh saùch. Sau ñaây laø ñònh nghóa lôùp List coù hai thuoäc tính
thaønh phaàn vaø taát caû caùc phöông thöùc maø chuùng ta ñaõ ñaëc taû.
template <class Entry>
class List {
public:
// Caùc phöông thöùc cuûa kieåu döõ lieäu tröøu töôïng danh saùch
List();
int size() const;
bool full() const;
bool empty() const;
void clear();
Chöông 4 – Danh saùch
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 55
void traverse(void (*visit)(Entry &));
ErrorCode retrieve(int position, Entry &x) const;
ErrorCode replace(int position, const Entry &x);
ErrorCode remove(int position, Entry &x);
ErrorCode insert(int position, const Entry &x);
protected:
// Caùc thuoäc tính cho hieän thöïc danh saùch lieân tuïc
int count;
Entry entry[max_list];
};
Haàu heát caùc phöông thöùc (List, clear, empty, full, size, retrieve)
raát deã hieän thöïc.
template <class Entry>
int List<Entry>::size() const
/*
post: traû veà soá phaàn töû cuûa danh saùch. Danh saùch khoâng ñoåi.
*/
{
return count;
}
Chuùng ta daønh caùc phöông thöùc ñôn giaûn khaùc laïi cho phaàn baøi taäp. ÔÛ ñaây
chuùng ta seõ taäp trung vaøo caùc phöông thöùc truy xuaát döõ lieäu. Khi theâm moät phaàn
töû môùi, caùc phaàn töû trong daõy phaûi ñöôïc di chuyeån ñeå nhöôøng choã.
template <class Entry>
ErrorCode List<Entry>::insert(int position, const Entry &x)
/*
post: Neáu danh saùch chöa ñaày vaø 0 ≤ position ≤ n, n laø soá phaàn töû hieän coù cuûa danh saùch,
phöông thöùc traû veà success: moïi phaàn töû töø position ñeán cuoái danh saùch seõ coù vò trí
taêng leân 1, x ñöôïc theâm vaøo taïi position; ngöôïc laïi, danh saùch khoâng ñoåi, ErrorCode seõ
cho bieát loãi cuï theå.
*/
{
if (full())
return overflow;
if (position < 0 || position > count)
return range_error;
for (int i = count - 1; i >= position; i--)
entry[i + 1] = entry[i];
entry[position] = x;
count++;
return success;
}
Coù bao nhieâu coâng vieäc maø haøm treân caàn phaûi laøm? Neáu phaàn töû môùi ñöôïc
theâm vaøo cuoái danh saùch thì haøm chæ phaûi thöïc hieän moät soá khoâng ñoåi caùc leänh.
Trong tröôøng hôïp ngöôïc laïi, neáu phaàn töû ñöôïc theâm vaøo ñaàu danh saùch, haøm seõ
phaûi dòch chuyeån moät soá phaàn töû lôùn nhaát ñeå taïo choã troáng, neáu danh saùch ñaõ
