第一篇：(哈希查表法)通過學(xué)號找身份證號

/* 本C語言例程實現(xiàn)了一個簡單的哈希查表算法:

使用隨機函數(shù)生成100個學(xué)生std[100]的學(xué)號與身份證號,分別為studentNum與idNum 通過一個最大能容納1024個學(xué)生的哈希表mHashTable來存儲這100個學(xué)生的身份資料 利用第i個學(xué)生獨立的學(xué)號生成的索引號indexNum = Hash(std[i].studentNum),把對應(yīng)這個學(xué)生的資料存儲進哈希表mHashTable.std[indexNum] = std[i];如果需要通過某個學(xué)生的學(xué)號查詢他的身份證號(抑或其他數(shù)據(jù)比如名字年齡性別什么的),就不需要遍歷查詢100個學(xué)生的學(xué)號,只需要利用學(xué)號生成索引號indexNum,再把對應(yīng)mHashTable.std[indexNum] 學(xué)生結(jié)構(gòu)體里的數(shù)據(jù)都拿出來就行了.哈希查表算法的關(guān)鍵在于: 1.int Hash(int key)哈希函數(shù)的設(shè)計,如何利用特定的數(shù)據(jù)算出一個索引號,下面是常用算法,需要根據(jù)關(guān)鍵字長度,哈希表大小,哈希函數(shù)計算時間,記錄查找頻率等因素來確定使用什么算法.(key是關(guān)鍵字,在本程序中指代studentNum 中的關(guān)鍵數(shù)據(jù),我懶了就直接用這個studentNum當(dāng)關(guān)鍵字)1.1直接定址法: return a*key + b;1.2數(shù)字分析法: 1.3平方取中法: return(int)(((key*key)>>16)&0x000000ff)平方后使用中間12位的數(shù)據(jù)

1.4 折疊法:

1.5 取模法:return key%512 本程序采用這種方法 1.6 隨機數(shù)法:rand()函數(shù)等

2.索引號沖突的處理算法,比如我有學(xué)號311422與311934 ,兩者通過取模法生成的索引號都是 126,由于311422的資料已占據(jù)了mHashTable.std[126] ,該如何得出新的索引號以防止311934的資料復(fù)寫到mHashTable.std[126]里,下面是常用的算法: 2.1 開放定址法: indexNum = indexNum + di , di可以是1,2,3到k(k

2.2 再哈希法: indexNum = R*Hash(indexNum);2.3 鏈地址法:所有同索引號的成員資料都存進同一個線性鏈表里 2.4 公共溢出區(qū):把所有沖突者的資料悉數(shù)放入另一張哈希表

*/

#include #include #include

#define MAX 1024 #define EMPTY 0 #define EXIST-1 #define FULL-2

typedef struct { int studentNum;int idNum;}Student;

typedef struct{ Student *std;int sizeIndex;int studentCount;}HashTable;

int Hash(int studentNum){ return studentNum%(MAX/2);}

void InitHash(HashTable *H){ int i;H->std =(Student*)malloc(MAX*sizeof(Student));H->sizeIndex = MAX;H->studentCount = 0;for(i=0;i

H->std[i].studentNum = 0;

H->std[i].idNum = 0;} }

int SearchHash(HashTable H,int studentNum,int *indexHash){ int count;*indexHash = Hash(studentNum);for(count = 0;count < MAX, *indexHash < MAX;count+=1){

if(H.std[*indexHash].studentNum == 0)

return EMPTY;

if(H.std[*indexHash].studentNum == studentNum)

return EXIST;

*indexHash = *indexHash + 1;} return FULL;}

int InsertHash(HashTable *H,Student std){ int indexHash;int ret = SearchHash(*H,std.studentNum,&indexHash);switch(ret){

case EXIST:

return EXIST;

case EMPTY:

H->std[indexHash] = std;

H->studentCount ++;

break;

case FULL:

return FULL;} return ret;}

void PrintHash(HashTable *H){

int i;printf(“Start print HashTable:n”);for(i=0;i

if(H->std[i].studentNum!=0)

printf(“Hash : std[%d].studentNum = %d n”,i,H->std[i].studentNum,H->std[i].idNum);} printf(“End of HashTablen”);return;}

Student* InitStudent(int num){ int i;Student *std;std =(Student *)malloc(num*sizeof(Student));for(i=0;i

srand((unsigned int)(time(0)*i));

std[i].studentNum = rand();

srand((unsigned int)(time(0)*std[i].studentNum));

std[i].idNum = rand();} return std;}

void PrintStudent(Student* std,int num){ int i;for(i=0;i

printf(“std[%d].studentNum = %d, = %dn”,i,std[i].studentNum,std[i].idNum);} int main(){ int i;int studentNum;int indexHash;Student *std;HashTable mHashTable;

std = InitStudent(100);

InitHash(&mHashTable);

std[20].studentNum=std[10].studentNum+(MAX/2);i=10;printf(“std[%d].studentNum = %d, = %dn”,i,std[i].studentNum,std[i].idNum);i=20;printf(“std[%d].studentNum = %d, = %dn”,i,std[i].studentNum,std[i].idNum);//PrintStudent(std,100);

for(i=0;i<100;i++)

InsertHash(&mHashTable,std[i]);

PrintHash(&mHashTable);printf(“student count = %d n”,mHashTable.studentCount);while(1){

printf(“Please use the ”student number“ to find the ”id numer“ :”);

idNum idNum idNum

scanf(“%d”,&studentNum);

if(mHashTable.std[Hash(studentNum)].studentNum == 0)

printf(“Student number error!n”);

if(EXIST == SearchHash(mHashTable,studentNum,&indexHash))

printf(“nStudent number %d 's id number is %d nn”,mHashTable.std[indexHash].studentNum,mHashTable.std[indexHash].idNum);}

PrintHash(&mHashTable);

return 0;}