Bài 33.1: Khái niệm danh sách liên kết đơn trong C++

Chào mừng các bạn quay trở lại với series blog về C++ của FullhouseDev!

Trong thế giới lập trình, việc lựa chọn cấu trúc dữ liệu phù hợp có vai trò quyết định đến hiệu suất và sự linh hoạt của chương trình. Chúng ta đã quen thuộc với mảng (arrays) - một cấu trúc dữ liệu tuyệt vời cho việc lưu trữ các phần tử cùng kiểu một cách liền kề trong bộ nhớ, cho phép truy cập ngẫu nhiên (random access) cực nhanh.

Tuy nhiên, mảng cũng có những hạn chế của nó. Kích thước của mảng thường phải được xác định trước (trừ các trường hợp vector), và việc thêm hoặc xóa một phần tử ở giữa mảng đòi hỏi phải di chuyển rất nhiều phần tử khác, dẫn đến chi phí cao về thời gian (độ phức tạp O(n)).

Vậy, khi chúng ta cần một cấu trúc dữ liệu có khả năng thay đổi kích thước linh hoạt và hỗ trợ việc thêm/xóa phần tử hiệu quả hơn ở một số vị trí nhất định, chúng ta sẽ nghĩ đến Danh sách liên kết (Linked List). Và trong bài viết này, chúng ta sẽ bắt đầu khám phá loại danh sách liên kết đơn giản nhất nhưng cũng là nền tảng nhất: Danh sách liên kết đơn (Singly Linked List).

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

Hãy tưởng tượng bạn có một chuỗi các toa tàu. Mỗi toa tàu không chỉ chứa "hành khách" (dữ liệu) mà còn có một liên kết đến toa tàu tiếp theo. Toa tàu đầu tiên là "đầu tàu", và toa tàu cuối cùng thì không liên kết đến toa nào nữa (coi như là điểm dừng cuối). Đó chính là ý tưởng cốt lõi của danh sách liên kết đơn!

Cụ thể hơn, danh sách liên kết đơn là một tập hợp các nút (nodes). Mỗi nút bao gồm hai phần chính:

Dữ liệu (Data): Đây là nơi lưu trữ thông tin thực tế mà bạn muốn lưu trữ (có thể là số nguyên, chuỗi, đối tượng, v.v.).
Con trỏ (Pointer): Một con trỏ trỏ đến nút tiếp theo trong danh sách.

Danh sách liên kết đơn chỉ duy trì một con trỏ duy nhất trỏ đến nút đầu tiên của danh sách, thường được gọi là con trỏ head (hoặc root). Nút cuối cùng trong danh sách có con trỏ next của nó trỏ đến null (hoặc nullptr trong C++ hiện đại) để đánh dấu kết thúc danh sách.

Cấu trúc của một Nút (Node) trong C++

Để hiện thực hóa khái niệm này trong C++, chúng ta có thể sử dụng struct hoặc class để định nghĩa cấu trúc của một nút.

#include <iostream>

struct Node {
    int d;
    Node* n;

    Node(int v) : d(v), n(nullptr) {}
};

Giải thích:

Chúng ta định nghĩa một struct tên là Node.
Bên trong struct, có một biến d kiểu int (bạn có thể thay thế int bằng bất kỳ kiểu dữ liệu nào bạn muốn lưu trữ).
Điều quan trọng là biến n. Nó là một con trỏ (*) kiểu Node*. Điều này có nghĩa là n có thể trỏ đến một đối tượng khác cùng kiểu Node. Chính con trỏ này tạo nên "liên kết" giữa các nút.
Chúng ta thêm một constructor đơn giản Node(int v). Khi tạo một nút mới, chúng ta có thể truyền giá trị ban đầu cho d, và con trỏ n sẽ được khởi tạo mặc định là nullptr (nghĩa là ban đầu nút này chưa trỏ đến nút nào cả).

Cách các Nút Liên kết với nhau

Một danh sách liên kết đơn được tạo thành bằng cách kết nối các nút lại với nhau thông qua con trỏ next. Con trỏ head giữ địa chỉ của nút đầu tiên.

Hãy xem ví dụ minh họa cách chúng ta có thể tạo và liên kết vài nút đơn giản:

#include <iostream>

struct Node {
    int d;
    Node* n;

    Node(int v) : d(v), n(nullptr) {}
};

int main() {
    Node* h = new Node(10);
    Node* s = new Node(20);
    Node* b = new Node(30);

    h->n = s;
    s->n = b;

    cout << "Du lieu nut dau tien: " << h->d << endl;
    cout << "Du lieu nut thu hai: " << h->n->d << endl;
    cout << "Du lieu nut thu ba: " << h->n->n->d << endl;

    delete h;
    delete s;
    delete b;

    return 0;
}

Output:

Du lieu nut dau tien: 10
Du lieu nut thu hai: 20
Du lieu nut thu ba: 30

Giải thích:

