指针实现 链表

其实链表很早就学过了，但我当时的写法局限于数组模拟，没有考虑过指针实现（好吧其实当时也就不知道指针这个玩意）但今天突然有人在QQ上问我：为什么用指针实现的链表居然会超时（luogu P1160 队列安排）！！！然而这个题用数组模拟就可以过了。 于是我copy了一下她的源代码

#include<iostream> #include<cstdio> using namespace std; int n,m,p,k,x; bool b[100001]={0}; struct lian{ int hao; lian * front=NULL; lian * behide=NULL; }; void show(lian * head) { lian * z=head; while(z->behide!=NULL){ cout<<z->hao<<" "; z=z->behide; } cout<<z->hao; cout<<endl; } int main() { lian * head; lian * z; z=new lian; lian * my; my=new lian; my->hao=1; b[1]=1; head=my; cin>>n; for(int i=2;i<=n;i++) { my=new lian; my->hao=i; cin>>k>>p; b[i]=1; z=head; while(z->hao!=k) z=z->behide; if(p==1){ if(z->behide==NULL) { z->behide=my; my->front=z; my->behide=NULL; } else{ my->behide=z->behide; z->behide->front=my; my->front=z; z->behide=my; } } else{ if(z==head) { head=my; my->behide=z; z->front=my; } else{ my->front=z->front; z->front->behide=my; my->behide=z; z->front=my; } } //show(head); } cin>>m; for(int i=1;i<=m;i++) { cin>>x; if(b[x]==1){ z=head; while(z->hao!=x) z=z->behide; if(z->front==NULL){ head=z->behide; z->behide->front=NULL; b[z->hao]=0; } else{ if(z->behide==NULL) { z->front->behide=NULL; b[z->hao]=0; } else{ z->front->behide=NULL; z->front->behide=z->behide; z->behide->front=z->front; b[z->hao]=0; } } } //show(head); } show(head); return 0; }

看完我就震惊了 100多行的 list .

于是就有了一个指针新手调试程序的过程。

指针

其实指针还是挺好理解的，大致可以理解为你在一个变量里存了一个地址，这个地址指向了一个准确的数值，当然也可以指向另一个指针。通过指针与指针之间的相互操作，我们可以优化很多代码。

指针在定义时一般为

int *x;//定义了一个int值的指针 /* 其实也可以对结构体定义指针； */ struct node{ int val; int *l,*r;//结构体里可以包含指针 }*list[100],a;//可以定义指针指向结构体

链表的模拟

首先，根据题目要求，我需要一个双端链表； 而我特别钟爱于使用结构体 于是就有了先前的定义

struct node{ int num; node *l,*r; node(int x){//写个构造函数下面插入的时候方便 num=x; l=r=NULL; } }*list[100100];

然后便开始了模拟的过程，不管三七二十八，先写了 main 函数。

int main(){ cin>>n; int num,op; list[1]=new node(1);//用之前的构造函数，new来申请空间 for(int i=2;i<=n;i++){ list[i]=new node(i); cin>>num>>op;//插入数字 insert(num,i,op); } cin>>m; for(int i=1;i<=m;i++){ cin>>num; erase(num);//删除数字 } outputans(); return 0; }

这里还差了三样东西

插入

删除

输出

然后便开始了思考的过程

首先解决插入

由于往一个数左边加数和右边加数完全等价（或者说是逆向操作） 所以只要做出向左边加数的情况 然后向右加数的时候便可以复制粘贴了

重点看代码吧，自认为比较易懂

void insert(int num,int i,int op){ if(op){ if(list[num]->r){//判断NULL list[num]->r->l=list[i]; list[i]->r=list[num]->r; } list[num]->r=list[i]; list[i]->l=list[num]; } //下面的代码是复制过去的,吧 l 和 r 换了一下 if(!op){ if(list[num]->l){//判断NULL list[num]->l->r=list[i]; list[i]->l=list[num]->l; } list[num]->l=list[i]; list[i]->r=list[num]; } }

这个其实写过数组模拟的应该都会 只是稍微注意一下用指针找值的时候用的是“->” （用惯了结构体的我不知道多少次写成“.”QAQ）

然后是删除（其实和插入也差不多，每个操作反向来一遍）

void erase(int num){//这么写不怕重复删 if(list[num]->l){//不是链表左端，合并 list[num]->l->r=list[num]->r; } if(list[num]->r){//不是链表右端，合并 list[num]->r->l=list[num]->l; if(num==start)start=list[num]->r->num; } list[num]->l=list[num]->r=NULL;//删掉这个点的指针 }

至于输出时的思路就不在说啦 循环跑一边就过去了

附：AC源代码

指针+双端链表 660ms

#include<iostream> #include<cstdio> using namespace std; bool b[100100]; struct node{ int num; node *l,*r; node(int x){//写个构造函数下面插入的时候方便 num=x; l=r=NULL; } }*list[100100],*temp; /* 用一个 *list[] 来存列表 list[1]表示数字1的位置 list[2]表示数字2的位置 以此类推 这样在 n 左边或右边修改时； 直接访问 list[n] 就好了 少了扫一遍链表的时间 */ int n,m,start; void insert(int num,int i,int op){// if(op){ if(list[num]->r){//判断NULL list[num]->r->l=list[i]; list[i]->r=list[num]->r; } list[num]->r=list[i]; list[i]->l=list[num]; }if(!op){ if(list[num]->l){//判断NULL list[num]->l->r=list[i]; list[i]->l=list[num]->l; } list[num]->l=list[i]; list[i]->r=list[num]; if(num==start)start=i; } } void erase(int num){//这么写不怕重复删 if(list[num]->l){ list[num]->l->r=list[num]->r; } if(list[num]->r){ list[num]->r->l=list[num]->l; if(num==start)start=list[num]->r->num; } list[num]->l=list[num]->r=NULL; } int main(){ cin>>n; int num,op; start=1; list[1]=new node(1); for(int i=2;i<=n;i++){ list[i]=new node(i); cin>>num>>op; insert(num,i,op); } cin>>m; for(int i=1;i<=m;i++){ cin>>num; erase(num); } node *s=list[start]; while(s){ cout<< s->num <<" "; s=s->r; } }

数组模拟 560ms

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> using namespace std; struct Node{ int l,r; }list[500500]; int n,m,k,p; int u; void output(){ int k=list[0].r; while(k!=-1){ printf("%d ",k); k=list[k].r; } cout<<endl; } void leftadd(int k,int i){ list[i].l=k; list[i].r=list[k].r; list[list[k].r].l=i; list[k].r=i; } void rightadd(int k,int i){ list[i].r=k; list[i].l=list[k].l; list[list[k].l].r=i; list[k].l=i; } int main(){ cin>>n; list[0].r=1; list[1].l=0;list[1].r=-1; for(int i=2;i<=n;i++){ cin>>k>>p; if(p==0)rightadd(k,i); else leftadd(k,i); } cin>>m; for(int i=1;i<=m;i++){ cin>>u; if(list[u].r== -1 && list[u].l== -1)continue; list[list[u].l].r=list[u].r; list[list[u].r].l=list[u].l; list[u].r=list[u].l=-1; } output(); return 0; }

由于是新手，所以指针的代码写的很丑也很长……..