c語言hash函數

A. 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,

B. 用哈希表實現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. 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;

}

D. C語言里的hash有什麼作用具體說說。

散列函數，可以加密用。具體的找本數據結構書看看

E. 如何用c語言建立哈希表 存有序對

#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0 // 0為無記錄標志
#define N 10 // 數據元素個數
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
typedef int KeyType; // 設關鍵字域為整型

struct ElemType // 數據元素類型
{
KeyType key;
int ord;
};

int hashsize[]={11,19,29,37}; // 哈希表容量遞增表，一個合適的素數序列
int m=0; // 哈希表表長，全局變數
struct HashTable
{
ElemType *elem; // 數據元素存儲基址，動態分配數組
int count; // 當前數據元素個數
int sizeindex; // hashsize[sizeindex]為當前容量
};

Status InitHashTable(HashTable &H)// 操作結果: 構造一個空的哈希表
{ int i;
H.count=0; // 當前元素個數為0
H.sizeindex=0; // 初始存儲容量為hashsize[0]
m=hashsize[0];
H.elem=(ElemType*)malloc(m*sizeof(ElemType));
if(!H.elem)
exit(OVERFLOW); // 存儲分配失敗
for(i=0;i<m;i++)
H.elem[i].key=NULLKEY; // 未填記錄的標志
return OK;
}

void DestroyHashTable(HashTable &H)// 初始條件: 哈希表H存在。操作結果: 銷毀哈希表H
{ free(H.elem);
H.elem=NULL;
H.count=0;
H.sizeindex=0;
}

unsigned Hash(KeyType K)// 一個簡單的哈希函數(m為表長，全局變數)
{ return K%m;
}

void collision(int &p,int d) // 線性探測再散列
{
p=(p+d)%m;// 開放定址法處理沖突
}

Status SearchHash(HashTable H,KeyType K,int &p,int &c)// 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據
{ p=Hash(K); // 求得哈希地址
while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))
{ // 該位置中填有記錄．並且關鍵字不相等
c++;
if(c<m)
collision(p,c); // 求得下一探查地址p
else
break;
}
if EQ(K,H.elem[p].key)
return SUCCESS; // 查找成功，p返回待查數據元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置
}

Status InsertHash(HashTable &,ElemType); // 對函數的聲明
void RecreateHashTable(HashTable &H) // 重建哈希表
{ int i,count=H.count;
ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
p=elem;
printf("重建哈希表\n");
for(i=0;i<m;i++) // 保存原有的數據到elem中
if((H.elem+i)->key!=NULLKEY) // 該單元有數據
*p++=*(H.elem+i);
H.count=0;
H.sizeindex++; // 增大存儲容量
m=hashsize[H.sizeindex];
p=(ElemType*)realloc(H.elem,m*sizeof(ElemType));
if(!p)
exit(OVERFLOW); // 存儲分配失敗
H.elem=p;
for(i=0;i<m;i++)
H.elem[i].key=NULLKEY; // 未填記錄的標志(初始化)
for(p=elem;p<elem+count;p++) // 將原有的數據按照新的表長插入到重建的哈希表中
InsertHash(H,*p);
}

Status InsertHash(HashTable &H,ElemType e)// 查找不成功時插入數據元素e到開放定址哈希表H中，並返回OK；
{ int c,p;
c=0;
if(SearchHash(H,e.key,p,c)) // 表中已有與e有相同關鍵字的元素
return DUPLICATE;
else if(c<hashsize[H.sizeindex]/2) // 沖突次數c未達到上限,(c的閥值可調)
{ // 插入e
H.elem[p]=e;
++H.count;
return OK;
}
else
RecreateHashTable(H); // 重建哈希表
return ERROR;
}

void TraverseHash(HashTable H,void(*Vi)(int,ElemType))// 按哈希地址的順序遍歷哈希表
{
printf("哈希地址0～%d\n",m-1);
for(int i=0;i<m;i++)
if(H.elem[i].key!=NULLKEY) // 有數據
Vi(i,H.elem[i]);
}

Status Find(HashTable H,KeyType K,int &p)// 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據
{ int c=0;
p=Hash(K); // 求得哈希地址
while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))// 該位置中填有記錄．並且關鍵字不相等
{ c++;
if(c<m)
collision(p,c); // 求得下一探查地址p
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
if EQ(K,H.elem[p].key)
return SUCCESS; // 查找成功，p返回待查數據元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}

void print(int p,ElemType r)//輸出
{
printf("address=%d (%d,%d)\n",p,r.key,r.ord);
}

void main()
{
ElemType r[N]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{60,9},{13,10}};
HashTable h;
int i,p;
Status j;
KeyType k;
InitHashTable(h);
for(i=0;i<N-1;i++)// 插入前N-1個記錄
{
j=InsertHash(h,r[i]);
if(j==DUPLICATE)
printf("表中已有關鍵字為%d的記錄，無法再插入記錄(%d,%d)\n",r[i].key,r[i].key,r[i].ord);
}
printf("按哈希地址的順序遍歷哈希表:\n");
TraverseHash(h,print);
printf("請輸入待查找記錄的關鍵字: ");
scanf("%d",&k);
j=Find(h,k,p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("沒找到\n");
j=InsertHash(h,r[i]); // 插入第N個記錄
if(j==ERROR) // 重建哈希表
j=InsertHash(h,r[i]); // 重建哈希表後重新插入
printf("按哈希地址的順序遍歷重建後的哈希表:\n");
TraverseHash(h,print);
printf("請輸入待查找記錄的關鍵字: ");
scanf("%d",&k);
j=Find(h,k,p);
if(j==SUCCESS)
print(p,h.elem[p]);
else
printf("沒找到\n");
DestroyHashTable(h);
}

F. 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);
}