Chúng ta tạo ba nút riêng biệt trên bộ nhớ heap bằng toán tử new. Mỗi new Node(...) trả về một con trỏ đến nút mới được tạo.
h = new Node(10); tạo nút đầu tiên và gán địa chỉ của nó cho con trỏ h. Ban đầu, h->n là nullptr.
h->n = s; không phải là sao chép dữ liệu, mà là gán địa chỉ. Nó làm cho con trỏ n của nút mà h đang trỏ tới (nút có data 10) trỏ đến cùng địa chỉ mà con trỏ s đang giữ (địa chỉ của nút có data 20).
Tương tự, s->n = b; liên kết nút 20 với nút 30.
Để truy cập dữ liệu của nút thứ hai, chúng ta không thể truy cập trực tiếp bằng tên biến s (vì h là điểm vào duy nhất). Chúng ta phải đi từ h, theo con trỏ n của nó: h->n sẽ cho ta con trỏ đến nút thứ hai. Sau đó, dùng ->d để lấy dữ liệu: h->n->d.
Để truy cập nút thứ ba, ta tiếp tục đi theo con trỏ n: h->n->n->d.
Việc quản lý bộ nhớ (delete) là cực kỳ quan trọng trong C++ khi sử dụng new. Nếu không giải phóng, bộ nhớ sẽ bị rò rỉ (memory leak). Trong ví dụ này, ta delete từng nút đã new. Tuy nhiên, cách tốt nhất để giải phóng toàn bộ danh sách là duyệt qua danh sách và xóa từng nút một cách cẩn thận (sẽ minh họa sau).

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

Một trong những thao tác cơ bản nhất với danh sách liên kết là duyệt qua nó để truy cập từng phần tử. Vì không có truy cập ngẫu nhiên như mảng, chúng ta phải bắt đầu từ head và theo con trỏ next từ nút này sang nút kế tiếp cho đến khi gặp nullptr.

#include <iostream>

struct Node {
    int d;
    Node* n;

    Node(int v) : d(v), n(nullptr) {}
};

int main() {
    Node* h = new Node(10);
    h->n = new Node(20);
    h->n->n = new Node(30);

    Node* c = h;
    cout << "Danh sach: ";
    while (c) {
        cout << c->d << " ";
        c = c->n;
    }
    cout << endl;

    c = h;
    while (c) {
        Node* t = c;
        c = c->n;
        delete t;
    }
    h = nullptr;

    return 0;
}

Output:

Danh sach: 10 20 30

Giải thích:

Chúng ta tạo một con trỏ tạm thời c và khởi tạo nó bằng h. c sẽ là "người đi bộ" qua danh sách.
Vòng lặp while (c) tiếp tục chạy miễn là c vẫn trỏ đến một nút hợp lệ (chưa đến cuối danh sách).
Bên trong vòng lặp:
- cout << c->d << " "; in ra dữ liệu của nút mà c đang trỏ tới.
- c = c->n; là bước chủ chốt. Nó cập nhật con trỏ c để trỏ đến nút tiếp theo. Nếu c đang trỏ đến nút cuối cùng, c->n sẽ là nullptr, và ở bước tiếp theo, vòng lặp sẽ kết thúc.
Phần giải phóng bộ nhớ: Vòng lặp thứ hai minh họa cách xóa toàn bộ danh sách một cách an toàn. Tại sao cần biến t? Nếu ta xóa c trước khi di chuyển c = c->n;, ta sẽ mất khả năng truy cập đến phần còn lại của danh sách. Bằng cách lưu c vào t, di chuyển c sang nút tiếp theo, rồi mới delete t, chúng ta đảm bảo không bị "mất dấu" chuỗi các nút. Cuối cùng, gán h = nullptr là một cách tốt để chỉ ra rằng danh sách hiện tại đã trống.

Ưu điểm và Nhược điểm của Danh sách liên kết đơn (Khái niệm)

Dựa trên cấu trúc và cách hoạt động cơ bản, chúng ta có thể thấy vài ưu điểm và nhược điểm so với mảng:

Ưu điểm:
- Kích thước linh hoạt (Dynamic Size): Danh sách có thể dễ dàng tăng hoặc giảm kích thước trong thời gian chạy chỉ bằng cách tạo hoặc xóa nút và cập nhật con trỏ.
- Thêm/Xóa hiệu quả ở đầu danh sách: Việc thêm một nút mới vào đầu danh sách hoặc xóa nút đầu tiên chỉ cần thay đổi con trỏ head và cập nhật liên kết của nút mới (nếu thêm). Độ phức tạp O(1). Việc thêm/xóa ở các vị trí khác cần duyệt (O(n)).
Nhược điểm:
- Không truy cập ngẫu nhiên (No Random Access): Để truy cập phần tử thứ i, bạn phải bắt đầu từ head và duyệt qua i-1 nút. Độ phức tạp O(n).
- Cần thêm bộ nhớ cho con trỏ: Mỗi nút cần một con trỏ để lưu địa chỉ nút tiếp theo, tốn thêm bộ nhớ so với mảng (chỉ lưu dữ liệu).
- Duyệt chỉ theo một chiều: Chỉ có thể đi từ đầu danh sách đến cuối danh sách. Không thể đi ngược lại dễ dàng (trừ khi dùng danh sách liên kết đôi).

