Thứ Hai, 19 Tháng Hai 2024
Trang chủLập trìnhLập trình C/C++Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập...

Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++

Danh sách liên kết (linked list) là một cấu trúc dữ liệu linh hoạt và phổ biến trong lập trình. Nó cho phép lưu trữ dữ liệu dưới dạng các nút (node) liên kết với nhau thông qua các con trỏ. Trong bài viết này, chúng ta sẽ cùng triển khai danh sách liên kết đơn (linked list) trong lập trình C/C++.

DANH SÁCH BÀI VIẾT
Tìm hiểu Cấu trúc dữ liệu Hash table trong lập trình C/C++
Cây đa phân trong lập trình C/C++ – Cấu trúc dữ liệu cây đa phân
Hiểu về cấu trúc dữ liệu cây trong lập trình C/C++
Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút
Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++
Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Cây nhị phân tìm kiếm – Tìm hiểu cây nhị phân tìm kiếm trong C/C++
Duyệt tiền tố, trung tố, hậu tố trong cây nhị phân – Lập trình C/C++

Cấu trúc dữ liệu Danh sách liên kết

Hình minh họa danh sách liên kết(linked list)

Trong lập trình C/C++, danh sách liên kết là một cấu trúc dữ liệu được sử dụng để lưu trữ một tập hợp các phần tử có thể được truy cập theo thứ tự. Nó bao gồm các nút được liên kết với nhau theo một chiều hoặc hai chiều. Bạn có thể hình dung danh sách liên kết nó như một sợi xích vậy.

Mỗi nút trong danh sách liên kết chứa hai phần: một phần dữ liệu để lưu trữ giá trị của phần tử và phần để lưu trữ con trỏ trỏ đến phần tử tiếp theo trong danh sách. Nếu danh sách liên kết là một danh sách liên kết đơn, mỗi nút sẽ chỉ trỏ đến phần tử tiếp theo trong danh sách. Nếu danh sách liên kết là một danh sách liên kết đôi, mỗi nút sẽ trỏ đến phần tử tiếp theo và phần tử trước đó trong danh sách.

Dưới đây là cấu trúc của một nút trong danh sách liên kết đơn:

struct Node {
    int data;
    Node* next;
};

Trong trường hợp liên kết đôi

struct Node {
    int data;
    Node* next;
    Node* prev;
};

Ở đây, data (1 số, chuỗi, hay 1 tập hợp) là dữ liệu của phần tử, next là con trỏ trỏ đến phần tử tiếp theo trong danh sách, và prev là con trỏ trỏ đến phần tử trước đó trong danh sách (chỉ dùng cho danh sách liên kết đôi).

XEM THÊM: Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay

Triển khai các hàm danh sách liên kết

Sau khi tạo ra cấu trúc của 1 Node, chúng ta có thể bắt đầu triển khai các hàm cho danh sách liên kết đơn.

  1. Hàm insert – Chèn phần tử vào cuối danh sách.

Để thêm một phần tử vào danh sách liên kết, ta cần tạo một nút mới và gán giá trị của nó. Sau đó, ta sẽ chèn nút mới vào đầu hoặc cuối danh sách liên kết tùy thuộc vào yêu cầu của bài toán.

Hàm chèn vào cuối danh sách

// Hàm chèn một nút mới vào cuối danh sách liên kết
void insert (Node** head, int data) {
    // Tạo một nút mới và khởi tạo giá trị dữ liệu và con trỏ next của nó
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;

    // Nếu danh sách liên kết rỗng, thì đặt nút mới làm head
    if (*head == NULL) {
        *head = newNode;
    }
    else {
        // Tìm nút cuối cùng trong danh sách liên kết
        Node* lastNode = *head;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }

        // Chèn nút mới vào cuối danh sách liên kết
        lastNode->next = newNode;
    }
}

2. Hàm insertAtBeginning – Chèn phần tử vào đầu danh sách.

void insertAtBeginning(struct Node** head, int newData) {
    // Tạo một nút mới và gán giá trị của nó
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    newNode->next = *head;//Cho nút mới trỏ tới nút đầu tiên của danh sách

    // Cập nhật lại nút gốc là nút newNode
    *head = newNode;
}

3. Hàm insertAtPosition – Hàm chèn phần tử vào vị trí bất kì trong danh sách

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;

    // Nếu danh sách rỗng hoặc muốn chèn vào vị trí đầu tiên
    if (*head == NULL || position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node* current = *head;
    Node* previous = NULL;
    int count = 1;

    // Duyệt đến vị trí cần chèn
    while (current != NULL && count < position) {
        previous = current;
        current = current->next;
        count++;
    }

    // Nếu vị trí chèn lớn hơn số lượng phần tử hiện tại của danh sách
    if (current == NULL && count < position) {
        cout << "Vị trí chèn lớn hơn số lượng phần tử hiện tại của danh sách." << endl;
        return;
    }

    // Chèn phần tử vào vị trí cần chèn
    previous->next = newNode;
    newNode->next = current;
}

4. Hàm isEmpty – Hàm để kiểm tra danh sách liên kết có rỗng hay không.

