3

自分用にスキップリストを実装していますが、C++ でいくつかの問題が発生しています。私は2つの構造を持っています:

  1. スキップリストのノード - その int 値と、他のノードへのポインターの配列へのポインターを保持します。

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

  2. リスト (センチネル) の先頭と末尾へのポインタを保持する Skiplist。

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

また、スキップリスト構造へのポインターを返す関数があります (この関数を使用してスキップリストを初期化します)。

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 によると:

[...] 関数の最後を流れることは、値のない戻りと同等です。これにより、値を返す関数で未定義の動作が発生します。

2番目の問題:

同様の投稿で述べたように、構造体の割り当てに new 演算子を使用しているため、ダングリング ポインターは発生しません [...]

残念ながら、ダングリング ポインターが発生します。コメントでAngewが述べたように、ここで何をしているのか：

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

ローカル配列オブジェクトを作成listHead->nextし、配列 (およびそれに含まれるオブジェクト) が返されると破棄されることを考慮せずに、その最初の要素を指すようにしcreateSkipList()ます。自動保存期間を持つオブジェクトは、スコープ外になると破棄されます。

newさらに、一般的なアドバイスとして、所有権のモデル化には生のポインター、、およびを使用して手動でメモリ管理を行うのではなく、スマート ポインターを使用することを検討してdeleteください。

于 2013-05-11T09:47:01.180 に答える