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

H C VI N CÔNG NGH BUU CHÍNH VI N THÔNG
C U TRÚC D LI U VÀ GI I THU T
(Dùng cho sinh viên h dào t o d i h c t xa)
Luu hành n i b
HÀ N I - 2007


L I NÓI Ð U
C u trúc d li u và gi i thu t là m t trong nh ng môn h c co 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 du c xem nhu là 2 y u t quan tr ng nh t
trong l p trình, dúng nhu câu nói n i ti ng c a Niklaus Wirth: Chuong trình = C u trúc d li u +
Gi i thu t (Programs = Data Structures + Algorithms). N m v ng các c u trúc d li u và các gi i
thu t là co s d sinh viên ti p c n v i vi c thi t k và xây d ng ph n m m cu ng nhu s d ng các
công c l p trình hi n d i.
C u trúc d li u có th du c xem nhu là 1 phuong pháp luu tr d li u trong máy tính
nh m s d ng m t cách có hi u qu các d li u này. Và d s d ng các d li u m t cách hi u qu
thì c n ph i có các thu t toán áp d ng trên các d li u dó. Do v y, c u trúc d li u và gi i thu t là
2 y u t không th tách r i và có nh ng liên quan ch t ch v i nhau. Vi c l a ch n m t c u trúc
d li u có th s nh hu ng l n t i vi c l a ch n áp d ng gi i thu t nào.
Tài li u “C u trúc d li u và gi i thu t” bao g m 7 chuong, trình bày v các c u trúc d li u
và các gi i thu t co b n nh t trong tin h c.
Chuong 1 trình bày v phân tích và thi t k thu t toán. Ð u tiên là cách phân tích 1 v n d ,
t th c ti n cho t i chuong trình, cách thi t k m t gi i pháp cho v n d theo cách gi i quy t b ng
máy tính. Ti p theo, các phuong pháp phân tích, d ánh giá d ph c t p và th i gian th c hi n gi i
thu t cung du c xem xét trong chuong. Chuong 2 trình bày v d qui, m t khái ni m r t co b n
trong toán h c và khoa h c máy tính. Vi c s d ng d qui có th xây d ng du c nh ng chuong
trình gi i quy t du c các v n d r t ph c t p ch b ng m t s ít câu l nh, d c bi t là các v n d
mang b n ch t d qui.
Chuong 3, 4, 5, 6 trình bày v các c u trúc d li u du c s d ng r t thông d ng nhu m ng
và danh sách liên k t, ngan x p và hàng d i, cây, d th . Ðó là các c u trúc d li u cu ng r t g n
gui v i các c u trúc trong th c ti n. Chuong 7 trình bày v các thu t toán s p x p và tìm ki m.
Các thu t toán này cùng v i các k thu t du c s d ng trong dó du c coi là các k thu t co s
cho l p trình máy tính. Các thu t toán du c xem xét bao g m các l p thu t toán don gi n và c
các thu t toán cài d t ph c t p nhung có th i gian th c hi n t i uu.
Cu i m i ph n d u có các câu h i và bài t p d sinh viên ôn luy n và t ki m tra ki n th c
c a mình. Cu i tài li u có các ph l c hu ng d n tr l i câu h i, mã ngu n tham kh o và tài li u
tham kh o.
V nguyên t c, các c u trúc d li u và các gi i thu t có th du c bi u di n và cài d t b ng
b t c ngôn ng l p trình hi n d i nào. Tuy nhiên, d có du c các phân tích sâu s c hon và có k t
qu th c t hon, tác gi dã s d ng ngôn ng l p trình C d minh ho cho các c u trúc d li u và
thu t toán. Do