Bài 33.2: Thao tác cơ bản trên danh sách liên kết trong C++

Chào mừng trở lại với series C++ của FullhouseDev! Sau khi đã nắm được khái niệm và cấu trúc của danh sách liên kết, hôm nay chúng ta sẽ bước vào phần quan trọng nhất: thực hành các thao tác cơ bản để thật sự làm chủ cấu trúc dữ liệu linh hoạt này trong C++.

Danh sách liên kết (Linked List) khác biệt đáng kể so với mảng (Array) hay vector ở cách chúng lưu trữ dữ liệu. Thay vì các phần tử nằm liền kề trong bộ nhớ, mỗi phần tử (gọi là Node) lại chứa một con trỏ trỏ đến phần tử tiếp theo. Chính cấu trúc này mang lại lợi thế về hiệu quả khi thực hiện các thao tác thêm hoặc xoá phần tử ở bất kỳ vị trí nào mà không cần dịch chuyển cả khối dữ liệu lớn.

Bài viết này sẽ tập trung vào các thao tác cốt lõi: thêm (insertion), xoá (deletion), và duyệt (traversal) trên danh sách liên kết đơn (Singly Linked List).

Để bắt đầu, chúng ta cần định nghĩa lại cấu trúc của một Node và một lớp (class) quản lý danh sách liên kết.

1. Cấu trúc cơ bản: Node và LinkedList

Mỗi Node trong danh sách liên kết đơn thường chứa hai thứ:

Dữ liệu (Data): Giá trị mà Node đó lưu giữ (có thể là bất kỳ kiểu dữ liệu nào).
Con trỏ Next (Next Pointer): Con trỏ trỏ đến Node tiếp theo trong danh sách. Con trỏ next của Node cuối cùng sẽ trỏ đến nullptr.

#include <iostream> // Cần cho cout

// Định nghĩa cấu trúc của một Node
struct Node {
    int data;     // Phần dữ liệu của Node
    Node* next;   // Con trỏ trỏ tới Node kế tiếp

    // Constructor tiện lợi để tạo Node mới
    Node(int val) : data(val), next(nullptr) {}
};

Để quản lý toàn bộ danh sách, chúng ta cần một điểm truy cập duy nhất, đó chính là con trỏ head (đầu danh sách). Một lớp LinkedList đơn giản có thể chỉ cần lưu giữ con trỏ này.

class LinkedList {
public:
    Node* head; // Con trỏ trỏ tới Node đầu tiên của danh sách

    // Constructor: Khởi tạo một danh sách liên kết rỗng
    LinkedList() : head(nullptr) {}

    // Chúng ta sẽ thêm các thao tác vào đây...

    // Hàm huỷ (Destructor) để giải phóng bộ nhớ khi đối tượng LinkedList bị huỷ
    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next; // Lưu lại Node kế tiếp trước khi xoá Node hiện tại
            delete current;       // Giải phóng bộ nhớ của Node hiện tại
            current = next;       // Di chuyển tới Node kế tiếp đã lưu
        }
        head = nullptr; // Đảm bảo head trỏ về null sau khi tất cả các Node được giải phóng
    }
};

Giải thích:

struct Node: Định nghĩa khuôn mẫu cho mỗi phần tử. data chứa giá trị, next là con trỏ kiểu Node* (con trỏ trỏ đến Node khác). Constructor Node(int val) giúp tạo Node mới một cách dễ dàng, tự động gán giá trị và thiết lập next ban đầu là nullptr.
class LinkedList: Lớp này quản lý danh sách bằng cách chỉ giữ con trỏ head. head ban đầu là nullptr, biểu thị danh sách rỗng.
~LinkedList(): Đây là hàm huỷ. Rất quan trọng trong C++ khi làm việc với con trỏ và cấp phát động (new). Khi một đối tượng LinkedList không còn được sử dụng, hàm huỷ sẽ tự động chạy để đi qua toàn bộ danh sách và delete từng Node một, tránh tình trạng rò rỉ bộ nhớ (memory leak).

Bây giờ, chúng ta sẽ đi vào chi tiết các thao tác.

2. Thêm phần tử (Insertion)

Thêm một Node mới vào danh sách liên kết có thể được thực hiện ở nhiều vị trí khác nhau: đầu danh sách, cuối danh sách, hoặc tại một vị trí cụ thể. Chúng ta sẽ tập trung vào hai trường hợp cơ bản nhất.

