1
Cấutrúcdữliệu
và giảithuật
Ngườithựchiện: GVC. TS. Nguyễn Trung Hòa
Email: ntrhoa@yahoo.com
Điệnthoại: 0904 162168
Tài liệuthamkhảo
1. Cấutrúcdữliệuvàgiảithuật
Đỗ Xuân Lôi, NXB ĐHQGHN,2004
2. Cẩm nang thuật toán
R. Sedgewick, NXB Khoa họcvàKỹ
thuật,1994
Đề cương chương trình
2
Chương 1. Giảithuật
1.1. Khái niệmgiảithuật
1.2. Thiếtkếgiảithuật
1.3. Phân tích và đánh giá giảithuật
1.1. Khái niệmgiảithuật
1.1.1. Giảithuậtlàgì?
1.1.2. Cấutrúcdữliệu
1.1.3. Diễnđạtgiảithuật
3
1.1.1. Giảithuậtlàgì?
1.1.1. Giảithuậtlàgì?
Ví dụmởđầu
Cho một dãy các sốthựca
1,a2,…,an. Tìm giá trị
lớnnhấtm củacácsốđã cho và chỉsốlớnnhấti
trong các sốđạtgiátrịm.
Vì phảitìmsốlớnnhấtvớichỉsốlớnnhất, ta sẽ
xuất phát từsốcuốicùngcủadãylàa
nvà sẽso
sánh vớicác sốtrướcđó, khi tìm thấymộtgiátrị
lớnhơnthìtaghi lại(đánh dấu) và lạitiếptụcso
sánh sốnày vớicác sốtrướcđó, công việcsẽ
đượcthựchiệnchođếnkhiđãso vớisốđầutiên.
4
1.1.1. Giảithuậtlàgì?
Giảithuậtlà:
Cách làm để giải quyết bài toán
Một dãy có trình tựcác thao tác trên mộtsốđối
tượng nào đósaochosau mộtsốhữuhạnbước
thựchiệnta đạtđượckếtquảmong muốn.
Mộtgiảithuậtcó
Đầu vào (Input): tậpcácđốitượng (dữliệu)
Đầu ra(Output): mộttập các giá trị(thông tin)
Các bướcthựchiện
Vào Ra
1.1.1. Giảithuậtlàgì?
Các đặctrưng củagiảithuật
Tính có đạilượng vào/ra
Tính xác định
Tính hữuhạn(tínhdừng)
Tính tổng quát
Tính hiệuquả
Mộtvàiđặcđiểmcầnlưuý
Không cầnbiếtgiátrịcụthểcủakếtquảsau mỗibước, chỉ
cầnbiết cách chuyểntừbướctrướctớibước sau;
Kếtquảcụthểcủagiảithuậtcóthểkhông phảilàkếtquả
đúng (chính xác) mặcdầuphương pháp là đúng.
5
1.1.2. Cấutrúcdữliệu
Dữliệucócấutrúc:
Tậphợpdữliệu
Có mốiquanhệvới nhau trong bài toán xác định
Lựachọncấutrúcdữliệuvàgiảithuậtthíchhợp: rất
quan trọng
Vídụ: viếtchương trình tìm kiếmsốđiệnthoại theo tên đơn
vị
Giảithuật+ Dữliệu= Chương trình
Biểudiễncấutrúcdữliệu trong bộnhớ:
Lưutrữtrong
Thông qua các biến
Lưutrữngoài
Tệp(định kiểuvàkhôngđịnh kiểu)
1.1.3. Diễnđạtgiảithuật
Ngôn ngữtựnhiên
Ngôn ngữliệtkêcácbước