Bài 33.3: Danh sách liên kết đôi trong C++

Chào mừng trở lại với series C++! Hôm nay, chúng ta sẽ đào sâu vào một cấu trúc dữ liệu vô cùng linh hoạt và mạnh mẽ: Danh sách liên kết đôi (Doubly Linked List). Nếu bạn đã quen thuộc với danh sách liên kết đơn (singly linked list), thì danh sách liên kết đôi sẽ là một bước tiến thú vị, mang lại những khả năng mới.

Vậy, danh sách liên kết đôi là gì và nó khác gì so với danh sách liên kết đơn?

Khác biệt cốt lõi: Hai con trỏ!

Điểm khác biệt quan trọng nhất nằm ở mỗi phần tử (hay node) của danh sách. Trong danh sách liên kết đơn, mỗi node chỉ chứa dữ liệu và một con trỏ next (trỏ tới node kế tiếp). Ngược lại, trong danh sách liên kết đôi, mỗi node chứa dữ liệu và hai con trỏ:

next: Con trỏ trỏ tới node kế tiếp trong danh sách.
prev: Con trỏ trỏ tới node trước đó trong danh sách.

Chính sự tồn tại của con trỏ prev này mang lại những ưu điểm đáng kể, đặc biệt là khả năng duyệt danh sách theo cả hai chiều (từ đầu đến cuối và từ cuối về đầu) và thao tác xoá dễ dàng hơn trong nhiều trường hợp.

Hãy cùng xem cấu trúc của một node trong C++:

struct Node {
    int data;    // Dữ liệu của node
    Node* next;  // Con trỏ tới node kế tiếp
    Node* prev;  // Con trỏ tới node trước đó

    // Constructor giúp khởi tạo nhanh
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

Giải thích code:

Chúng ta định nghĩa một struct tên là Node.
Nó có một thành viên data để lưu trữ dữ liệu (ở đây dùng int, bạn có thể dùng kiểu dữ liệu khác tùy ý).
next là một con trỏ kiểu Node*, trỏ đến node "đằng sau" nó.
prev là một con trỏ kiểu Node*, trỏ đến node "đằng trước" nó.
Constructor Node(int val) là một cách tiện lợi để tạo một node mới, gán giá trị val cho data và ban đầu đặt cả next lẫn prev là nullptr (chỉ báo rằng nó chưa liên kết với node nào khác).

Cấu trúc tổng thể của Danh sách liên kết đôi

Để quản lý toàn bộ danh sách, chúng ta thường sử dụng một lớp (class) hoặc struct chứa các con trỏ đặc biệt:

head: Con trỏ trỏ tới node đầu tiên của danh sách.
tail: Con trỏ trỏ tới node cuối cùng của danh sách.

Sự có mặt của con trỏ tail cũng là một điểm khác biệt so với danh sách liên kết đơn thông thường (mặc dù bạn có thể thêm tail vào danh sách đơn nếu cần). Việc có tail giúp các thao tác thêm/xoá ở cuối danh sách trở nên hiệu quả hơn rất nhiều (O(1)) thay vì phải duyệt toàn bộ danh sách từ đầu như trong danh sách đơn.

Lớp quản lý danh sách liên kết đôi có thể trông như thế này:

#include <iostream> // Cần cho nhập xuất

// Định nghĩa struct Node như ở trên
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
private:
    Node* head; // Con trỏ tới node đầu danh sách
    Node* tail; // Con trỏ tới node cuối danh sách

public:
    // Constructor: Khởi tạo danh sách rỗng
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // Destructor: Giải phóng bộ nhớ khi đối tượng danh sách bị hủy
    ~DoublyLinkedList();

    // Các thao tác cơ bản
    void insertAtBeginning(int data);
    void insertAtEnd(int data);
    void deleteNode(int key); // Xoá node với giá trị data là 'key'
    void displayForward() const;  // Duyệt và in danh sách từ đầu
    void displayBackward() const; // Duyệt và in danh sách từ cuối
    bool search(int key) const;   // Tìm kiếm giá trị
};

