Bỏ qua

Danh sách liên kết khối (Unrolled Linked List)

./images/kuaizhuanglianbiao.png

Danh sách liên kết khối (Block List) trông đại khái như thế này...

Không khó để nhận ra danh sách liên kết khối là một danh sách liên kết, mỗi nút (node) trỏ tới một mảng. Ta chia mảng có độ dài \(n\) ban đầu thành \(\sqrt{n}\) nút, mỗi nút tương ứng với một mảng có kích thước \(\sqrt{n}\). Vì vậy, ta định nghĩa cấu trúc như sau, xem mã bên dưới. Trong đó sqn biểu thị sqrt(n) tức là \(\sqrt{n}\), pb biểu thị push_back, tức là thêm một phần tử vào node này.

Thực hiện 
1
2
3
4
5
6
7
8
9
struct node {
  node* nxt;
  int size;
  char d[(sqn << 1) + 5];

  node() { size = 0, nxt = NULL, memset(d, 0, sizeof(d)); }

  void pb(char c) { d[size++] = c; }
};

Danh sách liên kết khối cần hỗ trợ tối thiểu: tách (split), chèn (insert), tìm kiếm (find). Tách là gì? Tách là chia một node thành hai node nhỏ hơn, để đảm bảo kích thước của mỗi node gần bằng \(\sqrt{n}\) (nếu không có thể thoái hóa thành mảng thông thường). Khi kích thước của một node vượt quá \(2\times \sqrt{n}\) thì thực hiện thao tác tách.

Thao tác tách được thực hiện thế nào? Đầu tiên tạo một nút mới, sau đó copy \(\sqrt{n}\) giá trị cuối cùng của nút bị tách sang nút mới, sau đó xóa \(\sqrt{n}\) giá trị cuối cùng của nút bị tách (size--), cuối cùng chèn nút mới vào sau nút bị tách là xong.

Độ phức tạp của tất cả các thao tác của danh sách liên kết khối đều là \(\sqrt{n}\).

Còn một điều cần nói nữa. Khi các phần tử được chèn (hoặc xóa), \(n\) sẽ thay đổi, \(\sqrt{n}\) cũng thay đổi. Như vậy kích thước khối sẽ thay đổi, chẳng lẽ ta phải duy trì kích thước khối mỗi lần sao?

Thực ra không cần, ta đặt \(\sqrt{n}\) là một giá trị cố định. Ví dụ phạm vi đề bài cho là \(10^6\), vậy \(\sqrt{n}\) có thể đặt là một hằng số có kích thước \(10^3\), không cần thay đổi nó.

1
list<vector<char>> orz_list;

rope trong libstdc++

Nhập

rope trong libstdc++ cũng đóng vai trò như danh sách liên kết khối, nó sử dụng cây cân bằng có tính bền vững (persistent balanced tree) để thực hiện, có thể hoàn thành các thao tác truy cập ngẫu nhiên và chèn, xóa phần tử.

Vì rope không thực sự được triển khai bằng danh sách liên kết khối, nên độ phức tạp thời gian của nó không tương đương với danh sách liên kết khối, mà tương đương với độ phức tạp của cây cân bằng có tính bền vững (tức là \(O(\log n)\)).

Có thể sử dụng cách sau để nhập:

1
2
#include <ext/rope>
using namespace __gnu_cxx;

Về hàm thư viện bắt đầu bằng hai dấu gạch dưới

Trong OI, việc có thể sử dụng hàm thư viện bắt đầu bằng hai dấu gạch dưới đã từng không chắc chắn, trong [Thông báo bổ sung về giới hạn sử dụng ngôn ngữ lập trình trong các hoạt động dòng NOI] do CCF phát hành năm 2021, có đề cập "Cho phép sử dụng các hàm hoặc macro thư viện bắt đầu bằng dấu gạch dưới, ngoại trừ các hàm và macro thư viện bị cấm rõ ràng". Do đó, hiện tại rope có thể được sử dụng bình thường trong OI.

Thao tác cơ bản

Thao tác Tác dụng
rope<int> a Khởi tạo rope (tương tự các container như vector)
a.push_back(x) Thêm phần tử x vào cuối a
a.insert(pos, x) Thêm phần tử x vào vị trí thứ pos của a
a.erase(pos, x) Xóa x phần tử tại vị trí pos của a
a.at(x) hoặc a[x] Truy cập phần tử thứ x của a
a.length() hoặc a.size() Lấy kích thước của a

Ví dụ đề bài

POJ2887 Big String

Giải thích: Đây là một bài tập mẫu rất đơn giản. Mã nguồn như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cctype>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int sqn = 1e3;

struct node {  // 定义块状链表
  node* nxt;
  int size;
  char d[(sqn << 1) + 5];

  node() { size = 0, nxt = NULL; }

  void pb(char c) { d[size++] = c; }
}* head = NULL;

char inits[(int)1e6 + 5];
int llen, q;

void readch(char& ch) {  // 读入字符
  do cin >> ch;
  while (!isalpha(ch));
}

void check(node* p) {  // 判断，记得要分裂
  if (p->size >= (sqn << 1)) {
    node* q = new node;
    for (int i = sqn; i < p->size; i++) q->pb(p->d[i]);
    p->size = sqn, q->nxt = p->nxt, p->nxt = q;
  }
}

void insert(char c, int pos) {  // 元素插入，借助链表来理解
  node* p = head;
  int tot, cnt;
  if (pos > llen++) {
    while (p->nxt != NULL) p = p->nxt;
    p->pb(c), check(p);
    return;
  }
  for (tot = head->size; p != NULL && tot < pos; p = p->nxt, tot += p->size);
  tot -= p->size, cnt = pos - tot - 1;
  for (int i = p->size - 1; i >= cnt; i--) p->d[i + 1] = p->d[i];
  p->d[cnt] = c, p->size++;
  check(p);
}

char query(int pos) {  // 查询
  node* p;
  int tot;
  for (p = head, tot = head->size; p != NULL && tot < pos;
       p = p->nxt, tot += p->size);
  tot -= p->size;
  return p->d[pos - tot - 1];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> inits >> q;
  llen = strlen(inits);
  node* p = new node;
  head = p;
  for (int i = 0; i < llen; i++) {
    if (i % sqn == 0 && i) p->nxt = new node, p = p->nxt;
    p->pb(inits[i]);
  }
  char a;
  int k;
  while (q--) {
    readch(a);
    if (a == 'Q')
      cin >> k, cout << query(k) << '\n';
    else
      readch(a), cin >> k, insert(a, k);
  }
  return 0;
}

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:HeRaNO, konnyakuxzy, littlefrog
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply