Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 1: Phần mở đầu

Chöông 1: Giôùi thieäu

Phaàn 1 – PHAÀN MÔÛ ÑAÀU

Chöông 1 – GIÔÙI THIEÄU

1.1. Veà phöông phaùp phaân tích thieát keá höôùng ñoái töôïng

Thoâng thöôøng phaàn quan troïng nhaát cuûa quaù trình phaân tích thieát keá laø chia

vaán ñeà thaønh nhieàu vaán ñeà nhoû deã hieåu vaø chi tieát hôn. Neáu chuùng vaãn coøn khoù

hieåu, chuùng laïi ñöôïc chia nhoû hôn nöõa. Trong baát kyø moät toå chöùc naøo, ngöôøi quaûn

lyù cao nhaát cuõng khoâng theå quan taâm ñeán moïi chi tieát cuõng nhö moïi hoaït ñoäng.

Hoï caàn taäp trung vaøo muïc tieâu vaø caùc nhieäm vuï chính, hoï chia bôùt traùch nhieäm

cho nhöõng ngöôøi coäng söï döôùi quyeàn cuûa hoï. Vieäc laäp trình trong maùy tính cuõng

töông töï. Ngay caû khi döï aùn ñuû nhoû cho moät ngöôøi thöïc hieän töø ñaàu tôùi cuoái, vieäc

chia nhoû coâng vieäc cuõng raát quan troïng. Phöông phaùp phaân tích thieát keá höôùng

ñoái töôïng döïa treân quan ñieåm naøy. Caùi khoù nhaát laø ñònh ra caùc lôùp sao cho moãi

lôùp sau naøy seõ cung caáp caùc ñoái töôïng coù caùc haønh vi ñuùng nhö chuùng ta mong ñôïi.

Vieäc laäp trình giaûi quyeát baøi toaùn lôùn cuûa chuùng ta seõ ñöôïc taäp trung vaøo nhöõng

giaûi thuaät lôùn. Chöông trình khi ñoù ñöôïc xem nhö moät kòch baûn, trong ñoù caùc ñoái

töôïng seõ ñöôïc goïi ñeå thöïc hieän caùc haønh vi cuûa mình vaøo nhöõng luùc caàn thieát.

Chuùng ta khoâng coøn phaûi lo bò maát phöông höôùng vì nhöõng chi tieát vuïn vaët khi

caàn phaûi phaùc thaûo moät kòch baûn ñuùng ñaén, moät khi chuùng ta ñaõ tin töôûng hoaøn

toaøn vaøo khaû naêng hoaøn thaønh nhieäm vuï cuûa caùc lôùp maø chuùng ta ñaõ giao phoù.

Caùc lôùp do ngöôøi laäp trình ñònh nghóa ñoùng vai troø trung taâm trong vieäc hieän

thöïc giaûi thuaät.

1.2. Giôùi thieäu moân hoïc Caáu truùc döõ lieäu (CTDL) vaø giaûi thuaät

Theo quan ñieåm cuûa phaân tích thieát keá höôùng ñoái töôïng, moãi lôùp seõ ñöôïc xaây

döïng vôùi moät soá chöùc naêng naøo ñoù vaø caùc ñoái töôïng cuûa noù seõ tham gia vaøo hoaït

ñoäng cuûa chöông trình. Ñieåm maïnh cuûa höôùng ñoái töôïng laø tính ñoùng kín vaø tính

söû duïng laïi cuûa caùc lôùp. Moãi phaàn meàm bieân dòch cho moät ngoân ngöõ laäp trình naøo

ñoù ñeàu chöùa raát nhieàu thö vieän caùc lôùp nhö vaäy. Chuùng ta thöû ñieåm qua moät soá

lôùp maø ngöôøi laäp trình thöôøng hay söû duïng: caùc lôùp coù nhieäm vuï ñoïc/ ghi ñeå trao

ñoåi döõ lieäu vôùi caùc thieát bò ngoaïi vi nhö ñóa, maùy in, baøn phím,…; caùc lôùp ñoà hoïa

cung caáp caùc chöùc naêng veõ, toâ maøu cô baûn; caùc lôùp ñieàu khieån cho pheùp xöû lyù vieäc

giao tieáp vôùi ngöôøi söû duïng thoâng qua baøn phím, chuoät, maøn hình; caùc lôùp phuïc vuï

caùc giao dòch truyeàn nhaän thoâng tin qua maïng;…Caùc lôùp CTDL maø chuùng ta saép

baøn ñeán cuõng khoâng laø moät tröôøng hôïp ngoaïi leä. Coù theå chia taát caû caùc lôùp naøy

thaønh hai nhoùm chính:

• Caùc lôùp dòch vuï.

• Caùc lôùp coù khaû naêng löu tröõ vaø xöû lyù löôïng döõ lieäu lôùn.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

1/16

Chöông 1: Giôùi thieäu

Nhoùm thöù hai muoán noùi ñeán caùc lôùp CTDL (CTDL). Vaäy coù gì gioáng vaø khaùc

nhau giöõa caùc lôùp CTDL vaø caùc lôùp khaùc?

• Ñieåm gioáng nhau giöõa caùc lôùp CTDL vaø caùc lôùp khaùc: moãi lôùp ñeàu phaûi

thöïc hieän moät soá chöùc naêng thoâng qua caùc haønh vi cuûa caùc ñoái töôïng cuûa

noù. Moät khi chuùng ta ñaõ xaây döïng xong moät lôùp CTDL naøo ñoù, chuùng ta

hoaøn toaøn tin töôûng raèng noù seõ hoaøn thaønh xuaát saéc nhöõng nhieäm vuï maø

chuùng ta ñaõ thieát keá vaø ñaõ giao phoù cho noù. Ñieàu naøy raát khaùc bieät so vôùi

nhöõng taøi lieäu vieát veà CTDL theo quan ñieåm höôùng thuû tuïc tröôùc ñaây: vieäc

xöû lyù döõ lieäu khoâng heà coù tính ñoùng kín vaø tính söû duïng laïi. Tuy veà maët

thöïc thi thì caùc chöông trình nhö theá coù khaû naêng chaïy nhanh hôn,

nhöng chuùng boäc loä raát nhieàu nhöôïc ñieåm: thôøi gian phaùt trieån giaûi thuaät

chính raát chaäm gaây khoù khaên nhieàu cho ngöôøi laäp trình, chöông trình

thieáu tính trong saùng, raát khoù söûa loãi vaø phaùt trieån.

• Ñaëc tröng rieâng cuûa caùc lôùp CTDL: Nhieäm vuï chính cuûa caùc lôùp CTDL laø

naém giöõ döõ lieäu sao cho coù theå ñaùp öùng moãi khi ñöôïc chöông trình yeâu caàu

traû veà moät döõ lieäu cuï theå naøo ñoù maø chöông trình caàn ñeán. Nhöõng thao

taùc cô baûn ñoái vôùi moät CTDL thöôøng laø: theâm döõ lieäu môùi, xoùa boû döõ lieäu

ñaõ coù, tìm kieám, truy xuaát.

Ngoaøi caùc thao taùc döõ lieäu cô baûn, caùc CTDL khaùc nhau seõ khaùc nhau veà caùc

thao taùc boå sung khaùc. Chính vì ñieàu naøy maø khi thieát keá nhöõng giaûi thuaät ñeå

giaûi quyeát caùc baøi toaùn lôùn, ngöôøi ta seõ löïa choïn CTDL naøo laø thích hôïp nhaát.

Chuùng ta thöû xem xeùt moät ví duï thaät ñôn giaûn sau ñaây.

Giaû söû chuùng ta caàn vieát moät chöông trình nhaän vaøo moät daõy caùc con soá, vaø in

chuùng ra theo thöù töï ngöôïc vôùi thöù töï nhaäp vaøo ban ñaàu.