// Triển khai Destructor (RẤT QUAN TRỌNG để tránh rò rỉ bộ nhớ)
DoublyLinkedList::~DoublyLinkedList() {
    Node* current = head;
    while (current != nullptr) {
        Node* nextNode = current->next; // Lưu con trỏ tới node kế tiếp
        delete current; // Giải phóng bộ nhớ của node hiện tại
        current = nextNode; // Di chuyển tới node kế tiếp
    }
    head = nullptr; // Đảm bảo head và tail trở về nullptr sau khi xoá
    tail = nullptr;
    cout << "Danh sach lien ket doi da duoc huy va giai phong bo nho." << endl;
}

// ... Triển khai các phương thức khác sẽ ở dưới ...

Giải thích code:

Lớp DoublyLinkedList chứa hai con trỏ head và tail, ban đầu được khởi tạo là nullptr trong constructor, biểu thị một danh sách rỗng.
Destructor ~DoublyLinkedList() là phần cực kỳ quan trọng. Vì chúng ta cấp phát bộ nhớ cho các node bằng new, chúng ta phải giải phóng chúng bằng delete khi không cần nữa để tránh rò rỉ bộ nhớ (memory leak). Destructor này duyệt qua toàn bộ danh sách và xoá từng node một cách an toàn.

Các thao tác cơ bản trên Danh sách liên kết đôi

Bây giờ, hãy đi sâu vào cách triển khai các thao tác phổ biến trên danh sách liên kết đôi.

1. Thêm node vào đầu danh sách (`insertAtBeginning`)

Thao tác này khá đơn giản, cần cập nhật con trỏ head và các liên kết của node mới cũng như node cũ ở đầu.

void DoublyLinkedList::insertAtBeginning(int data) {
    Node* newNode = new Node(data); // 1. Tạo node mới

    if (head == nullptr) { // 2a. Nếu danh sách rỗng
        head = newNode;
        tail = newNode;
    } else { // 2b. Nếu danh sách không rỗng
        newNode->next = head; // Node mới trỏ tới node head hiện tại
        head->prev = newNode; // Node head hiện tại trỏ ngược về node mới
        head = newNode;       // Cập nhật head là node mới
    }
    cout << "Da them " << data << " vao dau danh sach." << endl;
}

Giải thích code:

Tạo một node mới với dữ liệu cần thêm. Con trỏ next và prev của nó ban đầu là nullptr (từ constructor Node).
Kiểm tra danh sách rỗng: Nếu head là nullptr, tức danh sách chưa có phần tử nào, node mới chính là node đầu tiên và cũng là node cuối cùng. Cập nhật cả head và tail trỏ tới node mới.
Danh sách không rỗng:
- Con trỏ next của newNode sẽ trỏ tới node hiện đang là head.
- Con trỏ prev của node hiện đang là head sẽ trỏ ngược về newNode.
- Cập nhật head để nó trỏ tới newNode.

2. Thêm node vào cuối danh sách (`insertAtEnd`)

Thao tác này hiệu quả hơn nhiều so với danh sách đơn nhờ có con trỏ tail.

void DoublyLinkedList::insertAtEnd(int data) {
    Node* newNode = new Node(data); // 1. Tạo node mới

    if (tail == nullptr) { // 2a. Nếu danh sách rỗng
        head = newNode;
        tail = newNode;
    } else { // 2b. Nếu danh sách không rỗng
        newNode->prev = tail; // Node mới trỏ ngược về node tail hiện tại
        tail->next = newNode; // Node tail hiện tại trỏ tới node mới
        tail = newNode;       // Cập nhật tail là node mới
    }
    cout << "Da them " << data << " vao cuoi danh sach." << endl;
}

Giải thích code:

Tạo một node mới.
Kiểm tra danh sách rỗng: Giống như thêm vào đầu, node mới là head và tail.
Danh sách không rỗng:
- Con trỏ prev của newNode sẽ trỏ tới node hiện đang là tail.
- Con trỏ next của node hiện đang là tail sẽ trỏ tới newNode.
- Cập nhật tail để nó trỏ tới newNode.

3. Duyệt danh sách

Đây là lúc ưu điểm của danh sách đôi thể hiện rõ ràng: bạn có thể duyệt từ đầu hoặc từ cuối.

