›
›

Giáo trình Cấu trúc dữ liệu và giải thuật

pdf 203 trang phuongnguyen 3431
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật

  1. Cấu trúc dữ liệu và giải thuật
  2. GIíI THIÖU M¤N HäC Trong ng«n ng÷ lË p tr× nh, d÷ liÖ u bao gåm hai kiÓ u chÝ nh lµ : - KiÓ u d÷ liÖ u ®¬n gi¶ n: char, int, long, float, enumeration, subrange. - KiÓ u d÷ liÖ u cã cÊ u tróc : struct, array, file (kiÓ u d÷ liÖ u cã kÝ ch th­íc kh«ng ®æi) Gi¸ o tr× nh nµ y tË p trung vµ o viÖ c nghiª n cøu c¸ c kiÓ u d÷ liÖ u cã cÊ u tróc cã kÝ ch th­íc kh«ng ®æi hoÆ c thay ®æi trong ng«n ng÷ lË p tr× nh, m« t¶ th«ng qua ng«n ng÷ C. Ngoµ i ra cßn giíi thiÖ u c¸ c gi¶ i thuË t chung quanh c¸ c cÊ u tróc d÷ liÖ u nµ y nh­ c¸ ch tæ chøc, thùc hiÖ n c¸ c phÐ p to¸ n t× m kiÕ m, s¾ p thø tù néi, s¾ p thø tù ngo¹ i §iÒ u kiÖ n ®Ó cã thÓ t× m hiÓ u râ rµ ng vÒ m«n häc nµ y lµ häc viª n ®∙ biÕ t c¸ c kh¸ i niÖ m vÒ kü thuË t lË p tr× nh trª n ng«n ng÷ C. Trong phÇ n më ®Ç u, bµ i gi¶ ng nµ y sÏ giíi thiÖ u c¸ ch thøc ph© n tÝ ch & thiÕ t kÕ mét gi¶ i thuË t tr­íc khi t× m hiÓ u vÒ c¸ c cÊ u tróc d÷ liÖ u cô thÓ . Vµ o cuèi khãa häc, sinh viª n cã thÓ : - Ph© n tÝ ch ®é phøc t¹ p cña c¸ c ch­¬ng tr× nh cã kÝ ch th­íc nhá vµ trung b× nh. - NhË n thøc ®­îc sù cÇ n thiÕ t cña viÖ c thiÕ t kÕ cÊ u tróc d÷ liÖ u. - Lµ m quen víi c¸ c kh¸ i niÖ m stacks, queues, danh s¸ ch ®Æ c, danh s¸ ch liª n kÕ t, c© y nhÞ ph© n, c© y nhÞ ph© n t× m kiÕ m, - HiÓ u ®­îc nguyª n lý cña viÖ c x© y dùng mét ch­¬ng tr× nh m¸ y tÝ nh. - Cã thÓ chän lùa viÖ c tæ chøc d÷ liÖ u phï hîp vµ c¸ c gi¶ i thuË t xö lý d÷ liÖ u cã hiÖ u qu¶ trong khi x© y dùng ch­¬ng tr× nh. Sinh viª n cÇ n l­u ý r» ng, tïy vµ o c«ng viÖ c cô thÓ mµ ta nª n chän cÊ u tróc d÷ liÖ u nµ o lµ thÝ ch hîp theo h­íng tèi ­u vÒ thêi gian thùc hiÖ n hay tèi ­u vÒ bé nhí. 1
  3. Ch­¬n g I PH¢N TÝ CH & THIÕT KÕ GI¶I THUËT I. më ®Çu HÇ u hÕ t c¸ c bµ i to¸ n ®Ò u cã nhiÒ u gi¶ i thuË t kh¸ c nhau ®Ó gi¶ i quyÕ t chóng. VË y lµ m thÕ nµ o chän ®­îc mét gi¶ i thuË t tèt nhÊ t ? ViÖ c chän lùa phô thuéc vµ o nhiÒ u yÕ u tè nh­ : §é phøc t¹ p tÝ nh to¸ n cña gi¶ i thuË t, chiÕ m dung l­îng bé nhí, tÇ n suÊ t sö dông, tÝ nh ®¬n gi¶ n, tèc ®é thùc hiÖ n Th«ng th­êng môc tiª u chän lùa lµ : 1. Gi¶ i thuË t râ rµ ng, dÔ hiÓ u, dÔ m∙ hãa vµ hiÖ u chØ nh. 2. Gi¶ i thuË t sö dông cã hiÖ u qu¶ tµ i nguyª n cña m¸ y tÝ nh vµ ®Æ c biÖ t ch¹ y cµ ng nhanh cµ ng tèt. Do ®ã khi viÕ t ch­¬ng tr× nh ®Ó ch¹ y mét lÇ n hoÆ c Ý t ch¹ y th× môc tiª u 1 lµ quan träng h¬n c¶ . Ng­îc l¹ i khi viÕ t ch­¬ng tr× nh ®Ó ch¹ y nhiÒ u lÇ n th× phÝ tæn ch¹ y ch­¬ng tr× nh cã thÓ v­ît qu¸ phÝ tæn lË p ch­¬ng tr× nh, nhÊ t lµ khi ph¶ i nhË p nhiÒ u sè liÖ u. Nãi chung, ng­êi lË p tr× nh ph¶ i biÕ t chän lùa, viÕ t, ®¸ nh gi¸ c¸ c gi¶ i thuË t ®Ó cã ®­îc gi¶ i thuË t tèi ­u cho bµ i to¸ n cña m× nh. II. ®¸nh gi¸ thêi gian ch¹y cña ch­¬n g t r × n h Thêi gian ch¹ y cña ch­ong tr× nh phô thuéc vµ o : 1. Input cho ch­¬ng tr× nh 2. ChÊ t l­îng m∙ sinh ra cña ch­¬ng tr× nh dÞ ch. 3. Tr¹ ng th¸ i vµ tèc ®é cña c¸ c lÖ nh ch¹ y trª n m¸ y. 4. §é phøc t¹ p thêi gian cña gi¶ i thuË t. §iÒ u 1 lµ chøc n¨ ng nhË p. KÝ ch th­íc cña input (vÝ dô lµ n) vµ ta th­êng ký hiÖ u T(n) lµ ®¹ i l­îng thêi gian cÇ n thiÕ t ®Ó gi¶ i bµ i to¸ n kÝ ch th­íc n. §iÒ u 2, 3 th­êng ®¸ nh gi¸ khã kh¨ n v× phô thuéc vµ o phÇ n mÒ m ch­¬ng tr× nh dÞ ch vµ phÇ n cøng cña m¸ y. §iÒu 4 lµ ®iÒu mµ ng­êi lË p tr× nh cÇ n kh¶ o s¸ t ®Ó lµ m t¨ ng tèc ®é cña ch­¬ng tr× nh. 2
  4. III. ký hiÖu o(n) vµ Ω(n) : Ta ®¸ nh gi¸ tû lÖ ph¸ t triÓ n c¸ c hµ m T(n) qua ký hiÖ u O(n). Ta nãi thêi gian ch¹ y T(n) cña ch­¬ng tr× nh lµ O(n2) cã nghÜ a lµ : ∃ ∀ ≥ ≤ 2 c > 0 vµ n0 sao cho n n0 ta cã T(n) c.n . VÝ dô : Gi¶ sö T(0) = 1, T(1) = 4, v v 2 2 Tæng qu¸ t T(n) = (n +1) th× ta nãi T(n) lµ O(n ) v× cã thÓ ®Æ t c1 = 4, n0 = 1, th× khi n ≥ 1 ta cã (n +1)2 ≤ 4n2. 2 ∀ Nh­ng kh«ng thÓ lÊ y n0 = 0 v× T(0) = 1 kh«ng nhá h¬n c.0 = 0, c; gi¶ thiÕ t r» ng n ≥ 0 vµ T(n) ≥ 0. ∃ ≤ ∀ ≥ Ta nãi T(n) lµ O(f(n)) nÕ u const c vµ n0 sao cho T(n) c.f(n), n n0. Ch­¬ng tr× nh ch¹ y víi thêi gian O(f(n)) ta nãi nã ph¸ t triÓ n tû lÖ víi f(n). Khi nãi T(n) lµ O(f(n)) th× f(n) lµ chÆ n trª n cña T(n). §Ó nã i chÆ n d­íi cña T(n) ta dïng ký hiÖ u Ω. Ω ∃ ≥ ∀ ≥ Ta nãi T(n) lµ (g(n)) nÕ u const c, n0 sao cho T(n) c.g(n), n n0. VÝ dô : §Ó kiÓ m tra T(n) = n3 + 2n2 lµ Ω(n3) ta ®Æ t c = 1 th× T(n) ≥ c.n3, ∀n = 0, 1, (no= 0). * Sù tr¸ i ng­îc cña tû lÖ ph¸ t triÓ n : Ta gi¶ sö c¸ c ch­¬ng tr× nh cã thÓ ®¸ nh gi¸ b» ng c¸ ch so s¸ nh c¸ c hµ m thêi gian cña chóng víi c¸ c h» ng tû lÖ kh«ng ®¸ ng kÓ . Khi ®ã ta nãi ch­¬ng tr× nh cã thêi gian ch¹ y O(n2). NÕ u ch­¬ng tr× nh 1 ch¹ y mÊ t 100.n2 thêi gian (mili gi© y) th× ch­¬ng tr× nh 2 ch¹ y mÊ t 5.n3 thêi gian, th× ta cã tû sè thêi gian cña 2 ch­¬ng tr× nh lµ 5.n3/100.n2 = n/20, nghÜ a lµ khi n = 20 th× thêi gian ch¹ y 2 ch­¬ng tr× nh lµ b» ng nhau, khi n 20 th× nª n dïng ch­¬ng tr× nh 1. VÝ dô : Cã 4 ch­¬ng tr× nh cã 4 ®é phøc t¹ p kh¸ c nhau ®­îc biÓ u diÔ n trong b¶ ng d­íi ®©y. Thêi gian KÝ ch th­íc bµ i to¸ n KÝ ch th­íc bµ i to¸ n Tû lÖ t¨ ng vÒ ch¹ y T(n) tèi ®a cho 103s tèi ®a cho 104s kÝ ch th­íc 100.n 10 100 10.0 lÇ n 5.n2 14 45 3.2 lÇn n3/2 12 27 2.3 lÇn 2n 10 13 1.3 lÇ n Gi¶ sö trong 103s th× 4 ch­¬ng tr× nh gi¶ i c¸ c bµ i to¸ n cã kÝ ch th­íc tèi ®a trong cét 2. NÕ u cã m¸ y tèt tèc ®é t¨ ng lª n 10 lÇ n th× kÝ ch th­íc tèi ®a t­¬ng øng 3
  5. cña 4 ch­¬ng tr× nh tr× nh bµ y ë cét 3. TØ lÖ hai cét 1,2 ghi ë cét 4. Nh­ vË y nÕ u ®Çu t­ vÒ tèc ®é 10 lÇ n th× chØ thu lîi cã 30% vÒ kÝ ch th­íc bµ i to¸ n nÕ u dïng ch­¬ng tr× nh cã ®é phøc t¹ p O(2n). IV. c¸ch tÝ nh thêi gian ch¹y ch­¬n g t r × n h : 1. Qui t¾c tæng: Gi¶ sö T1(n) vµ T2(n) lµ thêi gian ch¹ y ch­¬ng tr× nh P1 vµ P2 t­¬ng øng ®­îc ®¸ nh gi¸ lµ O(f(n)) vµ O(g(n)). Khi ®ã T1(n) + T2(n) sÏ lµ O(max(f(n),g(n))) (ch¹ y xong ch­¬ng tr× nh P1 th× ch¹ y P2). Chøng minh: ∃ Theo ®Þ nh nghÜ a O(f(n)) vµ O(g(n)) th× c1, n1, c2, n2 sao cho ≤ ∀ ≥ ≤ ∀ ≥ T1(n) c1.f(n) n n1 ; T2(n) c2.g(n) n n2. §Æ t n 0 = max(n1, n2) ≥ ≤ NÕ u n no th× T1(n) + T2(n) (c1 + c2).max(f(n),g(n)). 2. Qui t¾c tÝ ch: T1(n). T2(n) lµ O(f(n).g(n)). Chøng minh : t­¬ng tù nh­ tæng. VÝ dô : Cã 3 ch­¬ng tr× nh cã thêi gian ch¹ y t­¬ng øng lµ O(n2), O(n3), O(n.logn). ThÕ th× thêi gian ch¹ y 3 ch­¬ng tr× nh ®ång thêi lµ O(max(n2, n3, nlogn)) sÏ lµ O(n3). Nãi chung thêi gian ch¹ y mét d∙ y cè ®Þ nh c¸ c b­íc lµ thêi gian ch¹ y lín nhÊ t cña mét b­íc nµo ®ã trong d∙ y. Còng cã tr­êng hîp cã 2 hay nhiÒ u b­íc cã thêi gian ch¹ y kh«ng t­¬ng xøng (kh«ng lín h¬n mµ còng kh«ng nhá h¬n). Khi ®ã qui t¾ c tÝ nh tæng ph¶ i ®­îc tÝ nh trong tõng tr­êng hîp. n4 nÕ u n ch½ n VÝ dô : f(n) = { n2 nÕ u n lÎ g(n) = n2 nÕ u n ch½ n { n3 nÕ u n lÏ Thêi gian ch¹ y lµ O(max(f(n),g(n))) lµ n4 nÕ u n ch½ n vµ n3 nÕ u n lÎ . ≤ ∀ ≥ NÕ u g(n) f(n), n no, no lµ const nµ o ®ã th× O(f(n)+g(n)) sÏ lµ O(f(n)). VÝ dô : O(n2 + n) = O(n2) Tr­íc khi ®­a ra qui t¾ c chung ®Ó ph© n tÝ ch thêi gian ch¹ y cña ch­¬ng tr× nh th× ta xÐ t vÝ dô ®¬n gi¶ n sau. 4
  6. VÝ dô : XÐ t ch­¬ng tr× nh Bubble dïng s¾ p d∙ y sè nguyª n theo chiÒ u t¨ ng. Procedure Bubble (var A: array [1 n] of integer); Var i, j, temp : integer ; Begin 1 For i := 2 to n do 2 For j := n downto i do 3 If A[j-1] > A[j] then Begin 4 temp := A[j-1] ; 5 A[j-1] := A[j] ; 6 A[j] := temp ; End ; End ; Ph© n tÝ ch : - N lµ sè phÇ n tö - kÝ ch th­íc cña bµ i to¸ n. Mçi lÖ nh g¸ n tõ dßng 4 - > dßng 6 mÊ t 3 ®¬n vÞ thêi gian, theo qui t¾ c tÝ nh tæng sÏ lµ O(max(1,1,1) = O(1). - Vßng If vµ For lång nhau, ta ph¶ i xÐ t tõ trong ra ngoµ i. §èi víi ®iÒ u kiÖ n sau If ph¶ i kiÓ m tra O(1) thêi gian. Ta kh«ng ch¾ c th© n lÖ nh If tõ 4 - 6 cã thùc hiÖ n hay kh«ng. V× xÐ t trong tr­êng hîp xÊ u nhÊ t nª n ta gi¶ thuyÕ t lµ c¸ c lÖ nh tõ 4 - 6 ®Ò u cã thùc hiÖ n. VË y nhãm If tõ c¸ c lÖ nh 3 -6 lµ m mÊ t O(1) thêi gian. - Ta xÐ t vßng lÆ p ngoµ i tõ 2 - 6. Nguyª n t¾ c chung cña vßng lÆ p: thêi gian vßng lÆ p lµ tæng thêi gian mçi lÇ n lÆ p trong th© n vßng lË p. Ý t nhÊ t lµ O(1) cho mçi lÇ n lÆ p khi chØ sè t¨ ng. Sè lÇ n lÆ p tõ 2 - 6 lµ n - i +1 VË y theo qui t¾ c tÝ ch : O((n - i +1), 1) lµ O(n -i +1). - Ta xÐ t vßng ngoµ i cïng chøa c¸ c lÖ nh cña ch­¬ng tr× nh. LÖ nh 1 lµ m n-1 lÇ n, tèn n-1 ®¬n vÞ thêi gian. VË y tæng thêi gian ch¹ y cña ch­¬ng tr× nh bÞ chÆ n d­íi bëi 1 thêi gian cè ®Þ nh lµ : n ∑ (n − i + 1) = n * (n − 1) / 2 tøc lµ O(n2) i=2 Tuy nhiª n kh«ng cã qui t¾ c ®Ç y ®ñ ®Ó ph© n tÝ ch ch­¬ng tr× nh. Nãi chung thêi gian ch¹ y cña 1 lÖ nh hoÆ c 1 nhãm lÖ nh cã thÓ lµ 1 hµ m cña kÝ ch th­íc c¸ c input hoÆ c 1 hay nhiÒ u biÕ n. Nh­ng chØ cã n - kÝ ch th­íc cña bµ i to¸ n lµ th«ng sè cho phÐ p ®èi víi thêi gian ch¹ y cña ch­¬ng tr× nh. 5
  7. 3. Qui t¾c tÝ nh thêi gian ch¹y a) Thêi gian ch¹ y cña mçi lÖ nh g¸ n, read, write cã gi¶ thiÕ t lµ O(1). b) Thêi gian ch¹ y cña 1 d∙ y lÖ nh x¸ c ®Þ nh theo qui t¾ c tæng; nghÜ a lµ thêi gian ch¹ y cña d∙ y lµ thêi gian lín nhÊ t cña 1 lÖ nh nµ o ®ã trong d∙ y lÖ nh. c) Thêi gian ch¹ y lÖ nh If lµ thêi gian thùc hiÖ n lÖ nh ®iÒ u kiÖ n céng víi thêi gian kiÓ m tra ®iÒ u kiÖ n. Thêi gian thùc hiÖ n lÖ nh If cã cÊ u tróc If then eles lµ thêi gian kiÓ m tra ®iÒ u kiÖ n céng víi thêi gian lín nhÊ t cña 1 trong 2 lÖ nh rÏ nh¸ nh true vµ false. d) Thêi gian thùc hiÖ n vßng lÆ p lµ tæng thêi gian thùc hiÖ n th© n vßng lÆ p vµ thêi gian kiÓ m tra kÕ t thóc vßng lÆ p. e) Gäi thñ tôc:NÕ u ch­¬ng tr× nh cã c¸ c thñ tôc vµ kh«ng cã thñ tôc nµ o lµ ®Ö qui th× ta cã thÓ tÝ nh thêi gian ch¹ y cïng mét lóc, b¾ t ®Ç u tõ c¸ c thñ tôc kh«ng gäi ®Õ n c¸ c thñ tôc kh¸ c. TÊ t nhiª n ph¶ i cã Ý t nhÊ t 1 thñ tôc nh­ vË y trong tr­êng hîp nµ y, nÕ u kh«ng th× ph¶ i cã thñ tôc ®Ö qui. Sau ®ã ta cã thÓ ®¸ nh gi¸ thêi gian ch¹ y cña c¸ c thñ tôc cã gäi, ®Õ n c¸ c thñ tôc kh«ng chøa lêi gäi ®∙ ® ­îc ®¸ nh gi¸ . Cø nh­ thÕ ta l¹ i ®¸ nh gi¸ thêi gian ch¹ y cña c¸ c thñ tôc cã lêi gäi ®Õ n c¸ c thñ tôc ®∙ ®¸ nh gi¸ , nghÜ a lµ mçi thñ tôc ®­îc ®¸ nh gi¸ sau khi ®¸ nh gi¸ hÕ t c¸ c thñ tôc mµ ®­îc nã gäi. NÕ u cã thñ tôc ®Ö qui th× kh«ng thÓ t× m ®­îc thø tù cña tÊ t c¶ c¸ c thñ tôc sao cho mçi thñ tôc chØ gäi ®Õ n c¸ c thñ tôc ®∙ ®¸ nh gi¸ . Khi ®ã ta ph¶ i lË p 1 liª n hÖ gi÷a mçi thñ tôc ®Ö qui víi 1 hµ m thêi gian ch­a biÕ t T(n) trong ®ã n lµ kÝ ch th­íc cña ®èi sè cña thñ tôc. Lóc ®ã ta cã thÓ nhË n ®­îc sù truy håi ®èi víi T(n), nghÜ a lµ 1 ph­¬ng tr× nh diÔ n t¶ T(n) qua c¸ c T(k) víi c¸ c gi¸ trÞ k kh¸ c nhau. VÝ dô : XÐ t ch­¬ng tr× nh ®Ö qui tÝ nh n giai thõa (n!), trong ®ã n lµ kÝ ch th­íc cña hµ m nª u trª n. Function Fact (n:integer) : LongInt ; Begin 1 If n <= 1 then 2 Fact := 1 Else 3 Fact := n*fact (n-1) End ; Ph© n tÝ ch: Ta ký hiÖ u T(n) lµ thêi gian ch¹ y ®Ó tÝ nh hµ m Fact(n). Thêi gian ch¹ y ®èi víi c¸ c dßng 1, 2 lµ O(1) vµ ®èi víi dßng 3 lµ O(1) + T(n-1). VË y víi c¸ c h» ng c, d nµ o ®ã ta cã ph­¬ng tr× nh: 6
  8. c + T(n-1) nÕ u n > 1 T(n) = { d nÕ u n ≤ 1 Gi¶ i ph­¬ng tr× nh : Gi¶ sö n > 2, ta cã thÓ khai triÓ n T(n-1) trong c«ng thøc : T(n) = 2.c + T(n-2) nÕ u n > 2 Sau ®ã ta l¹ i thay T(n-2) = c + T(n-3) ta ®­îc. T(n) = 3.c + T(n-3) nÕ u n > 3 T(n) = i.c + T(n-i) nÕ u n > i Cuèi cïng ta thay i = n - 1, ta ®­îc T(n) = c(n-1) + T(1) = c(n-1) + d KÕ t luË n T(n) lµ O(n). V. sù ph©n líp c¸c thuËt to¸n : Nh­ ® ∙ ® ­îc chó ý ë trª n, hÇ u hÕ t c¸ c thuË t to¸ n ®Ò u cã mét tham sè chÝ nh lµ N, Th«ng th­êng ®ã lµ sè l­îng c¸ c phÇ n tö d÷ liÖ u ®­îc xö lý mµ ¶ nh h­ëng rÊ t nhiÒ u tíi thêi gian ch¹ y. Tham sè N cã thÓ lµ bË c cña 1 ®a thøc, kÝ ch th­íc cña 1 tË p tin ®­îc s¾ p xÕ p hay t× m kiÕ m, sè nót trong 1 ®å thÞ HÇ u hÕ t tÊ t c¶ thuË t to¸ n trong bµ i gi¶ ng nµ y cã thêi gian ch¹ y tiÖ m cË n tíi 1 trong c¸ c hµ m sau : 1. HÇ u hÕ t tÊ t c¶ c¸ c chØ thÞ cña c¸ c ch­¬ng tr× nh ®Ò u ®­îc thùc hiÖ n mét lÇ n hay nhiÒ u nhÊ t chØ mét vµ i lÇ n. NÕ u tÊ t c¶ c¸ c chØ thÞ cña cïng 1 ch­¬ng tr× nh cã tÝ nh chÊ t nµ y th× chóng ta sÏ nãi r» ng thêi gian ch¹ y cña nã lµ h» ng sè. §iÒ u nµ y hiÓ n nhiª n lµ môc tiª u phÊ n ®Ê u ®Ó ®¹ t ®­îc trong viÖ c thiÕ t kÕ thuË t to¸ n. 2. logN Khi thêi gian ch¹ y cña ch­¬ng tr× nh lµ logarit, tøc lµ thêi gian ch¹ y ch­¬ng tr× nh tiÕ n chË m khi N lín dÇ n. Thêi gian ch¹ y lo¹ i nµ y xuÊ t hiÖ n trong c¸ c ch­¬ng tr× nh mµ gi¶ i 1 bµ i to¸ n lín b» ng c¸ ch chuyÓ n nã thµ nh bµ i to¸ n nhá h¬n, b» ng c¸ ch c¾ t bá kÝ ch th­íc bít 1 h» ng sè nµ o ®ã. Víi môc ®Ý ch cña chóng ta, thêi gian ch¹ y cã ®­îc xem nh­ nhá h¬n 1 h» ng sè "lín". C¬ sè cña logarit lµ m thay ®æi h» ng sè ®ã nh­ng kh«ng nhiÒ u: Khi n lµ 1000 th× logN lµ 3 nÕ u c¬ sè lµ 10; lµ 10 nÕ u c¬ sè lµ 2 ; khi N lµ 1000000, logN ®­îc nh©n gÊp ®«i. BÊt cø khi nµ o N ®­îc nh© n gÊ p ®«i, logN ®­îc t¨ ng lª n thª m mét h» ng sè, nh­ng logN kh«ng ®­îc nh© n gÊ p ®«i tíi khi N t¨ ng tíi N2. 3. N Khi thêi gian ch¹ y cña ch­¬ng tr× nh lµ tuyÕ n tÝ nh, nãi chung ®© y lµ tr­êng hîp mµ mét sè l­îng nhá c¸ c xö lý ®­îc lµ m cho mçi phÇ n tö d÷ liÖ u nhË p. 7
  9. Khi N lµ 1.000.000 th× thêi gian ch¹ y còng cì nh­ vË y. Khi N ®­îc nh© n gÊ p ®«i th× thêi gian ch¹ y còng ®­îc nh© n gÊ p ®«i. §©y lµ t× nh huèng tèi ­u cho 1 thuË t to¸ n mµ ph¶ i xö lý N d÷ liÖ u nhË p (hay s¶ n sinh ra N d÷ liÖ u xuÊ t). 4. NlogN §©y lµ thêi gian ch¹ y t¨ ng dÇ n lª n cho c¸ c thuË t to¸ n mµ gi¶ i 1 bµ i to¸ n b» ng c¸ ch t¸ ch nã thµ nh c¸ c bµ i to¸ n con nhá h¬n, kÕ ®Õ n gi¶ i quyÕ t chóng 1 c¸ ch ®éc lË p vµ sau ®ã tæ hîp c¸ c lêi gi¶ i. Bëi v× thiÕ u 1 tÝ nh tõ tèt h¬n (cã lÏ lµ "tuyÕ n tÝ nh logarit" ?), chóng ta nãi r» ng thêi gian ch¹ y cña thuË t to¸ n nh­ thÕ lµ "NlogN". Khi N lµ 1000000, NlogN cã lÏ kho¶ ng 6 triÖ u. Khi N ®­îc nh© n gÊ p ®«i, thêi gian ch¹ y bÞ nh© n lª n nhiÒ u h¬n gÊ p ®«i (nh­ng kh«ng nhiÒ u l¾ m). 5. N2 Khi thêi gian ch¹ y cña 1 thuË t to¸ n lµ bËc hai, tr­êng hîp nµ y chØ cã ý nghÜ a thùc tÕ cho c¸ c bµ i to¸ n t­¬ng ®èi nhá. Thêi gian b× nh ph­¬ng th­êng t¨ ng lª n trong c¸ c thuË t to¸ n mµ xö lý tÊ t c¶ c¸ c cÆ p phÇ n tö d÷ liÖ u (cã thÓ lµ 2 vßng lÆ p lång nhau). Khi N lµ 1000 th× thêi gian ch¹ y lµ 1000000. Khi N ®­îc nh© n ®«i th× thêi gian ch¹ y t¨ ng lª n gÊ p 4 lÇ n. 6. N3 T­¬ng tù, mét thuË t to¸ n mµ xö lý mét bé 3 cña c¸ c phÇ n tö d÷ liÖ u (cã lÏ 3 vßng lÆ p lång nhau) cã thêi gian ch¹ y bË c 3 vµ còng chØ cã ý nghÜ a thùc tÕ trong c¸ c bµ i to¸ n nhá. Khi N lµ 100 th× thêi gian ch¹ y lµ 1.000.000. Khi N ®­îc nh© n ®«i th× thêi gian ch¹ y t¨ ng lª n gÊ p 8 lÇ n. 7. 2n Mét sè Ý t thuË t to¸ n cã thêi gian ch¹ y lòy thõa l¹ i thÝ ch hîp trong 1 sè tr­êng hîp thùc tÕ , mÆ c dï c¸ c thuË t to¸ n nh­ thÕ lµ "sù Ð p buéc th« b¹ o" ®Ó gi¶ i bµ i to¸ n. Khi N lµ 20 th× thêi gian ch¹ y xÊ p xØ lµ 1.000.000 Khi N lµ gÊ p 2 th× thêi gian ch¹ y ®­îc n© ng lª n lòy thõa 2. Thêi gian ch¹ y cña 1 ch­¬ng tr× nh cô thÓ ®«i khi lµ mét h» ng sè nh© n víi c¸ c sè h¹ ng nãi trª n céng thª m mét sè h¹ ng nhá h¬n. C¸ c gi¸ trÞ cña h» ng sè vµ c¸ c sè h¹ ng phô thuéc vµ o c¸ c kÕ t qu¶ cña sù ph© n tÝ ch vµ c¸ c chi tiÕ t cµ i ®Æ t. HÖ sè cña h» ng sè liª n quan tíi sè chØ thÞ bª n trong vßng lÆ p : ë 1 tÇ ng tïy ý cña 8
  10. thiÕ t kÕ thuË t to¸ n th× ph¶ i cÈ n thË n giíi h¹ n sè chØ thÞ nh­ thÕ . Víi N lín th× c¸ c h» ng sè ®ãng vai trß chñ chèt, víi N nhá th× c¸ c sè h¹ ng cïng ®ãng gãp vµ o vµ sù so s¸ nh thuË t to¸ n sÏ khã kh¨ n h¬n. Ngoµ i nh÷ng hµ m võa nãi trª n còng cßn cã 1 sè hµ m kh¸ c, vÝ dô nh­ 1 thuË t to¸ n víi N2 phÇ n tö d÷ liÖ u nhË p mµ cã thêi gian ch¹ y lµ bË c 3 theo N th× sÏ ®­îc ph© n líp nh­ 1 thuË t to¸ n N3/2. Mét sè thuË t to¸ n cã 2 giai ®o¹ n ph© n t¸ ch thµ nh c¸ c bµ i to¸ n con vµ cã thêi gian ch¹ y xÊ p xØ víi Nlog2N. VI. c¸c c«ng thøc truy håi c¬ së : PhÇ n lín c¸ c thuË t to¸ n ®Ò u dùa trª n viÖ c ph© n r∙ ®Ö qui mét bµ i to¸ n lín thµ nh c¸ c bµ i to¸ n nhá h¬n, råi dïng c¸ c lêi gi¶ i cña c¸ c bµ i to¸ n nhá ®Ó gi¶ i bµ i to¸ n ban ®Ç u. Thêi gian ch¹ y cña c¸ c thuË t to¸ n nh­ thÕ ®­îc x¸ c ®Þ nh bëi kÝ ch th­í c vµ sè l­îng c¸ c bµ i to¸ n con vµ gi¸ ph¶ i tr¶ cña sù ph© n r∙ . Trong phÇ n nµ y ta quan s¸ t c¸ c ph­¬ng ph¸ p c¬ së ®Ó ph© n tÝ ch c¸ c thuË t to¸ n nh­ thÕ vµ tr× nh bµ y mét vµ i c«ng thøc chuÈ n th­êng ®­îc ¸ p dông trong viÖ c ph© n tÝ ch nhiÒ u thuË t to¸ n. TÝ nh chÊ t rÊ t tù nhiª n cña 1 ch­¬ng tr× nh ®Ö qui lµ thêi gian ch¹ y cho d÷ liÖ u nhË p cã kÝ ch th­íc N sÏ phô thuéc vµ o thêi gian ch¹ y cho c¸ c d÷ liÖ u nhË p cã kÝ ch th­íc nhá h¬n : ®iÒ u nµ y ®­îc diÔ n dÞ ch thµ nh 1 c«ng thøc to¸ n häc gäi lµ quan hÖ truy håi. C¸ c c«ng thøc nh­ thÕ m« t¶ chÝ nh x¸ c tÝ nh n¨ ng cña c¸ c thuË t to¸ n t­¬ng øng, do ®ã ®Ó cã ®­îc thêi gian ch¹ y chóng ta ph¶ i gi¶ i c¸ c bµ i to¸ n truy håi. B© y giê chóng ta chó ý vµ o c¸ c c«ng thøc chø kh«ng ph¶ i c¸ c thuË t to¸ n. C«ng thøc 1 : C«ng thøc nµ y th­êng dïng cho c¸ c ch­¬ng tr× nh ®Ö qui mµ cã vßng lÆ p duyÖ t qua d÷ liÖ u nhË p ®Ó bá bít 1 phÇ n tö. Cn = Cn-1 + n, víi n >= 2 vµ C1 = 1 Chøng minh : 2 Cn kho¶ ng n /2. §Ó gi¶ i 1 c«ng thøc truy håi nh­ trª n, chóng ta lÇ n l­ît ¸p dông chÝ nh c«ng thøc ®ã nh­ sau : Cn = Cn-1 + n = Cn-2 + (n-1) + n = = C1 + 2 + + (n-2) + (n-1) + n = 1 + 2 + + n = n(n+1)/2 9
  11. C«ng thøc 2 : C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ chia d÷ liÖ u nhË p thµ nh 2 phÇ n trong mçi b­íc. Cn = Cn/2 + 1, víi n >= 2 vµ C1 = 0 Chøng minh : Cn kho¶ ng logn. Ph­¬ng tr× nh nµ y v« nghÜ a trõ phi n ch½ n hay chóng ta gi¶ sö r» ng n/2 lµ phÐ p chia nguyª n : b© y giê chóng ta gi¶ sö r» ng n = 2m ®Ó cho c«ng thøc lu«n lu«n cã nghÜ a. Chóng ta viÕ t nh­ sau : m = m−1 + C2 C2 1 = m−2 + C2 2 = m−3 + C2 3 = = m−m + C2 m = m = log n C«ng thøc chÝ nh x¸ c cho n tæng qu¸ t th× phô thuéc vµ o biÓ u diÔ n nhÞ ph© n cña n, nãi chung Cn kho¶ ng logn víi mäi n. C«ng thøc 3 : C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ chia ®«i d÷ liÖ u nhË p nh­ng cã thÓ kiÓ m tra mçi phÇ n tö cña d÷ liÖ u nhË p. Cn = Cn/2 + n, víi n >= 2 vµ C1 = 0 Chøng minh : Cn kho¶ ng 2n. T­¬ng tù trª n, c«ng thøc nµ y chÝ nh lµ tæng n + n/2 + n/4 + (dÜ nhiª n ®iÒ u nµ y chØ chÝ nh x¸ c khi n lµ lòy thõa cña 2). NÕ u d∙y lµ v« h¹ n, th× ®© y lµ 1 chuçi h× nh häc ®¬n gi¶ n mµ ®­îc ­íc l­îng chÝ nh x¸ c lµ 2n. Trong tr­êng hîp tæng qu¸ t lêi gi¶ i chÝ nh x¸ c phô thuéc vµ o biÓ u diÔ n nhÞ ph© n cña n. C«ng thøc 4 : C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ duyÖ t tuyÕ n tÝ nh xuyª n qua d÷ liÖ u nhË p, tr­íc, trong, hay sau khi d÷ liÖ u nhË p ®­îc chia ®«i. Cn = 2Cn/2 + n, víi n >= 2 vµ C1 = 0 Chøng minh : Cn kho¶ ng nlogn. C«ng thøc nµ y ¸ p dông cho nhiÒ u thuË t to¸ n theo ph­¬ng ph¸ p "chia ®Ó trÞ ". 10
  12. m = m−1 + m C2 C2 2 m m−1 C2 = C2 + − 1 2m 2m 1 m−2 = C2 + + − 1 1 2m 2 m−m = C2 + − m 2m m = 0 + = C2 m m = m = ⇒ Cn m2 nlogn Lêi gi¶ i cho c«ng thøc nµ y rÊ t gièng nh­ trong c«ng thøc 2, nh­ng ph¶ i chia 2 vÕ cña c«ng thøc cho 2n trong b­íc thø hai. C«ng thøc 5 : C«ng thøc nµ y dïng cho ch­¬ng tr× nh ®Ö qui mµ t¸ ch d÷ liÖ u thµ nh 2 phÇ n. Cn = 2Cn/2 + 1, víi n >= 2 vµ C1 = 0 Chøng minh : Cn kho¶ ng 2n. Chøng minh gièng nh­ c«ng thøc 4. C¸ c biÕ n d¹ ng cña nh÷ng c«ng thøc nµ y ch¼ ng h¹ n nh­ ®iÒ u kiÖ n kh¸ c nhau hay c¸ c sè h¹ ng thª m vµ o kh¸ c nhau mét Ý t, cã thÓ ­íc l­îng b» ng c¸ ch dïng còng mét kü thuË t nh­ trª n. MÆ c dï vË y, chóng ta còng nª n chó ý 1 quan hÖ truy håi d­êng nh­ t­¬ng tù víi mét quan hÖ ®∙ biÕ t th× ®«i khi l¹ i khã gi¶ i h¬n rÊ t nhiÒ u. VII. gi¶i ph­¬ng tr× nh truy håi : §Ó gi¶ i ph­¬ng tr× nh truy håi cã nhiÒ u c¸ ch gi¶ i kh¸ c nhau, ë ®© y chóng t«i tr× nh bµ y c¸ ch gi¶ i ph­¬ng tr× nh truy håi b» ng c¸ ch truy vÒ ph­¬ng tr× nh ®Æ c tr­ng. Chóng t«i dïng c¸ ch gi¶ i nµ y ®Ó viÕ t ch­¬ng tr× nh gi¶ i tù ®éng ph­¬ng tr× nh truy håi. a) Ta xÐ t ph­¬ng tr× nh truy håi thuÇ n nhÊ t tuyÕ n tÝ nh víi c¸ c hÖ sè kh«ng ®æi sau ®©y : a0tn + a1tn-1 + + aktn-k = 0 (VII.1) trong ®ã ti(i=n, n-1, , n-k) lµ c¸ c È n sè cÇ n t× m. TuyÕ n tÝ nh v× c¸ c ti chØ cã bË c nhÊ t, thuÇ n nhÊ t v× vÕ ph¶ i b» ng kh«ng vµ c¸ c hÖ sè a0, a1, , ak lµ kh«ng ®æi v× kh«ng phô thuéc vµ o n. 11
  13. n Sau khi gi¶ thiÕ t tn = x ta ®­a (VII.1) vÒ d¹ ng: n n-1 n-k a0x + a1x + + akx = 0 n-k k k-1 hay x (a0x + a1x + + ak) = 0 Râ rµ ng x = 0 lµ nghiÖ m hiÓ n nhiª n, nh­ng ta quan t© m nghiÖ m ph­¬ng k k-1 tr× nh a0x + a1x + + ak = 0 (VII.2) vµ ®© y chÝ nh lµ ph­¬ng tr× nh ®Æ c tr­ng bË c k cña ph­¬ng tr× nh truy håi (VII.1) Gi¶ sö r1, r2, , rk lµ k nghiÖ m cña ph­¬ng tr× nh (VII.2) vµ chóng kh¸ c nhau (cã thÓ phøc). DÔ dµ ng kiÓ m tra: k = ∑ n t n ci ri i=1 Víi c1, c2, , ck lµ c¸ c h» ng x¸ c ®Þ nh tõ k ®iÒ u kiÖ n ban ®Ç u. VÝ dô 1 : XÐ t ph­¬ng tr× nh truy håi: − − = t n 3t n−1 4t n−2 0 §iÒ u kiÖ n ban ®Ç u : t0 = 1 ; t1 =1 Ph­¬ng tr× nh ®Æ c tr­ng t­¬ng øng cña nã lµ : x2 - 3x - 4 = 0 cã nghiÖ m b» ng -1 vµ 4. VË y nghiÖ m tæng qu¸ t lµ : n n = − + t n c1( 1) c2 (4) Theo ®iÒ u kiÖ n ban ®Ç u (khi n =0 vµ n = 1) ta cã : c1 + c2 = 1 = t0 - c1 + 4c2 =1 n n VË y c1 = 3/5, c2 = 2/5. Ta ®­îc tn = - [4 - (-1) ] /5 VÝ dô 2 : (ph­¬ng tr× nh Fibonacci) ≥ tn = tn-1 + tn-2 n 2 §iÒu kiÖn : t0 = 0, t1 = 1 ViÕ t l¹ i ph­¬ng tr× nh trª n : tn - tn-1 - tn -2 = 0 Ph­¬ng tr× nh ®Æ c tr­ng t­¬ng øng : x2 - x -1 = 0 12
  14. = + = − NghiÖ m : r1 (1 5)/ 2 , r2 (1 5)/ 2 n n NghiÖ m tæng qu¸ t : tn = c1r1 + c2r2 Tõ ®iÒ u kiÖ n ban ®Ç u : c1 + c2 = 0 (n = 0) r1c1 + r2c2 = 1 (n =1) = Ta cã c1 1/ 5 , = − c2 1/ 5 − VË y: tn = (r1n r2 n)/ 5 Gi¶ sö c¸ c nghiÖ m ph­¬ng tr× nh ®Æ c tr­ng lµ kh«ng ph© n biÖ t, P(x) lµ 1 ®a thøc. k k-1 P(x) = a0x + a1x + + ak vµ r lµ nghiÖ m kÐ p. Víi mçi r > k, ta xÐ t ®a thøc bË c n ®­îc x¸ c ®Þ nh nh­ sau : n-k n n-1 n-k h(x) = x [x P(x)] = a0nx + a1(n-1)x + + ak(n-k)x §Æt q(x) lµ ®a thøc tháa ®iÒ u kiÖ n P(x) = (x-r)2 q(x) Ta cã : h(x) = x[(x-r)2 xn-k q(x)] = x[2(x-r)xn-k q(x) + (x-r)2[xn-k q(x)]] Râ rµ ng h(r) = 0, do ®ã n n-1 n-k a0nr + a1(n-1)x + + ak(n-k) r = 0 NghÜ a lµ tn = nrn còng lµ nghiÖ m cña (5.13). Tæng qu¸ t h¬n, nÕ u nghiÖ m r trïng nhau m lÇ n (r béi m) th× n n 2 n m-1 n tn = r , tn = nr , tn = n r , , tn = n r còng lµ c¸ c nghiÖ m cña (5.13). NghiÖ m tæng qu¸ t (nghiÖ m chung) lµ tæ hîp tuyÕ n tÝ nh cña c¸ c nghiÖ m riª ng nµ y vµ nghiÖ m riª ng kh¸ c cña ph­¬ng tr× nh ®Æ c tr­ng. K h» ng ®­îc x¸ c ®Þ nh tõ c¸ c ®iÒ u kiÖ n ban ®Ç u. VÝ dô 3 : XÐ t ph­¬ng tr× nh ≥ tn = 5tn-1 - 8tn-2 + 4tn-3 n 3 víi c¸ c ®iÒ u kiÖ n t0 = 0, t1 = 1, t2 = 2 Ta viÕ t l¹ i ph­¬ng tr× nh: tn - 5tn-1 + 8tn-2 - 4tn-3 = 0 vµ ph­¬ng tr× nh ®Æ c tr­ng t­¬ng øng lµ : x3 - 5x2 + 8x - 4 = 0 hay (x-1) (x-2)2 = 0 13
  15. Ta cã c¸ c nghiÖ m 1 (cã béi 1), 2 (cã béi 2). VË y nghiÖ m tæng qu¸ t lµ : n n n tn = c11 + c22 + c3n2 C¸ c ®iÒ u kiÖ n ban ®Ç u cho tr­íc lµ : c1 + c2 = 0 khi n = 0 c1 + 2c2 + 2c3 = 1 khi n = 1 c1 + 4c2 + 8c3 = 2 khi n = 2 n+1 n-1 Tõ ®© y ta t× m ra c1 = -2, c2 = 2, c3 = -1/2. VË y tn = 2 - n2 - 2 b) Ph­¬ng tr× nh truy håi kh«ng thuÇ n nhÊ t: Ta xÐ t ph­¬ng tr× nh cã d¹ ng sau : n a0tn + a1tn-1 + + aktn-k = b P(n) (VII.3) Trong ®ã vÕ tr¸ i nh­ trong (VII.1), vÕ ph¶ i lµ bnP(n) víi b lµ h» ng vµ P(n) lµ ®a thøc. VÝ dô 4 : n tn - 2tn-1 = 3 th× b = 3 vµ P(n) = 1 lµ ®a thøc bË c 0. B» ng phÐ p biÕ n ®æi ®¬n gi¶ n ta cã thÓ chuyÓ n vÝ dô nµ y vÒ d¹ ng (VII.1) lµ ph­¬ng tr× nh truy håi thuÇ n nhÊ t. Tr­íc hÕ t ta nh© n 2 vÕ cho 3 ta ®­îc : n+1 3tn - 6tn-1 = 3 (1) Sau ®ã ta thay n ra n + 1 trong ph­¬ng tr× nh ban ®Ç u: n+1 tn+1 - 2tn = 3 (2) Cuèi cïng, lÊ y (2) - (1) , ta thu ®­îc (cã cïng vÕ ph¶ i 3n+1), ta ®­îc: tn+1 - 5tn + 6tn-1 = 0 §Õn ®© y ta cã thÓ gi¶ i ph­¬ng tr× nh ®∙ tr× nh bµ y ë môc a. Ph­¬ng tr× nh ®Æ c tr­ng cña nã lµ : x2 - 5x + 6 = 0 hay (x-2) (x-3) = 0 Trùc gi¸ c cho ta thÊ y r» ng thµ nh phÇ n (x-2) t­¬ng øng víi vÕ tr¸ i ph­¬ng tr× nh ban ®Ç u; cßn (x-3) lµ biÓ u hiÖ n kÕ t qu¶ cña viÖ c biÕ n ®æi vµ trõ vÕ ph¶ i. VÝ dô 5 : n tn - 2tn-1 = (n+5)3 14
  16. Sù biÕn ®æi cã phøc t¹p nh­ sau : - Nh© n 2 vÕ cho 9 - Thay n bëi n+2 - Thay n bëi n+1,sau ®ã nh© n cho -6 - Ta ®­îc kÕ t qu¶ : n+2 9tn - 18tn-1 = (n + 5) 3 n+2 tn+2 - 2tn+1 = (n + 7) 3 n+1 -6tn+1 + 12tn = -6(n + 6) 3 Céng 3 ph­¬ng tr× nh l¹ i ta ®­îc : tn+2 - 8tn+1 + 21tn - 18tn-1 = 0 Ph­¬ng tr× nh ®Æ c tr­ng. x2 - 8x2 + 21x - 18 = 0 hay (x-2) (x-3)2 = 0 Ta l¹ i thÊ y (x-2) t­¬ng øng vÕ tr¸ i ph­¬ng tr× nh ban ®Ç u vµ (x-3)2 lµ kÕ t qu¶ cña sù biÕ n ®æi. Nh­ vË y chóng ta cã thÓ nãi r» ng ®Ó gi¶ i ph­¬ng tr× nh truy håi kh«ng thuÇ n nhÊ t cã d¹ ng (VII.3) ta chØ cÇ n gi¶ i ph­¬ng tr× nh ®Æ c tr­ng sau. k k-1 d+1 (a0x + a1x + + ak) (x-b) = 0 (VII.4) VÝ dô 6 : (bµ i to¸ n th¸ p Hµ Néi) Ph­¬ng tr× nh truy håi cho bµ i to¸ n chuyÓ n n ®Ü a nµ y cã d¹ ng: 1 nÕ u n = 1 tn = { 2tn-1 + 1 nÕ u n > 1 hay tn = 2tn-1 + 1, n > 1 víi t0 = 0 Ta viÕ t l¹ i ph­¬ng tr× nh : tn - 2tn-1 = 1 Vµ thÊ y nã cã d¹ ng (VII.3) víi b = 1, P(n) = 1 bË c 0 Ph­¬ng tr× nh ®Æ c tr­ng lµ (x-2) (x-1) = 0 n n VË y : tn =c11 + c22 . Tõ t0 = 0 ®Ó t× m t1 ta viÕ t : t1 = 2to + 1 = 1 VË y c1 + c2 = 0, n = 0 c1 + 2c2 = 1, n = 1 n Suy ra c1 = -1, c2 = 1. VË y tn = 2 -1 n n n Ta nhË n thÊ y tõ tn = c11 + c22 còng cã thÓ kÕ t luË n tn cã O(2 ). 15
  17. VÝ dô 7 : tn = 2tn-1 + n hay tn - 2tn-1 = n ë ®© y b = 1, P(n) = n bË c 1 Ta cã ph­¬ng tr× nh ®Æ c tr­ng: (x-2) (x-1)2 = 0 VË y nghiÖ m tæng qu¸ t lµ : n n n tn = c12 + c21 + c3n1 NÕ u tn > 0 víi mçi n th× ta cã thÓ kÕ t luË n T(n)= O(2n), B© y giê ta xÐ t ph­¬ng tr× nh truy håi kh«ng thuÇ n nhÊ t tæng qu¸ t h¬n. n n aotn +a1tn-1 + + aktn-k = b1 p1(n) + b2 p2(n) + (VII.5) Trong ®ã bi lµ c¸ c h» ng kh¸ c nhau vµ pi(n) lµ c¸ c ®a thøc bË c di cña n. B» ng c¸ ch biÕ n ®æi gÇ n nh­ t­¬ng tù víi d¹ ng ph­¬ng tr× nh (VII.1), ta cã thÓ viÕt ®­îc ph­¬ng tr× nh ®Æ c tr­ng cho d¹ ng (VII.1)5) nh­ sau : k k-1 d1+1 d2+1 (aox + a1x + + ak) (x-b1) (x-b2) = 0 (VII.6) VÝ dô 8 : Gi¶ i ph­¬ng tr× nh n ≥ tn = 2tn-1 + n + 2 n 1 víi to = 0, ta cã n tn - 2tn-1 = n + 2 cã d¹ ng (VII.1)5) víi b1 = 1, p1(n) = n, b2 = 2, p2(n) = 1. BË c cña p1(n) lµ 1, bË c cña p2(n) lµ 0. VË y ph­¬ng tr× nh ®Æ c tr­ng lµ : (x-2) (x-1)2 (x-2) = 0 C¶ hai nghiÖ m 1 vµ 2 ®Ò u cã béi lµ 2. VË y nghiÖ m tæng qu¸ t cña ph­¬ng tr× nh truy håi lµ : n n n n tn = c11 + c2n1 + c32 + c4n2 n Sö dông d¹ ng truy håi tn = 2tn-1 + n+ 2 víi to = 0 ta cã thÓ tÝ nh ®­îc t1, t2 vµ t3 vµ tõ ®ã x¸c ®Þ nh ®­îc c¸ c hÖ sè c1, c2, c3 vµ c4 qua hÖ sau: c1 + c3 = 0 khi n = 0 c1 + c2 + 2c3 + 2c4 = 3 n = 1 c1 + 2c2 + 4c3 + 8c4 = 12 n = 2 c1 + 3c2 + 8c3 + 24c4 = 35 n = 3 16
  18. KÕ t qu¶ cuèi cïng lµ : n+1 n tn = -2 -n + 2 + n2 n DÔ dµ ng nhË n thÊ y tn cã O(n2 ) VÝ dô 9 : Gi¶ sö n lµ lòy thõa cña 2. T× m T(n) tõ ph­¬ng tr× nh: T(n) = 4T(n/2) + n, n > 1 Thay n b» ng 2k (víi k = logn), ta cã T(2k) = 4T(2k-1) + 2k. Khi ®ã ta cã thÓ viÕ t: k tk = 4tk-1 + 2 NÕ u tk = T(2k) = T(n). Ta ®∙ biÕ t c¸ ch gi¶ i ph­¬ng tr× nh truy håi míi nµ y. Ph­¬ng tr× nh ®Æ c tr­ng cña nã lµ : (x-4) (x-2) = 0 k k vµ tõ ®ã ta cã tk = c14 + c22 §Æt n ng­îc l¹ i thay cho k, ta t× m ®­îc : 2 T(n) = c1n + c2n Do ®ã T(n) cã 0(n2) khi n lµ lòy thõa cña 2. VÝ dô 10 : T(n) = 4t(n/2) + n2, n > 1, lòy thõa cña 2. §Æt n = 2k, ta cã. T(2k) = 4T(2k-1) + 4k k k Ph­¬ng tr× nh ®Æ c tr­ng (x-4)2 = 0 vµ ta cã tk = c14 + c2k4 2 2 VË y T(n) = c1n2 + c2n logn vµ T(n) lµ 0(n logn) víi n lòy thõa 2. VÝ dô 11 : T(n) = 2T(n/2) + nlogn, n > 1 Sau khi thay n = 2k, ta cã T(2k )= 2T(2k-1) + k2k vµ k tk = 2tk-1 + k2 3 k k 2 k Ph­¬ng tr× nh ®Æ c tr­ng (x-2) = 0 vµ tk = c12 + c2k2 + c3k 2 . 2 2 VË y T(n) = c1n + c2nlogn + c3nlog n cã 0(nlog n), n lòy thõa 2. 17
  19. VÝ dô 12 : T(n) = 3T(n/2) + cn (c lµ const, n = 2k> 1) Ta sÏ nhË n ®­îc : k k-1 k k T(2 ) = 3T(2 ) + c2 ; tk = 3tk-1 + c2 Ph­¬ng tr× nh ®Æ c tr­ng lµ (x-3) (x-2) = 0, vµ do ®ã. k k logn Tk = c13 + c22 ; T(n) = c13 + c2n log3 log3 Do alogb = bloga nª n T(n) = c1n + c2n cã 0(n ),n lòy thõa 2. c) Ph­¬ng tr× nh truy håi cã hÖ sè biÕ n ®æi Ta xÐ t vÝ dô cô thÓ : T(1) = 6 T(n) = nT2(n/2), n > 1,n lòy thõa cña 2 (hÖ sè ë vÕ ph¶i lµ biÕn n) k Tr­íc hÕ t ta ®Æ t tk = T(2 ) vµ tõ ®Ê y ta cã : k 2 tk = 2 t K-1 k > 0 to = 6 §Ó lË p ph­¬ng tr× nh truy håi míi kh«ng cã hÖ sè biÕ n ®æi ta ®Æ t Vk = lgtk, ta ®­îc : Vk = K + 2Vk-1 k >0 Vo = lg6 NghÜ a lµ ta cã hÖ ph­¬ng tr× nh d¹ ng (VI.3) Ph­¬ng tr× nh ®Æ c tr­ng sÏ lµ (x-2) (x-1)2 = 0 vµ do ®ã : k k k Vk = c12 + c21 + c3k1 Tõ Vo = 1 + lg3, V1 = 3+2lg3 vµ V2 = 8 + 4lg3 ta t× m ra c1 = 3 + lg3, c2 = -2 vµ c3 = -1. k VË y V3 = (3 + lg3) 2 - K -2 Cuèi cïng, sö dông tk = 2vk vµ T(n) = tlgn, ta ®­îc : 23n−23n T(n) = n 18
  20. ch­¬ng Ii ®Ö qui I. Kh¸i niÖm : §Ö qui lµ 1 c«ng cô rÊ t th­êng dïng trong khoa häc m¸ y tÝ nh vµ trong to¸ n häc ®Ó gi¶ i quyÕ t c¸ c vÊ n ®Ò . Tr­íc hÕ t, chóng ta h∙y kh¶ o s¸ t thÕ nµ o lµ mét vÊ n ®Ò cã ®Ö qui qua vÝ dô sau: TÝ nh S(n) = 1 +2 +3 +4+ +n Ta nhË n thÊ y r» ng, c«ng thøc trª n cã thÓ diÔ n ®¹ t l¹ i nh­ sau: S(n) = S(n-1) + n, vµ S(n-1) = S(n-2) + (n-1) S(2) = S(1) + 2 S(1) = 1 Nh­ vË y, mét vÊn ®Ò cã ®Ö qui lµ vÊn ®Ò ®­îc ®Þ nh nghÜ a l¹i b»ng chÝ nh nã. Mét c¸ ch tæng qu¸ t, mét ch­¬ng tr× nh ®Ö qui cã thÓ ®­îc biÓ u diÔ n nh­ bé P gåm c¸ c mÖ nh ®Ò c¬ së S (kh«ng chøa P) vµ b¶ n th© n P: ≡ P P (Si, P) §Ó tÝ nh S(n): ta cã kÕ t qu¶ cña S(1), thay nã vµ o S(2), cã S(2) ta thay nã vµ o S(3) , cø nh­ vË y cã S(n-1) ta sÏ tÝ nh ®­îc S(n) Còng nh­ c¸ c lÖ nh lÆ p, c¸ c thñ tôc ®Ö qui còng cã thÓ thùc hiÖ n c¸ c tÝ nh to¸ n kh«ng kÕ t thóc, v× vË y ta ph¶ i xÐ t ®Õ n vÊ n ®Ò kÕ t thóc c¸ c tÝ nh to¸ n trong gi¶ i thuË t ®Ö qui. Râ rµ ng 1 thñ tôc P ®­îc gäi ®Ö qui chØ khi nµ o tháa 1 ®iÒu kiÖ n B, vµ dÜ nhiª n ®iÒ u kiÖ n B nµ y ph¶ i kh«ng ®­îc tháa m∙ n t¹ i 1 thêi ®iÓ m nµo ®ã. Nh­ vË y m« h× nh vÒ c¸ c gi¶ i thuË t ®Ö qui lµ : ≡ P if (B) P(Si, P) ≡ hay P P(Si, if (B) P). Th«ng th­êng trong c¸ c vßng lÆ p while, ®Ó ®¶ m b¶ o cho vßng lÆ p kÕ t thóc ta ph¶ i ®Þ nh nghÜ a mét hµ m f(x) (x lµ 1 biÕ n trong ch­¬ng tr× nh) sao cho nã ph¶ i tr¶ vÒ trÞ b» ng 0 t¹ i mét thêi ®iÓ m nµ o ®ã. T­¬ng tù nh­ vË y, ch­¬ng tr× nh ®Ö qui còng cã thÓ ®­îc chøng minh lµ sÏ dõng b» ng c¸ ch chøng minh r» ng hµ m f(x) sÏ gi¶ m sau mçi lÇ n thùc hiÖ n. Mét c¸ ch th­êng lµ m lµ kÕ t hîp mét gi¸ trÞ n víi P vµ gäi P mét c¸ ch ®Ö qui víi gi¸ trÞ tham sè lµ n-1. §iÒ u kiÖ n B b© y giê lµ n > 0 th× sÏ ®¶ m b¶ o ®­îc sù kÕ t thóc cña gi¶ i thuË t ®Ö qui. Nh­ vË y, ta cã m« h× nh ®Ö qui míi: ≡ P(n) if (n >0) P(Si, P(n-1)) ≡ Hay P P (Si, if (n>0) P(n-1) ) 19
  21. II. Hµm ®Ö qui vµ Stack: Mét ch­¬ng tr× nh C th­êng gåm cã hµ m main() vµ c¸ c hµ m kh¸ c. Khi ch¹ y ch­¬ng tr× nh C th× hµ m main() sÏ ®­îc gäi ch¹ y tr­íc, sau ®ã hµ m main() gäi c¸ c hµ m kh¸ c, c¸ c hµ m nµ y trong khi ch¹ y cã thÓ gäi c¸ c hµ m kh¸ c n÷a. Khi mét hµ m ®­îc gäi, th× mét khung kÝ ch ho¹ t cña nã ®­îc t¹ o ra trong bé nhí stack. Khung kÝ ch ho¹ t nµ y chøa c¸ c biÕ n côc bé cña hµ m vµ mÈ u tin ho¹ t ®éng cña hµ m. MÈ u tin ho¹ t ®éng chøa ®Þ a chØ trë vÒ cña hµ m gäi nã vµ c¸ c tham sè kh¸ c. BiÕ n côc bé MÈ u tin { §Þ a chØ trë vÒ ho¹ t ®éng Th«ng sè kh¸ c Khung kÝ ch ho¹ t Sau khi hµ m ®­îc gäi ®∙ thi hµ nh xong th× ch­¬ng tr× nh sÏ thùc hiÖ n tiÕ p dßng lÖ nh ë ®Þ a chØ trë vÒ cña hµ m gäi nã, ®ång thêi xãa khung kÝ ch ho¹ t cña hµ m ®ã khái bé nhí. Gi¶ sö ta cã c¬ chÕ gäi hµ m trong mét ch­¬ng tr× nh C nh­ sau: main() A() B() C() D() { { ; { ; { ; { ; A(); C(); D(); D(); ; ; ; } ; } B(); D(); } ; } } H× nh sau ®© y cho ta thÊ y sù chiÕ m dông bé nhí stack khi ch¹ y ch­¬ng tr× nh C nh­ m« t¶ ë trª n. Boä nhôù Stack D CCC D D AAAAAAA BBB MMMMMMMMMMMMM Thôøi gian T­¬ng tù víi tr­êng hîp hµ m ®Ö qui, khi gäi ®Ö qui lÉ n nhau th× mét lo¹ t c¸ c khung kÝ ch ho¹ t sÏ ®­îc t¹ o ra vµ n¹ p vµ o bé nhí Stack. CÊ p ®Ö qui cµ ng cao 20
  22. th× sè khung kÝ ch ho¹ t trong Stack cµ ng nhiÒ u, do ®ã, cã kh¶ n¨ ng dÉ n ®Õ n trµ n Stack (Stack overflow). Trong nhiÒ u tr­êng hîp khi lË p tr× nh, nÕ u cã thÓ ®­îc, ta nª n gì ®Ö qui cho c¸ c bµ i to¸ n. III. vÝ dô VÝ dô 1: Hµ m giai thõa: 1*2*3* *(n-1)*n , n>0 n! = { 1 , n=0 n*(n-1)! , n>0 n! = { 1 , n= 0 NhËn xÐ t: - Theo c«ng thøc trª n, ta nhË n thÊ y trong ®Þ nh nghÜ a cña n giai thõa (n!) cã ®Þ nh nghÜ a l¹ i chÝ nh nã nª n hµ m giai thõa cã ®Ö qui. - §iÒ u kiÖ n dõng tÝ nh hµ m giai thõa lµ n=0, khi ®ã n! = 1 - Hµ m ®Ö qui: long giaithua(int n) { if (n == 0) return(1); else return(n * giaithua(n-1)); } hay: long giaithua(int n) { return ((n==0) ? 1 : n*giaithua(n-1)); } - Hµ m kh«ng ®Ö qui: long giaithua (int n) { long gt=1; for (int i=1; i<=n; i++) gt= gt * i ; return (gt); } 21
  23. VÝ dô 2: Hµ m FIBONACCI: 1 ; n =0,1 Fn = { Fn-1 + Fn-2 ; n>1 NhËn xÐ t: - Theo ®Þ nh nghÜ a trª n, hµ m Fibonacci cã lêi gäi ®Ö qui. - Qu¸ tr× nh tÝ nh dõng l¹ i khi n= 1 - Hµ m ®Ö qui: long fib(int n) { if (n==0 || n==1) return 1 ; else return(fib(n-1) + fib(n-2)); } - Hµ m kh«ng ®Ö qui: long fib(int n) { long kq, Fn_1, Fn_2; kq = 1; if (n > 1) { Fn_1 = 1; Fn_2 = 1; for (int i=2; i<=n; i++) { kq = Fn_1 + Fn_2 ; Fn_2 = Fn_1; Fn_1 = kq; } } return (kq); } VÝ dô 3: Bµ i to¸ n Th¸ p Hµ néi Cã 3 cét A, B, C. Cét A hiÖ n ®ang cã n dÜ a kÝ ch th­íc kh¸ c nhau, dÜ a nhá ë trª n dÜ a lín ë d­íi. H∙ y dêi n dÜ a tõ cét A sang cét C (xem cét B lµ cét trung gian) víi ®iÒ u kiÖ n mçi lÇ n chØ ®­îc dêi 1 dÜ a vµ dÜ a ®Æ t trª n bao giê còng nhá h¬n dÜ a ®Æ t d­íi. 22
  24. - Gi¶ i thuË t ®Ö qui: §Ó dêi n dÜ a tõ cét A sang cét C (víi cét B lµ cét trung gian), ta cã thÓ xem nh­ : + Dêi (n-1) dÜ a tõ cét A sang cét B ( víi cét C lµ cét trung gian) + Dêi dÜ a thø n tõ cét A sang cét C + Dêi (n-1) dÜ a tõ cét B sang cét C ( víi cét A lµ cét trung gian) - Ch­¬ng tr× nh: void hanoi (int n, char cotA, char cotC, char cotB) { if(n == 1) printf("\n%s%c%s%c", " chuyen dia 1 tu cot ", cotA, " den cot ", cotC); else { hanoi(n-1, cotA, cotB, cotC); printf("\n%s%d%s%c%s%c", " chuyen dia ", n, " tu cot ", cotA, " den cot ", cotC); hanoi(n-1, cotB, cotC, cotA); } } IV. C¸C THUËT TO¸N LÇN NG¦îC: Trong lË p tr× nh, ®«i khi ta ph¶ i x¸ c ®Þ nh c¸ c thuË t gi¶ i ®Ó t× m lêi gi¶ i cho c¸ c bµ i to¸ n nhÊ t ®Þ nh nh­ng kh«ng ph¶ i theo mét luË t tÝ nh to¸ n cè ®Þ nh, mµ b» ng c¸ ch thö-vµ -sai. C¸ ch chung lµ ph© n tÝ ch thö-vµ -sai thµ nh nh÷ng c«ng viÖ c côc bé. Th«ng th­êng c«ng viÖ c nµ y ®­îc thùc hiÖ n trong d¹ ng ®Ö qui vµ bao gåm viÖ c th¨ m dß mét sè h÷u h¹ n c¸ c nhiÖ m vô nhá. Trong bµ i gi¶ ng nµ y ta kh«ng t× m hiÓ u c¸ c qui t¾ c t× m kiÕ m tæng qu¸ t, mµ chØ t× m nh÷ng nguyª n lý chung ®Ó chia viÖ c gi¶ i bµ i to¸ n thµ nh nh÷ng viÖ c nhá vµ øng dông cña sù ®Ö qui lµ chñ ®Ò chÝ nh. Tr­íc hÕ t, ta minh häa kü thuË t c¨ n b¶ n b» ng c¸ ch xÐ t bµ i to¸ n m∙ ®i tuÇ n. VÝ dô 1. Bµ i to¸ n m∙ ®i tuÇ n. Cho bµ n cê cã n x n «. Mét con m∙ ® ­îc phÐ p ®i theo luË t cê vua, ®Ç u tiª n nã ®­îc ®Æt ë « cã to¹ ®é x0, y0. C© u hái lµ , nÕ u cã th× h∙ y t× m c¸ ch sao cho con m∙ ®i qua ®­îc tÊ t c¶ c¸ c « cña bµ n cê, mçi « ®i qua ®óng 1 lÇ n. * LuË t ®i cña con m∙ trª n bµ n cê: T¹ i mét « cã täa ®é cét x0, hµ ng y0 (x0,y0) trª n bµ n cê, con m∙ cã 1 trong 8 n­íc ®i nh­ sau: 23
  25. 3 2 4 1 Con M∙ 5 8 6 7 H× nh 2.1 8 n­íc ®i cã thÓ cña con m∙ xuÊt ph¸t tõ cét x0, hµng y0. Víi täa ®é b¾ t ®Ç u (x0,y0), cã tÊ t c¶ 8 « (u,v) mµ con m∙ cã thÓ ®i ®Õn ®­îc. Chóng ®­îc ®¸nh sè tõ 1 ®Õ n 8 trong h× nh 2.1 Ph­¬ng ph¸p ®¬n gi¶n ®Ó cã ®­îc u,v tõ x,y lµ céng c¸ c chª nh lÖ ch cét, dßng vÒ täa ®é ®­îc l­u trong 2 m¶ ng a vµ b. C¸ c gi¸ trÞ trong 2 m¶ ng a, b ®∙ ®­îc khëi ®éng thÝ ch øng nh­ sau: Ta xem nh­ cã 1 hÖ trôc täa ®é (Oxy) ngay t¹ i vÞ trÝ (x0,y0) cña con m∙ , th× : + VÞ trÝ 1 mµ con m∙ cã thÓ ®i ®­îc lµ : u= x0 + 2, v = y0 + 1 + VÞ trÝ 2 mµ con m∙ cã thÓ ®i ®­îc lµ : u= x0 + 1, v = y0 + 2 + VÞ trÝ 3 mµ con m∙ cã thÓ ®i ®­îc lµ : u= x0 + (-1), v = y0 + 2 Nh­ vË y, m¶ ng a vµ b cã gi¸ trÞ sau: int a[8] = {2, 1, -1,-2, -2, -1, 1, 2}; int b[8] = {1, 2, 2, 1, -1, -2,-2, -1}; * C¸ ch biÓ u diÔ n d÷ liÖ u: §Ó m« t¶ ®­îc bµ n cê, ta dïng ma trË n BanCo theo khai b¸ o sau: #define KICHTHUOC 5 // KÝ ch th­íc cña bµ n cê int BanCo[KICHTHUOC][KICHTHUOC]; // Tæ chøc bµ n cê lµ m∙ng hai chiÒ u Ta thÓ hiÖ n mçi « cê b» ng 1 sè nguyª n ®Ó ®¸ nh ®Ê u « ®ã ®∙ ® ­îc ®i qua ch­a, v× ta muèn lÇ n dß theo qu¸ tr× nh di chuyÓ n cña con m∙ . Vµ ta qui ­íc nh­ sau: BanCo [x][y]=0 ; « (x,y) ch­a ®i qua BanCo [x][y]=i ; « (x,y) ®∙ ®­îc ®i qua ë n­íc thø i ( 1 ≤ i ≤ n2 ) 24
  26. * ThuËt gi¶i: C¸ ch gi¶ i quyÕ t lµ ta ph¶ i xÐ t xem cã thÓ thùc hiÖ n mét n­íc ®i kÕ n÷a hay kh«ng tõ vÞ trÝ x0, y0. ThuË t gi¶ i ®Ó thö thùc hiÖ n n­íc ®i kÕ. void thö n­íc ®i kÕ { khëi ®éng c¸ c chän lùa cã thÓ ®i do { chän mét n­íc ®i; if chÊ p nhË n ®­îc { ghi nhË n n­íc ®i; if bµ n cê ch­a ®Ç y { thö n­íc ®i kÕ t¹ i vÞ trÝ võa ghi nhË n ®­îc; if kh«ng ®­îc xãa n­íc ®i tr­íc } } } while (kh«ng ®i ®­îc && cßn n­íc ®i) } * NhËn xÐ t: - §Ó x¸ c ®Þ nh täa ®é (u,v) cña n­íc ®i kÕ ( 0 ≤ i ≤ 7 ), ta thùc hiÖ n nh­ sau: u = x + a[i] ; v = y + b[i] - §iÒ u kiÖ n ®Ó n­íc ®i kÕ chÊ p nhË n ®­îc lµ (u,v) ph¶ i thuéc bµ n cê vµ con m∙ ch­a ®i qua « ®ã, nghÜ a lµ ta ph¶ i tháa c¸ c ®iÒ u kiÖ n sau: (0 ≤ u <KICHTHUOC && 0 ≤ v< KICHTHUOC && BanCo[u][v]==0 ) - Ghi nhË n n­íc ®i thø n, nghÜ a lµ BanCo [u][v] = n; cßn bá viÖ c ghi nhË n n­íc ®i lµ BanCo [u][v] = 0 - Bµ n cê ®Ç y khi ta ®∙ ®i qua tÊ t c¶ c¸ c « trong BanCo, lóc ®ã : n = KICHTHUOC 2. Qua nhË n xÐ t trª n, ta cã thuË t gi¶ i chi tiÕ t h¬n nh­ sau: void thu_nuoc_di(int n, int x, int y, int &q) // thö 8 c¸ ch ®i cña con m∙ t¹ i // n­íc thø n xuÊt ph¸t tõ « (x,y) { int u,v, q1; khëi ®éng c¸ c chän lùa cã thÓ ®i 25
  27. do { u = x + a[i] ; v = x + b[i]; if (0 ≤ u #include #include #define KICHTHUOC 5 // KÝ ch th­íc cña bµ n cê #define TRUE 1 #define FALSE 0 // Tæ chøc bµ n cê lµ m∙ ng hai chiÒ u int BanCo[KICHTHUOC][KICHTHUOC]; // 8 c¸ ch ®i cña con m∙ int a[8] = {2, 1, -1,-2, -2, -1, 1, 2}; int b[8] = {1, 2, 2, 1, -1, -2,-2, -1}; void innuocdi(int BanCo[][KICHTHUOC]) { int i, j; char c; randomize(); textmode(C80); textbackground(BLACK); 26
  28. textcolor(1); for(i = 0; i = 0 && u = 0 && v < KICHTHUOC) if (BanCo[u][v] ==0) { // §i n­íc thø n BanCo[u][v] = n; if (n < KICHTHUOC*KICHTHUOC) // D/kien dung, di duoc nuoc cuoi { try(n+1, u, v, q1); // Buoc de qui, goi di nuoc n+1 if (q1 == FALSE) BanCo[u][v]=0; } else q1=TRUE; } } while (q1==FALSE && k <7); q=q1; } void vebanco() { 27
  29. printf("\n\t\t\t CHUONG TRINH MA DI TUAN\n"); printf("\n\t\tKich thuoc ban co %dx%d", KICHTHUOC, KICHTHUOC); printf("\n\n\t\t 0 1 2 3 4 5 6 7"); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 0          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 1          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 2          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 3          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 4          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 5          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 6          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 7          "); printf("\n\t\t + + + + + + + + + "); } void main() { int i, j,q; clrscr(); vebanco(); for(i = 0; i < KICHTHUOC; i++) for(j = 0; j < KICHTHUOC; j++) BanCo[i][j] = 0; // Chon nuoc di dau tien va goi ham de qui de di nuoc thu hai BanCo[0][0] = 1; thu_nuoc_di(2, 0, 0,q); if (q==FALSE) printf ("\n Khong co loi giai"); else innuocdi(BanCo); } 28
  30. * B¶ ng sau ®© y cho ta mét sè lêi gi¶ i t­¬ng øng víi c¸ c vÞ trÝ ®Ç u vµ kÝ ch th­íc cña bµ n cê: - KÝ ch th­íc bµ n cê = 5 + VÞ trÝ b¾ t ®Ç u (1,1) + VÞ trÝ b¾ t ®Ç u (3,3) 1 6 15 10 21 23 10 15 4 25 14 9 20 5 16 16 5 24 9 14 19 2 7 22 11 11 22 1 18 3 8 13 24 17 4 6 17 20 13 8 25 18 3 12 23 21 12 7 2 19 - KÝ ch th­íc bµ n cê = 8 + VÞ trÝ b¾ t ®Ç u (1,1) 1 60 39 34 31 18 9 64 38 35 32 61 10 63 30 17 59 2 37 40 33 28 19 8 36 49 42 27 62 11 16 29 43 58 3 50 41 24 7 20 48 51 46 55 26 21 12 15 57 44 53 4 23 14 25 6 52 47 56 45 54 5 22 13 VÝ dô 2: Bµ i to¸ n t¸ m hoµ ng hË u. Bµ i to¸ n t¸ m hµ ng hË u ®­îc m« t¶ nh­ sau: t¸ m hoµ ng hË u ®­îc ®Æ t lª n bµ n cê vua sao cho kh«ng bµ nµ o cã thÓ chiÕ m lÊ y c¸ c bµ kh¸ c. * Theo luË t cña cê vua, mét hoµ ng hË u cã thÓ chiÕ m lÊ y c¸ c qu© n kh¸ c n» m ë cïng dßng, hay cïng cét, hay cïng c¸ c ®­êng chÐ o. Do ®ã, ta suy ra r» ng mçi cét chØ cã thÓ chøa mét hoµ ng hË u vµ chØ 1 mµ th«i. Ta qui ­íc hoµ ng hË u thø 0 sÏ ®Æ t ë cét 0, hoµ ng hË u thø 1 sÏ ®Æt ë cét 1, , hoµ ng hË u thø 7 sÏ ®Æ t ë cét 7. Nh­ vË y, viÖ c chän chç cho hoµ ng hË u thø i lµ t× m vÞ trÝ dßng j cã thÓ cã trª n cét i. Sau ®© y lµ h× nh minh häa cho mét lêi gi¶ i cña bµ i to¸ n: (0 6 4 7 1 3 5 2) 29
  31. 0 Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q * C¸ ch biÓ u diÔ n d÷ liÖ u: Bµ n cê 8x8 cã 8 hµ ng, 8 cét, 15 ®­êng chÐ o xu«i, 15 ®­êng chÐ o ng­îc, ta qui ­íc 1 con hË u chØ cã thÓ ®Æ t trª n 1 cét i vµ hµ ng j nµ o ®ã cña bµ n cê. Khi ®ã, c¸ c vÞ trÝ trª n ®­êng chÐ o xu«i vµ ®­êng chÐ o ng­îc cña bµ n cê kh«ng thÓ dïng ®Ó ®Æ t c¸ c con hË u kh¸ c. Ta l­u ý r» ng c¸ c phÇ n tö cïng n» m trª n 1 ® ­êng chÐ o xu«i cña bµ n cê tháa m∙ n biÓ u thøc sau (cét i - hµ ng j + 7 = h» ng sè), vµ c¸ c phÇ n tö cïng n» m trª n 1 ® ­êng chÐ o ng­îc cña bµ n cê tháa m∙ n biÓ u thøc sau (cét i + hµ ng j = h» ng sè) nh­ h× nh sau: ®­êng chÐ o xu«i ®­êng chÐo ng­îc §­êng §­êng chÐo xu«i chÐo ng­îc Haøng j:0 14 0 1 13 1 2 12 2 3 11 3 4 10 4 5 6 9 5 7 8 6 0 1 2 3 4 5 6 7 78910 11 12 13 14 Nh­ vË y, ta sÏ x© y dùng cÊ u tróc d÷ liÖ u sau ®Ó l­u tr÷ d÷ liÖ u: int hang_trong[8] ; // hµ ng trèng cßn cã thÓ ®Æ t hoµ ng hË u int cheo_xuoi[15]; // duong cheo xuoi co the dat hoang hau. Cac phan tu tren duong cheo xuoi //thoa (cot i -hang j +7 = hangso) int cheo_nguoc[15]; 30
  32. // duong cheo nguoc co the dat hoang hau. Cac phan tu tren duong cheo // nguoc thoa (cot i +hang j = hangso) int loi_giai[8] ; // loi giai chua ket qua. víi: - hang_trong[j] = TRUE nghÜ a lµ ch­a cã con hË u nµ o trª n hµ ng thø j - cheo_xuoi[k] = TRUE nghÜ a lµ ch­a cã con hË u nµ o trª n ®­êng chÐ o xu«i thø k - cheo_nguoc[k] = TRUE nghÜ a lµ ch­a cã con hË u nµ o trª n ®­êng chÐ o ng­îc thø k VÝ dô: C¸ c vÞ trÝ trª n ®­êng chÐo xu«i thø 12 : 5 - 0 +7 = 6 -1 +7 = 7 -2 + 7 = 12 C¸ c vÞ trÝ trª n ®­êng chÐ o ng­îc thø 12: 7 + 5 = 6 + 6 = 5 + 7 = 12 -loi_giai[i] chØ vÞ trÝ cña hoµ ng hË u ë cét thø i * ThuËt gi¶i: void chon_vi_tri (int i) // t× m vÞ trÝ thÝ ch hîp cho hoµ ng hË u thø i { khëi ®éng c¸ c vÞ trÝ cã thÓ chän cho hoµ ng hË u thø i do { chän vÞ trÝ kÕ ; if an toµ n { ®Æ t hoµ ng hË u if ch­a ®Æ t hÕ t 8 hoµ ng hË u { chon_vi_tri (i+1); if kh«ng thµ nh c«ng dêi hoµ ng hË u ®i } } } while (kh«ng thµ nh c«ng && ch­a ®Æ t hÕ t c¸ c vÞ trÝ ) } * NhËn xÐ t: Víi c¸ c d÷ liÖ u ®∙ cho, th× : - §iÒ u kiÖ n an toµ n lµ ®iÒ u kiÖ n sao cho hoµ ng hË u thø i (cét i) n» m trª n hµ ng j sao cho hµ ng j vµ c¸ c ®­êng chÐ o ®i qua « (j,i) ch­a bÞ chiÕ m gi÷ bëi c¸ c hoµ ng hË u kh¸ c; nghÜ a lµ nã ph¶ i tháa biÓ u thøc logic: hang_trong[j] && cheo_xuoi [i-j+7] && cheo_nguoc[i+j] - §Æt hoµ ng hË u sÏ ®­îc thÓ hiÖ n bëi: 31
  33. loi_giai[i] = j ; hang_trong[j] = FALSE ; cheo_xuoi [i-j+7] =FALSE; cheo_nguoc[i+j] = FALSE; - Dêi hoµ ng hË u ®i sÏ ®­îc thÓ hiÖ n bëi: hang_trong[j]=TRUE ; cheo_xuoi [i-j+7] =TRUE; cheo_nguoc[i+j] = TRUE; - §iÒu kiÖn ch­a ®Æ t hÕ t c¸ c hoµ ng hË u : i #include #include #define TRUE 1 #define FALSE 0 // tim 1 loi giai cho bai toan 8 hoang hau int hang_trong[8] ; // hµ ng trong con co the dat hoang hau int cheo_xuoi[15]; // duong cheo xuoi co the dat hoang hau. Cac phan tu // tren duong cheo xuoi thoa (cot i -hang j +7 = hangso) int cheo_nguoc[15]; // duong cheo nguoc co the dat hoang hau. Cac phan tu // tren duong cheo nguoc thoa (cot i +hang j = hangso) int loi_giai[8] ; // loi giai chua ket qua. int i, q; void in_loigiai(int *loigiai) { int i, j; char c; randomize(); textmode(C80); textbackground(BLACK); clrscr(); textcolor(1 + random(15)); 32
  34. printf("\n\t\t\t CHUONG TRINH 8 HOANG HAU\n"); printf("\n\n\t\t 0 1 2 3 4 5 6 7 "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 0          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 1          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 2          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 3          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 4          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 5          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 6          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 7          "); printf("\n\t\t + + + + + + + + + "); for(i = 0; i < 8; i++) { gotoxy(24+5*i,8+2*loigiai[i] ); textcolor(1 + random(15)); cprintf("Q"); } gotoxy(13, 25); printf("Nhan phim bat ky de thoat "); getche(); } void chon_vi_tri ( int i, int &q) { int j= -1; do { j++; q=FALSE; if (hang_trong[j] && cheo_xuoi[i-j+7] && cheo_nguoc[i+j]) { loi_giai[i]= j; hang_trong[j]=FALSE; cheo_xuoi[i-j+7] = FALSE; 33
  35. cheo_nguoc[i+j]=FALSE; if (i < 7) { chon_vi_tri (i+1,q); if (q==FALSE) { hang_trong[j]=TRUE; cheo_xuoi[i-j+7] = TRUE; cheo_nguoc[i+j]=TRUE; } } else q=TRUE; } } while ((q==FALSE) && (j<7)); //Ch­a thµ nh c«ng vµ ch­a hÕ t vÞ trÝ // th× tiÕ p tôc } void main (void) { /*Khoi dong tat ca cac hang, duong cheo xuoi, duong cheo nguoc deu co the dat hoang hau */ for(i = 0; i < 8; i++) hang_trong[i] = TRUE; for(i = 0; i < 15; i++) { cheo_xuoi [i] = TRUE; cheo_nguoc[i] = TRUE; } // Goi ham de qui de bat dau dat HoangHau0 (hoang hau o cot 0) chon_vi_tri (0,q); in_loigiai(loi_giai); } L­u ý: - Trª n ®© y lµ thuË t gi¶ i t× m mét lêi gi¶ i cho bµ i to¸ n 8 hoµ ng hË u. Tuy nhiª n, ta cã thÓ më réng ®Ó cã thÓ t× m mäi lêi gi¶ i cho bµ i to¸ n. S¬ ®å tæng qu¸ t cho gi¶ i thuË t back-tracking ®Ó t× m mäi lêi gi¶ i cho bµ i to¸ n: 34
  36. void chon_vi_tri (int i) { int j; for (j=0; j #include #include #define TRUE 1 #define FALSE 0 // tim tat ca loi giai cho bai toan 8 hoang hau int hang_trong[8] ; // cot trong con co the dat hoang hau int cheo_xuoi[15]; // duong cheo xuoi co the dat hoang hau int cheo_nguoc[15]; // duong cheo nguoc co the dat hoang hau int loi_giai[8] ; // loi giai chua ket qua int i, q; int SoLoiGiai =0; void in_loigiai(int *loigiai) { int i, j; char c; randomize(); textmode(C80); textbackground(BLACK); clrscr(); textcolor(1 + random(15)); 35
  37. cprintf("\n CHUONG TRINH 8 HOANG HAU\n "); printf("\n Loi giai thu %d", ++SoLoiGiai); printf("\n\n\t\t 0 1 2 3 4 5 6 7 "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 0          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 1          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 2          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 3          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 4          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 5          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 6          "); printf("\n\t\t + + + + + + + + + "); printf("\n\t\t 7          "); printf("\n\t\t + + + + + + + + + "); for(i = 0; i de thoat, nhan phim bat ky de tiep tuc "); c = getche(); if(c == 27) exit(1); } void chon_vi_tri( int i) { int j; for (j=0; j<8; j++) { if (hang_trong[j] && cheo_xuoi[i-j+7] && cheo_nguoc[i+j]) { loi_giai[i]= j; 36
  38. hang_trong[j]=FALSE; cheo_xuoi[i-j+7] = FALSE; cheo_nguoc[i+j]=FALSE; if (i < 7) chon_vi_tri (i+1); else in_loigiai(loi_giai); hang_trong[j]=TRUE; cheo_xuoi[i-j+7] = TRUE; cheo_nguoc[i+j]=TRUE; } } // for } // chon_vi_tri void main(void) { /* Khoi dong tat ca cac cot, duong cheo xuoi, duong cheo nguoc deu co the dat hoang hau */ for(i = 0; i < 8; i++) hang_trong[i] = TRUE; for(i = 0; i < 15; i++) { cheo_xuoi [i] = TRUE; cheo_nguoc[i] = TRUE; } // Goi ham de qui de bat dau dat HoangHau0 (hoang hau o hang 0) chon_vi_tri (0); } 37
  39. Bµi tËp 1. ViÕ t mét hµ m ®Ö quy vµ kh«ng ®Ö quy ®Ó tÝ nh gi¸ trÞ cña hµ m 1 , n=0 P (x)= x , n =1 n { Pn-1(x) - Pn-2 (x) , n >= 2 2. ViÕ t ch­¬ng tr× nh Th¸ p Hµ Néi. M« t¶ ch­¬ng tr× nh Th¸ p Hµ Néi : Ta cã 3 cäc A, B, C vµ n dÜ a ®­îc xÕ p trª n cäc A sao cho dÜ a nhá trª n dÜ a lín. H∙ y viÕ t ch­¬ng tr× nh di chuyÓ n n dÜ a tõ cäc A sang cäc C víi cäc B lµ m trung gian, theo ®iÒ u kiÖ n : - Mçi lÇ n chØ di chuyÓ n mét dÜ a - Bao giê dÜ a nhá còng n» m trª n dÜ a lín 3. ViÕ t ch­¬ng tr× nh t× m mäi lêi gi¶ i cho bµ i to¸ n m∙ ®i tuÇ n. 38
  40. ch­¬ng Iii Danh s¸ch tuyÕn tÝ nh KH¸I NIÖM : Danh s¸ ch lµ mét tË p hîp n phÇ n tö a0, a1, a2, , an-1, mçi phÇ n tö cã kiÓ u ®¬n gi¶ n hoÆ c kiÓ u d÷ liÖ u cã cÊ u tróc. TÝ nh tuyÕ n tÝ nh cña danh s¸ ch thÓ hiÖ n ë sù rµ ng buéc gi÷a c¸ c phÇ n tö trong danh s¸ ch víi nhau, vÝ dô nh­ tõ vÞ trÝ cña phÇ n tö ai ta sÏ t× m ®­îc gi¸ trÞ cña phÇ n tö ai+1. I. §Þnh nghÜ a: Danh s¸ ch tuyÕ n tÝ nh lµ 1 d∙ y c¸ c phÇ n tö cã cïng kiÓ u d÷ liÖ u ®­îc s¾p xÕ p liª n tiÕ p nhau trong bé nhí. 0100 0102 0 int 0104 1 danh s¸ ch n phÇ n tö n-1 Bé nhí ®Æ c ®iÓ m cña danh s¸ ch tuyÕ n tÝ nh: - KÝ ch th­íc cña danh s¸ ch sÏ ®­îc cÊ p ph¸ t theo khai b¸ o. - C¸ c phÇ n tö cña danh s¸ ch n» m liª n tôc nhau trong bé nhí, gi÷a c¸ c phÇ n tö nµ y kh«ng cã kho¶ ng trèng. - Tiª u biÓ u cho danh s¸ ch ®Æ c lµ d∙ y (array). §Ó cµ i ®Æ t danh s¸ ch tuyÕ n tÝ nh, ta dïng m¶ ng 1 chiÒ u. ! Khai b¸o: Ta khai b¸ o cÊ u tróc list lµ mét mÈ u tin (struct) cã 2 field: - n : cho biÕ t sè phÇ n tö hiÖ n cã trong danh s¸ ch. NÕ u n ==0 th× cã nghÜ a lµ danh s¸ ch rçng. - danhsach : lµ m¶ ng 1 chiÒ u, mçi phÇ n tö cña m¶ ng lµ 1 phÇ n tö trong danh s¸ ch. #define MAXLIST 100 typedef struct list { int n; // sè nót cña danh s¸ ch int danhsach[MAXLIST]; // danh s¸ ch lµ m∙ ng 1 chiÒ u 39
  41. }; struct list ds; // biÕ n ds thuéc kiÓ u struct list VÝ dô: Khai b¸ o 1 danh s¸ ch hä tª n häc viª n cña 1 líp häc, cã tèi ®a 50 häc viª n. #define MAXLIST 50 typedef struct list { int n; char dshv[MAXLIST][30]; // hä tª n häc viª n cã tèi ®a 30 ký tù }; struct list ds; II. C¸c phÐp to¸n trªn danh s¸ch tuyÕn tÝ nh: §Ó ®¬n gi¶ n, c¸ c phÐ p to¸ n sau ®© y sÏ ®­îc thao t¸ c trª n danh s¸ ch c¸ c sè nguyª n víi khai b¸ o nh­ sau: #define MAXLIST 100 typedef struct list { int n; // sè nót cña danh s¸ ch int nodes[MAXLIST]; // danh s¸ ch lµ m∙ ng 1 chiÒ u }; struct list ds; // biÕ n ds thuéc kiÓ u struct list 1. PhÐ p to¸n Empty: kiÓ m tra xem danh s¸ ch cã rçng hay kh«ng? int Empty(struct list plist) { return (plist.n==0 ? TRUE : FALSE); } 2. PhÐ p to¸n Full: kiÓ m tra xem danh s¸ ch ®∙ ®Çy ch­a? int Full(struct list plist) { return (plist.n==MAXLIST ? TRUE : FALSE); } 3. PhÐp thªm vµo : Thª m mét phÇ n tö cã néi dung lµ info vµ o vÞ trÝ thø i cña danh s¸ ch. NÕ u i ==0 : thª m phÇ n tö vµ o ®Ç u danh s¸ ch NÕ u i ==ds.n+1 : thª m phÇ n tö vµ o cuèi danh s¸ ch. 40
  42. L­u ý: Khi thª m mét phÇ n tö vµ o danh s¸ ch, ta ph¶ i kiÓ m tra xem danh s¸ ch ®∙ ®Ç y hay ch­a? void Insert_item(struct list &plist, int i, int info) { int j; if(i plist.n+1) printf("Vi tri chen khong phu hop."); else if(Full(plist)) printf("Danh sach bi day."); else { if (i==0) i=1; for(j = plist.n -1; j >= i-1; j ) plist.nodes[j+1] = plist.nodes[j]; plist.nodes[i-1] = info; plist.n ++; } } 4. PhÐ p lo¹ i bá : Lo¹ i bá phÇ n tö thø i khái danh s¸ ch tuyÕ n tÝ nh. Khi lo¹ i bá 1 phÇ n tö th× danh s¸ ch ph¶ i cã Ý t nhÊ t mét phÇ n tö. void Delete_item (struct list &plist, int i) { int j; int temp; if(i plist.n) printf("Vi tri xoa khong phu hop."); else if(Empty(plist)) printf("Danh sach khong co phan tu."); else { for(j = i; j< plist.n ; j++) plist.nodes[j-1] = plist.nodes[j]; plist.n ; } } * Muèn lo¹ i bá tÊ t c¶ c¸ c phÇ n tö trong danh s¸ ch, ta chØ cÇ n cho ds.n=0 41
  43. 5. DuyÖ t danh s¸ch: duyÖ t tõ ®Ç u cho ®Õ n cuèi danh s¸ ch, mçi phÇ n tö ®­îc duyÖ t qua 1 lÇ n. Gi¶ sö ta duyÖ t danh s¸ ch ®Ó in gi¸ trÞ c¸ c phÇ n tö. void Traverse(struct list plist) { int i; if(plist.n == 0) { printf("\n Danh sach khong co phan tu"); return; } for(i = 0; i < plist.n; i++) printf("%7d", plist.nodes[i]); } 6. T× m kiÕ m: t× m vÞ trÝ ®Ç u tiª n cña phÇ n tö cã gi¸ trÞ x trong danh s¸ ch plist. NÕ u kh«ng cã x trong plist th× hµ m Search_info sÏ tr¶ vÒ gi¸ trÞ -1. int Search_info(struct list plist, int info) { int vitri = 0; while( vitri < plist.n && plist.nodes[vitri] != info ) vitri++; return(vitri==plist.n ? -1 : vitri+1); } L­u ý: §Ó nhË p danh s¸ ch, ta cã thÓ dïng gi¶ i thuË t sau: void Create_list(struct list &plist) { int i; printf("\nSo phan tu cua danh sach :"); scanf("%d", &plist.n); for (i=0; i< plist.n; i++) { printf("List[%d] =", i+1); scanf("%d",&plist.nodes[i]); } } NhËn xÐ t : Danh s¸ ch ®Æ c dïng ph­¬ng ph¸ p truy xuÊ t trùc tiÕ p nª n thêi gian truy xuÊ t nhanh, nh­ng hiÖ u qu¶ sö dông bé nhí thÊ p. Danh s¸ ch ®Æ c kh«ng phï hîp víi phÐ p thª m vµ o vµ lo¹ i bá v× mçi lÇ n thª m vµ o vµ lo¹ i bá th× chóng ta ph¶ i ®æi chç nhiÒ u lÇ n. §Æc biÖ t tr­êng hîp xÊ u nhÊ t lµ khi thª m vµ o vµ lo¹ i bá ë ®Ç u danh s¸ ch 42
  44. KÕ t luËn : Danh s¸ ch ®Æ c kh«ng nª n sö dông cho c¸ c danh s¸ ch hay bÞ biÕ n ®éng. Cßn ®èi víi nh÷ng danh s¸ ch th­êng bÞ biÕ n ®éng th× ng­êi ta chän cÊu tróc lµ danh s¸ ch liª n kÕ t. VÝ dô: T¹ o mét menu cho phÐ p ta thùc hiÖ n c¸ c phÐ p to¸ n sau trª n danh s¸ ch c¸ c sè nguyª n: 1. T¹ o danh s¸ ch 2. LiÖ t kª danh s¸ ch trª n mµ n h× nh 3. Thª m mét phÇ n tö cã gi¸ trÞ info t¹ i vÞ trÝ thø i - NÕ u i ==0 : thª m phÇ n tö vµ o ®Ç u danh s¸ ch - NÕ u i ==ds.n+1 : thª m phÇ n tö vµ o cuèi danh s¸ ch. 4. Xãa phÇ n tö ®Ç u tiª n cã gi¸ trÞ info trong danh s¸ ch 5. Xãa toµ n bé danh s¸ ch. Tr­íc khi xãa hái l¹ i ng­êi sö dông cã muèn xãa hay kh«ng? NÕ u ng­êi sö dông ®ång ý "C" th× míi xãa. * Ch­¬ng tr× nh : #include #include #include #define MAXLIST 100 // so phan tu toi da trong danh sach #define TRUE 1 #define FALSE 0 typedef struct list { int n; int nodes[MAXLIST]; }; // Phep toan empty: kiem tra danh sach co bi rong khong int empty(struct list plist) { return(plist.n == 0 ? TRUE : FALSE); } // Phep toan full: kiem tra danh sach bi day khong int full(struct list plist) { return(plist.n == MAXLIST ? TRUE : FALSE); } // Tao danh sach 43
  45. void create_list(struct list &plist) { int i; printf("\nSo phan tu cua danh sach :"); scanf("%d", &plist.n); for (i=0; i n +1 : them vao cuoi danh sach void insert_item(struct list &plist, int i, int info) { int j; if(i plist.n+1) printf("Vi tri chen khong phu hop."); else if(full(plist)) printf("Danh sach bi day."); else { if (i==0) i=1; for(j = plist.n -1; j >= i-1; j ) plist.nodes[j+1] = plist.nodes[j]; plist.nodes[i-1] = info; plist.n ++; } } // Tac vu delete_item: xoa nut tai vi tri i trong danh sach void delete_item (struct list &plist, int i) { int j; int temp; if(i plist.n) printf("Vi tri xoa khong phu hop."); else if(empty(plist)) 44
  46. printf("Danh sach khong co phan tu."); else { for(j = i; j< plist.n ; j++) plist.nodes[j-1] = plist.nodes[j]; plist.n ; } } // Tac vu clearlist: xoa tat ca cac nut trong danh sach void clearlist(struct list &plist) { plist.n = 0; } // Tac vu traverse: duyet danh sach cac so nguyen void traverse(struct list plist) { int i; if(plist.n == 0) { printf("\n Danh sach khong co phan tu"); return; } for(i = 0; i < plist.n; i++) printf("%7d", plist.nodes[i]); } /* Phep toan search: tim kiem tuyen tinh, neu khong tim thay ham nay tra ve -1, neu tim thay ham nay tra ve vi tri tim thay */ int search_info(struct list plist, int info) { int vitri = 0; while( vitri < plist.n && plist.nodes[vitri] != info ) vitri++; return(vitri==plist.n ? -1 : vitri+1); } int menu() { int chucnang; clrscr(); 45
  47. // menu chinh cua chuong trinh printf("\n\n CHUONG TRINH QUAN LY DANH SACH CAC SO \n"); printf(" Cac chuc nang cua chuong trinh:\n"); printf(" 1: Nhap danh sach\n"); printf(" 2: Xem danh sach \n"); printf(" 3: Them mot so vao vi tri thu i\n"); printf(" 4: Xoa phan tu dau tien co tri info\n"); printf(" 5: Xoa toan bo danh sach\n"); printf(" 0: Ket thuc chuong trinh\n"); printf(" Chuc nang ban chon: "); do scanf("%d", &chucnang); while (chucnang 5); return chucnang; } void main() { struct list ds; int chucnang, vitri, info; char c; ds.n=0; do { clrscr(); chucnang=menu(); switch(chucnang) { case 1: { printf("\nNhap danh sach: "); create_list(ds); break; } case 2: { printf("\nDanh sach so: "); traverse(ds); 46
  48. getche(); break; } case 3: { printf("\nVi tri them (1, 2, ): "); scanf("%d", &vitri); printf("Gia tri: "); scanf("%d", &info); insert_item(ds, vitri, info); getche(); break; } case 4: { printf("\nGia tri so can xoa: "); scanf("%d", &info); vitri = search_info(ds, info); if(vitri == -1) printf("Khong co so %d trong danh sach", info); else delete_item(ds, vitri); getche(); break; } case 5: { printf("\nBan co chac muon xoa hay khong (c/k):"); c = toupper(getche()); if( c == 'C') clearlist(ds); break; } } } while(chucnang != 0); } 47
  49. III. stack (chång): III.1. Kh¸i niÖ m: Stack lµ mét danh s¸ ch mµ viÖ c thª m vµ o vµ lo¹ i bá chØ diÔ n ra cïng mét ®Ç u cña danh s¸ ch, tøc lµ theo c¬ chÕ LIFO (Last In First Out). Stack gåm nhiÒ u phÇ n tö cã cïng kiÓ u d÷ liÖ u, phÇ n tö trª n cïng Stack lu«n lu«n cã mét con trá chØ tíi ta gäi lµ Stack Pointer (ký hiÖ u: sp). §Ó t¹ o Stack ta cã hai c¸ ch : danh s¸ ch tuyÕ n tÝ nh (m¶ ng) hoÆ c danh s¸ ch liª n kÕ t (con trá). Trong ch­¬ng nµ y, ta chØ quan t© m ®Õ n viÖ c t¹ o Stack b» ng danh s¸ ch tuyÕ n tÝ nh. - Stack cã 2 phÐ p to¸ n chÝ nh : * Push : thª m mét phÇ n tö vµ o ®Ç u Stack * Pop : xãa mét phÇ n tö khái Stack, tr¶ cho ch­¬ng tr× nh gäi gi¸ trÞ cña phÇ n tö võa xãa. D­íi ®© y lµ h× nh minh häa cho c¸ c phÐ p to¸ n push, pop trª n Stack. sp 4 20 sp 3 5 3 5 2 10 2 10 1 15 1 15 0 20 push(20) 0 20 (a) (b) sp 5 1 sp 4 20 4 20 3 5 3 5 2 10 2 10 1 15 1 15 push(1)0 20 pop() 0 20 (c) (d) * L­u ý: Ta khai b¸ o biÕ n st cã kiÓ u cÊ u tróc stack nh­ sau: #define STACKSIZE 100 #define TRUE 1 #define FALSE 0 48
  50. struct stack { int sp; int nodes[STACKSIZE]; } st; III.2. C¸c phÐ p to¸n trª n stack: a. PhÐ p to¸n push : thª m mét phÇ n tö cã gi¸ trÞ x vµ o ®Ç u stack void push (struct stack &st, int x) { if(st.sp == STACKSIZE-1) { printf("%s", "stack bi day"); exit(1); } else st.nodes[++(st.sp)] = x; } b. PhÐ p to¸n pop : lo¹ i bá phÇ n tö khái Stack vµ tr¶ vÒ gi¸ trÞ cña phÇ n tö võa xãa; tr­íc khi xãa, ta ph¶ i kiÓ m tra Stack cã kh¸ c rçng hay kh«ng. int pop(struct stack &st) { if(empty(st)) { printf("%s", "stack bi rong"); exit(1); } return(st.nodes[(st.sp) ]); } øng dông cña Stack: - Stack th­êng ®­îc dïng trong c¸ c bµ i to¸ n cã c¬ chÕ LIFO (vµ o sau ra tr­íc) - Stack còng ®­îc dïng trong c¸ c bµ i to¸ n gì ®Ö qui (chuyÓ n mét gi¶ i thuË t ®Ö qui thµ nh gi¶ i thuË t kh«ng ®Ö qui) III.3. VÝ dô: a. ViÕ t ch­¬ng tr× nh ®æi sè nguyª n kh«ng © m ë hÖ thË p ph© n sang sè ë hÖ nhÞ ph© n. 49
  51. #include #include #include #define STACKSIZE 100 #define TRUE 1 #define FALSE 0 struct stack { int sp; int nodes[STACKSIZE]; }; int empty(struct stack st) { if(st.sp == -1) return(TRUE); else return(FALSE); } void push(struct stack &st, int x) { if(st.sp == STACKSIZE-1) { printf("%s", "stack bi day"); exit(1); } else st.nodes[++(st.sp)] = x; } int pop(struct stack &st) { if(empty(st)) { printf("%s", "stack bi rong"); exit(1); } return(st.nodes[(st.sp) ]); } 50
  52. void main() { struct stack st; int sodu; long int so; char c; clrscr(); do { st.sp =- 1; // khoi dong stack printf("\n\nNhap vao mot so thap phan: "); scanf("%lD", &so); do { sodu = so % 2; push(st, sodu); // push so du vao stack so = so / 2; } while (so != 0); printf("So da doi la: "); while(!empty(st)) printf("%d", pop(st)); // pop so du ra khoi stack printf("\n\nBan co muon tiep tuc khong? (c/k): "); c = getche(); } while(c == 'c' || c == 'C'); } b. ViÕ t ch­¬ng tr× nh tÝ nh trÞ mét biÓ u thøc d¹ ng hË u tè (PostFix), biÕ t r» ng mçi sè h¹ ng lµ 1 ký sè vµ c¸ c to¸ n tö trong biÓ u thøc gåm cã: céng(+), trõ (-), nh© n (*), chia (/), lòy thõa (^). D¹ ng hË u tè cña biÓ u thøc cã d¹ ng nh­ sau: 82- = 6 84-21+^ = 64 23+3^ = 125 #include #include #include #include #define TOIDA 80 51
  53. #define TRUE 1 #define FALSE 0 // Khai bao stack chua cac toan hang struct stack { int sp; double nodes[TOIDA]; } st; int empty(struct stack st) { if (st.sp == -1) return(TRUE); else return(FALSE); } void push(struct stack &st, double x) { if(st.sp == TOIDA-1) { printf("%s", "stack bi day"); exit(1); } else st.nodes[++(st.sp)] = x; } double pop(struct stack &st) { if(empty(st)) { printf("%s", "Bieu thuc sai nen khong the tinh"); getch(); exit(1); } else return(st.nodes[st.sp ]); } /* Ham tinh: tÝ nh trÞ cña hai to¸ n h¹ ng toanhang1 va toanhang2 qua phÐ p to¸ n toantu */ 52
  54. double tinh(int toantu, double toanhang1, double toanhang2) { switch(toantu) { case '+': return(toanhang1 + toanhang2); break; case '-': return(toanhang1 - toanhang2); break; case '*': return(toanhang1 * toanhang2); break; case '/': return(toanhang1 / toanhang2); break; case '^': return(pow(toanhang1, toanhang2)); break; default: printf("%s", "toan tu khong hop le"); exit(1); } } // Hµ m dinhtri: tÝ nh mét biÓ u thøc postfix double dinhtri(char bieuthuc[]) { int c, i; double toanhang1, toanhang2, tri; st.sp = -1; // khoi dong stack for(i = 0; (c = bieuthuc[i]) != '\0'; i++) if(c>='0' && c<='9') // c la toan hang push(st, (double)(c-'0')); else // c la toan tu { toanhang2 = pop(st); toanhang1 = pop(st); tri = tinh(c, toanhang1, toanhang2); // tinh ket qua trung gian push(st, tri); } return(pop(st)); } 53
  55. void main() { char c, bieuthuc[TOIDA]; clrscr(); do { printf("\n\nNhap bieu thuc postfix can dinh tri: "); gets(bieuthuc); double ketqua = dinhtri(bieuthuc) ; if (empty(st)) printf("Bieu thuc %s co tri la %5.2f", bieuthuc, ketqua); else printf("Bieu thuc sai nen khong the tinh"); printf("\n\nTiep tuc khong ? (c/k): "); c = getche(); } while(c == 'c' || c == 'C'); } IV. QUEUE (hµng ®îi): IV.1. Kh¸i niÖ m: Queue lµ mét danh s¸ ch h¹ n chÕ mµ viÖ c thª m vµ o ®­îc thùc hiÖn ë ®Çu danh s¸ ch, vµ viÖ c lo¹ i bá ®­îc thùc hiÖ n ë ®Ç u cßn l¹ i (FIFO - First In First Out). Queue chøa c¸ c phÇ n tö cã cïng kiÓ u d÷ liÖ u. Queue còng cã thÓ ®­îc tæ chøc theo danh s¸ ch tuyÕ n tÝ nh hoÆ c danh s¸ ch liª n kÕ t. ë ®© y, ta chØ tæ chøc queue theo danh s¸ ch tuyÕ n tÝ nh. - VÞ trÝ ®Ó lo¹ i bá phÇ n tö ®­îc gäi lµ Front - VÞ trÝ ®Ó thª m vµ o ®­îc gäi lµ Rear Queue cã hai phÐ p to¸ n chÝ nh: - Insert_queue : thª m mét phÇ n tö vµ o hµ ng ®îi; khi thª m ta ph¶ i l­u ý xem hµ ng ®îi bÞ trµ n hay bÞ ®Ç y ®Ó xö lý cho thÝ ch hîp. + Hµ ng ®îi bÞ trµ n : lµ tr­êng hîp khi Rear = QUEUESIZE-1 (=n) vµ Front > 0, tøc lµ kh«ng thÓ thª m phÇ n tö míi vµ o cuèi hµ ng. §Ó kh¾ c phôc tr­êng hîp nµ y, ta cã thÓ dïng mét trong 2 c¸ ch: " Di chuyÓ n tÞ nh tiÕ n tõng phÇ n tö lª n ®Ó cã Front = 0 vµ Rear < QUEUESIZE-1 (tr­êng hîp nµ y Front lu«n nhá h¬n Rear) " Di chuyÓ n vßng : cho Rear = 0, Front gi÷ nguyª n (tr­êng hîp nµ y Front cã lóc nhá h¬n, cã lóc lín h¬n Rear ) 54
  56. Front Rear 0 A 1 B Di chuyÓn 2 Rear C vßng 3 Front Di chuyÓn Front A tÞnh tiÕn A Rear B B C n C Hµng ®îi bÞ trµn Rear ≥ Front Rear >< Front + Hµ ng ®îi bÞ ®Ç y: hµ ng ®îi kh«ng cã phÇ n tö nµ o trèng: Front = 0 vµ Rear = n hoÆ c Rear ®øng ngay tr­íc Front; do ®ã nÕ u tiÕ p tôc thª m vµ o sÏ bÞ mÊ t d÷ liÖ u. Rear = QUEUESIZE-1 } Rear - Front + 1 = Rear ®øng ngay tr­íc Front: Front = -1 QUEUESIZE hoÆc Rear - Front + 1 = 0 Front 0 Rear Front Rear n Rear - Front + 1 = QUEUESIZE Rear - Front + 1 = 0 - Delete_queue: lo¹ i bá phÇ n tö khái Queue vµ tr¶ vÒ gi¸ trÞ cña phÇ n tö võa xãa; tr­íc khi xãa, ta ph¶ i kiÓ m tra Queue cã kh¸ c rçng hay kh«ng. - Khëi t¹ o hµ ng ®îi: Front := -1; Rear := -1; L­u ý: - PhÐ p to¸ n Insert_queue thùc hiÖ n ë cuèi hµ ng ®îi, cßn phÐ p to¸ n Delete_queue thùc hiÖ n ë ®Ç u hµ ng ®îi. Ta khai b¸ o biÕ n q cã kiÓ u cÊ u tróc Queue gåm 3 thµ nh phÇ n: - front, rear : sè nguyª n chØ ®Ç u vµ cuèi hµ ng ®îi - nodes: m¶ ng 1 chiÒ u, mçi phÇ n tö cña m¶ ng lµ 1 phÇ n tö trong queue. #define QUEUESIZE 100 #define TRUE 1 #define FALSE 0 struct queue 55
  57. { int front, rear; int nodes[QUEUESIZE]; } q; IV.2. C¸c phÐ p to¸n trª n hµng: §èi víi hµ ng ®îi, ta cã hai phÐ p to¸ n chñ yÕ u lµ thª m vµ o (Insert_queue) vµ lo¹ i bá (Delete_queue). a. PhÐp thªm vµo : thª m mét phÇ n tö x vµ o hµ ng ®îi; khi thª m ta ph¶ i l­u ý xem hµ ng ®îi bÞ trµ n hay bÞ ®Ç y ®Ó xö lý cho thÝ ch hîp. void Insert_queue(struct queue &q, int x) { if (q.rear - q.front + 1== 0 || q.rear -q.front+1== QUEUESIZE) { printf("\nHang bi day"); } else { if(q.front==-1) { q.front=0; q.rear =-1; } if (q.rear==QUEUESIZE-1) q.rear=-1; ++q.rear; q.nodes[q.rear]=x; } } b. PhÐ p lo¹i bá : lo¹ i bá phÇ n tö khái Queue vµ tr¶ vÒ gi¸ trÞ cña phÇ n tö võa xãa; tr­íc khi xãa, ta ph¶ i kiÓ m tra Queue cã kh¸ c rçng hay kh«ng. int Delete_queue(struct queue &q) { int x; if(empty(q)) printf("Hang doi rong"); else { x= q.nodes[q.front]; if(q.front == q.rear) // Hang chi co 1 phan tu { 56
  58. q.front = -1; q.rear = -1; } else { (q.front)++; if (q.front ==QUEUESIZE) q.front=0; } return x; } } * øng dông cña Queue: - Queue th­êng ®­îc dïng trong c¸ c bµ i to¸ n cã c¬ chÕ FIFO (vµ o tr­íc ra tr­íc). - Queue th­êng ®­îc dïng trong c¸ c c«ng viÖ c ®ang ®îi phôc vô trong c¸ c hÖ ®iÒ u hµ nh ®a nhiÖ m, ®Ó qu¶ n lý c¸ c hµ ng ®îi in trª n m¸ y in m¹ ng (print server) IV.3. VÝ dô: ViÕ t ch­¬ng tr× nh ®æi phÇ n thË p ph© n cña sè kh«ng © m ë hÖ thË p ph© n sang sè ë hÖ nhÞ ph© n, tèi ®a ta chØ lÊ y 8 sè lÏ trong hÖ nhÞ ph© n * Gi¶ i thuË t: #include #include #include #include #define QUEUESIZE 8 #define TRUE 1 #define FALSE 0 struct queue { int front, rear; int nodes[QUEUESIZE]; }; struct queue q; void Initialize(struct queue &q) { 57
  59. q.front = q.rear = -1; } int empty(struct queue q) { return((q.front == -1 || q.rear== -1) ? TRUE : FALSE); } void Insert_queue(struct queue &q, int x) { if (q.rear - q.front + 1== 0 || q.rear -q.front+1== QUEUESIZE) { printf("\nHang bi day"); } else { if(q.front==-1) { q.front=0; q.rear =-1; } if (q.rear==QUEUESIZE-1) q.rear=-1; ++q.rear; q.nodes[q.rear]=x; } } int Delete_queue(struct queue &q) { int x; if(empty(q)) printf("Hang doi rong"); else { x= q.nodes[q.front]; if(q.front == q.rear) // Hang chi co 1 phan tu { q.front = -1; q.rear = -1; } else { (q.front)++; 58
  60. if (q.front ==QUEUESIZE) q.front=0; } return x; } } void dec_bin2(double n) { double positive; double r, le; le = modf(n,&positive); // Hµ m modf t¸ ch sè double n ra thµ nh 2 phÇ n // phÇ n nguyª n chøa trong positive (double) vµ phÇ n thË p ph© n chøa // trong le (double) int i=0; do { r =le*2; le = modf(r,&positive); Insert_queue(q, positive); i++ ; } while (i <8 && r!=1); printf("\n So nhi phan cua phan le : 0."); while (!empty(q)) { printf("%d", Delete_queue(q)); } getch(); } // chuong trinh chinh void main(void) { int chucnang, so; float n; clrscr(); // khoi tao queue Initialize(q); printf("\nNhap phan thap phan cua so thuc :"); scanf("%e", &n); dec_bin2(n); } 59
  61. Bµi tËp 1. ViÕ t ch­¬ng tr× nh cho phÐ p : - NhË p mét v¨ n b¶ n cã tèi ®a 100 c© u, mçi c© u cã tèi ®a 80 ký tù, vµ mçi tõ trong c© u cã Ý t nhÊ t mét kho¶ ng tr¾ ng. Ta kÕ t thóc viÖ c nhË p b» ng c© u rçng. - Xö lý c© u : + In ra mµ n h× nh c¸ c c© u bÊ t kú trong v¨ n b¶ n + Lo¹ i bá mét ®o¹ n gåm mét sè c© u nµ o ®ã trong v¨ n b¶ n + Xen vµ o mét ®o¹ n míi t¹ i mét vÞ trÝ bÊ t kú trong v¨ n b¶ n - Xö lý tõ : + Cho biÕ t sè lÇ n xuÊ t hiÖ n cña mét tõ trong v¨ n b¶ n + Thay thÕ mét tõ b» ng mét tõ kh¸ c. 2. T¹ o menu thùc hiÖ n c¸ c c«ng viÖ c sau: a. NhË p danh s¸ ch häc viª n, mçi häc viª n gåm : maso (sè nguyª n), ho (chuçi), ten (chuçi). Danh s¸ ch häc viª n ®­îc l­u tr÷ trong 1 danh s¸ ch tuyÕ n tÝ nh cã tèi ®a 100 phÇ n tö. b. LiÖ t kª danh s¸ ch trª n mµ n h× nh c. S¾ p xÕ p l¹ i danh s¸ ch theo thø tù t¨ ng dÇ n cña tª n, trïng tª n th× s¾ p qua hä. d. Thª m mét häc viª n vµ o danh s¸ ch sao cho sau khi thª m th× vÉ n ®¶ m b¶ o tÝ nh thø tù cña danh s¸ ch. e. In ra mµ n h× nh th«ng tin cña häc viª n cã m∙ sè do ta nhË p f. Xãa häc viª n cã m∙ sè do ta nhË p g. Save danh s¸ ch häc viª n vµ o file DSHV.TXT. h. Load danh s¸ ch häc viª n tõ file DSHV.TXT vµ o danh s¸ ch tuyÕ n tÝ nh. 3. T¹ o menu thùc hiÖ n c¸ c c«ng viÖ c sau: a. §æi sè thùc d­¬ng ë hÖ thË p ph© n sang hÖ nhÞ ph© n b. §æi sè thùc d­¬ng ë hÖ thË p ph© n sang hÖ thË p lôc c. §æi sè nhÞ ph© n sang sè thË p ph© n d. §æi sè thË p lôc sang sè thË p ph© n 4. H∙ y ®Õ m cã bao nhiª u bit 1 trong 1000 tõ, mçi tõ 4 byte 60
  62. CH¦¥NG IV DANH S¸CH LI£N KÕT (LINKED LIST) I. Kh¸i niÖm: CÊ u tróc danh s¸ ch liª n kÕ t lµ cÊ u tróc ®éng, viÖ c cÊ p ph¸ t nót vµ gi¶ i phãng nót trª n danh s¸ ch x¶ y ra khi ch­¬ng tr× nh ®ang ch¹ y. Ta th­êng cÊ p ph¸ t nót cho danh s¸ ch liª n kÕ t b» ng biÕ n ®éng. Danh s¸ ch liª n kÕ t cã nhiÒ u lo¹ i nh­ danh s¸ ch liª n kÕ t ®¬n, danh s¸ ch liª n kÕ t kÐ p, danh s¸ ch liª n kÕ t ®a vµ danh s¸ ch liª n kÕ t vßng. Trong ch­¬ng nµ y ra sÏ kh¶ o s¸ t mét sè lo¹ i danh s¸ ch liª n kÕ t nh­ ®¬n, kÐ p vµ vßng. C¸ c phÇ n tö trong danh s¸ ch liª n kÕ t sÏ ®­îc cÊ p ph¸ t vïng nhí trong qu¸ tr× nh thùc thi ch­¬ng tr× nh, do ®ã chóng cã thÓ n» m r¶ i r¸ c ë nhiÒ u n¬i kh¸ c nhau trong bé nhí (kh«ng liª n tôc). 3 . Firs 1 2 3 • 4 • First 1 . Null 2 . 4 . Nul H× nh 4.1 Minh häa danh s¸ch liª n kÕ t trong bé nhí C¸ c phÇ n tö trong danh s¸ ch ®­îc kÕ t nèi víi nhau theo chïm liª n kÕ t nh­ h× nh trª n: - First lµ con trá chØ ®Õ n phÇ n tö ®Ç u cña danh s¸ ch liª n kÕ t - PhÇ n tö cuèi cña danh s¸ ch liª n kÕ t víi vïng liª n kÕ t cã gi¸ trÞ NULL - Mçi nót cña danh s¸ ch cã tr­êng info chøa néi dung cña nót vµ tr­êng next lµ con trá chØ ®Õ n nót kÕ tiÕ p trong danh s¸ ch. * L­u ý : - CÊ u tróc danh s¸ ch liª n kÕ t lµ cÊ u tróc ®éng, c¸ c nót ®­îc cÊ p ph¸ t hoÆ c bÞ gi¶ i phãng khi ch­¬ng tr× nh ®ang ch¹ y. 61
  63. - Danh s¸ ch liª n kÕ t rÊ t thÝ ch hîp khi thùc hiÖ n c¸ c phÐ p to¸ n trª n danh s¸ ch th­êng bÞ biÕ n ®éng. Trong tr­êng hîp xãa hay thª m phÇ n tö trong danh s¸ ch liª n kÕ t th× ta kh«ng dêi c¸ c phÇ n tö ®i nh­ trong danh s¸ ch tuyÕ n tÝ nh (m¶ ng) mµ chØ viÖ c hiÖ u chØ nh l¹ i tr­êng next t¹ i c¸ c nót ®ang thao t¸ c. Thêi gian thùc hiÖ n c¸ c phÐ p to¸ n thª m vµ o vµ lo¹ i bá kh«ng phô thuéc vµ o sè phÇ n tö cña danh s¸ ch liª n kÕ t. - Tuy nhiª n, danh s¸ ch liª n kÕ t còng cã c¸ c ®iÓ m h¹ n chÕ sau: + V× mçi nót cña danh s¸ ch liª n kÕ t ph¶ i chøa thª m tr­êng next nª n danh s¸ ch liª n kÕ t ph¶ i tèn thª m bé nhí. + T× m kiÕ m trª n danh s¸ ch liª n kÕ t kh«ng nhanh v× ta chØ ®­îc truy xuÊ t tuÇ n tù tõ ®Ç u danh s¸ ch. # Khai b¸ o : Mét phÇ n tö cña danh s¸ ch liª n kÕ t Ý t nhÊ t ph¶ i cã hai thµ nh phÇ n : néi dung cña phÇ n tö (info) vµ thµ nh phÇ n next ®Ó liª n kÕ t phÇ n tö nµ y víi phÇ n tö kh¸ c. Gi¶ sö ta khai b¸ o kiÓ u NODEPTR lµ kiÓ u con trá chØ ®Õ n nót trong 1 danh s¸ ch liª n kÕ t, mçi phÇ n tö cã 2 thµ nh phÇ n : info (sè nguyª n) vµ next. struct node { int info ; struct node *next ; }; typedef struct node *NODEPTR; - §Ó khai b¸ o biÕ n First qu¶ n lý danh s¸ ch liª n kÕ t ta viÕ t nh­ sau: NODEPTR First; - Khëi t¹ o danh s¸ ch liª n kÕ t : First = NULL; - Ghi chó : $ Thµ nh phÇ n chøa néi dung cã thÓ gåm nhiÒ u vïng víi c¸ c kiÓ u d÷ liÖ u kh¸ c nhau. VÝ dô: Khai b¸ o biÕ n First ®Ó qu¶ n lý mét danh s¸ ch sinh viª n víi cÊ u tróc d÷ liÖ u lµ danh s¸ ch liª n kÕ t ®¬n, mçi sinh viª n gåm cã 2 thµ nh phÇ n lµ : mssv (sè nguyª n) vµ hä tª n. struct sinhvien int mssv; char hoten[30]; }; struct node { sinhvien sv ; 62
  64. struct node *next ; }; typedef struct node *NODEPTR; NODEPTR First; $ Thµ nh phÇ n liª n kÕ t còng cã thÓ nhiÒ u h¬n mét nÕ u lµ danh s¸ ch ®a liª n kÕ t hoÆ c danh s¸ ch liª n kÕ t kÐ p. $ First lµ con trá trá ®Õ n phÇ n tö ®Ç u tiª n cña danh s¸ ch liª n kÕ t, nã cã thÓ lµ kiÓ u con trá (nh­ khai b¸ o trª n), vµ còng cã thÓ lµ mét struct cã hai thµ nh phÇ n: First trá ®Õ n phÇ n tö ®Ç u tiª n cña danh s¸ ch liª n kÕ t, vµ Last trá ®Õ n phÇ n tö cuèi cña danh s¸ ch liª n kÕ t. struct Linked_List; { First NODEPTR; Last NODEPTR; }; II. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt: §Ó ®¬n gi¶ n, c¸ c phÐ p to¸ n sau ®© y sÏ ®­îc thao t¸ c trª n danh s¸ ch c¸ c sè nguyª n víi khai b¸ o nh­ sau: struct node { int info ; struct node *next ; }; typedef struct node *NODEPTR; - §Ó khai b¸ o biÕ n First qu¶ n lý danh s¸ ch liª n kÕ t ta viÕ t nh­ sau: NODEPTR First; II.1. T¹o danh s¸ch: a. Khëi t¹o danh s¸ch (Initialize): dïng ®Ó khëi ®éng mét danh s¸ ch liª n kÕ t, cho ch­¬ng tr× nh hiÓ u lµ hiÖ n t¹ i danh s¸ ch liª n kÕ t ch­a cã phÇ n tö. void Initialize(NODEPTR &First) { First = NULL; } b. CÊp ph¸t vïng nhí (New_Node): cÊ p ph¸ t mét nót cho danh s¸ ch liª n kÕ t. Hµ m New_Node nµ y tr¶ vÒ ®Þ a chØ cña nót võa cÊ p ph¸ t. Trong ch­¬ng tr× nh cã sö dông hµ m malloc (trong ), hµ m nµ y cÊ p ph¸ t mét khèi nhí tÝ nh theo byte tõ bé nhí heap. NÕ u cÊ p ph¸ t thµ nh c«ng, hµ m malloc tr¶ vÒ ®Þ a chØ cña vïng nhí võa cÊ p ph¸ t, ng­îc l¹ i nã sÏ tr¶ vÒ NULL. 63
  65. NODEPTR New_node(void) { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return (p); } c. Thª m vµo ®Çu danh s¸ch (Insert_first): thª m mét nót cã néi dung x vµ o ®Ç u danh s¸ ch liª n kÕ t. First •• NULL x H× nh 4.2 Thª m nót cã néi dung x vµo ®Çu danh s¸ch liª n kÕ t void Insert_first(NODEPTR &First, int x) { NODEPTR p; p = New_node(); p->info = x; p->next = First; First = p; } d. Thª m nót míi vµo sau nót cã ®Þ a chØ p (Insert_after): thª m mét nót cã néi dung x vµ o sau nót cã ®Þ a chØ p trong danh s¸ ch liª n kÕ t First. p First •• NULL x q H× nh 4.3 Thª m nót cã néi dung x vµo sau nót cã ®Þ a chØ p void Insert_after(NODEPTR p, int x) { NODEPTR q; 64
  66. if(p == NULL) printf("khong them phan tu vao danh sach duoc"); else { q = New_node(); q->info = x; q->next = p->next; p->next = q; } } II.2. T× m kiÕ m (Search_info): T× m nót ®Ç u tiª n trong danh s¸ ch cã info b» ng víi x. Do ®© y lµ danh s¸ ch liª n kÕ t nª n ta ph¶ i t× m tõ ®Ç u danh s¸ ch. Hµ m Search_info nÕ u t× m thÊ y x trong danh s¸ ch th× tr¶ vÒ ®Þ a chØ cña nót cã trÞ b» ng x trong danh s¸ ch, nÕ u kh«ng cã th× tr¶ vÒ trÞ NULL. NODEPTR Search_info(NODEPTR First, int x) { NODEPTR p; p = First; while(p != NULL && p->info != x ) p = p->next; return(p); } II.3. CËp nhËt danh s¸ch: a. Gi¶i phãng vïng nhí (free): Hµ m nµ y dïng ®Ó hñy nót ®∙ cÊ p ph¸ t, vµ tr¶ vïng nhí vÒ l¹ i cho memory heap. free( p) ; víi p lµ biÕ n con trá b. KiÓ m tra danh s¸ch liª n kÕ t rçng hay kh«ng (Empty): hµ m Empty tr¶ vÒ TRUE nÕ u danh s¸ ch liª n kÕ t rçng, vµ ng­îc l¹ i. int Empty(NODEPTR First) { return(First == NULL ? TRUE : FALSE); } c. Xãa phÇn tö ®Çu cña danh s¸ch (Delete_First): muèn xãa 1 phÇ n tö khái danh s¸ ch liª n kÕ t th× ta ph¶ i kiÓ m tra xem danh s¸ ch cã rçng hay kh«ng. NÕ u danh s¸ ch cã phÇ n tö th× míi xãa ®­îc. 65
  67. p First •• NULL H× nh 4.4 Xãa nót ®Çu tiª n trong danh s¸ch liª n kÕ t void Delete_First (NODEPTR &First) { NODEPTR p; if (Empty(First)) printf("Danh sach rong nen khong the xoa"); else { p = First; // nut can xoa la nut dau First = p->next; free(p); } } d. Xãa phÇn tö ®øng sau nót cã ®Þ a chØ p (Delete_after): First •• p q NULL H× nh 4.5 Xãa nót sau nót cã ®Þ a chØ p void Delete_after(NODEPTR p) { NODEPTR q; // nÕ u p lµ NULL hoÆ c sau p kh«ng cã nót if((p == NULL) || (p->next == NULL)) printf("Khong xoa duoc"); else { q = p->next; // q chi nut can xoa p->next = q->next; free(q); } } e. Xãa phÇn tö theo néi dung (Delete_info): - T× m ®Þ a chØ cña phÇ n tö cã néi dung lµ x trong danh s¸ ch liª n kÕ t. - Lo¹ i bá phÇ n tö nµ y theo ®Þ a chØ . 66
  68. void Delete_info(NODEPTR &First,int x) { NODEPTR q,p; p= search_info(First,x); if (p==NULL) printf("Khong co gia tri %d trong danh sach", x); else { if (p==First) Delete_first(First); else { q=First; while (q->next != p) q=q->next; Delete_after(q); } printf("Da xoa phan tu co gia tri %d trong danh sach",x); } } L­u ý : Gi¶ i thuË t nµ y chØ lo¹ i bá phÇ n tö ®Ç u tiª n trong danh s¸ ch cã gi¸ trÞ info = x. f. Xãa toµn bé danh s¸ch (Clearlist): ta cã thÓ sö dông lÖ nh First = NULL ®Ó xãa toµ n bé danh s¸ ch, nh­ng trong bé nhí, c¸ c vïng nhí ®∙ cÊ p ph¸ t cho c¸ c nót kh«ng gi¶ i phãng vÒ l¹ i cho memory heap, nª n sÏ l∙ ng phÝ vïng nhí. Do ®ã, ta sö dông gi¶ i thuË t sau: void Clearlist(NODEPTR &First) { NODEPTR p; while(First != NULL) { p = First; First = First->next; free(p); } } II.4. DuyÖ t danh s¸ch: Th«ng th­êng ta hay duyÖ t danh s¸ ch liª n kÕ t ®Ó thùc hiÖ n mét c«ng viÖ c g× ®ã, nh­ liÖ t kª d÷ liÖ u trong danh s¸ ch hay ®Õ m sè nót trong danh s¸ ch 67
  69. void Traverse(NODEPTR First) { NODEPTR p; int stt = 0; p = First; if(p == NULL) printf("\n (Khong co phan tu trong danh sach)"); while(p != NULL) { printf("\n %5d%8d", stt++, p->info); p = p->next; } } II.5. S¾p xÕ p (Selection_Sort): s¾ p xÕ p danh s¸ ch liª n kÕ t theo thø tù info t¨ ng dÇ n. - Néi dung: Ta so s¸ nh tÊ t c¶ c¸ c phÇ n tö cña danh s¸ ch ®Ó chän ra mét phÇ n tö nhá nhÊ t ®­a vÒ ®Ç u danh s¸ ch; sau ®ã, tiÕ p tôc chän phÇ n tö nhá nhÊ t trong c¸ c phÇ n tö cßn l¹ i ®Ó ®­a vÒ phÇ n tö thø hai trong danh s¸ ch. Qu¸ tr× nh nµ y lÆ p l¹ i cho ®Õ n khi chän ra ®­îc phÇ n tö nhá thø (n-1). - Gi¶ i thuË t: void Selection_Sort(NODEPTR &First) { NODEPTR p, q, pmin; int min; for(p = First; p->next != NULL; p = p->next) { min = p->info; pmin = p; for(q = p->next; q != NULL; q = q->next) if(min > q->info) { min = q->info; pmin = q; } // hoan doi truong info cua hai nut p va pmin pmin->info = p->info; p->info = min; } } 68
  70. III. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt cã thø tù: Danh s¸ ch liª n kÕ t cã thø tù lµ mét danh s¸ ch liª n kÕ t ®∙ ® ­îc s¾ p xÕ p theo mét thø tù nhÊ t ®Þ nh (t¨ ng hay gi¶ m) trª n mét thµ nh phÇ n nµ o ®ã cña néi dung. ë ®© y, ta gi¶ sö danh s¸ ch liª n kÕ t First cã thø tù t¨ ng theo thµ nh phÇ n info. III.1. PhÐ p thª m vµo : Thª m vµ o danh s¸ ch liª n kÕ t cã thø tù mét phÇ n tö cã néi dung lµ x sao cho sau khi thª m vµ o vÉ n ®¶ m b¶ o tÝ nh cã thø tù cña danh s¸ ch. First •• t s NULL x p H× nh 4.6 Thª m nót cã néi dung x vµo danh s¸ch liª n kÕ t cã thø tù * Gi¶ i thuË t: - T¹ o phÇ n tö míi, g¸ n gi¸ trÞ x cho nã New_node (p) ; p->info = x ; - T× m vÞ trÝ thÝ ch hîp ®Ó ®­a phÇ n tö míi vµ o, nghÜ a lµ t× m hai vÞ trÝ t vµ s sao cho: t^.info info next); - G¸ n liª n kÕ t thÝ ch hîp sao cho p n» m gi÷a hai phÇ n tö cã ®Þ a chØ t vµ s: if(s == First) // them nut vao dau danh sach lien ket { p->next = First; First = p; } else // them nut p vao truoc nut s { p->next= s; t->next= p; } 69
  71. * Ch­¬ng tr× nh: void Insert_Order(NODEPTR &First, int x) { NODEPTR p, t, s; // q la nut truoc, p la nut sau p=New_node(); p->info=x; for(s = First; s != NULL && s->info next); if(s == First) // them nut vao dau danh sach lien ket { p->next = First; First = p; } else // them nut p vao truoc nut s { p->next= s; t->next= p; } } III.2. PhÐ p trén : Cho hai danh s¸ ch liª n kÕ t First1, First2 ®∙ cã thø tù. H∙ y trén hai danh s¸ ch nµ y l¹ i thµ nh mét danh s¸ ch liª n kÕ t míi First3 sao cho nã còng cã thø tù. First1 1 3 7 9 10 • NULL First2 285 NULL H× nh 4.7 Trén hai danh s¸ch liª n kÕ t cã thø tù a. Gi¶i thuËt: Gäi p1, p2, p3 lµ 3 biÕ n con trá ®Ó duyÖ t 3 danh s¸ ch First1, First2, First3 - T¹ o gi¶ nót ®Ç u tiª n trong danh s¸ ch liª n kÕ t First3 ®Ó h× nh thµ nh mét phÇ n tö cho p3 chØ ®Õ n. - DuyÖ t First1 vµ First2: NÕ u p1->info info : 70
  72. §­a phÇ n tö p1 vµ o sau phÇ n tö p3 Cho p1 chØ ®Õ n phÇ n tö kÕ trong danh s¸ ch First1 NÕ u p2->info info : §­a phÇ n tö p2 vµ o sau phÇ n tö p3 Cho p2 chØ ®Õ n phÇ n tö kÕ trong danh s¸ ch First2 Qu¸ tr× nh duyÖ t sÏ dõng l¹ i khi 1 trong 2 danh s¸ ch ®∙ duyÖ t xong - §­a nèt phÇ n cßn l¹ i cña danh s¸ ch ch­a duyÖ t xong vµ o danh s¸ ch liª n kÕ t First3. - Xãa phÇ n tö gi¶ ®Ç u danh s¸ ch First3 ®∙ t¹ o ë trª n. NODEPTR Merge(NODEPTR First1, NODEPTR First2) { NODEPTR p1, p2, p3; First3=New_node(); p1=First1; p2 = First2; p3=First3; while (p1 !=NULL && p2 !=NULL) if (p1->info info) { p3->next = p1; p3=p1; p1=p1->next ; } else { p3->next = p2; p3=p2; p2=p2->next ; } if (p1==NULL) p3->next=p2; else p3->next=p1; p3 = First3; First3=p3->next; free(p3); return First3; } VÝ dô: ViÕ t ch­¬ng tr× nh t¹ o mét menu ®Ó qu¶ n lý danh s¸ ch sinh viª n gåm c¸ c c«ng viÖ c sau: 71
  73. 1. T¹ o danh s¸ ch sinh viª n: Qu¸ tr× nh nhË p danh s¸ ch sÏ dõng l¹ i khi ta nhË p m∙ sè lµ 0. 2. Thª m sinh viª n vµ o danh s¸ ch: Thª m 1 sinh viª n vµ o danh s¸ ch, vÞ trÝ sinh viª n thª m vµ o do ta chän 3. Xem danh s¸ ch sinh viª n: LiÖ t kª danh s¸ ch sinh viª n trª n mµ n h× nh 4. HiÖ u chØ nh sinh viª n: nhË p vµ o vÞ trÝ sinh viª n cÇ n hiÖ u chØ nh, sau ®ã ch­¬ng tr× nh cho phÐ p ta hiÖ u chØ nh l¹ i m∙ sè, hä, tª n cña sinh viª n. 5. Xãa sinh viª n trong danh s¸ ch: xãa sinh viª n theo vÞ trÝ . 6. T× m kiÕ m sinh viª n theo m∙ sè: nhË p vµ o m∙ sè sinh viª n, sau ®ã in ra vÞ trÝ cña sinh viª n trong danh s¸ ch. 7. S¾ p xÕ p danh s¸ ch sinh viª n theo m∙ sè t¨ ng dÇ n 8. Thª m sinh viª n vµ o danh s¸ ch ®∙ cã thø tù t¨ ng dÇ n theo m∙ sè sao cho sau khi thª m th× danh s¸ ch vÉ n cßn t¨ ng dÇ n theo m∙ sè. 9. Xãa toµ n bé danh s¸ ch sinh viª n. BiÕ t r» ng: - Mçi sinh viª n gåm c¸ c th«ng tin: m∙ sè (int), hä, tª n - D¸ nh s¸ ch sinh viª n ®­îc tæ chøc theo danh s¸ ch liª n kÕ t ®¬n. Ch­¬ng tr× nh: #include #include #include #include #include #define TRUE 1 #define FALSE 0 struct sinhvien { int mssv; char ho[30]; char ten[10]; }; struct node { sinhvien sv; struct node *next; }; 72
  74. typedef node *NODEPTR; NODEPTR First; sinhvien sv; NODEPTR p; // Phep toan New_node: cap phat mot nut cho danh sach lien ket NODEPTR New_node(void) { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return(p); } /* Tac vu nodepointer: xac dinh con tro cua nut i trong danh sach lien ket (i = 2, ) */ NODEPTR nodepointer(NODEPTR First, int i) { NODEPTR p; int vitri=1; p = First; while(p != NULL && vitri next; vitri++; } return(p); } // Tac vu position: xac dinh vi tri cua nut p trong danh sach lien ket int position(NODEPTR First, NODEPTR p) { int vitri; NODEPTR q; q = First; vitri = 1; while(q != NULL && q != p) { q = q->next; vitri++; } 73
  75. if(q == NULL) return(-1); return(vitri); } // Phep toan initialize: khoi dong danh sach lien ket void initialize(NODEPTR &First) { First = NULL; } // Tac vu Empty: kiem tra danh sach lien ket co bi rong khong int Empty(NODEPTR First) { return(First == NULL ? TRUE : FALSE); } // Phep toan Insert_first: them nut moi vao dau danh sach lien ket void Insert_first(NODEPTR &First, sinhvien x) { NODEPTR p; p = New_node(); p->sv = x; p->next = First; First = p; } // Phep toan Insert_after: them nut moi sau nut co dia chi p void Insert_after(NODEPTR p, sinhvien x) { NODEPTR q; if(p == NULL) printf("khong them sinh vien vao danh sach duoc"); else { q = New_node(); q->sv = x; q->next = p->next; p->next = q; } } 74
  76. // Phep toan Delete_first: xoa nut o dau danh sach lien ket void Delete_first(NODEPTR &First) { NODEPTR p; if(Empty(First)) printf("Khong co sinh vien trong danh sach"); else { p = First; // nut can xoa la nut dau First = p->next; free(p); } } // Tac vu Delete_after: xoa nut sau nut p void Delete_after(NODEPTR p) { NODEPTR q; // neu p la NULL hoac p chi nut cuoi if((p == NULL) || (p->next == NULL)) printf("khong xoa sinh vien nay duoc"); else { q = p->next; // q chi nut can xoa p->next = q->next; free(q); } } /* Phep toan Insert_Order: Phep toan nay chi su dung khi them nut vao danh sach lien ket da co thu tu */ void Insert_Order(NODEPTR &First, sinhvien x) { NODEPTR p, q; // q la nut truoc, p la nut sau q = NULL; for(p = First; p != NULL && p->sv.mssv next) q = p; if(q == NULL) // them nut vao dau danh sach lien ket Insert_first(First, x); 75
  77. else // them nut vao sau nut q Insert_after(q, x); } // Phep toan clearlist: xoa tat ca cac nut trong danh sach lien ket void clearlist(NODEPTR &First) { NODEPTR p, q; // q la nut truoc, p la nut sau p = First; while(First != NULL) { p = First; First = First->next; free(p); } } // Phep toan traverse: duyet danh sach lien ket void traverse(NODEPTR First) { NODEPTR p; int stt = 0; p = First; if(p == NULL) printf("\n (Khong co sinh vien trong danh sach)"); while(p != NULL) { printf("\n %5d %8d %-30s %-10s", ++stt, p->sv.mssv, p->sv.ho,p->sv.ten); p = p->next; } } /* Tac vu search_info: tim kiem theo phuong phap tim kiem tuyen tinh, neu khong tim thay ham nay tra ve NULL, neu tim thay ham nay tra ve con tro chi nut tim thay */ NODEPTR search_info(NODEPTR First, int x) { NODEPTR p; p = First; 76
  78. while(p != NULL && p->sv.mssv != x ) p = p->next; return(p); } // Tac vu selectionsort: sap xep danh sach lien ket theo MSSV tang dan void selectionsort(NODEPTR &First) { NODEPTR p, q, pmin; sinhvien min; for(p = First; p->next != NULL; p = p->next) { min = p->sv; pmin = p; for(q = p->next; q != NULL; q = q->next) if(min.mssv > q->sv.mssv) { min = q->sv; pmin = q; } // hoan doi truong info cua hai nut p va pmin pmin->sv = p->sv; p->sv = min; } } char menu () { char chucnang; do { clrscr(); printf("\n\n\t\tCHUONG TRINH QUAN LY DANH SACH SINH VIEN"); printf("\n\nCac chuc nang cua chuong trinh:\n"); printf(" 1: Tao danh sach sinh vien\n"); printf(" 2: Them sinh vien vao danh sach\n"); printf(" 3: Xem danh sach sinh vien\n"); printf(" 4: Hieu chinh sinh vien\n"); printf(" 5: Xoa sinh vien trong danh sach\n"); printf(" 6: Tim kiem sinh vien theo MSSV\n"); 77
  79. printf(" 7: Sap xep danh sach theo MSSV\n"); printf(" 8: Them sinh vien vao danh sach da co thu tu\n"); printf(" 9: Xoa toan bo danh sach\n"); printf(" 0: Ket thuc chuong trinh\n"); printf("Chuc nang ban chon: "); chucnang = getche(); } while(chucnang '9') ; return chucnang; } void Create_list(NODEPTR &First) { NODEPTR Last,p ; sinhvien sv; char maso [5],c; clearlist(First); printf("Ma so sinh vien: "); gets(maso); sv.mssv = atoi(maso); while (sv.mssv !=0) { printf("Ho sinh vien: "); gets(sv.ho); printf("Ten sinh vien: "); gets(sv.ten); p=New_node(); p->sv=sv; if (First==NULL) First=p; else Last->next = p; Last=p; p->next=NULL; printf("Ma so sinh vien moi: "); gets(maso); sv.mssv = atoi(maso); } } 78
  80. // chuong trinh chinh void main() { int vitri; char chucnang, c, maso [5], c_vitri[5]; // khoi dong danh sach lien ket initialize(First); do { chucnang = menu(); flushall(); switch(chucnang) { case '1': { Create_list(First); break; } case '2': { printf("\nVi tri them (1, 2, ): "); gets(c_vitri); vitri = atoi(c_vitri); p = nodepointer(First, vitri-1);//p chi nut truoc nut can them if (vitri <=0 || p==NULL) { printf("Vi tri khong hop le"); getche(); } else { printf("Ma so sinh vien: "); gets(maso); sv.mssv = atoi(maso); printf("Ho sinh vien: "); gets(sv.ho); printf("Ten sinh vien: "); 79
  81. gets(sv.ten); if (vitri == 1) Insert_first(First, sv); else Insert_after(p, sv); } break; } case '3': { printf("\nDanh sach sinh vien: "); printf("\n STT MSSV HO TEN"); traverse(First); getche(); break; } case '4': { printf("\nVi tri hieu chinh (1, 2, ): "); gets(c_vitri); vitri = atoi(c_vitri); p = nodepointer(First, vitri); // p chi nut can hieu chinh if(p == NULL) { printf("Vi tri khong phu hop"); getche(); } else { printf("\nSTT:%d MSSV:%d HO:%s TEN:%s", vitri,p->sv.mssv, p->sv.ho, p->sv.ten); printf("\nMa so sv moi: "); gets(maso); sv.mssv = atoi(maso); printf("Ho sv moi: "); gets(sv.ho); printf("Ten sv moi: "); 80
  82. gets(sv.ten); p->sv = sv; } break; } case '5': { printf("\nVi tri xoa ( 1, 2, ): "); gets(c_vitri); vitri = atoi(c_vitri); p = nodepointer(First, vitri-1);//p chi nut truoc nut can xoa if (vitri <=0 || p==NULL) { printf("Vi tri khong hop le"); getche(); } else if(vitri == 1) Delete_first(First); else Delete_after(p); break; } case '6': { printf("\nMa so sinh vien can tim: "); gets(maso); sv.mssv = atoi(maso); p = search_info(First, sv.mssv); if(p == NULL) printf("Khong co sinh vien co MSSV %d trong danh sach", sv.mssv); else printf("Tim thay o vi tri %d trong danh sach", position(First, p)); getche(); break; } 81
  83. case '7': { printf("\n Ban co chac khong? (c/k): "); c = toupper(getche()); if( c == 'C') selectionsort(First); break; } case '8': { printf("\n Ban nho sap xep danh sach truoc. Nhan phim bat ky "); getche(); printf("\nMa so sinh vien: "); gets(maso); sv.mssv = atoi(maso); printf("Ho sinh vien: "); gets(sv.ho); printf("Ten sinh vien: "); gets(sv.ten); Insert_Order(First, sv); break; } case '9': { printf("\n Ban co chac khong (c/k): "); c = getche(); if(c == 'c' || c == 'C') clearlist(First); break; } } } while(chucnang != '0'); // xoa tat ca cac nut tren danh sach lien ket clearlist(First); } 82
  84. Iv. Danh s¸ch liªn kÕt vßng: IV.1. Kh¸i niÖ m : Danh s¸ ch liª n kÕ t vßng lµ danh s¸ ch liª n kÕ t mµ tr­êng next cña phÇ n tö cuèi sÏ chØ tíi phÇ n tö ®Ç u cña danh s¸ ch. info next Last • • • • H× nh 4.8 Danh s¸ch liª n kÕ t vßng Qui ­íc: §Ó ®¬n gi¶ n gi¶ i thuË t, ta qui ­íc dïng con trá Last ®Ó qu¶ n lý danh s¸ ch liª n kÕ t vßng, con trá nµ y sÏ chØ tíi phÇ n tö cuèi trong danh s¸ ch liª n kÕ t vßng. Nh­ vË y: + NÕ u danh s¸ ch liª n kÕ t vßng rçng % Last = NULL + NÕ u danh s¸ ch liª n kÕ t vßng chØ cã mét phÇ n tö % (Last ==Last->next) - Khai b¸ o: Ta khai b¸ o biÕ n Last qu¶ n lý danh s¸ ch liª n kÕ t vßng víi thµ nh phÇ n néi dung lµ sè nguyª n nh­ sau: struct node { int info ; struct node *next ; }; typedef struct node *NODEPTR; NODEPTR Last; IV.2. C¸c phÐ p to¸n trª n danh s¸ch liª n kÕ t vßng: IV.2.1.T¹o danh s¸ch: a. Khëi t¹o danh s¸ch (Initialize): dïng ®Ó khëi ®éng mét danh s¸ ch liª n kÕ t, cho ch­¬ng tr× nh hiÓ u lµ hiÖ n t¹ i danh s¸ ch liª n kÕ t ch­a cã phÇ n tö. void Initialize(NODEPTR &Last) { Last = NULL; } b. CÊp ph¸t vïng nhí (New_Node): cÊ p ph¸ t mét nót cho danh s¸ ch liª n kÕ t vßng. Hµ m New_Node nµ y tr¶ vÒ ®Þ a chØ cña nót võa cÊ p ph¸ t. 83
  85. NODEPTR New_node(void) { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return (p); } c. Thª m vµo ®Çu danh s¸ch (Ins_first): thª m mét nót cã néi dung x vµ o ®Ç u danh s¸ ch liª n kÕ t vßng. void Ins_first(NODEPTR &Last, int x) { NODEPTR p; p = New_node(); p->info = x; if (Empty(Last)) Last=p; else p->next = Last->next; Last->next = p; } d. Thª m vµo cuèi danh s¸ch (Ins_last): thª m mét nót cã néi dung x vµ o cuèi danh s¸ ch liª n kÕ t vßng. void Ins_last(NODEPTR &Last, int x) { NODEPTR p; p = New_node(); p->info = x; if (Empty(Last)) p->next=p; else { p->next = Last->next; Last->next = p; } Last = p; } 84
  86. e. Thª m nót míi vµo sau nót cã ®Þ a chØ p (Ins_after): thª m mét nót cã néi dung x vµ o sau nót cã ®Þ a chØ p trong danh s¸ ch liª n kÕ t vßng. void Ins_after(NODEPTR Last, NODEPTR p, int x) { NODEPTR q; if(p == NULL) printf("Nut hien tai khong co, nen khong the them"); else { if (p==Last) Ins_last(Last,x); else { q = New_node(); q->info = x; q->next = p->next; p->next = q; } } } IV.2.2. DuyÖ t danh s¸ch: Th«ng th­êng ta hay duyÖ t danh s¸ ch liª n kÕ t ®Ó thùc hiÖ n mét c«ng viÖ c g× ®ã, nh­ liÖ t kª d÷ liÖ u trong danh s¸ ch hay ®Õ m sè nót trong danh s¸ ch void Traverse(NODEPTR Last) { NODEPTR p; p = Last->next; // p chi toi phan tu dau trong dslk vong if(Last == NULL) printf("\n Danh sach rong "); else { printf("\n"); while(p != Last) { printf("%8d", p->info); p = p->next; } printf("%8d", p->info); } } 85
  87. IV.2.3. PhÐ p lo¹i bá: a. Gi¶i phãng vïng nhí (free): Hµ m nµ y dïng ®Ó hñy nót ®∙ cÊ p ph¸ t, vµ tr¶ vïng nhí vÒ l¹ i cho memory heap. free( p) ; víi p lµ biÕ n con trá b. KiÓ m tra danh s¸ch liª n kÕ t rçng hay kh«ng (Empty): hµ m Empty tr¶ vÒ TRUE nÕ u danh s¸ ch liª n kÕ t vßng rçng, vµ ng­îc l¹ i. int Empty(NODEPTR Last) { return(Last == NULL ? TRUE : FALSE); } c. Xãa phÇn tö ®Çu cña danh s¸ch (Del_first): muèn xãa 1 phÇ n tö khái danh s¸ ch liª n kÕ t th× ta ph¶ i kiÓ m tra xem danh s¸ ch cã rçng hay kh«ng. NÕ u danh s¸ ch cã phÇ n tö th× míi xãa ®­îc. void Del_first(NODEPTR &Last) { NODEPTR p; if(Empty(Last)) printf("Khong co nut trong danh sach lien ket vong, nen khong the xoa"); else { p = Last->next; // nut can xoa la nut dau if (p==Last) // danh sach chi co 1 nut Last=NULL; else Last->next = p->next; free(p); } } d. Xãa phÇn tö cuèi cña danh s¸ch (Del_last): muèn xãa 1 phÇ n tö khái danh s¸ ch liª n kÕ t th× ta ph¶ i kiÓ m tra xem danh s¸ ch cã rçng hay kh«ng. NÕ u danh s¸ ch cã phÇ n tö th× míi xãa ®­îc. void Del_last(NODEPTR &Last) { NODEPTR p; if(Empty(Last)) 86
  88. printf("Khong co nut trong danh sach lien ket vong, nen khong the xoa"); else { p = Last; // nut can xoa la nut cuoi if (Last->next==Last) // danh sach chi co 1 nut Last=NULL; else { for (NODEPTR q=Last->next;q->next !=Last; q=q->next); // q dung ngay truoc Last q->next = Last->next; Last=q; } free(p); } } e. Xãa phÇn tö ®øng sau nót cã ®Þ a chØ p (Del_after): xãa nót sau nót p. PhÐ p to¸ n nµ y kh«ng xãa ®­îc khi danh s¸ ch ®∙ rçng hoÆ c danh s¸ ch chØ cã 1 nót void Del_after(NODEPTR &Last, NODEPTR p) { NODEPTR q; if(Empty(Last)) printf("Khong co nut trong danh sach lien ket vong, nen khong the xoa"); else { // neu p la NULL hoac danh sach chi co 1 nut if((p == NULL) || (Last->next == Last)) printf("khong the xoa trong danh sach lien ket vong duoc"); else { q=p->next; if (p->next == Last) { p->next=Last->next; Last=p; } 87
  89. else p->next=q->next; free(q); } } } f. Xãa toµn bé danh s¸ch (Clearlist): ta cã thÓ sö dông lÖ nh Last=NULL ®Ó xãa toµ n bé danh s¸ ch, nh­ng trong bé nhí, c¸ c vïng nhí ®∙ cÊ p ph¸ t cho c¸ c nót kh«ng gi¶ i phãng vÒ l¹ i cho memory heap, nª n sÏ l∙ ng phÝ vïng nhí. Do ®ã, ta sö dông gi¶ i thuË t sau: void clearlist(NODEPTR &Last) { while(Last != NULL) Del_first(Last); } IV.2.4. T× m kiÕ m (Srch_info) : T× m nót ®Ç u tiª n trong danh s¸ ch liª n kÕ t vßng cã info b» ng víi x. Hµ m Srch_info nÕ u t× m thÊ y x trong danh s¸ ch th× tr¶ vÒ ®Þ a chØ cña nót ®ã trong danh s¸ ch, nÕ u kh«ng cã th× tr¶ vÒ trÞ NULL. NODEPTR Srch_info(NODEPTR Last, int x) { NODEPTR p; if (Empty(Last)) return (NULL); else { p = Last->next; // p chi toi phan tu dau cua dslk vong if (p->info==x) return (p); else { p=p->next; while(p != Last->next && p->info != x ) p = p->next; return (p->info==x ? p : NULL); } } } 88
  90. IV.2.5. S¾p xÕ p (Selection_Sort): S¾ p xÕ p danh s¸ ch liª n kÕ t vßng theo thø tù info t¨ ng dÇ n theo ph­¬ng ph¸ p Selection sort. - Néi dung: Ta so s¸ nh tÊ t c¶ c¸ c phÇ n tö cña danh s¸ ch ®Ó chän ra mét phÇ n tö nhá nhÊ t ®­a vÒ ®Ç u danh s¸ ch; sau ®ã, tiÕ p tôc chän phÇ n tö nhá nhÊ t trong c¸ c phÇ n tö cßn l¹ i ®Ó ®­a vÒ phÇ n tö thø hai trong danh s¸ ch. Qu¸ tr× nh nµ y lÆ p l¹ i cho ®Õ n khi chän ra ®­îc phÇ n tö nhá thø (n-1). - Gi¶ i thuË t: void selectionsort(NODEPTR &Last) { NODEPTR p, q, pmin; int min; for(p = Last->next; p->next != Last->next; p = p->next) { min = p->info; pmin = p; for(q = p->next; q != Last->next; q = q->next) if(min > q->info) { min = q->info; pmin = q; } // hoan doi truong info cua hai nut p va pmin pmin->info = p->info; p->info = min; } } VÝ dô: ViÕ t ch­¬ng tr× nh thùc hiÖ n c¸ c c«ng viÖ c sau trª n mét danh s¸ ch c¸ c sè nguyª n víi cÊ u tróc d÷ liÖ u lµ danh s¸ ch liª n kÕ t vßng : 1. T¹ o danh s¸ ch sè 2. Thª m phÇ n tö vµ o ®Ç u danh s¸ ch 3. Thª m phÇ n tö vµ o cuèi danh s¸ ch 4. Thª m phÇ n tö vµ o sau phÇ n tö cã gi¸ trÞ x 5. Xãa phÇ n tö ®Ç u trong danh s¸ ch 6. Xãa phÇ n tö cuèi trong danh s¸ ch 7. LiÖ t kª danh s¸ ch 89
  91. 8. S¾ p xÕ p danh s¸ ch theo thø tù t¨ ng 9. Xãa toµ n bé danh s¸ ch #include #include #include #include #include #define TRUE 1 #define FALSE 0 struct node { int info; struct node *next; }; typedef struct node *NODEPTR; NODEPTR Last; // Phep toan New_node: cap phat mot nut cho danh sach lien ket NODEPTR New_node(void) { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return(p); } // Phep toan initialize: khoi dong danh sach lien ket void Initialize(NODEPTR &Last) { Last = NULL; } // Tac vu Empty: kiem tra danh sach lien ket co bi rong khong int Empty(NODEPTR Last) { return(Last == NULL ? TRUE : FALSE); } // Phep toan Ins_first: them nut moi vao dau danh sach lien ket vong void Ins_first(NODEPTR &Last, int x) { NODEPTR p; 90
  92. p = New_node(); p->info = x; if (Empty(Last)) Last=p; else p->next = Last->next; Last->next = p; } // Phep toan Ins_last: them nut moi vao cuoi danh sach lien ket vong void Ins_last(NODEPTR &Last, int x) { NODEPTR p; p = New_node(); p->info = x; if (Empty(Last)) p->next=p; else { p->next = Last->next; Last->next = p; } Last = p; } // Phep toan Ins_after: them nut moi sau nut co dia chi p void Ins_after(NODEPTR Last, NODEPTR p, int x) { NODEPTR q; if(p == NULL) printf("Nut hien tai khong co, nen khong the them"); else { if (p==Last) Ins_last(Last,x); else { q = New_node(); q->info = x; q->next = p->next; 91