intTypePromotion=3

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

Chia sẻ: Trần Văn Nguyên | Ngày: | Loại File: PDF | Số trang:127

2
809
lượt xem
392
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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,...

Chủ đề:
Lưu

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

  1. C u trúc d li u và gi i thu t B i: Khoa CNTT ĐHSP KT Hưng Yên
  2. 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.
  3. 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
  4. iv
  5. 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 nên chương trình còn có modul “Phân tích thi t k thu t toán” h c kỳ sau. Hưng Yên, tháng 12 năm 2007 1 This content is available online at . 2 http://vi.wikipedia.org/wiki/Khoa_h c_máy_tính 3 http://vi.wikipedia.org/wiki/D _li u 4 http://vi.wikipedia.org/wiki/Máy_tính 5 http://vi.wikipedia.org/wiki/Thu t_toán 6 http://vi.wikipedia.org/w/index.php?title=C u_trúc_d _li u_tr u_tư ng&action=edit&redlink=1 7 http://vi.wikipedia.org/w/index.php?title=Ki u_d _li u&action=edit&redlink=1 8 http://vi.wikipedia.org/w/index.php?title=Tham_chi u&action=edit&redlink=1 9 http://vi.wikipedia.org/wiki/Ngôn_ng _l p_trình 10 http://vi.wikipedia.org/wiki/Thu t_toán 1
  6. 2 CHƯƠNG 1. M C L C Figure 1.1 Figure 1.2 Figure 1.3 Figure 1.4 Figure 1.5 Figure 1.6
  7. Chương 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 u1 2.1.1 GI I THU T Khi vi t m t chương trình máy tính, ta thư ng cài đ t m t phương pháp đã đư c nghĩ ra trư c đó đ gi i quy t m t v n đ . Phương pháp này thư ng là đ c l p v i m t máy tính c th s đư c dùng đ cài đ t: h u như nó thích h p cho nhi u máy tính. Trong b t kỳ trư ng h p nào, thìphương pháp, ch không ph i là b n thân chương trình máy tính là cái đư c nghiên c u đ h c cách làm th nào đ t n công vào bài toán. t “ Gi i thu t” hay “ Thu t toán” đư c dùng trong khoa h c máy tính đ mô t m t phương pháp gi i bài toán thích h p như là cài đ t các chương trình máy tính. Gi i thu t chúng là các đ i tư ng nghiên c u trung tâm trong h u h t các lĩnh v c c a Tin h c. Các chương trình máy tính thư ng quá t i ưu, đôi khi chúng ta không c n m t thu t toán quá t i ưu, tr khi m t thu t toán đư c dùng l i nhi u l n. N u không ch c n m t cài đ t đơn gi n và c n th n là đ đ ta có th tin tư ng r ng nó s ho t đ ng t t và nó có th ch y ch m hơn 5 đ n mư i l n m t phiên b n t t, đi u này có nghĩa nó có th ch y ch m hơn vài giây, trong khi n u ta ch n và thi t k m t cài đ t t i ưu và ph c t p ngay t đ u thì có th s t n nhi u phút, nhi u gi . . . Do v y đây ta s xem xét các cài đ t h p lý đơn gi n c a các thu t toán t t nh t. Thông thư ng đ gi i quy t m t bài toán ta có l a ch n nhi u thu t toán khác, vi c l a ch n m t thu t toán t t nh t là m t v n đ tương đ i khó khăn ph c t p, thư ng c n đ n m t quá trình phân tích tinh vi c a tin h c. Khái ni m Gi i thu t có t r t lâu do m t nhà toán h c ngư i Ar p phát ngôn, m t trong nh ng thu t toán n i ti ng có t th i c Hyl p là thu t toán Euclid (thu t toán tìm ư c s chung l n nh t c a 2 s ). Phương pháp c ng, nhân, chia. . . hai s cũng là m t gi i thu t. . . Trong Tin h c khái ni m v gi i thu t đư c trình bày như sau: Gi i thu t là các câu l nh (Statements) ch t ch và rõ ràng xác đ nh m t trình t các thao tác trên m t s đ i tư ng nào đó sao cho sau m t s h u h n bư c th c hi n ta đ t đư c k t qu mong mu n. (Thu t toán là m t dãy h u h n các bư c, m i bư c mô t chính xác các phép toán ho c hành đ ng c n th c hi n, đ gi i quy t m t v n đ ). Đ i tư ng ch ra đây chính là Input và k t qu mong mu n chính là Output trong thu t toán Euclid trên 2.1.2 M I QUAN H GI A C U TRÚC D LI U VÀ GI I THU T Th c hi n m t đ án tin h c là chuy n bài toán th c t thành bài toán có th gi i quy t trên máy tính. M t bài toán th c t b t kỳ đ u bao g m các đ i tư ng d li u và các yêu c u x lý trên nh ng đ i tư ng đó. 1 This content is available online at . 3
  8. 4 CHƯƠNG 2. BÀI 1: GI I THU T VÀ C U TRÚC D LI U Vì th , đ xây d ng m t mô hình tin h c ph n ánh đư c bài toán th c t c n chú tr ng đ n hai v n đ : 2.1.2.1 T ch c bi u di n các đ i tư ng th c t : Các thành ph n d li u th c t đa d ng, phong phú và thư ng ch a đ ng nh ng quan h nào đó v i nhau, do đó trong mô hình tin h c c a bài toán, c n ph i t ch c , xây d ng các c u trúc thích h p nh t sao cho v a có th ph n ánh chính xác các d li u th c t này, v a có th d dàng dùng máy tính đ x lý. Công vi c này đư c g i là xây d ng c u trúc d li u cho bài toán. 2.1.2.2 Xây d ng các thao tác x lý d li u: T nh ng yêu c u x lý th c t , c n tìm ra các gi i thu t tương ng đ xác đ nh trình t các thao tác máy tính ph i thi hành đ cho ra k t qu mong mu n, đây là bư c xây d ng gi i thu t cho bài toán. Tuy nhiên khi gi i quy t m t bài toán trên máy tính, chúng ta thư ng có khuynh hư ng ch chú tr ng đ n vi c xây d ng gi i thu t mà quên đi t m quan tr ng c a vi c t ch c d li u trong bài toán. Gi i thu t ph n ánh các phép x lý , còn đ i tư ng x lý c a gi i thu t l i là d li u, chính d li u ch a đ ng các thông tin c n thi t đ th c hi n gi i thu t. Đ xác đ nh đư c gi i thu t phù h p c n ph i bi t nó tác đ ng đ n lo i d li u nào (ví d đ làm nhuy n các h t đ u , ngư i ta dùng cách xay ch không băm b ng dao, vì đ u s văng ra ngoài) và khi ch n l a c u trúc d li u cũng c n ph i hi u rõ nh ng thao tác nào s tác đ ng đ n nó (ví d đ bi u di n các đi m s c a sinh viên ngư i ta dùng s th c thay vì chu i ký t vì còn ph i th c hi n thao tác tính trung bình t nh ng đi m s đó). Như v y trong m t đ án tin h c, gi i thu t và c u trúc d li u có m i quan h ch t ch v i nhau, đư c th hi n qua công th c : C u trúc d li u + Gi i thu t = Chương trình V i m t c u trúc d li u đã ch n, s có nh ng gi i thu t tương ng, phù h p. Khi c u trúc d li u thay đ i thư ng gi i thu t cũng ph i thay đ i theo đ tránh vi c x lý gư ng ép, thi u t nhiên trên m t c u trúc không phù h p. Hơn n a, m t c u trúc d li u t t s giúp gi i thu t x lý trên đó có th phát huy tác d ng t t hơn, v a đáp ng nhanh v a ti t ki m v t tư, gi i thu t cũng d hi u và đơn gi n hơn. Ví d 1.1: M t chương trình qu n lý đi m thi c a sinh viên c n lưu tr các đi m s c a 3 sinh viên. Do m i sinh viên có 4 đi m s ng v i 4 môn h c khác nhau nên d li u có d ng b ng như sau: Sinh viên Môn 1 Môn 2 Môn3 Môn4 SV 1 7 9 5 2 SV 2 5 0 9 4 SV 3 6 3 7 4 Table 2.1 Ch xét thao tác x lý là xu t đi m s các môn c a t ng sinh viên. Gi s có các phương án t ch c lưu tr sau: Phương án 1 : S d ng m ng m t chi u Có t t c 3(SV)*4(Môn) = 12 đi m s c n lưu tr , do đó khai báo m ng result như sau : int result [ 12 ] = {7, 9, 5, 2,5, 0, 9, 4,6, 3, 7, 4}; khi đó trong m ng result các ph n t s đư c lưu tr như sau:
  9. 5 Figure 2.1 Và truy xu t đi m s môn j c a sinh viên i - là ph n t t i (dòng i, c t j) trong b ng - ph i s d ng m t công th c xác đ nh ch s tương ng trong m ng result: b ngđi m(dòng i, c t j) ⇒ result[((i-1)*s c t) + j] Ngư c l i, v i m t ph n t b t kỳ trong m ng, mu n bi t đó là đi m s c a sinh viên nào, môn gì, ph i dùng công th c xác đ nh sau result[ i ] ⇒ b ngđi m (dòng((i / s c t) +1), c t (i % s c t) ) V i phương án này, thao tác x lý đư c cài đ t như sau : void XuatDiem() //Xu t đi m s c a t t c sinh viên{ const int so_mon = 4;int sv,mon;for (int i=0; i
  10. 6 CHƯƠNG 2. BÀI 1: GI I THU T VÀ C U TRÚC D LI U 2.1.3 CÁC TIÊU CHU N ĐÁNH GIÁ C U TRÚC D LI U Do t m quan tr ng đã đư c trình bày trong ph n 1.1, nh t thi t ph i chú tr ng đ n vi c l a ch n m t phương án t ch c d li u thích h p cho đ án. M t c u trúc d li u t t ph i th a mãn các tiêu chu n sau : 2.1.3.1 Ph n ánh đúng th c t : Đây là tiêu chu n quan tr ng nh t, quy t đ nh tính đúng đ n c a toàn b bài toán. C n xem xét k lư ng cũng như d trù các tr ng thái bi n đ i c a d li u trong chu trình s ng đ có th ch n c u trúc d li u lưu tr th hi n chính xác đ i tư ng th c t . Ví d 1.2 : M t s tình hu ng ch n c u trúc lưu tr sai : - Ch n m t bi n s nguyên int đ lưu tr ti n thư ng bán hàng (đư c tính theo công th c ti n thư ng bán hàng = tr giá hàng * 5%), do v y s làm tròn m i giá tr ti n thư ng gây thi t h i cho nhân viên bán hàng. Trư ng h p này ph i s d ng bi n s th c đ ph n ánh đúng k t qu c a công th c tính th c t . - Trong trư ng trung h c, m i l p có th nh n t i đa 28 h c sinh. L p hi n có 20 h c sinh, m i tháng m i h c sinh đóng h c phí $10. Ch n m t bi n s nguyên unsigned char ( kh năng lưu tr 0 - 255) đ lưu tr t ng h c phí c a l p h c trong tháng, n u x y ra trư ng h p có thêm 6 h c sinh đư c nh n vào l p thì giá tr t ng h c phí thu đư c là $260, vư t kh i kh năng lưu tr c a bi n đã ch n, gây ra tình tr ng tràn, sai l ch. 2.1.3.2 Phù h p v i các thao tác trên đó: Tiêu chu n này giúp tăng tính hi u qu c a đ án: vi c phát tri n các thu t toán đơn gi n, t nhiên hơn; chương trình đ t hi u qu cao hơn v t c đ x lý. Ví d 1.3 : M t tình hu ng ch n c u trúc lưu tr không phù h p: C n xây d ng m t chương trình so n th o văn b n, các thao tác x lý thư ng x y ra là chèn, xoá s a các ký t trên văn b n. Trong th i gian x lý văn b n, n u ch n c u trúc lưu tr văn b n tr c ti p lên t p tin thì s gây khó khăn khi xây d ng các gi i thu t c p nh t văn b n và làm ch m t c đ x lý c a chương trình vì ph i làm vi c trên b nh ngoài. Trư ng h p này nên tìm m t c u trúc d li u có th t ch c b nh trong đ lưu tr văn b n su t th i gian so n th o. LƯU Ý : Đ i v i m i ng d ng , c n chú ý đ n thao tác nào đư c s d ng nhi u nh t đ l a ch n c u trúc d li u cho thích h p. 2.1.3.3 Ti t ki m tài nguyên h th ng: C u trúc d li u ch nên s d ng tài nguyên h th ng v a đ đ đ m nhi m đư c ch c năng c a nó. Thông thư ng có 2 lo i tài nguyên c n lưu tâm nh t : CPU và b nh . N u t ch c s d ng đ án c n có nh ng x lý nhanh thì khi ch n c u trúc d li u y u t ti t ki m th i gian x lý ph i đ t n ng hơn tiêu chu n s d ng t i ưu b nh , và ngư c l i. Ví d 1.4: M t s tình hu ng ch n c u trúc lưu tr lãng phí: - S d ng bi n int (2 bytes) đ lưu tr m t giá tr cho bi t tháng hi n hành . Bi t r ng tháng ch có th nh n các giá tr t 1-12, nên ch c n s d ng ki u char (1 byte) là đ . - Đ lưu tr danh sách h c viên trong m t l p, s d ng m ng 50 ph n t (gi i h n s h c viên trong l p t i đa là 50). N u s lư ng h c viên th t s ít hơn 50, thì gây lãng phí. Trư ng h p này c n có m t c u trúc d li u linh đ ng hơn m ng- ví d danh sách liên k t - s đư c bàn đ n trong các bài sau.
  11. Chương 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án1 3.1.1 CÁC BƯ C CƠ B N Đ GI I QUY T BÀI TOÁN Xác đ nh bài toán Input → Process → Output (D li u vào → X lý → K t qu ra) Vi c xác đ nh bài toán t c là ph i xác đ nh xem ta ph i gi i quy t v n đ gì?, v i gi thi t nào đã cho và l i gi i c n ph i đ t nh ng yêu c u gì. Khác v i bài toán thu n tuý toán h c ch c n xác đ nh rõ gi thi t và k t lu n ch không c n xác đ nh yêu c u v l i gi i, đôi khi nh ng bài toán tin h c ng d ng trong th c t ch c n tìm l i gi i t t t i m c nào đó, th m chí là t i m c ch p nh n đư c. B i l i gi i t t nh t đòi h i quá nhi u th i gian và chi phí. Ví d 2.1: Khi cài đ t các hàm s ph c t p trên máy tính. N u tính b ng cách khai tri n chu i vô h n thì đ chính xác cao hơn nhưng th i gian ch m hơn hàng t l n so v i phương pháp x p x . Trên th c t vi c tính toán luôn luôn cho phép ch p nh n m t sai s nào đó nên các hàm s trong máy tính đ u đư c tính b ng phương pháp x p x c a gi i tích s . Xác đ nh đúng yêu c u bài toán là r t quan tr ng b i nó nh hư ng t i cách th c gi i quy t và ch t lư ng c a l i gi i. M t bài toán th c t thư ng cho b i nh ng thông tin khá mơ h và hình th c, ta ph i phát bi u l i m t cách chính xác và ch t ch đ hi u đúng bài toán. Ví d 2.2: Bài toán: M t d án có n ngư i tham gia th o lu n, h mu n chia thành các nhóm và m i nhóm th o lu n riêng v m t ph n c a d án. Nhóm có bao nhiêu ngư i thì đư c trình lên b y nhiêu ý ki n. N u l y m i nhóm m t ý ki n đem ghép l i thì đư c m t b ý ki n tri n khai d án. Hãy tìm cách chia đ s b ý ki n cu i cùng thu đư c là l n nh t. Phát bi u l i: Cho m t s nguyên dương n, tìm các phân tích n thành t ng các s nguyên dương sao cho tích c a các s đó là l n nh t. Trên th c t , ta nên xét m t vài trư ng h p c th đ thông qua đó hi u đư c bài toán rõ hơn và th y đư c các thao tác c n ph i ti n hành. Đ i v i nh ng bài toán đơn gi n, đôi khi ch c n qua ví d là ta đã có th đưa v m t bài toán quen thu c đ gi i. Tìm c u trúc d li u bi u di n bài toán Khi gi i m t bài toán, ta c n ph i đ nh nghĩa t p h p d li u đ bi u di n tình tr ng c th . Vi c l a ch n này tuỳ thu c vào v n đ c n gi i quy t và nh ng thao tác s ti n hành trên d li u vào. Có nh ng thu t toán ch thích ng v i m t cách t ch c d li u nh t đ nh, đ i v i nh ng cách t ch c d li u khác thì s kém hi u qu ho c không th th c hi n đư c. Chính vì v y nên bư c xây d ng c u trúc d li u không th tách r i bư c tìm ki m thu t toán gi i quy t v n đ . 1 This content is available online at . 7
  12. 8 CHƯƠNG 3. BÀI 2: PHÂN TÍCH VÀ THI T K BÀI TOÁN Các tiêu chu n khi l a ch n c u trúc d li u • C u trúc d li u trư c h t ph i bi u di n đư c đ y đ các thông tin nh p và xu t c a bài toán • C u trúc d li u ph i phù h p v i các thao tác c a thu t toán mà ta l a ch n đ gi i quy t bài toán. • C u trúc d li u ph i cài đ t đư c trên máy tính v i ngôn ng l p trình đang s d ng Đ i v i m t s bài toán, trư c khi t ch c d li u ta ph i vi t m t đo n chương trình nh đ kh o sát xem d li u c n lưu tr l n t i m c đ nào. Xác đ nh thu t toán Thu t toán là m t h th ng ch t ch và rõ ràng các quy t c nh m xác đ nh m t dãy thao tác trên c u trúc d li u sao cho: V i m t b d li u vào, sau m t s h u h n bư c th c hi n các thao tác đã ch ra, ta đ t đư c m c tiêu đã đ nh. Các đ c trưng c a thu t toán • Tính đơn nghĩa m i bư c c a thu t toán, các thao tác ph i h t s c rõ ràng, không gây nên s nh p nh ng, l n x n, tuỳ ti n, đa nghĩa. Không nên l n l n tính đơn nghĩa và tính đơn đ nh: Ngư i ta phân lo i thu t toán ra làm hai lo i: Đơn đ nh (Deterministic) và Ng u nhiên (Randomized). V i hai b d li u gi ng nhau cho trư c làm input, thu t toán đơn đ nh s thi hành các mã l nh gi ng nhau và cho k t qu gi ng nhau, còn thu t toán ng u nhiên có th th c hi n theo nh ng mã l nh khác nhau và cho k t qu khác nhau. Ví d như yêu c u ch n m t s t nhiên x: a ≤ x ≤ b, n u ta vi t x = a hay x = b hay x = (a + b) div 2, thu t toán s luôn cho m t giá tr duy nh t v i d li u vào là hai s t nhiên a và b. Nhưng n u ta vi t x = a + Random(b - a + 1) thì s có th thu đư c các k t qu khác nhau trong m i l n th c hi n v i input là a và b tuỳ theo máy tính và b t o s ng u nhiên. • Tính d ng Thu t toán không đư c rơi vào quá trình vô h n, ph i d ng l i và cho k t qu sau m t s h u h n bư c. • Tính đúng Sau khi th c hi n t t c các bư c c a thu t toán theo đúng quá trình đã đ nh, ta ph i đư c k t qu mong mu n v i m i b d li u đ u vào. K t qu đó đư c ki m ch ng b ng yêu c u bài toán. • Tính ph d ng Thu t toán ph i d s a đ i đ thích ng đư c v i b t kỳ bài toán nào trong m t l p các bài toán và có th làm vi c trên các d li u khác nhau. Tính kh thi • Kích thư c ph i đ nh : Ví d : M t thu t toán s có tính hi u qu b ng 0 n u lư ng b nh mà nó yêu c u vư t quá kh năng lưu tr c a h th ng máy tính. • Thu t toán ph i chuy n đư c thành chương trình: Ví d m t thu t toán yêu c u ph i bi u di n đư c s vô t v i đ chính xác tuy t đ i là không hi n th c v i các h th ng máy tính hi n nay • Thu t toán ph i đư c máy tính th c hi n trong th i gian cho phép, đi u này khác v i l i gi i toán (Ch c n ch ng minh là k t thúc sau h u h n bư c). Ví d như x p th i khoá bi u cho m t h c kỳ thì không th cho máy tính ch y t i h c kỳ sau m i ra đư c. Ví d 2.3: Input: 2 s nguyên t nhiên a và b không đ ng th i b ng 0 Output: Ư c s chung l n nh t c a a và b Thu t toán s ti n hành đư c mô t như sau: (Thu t toán Euclide)
  13. 9 Bư c 1 (Input): Nh p a và b: S t nhiên Bư c 2: N u b = 0 thì chuy n sang bư c 3, n u không thì b qua bư c 3, đi làm bư c 4 Bư c 3: Đ t r = a mod b; Đ t a = b; Đ t b = r; Quay tr l i bư c 2. Bư c 4 (Output): K t lu n ư c s chung l n nh t ph i tìm là giá tr c a a. K t thúc thu t toán. Khi mô t thu t toán b ng ngôn ng t nhiên, ta không c n ph i quá chi ti t các bư c và ti n trình th c hi n mà ch c n mô t m t cách hình th c đ đ chuy n thành ngôn ng l p trình. Vi t sơ đ các thu t toán đ quy là m t ví d . Đ i v i nh ng thu t toán ph c t p và n ng v tính toán, các bư c và các công th c nên mô t m t cách tư ng minh và chú thích rõ ràng đ khi l p trình ta có th nhanh chóng tra c u. Đ i v i nh ng thu t toán kinh đi n thì ph i thu c. Khi gi i m t bài toán l n trong m t th i gian gi i h n, ta ch ph i thi t k t ng th còn nh ng ch đã thu c thì c vi c l p ráp vào. Tính đúng đ n c a nh ng mô-đun đã thu c ta không c n ph i quan tâm n a mà t p trung gi i quy t các ph n khác. L p trình Sau khi đã có thu t toán, ta ph i ti n hành l p trình th hi n thu t toán đó. Mu n l p trình đ t hi u qu cao, c n ph i có k thu t l p trình t t. K thu t l p trình t t th hi n k năng vi t chương trình, kh năng g r i và thao tác nhanh. L p trình t t không ph i ch c n n m v ng ngôn ng l p trình là đ , ph i bi t cách vi t chương trình uy n chuy n và phát tri n d n d n đ chuy n các ý tư ng ra thành chương trình hoàn ch nh. Kinh nghi m cho th y m t thu t toán hay nhưng do cài đ t v ng v nên khi ch y l i cho k t qu sai ho c t c đ ch m. Thông thư ng, ta không nên c th hoá ngay toàn b chương trình mà nên ti n hành theo phương pháp tinh ch t ng bư c (Stepwise refinement): • Ban đ u, chương trình đư c th hi n b ng ngôn ng t nhiên, th hi n thu t toán v i các bư c t ng th , m i bư c nêu lên m t công vi c ph i th c hi n. • M t công vi c đơn gi n ho c là m t đo n chương trình đã đư c h c thu c thì ta ti n hành vi t mã l nh ngay b ng ngôn ng l p trình. • M t công vi c ph c t p thì ta l i chia ra thành nh ng công vi c nh hơn đ l i ti p t c v i nh ng công vi c nh hơn đó. Trong quá trình tinh ch t ng bư c, ta ph i đưa ra nh ng bi u di n d li u. Như v y cùng v i s tinh ch các công vi c, d li u cũng đư c tinh ch d n, có c u trúc hơn, th hi n rõ hơn m i liên h gi a các d li u. Phương pháp tinh ch t ng bư c là m t th hi n c a tư duy gi i quy t v n đ t trên xu ng, giúp cho ngư i l p trình có đư c m t đ nh hư ng th hi n trong phong cách vi t chương trình. Tránh vi c mò m m, xoá đi vi t l i nhi u l n, bi n chương trình thành t gi y nháp. Ki m th Ch y th và tìm l i Chương trình là do con ngư i vi t ra, mà đã là con ngư i thì ai cũng có th nh m l n. M t chương trình vi t xong chưa ch c đã ch y đư c ngay trên máy tính đ cho ra k t qu mong mu n. K năng tìm l i, s a l i, đi u ch nh l i chương trình cũng là m t k năng quan tr ng c a ngư i l p trình. K năng này ch có đư c b ng kinh nghi m tìm và s a ch a l i c a chính mình. Có ba lo i l i: • L i cú pháp: L i này hay g p nh t nhưng l i d s a nh t, ch c n n m v ng ngôn ng l p trình là đ . M t ngư i đư c coi là không bi t l p trình n u không bi t s a l i cú pháp. • L i cài đ t: Vi c cài đ t th hi n không đúng thu t toán đã đ nh, đ i v i l i này thì ph i xem l i t ng th chương trình, k t h p v i các ch c năng g r i đ s a l i cho đúng. • L i thu t toán: L i này ít g p nh t nhưng nguy hi m nh t, n u nh thì ph i đi u ch nh l i thu t toán, n u n ng thì có khi ph i lo i b hoàn toàn thu t toán sai và làm l i t đ u. Xây d ng các b test
  14. 10 CHƯƠNG 3. BÀI 2: PHÂN TÍCH VÀ THI T K BÀI TOÁN Có nhi u chương trình r t khó ki m tra tính đúng đ n. Nh t là khi ta không bi t k t qu đúng là th nào?. Vì v y n u như chương trình v n ch y ra k t qu (không bi t đúng sai th nào) thì vi c tìm l i r t khó khăn. Khi đó ta nên làm các b test đ th chương trình c a mình. Các b test nên đ t trong các file văn b n, b i vi c t o m t file văn b n r t nhanh và m i l n ch y th ch c n thay tên file d li u vào là xong, không c n gõ l i b test t bàn phím. Kinh nghi m làm các b test là: B t đ u v i m t b test nh , đơn gi n, làm b ng tay cũng có đư c đáp s đ so sánh v i k t qu chương trình ch y ra. Ti p theo v n là các b test nh , nhưng ch a các giá tr đ c bi t ho c t m thư ng. Kinh nghi m cho th y đây là nh ng test d sai nh t. Các b test ph i đa d ng, tránh s l p đi l p l i các b test tương t . Có m t vài test l n ch đ ki m tra tính ch u đ ng c a chương trình mà thôi. K t qu có đúng hay không thì trong đa s trư ng h p, ta không th ki m ch ng đư c v i test này. Lưu ý r ng chương trình ch y qua đư c h t các test không có nghĩa là chương trình đó đã đúng. B i có th ta chưa xây d ng đư c b test làm cho chương trình ch y sai. Vì v y n u có th , ta nên tìm cách ch ng minh tính đúng đ n c a thu t toán và chương trình, đi u này thư ng r t khó. T i ưu chương trình M t chương trình đã ch y đúng không có nghĩa là vi c l p trình đã xong, ta ph i s a đ i l i m t vài chi ti t đ chương trình có th ch y nhanh hơn, hi u qu hơn. Thông thư ng, trư c khi ki m th thì ta nên đ t m c tiêu vi t chương trình sao cho đơn gi n, mi n sao ch y ra k t qu đúng là đư c, sau đó khi t i ưu chương trình, ta xem l i nh ng ch nào vi t chưa t t thì t i ưu l i mã l nh đ chương trình ng n hơn, ch y nhanh hơn. Không nên vi t t i đâu t i ưu mã đ n đó, b i chương trình có mã l nh t i ưu thư ng ph c t p và khó ki m soát. Vi c t i ưu chương trình nên d a trên các tiêu chu n sau: • Tính tin c y Chương trình ph i ch y đúng như d đ nh, mô t đúng m t gi i thu t đúng. Thông thư ng khi vi t chương trình, ta luôn có thói quen ki m tra tính đúng đ n c a các bư c m i khi có th . • Tính uy n chuy n Chương trình ph i d s a đ i. B i ít có chương trình nào vi t ra đã hoàn h o ngay đư c mà v n c n ph i s a đ i l i. Chương trình vi t d s a đ i s làm gi m b t công s c c a l p trình viên khi phát tri n chương trình. • Tính trong sáng Chương trình vi t ra ph i d đ c d hi u, đ sau m t th i gian dài, khi đ c l i còn hi u mình làm cái gì?. Đ n u có đi u ki n thì còn có th s a sai (n u phát hi n l i m i), c i ti n hay bi n đ i đ đư c chương trình gi i quy t bài toán khác. Tính trong sáng c a chương trình ph thu c r t nhi u vào công c l p trình và phong cách l p trình. • Tính h u hi u Chương trình ph i ch y nhanh và ít t n b nh , t c là ti t ki m đư c c v không gian và th i gian. Đ có m t chương trình h u hi u, c n ph i có gi i thu t t t và nh ng ti u x o khi l p trình. Tuy nhiên, vi c áp d ng quá nhi u ti u x o có th khi n chương trình tr nên r i r m, khó hi u khi s a đ i. Tiêu chu n h u hi u nên d ng l i m c ch p nh n đư c, không quan tr ng b ng ba tiêu chu n trên. B i ph n c ng phát tri n r t nhanh, yêu c u h u hi u không c n ph i đ t ra quá n ng. T nh ng phân tích trên, chúng ta nh n th y r ng vi c làm ra m t chương trình đòi h i r t nhi u công đo n và tiêu t n khá nhi u công s c. Ch m t công đo n không h p lý s làm tăng chi phí vi t chương trình. Nghĩ ra cách gi i quy t v n đ đã khó, bi n ý tư ng đó thành hi n th c cũng không d chút nào.
  15. 11 Nh ng c u trúc d li u và gi i thu t đ c p t i trong chuyên đ này là nh ng ki n th c r t ph thông, m t ngư i h c l p trình không s m thì mu n cũng ph i bi t t i. Ch hy v ng r ng khi h c xong chuyên đ này, qua nh ng c u trúc d li u và gi i thu t h t s c m u m c, chúng ta rút ra đư c bài h c kinh nghi m: Đ ng bao gi vi t chương trình khi mà chưa suy xét k v gi i thu t và nh ng d li u c n thao tác, b i như v y ta d m c ph i hai sai l m tr m tr ng: ho c là sai v gi i thu t, ho c là gi i thu t không th tri n khai n i trên m t c u trúc d li u không phù h p. Ch c n m c m t trong hai l i đó thôi thì nguy cơ s p đ toàn b chương trình là hoàn toàn có th , càng c ch a càng b r i, kh năng h u như ch c ch n là ph i làm l i t đ u 3.1.2 MODUL HÓA VÀ VI C GI I QUY T BÀI TOÁN Trong th c t các bài toán đư c gi i trên máy tính đi n t ngày càng nhi u và càng ph c t p. Các gi i thu t ngày càng có qui mô l n và khó thi t l p. Đ đơn gi n hoá bài toán ngư i ta ti n hành phân chia bài toán l n thành các bài toán nh . Có nghĩa là n u bài toán l n là m t modul chính thì c n chia nó ra thành các modul con, đ n lư t nó m i modul con này l i có th chia ti p ra thành các modul con khác ng v i các ph n vi c cơ b n mà ngư i ta đã bi t cách gi i quy t. Vi c t ch c l i gi i c a bài toán có th đư c th c hi n theo c u trúc phân c p như sau : Figure 3.1 Chi n lư c gi i quy t bài toán theo ki u như v y g i là chi n lư c “chia đ tr ” (devide and conquare). Đ th hi n chi n lư c này ngư i ta s d ng phương pháp thi t k t trên “ đ nh - xu ng ” (top - down design). Đó là cách phân tích t ng quát toàn b m i v n đ , xu t phát t d ki n và các m c tiêu đ ra, đ đ c p đ n nh ng công vi c ch y u r i sau đó m i đi d n vào gi i quy t các ph n c th m t cách chi ti t hơn(g i đó là cách thi t k t khái quát đ n chi ti t) . Ví d : Ch t ch h i đ ng xét c p h c b ng c a nhà trư ng yêu c u chúng ta: “ Dùng máy tính đi n t đ qu n lý và b o trì các h sơ v h c b ng c a các sinh viên di n đư c tài tr , đ ng th i thư ng kỳ ph i l p các báo cáo t ng k t đ đ trình lên B ” Như v y trư c h t ta ph i hình dung đư c c th hơn đ u vào và đ u ra c a bài toán. Có th coi như ta đã có 1 t p h sơ (file) bao g m các b n ghi (records) v các thông tin liên quan đ n h c b ng c a sinh viên như : Mã SV, Đi m TB, đi m đ o đ c, kho n ti n tài tr . Và chương trình l p ra
  16. 12 CHƯƠNG 3. BÀI 2: PHÂN TÍCH VÀ THI T K BÀI TOÁN ph i t o đi u ki n cho ngư i s d ng gi i quy t đư c các yêu c u sau: 1> Tìm l i và hi n th đư c b n ghi c a b t kỳ sinh viên nào t i thi t b cu i (terminal) c a ngư i dùng. 2> C p nh t (update) đư c b n ghi c a m t sinh viên cho trư c b ng cách thay đ i đi m trung bình, đi m đ o đ c, kho n ti n tài tr n u c n. 3> In b ng t ng k t ch a nh ng thông tin hi n th i (đã đư c c p nh t m i khi có thay đ i) g m s li u, đi m trung bình, đi m đ o đ c, kho n ti n tài tr , n u c n. Xu t phát t nh ng nh n đ nh trên, gi i thu t x lý ph i gi i quy t 3 nhi m v chính như sau: 1- Nh ng thông tin v sinh viên đư c h c b ng, lưu tr trên đĩa ph i đư c đ c vào b nh trong đ có th x lý (g i là nhi m v “đ c t p”) 2- X lý các th ng tin này đ t o ra k t qu mong mu n (nhi m v “x lý t p”) 3- Sao chép nh ng thông tin đã đư c c p nh t vào t p trên đĩa đ lưu tr cho vi c x lý sau này( g i là nhi m v “ghi t p”). Figure 3.2 Các nhi m v m c đ u này tương đ i ph c t p thư ng chia thành các nhi m v con. Ch ng h n, nhi m v “x lý t p” s đư c phân thành 3 nhi m v con tương ng gi i quy t 3 yêu c u chính đư c nêu trên: 1> Tìm l i b n ghi c a m t sinh viên cho trư c. 2> C p nh t thông tin trong b n ghi sinh viên. 3> In b ng t ng k t nh ng thông tin v các sinh viên đư c h c b ng. Nh ng nhi m v con này cũng có th l i đư c chia nh thành các nhi m v theo sơ đ sau:
  17. 13 Figure 3.3 Cách thi t k gi i thu t theo ki u top - down này s giúp cho vi c gi i quy t bài toán đư c đ nh hư ng rõ ràng, d dàng th c hi n và nó chính là n n t ng cho vi c l p trình c u trúc. 3.1.3 PHƯƠNG PHÁP TINH CH NH D N T NG BƯ C (Stepwise refine- ment) Tinh ch nh t ng bư c là phương pháp thi t k gi i thu t g n li n v i l p trình. Nó ph n ánh tinh th n c a quá trình modul hoá bài toán và thi t k ki u top - down. Phương pháp này đư c ti n hành theo sơ đ : CTDL → CTDL lưu tr → Cách cài đ t DL h p lý → CTDL ti n đ nh. Trong quá trình th c hi n gi i thu t ban đ u chương trình đư c th c hi n b ng ngôn ng t nhiên ph n ánh ý chính c a công vi c c n làm. Đ n các bư c sau nh ng ý đó s đư c chi ti t hoá d n d n tương ng v i nh ng công vi c nh hơn. Ta g i đó là các bư c tinh ch nh, s tinh ch nh này s đư c hư ng v phía ngôn ng l p trình mà ta đã ch n. Càng các bư c sau l i l đ c t các công vi c x lý s đư c thay th b i các câu l nh hư ng t i câu l nh c a ngôn ng l p trình. Ví d 2.4: Gi s ta mu n l p chương trình s p x p m t dãy n s nguyên khác nhau theo th t tăng d n. Gi i thu t có th đư c phác th o m t cách th công đơn gi n như sau:“ Coi các ph n t c a dãy s như các ph n t c a m t véc tơ (có c u trúc m ng m t chi u) và dãy này đư c lưu tr b i m t vec tơ lưu tr g m n t máy k ti p b nh trong (a1, a2, . . ., an) m i t ai lưu tr m t ph n t th i (1 ≤ i ≤ n) c a dãy s . Qui ư c dãy s đư c s p x p r i v n đ t i ch cũ như đã cho. T các s đã cho ch n ra m t s nh nh t, đ t nó vào cu i dãy đã đư c s p x p. Sau đó ti n hành so sánh v i s hi n đang v trí đó n u như nó khác v i s này thì ph i ti n hành đ i ch . Công vi c c l p l i cho đ n ch dãy s chưa đư c s p x p tr thành r ng”. Bư c tinh ch nh đ u tiên đư c th c hi n nh ngôn ng t a C như sau: For( int i = 1, i ≤ n, i++) { + Xét t a i đ n a n đ tìm s nh nh t a j + Đ i ch gi a ai và aj } Các bư c ti n hành: + B1: Xét dãy đã cho. Tìm s nguyên nh nh t aj trong các s t ai đ n an + B2: Đ i ch gi a aj và ai
  18. 14 CHƯƠNG 3. BÀI 2: PHÂN TÍCH VÀ THI T K BÀI TOÁN Nhi m v đ u có th đư c th c hi n b ng cách: “ Tho t tiên coi ai là “ s nh nh t” t m th i; l n lư t so sánh ai v i ai+1,ai+2, . . . Khi đã so sánh v i an r i thì s nh nh t s đư c xác đ nh.” Đ xác đ nh ta ph i ch ra v trí c a nó, hay nói cách khác là n m đư c ch s c a ph n t y thông qua m t khâu trung gian: {Bư c tinh ch nh 1} j =i; For( int k =j+1, k ≤ n, k++) if ( a k < a j ) j=k; {Bư c tinh ch nh 2} B = a i ; a i = a j ; a j = B; Sau khi đã ch nh l i cách vi t bi n ch s cho đúng v i qui ư c ta có chương trình s p x p hoàn ch nh vi t dư i d ng th t c như sau: Void Sort(A,n) {các bi n i,j,k ki u nguyên; bi n trung gian B cùng ki u A} 1- For( int i = 1, i ≤ n, i++) { 2- {Ch n s nh nh t} j =i; For( int k =j+1, k ≤ n, k++) if ( A[k] < A[j] ) j = k; 1- {Đ i ch } B = A[i]; A[i]= A[j]; A[j] = B; } Ví d 2: Cho ma tr n vuông n × n các s nguyên. Hãy in ra các ph n t thu c đư ng chéo song song v i đư ng chéo chính theo th t tính t ph i sang trái. Figure 3.4 Ch n cách in t ph i sang trái ta có k t qu : a14 a13 a24 a12 a23 a34 a11 a22 a33 a44 a21 a32 a43 a31 a42
  19. 15 a41 N a tam giác trên các c t gi m d n t n → 1, đưa ra các ph n t thu c đư ng chéo ng v i c t j N a tam giác dư i các hàng tăng t 2 → n. V i m i hàng như v y ta ph i đưa ra các ph n t thu c đư ng chéo tương đương v i hàng i đã cho. Ta có th phác ho gi i thu t như sau: 1- Nh p c p ma tr n n 2- Nh p các ph n t c a ma tr n A[i,j] 3- In các đư ng chéo song song v i đư ng chéo chính. Hai nhi m v (1) và (2) có th d dàng th hi n b ng Pascal: 1. Cin n; 1. for ( i = 1, i
  20. 16 CHƯƠNG 3. BÀI 2: PHÂN TÍCH VÀ THI T K BÀI TOÁN For (j = 1,j

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản