HashTable的算法与实现
最近阅读《虚拟机的设计与实现-c/c++》发现第五章中哈希表的实现算法有点小bug，我对它算法做了一些修改并除掉了bug，如果按照书上的代码，大家一定会遇到 link2001 "0x..........."not read "0x............."是什么原因呢
其实此类问题是很严重的关于内存操作问题 就是变量没有初始化 对此例中的问题是在构造函数左右孩子没有初始化设置为null,
注意事项：1 大家应该尽量避免使用二重指针，二重指针很复杂，容易出错，应该适当的应用引用。
2 使用变量时一定要初始化，使用完后应该回收 尤其是以new申请的内存区域或指针。
必须回收 方法：例如: struct HashT * link = new struct HashT;
delete link; //必须
link= NULL://必须
3 要养成良好的编程风格。
此代码在vc6.0测试过， 如有问题发送我到J2MEZone@163.com ，谢谢。
代码解析：
//hashtable.cpp
#include"hashtable.h"
HashTable::HashTable()
{
int i;
for(i=0;i<PRIME;i++)
{
hashT[i].empty =true;
hashT[i].Field_Name[0]='\0';
hashT[i].left = NULL;//必须初始化
hashT[i].right = NULL;//必须初始化
}
}
HashTable::~HashTable()
{
int i;
for(i=0;i<PRIME;i++)
{
deleteAll((hashT[i].left));
deleteAll((hashT[i].right));
}
}
struct HashT* HashTable::queryHashT(char * str)
{
int hash;
hash =hashpjw(str);
if(hashT[hash].empty==true)
{
return(NULL);
}
else
{
return ( findNode((&hashT[hash]),str));
}
}
void HashTable::addHashT(char * val)
{
struct HashT * ptr;
int hash;
hash=hashpjw(val);
printf("HashTable.addHashT():hash(%s)=%d\n",val, hash);
if(hashT[hash].empty==true)
{
hashT[hash].empty=false;
strcpy(hashT[hash].Field_Name,val);
hashT[hash].left =NULL;
hashT[hash].right= NULL;
return;
}
ptr =&hashT[hash];
insertNode(ptr,val);
}
void HashTable::printHashT()
{
int i;
for(i=0;i<PRIME;i++)
{
if(hashT[i].empty==false)
{
printf("--Hash Slot (%d)--\n",i);
printTree(&(hashT[i]),0);
printf("\n");
}
}
printf("\n");
}
int HashTable::hashpjw(char *s)
{
unsigned char * p;
unsigned h=0,g;
for(p=((unsigned char * )s); * p!='\0';p=p+1)
{
h=(h<<4)+(*p);
if(g=(h&0xf0000000))
{
h=h^(g>>24);
h=h^g;
}
}
return h%PRIME;
}
struct HashT * HashTable::findNode(struct HashT * link, char * val)
{
if(link==NULL)
{
return(NULL);
}
else if(strcmp(val,link->Field_Name)==0)
{
return(link);
}
else if(strcmp(val,link->Field_Name)>0)
{
return(findNode(link->right,val));
}
else
{
return(findNode(link->left,val));
}
}
void HashTable::insertNode (struct HashT * &link, char *val)
{
if(link==NULL)
{
link= new struct HashT;//ÉêÇëÄÚ´æ
link->empty =false;
strcpy(link->Field_Name, val);
link->left = NULL;
link->right = NULL;
}
else if (strcmp(val,link->Field_Name)==0)
{
printf("HashTable.insertNode():redundant identifier %s\n",val);
}
else if (strcmp(val,link->Field_Name)<0)
{
insertNode(link->left,val);
}
else
{
insertNode(link->right,val);
}
}
void HashTable::printTree(struct HashT * link, int level)
{
int i;
if(link!=NULL)
{
printTree(link->right,level+1);
for(i=0;i<level;i++)
{
printf("-");
}
printf("identifer=%s\n",link->Field_Name);
printTree(link->left,level+1);
}
}
void HashTable::deleteAll(struct HashT *& link)
{
if(link!=NULL)
{
deleteAll(link->left);
deleteAll(link->right);
printf("HashTable.deleteAll():freeing %s \n",link->Field_Name);
delete link;
link =NULL;
}
}
//hashtable.h
#include<stdio.h>
#include<string.h>
#include<malloc.h>
struct HashT
{
bool empty;
char Field_Name[32];
struct HashT * left;
struct HashT * right;
};
#define PRIME 13
class HashTable
{
private:
struct HashT hashT[PRIME];
int hashpjw(char *s);
struct HashT * findNode(struct HashT * link, char * val);
void insertNode (struct HashT * &link, char *val);
void printTree(struct HashT * link, int level);
void deleteAll(struct HashT * &link);
public:
HashTable();
~HashTable();
struct HashT * queryHashT(char * str);
void addHashT(char * val);
void printHashT();
};
#include"hashtable.h"
int main()
{
char str[32];
HashTable ht;
char * FieldArray[2]={"CallingNO","CalledNO"};
ht.addHashT("CallingNO");
ht.addHashT("CalledNO");
ht.printHashT();
for (int i=0;i<2;i++)
{
strcpy(str,FieldArray[i]);
if((ht.queryHashT(str))!=NULL)
{
printf("found %s\n",str);
}
else
{
printf("did not find %s\n",str);
}
}
return 0 ;
}