Thứ Tư, 27 tháng 3, 2019

Home » » Danh sách liên kết đơn

Danh sách liên kết đơn

Không có nhận xét nào
1. Danh sách liên kết đơn
Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa “một giá trị”(Data) và “một con trỏ”(Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của linked list.
Hình ảnh mô tả cho một Node trong danh sách liên kết đơn:
Node trong danh sách liên kết
Và đây là hình ảnh mô phỏng một danh sách liên đơn kết đầy đủ:


Danh sách liên kết là gì?

2. Các loại Danh sách liên kết (Linked List)

Dưới đây là các loại Danh sách liên kết (Linked List) đa dạng:
  • Danh sách liên kết đơn (Simple Linked List): chỉ duyệt các phần tử theo chiều về trước.
  • Danh sách liên kết đôi (Doubly Linked List): các phần tử có thể được duyệt theo chiều về trước hoặc về sau.
  • Danh sách liên kết vòng (Circular Linked List): phần tử cuối cùng chứa link của phần tử đầu tiên như là next và phần tử đầu tiên có link tới phần tử cuối cùng như là prev.

3. Các hoạt động cơ bản trên Danh sách liên kết

Dưới đây là một số hoạt động cơ bản có thể được thực hiện bởi một danh sách liên kết:
  • Hoạt động chèn: thêm một phần tử vào đầu danh sách liên kết.
  • Hoạt động xóa (phần tử đầu): xóa một phần tử tại đầu danh sách liên kết.
  • Hiển thị: hiển thị toàn bộ danh sách.
  • Hoạt động tìm kiếm: tìm kiếm phần tử bởi sử dụng khóa (key) đã cung cấp.
  • Hoạt động xóa (bởi sử dụng khóa): xóa một phần tử bởi sử dụng khóa (key) đã cung cấp.

  • 3.1. Thêm Node vào danh sách liên kết

    Thêm vào đầu

    Việc thêm vào đầu chính là việc cập nhật lại thằng head. Ta gọi Node mới(temp), ta có:
    • Nếu head đang trỏ tới NULL, nghĩa là linked list đang trống, Node mới thêm vào sẽ làm head luôn
    • Ngược lại, ta phải thay thế thằng head cũ bằng head mới. Việc này phải làm theo thứ tự như sau:
      • Cho next của temp trỏ tới head hiện hành
      • Đặt temp làm head mới
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    node AddHead(node head, int value){
        node temp = CreateNode(value); // Khởi tạo node temp với data = value
        if(head == NULL){
            head = temp; // //Nếu linked list đang trống thì Node temp là head luôn
        }else{
            temp->next = head; // Trỏ next của temp = head hiện tại
            head = temp; // Đổi head hiện tại = temp(Vì temp bây giờ là head mới mà)
        }
        return head;
    }

    Thêm vào cuối

    Chúng ta sẽ cần Node đầu tiên, và giá trị muốn thêm. Khi đó, ta sẽ:
    1. Tạo một Node mới với giá trị value
    2. Nếu head = NULL, tức là danh sách liên kết đang trống. Khi đó Node mới(temp) sẽ là head luôn.
    3. Ngược lại, ta sẽ duyệt tới Node cuối cùng(Node có next = NULL), và trỏ next của thằng cuối tới Node mới(temp).
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    node AddTail(node head, int value){
        node temp,p;// Khai báo 2 node tạm temp và p
        temp = CreateNode(value);//Gọi hàm createNode để khởi tạo node temp có next trỏ tới NULL và giá trị là value
        if(head == NULL){
            head = temp;     //Nếu linked list đang trống thì Node temp là head luôn
        }
        else{
            p  = head;// Khởi tạo p trỏ tới head
            while(p->next != NULL){
                p = p->next;//Duyệt danh sách liên kết đến cuối. Node cuối là node có next = NULL
            }
            p->next = temp;//Gán next của thằng cuối = temp. Khi đó temp sẽ là thằng cuối(temp->next = NULL mà)
        }
        return head;
    }
    Tổng quan hơn, chúng ta sẽ sẽ viết hàm thêm một Node vào vị trí bất kỳ nhé.

    Thêm vào vị trí bất kỳ

    Thêm Node vào giữa danh sách liên kết
    Thêm Node vào giữa danh sách liên kết
    Để làm được việc này, ta phải duyệt từ đầu để tìm tới vị trí của Node cần chèn, giả sử là Node Q, khi đó ta cần làm theo thứ tự sau:
    • Cho next của Node mới trỏ tới Node mà Q đang trỏ tới
    • Cho Node Q trỏ tới Node mới
    Lưu ý: Chỉ số chèn bắt đầu từ chỉ số 0 nhé các bạn
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    node AddAt(node head, int value, int position){
        if(position == 0 || head == NULL){
            head = AddHead(head, value); // Nếu vị trí chèn là 0, tức là thêm vào đầu
        }else{
            // Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí
            int k = 1;
            node p = head;
            while(p != NULL && k != position){
                p = p->next;
                ++k;
            }
            if(k != position){
                // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định chèn cuối
                // Nếu bạn không muốn chèn, hãy thông báo vị trí chèn không hợp lệ
                head = AddTail(head, value);
                // printf("Vi tri chen vuot qua vi tri cuoi cung!\n");
            }else{
                node temp = CreateNode(value);
                temp->next = p->next;
                p->next = temp;
            }
        }
        return head;
    }
    Lưu ý: Bạn phải làm theo thứ tự trên, nếu bạn cho p->next = temp trước. Khi đó, bạn sẽ không thể lấy lại phần sau của danh sách liên kết nữa(Vì next chỉ được được lưu trong p->next mà thay đổi p->next rồi thì còn đâu giá trị cũ).

    3.2. Xóa Node khỏi danh sách liên kết

    Xóa đầu

    Xóa đầu đơn giản lắm, bây giờ chỉ cần cho thằng kế tiếp của head làm head là được thôi. Mà thằng kế tiếp của head chính là head->next.
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    node DelHead(node head){
        if(head == NULL){
            printf("\nCha co gi de xoa het!");
        }else{
            head = head->next;
        }
        return head;
    }

    Xóa cuối

    Xóa cuối mới nhọc nè, nhọc ở chỗ phải duyệt đến thằng cuối – 1, cho next của cuối – 1 đó bằng NULL.
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    node DelTail(node head){
        node p = head;
        while(p->next->next != NULL){
            p = p->next;
        }
        p->next = p->next->next; // Cho next bằng NULL
        // Hoặc viết p->next = NULL cũng được
        return head;
    }
    Thằng Node cuối – 1 là thằng có p->next->next = NULL. Bạn cho next của nó bằng NULL là xong.

    Xóa ở vị trí bất kỳ

    Việc xóa ở vị trí bất kỳ cũng khá giống xóa ở cuối kia. Đơn giản là chúng ta bỏ qua một phần tử, như ảnh sau:
    Xóa node trong danh sách liên kết
    Xóa node trong danh sách liên kết
    Lưu ý: Chỉ số xóa bắt đầu từ 0 nhé các bạn. Việc tìm vị trí càn xóa chỉ duyệt tới Node gần cuối thôi(cuối – 1). Sau đây là code xóa Node ở vị trí bất kỳ
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    node DelAt(node head, int position){
        if(position == 0 || head == NULL){
            head = DelHead(head); // Nếu vị trí chèn là 0, tức là thêm vào đầu
        }else{
            // Bắt đầu tìm vị trí cần chèn. Ta sẽ dùng k để đếm cho vị trí
            int k = 1;
            node p = head;
            while(p->next->next != NULL && k != position){
                p = p->next;
                ++k;
            }
            if(k != position){
                // Nếu duyệt hết danh sách lk rồi mà vẫn chưa đến vị trí cần chèn, ta sẽ mặc định xóa cuối
                // Nếu bạn không muốn xóa, hãy thông báo vị trí xóa không hợp lệ
                head = DelTail(head);
                // printf("Vi tri xoa vuot qua vi tri cuoi cung!\n");
            }else{
                p->next = p->next->next;
            }
        }
        return head;
    }

    3.3. Lấy giá trị ở vị trí bất kỳ

    Chúng ta sẽ viết một hàm để truy xuất giá trị ở chỉ số bất kỳ nhé. Trong trường hợp chỉ số vượt quá chiều dài của linked list – 1, hàm này trả về vị trí cuối cùng. Do hạn chế là chúng ta không thể raise error khi chỉ số không hợp lệ. Tôi mặc định chỉ số bạn truyền vào phải là số nguyên không âm.
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int Get(node head, int index){
        int k = 0;
        node p = head;
        while(p->next != NULL && k != index){
            p = p->next;
        }
        return p->data;
    }
    Lý do dùng p->next != NULL là vì chúng ta chỉ muốn đi qua các phần tử có value.

    3.4. Tìm kiếm trong danh sách liên kết

    Hàm tìm kiếm này sẽ trả về chỉ số của Node đầu tiên có giá trị bằng với giá trị cần tìm. Nếu không tìm thấy, chúng ta trả về -1.
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int Search(node head, int value){
        int position = 0;
        for(node p = head; p != NULL; p = p->next){
            if(p->data == value){
                return position;
            }
            ++position;
        }
        return -1;
    }
    Chúng ta có thể sử dụng hàm này để xóa tất cả các Node trong danh sách liên kết có giá trị chỉ định như sau:
    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    node DelByVal(node head, int value){
        int position = Search(head, value);
        while(position != -1){
            DelAt(head, position);
            position = Search(head, value);
        }
        return head;
    }

    3.5. Duyệt danh sách liên kết

    Việc duyệt danh sách liên kết cực đơn giản. Khởi tạo từ Node head, bạn cứ thế đi theo con trỏ next cho tới trước khi Node đó NULL.
    0
    1
    2
    3
    4
    5
    6
    7
    void Traverser(node head){
        printf("\n");
        for(node p = head; p != NULL; p = p->next){
            printf("%5d", p->data);
        }
    }

    3.6. Một số hàm bổ trợ khác

    Hàm khởi tạo Node head

    Đơn giản là cho con trỏ head = NULL thôi. Nếu bạn để ý, chúng ta vẫn check head = NULL để biết rằng danh sách liên kết chưa có phần tử nào ở các hàm phía trên.
    0
    1
    2
    3
    4
    5
    6
    node InitHead(){
        node head;
        head = NULL;
        return head;
    }

    Hàm lấy số phần tử của DSLK

    Duyệt và đếm chừng nào các Node chưa NULL. Sau cùng, trả về giá trị đếm được.
    0
    1
    2
    3
    4
    5
    6
    7
    8
    int Length(node head){
        int length = 0;
        for(node p = head; p != NULL; p = p->next){
            ++length;
        }
        return length;
    }

    Hàm nhập danh sách liên kết

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    node Input(){
        node head = InitHead();
        int n, value;
        do{
            printf("\nNhap so luong phan tu n = ");
            scanf("%d", &n);
        }while(n <= 0);
        for(int i = 0; i < n; ++i){
            printf("\nNhap gia tri can them: ");
            scanf("%d", &value);
            head = AddTail(head, value);
        }
        return head;
    }

  • Bài tập C về Danh sách liên kết đơn

    Dưới đây là các bài tập về Danh sách liên kết đơn trong C:

    Bài tập C về Danh sách liên kết vòng

    Để tìm hiểu thêm về các khái niệm của cấu trúc dữ liệu Danh sách liên kết vòng, mời bạn tham khảo ở chương Cấu trúc dữ liệu Danh sách liên kết vòng.
    Dưới đây là các bài tập về Danh sách liên kết vòng trong C:
Share:

Related Posts:

0 nhận xét:

Đăng nhận xét

Tìm kiếm Blog này
Được tạo bởi Blogger.

Học CSS căn bản

Trong phần này bạn sẽ được học kiến thức liên quan đến Học CSS nằm trong chuyên mục  HTML & CSS , nếu có vấn đề thắc mắc thì hãy liên h...