なぜこの関数で、先頭ノードの次に挿入できるのかわからない。

質問

柴田さんのC言語による「アルゴリズムとデータ構造」の中に出てくるハッシュ表に線形リストを用いてデータを挿入するチェイン法のプログラムでわからない処理があります。

ハッシュ表のバケット（リストの先頭ノードを持つポインタ）に対してデータを追加していきます。

絵を添付しようと思ったのですが、なぜか添付できなかったので、柴田さんの本をお持ちの方やご存知の方にご回答お願いします。

ハッシュ表の7のバケットには13で割った余りが7になる値を次々に挿入していきます。すでに、33と20が挿入されている状態です。そこに、13で割ったあまりがこれも7になるリストを挿入します。挿入するときは、イメージにあるように、バケットの次に挿入します。

この新しいノードを挿入する処理を行っているのは関数InsertNodeです。
/*引数にハッシュ表と追加するx（この場合46）をもらってくる。*/
int InsertNode(Hash *h,Data x)
{
/*ハッシュ値(データを13で割った余り)をkeyに設定する。hashはそういう仕様の関数です。*/
int key=hash(x.no);
/*Node型とはハッシュ表からつながっているリストのノード同士をつないだり、ノード自体のデータを格納する構造体型です。任意のノードであるpにハッシュ表の先頭要素であるバケットを挿入しています。*/
Node *p = h->table[key];
/*tempは新しく設定するノードの入れ物です。*/
Node *temp;

/*このループ処理により任意のノードpをデータがないところまで移動させます。この場合、20→33と伝って次のNULLまで行きます。これはすでにデータが登録済みかどうかをチェックするための処理です。たとえば20を関数InsertNodeの引数として持ってきたとすればメイン関数に1を返します。*/
while(p!=NULL)
{
if(p->data.no ==x.no)
{
return 1;
}
p=p->next;
}
/ここまで/

/*46は登録済みではないので、tempに新しい領域を設定します。もしも確保に失敗すればメイン関数に2を返します。*/
if((temp = (Node*)calloc(1,sizeof(Node)))==NULL)
{
return 2;
}

/*わからないのはこの処理です。*/
SetNode(temp,x,h->table[key]);
h->table[key] = temp;
/*ここまで*/

/*関数SetNodeの仕様としてはこの場合で言えば新しく挿入するノードtempに対して値46を設定する。それに加えて、次のノードに引数でもらってきたh->table[key]をさすようにするというものです。ところが私の解釈では、h->table[key]は先頭要素の値であり、挿入させてもらった絵のイメージとは違ってきてしまうと思うのです。SetNodeに渡す引数として、(temp,x,先頭の次の要素)でセットするのではないでしょうか。SetNodeの呼び出しの次の行で先頭要素であるバケットに新しく挿入する値46を挿入しておりますますわけがわからなくなってしまっています。*/
void SetNode(Node *n,Data x,Node *next)
{
n->data=x;
n->next=next;
}

return 0;

}

ところが、柴田氏の本に書かれているように記述すると私のイメージどおりに動いているようです。つまり私の解釈は間違っていることになります。上記の処理を解説していただきたいです。お手数ですが、よろしくお願いいたします。

回答No.1

D-Matsu · ベストアンサー

このリストは、挿入順とは逆順に並んでいます。
つまり、20, 33, 46と挿入したリストは先頭から46, 33, 20と並ぶということです。
「常に最新ノードが先頭になる」というところを踏まえて読めば理解できるかと。

お礼

理解できました。ありがとうございます。
SetNode(temp,x,h->table[key]);
この処理で、次が先頭要素を指すとされていて先頭の前が
あるのかと思ってしまっていましたが、冷静に考えれば
次の行でh->table[key] = temp;により挿入する46を先頭要素に
しているのですね。

D-Matsuさんがおっしゃっていたことはわかっていたのですが
「46の前に先頭要素がまた別にあるのではないか」のような間違った
解釈をしていたり、いろいろと変なことを思い込んでいたので
理解することができませんでした。

ですが、D-Matsuさんのアドバイスが呼び水となって理解まで持って
行くことができたので大変感謝を申し上げたいです。
ありがとうございました＾＾