HashTable 问题

这是我写的一个通用HashTable,但是在调试的时候报这样的错误，编译器用的是Vs2005

Windows 已在 HashTable.exe 中触发一个断点。
其原因可能是堆被损坏，这也说明 HashTable.exe 中或它所加载的任何 DLL 中有 bug。
输出窗口可能提供了更多诊断信息

在运行时报这样的错误

Debug Assertion Failed!
Expression:_CrtIsValidHeapPointer(pUserData)

我觉得应该是内存溢出或者数组越界之类的错误，但是我看了很多遍，不知道错在哪，哪位大侠能帮帮我，小弟我在此感激涕零 

源码贴在下面：

文件HashTable.h:

[CODE]

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include  <stdio.h>
#include  <stdlib.h>
#include  <math.h>
#include  <string.h>

#define INITSIZE 11/*哈希表初始容量*/

#define KEYNUM 1
#define KEYSTR 2

/*匹配函数*/
typedef int (*MatchFun) (void *key, void *value);
/*哈希函数*/
typedef int (*HashFun) (void *);
/*用于获取保存在HashTable中数据项的主键的函数*/
typedef void* (*GetKeyFun) (void *);

/*
*采用链地址法处理冲突，Hash*tem为链元素
*/
typedef struct _hash*tem
{
 void *value;
 struct _hash*tem *next;
}Hash*tem;

/*HashTable结构体*/
typedef struct
{
 MatchFun mf;/*匹配函数*/
 HashFun hf; /*哈希函数*/
 GetKeyFun gkf;/*用于获取保存在HashTable中数据项的主键的函数*/
 int  usedSize;/*哈希表已使用大小*/
 int  maxSize;/*哈希表能够容纳的最大元素个数*/
 float  loadFactor;/*装填因子*/
 Hash*tem  **value;/*哈希表的值,保存Hash*tem指针数组*/
}HashTable;

void init_hashtable(HashTable *ht, MatchFun mf, HashFun hf, GetKeyFun gkf, float loadFactor);
void free_hashtable(HashTable *ht);

int get_prime_number(int min);

void add_to_hashtable(HashTable *ht, void *key, void *value);
void remove_from_hashtable(HashTable *ht, void *key);
void *search_hashtable(HashTable *ht, void *key);
void modify_hashtable(HashTable *ht, void *key, void *value);
void recreate_hashtable(HashTable *ht);

#endif

[/CODE]

文件HashTable.c:

[CODE]

#include “hashtable.h”

/*
*初始化HashTable，设置匹配函数、哈希函数、装填因子、主键类型，并分配空间
*/
void init_hashtable(HashTable *ht, MatchFun mf, HashFun hf, GetKeyFun gkf, float loadFactor)
{
 ht->mf = mf;
 ht->hf = hf;
 ht->gkf = gkf;
 ht->loadFactor = loadFactor;
 ht->value = malloc(sizeof(Hash*tem *) * INITSIZE);
 memset(ht->value, 0, sizeof(Hash*tem *) * INITSIZE);
 ht->usedSize = 0;
 ht->maxSize = INITSIZE;
}

/*
*释放HashTable
*/
void free_hashtable(HashTable *ht)
{
 int i;
 Hash*tem *hi, *phi;
 for(i = 0; i  < ht->maxSize; i++)
  if(ht->value[i] == NULL)
   continue;
  else
  {
   hi = ht->value[i];
   while(hi)
   {
    phi = hi;
    hi = hi->next;
    free(phi->value);
    free(phi);
   }
  }
  free(ht->value);
}

/*
*获取大于min的最小质数，用于HashTable扩容时计算容量
*/
int get_prime_number(int min)
{
 int i, prime, flag;
 for( prime = min;; prime++)
 {
  flag = 0;
  for(i = 2; i  < sqrt(prime); i++)
   if(!(prime % i))
   {
    flag = 1;
    break;
   }
   if(!flag)
    return prime;
 }
}

/*
* 向HashTable添加元素
*/
void add_to_hashtable(HashTable *ht, void *key, void *value)
{
 unsigned long pos;
 Hash*tem *hi;
 if(search_hashtable(ht, key))/*已有元素*/
  return;
 pos = (*ht->hf)(key) % ht->maxSize;
 hi = malloc(sizeof(Hash*tem));
 if(hi == NULL)
 {
  puts(“Out Of Memory!”);
  exit(-1);
 }
 hi->value = value;
 if(ht->value[pos])
 {
  hi->next = ht->value[pos];
  ht->value[pos] = hi;
 }
 else
 {
  ht->value[pos] = hi;
  hi->next = NULL;
  ht->usedSize++;
 }
 if((float)(ht->usedSize) / ht->maxSize >= ht->loadFactor)
  recreate_hashtable(ht);
}
/*
*从HashTable中删除元素
*/
void remove_from_hashtable(HashTable *ht, void *key)
{
 unsigned long pos;
 Hash*tem *hi, *p;
 pos = (*ht->hf)(key) % ht->maxSize;
 if(ht->value[pos])
 {
  if((*ht->mf)(key, ht->value[pos]->value))
  {
   free(ht->value[pos]);
   ht->value[pos] = ht->value[pos]->next;
   if(!ht->value[pos])
    ht->usedSize–;
  }
  else
  {
   hi = ht->value[pos];
   while(hi->next)
   {
    if((*ht->mf)(key, hi->next->value))
    {
     p = hi->next;
     hi->next = hi->next->next;
     free(p);
    }
    hi = hi->next;
   }
  }
 }
}

