数据结构基础 | 链表练习

待我称王封你为后i 2023-07-09 12:25 22阅读 0赞

**例题6-4 破损的键盘**

//链表
    #include<cstdio>
    #include<cstring>
    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<cstdio>
    #include<algorithm>
    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;
    }

参考：

*  刘汝佳的紫书
 *  [链表练习：破损的键盘 移动盒子][Link 1]
 *  [原来&与&&是有区别的][Link 2]

[Link 1]: https://blog.csdn.net/fireflylane/article/details/82934110?ops_request_misc=%7B%22request_id%22:%22158293579219725222400373%22,%22scm%22:%2220140713.130056874..%22%7D&request_id=158293579219725222400373&biz_id=0&utm_source=distribute.pc_search_result.none-task
[Link 2]: https://blog.csdn.net/GHL1996/article/details/97656513?ops_request_misc=%7B%22request_id%22:%22158295769019725211952545%22,%22scm%22:%2220140713.130056874..%22%7D&request_id=158295769019725211952545&biz_id=0&utm_source=distribute.pc_search_result.none-task