LinkedList「節點跳轉」

試圖找出爲什麼我的list()類指針正在被第三個節點覆蓋。插入函數（下面）中發生的情況是，第三次插入函數被調用時，我的headByName->nextByName節點指針被第三個節點覆蓋，當它指向第二個節點時。因此，你可以猜測第4節點被第5節覆蓋，第6節節點被第7節覆蓋，因此節點中的「跳」。LinkedList「節點跳轉」

//main.cpp 
//the attributes of the winery object are the paramaters, name, location, acres, rating: 
list *listPtr = new list(); 
wineries->insert(winery("Lopez Island Vinyard", "San Juan Islands", 7, 95)); 
wineries->insert(winery("Gallo", "Napa Valley", 200, 25)); 
wineries->insert(winery("Cooper Mountain", "Willamette Valley", 100, 47));

然後酒廠構造函數被調用，其中我分配專用指針低級用戶隔離：

酒廠對象的屬性是通過酒廠構造函數，然後通過這些調用在主的list::insert函數傳遞

//winery.cpp 
winery::winery(const char * const name, const char * const location, const int acres, const int rating) 
    : m_acres(acres), m_rating(rating) 
{ 
    if (name) 
    { 
     size_t len = strlen(name) +1; 
     m_name = new char[len]; 
     strcpy_s(m_name, len, name); 
    } 
    else 
     m_name = NULL; 

    if (location) 
    { 
     size_t len = strlen(location) +1; 
     m_location = new char[len]; 
     strcpy_s(m_location, len, location); 
    } 
    else 
     m_location = NULL; 
}

然後到手邊的問題：如果你可以想象這個功能已被調用兩次，current_node將有第三酒莊。 headByName將擁有第一個節點並且[+]，headByName->next將擁有第三個節點。我需要headByName->next獲得第二名。我只是想知道爲什麼它已被覆蓋..

// list.cpp 
void list::insert(const winery& winery) 
{ 
    node *current_node = new node(winery); // the third wineries info! 
    node *next_node  = NULL; 
    list *list_ptr  = NULL; 
    do 
    { 
     if (headByName == NULL || headByRating == NULL) // then we are here for the first item 
     { 
      headByName = current_node; // the list ptrs have a node address. 
      headByRating = current_node; 
     } 
     else 
     {   

      next_node     = current_node; 
// transfer by the next call in main. 
      headByName->nextByName  = next_node; 
      headByRating->nextByRating = next_node; 

     } 
    } while (headByName == NULL || headByRating == NULL); 

    next_node = NULL; 
    current_node = NULL; 
}

有人可以找到我的第二個節點？噢，那是提供給我的指點：

struct node 
{ 
    winery item; 
    node * nextByName; 
    node * nextByRating; 
}; 

class list 
{ 
    ... 
private: 
    node * headByName; 
    node * headByRating; 
};

，這可能是一些重要的節點構造函數的其身體：

//list.cpp 
list::node::node(const winery &winery) : 
nextByName(NULL), nextByRating(NULL), item(winery.getName(), 
winery.getLocation(), winery.getAcres(), winery.getRating()) 
{ 
    // where the item paramters are all pub-mem functions of the winery class. 

}

來源

2009-08-22 user40120

我認爲這個問題是在這裏：

headByName->nextByName  = next_node; 
headByRating->nextByRating = next_node;

您總是覆蓋第二個節點。據我所知，你應該找到最後一個遍歷整個列表並插入最後一個節點後。

來源

2009-08-22 06:12:16

好首要的問題是，當你插入一個節點，你總是設置

headByName->nextByName  = next_node; 
headByRating->nextByRating = next_node;

所以第二個節點被適當地填補。然後，第三個出現並覆寫第二個節點，第二個節點消失。

來源

2009-08-22 06:13:54 Goz

你的構造不相關但伸出的第一件事就是這個錯誤在分配邏輯：

headByName->nextByName  = next_node; 
headByRating->nextByRating = next_node;

這裏你總是設置頭節點到下一個節點（第2節點）的任何新節點是。這就是爲什麼列表中的第二個節點總是最新的節點。

如果您希望將項目添加到列表的末尾，您應該保留一個指向插入最後項目的尾指針，從頭項目開始。

隨着你的任務將改爲：

tail_pointer->nextByName = current_node; 
tail_pointer->nextByRating = current_node; 

tail_pointer = current_node;

其次，DO/while循環是不必要的。headByName和headByRating總是被設置爲指向新分配的節點current_node，這意味着

while (headByName == NULL || headByRating)

總是會跳出循環的（前提是你是不是跑出來的，當然內存）。

您總是通過在list :: insert中的第一個if塊中使用延遲初始化來分配兩個變量。

鏈接列表插入是恆定時間O（1），因爲您不必在循環中迭代任何東西 - 您始終知道在哪裏操作：tail_pointer。

而且，這樣的：

next_node = NULL; 
current_node = NULL;

是良好的作風在我看來，但不要忘記，你實際上並沒有重新分配這個數據來看，這是你的意圖:-)

情況

保留一個始終指向最新項目的尾部指針！

來源

2009-08-22 06:48:29 jscharf

LinkedList「節點跳轉」

回答

相關問題