ハッシュテーブル構築

Question

出力結果がこのように、初期に定義した-1の値が出る時と出ない時があります。なぜなのでしょうか？線形リストができていないのでしょうか？よろしくお願いします。
0 120 0x7ff974c059f0 0x7ff974c05a00
910 0x7ff974c05a00 0x0

1 -1 0x7ff974c05940 0x7ff974c05a10
411 0x7ff974c05a10 0x0

2 -1 0x7ff974c05950 0x0

3 -1 0x7ff974c05960 0x0

4 344 0x7ff974c059d0 0x7ff974c05a20
824 0x7ff974c05a20 0x0

5 -1 0x7ff974c05980 0x7ff974c05a40
435 0x7ff974c05a40 0x0

6 676 0x7ff974c059e0 0x7ff974c05a50
426 0x7ff974c05a50 0x0

7 -1 0x7ff974c059a0 0x0

8 -1 0x7ff974c059b0 0x7ff974c05a30
658 0x7ff974c05a30 0x0

9 -1 0x7ff974c059c0 0x7ff974c05a60
529 0x7ff974c05a60 0x0

#include <iostream>
#include <cstdlib>
using namespace std;
#define HASH_NUM 10 //ハッシュデーブルの要素数m
#define N 10        //入力データ数n

struct CELL{
  int data;
  CELL *next;
};

int Hash(int);
void add_hash_struct(CELL**,int);
void show_hash_struct(CELL**);


int main()
{
  CELL *HashTable[HASH_NUM];

  for(int i = 0; i < HASH_NUM; i++){
    HashTable[i] = new CELL;
    HashTable[i]->data = -1;
    HashTable[i]->next = NULL;
  }
  
  srand((unsigned int)time(NULL));
  int x;
  for(int i = 0; i < N; i++){
    x = rand() % 900 + 100;
    add_hash_struct(HashTable,x);
    x = 0;
  }

  show_hash_struct(HashTable);

}

int Hash(int x)
{
  return x % HASH_NUM;
}

void add_hash_struct(CELL **HT,int x)
{
  CELL *newcell = new CELL;

  int key;
  key = Hash(x);

  while(HT[key]->next != NULL){
    HT[key] = HT[key]->next;
  }

  newcell->next = NULL;
  HT[key]->next = newcell;
  newcell->data = x;
}

void show_hash_struct(CELL **HT)
{
  CELL *p = new CELL;
  for(int i = 0; i < HASH_NUM; i++){
    cout << i << " " ;
    while(HT[i] != NULL){
      cout << HT[i]->data << " " << HT[i] << " " << HT[i]->next << endl;
      HT[i] = HT[i]->next;
    }
    cout << endl;
  }
}

Answer 1

値-1のCELLは何のために入れてあるんですか?

Comments

[Giovannaaa]

リストの先頭と表したいので-1(適当な値)を入れています。

[episteme]

末尾ならともかく、なんでそんなの必要なんですか?

[Giovannaaa]

一応なにか値を入れとこうと思いました。消しときます。

[episteme]

while(HT[key]->next != NULL){
HT[key] = HT[key]->next;
}
で、ここでリストの先頭を書き換えちゃっていいんですかね?

[Giovannaaa]

リストの先頭を書き換えているとはどういうことなのでしょうか？

Answer 2

add_hash_struct()でHT[key]つまりHashTable[key]を書き換えてしまっているので、
HashTable[0]~HashTable[9]それぞれに対して2回以上追加した場合、最後の2つしか表示されません。

void add_hash_struct(CELL** HT, int x)
{
    CELL* newcell = new CELL;

    int key;
    key = Hash(x);

    while (HT[key]->next != NULL) {
        HT[key] = HT[key]->next; // ここ
    }

---

書き換えたいのはHashTable[0]~HashTable[9]の末尾のNULLになっているnextでしょう？

void add_hash_struct(CELL **HT,int x)
{
  CELL *newcell = new CELL;

  int key;
  key = Hash(x);

+  CELL* lastCell = HT[key];
-  while(HT[key]->next != NULL){
+  while(lastCell->next != NULL){
-    HT[key] = HT[key]->next;
+    lastCell = lastCell->next;
    }

  newcell->next = NULL;
-  HT[key]->next = newcell;
+  lastCell->next = newcell;
  newcell->data = x;
}

show_hash_structでもHashTable[0]~HashTable[9]を書き換えてしまっていますが…

Comments

[Giovannaaa]

解決するためのアドバイスを教えて欲しいです。

[Giovannaaa]

よろしくお願いします。

[Giovannaaa]

構築することができました。ありがとうございます。最後になのですが、前のwhile文ではなぜ書き換えてしまうのかあまり分からないです。また、新たにCELLを追加することでなぜ解決できるのでしょうか？良ければ教えてほしいです。すみません。

[SHOMI]

HTは配列HashTableの先頭ポインタなので、
HT[key] = HT[key]->next;
で書き換わるのはHashTable[key]の内容そのものです。
一方、
CELL* lastCell = HT[key];
lastCell = lastCell->next;
で書き換わるのは、 HT[key]の内容をコピーしたlastCellです。

main内で
for (int i = 0; i < HASH_NUM; i++) {
cout << "&HashTable[" << i << "]:" << &HashTable[i] << endl;
}

add_hash_struct内で
CELL* lastCell = HT[key];
cout << "&last:" << &last << ",&HT[" << key << "]:" << &HT[key] << endl;
とすれば
&HashTable[0]~[9]と&HT[0]~[9]が同じアドレスであること、
&lastCellと&HT[key]が異なるアドレスであることが確認できます。

[Giovannaaa]

丁寧なご回答ありがとうございます。理解することができました。