Xem mẫu
- 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
∑ i
fn ( x ) = aix
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
MÖÔNG MAÙN 2g10 15g21 19g53 14g07 16g41 21g04 1g15 3g16 17g35 22g58
THAÙP CHAØM 5g01 18g06 22g47 16g43 19g19 0g08 4g05 6g03 20g19 2g15
NHA TRANG 4g10 6g47 20g00 0g47 18g50 21g10 1g57 5g42 8g06 22g46 5g15
TUY HOØA 9g43 23g09 3g39 21g53 0g19 5g11 8g36 10g50 2g10
DIEÂU TRÌ 8g12 11g49 1g20 5g46 0g00 2g30 7g09 10g42 13g00 4g15
QUAÛNG NGAÕI 15g41 4g55 9g24 3g24 5g55 11g21 14g35 17g04 7g34
TAM KYØ 6g11 10g39 4g38 7g10 12g40 16g08 18g21 9g03
ÑAØ NAÜNG 13g27 19g04 8g29 12g20 6g19 9g26 14g41 17g43 20g17 10g53
HUEÁ 16g21 22g42 12g29 15g47 11g12 14g32 18g13 21g14 23g50 15g10
ÑOÂNG HAØ 0g14 13g52 17g12 12g42 16g05 19g38 22g39 1g25
ÑOÀNG HÔÙI 19g15 2g27 15g52 19g46 14g41 17g59 21g38 0g52 3g28
VINH 23g21 7g45 21g00 1g08 20g12 23g50 2g59 7g07 9g20
THANH HOÙA 10g44 0g01 4g33 23g09 3g33 6g39 9g59 12g20
NINH BÌNH 12g04 1g28 5g54 0g31 4g50 7g57 11g12 13g51
NAM ÑÒNH 12g37 2g01 6g26 1g24 5g22 8g29 11g44 14g25
PHUÛ LYÙ 13g23 2g42 7g08 2g02 6g00 9g09 12g23 15g06
ÑEÁN HAØ NOÄI 5g00 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
nguon tai.lieu . vn
