Đồ án Chương trình học Tiếng Nga

lôùn. Neáu döõ lieäu trong heä thoáng ñaõ ñöôïc toå chöùc theo moät traät töï naøo ñoù, thì vieäc tìm kieám seõ tieán haønh nhanh choùng vaø hieäu quaû hôn. Ví duï: caùc töø trong töø ñieån ñöôïc saép xeáp theo töøng vaàn, trong moãi vaàn laïi ñöôïc saép xeáp theo thöù töï baûng chöõ caùi; saùch trong thö vieän ñöôïc xeáp theo chuû ñeà, teân taùc giaû.... Hieän nay ñaõ coù nhieàu giaûi thuaät tìm kieám vaø saép xeáp ñöôïc xaây döïng, möùc ñoä hieäu quaû cuûa töøng giaûi thuaät coøn phuï thuoäc vaøo tính chaát cuûa caáu truùc döõ lieäu cuï theå maø noù taùc ñoäng ñeán. Döõ lieäu ñöôïc löu tröõ chuû yeáu trong boä nhôù chính vaø treân boä nhôù phuï do ñaëc ñieåm khaùc nhau cuûa thieát bò löu tröõ, caùc thuaät toaùn saép xeáp vaø tìm kieám ñöôïc xaây döïng cho caùc caáu truùc löu tröõ treân boä nhôù chính hoaëc phuï cuõng coù nhöõng ñaëc thuø khaùc nhau. Caùc thuaät toaùn saép xeáp ñöôïc phaân thaønh hai nhoùm chính laø: - Saép thöù töï noäi: toaøn boä döõ lieäu caàn saép thöù töï phaûi ñöôïc ñöa vaøo trong boä nhôù chính, neân thôøi gian ñeå saép thöù töï töông ñoái nhanh. - Saép thöù töï ngoaïi: moät phaàn caùc döõ lieäu caàn saép thöù töï ñöôïc ñöa vaøo trong boä nhôù chính, phaàn döõ lieäu coøn laïi ñöôïc löu tröõ ôû treân boä nhôù ngoaøi. Thôøi gian ñeå saép thöù töï töông ñoái chaäm. 1.Moät soá giaûi thuaät saép xeáp. Saép xeáp laø quaù trình xöû lyù moät danh saùch caùc phaàn töû (hoaëc caùc maãu tin) ñeå ñaët chuùng theo moät thöù töï thoûa maõn moät tieâu chuaån naøo ñoù döïa treân noäi dung thoâng tin löu giöõ taïi moãi phaàn töû. Moät soá phöông phaùp saép xeáp thoâng duïng nhö: + Saép xeáp kieåu löïa choïn (Selection Sort) + Saép xeáp kieåu theâm daàn (Insertion Sort) + Saép xeáp kieåu ñoåi choã (Exchange Sort) + Saép xeáp kieåu noåi boït (Bubble Sort) + Saép xeáp kieåu phaân ñoaïn (Quick Sort) + Saép xeáp kieåu vun ñoáng (Heap Sort) + Saép xeáp kieån hoøa nhaäp (Merge Sort) + Saép xeáp vôùi ñoä daøi böôùc giaûm daàn (Shell Sort) + Saép xeáp theo phöông phaùp cô soá (Radix Sort) Nhaän xeùt vaø ñaùnh giaù caùc thuaät toaùn saép xeáp: Phaàn lôùn caùc thuaät toaùn saép xeáp cô baûn döïa treân söï so saùnh giaù trò giöõa caùc phaàn töû. Ñoù laø caùc thuaät toaùn choïn löïa, theâm daàn, noåi boït, ñoåi choã. Caùc thuaät toaùn naøy ñeàu coù moät ñieåm chung laø chi phí thöïc hieän chung laø tæ leä vôùi n2. Caùc thuaät toaùn shell-sort (caûi tieán cuûa phöông phaùp theâm daàn), heap-sort (caûi tieán cuûa phöông phaùp choïn löïa) laïi coù ñoä phöùc taïp nhoû hôn haún caùc thuaät toaùn goác. Thuaät toaùn shell-sort coù ñoä phöùc taïp O(nx) vôùi 1 x 2 vaø thuaät toaùn heap-sort coù ñoä phöùc taïp O(nlog2n). Caùc thuaät toaùn merge-sort vaø quick-sort laø nhöõng thuaät toaùn thöïc hieän theo chieán löôïc chia ñeå trò. Caøi ñaët chuùng tuy phöùc taïp hôn caùc thuaät toaùn khaùc nhöng chi phí thöïc hieän laïi thaáp, caû hai thuaät toaùn ñeàu coù ñoä phöùc taïp O(nlog2n). Merge-sort coù nhöôïc ñieåm laø caàn duøng theâm boä nhôù ñeäm. Thuaät toaùn naøy seõ phaùt huy toát öu ñieåm khi caøi ñaët treân caùc caáu truùc döõ lieäu khaùc phuø hôïp hôn nhö danh saùch lieân keát hay phi. Thuaät toaùn quick-sort ñöôïc ñaùnh giaù laø thuaät toaùn saép xeáp nhanh nhaát trong soá caùc thuaät toaùn saép xeáp döïa treân neàn taûng so saùnh giaù trò cuûa caùc phaàn töû. Tuy coù chi phí trong tröôøng hôïp xaáu nhaát laø O(n) nhöng trong kieåm nghieäm thöïc teá, thuaät toaùn quick-sort chaïy nhanh hôn hai thuaät toaùn cuøng nhoùm O(nlog2n) laø merge-sort vaø heap-sort. Thuaät toaùn Radix-sort laø moät thuaät toaùn ñöôïc phaùt trieån theo höôùng khaùc vôùi caùc thuaät toaùn treân. Noù ñöôïc phaùt trieån döïa treân moâ phoûng qui trình phaân phoái thö cuûa ngöôøi ñöa thö. Thuaät toaùn naøy ñaïi dieän cho nhoùm caùc thuaät toaùn saép xeáp coù ñoä phöùc taïp tuyeán tính. Tuy nhieân, thöôøng thì caùc thuaät toaùn naøy khoâng thích hôïp cho vieäc caøi ñaët treân caáu truùc döõ lieäu maûng moät chieàu. 2. Caùc giaûi thuaät tìm kieám noäi Thoâng thöôøng caùc döõ lieäu ñöôïc phaân chia thaønh caùc baûn ghi, moãi baûn ghi coù moät khoaù ñöôïc söû duïng trong vieäc tìm kieám. Vaán ñeà cuûa vieäc tìm kieám laø tìm taát caû caùc maåu tin coù cuøng khoaù k cho bieát tröôùc ñeå truy xuaát noäi dung cuûa baûn ghi. Coâng vieäc tìm kieám seõ hoaøn thaønh khi coù moät trong hai tình huoáng sau xaûy ra: - Tìm ñöôïc baûn ghi coù giaù trò khoùa töông öùng, luùc ñoù ta noùi: pheùp tìm kieám ñöôïc thoûa. - Khoâng tìm ñöôïc baûn ghi naøo coù giaù trò khoùa töông öùng: pheùp tìm kieám khoâng thoûa. Sau khi pheùp tìm kieám khoâng thoûa coù khi xuaát hieän yeâu caàu boå sung theâm baûn ghi môùi coù khoùa khoâng tìm thaáy vaøo baûng. Giaûi thuaät theå hieän caû yeâu caàu naøy ñöôïc goïi laø giaûi thuaät “Tìm kieám coù boå sung”. Ta coù moät soá thuaät toaùn tìm kieám nhö: + Tìm kieám tuaàn töï + Tìm kieám nhò phaân + Tìm kieám döïa vaøo giaù trò khoùa Nhaän xeùt vaø ñaùnh giaù caùc thuaät toaùn tìm kieám: Giaûi thuaät tìm nhò phaân döïa vaøo quan heä giaù trò cuûa caùc phaàn töû maûng ñeå ñònh höôùng trong quaù trình tìm kieám, do vaäy chæ aùp duïng ñöôïc cho nhöõng daõy ñaõ coù thöù töï. Giaûi thuaät tìm nhò phaân tieát kieäm thôøi gian hôn raát nhieàu so vôùi giaûi thuaät tìm kieám tuaàn töï do Tnhò phaân(n) = O(log2n) Ttuaàn töï(n) = O(n). Tuy nhieân khi muoán aùp duïng giaûi thuaät tìm nhò phaân caàn phaûi xeùt ñeán thôøi gian saép xeáp daõy soá ñeå thoûa ñieàu kieän daõy soá coù thöù töï. Vôùi phöông phaùp tìm kieám döïa vaøo giaù trò khoùa, caùc khoùa coù giaù trò khaùc nhau cuõng coù theå cuøng öùng vôùi moät ñòa chæ vaø hieän töôïng naøy ñöôïc goïi laø hieän töôïng ñuïng ñoä. Vì vaäy khi xeùt phöông phaùp naøy, khoâng nhöõng caàn chuù yù ñeán caùch xaây döïng haøm ñòa chæ maø coøn phaûi xeùt caû tôùi phöông phaùp khaéc phuïc ñuïng ñoä. II.3. CAÁU TRUÙC CAÂY 1. Ñònh nghóa vaø khaùi nieäm * Ñònh nghóa caây Caây laø moät taäp hôïp T roãng hoaëc goàm nhieàu phaàn töû ñöôïc goïi laø nuùt, trong ñoù: - Moät nuùt ñöôïc goïi laø nuùt goác (root). - Caùc nuùt coøn laïi ñöôïc phaân chia thaønh m nhoùm (m>=0), moãi nhoùm laø moät caây vaø ñöôïc goïi laø caây con. Trong ñoù nuùt coù theå ñöôïc xem nhö laø moät phaàn töû cuûa moät danh saùch vaø coù theå coù kieåu baát kyø. Caùc nuùt ñöôïc bieåu dieãn bôûi moät kyù töï chöõ, moät chuoãi, moät soá ghi trong moät voøng troøn. Giöõa caùc nuùt coù moät quan heä phaân caáp goïi laø “quan heä cha con”, caùc nuùt ngay beân treân tröïc tieáp laø nuùt cha, caùc nuùt ngay beân döôùi tröïc tieáp laø caùc con cuûa nuùt ñoù. Moät caây khoâng coù moät nuùt naøo caû goïi laø caây roãng. * Moät soá khaùi nieäm cô baûn - Baäc cuûa moät nuùt: laø soá caây con cuûa nuùt ñoù - Baäc cuûa moät caây: laø baäc lôùn nhaát cuûa caùc nuùt trong caây (soá caây con toái ña cuûa moät nuùt thuoäc caây). Caây coù baäc n thì goïi laø caây n-phaân. - Nuùt goác: laø nuùt khoâng coù nuùt cha. - Nuùt laù: laø nuùt coù baäc baèng 0. - Nuùt nhaùnh: laø nuùt coù baäc khaùc 0 vaø khoâng phaûi laø goác - Röøng caây: laø taäp hôïp nhieàu caây trong ñoù thöù töï caùc caây laø quan troïng. 2. Caùc caùch bieåu dieãn caây Ñeå bieåu dieãn moät caây, ta coù nhieàu caùch: a) Bieåu dieãn caây baèng ñoà thò b) Bieåu dieãn caây baèng giaûn ñoà c) Bieåu dieãn caây baèng caùc daáu ngoaëc loàng nhau d) Bieåu dieãn caây baèng phöông phaùp Indentation e) Bieåu dieãn caây baèng chæ soá 3. Caây nhò phaân * Khaùi nieäm: Caây nhò phaân laø moät daïng quan troïng cuûa caáu truùc caây. Noù coù ñaëc ñieåm laø: moïi nuùt treân caây chæ coù toái ña laø hai caây con (caây con traùi vaø caây con phaûi). Caây nhò phaân laø caây coù thöù töï. 3.1. Bieåu dieãn caây nhò phaân - Löu tröõ keá tieáp: caây ñöôïc löu tröõ baèng moät vectô V vôùi nuùt thöù i cuûa caây ñöôïc löu tröõ ôû V[i]. Vôùi caùch löu tröõ naøy neáu bieát ñöôïc ñòa chæ nuùt cha seõ tính ñöôïc ñòa chæ nuùt con vaø ngöôïc laïi. Tuy nhieân neáu caây nhò phaân khoâng ñaày ñuû thì caùch löu tröõ naøy khoâng thích hôïp vì seõ gaây ra laõng phí do coù nhieàu phaàn töû nhôù boû troáng (öùng vôùi caây con roãng). A B C F D E G Ví duï: Vôùi caây nhò phaân Bieåu dieãn phöông phaùp löu tröõ keá tieáp cuûa caây nhò phaân treân nhö sau: A B C D E EØ G V[1] V[2] V[3] V[4] V[5] V[6] V[7] - Löu tröõ moùc noái: moãi nuùt cuûa caây öùng vôùi moät phaàn töû nhôù goàm ba tröôøng laø: tröôøng INFO öùng vôùi thoâng tin döõ lieäu cuûa nuùt; tröôøng LPTR öùng vôùi con troû troû tôùi caây con traùi cuûa nuùt ñoù; tröôøng RPTR öùng vôùi con troû troû tôùi caây con phaûi cuûa nuùt ñoù. Vôùi caùch bieåu dieãn naøy thì nuùt cha coù theå truy nhaäp vaøo nuùt con deã daøng, nhöng ngöôïc laïi thì khoâng laøm ñöôïc Ví duï: Vôùi caây nhò phaân treân ta coù phöông phaùp löu tröõ moùc noái nhö sau A B C D G E F 3.2. Duyeät caây nhò phaân Coù ba pheùp duyeät khaùc nhau ñoái vôùi caây nhò phaân. - Duyeät theo thöù töï tröôùc: Kieåu duyeät naøy tröôùc tieân thaêm goác sau ñoù thaêm caùc nuùt cuûa caây con traùi roài ñeán caây con phaûi. - Duyeät theo thöù töï giöõa: Kieåu duyeät naøy tröôùc tieân thaêm caùc nuùt cuûa caây con traùi sau ñoù thaêm nuùt goác roài ñeán caây con phaûi. - Duyeät theo thöù töï sau: Kieåu duyeät naøy tröôùc tieân thaêm caùc nuùt cuûa caây con traùi sau ñoù thaêm ñeán caây con phaûi roài cuoái cuøng môùi thaêm nuùt goác. 4. Bieåu dieãn caây toång quaùt baèng caây nhò phaân - Caây toång quaùt: coù ñaëc ñieåm laø moïi nuùt treân caây coù theå coù nhieàu hôn hai caây con. - Nhöôïc ñieåm cuûa caùc caáu truùc caây toång quaùt laø baäc cuûa caùc nuùt treân caây coù theå dao ñoäng trong moät bieân ñoä lôùn, neân vieäc bieåu dieãn gaëp nhieàu khoù khaên vaø laõng phí. Hôn nöõa, vieäc xaây döïng caùc thao taùc treân caây toång quaùt phöùc taïp hôn treân caây nhò phaân nhieàu. Vì vaäy, thöôøng neáu khoâng quaù caàn thieát phaûi söû duïng caây toång quaùt, ngöôøi ta chuyeån caây toång quaùt thaønh caây nhò phaân. Ta coù theå bieán ñoåi moät caây baát kyø thaønh moät caây nhò phaân theo qui taéc sau: + Giöõ laïi nuùt con traùi nhaát laøm nuùt con traùi. + Caùc nuùt con coøn laïi chuyeån thaønh nuùt con phaûi. + Nhö vaäy, trong caây nhò phaân môùi, con traùi theå hieän quan heä cha con vaø con phaûi theå hieän quan heä anh em trong caây toång quaùt ban ñaàu. Khi ñoù caây toång quaùt bieåu dieãn theo qui taéc treân ñöôïc goïi laø caây nhò phaân töông ñöông. B A C E F G D H I J A B E C D G H I J F Ví duï: Caây toång quaùt chuyeån sang caây nhò phaân 5. Caây nhò phaân tìm kieám * Ñònh nghóa: Caây nhò phaân tìm kieám (CNPTK) laø caây nhò phaân trong ñoù taïi moãi nuùt, khoùa cuûa nuùt ñang xeùt lôùn hôn khoùa cuûa taát caû caùc nuùt thuoäc caây con traùi vaø nhoû hôn khoùa cuûa taát caû caùc nuùt thuoäc caây con phaûi. Nhôø raøng buoäc veà khoùa treân CNPTK, vieäc tìm kieám trôû neân coù ñònh höôùng. Hôn nöõa, do caáu truùc caây vieäc tìm kieám trôû neân nhanh ñaùng keå. Neáu soá nuùt treân caây laø N thì chi phí tìm kieám trung bình chæ khoaûng log2N. * Caùc thao taùc treân caây nhò phaân tìm kieám: a) Duyeät caây: Thao taùc duyeät caây treân caây nhò phaân tìm kieám hoaøn toaøn gioáng nhö treân caây nhò phaân. Chæ coù moät löu yù nhoû laø khi duyeät theo thöù töï giöõa, trình töï caùc nuùt duyeät qua seõ cho ta moät daõy caùc nuùt theo thöù töï taêng daàn cuûa khoùa. b) Theâm moät phaàn töû x vaøo caây: Vieäc theâm vaøo phaûi baûo ñaûm ñieàu kieän raøng buoäc cuûa CNPTK. Ta coù theå theâm voøa nhieàu choã khaùc nhau treân caây, nhöng neáu theâm vaøo moät nuùt laù seõ laø tieän lôïi nhaát do ta coù theå thöïc hieän quaù trình töông töï thao taùc tìm kieám. Khi chaám döùt quaù trình tìm kieám cuõng chính laø luùc tìm ñöôïc choã caàn theâm. c) Huûy moät phaàn töû coù khoùa x: Vieäc huûy moät phaàn töû x ra khoûi caây phaûi baûo ñaûm ñieàu kieän raøng buoäc cuûa CNPTK. Coù 3 tröôøng hôïp khi huûy nuùt x coù theå xaûy ra: + x laø nuùt laù: chæ ñôn giaûn huûy x vì noù khoâng moùc noái ñeán phaàn töû naøo khaùc. + x chæ coù 1 con (traùi hoaëc phaûi): tröôùc khi huûy x ta moùc noái cha cuûa x vôùi con duy nhaát cuûa noù. + x coù ñuû caû 2 con: ta khoâng theå huûy tröïc tieáp do x coù ñuû 2 con. Vì vaäy ta seõ huûy giaùn tieáp. Thay vì huûy x, ta seõ tìm moät phaàn töû theá maïng y. Phaàn töû naøy coù toái ña moät con. Thoâng tin löu taïi y seõ ñöôïc chuyeån leân löu taïi x. Sau ñoù, nuùt bò huûy thaät söï seõ laø y gioáng nhö 2 tröôøng hôïp ñaàu. Vaán ñeà laø phaûi choïn y sao cho khi löu y vaøo vò trí cuûa x, caây vaãn laø CNPTK. Coù 2 phaàn töû thoûa maõn yeâu caàu: Phaàn töû nhoû nhaát (traùi nhaát) treân caây con phaûi vaø phaàn töû lôùn nhaát (phaûi nhaát) treân caây con traùi. d) Taïo moät caây CNPTK: Ta coù theå taïo moät caây nhò phaân tìm kieám baèng caùch laëp laïi quaù trình theâm 1 phaàn töû vaøo moät caây roãng. e) Huûy toaøn boä CNPTK: Vieäc toaøn boä caây coù theå ñöôïc thöïc hieän thoâng qua thao taùc duyeät caây theo thöù töï sau. Nghóa laø ta seõ huûy caây con traùi, caây con phaûi roài môùi huûy nuùt goác. 6. Caây nhò phaân caân ñoái * Caây nhò phaân caân ñoái hoaøn toaøn: laø caây nhò phaân tìm kieám maø taïi moãi nuùt cuûa noù, soá nuùt cuûa caây con traùi cheânh leäch khoâng quaù moät so vôùi soá nuùt cuûa caây con phaûi. Nhaän xeùt: Moät caây khoù ñaït ñöôïc traïng thaùi caân baèng hoaøn toaøn. Tuy nhieân neáu caây caân ñoái thì vieäc tìm kieám seõ nhanh, trong tröôøng hôïp xaáu nhaát ta chæ phaûi tìm qua log2n phaàn töû (vôùi n laø soá nuùt treân caây). Do caây caân ñoái hoaøn toaøn laø moät caáu truùc keùm oån ñònh neân trong thöïc teá khoâng theå söû duïng. * Caây nhò phaân caân ñoái: laø caây maø taïi moãi nuùt cuûa noù ñoä cao cuûa caây con traùi vaø cuûa caây con phaûi cheânh leäch khoâng quaù moät. Nhaän xeùt: Caây caân ñoái hoaøn toaøn laø caây caân baèng. Ñieàu ngöôïc laïi khoâng ñuùng. Tuy nhieân caây caân ñoái laø caáu truùc döõ lieäu oån ñònh hôn haún caây caân ñoái hoaøn toaøn. Töø caây caân ñoái ngöôøi ta ñaõ phaùt trieån theâm nhieàu laïi caáu truùc döõ lieäu höõu duïng khaùc nhö caây ñoû-ñen, B-caây,... 7. Caây nhò phaân tìm kieám toái öu Xaây döïng caây nhò phaân tìm kieám töông öùng vôùi caùc töø khoùa. Ñoái vôùi caùc töø khoùa coù xaùc suaát xuaát hieän lôùn thì caàn phaûi ñöôïc tìm thaáy nhanh hôn, nghóa laø töông öùng vôùi ñöôøng ñi ngaén hôn. Muoán theá gaén vôùi moãi khoùa (nuùt) moät troïng soá, ñoù chính laø xaùc suaát xuaát hieän cuûa khoùa naøy trong tìm kieám. Vaø muïc ñích laø xaùc ñònh ñöôïc caây nhò phaân tìm kieám sao cho toång ñoä daøi ñöôøng ñi coù troïng soá töông öùng vôùi moïi nuùt treân caây (hay coøn goïi laø ñoä daøi ñöôøng ñi coù troïng soá cuûa caây) coù giaù trò nhoû nhaát. Tuy nhieân vieäc choïn moät caây coù troïng soá nhoû nhaát laø moät coâng veäc khoù thöïc hieän khi n khaù lôùn. Vaäy ñeå giaûi quyeát vaán ñeà naøy ta thöïc hieän theo nguyeân taéc sau: “Ñoái vôùi moät caây nhò phaân tìm kieám toái öu thì baát kyø moät caây con naøo cuûa noù cuõng phaûi laø caây nhò phaân tìm kieám toái öu ”. Töø ñoù daãn tôùi moät giaûi thuaät cho pheùp döïng ñöôïc caây nhò phaân tìm kieám toái öu lôùn daàn leân baét ñaàu töø moät nuùt laù maø ta goïi laø kyõ thuaät döïng caây nhò phaân tìm kieám toái öu theo kieåu “töø ñaùy leân” (bottom up). Phaàn III: TOÅ CHÖÙC LÖU TRÖÕ CAÂY TÖØ ÑIEÅN Moät caáu truùc döõ lieäu khaù ñieån hình vaø hôïp lyù vôùi baøi toaùn töø ñieån laø: caáu truùc caây töø ñieån. Quaûn lyù töø ñieån coù daïng caây laø kyõ thuaät thöôøng ñöôïc söû duïng ñeå xöû lyù nhöõng töø ñieån lôùn nhaèm thu nhoû dung löôïng. Caây töø ñieån laø taäp hôïp caùc baûn ghi lieân keát vôùi nhau (coøn goïi laø phöông phaùp löu tröõ moùc noái). Moãi baûn ghi goïi laø moät nuùt trong caây. Ñeå quaûn lyù caây töø ñieån ta luoân luoân phaûi giöõ ñòa chæ cuûa caây, töùc laø nuùt goác (nuùt ñaàu tieân cuûa caây). Moãi nuùt caây töø ñieån goàm coù 3 tröôøng: + Tröôøng Info: chöùa moät kí töï kieåu CHAR. + Tröôøng Left: chæ ñeán nuùt Anh Em cuûa noù. + Tröôøng Right: chæ ñeán nuùt con cuûa noù. Moät nuùt B goïi laø con cuûa nuùt A neáu B = A.left Töông töï nuùt B goïi laø nuùt Anh Em cuûa nuùt A neáu: B = A.right (hoaëc A = B.right). Töø ñaây môû roäng ra: neáu B laø Con cuûa A vaø C laø Anh Em cuûa B thì caû B vaø C ñeàu laø Con cuûa A. Neáu A laø Anh Em cuûa B vaø B laø Anh Em cuûa C thì A cuõng laø Anh Em cuûa C. Ñeå taïo thaønh caây töø ñieån trong quaù trình chaïy chöông trình, ta phaûi laøm thao taùc naïp caùc töø tieáng Nga vaøo caây. Veà tröôøng nghóa cuûa töø, vì noù raát lôùn neân khoâng theå naïp vaøo boä nhôù chöông trình ñöôïc. Vì vaäy ta phaûi ñeå nghóa cuûa töø ôû trong File. Ñieàu naøy baét buoäc ta phaûi xen keøm vaøo trong caây töø ñieån (töông öùng sau moãi töø tieáng Nga) chæ soá vò trí cuûa töø tieáng Nga ñoù trong File. Vaø taát nhieân chæ soá naøy phaûi ñöôïc ñoåi thaønh chuoãi kí töï thaäp phaân tröôùc khi thöïc hieän xen töø. Khi ñoïc thì seõ chuyeån ngöôïc chuoãi chæ soá naøy sang soá thaäp phaân. Ví duï: Vôùi caùc töø tieáng Nga: а/абажур/абзац/база/базар/бак/бакалея/ баклажан. Khi löu tröõ treân caây, caùc töø tieáng Nga naøy seõ laø caùc chuoãi coù caáu truùc nhö sau: а*1 абажур*2 абзац*3 база*4 базар*5 бак*6 бакалея*7 баклажан*8 ta coù caáu truùc caây töø ñieån nhö sau: * а * 1 б б а ж у р 2 з а ц * * 3 а з а * 4 р * 5 * к 6 а л е * я 7 а ж а н * 8 Root Nuùt ñaùnh daáu keát thuùc cuûa moãi töø Nuùt ñaùnh daáu soá thöù töï baûn ghi cuûa moãi töø, söû duïng cho vieäc tìm kieám vaø tra töø Nuùt theå hieän töøng kyù töï cuûa moãi töø Nhaän xeùt: Theo caây töø ñieån ñöôïc minh hoaï ôû treân, kí töï ‘*’ ñöôïc söû duïng laøm kyù töï ñaùnh daáu ôû ñaàu caáu truùc caây vaø laøm kyù töï keát thuùc cuûa moät töø. Nhö vaäy theo caây töø ñieån thì moãi töø tieáng Nga ngoaøi caùc kí töï hình thaønh coøn coù theâm kí töï ‘*’ ôû cuoái moãi töø ñeå ñaùnh daáu vaø caùc kí töï chöõ soá ñeå ñaùnh soá thöù töï töøng baûn ghi trong file döõ lieäu hoã trôï cho quaù trình tìm kieám treân caây. Moãi töø trong töø ñieån töông öùng vôùi moät baûn ghi goàm ba tröôøng: wordRec = record wordRus: string[25]; // tröôøng Tieáng Nga wordMea: string[200]; // tröôøng nghóa Tieáng Vieät STT:string[6];// tröôøng soá thöù töï cho hình aûnh, aâm thanh end; Nhö vaäy ñeå chöùa caùc töø treân caây chæ maát raát ít soá baûn ghi so vôùi döõ lieäu cuûa noù. Vôùi caáu truùc naøy ta coù theå naïp vaøo chöông trình khi chaïy taát caû caùc töø coù trong moät boä töø ñieån lôùn khoaûng 100.000 töø maø khoâng sôï bò traøn boä nhôù. Hôn nöõa thuaät toaùn xaây döïng caùc thao taùc treân caây töø ñieån naøy seõ hoaït ñoäng raát nhanh maø khoâng phuï thuoäc vaøo kích thöôùc döõ lieäu ñaàu vaøo. Khi chöông trình hoaït ñoäng, moãi laàn ta ñaùnh vaøo moät kí töï (trong quaù trình nhaäp töø ñeå tra) chöông trình seõ phaûi duyeät caây töø ñieån ñeå tìm ra caùc töø gaàn gioáng vôùi chuoãi töø maø ta ñang nhaäp nhaát. Danh saùch caùc töø naøy seõ hieän ra giao dieän chöông trình. Quaù trình duyeät baét ñaàu töø nuùt goác (Root) daàn daàn xuoáng tôùi caùc nuùt con. Ñaëc ñieåm cuûa caây töø ñieån coù raát nhieàu nuùt laù, chieàu cao cuûa caây laïi raát thaáp (do soá kí töï taïo ra töø khoâng nhieàu). Ñieàu naøy raát thích hôïp cho ta trong vieäc thöôøng xuyeân phaûi tìm kieám treân caây. Thuaät toaùn xaây döïng treân caáu truùc döõ lieäu naøy seõ ñôn giaûn vaø hoaït ñoäng raát nhanh. Keát luaän: Ñoái vôùi daïng caây Töø Ñieån ñaõ noùi ôû treân ta thaáy caây Töø Ñieån laø moät caây daïng toång quaùt coù tieàn toá chung. Nhöng ñeå ôû daïng caây toång quaùt thì vieäc thöïc hieän caùc thao taùc vaø caùc pheùp xöû lyù treân caây khoù khaên, cho neân caây ñöôïc chuyeån veà daïng caây nhò phaân vôùi thuaät toaùn chuyeån ñaõ trình baøy. Qua daïng caáu truùc cuûa caây nhò phaân Töø Ñieån ta coù nhaän xeùt chung: Moät töø luoân ñöôïc keát thuùc treân nhaùnh caây con traùi. Caùc töø coù tieàn toá chung khi chuùng laø caây con phaûi cuûa nuùt con traùi cuûa nuùt chöùa kí töï cuoái cuøng thuoäc chuoãi tieàn toá. Töø nhaän xeùt treân chuùng ta coù theå xaây döïng ñöôïc caùc giaûi thuaät tìm kieám, theâm, loaïi boû… moät caùch chính xaùc. Phaàn IV: THIEÁT KEÁ CHÖÔNG TRÌNH V.1. TAÏO BOÄ GOÕ VAØ FONT TIEÁNG NGA COÙ DAÁU NHAÁN TROÏNG AÂM CHO NGÖÔØI DUØNG 1. Khaùi quaùt veà boä goõ Khi nhaäp töø, vaán ñeà xaùc ñònh kí töï tieáng Nga treân baøn phím ñoái vôùi ngöôøi söû duïng laø raát khoù khaên. Vì theá, chöông trình Töø ñieån naøy ñaõ hoã trôï moät boä goõ tieáng Nga cho ngöôøi duøng trong quaù trình tra töø, khi ngöôøi duøng khoâng nhôù vò trí cuûa kí töï. Tuy thoâ sô nhöng giaûi phaùp naøy phaàn naøo ñaõ mang laïi cho ngöôøi duøng caûm giaùc thoaûi maùi khi söû duïng boä goõ. Vôùi giao dieän baøn phím nhìn thaáy ñöôïc treân maøn hình, ngöôøi söû duïng chöa quen vôùi baøn phím tieáng Nga coù theå xaùc ñònh ñöôïc caùc phím cuûa kí töï tieáng Anh töông öùng vôùi töøng kyù töï tieáng Nga, qua ñoù ngöôøi söû duïng coù theå goõ ñöôïc caùc töø tieáng Nga moät caùch deã daøng. Cuõng vôùi giao dieän naøy ta coù theå thieát keá ñeå ngöôøi söû duïng duøng chuoät click vaøo caùc phím treân boä goõ ñeå ñöôïc töø mong muoán. 2. Caùch thieát keá boä goõ Tieáng Nga vaø Tieáng Vieät cho rieâng chöông trình Khi söû duïng chöông trình Töø ñieån, neáu treân maùy ngöôøi duøng khoâng caøi ñaët caùc chöông trình nhö VietKey, VietWare.... thì khoâng theå thöïc hieän ñöôïc chöùc naêng tra töø tieáng Nga cuõng nhö theâm töø tieáng Vieät. Vì vaäy, vieäc taïo moät boä goõ tieáng Nga vaø tieán Vieät rieâng cho chöông trình laø ñieàu caàn thieát. Baèng font tieáng Nga töï thieát keá vaø moät soá font tieáng Vieät coù saün cuûa VietKey, döïa vaøo baûng maõ ASCII cuûa phoâng chöõ chuùng ta coù theå bieát ñöôïc caùc maõ töông öùng töøng chöõ caùi tieáng Nga cuõng nhö tieáng Vieät. Vôùi ngoân ngöõ Delphi coù hoã trôï thuû tuïc chaën thoâng ñieäp caùc phím baám töø baøn phím (thuû tuïc PostMessage). Ñeå taïo ra ñöôïc caùc kyù töï tieáng Nga, tieáng Vieät töông öùng vôùi phím goõ chöông trình caàn phaûi chaën ñöôïc thoâng ñieäp ñeán töø baøn phím, xaùc ñònh ñöôïc phím goõ töông öùng vôùi phím naøo cuûa baøn phím tieáng Nga cuõng nhö tieáng Vieät. Bình thöôøng thì kyù töï hieån thò treân maøn hình seõ laø kyù töï Latinh töông öùng phím goõ, do ñoù ñeå hieån thò ñöôïc kyù töï tieáng Nga chöông trình caàn phaûi xoùa kyù töï Latinh vaø thay theá baèng kyù töï tieáng Nga. Vieäc thay theá kyù töï tieáng Nga ñöôïc döïa treân maõ ASCII cuûa font chöõ tieáng Nga ñöôïc duøng ñeå hieån thò. Hai thuû tuïc sau trong chöông trình seõ thöïc hieän vieäc xoùa kyù töï Latinh vaø thay vaøo kyù töï tieáng Nga: 1 PostMessage (frmNgaVietAnh.cboNhapTu.handle, WM_CHAR, 8, 1); 2 PostMessage (frmNgaVietAnh.cboNhapTu.handle, WM_CHAR, MaFont, 1); 1 Duøng ñeå xoùa kyù töï Latinh vôùi maõ ASCII baèng 8 laø maõ cuûa phím Del. 2 Duøng ñeå hieån thò kyù töï Nga coù MaFont töông öùng vôùi maõ ASCII trong phoâng tieáng Nga cuûa phím ñöôïc goõ. Haøm PostMessage cuõng ñöôïc söû duïng töông töï cho kyù töï tieáng Vieät. 3. Phöông phaùp taïo Font Tieáng Nga môùi Phoâng chöõ tieáng Nga hieän nay vaãn ñang laø moät vaán ñeà quan taâm cuûa ngöôøi duøng. Trong nhöõng font chöõ hoã trôï tieáng Nga hieän nay cuûa caùc phaàn meàm nhö Vietkey 2002, VietKey4.0, Unikey,...thì khoâng moät font naøo coù kí töï daáu troïng aâm ( laø moät aâm nhaán treân ñaàu moãi töø ) nhaèm giuùp ngöôøi duøng bieát caùch phaùt aâm cuûa töø moät caùch chính xaùc . Taïo moät boä font môùi töôûng chöøng laø moät vaán ñeà nan giaûi, nhöng hieän nay vôùi söï hoã trôï cuûa nhieàu phaàn meàm chuyeân duïng thì vieäc giaûi quyeát khoâng coøn maáy khoù khaên. Vôùi phaàn meàm Photographer 4.1, baïn coù theå taïo ra moät boä font tuøy yù vôùi kí töï do chính baïn thieát keá. Caùc böôùc taïo font treân Photographer ñöôïc tieán haønh nhö sau: - Choïn moät boä font môùi, sau ñoù öùng vôùi töøng kí töï treân baøn phím ta coù theå veõ caùc kí töï baèng caùc coâng cuï thieát keá ñoà hoïa ñöôïc cung caáp saün trong phaàn meàm naøy. - Sau ñoù löu laïi ñeå taïo ra moät boä font môi, ñoù chính laø font RussTimes SNG ñöôïc söû duïng trong chöông trình naøy. Kí töï daáu nhaán troïng aâm sau khi ñöôïc thieát keá xong. Baûng coâng cuï thieát keá kí töï cuûa chöông trình. Vò trí cuûa daáu nhaán troïng aâm trong boä font môùi taïo. Nhôø phaàn meàm naøy maø chöông trình hoïc tieáng Nga ñaõ coù moät boä font môùi vôùi ñaày ñuû caùc chöùc naêng caàn thieát cho vieäc nhaäp döõ lieäu cuûa chöông trình. V.2. PHÖÔNG PHAÙP LÖU AÂM THANH VAØ HÌNH AÛNH CHO CHÖÔNG TRÌNH TÖØ ÑIEÅN 1. Löu aâm thanh Sau khi thu aâm gioïng ñoïc töø beân ngoaøi vaøo maùy thoâng qua chöông trình JetAudio, hoaëc chöông trình Recoder. Phieân aâm tieáng Nga ñöôïc taùch vaø löu thaønh caùc file .mp3. Vieäc taùch thaønh caùc file (.MP3) seõ tieát kieäm boä nhôù hôn so vôùi caùc file (.WAV). Ngoân ngöõ Delphi cho pheùp môû taäp tin aâm thanh (.WAV) vôùi haøm PlaySound(). Tuy nhieân haøm naøy laïi khoâng hoã trôï vieäc môû caùc taäp tin aâm thanh (.MP3), trong khi ñoù haàu heát caùc daïng taäp tin multimedia, töø aâm thanh cho ñeán phim aûnh, nhö (.WAV), (,MP3), (.MINI), (.DAT), (.AVI).... ñeàu coù theå môû ñöôïc thoâng qua ñoái töôïng TMediaPlayer ñöôïc cung caáp trong ngoân ngöõ laäp trình. Vì vaäy, chöông trình ñaõ söû duïng taäp hôïp caùc nuùt nhaán ñieàu khieån thoâng duïng nhö Play, Stop, Pause... cuûa ñoái töôïng TMediaPlayer ñeå thöïc hieän vieäc môû caùc taäp tin aâm thanh. 2. Löu hình aûnh AÛnh ñöôïc naïp vaøo chöông trình thoâng qua ñoái töôïng TImage cuûa ngoân ngöõ laäp trình. Ñeå naïp aûnh töø taäp tin vaøo ñoái töôïng TImage, ta söû duïng thuoäc tính TImage.Picture vaø goïi phöông thöùc LoadFromFile. 3. Caùch thöùc noái keát caùc file aâm thanh vaø hình vaøo chöông trình Moãi töø trong töø ñieån töông öùng vôùi moät baûn ghi goàm ba tröôøng nhö sau: wordRec = record wordRus: string[25]; // tröôøng Tieáng Nga wordMea: string[200]; // tröôøng nghóa Tieáng Vieät STT:string[6];// tröôøng soá thöù töï cho hình aûnh, aâm thanh end; Teân caùc file aâm thanh vaø hình aûnh ñöôïc gaén soá thöù töï töông öùng vôùi caùc tröôøng STT cuûa moãi töø. Vì theá sau khi hieän nghóa Tieáng Vieät, neáu tìm thaáy teân file aâm thanh hay hình aûnh töông öùng vôùi soá thöù töï cuûa tröôøng STT thì caùc file naøy ñöôïc naïp ñeå goïi trong chöông trình. V.3. MOÄT SOÁ GIAÛI THUAÄT TRONG CHÖÔNG TRÌNH Caùc giaûi thuaät haàu heát ñöôïc caøi ñaët qua caùc haøm, thuû tuïc DLL. Chuùng ñöôïc goïi töø caùc chöông trình DLL khaùc. Vieäc söû duïng caùc haøm, thuû tuïc DLL giuùp ngöôøi laäp trình traùnh ñöôïc nhöõng caâu leänh phöùc taïp, daøi doøng ñoàng thôøi chöông trình trôû neân chaët cheõ, deã hieåu vaø deã söûa chöõa khi coù sai soùt trong quaù trình thöû nghieäm. Moät soá giaûi thuaät ñöôïc söû duïng trong chöông trình Töø ñieån Nga – Vieät goàm: 1. Giaûi thuaät tìm kieám treân caây töø ñieån - Duyeät caây töø ñieån baét ñaàu töø nuùt goác - So saùnh töøng kí töï cuûa chuoãi caàn tìm kieám coù theâm kí töï ‘*’ ôû cuoái chuoãi vôùi töøng nuùt treân caây. - Neáu keát thuùc quaù trình duyeät caây gaëp kí töï ‘*’ thì thoâng baùo tìm kieám thaønh coâng. Ngöôïc laïi thì thoâng baùo quaù trình tìm kieám khoâng thaønh coâng. //** Haøm tìm töø treân caây Töø ñieån Function _FindWord(var p,q: TNode; st: string): Boolean;export;stdcall; var i: integer; ketQua, Found: Boolean; begin i:= 1; p:= Root; Found:=false; ketQua:= false; st:= st + '*'; While (i <length(st)) and (not ketQua) do begin q:=p; if st[i]= #96 then inc(i); {ki tu trong am} if st[i] < p^.Info then begin ketQua:= true; Found:= False; end else if st[i] > p^.Info then if p^.Right nil then begin p:= p^.Right; ketQua:= false; end else begin ketQua:= true; Found:=false; end else if p^.Left nil then if st[i]='*' then begin ketQua:=true; Found:=true; end else begin p:= p^.Left; inc(i); ketQua:=false; end else begin ketQua:=true; Found:=false; end; end; _FindWord:= Found; end; 2. Caùc böôùc tra töø - Goïi haøm tìm töø. - Neáu tìm khoâng thaønh coâng thì thoâng baùo loãi “Töø khoâng coù trong töø ñieån”. - Ngöôïc laïi: + Ñoïc tieáp caùc nuùt chöõ soá ñaùnh daáu soá thöù töï cuûa caùc baûn ghi trong file döõ lieäu. + Ñoåi chuoãi soá ñoïc ñöôïc thaønh soá. + Môû file döõ lieäu, chuyeån con troû file vò trí baûn ghi caàn tìm. + Xuaát tröôøng nghóa cuûa baûn ghi ra maøn hình. //** Thuû tuïc tra töø trong töø ñieån procedure_SearchWordNV(var keyWor: integer; st: string; MForm: TfrmNgaVietAnh); export;stdcall; var p,q:TNode; findWor:boolean; f:file of TWordNV; word:TWordNV; Begin st:= st + '*'; findWor:= _FindWord(p,q,st); If not findWor then ShowMessage('Khong tim thay tu trong tu dien') Else begin st:= ''; repeat { Doc thong tin cac nut luu so khoa-so thu tu ban ghi} begin p:= p^.Left; st:= st + p^.Info; end; until p^.Left = nil; keyWor:= StrToInt(st); AssignFile(f,FileName); Reset(f); Seek(f,keyWor); read(f,word); MForm.retTuViet.Lines.CommaText:= word.VieMean; MForm.lblHienChu.Caption:=word.RusWord; CloseFile(f); end; end; 3. Caùc böôùc theâm töø - Goïi thuû tuïc tìm töø. - Neáu tìm thaønh coâng thì thoâng baùo “Töø ñaõ coù trong töø ñieån”. - Ngöôïc laïi: + Theâm töø vaøo cuoái danh saùch. + Theâm töø vaøo cuoái file döõ lieäu. + Theâm töø vaøo caây. //** Thuû tuïc theâm töø trong töø ñieån procedure _AddWord(MForm: TfrmNgaVietAnh; stWor: string; stMea: string); export; stdcall; var p,q: TNode; findWor: Boolean; st: string; f: file of TWordNV; recNum: integer; begin st:= stWor + '*'; findWor:= _FindWord(p,q,st); // Ham tim tu If findWor then ShowMessage('Tu da co trong tu dien')//_ErrorMsg(3) // Thong bao co tu trong Tu Dien Else begin AssignFile(f,FileName); Reset(f); try recNum:= FileSize(f); finally CloseFile(f); end; st:= st + IntToStr(recNum); // Gan so ban ghi vao chuoi tu de de tim MForm.lstDSNV.Items.Add(stWor); _AddToFile(stWor,stMea); _AddToTree(st); // Thu tuc "Them tu vao cay" ShowMessage('Tõ míi ®· ®­îc l­u!'); end; end; 4. Caùc böôùc söûa töø - Goïi thuû tuïc tìm töø. - Neáu tìm khoâng thaønh coâng thì thoâng baùo “Khoâng coù töø trong töø ñieån”. - Ngöôïc laïi: + Môû file döõ lieäu. + Ñöa con troû file ñeán vò trí baûn ghi töông öùng. + Ghi ñeø baûn ghi môùi leân baûn ghi cuõ. / /** Thuû tuïc söûa töø trong töø ñieån procedure _RepairWord(stOld:string; stWor: string; stMea: string);export; stdcall; var f: file of TWordNV; findWor:boolean; key:integer; p,q:TNode; worRec:TWordNV; st: string; begin key:=0; st:= stOld + '*'; findWor:= _FindWord(p,q,st); If not findWor then ShowMessage('Tu khong co trong tu dien') //_ErrorMsg(2) Else begin //Doc khoa Repeat p:= p^.Left; key:= key + StrToInt(p^.Info); until p^.Left= nil; worRec.RusWord:= stWor; worRec.VieMean:= stMea; //Mo file AssignFile(f,FileName); Reset(f); //Ghi de len ban ghi hien hanh Seek(f,key); write(f,worRec); CloseFile(f); ShowMessage('Töø söûa ñaõ ñöôïc löu!'); end; end; 5. Caùc böôùc xoùa töø - Goïi thuû tuïc tìm töø. - Neáu khoâng tìm thaáy töø thì thoâng baùo “Töø khoâng coù trong töø ñieån”. - Ngöôïc laïi: + Xoaù tröôøng tieáng Nga trong danh saùch hieån thò töø. + Xoaù baûn ghi chöùa töø trong file. + Xoaù kí töï “*” ñaùnh daáu ôû cuoái töø caàn xoaù treân caây. //** Thuû tuïc xoùa töø trong töø ñieån procedure _DelWord(MForm:TfrmNgaVietAnh; st: string);export;stdcall; var findWor:boolean; p, q: TNode; begin st:= st + '*'; findWor:= _FindWord(p,q,st); If not findWor then ShowMessage('Khong tim thay tu trong tu dien')//_ErrorMsg(2) Else begin DelWordInFile(p); DelWordInTree(q,p); DelWordInList(MForm, st); ShowMessage('Töø ñaõ ñöôïc xoùa khoûi Töø Ñieån!'); end; end; 6. Giaûi thuaät tìm kieám nhò phaân ñeå cheøn töø vaøo ñuùng vò trí trong danh saùch - Tìm kieám trong danh saùch ñaõ ñöôïc saép xeáp thöù töï. - Tìm vò trí giöõa cuûa danh saùch ( i ). - Laàn löôït so saùnh töøng kí töï cuûa töø caàn cheøn (giaû söû laø x) vôùi kí töï cuûa töø taïi vò trí i cuûa danh saùch (giaû söû laø y) theo qui taéc sau: + Neáu x=y thì töø ñöôïc tìm thaáy. + Neáu x<y thì töø coù trong khoaûng töø ñaàu danh saùch ñeán kí töï thöù i-1. + Neáu x>y thì kí töï coù phaïm vi phía sau y. - Sau khi xaùc ñònh ñuùng vò trí thì töø seõ ñöôïc cheøn vaøo danh saùch. //** Thuû tuïc tìm kieám vaø cheøn töø Function FindCharFirst(st:string;len:word):word;export;stdcall; Var Tim:boolean; l,r,m:word; begin Tim:=false; l:= 0; r:= len; While (l<=r) and (Tim = false) do begin m:=(l+r)div 2; If st<frmNgaVietAnh.lstDSNV.Items[m] then r:=m-1 Else If st>frmNgaVietAnh.lstDSNV.Items[m] then l:=m+1 else Tim:= true; end; If l<= r then begin While st= frmNgaVietAnh.lstDSNV.Items[m] do m:=m-1; m:= m+1; end; FindCharFirst:= m; end; {===========} Function FindCharNext(st:string;index:word):word;export;stdcall; var m:word; begin While st< frmNgaVietAnh.lstDSNV.Items[index] do index:=index+1; If st=frmNgaVietAnh.lstDSNV.Items[index] then m:=index; If st> frmNgaVietAnh.lstDSNV.Items[index] then m:=index-1; FindCharNext:=m; end; {===========} Procedure _FindWordInDS(st:string;len:word);export;stdcall; begin If st = '' then index:= 0; If length(st)=1 then index := FindCharFirst(st,len) Else index := FindCharNext(st,index); {Di chuyen den vi tri can tim trong danh sach} SendMessage(frmNgaVietAnh.lstDSNV.Handle, lb_SetTopIndex, frmNgaVietAnh.lstDSNV.ItemIndex-1, 0); end; 7. Maõ leänh taïo boä goõ Tieáng Vieät //** Thuû tuïc taïo Boä goõ Tieáng Vieät duøng cho caùc ñoái töôïng coù FONT Vieät procedure _VietFont; var prevchar, key:char; begin if msg.message=WM_CHAR then begin key:=chr(msg.wParam); case key of '1':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(249); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(217); chr(234),chr(202),chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)-1,1); handled:=true; end; end; '2':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(248); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(216); chr(234),chr(202),chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)-2,1); handled:=true; end; end; '3':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(251); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(219); chr(234),chr(202):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+16,1); handled:=true; end; chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+3,1); handled:=true; end; end; '4':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(245); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(213); chr(234),chr(202):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+18,1); handled:=true; end; chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+1,1); handled:=true; end; end; '5':case prevchar of 'a','e','o','u','y','i',chr(246),chr(244):key:=chr(239); 'A','E','O','U','Y','I',chr(214),chr(212):key:=chr(207); chr(234),chr(202):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+1,1); handled:=true; end; chr(226),chr(194):begin PostMessage(Editor.handle,WM_CHAR,8,1); PostMessage(Editor.handle,WM_CHAR,ord(prevchar)+2,1); handled:=true; end; end; '6':case prevchar of 'a','e','o':key:=chr(226); 'A','E','O':key:=chr(194); end; '7':begin if prevchar in ['U','O','u','o'] then begin postmessage(Editor.handle,WM_CHAR,8,1); handled:=true; end; case prevchar of 'u':postmessage(Editor.handle,WM_CHAR,246,1); 'U':postmessage(Editor.handle,WM_CHAR,214,1); 'o':postmessage(Editor.handle,WM_CHAR,244,1); 'O':postmessage(Editor.handle,WM_CHAR,212,1); end; end; '8':case prevchar of 'a':key:=chr(234); 'A':key:=chr(202); end; '9':begin if prevchar in ['D','d'] then begin postmessage(Editor.handle,WM_CHAR,8,1); handled:=true; end; case prevchar of 'd':postmessage(Editor.handle,WM_CHAR,241,1); 'D':postmessage(Editor.handle,WM_CHAR,209,1); end; end; end; prevchar:=key; msg.wparam:=ord(key); end; end; 8. Maõ leänh taïo boä goõ Tieáng Nga //**Thuû tuïc ñoåi maõ font procedure DoiMaFont(formTuDien: TfrmNgaVietAnh; MaFont: byte); begin PostMessage(formTuDien.cboNhapTu.handle,WM_CHAR,8,1); PostMessage(formTuDien.cboNhapTu.handle,WM_CHAR,MaFont,1); end; {==============} //** Thuû tuïc choïn font cho caùc ñoái töôïng tieáng Nga procedure _ChoseFont(key:char; chose: byte);export;stdcall; begin case key of 'f':DoiMaFont(chose,224); 'F':DoiMaFont(chose,192); ',':DoiMaFont(chose,225); '<':DoiMaFont(chose,193); 'd':DoiMaFont(chose,226); 'D':DoiMaFont(chose,194); 'u':DoiMaFont(chose,227); 'U':DoiMaFont(chose,195); 'l':DoiMaFont(chose,228); 'L':DoiMaFont(chose,196); 't':DoiMaFont(chose,229); 'T':DoiMaFont(chose,197); '/':DoiMaFont(chose,184); '?':DoiMaFont(chose,168); ';':DoiMaFont(chose,230); ':':DoiMaFont(chose,198); 'p':DoiMaFont(chose,231); 'P':DoiMaFont(chose,199); 'b':DoiMaFont(chose,232); 'B':DoiMaFont(chose,200); 'q':DoiMaFont(chose,233); 'Q':DoiMaFont(chose,201); 'r':DoiMaFont(chose,234); 'R':DoiMaFont(chose,202); 'k':DoiMaFont(chose,235); 'K':DoiMaFont(chose,202); 'v':DoiMaFont(chose,236); 'V':DoiMaFont(chose,204); 'y':DoiMaFont(chose,237); 'Y':DoiMaFont(chose,205); 'j':DoiMaFont(chose,238); 'J':DoiMaFont(chose,206); 'g':DoiMaFont(chose,239); 'G':DoiMaFont(chose,207); 'h':DoiMaFont(chose,240); 'H':DoiMaFont(chose,208); 'c':DoiMaFont(chose,241); 'C':DoiMaFont(chose,209); 'n':DoiMaFont(chose,242); 'N':DoiMaFont(chose,210); 'e':DoiMaFont(chose,243); 'E':DoiMaFont(chose,211); 'a':DoiMaFont(chose,244); 'A':DoiMaFont(chose,212); '[':DoiMaFont(chose,245); '{':DoiMaFont(chose,213); 'w':DoiMaFont(chose,246); 'W':DoiMaFont(chose,214); 'x':DoiMaFont(chose,247); 'X':DoiMaFont(chose,215); 'i':DoiMaFont(chose,248); 'I':DoiMaFont(chose,216); 'o':DoiMaFont(chose,249); 'O':DoiMaFont(chose,217); ']':DoiMaFont(chose,250); '}{':DoiMaFont(chose,218); 's':DoiMaFont(chose,251); 'S':DoiMaFont(chose,219); 'm':DoiMaFont(chose,252); 'M':DoiMaFont(chose,220); chr(39):DoiMaFont(chose,253); '"':DoiMaFont(chose,221); '.':DoiMaFont(chose,254); '>':DoiMaFont(chose,222); 'z':DoiMaFont(chose,255); 'Z':DoiMaFont(chose,223); end; end; V.4. GIAO DIEÄN CUÛA CHÖÔNG TRÌNH VAØ CAÙCH THÖÙC HOAÏT ÑOÄNG 1. Giao dieän chính cuûa chöông trình vôùi caùc menu thaønh phaàn Taát caû caùc chöùc naêng ñeàu ñöôïc theå hieän roõ treân giao dieän chính cuûa chöông trình. Töø Form chính, ngöôøi söû duïng coù theå kích chuoät ñeå choïn moät trong caùc menu coù saún. ÖÙng vôùi töøng menu ñöôïc choïn, Form chính seõ noái keát ñeán töøng Form DLL töông öùng ñöôïc taïo saún. Muïc giôùi thieäu ñeà taøi vaø söû duïng chöông trình Menu cuûa caùc töø ñieån Ngöõ phaùp tieáng Nga Menu Thöïc haønh: duøng noái keát tôùi Form luyeän nghe hoaëc Form laøm baøi taäp traéc nghieäm. Menu Trôï giuùp: noái keát tôùi trang giôùi thieäu ñeà taøi hoaëc trang höôùng daãn söû duïng chöông trình. Menu Töø ñieån: noái keát tôùi Form Töø ñieån Nga – Vieät hoaëc Töø ñieån Nga – Anh. Menu Ngöõ phaùp: noái keát tôùi Form ngöõ phaùp tieáng Nga. Menu choïn chöông trình luyeän nghe vaø laøm baøi taäp 2. Giao dieän Töø ñieån Töø ñieån goàm caùc phím chöùc naêng cô baûn nhö : tra töø, trôû veà töø tröôùc ñoù, phaàn tieän ích vôùi caùc chöùc naêng: theâm töø, söûa töø, xoùa töø. Nhaán nuùt tra töø sau khi choïn moät töø baát kyø trong danh saùch, seõ xuaát hieän nghóa cuûa töø vaø hình aûnh (neáu coù). Khi goõ töøng kí töï vaøo oâ nhaäp töø, danh saùch caùc töø coù kí töï töông öùng ñöôïc nhaûy ñeán töï ñoäng nhaèm giuùp ngöôøi söû duïng trong quaù trình tra töø. Trôû veà töø tröôùc: ñoù giuùp ngöôøi duøng tieát kieäm thôøi gian trong vieäc tìm laïi nghóa nhöõng töø mình ñaõ tra. Ngoaøi ra Töø ñieån coøn cung caáp theâm hai nuùt chöùc naêng: hieån thò baøn phím vaø thay ñoåi kích côõ chöõ (coù 3 caáp ñoä: chöõ lôùn, chöõ trung bình vaø chöõ nhoû). OÂ nhaäp töø Phieân aâm (neáu coù) Nuùt tra töø Nuùt trôû laïi töø tröôùc ñoù Form baøn phím ñöôïc thieát keá nhö sau: öùng vôùi töøng kí töï tieáng Nga seõ coù moät kí töï cuûa baøn phím thoâng thöôøng coù kích thöôùc nhoû hôn ôû phía treân beân phaûi. Baøn phím Tieáng Nga cuûa töø ñieån. Thayñoåi kích côõ töø Hieån thò baøn phím tieáng Nga Nuùt tieän ích Töø ñieån Nga - Vieät Töø ñieån Nga - Anh Nuùt tieän ích chöùa ba chöùc naêng cô baûn ôû moät töø ñieån thoâng thöôøng, ñoù laø: xoùa töø, söûa töø, theâm töø. Choïn moät trong ba chöùc naêng naøy thì Form DLL töông öùng seõ xuaát hieän. Vôùi Form xoùa töø, chæ caàn nhaäp töø vaøo oâ xoùa töø vaø click chuoät vaøo nuùt Xoùa thì hoaëc laø töø seõ ñöôïc xoùa neáu tìm thaáy, hoaëc ñöa ra thoâng baùo “Khoâng tìm thaáy töø trong töø ñieån”. Ñeå söûa töø, laàn löôït goõ töø caàn söûa, töø thay theá vaø nghóa töø caàn söûa vaøo caùc oâ ñaõ ñeå troáng saún, roài nhaán nuùt Söûa. Neáu ñöôïc tìm thaáy thì töø seõ ñöôïc söûa vaø ñöa ra thoâng baùo “Töø ñaõ ñöôïc söûa xong” ngöôïc laïi thì ñöa ra thoâng baùo “Khoâng tìm thaáy töø trong töø ñieån”. Ñeå theâm töø, laàn löôït nhaäp töø môùi vaø nghóa töø môùi vaøo caùc oâ troáng, roài nhaán nuùt Löu. Neáu töø ñaõ coù trong danh saùch, hieån thò thoâng baùo “Töø ñaõ coù trong töø ñieån” ngöôïc laïi thì ñöa ra thoâng baùo “Töø ñaõ ñöôïc theâm vaøo töø ñieån”. 3. Giao dieän Ngöõ phaùp Giao dieän naøy goàm hai chöùc naêng: moät laø hieån thò caùc baøi ngöõ phaùp töø cô baûn ñeán phöùc taïp, hai laø cho pheùp ngöôøi söû duïng in ra baøi ngöõ phaùp ñoù. Ngöôøi söû duïng coù theå phoùng to, thu nhoû giao dieän trong quaù trình ñoïc. Nuùt hieån thò tieâu ñeà caùc baøi hoïc Ngöõ phaùp. Danh saùch caùc baøi hoïc ngöõ phaùp. Nuùt in baøi hoïc tieáng Nga. 4. Giao dieän Baøi taäp Treân giao dieän naøy, ngöôøi duøng ñöôïc pheùp choïn moät trong soá caùc baøi taäp trong danh saùch ñöôïc lieät keâ saún. Sau khi choïn baøi taäp thì nhaán nuùt BAÉT ÑAÀU ñeå hieån thò caâu hoûi vaø tieáp tuïc nhaán nuùt TIEÁP THEO ñeå xuaát hieän caùc caâu hoûi tieáp theo cuûa baøi taäp ñoù. Caùc baøi taäp coù daïng traéc nghieäm, beân döôùi moãi caâu hoûi seõ coù caùc caâu traû lôøi vaø ngöôøi söû duïng choïn ra caâu traû lôøi ñuùng nhaát trong soá chuùng ñeå ñaùnh daáu vaøo caùc oâ choïn A, B, C. Choïn xong caâu traû lôøi cho caùc caâu hoûi, ngöôøi duøng coù theå kieåm tra laïi caâu traû lôøi cuûa mình baèng caùch choïn muïc SÖÛA LOÃI hoaëc kieåm tra soá caâu ñuùng vaø soá caâu sai cuûa mình sau khi thöïc hieän ñaùnh daáu traéc nghieäm baøi taäp baát kyø qua muïc KEÁT QUAÛ . Ngöôøi söû duïng coù theå thoaùt khoûi chöông trình baøi taäp baèng caùch baám THOAÙT. Hình aûnh choïn baøi taäp. Baûng choïn caâu traû lôøi. Muïc hieån thò baûng keát quaû. Muïc söûa laïi keát quaû ñuùng. 5. Giao dieän Luyeän nghe Giao dieän cho pheùp ngöôøi duøng choïn moät trong soá caùc baøi nghe ñöôïc lieät keâ trong danh saùch ñeå thöïc haønh. Moät baøi nghe goàm hai cheá ñoä: Nghe ñoïc vaø Nghe. ÔÛ cheá ñoä nghe, ngöôøi duøng chæ ñöôïc hoã trôï veà töø vöïng trong muïc Ghi nhôù vaø döïa vaøo löôïng töø vöïng ñöôïc cung caáp ñeå ñoaùn noäi dung baøi ñoïc. Ngöôïc laïi, cheá ñoä Nghe ñoïc hieån thò caû noäi dung baøi ñoïc ñeå ngöôøi duøng nhaän bieát ñöôïc aâm cuûa töø hoaëc ñeå kieåm tra laïi baøi ñoïc sau khi nghe. 6. Trang giôùi thieäu ñeà taøi Phaàn V: NHÖÕNG KHOÙ KHAÊN, THUAÄN LÔÏI VAØ HÖÔÙNG PHAÙT TRIEÅN CHÖÔNG TRÌNH 1. Nhöõng khoù khaên Khi baét ñaàu thöïc hieän, chöông trình gaëp phaûi moät soá khoù khaên sau: - Vì chöông trình hoïc Tieáng Nga laø moät öùng duïng môùi neân vieäc tham khaûo veà noäi dung vaø kieåu daùng gaëp khoâng ít khoù khaên. - Moät soá font tieáng Nga coù saún khoâng hoã trôï daáu nhaán troïng aâm cuûa töø, do ñoù trong quaù trình söû duïng, ngöôøi duøng baét buoäc phaûi cheøn theâm daáu naøy ôû font khaùc. Ñieàu naøy gaây maát thôøi gian vaø khoù khaên cho ngöôøi duøng. - Maõ kí töï tieáng Nga khoâng theo thöù töï nhaát ñònh gaây khoù khaên cho vieäc saép xeáp töø trong töø ñieån. - Vieäc nhaäp döõ lieäu cho chöông trình gaëp trôû ngaïi trong vieäc chuyeån ñoåi boä goõ giöõa tieáng Nga vaø tieáng Vieät. - Caáu truùc con troû laø kieåu caáu truùc töông ñoái khoù thöïc hieän khi môùi baét ñaàu laøm quen. - Moät heä thoáng caùc baøi ñoïc, baøi taäp vaø baøi ngöõ phaùp hoaøn chænh ñoøi hoûi moät thôøi gian bieân soaïn vaø thu thaäp laâu daøi. 2. Thuaän lôïi - Hieän nay, ngaøy caøng coù nhieàu phaàn meàm öùng duïng raát tieän ích cho quaù trình xaây döïng heä thoáng aâm thanh, aûnh döõ lieäu, aûnh neàn, bieåu töôïng, font chöõ cuûa chöông trình. Caùc phaàn meàm ñoù laø: Photoshop, Photographer, VcdCutter, JetAudio,.... - Taøi lieäu veà Tieáng Nga tuy cuõ nhöng vaãn raát phong phuù, ña daïng. - Ñeà taøi ñöôïc thöïc hieän döôùi söï coá vaán vaø giuùp ñôõ cuûa caùc giaùo vieân tieáng Nga laâu naêm. - Neáu ñeà taøi ñöôïc hoaøn thieän thì noù coù theå ñöôïc öùng duïng roäng raõi, ñaëc bieät cho caùc baïn thích thuù muoán laøm quen vôùi Tieáng Nga, moät ngoân ngöõ voán raát phoå bieán tröôùc ñaây, cuõng nhö caùc baïn sinh vieân ñang hoïc ngoaïi ngöõ naøy trong nhaø tröôøng ( caùc tröôøng cao ñaúng, ñaïi hoïc treân toaøn quoác ). Hieän taïi, neáu ñöôïc thöïc hieän hoaøn taát thì ñeà taøi naøy seõ ñöôïc thöû nghieäm taïi khoa tieáng Nga tröôøng Cao ñaúng Sö phaïm Nha Trang, ñaây laø cô hoäi ñeå ñeà taøi coù theå tieáp tuïc ñöôïc chænh söûa vaø hoaøn thieän theâm. 3. Höôùng khaéc phuïc vaø phaùt trieån chöông trình Ñeå khaéc phuïc nhöõng thieáu soùt coøn laïi, caàn coù moät thôøi gian daøi tìm hieåu vaø thöû nghieäm thöïc teá. Ngoaøi ra chöông trình coù theå phaùt trieån theâm: + Moät soá töø ñieån nhö: Töø ñieån Anh – Nga, Töø Ñieån Tin Hoïc, Töø ñieån cô khí,… . + Caùc taøi lieäu ngöõ phaùp naâng cao keøm theo baøi taäp öùng duïng. + Caùc baøi nghe vôùi ñuû caùc caáp ñoä vaø cho pheùp ngöôøi söû duïng ñaùnh giaù ñöôïc trình ñoä nghe cuûa mình. ......... Phaàn VII: KEÁT LUAÄN Coù theå noùi ngoân ngöõ Delphi hoã trôï haàu heát caùc kieåu döõ lieäu caàn thieát cho vieäc thieát keá caáu truùc moät chöông trình Töø Ñieån. ÔÛ ñaây caáu truùc döõ lieäu kieåu con troû ñöôïc söû duïng ñeå thieát laäp caáu truùc caây Töø Ñieån, trong chöông trình moãi nuùt treân caây coù caáu truùc laø moät baûn ghi moùc noái goàm 3 tröôøng: Type TNode = ^Node; Node = record Info: char; Left, Right: TNode; End; Ñoái vôùi daïng caây Töø Ñieån ñaõ noùi ôû treân ta thaáy caây Töø Ñieån laø moät caây daïng toång quaùt coù tieàn toá chung. Nhöng ñeå ôû daïng caây toång quaùt thì vieäc thöïc hieän caùc thao taùc vaø caùc pheùp xöû lyù treân caây khoù khaên, cho neân caây ñöôïc chuyeån veà daïng caây nhò phaân vôùi thuaät toaùn chuyeån ñaõ trình baøy. Qua daïng caáu truùc cuûa caây nhò phaân Töø Ñieån ta coù nhaän xeùt chung: Moät töø luoân ñöôïc keát thuùc treân nhaùnh caây con traùi. Caùc töø coù tieàn toá chung khi chuùng laø caây con phaûi cuûa nuùt con traùi cuûa nuùt chöùa kí töï cuoái cuøng thuoäc chuoãi tieàn toá. Töø nhaän xeùt treân chuùng ta coù theå xaây döïng ñöôïc caùc giaûi thuaät tìm kieám, theâm, loaïi boû… moät caùch chính xaùc. Trong chöông trình, caùc giaûi thuaät ñöôïc thöïc hieän theo Heuristic nhaèm traùnh loãi traøn boä nhôù maø caùc giaûi thuaät ñeä qui maéc phaûi, tuy nhieân caùc phöông phaùp thöïc hieän giaûi thuaät naøy coù theå khoâng nhanh baèng giaûi thuaät ñeä qui. Haàu heát caùc form ñöôïc xaây döïng töø Form DLL neân quaù trình noái keát giöõa caùc Form raát thuaän tieän, nhanh choùng. Theâm vaøo ñoù, söï hoã trôï cuûa caùc haøm, thuû tuïc DLL trong quaù trình bieân dòch laøm chöông trình chính vì theá maø linh hoaït hôn. Trong thôøi gian thöïc taäp vöøa qua chöông trình ñaõ ñaït ñöôïc moät soá keát quaû khaû quan, mong raèng trong thôøi gian tôùi cuøng söï giuùp ñôõ, goùp yù cuûa caùc thaày coâ vaø caùc baïn, chöông trình seõ ñöôïc chænh söûa ñeå ngaøy caøng hoaøn thieän. TAØI LIEÄU THAM KHAÛO [1] “Caáu truùc döõ lieäu vaø giaûi thuaät” – Ñoã Xuaân Loâi – Nhaø xuaát baûn khoa hoïc vaø kyõ thuaät. [2] “Nhaäp moân thuaät toaùn vaø caáu truùc döõ lieäu” – J.Courtin I.Kowarski – do nhoùm taùc giaû: Ñaøo Nam Anh, Traàn Ñình Queá, Phaïm Ngoïc Khoâi dòch vaø hieäu ñính. [3] “Laäp trình naâng cao vôùi caùc kieåu döõ lieäu caáu truùc cuûa PASCAL” (2 taäp) – N.Wirth – do Leâ Minh Trung dòch. [4] “Caáu truùc döõ lieäu” – Nguyeãn Trung Tröïc – Tröôøng Ñaïi Hoïc Baùch Khoa TP.HCM. [5] “Caåm nang thuaät toaùn” – Taäp 1: “Caùc thuaät toaùn thoâng duïng” – Robert Sedgewick – Nhaø xuaát baûn khoa hoïc vaø kyõ thuaät. [6] Taäp san “Tin hoïc vaø nhaø tröôøng” – Soá 1-2 (40 - 41). [7] “Giaùo trình lyù thuyeát vaø baøi taäp Borland DelPhi” – Leâ Phöông Lan & Hoaøng Ñöùc Haûi – Nhaø xuaát baûn giaùo duïc. [8] “Caùc kyõ xaûo laäp trình vôùi Microsoft Visual Basic vaø Borland Delphi” – Leâ Höõu Ñaït (Chuû bieân)– Nhaø xuaát baûn giaùo duïc. [9] “Nhaäp moân caáu truùc döõ lieäu vaø giaûi thuaät” – Traàn Haïnh Nhi, Döông Anh Ñöùc, Hoaøng Kieám – Ñaïi hoïc Khoa Hoïc Töï Nhieân