//Hàm kiểm tra danh sách rỗng
bool isEmpty(Node* head) {
    return head == NULL; //Nếu head == NULL trả về 1, ngược lại trả về 0
}

Để kiểm tra danh sách liên kết rỗng, ta so sánh giá trị của con trỏ head với NULL. Nếu head bằng NULL, tức là danh sách không có phần tử nào, ta trả về true. Ngược lại, nếu head khác NULL, tức là danh sách có ít nhất một phần tử, ta trả về false.

5. Hàm length – Hàm tính chiều dài danh sách liên kết

//Hàm tính chiều dài danh sách liên kết
int length(Node* head) {
    int count = 0; // Khởi tạo biến đếm ban đầu bằng 0
    Node* current = head; // Khởi tạo con trỏ current trỏ đến đầu danh sách liên kết
    while (current != NULL) {  // Lặp lại việc tăng biến đếm cho tới khi con trỏ current trỏ đến 
        count++; // Tăng biến đếm lên một đơn vị
        current = current->next; // Di chuyển con trỏ current sang phần tử tiếp theo trong danh sách liên kết
    }
    return count;  // Trả về giá trị biến đếm sau khi đã tính được chiều dài của danh sách liên kết
}

Hàm length() sẽ được sử dụng khi chúng ta cần tính chiều dài của danh sách liên kết đơn. Hàm sử dụng một biến đếm để đếm số nút trong danh sách liên kết đơn, và sử dụng một con trỏ để duyệt từng nút trong danh sách liên kết. Mỗi lần duyệt qua một nút, hàm sẽ tăng biến đếm lên một đơn vị và di chuyển con trỏ tới nút tiếp theo. Cuối cùng, hàm sẽ trả về giá trị của biến đếm, tức là chiều dài của danh sách liên kết đơn.

6. Hàm printList – Hàm in ra các giá trị của danh sách liên kết đơn

// Hàm in ra các giá trị của danh sách liên kết đơn
// Input:
//      - head: con trỏ trỏ tới nút đầu tiên của danh sách liên kết đơn
void printList(Node* head) {
    Node* current = head; // Con trỏ current trỏ đến nút đầu tiên của danh sách liên kết đơn
    while (current != NULL) { // Vòng lặp sẽ thực hiện cho đến khi current trỏ đến NULL (cuối danh sách liên kết đơn)
        cout << current->data << " "; // In ra giá trị của nút hiện tại
        current = current->next; // Con trỏ current được di chuyển đến nút tiếp theo
    }
}

Hàm printList() sẽ được sử dụng khi chúng ta muốn in ra giá trị của từng nút trong danh sách liên kết đơn. Hàm sử dụng một vòng lặp để duyệt qua từng nút trong danh sách liên kết, in ra giá trị của từng nút và di chuyển con trỏ tới nút tiếp theo.

Chương trình ví dụ

Từ các hàm thành phần đã có bên trên, mình có thể viết một chương trình ví dụ đơn giản cho danh sách liên kết đơn như sau:

Chương trình này sẽ tạo cấu trúc của một danh sách liên kết đơn, với giá trị phần tử nút là một số kiểu int. Nhập danh sách và xuất danh sách ra màn hình.

Code mẫu:

#include <iostream>
using namespace std;

// Khai báo cấu trúc Node
struct Node {
    int data;
    Node* next;
};

// Hàm chèn phần tử vào đầu danh sách
void insertAtBeginning(Node** head, int data) {
    Node* newNode = new Node; // Tạo một node mới
    newNode->data = data;
    newNode->next = *head; // Thiết lập con trỏ next của node mới trỏ đến head
    *head = newNode; // Cập nhật head để trỏ đến node mới
}

// Hàm xuất danh sách liên kết đơn
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
}

// Hàm main
int main() {
    Node* head = NULL; // Khởi tạo danh sách rỗng

    // Chèn các phần tử vào danh sách
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 15);
    insertAtBeginning(&head, 20);

    // Xuất danh sách liên kết đơn
    cout << "Danh sach lien ket don la: ";
    printList(head);

    return 0;
}

Và đây là kết quả khi chạy trương trình này:

Kết quả khi chạy chương trình
Kết quả khi chạy chương trình

Cảm ơn bạn đã đọc hết bài viết, hy vọng qua bài viết này đã giúp bạn nắm rõ và áp dụng được cấu trúc dữ liệu danh sách liên kết.

[Xem tất cả bài viết chủ đề C/C++ tại đây]

XÊM THÊM
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Tìm hiểu các toán tử thao tác bit trong lập trình C/C++
Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++
Thuật toán đếm số lượng chữ số của số nguyên dương n
Thuật toán tính dãy số Fibonacci
Bài toán chuẩn hóa xâu ký tự
Kiểm tra số chẵn lẻ trong lập trình C/C++
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?

Dịch vụ code thuê

TUICOCACH.COM NHẬN ĐẶT TEXTLINK, BANNER, GP
0
Giáo sư! có thể ném gạch bên dưới nhé!x