插入排序链表段错误

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 有自己的头指针副本。当您在函数内部更改 head 时，它不会影响 main 中的值。解决方法是通过引用或通过地址传递head。

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;
    }
}

至于你的函数实现，函数处理头部的副本。副本的任何更改都不会影响参数本身。您应该通过引用传递 head 或 return 来自函数的 head。

插入排序链表段错误

Insert into sorted linked list segfaults

c++

linked-list