Ñeå giaûi quyeát baøi toaùn naøy, neáu chuùng ta nghó ñeán vieäc phaûi khai baùo caùc bieán ñeå

löu caùc giaù trò nhaäp vaøo nhö theá naøo, vaø sau ñoù laø thöù töï in ra sao ñeå ñaùp öùng yeâu

caàu baøi toaùn, thì döôøng nhö laø chuùng ta ñaõ queân aùp duïng nguyeân taéc laäp trình

höôùng ñoái töôïng: chuùng ta ñaõ phaûi baän taâm ñeán nhöõng vieäc quaù chi tieát. Ñaây chæ

laø moät ví duï voâ cuøng ñôn giaûn, nhöng noù coù theå minh hoïa cho vai troø cuûa CTDL.

Neáu chuùng ta nhôù raèng, vieäc toå chöùc vaø löu döõ lieäu nhö theá naøo laø moät vieäc quaù

chi tieát vaø tæ mæ khoâng neân thöïc hieän vaøo luùc naøy, thì ñoù chính laø luùc chuùng ta ñaõ

böôùc ñaàu hieåu ñöôïc vai troø cuûa caùc lôùp CTDL.

Moân CTDL vaø giaûi thuaät seõ giuùp chuùng ta hieåu roõ veà caùc lôùp CTDL coù saün

trong caùc phaàn meàm. Hôn theá nöõa, trong khi hoïc caùch xaây döïng caùc lôùp CTDL töø

ñôn giaûn ñeán phöùc taïp, chuùng ta seõ naém ñöôïc caùc phöông phaùp cuõng nhö caùc kyõ

naêng thoâng qua moät soá nguyeân taéc chung. Töø ñoù, ngoaøi khaû naêng hieåu roõ ñeå coù

theå löïa choïn moät caùch ñuùng ñaén nhaát nhöõng CTDL coù saün, chuùng ta coøn coù khaû

naêng xaây döïng nhöõng lôùp CTDL phöùc taïp hôn, tinh teá vaø thích hôïp hôn trong

moãi baøi toaùn maø chuùng ta caàn giaûi quyeát. Khaû naêng thöøa keá caùc CTDL coù saün ñeå

phaùt trieån theâm caùc tính naêng mong muoán cuõng laø moät ñieàu ñaùng löu yù.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

2/16

Chöông 1: Giôùi thieäu

Vôùi ví duï treân, nhöõng ai ñaõ töøng tieáp xuùc ít nhieàu vôùi vieäc laäp trình ñeàu khoâng

xa laï vôùi khaùi nieäm “ngaên xeáp”. Ñaây laø moät CTDL ñôn giaûn nhaát nhöng laïi raát

thoâng duïng, vaø dó nhieân chuùng ta seõ coù dòp hoïc kyõ hôn veà noù. ÔÛ ñaây chuùng ta

muoán möôïn noù ñeå minh hoïa, vaø cuõng nhaèm giuùp cho ngöôøi ñoïc laøm quen vôùi moät

phöông phaùp tieáp caän hoaøn toaøn nhaát quaùn trong suoát giaùo trình naøy.

Giaû söû CTDL ngaên xeáp cuûa chuùng ta ñaõ ñöôïc giao cho moät nhieäm vuï laø caát giöõ

nhöõng döõ lieäu vaø traû veà khi coù yeâu caàu, theo moät quy ñònh baát di baát dòch laø döõ

lieäu ñöa vaøo sau phaûi ñöôïc laáy ra tröôùc. Baèng caùch söû duïng CTDL ngaên xeáp,

chöông trình trôû neân heát söùc ñôn giaûn vaø ñöôïc trình baøy baèng ngoân ngöõ giaû nhö

sau:

Laëp cho ñeán khi nhaäp ñuû caùc con soá mong muoán

{

Nhaäp 1 con soá.

Caát vaøo ngaên xeáp con soá vöøa nhaäp.

}

Laëp trong khi maø ngaên xeáp vaãn coøn döõ lieäu

{

Laáy töø ngaên xeáp ra moät con soá.

In soá vöøa laáy ñöôïc.

}

Chuùng ta seõ coù dòp gaëp nhieàu baøi toaùn phöùc taïp hôn maø cuõng caàn söû duïng ñeán

ñaëc tính naøy cuûa ngaên xeáp. Tính ñoùng kín cuûa caùc lôùp giuùp cho chöông trình voâ

cuøng trong saùng. Ñoaïn chöông trình treân khoâng heà cho chuùng ta thaáy ngaên xeáp

ñaõ laøm vieäc vôùi caùc döõ lieäu ñöôïc ñöa vaøo nhö theá naøo, ñoù laø nhieäm vuï maø chuùng ta

ñaõ giao phoù cho noù vaø chuùng ta hoaøn toaøn yeân taâm veà ñieàu naøy. Baèng caùch naøy,

khi ñaõ coù nhöõng CTDL thích hôïp, ngöôøi laäp trình coù theå deã daøng giaûi quyeát caùc

baøi toaùn lôùn. Hoï coù theå yeân taâm taäp trung vaøo nhöõng ñieåm maáu choát ñeå xaây döïng,

tinh cheá giaûi thuaät vaø kieåm loãi.

Treân ñaây chuùng ta chæ vöøa môùi giôùi thieäu veà phaàn CTDL naèm trong noäi dung

cuûa moân hoïc “CTDL vaø giaûi thuaät”. Vaäy giaûi thuaät laø gì? Ñöùng treân quan ñieåm

thieát keá vaø laäp trình höôùng ñoái töôïng, chuùng ta ñaõ hieåu vai troø cuûa caùc lôùp. Vaäy

khi ñaõ coù caùc lôùp roài thì ngöôøi ta caàn xaây döïng kòch baûn cho caùc ñoái töôïng hoaït

ñoäng nhaèm giaûi quyeát baøi toaùn chính. Chuùng ta caàn moät caáu truùc chöông trình ñeå

taïo ra kòch baûn ñoù: vieäc gì laøm tröôùc, vieäc gì laøm sau; vieäc gì chæ laøm trong nhöõng

tình huoáng ñaëc bieät naøo ñoù; vieäc gì caàn laøm laëp laïi nhieàu laàn. Chuùng ta nhaéc ñeán

giaûi thuaät chính laø quay veà vôùi khaùi nieäm cuûa “laäp trình thuû tuïc” tröôùc kia. Ngoaøi

ra, chuùng ta cuõng caàn ñeán giaûi thuaät khi caàn hieän thöïc cho moãi lôùp: xong phaàn

ñaëc taû caùc phöông thöùc - phöông tieän giao tieáp cuûa lôùp vôùi beân ngoaøi - chuùng ta

caàn ñeán khaùi nieäm “laäp trình thuû tuïc” ñeå giaûi quyeát phaàn hieän thöïc beân trong cuûa

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

3/16

Chöông 1: Giôùi thieäu

caùc phöông thöùc naøy. Ñoù laø vieäc chuùng ta phaûi xöû lyù nhöõng döõ lieäu beân trong cuûa

chuùng nhö theá naøo môùi coù theå hoaøn thaønh ñöôïc chöùc naêng maø phöông thöùc phaûi

ñaûm nhieäm.

Nhö vaäy, veà phaàn giaûi thuaät trong moân hoïc naøy, chuû yeáu chuùng ta seõ tìm hieåu

caùc giaûi thuaät maø caùc phöông thöùc cuûa caùc lôùp CTDL duøng ñeán, moät soá giaûi thuaät

saép xeáp tìm kieám, vaø caùc giaûi thuaät trong caùc öùng duïng minh hoïa vieäc söû duïng caùc

lôùp CTDL ñeå giaûi quyeát moät soá baøi toaùn ñoù.

Trong giaùo trình naøy, yù töôûng veà caùc giaûi thuaät seõ ñöôïc trình baøy caën keõ, phaàn

