Báo cáo giáo trình cấu trúc dữ liệu và giải thuật kỹ thuật tìm kiếm Searching, SORTING, LIST, TREE

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

Cấu Trúc Dữ Liệu và Giải Thuật là một trong những môn học cơ bản của sinh viên ngành Công nghệ thông tin. Các cấu trúc dữ liệu và các giải thuật được xem như là hai yếu tố quan trọng nhất trong ngành lập trình, đúng như câu nói nổi tiếng của Niklaus Wirth: Chương trình = Cấu trúc dữ liệu + Giải thuật (Programs = Data Structues + Algỏithms). Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sở để sinh viên tiếp cận với các thiết kế và xây dựng phần mềm cũng như sử dụng các công cụ lập trình hiện đại.

MỤC LỤC

CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ………..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: KỸ THUẬT TÌM KIẾ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: KỸ THUẬT SẮP XẾ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
CHƯONG 4: DANH SACH (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: CÂ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
TÀI LIỆU THAM KHẢO ………………………………………………………..229