(哈希查表法)通过学号找身份证号（优秀范文五篇）

第一篇：(哈希查表法)通过学号找身份证号

/* 本C语言例程实现了一个简单的哈希查表算法:

使用随机函数生成100个学生std[100]的学号与身份证号,分别为studentNum与idNum 通过一个最大能容纳1024个学生的哈希表mHashTable来存储这100个学生的身份资料 利用第i个学生独立的学号生成的索引号indexNum = Hash(std[i].studentNum),把对应这个学生的资料存储进哈希表mHashTable.std[indexNum] = std[i];如果需要通过某个学生的学号查询他的身份证号(抑或其他数据比如名字年龄性别什么的),就不需要遍历查询100个学生的学号,只需要利用学号生成索引号indexNum,再把对应mHashTable.std[indexNum] 学生结构体里的数据都拿出来就行了.哈希查表算法的关键在于: 1.int Hash(int key)哈希函数的设计,如何利用特定的数据算出一个索引号,下面是常用算法,需要根据关键字长度,哈希表大小,哈希函数计算时间,记录查找频率等因素来确定使用什么算法.(key是关键字,在本程序中指代studentNum 中的关键数据,我懒了就直接用这个studentNum当关键字)1.1直接定址法: return a*key + b;1.2数字分析法: 1.3平方取中法: return(int)(((key*key)>>16)&0x000000ff)平方后使用中间12位的数据

1.4 折叠法:

1.5 取模法:return key%512 本程序采用这种方法 1.6 随机数法:rand()函数等

2.索引号冲突的处理算法,比如我有学号311422与311934 ,两者通过取模法生成的索引号都是 126,由于311422的资料已占据了mHashTable.std[126] ,该如何得出新的索引号以防止311934的资料复写到mHashTable.std[126]里,下面是常用的算法: 2.1 开放定址法: indexNum = indexNum + di , di可以是1,2,3到k(k

2.2 再哈希法: indexNum = R*Hash(indexNum);2.3 链地址法:所有同索引号的成员资料都存进同一个线性链表里 2.4 公共溢出区:把所有冲突者的资料悉数放入另一张哈希表

*/

#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;}