双链表

                     

贡献者: 有机物; addis

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

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

图
图 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 个插入的点的右边的结点的左指针

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


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利