思路
- 本题的结构其实不难,只是操作过于繁琐,大量的时间花费在格式化输入上面
- 关键点之一在于如何记录输入顺序
- 第一次尝试用额外的链表进行记录,但是while读取第k个会导致在100000数据量(最后一个数据)超时
- 于是将ind链表换成ind指针数组,随机存取,AC
BUG
链表的操作比较简单,但是需要思路清晰
- 在insertLeft和Right的时候,一开始将插入操作根据头结点进行,但是封装为函数后,直接套用在了IR和IL的操作上,但其实二者是不一样的,IL和IR需要定点操作,而不是在头结点操作
- 将封装函数按照IL和IR的方式书写,L和R的操作输入改为(t->right)(t->left),AC
- 格式化输入的时候,有时候会跳过c2\a2,所以最好是在循环开始赋值0,防止后续出错
- 节点释放后要及时回归NULL,这就要求rtK函数返回的是节点的父节点(此题为ind内存的指针),方便释放后置NULL;而这样的话,其余用到rtK的操作需要注意获取一下子节点(
temp = rtK()->left
) - 需要函数封装的时候最好在一开始就设计好思路,否则以非封装的形式写完再进行封装,可能会很麻烦
代码
#include <iostream>
#include <cstring>
using namespace std;
#define INF 0xfffffff
const int N = 1e5 + 10;
int aind;
typedef struct dlist
{
dlist* left;
dlist* right;
int val;
}*pdlist;
pdlist ind[N];
pdlist rtK(int k)
{
if (ind[k] != NULL)
{
return ind[k];
}
return NULL;
}
void insertLeft(pdlist t, int x)
{
pdlist temp = new dlist;
temp->val = x;
temp->right = t;
temp->left = t->left;
t->left->right = temp;
t->left = temp;
pdlist tind = new dlist;
aind++;
tind->left = temp;
tind->val = aind;
ind[aind] = tind;
}
void insertRight(pdlist t, int x)
{
pdlist temp = new dlist;
temp->val = x;
temp->left = t;
temp->right = t->right;
t->right->left = temp;
t->right = temp;
pdlist tind = new dlist;
aind++;
tind->left = temp;
tind->val = aind;
ind[aind] = tind;
}
void setList(pdlist t, char c1, char c2, int a1, int a2)
{
if (c1 == 'I')
{
pdlist temp = rtK(a1)->left;
if (c2 == 'L')
{
// L
insertLeft(temp, a2);
}
else
{
// R
insertRight(temp, a2);
}
}
else if (c1 == 'L')
{
// L
insertLeft(t->right, a1);
}
else if (c1 == 'R')
{
// R
insertRight(t->left, a1);
}
else if (c1 == 'D')
{
// D
pdlist tind = rtK(a1);
pdlist temp = tind->left;
tind->left = NULL;
temp->left->right = temp->right;
temp->right->left = temp->left;
delete(temp);
// 应该置零
}
}
int main()
{
aind = 0;
int n, a1, a2;
char c1, c2;
cin >> n;
pdlist t;
memset(ind, 0, sizeof ind);
// ind = new dlist;
t = new dlist;
// ind->right = NULL;
// ind->left = NULL;
// ind->val = 0;
t->right = t;
t->left = t;
t->val = -1;
for (int i = 0; i < n; i++)
{
c1 = c2 = '0';
a1 = a2 = 0;
cin >> c1;
if (c1 == 'I')
{
cin >> c2;
}
cin >> a1;
if (c1 == 'I')
{
cin >> a2;
}
setList(t, c1, c2, a1, a2);
}
pdlist p = t->right;
while (p != t)
{
cout << p->val << " ";
p = p->right;
// 循环列表,需要加判断退出
}
cout << endl;
return 0;
}
/*
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
*/