HashTable algorithm and implementation

Recently read "The Design and Implementation - C / C " found in Chapter 5 has a bit small bug, I have made some modifications to it and remove the bug, if you follow the code, Everyone will meet Lin2001 "0x ..........." NOT READ "0x ..........." What is the reason?

In fact, such problems are very serious about memory operations, the variable has no initialization. The problem is that the child is not initialized to null in the constructor.

Note: 1 Everyone should try to avoid using a dual pointer, and the dual pointer is complicated, and it is easy to make an error.

2 When using variables, it must be initialized and should be recovered after use, in particular the memory area or pointer applied by the New.

Methods must be recovered: for example: struct hasht * link = new struct hasht;

Delete link; // must

Link = null: // must

3 To develop a good programming style.

This code is tested in VC6.0. If you have any questions, I will send me to J2mezone@163.com, thank you.

Code analysis:

//hashtable.cpp

#include "hashtable.h" Hashtable :: HashTable () {INT i; for (i = 0; i

Hasht [i] .right = null; // must initialize}

} Hashtable :: ~ HashTable () {INT I; for (i = 0; i

Struct Hasht * Hashtable :: queryhasht (char * str) {int hash; hash = hashpjw (str); if (Hasht [hash] .empty == true) {return (null);} else {return (Findnode (" [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 [Hasht [Hasht [hash ] .left = null; hasht [hash] .right = null; return;} PTR = & haveht [hash]; insertnode (ptr, val);}

Void HashTable :: PrintHasht () {INT I; for (i = 0; I

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}} 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 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 #include #include struct hasht {bool empty; char field_name [32]; struct hasht * left; struct hasht * right;}; # define prime 13class 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 printesht ();

}

#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 }