首页 > 编程语言 > 详细

数组模拟双向链表

时间:2020-02-27 11:33:18      阅读:153      评论:0      收藏:0      [点我收藏+]

用途:多次删除插入操作

准备:l[N],r[N];分别记录该数的左右

操作1.连接两个元素

eg.连接u,v

l[v] = u;
r[u] = v;

小技巧:虚拟位置0的使用

插入第一个元素1,则r[0] = 1;l[1] = 0;

 

操作2.插入元素

1.将v插在u的右侧

2.将v插在u的左侧

//将v插在u的右侧
r[v] = r[u];
l[v] = u;
l[r[u]] = v;
r[u] = v;

//将v插在u的左侧
r[v] = u;
l[v] = l[u];
r[l[u]] = v;
l[u] = v;

  

操作3.删除元素

l[u] u r[u]//删除元素u

l[r[u]] = l[u];
r[l[u]] = r[u];
l[u] = r[u] = 0;

  

操作4.遍历数组

for(int i = r[0]; i; i = r[i]){
    /*输出以及其他操作*/
}

  

例题:洛谷P1160

数组模拟双向链表

原文:https://www.cnblogs.com/zhangqiling/p/12370616.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!