Giới thiệu về Danh sách Tuần tự (Sequential List)

Danh sách tuần tự, hay còn gọi là danh sách dựa trên mảng (Array-based List), là một cấu trúc dữ liệu tuyến tính trong đó các phần tử được lưu trữ tại các vị trí bộ nhớ liên tiếp. Đặc điểm này cho phép truy cập ngẫu nhiên (random access) với độ phức tạp thời gian O(1), nhưng việc chèn hoặc xóa phần tử ở giữa danh sách đòi hỏi phải dịch chuyển các phần tử còn lại, dẫn đến độ phức tạp O(n).

Bài viết này sẽ hướng dẫn cách thiết kế và triển khai một cấu trúc danh sách tuần tự hoàn chỉnh bằng ngôn ngữ C++, bao gồm các thao tác cơ bản như khởi tạo, chèn, xóa, cùng với một số thuật toán xử lý dữ liệu nâng cao như phân hoạch chẵn/lẻ và trộn hai danh sách đã sắp xếp.

Định nghĩa Cấu trúc Dữ liệu

Thay vì sử dụng các macro và định nghĩa kiểu cũ, chúng ta sẽ sử dụng struct trong C++ để đóng gói trạng thái của danh sách, bao gồm con trỏ trỏ đến vùng nhớ động, chiều dài hiện tại và sức chứa tối đa.

#include <iostream>
#include <algorithm>
#include <stdexcept>

const int DEFAULT_CAPACITY = 100;

struct SeqList {
    int* data;      // Con trỏ trỏ đến mảng động lưu trữ các phần tử
    int length;     // Số lượng phần tử thực tế hiện có
    int capacity;   // Sức chứa tối đa của mảng hiện tại
};

Triển khai Các Thao tác Cơ bản

Các hàm dưới đây xử lý việc cấp phát bộ nhớ, giải phóng bộ nhớ, chèn phần tử tại một vị trí cụ thể, xóa theo chỉ mục và xóa theo giá trị. Lưu ý rằng việc kiểm tra điều kiện biên (boundary conditions) là rất quan trọng để tránh lỗi truy cập bộ nhớ (segmentation fault).

// Khởi tạo danh sách với sức chứa mặc định hoặc tùy chỉnh
bool initializeList(SeqList& list, int cap = DEFAULT_CAPACITY) {
    list.data = new int[cap];
    if (!list.data) return false;
    list.length = 0;
    list.capacity = cap;
    return true;
}

// Giải phóng bộ nhớ động để tránh rò rỉ bộ nhớ (memory leak)
void destroyList(SeqList& list) {
    delete[] list.data;
    list.data = nullptr;
    list.length = 0;
    list.capacity = 0;
}

// Chèn phần tử vào vị trí index (0-based index)
bool insertAtIndex(SeqList& list, int index, int value) {
    if (index < 0 || index > list.length || list.length >= list.capacity) {
        return false;
    }
    // Dịch chuyển các phần tử từ cuối danh sách về phía sau để tạo chỗ trống
    for (int i = list.length; i > index; --i) {
        list.data[i] = list.data[i - 1];
    }
    list.data[index] = value;
    list.length++;
    return true;
}

// Xóa phần tử tại vị trí index và trả về giá trị đã xóa qua tham chiếu
bool removeAtIndex(SeqList& list, int index, int& removedValue) {
    if (index < 0 || index >= list.length) return false;
    removedValue = list.data[index];
    // Dịch chuyển các phần tử phía sau lên trước để lấp đầy chỗ trống
    for (int i = index; i < list.length - 1; ++i) {
        list.data[i] = list.data[i + 1];
    }
    list.length--;
    return true;
}

// Xóa tất cả các phần tử có giá trị bằng target
int removeByValue(SeqList& list, int target) {
    int writeIdx = 0;
    int removedCount = 0;
    for (int readIdx = 0; readIdx < list.length; ++readIdx) {
        if (list.data[readIdx] != target) {
            list.data[writeIdx++] = list.data[readIdx];
        } else {
            removedCount++;
        }
    }
    list.length = writeIdx;
    return removedCount;
}

// Hiển thị các phần tử trong danh sách
void printList(const SeqList& list) {
    std::cout << "Danh sach hien tai: ";
    for (int i = 0; i < list.length; ++i) {
        std::cout << list.data[i] << " ";
    }
    std::cout << std::endl;
}

Các Thuật toán Xử lý Dữ liệu Nâng cao

Ngoài các thao tác CRUD cơ bản, danh sách tuần tự thường được sử dụng để triển khai các thuật toán sắp xếp và trộn dữ liệu. Dưới đây là các thuật toán phân hoạch số chẵn/lẻ, xây dựng danh sách có thứ tự và trộn hai danh sách.

1. Phân hoạch Số lẻ và Số chẵn

Thuật toán này sắp xếp lại danh sách sao cho tất cả các số lẻ nằm ở nửa đầu và số chẵn nằm ở nửa sau. Chúng ta sử dụng kỹ thuật hai con trỏ (two-pointer) để đạt được độ phức tạp thời gian O(n) và không tốn thêm bộ nhớ phụ (in-place).

void partitionOddEven(SeqList& list) {
    int left = 0;
    int right = list.length - 1;
    
    while (left < right) {
        // Tìm phần tử chẵn từ trái sang
        while (left < right && list.data[left] % 2 != 0) left++;
        // Tìm phần tử lẻ từ phải sang
        while (left < right && list.data[right] % 2 == 0) right--;
        
        // Hoán đổi nếu tìm thấy cặp nghịch thế
        if (left < right) {
            std::swap(list.data[left], list.data[right]);
            left++;
            right--;
        }
    }
}

