May 12, 2012

Danh sách liên kết (Linked List)

Ngộ nhận ra bài này mình viết code rất dở, để khi nào rảnh sẽ edit lại. Danh sách liên kết có những ứng dụng rất thú vị

Hôm nay Kỹ Thuật Lập Trình được học danh sách liên kết, vì ở dưới chăm chú sửa cái code thực hành mà không bắt kịp vấn đề, dù những định nghĩa căn bản đều hiểu. Cần phải tìm hiểu nó một cách cụ thể.

1.Khái niệm: Danh sách liên kết (linked list) là một cấu trúc dữ liệu bao gồm một nhóm các nút (nodes) tao thành một chuỗi.  Thông thường mỗi nút gồm dữ liệu (data) ở nút đó và tham chiếu (reference) đến nút kế tiếp trong chuỗi.
Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến nhất.
(Nguồn: Wikipedia)
clip_image001
Ưu điểm:
  • Cung cấp giải pháp để chứa cấu trúc dữ liệu tuyến tính.
  • Dễ dàng thêm hoặc xóa các phần tử trong danh sách mà không cần phải cấp phát hoặc tổ chức lại trật tự của mảng.
  • Cấp phát bộ nhớ động
Nhược điểm:
  • Một danh sách liên kết đơn giản không cho phép truy cập ngẫu nhiên dữ liệu.
  • Chính vì lí do trên mà một số phép tính như tìm phần tử cuối cùng, xóa phần tử ngẫu nhiên hay chèn thêm, tìm kiếm có thể phải duyệt tất cả các phần tử.
Phân loại:
  • Danh sách tuyến tính (Linear list):
clip_image002
  • Danh sách vòng (circular list):
clip_image003
  • Danh sách liên kết đôi (Double list):
clip_image004
Cấu trúc:
clip_image005
Data: Thành phần chứa một hay nhiều biến dữ liệu.
Next ptr: Tham chiếu trỏ đến phần tử kế tiếp trong cấu trúc.
Head: biến tham chiếu trỏ đến phần tử đầu tiên của danh sách.
clip_image006

Struct LLnode {
DataType Data;
LLnode* next;
};
 
2.Các phép toán:
Cho cấu trúc đơn giản:
struct LLintNode {
int Data;
struct LLintNode* Next;
};
Đếm số phần tử của Linked List:
Duyệt từng phần tử rồi đếm, cho đến khi nào gặp phần tử cuối.

 
int LengthLL(LLNode* head) {
int length = 0;
while (head != NULL) {
++length;
head = head ->Next;
}
return length;
}
Thêm một phần tử vào cuối linked list:
Nếu danh sách rỗng, thêm nút vào head.
Ngược lại, tìm phần tử cuối cùng của danh sách rồi thêm nút mới vào Next của nút cuối cùng đó:

 
void AddLast(LLNode** head, int data) {
LLNode** tmp = head;
 
LLNode* NewNode;
NewNode = (LLNode*) malloc(sizeof(LLNode));
NewNode->Data = data;
NewNode->Next = NULL;
 
if ((*tmp) == NULL) {
(*tmp) = NewNode;
} else {
while ((*tmp)->Next !=NULL) {
tmp = &((*tmp)->Next);
}
(*tmp)->Next = NewNode;
}
}
 
Xóa phần tử cuối cùng:
Tìm phần tử cuối cùng của danh sách, rồi gán bằng NULL.

 
void RemoveLast(LLNode** head) {
    LLNode** tmp = head;
    if ((*tmp) !=NULL) {
        while ((*tmp)->Next != NULL) {
            tmp = &((*tmp)->Next);
        }
    }
    (*tmp) = NULL;
 
}
Thêm phần tử vào đầu danh sách:
clip_image007

 


void AddFirst(LLNode** head, int Data) {
    LLNode** tmp = head;
    LLNode* NewNode;
    
    NewNode = (LLNode*) malloc(sizeof(LLNode));
    NewNode->Data = Data;
    NewNode->Next = (*head);
    
    (*tmp) = NewNode;
 
}
Xóa phần tử đầu tiên:
Nếu danh sách khác rỗng, đưa phần tử Next lên phía trước.

 
void RemoveFirst(LLNode** head) {
    LLNode** tmp = head;
    if ((*tmp) != NULL) {
        (*tmp) = (*tmp)->Next;
    }
}
Tìm kiếm phần tử trong danh sách:

 
LLNode* FindNode(LLNode** head,LLNode* src) {
    LLNode** tmp = head;
    while ( src->Data != (*tmp)->Data) {
        tmp = &((*tmp)->Next);
    }
    return (*tmp);
 
}
Chèn thêm 1 phần tử sau phần tử currrent:

 
int InsertNode(LLNode** head, LLNode* current, LLNode* NewNode) {
    LLNode** tmp = head;
    while ((current != (*tmp)) && (*tmp != NULL)) {
        tmp = &((*tmp)->Next);
    }
    
    if (*tmp == NULL) {
        return 0;
    } else {
        NewNode->Next= current->Next;
        current->Next = NewNode;
        
        (*tmp) = current;
        return 1;
    }
        
 
}
Xóa phần tử bất kì biết trước dữ liệu:

int RemoveNode(LLNode** head, LLNode* current) {
    LLNode** tmp = head;
    while ((current != (*tmp)) && (*tmp != NULL)) {
        tmp = &((*tmp)->Next);
    }
    if (*tmp == NULL) {
        return 0;
    } else {
        (*tmp) = (*tmp)->Next;
        return 1;
    }
}
3.Tham khảo:
Nhãn: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)