chöông trình duøng ngoân ngöõ C++ hoaëc ngoân ngöõ giaû theo quy öôùc ôû cuoái chöông

naøy. Phaàn ñaùnh giaù giaûi thuaät chæ neâu nhöõng keát quaû ñaõ ñöôïc chöùng minh vaø

kieåm nghieäm, sinh vieân coù theå tìm hieåu kyõ hôn trong caùc saùch tham khaûo.

1.3. Caùch tieáp caän trong quaù trình tìm hieåu caùc lôùp CTDL

1.3.1. Caùc böôùc trong quaù trình phaân tích thieát keá höôùng ñoái töôïng

Quaù trình phaân tích thieát keá höôùng ñoái töôïng khi giaûi quyeát moät baøi toaùn goàm

caùc böôùc nhö sau:

1. Ñònh ra caùc lôùp vôùi caùc chöùc naêng maø chuùng ta mong ñôïi. Coâng vieäc naøy cuõng

gioáng nhö coâng vieäc phaân coâng coâng vieäc cho caùc nhaân vieân cuøng tham gia

moät döï aùn.

2. Giaûi quyeát baøi toaùn baèng caùch löïa choïn caùc giaûi thuaät chính. Ñoù laø vieäc taïo ra

moät moâi tröôøng ñeå caùc ñoái töôïng cuûa caùc lôùp neâu treân töông taùc laãn nhau.

Giaûi thuaät chính ñöôïc xem nhö moät kòch baûn daãn daét caùc ñoái töôïng thöïc hieän

caùc haønh vi cuûa chuùng vaøo nhöõng thôøi ñieåm caàn thieát.

3. Hieän thöïc cho moãi lôùp.

YÙ töôûng chính ôû ñaây naèm ôû böôùc thöù hai, daãu cho caùc lôùp chöa ñöôïc hieän thöïc,

chuùng ta hoaøn toaøn coù theå söû duïng chuùng sau khi ñaõ bieát roõ nhöõng chöùc naêng maø

moãi lôùp seõ phaûi hoaøn thanø h. Trung thaønh vôùi quan ñieåm naøy cuûa höôùng ñoái töôïng,

chuùng ta cuõng seõ neâu ra ñaây phöông phaùp tieáp caän maø chuùng ta seõ söû duïng moät

caùch hoaøn toaøn nhaát quaùn trong vieäc nghieân cöùu vaø xaây döïng caùc lôùp CTDL.

ÖÙng duïng trong chöông 18 veà chöông trình Game Of Life laø moät daãn chöùng veà

caùc böôùc phaân tích thieát keá trong quaù trình xaây döïng neân moät chöông trình. Sinh

vieân coù theå tham khaûo ngay phaàn naøy. Rieâng phaàn 18.4.2 phieân baûn thöù hai cuûa

chöông trình sinh vieân chæ coù theå tham khaûo sau khi ñoïc qua chöông 4 veà danh

saùch vaø chöông 12 veà baûng baêm.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

4/16

Chöông 1: Giôùi thieäu

1.3.2. Quaù trình xaây döïng caùc lôùp CTDL

Chuùng ta seõ laàn löôït xaây döïng töø caùc lôùp CTDL ñôn giaûn cho ñeán caùc lôùp

CTDL phöùc taïp hôn. Tuy nhieân, quaù trình thieát keá vaø hieän thöïc cho moïi lôùp

CTDL ñeàu tuaân theo ñuùng caùc böôùc sau ñaây:

1. Xuaát phaùt töø moät moâ hình toaùn hoïc hay döïa vaøo moät nhu caàu thöïc teá naøo

ñoù, chuùng ta ñònh ra caùc chöùc naêng cuûa lôùp CTDL chuùng ta caàn coù. Böôùc naøy

gioáng böôùc thöù nhaát ôû treân, vì lôùp CTDL, cuõng nhö caùc lôùp khaùc, seõ cung caáp

cho chuùng ta caùc ñoái töôïng ñeå hoaït ñoäng trong chöông trình chính. Vaø nhö

vaäy, nhöõng nhieäm vuï maø chuùng ta seõ giao cho noù seõ ñöôïc chæ ra moät caùch roõ

raøng vaø chính xaùc ôû böôùc keá tieáp sau ñaây.

2. Ñaëc taû ñaày ñuû caùch thöùc giao tieáp giöõa lôùp CTDL ñang ñöôïc thieát keá vôùi moâi

tröôøng ngoaøi (caùc chöông trình seõ söû duïng noù). Phaàn giao tieáp naøy ñöôïc moâ

taû thoâng qua ñònh nghóa caùc phöông thöùc cuûa lôùp. Moãi phöông thöùc laø moät

haønh vi cuûa ñoái töôïng CTDL sau naøy, phaàn ñaëc taû goàm caùc yeáu toá sau:

• Kieåu cuûa keát quaû maø phöông thöùc traû veà.

• Caùc thoâng soá vaøo / ra.

• Caùc ñieàu kieän ban ñaàu tröôùc khi phöông thöùc ñöôïc goïi (precondition).

• Caùc keát quaû maø phöông thöùc laøm ñöôïc (postcondition).

• Caùc lôùp, haøm coù söû duïng trong phöông thöùc (uses).

Thoâng qua phaàn ñaëc taû naøy, caùc CTDL hoaøn toaøn coù theå ñöôïc söû duïng trong

vieäc xaây döïng neân nhöõng giaûi thuaät lôùn trong caùc baøi toaùn lôùn. Phaàn ñaëc taû

naøy coù theå ñöôïc xem nhö nhöõng cam keát maø khoâng bao giôø ñöôïc quyeàn thay

ñoåi. Coù nhö vaäy caùc chöông trình coù söû duïng CTDL môùi khoâng bò thay ñoåi

moät khi ñaõ söû duïng chuùng.

3. Tìm hieåu caùc phöông aùn hieän thöïc cho lôùp CTDL. Chuùng ta cuõng neân nhôù

raèng, coù raát nhieàu caùch hieän thöïc khaùc nhau cho cuøng moät ñaëc taû cuûa moät lôùp

CTDL. Veà maët hieäu quaû, coù nhöõng phöông aùn gaàn nhö gioáng nhau, nhöng

cuõng coù nhöõng phöông aùn khaùc nhau raát xa. Ñieàu naøy phuï thuoäc raát nhieàu

vaøo caùch toå chöùc döõ lieäu beân trong baûn thaân cuûa lôùp CTDL, vaøo caùc giaûi

thuaät lieân quan ñeán vieäc xöû lyù döõ lieäu cuûa caùc phöông thöùc.

4. Choïn phöông aùn vaø hieän thöïc lôùp. Trong böôùc naøy bao goàm caû vieäc kieåm tra

ñeå hoaøn taát lôùp CTDL nhö laø moät lôùp ñeå boå sung vaøo thö vieän, ngöôøi laäp

trình coù theå söû duïng chuùng trong nhieàu chöông trình sau naøy. Coâng vieäc ôû

böôùc naøy keå cuõng khaù vaát vaû, vì chuùng ta seõ phaûi kieåm tra thaät kyõ löôõng,

tröôùc khi ñöa saûn phaåm ra nhö nhöõng ñoùng goùi, maø ngöôøi khaùc coù theå hoaøn

toaøn yeân taâm khi söû duïng chuùng.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

5/16

Chöông 1: Giôùi thieäu

Ñeå coù ñöôïc nhöõng saûn phaåm hoaøn haûo thöïc hieän ñuùng nhöõng ñieàu ñaõ cam keát,

böôùc thöù hai treân ñaây ñöôïc xem laø böôùc quan troïng nhaát. Vaø ñeå coù ñöôïc moät ñònh

nghóa vaø moät ñaëc taû ñaày ñuû vaø chính xaùc nhaát cho moät CTDL môùi naøo ñoù, buôùc

thöù hai phaûi ñöôïc thöïc hieän hoaøn toaøn ñoäc laäp vôùi hai böôùc sau noù. Ñaây laø nguyeân

taéc voâ cuøng quan troïng maø chuùng ta seõ phaûi tuaân thuû moät caùch trieät ñeå. Vì trong

tröôøng hôïp ngöôïc laïi, vieäc xem xeùt sôùm caùc chi tieát cuï theå seõ laøm cho chuùng ta deã

coù caùi nhìn phieán dieän, ñieàu naøy deã daãn ñeán nhöõng ñaëc taû mang nhieàu sô suaát.

1.4. Moät soá ñònh nghóa cô baûn

Chuùng ta baét ñaàu baèng ñònh nghóa cuûa moät kieåu döõ lieäu (type):

1.4.1. Ñònh nghóa kieåu döõ lieäu

Ñònh nghóa: Moät kieåu döõ lieäu laø moät taäp hôïp, caùc phaàn töû cuûa taäp hôïp naøy ñöôïc

goïi laø caùc trò cuûa kieåu döõ lieäu.

Chuùng ta coù theå goïi moät kieåu soá nguyeân laø moät taäp caùc soá nguyeân, kieåu soá thöïc

laø moät taäp caùc soá thöïc, hoaëc kieåu kyù töï laø moät taäp caùc kyù hieäu maø chuùng ta mong

muoán söû duïng trong caùc giaûi thuaät cuûa chuùng ta.

Löu yù raèng chuùng ta ñaõ coù theå chæ ra söï phaân bieät giöõa moät kieåu döõ lieäu tröøu

töôïng vaø caùch hieän thöïc cuûa noù. Chaúng haïn, kieåu int trong C++ khoâng phaûi laø taäp

cuûa taát caû caùc soá nguyeân, noù chæ chöùa caùc soá nguyeân ñöôïc bieåu dieãn thöïc söï bôûi

moät maùy tính xaùc ñònh, soá nguyeân lôùn nhaát trong taäp phuï thuoäc vaøo soá bit ngöôøi

ta daønh ñeå bieåu dieãn noù (thöôøng laø moät töø goàm 2 bytes töùc 16 bits). Töông töï, kieåu

float vaø double trong C++ bieåu dieãn moät taäp caùc soá thöïc coù daáu chaám ñoäng naøo

ñoù, vaø ñoù chæ laø moät taäp con cuûa taäp taát caû caùc soá thöïc.

1.4.2. Kieåu nguyeân toá vaø caùc kieåu coù caáu truùc

Caùc kieåu nhö int, float, char ñöôïc goïi laø caùc kieåu nguyeân toá (atomic) vì

chuùng ta xem caùc trò cuûa chuùng chæ laø moät thöïc theå ñôn, chuùng ta khoâng coù mong

muoán chia nhoû chuùng. Tuy nhieân, caùc ngoân ngöõ maùy tính thöôøng cung caáp caùc

coâng cuï cho pheùp chuùng ta xaây döïng caùc kieåu döõ lieäu môùi goïi laø caùc kieåu coù caáu

truùc (structured types). Chaúng haïn nhö moät struct trong C++ coù theå chöùa nhieàu

kieåu nguyeân toá khaùc nhau, trong ñoù khoâng loaïi tröø moät kieåu coù caáu truùc khaùc laøm

thaønh phaàn. Trò cuûa moät kieåu coù caáu truùc cho chuùng ta bieát noù ñöôïc taïo ra bôûi caùc

phaàn töû naøo.

1.4.3. Chuoãi noái tieáp vaø danh saùch

Ñònh nghóa: Moät chuoãi noái tieáp (sequence) kích thöôùc 0 laø moät chuoãi roãng. Moät

chuoãi noái tieáp kích thöôùc n ≥ 1 caùc phaàn töû cuûa taäp T laø moät caëp coù thöù

töï (Sn-1, t), trong ñoù Sn-1 laø moät chuoãi noái tieáp kích thöôùc n – 1 caùc

phaàn töû cuûa taäp T, vaø t laø moät phaàn töû cuûa taäp T.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

6/16

Chöông 1: Giôùi thieäu

Töø ñònh nghóa naøy chuùng ta coù theå taïo neân moät chuoãi noái tieáp daøi tuøy yù, baét

ñaàu töø moät chuoãi noái tieáp roãng vaø theâm moãi laàn moät phaàn töû cuûa taäp T.

Chuùng ta phaân bieät hai töø: noái tieáp (sequential) nguï yù caùc phaàn töû thuoäc moät

chuoãi noái tieáp veà maët luaän lyù, coøn töø lieân tuïc (contiguous) nguï yù caùc phaàn töû naèm

keà nhau trong boä nhôù. Trong ñònh nghóa treân ñaây chuùng ta chæ duøng töø noái tieáp

maø thoâi, chuùng ta chöa heà quan taâm veà maët vaät lyù.

Töø ñònh nghóa chuoãi noái tieáp höõu haïn cho pheùp chuùng ta ñònh nghóa moät danh

saùch (list):

Ñònh nghóa: Moät danh saùch caùc phaàn töû thuoäc kieåu T laø moät chuoãi noái tieáp höõu

haïn caùc phaàn töû kieåu T.

1.4.4. Caùc kieåu döõ lieäu tröøu töôïng

Ñònh nghóa: CTDL (Data Structure) laø moät söï keát hôïp cuûa caùc kieåu döõ lieäu nguyeân

toá, vaø/ hoaëc caùc kieåu döõ lieäu coù caáu truùc, vaø/ hoaëc caùc CTDL khaùc vaøo

moät taäp, cuøng caùc quy taéc veà caùc moái quan heä giöõa chuùng.

Trong ñònh nghóa naøy, caáu truùc coù nghóa laø taäp caùc quy taéc keát noái caùc döõ lieäu

vôùi nhau. Maët khaùc, ñöùng treân quan ñieåm cuûa höôùng ñoái töôïng, chuùng ta seõ xaây

döïng moãi CTDL nhö laø moät lôùp maø ngoaøi khaû naêng chöùa döõ lieäu, noù coøn coù caùc

haønh vi ñaëc tröng rieâng, ñoù chính laø caùc thao taùc cho pheùp caäp nhaäp, truy xuaát

caùc giaù trò döõ lieäu cho töøng ñoái töôïng. Nhôø ñoù, chuùng ta coù ñöôïc moät khaùi nieäm

môùi: kieåu döõ lieäu tröøu töôïng (abstract data type), thöôøng vieát taét laø ADT.

Nguyeân taéc quan troïng ôû ñaây laø moät ñònh nghóa cuûa baát kyø moät kieåu döõ lieäu

tröøu töôïng naøo cuõng goàm hai phaàn: phaàn thöù nhaát moâ taû caùch maø caùc phaàn töû

trong kieåu lieân quan ñeán nhau, phaàn thöù hai laø söï lieät keâ caùc thao taùc coù theå thöïc

hieän treân caùc phaàn töû cuûa kieåu döõ lieäu tröøu töôïng ñoù.

Löu yù raèng khi ñònh nghóa cho moät kieåu döõ lieäu tröøu töôïng chuùng ta hoaøn toaøn

khoâng quan taâm ñeán caùch hieän thöïc cuûa noù. Moät ñònh nghóa cho moät kieåu döõ lieäu

tröøu töôïng phuï thuoäc vaøo nhöõng nhieäm vuï maø chuùng ta troâng ñôïi noù phaûi thöïc

hieän ñöôïc. Döôùi ñaây laø moät soá vaán ñeà chuùng ta thöôøng hay xem xeùt:

• Coù quan taâm ñeán thöù töï theâm vaøo cuûa caùc phaàn töû hay khoâng?