Duyệt xuôi (từ head đến tail) - displayForward

void DoublyLinkedList::displayForward() const {
    if (head == nullptr) {
        cout << "Danh sach rong." << std.endl;
        return;
    }

    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " <-> "; // Dấu "<->" thể hiện liên kết hai chiều
        current = current->next; // Di chuyển tới node kế tiếp
    }
    cout << "nullptr" << endl; // Kết thúc danh sách
}

Giải thích code:

Kiểm tra danh sách rỗng.
Bắt đầu từ head.
Lặp chừng nào current còn khác nullptr.
In dữ liệu của node current.
Cập nhật current bằng current->next để di chuyển tới node tiếp theo.

Duyệt ngược (từ tail về head) - displayBackward

void DoublyLinkedList::displayBackward() const {
     if (tail == nullptr) { // Có thể kiểm tra head cũng được, vì nếu head nullptr thì tail cũng nullptr
        cout << "Danh sach rong." << endl;
        return;
    }

    Node* current = tail; // Bắt đầu từ tail
    while (current != nullptr) {
        cout << current->data << " <-> "; // Dấu "<->" thể hiện liên kết hai chiều
        current = current->prev; // Di chuyển tới node TRƯỚC ĐÓ
    }
    cout << "nullptr" << endl; // Kết thúc danh sách
}

Giải thích code:

Kiểm tra danh sách rỗng.
Bắt đầu từ tail.
Lặp chừng nào current còn khác nullptr.
In dữ liệu của node current.
Cập nhật current bằng current->prev để di chuyển tới node trước đó. Đây là điểm khác biệt so với duyệt xuôi.

4. Tìm kiếm giá trị (`search`)

Thao tác này tương tự như danh sách đơn, chỉ cần duyệt từ đầu đến cuối và kiểm tra dữ liệu.

bool DoublyLinkedList::search(int key) const {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key) {
            return true; // Tìm thấy!
        }
        current = current->next; // Di chuyển tới node kế tiếp
    }
    return false; // Duyệt hết mà không tìm thấy
}

Giải thích code:

Bắt đầu từ head.
Lặp qua từng node.
Trong mỗi node, kiểm tra xem current->data có bằng key cần tìm không.
Nếu bằng, trả về true ngay lập tức.
Nếu duyệt hết danh sách mà không tìm thấy, vòng lặp kết thúc và trả về false.

5. Xoá node (`deleteNode`)

Xoá một node là nơi danh sách liên kết đôi thể hiện sự tiện lợi nếu bạn đã có con trỏ tới node cần xoá. Tuy nhiên, thường chúng ta cần xoá một node có giá trị cụ thể, nên trước tiên phải tìm node đó. Sau khi tìm thấy, việc cập nhật con trỏ next của node đứng trước và con trỏ prev của node đứng sau node bị xoá là cần thiết. Phải cẩn thận xử lý các trường hợp đặc biệt: xoá node đầu, xoá node cuối, xoá node duy nhất.

void DoublyLinkedList::deleteNode(int key) {
    Node* current = head;

    // 1. Tìm node cần xoá
    while (current != nullptr && current->data != key) {
        current = current->next;
    }

    // 2. Nếu không tìm thấy node
    if (current == nullptr) {
        cout << "Node voi du lieu " << key << " khong tim thay." << endl;
        return;
    }

    // 3. Node được tìm thấy, tiến hành xoá
    cout << "Dang xoa node voi du lieu: " << key << endl;

    // Xử lý con trỏ 'prev' của node kế tiếp
    if (current->next != nullptr) {
        current->next->prev = current->prev; // Node kế tiếp trỏ ngược về node trước node bị xoá
    } else { // Nếu node bị xoá là node cuối (current->next là nullptr)
        tail = current->prev; // Cập nhật tail là node trước đó
    }

    // Xử lý con trỏ 'next' của node trước đó
    if (current->prev != nullptr) {
        current->prev->next = current->next; // Node trước đó trỏ tới node kế tiếp node bị xoá
    } else { // Nếu node bị xoá là node đầu (current->prev là nullptr)
        head = current->next; // Cập nhật head là node kế tiếp
    }

    // Xử lý trường hợp node bị xoá là node duy nhất
    if (head == nullptr) { // Nếu sau khi xoá head (hoặc node duy nhất), head trở thành nullptr
         tail = nullptr; // Đảm bảo tail cũng là nullptr
    }


    // 4. Giải phóng bộ nhớ của node bị xoá
    delete current;
}

