Kỹ thuật lập trình - Chương 5

Tài liệu tham khảo giáo trình kỹ thuật lập trình gồm 6 chương - Chương 5 Các thuật toán trên cấu trúc danh sách liên kết (LINKED LIST)
Nội dung trích xuất từ tài liệu:
Kỹ thuật lập trình - Chương 5 97Kü thuË t lË p tr× nhCH¦¥NG 5 C¸C THUËT TO¸N TR£N CÊU TRóC DANH S¸CH LI£N KÕT (LINKED LIST)I. Kh¸i niÖm: CÊ u tróc danh s¸ ch liª n kÕ t lµ cÊ u tróc ®éng, viÖ c cÊ p ph¸ t nót vµ gi¶ iphãng nót trª n danh s¸ ch x¶ y ra khi ch ¬ng tr× nh ®ang ch¹ y. Ta th êng cÊ p ph¸ tnót cho danh s¸ ch liª n kÕ t b» ng biÕ n ®éng. C¸ c phÇ n tö sÏ ® îc cÊ p ph¸ t vïng nhí trong qu¸ tr× nh thùc thi ch ¬ngtr× nh, do ®ã chóng cã thÓ n» m r¶ i r¸ c ë nhiÒ u n¬i kh¸ c nhau trong bé nhí (kh«ngliª n tôc) . First • • • • • 3 Nil •First 1 • 2 • 4 C¸ c phÇ n tö trong danh s¸ ch ® îc kÕ t nèi víi nhau theo chïm liª n kÕ t nhh× nh trª n: - First lµ con trá chØ ®Õ n phÇ n tö ®Ç u cña danh s¸ ch liª n kÕ t - PhÇ n tö cuèi cña danh s¸ ch liª n kÕ t víi vïng liª n kÕ t cã gi¸ trÞ NULL -Mçi nót cña danh s¸ ch cã tr êng info chøa néi dung cña nót vµ tr êngnext lµ con trá chØ ®Õ n nót kÕ tiÕ p trong danh s¸ ch.* L u ý : - CÊ u tróc danh s¸ ch liª n kÕ t lµ cÊ u tróc ®éng, c¸ c nót ® îc cÊ p ph¸ t hoÆ cbÞ gi¶ i phãng khi ch ¬ng tr× nh ®ang ch¹ y. - Danh s¸ ch liª n kÕ t rÊ t thÝ ch hîp khi thùc hiÖ n c¸ c phÐp to¸ n trª n danhs¸ ch th êng bÞ biÕ n ®éng. Trong tr êng hîp xãa hay thª m phÇ n tö trong danhs¸ ch liª n kÕ t th× ta kh«ng dêi c¸ c phÇ n tö ®i nh trong m¶ ng mµ chØ viÖ c hiÖ uchØ nh l¹ i tr êng next t¹ i c¸ c nót ®ang thao t¸ c. Thêi gian thùc hiÖ n c¸ c phÐp to¸ nthª m vµ o vµ lo¹ i bá kh«ng phô thuéc vµ o sè phÇ n tö cña danh s¸ ch liª n kÕ t. 98Kü thuË t lË p tr× nh - Tuy nhiª n, danh s¸ ch liª n kÕ t còng cã c¸ c ®iÓ m h¹ n chÕ sau: + V× mçi nót cña danh s¸ ch liª n kÕ t ph¶ i chøa thª m tr êng next nª n danhs¸ ch liª n kÕ t ph¶ i tèn thª m bé nhí. + T× m kiÕ m trª n danh s¸ ch liª n kÕ t kh«ng nhanh v× ta chØ ® îc truy xuÊ ttuÇ n tù tõ ®Ç u danh s¸ ch. & Khai b¸ o : Mét phÇ n tö cña danh s¸ ch liª n kÕ t Ý t nhÊ t ph¶ i cã hai thµ nhphÇ n : néi dung cña phÇ n tö (info) vµ thµ nh phÇ n next liª n kÕ t phÇ n tö nµ y víiphÇ n tö kh¸ c. Gi¶ sö ta khai b¸ o kiÓ u NODEPTR lµ kiÓ u con trá chØ ®Õ n nót trong 1 danhs¸ ch liª n kÕ t, mçi phÇ n tö cã 2 thµ nh phÇ n : info (int) vµ next . struct node { int info ; struct node *next ; }; typedef struct node *NODEPTR; - §Ó khai b¸ o biÕ n First qu¶ n lý danh s¸ ch liª n kÕ t ta viÕ t nh sau: NODEPTR First; - Khëi t¹ o danh s¸ ch liª n kÕ t : First = NULL; - Ghi chó : Thµ nh phÇ n chøa néi dung cã thÓ gåm nhiÒ u vïng víi c¸ c kiÓ u d÷ liÖ u kh¸ c nhau. Thµ nh phÇ n liª n kÕ t còng cã thÓ nhiÒ u h¬n mét nÕ u lµ danh s¸ ch ®a liª n kÕ t hoÆ c danh s¸ ch liª n kÕ t kÐp. First lµ con trá trá ®Õ n phÇ n tö ®Ç u tiª n cña danh s¸ ch liª n kÕ t, nã cã thÓ lµ kiÓ u con trá (nh khai b¸ o trª n), vµ còng cã thÓ lµ mét struct cã hai thµ nh phÇ n: First trá ®Õ n phÇ n tö ®Ç u tiª n cña danh s¸ ch liª n kÕ t, vµ Last trá ®Õ n phÇ n tö cuèi cña danh s¸ ch liª n kÕ t. struct Linked_List; { First NODEPTR; Last NODEPTR; };II. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt: 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ª nkÕ 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) { 99Kü thuË t lË p tr× nh 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ª nkÕ 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Ê pph¸ 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µ mmalloc 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): ...