Đại cương về lập trình

ª 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: 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) { Kü thuËt lËp tr× nh 99 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. NODEPTR New_Node() { 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. 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. void Insert_After(NODEPTR p, int x) { NODEPTR q; if(p == NULL) printf("khong them nut moi vao danh sach duoc"); else { q = New_Node(); q->info = x; q->next = p->next; p->next = q; } } Kü thuËt lËp tr× nh 100 II.2. CËp nhËt danh s¸ch: a. Gi¶ i phãng vïng nhí(Free_Node): 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. void Free_Node(NODEPTR p) { free(p); } 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. 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_Node(p); } } d. Xãa phÇ n tö ®øng sau nót cã ®Þa chØ p (Delete_After): 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; Kü thuËt lËp tr× nh 101 Free_Node(q); } } e. Xãa toµ n bé danh s¸ ch (Delete_All): 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 Delete_All (NODEPTR &First) { NODEPTR p; while (First != NULL) { p=First; First = First->next; // hoÆ c First = p->next Free_Node(p); } } II.3. 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 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", stt++, p->info); p = p->next; } } II.4. T× m kiÕ m (Search): 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 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(NODEPTR First, int x) { NODEPTR p; Kü thuËt lËp tr× nh 102 p = First; while(p != NULL && p->info != x ) p = p->next; return (p); } 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; } } Kü thuËt lËp tr× nh 103 Bµi tËp: 1. ViÕ t ch­¬ng tr× nh t¹ o mét menu thùc hiÖ n c¸ c c«ng viÖ c sau: a. NhË p danh s¸ ch liª n kÕ t theo gi¶ i thuË t thª m vÒ ®Ç u danh s¸ ch, mçi phÇ n tö gåm cã c¸ c th«ng tin sau: mssv (int), vµ hoten ( char hoten[30] ). b. LiÖ t kª danh s¸ ch ra mµ n h× nh c. Cho biÕ t tæng sè nót trong danh s¸ ch liª n kÕ t, ®Æ t tª n hµ m lµ Reccount ( int Reccount(NODEPTR First) ) d. Thª m 1 phÇ n tö cã néi dung info (mssv, hoten) vµ o sau phÇ n tö cã thø tù thø i trong danh s¸ ch. Ghi chó: - Thø tù theo qui ­íc b¾ t ®Ç u lµ 1 - NÕ u (i = 0) thª m vµ o ®Ç u danh s¸ ch NÕ u i > Reccount(&First) th× thª m vµ o cuèi danh s¸ ch. e. In ra hä tª n cña sinh viª n cã m∙ do ta nhË p vµ o. f. Lo¹ i bá nót cã m∙ do ta nhË p vµ o, tr­íc khi xãa hái l¹ i "B¹ n thË t sù muèn xãa (Y/N) ? " g. S¾ p xÕ p l¹ i danh s¸ ch theo thø tù m∙ sè gi¶ m dÇ n. h.Ghi toµ n bé danh s¸ ch vµ o file tª n 'DSSV.DAT' i. N¹ p danh s¸ ch tõ file 'DSSV.DAT' vµ o danh s¸ ch liª n kÕ t. NÕ u trong danh s¸ ch liª n kÕ t ®∙ cã nót th× xãa tÊ t c¶ d÷ liÖ u hiÖ n cã trong danh s¸ch liª n kÕ t tr­íc khi ®­a d÷ liÖ u tõ file vµ o. 2. ViÕ t ch­¬ng tr× nh t¹ o mét danh s¸ ch liª n kÕ t theo gi¶ i thuË t thª m vµ o cuèi danh s¸ ch, mçi nót chøa mét sè nguyª n. 3. -ViÕ t hµ m tª n Delete_Node ®Ó xãa nót cã ®Þa chØ p. - ViÕ t mét hµ m lo¹ i bá tÊ t c¶ c¸ c nót cã néi dung x trong danh s¸ ch liª n kÕ t First. 4. ViÕ t hµ m Copy_List trª n danh s¸ ch liª n kÕ t ®Ó t¹ o ra mét danh s¸ ch liª n kÕ t míi gièng danh s¸ ch liª n kÕ t cò. 5. GhÐp mét danh s¸ ch liª n kÕ t cã ®Þa chØ ®Ç u lµ First2 vµ o mét danh s¸ ch liª n kÕ t cã ®Þa chØ ®Ç u lµ First1 ngay sau phÇ n tö thø i trong danh s¸ ch liª n kÕ t First1. 6. ViÕ t hµ m läc danh s¸ ch liª n kÕ t ®Ó tr¸ nh tr­êng hîp c¸ c nót trong danh s¸ ch liª n kÕ t bÞ trïng info. 7. §¶ o ng­îc vïng liª n kÕ t cña mét danh s¸ ch liª n kÕ t sao cho: - First sÏ chØ ®Õ n phÇ n tö cuèi - PhÇ n tö ®Ç u cã liª n kÕ t lµ NULL. Kü thuËt lËp tr× nh 104 8. ViÕ t hµ m Left_Traverse (NODEPTR &First) ®Ó duyÖ t ng­îc danh s¸ ch liª n kÕ t. 9. ViÕ t gi¶ i thuË t t¸ ch mét danh s¸ ch liª n kÕ t thµ nh hai danh s¸ ch liª n kÕ t, trong ®ã mét danh s¸ ch liª n kÕ t chøa c¸ c phÇ n tö cã sè thø tù lÏ vµ mét danh s¸ ch liª n kÕ t chøa c¸ c phÇ n tö cã sè thø tù ch½ n trong danh s¸ ch liª n kÕ t cò. 10. - T¹ o mét danh s¸ ch liª n kÕ t chøa tª n häc viª n, ®iÓ m trung b× nh, h¹ ng cña häc viª n (víi ®iÒ u kiÖ n chØ nhË p tª n vµ ®iÓ m trung b× nh). Qu¸ tr× nh nhË p sÏ dõng l¹ i khi tª n nhË p vµ o lµ rçng. - XÕ p h¹ ng cho c¸ c häc viª n. In ra danh s¸ ch häc viª n thø tù h¹ ng t¨ ng dÇ n (Ghi chó : Cïng ®iÓ m trung b× nh th× cïng h¹ ng). 11. NhË p hai ®a thøc theo danh s¸ ch liª n kÕ t. In ra tÝ ch cña hai ®a thøc nµ y. VÝ dô: §a thøc First1 : 2x5+4x2-1 §a thøc First2 : 10x7-3x4+x2 ⇒ KÕ t qu¶ in ra : 20x12 + 34x9 - 8x7 - 12x6 + 7x4 - x2 (Ghi chó : Kh«ng nhË p vµ in ra c¸ c sè h¹ ng cã hÖ sè b» ng 0) 12. ViÕ t gi¶ i thuË t thª m phÇ n tö cã néi dung x vµ o danh s¸ ch liª n kÕ t cã thø tù t¨ ng dÇ n sao cho sau khi thª m danh s¸ ch liª n kÕ t vÉ n cã thø tù t¨ ng. 13. Lo¹ i bá phÇ n tö cã néi dung lµ x trong danh s¸ ch liª n kÕ t cã thø tù t¨ ng dÇ n. 14. Cho 2 danh s¸ ch liª n kÕ t First1, First2 cã thø tù t¨ ng dÇ n theo info. ViÕ t gi¶ i thuË t Merge ®Ó trén 2 danh s¸ ch liª n kÕ t nµ y l¹ i sao cho danh s¸ ch liª n kÕ t sau khi trén còng cã thø tù t¨ ng dÇ n. Kü thuËt lËp tr× nh 105 CH­¬NG 6 c¸c thuËt to¸n trªn cÊu tróc c©Y (Tree) C© y lµ mét cÊ u tróc d÷ liÖ u rÊ t th«ng dông vµ quan träng trong nhiÒ u ph¹ m vi kh¸ c nhau cña kü thuË t m¸ y tÝ nh. VÝ dô : Tæ chøc c¸ c quan hÖ hä hµ ng trong mét gia ph¶ , môc lôc cña mét cuèn s¸ ch, x© y dùng cÊ u tróc vÒ có ph¸ p trong c¸ c tr× nh biª n dÞch. Trong ch­¬ng tr× nh nµ y, chóng ta kh¶ o s¸ t c¸ c kh¸ i niÖ m c¬ b¶ n vÒ c© y, c¸c phÐp to¸ n trª n c© y nhÞ ph© n, còng nh­ c¸ c phÐp to¸ n trª n c© y nhÞ ph© n c© n b» ng ( AVL tree) vµ øng dông cña hai lo¹ i c© y nhÞ ph© n t× m kiÕ m (BST), c© y nhÞ ph© n c© n b» ng ( AVL tree). I. Ph©n lo¹i c©y: I.1. Mét sè kh¸i niÖ m c¬ b¶n: 1. C©y: C© y lµ tË p hîp c¸ c phÇ n tö gäi lµ nót, mét nót (t­¬ng tù nh­ mét phÇ n tö cña d∙ y) cã thÓ cã kiÓ u bÊ t kú. C¸ c nót ®­îc biÓ u diÔ n bëi 1 ký tù ch÷, mét chuçi, mét sè ghi trong mét vßng trßn. Mét sè ®Þnh nghÜ a theo ®Ö quy ( Mét nót ®¬n còng chÝ nh lµ mét c© y. ( C¸ c nót ®­îc gäi lµ ë cïng mét c© y khi cã ®­êng ®i gi÷a c¸ c nót nµ y. ( Mét c© y sÏ bao gåm mét nót gèc (Root) vµ m c© y con, trong mçi c© y con l¹ i cã mét nót gèc vµ m1 c© y con nhá h¬n v.v. ( Mét c© y kh«ng cã mét nót nµ o c¶ gäi lµ c© y rçng. VÝ dô 1 : A B C G H E J D F KI 1 2 3 4 Nuùt goác H× nh 5.1. C© y víi nót gèc lµ A - A lµ nót gèc víi 3 c© y con lÇ n l­ît cã 3 nót gèc riª ng lµ ø B, C, D - Nót cha (ancestor) Nót con (descendent) A lµ nót cha cña B, C, D G, H lµ nót con cña C G, H kh«ng quan hÖ cha con víi A Kü thuËt lËp tr× nh 106 VÝ dô 2 : Víi ®Ò c­¬ng mét m«n häc T, ta cã thÓ biÓ u diÔ n d¹ ng c© y nh­ sau : T CHÖÔNG I CHÖÔNG II CHÖÔNG III I.1 I.2 II.1 II.3II.2 II.1.1 II.1.2 H× nh 5.2 CH­¬NG I I.1 I.2 CH­¬NG II II.1 II.1.1 II.1.2 II.2 II.3 CH­¬NG III 2. Nót cha (Ancestor) : Nót ®øng trª n cña mét nót ®­îc gäi lµ nót cha C lµ nót cha cña G, H Nót con (descendent) : Nót ®øng sau mét nót kh¸ c ®­îc gäi lµ nót con cña nót ®ã. Nót I, J, K lµ nót con cña nót E 3. BËc (degree) : - BË c cña nót lµ sè c© y con cña nót ®ã. C cã bË c lµ 2, E cã bË c lµ 3 (H× nh 5.1) - BË c cña c© y lµ bË c lín nhÊ t cña c¸ c nót trong c© y. C© y trong h× nh 5.1 cã bË c lµ 3. C© y bË c n ®­îc gäi lµ c© y n ph© n nh­ c© y nhÞ ph© n, c© y tam ph© n. 4. Nót l¸ vµ nót trung gian: - Nót l¸ lµ nót cã bË c b» ng 0 (tøc lµ kh«ng cã c© y con nµ o) : - Nót trung gian: lµ mét nót cã bË c kh¸ c 0 vµ kh«ng ph¶ i lµ nót gèc. VÝ dô: Trong h× nh 5.1, B, G, H, I, J, K, F lµ nót l¸ C, D, E lµ nót trung gian. 5. Møc cña nót (level) : Nót gèc cã møc lµ 1 Møc cña nót con = møc cña nót cha + 1 Kü thuËt lËp tr× nh 107 VÝ dô: trong h× nh 5.1, A cã møc lµ 1 B, C, D cã møc lµ 2 G, H, E, F cã møc lµ 3 I, J, K cã møc lµ 4 6. ChiÒ u cao cña c©y (height) : lµ møc lín nhÊ t cña c¸ c nót l¸ trong c© y. VÝ dô: C© y trong h× nh 5.1 cã chiÒ u cao lµ 4 7. Thø tù cña c¸c nót (order of nodes) : NÕ u c© y ®­îc gäi lµ cã thø tù th× ph¶ i ®¶ m b¶ o vÞ trÝ cña c¸ c nót con tõ tr¸ i qua ph¶ i, tøc lµ nÕ u thay ®æi vÞ trÝ cña mét nót con bÊ t kú th× ta ®∙ cã mét c© y míi. VÝ dô : A B C A C B caây khaùc H× nh 5.3: Sau khi ®æi vÞ trÝ cña 2 nót B, C ta ®∙ cã c© y míi. 8. ChiÒ u dµi ®­êng ®i (Path length): - ChiÒ u dµ i ®­êng ®i cña nót x: lµ sè c¸ c c¹ nh ®i tõ nót gèc ®Õ n nót x. VÝ dô: Trong h× nh 5.1: Nót gèc A cã chiÒ u dµ i ®­êng ®i lµ 1 Nót B, C, D cã chiÒ u dµ i ®­êng ®i lµ 2 Tæng qu¸ t: mét nót t¹ i møc i cã chiÒ u dµ i ®­êng ®i lµ i - ChiÒ u dµ i ®­êng ®i cña c© y: lµ tæng cña c¸ c chiÒ u dµ i ®­êng ®i cña tÊ t c¶ c¸ c nót trong c© y. VÝ dô: ChiÒ u dµ i ®­êng ®i cña c© y trong h× nh 5.1 lµ 31. ChiÒ u dµ i ®­êng ®i trung b× nh cña c© y: n/)i.n(P i ii ∑= trong ®ã ni lµ sè c¸ c nót ë møc i vµ n lµ tæng sè c¸ c nót trong c© y. I.2. C¸ch biÓ u diÔ n c©y: ®Ó biÓ u diÔ n 1 c© y, ta cã nhiÒ u c¸ ch nh­ biÓ u diÔ n b» ng ®å thÞ,b» ng gi¶ n ®å, b» ng chØ sè.. Nh­ng th«ng th­êng, ta hay dïng d¹ ng ®å thÞ ®Ó biÓ u diÔ n 1 c© y nh­ h× nh 5.1 I.3. BiÓ u diÔ n thø tù c¸c nót trong c©y : Kü thuËt lËp tr× nh 108 Mét c© y th­êng tæ chøc c¸ c nót theo mét thø tù nhÊ t ®Þnh c¨ n cø vµ o mét néi dung gäi lµ khãa cña c¸ c nót. Cã thÓ tæ chøc c© y cã khãa t¨ ng dÇ n theo møc tõ tr¸ i qua ph¶ i nh­ vÝ dô sau : 1 2 3 4 Root 76 8 5 9 ROOT %1%2%3%4%5%6%7%8%9 Nh­ vË y khi duyÖ t l¹ i c© y theo møc t¨ ng dÇ n vµ tõ tr¸ i qua ph¶ i ta sÏ l¹ i cã ®­îc thø tù c¸ c nót nh­ trª n. H× nh 5.4. C© y cã thø tù t¨ ng dÇ n theo møc tõ tr¸ i qua ph¶ i II. C©y nhÞ ph©n (Binary tree) II.1. §Þnh nghÜ a : 1. C©y nhÞ ph©n lµ c© y cã bË c b» ng 2, tøc lµ sè nót con tèi ®a cña mét nót bÊ t kú trong c© y lµ 2. C© y nhÞ ph© n cã thÓ lµ mét c© y rçng (kh«ng cã nót nµ o) hoÆ c c© y chØ cã mét nót, hoÆ c c© y chØ cã c¸ c nót con bª n tr¸ i (Left Child) hoÆ c nót con bª n ph¶ i (Right Child) hoÆ c c¶ hai. VÝ dô: H× nh 5.4 lµ c© y nhÞ ph© n. 2. C¸c c©y nhÞ ph©n ®Æc biÖ t: - C© y nhÞ ph© n ®óng: Mét c© y nhÞ ph© n ®­îc gäi lµ c© y nhÞ ph© n ®óng nÕ u nót gèc vµ tÊ t c¶ c¸ c nót trung gian ®Ò u cã 2 nót con. A B D E G Y C X F H I H× nh 5.5. C© y nhÞ ph© n ®óng Kü thuËt lËp tr× nh 109 Ghi chó: nÕ u c© y nhÞ ph© n ®óng cã n nót l¸ th× c© y nµ y sÏ cã tÊ t c¶ 2n-1 nót. - C© y nhÞ ph© n ®Ç y: Mét c© y nhÞ ph© n gäi lµ c© y nhÞ ph© n ®Ç y víi chiÒ u cao d th× : . Nã ph¶ i lµ c© y nhÞ ph© n ®óng vµ . TÊ t c¶ c¸ c nót l¸ ®Ò u cã møc lµ d. H× nh 5.5 kh«ng ph¶ i lµ c© y nhÞ ph© n ®Ç y A B D H I E J K C F L M G N O H× nh 5.6. C© y nhÞ ph© n ®Ç y. Ghi chó: C© y nhÞ ph© n ®Ç y lµ c© y nhÞ ph© n cã sè nót tèi ®a ë mçi møc. - C© y nhÞ ph© n t× m kiÕ m (Binary Search Tree): Mét c© y nhÞ ph© n gäi lµ c© y nhÞ ph© n t× m kiÕ m nÕ u vµ chØ nÕ u ®èi víi mäi nót cña c© y th× khãa cña mét nót bÊ t kú ph¶ i lín h¬n khãa cña tÊ t c¶ c¸ c nót trong c© y con bª n tr¸ i cña nã vµ ph¶ i nhá h¬n khãa cña tÊ t c¶ c¸ c nót trong c© y con bª n ph¶ i cña nã. VÝ dô: 8 7 9 3 12 11 102 1 5 4 6 k1 <k1 <k1 H× nh 5.7. C© y nhÞ ph© n t× m kiÕ m (BST) Kü thuËt lËp tr× nh 110 - C© y nhÞ ph© n c© n b» ng (AVL): Mét c© y nhÞ ph© n ®­îc gäi lµ c© y nhÞ ph© n c© n b» ng nÕ u vµ chØ nÕ u ®èi víi mäi nót cña c© y th× chiÒ u cao cña c© y con bª n tr¸ i vµ chiÒ u cao cña c© y con bª n ph¶ i h¬n kÐm nhau nhiÒ u nhÊ t lµ 1. (Theo Adelson-Velski vµ Landis). A C E F B D G I JH H× nh 5.8. C© y nhÞ ph© n c© n b» ng - C© y nhÞ ph© n c© n b» ng hoµ n toµ n: Mét c© y nhÞ ph© n ®­îc gäi lµ c© y nhÞ ph© n c© n b» ng hoµ n toµ n nÕ u vµ chØ nÕ u ®èi víi mäi nót cña c© y th× sè nót cña c© y con bª n tr¸ i vµ sè nót cña c© y con bª n ph¶ i h¬n kÐm nhau nhiÒ u nhÊ t lµ 1. A C E F B D IH E H H× nh5.9. C© y nhÞ ph© n c© n b» ng hoµ n toµ n 3. C¸c phÐp duyÖ t c©y nhÞ ph©n (Traverse) : lµ qu¸ tr× nh ®i qua c¸ c nót ®óng mét lÇ n. Khi duyÖ t c© y, ta th­êng dïng 3 c¸ ch duyÖ t c¬ b¶ n sau : ' Preorder - TiÒ n tù (NLR) duyÖ t qua nót gèc tr­íc, sau ®ã ®i qua c© y con bª n tr¸ i l¹ i ¸ p dông Preorder cho c© y con bª n tr¸ i. Cuèi cïng qua c© y con bª n ph¶ i, ¸ p dông Preorder cho c© y con bª n ph¶ i. VÝ dô: Theo c© y nhÞ ph© n 5.4, ta cã: ROOT % 1 % 2 % 3 % 4 % 6 % 7 % 5 % 8 % 9 'Inorder - Trung tù (LNR) : qua c© y con bª n tr¸ i duyÖ t tr­íc (theo thø tù LNR), sau ®ã th¨ m nót gèc. Cuèi cïng qua c© y con bª n ph¶ i (theo thø tù LNR) VÝ dô: Theo c© y nhÞ ph© n 5.4, ta cã: ROOT % 2 % 1 % 6 % 4 % 7 % 3 % 8 % 5 % 9 'Postorder - HË u tù (LRN) : qua c© y con bª n tr¸ i duyÖ t tr­íc (theo thø tù LRN), sau ®ã qua c© y con bª n ph¶ i (theo thø tù LRN). Cuèi cïng th¨ m nót gèc. VÝ dô: Theo c© y nhÞ ph© n 5.4, ta cã: ROOT % 2 % 6 % 7 % 4 % 8 % 9 % 5 % 3 % 1 Kü thuËt lËp tr× nh 111 Ghi chó : §èi víi c© y ta cã thÓ tæ chøc thø tù theo khãa lµ mét néi dung cña nót hoÆ c ta ®Æ t thª m 1 field gäi lµ khãa cña nót . II.2. C¸c phÐp to¸n trª n c©y nhÞ ph©n: - Khai b¸o: §Ó tæ chøc d÷ liÖ u theo c© y nhÞ ph© n, ta cã thÓ dïng mét néi dung cña d÷ liÖ u ®Ó lµ m khãa s¾ p xÕ p vµ tæ chøc c© y theo nhiÒ u c¸ ch kh¸ c nhau. Nh­ng th«ng th­êng ®Ó thuË n tiÖ n cho viÖ c t× m kiÕ m vµ thùc hiÖ n c¸ c phÐp to¸ n kh¸ c trª n c© y, ng­êi ta t¹ o thª m mét khãa riª ng trong c¸ c phÇ n tö vµ t¹ o ra c© y nhÞ ph© n t× m kiÕ m. §Ó khai b¸ o biÕ n tree qu¶ n lý mét c© y nhÞ ph© n, víi néi dung info chøa sè nguyª n, ta khai b¸ o nh­ sau: struct nodetype { int key; int info; struct nodetype *left; struct nodetype *right; }; typedef struct nodetype *NODEPTR; NODEPTR tree; 1. T¹o c©y: a. Khëi t¹ o c© y(Initialize): dïng ®Ó khëi ®éng c© y nhÞ ph© n, cho ch­¬ng tr× nh hiÓ u lµ hiÖ n t¹ i c© y nhÞ ph© n rçng. void Initialize(NODEPTR &root) { root = NULL; } Lêi gäi hµ m: Initialize(tree); b. CÊ p ph¸ t vïng nhí (New_Node): cÊ p ph¸ t mét nót cho c© y nhÞ ph© n. Hµ m New_Node nµ y tr¶ vÒ ®Þa chØ cña nót võa cÊ p ph¸ t. NODEPTR New_Node(void) { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct nodetype)); return(p); } Lêi gäi hµ m: p= New_Node(); Kü thuËt lËp tr× nh 112 c. T¹ o c© y BST (Create_Tree): Trong gi¶ i thuË t t¹ o c© y BST, ta cã dïng hµ m Insert. Hµ m Insert: dïng ph­¬ng ph¸ p ®Ö qui thª m nót cã khãa x, néi dung a vµ o c© y cã nót gèc root . C© y nhÞ ph© n t¹ o ®­îc qua gi¶ i thuË t Create_Tree lµ c© y nhÞ ph© n t× m kiÕ m (BST). void Insert(NODEPTR root, int x, int a) { NODEPTR p; if(x == root->key) // khãa bÞ trïng, dõng ch­¬ng tr× nh { printf("bi trung khoa, khong them nut nay duoc"); return; } if(x info && root->left == NULL) // ®iÒ u kiÖ n dõng gi¶ i thuË t ®Ö qui { p = New_Node(); // cÊ p ph¸ t vïng nhí p->key =x; p->info = a; p->left = NULL; p->right = NULL; root->left=p; return; } if(x > root->info && root->right == NULL) //®iÒ u kiÖ n dõng gi¶ i thuË t ®Ö qui { p = New_Node(); p->key =x; p->info = a; p->left = NULL; p->right = NULL; root->right=p ; return; } if(x info) // b­íc ®Ö qui Insert(root->left, x,a); // gäi ®Ö qui qua nh¸ nh tr¸ i else Insert(root->right, x,a); // gäi ®Ö qui qua nh¸ nh ph¶ i } Kü thuËt lËp tr× nh 113 void Create_Tree(NODEPTR &root) { int khoa, noidung; char so[10]; NODEPTR p; do { printf("Nhap khoa :"); gets(so) ; khoa = atoi(so); if (khoa !=0) { printf("Nhap noi dung :"); gets(so) ; noidung = atoi(so); if (root==NULL) { p = New_Node(); p->key = khoa; p->info = noidung; p->left = NULL; p->right = NULL; root =p; } else Insert(root,khoa,noidung); } } while (khoa!=0); // khãa =0 th× dõng nhË p } Ghi chó : §Ó t¹ o c© y nhÞ ph© n do biÕ n tree qu¶ n lý, ta gäi: Create_Tree(tree); 2. CËp nhËt c©y: a. Gi¶ i phãng vïng nhí(Free_Node): gi¶ i phãng vïng nhí mµ p ®ang trá ®Õ n. void Free_Node(NODEPTR p) { free(p); } Lêi gäi hµ m: Free_Node (p); b. KiÓ m tra c© y nhÞ ph© n rçng hay kh«ng (Empty): hµ m Empty tr¶ vÒ TRUE nÕ u c© y nhÞ ph© n rçng, vµ ng­îc l¹ i. int Empty(NODEPTR root) return(root == NULL ? TRUE : FALSE); } Kü thuËt lËp tr× nh 114 Lêi gäi hµ m: Empty(tree) c. Hñy bá mét nót trong c© y nhÞ ph© n BST (Remove): Xãa nót cã khãa lµ x trong c© y nhÞ ph© n t× m kiÕ m sao cho sau khi xãa th× c© y nhÞ ph© n vÉ n lµ c© y nhÞ ph© n t× m kiÕ m. Ta cã 3 tr­êng hîp : - Tr­êng hîp 1: nót p cÇ n xãa lµ nót l¸ . ViÖ c xãa nót p chØ ®¬n gi¶ n lµ hñy nót p p1 p p1 p1 p p1 - Tr­êng hîp 2: Nót p cÇ n xãa cã 1 c© y con, th× ta cho rp chØ tíi nót p. Sau ®ã, ta t¹ o liª n kÕ t tõ nót cha cña p tíi nót con cña rp, cuèi cïng hñy nót p. 10 5 3 15 12 20 2 4 p xoùa nuùt p 10 3 15 12 202 4 rp H× nh 5.10. Xãa nót p trong tr­êng hîp nót nµ y cã 1 c© y con bª n tr¸ i. 2 10 5 3 15 4 20 18 25 rp p xoùa nuùt p 10 5 3 20 18 25 2 4 H× nh 5.11. Xãa nót p trong tr­êng hîp nót nµ y cã 1 c© y con bª n ph¶ i. - Tr­êng hîp 3: Nót p cÇ n xãa cã 2 c© y con. Ta cho rp chØ tíi nót p. Do tÝ nh chÊ t nót cùc tr¸ i cña c© y con bª n ph¶ i cña p cã khãa võa lín h¬n khãa cña p, nª n ®Ó lo¹ i p th× ta sÏ cho r chØ tíi nót cùc tr¸ i ®ã. Sau ®ã, ta sao chÐp néi dung Kü thuËt lËp tr× nh 115 vµ khãa cña nót r vµ o nót mµ rp ®ang chØ tíi. Ta t¹ o liª n kÕ t thÝ ch hîp ®Ó bøt nót rp ra khái c© y nhÞ ph© n vµ cuèi cïng xãa nót rp. 10 5 20 15 30 12 18 28 25 35 p nuùt traùi nhaát cuûa caây con beân phaûi 10 5 25 15 30 12 18 28 35 r H× nh 5.12. Xãa nót p trong tr­êng hîp nót nµ y cã 2 c© y con. Hµ m Remove xãa nót cã khãa lµ x: NODEPTR rp; void remove_case_3 ( NODEPTR &r ) { if (r->left != NULL) remove_case_3 (r->left); //den day r la nut cuc trai cua cay con ben phai co nut goc la rp} else { rp->key = r->key; //Chep noi dung cua r sang rp "; rp->info =r->info; // de lat nua free(rp) rp = r; r = r->right; } } void remove (int x , NODEPTR &p ) { if (p == NULL) printf ("Khong tm thay"); else if (x key) remove (x, p->left); else if (x > p->key) Kü thuËt lËp tr× nh 116 remove (x, p->right); else // p^.key = x { rp = p; if (rp->right == NULL) p = rp->left; // p lµ nót l¸ hoac la nut chi co cay con ben trai else if (rp->left == NULL) p = rp->right; // p lµ nut co cay con ben phai else remove_case_3 (rp->right); free (rp); } } Lêi gäi hµ m: Remove(x, tree); // x lµ khãa cña nót muèn xãa d. T× m kiÕ m (Search): T× m nót cã khãa b» ng x trª n c© y nhÞ ph© n BST cã gèc lµ root. NÕ u t× m thÊ y x trong c© y th× tr¶ vÒ ®Þa chØ cña nót cã trÞ b» ng x trong c© y, nÕ u kh«ng cã th× tr¶ vÒ trÞ NULL. Do c© y nhÞ ph© n lµ BST nª n ta cã thÓ t× m kiÕ m nhanh b» ng ph­¬ng ph¸ p t× m kiÕ m nhÞ ph© n. NODEPTR Search(NODEPTR root, int x) { NODEPTR p; p = root; while(p != NULL && x!=p->key) if(x key) p = p->left; else p = p->right; return(p); } Lêi gäi hµ m: p=Search(tree, x); 3. C¸c phÐp duyÖ t c©y: Cã 3 c¸ ch duyÖ t c¬ b¶ n lµ NLR, LNR, LRN vµ mét c¸ ch ®Æ c biÖ t lµ duyÖ t c© y theo møc. ë ®© y, ta chØ xÐt 3 ph­¬ng ph¸ p duyÖ t NLR, LNR vµ LRN. XÐt c© y sau : Kü thuËt lËp tr× nh 117 4 2 1 5 3 6 a. DuyÖ t c©y theo thø tù NLR (Preorder): void Preorder (NODEPTR root) { if(root != NULL) { printf("%d ", root->info); Preorder(root->left); Preorder (root->right); } } b. DuyÖ t c©y theo thø tù LNR (Inorder): void Inorder(NODEPTR root) { if(root != NULL) { Inorder(root->left); printf("%d ", root->info); Inorder(root->right); } } c. DuyÖ t c©y theo thø tù LRN (Posorder): void Posorder(NODEPTR root) { if(root != NULL) { Posorder(root->left); Posorder(root->right); printf("%d ", root->info); } } III. c©y nhÞ ph©n T×M KIÕM c©n b»ng (AVL): Chóng ta t¹ o c© y nhÞ ph© n t× m kiÕ m môc ®Ý ch lµ ®Ó t× m khãa cho nhanh, tuy nhiª n ®Ó t¨ ng tèc ®é t× m kiÕ m th× c© y cÇ n ph¶ i c© n ®èi vÒ 2 nh¸ nh theo tõng nót trong c© y. Do vË y, ta sÏ t× m c¸ ch tæ chøc l¹ i c© y BST sao cho nã c© n b» ng. Kü thuËt lËp tr× nh 118 III.1. §Þnh nghÜ a: - C© y nhÞ ph© n t× m kiÕ m c© n b» ng (AVL) lµ c© y nhÞ ph© n t× m kiÕ m mµ t¹ i tÊ t c¶ c¸ c nót cña nã chiÒ u cao cña c© y con bª n tr¸ i cña nã vµ chiÒ u cao cña c© y con bª n tr¸ i chª nh lÖ ch nhau kh«ng qu¸ mét. 10 20 15 30 6 8 12 25 4018 H× nh 5.14. C© y nhÞ ph© n t× m kiÕ m c© n b» ng L­u ý: Víi c© y AVL, viÖ c thª m vµ o hay lo¹ i bá 1 nót trª n c© y cã thÓ lµ m c© y mÊ t c© n b» ng, khi ®ã ta ph¶ i c© n b» ng l¹ i c© y. Tuy nhiª n viÖ c c© n b» ng l¹ i trª n c© y AVL chØ x¶ y ra ë ph¹ m vi côc bé b» ng c¸ ch xoay tr¸ i hoÆ c xoay ph¶ i ë mét vµ i nh¸ nh c© y con nª n gi¶ m thiÓ u chi phÝ c© n b» ng. - ChØ sè c©n b»ng (balance factor) cña mét nót p trª n c© y AVL= lh(p) - rh(p) Trong ®ã: lh (p) lµ chiÒ u cao cña c© y con bª n tr¸ i cña p rh(p) lµ chiÒ u cao cña c© y con bª n ph¶ i cña p Ta cã c¸ c tr­êng hîp sau: bf(p) = 0 nÕ u lh(p) = rh(p) nót p c© n b» ng bf(p) = 1 nÕ u lh(p) = rh(p) +1 nót p bÞ lÖ ch vÒ tr¸ i bf(p) = -1 nÕ u lh(p) = rh(p) -1 nót p bÞ lÖ ch vÒ ph¶ i -1 1 0 B 0 B 0 1 -1 00 U4 0 U3U2 0 U1 B 0 B B 0 B U8 0 U7U6 0 U5 U10 0 U9 U12 0 U11 A B C H× nh 5.15. Minh häa c¸ c vÞ trÝ cã thÓ thª m nót l¸ vµ o c© y AVL, khi thª m nót l¸ vµ o 1 trong c¸ c vÞ trÝ B th× c© y vÉ n c© n b» ng, khi thª m nót l¸ vµ o 1 trong c¸ c vÞ Kü thuËt lËp tr× nh 119 trÝ U th× c© y sÏ mÊ t c© n b» ng. C¸ c sè trª n c© y lµ chØ sè c© n b» ng cña c¸ c nót tr­íc khi thª m nót III.2. C¸c phÐp to¸n trª n c©y AVL: * Khai b¸o: Ta khai b¸ o c© y AVL víi mçi nót cã thª m tr­êng bf cho biÕ t chØ sè c© n b» ng cña nót ®ã. struct nodetype { int key; int info; int bf; struct nodetype *left, *right; }; typedef struct nodetype *NODEPTR; III.2.1. Thª m nót: - Néi dung: Thª m 1 nót cã khãa x, néi dung a vµ o c© y nhÞ ph© n t× m kiÕ m c© n b» ng sao cho sau khi thª m th× c© y nhÞ ph© n vÉ n lµ c© y nhÞ ph© n t× m kiÕ m c© n b» ng. - Gi¶ i thuË t: & Thª m nót vµ o c© y nh­ b× nh th­êng, nghÜ a lµ nót võa thª m sÏ lµ nót l¸ . & TÝ nh l¹ i chØ sè c© n b» ng cña c¸ c nót cã bÞ ¶ nh h­ëng & KiÓ m tra xem c© y cã bÞ mÊ t c© n b» ng hay kh«ng? NÕ u c© y bÞ mÊ t c© n b» ng th× ta c© n b» ng l¹ i c© y. * Tr­íc hÕ t, ta h·y xÐt xem c¸c tr­êng hîp nµo khi thª m nót lµm c©y bÞ mÊt c©n b»ng. Xem c© y h× nh 5.15, ta nhË n thÊ y: - NÕ u thª m nót vµ o 1 trong 6 vÞ trÝ B trª n c© y th× c© y vÉ n c© n b» ng. - NÕ u thª m nót vµ o 1 trong c¸ c vÞ trÝ U1%U12 trª n c© y th× c© y sÏ mÊ t c© n b» ng. + Thª m c¸ c nót vµ o sau bª n tr¸ i cña nót A (cfA = 1) th× c© y sÏ bÞ mÊ t c© n b» ng v× nót A ®ang bÞ lÖ ch tr¸ i. §ã lµ c¸ c vÞ trÝ U1, U2, U3, U4. + Thª m c¸ c nót vµ o sau bª n ph¶ i cña nót C (cfC = -1) th× c© y sÏ bÞ mÊ t c© n b» ng v× nót C ®ang bÞ lÖ ch ph¶ i. §ã lµ c¸ c vÞ trÝ U9, U10, U11, U12. Tãm l¹ i: Ta cã 2 tr­êng hîp khi thª m nót x vµo c©y AVL lµm c©y mÊt c©n b»ng, ®ã lµ thª m c¸c nót vµo sau bª n tr¸i cña nót cã cf = 1, vµ thª m c¸c nót vµo sau bª n ph¶i cña nót cã cf = -1. Kü thuËt lËp tr× nh 120 * C©n b»ng l¹i c©y: Gäi ya lµ nót tr­íc gÇ n nhÊ t bÞ mÊ t c© n b» ng khi thª m nót x vµ o c© y AVL. Do c¶ 2 tr­êng hîp bÞ mÊ t c© n b» ng khi thª m nót x lµ t­¬ng tù nhau nª n ta chØ xÐt tr­êng hîp bfya=1 vµ nót l¸ thª m vµ o lµ nót sau bª n tr¸ i cña nót ya. 1 0 T3 chieàu cao nT1 chieàu cao n T2 chieàu cao n S ya H× nh 5.16. Nh¸ nh c© y con nót gèc ya tr­íc khi thª m nót. NhË n xÐt: - V× nót ya cã bfya = 1 nª n nót ya ch¾ c ch¾ n cã nót con bª n tr¸ i s víi bfs = 0 - V× ya lµ nót gÇ n nhÊ t cã bf lµ 1 nª n nót s vµ c¸ c nót tr­íc kh¸ c cña nót x (sÏ thª m vµ o) cã bf lµ 0. -§écao (T1) = §écao(T2) = §écao(T3) Tr­êng hîp 1a: NÕ u thª m nót míi x vµ o vÞ trÝ nót sau bª n tr¸ i cña s (thuéc nh¸ nh T1) ta xoay ph¶ i quanh nót ya - Nót s sÏ lµ nót gèc míi cña nh¸ nh c© y nµ y víi bfs = 0 - Nót ya lµ nót con bª n ph¶ i cña s víi bfya = 0. 0 T1 chieàu saâu n 0 T2 chieàu saâu n T3 chieàu saâu n S ya x 2 1 T3 chieàu saâu nT1 chieàu saâu n T2 chieàu saâu n S ya x xoay phaûi quanh nuùt ya H× nh 5.17. Xoay ph¶ i quanh nót ya ®Ó c© n b» ng l¹ i c© y. Kü thuËt lËp tr× nh 121 Tr­êng hîp 1b: NÕ u thª m nót míi x vµ o vÞ trÝ nót sau bª n ph¶ i cña s (thuéc nh¸ nh T2) ta xoay 2 lÇ n (xoay kÐp): xoay tr¸ i quanh nót s vµ xoay ph¶ i quanh nót ya - Nót p sÏ lµ nót gèc míi cña nh¸ nh c© y nµ y víi bfp = 0 - Nót ya lµ nót con bª n ph¶ i cña p víi bfya = -1 - Nót s lµ nót con bª n tr¸ i cña p víi bfs = 0 2 -1 T3 chieàu saâu nT1 chieàu saâu n S ya 1 T2-1 chieàu saâu n-1 T2-2 chieàu saâu n-1 x p C©y AVL sau khi thªm nót x x T2-1 chieàu saâu n-1 2 0 T1 chieàu saâu n S p T2-2 chieàu saâu n-1 T3 chieàu saâu n ya 2 xoay traùi quanh nuùt S Kü thuËt lËp tr× nh 122 xoay phaûi quanh nuùt ya x T2-1 chieàu saâu n-1 0 0 T1 chieàu saâu n S p -1 T2-2 chieàu saâu n-1 T3 chieàu saâu n ya H× nh 5.18. Xoay kÐp (xoay tr¸ i quanh nót s, xoay ph¶ i quanh nót ya) ®Ó c© n b» ng l¹ i c© y. B¶ ng sau ®© y ph© n biÖ t c¸ c tr­êng hîp c© y bÞ mÊ t c© n b» ng khi thª m nót vµ c¸ c phÐp xoay c© y t­¬ng øng ®Ó c© n b» ng l¹ i c© y: Tr­êng hîp Tr­íc khi thª m nót x Sau khi thª m nót x C¸c phÐp xoay c©y vµ chØ sè c©n b»ng míi 1.a bfya = 1 bfs = 0 bfya = 2 bfs = 1 Xoay ph¶i quanh nót ya bfs=0, bf ya = 0 1.b bfya = 1 bfs = 0 bfya = 2 bfs = -1 Xoay kÐp 1. Xoay tr¸ i quanh nót s 2. Xoay ph¶ i quanh nót ya bfs=0, bf ya = -1 2.a bfya = -1 bfs = 0 bfya = -2 bfs = -1 Xoay tr¸i quanh nót ya bfs=0, bf ya = 0 2.b bfya = -1 bfs = 0 bfya = -2 bfs = 1 Xoay kÐp 1. Xoay ph¶ i quanh nót s 2. Xoay tr¸ i quanh nót ya bfs=0, bf ya = 1 - Gi¶ i thuË t: ! PhÐp xoay tr¸ i (Rotate_Left): xoay tr¸ i c© y nhÞ ph© n t× m kiÕ m cã nót gèc lµ root, yª u cÇ u root ph¶ i cã nót con bª n ph¶ i (gäi lµ nót p). Sau khi xoay tr¸ i th× nót p trë thµ nh nót gèc, nót gèc cò trë thµ nh nót con bª n tr¸ i cña nót gèc míi. PhÐp xoay tr¸ i tr¶ vÒ con trá chØ nót gèc míi. Kü thuËt lËp tr× nh 123 NODEPTR Rotate_Left(NODEPTR root) { NODEPTR p; if(root == NULL) printf("Khong the xoay trai vi cay bi rong."); else if(root->right == NULL) printf("Khong the xoay trai vi khong co nut con ben phai."); else { p = root->right; root->right = p->left; p->left = root; } return p; } ! PhÐp xoay ph¶ i (Rotate_Right): xoay ph¶ i c© y nhÞ ph© n t× m kiÕ m cã nót gèc lµ root, yª u cÇ u root ph¶ i cã nót con bª n tr¸ i (gäi lµ nót p). Sau khi xoay ph¶ i th× nót p trë thµ nh nót gèc, nót gèc cò trë thµ nh nót con bª n ph¶ i cña nót gèc míi. PhÐp xoay ph¶ i tr¶ vÒ con trá chØ nót gèc míi. NODEPTR Rotate_Right(NODEPTR root) { NODEPTR p; if(root == NULL) printf("Khong the xoay phai vi cay bi rong."); else if(root->left == NULL) printf("Khong the xoay phai vi khong co nut con ben trai."); else { p = root->left; root->left = p->right; p->right = root; } return p; } Kü thuËt lËp tr× nh 124 !Thª m nót (Insert): thª m nót cã khãa x, néi dung a vµ o c© y AVL: - Thª m nót theo gi¶ i thuË t thª m nót vµ o c© y nhÞ ph© n t× m kiÕ m . - C© n b» ng l¹ i c© y b» ng c¸ ch xoay ®¬n hay xoay kÐp void Insert(NODEPTR &pavltree, int x, int a) { NODEPTR fp, p, q, // fp lµ nót cha cña p, q lµ con cña p fya, ya, /* ya lµ nót tr­íc gÇ n nhÊ t cã thÓ mÊ t c© n b» ng fya lµ nót cha cña ya */ s; // s lµ nót con cña ya theo h­íng mÊ t c© n b» ng int imbal; /* imbal = 1 nÕ u bÞ lÖ ch vÒ nh¸ nh tr¸ i = -1 nÕ u bÞ lÖ ch vÒ nh¸ nh ph¶ i */ // Khëi ®éng c¸ c gi¸ trÞ fp = NULL; p = pavltree; fya = NULL; ya = p; // tim nut fp, ya va fya, nut moi them vao la nut la con cua nut fp while(p != NULL) { if(x == p->info) // bi trung noi dung return; if (x info) q = p->left; else q = p->right; if(q != NULL) if(q->bf != 0) // truong hop chi so can bang cua q la 1 hay -1 { fya = p; ya = q; } fp = p; p = q; } // Them nut moi (nut la) la con cua nut fp q = New_Node(); // cÊ p ph¸ t vïng nhí q->key =x; q->info = a; q->bf = 0; q->left = NULL; Kü thuËt lËp tr× nh 125 q->right = NULL; if(x info) fp->left = q; else fp->right = q; /* Hieu chinh chi so can bang cua tat ca cac nut giua ya va q, neu bi lech ve phia trai thi chi so can bang cua tat ca cac nut giua ya va q deu la 1, neu bi lech ve phia phai thi chi so can bang cua tat ca cac nut giua ya va q deu la -1 */ if(x info) p = ya->left; else p = ya->right; s = p; // s la con nut ya while(p != q) { if(x info) { p->bf = 1; p = p->left; } else { p->bf = -1; p = p->right; } } // xac dinh huong lech if(x info) imbal = 1; else imbal = -1; if(ya->bf == 0) { ya->bf = imbal; return; } if(ya->bf != imbal) { Kü thuËt lËp tr× nh 126 ya->bf = 0; return; } if(s->bf == imbal) // Truong hop xoay don { if(imbal == 1) // xoay phai p = Rotate_Right(ya); else // xoay trai p = Rotate_Left(ya); ya->bf = 0; s->bf = 0; } else // Truong hop xoay kep { if(imbal == 1) // xoay kep trai-phai { ya->left = Rotate_Left(s); p = Rotate_Right(ya); } else // xoay kep phai-trai - { ya->right = Rotate_Right(s); p = Rotate_Left(ya); } if(p->bf == 0) // truong hop p la nut moi them vao { ya->bf = 0; s->bf = 0; } else if(p->bf == imbal) { ya->bf = -imbal; s->bf = 0; } else { ya->bf = 0; s->bf = imbal; } Kü thuËt lËp tr× nh 127 p->bf = 0; } if(fya == NULL) pavltree = p; else if(ya == fya->right) fya->right = p; else fya->left = p; } * §Ó t¹ o c© y nhÞ ph© n t× m kiÕ m c© n b» ng, ta sö dông gi¶ i thuË t sau: void Create_AVLTree(NODEPTR &root) { int khoa, noidung; char so[10]; NODEPTR p; do { printf("Nhap khoa :"); gets(so) ; khoa = atoi(so); if (khoa !=0) { printf("Nhap noi dung :"); gets(so) ; noidung = atoi(so); if (root==NULL) { p = New_Node(); p->key = khoa; p->info = noidung; p->bf = 0 ; p->left = NULL; p->right = NULL; root =p; } else Insert(root,khoa,noidung); } } while (khoa!=0); // khãa =0 th× dõng nhË p } Ghi chó : §Ó t¹ o c© y nhÞ ph© n do biÕ n tree qu¶ n lý, ta gäi: Create_AVLTree(tree); Kü thuËt lËp tr× nh 128 III.2.2. CËp nhËt c©y: 1. T× m kiÕ m (Search): T× m nót cã khãa b» ng x trª n c© y nhÞ ph© n AVL cã gèc lµ root. NÕ u t× m thÊ y x trong c© y th× tr¶ vÒ ®Þa chØ cña nót cã trÞ b» ng x trongc© y, nÕ u kh«ng cã th× tr¶ vÒ trÞ NULL. Do AVL lµ c© y nhÞ ph© n BST nª n ta cã thÓ t× m kiÕ m nhanh b» ng ph­¬ng ph¸ p t× m kiÕ m nhÞ ph© n, vµ do tÝ nh chÊ t lóc nµ y c© y c© n b» ng nª n thêi gian t× m kiÕ m sÏ nhanh h¬n rÊ t nhiÒ u. NODEPTR search(NODEPTR root, int x) { NODEPTR p; p = root; while(p != NULL && x!=p->key) if(x key) p = p->left; else p = p->right; return(p); } 2. Xãa nót: Remove(root, x): - Néi dung: xãa nót cã khãa x trª n c© y AVL víi ®Þa chØ sao ®Ç u root sao cho sau khi xãa th× c© y vÉ n lµ AVL. - Gi¶ i thuË t: NÕ u root == NULL th× Th«ngb¸ o ("Kh«ng thÓ xãa ®­îc nót x trª n c© y") NÕ u root != NULL th× NÕ u xinfo th× : + Gäi ®Ö qui ®Ó xãa nót x ë nh¸ nh bª n tr¸ i cña root : Remove(root->left, x) + Gäi balance_left ®Ó c© n b» ng l¹ i c© y nót gèc root nÕ u nh¸ nh c© y con bª n tr¸ i bÞ gi¶ m ®é cao. NÕ u x > root->info th× : + Gäi ®Ö qui ®Ó xãa nót x ë nh¸ nh bª n ph¶ i cña root : Remove(root->right, x) + Gäi balance_right ®Ó c© n b» ng l¹ i c© y nót gèc root nÕ u nh¸ nh c© y con bª n ph¶ i bÞ gi¶ m ®é cao. NÕ u x==root->info th× : Xãa nót root nh­ phÐp to¸ n xãa trª n c© y nhÞ ph© n BST. - Ch­¬ng tr× nh : tù cµ i ®Æ t. Kü thuËt lËp tr× nh 129 III.2.3. C¸c phÐp duyÖ t c©y: Do c© y AVL còng lµ c© y nhÞ ph© n nª n ta sÏ ¸ p dông l¹ i c¸ c ph­¬ng ph¸ p duyÖ t Preorder, Inorder vµ Postorder vµ o c© y AVL. a. DuyÖ t c©y theo thø tù NLR (Preorder): void Preorder (NODEPTR root) { if(root != NULL) { printf("%d ", root->info); Preorder(root->left); Preorder (root->right); } } b. DuyÖ t c©y theo thø tù LNR (Inorder): void Inorder(NODEPTR root) { if(root != NULL) { Inorder(root->left); printf("%d ", root->info); Inorder(root->right); } } c. DuyÖ t c©y theo thø tù LRN (Posorder): void Posorder(NODEPTR root) { if(root != NULL) { Posorder(root->left); Posorder(root->right); printf("%d ", root->info); } } Kü thuËt lËp tr× nh 130 Bµi tËp: 1. ViÕ t l¹ i c¸ c ch­¬ng tr× nh duyÖ t c© y nhÞ ph© n theo ph­¬ng ph¸ p kh«ng ®Ö qui. 2. ViÕ t ch­¬ng tr× nh t¹ o mét menu thùc hiÖ n c¸ c môc sau: a. T¹ o c© y nhÞ ph© n t× m kiÕ m víi néi dung lµ sè nguyª n (kh«ng trïng nhau). b. LiÖ t kª c© y nhÞ ph© n ra mµ n h× nh theo thø tù NLR c. §Õ m tæng sè nót, sè nót l¸ , vµ sè nót trung gian cña c© y. d. TÝ nh ®é cao cña c© y. e. Lo¹ i bá nót cã néi dung lµ x trong c© y nhÞ ph© n BST. f. Thª m nót cã néi dung x vµ o c© y nhÞ ph© n BST sao cho sau khi thª m th× c© y vÉ n lµ BST. 3. Cho mét c© y nhÞ ph© n tree, h∙ y viÕ t ch­¬ng tr× nh ®Ó sao chÐp nã thµ nh mét c© y míi tree2, víi khãa, néi dung, vµ liª n kÕ t gièng nh­ c© y tree. 4. ViÕ t c¸ c hµ m kiÓ m tra xem c© y nhÞ ph© n: a. Cã ph¶ i lµ c© y nhÞ ph© n ®óng kh«ng. b. Cã ph¶ i lµ c© y nhÞ ph© n ®Ç y kh«ng. 5. ViÕ t hµ m kiÓ m tra nót x vµ y cã trª n c© y hay kh«ng, nÕ u cã c¶ x lÉ n y trª n c© y th× x¸ c ®Þnh nót gèc cña c© y con nhá nhÊ t cã chøa x vµ y. 6. Cho mét c© y biÓ u thøc, h∙ y viÕ t hµ m Calculate (NODEPTR root) ®Ó tÝ nh gi¸ trÞ cña c© y biÓ u thøc ®ã, biÕ t r» ng c¸ c to¸ n tö ®­îc dïng trong biÓ u thøc lµ : + - * / ^ % ! 7. VÏ l¹ i h× nh ¶ nh c© y nhÞ ph© n t× m kiÕ m, c© y nhÞ ph© n t× m kiÕ m c© n b» ng nÕ u c¸ c nót thª m vµ o c© y theo thø tù nh­ sau: 8 3 5 2 20 11 30 9 18 4 8. NhË p vµ o 1 biÓ u thøc sè häc, chuyÓ n biÓ u thøc ®ã thµ nh c© y nhÞ ph© n, nót gèc lµ to¸ n tö, nót l¸ lµ c¸ c to¸ n h¹ ng, biÕ t r» ng c¸ c to¸ n tö ®­îc dïng trong biÓ u thøc lµ : + - * / ^ % ! Kü thuËt lËp tr× nh 131 MôC LôC CH¦¥NG i §¹I C¦¥NG VÒ LËP TR×NH--------------------------------------------------- 1 I. Kh¸i niÖm thuËt to¸n--------------------------------------------------------------------------- 1 I.1. Kh¸i niÖm --------------------------------------------------------------------------------------------------- 1 I.2. C¸c tÝ nh chÊ t ®Æc tr­ng cña thuË t to¸n ----------------------------------------------------- 1 I.3. Ph©n lo¹ i ----------------------------------------------------------------------------------------------------- 1 II. M« t¶ thuËt to¸n b»ng l­u ®å ---------------------------------------------------- 1 II.1. L­u ®å ------------------------------------------------------------------------------------------------------ 1 II.2. C¸c ký hiÖu trªn l­u ®å --------------------------------------------------------------------------- 1 II.3. Mét sè vÝ dô biÓu diÔn thuË t to¸n b»ng l­u ®å---------------------------------------- 2 III. C¸C NG«N NG÷ LËP TR×NH & CH­¬NG TR×NH DÞCH -------------------- 5 III.1. Ng«n ng÷ lËp tr× nh ---------------------------------------------------------------------------------- 5 III.2. Ch­¬ng tr× nh dÞch------------------------------------------------------------------------------------ 6 CH­¬NG 2 LµM QUEN VíI NG«N NG÷ C--------------------------------------------- 7 * Giíi thiÖu ng«n ng÷ C ------------------------------------------------------------------------- 7 I. C¸C KH¸I NIÖM C¬ B¶N---------------------------------------------------------------------------- 7 I.1. CÊu tróc c¬ b¶n cña mét ch­¬ng tr× nh C -------------------------------------------------- 7 I.2. KiÓu d÷ liÖu c¬ b¶n---------------------------------------------------------------------------------- 13 I.3. BiÕn----------------------------------------------------------------------------------------------------------- 14 I.4 H»ng----------------------------------------------------------------------------------------------------------- 18 I.5. PhÐp to¸n -------------------------------------------------------------------------------------------------- 20 * Sù chuyÓn kiÓu----------------------------------------------------------------------------------------- 29 * Møc ®é ­u tiªn cña c¸ c phÐp to¸n---------------------------------------------------------- 29 I.6. Chuçi--------------------------------------------------------------------------------------------------------- 30 II. C¸c cÊu tróc ®iÒu khiÓn trong C ---------------------------------------------- 33 II.1 CÊu tróc tuÇn tù (Sequence) ------------------------------------------------------------------ 33 II.2. CÊu tróc chän------------------------------------------------------------------------------------------ 34 II.2.1. LÖnh if else -------------------------------------------------------------------------------------- 34 II.2.2. LÖnh switch_case ---------------------------------------------------------------------------- 35 II.3. CÊu tróc lÆp --------------------------------------------------------------------------------------------- 37 II.3.1. LÖnh while --------------------------------------------------------------------------------------- 37 II.3.2. LÖnh do while ---------------------------------------------------------------------------------- 38 II.3.3. LÖnh for-------------------------------------------------------------------------------------------- 39 * Ph¸t biÓu break, continue, goto -------------------------------------------------------------- 40 Bµ i tËp ---------------------------------------------------------------------------------------------------------------- 41 Kü thuËt lËp tr× nh 132 III. Hµm - §Ö quy ------------------------------------------------------------------------------------------ 45 III.1. Hµm-------------------------------------------------------------------------------------------------------- 45 III.2. §Ö qui (Recursion)-------------------------------------------------------------------------------- 52 IV. Structure----------------------------------------------------------------------------------------------- 54 IV.1. §Þnh nghÜ a------------------------------------------------------------------------------------ 55 IV.2. Khai b¸o--------------------------------------------------------------------------------------- 55 V. FILE---------------------------------------------------------------------------------------------------------------- 56 V.1. File v¨ n b¶n--------------------------------------------------------------------------------------------- 56 V.2. File nhÞ ph©n (file cã cÊu tróc) -------------------------------------------------------------- 61 V.3. Ph¸t hiÖn lçi khi truy xuÊ t tËp tin ---------------------------------------------------------- 66 Bµ i tËp ---------------------------------------------------------------------------------------------------------------- 67 CH­¬NG 3. C¸C THUËT TO¸N TR£N CÊU TRóC D÷ LIÖU M¶NG 69 I. M¶ng kh«ng s¾p xÕp vµ thuËt to¸n t×m kiÕm ------------------ 69 trªn m¶ng ch­a cã thø tù I.1. Mét sè kh¸i niÖm vÒ m¶ng ---------------------------------------------------------------------- 69 I.2. ThuËt to¸n t× m kiÕm trªn m¶ng ch­a cã thø tù -------------------------------------- 71 II. C¸c thuËt to¸n s¾p xÕp ------------------------------------------------------------------- 73 II.1. S¾p xÕp theo ph­¬ng ph¸p Bubble_Sort ------------------------------------------------ 73 II.2. S¾p xÕp theo ph­¬ng ph¸p Quick_Sort-------------------------------------------------- 75 III. T×m kiÕm trªn m¶ng ®· cã thø tù --------------------------------------------- 79 III.1. T× m kiÕm nhanh b»ng ph­¬ng ph¸p lÆp----------------------------------------------- 79 III.2. PhÐp t× m kiÕm nhÞ ph©n ------------------------------------------------------------------------ 80 III.3. PhÐp t× m kiÕm nhÞ ph©n ®Ö qui ------------------------------------------------------------- 81 Bµ i tËp ---------------------------------------------------------------------------------------------------------------- 82 CH¦¥NG 4 CON TRá (POINTER) ---------------------------------------------------------- 84 I. §ÞNH NGHÜA ------------------------------------------------------------------------------------------------- 84 I.1. Khai b¸o---------------------------------------------------------------------------------------------------- 84 I.2. TruyÒn ®Þa chØ cho hµm --------------------------------------------------------------------------- 85 II C¸c phÐp to¸n trªn biÕn con trá ----------------------------------------------- 85 II.1. To¸n tö ®Þa chØ &----------------------------------------------------------------------------------- 85 II.2. To¸n tö néi dung * --------------------------------------------------------------------------------- 85 II.3. PhÐp céng trõ biÕn con trá víi mét sè nguyªn-------------------------------------- 86 II.4. PhÐp g¸n vµ phÐp so s¸ nh----------------------------------------------------------------------- 86 II.5. Sù chuyÓn kiÓu---------------------------------------------------------------------------------------- 86 II.6. Khai b¸o mét con trá h»ng vµ con trá chØ ®Õn ®èi t­îng h»ng ------------ 87 III. Sù t­¬ng quan gi÷a con trá vµ m¶ng----------------------------------- 87 Kü thuËt lËp tr× nh 133 IV. Con trá vµ chuçi-------------------------------------------------------------------------------- 91 IV.1. Khai b¸o------------------------------------------------------------------------------------------------- 91 IV.2. XÐt mét sè vÝ dô vÒ c¸ c hµm xö lý chuçi--------------------------------------------- 91 IV.3. M¶ng con trá chØ ®Õn chuçi------------------------------------------------------------------ 93 Bµ i tËp ---------------------------------------------------------------------------------------------------------------- 95 CH¦¥NG 5 C¸C THUËT TO¸N TR£N CÊU TRóC --------------------------- 96 DANH S¸CH LI£N KÕT (LINKED LIST). I. Kh¸i niÖm---------------------------------------------------------------------------------------------------------------- 96 II. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt----------------------------------- 97 II.1. T¹o danh s¸ ch ----------------------------------------------------------------------------------------- 97 II.2. CËp nhËt danh s¸ ch--------------------------------------------------------------------------------- 99 II.3. DuyÖt danh s¸ ch------------------------------------------------------------------------------------100 II.4. T× m kiÕm-----------------------------------------------------------------------------------------------100 II.5. S¾p xÕp --------------------------------------------------------------------------------------------------101 Bµ i tËp --------------------------------------------------------------------------------------------------------------102 CH­¬NG 6 c¸c thuËt to¸n trªn cÊu tróc c©Y---------------------104 I. Ph©n lo¹i c©y----------------------------------------------------------------------------------------104 I.1. Mét sè kh¸i niÖm c¬ b¶n -----------------------------------------------------------------------104 I.2. C¸ch biÓu diÔn c©y ---------------------------------------------------------------------------------106 I.3. BiÓu diÔn thø tù c¸c nót trong c©y---------------------------------------------------------106 II. C©y nhÞ ph©n (Binary tree)----------------------------------------------------------107 II.1. §Þnh nghÜ a---------------------------------------------------------------------------------------------107 II.2. C¸c phÐp to¸n trªn c©y nhÞ ph©n----------------------------------------------------------110 1. T¹o c©y--------------------------------------------------------------------------------------------------110 2. CËp nhËt c©y -----------------------------------------------------------------------------------------112 3. C¸c phÐp duyÖ t c©y ------------------------------------------------------------------------------116 III. c©y nhÞ ph©n T×M KIÕM c©n b»ng (AVL) --------------------------------117 III.1. §Þnh nghÜ a-------------------------------------------------------------------------------------------117 III.2. C¸c phÐp to¸n trªn c©y AVL --------------------------------------------------------------118 III.2.1. Thªm nót---------------------------------------------------------------------------------------118 III.2.2. CËp nhËt c©y---------------------------------------------------------------------------------126 III.2.3. C¸c phÐp duyÖt c©y----------------------------------------------------------------------127 Bµ i tËp --------------------------------------------------------------------------------------------------------------129 TµI LIÖU THAM KH¶O 1. Kü thuË t lË p tr× nh Turbo C §ç Phóc, NguyÔ n Phi Khö, 1992 T¹ Minh Ch© u, NguyÔ n §× nh Tª 2. CÊ u tróc d÷ liÖ u – øng dông NguyÔ n Hång Ch­¬ng 1999 vµ cµ i ®Æ t b» ng C 3. Nh÷ng viª n ngäc Kü thuË t JohnBentley lË p tr× nh