Giải thích code:

Duyệt từ đầu danh sách để tìm node có data bằng key.
Nếu vòng lặp kết thúc mà current là nullptr, nghĩa là không tìm thấy node, in thông báo và kết thúc hàm.
Nếu tìm thấy (current không phải nullptr):
- Cập nhật con trỏ prev của node kế tiếp: Nếu node bị xoá không phải là node cuối cùng (current->next != nullptr), thì con trỏ prev của node đứng sau nó (current->next->prev) phải được cập nhật để trỏ tới node đứng trước node bị xoá (current->prev). Nếu node bị xoá là node cuối, cập nhật tail thành node đứng trước nó.
- Cập nhật con trỏ next của node trước đó: Nếu node bị xoá không phải là node đầu tiên (current->prev != nullptr), thì con trỏ next của node đứng trước nó (current->prev->next) phải được cập nhật để trỏ tới node đứng sau node bị xoá (current->next). Nếu node bị xoá là node đầu, cập nhật head thành node đứng sau nó.
- Trường hợp node duy nhất: Nếu sau khi xoá, head trở thành nullptr, điều đó có nghĩa là danh sách đã rỗng, nên tail cũng phải được đặt là nullptr.
Cuối cùng, sử dụng delete current để giải phóng bộ nhớ mà node đó đang chiếm giữ.

Ví dụ minh hoạ đầy đủ

Kết hợp tất cả lại, đây là một ví dụ đơn giản sử dụng các thao tác đã triển khai:

#include <iostream>

// Định nghĩa struct Node và class DoublyLinkedList
// (Copy toàn bộ phần code struct Node, class DoublyLinkedList,
// và triển khai các phương thức từ trên xuống đây)

struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class DoublyLinkedList {
private:
    Node* head;
    Node* tail;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
    ~DoublyLinkedList();
    void insertAtBeginning(int data);
    void insertAtEnd(int data);
    void deleteNode(int key);
    void displayForward() const;
    void displayBackward() const;
    bool search(int key) const;
};

DoublyLinkedList::~DoublyLinkedList() {
    Node* current = head;
    while (current != nullptr) {
        Node* nextNode = current->next;
        delete current;
        current = nextNode;
    }
    head = nullptr;
    tail = nullptr;
    cout << "Danh sach lien ket doi da duoc huy va giai phong bo nho." << endl;
}

void DoublyLinkedList::insertAtBeginning(int data) {
    Node* newNode = new Node(data);
    if (head == nullptr) {
        head = newNode;
        tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
    cout << "Da them " << data << " vao dau danh sach." << endl;
}

void DoublyLinkedList::insertAtEnd(int data) {
    Node* newNode = new Node(data);
    if (tail == nullptr) {
        head = newNode;
        tail = newNode;
    } else {
        newNode->prev = tail;
        tail->next = newNode;
        tail = newNode;
    }
    cout << "Da them " << data << " vao cuoi danh sach." << endl;
}

void DoublyLinkedList::deleteNode(int key) {
    Node* current = head;

    while (current != nullptr && current->data != key) {
        current = current->next;
    }

    if (current == nullptr) {
        cout << "Node voi du lieu " << key << " khong tim thay." << endl;
        return;
    }

    cout << "Dang xoa node voi du lieu: " << key << endl;

    if (current->prev != nullptr) {
        current->prev->next = current->next;
    } else {
        head = current->next;
    }

    if (current->next != nullptr) {
        current->next->prev = current->prev;
    } else {
        tail = current->prev;
    }

    if (head == nullptr) {
         tail = nullptr;
    }

    delete current;
}

void DoublyLinkedList::displayForward() const {
    if (head == nullptr) {
        cout << "Danh sach rong.";
    } else {
        Node* current = head;
        while (current != nullptr) {
            cout << current->data << " <-> ";
            current = current->next;
        }
        cout << "nullptr";
    }
     cout << endl;
}

void DoublyLinkedList::displayBackward() const {
     if (tail == nullptr) {
        cout << "Danh sach rong.";
    } else {
        Node* current = tail;
        while (current != nullptr) {
            cout << current->data << " <-> ";
            current = current->prev;
        }
        cout << "nullptr";
    }
    cout << endl;
}

bool DoublyLinkedList::search(int key) const {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == key) {
            return true;
        }
        current = current->next;
    }
    return false;
}


