www.pudn.com > HEC-linux.zip > hashtbl.cpp

#include 
#include 
#include 
 
#define TRUE   1 
#define FALSE  0 
 
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
+ declarations                                                      + 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
 
struct HashTbl 
{ 
	unsigned char empty;		/*indicates if entry is used or not*/ 
    char str[32];				/*string payload*/ 
    struct HashTbl *left; 
    struct HashTbl *right; 
}; 
 
#define PRIME 5 
 
class HashTable 
{ 
	struct HashTbl hashTbl[PRIME];	/*the hash table itself*/ 
 
	int hashpjw(char *s);  
 
	/*binary tree routines needed for collision resoltuion*/ 
 
	struct HashTbl* findNode(struct HashTbl* link, char *val); 
	void insertNode(struct HashTbl** link, char *val); 
	void printTree(struct HashTbl* link, int level); 
	void deleteAll(struct HashTbl **link); 
 
	public: 
	HashTable(); 
	~HashTable(); 
	struct HashTbl* queryHashTbl(char *str); 
	void addHashTblEntry(char *val); 
	void printHashTbl(); 
}; 
 
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
+ definitions                                                       + 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
 
HashTable::HashTable() 
{ 
	int i; 
	for(i=0;i> 24); 
			h = h ^ g; 
		} 
	} 
 
	return h % PRIME; 
 
}/*end hashpjw*/ 
 
/*-----------------------------------------------------------------*/ 
 
struct HashTbl* HashTable::findNode(struct HashTbl* link, char *val) 
{ 
    if(link==NULL) 
    {  
        return(NULL);  
    } 
    else if(strcmp(val,(*link).str)==0) 
    {  
        return(link);  
    } 
    else if(strcmp(val,(*link).str)>0 ) 
    {  
        return(findNode((*link).right,val));  
    } 
    else 
    { 
        return(findNode((*link).left,val)); 
    } 
 
}/*end findNode*/ 
 
/*-----------------------------------------------------------------*/ 
 
void HashTable::insertNode(struct HashTbl** link, char *val) 
{ 
    if( (*link) == NULL ) 
    { 
        (*link) = (struct HashTbl*)malloc(sizeof(struct HashTbl)); 
		(*(*link)).empty	= FALSE; 
		strcpy((*(*link)).str,val); 
        (*(*link)).left		= NULL; 
        (*(*link)).right	= NULL; 
    } 
    else if( strcmp(val,(*(*link)).str) == 0 ) 
    { 
		printf("HashTable.insertNode(): redundant identifier %s\n",val); 
        return; 
    } 
	else if( strcmp(val,(*(*link)).str) < 0 ) 
    { 
        insertNode( &((*(*link)).left) , val); 
    } 
    else 
    { 
        insertNode( &((*(*link)).right) ,val); 
    } 
    return; 
 
}/*end insertNode*/ 
 
/*-----------------------------------------------------------------*/ 
 
/* 
print tree by giving root to node and zero as args 
*/ 
 
void HashTable::printTree(struct HashTbl* link, int level) 
{ 
    int i; 
    if(link==NULL) 
    { 
        return; 
    } 
     
	printTree((*link).right,level+1); 
 
    for(i=0;i