链表
链表上操作
例题
块状链表
- 分割为\(\sqrt{n}\)块，用于数据空间发生变化的情况，方便的实现元素访问、任意位置插入、删除元素。
- 结合数组与链表，在\(O(\sqrt{n})\)时间完成常规操作：访问、插入、删除
- 常规操作后数组块元素数目会发生变化，需要进行维护操作
- 通过分割、合并操作；分割大于二倍大小的块，合并和小于标准大小的相邻块
- 插入时直接以块的形式整个插入，之后再进行维护（查找->分割->插入->维护）
- 删除时先在左右进行分割（得到要删除的单独块），之后删除块，再进行维护
- 思想：灵活进行分割与合并，以块为单位（链表节点）进行操作
- 使用list>实现
- P4008 文本编辑器
#include<bits/stdc++.h>
using namespace std;
int block = 2500; //一个块的标准大小 = sqrt(n)
list<vector<char> > List; //整体是链表，链表的每个元素是一个块
typedef list<vector<char> >::iterator it;
it Find(int &pos) { //返回块，并更新pos为这个块中的位置(下标)
for (it i = List.begin(); ;i++) { //逐个找链表上的每个块
if(i == List.end() || pos <= i->size()) return i;
pos -= i->size(); //每经过一个块，就更新x
}
}
void Output(int L, int R) { // [L, R)
it L_block = Find(L), R_block = Find(R);
for (it it1 = L_block; ; it1++){ //打印每个块
int a; it1 == L_block ? a=L : a=0; //一个块的起点
int b; it1 == R_block ? b=R : b=it1->size(); //块的终点
for (int i = a; i < b; i++) putchar(it1->at(i));
if(it1 == R_block) break; //迭代器it不能用 <= ，只有 == 和 !=
}
putchar('\n');
}
it Next(it x){return ++x; } //返回下一个块
void Merge(it x) { //合并块x和块x+1（将下一块插入到本快的末尾并删除下一块）
x->insert(x->end(), Next(x)->begin(), Next(x)->end());
List.erase(Next(x));
}
void Split(it x, int pos){ //把第x个块在这个块的pos处分成2块（在下一块插入后半部分，并删除本块中的后半部分）
if (pos == x->size()) return; //pos在这个块的末尾
List.insert(Next(x), vector<char>(x->begin() + pos, x->end()));
//把pos后面的部分划给下一个块
x->erase(x->begin() + pos, x->end()); //删除划出的部分
}
//维护块大小
void Update(){ //把每个块重新划成（近似）等长的块
for (it i = List.begin(); i != List.end(); i++){
while (i->size() >= (block << 1)) //如果块大于2个block，分开
Split(i, i->size() - block);
while (Next(i) != List.end() && i->size() + Next(i)->size() <= block)
Merge(i); //如果块+下一个块小于block，合并
while (Next(i) != List.end() && Next(i)->empty()) //删除空块
List.erase(Next(i));
}
}
void Insert(int pos, const vector<char>& ch){
it curr = Find(pos);
if (!List.empty()) Split(curr, pos); //把一个块拆为两个
List.insert(Next(curr), ch); //把字符串插到两个块中间
Update();
}
void Delete(int L, int R) { // [L, R)
it L_block, R_block;
L_block = Find(L); Split(L_block, L);
R_block = Find(R); Split(R_block, R);
R_block++;
while(Next(L_block) != R_block) List.erase(Next(L_block));
Update();
}
int main(){
vector<char> ch; int len, pos, n;
cin >> n;
while (n--) {
char opt[7]; cin >> opt;
if(opt[0]=='M') cin >> pos;
if(opt[0]=='I'){
ch.clear(); cin >> len; ch.resize(len);
for (int i = 0; i < len; i++){
ch[i] = getchar();
while(ch[i]<32||ch[i]>126) ch[i]=getchar();
} //读一个合法字符
Insert(pos, ch); //把字符串插入到链表中
}
if(opt[0]=='D'){ cin >> len; Delete(pos, pos + len); }
if(opt[0]=='G'){ cin >> len; Output(pos, pos + len); }
if(opt[0]=='P') pos--;
if(opt[0]=='N') pos++;
}
return 0;
}
题目