双链表

                     

贡献者: 有机物

   本文对应了上一篇文章,这里讲解双链表

   双链表在竞赛中用的不多,通常是因为需要优化某些问题而使用双链表。

图
图 1:双链表示意图

   双链表上的每个结点都有 $4$ 个值,$\mathtt{Lnext}$ 指针表示它左边的结点的下标,$\mathtt{Rnext}$ 指针表示它右边的结点的下标,其他的数组和变量和单链表的存储代表一个意思。

   用 C++ 的指针和结构体来实现双链表:

struct Double_List
{
    int value;
    Double_List *prev, *next;  // 左指针和右指针
};

   这里来详细的讲解一下如何使用数组来模拟双链表。

   数组模拟双链表需要这么几个数组和变量:

// 为了简化代码,我们用 e 表示 value, l 表示 Lnext, r 表示 Rnext
int e[N], l[N], r[N], idx;

   双链表的基本操作有:

  1. 在第 $k$ 个插入的数左侧插入一个数;
  2. 在第 $k$ 个插入的数右侧插入一个数;
  3. 将第 $k$ 个插入的数删除

   插入($\text{insert}$)操作:

图
图 2:在第 $k$ 个插入的点的右边插入一个数

   第 $1$ 步:先让要插入的点的右指针指向第 $k$ 个插入的点右边的点

   第 $2$ 步:让要插入的点的左指针指向第 $k$ 个插入的点

   第 $3$ 步:让第 $k$ 个插入的点的右边的点的左指针指向要插入的点

   第 $4$ 步:让第 $k$ 个插入的点的右指针指向要插入的点

// 在第 k 个插入的数的右边插入一个数
void insert(int k, int x)
{
    e[idx] = x;         // 赋值
    r[idx] = r[k];      // 第 1 步
    l[idx] = k;         // 第 2 步
    l[r[k]] = idx;      // 第 3 步
    // r[k] 是第 k 个插入的点的右边的点,
    // l[r[k] 就是第 k 个插入的点的右边的点的左指针
    r[k] = idx ++ ;     // 第 4 步
}


// 熟练掌握了之后就可以写成一行了。
e[idx] = x, r[idx] = r[k], l[idx] = k, l[r[k]] = idx, r[k] = idx ++ ;

   注意:

   第 $1$ 步和第 $2$ 步的操作的位置可互换,但是第 $3$ 步和第 $4$ 步的位置不可互换。 因为如果先操作第 $4$ 步的话,r[k] 就是修改之后的值了,如果接下来再调用 l[r[k]] 就不对了。

   如果想要在第 $k$ 个插入的数的左边插入一个数怎么办呢?

   最直接的办法就是照着刚才的逻辑对应着再写一遍,当然还有更见简便的方法。

   就是直接调用

insert(l[k + 1], x);
// 注意 k 要加 1,因为 idx 从 2 开始,所以下标也从 2 开始
意思就是在第 $k$ 个插入的数的左边插入一个数。

   删除($\text{remove}$)操作:

图
图 3:删除第 $k$ 个插入的点

   双链表的删除操作和单链表的删除类似

  1. 让第 $k$ 个插入的点的左边的结点的右指针指向第 $k$ 个插入的点的右边的结点
  2. 让第 $k$ 个插入的点的右边的结点的左指针指向第 $k$ 个插入的点的左边的结点

   对应到代码上:

// 删除第 k 个插入的点
void remove(int k)
{
    r[l[k]] = r[k], l[r[k]] = l[k];
}

// l[k] 为第 k 个插入的点的左边的结点,r[l[k]] 为第 k 个插入的点的左边的结点的右指针
// r[k] 为第 k 个插入的点的右边的结点,l[r[k]] 为第 k 个插入的点的右边的结点的左指针

   这样,双链表的基本操作就讲完了。

                     

© 小时科技 保留一切权利