1

重複の可能性:
双方向リンク リスト作成中のコンテキスト スイッチ

The Design of the UNIX Operating System (Maurice Bach)を読んでいました。

彼は、二重にリンクされたリストの次の例を示します。

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二重連結リストです。リストの 2 番目の項目として挿入bp1しbpます (これがコードの動作です)。

そのためには、4 つのポインターを設定する必要があります。

bp1->forpリストの 2 番目の項目を指す必要がありますbp->forp (//1上記) 。

bp1->backpリストの最初の項目を指す必要があります。bp

bp->forp挿入されたアイテムを指す必要があります。bp1

2 番目のアイテムのバック ポインターはbp1->forp->backp、挿入されたアイテムを指している必要がありますbp1。(//2上)

編集：

構造体を A、B、C、D... と呼びましょうbp。挿入前のリスト ( by が指すのは A、C、D... で構成されていますbp1。 <->.

前：

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

後：

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

二重リンクリストにアイテムを挿入するときは、新しい要素を指す2つのポインターと、新しい要素を指す2つのポインターを変更する必要があります。

でマークされた線//1は、新しいポインタの次のポインタを挿入位置の次のポインタに設定します。マークされた線//2は、次の要素の前のポインタを新しい要素に設定し、それらの間の双方向リンクを完成させます。

新しい要素がリストの最後に追加されると、このコードはセグメンテーション違反になることに注意してください。その場合bp1->forpはNULLになるためbp1->forp->backp、nullポインタの逆参照を試みます。

編集

最初に：

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.

この前にもう 1 行必要です。

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

これで準備完了です。

**最初は空のリストであると仮定します。

于 2012-11-12T15:12:37.783 に答える