• Vieäc truy xuaát phaàn töû phuï thuoäc thöù töï theâm vaøo cuûa caùc phaàn töû, hay coù

theå truy xuaát phaàn töû baát kyø döïa vaøo khoùa cho tröôùc?

• Vieäc tìm kieám phaàn töû theo khoùa, neáu ñöôïc pheùp, laø hoaøn toaøn nhö nhau

ñoái vôùi baát kyø khoùa naøo, hay phuï thuoäc vaøo thöù töï khi theâm vaøo, hay phuï

thuoäc vaøo taàn suaát maø khoùa ñöôïc truy xuaát?

• …

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

7/16

Chöông 1: Giôùi thieäu

Moät ñaëc taû cho moät kieåu döõ lieäu tröøu töôïng hoaøn toaøn coù theå coù nhieàu caùch

hieän thöïc khaùc nhau. Moãi caùch hieän thöïc mang laïi tính khaû thi vaø tính hieäu quaû

khaùc nhau. Ñieàu naøy phuï thuoäc vaøo yeâu caàu veà thôøi gian vaø khoâng gian cuûa baøi

toaùn. Nhöng caàn nhaán maïnh raèng, moïi caùch hieän thöïc cuûa moät kieåu döõ lieäu tröøu

töôïng ñeàu luoân trung thaønh vôùi ñaëc taû ban ñaàu veà caùc chöùc naêng cuûa noù.

Nhieäm vuï cuûa chuùng ta trong vieäc hieän thöïc CTDL trong C++ laø baét ñaàu töø

nhöõng khaùi nieäm, thöôøng laø ñònh nghóa cuûa moät ADT, sau ñoù tinh cheá daàn ñeå coù

ñöôïc hieän thöïc baèng moät lôùp trong C++. Caùc phöông thöùc cuûa lôùp trong C++ töông

öùng moät caùch töï nhieân vôùi caùc thao taùc döõ lieäu treân ADT, trong khi nhöõng thaønh

phaàn döõ lieäu cuûa lôùp trong C++ töông öùng vôùi CTDL vaät lyù maø chuùng ta choïn ñeå

bieåu dieãn ADT.

1.5. Moät soá nguyeân taéc vaø phöông phaùp ñeå hoïc toát moân CTDL vaø giaûi

thuaät

1.5.1. Caùch tieáp caän vaø phöông höôùng suy nghó tích cöïc

Moãi CTDL ñeàu ñöôïc trình baøy theo ñuùng caùc böôùc sau ñaây:

• Ñònh nghóa lôùp.

• Ñaëc taû lôùp.

• Phaân tích caùc phöông aùn hieän thöïc.

• Hieän thöïc lôùp.

•

Löu yù raèng, söï tröøu töôïng vaø ñaëc taû döõ lieäu phaûi luoân ñi tröôùc söï löïa choïn

caùch thöùc toå chöùc löu tröõ döõ lieäu vaø caùch hieän thöïc chuùng.

Trong phaàn ñònh nghóa vaø ñaëc taû lôùp, ñeå coù theå hieåu saâu vaán ñeà vaø caûm thaáy

höùng thuù hôn, sinh vieân neân töï xem mình laø moät trong nhöõng ngöôøi tham gia vaøo

coâng vieäc thieát keá. Vì chöùc naêng cuûa lôùp hoaøn toaøn phuï thuoäc vaøo quan ñieåm cuûa

ngöôøi thieát keá. Neáu chuùng ta giôùi haïn cho moãi lôùp CTDL moät soá chöùc naêng thao

taùc döõ lieäu cô baûn nhaát, chuùng ta coù moät thö vieän goïn nheï. Ngöôïc laïi, thö vieän seõ

raát lôùn, nhöng ngöôøi laäp trình coù theå goïi thöïc hieän baát cöù coâng vieäc naøo maø hoï

muoán töø nhöõng phöông thöùc ñaõ coù saün cuûa moãi lôùp. Thö vieän caùc lôùp CTDL trong

VC++ laø moät minh hoïa cho thaáy moãi lôùp CTDL coù saün raát nhieàu phöông thöùc ñaùp

öùng ñöôïc nhu caàu cuûa nhieàu ngöôøi duøng khaùc nhau.

Caùc phöông thöùc ñöôïc ñaëc taû kyõ caøng cho moãi lôùp trong giaùo trình naøy cuõng

chæ laø ñeå minh hoïa. Sinh vieân coù theå töï yù choïn löïa ñeå ñaëc taû moät soá phöông thöùc

boå sung khaùc theo yù muoán.

Tröôùc khi tìm hieåu caùc phöông aùn hieän thöïc ñöôïc trình baøy trong giaùo trình

daønh cho moãi lôùp CTDL, sinh vieân cuõng neân töï phaùc hoïa theo suy nghó cuûa rieâng

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

8/16

Chöông 1: Giôùi thieäu

baûn thaân mình. Vôùi caùch chuû ñoäng nhö vaäy, sinh vieân seõ deã daøng nhìn ra caùc öu

nhöôïc ñieåm trong töøng phöông aùn. Vaø neáu coù ñöôïc nhöõng yù töôûng hoaøn toaøn môùi

meû so vôùi nhöõng gì ñöôïc trình baøy trong giaùo trình, sinh vieân seõ töï tin hôn khi

caàn giaûi quyeát caùc baøi toaùn. Nhöõng CTDL nhaèm phuïc vuï cho caùc baøi toaùn lôùn ñoâi

khi ñöôïc hình thaønh töø söï gheùp noái cuûa moät soá CTDL ñôn giaûn. Chính söï gheùp

noái naøy laøm naûy sinh voâ vaøn phöông aùn khaùc nhau maø chuùng ta phaûi choïn löïa

thaät thaän troïng, ñeå baûo ñaûm tính khaû thi vaø hieäu quaû cuûa chöông trình. Moät khi

gaëp moät baøi toaùn caàn giaûi quyeát, neáu sinh vieân bieát choïn cho mình nhöõng phöông

aùn gheùp noái caùc CTDL ñôn giaûn, bieát caùch söû duïng laïi nhöõng gì ñaõ coù trong thö

vieän, vaø bieát caùch laøm theá naøo ñeå hieän thöïc boå sung nhöõng gì thuoäc veà nhöõng yù

töôûng môùi meû vöøa naûy sinh, xem nhö sinh vieân ñaõ hoïc toát moân CTDL vaø giaûi

thuaät.

So vôùi nhieàu giaùo trình khaùc, giaùo trình naøy taùch rieâng phaàn öùng duïng caùc

CTDL nhaèm laøm goïn nheï hôn cho phaàn II laø phaàn chæ trình baøy veà caùc CTDL.

Nhö vaäy seõ thuaän tieän hôn cho sinh vieân trong vieäc tìm hieåu nhöõng phaàn caên baûn

hay laø tra cöùu môû roäng kieán thöùc. Hôn nöõa, coù nhieàu öùng duïng lieân quan ñeán

nhieàu CTDL khaùc nhau.

1.5.2. Caùc nguyeân taéc

1. Tröôùc khi hieän thöïc baát kyø moät lôùp CTDL naøo, chuùng ta caàn chaéc chaén raèng

chuùng ta ñaõ ñònh nghóa CTDL vaø ñaëc taû caùc taùc vuï cho noù moät caùch thaät ñaày

ñuû. Coù nhö vaäy môùi baûo ñaûm ñöôïc raèng:

• Chuùng ta ñaõ hieåu veà noù moät caùch chính xaùc.

• Trong khi hieän thöïc chuùng ta khoâng phaûi quay laïi söûa ñoåi caùc ñaëc taû cuûa

noù, vì vieäc söûa ñoåi naøy coù theå laøm cho chuùng ta maát phöông höôùng, CTDL

seõ khoâng coøn ñuùng nhö nhöõng yù töôûng ban ñaàu maø chuùng ta ñaõ döï ñònh

