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

MUÏC LUÏC Muïc Trang CHÖÔNG 1: TOÅNG QUAN VEÀ CAÁU TRUÙC DÖÕ LIEÄU & GT ...........3 1.1. Taàm quan troïng cuûa CTDL & GT trong moät ñeà aùn tin hoïc ........................ 3 1.1.1. Xaây döïng caáu truùc döõ lieäu ......................................................................... 3 1.1.2. Xaây döïng giaûi thuaät ................................................................................... 3 1.1.3. Moái quan heä giöõa caáu truùc döõ lieäu vaø giaûi thuaät ....................................... 3 1.2. Ñaùnh giaù Caáu truùc döõ lieäu & Giaûi thuaät ....................................................... 3 1.2.1. Caùc tieâu chuaån ñaùnh giaù caáu truùc döõ lieäu ................................................. 3 1.2.2. Ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùn ........................................................ 4 1.3. Kieåu döõ lieäu ..................................................................................................... 4 1.3.1. Khaùi nieäm veà kieåu döõ lieäu .......................................................................... 4 1.3.2. Caùc kieåu döõ lieäu cô sôû ............................................................................... 4 1.3.3. Caùc kieåu döõ lieäu coù caáu truùc...................................................................... 5 1.3.4. Kieåu döõ lieäu con troû ................................................................................... 5 1.3.5. Kieåu döõ lieäu taäp tin.................................................................................... 5 Caâu hoûi vaø baøi taäp ................................................................................................. 6 CHÖÔNG 2: KYÕ THUAÄT TÌM KIEÁM (Searching) .............................8 2.1. Khaùi quaùt veà tìm kieám .................................................................................... 8 2.2. Caùc giaûi thuaät tìm kieám noäi ........................................................................... 8 2.2.1. Ñaët vaán ñeà ................................................................................................. 8 2.2.2. Tìm tuyeán tính............................................................................................ 8 2.2.3. Tìm nhò phaân ............................................................................................ 10 2.3. Caùc giaûi thuaät tìm kieám ngoaïi ..................................................................... 14 2.3.1. Ñaët vaán ñeà ............................................................................................... 14 2.3.2. Tìm tuyeán tính.......................................................................................... 14 2.3.3. Tìm kieám theo chæ muïc ............................................................................. 16 Caâu hoûi vaø baøi taäp ............................................................................................... 17 CHÖÔNG 3: KYÕ THUAÄT SAÉP XEÁP (SORTING) .............................19 3.1. Khaùi quaùt veà saép xeáp .................................................................................... 19 3.2. Caùc giaûi thuaät saép xeáp noäi ............................................................................ 19 3.2.1 Saép xeáp baèng phöông phaùp ñoåi choã .......................................................... 20 3.2.2. Saép xeáp baèng phöông phaùp choïn ............................................................. 28 3.2.3. Saép xeáp baèng phöông phaùp cheøn ............................................................. 33 3.2.4. Saép xeáp baèng phöông phaùp troän .............................................................. 40 3.3. Caùc giaûi thuaät saép xeáp ngoaïi ........................................................................ 60 3.3.1. Saép xeáp baèng phöông phaùp troän .............................................................. 60 3.3.2. Saép xeáp theo chæ muïc ............................................................................... 79 Caâu hoûi vaø baøi taäp ............................................................................................... 82 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät CHÖÔNG 4: DANH SAÙCH (LIST).....................................................84 4.1. Khaùi nieäm veà danh saùch ............................................................................... 84 4.2. Caùc pheùp toaùn treân danh saùch..................................................................... 84 4.3. Danh saùch ñaëc ............................................................................................... 85 4.3.1. Ñònh nghóa............................................................................................... 85 4.3.2. Bieåu dieãn danh saùch ñaëc .......................................................................... 85 4.3.3. Caùc thao taùc treân danh saùch ñaëc ............................................................. 85 4.3.4. Öu nhöôïc ñieåm vaø ÖÙng duïng ................................................................... 91 4.4. Danh saùch lieân keát ........................................................................................ 92 4.4.1. Ñònh nghóa............................................................................................... 92 4.4.2. Danh saùch lieân keát ñôn ............................................................................ 92 4.4.3. Danh saùch lieân keát keùp .......................................................................... 111 4.4.4. Öu nhöôïc ñieåm cuûa danh saùch lieân keát .................................................. 135 4.5. Danh saùch haïn cheá...................................................................................... 135 4.5.1. Haøng ñôïi ................................................................................................ 135 4.5.2. Ngaên xeáp ............................................................................................... 142 4.5.3. ÖÙng duïng cuûa danh saùch haïn cheá.......................................................... 147 Caâu hoûi vaø baøi taäp ............................................................................................. 147 CHÖÔNG 5: CAÂY (TREE) ............................................................... 149 5.1. Khaùi nieäm – Bieåu dieãn caây ......................................................................... 149 5.1.1. Ñònh nghóa caây ...................................................................................... 149 5.1.2. Moät soá khaùi nieäm lieân quan ................................................................... 149 5.1.3. Bieåu dieãn caây ......................................................................................... 151 5.2. Caây nhò phaân ............................................................................................... 152 5.2.1. Ñònh nghóa............................................................................................. 152 5.2.2. Bieåu dieãn vaø Caùc thao taùc ..................................................................... 152 5.2.3. Caây nhò phaân tìm kieám ........................................................................... 163 5.3. Caây caân baèng............................................................................................... 188 5.3.1. Ñònh nghóa – Caáu truùc döõ lieäu ............................................................... 188 5.3.2. Caùc thao taùc .......................................................................................... 189 Caâu hoûi vaø baøi taäp ............................................................................................. 227 OÂN TAÄP (REVIEW).......................................................................... 224 Heä thoáng laïi caùc Caáu truùc döõ lieäu vaø caùc Giaûi thuaät ñaõ hoïc .......................... 224 Caâu hoûi vaø Baøi taäp oân taäp toång hôïp ................................................................. 227 TAØI LIEÄU THAM KHAÛO ................................................................. 229 By Hút thuốc lá có hại cho sức khỏe at 9:19 pm, Jun 25, 2007 Trang: 2 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät Chöông 1: TOÅNG QUAN VEÀ CAÁU TRUÙC DÖÕ LIEÄU VAØ GIAÛI THUAÄT 1.1. Taàm quan troïng cuûa caáu truùc döõ lieäu vaø giaûi thuaät trong moät ñeà aùn tin hoïc 1.1.1. Xaây döïng caáu truùc döõ lieäu Coù theå noùi raèng khoâng coù moät chöông trình maùy tính naøo maø khoâng coù döõ lieäu ñeå xöû lyù. Döõ lieäu coù theå laø döõ lieäu ñöa vaøo (input data), döõ lieäu trung gian hoaëc döõ lieäu ñöa ra (output data). Do vaäy, vieäc toå chöùc ñeå löu tröõ döõ lieäu phuïc vuï cho chöông trình coù yù nghóa raát quan troïng trong toaøn boä heä thoáng chöông trình. Vieäc xaây döïng caáu truùc döõ lieäu quyeát ñònh raát lôùn ñeán chaát löôïng cuõng nhö coâng söùc cuûa ngöôøi laäp trình trong vieäc thieát keá, caøi ñaët chöông trình. 1.1.2. Xaây döïng giaûi thuaät Khaùi nieäm giaûi thuaät hay thuaät giaûi maø nhieàu khi coøn ñöôïc goïi laø thuaät toaùn duøng ñeå chæ phöông phaùp hay caùch thöùc (method) ñeå giaûi quyeát vaàn ñeà. Giaûi thuaät coù theå ñöôïc minh hoïa baèng ngoân ngöõ töï nhieân (natural language), baèng sô ñoà (flow chart) hoaëc baèng maõ giaû (pseudo code). Trong thöïc teá, giaûi thuaät thöôøng ñöôïc minh hoïa hay theå hieän baèng maõ giaû töïa treân moät hay moät soá ngoân ngöõ laäp trình naøo ñoù (thöôøng laø ngoân ngöõ maø ngöôøi laäp trình choïn ñeå caøi ñaët thuaät toaùn), chaúng haïn nhö C, Pascal, … Khi ñaõ xaùc ñònh ñöôïc caáu truùc döõ lieäu thích hôïp, ngöôøi laäp trình seõ baét ñaàu tieán haønh xaây döïng thuaät giaûi töông öùng theo yeâu caàu cuûa baøi toaùn ñaët ra treân cô sôû cuûa caáu truùc döõ lieäu ñaõ ñöôïc choïn. Ñeå giaûi quyeát moät vaán ñeà coù theå coù nhieàu phöông phaùp, do vaäy söï löïa choïn phöông phaùp phuø hôïp laø moät vieäc maø ngöôøi laäp trình phaûi caân nhaéc vaø tính toaùn. Söï löïa choïn naøy cuõng coù theå goùp phaàn ñaùng keå trong vieäc giaûm bôùt coâng vieäc cuûa ngöôøi laäp trình trong phaàn caøi ñaët thuaät toaùn treân moät ngoân ngöõ cuï theå. 1.1.3. Moái quan heä giöõa caáu truùc döõ lieäu vaø giaûi thuaät Moái quan heä giöõa caáu truùc döõ lieäu vaø Giaûi thuaät coù theå minh hoïa baèng ñaúng thöùc: Caáu truùc döõ lieäu + Giaûi thuaät = Chöông trình Nhö vaäy, khi ñaõ coù caáu truùc döõ lieäu toát, naém vöõng giaûi thuaät thöïc hieän thì vieäc theå hieän chöông trình baèng moät ngoân ngöõ cuï theå chæ laø vaán ñeà thôøi gian. Khi coù caáu truùc döõ lieäu maø chöa tìm ra thuaät giaûi thì khoâng theå coù chöông trình vaø ngöôïc laïi khoâng theå coù Thuaät giaûi khi chöa coù caáu truùc döõ lieäu. Moät chöông trình maùy tính chæ coù theå ñöôïc hoaøn thieän khi coù ñaày ñuû caû Caáu truùc döõ lieäu ñeå löu tröõ döõ lieäu vaø Giaûi thuaät xöû lyù döõ lieäu theo yeâu caàu cuûa baøi toaùn ñaët ra. 1.2. Ñaùnh giaù caáu truùc döõ lieäu vaø giaûi thuaät 1.2.1. Caùc tieâu chuaån ñaùnh giaù caáu truùc döõ lieäu Ñeå ñaùnh giaù moät caáu truùc döõ lieäu chuùng ta thöôøng döïa vaøo moät soá tieâu chí sau: - Caáu truùc döõ lieäu phaûi tieát kieäm taøi nguyeân (boä nhôù trong), Trang: 3 By Hút thuốc lá có hại cho sức khỏe at 9:19 pm, Jun 25, 2007 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät - Caáu truùc döõ lieäu phaûi phaûn aûnh ñuùng thöïc teá cuûa baøi toaùn, - Caáu truùc döõ lieäu phaûi deã daøng trong vieäc thao taùc döõ lieäu. 1.2.2. Ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùn Vieäc ñaùnh giaù ñoä phöùc taïp cuûa moät thuaät toaùn quaû khoâng deã daøng chuùt naøo. ÔÛ daây, chuùng ta chæ muoán öôùc löôïng thôøi gian thöïc hieän thuaän toaùn T(n) ñeå coù theå coù söï so saùnh töông ñoái giöõa caùc thuaät toaùn vôùi nhau. Trong thöïc teá, thôøi gian thöïc hieän moät thuaät toaùn coøn phuï thuoäc raát nhieàu vaøo caùc ñieàu kieän khaùc nhö caáu taïo cuûa maùy tính, döõ lieäu ñöa vaøo, …, ôû ñaây chuùng ta chæ xem xeùt treân möùc ñoä cuûa löôïng döõ lieäu ñöa vaøo ban ñaàu cho thuaät toaùn thöïc hieän. Ñeå öôùc löôïng thôøi gian thöïc hieän thuaät toaùn chuùng ta coù theå xem xeùt thôøi gian thöïc hieän thuaät toaùn trong hai tröôøng hôïp: - Trong tröôøng hôïp toát nhaát: Tmin - Trong tröôøng hôïp xaáu nhaát: Tmax Töø ñoù chuùng ta coù theå öôùc löôïng thôøi gian thöïc hieän trung bình cuûa thuaät toaùn: Tavg 1.3. Kieåu döõ lieäu 1.3.1. Khaùi nieäm veà kieåu döõ lieäu Kieåu döõ lieäu T coù theå xem nhö laø söï keát hôïp cuûa 2 thaønh phaàn: - Mieàn giaù trò maø kieåu döõ lieäu T coù theå löu tröõ: V, - Taäp hôïp caùc pheùp toaùn ñeå thao taùc döõ lieäu: O. T = Moãi kieåu döõ lieäu thöôøng ñöôïc ñaïi dieän bôûi moät teân (ñònh danh). Moãi phaàn töû döõ lieäu coù kieåu T seõ coù giaù trò trong mieàn V vaø coù theå ñöôïc thöïc hieän caùc pheùp toaùn thuoäc taäp hôïp caùc pheùp toaùn trong O. Ñeå löu tröõ caùc phaàn töû döõ lieäu naøy thöôøng phaûi toán moät soá byte(s) trong boä nhôù, soá byte(s) naøy goïi laø kích thöôùc cuûa kieåu döõ lieäu. 1.3.2. Caùc kieåu döõ lieäu cô sôû Haàu heát caùc ngoân ngöõ laäp trình ñeàu coù cung caáp caùc kieåu döõ lieäu cô sôû. Tuøy vaøo moãi ngoân ngöõ maø caùc kieåu döõ lieäu cô sôû coù theå coù caùc teân goïi khaùc nhau song chung quy laïi coù nhöõng loaïi kieåu döõ lieäu cô sôû nhö sau: - Kieåu soá nguyeân: Coù theå coù daáu hoaëc khoâng coù daáu vaø thöôøng coù caùc kích thöôùc sau: + Kieåu soá nguyeân 1 byte + Kieåu soá nguyeân 2 bytes + Kieåu soá nguyeân 4 bytes Kieåu soá nguyeân thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, -, *, /, DIV, MOD, <, >, <=, >=, =, …} Trang: 4 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät - Kieåu soá thöïc: Thöôøng coù caùc kích thöôùc sau: + Kieåu soá thöïc 4 bytes + Kieåu soá thöïc 6 bytes + Kieåu soá thöïc 8 bytes + Kieåu soá thöïc 10 bytes Kieåu soá thöïc thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, -, *, /, <, >, <=, >=, =, …} - Kieåu kyù töï: Coù theå coù caùc kích thöôùc sau: + Kieåu kyù töï byte + Kieåu kyù töï 2 bytes Kieåu kyù töï thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, -, <, >, <=, >=, =, ORD, CHR, …} - Kieåu chuoãi kyù töï: Coù kích thöôùc tuøy thuoäc vaøo töøng ngoân ngöõ laäp trình Kieåu chuoãi kyù töï thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, &, <, >, <=, >=, =, Length, Trunc, …} - Kieåu luaän lyù: Thöôøng coù kích thöôùc 1 byte Kieåu luaän lyù thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {NOT, AND, OR, XOR, <, >, <=, >=, =, …} 1.3.3. Caùc kieåu döõ lieäu coù caáu truùc Kieåu döõ lieäu coù caáu truùc laø caùc kieåu döõ lieäu ñöôïc xaây döïng treân cô sôû caùc kieåu döõ lieäu ñaõ coù (coù theå laïi laø moät kieåu döõ lieäu coù caáu truùc khaùc). Tuøy vaøo töøng ngoân ngöõ laäp trình song thöôøng coù caùc loaïi sau: - Kieåu maûng hay coøn goïi laø daõy: kích thöôùc baèng toång kích thöôùc cuûa caùc phaàn töû - Kieåu baûn ghi hay caáu truùc: kích thöôùc baèng toång kích thöôùc caùc thaønh phaàn (Field) 1.3.4. Kieåu döõ lieäu con troû Caùc ngoân ngöõ laäp trình thöôøng cung caáp cho chuùng ta moät kieåu döõ lieäu ñaëc bieät ñeå löu tröõ caùc ñòa chæ cuûa boä nhôù, ñoù laø con troû (Pointer). Tuøy vaøo loaïi con troû gaàn (near pointer) hay con troû xa (far pointer) maø kieåu döõ lieäu con troû coù caùc kích thöôùc khaùc nhau: + Con troû gaàn: 2 bytes + Con troû xa: 4 bytes 1.3.5. Kieåu döõ lieäu taäp tin Taäp tin (File) coù theå xem laø moät kieåu döõ lieäu ñaëc bieät, kích thöôùc toái ña cuûa taäp tin tuøy thuoäc vaøo khoâng gian ñóa nôi löu tröõ taäp tin. Vieäc ñoïc, ghi döõ lieäu tröïc tieáp treân taäp tin raát maát thôøi gian vaø khoâng baûo ñaûm an toaøn cho döõ lieäu treân taäp tin ñoù. Do vaäy, trong thöïc teá, chuùng ta khoâng thao taùc tröïc tieáp döõ lieäu treân taäp tin maø chuùng ta caàn chuyeån töøng phaàn hoaëc toaøn boä noäi dung cuûa taäp tin vaøo trong boä nhôù trong ñeå xöû lyù. Trang: 5 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät Caâu hoûi vaø Baøi taäp 1. Trình baøy taàm quan troïng cuûa Caáu truùc döõ lieäu vaø Giaûi thuaät ñoái vôùi ngöôøi laäp trình? 2. Caùc tieâu chuaån ñeå ñaùnh giaù caáu truùc döõ lieäu vaø giaûi thuaät? 3. Khi xaây döïng giaûi thuaät coù caàn thieát phaûi quan taâm tôùi caáu truùc döõ lieäu hay khoâng? Taïi sao? 4. Lieät keâ caùc kieåu döõ lieäu cô sôû, caùc kieåu döõ lieäu coù caáu truùc trong C, Pascal? 5. Söû duïng caùc kieåu döõ lieäu cô baûn trong C, haõy xaây döïng caáu truùc döõ lieäu ñeå löu tröõ trong boä nhôù trong (RAM) cuûa maùy tính ña thöùc coù baäc töï nhieân n (0 ≤ n ≤ 100) treân tröôøng soá thöïc (ai , x ∈ R): n fn ( x ) = ∑ aix i i=0 Vôùi caáu truùc döõ lieäu ñöôïc xaây döïng, haõy trình baøy thuaät toaùn vaø caøi ñaët chöông trình ñeå thöïc hieän caùc coâng vieäc sau: - Nhaäp, xuaát caùc ña thöùc. - Tính giaù trò cuûa ña thöùc taïi giaù trò x0 naøo ñoù. - Tính toång, tích cuûa hai ña thöùc. 6. Töông töï nhö baøi taäp 5. nhöng ña thöùc trong tröôøng soá höõu tyû Q (caùc heä soá ai vaø x laø caùc phaân soá coù töû soá vaø maãu soá laø caùc soá nguyeân). 7. Cho baûng giôø taøu ñi töø ga Saigon ñeán caùc ga nhö sau (ga cuoái laø ga Haø noäi): TAØU ÑI S2 S4 S6 S8 S10 S12 S14 S16 S18 LH2 SN2 HAØNH TRÌNH 32 giôø 41 giôø 41 giôø 41 giôø 41 giôø 41 giôø 41 giôø 41 giôø 41 giôø 27giôø 10g30 SAIGON ÑI 21g00 21g50 11g10 15g40 10g00 12g30 17g00 20g00 22g20 13g20 18g40 2g10 5g01 15g21 18g06 19g53 22g47 14g07 16g43 16g41 19g19 21g04 0g08 1g15 4g05 3g16 6g03 17g35 20g19 22g58 2g15 6g47 20g00 0g47 18g50 21g10 1g57 5g42 8g06 22g46 5g15 9g43 23g09 3g39 21g53 0g19 5g11 8g36 10g50 2g10 11g49 1g20 5g46 0g00 2g30 7g09 10g42 13g00 4g15 15g41 4g55 6g11 9g24 10g39 3g24 4g38 5g55 7g10 11g21 12g40 14g35 16g08 17g04 18g21 7g34 9g03 10g53 15g10 MÖÔNG MAÙN THAÙP CHAØM NHA TRANG 4g10 TUY HOØA DIEÂU TRÌ 8g12 QUAÛNG NGAÕI TAM KYØ ÑAØ NAÜNG HUEÁ 13g27 16g21 19g04 22g42 8g29 12g29 12g20 15g47 6g19 11g12 9g26 14g32 14g41 18g13 17g43 21g14 20g17 23g50 ÑOÂNG HAØ ÑOÀNG HÔÙI 19g15 0g14 2g27 13g52 15g52 17g12 19g46 12g42 14g41 16g05 17g59 19g38 21g38 22g39 0g52 1g25 3g28 VINH 23g21 THANH HOÙA NINH BÌNH NAM ÑÒNH PHUÛ LYÙ ÑEÁN HAØ NOÄI 5g00 7g45 21g00 1g08 20g12 23g50 2g59 7g07 9g20 10g44 12g04 12g37 13g23 0g01 1g28 2g01 2g42 4g33 5g54 6g26 7g08 23g09 0g31 1g24 2g02 3g33 4g50 5g22 6g00 6g39 7g57 8g29 9g09 9g59 11g12 11g44 12g23 12g20 13g51 14g25 15g06 14g40 4g00 8g30 3g15 7g10 10g25 13g45 16g20 Söû duïng caùc kieåu döõ lieäu cô baûn, haõy xaây döïng caáu truùc döõ lieäu thích hôïp ñeå löu tröõ baûng giôø taøu treân vaøo boä nhôù trong vaø boä nhôù ngoaøi (disk) cuûa maùy tính. Vôùi caáu truùc döõ lieäu ñaõ ñöôïc xaây döïng ôû treân, haõy trình baøy thuaät toaùn vaø caøi ñaët chöông trình ñeå thöïc hieän caùc coâng vieäc sau: - Xuaát ra giôø ñeán cuûa moät taøu T0 naøo ñoù taïi moät ga G0 naøo ñoù. Trang: 6 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät - Xuaát ra giôø ñeán caùc ga cuûa moät taøu T0 naøo ñoù. - Xuaát ra giôø caùc taøu ñeán moät ga G0 naøo ñoù. - Xuaát ra baûng giôø taøu theo maãu ôû treân. Löu yù: - Caùc oâ troáng ghi nhaän taïi caùc ga ñoù, taøu naøy khoâng ñi ñeán hoaëc chæ ñi qua maø khoâng döøng laïi. - Doøng “HAØNH TRÌNH” ghi nhaän toång soá giôø taøu chaïy töø ga Saigon ñeán ga Haø noäi. 8. Töông töï nhö baøi taäp 7. nhöng chuùng ta caàn ghi nhaän theâm thoâng tin veà ñoaøn taøu khi döøng taïi caùc ga chæ ñeå traùnh taøu hay ñeå cho khaùch leân/xuoáng (caùc doøng in nghieâng töông öùng vôùi caùc ga coù khaùch leân/xuoáng, caùc doøng khaùc chæ döøng ñeå traùnh taøu). 9. Söû duïng kieåu döõ lieäu caáu truùc trong C, haõy xaây döïng caáu truùc döõ lieäu ñeå löu tröõ trong boä nhôù trong (RAM) cuûa maùy tính traïng thaùi cuûa caùc coät ñeøn giao thoâng (coù 3 ñeøn: Xanh, Ñoû, Vaøng). Vôùi caáu truùc döõ lieäu ñaõ ñöôïc xaây döïng, haõy trình baøy thuaät toaùn vaø caøi ñaët chöông trình ñeå moâ phoûng (minh hoïa) cho hoaït ñoäng cuûa 2 coät ñeøn treân hai tuyeán ñöôøng giao nhau taïi moät ngaõ tö. 10. Söû duïng caùc kieåu döõ lieäu cô baûn trong C, haõy xaây döïng caáu truùc döõ lieäu ñeå löu tröõ trong boä nhôù trong (RAM) cuûa maùy tính traïng thaùi cuûa moät baøn côø CARO coù kích thöôùc M×N (0 ≤ M, N ≤ 20). Vôùi caáu truùc döõ lieäu ñöôïc xaây döïng, haõy trình baøy thuaät toaùn vaø caøi ñaët chöông trình ñeå thöïc hieän caùc coâng vieäc sau: - In ra maøn hình baøn côø CARO trong traïng thaùi hieän haønh. - Kieåm tra xem coù ai thaéng hay khoâng? Neáu coù thì thoâng baùo “Keát thuùc”, neáu khoâng coù thì thoâng baùo “Tieáp tuïc”. Trang: 7 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät Chöông 2: KYÕ THUAÄT TÌM KIEÁM (SEARCHING) 2.1. Khaùi quaùt veà tìm kieám Trong thöïc teá, khi thao taùc, khai thaùc döõ lieäu chuùng ta haàu nhö luùc naøo cuõng phaûi thöïc hieän thao taùc tìm kieám. Vieäc tìm kieám nhanh hay chaäm tuøy thuoäc vaøo traïng thaùi vaø traät töï cuûa döõ lieäu treân ñoù. Keát quaû cuûa vieäc tìm kieám coù theå laø khoâng coù (khoâng tìm thaáy) hoaëc coù (tìm thaáy). Neáu keát quaû tìm kieám laø coù tìm thaáy thì nhieàu khi chuùng ta coøn phaûi xaùc ñònh xem vò trí cuûa phaàn töû döõ lieäu tìm thaáy laø ôû ñaâu? Trong phaïm vi cuûa chöông naøy chuùng ta tìm caùch giaûi quyeát caùc caâu hoûi naøy. Tröôùc khi ñi vaøo nghieân cöùu chi tieát, chuùng ta giaû söû raèng moãi phaàn töû döõ lieäu ñöôïc xem xeùt coù moät thaønh phaàn khoùa (Key) ñeå nhaän dieän, coù kieåu döõ lieäu laø T naøo ñoù, caùc thaønh phaàn coøn laïi laø thoâng tin (Info) lieân quan ñeán phaàn töû döõ lieäu ñoù. Nhö vaäy moãi phaàn töû döõ lieäu coù caáu truùc döõ lieäu nhö sau: typedef struct DataElement { T Key; InfoType Info; } DataType; Trong taøi lieäu naøy, khi noùi tôùi giaù trò cuûa moät phaàn töû döõ lieäu chuùng ta muoán noùi tôùi giaù trò khoùa (Key) cuûa phaàn töû döõ lieäu ñoù. Ñeå ñôn giaûn, chuùng ta giaû söû raèng moãi phaàn töû döõ lieäu chæ laø thaønh phaàn khoùa nhaän dieän. Vieäc tìm kieám moät phaàn töû coù theå dieãn ra treân moät daõy/maûng (tìm kieám noäi) hoaëc dieãn ra treân moät taäp tin/ file (tìm kieám ngoaïi). Phaàn töû caàn tìm laø phaàn töû caàn thoûa maõn ñieàu kieän tìm kieám (thöôøng coù giaù trò baèng giaù trò tìm kieám). Tuøy thuoäc vaøo töøng baøi toaùn cuï theå maø ñieàu kieän tìm kieám coù theå khaùc nhau song chung quy vieäc tìm kieám döõ lieäu thöôøng ñöôïc vaän duïng theo caùc thuaät toaùn trình baøy sau ñaây. 2.2. Caùc giaûi thuaät tìm kieám noäi (Tìm kieám treân daõy/maûng) 2.2.1. Ñaët vaán ñeà Giaû söû chuùng ta coù moät maûng M goàm N phaàn töû. Vaán ñeà ñaët ra laø coù hay khoâng phaàn töû coù giaù trò baèng X trong maûng M? Neáu coù thì phaàn töû coù giaù trò baèng X laø phaàn töû thöù maáy trong maûng M? 2.2.2. Tìm tuyeán tính (Linear Search) Thuaät toaùn tìm tuyeán tính coøn ñöôïc goïi laø Thuaät toaùn tìm kieám tuaàn töï (Sequential Search). a. Tö töôûng: Laàn löôït so saùnh caùc phaàn töû cuûa maûng M vôùi giaù trò X baét ñaàu töø phaàn töû ñaàu tieân cho ñeán khi tìm ñeán ñöôïc phaàn töû coù giaù trò X hoaëc ñaõ duyeät qua heát taát caû caùc phaàn töû cuûa maûng M thì keát thuùc. Trang: 8 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät b. Thuaät toaùn: B1: k = 1 //Duyeät töø ñaàu maûng B2: IF M[k] ≠ X AND k ≤ N //Neáu chöa tìm thaáy vaø cuõng chöa duyeät heát maûng B2.1: k++ B2.2: Laëp laïi B2 B3: IF k ≤ N Tìm thaáy taïi vò trí k B4: ELSE Khoâng tìm thaáy phaàn töû coù giaù trò X B5: Keát thuùc c. Caøi ñaët thuaät toaùn: Haøm LinearSearch coù prototype: int LinearSearch (T M[], int N, T X); Haøm thöïc hieän vieäc tìm kieám phaàn töû coù giaù trò X treân maûng M coù N phaàn töû. Neáu tìm thaáy, haøm traû veà moät soá nguyeân coù giaù trò töø 0 ñeán N-1 laø vò trí töông öùng cuûa phaàn töû tìm thaáy. Trong tröôøng hôïp ngöôïc laïi, haøm traû veà giaù trò –1 (khoâng tìm thaáy). Noäi dung cuûa haøm nhö sau: int LinearSearch (T M[], int N, T X) { int k = 0; while (M[k] != X && k < N) k++; if (k < N) return (k); return (-1); } d. Phaân tích thuaät toaùn: - Tröôøng hôïp toát nhaát khi phaàn töû ñaàu tieân cuûa maûng coù giaù trò baèng X: Soá pheùp gaùn: Gmin = 1 Soá pheùp so saùnh: Smin = 2 + 1 = 3 - Tröôøng hôïp xaáu nhaát khi khoâng tìm thaáy phaàn töû naøo coù giaù trò baèng X: Soá pheùp gaùn: Gmax = 1 Soá pheùp so saùnh: Smax = 2N+1 - Trung bình: Soá pheùp gaùn: Gavg = 1 Soá pheùp so saùnh: Savg = (3 + 2N + 1) : 2 = N + 2 e. Caûi tieán thuaät toaùn: Trong thuaät toaùn treân, ôû moãi böôùc laëp chuùng ta caàn phaûi thöïc hieän 2 pheùp so saùnh ñeå kieåm tra söï tìm thaáy vaø kieåm soaùt söï heát maûng trong quaù trình duyeät maûng. Chuùng ta coù theå giaûm bôùt 1 pheùp so saùnh neáu chuùng ta theâm vaøo cuoái maûng moät phaàn töû caàm canh (sentinel/stand by) coù giaù trò baèng X ñeå nhaän dieän ra söï heát maûng khi duyeät maûng, khi ñoù thuaät toaùn naøy ñöôïc caûi tieán laïi nhö sau: Trang: 9 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät B1: k = 1 B2: M[N+1] = X //Phaàn töû caàm canh B3: IF M[k] ≠ X B3.1: k++ B3.2: Laëp laïi B3 B4: IF k < N Tìm thaáy taïi vò trí k B5: ELSE //k = N song ñoù chæ laø phaàn töû caàm canh Khoâng tìm thaáy phaàn töû coù giaù trò X B6: Keát thuùc Haøm LinearSearch ñöôïc vieát laïi thaønh haøm LinearSearch1 nhö sau: int LinearSearch1 (T M[], int N, T X) { int k = 0; M[N] = X; while (M[k] != X) k++; if (k < N) return (k); return (-1); } f. Phaân tích thuaät toaùn caûi tieán: - Tröôøng hôïp toát nhaát khi phaàn töû ñaàu tieân cuûa maûng coù giaù trò baèng X: Soá pheùp gaùn: Gmin = 2 Soá pheùp so saùnh: Smin = 1 + 1 = 2 - Tröôøng hôïp xaáu nhaát khi khoâng tìm thaáy phaàn töû naøo coù giaù trò baèng X: Soá pheùp gaùn: Gmax = 2 Soá pheùp so saùnh: Smax = (N+1) + 1 = N + 2 - Trung bình: Soá pheùp gaùn: Gavg = 2 Soá pheùp so saùnh: Savg = (2 + N + 2) : 2 = N/2 + 2 - Nhö vaäy, neáu thôøi gian thöïc hieän pheùp gaùn khoâng ñaùng keå thì thuaät toaùn caûi tieán seõ chaïy nhanh hôn thuaät toaùn nguyeân thuûy. 2.2.3. Tìm nhò phaân (Binary Search) Thuaät toaùn tìm tuyeán tính toû ra ñôn giaûn vaø thuaän tieän trong tröôøng hôïp soá phaàn töû cuûa daõy khoâng lôùn laém. Tuy nhieân, khi soá phaàn töû cuûa daõy khaù lôùn, chaúng haïn chuùng ta tìm kieám teân moät khaùch haøng trong moät danh baï ñieän thoaïi cuûa moät thaønh phoá lôùn theo thuaät toaùn tìm tuaàn töï thì quaû thöïc maát raát nhieàu thôøi gian. Trong thöïc teá, thoâng thöôøng caùc phaàn töû cuûa daõy ñaõ coù moät thöù töï, do vaäy thuaät toaùn tìm nhò phaân sau ñaây seõ ruùt ngaén ñaùng keå thôøi gian tìm kieám treân daõy ñaõ coù thöù töï. Trong thuaät toaùn naøy chuùng ta giaû söû caùc phaàn töû trong daõy ñaõ coù thöù töï taêng (khoâng giaûm daàn), töùc laø caùc phaàn töû ñöùng tröôùc luoân coù giaù trò nhoû hôn hoaëc baèng (khoâng lôùn hôn) phaàn töû ñöùng sau noù. Khi ñoù, neáu X nhoû hôn giaù trò phaàn töû ñöùng ôû giöõa daõy (M[Mid]) thì X chæ coù theå tìm Trang: 10