2.1. Thêm vào đầu danh sách (Insert at Head)

Đây là thao tác đơn giản và hiệu quả nhất trong danh sách liên kết đơn vì nó chỉ yêu cầu thay đổi con trỏ head và con trỏ next của Node mới.

Logic:

Tạo một Node mới với dữ liệu cần thêm.
Đặt con trỏ next của Node mới trỏ tới Node mà head hiện tại đang trỏ tới.
Cập nhật con trỏ head để nó trỏ tới Node mới.

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    // Hàm thêm Node vào đầu danh sách
    void insertAtHead(int val) {
        Node* newNode = new Node(val); // 1. Tạo Node mới

        // 2. Con trỏ next của Node mới trỏ tới head hiện tại
        //    (Kể cả khi head là nullptr, vẫn đúng)
        newNode->next = head;

        // 3. Cập nhật head thành Node mới
        head = newNode;

        cout << "Da them " << val << " vao dau danh sach.\n";
    }

    // ... các thao tác khác ...

    ~LinkedList() { /* ... */ } // Hàm huỷ đã nêu ở trên
};

Giải thích:

Node* newNode = new Node(val);: Cấp phát bộ nhớ cho Node mới và khởi tạo nó với giá trị val.
newNode->next = head;: Đây là bước then chốt. Con trỏ next của Node mới giờ đây trỏ đến Node đầu tiên cũ (hoặc nullptr nếu danh sách rỗng).
head = newNode;: Cập nhật con trỏ head để nó trỏ đến Node mới. Bây giờ, Node mới đã trở thành Node đầu tiên của danh sách.

Thao tác này có độ phức tạp thời gian là O(1) (hằng số) vì số bước thực hiện không phụ thuộc vào số lượng phần tử trong danh sách.

2.2. Thêm vào cuối danh sách (Insert at Tail)

Thêm vào cuối phức tạp hơn một chút so với thêm vào đầu, vì chúng ta cần duyệt qua toàn bộ danh sách để tìm Node cuối cùng.

Logic:

Tạo một Node mới với dữ liệu cần thêm.
Nếu danh sách rỗng (head là nullptr), Node mới chính là head.
Nếu không rỗng, duyệt từ head cho đến Node cuối cùng (Node mà có con trỏ next là nullptr).
Đặt con trỏ next của Node cuối cùng tìm được trỏ tới Node mới.

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtHead(int val) { /* ... */ } // Đã nêu ở trên

    // Hàm thêm Node vào cuối danh sách
    void insertAtTail(int val) {
        Node* newNode = new Node(val); // 1. Tạo Node mới

        if (head == nullptr) { // 2. Trường hợp danh sách rỗng
            head = newNode;
            cout << "Da them " << val << " vao danh sach rong (tro thanh head).\n";
            return;
        }

        // 3. Duyệt đến Node cuối cùng
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }

        // 4. Đặt con trỏ next của Node cuối cùng trỏ tới Node mới
        current->next = newNode;
        cout << "Da them " << val << " vao cuoi danh sach.\n";
    }

    // ... các thao tác khác ...

    ~LinkedList() { /* ... */ } // Hàm huỷ đã nêu ở trên
};

Giải thích:

if (head == nullptr) { ... }: Xử lý trường hợp đặc biệt: danh sách rỗng. Node mới sẽ trở thành Node đầu tiên và duy nhất.
Node* current = head;: Bắt đầu duyệt từ head.
while (current->next != nullptr) { current = current->next; }: Vòng lặp này di chuyển con trỏ current tiến lên cho đến khi current->next là nullptr, tức là current đang trỏ đến Node cuối cùng.
current->next = newNode;: Node cuối cùng (mà current đang trỏ tới) giờ đây trỏ đến Node mới, kết nối Node mới vào cuối danh sách.

Thao tác này có độ phức tạp thời gian là O(n), trong đó n là số lượng phần tử, vì trong trường hợp xấu nhất (thêm vào danh sách rất dài), chúng ta phải duyệt qua toàn bộ danh sách.

3. Xoá phần tử (Deletion)

Xoá một Node cũng có thể thực hiện ở đầu, cuối, hoặc theo giá trị/vị trí. Chúng ta sẽ xem xét xoá đầu và xoá theo giá trị.

3.1. Xoá phần tử đầu danh sách (Delete Head)

Tương tự như thêm vào đầu, xoá Node đầu tiên là một thao tác hiệu quả.

Logic:

Kiểm tra nếu danh sách rỗng. Nếu có, không làm gì.
Lưu lại con trỏ trỏ đến Node đầu tiên hiện tại (Node cần xoá).
Cập nhật con trỏ head để nó trỏ tới Node tiếp theo (Node mà head cũ đang trỏ tới).
Giải phóng bộ nhớ của Node đã lưu ở bước 2.

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtHead(int val) { /* ... */ } // Đã nêu ở trên
    void insertAtTail(int val) { /* ... */ } // Đã nêu ở trên

    // Hàm xoá Node ở đầu danh sách
    void deleteHead() {
        if (head == nullptr) { // 1. Danh sách rỗng, không làm gì
            cout << "Danh sach rong, khong the xoa dau.\n";
            return;
        }

        Node* oldHead = head; // 2. Lưu lại Node head hiện tại
        head = head->next;     // 3. Cập nhật head thành Node tiếp theo
        delete oldHead;        // 4. Giải phóng bộ nhớ của Node cũ (quan trọng!)

        cout << "Da xoa Node dau danh sach.\n";
    }

    // ... các thao tác khác ...

    ~LinkedList() { /* ... */ } // Hàm huỷ đã nêu ở trên
};

Giải thích:

if (head == nullptr): Kiểm tra danh sách rỗng để tránh lỗi truy cập con trỏ null.
Node* oldHead = head;: Tạo một con trỏ tạm để giữ địa chỉ của Node đầu tiên trước khi chúng ta thay đổi head. Điều này cho phép chúng ta delete đúng Node đó sau này.
head = head->next;: Con trỏ head giờ nhảy đến Node kế tiếp (hoặc nullptr nếu danh sách chỉ có 1 Node ban đầu).
delete oldHead;: Giải phóng bộ nhớ mà oldHead đang trỏ tới. Nếu không có bước này, bộ nhớ của Node bị xoá sẽ không được trả về hệ thống, dẫn đến rò rỉ bộ nhớ.

Thao tác này có độ phức tạp thời gian là O(1).

3.2. Xoá phần tử theo giá trị (Delete by Value)

Để xoá một Node có giá trị cụ thể, chúng ta cần tìm Node đó và Node đứng trước nó để có thể "bỏ qua" Node cần xoá khi liên kết lại.

Logic:

Kiểm tra nếu danh sách rỗng hoặc Node đầu tiên chứa giá trị cần xoá (trường hợp đặc biệt).
Nếu Node đầu tiên chứa giá trị, xử lý như deleteHead và kết thúc.
Nếu không, duyệt danh sách, giữ một con trỏ current (hoặc prev) trỏ đến Node trước Node mà chúng ta đang kiểm tra.
Khi tìm thấy Node cần xoá (current->next trỏ đến Node có giá trị đó), cập nhật con trỏ next của Node current để nó trỏ tới Node sau Node cần xoá (current->next = current->next->next;).
Giải phóng bộ nhớ của Node cần xoá.
Xử lý trường hợp không tìm thấy giá trị.

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtHead(int val) { /* ... */ } // Đã nêu ở trên
    void insertAtTail(int val) { /* ... */ } // Đã nêu ở trên
    void deleteHead() { /* ... */ }         // Đã nêu ở trên

    // Hàm xoá Node theo giá trị
    void deleteByValue(int val) {
        if (head == nullptr) { // Danh sách rỗng
            cout << "Danh sach rong, khong the xoa.\n";
            return;
        }

        // Trường hợp Node cần xoá là head
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            cout << "Da xoa Node dau co gia tri " << val << ".\n";
            return;
        }

        // Trường hợp Node cần xoá không phải head
        Node* current = head;
        // Duyệt tìm Node mà Node KẾ TIẾP CỦA NÓ chứa giá trị cần xoá
        // Điều kiện dừng: current->next là nullptr (đến cuối) hoặc current->next->data khớp giá trị
        while (current->next != nullptr && current->next->data != val) {
            current = current->next;
        }

        // Nếu tìm thấy Node có giá trị val (current->next không null và data khớp)
        if (current->next != nullptr) {
            Node* toDelete = current->next; // Lưu lại Node cần xoá
            current->next = toDelete->next; // Bỏ qua Node cần xoá trong liên kết
            delete toDelete;                // Giải phóng bộ nhớ
            cout << "Da xoa Node co gia tri " << val << ".\n";
        } else { // Không tìm thấy Node có giá trị val sau head
            cout << "Khong tim thay Node co gia tri " << val << " de xoa.\n";
        }
    }

    // ... các thao tác khác ...

    ~LinkedList() { /* ... */ } // Hàm huỷ đã nêu ở trên
};

