Con trỏ và cấu trúc dữ liệu động trong C++

Trong lập trình C++, việc quản lý bộ nhớ và thao tác với dữ liệu động đòi hỏi sự hiểu biết rõ ràng về con trỏ. Con trỏ là biến lưu trữ địa chỉ của một vùng nhớ, cho phép truy cập và thay đổi giá trị tại địa chỉ đó một cách linh hoạt.

Khai báo và sử dụng con trỏ

Để khai báo một con trỏ trỏ đến kiểu dữ liệu nguyên int, ta sử dụng ký hiệu *:

int *ptr;
// hoặc
int* ptr;

Cả hai cách viết đều hợp lệ. Để gán địa chỉ của một biến vào con trỏ, dùng toán tử lấy địa chỉ &:

int x = 42;
int *ptr = &x; // ptr giờ chứa địa chỉ của x

Để truy cập giá trị mà con trỏ đang trỏ tới (gọi là giải tham chiếu), sử dụng lại toán tử *:

int value = *ptr; // value = 42

Quan hệ giữa mảng và con trỏ

Tên mảng thực chất là một con trỏ hằng trỏ đến phần tử đầu tiên của mảng:

int arr[] = {10, 20, 30};
int *p = arr; // p trỏ đến arr[0]

Do đó, *(p + 1) sẽ truy cập phần tử thứ hai — tương đương với arr[1].

Giá trị null cho con trỏ

Một con trỏ chưa được khởi tạo có thể trỏ đến vùng nhớ ngẫu nhiên, gây lỗi. Vì vậy, nên khởi tạo con trỏ rỗng bằng nullptr:

int *safePtr = nullptr;

Cấu trúc danh sách liên kết đơn

Danh sách liên kết là cấu trúc dữ liệu động, khắc phục các hạn chế của mảng như kích thước cố định và vùng nhớ liên tục. Mỗi nút trong danh sách chứa hai thành phần:

• data: Dữ liệu lưu trữ (ví dụ: số nguyên).
• next: Con trỏ trỏ đến nút tiếp theo, hoặc nullptr nếu là nút cuối.

Định nghĩa nút danh sách với struct

Sử dụng từ khóa struct để nhóm các thành phần lại thành một kiểu dữ liệu mới:

struct Node {
    int data;
    Node* next;

    // Hàm tạo để khởi tạo nút mới
    Node(int value) : data(value), next(nullptr) {}
};

Hàm tạo Node(int value) tự động gán giá trị cho data và đặt next là nullptr, đảm bảo trạng thái ban đầu an toàn.

Vai trò của nút giả (dummy node)

Để đơn giản hóa thao tác chèn và xóa, đặc biệt ở vị trí đầu danh sách, người ta thường thêm một nút giả làm nút đầu tiên. Nút này không chứa dữ liệu thực tế, nhưng giúp code xử lý nhất quán cho mọi vị trí chèn.

Chèn phần tử vào danh sách

Để thêm một phần tử mới vào cuối danh sách:

1. Tạo nút mới trên vùng nhớ động bằng toán tử new.
2. Liên kết nút hiện tại cuối danh sách với nút mới qua con trỏ next.
3. Cập nhật con trỏ làm việc sang nút mới.

Toán tử -> dùng để truy cập thành viên thông qua con trỏ:

Node* current = head;
Node* newNode = new Node(100);
current->next = newNode;
current = newNode;

Giải bài toán: Xây dựng và in danh sách liên kết

Yêu cầu: Viết chương trình nhận số lượng phần tử và các giá trị, xây dựng danh sách liên kết đơn, sau đó in toàn bộ giá trị ra màn hình.

#include <iostream>
using namespace std;

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

class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = new Node(0); // Nút giả
    }

    void insertAtEnd(int val) {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = new Node(val);
    }

    void display() {
        Node* current = head->next; // Bắt đầu từ nút thật đầu tiên
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};

int main() {
    int n, value;
    while (cin >> n) {
        LinkedList list;
        for (int i = 0; i < n; ++i) {
            cin >> value;
            list.insertAtEnd(value);
        }
        list.display();
    }
    return 0;
}

Chương trình sử dụng lớp LinkedList để đóng gói hành vi danh sách, bao gồm khởi tạo, chèn và hiển thị. Vòng lặp while(cin >> n) hỗ trợ xử lý nhiều bộ dữ liệu đầu vào liên tiếp.