zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1

Chia sẻ: Gray Swan | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

274
lượt xem 61
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1.1. Tầm quan trọng của cấu trúc dữ liệu và giải thuật trong một đề án tin học 1.1.1. Xây dựng cấu trúc dữ liệu Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.