Giải thích:

Đầu tiên, hàm xử lý trường hợp danh sách rỗng và trường hợp đặc biệt khi Node đầu tiên là Node cần xoá.
Vòng lặp while (current->next != nullptr && current->next->data != val) duyệt danh sách. Nó dừng lại khi hoặc đi đến cuối danh sách (current->next là nullptr), hoặc Node tiếp theo của current chứa giá trị val cần xoá.
if (current->next != nullptr): Sau vòng lặp, nếu current->next không phải nullptr, nghĩa là chúng ta đã tìm thấy Node có giá trị val (Node đó là current->next).
Node* toDelete = current->next;: Lưu lại Node cần xoá để giải phóng bộ nhớ sau.
current->next = toDelete->next;: Đây là bước quan trọng để xoá Node khỏi danh sách về mặt logic. Con trỏ next của Node trước Node cần xoá (current) giờ đây trỏ thẳng tới Node sau Node cần xoá (toDelete->next), hiệu quả là bỏ qua toDelete.
delete toDelete;: Giải phóng bộ nhớ.
Phần else xử lý khi vòng lặp kết thúc mà không tìm thấy giá trị (chỉ đến cuối danh sách).

Thao tác này có độ phức tạp thời gian là O(n) vì trong trường hợp xấu nhất (Node cần xoá ở cuối hoặc không tồn tại), chúng ta phải duyệt toàn bộ danh sách.

4. Duyệt danh sách (Traversal)

Duyệt danh sách là thao tác đi qua từng Node một, thường để in ra dữ liệu hoặc thực hiện một hành động nào đó trên mỗi Node.

Logic:

Bắt đầu từ head.
Đi qua từng Node bằng cách theo con trỏ next.
Dừng lại khi gặp nullptr.

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtHead(int val) { /* ... */ } // Đã nêu ở trên
    void insertAtTail(int val) { /* ... */ } // Đã nêu ở trên
    void deleteHead() { /* ... */ }         // Đã nêu ở trên
    void deleteByValue(int val) { /* ... */ } // Đã nêu ở trên

    // Hàm hiển thị (duyệt) danh sách
    void display() {
        if (head == nullptr) {
            cout << "Danh sach rong.\n";
            return;
        }

        Node* current = head; // Bắt đầu từ head
        cout << "Danh sach: ";
        while (current != nullptr) { // Lặp cho đến khi gặp nullptr (cuối danh sách)
            cout << current->data << " -> "; // In dữ liệu của Node hiện tại
            current = current->next;             // Di chuyển tới Node kế tiếp
        }
        cout << "nullptr\n"; // Dấu hiệu kết thúc danh sách
    }

    // ... các thao tác khác ...

    ~LinkedList() { /* ... */ } // Hàm huỷ đã nêu ở trên
};

Giải thích:

if (head == nullptr): Kiểm tra danh sách rỗng.
Node* current = head;: Sử dụng một con trỏ current để không làm mất vị trí của head.
while (current != nullptr): Vòng lặp tiếp tục miễn là current vẫn trỏ đến một Node hợp lệ (chưa phải cuối danh sách).
cout << current->data << " -> ";: In dữ liệu của Node hiện tại.
current = current->next;: Di chuyển con trỏ current sang Node kế tiếp.
cout << "nullptr\n";: In nullptr để biểu thị điểm kết thúc của danh sách.

Thao tác này có độ phức tạp thời gian là O(n) vì nó cần thăm tất cả n Node trong danh sách.

5. Tìm kiếm phần tử (Searching)

Tìm kiếm một giá trị cụ thể trong danh sách liên kết cũng tương tự như duyệt, nhưng dừng lại khi tìm thấy giá trị.

Logic:

