最近在学习散列。学的很迷糊。我就找了个别人编的程序看看。 以下代码仅在 g++ 3.4.2中编译通过，令人惊奇的是VC 2005竟然编译出错，看来以后用VC 2005还得小心才行。   //结点类型template <typename T, typename Tar>struct node...{    T data;    Tar value;    node* next;    //初始化为空    node()        : value(0), next(NULL)    ...{}};//Hash表//第一个类型参数的类型可以是：int, long, char, string//第二个类型参数的类型可以是：int, bool, char//此Hash表支持的操作有：//insert(T x)：将类型为T的元素插入hash表中，如果已存在则直接退出//search(T x)：查找是否存在值为x的元素（返回bool型）//remove(T x)：将值为x的元素从表中删除//对于[]的重载：返回value域的引用template <typename T, typename Tar>class Hash_Table...{private:    static const int size = 350899;    //尺寸    node<T, Tar> *t;    //直接hash    inline int hash(int n)    ...{        return n % size;    }    //用于串的elfhash    inline int hash(const char* key)    ...{        unsigned int h = 0;        while (*key)        ...{            h = (h << 4) + *key++;            unsigned int g = h & 0xF0000000L;            if (g)                h ^= g >> 24;            h &= ~g;        }        return h % size;    }    //string的elfhash    inline int hash(const string& str)    ...{        return hash(str.c_str());    }public:    Hash_Table()        : t(new node<T, Tar>[size])    ...{}    //插入一个元素    inline void insert(const T& item)    ...{        if (search(item))    //如果已存在就退出            return;        int key = hash(item);        if (!t[key].value)    //空的        ...{            t[key].value = 1;            t[key].data = item;            t[key].next = NULL;        }        else    //非空，insert item at the head of the list        ...{            node<T, Tar>* tmp = new node<T, Tar>;            tmp->value = t[key].value;            tmp->data = t[key].data;            tmp->next = t[key].next;            t[key].value = 1;            t[key].data = item;            t[key].next = tmp;        }    }    inline bool search(const T& item)    ...{        int key = hash(item);        if (!t[key].value) //空的            return false;        node<T, Tar>* tmp = &t[key];        while (tmp->next != NULL && tmp->data != item)            tmp = tmp->next;        return (tmp->data == item);    }    inline void remove(const T& item)    ...{        int key = hash(item);        if (t[key].value && t[key].data == item)    //不空,并且要删的是第一个        ...{            if (t[key].next != NULL)            ...{                node<T, Tar>* tmp = t[key].next;                t[key].data = tmp->data;                t[key].next = tmp->next;                delete tmp;            }            else                t[key].value = 0;        }        else        ...{            if (t[key].value)    //不空才执行            ...{                node<T, Tar>* tmp = &t[key];                while (tmp->next != NULL && tmp->next->data != item)                    tmp = tmp->next;                if (tmp->next != NULL)                ...{                    node<T, Tar>* p = tmp->next;                    tmp->next = p->next;                    delete p;                }            }        }    }    Tar& operator[](const T& item)    ...{        int key = hash(item);        node<T, Tar>* tmp = &t[key];        while (tmp->next != NULL && tmp->data != item)            tmp = tmp->next;        tmp->data = item;        return tmp->value;    }};

评论