PTA 查找算法设计 3 哈希表查找算法设计

作者 张鏖烽单位 湖南工程学院计算机与通信学院编程实现哈希表创建和查找函数(1) int PrimeNum(int n)求小于等于n的最大质数(2) CreateHash(A,n,H,m,p)创建哈希表HH[]数组初始化为INF(3) SearchHash(H,m,pkey)在哈希表H中查找关键字key函数接口定义在这里描述函数接口。例如 int PrimeNum(int n); void CreateHash(int A[],int n,int H[],int m,int p); int SearchHash(int H[],int m,int key,int p);其中A[]为关键字数组n为关键字序列长度H[]为哈希表数组m为哈希表数组容量mn2,p为小于等于m的质数key为要查找的关键字裁判测试程序样例在这里给出函数被调用进行测试的例子。例如 #includestdio.h #includemalloc.h #define MaxSize 100 #define INF 3478569 int PrimeNum(int n);//求一个小于等于n的质数 void CreateHash(int A[],int n,int H[],int m,int p);//创建哈希表HH[]数组初始化为INF int SearchHash(int H[],int m,int key,int p);//在哈希表H中查找关键字key int main() { int A[MaxSize]; int n,key,i,p,m; //输入关键字序列长度n scanf(%d,n); mn2; int H[m]; //求小于等于m的质数p pPrimeNum(m); //输入关键字序列 for(i0;in;i) scanf(%d,A[i]); //创建哈希表H CreateHash(A,n,H,m,p); //输出哈希表 printf(哈希数组H[]); for(i0;im;i) { if(H[i]INF) printf(%d ,H[i]); else printf(INF ); } printf(\n); //输入待查找关键字key scanf(%d,key); printf(\n查找关键字%d需要依次比较,key); iSearchHash(H,m,key,p); if(i1) printf(关键字%d查找成功,key); else printf(关键字%d查找失败,key); return 0; } /* 请在这里填写答案 */输入样例在这里给出一组输入。例如第1行输入关键字序列长度n第2行输入关键字序列第3行输入待查找关键字key9 19 24 16 29 37 48 56 34 89 48输出样例在这里给出相应的输出。例如哈希数组H[]INF 56 24 34 37 16 48 29 19 89 INF 查找关键字48需要依次比较37 16 48 关键字48查找成功参考代码int PrimeNum(int n){ if(n2) return 0; for(int in;i2;i--){ int isPrime1; for(int j2;j*ji;j) if(i%j0) {isPrime0;break;} if(isPrime)return i; } return 2; } void CreateHash(int A[],int n,int H[],int m,int p){ for(int i0;im;i)H[i]INF; for(int i0;in;i){ int aA[i]%p; while(H[a]!INF)a(a1)%m; H[a]A[i]; } } int SearchHash(int H[],int m,int key,int p){ int akey%p,oa; printf(H[a]INF?INF :%d ,H[a]); if(H[a]key)return 1; a(a1)%m; while(H[a]!INFa!o){ printf(H[a]INF?INF :%d ,H[a]); if(H[a]key)return 1; a(a1)%m; } return 0; }