Mục lục cấu trúc dữ liệu và giải thuật | Cấu trúc dữ liệu và giải thuật

Muïc luïc MUÏC LUÏC
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...............................1 1.2.
Giôùi thieäu moân hoïc Caáu truùc döõ lieäu (CTDL) vaø giaûi thuaät .....................1 1.3.
Caùch tieáp caän trong quaù trình tìm hieåu caùc lôùp CTDL ............................4 1.3.1.
Caùc böôùc trong quaù trình phaân tích thieát keá höôùng ñoái töôïng.........4 1.3.2.
Quaù trình xaây döïng caùc lôùp CTDL ......................................................5 1.4.
Moät soá ñònh nghóa cô baûn ...........................................................................6 1.4.1.
Ñònh nghóa kieåu döõ lieäu .......................................................................6 1.4.2.
Kieåu nguyeân toá vaø caùc kieåu coù caáu truùc...............................................6 1.4.3.
Chuoãi noái tieáp vaø danh saùch................................................................6 1.4.4.
Caùc kieåu döõ lieäu tröøu töôïng..................................................................7 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..............................................................................................................8 1.5.1.
Caùch tieáp caän vaø phöông höôùng suy nghó tích cöïc ............................8 1.5.2. Caùc nguyeân
taéc......................................................................................9 1.5.3.
Phong caùch laäp trình (style of programming) vaø caùc kyõ naêng:.......10 1.6.
Giôùi thieäu veà ngoân ngöõ giaû: ......................................................................14
Phaàn 2 – CAÙC CAÁU TRUÙC DÖÕ LIEÄU
Chöông 2 – NGAÊN XEÁP 2.1.
Ñònh nghóa ngaên xeáp.................................................................................17 2.2.
Ñaëc taû ngaên xeáp.........................................................................................18 2.3.
Caùc phöông aùn hieän thöïc ngaên xeáp..........................................................22 2.4.
Hieän thöïc ngaên xeáp ...................................................................................22 2.4.1.
Hieän thöïc ngaên xeáp lieân tuïc ..............................................................22 2.4.2.
Hieän thöïc ngaên xeáp lieân keát..............................................................25 2.4.3.
Ngaên xeáp lieân keát vôùi söï an toaøn......................................................29 2.4.4.
Ñaëc taû ngaên xeáp lieân keát ñaõ hieäu chænh ...........................................34
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät i Muïc luïc
Chöông 3 – HAØNG ÑÔÏI 3.1.
Ñònh nghóa haøng ....................................................................................... 37 3.2. Ñaëc taû
haøng ............................................................................................... 38 3.3.
Caùc phöông aùn hieän thöïc haøng ................................................................ 41 3.3.1.
Caùc phöông aùn hieän thöïc haøng lieân tuïc ........................................... 41 3.3.2.
Phöông aùn hieän thöïc haøng lieân keát.................................................. 45 3.4. Hieän thöïc
haøng.......................................................................................... 46 3.4.1.
Hieän thöïc haøng lieân tuïc..................................................................... 46 3.4.2.
Hieän thöïc haøng lieân keát .................................................................... 48 3.4.3.
Haøng lieân keát môû roäng ...................................................................... 50
Chöông 4 – DANH SAÙCH 4.1.
Ñònh nghóa danh saùch .............................................................................. 51 4.2.
Ñaëc taû caùc phöông thöùc cho danh saùch ................................................... 51 4.3.
Hieän thöïc danh saùch................................................................................. 54 4.3.1.
Hieän thöïc danh saùch lieân tuïc............................................................ 54 4.3.2.
Hieän thöïc danh saùch lieân keát ñôn giaûn ........................................... 56 4.3.3.
Löu laïi vò trí hieän taïi......................................................................... 61 4.3.4.
Danh saùch lieân keát keùp ..................................................................... 63 4.4.
So saùnh caùc caùch hieän thöïc cuûa danh saùch ............................................. 66 4.5.
Danh saùch lieân keát trong maûng lieân tuïc ................................................. 67 4.5.1. Phöông
phaùp....................................................................................... 67 4.5.2.
Caùc taùc vuï quaûn lyù vuøng nhôù............................................................. 70 4.5.3.
Caùc taùc vuï khaùc .................................................................................. 73 4.5.4.
Caùc bieán theå cuûa danh saùch lieân keát trong maûng lieân tuïc ............. 74
Chöông 5 – CHUOÃI KYÙ TÖ 5.1.
Chuoãi kyù töï trong C vaø trong C++........................................................... 75 5.2.
Ñaëc taû cuûa lôùp String ................................................................................ 77 5.2.1.
Caùc pheùp so saùnh ............................................................................... 77 5.2.2. Moät soá
constructor tieän duïng ............................................................ 77 5.3.
Hieän thöïc lôùp String ................................................................................. 79 5.4.
Caùc taùc vuï treân String .............................................................................. 81 5.5.
Caùc giaûi thuaät tìm moät chuoãi con trong moät chuoãi................................. 83 5.5.1.
Giaûi thuaät Brute-Force ...................................................................... 83 5.5.2.
Giaûi thuaät Knuth-Morris-Pratt ......................................................... 85
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät ii Muïc luïc
Chöông 6 – ÑEÄ QUY 6.1.
Giôùi thieäu veà ñeä quy ..................................................................................91 6.1.1.
Cô caáu ngaên xeáp cho caùc laàn goïi haøm...............................................91 6.1.2.
Caây bieåu dieãn caùc laàn goïi haøm ..........................................................92 6.1.3.
Giai thöøa: Moät ñònh nghóa ñeä quy.....................................................93 6.1.4.
Chia ñeå trò: Baøi toaùn Thaùp Haø Noäi...................................................95 6.2.
Caùc nguyeân taéc cuûa ñeä quy......................................................................100 6.2.1.
Thieát keá giaûi thuaät ñeä quy ...............................................................100 6.2.2.
Caùch thöïc hieän cuûa ñeä quy...............................................................102 6.2.3.
Ñeä quy ñuoâi .......................................................................................104 6.2.4.
Phaân tích moät soá tröôøng hôïp neân vaø khoâng neân duøng ñeä quy .....106 6.2.5. Caùc nhaän
xeùt.....................................................................................110 6.3.
Phöông phaùp quay lui (backtracking).....................................................112 6.3.1.
Lôøi giaûi cho baøi toaùn taùm con haäu ..................................................112 6.3.2.
Ví duï vôùi boán con Haäu......................................................................114 6.3.3.
Phöông phaùp quay lui (Backtracking) .............................................115 6.3.4.
Phaùc thaûo chung cho chöông trình ñaët caùc con haäu leân baøn côø ...115 6.3.5.
Tinh cheá: Caáu truùc döõ lieäu ñaàu tieân vaø caùc phöông thöùc...............118 6.3.6.
Xem xeùt laïi vaø tinh cheá ...................................................................120 6.3.7.
Phaân tích veà phöông phaùp quay lui ................................................124 6.4.
Caùc chöông trình coù caáu truùc caây: döï ñoaùn tröôùc trong caùc troø chôi ...127 6.4.1.
Caùc caây troø chôi ................................................................................127 6.4.2.
Phöông phaùp Minimax.....................................................................128 6.4.3.
Phaùt trieån giaûi thuaät ........................................................................130 6.4.4. Tinh
cheá ............................................................................................131
6.4.5. Tic-Tac-Toe........................................................................................132
Chöông 7 – TÌM KIEÁM 7.1. Giôùi
thieäu..................................................................................................137
7.1.1. Khoùa...................................................................................................137 7.1.2. Phaân
tích...........................................................................................137 7.1.3.
Tìm kieám noäi vaø tìm kieám ngoaïi ....................................................137 7.1.4.
Lôùp Record vaø lôùp Key.....................................................................138 7.1.5. Thoâng
soá............................................................................................139 7.2.
Tìm kieám tuaàn töï.....................................................................................139
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät iii Muïc luïc 7.2.1.
Giaûi thuaät vaø haøm............................................................................ 139 7.2.2. Phaân
tích .......................................................................................... 140 7.3.
Tìm kieám nhò phaân ................................................................................. 141 7.3.1.
Danh saùch coù thöù töï......................................................................... 142 7.3.2.
Xaây döïng giaûi thuaät ......................................................................... 143 7.3.3.
Phieân baûn thöù nhaát.......................................................................... 143 7.3.4.
Nhaän bieát sôùm phaàn töû coù chöùa khoùa ñích .................................... 145 7.4.
Caây so saùnh ............................................................................................. 147
Chöông 8 – SAÉP XEÁP 8.1. Giôùi
thieäu ................................................................................................. 149 8.2.
Saép xeáp kieåu cheøn (Insertion Sort)........................................................ 150 8.2.1.
Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï..................................... 150 8.2.2.
Saép xeáp kieåu cheøn cho danh saùch lieân tuïc..................................... 151 8.2.3.
Saép xeáp kieåu cheøn cho danh saùch lieân keát .................................... 153 8.3.
Saép xeáp kieåu choïn (Selection Sort)........................................................ 155 8.3.1. Giaûi
thuaät.......................................................................................... 155 8.3.2.
Saép xeáp choïn treân danh saùch lieân tuïc............................................ 156
8.4. Shell_sort................................................................................................. 158 8.5.
Caùc phöông phaùp saép xeáp theo kieåu chia ñeå trò ................................... 160 8.5.1.
YÙ töôûng cô baûn ................................................................................. 160 8.5.2. Ví
duï.................................................................................................. 161 8.6.
Merge_sort cho danh saùch lieân keát ....................................................... 164 8.7.
Quick_sort cho danh saùch lieân tuïc......................................................... 167 8.7.1. Caùc
haøm ............................................................................................ 167 8.7.2. Phaân hoaïch danh
saùch .................................................................... 168 8.8.
Heap vaø Heap_sort.................................................................................. 170 8.8.1.
Ñònh nghóa heap nhò phaân.............................................................. 171 8.8.2.
Phaùt trieån giaûi thuaät Heap_sort ..................................................... 172 8.9. Radix
Sort................................................................................................ 176 8.9.1. YÙ
töôûng.............................................................................................. 177 8.9.2. Hieän
thöïc .......................................................................................... 177 8.9.3.
Phaân tích phöông phaùp radix_sort................................................. 181
Chöông 9 – CAÂY NHÒ PHAÂN 9.1.
Caùc khaùi nieäm cô baûn veà caây ................................................................. 183
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät iv Muïc luïc 9.2. Caây nhò
phaân ...........................................................................................185 9.2.1. Caùc ñònh
nghóa..................................................................................185 9.2.2.
Duyeät caây nhò phaân ..........................................................................187 9.2.3.
Hieän thöïc lieân keát cuûa caây nhò phaân ..............................................193 9.3.
Caây nhò phaân tìm kieám...........................................................................197 9.3.1.
Caùc danh saùch coù thöù töï vaø caùc caùch hieän thöïc .............................198 9.3.2.
Tìm kieám treân caây............................................................................199 9.3.3.
Theâm phaàn töû vaøo caây nhò phaân tìm kieám ....................................203 9.3.4.
Saép thöù töï theo caây ..........................................................................206 9.3.5.
Loaïi phaàn töû trong caây nhò phaân tìm kieám ...................................207 9.4.
Xaây döïng moät caây nhò phaân tìm kieám ...................................................210 9.4.1.
Thieát keá giaûi thuaät ...........................................................................212 9.4.2.
Caùc khai baùo vaø haøm main..............................................................213 9.4.3.
Theâm moät nuùt ...................................................................................214 9.4.4.
Hoaøn taát coâng vieäc............................................................................215 9.4.5. Ñaùnh
giaù............................................................................................217 9.5.
Caân baèng chieàu cao: Caây AVL ................................................................218 9.5.1. Ñònh
nghóa ........................................................................................218 9.5.2.
Theâm moät nuùt ...................................................................................222 9.5.3. Loaïi moät
nuùt .....................................................................................230 9.5.4.
Chieàu cao cuûa caây AVL.....................................................................234
Chöông 10 – CAÂY NHIEÀU NHAÙNH 10.1.
Vöôøn caây, caây, vaø caây nhò phaân..............................................................237 10.1.1.
Caùc teân goïi cho caây...........................................................................237 10.1.2.
Caây coù thöù töï.....................................................................................239 10.1.3.
Röøng vaø vöôøn ....................................................................................241 10.1.4.
Söï töông öùng hình thöùc....................................................................243 10.1.5. Pheùp
quay..........................................................................................244 10.1.6. Toång
keát ............................................................................................244 10.2.
Caây töø ñieån tìm kieám: Trie .....................................................................245
10.2.1. Tries...................................................................................................245 10.2.2.
Tìm kieám moät khoùa..........................................................................245 10.2.3.
Giaûi thuaät C++..................................................................................246 10.2.4.
Tìm kieám trong caây Trie..................................................................247 10.2.5.
Theâm phaàn töû vaøo Trie ....................................................................247 10.2.6.
Loaïi phaàn töû trong Trie ...................................................................248
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät v Muïc luïc 10.2.7. Truy xuaát
Trie .................................................................................. 248 10.3.
Tìm kieám ngoaøi: B-tree .......................................................................... 249 10.3.1.
Thôøi gian truy xuaát .......................................................................... 249 10.3.2.
Caây tìm kieám nhieàu nhaùnh ............................................................. 250 10.3.3.
Caây nhieàu nhaùnh caân baèng ............................................................. 250 10.3.4.
Theâm phaàn töû vaøo B-tree ................................................................ 251 10.3.5.
Giaûi thuaät C++: tìm kieám vaø theâm vaøo.......................................... 253 10.3.6.
Loaïi phaàn töû trong B-tree ............................................................... 263 10.4. Caây
ñoû-ñen ............................................................................................... 271 10.4.1. Daãn
nhaäp .......................................................................................... 271 10.4.2.
Ñònh nghóa vaø phaân tích ................................................................. 272 10.4.3.
Ñaëc taû caây ñoû ñen............................................................................. 274 10.4.4.
Theâm phaàn töû................................................................................... 276 10.4.5.
Phöông thöùc theâm vaøo. Hieän thöïc .................................................. 279 10.4.6. Loaïi moät
nuùt..................................................................................... 282
Chöông 11 – HAØNG ÖU TIEÂN 11.1.
Ñònh nghóa haøng öu tieân ........................................................................ 283 11.2.
Caùc phöông aùn hieän thöïc haøng öu tieân ................................................. 283 11.3.
Hieän thöïc caùc taùc vuï cô baûn treân heap nhò phaân ................................. 284 11.3.1.
Taùc vuï theâm phaàn töû ....................................................................... 284 11.3.2.
Taùc vuï loaïi phaàn töû .......................................................................... 286 11.4.
Caùc taùc vuï khaùc treân heap nhò phaân ..................................................... 287 11.4.1.
Taùc vuï tìm phaàn töû lôùn nhaát........................................................... 287 11.4.2.
Taùc vuï taêng giaûm ñoä öu tieân ........................................................... 287 11.4.3.
Taùc vuï loaïi moät phaàn töû khoâng ôû ñaàu haøng................................... 288 11.5.
Moät soá phöông aùn khaùc cuûa heap .......................................................... 288
11.5.1. d-heaps.............................................................................................. 288 11.5.2.
Heap leäch traùi (Leftist heap)........................................................... 289 11.5.3. Skew
heap ........................................................................................ 295 11.5.4.
Haøng nhò thöùc (Binomial Queue).................................................... 295
Chöông 12 – BAÛNG VAØ TRUY XUAÁT THOÂNG TIN 12.1.
Daãn nhaäp: phaù vôõ raøo caûn lgn ............................................................... 305 12.2.
Caùc baûng chöõ nhaät .................................................................................. 306 12.2.1.
Thöù töï öu tieân haøng vaø thöù töï öu tieân coät...................................... 306
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät vi Muïc luïc 12.2.2.
Ñaùnh chæ soá cho baûng chöõ nhaät.......................................................307 12.2.3.
Bieán theå: maûng truy xuaát.................................................................308 12.3.
Caùc baûng vôùi nhieàu hình daïng khaùc nhau.............................................308 12.3.1.
Caùc baûng tam giaùc ............................................................................309 12.3.2.
Caùc baûng loài loõm...............................................................................310 12.3.3.
Caùc baûng chuyeån ñoåi ........................................................................311 12.4.
Baûng: Moät kieåu döõ lieäu tröøu töôïng môùi..................................................313 12.4.1. Caùc
haøm.............................................................................................313 12.4.2.
Moät kieåu döõ lieäu tröøu töôïng .............................................................314 12.4.3. Hieän
thöïc...........................................................................................315 12.4.4.
So saùnh giöõa danh saùch vaø baûng.....................................................315 12.5. Baûng
baêm .................................................................................................317 12.5.1.
Caùc baûng thöa ...................................................................................317 12.5.2.
Löïa choïn haøm baêm...........................................................................318 12.5.3.
Phaùc thaûo giaûi thuaät cho caùc thao taùc döõ lieäu trong baûng baêm ....321 12.5.4.
Ví duï trong C++ ................................................................................322 12.5.5.
Giaûi quyeát ñuïng ñoä baèng phöông phaùp ñòa chæ môû ........................323 12.5.6.
Giaûi quyeát ñuïng ñoä baèng phöông phaùp noái keát..............................323 12.6.
Phaân tích baûng baêm ................................................................................331 12.6.1.
Ñieàu ngaïc nhieân veà ngaøy sinh.........................................................331 12.6.2.
Ñeám soá laàn thöû .................................................................................332 12.6.3.
Phaân tích phöông phaùp noái keát.......................................................332 12.6.4.
Phaân tích phöông phaùp ñòa chæ môû.................................................333 12.6.5.
Caùc so saùnh lyù thuyeát.......................................................................334 12.6.6.
Caùc so saùnh thöïc nghieäm.................................................................335 12.7.
Keát luaän: so saùnh caùc phöông phaùp .......................................................336
Chöông 13 – ÑOÀ THÒ 13.1.
Neàn taûng toaùn hoïc ...................................................................................339 13.1.1.
Caùc ñònh nghóa vaø ví duï...................................................................339 13.1.2.
Ñoà thò voâ höôùng ................................................................................340 13.1.3.
Ñoà thò coù höôùng.................................................................................341 13.2.
Bieåu dieãn baèng maùy tính ........................................................................341 13.2.1.
Bieåu dieãn cuûa taäp hôïp ......................................................................342 13.2.2.
Danh saùch keà ....................................................................................344 13.2.3.
Caùc thoâng tin khaùc trong ñoà thò......................................................346 13.3. Duyeät ñoà
thò .............................................................................................346
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät vii Muïc luïc 13.3.1.
Caùc phöông phaùp.............................................................................. 346 13.3.2.
Giaûi thuaät duyeät theo chieàu saâu...................................................... 347 13.3.3.
Giaûi thuaät duyeät theo chieàu roäng.................................................... 348 13.4.
Saép thöù töï topo........................................................................................ 349 13.4.1.
Ñaët vaán ñeà ........................................................................................ 349 13.4.2.
Giaûi thuaät duyeät theo chieàu saâu...................................................... 350 13.4.3.
Giaûi thuaät duyeät theo chieàu roäng.................................................... 352 13.5.
Giaûi thuaät Greedy: Tìm ñöôøng ñi ngaén nhaát ........................................ 353 13.5.1.
Ñaët vaán ñeà ........................................................................................ 353 13.5.2. Phöông
phaùp..................................................................................... 354 13.5.3. Ví
duï.................................................................................................. 356 13.5.4. Hieän
thöïc .......................................................................................... 356 13.6.
Caây phuû toái tieåu....................................................................................... 357 13.6.1.
Ñaët vaán ñeà ........................................................................................ 357 13.6.2. Phöông
phaùp..................................................................................... 359 13.6.3. Hieän
thöïc .......................................................................................... 361 13.6.4.
Kieåm tra giaûi thuaät Prim ................................................................ 362 13.7.
Söû duïng ñoà thò nhö laø caáu truùc döõ lieäu .................................................. 364
Phaàn 3 – CAÙC ÖÙNG DUÏNG CUÛA CAÙC LÔÙP CTDL
Chöông 14 – ÖÙNG DUÏNG CUÛA NGAÊN XEÁP 14.1.
Ñaûo ngöôïc döõ lieäu .................................................................................... 365 14.2.
Phaân tích bieân dòch (parsing) döõ lieäu.................................................... 366 14.3.
Trì hoaõn coâng vieäc................................................................................... 368 14.3.1.
ÖÙng duïng tính trò cuûa bieåu thöùc postfix ......................................... 368 14.3.2.
ÖÙng duïng chuyeån ñoåi bieåu thöùc daïng infix thaønh daïng postfix ... 371 14.4.
Giaûi thuaät quay lui (backtracking) ......................................................... 372 14.4.1.
ÖÙng duïng trong baøi toaùn tìm ñích (goal seeking). ........................ 372 14.4.2.
Baøi toaùn maõ ñi tuaàn vaø baøi toaùn taùm con haäu............................... 375
Chöông 15 – ÖÙNG DUÏNG CUÛA HAØNG ÑÔÏI 15.1. Caùc dòch
vuï .............................................................................................. 377 15.2. Phaân
loaïi.................................................................................................. 377 15.3.
Phöông phaùp saép thöù töï Radix Sort ...................................................... 377
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät viii Muïc luïc 15.4.
Tính trò cho bieåu thöùc prefix...................................................................378 15.5.
ÖÙng duïng pheùp tính treân ña thöùc ..........................................................378 15.5.1.
Muïc ñích cuûa öùng duïng.....................................................................378 15.5.2. Chöông
trình.....................................................................................378 15.5.3.
Caáu truùc döõ lieäu cuûa ña thöùc ............................................................381 15.5.4.
Ñoïc vaø ghi caùc ña thöùc .....................................................................384 15.5.5.
Pheùp coäng ña thöùc ............................................................................385 15.5.6.
Hoaøn taát chöông trình .....................................................................386
Chöông 16 – ÖÙNG DUÏNG XÖÛ LYÙ VAÊN BAÛN 16.1.
Caùc ñaëc taû.................................................................................................387 16.2. Hieän
thöïc..................................................................................................388 16.2.1.
Chöông trình chính ..........................................................................388 16.2.2.
Ñaëc taû lôùp Editor ..............................................................................389 16.2.3.
Nhaän leänh töø ngöôøi söû duïng ............................................................390 16.2.4. Thöïc hieän
leänh..................................................................................390 16.2.5.
Ñoïc vaø ghi taäp tin.............................................................................392 16.2.6.
Cheøn moät haøng .................................................................................393 16.2.7.
Tìm moät chuoãi kyù töï .........................................................................393 16.2.8.
Bieán ñoåi chuoãi kyù töï .........................................................................394
Chöông 17 – ÖÙNG DUÏNG SINH CAÙC HOAÙN VÒ 17.1. YÙ
töôûng .....................................................................................................395 17.2. Tinh
cheá....................................................................................................396 17.3. Thuû tuïc
chung...........................................................................................396 17.4.
Toái öu hoùa caáu truùc döõ lieäu ñeå taêng toác ñoä cho chöông trình sinh caùc
hoaùn vò......................................................................................................397 17.5. Chöông
trình............................................................................................398
Chöông 18 – ÖÙNG DUÏNG DANH SAÙCH LIEÂN KEÁT VAØ BAÛNG BAÊM 18.1.
Giôùi thieäu veà chöông trình Game_Of_Life ............................................401 18.2. Caùc ví
duï...................................................................................................401 18.3. Giaûi
thuaät .................................................................................................402 18.4.
Chöông trình chính cho Game_Of_Life .................................................403
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät ix Muïc luïc 18.4.1.
Phieân baûn thöù nhaát cho lôùp Life .................................................... 404 18.4.2.
Phieân baûn thöù hai vôùi CTDL môùi cho Life .................................... 407
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät x