正文
哈希表的插入函数c语言,c实现哈希表
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
C语言中的hash函数
Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码里，叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。Hash算法在信息安全方面的应用主要体现在以下的3个方面：文件校验、数字签名、鉴权协议
程程序实现
// 说明：Hash函数（即散列函数）在程序设计中的应用目标 ------ 把一个对象通过某种转换机制对应到一个
//size_t类型（即unsigned long）的整型值。
// 而应用Hash函数的领域主要是 hash表（应用非常广）、密码等领域。
// 实现说明：
// ⑴、这里使用了函数对象以及泛型技术，使得对所有类型的对象（关键字）都适用。
// ⑵、常用类型有对应的偏特化，比如string、char*、各种整形等。
// ⑶、版本可扩展，如果你对某种类型有特殊的需要，可以在后面实现专门化。
// ⑷、以下实现一般放在头文件中，任何包含它的都可使用hash函数对象。
//------------------------------------实现------------------------------------------------
#include string
using std::string;
inlinesize_thash_str(const char* s)
{
unsigned long res = 0;
for (; *s; ++s)
res = 5 * res + *s;
returnsize_t(res);
}
template class Key
struct hash
{
size_toperator () (const Key k) const;
};
// 一般的对象，比如：vector queuestring ；的对象，需要强制转化
template class Key
size_thashKey::operator () (const Key k) const
{
size_tres = 0;
size_tlen = sizeof(Key);
const char* p = reinterpret_castconst char*(k);
while (len--)
{
res = (res1）^*p++;
}
return res;
}
// 偏特化
template
size_thash string ::operator () (const string str) const
{
return hash_str(str.c_str());
}
typedef char* PChar;
template
size_thashPChar::operator () (const PChar s) const
{
return hash_str(s);
}
typedef const char* PCChar;
template
size_thashPCChar::operator () (const PCChar s) const
{
return hash_str(s);
}
template size_t hashchar::operator () (const char x) const { return x; }
template size_t hashunsigned char::operator () (const unsigned char x) const { return x; }
template size_t hashsigned char::operator () (const signed char x) const { return x; }
template size_t hashshort::operator () (const short x) const { return x; }
template size_t hashunsigned short::operator () (const unsigned short x) const { return x; }
template size_t hashint::operator () (const int x) const { return x; }
template size_t hashunsigned int::operator () (const unsigned int x) const { return x; }
template size_t hashlong::operator () (const long x) const { return x; }
template size_t hashunsigned long::operator () (const unsigned long x) const { return x; }
// 使用说明：
//
// ⑴、使用时首先由于是泛型，所以要加上关键字类型。
//
// ⑵、其次要有一个函数对象，可以临时、局部、全局的，只要在作用域就可以。
//
// ⑶、应用函数对象作用于对应类型的对象。
//----------------------- hash函数使用举例 -------------------------
#include iostream
#include vector
#include string
using namespace std;
int main()
{
vectorstring vstr⑵；
vstr[0] = "sjw";
vstr[1] = "suninf";
hashstring strhash; // 局部函数对象
cout " Hash value: " strhash(vstr[0]) endl;
cout " Hash value: " strhash(vstr[1]) endl;
cout " Hash value: " hash vectorstring () (vstr) endl;
cout " Hash value: " hashint() （100） endl; // hashint() 临时函数对象
return 0;
}
相关问答
Q1: C语言实现哈希表的相关运算算法 编写程序实现哈希表的构造过程。
#define MaxSize 100 //定义最大哈希表长度
#define NULLKEY -1 //定义空关键字值
#define DELKEY -2 //定义被删关键字值
typedef int KeyType; //关键字类型
typedef char * InfoType; //其他数据类型
typedef struct
{
KeyType key; //关键字域
InfoType data; //其他数据域
int count; //探查次数域
} HashData;
typedef HashData HashTable[MaxSize]; //哈希表类型
void InsertHT(HashTable ha,int n,KeyType k,int p) //将关键字k插入到哈希表中
{
int i,adr;
adr=k % p;
if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中
{
ha[adr].key=k;
ha[adr].count=1;
}
else //发生冲突时采用线性探查法解决冲突
{
i=1; //i记录x[j]发生冲突的次数
do
{
adr=(adr+1) % p;
i++;
}
while (ha[adr].key!=NULLKEY ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
void CreateHT(HashTable ha,KeyType x[],int n,
Q2: 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;
cintemp-name;
cout"输入地址："endl;
cintemp-address;
cout"输入电话："endl;
cintemp-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;i20;i++)
{
phone[i]=new node;
phone[i]-next=NULL;
}
}
void create2() //新建节点
{
int i;
nam=new mingzi[20];
for(i=0;i20;i++)
{
nam[i]=new node;
nam[i]-next=NULL;
}
}
void list() //显示列表
{
int i;
node *p;
for(i=0;i20;i++)
{
p=phone[i]-next;
while(p)
{
coutp-name'_'p-address'_'p-numendl;
p=p-next;
}
}
}
void list2() //显示列表
{
int i;
node *p;
for(i=0;i20;i++)
{
p=nam[i]-next;
while(p)
{
coutp-name'_'p-address'_'p-numendl;
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)
coutq-name"_" q-address"_"q-numendl;
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)
coutq-name"_" q-address"_"q-numendl;
else cout"无此记录"endl;
}
void save() //保存用户信息
{
int i;
node *p;
for(i=0;i20;i++)
{
p=phone[i]-next;
while(p)
{
fstream iiout("out.txt", ios::out);
iioutp-name"_"p-address"_"p-numendl;
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();
cinsel;
if(sel==3)
{ cout"9号码查询，8姓名查询"endl;
int b;
cinb;
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;
}
Q3: 数据结构 哈希表，C语言解答
#include stdio.h
#includemalloc.h
#includestring.h
//#include
#define HASH_LEN 50 //哈希表的长度
#define M 47
#define NAME_NO 30 //人名的个数
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()
{ int i;
char *f;
int r,s0;
NameList[0].py="chenghongxiu";
NameList[1].py="yuanhao";
NameList[2].py="yangyang";
NameList[3].py="zhanghen";
NameList[4].py="chenghongxiu";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
NameList[8].py="chengdaoquan";
NameList[9].py="ludaoqing";
NameList[10].py="gongyunxiang";
NameList[11].py="sunzhenxing";
NameList[12].py="sunrongfei";
NameList[13].py="sunminglong";
NameList[14].py="zhanghao";
NameList[15].py="tianmiao";
NameList[16].py="yaojianzhong";
NameList[17].py="yaojianqing";
NameList[18].py="yaojianhua";
NameList[19].py="yaohaifeng";
NameList[20].py="chengyanhao";
NameList[21].py="yaoqiufeng";
NameList[22].py="qianpengcheng";
NameList[23].py="yaohaifeng";
NameList[24].py="bianyan";
NameList[25].py="linglei";
NameList[26].py="fuzhonghui";
NameList[27].py="huanhaiyan";
NameList[28].py="liudianqin";
NameList[29].py="wangbinnian";
for (i=0;iNAME_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; iHASH_LEN;i++)//哈希表的初始化
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for (i=0; iNAME_NO;)
{
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 //冲突
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪散列
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}i++;
}
}
/*-------------------------------------查找------------------------------------*/
void FindList()
{ int r;
char name[20]={0};
int s0=0;
int sum=1;
int adr;
int d;
printf("\n\n请输入姓名的拼音: "); //输入姓名
scanf("%s",name);
for ( r=0;r20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
adr=s0 % M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
else if (HashList[adr].k==0)
printf("无该记录!");
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //伪散列
sum=sum+1;
if (HashList[d].k==0)
{
printf("无记录! ");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}
/*--------------------------------显示哈希表----------------------------*/
void Display()
{int i;
float average=0;
printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式
for( i=0; i15; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n"); //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
// getch();
for( i=15; i30; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n");
// getch();
for( i=30; i40; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
//printf("按任意键继续显示...\n");
//getch();
for( i=40; i50; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
for (i=0;iHASH_LEN;i++)
{average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);
}
}
/*--------------------------------主函数----------------------------*/
void main()
{
/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题
HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色
*/
printf("\n------------------------哈希表的建立和查找----------------------");
InitNameList();
CreateHashList ();
while(1)
{ char ch1;
printf("\n\n");
printf(" 1. 显示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");
err:
scanf("%c",ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n请输入正确的选择!");
goto err;
}
}
}