Bắt đầu từ head.
Duyệt qua từng Node.
Tại mỗi Node, kiểm tra xem dữ liệu của nó có khớp với giá trị cần tìm không.
Nếu khớp, trả về true (hoặc con trỏ đến Node đó).
Nếu duyệt hết danh sách mà không tìm thấy, trả về false (hoặc nullptr).

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void insertAtHead(int val) { /* ... */ } // Đã nêu ở trên
    void insertAtTail(int val) { /* ... */ } // Đã nêu ở trên
    void deleteHead() { /* ... */ }         // Đã nêu ở trên
    void deleteByValue(int val) { /* ... */ } // Đã nêu ở trên
    void display() { /* ... */ }            // Đã nêu ở trên

    // Hàm tìm kiếm giá trị trong danh sách
    bool search(int val) {
        Node* current = head; // Bắt đầu từ head
        while (current != nullptr) { // Lặp cho đến khi gặp nullptr
            if (current->data == val) { // Nếu tìm thấy giá trị
                return true; // Trả về true ngay lập tức
            }
            current = current->next; // Di chuyển tới Node kế tiếp
        }
        return false; // Nếu lặp xong mà không tìm thấy
    }

    ~LinkedList() { /* ... */ } // Hàm huỷ đã nêu ở trên
};

Giải thích:

Bắt đầu từ head với con trỏ current.
Vòng lặp while (current != nullptr) duyệt qua từng Node.
if (current->data == val): Kiểm tra dữ liệu của Node hiện tại. Nếu khớp, trả về true.
current = current->next;: Di chuyển đến Node kế tiếp.
Nếu vòng lặp kết thúc mà không tìm thấy giá trị, hàm trả về false.

Thao tác này có độ phức tạp thời gian là O(n) trong trường hợp xấu nhất (giá trị ở cuối hoặc không tồn tại) và O(1) trong trường hợp tốt nhất (giá trị ở đầu).

6. Ví dụ minh hoạ tổng hợp

Hãy cùng xem một ví dụ nhỏ sử dụng tất cả các thao tác cơ bản chúng ta vừa học.

#include <iostream> // Cần cho cout

// Định nghĩa cấu trúc của một Node (như trên)
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Class LinkedList với các phương thức (như trên)
class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    // Các phương thức insert, delete, display, search đã định nghĩa ở trên
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
        cout << "Da them " << val << " vao dau danh sach.\n";
    }

    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
            cout << "Da them " << val << " vao danh sach rong (tro thanh head).\n";
            return;
        }
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
        cout << "Da them " << val << " vao cuoi danh sach.\n";
    }

    void deleteHead() {
        if (head == nullptr) {
            cout << "Danh sach rong, khong the xoa dau.\n";
            return;
        }
        Node* oldHead = head;
        head = head->next;
        delete oldHead;
        cout << "Da xoa Node dau danh sach.\n";
    }

    void deleteByValue(int val) {
        if (head == nullptr) {
            cout << "Danh sach rong, khong the xoa.\n";
            return;
        }
        if (head->data == val) {
            Node* temp = head;
            head = head->next;
            delete temp;
            cout << "Da xoa Node dau co gia tri " << val << ".\n";
            return;
        }
        Node* current = head;
        while (current->next != nullptr && current->next->data != val) {
            current = current->next;
        }
        if (current->next != nullptr) {
            Node* toDelete = current->next;
            current->next = toDelete->next;
            delete toDelete;
            cout << "Da xoa Node co gia tri " << val << ".\n";
        } else {
            cout << "Khong tim thay Node co gia tri " << val << " de xoa.\n";
        }
    }

    void display() {
        if (head == nullptr) {
            cout << "Danh sach rong.\n";
            return;
        }
        Node* current = head;
        cout << "Danh sach: ";
        while (current != nullptr) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "nullptr\n";
    }

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

    // Hàm huỷ (như trên)
    ~LinkedList() {
        Node* current = head;
        Node* next;
        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
    }
};