cho noù.

•

Caùc chöông trình öùng duïng khoâng caàn phaûi ñöôïc chænh söûa moät khi ñaõ söû

duïng CTDL naøy.

• Neáu chuùng ta cung caáp nhieàu hieän thöïc khaùc nhau cho cuøng moät CTDL,

thì khi ñoåi sang söû duïng moät hieän thöïc khaùc, chöông trình öùng duïng

khoâng ñoøi hoûi phaûi ñöôïc chænh söûa laïi. Caùc hieän thöïc khaùc nhau cuûa cuøng

moät CTDL luoân coù cuøng moät giao dieän thoáng nhaát.

2. Moãi phöông thöùc cuûa lôùp luoân coù naêm phaàn moâ taû (kieåu traû veà, thoâng soá vaøo/

ra, precondition, postcondition, uses)

Ñaây laø yeâu caàu chung trong vieäc laäp taøi lieäu cho moät haøm. Caùc CTDL cuûa

chuùng ta seõ ñöôïc söû duïng trong raát nhieàu öùng duïng khaùc nhau. Do ñoù chuùng

ta caàn xaây döïng sao cho ngöôøi laäp trình bôùt ñöôïc moïi coâng söùc coù theå. Lôøi

khuyeân ôû ñaây laø: phaàn precondition chæ nhaèm giaûi thích yù nghóa caùc thoâng soá

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

9/16

Chöông 1: Giôùi thieäu

vaøo, chöù khoâng neân raøng buoäc nhöõng trò hôïp leä maø thoâng soá vaøo phaûi thoaû.

Nhieäm vuï trong phaàn hieän thöïc cuûa phöông thöùc laø chuùng ta phaûi löôøng heát

moïi khaû naêng coù theå coù cuûa thoâng soá vaoø vaø giaûi quyeát thoûa ñaùng töøng tröôøng

hôïp.

Chuùng ta xem caùc CTDL cuõng nhö caùc dòch vuï, chuùng ñöôïc vieát moät

laàn vaø ñöôïc söû duïng trong raát nhieàu öùng duïng khaùc nhau. Do ñoù CTDL

caàn ñöôïc xaây döïng sao cho ngöôøi söû duïng bôùt ñöôïc coâng söùc moïi luùc coù

theå.

Caùc phöông thöùc public cuûa caùc CTDL neân ñöôïc hieän thöïc khoâng coù

precondition.

3. Ñaûm baûo tính ñoùng kín (encapsulation) cuûa lôùp CTDL. Döõ lieäu coù tính ñoùng

kín khi chuùng chæ coù theå ñöôïc truy xuaát bôûi caùc phöông thöùc cuûa lôùp.

Öu ñieåm cuûa vieäc söû duïng moät lôùp coù tính ñoùng kín laø khi chuùng ta ñaëc taû

vaø hieän thöïc caùc phöông thöùc, chuùng ta khoâng phaûi lo laéng ñeán caùc giaù trò

khoâng hôïp leä cuûa caùc döõ lieäu ñang ñöôïc löu trong ñoái töôïng cuûa lôùp.

Caùc thaønh phaàn döõ lieäu cuûa CTDL neân ñöôïc khai baùo private.

4. Ngoaïi tröø caùc constructor coù chuû ñích, moãi ñoái töôïng cuûa CTDL luoân phaûi

ñöôïc khôûi taïo laø moät ñoái töôïng roãng vaø chæ ñöôïc söûa ñoåi bôûi chính caùc

phöông thöùc cuûa lôùp. Vôùi caùc phöông thöùc ñaõ ñöôïc hieän thöïc vaø kieåm tra kyõ

löôõng, chuùng ta luoân an taâm raèng caùc ñoái töôïng CTDL luoân chöùa nhöõng döõ

lieäu hôïp leä. Ñieàu naøy giuùp chuùng luoân hoaøn thaønh nhieäm vuï ñöôïc giao, vaø ñoù

cuõng laø nguyeân taéc cuûa höôùng ñoái töôïng.

1.5.3. Phong caùch laäp trình (style of programming) vaø caùc kyõ naêng:

1. Vaán ñeà xöû lyù loãi:

Vieäc xöû lyù loãi cung caáp moät möùc ñoä an toaøn caàn thieát maø chuùng ta neân

thöïc hieän moïi luùc coù theå trong CTDL cuûa chuùng ta. Coù vaøi caùch khaùc nhau

trong vieäc xöû lyù loãi. Chaúng haïn chuùng ta coù theå in ra thoâng baùo hoaëc ngöng

chöông trình khi gaëp loãi. Hoaëc thay vaøo ñoù, chuùng ta daønh vieäc xöû lyù loãi laïi

cho ngöôøi laäp trình söû duïng CTDL cuûa chuùng ta baèng caùch traû veà caùc maõ loãi

thoâng qua trò traû veà cuûa caùc phöông thöùc. Caùch cuoái cuøng naøy hay hôn vì noù

cung caáp khaû naêng löïa choïn cho ngöôøi laäp trình. Coù nhöõng tình huoáng maø

ngöôøi laäp trình thaáy caàn thieát phaûi ngöng ngay chöông trình, nhöng cuõng coù

nhöõng tình huoáng loãi coù theå boû qua ñeå chöông trình tieáp tuïc chaïy. Baèng caùch

naøy, ngöôøi laäp trình khi söû duïng caùc CTDL hoaøn toaøn coù theå chuû ñoäng ñoái

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

10/16

Chöông 1: Giôùi thieäu

phoù vôùi moïi tình huoáng. Hôn nöõa, caùc CTDL cuûa chuùng ta seõ ñöôïc xaây döïng

nhö laø caùc thö vieän duøng chung cho raát nhieàu chöông trình.

Khi söû duïng moät phöông thöùc cuûa moät lôùp CTDL, ngöôøi laäp trình caàn

phaûi xem xeùt laïi maõ loãi maø phöông thöùc traû veà ñeå xöû lyù loãi khi caàn thieát.

Caùc lôùp CTDL caàn phaûi ñöôïc thieát keá sao cho coù theå cho pheùp ngöôøi laäp

trình choïn löïa caùch thöùc xöû lyù loãi theo yù muoán.

Chuùng ta seõ duøng khai baùo ErrorCode nhö moät kieåu döõ lieäu kieåu lieät keâ

taäp caùc trò töông öùng caùc tình huoáng coù theå xaûy ra khi moät phöông thöùc cuûa

moät lôùp ñöôïc goïi: thaønh coâng hay thaát baïi, traøn boä nhôù, trò thoâng soá khoâng

hôïp leä,… Chuùng ta seõ coá gaéng thieát keá moät caùch thaät nhaát quaùn: haàu heát caùc

phöông thöùc cuûa caùc lôùp traû veà kieåu ErrorCodenaøy.

Söï nhaát quaùn bao giôø cuõng taïo ra thoùi quen raát toát trong phong caùch

laäp trình. Ñieàu naøy tieát kieäm raát nhieàu coâng söùc vaø thôøi gian cuûa ngöôøi laäp

trình.

2. Caùch truyeàn nhaän döõ lieäu giöõa ñoái töôïng CTDL vôùi chöông trình söû duïng

Caùc giao tieáp truyeàn nhaän döõ lieäu khaùc giöõa chöông trình söû duïng vaø caùc

lôùp CTDL dó nhieân cuõng thoâng qua danh saùch caùc thoâng soá. Trong phöông

thöùc cuûa lôùp CTDL seõ khoâng coù vieäc chôø nhaän döõ lieäu tröïc tieáp töø baøn phím.

Chuùng ta neân daønh cho ngöôøi laäp trình quyeàn chuyeån höôùng doøng nhaäp xuaát

döõ lieäu vôùi caùc thieát bò beân ngoaøi nhö baøn phím, maøn hình, taäp tin, maùy in,…

