在插入期間對鏈表進行排序

所以我試圖按降序將節點插入鏈表中，但是當我得到重複的數字並且找不到問題的好解決方案時，我很掙扎。我要麼遇到丟失的數字/程序崩潰或程序列表只有1個無限次數。在插入期間對鏈表進行排序

這裏是我的代碼，我認爲工程達到了「其他」的聲明，那就是我找不出和IM只是離開我的最後一個版本，該犯規顯然工作

void Link::insert(int number) { 
    Node *news = new Node; 

    news->number = number; 

    if(first == NULL) { 
     first = news; 
    } 
    if(news->number > first->number) { 
     Node *temp = first; 
     first = news; 
     news->next = temp; 
    } else { 
     Node *temp = first; 
     while (temp->next || news->number < temp->number) { 
      temp=temp->next; 
     } 
     temp->next = news; 
     news->next = temp->next; 
    } 

}

如果其他部分函數是需要的或我的main.cpp請讓我知道。

來源

2017-05-14 BigPaws

當你第一次插入，它進入你的第一個if條件，然後設置first=news，但在那之後其再次檢查news->number > first->number這將是錯誤的，所以進入的其他條件不必要的。因此，要麼在第一個if區塊中添加return;，要麼將其他人放在else區塊中。跟蹤先前元素的

else{ 
    Node *temp=first,*prev=null; 
    while (temp && (temp->next || news->number < temp->number)){ 
     prev=temp; 
     temp=temp->next; 
    } 
    if(prev==null){ 
     news->next=first;first=news; 
    } 
    else{ 
     prev->next=news;news->next=temp; 
    } 
}

來源

2017-05-14 13:08:12 rakesh

這解決了問題的一半明顯。它仍然沒有正確排序，例如當我輸入1 3 2 5時，它無限地打印2。 – BigPaws

編輯我的回答 – rakesh

也許

void Link::insert(int number){ 
Node *news = new Node; 

news->number = number; 

if(first == NULL){ 
    first = news; 
    return; 
} 

for(Node *i=first, *pred=NULL;!i;i=i->next){ 
if(i->number<number){ 
    if(i==first) { 
    news->next=first; 
    first=news; 
    } else { 
    pred->next=news; 
    news->next=i; 
    } 
    break; 
} 
pred=i; 
} 
}

來源

2017-05-14 13:16:14 Stilet

對不起，我是鏈接列表和C++的初學者，所以我幾乎不知道你的解決方案中發生了什麼，因爲這個if語句。 – BigPaws

你應該換你的最後2行，否則你有news->next = news，創建一個週期。

無論如何，我建議在2（私人的）部分分裂功能：一是其中發現的Node*後在哪裏插入（或nullptr爲第一位置），和用於插入的方法（它是調試所以容易）。

Node* Link::upper_bound(int value) const 
{ 
    if (first == nullptr || first->number <= value) { 
     return nullptr; 
    } 
    Node* node = first; 
    Node* next = first->next; 

    while (next && value < next->number) { 
     node = next; 
     next = node->next; 
    } 
    return node; // we have: node->number < value && (next == nullptr || value <= next->number) 
} 

void Link::insert_after(Node* node, int value) 
{ 
    Node* new_node = new Node(value); 

    if (node == nullptr) { 
     new_node->next = first; 
     first = new_node; 
    } else { 
     new_node->next = node->next; 
     node->next = new_node; 
    } 
}

最後：

void Link::insert(int number) { 
    insert_after(upper_bound(number), number); 
}

來源

2017-05-14 15:22:00 Jarod42

在插入期間對鏈表進行排序

回答

相關問題