int main() {
    LinkedList myShoppingList; // Tạo một danh sách liên kết mới

    // Thêm một vài mặt hàng vào cuối danh sách
    myShoppingList.insertAtTail(10); // Trở thành head vì list rỗng
    myShoppingList.insertAtTail(20);
    myShoppingList.insertAtTail(30);
    myShoppingList.display(); // Output: Danh sach: 10 -> 20 -> 30 -> nullptr

    // Thêm một mặt hàng vào đầu danh sách
    myShoppingList.insertAtHead(5);
    myShoppingList.display(); // Output: Danh sach: 5 -> 10 -> 20 -> 30 -> nullptr

    // Tìm kiếm mặt hàng
    cout << "\nKet qua tim kiem 20: " << (myShoppingList.search(20) ? "Tim thay" : "Khong tim thay") << endl; // Output: Tim thay
    cout << "Ket qua tim kiem 100: " << (myShoppingList.search(100) ? "Tim thay" : "Khong tim thay") << endl; // Output: Khong tim thay

    // Xoá mặt hàng đầu danh sách
    cout << "\nXoa dau danh sach...\n";
    myShoppingList.deleteHead(); // Xoá 5
    myShoppingList.display(); // Output: Danh sach: 10 -> 20 -> 30 -> nullptr

    // Xoá một mặt hàng theo giá trị
    cout << "\nXoa gia tri 20...\n";
    myShoppingList.deleteByValue(20); // Xoá 20
    myShoppingList.display(); // Output: Danh sach: 10 -> 30 -> nullptr

    cout << "\nThu xoa gia tri 50 (khong ton tai)...\n";
    myShoppingList.deleteByValue(50); // Thử xoá 50 (không có)
    myShoppingList.display(); // Output: Khong tim thay Node co gia tri 50 de xoa.\n Danh sach: 10 -> 30 -> nullptr

    cout << "\nXoa gia tri 10 (Node dau hien tai)...\n";
    myShoppingList.deleteByValue(10); // Xoá 10 (Node đầu hiện tại)
    myShoppingList.display(); // Output: Da xoa Node dau co gia tri 10.\n Danh sach: 30 -> nullptr

    cout << "\nXoa gia tri 30 (Node cuoi hien tai)...\n";
    myShoppingList.deleteByValue(30); // Xoá 30 (Node cuối hiện tại)
    myShoppingList.display(); // Output: Da xoa Node co gia tri 30.\n Danh sach rong.

    cout << "\nThu xoa dau khi danh sach rong...\n";
    myShoppingList.deleteHead(); // Thử xoá khi danh sách rỗng

    return 0;
}

Giải thích: Đoạn code main này minh hoạ việc sử dụng các phương thức insertAtTail, insertAtHead, display, search, deleteHead, và deleteByValue theo một trình tự logic, cho thấy cách danh sách thay đổi sau mỗi thao tác. Chú ý cách các thông báo được in ra giúp bạn dễ dàng theo dõi từng bước. Hàm ~LinkedList() sẽ tự động chạy khi myShoppingList kết thúc phạm vi tồn tại (cuối main), đảm bảo bộ nhớ được giải phóng sạch sẽ.

Bài tập ví dụ: C++ Bài 21.A2: Về đích

Về đích

Mô tả

FullHouse Dev đã có được vị trí mơ ước trong đội đua F1 và giành được vị trí thứ 3 trong cuộc đua ra mắt của mình. Bây giờ anh ấy muốn biết khoảng cách thời gian giữa mình và người chiến thắng của cuộc đua.

Bạn là kỹ sư trưởng của FullHouse Dev và bạn chỉ biết khoảng cách thời gian giữa FullHouse Dev và người về nhì của cuộc đua, được cho là A giây, và khoảng cách thời gian giữa người về nhì và người chiến thắng của cuộc đua, được cho là B giây.

Hãy tính toán và thông báo cho FullHouse Dev về khoảng cách thời gian giữa anh ấy và người chiến thắng của cuộc đua.

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 A và B cách nhau bởi dấu cách, lần lượt là khoảng cách thời gian giữa FullHouse Dev và người về nhì, và khoảng cách thời gian giữa người về nhì và người chiến thắng.

Output

Với mỗi test case, in ra một số nguyên - khoảng cách thời gian giữa FullHouse Dev và người chiến thắng của cuộc đua.

Constraints

1 ≤ T ≤ 100
1 ≤ A, B ≤ 10

Sample

Input	Output
4
1 1	2
2 5	7
3 2	5
5 6	11

Giải thích

