ハッシュテーブルを作成したいのですが、、、

Question

前提・実現したいこと

3 桁の数値 x に対して,ハッシュ関数の値 h(x) をハッシュテーブルのインデックスとして用い,これを先頭とする線形リストに連結するプログラムを実装しようとしています。

実装中に以下の実行結果が出力されました。

##実行結果

Linear-List:
No. Pointer Linked to

-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0
-1 0x7ffc77076d90 0

*** stack smashing detected ***: <unknown> terminated
中止 (コアダンプ)

該当のソースコード

C++言語
ソースコード

#include<iostream>
#include<string>
#include<ctime>

using namespace std;

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

void add_list( CELL * ,int);

void show_hash_table( CELL ** );

int Hash(int);

int main( void ){

const int Hash_NUM = 20;
const int num=10;
int data[num]={99,88,77,66,55,44,33,22,11,0};
int hash[num];

CELL *Hash_Table[num];

for(int i=0;i<Hash_NUM;i++){
Hash_Table[i]=new CELL;
Hash_Table[i]->data=-1;
Hash_Table[i]->next=NULL;
}

for(int i=0;i<num;i++){
hash[i]=Hash(data[i]);

if(hash[i]==i){
add_list(Hash_Table[i],data[i]);
}
}

show_hash_table(Hash_Table->next);

return 0;
}

int Hash(int data){
int hash;
hash=data%20;

return hash;
}

void add_list(CELL *hashtable,int data){

CELL *newcell = new CELL;
while( hashtable->next != NULL ){
hashtable = hashtable->next;
}
newcell->next = hashtable->next;
hashtable->next = newcell;
newcell->data = data;
}

void show_hash_table( CELL **p ){

cout << "-----------------------------" << endl;
cout << " Linear-List: " << endl;
cout << " No. Pointer Linked to" << endl;
cout << "-----------------------------" << endl;
for(int i=0;i<10;i++){

while( p[i] != NULL ){
cout << " " << p[i]->data << " " << p << " " << p[i]->next << endl;
p[i] = p[i]->next; /* 次のセルにポインタを移動 */
}
}

cout << "-----------------------------" << endl;
}

関数add_listは新しい入力に対してハッシュテーブルに線形リストを連結させる関数
関数Hashはハッシュ値を求める関数
関数show_hash_tableはハッシュテーブルを連結順に出力させる関数
です。

Comments

[itagagaki]

ん－、デバッグを手伝えということですか？
自分でどこまでデバッグしてみたのですか？

[episteme]

しつもんはなんですか?

Answer 1

#include <iostream>
#include <iomanip>
#include <algorithm>

struct CELL {
    int data;
    CELL* next;
    CELL(int d =0) : data(d), next(nullptr) {}
    CELL* tail() { // 末尾を探す
        CELL* p = this;
        CELL* prev = p;
        while ( p != nullptr ) {
            prev = p;
            p = p->next;
        }
        return prev;
    }
};

struct HashTable {
    size_t size;
    CELL** table;

    HashTable(size_t s) : size(s) { // まえじゅんび
        table = new CELL*[size]; // size個用意して
        std::fill(table, table + size, nullptr); // nullptrで埋めておく
    }

    ~HashTable() { // あとかたづけ:全要素を廃棄する
        for (int i = 0; i < size; ++i) {
            CELL* p = table[i];
            while ( p != nullptr ) {
                CELL* tmp = p->next;
                delete p;
                p = tmp;
            }
        }
        delete[] table;
    }

    void add_list(CELL*& list, int value) { // listの末尾にCELLを繋ぐ
        CELL* last = list->tail(); // 末尾を探し、
        if ( last == nullptr ) { // なかったら先頭の要素
            list = new CELL(value);
        } else { // あったらその直後に繋ぐ
            last->next = new CELL(value);
        }
    }

   void add(int value) { // 挿入:適切な位置にCELLを繋ぐ
        add_list(table[Hash(value)%size], value);
    }

    void show() const {
        std::cout << 
          "-----------------------------\n"
          " Linear-List: \n"
          " No. Pointer Linked to\n"
          "-----------------------------\n";
        for ( int i = 0; i < size; ++i ) {
            for ( CELL* p = table[i]; p != nullptr; p = p->next ) {
                std::cout << std::right << std::setw(3) << p->data 
                          << " " << static_cast<void*>(p) 
                          << " " << static_cast<void*>(p->next) 
                          << std::endl;
            }
        }
        std::cout << "-----------------------------\n";
    }

    int Hash(int data) const { return data; }
};

int main(void) {

    const int num = 10;
    int data[num] = { 99,88,77,66,55,44,33,22,11,0 };

    HashTable ht(3);

    for (int i = 0; i < num; i++) {
      ht.add(data[i]);
    }

    ht.show();
    return 0;
}

Answer 2

配列の要素数は正しいですか？
ハッシュ値は0～19の範囲になるのですよね？

const int Hash_NUM = 20;
const int num=10;

CELL *Hash_Table[num];

これだとハッシュ値がdataのインデックスと一致しないとテーブルに追加されませんが、意図した動作ですか？
例えばdata[0]%20==19になるのでi=0のときはdata[0]はどこにも追加されませんね。

for(int i=0;i<num;i++){
  hash[i]=Hash(data[i]);

  if(hash[i]==i){
    add_list(Hash_Table[i],data[i]);
  }

関数に渡す引数の型が合っていません。
宣言ではCELL**なのにCELL*を渡しています。

show_hash_table(Hash_Table->next);