int main() {
    DoublyLinkedList list; // Tạo một danh sách rỗng

    // Thêm một vài phần tử
    list.insertAtEnd(10);
    list.insertAtBeginning(5);
    list.insertAtEnd(20);
    list.insertAtBeginning(1);
    list.insertAtEnd(30);

    // Hiển thị danh sách
    cout << "\n--- Danh sach sau khi them ---" << endl;
    cout << "Duyet xuoi: ";
    list.displayForward(); // Expected: 1 <-> 5 <-> 10 <-> 20 <-> 30 <-> nullptr
    cout << "Duyet nguoc: ";
    list.displayBackward(); // Expected: 30 <-> 20 <-> 10 <-> 5 <-> 1 <-> nullptr

    // Tìm kiếm
    cout << "\n--- Tim kiem ---" << endl;
    int search_val = 10;
    if (list.search(search_val)) {
        cout << search_val << " co trong danh sach." << endl;
    } else {
        cout << search_val << " khong co trong danh sach." << endl;
    }
    search_val = 100;
     if (list.search(search_val)) {
        cout << search_val << " co trong danh sach." << endl;
    } else {
        cout << search_val << " khong co trong danh sach." << endl;
    }

    // Xoá các phần tử
    cout << "\n--- Xoa phan tu ---" << endl;
    list.deleteNode(20); // Xoá node giữa
    list.deleteNode(1);  // Xoá node đầu
    list.deleteNode(30); // Xoá node cuối
    list.deleteNode(100); // Xoá node không tồn tại

    cout << "\n--- Danh sach sau khi xoa ---" << endl;
    cout << "Duyet xuoi: ";
    list.displayForward(); // Expected: 5 <-> 10 <-> nullptr
    cout << "Duyet nguoc: ";
    list.displayBackward(); // Expected: 10 <-> 5 <-> nullptr

     list.deleteNode(5); // Xoá node còn lại
     list.deleteNode(10); // Xoá node cuối cùng

    cout << "\n--- Danh sach sau khi xoa het ---" << endl;
    cout << "Duyet xuoi: ";
    list.displayForward(); // Expected: Danh sach rong.
    cout << "Duyet nguoc: ";
    list.displayBackward(); // Expected: Danh sach rong.


    return 0; // Đối tượng list sẽ bị hủy, destructor được gọi tự động
}

Giải thích code main:

Tạo một đối tượng list thuộc lớp DoublyLinkedList.
Sử dụng các phương thức insertAtEnd và insertAtBeginning để thêm các số vào danh sách.
Gọi displayForward và displayBackward để xem trạng thái danh sách từ hai chiều.
Sử dụng search để kiểm tra sự tồn tại của các giá trị.
Gọi deleteNode nhiều lần để minh hoạ việc xoá các node ở các vị trí khác nhau (giữa, đầu, cuối) và cả node không tồn tại.
Sau mỗi lần xoá, hiển thị lại danh sách để thấy sự thay đổi.
Khi chương trình kết thúc (return 0), đối tượng list nằm trong hàm main sẽ bị hủy, và destructor ~DoublyLinkedList() sẽ tự động được gọi để giải phóng toàn bộ bộ nhớ đã cấp phát cho các node, tránh rò rỉ bộ nhớ.

Ưu điểm và Nhược điểm của Danh sách liên kết đôi

Ưu điểm:

Duyệt hai chiều dễ dàng: Có thể đi từ head đến tail hoặc ngược lại một cách hiệu quả.
Xoá node hiệu quả hơn: Nếu bạn đã có con trỏ tới node cần xoá, việc cập nhật các liên kết chỉ mất thời gian O(1) (hằng số), không cần tìm node trước đó như trong danh sách đơn.
Thêm/Xoá ở cuối nhanh chóng: Nhờ có con trỏ tail, các thao tác này cũng chỉ mất thời gian O(1).

