带有函数的c++自定义链表

Question

我实现了一个简单的链表。看哪!

struct List{
    List *next;
    bool last;
    string data;
};
List *head;

然而，当我试图用一个函数构建它，然后遍历它时，程序崩溃并报错0x00005(这是内存错误，对吧?)在构建函数中，一切似乎都很好，但它会抛出一个错误。下面是我列出的函数:

void mkList(List *ptr, int num){
    if(num != 0){
        ptr = new List;
        ptr->data = "asd";
        if(num == 1)ptr->last = true;
            else ptr->last = false;
        mkList(ptr->next,num-1);
    }
}

，我尝试遍历列表的方法在main:

int main(){
    mkList(head,5);
    List *ptr = head;
    while(!ptr->last){
        cout << ptr->data <<endl;
        ptr = ptr->next;
    }
    return 0;
}

在第二个元素之前，一切似乎都很好，我甚至可以计算第一个元素的数据!我做错了什么?

Answer 1

我认为你需要重新审视指针的概念。你需要明白指针是一个变量，它保存着另一个变量的内存地址。

如果你有这样的代码:

void foo(int a){
 a = 5;
}
// ...
int b = 0;
foo(b)

你不会希望b在最后一行之后变成5吧?指针也是一样。

void foo(List *a){
 a = new List;
}
// ...
List *b;
foo(b);

不以任何方式影响b。现在，如果你想从另一个函数设置b的值，你可以传递一个指针给b(记住，指针是一个变量，所以有一个指向指针的指针是完全没问题的):

void foo(List **a){
 a = new List;
}
// ...
List *b;
foo(&b);
// now b will point to the newly allocated memory

一旦你理解了这一点，你将很容易修复这段代码。

Answer 2

本行

mkList(ptr->next,num-1);

传递的是一个悬空指针。它指向任何地方。你需要传递指针的地址就像

mkList(&ptr->next,num-1);

并将函数重新定义为

void mkList(List **ptr, int num);

Answer 3

程序崩溃的原因是:

ptr = new List;
ptr->data = "asd";
...
mkList(ptr->next,num-1); // <-- ptr->next is uninitialized !

您使用未初始化的变量ptr->next，它产生未定义行为。可能的解决方案是为struct定义一个默认构造函数:

struct List{
    List() : next(NULL) { }
    List *next;
    string data;
};

，其中链表中的最后一个元素是next设置为NULL的元素。您不需要额外的数据成员来标记最后一个元素(您不需要bool last)。

这将解决未定义的行为，但实际上使您的程序按预期工作，您将需要更改void mkList(List *ptr, int num)的原型，使ptr作为指向List的指针的指针，以便对指针本身所做的更改对调用者可见:

void mkList(List** ptr, int num) {
    if (num <= 0)
        return;
    *ptr = new List();
    (*ptr)->data = "asd";
    mkList(&(*ptr)->next, num-1);
}

像这样从main: 调用

mkList(&head, 5);

虽然递归在这里不是最幸运的选择。保持简单是很好的做法，如果为了可读性，不要害怕写更多的代码行:

void mkList(List** ptr, int num)
{
    List* lastNode = NULL;
    for (int i = 0; i < num; ++i)
    {
        // create new node:
        List* node = new List();
        node->data = "asd";
        // store the pointer to the head:
        if (i == 0) *ptr = node;
        // move to the next element:
        if (lastNode) lastNode->next = node;
        lastNode = node;
    }
}