衝突の問題を解決するためにリンクされたリストを使用してハッシュ テーブルを実装しようとしています。ハッシュ テーブルを初期化するためのコードでいくつかの問題に直面しています。セグメンテーション違反が発生します。問題が正確にどこにあるかを確認しようとして、valgrind を使用しました。このツールを使用すると、次の警告が表示されます。
「アドレス 0x8 は、スタック、malloc、または (最近) 解放されていません」
ハッシュテーブルを「編集」しようとするほとんどすべての場合。たとえば、サイズ、sth の挿入、削除などです。コードを何度も調べましたが、何が問題なのかわかりません。すべてを正しくmallocしてスタックしたと思いました。しかし、このメッセージでは、明らかに sth が間違っています。これに関するアイデアはありますか？
私のコード:
//hash table structure
typedef struct HashTable
{
int size; //size of table with connections
struct List **table; //table elements
}HashTable;
typedef struct List
{
char* number;
struct List *next;
}List;
struct HashTable *initHashTable(int size)
{
struct HashTable *blankTable=(struct HashTable *)malloc(sizeof(struct HashTable));
if (size<1)
{
return NULL;
}
if ((blankTable=malloc(sizeof(HashTable)))==NULL)
{
return NULL;
}
if ( (blankTable->table=malloc(size*sizeof(List))) == NULL)
{
return NULL;
}
int i;
for (i=0; i<size; i++) //initializes hash table
{
blankTable->table[i]=malloc(sizeof(List));
blankTable->table[i]=NULL; //Valgrind :: Invalid write of size 8
}
blankTable->size = size;
//printf("blankTable size:%d\n",blankTable->size);
return blankTable;
}
その他の注意: 次のコードを使用して、数値がハッシュ テーブルに既に存在するかどうかを検索します。私はこれをvalgrindから取得します:
サイズ 8 の無効な読み取り ==3773== 0x40110E: lookup(360) ==3773== アドレス 0x8 は、スタック、malloc、または (最近) 解放されていません
struct List *lookup(HashTable *hashtable,char *number)
{
struct List *list= (struct List *) malloc (sizeof(struct List )); ;
unsigned int hashval= hash(number);
if ( (hashtable->table[hashval])!=NULL)
{
for( list=hashtable->table[hashval]; list!=NULL; list=list->next)
{ if(strcmp(number,list->number)==0) //SEGMENTATION!
{
return list;
}
}
}
return NULL;
}
テーブルのサイズを確認するために呼び出すと、セグメンテーションも取得されるという事実は、さらに心配です。これを呼び出す：
unsigned int size = Array[pos].TableHead->size;
Array[pos].TableHead は、hashTable の構造体へのポインターです。
編集：
valgring を実行すると、次のレポートが表示されます。
Invalid write of size 8
==8724== at 0x4016D2: initHashTable (hash.c:524)
==8724== by 0x4019CE: main (hash.c:792)
==8724== Address 0x5199180 is 8 bytes after a block of size 8 alloc'd
==8724== at 0x4C25153: malloc (vg_replace_malloc.c:195)
==8724== by 0x4016B6: initHashTable (hash.c:522)
==8724== by 0x4019CE: main (hash.c:792)
==8724== Use of uninitialised value of size 8
==8724== at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724== by 0x4017A0: lookup (hash.c:551)
==8724== by 0x401820: add(hash.c:566)
==8724== by 0x401AAB: main (hash.c:817)
==8724==
==8724== Invalid read of size 1
==8724== at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724== by 0x4017A0: lookup (hash.c:551)
==8724== by 0x401820: add (hash.c:566)
==8724== by 0x401AAB: main (hash.c:817)
==8724== Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8724==
==8724==
==8724== Process terminating with default action of signal 11 (SIGSEGV)
==8724== Access not within mapped region at address 0x0
==8724== at 0x4C264C4: strcmp (mc_replace_strmem.c:412)
==8724== by 0x4017A0: lookup (hash.c:551)
==8724== by 0x401820: add (hash.c:566)
==8724== by 0x401AAB: main (hash.c:817)
==8724== If you believe this happened as a result of a stack
==8724== overflow in your program's main thread (unlikely but
==8724== possible), you can try to increase the size of the
==8724== main thread stack using the --main-stacksize= flag.
==8724== The main thread stack size used in this run was 8388608.
これを読んで、私の番号にはヌルターミネータがないと最初に思いました。だから、私はそれを再初期化し、最後のインデックスにnullを追加しました。残念ながら、ご覧のとおり問題が残っています。最初の実行 (ルックアップ関数) で、数値をリストの数値と比較します。これは null です。セグメンテーションがあります。しかし、私はなぜさまよいます。NULL を返すことはできませんか?
ありがとうございました。