-1

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

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

我试图遍历列表的方法主要是:

int main(){
    mkList(head,5);

    List *ptr = head;

    while(!ptr->last){
        cout << ptr->data <<endl;
        ptr = ptr->next;
    }
    return 0;
}

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

4

3 回答 3

0

在这一行

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

您正在传递一个悬空指针。它只是指向任何地方。您实际上需要传递指针的地址,如

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

并将您的功能重新定义为

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

但这很疯狂,可以更容易地完成......

于 2013-04-03T20:01:27.103 回答
0

您的程序崩溃的原因是在这段代码中:

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;
    }
}
于 2013-04-03T20:01:47.213 回答
0

我认为您需要重新访问指针的概念。您需要了解指针是保存另一个变量内存地址的变量。

如果你有这样的代码:

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

一旦你理解了这一点,你就很容易修复这个代码。

于 2013-04-03T20:09:18.853 回答