最初のノードを削除した後の逆方向DLLをトラバースする

Question

私は、挿入メソッドを使用して二重リンクリストをセットアップしました。

struct NODE 
{ 
    struct NODE *fwd; 
    struct NODE *bwd; 
    int value; 
}; 
typedef struct NODE Node; 

そして、この初期化：

void initializeList(Node *rt) 
{ 
    rt->fwd = NULL; 
    rt->bwd = NULL; 
    rt->value = 0; 
} 

私の主な機能は次のとおりです。

main() 
{ 
    Node root; 
    int j; 
    initializeList(&root); 
    for (j = 0; j < 15; j++) 
     insertFirst(&root, j); 
    printf("The list traversed forward \n"); 
    traverseForward(root); 
    printf("\n"); 
    printf("The list traversed backward \n"); 
    traverseBackward(root); 
    printf("\n"); 
    printf("After first deletion traverse forward\n"); 
    deleteFirst(&root); 
    traverseForward(root); 
    printf("\n"); 
    printf("After first deletion traverse backwards\n"); 
    printf("\n"); 
    traverseBackward(root); 
} 

私deletefirst機能は次のとおりです。

void deleteFirst(Node *rt) 
{ 
    Node *newnode = rt; 
    Node *tmp = NULL; 
    if (newnode != NULL) 
    { 
     if (newnode->fwd != NULL) 
     { 
      newnode = newnode->fwd; 
      tmp = newnode->bwd; 
      *rt = *newnode; 
     } 
     else 
      tmp = newnode; 
    } 
    free(tmp); 
    } 

挿入機能 この構造体を使用します：

int insertFirst(Node *rt, int val) 
{ 
    Node *node = (Node *)malloc(sizeof(Node)); 
    if (node == NULL) return 0; 
    node->value = val; 
    /* For a previously empty list */ 
    if (rt->fwd == NULL) 
    { 
     rt->fwd = node; 
     rt->bwd = node; 
     node->fwd = NULL; 
     node->bwd = NULL; 
    } 
    /* For a list with at least one node */ 
    else 
    { 
     /* previous first node now new node's successor */ 
     rt->fwd->bwd = node; 
     node->fwd = rt->fwd; 
     /* no predecessor to the new first node */ 
     node->bwd = NULL; 
     /* root points to this new first */ 
     rt->fwd = node; 
    } 
    return 1; 
} 

トラバース機能：

void traverseForward(Node root) 
{ 
    Node *q = root.fwd; 
    while (q) 
    { 
     printf("%d ", q->value); 
     q = q->fwd; 
    } 
} 
void traverseBackward(Node root) 
{ 
    Node *q = root.bwd; 
    while (q) 
    { 
     printf("%d ", q->value); 
     q = q->bwd; 
    } 
} 

システムはリストを出力リストアウトシステムのプリントが後進1削除後

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 

を横切っフォワード

14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

横断しました順方向tr最初の削除、後方トラバーサル

（何も印刷されていない）

した後、私はそれを動作させるために、ポインタを調整する方法を見つけ出すカント

13 12 11 10 9 8 7 6 5 4 3 2 1 0 

aversal。

Answer 1

私は、ルートノード内のリストの先頭と末尾に先頭と末尾のポインタを格納しておき、それをリストの実際のノードと置き換えて混在させるという奇妙な方法があると考えています。単純なNode *headとNode *tailポインタがあれば、この混乱を排除できますが、それは単なる提案に過ぎません。

あなたの削除機能では、あなたがrt->fwd->fwdとして転送トラバーサルの罰金であるルートノードへの効果的rt->fwdを、設定が望まれているものですが、あなたは常に最初の項目にNULLを指しているrt->fwd->bwdの値を考慮することを忘れ（論理的にはこのノードの前には何もないので）、その論理によって所望の機能であるリストの実際の末尾ではない。

これは明らかに、リストが空であると考えて逆方向に反復するときに問題を引き起こします。あなたはこのような何かにあなたの削除コードを変更する必要があります。

void deleteFirst(Node *rt) 
{ 
    if (rt == NULL) 
    { 
    return; /* Return if an invalid root was passed in */ 
    } 

    if (rt->fwd == NULL) { 
    return; /* Return if the list is already empty */ 
    } 

    Node *tmpfwd = rt->fwd; /* Store the current "head" */ 

    rt->fwd = rt->fwd->fwd; /* Set the root's head to the current head's next node */ 
    rt->fwd->bwd = NULL; /* Set the new head's previous node to NULL as it is the start of the list */ 

    free(tmpfwd); /* Delete the old "head" */ 
} 

他の問題の多くがここにありますエッジケースと物事に関するコメントが言及している（ただ、全体的なデザインは、これは非常に問題のあるものにする）が、私はこれがあると思いますあなたが現在持っている問題。