为什么在实现链表时会出现分段错误？

Question

在这个函数中，我遇到了分段错误。我认为这与内存分配有关。我犯了什么错误？

现在，如果我初始化 Node* a =NULL，我最终得到的头指针为 NULL。

struct Node {
    int data;
    struct Node* next;
    Node(int x) {
        data = x;
        next = NULL;
    }
};

Node* addTwoLists(Node* first, Node* second) {
    // Code here
    Node *a;
    Node *head = a;
    int bor = 0;
    while(first->next && second->next) {
        int ans = first->data + second->data;
        a = new Node((ans%10)+bor);
        bor = ans/10;
        a=a->next;
        first = first->next;
        second = second->next;
    }
    return head;
}

Answer 1

a 未初始化。在分配值

a

你永远不会再分配给 head，所以它永远不会是任何其他东西。

Answer 2

由于各种原因，您可能会在此处遇到分段错误。

如果 first 或 second 是 NULL 那么你会得到分段错误。所以要确保如果这两个节点不是NULL.
您没有初始化所以先初始化一下。

如您所愿，head 变量应包含答案列表的起始节点，因此您需要在列表开始时分配节点。

在a = new Node((ans%10)+bor);

之后添加这一行

if(head == NULL) head = a;

Answer 3

错的不是分配，而是指针的使用。

它应该是这样的。此代码维护一个变量 last，它是添加到列表中的最后一个节点。你需要这个变量，这样你就可以在列表的末尾。明明是你自己想做的，却搞错了逻辑。

Node* addTwoLists(Node* first, Node* second) {
    Node *last = NULL;
    Node *head = NULL;
    int bor = 0;
    while(first->next && second->next) {
        int ans = first->data + second->data;
        Node* a = new Node((ans%10)+bor);
        if (head == NULL) {
            head = last = a; // first node, update head and end of list
        }
        else {
            last->next = a; // add a to the end of the list
            last = a;       // update the end of the list
        }
        bor = ans/10;
        first = first->next;
        second = second->next;
    }
    return head;
}

未经测试的代码。

Answer 4

对于初学者来说，变量 head 具有不确定的值，并且在函数中不会更改。

Node *a;
Node *head = a;

改变变量 a 并不意味着改变表达式 a->next.

的值

// ...
a = new Node((ans%10)+bor);
//...
a=a->next;

函数可以这样写（未测试）

Node * addTwoLists( const Node *first, const Node *second ) 
{
    const int Base = 10;

    Node *head = nullptr;

    int bor = 0;

    Node **current = &head;

    for ( ; first != nullptr && second != nullptr; first = first->next, second = second->next )
    { 
        int sum = first->data + second->data + bor;
        *current = new Node( sum % Base );
        bor = sum / Base;
        current = &( *current )->next;
    }

    if ( bor )
    {
        *current = new Node( bor );
    }

    return head;
}

这是一个演示程序

#include <iostream>

struct Node 
{
    explicit Node( int data, Node *next = nullptr ) : data( data ), next( next )
    {
    }

    int data;
    Node *next;
};

void push_front( Node **head, int x )
{
    *head = new Node( x, *head );
}

Node * addTwoLists( const Node *first, const Node *second ) 
{
    const int Base = 10;

    Node *head = nullptr;

    int bor = 0;

    Node **current = &head;

    for ( ; first != nullptr && second != nullptr; first = first->next, second = second->next )
    { 
        int sum = first->data + second->data + bor;
        *current = new Node( sum % Base );
        bor = sum / Base;
        current = &( *current )->next;
    }

    if ( bor )
    {
        *current = new Node( bor );
    }

    return head;
}

std::ostream & display_list( const Node *head, std::ostream &os = std::cout )
{
    for ( ; head != nullptr; head = head->next )
    {
        os << head->data << ' ';
    }

    return os;
}

int main()
{
    const int N = 10;
    Node *list1 = nullptr;
    Node *list2 = nullptr;

    for ( int i = 1; i < N; i++ ) push_front( &list1, i );
    for ( int i = N; --i != 0; ) push_front( &list2, i );

    display_list( list1 ) << '\n';
    display_list( list2 ) << '\n';

    Node *list3 = addTwoLists( list1, list2 );

    display_list( list3 ) << '\n';
}

它的输出是

9 8 7 6 5 4 3 2 1 
1 2 3 4 5 6 7 8 9 
0 1 1 1 1 1 1 1 1 1

为什么在实现链表时会出现分段错误？

Why am I getting segmentation fault while implementing linked list?

c++

struct

initialization

linked-list

singly-linked-list