3

我正在为自己实现一个跳过列表，但我在使用 C++ 时遇到了一些问题。我有两个结构：

  1. 跳过列表的一个节点 - 它保存其 int 值，以及指向指向其他节点的指针数组的指针。

    struct node{
    int val;
    node** next;
};

  2. Skiplist 保存指向列表头部和尾部的指针（哨兵）。

    struct skiplist{
    node *head, *tail;
};

另外，我有一个函数，它返回一个指向skiplist结构的指针（我使用这个函数来初始化skiplist）：

skiplist* createSkipList(){
    skiplist* l = new skiplist;
    node* listHead = new node;
    node* listTail = new node;

    node* headNext[MAX_LEVEL]; //array of pointers
    listHead->next = headNext;

    for(int i=0; i<MAX_LEVEL; i++){
        listHead->next[i] = listTail;
    }

    l->head=listHead;
    l->tail=listTail;
}

在我调用的 main() 函数中：

skiplist* skiplist=createSkipList();

该函数中的一切工作正常createSkipList()，但如果我想引用 main() 中的跳过列表，即通过访问skiplist->tail程序崩溃。我一直在寻找相关的帖子，但他们没有帮助我。

正如在类似帖子中提到的，我不应该遇到悬空指针，因为我使用new运算符来分配结构。我将不胜感激任何提示；）

4

1 回答 1

5

第一个问题：

您没有从 中返回任何内容createSkipList()，这意味着您的程序具有未定义的行为。添加return声明：

skiplist* createSkipList(){
    skiplist* l = new skiplist;
    // ...
    return l;
//  ^^^^^^^^^
}

根据 C++11 标准的第 6.6.3/2 段：

[...] 从函数末尾流出相当于没有值的返回；这会导致值返回函数中的未定义行为。

第二个问题：

正如在类似帖子中提到的，我不应该遇到悬空指针，因为我正在使用 new 运算符来分配结构 [...]

不幸的是，您确实会遇到悬空指针。正如 Angew在评论中提到的，你在这里做什么：

node* headNext[MAX_LEVEL]; //array of pointers
listHead->next = headNext;

是创建一个本地数组对象并让它listHead->next指向它的第一个元素，而不考虑数组（以及它包含的对象）一旦createSkipList()返回就会被销毁 - 具有自动存储持续时间的对象在超出范围时会被销毁。

此外，作为一般建议，请考虑使用智能指针来建模所有权，而不是通过原始指针new、 和delete.

于 2013-05-11T09:47:01.180 回答