1. Khái niệm về danh sách liên tiếp

Danh sách liên tiếp là một cấu trúc dữ liệu cơ bản, sử dụng bộ nhớ liên tục để lưu trữ các phần tử. Nó có thể tự động điều chỉnh kích thước dựa trên số lượng phần tử cần lưu trữ. Bài viết này sẽ hướng dẫn cách triển khai các thao tác như khởi tạo, thêm, xóa, sửa, đọc/ghi file cho danh sách liên tiếp.

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

// Định nghĩa cấu trúc danh sách liên tiếp (cho kiểu int)
typedef struct {
    int* arr;       // Con trỏ tới mảng chứa dữ liệu
    int count;      // Số phần tử hiện tại trong danh sách
    int max_size;  // Kích thước tối đa của mảng
} List;

// Các hàm chức năng
int createList(List* list); // Khởi tạo danh sách
int resizeList(List* list); // Thay đổi kích thước danh sách
int checkCapacity(List* list); // Kiểm tra dung lượng

int addElement(List* list, int value); // Thêm phần tử vào cuối
int prependElement(List* list, int value); // Thêm phần tử vào đầu

int removeFirst(List* list); // Xóa phần tử đầu tiên
int removeLast(List* list); // Xóa phần tử cuối cùng

void clearList(List* list); // Xóa toàn bộ dữ liệu
void printList(List* list); // In ra danh sách
void destroyList(List* list); // Huỷ danh sách

// Đọc ghi file
int saveListToFile(List* list, const char* path); // Lưu danh sách vào file
int loadListFromFile(List* list, const char* path); // Đọc danh sách từ file

// Tìm kiếm, chèn, xóa
int searchValue(List* list, int value); // Tìm kiếm giá trị
void insertAt(List* list, size_t pos, int value); // Chèn tại vị trí
void eraseAt(List* list, size_t pos); // Xóa tại vị trí
void updateAt(List* list, size_t pos, int value); // Cập nhật tại vị trí

Mã nguồn trên cung cấp cái nhìn tổng quan về các thành phần chính của danh sách liên tiếp.

2. Cấu trúc danh sách liên tiếp

Cấu trúc danh sách bao gồm ba yếu tố chính:

• arr: Mảng động lưu trữ dữ liệu.
• count: Số lượng phần tử hiện tại.
• max_size: Kích thước tối đa của mảng.

2.1. Khởi tạo danh sách

Hàm khởi tạo sẽ phân bổ bộ nhớ ban đầu cho mảng và thiết lập các thông số ban đầu.

#define INITIAL_SIZE 4

int createList(List* list) {
    assert(list);
    list->arr = (int*)malloc(INITIAL_SIZE * sizeof(int));
    if (!list->arr) {
        printf("Không thể cấp phát bộ nhớ!\n");
        return -1;
    }
    list->count = 0;
    list->max_size = INITIAL_SIZE;
    return 0;
}

2.2. Điều chỉnh kích thước

Khi số lượng phần tử vượt quá dung lượng hiện tại, cần tăng kích thước mảng.

static int resizeList(List* list) {
    assert(list);
    int new_max = list->max_size * 2;
    int* new_arr = (int*)realloc(list->arr, new_max * sizeof(int));
    if (!new_arr) {
        printf("Không thể mở rộng danh sách!\n");
        return -1;
    }
    list->arr = new_arr;
    list->max_size = new_max;
    return 0;
}

int checkCapacity(List* list) {
    if (list->count == list->max_size) {
        return resizeList(list);
    }
    return 0;
}

2.3. Thêm/xóa phần tử

Thêm phần tử vào cuối danh sách:

int addElement(List* list, int value) {
    if (checkCapacity(list)) return -1;
    list->arr[list->count++] = value;
    return 0;
}

Thêm phần tử vào đầu danh sách:

int prependElement(List* list, int value) {
    if (checkCapacity(list)) return -1;
    for (int i = list->count; i > 0; --i) {
        list->arr[i] = list->arr[i - 1];
    }
    list->arr[0] = value;
    list->count++;
    return 0;
}

Xóa phần tử cuối cùng:

int removeLast(List* list) {
    if (list->count == 0) return -1;
    list->count--;
    return 0;
}

Xóa phần tử đầu tiên:

int removeFirst(List* list) {
    if (list->count == 0) return -1;
    for (int i = 0; i < list->count - 1; ++i) {
        list->arr[i] = list->arr[i + 1];
    }
    list->count--;
    return 0;
}

3. Lưu và tải dữ liệu từ file

Chức năng lưu và tải giúp lưu trữ dữ liệu giữa các phiên làm việc.

int saveListToFile(List* list, const char* path) {
    FILE* f = fopen(path, "w");
    if (!f) {
        printf("Không thể mở file %s!\n", path);
        return -1;
    }
    for (int i = 0; i < list->count; ++i) {
        fprintf(f, "%d\n", list->arr[i]);
    }
    fclose(f);
    return 0;
}

int loadListFromFile(List* list, const char* path) {
    clearList(list);
    FILE* f = fopen(path, "r");
    if (!f) {
        printf("File %s không tồn tại!\n", path);
        return -1;
    }
    int val;
    while (fscanf(f, "%d", &val) == 1) {
        addElement(list, val);
    }
    fclose(f);
    return 0;
}

4. Ví dụ thực hành

#include "list.h"
int main() {
    List my_list;
    createList(&my_list);

    addElement(&my_list, 5);
    addElement(&my_list, 10);
    addElement(&my_list, 15);

    printList(&my_list);

    saveListToFile(&my_list, "data.txt");
    clearList(&my_list);
    loadListFromFile(&my_list, "data.txt");

    destroyList(&my_list);
    return 0;
}