Giáo trình môn Kỹ thuật 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