数据结构基础 | 链表练习数据结构

【数据结构基础 | 链表练习】例题6-4 破损的键盘

//链表 #include #include const int maxn=100000+5; int last,cur,next[maxn]; //光标位于cur号字母的后面 char s[maxn]; int main() { while(scanf("%s",s+1)==1){ int n=strlen(s+1); //输入保存在s[1]、s[2]中 last=cur=0; //记得初始化 next[0]=0; for(int i=1; i<=n; i++) { char ch=s[i]; if(ch=='[') cur=0; else if (ch==']') cur=last; else{ next[i]=next[cur]; //下一个字符的位置，记录在数组里面 next[cur]=i; if(cur==last) last=i; //更新最后一个字符的编号 cur=i; //移动光标 } } for(int i=next[0]; i!=0; i=next[i]) printf("%c",s[i]); printf("\n"); } return 0; }

例题6-5 移动盒子

//双向链表 #include #include using namespace std; const int maxn=100000+5; int n,left[maxn],right[maxn]; //n个盒子inline void link(int L, int R) { right[L]=R; left[R]=L; }int main() { int m,kase=0; //m条指令 while(scanf("%d%d",&n,&m)==2){ for(int i=1; i<=n; i++) { left[i]=i-1; right[i]=(i+1)%(n+1); //一致性处理 } right[0]=1; left[0]=n; //初始化 int op,X,Y,inv=0; while(m--){ scanf("%d",&op); if(op==4) inv=!inv; else{ scanf("%d%d",&X,&Y); if(op==3 && right[Y]==X) swap(X,Y); if(op !=3 &&inv)op=3-op; if(op==1 &&X==left[Y]) continue; if(op==2 && X==right[Y]) continue; int LX=left[X],RX=right[X],LY=left[Y],RY=right[Y]; if(op==1) { link(LX,RX); link(LY,X); link(X,Y); } else if(op==2) { link(LX,RX); link(Y,X); link(X,RY); } else if(op==3){ if(right[X]==Y){link(LX,Y); link(Y,X); link(X,RY); } else{link(LX,Y); link(Y,RX); link(LY,X); link(X,RY); } } } } int b=0; long long ans=0; for(int i=1; i<=n; i++){ b=right[b]; if(i%2==1) ans+=b; } if(inv && n%2==0) ans=(long long)n*(n+1)/2-ans; //如果链条反转了奇数次且盒子数量是偶数，那么ans就是需要做这个操作 printf("Case %d:%lld\n",++kase,ans); } return 0; }

参考：