C++中使用vector初始化链表

Question

这是我的 linked list 结构代码。我想用一个向量来初始化 TreeNode。但是在构造函数中，ptr->next = tem有错误Exception thrown: write access violation. ptr was 0xCDCDCDCD.有人知道原因以及如何更正吗？

#include<iostream>
#include<vector>

using namespace std;

struct ListNode {
    int val = 0;
    ListNode* next = NULL;

    ListNode(int val) : val(val){};

    ListNode(vector<int> vec) {
        if (vec.empty())
            return;
        val = vec[0];
        ListNode* ptr = this;
        for (int i = 1; i < vec.size();i++)
        {
            ptr->next = new ListNode(vec[i]);
            ptr = ptr->next;
        }
    }
};

Answer 1

在第一次迭代中，"next" 将被取消初始化，因此 ptr->next 不会指向任何有意义的内容，并且可能会导致段错误。

这不是方法中的唯一错误。

此外，在调试模式下，一些编译器会在未初始化的内存中放置特定的位模式以帮助调试。 0xCDCDCDCD 看起来很像那些位模式之一。

Answer 2

您的第一次迭代未正确初始化。

尝试

...
    ListNode(vector<int> vec) {
             ListNode* ptr = this;
...

它也没有正确对齐列表中的值。设置 this 的值，然后继续使用迭代器

        vit it = vec.begin();
        val = *it;

        for ( ++it; it != vec.end(); it++)
        {
            ListNode* tem = new ListNode(*it);
            ptr->next = tem;
            ptr = ptr->next;
        }

改为

Answer 3

对于初学者来说，这是一个糟糕的设计。用向量的元素初始化节点没有意义。

它是一个列表，可以由向量而不是节点的元素初始化。

构造函数的定义ListNode也没有意义

例如它的数据成员next没有初始化。

    ListNode* ptr = next;

所以这个声明

        ptr->next = tem;

调用未定义的行为。

一个节点被分配然后被删除

        ListNode* tem = new ListNode(*it);
        // ...
        delete tem;

那么列表将包含什么？:)

另外，像这样使用 typedef 也是个坏主意

typedef vector<int>::iterator vit;

它只会让代码的读者感到困惑。

class可以按照下面的方式定义，如演示程序所示。当然，您自己需要在 class 定义后附加其他构造函数、赋值运算符和析构函数。

#include <iostream>
#include <vector>

class List 
{
protected:
    struct Node
    {
        int val;
        Node *next;
    } *head = nullptr;      

public:

    explicit List() = default;

    List( const std::vector<int> &v )
    {
        Node **current = &head;

        for ( const auto &value : v )
        {
            *current = new Node { value, *current };
            current = &( *current )->next;
        }
    }

    friend std::ostream & operator <<( std::ostream &, const List & );
};

std::ostream & operator <<( std::ostream &os, const List &list )
{
    for ( List::Node *current = list.head; current != nullptr; current = current->next )
    {
        os << current->val << " -> ";
    }

    return os << "nullptr";
}

int main()
{
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    List list( v );

    std::cout << list << '\n';
}

程序输出为

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> nullptr

由于接受向量的列表的构造函数不是显式的，因此您可以按以下方式声明列表

List list( { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } );

C++中使用vector初始化链表

Use a vector to initialize the linked list in C++

c++

constructor

linked-list

vector

singly-linked-list