/*
*根据Key查找
*/
void *search_hashtable(HashTable *ht, void *key)
{
 unsigned long pos, i;
 Hash*tem *hi;
 i = (*ht->hf)(key);
 pos = i % ht->maxSize;
 if(ht->value[pos])
 {
  hi = ht->value[pos];
  while(hi)
  {
   if((*ht->mf)(key, hi->value))
    return hi->value;
   hi = hi->next;
  }
  return NULL;
 }
 else
  return NULL;
}

/*
*当实际的装填因子超过预设值时，重建HashTable,具体方法是先将所有元素取出，
*存入一个单向链表，然后将重新分配空间的HashTable清空，再逐项将元素加入HashTable
*/
void recreate_hashtable(HashTable *ht)
{
 int i, newSize, newPos;
 Hash*tem *head = NULL, *p;

 for(i = 0; i  < ht->maxSize; i++)
 {
  if(ht->value[i])
  {
   if(!head)
    head = p = ht->value[i];
   else
    p->next = ht->value[i];
   while(p->next)
    p = p->next;
  }
 }

 newSize = get_prime_number(ht->maxSize * 2);/*新容量设置为大于原容量2倍的最小质数*/
 ht->value = realloc(ht->value, newSize * sizeof(Hash*tem *));
 memset(ht->value, 0, newSize * sizeof(Hash*tem *));
 ht->usedSize = 0;
 ht->maxSize = newSize;

 while(head)
 {
  add_to_hashtable(ht, (*ht->gkf)(head->value), head->value);
  p = head;
  head = head->next;
  free(p);
 }
}

[/CODE]
文件main.c:

[CODE]

#include “hashtable.h”
//#include “hashfunction.h”

/*
*OpenSSL中出现的字符串Hash函数
*/
unsigned long lh_strhash(const char *c)
{
 unsigned long ret=0;
 long n;
 unsigned long v;
 int r;

 if ((c == NULL)  ¦ ¦ (*c == ‘\0′))
  return(ret);

 n=0×100;
 while(*c)
 {
  v = n  ¦ (*c);
  n += 0×100;
  r= (int)((v >> 2) ^ v) & 0x0f;
  ret=(ret  < < r)  ¦ (ret >> (32 – r));
  ret &= 0xFFFFFFFFL;
  ret ^= v * v;
  c++;
 }
 return((ret>>16)^ret);
}

/*
*MySql中出现的字符串Hash函数
*/
/* Calc hashvalue for a key */
unsigned long calc_hashnr(const char *key)
{
 register unsigned int nr = 1, nr2 = 4;
 int length;
 length = strlen(key);
 while(length–)
 {
  nr^= (((nr & 63) + nr2) * ((unsigned int) (unsigned char) *key++)) + (nr  < < 8);
  nr2+=3;
 }
 return ((unsigned int) nr);
}

/*
*一个经验字符串Hash函数
*/
unsigned long hash(char *str)
{
 register unsigned int h;
 register unsigned char *p;

 for(h=0, p = (unsigned char *)str; *p ; p++)
  h = 31 * h + *p;

 return h;
}

int test_match(char *key, char *value)
{
 return !strcmp(key, value);
}

char* test_getkeyfun(char *value)
{
 return value;
}

/*
*构造一个字符串HashTable，从文件中读取单词
*/
void build_hashtable(HashTable *ht, char *file)
{
 FILE *fp;
 char *str;
 if((fp = fopen(file,”r”)) == NULL)
  return;
 while(!feof(fp) && !ferror(fp))
 {
  str = malloc(sizeof(char) * 50);
  fscanf(fp, “%s”, str);
  add_to_hashtable(ht, str, str);
 }
}

void print_result(HashTable *ht)
{
 int i, j, res[7], num = 0;
 Hash*tem *hi;
 memset(res, 0, sizeof(int) * 7);
 for(i = 0; i  < ht->maxSize; i++)
 {
  if(ht->value[i])
  {
   j = 0;
   hi = ht->value[i];
   while(hi)
   {
    hi = hi->next;
    j++;
    num++;
   }
   if(j > 5)
    res[6]++;
   else
    res[j]++;
  }
 }
 printf(“哈希表总大小:%d 已使用大小:%d 元素个数:%d\n”, ht->maxSize, ht->usedSize, num);
 printf(“实际装填因子:%4f 预设装填因子:%4f\n”, (float)ht->usedSize / ht->maxSize, ht->loadFactor);
 for(i = 0; i  < 7; i++)
  printf(“冲突%d次元素个数:%d\n”, i – 1, res[i]);
}
int main()
{
 HashTable hashtable;
 char *str;
 init_hashtable(&hashtable, test_match, lh_strhash, test_getkeyfun, 0.7);
 build_hashtable(&hashtable, “D:\\HashTableTest.txt”);
 str = search_hashtable(&hashtable, “abature”);
 if(str)
  puts(str);
 print_result(&hashtable);
 free_hashtable(&hashtable);
 return 0;
}
[/CODE]