Cấu trúc dữ liệu và giải thuật - ĐH CNTT Kỹ Thuật Hưng Yên

Tài liệu "Cấu trúc dữ liệu và giải thuật - ĐH CNTT Kỹ Thuật Hưng Yên" gồm 15 bài với nội dung: giải thuật và cấu trúc dữ liệu, phân tích và thiết kế bài toán, phân tích thời gian thực hiện giải thuật, mảng và danh sách,...
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - ĐH CNTT Kỹ Thuật Hưng Yên C u trúc d li u và gi i thu t B i: Khoa CNTT ĐHSP KT Hưng Yên Tài li u này và s biên t p n i dung có b n quy n thu c v Khoa CNTT ĐHSP KT Hưng Yên. Tài li u này tuân th gi y phép Creative Commons Attribution 3.0 (http://creativecommons.org/licenses/by/3.0/). Tài li u đư c hi u đính b i: August 13, 2010 Ngày t o PDF: August 19, 2010 Đ bi t thông tin v đóng góp cho các module có trong tài li u này, xem tr. 118. N i dung 1 M cl c 1.1 M c l c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Bài 1: Gi i thu t và c u trúc d li u 2.1 Gi i thu t và c u trúc d li u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Bài 2: Phân tích và thi t k bài toán 3.1 Phân tích và thi t k bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Bài 3: Phân tích th i gian th c hi n gi i thu t 4.1 Phân tích th i gian th c hi n thu t toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5 Bài 4: M ng và danh sách 5.1 M ng và danh sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6 Bài 5: Danh sách n i đơn (Singlely Linked List) 6.1 Danh sách n i đơn (Singlely Linked List) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7 Bài 6: Th c hành cài đ t danh sách n i đơn 7.1 Th c hành và cài đ t danh sách n i đơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8 Bài 7: Danh sách tuy n tình ngăn x p (Stack) 8.1 Danh sách tuy n tính ngăn x p (Stack) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 9 Bài 8: Danh sách tuy n tình hàng đ i (Queue) 9.1 Danh sách tuy n tính ki u hàng đ i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 10 Bài 9: Th c hành danh sách Queue 10.1 Th c hành cái đ t danh sách ki u hàng đ i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 11 Bài 10: Danh sách n i vòng và n i kép 11.1 Danh sách n i vòng và n i kép . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 12 Bài 11: Th c hành danh sách liên k t kép 12.1 Th c hành cài đ t danh sách liên k t kép . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 13 Bài 12: D li u ki u cây 13.1 Ki u d li u cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 14 Bài 13: Th c hành cài đ t cây nh phân 14.1 Th c hành cài đ t cây nh phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 109 15 Bài 14: Cây nh phân và ng d ng 15.1 Cây nh phân và ng d ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 16 Bài 15: Th c hành cài đ t cây nh phân tìm ki m 16.1 Th c hành cài đ t cây nh phân tìm ki m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Attributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .118 iv Chương 1 M cl c 1.1 M c l c1 M CL C2 M CL C Trong khoa h c máy tính2 , c u trúc d li u là m t cách lưu d li u3 trong máy tính4 sao cho nó có th đư c s d ng m t cách hi u qu . Thông thư ng, m t c u trúc d li u đư c ch n c n th n s cho phép th c hi n thu t toán5 hi u qu hơn. Vi c ch n c u trúc d li u thư ng b t đ u t ch n m t c u trúc d li u tr u tư ng6 . M t c u trúc d li u đư c thi t k t t cho phép th c hi n nhi u phép toán, s d ng càng ít tài nguyên, th i gian x lý và không gian b nh càng t t. Các c u trúc d li u đư c tri n khai b ng cách s d ng các ki u d li u7 , các tham chi u8 và các phép toán trên đó đư c cung c p b i m t ngôn ng l p trình9 . Trong thi t k nhi u lo i chương trình, vi c ch n c u trúc d li u là v n đ quan tr ng. Kinh nghi m trong vi c xây d ng các h thóng l n cho th y khó khăn c a vi c tri n khai chương trình, ch t lư ng và hi u năng c a k t qu cu i cùng ph thu c r t nhi u vào vi c ch n c u trúc d li u t t nh t. Sau khi c u trúc d li u đư c ch n, ngư i ta thư ng d nh n th y thu t toán10 c n s d ng. Đôi khi trình t công vi c di n ra theo th t ngư c l i: c u trúc d li u đư c ch n do nh ng bài toán quan tr ng nh t đ nh có thu t toán ch y t t nh t v i m t s c u trúc d li u c th . Trong c hai trư ng h p, vi c l a ch n c u trúc d li u là r t quan tr ng. Trong modul này, v i th i lư ng h n ch , ch trình bày nh ng v n đ cơ b n nh t c a c u trúc d li u như danh sách n i đơn, kép, ngăn x p, hàng đ i, cây. Còn r t nhi u c u trúc d li u m nh khác như t p h p, b ng băm, B-tree,. . . mà modul này không đ th i lư ng trình bày. Ngoài ra, thu t toán cũng đư c trình bày r t ng n g n đi li n v i c u trúc d li u tương ng. Vì thu t toán là m t lĩnh v c quan tr ng và r ng ...