瞭解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->下一步 - >先前= 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將從列表中完全移出。

 -------------------------------------------------------- 
     |            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

首先，鏈接列表通過指針相互鏈接。事實上，它們並不是按照內存分配的。

讓我來看看你的問題-1 list->prev->next=list; 在這裏您將鏈接前一個節點與當前節點。此代碼意味着將前一個節點鏈接到當前節點。然後，前一個節點現在與在結構中定義的下一個指針鏈接。 獲取問題-2 f->next->prev=f->prev; 我不知道這是定義在哪裏，但在這裏你正在做一個圓圈鏈表。通過此代碼鏈接到第一個節點的最後一個節點。

Answer 4

Element_t是一個大概typedef類似以下內容：

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

假設這，您鏈表basicly是這樣工作的：

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

所以，現在你想添加一個A前面的新節點N

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

所以，1 A->分組需要被設置爲N和2 N->下需要設置爲A.

list->prev=allocate();此分配新的N和已經分配A->先前= N。

Next in line：list->prev->next=list：將list->prev作爲剛剛獲得分配的新節點。然後是N-> next = A - 第二步。

而您的新元素已鏈接到列表中。顯然，allocate()需要初始化next和prev至NULL。

這是什麼意思：f-> next-> prev = f-> prev？

取決於它的寫入位置。在這裏，它可能是一個函數的一部分，它從列表中刪除一個節點。