尝试使用链表实现哈希表来解决冲突问题我在初始化哈希表的代码中遇到了一些问题。 我遇到段错误。为了找出问题到底出在哪里,我使用了 valgrind。使用这个工具我收到警告:
"Address 0x8 is not stack'd, malloc'd or (recently) free'd"
几乎每次我尝试“编辑”哈希表时。 例如,大小、插入、删除等。 我一遍又一遍地查看我的代码,但我找不到问题所在。我以为我已经正确地分配和堆叠了所有内容。但有了这个消息,显然出了问题。 对此有什么想法吗?
我的代码:
//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 得到这个:
Invalid read of size 8 ==3773== at 0x40110E: lookup(360) ==3773== Address 0x8 is not stack'd, malloc'd or (recently) free'd
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;
}
事实上,如果我打电话查看 table 的大小,我也会得到分段,这让我更担心。 调用此:
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。不幸的是,如您所见,问题仍然存在。在第一次运行时(查找函数),它将该数字与列表中的数字进行比较,该数字为空。有 segmentation 。但我想知道为什么。不能直接返回 NULL 吗?
谢谢。
最佳答案
blankTable->table[i]=malloc(sizeof(List));
blankTable->table[i]=NULL;
您为列表项分配内存,然后将其设置为NULL
(0x0)。
关于c - 初始化哈希表的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4292953/