Nhược điểm:

Tốn bộ nhớ hơn: Mỗi node cần thêm một con trỏ (prev), do đó tốn bộ nhớ gấp rưỡi hoặc gấp đôi so với danh sách liên kết đơn (tùy thuộc vào việc lưu trữ dữ liệu).
Thao tác thêm/xoá phức tạp hơn: Cần cập nhật hai con trỏ (next và prev) cho mỗi node bị ảnh hưởng, thay vì chỉ một như trong danh sách đơn. Điều này dễ dẫn đến sai sót nếu không cẩn thận.

Khi nào sử dụng Danh sách liên kết đôi?

Bạn nên cân nhắc sử dụng danh sách liên kết đôi khi:

Bạn cần thường xuyên duyệt danh sách theo cả hai chiều.
Bạn cần thực hiện các thao tác thêm/xoá hiệu quả ở cả đầu và cuối danh sách.
Bạn cần khả năng xoá một node nhanh chóng khi đã có sẵn con trỏ tới node đó.

Tuy nhiên, trong nhiều trường hợp thực tế, thư viện chuẩn C++ (list) đã cung cấp một triển khai danh sách liên kết đôi tối ưu và an toàn. Bạn nên ưu tiên sử dụng list trừ khi bạn có lý do cụ thể để tự triển khai (ví dụ: để học tập, tối ưu hóa rất đặc thù, hoặc làm việc trong môi trường không có STL).

Sử dụng `list` (Thay thế thực tế)

Để hoàn thiện bức tranh, hãy xem cách sử dụng list đơn giản:

#include <iostream>
#include <list> // Cần include header <list>
#include <algorithm> // Cần cho find

int main() {
    // list là một danh sách liên kết đôi
    list<int> myStdList;

    // Thêm phần tử
    myStdList.push_back(10); // Thêm vào cuối
    myStdList.push_front(5); // Thêm vào đầu
    myStdList.push_back(20);

    cout << "Danh sach list: ";
    // Duyệt và in
    for (int val : myStdList) {
        cout << val << " <-> ";
    }
    cout << "nullptr" << endl; // Expected: 5 <-> 10 <-> 20 <-> nullptr

    // Xoá phần tử (theo giá trị, cần tìm trước)
    auto it = find(myStdList.begin(), myStdList.end(), 10);
    if (it != myStdList.end()) {
        myStdList.erase(it); // Xoá tại vị trí con trỏ (iterator)
        cout << "Da xoa 10." << endl;
    }

    cout << "Danh sach sau khi xoa 10: ";
    for (int val : myStdList) {
        cout << val << " <-> ";
    }
    cout << "nullptr" << endl; // Expected: 5 <-> 20 <-> nullptr

    // list cũng có các phương thức như pop_front(), pop_back()
    myStdList.pop_front(); // Xoá phần tử đầu
    cout << "Sau khi pop_front: ";
     for (int val : myStdList) {
        cout << val << " <-> ";
    }
    cout << "nullptr" << endl; // Expected: 20 <-> nullptr

    return 0; // list sẽ tự động giải phóng bộ nhớ
}

Giải thích code list:

Sử dụng list<int> để tạo một danh sách các số nguyên.
push_back và push_front thêm phần tử vào cuối và đầu tương ứng.
Duyệt danh sách dễ dàng bằng range-based for loop.
Để xoá theo giá trị, bạn cần dùng find để lấy iterator tới phần tử đó, sau đó dùng phương thức erase của list với iterator này.
pop_front và pop_back xoá phần tử ở đầu và cuối.
Ưu điểm lớn nhất là list tự động quản lý bộ nhớ, bạn không cần lo lắng về new và delete.

Bài tập ví dụ: C++ Bài 21.A3: Vé vào hội chợ

Vé vào hội chợ

FullHouse Dev đang tổ chức một hội chợ ở FullHouseLand. Anh ấy muốn tham gia hội chợ cùng với N người bạn của mình. Anh ấy đã thu thập được K vé vào cửa. Liệu Anh ấy có thể vào hội chợ cùng với tất cả N người bạn của mình không?

