如何插入排序後的鏈接列表？

Question

可能重複：
LinkedList 「node jump」

我只需要通過名稱有順序的鏈接列表。我只能得到第一，第三，第五，...節點。我想不出這麼遠。我想成爲一名C++程序員，但如果我不明白這是他們的任何希望？作爲學生，STL容器std::lists在這一點上不適合我。你在列表中看到的是我想要理解的東西。

list::node::node(const winery &winery) : item(winery.getName(), winery.getLocation(), 
    winery.getAcres(), winery.getRating()), nextByName(NULL), nextByRating(NULL) 
{ 

} 

void list::insert(const winery& winery) 
{ 
    node *current_node = new node(winery); // but came here and did this so it has new info! 
    node *next_node  = NULL; 
    node *tail_node  = current_node; 

    if (headByName == NULL) // then we are here for the first item 
    {  
     headByName = current_node; // the list ptrs will have the first node's address. 
     headByRating = current_node; 
    } 
    while (headByName->nextByName != NULL) 
    { 
     headByName->nextByName = tail_node; 
     tail_node = next_node; 
     //next_node = current_node; 
    } 
    tail_node = new node(winery); 
    headByName->nextByName = tail_node; 
} 

而這是提供給我的指點：

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

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

Answer 1

當然有希望，我們都必須從某個地方開始！ :)

首先，我必須在實現指出一個危險的做法是用我自己的學生，通常導致大量的頭劃傷查找問題：

while (headByName->nextByName != NULL) 
{ 
    headByName->nextByName = tail_node; 
    tail_node = next_node; 
    //next_node = current_node; 
} 

不要在循環中使用像headByName這樣的列表成員作爲迭代變量，除非它是絕對必要的。您應該首先使用局部變量找到適當的節點，然後修改該節點。

這就是說，羅伯肯尼迪是正確的，你應該分別處理的名稱和等級（即一個「純粹」的實施將有一個泛型列表類，它是不知道什麼「名」和'的兩個實例評分'的意思），但是我假設上面的列表，節點和函數的接口在賦值中給了你（如果沒有，忽略我的答案的其餘部分:)）。

鑑於上述接口，我的方法是如下：

void list::insert(const winery& winery) 
{ 
    node* wineryNode = new node(winery); 
    assert (wineryNode); 

    // Find a node in the list with a name greater than wineryNode's 
    node* prevNode = NULL; 
    node* searchNode = headByName; // Note: not using the list member itself to iterate but a local variable 
    while (NULL != searchNode && 
     searchNode.winery.getName() < wineryNode.winery.getName()) 
    { 
     // Keep iterating through the list until there are no more items, or the right node is found 
     prevNode = searchNode; 
     searchNode = searchNode->nextByName; 
    } 

    /* At this point searchNode is either NULL 
     or it's name is greater than or equal to wineryNode's */ 

    // Check for the case where the list was empty, or the first item was what we wanted 
    if (NULL == prevNode) 
    { 
     headByName = wineryNode; 
    } 
    else 
    { 
     // prevNode is not NULL, and it's Name is less wineryNode's 
     prevNode-> nextByName = wineryNode; 
    } 
    wineryNode->nextByName = searchNode;  

    /* Now you just need to insert sorted by rating using the same approach as above, except initialize searchNode to headByRating, 
    and compare and iterate by ratings in the while loop. Don't forget to reset prevNode to NULL */ 
} 

Answer 2

要成爲一個雙向鏈表之前和之後的每個節點都必須有一個指針的節點。如果您願意，您還可以存儲頭部和尾部節點，但這樣做更符合個人的便利，而不是滿足雙向鏈接列表的要求。

Answer 3

我不確定我完全理解你的問題。只是從「如何插入已排序的鏈接列表？」主題開始我會做這樣的事情（僞）：

list::insert(Winery winery) { 
    Winery node = getHeadNode(); 

    // winery comes before the head node 
    if (winery.name < node.name) { 
     // the old head node now goes after this new node 
     // and this new node becomes the new head node 
     winery.next = node; 
     setHeadNode(winery); 
     return; 
    } 

    // let's iterate over the rest of the nodes in the list 
    Winery previous_node = node; 
    node = node.next; 
    while (node != NULL) { 
     // we found our insertion point 
     if (winery.name < node.name) { 
      // insert our new node 
      previous_node.next = winery; 
      winery.next = node; 
      return; 
     } 

     // insertion point not found, move to the next node and repeat 
     previous_node = node; 
     node = node.next; 
    } 

    // all elements visited, append our new element to the end of the list 
    previous_node.next = winery; 
    winery.next = NULL; 
} 

上述算法將插入新的節點列表中的適當位置，假設該列表是按名稱排序。

Answer 4

你稱之爲雙向鏈表，儘管你的節點每個鏈接都有兩個鏈接，但大多數人在聽到雙向鏈表時並不這麼認爲。由於您的兩個鏈接顯然與彼此無關 - 沒有人按字母順序對釀酒廠進行評級 - 如果您不認爲這是雙向鏈接列表，則會更容易一些。

當不需要更具體的順序時，插入鏈接列表的通常位置是列表的末尾。步驟如下：

1. 創建一個新節點。
2. 找到插入新節點的位置（即列表末尾的最後一個節點）
3. 更新最後一個節點的「下一個」指針指向新節點。

當你插入了可能是列表的中間，因爲是你的話，那麼還有另外一個步驟：

2.5。更新新節點的「下一個」指針。

步驟通常不存在的原因是，當插入列表末尾時，新節點的「下一個」指針在構建新節點對象時已經爲空。

你已經想出了第一步。事實上，你已經完成了也以及因爲你的代碼實際上創建了兩個新節點。您在current_node中存儲的其中一個以及您在tail_node中存儲的其他存儲。擺脫第二個。

步驟2是要確定哪個節點應該是緊挨着新節點的節點。按名稱排序時，該節點會出現在您找到的第一個節點之前，名稱爲，當前名稱爲。您將不得不沿着列表行走，可能會看到每個節點，直到找到之後的新節點的名稱。當你沿着列表移動時，你將不得不跟蹤哪個節點在之前，因爲一旦找到了你要找的節點，你將不得不回溯。

分別擔心名稱和評分。不要試圖一次解決這兩個部分。一旦你得到酒廠名稱正確插入，然後複製該代碼，並將「名稱」替換爲「評級」。但不要創建另一個節點對象。繼續使用之前創建的同一個。

正如你在這個任務上工作過的，你有沒有繪製箭頭指向其他節點的節點的任何圖片？嘗試一下。你確實已經看到它在你的教科書或老師的黑板上完成了。如果一個問題太大，你不能完全理解你的想法，那就用一些東西來幫助你跟蹤你腦海中的事情。專業人士也這樣做。由於每個節點都有多個指針，因此您應該爲指針指定標籤或使用不同的顏色來指定名稱和評級。