Test case 1: Khoảng cách thời gian giữa FullHouse Dev và người về nhì là 1 giây. Khoảng cách thời gian giữa người về nhì và người chiến thắng là 1 giây. Do đó, khoảng cách thời gian giữa FullHouse Dev và người chiến thắng là 1 + 1 = 2 giây.
Test case 2: Khoảng cách thời gian giữa FullHouse Dev và người về nhì là 2 giây. Khoảng cách thời gian giữa người về nhì và người chiến thắng là 5 giây. Do đó, khoảng cách thời gian giữa FullHouse Dev và người chiến thắng là 2 + 5 = 7 giây.
Test case 3: Khoảng cách thời gian giữa FullHouse Dev và người về nhì là 3 giây. Khoảng cách thời gian giữa người về nhì và người chiến thắng là 2 giây. Do đó, khoảng cách thời gian giữa FullHouse Dev và người chiến thắng là 3 + 2 = 5 giây.
Test case 4: Khoảng cách thời gian giữa FullHouse Dev và người về nhì là 5 giây. Khoảng cách thời gian giữa người về nhì và người chiến thắng là 6 giây. Do đó, khoảng cách thời gian giữa FullHouse Dev và người chiến thắng là 5 + 6 = 11 giây. Chào bạn, đây là hướng dẫn giải bài tập "Về đích" bằng C++ theo yêu cầu, tập trung vào hướng giải và sử dụng các thành phần chuẩn của thư viện C++:

Phân tích bài toán:
- Bài toán cho biết hai thông tin:
  - Khoảng thời gian A: FullHouse Dev (về đích thứ 3) chậm hơn người về đích thứ 2 là A giây.
  - Khoảng thời gian B: Người về đích thứ 2 chậm hơn người về đích thứ nhất là B giây.
- Yêu cầu: Tính tổng khoảng thời gian FullHouse Dev chậm hơn người về đích thứ nhất.
- Logíc rất đơn giản: Nếu người thứ 3 chậm hơn người thứ 2 là A giây, và người thứ 2 lại chậm hơn người thứ 1 là B giây, thì tổng cộng người thứ 3 sẽ chậm hơn người thứ 1 là A + B giây.
Cấu trúc chương trình C++:
- Chương trình sẽ cần đọc số lượng test case T.
- Sau đó, chương trình sẽ lặp lại T lần.
- Trong mỗi lần lặp (mỗi test case):
  - Đọc hai số nguyên A và B từ input.
  - Tính tổng A + B.
  - In kết quả ra màn hình.
Các thành phần C++ cần sử dụng:
- Input/Output: Sử dụng thư viện chuẩn <iostream> để đọc dữ liệu từ đầu vào (standard input) và in kết quả ra đầu ra (standard output).
  - Dùng cin để đọc các giá trị T, A, và B.
  - Dùng cout để in kết quả.
  - Dùng endl hoặc '\n' để xuống dòng sau mỗi kết quả của test case.
- Biến: Khai báo các biến kiểu số nguyên (ví dụ: int) để lưu trữ T, A, B, và kết quả tính toán (A + B). Do ràng buộc A, B <= 10, tổng A+B sẽ không vượt quá 20, nên kiểu int là đủ.
- Vòng lặp: Sử dụng cấu trúc vòng lặp như for hoặc while để xử lý T test case. Vòng lặp while (T--) là một cách viết ngắn gọn thường dùng trong các bài có số lượng test case cố định ban đầu.
Hướng dẫn triển khai cụ thể (không code hoàn chỉnh):
- Bắt đầu với hàm main().
- Bao gồm header <iostream>.
- Trong main, khai báo một biến T kiểu int.
- Đọc giá trị của T bằng cin.
- Sử dụng một vòng lặp (ví dụ: while (T--)) để thực hiện các thao tác cho mỗi test case. Vòng lặp này sẽ chạy T lần và sau mỗi lần lặp giá trị của T sẽ giảm đi 1.
- Bên trong vòng lặp:
  - Khai báo hai biến A và B kiểu int.
  - Đọc giá trị của A và B từ một dòng input bằng cin >> A >> B;.
  - Tính tổng A + B.
  - In kết quả tính được bằng cout, theo sau là endl để đảm bảo mỗi kết quả nằm trên một dòng riêng biệt.
- Hàm main kết thúc sau khi vòng lặp hoàn thành.

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

Comments

There are no comments at the moment.