0

スキップリストがどのように機能するかについての基本的な理解があると思いますが、C初心者であることに加えて、スキップリストに慣れていないため、いくつかの点、特にリストの初期化で混乱しています。これが私が従おうとしているコードです：

#define MAXSKIPLEVEL 5

typedef struct Node {
    int data;
    struct Node *next[1]; 
} Node;

typedef struct SkipList {
    Node *header;
    int level;
} SkipList;


// Initialize skip list
SkipList* initList() {

    SkipList *list = calloc(1, sizeof(SkipList));

    if ((list->header = calloc(1, sizeof(Node) + MAXSKIPLEVEL*sizeof(Node*))) == 0) {
        printf("Memory Error\n");
        exit(1);
    }

    for (int i = 0; i < MAXSKIPLEVEL; i++)
        list->header->next[i] = list->header;

    return list;
}

私はまだ C でポインターの配列を使って何もしていません。誰かが私を助けてくれるほど親切かどうか、いくつか質問があります。

最初にやっsizeof(int)たら 4sizeof(Node*)が出て 8 だったのでsizeof(Node)12 になると思っていたのに 16 になってしまったのはなぜですか? SkipListその内容のサイズと比較してのサイズと同じ混乱。どちらが原因なのかtypedefアンドを取り出してみましたが、サイズは16のままでした。[1]

次に、[1] が にあるのはなぜstruct Node *next[1]ですか? list->header->next[i]後で必要ですか？next[i]1を超えても大丈夫ですか？各ノードのポインターの数が可変であるという理由だけで、配列にして後で個別に増やしますか?

第三に、なぜlist->header->next[i] = list->header最初は代わりにNULL?

アドバイス/コメントは大歓迎です、ありがとう。

4

2 に答える 2

1

あなたの最初の質問について - なぜstructそのメンバーのサイズのサイズではないのですか? - これはstruct paddingによるもので、コンパイラは、通常は位置合わせの理由で、 a のメンバーの間または後に余分な空白を追加しstructて、サイズをいくつかの基本サイズ (多くの場合 8 または 16) の適切な倍数にすることができます。 . ほとんどのコンパイラには、これを行うために切り替えることができるカスタム スイッチがいくつかありますが、構造体のサイズをそのメンバーのサイズと正確に一致させる移植可能な方法はありません。

2 番目の質問については、なぜ[1]? - ここでの考え方は、ノード s の 1 つを実際に割り当てるときにstruct、領域を過剰に割り当てて、 の末尾のメモリをstructポインターに使用できるようにすることです。長さ 1 の配列を作成してからスペースを過剰に割り当てることにより、この過剰に割り当てられたスペースに、全体の一部であるかのようにアクセスすることが構文的に便利になりますstruct。C の新しいバージョンには、この手法に取って代わった柔軟な配列メンバーと呼ばれる概念があります。グーグルで調べて、それが役立つかどうかを確認することをお勧めします。

list->header->next[i]あなたの最後の質問について - が最初にlist->headerではなくを指すのはなぜNULLですか? -コードをもっと見ないと、なんとも言えません。リンクされたリスト構造の多くの実装では、このようなある種のトリックを使用しNULLて、実装で特別なケースを使用する必要がなくなります。この種のトリックがここでも使用される可能性は十分にあります。

于 2016-07-19T21:42:34.340 に答える