Nguồn: Bài toán Mẫu

Thẻ thuật toán: Danh sách liên kết

Mô tả bài toán

Thực hiện một danh sách liên kết đơn, danh sách ban đầu rỗng, hỗ trợ ba thao tác:

(1) Chèn một số vào đầu danh sách;

(2) Xóa số đứng sau số thứ k được chèn;

(3) Chèn một số sau số thứ k được chèn

Bây giờ cần thực hiện M thao tác trên danh sách liên kết này, sau khi hoàn thành tất cả các thao tác, xuất toàn bộ danh sách liên kết từ đầu đến cuối.

Lưu ý: Số thứ k được chèn trong bài toán không phải là số thứ k trong danh sách liên kết hiện tại. Ví dụ, trong quá trình thực hiện, nếu đã chèn tổng cộng n số, thì theo thứ tự thời gian chèn, n số này lần lượt là: số thứ 1 được chèn, số thứ 2 được chèn, ... số thứ n được chèn.

Định dạng đầu vào

Dòng đầu tiên chứa số nguyên M, biểu thị số lần thao tác.

M dòng tiếp theo, mỗi dòng chứa một lệnh thao tác, lệnh thao tác có thể là một trong các loại sau:

(1) "H x", biểu thị chèn một số x vào đầu danh sách.

(2) "D k", biểu thị xóa số đứng sau số thứ k được nhập (khi k bằng 0, biểu thị xóa nút đầu).

(3) "I k x", biểu thị chèn một số x sau số thứ k được nhập (trong thao tác này, k luôn lớn hơn 0).

Định dạng đầu ra

Chỉ một dòng, xuất toàn bộ danh sách liên kết từ đầu đến cuối.

Phạm vi dữ liệu

1≤M≤100000 Tất cả các thao tác đảm bảo hợp lệ.

Ví dụ đầu vào:

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

Ví dụ đầu ra:

6 4 6 5

Phương pháp giải

Tại sao sử dụng mảng tĩnh để mô phỏng danh sách liên kết? Sử dụng mảng tĩnh để mô phỏng danh sách liên kết có thể giảm thời gian truy cập từ o(n) động xuống o(1); Trong các cuộc thi lập trình, thường hy sinh một phần không gian để đổi lấy thời gian hiệu quả.

Xóa dữ liệu thứ t:

Kết nối mảng liên kết tại vị trí hiện tại với mảng liên kết của mảng liên kết tương ứng.

void xoa(int t)
{
    next[t] = next[next[t]];
}

Thêm nút t tại vị trí thứ K:

Lưu giá trị t trong val[idx], nút hiện tại idx trỏ đến giá trị mà nút đầu trỏ đến, nút đầu trỏ đến nút hiện tại, giá trị nút hiện tại tăng lên 1.

void chenDau(int t)
{
    val[idx] = t;
    next[idx] = dau;
    dau = idx++;
}

Thêm nút K sau vị trí chỉ định K:

Lưu giá trị t trong val[idx], nút hiện tại idx trỏ đến nút mà nút K trỏ đến, nút K trỏ đến nút hiện tại, giá trị nút hiện tại tăng lên 1.

void chenSau(int k, int t)
{
    val[idx] = t;
    next[idx] = next[k];
    next[k] = idx++;
}

Mã C++

#include<iostream>

using namespace std;
const int MAXN = 100010;
int val[MAXN], next[MAXN], dau, idx;

void xoa(int x)
{
    next[x] = next[next[x]];
}

void chenDau(int x)
{
    val[idx] = x;
    next[idx] = dau;
    dau = idx++;    
}

void chenSau(int k, int x)
{
    val[idx] = x;
    next[idx] = next[k];
    next[k] = idx++;
}

int main()
{
    int n;
    cin >> n;
    
    dau = -1; // Khởi tạo dau = -1, idx = 0; Vì idx mặc định toàn cục là 0, dau = -1 thực chất -1 sẽ được xếp ở cuối để kết thúc danh sách liên kết
    char lenh; int t, k;
    while(n--)
    {
        cin >> lenh;
        if(lenh == 'H')
        {
            cin >> t;
            chenDau(t);
        }
        else if(lenh == 'D')
        {
            cin >> k;
            if(k == 0) dau = next[dau];
            else xoa(k-1);
        }
        else
        {
            cin >> k >> t;
            chenSau(k-1, t); // Vì chỉ số bắt đầu từ 0, nên số thứ k thực chất là k-1.
        }
    }
    for(int i = dau; i != -1; i = next[i]) cout << val[i] << " "; // Cập nhật theo cách trỏ của danh sách liên kết
    return 0;
}