Download miễn phí Giáo trình Cấu trúc dữ liệu và giải thuật (5 chương)
MỤC LỤC
Mục Trang
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & GT .3
1.1. Tầm quan trọng của CTDL & GT trong một đề án tin học . 3
1.1.1. Xây dựng cấu trúc dữ liệu . 3
1.1.2. Xây dựng giải thuật . 3
1.1.3. Mối quan hệ giữa cấu trúc dữ liệu vàgiải thuật . 3
1.2. Đánh giá Cấu trúc dữ liệu & Giải thuật . 3
1.2.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu . 3
1.2.2. Đánh giá độ phức tạp của thuật toán . 4
1.3. Kiểu dữ liệu . 4
1.3.1. Khái niệm về kiểu dữ liệu . 4
1.3.2. Các kiểu dữ liệu cơ sở . 4
1.3.3. Các kiểu dữ liệu có cấu trúc. 5
1.3.4. Kiểu dữ liệu con trỏ. 5
1.3.5. Kiểu dữ liệu tập tin. 5
Câu hỏi và bài tập . 6
CHƯƠNG 2: KỸ THUẬT TÌM KIẾM (Searching) .8
2.1. Khái quát về tìm kiếm . 8
2.2. Các giải thuật tìm kiếm nội . 8
2.2.1. Đặt vấn đề . 8
2.2.2. Tìm tuyến tính. 8
2.2.3. Tìm nhị phân. 10
2.3. Các giải thuật tìm kiếm ngoại . 14
2.3.1. Đặt vấn đề . 14
2.3.2. Tìm tuyến tính. 14
2.3.3. Tìm kiếm theo chỉ mục . 16
Câu hỏi và bài tập . 17
CHƯƠNG 3: KỸ THUẬT SẮP XẾP (SORTING) . 19
3.1. Khái quát về sắp xếp . 19
3.2. Các giải thuật sắp xếp nội . 19
3.2.1 Sắp xếp bằng phương pháp đổi chỗ . 20
3.2.2. Sắp xếp bằng phương pháp chọn . 28
3.2.3. Sắp xếp bằng phương pháp chèn . 33
3.2.4. Sắp xếp bằng phương pháp trộn . 40
3.3. Các giải thuật sắp xếp ngoại . 60
3.3.1. Sắp xếp bằng phương pháp trộn . 60
3.3.2. Sắp xếp theo chỉ mục . 79
Câu hỏi và bài tập . 82
CHƯƠNG 4: DANH SÁCH (LIST) . 84
4.1. Khái niệm về danh sách . 84
4.2. Các phép toán trên danh sách . 84
4.3. Danh sách đặc . 85
4.3.1. Định nghĩa . 85
4.3.2. Biểu diễn danh sách đặc. 85
4.3.3. Các thao tác trên danh sách đặc . 85
4.3.4. Ưu nhược điểm và Ứng dụng . 91
4.4. Danh sách liên kết . 92
4.4.1. Định nghĩa . 92
4.4.2. Danh sách liên kết đơn . 92
4.4.3. Danh sách liên kết kép . 111
4.4.4. Ưu nhược điểm của danh sách liên kết . 135
4.5. Danh sách hạn chế . 135
4.5.1. Hàng đợi. 135
4.5.2. Ngăn xếp . 142
4.5.3. Ứng dụng của danh sách hạn chế. 147
Câu hỏi và bài tập . 147
CHƯƠNG 5: CÂY (TREE) . 149
5.1. Khái niệm – Biểu diễn cây. 149
5.1.1. Định nghĩa cây . 149
5.1.2. Một số khái niệm liên quan . 149
5.1.3. Biểu diễn cây . 151
5.2. Cây nhị phân . 152
5.2.1. Định nghĩa . 152
5.2.2. Biểu diễn và Các thao tác . 152
5.2.3. Cây nhị phân tìm kiếm. 163
5.3. Cây cân bằng . 188
5.3.1. Định nghĩa – Cấu trúc dữ liệu. 188
5.3.2. Các thao tác . 189
Câu hỏi và bài tập . 227
ÔN TẬP (REVIEW) . 224
Hệ thống lại các Cấu trúc dữ liệu và cácGiải thuật đã học. 224
Câu hỏi và Bài tập ôn tập tổng hợp . 227
TÀI LIỆU THAM KHẢO . 229
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
où 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, <,
>, =, =, …}
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
Trang: 5
- 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ù.
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
Trang: 6
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):
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
H AØ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
TH ANH 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ù.
∑
=
=
n
i
i
i xaxfn
0
)(
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
Trang: 7
- Xuaát ra giôø ñeán caùc ga cuûa moät taøu T 0 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”.
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
Trang: 8
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 v...