G. C語言哈希表，為什麼輸入查找名字就沒了音訊（點進來有詳細內容喲~）

HASH函數里 scanf("%s",&namekey); 去掉namekey前的&號。namekey已經是一個指針了，不需要再取地址。

H. 用C語言設計本班級花名冊的哈希表並提供查找界面。還要有HASH函數和解決沖突的方法

首先 你要明白方法裡面的變數是沒有傳值到外面的
也就是 局部變數的關系
scanf("%f%f%f",&x,&y,&z);
max(x,y,z);
printf("%f",x);
這里你的max 不會傳值到x裡面
你可以這樣
x=max(x,y,z);
printf("%f",x);

或者用指針做形參實現傳值

I. C語言版數據結構哈希演算法題：設m=16,HASH函數為H（key）=key mod 13,現採用再哈希法Hi=RHi(key）處理沖突

應該是這個意思：
第一次沖突就是散列的位置+1，這次發生沖突了就繼續第二次
第二次用的是平方取中，55^2= 3025，當然第二次沖突的RH2就是02了，答案(2)

J. 希望大家幫幫我啊！！！C語言 哈希表生成及哈希查找演算法 輸入：待哈希數據序列 功能要求：輸出哈希方法和

你看看這個哈希演算法吧、、貌似。，，也差不多咯

#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
typedef int KeyType;
typedef struct /*元素類型定義*/
{
KeyType key; /*關鍵字*/
int hi; /*沖突次數*/
}DataType;
typedef struct /*哈希表類型定義*/
{
DataType *data;
int tableSize; /*哈希表的長度*/
int curSize; /*表中關鍵字個數*/
}HashTable;
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n);
int SearchHash(HashTable H,KeyType k);
void DisplayHash(HashTable H,int m);
void HashASL(HashTable H,int m);
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n)
/*構造一個空的哈希表，並處理沖突*/
{
int i,sum,addr,di,k=1;
(*H).data=(DataType*)malloc(m*sizeof(DataType));/*為哈希表分配存儲空間*/
if(!(*H).data)
exit(-1);
for(i=0;i<m;i++) /*初始化哈希表*/
{
(*H).data[i].key=-1;
(*H).data[i].hi=0;
}
for(i=0;i<n;i++) /*求哈希函數地址並處理沖突*/
{
sum=0; /*沖突的次數*/
addr=hash[i]%p; /*利用除留余數法求哈希函數地址*/
di=addr;
if((*H).data[addr].key==-1) /*如果不沖突則將元素存儲在表中*/
{
(*H).data[addr].key=hash[i];
(*H).data[addr].hi=1;
}
else /*用線性探測再散列法處理沖突*/
{
do
{
di=(di+k)%m;
sum+=1;
} while((*H).data[di].key!=-1);
(*H).data[di].key=hash[i];
(*H).data[di].hi=sum+1;
}
}
(*H).curSize=n; /*哈希表中關鍵字個數為n*/
(*H).tableSize=m; /*哈希表的長度*/
}
int SearchHash(HashTable H,KeyType k)
/*在哈希表H中查找關鍵字k的元素*/
{
int d,d1,m;
m=H.tableSize;
d=d1=k%m; /*求k的哈希地址*/
while(H.data[d].key!=-1)
{
if(H.data[d].key==k)/*如果是要查找的關鍵字k，則返回k的位置*/
return d;
else /*繼續往後查找*/
d=(d+1)%m;
if(d==d1) /*如果查找了哈希表中的所有位置，沒有找到返回0*/
return 0;
}
return 0; /*該位置不存在關鍵字k*/
}
void DisplayHash(HashTable H,int m)
/*輸出哈希表*/
{
int i;
printf("哈希表地址：");
for(i=0;i<m;i++)
printf("%-5d",i);
printf("\n");
printf("關鍵字key: ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].key);
printf("\n");
printf("沖突次數： ");
for(i=0;i<m;i++)
printf("%-5d",H.data[i].hi);
printf("\n");

}
void HashASL(HashTable H,int m)
/*求哈希表的平均查找長度*/
{
float average=0;
int i;
for(i=0;i<m;i++)
average=average+H.data[i].hi;
average=average/H.curSize;
printf("平均查找長度ASL=%.2f",average);
printf("\n");
}

void main()
{
int hash[]={23,35,12,56,123,39,342,90};
int m=11,p=11,n=8,pos;
KeyType k;
HashTable H;
CreateHashTable(&H,m,p,hash,n);
DisplayHash(H,m);
k=123;
pos=SearchHash(H,k);
printf("關鍵字%d在哈希表中的位置為：%d\n",k,pos);
HashASL(H,m);
}