自己写的又臭又长~~~~哭了
样例
#include<iostream>
using namespace std;
const int N=100010;
struct Node{
int data;
int pre;
int next;
};
Node lst[N];
int head,tail;
int pos;
void init(){
head=-1;
tail=-1;
pos=0;
}
void head_add(int a){
if(head==-1&&tail==-1){
lst[pos].data=a;
lst[pos].pre=-1;
lst[pos].next=-1;
head=pos;
tail=pos;
pos++;
}else{
lst[pos].data=a;
lst[pos].pre=-1;
lst[pos].next=head;
lst[head].pre=pos;
head=pos;
pos++;
}
}
void tail_add(int a){
if(head==-1&&tail==-1){
lst[pos].data=a;
lst[pos].pre=-1;
lst[pos].next=-1;
head=pos;
tail=pos;
pos++;
}else{
lst[pos].data=a;
lst[pos].pre=tail;
lst[pos].next=-1;
lst[tail].next=pos;
tail=pos;
pos++;
}
}
void del(int k){
if(head==tail&&head!=-1){//如果当前链表长度为1
head=-1;
tail=-1;
}else if(head==(k-1)){//如果删掉的元素在头或者尾部,要修改head和tail
// cout<<head<<"?????";
lst[lst[head].next].pre=-1;
head=lst[k-1].next;
}else if(tail==(k-1)){
lst[lst[tail].pre].next=-1;
tail=lst[k-1].pre;
}
else{
lst[lst[k-1].pre].next=lst[k-1].next;
lst[lst[k-1].next].pre=lst[k-1].pre;
}
}
void pre_insert(int k,int a){
if(lst[k-1].pre==-1){
head_add(a);
}else{
lst[pos].data=a;
lst[pos].next=k-1;
lst[pos].pre=lst[k-1].pre;
lst[lst[k-1].pre].next=pos;
lst[k-1].pre=pos;
pos++;
}
}
void next_insert(int k,int a){
if(lst[k-1].next==-1){
tail_add(a);
}else{
lst[pos].data=a;
lst[pos].pre=k-1;
lst[pos].next=lst[k-1].next;
lst[lst[k-1].next].pre=pos;
lst[k-1].next=pos;
pos++;
}
}
int main(){
int m;
cin>>m;
init();
for(int i=0;i<m;i++){
char op;
int k,a;
cin>>op;
if(op=='L'){
cin>>a;
head_add(a);
}
else if(op=='R'){
cin>>a;
tail_add(a);
}
else if(op=='D'){
cin>>k;
del(k);
}
else if(op=='I'){
char op2;
cin>>op2;
cin>>k>>a;
if(op2=='L'){
pre_insert(k,a);
}
else if(op2=='R'){
next_insert(k,a);
}
}
//调试一下
// cout<<head<<' '<<tail<<endl;;
// for(int j=0;j<pos;j++){
// cout<<lst[j].pre<<' '<<lst[j].data<<' '<<lst[j].next<<endl;
// }
}
int p=head;
while(p!=-1)
{
cout<<lst[p].data<<' ';
if(p==tail){
break;
}
p=lst[p].next;
}
return 0;
}
调试过程中遇到的几个注意的点:
- 删除元素时需要处理删除的结点如果是头结点或者尾部结点,则需要修改head和tail伪指针
- 判断相等打错了几个==和=
- 插入别忘了pos++
- main函数忘记调用init()函数初始化参数