Bài tập ví dụ: C++ Bài 21.A1: Điểm Mana

Điểm Mana

Mô tả

FullHouse Dev đang chơi một trò chơi di động. Trong trò chơi này, FullHouse Dev có thể thực hiện các đòn tấn công đặc biệt. Tuy nhiên, mỗi đòn tấn công đặc biệt tiêu tốn X điểm mana.

Nếu FullHouse Dev hiện có Y điểm mana, hãy xác định số lượng đòn tấn công đặc biệt tối đa mà anh ấy có thể thực hiện.

Input

Dòng đầu tiên chứa một số nguyên T - số lượng test case.
Mỗi test case gồm một dòng chứa hai số nguyên X và Y cách nhau bởi dấu cách - chi phí của một đòn tấn công đặc biệt và số điểm mana FullHouse Dev có ban đầu.

Output

Với mỗi test case, in ra số lượng đòn tấn công đặc biệt tối đa mà FullHouse Dev có thể thực hiện.

Ràng buộc

\(1 ≤ T ≤ 10^5\)
\(1 ≤ X ≤ 100\)
\(1 ≤ Y ≤ 1000\)

Ví dụ

Input:

Output:

3
6
8

Giải thích

Test case 1: FullHouse Dev có thể thực hiện 3 đòn tấn công đặc biệt, mỗi đòn tiêu tốn 10 điểm mana, tổng cộng 30 điểm mana.
Test case 2: FullHouse Dev có thể thực hiện 6 đòn tấn công đặc biệt, mỗi đòn tiêu tốn 6 điểm mana, tổng cộng 36 điểm mana. Còn lại 5 điểm mana không đủ để thực hiện thêm đòn tấn công nào.
Test case 3: FullHouse Dev có thể thực hiện 8 đòn tấn công đặc biệt, mỗi đòn tiêu tốn 50 điểm mana, tổng cộng 400 điểm mana. Chào bạn, đây là hướng dẫn giải bài tập "Điểm Mana" bằng C++ theo yêu cầu:

Bài toán yêu cầu tìm số lần tối đa bạn có thể thực hiện một hành động (đòn tấn công) khi mỗi lần tiêu tốn một lượng tài nguyên nhất định (X mana) và bạn có tổng cộng một lượng tài nguyên khác (Y mana).

Phân tích bài toán:

Đây là một bài toán chia đơn giản. Nếu bạn có Y mana và mỗi đòn tấn công tốn X mana, thì số lần tấn công tối đa bạn có thể thực hiện chính là số lần X "vừa vặn" chứa trong Y. Bất kỳ lượng mana còn lại nào nhỏ hơn X sẽ không đủ để thực hiện thêm một đòn tấn công nữa.

Trong lập trình, phép toán này chính là phép chia nguyên (integer division).

Hướng giải chi tiết:

Đọc số lượng test case: Bạn cần đọc giá trị T đầu tiên để biết có bao nhiêu bộ dữ liệu cần xử lý.
Vòng lặp xử lý test case: Sử dụng một vòng lặp (ví dụ: while hoặc for) để lặp lại T lần. Mỗi lần lặp sẽ xử lý một test case.
Đọc dữ liệu cho mỗi test case: Bên trong vòng lặp, đọc hai số nguyên X và Y cho mỗi test case.
Tính toán kết quả: Thực hiện phép chia nguyên Y / X. Kết quả của phép chia nguyên này chính là số đòn tấn công tối đa có thể thực hiện.
In kết quả: In kết quả của phép chia nguyên ra màn hình. Đảm bảo in mỗi kết quả trên một dòng riêng biệt (sử dụng ký tự xuống dòng).
Sử dụng thư viện chuẩn: Cần bao gồm thư viện iostream để sử dụng các hàm nhập/xuất chuẩn như cin và cout.
Kiểu dữ liệu: Với ràng buộc Y <= 1000 và X <= 100, kiểu dữ liệu int là đủ để lưu trữ X, Y và kết quả.

Ví dụ logic với các test case:

X=10, Y=30: 30 chia nguyên cho 10 bằng 3. (3 * 10 = 30 mana dùng hết)
X=6, Y=41: 41 chia nguyên cho 6 bằng 6. (6 * 6 = 36 mana dùng, còn lại 5 mana không đủ cho đòn tiếp theo)
X=50, Y=400: 400 chia nguyên cho 50 bằng 8. (8 * 50 = 400 mana dùng hết)

Gợi ý về cấu trúc code (không phải code hoàn chỉnh):

#include <iostream>

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int x, y;
        cin >> x >> y;
        cout << y / x << endl;
    }

    return 0;
}

Output:

3
6
8

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.