c（リンクされたリスト）のコードを理解する

Question

リンクされたリストを理解するのに大きな問題があります。誰かが私に次のことを説明できるなら、非常に感謝します。

Element_t *pushfront(Element_t *list) 
{ 
if(list==0) 
return allocate(); 

list->prev=allocate(); 

list->prev->next=list; 

list=list->prev; 

return list; 
} 

ここで意味するものはlist->prev->next=listですか？

この意味は：f->next->prev=f->prev？

私はこれがプログラムコードの一部であることを知っていますが、誰かが私にこれらの一般的な意味をできるだけ簡単に与えることを願っていますか？

Answer 1

リストには、前のノードおよびリスト内の次のノードへの参照を持つノードがあります。

この関数は、リストの最初のノードを取得します。したがって、この最初のノードには前のノードがありません。このステートメントで

list->prev=allocate(); 

それは関数名から以下のように、それはリストの先頭に新しいノードをプッシュするため、前のノードが作成されます。このステートメントで

list->prev->next=list; 

表現list->prevは新しい作成されたノードのアドレスを生成します。この作成されたノードは、リストの現在の最初のノードを指すものとする。従って、そのデータメンバnextは、ノードlistのアドレスを含むものとする。

そして、この文

list->prev->next=list; 

はこれを行います。

中間変数を導入するほうが簡単です。この質問

については

例えば

Element_t *new_node = allocate(); 

list->prev = new_node;  // list->prev=allocate(); 
new_node->next = list;  //list->prev->next=list; 
list = new_node;   //list=list->prev; 

return list; 

この意味するところ：F->ネクスト> PREV = F->前のページ？

ノードfがリストから削除されているように見えます。今すぐ次のノード（f->next）はfを指していませんが、前のノードfを指します。

ここでも、中間変数を導入するかどうかがより明確になります。

Element_t *previous_node_of_f = f->prev; 
Element_t *next_node_of_f = f->next; 

next_node_of_f->prev = previous_node_of_f; // f->next->prev=f->prev 

もこの

previous_node_of_f->next = next_node_of_f; 

のようなステートメントを追加する場合は、ノードfは、リストから完全に削除されます。だから今、あなたが追加したい

    (list) 
        A    B    C 
       +----------+ +----------+ +----------+ 
       | next=B |--->| next=C |--->| next=0 | 
       | prev=0 |<---| prev=A |<---| prev=B | 
       | data="A" | | data="B" | | data="C" | 
       +----------+ +----------+ +----------+ 

を：

typedef struct Element { 
    struct Element * next; 
    struct Element * prev; 
    void * data; 
} Element_t; 

これを仮定すると、あなたのリンクリストがbasicly次のように動作します。

 -------------------------------------------------------- 
     |            prev ^
     |              | 
---------------------- ---------------------- ---------------------- 
| previous_node_of_f | |   f   | | next_node_of_f |  
---------------------- ---------------------- ---------------------- 
     |             ^ 
     | next            | 
     ------------------------------------------------------- 

Answer 2

ここには、何が起こっているかを示すコメント付きのコードがあります。

Element_t *pushfront(Element_t *list) 
{ 
if(list==0) // If the list is emtpy 
return allocate(); /* then you simply create a new node, which 
represents your list and return it. The size of your list grew from 0 to 1.*/ 

list->prev=allocate(); /*If the list is not empty, you add a new node by creating it, 
and then the prev pointer of the first element in the list (list->prev) 
is set to this new element, as you want it to be first.*/ 

list->prev->next=list; /*Then you need to set the next pointer 
to the element you just added. The new element is at list->prev, 
so by list->prev->next, you just say, that the next element of the one 
you just created is the element that was first before you added the new one*/ 

list=list->prev; /* Here you just set the new element as the head of the list*/ 

return list; /*And here you return the new list*/ 
} 

それはあなたが必要とするすべてだとして、あなたのリストは常に、ちょうど最初の要素へのポインタとして渡されることに注意してください。 nextポインタですべての要素にアクセスできます。これはリストの各要素に設定されています。

Answer 3

まず、リンクされたリストは、相互にポインタでリンクされています。彼らは実際には順序通りではありません、彼らはメモリに分散されています。

あなたの質問にお答えください。-list->prev->next=list; ここでは、前のノードを現在のノードにリンクしています。このコードは、前のノードを現在のノードにリンクすることを意味します。それで、前のノードは構造体で定義された次のポインタとリンクします。 質問2を得るf->next->prev=f->prev; これはどこに定義されているのかわかりませんが、ここでは円で囲まれたリンクリストを作成しています。このコードによって最初のノードにリンクされた最後のノード。

Answer 4

Element_tは、おそらく次のようtypedefがありますAの前の新しいノードN

ので、1 A-> PREVは、これが新しいNを割り当て、既にA-> PREV = Nを割り当てA.

list->prev=allocate();に設定するようにNを設定する必要があり、2 N->次のニーズ。

次の行：list->prev->next=list：ちょうど割り当てられた新しいノードとしてlist->prevを読んでください。次に、N> next = A - 2番目のステップです。

あなたの新しい要素がリストにリンクされています。明らかに、allocate()は、nextおよびprevからNULLまで初期化する必要があります。

このことを意味します：f-> next-> prev = f-> prev？

どこに書かれているかによって異なります。ここではおそらく関数の一部であり、リストからノードを削除します。