数组简化双向链表实际应用【模版】（洛谷1160队列安排）

双向链表的好处在于可以随时在链表内对任意位置元素进行删改与添加为此想要用数组代替链表指针需要构建结构体用l和r来分别充当左右方向指针解题思路1题目所给条件需要对不同随机位置的地方增添学生并且删除学生与我们双链表的应用恰好吻合2我们的左右代替变量中a数组用来存储第i位的数据编号然后利用r或l来指向这个编号所对应的左边或者是右边的学生编号是多少而最终要求输出的也是学生编号我们就不必要再采用数据加id的结构体套路而是省略数据利用id来作为数组的存储项以及循环的递归变量套入for循环中依次输入输出3模拟双链表的插入操作的实现先将待插入值的左指针l变量连上插入位置的左元素右指针同理然后再将左方元素的右指针连接待插入元素右方同理4双链表的删除操作则是将第i位元素待删元素的左方元素的右指针连接第i1位元素将第i1位元素的左指针连接第i-1位元素然后再将第i位元素的左右指针指向空值既从链表中删去了第i位元素代码分析1由于题目默认第一位学生编号是1我们赋值也从i2开始而不用考虑将1号同学放在几号同学的身边,因为链表中只有1同学,无论如何都是在头部,若k为1既编号为i的同学要赋值到1号同学的身边数组a[k]也会进行对应的赋值操作,所以不用担心1号同学被错过.2,if条件下方就是模拟双链表的插入操作的实现若是将i插在k的左边,先将待插入值的右指针l变量连接k再将i的左指针连接k的现在所处位置的左方元素,于是i就跑到了k的左边和k-1(i出入来之前)的右边(但还没有完全插入进来,只是i此时可以访问他们两者,但是无法通过他们两个元素来访问自己),然后再将左右元素的对应右左指针分别连接在i身上,彻底完成插入操作.for(int i2;in;i){ int k,p; cinkp; if(p0){ a[i].rk; a[i].la[k].l; a[a[k].l].ri; a[k].li; } else { a[i].lk; a[i].ra[k].r; a[a[k].r].li; a[k].ri; } }双链表的删除操作则是将第i位元素待删元素的左方元素的右指针连接第i1位元素将第i1位元素的左指针连接第i-1位元素然后再将第i位元素的左右指针指向空值既从链表中删去了第i位元素,参考代码很好理解,不多做赘述.for(int i1;im;i){ int x; cinx; a[a[x].l].ra[x].r; a[a[x].r].la[x].l; a[x].la[x].r0; }1, 另外是关于输出的函数,在主函数中先判断是哪个元素在链表的最左端,既它左指针为空,右指针不为空,找到之后输出它本身的编号,然后将它丢进coute函数中;2,在coute函数中,如果它不是最后一个元素,既它的右边不为空,则输出它的右方元素,并将它的右方元素丢进coute函数,来实现将链表从左到右依次输出学生编号,注意函数输出的它右方的值,而非本身,所以我在主函数中才选择主动输出第一个元素;3,最后不要忘记,for循环的作用在于找到谁是第一个元素,而非输出每一个递归值,所以在for循环中一旦找到了就break掉,输出链表是coute函数的工作;void count(int k) { if(!a[k].r)return; couta[k].r ; count(a[k].r); } for(int i1;in;i) if(!a[i].la[i].r) { couti ; count(i); break; }最后献上Ac代码:#includebits/stdc.h using namespace std; int n,m; struct node{ int r; int l; }a[100007]; void count(int k){ if(!a[k].r)return; couta[k].r ; count(a[k].r); } int main(){ cinn; for(int i2;in;i){ int k,p; cinkp; if(p0){ a[i].rk; a[i].la[k].l; a[a[k].l].ri; a[k].li; } else { a[i].lk; a[i].ra[k].r; a[a[k].r].li; a[k].ri; } } cinm; for(int i1;im;i){ int x; cinx; a[a[x].l].ra[x].r; a[a[x].r].la[x].l; a[x].la[x].r0; } for(int i1;in;i) if(!a[i].la[i].r){ couti ; count(i); break; } return 0; }