c语言实现hash
‘壹’ 如何使用c语言获取文件的SHA1哈希值
有现成的SHA1算法函数
复制过来。
然后打开文件， 读数据， 调用SHA1函数即可。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<errno.h>
#undefBIG_ENDIAN_HOST
typedefunsignedintu32;
/****************
*Rotatea32bitintegerbynbytes
*/
#ifdefined(__GNUC__)&&defined(__i386__)
staticinlineu32
rol(u32x,intn)
{
__asm__("roll%%cl,%0"
:"=r"(x)
:"0"(x),"c"(n));
returnx;
}
#else
#definerol(x,n)(((x)<<(n))|((x)>>(32-(n))))
#endif
typedefstruct{
u32h0,h1,h2,h3,h4;
u32nblocks;
unsignedcharbuf[64];
intcount;
}SHA1_CONTEXT;void
sha1_init(SHA1_CONTEXT*hd)
{
hd->h0=0x67452301;
hd->h1=0xefcdab89;
hd->h2=0x98badcfe;
hd->h3=0x10325476;
hd->h4=0xc3d2e1f0;
hd->nblocks=0;
hd->count=0;
}
/****************
*-bit-words
*/
staticvoid
transform(SHA1_CONTEXT*hd,unsignedchar*data)
{
u32a,b,c,d,e,tm;
u32x[16];
/*getvaluesfromthechainingvars*/
a=hd->h0;
b=hd->h1;
c=hd->h2;
d=hd->h3;
e=hd->h4;
#ifdefBIG_ENDIAN_HOST
memcpy(x,data,64);
#else
{
inti;
unsignedchar*p2;
for(i=0,p2=(unsignedchar*)x;i<16;i++,p2+=4)
{
p2[3]=*data++;
p2[2]=*data++;
p2[1]=*data++;
p2[0]=*data++;
}
}
#endif
#defineK10x5A827999L
#defineK20x6ED9EBA1L
#defineK30x8F1BBCDCL
#defineK40xCA62C1D6L
#defineF1(x,y,z)(z^(x&(y^z)))
#defineF2(x,y,z)(x^y^z)
#defineF3(x,y,z)((x&y)|(z&(x|y)))
#defineF4(x,y,z)(x^y^z)
#defineM(i)(tm=x[i&0x0f]^x[(i-14)&0x0f]
^x[(i-8)&0x0f]^x[(i-3)&0x0f]
,(x[i&0x0f]=rol(tm,1)))
#defineR(a,b,c,d,e,f,k,m)do{e+=rol(a,5)
+f(b,c,d)
+k
+m;
b=rol(b,30);
}while(0)
R(a,b,c,d,e,F1,K1,x[0]);
R(e,a,b,c,d,F1,K1,x[1]);
R(d,e,a,b,c,F1,K1,x[2]);
R(c,d,e,a,b,F1,K1,x[3]);
R(b,c,d,e,a,F1,K1,x[4]);
R(a,b,c,d,e,F1,K1,x[5]);
R(e,a,b,c,d,F1,K1,x[6]);
R(d,e,a,b,c,F1,K1,x[7]);
R(c,d,e,a,b,F1,K1,x[8]);
R(b,c,d,e,a,F1,K1,x[9]);
R(a,b,c,d,e,F1,K1,x[10]);
R(e,a,b,c,d,F1,K1,x[11]);
R(d,e,a,b,c,F1,K1,x[12]);
R(c,d,e,a,b,F1,K1,x[13]);
R(b,c,d,e,a,F1,K1,x[14]);
R(a,b,c,d,e,F1,K1,x[15]);
R(e,a,b,c,d,F1,K1,M(16));
R(d,e,a,b,c,F1,K1,M(17));
R(c,d,e,a,b,F1,K1,M(18));
R(b,c,d,e,a,F1,K1,M(19));
R(a,b,c,d,e,F2,K2,M(20));
R(e,a,b,c,d,F2,K2,M(21));
R(d,e,a,b,c,F2,K2,M(22));
R(c,d,e,a,b,F2,K2,M(23));
R(b,c,d,e,a,F2,K2,M(24));
R(a,b,c,d,e,F2,K2,M(25));
R(e,a,b,c,d,F2,K2,M(26));
R(d,e,a,b,c,F2,K2,M(27));
R(c,d,e,a,b,F2,K2,M(28));
R(b,c,d,e,a,F2,K2,M(29));
R(a,b,c,d,e,F2,K2,M(30));
R(e,a,b,c,d,F2,K2,M(31));
R(d,e,a,b,c,F2,K2,M(32));
R(c,d,e,a,b,F2,K2,M(33));
R(b,c,d,e,a,F2,K2,M(34));
R(a,b,c,d,e,F2,K2,M(35));
R(e,a,b,c,d,F2,K2,M(36));
R(d,e,a,b,c,F2,K2,M(37));
R(c,d,e,a,b,F2,K2,M(38));
R(b,c,d,e,a,F2,K2,M(39));
R(a,b,c,d,e,F3,K3,M(40));
R(e,a,b,c,d,F3,K3,M(41));
R(d,e,a,b,c,F3,K3,M(42));
R(c,d,e,a,b,F3,K3,M(43));
R(b,c,d,e,a,F3,K3,M(44));
R(a,b,c,d,e,F3,K3,M(45));
R(e,a,b,c,d,F3,K3,M(46));
R(d,e,a,b,c,F3,K3,M(47));
R(c,d,e,a,b,F3,K3,M(48));
R(b,c,d,e,a,F3,K3,M(49));
R(a,b,c,d,e,F3,K3,M(50));
R(e,a,b,c,d,F3,K3,M(51));
R(d,e,a,b,c,F3,K3,M(52));
R(c,d,e,a,b,F3,K3,M(53));
R(b,c,d,e,a,F3,K3,M(54));
R(a,b,c,d,e,F3,K3,M(55));
R(e,a,b,c,d,F3,K3,M(56));
R(d,e,a,b,c,F3,K3,M(57));
R(c,d,e,a,b,F3,K3,M(58));
R(b,c,d,e,a,F3,K3,M(59));
R(a,b,c,d,e,F4,K4,M(60));
R(e,a,b,c,d,F4,K4,M(61));
R(d,e,a,b,c,F4,K4,M(62));
R(c,d,e,a,b,F4,K4,M(63));
R(b,c,d,e,a,F4,K4,M(64));
R(a,b,c,d,e,F4,K4,M(65));
R(e,a,b,c,d,F4,K4,M(66));
R(d,e,a,b,c,F4,K4,M(67));
R(c,d,e,a,b,F4,K4,M(68));
R(b,c,d,e,a,F4,K4,M(69));
R(a,b,c,d,e,F4,K4,M(70));
R(e,a,b,c,d,F4,K4,M(71));
R(d,e,a,b,c,F4,K4,M(72));
R(c,d,e,a,b,F4,K4,M(73));
R(b,c,d,e,a,F4,K4,M(74));
R(a,b,c,d,e,F4,K4,M(75));
R(e,a,b,c,d,F4,K4,M(76));
R(d,e,a,b,c,F4,K4,M(77));
R(c,d,e,a,b,F4,K4,M(78));
R(b,c,d,e,a,F4,K4,M(79));
/*Updatechainingvars*/
hd->h0+=a;
hd->h1+=b;
hd->h2+=c;
hd->h3+=d;
hd->h4+=e;
}
/*
*ofINBUFwithlengthINLEN.
*/
staticvoid
sha1_write(SHA1_CONTEXT*hd,unsignedchar*inbuf,size_tinlen)
{
if(hd->count==64){/*flushthebuffer*/
transform(hd,hd->buf);
hd->count=0;
hd->nblocks++;
}
if(!inbuf)
return;
if(hd->count){
for(;inlen&&hd->count<64;inlen--)
hd->buf[hd->count++]=*inbuf++;
sha1_write(hd,NULL,0);
if(!inlen)
return;
}
while(inlen>=64){
transform(hd,inbuf);
hd->count=0;
hd->nblocks++;
inlen-=64;
inbuf+=64;
}
for(;inlen&&hd->count<64;inlen--)
hd->buf[hd->count++]=*inbuf++;
}
/*
*returnsthedigest.
*,butaddingbytestothe
*.
*Returns:20bytesrepresentingthedigest.
*/
staticvoid
sha1_final(SHA1_CONTEXT*hd)
{
u32t,msb,lsb;
unsignedchar*p;
sha1_write(hd,NULL,0);/*flush*/;
t=hd->nblocks;
/*multiplyby64tomakeabytecount*/
lsb=t<<6;
msb=t>>26;
/*addthecount*/
t=lsb;
if((lsb+=hd->count)<t)
msb++;
/*multiplyby8tomakeabitcount*/
t=lsb;
lsb<<=3;
msb<<=3;
msb|=t>>29;
if(hd->count<56){/*enoughroom*/
hd->buf[hd->count++]=0x80;/*pad*/
while(hd->count<56)
hd->buf[hd->count++]=0;/*pad*/
}
else{/*needoneextrablock*/
hd->buf[hd->count++]=0x80;/*padcharacter*/
while(hd->count<64)
hd->buf[hd->count++]=0;
sha1_write(hd,NULL,0);/*flush*/;
memset(hd->buf,0,56);/*fillnextblockwithzeroes*/
}
/*appendthe64bitcount*/
hd->buf[56]=msb>>24;
hd->buf[57]=msb>>16;
hd->buf[58]=msb>>8;
hd->buf[59]=msb ;
hd->buf[60]=lsb>>24;
hd->buf[61]=lsb>>16;
hd->buf[62]=lsb>>8;
hd->buf[63]=lsb ;
transform(hd,hd->buf);
p=hd->buf;
#ifdefBIG_ENDIAN_HOST
#defineX(a)do{*(u32*)p=hd->h##a;p+=4;}while(0)
#else/*littleendian*/
#defineX(a)do{*p++=hd->h##a>>24;*p++=hd->h##a>>16;
*p++=hd->h##a>>8;*p++=hd->h##a;}while(0)
#endif
X(0);
X(1);
X(2);
X(3);
X(4);
#undefX
}
‘贰’ c语言使用hash表的一个问题，懂得帮忙解决一下，谢谢
elem结构体中的ord开辟内存空间了没
‘叁’ C语言编程，求字符串的hash值（散列值）
#include<stdio.h>
intmain(){
chars[256];
char*p;
unsignedlonglonginth=0;
scanf("%s",s);
for(p=s;*p;p++){
h=h*31+*p;
}
printf("%llu",h);
}
‘肆’ 用哈希表实现C语言关键字的算法
#include <iostream.h>
#include<fstream.h>
#include <string>
#include <iomanip.h>
using namespace std;
const int TOTAL=32;
const int MAXLEN=10;
const int HASHLEN=41;
int cont=0;
class HashTable
{
public:
char keyword[MAXLEN];
int count;
int num;
};
HashTable HS[HASHLEN];
char KeyWords[TOTAL][MAXLEN]= {
"char", "double", "enum", "float", "int", "long", "short", "signed",
"struct", "union", "unsigned", "void", "break", "case", "continue",
"default", "do", "else", "for", "goto", "if", "return", "switch", "while",
"auto", "extern", "register", "static", "const", "sizeof", "typedef", "volatile"
};
template<class T>
class HASH
{
public:
void Show(int key);
int CreatHX(char *keyword);
int GetFreePos(int key);
void ResetHX();
int GetKey(char *keyword);
int isKeyWords(char *word);
int Read(char *filename);
int isLetter(char ch);
int FindHX(char *keyword);
private:
int key;
char *keyword;
char *word;
char ch;
};
template<class T>
void HASH<T>::Show(int key)
{
if(key<0||key>=HASHLEN)
{
cout<<"关键字不存在!"<<endl;
return;
}
if(strlen(HS[key].keyword)==0)
{
cout<<"哈希表位置："<<key<<" 记录是空的"<<endl;
return ;
}
cout<<"哈希表位置: "<<key<<" 关键字: "
<<HS[key].keyword<<" 出现次数 "<<HS[key].count<<endl;
cont++;
}
template<class T>
int HASH<T>::CreatHX(char *keyword)
{
int key;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strlen(HS[key].keyword)>0)
{
if(strcmp(HS[key].keyword,keyword)==0)
{
HS[key].count++;
return 1;
}
key=FindHX(keyword);
if(key<0)
{
key=GetFreePos(GetKey(keyword));
if(key<0) return -1;
strcpy(HS[key].keyword,keyword);
}
if(key<0) return -1;
HS[key].count++;
}
else
{
strcpy(HS[key].keyword,keyword);
HS[key].count++;
}
return 1;
}
template<class T>
int HASH<T>::GetFreePos(int key)
{
int find,tem=0;
if(key<0||key>=HASHLEN) return -1;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
for(find=0;find<key;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}
template<class T>
void HASH<T>::ResetHX()
{
int i;
for(i=0;i<HASHLEN;i++)
{
strcpy(HS[i].keyword,"");
HS[i].count=0;
HS[i].num=0;
}
}
template<class T>
int HASH<T>::GetKey(char *keyword)
{
return ( keyword[0]*100+keyword[strlen(keyword)-1] ) % 41;
}
template<class T>
int HASH<T>::isKeyWords(char *word)
{
int i;
for(i=0;i<TOTAL;i++)
if(strcmp(word,KeyWords[i])==0) return 1;
return 0;
}
template<class T>
int HASH<T>::isLetter(char ch)
{
if( (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z') ) return 1;
else return 0;
}
template<class T>
int HASH<T>::FindHX(char *keyword)
{
int key,find,tem=0;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strcmp(HS[key].keyword,keyword)==0) return key;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
for(find=0;find<key;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}
template<class T>
int HASH<T>::Read(char *filename)
{
char word[MAXLEN],ch;
int i;
FILE *read;
fstream myfile;
myfile.open("filename");
if(!myfile)
{
cout<<"文件不存在,请确认好再输入!"<<endl;
return -1;
}
ResetHX();
while(!feof(read))
{
i=0;
ch=fgetc(read);
while(isLetter(ch)==0 && feof(read)==0 )
ch=fgetc(read);
while(isLetter(ch)==1 && feof(read)==0 )
{
if(i==MAXLEN)
{
while(isLetter(ch)==1&& feof(read)==0)
{
ch=fgetc(read);
}
i=0;
break;
}
else
{
word[i++]=ch;
ch=fgetc(read);
}
}
word[i]='\0';
if(isKeyWords(word))
{
CreatHX(word);
}
}
fclose(read);
cout<<"读取成功，文件中关键字已经存入hash表，请继续操作"<<endl;
return 1;
}
void main()
{
HASH<char> hash;
char filename[128],word[MAXLEN];
int i=0,count=0;
int key;
char j,y;
cout<<"请输入要读取的文件名:";
cin>>filename;
cout<<endl;
hash.Read(filename);
for(i=0;i<HASHLEN;i++)
{
hash.Show(i);
getchar();
}
cout<<"关键字总数为："<<cont<<endl;
cout<<"请输入你想要查找的关键字： ";
cin>>word;
cout<<endl;
hash.Show(hash.FindHX(word));
cout<<" C语言中的关键字和其在哈希表的位置:"<<endl;
for(i=0;i<TOTAL;i++)
{
cout<<setiosflags(ios::left)<<"["<<setw(2)<<hash.GetKey(KeyWords[i])<<"]"
<<setiosflags(ios::left)<<setw(11)<<KeyWords[i];
if((i+1)%4==0) cout<<endl;
}
cout<<"是否显示冲突关键字列表？y(是) 其它（否）:";
cin>>j;
if(j=='y')
{
cout<<"冲突关键字列表"<<endl;
for(i=0;i<HASHLEN;i++)
{
if(strlen(HS[i].keyword)>0)
{
key=hash.GetKey(HS[i].keyword);
if(key!=i)
{
count++;
cout<<setiosflags(ios::left)<<setw(14)<<
"\t[关键 字]:"<<HS[i].keyword<<setiosflags(ios::left)<<
setw(20)<<"\t[哈希表当前位置]: "<<i<<setiosflags(ios::left)<<
setw(20)<<"\t[冲突次数]: "<<HS[i].num<<endl;
}
}
}
if(count==0)
cout<<"没有冲突"<<endl;
else
cout<<"\t冲突关键字共:"<<count<<"个"<<endl;
}
else
cout<<"不显示冲突关键字列表，但已存在！"<<endl;
return;
}
‘伍’ c语言hash函数有几种
#include<stdio.h>#include<stdlib.h>//这里我自己设计一个hash算法来快速查找一堆数字中相等的数字，这也许是最接近原理的算法了//一个整数整除27后的来作为hash函数//定义一个保存实际数据的结构体节点structdata_node{intnum;intcount;structdata_node*next;};//定义一个结构体时hash表的一部分typedefstruct{intkey;//余数structdata_node*p;//链表的头指针}hash_node;#defineHASH_SIZE27intdo_hash(intnum)//hash表来求余数，这样就可以了{returnnum%HASH_SIZE;}//初始化//添加数字//更新数字//删除数字//查找数字hash_nodeHashTable[HASH_SIZE];//这里申明一个hashtable的数组//初始化函数，需要做的事将key复制为null，将p指针指向null,返回一个头指针来指向这个hashtablevoidInitHashTable(hash_node*HashTable)
{//进行参数的校验for(inti=0;i<HASH_SIZE;i++)
{
HashTable[i].key=0;HashTable[i].p=NULL;}
}//保存到这个链表中//如果这个链表是空的话，就作为头指针，如果这个链表不为空，则添加到吧数字添加到末尾intsavedata(structdata_node**head,intnum)
{structdata_node*tmp_p=*head;structdata_node*p=(structdata_node*)malloc(sizeof(structdata_node));if(p==NULL)return0;if(*head==NULL)
{
*head=p;p->count=1;p->num=num;p->next=NULL;}else//如果不为空，则这个时候应该添加到链表末尾{while(tmp_p!=NULL)//如果存在，则将这个节点的count加1就可以了{if(tmp_p->num==num)
{
free(p);++tmp_p->count;return0;}if(tmp_p->next==NULL)break;tmp_p=tmp_p->next;}
tmp_p->next=p;p->count=1;p->num=num;p->next=NULL;}return0;}//添加数字//将这个数字经过hash求出结果，然后再保存到相应的链表中//返回真或者假就可以了intadd_hash(hash_node*HashTable,intnum)
{intmod=do_hash(num);returnsavedata(&HashTable[mod].p,num);}intmain()
{intnum=100;hash_node*H=HashTable;InitHashTable(H);add_hash(H,num);add_hash(H,num);add_hash(H,3);add_hash(H,1);add_hash(H,4);//在这里我们可以发现一个好的hash函数是多么的重要，如果hash函数不好造成很多冲突的话，效率并不会提高很多的，理想的情况是冲突几乎没有//这也就是设计hash函数的精髓所在return0;}
‘陆’ redis中怎么实现hash表的c语言函数
获敏旦斗取hash表的所有域值
[plain] view plain
redis 127.0.0.1:6379> hgetall user.2 #存在的hash表
1) "name" #域
2) "niuer" #域name的值迟键
3) "age" #域
4) "34" #域age的值桥磨
redis 127.0.0.1:6379> hgetall user.3 #不存在的hansh表
(empty list or set)
‘柒’ Hash表的设计 (2人)(使用C语言)
#include<iostream>
#include<string>
using namespace std;
#define HASH_LENGTH 50 //哈希表的长度
#define M 47 //随机数
#define NAME_NO 30 //人名的个数
typedef struct
{ char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LENGTH]; //全局变量NAME
typedef struct //哈希表
{ char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LENGTH]; //全局变量HASH
void InitNameList() //姓名（结构体数组乎羡）初始化
{ char *f;
int r,s0,i;
for (i=0; i<HASH_LENGTH; i++)//★
{//★
NameList[i].py = new char[64];//★
NameList[i].py[0] = 0;//★
}//★
strcpy(NameList[0].py, "baojie");//★
strcpy(NameList[1].py, "chengaoyang");//★
strcpy(NameList[2].py, "chenguangzhong");//★
strcpy(NameList[3].py, "chenliangliang");//★
strcpy(NameList[4].py, "chenyongzhou");//★
strcpy(NameList[5].py, "fengchao");//★
strcpy(NameList[6].py, "gexiangfeng");//★
strcpy(NameList[7].py, "huting");//★
strcpy(NameList[8].py, "huangpinjin");//★
strcpy(NameList[9].py, "jiangxiaojia");//★
strcpy(NameList[10].py, "laidongjie");//★
strcpy(NameList[11].py, "liyexiao");//★
strcpy(NameList[12].py, "lihui");//★
strcpy(NameList[13].py, "lijue");//★
strcpy(NameList[14].py, "lizhuoqun");//★
strcpy(NameList[15].py, "linfujun");//★
strcpy(NameList[16].py, "luobin");//辩顷纤★
strcpy(NameList[17].py, "luokeqing");//★
strcpy(NameList[18].py, "nichao"携仿);//★
strcpy(NameList[19].py, "panhuafeng");//★
strcpy(NameList[20].py, "sijun");//★
strcpy(NameList[21].py, "songzhanhui"); //★
strcpy(NameList[22].py, "sunzhengqing");//★
strcpy(NameList[23].py, "wanghaofeng");//★
strcpy(NameList[24].py, "wangjunshuai");//★
strcpy(NameList[25].py, "wangqinde");//★
strcpy(NameList[26].py, "wangzejun");//★
strcpy(NameList[27].py, "wangkeke");//★
strcpy(NameList[28].py, "weixing");//★
strcpy(NameList[29].py, "wurenke");//★
for(i=0;i<NAME_NO;i++)
{
s0=0;
f=NameList[i].py;
for(r=0;*(f+r)!='\0';r++)
/* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/
s0=*(f+r)+s0;
NameList[i].k=s0;
}
}
void CreateHashList() //建立哈希表
{
int i;
for(i=0; i<HASH_LENGTH;i++)
{
HashList[i].py=new char[64];//★
HashList[i].py[0] = 0; //★
HashList[i].k=0;
HashList[i].si=0;
}
for(i=0;i<HASH_LENGTH;i++)
{
int sum=0;
int adr=(NameList[i].k)%M;
//哈希函数
int d=adr;
if(HashList[adr].si==0) //如果不冲突
{
HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突
{
while (HashList[d].k!=0)
{
d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1; //查找次数加1
};
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}
}
}
void FindList() //查找
{
string name;
int s0=0,r,sum=1,adr,d;
cout<<"请输入姓名的拼音:"<<endl;
cin>>name;;
for(r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
adr=s0%M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
cout<<"姓名:"<<HashList[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为: 1"<<endl;
else if (HashList[adr].k==0)
cout<<"无此记录!"<<endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1;
if(HashList[d].k==0)
{
cout<<"无此记录!"<<endl;
g=1;
}
if(HashList[d].k==s0)
{
cout<<"姓名:"<<HashList[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为:"<<sum<<endl;
g=1;
}
};
}
}
void Display() // 显示哈希表
{
int i;
float average=0;
cout<<"\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"; //显示的格式
for(i=0; i<50; i++)
{
cout<<i<<" ";
cout<<"\t"<<HashList[i].k<<" ";
cout<<"\t\t"<<HashList[i].si<<" ";
cout<<"\t\t"<<(HashList[i].k%M)<<" ";
cout<<"\t "<<HashList[i].py<<" ";
cout<<"\n";
}
for(i=0;i<HASH_LENGTH;i++)
average+=HashList[i].si;
average/=NAME_NO;
cout<<"平均查找长度：ASL("<<NAME_NO<<")="<<average<<endl;
}
int main()
{
char x;
InitNameList();
CreateHashList ();
cout<<"d. 显示哈希表 f. 查找 任意键退出 请选择："<<endl;
while(cin>>x)
{
if(x=='d')
{
Display();
cout<<endl;
}
else if(x=='f')
{
FindList();
cout<<endl;
}
else break;
}
for (int i=0; i<HASH_LENGTH; i++)//★
{
free(NameList[i].py);//★
free(HashList[i].py);//★
}//★
return 0;
}
希望能帮助到你。
‘捌’ 数据结构-如何用二叉树实现hash表（C语言）
在用二叉树实现散列表之前，首先需要明白的是二叉树与散列表各自的特性。
对于二叉树，主要表现形式是一对二；拿链型二叉树来说，即一个结点含有一个前驱，两个后继，两个后继即是该结点的两个孩子，如图。建立和处理用递归的方法可以轻松实现。具体关于树的结构在此不再详解。
对于散列表，通俗来说，即对于将要插入的元素再通过一种函数式（如取余）后，得到一个具体数字（或字符），这个数字（或字符）将决定该元素所存放的位置，如果这个位置已经存有元素，则需要再次经过一系列的处理（或计算）得到一个新的地址位置，然后再原来的元素存入该为空的位置；具体的实现方法在此也不再详解。
在对两者进行结合的过程中，需要考虑两者的特性，然后再进行实现。下面是个人在VC环境下使用了两个自定义函数对其进行中序实现的过程。
数字可以分为两种，奇数和偶数，根据此特点，可以对该数字进行不断的除二取余的方式得到储存地址
如图，首先插入的数是2,2%2==0，则在头结点的左边建立一个晌纳结点，存放数字2，并将其地址赋予头结点的lchild，然后插入的是奇数3，判断得其为奇数，故存放与右侧地址2；在再次插入偶数6时，经判断，6是偶数，而地址1中又存有元素，则需要重新寻找新的空的地址，再次做出的处理是6/2=3；3是奇数，则存放的是4，即作为1的右子树，依次类推，在相应的地址已经存放有元素的情况下，改变参数，寻找新的地址。由于每个数在取余过一定的次数以后，得到的数是不会重复的，所以每一个数字都会有一个地址来存放，不会发生冲突，二叉树就可以顺利实现。
在其中需要注意的是，每个元素在经过除二之后虽消型然参数发生了变化，但是在找到并开辟好了需要存放该元素的空间后，存放的元素却还是客户端键入的原数字，所以在程序的运行中，要注意赋值对象是否正确。所以我在程序的实现中，采用了函数嵌套的方法，一个函数的作用是找到地址开辟空间，其返回值便是需要进行赋值的空间，在调用过后，只需将原来的元素放到该返回地址的相应区域即可。
如果各位还不够明白，则下面开始解读程序。
在运行开始，用户首先键入数字2，初始化成功的情况下，判断出2的存放位置应是位置1，（满足条件2%2==0&&p->lchild==NULL）这时宴桥没建立一个结点，把这个结点放到头结点的左子树处，返回这个新建结点的地址，find函数执行一次，由于判断语句是else if型，直接退出进入insert函数实现赋值。在插入12时，满足else if (data%2==0&&p->lchild !=NULL)，进入递归，p指向的是地址1,12/2==6，参数为6，对6继续判断，满足else if (data%2==0&&p->lchild!=NULL)，再次递归，直到else if (data%2==1&&p->rchild==NULL)，此时，data为3，开始创建空间并且退出递归，最后，在insert中返回的地址仍为新开辟的地址，此时开始赋值。
在进行删除的过程中，只需要找到对应与欲删除元素相匹配的地址，然后改变地址中元素的值即可（如if (p->data==data)p->data=-1;）遍历时遇到-1即不进行遍历即可，不需要释放空间。
以上存属个人看法，如有不足，欢迎指正。
‘玖’ 谁能帮忙写一个C语言的哈希排序小女感激不尽~~
1.选择合适的哈希函数H(key)=key%p(p为小于或等于哈希表长的最大质数)；
2.计算各个关键字的直接哈希函数值；
3.根据处理冲突的方法建立哈希表，并输出；
4.在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。
#include<stdlib.h>
#include<stdio.h>
#define NULL 0
typedef int KeyType;
typedef struct
{
KeyType key;
} ElemType;
int haxi(KeyType key,int m) /*根据哈希表长m，构造除留余数法的哈希函数haxi*/
{
int i,p,flag;
for(p=m;p>=2;p--) /*p为不超过m的最大素数*/
{
for(i=2,flag=1;i<=p/2&&flag;i++)
if(p%i==0)
flag=0;
if(flag==1)
break;
}
return key%p; /*哈希函数*/
}
void inputdata(ElemType **ST,int n) /*从键盘输入n个数据，存入数据表ST(采用动态分配的数组空间)*/
{
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\nPlease input %d data:",n);
for(i=1;i<=n;i++)
scanf("%d",&((*ST)[i].key));
}
void createhaxi(ElemType **HASH,ElemType *ST,int n,int m) /*由数据表ST构造哈希表HASH，n、m分别为数据集合ST和哈希表的长度*/
{
int i,j;
(*HASH)=(ElemType *)malloc(m*sizeof(ElemType));
for(i=0;i<m;i++)
(*HASH)[i].key=NULL; /*初始化哈希为空表(以0表示空)*/
for(i=0;i<n;i++)
{
j=haxi(ST[i].key,m); /*获得直接哈希地址*/
while((*HASH)[j].key!=NULL)
j=(j+1)%m; /*用线性探测再散列技术确定存放位置*/
(*HASH)[j].key=ST[i].key; /*将元素存入哈希表的相应位置*/
}
}
int search(ElemType *HASH,KeyType key,int m,int *time) /*在表长为m的哈希表中查找关键字等于key的元素，并用time记录比较次数，若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/
{
int i;
*time=1;
i=haxi(key,m);
while(HASH[i].key!=0&&HASH[i].key!=key)
{
i++;
++*time;
}
if(HASH[i].key==0)
return -1;
else
return i;
}
main()
{
ElemType *ST,*HASH;
KeyType key;
int i,n,m,stime,time;
char ch;
printf("\nPlease input n&&m(n<=m)"); /*输入关键字集合元素个数和哈希表长*/
scanf("%d%d",&n,&m);
inputdata(&ST,n); /*输入n个数据*/
createhaxi(&HASH,ST,n,m); /*创建哈希表*/
printf("\nThe haxi Table is\n"); /*输出已建立的哈希表*/
for(i=0;i<m;i++)
printf("%5d",i);
printf("\n");
for(i=0;i<m;i++)
printf("%5d",HASH[i].key);
do /*哈希表的查找，可进行多次查找*/
{
printf("\nInput the key you want to search:");
scanf("%d",&key);
i=search(HASH,key,m,&time);
if(i!=-1) /*查找成功*/
{
printf("\nSuccess,the position is %d",i);
printf("\nThe time of compare is %d",time);
}
else /*查找失败*/
{
printf("\nUnsuccess");
printf("\nThe time of compare is %d",time);
}
printf("\nContiue(y/n):\n"); /*是否继续查找yes or no*/
ch=getch();
}
while(ch=='y'||ch=='Y'); /*计算表在等概率情况下的平均查找长度，并输出*/
for(stime=0,i=0;i<n;i++)
{
search(HASH,ST[i].key,m,&time);
stime+=time;
}
printf("\nThe Average Search Length is %5.2f",(float)stime/n);
ch=getch();
}
‘拾’ C语言哈希表
/#include "iostream.h"
#include <iostream>
#include "string.h"
#include "fstream"
#define NULL 0
unsigned int key;
unsigned int key2;
int *p;
struct node //建节点
{
char name[8],address[20];
char num[11];
node * next;
};
typedef node* pnode;
typedef node* mingzi;
node **phone;
node **nam;
node *a;
using namespace std; //使用名称空间
void hash(char num[11]) //哈希函数
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20;
}
void hash2(char name[8]) //哈希函数
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
key2=key2%20;
}
node* input() //输入节点
{
node *temp;
temp = new node;
temp->next=NULL;
cout<<"输入姓名："<<endl;
cin>>temp->name;
cout<<"输入地址："<<endl;
cin>>temp->address;
cout<<"输入电话："<<endl;
cin>>temp->num;
return temp;
}
int apend() //添加节点
{
node *newphone;
node *newname;
newphone=input();
newname=newphone;
newphone->next=NULL;
newname->next=NULL;
hash(newphone->num);
hash2(newname->name);
newphone->next = phone[key]->next;
phone[key]->next=newphone;
newname->next = nam[key2]->next;
nam[key2]->next=newname;
return 0;
}
void create() //新建节点
{
int i;
phone=new pnode[20];
for(i=0;i<20;i++)
{
phone[i]=new node;
phone[i]->next=NULL;
}
}
void create2() //新建节点
{
int i;
nam=new mingzi[20];
for(i=0;i<20;i++)
{
nam[i]=new node;
nam[i]->next=NULL;
}
}
void list() //显示列表
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
p=p->next;
}
}
}
void list2() //显示列表
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=nam[i]->next;
while(p)
{
cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;
p=p->next;
}
}
}
void find(char num[11]) //查找用户信息
{
hash(num);
node *q=phone[key]->next;
while(q!= NULL)
{
if(strcmp(num,q->num)==0)
break;
q=q->next;
}
if(q)
cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;
else cout<<"无此记录"<<endl;
}
void find2(char name[8]) //查找用户信息
{
hash2(name);
node *q=nam[key2]->next;
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
break;
q=q->next;
}
if(q)
cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;
else cout<<"无此记录"<<endl;
}
void save() //保存用户信息
{
int i;
node *p;
for(i=0;i<20;i++)
{
p=phone[i]->next;
while(p)
{
fstream iiout("out.txt", ios::out);
iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl;
p=p->next;
}
}
}
void menu() //菜单
{
cout<<"0.添加记录"<<endl;
cout<<"3.查找记录"<<endl;
cout<<"2.姓名散列"<<endl;
cout<<"4.号码散列"<<endl;
cout<<"5.清空记录"<<endl;
cout<<"6.保存记录"<<endl;
cout<<"7.退出系统"<<endl;
}
int main()
{
char num[11];
char name[8];
create();
create2() ;
int sel;
while(1)
{
menu();
cin>>sel;
if(sel==3)
{ cout<<"9号码查询，8姓名查询"<<endl;
int b;
cin>>b;
if(b==9)
{ cout<<"请输入电话号码:"<<endl;
cin >>num;
cout<<"输出查找的信息:"<<endl;
find(num);
}
else
{ cout<<"请输入姓名:"<<endl;
cin >>name;
cout<<"输出查找的信息:"<<endl;
find2(name);}
}
if(sel==2)
{ cout<<"姓名散列结果:"<<endl;
list2();
}
if(sel==0)
{ cout<<"请输入要添加的内容:"<<endl;
apend();
}
if(sel==4)
{ cout<<"号码散列结果:"<<endl;
list();
}
if(sel==5)
{ cout<<"列表已清空:"<<endl;
create();
create2();
}
if(sel==6)
{ cout<<"通信录已保存:"<<endl;
save();
}
if(sel==7) return 0;
}
return 0;
}