#define MaxSize 100 //定義最大哈希表長度
創(chuàng)新互聯(lián)從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站制作、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元滎經(jīng)做網(wǎng)站,已為上家服務(wù),為滎經(jīng)各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108
#define NULLKEY -1 //定義空關(guān)鍵字值
#define DELKEY -2 //定義被刪關(guān)鍵字值
typedef int KeyType; //關(guān)鍵字類型
typedef char * InfoType; //其他數(shù)據(jù)類型
typedef struct
{
KeyType key; //關(guān)鍵字域
InfoType data; //其他數(shù)據(jù)域
int count; //探查次數(shù)域
} HashData;
typedef HashData HashTable[MaxSize]; //哈希表類型
void InsertHT(HashTable ha,int n,KeyType k,int p) //將關(guān)鍵字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 //發(fā)生沖突時(shí)采用線性探查法解決沖突
{
i=1; //i記錄x[j]發(fā)生沖突的次數(shù)
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,
/#include "iostream.h"
#include iostream
#include "string.h"
#include "fstream"
#define NULL 0
unsigned int key;
unsigned int key2;
int *p;
struct node //建節(jié)點(diǎn)
{
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]) //哈希函數(shù)
{
int i = 3;
key=(int)num[2];
while(num[i]!=NULL)
{
key+=(int)num[i];
i++;
}
key=key%20;
}
void hash2(char name[8]) //哈希函數(shù)
{
int i = 1;
key2=(int)name[0];
while(name[i]!=NULL)
{
key2+=(int)name[i];
i++;
}
key2=key2%20;
}
node* input() //輸入節(jié)點(diǎn)
{
node *temp;
temp = new node;
temp-next=NULL;
cout"輸入姓名："endl;
cintemp-name;
cout"輸入地址："endl;
cintemp-address;
cout"輸入電話："endl;
cintemp-num;
return temp;
}
int apend() //添加節(jié)點(diǎn)
{
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() //新建節(jié)點(diǎn)
{
int i;
phone=new pnode[20];
for(i=0;i20;i++)
{
phone[i]=new node;
phone[i]-next=NULL;
}
}
void create2() //新建節(jié)點(diǎn)
{
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.號(hào)碼散列"endl;
cout"5.清空記錄"endl;
cout"6.保存記錄"endl;
cout"7.退出系統(tǒng)"endl;
}
int main()
{
char num[11];
char name[8];
create();
create2() ;
int sel;
while(1)
{
menu();
cinsel;
if(sel==3)
{ cout"9號(hào)碼查詢，8姓名查詢"endl;
int b;
cinb;
if(b==9)
{ cout"請(qǐng)輸入電話號(hào)碼:"endl;
cin num;
cout"輸出查找的信息:"endl;
find(num);
}
else
{ cout"請(qǐng)輸入姓名:"endl;
cin name;
cout"輸出查找的信息:"endl;
find2(name);}
}
if(sel==2)
{ cout"姓名散列結(jié)果:"endl;
list2();
}
if(sel==0)
{ cout"請(qǐng)輸入要添加的內(nèi)容:"endl;
apend();
}
if(sel==4)
{ cout"號(hào)碼散列結(jié)果:"endl;
list();
}
if(sel==5)
{ cout"列表已清空:"endl;
create();
create2();
}
if(sel==6)
{ cout"通信錄已保存:"endl;
save();
}
if(sel==7) return 0;
}
return 0;
}
#include?stdio.h#include?stdlib.h//這里我自己設(shè)計(jì)一個(gè)hash算法來快速查找一堆數(shù)字中相等的數(shù)字，這也許是最接近原理的算法了//一個(gè)整數(shù)整除27后的來作為hash函數(shù)//定義一個(gè)保存實(shí)際數(shù)據(jù)的結(jié)構(gòu)體節(jié)點(diǎn)struct?data_node{????int?num;????int?count;????struct?data_node?*next;};//定義一個(gè)結(jié)構(gòu)體時(shí)hash表的一部分typedef?struct{????int?key;?//余數(shù)????struct?data_node?*p;?//鏈表的頭指針}?hash_node;#define?HASH_SIZE?27int?do_hash(int?num)?//hash表來求余數(shù)，這樣就可以了{(lán)????return?num%HASH_SIZE;}//初始化//添加數(shù)字//更新數(shù)字//刪除數(shù)字//查找數(shù)字hash_node?HashTable[HASH_SIZE];?//這里申明一個(gè)hashtable的數(shù)組//初始化函數(shù)，需要做的事將key復(fù)制為null，將p指針指向null,返回一個(gè)頭指針來指向這個(gè)hashtablevoid?InitHashTable(hash_node?*HashTable)
{????//進(jìn)行參數(shù)的校驗(yàn)????for(int?i=0;iHASH_SIZE;i++)
{
HashTable[i].key?=?0;????????HashTable[i].p?=NULL;????}
}//保存到這個(gè)鏈表中//如果這個(gè)鏈表是空的話，就作為頭指針，如果這個(gè)鏈表不為空，則添加到吧數(shù)字添加到末尾int?savedata(struct?data_node?**head,int?num)
{????struct?data_node?*tmp_p?=?*head;????struct?data_node?*p?=?(struct?data_node?*)malloc(sizeof(struct?data_node));????if(p?==?NULL)????????return?0;????if(*head?==?NULL)
{
*head?=?p;????????p-count?=?1;????????p-num?=?num;????????p-next?=?NULL;????}????else?//如果不為空，則這個(gè)時(shí)候應(yīng)該添加到鏈表末尾????{????????while(tmp_p?!=?NULL)//如果存在，則將這個(gè)節(jié)點(diǎn)的count加1就可以了????????{????????????if(tmp_p-num?==?num)
{
free(p);????????????????++tmp_p-count?;????????????????return?0;????????????}????????????if(tmp_p-next?==?NULL)????????????????break;????????????tmp_p?=?tmp_p-next;????????}
tmp_p-next?=?p;????????p-count?=1;????????p-num?=?num;????????p-next?=?NULL;????}????return?0;}//添加數(shù)字//將這個(gè)數(shù)字經(jīng)過hash求出結(jié)果，然后再保存到相應(yīng)的鏈表中//返回真或者假就可以了int?add_hash(hash_node?*HashTable,int?num)
{????int?mod?=?do_hash(num);????return?savedata(HashTable[mod].p,num);}int?main()
{????int?num?=?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);????//在這里我們可以發(fā)現(xiàn)一個(gè)好的hash函數(shù)是多么的重要，如果hash函數(shù)不好造成很多沖突的話，效率并不會(huì)提高很多的，理想的情況是沖突幾乎沒有????//這也就是設(shè)計(jì)hash函數(shù)的精髓所在????return?0;}
Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。
HASH主要用于信息安全領(lǐng)域中加密算法，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼里，叫做HASH值. 也可以說，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個(gè)方面：文件校驗(yàn)、數(shù)字簽名、鑒權(quán)協(xié)議
程程序?qū)崿F(xiàn)
// 說明：Hash函數(shù)（即散列函數(shù)）在程序設(shè)計(jì)中的應(yīng)用目標(biāo) ------ 把一個(gè)對(duì)象通過某種轉(zhuǎn)換機(jī)制對(duì)應(yīng)到一個(gè)
//size_t類型（即unsigned long）的整型值。
// 而應(yīng)用Hash函數(shù)的領(lǐng)域主要是 hash表（應(yīng)用非常廣）、密碼等領(lǐng)域。
// 實(shí)現(xiàn)說明：
// ⑴、這里使用了函數(shù)對(duì)象以及泛型技術(shù)，使得對(duì)所有類型的對(duì)象（關(guān)鍵字）都適用。
// ⑵、常用類型有對(duì)應(yīng)的偏特化，比如string、char*、各種整形等。
// ⑶、版本可擴(kuò)展，如果你對(duì)某種類型有特殊的需要，可以在后面實(shí)現(xiàn)專門化。
// ⑷、以下實(shí)現(xiàn)一般放在頭文件中，任何包含它的都可使用hash函數(shù)對(duì)象。
//------------------------------------實(shí)現(xiàn)------------------------------------------------
#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;
};
// 一般的對(duì)象，比如：vector queuestring ；的對(duì)象，需要強(qiáng)制轉(zhuǎn)化
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; }
// 使用說明：
//
// ⑴、使用時(shí)首先由于是泛型，所以要加上關(guān)鍵字類型。
//
// ⑵、其次要有一個(gè)函數(shù)對(duì)象，可以臨時(shí)、局部、全局的，只要在作用域就可以。
//
// ⑶、應(yīng)用函數(shù)對(duì)象作用于對(duì)應(yīng)類型的對(duì)象。
//----------------------- hash函數(shù)使用舉例 -------------------------
#include iostream
#include vector
#include string
using namespace std;
int main()
{
vectorstring vstr⑵；
vstr[0] = "sjw";
vstr[1] = "suninf";
hashstring strhash; // 局部函數(shù)對(duì)象
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() 臨時(shí)函數(shù)對(duì)象
return 0;
}
重慶分公司
重慶分公司
