關於C++中鏈接列表/指針的問題

C++中指針爲NULL的本質似乎感到任意。我確信有一種方法可以讓我失蹤，但以下幾點對我來說很有意義，但似乎並不奏效。我有一個節點添加到鏈接列表下面的方法：關於C++中鏈接列表/指針的問題

LLNode *ll; // set to NULL in constructor. 
void addToLL(Elem *e) 
{ 
    LLNode *current = ll; 
    while(true) 
    { 
     // edge case of an empty list. 
     if (ll == NULL) 
     { 

      ll = new LLNode(e); 
      break; 
     } 
     else if (current == NULL) 
     { 
      current = new LLNode(e); 
      break; 
     } 
     else { 
      current = current->next; 
     } 

    } 
}

當添加第二個節點添加到列表中，對於current == NULL的情況下不被抓住，因此它試圖調用current = current->next和崩潰做訪問無效的記憶。爲什麼會這樣呢？一個LLNode有一個指向Elem的指針，一個指向另一個LLNode的指針。

來源

2011-02-02 waterbo

您的插入邏輯不正確：您更改`current`指針，但是您絕不會將任何節點的`next`指針更改爲指向鏈接列表中的新元素。正如所寫，您的列表中永遠不會有多個節點。 – 2011-02-02 16:14:37

既然你說你在構造函數中將`ll`設置爲NULL，它是否是類的成員？這個addToLL函數是一個類的方法嗎？ – tenpn 2011-02-02 16:14:40

對不起，爲了簡潔起見，我把它砍下來了。 ll和方法都是同一個類的成員。 – waterbo 2011-02-02 16:24:00

您可能沒有在LLNode構造函數中將next指針設置爲NULL。

C++（指針類型，數值類型等）中的基本類型的對象具有不確定的初始值：它們在默認情況下不會被初始化。在使用它們之前，您需要明確地初始化這些對象。

來源

2011-02-02 16:11:34

對於這樣的事情，你需要一個指針的指針，以奪走了很多在實施不必要的異常：

LLNode *ll = NULL; 

void addToLL(Elem *e) 
{ 
    LLNode** current = &ll; 

    // While the current pointer to pointer is mapped to something, 
    // step through the linked list. 
    while (*current) 
    current = &(*current->next); 

    // At this point current is pointing to a NULL pointer and can 
    // be assigned to. 
    *current = new LLNode(e); 
}

原因指針NULL是因爲計算結果爲假，允許你做簡單的檢查，如while (*current)沒有大量的開銷。在CPU中，這通常最終被實現爲測試 - 零 - 假操作。

如果初始化，指針僅爲NULL。在C語言中，它們通常是未定義的，除非正確初始化並且引用未初始化的指針是災難性的。您需要確保您定義的指針始終在使用前初始化爲有效的指針。

來源

2011-02-02 16:15:59 tadman

1）您認爲ll在構造函數中設置爲NULL。但是什麼構造函數？這裏沒有類定義。 ll是一個全局變量嗎？你確定LLNode的構造函數將next指針設置爲NULL嗎？

2）條件

if (ll == NULL)

罐和應在循環之外進行檢查，如ll不被修改內部循環。

3）current是一個本地堆棧變量，因此一旦函數退出，賦值給它就不起作用。特別是，current = new LLNode(e)是內存泄漏。

4）要將節點添加到鏈接列表，您必須找到現有列表的最後一個節點，並修改其指針next。像這樣的東西會工作：

// ll is a field representing the first node in your existing linked list. 
if (ll == NULL) { 
    ll = new LLNode(e); 
} 
else { 
    current = ll; 
    while (current->next != NULL) { 
     current = current->next; 
    } 
    current->next = new LLNode(e); 
}

編輯：修改根據您的意見，即ll是類成員以上。

來源

2011-02-02 16:18:31

我在代碼中看到的第一件事是當前是本地的，獲得新的分配但實際上從未附加到列表中。

當然你的代碼應該是當然的

else if(current->next == NULL) 
{ 
    current->next = new LLNode(e); 
    break; 
}

LLNode必須初始化旁邊NULL在其構造。

當然，你的列表中有O（N）個插入時間，如果這是練習以外的任何事情，你幾乎肯定會使用標準庫容器。

您應該也可能將邊緣案例移出循環。

來源

2011-02-02 16:43:30 CashCow

關於C++中鏈接列表/指針的問題

回答

相關問題