2. Chèn Phần tử vào Danh sách Đã Sắp xếp

Để xây dựng một danh sách luôn duy trì trạng thái tăng dần, mỗi khi thêm một phần tử mới, ta cần tìm vị trí thích hợp và dịch chuyển các phần tử lớn hơn về phía sau.

void buildSortedlist(SeqList& list, int n) {
    std::cout << "Nhap " << n << " phan tu: ";
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        
        int pos = list.length - 1;
        // Tìm vị trí chèn và dịch chuyển phần tử
        while (pos >= 0 && list.data[pos] > val) {
            list.data[pos + 1] = list.data[pos];
            pos--;
        }
        list.data[pos + 1] = val;
        list.length++;
    }
}

3. Trộn Hai Danh sách Đã Sắp xếp

Cho hai danh sách A và B đã được sắp xếp theo thứ tự không giảm, thuật toán dưới đây sẽ trộn chúng thành một danh sách C mới bằng cách so sánh từng cặp phần tử và đưa phần tử nhỏ hơn vào danh sách kết quả.

void mergeSortedLists(const SeqList& listA, const SeqList& listB, SeqList& listC) {
    if (listC.data) delete[] listC.data; // Dọn dẹp bộ nhớ cũ nếu có
    
    listC.capacity = listA.length + listB.length;
    listC.data = new int[listC.capacity];
    listC.length = 0;

    int i = 0, j = 0;
    while (i < listA.length && j < listB.length) {
        if (listA.data[i] <= listB.data[j]) {
            listC.data[listC.length++] = listA.data[i++];
        } else {
            listC.data[listC.length++] = listB.data[j++];
        }
    }
    // Sao chép các phần tử còn lại (nếu có)
    while (i < listA.length) listC.data[listC.length++] = listA.data[i++];
    while (j < listB.length) listC.data[listC.length++] = listB.data[j++];
}

Chương trình Chính và Menu Tương tác

Hàm main dưới đây tích hợp tất cả các hàm đã triển khai vào một giao diện menu điều khiển bằng console, cho phép người dùng kiểm thử từng chức năng một cách trực quan.

void displayMenu() {
    std::cout << "\n=== MENU THAO TAC DANH SACH TUAN TU ===\n";
    std::cout << "1. Tao danh sach moi\n";
    std::cout << "2. Hien thi danh sach\n";
    std::cout << "3. Xoa phan tu tai vi tri i\n";
    std::cout << "4. Xoa phan tu co gia tri x\n";
    std::cout << "5. Sap xep le truoc, chan sau\n";
    std::cout << "6. Tao danh sach tang dan\n";
    std::cout << "7. Tron hai danh sach tang dan\n";
    std::cout << "0. Thoat\n";
    std::cout << "Lua chon cua ban: ";
}

int main() {
    int choice, n, index, value;
    SeqList mainList = {nullptr, 0, 0};
    SeqList listA = {nullptr, 0, 0};
    SeqList listB = {nullptr, 0, 0};
    SeqList listC = {nullptr, 0, 0};

    initializeList(mainList);

    do {
        displayMenu();
        std::cin >> choice;

        switch (choice) {
            case 1: {
                std::cout << "Nhap so luong phan tu: ";
                std::cin >> n;
                mainList.length = 0; // Reset list
                std::cout << "Nhap " << n << " phan tu: ";
                for (int i = 0; i < n; ++i) {
                    std::cin >> mainList.data[i];
                    mainList.length++;
                }
                std::cout << "Da tao danh sach thanh cong.\n";
                break;
            }
            case 2:
                printList(mainList);
                break;
            case 3:
                std::cout << "Nhap vi tri can xoa (0-based): ";
                std::cin >> index;
                if (removeAtIndex(mainList, index, value)) {
                    std::cout << "Da xoa phan tu co gia tri: " << value << "\n";
                } else {
                    std::cout << "Vi tri khong hop le.\n";
                }
                break;
            case 4:
                std::cout << "Nhap gia tri can xoa: ";
                std::cin >> value;
                int removedCount = removeByValue(mainList, value);
                std::cout << "Da xoa " << removedCount << " phan tu.\n";
                printList(mainList);
                break;
            case 5:
                partitionOddEven(mainList);
                std::cout << "Danh sach sau khi phan hoach:\n";
                printList(mainList);
                break;
            case 6:
                std::cout << "Nhap so luong phan tu cho danh sach tang dan: ";
                std::cin >> n;
                mainList.length = 0; // Reset list
                buildSortedlist(mainList, n);
                printList(mainList);
                break;
            case 7:
                std::cout << "-- Tao danh sach A --\n";
                std::cout << "Nhap so luong phan tu cho A: ";
                std::cin >> n;
                initializeList(listA, n);
                buildSortedlist(listA, n);
                
                std::cout << "-- Tao danh sach B --\n";
                std::cout << "Nhap so luong phan tu cho B: ";
                std::cin >> n;
                initializeList(listB, n);
                buildSortedlist(listB, n);
                
                mergeSortedLists(listA, listB, listC);
                std::cout << "Danh sach C sau khi tron:\n";
                printList(listC);
                break;
            case 0:
                std::cout << "Thoat chuong trinh.\n";
                break;
            default:
                std::cout << "Lua chon khong hop le. Vui long nhap lai.\n";
        }
    } while (choice != 0);

    // Giải phóng bộ nhớ trước khi kết thúc
    destroyList(mainList);
    destroyList(listA);
    destroyList(listB);
    destroyList(listC);

    return 0;
}