3. Vaán ñeà kieåu cuûa döõ lieäu ñöôïc löu trong CTDL.

Moãi lôùp CTDL maø chuùng ta xaây döïng ñeàu coù tính toång quaùt cao, noù coù theå

chaáp nhaän baát kyø moät kieåu döõ lieäu naøo cho döõ lieäu ñöôïc löu trong noù. Trong

C++ töø khoùa templatecho pheùp chuùng ta laøm ñieàu naøy. Caùc kieåu döõ lieäu naøy

thöôøng ñöôïc yeâu caàu phaûi coù saün moät soá thao taùc caàn thieát nhö so saùnh,

nhaäp, xuaát,…

4. Caùc khai baùo beân trong moät lôùp CTDL.

Lôùp CTDL cung caáp caùc thao taùc döõ lieäu thoâng qua caùc phöông thöùc ñöôïc

khai baùo laø public.

Taát caû nhöõng thuoäc tính vaø caùc haøm coøn laïi luoân ñöôïc khai baùo private

hoaëc protected.

Caùc thuoäc tính cuûa moät lôùp CTDL coù theå ñöôïc phaân laøm hai loaïi:

• Thuoäc tính baét buoäc phaûi coù ñeå löu döõ lieäu.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

11/16

Chöông 1: Giôùi thieäu

• Thuoäc tính maø ñoái töôïng caàn coù ñeå töï quaûn lyù, trong soá naøy coù thuoäc tính

ñöôïc boå sung chæ ñeå ñaåy nhanh toác ñoä cuûa caùc thao taùc döõ lieäu.

Caùc haøm ñöôïc che daáu beân trong lôùp ñöôïc goïi laø caùc haøm phuï trôï (auxilary

function), chuùng chæ ñöôïc söû duïng bôûi chính caùc phöông thöùc cuûa lôùp CTDL

ñoù maø thoâi.

Vieäc môû roäng theâm caùc taùc vuï cho moät lôùp coù saün coù theå theo moät trong

hai caùch:

• Boå sung theâm phöông thöùc môùi.

• Xaây döïng lôùp thöøa keá.

5. Moät soá höôùng daãn caàn thieát trong vieäc thöû nghieäm chöông trình.

9 Boä chöông trình thöû (driver): Ñaây laø ñoaïn chöông trình thöôøng ñöôïc vieát

trong haøm main vaø chöùa moät thöïc ñôn (menu) cho pheùp thöû moïi phöông

thöùc cuûa lôùp CTDL ñang ñöôïc xaây döïng.

Chuùng ta seõ vieát, thöû nghieäm, vaø hoaøn chænh nhieàu lôùp CTDL khaùc nhau.

Do ñoù ngay töø ñaàu chuùng ta neân xaây dönï g moät driver sao cho toång quaùt, khi

caàn thöû vôùi moät CTDL naøo ñoù chæ caàn chænh söûa laïi ñoâi chuùt maø thoâi.

Trong driver chuùng ta neân chuaån hoùa vieäc ñoïc ghi taäp tin, xöû lyù caùc thao

taùc ñoïc töø baøn phím vaø xuaát ra maøn hình. Phaàn coøn laïi laø moät menu cho

pheùp ngöôøi söû duïng chaïy chöông trình choïn caùc chöùc naêng nhö taïo ñoái

töôïng CTDL môùi, goïi caùc thao taùc theâm, xoùa, tìm kieám, truy xuaát,… treân

CTDL ñoù.

9 Caùc maåu taïm (stub): ñaây laø moät meïo nhoû nhöng raát höõu ích. Ñeå dòch vaø

chaïy thöû moät vaøi phaàn nhoû ñaõ vieát, nhöõng phaàn chöa vieát cuûa chöông trình

seõ ñöôïc taïo nhö nhöõng maåu nhoû vaø chæ caàn hôïp cuù phaùp (Xem öùng duïng

tính toaùn caùc ña thöùc trong chöông 15).

Ví duï: Trong ñoaïn chöông trình naøo ñoù chuùng ta ñang muoán chaïy thöû maø

coù söû duïng lôùp A, haøm B,…, chuùng ta seõ taïm khai baùo caùc stub:

class A

{

}; // Moät lôùp chöa coù thuoäc tính vì chuùng ta chöa quyeát ñònh neân choïn

kieåu

thuoäc tính nhö theá naøo.

void B()

{

} // Moät haøm vôùi thaân haøm coøn roãng maø chuùng ta heïn seõ vieát sau.

Neáu moät haøm ñaõ coù ñònh nghóa thì chæ caàn traû veà sao cho hôïp leä:

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

12/16

Chöông 1: Giôùi thieäu

int C()

{

return 1;

} // chæ caàn caån thaän trong tröôøng hôïp neáu nhö giaù trò traû veà laïi ñöôïc

duøng trong moät bieåu thöùc luaän lyù ñeå xeùt ñieàu kieän laëp voøng thì coù

khaû naêng voøng laëp khoâng ñöôïc thöïc hieän hoaëc laëp voâ taän.

9 Caùch thöùc theo doõi moät chöông trình ñang chaïy hoaëc nhu caàu khaûo saùt caùch

laøm vieäc cuûa moät trình bieân dòch naøo ñoù:

Ví duï gôïi yù:

void D()

{

count << “\n Haøm D ñang ñöôïc goïi \n”;

}

Trong C++ caùc haøm constructor vaø destructor ñöôïc 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. Vaäy neáu coù thaéc maéc veà thöù

töï goïi caùc haøm naøy cuûa moät lôùp thöøa keá töø lôùp khaùc, chuùng ta coù theå duøng

caùch töông töï ñeå vieát trong constructor vaø destructor cuûa töøng lôùp cha, con.

Neáu chuùng ta coù thaéc maéc veà caùch öùng xöû cuûa trình bieân dòch khi goïi caùc

haøm naøy hay caùc haøm ñöôïc ñònh nghóa ñeø (overloaded, overwriten) trong

tröôøng hôïp caùc lôùp thöøa keá laãn nhau, hoaëc moät soá tröôøng hôïp khaùc naøo ñoù,

thì ñaây laø caùch hay nhaát ñeå chuùng ta töï kieåm nghieäm laáy.

Phaàn lôùn caùc giaûi thuaät ñöôïc nghieân cöùu tröôùc heát chæ döïa treân yù töôûng

(bieåu dieãn baèng ngoân ngöõ giaû vaø ñoäc laäp vôùi moïi ngoân ngöõ laäp trình). Tuy

nhieân khi hieän thöïc chuùng ta thöôøng gaëp vöôùng maéc ôû choã moãi ngoân ngöõ

laäp trình coù moät soá ñaëc ñieåm khaùc nhau, vaø ngay caû khi duøng chung moät

ngoân ngöõ, caùc trình bieân dòch khaùc nhau (khaùc haõng saûn xuaát hay khaùc

phieân baûn) ñoâi khi cuõng öùng xöû khaùc nhau. Ñieàu ñoù gaây raát nhieàu khoù khaên

vaø laõng phí thôøi gian cuûa nhieàu sinh vieân.

Chæ caàn laáy moät ví duï ñôn giaûn, ñoù laø vieäc ñoïc ghi file, vieäc thöôøng xuyeân

phaûi caàn ñeán khi muoán thöû nghieäm moät giaûi thuaät naøo ñoù. Caùc voøng laëp

thöôøng nhaàm laãn ôû ñieàu kieän keát thuùc file trong ngoân ngöõ C++, maø ñieàu

naøy hoaøn toaøn phuï thuoäc vaøo vieäc xöû lyù con troû file cuûa trình bieân dòch.

Ngay moät phaàn meàm nhö Visual C++ hieän taïi cuõng chöùa cuøng luùc trong thö

