Kỹ thuật lập trì nh
97
CHƯƠ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ả i
phóng nút trê n danh sá ch xả y ra khi chương trì nh đang chạy. Ta thường cấ p phá t
nút cho danh sá ch liê n kế t bằ ng biế n động.
Cá c phầ n tử sẽ đ ược cấ p phá t vùng nhớ trong quá trì nh thực thi chương
trì nh, do đó chú ng có thể nằ m rả i rá c ở nhiề u nơi khá c nhau trong bộ nhớ (không
liê n tục) .

















First
1

2



















4

sá ch thường bị biế n động. Trong trường hợp xóa hay thê m phầ n tử trong danh
sá ch liê n kế t thì ta không dời cá c phầ n tử đi như trong mả ng mà chỉ việ c hiệ u
chỉ nh lạ i trường next tạ i cá c nút đang thao tác. Thời gian thực hiệ n cá c phép toá n
thê m và o và loạ i bỏ không phụ thuộc và o số phầ n tử của danh sá ch liê n kế t.
Nil
First

Kỹ thuật lập trì nh
98
- Tuy nhiê n, danh sá ch liê n kế t cũng có cá c điể m hạ n chế sau:
+ Vì mỗi nút của danh sá ch liê n kế t phả i chứa thê m trường next nê n danh
sá ch liê n kế t phả i tốn thê m bộ nhớ.
+ Tì m kiế m trê n danh sá ch liê n kế t không nhanh vì ta chỉ được truy xuấ t
tuầ n tự từ đầ u danh sá ch.
& Khai bá o
: Một phầ n tử của danh sá ch liê n kế t í t nhấ t phả i có hai thà nh
phầ n : nội dung của phầ n tử (info) và thà nh phầ n next liê n kế t phầ n tử nà y với
phầ n tử khá c.
Giả sử ta khai bá o kiể u NODEPTR là kiể u con trỏ chỉ đế n nút trong 1 danh
sá ch liê n kế t, mỗi phầ n tử có 2 thà nh phầ n : info (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ú
:

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;

{
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)