C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
1
N I DUNGỘ
DANH SÁCH LIÊN K T Đ N (LIST)Ế Ơ
C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
2
T Ch c C a DSLK Đ nổ ứ ủ ơ
Mi ph n t liên k t v i ph n t đ ng li n sau trong ỗ ầ ử ế ớ ầ ử ứ ề
danh sách
M i ph n t trong danh sách liên k t đ n là m t c u ỗ ầ ử ế ơ ộ ấ
trúc có hai thành ph nầ
Thành ph n d li uầ ữ ệ : L u tr thông tin v b n thân ư ữ ề ả
ph n tầ ử
Thành ph n liên k tầ ế : L u đ a ch ph n t đ ng ư ị ỉ ầ ử ứ
sau trong danh sách ho c b ng NULL n u là ph n ặ ằ ế ầ
t cu i danh sách.ử ố
x0 x1
x2
x3
C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
3
CTDL c a DSLK đ nủ ơ
Cu trúc d li u c a 1 nút trong List đ nấ ữ ệ ủ ơ
typedef struct tagNode
{ Data Info; // L u thông tin b n thânư ả
struct tagNode *pNext; //L u đ a ch c a Node đ ng sauư ị ỉ ủ ứ
}Node;
Cu trúc d li u c a DSLK đ nấ ữ ệ ủ ơ
typedef struct tagList
{Node *pHead;//L u đ a ch Node đ u tiên trong Listư ị ỉ ầ
Node *pTail; //L u đ a ch c a Node cu i cùng trong Listư ị ỉ ủ ố
}LIST;// ki u danh sách liên k t đ nể ế ơ
Info
pNext
C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
4
Ví d t ch c DSLK đ n trong b nhụ ổ ứ ơ ộ ớ
4f4
3f
NULL65f7
4f 5f
pHead pTail
Trong ví d trên thành ph n d li u là 1 s nguyênụ ầ ữ ệ ố
C U TRÚC D LI U VÀ GI I THU TẤ Ữ Ệ Ả Ậ
5
Các thao tác c b n trên DSLK đ nơ ả ơ
T o 1 danh sách liên k t đ n r ngạ ế ơ ỗ
T o 1 nút có tr ng Infor b ng xạ ườ ằ
Tìm m t ph n t có Info b ng xộ ầ ử ằ
Thêm m t ph n t có khóa x vào danh sáchộ ầ ử
H y m t ph n t trong danh sáchủ ộ ầ ử
Duy t danh sáchệ
S p x p danh sách liên k t đ nắ ế ế ơ