链表---移动盒子（双向链表）

作者: Celia_QAQ | 来源:发表于2019-05-03 18:54 被阅读0次

链表---移动盒子（双向链表）
双向链表&双向循环链表
线性表-双向链表与双向循环链表
线性表--链式存储结构--双向链表
数据结构与算法之双向链表(3.3)
双向链表和双向循环链表
day03-双向链表
双向链表&双向循环链表
9.双向链表DoubleLinkList
双向链表

题目：移动盒子UVa 12657

你有一行盒子，从左到右依次编号为1,2,3,…,n。可以执行以下4种指令：

1 x y：表示把盒子x移动到盒子y的左边（如果x已经在y的左边则忽略此指令）。
2 x y：表示把盒子x移动到盒子y的右边（如果x已经在y的右边则忽略此指令）。
3 x y：表示交换盒子x和y的位置。
4：表示反转整条链。

指令保证合法，即x不等于y。

【输入格式】
输入包含不超过10组数据，每组数据第一行为盒子数n和指令m，以下m行每行包含一条指令。
【输出格式】
每组数据输出一行，即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。
【输入样例】
6 4
1 1 4
2 3 5
3 1 6
4
6 3
1 1 4
2 3 5
3 1 6
100000 1
4
【输出样例】
case 1: 12
case 2: 9
case 3: 2500050000

[作者：大1234草]
原文：(https://blog.csdn.net/sinat_38816924/article/details/83514484)

如果是使用数组会超时。
--->Left[i]和Right[i]分别表示编号为i的盒子左边和右边的盒子编号
但是注意了如果执行了操作4后，如果操作1 2操作不变的话，那么操作1就是2，2 就是1（放在左边 + 反转 = 放在右边）

表格（以样例1为例）
输入6个盒子，4条指令

	0	1	2	3	4	5	6
Left [i]	1	0	1	2	3	4	5
Right [i]	6	2	3	4	5	6	0
盒变化
盒子0		1	2	3	4	5	6
1 1 4
盒子1		2	3	1	4	5	6
2 3 5
盒子2		2	1	4	5	3	6
3 1 6
盒子3		2	6	4	5	3	1
4
盒子4		1	3	5	4	6	2

书上代码：

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#define N 100001 
using namespace std;
int Left[N],Right[N];//左右盒子编号 
int n;

int swap(int a,int b){//交换两个值
    int t;
    t=a;
    a=b;
    b=t;
    return a,b;
}
//双向链表的一个比较实用的函数
void link(int l,int r){//连接两个节点 
    Right[l]=r;
    Left[r]=l;
} 

int main()
{
    int m,kase=0;
    //n,m分别为盒子个数和指令条数
    while(scanf("%d%d",&n,&m)==2){//读取两个整形值到n和m
        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;//inv表示操作4是否执行 
        
        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);
                }//X的左右连起来，按照链的顺序来写可能更加清晰
                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;//
            printf("case %d: %lld\n",++kase,ans);          //输出 
    }
    return 0; 
}

大佬的代码：
链表解法:::作者：不羡

#include<iostream>  
using namespace std;  
int bigflag = 0;  
struct node {  
    int x;  
    node * next;  
};  
int main() {  
    int n, m;  
    while (cin >> n >> m)  
    {  
        node *head = new node;;  
        head->x = 1;  
        node *temp = head;  
        for (int i = 2; i <= n; i++) {  
            node *p = new node;  
            p->x = i;  
            temp->next = p;  
            temp = p;  
        }  
        temp->next = NULL;  
        int a, b, c;  
        for (int flag = 0; flag < m; flag++) {  
            cin >> a;  
            if (a == 1) {  
                cin >> b >> c;  
                int i, j;  
                node *zz = head;  
                node *hh = head;  
                if (zz->x == b)i = 0;  
                else {  
                    for (i = 1; i < n; i++) {  
                        if (zz->next->x == b)break;  
                        zz == zz->next;  
                    }  
                }//真实位置i+1,要单独考虑在头的情况；  
                if (hh->x == c)j = 0;  
                else {  
                    for (j = 1; j < n; j++) {  
                        if (hh->next->x == c)break;  
                        hh = hh->next;  
                    }  
                }//真实情况j+1;  
                if (i + 1 + 1 != j + 1) {  
                    if (i == 0) {  
                        head = zz->next;  
                        zz->next = hh->next;  
                        hh->next = zz;  
                    }  
                    else {  
                        node *s = new node;  
                        s = zz->next;  
                        zz->next = zz->next->next;  
                        s->next = hh->next;  
                        hh->next = s;  
                    }  
                }  
                node * w = head;  
            }  
            else if (a == 2) {  
                cin >> b >> c;  
                int i, j;  
                node *zz = head;  
                node *hh = head;  
                if (zz->x == b)i = 0;  
                else {  
                    for (i = 1; i < n; i++) {  
                        if (zz->next->x == b)break;  
                        zz == zz->next;  
                    }  
                }//真实位置i+1,要单独考虑在头的情况；  
                for (j = 1; j < n; j++) {  
                    if (hh->x == c)break;  
                    hh = hh->next;  
                }  
                if (i + 1 != j + 1) {  
                    if (i == 0) {  
                        head = zz->next;  
                        zz->next = hh->next;  
                        hh->next = zz;  
                    }  
                    else {  
                        node *p = new node;  
                        p = zz->next;  
                        zz->next = zz->next->next;  
                        p->next = hh->next;  
                        hh->next = p;  
                    }  
                }  
            }  
            else if (a == 3) {  
                cin >> b >> c;  
                node *zz = head;  
                node *hh = head;  
                int i, j;  
                for (i = 1; i < n; i++) {  
                    if (zz->x == b)break;  
                    zz = zz->next;  
                }  
                for (j = 1; j < n; j++) {  
                    if (hh->x == c)break;  
                    hh = hh->next;  
                }  
                int temp;  
                temp = zz->x;  
                zz->x = hh->x;  
                hh->x = temp;  
                node * e = head;  
                int sum = 0;  
            }  
            else if (a == 4) {  
                node *mid = head;  
                node *tail = head->next;  
                for (int i = 1; i < n; i++) {  
                    node *pre = tail->next;  
                    tail->next = mid;  
                    mid = tail;  
                    tail = pre;  
                }  
                node *mm = mid;  
                head = mid;  
            }  
        }  
        node *mark = head;  
        int sum = 0;  
        for (int i = 1; i <= n; i = i + 2) {  
            sum = sum + mark->x;  
            mark = mark->next->next;  
        }  
        cout << "Case "<<bigflag+1<<": "<<sum << endl;  
        bigflag++;  
    }  
    system("pause");  
    return 0;