vieän khoâng bieát bao nhieâu lôùp phuïc vuï cho vieäc khai baùo vaø ñoïc ghi file.

Chuùng ta chæ coù theå söû duïng moät trong caùc thö vieän ñoù moät caùch chính xaùc

sau khi ñaõ tìm hieåu thaät kyõ! Moät ví duï khaùc cuõng hay gaây nhöõng loãi maát

raát nhieàu thôøi gian, ñoù laø vieäc so saùnh caùc trò: NULL, ‘0’, ‘\0’, 0, … maø neáu

khoâng khaûo saùt kyõ chuùng ta seõ bò traû giaù bôûi söï chuû quan cho raèng mình ñaõ

hieåu ñuùng quy öôùc cuûa trình bieân dòch.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

13/16

Chöông 1: Giôùi thieäu

Vieäc tìm ñoïc taøi lieäu keøm theo trình bieân dòch laø moät vieäc laøm caàn thieát, noù

cho chuùng ta söï hieåu bieát ñaày ñuû vaø chính xaùc. Nhöng ñeå ruùt ngaén thôøi gian

thì gôïi yù treân ñaây cuõng laø moät lôøi khuyeân quyù baùu. Khoâng gì nhanh vaø

chính xaùc baèng caùch tìm caâu traû lôøi trong thöû nghieäm. Vieäc söûa ñoåi chöông

trình nhö theá naøo ñeå coù ñöôïc caùc stub thoûa nhöõng nhu caàu caàn thöû nghieäm

laø tuøy thuoäc vaøo söï tích cöïc, say meâ vaø saùng taïo cuûa sinh vieân.

9 Gôõ roái chöông trình (debug)

Ñaây laø khaû naêng theo veát chöông trình ôû nhöõng ñoaïn maø ngöôøi laäp trình

coøn nghi ngôø coù loãi. Baát cöù ngöôøi laäp trình naøo cuõng coù luùc caàn phaûi chaïy

debug. Vì vaäy toát hôn heát laø ngay töø ñaàu sinh vieân neân tìm hieåu kyõ caùc khaû

naêng cuûa coâng cuï debug cuûa trình bieân dòch maø mình söû duïng (cho pheùp

theo doõi trò caùc bieán, lòch söû caùc laàn goïi haøm,…).

Moät gôïi yù trong phaàn naøy laø sinh vieân caàn bieát caùch coâ laäp töøng phaàn cuûa

chöông trình ñaõ vieát baèng caùch duøng kyù hieäu daønh cho phaàn chuù thích

(comment) ñeå khoùa bôùt nhöõng phaàn chöa ñeán löôït kieåm tra. Hoaëc khi loãi do

trình bieân dòch baùo coù veû mô hoà, thì caùch coâ laäp baèng caùch giôùi haïn daàn

ñoaïn chöông trình ñang dòch thöû seõ giuùp chuùng ta sôùm xaùc ñònh ñöôïc phaïm

vi coù loãi. Cuõng coù theå laøm ngöôïc laïi, chæ dòch thöû vaø chænh söûa töøng ñoaïn

chöông trình nhoû, cho ñeán khi heát loãi môùi nôùi daàn phaïm vi chöông trình ñeå

dòch tieáp.

1.6. Giôùi thieäu veà ngoân ngöõ giaû:

Phaàn lôùn chöông trình ñöôïc trình baøy trong giaùo trình naøy ñeàu söû duïng ngoân

ngöõ C++, sau khi yù töôûng veà giaûi thuaät ñaõ ñöôïc giaûi thích caën keõ. Phaàn coøn laïi coù

moät soá giaûi thuaät ñöôïc trình baøy baèng ngoân ngöõ giaû.

Ngoân ngöõ giaû, hay coøn goïi laø maõ giaû (pseudocode), laø moät caùch bieåu dieãn ñoäc

laäp vôùi moïi ngoân ngöõ laäp trình, noù khoâng raøng buoäc sinh vieân vaøo nhöõng cuù phaùp

nghieâm ngaët cuõng nhö caùch goïi sao cho chính xaùc caùc töø khoùa, caùc haøm coù trong

thö vieän moät trình bieân dòch naøo ñoù. Nhôø ñoù sinh vieân coù theå taäp trung vaøo yù

töôûng lôùn cuûa giaûi thuaät.

Caùc quy ñònh veà maõ giaû ñöôïc söû duïng trong giaùo trình naøy:

¾ Bieåu dieãn söï tuaàn töï cuûa caùc leänh chöông trình: caùc leänh ñöôïc thöïc thi tuaàn töï

leänh naøy sang leänh khaùc seõ coù cuøng khoaûng caùch canh leà nhö nhau vaø ñöôïc

ñaùnh soá thöù töï taêng daàn, luoân baét ñaàu töø 1.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

14/16

Chöông 1: Giôùi thieäu

¾ Caáu truùc khoái loàng nhau: moät khoái naèm trong moät khoái khaùc seõ coù khoaûng

caùch canh leà lôùn hôn.

Trong giaùo trình naøy, chæ nhöõng phaàn ñöôïc trình baøy baèng maõ giaû môùi coù soá

thöù töï ôû ñaàu moãi doøng leänh.

Ví duï:

1.

2.

1. // Ñaây laø doøng leänh coù soá thöù töï laø 1.2.1

2.

3.

2.

1.

3.

1.

2.

¾ Söï reõ nhaùnh: chuùng ta söû duïng caùc töø khoùa:

• if<bieåu thöùc luaän lyù>

…

endif

• if<bieåu thöùc luaän lyù>

…

else

…

endif

• case

case1: …

case2: …

case3: …

else:

…

endcase

¾ Söï laëp voøng:

• loop<bieåu thöùc luaän lyù>

…

endloop// laëp trong khi bieåu thöùc luaän lyù coøn ñuùng.

• repeat

…

until <bieåu thöùc luaän lyù> // laëp cho ñeán khi bieåu thöùc luaän lyù

ñuùng.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

15/16

Chöông 1: Giôùi thieäu

¾ Khai baùo haøm:

<kieåu traû veà> teân haøm (danh saùch thoâng soá)

trong ñoù danh saùch thoâng soá: val/ ref<teân kieåu> teân thoâng soá, val/ ref

<teân kieåu> teân thoâng soá,…

val: daønh cho tham trò; ref: daønh cho tham bieán.

¾ Khai baùo caáu truùc, lôùp:

structteân kieåu döõ lieäu caáu truùc

end struct

class teân kieåu döõ lieäu caáu truùc

end class

¾ Khai baùo phöông thöùc cuûa lôùp:

<kieåu traû veà> teân lôùp::teân haøm (danh saùch thoâng soá);

¾ Khai baùo bieán:

<teân kieåu> teân bieán

Moät chuùt löu yù veà caùch trình baøy trong giaùo trình:

Do caùc ñoaïn chöông trình söû duïng font chöõ Courier New, neân caùc teân bieán,

teân lôùp, teân ñoái töôïng, teân caùc haøm khi ñöôïc nhaéc ñeán cuõng duøng font chöõ naøy.

Caùc töø tieáng Anh khaùc ñöôïc in nghieâng. Ñaëc bieät nhöõng phaàn coù lieân quan chaët

cheõ ñeán nhöõng ñaëc thuø cuûa ngoân ngöõ laäp trình C++ thöôøng duøng kích côõ chöõ nhoû

hôn, ñeå phaân bieät vôùi nhöõng phaàn quan troïng khaùc khi noùi veà yù töôûng vaø giaûi

thuaät, vaø ñoù môùi laø muïc ñích chính cuûa moân hoïc naøy.

Coù moät soá töø hay ñoaïn ñöôïc in ñaäm hay gaïch döôùi nhaèm giuùp sinh vieân ñoïc deã

daøng hôn.

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät

16/16

Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 1: Phần mở đầu - Chương 1: Giới thiệu