0

私はスキップリストをグーグルで検索し、「アルゴリズムの紹介」 http://epaperpress.com/sortsearch/index.htmlという本を見つけ、次のhttp://epaperpress.com/sortsearch/skl.html からスキップリストのチュートリアルサンプルを入手しました

正常に動作している skl.c がありますが、コードを調べていると、次のように混乱することがわかりました。

typedef int keyType;            /* type of key */

/* user data stored in tree */
typedef struct {
    int stuff;                  /* optional related data */
} recType;


/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;

/* implementation independent declarations */
typedef struct {
    nodeType *hdr;              /* list Header */
    int listLevel;              /* current level of list */
} SkipList;

SkipList list;                  /* skip list information */

そして私を混乱させた機能は次のとおりです：

void initList() {
    int i;

   /**************************
    *  initialize skip list  *
    **************************/

    if ((list.hdr = malloc(
        sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *))) == 0) {
        printf ("insufficient memory (initList)\n");
        exit(1);
    }
    for (i = 0; i <= MAXLEVEL; i++)
        list.hdr->forward[i] = NIL;
    list.listLevel = 0;
}

このテストでは MAXLEVEL = 15 のように見えるので、 initList() では list.hdr->forward[0] = NIL; を実行します。list.hdr->forward[15] = NIL へ。そして nodeType structure を見てください。それには forward var struct nodeTag *forward[1]; があります。、struct nodeTag *forward[MAXLEVEL]; ではありません。

正しい構造は次のようにする必要があると思います：

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[MAXLEVEL]; /* skip list forward pointer */
} nodeType;

いいえ

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;

または私は何かを逃した？

4

1 に答える 1

1

原文は正しいと思います。

この malloc を注意深く見てください。

list.hdr = malloc(sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *)));

式の MAXLEVEL*sizeof(nodeType *) に注意してください。これは、単一の malloc で nodeType と MAXLEVEL * nodeType* を割り当てています。したがって、ノードと nodeType* の配列を割り当てています。これは、配列が構造体の最後のフィールドであるため機能します。したがって、ノードと配列は 1 つの連続したメモリです。

間違いなくもっと正しいのは typedef だったでしょう

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[0]; /* skip list forward pointer */
} nodeType;

ゼロの配列サイズに注意してください。

これは、上記の malloc 式で使用される一般的な C のイディオムです。これにより、コンパイル時ではなく実行時に配列サイズを決定できます。ただし、配列は構造体の最後のフィールドでなければならないことに注意してください。

Rici は、以下のコメントで 2 つの非常に優れた点を挙げています。

于 2013-09-12T02:27:27.257 に答える