1

可能重复：
双向链表创建期间的上下文切换

我正在阅读UNIX 操作系统的设计（莫里斯·巴赫）。

他给出了以下双向链表示例。

struct queue{
    //pointers (back and forward)
    //other data
}*bp, *bp1

bp1->forp = bp->forp; //1

bp1->backp = bp; //makes sense
bp->forp = bp1; //makes sense

bp1->forp->backp = bp1; //2

我无法理解标有1和的语句的目的2。1似乎错了，2看起来是多余的。

这是创建双向链表的有效方法吗？

4

3 回答 3

3

代码是正确的。

bp是一个双向链表。您想作为列表中的第二项插入bp1（bp这就是代码所做的）。

为此，您需要设置 4 个指针：

bp1->forp应该指向列表中的第二项，bp->forp （//1上）

bp1->backp应该指向列表中的第一项，bp

bp->forp应该指向插入的项目，bp1

第二个项目的后退指针，bp1->forp->backp应该指向插入的项目，bp1。（//2上）

编辑：

让我们调用结构 A、B、C、D... 列表（由 A、C、D... 指向的列表bp在插入之前组成。我们要插入 B（由bp1. 指向）<->表示前向和后向指针.

前：

bp --> A <-> C <-> D <-> E <-> ...
bp1--> B

后：

bp--> A <-> B <-> C <-> D <-> E <-> ...
于 2012-11-12T14:50:51.963 回答
1

向双向链表中插入项时，必须更改指向新元素的两个指针和指向新元素的两个指针。

用 标记的行将//1新的下一个指针设置为插入位置之后的下一个。标记的行将//2下一个元素的前一个指针设置为新元素，完成它们之间的双向链接。

请注意，当新元素添加到列表末尾时，此代码将出现段错误。在这种情况下bp1->forp将为 NULL，因此bp1->forp->backp将尝试取消引用空指针。

编辑

一开始：

bp  ->forp  = next
next->backp = bp  
bp1 ->forp  = null
bp1 ->backp = null 

The list looks like this. bp and next are linked, bp1 is outside of the list.

       /---\/            
    [bp]   [next]         [bp1]
      /\---/

线后//1

bp  ->forp  = next
next->backp = bp   
bp1 ->forp  = next
bp1 ->backp = null 

the forward pointer of bp1 points to the next element, but nothing points
to bp1 yet:

        /------------\/    
       /        /----\/
    [bp]    [bp1]    [next] 
      /\------------/

行前//2

bp  ->forp  = bp1
bp1 ->forp  = next
bp1 ->backp = bp 
next->backp = bp   

The link from next to bp1 hasn't been updated yet - it still points to bp:

      /---\/  /---\/            
  [bp]    [bp1]   [next]
    /\----/       /
    /\-----------/

线后//2

bp  ->forp  = bp1
bp1 ->forp  = next
bp1 ->backp = bp 
next->backp = bp   

The list is linked correctly:

      /---\/  /---\/            
   [bp]   [bp1]   [next]
    /\----/  /\---/
于 2012-11-12T14:44:48.510 回答
1

Is this a valid way to create a doubly linked-list?

**不，现在，这段代码只会给你一个分段错误。很明显，为什么在每个步骤之后添加以下行：

printf("bp = %#x\n\tbp->forp=%#x\n\tbp->backp=%#x\n", bp, bp->forp, bp->backp);
printf("bp1 = %#x\n\tbp1->forp=%#x\n\tbp1->backp=%#x\n", bp1, bp1->forp, bp1->backp);

首先，您需要分配和初始化您的结构：

bp = malloc(sizeof(struct queue));
bp->forp = NULL;
bp->backp = NULL;
bp1 = malloc(sizeof(struct queue));
bp1->forp = NULL;
bp1->backp = NULL;

然后我们打印您会看到的值，如下所示：

bp = 0x804b008
    bp->forp=0     //forward and back pointers are not pointing anywhere, good start
    bp->backp=0
bp1 = 0x804b018
    bp1->forp=0
    bp1->backp=0

在这些行之后：

    bp1->forp = bp->forp;  //bp1->forp is pointing no where (NULL), neither is bp->forp
                           // so this does nothing really... 
    bp1->backp = bp;
    bp->forp = bp1;

现在你会有类似的东西：

bp = 0x804b008
    bp->forp=0x804b018
    bp->backp=0
bp1 = 0x804b018
    bp1->forp=0
    bp1->backp=0x804b008

所以正如你所说，这是有道理的。现在我们尝试下一行？

bp1->forp->backp = bp1; //2
       ^
       |
       +------ That's NULL, and a seg fault.

在此之前您还需要一行：

bp1->forp-> = bp;
bp1->forp->backp = bp1;

现在你可以走了。

**假设最初是一个空列表。

于 2012-11-12T15:12:37.783 回答