超简略哈希表的实现

lchjczw 2013-01-08

展开全文

#ifndef _MY_HASHTABLE_HEAD

002 #define _MY_HASHTABLE_HEAD

003

004 #include <string.h>

005

006 template <typename T>

007 class Hash//哈希表说到底和桶排序、基数排序一个原理，均基于分治策略

008 {

009 public:

010 T error;//寻址不存在时或者键为空时给出它

011 T start;//自动增加模式时用来初始化新元素

012 bool type;//默认为假，不自动增加元素。为真，则寻址不存在时自动增加元素。

013 protected:

014 struct Proj{

015 char *key;

016 T vlu;

017 Proj *nxt;

018 }*(bar)[2593];//2593个桶，差不多10kb的大小用来储存地址

019 public:

020 Hash();

021 Hash(char**,T*,short);

022 ~Hash();

023 void add(char*,T);

024 void add(char**,T*,short);

025 bool fnd(char*);

026 void del(char*);

027 void cls();

028 void show();

029 T& operator[](char*);

030 };

031 template <typename T>

032 Hash<T>::Hash()

033 {

034 short i;

035 for(i=0;i<2593;i++)bar[i]=NULL;

036 type=false;

037 }

038 template <typename T>

039 Hash<T>::Hash(char **ps,T *pv,short nm)

040 {

041 unsigned char *w;

042 Proj *p,*q;

043 long t;

044 for(t=0;t<2593;t++)bar[t]=NULL;

045 for(nm--;nm>=0;nm--)

046 if(ps[nm][0])

047 {

048 for(w=(unsigned char*)ps[nm],t=1;*w;w++)t=(t*256+*w)%2593;//取得桶号

049 for(p=bar[t];p;p=p->nxt)

050 if(strcmp(p->key,ps[nm])==0)

051 break;

052 if(!p)//不存在该键值对，插入新元素

053 {

054 q=new Proj;

055 q->key=new char[(char*)w-ps[nm]+1];

056 strcpy(q->key,ps[nm]);

057 q->vlu=pv[nm];

058 q->nxt=bar[t];

059 bar[t]=q;

060 }

061 else p->vlu=pv[nm];//存在则覆盖老键值对

062 }

063 }

064 template <typename T>

065 Hash<T>::~Hash()

066 {

067 Proj *p,*q;

068 short i;

069 for(i=0;i<2593;i++)

070 if(bar[i])

071 for(p=bar[i];p;p=q)

072 (q=p->nxt,delete p->key,delete p);

073 }

074 template <typename T>

075 void Hash<T>::add(char *s, T v)

076 {

077 unsigned char *w;

078 Proj *p,*q;

079 long t;

080 if(*s)

081 {

082 for(w=(unsigned char*)s,t=1;*w;w++)t=(t*256+*w)%2593;

083 for(p=bar[t];p;p=p->nxt)

084 if(strcmp(p->key,s)==0)

085 break;

086 if(!p)

087 {

088 q=new Proj;

089 q->key=new char[(char*)w-s+1];

090 strcpy(q->key,s);

091 q->vlu=v;

092 q->nxt=bar[t];

093 bar[t]=q;

094 }

095 else p->vlu=v;

096 }

097 }

098 template <typename T>

099 void Hash<T>::add(char **ps,T *pv,short nm)

100 {

101 unsigned char *w;

102 Proj *p,*q;

103 long t;

104 for(nm--;nm>=0;nm--)

105 if(ps[nm][0])

106 {

107 for(w=(unsigned char*)ps[nm],t=1;*w;w++)t=(t*256+*w)%2593;//取得桶号

108 for(p=bar[t];p;p=p->nxt)

109 if(strcmp(p->key,ps[nm])==0)

110 break;

111 if(!p)

112 {

113 q=new Proj;

114 q->key=new char[(char*)w-ps[nm]+1];

115 strcpy(q->key,ps[nm]);

116 q->vlu=pv[nm];

117 q->nxt=bar[t];

118 bar[t]=q;

119 }

120 else p->vlu=pv[nm];

121 }

122 }

123 template <typename T>

124 void Hash<T>::del(char *s)

125 {

126 unsigned char *w;

127 Proj *p,*q;

128 long t;

129 if(*s)

130 {

131 for(w=(unsigned char*)s,t=1;*w;w++)t=(t*256+*w)%2593;//取得桶号

132 for(q=NULL,p=bar[t];p;q=p,p=p->nxt)

133 if(strcmp(p->key,s)==0)

134 break;

135 if(p)//查到元素存在，进行删除操作

136 {

137 if(q)q->nxt=p->nxt;//在中间

138 else bar[t]=p->nxt;//在头部

139 delete p->key;

140 delete p;

141 }

142 }

143 }

144 template <typename T>

145 void Hash<T>::cls()

146 {

147 Proj *p,*q;

148 short i;

149 for(i=0;i<2593;i++)

150 if(bar[i])

151 {

152 for(p=bar[i];p;p=q)

153 (q=p->nxt,delete p->key,delete p);

154 bar[i]=NULL;

155 }

156 }

157 template <typename T>

158 void Hash<T>::show()

159 {

160 Proj *p,*q;

161 short i,t;

162 for(i=0;i<2593;i++)

163 if(bar[i])

164 {

165 printf("%-4d:",i);

166 for(p=bar[i],t=0;p;t++,p=p->nxt)printf("[%s]",p->key);

167 printf("\n");

168 }

169 }

170 template <typename T>

171 T& Hash<T>::operator[](char *s)

172 {

173 unsigned char *w;

174 Proj *p;

175 long t;

176 if(*s)

177 {

178 for(w=(unsigned char*)s,t=1;*w;w++)t=(t*256+*w)%2593;

179 for(p=bar[t];p;p=p->nxt)

180 if(strcmp(p->key,s)==0)

181 break;

182 if(p)

183 {

184 return p->vlu;

185 }

186 else if(type)

187 {

188 p=new Proj;

189 p->key=new char[(char*)w-s+1];

190 strcpy(p->key,s);

191 p->vlu=start;

192 p->nxt=bar[t];

193 bar[t]=p;

194 return p->vlu;

195 }

196 }

197 return error;

198 }

199

200 #endif