- #ifndef _MY_HASHTABLE_HEAD
- #define _MY_HASHTABLE_HEAD
- #include <string.h>
- template <typename T>
- class Hash//哈希表说到底和桶排序、基数排序一个原理,均基于分治策略
- {
- public:
- T error;//寻址不存在时或者键为空时给出它
- T start;//自动增加模式时用来初始化新元素
- bool type;//默认为假,不自动增加元素。为真,则寻址不存在时自动增加元素。
- protected:
- struct Proj{
- char *key;
- T vlu;
- Proj *nxt;
- }*(bar)[2593];//2593个桶,差不多10kb的大小用来储存地址
- public:
- Hash();
- Hash(char**,T*,short);
- ~Hash();
- void add(char*,T);
- void add(char**,T*,short);
- bool fnd(char*);
- void del(char*);
- void cls();
- void show();
- T& operator[](char*);
- };
- template <typename T>
- Hash<T>::Hash()
- {
- short i;
- for(i=0;i<2593;i++)bar[i]=NULL;
- type=false;
- }
- template <typename T>
- Hash<T>::Hash(char **ps,T *pv,short nm)
- {
- unsigned char *w;
- Proj *p,*q;
- long t;
- for(t=0;t<2593;t++)bar[t]=NULL;
- for(nm--;nm>=0;nm--)
- if(ps[nm][0])
- {
- for(w=(unsigned char*)ps[nm],t=1;*w;w++)t=(t*256+*w)%2593;//取得桶号
- for(p=bar[t];p;p=p->nxt)
- if(strcmp(p->key,ps[nm])==0)
- break;
- if(!p)//不存在该键值对,插入新元素
- {
- q=new Proj;
- q->key=new char[(char*)w-ps[nm]+1];
- strcpy(q->key,ps[nm]);
- q->vlu=pv[nm];
- q->nxt=bar[t];
- bar[t]=q;
- }
- else p->vlu=pv[nm];//存在则覆盖老键值对
- }
- }
- template <typename T>
- Hash<T>::~Hash()
- {
- Proj *p,*q;
- short i;
- for(i=0;i<2593;i++)
- if(bar[i])
- for(p=bar[i];p;p=q)
- (q=p->nxt,delete p->key,delete p);
- }
- template <typename T>
- void Hash<T>::add(char *s, T v)
- {
- unsigned char *w;
- Proj *p,*q;
- long t;
- if(*s)
- {
- for(w=(unsigned char*)s,t=1;*w;w++)t=(t*256+*w)%2593;
- for(p=bar[t];p;p=p->nxt)
- if(strcmp(p->key,s)==0)
- break;
- if(!p)
- {
- q=new Proj;
- q->key=new char[(char*)w-s+1];
- strcpy(q->key,s);
- q->vlu=v;
- q->nxt=bar[t];
- bar[t]=q;
- }
- else p->vlu=v;
- }
- }
- template <typename T>
- void Hash<T>::add(char **ps,T *pv,short nm)
- {
- unsigned char *w;
- Proj *p,*q;
- long t;
- for(nm--;nm>=0;nm--)
- if(ps[nm][0])
- {
- for(w=(unsigned char*)ps[nm],t=1;*w;w++)t=(t*256+*w)%2593;//取得桶号
- for(p=bar[t];p;p=p->nxt)
- if(strcmp(p->key,ps[nm])==0)
- break;
- if(!p)
- {
- q=new Proj;
- q->key=new char[(char*)w-ps[nm]+1];
- strcpy(q->key,ps[nm]);
- q->vlu=pv[nm];
- q->nxt=bar[t];
- bar[t]=q;
- }
- else p->vlu=pv[nm];
- }
- }
- template <typename T>
- void Hash<T>::del(char *s)
- {
- unsigned char *w;
- Proj *p,*q;
- long t;
- if(*s)
- {
- for(w=(unsigned char*)s,t=1;*w;w++)t=(t*256+*w)%2593;//取得桶号
- for(q=NULL,p=bar[t];p;q=p,p=p->nxt)
- if(strcmp(p->key,s)==0)
- break;
- if(p)//查到元素存在,进行删除操作
- {
- if(q)q->nxt=p->nxt;//在中间
- else bar[t]=p->nxt;//在头部
- delete p->key;
- delete p;
- }
- }
- }
- template <typename T>
- void Hash<T>::cls()
- {
- Proj *p,*q;
- short i;
- for(i=0;i<2593;i++)
- if(bar[i])
- {
- for(p=bar[i];p;p=q)
- (q=p->nxt,delete p->key,delete p);
- bar[i]=NULL;
- }
- }
- template <typename T>
- void Hash<T>::show()
- {
- Proj *p,*q;
- short i,t;
- for(i=0;i<2593;i++)
- if(bar[i])
- {
- printf("%-4d:",i);
- for(p=bar[i],t=0;p;t++,p=p->nxt)printf("[%s]",p->key);
- printf("\\n");
- }
- }
- template <typename T>
- T& Hash<T>::operator[](char *s)
- {
- unsigned char *w;
- Proj *p;
- long t;
- if(*s)
- {
- for(w=(unsigned char*)s,t=1;*w;w++)t=(t*256+*w)%2593;
- for(p=bar[t];p;p=p->nxt)
- if(strcmp(p->key,s)==0)
- break;
- if(p)
- {
- return p->vlu;
- }
- else if(type)
- {
- p=new Proj;
- p->key=new char[(char*)w-s+1];
- strcpy(p->key,s);
- p->vlu=start;
- p->nxt=bar[t];
- bar[t]=p;
- return p->vlu;
- }
- }
- return error;
- }
- #endif
- //该片段来自于http://www.codesnippet.cn/detail/130820135129.html
来源: http://www.codesnippet.cn/detail/130820135129.html