Mỗi người cần một vé để vào hội chợ, và mỗi vé chỉ có thể được sử dụng bởi một người.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
Mỗi bộ test gồm một dòng chứa hai số nguyên cách nhau bởi dấu cách N, K.

OUTPUT FORMAT

Với mỗi bộ test, in ra trên một dòng mới YES nếu Anh ấy có thể vào hội chợ cùng với tất cả N người bạn của mình và NO nếu không thể.

CONSTRAINTS

1 ≤ T ≤ 100
1 ≤ N, K ≤ 100

Ví dụ

Input

Output

YES
NO
NO
YES

Giải thích:

Test 1: Anh ấy cần 5 vé cho bạn bè và một vé cho mình, và anh ấy đã thu thập được 8 vé. Vì vậy, anh ấy sẽ có thể vào hội chợ cùng với tất cả bạn bè.
Test 2: Anh ấy cần 6 vé cho bạn bè và một vé cho mình, trong khi anh ấy chỉ thu thập được 3 vé. Vì vậy, anh ấy sẽ không thể vào hội chợ cùng với tất cả bạn bè, chỉ có ba người có thể vào hội chợ.
Test 3: Anh ấy cần 2 vé cho bạn bè và một vé cho mình, trong khi anh ấy chỉ thu thập được 2 vé. Vì vậy, hoặc Anh ấy hoặc một trong những người bạn của anh ấy không thể vào hội chợ.
Test 4: Anh ấy cần tổng cộng 2 vé, một cho mình và một cho bạn. Anh ấy đã thu thập được 2 vé. Vì vậy, anh ấy sẽ có thể vào hội chợ cùng với người bạn của mình. Chào bạn, đây là hướng dẫn giải bài "Vé vào hội chợ" bằng C++ một cách ngắn gọn, tập trung vào logic và sử dụng các thư viện chuẩn (std).

Bài toán yêu cầu xác định xem với số vé K có đủ cho "Anh ấy" và toàn bộ N người bạn của mình cùng vào hội chợ hay không.

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

Số người cần vé: Anh ấy là 1 người, và có N người bạn. Tổng cộng có 1 + N người cần vé.
Điều kiện đủ vé: Để tất cả mọi người cùng vào được, số vé Anh ấy có (K) phải lớn hơn hoặc bằng tổng số người cần vé.
Kết quả:
- Nếu K đủ (tức là K >= 1 + N), in ra "YES".
- Nếu K không đủ (tức là K < 1 + N), in ra "NO".

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

Bạn cần đọc số lượng bộ test T.
Sử dụng một vòng lặp để xử lý T bộ test.
Bên trong vòng lặp:
- Đọc hai số nguyên N và K cho bộ test hiện tại.
- Tính tổng số người cần vé: tong_nguoi = N + 1.
- So sánh số vé Anh ấy có (K) với tổng số người cần vé (tong_nguoi).
- Nếu K >= tong_nguoi, in ra "YES".
- Ngược lại (nếu K < tong_nguoi), in ra "NO".
- Đảm bảo sau mỗi kết quả "YES" hoặc "NO", xuống dòng (endl).

Các bước thực hiện trong code C++:

Bao gồm header cần thiết cho nhập xuất, ví dụ: <iostream>.
Sử dụng int main() { ... }.
Khai báo biến T và đọc giá trị của nó.
Sử dụng vòng lặp while (T--) hoặc for (int i = 0; i < T; ++i) để lặp T lần.
Bên trong vòng lặp, khai báo biến N và K, đọc giá trị của chúng.
Sử dụng câu lệnh điều kiện if-else để so sánh K với N + 1.
Sử dụng cout để in ra "YES" hoặc "NO" và endl để xuống dòng.

Lưu ý:

Sử dụng các kiểu dữ liệu số nguyên phù hợp cho N và K (ví dụ: int).
Không cần sử dụng các cấu trúc dữ liệu phức tạp, chỉ cần đọc, tính toán đơn giản và so sánh.
Ưu tiên sử dụng các hàm và đối tượng từ namespace std (cin, cout, endl).

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

Comments

There are no comments at the moment.