洛谷 P1160 队列安排

首先，这个题目有一个天然的条件，就是插入的顺序是和编号顺序是一致的，那么要想做到一直对应，而且想要随时访问，那么用数组又是一个很好的选择，但是，这个顺序删来删去，逻辑结构肯定不会是像数组一样连续的，同时呢，题目很明确的表示了：此题目有插入操作，同时也有删除操作，且还会分前后之别，所以很容易就要想到：双向链表+数组来做这道题。

以队列中其中一个人为研究对象，整合一下我们需要的信息：

1.前面的同学;

2.后面的同学；

3.我出队列了吗？（这会决定删人的时候该不该忽略）

4.我的编号？

则链表结点结构体安排：

typedef struct listnode { bool stillthere;//判定是不是离开了 struct listnode* left; struct listnode* right; int num;//编号 }node;

接下来就是双向链表的删除，插入操作，很好想，思路不是很难，但是，边界情况一定一定要记得先讨论！

全部代码：

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdbool.h> typedef struct listnode { bool stillthere;//判定是不是离开了 struct listnode* left; struct listnode* right; int num;//编号 }node; node* buynode(int x) { node* newnode = (node*)malloc(sizeof(node)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->stillthere = true; newnode->num = x; newnode->left = NULL; newnode->right = NULL; return newnode; } int main() { int n; while (scanf("%d", &n) != EOF) { node* student[100001]; student[1] = buynode(1); for (int i = 2; i <= n; i++) { student[i] = buynode(i); int lor = 1; int beinsertednum = 0; scanf("%d %d", &beinsertednum, &lor); if (lor == 1) { if (student[beinsertednum]->right == NULL) { student[i]->right = NULL; student[i]->left = student[beinsertednum]; student[beinsertednum]->right = student[i]; } else { student[i]->right = student[beinsertednum]->right; student[beinsertednum]->right->left = student[i]; student[i]->left = student[beinsertednum]; student[beinsertednum]->right = student[i]; } } else { if (student[beinsertednum]->left == NULL) { student[i]->left = NULL; student[i]->right = student[beinsertednum]; student[beinsertednum]->left = student[i]; } else { student[i]->left = student[beinsertednum]->left; student[beinsertednum]->left->right = student[i]; student[i]->right = student[beinsertednum]; student[beinsertednum]->left = student[i]; } //目前没啥问题，但是怕就怕在特殊情况，如头插，上一个就比如说尾插，很难受，要处理一下. } } int m = 0; scanf("%d", &m); for (int i = 0; i < m; i++) { int x; scanf("%d", &x); //依然是remember处理特殊的边界情况 if (student[x]->stillthere == true) { node* rs = student[x]->right; node* ls = student[x]->left; if (rs == NULL && ls != NULL) { ls->right = NULL; student[x]->stillthere = false; } else if (ls == NULL && rs != NULL) { rs->left = NULL; student[x]->stillthere = false; } else if (ls == NULL && rs == NULL) { printf(" \n"); } else { ls->right = rs; rs->left = ls; student[x]->stillthere = false; //今后工作了之后要free掉这个student[i] } } } int cur=0; for (int i = 1; i <= n; i++) { if (student[i]->stillthere == true) { cur = i; break; } } node* pcur = student[cur]; while (pcur->left != NULL) { pcur = pcur->left; } while (pcur != NULL) { printf("%d ", pcur->num); pcur = pcur->right; } printf("\n"); } return 0; }