插入已排序的鏈接列表段落默認

Question

看起來像在「SortedInsert」中，頭部始終爲零，然後代碼段錯誤...無論如何...真的令人沮喪。任何想法爲什麼頭總是零，即使我把它設置爲某些東西，然後爲什麼代碼段錯誤一般？ 感謝

#include <iostream> 
#include <cassert> 
#include <string> 
#include <stdlib.h> 
#include <sstream> 
using namespace std; 

struct Node { 
    Node* next = 0; 
    int data; 
    ~Node(){ 
     if (next != 0){ 
      delete next; 
     } 
    } 
}; 

void SortedInsert(Node* head, int value){ 
    if(head == 0){ 
     Node* header = new Node; 
     header->data = value; 
     head = header; 
     return; 
    } 
    cout << "TEST" << endl; 
    Node* temp = head; 
    while(temp != 0){ 
     if(value > temp->data){ 
      Node* insert = temp->next; 
      Node* otherTemp = new Node; 
      otherTemp->data = value; 
      temp->next= otherTemp; 
      temp->next->next = insert; 
     } 
    temp=temp->next; 
    } 
    return; 
    } 

int main() { 
    srand(32); 
    Node* sortedList = 0; 
    for (int i = 0; i < 10; i++){ 
     SortedInsert(sortedList, rand() % 100); 
    } 

    Node* temp = sortedList; 
    for (int i=0; i < 9; i++){ 
     assert(temp->data <= temp->next->data); 
     temp = temp->next; 
    } 

    delete sortedList; 
} 

Answer 1

SortedInsert都有自己的頭指針的副本。當你在函數內改變頭部時，它不會影響main中的值。解決方案是通過引用或通過地址傳遞頭部。

void SortedInsert(Node** head, int value) { 
    //Use *head to refer to the head of the list 
} 
int main() { 
    ... 
    Node* sortedList = 0; 
    SortedInsert(&sortedList, ...); 
    ... 
} 

或者

void SortedInsert(Node*& head, int value) { 
    //Use head to refer to the head of the list 
} 
int main() { 
    ... 
    Node* sortedList = 0; 
    SortedInsert(sortedList, ...); 
    ... 
} 

Answer 2

請嘗試以下

void SortedInsert(Node* &head, int value) 
{ 
    if (head == nullptr || value < head->data) 
    { 
     head = new Node { head, value }; 
    } 
    else 
    { 
     Node *current = head; 

     while (current->next != nullptr && !(value < current->next->data)) 
     { 
      current = current->next; 
     } 

     Node *tmp = new Node { current->next, value }; 
     current->next = tmp; 
    } 
} 

至於你funcion實現，那麼該函數涉及的頭的副本。副本的任何更改都不會影響參數本身。你應該通過引用傳遞頭部或者從函數返回頭部。